bgpd: improve labelpool performance at scale

[mirror_frr.git] / bgpd / bgp_labelpool.c

/*
 * BGP Label Pool - Manage label chunk allocations from zebra asynchronously
 *
 * Copyright (C) 2018 LabN Consulting, L.L.C.
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 * more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; see the file COPYING; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <zebra.h>

#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

#ifndef VTYSH_EXTRACT_PL
#include "bgpd/bgp_labelpool_clippy.c"
#endif


/*
 * 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 thread_master *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();
#if CONFDATE > 20230131
CPP_NOTICE("Remove JSON object commands with keys starting with capital")
#endif
                json_object_int_add(json, "Ledger", skiplist_count(lp->ledger));
                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, "inUse", skiplist_count(lp->inuse));
                json_object_int_add(json, "Requests",
                                    lp_fifo_count(&lp->requests));
                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, "labelChunks", listcount(lp->chunks));
                json_object_int_add(json, "Pending", lp->pending_count);
                json_object_int_add(json, "pending", lp->pending_count);
                json_object_int_add(json, "Reconnects", lp->reconnect_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 thread *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 thread *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)
                thread_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)
                thread_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 */
}