From aac2483887eddfe782a31f03b5a30643793935f5 Mon Sep 17 00:00:00 2001 From: Jorge Boncompte Date: Sat, 5 Aug 2017 12:59:05 +0200 Subject: [PATCH] bgpd: bgp process queue optimization There are several code paths that dump nodes to the queue for route processing in a loop. This patch tries to reduce memory allocations/freeing (work item, list node) and thread scheduling overhead by batching the nodes in a simple queue list. In the past when route processing wasn't event driven (bgp_scan()), this used to have a noticeable impact in table loading, convergence time and memory heap fragmentation due to reduced alloc's/free's. Signed-off-by: Jorge Boncompte --- bgpd/bgp_route.c | 116 +++++++++++++++++++++++++++++++---------------- bgpd/bgp_table.h | 3 ++ 2 files changed, 80 insertions(+), 39 deletions(-) diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c index 741fa5ceeb..bb204b01f1 100644 --- a/bgpd/bgp_route.c +++ b/bgpd/bgp_route.c @@ -2001,18 +2001,15 @@ int bgp_zebra_has_route_changed(struct bgp_node *rn, struct bgp_info *selected) struct bgp_process_queue { struct bgp *bgp; - struct bgp_node *rn; - afi_t afi; - safi_t safi; + STAILQ_HEAD(, bgp_node)pqueue; +#define BGP_PROCESS_QUEUE_EOIU_MARKER (1 << 0) + unsigned int flags; + unsigned int queued; }; -static wq_item_status bgp_process_main(struct work_queue *wq, void *data) +static void bgp_process_main_one(struct bgp *bgp, struct bgp_node *rn, + afi_t afi, safi_t safi) { - struct bgp_process_queue *pq = data; - struct bgp *bgp = pq->bgp; - struct bgp_node *rn = pq->rn; - afi_t afi = pq->afi; - safi_t safi = pq->safi; struct prefix *p = &rn->p; struct bgp_info *new_select; struct bgp_info *old_select; @@ -2033,7 +2030,7 @@ static wq_item_status bgp_process_main(struct work_queue *wq, void *data) bgp->main_peers_update_hold = 0; bgp_start_routeadv(bgp); - return WQ_SUCCESS; + return; } /* Best path selection. */ @@ -2114,7 +2111,7 @@ static wq_item_status bgp_process_main(struct work_queue *wq, void *data) } UNSET_FLAG(rn->flags, BGP_NODE_PROCESS_SCHEDULED); - return WQ_SUCCESS; + return; } /* If the user did "clear ip bgp prefix x.x.x.x" this flag will be set @@ -2192,21 +2189,42 @@ static wq_item_status bgp_process_main(struct work_queue *wq, void *data) bgp_info_reap(rn, old_select); UNSET_FLAG(rn->flags, BGP_NODE_PROCESS_SCHEDULED); - return WQ_SUCCESS; + return; } -static void bgp_processq_del(struct work_queue *wq, void *data) +static wq_item_status bgp_process_wq(struct work_queue *wq, void *data) { - struct bgp_process_queue *pq = data; + struct bgp_process_queue *pqnode = data; + struct bgp *bgp = pqnode->bgp; struct bgp_table *table; + struct bgp_node *rn, *nrn; + + /* eoiu marker */ + if (CHECK_FLAG(pqnode->flags, BGP_PROCESS_QUEUE_EOIU_MARKER)) { + bgp_process_main_one(bgp, NULL, 0, 0); - bgp_unlock(pq->bgp); - if (pq->rn) { - table = bgp_node_table(pq->rn); - bgp_unlock_node(pq->rn); + return WQ_SUCCESS; + } + + STAILQ_FOREACH_SAFE(rn, &pqnode->pqueue, pq, nrn) { + table = bgp_node_table(rn); + + bgp_process_main_one(bgp, rn, table->afi, table->safi); + + bgp_unlock_node(rn); bgp_table_unlock(table); } - XFREE(MTYPE_BGP_PROCESS_QUEUE, pq); + + return WQ_SUCCESS; +} + +static void bgp_processq_del(struct work_queue *wq, void *data) +{ + struct bgp_process_queue *pqnode = data; + + bgp_unlock(pqnode->bgp); + + XFREE(MTYPE_BGP_PROCESS_QUEUE, pqnode); } void bgp_process_queue_init(void) @@ -2221,7 +2239,7 @@ void bgp_process_queue_init(void) } } - bm->process_main_queue->spec.workfunc = &bgp_process_main; + bm->process_main_queue->spec.workfunc = &bgp_process_wq; bm->process_main_queue->spec.del_item_data = &bgp_processq_del; bm->process_main_queue->spec.max_retries = 0; bm->process_main_queue->spec.hold = 50; @@ -2229,30 +2247,56 @@ void bgp_process_queue_init(void) bm->process_main_queue->spec.yield = 50 * 1000L; } +static struct bgp_process_queue *bgp_process_queue_work(struct work_queue *wq, + struct bgp *bgp) +{ + struct bgp_process_queue *pqnode; + + pqnode = XCALLOC(MTYPE_BGP_PROCESS_QUEUE, sizeof(struct bgp_process_queue)); + + /* unlocked in bgp_processq_del */ + pqnode->bgp = bgp_lock(bgp); + STAILQ_INIT(&pqnode->pqueue); + + work_queue_add(wq, pqnode); + + return pqnode; +} + void bgp_process(struct bgp *bgp, struct bgp_node *rn, afi_t afi, safi_t safi) { +#define ARBITRARY_PROCESS_QLEN 10000 + struct work_queue *wq = bm->process_main_queue; struct bgp_process_queue *pqnode; /* already scheduled for processing? */ if (CHECK_FLAG(rn->flags, BGP_NODE_PROCESS_SCHEDULED)) return; - if (bm->process_main_queue == NULL) + if (wq == NULL) return; - pqnode = XCALLOC(MTYPE_BGP_PROCESS_QUEUE, - sizeof(struct bgp_process_queue)); - if (!pqnode) - return; + /* Add route nodes to an existing work queue item until reaching the + limit only if is from the same BGP view and it's not an EOIU marker */ + if (work_queue_item_count(wq)) { + struct work_queue_item *item = work_queue_last_item(wq); + pqnode = item->data; - /* all unlocked in bgp_processq_del */ + if (CHECK_FLAG(pqnode->flags, BGP_PROCESS_QUEUE_EOIU_MARKER) || + pqnode->bgp != bgp || pqnode->queued >= ARBITRARY_PROCESS_QLEN) + pqnode = bgp_process_queue_work(wq, bgp); + } else + pqnode = bgp_process_queue_work(wq, bgp); + + /* all unlocked in bgp_process_wq */ bgp_table_lock(bgp_node_table(rn)); - pqnode->rn = bgp_lock_node(rn); - pqnode->bgp = bgp_lock(bgp); - pqnode->afi = afi; - pqnode->safi = safi; - work_queue_add(bm->process_main_queue, pqnode); + SET_FLAG(rn->flags, BGP_NODE_PROCESS_SCHEDULED); + bgp_lock_node(rn); + + STAILQ_INSERT_TAIL(&pqnode->pqueue, rn, pq); + pqnode->queued++; + return; } @@ -2263,15 +2307,9 @@ void bgp_add_eoiu_mark(struct bgp *bgp) if (bm->process_main_queue == NULL) return; - pqnode = XCALLOC(MTYPE_BGP_PROCESS_QUEUE, - sizeof(struct bgp_process_queue)); - if (!pqnode) - return; + pqnode = bgp_process_queue_work(bm->process_main_queue, bgp); - pqnode->rn = NULL; - pqnode->bgp = bgp; - bgp_lock(bgp); - work_queue_add(bm->process_main_queue, pqnode); + SET_FLAG(pqnode->flags, BGP_PROCESS_QUEUE_EOIU_MARKER); } static int bgp_maximum_prefix_restart_timer(struct thread *thread) diff --git a/bgpd/bgp_table.h b/bgpd/bgp_table.h index 0d5706f7cb..a4f3b604c2 100644 --- a/bgpd/bgp_table.h +++ b/bgpd/bgp_table.h @@ -23,6 +23,7 @@ #include "mpls.h" #include "table.h" +#include "queue.h" struct bgp_table { /* afi/safi of this table */ @@ -52,6 +53,8 @@ struct bgp_node { struct bgp_node *prn; + STAILQ_ENTRY(bgp_node) pq; + mpls_label_t local_label; uint64_t version; -- 2.39.5