// SPDX-License-Identifier: GPL-2.0-or-later /* * BGP Label Pool - Manage label chunk allocations from zebra asynchronously * * Copyright (C) 2018 LabN Consulting, L.L.C. */ #include #include "log.h" #include "memory.h" #include "stream.h" #include "mpls.h" #include "vty.h" #include "linklist.h" #include "skiplist.h" #include "workqueue.h" #include "zclient.h" #include "mpls.h" #include "bgpd/bgpd.h" #include "bgpd/bgp_labelpool.h" #include "bgpd/bgp_debug.h" #include "bgpd/bgp_errors.h" #include "bgpd/bgp_route.h" #define BGP_LABELPOOL_ENABLE_TESTS 0 #include "bgpd/bgp_labelpool_clippy.c" /* * Definitions and external declarations. */ extern struct zclient *zclient; #if BGP_LABELPOOL_ENABLE_TESTS static void lptest_init(void); static void lptest_finish(void); #endif /* * Remember where pool data are kept */ static struct labelpool *lp; /* * Number of labels requested at a time from the zebra label manager. * We start small but double the request size each time up to a * maximum size. * * The label space is 20 bits which is shared with other FRR processes * on this host, so to avoid greedily requesting a mostly wasted chunk, * we limit the chunk size to 1/16 of the label space (that's the -4 bits * in the definition below). This limit slightly increases our cost of * finding free labels in our allocated chunks. */ #define LP_CHUNK_SIZE_MIN 128 #define LP_CHUNK_SIZE_MAX (1 << (20 - 4)) DEFINE_MTYPE_STATIC(BGPD, BGP_LABEL_CHUNK, "BGP Label Chunk"); DEFINE_MTYPE_STATIC(BGPD, BGP_LABEL_FIFO, "BGP Label FIFO item"); DEFINE_MTYPE_STATIC(BGPD, BGP_LABEL_CB, "BGP Dynamic Label Assignment"); DEFINE_MTYPE_STATIC(BGPD, BGP_LABEL_CBQ, "BGP Dynamic Label Callback"); struct lp_chunk { uint32_t first; uint32_t last; uint32_t nfree; /* un-allocated count */ uint32_t idx_last_allocated; /* start looking here */ bitfield_t allocated_map; }; /* * label control block */ struct lp_lcb { mpls_label_t label; /* MPLS_LABEL_NONE = not allocated */ int type; void *labelid; /* unique ID */ /* * callback for label allocation and loss * * allocated: false = lost */ int (*cbfunc)(mpls_label_t label, void *lblid, bool alloc); }; struct lp_fifo { struct lp_fifo_item fifo; struct lp_lcb lcb; }; DECLARE_LIST(lp_fifo, struct lp_fifo, fifo); struct lp_cbq_item { int (*cbfunc)(mpls_label_t label, void *lblid, bool alloc); int type; mpls_label_t label; void *labelid; bool allocated; /* false = lost */ }; static wq_item_status lp_cbq_docallback(struct work_queue *wq, void *data) { struct lp_cbq_item *lcbq = data; int rc; int debug = BGP_DEBUG(labelpool, LABELPOOL); if (debug) zlog_debug("%s: calling callback with labelid=%p label=%u allocated=%d", __func__, lcbq->labelid, lcbq->label, lcbq->allocated); if (lcbq->label == MPLS_LABEL_NONE) { /* shouldn't happen */ flog_err(EC_BGP_LABEL, "%s: error: label==MPLS_LABEL_NONE", __func__); return WQ_SUCCESS; } rc = (*(lcbq->cbfunc))(lcbq->label, lcbq->labelid, lcbq->allocated); if (lcbq->allocated && rc) { /* * Callback rejected allocation. This situation could arise * if there was a label request followed by the requestor * deciding it didn't need the assignment (e.g., config * change) while the reply to the original request (with * label) was in the work queue. */ if (debug) zlog_debug("%s: callback rejected allocation, releasing labelid=%p label=%u", __func__, lcbq->labelid, lcbq->label); uintptr_t lbl = lcbq->label; void *labelid; struct lp_lcb *lcb; /* * If the rejected label was marked inuse by this labelid, * release the label back to the pool. * * Further, if the rejected label was still assigned to * this labelid in the LCB, delete the LCB. */ if (!skiplist_search(lp->inuse, (void *)lbl, &labelid)) { if (labelid == lcbq->labelid) { if (!skiplist_search(lp->ledger, labelid, (void **)&lcb)) { if (lcbq->label == lcb->label) skiplist_delete(lp->ledger, labelid, NULL); } skiplist_delete(lp->inuse, (void *)lbl, NULL); } } } return WQ_SUCCESS; } static void lp_cbq_item_free(struct work_queue *wq, void *data) { XFREE(MTYPE_BGP_LABEL_CBQ, data); } static void lp_lcb_free(void *goner) { XFREE(MTYPE_BGP_LABEL_CB, goner); } static void lp_chunk_free(void *goner) { struct lp_chunk *chunk = (struct lp_chunk *)goner; bf_free(chunk->allocated_map); XFREE(MTYPE_BGP_LABEL_CHUNK, goner); } void bgp_lp_init(struct event_loop *master, struct labelpool *pool) { if (BGP_DEBUG(labelpool, LABELPOOL)) zlog_debug("%s: entry", __func__); lp = pool; /* Set module pointer to pool data */ lp->ledger = skiplist_new(0, NULL, lp_lcb_free); lp->inuse = skiplist_new(0, NULL, NULL); lp->chunks = list_new(); lp->chunks->del = lp_chunk_free; lp_fifo_init(&lp->requests); lp->callback_q = work_queue_new(master, "label callbacks"); lp->callback_q->spec.workfunc = lp_cbq_docallback; lp->callback_q->spec.del_item_data = lp_cbq_item_free; lp->callback_q->spec.max_retries = 0; lp->next_chunksize = LP_CHUNK_SIZE_MIN; #if BGP_LABELPOOL_ENABLE_TESTS lptest_init(); #endif } /* check if a label callback was for a BGP LU node, and if so, unlock it */ static void check_bgp_lu_cb_unlock(struct lp_lcb *lcb) { if (lcb->type == LP_TYPE_BGP_LU) bgp_dest_unlock_node(lcb->labelid); } /* check if a label callback was for a BGP LU node, and if so, lock it */ static void check_bgp_lu_cb_lock(struct lp_lcb *lcb) { if (lcb->type == LP_TYPE_BGP_LU) bgp_dest_lock_node(lcb->labelid); } void bgp_lp_finish(void) { struct lp_fifo *lf; struct work_queue_item *item, *titem; #if BGP_LABELPOOL_ENABLE_TESTS lptest_finish(); #endif if (!lp) return; skiplist_free(lp->ledger); lp->ledger = NULL; skiplist_free(lp->inuse); lp->inuse = NULL; list_delete(&lp->chunks); while ((lf = lp_fifo_pop(&lp->requests))) { check_bgp_lu_cb_unlock(&lf->lcb); XFREE(MTYPE_BGP_LABEL_FIFO, lf); } lp_fifo_fini(&lp->requests); /* we must unlock path infos for LU callbacks; but we cannot do that * in the deletion callback of the workqueue, as that is also called * to remove an element from the queue after it has been run, resulting * in a double unlock. Hence we need to iterate over our queues and * lists and manually perform the unlocking (ugh) */ STAILQ_FOREACH_SAFE (item, &lp->callback_q->items, wq, titem) check_bgp_lu_cb_unlock(item->data); work_queue_free_and_null(&lp->callback_q); lp = NULL; } static mpls_label_t get_label_from_pool(void *labelid) { struct listnode *node; struct lp_chunk *chunk; int debug = BGP_DEBUG(labelpool, LABELPOOL); /* * Find a free label */ for (ALL_LIST_ELEMENTS_RO(lp->chunks, node, chunk)) { uintptr_t lbl; unsigned int index; if (debug) zlog_debug("%s: chunk first=%u last=%u", __func__, chunk->first, chunk->last); /* * don't look in chunks with no available labels */ if (!chunk->nfree) continue; /* * roll through bitfield starting where we stopped * last time */ index = bf_find_next_clear_bit_wrap( &chunk->allocated_map, chunk->idx_last_allocated + 1, 0); /* * since chunk->nfree is non-zero, we should always get * a valid index */ assert(index != WORD_MAX); lbl = chunk->first + index; if (skiplist_insert(lp->inuse, (void *)lbl, labelid)) { /* something is very wrong */ zlog_err("%s: unable to insert inuse label %u (id %p)", __func__, (uint32_t)lbl, labelid); return MPLS_LABEL_NONE; } /* * Success */ bf_set_bit(chunk->allocated_map, index); chunk->idx_last_allocated = index; chunk->nfree -= 1; return lbl; } return MPLS_LABEL_NONE; } /* * Success indicated by value of "label" field in returned LCB */ static struct lp_lcb *lcb_alloc( int type, void *labelid, int (*cbfunc)(mpls_label_t label, void *labelid, bool allocated)) { /* * Set up label control block */ struct lp_lcb *new = XCALLOC(MTYPE_BGP_LABEL_CB, sizeof(struct lp_lcb)); new->label = get_label_from_pool(labelid); new->type = type; new->labelid = labelid; new->cbfunc = cbfunc; return new; } /* * Callers who need labels must supply a type, labelid, and callback. * The type is a value defined in bgp_labelpool.h (add types as needed). * The callback is for asynchronous notification of label allocation. * The labelid is passed as an argument to the callback. It should be unique * to the requested label instance. * * If zebra is not connected, callbacks with labels will be delayed * until connection is established. If zebra connection is lost after * labels have been assigned, existing assignments via this labelpool * module will continue until reconnection. * * When connection to zebra is reestablished, previous label assignments * will be invalidated (via callbacks having the "allocated" parameter unset) * and new labels will be automatically reassigned by this labelpool module * (that is, a requestor does not need to call bgp_lp_get() again if it is * notified via callback that its label has been lost: it will eventually * get another callback with a new label assignment). * * The callback function should return 0 to accept the allocation * and non-zero to refuse it. The callback function return value is * ignored for invalidations (i.e., when the "allocated" parameter is false) * * Prior requests for a given labelid are detected so that requests and * assignments are not duplicated. */ void bgp_lp_get( int type, void *labelid, int (*cbfunc)(mpls_label_t label, void *labelid, bool allocated)) { struct lp_lcb *lcb; int requested = 0; int debug = BGP_DEBUG(labelpool, LABELPOOL); if (debug) zlog_debug("%s: labelid=%p", __func__, labelid); /* * Have we seen this request before? */ if (!skiplist_search(lp->ledger, labelid, (void **)&lcb)) { requested = 1; } else { lcb = lcb_alloc(type, labelid, cbfunc); if (debug) zlog_debug("%s: inserting lcb=%p label=%u", __func__, lcb, lcb->label); int rc = skiplist_insert(lp->ledger, labelid, lcb); if (rc) { /* shouldn't happen */ flog_err(EC_BGP_LABEL, "%s: can't insert new LCB into ledger list", __func__); XFREE(MTYPE_BGP_LABEL_CB, lcb); return; } } if (lcb->label != MPLS_LABEL_NONE) { /* * Fast path: we filled the request from local pool (or * this is a duplicate request that we filled already). * Enqueue response work item with new label. */ struct lp_cbq_item *q; q = XCALLOC(MTYPE_BGP_LABEL_CBQ, sizeof(struct lp_cbq_item)); q->cbfunc = lcb->cbfunc; q->type = lcb->type; q->label = lcb->label; q->labelid = lcb->labelid; q->allocated = true; /* if this is a LU request, lock node before queueing */ check_bgp_lu_cb_lock(lcb); work_queue_add(lp->callback_q, q); return; } if (requested) return; if (debug) zlog_debug("%s: slow path. lcb=%p label=%u", __func__, lcb, lcb->label); /* * Slow path: we are out of labels in the local pool, * so remember the request and also get another chunk from * the label manager. * * We track number of outstanding label requests: don't * need to get a chunk for each one. */ struct lp_fifo *lf = XCALLOC(MTYPE_BGP_LABEL_FIFO, sizeof(struct lp_fifo)); lf->lcb = *lcb; /* if this is a LU request, lock node before queueing */ check_bgp_lu_cb_lock(lcb); lp_fifo_add_tail(&lp->requests, lf); if (lp_fifo_count(&lp->requests) > lp->pending_count) { if (!zclient || zclient->sock < 0) return; if (zclient_send_get_label_chunk(zclient, 0, lp->next_chunksize, MPLS_LABEL_BASE_ANY) != ZCLIENT_SEND_FAILURE) { lp->pending_count += lp->next_chunksize; if ((lp->next_chunksize << 1) <= LP_CHUNK_SIZE_MAX) lp->next_chunksize <<= 1; } } } void bgp_lp_release( int type, void *labelid, mpls_label_t label) { struct lp_lcb *lcb; if (!skiplist_search(lp->ledger, labelid, (void **)&lcb)) { if (label == lcb->label && type == lcb->type) { struct listnode *node; struct lp_chunk *chunk; uintptr_t lbl = label; bool deallocated = false; /* no longer in use */ skiplist_delete(lp->inuse, (void *)lbl, NULL); /* no longer requested */ skiplist_delete(lp->ledger, labelid, NULL); /* * Find the chunk this label belongs to and * deallocate the label */ for (ALL_LIST_ELEMENTS_RO(lp->chunks, node, chunk)) { uint32_t index; if ((label < chunk->first) || (label > chunk->last)) continue; index = label - chunk->first; assert(bf_test_index(chunk->allocated_map, index)); bf_release_index(chunk->allocated_map, index); chunk->nfree += 1; deallocated = true; } assert(deallocated); } } } /* * zebra response giving us a chunk of labels */ void bgp_lp_event_chunk(uint8_t keep, uint32_t first, uint32_t last) { struct lp_chunk *chunk; int debug = BGP_DEBUG(labelpool, LABELPOOL); struct lp_fifo *lf; uint32_t labelcount; if (last < first) { flog_err(EC_BGP_LABEL, "%s: zebra label chunk invalid: first=%u, last=%u", __func__, first, last); return; } chunk = XCALLOC(MTYPE_BGP_LABEL_CHUNK, sizeof(struct lp_chunk)); labelcount = last - first + 1; chunk->first = first; chunk->last = last; chunk->nfree = labelcount; bf_init(chunk->allocated_map, labelcount); /* * Optimize for allocation by adding the new (presumably larger) * chunk at the head of the list so it is examined first. */ listnode_add_head(lp->chunks, chunk); lp->pending_count -= labelcount; if (debug) { zlog_debug("%s: %zu pending requests", __func__, lp_fifo_count(&lp->requests)); } while (labelcount && (lf = lp_fifo_first(&lp->requests))) { struct lp_lcb *lcb; void *labelid = lf->lcb.labelid; if (skiplist_search(lp->ledger, labelid, (void **)&lcb)) { /* request no longer in effect */ if (debug) { zlog_debug("%s: labelid %p: request no longer in effect", __func__, labelid); } /* if this was a BGP_LU request, unlock node */ check_bgp_lu_cb_unlock(lcb); goto finishedrequest; } /* have LCB */ if (lcb->label != MPLS_LABEL_NONE) { /* request already has a label */ if (debug) { zlog_debug("%s: labelid %p: request already has a label: %u=0x%x, lcb=%p", __func__, labelid, lcb->label, lcb->label, lcb); } /* if this was a BGP_LU request, unlock node */ check_bgp_lu_cb_unlock(lcb); goto finishedrequest; } lcb->label = get_label_from_pool(lcb->labelid); if (lcb->label == MPLS_LABEL_NONE) { /* * Out of labels in local pool, await next chunk */ if (debug) { zlog_debug("%s: out of labels, await more", __func__); } break; } labelcount -= 1; /* * we filled the request from local pool. * Enqueue response work item with new label. */ struct lp_cbq_item *q = XCALLOC(MTYPE_BGP_LABEL_CBQ, sizeof(struct lp_cbq_item)); q->cbfunc = lcb->cbfunc; q->type = lcb->type; q->label = lcb->label; q->labelid = lcb->labelid; q->allocated = true; if (debug) zlog_debug("%s: assigning label %u to labelid %p", __func__, q->label, q->labelid); work_queue_add(lp->callback_q, q); finishedrequest: lp_fifo_del(&lp->requests, lf); XFREE(MTYPE_BGP_LABEL_FIFO, lf); } } /* * continue using allocated labels until zebra returns */ void bgp_lp_event_zebra_down(void) { /* rats. */ } /* * Inform owners of previously-allocated labels that their labels * are not valid. Request chunk from zebra large enough to satisfy * previously-allocated labels plus any outstanding requests. */ void bgp_lp_event_zebra_up(void) { unsigned int labels_needed; unsigned int chunks_needed; void *labelid; struct lp_lcb *lcb; int lm_init_ok; lp->reconnect_count++; /* * Get label chunk allocation request dispatched to zebra */ labels_needed = lp_fifo_count(&lp->requests) + skiplist_count(lp->inuse); if (labels_needed > lp->next_chunksize) { while ((lp->next_chunksize < labels_needed) && (lp->next_chunksize << 1 <= LP_CHUNK_SIZE_MAX)) lp->next_chunksize <<= 1; } /* round up */ chunks_needed = (labels_needed / lp->next_chunksize) + 1; labels_needed = chunks_needed * lp->next_chunksize; lm_init_ok = lm_label_manager_connect(zclient, 1) == 0; if (!lm_init_ok) { zlog_err("%s: label manager connection error", __func__); return; } zclient_send_get_label_chunk(zclient, 0, labels_needed, MPLS_LABEL_BASE_ANY); lp->pending_count = labels_needed; /* * Invalidate current list of chunks */ list_delete_all_node(lp->chunks); /* * Invalidate any existing labels and requeue them as requests */ while (!skiplist_first(lp->inuse, NULL, &labelid)) { /* * Get LCB */ if (!skiplist_search(lp->ledger, labelid, (void **)&lcb)) { if (lcb->label != MPLS_LABEL_NONE) { /* * invalidate */ struct lp_cbq_item *q; q = XCALLOC(MTYPE_BGP_LABEL_CBQ, sizeof(struct lp_cbq_item)); q->cbfunc = lcb->cbfunc; q->type = lcb->type; q->label = lcb->label; q->labelid = lcb->labelid; q->allocated = false; check_bgp_lu_cb_lock(lcb); work_queue_add(lp->callback_q, q); lcb->label = MPLS_LABEL_NONE; } /* * request queue */ struct lp_fifo *lf = XCALLOC(MTYPE_BGP_LABEL_FIFO, sizeof(struct lp_fifo)); lf->lcb = *lcb; check_bgp_lu_cb_lock(lcb); lp_fifo_add_tail(&lp->requests, lf); } skiplist_delete_first(lp->inuse); } } DEFUN(show_bgp_labelpool_summary, show_bgp_labelpool_summary_cmd, "show bgp labelpool summary [json]", SHOW_STR BGP_STR "BGP Labelpool information\n" "BGP Labelpool summary\n" JSON_STR) { bool uj = use_json(argc, argv); json_object *json = NULL; if (!lp) { if (uj) vty_out(vty, "{}\n"); else vty_out(vty, "No existing BGP labelpool\n"); return (CMD_WARNING); } if (uj) { json = json_object_new_object(); json_object_int_add(json, "ledger", skiplist_count(lp->ledger)); json_object_int_add(json, "inUse", skiplist_count(lp->inuse)); json_object_int_add(json, "requests", lp_fifo_count(&lp->requests)); json_object_int_add(json, "labelChunks", listcount(lp->chunks)); json_object_int_add(json, "pending", lp->pending_count); json_object_int_add(json, "reconnects", lp->reconnect_count); vty_json(vty, json); } else { vty_out(vty, "Labelpool Summary\n"); vty_out(vty, "-----------------\n"); vty_out(vty, "%-13s %d\n", "Ledger:", skiplist_count(lp->ledger)); vty_out(vty, "%-13s %d\n", "InUse:", skiplist_count(lp->inuse)); vty_out(vty, "%-13s %zu\n", "Requests:", lp_fifo_count(&lp->requests)); vty_out(vty, "%-13s %d\n", "LabelChunks:", listcount(lp->chunks)); vty_out(vty, "%-13s %d\n", "Pending:", lp->pending_count); vty_out(vty, "%-13s %d\n", "Reconnects:", lp->reconnect_count); } return CMD_SUCCESS; } DEFUN(show_bgp_labelpool_ledger, show_bgp_labelpool_ledger_cmd, "show bgp labelpool ledger [json]", SHOW_STR BGP_STR "BGP Labelpool information\n" "BGP Labelpool ledger\n" JSON_STR) { bool uj = use_json(argc, argv); json_object *json = NULL, *json_elem = NULL; struct lp_lcb *lcb = NULL; struct bgp_dest *dest; void *cursor = NULL; const struct prefix *p; int rc, count; if (!lp) { if (uj) vty_out(vty, "{}\n"); else vty_out(vty, "No existing BGP labelpool\n"); return (CMD_WARNING); } if (uj) { count = skiplist_count(lp->ledger); if (!count) { vty_out(vty, "{}\n"); return CMD_SUCCESS; } json = json_object_new_array(); } else { vty_out(vty, "Prefix Label\n"); vty_out(vty, "---------------------------\n"); } for (rc = skiplist_next(lp->ledger, (void **)&dest, (void **)&lcb, &cursor); !rc; rc = skiplist_next(lp->ledger, (void **)&dest, (void **)&lcb, &cursor)) { if (uj) { json_elem = json_object_new_object(); json_object_array_add(json, json_elem); } switch (lcb->type) { case LP_TYPE_BGP_LU: if (!CHECK_FLAG(dest->flags, BGP_NODE_LABEL_REQUESTED)) if (uj) { json_object_string_add( json_elem, "prefix", "INVALID"); json_object_int_add(json_elem, "label", lcb->label); } else vty_out(vty, "%-18s %u\n", "INVALID", lcb->label); else { p = bgp_dest_get_prefix(dest); if (uj) { json_object_string_addf( json_elem, "prefix", "%pFX", p); json_object_int_add(json_elem, "label", lcb->label); } else vty_out(vty, "%-18pFX %u\n", p, lcb->label); } break; case LP_TYPE_VRF: if (uj) { json_object_string_add(json_elem, "prefix", "VRF"); json_object_int_add(json_elem, "label", lcb->label); } else vty_out(vty, "%-18s %u\n", "VRF", lcb->label); break; } } if (uj) vty_json(vty, json); return CMD_SUCCESS; } DEFUN(show_bgp_labelpool_inuse, show_bgp_labelpool_inuse_cmd, "show bgp labelpool inuse [json]", SHOW_STR BGP_STR "BGP Labelpool information\n" "BGP Labelpool inuse\n" JSON_STR) { bool uj = use_json(argc, argv); json_object *json = NULL, *json_elem = NULL; struct bgp_dest *dest; mpls_label_t label; struct lp_lcb *lcb; void *cursor = NULL; const struct prefix *p; int rc, count; if (!lp) { vty_out(vty, "No existing BGP labelpool\n"); return (CMD_WARNING); } if (!lp) { if (uj) vty_out(vty, "{}\n"); else vty_out(vty, "No existing BGP labelpool\n"); return (CMD_WARNING); } if (uj) { count = skiplist_count(lp->inuse); if (!count) { vty_out(vty, "{}\n"); return CMD_SUCCESS; } json = json_object_new_array(); } else { vty_out(vty, "Prefix Label\n"); vty_out(vty, "---------------------------\n"); } for (rc = skiplist_next(lp->inuse, (void **)&label, (void **)&dest, &cursor); !rc; rc = skiplist_next(lp->ledger, (void **)&label, (void **)&dest, &cursor)) { if (skiplist_search(lp->ledger, dest, (void **)&lcb)) continue; if (uj) { json_elem = json_object_new_object(); json_object_array_add(json, json_elem); } switch (lcb->type) { case LP_TYPE_BGP_LU: if (!CHECK_FLAG(dest->flags, BGP_NODE_LABEL_REQUESTED)) if (uj) { json_object_string_add( json_elem, "prefix", "INVALID"); json_object_int_add(json_elem, "label", label); } else vty_out(vty, "INVALID %u\n", label); else { p = bgp_dest_get_prefix(dest); if (uj) { json_object_string_addf( json_elem, "prefix", "%pFX", p); json_object_int_add(json_elem, "label", label); } else vty_out(vty, "%-18pFX %u\n", p, label); } break; case LP_TYPE_VRF: if (uj) { json_object_string_add(json_elem, "prefix", "VRF"); json_object_int_add(json_elem, "label", label); } else vty_out(vty, "%-18s %u\n", "VRF", label); break; } } if (uj) vty_json(vty, json); return CMD_SUCCESS; } DEFUN(show_bgp_labelpool_requests, show_bgp_labelpool_requests_cmd, "show bgp labelpool requests [json]", SHOW_STR BGP_STR "BGP Labelpool information\n" "BGP Labelpool requests\n" JSON_STR) { bool uj = use_json(argc, argv); json_object *json = NULL, *json_elem = NULL; struct bgp_dest *dest; const struct prefix *p; struct lp_fifo *item, *next; int count; if (!lp) { if (uj) vty_out(vty, "{}\n"); else vty_out(vty, "No existing BGP labelpool\n"); return (CMD_WARNING); } if (uj) { count = lp_fifo_count(&lp->requests); if (!count) { vty_out(vty, "{}\n"); return CMD_SUCCESS; } json = json_object_new_array(); } else { vty_out(vty, "Prefix \n"); vty_out(vty, "----------------\n"); } for (item = lp_fifo_first(&lp->requests); item; item = next) { next = lp_fifo_next_safe(&lp->requests, item); dest = item->lcb.labelid; if (uj) { json_elem = json_object_new_object(); json_object_array_add(json, json_elem); } switch (item->lcb.type) { case LP_TYPE_BGP_LU: if (!CHECK_FLAG(dest->flags, BGP_NODE_LABEL_REQUESTED)) { if (uj) json_object_string_add( json_elem, "prefix", "INVALID"); else vty_out(vty, "INVALID\n"); } else { p = bgp_dest_get_prefix(dest); if (uj) json_object_string_addf( json_elem, "prefix", "%pFX", p); else vty_out(vty, "%-18pFX\n", p); } break; case LP_TYPE_VRF: if (uj) json_object_string_add(json_elem, "prefix", "VRF"); else vty_out(vty, "VRF\n"); break; } } if (uj) vty_json(vty, json); return CMD_SUCCESS; } DEFUN(show_bgp_labelpool_chunks, show_bgp_labelpool_chunks_cmd, "show bgp labelpool chunks [json]", SHOW_STR BGP_STR "BGP Labelpool information\n" "BGP Labelpool chunks\n" JSON_STR) { bool uj = use_json(argc, argv); json_object *json = NULL, *json_elem; struct listnode *node; struct lp_chunk *chunk; int count; if (!lp) { if (uj) vty_out(vty, "{}\n"); else vty_out(vty, "No existing BGP labelpool\n"); return (CMD_WARNING); } if (uj) { count = listcount(lp->chunks); if (!count) { vty_out(vty, "{}\n"); return CMD_SUCCESS; } json = json_object_new_array(); } else { vty_out(vty, "%10s %10s %10s %10s\n", "First", "Last", "Size", "nfree"); vty_out(vty, "-------------------------------------------\n"); } for (ALL_LIST_ELEMENTS_RO(lp->chunks, node, chunk)) { uint32_t size; size = chunk->last - chunk->first + 1; if (uj) { json_elem = json_object_new_object(); json_object_array_add(json, json_elem); json_object_int_add(json_elem, "first", chunk->first); json_object_int_add(json_elem, "last", chunk->last); json_object_int_add(json_elem, "size", size); json_object_int_add(json_elem, "numberFree", chunk->nfree); } else vty_out(vty, "%10u %10u %10u %10u\n", chunk->first, chunk->last, size, chunk->nfree); } if (uj) vty_json(vty, json); return CMD_SUCCESS; } #if BGP_LABELPOOL_ENABLE_TESTS /*------------------------------------------------------------------------ * Testing code start *------------------------------------------------------------------------*/ DEFINE_MTYPE_STATIC(BGPD, LABELPOOL_TEST, "Label pool test"); #define LPT_STAT_INSERT_FAIL 0 #define LPT_STAT_DELETE_FAIL 1 #define LPT_STAT_ALLOCATED 2 #define LPT_STAT_DEALLOCATED 3 #define LPT_STAT_MAX 4 const char *lpt_counter_names[] = { "sl insert failures", "sl delete failures", "labels allocated", "labels deallocated", }; static uint8_t lpt_generation; static bool lpt_inprogress; static struct skiplist *lp_tests; static unsigned int lpt_test_cb_tcb_lookup_fails; static unsigned int lpt_release_tcb_lookup_fails; static unsigned int lpt_test_event_tcb_lookup_fails; static unsigned int lpt_stop_tcb_lookup_fails; struct lp_test { uint8_t generation; unsigned int request_maximum; unsigned int request_blocksize; uintptr_t request_count; /* match type of labelid */ int label_type; struct skiplist *labels; struct timeval starttime; struct skiplist *timestamps_alloc; struct skiplist *timestamps_dealloc; struct event *event_thread; unsigned int counter[LPT_STAT_MAX]; }; /* test parameters */ #define LPT_MAX_COUNT 500000 /* get this many labels in all */ #define LPT_BLKSIZE 10000 /* this many at a time, then yield */ #define LPT_TS_INTERVAL 10000 /* timestamp every this many labels */ static int test_cb(mpls_label_t label, void *labelid, bool allocated) { uintptr_t generation; struct lp_test *tcb; generation = ((uintptr_t)labelid >> 24) & 0xff; if (skiplist_search(lp_tests, (void *)generation, (void **)&tcb)) { /* couldn't find current test in progress */ ++lpt_test_cb_tcb_lookup_fails; return -1; /* reject allocation */ } if (allocated) { ++tcb->counter[LPT_STAT_ALLOCATED]; if (!(tcb->counter[LPT_STAT_ALLOCATED] % LPT_TS_INTERVAL)) { uintptr_t time_ms; time_ms = monotime_since(&tcb->starttime, NULL) / 1000; skiplist_insert(tcb->timestamps_alloc, (void *)(uintptr_t)tcb ->counter[LPT_STAT_ALLOCATED], (void *)time_ms); } if (skiplist_insert(tcb->labels, labelid, (void *)(uintptr_t)label)) { ++tcb->counter[LPT_STAT_INSERT_FAIL]; return -1; } } else { ++tcb->counter[LPT_STAT_DEALLOCATED]; if (!(tcb->counter[LPT_STAT_DEALLOCATED] % LPT_TS_INTERVAL)) { uintptr_t time_ms; time_ms = monotime_since(&tcb->starttime, NULL) / 1000; skiplist_insert(tcb->timestamps_dealloc, (void *)(uintptr_t)tcb ->counter[LPT_STAT_ALLOCATED], (void *)time_ms); } if (skiplist_delete(tcb->labels, labelid, 0)) { ++tcb->counter[LPT_STAT_DELETE_FAIL]; return -1; } } return 0; } static void labelpool_test_event_handler(struct event *thread) { struct lp_test *tcb; if (skiplist_search(lp_tests, (void *)(uintptr_t)(lpt_generation), (void **)&tcb)) { /* couldn't find current test in progress */ ++lpt_test_event_tcb_lookup_fails; return; } /* * request a bunch of labels */ for (unsigned int i = 0; (i < tcb->request_blocksize) && (tcb->request_count < tcb->request_maximum); ++i) { uintptr_t id; ++tcb->request_count; /* * construct 32-bit id from request_count and generation */ id = ((uintptr_t)tcb->generation << 24) | (tcb->request_count & 0x00ffffff); bgp_lp_get(LP_TYPE_VRF, (void *)id, test_cb); } if (tcb->request_count < tcb->request_maximum) thread_add_event(bm->master, labelpool_test_event_handler, NULL, 0, &tcb->event_thread); } static void lptest_stop(void) { struct lp_test *tcb; if (!lpt_inprogress) return; if (skiplist_search(lp_tests, (void *)(uintptr_t)(lpt_generation), (void **)&tcb)) { /* couldn't find current test in progress */ ++lpt_stop_tcb_lookup_fails; return; } if (tcb->event_thread) event_cancel(&tcb->event_thread); lpt_inprogress = false; } static int lptest_start(struct vty *vty) { struct lp_test *tcb; if (lpt_inprogress) { vty_out(vty, "test already in progress\n"); return -1; } if (skiplist_count(lp_tests) >= (1 << (8 * sizeof(lpt_generation))) - 1) { /* * Too many test runs */ vty_out(vty, "too many tests: clear first\n"); return -1; } /* * We pack the generation and request number into the labelid; * make sure they fit. */ unsigned int n1 = LPT_MAX_COUNT; unsigned int sh = 0; unsigned int label_bits; label_bits = 8 * (sizeof(tcb->request_count) - sizeof(lpt_generation)); /* n1 should be same type as tcb->request_maximum */ assert(sizeof(n1) == sizeof(tcb->request_maximum)); while (n1 >>= 1) ++sh; sh += 1; /* number of bits needed to hold LPT_MAX_COUNT */ if (sh > label_bits) { vty_out(vty, "Sorry, test iteration count too big on this platform (LPT_MAX_COUNT %u, need %u bits, but label_bits is only %u)\n", LPT_MAX_COUNT, sh, label_bits); return -1; } lpt_inprogress = true; ++lpt_generation; tcb = XCALLOC(MTYPE_LABELPOOL_TEST, sizeof(*tcb)); tcb->generation = lpt_generation; tcb->label_type = LP_TYPE_VRF; tcb->request_maximum = LPT_MAX_COUNT; tcb->request_blocksize = LPT_BLKSIZE; tcb->labels = skiplist_new(0, NULL, NULL); tcb->timestamps_alloc = skiplist_new(0, NULL, NULL); tcb->timestamps_dealloc = skiplist_new(0, NULL, NULL); thread_add_event(bm->master, labelpool_test_event_handler, NULL, 0, &tcb->event_thread); monotime(&tcb->starttime); skiplist_insert(lp_tests, (void *)(uintptr_t)tcb->generation, tcb); return 0; } DEFPY(start_labelpool_perf_test, start_labelpool_perf_test_cmd, "debug bgp lptest start", DEBUG_STR BGP_STR "label pool test\n" "start\n") { lptest_start(vty); return CMD_SUCCESS; } static void lptest_print_stats(struct vty *vty, struct lp_test *tcb) { unsigned int i; vty_out(vty, "Global Lookup Failures in test_cb: %5u\n", lpt_test_cb_tcb_lookup_fails); vty_out(vty, "Global Lookup Failures in release: %5u\n", lpt_release_tcb_lookup_fails); vty_out(vty, "Global Lookup Failures in event: %5u\n", lpt_test_event_tcb_lookup_fails); vty_out(vty, "Global Lookup Failures in stop: %5u\n", lpt_stop_tcb_lookup_fails); vty_out(vty, "\n"); if (!tcb) { if (skiplist_search(lp_tests, (void *)(uintptr_t)lpt_generation, (void **)&tcb)) { vty_out(vty, "Error: can't find test %u\n", lpt_generation); return; } } vty_out(vty, "Test Generation %u:\n", tcb->generation); vty_out(vty, "Counter Value\n"); for (i = 0; i < LPT_STAT_MAX; ++i) { vty_out(vty, "%20s: %10u\n", lpt_counter_names[i], tcb->counter[i]); } vty_out(vty, "\n"); if (tcb->timestamps_alloc) { void *Key; void *Value; void *cursor; float elapsed; vty_out(vty, "%10s %10s\n", "Count", "Seconds"); cursor = NULL; while (!skiplist_next(tcb->timestamps_alloc, &Key, &Value, &cursor)) { elapsed = ((float)(uintptr_t)Value) / 1000; vty_out(vty, "%10llu %10.3f\n", (unsigned long long)(uintptr_t)Key, elapsed); } vty_out(vty, "\n"); } } DEFPY(show_labelpool_perf_test, show_labelpool_perf_test_cmd, "debug bgp lptest show", DEBUG_STR BGP_STR "label pool test\n" "show\n") { if (lp_tests) { void *Key; void *Value; void *cursor; cursor = NULL; while (!skiplist_next(lp_tests, &Key, &Value, &cursor)) { lptest_print_stats(vty, (struct lp_test *)Value); } } else { vty_out(vty, "no test results\n"); } return CMD_SUCCESS; } DEFPY(stop_labelpool_perf_test, stop_labelpool_perf_test_cmd, "debug bgp lptest stop", DEBUG_STR BGP_STR "label pool test\n" "stop\n") { if (lpt_inprogress) { lptest_stop(); lptest_print_stats(vty, NULL); } else { vty_out(vty, "no test in progress\n"); } return CMD_SUCCESS; } DEFPY(clear_labelpool_perf_test, clear_labelpool_perf_test_cmd, "debug bgp lptest clear", DEBUG_STR BGP_STR "label pool test\n" "clear\n") { if (lpt_inprogress) { lptest_stop(); } if (lp_tests) { while (!skiplist_first(lp_tests, NULL, NULL)) /* del function of skiplist cleans up tcbs */ skiplist_delete_first(lp_tests); } return CMD_SUCCESS; } /* * With the "release" command, we can release labels at intervals through * the ID space. Thus we can to exercise the bitfield-wrapping behavior * of the allocator in a subsequent test. */ /* clang-format off */ DEFPY(release_labelpool_perf_test, release_labelpool_perf_test_cmd, "debug bgp lptest release test GENERATION$generation every (1-5)$every_nth", DEBUG_STR BGP_STR "label pool test\n" "release labels\n" "\"test\"\n" "test number\n" "\"every\"\n" "label fraction denominator\n") { /* clang-format on */ unsigned long testnum; char *end; struct lp_test *tcb; testnum = strtoul(generation, &end, 0); if (*end) { vty_out(vty, "Invalid test number: \"%s\"\n", generation); return CMD_SUCCESS; } if (lpt_inprogress && (testnum == lpt_generation)) { vty_out(vty, "Error: Test %lu is still in progress (stop first)\n", testnum); return CMD_SUCCESS; } if (skiplist_search(lp_tests, (void *)(uintptr_t)testnum, (void **)&tcb)) { /* couldn't find current test in progress */ vty_out(vty, "Error: Can't look up test number: \"%lu\"\n", testnum); ++lpt_release_tcb_lookup_fails; return CMD_SUCCESS; } void *Key, *cKey; void *Value, *cValue; void *cursor; unsigned int iteration; int rc; cursor = NULL; iteration = 0; rc = skiplist_next(tcb->labels, &Key, &Value, &cursor); while (!rc) { cKey = Key; cValue = Value; /* find next item before we delete this one */ rc = skiplist_next(tcb->labels, &Key, &Value, &cursor); if (!(iteration % every_nth)) { bgp_lp_release(tcb->label_type, cKey, (mpls_label_t)(uintptr_t)cValue); skiplist_delete(tcb->labels, cKey, NULL); ++tcb->counter[LPT_STAT_DEALLOCATED]; } ++iteration; } return CMD_SUCCESS; } static void lptest_delete(void *val) { struct lp_test *tcb = (struct lp_test *)val; void *Key; void *Value; void *cursor; if (tcb->labels) { cursor = NULL; while (!skiplist_next(tcb->labels, &Key, &Value, &cursor)) bgp_lp_release(tcb->label_type, Key, (mpls_label_t)(uintptr_t)Value); skiplist_free(tcb->labels); tcb->labels = NULL; } if (tcb->timestamps_alloc) { cursor = NULL; skiplist_free(tcb->timestamps_alloc); tcb->timestamps_alloc = NULL; } if (tcb->timestamps_dealloc) { cursor = NULL; skiplist_free(tcb->timestamps_dealloc); tcb->timestamps_dealloc = NULL; } if (tcb->event_thread) event_cancel(&tcb->event_thread); memset(tcb, 0, sizeof(*tcb)); XFREE(MTYPE_LABELPOOL_TEST, tcb); } static void lptest_init(void) { lp_tests = skiplist_new(0, NULL, lptest_delete); } static void lptest_finish(void) { if (lp_tests) { skiplist_free(lp_tests); lp_tests = NULL; } } /*------------------------------------------------------------------------ * Testing code end *------------------------------------------------------------------------*/ #endif /* BGP_LABELPOOL_ENABLE_TESTS */ void bgp_lp_vty_init(void) { install_element(VIEW_NODE, &show_bgp_labelpool_summary_cmd); install_element(VIEW_NODE, &show_bgp_labelpool_ledger_cmd); install_element(VIEW_NODE, &show_bgp_labelpool_inuse_cmd); install_element(VIEW_NODE, &show_bgp_labelpool_requests_cmd); install_element(VIEW_NODE, &show_bgp_labelpool_chunks_cmd); #if BGP_LABELPOOL_ENABLE_TESTS install_element(ENABLE_NODE, &start_labelpool_perf_test_cmd); install_element(ENABLE_NODE, &show_labelpool_perf_test_cmd); install_element(ENABLE_NODE, &stop_labelpool_perf_test_cmd); install_element(ENABLE_NODE, &release_labelpool_perf_test_cmd); install_element(ENABLE_NODE, &clear_labelpool_perf_test_cmd); #endif /* BGP_LABELPOOL_ENABLE_TESTS */ }