#ifndef cl_inc_mac_lookup_table_h #define cl_inc_mac_lookup_table_h /* Cesar project {{{ * * Copyright (C) 2008 Spidcom * * <<>> * * }}} */ /** * \file cl/inc/mac_lookup_table.h * \brief MAC lookup table private header. * \ingroup cl * * The MAC lookup table relies on the 512 bytes block allocator module. In * fact, all entries are stored on those blocks. * * An entry is 8 bytes long: * - 48 bits for the MAC address field, * - 16 bits for the extra information field. * * A block can contain, at most, 64 entries. * * The non-sorted format simply stored all the new entries in the blocks, * adding more blocks if needed. But this format is not optimized to find a * MAC address in all the entries. * * The indexed format use the same data structure as the non-sorted one with * some enhancements. First, it sorts the table. Then it present the whole * linked blocks as a big table. To achieve this, it create a small index * table on the last block (sometimes it creates a new block to store it): * each entry of this index contains the first entry of each linked blocks. * The dichotomy search algorithm can be used on this index to have an * optimized search on the table. */ /** * A data entry of the MAC lookup table. * The entry contains the MAC address (stored on 48 bits) field and the extra * information field (stored on 16 bits). */ struct mac_lookup_data_entry_t { /** The MAC address. */ u64 mac_address: 48; /** The extra informations. */ u64 extra_info: 16; }; typedef struct mac_lookup_data_entry_t mac_lookup_data_entry_t; /** * Maximum number of entries per block. */ #define MAX_ENTRIES_PER_BLOCK (BLK_SIZE / sizeof (mac_lookup_data_entry_t)) /** * Maximum number of entries of the whole table. * It is limited by the size of indexed table which must fit on a 512 bytes * block. */ #define MAX_ENTRIES_PER_TABLE \ ((BLK_SIZE - sizeof (mac_lookup_block_header_t *) - sizeof (uint)) \ / sizeof (mac_lookup_data_entry_t *) * MAX_ENTRIES_PER_BLOCK) /** * Data block header of the lookup table. * If you use this header, you are accessing the non-sorted version of the MAC * lookup table. * This header is repeated at the beginning of each linked block (512 bytes * long) of data. The header of the first block contains some additional * informations for optimization purpose (those informations are not reported * on the other block header entries!). It must respect \c blk_t structure. * The block of data contains some \c mac_lookup_data_entry_t. */ struct mac_lookup_block_header_t { /** The next data block header. */ struct mac_lookup_block_header_t *next; /** The beginning of the entries of data of this block. */ struct mac_lookup_data_entry_t *data; /** Total count of entries in all the linked blocks. It is used to compute * the position of the next entry to add to the table. It is only filed in * the first block. */ uint total_entry_count; /** Last allocated block of data. It is used to prevent scanning the whole * table to access the last allocated block.It is only filed in the first * block. */ struct mac_lookup_block_header_t *last_allocated_header; }; /** * The indexed MAC lookup table. * If you use this structure, you are accessing the indexed version of the MAC * lookup table and you can not change the MAC address of the entries anymore. * This table tries to hide the way data are stored (on linked blocks). * Instead, it presents them as a one dimensional array (of one line and one * column for each entry). * This table is stored on the last linked block. It may required to add a * block to have enough space to store it. */ struct mac_lookup_table_t { /** A pointer to the first block header. It is useful to access the \a * total_entry_count to know the number of entries in the whole table. */ mac_lookup_block_header_t *first; /** The size of the \a data_entry table (not the count of entries of the * whole indexed table). */ uint data_entry_size; /** A table containing pointers to the first data entry of each block of * the MAC lookup table. */ mac_lookup_data_entry_t *data_entry[]; }; BEGIN_DECLS /** * Swap two data entries in the indexed MAC lookup table. * \param table an indexed MAC lookup table. * \param pos1 the first position of a data entry to swap. * \param pos2 the second position of a data entry to swap. * * This function is used to sort the indexed table. */ void mac_lookup_table_swap (mac_lookup_table_t* table, uint pos1, uint pos2); /** * Find an entry corresponding to the MAC address into the MAC lookup table. * \param table the MAC lookup table in which to search the MAC address. * \param mac_address the MAC address of the entry to lookup for. * \return a pointer to the data entry if found, otherwise, returns NULL. * * This function is internal because it returns a pointer for a direct access * to the data entry. */ mac_lookup_data_entry_t * mac_lookup_table_find (mac_lookup_table_t *table, mac_t mac_address); /** * Copy entries with or without specific extra information from an indexed * table to a non-sorted one. * \param indexed_table the indexed MAC lookup table. * \param non_sorted_table the non-sorted MAC lookup table. * \param mask the mask to apply to the extra information for matching only * part of the extra information (useful if you have stored more than one * information in the extra information field). * \param value the value to match against a part of the extra information. * \param negate negate matching condition: * - true will negate the matching condition (by adding a !), * - false will not negate the matching condition. * \return the count of copied entries to \a non_sorted_table. */ uint mac_lookup_table_copy_conditional (mac_lookup_table_t *indexed_table, mac_lookup_block_header_t *non_sorted_table, u16 mask, u16 value, bool negate); /** * Get the data entry at a desired position of a MAC lookup table. * \param table the indexed MAC lookup table. * \param position the position to get. * \return the data entry located at \a position. */ static inline mac_lookup_data_entry_t * mac_lookup_get_data_entry (mac_lookup_table_t *table, uint position) { /* Check parameters. */ dbg_assert (table); dbg_assert (table->first); dbg_assert (table->data_entry); dbg_assert (position < table->first->total_entry_count); /* Get corresponding block position. */ uint block_position = position / MAX_ENTRIES_PER_BLOCK; dbg_assert (block_position < table->data_entry_size); dbg_assert (table->data_entry[block_position]); /* Return entry. */ return &(table->data_entry[block_position] [position % MAX_ENTRIES_PER_BLOCK]); } /** * Get MAC address at a desired position of a MAC lookup table. * \param table the indexed MAC lookup table. * \param position the position to get. * \return the MAC address located at \a position. */ static inline mac_t mac_lookup_get_mac__ (mac_lookup_table_t *table, uint position) { /* Get entry. */ mac_lookup_data_entry_t *result = mac_lookup_get_data_entry (table, position); dbg_assert (result); /* Return MAC address field. */ return result->mac_address; } /** * Compare two MAC addresses of the indexed MAC lookup table. * \param table an indexed MAC lookup table. * \param pos1 the first position of a data entry to compare. * \param pos2 the second position of a data entry to compare. * \return true if the MAC address of the data entry at \c pos1 is less than the * one at \c pos2, otherwise, it returns false. */ static inline bool mac_lookup_table_compare (mac_lookup_table_t* table, uint pos1, uint pos2) { /* Check parameter. */ dbg_assert (table); /* Compare MAC values. */ if (mac_lookup_get_mac__ (table, pos1) < mac_lookup_get_mac__ (table, pos2)) return true; else return false; } END_DECLS #endif /* cl_inc_mac_lookup_table_h */