1.. SPDX-License-Identifier: BSD-3-Clause 2 Copyright(c) 2010-2015 Intel Corporation. 3 Copyright(c) 2018 Arm Limited. 4 5.. _Hash_Library: 6 7Hash Library 8============ 9 10The DPDK provides a Hash Library for creating hash table for fast lookup. 11The hash table is a data structure optimized for searching through a set of entries that are each identified by a unique key. 12For increased performance the DPDK Hash requires that all the keys have the same number of bytes which is set at the hash creation time. 13 14Hash API Overview 15----------------- 16 17The main configuration parameters for the hash are: 18 19* Total number of hash entries 20 21* Size of the key in bytes 22 23* An extra flag used to describe additional settings, for example the multithreading mode of operation (as will be described later) 24 25The hash also allows the configuration of some low-level implementation related parameters such as: 26 27* Hash function to translate the key into a bucket index 28 29The main methods exported by the hash are: 30 31* Add entry with key: The key is provided as input. If a new entry is successfully added to the hash for the specified key, 32 or there is already an entry in the hash for the specified key, then the position of the entry is returned. 33 If the operation was not successful, for example due to lack of free entries in the hash, then a negative value is returned; 34 35* Delete entry with key: The key is provided as input. If an entry with the specified key is found in the hash, 36 then the entry is removed from the hash and the position where the entry was found in the hash is returned. 37 If no entry with the specified key exists in the hash, then a negative value is returned 38 39* 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), 40 then the position of the entry is returned, otherwise (lookup miss) a negative value is returned. 41 42Apart from these methods explained above, the API provides the user with few more options: 43 44* Add / lookup / delete with key and precomputed hash: Both the key and its precomputed hash are provided as input. This allows 45 the user to perform these operations faster, as hash is already computed. 46 47* Add / lookup with key and data: A pair of key-value is provided as input. This allows the user to store 48 not only the key, but also data which may be either a 8-byte integer or a pointer to external data (if data size is more than 8 bytes). 49 50* Combination of the two options above: User can provide key, precomputed hash and data. 51 52* Ability to not free the position of the entry in the hash upon calling delete. This is useful for multi-threaded scenarios where 53 readers continue to use the position even after the entry is deleted. 54 55Also, the API contains a method to allow the user to look up entries in bursts, achieving higher performance 56than looking up individual entries, as the function prefetches next entries at the time it is operating 57with the first ones, which reduces significantly the impact of the necessary memory accesses. 58 59 60The actual data associated with each key can be either managed by the user using a separate table that 61mirrors the hash in terms of number of entries and position of each entry, 62as shown in the Flow Classification use case describes in the following sections, 63or stored in the hash table itself. 64 65The 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. 66However, 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. 67 68Multi-process support 69--------------------- 70 71The hash library can be used in a multi-process environment. 72The only function that can only be used in single-process mode is rte_hash_set_cmp_func(), which sets up 73a custom compare function, which is assigned to a function pointer (therefore, it is not supported in 74multi-process mode). 75 76 77Multi-thread support 78--------------------- 79 80The hash library supports multithreading, and the user specifies the needed mode of operation at the creation time of the hash table 81by appropriately setting the flag. In all modes of operation lookups are thread-safe meaning lookups can be called from multiple 82threads concurrently. 83 84For concurrent writes, and concurrent reads and writes the following flag values define the corresponding modes of operation: 85 86* If the multi-writer flag (RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD) is set, multiple threads writing to the table is allowed. 87 Key add, delete, and table reset are protected from other writer threads. With only this flag set, readers are not protected from ongoing writes. 88 89* If the read/write concurrency (RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY) is set, multithread read/write operation is safe 90 (i.e., application does not need to stop the readers from accessing the hash table until writers finish their updates. Readers and writers can operate on the table concurrently). 91 The library uses a reader-writer lock to provide the concurrency. 92 93* In addition to these two flag values, if the transactional memory flag (RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT) is also set, 94 the reader-writer lock will use hardware transactional memory to guarantee thread safety as long as it is supported by the hardware (for example the Intel® TSX support). 95 If the platform supports Intel® TSX, it is advised to set the transactional memory flag, as this will speed up concurrent table operations. 96 Otherwise concurrent operations will be slower because of the overhead associated with the software locking mechanisms. 97 98* If lock free read/write concurrency (RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) is set, read/write concurrency is provided without using reader-writer lock. 99 For platforms (ex: current Arm based platforms), that do not support transactional memory, it is advised to set this flag to achieve greater scalability in performance. 100 101* If, do not free on delete (RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL) flag is set, the position of the entry in the hash is not freed upon calling delete. This flag is enabled 102 by default when lock free read/write concurrency is set. The application should free the position after all the readers have stopped referencing the position. 103 Where required, the application can make use of RCU mechanisms to determine when the readers have stopped referencing the position. 104 105Implementation Details 106---------------------- 107 108The hash table has two main tables: 109 110* First table is an array of entries which is further divided into buckets, 111 with the same number of consecutive array entries in each bucket. Each entry contains the computed primary 112 and secondary hashes of a given key (explained below), and an index to the second table. 113 114* The second table is an array of all the keys stored in the hash table and its data associated to each key. 115 116The hash library uses the cuckoo hash method to resolve collisions. 117For any input key, there are two possible buckets (primary and secondary/alternative location) 118where that key can be stored in the hash, therefore only the entries within those bucket need to be examined 119when the key is looked up. 120The lookup speed is achieved by reducing the number of entries to be scanned from the total 121number of hash entries down to the number of entries in the two hash buckets, 122as opposed to the basic method of linearly scanning all the entries in the array. 123The hash uses a hash function (configurable) to translate the input key into a 4-byte key signature. 124The bucket index is the key signature modulo the number of hash buckets. 125 126Once the buckets are identified, the scope of the hash add, 127delete and lookup operations is reduced to the entries in those buckets (it is very likely that entries are in the primary bucket). 128 129To 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. 130For large key sizes, comparing the input key against a key from the bucket can take significantly more time than 131comparing the 4-byte signature of the input key against the signature of a key from the bucket. 132Therefore, the signature comparison is done first and the full key comparison done only when the signatures matches. 133The full key comparison is still necessary, as two input keys from the same bucket can still potentially have the same 4-byte hash signature, 134although this event is relatively rare for hash functions providing good uniform distributions for the set of input keys. 135 136Example of lookup: 137 138First of all, the primary bucket is identified and entry is likely to be stored there. 139If signature was stored there, we compare its key against the one provided and return the position 140where it was stored and/or the data associated to that key if there is a match. 141If signature is not in the primary bucket, the secondary bucket is looked up, where same procedure 142is carried out. If there is no match there either, key is considered not to be in the table. 143 144Example of addition: 145 146Like lookup, the primary and secondary buckets are identified. If there is an empty slot in 147the primary bucket, primary and secondary signatures are stored in that slot, key and data (if any) are added to 148the second table and an index to the position in the second table is stored in the slot of the first table. 149If there is no space in the primary bucket, one of the entries on that bucket is pushed to its alternative location, 150and the key to be added is inserted in its position. 151To know where the alternative bucket of the evicted entry is, the secondary signature is looked up and alternative bucket index 152is calculated from doing the modulo, as seen above. If there is room in the alternative bucket, the evicted entry 153is stored in it. If not, same process is repeated (one of the entries gets pushed) until a non full bucket is found. 154Notice that despite all the entry movement in the first table, the second table is not touched, which would impact 155greatly in performance. 156 157In the very unlikely event that table enters in a loop where same entries are being evicted indefinitely, 158key is considered not able to be stored. 159With random keys, this method allows the user to get around 90% of the table utilization, without 160having to drop any stored entry (LRU) or allocate more memory (extended buckets). 161 162 163Example of deletion: 164 165Similar to lookup, the key is searched in its primary and secondary buckets. If the key is found, the bucket 166entry is marked as an empty slot. If the hash table was configured with 'no free on delete' or 'lock free read/write concurrency', 167the position of the key is not freed. It is the responsibility of the user to free the position while making sure that 168readers are not referencing the position anymore. 169 170Entry distribution in hash table 171-------------------------------- 172 173As mentioned above, Cuckoo hash implementation pushes elements out of their bucket, 174if there is a new entry to be added which primary location coincides with their current bucket, 175being pushed to their alternative location. 176Therefore, as user adds more entries to the hash table, distribution of the hash values 177in the buckets will change, being most of them in their primary location and a few in 178their secondary location, which the later will increase, as table gets busier. 179This information is quite useful, as performance may be lower as more entries 180are evicted to their secondary location. 181 182See the tables below showing example entry distribution as table utilization increases. 183 184.. _table_hash_lib_1: 185 186.. table:: Entry distribution measured with an example table with 1024 random entries using jhash algorithm 187 188 +--------------+-----------------------+-------------------------+ 189 | % Table used | % In Primary location | % In Secondary location | 190 +==============+=======================+=========================+ 191 | 25 | 100 | 0 | 192 +--------------+-----------------------+-------------------------+ 193 | 50 | 96.1 | 3.9 | 194 +--------------+-----------------------+-------------------------+ 195 | 75 | 88.2 | 11.8 | 196 +--------------+-----------------------+-------------------------+ 197 | 80 | 86.3 | 13.7 | 198 +--------------+-----------------------+-------------------------+ 199 | 85 | 83.1 | 16.9 | 200 +--------------+-----------------------+-------------------------+ 201 | 90 | 77.3 | 22.7 | 202 +--------------+-----------------------+-------------------------+ 203 | 95.8 | 64.5 | 35.5 | 204 +--------------+-----------------------+-------------------------+ 205 206| 207 208.. _table_hash_lib_2: 209 210.. table:: Entry distribution measured with an example table with 1 million random entries using jhash algorithm 211 212 +--------------+-----------------------+-------------------------+ 213 | % Table used | % In Primary location | % In Secondary location | 214 +==============+=======================+=========================+ 215 | 50 | 96 | 4 | 216 +--------------+-----------------------+-------------------------+ 217 | 75 | 86.9 | 13.1 | 218 +--------------+-----------------------+-------------------------+ 219 | 80 | 83.9 | 16.1 | 220 +--------------+-----------------------+-------------------------+ 221 | 85 | 80.1 | 19.9 | 222 +--------------+-----------------------+-------------------------+ 223 | 90 | 74.8 | 25.2 | 224 +--------------+-----------------------+-------------------------+ 225 | 94.5 | 67.4 | 32.6 | 226 +--------------+-----------------------+-------------------------+ 227 228.. note:: 229 230 Last values on the tables above are the average maximum table 231 utilization with random keys and using Jenkins hash function. 232 233Use Case: Flow Classification 234----------------------------- 235 236Flow classification is used to map each input packet to the connection/flow it belongs to. 237This operation is necessary as the processing of each input packet is usually done in the context of their connection, 238so the same set of operations is applied to all the packets from the same flow. 239 240Applications using flow classification typically have a flow table to manage, with each separate flow having an entry associated with it in this table. 241The size of the flow table entry is application specific, with typical values of 4, 16, 32 or 64 bytes. 242 243Each application using flow classification typically has a mechanism defined to uniquely identify a flow based on 244a number of fields read from the input packet that make up the flow key. 245One example is to use the DiffServ 5-tuple made up of the following fields of the IP and transport layer packet headers: 246Source IP Address, Destination IP Address, Protocol, Source Port, Destination Port. 247 248The DPDK hash provides a generic method to implement an application specific flow classification mechanism. 249Given 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 250with the hash key size set to the number of bytes in the selected flow key. 251 252The flow table operations on the application side are described below: 253 254* Add flow: Add the flow key to hash. 255 If the returned position is valid, use it to access the flow entry in the flow table for adding a new flow or 256 updating the information associated with an existing flow. 257 Otherwise, the flow addition failed, for example due to lack of free entries for storing new flows. 258 259* Delete flow: Delete the flow key from the hash. If the returned position is valid, 260 use it to access the flow entry in the flow table to invalidate the information associated with the flow. 261 262* Free flow: Free flow key position. If 'no free on delete' or 'lock-free read/write concurrency' flags are set, 263 wait till the readers are not referencing the position returned during add/delete flow and then free the position. 264 RCU mechanisms can be used to find out when the readers are not referencing the position anymore. 265 266* Lookup flow: Lookup for the flow key in the hash. 267 If the returned position is valid (flow lookup hit), use the returned position to access the flow entry in the flow table. 268 Otherwise (flow lookup miss) there is no flow registered for the current packet. 269 270References 271---------- 272 273* Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition), 1998, Addison-Wesley Professional 274