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