1 /*
2 * BIRD -- The Babel protocol
3 *
4 * Copyright (c) 2015--2016 Toke Hoiland-Jorgensen
5 * (c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org>
6 * (c) 2016--2017 CZ.NIC z.s.p.o.
7 *
8 * Can be freely distributed and used under the terms of the GNU GPL.
9 *
10 * This file contains the data structures used by Babel.
11 */
12
13 #ifndef _BIRD_BABEL_H_
14 #define _BIRD_BABEL_H_
15
16 #include "nest/bird.h"
17 #include "nest/cli.h"
18 #include "nest/iface.h"
19 #include "nest/route.h"
20 #include "nest/protocol.h"
21 #include "nest/locks.h"
22 #include "lib/resource.h"
23 #include "lib/lists.h"
24 #include "lib/socket.h"
25 #include "lib/string.h"
26 #include "lib/timer.h"
27
28 #define EA_BABEL_METRIC EA_CODE(PROTOCOL_BABEL, 0)
29 #define EA_BABEL_ROUTER_ID EA_CODE(PROTOCOL_BABEL, 1)
30
31 #define BABEL_MAGIC 42
32 #define BABEL_VERSION 2
33 #define BABEL_PORT 6696
34 #define BABEL_INFINITY 0xFFFF
35
36
37 #define BABEL_HELLO_INTERVAL_WIRED (4 S_) /* Default hello intervals in seconds */
38 #define BABEL_HELLO_INTERVAL_WIRELESS (4 S_)
39 #define BABEL_HELLO_LIMIT 12
40 #define BABEL_UPDATE_INTERVAL_FACTOR 4
41 #define BABEL_IHU_INTERVAL_FACTOR 3
42 #define BABEL_HOLD_TIME_FACTOR 4 /* How long we keep unreachable route relative to update interval */
43 #define BABEL_IHU_EXPIRY_FACTOR(X) ((btime)(X)*7/2) /* 3.5 */
44 #define BABEL_HELLO_EXPIRY_FACTOR(X) ((btime)(X)*3/2) /* 1.5 */
45 #define BABEL_ROUTE_EXPIRY_FACTOR(X) ((btime)(X)*7/2) /* 3.5 */
46 #define BABEL_ROUTE_REFRESH_FACTOR(X) ((btime)(X)*5/2) /* 2.5 */
47 #define BABEL_SEQNO_REQUEST_RETRY 4
48 #define BABEL_SEQNO_REQUEST_EXPIRY (2 S_)
49 #define BABEL_GARBAGE_INTERVAL (300 S_)
50 #define BABEL_RXCOST_WIRED 96
51 #define BABEL_RXCOST_WIRELESS 256
52 #define BABEL_INITIAL_HOP_COUNT 255
53 #define BABEL_MAX_SEND_INTERVAL 5 /* Unused ? */
54
55 /* Max interval that will not overflow when carried as 16-bit centiseconds */
56 #define BABEL_TIME_UNITS 10000 /* On-wire times are counted in centiseconds */
57 #define BABEL_MIN_INTERVAL (0x0001 * BABEL_TIME_UNITS)
58 #define BABEL_MAX_INTERVAL (0xFFFF * BABEL_TIME_UNITS)
59
60 #define BABEL_OVERHEAD (IP6_HEADER_LENGTH+UDP_HEADER_LENGTH)
61 #define BABEL_MIN_MTU (512 + BABEL_OVERHEAD)
62
63
64 enum babel_tlv_type {
65 BABEL_TLV_PAD1 = 0,
66 BABEL_TLV_PADN = 1,
67 BABEL_TLV_ACK_REQ = 2,
68 BABEL_TLV_ACK = 3,
69 BABEL_TLV_HELLO = 4,
70 BABEL_TLV_IHU = 5,
71 BABEL_TLV_ROUTER_ID = 6,
72 BABEL_TLV_NEXT_HOP = 7,
73 BABEL_TLV_UPDATE = 8,
74 BABEL_TLV_ROUTE_REQUEST = 9,
75 BABEL_TLV_SEQNO_REQUEST = 10,
76 /* extensions - not implemented
77 BABEL_TLV_TS_PC = 11,
78 BABEL_TLV_HMAC = 12,
79 BABEL_TLV_SS_UPDATE = 13,
80 BABEL_TLV_SS_REQUEST = 14,
81 BABEL_TLV_SS_SEQNO_REQUEST = 15,
82 */
83 BABEL_TLV_MAX
84 };
85
86 enum babel_subtlv_type {
87 BABEL_SUBTLV_PAD1 = 0,
88 BABEL_SUBTLV_PADN = 1,
89
90 /* Mandatory subtlvs */
91 BABEL_SUBTLV_SOURCE_PREFIX = 128,
92 };
93
94 enum babel_iface_type {
95 /* In practice, UNDEF and WIRED give equivalent behaviour */
96 BABEL_IFACE_TYPE_UNDEF = 0,
97 BABEL_IFACE_TYPE_WIRED = 1,
98 BABEL_IFACE_TYPE_WIRELESS = 2,
99 BABEL_IFACE_TYPE_MAX
100 };
101
102 enum babel_ae_type {
103 BABEL_AE_WILDCARD = 0,
104 BABEL_AE_IP4 = 1,
105 BABEL_AE_IP6 = 2,
106 BABEL_AE_IP6_LL = 3,
107 BABEL_AE_MAX
108 };
109
110
111 struct babel_config {
112 struct proto_config c;
113 list iface_list; /* List of iface configs (struct babel_iface_config) */
114 uint hold_time; /* Time to hold stale entries and unreachable routes */
115 u8 randomize_router_id;
116
117 struct channel_config *ip4_channel;
118 struct channel_config *ip6_channel;
119 };
120
121 struct babel_iface_config {
122 struct iface_patt i;
123
124 u16 rxcost;
125 u8 type;
126 u8 limit; /* Minimum number of Hellos to keep link up */
127 u8 check_link;
128 uint port;
129 uint hello_interval; /* Hello interval, in us */
130 uint ihu_interval; /* IHU interval, in us */
131 uint update_interval; /* Update interval, in us */
132
133 u16 rx_buffer; /* RX buffer size, 0 for MTU */
134 u16 tx_length; /* TX packet length limit (including headers), 0 for MTU */
135 int tx_tos;
136 int tx_priority;
137
138 ip_addr next_hop_ip4;
139 ip_addr next_hop_ip6;
140 };
141
142 struct babel_proto {
143 struct proto p;
144 timer *timer;
145 struct fib ip4_rtable;
146 struct fib ip6_rtable;
147
148 struct channel *ip4_channel;
149 struct channel *ip6_channel;
150
151 list interfaces; /* Interfaces we really know about (struct babel_iface) */
152 u64 router_id;
153 u16 update_seqno; /* To be increased on request */
154 u8 update_seqno_inc; /* Request for update_seqno increase */
155 u8 triggered; /* For triggering global updates */
156
157 slab *route_slab;
158 slab *source_slab;
159 slab *msg_slab;
160 slab *seqno_slab;
161
162 struct tbf log_pkt_tbf; /* TBF for packet messages */
163 };
164
165 struct babel_iface {
166 node n;
167
168 struct babel_proto *proto;
169 struct iface *iface;
170
171 struct babel_iface_config *cf;
172
173 u8 up;
174
175 pool *pool;
176 char *ifname;
177 sock *sk;
178 ip_addr addr;
179 ip_addr next_hop_ip4;
180 ip_addr next_hop_ip6;
181 int tx_length;
182 list neigh_list; /* List of neighbors seen on this iface (struct babel_neighbor) */
183 list msg_queue;
184
185 u16 hello_seqno; /* To be increased on each hello */
186
187 btime next_hello;
188 btime next_regular;
189 btime next_triggered;
190 btime want_triggered;
191
192 timer *timer;
193 event *send_event;
194 };
195
196 struct babel_neighbor {
197 node n;
198 struct babel_iface *ifa;
199
200 ip_addr addr;
201 uint uc; /* Reference counter for seqno requests */
202 u16 rxcost; /* Sent in last IHU */
203 u16 txcost; /* Received in last IHU */
204 u16 cost; /* Computed neighbor cost */
205 s8 ihu_cnt; /* IHU countdown, 0 to send it */
206 u8 hello_cnt;
207 u16 hello_map;
208 u16 next_hello_seqno;
209 uint last_hello_int;
210 /* expiry timers */
211 btime hello_expiry;
212 btime ihu_expiry;
213
214 list routes; /* Routes this neighbour has sent us (struct babel_route) */
215 };
216
217 struct babel_source {
218 node n;
219
220 u64 router_id;
221 u16 seqno;
222 u16 metric;
223 btime expires;
224 };
225
226 struct babel_route {
227 node n;
228 node neigh_route;
229 struct babel_entry *e;
230 struct babel_neighbor *neigh;
231
232 u8 feasible;
233 u16 seqno;
234 u16 metric;
235 u16 advert_metric;
236 u64 router_id;
237 ip_addr next_hop;
238 btime refresh_time;
239 btime expires;
240 };
241
242 struct babel_seqno_request {
243 node n;
244 u64 router_id;
245 u16 seqno;
246 u8 hop_count;
247 u8 count;
248 btime expires;
249 struct babel_neighbor *nbr;
250 };
251
252 struct babel_entry {
253 struct babel_route *selected;
254
255 list routes; /* Routes for this prefix (struct babel_route) */
256 list sources; /* Source entries for this prefix (struct babel_source). */
257 list requests;
258
259 u8 valid; /* Entry validity state (BABEL_ENTRY_*) */
260 u8 unreachable; /* Unreachable route is announced */
261 u16 seqno; /* Outgoing seqno */
262 u16 metric; /* Outgoing metric */
263 u64 router_id; /* Outgoing router ID */
264 btime updated; /* Last change of outgoing rte, for triggered updates */
265
266 struct fib_node n;
267 };
268
269 #define BABEL_ENTRY_DUMMY 0 /* No outgoing route */
270 #define BABEL_ENTRY_VALID 1 /* Valid outgoing route */
271 #define BABEL_ENTRY_STALE 2 /* Stale outgoing route, waiting for GC */
272
273
274 /*
275 * Internal TLV messages
276 */
277
278 struct babel_msg_ack_req {
279 u8 type;
280 u16 nonce;
281 uint interval;
282 ip_addr sender;
283 };
284
285 struct babel_msg_ack {
286 u8 type;
287 u16 nonce;
288 };
289
290 struct babel_msg_hello {
291 u8 type;
292 u16 seqno;
293 uint interval;
294 ip_addr sender;
295 };
296
297 struct babel_msg_ihu {
298 u8 type;
299 u8 ae;
300 u16 rxcost;
301 uint interval;
302 ip_addr addr;
303 ip_addr sender;
304 };
305
306 struct babel_msg_update {
307 u8 type;
308 u8 wildcard;
309 uint interval;
310 u16 seqno;
311 u16 metric;
312 u64 router_id;
313 union {
314 net_addr net;
315 net_addr_ip6_sadr net_sadr;
316 };
317 ip_addr next_hop;
318 ip_addr sender;
319 };
320
321 struct babel_msg_route_request {
322 u8 type;
323 u8 full;
324 union {
325 net_addr net;
326 net_addr_ip6_sadr net_sadr;
327 };
328 };
329
330 struct babel_msg_seqno_request {
331 u8 type;
332 u8 hop_count;
333 u16 seqno;
334 u64 router_id;
335 union {
336 net_addr net;
337 net_addr_ip6_sadr net_sadr;
338 };
339 ip_addr sender;
340 };
341
342 union babel_msg {
343 u8 type;
344 struct babel_msg_ack_req ack_req;
345 struct babel_msg_ack ack;
346 struct babel_msg_hello hello;
347 struct babel_msg_ihu ihu;
348 struct babel_msg_update update;
349 struct babel_msg_route_request route_request;
350 struct babel_msg_seqno_request seqno_request;
351 };
352
353 struct babel_msg_node {
354 node n;
355 union babel_msg msg;
356 };
357
babel_sadr_enabled(struct babel_proto * p)358 static inline int babel_sadr_enabled(struct babel_proto *p)
359 { return p->ip6_rtable.addr_type == NET_IP6_SADR; }
360
361 /* babel.c */
362 void babel_handle_ack_req(union babel_msg *msg, struct babel_iface *ifa);
363 void babel_handle_ack(union babel_msg *msg, struct babel_iface *ifa);
364 void babel_handle_hello(union babel_msg *msg, struct babel_iface *ifa);
365 void babel_handle_ihu(union babel_msg *msg, struct babel_iface *ifa);
366 void babel_handle_router_id(union babel_msg *msg, struct babel_iface *ifa);
367 void babel_handle_update(union babel_msg *msg, struct babel_iface *ifa);
368 void babel_handle_route_request(union babel_msg *msg, struct babel_iface *ifa);
369 void babel_handle_seqno_request(union babel_msg *msg, struct babel_iface *ifa);
370
371 void babel_show_interfaces(struct proto *P, const char *iff);
372 void babel_show_neighbors(struct proto *P, const char *iff);
373 void babel_show_entries(struct proto *P);
374 void babel_show_routes(struct proto *P);
375
376 /* packets.c */
377 void babel_enqueue(union babel_msg *msg, struct babel_iface *ifa);
378 void babel_send_unicast(union babel_msg *msg, struct babel_iface *ifa, ip_addr dest);
379 int babel_open_socket(struct babel_iface *ifa);
380 void babel_send_queue(void *arg);
381
382
383 #endif
384