The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/netinet/ip_id.c

Version: -  FREEBSD  -  FREEBSD11  -  FREEBSD10  -  FREEBSD9  -  FREEBSD92  -  FREEBSD91  -  FREEBSD90  -  FREEBSD8  -  FREEBSD82  -  FREEBSD81  -  FREEBSD80  -  FREEBSD7  -  FREEBSD74  -  FREEBSD73  -  FREEBSD72  -  FREEBSD71  -  FREEBSD70  -  FREEBSD6  -  FREEBSD64  -  FREEBSD63  -  FREEBSD62  -  FREEBSD61  -  FREEBSD60  -  FREEBSD5  -  FREEBSD55  -  FREEBSD54  -  FREEBSD53  -  FREEBSD52  -  FREEBSD51  -  FREEBSD50  -  FREEBSD4  -  FREEBSD3  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 
    2 /*-
    3  * Copyright (c) 2008 Michael J. Silbersack.
    4  * All rights reserved.
    5  *
    6  * Redistribution and use in source and binary forms, with or without
    7  * modification, are permitted provided that the following conditions
    8  * are met:
    9  * 1. Redistributions of source code must retain the above copyright
   10  *    notice unmodified, this list of conditions, and the following
   11  *    disclaimer.
   12  * 2. Redistributions in binary form must reproduce the above copyright
   13  *    notice, this list of conditions and the following disclaimer in the
   14  *    documentation and/or other materials provided with the distribution.
   15  *
   16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
   17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
   19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
   20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
   21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
   22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
   23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
   25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   26  */
   27 
   28 #include <sys/cdefs.h>
   29 __FBSDID("$FreeBSD: releng/8.2/sys/netinet/ip_id.c 199583 2009-11-20 15:27:52Z jhb $");
   30 
   31 /*
   32  * IP ID generation is a fascinating topic.
   33  *
   34  * In order to avoid ID collisions during packet reassembly, common sense
   35  * dictates that the period between reuse of IDs be as large as possible.
   36  * This leads to the classic implementation of a system-wide counter, thereby
   37  * ensuring that IDs repeat only once every 2^16 packets.
   38  *
   39  * Subsequent security researchers have pointed out that using a global
   40  * counter makes ID values predictable.  This predictability allows traffic
   41  * analysis, idle scanning, and even packet injection in specific cases.
   42  * These results suggest that IP IDs should be as random as possible.
   43  *
   44  * The "searchable queues" algorithm used in this IP ID implementation was
   45  * proposed by Amit Klein.  It is a compromise between the above two
   46  * viewpoints that has provable behavior that can be tuned to the user's
   47  * requirements.
   48  *
   49  * The basic concept is that we supplement a standard random number generator
   50  * with a queue of the last L IDs that we have handed out to ensure that all
   51  * IDs have a period of at least L.
   52  *
   53  * To efficiently implement this idea, we keep two data structures: a
   54  * circular array of IDs of size L and a bitstring of 65536 bits.
   55  *
   56  * To start, we ask the RNG for a new ID.  A quick index into the bitstring
   57  * is used to determine if this is a recently used value.  The process is
   58  * repeated until a value is returned that is not in the bitstring.
   59  *
   60  * Having found a usable ID, we remove the ID stored at the current position
   61  * in the queue from the bitstring and replace it with our new ID.  Our new
   62  * ID is then added to the bitstring and the queue pointer is incremented.
   63  *
   64  * The lower limit of 512 was chosen because there doesn't seem to be much
   65  * point to having a smaller value.  The upper limit of 32768 was chosen for
   66  * two reasons.  First, every step above 32768 decreases the entropy.  Taken
   67  * to an extreme, 65533 would offer 1 bit of entropy.  Second, the number of
   68  * attempts it takes the algorithm to find an unused ID drastically
   69  * increases, killing performance.  The default value of 8192 was chosen
   70  * because it provides a good tradeoff between randomness and non-repetition.
   71  *
   72  * With L=8192, the queue will use 16K of memory.  The bitstring always
   73  * uses 8K of memory.  No memory is allocated until the use of random ids is
   74  * enabled.
   75  */
   76 
   77 #include <sys/types.h>
   78 #include <sys/malloc.h>
   79 #include <sys/param.h>
   80 #include <sys/time.h>
   81 #include <sys/kernel.h>
   82 #include <sys/libkern.h>
   83 #include <sys/lock.h>
   84 #include <sys/mutex.h>
   85 #include <sys/random.h>
   86 #include <sys/systm.h>
   87 #include <sys/sysctl.h>
   88 #include <netinet/in.h>
   89 #include <netinet/ip_var.h>
   90 #include <sys/bitstring.h>
   91 
   92 static MALLOC_DEFINE(M_IPID, "ipid", "randomized ip id state");
   93 
   94 static u_int16_t        *id_array = NULL;
   95 static bitstr_t         *id_bits = NULL;
   96 static int               array_ptr = 0;
   97 static int               array_size = 8192;
   98 static int               random_id_collisions = 0;
   99 static int               random_id_total = 0;
  100 static struct mtx        ip_id_mtx;
  101 
  102 static void     ip_initid(void);
  103 static int      sysctl_ip_id_change(SYSCTL_HANDLER_ARGS);
  104 
  105 MTX_SYSINIT(ip_id_mtx, &ip_id_mtx, "ip_id_mtx", MTX_DEF);
  106 
  107 SYSCTL_DECL(_net_inet_ip);
  108 SYSCTL_PROC(_net_inet_ip, OID_AUTO, random_id_period, CTLTYPE_INT|CTLFLAG_RW,
  109     &array_size, 0, sysctl_ip_id_change, "IU", "IP ID Array size");
  110 SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_collisions, CTLFLAG_RD,
  111     &random_id_collisions, 0, "Count of IP ID collisions");
  112 SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_total, CTLFLAG_RD,
  113     &random_id_total, 0, "Count of IP IDs created");
  114 
  115 static int
  116 sysctl_ip_id_change(SYSCTL_HANDLER_ARGS)
  117 {
  118         int error, new;
  119 
  120         new = array_size;
  121         error = sysctl_handle_int(oidp, &new, 0, req);
  122         if (error == 0 && req->newptr) {
  123                 if (new >= 512 && new <= 32768) {
  124                         mtx_lock(&ip_id_mtx);
  125                         array_size = new;
  126                         ip_initid();
  127                         mtx_unlock(&ip_id_mtx);
  128                 } else
  129                         error = EINVAL;
  130         }
  131         return (error);
  132 }
  133 
  134 /*
  135  * ip_initid() runs with a mutex held and may execute in a network context.
  136  * As a result, it uses M_NOWAIT.  Ideally, we would always do this
  137  * allocation from the sysctl contact and have it be an invariant that if
  138  * this random ID allocation mode is selected, the buffers are present.  This
  139  * would also avoid potential network context failures of IP ID generation.
  140  */
  141 static void
  142 ip_initid(void)
  143 {
  144 
  145         mtx_assert(&ip_id_mtx, MA_OWNED);
  146 
  147         if (id_array != NULL) {
  148                 free(id_array, M_IPID);
  149                 free(id_bits, M_IPID);
  150         }
  151         random_id_collisions = 0;
  152         random_id_total = 0;
  153         array_ptr = 0;
  154         id_array = (u_int16_t *) malloc(array_size * sizeof(u_int16_t),
  155             M_IPID, M_NOWAIT | M_ZERO);
  156         id_bits = (bitstr_t *) malloc(bitstr_size(65536), M_IPID,
  157             M_NOWAIT | M_ZERO);
  158         if (id_array == NULL || id_bits == NULL) {
  159                 /* Neither or both. */
  160                 if (id_array != NULL) {
  161                         free(id_array, M_IPID);
  162                         id_array = NULL;
  163                 }
  164                 if (id_bits != NULL) {
  165                         free(id_bits, M_IPID);
  166                         id_bits = NULL;
  167                 }
  168         }
  169 }
  170 
  171 u_int16_t
  172 ip_randomid(void)
  173 {
  174         u_int16_t new_id;
  175 
  176         mtx_lock(&ip_id_mtx);
  177         if (id_array == NULL)
  178                 ip_initid();
  179 
  180         /*
  181          * Fail gracefully; return a fixed id if memory allocation failed;
  182          * ideally we wouldn't do allocation in this context in order to
  183          * avoid the possibility of this failure mode.
  184          */
  185         if (id_array == NULL) {
  186                 mtx_unlock(&ip_id_mtx);
  187                 return (1);
  188         }
  189 
  190         /*
  191          * To avoid a conflict with the zeros that the array is initially
  192          * filled with, we never hand out an id of zero.
  193          */
  194         new_id = 0;
  195         do {
  196                 if (new_id != 0)
  197                         random_id_collisions++;
  198                 arc4rand(&new_id, sizeof(new_id), 0);
  199         } while (bit_test(id_bits, new_id) || new_id == 0);
  200         bit_clear(id_bits, id_array[array_ptr]);
  201         bit_set(id_bits, new_id);
  202         id_array[array_ptr] = new_id;
  203         array_ptr++;
  204         if (array_ptr == array_size)
  205                 array_ptr = 0;
  206         random_id_total++;
  207         mtx_unlock(&ip_id_mtx);
  208         return (new_id);
  209 }

Cache object: 3c0f633a80eb3957206509f02559e9fe


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.