doc/guides/prog_guide/hash_lib.rst

   1 ..  BSD LICENSE
   2     Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
   3     All rights reserved.
   4
   5     Redistribution and use in source and binary forms, with or without
   6     modification, are permitted provided that the following conditions
   7     are met:
   8
   9     * Redistributions of source code must retain the above copyright
  10     notice, this list of conditions and the following disclaimer.
  11     * Redistributions in binary form must reproduce the above copyright
  12     notice, this list of conditions and the following disclaimer in
  13     the documentation and/or other materials provided with the
  14     distribution.
  15     * Neither the name of Intel Corporation nor the names of its
  16     contributors may be used to endorse or promote products derived
  17     from this software without specific prior written permission.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30
  31 .. _Hash_Library:
  32
  33 Hash Library
  34 ============
  35
  36 The DPDK provides a Hash Library for creating hash table for fast lookup.
  37 The hash table is a data structure optimized for searching through a set of entries that are each identified by a unique key.
  38 For increased performance the DPDK Hash requires that all the keys have the same number of bytes which is set at the hash creation time.
  39
  40 Hash API Overview
  41 -----------------
  42
  43 The main configuration parameters for the hash are:
  44
  45 *   Total number of hash entries
  46
  47 *   Size of the key in bytes
  48
  49 The hash also allows the configuration of some low-level implementation related parameters such as:
  50
  51 *   Hash function to translate the key into a bucket index
  52
  53 *   Number of entries per bucket
  54
  55 The main methods exported by the hash are:
  56
  57 *   Add entry with key: The key is provided as input. If a new entry is successfully added to the hash for the specified key,
  58     or there is already an entry in the hash for the specified key, then the position of the entry is returned.
  59     If the operation was not successful, for example due to lack of free entries in the hash, then a negative value is returned;
  60
  61 *   Delete entry with key: The key is provided as input. If an entry with the specified key is found in the hash,
  62     then the entry is removed from the hash and the position where the entry was found in the hash is returned.
  63     If no entry with the specified key exists in the hash, then a negative value is returned
  64
  65 *   Lookup for entry with key: The key is provided as input. If an entry with the specified key is found in the hash (lookup hit),
  66     then the position of the entry is returned, otherwise (lookup miss) a negative value is returned.
  67
  68 The current hash implementation handles the key management only.
  69 The actual data associated with each key has to be managed by the user using a separate table that
  70 mirrors the hash in terms of number of entries and position of each entry,
  71 as shown in the Flow Classification use case describes in the following sections.
  72
  73 The example hash tables in the L2/L3 Forwarding sample applications defines which port to forward a packet to based on a packet flow identified by the five-tuple lookup.
  74 However, this table could also be used for more sophisticated features and provide many other functions and actions that could be performed on the packets and flows.
  75
  76 Implementation Details
  77 ----------------------
  78
  79 The hash table is implemented as an array of entries which is further divided into buckets,
  80 with the same number of consecutive array entries in each bucket.
  81 For any input key, there is always a single bucket where that key can be stored in the hash,
  82 therefore only the entries within that bucket need to be examined when the key is looked up.
  83 The lookup speed is achieved by reducing the number of entries to be scanned from the total
  84 number of hash entries down to the number of entries in a hash bucket,
  85 as opposed to the basic method of linearly scanning all the entries in the array.
  86 The hash uses a hash function (configurable) to translate the input key into a 4-byte key signature.
  87 The bucket index is the key signature modulo the number of hash buckets.
  88 Once the bucket is identified, the scope of the hash add,
  89 delete and lookup operations is reduced to the entries in that bucket.
  90
  91 To speed up the search logic within the bucket, each hash entry stores the 4-byte key signature together with the full key for each hash entry.
  92 For large key sizes, comparing the input key against a key from the bucket can take significantly more time than
  93 comparing the 4-byte signature of the input key against the signature of a key from the bucket.
  94 Therefore, the signature comparison is done first and the full key comparison done only when the signatures matches.
  95 The full key comparison is still necessary, as two input keys from the same bucket can still potentially have the same 4-byte hash signature,
  96 although this event is relatively rare for hash functions providing good uniform distributions for the set of input keys.
  97
  98 Use Case: Flow Classification
  99 -----------------------------
 100
 101 Flow classification is used to map each input packet to the connection/flow it belongs to.
 102 This operation is necessary as the processing of each input packet is usually done in the context of their connection,
 103 so the same set of operations is applied to all the packets from the same flow.
 104
 105 Applications using flow classification typically have a flow table to manage, with each separate flow having an entry associated with it in this table.
 106 The size of the flow table entry is application specific, with typical values of 4, 16, 32 or 64 bytes.
 107
 108 Each application using flow classification typically has a mechanism defined to uniquely identify a flow based on
 109 a number of fields read from the input packet that make up the flow key.
 110 One example is to use the DiffServ 5-tuple made up of the following fields of the IP and transport layer packet headers:
 111 Source IP Address, Destination IP Address, Protocol, Source Port, Destination Port.
 112
 113 The DPDK hash provides a generic method to implement an application specific flow classification mechanism.
 114 Given a flow table implemented as an array, the application should create a hash object with the same number of entries as the flow table and
 115 with the hash key size set to the number of bytes in the selected flow key.
 116
 117 The flow table operations on the application side are described below:
 118
 119 *   Add flow: Add the flow key to hash.
 120     If the returned position is valid, use it to access the flow entry in the flow table for adding a new flow or
 121     updating the information associated with an existing flow.
 122     Otherwise, the flow addition failed, for example due to lack of free entries for storing new flows.
 123
 124 *   Delete flow: Delete the flow key from the hash. If the returned position is valid,
 125     use it to access the flow entry in the flow table to invalidate the information associated with the flow.
 126
 127 *   Lookup flow: Lookup for the flow key in the hash.
 128     If the returned position is valid (flow lookup hit), use the returned position to access the flow entry in the flow table.
 129     Otherwise (flow lookup miss) there is no flow registered for the current packet.
 130
 131 References
 132 ----------
 133
 134 *   Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition), 1998, Addison-Wesley Professional