[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 "bgpd/bgpd.h"
#include "bgpd/bgp_labelpool.h"
#include "bgpd/bgp_debug.h"
#include "bgpd/bgp_errors.h"

/*
 * Definitions and external declarations.
 */
extern struct zclient *zclient;

/*
 * Remember where pool data are kept
 */
static struct labelpool *lp;

/* request this many labels at a time from zebra */
#define LP_CHUNK_SIZE	50

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;
};

/*
 * 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)
{
	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;
}

void bgp_lp_finish(void)
{
	struct lp_fifo *lf;

	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)))
		XFREE(MTYPE_BGP_LABEL_FIFO, lf);
	lp_fifo_fini(&lp->requests);

	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
	 * Linear search is not efficient but should be executed infrequently.
	 */
	for (ALL_LIST_ELEMENTS_RO(lp->chunks, node, chunk)) {
		uintptr_t lbl;

		if (debug)
			zlog_debug("%s: chunk first=%u last=%u",
				__func__, chunk->first, chunk->last);

		for (lbl = chunk->first; lbl <= chunk->last; ++lbl) {
			/* labelid is key to all-request "ledger" list */
			if (!skiplist_insert(lp->inuse, (void *)lbl, labelid)) {
				/*
				 * Success
				 */
				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 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).
 *
 * 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;

		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;
	lp_fifo_add_tail(&lp->requests, lf);

	if (lp_fifo_count(&lp->requests) > lp->pending_count) {
		if (!zclient_send_get_label_chunk(zclient, 0, LP_CHUNK_SIZE)) {
			lp->pending_count += LP_CHUNK_SIZE;
			return;
		}
	}
}

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) {
			uintptr_t lbl = label;

			/* no longer in use */
			skiplist_delete(lp->inuse, (void *)lbl, NULL);

			/* no longer requested */
			skiplist_delete(lp->ledger, labelid, NULL);
		}
	}
}

/*
 * 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;

	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));

	chunk->first = first;
	chunk->last = last;

	listnode_add(lp->chunks, chunk);

	lp->pending_count -= (last - first + 1);

	if (debug) {
		zlog_debug("%s: %zu pending requests", __func__,
			lp_fifo_count(&lp->requests));
	}

	while ((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);
			}
			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);
			}
			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;
		}

		/*
		 * 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)
{
	int labels_needed;
	int chunks_needed;
	void *labelid;
	struct lp_lcb *lcb;
	int lm_init_ok;

	/*
	 * Get label chunk allocation request dispatched to zebra
	 */
	labels_needed = lp_fifo_count(&lp->requests) +
		skiplist_count(lp->inuse);

	/* round up */
	chunks_needed = (labels_needed / LP_CHUNK_SIZE) + 1;
	labels_needed = chunks_needed * LP_CHUNK_SIZE;

	lm_init_ok = lm_label_manager_connect(zclient, 1) == 0;

	if (!lm_init_ok)
		zlog_err("%s: label manager connection error", __func__);

	zclient_send_get_label_chunk(zclient, 0, labels_needed);
	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;
				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;
			lp_fifo_add_tail(&lp->requests, lf);
		}

		skiplist_delete_first(lp->inuse);
	}
}
Commit	Line	Data
955bfd98 PZ	1	/*
	2	* BGP Label Pool - Manage label chunk allocations from zebra asynchronously
	3	*
	4	* Copyright (C) 2018 LabN Consulting, L.L.C.
	5	*
	6	* This program is free software; you can redistribute it and/or modify it
	7	* under the terms of the GNU General Public License as published by the Free
	8	* Software Foundation; either version 2 of the License, or (at your option)
	9	* any later version.
	10	*
	11	* This program is distributed in the hope that it will be useful, but WITHOUT
	12	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	13	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
	14	* more details.
	15	*
	16	* You should have received a copy of the GNU General Public License along
	17	* with this program; see the file COPYING; if not, write to the Free Software
	18	* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
	19	*/
	20
	21	#include <zebra.h>
	22
	23	#include "log.h"
	24	#include "memory.h"
	25	#include "stream.h"
	26	#include "mpls.h"
	27	#include "vty.h"
955bfd98 PZ	28	#include "linklist.h"
	29	#include "skiplist.h"
	30	#include "workqueue.h"
	31	#include "zclient.h"
	32
	33	#include "bgpd/bgpd.h"
	34	#include "bgpd/bgp_labelpool.h"
	35	#include "bgpd/bgp_debug.h"
14454c9f	36	#include "bgpd/bgp_errors.h"
955bfd98 PZ	37
	38	/*
	39	* Definitions and external declarations.
	40	*/
	41	extern struct zclient *zclient;
	42
	43	/*
	44	* Remember where pool data are kept
	45	*/
	46	static struct labelpool *lp;
	47
	48	/* request this many labels at a time from zebra */
	49	#define LP_CHUNK_SIZE 50
	50
	51	DEFINE_MTYPE_STATIC(BGPD, BGP_LABEL_CHUNK, "BGP Label Chunk")
41397f2e	52	DEFINE_MTYPE_STATIC(BGPD, BGP_LABEL_FIFO, "BGP Label FIFO item")
955bfd98 PZ	53	DEFINE_MTYPE_STATIC(BGPD, BGP_LABEL_CB, "BGP Dynamic Label Assignment")
	54	DEFINE_MTYPE_STATIC(BGPD, BGP_LABEL_CBQ, "BGP Dynamic Label Callback")
	55
955bfd98 PZ	56	struct lp_chunk {
	57	uint32_t first;
	58	uint32_t last;
	59	};
	60
	61	/*
	62	* label control block
	63	*/
	64	struct lp_lcb {
	65	mpls_label_t label; /* MPLS_LABEL_NONE = not allocated */
	66	int type;
	67	void labelid; / unique ID */
	68	/*
	69	* callback for label allocation and loss
	70	*
	71	* allocated: false = lost
	72	*/
	73	int (cbfunc)(mpls_label_t label, void lblid, bool alloc);
	74	};
	75
955bfd98	76	struct lp_fifo {
41397f2e	77	struct lp_fifo_item fifo;
955bfd98 PZ	78	struct lp_lcb lcb;
	79	};
	80
41397f2e DL	81	DECLARE_LIST(lp_fifo, struct lp_fifo, fifo)
41397f2e DL	82
955bfd98 PZ	83	struct lp_cbq_item {
	84	int (cbfunc)(mpls_label_t label, void lblid, bool alloc);
	85	int type;
	86	mpls_label_t label;
	87	void *labelid;
	88	bool allocated; /* false = lost */
	89	};
	90
	91	static wq_item_status lp_cbq_docallback(struct work_queue wq, void data)
	92	{
	93	struct lp_cbq_item *lcbq = data;
	94	int rc;
	95	int debug = BGP_DEBUG(labelpool, LABELPOOL);
	96
	97	if (debug)
	98	zlog_debug("%s: calling callback with labelid=%p label=%u allocated=%d",
	99	__func__, lcbq->labelid, lcbq->label, lcbq->allocated);
	100
	101	if (lcbq->label == MPLS_LABEL_NONE) {
	102	/* shouldn't happen */
e50f7cfd	103	flog_err(EC_BGP_LABEL, "%s: error: label==MPLS_LABEL_NONE",
1c50c1c0	104	__func__);
955bfd98 PZ	105	return WQ_SUCCESS;
	106	}
	107
	108	rc = (*(lcbq->cbfunc))(lcbq->label, lcbq->labelid, lcbq->allocated);
	109
	110	if (lcbq->allocated && rc) {
	111	/*
	112	* Callback rejected allocation. This situation could arise
	113	* if there was a label request followed by the requestor
	114	* deciding it didn't need the assignment (e.g., config
	115	* change) while the reply to the original request (with
	116	* label) was in the work queue.
	117	*/
	118	if (debug)
	119	zlog_debug("%s: callback rejected allocation, releasing labelid=%p label=%u",
	120	__func__, lcbq->labelid, lcbq->label);
	121
	122	uintptr_t lbl = lcbq->label;
	123	void *labelid;
	124	struct lp_lcb *lcb;
	125
	126	/*
	127	* If the rejected label was marked inuse by this labelid,
	128	* release the label back to the pool.
	129	*
	130	* Further, if the rejected label was still assigned to
	131	* this labelid in the LCB, delete the LCB.
	132	*/
	133	if (!skiplist_search(lp->inuse, (void *)lbl, &labelid)) {
	134	if (labelid == lcbq->labelid) {
	135	if (!skiplist_search(lp->ledger, labelid,
	136	(void **)&lcb)) {
	137	if (lcbq->label == lcb->label)
	138	skiplist_delete(lp->ledger,
	139	labelid, NULL);
	140	}
	141	skiplist_delete(lp->inuse, (void *)lbl, NULL);
	142	}
	143	}
	144	}
	145
	146	return WQ_SUCCESS;
	147	}
	148
	149	static void lp_cbq_item_free(struct work_queue wq, void data)
	150	{
	151	XFREE(MTYPE_BGP_LABEL_CBQ, data);
	152	}
	153
	154	static void lp_lcb_free(void *goner)
	155	{
0a22ddfb	156	XFREE(MTYPE_BGP_LABEL_CB, goner);
955bfd98 PZ	157	}
	158
	159	static void lp_chunk_free(void *goner)
	160	{
0a22ddfb	161	XFREE(MTYPE_BGP_LABEL_CHUNK, goner);
955bfd98 PZ	162	}
	163
	164	void bgp_lp_init(struct thread_master master, struct labelpool pool)
	165	{
	166	if (BGP_DEBUG(labelpool, LABELPOOL))
	167	zlog_debug("%s: entry", __func__);
	168
	169	lp = pool; /* Set module pointer to pool data */
	170
	171	lp->ledger = skiplist_new(0, NULL, lp_lcb_free);
	172	lp->inuse = skiplist_new(0, NULL, NULL);
	173	lp->chunks = list_new();
	174	lp->chunks->del = lp_chunk_free;
41397f2e	175	lp_fifo_init(&lp->requests);
955bfd98	176	lp->callback_q = work_queue_new(master, "label callbacks");
955bfd98 PZ	177
	178	lp->callback_q->spec.workfunc = lp_cbq_docallback;
	179	lp->callback_q->spec.del_item_data = lp_cbq_item_free;
	180	lp->callback_q->spec.max_retries = 0;
	181	}
	182
	183	void bgp_lp_finish(void)
	184	{
	185	struct lp_fifo *lf;
	186
	187	if (!lp)
	188	return;
	189
	190	skiplist_free(lp->ledger);
	191	lp->ledger = NULL;
	192
	193	skiplist_free(lp->inuse);
	194	lp->inuse = NULL;
	195
6a154c88	196	list_delete(&lp->chunks);
955bfd98	197
41397f2e	198	while ((lf = lp_fifo_pop(&lp->requests)))
955bfd98	199	XFREE(MTYPE_BGP_LABEL_FIFO, lf);
41397f2e	200	lp_fifo_fini(&lp->requests);
955bfd98 PZ	201
	202	work_queue_free_and_null(&lp->callback_q);
	203
	204	lp = NULL;
	205	}
	206
	207	static mpls_label_t get_label_from_pool(void *labelid)
	208	{
	209	struct listnode *node;
	210	struct lp_chunk *chunk;
	211	int debug = BGP_DEBUG(labelpool, LABELPOOL);
	212
	213	/*
	214	* Find a free label
	215	* Linear search is not efficient but should be executed infrequently.
	216	*/
	217	for (ALL_LIST_ELEMENTS_RO(lp->chunks, node, chunk)) {
	218	uintptr_t lbl;
	219
	220	if (debug)
	221	zlog_debug("%s: chunk first=%u last=%u",
	222	__func__, chunk->first, chunk->last);
	223
	224	for (lbl = chunk->first; lbl <= chunk->last; ++lbl) {
	225	/* labelid is key to all-request "ledger" list */
	226	if (!skiplist_insert(lp->inuse, (void *)lbl, labelid)) {
	227	/*
	228	* Success
	229	*/
	230	return lbl;
	231	}
	232	}
	233	}
	234	return MPLS_LABEL_NONE;
	235	}
	236
	237	/*
	238	* Success indicated by value of "label" field in returned LCB
	239	*/
	240	static struct lp_lcb *lcb_alloc(
	241	int type,
	242	void *labelid,
	243	int (cbfunc)(mpls_label_t label, void labelid, bool allocated))
	244	{
	245	/*
	246	* Set up label control block
	247	*/
	248	struct lp_lcb *new = XCALLOC(MTYPE_BGP_LABEL_CB,
	249	sizeof(struct lp_lcb));
	250
	251	new->label = get_label_from_pool(labelid);
	252	new->type = type;
	253	new->labelid = labelid;
	254	new->cbfunc = cbfunc;
	255
	256	return new;
	257	}
	258
	259	/*
	260	* Callers who need labels must supply a type, labelid, and callback.
	261	* The type is a value defined in bgp_labelpool.h (add types as needed).
	262	* The callback is for asynchronous notification of label allocation.
	263	* The labelid is passed as an argument to the callback. It should be unique
	264	* to the requested label instance.
265	*
266	* If zebra is not connected, callbacks with labels will be delayed
267	* until connection is established. If zebra connection is lost after
268	* labels have been assigned, existing assignments via this labelpool
269	* module will continue until reconnection.
270	*
271	* When connection to zebra is reestablished, previous label assignments
272	* will be invalidated (via callbacks having the "allocated" parameter unset)
273	* and new labels will be automatically reassigned by this labelpool module
274	* (that is, a requestor does not need to call lp_get() again if it is
275	* notified via callback that its label has been lost: it will eventually
276	* get another callback with a new label assignment).
277	*
278	* Prior requests for a given labelid are detected so that requests and
279	* assignments are not duplicated.
280	*/
281	void bgp_lp_get(
282	int type,
283	void *labelid,
284	int (cbfunc)(mpls_label_t label, void labelid, bool allocated))
285	{
286	struct lp_lcb *lcb;
287	int requested = 0;
288	int debug = BGP_DEBUG(labelpool, LABELPOOL);
289
290	if (debug)
291	zlog_debug("%s: labelid=%p", __func__, labelid);
292
293	/*
294	* Have we seen this request before?
295	*/
296	if (!skiplist_search(lp->ledger, labelid, (void **)&lcb)) {
297	requested = 1;
298	} else {
299	lcb = lcb_alloc(type, labelid, cbfunc);
300	if (debug)
301	zlog_debug("%s: inserting lcb=%p label=%u",
302	__func__, lcb, lcb->label);
303	int rc = skiplist_insert(lp->ledger, labelid, lcb);
304
305	if (rc) {
306	/* shouldn't happen */
e50f7cfd	307	flog_err(EC_BGP_LABEL,
1c50c1c0 QY	308	"%s: can't insert new LCB into ledger list",
1c50c1c0 QY	309	__func__);
955bfd98 PZ	310	XFREE(MTYPE_BGP_LABEL_CB, lcb);
	311	return;
	312	}
	313	}
	314
	315	if (lcb->label != MPLS_LABEL_NONE) {
	316	/*
	317	* Fast path: we filled the request from local pool (or
	318	* this is a duplicate request that we filled already).
	319	* Enqueue response work item with new label.
	320	*/
	321	struct lp_cbq_item *q;
	322
	323	q = XCALLOC(MTYPE_BGP_LABEL_CBQ, sizeof(struct lp_cbq_item));
	324
	325	q->cbfunc = lcb->cbfunc;
	326	q->type = lcb->type;
	327	q->label = lcb->label;
	328	q->labelid = lcb->labelid;
	329	q->allocated = true;
	330
	331	work_queue_add(lp->callback_q, q);
	332
	333	return;
	334	}
	335
	336	if (requested)
	337	return;
	338
	339	if (debug)
	340	zlog_debug("%s: slow path. lcb=%p label=%u",
	341	__func__, lcb, lcb->label);
	342
	343	/*
	344	* Slow path: we are out of labels in the local pool,
	345	* so remember the request and also get another chunk from
	346	* the label manager.
	347	*
	348	* We track number of outstanding label requests: don't
	349	* need to get a chunk for each one.
	350	*/
	351
	352	struct lp_fifo *lf = XCALLOC(MTYPE_BGP_LABEL_FIFO,
	353	sizeof(struct lp_fifo));
	354
	355	lf->lcb = *lcb;
41397f2e	356	lp_fifo_add_tail(&lp->requests, lf);
955bfd98	357
41397f2e	358	if (lp_fifo_count(&lp->requests) > lp->pending_count) {
955bfd98 PZ	359	if (!zclient_send_get_label_chunk(zclient, 0, LP_CHUNK_SIZE)) {
	360	lp->pending_count += LP_CHUNK_SIZE;
	361	return;
	362	}
	363	}
	364	}
	365
	366	void bgp_lp_release(
	367	int type,
	368	void *labelid,
	369	mpls_label_t label)
	370	{
	371	struct lp_lcb *lcb;
	372
	373	if (!skiplist_search(lp->ledger, labelid, (void **)&lcb)) {
	374	if (label == lcb->label && type == lcb->type) {
	375	uintptr_t lbl = label;
	376
	377	/* no longer in use */
	378	skiplist_delete(lp->inuse, (void *)lbl, NULL);
	379
	380	/* no longer requested */
	381	skiplist_delete(lp->ledger, labelid, NULL);
	382	}
	383	}
	384	}
	385
	386	/*
	387	* zebra response giving us a chunk of labels
	388	*/
	389	void bgp_lp_event_chunk(uint8_t keep, uint32_t first, uint32_t last)
	390	{
	391	struct lp_chunk *chunk;
	392	int debug = BGP_DEBUG(labelpool, LABELPOOL);
	393	struct lp_fifo *lf;
	394
	395	if (last < first) {
e50f7cfd	396	flog_err(EC_BGP_LABEL,
1c50c1c0 QY	397	"%s: zebra label chunk invalid: first=%u, last=%u",
1c50c1c0 QY	398	__func__, first, last);
955bfd98 PZ	399	return;
	400	}
	401
	402	chunk = XCALLOC(MTYPE_BGP_LABEL_CHUNK, sizeof(struct lp_chunk));
	403
	404	chunk->first = first;
	405	chunk->last = last;
	406
	407	listnode_add(lp->chunks, chunk);
	408
	409	lp->pending_count -= (last - first + 1);
	410
	411	if (debug) {
41397f2e DL	412	zlog_debug("%s: %zu pending requests", __func__,
41397f2e DL	413	lp_fifo_count(&lp->requests));
955bfd98 PZ	414	}
955bfd98 PZ	415
41397f2e	416	while ((lf = lp_fifo_first(&lp->requests))) {
955bfd98 PZ	417
	418	struct lp_lcb *lcb;
	419	void *labelid = lf->lcb.labelid;
	420
	421	if (skiplist_search(lp->ledger, labelid, (void **)&lcb)) {
	422	/* request no longer in effect */
	423
	424	if (debug) {
	425	zlog_debug("%s: labelid %p: request no longer in effect",
	426	__func__, labelid);
	427	}
	428	goto finishedrequest;
	429	}
	430
	431	/* have LCB */
	432	if (lcb->label != MPLS_LABEL_NONE) {
	433	/* request already has a label */
	434	if (debug) {
	435	zlog_debug("%s: labelid %p: request already has a label: %u=0x%x, lcb=%p",
	436	__func__, labelid,
	437	lcb->label, lcb->label, lcb);
	438	}
	439	goto finishedrequest;
	440	}
	441
	442	lcb->label = get_label_from_pool(lcb->labelid);
	443
	444	if (lcb->label == MPLS_LABEL_NONE) {
	445	/*
	446	* Out of labels in local pool, await next chunk
	447	*/
	448	if (debug) {
	449	zlog_debug("%s: out of labels, await more",
	450	__func__);
	451	}
	452	break;
	453	}
	454
	455	/*
	456	* we filled the request from local pool.
	457	* Enqueue response work item with new label.
	458	*/
	459	struct lp_cbq_item *q = XCALLOC(MTYPE_BGP_LABEL_CBQ,
	460	sizeof(struct lp_cbq_item));
	461
	462	q->cbfunc = lcb->cbfunc;
	463	q->type = lcb->type;
	464	q->label = lcb->label;
	465	q->labelid = lcb->labelid;
	466	q->allocated = true;
	467
	468	if (debug)
	469	zlog_debug("%s: assigning label %u to labelid %p",
	470	__func__, q->label, q->labelid);
	471
	472	work_queue_add(lp->callback_q, q);
	473
	474	finishedrequest:
41397f2e	475	lp_fifo_del(&lp->requests, lf);
955bfd98 PZ	476	XFREE(MTYPE_BGP_LABEL_FIFO, lf);
	477	}
	478	}
	479
	480	/*
	481	* continue using allocated labels until zebra returns
	482	*/
	483	void bgp_lp_event_zebra_down(void)
	484	{
	485	/* rats. */
	486	}
	487
	488	/*
	489	* Inform owners of previously-allocated labels that their labels
	490	* are not valid. Request chunk from zebra large enough to satisfy
	491	* previously-allocated labels plus any outstanding requests.
	492	*/
	493	void bgp_lp_event_zebra_up(void)
	494	{
	495	int labels_needed;
	496	int chunks_needed;
	497	void *labelid;
	498	struct lp_lcb *lcb;
f533be73	499	int lm_init_ok;
955bfd98 PZ	500
	501	/*
	502	* Get label chunk allocation request dispatched to zebra
	503	*/
41397f2e	504	labels_needed = lp_fifo_count(&lp->requests) +
955bfd98 PZ	505	skiplist_count(lp->inuse);
	506
	507	/* round up */
	508	chunks_needed = (labels_needed / LP_CHUNK_SIZE) + 1;
	509	labels_needed = chunks_needed * LP_CHUNK_SIZE;
	510
f533be73	511	lm_init_ok = lm_label_manager_connect(zclient, 1) == 0;
	512
	513	if (!lm_init_ok)
	514	zlog_err("%s: label manager connection error", __func__);
	515
955bfd98 PZ	516	zclient_send_get_label_chunk(zclient, 0, labels_needed);
	517	lp->pending_count = labels_needed;
	518
	519	/*
	520	* Invalidate current list of chunks
	521	*/
	522	list_delete_all_node(lp->chunks);
	523
	524	/*
	525	* Invalidate any existing labels and requeue them as requests
	526	*/
	527	while (!skiplist_first(lp->inuse, NULL, &labelid)) {
	528
	529	/*
	530	* Get LCB
	531	*/
	532	if (!skiplist_search(lp->ledger, labelid, (void **)&lcb)) {
	533
	534	if (lcb->label != MPLS_LABEL_NONE) {
	535	/*
	536	* invalidate
	537	*/
	538	struct lp_cbq_item *q;
	539
	540	q = XCALLOC(MTYPE_BGP_LABEL_CBQ,
	541	sizeof(struct lp_cbq_item));
	542	q->cbfunc = lcb->cbfunc;
	543	q->type = lcb->type;
	544	q->label = lcb->label;
	545	q->labelid = lcb->labelid;
	546	q->allocated = false;
	547	work_queue_add(lp->callback_q, q);
	548
	549	lcb->label = MPLS_LABEL_NONE;
	550	}
	551
	552	/*
	553	* request queue
	554	*/
	555	struct lp_fifo *lf = XCALLOC(MTYPE_BGP_LABEL_FIFO,
	556	sizeof(struct lp_fifo));
	557
	558	lf->lcb = *lcb;
41397f2e	559	lp_fifo_add_tail(&lp->requests, lf);
955bfd98 PZ	560	}
	561
	562	skiplist_delete_first(lp->inuse);
	563	}
	564	}