netdev - Re: [PATCH net-next] net: rfs: hash function change

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <CANn89iKz2PfhP1qdSqaV5bG0YncDFW1s=5MiimUR2TYgKqpZ9w@mail.gmail.com>
Date: Mon, 24 Mar 2025 15:35:39 +0100
From: Eric Dumazet <edumazet@...gle.com>
To: Simon Horman <horms@...nel.org>
Cc: "David S. Miller" <davem@...emloft.net>, Jakub Kicinski <kuba@...nel.org>, 
	Paolo Abeni <pabeni@...hat.com>, Willem de Bruijn <willemb@...gle.com>, 
	Kuniyuki Iwashima <kuniyu@...zon.com>, Neal Cardwell <ncardwell@...gle.com>, netdev@...r.kernel.org, 
	eric.dumazet@...il.com, Tom Herbert <tom@...bertland.com>
Subject: Re: [PATCH net-next] net: rfs: hash function change

On Mon, Mar 24, 2025 at 3:16 PM Simon Horman <horms@...nel.org> wrote:
>
> On Fri, Mar 21, 2025 at 05:13:09PM +0000, Eric Dumazet wrote:
> > RFS is using two kinds of hash tables.
> >
> > First one is controled by /proc/sys/net/core/rps_sock_flow_entries = 2^N
> > and using the N low order bits of the l4 hash is good enough.
> >
> > Then each RX queue has its own hash table, controled by
> > /sys/class/net/eth1/queues/rx-$q/rps_flow_cnt = 2^X
> >
> > Current hash function, using the X low order bits is suboptimal,
> > because RSS is usually using Func(hash) = (hash % power_of_two);
> >
> > For example, with 32 RX queues, 6 low order bits have no entropy
> > for a given queue.
> >
> > Switch this hash function to hash_32(hash, log) to increase
> > chances to use all possible slots and reduce collisions.
> >
> > Signed-off-by: Eric Dumazet <edumazet@...gle.com>
> > Cc: Tom Herbert <tom@...bertland.com>
>
> Reviewed-by: Simon Horman <horms@...nel.org>
>
> ...
>
> > @@ -4903,13 +4908,13 @@ bool rps_may_expire_flow(struct net_device *dev, u16 rxq_index,
> >
> >       rcu_read_lock();
> >       flow_table = rcu_dereference(rxqueue->rps_flow_table);
> > -     if (flow_table && flow_id <= flow_table->mask) {
> > +     if (flow_table && flow_id < (1UL << flow_table->log)) {
> >               rflow = &flow_table->flows[flow_id];
> >               cpu = READ_ONCE(rflow->cpu);
> >               if (READ_ONCE(rflow->filter) == filter_id && cpu < nr_cpu_ids &&
> >                   ((int)(READ_ONCE(per_cpu(softnet_data, cpu).input_queue_head) -
> >                          READ_ONCE(rflow->last_qtail)) <
> > -                  (int)(10 * flow_table->mask)))
> > +                  (int)(10 << flow_table->log)))
>
> I am assuming that we don't care that (10 * flow_table->mask) and
> (10 << flow_table->log) are close but not exactly the same.
>
> e.g. mask = 0x3f => log = 6

Yes, I doubt we care.
The 10 constant seems quite arbitrary anyway.

We also could keep both fields in flow_table : ->log and ->mask

I chose to remove ->mask mostly to detect all places needing scrutiny
for the hash function change.