1 /* vim: set expandtab ts=4 sw=4: */
2 /*
3 * You may redistribute this program and/or modify it under the terms of
4 * the GNU General Public License as published by the Free Software Foundation,
5 * either version 3 of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program. If not, see <https://www.gnu.org/licenses/>.
14 */
15 #include "benc/String.h"
16 #include "benc/Dict.h"
17 #include "util/platform/Sockaddr.h"
18 #include "exception/Except.h"
19 #include "benc/List.h"
20 #include "tunnel/RouteGen.h"
21 #include "util/log/Log.h"
22 #include "util/Identity.h"
23 #include "util/Bits.h"
24 #include "util/platform/netdev/NetDev.h"
25
26 struct Prefix6
27 {
28 uint64_t highBits;
29 uint64_t lowBits;
30 int prefix;
31 struct Allocator* alloc;
32 };
comparePrefixes6(struct Prefix6 * a,struct Prefix6 * b)33 static int comparePrefixes6(struct Prefix6* a, struct Prefix6* b)
34 {
35 if (a->prefix != b->prefix) {
36 return (a->prefix < b->prefix) ? -1 : 1;
37 }
38 if (a->highBits != b->highBits) {
39 return (a->highBits < b->highBits) ? 1 : -1;
40 }
41 if (a->lowBits != b->lowBits) {
42 return (a->lowBits < b->lowBits) ? 1 : -1;
43 }
44 return 0;
45 }
46 #define ArrayList_COMPARE comparePrefixes6
47 #define ArrayList_TYPE struct Prefix6
48 #define ArrayList_NAME OfPrefix6
49 #include "util/ArrayList.h"
50
51 struct Prefix4
52 {
53 uint32_t bits;
54 int prefix;
55 struct Allocator* alloc;
56 };
comparePrefixes4(struct Prefix4 * a,struct Prefix4 * b)57 static int comparePrefixes4(struct Prefix4* a, struct Prefix4* b)
58 {
59 if (a->prefix != b->prefix) {
60 return (a->prefix < b->prefix) ? -1 : 1;
61 }
62 if (a->bits != b->bits) {
63 return (a->bits < b->bits) ? 1 : -1;
64 }
65 return 0;
66 }
67 #define ArrayList_COMPARE comparePrefixes4
68 #define ArrayList_TYPE struct Prefix4
69 #define ArrayList_NAME OfPrefix4
70 #include "util/ArrayList.h"
71
72 struct Prefix46 {
73 struct ArrayList_OfPrefix4* prefix4;
74 struct ArrayList_OfPrefix6* prefix6;
75 };
76
77 struct RouteGen_pvt
78 {
79 struct RouteGen pub;
80 struct ArrayList_OfPrefix6* prefixes6;
81 struct ArrayList_OfPrefix6* localPrefixes6;
82 struct ArrayList_OfPrefix6* exceptions6;
83
84 struct ArrayList_OfPrefix4* prefixes4;
85 struct ArrayList_OfPrefix4* localPrefixes4;
86 struct ArrayList_OfPrefix4* exceptions4;
87
88 struct Allocator* alloc;
89 struct Log* log;
90
91 Identity
92 };
93
sockaddrForPrefix4(struct Allocator * alloc,struct Prefix4 * pfx4)94 static struct Sockaddr* sockaddrForPrefix4(struct Allocator* alloc, struct Prefix4* pfx4)
95 {
96 union {
97 uint32_t addr_be;
98 uint8_t bytes[4];
99 } un;
100 un.addr_be = Endian_hostToBigEndian32(pfx4->bits);
101 struct Sockaddr* out = Sockaddr_fromBytes(un.bytes, Sockaddr_AF_INET, alloc);
102 out->flags |= Sockaddr_flags_PREFIX;
103 out->prefix = pfx4->prefix;
104 return out;
105 }
106
printPrefix4(struct Allocator * alloc,struct Prefix4 * pfx4)107 static String* printPrefix4(struct Allocator* alloc, struct Prefix4* pfx4)
108 {
109 return String_new(Sockaddr_print(sockaddrForPrefix4(alloc, pfx4), alloc), alloc);
110 }
111
sockaddrForPrefix6(struct Allocator * alloc,struct Prefix6 * pfx6)112 static struct Sockaddr* sockaddrForPrefix6(struct Allocator* alloc, struct Prefix6* pfx6)
113 {
114 union {
115 struct {
116 uint64_t highBits_be;
117 uint64_t lowBits_be;
118 } longs;
119 uint8_t bytes[16];
120 } un;
121 un.longs.highBits_be = Endian_hostToBigEndian64(pfx6->highBits);
122 un.longs.lowBits_be = Endian_hostToBigEndian64(pfx6->lowBits);
123 struct Sockaddr* out = Sockaddr_fromBytes(un.bytes, Sockaddr_AF_INET6, alloc);
124 out->flags |= Sockaddr_flags_PREFIX;
125 out->prefix = pfx6->prefix;
126 return out;
127 }
128
printPrefix6(struct Allocator * alloc,struct Prefix6 * pfx6)129 static String* printPrefix6(struct Allocator* alloc, struct Prefix6* pfx6)
130 {
131 return String_new(Sockaddr_print(sockaddrForPrefix6(alloc, pfx6), alloc), alloc);
132 }
133
sockaddrToPrefix4(struct Sockaddr * sa,struct Allocator * allocator)134 static struct Prefix4* sockaddrToPrefix4(struct Sockaddr* sa, struct Allocator* allocator)
135 {
136 uint32_t addrNum;
137 uint8_t* addr;
138 Assert_true(Sockaddr_getAddress(sa, &addr) == 4);
139 Bits_memcpy(&addrNum, addr, 4);
140 struct Allocator* alloc = Allocator_child(allocator);
141 struct Prefix4* out = Allocator_calloc(alloc, sizeof(struct Prefix4), 1);
142 out->bits = Endian_bigEndianToHost32(addrNum);
143 int pfx = Sockaddr_getPrefix(sa);
144 Assert_true(pfx > -1);
145 out->prefix = pfx;
146 out->alloc = alloc;
147 return out;
148 }
149
sockaddrToPrefix6(struct Sockaddr * sa,struct Allocator * allocator)150 static struct Prefix6* sockaddrToPrefix6(struct Sockaddr* sa, struct Allocator* allocator)
151 {
152 struct {
153 uint64_t highBits_be;
154 uint64_t lowBits_be;
155 } longs;
156 uint8_t* addr;
157 Assert_true(Sockaddr_getAddress(sa, &addr) == 16);
158 Bits_memcpy(&longs, addr, 16);
159 struct Allocator* alloc = Allocator_child(allocator);
160 struct Prefix6* out = Allocator_calloc(alloc, sizeof(struct Prefix6), 1);
161 out->highBits = Endian_bigEndianToHost64(longs.highBits_be);
162 out->lowBits = Endian_bigEndianToHost64(longs.lowBits_be);
163 int pfx = Sockaddr_getPrefix(sa);
164 Assert_true(pfx > -1);
165 out->prefix = pfx;
166 out->alloc = alloc;
167 return out;
168 }
169
addSomething(struct RouteGen_pvt * rp,struct Sockaddr * exempt,struct ArrayList_OfPrefix6 * list6,struct ArrayList_OfPrefix4 * list4)170 static void addSomething(struct RouteGen_pvt* rp,
171 struct Sockaddr* exempt,
172 struct ArrayList_OfPrefix6* list6,
173 struct ArrayList_OfPrefix4* list4)
174 {
175 if (Sockaddr_getFamily(exempt) == Sockaddr_AF_INET) {
176 struct Prefix4* p4 = sockaddrToPrefix4(exempt, rp->alloc);
177 ArrayList_OfPrefix4_add(list4, p4);
178 } else if (Sockaddr_getFamily(exempt) == Sockaddr_AF_INET6) {
179 struct Prefix6* p6 = sockaddrToPrefix6(exempt, rp->alloc);
180 ArrayList_OfPrefix6_add(list6, p6);
181 } else {
182 Assert_failure("unexpected addr type");
183 }
184 rp->pub.hasUncommittedChanges = true;
185 }
186
RouteGen_addException(struct RouteGen * rg,struct Sockaddr * destination)187 void RouteGen_addException(struct RouteGen* rg, struct Sockaddr* destination)
188 {
189 struct RouteGen_pvt* rp = Identity_check((struct RouteGen_pvt*) rg);
190 addSomething(rp, destination, rp->exceptions6, rp->exceptions4);
191 }
192
RouteGen_addPrefix(struct RouteGen * rg,struct Sockaddr * destination)193 void RouteGen_addPrefix(struct RouteGen* rg, struct Sockaddr* destination)
194 {
195 struct RouteGen_pvt* rp = Identity_check((struct RouteGen_pvt*) rg);
196 addSomething(rp, destination, rp->prefixes6, rp->prefixes4);
197 }
198
RouteGen_addLocalPrefix(struct RouteGen * rg,struct Sockaddr * destination)199 void RouteGen_addLocalPrefix(struct RouteGen* rg, struct Sockaddr* destination)
200 {
201 struct RouteGen_pvt* rp = Identity_check((struct RouteGen_pvt*) rg);
202 addSomething(rp, destination, rp->localPrefixes6, rp->localPrefixes4);
203 }
204
getSomething(struct RouteGen_pvt * rp,struct Allocator * alloc,struct ArrayList_OfPrefix6 * list6,struct ArrayList_OfPrefix4 * list4)205 static Dict* getSomething(struct RouteGen_pvt* rp,
206 struct Allocator* alloc,
207 struct ArrayList_OfPrefix6* list6,
208 struct ArrayList_OfPrefix4* list4)
209 {
210 ArrayList_OfPrefix6_sort(list6);
211 ArrayList_OfPrefix4_sort(list4);
212 List* prefixes4 = List_new(alloc);
213 for (int i = 0; i < list4->length; i++) {
214 struct Prefix4* pfx4 = ArrayList_OfPrefix4_get(list4, i);
215 List_addString(prefixes4, printPrefix4(alloc, pfx4), alloc);
216 }
217 List* prefixes6 = List_new(alloc);
218 for (int i = 0; i < list6->length; i++) {
219 struct Prefix6* pfx6 = ArrayList_OfPrefix6_get(list6, i);
220 List_addString(prefixes6, printPrefix6(alloc, pfx6), alloc);
221 }
222 Dict* out = Dict_new(alloc);
223 Dict_putList(out, String_new("ipv4", alloc), prefixes4, alloc);
224 Dict_putList(out, String_new("ipv6", alloc), prefixes6, alloc);
225 return out;
226 }
227
RouteGen_getPrefixes(struct RouteGen * rg,struct Allocator * alloc)228 Dict* RouteGen_getPrefixes(struct RouteGen* rg, struct Allocator* alloc)
229 {
230 struct RouteGen_pvt* rp = Identity_check((struct RouteGen_pvt*) rg);
231 return getSomething(rp, alloc, rp->prefixes6, rp->prefixes4);
232 }
233
RouteGen_getLocalPrefixes(struct RouteGen * rg,struct Allocator * alloc)234 Dict* RouteGen_getLocalPrefixes(struct RouteGen* rg, struct Allocator* alloc)
235 {
236 struct RouteGen_pvt* rp = Identity_check((struct RouteGen_pvt*) rg);
237 return getSomething(rp, alloc, rp->localPrefixes6, rp->localPrefixes4);
238 }
239
RouteGen_getExceptions(struct RouteGen * rg,struct Allocator * alloc)240 Dict* RouteGen_getExceptions(struct RouteGen* rg, struct Allocator* alloc)
241 {
242 struct RouteGen_pvt* rp = Identity_check((struct RouteGen_pvt*) rg);
243 return getSomething(rp, alloc, rp->exceptions6, rp->exceptions4);
244 }
245
removeSomething(struct RouteGen_pvt * rp,struct Sockaddr * toRemove,struct ArrayList_OfPrefix6 * list6,struct ArrayList_OfPrefix4 * list4)246 static bool removeSomething(struct RouteGen_pvt* rp,
247 struct Sockaddr* toRemove,
248 struct ArrayList_OfPrefix6* list6,
249 struct ArrayList_OfPrefix4* list4)
250 {
251 struct Allocator* tempAlloc = Allocator_child(rp->alloc);
252 bool ret = false;
253 if (Sockaddr_getFamily(toRemove) == Sockaddr_AF_INET) {
254 struct Prefix4* p4 = sockaddrToPrefix4(toRemove, tempAlloc);
255 for (int i = list4->length - 1; i >= 0; i--) {
256 struct Prefix4* p42 = ArrayList_OfPrefix4_get(list4, i);
257 if (!comparePrefixes4(p4, p42)) {
258 ArrayList_OfPrefix4_remove(list4, i);
259 ret = true;
260 }
261 }
262 } else if (Sockaddr_getFamily(toRemove) == Sockaddr_AF_INET6) {
263 struct Prefix6* p6 = sockaddrToPrefix6(toRemove, tempAlloc);
264 for (int i = list6->length - 1; i >= 0; i--) {
265 struct Prefix6* p62 = ArrayList_OfPrefix6_get(list6, i);
266 if (!comparePrefixes6(p6, p62)) {
267 ArrayList_OfPrefix6_remove(list6, i);
268 ret = true;
269 }
270 }
271 } else {
272 Assert_failure("unexpected addr type");
273 }
274 Allocator_free(tempAlloc);
275 return ret;
276 }
277
RouteGen_removePrefix(struct RouteGen * rg,struct Sockaddr * toRemove)278 bool RouteGen_removePrefix(struct RouteGen* rg, struct Sockaddr* toRemove)
279 {
280 struct RouteGen_pvt* rp = Identity_check((struct RouteGen_pvt*) rg);
281 return removeSomething(rp, toRemove, rp->prefixes6, rp->prefixes4);
282 }
283
RouteGen_removeLocalPrefix(struct RouteGen * rg,struct Sockaddr * toRemove)284 bool RouteGen_removeLocalPrefix(struct RouteGen* rg, struct Sockaddr* toRemove)
285 {
286 struct RouteGen_pvt* rp = Identity_check((struct RouteGen_pvt*) rg);
287 return removeSomething(rp, toRemove, rp->localPrefixes6, rp->localPrefixes4);
288 }
289
RouteGen_removeException(struct RouteGen * rg,struct Sockaddr * toRemove)290 bool RouteGen_removeException(struct RouteGen* rg, struct Sockaddr* toRemove)
291 {
292 struct RouteGen_pvt* rp = Identity_check((struct RouteGen_pvt*) rg);
293 return removeSomething(rp, toRemove, rp->exceptions6, rp->exceptions4);
294 }
295
invertPrefix4(struct Prefix4 * toInvert,struct Allocator * alloc)296 static struct ArrayList_OfPrefix4* invertPrefix4(struct Prefix4* toInvert, struct Allocator* alloc)
297 {
298 struct ArrayList_OfPrefix4* result = ArrayList_OfPrefix4_new(alloc);
299 for (int i = 32 - toInvert->prefix; i < 32; i++) {
300 struct Prefix4* pfx = Allocator_calloc(alloc, sizeof(struct Prefix4), 1);
301 pfx->bits = ( toInvert->bits & ((uint32_t)~0 << i) ) ^ ((uint32_t)1 << i);
302 pfx->prefix = 32 - i;
303 ArrayList_OfPrefix4_add(result, pfx);
304 }
305 return result;
306 }
307
invertPrefix6(struct Prefix6 * toInvert,struct Allocator * alloc)308 static struct ArrayList_OfPrefix6* invertPrefix6(struct Prefix6* toInvert, struct Allocator* alloc)
309 {
310 struct ArrayList_OfPrefix6* result = ArrayList_OfPrefix6_new(alloc);
311 for (int i = 128 - toInvert->prefix; i < 128; i++) {
312 struct Prefix6* pfx = Allocator_calloc(alloc, sizeof(struct Prefix6), 1);
313 if (i >= 64) {
314 pfx->highBits = ( toInvert->highBits & (~((uint64_t)0) << (i-64)) ) ^
315 (((uint64_t)1) << (i-64));
316 pfx->lowBits = 0;
317 } else {
318 pfx->highBits = toInvert->highBits;
319 pfx->lowBits = ( toInvert->lowBits & (~((uint64_t)0) << i) ) ^ (((uint64_t)1) << i);
320 }
321 pfx->prefix = 128 - i;
322 ArrayList_OfPrefix6_add(result, pfx);
323 }
324 return result;
325 }
326
isSubsetOf4(struct Prefix4 * isSubset,struct Prefix4 * isSuperset)327 static bool isSubsetOf4(struct Prefix4* isSubset, struct Prefix4* isSuperset)
328 {
329 if (isSuperset->prefix > isSubset->prefix) { return false; }
330 if (isSuperset->prefix >= 32) {
331 return isSuperset->bits == isSubset->bits;
332 }
333 if (!isSuperset->prefix) { return true; }
334 uint32_t shift = 32 - isSuperset->prefix;
335 return (isSuperset->bits >> shift) == (isSubset->bits >> shift);
336 }
337
isSubsetOf6(struct Prefix6 * isSubset,struct Prefix6 * isSuperset)338 static bool isSubsetOf6(struct Prefix6* isSubset, struct Prefix6* isSuperset)
339 {
340 if (isSuperset->prefix > isSubset->prefix) { return false; }
341 if (isSuperset->prefix > 64) {
342 uint64_t shift = 128 - isSuperset->prefix;
343 return isSuperset->highBits == isSubset->highBits &&
344 (isSuperset->lowBits >> shift) == (isSubset->lowBits >> shift);
345 } else if (isSuperset->prefix) {
346 uint64_t shift = 64 - isSuperset->prefix;
347 return (isSuperset->highBits >> shift) == (isSubset->highBits >> shift);
348 } else {
349 return true;
350 }
351 }
352
mergePrefixSets4(struct ArrayList_OfPrefix4 * mergeInto,struct ArrayList_OfPrefix4 * prefixes)353 static void mergePrefixSets4(struct ArrayList_OfPrefix4* mergeInto,
354 struct ArrayList_OfPrefix4* prefixes)
355 {
356 struct Prefix4* highestPrefix = NULL;
357 for (int j = 0; j < prefixes->length; j++) {
358 struct Prefix4* result = ArrayList_OfPrefix4_get(prefixes, j);
359 Assert_true(result);
360 if (!highestPrefix || highestPrefix->prefix < result->prefix) {
361 highestPrefix = result;
362 }
363 }
364
365 struct Prefix4 target;
366 Bits_memcpy(&target, highestPrefix, sizeof(struct Prefix4));
367 target.bits ^= (target.prefix) ? ((uint32_t)1 << (32 - target.prefix)) : 0;
368 for (int i = mergeInto->length - 1; i >= 0; i--) {
369 struct Prefix4* result = ArrayList_OfPrefix4_get(mergeInto, i);
370 Assert_true(result);
371 if (isSubsetOf4(&target, result)) {
372 ArrayList_OfPrefix4_remove(mergeInto, i);
373 }
374 }
375
376 for (int i = 0; i < prefixes->length; i++) {
377 bool include = true;
378 struct Prefix4* toInclude = ArrayList_OfPrefix4_get(prefixes, i);
379 for (int j = 0; j < mergeInto->length; j++) {
380 struct Prefix4* test = ArrayList_OfPrefix4_get(mergeInto, j);
381 if (isSubsetOf4(test, toInclude)) {
382 include = false;
383 break;
384 }
385 }
386 if (include) {
387 ArrayList_OfPrefix4_add(mergeInto, toInclude);
388 }
389 }
390 }
391
mergePrefixSets6(struct ArrayList_OfPrefix6 * mergeInto,struct ArrayList_OfPrefix6 * prefixes,struct Allocator * alloc)392 static void mergePrefixSets6(struct ArrayList_OfPrefix6* mergeInto,
393 struct ArrayList_OfPrefix6* prefixes, struct Allocator* alloc)
394 {
395 struct Prefix6* highestPrefix = NULL;
396 for (int j = 0; j < prefixes->length; j++) {
397 struct Prefix6* result = ArrayList_OfPrefix6_get(prefixes, j);
398 Assert_true(result);
399 if (!highestPrefix || highestPrefix->prefix < result->prefix) {
400 highestPrefix = result;
401 }
402 }
403
404 struct Prefix6 target;
405 Bits_memcpy(&target, highestPrefix, sizeof(struct Prefix6));
406 if (target.prefix > 64) {
407 target.lowBits ^= (((uint64_t)1) << (128 - target.prefix));
408 } else if (target.prefix) {
409 target.highBits ^= (((uint64_t)1) << (64 - target.prefix));
410 target.lowBits = 0;
411 }
412
413 for (int i = mergeInto->length - 1; i >= 0; i--) {
414 struct Prefix6* result = ArrayList_OfPrefix6_get(mergeInto, i);
415 Assert_true(result);
416 if (isSubsetOf6(&target, result)) {
417 ArrayList_OfPrefix6_remove(mergeInto, i);
418 }
419 }
420
421 for (int i = 0; i < prefixes->length; i++) {
422 bool include = true;
423 struct Prefix6* toInclude = ArrayList_OfPrefix6_get(prefixes, i);
424 for (int j = 0; j < mergeInto->length; j++) {
425 struct Prefix6* test = ArrayList_OfPrefix6_get(mergeInto, j);
426 if (isSubsetOf6(test, toInclude)) {
427 include = false;
428 break;
429 }
430 }
431 if (include) {
432 ArrayList_OfPrefix6_add(mergeInto, toInclude);
433 }
434 }
435 }
436
clonePrefix4(struct Prefix4 * original,struct Allocator * alloc)437 static struct Prefix4* clonePrefix4(struct Prefix4* original, struct Allocator* alloc)
438 {
439 struct Prefix4* clone = Allocator_clone(alloc, original);
440 clone->alloc = alloc;
441 return clone;
442 }
443
clonePrefix6(struct Prefix6 * original,struct Allocator * alloc)444 static struct Prefix6* clonePrefix6(struct Prefix6* original, struct Allocator* alloc)
445 {
446 struct Prefix6* clone = Allocator_clone(alloc, original);
447 clone->alloc = alloc;
448 return clone;
449 }
450
mkPseudoDefault4(struct Allocator * alloc)451 static struct ArrayList_OfPrefix4* mkPseudoDefault4(struct Allocator* alloc)
452 {
453 struct Prefix4* pfxs = Allocator_calloc(alloc, sizeof(struct Prefix4), 2);
454 pfxs[0].prefix = 1;
455 pfxs[1].prefix = 1;
456 pfxs[1].bits = 0x80000000;
457 struct ArrayList_OfPrefix4* out = ArrayList_OfPrefix4_new(alloc);
458 ArrayList_OfPrefix4_add(out, &pfxs[0]);
459 ArrayList_OfPrefix4_add(out, &pfxs[1]);
460 return out;
461 }
462
mkPseudoDefault6(struct Allocator * alloc)463 static struct ArrayList_OfPrefix6* mkPseudoDefault6(struct Allocator* alloc)
464 {
465 struct Prefix6* pfxs = Allocator_calloc(alloc, sizeof(struct Prefix6), 2);
466 pfxs[0].prefix = 1;
467 pfxs[1].prefix = 1;
468 pfxs[1].highBits = 0x8000000000000000ull;
469 struct ArrayList_OfPrefix6* out = ArrayList_OfPrefix6_new(alloc);
470 ArrayList_OfPrefix6_add(out, &pfxs[0]);
471 ArrayList_OfPrefix6_add(out, &pfxs[1]);
472 return out;
473 }
474
isDefaultRoute4(struct ArrayList_OfPrefix4 * prefixes)475 static bool isDefaultRoute4(struct ArrayList_OfPrefix4* prefixes)
476 {
477 if (prefixes->length != 1) { return false; }
478 struct Prefix4* pfx = ArrayList_OfPrefix4_get(prefixes, 0);
479 return pfx->prefix == 0;
480 }
481
isDefaultRoute6(struct ArrayList_OfPrefix6 * prefixes)482 static bool isDefaultRoute6(struct ArrayList_OfPrefix6* prefixes)
483 {
484 if (prefixes->length != 1) { return false; }
485 struct Prefix6* pfx = ArrayList_OfPrefix6_get(prefixes, 0);
486 return pfx->prefix == 0;
487 }
488
genPrefixes4(struct ArrayList_OfPrefix4 * prefixes,struct ArrayList_OfPrefix4 * exceptions,struct ArrayList_OfPrefix4 * localPrefixes,struct Allocator * alloc)489 static struct ArrayList_OfPrefix4* genPrefixes4(struct ArrayList_OfPrefix4* prefixes,
490 struct ArrayList_OfPrefix4* exceptions,
491 struct ArrayList_OfPrefix4* localPrefixes,
492 struct Allocator* alloc)
493 {
494 struct Allocator* tempAlloc = Allocator_child(alloc);
495
496 struct ArrayList_OfPrefix4* effectiveLocalPrefixes = ArrayList_OfPrefix4_new(tempAlloc);
497 for (int i = 0; i < localPrefixes->length; i++) {
498 bool add = true;
499 struct Prefix4* localPfx = ArrayList_OfPrefix4_get(localPrefixes, i);
500 for (int j = 0; j < prefixes->length; j++) {
501 struct Prefix4* pfx = ArrayList_OfPrefix4_get(prefixes, j);
502 if (isSubsetOf4(pfx, localPfx)) {
503 add = false;
504 break;
505 }
506 }
507 if (add) {
508 ArrayList_OfPrefix4_add(effectiveLocalPrefixes, localPfx);
509 }
510 }
511
512 struct ArrayList_OfPrefix4* allPrefixes = ArrayList_OfPrefix4_new(tempAlloc);
513 for (int i = 0; i < exceptions->length; i++) {
514 struct Prefix4* pfxToInvert = ArrayList_OfPrefix4_get(exceptions, i);
515 bool add = true;
516 for (int j = 0; j < effectiveLocalPrefixes->length; j++) {
517 struct Prefix4* localPfx = ArrayList_OfPrefix4_get(effectiveLocalPrefixes, j);
518 if (isSubsetOf4(pfxToInvert, localPfx)) {
519 add = false;
520 break;
521 }
522 }
523 if (add) {
524 struct ArrayList_OfPrefix4* prefixes4 = invertPrefix4(pfxToInvert, tempAlloc);
525 mergePrefixSets4(allPrefixes, prefixes4);
526 }
527 }
528
529 for (int i = allPrefixes->length - 2; i >= 0; i--) {
530 struct Prefix4* pfx = ArrayList_OfPrefix4_get(allPrefixes, i);
531 struct Prefix4* pfx2 = ArrayList_OfPrefix4_get(allPrefixes, i+1);
532 if (isSubsetOf4(pfx2, pfx)) {
533 ArrayList_OfPrefix4_remove(allPrefixes, i+1);
534 if (i < (allPrefixes->length - 2)) { i++; }
535 }
536 }
537
538 for (int i = 0; i < prefixes->length; i++) {
539 struct Prefix4* pfx = ArrayList_OfPrefix4_get(prefixes, i);
540 int addPrefix = true;
541 for (int j = allPrefixes->length - 1; j >= 0; j--) {
542 struct Prefix4* pfx2 = ArrayList_OfPrefix4_get(allPrefixes, j);
543 if (isSubsetOf4(pfx2, pfx)) {
544 addPrefix = false;
545 }
546 }
547 if (addPrefix) {
548 ArrayList_OfPrefix4_add(allPrefixes, pfx);
549 }
550 }
551
552 ArrayList_OfPrefix4_sort(allPrefixes);
553
554 struct ArrayList_OfPrefix4* out = ArrayList_OfPrefix4_new(alloc);
555 for (int i = 0; i < allPrefixes->length; i++) {
556 struct Prefix4* pfx = ArrayList_OfPrefix4_get(allPrefixes, i);
557 for (int j = 0; j < prefixes->length; j++) {
558 struct Prefix4* pfx2 = ArrayList_OfPrefix4_get(prefixes, j);
559 if (isSubsetOf4(pfx, pfx2)) {
560 ArrayList_OfPrefix4_add(out, clonePrefix4(pfx, alloc));
561 break;
562 }
563 }
564 }
565 Allocator_free(tempAlloc);
566 return out;
567 }
568
569 // Annoyingly, this function is *exactly* the same content as genPrefixes4()
570 // but with evert 4 converted to a 6...
genPrefixes6(struct ArrayList_OfPrefix6 * prefixes,struct ArrayList_OfPrefix6 * exceptions,struct ArrayList_OfPrefix6 * localPrefixes,struct Allocator * alloc)571 static struct ArrayList_OfPrefix6* genPrefixes6(struct ArrayList_OfPrefix6* prefixes,
572 struct ArrayList_OfPrefix6* exceptions,
573 struct ArrayList_OfPrefix6* localPrefixes,
574 struct Allocator* alloc)
575 {
576 struct Allocator* tempAlloc = Allocator_child(alloc);
577
578 struct ArrayList_OfPrefix6* effectiveLocalPrefixes = ArrayList_OfPrefix6_new(tempAlloc);
579 for (int i = 0; i < localPrefixes->length; i++) {
580 bool add = true;
581 struct Prefix6* localPfx = ArrayList_OfPrefix6_get(localPrefixes, i);
582 for (int j = 0; j < prefixes->length; j++) {
583 struct Prefix6* pfx = ArrayList_OfPrefix6_get(prefixes, j);
584 if (isSubsetOf6(pfx, localPfx)) {
585 add = false;
586 break;
587 }
588 }
589 if (add) {
590 ArrayList_OfPrefix6_add(effectiveLocalPrefixes, localPfx);
591 }
592 }
593
594 struct ArrayList_OfPrefix6* allPrefixes = ArrayList_OfPrefix6_new(tempAlloc);
595 for (int i = 0; i < exceptions->length; i++) {
596 struct Prefix6* pfxToInvert = ArrayList_OfPrefix6_get(exceptions, i);
597 bool add = true;
598 for (int j = 0; j < effectiveLocalPrefixes->length; j++) {
599 struct Prefix6* localPfx = ArrayList_OfPrefix6_get(effectiveLocalPrefixes, j);
600 if (isSubsetOf6(pfxToInvert, localPfx)) {
601 add = false;
602 break;
603 }
604 }
605 if (add) {
606 struct ArrayList_OfPrefix6* prefixes6 = invertPrefix6(pfxToInvert, tempAlloc);
607 mergePrefixSets6(allPrefixes, prefixes6, alloc);
608 }
609 }
610
611 ArrayList_OfPrefix6_sort(allPrefixes);
612
613 for (int i = allPrefixes->length - 2; i >= 0; i--) {
614 struct Prefix6* pfx = ArrayList_OfPrefix6_get(allPrefixes, i);
615 struct Prefix6* pfx2 = ArrayList_OfPrefix6_get(allPrefixes, i+1);
616 if (isSubsetOf6(pfx2, pfx)) {
617 ArrayList_OfPrefix6_remove(allPrefixes, i+1);
618 if (i < (allPrefixes->length - 2)) { i++; }
619 }
620 }
621
622 for (int i = 0; i < prefixes->length; i++) {
623 struct Prefix6* pfx = ArrayList_OfPrefix6_get(prefixes, i);
624 int addPrefix = true;
625 for (int j = allPrefixes->length - 1; j >= 0; j--) {
626 struct Prefix6* pfx2 = ArrayList_OfPrefix6_get(allPrefixes, j);
627 if (isSubsetOf6(pfx2, pfx)) {
628 addPrefix = false;
629 }
630 }
631 if (addPrefix) {
632 ArrayList_OfPrefix6_add(allPrefixes, pfx);
633 }
634 }
635
636 ArrayList_OfPrefix6_sort(allPrefixes);
637
638 struct ArrayList_OfPrefix6* out = ArrayList_OfPrefix6_new(alloc);
639 for (int i = 0; i < allPrefixes->length; i++) {
640 struct Prefix6* pfx = ArrayList_OfPrefix6_get(allPrefixes, i);
641 for (int j = 0; j < prefixes->length; j++) {
642 struct Prefix6* pfx2 = ArrayList_OfPrefix6_get(prefixes, j);
643 if (isSubsetOf6(pfx, pfx2)) {
644 ArrayList_OfPrefix6_add(out, clonePrefix6(pfx, alloc));
645 break;
646 }
647 }
648 }
649 Allocator_free(tempAlloc);
650 return out;
651 }
652
getGeneratedRoutes(struct RouteGen_pvt * rp,struct Allocator * alloc)653 static struct Prefix46* getGeneratedRoutes(struct RouteGen_pvt* rp, struct Allocator* alloc)
654 {
655 struct Prefix46* out = Allocator_calloc(alloc, sizeof(struct Prefix46), 1);
656 if (rp->prefixes4->length > 0) {
657 out->prefix4 = genPrefixes4(rp->prefixes4, rp->exceptions4, rp->localPrefixes4, alloc);
658 if (isDefaultRoute4(out->prefix4)) {
659 out->prefix4 = mkPseudoDefault4(alloc);
660 }
661 } else {
662 out->prefix4 = ArrayList_OfPrefix4_new(alloc);
663 }
664 if (rp->prefixes6->length > 0) {
665 out->prefix6 = genPrefixes6(rp->prefixes6, rp->exceptions6, rp->localPrefixes6, alloc);
666 if (isDefaultRoute6(out->prefix6)) {
667 out->prefix6 = mkPseudoDefault6(alloc);
668 }
669 } else {
670 out->prefix6 = ArrayList_OfPrefix6_new(alloc);
671 }
672 return out;
673 }
674
RouteGen_getGeneratedRoutes(struct RouteGen * rg,struct Allocator * alloc)675 Dict* RouteGen_getGeneratedRoutes(struct RouteGen* rg, struct Allocator* alloc)
676 {
677 struct RouteGen_pvt* rp = Identity_check((struct RouteGen_pvt*) rg);
678 struct Prefix46* p46 = getGeneratedRoutes(rp, alloc);
679 return getSomething(rp, alloc, p46->prefix6, p46->prefix4);
680 }
681
Er_DEFUN(void RouteGen_commit (struct RouteGen * rg,const char * tunName,struct Allocator * tempAlloc))682 Er_DEFUN(void RouteGen_commit(struct RouteGen* rg,
683 const char* tunName,
684 struct Allocator* tempAlloc))
685 {
686 struct RouteGen_pvt* rp = Identity_check((struct RouteGen_pvt*) rg);
687 struct Prefix46* p46 = getGeneratedRoutes(rp, tempAlloc);
688 struct Sockaddr** prefixSet =
689 Allocator_calloc(tempAlloc, sizeof(char*), p46->prefix4->length + p46->prefix6->length);
690 int prefixNum = 0;
691 for (int i = 0; i < p46->prefix4->length; i++) {
692 struct Prefix4* pfx4 = ArrayList_OfPrefix4_get(p46->prefix4, i);
693 prefixSet[prefixNum++] = sockaddrForPrefix4(tempAlloc, pfx4);
694 }
695 for (int i = 0; i < p46->prefix6->length; i++) {
696 struct Prefix6* pfx6 = ArrayList_OfPrefix6_get(p46->prefix6, i);
697 prefixSet[prefixNum++] = sockaddrForPrefix6(tempAlloc, pfx6);
698 }
699 Assert_true(prefixNum == p46->prefix4->length + p46->prefix6->length);
700 Er(NetDev_setRoutes(tunName, prefixSet, prefixNum, rp->log, tempAlloc));
701 rp->pub.hasUncommittedChanges = false;
702 Er_ret();
703 }
704
setupDefaultLocalPrefixes(struct RouteGen_pvt * rp)705 static void setupDefaultLocalPrefixes(struct RouteGen_pvt* rp)
706 {
707 struct Sockaddr_storage ss;
708 #define ADD_PREFIX(str) \
709 Assert_true(!Sockaddr_parse(str, &ss)); \
710 RouteGen_addLocalPrefix(&rp->pub, &ss.addr)
711
712 ADD_PREFIX("fe80::/10");
713 ADD_PREFIX("fd00::/8");
714
715 ADD_PREFIX("10.0.0.0/8");
716 ADD_PREFIX("172.16.0.0/12");
717 ADD_PREFIX("192.168.0.0/16");
718 ADD_PREFIX("127.0.0.0/8");
719
720 #undef ADD_PREFIX
721 }
722
RouteGen_new(struct Allocator * allocator,struct Log * log)723 struct RouteGen* RouteGen_new(struct Allocator* allocator, struct Log* log)
724 {
725 struct Allocator* alloc = Allocator_child(allocator);
726 struct RouteGen_pvt* rp = Allocator_calloc(alloc, sizeof(struct RouteGen_pvt), 1);
727 rp->prefixes6 = ArrayList_OfPrefix6_new(alloc);
728 rp->localPrefixes6 = ArrayList_OfPrefix6_new(alloc);
729 rp->exceptions6 = ArrayList_OfPrefix6_new(alloc);
730 rp->prefixes4 = ArrayList_OfPrefix4_new(alloc);
731 rp->localPrefixes4 = ArrayList_OfPrefix4_new(alloc);
732 rp->exceptions4 = ArrayList_OfPrefix4_new(alloc);
733 rp->log = log;
734 rp->alloc = alloc;
735 Identity_set(rp);
736 setupDefaultLocalPrefixes(rp);
737 return &rp->pub;
738 }
739