|
11 | 11 | // For more information, see Yoichi Hariguchi's paper: |
12 | 12 | // https://cseweb.ucsd.edu//~varghese/TEACH/cs228/artlookup.pdf |
13 | 13 | package art |
| 14 | + |
| 15 | +import ( |
| 16 | + "bytes" |
| 17 | + "fmt" |
| 18 | + "io" |
| 19 | + "net/netip" |
| 20 | + "strings" |
| 21 | +) |
| 22 | + |
| 23 | +// Table is an IPv4 and IPv6 routing table. |
| 24 | +type Table[T any] struct { |
| 25 | + v4 strideTable[T] |
| 26 | + v6 strideTable[T] |
| 27 | +} |
| 28 | + |
| 29 | +// Get does a route lookup for addr and returns the associated value, or nil if |
| 30 | +// no route matched. |
| 31 | +func (t *Table[T]) Get(addr netip.Addr) *T { |
| 32 | + st := &t.v4 |
| 33 | + if addr.Is6() { |
| 34 | + st = &t.v6 |
| 35 | + } |
| 36 | + |
| 37 | + var ret *T |
| 38 | + for _, stride := range addr.AsSlice() { |
| 39 | + rt, child := st.getValAndChild(stride) |
| 40 | + if rt != nil { |
| 41 | + // Found a more specific route than whatever we found previously, |
| 42 | + // keep a note. |
| 43 | + ret = rt |
| 44 | + } |
| 45 | + if child == nil { |
| 46 | + // No sub-routes further down, whatever we have recorded in ret is |
| 47 | + // the result. |
| 48 | + return ret |
| 49 | + } |
| 50 | + st = child |
| 51 | + } |
| 52 | + |
| 53 | + // Unreachable because Insert/Delete won't allow the leaf strideTables to |
| 54 | + // have children, so we must return via the nil check in the loop. |
| 55 | + panic("unreachable") |
| 56 | +} |
| 57 | + |
| 58 | +// Insert adds pfx to the table, with value val. |
| 59 | +// If pfx is already present in the table, its value is set to val. |
| 60 | +func (t *Table[T]) Insert(pfx netip.Prefix, val *T) { |
| 61 | + if val == nil { |
| 62 | + panic("Table.Insert called with nil value") |
| 63 | + } |
| 64 | + st := &t.v4 |
| 65 | + if pfx.Addr().Is6() { |
| 66 | + st = &t.v6 |
| 67 | + } |
| 68 | + bs := pfx.Addr().AsSlice() |
| 69 | + i := 0 |
| 70 | + numBits := pfx.Bits() |
| 71 | + |
| 72 | + // The strideTable we want to insert into is potentially at the end of a |
| 73 | + // chain of parent tables, each one encoding successive 8 bits of the |
| 74 | + // prefix. Navigate downwards, allocating child tables as needed, until we |
| 75 | + // find the one this prefix belongs in. |
| 76 | + for numBits > 8 { |
| 77 | + st = st.getOrCreateChild(bs[i]) |
| 78 | + i++ |
| 79 | + numBits -= 8 |
| 80 | + } |
| 81 | + // Finally, insert the remaining 0-8 bits of the prefix into the child |
| 82 | + // table. |
| 83 | + st.insert(bs[i], numBits, val) |
| 84 | +} |
| 85 | + |
| 86 | +// Delete removes pfx from the table, if it is present. |
| 87 | +func (t *Table[T]) Delete(pfx netip.Prefix) { |
| 88 | + st := &t.v4 |
| 89 | + if pfx.Addr().Is6() { |
| 90 | + st = &t.v6 |
| 91 | + } |
| 92 | + bs := pfx.Addr().AsSlice() |
| 93 | + i := 0 |
| 94 | + numBits := pfx.Bits() |
| 95 | + |
| 96 | + // Deletion may drive the refcount of some strideTables down to zero. We |
| 97 | + // need to clean up these dangling tables, so we have to keep track of which |
| 98 | + // tables we touch on the way down, and which strideEntry index each child |
| 99 | + // is registered in. |
| 100 | + strideTables := [16]*strideTable[T]{st} |
| 101 | + var strideIndexes [16]int |
| 102 | + |
| 103 | + // Similar to Insert, navigate down the tree of strideTables, looking for |
| 104 | + // the one that houses the last 0-8 bits of the prefix to delete. |
| 105 | + // |
| 106 | + // The only difference is that here, we don't create missing child tables. |
| 107 | + // If a child necessary to pfx is missing, then the pfx cannot exist in the |
| 108 | + // Table, and we can exit early. |
| 109 | + for numBits > 8 { |
| 110 | + child, idx := st.getChild(bs[i]) |
| 111 | + if child == nil { |
| 112 | + // Prefix can't exist in the table, one of the necessary |
| 113 | + // strideTables doesn't exit. |
| 114 | + return |
| 115 | + } |
| 116 | + // Note that the strideIndex and strideTables entries are off-by-one. |
| 117 | + // The child table pointer is recorded at i+1, but it is referenced by a |
| 118 | + // particular index in the parent table, at index i. |
| 119 | + strideIndexes[i] = idx |
| 120 | + i++ |
| 121 | + strideTables[i] = child |
| 122 | + numBits -= 8 |
| 123 | + st = child |
| 124 | + } |
| 125 | + if st.delete(bs[i], numBits) == nil { |
| 126 | + // Prefix didn't exist in the expected strideTable, refcount hasn't |
| 127 | + // changed, no need to run through cleanup. |
| 128 | + return |
| 129 | + } |
| 130 | + |
| 131 | + // st.delete reduced st's refcount by one, so we may be hanging onto a chain |
| 132 | + // of redundant strideTables. Walk back up the path we recorded in the |
| 133 | + // descent loop, deleting tables until we encounter one that still has other |
| 134 | + // refs (or we hit the root strideTable, which is never deleted). |
| 135 | + for i > 0 && strideTables[i].refs == 0 { |
| 136 | + strideTables[i-1].deleteChild(strideIndexes[i-1]) |
| 137 | + i-- |
| 138 | + } |
| 139 | +} |
| 140 | + |
| 141 | +// debugSummary prints the tree of allocated strideTables in t, with each |
| 142 | +// strideTable's refcount. |
| 143 | +func (t *Table[T]) debugSummary() string { |
| 144 | + var ret bytes.Buffer |
| 145 | + fmt.Fprintf(&ret, "v4: ") |
| 146 | + strideSummary(&ret, &t.v4, 0) |
| 147 | + fmt.Fprintf(&ret, "v6: ") |
| 148 | + strideSummary(&ret, &t.v6, 0) |
| 149 | + return ret.String() |
| 150 | +} |
| 151 | + |
| 152 | +func strideSummary[T any](w io.Writer, st *strideTable[T], indent int) { |
| 153 | + fmt.Fprintf(w, "%d refs\n", st.refs) |
| 154 | + indent += 2 |
| 155 | + for i := firstHostIndex; i <= lastHostIndex; i++ { |
| 156 | + if child := st.entries[i].child; child != nil { |
| 157 | + addr, len := inversePrefixIndex(i) |
| 158 | + fmt.Fprintf(w, "%s%d/%d: ", strings.Repeat(" ", indent), addr, len) |
| 159 | + strideSummary(w, child, indent) |
| 160 | + } |
| 161 | + } |
| 162 | +} |
0 commit comments