maskmap/maskmap.c

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