The Format String is a string that is used to configure the parameters of the CAM. It is used for both hardware generation and by the software TCAM algorithms. The amount of hardware resources required for a TCAM depends on the key width, response width, priority width, the number of entries, and the complexity of the format string. The hardware generation needs to know for which bit positions it should generate range logic. The software uses the format string to validate input arguments such as the key and mask. For example, for a prefix field, the mask should have consecutive ones and zeroes and for a range field the key bits are used for the min. value and the mask bits are used for the max. value. The software also uses the format string to sort keys to the right memories based on available hash bits in the key.
The format string is composed by VitisNetP4. The information in the format string is extracted from the P4 code. For standalone usage, the format string needs to be created explicitly.
The string describes the format of all keys and masks. A key consists of several fields and the format string specifies the location and size of the fields. In the string, fields are separated by a colon ':'. The string is read left to right. The first field corresponds to the least significant bit of the key. The key is specified as little-endian. Each field is specified with a field length and field type. There are no alignment restrictions for the fields. The location, type, number, and size of fields is fully flexible.
- b - bit field
- The field mask is either all zeroes or all ones.
field len = 1...128 bit, complexity = 2.
- t - ternary field
- The field mask can have any value.
field len = 2..16 bit, complexity = 2^field_len.
- c - constant bit field
- The mask is all ones.
field len = 1...128 bit, complexity = 1.
- u - unused bit field
- The mask is all zeroes.
field len = 1...128 bit, complexity = 1.
- p - prefix field
- The mask has consecutive ones (MSBs) followed by consecutive zeroes
(LSBs).
field len = 1...128 bit, complexity = field_len + 1.
- r - range field
- Matching is done with logic comparators within start/end
values.
field len = 1..16 bit, complexity = 2, max 8 ranges per format.
For example, the format "16r:16r:64p:64p:48b:48b" contains: 2 x 16-bit range fields for port numbers, 2 x 64-bit prefix fields for IPv6 addresses and 2 x 48-bit fields for MAC addresses. The 16r field is located in the 16 least significant bits of the key.
The processing required by the software depends on the complexity of the string. The software keeps potential mask permutations in its memory and tries to sort keys according to the permutations. The more permutations, the more processing is required. Ternary and prefix fields are particularly computationally heavy. A prefix field multiplies the number of permutations with its prefix length, a ternary field multiplies the number of permutations with a power of two of its length and a binary field multiples the number of permutations by two. The complexity is a combination of the number of fields and the type of the field.
For example, a format string with three binary fields has a complexity of 2*2*2 = 8.
A format string with one binary field and one ternary field of length 4 has a complexity of 2 * 2^4 = 32.
A format string with one constant field, one binary field and one prefix field of length 32 has a complexity of 1 * 2 * (32 + 1) = 66.