netdev - Re: tc: u32: Wrong sample hash calculation

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: <8df2e0cc-3de4-7084-6859-df1559921fc7@mojatatu.com>
Date:   Wed, 20 Jan 2021 08:55:11 -0500
From:   Jamal Hadi Salim <jhs@...atatu.com>
To:     Phil Sutter <phil@....cc>,
        Stephen Hemminger <stephen@...workplumber.org>,
        netdev@...r.kernel.org, Cong Wang <xiyou.wangcong@...il.com>,
        Jiri Pirko <jiri@...nulli.us>,
        Russell Stuart <russell-lartc@...art.id.au>
Subject: Re: tc: u32: Wrong sample hash calculation

Hi,

On 2021-01-18 6:29 a.m., Phil Sutter wrote:
> Hi!
> 
> Playing with u32 filter's hash table I noticed it is not possible to use
> 'sample' option with keys larger than 8bits to calculate the hash
> bucket. 


I have mostly used something like: ht 2:: sample ip protocol 1 0xff
Hoping this is continuing to work.

I feel i am missing something basic in the rest of your email:
Sample is a user space concept i.e it is used to instruct the
kernel what table/bucket to insert the node into. This computation
is done in user space. The kernel should just walk the nodes in
the bucket and match.
Reminder: you can only have 256 buckets (8 bit representation).
Could that be the contributing factor?
Here's an example of something which is not 8 bit that i found in
an old script that should work (but I didnt test in current kernels).
ht 2:: sample u32 0x00000800 0x0000ff00 at 12
We are still going to extract only 8 bits for the bucket.

Can you provide an example of what wouldnt work?

cheers,
jamal

> Turns out key hashing in kernel and iproute2 differ:
> 
> * net/sched/cls_u32.c (kernel) basically does:
> 
> hash = ntohl(key & mask);
> hash >>= ffs(ntohl(mask)) - 1;
> hash &= 0xff;
> hash %= divisor;
> 
> * while tc/f_u32.c (iproute2) does:
> 
> hash = key & mask;
> hash ^= hash >> 16;
> hash ^= hash >> 8;
> hash %= divisor;
> 
> In iproute2, the code changed in 2006 with commit 267480f55383c
> ("Backout the 2.4 utsname hash patch."), here's the relevant diff:
> 
>    hash = sel2.sel.keys[0].val&sel2.sel.keys[0].mask;
> - uname(&utsname);
> - if (strncmp(utsname.release, "2.4.", 4) == 0) {
> -         hash ^= hash>>16;
> -         hash ^= hash>>8;
> - }
> - else {
> -         __u32 mask = sel2.sel.keys[0].mask;
> -         while (mask && !(mask & 1)) {
> -                 mask >>= 1;
> -                 hash >>= 1;
> -         }
> -         hash &= 0xFF;
> - }
> + hash ^= hash>>16;
> + hash ^= hash>>8;
>    htid = ((hash%divisor)<<12)|(htid&0xFFF00000);
> 
> The old code would work if key and mask weren't in network byteorder. I
> guess that also changed since then.
> 
> I would simply send a patch to fix iproute2, but I don't like the
> kernel's hash "folding" as it ignores any bits beyond the first eight.
> So I would prefer to "fix" the kernel instead but would like to hear
> your opinions as that change has a much larger scope than just
> iproute2's 'sample' option.
> 
> Thanks, Phil
>