filter/f-util.c

   1 /*
   2  *      Filters: utility functions
   3  *
   4  *      Copyright 1998 Pavel Machek <pavel@ucw.cz>
   5  *                2017 Jan Maria Matejka <mq@ucw.cz>
   6  *
   7  *      Can be freely distributed and used under the terms of the GNU GPL.
   8  */
   9
  10 #include "nest/bird.h"
  11 #include "conf/conf.h"
  12 #include "filter/filter.h"
  13 #include "filter/f-inst.h"
  14 #include "lib/idm.h"
  15 #include "nest/protocol.h"
  16 #include "nest/route.h"
  17
  18 #define P(a,b) ((a<<8) | b)
  19
  20 const char *
  21 filter_name(const struct filter *filter)
  22 {
  23   if (!filter)
  24     return "ACCEPT";
  25   else if (filter == FILTER_REJECT)
  26     return "REJECT";
  27   else if (!filter->sym)
  28     return "(unnamed)";
  29   else
  30     return filter->sym->name;
  31 }
  32
  33 struct filter *
  34 f_new_where(struct f_inst *where)
  35 {
  36   struct f_inst *cond = f_new_inst(FI_CONDITION, where,
  37                                    f_new_inst(FI_DIE, F_ACCEPT),
  38                                    f_new_inst(FI_DIE, F_REJECT));
  39
  40   struct filter *f = cfg_allocz(sizeof(struct filter));
  41   f->root = f_linearize(cond, 0);
  42   return f;
  43 }
  44
  45 static inline int
  46 f_match_signature(const struct f_method *dsc, struct f_inst *args)
  47 {
  48   int i, arg_num = (int) dsc->arg_num;
  49
  50   for (i = 1; args && (i < arg_num); args = args->next, i++)
  51     if (dsc->args_type[i] && (args->type != dsc->args_type[i]) &&
  52         !f_try_const_promotion(args, dsc->args_type[i]))
  53       return 0;
  54
  55   return !args && !(i < arg_num);
  56 }
  57
  58 /* Variant of f_match_signature(), optimized for error reporting */
  59 static inline void
  60 f_match_signature_err(const struct f_method *dsc, struct f_inst *args, int *pos, int *want, int *got)
  61 {
  62   int i, arg_num = (int) dsc->arg_num;
  63
  64   for (i = 1; args && (i < arg_num); args = args->next, i++)
  65     if (dsc->args_type[i] && (args->type != dsc->args_type[i]) &&
  66         !f_try_const_promotion(args, dsc->args_type[i]))
  67       break;
  68
  69   *pos = i;
  70   *want = (i < arg_num) ? dsc->args_type[i] : T_NONE;
  71   *got = args ? args->type : T_NONE;
  72 }
  73
  74 struct f_inst *
  75 f_dispatch_method(struct symbol *sym, struct f_inst *obj, struct f_inst *args, int skip)
  76 {
  77   /* Find match */
  78   for (const struct f_method *dsc = sym->method; dsc; dsc = dsc->next)
  79     if (f_match_signature(dsc, args))
  80       return dsc->new_inst(obj, args);
  81
  82
  83   /* No valid match - format error message */
  84
  85   int best_pos = -1;    /* Longest argument position with partial match */
  86   int best_got = 0;     /* Received type at best partial match position */
  87   int best_count = 0;   /* Number of partial matches at best position */
  88   const int best_max = 8;       /* Max number of reported types */
  89   int best_want[best_max];      /* Expected types at best position */
  90
  91   for (const struct f_method *dsc = sym->method; dsc; dsc = dsc->next)
  92   {
  93     int pos, want, got;
  94     f_match_signature_err(dsc, args, &pos, &want, &got);
  95
  96     /* Ignore shorter match */
  97     if (pos < best_pos)
  98       continue;
  99
 100     /* Found longer match, reset existing results */
 101     if (pos > best_pos)
 102     {
 103       best_pos = pos;
 104       best_got = got;
 105       best_count = 0;
 106     }
 107
 108     /* Skip duplicates */
 109     for (int i = 0; i < best_count; i++)
 110       if (best_want[i] == want)
 111         goto next;
 112
 113     /* Skip if we have enough types */
 114     if (best_count >= best_max)
 115       continue;
 116
 117     /* Add new expected type */
 118     best_want[best_count] = want;
 119     best_count++;
 120   next:;
 121   }
 122
 123   /* There is at least one method */
 124   ASSERT(best_pos >= 0 && best_count > 0);
 125
 126   /* Update best_pos for printing */
 127   best_pos = best_pos - skip + 1;
 128
 129   if (!best_got)
 130     cf_error("Cannot infer type of argument %d of '%s', please assign it to a variable", best_pos, sym->name);
 131
 132   /* Format list of expected types */
 133   buffer tbuf;
 134   STACK_BUFFER_INIT(tbuf, 128);
 135   for (int i = 0; i < best_count; i++)
 136     buffer_print(&tbuf, " / %s", best_want[i] ? f_type_name(best_want[i]) : "any");
 137   char *types = tbuf.start + 3;
 138   char *dots = (best_count >= best_max) || (tbuf.pos == tbuf.end) ? " / ..." : "";
 139
 140   cf_error("Argument %d of '%s' expected %s%s, got %s",
 141            best_pos, sym->name, types, dots, f_type_name(best_got));
 142 }
 143
 144 struct f_inst *
 145 f_dispatch_method_x(const char *name, enum f_type t, struct f_inst *obj, struct f_inst *args)
 146 {
 147   struct sym_scope *scope = f_type_method_scope(t);
 148   struct symbol *sym = cf_find_symbol_scope(scope, name);
 149
 150   if (!sym)
 151     cf_error("Cannot dispatch method '%s'", name);
 152
 153   return f_dispatch_method(sym, obj, args, 0);
 154 }
 155
 156
 157 struct f_inst *
 158 f_for_cycle(struct symbol *var, struct f_inst *term, struct f_inst *block)
 159 {
 160   ASSERT((var->class & ~0xff) == SYM_VARIABLE);
 161   ASSERT(term->next == NULL);
 162
 163   /* Static type check */
 164   if (term->type == T_VOID)
 165     cf_error("Cannot infer type of FOR expression, please assign it to a variable");
 166
 167   enum f_type el_type = f_type_element_type(term->type);
 168   struct sym_scope *scope = el_type ? f_type_method_scope(term->type) : NULL;
 169   struct symbol *ms = scope ? cf_find_symbol_scope(scope, "!for_next") : NULL;
 170
 171   if (!ms)
 172     cf_error("Type %s is not iterable, can't be used in FOR", f_type_name(term->type));
 173
 174   if (var->class != (SYM_VARIABLE | el_type))
 175     cf_error("Loop variable '%s' in FOR must be of type %s, got %s",
 176         var->name, f_type_name(el_type), f_type_name(var->class & 0xff));
 177
 178   /* Push the iterator auxiliary value onto stack */
 179   struct f_inst *iter = term->next = f_new_inst(FI_CONSTANT, (struct f_val) {});
 180
 181   /* Initialize the iterator variable */
 182   iter->next = f_new_inst(FI_CONSTANT, (struct f_val) { .type = el_type });
 183
 184   /* Prepend the loop block with loop beginning instruction */
 185   struct f_inst *loop_start = f_new_inst(FI_FOR_LOOP_START, var);
 186   loop_start->next = block;
 187
 188   return ms->method->new_inst(term, loop_start);
 189 }
 190
 191 struct f_inst *
 192 f_print(struct f_inst *vars, int flush, enum filter_return fret)
 193 {
 194 #define AX(...)  do { struct f_inst *_tmp = f_new_inst(__VA_ARGS__); _tmp->next = output; output = _tmp; } while (0)
 195   struct f_inst *output = NULL;
 196   if (fret != F_NOP)
 197     AX(FI_DIE, fret);
 198
 199   if (flush)
 200     AX(FI_FLUSH);
 201
 202   while (vars)
 203   {
 204     struct f_inst *tmp = vars;
 205     vars = vars->next;
 206     tmp->next = NULL;
 207
 208     AX(FI_PRINT, tmp);
 209   }
 210
 211   return output;
 212 #undef AX
 213 }
 214
 215
 216 #define CA_KEY(n)       n->name, n->fda.type
 217 #define CA_NEXT(n)      n->next
 218 #define CA_EQ(na,ta,nb,tb)      (!strcmp(na,nb) && (ta == tb))
 219 #define CA_FN(n,t)      (mem_hash(n, strlen(n)) ^ (t*0xaae99453U))
 220 #define CA_ORDER        8 /* Fixed */
 221
 222 struct ca_storage {
 223   struct ca_storage *next;
 224   struct f_dynamic_attr fda;
 225   u32 uc;
 226   char name[0];
 227 };
 228
 229 HASH(struct ca_storage) ca_hash;
 230
 231 static struct idm ca_idm;
 232 static struct ca_storage **ca_storage;
 233 static uint ca_storage_max;
 234
 235 static void
 236 ca_free(resource *r)
 237 {
 238   struct custom_attribute *ca = (void *) r;
 239   struct ca_storage *cas = HASH_FIND(ca_hash, CA, ca->name, ca->fda->type);
 240   ASSERT(cas);
 241
 242   ca->name = NULL;
 243   ca->fda = NULL;
 244   if (!--cas->uc) {
 245     uint id = EA_CUSTOM_ID(cas->fda.ea_code);
 246     idm_free(&ca_idm, id);
 247     HASH_REMOVE(ca_hash, CA, cas);
 248     ca_storage[id] = NULL;
 249     mb_free(cas);
 250   }
 251 }
 252
 253 static void
 254 ca_dump(resource *r)
 255 {
 256   struct custom_attribute *ca = (void *) r;
 257   debug("name \"%s\" id 0x%04x ea_type 0x%02x f_type 0x%02x\n",
 258       ca->name, ca->fda->ea_code, ca->fda->type, ca->fda->f_type);
 259 }
 260
 261 static struct resclass ca_class = {
 262   .name = "Custom attribute",
 263   .size = sizeof(struct custom_attribute),
 264   .free = ca_free,
 265   .dump = ca_dump,
 266   .lookup = NULL,
 267   .memsize = NULL,
 268 };
 269
 270 struct custom_attribute *
 271 ca_lookup(pool *p, const char *name, int f_type)
 272 {
 273   int ea_type;
 274
 275   switch (f_type) {
 276     case T_INT:
 277       ea_type = EAF_TYPE_INT;
 278       break;
 279     case T_IP:
 280       ea_type = EAF_TYPE_IP_ADDRESS;
 281       break;
 282     case T_QUAD:
 283       ea_type = EAF_TYPE_ROUTER_ID;
 284       break;
 285     case T_PATH:
 286       ea_type = EAF_TYPE_AS_PATH;
 287       break;
 288     case T_CLIST:
 289       ea_type = EAF_TYPE_INT_SET;
 290       break;
 291     case T_ECLIST:
 292       ea_type = EAF_TYPE_EC_SET;
 293       break;
 294     case T_LCLIST:
 295       ea_type = EAF_TYPE_LC_SET;
 296       break;
 297     case T_STRING:
 298       ea_type = EAF_TYPE_STRING;
 299       break;
 300     case T_BYTESTRING:
 301       ea_type = EAF_TYPE_OPAQUE;
 302       break;
 303     default:
 304       cf_error("Custom route attribute of unsupported type");
 305   }
 306
 307   static int inited = 0;
 308   if (!inited) {
 309     idm_init(&ca_idm, config_pool, 8);
 310     HASH_INIT(ca_hash, config_pool, CA_ORDER);
 311
 312     ca_storage_max = 256;
 313     ca_storage = mb_allocz(config_pool, sizeof(struct ca_storage *) * ca_storage_max);
 314
 315     inited++;
 316   }
 317
 318   struct ca_storage *cas = HASH_FIND(ca_hash, CA, name, ea_type);
 319   if (cas) {
 320     cas->uc++;
 321   } else {
 322
 323     uint id = idm_alloc(&ca_idm);
 324
 325     if (id >= EA_CUSTOM_BIT)
 326       cf_error("Too many custom attributes.");
 327
 328     if (id >= ca_storage_max) {
 329       ca_storage_max *= 2;
 330       ca_storage = mb_realloc(ca_storage, sizeof(struct ca_storage *) * ca_storage_max * 2);
 331     }
 332
 333     cas = mb_allocz(config_pool, sizeof(struct ca_storage) + strlen(name) + 1);
 334     cas->fda = f_new_dynamic_attr(ea_type, f_type, EA_CUSTOM(id));
 335     cas->uc = 1;
 336
 337     strcpy(cas->name, name);
 338     ca_storage[id] = cas;
 339
 340     HASH_INSERT(ca_hash, CA, cas);
 341   }
 342
 343   struct custom_attribute *ca = ralloc(p, &ca_class);
 344   ca->fda = &(cas->fda);
 345   ca->name = cas->name;
 346   return ca;
 347 }
 348
 349 const char *
 350 ea_custom_name(uint ea)
 351 {
 352   uint id = EA_CUSTOM_ID(ea);
 353   if (id >= ca_storage_max)
 354     return NULL;
 355
 356   if (!ca_storage[id])
 357     return NULL;
 358
 359   return ca_storage[id]->name;
 360 }
 361