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 <stdio.h>
   6 #include <string.h>
   7 #include "ipaddr.h"
   8
   9 #define DEFAULT_ALLOC 2
  10 #define EXTEND_ALLOC_BY 4
  11
  12 struct subnet_list *subnet_list_new(void)
  13 {
  14     struct subnet_list *r;
  15     r=safe_malloc(sizeof(*r),"subnet_list_new:list");
  16     r->entries=0;
  17     r->alloc=DEFAULT_ALLOC;
  18     r->list=safe_malloc(sizeof(*r->list)*r->alloc,"subnet_list_new:data");
  19     return r;
  20 }
  21
  22 void subnet_list_free(struct subnet_list *a)
  23 {
  24     if (a->list) free(a->list);
  25     free(a);
  26 }
  27
  28 static void subnet_list_set_len(struct subnet_list *a, uint32_t l)
  29 {
  30     struct subnet *nd;
  31     uint32_t na;
  32
  33     if (l>a->alloc) {
  34         na=a->alloc+EXTEND_ALLOC_BY;
  35         nd=realloc(a->list,sizeof(*nd)*na);
  36         if (!nd) {
  37             fatal_perror("subnet_list_set_len: realloc");
  38         }
  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, uint32_t len)
  46 {
  47     struct subnet *sn;
  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     r=safe_malloc(sizeof(*r),"ipset_new:set");
  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     uint32_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     uint32_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, uint32_t l)
 112 {
 113     struct iprange *nd;
 114     uint32_t na;
 115
 116     if (l>a->a) {
 117         na=a->a+EXTEND_ALLOC_BY;
 118         nd=realloc(a->d,sizeof(*nd)*na);
 119         if (!nd) {
 120             fatal_perror("ipset_set_len: realloc");
 121         }
 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 #define max(a,b) (a>b?a:b)
 135 struct ipset *ipset_union(struct ipset *a, struct ipset *b)
 136 {
 137     struct ipset *c;
 138     struct iprange r;
 139     uint32_t ia,ib;
 140
 141     c=ipset_new();
 142     ia=0; ib=0;
 143     while (ia<a->l || ib<b->l) {
 144         if (ia<a->l)
 145             if (ib<b->l)
 146                 if (a->d[ia].a < b->d[ib].a)
 147                     r=a->d[ia++];
 148                 else
 149                     r=b->d[ib++];
 150             else
 151                 r=a->d[ia++];
 152         else
 153             r=b->d[ib++];
 154
 155         if (c->l==0)
 156             ipset_append_range(c,r);
 157         else if (r.a <= c->d[c->l-1].b+1)
 158             /* Extends (or is consumed by) the last range */
 159             c->d[c->l-1].b=max(c->d[c->l-1].b, r.b);
 160         else
 161             ipset_append_range(c,r);
 162     }
 163     return c;
 164 }
 165
 166 struct ipset *ipset_intersection(struct ipset *a, struct ipset *b)
 167 {
 168     struct ipset *r;
 169     struct iprange ra, rb;
 170     uint32_t ia,ib;
 171
 172     r=ipset_new();
 173     ia=0; ib=0;
 174
 175     while (ia<a->l && ib<b->l) {
 176         ra=a->d[ia];
 177         rb=b->d[ib];
 178         if (ra.b < rb.a)
 179             /* The first entry of a doesn't overlap with any part of b */
 180             ia++;
 181         else if (ra.a > rb.b)
 182             /* The first entry of b doesn't overlap with any part of a */
 183             ib++;
 184         else {
 185             /* Trim away any leading edges */
 186             if (ra.a < rb.a)
 187                 /* a starts before b */
 188                 ra.a=rb.a;
 189             else if (ra.a > rb.a)
 190                 /* b starts before a */
 191                 rb.a=ra.a;
 192
 193             /* Now the ranges start at the same point */
 194             if (ra.b == rb.b) {
 195                 /* The ranges are equal */
 196                 ipset_append_range(r,ra);
 197                 ia++;
 198                 ib++;
 199             } else if (ra.b < rb.b) {
 200                 /* a is the smaller range */
 201                 ipset_append_range(r,ra);
 202                 ia++;
 203             } else {
 204                 /* y is the smaller range */
 205                 ipset_append_range(r,rb);
 206                 ib++;
 207             }
 208         }
 209     }
 210     return r;
 211 }
 212
 213 struct ipset *ipset_complement(struct ipset *a)
 214 {
 215     struct ipset *r;
 216     struct iprange n;
 217     int64_t pre;
 218     uint32_t i,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     uint32_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     int32_t bits;
 289     uint32_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 /* The string buffer must be at least 16 bytes long */
 321 string_t ipaddr_to_string(uint32_t addr)
 322 {
 323     uint8_t a,b,c,d;
 324     string_t s;
 325
 326     s=safe_malloc(16,"ipaddr_to_string");
 327     a=addr>>24;
 328     b=addr>>16;
 329     c=addr>>8;
 330     d=addr;
 331     snprintf(s, 16, "%d.%d.%d.%d", a, b, c, d);
 332     return s;
 333 }
 334
 335 string_t subnet_to_string(struct subnet sn)
 336 {
 337     uint32_t addr=sn.prefix;
 338     uint8_t a,b,c,d;
 339     string_t s;
 340
 341     s=safe_malloc(19,"subnet_to_string");
 342     a=addr>>24;
 343     b=addr>>16;
 344     c=addr>>8;
 345     d=addr;
 346     snprintf(s, 19, "%d.%d.%d.%d/%d", a, b, c, d, sn.len);
 347     return s;
 348 }
 349
 350 static struct subnet string_item_to_subnet(item_t *i, cstring_t desc,
 351                                            bool_t *invert)
 352 {
 353     struct subnet s;
 354     uint32_t a, b, c, d, n;
 355     uint32_t match;
 356     cstring_t in;
 357
 358     *invert=False;
 359
 360     /* i is not guaranteed to be a string */
 361     if (i->type!=t_string) {
 362         cfgfatal(i->loc,desc,"expecting a string (subnet specification)\n");
 363     }
 364     in=i->data.string;
 365
 366     if (strcmp(in,"default")==0) {
 367         s.prefix=0;
 368         s.mask=0;
 369         s.len=0;
 370         return s;
 371     }
 372
 373     if (*in=='!') {
 374         *invert=True;
 375         in++;
 376     }
 377     /* We expect strings of the form "a.b.c.d[/n]", i.e. the dots are
 378        NOT optional. The subnet mask is optional; if missing it is assumed
 379        to be /32. */
 380     match=sscanf(in,"%u.%u.%u.%u/%u", &a, &b, &c, &d, &n);
 381     if (match<4) {
 382         cfgfatal(i->loc,desc,"\"%s\" is not a valid "
 383                  "subnet specification\n",in);
 384     }
 385     if (match<5) {
 386         n=32;
 387     }
 388     if (a>255 || b>255 || c>255 || d>255 || n>32) {
 389         cfgfatal(i->loc,desc,"\"%s\": range error\n",in);
 390     }
 391     s.prefix=(a<<24)|(b<<16)|(c<<8)|(d);
 392     s.mask=n?(~0UL << (32-n)):0;
 393     s.len=n;
 394     if (s.prefix & ~s.mask) {
 395         cfgfatal(i->loc,desc,"\"%s\": prefix not fully contained "
 396                  "in mask\n",in);
 397     }
 398     return s;
 399 }
 400
 401 uint32_t string_item_to_ipaddr(item_t *i, cstring_t desc)
 402 {
 403     uint32_t a, b, c, d;
 404     uint32_t match;
 405
 406     /* i is not guaranteed to be a string */
 407     if (i->type!=t_string) {
 408         cfgfatal(i->loc,desc,"expecting a string (IP address)\n");
 409     }
 410
 411     match=sscanf(i->data.string,"%u.%u.%u.%u", &a, &b, &c, &d);
 412     if (match<4) {
 413         cfgfatal(i->loc,desc,"\"%s\" is not a valid "
 414                  "IP address\n",i->data.string);
 415     }
 416     if (a>255 || b>255 || c>255 || d>255) {
 417         cfgfatal(i->loc,desc,"\"%s\": range error\n",i->data.string);
 418     }
 419     return (a<<24)|(b<<16)|(c<<8)|(d);
 420 }
 421
 422 struct ipset *string_list_to_ipset(list_t *l, struct cloc loc,
 423                                    cstring_t module, cstring_t param)
 424 {
 425     struct ipset *r, *n, *isn;
 426     uint32_t e,i;
 427     item_t *item;
 428     bool_t inv;
 429
 430     r=ipset_new();
 431     e=list_length(l);
 432     for (i=0; i<e; i++) {
 433         item=list_elem(l,i);
 434         isn=ipset_from_subnet(string_item_to_subnet(item,param,&inv));
 435         if (inv) {
 436             n=ipset_subtract(r,isn);
 437         } else {
 438             n=ipset_union(r,isn);
 439         }
 440         ipset_free(r);
 441         ipset_free(isn);
 442         r=n;
 443     }
 444     return r;
 445 }