qemu/roms/ipxe/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 };