From b900620c33fbabab5c84d6791e40c856f4854a10 Mon Sep 17 00:00:00 2001 From: claudio Date: Fri, 10 Mar 2023 07:57:15 +0000 Subject: [PATCH] Compile the output filter rules into per peer filter rules. especially on route-servers the output filters are in the hot path so reducing the number of rules to check has a big impact. I have seen a 25% to 30% speedup in my big IXP testbench. The output ruleset is applied and copied for each peer during config reload and when a peer is initially added. OK tb@ --- usr.sbin/bgpd/bgpd.h | 7 +++-- usr.sbin/bgpd/rde.c | 49 ++++++++++++++++----------------- usr.sbin/bgpd/rde.h | 29 ++++++++++---------- usr.sbin/bgpd/rde_filter.c | 29 +++++++------------- usr.sbin/bgpd/rde_peer.c | 55 +++++++++++++++++++++++++++++--------- usr.sbin/bgpd/rde_update.c | 36 +++++++++++-------------- 6 files changed, 107 insertions(+), 98 deletions(-) diff --git a/usr.sbin/bgpd/bgpd.h b/usr.sbin/bgpd/bgpd.h index af2f67509e2..dc65a2bc082 100644 --- a/usr.sbin/bgpd/bgpd.h +++ b/usr.sbin/bgpd/bgpd.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bgpd.h,v 1.463 2023/03/09 17:21:21 claudio Exp $ */ +/* $OpenBSD: bgpd.h,v 1.464 2023/03/10 07:57:15 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer @@ -1111,11 +1111,10 @@ struct filter_rule { struct filter_peers peer; struct filter_match match; struct filter_set_head set; -#define RDE_FILTER_SKIP_DIR 0 +#define RDE_FILTER_SKIP_PEERID 0 #define RDE_FILTER_SKIP_GROUPID 1 #define RDE_FILTER_SKIP_REMOTE_AS 2 -#define RDE_FILTER_SKIP_PEERID 3 -#define RDE_FILTER_SKIP_COUNT 4 +#define RDE_FILTER_SKIP_COUNT 3 struct filter_rule *skip[RDE_FILTER_SKIP_COUNT]; enum filter_actions action; enum directions dir; diff --git a/usr.sbin/bgpd/rde.c b/usr.sbin/bgpd/rde.c index dce91d6b274..64153f87c49 100644 --- a/usr.sbin/bgpd/rde.c +++ b/usr.sbin/bgpd/rde.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.c,v 1.594 2023/03/09 13:12:19 claudio Exp $ */ +/* $OpenBSD: rde.c,v 1.595 2023/03/10 07:57:15 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer @@ -198,17 +198,16 @@ rde_main(int debug, int verbose) imsg_init(ibuf_main, 3); /* initialize the RIB structures */ + if ((out_rules = calloc(1, sizeof(struct filter_head))) == NULL) + fatal(NULL); + TAILQ_INIT(out_rules); + pt_init(); - peer_init(); + peer_init(out_rules); /* make sure the default RIBs are setup */ rib_new("Adj-RIB-In", 0, F_RIB_NOFIB | F_RIB_NOEVALUATE); - out_rules = calloc(1, sizeof(struct filter_head)); - if (out_rules == NULL) - fatal(NULL); - TAILQ_INIT(out_rules); - conf = new_config(); log_info("route decision engine ready"); @@ -396,7 +395,7 @@ rde_dispatch_imsg_session(struct imsgbuf *ibuf) if (imsg.hdr.len - IMSG_HEADER_SIZE != sizeof(struct peer_config)) fatalx("incorrect size of session request"); - peer = peer_add(imsg.hdr.peerid, imsg.data); + peer = peer_add(imsg.hdr.peerid, imsg.data, out_rules); /* make sure rde_eval_all is on if needed. */ if (peer->conf.flags & PEERFLAG_EVALUATE_ALL) rde_eval_all = 1; @@ -896,6 +895,7 @@ rde_dispatch_imsg_parent(struct imsgbuf *ibuf) if ((rib = rib_byid(rib_find(r->rib))) == NULL) { log_warnx("IMSG_RECONF_FILTER: filter rule " "for nonexistent rib %s", r->rib); + filterset_free(&r->set); free(r); break; } @@ -911,8 +911,9 @@ rde_dispatch_imsg_parent(struct imsgbuf *ibuf) rib->in_rules_tmp = nr; } TAILQ_INSERT_TAIL(nr, r, entry); - } else + } else { TAILQ_INSERT_TAIL(out_rules_tmp, r, entry); + } break; case IMSG_RECONF_PREFIX_SET: case IMSG_RECONF_ORIGIN_SET: @@ -3559,20 +3560,15 @@ rde_reload_done(void) rde_mark_prefixsets_dirty(&originsets_old, &conf->rde_originsets); as_sets_mark_dirty(&as_sets_old, &conf->as_sets); - /* - * make the new filter rules the active one but keep the old for - * softrconfig. This is needed so that changes happening are using - * the right filters. - */ - fh = out_rules; - out_rules = out_rules_tmp; - out_rules_tmp = fh; - - rde_filter_calc_skip_steps(out_rules); /* make sure that rde_eval_all is correctly set after a config change */ rde_eval_all = 0; + /* Make the new outbound filter rules the active one. */ + filterlist_free(out_rules); + out_rules = out_rules_tmp; + out_rules_tmp = NULL; + /* check if filter changed */ RB_FOREACH(peer, peer_tree, &peertable) { if (peer->conf.id == 0) /* ignore peerself */ @@ -3641,12 +3637,17 @@ rde_reload_done(void) softreconfig++; /* account for the running flush */ continue; } - if (!rde_filter_equal(out_rules, out_rules_tmp, peer)) { + + /* reapply outbound filters for this peer */ + fh = peer_apply_out_filter(peer, out_rules); + + if (!rde_filter_equal(peer->out_rules, fh)) { char *p = log_fmt_peer(&peer->conf); log_debug("out filter change: reloading peer %s", p); free(p); peer->reconf_out = 1; } + filterlist_free(fh); } /* bring ribs in sync */ @@ -3696,8 +3697,7 @@ rde_reload_done(void) rib->state = RECONF_KEEP; /* FALLTHROUGH */ case RECONF_KEEP: - if (rde_filter_equal(rib->in_rules, - rib->in_rules_tmp, NULL)) + if (rde_filter_equal(rib->in_rules, rib->in_rules_tmp)) /* rib is in sync */ break; log_debug("in filter change: reloading RIB %s", @@ -3717,8 +3717,6 @@ rde_reload_done(void) rib->in_rules_tmp = NULL; } - filterlist_free(out_rules_tmp); - out_rules_tmp = NULL; /* old filters removed, free all sets */ free_rde_prefixsets(&prefixsets_old); free_rde_prefixsets(&originsets_old); @@ -3789,8 +3787,7 @@ rde_softreconfig_in_done(void *arg, uint8_t dummy) /* just resend the default route */ for (aid = 0; aid < AID_MAX; aid++) { if (peer->capa.mp[aid]) - up_generate_default(out_rules, - peer, aid); + up_generate_default(peer, aid); } peer->reconf_out = 0; } else diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h index 9488f2d5ba4..e37007e2e45 100644 --- a/usr.sbin/bgpd/rde.h +++ b/usr.sbin/bgpd/rde.h @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.h,v 1.284 2023/03/09 13:12:19 claudio Exp $ */ +/* $OpenBSD: rde.h,v 1.285 2023/03/10 07:57:15 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker and @@ -88,6 +88,7 @@ struct rde_peer { struct prefix_index adj_rib_out; struct prefix_tree updates[AID_MAX]; struct prefix_tree withdraws[AID_MAX]; + struct filter_head *out_rules; time_t staletime[AID_MAX]; uint32_t remote_bgpid; /* host byte order! */ uint32_t path_id_tx; @@ -401,12 +402,14 @@ int rde_match_peer(struct rde_peer *, struct ctl_neighbor *); int peer_has_as4byte(struct rde_peer *); int peer_has_add_path(struct rde_peer *, uint8_t, int); int peer_accept_no_as_set(struct rde_peer *); -void peer_init(void); +void peer_init(struct filter_head *); void peer_shutdown(void); void peer_foreach(void (*)(struct rde_peer *, void *), void *); struct rde_peer *peer_get(uint32_t); struct rde_peer *peer_match(struct ctl_neighbor *, uint32_t); -struct rde_peer *peer_add(uint32_t, struct peer_config *); +struct rde_peer *peer_add(uint32_t, struct peer_config *, struct filter_head *); +struct filter_head *peer_apply_out_filter(struct rde_peer *, + struct filter_head *); void rde_generate_updates(struct rib_entry *, struct prefix *, struct prefix *, enum eval_mode); @@ -532,14 +535,14 @@ void prefix_evaluate_nexthop(struct prefix *, enum nexthop_state, /* rde_filter.c */ void rde_apply_set(struct filter_set_head *, struct rde_peer *, - struct rde_peer *, struct filterstate *, uint8_t); + struct rde_peer *, struct filterstate *, u_int8_t); void rde_filterstate_init(struct filterstate *); void rde_filterstate_prep(struct filterstate *, struct prefix *); void rde_filterstate_copy(struct filterstate *, struct filterstate *); void rde_filterstate_set_vstate(struct filterstate *, uint8_t, uint8_t); void rde_filterstate_clean(struct filterstate *); -int rde_filter_equal(struct filter_head *, struct filter_head *, - struct rde_peer *); +int rde_filter_skip_rule(struct rde_peer *, struct filter_rule *); +int rde_filter_equal(struct filter_head *, struct filter_head *); void rde_filter_calc_skip_steps(struct filter_head *); enum filter_actions rde_filter(struct filter_head *, struct rde_peer *, struct rde_peer *, struct bgpd_addr *, uint8_t, @@ -727,15 +730,11 @@ int nexthop_compare(struct nexthop *, struct nexthop *); /* rde_update.c */ void up_init(struct rde_peer *); -void up_generate_updates(struct filter_head *, struct rde_peer *, - struct rib_entry *); -void up_generate_addpath(struct filter_head *, struct rde_peer *, - struct rib_entry *); -void up_generate_addpath_all(struct filter_head *, - struct rde_peer *, struct rib_entry *, struct prefix *, - struct prefix *); -void up_generate_default(struct filter_head *, struct rde_peer *, - uint8_t); +void up_generate_updates(struct rde_peer *, struct rib_entry *); +void up_generate_addpath(struct rde_peer *, struct rib_entry *); +void up_generate_addpath_all(struct rde_peer *, struct rib_entry *, + struct prefix *, struct prefix *); +void up_generate_default(struct rde_peer *, uint8_t); int up_is_eor(struct rde_peer *, uint8_t); int up_dump_withdraws(u_char *, int, struct rde_peer *, uint8_t); int up_dump_mp_unreach(u_char *, int, struct rde_peer *, uint8_t); diff --git a/usr.sbin/bgpd/rde_filter.c b/usr.sbin/bgpd/rde_filter.c index be8fe97cd73..e8871b8bd37 100644 --- a/usr.sbin/bgpd/rde_filter.c +++ b/usr.sbin/bgpd/rde_filter.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde_filter.c,v 1.133 2023/01/24 14:13:12 claudio Exp $ */ +/* $OpenBSD: rde_filter.c,v 1.134 2023/03/10 07:57:15 claudio Exp $ */ /* * Copyright (c) 2004 Claudio Jeker @@ -319,7 +319,7 @@ rde_filter_match(struct filter_rule *f, struct rde_peer *peer, } /* return true when the rule f can never match for this peer */ -static int +int rde_filter_skip_rule(struct rde_peer *peer, struct filter_rule *f) { /* if any of the two is unset then rule can't be skipped */ @@ -350,8 +350,7 @@ rde_filter_skip_rule(struct rde_peer *peer, struct filter_rule *f) } int -rde_filter_equal(struct filter_head *a, struct filter_head *b, - struct rde_peer *peer) +rde_filter_equal(struct filter_head *a, struct filter_head *b) { struct filter_rule *fa, *fb; struct rde_prefixset *psa, *psb, *osa, *osb; @@ -362,16 +361,6 @@ rde_filter_equal(struct filter_head *a, struct filter_head *b, fb = b ? TAILQ_FIRST(b) : NULL; while (fa != NULL || fb != NULL) { - /* skip all rules with wrong peer */ - if (rde_filter_skip_rule(peer, fa)) { - fa = TAILQ_NEXT(fa, entry); - continue; - } - if (rde_filter_skip_rule(peer, fb)) { - fb = TAILQ_NEXT(fb, entry); - continue; - } - /* compare the two rules */ if ((fa == NULL && fb != NULL) || (fa != NULL && fb == NULL)) /* new rule added or removed */ @@ -805,12 +794,12 @@ rde_filter_calc_skip_steps(struct filter_head *rules) for (i = 0; i < RDE_FILTER_SKIP_COUNT; ++i) head[i] = cur; while (cur != NULL) { + if (cur->peer.peerid != prev->peer.peerid) + RDE_FILTER_SET_SKIP_STEPS(RDE_FILTER_SKIP_PEERID); if (cur->peer.groupid != prev->peer.groupid) RDE_FILTER_SET_SKIP_STEPS(RDE_FILTER_SKIP_GROUPID); if (cur->peer.remote_as != prev->peer.remote_as) RDE_FILTER_SET_SKIP_STEPS(RDE_FILTER_SKIP_REMOTE_AS); - if (cur->peer.peerid != prev->peer.peerid) - RDE_FILTER_SET_SKIP_STEPS(RDE_FILTER_SKIP_PEERID); prev = cur; cur = TAILQ_NEXT(cur, entry); } @@ -847,6 +836,10 @@ rde_filter(struct filter_head *rules, struct rde_peer *peer, f = TAILQ_FIRST(rules); while (f != NULL) { + RDE_FILTER_TEST_ATTRIB( + (f->peer.peerid && + f->peer.peerid != peer->conf.id), + f->skip[RDE_FILTER_SKIP_PEERID]); RDE_FILTER_TEST_ATTRIB( (f->peer.groupid && f->peer.groupid != peer->conf.groupid), @@ -855,10 +848,6 @@ rde_filter(struct filter_head *rules, struct rde_peer *peer, (f->peer.remote_as && f->peer.remote_as != peer->conf.remote_as), f->skip[RDE_FILTER_SKIP_REMOTE_AS]); - RDE_FILTER_TEST_ATTRIB( - (f->peer.peerid && - f->peer.peerid != peer->conf.id), - f->skip[RDE_FILTER_SKIP_PEERID]); if (rde_filter_match(f, peer, from, state, prefix, plen)) { rde_apply_set(&f->set, peer, from, state, prefix->aid); diff --git a/usr.sbin/bgpd/rde_peer.c b/usr.sbin/bgpd/rde_peer.c index 181f75ff8d0..9248851c1d6 100644 --- a/usr.sbin/bgpd/rde_peer.c +++ b/usr.sbin/bgpd/rde_peer.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde_peer.c,v 1.30 2023/03/09 13:12:19 claudio Exp $ */ +/* $OpenBSD: rde_peer.c,v 1.31 2023/03/10 07:57:16 claudio Exp $ */ /* * Copyright (c) 2019 Claudio Jeker @@ -38,8 +38,6 @@ struct iq { struct imsg imsg; }; -extern struct filter_head *out_rules; - int peer_has_as4byte(struct rde_peer *peer) { @@ -68,7 +66,7 @@ peer_accept_no_as_set(struct rde_peer *peer) } void -peer_init(void) +peer_init(struct filter_head *rules) { struct peer_config pc; @@ -78,7 +76,7 @@ peer_init(void) snprintf(pc.descr, sizeof(pc.descr), "LOCAL"); pc.id = PEER_ID_SELF; - peerself = peer_add(PEER_ID_SELF, &pc); + peerself = peer_add(PEER_ID_SELF, &pc, rules); peerself->state = PEER_UP; } @@ -132,13 +130,13 @@ peer_match(struct ctl_neighbor *n, uint32_t peerid) for (; peer != NULL; peer = RB_NEXT(peer_tree, &peertable, peer)) { if (rde_match_peer(peer, n)) - return (peer); + return peer; } - return (NULL); + return NULL; } struct rde_peer * -peer_add(uint32_t id, struct peer_config *p_conf) +peer_add(uint32_t id, struct peer_config *p_conf, struct filter_head *rules) { struct rde_peer *peer; int conflict; @@ -164,6 +162,8 @@ peer_add(uint32_t id, struct peer_config *p_conf) peer->flags = peer->conf.flags; SIMPLEQ_INIT(&peer->imsg_queue); + peer_apply_out_filter(peer, rules); + /* * Assign an even random unique transmit path id. * Odd path_id_tx numbers are for peers using add-path recv. @@ -187,6 +187,32 @@ peer_add(uint32_t id, struct peer_config *p_conf) return (peer); } +struct filter_head * +peer_apply_out_filter(struct rde_peer *peer, struct filter_head *rules) +{ + struct filter_head *old; + struct filter_rule *fr, *new; + + old = peer->out_rules; + if ((peer->out_rules = malloc(sizeof(*peer->out_rules))) == NULL) + fatal(NULL); + TAILQ_INIT(peer->out_rules); + + TAILQ_FOREACH(fr, rules, entry) { + if (rde_filter_skip_rule(peer, fr)) + continue; + + if ((new = malloc(sizeof(*new))) == NULL) + fatal(NULL); + memcpy(new, fr, sizeof(*new)); + filterset_copy(&fr->set, &new->set); + + TAILQ_INSERT_TAIL(peer->out_rules, new, entry); + } + + return old; +} + static inline int peer_cmp(struct rde_peer *a, struct rde_peer *b) { @@ -231,17 +257,16 @@ peer_generate_update(struct rde_peer *peer, struct rib_entry *re, /* handle peers with add-path */ if (peer_has_add_path(peer, aid, CAPA_AP_SEND)) { if (peer->eval.mode == ADDPATH_EVAL_ALL) - up_generate_addpath_all(out_rules, peer, re, - newpath, oldpath); + up_generate_addpath_all(peer, re, newpath, oldpath); else - up_generate_addpath(out_rules, peer, re); + up_generate_addpath(peer, re); return; } /* skip regular peers if the best path didn't change */ if (mode == EVAL_ALL && (peer->flags & PEERFLAG_EVALUATE_ALL) == 0) return; - up_generate_updates(out_rules, peer, re); + up_generate_updates(peer, re); } void @@ -362,6 +387,7 @@ rde_up_dump_upcall(struct rib_entry *re, void *ptr) if ((p = prefix_best(re)) == NULL) /* no eligible prefix, not even for 'evaluate all' */ return; + peer_generate_update(peer, re, NULL, NULL, 0); } @@ -449,6 +475,9 @@ peer_down(struct rde_peer *peer, void *bula) peer->stats.prefix_cnt = 0; peer->stats.prefix_out_cnt = 0; + /* free filters */ + filterlist_free(peer->out_rules); + RB_REMOVE(peer_tree, &peertable, peer); free(peer); } @@ -531,7 +560,7 @@ peer_dump(struct rde_peer *peer, uint8_t aid) if (peer->capa.grestart.restart) prefix_add_eor(peer, aid); } else if (peer->export_type == EXPORT_DEFAULT_ROUTE) { - up_generate_default(out_rules, peer, aid); + up_generate_default(peer, aid); rde_up_dump_done(peer, aid); } else { if (rib_dump_new(peer->loc_rib_id, aid, RDE_RUNNER_ROUNDS, peer, diff --git a/usr.sbin/bgpd/rde_update.c b/usr.sbin/bgpd/rde_update.c index 5b0eca0760f..4276c3680bb 100644 --- a/usr.sbin/bgpd/rde_update.c +++ b/usr.sbin/bgpd/rde_update.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde_update.c,v 1.157 2023/03/09 13:12:19 claudio Exp $ */ +/* $OpenBSD: rde_update.c,v 1.158 2023/03/10 07:57:16 claudio Exp $ */ /* * Copyright (c) 2004 Claudio Jeker @@ -150,8 +150,8 @@ up_enforce_open_policy(struct rde_peer *peer, struct filterstate *state, * - UP_EXCLUDED if prefix was excluded because of up_test_update() */ static enum up_state -up_process_prefix(struct filter_head *rules, struct rde_peer *peer, - struct prefix *new, struct prefix *p, struct bgpd_addr *addr, uint8_t plen) +up_process_prefix(struct rde_peer *peer, struct prefix *new, struct prefix *p, + struct bgpd_addr *addr, uint8_t plen) { struct filterstate state; int excluded = 0; @@ -166,8 +166,8 @@ up_process_prefix(struct filter_head *rules, struct rde_peer *peer, excluded = 1; rde_filterstate_prep(&state, new); - if (rde_filter(rules, peer, prefix_peer(new), addr, plen, &state) == - ACTION_DENY) { + if (rde_filter(peer->out_rules, peer, prefix_peer(new), addr, plen, + &state) == ACTION_DENY) { rde_filterstate_clean(&state); return UP_FILTERED; } @@ -206,8 +206,7 @@ up_process_prefix(struct filter_head *rules, struct rde_peer *peer, } void -up_generate_updates(struct filter_head *rules, struct rde_peer *peer, - struct rib_entry *re) +up_generate_updates(struct rde_peer *peer, struct rib_entry *re) { struct bgpd_addr addr; struct prefix *new, *p; @@ -220,8 +219,7 @@ up_generate_updates(struct filter_head *rules, struct rde_peer *peer, new = prefix_best(re); while (new != NULL) { - switch (up_process_prefix(rules, peer, new, p, - &addr, prefixlen)) { + switch (up_process_prefix(peer, new, p, &addr, prefixlen)) { case UP_OK: case UP_ERR_LIMIT: return; @@ -251,8 +249,7 @@ done: * less churn is needed. */ void -up_generate_addpath(struct filter_head *rules, struct rde_peer *peer, - struct rib_entry *re) +up_generate_addpath(struct rde_peer *peer, struct rib_entry *re) { struct bgpd_addr addr; struct prefix *head, *new, *p; @@ -313,8 +310,8 @@ up_generate_addpath(struct filter_head *rules, struct rde_peer *peer, } } - switch (up_process_prefix(rules, peer, new, (void *)-1, - &addr, prefixlen)) { + switch (up_process_prefix(peer, new, (void *)-1, &addr, + prefixlen)) { case UP_OK: maxpaths++; extrapaths += extra; @@ -345,8 +342,8 @@ up_generate_addpath(struct filter_head *rules, struct rde_peer *peer, * are distributed just remove old and add new. */ void -up_generate_addpath_all(struct filter_head *rules, struct rde_peer *peer, - struct rib_entry *re, struct prefix *new, struct prefix *old) +up_generate_addpath_all(struct rde_peer *peer, struct rib_entry *re, + struct prefix *new, struct prefix *old) { struct bgpd_addr addr; struct prefix *p, *head = NULL; @@ -379,8 +376,8 @@ up_generate_addpath_all(struct filter_head *rules, struct rde_peer *peer, /* add new path (or multiple if all is set) */ while (new != NULL) { - switch (up_process_prefix(rules, peer, new, (void *)-1, - &addr, prefixlen)) { + switch (up_process_prefix(peer, new, (void *)-1, &addr, + prefixlen)) { case UP_OK: case UP_FILTERED: case UP_EXCLUDED: @@ -414,8 +411,7 @@ int rib_empty(struct rib_entry *); /* send a default route to the specified peer */ void -up_generate_default(struct filter_head *rules, struct rde_peer *peer, - uint8_t aid) +up_generate_default(struct rde_peer *peer, uint8_t aid) { extern struct rde_peer *peerself; struct filterstate state; @@ -444,7 +440,7 @@ up_generate_default(struct filter_head *rules, struct rde_peer *peer, p = prefix_adjout_lookup(peer, &addr, 0); /* outbound filter as usual */ - if (rde_filter(rules, peer, peerself, &addr, 0, &state) == + if (rde_filter(peer->out_rules, peer, peerself, &addr, 0, &state) == ACTION_DENY) { rde_filterstate_clean(&state); return; -- 2.20.1