RFC-2461 IPv6 NDP中NA延时的一个实现方案：异步/多实例/实时性

背景

最近为了实现NDP(Neighbor Discovery Protocol)里头proxy延迟的问题，去看了一下RFC-2461，以及思考了下如果要实现Multiple instance NDP应该怎么做扩展。

知识介绍

在最新的iFreeBSD(FeeBSD 11.X)代码里依然没有实现RFC-2461中规定的对于anycast或者proxy类型的NS包在回NA的时候需要一个小于1S的随机时间的延时:
“If the Target Address is an anycast address the sender SHOULD delay sending a response for a random time between 0 and MAX_ANYCAST_DELAY_TIME seconds.”
其中，MAX_ANYCAST_DELAY_TIME为1 second.
大致意思就是说，对于接受到的每一个NS包，需要回一个NA给对端。对于anycast或者proxy这种类型的包，再回NA的时候需要一个时间延迟，该延时时一个小于1S的随机时间。

引入延迟的主要原因是为了使代理的邻居项的优先级比其他授权的主机（例如，实际拥有Solicited L3地址的主机）的低。延迟时间是一个随机数的原因是，随机数的使用可以降低多个主机同时发出请求，并导致拥塞的可能。

FreeBSD的代码具体参见下面这个函数：

  /*
   * Neighbor advertisement input handling.
   *
   * Based on RFC 2461
   * Based on RFC 2462 (duplicate address detection)
   *
   * the following items are not implemented yet:
   * - proxy advertisement delay rule (RFC2461 7.2.8, last paragraph, SHOULD)
   * - anycast advertisement delay rule (RFC2461 7.2.7, SHOULD)
   */

void nd6_na_input(struct mbuf *m, int off, int icmp6len);

在Kernel里头对于延时的一个做法是借助一个timer机制：即我们启动一个定时器，给定时器设置一个超时时间，然后在定时器超时后去执行相应的操作。我们对这个场景做一些简化，只需要如下三个timer的API：

/* 初始化一个timer */
void timer_init(struct timer *t);

/* 启动timer，ticks是timer多长时间超时，超时后去执行func这个函数，arg是传递给func的参数 */
void timer_start(struct timer *t, int ticks, void *func, void *arg);

/* 强制终止一个timer，用在处理异常情况 */
void timer_stop(struct timer *t);

一个简单的实现

然后我们假设NA要执行的函数是anycast_delay_handler, 用到的参数na_arg,.
那么我们可以做如下一个大致实现:

nd6_na_input()
{
    if (anycast || proxy ) {
        int delay = random() % HZ;
        struct timer *anycast_delay_timer;
        anycast_delay_timer = (struct timer *)malloc(sizeof(struct timer));
        if (anycast == NULL) {
            goto freeit;
        }
        na_arg->timer = anycast_delay_timer; /* need free it in the async function */
        jtimer_init(anycast_delay_timer);
        jtimer_start(anycast_delay_timer, delay, anycast_delay_handler, na_arg);
        return;
    }

freeit:
    …
}

void
anycast_delay_handler(void *arg)
{
    struct na_arg_t *na_arg = (struct na_arg_t *)arg;
     /*send out the NA packet*/
    ...
    free(na_arg->timer);
}

一些说明：

anycast_delay_handler 是一个异步函数，即启动timer的函数nd6_na_input()不用等待该函数执行就直接返回，这也是timer的一种做法。如果是同步函数，那就得等待该函数执行完毕后，nd6_na_input()再返回。
由于anycast_delay_handler是异步函数，所以这个local timer就不能分配在栈空间，必须分配在堆空间，然后在timer超时后再在anycast_delay_handler里面free掉该timer。
但是这种做法不太scalable，它的扩展性比较差。比如我们要想强制stop该timer就不是很好处理。通常我们都是把timer来定义为一个全局变量，而不是局部变量，然后让timer分时对处理各个任务。我们可以看到在Linux Kerrnel里头，NDP/ARP都是有一个全局的neighbor table，比如ndp_tbl, arp_tbl，也就是每个协议在内核协议栈里面都是单实例的，所以对于NDP我们最好只使用一个timer，而不是每个packet都创建一个timer。
HZ这个值是可以配置的，用来表示时钟中断的频率，即1S有HZ个时钟中断。在Kernel里面一般默认为100或者1000. 这里(randome() % HZ)表示最大1S的时间。

可扩展性考虑

所以，为了scalable考虑，我们还是得将该timer定义为一个全局的timer。
static struct timer anycast_delay_timer; / 定义为一个static变量 /
由于timeout handler跟start timer的函数是异步的，一旦定义为全局timer后，就要面临一个异步问题：在一个新的NS包到来后前一个NS包的NA的timer可能还没有超时，那么这个新的NA包去start这个timer就会出现问题。所以我们必须把需要发送的NS包都给添加到一个链表里面，然后该timer去这个链表里面去取。这可以借助FreeBSD的TAILQ机制来实现。

struct na_struct_t
{
    ...
    /* 放到一个TAILQ里头 */
    TAILQ_ENTRY(na_struct_t) anycast_delay_list;
};

TAILQ_HEAD(anycast_list_, na_struct_t) anycast_list = TAILQ_HEAD_INITIALIZER(anycast_list);

static struct timer anycast_delay_timer;
static boolean timer_running = false;
/* the max members in the anycast_delay_list */
#define ANYCAST_DELAY_MAX_LEN 64
/* anycast/proxy delay list length */
int anycast_delay_len = 0;

nd6_na_input()
{
    ...
    if (anycast || proxy ) {
        int delay = random() % HZ;
        struct na_struct_t *na_arg = set_na(...);
        spin_lock(&anycast_list_lock);
        if (anycast_delay_len > ANYCAST_DELAY_MAX_LEN) {
            goto freeit;
        }
        TAILQ_INSERT_TAIL(&anycast_list, na_arg, anycast_delay_list);
        anycast_delay_len++;
        spin_unlock(&anycast_list_lock);
        if (!timer_running) {
            timer_running = true;
            timer_start(&anycast_delay_timer, delay, anycast_delay_handler, (void *)0);
        }

        return;
    }
}

void
anycast_delay_handler(void *arg)
{
    spin_lock(&anycast_list_lock);
    /* once this function is executed, the tail should not be empty */
    struct na_arg_t *na = TAILQ_FIRST(&anycast_list);
    TAILQ_REMOVE(&anycast_list, na, anycast_delay_list);
    anycast_delay_len--;
    /*send out the NA packet*/
     ...
    if (!TAILQ_EMPTY(&anycast_list)) {
        int delay = random() % HZ;
        /* 还有NA需要send， 所以重启定时器 */
        timer_start(&anycast_delay_timer, delay, anycast_delay_handler, (void *)0);
    } else {
        /* 没有NA了，所以NS里面可以启动定时器了 */
        timer_running = false;
    }
    spin_unlock(&anycast_list_lock);
}

一些说明：

在timeout函数的尾部判断是否需要重启定时器，这样来一个一个的处理TAILQ里面的元素
这个TAILQ是一个全局的链表，所以需要考虑到并行问题，在对这个链表操作时需要加锁。这个锁的粒度有些大，可以更改的更加小粒度一些，比如只要锁住插入/删除位置即可。定时器超时函数是在软中断中执行的，它不是进程上下文，所以不能执行休眠和调度。所以在timeout函数里面访问共享数据的时候，不能使用mutex来加锁，要使用spinlock来加锁。(mutex会睡眠，spinlock则是一直忙等)
在往这个链表里面添加元素时，得确保这个链表不会很长，否则就导致占用太多资源，而且NA也不能及时的发送出去。所以我们得为这个链表设置一个最大长度，比如64. 如果超出这个值，就直接简单的丢弃掉这个包，这个网络处理的机制是一致的，网络太繁忙处理不过来，所以直接丢弃

由于将所有的NA包都添加到了一个链表中来处理，那么就有可能导致链表很长，然后链表尾部的元素就可能花费N*delay(N为链表里面总的元素数)，这个时间就可能会远大于1s，这就跟RFC的标准不一致。所以得重新思考一个算法，使得确保这个时间小于1S。另外，由于FreeBSD/Linux是非实时的系统，所以还得考虑到这个时间误差。

基于时间的考虑

所谓实时操作系统是指，如果一个任务需要执行，它会立即得到执行，而不会有时间延迟。对于Linux/FreeBSD这类系统而言，任务的执行都是依赖于时钟中断引起的调度，各个任务会有自己的优先级，在调度的时候会根据优先级来选择某一个任务得到执行，而且任务必须得等到时钟中断到来才可能得到执行机会，这就导致Linux/FreeBSD是非实时的。考虑到这个因素，anycast/proxy的delay时间最好设置为一个小于1S的随机时间，比如最大为1s * (8 / 10)。

/* the max members in the anycast_delay_list */
#define ANYCAST_DELAY_MAX_LEN 64
/* anycast/proxy delay list length */
int anycast_delay_len = 0;

struct na_struct_t
{
    ...
    int expire; /*这个包需要延时发送的时刻 */
    TAILQ_ENTRY(na_struct_t) anycast_delay_list; /* 放到一个TAILQ里头 */
};

TAILQ_HEAD(anycast_list_, na_struct_t) anycast_list = TAILQ_HEAD_INITIALIZER(anycast_list);

static struct timer anycast_delay_timer;
static boolean timer_running = false;

nd6_na_input()
{
    ...
    if (anycast || proxy ) {
        int delay = random() % HZ;
        struct na_struct_t *na_arg = set_na(...);
        na_arg->expire = ticks + delay;
        spin_lock(&anycast_list_lock);
        if (anycast_delay_len > ANYCAST_DELAY_MAX_LEN) {
            goto freeit;
        }
        TAILQ_INSERT_TAIL(&anycast_list, na_arg, anycast_delay_list);
        anycast_delay_len++;
        spin_unlock(&anycast_list_lock);
        if (!timer_running) {
            timer_running = true;
            timer_start(&anycast_delay_timer, delay, anycast_delay_handler, (void *)0);
        }

        return;
    }

freeit:
    ...
}

void
anycast_delay_handler(void *arg __unused)
{
    struct na_arg_anycast_delay *na_arg = NULL;
    int now = ticks;
    int delay = 0;
    spin_lock(&anycast_list_lock);
    TAILQ_FOREACH (na_arg, &anycast_list, anycast_delay_list) {
        if (na_arg->expire < now) {  /* already expired. */
            anycast_delay_len--;
            /*send out the NA packet*/
             ...
        } else if (!delay || na_arg->expire - now < na_arg) {
            delay = na_arg->expire - now;
        }
    }
    if (!delay) {
        /* 还有NA需要send， 所以重启定时器 */
        timer_start(&anycast_delay_timer, delay, anycast_delay_handler, (void *)0);
    } else {
        /* 没有NA了，所以NS里面可以启动定时器了 */
        timer_running = false;
    }
    spin_unlock(&anycast_list_lock);
}

一些说明:

在na_struct_t结构里增加了一个expire成员，用来记录该NA包需要被发送的时刻。
在timeout函数里，不是再去取TAILQ的first元素，而是去取所有expire时刻小于当前时刻的元素，即已经expire的NA，然后把它发送出去。同时找出下一个最近要发送的NA，找出它的expire时刻与当前时刻的差值，作为timer的下一个超时时间
ticks是FreeBSD Kernel里头表示时间的一个全局变量，类似于Linux Kernel里的jiffies

Ref

FreeBSD
RFC-2461
Linux Kernel
深入理解Linux网络技术内
深入理解Linux内核

One Man's Yammer