网络子系统29_桥接转发数据库

//	转发数据库
//		1.容量
//			net_bridge->hash[BR_HASH_SIZE]，其中BR_HASH_SIZE为(1<<8)，有256个bucket
//		2.老化机制，
//			2.1 gc函数，到期时会顺序遍历age_list上的转发项，修改gc函数下一次到期时间为age_list中第一个没有过期的转发项的剩余时间。
//			2.2 age_list链表，保存除本机l2地址以外的所有转发项，按照到期时间进行排序，新添加或更新的转发项保存在age_list尾部。


//	网桥转发数据库初始化
//	调用路径：br_init->br_fdb_init
1.1 void __init br_fdb_init(void)
{
	//创建转发项的SLAB cache
	br_fdb_cache = kmem_cache_create("bridge_fdb_cache",
					 sizeof(struct net_bridge_fdb_entry),
					 0,
					 SLAB_HWCACHE_ALIGN, NULL, NULL);
}


//	查询转发项
//		__br_fdb_xxx不会递增net_bridge_fdb_entry的引用计数，br_fdb_xxx会递增net_bridge_fdb_entry的引用计数		
//	参数：
//		addr，目的l2地址
//	函数主要任务：
//		hash l2地址到正确的bucket，遍历bucket查找具有相同l2地址的转发项
2.1 struct net_bridge_fdb_entry *__br_fdb_get(struct net_bridge *br,
					  const unsigned char *addr)
{
	struct hlist_node *h;
	struct net_bridge_fdb_entry *fdb;
	//net_bridge->hash为转发数据库的hash表
	hlist_for_each_entry_rcu(fdb, h, &br->hash[br_mac_hash(addr)], hlist) {//遍历对应的bucket的链表
		if (!memcmp(fdb->addr.addr, addr, ETH_ALEN)) {//比较转发项的地址与查询的地址
			if (unlikely(has_expired(br, fdb)))
				break;
			return fdb;//找到返回转发项
		}
	}

	return NULL;//否则返回null
}

//	添加转发项
//		转发数据库由hash_lock保护
2.2 int br_fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
		  const unsigned char *addr, int is_local)
{
	int ret;

	spin_lock_bh(&br->hash_lock);//获取hash表的锁，关下半部中断
	ret = fdb_insert(br, source, addr, is_local);//
	spin_unlock_bh(&br->hash_lock);
	return ret;
}
//	调用路径：br_fdb_insert->fdb_insert
//	函数主要任务：
//		1.遍历对应的bucket
//		2.如果对应的转发项已经存在
//			2.1 转发项为本机地址，添加的地址为本机地址，返回
//			2.2 转发项非本机，添加的地址为本机，更新已有的转发项
//			2.3 转发项非本机，添加的地址非本机
//				2.3.1 如果转发项静态配置，则不更新已有转发项
//				2.3.2 否则从age_list上删除转发项，更新已有转发项
//		3.转发项不存在，分配新的转发项，更新转发项，添加到hash表

//	对已有选项的更新：
//		1.设置转发项是否为本机
//		2.本机转发项设置为static
//		3.非本机转发项添加到age_list上	
2.3 static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
		  const unsigned char *addr, int is_local)
{
	struct hlist_node *h;
	struct net_bridge_fdb_entry *fdb;
	int hash = br_mac_hash(addr);

	if (!is_valid_ether_addr(addr))//非全0，非广播或多播地址
		return -EADDRNOTAVAIL;

	hlist_for_each_entry(fdb, h, &br->hash[hash], hlist) {//遍历对应的bucket
		if (!memcmp(fdb->addr.addr, addr, ETH_ALEN)) {//已存在l2地址对应的转发项
			if (fdb->is_local) {//转发项为本机地址
				if (is_local) //要添加的本机地址已经存在，直接返回
					return 0;

				return -EEXIST;//返回错误
			}

			if (is_local) {//转发项非本机地址，将此转发项修改为本机地址
				printk(KERN_WARNING "%s adding interface with same address "
				       "as a received packet\n",
				       source->dev->name);
				goto update;
			}

			if (fdb->is_static)//转发项静态配置
				return 0;

			list_del(&fdb->u.age_list);//将fdb从br->age_list链表上删除
			goto update;
		}
	}

	fdb = kmem_cache_alloc(br_fdb_cache, GFP_ATOMIC);//分配新的转发项
	if (!fdb)
		return ENOMEM;

	memcpy(fdb->addr.addr, addr, ETH_ALEN);//复制l2地址
	atomic_set(&fdb->use_count, 1);
	hlist_add_head_rcu(&fdb->hlist, &br->hash[hash]);//添加到对应的bucket

	if (!timer_pending(&br->gc_timer)) {
		br->gc_timer.expires = jiffies + hold_time(br);
		add_timer(&br->gc_timer);//启动垃圾回收定时器
	}

 update:
	fdb->dst = source;//到达此l2地址的端口
	fdb->is_local = is_local;//指示是否为本机地址
	fdb->is_static = is_local;//本机地址为静态配置地址
	fdb->ageing_timer = jiffies;//最近一次被使用的时间
	if (!is_local) 
		list_add_tail(&fdb->u.age_list, &br->age_list);//对于非本机地址的转发项，添加到br->age_list链表，执行垃圾回收机制

	return 0;
}

//	垃圾回收定时器
//		除本机地址外的所有转发项，链接在lru链表中，遍历链表，直到最后一个没有过期的转发项。
//	转发项到期时间：
//		1.正常情况下，300HZ
//		2.拓扑发生变化时，short aging机制，过期时间为15HZ

//	函数主要任务：
//		1.遍历age_list，释放过期的转发项
//		2.修改gc下一次到期时间为最近到期的邻居项的到期时间。
2.5 void br_fdb_cleanup(unsigned long _data)
{
	struct net_bridge *br = (struct net_bridge *)_data;
	struct list_head *l, *n;
	unsigned long delay;
	//在获取转发数据库的锁之后进行清理操作
	spin_lock_bh(&br->hash_lock);
	//1.当拓扑发生改变时，启动short aging机制，过期时间为15HZ，转发数据库中的项很快过期
	//2.在正常情况下，过期时间为300HZ
	delay = hold_time(br);

	list_for_each_safe(l, n, &br->age_list) {//安全方式遍历age_list
		struct net_bridge_fdb_entry *f;
		unsigned long expires;

		f = list_entry(l, struct net_bridge_fdb_entry, u.age_list);
		expires = f->ageing_timer + delay;//转发项的到期时间

		if (time_before_eq(expires, jiffies)) {//如果转发项到期
			WARN_ON(f->is_static);
			pr_debug("expire age %lu jiffies %lu\n",
				 f->ageing_timer, jiffies);
			fdb_delete(f);
		} else {
			mod_timer(&br->gc_timer, expires);//第一个没有过期的转发项，之后的所有转发项都不会过期，则调整gc_timer的下一次运行时间，返回
			break;
		}
	}
	spin_unlock_bh(&br->hash_lock);
}

//	调用路径br_fdb_cleanup->fdb_delete
2.6 static __inline__ void fdb_delete(struct net_bridge_fdb_entry *f)
{
	hlist_del_rcu(&f->hlist);//从hash表上删除此转发项
	if (!f->is_static)//is_static=1，说明为本机地址，本机地址不会出现在age_list上
		list_del(&f->u.age_list);//从age_list上删除此转发项

	br_fdb_put(f);//递减引用计数，为0时，直接释放
}