• Jason A. Donenfeld's avatar
    wireguard: allowedips: remove nodes in O(1) · f634f418
    Jason A. Donenfeld authored
    Previously, deleting peers would require traversing the entire trie in
    order to rebalance nodes and safely free them. This meant that removing
    1000 peers from a trie with a half million nodes would take an extremely
    long time, during which we're holding the rtnl lock. Large-scale users
    were reporting 200ms latencies added to the networking stack as a whole
    every time their userspace software would queue up significant removals.
    That's a serious situation.
    
    This commit fixes that by maintaining a double pointer to the parent's
    bit pointer for each node, and then using the already existing node list
    belonging to each peer to go directly to the node, fix up its pointers,
    and free it with RCU. This means removal is O(1) instead of O(n), and we
    don't use gobs of stack.
    
    The removal algorithm has the same downside as the code that it fixes:
    it won't collapse needlessly long runs of fillers.  We can enhance that
    in the future if it ever becomes a problem. This commit documents that
    limitation with a TODO comment in code, a small but meaningful
    improvement over the prior situation.
    
    Currently the biggest flaw, which the next commit addresses, is that
    because this increases the node size on 64-bit machines from 60 bytes to
    68 bytes. 60 rounds up to 64, but 68 rounds up to 128. So we wind up
    using twice as much memory per node, because of power-of-two
    allocations, which is a big bummer. We'll need to figure something out
    there.
    
    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>
    f634f418
allowedips.c 10.1 KB