Skip to content
  • Marko Zec's avatar
    [fib_algo][dxr] Split unused range chunk list in multiple buckets · 43880c51
    Marko Zec authored
    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
    43880c51