[neighbour] Generalise concept of neighbour discovery

Split the protocol-independent portions of arp.c into a separate file
neighbour.c, to allow for sharing of functionality between IPv4+ARP
and IPv6+NDP.

Signed-off-by: Michael Brown <mcb30@ipxe.org>

1 files changed, 479 insertions, 0 deletions

diff --git a/src/net/neighbour.c b/src/net/neighbour.c
new file mode 100644
index 00000000..210b7138
--- /dev/null
+++ b/src/net/neighbour.c
@@ -0,0 +1,479 @@
+/*
+ * Copyright (C) 2013 Michael Brown <mbrown@fensystems.co.uk>.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA.
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER );
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+#include <ipxe/refcnt.h>
+#include <ipxe/list.h>
+#include <ipxe/iobuf.h>
+#include <ipxe/retry.h>
+#include <ipxe/timer.h>
+#include <ipxe/malloc.h>
+#include <ipxe/neighbour.h>
+
+/** @file
+ *
+ * Neighbour discovery
+ *
+ * This file implements the abstract functions of neighbour discovery,
+ * independent of the underlying network protocol (e.g. ARP or NDP).
+ *
+ */
+
+/** A neighbour cache entry */
+struct neighbour {
+	/** Reference count */
+	struct refcnt refcnt;
+	/** List of neighbour cache entries */
+	struct list_head list;
+
+	/** Network device */
+	struct net_device *netdev;
+	/** Network-layer protocol */
+	struct net_protocol *net_protocol;
+	/** Network-layer destination address */
+	uint8_t net_dest[MAX_NET_ADDR_LEN];
+	/** Link-layer destination address */
+	uint8_t ll_dest[MAX_LL_ADDR_LEN];
+
+	/** Neighbour discovery protocol (if any) */
+	struct neighbour_discovery *discovery;
+	/** Network-layer source address (if any) */
+	uint8_t net_source[MAX_NET_ADDR_LEN];
+	/** Retransmission timer */
+	struct retry_timer timer;
+
+	/** Pending I/O buffers */
+	struct list_head tx_queue;
+};
+
+/** Neighbour discovery minimum timeout */
+#define NEIGHBOUR_MIN_TIMEOUT ( TICKS_PER_SEC / 8 )
+
+/** Neighbour discovery maximum timeout */
+#define NEIGHBOUR_MAX_TIMEOUT ( TICKS_PER_SEC * 3 )
+
+/** The neighbour cache */
+static LIST_HEAD ( neighbours );
+
+static void neighbour_expired ( struct retry_timer *timer, int over );
+
+/**
+ * Free neighbour cache entry
+ *
+ * @v refcnt		Reference count
+ */
+static void neighbour_free ( struct refcnt *refcnt ) {
+	struct neighbour *neighbour =
+		container_of ( refcnt, struct neighbour, refcnt );
+
+	/* Sanity check */
+	assert ( list_empty ( &neighbour->tx_queue ) );
+
+	/* Drop reference to network device */
+	netdev_put ( neighbour->netdev );
+
+	/* Free neighbour */
+	free ( neighbour );
+}
+
+/**
+ * Test if neighbour cache entry has a valid link-layer address
+ *
+ * @v neighbour		Neighbour cache entry
+ * @ret has_ll_dest	Neighbour cache entry has a valid link-layer address
+ */
+static inline __attribute__ (( always_inline )) int
+neighbour_has_ll_dest ( struct neighbour *neighbour ) {
+	return ( ! timer_running ( &neighbour->timer ) );
+}
+
+/**
+ * Create neighbour cache entry
+ *
+ * @v netdev		Network device
+ * @v net_protocol	Network-layer protocol
+ * @v net_dest		Destination network-layer address
+ * @ret neighbour	Neighbour cache entry, or NULL if allocation failed
+ */
+static struct neighbour * neighbour_create ( struct net_device *netdev,
+					     struct net_protocol *net_protocol,
+					     const void *net_dest ) {
+	struct neighbour *neighbour;
+
+	/* Allocate and initialise entry */
+	neighbour = zalloc ( sizeof ( *neighbour ) );
+	if ( ! neighbour )
+		return NULL;
+	ref_init ( &neighbour->refcnt, neighbour_free );
+	neighbour->netdev = netdev_get ( netdev );
+	neighbour->net_protocol = net_protocol;
+	memcpy ( neighbour->net_dest, net_dest,
+		 net_protocol->net_addr_len );
+	timer_init ( &neighbour->timer, neighbour_expired, &neighbour->refcnt );
+	neighbour->timer.min_timeout = NEIGHBOUR_MIN_TIMEOUT;
+	neighbour->timer.max_timeout = NEIGHBOUR_MAX_TIMEOUT;
+	INIT_LIST_HEAD ( &neighbour->tx_queue );
+
+	/* Transfer ownership to cache */
+	list_add ( &neighbour->list, &neighbours );
+
+	DBGC ( neighbour, "NEIGHBOUR %s %s %s created\n", netdev->name,
+	       net_protocol->name, net_protocol->ntoa ( net_dest ) );
+	return neighbour;
+}
+
+/**
+ * Find neighbour cache entry
+ *
+ * @v netdev		Network device
+ * @v net_protocol	Network-layer protocol
+ * @v net_dest		Destination network-layer address
+ * @ret neighbour	Neighbour cache entry, or NULL if not found
+ */
+static struct neighbour * neighbour_find ( struct net_device *netdev,
+					   struct net_protocol *net_protocol,
+					   const void *net_dest ) {
+	struct neighbour *neighbour;
+
+	list_for_each_entry ( neighbour, &neighbours, list ) {
+		if ( ( neighbour->netdev == netdev ) &&
+		     ( neighbour->net_protocol == net_protocol ) &&
+		     ( memcmp ( neighbour->net_dest, net_dest,
+				net_protocol->net_addr_len ) == 0 ) ) {
+
+			/* Move to start of cache */
+			list_del ( &neighbour->list );
+			list_add ( &neighbour->list, &neighbours );
+
+			return neighbour;
+		}
+	}
+	return NULL;
+}
+
+/**
+ * Start neighbour discovery
+ *
+ * @v neighbour		Neighbour cache entry
+ * @v discovery		Neighbour discovery protocol
+ * @v net_source	Source network-layer address
+ */
+static void neighbour_discover ( struct neighbour *neighbour,
+				 struct neighbour_discovery *discovery,
+				 const void *net_source ) {
+	struct net_device *netdev = neighbour->netdev;
+	struct net_protocol *net_protocol = neighbour->net_protocol;
+
+	/* Record discovery protocol and source network-layer address */
+	neighbour->discovery = discovery;
+	memcpy ( neighbour->net_source, net_source,
+		 net_protocol->net_addr_len );
+
+	/* Start timer to trigger neighbour discovery */
+	start_timer_nodelay ( &neighbour->timer );
+
+	DBGC ( neighbour, "NEIGHBOUR %s %s %s discovering via %s\n",
+	       netdev->name, net_protocol->name,
+	       net_protocol->ntoa ( neighbour->net_dest ),
+	       neighbour->discovery->name );
+}
+
+/**
+ * Complete neighbour discovery
+ *
+ * @v neighbour		Neighbour cache entry
+ * @v ll_dest		Destination link-layer address
+ */
+static void neighbour_discovered ( struct neighbour *neighbour,
+				   const void *ll_dest ) {
+	struct net_device *netdev = neighbour->netdev;
+	struct ll_protocol *ll_protocol = netdev->ll_protocol;
+	struct net_protocol *net_protocol = neighbour->net_protocol;
+	struct io_buffer *iobuf;
+	int rc;
+
+	/* Fill in link-layer address */
+	memcpy ( neighbour->ll_dest, ll_dest, ll_protocol->ll_addr_len );
+	DBGC ( neighbour, "NEIGHBOUR %s %s %s is %s %s\n", netdev->name,
+	       net_protocol->name, net_protocol->ntoa ( neighbour->net_dest ),
+	       ll_protocol->name, ll_protocol->ntoa ( neighbour->ll_dest ) );
+
+	/* Stop retransmission timer */
+	stop_timer ( &neighbour->timer );
+
+	/* Transmit any packets in queue.  Take out a temporary
+	 * reference on the entry to prevent it from going out of
+	 * scope during the call to net_tx().
+	 */
+	ref_get ( &neighbour->refcnt );
+	while ( ( iobuf = list_first_entry ( &neighbour->tx_queue,
+					     struct io_buffer, list )) != NULL){
+		DBGC2 ( neighbour, "NEIGHBOUR %s %s %s transmitting deferred "
+			"packet\n", netdev->name, net_protocol->name,
+			net_protocol->ntoa ( neighbour->net_dest ) );
+		list_del ( &iobuf->list );
+		if ( ( rc = net_tx ( iobuf, netdev, net_protocol, ll_dest,
+				     netdev->ll_addr ) ) != 0 ) {
+			DBGC ( neighbour, "NEIGHBOUR %s %s %s could not "
+			       "transmit deferred packet: %s\n",
+			       netdev->name, net_protocol->name,
+			       net_protocol->ntoa ( neighbour->net_dest ),
+			       strerror ( rc ) );
+			/* Ignore error and continue */
+		}
+	}
+	ref_put ( &neighbour->refcnt );
+}
+
+/**
+ * Destroy neighbour cache entry
+ *
+ * @v neighbour		Neighbour cache entry
+ * @v rc		Reason for destruction
+ */
+static void neighbour_destroy ( struct neighbour *neighbour, int rc ) {
+	struct net_device *netdev = neighbour->netdev;
+	struct net_protocol *net_protocol = neighbour->net_protocol;
+	struct io_buffer *iobuf;
+
+	/* Take ownership from cache */
+	list_del ( &neighbour->list );
+
+	/* Stop timer */
+	stop_timer ( &neighbour->timer );
+
+	/* Discard any outstanding I/O buffers */
+	while ( ( iobuf = list_first_entry ( &neighbour->tx_queue,
+					     struct io_buffer, list )) != NULL){
+		DBGC2 ( neighbour, "NEIGHBOUR %s %s %s discarding deferred "
+			"packet: %s\n", netdev->name, net_protocol->name,
+			net_protocol->ntoa ( neighbour->net_dest ),
+			strerror ( rc ) );
+		list_del ( &iobuf->list );
+		netdev_tx_err ( neighbour->netdev, iobuf, rc );
+	}
+
+	DBGC ( neighbour, "NEIGHBOUR %s %s %s destroyed: %s\n", netdev->name,
+	       net_protocol->name, net_protocol->ntoa ( neighbour->net_dest ),
+	       strerror ( rc ) );
+
+	/* Drop remaining reference */
+	ref_put ( &neighbour->refcnt );
+}
+
+/**
+ * Handle neighbour timer expiry
+ *
+ * @v timer		Retry timer
+ * @v fail		Failure indicator
+ */
+static void neighbour_expired ( struct retry_timer *timer, int fail ) {
+	struct neighbour *neighbour =
+		container_of ( timer, struct neighbour, timer );
+	struct net_device *netdev = neighbour->netdev;
+	struct net_protocol *net_protocol = neighbour->net_protocol;
+	struct neighbour_discovery *discovery =
+		neighbour->discovery;
+	const void *net_dest = neighbour->net_dest;
+	const void *net_source = neighbour->net_source;
+	int rc;
+
+	/* If we have failed, destroy the cache entry */
+	if ( fail ) {
+		neighbour_destroy ( neighbour, -ETIMEDOUT );
+		return;
+	}
+
+	/* Restart the timer */
+	start_timer ( &neighbour->timer );
+
+	/* Transmit neighbour request */
+	if ( ( rc = discovery->tx_request ( netdev, net_protocol, net_dest,
+					    net_source ) ) != 0 ) {
+		DBGC ( neighbour, "NEIGHBOUR %s %s %s could not transmit %s "
+		       "request: %s\n", netdev->name, net_protocol->name,
+		       net_protocol->ntoa ( neighbour->net_dest ),
+		       neighbour->discovery->name, strerror ( rc ) );
+		/* Retransmit when timer expires */
+		return;
+	}
+}
+
+/**
+ * Transmit packet, determining link-layer address via neighbour discovery
+ *
+ * @v iobuf		I/O buffer
+ * @v netdev		Network device
+ * @v discovery		Neighbour discovery protocol
+ * @v net_protocol	Network-layer protocol
+ * @v net_dest		Destination network-layer address
+ * @v net_source	Source network-layer address
+ * @v ll_source		Source link-layer address
+ * @ret rc		Return status code
+ */
+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 ) {
+	struct neighbour *neighbour;
+
+	/* Find or create neighbour cache entry */
+	neighbour = neighbour_find ( netdev, net_protocol, net_dest );
+	if ( ! neighbour ) {
+		neighbour = neighbour_create ( netdev, net_protocol, net_dest );
+		if ( ! neighbour )
+			return -ENOMEM;
+		neighbour_discover ( neighbour, discovery, net_source );
+	}
+
+	/* If a link-layer address is available then transmit
+	 * immediately, otherwise queue for later transmission.
+	 */
+	if ( neighbour_has_ll_dest ( neighbour ) ) {
+		return net_tx ( iobuf, netdev, net_protocol, neighbour->ll_dest,
+				ll_source );
+	} else {
+		DBGC2 ( neighbour, "NEIGHBOUR %s %s %s deferring packet\n",
+			netdev->name, net_protocol->name,
+			net_protocol->ntoa ( net_dest ) );
+		list_add_tail ( &iobuf->list, &neighbour->tx_queue );
+		return -EAGAIN;
+	}
+}
+
+/**
+ * Update existing neighbour cache entry
+ *
+ * @v netdev		Network device
+ * @v net_protocol	Network-layer protocol
+ * @v net_dest		Destination network-layer address
+ * @v ll_dest		Destination link-layer address
+ * @ret rc		Return status code
+ */
+int neighbour_update ( struct net_device *netdev,
+		       struct net_protocol *net_protocol,
+		       const void *net_dest, const void *ll_dest ) {
+	struct neighbour *neighbour;
+
+	/* Find neighbour cache entry */
+	neighbour = neighbour_find ( netdev, net_protocol, net_dest );
+	if ( ! neighbour )
+		return -ENOENT;
+
+	/* Set destination address */
+	neighbour_discovered ( neighbour, ll_dest );
+
+	return 0;
+}
+
+/**
+ * Define neighbour cache entry
+ *
+ * @v netdev		Network device
+ * @v net_protocol	Network-layer protocol
+ * @v net_dest		Destination network-layer address
+ * @v ll_dest		Destination link-layer address, if known
+ * @ret rc		Return status code
+ */
+int neighbour_define ( struct net_device *netdev,
+		       struct net_protocol *net_protocol,
+		       const void *net_dest, const void *ll_dest ) {
+	struct neighbour *neighbour;
+
+	/* Find or create neighbour cache entry */
+	neighbour = neighbour_find ( netdev, net_protocol, net_dest );
+	if ( ! neighbour ) {
+		neighbour = neighbour_create ( netdev, net_protocol, net_dest );
+		if ( ! neighbour )
+			return -ENOMEM;
+	}
+
+	/* Set destination address */
+	neighbour_discovered ( neighbour, ll_dest );
+
+	return 0;
+}
+
+/**
+ * Update neighbour cache on network device creation
+ *
+ * @v netdev		Network device
+ */
+static int neighbour_probe ( struct net_device *netdev __unused ) {
+	/* Nothing to do */
+	return 0;
+}
+
+/**
+ * Update neighbour cache on network device state change or removal
+ *
+ * @v netdev		Network device
+ */
+static void neighbour_flush ( struct net_device *netdev ) {
+	struct neighbour *neighbour;
+	struct neighbour *tmp;
+
+	/* Remove all neighbour cache entries when a network device is closed */
+	if ( ! netdev_is_open ( netdev ) ) {
+		list_for_each_entry_safe ( neighbour, tmp, &neighbours, list )
+			neighbour_destroy ( neighbour, -ENODEV );
+	}
+}
+
+/** Neighbour driver (for net device notifications) */
+struct net_driver neighbour_net_driver __net_driver = {
+	.name = "Neighbour",
+	.probe = neighbour_probe,
+	.notify = neighbour_flush,
+	.remove = neighbour_flush,
+};
+
+/**
+ * Discard some cached neighbour entries
+ *
+ * @ret discarded	Number of cached items discarded
+ */
+static unsigned int neighbour_discard ( void ) {
+	struct neighbour *neighbour;
+
+	/* Drop oldest cache entry, if any */
+	neighbour = list_last_entry ( &neighbours, struct neighbour, list );
+	if ( neighbour ) {
+		neighbour_destroy ( neighbour, -ENOBUFS );
+		return 1;
+	} else {
+		return 0;
+	}
+}
+
+/**
+ * Neighbour cache discarder
+ *
+ * Neighbour cache entries are deemed to have a high replacement cost,
+ * since flushing an active neighbour cache entry midway through a TCP
+ * transfer will cause substantial disruption.
+ */
+struct cache_discarder neighbour_discarder __cache_discarder (CACHE_EXPENSIVE)={
+	.discard = neighbour_discard,
+};