]> git.proxmox.com Git - mirror_frr.git/commit - lib/id_alloc.h
lib: Implement an allocator for 32 bit ID numbers
authorMitch Skiba <mskiba@amazon.com>
Thu, 17 May 2018 19:06:08 +0000 (19:06 +0000)
committerMitch Skiba <mskiba@amazon.com>
Fri, 9 Nov 2018 21:50:34 +0000 (21:50 +0000)
commita94eca0968d914d58dff819c2411542377f56bae
tree602a730deb50b0dceffb5beae2e9aec5ad27f5de
parent4c056cfb30cb980dc9b9b2f65a7ec7def310a944
lib: Implement an allocator for 32 bit ID numbers

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>
lib/id_alloc.c [new file with mode: 0644]
lib/id_alloc.h [new file with mode: 0644]
lib/lib_errors.h
lib/subdir.am
tests/lib/test_idalloc.c [new file with mode: 0644]
tests/lib/test_idalloc.py [new file with mode: 0644]
tests/subdir.am