HomeFreeBSD

[fib_algo][dxr] Split unused range chunk list in multiple buckets

Description

[fib_algo][dxr] Split unused range chunk list in multiple buckets

Traversing a single list of unused range chunks in search for a block
of optimal size was suboptimal.

The experience with real-world BGP workloads has shown that on average
unused range chunks are tiny, mostly in length from 1 to 4 or 5, when
DXR is configured with K = 20 which is the current default (D16X4R).

Therefore, introduce a limited amount of buckets to accomodate descriptors
of empty blocks of fixed (small) size, so that those can be found in O(1)
time. If no empty chunks of the requested size can be found in fixed-size
buckets, the search continues in an unsorted list of empty chunks of
variable lengths, which should only happen infrequently.

This change should permit us to manage significantly more empty range
chunks without sacrifying the speed of incremental range table updating.

MFC after: 3 days

Details

Provenance
zecAuthored on Sep 25 2021, 4:29 AM
Parents
rGc5981a8130e2: [fib_algo][dxr] Merge adjacent empty range table chunks.
Branches
Unknown
Tags
Unknown