[PATCH libnl v2 0/5] route cache: support for non-exclusive and append routes

[David Ahern]

From: Roopa Prabhu <roopa at cumulusnetworks.com>

[ sending for Roopa; her patches are still not showing on list ]

This series adds support for append and non-exclusive routes in the route cache

Problem with ipv4 route appends and non-exclusive routes today:
Todays libnl route cache looks at prefix + tos + priority to lookup a
route object. To support route append operation, where routes with same
prefix + tos + priority but different nexthop information can co-exist,
we need to also look at nexthop info. Else we will wrongly store only
one route for all appended routes. This happens Because the libnl cache
inclusion process looks up a route by prefix + tos + priority and replaces
it with the new object with the same prefix + tos + priority.

Only adding nexthop attribute during lookup does not solve the whole
problem. Because NLM_F_REPLACE of objects needs special handling.


example showing two interfaces on the same subnet

4: dummy0 at NONE: <BROADCAST,NOARP,UP,LOWER_UP> mtu 1500 qdisc noqueue state UNKNOWN group default
    link/ether ce:31:84:aa:d9:fa brd ff:ff:ff:ff:ff:ff
    inet 11.0.2.115/28 scope global dummy0
       valid_lft forever preferred_lft forever
5: dummy1 at NONE: <BROADCAST,NOARP,UP,LOWER_UP> mtu 1500 qdisc noqueue state UNKNOWN group default
    link/ether 12:5e:25:06:2a:25 brd ff:ff:ff:ff:ff:ff
    inet 11.0.2.115/28 scope global dummy1
       valid_lft forever preferred_lft forever

# ip route show
11.0.2.112/28 dev dummy0  proto kernel  scope link  src 11.0.2.115
11.0.2.112/28 dev dummy1  proto kernel  scope link  src 11.0.2.115

cache before patch:
 inet 11.0.2.112/28 table main type unicast via dev 4

cache after patch:
 inet 11.0.2.112/28 table main type unicast via dev 4
 inet 11.0.2.112/28 table main type unicast via dev 5


Append routes example:
ip route add 10.0.14.0/24 dev dummy0
ip route append 10.0.14.0/24 dev dummy1

# ip route show
10.0.14.0/24 dev dummy0  scope link
10.0.14.0/24 dev dummy1  scope link

cache before patch
inet 10.0.14.0/24 table main type unicast via dev 4

cache after patch
inet 10.0.14.0/24 table main type unicast via dev 4
inet 10.0.14.0/24 table main type unicast via dev 5

This series does the following:
1) Adds a cache specific operation to get search attributes specific to
a cache depending on the netlink flags during inclusion of an object to the
cache. This is used by the route cache which will need to use different
attributes for lookup depending on kernel route creation flags like
NLM_F_APPEND and NLM_F_REPLACE.

2) convert hashtable bucket list to a circular doubly linked list for
O(1) enqueue/dequeue. Because with append you do an enqueue tail and
With non-exclusive (ie create only flag) you do an enqueue head.

3) New object operation oo_hash_attrs_get to get the hash attributes of a
object

4) New object flag NL_OBJ_DUMP
This is needed because, During resync we don't have any
obj creation flags and we need to maintain the order the
kernel sent us

FWIW, This patch has been in production on our debian based distribution
(Cumulus Linux) for more than 2 years now.

v1/RFC - v2:
	- a few cleanups
	- fix route_update NLM_F_REPLACE handling
	to follow the new ipv6 replace kernel behaviour
	- fix route_id_attrs_get to include ROUTE_ATTR_MULTIPATH
	only if present.

Roopa Prabhu (5):
  hashtable: convert hashtable bucket list to a circular doubly linked
    list
  cache: modify nl_cache_search to look at cache provided attributes for
    search
  obj_ops: add new oo_hash_attrs_get to get hash key attributes of any
    object
  cache: add new NL_OBJ_DUMP cache flag (ce_flags)
  route: cache and object changes to support non-exclusive and append
    routes

 include/netlink-private/cache-api.h  |  15 ++++
 include/netlink-private/object-api.h |   5 ++
 include/netlink-private/types.h      |   1 +
 include/netlink/cache.h              |   3 +
 include/netlink/hashtable.h          |   4 +-
 include/netlink/object.h             |   3 +
 include/netlink/route/nexthop.h      |   1 +
 include/netlink/route/route.h        |   8 ++
 lib/cache.c                          |  74 +++++++++++++++++-
 lib/hashtable.c                      | 145 ++++++++++++++++++++++++-----------
 lib/object.c                         |  11 +++
 lib/route/nexthop.c                  |   5 ++
 lib/route/route.c                    |  21 +++++
 lib/route/route_obj.c                |  96 +++++++++++++++++++----
 14 files changed, 330 insertions(+), 62 deletions(-)

--