iPXE
neighbour.c
Go to the documentation of this file.
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 */
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 */
67 
68  /* Drop reference to network device */
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;
97  timer_init ( &neighbour->timer, neighbour_expired, &neighbour->refcnt );
98  set_timer_limits ( &neighbour->timer, NEIGHBOUR_MIN_TIMEOUT,
101 
102  /* Transfer ownership to cache */
104 
105  DBGC ( neighbour, "NEIGHBOUR %s %s %s created\n", netdev->name,
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 
124  if ( ( neighbour->netdev == netdev ) &&
127  net_protocol->net_addr_len ) == 0 ) ) {
128 
129  /* Move to start of cache */
130  list_del ( &neighbour->list );
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,
148  const void *net_source ) {
149  struct net_device *netdev = neighbour->netdev;
151 
152  /* Record discovery protocol and source network-layer address */
153  neighbour->discovery = discovery;
154  memcpy ( neighbour->net_source, net_source,
156 
157  /* Start timer to trigger neighbour discovery */
159 
160  DBGC ( neighbour, "NEIGHBOUR %s %s %s discovering via %s\n",
164 }
165 
166 /**
167  * Complete neighbour discovery
168  *
169  * @v neighbour Neighbour cache entry
170  * @v ll_dest Destination link-layer address
171  */
173  const void *ll_dest ) {
174  struct net_device *netdev = neighbour->netdev;
177  struct io_buffer *iobuf;
178  int rc;
179 
180  /* Fill in link-layer address */
182  DBGC ( neighbour, "NEIGHBOUR %s %s %s is %s %s\n", netdev->name,
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,
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",
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;
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,
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,
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;
260  struct neighbour_discovery *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 ) {
269  return;
270  }
271 
272  /* Restart the 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,
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 */
307  if ( ! neighbour ) {
309  if ( ! neighbour )
310  return -ENOMEM;
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",
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  */
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 */
345  if ( ! neighbour )
346  return -ENOENT;
347 
348  /* Set destination address */
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  */
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 */
370  if ( ! neighbour ) {
372  if ( ! neighbour )
373  return -ENOMEM;
374  }
375 
376  /* Set destination address */
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 ) ) {
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 */
415  if ( neighbour ) {
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)={
432 };
struct arbelprm_rc_send_wqe rc
Definition: arbel.h:14
const char * name
Protocol name.
Definition: netdevice.h:66
const char * name
Name.
Definition: neighbour.h:21
#define NEIGHBOUR_MIN_TIMEOUT
Neighbour discovery minimum timeout.
Definition: neighbour.c:46
static struct neighbour * neighbour_find(struct net_device *netdev, struct net_protocol *net_protocol, const void *net_dest)
Find neighbour cache entry.
Definition: neighbour.c:118
static void start_timer_nodelay(struct retry_timer *timer)
Start timer with no delay.
Definition: retry.h:99
uint8_t ll_addr_len
Link-layer address length.
Definition: netdevice.h:198
struct cache_discarder neighbour_discarder __cache_discarder(CACHE_EXPENSIVE)
Neighbour cache discarder.
static struct neighbour * neighbour_create(struct net_device *netdev, struct net_protocol *net_protocol, const void *net_dest)
Create neighbour cache entry.
Definition: neighbour.c:83
uint8_t net_dest[MAX_NET_ADDR_LEN]
Network-layer destination address.
Definition: neighbour.h:48
#define list_add(new, head)
Add a new entry to the head of a list.
Definition: list.h:69
void netdev_tx_err(struct net_device *netdev, struct io_buffer *iobuf, int rc)
Discard transmitted packet.
Definition: netdevice.c:369
#define ref_init(refcnt, free)
Initialise a reference counter.
Definition: refcnt.h:64
Error codes.
I/O buffers.
struct net_protocol * net_protocol
Network-layer protocol.
Definition: neighbour.h:46
Retry timers.
#define DBGC(...)
Definition: compiler.h:505
struct list_head neighbours
The neighbour cache.
Definition: neighbour.c:52
struct retry_timer timer
Retransmission timer.
Definition: neighbour.h:57
A retry timer.
Definition: retry.h:21
A neighbour discovery protocol.
Definition: neighbour.h:19
#define ENOENT
No such file or directory.
Definition: errno.h:514
iPXE timers
int neighbour_update(struct net_device *netdev, struct net_protocol *net_protocol, const void *net_dest, const void *ll_dest)
Update existing neighbour cache entry.
Definition: neighbour.c:338
#define list_last_entry(list, type, member)
Get the container of the last entry in a list.
Definition: list.h:346
A network upper-layer driver.
Definition: netdevice.h:461
A link-layer protocol.
Definition: netdevice.h:114
A doubly-linked list entry (or list head)
Definition: list.h:18
Dynamic memory allocation.
A reference counter.
Definition: refcnt.h:26
A timer.
Definition: timer.h:28
struct refcnt refcnt
Reference count.
Definition: neighbour.h:39
struct list_head list
List of neighbour cache entries.
Definition: neighbour.h:41
#define list_empty(list)
Test whether a list is empty.
Definition: list.h:136
#define list_first_entry(list, type, member)
Get the container of the first entry in a list.
Definition: list.h:333
const char * name
Protocol name.
Definition: netdevice.h:116
#define list_del(list)
Delete an entry from a list.
Definition: list.h:119
int(* tx_request)(struct net_device *netdev, struct net_protocol *net_protocol, const void *net_dest, const void *net_source)
Transmit neighbour discovery request.
Definition: neighbour.h:31
#define ENOMEM
Not enough space.
Definition: errno.h:534
void * memcpy(void *dest, const void *src, size_t len) __nonnull
const char * name
Name.
Definition: netdevice.h:463
static int netdev_is_open(struct net_device *netdev)
Check whether or not network device is open.
Definition: netdevice.h:652
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
static void netdev_put(struct net_device *netdev)
Drop reference to network device.
Definition: netdevice.h:555
#define container_of(ptr, type, field)
Get containing structure.
Definition: stddef.h:35
#define CACHE_EXPENSIVE
Items with a high replacement cost.
Definition: malloc.h:109
unsigned int(* discard)(void)
Discard some cached data.
Definition: malloc.h:93
struct neighbour_discovery * discovery
Neighbour discovery protocol (if any)
Definition: neighbour.h:53
#define list_for_each_entry(pos, head, member)
Iterate over entries in a list.
Definition: list.h:420
#define list_add_tail(new, head)
Add a new entry to the tail of a list.
Definition: list.h:93
const char *(* ntoa)(const void *net_addr)
Transcribe network-layer address.
Definition: netdevice.h:94
int neighbour_define(struct net_device *netdev, struct net_protocol *net_protocol, const void *net_dest, const void *ll_dest)
Define neighbour cache entry.
Definition: neighbour.c:363
static struct net_device * netdev
Definition: gdbudp.c:52
struct net_driver neighbour_net_driver __net_driver
Neighbour driver (for net device notifications)
Definition: neighbour.c:399
struct list_head tx_queue
Pending I/O buffers.
Definition: neighbour.h:60
static unsigned int neighbour_discard(void)
Discard some cached neighbour entries.
Definition: neighbour.c:410
uint8_t ll_dest[MAX_LL_ADDR_LEN]
Link-layer destination address.
Definition: neighbour.h:50
#define list_for_each_entry_safe(pos, tmp, head, member)
Iterate over entries in a list, safe against deletion of the current entry.
Definition: list.h:447
char * strerror(int errno)
Retrieve string representation of error number.
Definition: strerror.c:78
static void(* free)(struct refcnt *refcnt))
Definition: refcnt.h:54
void * zalloc(size_t size)
Allocate cleared memory.
Definition: malloc.c:624
#define ref_get(refcnt)
Get additional reference to object.
Definition: refcnt.h:92
uint8_t * tmp
Definition: entropy.h:156
A network device.
Definition: netdevice.h:348
#define ENODEV
No such device.
Definition: errno.h:509
A cache discarder.
Definition: malloc.h:87
static void neighbour_discovered(struct neighbour *neighbour, const void *ll_dest)
Complete neighbour discovery.
Definition: neighbour.c:172
static struct net_device * netdev_get(struct net_device *netdev)
Get reference to network device.
Definition: netdevice.h:544
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
A neighbour cache entry.
Definition: neighbour.h:37
void start_timer(struct retry_timer *timer)
Start timer.
Definition: retry.c:93
A network-layer protocol.
Definition: netdevice.h:64
int neighbour_tx(struct io_buffer *iobuf, struct net_device *netdev, struct net_protocol *net_protocol, const void *net_dest, struct neighbour_discovery *discovery, const void *net_source, const void *ll_source)
Transmit packet, determining link-layer address via neighbour discovery.
Definition: neighbour.c:299
#define INIT_LIST_HEAD(list)
Initialise a list head.
Definition: list.h:45
void stop_timer(struct retry_timer *timer)
Stop timer.
Definition: retry.c:117
char name[NETDEV_NAME_LEN]
Name of this network device.
Definition: netdevice.h:358
struct list_head list
List of which this buffer is a member.
Definition: iobuf.h:39
int net_tx(struct io_buffer *iobuf, struct net_device *netdev, struct net_protocol *net_protocol, const void *ll_dest, const void *ll_source)
Transmit network-layer packet.
Definition: netdevice.c:999
#define NEIGHBOUR_MAX_TIMEOUT
Neighbour discovery maximum timeout.
Definition: neighbour.c:49
#define ENOBUFS
No buffer space available.
Definition: errno.h:498
#define DBGC2(...)
Definition: compiler.h:522
uint8_t net_addr_len
Network-layer address length.
Definition: netdevice.h:101
Neighbour discovery.
static void neighbour_expired(struct retry_timer *timer, int over)
Handle neighbour timer expiry.
Definition: neighbour.c:255
struct net_device * netdev
Network device.
Definition: neighbour.h:44
const char *(* ntoa)(const void *ll_addr)
Transcribe link-layer address.
Definition: netdevice.h:163
static void neighbour_destroy(struct neighbour *neighbour, int rc)
Destroy neighbour cache entry.
Definition: neighbour.c:219
static void neighbour_free(struct refcnt *refcnt)
Free neighbour cache entry.
Definition: neighbour.c:61
static void neighbour_flush(struct net_device *netdev)
Update neighbour cache on network device state change or removal.
Definition: neighbour.c:387
uint8_t ll_addr[MAX_LL_ADDR_LEN]
Link-layer address.
Definition: netdevice.h:381
#define LIST_HEAD_INIT(list)
Initialise a static list head.
Definition: list.h:30
int memcmp(const void *first, const void *second, size_t len)
Compare memory regions.
Definition: string.c:98
#define NULL
NULL pointer (VOID *)
Definition: Base.h:362
#define ETIMEDOUT
Connection timed out.
Definition: errno.h:669
String functions.
uint8_t net_source[MAX_NET_ADDR_LEN]
Network-layer source address (if any)
Definition: neighbour.h:55
struct ll_protocol * ll_protocol
Link-layer protocol.
Definition: netdevice.h:366
#define ref_put(refcnt)
Drop reference to object.
Definition: refcnt.h:106
static int neighbour_has_ll_dest(struct neighbour *neighbour)
Test if neighbour cache entry has a valid link-layer address.
Definition: neighbour.h:70
static void neighbour_discover(struct neighbour *neighbour, struct neighbour_discovery *discovery, const void *net_source)
Start neighbour discovery.
Definition: neighbour.c:146
A persistent I/O buffer.
Definition: iobuf.h:32