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