1 /* The 'ipset' data structure and related algorithms in this file were
2 inspired by the 'ipaddr.py' library from Cendio Systems AB. */
4 * This file is part of secnet.
5 * See README for full list of copyright holders.
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 3 of the License, or
10 * (at your option) any later version.
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.
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.
30 #define DEFAULT_ALLOC 2
31 #define EXTEND_ALLOC_BY 4
33 struct subnet_list *subnet_list_new(void)
35 struct subnet_list *r;
38 r->alloc=DEFAULT_ALLOC;
39 NEW_ARY(r->list,r->alloc);
43 void subnet_list_free(struct subnet_list *a)
45 if (a->list) free(a->list);
49 static void subnet_list_set_len(struct subnet_list *a, int32_t l)
54 assert(a->alloc < INT_MAX-EXTEND_ALLOC_BY);
55 na=a->alloc+EXTEND_ALLOC_BY;
56 REALLOC_ARY(a->list,na);
62 void subnet_list_append(struct subnet_list *a, uint32_t prefix, int len)
65 assert(a->entries < INT_MAX);
66 subnet_list_set_len(a,a->entries+1);
67 sn=&a->list[a->entries-1];
70 sn->mask=len?(0xffffffff << (32-len)):0;
73 struct ipset *ipset_new(void)
83 void ipset_free(struct ipset *a)
90 static void ipset_dump(struct ipset *a, string_t name)
95 for (i=0; i<a->l; i++) {
96 printf("[%08x-%08x] ",a->d[i].a,a->d[i].b);
102 struct ipset *ipset_from_subnet(struct subnet s)
109 r->d[0].b=s.prefix | (~s.mask);
113 struct ipset *ipset_from_subnet_list(struct subnet_list *l)
115 struct ipset *r, *a, *b;
119 for (i=0; i<l->entries; i++) {
120 a=ipset_from_subnet(l->list[i]);
129 static void ipset_set_len(struct ipset *a, int32_t l)
134 assert(a->a < INT_MAX-EXTEND_ALLOC_BY);
135 na=a->a+EXTEND_ALLOC_BY;
136 REALLOC_ARY(a->d,na);
142 static void ipset_append_range(struct ipset *a, struct iprange r)
144 ipset_set_len(a,a->l+1);
148 struct ipset *ipset_union(struct ipset *a, struct ipset *b)
156 while (ia<a->l || ib<b->l) {
159 if (a->d[ia].a < b->d[ib].a)
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);
174 ipset_append_range(c,r);
179 struct ipset *ipset_intersection(struct ipset *a, struct ipset *b)
182 struct iprange ra, rb;
188 while (ia<a->l && ib<b->l) {
192 /* The first entry of a doesn't overlap with any part of b */
194 else if (ra.a > rb.b)
195 /* The first entry of b doesn't overlap with any part of a */
198 /* Trim away any leading edges */
200 /* a starts before b */
202 else if (ra.a > rb.a)
203 /* b starts before a */
206 /* Now the ranges start at the same point */
208 /* The ranges are equal */
209 ipset_append_range(r,ra);
212 } else if (ra.b < rb.b) {
213 /* a is the smaller range */
214 ipset_append_range(r,ra);
217 /* y is the smaller range */
218 ipset_append_range(r,rb);
226 struct ipset *ipset_complement(struct ipset *a)
236 for (i=0; i<a->l; i++) {
242 ipset_append_range(r,n);
246 if (pre!=0xffffffff) {
249 ipset_append_range(r,n);
255 struct ipset *ipset_subtract(struct ipset *a, struct ipset *b)
258 c=ipset_complement(b);
259 r=ipset_intersection(a,c);
264 bool_t ipset_is_empty(struct ipset *a)
269 bool_t ipset_contains_addr(struct ipset *a, uint32_t addr)
274 for (i=0; i<a->l; i++) {
276 if (addr>=r.a && addr<=r.b) return True;
277 if (addr<r.a) return False;
282 /* sub is a subset of super if it does not intersect with the complement
284 bool_t ipset_is_subset(struct ipset *super, struct ipset *sub)
286 struct ipset *superc;
290 superc=ipset_complement(super);
291 inter=ipset_intersection(superc,sub);
292 empty=ipset_is_empty(inter);
298 struct subnet_list *ipset_to_subnet_list(struct ipset *is)
300 struct subnet_list *r;
301 int64_t a,b,lobit,himask,lomask;
306 for (i=0; i<is->l; i++) {
315 if ((a & lomask) != 0) {
316 subnet_list_append(r,a,bits);
318 } else if ((b & lomask) != lomask) {
319 subnet_list_append(r,b&himask,bits);
322 lomask = (lomask << 1) | 1;
323 lobit = (lobit << 1);
324 himask = himask ^ lobit;
334 #define IPADDR_BUFLEN 20
336 static char *ipaddr_getbuf(void)
338 SBUF_DEFINE(16, IPADDR_BUFLEN);
342 /* The string buffer must be at least 16 bytes long */
343 string_t ipaddr_to_string(uint32_t addr)
353 snprintf(s, 16, "%d.%d.%d.%d", a, b, c, d);
357 string_t subnet_to_string(struct subnet sn)
359 uint32_t addr=sn.prefix;
368 snprintf(s, 19, "%d.%d.%d.%d/%d", a, b, c, d, sn.len);
372 static struct subnet string_item_to_subnet(item_t *i, cstring_t desc,
376 uint32_t a, b, c, d, n;
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");
388 if (strcmp(in,"default")==0) {
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
402 match=sscanf(in,"%u.%u.%u.%u/%u", &a, &b, &c, &d, &n);
404 cfgfatal(i->loc,desc,"\"%s\" is not a valid "
405 "subnet specification\n",in);
410 if (a>255 || b>255 || c>255 || d>255 || n>32) {
411 cfgfatal(i->loc,desc,"\"%s\": range error\n",in);
413 s.prefix=(a<<24)|(b<<16)|(c<<8)|(d);
414 s.mask=n?(~0UL << (32-n)):0;
416 if (s.prefix & ~s.mask) {
417 cfgfatal(i->loc,desc,"\"%s\": prefix not fully contained "
423 uint32_t string_item_to_ipaddr(const item_t *i, cstring_t desc)
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");
433 match=sscanf(i->data.string,"%u.%u.%u.%u", &a, &b, &c, &d);
435 cfgfatal(i->loc,desc,"\"%s\" is not a valid "
436 "IP address\n",i->data.string);
438 if (a>255 || b>255 || c>255 || d>255) {
439 cfgfatal(i->loc,desc,"\"%s\": range error\n",i->data.string);
441 return (a<<24)|(b<<16)|(c<<8)|(d);
444 struct ipset *string_list_to_ipset(list_t *l, struct cloc loc,
445 cstring_t module, cstring_t param)
447 struct ipset *r, *n, *isn;
454 for (i=0; i<e; i++) {
456 isn=ipset_from_subnet(string_item_to_subnet(item,param,&inv));
458 n=ipset_subtract(r,isn);
460 n=ipset_union(r,isn);