• Jason A. Donenfeld's avatar
    wireguard: allowedips: free empty intermediate nodes when removing single node · bf7b042d
    Jason A. Donenfeld authored
    When removing single nodes, it's possible that that node's parent is an
    empty intermediate node, in which case, it too should be removed.
    Otherwise the trie fills up and never is fully emptied, leading to
    gradual memory leaks over time for tries that are modified often. There
    was originally code to do this, but was removed during refactoring in
    2016 and never reworked. Now that we have proper parent pointers from
    the previous commits, we can implement this properly.
    
    In order to reduce branching and expensive comparisons, we want to keep
    the double pointer for parent assignment (which lets us easily chain up
    to the root), but we still need to actually get the parent's base
    address. So encode the bit number into the last two bits of the pointer,
    and pack and unpack it as needed. This is a little bit clumsy but is the
    fastest and less memory wasteful of the compromises. Note that we align
    the root struct here to a minimum of 4, because it's embedded into a
    larger struct, and we're relying on having the bottom two bits for our
    flag, which would only be 16-bit aligned on m68k.
    
    The existing macro-based helpers were a bit unwieldy for adding the bit
    packing to, so this commit replaces them with safer and clearer ordinary
    functions.
    
    We add a test to the randomized/fuzzer part of the selftests, to free
    the randomized tries by-peer, refuzz it, and repeat, until it's supposed
    to be empty, and then then see if that actually resulted in the whole
    thing being emptied. That combined with kmemcheck should hopefully make
    sure this commit is doing what it should. Along the way this resulted in
    various other cleanups of the tests and fixes for recent graphviz.
    
    Fixes: e7096c13 ("net: WireGuard secure network tunnel")
    Cc: stable@vger.kernel.org
    Signed-off-by: default avatarJason A. Donenfeld <Jason@zx2c4.com>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    bf7b042d
allowedips.h 1.83 KB