diff options
| -rw-r--r-- | doc/developer/lists.rst | 10 | ||||
| -rw-r--r-- | lib/linklist.c | 17 | ||||
| -rw-r--r-- | lib/linklist.h | 13 | ||||
| -rw-r--r-- | lib/typerb.h | 1 | ||||
| -rw-r--r-- | lib/typesafe.h | 71 | ||||
| -rw-r--r-- | pimd/pim_bsm.c | 173 | ||||
| -rw-r--r-- | pimd/pim_bsm.h | 43 | ||||
| -rw-r--r-- | pimd/pim_cmd.c | 119 | ||||
| -rw-r--r-- | pimd/pim_rp.c | 2 | ||||
| -rw-r--r-- | tests/lib/test_typelist.h | 126 | ||||
| -rw-r--r-- | tests/topotests/Dockerfile | 1 |
11 files changed, 365 insertions, 211 deletions
diff --git a/doc/developer/lists.rst b/doc/developer/lists.rst index 86db788c0e..553bd1f596 100644 --- a/doc/developer/lists.rst +++ b/doc/developer/lists.rst @@ -108,6 +108,8 @@ Functions provided: | _first, _next, _next_safe, | yes | yes | yes | yes | yes | | _const_first, _const_next | | | | | | +------------------------------------+------+------+------+---------+------------+ +| _swap_all | yes | yes | yes | yes | yes | ++------------------------------------+------+------+------+---------+------------+ | _add_head, _add_tail, _add_after | yes | -- | -- | -- | -- | +------------------------------------+------+------+------+---------+------------+ | _add | -- | yes | yes | yes | yes | @@ -322,6 +324,14 @@ The following documentation assumes that a list has been defined using return ``item``. The function may also call ``assert()`` (but most don't.) +.. c:function:: itemtype *Z_swap_all(struct Z_head *, struct Z_head *) + + Swap the contents of 2 containers (of identical type). This exchanges the + contents of the two head structures and updates pointers if necessary for + the particular data structure. Fast for all structures. + + (Not currently available on atomic containers.) + .. todo:: ``Z_del_after()`` / ``Z_del_hint()``? diff --git a/lib/linklist.c b/lib/linklist.c index 5de6c8a817..8137b68d84 100644 --- a/lib/linklist.c +++ b/lib/linklist.c @@ -320,23 +320,6 @@ void list_delete_all_node(struct list *list) list->count = 0; } -void list_filter_out_nodes(struct list *list, bool (*cond)(void *data)) -{ - struct listnode *node; - struct listnode *next; - void *data; - - assert(list); - - for (ALL_LIST_ELEMENTS(list, node, next, data)) { - if ((cond && cond(data)) || (!cond)) { - if (*list->del) - (*list->del)(data); - list_delete_node(list, node); - } - } -} - void list_delete(struct list **list) { assert(*list); diff --git a/lib/linklist.h b/lib/linklist.h index d8820c924d..1452145218 100644 --- a/lib/linklist.h +++ b/lib/linklist.h @@ -295,19 +295,6 @@ extern void list_delete_all_node(struct list *list); extern void list_delete_node(struct list *list, struct listnode *node); /* - * Delete all nodes which satisfy a condition from a list. - * Deletes the node if cond function returns true for the node. - * If function ptr passed is NULL, it deletes all nodes - * - * list - * list to operate on - * cond - * function pointer which takes node data as input and return true or false - */ - -extern void list_filter_out_nodes(struct list *list, bool (*cond)(void *data)); - -/* * Insert a new element into a list with insertion sort if there is no * duplicate element present in the list. This assumes the input list is * sorted. If unsorted, it will check for duplicate until it finds out diff --git a/lib/typerb.h b/lib/typerb.h index 60e6d09016..cbed8d4893 100644 --- a/lib/typerb.h +++ b/lib/typerb.h @@ -117,6 +117,7 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ typed_rb_remove(&h->rr, re); \ return container_of(re, type, field.re); \ } \ +TYPESAFE_SWAP_ALL_SIMPLE(prefix) \ macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ const struct typed_rb_entry *re; \ diff --git a/lib/typesafe.h b/lib/typesafe.h index 27e7be1286..ecac1a4381 100644 --- a/lib/typesafe.h +++ b/lib/typesafe.h @@ -78,6 +78,19 @@ macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \ } \ /* ... */ +/* SWAP_ALL_SIMPLE = for containers where the items don't point back to the + * head *AND* the head doesn'T points to itself (= everything except LIST, + * DLIST and SKIPLIST), just switch out the entire head + */ +#define TYPESAFE_SWAP_ALL_SIMPLE(prefix) \ +macro_inline void prefix ## _swap_all(struct prefix##_head *a, \ + struct prefix##_head *b) \ +{ \ + struct prefix##_head tmp = *a; \ + *a = *b; \ + *b = tmp; \ +} \ +/* ... */ /* single-linked list, unsorted/arbitrary. * can be used as queue with add_tail / pop @@ -169,6 +182,17 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ h->sh.last_next = &h->sh.first; \ return container_of(sitem, type, field.si); \ } \ +macro_inline void prefix ## _swap_all(struct prefix##_head *a, \ + struct prefix##_head *b) \ +{ \ + struct prefix##_head tmp = *a; \ + *a = *b; \ + *b = tmp; \ + if (a->sh.last_next == &b->sh.first) \ + a->sh.last_next = &a->sh.first; \ + if (b->sh.last_next == &a->sh.first) \ + b->sh.last_next = &b->sh.first; \ +} \ macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ return container_of_null(h->sh.first, type, field.si); \ @@ -215,6 +239,34 @@ static inline void typesafe_dlist_add(struct dlist_head *head, head->count++; } +static inline void typesafe_dlist_swap_all(struct dlist_head *a, + struct dlist_head *b) +{ + struct dlist_head tmp = *a; + + a->count = b->count; + if (a->count) { + a->hitem.next = b->hitem.next; + a->hitem.prev = b->hitem.prev; + a->hitem.next->prev = &a->hitem; + a->hitem.prev->next = &a->hitem; + } else { + a->hitem.next = &a->hitem; + a->hitem.prev = &a->hitem; + } + + b->count = tmp.count; + if (b->count) { + b->hitem.next = tmp.hitem.next; + b->hitem.prev = tmp.hitem.prev; + b->hitem.next->prev = &b->hitem; + b->hitem.prev->next = &b->hitem; + } else { + b->hitem.next = &b->hitem; + b->hitem.prev = &b->hitem; + } +} + /* double-linked list, for fast item deletion */ #define PREDECL_DLIST(prefix) \ @@ -271,6 +323,11 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ h->dh.count--; \ return container_of(ditem, type, field.di); \ } \ +macro_inline void prefix ## _swap_all(struct prefix##_head *a, \ + struct prefix##_head *b) \ +{ \ + typesafe_dlist_swap_all(&a->dh, &b->dh); \ +} \ macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ const struct dlist_item *ditem = h->dh.hitem.next; \ @@ -380,6 +437,7 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ typesafe_heap_resize(&h->hh, false); \ return container_of(hitem, type, field.hi); \ } \ +TYPESAFE_SWAP_ALL_SIMPLE(prefix) \ macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ if (h->hh.count == 0) \ @@ -518,6 +576,7 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ h->sh.first = sitem->next; \ return container_of(sitem, type, field.si); \ } \ +TYPESAFE_SWAP_ALL_SIMPLE(prefix) \ macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ return container_of_null(h->sh.first, type, field.si); \ @@ -708,6 +767,7 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ } \ return NULL; \ } \ +TYPESAFE_SWAP_ALL_SIMPLE(prefix) \ macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ uint32_t i; \ @@ -824,6 +884,17 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ struct sskip_item *sitem = typesafe_skiplist_pop(&h->sh); \ return container_of_null(sitem, type, field.si); \ } \ +macro_inline void prefix ## _swap_all(struct prefix##_head *a, \ + struct prefix##_head *b) \ +{ \ + struct prefix##_head tmp = *a; \ + *a = *b; \ + *b = tmp; \ + a->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *) \ + ((uintptr_t)a->sh.overflow | 1); \ + b->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *) \ + ((uintptr_t)b->sh.overflow | 1); \ +} \ macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ const struct sskip_item *first = h->sh.hitem.next[0]; \ diff --git a/pimd/pim_bsm.c b/pimd/pim_bsm.c index f43a31fde2..3fbe3317ba 100644 --- a/pimd/pim_bsm.c +++ b/pimd/pim_bsm.c @@ -43,8 +43,8 @@ static inline void pim_g2rp_timer_restart(struct bsm_rpinfo *bsrp, /* Memory Types */ DEFINE_MTYPE_STATIC(PIMD, PIM_BSGRP_NODE, "PIM BSR advertised grp info"); -DEFINE_MTYPE_STATIC(PIMD, PIM_BSRP_NODE, "PIM BSR advertised RP info"); -DEFINE_MTYPE_STATIC(PIMD, PIM_BSM_INFO, "PIM BSM Info"); +DEFINE_MTYPE_STATIC(PIMD, PIM_BSRP_INFO, "PIM BSR advertised RP info"); +DEFINE_MTYPE_STATIC(PIMD, PIM_BSM_FRAG, "PIM BSM fragment"); DEFINE_MTYPE_STATIC(PIMD, PIM_BSM_PKT_VAR_MEM, "PIM BSM Packet"); /* All bsm packets forwarded shall be fit within ip mtu less iphdr(max) */ @@ -63,12 +63,24 @@ void pim_bsm_write_config(struct vty *vty, struct interface *ifp) } } +static void pim_bsm_rpinfo_free(struct bsm_rpinfo *bsrp_info) +{ + THREAD_OFF(bsrp_info->g2rp_timer); + XFREE(MTYPE_PIM_BSRP_INFO, bsrp_info); +} + +void pim_bsm_rpinfos_free(struct bsm_rpinfos_head *head) +{ + struct bsm_rpinfo *bsrp_info; + + while ((bsrp_info = bsm_rpinfos_pop(head))) + pim_bsm_rpinfo_free(bsrp_info); +} + void pim_free_bsgrp_data(struct bsgrp_node *bsgrp_node) { - if (bsgrp_node->bsrp_list) - list_delete(&bsgrp_node->bsrp_list); - if (bsgrp_node->partial_bsrp_list) - list_delete(&bsgrp_node->partial_bsrp_list); + pim_bsm_rpinfos_free(bsgrp_node->bsrp_list); + pim_bsm_rpinfos_free(bsgrp_node->partial_bsrp_list); XFREE(MTYPE_PIM_BSGRP_NODE, bsgrp_node); } @@ -84,14 +96,21 @@ void pim_free_bsgrp_node(struct route_table *rt, struct prefix *grp) } } -static void pim_bsm_node_free(struct bsm_info *bsm) +static void pim_bsm_frag_free(struct bsm_frag *bsfrag) { - XFREE(MTYPE_PIM_BSM_PKT_VAR_MEM, bsm->bsm); - XFREE(MTYPE_PIM_BSM_INFO, bsm); + XFREE(MTYPE_PIM_BSM_FRAG, bsfrag); } -static int pim_g2rp_list_compare(struct bsm_rpinfo *node1, - struct bsm_rpinfo *node2) +void pim_bsm_frags_free(struct bsm_scope *scope) +{ + struct bsm_frag *bsfrag; + + while ((bsfrag = bsm_frags_pop(scope->bsm_frags))) + pim_bsm_frag_free(bsfrag); +} + +int pim_bsm_rpinfo_cmp(const struct bsm_rpinfo *node1, + const struct bsm_rpinfo *node2) { /* RP election Algo : * Step-1 : Loweset Rp priority will have higher precedance. @@ -115,27 +134,6 @@ static int pim_g2rp_list_compare(struct bsm_rpinfo *node1, return 0; } -static void pim_free_bsrp_node(struct bsm_rpinfo *bsrp_info) -{ - THREAD_OFF(bsrp_info->g2rp_timer); - XFREE(MTYPE_PIM_BSRP_NODE, bsrp_info); -} - -static struct list *pim_alloc_bsrp_list(void) -{ - struct list *new_list = NULL; - - new_list = list_new(); - - if (!new_list) - return NULL; - - new_list->cmp = (int (*)(void *, void *))pim_g2rp_list_compare; - new_list->del = (void (*)(void *))pim_free_bsrp_node; - - return new_list; -} - static struct bsgrp_node *pim_bsm_new_bsgrp_node(struct route_table *rt, struct prefix *grp) { @@ -150,14 +148,8 @@ static struct bsgrp_node *pim_bsm_new_bsgrp_node(struct route_table *rt, bsgrp = XCALLOC(MTYPE_PIM_BSGRP_NODE, sizeof(struct bsgrp_node)); rn->info = bsgrp; - bsgrp->bsrp_list = pim_alloc_bsrp_list(); - bsgrp->partial_bsrp_list = pim_alloc_bsrp_list(); - - if ((!bsgrp->bsrp_list) || (!bsgrp->partial_bsrp_list)) { - route_unlock_node(rn); - pim_free_bsgrp_data(bsgrp); - return NULL; - } + bsm_rpinfos_init(bsgrp->bsrp_list); + bsm_rpinfos_init(bsgrp->partial_bsrp_list); prefix_copy(&bsgrp->group, grp); return bsgrp; @@ -197,7 +189,7 @@ static int pim_on_bs_timer(struct thread *t) scope->current_bsr_first_ts = 0; scope->current_bsr_last_ts = 0; scope->bsm_frag_tag = 0; - list_delete_all_node(scope->bsm_list); + pim_bsm_frags_free(scope); for (rn = route_top(scope->bsrp_table); rn; rn = route_next(rn)) { @@ -208,16 +200,13 @@ static int pim_on_bs_timer(struct thread *t) continue; } /* Give grace time for rp to continue for another hold time */ - if ((bsgrp_node->bsrp_list) && (bsgrp_node->bsrp_list->count)) { - bsrp = listnode_head(bsgrp_node->bsrp_list); + bsrp = bsm_rpinfos_first(bsgrp_node->bsrp_list); + if (bsrp) pim_g2rp_timer_restart(bsrp, bsrp->rp_holdtime); - } + /* clear pending list */ - if ((bsgrp_node->partial_bsrp_list) - && (bsgrp_node->partial_bsrp_list->count)) { - list_delete_all_node(bsgrp_node->partial_bsrp_list); - bsgrp_node->pend_rp_cnt = 0; - } + pim_bsm_rpinfos_free(bsgrp_node->partial_bsrp_list); + bsgrp_node->pend_rp_cnt = 0; } return 0; } @@ -260,8 +249,7 @@ void pim_bsm_proc_init(struct pim_instance *pim) pim->global_scope.accept_nofwd_bsm = true; pim->global_scope.state = NO_INFO; pim->global_scope.pim = pim; - pim->global_scope.bsm_list = list_new(); - pim->global_scope.bsm_list->del = (void (*)(void *))pim_bsm_node_free; + bsm_frags_init(pim->global_scope.bsm_frags); pim_bs_timer_start(&pim->global_scope, PIM_BS_TIME); } @@ -271,9 +259,7 @@ void pim_bsm_proc_free(struct pim_instance *pim) struct bsgrp_node *bsgrp; pim_bs_timer_stop(&pim->global_scope); - - if (pim->global_scope.bsm_list) - list_delete(&pim->global_scope.bsm_list); + pim_bsm_frags_free(&pim->global_scope); for (rn = route_top(pim->global_scope.bsrp_table); rn; rn = route_next(rn)) { @@ -303,7 +289,6 @@ static int pim_on_g2rp_timer(struct thread *t) struct bsm_rpinfo *bsrp; struct bsm_rpinfo *bsrp_node; struct bsgrp_node *bsgrp_node; - struct listnode *bsrp_ln; struct pim_instance *pim; struct rp_info *rp_info; struct route_node *rn; @@ -319,14 +304,17 @@ static int pim_on_g2rp_timer(struct thread *t) bsrp_addr = bsrp->rp_address; /* update elapse for all bsrp nodes */ - for (ALL_LIST_ELEMENTS_RO(bsgrp_node->bsrp_list, bsrp_ln, bsrp_node)) + frr_each_safe (bsm_rpinfos, bsgrp_node->bsrp_list, bsrp_node) { bsrp_node->elapse_time += elapse; - /* remove the expired nodes from the list */ - list_filter_out_nodes(bsgrp_node->bsrp_list, is_hold_time_elapsed); + if (is_hold_time_elapsed(bsrp_node)) { + bsm_rpinfos_del(bsgrp_node->bsrp_list, bsrp_node); + pim_bsm_rpinfo_free(bsrp_node); + } + } /* Get the next elected rp node */ - bsrp = listnode_head(bsgrp_node->bsrp_list); + bsrp = bsm_rpinfos_first(bsgrp_node->bsrp_list); pim = bsgrp_node->scope->pim; rn = route_node_lookup(pim->rp_table, &bsgrp_node->group); @@ -356,8 +344,8 @@ static int pim_on_g2rp_timer(struct thread *t) } } - if ((!bsgrp_node->bsrp_list->count) - && (!bsgrp_node->partial_bsrp_list->count)) { + if (!bsm_rpinfos_count(bsgrp_node->bsrp_list) + && !bsm_rpinfos_count(bsgrp_node->partial_bsrp_list)) { pim_free_bsgrp_node(pim->global_scope.bsrp_table, &bsgrp_node->group); pim_free_bsgrp_data(bsgrp_node); @@ -420,7 +408,6 @@ static void pim_instate_pend_list(struct bsgrp_node *bsgrp_node) { struct bsm_rpinfo *active; struct bsm_rpinfo *pend; - struct list *temp; struct rp_info *rp_info; struct route_node *rn; struct pim_instance *pim; @@ -429,11 +416,14 @@ static void pim_instate_pend_list(struct bsgrp_node *bsgrp_node) bool had_rp_node = true; pim = bsgrp_node->scope->pim; - active = listnode_head(bsgrp_node->bsrp_list); + active = bsm_rpinfos_first(bsgrp_node->bsrp_list); /* Remove nodes with hold time 0 & check if list still has a head */ - list_filter_out_nodes(bsgrp_node->partial_bsrp_list, is_hold_time_zero); - pend = listnode_head(bsgrp_node->partial_bsrp_list); + frr_each_safe (bsm_rpinfos, bsgrp_node->partial_bsrp_list, pend) + if (is_hold_time_zero(pend)) + bsm_rpinfos_del(bsgrp_node->partial_bsrp_list, pend); + + pend = bsm_rpinfos_first(bsgrp_node->partial_bsrp_list); if (!str2prefix("224.0.0.0/4", &group_all)) return; @@ -541,14 +531,12 @@ static void pim_instate_pend_list(struct bsgrp_node *bsgrp_node) * pend is head of bsrp list * So check appriate head after swap and clean the new partial list */ - temp = bsgrp_node->bsrp_list; - bsgrp_node->bsrp_list = bsgrp_node->partial_bsrp_list; - bsgrp_node->partial_bsrp_list = temp; + bsm_rpinfos_swap_all(bsgrp_node->bsrp_list, + bsgrp_node->partial_bsrp_list); - if (active) { + if (active) pim_g2rp_timer_stop(active); - list_delete_all_node(bsgrp_node->partial_bsrp_list); - } + pim_bsm_rpinfos_free(bsgrp_node->partial_bsrp_list); } static bool pim_bsr_rpf_check(struct pim_instance *pim, struct in_addr bsr, @@ -896,8 +884,7 @@ bool pim_bsm_new_nbr_fwd(struct pim_neighbor *neigh, struct interface *ifp) struct in_addr dst_addr; struct pim_interface *pim_ifp; struct bsm_scope *scope; - struct listnode *bsm_ln; - struct bsm_info *bsminfo; + struct bsm_frag *bsfrag; char neigh_src_str[INET_ADDRSTRLEN]; uint32_t pim_mtu; bool no_fwd = true; @@ -929,7 +916,7 @@ bool pim_bsm_new_nbr_fwd(struct pim_neighbor *neigh, struct interface *ifp) scope = &pim_ifp->pim->global_scope; - if (!scope->bsm_list->count) { + if (!bsm_frags_count(scope->bsm_frags)) { if (PIM_DEBUG_BSM) zlog_debug("%s: BSM list for the scope is empty", __func__); @@ -950,10 +937,10 @@ bool pim_bsm_new_nbr_fwd(struct pim_neighbor *neigh, struct interface *ifp) pim_mtu = ifp->mtu - MAX_IP_HDR_LEN; pim_hello_require(ifp); - for (ALL_LIST_ELEMENTS_RO(scope->bsm_list, bsm_ln, bsminfo)) { - if (pim_mtu < bsminfo->size) { - ret = pim_bsm_frag_send(bsminfo->bsm, bsminfo->size, - ifp, pim_mtu, dst_addr, no_fwd); + frr_each (bsm_frags, scope->bsm_frags, bsfrag) { + if (pim_mtu < bsfrag->size) { + ret = pim_bsm_frag_send(bsfrag->data, bsfrag->size, ifp, + pim_mtu, dst_addr, no_fwd); if (!ret) { if (PIM_DEBUG_BSM) zlog_debug( @@ -962,10 +949,10 @@ bool pim_bsm_new_nbr_fwd(struct pim_neighbor *neigh, struct interface *ifp) } } else { /* Pim header needs to be constructed */ - pim_msg_build_header(bsminfo->bsm, bsminfo->size, + pim_msg_build_header(bsfrag->data, bsfrag->size, PIM_MSG_TYPE_BOOTSTRAP, no_fwd); - ret = pim_bsm_send_intf(bsminfo->bsm, bsminfo->size, - ifp, dst_addr); + ret = pim_bsm_send_intf(bsfrag->data, bsfrag->size, ifp, + dst_addr); if (!ret) { if (PIM_DEBUG_BSM) zlog_debug( @@ -1035,7 +1022,7 @@ static bool pim_install_bsm_grp_rp(struct pim_instance *pim, uint8_t hashMask_len = pim->global_scope.hashMasklen; /*memory allocation for bsm_rpinfo */ - bsm_rpinfo = XCALLOC(MTYPE_PIM_BSRP_NODE, sizeof(*bsm_rpinfo)); + bsm_rpinfo = XCALLOC(MTYPE_PIM_BSRP_INFO, sizeof(*bsm_rpinfo)); bsm_rpinfo->rp_prio = rp->rp_pri; bsm_rpinfo->rp_holdtime = rp->rp_holdtime; @@ -1049,7 +1036,7 @@ static bool pim_install_bsm_grp_rp(struct pim_instance *pim, /* update hash for this rp node */ bsm_rpinfo->hash = hash_calc_on_grp_rp(grpnode->group, rp->rpaddr.addr, hashMask_len); - if (listnode_add_sort_nodup(grpnode->partial_bsrp_list, bsm_rpinfo)) { + if (bsm_rpinfos_add(grpnode->partial_bsrp_list, bsm_rpinfo) == NULL) { if (PIM_DEBUG_BSM) zlog_debug( "%s, bs_rpinfo node added to the partial bs_rplist.", @@ -1060,7 +1047,7 @@ static bool pim_install_bsm_grp_rp(struct pim_instance *pim, if (PIM_DEBUG_BSM) zlog_debug("%s: list node not added", __func__); - XFREE(MTYPE_PIM_BSRP_NODE, bsm_rpinfo); + XFREE(MTYPE_PIM_BSRP_INFO, bsm_rpinfo); return false; } @@ -1078,7 +1065,7 @@ static void pim_update_pending_rp_cnt(struct bsm_scope *sz, zlog_debug( "%s,Received a new BSM ,so clear the pending bs_rpinfo list.", __func__); - list_delete_all_node(bsgrp->partial_bsrp_list); + pim_bsm_rpinfos_free(bsgrp->partial_bsrp_list); bsgrp->pend_rp_cnt = total_rp_count; } } else @@ -1227,7 +1214,7 @@ int pim_bsm_process(struct interface *ifp, struct ip *ip_hdr, uint8_t *buf, int sz = PIM_GBL_SZ_ID; struct bsmmsg_grpinfo *msg_grp; struct pim_interface *pim_ifp = NULL; - struct bsm_info *bsminfo; + struct bsm_frag *bsfrag; struct pim_instance *pim; char bsr_str[INET_ADDRSTRLEN]; uint16_t frag_tag; @@ -1383,7 +1370,7 @@ int pim_bsm_process(struct interface *ifp, struct ip *ip_hdr, uint8_t *buf, pim_ifp->pim->global_scope.bsm_frag_tag, frag_tag); } - list_delete_all_node(pim_ifp->pim->global_scope.bsm_list); + pim_bsm_frags_free(&pim_ifp->pim->global_scope); pim_ifp->pim->global_scope.bsm_frag_tag = frag_tag; } @@ -1392,13 +1379,13 @@ int pim_bsm_process(struct interface *ifp, struct ip *ip_hdr, uint8_t *buf, if (!no_fwd) { pim_bsm_fwd_whole_sz(pim_ifp->pim, buf, buf_size, sz); - bsminfo = XCALLOC(MTYPE_PIM_BSM_INFO, sizeof(struct bsm_info)); - - bsminfo->bsm = XCALLOC(MTYPE_PIM_BSM_PKT_VAR_MEM, buf_size); + bsfrag = XCALLOC(MTYPE_PIM_BSM_FRAG, + sizeof(struct bsm_frag) + buf_size); - bsminfo->size = buf_size; - memcpy(bsminfo->bsm, buf, buf_size); - listnode_add(pim_ifp->pim->global_scope.bsm_list, bsminfo); + bsfrag->size = buf_size; + memcpy(bsfrag->data, buf, buf_size); + bsm_frags_add_tail(pim_ifp->pim->global_scope.bsm_frags, + bsfrag); } return 0; diff --git a/pimd/pim_bsm.h b/pimd/pim_bsm.h index 2829c1e05a..dbfeeceec8 100644 --- a/pimd/pim_bsm.h +++ b/pimd/pim_bsm.h @@ -25,7 +25,7 @@ #include "if.h" #include "vty.h" -#include "linklist.h" +#include "typesafe.h" #include "table.h" #include "pim_rp.h" #include "pim_msg.h" @@ -54,6 +54,8 @@ enum ncbsr_state { ACCEPT_PREFERRED }; +PREDECL_DLIST(bsm_frags); + /* BSM scope - bsm processing is per scope */ struct bsm_scope { int sz_id; /* scope zone id */ @@ -66,36 +68,49 @@ struct bsm_scope { uint16_t bsm_frag_tag; /* Last received frag tag from E-BSR */ uint8_t hashMasklen; /* Mask in hash calc RFC 7761 4.7.2 */ struct pim_instance *pim; /* Back pointer to pim instance */ - struct list *bsm_list; /* list of bsm frag for frowarding */ + + /* current set of fragments for forwarding */ + struct bsm_frags_head bsm_frags[1]; + struct route_table *bsrp_table; /* group2rp mapping rcvd from BSR */ struct thread *bs_timer; /* Boot strap timer */ - struct thread *sz_timer; }; -/* BSM packet - this is stored as list in bsm_list inside scope +/* BSM packet (= fragment) - this is stored as list in bsm_frags inside scope * This is used for forwarding to new neighbors or restarting mcast routers */ -struct bsm_info { - uint32_t size; /* size of the packet */ - unsigned char *bsm; /* Actual packet */ +struct bsm_frag { + struct bsm_frags_item item; + + uint32_t size; /* size of the packet */ + uint8_t data[0]; /* Actual packet (dyn size) */ }; +DECLARE_DLIST(bsm_frags, struct bsm_frag, item); + +PREDECL_SORTLIST_UNIQ(bsm_rpinfos); + /* This is the group node of the bsrp table in scope. * this node maintains the list of rp for the group. */ struct bsgrp_node { struct prefix group; /* Group range */ struct bsm_scope *scope; /* Back ptr to scope */ - struct list *bsrp_list; /* list of RPs adv by BSR */ - struct list *partial_bsrp_list; /* maintained until all RPs received */ + + /* RPs advertised by BSR, and temporary list while receiving new set */ + struct bsm_rpinfos_head bsrp_list[1]; + struct bsm_rpinfos_head partial_bsrp_list[1]; + int pend_rp_cnt; /* Total RP - Received RP */ uint16_t frag_tag; /* frag tag to identify the fragment */ }; -/* This is the list node of bsrp_list and partial bsrp list in - * bsgrp_node. Hold info of each RP received for the group +/* Items on [partial_]bsrp_list above. + * Holds info of each candidate RP received for the bsgrp_node's prefix. */ struct bsm_rpinfo { + struct bsm_rpinfos_item item; + uint32_t hash; /* Hash Value as per RFC 7761 4.7.2 */ uint32_t elapse_time; /* upd at expiry of elected RP node */ uint16_t rp_prio; /* RP priority */ @@ -105,6 +120,10 @@ struct bsm_rpinfo { struct thread *g2rp_timer; /* Run only for elected RP node */ }; +extern int pim_bsm_rpinfo_cmp(const struct bsm_rpinfo *a, + const struct bsm_rpinfo *b); +DECLARE_SORTLIST_UNIQ(bsm_rpinfos, struct bsm_rpinfo, item, pim_bsm_rpinfo_cmp); + /* Structures to extract Bootstrap Message header and Grp to RP Mappings * ===================================================================== * BSM Format: @@ -196,6 +215,8 @@ bool pim_bsm_new_nbr_fwd(struct pim_neighbor *neigh, struct interface *ifp); struct bsgrp_node *pim_bsm_get_bsgrp_node(struct bsm_scope *scope, struct prefix *grp); void pim_bs_timer_stop(struct bsm_scope *scope); +void pim_bsm_frags_free(struct bsm_scope *scope); +void pim_bsm_rpinfos_free(struct bsm_rpinfos_head *head); void pim_free_bsgrp_data(struct bsgrp_node *bsgrp_node); void pim_free_bsgrp_node(struct route_table *rt, struct prefix *grp); #endif diff --git a/pimd/pim_cmd.c b/pimd/pim_cmd.c index c01cfec88e..4b72bcb4c3 100644 --- a/pimd/pim_cmd.c +++ b/pimd/pim_cmd.c @@ -3000,15 +3000,14 @@ static void pim_show_nexthop(struct pim_instance *pim, struct vty *vty) /* Display the bsm database details */ static void pim_show_bsm_db(struct pim_instance *pim, struct vty *vty, bool uj) { - struct listnode *bsmnode; int count = 0; int fragment = 1; - struct bsm_info *bsm; + struct bsm_frag *bsfrag; json_object *json = NULL; json_object *json_group = NULL; json_object *json_row = NULL; - count = pim->global_scope.bsm_list->count; + count = bsm_frags_count(pim->global_scope.bsm_frags); if (uj) { json = json_object_new_object(); @@ -3019,7 +3018,7 @@ static void pim_show_bsm_db(struct pim_instance *pim, struct vty *vty, bool uj) vty_out(vty, "\n"); } - for (ALL_LIST_ELEMENTS_RO(pim->global_scope.bsm_list, bsmnode, bsm)) { + frr_each (bsm_frags, pim->global_scope.bsm_frags, bsfrag) { char grp_str[PREFIX_STRLEN]; char rp_str[INET_ADDRSTRLEN]; char bsr_str[INET_ADDRSTRLEN]; @@ -3032,8 +3031,8 @@ static void pim_show_bsm_db(struct pim_instance *pim, struct vty *vty, bool uj) uint32_t len = 0; uint32_t frag_rp_cnt = 0; - buf = bsm->bsm; - len = bsm->size; + buf = bsfrag->data; + len = bsfrag->size; /* skip pim header */ buf += PIM_MSG_HEADER_LEN; @@ -3160,7 +3159,6 @@ static void pim_show_group_rp_mappings_info(struct pim_instance *pim, struct vty *vty, bool uj) { struct bsgrp_node *bsgrp; - struct listnode *rpnode; struct bsm_rpinfo *bsm_rp; struct route_node *rn; char bsr_str[INET_ADDRSTRLEN]; @@ -3209,42 +3207,33 @@ static void pim_show_group_rp_mappings_info(struct pim_instance *pim, vty_out(vty, "(ACTIVE)\n"); } - if (bsgrp->bsrp_list) { - for (ALL_LIST_ELEMENTS_RO(bsgrp->bsrp_list, rpnode, - bsm_rp)) { - char rp_str[INET_ADDRSTRLEN]; + frr_each (bsm_rpinfos, bsgrp->bsrp_list, bsm_rp) { + char rp_str[INET_ADDRSTRLEN]; - pim_inet4_dump("<Rp Address?>", - bsm_rp->rp_address, rp_str, - sizeof(rp_str)); + pim_inet4_dump("<Rp Address?>", bsm_rp->rp_address, + rp_str, sizeof(rp_str)); - if (uj) { - json_row = json_object_new_object(); - json_object_string_add( - json_row, "Rp Address", rp_str); - json_object_int_add( - json_row, "Rp HoldTime", - bsm_rp->rp_holdtime); - json_object_int_add(json_row, - "Rp Priority", - bsm_rp->rp_prio); - json_object_int_add(json_row, - "Hash Val", - bsm_rp->hash); - json_object_object_add( - json_group, rp_str, json_row); + if (uj) { + json_row = json_object_new_object(); + json_object_string_add(json_row, "Rp Address", + rp_str); + json_object_int_add(json_row, "Rp HoldTime", + bsm_rp->rp_holdtime); + json_object_int_add(json_row, "Rp Priority", + bsm_rp->rp_prio); + json_object_int_add(json_row, "Hash Val", + bsm_rp->hash); + json_object_object_add(json_group, rp_str, + json_row); - } else { - vty_out(vty, - "%-15s %-15u %-15u %-15u\n", - rp_str, bsm_rp->rp_prio, - bsm_rp->rp_holdtime, - bsm_rp->hash); - } + } else { + vty_out(vty, "%-15s %-15u %-15u %-15u\n", + rp_str, bsm_rp->rp_prio, + bsm_rp->rp_holdtime, bsm_rp->hash); } - if (!bsgrp->bsrp_list->count && !uj) - vty_out(vty, "Active List is empty.\n"); } + if (!bsm_rpinfos_count(bsgrp->bsrp_list) && !uj) + vty_out(vty, "Active List is empty.\n"); if (uj) { json_object_int_add(json_group, "Pending RP count", @@ -3259,40 +3248,32 @@ static void pim_show_group_rp_mappings_info(struct pim_instance *pim, "Hash"); } - if (bsgrp->partial_bsrp_list) { - for (ALL_LIST_ELEMENTS_RO(bsgrp->partial_bsrp_list, - rpnode, bsm_rp)) { - char rp_str[INET_ADDRSTRLEN]; + frr_each (bsm_rpinfos, bsgrp->partial_bsrp_list, bsm_rp) { + char rp_str[INET_ADDRSTRLEN]; - pim_inet4_dump("<Rp Addr?>", bsm_rp->rp_address, - rp_str, sizeof(rp_str)); + pim_inet4_dump("<Rp Addr?>", bsm_rp->rp_address, rp_str, + sizeof(rp_str)); - if (uj) { - json_row = json_object_new_object(); - json_object_string_add( - json_row, "Rp Address", rp_str); - json_object_int_add( - json_row, "Rp HoldTime", - bsm_rp->rp_holdtime); - json_object_int_add(json_row, - "Rp Priority", - bsm_rp->rp_prio); - json_object_int_add(json_row, - "Hash Val", - bsm_rp->hash); - json_object_object_add( - json_group, rp_str, json_row); - } else { - vty_out(vty, - "%-15s %-15u %-15u %-15u\n", - rp_str, bsm_rp->rp_prio, - bsm_rp->rp_holdtime, - bsm_rp->hash); - } + if (uj) { + json_row = json_object_new_object(); + json_object_string_add(json_row, "Rp Address", + rp_str); + json_object_int_add(json_row, "Rp HoldTime", + bsm_rp->rp_holdtime); + json_object_int_add(json_row, "Rp Priority", + bsm_rp->rp_prio); + json_object_int_add(json_row, "Hash Val", + bsm_rp->hash); + json_object_object_add(json_group, rp_str, + json_row); + } else { + vty_out(vty, "%-15s %-15u %-15u %-15u\n", + rp_str, bsm_rp->rp_prio, + bsm_rp->rp_holdtime, bsm_rp->hash); } - if (!bsgrp->partial_bsrp_list->count && !uj) - vty_out(vty, "Partial List is empty\n"); } + if (!bsm_rpinfos_count(bsgrp->partial_bsrp_list) && !uj) + vty_out(vty, "Partial List is empty\n"); if (!uj) vty_out(vty, "\n"); @@ -4083,7 +4064,7 @@ static void clear_pim_bsr_db(struct pim_instance *pim) pim->global_scope.current_bsr_first_ts = 0; pim->global_scope.current_bsr_last_ts = 0; pim->global_scope.bsm_frag_tag = 0; - list_delete_all_node(pim->global_scope.bsm_list); + pim_bsm_frags_free(&pim->global_scope); pim_bs_timer_stop(&pim->global_scope); diff --git a/pimd/pim_rp.c b/pimd/pim_rp.c index dbba6b66d8..feaeea929d 100644 --- a/pimd/pim_rp.c +++ b/pimd/pim_rp.c @@ -702,7 +702,7 @@ int pim_rp_del(struct pim_instance *pim, struct in_addr rp_addr, bsgrp = pim_bsm_get_bsgrp_node(&pim->global_scope, &group); if (bsgrp) { - bsrp = listnode_head(bsgrp->bsrp_list); + bsrp = bsm_rpinfos_first(bsgrp->bsrp_list); if (bsrp) { if (PIM_DEBUG_PIM_TRACE) { char bsrp_str[INET_ADDRSTRLEN]; diff --git a/tests/lib/test_typelist.h b/tests/lib/test_typelist.h index 32331c14a0..379a2396b4 100644 --- a/tests/lib/test_typelist.h +++ b/tests/lib/test_typelist.h @@ -17,6 +17,7 @@ /* C++ called, they want their templates back */ #define item concat(item_, TYPE) #define itm concat(itm_, TYPE) +#define itmswap concat(itmswap_, TYPE) #define head concat(head_, TYPE) #define list concat(TYPE, ) #define list_head concat(TYPE, _head) @@ -40,8 +41,9 @@ #define list_find_gteq concat(TYPE, _find_gteq) #define list_del concat(TYPE, _del) #define list_pop concat(TYPE, _pop) +#define list_swap_all concat(TYPE, _swap_all) -#define ts_hash concat(ts_hash_, TYPE) +#define ts_hash_head concat(ts_hash_head_, TYPE) #ifndef REALTYPE #define REALTYPE TYPE @@ -89,10 +91,12 @@ DECLARE(REALTYPE, list, struct item, itm); #endif #define NITEM 10000 -struct item itm[NITEM]; +#define NITEM_SWAP 100 /* other container for swap */ +struct item itm[NITEM], itmswap[NITEM_SWAP]; static struct list_head head = concat(INIT_, REALTYPE)(head); -static void ts_hash(const char *text, const char *expect) +static void ts_hash_head(struct list_head *h, const char *text, + const char *expect) { int64_t us = monotime_since(&ref, NULL); SHA256_CTX ctx; @@ -102,13 +106,13 @@ static void ts_hash(const char *text, const char *expect) char hashtext[65]; uint32_t swap_count, count; - count = list_count(&head); + count = list_count(h); swap_count = htonl(count); SHA256_Init(&ctx); SHA256_Update(&ctx, &swap_count, sizeof(swap_count)); - frr_each (list, &head, item) { + frr_each (list, h, item) { struct { uint32_t val_upper, val_lower, index; } hashitem = { @@ -135,15 +139,20 @@ static void ts_hash(const char *text, const char *expect) } /* hashes will have different item ordering */ #if IS_HASH(REALTYPE) || IS_HEAP(REALTYPE) -#define ts_hashx(pos, csum) ts_hash(pos, NULL) +#define ts_hash(pos, csum) ts_hash_head(&head, pos, NULL) +#define ts_hashx(pos, csum) ts_hash_head(&head, pos, NULL) +#define ts_hash_headx(head, pos, csum) ts_hash_head(head, pos, NULL) #else -#define ts_hashx(pos, csum) ts_hash(pos, csum) +#define ts_hash(pos, csum) ts_hash_head(&head, pos, csum) +#define ts_hashx(pos, csum) ts_hash_head(&head, pos, csum) +#define ts_hash_headx(head, pos, csum) ts_hash_head(head, pos, csum) #endif static void concat(test_, TYPE)(void) { size_t i, j, k, l; struct prng *prng; + struct prng *prng_swap __attribute__((unused)); struct item *item, *prev __attribute__((unused)); struct item dummy __attribute__((unused)); @@ -151,6 +160,10 @@ static void concat(test_, TYPE)(void) for (i = 0; i < NITEM; i++) itm[i].val = i; + memset(itmswap, 0, sizeof(itmswap)); + for (i = 0; i < NITEM_SWAP; i++) + itmswap[i].val = i; + printfrr("%s start\n", str(TYPE)); ts_start(); @@ -178,6 +191,56 @@ static void concat(test_, TYPE)(void) assert(list_first(&head) != NULL); ts_hashx("fill", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838"); +#if !IS_ATOMIC(REALTYPE) + struct list_head other; + + list_init(&other); + list_swap_all(&head, &other); + + assert(list_count(&head) == 0); + assert(!list_first(&head)); + assert(list_count(&other) == k); + assert(list_first(&other) != NULL); + ts_hash_headx( + &other, "swap1", + "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838"); + + prng_swap = prng_new(0x1234dead); + l = 0; + for (i = 0; i < NITEM_SWAP; i++) { + j = prng_rand(prng_swap) % NITEM_SWAP; + if (itmswap[j].scratchpad == 0) { + list_add(&head, &itmswap[j]); + itmswap[j].scratchpad = 1; + l++; + } +#if !IS_HEAP(REALTYPE) + else { + struct item *rv = list_add(&head, &itmswap[j]); + assert(rv == &itmswap[j]); + } +#endif + } + assert(list_count(&head) == l); + assert(list_first(&head) != NULL); + ts_hash_headx( + &head, "swap-fill", + "26df437174051cf305d1bbb62d779ee450ca764167a1e7a94be1aece420008e6"); + + list_swap_all(&head, &other); + + assert(list_count(&other) == l); + assert(list_first(&other)); + ts_hash_headx( + &other, "swap2a", + "26df437174051cf305d1bbb62d779ee450ca764167a1e7a94be1aece420008e6"); + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hash_headx( + &head, "swap2b", + "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838"); +#endif /* !IS_ATOMIC */ + k = 0; #if IS_ATOMIC(REALTYPE) @@ -344,6 +407,50 @@ static void concat(test_, TYPE)(void) assert(list_first(&head) != NULL); ts_hash("fill / add_tail", "eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19"); +#if !IS_ATOMIC(REALTYPE) + struct list_head other; + + list_init(&other); + list_swap_all(&head, &other); + + assert(list_count(&head) == 0); + assert(!list_first(&head)); + assert(list_count(&other) == k); + assert(list_first(&other) != NULL); + ts_hash_head( + &other, "swap1", + "eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19"); + + prng_swap = prng_new(0x1234dead); + l = 0; + for (i = 0; i < NITEM_SWAP; i++) { + j = prng_rand(prng_swap) % NITEM_SWAP; + if (itmswap[j].scratchpad == 0) { + list_add_tail(&head, &itmswap[j]); + itmswap[j].scratchpad = 1; + l++; + } + } + assert(list_count(&head) == l); + assert(list_first(&head) != NULL); + ts_hash_head( + &head, "swap-fill", + "833e6ae437e322dfbd36eda8cfc33a61109be735b43f15d256c05e52d1b01909"); + + list_swap_all(&head, &other); + + assert(list_count(&other) == l); + assert(list_first(&other)); + ts_hash_head( + &other, "swap2a", + "833e6ae437e322dfbd36eda8cfc33a61109be735b43f15d256c05e52d1b01909"); + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hash_head( + &head, "swap2b", + "eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19"); +#endif + for (i = 0; i < NITEM / 2; i++) { j = prng_rand(prng) % NITEM; if (itm[j].scratchpad == 1) { @@ -546,10 +653,14 @@ static void concat(test_, TYPE)(void) printfrr("%s end\n", str(TYPE)); } +#undef ts_hash #undef ts_hashx +#undef ts_hash_head +#undef ts_hash_headx #undef item #undef itm +#undef itmswap #undef head #undef list #undef list_head @@ -571,6 +682,7 @@ static void concat(test_, TYPE)(void) #undef list_find_gteq #undef list_del #undef list_pop +#undef list_swap_all #undef REALTYPE #undef TYPE diff --git a/tests/topotests/Dockerfile b/tests/topotests/Dockerfile index c9110d2db9..1503e67d31 100644 --- a/tests/topotests/Dockerfile +++ b/tests/topotests/Dockerfile @@ -44,6 +44,7 @@ RUN export DEBIAN_FRONTEND=noninteractive \ xterm \ && pip install \ exabgp==3.4.17 \ + "scapy>=2.4.2" \ ipaddr \ pytest \ && rm -rf /var/lib/apt/lists/* |