iPXE
neighbour.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2013 Michael Brown <mbrown@fensystems.co.uk>.
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License as
00006  * published by the Free Software Foundation; either version 2 of the
00007  * License, or any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00017  * 02110-1301, USA.
00018  *
00019  * You can also choose to distribute this program under the terms of
00020  * the Unmodified Binary Distribution Licence (as given in the file
00021  * COPYING.UBDL), provided that you have satisfied its requirements.
00022  */
00023 
00024 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00025 
00026 #include <stdint.h>
00027 #include <stdlib.h>
00028 #include <string.h>
00029 #include <errno.h>
00030 #include <ipxe/iobuf.h>
00031 #include <ipxe/retry.h>
00032 #include <ipxe/timer.h>
00033 #include <ipxe/malloc.h>
00034 #include <ipxe/neighbour.h>
00035 
00036 /** @file
00037  *
00038  * Neighbour discovery
00039  *
00040  * This file implements the abstract functions of neighbour discovery,
00041  * independent of the underlying network protocol (e.g. ARP or NDP).
00042  *
00043  */
00044 
00045 /** Neighbour discovery minimum timeout */
00046 #define NEIGHBOUR_MIN_TIMEOUT ( TICKS_PER_SEC / 8 )
00047 
00048 /** Neighbour discovery maximum timeout */
00049 #define NEIGHBOUR_MAX_TIMEOUT ( TICKS_PER_SEC * 3 )
00050 
00051 /** The neighbour cache */
00052 struct list_head neighbours = LIST_HEAD_INIT ( neighbours );
00053 
00054 static void neighbour_expired ( struct retry_timer *timer, int over );
00055 
00056 /**
00057  * Free neighbour cache entry
00058  *
00059  * @v refcnt            Reference count
00060  */
00061 static void neighbour_free ( struct refcnt *refcnt ) {
00062         struct neighbour *neighbour =
00063                 container_of ( refcnt, struct neighbour, refcnt );
00064 
00065         /* Sanity check */
00066         assert ( list_empty ( &neighbour->tx_queue ) );
00067 
00068         /* Drop reference to network device */
00069         netdev_put ( neighbour->netdev );
00070 
00071         /* Free neighbour */
00072         free ( neighbour );
00073 }
00074 
00075 /**
00076  * Create neighbour cache entry
00077  *
00078  * @v netdev            Network device
00079  * @v net_protocol      Network-layer protocol
00080  * @v net_dest          Destination network-layer address
00081  * @ret neighbour       Neighbour cache entry, or NULL if allocation failed
00082  */
00083 static struct neighbour * neighbour_create ( struct net_device *netdev,
00084                                              struct net_protocol *net_protocol,
00085                                              const void *net_dest ) {
00086         struct neighbour *neighbour;
00087 
00088         /* Allocate and initialise entry */
00089         neighbour = zalloc ( sizeof ( *neighbour ) );
00090         if ( ! neighbour )
00091                 return NULL;
00092         ref_init ( &neighbour->refcnt, neighbour_free );
00093         neighbour->netdev = netdev_get ( netdev );
00094         neighbour->net_protocol = net_protocol;
00095         memcpy ( neighbour->net_dest, net_dest,
00096                  net_protocol->net_addr_len );
00097         timer_init ( &neighbour->timer, neighbour_expired, &neighbour->refcnt );
00098         set_timer_limits ( &neighbour->timer, NEIGHBOUR_MIN_TIMEOUT,
00099                            NEIGHBOUR_MAX_TIMEOUT );
00100         INIT_LIST_HEAD ( &neighbour->tx_queue );
00101 
00102         /* Transfer ownership to cache */
00103         list_add ( &neighbour->list, &neighbours );
00104 
00105         DBGC ( neighbour, "NEIGHBOUR %s %s %s created\n", netdev->name,
00106                net_protocol->name, net_protocol->ntoa ( net_dest ) );
00107         return neighbour;
00108 }
00109 
00110 /**
00111  * Find neighbour cache entry
00112  *
00113  * @v netdev            Network device
00114  * @v net_protocol      Network-layer protocol
00115  * @v net_dest          Destination network-layer address
00116  * @ret neighbour       Neighbour cache entry, or NULL if not found
00117  */
00118 static struct neighbour * neighbour_find ( struct net_device *netdev,
00119                                            struct net_protocol *net_protocol,
00120                                            const void *net_dest ) {
00121         struct neighbour *neighbour;
00122 
00123         list_for_each_entry ( neighbour, &neighbours, list ) {
00124                 if ( ( neighbour->netdev == netdev ) &&
00125                      ( neighbour->net_protocol == net_protocol ) &&
00126                      ( memcmp ( neighbour->net_dest, net_dest,
00127                                 net_protocol->net_addr_len ) == 0 ) ) {
00128 
00129                         /* Move to start of cache */
00130                         list_del ( &neighbour->list );
00131                         list_add ( &neighbour->list, &neighbours );
00132 
00133                         return neighbour;
00134                 }
00135         }
00136         return NULL;
00137 }
00138 
00139 /**
00140  * Start neighbour discovery
00141  *
00142  * @v neighbour         Neighbour cache entry
00143  * @v discovery         Neighbour discovery protocol
00144  * @v net_source        Source network-layer address
00145  */
00146 static void neighbour_discover ( struct neighbour *neighbour,
00147                                  struct neighbour_discovery *discovery,
00148                                  const void *net_source ) {
00149         struct net_device *netdev = neighbour->netdev;
00150         struct net_protocol *net_protocol = neighbour->net_protocol;
00151 
00152         /* Record discovery protocol and source network-layer address */
00153         neighbour->discovery = discovery;
00154         memcpy ( neighbour->net_source, net_source,
00155                  net_protocol->net_addr_len );
00156 
00157         /* Start timer to trigger neighbour discovery */
00158         start_timer_nodelay ( &neighbour->timer );
00159 
00160         DBGC ( neighbour, "NEIGHBOUR %s %s %s discovering via %s\n",
00161                netdev->name, net_protocol->name,
00162                net_protocol->ntoa ( neighbour->net_dest ),
00163                neighbour->discovery->name );
00164 }
00165 
00166 /**
00167  * Complete neighbour discovery
00168  *
00169  * @v neighbour         Neighbour cache entry
00170  * @v ll_dest           Destination link-layer address
00171  */
00172 static void neighbour_discovered ( struct neighbour *neighbour,
00173                                    const void *ll_dest ) {
00174         struct net_device *netdev = neighbour->netdev;
00175         struct ll_protocol *ll_protocol = netdev->ll_protocol;
00176         struct net_protocol *net_protocol = neighbour->net_protocol;
00177         struct io_buffer *iobuf;
00178         int rc;
00179 
00180         /* Fill in link-layer address */
00181         memcpy ( neighbour->ll_dest, ll_dest, ll_protocol->ll_addr_len );
00182         DBGC ( neighbour, "NEIGHBOUR %s %s %s is %s %s\n", netdev->name,
00183                net_protocol->name, net_protocol->ntoa ( neighbour->net_dest ),
00184                ll_protocol->name, ll_protocol->ntoa ( neighbour->ll_dest ) );
00185 
00186         /* Stop retransmission timer */
00187         stop_timer ( &neighbour->timer );
00188 
00189         /* Transmit any packets in queue.  Take out a temporary
00190          * reference on the entry to prevent it from going out of
00191          * scope during the call to net_tx().
00192          */
00193         ref_get ( &neighbour->refcnt );
00194         while ( ( iobuf = list_first_entry ( &neighbour->tx_queue,
00195                                              struct io_buffer, list )) != NULL){
00196                 DBGC2 ( neighbour, "NEIGHBOUR %s %s %s transmitting deferred "
00197                         "packet\n", netdev->name, net_protocol->name,
00198                         net_protocol->ntoa ( neighbour->net_dest ) );
00199                 list_del ( &iobuf->list );
00200                 if ( ( rc = net_tx ( iobuf, netdev, net_protocol, ll_dest,
00201                                      netdev->ll_addr ) ) != 0 ) {
00202                         DBGC ( neighbour, "NEIGHBOUR %s %s %s could not "
00203                                "transmit deferred packet: %s\n",
00204                                netdev->name, net_protocol->name,
00205                                net_protocol->ntoa ( neighbour->net_dest ),
00206                                strerror ( rc ) );
00207                         /* Ignore error and continue */
00208                 }
00209         }
00210         ref_put ( &neighbour->refcnt );
00211 }
00212 
00213 /**
00214  * Destroy neighbour cache entry
00215  *
00216  * @v neighbour         Neighbour cache entry
00217  * @v rc                Reason for destruction
00218  */
00219 static void neighbour_destroy ( struct neighbour *neighbour, int rc ) {
00220         struct net_device *netdev = neighbour->netdev;
00221         struct net_protocol *net_protocol = neighbour->net_protocol;
00222         struct io_buffer *iobuf;
00223 
00224         /* Take ownership from cache */
00225         list_del ( &neighbour->list );
00226 
00227         /* Stop timer */
00228         stop_timer ( &neighbour->timer );
00229 
00230         /* Discard any outstanding I/O buffers */
00231         while ( ( iobuf = list_first_entry ( &neighbour->tx_queue,
00232                                              struct io_buffer, list )) != NULL){
00233                 DBGC2 ( neighbour, "NEIGHBOUR %s %s %s discarding deferred "
00234                         "packet: %s\n", netdev->name, net_protocol->name,
00235                         net_protocol->ntoa ( neighbour->net_dest ),
00236                         strerror ( rc ) );
00237                 list_del ( &iobuf->list );
00238                 netdev_tx_err ( neighbour->netdev, iobuf, rc );
00239         }
00240 
00241         DBGC ( neighbour, "NEIGHBOUR %s %s %s destroyed: %s\n", netdev->name,
00242                net_protocol->name, net_protocol->ntoa ( neighbour->net_dest ),
00243                strerror ( rc ) );
00244 
00245         /* Drop remaining reference */
00246         ref_put ( &neighbour->refcnt );
00247 }
00248 
00249 /**
00250  * Handle neighbour timer expiry
00251  *
00252  * @v timer             Retry timer
00253  * @v fail              Failure indicator
00254  */
00255 static void neighbour_expired ( struct retry_timer *timer, int fail ) {
00256         struct neighbour *neighbour =
00257                 container_of ( timer, struct neighbour, timer );
00258         struct net_device *netdev = neighbour->netdev;
00259         struct net_protocol *net_protocol = neighbour->net_protocol;
00260         struct neighbour_discovery *discovery =
00261                 neighbour->discovery;
00262         const void *net_dest = neighbour->net_dest;
00263         const void *net_source = neighbour->net_source;
00264         int rc;
00265 
00266         /* If we have failed, destroy the cache entry */
00267         if ( fail ) {
00268                 neighbour_destroy ( neighbour, -ETIMEDOUT );
00269                 return;
00270         }
00271 
00272         /* Restart the timer */
00273         start_timer ( &neighbour->timer );
00274 
00275         /* Transmit neighbour request */
00276         if ( ( rc = discovery->tx_request ( netdev, net_protocol, net_dest,
00277                                             net_source ) ) != 0 ) {
00278                 DBGC ( neighbour, "NEIGHBOUR %s %s %s could not transmit %s "
00279                        "request: %s\n", netdev->name, net_protocol->name,
00280                        net_protocol->ntoa ( neighbour->net_dest ),
00281                        neighbour->discovery->name, strerror ( rc ) );
00282                 /* Retransmit when timer expires */
00283                 return;
00284         }
00285 }
00286 
00287 /**
00288  * Transmit packet, determining link-layer address via neighbour discovery
00289  *
00290  * @v iobuf             I/O buffer
00291  * @v netdev            Network device
00292  * @v discovery         Neighbour discovery protocol
00293  * @v net_protocol      Network-layer protocol
00294  * @v net_dest          Destination network-layer address
00295  * @v net_source        Source network-layer address
00296  * @v ll_source         Source link-layer address
00297  * @ret rc              Return status code
00298  */
00299 int neighbour_tx ( struct io_buffer *iobuf, struct net_device *netdev,
00300                    struct net_protocol *net_protocol, const void *net_dest,
00301                    struct neighbour_discovery *discovery,
00302                    const void *net_source, const void *ll_source ) {
00303         struct neighbour *neighbour;
00304 
00305         /* Find or create neighbour cache entry */
00306         neighbour = neighbour_find ( netdev, net_protocol, net_dest );
00307         if ( ! neighbour ) {
00308                 neighbour = neighbour_create ( netdev, net_protocol, net_dest );
00309                 if ( ! neighbour )
00310                         return -ENOMEM;
00311                 neighbour_discover ( neighbour, discovery, net_source );
00312         }
00313 
00314         /* If a link-layer address is available then transmit
00315          * immediately, otherwise queue for later transmission.
00316          */
00317         if ( neighbour_has_ll_dest ( neighbour ) ) {
00318                 return net_tx ( iobuf, netdev, net_protocol, neighbour->ll_dest,
00319                                 ll_source );
00320         } else {
00321                 DBGC2 ( neighbour, "NEIGHBOUR %s %s %s deferring packet\n",
00322                         netdev->name, net_protocol->name,
00323                         net_protocol->ntoa ( net_dest ) );
00324                 list_add_tail ( &iobuf->list, &neighbour->tx_queue );
00325                 return 0;
00326         }
00327 }
00328 
00329 /**
00330  * Update existing neighbour cache entry
00331  *
00332  * @v netdev            Network device
00333  * @v net_protocol      Network-layer protocol
00334  * @v net_dest          Destination network-layer address
00335  * @v ll_dest           Destination link-layer address
00336  * @ret rc              Return status code
00337  */
00338 int neighbour_update ( struct net_device *netdev,
00339                        struct net_protocol *net_protocol,
00340                        const void *net_dest, const void *ll_dest ) {
00341         struct neighbour *neighbour;
00342 
00343         /* Find neighbour cache entry */
00344         neighbour = neighbour_find ( netdev, net_protocol, net_dest );
00345         if ( ! neighbour )
00346                 return -ENOENT;
00347 
00348         /* Set destination address */
00349         neighbour_discovered ( neighbour, ll_dest );
00350 
00351         return 0;
00352 }
00353 
00354 /**
00355  * Define neighbour cache entry
00356  *
00357  * @v netdev            Network device
00358  * @v net_protocol      Network-layer protocol
00359  * @v net_dest          Destination network-layer address
00360  * @v ll_dest           Destination link-layer address, if known
00361  * @ret rc              Return status code
00362  */
00363 int neighbour_define ( struct net_device *netdev,
00364                        struct net_protocol *net_protocol,
00365                        const void *net_dest, const void *ll_dest ) {
00366         struct neighbour *neighbour;
00367 
00368         /* Find or create neighbour cache entry */
00369         neighbour = neighbour_find ( netdev, net_protocol, net_dest );
00370         if ( ! neighbour ) {
00371                 neighbour = neighbour_create ( netdev, net_protocol, net_dest );
00372                 if ( ! neighbour )
00373                         return -ENOMEM;
00374         }
00375 
00376         /* Set destination address */
00377         neighbour_discovered ( neighbour, ll_dest );
00378 
00379         return 0;
00380 }
00381 
00382 /**
00383  * Update neighbour cache on network device state change or removal
00384  *
00385  * @v netdev            Network device
00386  */
00387 static void neighbour_flush ( struct net_device *netdev ) {
00388         struct neighbour *neighbour;
00389         struct neighbour *tmp;
00390 
00391         /* Remove all neighbour cache entries when a network device is closed */
00392         if ( ! netdev_is_open ( netdev ) ) {
00393                 list_for_each_entry_safe ( neighbour, tmp, &neighbours, list )
00394                         neighbour_destroy ( neighbour, -ENODEV );
00395         }
00396 }
00397 
00398 /** Neighbour driver (for net device notifications) */
00399 struct net_driver neighbour_net_driver __net_driver = {
00400         .name = "Neighbour",
00401         .notify = neighbour_flush,
00402         .remove = neighbour_flush,
00403 };
00404 
00405 /**
00406  * Discard some cached neighbour entries
00407  *
00408  * @ret discarded       Number of cached items discarded
00409  */
00410 static unsigned int neighbour_discard ( void ) {
00411         struct neighbour *neighbour;
00412 
00413         /* Drop oldest cache entry, if any */
00414         neighbour = list_last_entry ( &neighbours, struct neighbour, list );
00415         if ( neighbour ) {
00416                 neighbour_destroy ( neighbour, -ENOBUFS );
00417                 return 1;
00418         } else {
00419                 return 0;
00420         }
00421 }
00422 
00423 /**
00424  * Neighbour cache discarder
00425  *
00426  * Neighbour cache entries are deemed to have a high replacement cost,
00427  * since flushing an active neighbour cache entry midway through a TCP
00428  * transfer will cause substantial disruption.
00429  */
00430 struct cache_discarder neighbour_discarder __cache_discarder (CACHE_EXPENSIVE)={
00431         .discard = neighbour_discard,
00432 };