跳转至

LPM

LPM,最长前缀匹配(Longest Prefix Match)
LPM库分为LPM4和LPM6两种，分别对应IPV4(32bit)和IPV6(128bit)
用于三层转发路由查找

LPM4

基于DIR-24-8算法，DPDK使用tbl24表和tbl8表
tbl24有2^24个表项，以牺牲内存来缩短查询时间
tbl8有2^8个表项，由于子网掩码长度超过24位情况较少，tbl8表个数也较少

lpm

表项结构

tbl24和tbl8共用同一个表项，定义如下

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
struct rte_lpm_tbl_entry {
    uint32_t next_hop    :24;
    uint32_t valid       :1;   /**< 有效表示. */
    /**
     * 对于tbl24:
     *  - valid_group == 0: next_hop是下一跳的索引
     *  - valid_group == 1: next_htp是tbl8表索引 
     * 对于tbl8:
     *  - valid_group表示该tbl8表是否被使用
     */
    uint32_t valid_group :1;
    uint32_t depth       :6; /**< Rule depth. */
};

LPM定义

C
1
2
3
4
5
6
struct rte_lpm {
    //tbl24表，固定2^256个
    struct rte_lpm_tbl_entry tbl24[RTE_LPM_TBL24_NUM_ENTRIES]__rte_cache_aligned; 
    //tbl8指针,创建时，指定个数
    struct rte_lpm_tbl_entry *tbl8; 
};

LPM创建

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#dpdk内部对lpm进行了一层封装
struct __rte_lpm {
    /* Exposed LPM data. */
    struct rte_lpm lpm;
    ...
    ...
};

#所有的__rte_lpm都存在一个TAILQ中
static struct rte_tailq_elem rte_lpm_tailq = {
    .name = "RTE_LPM",
};
EAL_REGISTER_TAILQ(rte_lpm_tailq)

#lpm的创建，删除实际都是在TAILQ中完成

LPM添加

  • 根据掩码长度计算范围
  • 若长度小于等于24，则在指定范围内插入记录(或更新记录)；
  • 若长度大于24，则遍历tbl8分配空间，计算范围插入记录；
  • 临时结构体赋值后，原子性写入

LPM删除

  • 查找，计算范围
  • 原子性清空结构体

LPM6

同LMP4
使用tbl24表和tbl8表两种表
由于IPv6地址是128bit，前24bit使用1个tbl24
后续108bit使用多级tbl8，13(104/8)级
一共最大可达14级。
lpm6

参考

官网 LPM4库
官网 LPM6库