bgpd optimize filter rules

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

bgpd optimize filter rules

Claudio Jeker
There is a trivial optimization that bgpd can do when loading the filter
ruleset. If the rule is the same as the previous rule than the filterset
can be merged.  e.g.

    match from ebgp set community delete $myAS:*
    match from ebgp set community $myAS:15
    match from ebgp set med 100

Will be optimized into:

    match from ebgp set { metric 100 community delete $myAS:* community $myAS:15 }

The following diff is doing this and saves around 5% of the rules in
arouteserver configs and probably similar amount in other peoples config.
--
:wq Claudio

Index: bgpd.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/bgpd.h,v
retrieving revision 1.355
diff -u -p -r1.355 bgpd.h
--- bgpd.h 28 Nov 2018 08:32:26 -0000 1.355
+++ bgpd.h 28 Nov 2018 10:07:50 -0000
@@ -966,10 +966,10 @@ enum action_types {
  ACTION_SET_NEXTHOP_BLACKHOLE,
  ACTION_SET_NEXTHOP_NOMODIFY,
  ACTION_SET_NEXTHOP_SELF,
- ACTION_SET_COMMUNITY,
  ACTION_DEL_COMMUNITY,
- ACTION_SET_EXT_COMMUNITY,
+ ACTION_SET_COMMUNITY,
  ACTION_DEL_EXT_COMMUNITY,
+ ACTION_SET_EXT_COMMUNITY,
  ACTION_PFTABLE,
  ACTION_PFTABLE_ID,
  ACTION_RTLABEL,
Index: parse.y
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/parse.y,v
retrieving revision 1.364
diff -u -p -r1.364 parse.y
--- parse.y 28 Nov 2018 08:32:27 -0000 1.364
+++ parse.y 28 Nov 2018 10:09:34 -0000
@@ -150,7 +150,7 @@ int expand_rule(struct filter_rule *,
 int str2key(char *, char *, size_t);
 int neighbor_consistent(struct peer *);
 int merge_filterset(struct filter_set_head *, struct filter_set *);
-void merge_filter_lists(struct filter_head *, struct filter_head *);
+void optimize_filters(struct filter_head *);
 struct filter_rule *get_rule(enum action_types);
 
 int parsecommunity(struct filter_community *, int, char *);
@@ -3345,13 +3345,15 @@ parse_config(char *filename, struct bgpd
  free_config(conf);
  } else {
  /*
- * Move filter list and static group and peer filtersets
+ * Concatenate filter list and static group and peer filtersets
  * together. Static group sets come first then peer sets
  * last normal filter rules.
  */
- merge_filter_lists(conf->filters, groupfilter_l);
- merge_filter_lists(conf->filters, peerfilter_l);
- merge_filter_lists(conf->filters, filter_l);
+ TAILQ_CONCAT(conf->filters, groupfilter_l, entry);
+ TAILQ_CONCAT(conf->filters, peerfilter_l, entry);
+ TAILQ_CONCAT(conf->filters, filter_l, entry);
+
+ optimize_filters(conf->filters);
 
  errors += mrt_mergeconfig(xconf->mrt, conf->mrt);
  errors += merge_config(xconf, conf, peer_l);
@@ -4180,39 +4182,17 @@ neighbor_consistent(struct peer *p)
  return (0);
 }
 
-int
-merge_filterset(struct filter_set_head *sh, struct filter_set *s)
+static void
+filterset_add(struct filter_set_head *sh, struct filter_set *s)
 {
  struct filter_set *t;
 
  TAILQ_FOREACH(t, sh, entry) {
- /*
- * need to cycle across the full list because even
- * if types are not equal filterset_cmp() may return 0.
- */
- if (filterset_cmp(s, t) == 0) {
- if (s->type == ACTION_SET_COMMUNITY)
- yyerror("community is already set");
- else if (s->type == ACTION_DEL_COMMUNITY)
- yyerror("community will already be deleted");
- else if (s->type == ACTION_SET_EXT_COMMUNITY)
- yyerror("ext-community is already set");
- else if (s->type == ACTION_DEL_EXT_COMMUNITY)
- yyerror(
-    "ext-community will already be deleted");
- else
- yyerror("redefining set parameter %s",
-    filterset_name(s->type));
- return (-1);
- }
- }
-
- TAILQ_FOREACH(t, sh, entry) {
  if (s->type < t->type) {
  TAILQ_INSERT_BEFORE(t, s, entry);
- return (0);
+ return;
  }
- if (s->type == t->type)
+ if (s->type == t->type) {
  switch (s->type) {
  case ACTION_SET_COMMUNITY:
  case ACTION_DEL_COMMUNITY:
@@ -4220,42 +4200,145 @@ merge_filterset(struct filter_set_head *
     &t->action.community,
     sizeof(s->action.community)) < 0) {
  TAILQ_INSERT_BEFORE(t, s, entry);
- return (0);
- }
- break;
+ return;
+ } else if (memcmp(&s->action.community,
+    &t->action.community,
+    sizeof(s->action.community)) == 0)
+ break;
+ continue;
  case ACTION_SET_EXT_COMMUNITY:
  case ACTION_DEL_EXT_COMMUNITY:
  if (memcmp(&s->action.ext_community,
     &t->action.ext_community,
     sizeof(s->action.ext_community)) < 0) {
  TAILQ_INSERT_BEFORE(t, s, entry);
- return (0);
- }
- break;
+ return;
+ } else if (memcmp(&s->action.ext_community,
+    &t->action.ext_community,
+    sizeof(s->action.ext_community)) == 0)
+ break;
+ continue;
  case ACTION_SET_NEXTHOP:
+ /* only last nexthop per AF matters */
  if (s->action.nexthop.aid <
     t->action.nexthop.aid) {
  TAILQ_INSERT_BEFORE(t, s, entry);
- return (0);
+ return;
+ } else if (s->action.nexthop.aid ==
+    t->action.nexthop.aid) {
+ t->action.nexthop = s->action.nexthop;
+ break;
  }
+ continue;
+ case ACTION_SET_NEXTHOP_BLACKHOLE:
+ case ACTION_SET_NEXTHOP_REJECT:
+ case ACTION_SET_NEXTHOP_NOMODIFY:
+ case ACTION_SET_NEXTHOP_SELF:
+ /* set it only once */
+ break;
+ case ACTION_SET_LOCALPREF:
+ case ACTION_SET_MED:
+ case ACTION_SET_WEIGHT:
+ /* only last set matters */
+ t->action.metric = s->action.metric;
+ break;
+ case ACTION_SET_RELATIVE_LOCALPREF:
+ case ACTION_SET_RELATIVE_MED:
+ case ACTION_SET_RELATIVE_WEIGHT:
+ /* sum all relative numbers */
+ t->action.relative += s->action.relative;
+ break;
+ case ACTION_SET_ORIGIN:
+ /* only last set matters */
+ t->action.origin = s->action.origin;
+ break;
+ case ACTION_PFTABLE:
+ /* only last set matters */
+ strlcpy(t->action.pftable, s->action.pftable,
+    sizeof(t->action.pftable));
+ break;
+ case ACTION_RTLABEL:
+ /* only last set matters */
+ strlcpy(t->action.rtlabel, s->action.rtlabel,
+    sizeof(t->action.rtlabel));
  break;
  default:
  break;
  }
+ free(s);
+ return;
+ }
  }
 
  TAILQ_INSERT_TAIL(sh, s, entry);
+}
+
+int
+merge_filterset(struct filter_set_head *sh, struct filter_set *s)
+{
+ struct filter_set *t;
+
+ TAILQ_FOREACH(t, sh, entry) {
+ /*
+ * need to cycle across the full list because even
+ * if types are not equal filterset_cmp() may return 0.
+ */
+ if (filterset_cmp(s, t) == 0) {
+ if (s->type == ACTION_SET_COMMUNITY)
+ yyerror("community is already set");
+ else if (s->type == ACTION_DEL_COMMUNITY)
+ yyerror("community will already be deleted");
+ else if (s->type == ACTION_SET_EXT_COMMUNITY)
+ yyerror("ext-community is already set");
+ else if (s->type == ACTION_DEL_EXT_COMMUNITY)
+ yyerror(
+    "ext-community will already be deleted");
+ else
+ yyerror("redefining set parameter %s",
+    filterset_name(s->type));
+ return (-1);
+ }
+ }
+
+ filterset_add(sh, s);
  return (0);
 }
 
+static int
+filter_equal(struct filter_rule *fa, struct filter_rule *fb)
+{
+ if (fa == NULL || fb == NULL)
+ return 0;
+ if (fa->action != fb->action || fa->quick != fb->quick ||
+    fa->dir != fb->dir)
+ return 0;
+ if (memcmp(&fa->peer, &fb->peer, sizeof(fa->peer)))
+ return 0;
+ if (memcmp(&fa->match, &fb->match, sizeof(fa->match)))
+ return 0;
+
+ return 1;
+}
+
+/* do a basic optimization by folding equal rules together */
 void
-merge_filter_lists(struct filter_head *dst, struct filter_head *src)
+optimize_filters(struct filter_head *fh)
 {
- struct filter_rule *r;
+ struct filter_rule *r, *nr;
+
+ TAILQ_FOREACH_SAFE(r, fh, entry, nr) {
+ while (filter_equal(r, nr)) {
+ struct filter_set *t;
 
- while ((r = TAILQ_FIRST(src)) != NULL) {
- TAILQ_REMOVE(src, r, entry);
- TAILQ_INSERT_TAIL(dst, r, entry);
+ while((t = TAILQ_FIRST(&nr->set)) != NULL) {
+ TAILQ_REMOVE(&nr->set, t, entry);
+ filterset_add(&r->set, t);
+ }
+
+ TAILQ_REMOVE(fh, nr, entry);
+ free(nr);
+ nr = TAILQ_NEXT(r, entry);
+ }
  }
 }
 

Reply | Threaded
Open this post in threaded view
|

Re: bgpd optimize filter rules

Job Snijders-2
On Mon, Dec 03, 2018 at 12:14:13PM +0100, Claudio Jeker wrote:

> There is a trivial optimization that bgpd can do when loading the filter
> ruleset. If the rule is the same as the previous rule than the filterset
> can be merged.  e.g.
>
>     match from ebgp set community delete $myAS:*
>     match from ebgp set community $myAS:15
>     match from ebgp set med 100
>
> Will be optimized into:
>
>     match from ebgp set { metric 100 community delete $myAS:* community $myAS:15 }
>
> The following diff is doing this and saves around 5% of the rules in
> arouteserver configs and probably similar amount in other peoples config.

OK job@