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
);