-
Notifications
You must be signed in to change notification settings - Fork 82
/
iproutetable.hh
258 lines (194 loc) · 9.44 KB
/
iproutetable.hh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
// -*- c-basic-offset: 4 -*-
#ifndef CLICK_IPROUTETABLE_HH
#define CLICK_IPROUTETABLE_HH
#include <click/glue.hh>
#include <click/batchelement.hh>
CLICK_DECLS
/*
=c
IPRouteTable
=s iproute
IP routing table superclass
=d
IPRouteTable defines an interface useful for implementing IPv4 route lookup
elements. It parses configuration strings -- see LinearIPLookup for an example
-- and calls virtual functions to add the resulting routes. A default C<push>
function uses those virtual functions to look up routes and output packets
accordingly. There are also some functions useful for implementing handlers.
=head1 PERFORMANCE
Click provides several elements that implement all or part of the IPRouteTable
interface. Marko Zec has compared their performance, in terms of lookup speed
and memory size, for full BGP feeds; here are the results.
Methodology: 2.8GHz Pentium P4 CPU, 521K L2 cache, FreeBSD 4.10, userspace
Click. RangeIPLookup has two lookup tables, the larger of which is used only
at update time. The "warm cache" numbers perform the same lookup several
times in a loop to populate the cache; only the last lookup's performance is
reported.
ICSI BGP dump, 150700 routes, 2 next-hops
Element | cycles | lookups | setup | lookup
| /lookup | /sec | time | tbl. size
-----------------+---------+---------+-------+----------------
RadixIPLookup | 1025 | 2.73M | 0.59s | 5.8 MB
DirectIPLookup | 432 | 6.48M | 0.74s | 33 MB
RangeIPLookup | 279 | 10.0 M | 0.83s | 0.21MB (+33MB)
" (warm cache) | 44 | 63.6 M | " | " "
routeviews.org dump, 167000 routes, 52 nexthops
Element | cycles | lookups | setup | lookup
| /lookup | /sec | time | tbl. size
-----------------+---------+---------+-------+----------------
RadixIPLookup | 1095 | 2.55M | 0.67s | 6.6 MB
DirectIPLookup | 434 | 6.45M | 0.77s | 33 MB
RangeIPLookup | 508 | 5.51M | 0.88s | 0.51MB (+33MB)
" (warm cache) | 61 | 45.9 M | " | " "
The RadixIPLookup, DirectIPLookup, and RangeIPLookup elements are well suited
for implementing large tables. We also provide the LinearIPLookup,
StaticIPLookup, and SortedIPLookup elements; they are simple, but their O(N)
lookup speed is orders of magnitude slower. RadixIPLookup or DirectIPLookup
should be preferred for almost all purposes.
1500-entry fraction of the ICSI BGP dump
Method | cycles | lookups | setup | lookup
| /lookup | /sec | time | tbl. size
---------------+---------+---------+-------+----------
LinearIPLookup | 12000 | 233K | 10s | 29 KB
StaticIPLookup | 12000 | 233K | 10s | 29 KB
SortedIPLookup | 12500 | 224K | 38s | 29 KB
A Click script containing the 167000-route dump is available at
https://github.com/kohler/click/wiki/files/routetabletest-167k.click.gz
=head1 INTERFACE
These four IPRouteTable virtual functions should generally be overridden by
particular routing table elements.
=over 4
=item C<int B<add_route>(const IPRoute& r, bool set, IPRoute* old_route, ErrorHandler *errh)>
Add a route sending packets with destination addresses matching
C<r.addr/r.mask> to gateway C<r.gw>, via output port C<r.port>. If a route
for this exact prefix already exists, then the behavior depends on C<set>. If
C<set> is true, then any existing route is silently overwritten (after
possibly being stored in C<*old_route>); if C<set> is false, the function
should return C<-EEXIST>. Report errors to C<errh>. Should return 0 on
success and negative on failure. The default implementation reports an error
"cannot add routes to this routing table".
=item C<int B<remove_route>(const IPRoute& r, IPRoute* old_route, ErrorHandler *errh)>
Removes the route sending packets with destination addresses matching
C<r.addr/r.mask> to gateway C<r.gw>, via the element's output port C<r.port>.
All four fields must match, unless C<r.port> is less than 0, in which case
only C<r.addr/r.mask> must match. If no route for that prefix exists, the
function should return C<-ENOENT>; otherwise, the old route should be stored
in C<*old_route> (assuming it's not null). Any errors are reported to
C<errh>. Should return 0 on success and negative on failure. The default
implementation reports an error "cannot delete routes from this routing
table".
=item C<int B<lookup_route>(IPAddress dst, IPAddress &gw_return) const>
Looks up the route associated with address C<dst>. Should set C<gw_return> to
the resulting gateway and return the relevant output port (or negative if
there is no route). The default implementation returns -1.
=item C<String B<dump_routes>()>
Returns a textual description of the current routing table. The default
implementation returns an empty string.
=back
The following functions, overridden by IPRouteTable, are available for use by
subclasses.
=over 4
=item C<int B<configure>(VectorE<lt>StringE<gt> &conf, ErrorHandler *)>
The default implementation of B<configure> parses C<conf> as a list of routes,
where each route is the space-separated list `C<address/mask [gateway]
output>'. The routes are successively added to the element with B<add_route>.
=item C<void B<push>(int port, Packet *p)>
The default implementation of B<push> uses B<lookup_route> to perform IP
routing lookup. Normally, subclasses implement their own B<push> methods,
avoiding virtual function call overhead.
=item C<static int B<add_route_handler>(const String &, Element *, void *, ErrorHandler *)>
This write handler callback parses its input as an add-route request
and calls B<add_route> with the results. Normally hooked up to the `C<add>'
handler.
=item C<static int B<remove_route_handler>(const String &, Element *, void *, ErrorHandler *)>
This write handler callback parses its input as a remove-route request and
calls B<remove_route> with the results. Normally hooked up to the `C<remove>'
handler.
=item C<static int B<ctrl_handler>(const String &, Element *, void *, ErrorHandler *)>
This write handler callback function parses its input as a route control
request and calls B<add_route> or B<remove_route> as directed. Normally hooked
up to the `C<ctrl>' handler.
=item C<static String B<table_handler>(Element *, void *)>
This read handler callback function returns the element's routing table via
the B<dump_routes> function. Normally hooked up to the `C<table>' handler.
=back
=a RadixIPLookup, DirectIPLookup, RangeIPLookup, StaticIPLookup,
LinearIPLookup, SortedIPLookup, LinuxIPLookup */
struct IPRoute {
IPAddress addr;
IPAddress mask;
IPAddress gw;
int32_t port;
int32_t extra;
IPRoute() : port(-1) { }
IPRoute(IPAddress a, IPAddress m, IPAddress g, int p)
: addr(a), mask(m), gw(g), port(p) { }
inline bool real() const { return port > (int32_t) -0x80000000; }
inline void kill() { addr = 0; mask = 0xFFFFFFFFU; port = -0x80000000; }
inline bool contains(IPAddress a) const;
inline bool contains(const IPRoute& r) const;
inline bool mask_as_specific(IPAddress m) const;
inline bool mask_as_specific(const IPRoute& r) const;
inline bool match(const IPRoute& r) const;
int prefix_len() const { return mask.mask_to_prefix_len(); }
StringAccum &unparse(StringAccum&, bool tabs) const;
String unparse() const;
String unparse_addr() const { return addr.unparse_with_mask(mask); }
};
class IPRouteTable : public BatchElement { public:
void* cast(const char*);
int configure(Vector<String>&, ErrorHandler*) CLICK_COLD;
void add_handlers() CLICK_COLD;
virtual int add_route(const IPRoute& route, bool allow_replace, IPRoute* replaced_route, ErrorHandler* errh);
virtual int remove_route(const IPRoute& route, IPRoute* removed_route, ErrorHandler* errh);
virtual int lookup_route(IPAddress addr, IPAddress& gw) const = 0;
virtual String dump_routes();
void push(int, Packet *p);
#if HAVE_BATCH
void push_batch (int, PacketBatch *batch);
#endif
static int add_route_handler(const String&, Element*, void*, ErrorHandler*);
static int remove_route_handler(const String&, Element*, void*, ErrorHandler*);
static int ctrl_handler(const String&, Element*, void*, ErrorHandler*);
static int lookup_handler(int operation, String&, Element*, const Handler*, ErrorHandler*);
static String table_handler(Element*, void*);
private:
enum { CMD_ADD, CMD_SET, CMD_REMOVE };
int run_command(int command, const String &, Vector<IPRoute>* old_routes, ErrorHandler*);
// The actual processing of this element is abstracted from the push operation.
// This allows both push and push_batch to exploit the same processing.
int process(int port, Packet *p);
};
inline StringAccum&
operator<<(StringAccum& sa, const IPRoute& route)
{
return route.unparse(sa, false);
}
inline bool
IPRoute::contains(IPAddress a) const
{
return a.matches_prefix(addr, mask);
}
inline bool
IPRoute::contains(const IPRoute& r) const
{
return r.addr.matches_prefix(addr, mask) && r.mask.mask_as_specific(mask);
}
inline bool
IPRoute::mask_as_specific(IPAddress m) const
{
return mask.mask_as_specific(m);
}
inline bool
IPRoute::mask_as_specific(const IPRoute& r) const
{
return mask.mask_as_specific(r.mask);
}
inline bool
IPRoute::match(const IPRoute& r) const
{
return addr == r.addr && mask == r.mask
&& (port < 0 || (gw == r.gw && port == r.port));
}
CLICK_ENDDECLS
#endif