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