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