CHAPTER2：寻路的向导——ARP
一、简介
我们使用TCP/IP进行通信，从高层来看使用的是IP地址作为源/目的地的标示，但通信最终还是要由物理网络使用底层网络硬件提供的物理编址方案执行。我们通常使用的网络硬件就是以太网卡，其物理地址也就是网卡的MAC。ARP地址解析协议所要做的就是将物理地址和IP地址绑定，让高层协议通过使用IP地址即能和目的地产生通信。ARP的工作方式在comer的《用TCP/IP进行网际互联第一卷》中讲的非常清楚，在此不在累述。我们关心的是ARP的具体实现方式。在comer的协议栈中，实现的ARP协议的文件共有9个，分别对应9个函数，分别是：arpsend.c(发送ARP请求)、arpalloc.c（在ARP高速缓存中分配一个表项）、arpdq.c（释放与ARP高速缓存表项相关的队列）、arpinit.c（初始化ARP）、arp_in.c（处理收到的ARP数据包）、arpadd.c（在ARP高速缓存中添加一个表项）、arpfind.c（在ARP高速缓存中搜索一个表项）、arpqsend.c（发送与ARP表项相关的队列）、arptimer.c（ARP高速缓存表定时维护）。从函数的功能我们可以看出，整个ARP协议的操作都是围绕着一张ARP 高速缓存表来实现的，其数据结构在arp.h文件中定义的非常清楚。除此之外，ARP协议与其它层次协议有部分交互操作，主要靠两个文件中的函数实现：ni_in.c（用于数据包的传入）、netwrite.c（用于向外发送数据，发送前检查是否已经ARP绑定），这在后面的源码中会依次介绍。对整个ARP协议实现的移植没有花费太大工作，因为我们已经实现了网络接口层，而ARP的代码大部分是脱离网络接口层实现的，只有在发送数据、关闭中断、队列管理时做了部分修改，以及修正了comer中ARP实现的一些小bug（准确的说，这不一定是bug，因为comer的TCP/IP是和xinu系统结合的，也许部分工作放到了xinu中实现，但仅从协议栈来看，它确实是bug。这些bug会使我们的ARP协议无法正常工作）。在本文的最后，将给出一个使用移植后的ARP实现的小程序，用于获取指定IP的物理地址。在看源码之前，我建议大家先看一遍arp.h的定义，对要使用到的数据结构有一个大概的了解，在源码里遇到它们时才不会陌生。
二、源码
仍然先说一说头文件，对于comer中的arp.h文件，我没有做太大修改，仅仅是增加了一个linux下的互斥锁结构：pthread_mutex_t arp_mutex;。使用互斥锁的目的，是替代comer中disable操作（关闭中断）。因为在comer的xinu系统中可以轻易调用disable函数关闭中断，防止不同进程同时操作临界资源，但在linux下就不是这么容易了。我查了半天资料，也没搞懂如何直接关闭系统中断（嘿嘿，记住，我只是一个才使用linux不到两个月的菜鸟），但可以想像的是，在用户层编程是不可能直接关闭系统中断的，即使要，也应该使用ioctl授权。为了避免这么复杂的操作，同时考虑到我们是在用户层编程，我使用了互斥锁解决临界资源的访问问题。为了定义互斥锁，必须包含pthread.h文件。我把它放在了network.h文件中，方便以后在其它地方使用互斥锁时避免重复包含。这里顺便讲一下network.h头文件。Comer在定义这个文件时对每个头文件的顺序进行了精心安排，后面的头文件很可能使用到前面头文件中的定义。我建议大家不要更改其中的排列顺序，避免在编译时出现找不到某个定义的情况（例如，在netif.h文件中就使用了IPaddr，而IPaddr是在ip.h中定义的，所以ip.h放在了netif.h的前面）。最后，每个文件都包含了kernel.h头文件，它定义了一些常量和typedef类型定义，几乎所有的头文件都要使用到，所以在包含的时候我们总把它放在network.h文件之上。
源码的具体讲解请参见comer的《用TCP/IP进行网际互联第二卷》，这里只着重讲做了改动的地方。
1、 arpfind.c － 搜索ARP高速缓存
同样先给出源码：
/* arpfind.c －搜索ARP 高速缓存(2006.4.6)*/
//#include <conf.h>
#include <kernel.h>
#include <network.h>
/*
*通过给定的协议地址(这里应该是物理地址) 和网络接口号
*来搜索缓存表项(ARP entry)
*
*/
struct arpentry *arpfind(u_char *pra,u_short prtype,struct netif *pni)
{
struct arpentry *pae;
int i;
for (i = 0; i < ARP_TSIZE; ++i)
{
pae = &arptable[i];
//空闲的表项当然不是我们要找的
if (pae->ae_state == AS_FREE)
continue;
//比较协议类型，接口号，协议地址
//都满足则是我们要找的表项
if (pae->ae_prtype == prtype && pae->ae_pni == pni
&& memcmp(pae->ae_pra,pra,pae->ae_prlen))
return pae;
}
return NULL;
}
arpfind函数非常简单，这里没有做什么改动，仅仅更改了一个地方，把if (pae->ae_prtype == prtype && pae->ae_pni == pni&& BLKEQU(pae->ae_pra,pra,pae->ae_prlen)) 中的BLKEQU宏用c函数memcmp替换了。如果你查看了xinu系统中关于BLKEQU宏的源码，就可以发现它仅仅是memcmp函数的一个替换，所以我们在这里直接使用memcmp函数并不会改变程序的功能。源码的解释在书中和以上注释都写的非常清楚，不再累述。
2、 arpseng.c － 发送ARP请求广播
/* arpsend －广播ARP 请求(2006.4.6)*/
/*利用arpentry 中的大部分信息构造一个ARP请求包
*利用广播地址发送出去
*
*
*/
//#include <conf.h>
#include <kernel.h>
#include <network.h>
int arpsend(struct arpentry *pae)
{
struct netif *pni = pae->ae_pni;
struct ep *pep;
struct arp *parp;
int arplen;
//这里用malloc 代替了本来的缓冲池，
pep = (struct ep *) malloc(sizeof(struct ep));
if ((int) pep == SYSERR || pep == NULL)
return SYSERR;
//这里填写了以太网头，用广播地址作为目的地址
//comer没填源硬件地址，这里把它加上了
memcpy(pep->ep_dst,pni->ni_hwb.ha_addr,pae->ae_hwlen);
memcpy(pep->ep_src,pni->ni_hwa.ha_addr,pae->ae_hwlen);
//注意，此处书中没做字节顺序转换
pep->ep_type = hs2net(EPT_ARP);
pep->ep_order = EPO_NET;
//下面填写了arp 包，目的物理地址设为0，等待对方应答填写
parp = (struct arp *) pep->ep_data;
parp->ar_hwtype = hs2net(pae->ae_hwtype);
parp->ar_prtype = hs2net(pae->ae_prtype);
parp->ar_hwlen = pae->ae_hwlen;
parp->ar_prlen = pae->ae_prlen;
parp->ar_op = hs2net(AR_REQUEST);
memcpy(SHA(parp),pni->ni_hwa.ha_addr,pae->ae_hwlen);
memcpy(SPA(parp),&pni->ni_ip,pae->ae_prlen);
memset(THA(parp),0,pae->ae_hwlen);
memcpy(TPA(parp),pae->ae_pra,pae->ae_prlen);
arplen = ARP_HLEN + 2 * (parp->ar_hwlen + parp->ar_prlen);
return link_write((u_char *)pep,EP_HETHLEN+ arplen);
}
arpsend.c所做变动比较大，首先，我们用malloc替代了getbuf函数。Getbuf是xinu系统中的缓冲池分配函数，用于comer所提到了缓冲区分配。为了简化编程工作，缓冲区的分配不是我所关注的，故简单的使用malloc分配内存，并不考虑其效率问题。同样，在程序中所有的内存分配处都使用了malloc代替，释放的时候相应的就该使用free函数。大家或许注意到了pep->ep_type = hs2net(EPT_ARP); 这条语句，在comer的书中和协议栈中，都没有使用hs2net做本机到网络的字节转换（或许这项工作在xinu系统中放到了网络接口层，或许是个bug。但一种规范的方式是，我们在将数据包提交给网络接口层发送前，就应该做好了所有的封包工作，而不是在网络接口层再做一次），如果不做字节转换的话，我们所发出的ARP请求是得不到对方响应的。另外，我还想提一下arp结构中的ar_op字段，它代表了ARP报文中的操作字段。在comer的书中（第一卷），是这样描述的：操作（OPERATION）字段指明是ARP请求（1）、ARP响应（2）、RARP请求（3）、RARP响应（4）。 网上的资料延续了这种说法。与之对比的是，在之前讲协议类型时（就在讲操作字段前），作者特别提醒协议类型字段（ar_prtype）的0806是16进制值。这就很容易造成我们认为操作字段的1、2、3、4代表了10进制。其实它们都是16进制值，从程序中做了字节地址转换就可以看出（当时我在用libpcap做一个收包程序的时候，就是忽略了这点，半天不能检测出ARP请求报文）。SHA(x)、SPA(x)、THA(x)、TPA(x) 4个宏定义于arp.h文件中，作用分别是取出参数所指定的arp结构中的源物理地址、源协议地址（ip地址）、目的硬件地址、目的协议地址的指针。这是个c语言下动态数组的实现方法，大家可以从arp.h文件中的定义看出。最后，我们调用了网络接口层的link_write函数发送数据包，注意这里len参数我们用EP_HETHLEN （＝14，以太网帧头长度，自己添加的，定义于ether.h中）代替了原来的 EP_HLEN (=24，comer的扩展以太网帧头长度)，目的是发送一个标准的以太网帧，这在前面的网络接口一文中有提到。最后，函数返回了发送的字节数，代替了原来的OK。
3、 netwrit.c －发送数据包到指定网络接口
/* netwrite.c －输出过程(2006.4.8)*/
/*netwrite用于接收将要被发往某个网络接口的分组。
*当不知道对方物理地址时，用ARP 发现
*
*
*/
//#include <conf.h>
#include <kernel.h>
#include <network.h>
#include <q.h>
//申明arp 的全局互斥锁，用于代替disable 的关中断动作(定义于arp.h 中)
extern pthread_mutex_t arp_mutex;
struct arpentry *arpalloc();
struct arpentry *arpfind(u_char * pra, u_short prtype, struct netif * pni);
int arpsend(struct arpentry * pae);
//local_out用于将目的是本地机的数据包通过loopback 发送到指定本机端口
int local_out(struct ep *);
int netwrite(struct netif * pni, struct ep * pep, unsigned len)
{
struct arpentry *pae;
//首先检查网络接口是否可用。注意，我们这里的
//pep 全部是用free 释放，malloc 分配。
if (pni->ni_state != NIS_UP)
{
free(pep);
return SYSERR;
}
pep->ep_len = len;
//如果是本地接口，用local_out 发送。
//否则，首先检查下一跳是否是广播地址 ，若是，
//填写目的物理地址为广播物理地址，发送
if (pni == &nif[NI_LOCAL])
return OK;
//return local_out(pep);
else if (isbrc(pep->ep_nexthop))
{
memcpy(pep->ep_dst,pni->ni_hwb.ha_addr,EP_ALEN);
link_write((u_char *)pep,len);
return OK;
}
//如果下一跳地址不是广播地址，则先在arp 缓存表
//中查找是否有绑定的物理地址，有则直接发送
//，没有则先做arp 地址绑定。
pthread_mutex_lock(&arp_mutex);
pae = arpfind((u_char *) &pep->ep_nexthop,pep->ep_type,pni);
if (pae && pae->ae_state == AS_RESOLVED)
{
memcpy(pep->ep_dst,pae->ae_hwa,pae->ae_hwlen);
pthread_mutex_unlock(&arp_mutex);
return link_write((u_char *)pep,len);
}
//下一跳地址为d 类地址则直接返回
if (IP_CLASSD(pep->ep_nexthop))
{
pthread_mutex_unlock(&arp_mutex);
return SYSERR;
}
//没有绑定，做arp 解析。
//先分配一个缓存表项，填写各字段，调用arpsend 发送arp 包
if (pae == NULL)
{
pae = arpalloc();
pae->ae_hwtype = AR_HARDWARE;
pae->ae_prtype = EPT_IP;
pae->ae_hwlen = EP_ALEN;
pae->ae_prlen = IP_ALEN;
pae->ae_pni = pni;
pae->ae_queue = EMPTY;
memcpy(pae->ae_pra,&pep->ep_nexthop,pae->ae_prlen);
pae->ae_attempts = 0;
pae->ae_ttl = ARP_RESEND;
arpsend(pae);
}
//将等待arp 绑定的数据包存放在和arp 表项相关的队列
//中，如果队列为空，则分配一个。
if (pae->ae_queue == EMPTY)
pae->ae_queue = newq(ARP_QSIZE,QF_NOWAIT);
if (enq(pae->ae_queue,pep,0) < 0)
free(pep);
pthread_mutex_unlock(&arp_mutex);
return OK;
}
代码注释非常清楚，再加上comer在书中的讲解，可以非常容易的看懂程序。这里仅仅要注意的是我们用前面提到的互斥锁代替了原程序中的disable(ps)和restore(ps)，用于临界资源的访问控制。最后说一下newq、enq、freeq这几个函数，它们是xinu系统中的队列管理函数，用于分配、插入、释放队列，定义于sys/gpq.c文件中。由于其中也涉及到了临界资源的访问，同样我们用linux下的互斥锁和信号灯对其进行了改写。如果你对它的实现不感兴趣，可以跳过下面源码。源码同时给出了队列管理代码的注释，现在只改写了用到的几个函数，其它函数等用到的时候再改写。关于linux信号灯和互斥锁的操作方法请参见相关书籍和资料。
/* zgpq.c -- xinu系统中gpq.c 文件的linux 实现 (2006.4.8)*/
/* 队列管理函数 */
//#include <conf.h>
#include <kernel.h>
#include <q.h>
//用于实现互斥锁
#include <pthread.h>
//linux下头文件，用于实现信号灯
#include <linux/sem.h>
struct qinfo {
Bool q_valid; //元素是否可用，FALSE 可用，TURE 不可用
int q_type; /* mutex type 队列类型(是否阻塞)*/
int q_max;//队列大小
int q_count;//队列中数据包的个数
int q_seen;
int q_mutex;
int *q_key;//关键字(其实是个int 数组，表示数据包在队列中的大概位置，值越大越靠前)
char **q_elt;//数据区(一个字符串数组，每个元素对应一个数据包)
};
static int qinit = FALSE; //用于指明队列是否初始化
static int initq();
#ifndef MAXNQ //队列表最大长度100
#define MAXNQ 100
#endif !MAXNQ
static struct qinfo Q[MAXNQ]; //队列表，每个元素为一个队列
/* linux 信号灯设置部分*/
struct sembuf semwait,semsignal;
#define PERMS IPC_CREAT|IPC_NOWAIT
//设置互斥锁，替代disable 关中断
pthread_mutex_t q_mutex;
//信号灯操作方式初始化函数
//信号灯操作方式，也就是semop 函数的第二个参数
void init_sem_struct(struct sembuf *sem,int semnum,int semop,int semflg)
{
sem->sem_num = semnum;
sem->sem_op = semop;
sem->sem_flg = semflg;
}
//删除信号灯
int del_sem(int semid)
{
return semctl(semid,0,IPC_RMID);
}
//分配一个新队列，返回队列的序号(也就是在数组中的位置)
int newq(unsigned size, unsigned mtype)
{
struct qinfo *qp;
int i;
//若没有初始化，初始化队列表
if (!qinit)
initq();
//寻找一个空闲的表项
for (i=0; i<MAXNQ; ++i) {
if (!Q[i].q_valid)
break;
}
//没有找到退出
if (i == MAXNQ)
return -1;
qp = &Q[i];
qp->q_valid = TRUE; //设置表项为已用
qp->q_type = mtype;//设置队列类型(是否使用信号灯)
qp->q_max = size;//队列长度
qp->q_count = 0;//初始数据包为0个
qp->q_seen = -1;
//如果队列类型阻塞方式，则启用信号灯(这里用liunx方式)
if (mtype != QF_NOWAIT)
qp->q_mutex = semget(IPC_PRIVATE,1,PERMS);
//如果信号灯启动失败，则将队列设为非阻塞方式
if (qp->q_mutex == -1)
qp->q_type = QF_NOWAIT;
else
{ /*这里首先用semop 执行一次signal 操作是必要的。
因为semget 后信号灯为0，没有可用资源
所以要先释放一次 。同样，如果执行失败
，则将队列设为非阻塞*/
if ((semop(qp->q_mutex,&semsignal,0)) == -1)
qp->q_type = QF_NOWAIT;
}
//分配队列缓存和关键字
qp->q_elt = (char **) malloc(sizeof(char *) * size);
qp->q_key = (int *) malloc(sizeof(int) * size);
if (qp->q_key == (int *) SYSERR || qp->q_elt == (char **) SYSERR
|| qp->q_key == NULL || qp->q_elt == NULL)
return -1;
return i;
}
int enq(int q, void *elt, int key)
{
struct qinfo *qp;
int i, j, left;
//判断序号是否正常
if (q < 0 || q >= MAXNQ)
return -1;
if (!Q[q].q_valid || Q[q].q_count >= Q[q].q_max)
return -1;
qp = &Q[q];
//根据是否阻塞采取不同的操作
if (qp->q_type == QF_NOWAIT)
pthread_mutex_lock(&q_mutex);
else
semop(qp->q_mutex,&semwait,0);
/* start at tail and move towards head, as long as key is greater */
/* this shouldn't happen, but... */
/*根据key 值来确定数据包在队列中的位置。
*key 越大，位置越靠前。
*/
if (qp->q_count < 0)
qp->q_count = 0;
i = qp->q_count-1;
while(i >= 0 && key > qp->q_key[i])
--i;
/* i can be -1 (new head) -- it still works */
for (j = qp->q_count-1; j > i; --j) {
qp->q_key[j+1] = qp->q_key[j];
qp->q_elt[j+1] = qp->q_elt[j];
}
qp->q_key[i+1] = key;
qp->q_elt[i+1] = elt;
qp->q_count++;
//返回值是队列空闲数量
left = qp->q_max - qp->q_count;
if (qp->q_type == QF_NOWAIT)
pthread_mutex_unlock(&q_mutex);
else
semop(qp->q_mutex,&semsignal,0);
return left;
}
//从队列顶部取出一个数据包，并在队列中删除。
//程序很简单，取出顶部的包后，将后面的包依次
//向前移动一位，包计数器(count) 减1
void *deq(int q)
{
struct qinfo *qp;
char *elt;
int i;
if (q < 0 || q >= MAXNQ)
return NULL;
if (!Q[q].q_valid || Q[q].q_count <= 0)
return NULL;
qp = &Q[q];
if (qp->q_type == QF_NOWAIT)
pthread_mutex_lock(&q_mutex);
else
semop(qp->q_mutex,&semwait,0);
elt = qp->q_elt[0];
for (i=1; i<qp->q_count; ++i) {
qp->q_elt[i-1] = qp->q_elt[i];
qp->q_key[i-1] = qp->q_key[i];
}
qp->q_count--;
if (qp->q_type == QF_NOWAIT)
pthread_mutex_unlock(&q_mutex);
else
semop(qp->q_mutex,&semsignal,0);
return(elt);
}
//释放队列。注意，在newq 中我们使用malloc 为队列分配
//空间的，所以这里同样应该用free 释放。
//程序很简单，注意这里q_count 必须为0 时队列才能被
//释放，以确保队列中所有的包都被发送出去后才释放队列。
int freeq(int q)
{
struct qinfo *qp;
if (q < 0 || q >= MAXNQ)
return FALSE;
if (!Q[q].q_valid || Q[q].q_count != 0)
return FALSE;
qp = &Q[q];
free(qp->q_key);
free(qp->q_elt);
if (qp->q_type != QF_NOWAIT)
//队列释放后，信号灯也被删除
del_sem(qp->q_mutex);
qp->q_valid = FALSE;
return TRUE;
}
//初始化队列
static int initq()
{
int i;
for (i=0; i<MAXNQ; ++i)
Q[i].q_valid = FALSE;
qinit = TRUE;
//注意，这里使用了SEM_UNDO 参数，是为了
//在我们忘记释放资源的时候，由内核自动释放
/* semsignal是释放资源的操作(+1) */
init_sem_struct(&semwait,0,-1,SEM_UNDO);
/* semwait是要求资源的操作(-1) */
init_sem_struct(&semsignal,0,1,SEM_UNDO);
//初始化互斥锁
pthread_mutex_init(&q_mutex,NULL);
}
4、 arpqsend － 发送等待的队列
/* arpqsend.c －发送等待发送的分组(2006.4.8) */
/*在netwrite 函数中，我们将没有绑定物理地址的分组保存
*在队列中，然后进行arp 地址解析,
*arpqsend 将这些等待的分组发送出去。被arp_in 调用
*/
//#include <conf.h>
#include <kernel.h>
#include <network.h>
int netwrite(struct netif * pni, struct ep * pep, unsigned len);
//程序很简单，取出表项对应的队列，依次发送完后
//释放队列。将arp 表项的队列序号设为－1
void arpqsend(struct arpentry *pae)
{
struct ep *pep;
struct netif *pni;
if (pae->ae_queue == EMPTY)
return;
pni = pae->ae_pni;
while (pep = (struct ep *) deq(pae->ae_queue))
netwrite(pni,pep,pep->ep_len);
freeq(pae->ae_queue);
pae->ae_queue = EMPTY;
}
程序很简单，没有做任何改动，其中的队列管理函数deq和freeq在上面已经介绍。
－－未完待续