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