filter/data.c

   1 /*
   2  *      Filters: utility functions
   3  *
   4  *      (c) 1998 Pavel Machek <pavel@ucw.cz>
   5  *      (c) 2019 Maria Matejka <mq@jmq.cz>
   6  *
   7  *      Can be freely distributed and used under the terms of the GNU GPL.
   8  *
   9  */
  10
  11 #include "nest/bird.h"
  12 #include "lib/lists.h"
  13 #include "lib/resource.h"
  14 #include "lib/socket.h"
  15 #include "lib/string.h"
  16 #include "lib/unaligned.h"
  17 #include "lib/net.h"
  18 #include "lib/ip.h"
  19 #include "nest/route.h"
  20 #include "nest/protocol.h"
  21 #include "nest/iface.h"
  22 #include "nest/attrs.h"
  23 #include "conf/conf.h"
  24 #include "filter/filter.h"
  25 #include "filter/f-inst.h"
  26 #include "filter/data.h"
  27
  28 static const char * const f_type_str[] = {
  29   [T_VOID]      = "void",
  30   [T_NONE]      = "none",
  31
  32   [T_INT]       = "int",
  33   [T_BOOL]      = "bool",
  34   [T_PAIR]      = "pair",
  35   [T_QUAD]      = "quad",
  36
  37   [T_ENUM_RTS]  = "enum rts",
  38   [T_ENUM_BGP_ORIGIN] = "enum bgp_origin",
  39   [T_ENUM_SCOPE] = "enum scope",
  40   [T_ENUM_RTC]  = "enum rtc",
  41   [T_ENUM_RTD]  = "enum rtd",
  42   [T_ENUM_ROA]  = "enum roa",
  43   [T_ENUM_NETTYPE] = "enum nettype",
  44   [T_ENUM_RA_PREFERENCE] = "enum ra_preference",
  45   [T_ENUM_AF]   = "enum af",
  46
  47   [T_IP]        = "ip",
  48   [T_NET]       = "prefix",
  49   [T_STRING]    = "string",
  50   [T_BYTESTRING]        = "bytestring",
  51   [T_PATH_MASK] = "bgpmask",
  52   [T_PATH]      = "bgppath",
  53   [T_CLIST]     = "clist",
  54   [T_EC]        = "ec",
  55   [T_ECLIST]    = "eclist",
  56   [T_LC]        = "lc",
  57   [T_LCLIST]    = "lclist",
  58   [T_RD]        = "rd",
  59
  60   [T_ROUTE] = "route",
  61   [T_ROUTES_BLOCK] = "block of routes",
  62 };
  63
  64 const char *
  65 f_type_name(enum f_type t)
  66 {
  67   if (t < ARRAY_SIZE(f_type_str))
  68     return f_type_str[t] ?: "?";
  69
  70   if ((t == T_SET) || (t == T_PREFIX_SET))
  71     return "set";
  72
  73   return "?";
  74 }
  75
  76 enum f_type
  77 f_type_element_type(enum f_type t)
  78 {
  79   switch(t) {
  80     case T_PATH:   return T_INT;
  81     case T_CLIST:  return T_PAIR;
  82     case T_ECLIST: return T_EC;
  83     case T_LCLIST: return T_LC;
  84     case T_ROUTES_BLOCK: return T_ROUTE;
  85     default: return T_VOID;
  86   };
  87 }
  88
  89 const struct f_trie f_const_empty_trie = { .ipv4 = -1, };
  90 const struct f_val f_const_empty_prefix_set = {
  91   .type = T_PREFIX_SET,
  92   .val.ti = &f_const_empty_trie,
  93 };
  94
  95 static struct adata *
  96 adata_empty(struct linpool *pool, int l)
  97 {
  98   struct adata *res = lp_alloc(pool, sizeof(struct adata) + l);
  99   res->length = l;
 100   return res;
 101 }
 102
 103 static void
 104 pm_format(const struct f_path_mask *p, buffer *buf)
 105 {
 106   int loop = 0;
 107
 108   buffer_puts(buf, "[= ");
 109
 110   for (uint i=0; i<p->len; i++)
 111   {
 112     switch(p->item[i].kind)
 113     {
 114     case PM_ASN:
 115       buffer_print(buf, "%u ", p->item[i].asn);
 116       break;
 117
 118     case PM_QUESTION:
 119       buffer_puts(buf, "? ");
 120       break;
 121
 122     case PM_ASTERISK:
 123       buffer_puts(buf, "* ");
 124       break;
 125
 126     case PM_LOOP:
 127       loop = 1;
 128       break;
 129
 130     case PM_ASN_RANGE:
 131       buffer_print(buf, "%u..%u ", p->item[i].from, p->item[i].to);
 132       break;
 133
 134     case PM_ASN_SET:
 135       tree_format(p->item[i].set, buf);
 136       buffer_puts(buf, " ");
 137       break;
 138
 139     case PM_ASN_EXPR:
 140       ASSERT(0);
 141     }
 142
 143     if (loop && (p->item[i].kind != PM_LOOP))
 144     {
 145       buffer_puts(buf, "+ ");
 146       loop = 0;
 147     }
 148   }
 149
 150   buffer_puts(buf, "=]");
 151 }
 152
 153 static inline int
 154 lcomm_cmp(lcomm v1, lcomm v2)
 155 {
 156   if (v1.asn != v2.asn)
 157     return (v1.asn > v2.asn) ? 1 : -1;
 158   if (v1.ldp1 != v2.ldp1)
 159     return (v1.ldp1 > v2.ldp1) ? 1 : -1;
 160   if (v1.ldp2 != v2.ldp2)
 161     return (v1.ldp2 > v2.ldp2) ? 1 : -1;
 162   return 0;
 163 }
 164
 165 /**
 166  * val_compare - compare two values
 167  * @v1: first value
 168  * @v2: second value
 169  *
 170  * Compares two values and returns -1, 0, 1 on <, =, > or F_CMP_ERROR on
 171  * error. Tree module relies on this giving consistent results so
 172  * that it can be used for building balanced trees.
 173  */
 174 int
 175 val_compare(const struct f_val *v1, const struct f_val *v2)
 176 {
 177   if (v1->type != v2->type) {
 178     if (v1->type == T_VOID)     /* Hack for else */
 179       return -1;
 180     if (v2->type == T_VOID)
 181       return 1;
 182
 183     /* IP->Quad implicit conversion */
 184     if ((v1->type == T_QUAD) && val_is_ip4(v2))
 185       return uint_cmp(v1->val.i, ipa_to_u32(v2->val.ip));
 186     if (val_is_ip4(v1) && (v2->type == T_QUAD))
 187       return uint_cmp(ipa_to_u32(v1->val.ip), v2->val.i);
 188
 189     DBG( "Types do not match in val_compare\n" );
 190     return F_CMP_ERROR;
 191   }
 192
 193   switch (v1->type) {
 194   case T_VOID:
 195     return 0;
 196   case T_ENUM:
 197   case T_INT:
 198   case T_BOOL:
 199   case T_PAIR:
 200   case T_QUAD:
 201     return uint_cmp(v1->val.i, v2->val.i);
 202   case T_EC:
 203   case T_RD:
 204     return u64_cmp(v1->val.ec, v2->val.ec);
 205   case T_LC:
 206     return lcomm_cmp(v1->val.lc, v2->val.lc);
 207   case T_IP:
 208     return ipa_compare(v1->val.ip, v2->val.ip);
 209   case T_NET:
 210     return net_compare(v1->val.net, v2->val.net);
 211   case T_STRING:
 212     return strcmp(v1->val.s, v2->val.s);
 213   case T_PATH:
 214     return as_path_compare(v1->val.ad, v2->val.ad);
 215   case T_ROUTE:
 216   /* Fall through */
 217   case T_ROUTES_BLOCK:
 218   default:
 219     return F_CMP_ERROR;
 220   }
 221 }
 222
 223 static inline int
 224 bs_same(const struct adata *bs1, const struct adata *bs2)
 225 {
 226   return (bs1->length == bs2->length) && !memcmp(bs1->data, bs2->data, bs1->length);
 227 }
 228
 229 static inline int
 230 pmi_same(const struct f_path_mask_item *mi1, const struct f_path_mask_item *mi2)
 231 {
 232   if (mi1->kind != mi2->kind)
 233     return 0;
 234
 235   switch (mi1->kind) {
 236     case PM_ASN:
 237       if (mi1->asn != mi2->asn)
 238         return 0;
 239       break;
 240     case PM_ASN_EXPR:
 241       if (!f_same(mi1->expr, mi2->expr))
 242         return 0;
 243       break;
 244     case PM_ASN_RANGE:
 245       if (mi1->from != mi2->from)
 246         return 0;
 247       if (mi1->to != mi2->to)
 248         return 0;
 249       break;
 250     case PM_ASN_SET:
 251       if (!same_tree(mi1->set, mi2->set))
 252         return 0;
 253       break;
 254   }
 255
 256   return 1;
 257 }
 258
 259 static int
 260 pm_same(const struct f_path_mask *m1, const struct f_path_mask *m2)
 261 {
 262   if (m1->len != m2->len)
 263     return 0;
 264
 265   for (uint i=0; i<m1->len; i++)
 266     if (!pmi_same(&(m1->item[i]), &(m2->item[i])))
 267       return 0;
 268
 269   return 1;
 270 }
 271
 272 /**
 273  * val_same - compare two values
 274  * @v1: first value
 275  * @v2: second value
 276  *
 277  * Compares two values and returns 1 if they are same and 0 if not.
 278  * Comparison of values of different types is valid and returns 0.
 279  */
 280 int
 281 val_same(const struct f_val *v1, const struct f_val *v2)
 282 {
 283   int rc;
 284
 285   rc = val_compare(v1, v2);
 286   if (rc != F_CMP_ERROR)
 287     return !rc;
 288
 289   if (v1->type != v2->type)
 290     return 0;
 291
 292   switch (v1->type) {
 293   case T_BYTESTRING:
 294     return bs_same(v1->val.bs, v2->val.bs);
 295   case T_PATH_MASK:
 296     return pm_same(v1->val.path_mask, v2->val.path_mask);
 297   case T_PATH_MASK_ITEM:
 298     return pmi_same(&(v1->val.pmi), &(v2->val.pmi));
 299   case T_PATH:
 300   case T_CLIST:
 301   case T_ECLIST:
 302   case T_LCLIST:
 303     return adata_same(v1->val.ad, v2->val.ad);
 304   case T_SET:
 305     return same_tree(v1->val.t, v2->val.t);
 306   case T_PREFIX_SET:
 307     return trie_same(v1->val.ti, v2->val.ti);
 308   case T_ROUTE:
 309     return v1->val.rte == v2->val.rte;
 310   case T_ROUTES_BLOCK:
 311     return v1->val.ad == v2->val.ad;
 312   default:
 313     bug("Invalid type in val_same(): %x", v1->type);
 314   }
 315 }
 316
 317 int
 318 clist_set_type(const struct f_tree *set, struct f_val *v)
 319 {
 320   if (!set)
 321   {
 322     v->type = T_VOID;
 323     return 1;
 324   }
 325
 326   switch (set->from.type)
 327   {
 328   case T_PAIR:
 329     v->type = T_PAIR;
 330     return 1;
 331
 332   case T_QUAD:
 333     v->type = T_QUAD;
 334     return 1;
 335
 336   case T_IP:
 337     if (val_is_ip4(&(set->from)) && val_is_ip4(&(set->to)))
 338     {
 339       v->type = T_QUAD;
 340       return 1;
 341     }
 342     /* Fall through */
 343   default:
 344     v->type = T_VOID;
 345     return 0;
 346   }
 347 }
 348
 349 int
 350 clist_match_set(const struct adata *clist, const struct f_tree *set)
 351 {
 352   if (!clist)
 353     return 0;
 354
 355   struct f_val v;
 356   if (!clist_set_type(set, &v))
 357     return F_CMP_ERROR;
 358
 359   u32 *l = (u32 *) clist->data;
 360   u32 *end = l + clist->length/4;
 361
 362   while (l < end) {
 363     v.val.i = *l++;
 364     if (find_tree(set, &v))
 365       return 1;
 366   }
 367   return 0;
 368 }
 369
 370 int
 371 eclist_match_set(const struct adata *list, const struct f_tree *set)
 372 {
 373   if (!list)
 374     return 0;
 375
 376   if (!eclist_set_type(set))
 377     return F_CMP_ERROR;
 378
 379   struct f_val v;
 380   u32 *l = int_set_get_data(list);
 381   int len = int_set_get_size(list);
 382   int i;
 383
 384   v.type = T_EC;
 385   for (i = 0; i < len; i += 2) {
 386     v.val.ec = ec_get(l, i);
 387     if (find_tree(set, &v))
 388       return 1;
 389   }
 390
 391   return 0;
 392 }
 393
 394 int
 395 lclist_match_set(const struct adata *list, const struct f_tree *set)
 396 {
 397   if (!list)
 398     return 0;
 399
 400   if (!lclist_set_type(set))
 401     return F_CMP_ERROR;
 402
 403   struct f_val v;
 404   u32 *l = int_set_get_data(list);
 405   int len = int_set_get_size(list);
 406   int i;
 407
 408   v.type = T_LC;
 409   for (i = 0; i < len; i += 3) {
 410     v.val.lc = lc_get(l, i);
 411     if (find_tree(set, &v))
 412       return 1;
 413   }
 414
 415   return 0;
 416 }
 417
 418 const struct adata *
 419 clist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos)
 420 {
 421   if (!list)
 422     return NULL;
 423
 424   int tree = (set->type == T_SET);      /* 1 -> set is T_SET, 0 -> set is T_CLIST */
 425   struct f_val v;
 426   if (tree)
 427     clist_set_type(set->val.t, &v);
 428   else
 429     v.type = T_PAIR;
 430
 431   int len = int_set_get_size(list);
 432   u32 *l = int_set_get_data(list);
 433   u32 tmp[len];
 434   u32 *k = tmp;
 435   u32 *end = l + len;
 436
 437   while (l < end) {
 438     v.val.i = *l++;
 439     /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
 440     if ((tree ? !!find_tree(set->val.t, &v) : int_set_contains(set->val.ad, v.val.i)) == pos)
 441       *k++ = v.val.i;
 442   }
 443
 444   uint nl = (k - tmp) * sizeof(u32);
 445   if (nl == list->length)
 446     return list;
 447
 448   struct adata *res = adata_empty(pool, nl);
 449   memcpy(res->data, tmp, nl);
 450   return res;
 451 }
 452
 453 const struct adata *
 454 eclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos)
 455 {
 456   if (!list)
 457     return NULL;
 458
 459   int tree = (set->type == T_SET);      /* 1 -> set is T_SET, 0 -> set is T_CLIST */
 460   struct f_val v;
 461
 462   int len = int_set_get_size(list);
 463   u32 *l = int_set_get_data(list);
 464   u32 tmp[len];
 465   u32 *k = tmp;
 466   int i;
 467
 468   v.type = T_EC;
 469   for (i = 0; i < len; i += 2) {
 470     v.val.ec = ec_get(l, i);
 471     /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
 472     if ((tree ? !!find_tree(set->val.t, &v) : ec_set_contains(set->val.ad, v.val.ec)) == pos) {
 473       *k++ = l[i];
 474       *k++ = l[i+1];
 475     }
 476   }
 477
 478   uint nl = (k - tmp) * sizeof(u32);
 479   if (nl == list->length)
 480     return list;
 481
 482   struct adata *res = adata_empty(pool, nl);
 483   memcpy(res->data, tmp, nl);
 484   return res;
 485 }
 486
 487 const struct adata *
 488 lclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos)
 489 {
 490   if (!list)
 491     return NULL;
 492
 493   int tree = (set->type == T_SET);      /* 1 -> set is T_SET, 0 -> set is T_CLIST */
 494   struct f_val v;
 495
 496   int len = int_set_get_size(list);
 497   u32 *l = int_set_get_data(list);
 498   u32 tmp[len];
 499   u32 *k = tmp;
 500   int i;
 501
 502   v.type = T_LC;
 503   for (i = 0; i < len; i += 3) {
 504     v.val.lc = lc_get(l, i);
 505     /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
 506     if ((tree ? !!find_tree(set->val.t, &v) : lc_set_contains(set->val.ad, v.val.lc)) == pos)
 507       k = lc_copy(k, l+i);
 508   }
 509
 510   uint nl = (k - tmp) * sizeof(u32);
 511   if (nl == list->length)
 512     return list;
 513
 514   struct adata *res = adata_empty(pool, nl);
 515   memcpy(res->data, tmp, nl);
 516   return res;
 517 }
 518
 519 /**
 520  * val_in_range - implement |~| operator
 521  * @v1: element
 522  * @v2: set
 523  *
 524  * Checks if @v1 is element (|~| operator) of @v2.
 525  */
 526 int
 527 val_in_range(const struct f_val *v1, const struct f_val *v2)
 528 {
 529   if ((v1->type == T_PATH) && (v2->type == T_PATH_MASK))
 530     return as_path_match(v1->val.ad, v2->val.path_mask);
 531
 532   if ((v1->type == T_INT) && (v2->type == T_PATH))
 533     return as_path_contains(v2->val.ad, v1->val.i, 1);
 534
 535   if (((v1->type == T_PAIR) || (v1->type == T_QUAD)) && (v2->type == T_CLIST))
 536     return int_set_contains(v2->val.ad, v1->val.i);
 537   /* IP->Quad implicit conversion */
 538   if (val_is_ip4(v1) && (v2->type == T_CLIST))
 539     return int_set_contains(v2->val.ad, ipa_to_u32(v1->val.ip));
 540
 541   if ((v1->type == T_EC) && (v2->type == T_ECLIST))
 542     return ec_set_contains(v2->val.ad, v1->val.ec);
 543
 544   if ((v1->type == T_LC) && (v2->type == T_LCLIST))
 545     return lc_set_contains(v2->val.ad, v1->val.lc);
 546
 547   if ((v1->type == T_STRING) && (v2->type == T_STRING))
 548     return patmatch(v2->val.s, v1->val.s);
 549
 550   if ((v1->type == T_IP) && (v2->type == T_NET))
 551     return ipa_in_netX(v1->val.ip, v2->val.net);
 552
 553   if ((v1->type == T_NET) && (v2->type == T_NET))
 554     return net_in_netX(v1->val.net, v2->val.net);
 555
 556   if ((v1->type == T_NET) && (v2->type == T_PREFIX_SET))
 557     return trie_match_net(v2->val.ti, v1->val.net);
 558
 559   if (v2->type != T_SET)
 560     return F_CMP_ERROR;
 561
 562   if (!v2->val.t)
 563     return 0;
 564
 565   /* With integrated Quad<->IP implicit conversion */
 566   if ((v1->type == v2->val.t->from.type) ||
 567       ((v1->type == T_QUAD) && val_is_ip4(&(v2->val.t->from)) && val_is_ip4(&(v2->val.t->to))))
 568     return !!find_tree(v2->val.t, v1);
 569
 570   if (v1->type == T_CLIST)
 571     return clist_match_set(v1->val.ad, v2->val.t);
 572
 573   if (v1->type == T_ECLIST)
 574     return eclist_match_set(v1->val.ad, v2->val.t);
 575
 576   if (v1->type == T_LCLIST)
 577     return lclist_match_set(v1->val.ad, v2->val.t);
 578
 579   if (v1->type == T_PATH)
 580     return as_path_match_set(v1->val.ad, v2->val.t);
 581
 582   return F_CMP_ERROR;
 583 }
 584
 585 /*
 586  * rte_format - format route information
 587  */
 588 static void
 589 rte_format(const struct rte *rte, buffer *buf)
 590 {
 591   if (rte)
 592     buffer_print(buf, "Route [%d] to %N from %s.%s via %s",
 593                  rte->src->global_id, rte->net->n.addr,
 594                  rte->sender->proto->name, rte->sender->name,
 595                  rte->src->proto->name);
 596   else
 597     buffer_puts(buf, "[No route]");
 598 }
 599
 600 static void
 601 rte_block_format(const struct rte *rte, buffer *buf)
 602 {
 603   buffer_print(buf, "Block of routes:");
 604
 605   int i = 0;
 606   while (rte)
 607   {
 608     buffer_print(buf, "%s%d: ", i ? "; " : " ", i);
 609     rte_format(rte, buf);
 610     rte = rte->next;
 611     i++;
 612   }
 613 }
 614
 615 /*
 616  * val_format - format filter value
 617  */
 618 void
 619 val_format(const struct f_val *v, buffer *buf)
 620 {
 621   char buf2[1024];
 622   switch (v->type)
 623   {
 624   case T_VOID:  buffer_puts(buf, "(void)"); return;
 625   case T_BOOL:  buffer_puts(buf, v->val.i ? "TRUE" : "FALSE"); return;
 626   case T_INT:   buffer_print(buf, "%u", v->val.i); return;
 627   case T_STRING: buffer_print(buf, "%s", v->val.s); return;
 628   case T_BYTESTRING: bstrbintohex(v->val.bs->data, v->val.bs->length, buf2, 1000, ':'); buffer_print(buf, "%s", buf2); return;
 629   case T_IP:    buffer_print(buf, "%I", v->val.ip); return;
 630   case T_NET:   buffer_print(buf, "%N", v->val.net); return;
 631   case T_PAIR:  buffer_print(buf, "(%u,%u)", v->val.i >> 16, v->val.i & 0xffff); return;
 632   case T_QUAD:  buffer_print(buf, "%R", v->val.i); return;
 633   case T_EC:    ec_format(buf2, v->val.ec); buffer_print(buf, "%s", buf2); return;
 634   case T_LC:    lc_format(buf2, v->val.lc); buffer_print(buf, "%s", buf2); return;
 635   case T_RD:    rd_format(v->val.ec, buf2, 1024); buffer_print(buf, "%s", buf2); return;
 636   case T_PREFIX_SET: trie_format(v->val.ti, buf); return;
 637   case T_SET:   tree_format(v->val.t, buf); return;
 638   case T_ENUM:  buffer_print(buf, "(enum %x)%u", v->type, v->val.i); return;
 639   case T_PATH:  as_path_format(v->val.ad, buf2, 1000); buffer_print(buf, "(path %s)", buf2); return;
 640   case T_CLIST: int_set_format(v->val.ad, 1, -1, buf2, 1000); buffer_print(buf, "(clist %s)", buf2); return;
 641   case T_ECLIST: ec_set_format(v->val.ad, -1, buf2, 1000); buffer_print(buf, "(eclist %s)", buf2); return;
 642   case T_LCLIST: lc_set_format(v->val.ad, -1, buf2, 1000); buffer_print(buf, "(lclist %s)", buf2); return;
 643   case T_PATH_MASK: pm_format(v->val.path_mask, buf); return;
 644   case T_ROUTE: rte_format(v->val.rte, buf); return;
 645   case T_ROUTES_BLOCK: rte_block_format(v->val.rte, buf); return;
 646   default:      buffer_print(buf, "[unknown type %x]", v->type); return;
 647   }
 648 }
 649
 650 char *
 651 val_format_str(struct linpool *lp, const struct f_val *v) {
 652   buffer b;
 653   LOG_BUFFER_INIT(b);
 654   val_format(v, &b);
 655   return lp_strdup(lp, b.start);
 656 }
 657
 658
 659 static char val_dump_buffer[1024];
 660 const char *
 661 val_dump(const struct f_val *v) {
 662   static buffer b = {
 663     .start = val_dump_buffer,
 664     .end = val_dump_buffer + 1024,
 665   };
 666   b.pos = b.start;
 667   val_format(v, &b);
 668   return val_dump_buffer;
 669 }