1 /* -*- coding: utf-8 -*-
2 * ----------------------------------------------------------------------
3 * Copyright © 2010-2012, RedJack, LLC.
4 * All rights reserved.
5 *
6 * Please see the LICENSE.txt file in this distribution for license
7 * details.
8 * ----------------------------------------------------------------------
9 */
10
11 #include <string.h>
12
13 #include <libcork/core.h>
14
15 #include "ipset/bdd/nodes.h"
16 #include "ipset/bits.h"
17 #include "ipset/ipset.h"
18 #include "ipset/logging.h"
19
20
21 #define IPV4_BIT_SIZE 32
22 #define IPV6_BIT_SIZE 128
23
24
25 /* Forward declarations */
26
27 static void
28 process_assignment(struct ipset_iterator *iterator);
29
30 static void
31 expand_ipv6(struct ipset_iterator *iterator);
32
33
34 /**
35 * Find the highest non-EITHER bit in an assignment, starting from the
36 * given bit index.
37 */
38 static unsigned int
find_last_non_either_bit(struct ipset_assignment * assignment,unsigned int starting_bit)39 find_last_non_either_bit(struct ipset_assignment *assignment,
40 unsigned int starting_bit)
41 {
42 unsigned int i;
43
44 for (i = starting_bit; i >= 1; i--) {
45 enum ipset_tribool value = ipset_assignment_get(assignment, i);
46 if (value != IPSET_EITHER) {
47 return i;
48 }
49 }
50
51 return 0;
52 }
53
54
55 /**
56 * Create a generic IP address object from the current expanded
57 * assignment.
58 */
59 static void
create_ip_address(struct ipset_iterator * iterator)60 create_ip_address(struct ipset_iterator *iterator)
61 {
62 struct cork_ip *addr = &iterator->addr;
63 struct ipset_expanded_assignment *exp = iterator->assignment_iterator;
64
65 /* Initialize the address to all 0 bits. */
66 memset(addr, 0, sizeof(struct cork_ip));
67
68 /* Check variable 0 to see if this is an IPv4 or IPv6 address. */
69 addr->version = IPSET_BIT_GET(exp->values.buf, 0)? 4: 6;
70
71 /* Copy bits from the expanded assignment. The number of bits to
72 * copy is given as the current netmask. We'll have calculated that
73 * already based on the non-expanded assignment. */
74 unsigned int i;
75 for (i = 0; i < iterator->cidr_prefix; i++) {
76 IPSET_BIT_SET(&addr->ip, i, IPSET_BIT_GET(exp->values.buf, i+1));
77 }
78
79 #if IPSET_DEBUG
80 char buf[CORK_IP_STRING_LENGTH];
81 cork_ip_to_raw_string(addr, buf);
82 DEBUG("Current IP address is %s/%u", buf, iterator->cidr_prefix);
83 #endif
84 }
85
86
87 /**
88 * Advance the BDD iterator, taking into account that some assignments
89 * need to be expanded twice.
90 */
91 static void
advance_assignment(struct ipset_iterator * iterator)92 advance_assignment(struct ipset_iterator *iterator)
93 {
94 /* Check the current state of the iterator to determine how to
95 * advance. */
96
97 /* In most cases, the assignment we just finished only needed to be
98 * expanded once. So we move on to the next assignment and process
99 * it. */
100 if (CORK_LIKELY(iterator->multiple_expansion_state ==
101 IPSET_ITERATOR_NORMAL))
102 {
103 ipset_bdd_iterator_advance(iterator->bdd_iterator);
104 process_assignment(iterator);
105 return;
106 }
107
108 /* If the assignment needs to be expanded twice, we'll do the IPv4
109 * expansion first. If that's what we've just finished, do the IPv6
110 * expansion next. */
111
112 if (iterator->multiple_expansion_state == IPSET_ITERATOR_MULTIPLE_IPV4) {
113 DEBUG("Expanding IPv6 second");
114
115 iterator->multiple_expansion_state = IPSET_ITERATOR_MULTIPLE_IPV6;
116 ipset_assignment_set
117 (iterator->bdd_iterator->assignment, 0, IPSET_FALSE);
118 expand_ipv6(iterator);
119 return;
120 }
121
122 /* If we've just finished the IPv6 expansion, then we've finished
123 * with this assignment. Before moving on to the next one, we have
124 * to reset variable 0 to EITHER (which it was before we started
125 * this whole mess). */
126
127 if (iterator->multiple_expansion_state == IPSET_ITERATOR_MULTIPLE_IPV6) {
128 DEBUG("Finished both expansions");
129
130 ipset_assignment_set
131 (iterator->bdd_iterator->assignment, 0, IPSET_EITHER);
132 ipset_bdd_iterator_advance(iterator->bdd_iterator);
133 process_assignment(iterator);
134 return;
135 }
136 }
137
138
139 /**
140 * Process the current expanded assignment in the current BDD
141 * assignment.
142 */
143 static void
process_expanded_assignment(struct ipset_iterator * iterator)144 process_expanded_assignment(struct ipset_iterator *iterator)
145 {
146 if (iterator->assignment_iterator->finished) {
147 /* If there isn't anything in the expanded assignment, advance
148 * to the next BDD assignment. */
149
150 DEBUG("Expanded assignment is finished");
151 ipset_expanded_assignment_free(iterator->assignment_iterator);
152 iterator->assignment_iterator = NULL;
153 advance_assignment(iterator);
154 } else {
155 /* Otherwise, we've found a fully expanded assignment, so create
156 * an IP address for it and return. */
157 create_ip_address(iterator);
158 }
159 }
160
161
162 /**
163 * Expand the current assignment as IPv4 addresses.
164 */
165 static void
expand_ipv4(struct ipset_iterator * iterator)166 expand_ipv4(struct ipset_iterator *iterator)
167 {
168 unsigned int last_bit;
169
170 if (iterator->summarize) {
171 last_bit = find_last_non_either_bit
172 (iterator->bdd_iterator->assignment, IPV4_BIT_SIZE);
173 DEBUG("Last non-either bit is %u", last_bit);
174 } else {
175 last_bit = IPV4_BIT_SIZE;
176 }
177
178 iterator->assignment_iterator =
179 ipset_assignment_expand
180 (iterator->bdd_iterator->assignment, last_bit + 1);
181 iterator->cidr_prefix = last_bit;
182
183 process_expanded_assignment(iterator);
184 }
185
186
187 /**
188 * Expand the current assignment as IPv4 addresses.
189 */
190 static void
expand_ipv6(struct ipset_iterator * iterator)191 expand_ipv6(struct ipset_iterator *iterator)
192 {
193 unsigned int last_bit;
194
195 if (iterator->summarize) {
196 last_bit = find_last_non_either_bit
197 (iterator->bdd_iterator->assignment, IPV6_BIT_SIZE);
198 DEBUG("Last non-either bit is %u", last_bit);
199 } else {
200 last_bit = IPV6_BIT_SIZE;
201 }
202
203 iterator->assignment_iterator =
204 ipset_assignment_expand
205 (iterator->bdd_iterator->assignment, last_bit + 1);
206 iterator->cidr_prefix = last_bit;
207
208 process_expanded_assignment(iterator);
209 }
210
211
212 /**
213 * Process the current assignment in the BDD iterator.
214 */
215
216 static void
process_assignment(struct ipset_iterator * iterator)217 process_assignment(struct ipset_iterator *iterator)
218 {
219 while (!iterator->bdd_iterator->finished) {
220 if (iterator->bdd_iterator->value == iterator->desired_value) {
221 /* If the BDD iterator hasn't finished, and the result of
222 * the function with this assignment matches what the caller
223 * wants, then we've found an assignment to generate IP
224 * addresses from.
225 *
226 * Try to expand this assignment, and process the first
227 * expanded assignment. We want 32 + 1 variables if the
228 * current address is IPv4; 128 + 1 if it's IPv6. */
229
230 DEBUG("Got a matching BDD assignment");
231 enum ipset_tribool address_type = ipset_assignment_get
232 (iterator->bdd_iterator->assignment, 0);
233
234 if (address_type == IPSET_FALSE) {
235 /* FALSE means IPv6*/
236 DEBUG("Assignment is IPv6");
237 iterator->multiple_expansion_state = IPSET_ITERATOR_NORMAL;
238 expand_ipv6(iterator);
239 return;
240 } else if (address_type == IPSET_TRUE) {
241 /* TRUE means IPv4*/
242 DEBUG("Assignment is IPv4");
243 iterator->multiple_expansion_state = IPSET_ITERATOR_NORMAL;
244 expand_ipv4(iterator);
245 return;
246 } else {
247 /* EITHER means that this assignment contains both IPv4
248 * and IPv6 addresses. Expand it as IPv4 first. */
249 DEBUG("Assignment is both IPv4 and IPv6");
250 DEBUG("Expanding IPv4 first");
251 iterator->multiple_expansion_state =
252 IPSET_ITERATOR_MULTIPLE_IPV4;
253 ipset_assignment_set
254 (iterator->bdd_iterator->assignment, 0, IPSET_TRUE);
255 expand_ipv4(iterator);
256 return;
257 }
258 }
259
260 /* The BDD iterator has a value, but it doesn't match the one we
261 * want. Advance the BDD iterator and try again. */
262 DEBUG("Value is %d, skipping", iterator->bdd_iterator->value);
263 ipset_bdd_iterator_advance(iterator->bdd_iterator);
264 }
265
266 /* If we fall through, then the BDD iterator has finished. That
267 * means there's nothing left for the set iterator. */
268
269 DEBUG("Set iterator is finished");
270 ipset_expanded_assignment_free(iterator->assignment_iterator);
271 iterator->assignment_iterator = NULL;
272
273 ipset_bdd_iterator_free(iterator->bdd_iterator);
274 iterator->bdd_iterator = NULL;
275 iterator->finished = true;
276 }
277
278
279 static struct ipset_iterator *
create_iterator(struct ip_set * set,bool desired_value,bool summarize)280 create_iterator(struct ip_set *set, bool desired_value, bool summarize)
281 {
282 /* First allocate the iterator itself. */
283 struct ipset_iterator *iterator = cork_new(struct ipset_iterator);
284 iterator->finished = false;
285 iterator->assignment_iterator = NULL;
286 iterator->desired_value = desired_value;
287 iterator->summarize = summarize;
288
289 /* Then create the iterator that returns each BDD assignment. */
290 DEBUG("Iterating set");
291 iterator->bdd_iterator = ipset_node_iterate(set->cache, set->set_bdd);
292
293 /* Then drill down from the current BDD assignment, creating an
294 * expanded assignment for it. */
295 process_assignment(iterator);
296 return iterator;
297 }
298
299
300 struct ipset_iterator *
ipset_iterate(struct ip_set * set,bool desired_value)301 ipset_iterate(struct ip_set *set, bool desired_value)
302 {
303 return create_iterator(set, desired_value, false);
304 }
305
306
307 struct ipset_iterator *
ipset_iterate_networks(struct ip_set * set,bool desired_value)308 ipset_iterate_networks(struct ip_set *set, bool desired_value)
309 {
310 return create_iterator(set, desired_value, true);
311 }
312
313
314 void
ipset_iterator_free(struct ipset_iterator * iterator)315 ipset_iterator_free(struct ipset_iterator *iterator)
316 {
317 if (iterator->bdd_iterator != NULL) {
318 ipset_bdd_iterator_free(iterator->bdd_iterator);
319 }
320 if (iterator->assignment_iterator != NULL) {
321 ipset_expanded_assignment_free(iterator->assignment_iterator);
322 }
323 free(iterator);
324 }
325
326
327 void
ipset_iterator_advance(struct ipset_iterator * iterator)328 ipset_iterator_advance(struct ipset_iterator *iterator)
329 {
330 /* If we're already at the end of the iterator, don't do anything. */
331
332 if (CORK_UNLIKELY(iterator->finished)) {
333 return;
334 }
335
336 /* Otherwise, advance the expanded assignment iterator to the next
337 * assignment, and then drill down into it. */
338
339 DEBUG("Advancing set iterator");
340 ipset_expanded_assignment_advance(iterator->assignment_iterator);
341 process_expanded_assignment(iterator);
342 }
343