X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=chiark-tcl.git;a=blobdiff_plain;f=maskmap%2Fmaskmap.c;h=ad141a925ca38123224a0cd21cb0ccd2b420cdff;hp=9c92810f0197c4a5d8aea6356ba72ba36e5bb2f5;hb=5dca360f2da544c9b6baf9d18ad8cd0b0e073e60;hpb=0bcca45f296b613b1f1449d232f43eb0ada0014b diff --git a/maskmap/maskmap.c b/maskmap/maskmap.c index 9c92810..ad141a9 100644 --- a/maskmap/maskmap.c +++ b/maskmap/maskmap.c @@ -1,49 +1,59 @@ /* + * maskmap - Tcl extension for address mask map data structures + * Copyright 2006 Ian Jackson + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA + * 02110-1301, USA. */ -#include +#include "chiark_tcl_hbytes.h" -#include "tables.h" -#include "hbytes.h" +/*---------- operations on AddrMap_Entry ----------*/ -typedef struct { - int prefixlen; /* there may be some empty slots with prefixlen==-1 at end */ - Byte *prefix; /* ceil(prefixlen/8) bytes */ - Tcl_Obj *data; -} MaskMap_Entry; +static void ame_init(AddrMap_Entry *ame) { + ame->prefixlen= -1; + ame->prefix= 0; + ame->data= 0; +} -struct MaskMap_Value { - int allocd; - MaskMap_Entry *entries; -}; /* overlays internalRep */ +static unsigned ame_clear_unwanted(AddrMap_Entry *ame, int bytes) { + /* returns non-0 iff some bits were cleared */ + int sparebits; + unsigned result, sparemask; + Byte *datap; -/*---------- useful stuff ----------*/ + sparebits= bytes * 8 - ame->prefixlen; + if (!sparebits) return 0; -static int prefix_bytes (int prefixlen) { - return (prefixlen + 7)/8; -} + sparemask= (1u << sparebits) - 1; + datap= &ame->prefix[bytes-1]; -/*---------- operations on MaskMap_Entry ----------*/ + result= *datap & sparemask; + *datap &= ~sparemask; -static void mme_init(MaskMap_Entry *mme) { - mme->prefixlen= -1; - mme->prefix= 0; - mme->data= 0; + return result; } -static void mme_free(MaskMap_Entry *mme) { - TFREE(mme->prefix); mme->prefix=0; - if (mme->data) { Tcl_DecrRefCount(mme->data); mme->data=0; } -} - -static int mme_parsekey(Tcl_Interp *ip, MaskMap_Entry *mme, +static int ame_parsekey(Tcl_Interp *ip, AddrMap_Entry *ame, Tcl_Obj *prefixo, Tcl_Obj *prefixbitso, int inmap) { - /* *mme should be blank entry; after exit (even error exit) it will be valid + /* *ame should be blank entry; after exit (even error exit) it will be valid * - on errors, it will be blank. inmap is 1 if we're parsing an existing * map or 0 if it's an entry to be added or modified. */ HBytes_Value prefix; - int suppliedprefixbytes, prefixbits, wantprefixbytes, sparebits; + int suppliedprefixbytes, prefixbits, wantprefixbytes; const Byte *data; int rc; @@ -56,252 +66,325 @@ static int mme_parsekey(Tcl_Interp *ip, MaskMap_Entry *mme, suppliedprefixbytes= hbytes_len(&prefix); if (suppliedprefixbytes < wantprefixbytes) { - rc= staticerr(ip, "mask-map entry PREFIX too short for PREFIX-LEN", - "HBYTES MASKMAP SYNTAX UNDERRUN"); + rc= staticerr(ip, "addr-map entry PREFIX too short for PREFIX-LEN", + "HBYTES ADDRMAP SYNTAX UNDERRUN"); goto x_rc; } if (inmap && suppliedprefixbytes > wantprefixbytes) { - rc= staticerr(ip, "mask-map existing entry PREFIX too long for PREFIX-LEN", - "HBYTES MASKMAP SYNTAX OVERRUN"); + rc= staticerr(ip, "addr-map existing entry PREFIX too long for PREFIX-LEN", + "HBYTES ADDRMAP SYNTAX OVERRUN"); goto x_rc; } - sparebits= wantprefixbytes*8 - prefixbits; - data= hbytes_data(&prefix); - if (sparebits && (data[wantprefixbytes-1] & ((1u << sparebits)-1))) { - rc= staticerr(ip, "mask-map entry PREFIX contains bits excluded" - " by PREFIX-LEN", "HBYTES MASKMAP SYNTAX EXCLBITS"); + + ame->prefixlen= prefixbits; + ame->prefix= TALLOC(wantprefixbytes); assert(ame->prefix); + memcpy(ame->prefix, data, wantprefixbytes); + + if (ame_clear_unwanted(ame, wantprefixbytes)) { + rc= staticerr(ip, "addr-map entry PREFIX contains bits excluded" + " by PREFIX-LEN", "HBYTES ADDRMAP SYNTAX EXCLBITS"); goto x_rc; } - mme->prefixlen= prefixbits; - mme->prefix= TALLOC(wantprefixbytes); assert(mme->prefix); - memcpy(mme->prefix, data, wantprefixbytes); return TCL_OK; x_rc: - mme_free(mme); + ame_free(ame); return rc; } -static int mme_ordercompare(MaskMap_Entry *a, MaskMap_Entry *b) { - if (a->prefixlen != b->prefixlen) - return a->prefixlen - b->prefixlen; - else - return memcmp(b->prefix, a->prefix, prefix_bytes(a->prefixlen)); -} - -/*---------- useful operations on MaskMap_Value etc. ----------*/ - -static int mm_count(const MaskMap_Value *mm) { - int i; - for (i=0; iallocd && mm->entries[i].prefixlen != -1; i++); - return i; -} - -static void mm_init(MaskMap_Value *mm) { - mm->allocd= 0; - mm->entries= 0; +static int ame_contains(const AddrMap_Entry *ref, const Byte *addr, int len) { + int directbytes, leftoverbits; + + assert(len >= ref->prefixlen); + + directbytes= ref->prefixlen / 8; + if (memcmp(ref->prefix, addr, directbytes)) return 0; + + leftoverbits= ref->prefixlen % 8; + if (leftoverbits) + if ((addr[directbytes] & (0xffu << leftoverbits)) + != search->prefix[directbytes]) + return 0; + + return 1; +} + +static int ame_compare(const AddrMap_Entry *a, const AddrMap_Entry *b) { + /* +2 = a covers later range of address space than b + * +1 = a wholly contains but is not equal to b + * 0 = a is identical to b + * -1 = b wholly contains but is not equal to a + * -2 = b covers later range of address space than a + */ + int al= a->prefixlen; + int bl= b->prefixlen; + int ml, d; + + if (al==bl) { ml=al; } + else if (alprefix,bl)) return +1; } + else if (blprefix,al)) return -1; } + + d= memcmp(b->prefix, a->prefix, prefix_bytes(ml)); + return (d > 0 ? +2 : + d < 0 ? -2 : + 0); } -static void mm_reallocentries(MaskMap_Value *mm, int len) { - int i; - MaskMap_Entry *newentries, *clear; +/*---------- searching maps ----------*/ - assert(len >= mm->allocd); - if (!len) return; +typedef enum { + sr_notfound, + sr_exact, + sr_inbig, + sr_aroundsmall +} Search_Result; - newentries= TREALLOC(mm->entries, sizeof(*newentries)*len); - assert(newentries); +static int +am_binarychop(AddrMap_Value *am, int low_oreq, int high_strict, void *u, + int (*test)(AddrMap_Entry *am, void *u) /* -ve => look left */, + int *found_r) { + int mid, cmp; - for (i=mm->allocd, clear=newentries+mm->allocd; - i < len; - i++, clear++) - mme_init(clear); - - mm->allocd= len; - mm->entries= newentries; -} - -/*---------- substantial operations on mask maps ----------*/ - -int do_maskmap_amend(ClientData cd, Tcl_Interp *ip, - MaskMap_Var map, Tcl_Obj *prefix, - Tcl_Obj *preflen, Tcl_Obj *data) { - MaskMap_Value *mm= map.mm; - MaskMap_Entry mme, *search; - int rc, insertat, findend, cmp; + for (;;) { + if (high_strict <= low_oreq) { + assert(high_strict == low_oreq); + *found_r= 0; + return high_strict; + } - mme_init(&mme); - - rc= mme_parsekey(ip,&mme,prefix,preflen,0); if (rc) goto x_rc; + mid= (high_strict + low_oreq) / 2; + cmp= test(&am->entries[mid], u); - for (insertat=0, search=mm->entries; - insertat < mm->allocd && - search->prefixlen != -1; - insertat++, search++) { - cmp= mme_ordercompare(&mme,search); if (!cmp) { - mme_free(&mme); - Tcl_DecrRefCount(search->data); - goto put_here; + *found_r= 1; + return mid; } - if (cmp>0) - /* the new one sorts later, insert it here */ - break; - } - /* we're adding an entry, make room for it */ - findend= mm_count(mm); - if (findend == mm->allocd) { - mm_reallocentries(mm, mm->allocd*2 + 1); - search= mm->entries + insertat; + if (cmp < 0) + high_strict= mid; + else + low_oreq= mid+1; } - if (findend > insertat) - memmove(search + 1, search, sizeof(*search) * (findend - insertat)); - *search= mme; +} - put_here: - Tcl_IncrRefCount(data); - search->data= data; - return TCL_OK; +struct am_search_u { + int forbid_aroundsmall; + AddrMap_Entry proposed; + Search_Result sr; +}; - x_rc: - mme_free(&mme); - return rc; +static int +am_search_binchoptest(AddrMap_Entry *ame, void *u_v) { + struct am_search_u *u= u_v; + int cmp; + + cmp= ame_compare(&u.proposed, ame); + switch (cmp) { + case -1: u->sr= sr_inbig; return 0; + case 0: u->sr= sr_exact; return 0; + case +1: u->sr= sr_aroundsmall; return 0; + default: return cmp; + } } -int do_maskmap_lookup(ClientData cd, Tcl_Interp *ip, - Tcl_Obj *mapo, HBytes_Value addr, Tcl_Obj *def, - Tcl_Obj **result) { - /*MaskMap_Var *map= (void*)&mapo->internalRep;*/ - *result= Tcl_NewIntObj(42); - return TCL_OK; /*fixme*/ -} +static Search_Result +am_search(AddrMap_Value *am, const AddrMap_Entry *proposed, int *place_r) { + int place, found; + struct am_search_u u; -/*---------- Tcl type and arg parsing functions ----------*/ + u.forbid_aroundsmall= forbid_aroundsmall; + u.proposed= proposed; + u.sr= sr_notfound; -int pat_maskmapv(Tcl_Interp *ip, Tcl_Obj *var, MaskMap_Var *agg) { - int rc; - rc= pat_somethingv(ip,var,&agg->sth,&maskmap_type); if (rc) return rc; - agg->mm= (void*)&agg->sth.obj->internalRep; - return TCL_OK; -} + *place_r= am_binarychop(am, 0, am.used, &u, am_search_binchoptest, &found); -static void maskmap_t_free(Tcl_Obj *o) { - MaskMap_Value *mm= (void*)&o->internalRep; - MaskMap_Entry *mme; - int i; - - for (i=0, mme=mm->entries; iallocd; i++, mme++) { - if (mme->prefixlen==-1) break; - mme_free(mme); - } + assert(!!found == (u.sr != sr_notfound)); + return u.sr; } -static void maskmap_t_dup(Tcl_Obj *sob, Tcl_Obj *dob) { - MaskMap_Value *sm= (void*)&sob->internalRep; - MaskMap_Value *dm= (void*)&dob->internalRep; - MaskMap_Entry *sme, *dme; - int l, i, nbytes; - - assert(sob->typePtr == &maskmap_type); - objfreeir(dob); - l= mm_count(sm); - - mm_init(dm); - mm_reallocentries(dm,l); - for (i=0, sme=sm->entries, dme=dm->entries; - iallocd; - i++, sme++, dme++) { - *dme= *sme; - nbytes= prefix_bytes(sme->prefixlen); - dme->prefix= TALLOC(nbytes); assert(dme->prefix); - memcpy(dme->prefix, sme->prefix, nbytes); - Tcl_IncrRefCount(dme->data); - } - dob->typePtr= &maskmap_type; -} +/*---------- useful operations on AddrMap_Value etc. ----------*/ -static void maskmap_t_ustr(Tcl_Obj *so) { - MaskMap_Value *sm= (void*)&so->internalRep; - Tcl_Obj **mainlobjsl, *mainobj; - int i, l; +/*---------- amendment (complex algorithm) ----------*/ - assert(so->typePtr == &maskmap_type); - l= mm_count(sm); - mainlobjsl= TALLOC(sizeof(*mainlobjsl) * l); assert(mainlobjsl); +struct am_amend_aroundsmall_u { + AddrMap_Entry *new; + int sign; +}; - for (i=0; ientries[i]; - HBytes_Value hb; - Tcl_Obj *subl[3], *sublo; - hbytes_array(&hb, sme->prefix, prefix_bytes(sme->prefixlen)); - subl[0]= ret_hb(0, hb); assert(subl[0]); - subl[1]= Tcl_NewIntObj(sme->prefixlen); assert(subl[1]); - subl[2]= sme->data; - - sublo= Tcl_NewListObj(3,subl); assert(sublo); - mainlobjsl[i]= sublo; - } +static int +am_amend_aroundsmall_binchoptest(AddrMap_Entry *search, void *u_v) { + struct am_amend_aroundsmall_u *u= u_v; - mainobj= Tcl_NewListObj(l,mainlobjsl); assert(mainobj); - so->bytes= Tcl_GetStringFromObj(mainobj, &so->length); assert(so->bytes); - mainobj->bytes= 0; mainobj->length= 0; /* we stole it */ + cmp= u->sign * ame_compare(search, u->new); + + switch (cmp) { + case +2: return -u->sign; + case +1: return +u->sign; + default: abort(); + } } -static int maskmap_t_sfa(Tcl_Interp *ip, Tcl_Obj *o) { - int rc, len, eol, i; - MaskMap_Value mm; - Tcl_Obj *eo, *prefixo, *prefixleno; +int do_addrmap_amend(ClientData cd, Tcl_Interp *ip, + AddrMap_Var map, Tcl_Obj *prefix, + Tcl_Obj *preflen, Tcl_Obj *data) { + AddrMap_Value *am= map.am; + AddrMap_Entry new, *fragment; + AddrMap_Entry *breaking, *replacements; + int rc, insertat, findend, cmp, nreplacements, new_used; + struct am_amend_aroundsmall_u u; - mm_init(&mm); - - rc= Tcl_ListObjLength(ip,o,&len); if (rc) goto x_rc; - mm_reallocentries(&mm, len); + ame_init(&new); - for (i=0; i0) { - if (mme_ordercompare(&mm.entries[i-1], &mm.entries[i]) <= 0) { - rc= staticerr(ip, "mask-map entries out of order", - "HBYTES MASKMAP SYNTAX ORDER"); - goto x_rc; + rc= ame_parsekey(ip,&new,prefix,preflen,0); if (rc) return rc; + + sr= am_search(am, &new, &searched); + + replacements= &new; + nreplacements= 1; + replace_start= searched; + replace_end= searched; + + switch (sr) { + + case sr_notfound: + break; + + case sr_exact: + replace_end= searched+1; + break; + + case sr_aroundsmall: + u.ame= new; + u.sign= -1; + replace_start= am_binarychop(am, 0, searched, &u, + am_amend_aroundsmall_binchoptest, &dummy); + u.sign= +1; + replace_end= am_binarychop(am, searched+1, am.used, &u, + am_amend_aroundsmall_binchoptest, &dummy); + break; + + case sr_inbig: + /* Urgh, we need to break it up. This produces + * - innermost prefix (the new one) as specified + * - one for each bitlength + * <= innermost + * > outermost (the existing one) + * each one specifying the outermost prefix plus zero, one, + * two, etc. bits of the innermost followed by one bit + * opposite to the innermost, with the outermost's data + * Eg, if we have ff/8=>A and want to amend so that ffff/16=>B + * then we replace ff/8 with ff0/9=>A ff8/10=>A ffc/11=>A ... + * ... fff8/14=>A fffc/15=>A fffe/16=>A ffff/16=>B. + */ + + breaking= &am.entries[searched]; + nreplacements= new.prefix - breaking->prefixlen + 1; + replacements= TALLOC(sizeof(*replacements) * nreplacements); + + for (fragmentlen= breaking->prefixlen + 1, + left_insert= 0, right_insert= nreplacements; + fragmentlen <= new.prefix; + fragmentlen++) { + int fragmentbytes; + + fragmentbytes= prefix_bytes(fragmentlen) + fragment->prefixlen= fragmentlen; + fragment->prefix= TALLOC(fragmentbytes); + memcpy(fragment->prefix, new.prefix, fragmentbytes); + ame_clear_unwanted(fragment, fragmentbytes); + + fragment->prefix[fragmentbytes] ^= + 0x80u >> ((fragmentlen+7) & 7); + + switch (ame_compare(&fragment, &new)) { + case -2: replacements[left_insert++]= fragment; break; + case +2: replacements[--right_insert]= fragment; break; + default: abort(); } } + assert(left_insert == right_insert-1); + replacements[left_insert]= new; + ame_init(&new); + + replace_end= searched+1; + break; + } - /* we commit now */ - assert(sizeof(mm) <= sizeof(o->internalRep)); - objfreeir(o); - memcpy(&o->internalRep, &mm, sizeof(mm)); - o->typePtr= &maskmap_type; + new_used= am.used - (replace_end - replace_start) + nreplacements; + + if (new_used > am.space) + am_reallocentries(am, new_used * 2); + + for (scan=replacements, i=0; + i < nreplacements; + scan++, i++) { + scan->data= data; + Tcl_IncrRefCount(scan->data); + } + + for (i= replace_start, scan= am.entries+i; + i < replace_end; + i++, scan++) { + ame_free(scan); + } + + memmove(am.entries + replace_start + nreplacements, + am.entries + replace_end, + sizeof(*am.entries) * (am.used - replace_end)); + + memcpy(am.entries + replace_start, + replacements, + sizeof(*am.entries) * nreplacements); + + am.used= new_used; + if (replacements != &new) + /* we don't bother freeing the actual array elements because + * if replacements!=&new the array is only full if we're + * committed and have already copied the values into the actual + * AddrMap_Value. */ + TFREE(replacements); + return TCL_OK; +} + +/*---------- other substantial operations on mask maps ----------*/ -x_rc: - if (mm.entries) { - for (i=0; iinternalRep; + const Byte *addr= hbytes_data(&addrhb); + int addrbytes= hbytes_len(&addrhb); + int i, addrbits, place; + Search_Result sr; + + addrbits= addrbytes * 8; + sr= am_search(am, addr, addrbits, &place); + + switch (sr) { + + case sr_notfound: + if (!def) return staticerr(ip, "address not found in addr-map", + "HBYTES ADDRMAP NOMATCH"); + *result= def; + break; + + case sr_aroundsmall: + return staticerr(ip, "address shorter than mask in map", + "HBYTES ADDRMAP UNDERRUN"); + + case sr_exact: + case sr_inbig: + *result= am.entres[place].data; + break; + } - return rc; + + return TCL_OK; } -Tcl_ObjType maskmap_type = { - "mask-map", - maskmap_t_free, maskmap_t_dup, maskmap_t_ustr, maskmap_t_sfa -}; +/*---------- Tcl type and arg parsing functions ----------*/ +