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 inline int
 150 pmi_same(const struct f_path_mask_item *mi1, const struct f_path_mask_item *mi2)
 151 {
 152   if (mi1->kind != mi2->kind)
 153     return 0;
 154
 155   switch (mi1->kind) {
 156     case PM_ASN:
 157       if (mi1->asn != mi2->asn)
 158         return 0;
 159       break;
 160     case PM_ASN_EXPR:
 161       if (!f_same(mi1->expr, mi2->expr))
 162         return 0;
 163       break;
 164     case PM_ASN_RANGE:
 165       if (mi1->from != mi2->from)
 166         return 0;
 167       if (mi1->to != mi2->to)
 168         return 0;
 169       break;
 170   }
 171
 172   return 1;
 173 }
 174
 175 static int
 176 pm_same(const struct f_path_mask *m1, const struct f_path_mask *m2)
 177 {
 178   if (m1->len != m2->len)
 179
 180   for (uint i=0; i<m1->len; i++)
 181     if (!pmi_same(&(m1->item[i]), &(m2->item[i])))
 182       return 0;
 183
 184   return 1;
 185 }
 186
 187 /**
 188  * val_same - compare two values
 189  * @v1: first value
 190  * @v2: second value
 191  *
 192  * Compares two values and returns 1 if they are same and 0 if not.
 193  * Comparison of values of different types is valid and returns 0.
 194  */
 195 int
 196 val_same(const struct f_val *v1, const struct f_val *v2)
 197 {
 198   int rc;
 199
 200   rc = val_compare(v1, v2);
 201   if (rc != F_CMP_ERROR)
 202     return !rc;
 203
 204   if (v1->type != v2->type)
 205     return 0;
 206
 207   switch (v1->type) {
 208   case T_PATH_MASK:
 209     return pm_same(v1->val.path_mask, v2->val.path_mask);
 210   case T_PATH_MASK_ITEM:
 211     return pmi_same(&(v1->val.pmi), &(v2->val.pmi));
 212   case T_PATH:
 213   case T_CLIST:
 214   case T_ECLIST:
 215   case T_LCLIST:
 216     return adata_same(v1->val.ad, v2->val.ad);
 217   case T_SET:
 218     return same_tree(v1->val.t, v2->val.t);
 219   case T_PREFIX_SET:
 220     return trie_same(v1->val.ti, v2->val.ti);
 221   default:
 222     bug("Invalid type in val_same(): %x", v1->type);
 223   }
 224 }
 225
 226 int
 227 clist_set_type(const struct f_tree *set, struct f_val *v)
 228 {
 229   switch (set->from.type)
 230   {
 231   case T_PAIR:
 232     v->type = T_PAIR;
 233     return 1;
 234
 235   case T_QUAD:
 236     v->type = T_QUAD;
 237     return 1;
 238
 239   case T_IP:
 240     if (val_is_ip4(&(set->from)) && val_is_ip4(&(set->to)))
 241     {
 242       v->type = T_QUAD;
 243       return 1;
 244     }
 245     /* Fall through */
 246   default:
 247     v->type = T_VOID;
 248     return 0;
 249   }
 250 }
 251
 252 static int
 253 clist_match_set(const struct adata *clist, const struct f_tree *set)
 254 {
 255   if (!clist)
 256     return 0;
 257
 258   struct f_val v;
 259   if (!clist_set_type(set, &v))
 260     return F_CMP_ERROR;
 261
 262   u32 *l = (u32 *) clist->data;
 263   u32 *end = l + clist->length/4;
 264
 265   while (l < end) {
 266     v.val.i = *l++;
 267     if (find_tree(set, &v))
 268       return 1;
 269   }
 270   return 0;
 271 }
 272
 273 static int
 274 eclist_match_set(const struct adata *list, const struct f_tree *set)
 275 {
 276   if (!list)
 277     return 0;
 278
 279   if (!eclist_set_type(set))
 280     return F_CMP_ERROR;
 281
 282   struct f_val v;
 283   u32 *l = int_set_get_data(list);
 284   int len = int_set_get_size(list);
 285   int i;
 286
 287   v.type = T_EC;
 288   for (i = 0; i < len; i += 2) {
 289     v.val.ec = ec_get(l, i);
 290     if (find_tree(set, &v))
 291       return 1;
 292   }
 293
 294   return 0;
 295 }
 296
 297 static int
 298 lclist_match_set(const struct adata *list, const struct f_tree *set)
 299 {
 300   if (!list)
 301     return 0;
 302
 303   if (!lclist_set_type(set))
 304     return F_CMP_ERROR;
 305
 306   struct f_val v;
 307   u32 *l = int_set_get_data(list);
 308   int len = int_set_get_size(list);
 309   int i;
 310
 311   v.type = T_LC;
 312   for (i = 0; i < len; i += 3) {
 313     v.val.lc = lc_get(l, i);
 314     if (find_tree(set, &v))
 315       return 1;
 316   }
 317
 318   return 0;
 319 }
 320
 321 const struct adata *
 322 clist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos)
 323 {
 324   if (!list)
 325     return NULL;
 326
 327   int tree = (set->type == T_SET);      /* 1 -> set is T_SET, 0 -> set is T_CLIST */
 328   struct f_val v;
 329   if (tree)
 330     clist_set_type(set->val.t, &v);
 331   else
 332     v.type = T_PAIR;
 333
 334   int len = int_set_get_size(list);
 335   u32 *l = int_set_get_data(list);
 336   u32 tmp[len];
 337   u32 *k = tmp;
 338   u32 *end = l + len;
 339
 340   while (l < end) {
 341     v.val.i = *l++;
 342     /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
 343     if ((tree ? !!find_tree(set->val.t, &v) : int_set_contains(set->val.ad, v.val.i)) == pos)
 344       *k++ = v.val.i;
 345   }
 346
 347   uint nl = (k - tmp) * sizeof(u32);
 348   if (nl == list->length)
 349     return list;
 350
 351   struct adata *res = adata_empty(pool, nl);
 352   memcpy(res->data, tmp, nl);
 353   return res;
 354 }
 355
 356 const struct adata *
 357 eclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos)
 358 {
 359   if (!list)
 360     return NULL;
 361
 362   int tree = (set->type == T_SET);      /* 1 -> set is T_SET, 0 -> set is T_CLIST */
 363   struct f_val v;
 364
 365   int len = int_set_get_size(list);
 366   u32 *l = int_set_get_data(list);
 367   u32 tmp[len];
 368   u32 *k = tmp;
 369   int i;
 370
 371   v.type = T_EC;
 372   for (i = 0; i < len; i += 2) {
 373     v.val.ec = ec_get(l, i);
 374     /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
 375     if ((tree ? !!find_tree(set->val.t, &v) : ec_set_contains(set->val.ad, v.val.ec)) == pos) {
 376       *k++ = l[i];
 377       *k++ = l[i+1];
 378     }
 379   }
 380
 381   uint nl = (k - tmp) * sizeof(u32);
 382   if (nl == list->length)
 383     return list;
 384
 385   struct adata *res = adata_empty(pool, nl);
 386   memcpy(res->data, tmp, nl);
 387   return res;
 388 }
 389
 390 const struct adata *
 391 lclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos)
 392 {
 393   if (!list)
 394     return NULL;
 395
 396   int tree = (set->type == T_SET);      /* 1 -> set is T_SET, 0 -> set is T_CLIST */
 397   struct f_val v;
 398
 399   int len = int_set_get_size(list);
 400   u32 *l = int_set_get_data(list);
 401   u32 tmp[len];
 402   u32 *k = tmp;
 403   int i;
 404
 405   v.type = T_LC;
 406   for (i = 0; i < len; i += 3) {
 407     v.val.lc = lc_get(l, i);
 408     /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
 409     if ((tree ? !!find_tree(set->val.t, &v) : lc_set_contains(set->val.ad, v.val.lc)) == pos)
 410       k = lc_copy(k, l+i);
 411   }
 412
 413   uint nl = (k - tmp) * sizeof(u32);
 414   if (nl == list->length)
 415     return list;
 416
 417   struct adata *res = adata_empty(pool, nl);
 418   memcpy(res->data, tmp, nl);
 419   return res;
 420 }
 421
 422 /**
 423  * val_in_range - implement |~| operator
 424  * @v1: element
 425  * @v2: set
 426  *
 427  * Checks if @v1 is element (|~| operator) of @v2.
 428  */
 429 int
 430 val_in_range(const struct f_val *v1, const struct f_val *v2)
 431 {
 432   if ((v1->type == T_PATH) && (v2->type == T_PATH_MASK))
 433     return as_path_match(v1->val.ad, v2->val.path_mask);
 434
 435   if ((v1->type == T_INT) && (v2->type == T_PATH))
 436     return as_path_contains(v2->val.ad, v1->val.i, 1);
 437
 438   if (((v1->type == T_PAIR) || (v1->type == T_QUAD)) && (v2->type == T_CLIST))
 439     return int_set_contains(v2->val.ad, v1->val.i);
 440   /* IP->Quad implicit conversion */
 441   if (val_is_ip4(v1) && (v2->type == T_CLIST))
 442     return int_set_contains(v2->val.ad, ipa_to_u32(v1->val.ip));
 443
 444   if ((v1->type == T_EC) && (v2->type == T_ECLIST))
 445     return ec_set_contains(v2->val.ad, v1->val.ec);
 446
 447   if ((v1->type == T_LC) && (v2->type == T_LCLIST))
 448     return lc_set_contains(v2->val.ad, v1->val.lc);
 449
 450   if ((v1->type == T_STRING) && (v2->type == T_STRING))
 451     return patmatch(v2->val.s, v1->val.s);
 452
 453   if ((v1->type == T_IP) && (v2->type == T_NET))
 454     return ipa_in_netX(v1->val.ip, v2->val.net);
 455
 456   if ((v1->type == T_NET) && (v2->type == T_NET))
 457     return net_in_netX(v1->val.net, v2->val.net);
 458
 459   if ((v1->type == T_NET) && (v2->type == T_PREFIX_SET))
 460     return trie_match_net(v2->val.ti, v1->val.net);
 461
 462   if (v2->type != T_SET)
 463     return F_CMP_ERROR;
 464
 465   /* With integrated Quad<->IP implicit conversion */
 466   if ((v1->type == v2->val.t->from.type) ||
 467       ((v1->type == T_QUAD) && val_is_ip4(&(v2->val.t->from)) && val_is_ip4(&(v2->val.t->to))))
 468     return !!find_tree(v2->val.t, v1);
 469
 470   if (v1->type == T_CLIST)
 471     return clist_match_set(v1->val.ad, v2->val.t);
 472
 473   if (v1->type == T_ECLIST)
 474     return eclist_match_set(v1->val.ad, v2->val.t);
 475
 476   if (v1->type == T_LCLIST)
 477     return lclist_match_set(v1->val.ad, v2->val.t);
 478
 479   if (v1->type == T_PATH)
 480     return as_path_match_set(v1->val.ad, v2->val.t);
 481
 482   return F_CMP_ERROR;
 483 }
 484
 485 /*
 486  * val_format - format filter value
 487  */
 488 void
 489 val_format(const struct f_val *v, buffer *buf)
 490 {
 491   char buf2[1024];
 492   switch (v->type)
 493   {
 494   case T_VOID:  buffer_puts(buf, "(void)"); return;
 495   case T_BOOL:  buffer_puts(buf, v->val.i ? "TRUE" : "FALSE"); return;
 496   case T_INT:   buffer_print(buf, "%u", v->val.i); return;
 497   case T_STRING: buffer_print(buf, "%s", v->val.s); return;
 498   case T_IP:    buffer_print(buf, "%I", v->val.ip); return;
 499   case T_NET:   buffer_print(buf, "%N", v->val.net); return;
 500   case T_PAIR:  buffer_print(buf, "(%u,%u)", v->val.i >> 16, v->val.i & 0xffff); return;
 501   case T_QUAD:  buffer_print(buf, "%R", v->val.i); return;
 502   case T_EC:    ec_format(buf2, v->val.ec); buffer_print(buf, "%s", buf2); return;
 503   case T_LC:    lc_format(buf2, v->val.lc); buffer_print(buf, "%s", buf2); return;
 504   case T_RD:    rd_format(v->val.ec, buf2, 1024); buffer_print(buf, "%s", buf2); return;
 505   case T_PREFIX_SET: trie_format(v->val.ti, buf); return;
 506   case T_SET:   tree_format(v->val.t, buf); return;
 507   case T_ENUM:  buffer_print(buf, "(enum %x)%u", v->type, v->val.i); return;
 508   case T_PATH:  as_path_format(v->val.ad, buf2, 1000); buffer_print(buf, "(path %s)", buf2); return;
 509   case T_CLIST: int_set_format(v->val.ad, 1, -1, buf2, 1000); buffer_print(buf, "(clist %s)", buf2); return;
 510   case T_ECLIST: ec_set_format(v->val.ad, -1, buf2, 1000); buffer_print(buf, "(eclist %s)", buf2); return;
 511   case T_LCLIST: lc_set_format(v->val.ad, -1, buf2, 1000); buffer_print(buf, "(lclist %s)", buf2); return;
 512   case T_PATH_MASK: pm_format(v->val.path_mask, buf); return;
 513   default:      buffer_print(buf, "[unknown type %x]", v->type); return;
 514   }
 515 }
 516
 517 static char val_dump_buffer[1024];
 518 const char *
 519 val_dump(const struct f_val *v) {
 520   static buffer b = {
 521     .start = val_dump_buffer,
 522     .end = val_dump_buffer + 1024,
 523   };
 524   b.pos = b.start;
 525   val_format(v, &b);
 526   return val_dump_buffer;
 527 }
 528