Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Wed, 26 Oct 2022 12:03:36 -0700
From:   Luis Chamberlain <mcgrof@kernel.org>
To:     "Leizhen (ThunderTown)" <thunder.leizhen@huawei.com>
Cc:     Josh Poimboeuf <jpoimboe@kernel.org>,
        Jiri Kosina <jikos@kernel.org>,
        Miroslav Benes <mbenes@suse.cz>,
        Petr Mladek <pmladek@suse.com>,
        Joe Lawrence <joe.lawrence@redhat.com>,
        live-patching@vger.kernel.org, linux-kernel@vger.kernel.org,
        Masahiro Yamada <masahiroy@kernel.org>,
        Alexei Starovoitov <ast@kernel.org>,
        Jiri Olsa <jolsa@kernel.org>,
        Kees Cook <keescook@chromium.org>,
        Andrew Morton <akpm@linux-foundation.org>,
        linux-modules@vger.kernel.org,
        Steven Rostedt <rostedt@goodmis.org>,
        Ingo Molnar <mingo@redhat.com>
Subject: Re: [PATCH v7 00/11] kallsyms: Optimizes the performance of lookup
 symbols
Message-ID: <Y1mEiIvbld4SX1lx@bombadil.infradead.org>
References: <20221017064950.2038-1-thunder.leizhen@huawei.com>
 <Y0/nEngJF6bbINEx@bombadil.infradead.org>
 <ad9e51c6-f77d-d9e9-9c13-42fcbbde7147@huawei.com>
 <Y1gisUFzgt1D1Jle@bombadil.infradead.org>
 <77f1c8f0-5e67-0e57-9285-15ba613044fb@huawei.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <77f1c8f0-5e67-0e57-9285-15ba613044fb@huawei.com>
Sender: Luis Chamberlain <mcgrof@infradead.org>
Precedence: bulk

On Wed, Oct 26, 2022 at 02:44:36PM +0800, Leizhen (ThunderTown) wrote:
> On 2022/10/26 1:53, Luis Chamberlain wrote:
> > This answers how we don't use a hash table, the question was *should* we
> > use one?
> 
> I'm not the original author, and I can only answer now based on my understanding. Maybe
> the original author didn't think of the hash method, or he has weighed it out.
> 
> Hash is a good solution if only performance is required and memory overhead is not
> considered. Using hash will increase the memory size by up to "4 * kallsyms_num_syms +
> 4 * ARRAY_SIZE(hashtable)" bytes, kallsyms_num_syms is about 1-2 million.
> 
> Because I don't know what hash algorithm will be used, the cost of generating the
> hash value corresponding to the symbol name is unknown now. But I think it's gonna
> be small. But it definitely needs a simpler algorithm, the tool needs to implement
> the same hash algorithm.

For instance, you can look at evaluating if alloc_large_system_hash() would help.

  Luis