chiark - git - mdw - secnet/blob - ipaddr.c

   1 /* The 'ipset' data structure and related algorithms in this file were
   2    inspired by the 'ipaddr.py' library from Cendio Systems AB. */
   3
   4 #include "secnet.h"
   5 #include <limits.h>
   6 #include <assert.h>
   7 #include <stdio.h>
   8 #include <string.h>
   9 #include "ipaddr.h"
  10 #include "util.h"
  11
  12 #define DEFAULT_ALLOC 2
  13 #define EXTEND_ALLOC_BY 4
  14
  15 struct subnet_list *subnet_list_new(void)
  16 {
  17     struct subnet_list *r;
  18     NEW(r);
  19     r->entries=0;
  20     r->alloc=DEFAULT_ALLOC;
  21     NEW_ARY(r->list,r->alloc);
  22     return r;
  23 }
  24
  25 void subnet_list_free(struct subnet_list *a)
  26 {
  27     if (a->list) free(a->list);
  28     free(a);
  29 }
  30
  31 static void subnet_list_set_len(struct subnet_list *a, int32_t l)
  32 {
  33     int32_t na;
  34
  35     if (l>a->alloc) {
  36         assert(a->alloc < INT_MAX-EXTEND_ALLOC_BY);
  37         na=a->alloc+EXTEND_ALLOC_BY;
  38         REALLOC_ARY(a->list,na);
  39         a->alloc=na;
  40     }
  41     a->entries=l;
  42 }
  43
  44 void subnet_list_append(struct subnet_list *a, uint32_t prefix, int len)
  45 {
  46     struct subnet *sn;
  47     assert(a->entries < INT_MAX);
  48     subnet_list_set_len(a,a->entries+1);
  49     sn=&a->list[a->entries-1];
  50     sn->prefix=prefix;
  51     sn->len=len;
  52     sn->mask=len?(0xffffffff << (32-len)):0;
  53 }
  54
  55 struct ipset *ipset_new(void)
  56 {
  57     struct ipset *r;
  58     NEW(r);
  59     r->l=0;
  60     r->a=DEFAULT_ALLOC;
  61     r->d=safe_malloc(sizeof(*r->d)*r->a,"ipset_new:data");
  62     return r;
  63 }
  64
  65 void ipset_free(struct ipset *a)
  66 {
  67     if (a->d) free(a->d);
  68     free(a);
  69 }
  70
  71 #ifdef DEBUG
  72 static void ipset_dump(struct ipset *a, string_t name)
  73 {
  74     int32_t i;
  75
  76     printf("%s: ",name);
  77     for (i=0; i<a->l; i++) {
  78         printf("[%08x-%08x] ",a->d[i].a,a->d[i].b);
  79     }
  80     printf("\n");
  81 }
  82 #endif
  83
  84 struct ipset *ipset_from_subnet(struct subnet s)
  85 {
  86     struct ipset *r;
  87
  88     r=ipset_new();
  89     r->l=1;
  90     r->d[0].a=s.prefix;
  91     r->d[0].b=s.prefix | (~s.mask);
  92     return r;
  93 }
  94
  95 struct ipset *ipset_from_subnet_list(struct subnet_list *l)
  96 {
  97     struct ipset *r, *a, *b;
  98     int32_t i;
  99
 100     r=ipset_new();
 101     for (i=0; i<l->entries; i++) {
 102         a=ipset_from_subnet(l->list[i]);
 103         b=ipset_union(r,a);
 104         ipset_free(a);
 105         ipset_free(r);
 106         r=b;
 107     }
 108     return r;
 109 }
 110
 111 static void ipset_set_len(struct ipset *a, int32_t l)
 112 {
 113     int32_t na;
 114
 115     if (l>a->a) {
 116         assert(a->a < INT_MAX-EXTEND_ALLOC_BY);
 117         na=a->a+EXTEND_ALLOC_BY;
 118         REALLOC_ARY(a->d,na);
 119         a->a=na;
 120     }
 121     a->l=l;
 122 }
 123
 124 static void ipset_append_range(struct ipset *a, struct iprange r)
 125 {
 126     ipset_set_len(a,a->l+1);
 127     a->d[a->l-1]=r;
 128 }
 129
 130 struct ipset *ipset_union(struct ipset *a, struct ipset *b)
 131 {
 132     struct ipset *c;
 133     struct iprange r;
 134     int32_t ia,ib;
 135
 136     c=ipset_new();
 137     ia=0; ib=0;
 138     while (ia<a->l || ib<b->l) {
 139         if (ia<a->l)
 140             if (ib<b->l)
 141                 if (a->d[ia].a < b->d[ib].a)
 142                     r=a->d[ia++];
 143                 else
 144                     r=b->d[ib++];
 145             else
 146                 r=a->d[ia++];
 147         else
 148             r=b->d[ib++];
 149
 150         if (c->l==0)
 151             ipset_append_range(c,r);
 152         else if (r.a <= c->d[c->l-1].b+1)
 153             /* Extends (or is consumed by) the last range */
 154             c->d[c->l-1].b=MAX(c->d[c->l-1].b, r.b);
 155         else
 156             ipset_append_range(c,r);
 157     }
 158     return c;
 159 }
 160
 161 struct ipset *ipset_intersection(struct ipset *a, struct ipset *b)
 162 {
 163     struct ipset *r;
 164     struct iprange ra, rb;
 165     int32_t ia,ib;
 166
 167     r=ipset_new();
 168     ia=0; ib=0;
 169
 170     while (ia<a->l && ib<b->l) {
 171         ra=a->d[ia];
 172         rb=b->d[ib];
 173         if (ra.b < rb.a)
 174             /* The first entry of a doesn't overlap with any part of b */
 175             ia++;
 176         else if (ra.a > rb.b)
 177             /* The first entry of b doesn't overlap with any part of a */
 178             ib++;
 179         else {
 180             /* Trim away any leading edges */
 181             if (ra.a < rb.a)
 182                 /* a starts before b */
 183                 ra.a=rb.a;
 184             else if (ra.a > rb.a)
 185                 /* b starts before a */
 186                 rb.a=ra.a;
 187
 188             /* Now the ranges start at the same point */
 189             if (ra.b == rb.b) {
 190                 /* The ranges are equal */
 191                 ipset_append_range(r,ra);
 192                 ia++;
 193                 ib++;
 194             } else if (ra.b < rb.b) {
 195                 /* a is the smaller range */
 196                 ipset_append_range(r,ra);
 197                 ia++;
 198             } else {
 199                 /* y is the smaller range */
 200                 ipset_append_range(r,rb);
 201                 ib++;
 202             }
 203         }
 204     }
 205     return r;
 206 }
 207
 208 struct ipset *ipset_complement(struct ipset *a)
 209 {
 210     struct ipset *r;
 211     struct iprange n;
 212     int64_t pre;
 213     int32_t i;
 214     uint32_t lo,hi;
 215
 216     r=ipset_new();
 217     pre=-1;
 218     for (i=0; i<a->l; i++) {
 219         lo=a->d[i].a;
 220         hi=a->d[i].b;
 221         if (lo!=0) {
 222             n.a=pre+1;
 223             n.b=lo-1;
 224             ipset_append_range(r,n);
 225         }
 226         pre=hi;
 227     }
 228     if (pre!=0xffffffff) {
 229         n.a=pre+1;
 230         n.b=0xffffffff;
 231         ipset_append_range(r,n);
 232     }
 233     return r;
 234 }
 235
 236 /* Return a-b */
 237 struct ipset *ipset_subtract(struct ipset *a, struct ipset *b)
 238 {
 239     struct ipset *c, *r;
 240     c=ipset_complement(b);
 241     r=ipset_intersection(a,c);
 242     ipset_free(c);
 243     return r;
 244 }
 245
 246 bool_t ipset_is_empty(struct ipset *a)
 247 {
 248    return (a->l==0);
 249 }
 250
 251 bool_t ipset_contains_addr(struct ipset *a, uint32_t addr)
 252 {
 253     int32_t i;
 254     struct iprange r;
 255
 256     for (i=0; i<a->l; i++) {
 257         r=a->d[i];
 258         if (addr>=r.a && addr<=r.b) return True;
 259         if (addr<r.a) return False;
 260     }
 261     return False;
 262 }
 263
 264 /* sub is a subset of super if it does not intersect with the complement
 265    of super */
 266 bool_t ipset_is_subset(struct ipset *super, struct ipset *sub)
 267 {
 268     struct ipset *superc;
 269     struct ipset *inter;
 270     bool_t empty;
 271
 272     superc=ipset_complement(super);
 273     inter=ipset_intersection(superc,sub);
 274     empty=ipset_is_empty(inter);
 275     ipset_free(inter);
 276     ipset_free(superc);
 277     return empty;
 278 }
 279
 280 struct subnet_list *ipset_to_subnet_list(struct ipset *is)
 281 {
 282     struct subnet_list *r;
 283     int64_t a,b,lobit,himask,lomask;
 284     int bits;
 285     int32_t i;
 286
 287     r=subnet_list_new();
 288     for (i=0; i<is->l; i++) {
 289         a=is->d[i].a;
 290         b=is->d[i].b;
 291
 292         lomask=1;
 293         lobit=1;
 294         himask=0xfffffffe;
 295         bits=32;
 296         while (a<=b) {
 297             if ((a & lomask) != 0) {
 298                 subnet_list_append(r,a,bits);
 299                 a=a+lobit;
 300             } else if ((b & lomask) != lomask) {
 301                 subnet_list_append(r,b&himask,bits);
 302                 b=b-lobit;
 303             } else {
 304                 lomask = (lomask << 1) | 1;
 305                 lobit = (lobit << 1);
 306                 himask = himask ^ lobit;
 307                 bits = bits - 1;
 308                 ASSERT(bits>=0);
 309             }
 310         }
 311     }
 312     /* Sort the list? */
 313     return r;
 314 }
 315
 316 #define IPADDR_NBUFS_SHIFT 4
 317 #define IPADDR_NBUFS (1 << IPADDR_NBUFS_SHIFT)
 318 #define IPADDR_BUFLEN 20
 319
 320 static char *ipaddr_getbuf(void)
 321 {
 322     static int ipaddr_bufnum;
 323     static char ipaddr_bufs[IPADDR_NBUFS][IPADDR_BUFLEN];
 324
 325     ipaddr_bufnum++;
 326     ipaddr_bufnum &= IPADDR_NBUFS-1;
 327     return ipaddr_bufs[ipaddr_bufnum];
 328 }
 329
 330 /* The string buffer must be at least 16 bytes long */
 331 string_t ipaddr_to_string(uint32_t addr)
 332 {
 333     uint8_t a,b,c,d;
 334     string_t s;
 335
 336     s=ipaddr_getbuf();
 337     a=addr>>24;
 338     b=addr>>16;
 339     c=addr>>8;
 340     d=addr;
 341     snprintf(s, 16, "%d.%d.%d.%d", a, b, c, d);
 342     return s;
 343 }
 344
 345 string_t subnet_to_string(struct subnet sn)
 346 {
 347     uint32_t addr=sn.prefix;
 348     uint8_t a,b,c,d;
 349     string_t s;
 350
 351     s=ipaddr_getbuf();
 352     a=addr>>24;
 353     b=addr>>16;
 354     c=addr>>8;
 355     d=addr;
 356     snprintf(s, 19, "%d.%d.%d.%d/%d", a, b, c, d, sn.len);
 357     return s;
 358 }
 359
 360 static struct subnet string_item_to_subnet(item_t *i, cstring_t desc,
 361                                            bool_t *invert)
 362 {
 363     struct subnet s;
 364     uint32_t a, b, c, d, n;
 365     int match;
 366     cstring_t in;
 367
 368     *invert=False;
 369
 370     /* i is not guaranteed to be a string */
 371     if (i->type!=t_string) {
 372         cfgfatal(i->loc,desc,"expecting a string (subnet specification)\n");
 373     }
 374     in=i->data.string;
 375
 376     if (strcmp(in,"default")==0) {
 377         s.prefix=0;
 378         s.mask=0;
 379         s.len=0;
 380         return s;
 381     }
 382
 383     if (*in=='!') {
 384         *invert=True;
 385         in++;
 386     }
 387     /* We expect strings of the form "a.b.c.d[/n]", i.e. the dots are
 388        NOT optional. The subnet mask is optional; if missing it is assumed
 389        to be /32. */
 390     match=sscanf(in,"%u.%u.%u.%u/%u", &a, &b, &c, &d, &n);
 391     if (match<4) {
 392         cfgfatal(i->loc,desc,"\"%s\" is not a valid "
 393                  "subnet specification\n",in);
 394     }
 395     if (match<5) {
 396         n=32;
 397     }
 398     if (a>255 || b>255 || c>255 || d>255 || n>32) {
 399         cfgfatal(i->loc,desc,"\"%s\": range error\n",in);
 400     }
 401     s.prefix=(a<<24)|(b<<16)|(c<<8)|(d);
 402     s.mask=n?(~0UL << (32-n)):0;
 403     s.len=n;
 404     if (s.prefix & ~s.mask) {
 405         cfgfatal(i->loc,desc,"\"%s\": prefix not fully contained "
 406                  "in mask\n",in);
 407     }
 408     return s;
 409 }
 410
 411 uint32_t string_item_to_ipaddr(const item_t *i, cstring_t desc)
 412 {
 413     uint32_t a, b, c, d;
 414     int match;
 415
 416     /* i is not guaranteed to be a string */
 417     if (i->type!=t_string) {
 418         cfgfatal(i->loc,desc,"expecting a string (IP address)\n");
 419     }
 420
 421     match=sscanf(i->data.string,"%u.%u.%u.%u", &a, &b, &c, &d);
 422     if (match<4) {
 423         cfgfatal(i->loc,desc,"\"%s\" is not a valid "
 424                  "IP address\n",i->data.string);
 425     }
 426     if (a>255 || b>255 || c>255 || d>255) {
 427         cfgfatal(i->loc,desc,"\"%s\": range error\n",i->data.string);
 428     }
 429     return (a<<24)|(b<<16)|(c<<8)|(d);
 430 }
 431
 432 struct ipset *string_list_to_ipset(list_t *l, struct cloc loc,
 433                                    cstring_t module, cstring_t param)
 434 {
 435     struct ipset *r, *n, *isn;
 436     uint32_t e,i;
 437     item_t *item;
 438     bool_t inv;
 439
 440     r=ipset_new();
 441     e=list_length(l);
 442     for (i=0; i<e; i++) {
 443         item=list_elem(l,i);
 444         isn=ipset_from_subnet(string_item_to_subnet(item,param,&inv));
 445         if (inv) {
 446             n=ipset_subtract(r,isn);
 447         } else {
 448             n=ipset_union(r,isn);
 449         }
 450         ipset_free(r);
 451         ipset_free(isn);
 452         r=n;
 453     }
 454     return r;
 455 }