1 // $Id$
2 // Copyright (c) 2001,2002 RIPE NCC
3 //
4 // All Rights Reserved
5 //
6 // Permission to use, copy, modify, and distribute this software and its
7 // documentation for any purpose and without fee is hereby granted,
8 // provided that the above copyright notice appear in all copies and that
9 // both that copyright notice and this permission notice appear in
10 // supporting documentation, and that the name of the author not be
11 // used in advertising or publicity pertaining to distribution of the
12 // software without specific, written prior permission.
13 //
14 // THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
15 // ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS; IN NO EVENT SHALL
16 // AUTHOR BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY
17 // DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
18 // AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
19 // OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 //
21 //
22 // Copyright (c) 1994 by the University of Southern California
23 // All rights reserved.
24 //
25 // Permission is hereby granted, free of charge, to any person obtaining a copy
26 // of this software and associated documentation files (the "Software"), to deal
27 // in the Software without restriction, including without limitation the rights
28 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
29 // copies of the Software, and to permit persons to whom the Software is
30 // furnished to do so, subject to the following conditions:
31 //
32 // The above copyright notice and this permission notice shall be included in
33 // all copies or substantial portions of the Software.
34 //
35 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
36 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
37 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
38 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
39 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
40 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
41 // THE SOFTWARE.
42 //
43 // Questions concerning this software should be directed to
44 // irrtoolset@cs.usc.edu.
45 //
46 // Author(s): Cengiz Alaettinoglu <cengiz@ISI.EDU>
47 // Katie Petrusha <katie@ripe.net>
48
49 #include "config.h"
50 #include <iostream>
51 #include "NE.hh"
52 #include "irrutil/debug.hh"
53 #include "irr/irr.hh"
54 #include "irr/classes.hh"
55 #include "rpsl/schema.hh"
56 #include "dataset/SetOfUInt.hh"
57 #include "dataset/prefixranges.hh"
58
59 using namespace std;
60
61 CLASS_DEBUG_MEMORY_CC(NormalExpression);
62
NormalExpression(NormalExpression & a)63 NormalExpression::NormalExpression(NormalExpression& a) {
64 singleton_flag = a.singleton_flag;
65 for (Pix i = a.terms.first(); i; a.terms.next(i))
66 terms.append(new NormalTerm(*a.terms(i)));
67 }
68
evaluate(const FilterRPAttribute * ptree,ASt peerAS,unsigned int expand)69 NormalExpression *NormalExpression::evaluate(const FilterRPAttribute *ptree,
70 ASt peerAS,
71 unsigned int expand) {
72 static const AttrRPAttr *comm_rp_attr = (AttrRPAttr *) NULL;
73 static const AttrMethod *comm_contains = (AttrMethod *) NULL;
74 static const AttrMethod *comm_fcall = (AttrMethod *) NULL;
75 static const AttrMethod *comm_equals = (AttrMethod *) NULL;
76
77 if (!comm_rp_attr)
78 comm_rp_attr = schema.searchRPAttr("community");
79 if (!comm_contains)
80 comm_contains = comm_rp_attr->searchMethod("contains");
81 if (!comm_fcall)
82 comm_fcall = comm_rp_attr->searchMethod("()");
83 if (!comm_equals)
84 comm_equals = comm_rp_attr->searchMethod("==");
85
86 NormalExpression *ne = new NormalExpression;
87
88 if (ptree->rp_attr != comm_rp_attr) {
89 cerr << "Warning: unimplemented rp-attribute "
90 << ptree->rp_attr->name << " in filter, assuming NOT ANY.\n";
91 return ne;
92 }
93 if (ptree->rp_method != comm_contains
94 && ptree->rp_method != comm_fcall
95 && ptree->rp_method != comm_equals) {
96 cerr << "Warning: unimplemented method " << ptree->rp_attr->name << "."
97 << ptree->rp_method->name << " in filter, assuming NOT ANY.\n";
98 return ne;
99 }
100
101 NormalTerm *nt = new NormalTerm;
102
103 if (ptree->rp_method == comm_equals) {
104 CommunitySet *clist = new CommunitySet;
105 ItemList *arg1 = (ItemList *) ptree->args->head();
106 for (Item *nd = arg1->head(); nd; nd = arg1->next(nd))
107 clist->addCommunity(nd);
108 nt->community.set(clist, true);
109 } else
110 for (Item *nd = ptree->args->head();
111 nd;
112 nd = ptree->args->next(nd)) {
113 FilterOfCommunity *fc = new FilterOfCommunity;
114 fc->set(new CommunitySet(nd));
115 nt->community |= *fc;
116 delete fc;
117 }
118
119 nt->make_universal(NormalTerm::COMMUNITY); // this makes it universal
120 ne->singleton_flag = NormalTerm::COMMUNITY;
121
122 *ne += nt;
123 return ne;
124 }
125
evaluate(const Filter * ptree,ASt peerAS,unsigned int expand)126 NormalExpression *NormalExpression::evaluate(const Filter *ptree,
127 ASt peerAS,
128 unsigned int expand) {
129 NormalExpression *ne, *ne2;
130 NormalTerm *nt;
131
132 if (typeid(*ptree) == typeid(FilterOR)) {
133 ne = evaluate(((FilterOR *) ptree)->f1, peerAS, expand);
134 if (ne->is_universal())
135 return ne;
136
137 ne2 = evaluate(((FilterOR *) ptree)->f2, peerAS, expand);
138 Debug(Channel(DBG_NE_OR) << "op1: " << *ne << "\n");
139 Debug(Channel(DBG_NE_OR) << "op2: " << *ne2 << "\n");
140 ne->do_or(*ne2);
141 Debug(Channel(DBG_NE_OR) << "or: " << *ne << "\n");
142 delete ne2;
143
144 return ne;
145 }
146
147 if (typeid(*ptree) == typeid(FilterAND)) {
148 ne = evaluate(((FilterAND *) ptree)->f1, peerAS, expand);
149 if (ne->isEmpty())
150 return ne;
151
152 ne2 = evaluate(((FilterAND *) ptree)->f2, peerAS, expand);
153 Debug(Channel(DBG_NE_AND) << "op1: " << *ne << "\n");
154 Debug(Channel(DBG_NE_AND) << "op2: " << *ne2 << "\n");
155 ne->do_and(*ne2);
156 Debug(Channel(DBG_NE_AND) << "and: " << *ne << "\n");
157 delete ne2;
158
159 return ne;
160 }
161
162 if (typeid(*ptree) == typeid(FilterNOT)) {
163 ne = evaluate(((FilterNOT *) ptree)->f1, peerAS, expand);
164 Debug(Channel(DBG_NE_NOT) << "op1: " << *ne << "\n");
165 ne->do_not();
166 Debug(Channel(DBG_NE_NOT) << "not: " << *ne << "\n");
167 return ne;
168 }
169
170 if (typeid(*ptree) == typeid(FilterMS)) {
171 ne = evaluate(((FilterMS *) ptree)->f1, peerAS, expand);
172 Debug(Channel(DBG_NE_NOT) << "op1: " << *ne << "\n");
173 ne->makeMoreSpecific(((FilterMS *) ptree)->code,
174 ((FilterMS *) ptree)->n,
175 ((FilterMS *) ptree)->m);
176 Debug(Channel(DBG_NE_NOT) << "ms: " << *ne << "\n");
177 return ne;
178 }
179
180 if (typeid(*ptree) == typeid(FilterASNO)) {
181 ne = new NormalExpression;
182
183 if (expand & EXPAND_AS) {
184 const MPPrefixRanges *s = irr->expandAS(((FilterASNO *) ptree)->asno);
185 if (!s || s->empty())
186 return ne;
187 FilterMPPRFXList *list = new FilterMPPRFXList(*s);
188 ne = evaluate((FilterMPPRFXList *) list, peerAS, expand);
189 } else {
190 nt = new NormalTerm;
191 nt->symbols.add(((FilterASNO *) ptree)->asno);
192 nt->make_universal(NormalTerm::SYMBOLS); // this makes it universal
193 ne->singleton_flag = NormalTerm::SYMBOLS;
194 *ne += nt;
195 }
196
197 return ne;
198 }
199
200 if (typeid(*ptree) == typeid(FilterPeerAS)) {
201 ne = new NormalExpression;
202
203 if (expand & EXPAND_AS) {
204 const MPPrefixRanges *s = irr->expandAS(peerAS);
205 if (!s || s->empty())
206 return ne;
207 FilterMPPRFXList *list = new FilterMPPRFXList(*s);
208 ne = evaluate((FilterMPPRFXList *) list, peerAS, expand);
209 } else {
210 nt = new NormalTerm;
211 nt->symbols.add(peerAS);
212 nt->make_universal(NormalTerm::SYMBOLS); // this makes it universal
213 ne->singleton_flag = NormalTerm::SYMBOLS;
214 *ne += nt;
215 }
216
217 return ne;
218 }
219
220 if (typeid(*ptree) == typeid(FilterASNAME)) {
221 ne = new NormalExpression;
222
223 SymID name = symbols.resolvePeerAS(((FilterASNAME *) ptree)->asname, peerAS);
224
225 if (expand & EXPAND_AS_MACROS) {
226 const SetOfUInt *s = irr->expandASSet(name);
227 if (!s || s->isEmpty()) {
228 return ne;
229 }
230
231 if (expand & EXPAND_AS) {
232 MPPrefixRanges *full = new MPPrefixRanges;
233
234 for (Pix p = s->first(); p; s->next(p)) {
235 const MPPrefixRanges *sr;
236 sr = irr->expandAS((*s)(p));
237 if (sr)
238 full->append_list(sr);
239 }
240
241 if (full->empty()) {
242 return ne;
243 }
244
245 FilterMPPRFXList *list = new FilterMPPRFXList(*full);
246 ne = evaluate((FilterMPPRFXList *) list, peerAS, expand);
247
248 }
249 else {
250 // set assignment makes a copy
251 nt = new NormalTerm;
252 nt->symbols = *s;
253 nt->make_universal(NormalTerm::SYMBOLS); // this makes it universal
254 ne->singleton_flag = NormalTerm::SYMBOLS;
255 *ne += nt;
256 }
257 }
258 else {
259 nt = new NormalTerm;
260 nt->symbols.add(name);
261 nt->make_universal(NormalTerm::SYMBOLS); // this makes it universal
262 ne->singleton_flag = NormalTerm::SYMBOLS;
263 *ne += nt;
264 }
265
266 return ne;
267 }
268
269 if (typeid(*ptree) == typeid(FilterRSNAME)) {
270 ne = new NormalExpression;
271
272 SymID name = symbols.resolvePeerAS(((FilterRSNAME *) ptree)->rsname,
273 peerAS);
274
275 if (expand & EXPAND_COMMUNITIES) {
276 const MPPrefixRanges *s = irr->expandRSSet(name);
277 if (!s || s->empty())
278 return ne;
279 FilterMPPRFXList *list = new FilterMPPRFXList(*s);
280 ne = evaluate((FilterMPPRFXList *) list, peerAS, expand);
281 } else {
282 nt = new NormalTerm;
283 nt->symbols.add(name);
284 nt->make_universal(NormalTerm::SYMBOLS); // this makes it universal
285 ne->singleton_flag = NormalTerm::SYMBOLS;
286 *ne += nt;
287 }
288
289 return ne;
290 }
291
292 if (typeid(*ptree) == typeid(FilterANY)) {
293 ne = new NormalExpression;
294 ne->become_universal();
295 return ne;
296 }
297
298 if (typeid(*ptree) == typeid(FilterFLTRNAME)) {
299 SymID name = symbols.resolvePeerAS(((FilterFLTRNAME *) ptree)->fltrname, peerAS);
300 const FilterSet *fset = irr->getFilterSet(name);
301 if (fset) {
302 AttrIterator<AttrFilter> itr(fset, "filter");
303 if (itr) {
304 return evaluate(itr()->filter, peerAS, expand);
305 }
306 AttrIterator<AttrFilter> itr1(fset, "mp-filter");
307 if (itr1)
308 return evaluate(itr1()->filter, peerAS, expand);
309 }
310
311 ne = new NormalExpression;
312 return ne;
313 }
314
315 if (typeid(*ptree) == typeid(FilterASPath)) {
316 ne = new NormalExpression;
317 nt = new NormalTerm;
318
319 nt->as_path.compile(((FilterASPath *) ptree)->re, peerAS);
320 nt->make_universal(NormalTerm::AS_PATH); // this makes it universal
321 ne->singleton_flag = NormalTerm::AS_PATH;
322
323 *ne += nt;
324 return ne;
325 }
326
327 if (typeid(*ptree) == typeid(FilterPRFXList)) {
328 ne = new NormalExpression;
329 nt = new NormalTerm;
330
331 nt->prfx_set |= * (FilterPRFXList *) ptree; //RadixSet created here
332 nt->make_universal(NormalTerm::PRFX); // this makes it universal
333 ne->singleton_flag = NormalTerm::PRFX;
334
335 *ne += nt;
336 return ne;
337 }
338
339 if (typeid(*ptree) == typeid(FilterRPAttribute))
340 return evaluate((FilterRPAttribute *) ptree, peerAS, expand);
341
342
343 if (typeid(*ptree) == typeid(FilterAFI)) {
344
345 ne = evaluate(((FilterAFI *) ptree)->f, peerAS, expand);
346 Debug(Channel(DBG_NE_AFI) << "op1: " << *ne << "\n");
347
348 if (ne->is_any() == NEITHER &&
349 (ne->singleton_flag == -1)) {
350 ne->restrict((FilterAFI *) ptree);
351 }
352
353 Debug(Channel(DBG_NE_AFI) << "afi: " << *ne << "\n");
354 return ne;
355
356 }
357
358 if (typeid(*ptree) == typeid(FilterMPPRFXList)) {
359
360 // mixed v4/v6 prefix lists
361 FilterPRFXList *list_v4 = ((FilterMPPRFXList *) ptree)->get_v4();
362 FilterMPPRFXList *list_v6 = ((FilterMPPRFXList *) ptree)->get_v6();
363
364 ne = new NormalExpression;
365 if (list_v4) {
366 nt = new NormalTerm;
367 nt->prfx_set |= * (FilterPRFXList *) list_v4; // radix set filled here with ipv4 prefixes
368 nt->make_universal(NormalTerm::PRFX); // make all other filter types universal
369 if (!list_v6) ne->singleton_flag = NormalTerm::PRFX;
370 *ne += nt;
371 }
372 if (list_v6) {
373 nt = new NormalTerm;
374 nt->ipv6_prfx_set |= * (FilterMPPRFXList *) list_v6; // radix set filled here with ipv6 prefixes
375 nt->make_universal(NormalTerm::IPV6_PRFX); // make all other filter types universal
376 if (!list_v4) ne->singleton_flag = NormalTerm::IPV6_PRFX;
377 *ne += nt;
378 }
379 return ne;
380 }
381
382 assert(0);
383 }
384
operator <<(ostream & stream,NormalExpression & ne)385 ostream& operator<<(ostream& stream, NormalExpression& ne) {
386 NormalTerm *term;
387 Pix i;
388
389 switch (ne.is_any()) {
390 case ANY:
391 stream << "ANY";
392 break;
393 case NOT_ANY:
394 stream << "NOT ANY";
395 break;
396 default:
397 for (i = ne.terms.first(); i; ) {
398 term = ne.terms(i);
399 stream << "(" << *term << ")";
400 ne.terms.next(i);
401 if (i)
402 stream << " OR ";
403 }
404 }
405 return stream;
406 }
407
reduce()408 void NormalExpression::reduce() {
409 NormalTerm *term, *otherterm;
410 int change = 1;
411 Pix pixi, pixj, nextpixj;
412 int j;
413
414 // worst case O(N^3) Sigh.
415 // can be improved by keeping sorted lists on set sizes
416 while (change) {
417 change = 0;
418 for (pixi = terms.first(); pixi; terms.next(pixi)) {
419 term = terms(pixi);
420 for (pixj = pixi, terms.next(pixj); pixj; pixj = nextpixj) {
421 otherterm = terms(pixj);
422 nextpixj = pixj;
423 terms.next(nextpixj);
424
425 Debug(Channel(DBG_NE_REDUCE_DETAIL) << *this << "\n");
426
427 j = term->find_diff(*otherterm); // returns -1 if more than 1 diff
428 if (j >= 0) {
429 // term and otherterm are identical
430 // except in the set indexed by j
431 if (j != NormalTerm::FILTER_COUNT) // o/w *term == *otherterm
432 (*term)[j] |= (*otherterm)[j];
433
434 delete otherterm;
435 terms.del(pixj);
436
437 change = 1;
438
439 int jj;
440 for (jj = 0; jj < NormalTerm::FILTER_COUNT; jj++)
441 if (!(*term)[jj].is_universal())
442 break;
443 if (jj == NormalTerm::FILTER_COUNT) {
444 // we became ANY
445 become_universal();
446 return;
447 }
448 }
449 }
450 Debug(Channel(DBG_NE_REDUCE) << *this << "\n");
451 }
452 }
453 }
454
do_or(NormalExpression & other)455 void NormalExpression::do_or(NormalExpression &other) {
456 NormalTerm *term, *otherterm;
457
458 if (is_any() == ANY)
459 return;
460 if (other.is_any() == NOT_ANY)
461 return;
462
463 if (other.is_any() == ANY) { // become ANY
464 become_universal();
465 return;
466 }
467
468 if (is_any() == NOT_ANY) { // become other
469 terms.join(other.terms);
470 singleton_flag = other.singleton_flag;
471 return;
472 }
473
474 assert(is_any() == NEITHER && other.is_any() == NEITHER);
475
476 if (singleton_flag >= 0 && other.singleton_flag == singleton_flag) {
477 // special case for speedup
478 term = terms(terms.first());
479 otherterm = other.terms(other.terms.first());
480 (*term)[singleton_flag] |= (*otherterm)[singleton_flag];
481 if ((*term)[singleton_flag].is_universal())
482 become_universal();
483 return;
484 }
485
486 // GENERAL CASE
487
488 singleton_flag = -1;
489
490 // add his terms to my terms
491 terms.join(other.terms);
492
493 // get rid of duplicate terms
494 reduce();
495 }
496
do_and(NormalExpression & other)497 void NormalExpression::do_and(NormalExpression &other) {
498 NormalTerm *term, *newt, *otherterm;
499 NormalExpression result;
500
501 if (is_any() == NOT_ANY)
502 return;
503 if (other.is_any() == ANY)
504 return;
505
506 if (other.is_any() == NOT_ANY) { // become NOT ANY
507 become_empty();
508 return;
509 }
510
511 if (is_any() == ANY) { // become other
512 terms.clear();
513 terms.join(other.terms);
514 singleton_flag = other.singleton_flag;
515 return;
516 }
517
518 assert(is_any() == NEITHER && other.is_any() == NEITHER);
519
520 if (singleton_flag >= 0 && other.singleton_flag == singleton_flag) {
521 // special case for speedup
522 term = terms(terms.first());
523 otherterm = other.terms(other.terms.first());
524 (*term)[singleton_flag] &= (*otherterm)[singleton_flag];
525 if ((*term)[singleton_flag].isEmpty())
526 become_empty();
527 return;
528 }
529
530 singleton_flag = -1;
531
532 if (terms.length() == 1 && other.terms.length() == 1) {
533 // special case for speedup
534 term = terms(terms.first());
535 otherterm = other.terms(other.terms.first());
536 for (int i = 0; i < NormalTerm::FILTER_COUNT; i++) {
537 (*term)[i] &= (*otherterm)[i];
538 if ((*term)[i].isEmpty()) {
539 become_empty();
540 break;
541 }
542 }
543 return;
544 }
545
546 // GENERAL CASE
547
548 // do a cartesian product
549 NormalTerm *tempt = new NormalTerm; //use tempt to take the hit
550 for (Pix pixi = terms.first(); pixi; terms.next(pixi)) {
551 term = terms(pixi);
552 for (Pix pixj = other.terms.first(); pixj; other.terms.next(pixj)) {
553 otherterm = other.terms(pixj);
554 newt = new NormalTerm;
555
556 for (int i=0; i < NormalTerm::FILTER_COUNT; i++) {
557 (*newt)[i] = (*term)[i];
558 (*tempt)[i] = (*otherterm)[i]; //copy into tempt
559 (*newt)[i] &= (*tempt)[i]; //blast tempt, not otherterm!
560 if ((*newt)[i].isEmpty()) {
561 delete newt;
562 goto skip_otherterm;
563 }
564 }
565
566 result.terms.append(newt);
567
568 skip_otherterm: ;
569 }
570 }
571 delete tempt;
572
573 terms.clear();
574 terms.join(result.terms);
575 if (!terms.empty())
576 reduce(); // get rid of duplicate terms
577 }
578
579 void NormalExpression::restrict(FilterAFI *af) {
580 /* this wasn't thought out so well, needs serious rework */
581
582 NormalTerm *term = new NormalTerm;
583 NormalExpression *ne = new NormalExpression (*this);
584 become_empty();
585 this->singleton_flag = ne->singleton_flag;
586
587 for (term = ne->first(); term ; term = ne->next()) {
588 if (term->prfx_set.universal() && term->ipv6_prfx_set.universal()) {
589 /* neither a IPv4 or an IPv6 prefix set, e.g. an AS path */
590 *this += term;
591 } else if (term->prfx_set.universal()) { // v6
592 term->ipv6_prfx_set.restrict(af->afi_list);
593 if (! term->ipv6_prfx_set.isEmpty()) {
594 *this += term;
595 }
596 } else if (term->ipv6_prfx_set.universal()) {
597 term->prfx_set.restrict(af->afi_list);
598 if (! term->prfx_set.isEmpty()) {
599 *this += term;
600 }
601 }
602 }
603 }
604
do_not()605 void NormalExpression::do_not() {
606 // the value of singleton_flag is not affected by do_not
607 NormalTerm *term, *newt;
608 NormalExpression result;
609 NormalExpression tmpexp;
610
611 if (is_any() == NOT_ANY) { // become ANY
612 become_universal();
613 return;
614 }
615 if (is_any() == ANY) { // become NOT_ANY
616 become_empty();
617 return;
618 }
619
620 if (singleton_flag >= 0) { // special case for speedup
621 ~(*terms(terms.first()))[singleton_flag];
622 return;
623 }
624
625
626 // GENERAL CASE
627 result.become_universal();
628
629 for (Pix pixi = terms.first(); pixi; terms.next(pixi)) {
630 term = terms(pixi);
631 for (int i = 0; i < NormalTerm::FILTER_COUNT; i++) {
632 if (!(*term)[i].is_universal()) {
633 newt = new NormalTerm;
634 (*newt)[i] = (*term)[i];
635 ~(*newt)[i];
636
637 newt->make_universal(i);
638
639 tmpexp.terms.append(newt);
640 }
641 }
642
643 Debug(Channel(DBG_NE_NOT) << tmpexp << "\n");
644 result.do_and(tmpexp);
645 tmpexp.terms.clear(); // this also free's elements' memory
646 }
647
648 terms.clear();
649 terms.join(result.terms);
650 }
651
652