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