[From nobody Sun May 29 05:38:44 2016 Received: from zmta01.collab.prod.int.phx2.redhat.com (LHLO zmta01.collab.prod.int.phx2.redhat.com) (10.5.81.8) by zmail21.collab.prod.int.phx2.redhat.com with LMTP; Mon, 2 Nov 2015 17:12:20 -0500 (EST) Received: from int-mx14.intmail.prod.int.phx2.redhat.com (int-mx14.intmail.prod.int.phx2.redhat.com [10.5.11.27]) by zmta01.collab.prod.int.phx2.redhat.com (Postfix) with ESMTP id 6AF6F1854EF for <thaller@mail.corp.redhat.com>; Mon, 2 Nov 2015 17:12:20 -0500 (EST) Received: from mx1.redhat.com (ext-mx05.extmail.prod.ext.phx2.redhat.com [10.5.110.29]) by int-mx14.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id tA2MCK8N011533 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO) for <thaller@redhat.com>; Mon, 2 Nov 2015 17:12:20 -0500 Received: from mail-pa0-f46.google.com (mail-pa0-f46.google.com [209.85.220.46]) by mx1.redhat.com (Postfix) with ESMTPS id 6C3B642E5AB for <thaller@redhat.com>; Mon, 2 Nov 2015 22:12:17 +0000 (UTC) Received: by padec8 with SMTP id ec8so51416842pad.1 for <thaller@redhat.com>; Mon, 02 Nov 2015 14:12:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cumulusnetworks.com; s=google; h=from:to:cc:subject:date:message-id; bh=/17SnSrsJnpqBRDkou/pA6aqkYEqPP37AGTqiwwF7G8=; b=ZF0c4mzUKzFxnYHLEqZJ/DmFjiP54f056MnD1dey9A5/MQ7+sy76em0JUmiS2cqesg mbgsnI91H/HsKX4o/mBqLoW04P47t05ff+rX72R5wmZCDU2NWmapRp8UcvaBt4eo71+n U8yXSWNGd7lyteU1526jERf7yKFZ2qPZowB+E= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id; bh=/17SnSrsJnpqBRDkou/pA6aqkYEqPP37AGTqiwwF7G8=; b=Bcj8bDV8MfkSxWgDbuVMDqwpIHQDGIq4LZCI38UnOAP/Xzc8NEl5IMR33/YRotGYLd 39Ub0onwe7tqboUFHNNFIRivDiH9sFwBxsp/HSJhV056bv9pBVkTBQWsPc/+zxf4bMQb G/qMa1o0Q425o7jwONtSbAmpEk09BnhIJZU+eSFuPtCXVDult9RQWCFf+TLljLNqSYIQ DHQIZWM3IR1G0VzjpuuaNx4UBrUwxI1Xb7cPL20PobL3vBVUeHuJCUMxX7ac68lZpfJh Qt2fQSmyIsql4fx95s7y2nbj5pT/XAZX+Oi5Cz1L+v+j5utdprYjhigGe3mfxJiFVJhG KlrA== X-Gm-Message-State: ALoCoQnqGKZ90SeC9hor0HnutedJNga7LKthejm3ha8drSCwToDrM1he4qlNiH5FoDpA5bcfvnVU X-Received: by 10.68.189.69 with SMTP id gg5mr29882716pbc.55.1446501936120; Mon, 02 Nov 2015 14:05:36 -0800 (PST) Received: from hydra-01.cumulusnetworks.com ([216.129.126.126]) by smtp.googlemail.com with ESMTPSA id bz1sm25892966pab.20.2015.11.02.14.05.35 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 02 Nov 2015 14:05:35 -0800 (PST) From: Roopa Prabhu <roopa@cumulusnetworks.com> X-Google-Original-From: Roopa Prabhu To: libnl@lists.infradead.org Cc: thaller@redhat.com, roopa@cumulusnetworks.com Subject: [PATCH 0/6] route cache: support for non-exclusive and append routes Date: Mon, 2 Nov 2015 14:05:23 -0800 Message-Id: <1446501929-32003-1-git-send-email-roopa@cumulusnetworks.com> X-RedHat-Spam-Score: 2.08 ** (ANY_BOUNCE_MESSAGE, BAYES_50, BOUNCE_MESSAGE, DCC_REPUT_13_19, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DSN_NO_MIMEVERSION, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, URIBL_BLOCKED) 209.85.220.46 mail-pa0-f46.google.com 209.85.220.46 mail-pa0-f46.google.com <> X-Scanned-By: MIMEDefang 2.68 on 10.5.11.27 X-Scanned-By: MIMEDefang 2.78 on 10.5.110.29 Mime-Version: 1.0 Content-Transfer-Encoding: quoted-printable From: Roopa Prabhu <roopa@cumulusnetworks.com> This series adds support for append and non-exclusive routes in the route c= ache 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@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@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. Roopa Prabhu (6): nl_object: add new ce_msgflags field to nl_object 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 | 6 ++ include/netlink-private/types.h | 1 + include/netlink/cache.h | 3 + include/netlink/hashtable.h | 4 +- include/netlink/object.h | 2 + include/netlink/route/route.h | 8 ++ lib/cache.c | 74 ++++++++++++++++- lib/hashtable.c | 145 +++++++++++++++++++++++-------= ---- lib/object.c | 11 +++ lib/route/route.c | 21 +++++ lib/route/route_obj.c | 65 +++++++++++---- 12 files changed, 293 insertions(+), 62 deletions(-) --=20 1.7.10.4 ]