vlan-mapping映射功能设计数据结构与算法娜个女孩博客-

一、功能需求

      vlan-mapping，比如A公司想蹭腾讯的服务，为了成本以及A公司和腾讯的服务都不受影响，有了vlan-mapping，映射对应的vlan，比如将A公司的网络接入B公司，但由于A和B的配置不同，不可能将其改为一样的配置，所以有了此需求，vlan映射，相当于网络映射。

二、 大致流程

三、详细需求

1、支持如下四种配置，单个，多个，连续，混合模式

CLI配置示例：

interface gigabitethernet 1/1

    vlan-mapping vlan 100 map-vlan 500                       //上行：将vlan 100映射为vlan 500  下行：将vlan 500映射为vlan 100

    vlan-mapping vlan 200,300 map-vlan 600,700

    vlan-mapping vlan 3-6 map-vlan 13-16

    vlan-mapping vlan 3-6,100,200 map-vlan 13-16,500,600

2、交换机接口支持配置80条vlan-maping配置，每条配置支持满配（4096个vlan）2048对vlan映射

3、CLI下发如上示列所示配置，data plane最后以映射关系存在shared_memory中，在报文转发时替换vlan tag。而CLI show配置时，是从control plane中的结构体中将配置恢复为如上示列所示（所以数据结构用——双链表，这样保证配置删除和恢复可靠性），比如配置是这样的vlan-mapping vlan 3-10 map-vlan 13-20，中途删除了vlan 4和vlan14的映射关系， ​​​​​​最后配置需要显示为， vlan-mapping vlan 3，5-10 map-vlan 13,15-20

4、在报文到来，有vlan-mapping配置时，需要查找映射的vlanid并对应替换vlan tag，查找速度快用——数组 + bitmap

额外：转发层的表项结构——都是hash桶的结构，求hash值，再对应的槽位，添加节点（节点是从统一的一个单链表pool拿过来的），当删除释放时，又将此节点放回单链表pool 

四、数据结构设计

#ifndef _VLAN_MAPPING_H
#define _VLAN_MAPPING_H
    
#include “./policyroute/policy_routemap_list.h”
    
/* Vlan-mapping */
    
#define VLAN_MAP_MAX_NUM            (4096)    
#define VLAN_MAP_BITMAP             (64)
#define VLAN_MAP_MAX_INDEX          (2048)    
#define VLAN_MAP_CONFIG_MAX         (80)

/* node of per config */
struct nsm_vlan_mapping {    
    u_int16_t cnt;                                                                 /* count pair */    
    u_int16_t coming_vlan[VLAN_MAP_MAX_NUM];        /* save all vlan-map, index: coming_vlan, value: mapped_vlan*/    
    u_int16_t coming_index[VLAN_MAP_MAX_INDEX];   /* for show config, record coming_vlan order. index id 0,1,2…*/
    u_int64_t coming_bitmap[VLAN_MAP_BITMAP];        /* use search; bitmap of coming_vlan*/
    u_int64_t mapped_bitmap[VLAN_MAP_BITMAP];       /* use search; bitmap of mapped_vlan*/
    struct list_head lists;    
}; //从访问速度、省内存，还有配置恢复考虑，用双向链表+数组+bitmap实现 

/* double-list head */
struct vlan_mapping_head {
    u_int8_t length;
    struct list_head lists;
}; 

/* init head */
void init_vlan_mapping_head(struct vlan_mapping_head *h);
/* create node */
struct nsm_vlan_mapping *vlan_mapping_create_node();    
/* Delete node */
void vlan_mapping_del_node(struct nsm_vlan_mapping *node);    
/* Delete all */
void nsm_unset_vlan_mapping_all(struct vlan_mapping_head *h);    
/* insert node */
int vlan_mapping_insert_node(struct vlan_mapping_head *h, u_int16_t cnt, u_int64_t coming_bitmap[], u_int64_t mapped_bitmap[], u_int16_t coming_index[], u_int16_t coming_vlan[]);
/* search node */
void vlan_mapping_search_list(struct vlan_mapping_head *h, u_int16_t coming_v[], u_int16_t mapped_v[], u_int16_t cnt);
/* convert bitmap */
void convert_vlan_mapping2bitmap(u_int16_t vlan_v[], u_int16_t cnt, u_int64_t vlan_bitmap[]);
/* check vlan characters len*/
int check_vlan_mapping_characters_len(char *vlan_coming, char *vlan_mapped);     
/* check illegal characters */
int check_illegal_characters(char *vlan_coming, char *vlan_mapped); 
/* check vlan id repetiton */    
int check_vlan_id_repetition(u_int16_t vlan_coming[], u_int16_t vlan_mapped[], u_int16_t vlan_num);
/* convert coming vlan */
void record_coming_vlan_map(u_int16_t coming_vlan[], u_int16_t vlan_num, u_int16_t coming_v[], u_int16_t mapped_v[]);
/* set configs */
int nsm_set_vlan_mapping_config(struct vlan_mapping_head *h, u_int16_t coming_v[], u_int16_t mapped_v[], u_int16_t vlan_num);
/* end Vlan-mapping */    
#endif

五、将配置从结构体恢复为CLI示列所示——代码
void show_vlan_mapping_config(char *vlan_v, uint16_t vlan_id, uint16_t *base, uint16_t *continuous, uint16_t *first)    
{    
    char *p = vlan_v;    
    
    /* vlan-mapping vlan %d map-vlan %d */    
    if ((*continuous) == 1) {    
        if ((*first) == 1) {    
            *base = vlan_id;    
            *first = 0;    
            *continuous = 0;    
            sprintf(p, “%d”, vlan_id);    
        } else {
            if ((vlan_id – (*base)) == 1) {    
                *base = vlan_id;
            } else {
                while (*p != ‘’) {    
                    p++;
                }
                sprintf(p, “-%d”, *base);    
                *base = vlan_id;    
                *continuous = 0;    
                while (*p != ‘’) {
                    p++;    
                }    
                sprintf(p, “,%d”, vlan_id);    
            }    
        }    
    } else {    
        if ((vlan_id – (*base)) == 1) {    
            *base = vlan_id;    
            *continuous = 1;    
        } else {    
            *base = vlan_id;    
            while (*p != ‘’) {    
                p++;    
            }    
            sprintf(p, “,%d”, vlan_id);    
        }    
    }    
}

void vlan_mapping_config_write(struct cli *cli, struct vlan_mapping_head *h)
{    
    struct nsm_vlan_mapping *node;    
    struct list_head *pos, *n;    
    u_int16_t i;
    
    list_for_each_safe(pos, n, &h->lists) {    
        if (!(node = list_entry(pos, struct nsm_vlan_mapping, lists))) {
            break;    
        }    
        u_int16_t base = 0, continuous = 1, first  = 1;
        u_int16_t end = 0, continuouss = 1, firsts = 1;
        u_int16_t coming_vlan, mapped_vlan;
        char coming_v[256] = {0};    
        char mapped_v[256] = {0};
        
        i = 0;
        while (i < node->cnt) {    
            coming_vlan = node->coming_index[i];    
            if (VLAN_MAP_BITMAP_EXISTED(node->coming_bitmap, coming_vlan)) {    
                show_vlan_mapping_config(coming_v, coming_vlan, &base, &continuous, &first);
            }
            
            mapped_vlan = node->coming_vlan[coming_vlan];
            if (VLAN_MAP_BITMAP_EXISTED(node->mapped_bitmap, mapped_vlan)) {    
                show_vlan_mapping_config(mapped_v, mapped_vlan, &end, &continuouss, &firsts);    
            }    
            i++;    
        }    
    
        if (continuous == 1 && base != 0) {     
            char *p = coming_v;    
            while (*p != ‘’) {    
                p++;    
            }    
            sprintf(p, “-%d”, base);
        }
    
        if (continuouss == 1 && end != 0) {     
            char *p = mapped_v;    
            while (*p != ‘’) {    
                p++;    
            }
            sprintf(p, “-%d”, end);    
        }    
        
        cli_out (cli, ”    vlan-mapping vlan %s map-vlan %sn”, coming_v, mapped_v);
    }    
}

 六、需要注意bitmap——64位系统一定要用 0X1LL，之前就是被这里坑了 

#define VLAN_MAP_BITMAP_WIDTH       (64)
#define VLAN_MAP_BITMAP_SET(bitmap, vlan_id)                                    
    do {                                                                        
        int _word = (vlan_id) / VLAN_MAP_BITMAP_WIDTH;                          
        bitmap[_word] |= (0x1LL << ((vlan_id) % VLAN_MAP_BITMAP_WIDTH));        
    } while (0)

define VLAN_MAP_BITMAP_UNSET(bitmap, vlan_id)                                  
    do {                                                                        
        int _word = (vlan_id) / VLAN_MAP_BITMAP_WIDTH;                          
        bitmap[_word] &= ~(0x1LL <<((vlan_id) % VLAN_MAP_BITMAP_WIDTH));            
    } while (0)

#define VLAN_MAP_BITMAP_EXISTED(bitmap, vlan_id)                                
  bitmap[(vlan_id) / VLAN_MAP_BITMAP_WIDTH] & (0x1LL << ((vlan_id) % VLAN_MAP_BITMAP_WIDTH))