On Wed, 10 Dec 2025, Claudio Jeker wrote:

> To deduplicate the adj-rib-out in bgpd I want to use a bitmap per prefix
> to store all the peers that have that prefix in the adj-rib-out.
> The idea is that this uses 1 bit per peer instead of sizeof(struct
> adjout_prefix) per peer. Which is a massive win when you have many peers.
> 
> Here is the bitmap API that I bolted together. I had a look at the API we
> have in libc but decided against it since it is not dynamic enough for my
> needs.
> 
> The bitmap I want to use needs to scale dynamically up but should also be
> minimal for small sets (most bgpd users have less than 100 peers).
> Because of this I came up with a new API.
> 
> Functions include:
> - set, test, clear: set, test and clear a bit in the map
> - empty: check if a bitmap is empty (has no bit set).
> - id_get: return the lowest free id in map
> - id_put: return an id to the map, aka clear
> - init, reset: initialize and free a map
> 
> The first 127 elements are put directly into struct bitmap without further
> allocation. For maps with more than 127 elements external memory is allocated
> in the set function. This memory is only freed by reset which must be called
> before an object is removed containing a bitmap.
> It is not possible to set bit 0 of a bitmap since that bit is used to
> differentiate between access modes. In my use cases this is perfectly fine
> since most code already treats 0 in a special way.

fwiw there's also a bitmap.[ch] in openssh, which has a more simplistic
implementation but also a fair bit of fuzzing history.

-d