]>
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(EC_BGP_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
)
183 XFREE(MTYPE_BGP_LABEL_CB
, goner
);
186 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");
206 lp
->callback_q
->spec
.workfunc
= lp_cbq_docallback
;
207 lp
->callback_q
->spec
.del_item_data
= lp_cbq_item_free
;
208 lp
->callback_q
->spec
.max_retries
= 0;
211 void bgp_lp_finish(void)
218 skiplist_free(lp
->ledger
);
221 skiplist_free(lp
->inuse
);
224 list_delete(&lp
->chunks
);
226 while ((lf
= LABEL_FIFO_HEAD(lp
->requests
))) {
228 LABEL_FIFO_DEL(lp
->requests
, lf
);
229 XFREE(MTYPE_BGP_LABEL_FIFO
, lf
);
231 XFREE(MTYPE_BGP_LABEL_FIFO
, lp
->requests
);
234 work_queue_free_and_null(&lp
->callback_q
);
239 static mpls_label_t
get_label_from_pool(void *labelid
)
241 struct listnode
*node
;
242 struct lp_chunk
*chunk
;
243 int debug
= BGP_DEBUG(labelpool
, LABELPOOL
);
247 * Linear search is not efficient but should be executed infrequently.
249 for (ALL_LIST_ELEMENTS_RO(lp
->chunks
, node
, chunk
)) {
253 zlog_debug("%s: chunk first=%u last=%u",
254 __func__
, chunk
->first
, chunk
->last
);
256 for (lbl
= chunk
->first
; lbl
<= chunk
->last
; ++lbl
) {
257 /* labelid is key to all-request "ledger" list */
258 if (!skiplist_insert(lp
->inuse
, (void *)lbl
, labelid
)) {
266 return MPLS_LABEL_NONE
;
270 * Success indicated by value of "label" field in returned LCB
272 static struct lp_lcb
*lcb_alloc(
275 int (*cbfunc
)(mpls_label_t label
, void *labelid
, bool allocated
))
278 * Set up label control block
280 struct lp_lcb
*new = XCALLOC(MTYPE_BGP_LABEL_CB
,
281 sizeof(struct lp_lcb
));
283 new->label
= get_label_from_pool(labelid
);
285 new->labelid
= labelid
;
286 new->cbfunc
= cbfunc
;
292 * Callers who need labels must supply a type, labelid, and callback.
293 * The type is a value defined in bgp_labelpool.h (add types as needed).
294 * The callback is for asynchronous notification of label allocation.
295 * The labelid is passed as an argument to the callback. It should be unique
296 * to the requested label instance.
298 * If zebra is not connected, callbacks with labels will be delayed
299 * until connection is established. If zebra connection is lost after
300 * labels have been assigned, existing assignments via this labelpool
301 * module will continue until reconnection.
303 * When connection to zebra is reestablished, previous label assignments
304 * will be invalidated (via callbacks having the "allocated" parameter unset)
305 * and new labels will be automatically reassigned by this labelpool module
306 * (that is, a requestor does not need to call lp_get() again if it is
307 * notified via callback that its label has been lost: it will eventually
308 * get another callback with a new label assignment).
310 * Prior requests for a given labelid are detected so that requests and
311 * assignments are not duplicated.
316 int (*cbfunc
)(mpls_label_t label
, void *labelid
, bool allocated
))
320 int debug
= BGP_DEBUG(labelpool
, LABELPOOL
);
323 zlog_debug("%s: labelid=%p", __func__
, labelid
);
326 * Have we seen this request before?
328 if (!skiplist_search(lp
->ledger
, labelid
, (void **)&lcb
)) {
331 lcb
= lcb_alloc(type
, labelid
, cbfunc
);
333 zlog_debug("%s: inserting lcb=%p label=%u",
334 __func__
, lcb
, lcb
->label
);
335 int rc
= skiplist_insert(lp
->ledger
, labelid
, lcb
);
338 /* shouldn't happen */
339 flog_err(EC_BGP_LABEL
,
340 "%s: can't insert new LCB into ledger list",
342 XFREE(MTYPE_BGP_LABEL_CB
, lcb
);
347 if (lcb
->label
!= MPLS_LABEL_NONE
) {
349 * Fast path: we filled the request from local pool (or
350 * this is a duplicate request that we filled already).
351 * Enqueue response work item with new label.
353 struct lp_cbq_item
*q
;
355 q
= XCALLOC(MTYPE_BGP_LABEL_CBQ
, sizeof(struct lp_cbq_item
));
357 q
->cbfunc
= lcb
->cbfunc
;
359 q
->label
= lcb
->label
;
360 q
->labelid
= lcb
->labelid
;
363 work_queue_add(lp
->callback_q
, q
);
372 zlog_debug("%s: slow path. lcb=%p label=%u",
373 __func__
, lcb
, lcb
->label
);
376 * Slow path: we are out of labels in the local pool,
377 * so remember the request and also get another chunk from
380 * We track number of outstanding label requests: don't
381 * need to get a chunk for each one.
384 struct lp_fifo
*lf
= XCALLOC(MTYPE_BGP_LABEL_FIFO
,
385 sizeof(struct lp_fifo
));
388 LABEL_FIFO_ADD(lp
->requests
, lf
);
390 if (LABEL_FIFO_COUNT(lp
->requests
) > lp
->pending_count
) {
391 if (!zclient_send_get_label_chunk(zclient
, 0, LP_CHUNK_SIZE
)) {
392 lp
->pending_count
+= LP_CHUNK_SIZE
;
405 if (!skiplist_search(lp
->ledger
, labelid
, (void **)&lcb
)) {
406 if (label
== lcb
->label
&& type
== lcb
->type
) {
407 uintptr_t lbl
= label
;
409 /* no longer in use */
410 skiplist_delete(lp
->inuse
, (void *)lbl
, NULL
);
412 /* no longer requested */
413 skiplist_delete(lp
->ledger
, labelid
, NULL
);
419 * zebra response giving us a chunk of labels
421 void bgp_lp_event_chunk(uint8_t keep
, uint32_t first
, uint32_t last
)
423 struct lp_chunk
*chunk
;
424 int debug
= BGP_DEBUG(labelpool
, LABELPOOL
);
428 flog_err(EC_BGP_LABEL
,
429 "%s: zebra label chunk invalid: first=%u, last=%u",
430 __func__
, first
, last
);
434 chunk
= XCALLOC(MTYPE_BGP_LABEL_CHUNK
, sizeof(struct lp_chunk
));
436 chunk
->first
= first
;
439 listnode_add(lp
->chunks
, chunk
);
441 lp
->pending_count
-= (last
- first
+ 1);
444 zlog_debug("%s: %u pending requests", __func__
,
445 LABEL_FIFO_COUNT(lp
->requests
));
448 while ((lf
= LABEL_FIFO_HEAD(lp
->requests
))) {
451 void *labelid
= lf
->lcb
.labelid
;
453 if (skiplist_search(lp
->ledger
, labelid
, (void **)&lcb
)) {
454 /* request no longer in effect */
457 zlog_debug("%s: labelid %p: request no longer in effect",
460 goto finishedrequest
;
464 if (lcb
->label
!= MPLS_LABEL_NONE
) {
465 /* request already has a label */
467 zlog_debug("%s: labelid %p: request already has a label: %u=0x%x, lcb=%p",
469 lcb
->label
, lcb
->label
, lcb
);
471 goto finishedrequest
;
474 lcb
->label
= get_label_from_pool(lcb
->labelid
);
476 if (lcb
->label
== MPLS_LABEL_NONE
) {
478 * Out of labels in local pool, await next chunk
481 zlog_debug("%s: out of labels, await more",
488 * we filled the request from local pool.
489 * Enqueue response work item with new label.
491 struct lp_cbq_item
*q
= XCALLOC(MTYPE_BGP_LABEL_CBQ
,
492 sizeof(struct lp_cbq_item
));
494 q
->cbfunc
= lcb
->cbfunc
;
496 q
->label
= lcb
->label
;
497 q
->labelid
= lcb
->labelid
;
501 zlog_debug("%s: assigning label %u to labelid %p",
502 __func__
, q
->label
, q
->labelid
);
504 work_queue_add(lp
->callback_q
, q
);
507 LABEL_FIFO_DEL(lp
->requests
, lf
);
508 XFREE(MTYPE_BGP_LABEL_FIFO
, lf
);
513 * continue using allocated labels until zebra returns
515 void bgp_lp_event_zebra_down(void)
521 * Inform owners of previously-allocated labels that their labels
522 * are not valid. Request chunk from zebra large enough to satisfy
523 * previously-allocated labels plus any outstanding requests.
525 void bgp_lp_event_zebra_up(void)
534 * Get label chunk allocation request dispatched to zebra
536 labels_needed
= LABEL_FIFO_COUNT(lp
->requests
) +
537 skiplist_count(lp
->inuse
);
540 chunks_needed
= (labels_needed
/ LP_CHUNK_SIZE
) + 1;
541 labels_needed
= chunks_needed
* LP_CHUNK_SIZE
;
543 lm_init_ok
= lm_label_manager_connect(zclient
, 1) == 0;
546 zlog_err("%s: label manager connection error", __func__
);
548 zclient_send_get_label_chunk(zclient
, 0, labels_needed
);
549 lp
->pending_count
= labels_needed
;
552 * Invalidate current list of chunks
554 list_delete_all_node(lp
->chunks
);
557 * Invalidate any existing labels and requeue them as requests
559 while (!skiplist_first(lp
->inuse
, NULL
, &labelid
)) {
564 if (!skiplist_search(lp
->ledger
, labelid
, (void **)&lcb
)) {
566 if (lcb
->label
!= MPLS_LABEL_NONE
) {
570 struct lp_cbq_item
*q
;
572 q
= XCALLOC(MTYPE_BGP_LABEL_CBQ
,
573 sizeof(struct lp_cbq_item
));
574 q
->cbfunc
= lcb
->cbfunc
;
576 q
->label
= lcb
->label
;
577 q
->labelid
= lcb
->labelid
;
578 q
->allocated
= false;
579 work_queue_add(lp
->callback_q
, q
);
581 lcb
->label
= MPLS_LABEL_NONE
;
587 struct lp_fifo
*lf
= XCALLOC(MTYPE_BGP_LABEL_FIFO
,
588 sizeof(struct lp_fifo
));
591 LABEL_FIFO_ADD(lp
->requests
, lf
);
594 skiplist_delete_first(lp
->inuse
);