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     r->list=safe_malloc_ary(sizeof(*r->list),r->alloc,"subnet_list_new:data");
  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     struct subnet *nd;
  34     int32_t na;
  35
  36     if (l>a->alloc) {
  37         assert(a->alloc < (int)(INT_MAX/sizeof(*nd))-EXTEND_ALLOC_BY);
  38         na=a->alloc+EXTEND_ALLOC_BY;
  39         nd=safe_realloc_ary(a->list,sizeof(*nd),na,"subnet_list_set_len");
  40         a->alloc=na;
  41         a->list=nd;
  42     }
  43     a->entries=l;
  44 }
  45
  46 void subnet_list_append(struct subnet_list *a, uint32_t prefix, int len)
  47 {
  48     struct subnet *sn;
  49     assert(a->entries < INT_MAX);
  50     subnet_list_set_len(a,a->entries+1);
  51     sn=&a->list[a->entries-1];
  52     sn->prefix=prefix;
  53     sn->len=len;
  54     sn->mask=len?(0xffffffff << (32-len)):0;
  55 }
  56
  57 struct ipset *ipset_new(void)
  58 {
  59     struct ipset *r;
  60     NEW(r);
  61     r->l=0;
  62     r->a=DEFAULT_ALLOC;
  63     r->d=safe_malloc(sizeof(*r->d)*r->a,"ipset_new:data");
  64     return r;
  65 }
  66
  67 void ipset_free(struct ipset *a)
  68 {
  69     if (a->d) free(a->d);
  70     free(a);
  71 }
  72
  73 #ifdef DEBUG
  74 static void ipset_dump(struct ipset *a, string_t name)
  75 {
  76     int32_t i;
  77
  78     printf("%s: ",name);
  79     for (i=0; i<a->l; i++) {
  80         printf("[%08x-%08x] ",a->d[i].a,a->d[i].b);
  81     }
  82     printf("\n");
  83 }
  84 #endif
  85
  86 struct ipset *ipset_from_subnet(struct subnet s)
  87 {
  88     struct ipset *r;
  89
  90     r=ipset_new();
  91     r->l=1;
  92     r->d[0].a=s.prefix;
  93     r->d[0].b=s.prefix | (~s.mask);
  94     return r;
  95 }
  96
  97 struct ipset *ipset_from_subnet_list(struct subnet_list *l)
  98 {
  99     struct ipset *r, *a, *b;
 100     int32_t i;
 101
 102     r=ipset_new();
 103     for (i=0; i<l->entries; i++) {
 104         a=ipset_from_subnet(l->list[i]);
 105         b=ipset_union(r,a);
 106         ipset_free(a);
 107         ipset_free(r);
 108         r=b;
 109     }
 110     return r;
 111 }
 112
 113 static void ipset_set_len(struct ipset *a, int32_t l)
 114 {
 115     struct iprange *nd;
 116     int32_t na;
 117
 118     if (l>a->a) {
 119         assert(a->a < INT_MAX-EXTEND_ALLOC_BY);
 120         na=a->a+EXTEND_ALLOC_BY;
 121         nd=safe_realloc_ary(a->d,sizeof(*nd),na,"ipset_set_len");
 122         a->a=na;
 123         a->d=nd;
 124     }
 125     a->l=l;
 126 }
 127
 128 static void ipset_append_range(struct ipset *a, struct iprange r)
 129 {
 130     ipset_set_len(a,a->l+1);
 131     a->d[a->l-1]=r;
 132 }
 133
 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 }