]>
Commit | Line | Data |
---|---|---|
23b1539b PM |
1 | /* |
2 | * Filters: utility functions | |
3 | * | |
4 | * Copyright 1998 Pavel Machek <pavel@ucw.cz> | |
5 | * | |
6 | * Can be freely distributed and used under the terms of the GNU GPL. | |
29818140 | 7 | * |
23b1539b PM |
8 | */ |
9 | ||
2337ade7 PM |
10 | /** |
11 | * DOC: Filters | |
12 | * | |
725270cb MM |
13 | * You can find sources of the filter language in |filter/| |
14 | * directory. File |filter/config.Y| contains filter grammar and basically translates | |
15 | * the source from user into a tree of &f_inst structures. These trees are | |
16 | * later interpreted using code in |filter/filter.c|. | |
fe613ecd | 17 | * |
725270cb MM |
18 | * A filter is represented by a tree of &f_inst structures, one structure per |
19 | * "instruction". Each &f_inst contains @code, @aux value which is | |
20 | * usually the data type this instruction operates on and two generic | |
21 | * arguments (@a1, @a2). Some instructions contain pointer(s) to other | |
22 | * instructions in their (@a1, @a2) fields. | |
2337ade7 | 23 | * |
725270cb MM |
24 | * Filters use a &f_val structure for their data. Each &f_val |
25 | * contains type and value (types are constants prefixed with %T_). Few | |
26 | * of the types are special; %T_RETURN can be or-ed with a type to indicate | |
27 | * that return from a function or from the whole filter should be | |
28 | * forced. Important thing about &f_val's is that they may be copied | |
29 | * with a simple |=|. That's fine for all currently defined types: strings | |
2337ade7 | 30 | * are read-only (and therefore okay), paths are copied for each |
4c5f93d7 PM |
31 | * operation (okay too). |
32 | */ | |
2337ade7 | 33 | |
9a220cab | 34 | #undef LOCAL_DEBUG |
6b9fa320 | 35 | |
23b1539b PM |
36 | #include "nest/bird.h" |
37 | #include "lib/lists.h" | |
38 | #include "lib/resource.h" | |
39 | #include "lib/socket.h" | |
38506f71 | 40 | #include "lib/string.h" |
7f77e250 | 41 | #include "lib/unaligned.h" |
0264ccf6 PT |
42 | #include "lib/net.h" |
43 | #include "lib/ip.h" | |
23b1539b PM |
44 | #include "nest/route.h" |
45 | #include "nest/protocol.h" | |
46 | #include "nest/iface.h" | |
159fa4ce | 47 | #include "nest/attrs.h" |
23b1539b PM |
48 | #include "conf/conf.h" |
49 | #include "filter/filter.h" | |
50 | ||
38506f71 PM |
51 | #define CMP_ERROR 999 |
52 | ||
fc8df41e JMM |
53 | #define FILTER_STACK_DEPTH 16384 |
54 | ||
55 | /* Filter interpreter stack. Make this thread local after going parallel. */ | |
56 | struct filter_stack { | |
57 | struct f_val val; | |
58 | }; | |
59 | ||
60 | static struct filter_stack filter_stack[FILTER_STACK_DEPTH]; | |
61 | ||
a946317f JMM |
62 | /* Internal filter state, to be allocated on stack when executing filters */ |
63 | struct filter_state { | |
64 | struct rte **rte; | |
65 | struct rta *old_rta; | |
66 | struct ea_list **eattrs; | |
67 | struct linpool *pool; | |
68 | struct buffer buf; | |
fc8df41e JMM |
69 | struct filter_stack *stack; |
70 | int stack_ptr; | |
a946317f JMM |
71 | int flags; |
72 | }; | |
73 | ||
9b0a0ba9 OZ |
74 | void (*bt_assert_hook)(int result, struct f_inst *assert); |
75 | ||
8f8671bc OZ |
76 | static struct adata undef_adata; /* adata of length 0 used for undefined */ |
77 | ||
78 | /* Special undef value for paths and clists */ | |
79 | static inline int | |
80 | undef_value(struct f_val v) | |
81 | { | |
82 | return ((v.type == T_PATH) || (v.type == T_CLIST) || | |
83 | (v.type == T_ECLIST) || (v.type == T_LCLIST)) && | |
84 | (v.val.ad == &undef_adata); | |
85 | } | |
86 | ||
9831e591 | 87 | static struct adata * |
42a0c054 | 88 | adata_empty(struct linpool *pool, int l) |
ad9074e9 | 89 | { |
42a0c054 OZ |
90 | struct adata *res = lp_alloc(pool, sizeof(struct adata) + l); |
91 | res->length = l; | |
ad9074e9 PM |
92 | return res; |
93 | } | |
94 | ||
11cb6202 | 95 | static void |
0e175f9f | 96 | pm_format(struct f_path_mask *p, buffer *buf) |
11cb6202 | 97 | { |
0e175f9f | 98 | buffer_puts(buf, "[= "); |
11cb6202 OZ |
99 | |
100 | while (p) | |
0e175f9f OZ |
101 | { |
102 | switch(p->kind) | |
11cb6202 | 103 | { |
0e175f9f OZ |
104 | case PM_ASN: |
105 | buffer_print(buf, "%u ", p->val); | |
106 | break; | |
92a72a4c | 107 | |
0e175f9f OZ |
108 | case PM_QUESTION: |
109 | buffer_puts(buf, "? "); | |
110 | break; | |
92a72a4c | 111 | |
0e175f9f OZ |
112 | case PM_ASTERISK: |
113 | buffer_puts(buf, "* "); | |
114 | break; | |
11cb6202 | 115 | |
a0fe1944 OF |
116 | case PM_ASN_RANGE: |
117 | buffer_print(buf, "%u..%u ", p->val, p->val2); | |
118 | break; | |
119 | ||
0e175f9f | 120 | case PM_ASN_EXPR: |
e8bc64e3 | 121 | ASSERT(0); |
11cb6202 OZ |
122 | } |
123 | ||
0e175f9f OZ |
124 | p = p->next; |
125 | } | |
126 | ||
127 | buffer_puts(buf, "=]"); | |
11cb6202 OZ |
128 | } |
129 | ||
5e173e9f JMM |
130 | static inline int val_is_ip4(const struct f_val v) |
131 | { return (v.type == T_IP) && ipa_is_ip4(v.val.ip); } | |
42a0c054 | 132 | |
66dbdbd9 OZ |
133 | static inline int |
134 | lcomm_cmp(lcomm v1, lcomm v2) | |
135 | { | |
136 | if (v1.asn != v2.asn) | |
137 | return (v1.asn > v2.asn) ? 1 : -1; | |
138 | if (v1.ldp1 != v2.ldp1) | |
139 | return (v1.ldp1 > v2.ldp1) ? 1 : -1; | |
140 | if (v1.ldp2 != v2.ldp2) | |
141 | return (v1.ldp2 > v2.ldp2) ? 1 : -1; | |
142 | return 0; | |
143 | } | |
144 | ||
8dcf2544 | 145 | /** |
3e82b32d | 146 | * val_compare - compare two values |
8dcf2544 PM |
147 | * @v1: first value |
148 | * @v2: second value | |
149 | * | |
28a10f84 OZ |
150 | * Compares two values and returns -1, 0, 1 on <, =, > or CMP_ERROR on |
151 | * error. Tree module relies on this giving consistent results so | |
152 | * that it can be used for building balanced trees. | |
b093c328 | 153 | */ |
38506f71 PM |
154 | int |
155 | val_compare(struct f_val v1, struct f_val v2) | |
156 | { | |
f71bded6 | 157 | if (v1.type != v2.type) { |
70c57805 OZ |
158 | if (v1.type == T_VOID) /* Hack for else */ |
159 | return -1; | |
160 | if (v2.type == T_VOID) | |
161 | return 1; | |
162 | ||
126683fe | 163 | /* IP->Quad implicit conversion */ |
5e173e9f JMM |
164 | if ((v1.type == T_QUAD) && val_is_ip4(v2)) |
165 | return uint_cmp(v1.val.i, ipa_to_u32(v2.val.ip)); | |
166 | if (val_is_ip4(v1) && (v2.type == T_QUAD)) | |
167 | return uint_cmp(ipa_to_u32(v1.val.ip), v2.val.i); | |
126683fe | 168 | |
f71bded6 | 169 | debug( "Types do not match in val_compare\n" ); |
7db7b7db | 170 | return CMP_ERROR; |
f71bded6 | 171 | } |
28a10f84 | 172 | |
38506f71 | 173 | switch (v1.type) { |
28a10f84 OZ |
174 | case T_VOID: |
175 | return 0; | |
f4536657 | 176 | case T_ENUM: |
a6c9f064 OF |
177 | case T_INT: |
178 | case T_BOOL: | |
d3dd620b | 179 | case T_PAIR: |
126683fe | 180 | case T_QUAD: |
2dec1e34 | 181 | return uint_cmp(v1.val.i, v2.val.i); |
42a0c054 | 182 | case T_EC: |
8c9986d3 | 183 | case T_RD: |
42a0c054 | 184 | return u64_cmp(v1.val.ec, v2.val.ec); |
66dbdbd9 OZ |
185 | case T_LC: |
186 | return lcomm_cmp(v1.val.lc, v2.val.lc); | |
43fc099b | 187 | case T_IP: |
5e173e9f JMM |
188 | return ipa_compare(v1.val.ip, v2.val.ip); |
189 | case T_NET: | |
190 | return net_compare(v1.val.net, v2.val.net); | |
e29fa06e OZ |
191 | case T_STRING: |
192 | return strcmp(v1.val.s, v2.val.s); | |
3076b5ae MM |
193 | default: |
194 | return CMP_ERROR; | |
38506f71 PM |
195 | } |
196 | } | |
197 | ||
28a10f84 | 198 | static int |
122deb6d | 199 | pm_same(struct f_path_mask *m1, struct f_path_mask *m2) |
dfd48621 | 200 | { |
28a10f84 OZ |
201 | while (m1 && m2) |
202 | { | |
122deb6d | 203 | if (m1->kind != m2->kind) |
28a10f84 OZ |
204 | return 0; |
205 | ||
122deb6d OZ |
206 | if (m1->kind == PM_ASN_EXPR) |
207 | { | |
208 | if (!i_same((struct f_inst *) m1->val, (struct f_inst *) m2->val)) | |
209 | return 0; | |
210 | } | |
211 | else | |
212 | { | |
213 | if ((m1->val != m2->val) || (m1->val2 != m2->val2)) | |
214 | return 0; | |
215 | } | |
216 | ||
28a10f84 OZ |
217 | m1 = m1->next; |
218 | m2 = m2->next; | |
219 | } | |
220 | ||
33d22f0e | 221 | return !m1 && !m2; |
28a10f84 OZ |
222 | } |
223 | ||
224 | /** | |
225 | * val_same - compare two values | |
226 | * @v1: first value | |
227 | * @v2: second value | |
228 | * | |
229 | * Compares two values and returns 1 if they are same and 0 if not. | |
230 | * Comparison of values of different types is valid and returns 0. | |
231 | */ | |
232 | int | |
233 | val_same(struct f_val v1, struct f_val v2) | |
dfd48621 | 234 | { |
28a10f84 OZ |
235 | int rc; |
236 | ||
237 | rc = val_compare(v1, v2); | |
238 | if (rc != CMP_ERROR) | |
239 | return !rc; | |
240 | ||
241 | if (v1.type != v2.type) | |
242 | return 0; | |
243 | ||
244 | switch (v1.type) { | |
245 | case T_PATH_MASK: | |
122deb6d | 246 | return pm_same(v1.val.path_mask, v2.val.path_mask); |
28a10f84 OZ |
247 | case T_PATH: |
248 | case T_CLIST: | |
249 | case T_ECLIST: | |
66dbdbd9 | 250 | case T_LCLIST: |
28a10f84 OZ |
251 | return adata_same(v1.val.ad, v2.val.ad); |
252 | case T_SET: | |
253 | return same_tree(v1.val.t, v2.val.t); | |
254 | case T_PREFIX_SET: | |
255 | return trie_same(v1.val.ti, v2.val.ti); | |
256 | default: | |
257 | bug("Invalid type in val_same(): %x", v1.type); | |
258 | } | |
dfd48621 | 259 | } |
b1a597e0 | 260 | |
ba5c0057 OZ |
261 | static int |
262 | clist_set_type(struct f_tree *set, struct f_val *v) | |
263 | { | |
e92a4b85 OZ |
264 | switch (set->from.type) |
265 | { | |
ba5c0057 OZ |
266 | case T_PAIR: |
267 | v->type = T_PAIR; | |
268 | return 1; | |
e92a4b85 | 269 | |
ba5c0057 | 270 | case T_QUAD: |
ba5c0057 OZ |
271 | v->type = T_QUAD; |
272 | return 1; | |
e92a4b85 OZ |
273 | |
274 | case T_IP: | |
275 | if (val_is_ip4(set->from) && val_is_ip4(set->to)) | |
276 | { | |
277 | v->type = T_QUAD; | |
278 | return 1; | |
279 | } | |
280 | /* Fall through */ | |
ba5c0057 OZ |
281 | default: |
282 | v->type = T_VOID; | |
283 | return 0; | |
284 | } | |
285 | } | |
286 | ||
42a0c054 OZ |
287 | static inline int |
288 | eclist_set_type(struct f_tree *set) | |
289 | { return set->from.type == T_EC; } | |
290 | ||
66dbdbd9 OZ |
291 | static inline int |
292 | lclist_set_type(struct f_tree *set) | |
293 | { return set->from.type == T_LC; } | |
294 | ||
ba5c0057 OZ |
295 | static int |
296 | clist_match_set(struct adata *clist, struct f_tree *set) | |
297 | { | |
298 | if (!clist) | |
299 | return 0; | |
300 | ||
301 | struct f_val v; | |
302 | if (!clist_set_type(set, &v)) | |
303 | return CMP_ERROR; | |
304 | ||
305 | u32 *l = (u32 *) clist->data; | |
306 | u32 *end = l + clist->length/4; | |
42a0c054 | 307 | |
ba5c0057 OZ |
308 | while (l < end) { |
309 | v.val.i = *l++; | |
310 | if (find_tree(set, v)) | |
311 | return 1; | |
312 | } | |
313 | return 0; | |
314 | } | |
315 | ||
42a0c054 OZ |
316 | static int |
317 | eclist_match_set(struct adata *list, struct f_tree *set) | |
318 | { | |
319 | if (!list) | |
320 | return 0; | |
321 | ||
322 | if (!eclist_set_type(set)) | |
323 | return CMP_ERROR; | |
324 | ||
325 | struct f_val v; | |
326 | u32 *l = int_set_get_data(list); | |
327 | int len = int_set_get_size(list); | |
328 | int i; | |
329 | ||
330 | v.type = T_EC; | |
331 | for (i = 0; i < len; i += 2) { | |
332 | v.val.ec = ec_get(l, i); | |
333 | if (find_tree(set, v)) | |
334 | return 1; | |
335 | } | |
336 | ||
337 | return 0; | |
338 | } | |
339 | ||
66dbdbd9 OZ |
340 | static int |
341 | lclist_match_set(struct adata *list, struct f_tree *set) | |
342 | { | |
343 | if (!list) | |
344 | return 0; | |
345 | ||
346 | if (!lclist_set_type(set)) | |
347 | return CMP_ERROR; | |
348 | ||
349 | struct f_val v; | |
350 | u32 *l = int_set_get_data(list); | |
351 | int len = int_set_get_size(list); | |
352 | int i; | |
353 | ||
354 | v.type = T_LC; | |
355 | for (i = 0; i < len; i += 3) { | |
356 | v.val.lc = lc_get(l, i); | |
357 | if (find_tree(set, v)) | |
358 | return 1; | |
359 | } | |
360 | ||
361 | return 0; | |
362 | } | |
363 | ||
ba5c0057 | 364 | static struct adata * |
0888a737 | 365 | clist_filter(struct linpool *pool, struct adata *list, struct f_val set, int pos) |
ba5c0057 | 366 | { |
0888a737 | 367 | if (!list) |
ba5c0057 OZ |
368 | return NULL; |
369 | ||
0888a737 | 370 | int tree = (set.type == T_SET); /* 1 -> set is T_SET, 0 -> set is T_CLIST */ |
ba5c0057 | 371 | struct f_val v; |
0888a737 OZ |
372 | if (tree) |
373 | clist_set_type(set.val.t, &v); | |
374 | else | |
375 | v.type = T_PAIR; | |
ba5c0057 | 376 | |
0888a737 OZ |
377 | int len = int_set_get_size(list); |
378 | u32 *l = int_set_get_data(list); | |
379 | u32 tmp[len]; | |
ba5c0057 | 380 | u32 *k = tmp; |
0888a737 | 381 | u32 *end = l + len; |
ba5c0057 OZ |
382 | |
383 | while (l < end) { | |
384 | v.val.i = *l++; | |
0888a737 OZ |
385 | /* pos && member(val, set) || !pos && !member(val, set), member() depends on tree */ |
386 | if ((tree ? !!find_tree(set.val.t, v) : int_set_contains(set.val.ad, v.val.i)) == pos) | |
ba5c0057 OZ |
387 | *k++ = v.val.i; |
388 | } | |
389 | ||
3e236955 | 390 | uint nl = (k - tmp) * sizeof(u32); |
0888a737 OZ |
391 | if (nl == list->length) |
392 | return list; | |
ba5c0057 | 393 | |
42a0c054 OZ |
394 | struct adata *res = adata_empty(pool, nl); |
395 | memcpy(res->data, tmp, nl); | |
396 | return res; | |
397 | } | |
398 | ||
399 | static struct adata * | |
0888a737 | 400 | eclist_filter(struct linpool *pool, struct adata *list, struct f_val set, int pos) |
42a0c054 OZ |
401 | { |
402 | if (!list) | |
403 | return NULL; | |
404 | ||
0888a737 | 405 | int tree = (set.type == T_SET); /* 1 -> set is T_SET, 0 -> set is T_CLIST */ |
42a0c054 OZ |
406 | struct f_val v; |
407 | ||
408 | int len = int_set_get_size(list); | |
409 | u32 *l = int_set_get_data(list); | |
410 | u32 tmp[len]; | |
411 | u32 *k = tmp; | |
412 | int i; | |
413 | ||
414 | v.type = T_EC; | |
415 | for (i = 0; i < len; i += 2) { | |
416 | v.val.ec = ec_get(l, i); | |
0888a737 OZ |
417 | /* pos && member(val, set) || !pos && !member(val, set), member() depends on tree */ |
418 | if ((tree ? !!find_tree(set.val.t, v) : ec_set_contains(set.val.ad, v.val.ec)) == pos) { | |
42a0c054 OZ |
419 | *k++ = l[i]; |
420 | *k++ = l[i+1]; | |
421 | } | |
422 | } | |
423 | ||
3e236955 | 424 | uint nl = (k - tmp) * sizeof(u32); |
42a0c054 OZ |
425 | if (nl == list->length) |
426 | return list; | |
427 | ||
428 | struct adata *res = adata_empty(pool, nl); | |
ba5c0057 OZ |
429 | memcpy(res->data, tmp, nl); |
430 | return res; | |
431 | } | |
432 | ||
66dbdbd9 OZ |
433 | static struct adata * |
434 | lclist_filter(struct linpool *pool, struct adata *list, struct f_val set, int pos) | |
435 | { | |
436 | if (!list) | |
437 | return NULL; | |
438 | ||
439 | int tree = (set.type == T_SET); /* 1 -> set is T_SET, 0 -> set is T_CLIST */ | |
440 | struct f_val v; | |
441 | ||
442 | int len = int_set_get_size(list); | |
443 | u32 *l = int_set_get_data(list); | |
444 | u32 tmp[len]; | |
445 | u32 *k = tmp; | |
446 | int i; | |
447 | ||
448 | v.type = T_LC; | |
449 | for (i = 0; i < len; i += 3) { | |
450 | v.val.lc = lc_get(l, i); | |
451 | /* pos && member(val, set) || !pos && !member(val, set), member() depends on tree */ | |
452 | if ((tree ? !!find_tree(set.val.t, v) : lc_set_contains(set.val.ad, v.val.lc)) == pos) | |
453 | k = lc_copy(k, l+i); | |
454 | } | |
455 | ||
3e236955 | 456 | uint nl = (k - tmp) * sizeof(u32); |
42a0c054 OZ |
457 | if (nl == list->length) |
458 | return list; | |
459 | ||
460 | struct adata *res = adata_empty(pool, nl); | |
ba5c0057 OZ |
461 | memcpy(res->data, tmp, nl); |
462 | return res; | |
463 | } | |
464 | ||
8dcf2544 | 465 | /** |
3e82b32d | 466 | * val_in_range - implement |~| operator |
8dcf2544 PM |
467 | * @v1: element |
468 | * @v2: set | |
469 | * | |
b655596d | 470 | * Checks if @v1 is element (|~| operator) of @v2. |
b093c328 | 471 | */ |
9831e591 | 472 | static int |
7db7b7db PM |
473 | val_in_range(struct f_val v1, struct f_val v2) |
474 | { | |
b655596d OZ |
475 | if ((v1.type == T_PATH) && (v2.type == T_PATH_MASK)) |
476 | return as_path_match(v1.val.ad, v2.val.path_mask); | |
6dc7a0cb | 477 | |
b655596d | 478 | if ((v1.type == T_INT) && (v2.type == T_PATH)) |
a15dab76 | 479 | return as_path_contains(v2.val.ad, v1.val.i, 1); |
6dc7a0cb | 480 | |
b655596d OZ |
481 | if (((v1.type == T_PAIR) || (v1.type == T_QUAD)) && (v2.type == T_CLIST)) |
482 | return int_set_contains(v2.val.ad, v1.val.i); | |
b655596d | 483 | /* IP->Quad implicit conversion */ |
5e173e9f JMM |
484 | if (val_is_ip4(v1) && (v2.type == T_CLIST)) |
485 | return int_set_contains(v2.val.ad, ipa_to_u32(v1.val.ip)); | |
b1a597e0 | 486 | |
b655596d OZ |
487 | if ((v1.type == T_EC) && (v2.type == T_ECLIST)) |
488 | return ec_set_contains(v2.val.ad, v1.val.ec); | |
ba5c0057 | 489 | |
66dbdbd9 OZ |
490 | if ((v1.type == T_LC) && (v2.type == T_LCLIST)) |
491 | return lc_set_contains(v2.val.ad, v1.val.lc); | |
492 | ||
b655596d OZ |
493 | if ((v1.type == T_STRING) && (v2.type == T_STRING)) |
494 | return patmatch(v2.val.s, v1.val.s); | |
42a0c054 | 495 | |
5e173e9f JMM |
496 | if ((v1.type == T_IP) && (v2.type == T_NET)) |
497 | return ipa_in_netX(v1.val.ip, v2.val.net); | |
7db7b7db | 498 | |
5e173e9f JMM |
499 | if ((v1.type == T_NET) && (v2.type == T_NET)) |
500 | return net_in_netX(v1.val.net, v2.val.net); | |
0d1b3c4c | 501 | |
5e173e9f JMM |
502 | if ((v1.type == T_NET) && (v2.type == T_PREFIX_SET)) |
503 | return trie_match_net(v2.val.ti, v1.val.net); | |
0d1b3c4c | 504 | |
b655596d OZ |
505 | if (v2.type != T_SET) |
506 | return CMP_ERROR; | |
0d1b3c4c | 507 | |
b655596d OZ |
508 | /* With integrated Quad<->IP implicit conversion */ |
509 | if ((v1.type == v2.val.t->from.type) || | |
e92a4b85 | 510 | ((v1.type == T_QUAD) && val_is_ip4(v2.val.t->from) && val_is_ip4(v2.val.t->to))) |
b655596d | 511 | return !!find_tree(v2.val.t, v1); |
0d1b3c4c | 512 | |
b655596d | 513 | if (v1.type == T_CLIST) |
ba5c0057 | 514 | return clist_match_set(v1.val.ad, v2.val.t); |
0d1b3c4c | 515 | |
b655596d | 516 | if (v1.type == T_ECLIST) |
42a0c054 OZ |
517 | return eclist_match_set(v1.val.ad, v2.val.t); |
518 | ||
66dbdbd9 OZ |
519 | if (v1.type == T_LCLIST) |
520 | return lclist_match_set(v1.val.ad, v2.val.t); | |
521 | ||
b655596d | 522 | if (v1.type == T_PATH) |
cc31b75a OZ |
523 | return as_path_match_set(v1.val.ad, v2.val.t); |
524 | ||
7db7b7db | 525 | return CMP_ERROR; |
38506f71 PM |
526 | } |
527 | ||
4c5f93d7 | 528 | /* |
0e175f9f | 529 | * val_format - format filter value |
b093c328 | 530 | */ |
508d9360 | 531 | void |
0e175f9f | 532 | val_format(struct f_val v, buffer *buf) |
38506f71 | 533 | { |
ecd25633 | 534 | char buf2[1024]; |
0e175f9f OZ |
535 | switch (v.type) |
536 | { | |
537 | case T_VOID: buffer_puts(buf, "(void)"); return; | |
538 | case T_BOOL: buffer_puts(buf, v.val.i ? "TRUE" : "FALSE"); return; | |
52e030e1 | 539 | case T_INT: buffer_print(buf, "%u", v.val.i); return; |
0e175f9f | 540 | case T_STRING: buffer_print(buf, "%s", v.val.s); return; |
5e173e9f JMM |
541 | case T_IP: buffer_print(buf, "%I", v.val.ip); return; |
542 | case T_NET: buffer_print(buf, "%N", v.val.net); return; | |
52e030e1 | 543 | case T_PAIR: buffer_print(buf, "(%u,%u)", v.val.i >> 16, v.val.i & 0xffff); return; |
0e175f9f OZ |
544 | case T_QUAD: buffer_print(buf, "%R", v.val.i); return; |
545 | case T_EC: ec_format(buf2, v.val.ec); buffer_print(buf, "%s", buf2); return; | |
66dbdbd9 | 546 | case T_LC: lc_format(buf2, v.val.lc); buffer_print(buf, "%s", buf2); return; |
8c9986d3 | 547 | case T_RD: rd_format(v.val.ec, buf2, 1024); buffer_print(buf, "%s", buf2); return; |
0e175f9f OZ |
548 | case T_PREFIX_SET: trie_format(v.val.ti, buf); return; |
549 | case T_SET: tree_format(v.val.t, buf); return; | |
52e030e1 | 550 | case T_ENUM: buffer_print(buf, "(enum %x)%u", v.type, v.val.i); return; |
0e175f9f OZ |
551 | case T_PATH: as_path_format(v.val.ad, buf2, 1000); buffer_print(buf, "(path %s)", buf2); return; |
552 | case T_CLIST: int_set_format(v.val.ad, 1, -1, buf2, 1000); buffer_print(buf, "(clist %s)", buf2); return; | |
553 | case T_ECLIST: ec_set_format(v.val.ad, -1, buf2, 1000); buffer_print(buf, "(eclist %s)", buf2); return; | |
66dbdbd9 | 554 | case T_LCLIST: lc_set_format(v.val.ad, -1, buf2, 1000); buffer_print(buf, "(lclist %s)", buf2); return; |
0e175f9f OZ |
555 | case T_PATH_MASK: pm_format(v.val.path_mask, buf); return; |
556 | default: buffer_print(buf, "[unknown type %x]", v.type); return; | |
38506f71 | 557 | } |
38506f71 PM |
558 | } |
559 | ||
36bbfc70 | 560 | |
a946317f | 561 | static inline void f_cache_eattrs(struct filter_state *fs) |
13c0be19 | 562 | { |
a946317f | 563 | fs->eattrs = &((*fs->rte)->attrs->eattrs); |
13c0be19 JMM |
564 | } |
565 | ||
a946317f | 566 | static inline void f_rte_cow(struct filter_state *fs) |
a03ede64 | 567 | { |
a946317f | 568 | if (!((*fs->rte)->flags & REF_COW)) |
13c0be19 JMM |
569 | return; |
570 | ||
a946317f | 571 | *fs->rte = rte_cow(*fs->rte); |
a03ede64 OZ |
572 | } |
573 | ||
4c5f93d7 | 574 | /* |
b093c328 PM |
575 | * rta_cow - prepare rta for modification by filter |
576 | */ | |
9831e591 | 577 | static void |
a946317f | 578 | f_rta_cow(struct filter_state *fs) |
26c09e1d | 579 | { |
a946317f | 580 | if (!rta_is_cached((*fs->rte)->attrs)) |
8d9eef17 OZ |
581 | return; |
582 | ||
583 | /* Prepare to modify rte */ | |
a946317f | 584 | f_rte_cow(fs); |
8d9eef17 OZ |
585 | |
586 | /* Store old rta to free it later, it stores reference from rte_cow() */ | |
a946317f | 587 | fs->old_rta = (*fs->rte)->attrs; |
8d9eef17 OZ |
588 | |
589 | /* | |
590 | * Get shallow copy of rta. Fields eattrs and nexthops of rta are shared | |
a946317f | 591 | * with fs->old_rta (they will be copied when the cached rta will be obtained |
8d9eef17 OZ |
592 | * at the end of f_run()), also the lock of hostentry is inherited (we |
593 | * suppose hostentry is not changed by filters). | |
594 | */ | |
a946317f | 595 | (*fs->rte)->attrs = rta_do_cow((*fs->rte)->attrs, fs->pool); |
13c0be19 JMM |
596 | |
597 | /* Re-cache the ea_list */ | |
a946317f | 598 | f_cache_eattrs(fs); |
26c09e1d PM |
599 | } |
600 | ||
4b135d09 | 601 | static char * |
a946317f | 602 | val_format_str(struct filter_state *fs, struct f_val v) { |
4b135d09 PT |
603 | buffer b; |
604 | LOG_BUFFER_INIT(b); | |
605 | val_format(v, &b); | |
a946317f | 606 | return lp_strdup(fs->pool, b.start); |
4b135d09 PT |
607 | } |
608 | ||
1123e707 | 609 | static struct tbf rl_runtime_err = TBF_DEFAULT_LOG_LIMITS; |
cb530392 | 610 | |
b093c328 PM |
611 | /** |
612 | * interpret | |
a946317f | 613 | * @fs: filter state |
2e9b2421 | 614 | * @what: filter to interpret |
b093c328 | 615 | * |
4c5f93d7 | 616 | * Interpret given tree of filter instructions. This is core function |
b093c328 | 617 | * of filter system and does all the hard work. |
771ae456 PM |
618 | * |
619 | * Each instruction has 4 fields: code (which is instruction code), | |
620 | * aux (which is extension to instruction code, typically type), | |
621 | * arg1 and arg2 - arguments. Depending on instruction, arguments | |
315f23a0 | 622 | * are either integers, or pointers to instruction trees. Common |
771ae456 PM |
623 | * instructions like +, that have two expressions as arguments use |
624 | * TWOARGS macro to get both of them evaluated. | |
b093c328 | 625 | */ |
7afa1438 | 626 | static enum filter_return |
fc8df41e | 627 | interpret(struct filter_state *fs, struct f_inst *what) |
23b1539b PM |
628 | { |
629 | struct symbol *sym; | |
fc8df41e | 630 | struct f_val *vp; |
92a72a4c | 631 | unsigned u1, u2; |
7afa1438 | 632 | enum filter_return fret; |
6a57bb31 | 633 | int i; |
7ea5b00f | 634 | u32 as; |
23b1539b | 635 | |
fc8df41e JMM |
636 | #define res fs->stack[fs->stack_ptr].val |
637 | #define v1 fs->stack[fs->stack_ptr + 1].val | |
638 | #define v2 fs->stack[fs->stack_ptr + 2].val | |
639 | #define v3 fs->stack[fs->stack_ptr + 3].val | |
640 | ||
641 | res = (struct f_val) { .type = T_VOID }; | |
7afa1438 | 642 | |
7c601e6b | 643 | for ( ; what; what = what->next) { |
7afa1438 | 644 | res = (struct f_val) { .type = T_VOID }; |
5a14df39 | 645 | switch(what->fi_code) { |
7afa1438 | 646 | |
aca82639 JMM |
647 | #define runtime(fmt, ...) do { \ |
648 | if (!(fs->flags & FF_SILENT)) \ | |
649 | log_rl(&rl_runtime_err, L_ERR "filters, line %d: " fmt, what->lineno, ##__VA_ARGS__); \ | |
7afa1438 | 650 | return F_ERROR; \ |
aca82639 JMM |
651 | } while(0) |
652 | ||
fc8df41e | 653 | #define ARG_ANY(n) INTERPRET(what->a##n.p, n) |
aca82639 | 654 | |
fc8df41e | 655 | #define ARG(n,t) ARG_ANY(n); \ |
aca82639 JMM |
656 | if (v##n.type != t) \ |
657 | runtime("Argument %d of instruction %s must be of type %02x, got %02x", \ | |
658 | n, f_instruction_name(what->fi_code), t, v##n.type); | |
659 | ||
fc8df41e JMM |
660 | #define INTERPRET(what_, n) do { \ |
661 | fs->stack_ptr += n; \ | |
662 | fret = interpret(fs, what_); \ | |
663 | fs->stack_ptr -= n; \ | |
664 | if (fret == F_RETURN) \ | |
665 | bug("This shall not happen"); \ | |
666 | if (fret > F_RETURN) \ | |
667 | return fret; \ | |
668 | } while (0) | |
aca82639 JMM |
669 | |
670 | #define ACCESS_RTE \ | |
671 | do { if (!fs->rte) runtime("No route to access"); } while (0) | |
672 | ||
673 | #define ACCESS_EATTRS \ | |
674 | do { if (!fs->eattrs) f_cache_eattrs(fs); } while (0) | |
675 | ||
25566c68 JMM |
676 | #define BITFIELD_MASK(what_) (1u << EA_BIT_GET(what_->a2.i)) |
677 | ||
f62a369f | 678 | #include "filter/f-inst.c" |
aca82639 | 679 | |
7afa1438 | 680 | #undef res |
aca82639 JMM |
681 | #undef runtime |
682 | #undef ARG_ANY | |
683 | #undef ARG | |
684 | #undef INTERPRET | |
685 | #undef ACCESS_RTE | |
686 | #undef ACCESS_EATTRS | |
7c601e6b | 687 | }} |
7afa1438 | 688 | return F_NOP; |
23b1539b PM |
689 | } |
690 | ||
0ec6b5ec JMM |
691 | |
692 | #define ARG(n) \ | |
693 | if (!i_same(f1->a##n.p, f2->a##n.p)) \ | |
9a4037d4 PM |
694 | return 0; |
695 | ||
0ec6b5ec JMM |
696 | #define ONEARG ARG(1); |
697 | #define TWOARGS ONEARG; ARG(2); | |
698 | #define THREEARGS TWOARGS; ARG(3); | |
9a4037d4 PM |
699 | |
700 | #define A2_SAME if (f1->a2.i != f2->a2.i) return 0; | |
701 | ||
4c5f93d7 | 702 | /* |
b093c328 PM |
703 | * i_same - function that does real comparing of instruction trees, you should call filter_same from outside |
704 | */ | |
9a4037d4 PM |
705 | int |
706 | i_same(struct f_inst *f1, struct f_inst *f2) | |
707 | { | |
9a4037d4 PM |
708 | if ((!!f1) != (!!f2)) |
709 | return 0; | |
d4d75628 PM |
710 | if (!f1) |
711 | return 1; | |
9a4037d4 PM |
712 | if (f1->aux != f2->aux) |
713 | return 0; | |
5a14df39 | 714 | if (f1->fi_code != f2->fi_code) |
9a4037d4 | 715 | return 0; |
d4d75628 PM |
716 | if (f1 == f2) /* It looks strange, but it is possible with call rewriting trickery */ |
717 | return 1; | |
9a4037d4 | 718 | |
5a14df39 | 719 | switch(f1->fi_code) { |
74bfd2f9 | 720 | case FI_ADD: /* fall through */ |
5a14df39 MJM |
721 | case FI_SUBTRACT: |
722 | case FI_MULTIPLY: | |
723 | case FI_DIVIDE: | |
724 | case FI_OR: | |
725 | case FI_AND: | |
726 | case FI_PAIR_CONSTRUCT: | |
727 | case FI_EC_CONSTRUCT: | |
728 | case FI_NEQ: | |
729 | case FI_EQ: | |
730 | case FI_LT: | |
731 | case FI_LTE: TWOARGS; break; | |
732 | ||
e8bc64e3 JMM |
733 | case FI_PATHMASK_CONSTRUCT: if (!pm_same(f1->a1.p, f2->a1.p)) return 0; break; |
734 | ||
5a14df39 MJM |
735 | case FI_NOT: ONEARG; break; |
736 | case FI_NOT_MATCH: | |
737 | case FI_MATCH: TWOARGS; break; | |
738 | case FI_DEFINED: ONEARG; break; | |
d1ba927b | 739 | case FI_TYPE: ONEARG; break; |
5a14df39 MJM |
740 | |
741 | case FI_LC_CONSTRUCT: | |
478f9bab | 742 | THREEARGS; |
66dbdbd9 OZ |
743 | break; |
744 | ||
5a14df39 | 745 | case FI_SET: |
0ec6b5ec | 746 | ARG(2); |
9a4037d4 PM |
747 | { |
748 | struct symbol *s1, *s2; | |
749 | s1 = f1->a1.p; | |
750 | s2 = f2->a1.p; | |
751 | if (strcmp(s1->name, s2->name)) | |
752 | return 0; | |
753 | if (s1->class != s2->class) | |
754 | return 0; | |
755 | } | |
756 | break; | |
757 | ||
5a14df39 | 758 | case FI_CONSTANT: |
b1a597e0 OZ |
759 | switch (f1->aux) { |
760 | ||
761 | case T_PREFIX_SET: | |
762 | if (!trie_same(f1->a2.p, f2->a2.p)) | |
763 | return 0; | |
9be1086d | 764 | break; |
b1a597e0 OZ |
765 | |
766 | case T_SET: | |
4bb18dd2 PM |
767 | if (!same_tree(f1->a2.p, f2->a2.p)) |
768 | return 0; | |
9be1086d | 769 | break; |
b1a597e0 | 770 | |
4bb18dd2 PM |
771 | case T_STRING: |
772 | if (strcmp(f1->a2.p, f2->a2.p)) | |
773 | return 0; | |
774 | break; | |
b1a597e0 | 775 | |
4bb18dd2 PM |
776 | default: |
777 | A2_SAME; | |
778 | } | |
779 | break; | |
507e182a | 780 | |
5a14df39 | 781 | case FI_CONSTANT_INDIRECT: |
28a10f84 | 782 | if (!val_same(* (struct f_val *) f1->a1.p, * (struct f_val *) f2->a1.p)) |
9a4037d4 PM |
783 | return 0; |
784 | break; | |
28a10f84 | 785 | |
5a14df39 | 786 | case FI_VARIABLE: |
9be1086d OF |
787 | if (strcmp((char *) f1->a2.p, (char *) f2->a2.p)) |
788 | return 0; | |
789 | break; | |
5a14df39 MJM |
790 | case FI_PRINT: case FI_LENGTH: ONEARG; break; |
791 | case FI_CONDITION: TWOARGS; break; | |
792 | case FI_NOP: case FI_EMPTY: break; | |
793 | case FI_PRINT_AND_DIE: ONEARG; A2_SAME; break; | |
794 | case FI_PREF_GET: | |
795 | case FI_RTA_GET: A2_SAME; break; | |
796 | case FI_EA_GET: A2_SAME; break; | |
797 | case FI_PREF_SET: | |
798 | case FI_RTA_SET: | |
799 | case FI_EA_SET: ONEARG; A2_SAME; break; | |
800 | ||
801 | case FI_RETURN: ONEARG; break; | |
823ad121 JMM |
802 | case FI_ROA_MAXLEN: ONEARG; break; |
803 | case FI_ROA_ASN: ONEARG; break; | |
b24b7811 | 804 | case FI_SADR_SRC: ONEARG; break; |
5a14df39 | 805 | case FI_IP: ONEARG; break; |
823ad121 | 806 | case FI_IS_V4: ONEARG; break; |
d1ba927b | 807 | case FI_ROUTE_DISTINGUISHER: ONEARG; break; |
5a14df39 | 808 | case FI_CALL: /* Call rewriting trickery to avoid exponential behaviour */ |
315f23a0 | 809 | ONEARG; |
d4d75628 | 810 | if (!i_same(f1->a2.p, f2->a2.p)) |
315f23a0 | 811 | return 0; |
d4d75628 PM |
812 | f2->a2.p = f1->a2.p; |
813 | break; | |
5a14df39 MJM |
814 | case FI_CLEAR_LOCAL_VARS: break; /* internal instruction */ |
815 | case FI_SWITCH: ONEARG; if (!same_tree(f1->a2.p, f2->a2.p)) return 0; break; | |
816 | case FI_IP_MASK: TWOARGS; break; | |
817 | case FI_PATH_PREPEND: TWOARGS; break; | |
818 | case FI_CLIST_ADD_DEL: TWOARGS; break; | |
819 | case FI_AS_PATH_FIRST: | |
820 | case FI_AS_PATH_LAST: | |
821 | case FI_AS_PATH_LAST_NAG: ONEARG; break; | |
822 | case FI_ROA_CHECK: | |
af582c48 | 823 | TWOARGS; |
6f535924 | 824 | /* Does not really make sense - ROA check results may change anyway */ |
315f23a0 | 825 | if (strcmp(((struct f_inst_roa_check *) f1)->rtc->name, |
af582c48 OZ |
826 | ((struct f_inst_roa_check *) f2)->rtc->name)) |
827 | return 0; | |
828 | break; | |
823ad121 JMM |
829 | case FI_FORMAT: ONEARG; break; |
830 | case FI_ASSERT: ONEARG; break; | |
9a4037d4 | 831 | default: |
5a14df39 | 832 | bug( "Unknown instruction %d in same (%c)", f1->fi_code, f1->fi_code & 0xff); |
9a4037d4 PM |
833 | } |
834 | return i_same(f1->next, f2->next); | |
835 | } | |
836 | ||
ff95080f | 837 | /** |
a03ede64 OZ |
838 | * f_run - run a filter for a route |
839 | * @filter: filter to run | |
840 | * @rte: route being filtered, may be modified | |
ff95080f | 841 | * @tmp_pool: all filter allocations go from this pool |
4c5f93d7 | 842 | * @flags: flags |
a03ede64 OZ |
843 | * |
844 | * If filter needs to modify the route, there are several | |
845 | * posibilities. @rte might be read-only (with REF_COW flag), in that | |
846 | * case rw copy is obtained by rte_cow() and @rte is replaced. If | |
847 | * @rte is originally rw, it may be directly modified (and it is never | |
848 | * copied). | |
849 | * | |
850 | * The returned rte may reuse the (possibly cached, cloned) rta, or | |
851 | * (if rta was modificied) contains a modified uncached rta, which | |
852 | * uses parts allocated from @tmp_pool and parts shared from original | |
853 | * rta. There is one exception - if @rte is rw but contains a cached | |
854 | * rta and that is modified, rta in returned rte is also cached. | |
855 | * | |
856 | * Ownership of cached rtas is consistent with rte, i.e. | |
857 | * if a new rte is returned, it has its own clone of cached rta | |
858 | * (and cached rta of read-only source rte is intact), if rte is | |
859 | * modified in place, old cached rta is possibly freed. | |
ff95080f | 860 | */ |
7afa1438 | 861 | enum filter_return |
13c0be19 | 862 | f_run(struct filter *filter, struct rte **rte, struct linpool *tmp_pool, int flags) |
23b1539b | 863 | { |
36da2857 OZ |
864 | if (filter == FILTER_ACCEPT) |
865 | return F_ACCEPT; | |
866 | ||
867 | if (filter == FILTER_REJECT) | |
868 | return F_REJECT; | |
869 | ||
a03ede64 | 870 | int rte_cow = ((*rte)->flags & REF_COW); |
6b9fa320 | 871 | DBG( "Running filter `%s'...", filter->name ); |
23b1539b | 872 | |
a946317f JMM |
873 | struct filter_state fs = { |
874 | .rte = rte, | |
875 | .pool = tmp_pool, | |
876 | .flags = flags, | |
fc8df41e | 877 | .stack = filter_stack, |
a946317f | 878 | }; |
0d1b3c4c | 879 | |
a946317f | 880 | LOG_BUFFER_INIT(fs.buf); |
0e175f9f | 881 | |
fc8df41e | 882 | enum filter_return fret = interpret(&fs, filter->root); |
a03ede64 | 883 | |
a946317f | 884 | if (fs.old_rta) { |
a03ede64 | 885 | /* |
a946317f | 886 | * Cached rta was modified and fs->rte contains now an uncached one, |
a03ede64 | 887 | * sharing some part with the cached one. The cached rta should |
a946317f | 888 | * be freed (if rte was originally COW, fs->old_rta is a clone |
a03ede64 OZ |
889 | * obtained during rte_cow()). |
890 | * | |
891 | * This also implements the exception mentioned in f_run() | |
892 | * description. The reason for this is that rta reuses parts of | |
a946317f | 893 | * fs->old_rta, and these may be freed during rta_free(fs->old_rta). |
a03ede64 OZ |
894 | * This is not the problem if rte was COW, because original rte |
895 | * also holds the same rta. | |
896 | */ | |
897 | if (!rte_cow) | |
a946317f | 898 | (*fs.rte)->attrs = rta_lookup((*fs.rte)->attrs); |
a03ede64 | 899 | |
a946317f | 900 | rta_free(fs.old_rta); |
a03ede64 OZ |
901 | } |
902 | ||
0d1b3c4c | 903 | |
7afa1438 | 904 | if (fret < F_ACCEPT) { |
a946317f | 905 | if (!(fs.flags & FF_SILENT)) |
b9405791 | 906 | log_rl(&rl_runtime_err, L_ERR "Filter %s did not return accept nor reject. Make up your mind", filter->name); |
23b1539b | 907 | return F_ERROR; |
0b1cad81 | 908 | } |
52e030e1 | 909 | DBG( "done (%u)\n", res.val.i ); |
7afa1438 | 910 | return fret; |
23b1539b PM |
911 | } |
912 | ||
1321e12a OZ |
913 | /* TODO: perhaps we could integrate f_eval(), f_eval_rte() and f_run() */ |
914 | ||
7afa1438 | 915 | enum filter_return |
1321e12a OZ |
916 | f_eval_rte(struct f_inst *expr, struct rte **rte, struct linpool *tmp_pool) |
917 | { | |
1321e12a | 918 | |
a946317f JMM |
919 | struct filter_state fs = { |
920 | .rte = rte, | |
921 | .pool = tmp_pool, | |
fc8df41e | 922 | .stack = filter_stack, |
a946317f | 923 | }; |
1321e12a | 924 | |
a946317f | 925 | LOG_BUFFER_INIT(fs.buf); |
1321e12a OZ |
926 | |
927 | /* Note that in this function we assume that rte->attrs is private / uncached */ | |
fc8df41e | 928 | return interpret(&fs, expr); |
1321e12a OZ |
929 | } |
930 | ||
7afa1438 JMM |
931 | enum filter_return |
932 | f_eval(struct f_inst *expr, struct linpool *tmp_pool, struct f_val *pres) | |
1c20608e | 933 | { |
a946317f JMM |
934 | struct filter_state fs = { |
935 | .pool = tmp_pool, | |
fc8df41e | 936 | .stack = filter_stack, |
a946317f | 937 | }; |
0d1b3c4c | 938 | |
a946317f | 939 | LOG_BUFFER_INIT(fs.buf); |
0e175f9f | 940 | |
fc8df41e JMM |
941 | enum filter_return fret = interpret(&fs, expr); |
942 | *pres = filter_stack[0].val; | |
943 | return fret; | |
508d9360 | 944 | } |
0d1b3c4c | 945 | |
52e030e1 | 946 | uint |
508d9360 OZ |
947 | f_eval_int(struct f_inst *expr) |
948 | { | |
949 | /* Called independently in parse-time to eval expressions */ | |
fc8df41e JMM |
950 | struct filter_state fs = { |
951 | .pool = cfg_mem, | |
952 | .stack = filter_stack, | |
953 | }; | |
954 | ||
955 | LOG_BUFFER_INIT(fs.buf); | |
956 | ||
957 | if (interpret(&fs, expr) > F_RETURN) | |
7afa1438 | 958 | cf_error("Runtime error while evaluating expression"); |
0d1b3c4c | 959 | |
fc8df41e | 960 | if (filter_stack[0].val.type != T_INT) |
b1c9d871 | 961 | cf_error("Integer expression expected"); |
508d9360 | 962 | |
fc8df41e | 963 | return filter_stack[0].val.val.i; |
b1c9d871 | 964 | } |
1c20608e | 965 | |
ff95080f PM |
966 | /** |
967 | * filter_same - compare two filters | |
968 | * @new: first filter to be compared | |
969 | * @old: second filter to be compared, notice that this filter is | |
970 | * damaged while comparing. | |
971 | * | |
972 | * Returns 1 in case filters are same, otherwise 0. If there are | |
973 | * underlying bugs, it will rather say 0 on same filters than say | |
974 | * 1 on different. | |
975 | */ | |
30a6108c MM |
976 | int |
977 | filter_same(struct filter *new, struct filter *old) | |
978 | { | |
81ce667b MM |
979 | if (old == new) /* Handle FILTER_ACCEPT and FILTER_REJECT */ |
980 | return 1; | |
981 | if (old == FILTER_ACCEPT || old == FILTER_REJECT || | |
982 | new == FILTER_ACCEPT || new == FILTER_REJECT) | |
983 | return 0; | |
9a4037d4 | 984 | return i_same(new->root, old->root); |
30a6108c | 985 | } |