provides the set of actions to be applied on the current packet,
as well as the next hop for the packet, which can be either another table, an output port or packet drop.
-An example of packet processing pipeline is presented in Figure 32:
+An example of packet processing pipeline is presented in :numref:`figure_figure32`:
-.. _pg_figure_32:
+.. _figure_figure32:
-**Figure 32 Example of Packet Processing Pipeline where Input Ports 0 and 1 are Connected with Output Ports 0, 1 and 2 through Tables 0 and 1**
+.. figure:: img/figure32.*
-.. Object_1_png has been renamed
+ Example of Packet Processing Pipeline where Input Ports 0 and 1
+ are Connected with Output Ports 0, 1 and 2 through Tables 0 and 1
-|figure32|
Port Library Design
-------------------
to just the set of keys currently in the identified table bucket.
The performance of the hash table lookup operation is greatly improved,
-provided that the table keys are evenly distributed amongst the hash table buckets,
+provided that the table keys are evenly distributed among the hash table buckets,
which can be achieved by using a hash function with uniform distribution.
The rule to map a key to its bucket can simply be to use the key signature (modulo the number of table buckets) as the table bucket ID:
this means that all the keys that end up in the same hash table bucket have the lower *n_bits* of their signature identical.
In order to reduce the number of keys in the same bucket (collisions), the number of hash table buckets needs to be increased.
-In packet processing context, the sequence of operations involved in hash table operations is described in Figure 33:
+In packet processing context, the sequence of operations involved in hash table operations is described in :numref:`figure_figure33`:
-.. _pg_figure_33:
+.. _figure_figure33:
-**Figure 33 Sequence of Steps for Hash Table Operations in a Packet Processing Context**
+.. figure:: img/figure33.*
+
+ Sequence of Steps for Hash Table Operations in a Packet Processing Context
-|figure33|
Hash Table Use Cases
When a key needs to be picked and dropped, the first candidate for drop, i.e. the current LRU key, is always picked.
The LRU logic requires maintaining specific data structures per each bucket.
-#. **Extendible Bucket Hash Table.**
+#. **Extendable Bucket Hash Table.**
The bucket is extended with space for 4 more keys.
This is done by allocating additional memory at table initialization time,
which is used to create a pool of free keys (the size of this pool is configurable and always a multiple of 4).
when the key to be deleted is the only key that was used within its group of 4 keys at that time.
On key lookup operation, if the current bucket is in extended state and a match is not found in the first group of 4 keys,
the search continues beyond the first group of 4 keys, potentially until all keys in this bucket are examined.
- The extendible bucket logic requires maintaining specific data structures per table and per each bucket.
+ The extendable bucket logic requires maintaining specific data structures per table and per each bucket.
.. _pg_table_23:
-**Table 23 Configuration Parameters Specific to Extendible Bucket Hash Table**
+**Table 23 Configuration Parameters Specific to Extendable Bucket Hash Table**
+---+---------------------------+--------------------------------------------------+
| # | Parameter | Details |
Configurable Key Size Hash Table
""""""""""""""""""""""""""""""""
-Figure 34, Table 25 and Table 26 detail the main data structures used to implement configurable key size hash tables (either LRU or extendable bucket,
+:numref:`figure_figure34`, Table 25 and Table 26 detail the main data structures used to implement configurable key size hash tables (either LRU or extendable bucket,
either with pre-computed signature or "do-sig").
-.. _pg_figure_34:
+.. _figure_figure34:
-**Figure 34 Data Structures for Configurable Key Size Hash Tables**
+.. figure:: img/figure34.*
-.. image65_png has been renamed
+ Data Structures for Configurable Key Size Hash Tables
-|figure34|
.. _pg_table_25:
| | | | | |
+---+-------------------------+------------------------------+---------------------------+-------------------------------+
| 2 | Bucket extensions array | n_buckets_ext (configurable) | 32 | This array is only created |
-| | | | | for extendible bucket tables. |
+| | | | | for extendable bucket tables. |
| | | | | |
+---+-------------------------+------------------------------+---------------------------+-------------------------------+
| 3 | Key array | n_keys | key_size (configurable) | Keys added to the hash table. |
| | | | Entry 0 stores the index (0 .. 3) of the MRU key, while entry 3 |
| | | | stores the index of the LRU key. |
| | | | |
-| | | | For extendible bucket tables, this field represents the next |
+| | | | For extendable bucket tables, this field represents the next |
| | | | pointer (i.e. the pointer to the next group of 4 keys linked to |
| | | | the current bucket). The next pointer is not NULL if the bucket |
| | | | is currently extended or NULL otherwise. |
+---+------------------+--------------------+------------------------------------------------------------------+
-Figure 35 and Table 27 detail the bucket search pipeline stages (either LRU or extendable bucket,
+:numref:`figure_figure35` and Table 27 detail the bucket search pipeline stages (either LRU or extendable bucket,
either with pre-computed signature or "do-sig").
For each pipeline stage, the described operations are applied to each of the two packets handled by that stage.
-.. _pg_figure_35:
+.. _figure_figure35:
+
+.. figure:: img/figure35.*
-**Figure 35 Bucket Search Pipeline for Key Lookup Operation (Configurable Key Size Hash Tables)**
+ Bucket Search Pipeline for Key Lookup Operation (Configurable Key Size Hash
+ Tables)
-|figure35|
.. _pg_table_27:
| | | |
+------------+------------------------------------------+-------------------+
-The pseudo-code is displayed in Figure 36.
-
-.. _pg_figure_36:
-**Figure 36 Pseudo-code for match, match_many and match_pos**
+The pseudo-code for match, match_many and match_pos is::
match = (0xFFFELLU >> mask) & 1;
Single Key Size Hash Tables
"""""""""""""""""""""""""""
-Figure 37, Figure 38, Table 30 and 31 detail the main data structures used to implement 8-byte and 16-byte key hash tables
+:numref:`figure_figure37`, :numref:`figure_figure38`, Table 30 and 31 detail the main data structures used to implement 8-byte and 16-byte key hash tables
(either LRU or extendable bucket, either with pre-computed signature or "do-sig").
-.. _pg_figure_37:
+.. _figure_figure37:
-**Figure 37 Data Structures for 8-byte Key Hash Tables**
+.. figure:: img/figure37.*
-.. image66_png has been renamed
+ Data Structures for 8-byte Key Hash Tables
-|figure37|
-.. _pg_figure_38:
+.. _figure_figure38:
-**Figure 38 Data Structures for 16-byte Key Hash Tables**
+.. figure:: img/figure38.*
-.. image67_png has been renamed
+ Data Structures for 16-byte Key Hash Tables
-|figure38|
.. _pg_table_30:
| | | | | |
+---+-------------------------+------------------------------+----------------------+------------------------------------+
| 2 | Bucket extensions array | n_buckets_ext (configurable) | *8-byte key size:* | This array is only created for |
-| | | | | extendible bucket tables. |
+| | | | | extendable bucket tables. |
| | | | | |
| | | | 64 + 4 x entry_size | |
| | | | | |
+===+===============+====================+===============================================================================+
| 1 | Valid | 8 | Bit X (X = 0 .. 3) is set to 1 if key X is valid or to 0 otherwise. |
| | | | |
-| | | | Bit 4 is only used for extendible bucket tables to help with the |
+| | | | Bit 4 is only used for extendable bucket tables to help with the |
| | | | implementation of the branchless logic. In this case, bit 4 is set to 1 if |
| | | | next pointer is valid (not NULL) or to 0 otherwise. |
| | | | |
| | | | stored as array of 4 entries of 2 bytes each. Entry 0 stores the index |
| | | | (0 .. 3) of the MRU key, while entry 3 stores the index of the LRU key. |
| | | | |
-| | | | For extendible bucket tables, this field represents the next pointer (i.e. |
+| | | | For extendable bucket tables, this field represents the next pointer (i.e. |
| | | | the pointer to the next group of 4 keys linked to the current bucket). The |
| | | | next pointer is not NULL if the bucket is currently extended or NULL |
| | | | otherwise. |
either with pre-computed signature or "do-sig").
For each pipeline stage, the described operations are applied to each of the two packets handled by that stage.
-.. _pg_figure_39:
+.. _figure_figure39:
-**Figure 39 Bucket Search Pipeline for Key Lookup Operation (Single Key Size Hash Tables)**
+.. figure:: img/figure39.*
+
+ Bucket Search Pipeline for Key Lookup Operation (Single Key Size Hash
+ Tables)
-|figure39|
.. _pg_table_32:
#. The pipelined version of the bucket search algorithm is executed only if there are at least 5 packets in the burst of input packets.
If there are less than 5 packets in the burst of input packets, a non-optimized implementation of the bucket search algorithm is executed.
-#. For extendible bucket hash tables only,
+#. For extendable bucket hash tables only,
once the pipelined version of the bucket search algorithm has been executed for all the packets in the burst of input packets,
the non-optimized implementation of the bucket search algorithm is also executed for any packets that did not produce a lookup hit,
but have the bucket in extended state.
The threads performing table entry add/delete operations send table update requests to the reader (typically through message passing queues),
which does the actual table updates and then sends the response back to the request initiator.
-#. **Single writer thread performing table entry add/delete operations and multiple reader threads that performtable lookup operations with read-only access to the table entries.**
+#. **Single writer thread performing table entry add/delete operations and multiple reader threads that perform table lookup operations with read-only access to the table entries.**
The reader threads use the main table copy while the writer is updating the mirror copy.
Once the writer update is done, the writer can signal to the readers and busy wait until all readers swaps between the mirror copy (which now becomes the main copy) and
the mirror copy (which now becomes the main copy).
with all the implementations sharing the same API: pure SW implementation (no acceleration), implementation using accelerator A, implementation using accelerator B, etc.
The selection between these implementations could be done at build time or at run-time (recommended), based on which accelerators are present in the system,
with no application changes required.
-
-.. |figure33| image:: img/figure33.png
-
-.. |figure35| image:: img/figure35.png
-
-.. |figure39| image:: img/figure39.png
-
-.. |figure34| image:: img/figure34.png
-
-.. |figure32| image:: img/figure32.png
-
-.. |figure37| image:: img/figure37.png
-
-.. |figure38| image:: img/figure38.png
git.droids-corp.org / dpdk.git / blobdiff