|
|
This commit introduces lib/id_alloc, which has facilities for both an ID number
allocator, and less efficient ID holding pools. The pools are meant to be a
temporary holding area for ID numbers meant to be re-used, and are implemented
as a linked-list stack.
The allocator itself is much more efficient with memory. Based on sizeof
values on my 64 bit desktop, the allocator requires around 155 KiB per
million IDs tracked.
IDs are ultimately tracked in a bit-map split into many "pages." The
allocator tracks a list of pages that have free bits, and which sections
of each page have free IDs, so there isn't any scanning required to find
a free ID. (The library utility ffs, or "Find First Set," is generally a
single CPU instruction.) At the moment, totally empty pages will not be
freed, so the memory utilization of this allocator will remain at the
high water mark.
The initial intended use case is for BGP's TX Addpath IDs to be pulled
from an allocator that tracks which IDs are in use, rather than a free
running counter. The allocator reserves ID #0 as a sentinel value for
an invalid ID numbers, and BGP will want ID #1 reserved as well. To
support this, the allocator allows for IDs to be explicitly reserved,
though be aware this is only practical to use with low numbered IDs
because the allocator must allocate pages in order.
Signed-off-by Mitchell Skiba <mskiba@amazon.com>
|
