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
  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 };