[Olsr-dev] OLSRD RT refactoring

[Sven-Ola Tuecke]

Hannes,

great work - thanks a lot:) I've done a little patching on top of your
stuff - you may see them as a kind of comment from my side:

100-olsrd-cvs.patch
  olsrd-0.5.3.tar.gz up to CVS

101-olsrd-rt-refactoring.patch
  Your patch (applyable with -p1)

102-olsrd-rt-refactoring-fixes.patch
  Because you changed a lot of basics: It's time to handle a general
  flaw in the routing system. Plase take a look at chk_if_changed(). This
  will free() any "struct interface" pointer without warning at any time.
  This is why it's possile to SEGV olsrd with a simple "ifdown xxx". 
  The patch replaces the (maybe) invalid pointer with an index reference
  "iif_index". You can always ask the OS for a name. Please note, that I do
  not have a working BSD toolchain, so I've placed an #error in the IPv6
  BSD-part where the author/porter has started to hack something funny.

103-olsrd-rt-exportroute-cleanup.patch
  This is the reworked hooking for quagga.

104-olsrd-policy-routing.patch
  This is policy routing with the changes necessary to work with
  your rt-refactoring.

I have at least one soft (olsr-viz) which depends on the metric value. 

Mentined patches are here as ususal:
http://download-master.berlin.freifunk.net/sven-ola/nylon/packages/olsrd/files/

P.S.: I'm not against vim/emacs control info in sources files. But because
diff and patch do not handle them well, it will be more convenient if all
source files have that comments at the end (just in case someone wants to
apply diffs at EOF)

Have a nice weekend,
// Sven-Ola

Hannes Gredler wrote:

> hi olsr developers,
> 
> attached a patch for refactoring the olsr routing table implementation.
> this is both a cleanup of duplicate routines, as well a clean
> reimplementation of the RIB.
> 
> change list:
> 
> - get rid of separate routing tables for HNA and per-node routes,
>    everything is now unified in an AVL routing tree (&routingtree)
> 
> - introduce walking macros (OLSR_FOR_ALL_RT_ENTRIES()) that hide
>    the internal structure of the RIB for making life of the plugin
>    authors easier.
> 
> - get rid of different SPF implementations for LQ and non-LQ code paths.
>    a non-LQ edge is simply substituted with a cost of 1.0
> 
> - get rid of host masks - a new data type olsr_prefix is
>    introduced which is basically an ip address plus a prefix length.
> 
> - do not install the metric in the kernel FIB - for the kernel its
>    pointless if the route gets installed with a metric of N or M.
> 
>    we do not need to update the kernel FIB if we have hop count only
>    changes (for example if there is a reroute action further downstream)
> 
>    the only things which triggers a kernel FIB route update is a next hop
>    change (a next hop is neighboring gateway router plus an interface).
> 
>    all OLSR routes are installed with a metric of 2
> 
> - separate between rt_entry and rt_path - the former is a route
>    installed in the kernel with an next hop. the latter is
>    a candidate for best path selection after SPF calculation has
>    been done. in the rt_entry we keep a pointer to the best_path and
>    also to the next hop that was installed in the kernel FIB.
>    we always keep all originator of a route, if a route originator
>    goes away we can easy recompute the best path for the route.
> 
>    the next hop in the rt_entry gets only updated upon a successful
>    route_add call - that way we always remember what next hop to delete.
> 
>    stray routes should be history now.
> 
> - tweak the linked list toolkit to operate on circular lists.
> 
> - get rid of malloc calls for building the kernel update list.
>    the list node is now embedded in the rt_entry.
> 
> - introduce three queues (add/chg/del) for kernel updates.
>    for neighbor route dependency tracking the neighbor routes
>    are queued first or last (depending on which queue you work on)
> 
> - rework all the plugins which directly manipulate rt entries.
> 
> - rework the plugins that read from the routing table (most notably
>    nameserver, httpinfo and quagga plugin)
> 
> - lots of comments that explains the intentions and purpose of this
>    code-piece.
> 
> non RT related stuff:
> 
> - use a list rather than a tree for storing the post-SPF results,
>    which further improves the raw-SPF runtime.
> 
> - add display of SPF runtime (masked behind #ifdef SPF_PROFILING)
> 
> the overall CPU savings of this change are not dramatic (app. 10-15%
> for the entire route-calculation path) - however it provides the necessary
> infrastructure (particularly the separation between rt_entry and rt_path)
> for doing in place SPF calculations further down the road
> 
> asking for feedback and inclusion into CVS head.
> 
> tx,
> 
> /hannes