netdev - [FIB]: full_children & empty_children should be uint, not ushort

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <478A58BD.8010304@cosmosbay.com>
Date:	Sun, 13 Jan 2008 19:30:21 +0100
From:	Eric Dumazet <dada1@...mosbay.com>
To:	David Miller <davem@...emloft.net>
CC:	Stephen Hemminger <stephen.hemminger@...tta.com>,
	Robert Olsson <robert.olsson@....uu.se>, netdev@...r.kernel.org
Subject: [FIB]: full_children & empty_children should be uint, not ushort

Eric Dumazet a écrit :
> 4) full_children & empty_children being 'unsigned short',
>    we probably are limited to 2^15 elements, but I could not
>    find this limit enforced somewhere.

Hi David

In my testings, I found that once a tnode is built with 2^16 slots (or more), 
it cannot be freed.

Extract of /proc/net/fib_triestat

Main:
  Aver depth:     1.50
  Max depth:      2
  Leaves:         2
  Internal nodes: 3
    1: 1  2: 1  17: 1
  Pointers: 131078
Null ptrs: 131074
Total size: 513  kB
# ip route
192.168.11.0/24 dev eth0  proto kernel  scope link  src 192.168.11.129
default via 192.168.11.2 dev eth0

Two fixes are possible : Enlarge full_children & empty_children to 32bits, or 
force a limit in code to never exceed 2^15 children in a tnode. I chose the 
first solution since it can be done with 0 memory cost on 64bit arches.

Thank you

[FIB]: full_children & empty_children should be uint, not ushort

If declared as unsigned short, these fields can overflow, and whole trie logic
is broken. I could not make the machine crash, but some tnode can never
be freed.

Note for 64 bit arches : By reordering t_key and parent in [node, leaf, tnode] 
structures, we can use 32 bits hole after t_key so that sizeof(struct tnode) 
doesnt change after this patch.

Signed-off-by: Eric Dumazet <dada1@...mosbay.com>

View attachment "fib_trie.patch" of type "text/plain" (2516 bytes)