Skip to content
  • Thomas Haller's avatar
    platform: use NMDedupMultiIndex for routes in NMPCache · 9440eefb
    Thomas Haller authored
    Rework platform object cache to use NMDedupMultiIndex.
    
    Already previously, NMPCache used NMMultiIndex and had thus
    O(1) for most operations. What is new is:
    
    - Contrary to NMMultiIndex, NMDedupMultiIndex preserves the order of
      the cached items. That is crucial to handle routes properly as kernel
      will replace the first matching route based on network/plen/metric
      properties. See related bug rh#1337855.
      Without tracking the order of routes as they are exposed
      by kernel, we cannot properly maintain the route cache.
    
    - All NMPObject instances are now treated immutable, refcounted
      and get de-duplicated via NMDedupMultiIndex. This allows
      to have a global NMDedupMultiIndex that can be shared with
      NMIP4Config and NMRouteManager. It also allows to share the
      objects themselves.
      Immutable objects are so much nicer. We can get rid of the
      update pre-hook callback, which was required previously because
      we would mutate the object inplace. Now, we can just update
      the cache, and compare obj_old and obj_new after the fact.
    
    - NMMultiIndex was treated as an internal of NMPCache. On the other
      hand, NMDedupMultiIndex exposes NMDedupMultiHeadEntry, which is
      basically an object that allows to iterate over all related
      objects. That means, we can now lookup objects in the cache
      and give the NMDedupMultiHeadEntry instance to the caller,
      which then can iterate the list on it's own -- without need
      for copying anything.
      Currently, at various places we still create copies of lookup
      results. That can be improved later.
    
    The ability to share NMPObject instances should enable us to
    significantly improve performance and scale with large number
    of routes.
    
    Of course there is a memory overhead of having an index for each list
    entry. Each NMPObject may also require an NMDedupMultiEntry,
    NMDedupMultiHeadEntry, and NMDedupMultiBox item, which are tracked
    in a GHashTable. Optimally, one NMDedupMultiHeadEntry is the head
    for multiple objects, and NMDedupMultiBox is able to deduplicate several
    NMPObjects, so that there is a net saving.
    Also, each object type has several indexes of type NMPCacheIdType.
    So, worst case an NMPlatformIP4Route in the platform cache is tracked
    by 8 NMPCacheIdType indexes, for each we require a NMDedupMultiEntry,
    plus the shared NMDedupMultiHeadEntry. The NMDedupMultiBox instance
    is shared between the 8 indexes (and possibly other).
    9440eefb