[prefix] Use garbage-collectable section names
[ipxe.git] / src / net / neighbour.c
1 /*
2 * Copyright (C) 2013 Michael Brown <mbrown@fensystems.co.uk>.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation; either version 2 of the
7 * License, or any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17 * 02110-1301, USA.
18 *
19 * You can also choose to distribute this program under the terms of
20 * the Unmodified Binary Distribution Licence (as given in the file
21 * COPYING.UBDL), provided that you have satisfied its requirements.
22 */
23
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
25
26 #include <stdint.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include <errno.h>
30 #include <ipxe/iobuf.h>
31 #include <ipxe/retry.h>
32 #include <ipxe/timer.h>
33 #include <ipxe/malloc.h>
34 #include <ipxe/neighbour.h>
35
36 /** @file
37 *
38 * Neighbour discovery
39 *
40 * This file implements the abstract functions of neighbour discovery,
41 * independent of the underlying network protocol (e.g. ARP or NDP).
42 *
43 */
44
45 /** Neighbour discovery minimum timeout */
46 #define NEIGHBOUR_MIN_TIMEOUT ( TICKS_PER_SEC / 8 )
47
48 /** Neighbour discovery maximum timeout */
49 #define NEIGHBOUR_MAX_TIMEOUT ( TICKS_PER_SEC * 3 )
50
51 /** The neighbour cache */
52 struct list_head neighbours = LIST_HEAD_INIT ( neighbours );
53
54 static void neighbour_expired ( struct retry_timer *timer, int over );
55
56 /**
57 * Free neighbour cache entry
58 *
59 * @v refcnt Reference count
60 */
61 static void neighbour_free ( struct refcnt *refcnt ) {
62 struct neighbour *neighbour =
63 container_of ( refcnt, struct neighbour, refcnt );
64
65 /* Sanity check */
66 assert ( list_empty ( &neighbour->tx_queue ) );
67
68 /* Drop reference to network device */
69 netdev_put ( neighbour->netdev );
70
71 /* Free neighbour */
72 free ( neighbour );
73 }
74
75 /**
76 * Create neighbour cache entry
77 *
78 * @v netdev Network device
79 * @v net_protocol Network-layer protocol
80 * @v net_dest Destination network-layer address
81 * @ret neighbour Neighbour cache entry, or NULL if allocation failed
82 */
83 static struct neighbour * neighbour_create ( struct net_device *netdev,
84 struct net_protocol *net_protocol,
85 const void *net_dest ) {
86 struct neighbour *neighbour;
87
88 /* Allocate and initialise entry */
89 neighbour = zalloc ( sizeof ( *neighbour ) );
90 if ( ! neighbour )
91 return NULL;
92 ref_init ( &neighbour->refcnt, neighbour_free );
93 neighbour->netdev = netdev_get ( netdev );
94 neighbour->net_protocol = net_protocol;
95 memcpy ( neighbour->net_dest, net_dest,
96 net_protocol->net_addr_len );
97 timer_init ( &neighbour->timer, neighbour_expired, &neighbour->refcnt );
98 set_timer_limits ( &neighbour->timer, NEIGHBOUR_MIN_TIMEOUT,
99 NEIGHBOUR_MAX_TIMEOUT );
100 INIT_LIST_HEAD ( &neighbour->tx_queue );
101
102 /* Transfer ownership to cache */
103 list_add ( &neighbour->list, &neighbours );
104
105 DBGC ( neighbour, "NEIGHBOUR %s %s %s created\n", netdev->name,
106 net_protocol->name, net_protocol->ntoa ( net_dest ) );
107 return neighbour;
108 }
109
110 /**
111 * Find neighbour cache entry
112 *
113 * @v netdev Network device
114 * @v net_protocol Network-layer protocol
115 * @v net_dest Destination network-layer address
116 * @ret neighbour Neighbour cache entry, or NULL if not found
117 */
118 static struct neighbour * neighbour_find ( struct net_device *netdev,
119 struct net_protocol *net_protocol,
120 const void *net_dest ) {
121 struct neighbour *neighbour;
122
123 list_for_each_entry ( neighbour, &neighbours, list ) {
124 if ( ( neighbour->netdev == netdev ) &&
125 ( neighbour->net_protocol == net_protocol ) &&
126 ( memcmp ( neighbour->net_dest, net_dest,
127 net_protocol->net_addr_len ) == 0 ) ) {
128
129 /* Move to start of cache */
130 list_del ( &neighbour->list );
131 list_add ( &neighbour->list, &neighbours );
132
133 return neighbour;
134 }
135 }
136 return NULL;
137 }
138
139 /**
140 * Start neighbour discovery
141 *
142 * @v neighbour Neighbour cache entry
143 * @v discovery Neighbour discovery protocol
144 * @v net_source Source network-layer address
145 */
146 static void neighbour_discover ( struct neighbour *neighbour,
147 struct neighbour_discovery *discovery,
148 const void *net_source ) {
149 struct net_device *netdev = neighbour->netdev;
150 struct net_protocol *net_protocol = neighbour->net_protocol;
151
152 /* Record discovery protocol and source network-layer address */
153 neighbour->discovery = discovery;
154 memcpy ( neighbour->net_source, net_source,
155 net_protocol->net_addr_len );
156
157 /* Start timer to trigger neighbour discovery */
158 start_timer_nodelay ( &neighbour->timer );
159
160 DBGC ( neighbour, "NEIGHBOUR %s %s %s discovering via %s\n",
161 netdev->name, net_protocol->name,
162 net_protocol->ntoa ( neighbour->net_dest ),
163 neighbour->discovery->name );
164 }
165
166 /**
167 * Complete neighbour discovery
168 *
169 * @v neighbour Neighbour cache entry
170 * @v ll_dest Destination link-layer address
171 */
172 static void neighbour_discovered ( struct neighbour *neighbour,
173 const void *ll_dest ) {
174 struct net_device *netdev = neighbour->netdev;
175 struct ll_protocol *ll_protocol = netdev->ll_protocol;
176 struct net_protocol *net_protocol = neighbour->net_protocol;
177 struct io_buffer *iobuf;
178 int rc;
179
180 /* Fill in link-layer address */
181 memcpy ( neighbour->ll_dest, ll_dest, ll_protocol->ll_addr_len );
182 DBGC ( neighbour, "NEIGHBOUR %s %s %s is %s %s\n", netdev->name,
183 net_protocol->name, net_protocol->ntoa ( neighbour->net_dest ),
184 ll_protocol->name, ll_protocol->ntoa ( neighbour->ll_dest ) );
185
186 /* Stop retransmission timer */
187 stop_timer ( &neighbour->timer );
188
189 /* Transmit any packets in queue. Take out a temporary
190 * reference on the entry to prevent it from going out of
191 * scope during the call to net_tx().
192 */
193 ref_get ( &neighbour->refcnt );
194 while ( ( iobuf = list_first_entry ( &neighbour->tx_queue,
195 struct io_buffer, list )) != NULL){
196 DBGC2 ( neighbour, "NEIGHBOUR %s %s %s transmitting deferred "
197 "packet\n", netdev->name, net_protocol->name,
198 net_protocol->ntoa ( neighbour->net_dest ) );
199 list_del ( &iobuf->list );
200 if ( ( rc = net_tx ( iobuf, netdev, net_protocol, ll_dest,
201 netdev->ll_addr ) ) != 0 ) {
202 DBGC ( neighbour, "NEIGHBOUR %s %s %s could not "
203 "transmit deferred packet: %s\n",
204 netdev->name, net_protocol->name,
205 net_protocol->ntoa ( neighbour->net_dest ),
206 strerror ( rc ) );
207 /* Ignore error and continue */
208 }
209 }
210 ref_put ( &neighbour->refcnt );
211 }
212
213 /**
214 * Destroy neighbour cache entry
215 *
216 * @v neighbour Neighbour cache entry
217 * @v rc Reason for destruction
218 */
219 static void neighbour_destroy ( struct neighbour *neighbour, int rc ) {
220 struct net_device *netdev = neighbour->netdev;
221 struct net_protocol *net_protocol = neighbour->net_protocol;
222 struct io_buffer *iobuf;
223
224 /* Take ownership from cache */
225 list_del ( &neighbour->list );
226
227 /* Stop timer */
228 stop_timer ( &neighbour->timer );
229
230 /* Discard any outstanding I/O buffers */
231 while ( ( iobuf = list_first_entry ( &neighbour->tx_queue,
232 struct io_buffer, list )) != NULL){
233 DBGC2 ( neighbour, "NEIGHBOUR %s %s %s discarding deferred "
234 "packet: %s\n", netdev->name, net_protocol->name,
235 net_protocol->ntoa ( neighbour->net_dest ),
236 strerror ( rc ) );
237 list_del ( &iobuf->list );
238 netdev_tx_err ( neighbour->netdev, iobuf, rc );
239 }
240
241 DBGC ( neighbour, "NEIGHBOUR %s %s %s destroyed: %s\n", netdev->name,
242 net_protocol->name, net_protocol->ntoa ( neighbour->net_dest ),
243 strerror ( rc ) );
244
245 /* Drop remaining reference */
246 ref_put ( &neighbour->refcnt );
247 }
248
249 /**
250 * Handle neighbour timer expiry
251 *
252 * @v timer Retry timer
253 * @v fail Failure indicator
254 */
255 static void neighbour_expired ( struct retry_timer *timer, int fail ) {
256 struct neighbour *neighbour =
257 container_of ( timer, struct neighbour, timer );
258 struct net_device *netdev = neighbour->netdev;
259 struct net_protocol *net_protocol = neighbour->net_protocol;
260 struct neighbour_discovery *discovery =
261 neighbour->discovery;
262 const void *net_dest = neighbour->net_dest;
263 const void *net_source = neighbour->net_source;
264 int rc;
265
266 /* If we have failed, destroy the cache entry */
267 if ( fail ) {
268 neighbour_destroy ( neighbour, -ETIMEDOUT );
269 return;
270 }
271
272 /* Restart the timer */
273 start_timer ( &neighbour->timer );
274
275 /* Transmit neighbour request */
276 if ( ( rc = discovery->tx_request ( netdev, net_protocol, net_dest,
277 net_source ) ) != 0 ) {
278 DBGC ( neighbour, "NEIGHBOUR %s %s %s could not transmit %s "
279 "request: %s\n", netdev->name, net_protocol->name,
280 net_protocol->ntoa ( neighbour->net_dest ),
281 neighbour->discovery->name, strerror ( rc ) );
282 /* Retransmit when timer expires */
283 return;
284 }
285 }
286
287 /**
288 * Transmit packet, determining link-layer address via neighbour discovery
289 *
290 * @v iobuf I/O buffer
291 * @v netdev Network device
292 * @v discovery Neighbour discovery protocol
293 * @v net_protocol Network-layer protocol
294 * @v net_dest Destination network-layer address
295 * @v net_source Source network-layer address
296 * @v ll_source Source link-layer address
297 * @ret rc Return status code
298 */
299 int neighbour_tx ( struct io_buffer *iobuf, struct net_device *netdev,
300 struct net_protocol *net_protocol, const void *net_dest,
301 struct neighbour_discovery *discovery,
302 const void *net_source, const void *ll_source ) {
303 struct neighbour *neighbour;
304
305 /* Find or create neighbour cache entry */
306 neighbour = neighbour_find ( netdev, net_protocol, net_dest );
307 if ( ! neighbour ) {
308 neighbour = neighbour_create ( netdev, net_protocol, net_dest );
309 if ( ! neighbour )
310 return -ENOMEM;
311 neighbour_discover ( neighbour, discovery, net_source );
312 }
313
314 /* If a link-layer address is available then transmit
315 * immediately, otherwise queue for later transmission.
316 */
317 if ( neighbour_has_ll_dest ( neighbour ) ) {
318 return net_tx ( iobuf, netdev, net_protocol, neighbour->ll_dest,
319 ll_source );
320 } else {
321 DBGC2 ( neighbour, "NEIGHBOUR %s %s %s deferring packet\n",
322 netdev->name, net_protocol->name,
323 net_protocol->ntoa ( net_dest ) );
324 list_add_tail ( &iobuf->list, &neighbour->tx_queue );
325 return 0;
326 }
327 }
328
329 /**
330 * Update existing neighbour cache entry
331 *
332 * @v netdev Network device
333 * @v net_protocol Network-layer protocol
334 * @v net_dest Destination network-layer address
335 * @v ll_dest Destination link-layer address
336 * @ret rc Return status code
337 */
338 int neighbour_update ( struct net_device *netdev,
339 struct net_protocol *net_protocol,
340 const void *net_dest, const void *ll_dest ) {
341 struct neighbour *neighbour;
342
343 /* Find neighbour cache entry */
344 neighbour = neighbour_find ( netdev, net_protocol, net_dest );
345 if ( ! neighbour )
346 return -ENOENT;
347
348 /* Set destination address */
349 neighbour_discovered ( neighbour, ll_dest );
350
351 return 0;
352 }
353
354 /**
355 * Define neighbour cache entry
356 *
357 * @v netdev Network device
358 * @v net_protocol Network-layer protocol
359 * @v net_dest Destination network-layer address
360 * @v ll_dest Destination link-layer address, if known
361 * @ret rc Return status code
362 */
363 int neighbour_define ( struct net_device *netdev,
364 struct net_protocol *net_protocol,
365 const void *net_dest, const void *ll_dest ) {
366 struct neighbour *neighbour;
367
368 /* Find or create neighbour cache entry */
369 neighbour = neighbour_find ( netdev, net_protocol, net_dest );
370 if ( ! neighbour ) {
371 neighbour = neighbour_create ( netdev, net_protocol, net_dest );
372 if ( ! neighbour )
373 return -ENOMEM;
374 }
375
376 /* Set destination address */
377 neighbour_discovered ( neighbour, ll_dest );
378
379 return 0;
380 }
381
382 /**
383 * Update neighbour cache on network device state change or removal
384 *
385 * @v netdev Network device
386 */
387 static void neighbour_flush ( struct net_device *netdev ) {
388 struct neighbour *neighbour;
389 struct neighbour *tmp;
390
391 /* Remove all neighbour cache entries when a network device is closed */
392 if ( ! netdev_is_open ( netdev ) ) {
393 list_for_each_entry_safe ( neighbour, tmp, &neighbours, list )
394 neighbour_destroy ( neighbour, -ENODEV );
395 }
396 }
397
398 /** Neighbour driver (for net device notifications) */
399 struct net_driver neighbour_net_driver __net_driver = {
400 .name = "Neighbour",
401 .notify = neighbour_flush,
402 .remove = neighbour_flush,
403 };
404
405 /**
406 * Discard some cached neighbour entries
407 *
408 * @ret discarded Number of cached items discarded
409 */
410 static unsigned int neighbour_discard ( void ) {
411 struct neighbour *neighbour;
412
413 /* Drop oldest cache entry, if any */
414 neighbour = list_last_entry ( &neighbours, struct neighbour, list );
415 if ( neighbour ) {
416 neighbour_destroy ( neighbour, -ENOBUFS );
417 return 1;
418 } else {
419 return 0;
420 }
421 }
422
423 /**
424 * Neighbour cache discarder
425 *
426 * Neighbour cache entries are deemed to have a high replacement cost,
427 * since flushing an active neighbour cache entry midway through a TCP
428 * transfer will cause substantial disruption.
429 */
430 struct cache_discarder neighbour_discarder __cache_discarder (CACHE_EXPENSIVE)={
431 .discard = neighbour_discard,
432 };