X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=maskmap%2Fmaskmap.c;h=ad141a925ca38123224a0cd21cb0ccd2b420cdff;hb=73cb29760348de6e329efdab662b8a320c92b136;hp=f51dba4b19cf587690b170174a9c933dd36b6150;hpb=d6fd8ff47e228354088d5be383a55d1d24099c36;p=chiark-tcl.git diff --git a/maskmap/maskmap.c b/maskmap/maskmap.c index f51dba4..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,286 +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)); +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); +} + +/*---------- searching maps ----------*/ + +typedef enum { + sr_notfound, + sr_exact, + sr_inbig, + sr_aroundsmall +} Search_Result; + +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 (;;) { + if (high_strict <= low_oreq) { + assert(high_strict == low_oreq); + *found_r= 0; + return high_strict; + } + + mid= (high_strict + low_oreq) / 2; + cmp= test(&am->entries[mid], u); + + if (!cmp) { + *found_r= 1; + return mid; + } + + if (cmp < 0) + high_strict= mid; + else + low_oreq= mid+1; + } } -/*---------- useful operations on MaskMap_Value etc. ----------*/ +struct am_search_u { + int forbid_aroundsmall; + AddrMap_Entry proposed; + Search_Result sr; +}; -static int mm_count(const MaskMap_Value *mm) { - int i; - for (i=0; iallocd && mm->entries[i].prefixlen != -1; i++); - return i; +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; + } } -static void mm_init(MaskMap_Value *mm) { - mm->allocd= 0; - mm->entries= 0; +static Search_Result +am_search(AddrMap_Value *am, const AddrMap_Entry *proposed, int *place_r) { + int place, found; + struct am_search_u u; + + u.forbid_aroundsmall= forbid_aroundsmall; + u.proposed= proposed; + u.sr= sr_notfound; + + *place_r= am_binarychop(am, 0, am.used, &u, am_search_binchoptest, &found); + + assert(!!found == (u.sr != sr_notfound)); + return u.sr; } -static void mm_reallocentries(MaskMap_Value *mm, int len) { - int i; - MaskMap_Entry *newentries, *clear; +/*---------- useful operations on AddrMap_Value etc. ----------*/ - assert(len >= mm->allocd); - if (!len) return; +/*---------- amendment (complex algorithm) ----------*/ - newentries= TREALLOC(mm->entries, sizeof(*newentries)*len); - assert(newentries); - - for (i=mm->allocd, clear=newentries+mm->allocd; - i < len; - i++, clear++) - mme_init(clear); +struct am_amend_aroundsmall_u { + AddrMap_Entry *new; + int sign; +}; + + +static int +am_amend_aroundsmall_binchoptest(AddrMap_Entry *search, void *u_v) { + struct am_amend_aroundsmall_u *u= u_v; - mm->allocd= len; - mm->entries= newentries; + cmp= u->sign * ame_compare(search, u->new); + + switch (cmp) { + case +2: return -u->sign; + case +1: return +u->sign; + default: abort(); + } } - -/*---------- substantial operations on mask maps ----------*/ -int do_maskmap_amend(ClientData cd, Tcl_Interp *ip, - MaskMap_Var map, Tcl_Obj *prefix, +int do_addrmap_amend(ClientData cd, Tcl_Interp *ip, + AddrMap_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; + 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; - mme_init(&mme); + ame_init(&new); - rc= mme_parsekey(ip,&mme,prefix,preflen,0); if (rc) goto x_rc; - - 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; + 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(); + } } - if (cmp>0) - /* the new one sorts later, insert it here */ - break; - } + assert(left_insert == right_insert-1); + replacements[left_insert]= new; + ame_init(&new); + + replace_end= searched+1; + 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 (findend > insertat) - memmove(search + 1, search, sizeof(*search) * (findend - insertat)); - *search= mme; - put_here: - Tcl_IncrRefCount(data); - search->data= data; - return TCL_OK; + new_used= am.used - (replace_end - replace_start) + nreplacements; - x_rc: - mme_free(&mme); - return rc; -} + if (new_used > am.space) + am_reallocentries(am, new_used * 2); -int do_maskmap_lookup(ClientData cd, Tcl_Interp *ip, - Tcl_Obj *mapo, HBytes_Value addrhb, Tcl_Obj *def, - Tcl_Obj **result) { - MaskMap_Value *mm= (void*)&mapo->internalRep; - MaskMap_Entry *search; - const Byte *addr= hbytes_data(&addrhb); - int addrbytes= hbytes_len(&addrhb); - int i, directbytes, leftoverbits; - - search= mm->entries; - if (!search || search->prefixlen==-1) goto not_found; - - /* longest masks are first, so we can test this once */ - if (addrbytes < prefix_bytes(search->prefixlen)) - return staticerr(ip, "address shorter than mask(s) in map", - "HBYTES MASKMAP UNDERRUN"); - - for (i=0; - i < mm->allocd && search->prefixlen != -1; - i++, search++) { - directbytes= search->prefixlen / 8; - if (memcmp(search->prefix, addr, directbytes)) continue; - - leftoverbits= search->prefixlen % 8; - if (leftoverbits) - if ((addr[directbytes] & (0xffu << leftoverbits)) - != search->prefix[directbytes]) - continue; - - /*found*/ - *result= search->data; - return TCL_OK; + for (scan=replacements, i=0; + i < nreplacements; + scan++, i++) { + scan->data= data; + Tcl_IncrRefCount(scan->data); } - not_found: - if (!def) - return staticerr(ip, "address not found in mask-map", - "HBYTES MASKMAP NOMATCH"); - *result= def; - return TCL_OK; -} + for (i= replace_start, scan= am.entries+i; + i < replace_end; + i++, scan++) { + ame_free(scan); + } -/*---------- Tcl type and arg parsing functions ----------*/ + memmove(am.entries + replace_start + nreplacements, + am.entries + replace_end, + sizeof(*am.entries) * (am.used - replace_end)); -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; -} + memcpy(am.entries + replace_start, + replacements, + sizeof(*am.entries) * nreplacements); -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); - } -} + 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); -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; + return TCL_OK; } -static void maskmap_t_ustr(Tcl_Obj *so) { - MaskMap_Value *sm= (void*)&so->internalRep; - Tcl_Obj **mainlobjsl, *mainobj; - int i, l; +/*---------- other substantial operations on mask maps ----------*/ - assert(so->typePtr == &maskmap_type); - l= mm_count(sm); - mainlobjsl= TALLOC(sizeof(*mainlobjsl) * l); assert(mainlobjsl); +int do_addrmap_lookup(ClientData cd, Tcl_Interp *ip, + Tcl_Obj *mapo, HBytes_Value addrhb, Tcl_Obj *def, + Tcl_Obj **result) { + AddrMap_Value *am= (void*)&mapo->internalRep; + const Byte *addr= hbytes_data(&addrhb); + int addrbytes= hbytes_len(&addrhb); + int i, addrbits, place; + Search_Result sr; - for (i=0; ientries[i]; - HBytes_Value hb; - Tcl_Obj *subl[3], *sublo; + addrbits= addrbytes * 8; + sr= am_search(am, addr, addrbits, &place); - 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; - } + switch (sr) { - 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 */ -} + case sr_notfound: + if (!def) return staticerr(ip, "address not found in addr-map", + "HBYTES ADDRMAP NOMATCH"); + *result= def; + break; -static int maskmap_t_sfa(Tcl_Interp *ip, Tcl_Obj *o) { - int rc, len, eol, i; - MaskMap_Value mm; - Tcl_Obj *eo, *prefixo, *prefixleno; + case sr_aroundsmall: + return staticerr(ip, "address shorter than mask in map", + "HBYTES ADDRMAP UNDERRUN"); - mm_init(&mm); - - rc= Tcl_ListObjLength(ip,o,&len); if (rc) goto x_rc; - mm_reallocentries(&mm, len); - - 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; - } - } + case sr_exact: + case sr_inbig: + *result= am.entres[place].data; + break; + } - /* we commit now */ - assert(sizeof(mm) <= sizeof(o->internalRep)); - objfreeir(o); - memcpy(&o->internalRep, &mm, sizeof(mm)); - o->typePtr= &maskmap_type; return TCL_OK; - -x_rc: - if (mm.entries) { - for (i=0; i