1 /* The 'ipset' data structure and related algorithms in this file were
2 inspired by the 'ipaddr.py' library from Cendio Systems AB. */
12 #define DEFAULT_ALLOC 2
13 #define EXTEND_ALLOC_BY 4
15 struct subnet_list *subnet_list_new(void)
17 struct subnet_list *r;
18 r=safe_malloc(sizeof(*r),"subnet_list_new:list");
20 r->alloc=DEFAULT_ALLOC;
21 r->list=safe_malloc_ary(sizeof(*r->list),r->alloc,"subnet_list_new:data");
25 void subnet_list_free(struct subnet_list *a)
27 if (a->list) free(a->list);
31 static void subnet_list_set_len(struct subnet_list *a, int32_t l)
37 assert(a->alloc < (int)(INT_MAX/sizeof(*nd))-EXTEND_ALLOC_BY);
38 na=a->alloc+EXTEND_ALLOC_BY;
39 nd=safe_realloc_ary(a->list,sizeof(*nd),na,"subnet_list_set_len");
46 void subnet_list_append(struct subnet_list *a, uint32_t prefix, int len)
49 assert(a->entries < INT_MAX);
50 subnet_list_set_len(a,a->entries+1);
51 sn=&a->list[a->entries-1];
54 sn->mask=len?(0xffffffff << (32-len)):0;
57 struct ipset *ipset_new(void)
60 r=safe_malloc(sizeof(*r),"ipset_new:set");
63 r->d=safe_malloc(sizeof(*r->d)*r->a,"ipset_new:data");
67 void ipset_free(struct ipset *a)
74 static void ipset_dump(struct ipset *a, string_t name)
79 for (i=0; i<a->l; i++) {
80 printf("[%08x-%08x] ",a->d[i].a,a->d[i].b);
86 struct ipset *ipset_from_subnet(struct subnet s)
93 r->d[0].b=s.prefix | (~s.mask);
97 struct ipset *ipset_from_subnet_list(struct subnet_list *l)
99 struct ipset *r, *a, *b;
103 for (i=0; i<l->entries; i++) {
104 a=ipset_from_subnet(l->list[i]);
113 static void ipset_set_len(struct ipset *a, int32_t l)
119 assert(a->a < INT_MAX-EXTEND_ALLOC_BY);
120 na=a->a+EXTEND_ALLOC_BY;
121 nd=safe_realloc_ary(a->d,sizeof(*nd),na,"ipset_set_len");
128 static void ipset_append_range(struct ipset *a, struct iprange r)
130 ipset_set_len(a,a->l+1);
134 struct ipset *ipset_union(struct ipset *a, struct ipset *b)
142 while (ia<a->l || ib<b->l) {
145 if (a->d[ia].a < b->d[ib].a)
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);
160 ipset_append_range(c,r);
165 struct ipset *ipset_intersection(struct ipset *a, struct ipset *b)
168 struct iprange ra, rb;
174 while (ia<a->l && ib<b->l) {
178 /* The first entry of a doesn't overlap with any part of b */
180 else if (ra.a > rb.b)
181 /* The first entry of b doesn't overlap with any part of a */
184 /* Trim away any leading edges */
186 /* a starts before b */
188 else if (ra.a > rb.a)
189 /* b starts before a */
192 /* Now the ranges start at the same point */
194 /* The ranges are equal */
195 ipset_append_range(r,ra);
198 } else if (ra.b < rb.b) {
199 /* a is the smaller range */
200 ipset_append_range(r,ra);
203 /* y is the smaller range */
204 ipset_append_range(r,rb);
212 struct ipset *ipset_complement(struct ipset *a)
222 for (i=0; i<a->l; i++) {
228 ipset_append_range(r,n);
232 if (pre!=0xffffffff) {
235 ipset_append_range(r,n);
241 struct ipset *ipset_subtract(struct ipset *a, struct ipset *b)
244 c=ipset_complement(b);
245 r=ipset_intersection(a,c);
250 bool_t ipset_is_empty(struct ipset *a)
255 bool_t ipset_contains_addr(struct ipset *a, uint32_t addr)
260 for (i=0; i<a->l; i++) {
262 if (addr>=r.a && addr<=r.b) return True;
263 if (addr<r.a) return False;
268 /* sub is a subset of super if it does not intersect with the complement
270 bool_t ipset_is_subset(struct ipset *super, struct ipset *sub)
272 struct ipset *superc;
276 superc=ipset_complement(super);
277 inter=ipset_intersection(superc,sub);
278 empty=ipset_is_empty(inter);
284 struct subnet_list *ipset_to_subnet_list(struct ipset *is)
286 struct subnet_list *r;
287 int64_t a,b,lobit,himask,lomask;
292 for (i=0; i<is->l; i++) {
301 if ((a & lomask) != 0) {
302 subnet_list_append(r,a,bits);
304 } else if ((b & lomask) != lomask) {
305 subnet_list_append(r,b&himask,bits);
308 lomask = (lomask << 1) | 1;
309 lobit = (lobit << 1);
310 himask = himask ^ lobit;
320 #define IPADDR_NBUFS_SHIFT 4
321 #define IPADDR_NBUFS (1 << IPADDR_NBUFS_SHIFT)
322 #define IPADDR_BUFLEN 20
324 static char *ipaddr_getbuf(void)
326 static int ipaddr_bufnum;
327 static char ipaddr_bufs[IPADDR_NBUFS][IPADDR_BUFLEN];
330 ipaddr_bufnum &= IPADDR_NBUFS-1;
331 return ipaddr_bufs[ipaddr_bufnum];
334 /* The string buffer must be at least 16 bytes long */
335 string_t ipaddr_to_string(uint32_t addr)
345 snprintf(s, 16, "%d.%d.%d.%d", a, b, c, d);
349 string_t subnet_to_string(struct subnet sn)
351 uint32_t addr=sn.prefix;
360 snprintf(s, 19, "%d.%d.%d.%d/%d", a, b, c, d, sn.len);
364 static struct subnet string_item_to_subnet(item_t *i, cstring_t desc,
368 uint32_t a, b, c, d, n;
374 /* i is not guaranteed to be a string */
375 if (i->type!=t_string) {
376 cfgfatal(i->loc,desc,"expecting a string (subnet specification)\n");
380 if (strcmp(in,"default")==0) {
391 /* We expect strings of the form "a.b.c.d[/n]", i.e. the dots are
392 NOT optional. The subnet mask is optional; if missing it is assumed
394 match=sscanf(in,"%u.%u.%u.%u/%u", &a, &b, &c, &d, &n);
396 cfgfatal(i->loc,desc,"\"%s\" is not a valid "
397 "subnet specification\n",in);
402 if (a>255 || b>255 || c>255 || d>255 || n>32) {
403 cfgfatal(i->loc,desc,"\"%s\": range error\n",in);
405 s.prefix=(a<<24)|(b<<16)|(c<<8)|(d);
406 s.mask=n?(~0UL << (32-n)):0;
408 if (s.prefix & ~s.mask) {
409 cfgfatal(i->loc,desc,"\"%s\": prefix not fully contained "
415 uint32_t string_item_to_ipaddr(const item_t *i, cstring_t desc)
420 /* i is not guaranteed to be a string */
421 if (i->type!=t_string) {
422 cfgfatal(i->loc,desc,"expecting a string (IP address)\n");
425 match=sscanf(i->data.string,"%u.%u.%u.%u", &a, &b, &c, &d);
427 cfgfatal(i->loc,desc,"\"%s\" is not a valid "
428 "IP address\n",i->data.string);
430 if (a>255 || b>255 || c>255 || d>255) {
431 cfgfatal(i->loc,desc,"\"%s\": range error\n",i->data.string);
433 return (a<<24)|(b<<16)|(c<<8)|(d);
436 struct ipset *string_list_to_ipset(list_t *l, struct cloc loc,
437 cstring_t module, cstring_t param)
439 struct ipset *r, *n, *isn;
446 for (i=0; i<e; i++) {
448 isn=ipset_from_subnet(string_item_to_subnet(item,param,&inv));
450 n=ipset_subtract(r,isn);
452 n=ipset_union(r,isn);