]>
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"
39 * Definitions and external declarations.
41 extern struct zclient
*zclient
;
44 * Remember where pool data are kept
46 static struct labelpool
*lp
;
48 /* request this many labels at a time from zebra */
49 #define LP_CHUNK_SIZE 50
51 DEFINE_MTYPE_STATIC(BGPD
, BGP_LABEL_CHUNK
, "BGP Label Chunk")
52 DEFINE_MTYPE_STATIC(BGPD
, BGP_LABEL_FIFO
, "BGP Label FIFO")
53 DEFINE_MTYPE_STATIC(BGPD
, BGP_LABEL_CB
, "BGP Dynamic Label Assignment")
54 DEFINE_MTYPE_STATIC(BGPD
, BGP_LABEL_CBQ
, "BGP Dynamic Label Callback")
56 #define LABEL_FIFO_ADD(F, N) \
62 #define LABEL_FIFO_DEL(F, N) \
68 #define LABEL_FIFO_INIT(F) \
74 #define LABEL_FIFO_COUNT(F) ((F)->count)
76 #define LABEL_FIFO_EMPTY(F) FIFO_EMPTY(F)
78 #define LABEL_FIFO_HEAD(F) ((F)->next == (F) ? NULL : (F)->next)
89 mpls_label_t label
; /* MPLS_LABEL_NONE = not allocated */
91 void *labelid
; /* unique ID */
93 * callback for label allocation and loss
95 * allocated: false = lost
97 int (*cbfunc
)(mpls_label_t label
, void *lblid
, bool alloc
);
100 /* XXX same first elements as "struct fifo" */
102 struct lp_fifo
*next
;
103 struct lp_fifo
*prev
;
110 int (*cbfunc
)(mpls_label_t label
, void *lblid
, bool alloc
);
114 bool allocated
; /* false = lost */
117 static wq_item_status
lp_cbq_docallback(struct work_queue
*wq
, void *data
)
119 struct lp_cbq_item
*lcbq
= data
;
121 int debug
= BGP_DEBUG(labelpool
, LABELPOOL
);
124 zlog_debug("%s: calling callback with labelid=%p label=%u allocated=%d",
125 __func__
, lcbq
->labelid
, lcbq
->label
, lcbq
->allocated
);
127 if (lcbq
->label
== MPLS_LABEL_NONE
) {
128 /* shouldn't happen */
129 zlog_err("%s: error: label==MPLS_LABEL_NONE", __func__
);
133 rc
= (*(lcbq
->cbfunc
))(lcbq
->label
, lcbq
->labelid
, lcbq
->allocated
);
135 if (lcbq
->allocated
&& rc
) {
137 * Callback rejected allocation. This situation could arise
138 * if there was a label request followed by the requestor
139 * deciding it didn't need the assignment (e.g., config
140 * change) while the reply to the original request (with
141 * label) was in the work queue.
144 zlog_debug("%s: callback rejected allocation, releasing labelid=%p label=%u",
145 __func__
, lcbq
->labelid
, lcbq
->label
);
147 uintptr_t lbl
= lcbq
->label
;
152 * If the rejected label was marked inuse by this labelid,
153 * release the label back to the pool.
155 * Further, if the rejected label was still assigned to
156 * this labelid in the LCB, delete the LCB.
158 if (!skiplist_search(lp
->inuse
, (void *)lbl
, &labelid
)) {
159 if (labelid
== lcbq
->labelid
) {
160 if (!skiplist_search(lp
->ledger
, labelid
,
162 if (lcbq
->label
== lcb
->label
)
163 skiplist_delete(lp
->ledger
,
166 skiplist_delete(lp
->inuse
, (void *)lbl
, NULL
);
174 static void lp_cbq_item_free(struct work_queue
*wq
, void *data
)
176 XFREE(MTYPE_BGP_LABEL_CBQ
, data
);
179 static void lp_lcb_free(void *goner
)
182 XFREE(MTYPE_BGP_LABEL_CB
, goner
);
185 static void lp_chunk_free(void *goner
)
188 XFREE(MTYPE_BGP_LABEL_CHUNK
, goner
);
191 void bgp_lp_init(struct thread_master
*master
, struct labelpool
*pool
)
193 if (BGP_DEBUG(labelpool
, LABELPOOL
))
194 zlog_debug("%s: entry", __func__
);
196 lp
= pool
; /* Set module pointer to pool data */
198 lp
->ledger
= skiplist_new(0, NULL
, lp_lcb_free
);
199 lp
->inuse
= skiplist_new(0, NULL
, NULL
);
200 lp
->chunks
= list_new();
201 lp
->chunks
->del
= lp_chunk_free
;
202 lp
->requests
= XCALLOC(MTYPE_BGP_LABEL_FIFO
, sizeof(struct lp_fifo
));
203 LABEL_FIFO_INIT(lp
->requests
);
204 lp
->callback_q
= work_queue_new(master
, "label callbacks");
205 if (!lp
->callback_q
) {
206 zlog_err("%s: Failed to allocate work queue", __func__
);
210 lp
->callback_q
->spec
.workfunc
= lp_cbq_docallback
;
211 lp
->callback_q
->spec
.del_item_data
= lp_cbq_item_free
;
212 lp
->callback_q
->spec
.max_retries
= 0;
215 void bgp_lp_finish(void)
222 skiplist_free(lp
->ledger
);
225 skiplist_free(lp
->inuse
);
228 list_delete_and_null(&lp
->chunks
);
230 while ((lf
= LABEL_FIFO_HEAD(lp
->requests
))) {
232 LABEL_FIFO_DEL(lp
->requests
, lf
);
233 XFREE(MTYPE_BGP_LABEL_FIFO
, lf
);
235 XFREE(MTYPE_BGP_LABEL_FIFO
, lp
->requests
);
238 work_queue_free_and_null(&lp
->callback_q
);
243 static mpls_label_t
get_label_from_pool(void *labelid
)
245 struct listnode
*node
;
246 struct lp_chunk
*chunk
;
247 int debug
= BGP_DEBUG(labelpool
, LABELPOOL
);
251 * Linear search is not efficient but should be executed infrequently.
253 for (ALL_LIST_ELEMENTS_RO(lp
->chunks
, node
, chunk
)) {
257 zlog_debug("%s: chunk first=%u last=%u",
258 __func__
, chunk
->first
, chunk
->last
);
260 for (lbl
= chunk
->first
; lbl
<= chunk
->last
; ++lbl
) {
261 /* labelid is key to all-request "ledger" list */
262 if (!skiplist_insert(lp
->inuse
, (void *)lbl
, labelid
)) {
270 return MPLS_LABEL_NONE
;
274 * Success indicated by value of "label" field in returned LCB
276 static struct lp_lcb
*lcb_alloc(
279 int (*cbfunc
)(mpls_label_t label
, void *labelid
, bool allocated
))
282 * Set up label control block
284 struct lp_lcb
*new = XCALLOC(MTYPE_BGP_LABEL_CB
,
285 sizeof(struct lp_lcb
));
287 new->label
= get_label_from_pool(labelid
);
289 new->labelid
= labelid
;
290 new->cbfunc
= cbfunc
;
296 * Callers who need labels must supply a type, labelid, and callback.
297 * The type is a value defined in bgp_labelpool.h (add types as needed).
298 * The callback is for asynchronous notification of label allocation.
299 * The labelid is passed as an argument to the callback. It should be unique
300 * to the requested label instance.
302 * If zebra is not connected, callbacks with labels will be delayed
303 * until connection is established. If zebra connection is lost after
304 * labels have been assigned, existing assignments via this labelpool
305 * module will continue until reconnection.
307 * When connection to zebra is reestablished, previous label assignments
308 * will be invalidated (via callbacks having the "allocated" parameter unset)
309 * and new labels will be automatically reassigned by this labelpool module
310 * (that is, a requestor does not need to call lp_get() again if it is
311 * notified via callback that its label has been lost: it will eventually
312 * get another callback with a new label assignment).
314 * Prior requests for a given labelid are detected so that requests and
315 * assignments are not duplicated.
320 int (*cbfunc
)(mpls_label_t label
, void *labelid
, bool allocated
))
324 int debug
= BGP_DEBUG(labelpool
, LABELPOOL
);
327 zlog_debug("%s: labelid=%p", __func__
, labelid
);
330 * Have we seen this request before?
332 if (!skiplist_search(lp
->ledger
, labelid
, (void **)&lcb
)) {
335 lcb
= lcb_alloc(type
, labelid
, cbfunc
);
337 zlog_debug("%s: inserting lcb=%p label=%u",
338 __func__
, lcb
, lcb
->label
);
339 int rc
= skiplist_insert(lp
->ledger
, labelid
, lcb
);
342 /* shouldn't happen */
343 zlog_err("%s: can't insert new LCB into ledger list",
345 XFREE(MTYPE_BGP_LABEL_CB
, lcb
);
350 if (lcb
->label
!= MPLS_LABEL_NONE
) {
352 * Fast path: we filled the request from local pool (or
353 * this is a duplicate request that we filled already).
354 * Enqueue response work item with new label.
356 struct lp_cbq_item
*q
;
358 q
= XCALLOC(MTYPE_BGP_LABEL_CBQ
, sizeof(struct lp_cbq_item
));
360 q
->cbfunc
= lcb
->cbfunc
;
362 q
->label
= lcb
->label
;
363 q
->labelid
= lcb
->labelid
;
366 work_queue_add(lp
->callback_q
, q
);
375 zlog_debug("%s: slow path. lcb=%p label=%u",
376 __func__
, lcb
, lcb
->label
);
379 * Slow path: we are out of labels in the local pool,
380 * so remember the request and also get another chunk from
383 * We track number of outstanding label requests: don't
384 * need to get a chunk for each one.
387 struct lp_fifo
*lf
= XCALLOC(MTYPE_BGP_LABEL_FIFO
,
388 sizeof(struct lp_fifo
));
391 LABEL_FIFO_ADD(lp
->requests
, lf
);
393 if (LABEL_FIFO_COUNT(lp
->requests
) > lp
->pending_count
) {
394 if (!zclient_send_get_label_chunk(zclient
, 0, LP_CHUNK_SIZE
)) {
395 lp
->pending_count
+= LP_CHUNK_SIZE
;
408 if (!skiplist_search(lp
->ledger
, labelid
, (void **)&lcb
)) {
409 if (label
== lcb
->label
&& type
== lcb
->type
) {
410 uintptr_t lbl
= label
;
412 /* no longer in use */
413 skiplist_delete(lp
->inuse
, (void *)lbl
, NULL
);
415 /* no longer requested */
416 skiplist_delete(lp
->ledger
, labelid
, NULL
);
422 * zebra response giving us a chunk of labels
424 void bgp_lp_event_chunk(uint8_t keep
, uint32_t first
, uint32_t last
)
426 struct lp_chunk
*chunk
;
427 int debug
= BGP_DEBUG(labelpool
, LABELPOOL
);
431 zlog_err("%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
);