]>
git.proxmox.com Git - mirror_frr.git/blob - bgpd/bgp_labelpool.c
2 * BGP Label Pool - Manage label chunk allocations from zebra asynchronously
4 * Copyright (C) 2018 LabN Consulting, L.L.C.
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)
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
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
31 #include "workqueue.h"
34 #include "bgpd/bgpd.h"
35 #include "bgpd/bgp_labelpool.h"
36 #include "bgpd/bgp_debug.h"
37 #include "bgpd/bgp_errors.h"
40 * Definitions and external declarations.
42 extern struct zclient
*zclient
;
45 * Remember where pool data are kept
47 static struct labelpool
*lp
;
49 /* request this many labels at a time from zebra */
50 #define LP_CHUNK_SIZE 50
52 DEFINE_MTYPE_STATIC(BGPD
, BGP_LABEL_CHUNK
, "BGP Label Chunk")
53 DEFINE_MTYPE_STATIC(BGPD
, BGP_LABEL_FIFO
, "BGP Label FIFO")
54 DEFINE_MTYPE_STATIC(BGPD
, BGP_LABEL_CB
, "BGP Dynamic Label Assignment")
55 DEFINE_MTYPE_STATIC(BGPD
, BGP_LABEL_CBQ
, "BGP Dynamic Label Callback")
57 #define LABEL_FIFO_ADD(F, N) \
63 #define LABEL_FIFO_DEL(F, N) \
69 #define LABEL_FIFO_INIT(F) \
75 #define LABEL_FIFO_COUNT(F) ((F)->count)
77 #define LABEL_FIFO_EMPTY(F) FIFO_EMPTY(F)
79 #define LABEL_FIFO_HEAD(F) ((F)->next == (F) ? NULL : (F)->next)
90 mpls_label_t label
; /* MPLS_LABEL_NONE = not allocated */
92 void *labelid
; /* unique ID */
94 * callback for label allocation and loss
96 * allocated: false = lost
98 int (*cbfunc
)(mpls_label_t label
, void *lblid
, bool alloc
);
101 /* XXX same first elements as "struct fifo" */
103 struct lp_fifo
*next
;
104 struct lp_fifo
*prev
;
111 int (*cbfunc
)(mpls_label_t label
, void *lblid
, bool alloc
);
115 bool allocated
; /* false = lost */
118 static wq_item_status
lp_cbq_docallback(struct work_queue
*wq
, void *data
)
120 struct lp_cbq_item
*lcbq
= data
;
122 int debug
= BGP_DEBUG(labelpool
, LABELPOOL
);
125 zlog_debug("%s: calling callback with labelid=%p label=%u allocated=%d",
126 __func__
, lcbq
->labelid
, lcbq
->label
, lcbq
->allocated
);
128 if (lcbq
->label
== MPLS_LABEL_NONE
) {
129 /* shouldn't happen */
130 flog_err(BGP_ERR_LABEL
, "%s: error: label==MPLS_LABEL_NONE",
135 rc
= (*(lcbq
->cbfunc
))(lcbq
->label
, lcbq
->labelid
, lcbq
->allocated
);
137 if (lcbq
->allocated
&& rc
) {
139 * Callback rejected allocation. This situation could arise
140 * if there was a label request followed by the requestor
141 * deciding it didn't need the assignment (e.g., config
142 * change) while the reply to the original request (with
143 * label) was in the work queue.
146 zlog_debug("%s: callback rejected allocation, releasing labelid=%p label=%u",
147 __func__
, lcbq
->labelid
, lcbq
->label
);
149 uintptr_t lbl
= lcbq
->label
;
154 * If the rejected label was marked inuse by this labelid,
155 * release the label back to the pool.
157 * Further, if the rejected label was still assigned to
158 * this labelid in the LCB, delete the LCB.
160 if (!skiplist_search(lp
->inuse
, (void *)lbl
, &labelid
)) {
161 if (labelid
== lcbq
->labelid
) {
162 if (!skiplist_search(lp
->ledger
, labelid
,
164 if (lcbq
->label
== lcb
->label
)
165 skiplist_delete(lp
->ledger
,
168 skiplist_delete(lp
->inuse
, (void *)lbl
, NULL
);
176 static void lp_cbq_item_free(struct work_queue
*wq
, void *data
)
178 XFREE(MTYPE_BGP_LABEL_CBQ
, data
);
181 static void lp_lcb_free(void *goner
)
184 XFREE(MTYPE_BGP_LABEL_CB
, goner
);
187 static void lp_chunk_free(void *goner
)
190 XFREE(MTYPE_BGP_LABEL_CHUNK
, goner
);
193 void bgp_lp_init(struct thread_master
*master
, struct labelpool
*pool
)
195 if (BGP_DEBUG(labelpool
, LABELPOOL
))
196 zlog_debug("%s: entry", __func__
);
198 lp
= pool
; /* Set module pointer to pool data */
200 lp
->ledger
= skiplist_new(0, NULL
, lp_lcb_free
);
201 lp
->inuse
= skiplist_new(0, NULL
, NULL
);
202 lp
->chunks
= list_new();
203 lp
->chunks
->del
= lp_chunk_free
;
204 lp
->requests
= XCALLOC(MTYPE_BGP_LABEL_FIFO
, sizeof(struct lp_fifo
));
205 LABEL_FIFO_INIT(lp
->requests
);
206 lp
->callback_q
= work_queue_new(master
, "label callbacks");
208 lp
->callback_q
->spec
.workfunc
= lp_cbq_docallback
;
209 lp
->callback_q
->spec
.del_item_data
= lp_cbq_item_free
;
210 lp
->callback_q
->spec
.max_retries
= 0;
213 void bgp_lp_finish(void)
220 skiplist_free(lp
->ledger
);
223 skiplist_free(lp
->inuse
);
226 list_delete_and_null(&lp
->chunks
);
228 while ((lf
= LABEL_FIFO_HEAD(lp
->requests
))) {
230 LABEL_FIFO_DEL(lp
->requests
, lf
);
231 XFREE(MTYPE_BGP_LABEL_FIFO
, lf
);
233 XFREE(MTYPE_BGP_LABEL_FIFO
, lp
->requests
);
236 work_queue_free_and_null(&lp
->callback_q
);
241 static mpls_label_t
get_label_from_pool(void *labelid
)
243 struct listnode
*node
;
244 struct lp_chunk
*chunk
;
245 int debug
= BGP_DEBUG(labelpool
, LABELPOOL
);
249 * Linear search is not efficient but should be executed infrequently.
251 for (ALL_LIST_ELEMENTS_RO(lp
->chunks
, node
, chunk
)) {
255 zlog_debug("%s: chunk first=%u last=%u",
256 __func__
, chunk
->first
, chunk
->last
);
258 for (lbl
= chunk
->first
; lbl
<= chunk
->last
; ++lbl
) {
259 /* labelid is key to all-request "ledger" list */
260 if (!skiplist_insert(lp
->inuse
, (void *)lbl
, labelid
)) {
268 return MPLS_LABEL_NONE
;
272 * Success indicated by value of "label" field in returned LCB
274 static struct lp_lcb
*lcb_alloc(
277 int (*cbfunc
)(mpls_label_t label
, void *labelid
, bool allocated
))
280 * Set up label control block
282 struct lp_lcb
*new = XCALLOC(MTYPE_BGP_LABEL_CB
,
283 sizeof(struct lp_lcb
));
285 new->label
= get_label_from_pool(labelid
);
287 new->labelid
= labelid
;
288 new->cbfunc
= cbfunc
;
294 * Callers who need labels must supply a type, labelid, and callback.
295 * The type is a value defined in bgp_labelpool.h (add types as needed).
296 * The callback is for asynchronous notification of label allocation.
297 * The labelid is passed as an argument to the callback. It should be unique
298 * to the requested label instance.
300 * If zebra is not connected, callbacks with labels will be delayed
301 * until connection is established. If zebra connection is lost after
302 * labels have been assigned, existing assignments via this labelpool
303 * module will continue until reconnection.
305 * When connection to zebra is reestablished, previous label assignments
306 * will be invalidated (via callbacks having the "allocated" parameter unset)
307 * and new labels will be automatically reassigned by this labelpool module
308 * (that is, a requestor does not need to call lp_get() again if it is
309 * notified via callback that its label has been lost: it will eventually
310 * get another callback with a new label assignment).
312 * Prior requests for a given labelid are detected so that requests and
313 * assignments are not duplicated.
318 int (*cbfunc
)(mpls_label_t label
, void *labelid
, bool allocated
))
322 int debug
= BGP_DEBUG(labelpool
, LABELPOOL
);
325 zlog_debug("%s: labelid=%p", __func__
, labelid
);
328 * Have we seen this request before?
330 if (!skiplist_search(lp
->ledger
, labelid
, (void **)&lcb
)) {
333 lcb
= lcb_alloc(type
, labelid
, cbfunc
);
335 zlog_debug("%s: inserting lcb=%p label=%u",
336 __func__
, lcb
, lcb
->label
);
337 int rc
= skiplist_insert(lp
->ledger
, labelid
, lcb
);
340 /* shouldn't happen */
341 flog_err(BGP_ERR_LABEL
,
342 "%s: can't insert new LCB into ledger list",
344 XFREE(MTYPE_BGP_LABEL_CB
, lcb
);
349 if (lcb
->label
!= MPLS_LABEL_NONE
) {
351 * Fast path: we filled the request from local pool (or
352 * this is a duplicate request that we filled already).
353 * Enqueue response work item with new label.
355 struct lp_cbq_item
*q
;
357 q
= XCALLOC(MTYPE_BGP_LABEL_CBQ
, sizeof(struct lp_cbq_item
));
359 q
->cbfunc
= lcb
->cbfunc
;
361 q
->label
= lcb
->label
;
362 q
->labelid
= lcb
->labelid
;
365 work_queue_add(lp
->callback_q
, q
);
374 zlog_debug("%s: slow path. lcb=%p label=%u",
375 __func__
, lcb
, lcb
->label
);
378 * Slow path: we are out of labels in the local pool,
379 * so remember the request and also get another chunk from
382 * We track number of outstanding label requests: don't
383 * need to get a chunk for each one.
386 struct lp_fifo
*lf
= XCALLOC(MTYPE_BGP_LABEL_FIFO
,
387 sizeof(struct lp_fifo
));
390 LABEL_FIFO_ADD(lp
->requests
, lf
);
392 if (LABEL_FIFO_COUNT(lp
->requests
) > lp
->pending_count
) {
393 if (!zclient_send_get_label_chunk(zclient
, 0, LP_CHUNK_SIZE
)) {
394 lp
->pending_count
+= LP_CHUNK_SIZE
;
407 if (!skiplist_search(lp
->ledger
, labelid
, (void **)&lcb
)) {
408 if (label
== lcb
->label
&& type
== lcb
->type
) {
409 uintptr_t lbl
= label
;
411 /* no longer in use */
412 skiplist_delete(lp
->inuse
, (void *)lbl
, NULL
);
414 /* no longer requested */
415 skiplist_delete(lp
->ledger
, labelid
, NULL
);
421 * zebra response giving us a chunk of labels
423 void bgp_lp_event_chunk(uint8_t keep
, uint32_t first
, uint32_t last
)
425 struct lp_chunk
*chunk
;
426 int debug
= BGP_DEBUG(labelpool
, LABELPOOL
);
430 flog_err(BGP_ERR_LABEL
,
431 "%s: zebra label chunk invalid: first=%u, last=%u",
432 __func__
, first
, last
);
436 chunk
= XCALLOC(MTYPE_BGP_LABEL_CHUNK
, sizeof(struct lp_chunk
));
438 chunk
->first
= first
;
441 listnode_add(lp
->chunks
, chunk
);
443 lp
->pending_count
-= (last
- first
+ 1);
446 zlog_debug("%s: %u pending requests", __func__
,
447 LABEL_FIFO_COUNT(lp
->requests
));
450 while ((lf
= LABEL_FIFO_HEAD(lp
->requests
))) {
453 void *labelid
= lf
->lcb
.labelid
;
455 if (skiplist_search(lp
->ledger
, labelid
, (void **)&lcb
)) {
456 /* request no longer in effect */
459 zlog_debug("%s: labelid %p: request no longer in effect",
462 goto finishedrequest
;
466 if (lcb
->label
!= MPLS_LABEL_NONE
) {
467 /* request already has a label */
469 zlog_debug("%s: labelid %p: request already has a label: %u=0x%x, lcb=%p",
471 lcb
->label
, lcb
->label
, lcb
);
473 goto finishedrequest
;
476 lcb
->label
= get_label_from_pool(lcb
->labelid
);
478 if (lcb
->label
== MPLS_LABEL_NONE
) {
480 * Out of labels in local pool, await next chunk
483 zlog_debug("%s: out of labels, await more",
490 * we filled the request from local pool.
491 * Enqueue response work item with new label.
493 struct lp_cbq_item
*q
= XCALLOC(MTYPE_BGP_LABEL_CBQ
,
494 sizeof(struct lp_cbq_item
));
496 q
->cbfunc
= lcb
->cbfunc
;
498 q
->label
= lcb
->label
;
499 q
->labelid
= lcb
->labelid
;
503 zlog_debug("%s: assigning label %u to labelid %p",
504 __func__
, q
->label
, q
->labelid
);
506 work_queue_add(lp
->callback_q
, q
);
509 LABEL_FIFO_DEL(lp
->requests
, lf
);
510 XFREE(MTYPE_BGP_LABEL_FIFO
, lf
);
515 * continue using allocated labels until zebra returns
517 void bgp_lp_event_zebra_down(void)
523 * Inform owners of previously-allocated labels that their labels
524 * are not valid. Request chunk from zebra large enough to satisfy
525 * previously-allocated labels plus any outstanding requests.
527 void bgp_lp_event_zebra_up(void)
535 * Get label chunk allocation request dispatched to zebra
537 labels_needed
= LABEL_FIFO_COUNT(lp
->requests
) +
538 skiplist_count(lp
->inuse
);
541 chunks_needed
= (labels_needed
/ LP_CHUNK_SIZE
) + 1;
542 labels_needed
= chunks_needed
* LP_CHUNK_SIZE
;
544 zclient_send_get_label_chunk(zclient
, 0, labels_needed
);
545 lp
->pending_count
= labels_needed
;
548 * Invalidate current list of chunks
550 list_delete_all_node(lp
->chunks
);
553 * Invalidate any existing labels and requeue them as requests
555 while (!skiplist_first(lp
->inuse
, NULL
, &labelid
)) {
560 if (!skiplist_search(lp
->ledger
, labelid
, (void **)&lcb
)) {
562 if (lcb
->label
!= MPLS_LABEL_NONE
) {
566 struct lp_cbq_item
*q
;
568 q
= XCALLOC(MTYPE_BGP_LABEL_CBQ
,
569 sizeof(struct lp_cbq_item
));
570 q
->cbfunc
= lcb
->cbfunc
;
572 q
->label
= lcb
->label
;
573 q
->labelid
= lcb
->labelid
;
574 q
->allocated
= false;
575 work_queue_add(lp
->callback_q
, q
);
577 lcb
->label
= MPLS_LABEL_NONE
;
583 struct lp_fifo
*lf
= XCALLOC(MTYPE_BGP_LABEL_FIFO
,
584 sizeof(struct lp_fifo
));
587 LABEL_FIFO_ADD(lp
->requests
, lf
);
590 skiplist_delete_first(lp
->inuse
);