[Olsr-dev] OLSRD RT refactoring

[Hannes Gredler]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: rt-refactoring-4.diff.gz
Type: application/gzip
Size: 32983 bytes
Desc: not available
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20070823/af04902d/attachment.gz>