maskmap/maskmap.c

   1
   2
   3 /*---------- operations on AddrMap_Entry ----------*/
   4
   5 static void ame_init(AddrMap_Entry *ame) {
   6   ame->prefixlen= -1;
   7   ame->prefix= 0;
   8   ame->data= 0;
   9 }
  10
  11 static unsigned ame_clear_unwanted(AddrMap_Entry *ame, int bytes) {
  12   /* returns non-0 iff some bits were cleared */
  13   int sparebits;
  14   unsigned result, sparemask;
  15   Byte *datap;
  16
  17   sparebits= bytes * 8 - ame->prefixlen;
  18   if (!sparebits) return 0;
  19
  20   sparemask= (1u << sparebits) - 1;
  21   datap= &ame->prefix[bytes-1];
  22
  23   result= *datap & sparemask;
  24   *datap &= ~sparemask;
  25
  26   return result;
  27 }
  28
  29 static int ame_parsekey(Tcl_Interp *ip, AddrMap_Entry *ame,
  30                         Tcl_Obj *prefixo, Tcl_Obj *prefixbitso,
  31                         int inmap) {
  32  /* *ame should be blank entry; after exit (even error exit) it will be valid
  33   * - on errors, it will be blank.  inmap is 1 if we're parsing an existing
  34   * map or 0 if it's an entry to be added or modified. */
  35   HBytes_Value prefix;
  36   int suppliedprefixbytes, prefixbits, wantprefixbytes;
  37   const Byte *data;
  38   int rc;
  39
  40   hbytes_empty(&prefix);
  41
  42   rc= pat_hb(ip,prefixo,&prefix);  if (rc) goto x_rc;
  43   rc= pat_int(ip,prefixbitso,&prefixbits);  if (rc) goto x_rc;
  44
  45   wantprefixbytes= prefix_bytes(prefixbits);
  46   suppliedprefixbytes= hbytes_len(&prefix);
  47
  48   if (suppliedprefixbytes < wantprefixbytes) {
  49     rc= staticerr(ip, "addr-map entry PREFIX too short for PREFIX-LEN",
  50                   "HBYTES ADDRMAP SYNTAX UNDERRUN");
  51     goto x_rc;
  52   }
  53   if (inmap && suppliedprefixbytes > wantprefixbytes) {
  54     rc= staticerr(ip, "addr-map existing entry PREFIX too long for PREFIX-LEN",
  55                   "HBYTES ADDRMAP SYNTAX OVERRUN");
  56     goto x_rc;
  57   }
  58
  59   ame->prefixlen= prefixbits;
  60   ame->prefix= TALLOC(wantprefixbytes);  assert(ame->prefix);
  61   memcpy(ame->prefix, data, wantprefixbytes);
  62
  63   if (ame_clear_unwanted(ame, wantprefixbytes)) {
  64     rc= staticerr(ip, "addr-map entry PREFIX contains bits excluded"
  65                   " by PREFIX-LEN", "HBYTES ADDRMAP SYNTAX EXCLBITS");
  66     goto x_rc;
  67   }
  68
  69   return TCL_OK;
  70
  71  x_rc:
  72   ame_free(ame);
  73   return rc;
  74 }
  75
  76 static int ame_contains(const AddrMap_Entry *ref, const Byte *addr, int len) {
  77   int directbytes, leftoverbits;
  78
  79   assert(len >= ref->prefixlen);
  80
  81   directbytes= ref->prefixlen / 8;
  82   if (memcmp(ref->prefix, addr, directbytes)) return 0;
  83
  84   leftoverbits= ref->prefixlen % 8;
  85   if (leftoverbits)
  86     if ((addr[directbytes] & (0xffu << leftoverbits))
  87         != search->prefix[directbytes])
  88       return 0;
  89
  90   return 1;
  91 }
  92
  93 static int ame_compare(const AddrMap_Entry *a, const AddrMap_Entry *b) {
  94   /*    +2 =    a   covers later range of address space than  b
  95    *    +1 =    a   wholly contains but is not equal to       b
  96    *     0 =    a   is identical to                           b
  97    *    -1 =    b   wholly contains but is not equal to       a
  98    *    -2 =    b   covers later range of address space than  a
  99    */
 100   int al= a->prefixlen;
 101   int bl= b->prefixlen;
 102   int ml, d;
 103
 104   if (al==bl) { ml=al; }
 105   else if (al<bl) { ml=al; if (ame_contains(a,b->prefix,bl)) return +1; }
 106   else if (bl<al) { ml=bl; if (ame_contains(b,a->prefix,al)) return -1; }
 107
 108   d= memcmp(b->prefix, a->prefix, prefix_bytes(ml));
 109   return (d > 0 ? +2 :
 110           d < 0 ? -2 :
 111           0);
 112 }
 113
 114 /*---------- searching maps ----------*/
 115
 116 typedef enum {
 117   sr_notfound,
 118   sr_exact,
 119   sr_inbig,
 120   sr_aroundsmall
 121 } Search_Result;
 122
 123 static int
 124 am_binarychop(AddrMap_Value *am, int low_oreq, int high_strict, void *u,
 125               int (*test)(AddrMap_Entry *am, void *u) /* -ve => look left */,
 126               int *found_r) {
 127   int mid, cmp;
 128
 129   for (;;) {
 130     if (high_strict <= low_oreq) {
 131       assert(high_strict == low_oreq);
 132       *found_r= 0;
 133       return high_strict;
 134     }
 135
 136     mid= (high_strict + low_oreq) / 2;
 137     cmp= test(&am->entries[mid], u);
 138
 139     if (!cmp) {
 140       *found_r= 1;
 141       return mid;
 142     }
 143
 144     if (cmp < 0)
 145       high_strict= mid;
 146     else
 147       low_oreq= mid+1;
 148   }
 149 }
 150
 151 struct am_search_u {
 152   int forbid_aroundsmall;
 153   AddrMap_Entry proposed;
 154   Search_Result sr;
 155 };
 156
 157 static int
 158 am_search_binchoptest(AddrMap_Entry *ame, void *u_v) {
 159   struct am_search_u *u= u_v;
 160   int cmp;
 161
 162   cmp= ame_compare(&u.proposed, ame);
 163   switch (cmp) {
 164   case -1:  u->sr= sr_inbig;        return  0;
 165   case  0:  u->sr= sr_exact;        return  0;
 166   case +1:  u->sr= sr_aroundsmall;  return  0;
 167   default:                          return cmp;
 168   }
 169 }
 170
 171 static Search_Result
 172 am_search(AddrMap_Value *am, const AddrMap_Entry *proposed, int *place_r) {
 173   int place, found;
 174   struct am_search_u u;
 175
 176   u.forbid_aroundsmall= forbid_aroundsmall;
 177   u.proposed= proposed;
 178   u.sr= sr_notfound;
 179
 180   *place_r= am_binarychop(am, 0, am.used, &u, am_search_binchoptest, &found);
 181
 182   assert(!!found == (u.sr != sr_notfound));
 183   return u.sr;
 184 }
 185
 186 /*---------- useful operations on AddrMap_Value etc. ----------*/
 187
 188 /*---------- amendment (complex algorithm) ----------*/
 189
 190 struct am_amend_aroundsmall_u {
 191   AddrMap_Entry *new;
 192   int sign;
 193 };
 194
 195
 196 static int
 197 am_amend_aroundsmall_binchoptest(AddrMap_Entry *search, void *u_v) {
 198   struct am_amend_aroundsmall_u *u= u_v;
 199
 200   cmp= u->sign * ame_compare(search, u->new);
 201
 202   switch (cmp) {
 203   case +2:  return -u->sign;
 204   case +1:  return +u->sign;
 205   default:  abort();
 206   }
 207 }
 208
 209 int do_addrmap_amend(ClientData cd, Tcl_Interp *ip,
 210                      AddrMap_Var map, Tcl_Obj *prefix,
 211                      Tcl_Obj *preflen, Tcl_Obj *data) {
 212   AddrMap_Value *am= map.am;
 213   AddrMap_Entry new, *fragment;
 214   AddrMap_Entry *breaking, *replacements;
 215   int rc, insertat, findend, cmp, nreplacements, new_used;
 216   struct am_amend_aroundsmall_u u;
 217
 218   ame_init(&new);
 219
 220   rc= ame_parsekey(ip,&new,prefix,preflen,0);  if (rc) return rc;
 221
 222   sr= am_search(am, &new, &searched);
 223
 224   replacements= &new;
 225   nreplacements= 1;
 226   replace_start= searched;
 227   replace_end= searched;
 228
 229   switch (sr) {
 230
 231   case sr_notfound:
 232     break;
 233
 234   case sr_exact:
 235     replace_end= searched+1;
 236     break;
 237
 238   case sr_aroundsmall:
 239     u.ame= new;
 240     u.sign= -1;
 241     replace_start= am_binarychop(am, 0, searched, &u,
 242                                  am_amend_aroundsmall_binchoptest, &dummy);
 243     u.sign= +1;
 244     replace_end= am_binarychop(am, searched+1, am.used, &u,
 245                                  am_amend_aroundsmall_binchoptest, &dummy);
 246     break;
 247
 248   case sr_inbig:
 249     /* Urgh, we need to break it up.  This produces
 250      *   - innermost prefix (the new one) as specified
 251      *   - one for each bitlength
 252      *       <= innermost
 253      *        > outermost (the existing one)
 254      *     each one specifying the outermost prefix plus zero, one,
 255      *     two, etc. bits of the innermost followed by one bit
 256      *     opposite to the innermost, with the outermost's data
 257      * Eg, if we have ff/8=>A and want to amend so that ffff/16=>B
 258      * then we replace ff/8 with ff0/9=>A ff8/10=>A ffc/11=>A ...
 259      * ... fff8/14=>A fffc/15=>A fffe/16=>A ffff/16=>B.
 260      */
 261
 262     breaking= &am.entries[searched];
 263     nreplacements= new.prefix - breaking->prefixlen + 1;
 264     replacements= TALLOC(sizeof(*replacements) * nreplacements);
 265
 266     for (fragmentlen= breaking->prefixlen + 1,
 267            left_insert= 0, right_insert= nreplacements;
 268          fragmentlen <= new.prefix;
 269          fragmentlen++) {
 270       int fragmentbytes;
 271
 272       fragmentbytes= prefix_bytes(fragmentlen)
 273       fragment->prefixlen= fragmentlen;
 274       fragment->prefix= TALLOC(fragmentbytes);
 275       memcpy(fragment->prefix, new.prefix, fragmentbytes);
 276       ame_clear_unwanted(fragment, fragmentbytes);
 277
 278       fragment->prefix[fragmentbytes] ^=
 279         0x80u >> ((fragmentlen+7) & 7);
 280
 281       switch (ame_compare(&fragment, &new)) {
 282       case -2:  replacements[left_insert++]=  fragment;  break;
 283       case +2:  replacements[--right_insert]= fragment;  break;
 284       default: abort();
 285       }
 286     }
 287     assert(left_insert == right_insert-1);
 288     replacements[left_insert]= new;
 289     ame_init(&new);
 290
 291     replace_end= searched+1;
 292     break;
 293
 294   }
 295
 296   new_used= am.used - (replace_end - replace_start) + nreplacements;
 297
 298   if (new_used > am.space)
 299     am_reallocentries(am, new_used * 2);
 300
 301   for (scan=replacements, i=0;
 302        i < nreplacements;
 303        scan++, i++) {
 304     scan->data= data;
 305     Tcl_IncrRefCount(scan->data);
 306   }
 307
 308   for (i= replace_start, scan= am.entries+i;
 309        i < replace_end;
 310        i++, scan++) {
 311     ame_free(scan);
 312   }
 313
 314   memmove(am.entries + replace_start + nreplacements,
 315           am.entries + replace_end,
 316           sizeof(*am.entries) * (am.used - replace_end));
 317
 318   memcpy(am.entries + replace_start,
 319          replacements,
 320          sizeof(*am.entries) * nreplacements);
 321
 322   am.used= new_used;
 323   if (replacements != &new)
 324     /* we don't bother freeing the actual array elements because
 325      * if replacements!=&new the array is only full if we're
 326      * committed and have already copied the values into the actual
 327      * AddrMap_Value. */
 328     TFREE(replacements);
 329
 330   return TCL_OK;
 331 }
 332
 333 /*---------- other substantial operations on mask maps ----------*/
 334
 335 int do_addrmap_lookup(ClientData cd, Tcl_Interp *ip,
 336                       Tcl_Obj *mapo, HBytes_Value addrhb, Tcl_Obj *def,
 337                       Tcl_Obj **result) {
 338   AddrMap_Value *am= (void*)&mapo->internalRep;
 339   const Byte *addr= hbytes_data(&addrhb);
 340   int addrbytes= hbytes_len(&addrhb);
 341   int i, addrbits, place;
 342   Search_Result sr;
 343
 344   addrbits= addrbytes * 8;
 345   sr= am_search(am, addr, addrbits, &place);
 346
 347   switch (sr) {
 348
 349   case sr_notfound:
 350     if (!def) return staticerr(ip, "address not found in addr-map",
 351                                "HBYTES ADDRMAP NOMATCH");
 352     *result= def;
 353     break;
 354
 355   case sr_aroundsmall:
 356     return staticerr(ip, "address shorter than mask in map",
 357                      "HBYTES ADDRMAP UNDERRUN");
 358
 359   case sr_exact:
 360   case sr_inbig:
 361     *result= am.entres[place].data;
 362     break;
 363
 364   }
 365
 366   return TCL_OK;
 367 }
 368
 369 /*---------- Tcl type and arg parsing functions ----------*/
 370