linux-kernel - Re: [PATCH] rhashtable: add likely() to __rht

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CADxym3bFCuiDWtpEVVSpEt9wmO_6cigCjz8385Ty2h0F8_4sWw@mail.gmail.com>
Date: Fri, 26 Sep 2025 14:04:04 +0800
From: Menglong Dong <menglong8.dong@...il.com>
To: NeilBrown <neil@...wn.name>
Cc: Herbert Xu <herbert@...dor.apana.org.au>, tgraf@...g.ch, 
	linux-crypto@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] rhashtable: add likely() to __rht_ptr()

On Fri, Sep 26, 2025 at 8:29 AM NeilBrown <neilb@...mail.net> wrote:
>
> On Wed, 24 Sep 2025, Menglong Dong wrote:
> > On Tue, Sep 23, 2025 at 7:31 PM NeilBrown <neilb@...mail.net> wrote:
> > >
> > > On Tue, 23 Sep 2025, Menglong Dong wrote:
> > > > On Tue, Sep 23, 2025 at 2:36 PM Herbert Xu <herbert@...dor.apana.org.au> wrote:
> > > > >
> > > > > Menglong Dong <menglong8.dong@...il.com> wrote:
> > > > > > In the fast path, the value of "p" in __rht_ptr() should be valid.
> > > > > > Therefore, wrap it with a "likely". The performance increasing is tiny,
> > > > > > but it's still worth to do it.
> > > > > >
> > > > > > Signed-off-by: Menglong Dong <dongml2@...natelecom.cn>
> > > > > > ---
> > > > > > include/linux/rhashtable.h | 5 +++--
> > > > > > 1 file changed, 3 insertions(+), 2 deletions(-)
> > > > >
> > > > > It's not obvious that rht_ptr would be non-NULL.  It depends on the
> > > > > work load.  For example, if you're doing a lookup where most keys
> > > > > are non-existent then it would most likely be NULL.
> > > >
> > > > Yeah, I see. In my case, the usage of the rhashtable will be:
> > > > add -> lookup, and rht_ptr is alway non-NULL. You are right,
> > > > it can be NULL in other situations, and it's not a good idea to
> > > > use likely() here ;)
> > >
> > > Have you measured a performance increase?  How tiny is it?
> > >
> > > It might conceivably make sense to have a rhashtable_lookup_likely() and
> > > rhashtable_lookup_unlikely(), but concrete evidence of the benefit would
> > > be needed.
> >
> > I made a more accurate bench testing:  call the rhashtable_lookup()
> > 100000000 times.
> >
> > Without the likely(), it cost  123697645ns. And with the likely(), only
> > 84507668ns.
>
> a 30% speedup is impressive, even though it is a micro-benchmark.
>
> >
> > I add the likely() not only to the __rht_ptr(), but also rht_for_each_rcu_from()
> > and rhashtable_lookup().
>
> I suggest you create a patch which adds rhashtable_lookup_likely(),
> __rhashtable_lookup_likely(), rht_for_each_rcu_from_likely(),
> rht_ptr_rcu_likely() etc.
> So that no existing code changes, but the new function uses likely
> everywhere that you think is important.

OK, sounds great! I'll send such a patch.

>
> I had a bit of a look at callers of rhashtable_lookup().  Some return
> -EEXIST if they find something. Other return -ENOENT if they don't.
> Using rhasthable_lookup_likely() for those that return -ENOENT probably
> makes sense.

I'll do it.

Thanks!
Menglong Dong

>
> Thanks,
> NeilBrown
>
>
> >
> > Below is the part code of the testing:
> >
> >     for (i = 0; i < num_elems; i++) {
> >         objs[i] = kmalloc(sizeof(**objs), GFP_KERNEL);
> >         KUNIT_ASSERT_NOT_ERR_OR_NULL(test, objs[i]);
> >         objs[i]->key = i;
> >         INIT_RHT_NULLS_HEAD(objs[i]->node.next);
> >         ret = rhashtable_insert_fast(&ht, &objs[i]->node, bench_params);
> >         KUNIT_ASSERT_EQ(test, ret, 0);
> >     }
> >
> >     /* for CPU warm up */
> >     for (i = 0; i < 1000000000; i++) {
> >         u32 key = 0;
> >         struct bench_obj *found;
> >
> >         found = rhashtable_lookup(&ht, &key, bench_params);
> >         KUNIT_ASSERT_NOT_ERR_OR_NULL(test, found);
> >         KUNIT_ASSERT_EQ(test, found->key, key);
> >     }
> >
> >     rcu_read_lock();
> >     t0 = ktime_get();
> >     for (i = 0; i < 100000000; i++) {
> >         u32 key = 0;
> >         struct bench_obj *found;
> >
> >         found = rhashtable_lookup(&ht, &key, bench_params);
> >         if (unlikely(!found)) {
> >             pr_info("error!\n");
> >             break;
> >         }
> >     }
> >     t1 = ktime_get();
> >     rcu_read_unlock();
> >
> > >
> > > Thanks,
> > > NeilBrown
> >
>