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