X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=secnet.git;a=blobdiff_plain;f=ipaddr.c;h=f8cda00eabbc3f6c5dac170c249a9cb8211572b0;hp=2dc5928819cd543b328b7ef9788c4702f0c01753;hb=090dbeef60c7e578950c3dbe807a9e2ea7e24875;hpb=7138d0c54cd2212439434d27cb2d6ea775c3039b

diff --git a/ipaddr.c b/ipaddr.c
index 2dc5928..f8cda00 100644
--- a/ipaddr.c
+++ b/ipaddr.c
@@ -1,48 +1,328 @@
+/* The 'ipset' data structure and related algorithms in this file were
+   inspired by the 'ipaddr.py' library from Cendio Systems AB. */
+
 #include "secnet.h"
+#include <limits.h>
+#include <assert.h>
 #include <stdio.h>
+#include <string.h>
+#include "ipaddr.h"
+
+#define DEFAULT_ALLOC 2
+#define EXTEND_ALLOC_BY 4
 
-/* This file should eventually incorporate all the functionality of
-   ipaddr.py */
+struct subnet_list *subnet_list_new(void)
+{
+    struct subnet_list *r;
+    r=safe_malloc(sizeof(*r),"subnet_list_new:list");
+    r->entries=0;
+    r->alloc=DEFAULT_ALLOC;
+    r->list=safe_malloc_ary(sizeof(*r->list),r->alloc,"subnet_list_new:data");
+    return r;
+}
 
-bool_t subnet_match(struct subnet *s, uint32_t address)
+void subnet_list_free(struct subnet_list *a)
 {
-    return (s->prefix==(address&s->mask));
+    if (a->list) free(a->list);
+    free(a);
 }
 
-bool_t subnet_matches_list(struct subnet_list *list, uint32_t address)
+static void subnet_list_set_len(struct subnet_list *a, int32_t l)
 {
-    uint32_t i;
-    for (i=0; i<list->entries; i++) {
-	if (list->list[i].prefix == (address&list->list[i].mask)) return True;
+    struct subnet *nd;
+    int32_t na;
+
+    if (l>a->alloc) {
+	assert(a->alloc < (int)(INT_MAX/sizeof(*nd))-EXTEND_ALLOC_BY);
+	na=a->alloc+EXTEND_ALLOC_BY;
+	nd=realloc(a->list,sizeof(*nd)*na);
+	if (!nd) {
+	    fatal_perror("subnet_list_set_len: realloc");
+	}
+	a->alloc=na;
+	a->list=nd;
     }
-    return False;
+    a->entries=l;
+}
+
+void subnet_list_append(struct subnet_list *a, uint32_t prefix, int len)
+{
+    struct subnet *sn;
+    assert(a->entries < INT_MAX);
+    subnet_list_set_len(a,a->entries+1);
+    sn=&a->list[a->entries-1];
+    sn->prefix=prefix;
+    sn->len=len;
+    sn->mask=len?(0xffffffff << (32-len)):0;
+}
+
+struct ipset *ipset_new(void)
+{
+    struct ipset *r;
+    r=safe_malloc(sizeof(*r),"ipset_new:set");
+    r->l=0;
+    r->a=DEFAULT_ALLOC;
+    r->d=safe_malloc(sizeof(*r->d)*r->a,"ipset_new:data");
+    return r;
 }
 
-bool_t subnets_intersect(struct subnet a, struct subnet b)
+void ipset_free(struct ipset *a)
 {
-    uint32_t mask=a.mask&b.mask;
-    return ((a.prefix&mask)==(b.prefix&mask));
+    if (a->d) free(a->d);
+    free(a);
 }
 
-bool_t subnet_intersects_with_list(struct subnet a, struct subnet_list *b)
+#ifdef DEBUG
+static void ipset_dump(struct ipset *a, string_t name)
 {
-    uint32_t i;
+    int32_t i;
 
-    for (i=0; i<b->entries; i++) {
-	if (subnets_intersect(a,b->list[i])) return True;
+    printf("%s: ",name);
+    for (i=0; i<a->l; i++) {
+	printf("[%08x-%08x] ",a->d[i].a,a->d[i].b);
     }
-    return False;
+    printf("\n");
+}
+#endif
+
+struct ipset *ipset_from_subnet(struct subnet s)
+{
+    struct ipset *r;
+
+    r=ipset_new();
+    r->l=1;
+    r->d[0].a=s.prefix;
+    r->d[0].b=s.prefix | (~s.mask);
+    return r;
+}
+
+struct ipset *ipset_from_subnet_list(struct subnet_list *l)
+{
+    struct ipset *r, *a, *b;
+    int32_t i;
+
+    r=ipset_new();
+    for (i=0; i<l->entries; i++) {
+	a=ipset_from_subnet(l->list[i]);
+	b=ipset_union(r,a);
+	ipset_free(a);
+	ipset_free(r);
+	r=b;
+    }
+    return r;
+}
+
+static void ipset_set_len(struct ipset *a, int32_t l)
+{
+    struct iprange *nd;
+    int32_t na;
+
+    if (l>a->a) {
+	assert(a->a < INT_MAX-EXTEND_ALLOC_BY);
+	na=a->a+EXTEND_ALLOC_BY;
+	nd=realloc(a->d,sizeof(*nd)*na);
+	if (!nd) {
+	    fatal_perror("ipset_set_len: realloc");
+	}
+	a->a=na;
+	a->d=nd;
+    }
+    a->l=l;
+}
+
+static void ipset_append_range(struct ipset *a, struct iprange r)
+{
+    ipset_set_len(a,a->l+1);
+    a->d[a->l-1]=r;
+}
+
+#define max(a,b) (a>b?a:b)
+struct ipset *ipset_union(struct ipset *a, struct ipset *b)
+{
+    struct ipset *c;
+    struct iprange r;
+    int32_t ia,ib;
+
+    c=ipset_new();
+    ia=0; ib=0;
+    while (ia<a->l || ib<b->l) {
+	if (ia<a->l)
+	    if (ib<b->l)
+		if (a->d[ia].a < b->d[ib].a)
+		    r=a->d[ia++];
+		else
+		    r=b->d[ib++];
+	    else
+		r=a->d[ia++];
+	else
+	    r=b->d[ib++];
+
+	if (c->l==0)
+	    ipset_append_range(c,r);
+	else if (r.a <= c->d[c->l-1].b+1)
+	    /* Extends (or is consumed by) the last range */
+	    c->d[c->l-1].b=max(c->d[c->l-1].b, r.b);
+	else
+	    ipset_append_range(c,r);
+    }
+    return c;
+}
+
+struct ipset *ipset_intersection(struct ipset *a, struct ipset *b)
+{
+    struct ipset *r;
+    struct iprange ra, rb;
+    int32_t ia,ib;
+
+    r=ipset_new();
+    ia=0; ib=0;
+
+    while (ia<a->l && ib<b->l) {
+	ra=a->d[ia];
+	rb=b->d[ib];
+	if (ra.b < rb.a)
+	    /* The first entry of a doesn't overlap with any part of b */
+	    ia++;
+	else if (ra.a > rb.b)
+	    /* The first entry of b doesn't overlap with any part of a */
+	    ib++;
+	else {
+	    /* Trim away any leading edges */
+	    if (ra.a < rb.a)
+		/* a starts before b */
+		ra.a=rb.a;
+	    else if (ra.a > rb.a)
+		/* b starts before a */
+		rb.a=ra.a;
+
+	    /* Now the ranges start at the same point */
+	    if (ra.b == rb.b) {
+		/* The ranges are equal */
+		ipset_append_range(r,ra);
+		ia++;
+		ib++;
+	    } else if (ra.b < rb.b) {
+		/* a is the smaller range */
+		ipset_append_range(r,ra);
+		ia++;
+	    } else {
+		/* y is the smaller range */
+		ipset_append_range(r,rb);
+		ib++;
+	    }
+	}
+    }
+    return r;
+}
+
+struct ipset *ipset_complement(struct ipset *a)
+{
+    struct ipset *r;
+    struct iprange n;
+    int64_t pre;
+    int32_t i;
+    uint32_t lo,hi;
+
+    r=ipset_new();
+    pre=-1;
+    for (i=0; i<a->l; i++) {
+	lo=a->d[i].a;
+	hi=a->d[i].b;
+	if (lo!=0) {
+	    n.a=pre+1;
+	    n.b=lo-1;
+	    ipset_append_range(r,n);
+	}
+	pre=hi;
+    }
+    if (pre!=0xffffffff) {
+	n.a=pre+1;
+	n.b=0xffffffff;
+	ipset_append_range(r,n);
+    }
+    return r;
+}
+
+/* Return a-b */
+struct ipset *ipset_subtract(struct ipset *a, struct ipset *b)
+{
+    struct ipset *c, *r;
+    c=ipset_complement(b);
+    r=ipset_intersection(a,c);
+    ipset_free(c);
+    return r;
 }
 
-bool_t subnet_lists_intersect(struct subnet_list *a, struct subnet_list *b)
+bool_t ipset_is_empty(struct ipset *a)
 {
-    uint32_t i;
-    for (i=0; i<a->entries; i++) {
-	if (subnet_intersects_with_list(a->list[i],b)) return True;
+   return (a->l==0);
+}
+
+bool_t ipset_contains_addr(struct ipset *a, uint32_t addr)
+{
+    int32_t i;
+    struct iprange r;
+
+    for (i=0; i<a->l; i++) {
+	r=a->d[i];
+	if (addr>=r.a && addr<=r.b) return True;
+	if (addr<r.a) return False;
     }
     return False;
 }
 
+/* sub is a subset of super if it does not intersect with the complement 
+   of super */
+bool_t ipset_is_subset(struct ipset *super, struct ipset *sub)
+{
+    struct ipset *superc;
+    struct ipset *inter;
+    bool_t empty;
+
+    superc=ipset_complement(super);
+    inter=ipset_intersection(superc,sub);
+    empty=ipset_is_empty(inter);
+    ipset_free(inter);
+    ipset_free(superc);
+    return empty;
+}
+
+struct subnet_list *ipset_to_subnet_list(struct ipset *is)
+{
+    struct subnet_list *r;
+    int64_t a,b,lobit,himask,lomask;
+    int bits;
+    int32_t i;
+
+    r=subnet_list_new();
+    for (i=0; i<is->l; i++) {
+	a=is->d[i].a;
+	b=is->d[i].b;
+
+	lomask=1;
+	lobit=1;
+	himask=0xfffffffe;
+	bits=32;
+	while (a<=b) {
+	    if ((a & lomask) != 0) {
+		subnet_list_append(r,a,bits);
+		a=a+lobit;
+	    } else if ((b & lomask) != lomask) {
+		subnet_list_append(r,b&himask,bits);
+		b=b-lobit;
+	    } else {
+		lomask = (lomask << 1) | 1;
+		lobit = (lobit << 1);
+		himask = himask ^ lobit;
+		bits = bits - 1;
+		ASSERT(bits>=0);
+	    }
+	}
+    }
+    /* Sort the list? */
+    return r;
+}
+
 /* The string buffer must be at least 16 bytes long */
 string_t ipaddr_to_string(uint32_t addr)
 {
@@ -58,24 +338,114 @@ string_t ipaddr_to_string(uint32_t addr)
     return s;
 }
 
-string_t subnet_to_string(struct subnet *sn)
+string_t subnet_to_string(struct subnet sn)
 {
-    uint32_t mask=sn->mask, addr=sn->prefix;
+    uint32_t addr=sn.prefix;
     uint8_t a,b,c,d;
     string_t s;
-    int i;
 
     s=safe_malloc(19,"subnet_to_string");
     a=addr>>24;
     b=addr>>16;
     c=addr>>8;
     d=addr;
-    for (i=0; mask; i++) {
-	mask=(mask<<1);
+    snprintf(s, 19, "%d.%d.%d.%d/%d", a, b, c, d, sn.len);
+    return s;
+}
+
+static struct subnet string_item_to_subnet(item_t *i, cstring_t desc,
+					   bool_t *invert)
+{
+    struct subnet s;
+    uint32_t a, b, c, d, n;
+    int match;
+    cstring_t in;
+
+    *invert=False;
+
+    /* i is not guaranteed to be a string */
+    if (i->type!=t_string) {
+	cfgfatal(i->loc,desc,"expecting a string (subnet specification)\n");
+    }
+    in=i->data.string;
+
+    if (strcmp(in,"default")==0) {
+	s.prefix=0;
+	s.mask=0;
+	s.len=0;
+	return s;
+    }
+
+    if (*in=='!') {
+	*invert=True;
+	in++;
+    }
+    /* We expect strings of the form "a.b.c.d[/n]", i.e. the dots are
+       NOT optional. The subnet mask is optional; if missing it is assumed
+       to be /32. */
+    match=sscanf(in,"%u.%u.%u.%u/%u", &a, &b, &c, &d, &n);
+    if (match<4) {
+	cfgfatal(i->loc,desc,"\"%s\" is not a valid "
+		 "subnet specification\n",in);
+    }
+    if (match<5) {
+	n=32;
     }
-    if (i!=sn->len) {
-	fatal("subnet_to_string: invalid subnet structure!\n");
+    if (a>255 || b>255 || c>255 || d>255 || n>32) {
+	cfgfatal(i->loc,desc,"\"%s\": range error\n",in);
+    }
+    s.prefix=(a<<24)|(b<<16)|(c<<8)|(d);
+    s.mask=n?(~0UL << (32-n)):0;
+    s.len=n;
+    if (s.prefix & ~s.mask) {
+	cfgfatal(i->loc,desc,"\"%s\": prefix not fully contained "
+		 "in mask\n",in);
     }
-    snprintf(s, 19, "%d.%d.%d.%d/%d", a, b, c, d, sn->len);
     return s;
 }
+
+uint32_t string_item_to_ipaddr(item_t *i, cstring_t desc)
+{
+    uint32_t a, b, c, d;
+    int match;
+
+    /* i is not guaranteed to be a string */
+    if (i->type!=t_string) {
+	cfgfatal(i->loc,desc,"expecting a string (IP address)\n");
+    }
+
+    match=sscanf(i->data.string,"%u.%u.%u.%u", &a, &b, &c, &d);
+    if (match<4) {
+	cfgfatal(i->loc,desc,"\"%s\" is not a valid "
+		 "IP address\n",i->data.string);
+    }
+    if (a>255 || b>255 || c>255 || d>255) {
+	cfgfatal(i->loc,desc,"\"%s\": range error\n",i->data.string);
+    }
+    return (a<<24)|(b<<16)|(c<<8)|(d);
+}
+
+struct ipset *string_list_to_ipset(list_t *l, struct cloc loc,
+				   cstring_t module, cstring_t param)
+{
+    struct ipset *r, *n, *isn;
+    uint32_t e,i;
+    item_t *item;
+    bool_t inv;
+
+    r=ipset_new();
+    e=list_length(l);
+    for (i=0; i<e; i++) {
+	item=list_elem(l,i);
+	isn=ipset_from_subnet(string_item_to_subnet(item,param,&inv));
+	if (inv) {
+	    n=ipset_subtract(r,isn);
+	} else {
+	    n=ipset_union(r,isn);
+	}
+	ipset_free(r);
+	ipset_free(isn);
+	r=n;
+    }
+    return r;
+}