Linux 경로 학습 노트 중 하나 와 관련 된 데이터 구조

지금부터 루트 와 관련 된 코드 를 배우 고 코드 를 분석 하기 전에 우 리 는 먼저 데이터 구 조 를 분석 하고 데이터 구조 간 의 관 계 를 이해 한 후에 코드 를 이해 하 는 것 이 비교적 수월 하 다.이 소절 은 먼저 루트 와 관련 된 데이터 구 조 를 분석한다.커 널 안의 대부분 모듈 이 정의 하 는 데이터 구조 간 에는 일반적으로 링크 나 hash 표를 사용 하여 연결 작업 을 실현 합 니 다.
루트 테이블 에 대해 관련 데이터 구 조 는 fibtable、fn_hash、fn_zone、fib_node、fib_alias、fib_info、fib_nh 등, 다음은 이 몇 개의 데이터 구 조 를 각각 소개 한다.
 
루트 테이블 구조, 이 구 조 는 루트 테이블 의 추상 으로 루트 테이블 의 id, 루트 추가 함수, 루트 찾기 함수, 루트 삭제 함수 등 을 포함한다.

struct fib_table {
/*  hash               */
struct hlist_node tb_hlist;
/* id*/
u32	 tb_id;
unsigned	tb_stamp;
/*      */
int	 (*tb_lookup)(struct fib_table *tb, const struct flowi *flp, struct fib_result *res);
/*      */
int	 (*tb_insert)(struct fib_table *, struct fib_config *);
/*       */
int	 (*tb_delete)(struct fib_table *, struct fib_config *);
int	 (*tb_dump)(struct fib_table *table, struct sk_buff *skb,
     struct netlink_callback *cb);
/*        */
int	 (*tb_flush)(struct fib_table *table);
void	 (*tb_select_default)(struct fib_table *table,
     const struct flowi *flp, struct fib_result *res);
 
/*     ，            hash  */
unsigned char	tb_data[0];
};

 
이 구 조 는 주로 마스크 로 구 분 된 지역 구조 와 마스크 구역 간 의 관 계 를 묘사 하 는 데 쓰 인 다.
ipv 4 에 있어 마스크 는 0 - 32 총 33 가지 가능성 이 있 기 때문에 fnhash
33 개 fn 포함zone 의 배열, 링크 fnzone_list, 주로 표 에 있 는 경로 입 니 다.
fn_zone 링크 가 함께 연결 되 어 있 습 니 다.
 

struct fn_hash {
struct fn_zone	*fn_zones[33];
struct fn_zone	*fn_zone_list;
};

 
마스크 로 구 분 된 지역 구조 가 추상 적 이 고 마스크 길이 가 같은 모든 길 을 같은 fn 에 두 었 습 니 다.zone 에서 hash 표 에 있 습 니 다.

struct fn_zone {
/*        fn_zone*/
struct fn_zone	 *fz_next;
 
/*        hash  ，         ip  ，        
 hash ，   fn_node        hash   */
struct hlist_head	*fz_hash;	/* Hash table pointer	*/
 
/*fn_node       ，fn_node              ，       
         ，            ，    tos、priority、mark   
     ，    fn_node   fn_alias              */
int	 fz_nent;	/* Number of entries	*/
 
/* fn_zone fz_hash     */
int	 fz_divisor;	/* Hash divisor	 */
/*fz_hash mask */
u32	 fz_hashmask;	/* (fz_divisor - 1)	*/
#define FZ_HASHMASK(fz)	 ((fz)->fz_hashmask)
   /*       fz_hash         */
 
/* fn_zone       */
int	 fz_order;	/* Zone order	 */
/*  fz_order       */
__be32	 fz_mask;
/*   fn_zone      */
#define FZ_MASK(fz)	 ((fz)->fz_mask)
};

 
 
 
 
하나의 목적 네트워크 주소 와 같은 모든 경로 항목 의 기본 구조 로 추상 화 되 며, 그 중의 fnalias, 이 구조 에 포 함 된 존재 하 는 경로 항목 의 링크, fnkey 는 이 구조 에 대응 하 는 목적 네트워크 주소 값 입 니 다.
마스크 길이 와 같은 다른 fib 에 사용node 구분, 같은 fnzone 의 fibnode, 모두 fn 로 연결zone->fz_hash 에 해당 하 는 hash 표 중
 

struct fib_node {
    /*   hash   ，          ，    
        fib_node       */
struct hlist_node	fn_hash;
struct list_head	fn_alias;
__be32	 fn_key;
};

 
 
그 구 조 는 경로 항목 의 추상 으로 이해 할 수 있다.
루트 항목 의 목적 네트워크 주소 와 동시에 이 구조 변수 에 따라 서로 다른 루트 항목 을 구분 할 수 있다.tos, type, scope, state 및 fib 포함info 경로 항목 구분
 
방법:
1. 먼저 tos, type, scope 등에 따라 fibalias
2. 당 fibalias 확정 후 priority 등가 에 따라 fibinfo,
3. fibinfo 출구 장치 와 다음 스위치 의 ip 주 소 를 확인 합 니 다.

struct fib_alias {
struct list_head	fa_list;
struct rcu_head rcu;
struct fib_info	 *fa_info;
u8	 fa_tos;
u8	 fa_type;
u8	 fa_scope;
u8	 fa_state;
};

그리고 fascope 는 경로 의 scope 를 나타 내 고 수치 범 위 는 다음 과 같다.
RT_SCOPE_UNIVERSE: 이 옵션 은 비 직선 목적지 로 통 하 는 모든 경로 표 항목 에 사 용 됩 니 다. 즉,
                              응용 층 이 만 든 경로 에는 via 의 경로 가 포함 되 어 있 습 니 다.                       
RT_SCOPE_LINK: 이 옵션 은 로 컬 네트워크 의 경로 항목 에 사 용 됩 니 다.
RT_SCOPE_HOST: 이 옵션 은 이 컴퓨터 인터페이스 에 사 용 됩 니 다.
RT_SCOPE_NOWHERE: 이 옵션 은 경로 가 도착 할 수 없 는 데 사 용 됩 니 다.                                

enum rt_scope_t
{
RT_SCOPE_UNIVERSE=0,
/* User defined values  */
RT_SCOPE_SITE=200,
RT_SCOPE_LINK=253,
RT_SCOPE_HOST=254,
RT_SCOPE_NOWHERE=255
};

 
 
 
 
 
기능: 주로 수출 설비 와 다음 게 이 트 웨 이 를 가 져 오 는 데이터 구조, 그리고 경로 항목 의 우선 순위, 경로 생 성 프로 토 콜 fibprotocol (RTPROTO KERNEL, RTPROTO BOOT, RTPROTO STATIC 등 수치 추출).반면 fibhash 와 fiblhash 는 fibinfo 대응 하 는 hash 링크 fibinfo_hash [] 와 fibinfo_laddrhash [] 에서 갔 어 요.

struct fib_info {
/*         fib_info   hash   */
struct hlist_node	fib_hash;
struct hlist_node	fib_lhash;
int	 fib_treeref;
atomic_t	 fib_clntref;
/*         fib_info  */
int	 fib_dead;
unsigned	 fib_flags;
int	 fib_protocol;
__be32	 fib_prefsrc;
/*   */
u32	 fib_priority;
u32	 fib_metrics[RTAX_MAX];
#define fib_mtu fib_metrics[RTAX_MTU-1]
#define fib_window fib_metrics[RTAX_WINDOW-1]
#define fib_rtt fib_metrics[RTAX_RTT-1]
#define fib_advmss fib_metrics[RTAX_ADVMSS-1]
/*fib_nh     */
int	 fib_nhs;
#ifdef CONFIG_IP_ROUTE_MULTIPATH
int	 fib_power;
#endif
#ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED
u32	 fib_mp_alg;
#endif
    /*      ，      fib_nh    */
struct fib_nh	 fib_nh[0];
#define fib_dev	 fib_nh[0].nh_dev
};

 
 
 
 
다음 스위치 와 출구 설 비 를 포함 하 는 구조

struct fib_nh {
    /*         */
struct net_device	*nh_dev;
/* fib_nh     hash   */
struct hlist_node	nh_hash;
/*      fib_info  */
struct fib_info	 *nh_parent;
unsigned	 nh_flags;
unsigned char	 nh_scope;
#ifdef CONFIG_IP_ROUTE_MULTIPATH
int	 nh_weight;
int	 nh_power;
#endif
#ifdef CONFIG_NET_CLS_ROUTE
__u32	 nh_tclassid;
#endif
/*     index*/
int	 nh_oif;
/*       */
__be32	 nh_gw;
};

그리고 nhhash 는 fib 를nh 변 수 는 대응 하 는 fib 로 연 결 됩 니 다.info_devhash [] 링크 에 있 는.
 
이상 은 해당 하 는 데이터 구조 분석 이 고 다음은 이러한 데이터 구조 간 의 논리 적 관계 이다.fib 를 드 리 지 않 았 습 니 다info_hash[]、fib_info_laddrhash [] 와 fibinfo 사이 의, fib 도 주지 않 았 습 니 다.nh 와 fibinfo_devhash 사이 의 관계
이상 은 경로 와 관련 된 데이터 구조 이 고 다음 절 부터 경로 의 추가 와 삭제 등 기능 을 분석 하 는 것 이다.상기 분석 한 데이터 구 조 는 캐 시 와 관련 된 데이터 구 조 를 포함 하지 않 고 캐 시 에 소 개 될 때 까지 기 다 렸 다가 분석 합 니 다.