diff options
57 files changed, 1258 insertions, 376 deletions
diff --git a/.clang-format b/.clang-format index a65a29f8c9..4bd962747f 100644 --- a/.clang-format +++ b/.clang-format @@ -25,6 +25,9 @@ CommentPragmas: '\$(FRR|clippy)' ContinuationIndentWidth: 8 ForEachMacros: # lib + - frr_each + - frr_each_safe + - frr_each_from - LIST_FOREACH - LIST_FOREACH_SAFE - SLIST_FOREACH diff --git a/bgpd/bgp_advertise.h b/bgpd/bgp_advertise.h index 7d2fdf1f0b..1b55b6e64b 100644 --- a/bgpd/bgp_advertise.h +++ b/bgpd/bgp_advertise.h @@ -23,7 +23,7 @@ #include "lib/typesafe.h" -PREDECL_LIST(bgp_adv_fifo) +PREDECL_DLIST(bgp_adv_fifo) struct update_subgroup; @@ -60,7 +60,7 @@ struct bgp_advertise { struct bgp_path_info *pathi; }; -DECLARE_LIST(bgp_adv_fifo, struct bgp_advertise, fifo) +DECLARE_DLIST(bgp_adv_fifo, struct bgp_advertise, fifo) /* BGP adjacency out. */ struct bgp_adj_out { diff --git a/bgpd/bgp_errors.c b/bgpd/bgp_errors.c index 753ee6baf1..6e181697d6 100644 --- a/bgpd/bgp_errors.c +++ b/bgpd/bgp_errors.c @@ -122,12 +122,6 @@ static struct log_ref ferr_bgp_warn[] = { .suggestion = "Please collect log files and open Issue", }, { - .code = EC_BGP_NO_SOCKOPT_MARK, - .title = "Unable to set socket MARK option", - .description = "BGP attempted to set the SO_MARK option for a socket and was unable to do so", - .suggestion = "Please collect log files and open Issue", - }, - { .code = EC_BGP_EVPN_PMSI_PRESENT, .title = "BGP Received a EVPN NLRI with PMSI included", .description = "BGP has received a type-3 NLRI with PMSI information. At this time FRR is not capable of properly handling this NLRI type", diff --git a/bgpd/bgp_errors.h b/bgpd/bgp_errors.h index 13bd318e27..39d043ff13 100644 --- a/bgpd/bgp_errors.h +++ b/bgpd/bgp_errors.h @@ -88,7 +88,6 @@ enum bgp_log_refs { EC_BGP_UPDATE_PACKET_LONG, EC_BGP_UNRECOGNIZED_CAPABILITY, EC_BGP_NO_TCP_MD5, - EC_BGP_NO_SOCKOPT_MARK, EC_BGP_EVPN_PMSI_PRESENT, EC_BGP_EVPN_VPN_VNI, EC_BGP_EVPN_ESI, diff --git a/bgpd/bgp_main.c b/bgpd/bgp_main.c index adba73e404..abd8586f4c 100644 --- a/bgpd/bgp_main.c +++ b/bgpd/bgp_main.c @@ -70,10 +70,6 @@ static const struct option longopts[] = { {"bgp_port", required_argument, NULL, 'p'}, {"listenon", required_argument, NULL, 'l'}, -#if CONFDATE > 20190521 - CPP_NOTICE("-r / --retain has reached deprecation EOL, remove") -#endif - {"retain", no_argument, NULL, 'r'}, {"no_kernel", no_argument, NULL, 'n'}, {"skip_runas", no_argument, NULL, 'S'}, {"ecmp", required_argument, NULL, 'e'}, @@ -367,10 +363,7 @@ FRR_DAEMON_INFO(bgpd, BGP, .vty_port = BGP_VTY_PORT, .privs = &bgpd_privs, .yang_modules = bgpd_yang_modules, .n_yang_modules = array_size(bgpd_yang_modules), ) -#if CONFDATE > 20190521 -CPP_NOTICE("-r / --retain has reached deprecation EOL, remove") -#endif -#define DEPRECATED_OPTIONS "r" +#define DEPRECATED_OPTIONS "" /* Main routine of bgpd. Treatment of argument and start bgp finite state machine is handled at here. */ diff --git a/bgpd/bgp_network.c b/bgpd/bgp_network.c index 6a5c2c4b38..8e18ed7529 100644 --- a/bgpd/bgp_network.c +++ b/bgpd/bgp_network.c @@ -588,8 +588,6 @@ static int bgp_update_source(struct peer *peer) return ret; } -#define DATAPLANE_MARK 254 /* main table ID */ - /* BGP try to connect to the peer. */ int bgp_connect(struct peer *peer) { @@ -619,10 +617,6 @@ int bgp_connect(struct peer *peer) sockopt_reuseaddr(peer->fd); sockopt_reuseport(peer->fd); - if (sockopt_mark_default(peer->fd, DATAPLANE_MARK, &bgpd_privs) < 0) - flog_warn(EC_BGP_NO_SOCKOPT_MARK, - "Unable to set mark on FD for peer %s, err=%s", - peer->host, safe_strerror(errno)); #ifdef IPTOS_PREC_INTERNETCONTROL frr_elevate_privs(&bgpd_privs) { diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c index e554b905f3..31243c899d 100644 --- a/bgpd/bgp_route.c +++ b/bgpd/bgp_route.c @@ -8051,6 +8051,7 @@ static const char *bgp_path_selection_reason2str( return "Nothing left to compare"; break; } + return "Invalid (internal error)"; } void route_vty_out_detail(struct vty *vty, struct bgp *bgp, diff --git a/bgpd/bgp_routemap.c b/bgpd/bgp_routemap.c index 9ff4196dae..b0ae9d78d1 100644 --- a/bgpd/bgp_routemap.c +++ b/bgpd/bgp_routemap.c @@ -3090,8 +3090,6 @@ static void bgp_route_map_process_peer(const char *rmap_name, struct route_map *map, struct peer *peer, int afi, int safi, int route_update) { - - int update; struct bgp_filter *filter; if (!peer || !rmap_name) @@ -3102,52 +3100,16 @@ static void bgp_route_map_process_peer(const char *rmap_name, * in is for non-route-server clients, * out is for all peers */ - if (!CHECK_FLAG(peer->flags, PEER_FLAG_RSERVER_CLIENT)) { - if (filter->map[RMAP_IN].name - && (strcmp(rmap_name, filter->map[RMAP_IN].name) == 0)) { - filter->map[RMAP_IN].map = map; - - if (route_update && peer->status == Established) { - if (CHECK_FLAG(peer->af_flags[afi][safi], - PEER_FLAG_SOFT_RECONFIG)) { - if (bgp_debug_update(peer, NULL, NULL, - 1)) - zlog_debug( - "Processing route_map %s update on " - "peer %s (inbound, soft-reconfig)", - rmap_name, peer->host); - - bgp_soft_reconfig_in(peer, afi, safi); - } else if ( - CHECK_FLAG(peer->cap, - PEER_CAP_REFRESH_OLD_RCV) - || CHECK_FLAG( - peer->cap, - PEER_CAP_REFRESH_NEW_RCV)) { - - if (bgp_debug_update(peer, NULL, NULL, - 1)) - zlog_debug( - "Processing route_map %s update on " - "peer %s (inbound, route-refresh)", - rmap_name, peer->host); - bgp_route_refresh_send(peer, afi, safi, - 0, 0, 0); - } - } - } - } - - if (CHECK_FLAG(peer->flags, PEER_FLAG_RSERVER_CLIENT)) { - update = 0; + if (filter->map[RMAP_IN].name + && (strcmp(rmap_name, filter->map[RMAP_IN].name) == 0)) { + filter->map[RMAP_IN].map = map; - if (update && route_update && peer->status == Established) { + if (route_update && peer->status == Established) { if (CHECK_FLAG(peer->af_flags[afi][safi], PEER_FLAG_SOFT_RECONFIG)) { if (bgp_debug_update(peer, NULL, NULL, 1)) zlog_debug( - "Processing route_map %s update on " - "peer %s (import, soft-reconfig)", + "Processing route_map %s update on peer %s (inbound, soft-reconfig)", rmap_name, peer->host); bgp_soft_reconfig_in(peer, afi, safi); @@ -3157,13 +3119,11 @@ static void bgp_route_map_process_peer(const char *rmap_name, PEER_CAP_REFRESH_NEW_RCV)) { if (bgp_debug_update(peer, NULL, NULL, 1)) zlog_debug( - "Processing route_map %s update on " - "peer %s (import, route-refresh)", + "Processing route_map %s update on peer %s (inbound, route-refresh)", rmap_name, peer->host); bgp_route_refresh_send(peer, afi, safi, 0, 0, 0); } - /* DD: Else, what else do we do ? Reset peer ? */ } } diff --git a/bgpd/bgp_rpki.c b/bgpd/bgp_rpki.c index 010322233d..aa09026b78 100644 --- a/bgpd/bgp_rpki.c +++ b/bgpd/bgp_rpki.c @@ -737,28 +737,27 @@ static int rpki_validate_prefix(struct peer *peer, struct attr *attr, prefix->prefixlen, &result); // Print Debug output - prefix_string = - inet_ntop(prefix->family, &prefix->u.prefix, buf, BUFSIZ); + prefix_string = prefix2str(prefix, buf, sizeof(buf)); switch (result) { case BGP_PFXV_STATE_VALID: RPKI_DEBUG( - "Validating Prefix %s/%hhu from asn %u Result: VALID", - prefix_string, prefix->prefixlen, as_number); + "Validating Prefix %s from asn %u Result: VALID", + prefix_string, as_number); return RPKI_VALID; case BGP_PFXV_STATE_NOT_FOUND: RPKI_DEBUG( - "Validating Prefix %s/%hhu from asn %u Result: NOT FOUND", - prefix_string, prefix->prefixlen, as_number); + "Validating Prefix %s from asn %u Result: NOT FOUND", + prefix_string, as_number); return RPKI_NOTFOUND; case BGP_PFXV_STATE_INVALID: RPKI_DEBUG( - "Validating Prefix %s/%hhu from asn %u Result: INVALID", - prefix_string, prefix->prefixlen, as_number); + "Validating Prefix %s from asn %u Result: INVALID", + prefix_string, as_number); return RPKI_INVALID; default: RPKI_DEBUG( - "Validating Prefix %s/%hhu from asn %u Result: CANNOT VALIDATE", - prefix_string, prefix->prefixlen, as_number); + "Validating Prefix %s from asn %u Result: CANNOT VALIDATE", + prefix_string, as_number); break; } return 0; diff --git a/bgpd/bgp_updgrp.h b/bgpd/bgp_updgrp.h index 39e67bf608..bb547454f2 100644 --- a/bgpd/bgp_updgrp.h +++ b/bgpd/bgp_updgrp.h @@ -56,6 +56,7 @@ #define PEER_UPDGRP_AF_FLAGS \ (PEER_FLAG_SEND_COMMUNITY | PEER_FLAG_SEND_EXT_COMMUNITY \ + | PEER_FLAG_SEND_LARGE_COMMUNITY \ | PEER_FLAG_DEFAULT_ORIGINATE | PEER_FLAG_REFLECTOR_CLIENT \ | PEER_FLAG_RSERVER_CLIENT | PEER_FLAG_NEXTHOP_SELF \ | PEER_FLAG_NEXTHOP_UNCHANGED | PEER_FLAG_FORCE_NEXTHOP_SELF \ diff --git a/bgpd/bgp_vty.c b/bgpd/bgp_vty.c index 880b877806..ae51f1d780 100644 --- a/bgpd/bgp_vty.c +++ b/bgpd/bgp_vty.c @@ -2143,28 +2143,6 @@ DEFUN (no_bgp_fast_external_failover, return CMD_SUCCESS; } -/* "bgp enforce-first-as" configuration. */ -#if CONFDATE > 20190517 -CPP_NOTICE("bgpd: remove deprecated '[no] bgp enforce-first-as' commands") -#endif - -DEFUN_HIDDEN (bgp_enforce_first_as, - bgp_enforce_first_as_cmd, - "[no] bgp enforce-first-as", - NO_STR - BGP_STR - "Enforce the first AS for EBGP routes\n") -{ - VTY_DECLVAR_CONTEXT(bgp, bgp); - - if (strmatch(argv[0]->text, "no")) - bgp_flag_unset(bgp, BGP_FLAG_ENFORCE_FIRST_AS); - else - bgp_flag_set(bgp, BGP_FLAG_ENFORCE_FIRST_AS); - - return CMD_SUCCESS; -} - /* "bgp bestpath compare-routerid" configuration. */ DEFUN (bgp_bestpath_compare_router_id, bgp_bestpath_compare_router_id_cmd, @@ -10931,11 +10909,11 @@ static void bgp_show_peer(struct vty *vty, struct peer *p, bool use_json, if (p->password) vty_out(vty, "Peer Authentication Enabled\n"); - vty_out(vty, "Read thread: %s Write thread: %s\n", + vty_out(vty, "Read thread: %s Write thread: %s FD used: %d\n", p->t_read ? "on" : "off", CHECK_FLAG(p->thread_flags, PEER_THREAD_WRITES_ON) ? "on" - : "off"); + : "off", p->fd); } if (p->notify.code == BGP_NOTIFY_OPEN_ERR @@ -13036,9 +13014,6 @@ void bgp_vty_init(void) install_element(BGP_NODE, &bgp_fast_external_failover_cmd); install_element(BGP_NODE, &no_bgp_fast_external_failover_cmd); - /* "bgp enforce-first-as" commands */ - install_element(BGP_NODE, &bgp_enforce_first_as_cmd); - /* "bgp bestpath compare-routerid" commands */ install_element(BGP_NODE, &bgp_bestpath_compare_router_id_cmd); install_element(BGP_NODE, &no_bgp_bestpath_compare_router_id_cmd); diff --git a/bgpd/bgpd.c b/bgpd/bgpd.c index c0f1f3184a..2e648af1bb 100644 --- a/bgpd/bgpd.c +++ b/bgpd/bgpd.c @@ -2232,6 +2232,8 @@ int peer_delete(struct peer *peer) SET_FLAG(peer->flags, PEER_FLAG_DELETE); + bgp_bfd_deregister_peer(peer); + /* If this peer belongs to peer group, clear up the relationship. */ if (peer->group) { @@ -7557,12 +7559,6 @@ static void bgp_config_write_family(struct vty *vty, struct bgp *bgp, afi_t afi, vty_endframe(vty, " exit-address-family\n"); } -/* clang-format off */ -#if CONFDATE > 20190517 -CPP_NOTICE("bgpd: remove 'bgp enforce-first-as' config migration from bgp_config_write") -#endif -/* clang-format on */ - int bgp_config_write(struct vty *vty) { int write = 0; @@ -7598,15 +7594,6 @@ int bgp_config_write(struct vty *vty) if (CHECK_FLAG(bgp->vrf_flags, BGP_VRF_AUTO)) continue; - /* Migrate deprecated 'bgp enforce-first-as' - * config to 'neighbor * enforce-first-as' configs - */ - if (bgp_flag_check(bgp, BGP_FLAG_ENFORCE_FIRST_AS)) { - for (ALL_LIST_ELEMENTS(bgp->peer, node, nnode, peer)) - peer_flag_set(peer, PEER_FLAG_ENFORCE_FIRST_AS); - bgp_flag_unset(bgp, BGP_FLAG_ENFORCE_FIRST_AS); - } - /* Router bgp ASN */ vty_out(vty, "router bgp %u", bgp->as); diff --git a/bgpd/bgpd.h b/bgpd/bgpd.h index b0f6567534..c600d9f3f3 100644 --- a/bgpd/bgpd.h +++ b/bgpd/bgpd.h @@ -348,7 +348,6 @@ struct bgp { #define BGP_FLAG_MED_CONFED (1 << 3) #define BGP_FLAG_NO_DEFAULT_IPV4 (1 << 4) #define BGP_FLAG_NO_CLIENT_TO_CLIENT (1 << 5) -#define BGP_FLAG_ENFORCE_FIRST_AS (1 << 6) #define BGP_FLAG_COMPARE_ROUTER_ID (1 << 7) #define BGP_FLAG_ASPATH_IGNORE (1 << 8) #define BGP_FLAG_IMPORT_CHECK (1 << 9) diff --git a/doc/developer/building-frr-for-debian8.rst b/doc/developer/building-frr-for-debian8.rst index 9c6e48a6f8..a26d055bc2 100644 --- a/doc/developer/building-frr-for-debian8.rst +++ b/doc/developer/building-frr-for-debian8.rst @@ -17,7 +17,8 @@ Add packages: sudo apt-get install git autoconf automake libtool make \ libreadline-dev texinfo libjson-c-dev pkg-config bison flex python-pip \ - libc-ares-dev python3-dev python3-sphinx build-essential libsystemd-dev + libc-ares-dev python3-dev python3-sphinx build-essential libsystemd-dev \ + libsnmp-dev Install newer pytest (>3.0) from pip diff --git a/doc/developer/building-frr-for-debian9.rst b/doc/developer/building-frr-for-debian9.rst index 39e7488cd7..2c5a9681af 100644 --- a/doc/developer/building-frr-for-debian9.rst +++ b/doc/developer/building-frr-for-debian9.rst @@ -11,7 +11,7 @@ Add packages: sudo apt-get install git autoconf automake libtool make \ libreadline-dev texinfo libjson-c-dev pkg-config bison flex python-pip \ libc-ares-dev python3-dev python-pytest python3-sphinx build-essential \ - libsystemd-dev + libsnmp-dev libsystemd-dev .. include:: building-libyang.rst diff --git a/doc/developer/lists.rst b/doc/developer/lists.rst index 987b3b7f4f..fc47a67e42 100644 --- a/doc/developer/lists.rst +++ b/doc/developer/lists.rst @@ -13,15 +13,22 @@ FRR includes a set of list-like data structure implementations with abstracted common APIs. The purpose of this is easily allow swapping out one data structure for another while also making the code easier to read and write. There is one API for unsorted lists and a similar but not identical API for -sorted lists. +sorted lists - and heaps use a middle ground of both. For unsorted lists, the following implementations exist: - single-linked list with tail pointer (e.g. STAILQ in BSD) +- double-linked list + - atomic single-linked list with tail pointer +Being partially sorted, the oddball structure: + +- an 8-ary heap + + For sorted lists, these data structures are implemented: - single-linked list @@ -38,6 +45,8 @@ Except for hash tables, each of the sorted data structures has a variant with unique and non-unique list items. Hash tables always require unique items and mostly follow the "sorted" API but use the hash value as sorting key. Also, iterating while modifying does not work with hash tables. +Conversely, the heap always has non-unique items, but iterating while modifying +doesn't work either. The following sorted structures are likely to be implemented at some point @@ -61,6 +70,8 @@ Only the following pieces use dynamically allocated memory: - skiplists store up to 4 next pointers inline but will dynamically allocate memory to hold an item's 5th up to 16th next pointer (if they exist) +- the heap uses a dynamically grown and shrunk array of items + Cheat sheet ----------- @@ -70,6 +81,9 @@ Available types: DECLARE_LIST DECLARE_ATOMLIST + DECLARE_DLIST + + DECLARE_HEAP DECLARE_SORTLIST_UNIQ DECLARE_SORTLIST_NONUNIQ @@ -84,25 +98,26 @@ Available types: Functions provided: -+------------------------------------+------+------+---------+------------+ -| Function | LIST | HASH | \*_UNIQ | \*_NONUNIQ | -+====================================+======+======+=========+============+ -| _init, _fini | yes | yes | yes | yes | -+------------------------------------+------+------+---------+------------+ -| _first, _next, _next_safe | yes | yes | yes | yes | -+------------------------------------+------+------+---------+------------+ -| _add_head, _add_tail, _add_after | yes | -- | -- | -- | -+------------------------------------+------+------+---------+------------+ -| _add | -- | yes | yes | yes | -+------------------------------------+------+------+---------+------------+ -| _del, _pop | yes | yes | yes | yes | -+------------------------------------+------+------+---------+------------+ -| _find | -- | yes | yes | -- | -+------------------------------------+------+------+---------+------------+ -| _find_lt, _find_gteq | -- | -- | yes | yes | -+------------------------------------+------+------+---------+------------+ -| use with for_each() macros | yes | yes | yes | yes | -+------------------------------------+------+------+---------+------------+ ++------------------------------------+------+------+------+---------+------------+ +| Function | LIST | HEAP | HASH | \*_UNIQ | \*_NONUNIQ | ++====================================+======+======+======+=========+============+ +| _init, _fini | yes | yes | yes | yes | yes | ++------------------------------------+------+------+------+---------+------------+ +| _first, _next, _next_safe | yes | yes | yes | yes | yes | ++------------------------------------+------+------+------+---------+------------+ +| _add_head, _add_tail, _add_after | yes | -- | -- | -- | -- | ++------------------------------------+------+------+------+---------+------------+ +| _add | -- | yes | yes | yes | yes | ++------------------------------------+------+------+------+---------+------------+ +| _del, _pop | yes | yes | yes | yes | yes | ++------------------------------------+------+------+------+---------+------------+ +| _find | -- | -- | yes | yes | -- | ++------------------------------------+------+------+------+---------+------------+ +| _find_lt, _find_gteq | -- | -- | -- | yes | yes | ++------------------------------------+------+------+------+---------+------------+ +| use with frr_each() macros | yes | yes | yes | yes | yes | ++------------------------------------+------+------+------+---------+------------+ + Datastructure type setup @@ -161,7 +176,7 @@ Common iteration macros The following iteration macros work across all data structures: -.. c:function:: for_each(Z, &head, item) +.. c:function:: frr_each(Z, &head, item) Equivalent to: @@ -172,7 +187,7 @@ The following iteration macros work across all data structures: Note that this will fail if the list is modified while being iterated over. -.. c:function:: for_each_safe(Z, &head, item) +.. c:function:: frr_each_safe(Z, &head, item) Same as the previous, but the next element is pre-loaded into a "hidden" variable (named ``Z_safe``.) Equivalent to: @@ -191,7 +206,7 @@ The following iteration macros work across all data structures: tables is resized while iterating. This will cause items to be skipped or iterated over twice. -.. c:function:: for_each_from(Z, &head, item, from) +.. c:function:: frr_each_from(Z, &head, item, from) Iterates over the list, starting at item ``from``. This variant is "safe" as in the previous macro. Equivalent to: @@ -313,8 +328,8 @@ are several functions exposed to insert data: .. c:function:: DECLARE_XXX(Z, type, field) - :param listtype XXX: ``LIST`` or ``ATOMLIST`` to select a data structure - implementation. + :param listtype XXX: ``LIST``, ``DLIST`` or ``ATOMLIST`` to select a data + structure implementation. :param token Z: Gives the name prefix that is used for the functions created for this instantiation. ``DECLARE_XXX(foo, ...)`` gives ``struct foo_item``, ``foo_add_head()``, ``foo_count()``, etc. Note @@ -348,7 +363,7 @@ are several functions exposed to insert data: itemtype *prev = NULL, *item; - for_each_safe(Z, head, item) { + frr_each_safe(Z, head, item) { if (something) { Z_add_after(head, prev, item); break; @@ -479,6 +494,21 @@ the same semantics as noted above. :c:func:`Z_find_gteq()` and :c:func:`Z_find_lt()` are **not** provided for hash tables. +API for heaps +------------- + +Heaps provide the same API as the sorted data structures, except: + +* none of the find functions (:c:func:`Z_find()`, :c:func:`Z_find_gteq()` + or :c:func:`Z_find_lt()`) are available. +* iterating over the heap yields the items in semi-random order, only the + first item is guaranteed to be in order and actually the "lowest" item + on the heap. Being a heap, only the rebalancing performed on removing the + first item (either through :c:func:`Z_pop()` or :c:func:`Z_del()`) causes + the new lowest item to bubble up to the front. +* all heap modifications are O(log n). However, cacheline efficiency and + latency is likely quite a bit better than with other data structures. + Atomic lists ------------ @@ -555,7 +585,7 @@ Iteration: struct item *i; pthread_rwlock_rdlock(&itemhead_rwlock); - for_each(itemlist, &itemhead, i) { + frr_each(itemlist, &itemhead, i) { /* lock must remain held while iterating */ ... } @@ -572,7 +602,7 @@ Head removal (pop) and deallocation: pthread_rwlock_unlock(&itemhead_rwlock); /* i might still be visible for another thread doing an - * for_each() (but won't be returned by another pop()) */ + * frr_each() (but won't be returned by another pop()) */ ... pthread_rwlock_wrlock(&itemhead_rwlock); diff --git a/doc/user/basic.rst b/doc/user/basic.rst index f55b1b9d73..3df60169f7 100644 --- a/doc/user/basic.rst +++ b/doc/user/basic.rst @@ -414,6 +414,22 @@ Terminal Mode Commands (view) show [ip] bgp l2vpn evpn all overlay ... +.. _common-show-commands: + +.. index:: show thread cpu +.. clicmd:: show thread cpu [r|w|t|e|x] + + This command displays system run statistics for all the different event + types. If no options is specified all different run types are displayed + together. Additionally you can ask to look at (r)ead, (w)rite, (t)imer, + (e)vent and e(x)ecute thread event types. + +.. index:: show thread poll +.. clicmd:: show thread poll + + This command displays FRR's poll data. It allows a glimpse into how + we are setting each individual fd for the poll command at that point + in time. .. _common-invocation-options: diff --git a/doc/user/bgp.rst b/doc/user/bgp.rst index d663b4fc10..768f22c873 100644 --- a/doc/user/bgp.rst +++ b/doc/user/bgp.rst @@ -1862,11 +1862,11 @@ address-family: .. index:: label vpn export (0..1048575)|auto .. clicmd:: label vpn export (0..1048575)|auto - Specifies an optional MPLS label to be attached to a route exported from the - current unicast VRF to VPN. If label is specified as ``auto``, the label - value is automatically assigned from a pool maintained by the zebra - daemon. If zebra is not running, automatic label assignment will not - complete, which will block corresponding route export. + Enables an MPLS label to be attached to a route exported from the current + unicast VRF to VPN. If the value specified is ``auto``, the label value is + automatically assigned from a pool maintained by the Zebra daemon. If Zebra + is not running, or if this command is not configured, automatic label + assignment will not complete, which will block corresponding route export. .. index:: no label vpn export [(0..1048575)|auto] .. clicmd:: no label vpn export [(0..1048575)|auto] diff --git a/doc/user/setup.rst b/doc/user/setup.rst index ffefe37905..2cdd3a7c7f 100644 --- a/doc/user/setup.rst +++ b/doc/user/setup.rst @@ -6,8 +6,8 @@ Basic Setup After installing FRR, some basic configuration must be completed before it is ready to use. -Daemons File ------------- +Daemons Configuration File +-------------------------- After a fresh install, starting FRR will do nothing. This is because daemons must be explicitly enabled by editing a file in your configuration directory. This file is usually located at :file:`/etc/frr/daemons` and determines which @@ -34,19 +34,6 @@ systemd. The file initially looks like this: bfdd=no fabricd=no -To enable a particular daemon, simply change the corresponding 'no' to 'yes'. -Subsequent service restarts should start the daemon. - -Daemons Configuration File --------------------------- -There is another file that controls the default options passed to daemons when -starting FRR as a service. This file is located in your configuration -directory, usually at :file:`/etc/frr/daemons`. - -This file has several parts. Here is an example: - -:: - # # If this option is set the /etc/init.d/frr script automatically loads # the config via "vtysh -b" when the servers are started. @@ -71,6 +58,7 @@ This file has several parts. Here is an example: bfdd_options=" --daemon -A 127.0.0.1" fabricd_options=" --daemon -A 127.0.0.1" + #MAX_FDS=1024 # The list of daemons to watch is automatically generated by the init script. #watchfrr_options="" @@ -85,6 +73,13 @@ Breaking this file down: :: + bgpd=yes + +To enable a particular daemon, simply change the corresponding 'no' to 'yes'. +Subsequent service restarts should start the daemon. + +:: + vtysh_enable=yes As the comment says, this causes :ref:`VTYSH <vty-shell>` to apply @@ -93,6 +88,16 @@ reasons touched on in the VTYSH documentation and should generally be enabled. :: + MAX_FDS=1024 + +This allows the operator to control the number of open file descriptors +each daemon is allowed to start with. The current assumed value on +most operating systems is 1024. If the operator plans to run bgp with +several thousands of peers than this is where we would modify FRR to +allow this to happen. + +:: + zebra_options=" -s 90000000 --daemon -A 127.0.0.1" bgpd_options=" --daemon -A 127.0.0.1" ... diff --git a/doc/user/zebra.rst b/doc/user/zebra.rst index f38db9d241..40d8949297 100644 --- a/doc/user/zebra.rst +++ b/doc/user/zebra.rst @@ -23,9 +23,12 @@ Besides the common invocation options (:ref:`common-invocation-options`), the Runs in batch mode. *zebra* parses configuration file and terminates immediately. -.. option:: -k, --keep_kernel +.. option:: -K TIME, --graceful_restart TIME - When zebra starts up, don't delete old self inserted routes. + If this option is specified, the graceful restart time is TIME seconds. + Zebra, when started, will read in routes. Those routes that Zebra + identifies that it was the originator of will be swept in TIME seconds. + If no time is specified then we will sweep those routes immediately. .. option:: -r, --retain diff --git a/isisd/isis_circuit.c b/isisd/isis_circuit.c index f9a0285872..8d008d78bd 100644 --- a/isisd/isis_circuit.c +++ b/isisd/isis_circuit.c @@ -551,7 +551,7 @@ static void isis_circuit_update_all_srmflags(struct isis_circuit *circuit, if (!lspdb_count(&area->lspdb[level - 1])) continue; - for_each (lspdb, &area->lspdb[level - 1], lsp) { + frr_each (lspdb, &area->lspdb[level - 1], lsp) { if (is_set) { isis_tx_queue_add(circuit->tx_queue, lsp, TX_LSP_NORMAL); diff --git a/isisd/isis_lsp.c b/isisd/isis_lsp.c index 1991666954..4b29e6dc7e 100644 --- a/isisd/isis_lsp.c +++ b/isisd/isis_lsp.c @@ -574,7 +574,7 @@ void lsp_build_list_nonzero_ht(struct lspdb_head *head, const uint8_t *start_id, memcpy(&searchfor.hdr.lsp_id, start_id, sizeof(searchfor.hdr.lsp_id)); start = lspdb_find_gteq(head, &searchfor); - for_each_from (lspdb, head, lsp, start) { + frr_each_from (lspdb, head, lsp, start) { if (memcmp(lsp->hdr.lsp_id, stop_id, ISIS_SYS_ID_LEN + 2) > 0) break; @@ -682,12 +682,12 @@ int lsp_print_all(struct vty *vty, struct lspdb_head *head, char detail, int lsp_count = 0; if (detail == ISIS_UI_LEVEL_BRIEF) { - for_each (lspdb, head, lsp) { + frr_each (lspdb, head, lsp) { lsp_print(lsp, vty, dynhost); lsp_count++; } } else if (detail == ISIS_UI_LEVEL_DETAIL) { - for_each (lspdb, head, lsp) { + frr_each (lspdb, head, lsp) { lsp_print_detail(lsp, vty, dynhost); lsp_count++; } @@ -1855,7 +1855,7 @@ int lsp_tick(struct thread *thread) */ for (level = 0; level < ISIS_LEVELS; level++) { struct isis_lsp *next = lspdb_first(&area->lspdb[level]); - for_each_from (lspdb, &area->lspdb[level], lsp, next) { + frr_each_from (lspdb, &area->lspdb[level], lsp, next) { /* * The lsp rem_lifetime is kept at 0 for MaxAge * or diff --git a/isisd/isis_pdu.c b/isisd/isis_pdu.c index 9c633117b0..3d16d56016 100644 --- a/isisd/isis_pdu.c +++ b/isisd/isis_pdu.c @@ -2258,7 +2258,7 @@ static int send_psnp(int level, struct isis_circuit *circuit) if (CHECK_FLAG(passwd->snp_auth, SNP_AUTH_SEND)) isis_tlvs_add_auth(tlvs, passwd); - for_each (lspdb, &circuit->area->lspdb[level - 1], lsp) { + frr_each (lspdb, &circuit->area->lspdb[level - 1], lsp) { if (ISIS_CHECK_FLAG(lsp->SSNflags, circuit)) isis_tlvs_add_lsp_entry(tlvs, lsp); diff --git a/isisd/isis_tlvs.c b/isisd/isis_tlvs.c index ae149a0428..6b8e74f07b 100644 --- a/isisd/isis_tlvs.c +++ b/isisd/isis_tlvs.c @@ -3552,7 +3552,7 @@ void isis_tlvs_add_csnp_entries(struct isis_tlvs *tlvs, uint8_t *start_id, if (!first) return; - for_each_from (lspdb, head, lsp, first) { + frr_each_from (lspdb, head, lsp, first) { if (memcmp(lsp->hdr.lsp_id, stop_id, sizeof(lsp->hdr.lsp_id)) > 0 || tlvs->lsp_entries.count == num_lsps) break; diff --git a/isisd/isis_vty_fabricd.c b/isisd/isis_vty_fabricd.c index 7f2061692f..2476bd2552 100644 --- a/isisd/isis_vty_fabricd.c +++ b/isisd/isis_vty_fabricd.c @@ -176,7 +176,7 @@ DEFUN (show_lsp_flooding, continue; } - for_each (lspdb, head, lsp) { + frr_each (lspdb, head, lsp) { lsp_print_flooding(vty, lsp); vty_out(vty, "\n"); } diff --git a/lib/atomlist.h b/lib/atomlist.h index 373c481f2a..e4098ccb54 100644 --- a/lib/atomlist.h +++ b/lib/atomlist.h @@ -152,6 +152,15 @@ macro_inline type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ { return item ? prefix##_next(h, item) : NULL; } \ macro_inline size_t prefix ## _count(struct prefix##_head *h) \ { return atomic_load_explicit(&h->ah.count, memory_order_relaxed); } \ +macro_inline void prefix ## _init(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline void prefix ## _fini(struct prefix##_head *h) \ +{ \ + assert(prefix ## _count(h) == 0); \ + memset(h, 0, sizeof(*h)); \ +} \ /* ... */ /* add_head: diff --git a/lib/compiler.h b/lib/compiler.h index 474adc7c8b..c2e57db7f8 100644 --- a/lib/compiler.h +++ b/lib/compiler.h @@ -76,6 +76,15 @@ extern "C" { #define _DEPRECATED(x) deprecated #endif +/* pure = function does not modify memory & return value is the same if + * memory hasn't changed (=> allows compiler to optimize) + * + * Mostly autodetected by the compiler if function body is available (i.e. + * static inline functions in headers). Since that implies it should only be + * used in headers for non-inline functions, the "extern" is included here. + */ +#define ext_pure extern __attribute__((pure)) + /* for helper functions defined inside macros */ #define macro_inline static inline __attribute__((unused)) #define macro_pure static inline __attribute__((unused, pure)) diff --git a/lib/frrstr.c b/lib/frrstr.c index fbbc890ec6..c575c0b568 100644 --- a/lib/frrstr.c +++ b/lib/frrstr.c @@ -178,7 +178,7 @@ char *frrstr_replace(const char *str, const char *find, const char *replace) return nustr; } -bool begins_with(const char *str, const char *prefix) +bool frrstr_startswith(const char *str, const char *prefix) { if (!str || !prefix) return false; @@ -192,6 +192,20 @@ bool begins_with(const char *str, const char *prefix) return strncmp(str, prefix, lenprefix) == 0; } +bool frrstr_endswith(const char *str, const char *suffix) +{ + if (!str || !suffix) + return false; + + size_t lenstr = strlen(str); + size_t lensuffix = strlen(suffix); + + if (lensuffix > lenstr) + return false; + + return strncmp(&str[lenstr - lensuffix], suffix, lensuffix) == 0; +} + int all_digit(const char *str) { for (; *str != '\0'; str++) diff --git a/lib/frrstr.h b/lib/frrstr.h index d40ca14ba5..3a935c90cb 100644 --- a/lib/frrstr.h +++ b/lib/frrstr.h @@ -109,6 +109,7 @@ void frrstr_strvec_free(vector v); * the replacement on 'str'. This must be freed by the caller. */ char *frrstr_replace(const char *str, const char *find, const char *replace); + /* * Prefix match for string. * @@ -119,9 +120,23 @@ char *frrstr_replace(const char *str, const char *find, const char *replace); * prefix to look for * * Returns: - * true str starts with prefix, false otherwise + * true if str starts with prefix, false otherwise + */ +bool frrstr_startswith(const char *str, const char *prefix); + +/* + * Suffix match for string. + * + * str + * string to check for suffix match + * + * suffix + * suffix to look for + * + * Returns: + * true if str ends with suffix, false otherwise */ -bool begins_with(const char *str, const char *prefix); +bool frrstr_endswith(const char *str, const char *suffix); /* * Check the string only contains digit characters. diff --git a/lib/sockunion.c b/lib/sockunion.c index 5afd10eb48..8fa9a3fad9 100644 --- a/lib/sockunion.c +++ b/lib/sockunion.c @@ -366,21 +366,6 @@ int sockopt_cork(int sock, int onoff) return 0; } -int sockopt_mark_default(int sock, int mark, struct zebra_privs_t *cap) -{ -#ifdef SO_MARK - int ret; - - frr_elevate_privs(cap) { - ret = setsockopt(sock, SOL_SOCKET, SO_MARK, &mark, - sizeof(mark)); - } - return ret; -#else - return 0; -#endif -} - int sockopt_minttl(int family, int sock, int minttl) { #ifdef IP_MINTTL diff --git a/lib/sockunion.h b/lib/sockunion.h index b996735550..7091c1b5e7 100644 --- a/lib/sockunion.h +++ b/lib/sockunion.h @@ -93,7 +93,6 @@ extern int sockunion_bind(int sock, union sockunion *, unsigned short, extern int sockopt_ttl(int family, int sock, int ttl); extern int sockopt_minttl(int family, int sock, int minttl); extern int sockopt_cork(int sock, int onoff); -extern int sockopt_mark_default(int sock, int mark, struct zebra_privs_t *); extern int sockunion_socket(const union sockunion *su); extern const char *inet_sutop(const union sockunion *su, char *str); extern enum connect_result sockunion_connect(int fd, const union sockunion *su, diff --git a/lib/table.c b/lib/table.c index 2d42e2d55c..728615c776 100644 --- a/lib/table.c +++ b/lib/table.c @@ -33,10 +33,10 @@ DEFINE_MTYPE(LIB, ROUTE_NODE, "Route node") static void route_table_free(struct route_table *); -static int route_table_hash_cmp(const void *a, const void *b) +static int route_table_hash_cmp(const struct route_node *a, + const struct route_node *b) { - const struct prefix *pa = a, *pb = b; - return prefix_cmp(pa, pb); + return prefix_cmp(&a->p, &b->p); } DECLARE_HASH(rn_hash_node, struct route_node, nodehash, route_table_hash_cmp, @@ -191,7 +191,7 @@ static void set_link(struct route_node *node, struct route_node *new) } /* Find matched prefix. */ -struct route_node *route_node_match(const struct route_table *table, +struct route_node *route_node_match(struct route_table *table, union prefixconstptr pu) { const struct prefix *p = pu.p; @@ -221,7 +221,7 @@ struct route_node *route_node_match(const struct route_table *table, return NULL; } -struct route_node *route_node_match_ipv4(const struct route_table *table, +struct route_node *route_node_match_ipv4(struct route_table *table, const struct in_addr *addr) { struct prefix_ipv4 p; @@ -234,7 +234,7 @@ struct route_node *route_node_match_ipv4(const struct route_table *table, return route_node_match(table, (struct prefix *)&p); } -struct route_node *route_node_match_ipv6(const struct route_table *table, +struct route_node *route_node_match_ipv6(struct route_table *table, const struct in6_addr *addr) { struct prefix_ipv6 p; @@ -244,48 +244,50 @@ struct route_node *route_node_match_ipv6(const struct route_table *table, p.prefixlen = IPV6_MAX_PREFIXLEN; p.prefix = *addr; - return route_node_match(table, (struct prefix *)&p); + return route_node_match(table, &p); } /* Lookup same prefix node. Return NULL when we can't find route. */ -struct route_node *route_node_lookup(const struct route_table *table, +struct route_node *route_node_lookup(struct route_table *table, union prefixconstptr pu) { - struct prefix p; - struct route_node *node; - prefix_copy(&p, pu.p); - apply_mask(&p); + struct route_node rn, *node; + prefix_copy(&rn.p, pu.p); + apply_mask(&rn.p); - node = rn_hash_node_find(&table->hash, (void *)&p); + node = rn_hash_node_find(&table->hash, &rn); return (node && node->info) ? route_lock_node(node) : NULL; } /* Lookup same prefix node. Return NULL when we can't find route. */ -struct route_node *route_node_lookup_maynull(const struct route_table *table, +struct route_node *route_node_lookup_maynull(struct route_table *table, union prefixconstptr pu) { - struct prefix p; - struct route_node *node; - prefix_copy(&p, pu.p); - apply_mask(&p); + struct route_node rn, *node; + prefix_copy(&rn.p, pu.p); + apply_mask(&rn.p); - node = rn_hash_node_find(&table->hash, (void *)&p); + node = rn_hash_node_find(&table->hash, &rn); return node ? route_lock_node(node) : NULL; } /* Add node to routing table. */ -struct route_node *route_node_get(struct route_table *const table, +struct route_node *route_node_get(struct route_table *table, union prefixconstptr pu) { - const struct prefix *p = pu.p; + struct route_node search; + struct prefix *p = &search.p; + + prefix_copy(p, pu.p); + apply_mask(p); + struct route_node *new; struct route_node *node; struct route_node *match; uint16_t prefixlen = p->prefixlen; const uint8_t *prefix = &p->u.prefix; - apply_mask((struct prefix *)p); - node = rn_hash_node_find(&table->hash, (void *)p); + node = rn_hash_node_find(&table->hash, &search); if (node && node->info) return route_lock_node(node); @@ -469,7 +471,7 @@ struct route_node *route_next_until(struct route_node *node, return NULL; } -unsigned long route_table_count(const struct route_table *table) +unsigned long route_table_count(struct route_table *table) { return table->count; } @@ -604,7 +606,7 @@ static struct route_node *route_get_subtree_next(struct route_node *node) * @see route_table_get_next */ static struct route_node * -route_table_get_next_internal(const struct route_table *table, +route_table_get_next_internal(struct route_table *table, const struct prefix *p) { struct route_node *node, *tmp_node; @@ -705,7 +707,7 @@ route_table_get_next_internal(const struct route_table *table, * Find the node that occurs after the given prefix in order of * iteration. */ -struct route_node *route_table_get_next(const struct route_table *table, +struct route_node *route_table_get_next(struct route_table *table, union prefixconstptr pu) { const struct prefix *p = pu.p; diff --git a/lib/table.h b/lib/table.h index 3e3fb658ae..14be7ab656 100644 --- a/lib/table.h +++ b/lib/table.h @@ -198,26 +198,29 @@ static inline void route_table_set_info(struct route_table *table, void *d) table->info = d; } +/* ext_pure => extern __attribute__((pure)) + * does not modify memory (but depends on mem), allows compiler to optimize + */ + extern void route_table_finish(struct route_table *table); -extern struct route_node *route_top(struct route_table *table); -extern struct route_node *route_next(struct route_node *node); -extern struct route_node *route_next_until(struct route_node *node, - const struct route_node *limit); -extern struct route_node *route_node_get(struct route_table *const table, +ext_pure struct route_node *route_top(struct route_table *table); +ext_pure struct route_node *route_next(struct route_node *node); +ext_pure struct route_node *route_next_until(struct route_node *node, + const struct route_node *limit); +extern struct route_node *route_node_get(struct route_table *table, union prefixconstptr pu); -extern struct route_node *route_node_lookup(const struct route_table *table, - union prefixconstptr pu); -extern struct route_node * -route_node_lookup_maynull(const struct route_table *table, - union prefixconstptr pu); -extern struct route_node *route_node_match(const struct route_table *table, - union prefixconstptr pu); -extern struct route_node *route_node_match_ipv4(const struct route_table *table, - const struct in_addr *addr); -extern struct route_node *route_node_match_ipv6(const struct route_table *table, - const struct in6_addr *addr); - -extern unsigned long route_table_count(const struct route_table *table); +ext_pure struct route_node *route_node_lookup(struct route_table *table, + union prefixconstptr pu); +ext_pure struct route_node *route_node_lookup_maynull(struct route_table *table, + union prefixconstptr pu); +ext_pure struct route_node *route_node_match(struct route_table *table, + union prefixconstptr pu); +ext_pure struct route_node *route_node_match_ipv4(struct route_table *table, + const struct in_addr *addr); +ext_pure struct route_node *route_node_match_ipv6(struct route_table *table, + const struct in6_addr *addr); + +ext_pure unsigned long route_table_count(struct route_table *table); extern struct route_node *route_node_create(route_table_delegate_t *delegate, struct route_table *table); @@ -226,10 +229,10 @@ extern void route_node_destroy(route_table_delegate_t *delegate, struct route_table *table, struct route_node *node); -extern struct route_node *route_table_get_next(const struct route_table *table, - union prefixconstptr pu); -extern int route_table_prefix_iter_cmp(const struct prefix *p1, - const struct prefix *p2); +ext_pure struct route_node *route_table_get_next(struct route_table *table, + union prefixconstptr pu); +ext_pure int route_table_prefix_iter_cmp(const struct prefix *p1, + const struct prefix *p2); /* * Iterator functions. diff --git a/lib/thread.c b/lib/thread.c index 9489e3e923..d3fb2cdf36 100644 --- a/lib/thread.c +++ b/lib/thread.c @@ -281,7 +281,7 @@ DEFUN (show_thread_cpu, SHOW_STR "Thread information\n" "Thread CPU usage\n" - "Display filter (rwtexb)\n") + "Display filter (rwtex)\n") { uint8_t filter = (uint8_t)-1U; int idx = 0; @@ -312,7 +312,8 @@ static void show_thread_poll_helper(struct vty *vty, struct thread_master *m) vty_out(vty, "\nShowing poll FD's for %s\n", name); vty_out(vty, "----------------------%s\n", underline); - vty_out(vty, "Count: %u\n", (uint32_t)m->handler.pfdcount); + vty_out(vty, "Count: %u/%d\n", (uint32_t)m->handler.pfdcount, + m->fd_limit); for (i = 0; i < m->handler.pfdcount; i++) vty_out(vty, "\t%6d fd:%6d events:%2d revents:%2d\n", i, m->handler.pfds[i].fd, @@ -1034,7 +1035,7 @@ static void do_thread_cancel(struct thread_master *master) if (cr->eventobj) { struct thread *t; - for_each_safe(thread_list, &master->event, t) { + frr_each_safe(thread_list, &master->event, t) { if (t->arg != cr->eventobj) continue; thread_list_del(&master->event, t); @@ -1043,7 +1044,7 @@ static void do_thread_cancel(struct thread_master *master) thread_add_unuse(master, t); } - for_each_safe(thread_list, &master->ready, t) { + frr_each_safe(thread_list, &master->ready, t) { if (t->arg != cr->eventobj) continue; thread_list_del(&master->ready, t); diff --git a/lib/typerb.h b/lib/typerb.h index 3d8db06fe0..ce8446f853 100644 --- a/lib/typerb.h +++ b/lib/typerb.h @@ -22,6 +22,10 @@ #include "typesafe.h" +#ifdef __cplusplus +extern "C" { +#endif + struct typed_rb_entry { struct typed_rb_entry *rbt_parent; struct typed_rb_entry *rbt_left; @@ -179,4 +183,8 @@ macro_inline int prefix ## __cmp_uq(const struct typed_rb_entry *a, \ _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp_uq) \ /* ... */ +#ifdef __cplusplus +} +#endif + #endif /* _FRR_TYPERB_H */ diff --git a/lib/typesafe.c b/lib/typesafe.c index bd269e9b54..47a6d0af48 100644 --- a/lib/typesafe.c +++ b/lib/typesafe.c @@ -22,6 +22,7 @@ DEFINE_MTYPE_STATIC(LIB, TYPEDHASH_BUCKET, "Typed-hash bucket") DEFINE_MTYPE_STATIC(LIB, SKIPLIST_OFLOW, "Skiplist overflow") +DEFINE_MTYPE_STATIC(LIB, HEAP_ARRAY, "Typed-heap array") #if 0 static void hash_consistency_check(struct thash_head *head) @@ -375,3 +376,180 @@ void typesafe_skiplist_del(struct sskip_head *head, struct sskip_item *item, } memset(item, 0, sizeof(*item)); } + +struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head) +{ + size_t level = SKIPLIST_MAXDEPTH; + struct sskip_item *prev = &head->hitem, *next, *item; + + item = sl_level_get(prev, 0); + if (!item) + return NULL; + + do { + level--; + + next = sl_level_get(prev, level); + if (next != item) + continue; + + sl_level_set(prev, level, sl_level_get(item, level)); + } while (level); + + head->count--; + + if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) { + uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW]; + ptrval &= UINTPTR_MAX - 3; + struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval; + XFREE(MTYPE_SKIPLIST_OFLOW, oflow); + } + memset(item, 0, sizeof(*item)); + + return item; +} + +/* heap */ + +#if 0 +static void heap_consistency_check(struct heap_head *head, + int (*cmpfn)(const struct heap_item *a, + const struct heap_item *b), + uint32_t pos) +{ + uint32_t rghtpos = pos + 1; + uint32_t downpos = HEAP_NARY * (pos + 1); + + if (pos + 1 > ~0U / HEAP_NARY) + downpos = ~0U; + + if ((pos & (HEAP_NARY - 1)) != HEAP_NARY - 1 && rghtpos < head->count) { + assert(cmpfn(head->array[rghtpos], head->array[pos]) >= 0); + heap_consistency_check(head, cmpfn, rghtpos); + } + if (downpos < head->count) { + assert(cmpfn(head->array[downpos], head->array[pos]) >= 0); + heap_consistency_check(head, cmpfn, downpos); + } +} +#else +#define heap_consistency_check(head, cmpfn, pos) +#endif + +void typesafe_heap_resize(struct heap_head *head, bool grow) +{ + uint32_t newsize; + + if (grow) { + newsize = head->arraysz; + if (newsize <= 36) + newsize = 72; + else if (newsize < 262144) + newsize += newsize / 2; + else if (newsize < 0xaaaa0000) + newsize += newsize / 3; + else + assert(!newsize); + } else if (head->count > 0) { + newsize = head->count; + } else { + XFREE(MTYPE_HEAP_ARRAY, head->array); + head->arraysz = 0; + return; + } + + newsize += HEAP_NARY - 1; + newsize &= ~(HEAP_NARY - 1); + if (newsize == head->arraysz) + return; + + head->array = XREALLOC(MTYPE_HEAP_ARRAY, head->array, + newsize * sizeof(struct heap_item *)); + head->arraysz = newsize; +} + +void typesafe_heap_pushdown(struct heap_head *head, uint32_t pos, + struct heap_item *item, + int (*cmpfn)(const struct heap_item *a, + const struct heap_item *b)) +{ + uint32_t rghtpos, downpos, moveto; + + while (1) { + /* rghtpos: neighbor to the "right", inside block of NARY. + * may be invalid if last in block, check nary_last() + * downpos: first neighbor in the "downwards" block further + * away from the root + */ + rghtpos = pos + 1; + + /* make sure we can use the full 4G items */ + downpos = HEAP_NARY * (pos + 1); + if (pos + 1 > ~0U / HEAP_NARY) + /* multiplication overflowed. ~0U is guaranteed + * to be an invalid index; size limit is enforced in + * resize() + */ + downpos = ~0U; + + /* only used on break */ + moveto = pos; + +#define nary_last(x) (((x) & (HEAP_NARY - 1)) == HEAP_NARY - 1) + if (downpos >= head->count + || cmpfn(head->array[downpos], item) >= 0) { + /* not moving down; either at end or down is >= item */ + if (nary_last(pos) || rghtpos >= head->count + || cmpfn(head->array[rghtpos], item) >= 0) + /* not moving right either - got our spot */ + break; + + moveto = rghtpos; + + /* else: downpos is valid and < item. choose between down + * or right (if the latter is an option) */ + } else if (nary_last(pos) || cmpfn(head->array[rghtpos], + head->array[downpos]) >= 0) + moveto = downpos; + else + moveto = rghtpos; +#undef nary_last + + head->array[pos] = head->array[moveto]; + head->array[pos]->index = pos; + pos = moveto; + } + + head->array[moveto] = item; + item->index = moveto; + + heap_consistency_check(head, cmpfn, 0); +} + +void typesafe_heap_pullup(struct heap_head *head, uint32_t pos, + struct heap_item *item, + int (*cmpfn)(const struct heap_item *a, + const struct heap_item *b)) +{ + uint32_t moveto; + + while (pos != 0) { + if ((pos & (HEAP_NARY - 1)) == 0) + moveto = pos / HEAP_NARY - 1; + else + moveto = pos - 1; + + if (cmpfn(head->array[moveto], item) <= 0) + break; + + head->array[pos] = head->array[moveto]; + head->array[pos]->index = pos; + + pos = moveto; + } + + head->array[pos] = item; + item->index = pos; + + heap_consistency_check(head, cmpfn, 0); +} diff --git a/lib/typesafe.h b/lib/typesafe.h index 94002da599..0a4ed69e4e 100644 --- a/lib/typesafe.h +++ b/lib/typesafe.h @@ -23,19 +23,23 @@ #include <assert.h> #include "compiler.h" +#ifdef __cplusplus +extern "C" { +#endif + /* generic macros for all list-like types */ -#define for_each(prefix, head, item) \ +#define frr_each(prefix, head, item) \ for (item = prefix##_first(head); item; \ item = prefix##_next(head, item)) -#define for_each_safe(prefix, head, item) \ +#define frr_each_safe(prefix, head, item) \ for (typeof(prefix##_next_safe(head, NULL)) prefix##_safe = \ prefix##_next_safe(head, \ (item = prefix##_first(head))); \ item; \ item = prefix##_safe, \ prefix##_safe = prefix##_next_safe(head, prefix##_safe)) -#define for_each_from(prefix, head, item, from) \ +#define frr_each_from(prefix, head, item, from) \ for (item = from, from = prefix##_next_safe(head, item); \ item; \ item = from, from = prefix##_next_safe(head, from)) @@ -151,6 +155,221 @@ macro_pure size_t prefix ## _count(struct prefix##_head *h) \ } \ /* ... */ +/* don't use these structs directly */ +struct dlist_item { + struct dlist_item *next; + struct dlist_item *prev; +}; + +struct dlist_head { + struct dlist_item hitem; + size_t count; +}; + +static inline void typesafe_dlist_add(struct dlist_head *head, + struct dlist_item *prev, struct dlist_item *item) +{ + item->next = prev->next; + item->next->prev = item; + item->prev = prev; + prev->next = item; + head->count++; +} + +/* double-linked list, for fast item deletion + */ +#define PREDECL_DLIST(prefix) \ +struct prefix ## _head { struct dlist_head dh; }; \ +struct prefix ## _item { struct dlist_item di; }; + +#define INIT_DLIST(var) { .dh = { \ + .hitem = { &var.dh.hitem, &var.dh.hitem }, }, } + +#define DECLARE_DLIST(prefix, type, field) \ + \ +macro_inline void prefix ## _init(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ + h->dh.hitem.prev = &h->dh.hitem; \ + h->dh.hitem.next = &h->dh.hitem; \ +} \ +macro_inline void prefix ## _fini(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \ +{ \ + typesafe_dlist_add(&h->dh, &h->dh.hitem, &item->field.di); \ +} \ +macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \ +{ \ + typesafe_dlist_add(&h->dh, h->dh.hitem.prev, &item->field.di); \ +} \ +macro_inline void prefix ## _add_after(struct prefix##_head *h, \ + type *after, type *item) \ +{ \ + struct dlist_item *prev; \ + prev = after ? &after->field.di : &h->dh.hitem; \ + typesafe_dlist_add(&h->dh, prev, &item->field.di); \ +} \ +macro_inline void prefix ## _del(struct prefix##_head *h, type *item) \ +{ \ + struct dlist_item *ditem = &item->field.di; \ + ditem->prev->next = ditem->next; \ + ditem->next->prev = ditem->prev; \ + h->dh.count--; \ + ditem->prev = ditem->next = NULL; \ +} \ +macro_inline type *prefix ## _pop(struct prefix##_head *h) \ +{ \ + struct dlist_item *ditem = h->dh.hitem.next; \ + if (ditem == &h->dh.hitem) \ + return NULL; \ + ditem->prev->next = ditem->next; \ + ditem->next->prev = ditem->prev; \ + h->dh.count--; \ + return container_of(ditem, type, field.di); \ +} \ +macro_pure type *prefix ## _first(struct prefix##_head *h) \ +{ \ + struct dlist_item *ditem = h->dh.hitem.next; \ + if (ditem == &h->dh.hitem) \ + return NULL; \ + return container_of(ditem, type, field.di); \ +} \ +macro_pure type *prefix ## _next(struct prefix##_head * h, type *item) \ +{ \ + struct dlist_item *ditem = &item->field.di; \ + if (ditem->next == &h->dh.hitem) \ + return NULL; \ + return container_of(ditem->next, type, field.di); \ +} \ +macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ +{ \ + if (!item) \ + return NULL; \ + return prefix ## _next(h, item); \ +} \ +macro_pure size_t prefix ## _count(struct prefix##_head *h) \ +{ \ + return h->dh.count; \ +} \ +/* ... */ + +/* note: heap currently caps out at 4G items */ + +#define HEAP_NARY 8U +typedef uint32_t heap_index_i; + +struct heap_item { + uint32_t index; +}; + +struct heap_head { + struct heap_item **array; + uint32_t arraysz, count; +}; + +#define HEAP_RESIZE_TRESH_UP(h) \ + (h->hh.count + 1 >= h->hh.arraysz) +#define HEAP_RESIZE_TRESH_DN(h) \ + (h->hh.count == 0 || \ + h->hh.arraysz - h->hh.count > (h->hh.count + 1024) / 2) + +#define PREDECL_HEAP(prefix) \ +struct prefix ## _head { struct heap_head hh; }; \ +struct prefix ## _item { struct heap_item hi; }; + +#define INIT_HEAP(var) { } + +#define DECLARE_HEAP(prefix, type, field, cmpfn) \ + \ +macro_inline void prefix ## _init(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline void prefix ## _fini(struct prefix##_head *h) \ +{ \ + assert(h->hh.count == 0); \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline int prefix ## __cmp(const struct heap_item *a, \ + const struct heap_item *b) \ +{ \ + return cmpfn(container_of(a, type, field.hi), \ + container_of(b, type, field.hi)); \ +} \ +macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ +{ \ + if (HEAP_RESIZE_TRESH_UP(h)) \ + typesafe_heap_resize(&h->hh, true); \ + typesafe_heap_pullup(&h->hh, h->hh.count, &item->field.hi, \ + prefix ## __cmp); \ + h->hh.count++; \ + return NULL; \ +} \ +macro_inline void prefix ## _del(struct prefix##_head *h, type *item) \ +{ \ + struct heap_item *other; \ + uint32_t index = item->field.hi.index; \ + assert(h->hh.array[index] == &item->field.hi); \ + h->hh.count--; \ + other = h->hh.array[h->hh.count]; \ + if (cmpfn(container_of(other, type, field.hi), item) < 0) \ + typesafe_heap_pullup(&h->hh, index, other, prefix ## __cmp); \ + else \ + typesafe_heap_pushdown(&h->hh, index, other, prefix ## __cmp); \ + if (HEAP_RESIZE_TRESH_DN(h)) \ + typesafe_heap_resize(&h->hh, false); \ +} \ +macro_inline type *prefix ## _pop(struct prefix##_head *h) \ +{ \ + struct heap_item *hitem, *other; \ + if (h->hh.count == 0) \ + return NULL; \ + hitem = h->hh.array[0]; \ + h->hh.count--; \ + other = h->hh.array[h->hh.count]; \ + typesafe_heap_pushdown(&h->hh, 0, other, prefix ## __cmp); \ + if (HEAP_RESIZE_TRESH_DN(h)) \ + typesafe_heap_resize(&h->hh, false); \ + return container_of(hitem, type, field.hi); \ +} \ +macro_pure type *prefix ## _first(struct prefix##_head *h) \ +{ \ + if (h->hh.count == 0) \ + return NULL; \ + return container_of(h->hh.array[0], type, field.hi); \ +} \ +macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \ +{ \ + uint32_t idx = item->field.hi.index + 1; \ + if (idx >= h->hh.count) \ + return NULL; \ + return container_of(h->hh.array[idx], type, field.hi); \ +} \ +macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ +{ \ + if (!item) \ + return NULL; \ + return prefix ## _next(h, item); \ +} \ +macro_pure size_t prefix ## _count(struct prefix##_head *h) \ +{ \ + return h->hh.count; \ +} \ +/* ... */ + +extern void typesafe_heap_resize(struct heap_head *head, bool grow); +extern void typesafe_heap_pushdown(struct heap_head *head, uint32_t index, + struct heap_item *item, + int (*cmpfn)(const struct heap_item *a, + const struct heap_item *b)); +extern void typesafe_heap_pullup(struct heap_head *head, uint32_t index, + struct heap_item *item, + int (*cmpfn)(const struct heap_item *a, + const struct heap_item *b)); + /* single-linked list, sorted. * can be used as priority queue with add / pop */ @@ -275,7 +494,7 @@ macro_pure size_t prefix ## _count(struct prefix##_head *h) \ #define DECLARE_SORTLIST_UNIQ(prefix, type, field, cmpfn) \ _DECLARE_SORTLIST(prefix, type, field, cmpfn, cmpfn) \ \ -macro_inline type *prefix ## _find(const struct prefix##_head *h, const type *item) \ +macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \ { \ struct ssort_item *sitem = h->sh.first; \ int cmpval = 0; \ @@ -383,7 +602,7 @@ macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ *np = &item->field.hi; \ return NULL; \ } \ -macro_inline type *prefix ## _find(const struct prefix##_head *h, const type *item) \ +macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \ { \ if (!h->hh.tabshift) \ return NULL; \ @@ -538,11 +757,8 @@ macro_inline void prefix ## _del(struct prefix##_head *h, type *item) \ } \ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ { \ - struct sskip_item *sitem = h->sh.hitem.next[0]; \ - if (!sitem) \ - return NULL; \ - typesafe_skiplist_del(&h->sh, sitem, cmpfn_uq); \ - return container_of(sitem, type, field.si); \ + struct sskip_item *sitem = typesafe_skiplist_pop(&h->sh); \ + return container_of_null(sitem, type, field.si); \ } \ macro_pure type *prefix ## _first(struct prefix##_head *h) \ { \ @@ -576,7 +792,7 @@ macro_inline int prefix ## __cmp(const struct sskip_item *a, \ return cmpfn(container_of(a, type, field.si), \ container_of(b, type, field.si)); \ } \ -macro_inline type *prefix ## _find(const struct prefix##_head *h, const type *item) \ +macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \ { \ struct sskip_item *sitem = typesafe_skiplist_find(&h->sh, \ &item->field.si, &prefix ## __cmp); \ @@ -636,6 +852,11 @@ extern void typesafe_skiplist_del(struct sskip_head *head, struct sskip_item *item, int (*cmpfn)( const struct sskip_item *a, const struct sskip_item *b)); +extern struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head); + +#ifdef __cplusplus +} +#endif /* this needs to stay at the end because both files include each other. * the resolved order is typesafe.h before typerb.h diff --git a/pimd/pim_ifchannel.c b/pimd/pim_ifchannel.c index 352177db2b..9b242e9be5 100644 --- a/pimd/pim_ifchannel.c +++ b/pimd/pim_ifchannel.c @@ -1404,7 +1404,9 @@ void pim_ifchannel_set_star_g_join_state(struct pim_ifchannel *ch, int eom, PIM_IF_FLAG_UNSET_S_G_RPT(child->flags); child->ifjoin_state = PIM_IFJOIN_NOINFO; - if (I_am_RP(pim, child->sg.grp)) { + if ((I_am_RP(pim, child->sg.grp)) && + (!pim_upstream_empty_inherited_olist( + child->upstream))) { pim_channel_add_oif( child->upstream->channel_oil, ch->interface, PIM_OIF_FLAG_PROTO_STAR); diff --git a/ripd/rip_main.c b/ripd/rip_main.c index 65da51f83a..773cb1d0fe 100644 --- a/ripd/rip_main.c +++ b/ripd/rip_main.c @@ -41,10 +41,7 @@ #include "ripd/rip_errors.h" /* ripd options. */ -#if CONFDATE > 20190521 - CPP_NOTICE("-r / --retain has reached deprecation EOL, remove") -#endif -static struct option longopts[] = {{"retain", no_argument, NULL, 'r'}, {0}}; +static struct option longopts[] = {{0}}; /* ripd privileges */ zebra_capabilities_t _caps_p[] = {ZCAP_NET_RAW, ZCAP_BIND, ZCAP_SYS_ADMIN}; @@ -129,10 +126,7 @@ FRR_DAEMON_INFO(ripd, RIP, .vty_port = RIP_VTY_PORT, .privs = &ripd_privs, .yang_modules = ripd_yang_modules, .n_yang_modules = array_size(ripd_yang_modules), ) -#if CONFDATE > 20190521 -CPP_NOTICE("-r / --retain has reached deprecation EOL, remove") -#endif -#define DEPRECATED_OPTIONS "r" +#define DEPRECATED_OPTIONS "" /* Main routine of ripd. */ int main(int argc, char **argv) diff --git a/ripngd/ripng_main.c b/ripngd/ripng_main.c index c755bd83ce..4b027019c0 100644 --- a/ripngd/ripng_main.c +++ b/ripngd/ripng_main.c @@ -41,10 +41,7 @@ #include "ripngd/ripngd.h" /* RIPngd options. */ -#if CONFDATE > 20190521 - CPP_NOTICE("-r / --retain has reached deprecation EOL, remove") -#endif -struct option longopts[] = {{"retain", no_argument, NULL, 'r'}, {0}}; +struct option longopts[] = {{0}}; /* ripngd privileges */ zebra_capabilities_t _caps_p[] = {ZCAP_NET_RAW, ZCAP_BIND, ZCAP_SYS_ADMIN}; @@ -132,10 +129,7 @@ FRR_DAEMON_INFO(ripngd, RIPNG, .vty_port = RIPNG_VTY_PORT, .yang_modules = ripngd_yang_modules, .n_yang_modules = array_size(ripngd_yang_modules), ) -#if CONFDATE > 20190521 -CPP_NOTICE("-r / --retain has reached deprecation EOL, remove") -#endif -#define DEPRECATED_OPTIONS "r" +#define DEPRECATED_OPTIONS "" /* RIPngd main routine. */ int main(int argc, char **argv) diff --git a/tests/lib/cxxcompat.c b/tests/lib/cxxcompat.c index 12c333c8b6..48fa0ec8a9 100644 --- a/tests/lib/cxxcompat.c +++ b/tests/lib/cxxcompat.c @@ -92,6 +92,8 @@ #include "lib/table.h" #include "lib/termtable.h" #include "lib/thread.h" +#include "lib/typesafe.h" +#include "lib/typerb.h" #include "lib/vector.h" #include "lib/vlan.h" #include "lib/vrf.h" diff --git a/tests/lib/test_atomlist.c b/tests/lib/test_atomlist.c index 078e05e336..249fff8edb 100644 --- a/tests/lib/test_atomlist.c +++ b/tests/lib/test_atomlist.c @@ -308,7 +308,7 @@ static void run_tr(struct testrun *tr) if (tr->sorted) { uint64_t prevval = 0; - for_each(asort, &shead, item) { + frr_each(asort, &shead, item) { assert(item->val1 >= prevval); prevval = item->val1; c++; @@ -316,7 +316,7 @@ static void run_tr(struct testrun *tr) assert(c == asort_count(&shead)); } else { prev = &dummy; - for_each(alist, &ahead, item) { + frr_each(alist, &ahead, item) { assert(item != prev); prev = item; c++; @@ -335,7 +335,7 @@ static void dump(const char *lbl) size_t ctr = 0; printf("dumping %s:\n", lbl); - for_each_safe(alist, &ahead, item) { + frr_each_safe(alist, &ahead, item) { printf("%s %3zu %p %3"PRIu64" %3"PRIu64"\n", lbl, ctr++, (void *)item, item->val1, item->val2); } diff --git a/tests/lib/test_typelist.c b/tests/lib/test_typelist.c index 68ea82ea41..2438fb5f08 100644 --- a/tests/lib/test_typelist.c +++ b/tests/lib/test_typelist.c @@ -25,6 +25,7 @@ #include <string.h> #include <unistd.h> #include <assert.h> +#include <arpa/inet.h> #define WNO_ATOMLIST_UNSAFE_FIND @@ -32,6 +33,8 @@ #include "atomlist.h" #include "memory.h" #include "monotime.h" +#include "jhash.h" +#include "sha256.h" #include "tests/helpers/c/prng.h" @@ -49,31 +52,32 @@ #define _DECLARE(type, ...) DECLARE_##type(__VA_ARGS__) #define DECLARE(type, ...) _DECLARE(type, __VA_ARGS__) -#define _U_SORTLIST_UNIQ 1 -#define _U_SORTLIST_NONUNIQ 0 -#define _U_HASH 1 -#define _U_SKIPLIST_UNIQ 1 -#define _U_SKIPLIST_NONUNIQ 0 -#define _U_RBTREE_UNIQ 1 -#define _U_RBTREE_NONUNIQ 0 -#define _U_ATOMSORT_UNIQ 1 -#define _U_ATOMSORT_NONUNIQ 0 - -#define _IS_UNIQ(type) _U_##type -#define IS_UNIQ(type) _IS_UNIQ(type) - -#define _H_SORTLIST_UNIQ 0 -#define _H_SORTLIST_NONUNIQ 0 -#define _H_HASH 1 -#define _H_SKIPLIST_UNIQ 0 -#define _H_SKIPLIST_NONUNIQ 0 -#define _H_RBTREE_UNIQ 0 -#define _H_RBTREE_NONUNIQ 0 -#define _H_ATOMSORT_UNIQ 0 -#define _H_ATOMSORT_NONUNIQ 0 - -#define _IS_HASH(type) _H_##type -#define IS_HASH(type) _IS_HASH(type) +#define T_SORTED (1 << 0) +#define T_UNIQ (1 << 1) +#define T_HASH (1 << 2) +#define T_HEAP (1 << 3) +#define T_ATOMIC (1 << 4) + +#define _T_LIST (0) +#define _T_DLIST (0) +#define _T_ATOMLIST (0 | T_ATOMIC) +#define _T_HEAP (T_SORTED | T_HEAP) +#define _T_SORTLIST_UNIQ (T_SORTED | T_UNIQ) +#define _T_SORTLIST_NONUNIQ (T_SORTED) +#define _T_HASH (T_SORTED | T_UNIQ | T_HASH) +#define _T_SKIPLIST_UNIQ (T_SORTED | T_UNIQ) +#define _T_SKIPLIST_NONUNIQ (T_SORTED) +#define _T_RBTREE_UNIQ (T_SORTED | T_UNIQ) +#define _T_RBTREE_NONUNIQ (T_SORTED) +#define _T_ATOMSORT_UNIQ (T_SORTED | T_UNIQ | T_ATOMIC) +#define _T_ATOMSORT_NONUNIQ (T_SORTED | T_ATOMIC) + +#define _T_TYPE(type) _T_##type +#define IS_SORTED(type) (_T_TYPE(type) & T_SORTED) +#define IS_UNIQ(type) (_T_TYPE(type) & T_UNIQ) +#define IS_HASH(type) (_T_TYPE(type) & T_HASH) +#define IS_HEAP(type) (_T_TYPE(type) & T_HEAP) +#define IS_ATOMIC(type) (_T_TYPE(type) & T_ATOMIC) static struct timeval ref, ref0; @@ -96,6 +100,18 @@ static void ts_end(void) printf("%7"PRId64"us total\n", us); } +#define TYPE LIST +#include "test_typelist.h" + +#define TYPE DLIST +#include "test_typelist.h" + +#define TYPE ATOMLIST +#include "test_typelist.h" + +#define TYPE HEAP +#include "test_typelist.h" + #define TYPE SORTLIST_UNIQ #include "test_typelist.h" @@ -105,6 +121,12 @@ static void ts_end(void) #define TYPE HASH #include "test_typelist.h" +#define TYPE HASH_collisions +#define REALTYPE HASH +#define SHITTY_HASH +#include "test_typelist.h" +#undef SHITTY_HASH + #define TYPE SKIPLIST_UNIQ #include "test_typelist.h" @@ -127,9 +149,14 @@ int main(int argc, char **argv) { srandom(1); + test_LIST(); + test_DLIST(); + test_ATOMLIST(); + test_HEAP(); test_SORTLIST_UNIQ(); test_SORTLIST_NONUNIQ(); test_HASH(); + test_HASH_collisions(); test_SKIPLIST_UNIQ(); test_SKIPLIST_NONUNIQ(); test_RBTREE_UNIQ(); diff --git a/tests/lib/test_typelist.h b/tests/lib/test_typelist.h index 60a37e84ed..b288f0bd8e 100644 --- a/tests/lib/test_typelist.h +++ b/tests/lib/test_typelist.h @@ -30,33 +30,47 @@ #define list_next_safe concat(TYPE, _next_safe) #define list_count concat(TYPE, _count) #define list_add concat(TYPE, _add) +#define list_add_head concat(TYPE, _add_head) +#define list_add_tail concat(TYPE, _add_tail) +#define list_add_after concat(TYPE, _add_after) #define list_find concat(TYPE, _find) #define list_find_lt concat(TYPE, _find_lt) #define list_find_gteq concat(TYPE, _find_gteq) #define list_del concat(TYPE, _del) #define list_pop concat(TYPE, _pop) -PREDECL(TYPE, list) +#define ts_hash concat(ts_hash_, TYPE) + +#ifndef REALTYPE +#define REALTYPE TYPE +#endif + +PREDECL(REALTYPE, list) struct item { uint64_t val; struct list_item itm; int scratchpad; }; +#if IS_SORTED(REALTYPE) static int list_cmp(const struct item *a, const struct item *b); -#if IS_HASH(TYPE) +#if IS_HASH(REALTYPE) static uint32_t list_hash(const struct item *a); -DECLARE(TYPE, list, struct item, itm, list_cmp, list_hash) +DECLARE(REALTYPE, list, struct item, itm, list_cmp, list_hash) static uint32_t list_hash(const struct item *a) { +#ifdef SHITTY_HASH /* crappy hash to get some hash collisions */ return a->val ^ (a->val << 29) ^ 0x55AA0000U; +#else + return jhash_1word(a->val, 0xdeadbeef); +#endif } #else -DECLARE(TYPE, list, struct item, itm, list_cmp) +DECLARE(REALTYPE, list, struct item, itm, list_cmp) #endif static int list_cmp(const struct item *a, const struct item *b) @@ -68,16 +82,67 @@ static int list_cmp(const struct item *a, const struct item *b) return 0; } +#else /* !IS_SORTED */ +DECLARE(REALTYPE, list, struct item, itm) +#endif + #define NITEM 10000 struct item itm[NITEM]; -static struct list_head head = concat(INIT_, TYPE)(head); +static struct list_head head = concat(INIT_, REALTYPE)(head); + +static void ts_hash(const char *text, const char *expect) +{ + int64_t us = monotime_since(&ref, NULL); + SHA256_CTX ctx; + struct item *item; + unsigned i = 0; + uint8_t hash[32]; + char hashtext[65]; + uint32_t count; + + count = htonl(list_count(&head)); + + SHA256_Init(&ctx); + SHA256_Update(&ctx, &count, sizeof(count)); + + frr_each (list, &head, item) { + struct { + uint32_t val_upper, val_lower, index; + } hashitem = { + htonl(item->val >> 32), + htonl(item->val & 0xFFFFFFFFULL), + htonl(i), + }; + SHA256_Update(&ctx, &hashitem, sizeof(hashitem)); + i++; + assert(i < count); + } + SHA256_Final(hash, &ctx); + + for (i = 0; i < sizeof(hash); i++) + sprintf(hashtext + i * 2, "%02x", hash[i]); + + printf("%7"PRId64"us %-25s %s%s\n", us, text, + expect ? " " : "*", hashtext); + if (expect && strcmp(expect, hashtext)) { + printf("%-21s %s\n", "EXPECTED:", expect); + assert(0); + } + monotime(&ref); +} +/* hashes will have different item ordering */ +#if IS_HASH(REALTYPE) || IS_HEAP(REALTYPE) +#define ts_hashx(pos, csum) ts_hash(pos, NULL) +#else +#define ts_hashx(pos, csum) ts_hash(pos, csum) +#endif static void concat(test_, TYPE)(void) { size_t i, j, k, l; struct prng *prng; - struct item *item, *prev; - struct item dummy; + struct item *item, *prev __attribute__((unused)); + struct item dummy __attribute__((unused)); memset(itm, 0, sizeof(itm)); for (i = 0; i < NITEM; i++) @@ -87,10 +152,11 @@ static void concat(test_, TYPE)(void) ts_start(); list_init(&head); - ts_ref("init"); - assert(list_first(&head) == NULL); + ts_hash("init", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119"); + +#if IS_SORTED(REALTYPE) prng = prng_new(0); k = 0; for (i = 0; i < NITEM; i++) { @@ -99,17 +165,20 @@ static void concat(test_, TYPE)(void) list_add(&head, &itm[j]); itm[j].scratchpad = 1; k++; - } else + } +#if !IS_HEAP(REALTYPE) + else assert(list_add(&head, &itm[j]) == &itm[j]); +#endif } assert(list_count(&head) == k); assert(list_first(&head) != NULL); - ts_ref("fill"); + ts_hashx("fill", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838"); k = 0; prev = NULL; - for_each(list, &head, item) { -#if IS_HASH(TYPE) + frr_each(list, &head, item) { +#if IS_HASH(REALTYPE) || IS_HEAP(REALTYPE) /* hash table doesn't give sorting */ (void)prev; #else @@ -121,7 +190,7 @@ static void concat(test_, TYPE)(void) assert(list_count(&head) == k); ts_ref("walk"); -#if IS_UNIQ(TYPE) +#if IS_UNIQ(REALTYPE) prng_free(prng); prng = prng_new(0); @@ -143,8 +212,23 @@ static void concat(test_, TYPE)(void) list_del(&head, &dummy); } } - ts_ref("add-dup"); -#else /* !IS_UNIQ(TYPE) */ + ts_hashx("add-dup", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838"); + +#elif IS_HEAP(REALTYPE) + /* heap - partially sorted. */ + prev = NULL; + l = k / 2; + for (i = 0; i < l; i++) { + item = list_pop(&head); + if (prev) + assert(prev->val < item->val); + item->scratchpad = 0; + k--; + prev = item; + } + ts_hash("pop", NULL); + +#else /* !IS_UNIQ(REALTYPE) && !IS_HEAP(REALTYPE) */ for (i = 0; i < NITEM; i++) { j = prng_rand(prng) % NITEM; memset(&dummy, 0, sizeof(dummy)); @@ -173,9 +257,9 @@ static void concat(test_, TYPE)(void) assert(list_next(&head, &dummy)->val > j); list_del(&head, &dummy); } - ts_ref("add-dup+find_{lt,gteq}"); + ts_hash("add-dup+find_{lt,gteq}", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838"); #endif -#if !IS_HASH(TYPE) +#if !IS_HASH(REALTYPE) && !IS_HEAP(REALTYPE) prng_free(prng); prng = prng_new(123456); @@ -217,9 +301,9 @@ static void concat(test_, TYPE)(void) } } assert(l + list_count(&head) == k); - ts_ref("del"); + ts_hashx("del", "cb2e5d80f08a803ef7b56c15e981b681adcea214bebc2f55e12e0bfb242b07ca"); - for_each_safe(list, &head, item) { + frr_each_safe(list, &head, item) { assert(item->scratchpad != 0); if (item->val & 1) { @@ -229,8 +313,34 @@ static void concat(test_, TYPE)(void) } } assert(l + list_count(&head) == k); - ts_ref("for_each_safe+del"); + ts_hashx("frr_each_safe+del", "e0beb71dd963a75af05b722b8e71b61b304587d860c8accdc4349067542b86bb"); +#else /* !IS_SORTED */ + prng = prng_new(0); + k = 0; + for (i = 0; i < NITEM; i++) { + j = prng_rand(prng) % NITEM; + if (itm[j].scratchpad == 0) { + list_add_tail(&head, &itm[j]); + itm[j].scratchpad = 1; + k++; + } + } + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hash("fill / add_tail", "eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19"); + + for (i = 0; i < NITEM / 2; i++) { + j = prng_rand(prng) % NITEM; + if (itm[j].scratchpad == 1) { + list_del(&head, &itm[j]); + itm[j].scratchpad = 0; + k--; + } + } + ts_hash("del-prng", "86d568a95eb429dab3162976c5a5f3f75aabc835932cd682aa280b6923549564"); + + l = 0; while ((item = list_pop(&head))) { assert(item->scratchpad != 0); @@ -240,7 +350,181 @@ static void concat(test_, TYPE)(void) assert(l == k); assert(list_count(&head) == 0); assert(list_first(&head) == NULL); - ts_ref("pop"); + ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119"); + + prng_free(prng); + prng = prng_new(0x1e5a2d69); + + k = 0; + for (i = 0; i < NITEM; i++) { + j = prng_rand(prng) % NITEM; + if (itm[j].scratchpad == 0) { + list_add_head(&head, &itm[j]); + itm[j].scratchpad = 1; + k++; + } + } + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hash("fill / add_head", "3084d8f8a28b8c756ccc0a92d60d86f6d776273734ddc3f9e1d89526f5ca2795"); + + for (i = 0; i < NITEM / 2; i++) { + j = prng_rand(prng) % NITEM; + if (itm[j].scratchpad == 1) { + list_del(&head, &itm[j]); + itm[j].scratchpad = 0; + k--; + } + } + ts_hash("del-prng", "dc916fa7ea4418792c7c8232d74df2887f9975ead4222f4b977be6bc0b52285e"); + + l = 0; + while ((item = list_pop(&head))) { + assert(item->scratchpad != 0); + + item->scratchpad = 0; + l++; + } + assert(l == k); + assert(list_count(&head) == 0); + assert(list_first(&head) == NULL); + ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119"); + + prng_free(prng); + prng = prng_new(0x692d1e5a); + + k = 0; + for (i = 0; i < NITEM; i++) { + j = prng_rand(prng) % NITEM; + if (itm[j].scratchpad == 0) { + if (prng_rand(prng) & 1) { + list_add_tail(&head, &itm[j]); + } else { + list_add_head(&head, &itm[j]); + } + itm[j].scratchpad = 1; + k++; + } + } + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hash("fill / add_{head,tail}", "93fa180a575c96e4b6c3775c2de7843ee3254dd6ed5af699bbe155f994114b06"); + + for (i = 0; i < NITEM * 3; i++) { + int op = prng_rand(prng); + j = prng_rand(prng) % NITEM; + + if (op & 1) { + /* delete or pop */ + if (op & 2) { + item = list_pop(&head); + if (!item) + continue; + } else { + item = &itm[j]; + if (item->scratchpad == 0) + continue; + list_del(&head, item); + } + item->scratchpad = 0; + k--; + } else { + item = &itm[j]; + if (item->scratchpad != 0) + continue; + + item->scratchpad = 1; + k++; + + switch ((op >> 1) & 1) { + case 0: + list_add_head(&head, item); + break; + case 1: + list_add_tail(&head, item); + break; + default: + assert(0); + } + } + } + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hash("prng add/del", "4909f31d06bb006efca4dfeebddb8de071733ddf502f89b6d532155208bbc6df"); + +#if !IS_ATOMIC(REALTYPE) + /* variant with add_after */ + + for (i = 0; i < NITEM * 3; i++) { + int op = prng_rand(prng); + j = prng_rand(prng) % NITEM; + + if (op & 1) { + /* delete or pop */ + if (op & 2) { + item = list_pop(&head); + if (!item) + continue; + } else { + item = &itm[j]; + if (item->scratchpad == 0) + continue; + list_del(&head, item); + } + item->scratchpad = 0; + k--; + } else { + item = &itm[j]; + if (item->scratchpad != 0) + continue; + + item->scratchpad = 1; + k++; + + switch ((op >> 1) & 3) { + case 0: + list_add_head(&head, item); + break; + case 1: + list_add_tail(&head, item); + break; + case 2: + case 3: + prev = NULL; + l = 0; + do { + j = prng_rand(prng) % NITEM; + prev = &itm[j]; + if (prev->scratchpad == 0 + || prev == item) + prev = NULL; + l++; + } while (!prev && l < 10); + list_add_after(&head, prev, item); + break; + default: + assert(0); + } + } + } + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hash("prng add/after/del", "84c5fc83294eabebb9808ccbba32a303c4fca084db87ed1277d2bae1f8c5bee4"); +#endif + + l = 0; +#endif + + while ((item = list_pop(&head))) { + assert(item->scratchpad != 0); + + item->scratchpad = 0; + l++; + } + assert(l == k); + assert(list_count(&head) == 0); + assert(list_first(&head) == NULL); + ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119"); list_fini(&head); ts_ref("fini"); @@ -248,6 +532,8 @@ static void concat(test_, TYPE)(void) printf("%s end\n", str(TYPE)); } +#undef ts_hashx + #undef item #undef itm #undef head @@ -263,10 +549,14 @@ static void concat(test_, TYPE)(void) #undef list_next_safe #undef list_count #undef list_add +#undef list_add_head +#undef list_add_tail +#undef list_add_after #undef list_find #undef list_find_lt #undef list_find_gteq #undef list_del #undef list_pop +#undef REALTYPE #undef TYPE diff --git a/tests/lib/test_typelist.py b/tests/lib/test_typelist.py index 3b7373ceb8..0b3c743971 100644 --- a/tests/lib/test_typelist.py +++ b/tests/lib/test_typelist.py @@ -3,9 +3,14 @@ import frrtest class TestTypelist(frrtest.TestMultiOut): program = './test_typelist' +TestTypelist.onesimple('LIST end') +TestTypelist.onesimple('DLIST end') +TestTypelist.onesimple('ATOMLIST end') +TestTypelist.onesimple('HEAP end') TestTypelist.onesimple('SORTLIST_UNIQ end') TestTypelist.onesimple('SORTLIST_NONUNIQ end') TestTypelist.onesimple('HASH end') +TestTypelist.onesimple('HASH_collisions end') TestTypelist.onesimple('SKIPLIST_UNIQ end') TestTypelist.onesimple('SKIPLIST_NONUNIQ end') TestTypelist.onesimple('RBTREE_UNIQ end') diff --git a/tools/etc/frr/daemons b/tools/etc/frr/daemons index b920621d70..79c52d30d1 100644 --- a/tools/etc/frr/daemons +++ b/tools/etc/frr/daemons @@ -56,6 +56,14 @@ bfdd_options=" -A 127.0.0.1" fabricd_options="-A 127.0.0.1" vrrpd_options=" -A 127.0.0.1" +# +# This is the maximum number of FD's that will be available. +# Upon startup this is read by the control files and ulimit +# is called. Uncomment and use a reasonable value for your +# setup if you are expecting a large number of peers in +# say BGP. +#MAX_FDS=1024 + # The list of daemons to watch is automatically generated by the init script. #watchfrr_options="" diff --git a/vrrpd/vrrp.c b/vrrpd/vrrp.c index ad09caf359..3d535cbfba 100644 --- a/vrrpd/vrrp.c +++ b/vrrpd/vrrp.c @@ -763,7 +763,7 @@ static void vrrp_send_advertisement(struct vrrp_router *r) const char *group = r->family == AF_INET ? VRRP_MCASTV4_GROUP_STR : VRRP_MCASTV6_GROUP_STR; - str2sockunion(group, &dest); + (void)str2sockunion(group, &dest); ssize_t sent = sendto(r->sock_tx, pkt, (size_t)pktsz, 0, &dest.sa, sockunion_sizeof(&dest)); @@ -969,7 +969,7 @@ static int vrrp_read(struct thread *thread) uint8_t control[64]; struct ipaddr src = {}; - struct msghdr m; + struct msghdr m = {}; struct iovec iov; iov.iov_base = r->ibuf; @@ -1384,7 +1384,6 @@ static void vrrp_change_state_backup(struct vrrp_router *r) */ static void vrrp_change_state_initialize(struct vrrp_router *r) { - r->vr->advertisement_interval = r->vr->advertisement_interval; r->master_adver_interval = 0; vrrp_recalculate_timers(r); diff --git a/vrrpd/vrrp_arp.c b/vrrpd/vrrp_arp.c index 8e903e137f..78e153a082 100644 --- a/vrrpd/vrrp_arp.c +++ b/vrrpd/vrrp_arp.c @@ -124,7 +124,7 @@ void vrrp_garp_send(struct vrrp_router *r, struct in_addr *v4) if (ifp->flags & IFF_NOARP) { zlog_warn( VRRP_LOGPFX VRRP_LOGPFX_VRID VRRP_LOGPFX_FAM - "Unable to send gratuitous ARP on %s; has IFF_NOARP\n", + "Unable to send gratuitous ARP on %s; has IFF_NOARP", r->vr->vrid, family2str(r->family), ifp->name); return; } @@ -132,6 +132,14 @@ void vrrp_garp_send(struct vrrp_router *r, struct in_addr *v4) /* Build garp */ garpbuf_len = vrrp_build_garp(garpbuf, ifp, v4); + if (garpbuf_len < 0) { + zlog_warn( + VRRP_LOGPFX VRRP_LOGPFX_VRID VRRP_LOGPFX_FAM + "Unable to send gratuitous ARP on %s; MAC address unknown", + r->vr->vrid, family2str(r->family), ifp->name); + return; + }; + /* Send garp */ inet_ntop(AF_INET, v4, astr, sizeof(astr)); diff --git a/vrrpd/vrrp_ndisc.c b/vrrpd/vrrp_ndisc.c index 8081533ebc..348958509a 100644 --- a/vrrpd/vrrp_ndisc.c +++ b/vrrpd/vrrp_ndisc.c @@ -139,7 +139,10 @@ static int vrrp_ndisc_una_build(struct interface *ifp, struct ipaddr *ip, ph.dst = ip6h->ip6_dst; ph.ulpl = htonl(len); ph.next_hdr = IPPROTO_ICMPV6; - icmp6h->icmp6_cksum = in_cksum_with_ph6(&ph, (void *)icmp6h, len); + + /* Suppress static analysis warnings about accessing icmp6 oob */ + void *offset = icmp6h; + icmp6h->icmp6_cksum = in_cksum_with_ph6(&ph, offset, len); return 0; } diff --git a/vtysh/vtysh.c b/vtysh/vtysh.c index f1a5eca74b..a0b119c3eb 100644 --- a/vtysh/vtysh.c +++ b/vtysh/vtysh.c @@ -3347,7 +3347,7 @@ static void vtysh_update_all_instances(struct vtysh_client *head_client) dir = opendir(vtydir); if (dir) { while ((file = readdir(dir)) != NULL) { - if (begins_with(file->d_name, "ospfd-") + if (frrstr_startswith(file->d_name, "ospfd-") && ends_with(file->d_name, ".vty")) { if (n == MAXIMUM_INSTANCES) { fprintf(stderr, diff --git a/zebra/main.c b/zebra/main.c index cff5e06933..5797a5846a 100644 --- a/zebra/main.c +++ b/zebra/main.c @@ -74,8 +74,7 @@ int retain_mode = 0; /* Allow non-quagga entities to delete quagga routes */ int allow_delete = 0; -/* Don't delete kernel route. */ -int keep_kernel_mode = 0; +int graceful_restart; bool v6_rr_semantics = false; @@ -95,6 +94,7 @@ struct option longopts[] = { {"label_socket", no_argument, NULL, 'l'}, {"retain", no_argument, NULL, 'r'}, {"vrfdefaultname", required_argument, NULL, 'o'}, + {"graceful_restart", required_argument, NULL, 'K'}, #ifdef HAVE_NETLINK {"vrfwnetns", no_argument, NULL, 'n'}, {"nl-bufsize", required_argument, NULL, 's'}, @@ -262,13 +262,14 @@ int main(int argc, char **argv) char *netlink_fuzzing = NULL; #endif /* HANDLE_NETLINK_FUZZING */ + graceful_restart = 0; vrf_configure_backend(VRF_BACKEND_VRF_LITE); logicalrouter_configure_backend(LOGICALROUTER_BACKEND_NETNS); frr_preinit(&zebra_di, argc, argv); frr_opt_add( - "bakz:e:l:o:r" + "baz:e:l:o:rK:" #ifdef HAVE_NETLINK "s:n" #endif @@ -280,24 +281,24 @@ int main(int argc, char **argv) #endif /* HANDLE_NETLINK_FUZZING */ , longopts, - " -b, --batch Runs in batch mode\n" - " -a, --allow_delete Allow other processes to delete zebra routes\n" - " -z, --socket Set path of zebra socket\n" - " -e, --ecmp Specify ECMP to use.\n" - " -l, --label_socket Socket to external label manager\n" - " -k, --keep_kernel Don't delete old routes which were installed by zebra.\n" - " -r, --retain When program terminates, retain added route by zebra.\n" - " -o, --vrfdefaultname Set default VRF name.\n" + " -b, --batch Runs in batch mode\n" + " -a, --allow_delete Allow other processes to delete zebra routes\n" + " -z, --socket Set path of zebra socket\n" + " -e, --ecmp Specify ECMP to use.\n" + " -l, --label_socket Socket to external label manager\n" + " -r, --retain When program terminates, retain added route by zebra.\n" + " -o, --vrfdefaultname Set default VRF name.\n" + " -K, --graceful_restart Graceful restart at the kernel level, timer in seconds for expiration\n" #ifdef HAVE_NETLINK - " -n, --vrfwnetns Use NetNS as VRF backend\n" - " -s, --nl-bufsize Set netlink receive buffer size\n" - " --v6-rr-semantics Use v6 RR semantics\n" + " -n, --vrfwnetns Use NetNS as VRF backend\n" + " -s, --nl-bufsize Set netlink receive buffer size\n" + " --v6-rr-semantics Use v6 RR semantics\n" #endif /* HAVE_NETLINK */ #if defined(HANDLE_ZAPI_FUZZING) - " -c <file> Bypass normal startup and use this file for testing of zapi\n" + " -c <file> Bypass normal startup and use this file for testing of zapi\n" #endif /* HANDLE_ZAPI_FUZZING */ #if defined(HANDLE_NETLINK_FUZZING) - " -w <file> Bypass normal startup and use this file for testing of netlink input\n" + " -w <file> Bypass normal startup and use this file for testing of netlink input\n" #endif /* HANDLE_NETLINK_FUZZING */ ); @@ -316,9 +317,6 @@ int main(int argc, char **argv) case 'a': allow_delete = 1; break; - case 'k': - keep_kernel_mode = 1; - break; case 'e': zrouter.multipath_num = atoi(optarg); if (zrouter.multipath_num > MULTIPATH_NUM @@ -348,6 +346,9 @@ int main(int argc, char **argv) case 'r': retain_mode = 1; break; + case 'K': + graceful_restart = atoi(optarg); + break; #ifdef HAVE_NETLINK case 's': nl_rcvbufsize = atoi(optarg); @@ -435,8 +436,9 @@ int main(int argc, char **argv) * will be equal to the current getpid(). To know about such routes, * we have to have route_read() called before. */ - if (!keep_kernel_mode) - rib_sweep_route(); + zrouter.startup_time = monotime(NULL); + thread_add_timer(zrouter.master, rib_sweep_route, + NULL, graceful_restart, NULL); /* Needed for BSD routing socket. */ pid = getpid(); diff --git a/zebra/rib.h b/zebra/rib.h index c39abaffcc..0353c9bb99 100644 --- a/zebra/rib.h +++ b/zebra/rib.h @@ -99,9 +99,6 @@ struct route_entry { /* Type fo this route. */ int type; - /* Source protocol instance */ - unsigned short instance; - /* VRF identifier. */ vrf_id_t vrf_id; @@ -115,9 +112,6 @@ struct route_entry { uint32_t mtu; uint32_t nexthop_mtu; - /* Distance. */ - uint8_t distance; - /* Flags of this route. * This flag's definition is in lib/zebra.h ZEBRA_FLAG_* and is exposed * to clients via Zserv @@ -146,6 +140,12 @@ struct route_entry { /* Sequence value incremented for each dataplane operation */ uint32_t dplane_sequence; + + /* Source protocol instance */ + uint16_t instance; + + /* Distance. */ + uint8_t distance; }; #define RIB_SYSTEM_ROUTE(R) RSYSTEM_ROUTE((R)->type) @@ -400,7 +400,7 @@ extern struct route_entry *rib_lookup_ipv4(struct prefix_ipv4 *p, extern void rib_update(vrf_id_t vrf_id, rib_update_event_t event); extern void rib_update_table(struct route_table *table, rib_update_event_t event); -extern void rib_sweep_route(void); +extern int rib_sweep_route(struct thread *t); extern void rib_sweep_table(struct route_table *table); extern void rib_close_table(struct route_table *table); extern void rib_init(void); diff --git a/zebra/zebra_fpm_netlink.c b/zebra/zebra_fpm_netlink.c index 065bdee208..2ac79b100c 100644 --- a/zebra/zebra_fpm_netlink.c +++ b/zebra/zebra_fpm_netlink.c @@ -41,6 +41,7 @@ #include "nexthop.h" #include "zebra/zebra_fpm_private.h" +#include "zebra/zebra_vxlan_private.h" /* * addr_to_a @@ -102,6 +103,51 @@ static size_t af_addr_size(uint8_t af) } /* + * We plan to use RTA_ENCAP_TYPE attribute for VxLAN encap as well. + * Currently, values 0 to 8 for this attribute are used by lwtunnel_encap_types + * So, we cannot use these values for VxLAN encap. + */ +enum fpm_nh_encap_type_t { + FPM_NH_ENCAP_NONE = 0, + FPM_NH_ENCAP_VXLAN = 100, + FPM_NH_ENCAP_MAX, +}; + +/* + * fpm_nh_encap_type_to_str + */ +static const char *fpm_nh_encap_type_to_str(enum fpm_nh_encap_type_t encap_type) +{ + switch (encap_type) { + case FPM_NH_ENCAP_NONE: + return "none"; + + case FPM_NH_ENCAP_VXLAN: + return "VxLAN"; + + case FPM_NH_ENCAP_MAX: + return "invalid"; + } + + return "invalid"; +} + +struct vxlan_encap_info_t { + vni_t vni; +}; + +enum vxlan_encap_info_type_t { + VXLAN_VNI = 0, +}; + +struct fpm_nh_encap_info_t { + enum fpm_nh_encap_type_t encap_type; + union { + struct vxlan_encap_info_t vxlan_encap; + }; +}; + +/* * netlink_nh_info_t * * Holds information about a single nexthop for netlink. These info @@ -118,6 +164,7 @@ typedef struct netlink_nh_info_t_ { */ int recursive; enum nexthop_types_t type; + struct fpm_nh_encap_info_t encap_info; } netlink_nh_info_t; /* @@ -151,10 +198,12 @@ typedef struct netlink_route_info_t_ { * Returns TRUE if a nexthop was added, FALSE otherwise. */ static int netlink_route_info_add_nh(netlink_route_info_t *ri, - struct nexthop *nexthop) + struct nexthop *nexthop, + struct route_entry *re) { netlink_nh_info_t nhi; union g_addr *src; + zebra_l3vni_t *zl3vni = NULL; memset(&nhi, 0, sizeof(nhi)); src = NULL; @@ -186,6 +235,17 @@ static int netlink_route_info_add_nh(netlink_route_info_t *ri, if (!nhi.gateway && nhi.if_index == 0) return 0; + if (re && CHECK_FLAG(re->flags, ZEBRA_FLAG_EVPN_ROUTE)) { + nhi.encap_info.encap_type = FPM_NH_ENCAP_VXLAN; + + zl3vni = zl3vni_from_vrf(ri->rtm_table); + if (zl3vni && is_l3vni_oper_up(zl3vni)) { + + /* Add VNI to VxLAN encap info */ + nhi.encap_info.vxlan_encap.vni = zl3vni->vni; + } + } + /* * We have a valid nhi. Copy the structure over to the route_info. */ @@ -224,6 +284,7 @@ static int netlink_route_info_fill(netlink_route_info_t *ri, int cmd, rib_dest_t *dest, struct route_entry *re) { struct nexthop *nexthop; + struct zebra_vrf *zvrf; memset(ri, 0, sizeof(*ri)); @@ -231,7 +292,9 @@ static int netlink_route_info_fill(netlink_route_info_t *ri, int cmd, ri->af = rib_dest_af(dest); ri->nlmsg_type = cmd; - ri->rtm_table = zvrf_id(rib_dest_vrf(dest)); + zvrf = rib_dest_vrf(dest); + if (zvrf) + ri->rtm_table = zvrf->table_id; ri->rtm_protocol = RTPROT_UNSPEC; /* @@ -277,7 +340,7 @@ static int netlink_route_info_fill(netlink_route_info_t *ri, int cmd, && CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE)) || (cmd == RTM_DELROUTE && CHECK_FLAG(re->status, ROUTE_ENTRY_INSTALLED))) { - netlink_route_info_add_nh(ri, nexthop); + netlink_route_info_add_nh(ri, nexthop, re); } } @@ -303,6 +366,10 @@ static int netlink_route_info_encode(netlink_route_info_t *ri, char *in_buf, unsigned int nexthop_num = 0; size_t buf_offset; netlink_nh_info_t *nhi; + enum fpm_nh_encap_type_t encap; + struct rtattr *nest; + struct vxlan_encap_info_t *vxlan; + int nest_len; struct { struct nlmsghdr n; @@ -327,7 +394,21 @@ static int netlink_route_info_encode(netlink_route_info_t *ri, char *in_buf, req->n.nlmsg_flags = NLM_F_CREATE | NLM_F_REQUEST; req->n.nlmsg_type = ri->nlmsg_type; req->r.rtm_family = ri->af; - req->r.rtm_table = ri->rtm_table; + + /* + * rtm_table field is a uchar field which can accomodate table_id less + * than 256. + * To support table id greater than 255, if the table_id is greater than + * 255, set rtm_table to RT_TABLE_UNSPEC and add RTA_TABLE attribute + * with 32 bit value as the table_id. + */ + if (ri->rtm_table < 256) + req->r.rtm_table = ri->rtm_table; + else { + req->r.rtm_table = RT_TABLE_UNSPEC; + addattr32(&req->n, in_buf_len, RTA_TABLE, ri->rtm_table); + } + req->r.rtm_dst_len = ri->prefix->prefixlen; req->r.rtm_protocol = ri->rtm_protocol; req->r.rtm_scope = RT_SCOPE_UNIVERSE; @@ -355,6 +436,26 @@ static int netlink_route_info_encode(netlink_route_info_t *ri, char *in_buf, addattr32(&req->n, in_buf_len, RTA_OIF, nhi->if_index); } + encap = nhi->encap_info.encap_type; + if (encap > FPM_NH_ENCAP_NONE) { + addattr_l(&req->n, in_buf_len, RTA_ENCAP_TYPE, &encap, + sizeof(uint16_t)); + switch (encap) { + case FPM_NH_ENCAP_NONE: + break; + case FPM_NH_ENCAP_VXLAN: + vxlan = &nhi->encap_info.vxlan_encap; + nest = addattr_nest(&req->n, in_buf_len, + RTA_ENCAP); + addattr32(&req->n, in_buf_len, VXLAN_VNI, + vxlan->vni); + addattr_nest_end(&req->n, nest); + break; + case FPM_NH_ENCAP_MAX: + break; + } + } + goto done; } @@ -388,6 +489,28 @@ static int netlink_route_info_encode(netlink_route_info_t *ri, char *in_buf, rtnh->rtnh_ifindex = nhi->if_index; } + encap = nhi->encap_info.encap_type; + if (encap > FPM_NH_ENCAP_NONE) { + rta_addattr_l(rta, sizeof(buf), RTA_ENCAP_TYPE, + &encap, sizeof(uint16_t)); + rtnh->rtnh_len += sizeof(struct rtattr) + + sizeof(uint16_t); + switch (encap) { + case FPM_NH_ENCAP_NONE: + break; + case FPM_NH_ENCAP_VXLAN: + vxlan = &nhi->encap_info.vxlan_encap; + nest = rta_nest(rta, sizeof(buf), RTA_ENCAP); + rta_addattr_l(rta, sizeof(buf), VXLAN_VNI, + &vxlan->vni, sizeof(uint32_t)); + nest_len = rta_nest_end(rta, nest); + rtnh->rtnh_len += nest_len; + break; + case FPM_NH_ENCAP_MAX: + break; + } + } + rtnh = RTNH_NEXT(rtnh); } @@ -424,10 +547,12 @@ static void zfpm_log_route_info(netlink_route_info_t *ri, const char *label) for (i = 0; i < ri->num_nhs; i++) { nhi = &ri->nhs[i]; - zfpm_debug(" Intf: %u, Gateway: %s, Recursive: %s, Type: %s", + zfpm_debug(" Intf: %u, Gateway: %s, Recursive: %s, Type: %s, Encap type: %s", nhi->if_index, addr_to_a(ri->af, nhi->gateway), nhi->recursive ? "yes" : "no", - nexthop_type_to_str(nhi->type)); + nexthop_type_to_str(nhi->type), + fpm_nh_encap_type_to_str(nhi->encap_info.encap_type) + ); } } diff --git a/zebra/zebra_rib.c b/zebra/zebra_rib.c index 3b305f6e3d..391917ec68 100644 --- a/zebra/zebra_rib.c +++ b/zebra/zebra_rib.c @@ -1229,7 +1229,7 @@ void zebra_rib_evaluate_rn_nexthops(struct route_node *rn, uint32_t seq) * nht resolution and as such we need to call the * nexthop tracking evaluation code */ - for_each (rnh_list, &dest->nht, rnh) { + frr_each (rnh_list, &dest->nht, rnh) { struct zebra_vrf *zvrf = zebra_vrf_lookup_by_id(rnh->vrf_id); struct prefix *p = &rnh->node->p; @@ -3127,6 +3127,7 @@ void rib_sweep_table(struct route_table *table) for (rn = route_top(table); rn; rn = srcdest_route_next(rn)) { RNODE_FOREACH_RE_SAFE (rn, re, next) { + if (IS_ZEBRA_DEBUG_RIB) route_entry_dump(&rn->p, NULL, re); @@ -3137,6 +3138,14 @@ void rib_sweep_table(struct route_table *table) continue; /* + * If routes are older than startup_time then + * we know we read them in from the kernel. + * As such we can safely remove them. + */ + if (zrouter.startup_time < re->uptime) + continue; + + /* * So we are starting up and have received * routes from the kernel that we have installed * from a previous run of zebra but not cleaned @@ -3165,7 +3174,7 @@ void rib_sweep_table(struct route_table *table) } /* Sweep all RIB tables. */ -void rib_sweep_route(void) +int rib_sweep_route(struct thread *t) { struct vrf *vrf; struct zebra_vrf *zvrf; @@ -3179,6 +3188,8 @@ void rib_sweep_route(void) } zebra_router_sweep_route(); + + return 0; } /* Remove specific by protocol routes from 'table'. */ @@ -3223,7 +3234,7 @@ unsigned long rib_score_proto(uint8_t proto, unsigned short instance) proto, instance, zvrf->table[AFI_IP6][SAFI_UNICAST]); - for_each(otable, &zvrf->other_tables, ort) cnt += + frr_each(otable, &zvrf->other_tables, ort) cnt += rib_score_proto_table(proto, instance, ort->table); } diff --git a/zebra/zebra_router.h b/zebra/zebra_router.h index b3def297ac..6c9f3a0f28 100644 --- a/zebra/zebra_router.h +++ b/zebra/zebra_router.h @@ -112,8 +112,15 @@ struct zebra_router { struct zebra_vrf *evpn_vrf; uint32_t multipath_num; + + /* + * Time for when we sweep the rib from old routes + */ + time_t startup_time; }; +#define GRACEFUL_RESTART_TIME 60 + extern struct zebra_router zrouter; extern void zebra_router_init(void); diff --git a/zebra/zebra_vxlan.c b/zebra/zebra_vxlan.c index feb0aadfa8..f2f8a2a059 100644 --- a/zebra/zebra_vxlan.c +++ b/zebra/zebra_vxlan.c @@ -143,7 +143,6 @@ static zebra_l3vni_t *zl3vni_lookup(vni_t vni); static void *zl3vni_alloc(void *p); static zebra_l3vni_t *zl3vni_add(vni_t vni, vrf_id_t vrf_id); static int zl3vni_del(zebra_l3vni_t *zl3vni); -static zebra_l3vni_t *zl3vni_from_vrf(vrf_id_t); static struct interface *zl3vni_map_to_svi_if(zebra_l3vni_t *zl3vni); static struct interface *zl3vni_map_to_vxlan_if(zebra_l3vni_t *zl3vni); static void zebra_vxlan_process_l3vni_oper_up(zebra_l3vni_t *zl3vni); @@ -4842,7 +4841,7 @@ static struct interface *zl3vni_map_to_svi_if(zebra_l3vni_t *zl3vni) return zvni_map_to_svi(vxl->access_vlan, zif->brslave_info.br_if); } -static zebra_l3vni_t *zl3vni_from_vrf(vrf_id_t vrf_id) +zebra_l3vni_t *zl3vni_from_vrf(vrf_id_t vrf_id) { struct zebra_vrf *zvrf = NULL; diff --git a/zebra/zebra_vxlan_private.h b/zebra/zebra_vxlan_private.h index 9f945442bb..1dd42b7083 100644 --- a/zebra/zebra_vxlan_private.h +++ b/zebra/zebra_vxlan_private.h @@ -430,6 +430,8 @@ struct nh_walk_ctx { struct json_object *json; }; +extern zebra_l3vni_t *zl3vni_from_vrf(vrf_id_t vrf_id); + #ifdef __cplusplus } #endif |