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 "ipaddr.h"
   7
   8 #define DEFAULT_ALLOC 2
   9 #define EXTEND_ALLOC_BY 4
  10
  11 struct subnet_list *subnet_list_new(void)
  12 {
  13     struct subnet_list *r;
  14     r=safe_malloc(sizeof(*r),"subnet_list_new:list");
  15     r->entries=0;
  16     r->alloc=DEFAULT_ALLOC;
  17     r->list=safe_malloc(sizeof(*r->list)*r->alloc,"subnet_list_new:data");
  18     return r;
  19 }
  20
  21 void subnet_list_free(struct subnet_list *a)
  22 {
  23     if (a->list) free(a->list);
  24     free(a);
  25 }
  26
  27 static void subnet_list_set_len(struct subnet_list *a, uint32_t l)
  28 {
  29     struct subnet *nd;
  30     uint32_t na;
  31
  32     if (l>a->alloc) {
  33         na=a->alloc+EXTEND_ALLOC_BY;
  34         nd=realloc(a->list,sizeof(*nd)*na);
  35         if (!nd) {
  36             fatal_perror("subnet_list_set_len: realloc");
  37         }
  38         a->alloc=na;
  39         a->list=nd;
  40     }
  41     a->entries=l;
  42 }
  43
  44 void subnet_list_append(struct subnet_list *a, uint32_t prefix, uint32_t len)
  45 {
  46     struct subnet *sn;
  47     subnet_list_set_len(a,a->entries+1);
  48     sn=&a->list[a->entries-1];
  49     sn->prefix=prefix;
  50     sn->len=len;
  51     sn->mask=len?(0xffffffff << (32-len)):0;
  52 }
  53
  54 struct ipset *ipset_new(void)
  55 {
  56     struct ipset *r;
  57     r=safe_malloc(sizeof(*r),"ipset_new:set");
  58     r->l=0;
  59     r->a=DEFAULT_ALLOC;
  60     r->d=safe_malloc(sizeof(*r->d)*r->a,"ipset_new:data");
  61     return r;
  62 }
  63
  64 void ipset_free(struct ipset *a)
  65 {
  66     if (a->d) free(a->d);
  67     free(a);
  68 }
  69
  70 #ifdef DEBUG
  71 static void ipset_dump(struct ipset *a, string_t name)
  72 {
  73     uint32_t i;
  74
  75     printf("%s: ",name);
  76     for (i=0; i<a->l; i++) {
  77         printf("[%08x-%08x] ",a->d[i].a,a->d[i].b);
  78     }
  79     printf("\n");
  80 }
  81 #endif
  82
  83 struct ipset *ipset_from_subnet(struct subnet s)
  84 {
  85     struct ipset *r;
  86
  87     r=ipset_new();
  88     r->l=1;
  89     r->d[0].a=s.prefix;
  90     r->d[0].b=s.prefix | (~s.mask);
  91     return r;
  92 }
  93
  94 struct ipset *ipset_from_subnet_list(struct subnet_list *l)
  95 {
  96     struct ipset *r, *a, *b;
  97     uint32_t i;
  98
  99     r=ipset_new();
 100     for (i=0; i<l->entries; i++) {
 101         a=ipset_from_subnet(l->list[i]);
 102         b=ipset_union(r,a);
 103         ipset_free(a);
 104         ipset_free(r);
 105         r=b;
 106     }
 107     return r;
 108 }
 109
 110 static void ipset_set_len(struct ipset *a, uint32_t l)
 111 {
 112     struct iprange *nd;
 113     uint32_t na;
 114
 115     if (l>a->a) {
 116         na=a->a+EXTEND_ALLOC_BY;
 117         nd=realloc(a->d,sizeof(*nd)*na);
 118         if (!nd) {
 119             fatal_perror("ipset_set_len: realloc");
 120         }
 121         a->a=na;
 122         a->d=nd;
 123     }
 124     a->l=l;
 125 }
 126
 127 static void ipset_append_range(struct ipset *a, struct iprange r)
 128 {
 129     ipset_set_len(a,a->l+1);
 130     a->d[a->l-1]=r;
 131 }
 132
 133 #define max(a,b) (a>b?a:b)
 134 struct ipset *ipset_union(struct ipset *a, struct ipset *b)
 135 {
 136     struct ipset *c;
 137     struct iprange r;
 138     uint32_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     uint32_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     uint32_t i,lo,hi;
 218
 219     r=ipset_new();
 220     pre=-1;
 221     for (i=0; i<a->l; i++) {
 222         lo=a->d[i].a;
 223         hi=a->d[i].b;
 224         if (lo!=0) {
 225             n.a=pre+1;
 226             n.b=lo-1;
 227             ipset_append_range(r,n);
 228         }
 229         pre=hi;
 230     }
 231     if (pre!=0xffffffff) {
 232         n.a=pre+1;
 233         n.b=0xffffffff;
 234         ipset_append_range(r,n);
 235     }
 236     return r;
 237 }
 238
 239 /* Return a-b */
 240 struct ipset *ipset_subtract(struct ipset *a, struct ipset *b)
 241 {
 242     struct ipset *c, *r;
 243     c=ipset_complement(b);
 244     r=ipset_intersection(a,c);
 245     ipset_free(c);
 246     return r;
 247 }
 248
 249 bool_t ipset_is_empty(struct ipset *a)
 250 {
 251    return (a->l==0);
 252 }
 253
 254 bool_t ipset_contains_addr(struct ipset *a, uint32_t addr)
 255 {
 256     uint32_t i;
 257     struct iprange r;
 258
 259     for (i=0; i<a->l; i++) {
 260         r=a->d[i];
 261         if (addr>=r.a && addr<=r.b) return True;
 262         if (addr<r.a) return False;
 263     }
 264     return False;
 265 }
 266
 267 /* sub is a subset of super if it does not intersect with the complement
 268    of super */
 269 bool_t ipset_is_subset(struct ipset *super, struct ipset *sub)
 270 {
 271     struct ipset *superc;
 272     struct ipset *inter;
 273     bool_t empty;
 274
 275     superc=ipset_complement(super);
 276     inter=ipset_intersection(superc,sub);
 277     empty=ipset_is_empty(inter);
 278     ipset_free(inter);
 279     ipset_free(superc);
 280     return empty;
 281 }
 282
 283 struct subnet_list *ipset_to_subnet_list(struct ipset *is)
 284 {
 285     struct subnet_list *r;
 286     int64_t a,b,lobit,himask,lomask;
 287     int32_t bits;
 288     uint32_t i;
 289
 290     r=subnet_list_new();
 291     for (i=0; i<is->l; i++) {
 292         a=is->d[i].a;
 293         b=is->d[i].b;
 294
 295         lomask=1;
 296         lobit=1;
 297         himask=0xfffffffe;
 298         bits=32;
 299         while (a<=b) {
 300             if ((a & lomask) != 0) {
 301                 subnet_list_append(r,a,bits);
 302                 a=a+lobit;
 303             } else if ((b & lomask) != lomask) {
 304                 subnet_list_append(r,b&himask,bits);
 305                 b=b-lobit;
 306             } else {
 307                 lomask = (lomask << 1) | 1;
 308                 lobit = (lobit << 1);
 309                 himask = himask ^ lobit;
 310                 bits = bits - 1;
 311                 ASSERT(bits>=0);
 312             }
 313         }
 314     }
 315     /* Sort the list? */
 316     return r;
 317 }
 318
 319 /* The string buffer must be at least 16 bytes long */
 320 string_t ipaddr_to_string(uint32_t addr)
 321 {
 322     uint8_t a,b,c,d;
 323     string_t s;
 324
 325     s=safe_malloc(16,"ipaddr_to_string");
 326     a=addr>>24;
 327     b=addr>>16;
 328     c=addr>>8;
 329     d=addr;
 330     snprintf(s, 16, "%d.%d.%d.%d", a, b, c, d);
 331     return s;
 332 }
 333
 334 string_t subnet_to_string(struct subnet sn)
 335 {
 336     uint32_t addr=sn.prefix;
 337     uint8_t a,b,c,d;
 338     string_t s;
 339
 340     s=safe_malloc(19,"subnet_to_string");
 341     a=addr>>24;
 342     b=addr>>16;
 343     c=addr>>8;
 344     d=addr;
 345     snprintf(s, 19, "%d.%d.%d.%d/%d", a, b, c, d, sn.len);
 346     return s;
 347 }
 348
 349 static struct subnet string_item_to_subnet(item_t *i, cstring_t desc,
 350                                            bool_t *invert)
 351 {
 352     struct subnet s;
 353     uint32_t a, b, c, d, n;
 354     uint32_t match;
 355     cstring_t in;
 356
 357     *invert=False;
 358
 359     /* i is not guaranteed to be a string */
 360     if (i->type!=t_string) {
 361         cfgfatal(i->loc,desc,"expecting a string (subnet specification)\n");
 362     }
 363     in=i->data.string;
 364
 365     if (strcmp(in,"default")==0) {
 366         s.prefix=0;
 367         s.mask=0;
 368         s.len=0;
 369         return s;
 370     }
 371
 372     if (*in=='!') {
 373         *invert=True;
 374         in++;
 375     }
 376     /* We expect strings of the form "a.b.c.d[/n]", i.e. the dots are
 377        NOT optional. The subnet mask is optional; if missing it is assumed
 378        to be /32. */
 379     match=sscanf(in,"%u.%u.%u.%u/%u", &a, &b, &c, &d, &n);
 380     if (match<4) {
 381         cfgfatal(i->loc,desc,"\"%s\" is not a valid "
 382                  "subnet specification\n",in);
 383     }
 384     if (match<5) {
 385         n=32;
 386     }
 387     if (a>255 || b>255 || c>255 || d>255 || n>32) {
 388         cfgfatal(i->loc,desc,"\"%s\": range error\n",in);
 389     }
 390     s.prefix=(a<<24)|(b<<16)|(c<<8)|(d);
 391     s.mask=n?(~0UL << (32-n)):0;
 392     s.len=n;
 393     if (s.prefix & ~s.mask) {
 394         cfgfatal(i->loc,desc,"\"%s\": prefix not fully contained "
 395                  "in mask\n",in);
 396     }
 397     return s;
 398 }
 399
 400 uint32_t string_item_to_ipaddr(item_t *i, cstring_t desc)
 401 {
 402     uint32_t a, b, c, d;
 403     uint32_t match;
 404
 405     /* i is not guaranteed to be a string */
 406     if (i->type!=t_string) {
 407         cfgfatal(i->loc,desc,"expecting a string (IP address)\n");
 408     }
 409
 410     match=sscanf(i->data.string,"%u.%u.%u.%u", &a, &b, &c, &d);
 411     if (match<4) {
 412         cfgfatal(i->loc,desc,"\"%s\" is not a valid "
 413                  "IP address\n",i->data.string);
 414     }
 415     if (a>255 || b>255 || c>255 || d>255) {
 416         cfgfatal(i->loc,desc,"\"%s\": range error\n",i->data.string);
 417     }
 418     return (a<<24)|(b<<16)|(c<<8)|(d);
 419 }
 420
 421 struct ipset *string_list_to_ipset(list_t *l, struct cloc loc,
 422                                    cstring_t module, cstring_t param)
 423 {
 424     struct ipset *r, *n, *isn;
 425     uint32_t e,i;
 426     item_t *item;
 427     bool_t inv;
 428
 429     r=ipset_new();
 430     e=list_length(l);
 431     for (i=0; i<e; i++) {
 432         item=list_elem(l,i);
 433         isn=ipset_from_subnet(string_item_to_subnet(item,param,&inv));
 434         if (inv) {
 435             n=ipset_subtract(r,isn);
 436         } else {
 437             n=ipset_union(r,isn);
 438         }
 439         ipset_free(r);
 440         ipset_free(isn);
 441         r=n;
 442     }
 443     return r;
 444 }