[Olsr-dev] OLSRD RT refactoring

[Hannes Gredler]

hi,

since the mailing-list seems do dislike attachments the patch is at

http://gredler.at/download/olsrd/rt-refactoring-4.diff.gz

/hannes

--

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