JunOS filter list ordering issue
S.P.Zeidler
spz at serpens.de
Fri Jan 29 22:50:14 UTC 2010
Hi,
I'm getting increasingly rusty about this, but as far as I remember
there was an issue with JunOS filter lists due to eg:
route-filter 10.11.0.0/16 exact accept;
route-filter 10.11.0.0/17 exact accept;
being bad karma because JunOS would see the first line matching on the
range and then fail on the exact, and not continue to the next line that
had the match on both the range and the exact.
The way to solve this (afair) was to sort in reverse.
The attached patch does that.
Is the issue even relevant any more?
regards,
spz
--
spz at serpens.de (S.P.Zeidler)
-------------- next part --------------
Index: src/rtconfig/f_junos.cc
===================================================================
--- src/rtconfig/f_junos.cc (revision 311)
+++ src/rtconfig/f_junos.cc (working copy)
@@ -123,6 +123,7 @@
cout << " policy-statement prefix-list-" << aclID << " {\n"
<< " term prefixes {\n";
+ IPv6RadixSet::reverseSort = true;
IPv6RadixSet::SortedPrefixIterator itr(&nets.members);
ipv6_addr_t addr;
u_int leng;
@@ -189,6 +190,7 @@
cout << " from {\n";
if (compressAcls) {
+ RadixSet::reverseSort = true;
RadixSet::SortedPrefixRangeIterator itr(&nets.members);
u_int addr;
u_int leng;
@@ -213,6 +215,7 @@
cout << returnPermitOrDeny(allow_flag) << "\n";
}
} else {
+ RadixSet::reverseSort = true;
RadixSet::SortedPrefixIterator itr(&nets.members);
u_int addr;
u_int leng;
Index: src/normalform/RadixSet.hh
===================================================================
--- src/normalform/RadixSet.hh (revision 311)
+++ src/normalform/RadixSet.hh (working copy)
@@ -154,6 +154,7 @@
class RadixSet {
public:
static bool compressedPrint;
+ static bool reverseSort;
class Iterator {
private:
Index: src/normalform/IPv6RadixSet.hh
===================================================================
--- src/normalform/IPv6RadixSet.hh (revision 311)
+++ src/normalform/IPv6RadixSet.hh (working copy)
@@ -153,6 +153,7 @@
public:
static bool compressedPrint;
+ static bool reverseSort;
class Iterator {
private:
Index: src/normalform/RadixSet.cc
===================================================================
--- src/normalform/RadixSet.cc (revision 311)
+++ src/normalform/RadixSet.cc (working copy)
@@ -90,6 +90,7 @@
FixedSizeAllocator RadixTreeAllocator(sizeof(RadixTree), 1000);
bool RadixSet::compressedPrint = false;
+bool RadixSet::reverseSort = false;
inline const RadixTree* RadixTree::Iterator::first() {
dfsStack.clear();
@@ -160,14 +161,25 @@
// this is insertion sorting
// it can be as bad as O(n^2)
// but since radix tree is almost sorted, it will be around (O(n))
- for (p = l.head();
- p && (p->addr < addr || (p->addr == addr && p->leng < leng));
- p = l.next(p))
- ;
- if (p)
- l.insertBefore(p, (new PrefixLNode(addr, leng, rngs)));
- else
- l.append((new PrefixLNode(addr, leng, rngs)));
+ if (RadixSet::reverseSort) {
+ for (p = l.head();
+ p && (addr < p->addr || (p->addr == addr && leng < p->leng));
+ p = l.next(p))
+ ;
+ if (p)
+ l.insertBefore(p, (new PrefixLNode(addr, leng, rngs)));
+ else
+ l.append((new PrefixLNode(addr, leng, rngs)));
+ } else {
+ for (p = l.head();
+ p && (p->addr < addr || (p->addr == addr && p->leng < leng));
+ p = l.next(p))
+ ;
+ if (p)
+ l.insertBefore(p, (new PrefixLNode(addr, leng, rngs)));
+ else
+ l.append((new PrefixLNode(addr, leng, rngs)));
+ }
}
return next(_addr, _leng, _rngs);
@@ -251,14 +263,25 @@
// this is insertion sorting
// it can be as bad as O(n^2)
// but since radix tree is almost sorted, it will be around (O(n))
- for (p = l.head();
- p && (p->addr < addr || (p->addr == addr && p->leng < leng));
- p = l.next(p))
- ;
- if (p)
- l.insertBefore(p, (new PrefixLNode(addr, leng)));
- else
- l.append((new PrefixLNode(addr, leng)));
+ if (RadixSet::reverseSort) {
+ for (p = l.head();
+ p && (addr < p->addr || (p->addr == addr && leng < p->leng));
+ p = l.next(p))
+ ;
+ if (p)
+ l.insertBefore(p, (new PrefixLNode(addr, leng)));
+ else
+ l.append((new PrefixLNode(addr, leng)));
+ } else {
+ for (p = l.head();
+ p && (p->addr < addr || (p->addr == addr && p->leng < leng));
+ p = l.next(p))
+ ;
+ if (p)
+ l.insertBefore(p, (new PrefixLNode(addr, leng)));
+ else
+ l.append((new PrefixLNode(addr, leng)));
+ }
}
return next(_addr, _leng);
@@ -292,19 +315,35 @@
// this is insertion sorting
// it can be as bad as O(n^2)
// but since radix tree is almost sorted, it will be around (O(n))
- for (p = l.head();
- p && (p->addr < addr
- || (p->addr == addr && p->leng < leng)
- || (p->addr == addr && p->leng == leng && p->start < start)
- || (p->addr == addr && p->leng == leng && p->start == start
- && p->end < end)
- );
- p = l.next(p))
- ;
- if (p)
- l.insertBefore(p, new PrefixLNode(addr, leng, start, end));
- else
- l.append(new PrefixLNode(addr, leng, start, end));
+ if (RadixSet::reverseSort) {
+ for (p = l.head();
+ p && (addr < p->addr
+ || (p->addr == addr && leng < p->leng)
+ || (p->addr == addr && p->leng == leng && start < p->start)
+ || (p->addr == addr && p->leng == leng && p->start == start
+ && end < p->end)
+ );
+ p = l.next(p))
+ ;
+ if (p)
+ l.insertBefore(p, new PrefixLNode(addr, leng, start, end));
+ else
+ l.append(new PrefixLNode(addr, leng, start, end));
+ } else {
+ for (p = l.head();
+ p && (p->addr < addr
+ || (p->addr == addr && p->leng < leng)
+ || (p->addr == addr && p->leng == leng && p->start < start)
+ || (p->addr == addr && p->leng == leng && p->start == start
+ && p->end < end)
+ );
+ p = l.next(p))
+ ;
+ if (p)
+ l.insertBefore(p, new PrefixLNode(addr, leng, start, end));
+ else
+ l.append(new PrefixLNode(addr, leng, start, end));
+ }
}
return next(_addr, _leng, _start, _end);
Index: src/normalform/IPv6RadixSet.cc
===================================================================
--- src/normalform/IPv6RadixSet.cc (revision 311)
+++ src/normalform/IPv6RadixSet.cc (working copy)
@@ -67,6 +67,7 @@
FixedSizeAllocator IPv6RadixTreeAllocator(sizeof(IPv6RadixTree), 1000);
bool IPv6RadixSet::compressedPrint = false;
+bool IPv6RadixSet::reverseSort = false;
bool IPv6RadixSet::Iterator::first(ipv6_addr_t &addr, u_int &leng, ipv6_addr_t &rngs) {
now = itr.first();
@@ -107,14 +108,25 @@
// this is insertion sorting
// it can be as bad as O(n^2)
// but since radix tree is almost sorted, it will be around (O(n))
- for (p = l.head();
- p && (p->addr < addr || (p->addr == addr && p->leng < leng));
- p = l.next(p))
- ;
- if (p)
- l.insertBefore(p, (new PrefixLNode(addr, leng, rngs)));
- else
- l.append((new PrefixLNode(addr, leng, rngs)));
+ if (IPv6RadixSet::reverseSort) {
+ for (p = l.head();
+ p && (addr < p->addr || (p->addr == addr && leng < p->leng));
+ p = l.next(p))
+ ;
+ if (p)
+ l.insertBefore(p, (new PrefixLNode(addr, leng, rngs)));
+ else
+ l.append((new PrefixLNode(addr, leng, rngs)));
+ } else {
+ for (p = l.head();
+ p && (p->addr < addr || (p->addr == addr && p->leng < leng));
+ p = l.next(p))
+ ;
+ if (p)
+ l.insertBefore(p, (new PrefixLNode(addr, leng, rngs)));
+ else
+ l.append((new PrefixLNode(addr, leng, rngs)));
+ }
}
return next(_addr, _leng, _rngs);
@@ -202,14 +214,25 @@
// this is insertion sorting
// it can be as bad as O(n^2)
// but since radix tree is almost sorted, it will be around (O(n))
- for (p = l.head();
- p && (p->addr < addr || (p->addr == addr && p->leng < leng));
- p = l.next(p))
- ;
- if (p)
- l.insertBefore(p, (new PrefixLNode(addr, leng)));
- else
- l.append((new PrefixLNode(addr, leng)));
+ if (IPv6RadixSet::reverseSort) {
+ for (p = l.head();
+ p && (addr < p->addr || (p->addr == addr && leng < p->leng));
+ p = l.next(p))
+ ;
+ if (p)
+ l.insertBefore(p, (new PrefixLNode(addr, leng)));
+ else
+ l.append((new PrefixLNode(addr, leng)));
+ } else {
+ for (p = l.head();
+ p && (p->addr < addr || (p->addr == addr && p->leng < leng));
+ p = l.next(p))
+ ;
+ if (p)
+ l.insertBefore(p, (new PrefixLNode(addr, leng)));
+ else
+ l.append((new PrefixLNode(addr, leng)));
+ }
}
return next(_addr, _leng);
@@ -244,19 +267,35 @@
// this is insertion sorting
// it can be as bad as O(n^2)
// but since radix tree is almost sorted, it will be around (O(n))
- for (p = l.head();
- p && (p->addr < addr
- || (p->addr == addr && p->leng < leng)
- || (p->addr == addr && p->leng == leng && p->start < start)
- || (p->addr == addr && p->leng == leng && p->start == start
- && p->end < end)
- );
- p = l.next(p))
- ;
- if (p)
- l.insertBefore(p, new PrefixLNode(addr, leng, start, end));
- else
- l.append(new PrefixLNode(addr, leng, start, end));
+ if (IPv6RadixSet::reverseSort) {
+ for (p = l.head();
+ p && (addr < p->addr
+ || (p->addr == addr && leng < p->leng)
+ || (p->addr == addr && p->leng == leng && start < p->start)
+ || (p->addr == addr && p->leng == leng && p->start == start
+ && end < p->end)
+ );
+ p = l.next(p))
+ ;
+ if (p)
+ l.insertBefore(p, new PrefixLNode(addr, leng, start, end));
+ else
+ l.append(new PrefixLNode(addr, leng, start, end));
+ } else {
+ for (p = l.head();
+ p && (p->addr < addr
+ || (p->addr == addr && p->leng < leng)
+ || (p->addr == addr && p->leng == leng && p->start < start)
+ || (p->addr == addr && p->leng == leng && p->start == start
+ && p->end < end)
+ );
+ p = l.next(p))
+ ;
+ if (p)
+ l.insertBefore(p, new PrefixLNode(addr, leng, start, end));
+ else
+ l.append(new PrefixLNode(addr, leng, start, end));
+ }
}
return next(_addr, _leng, _start, _end);
More information about the irrtoolset
mailing list