https://github.com/torvalds/linux
Revision f634f418c227c912e7ea95a3299efdc9b10e4022 authored by Jason A. Donenfeld on 04 June 2021, 15:17:36 UTC, committed by David S. Miller on 04 June 2021, 21:25:14 UTC
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: e7096c131e51 ("net: WireGuard secure network tunnel") Cc: stable@vger.kernel.org Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> Signed-off-by: David S. Miller <davem@davemloft.net>
1 parent 46cfe8e
Tip revision: f634f418c227c912e7ea95a3299efdc9b10e4022 authored by Jason A. Donenfeld on 04 June 2021, 15:17:36 UTC
wireguard: allowedips: remove nodes in O(1)
wireguard: allowedips: remove nodes in O(1)
Tip revision: f634f41
initramfs_data.S
/* SPDX-License-Identifier: GPL-2.0 */
/*
initramfs_data includes the compressed binary that is the
filesystem used for early user space.
Note: Older versions of "as" (prior to binutils 2.11.90.0.23
released on 2001-07-14) dit not support .incbin.
If you are forced to use older binutils than that then the
following trick can be applied to create the resulting binary:
ld -m elf_i386 --format binary --oformat elf32-i386 -r \
-T initramfs_data.scr initramfs_data.cpio.gz -o initramfs_data.o
ld -m elf_i386 -r -o built-in.a initramfs_data.o
For including the .init.ramfs sections, see include/asm-generic/vmlinux.lds.
The above example is for i386 - the parameters vary from architectures.
Eventually look up LDFLAGS_BLOB in an older version of the
arch/$(ARCH)/Makefile to see the flags used before .incbin was introduced.
Using .incbin has the advantage over ld that the correct flags are set
in the ELF header, as required by certain architectures.
*/
.section .init.ramfs,"a"
__irf_start:
.incbin "usr/initramfs_inc_data"
__irf_end:
.section .init.ramfs.info,"a"
.globl __initramfs_size
__initramfs_size:
#ifdef CONFIG_64BIT
.quad __irf_end - __irf_start
#else
.long __irf_end - __irf_start
#endif
Computing file changes ...