 |
P4C
The P4 Compiler
|
|
P4C
The P4 Compiler
|
Classes | |
| struct | Use |
Public Member Functions | |
| TableFormat (const LayoutOption &l, const IXBar::Use *mi, const IXBar::Use *phi, const IR::MAU::Table *t, const bitvec im, bool gl, FindPayloadCandidates &fpc, const PhvInfo &phv) | |
| bool | find_format (Use *u) |
| void | verify () |
Static Public Member Functions | |
| static TableFormat * | create (const LayoutOption &l, const IXBar::Use *mi, const IXBar::Use *phi, const IR::MAU::Table *t, const bitvec im, bool gl, FindPayloadCandidates &fpc, const PhvInfo &phv) |
Protected Member Functions | |
| virtual void | allocate_full_fits (int width_sect, int group=-1) |
| virtual bool | allocate_overhead (bool alloc_match=false) |
| virtual bool | analyze_layout_option () |
| int | bits_necessary (type_t type) const |
| virtual void | choose_ghost_bits (safe_vector< std::pair< IXBar::Use::Byte, bitvec > > &potential_ghost) |
| void | fill_out_use (int group, const safe_vector< ByteInfo > &alloced, bitvec &version_loc) |
| virtual void | get_potential_ghost_byte (const IXBar::Use::Byte byte, const std::map< cstring, bitvec > &hash_masks, safe_vector< std::pair< IXBar::Use::Byte, bitvec > > &potential_ghost) |
| bool | initialize_byte (int byte_offset, int width_sect, const ByteInfo &info, safe_vector< ByteInfo > &alloced, bitvec &byte_attempt, bitvec &bit_attempted) |
Protected Attributes | |
| safe_vector< int > | full_match_groups_per_RAM |
| int | ghost_bits_count = 0 |
| safe_vector< ByteInfo > | ghost_bytes |
| bitvec | interleaved_match_byte_use |
| const LayoutOption & | layout_option |
| bitvec | match_byte_use |
| safe_vector< ByteInfo > | match_bytes |
| const IXBar::Use * | match_ixbar |
| safe_vector< int > | overhead_groups_per_RAM |
| Which RAM sections contain the match groups. | |
| safe_vector< int > | search_bus_per_width |
| Specifically which search bus coordinates to which RAM. | |
| safe_vector< int > | shared_groups_per_RAM |
| safe_vector< IXBar::Use::Byte > | single_match |
| const IR::MAU::Table * | tbl |
| bitvec | total_use |
| Use * | use = nullptr |
|
protectedvirtual |
Given a number of overhead entries, this algorithm determines how many match groups can fully fit into that particular RAM. It both allocates match and version, as both of those have to be placed in order for the entry to fit.
For wide matches, this ensures that the entirety of the search bus is placed, but not necessarily version, as version can be placed in any of the wide match sections.
|
protectedvirtual |
Allocate all overhead data that could head to match central. This includes the following information, if needed:
The current algorithm just packs as close to the bottom as it can, and does not leave any holes to put match data in. This could be optimized to pack match data.
|
protectedvirtual |
The goal of this code is to determine how to initial divide up the match data and the overhead, and which RAM correspond to which input xbar group.
If you look at section 6.2.3 Exact Match Row Vertical/Horizontal (VH) Xbars, one can the inputs to an individual RAM line. There are two search buses per line, which themselves are 128 bits wide, the same as an individual RAM row. Each search bus can select from one of 8 crossbar groups that come from the input crossbar. Thus, the number of input xbars groups needed is the number of search buses needed. (This is not entirely true, as in ATCAM a single xbar bytes is actually in multiple places on the RAM. This information is tracked through the search_bus field in each IXBar::Byte)
Thus the algorithm is divided into two types, skinny and wide. Skinny means that only one search bus is required, while wide means multiple search buses are required.
The analyze option assigns both a number of overhead entries per RAM as well as a search bus assigned to each width. Thus only bytes with that search_bus value can be found at that particular location.
|
protectedvirtual |
Ghost bits are bits that are used in the hash to find the location of the entry, but are not contained within the match. It is an optimization to save space on match bits.
The number of bits one can ghost is the minimum number of bits used to select a RAM row and a RAM on the hash bus. One automatically gets 10 bits, for the 10 bits of hash that determines the RAM row. Extra bits can be ghosted by the log2size of the minimum way.
This algorithm chooses which bits to ghost. If the match requires multiple search buses then the search bus which is going to have the overhead is preferred. Match requirements that don't require the full byte are preferred over bytes that require the full 8 bits. That way, the algorithm can eliminate more match bytes.
For examples, say the match has the following, which were all in separate PHV containers: 3 3 bit fields 1 1 bit field 4 8 bit fields
It would be optimal to ghost off the 3 3 bit fields, and the 1 bit fields, as it would remove 4 total PHV bytes to match on.
Ghost bits selection now considers the mask specified with the @hash_mask
annotation: bits that are masked off through the annotation are not selected
to be part of ghost bits.
|
protected |
This fills out the use object, as well as the global structures for keeping track of the format. This does this for both match and version information.
| bool TableFormat::find_format | ( | Use * | u | ) |
The algorithm find_format is to determine how to best pack the RAMs of match tables. * For any table using SRAMs only (i.e. exact match/atcam), this means determining how the RAM line is filled. For tables using the TCAMs, (i.e. ternary), this is specifically for the ternary indirect packing.
The RAM is packed with two classes of information, match data and overhead. Match data is anything that is to be directly compared with packet data. Overhead is everything else. Overhead consists of anything that could go to match central as well as version bits.
When an entry hits within a table, the lower 64 bits of the RAM (or in the case of a wide match, one of the RAMs), are sent to match central for further processing. Thus any information that is needed by match central for later processing is considered overhead, and must fit within the lower 64 bits.
The exception to the previous paragraph is what we call version bits. These are bits that are matched not as part of the packet, but as a way to ensure that an entry is valid, and that all data is atomically written into the RAM. Version bits are then appended on before the match, and thus can be anywhere within the RAM line.
Data from the packet comes in through the input xbar. The algorithm is as follows.
The constraints for these individual pieces will be described above the function which are part of the algorithm.
FIXME: Noted weaknesses in the algorithm to address in the future:
|
protectedvirtual |
Adds the specified byte along with its mask to vector potential_ghost.
The mask originates from the @hash_mask() annotation specified with the match key in the P4 code. Bits that are masked off by @hash_mask() are excluded from the list of ghost bits candidates.
When @hash_mask() is not specified, the mask is set to byte.bit_use, allowing all bits to be candidates for ghost bits selection.
|
protected |
Save information on a byte by byte basis so that fill out use can correctly be used. Note that each individual byte from PHV requires an individual byte in the match format, and cannot be reused by a separate entry.
|
protected |
Which RAM sections contain the match groups.
Which RAM sections contain overhead info
1.12.0