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, uint32_t l)
  31 {
  32     struct subnet *nd;
  33     uint32_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, uint32_t 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     uint32_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     uint32_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, uint32_t l)
 116 {
 117     struct iprange *nd;
 118     uint32_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     uint32_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     uint32_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     uint32_t i,lo,hi;
 224
 225     r=ipset_new();
 226     pre=-1;
 227     for (i=0; i<a->l; i++) {
 228         lo=a->d[i].a;
 229         hi=a->d[i].b;
 230         if (lo!=0) {
 231             n.a=pre+1;
 232             n.b=lo-1;
 233             ipset_append_range(r,n);
 234         }
 235         pre=hi;
 236     }
 237     if (pre!=0xffffffff) {
 238         n.a=pre+1;
 239         n.b=0xffffffff;
 240         ipset_append_range(r,n);
 241     }
 242     return r;
 243 }
 244
 245 /* Return a-b */
 246 struct ipset *ipset_subtract(struct ipset *a, struct ipset *b)
 247 {
 248     struct ipset *c, *r;
 249     c=ipset_complement(b);
 250     r=ipset_intersection(a,c);
 251     ipset_free(c);
 252     return r;
 253 }
 254
 255 bool_t ipset_is_empty(struct ipset *a)
 256 {
 257    return (a->l==0);
 258 }
 259
 260 bool_t ipset_contains_addr(struct ipset *a, uint32_t addr)
 261 {
 262     uint32_t i;
 263     struct iprange r;
 264
 265     for (i=0; i<a->l; i++) {
 266         r=a->d[i];
 267         if (addr>=r.a && addr<=r.b) return True;
 268         if (addr<r.a) return False;
 269     }
 270     return False;
 271 }
 272
 273 /* sub is a subset of super if it does not intersect with the complement
 274    of super */
 275 bool_t ipset_is_subset(struct ipset *super, struct ipset *sub)
 276 {
 277     struct ipset *superc;
 278     struct ipset *inter;
 279     bool_t empty;
 280
 281     superc=ipset_complement(super);
 282     inter=ipset_intersection(superc,sub);
 283     empty=ipset_is_empty(inter);
 284     ipset_free(inter);
 285     ipset_free(superc);
 286     return empty;
 287 }
 288
 289 struct subnet_list *ipset_to_subnet_list(struct ipset *is)
 290 {
 291     struct subnet_list *r;
 292     int64_t a,b,lobit,himask,lomask;
 293     int32_t bits;
 294     uint32_t i;
 295
 296     r=subnet_list_new();
 297     for (i=0; i<is->l; i++) {
 298         a=is->d[i].a;
 299         b=is->d[i].b;
 300
 301         lomask=1;
 302         lobit=1;
 303         himask=0xfffffffe;
 304         bits=32;
 305         while (a<=b) {
 306             if ((a & lomask) != 0) {
 307                 subnet_list_append(r,a,bits);
 308                 a=a+lobit;
 309             } else if ((b & lomask) != lomask) {
 310                 subnet_list_append(r,b&himask,bits);
 311                 b=b-lobit;
 312             } else {
 313                 lomask = (lomask << 1) | 1;
 314                 lobit = (lobit << 1);
 315                 himask = himask ^ lobit;
 316                 bits = bits - 1;
 317                 ASSERT(bits>=0);
 318             }
 319         }
 320     }
 321     /* Sort the list? */
 322     return r;
 323 }
 324
 325 /* The string buffer must be at least 16 bytes long */
 326 string_t ipaddr_to_string(uint32_t addr)
 327 {
 328     uint8_t a,b,c,d;
 329     string_t s;
 330
 331     s=safe_malloc(16,"ipaddr_to_string");
 332     a=addr>>24;
 333     b=addr>>16;
 334     c=addr>>8;
 335     d=addr;
 336     snprintf(s, 16, "%d.%d.%d.%d", a, b, c, d);
 337     return s;
 338 }
 339
 340 string_t subnet_to_string(struct subnet sn)
 341 {
 342     uint32_t addr=sn.prefix;
 343     uint8_t a,b,c,d;
 344     string_t s;
 345
 346     s=safe_malloc(19,"subnet_to_string");
 347     a=addr>>24;
 348     b=addr>>16;
 349     c=addr>>8;
 350     d=addr;
 351     snprintf(s, 19, "%d.%d.%d.%d/%d", a, b, c, d, sn.len);
 352     return s;
 353 }
 354
 355 static struct subnet string_item_to_subnet(item_t *i, cstring_t desc,
 356                                            bool_t *invert)
 357 {
 358     struct subnet s;
 359     uint32_t a, b, c, d, n;
 360     uint32_t match;
 361     cstring_t in;
 362
 363     *invert=False;
 364
 365     /* i is not guaranteed to be a string */
 366     if (i->type!=t_string) {
 367         cfgfatal(i->loc,desc,"expecting a string (subnet specification)\n");
 368     }
 369     in=i->data.string;
 370
 371     if (strcmp(in,"default")==0) {
 372         s.prefix=0;
 373         s.mask=0;
 374         s.len=0;
 375         return s;
 376     }
 377
 378     if (*in=='!') {
 379         *invert=True;
 380         in++;
 381     }
 382     /* We expect strings of the form "a.b.c.d[/n]", i.e. the dots are
 383        NOT optional. The subnet mask is optional; if missing it is assumed
 384        to be /32. */
 385     match=sscanf(in,"%u.%u.%u.%u/%u", &a, &b, &c, &d, &n);
 386     if (match<4) {
 387         cfgfatal(i->loc,desc,"\"%s\" is not a valid "
 388                  "subnet specification\n",in);
 389     }
 390     if (match<5) {
 391         n=32;
 392     }
 393     if (a>255 || b>255 || c>255 || d>255 || n>32) {
 394         cfgfatal(i->loc,desc,"\"%s\": range error\n",in);
 395     }
 396     s.prefix=(a<<24)|(b<<16)|(c<<8)|(d);
 397     s.mask=n?(~0UL << (32-n)):0;
 398     s.len=n;
 399     if (s.prefix & ~s.mask) {
 400         cfgfatal(i->loc,desc,"\"%s\": prefix not fully contained "
 401                  "in mask\n",in);
 402     }
 403     return s;
 404 }
 405
 406 uint32_t string_item_to_ipaddr(item_t *i, cstring_t desc)
 407 {
 408     uint32_t a, b, c, d;
 409     uint32_t match;
 410
 411     /* i is not guaranteed to be a string */
 412     if (i->type!=t_string) {
 413         cfgfatal(i->loc,desc,"expecting a string (IP address)\n");
 414     }
 415
 416     match=sscanf(i->data.string,"%u.%u.%u.%u", &a, &b, &c, &d);
 417     if (match<4) {
 418         cfgfatal(i->loc,desc,"\"%s\" is not a valid "
 419                  "IP address\n",i->data.string);
 420     }
 421     if (a>255 || b>255 || c>255 || d>255) {
 422         cfgfatal(i->loc,desc,"\"%s\": range error\n",i->data.string);
 423     }
 424     return (a<<24)|(b<<16)|(c<<8)|(d);
 425 }
 426
 427 struct ipset *string_list_to_ipset(list_t *l, struct cloc loc,
 428                                    cstring_t module, cstring_t param)
 429 {
 430     struct ipset *r, *n, *isn;
 431     uint32_t e,i;
 432     item_t *item;
 433     bool_t inv;
 434
 435     r=ipset_new();
 436     e=list_length(l);
 437     for (i=0; i<e; i++) {
 438         item=list_elem(l,i);
 439         isn=ipset_from_subnet(string_item_to_subnet(item,param,&inv));
 440         if (inv) {
 441             n=ipset_subtract(r,isn);
 442         } else {
 443             n=ipset_union(r,isn);
 444         }
 445         ipset_free(r);
 446         ipset_free(isn);
 447         r=n;
 448     }
 449     return r;
 450 }