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