在阅读C standard以及Cpp standard的过程中我们经常可以发现标准中并没有给出明确的行为，取而代之的是//the behavior is undefined.

比如说：

Anything at all can happen; the Standard imposes no requirements. The program may fail to compile, or it may execute incorrectly (either crashing or silently generating incorrect results), or it may fortuitously do exactly what the programmer intended.

From C FAQ

今天看到LLVM blog上有一篇关于C语言中的undefined behavior的介绍，里面推荐了另外一篇文章A Guide to Undefined Behaviors in C and C++

这里简单翻译一些后面那篇文章，作为对这方面的一个总结吧。

Undefined Behavior模型

暂时忽略编译器，只考虑C语言的实现，这种实现符合C语言标准（行为与C虚拟机的行为一致）。如果执行一个程序的过程中，每一步行为都是明确定义的，那么整个过程都是明确定义的。不过，注意就算如此，过程的行为仍然不是唯一的，这里又设计到了未特殊化以及实现确立的行为（在这里忽略）。

如果程序执行过程中有任何一部存在undefined行为，那么整个执行都是“无意义”的。

看一个简单的例子：

#include <limits.h>
#include <stdio.h>
int main (void)
{
printf ("%d\n", (INT_MAX+1) < 0);
return 0;
}

这个程序需要C实现解决一个简单的问题，如果我们在最大可表示出来的整型上加一，是否结果为负数？

$ cc test.c -o test
$ ./test
1

可能得到这样的结果：

$ cc test.c -o test
$ ./test
0

也有可能是：

$ cc test.c -o test
$ ./test
42

还有可能是：

$ cc test.c -o test
$ ./test
Formatting root partition, chomp chomp

可能有人会说编译器行为是不正确的，因为在C标准明确指出关系操作符返回的必须是1或者0.但是因为这里的程序“没有意义”，所以实现时可以做任何编译器想做的事情。

Undefined behavior扰乱了C虚拟机中的所有其他行为。当然最后一个可能性几乎是为零的，但是这些undefined behavior经常导致安全漏洞。

人们常常会说，至少这么认为：

x86下ADD汇编指令是用来实现C中的带符号加法的，那么当结果溢出时，这个指令有两种互补的行为。我现在正在X86下变成，那么至少我能肯定溢出时会出现其中一种语义结果。

这样说是不对的，正如你说：

有些人告诉我在篮球比赛中，可以抱住球然后跑动。我又一个篮球，并且尝试是可以的。明显他是理解篮球比赛规则的。

其实这中情况有点微妙：

1. 有任何C语言实现形式保证实现了这两种互补的行为么？当然有。许多编译器在优化选项关闭时会实现这种行为，如gcc中有一个(-fwrapv)选项用来在任何优化级别下强制使用这种行为。其他编译器默认强制使用。
2. 然而，同样也有某些编译器并没有实现这两种互补行为。
3. 更有甚者，有些编译器（比如GCC）整型溢出的行文已经存在多年，优化器变得更聪明了，导致与整型溢出突然静悄悄的不像想象中那样工作了。

这些当然对于标准来说都是可以接受的，但是对开发者来说这是一种噩梦。不过，这对编译器小组来说在跑分方面是一种胜利。

Undefined Behavior的优缺点：

优点：

1. 唯一的优点就是简化了编译器的工作。让它在某些情况下产生非常有效率的代码。通常这些情况包含紧循环。

缺点：

1. 当程序员对可靠的避免undefined behavior没有信心的时候，通常会造成行为异常的程序。
2. 另外一个不太严重的问题是，或者说是困扰的是，undefined behavior仅仅是为了给编译器小组编写减轻负担，而不是为了获得更高的效率。

从编译器的角度来理解Undefined Behavior

一种关键的深入理解含有Undefined Behavior的语言的方式是编译器只需要尽职尽责的考虑并且完成明确定义的行为。

如果我们假象一个C程序正在被C虚拟机执行，undefined behavior是非常容易理解的：程序中的每个操作不是defined的就是undefined的，并且通常很容易区分。当我们开始关系程序所有可能的执行方式的时候，undefined behavior变得很难处理。程序开发者，通常需要在每种情况下都获得正确结果，因此很在意这些可能性，同样需要在任何可能情况下都生成正确的机器码的编译器开发者也如此。

下面讨论一个程序的所有可能执行方式，首先我们对其进行一定简化，加入如下的一些条件：

• 仅讨论C/C++函数，而不是整个程序
• 假设对任何输入，函数都能结束
• 假设函数的执行是确定性的，如并不和其他线程通过共享内存交互
• 假设我们有无限的资源来完整测试函数，这里的完整测试指的是所有可能的输入都测试。完整测试枚举所有的输入，从最小的输入（根据比特位衡量）开始，测试所有符合输入定义的可能的比特组合。

根据这个测试我们可以得到始终情况：

1. 对于所有输入，行为都是确定的
2. 对于所有输入，某些是确定的，某些不是
3. 对于所有输入，所有都是不确定的

情况一：

对输入无限制，行为都是确定的。通常API级别的函数以及那些处理“未净化数据”的函数应该满足这一类。

例，处理整型除法的应用函数：

int32_t safe_div_int32_t (int32_t a, int32_t b) {
  if ((b == 0) || ((a == INT32_MIN) && (b == -1))) {
    report_integer_math_error();
    return 0;
  } else {
    return a / b;
  }
}

情况三：

这类函数没有明确定义的执行方式。严格来说，这些函数是“无意义“的：编译器甚至不被要求生成一个return标志。那么这种类型真的存在么？是的，而且很常见。

比如说无论输入是什么的时候，函数中只用了一个并没初始化的变量时（这通常在无意间写出）。编译器在识别以及利用这种代码方面变得越来越智能。下面是Google Native Client project中的代码：

When returning from trusted to untrusted code, we must sanitize the return address before taking it. This ensures that untrusted code cannot use the syscall interface to vector execution to an arbitrary address. This role is entrusted to the function NaClSandboxAddr, in sel_ldr.h. Unfortunately, since r572, this function has been a no-op on x86.

-- What happened?

During a routine refactoring, code that once read

aligned_tramp_ret = tramp_ret & ~(nap->align_boundary - 1);

was changed to read

return addr & ~(uintptr_t)((1 << nap->align_boundary) - 1);

Besides the variable renames (which were intentional and correct), a shift was introduced, treating nap->align_boundary as the log2 of bundle size.

We didn't notice this because NaCl on x86 uses a 32-byte bundle size.  On x86 with gcc, (1 << 32) == 1. (I believe the standard leaves this behavior undefined, but I'm rusty.) Thus, the entire sandboxing sequence became a no-op.

This change had four listed reviewers and was explicitly LGTM'd by two. Nobody appears to have noticed the change.

-- Impact

There is a potential for untrusted code on 32-bit x86 to unalign its instruction stream by constructing a return address and making a syscall. This could subvert the validator. A similar vulnerability may affect x86- 64.

ARM is not affected for historical reasons: the ARM implementation masks the untrusted return address using a different method.

到底发生了什么？一个简单的重构将包含这个代码的函数变为了类型三。报告这个问题的人认为x86下gcc会将(1<<32)解释为1，但是这里并没有任何理由确认这个行为是可靠的（实际上一些我试过的x86-gcc并没有这么做）。这样的构造理所当然的是undefined因此编译器可以做任何它想做的事。对于典型的C编译器，并不会产生对应于这个undefined操作的指令（C编译器的首要任务是产生高效率的代码）。

类型二

对于某些输入有确定行为，而对其他的没有。这也是我们要讨论的最有趣的部分。

简单的带符号除法就是一个很好的例子：

int32_t unsafe_div_int32_t (int32_t a, int32_t b) {
  return a / b;
}

这个函数存在前提条件，因为它只能被满足如下条件的参数调用。

(b != 0) && (!((a == INT32_MIN) && (b == -1)))

与类型一的判决条件相似当然不是一个意外。如果调用方违反了这个先决条件，你的程序的含义也遭到破坏。

那么编写这样的，没有细节先决判别条件的函数是否好呢？总体上来说，对于内部使用，这是可以的，只需要有文档指出这种条件的存在。

现在，让我们来看看编译器将这函数编译为object code的工作。编译器执行一个分析：

1. 在如上条件满足的情况下，编译器有责任生成计算a/b的指令
2. 不满足时，编译器并无任何责任

编译器编写者会问自己这样一个问题：最有效的实现下面这两种情形的方法是什么？因为第二种情况并无编译器任何责任产生正确代码，所以最简单的事就是不要考虑它。编译器可以只对第一种情况生成指令。（在Java编译器中，则相反，Java编译器有责任解决第二种情况，虽然在这里是一种特殊情况，程序并不需要运行时的开销，因为预编译器通常可以在除零时提供自陷行为）

在看一个类型二的函数：

int stupid (int a) {
  return (a+1) > a;
}

先决条件是：

(a != INT_MAX)

通常好的编译器只会产生这样的汇编代码：

stupid:
  movl $1, %eax
  ret

但是如果在这儿我们使用-fwrapv标志，告诉GCC，整型溢出有两种互补行为，我们会得到不同的分析结果：

1. a != INT_MAX：有责任返回1
2. a == INT_MAX: 有责任返回0

这样编译器必须生成需要计算而且检查结果的代码:

stupid:
  leal 1(%rdi), %eax
  cmpl %edi, %eax
  setg %al
  movzbl %al, %eax
  ret

同样，Java也需要做同样的操作。

_ZN13HelloWorldApp6stupidEJbii:
  leal 1(%rsi), %eax
  cmpl %eax, %esi
  setl %al
  ret

只需要牢记，编译器的任务就是提供给你满足要求的快速的代码，所以他们会试着忘记undefined behavior，以能够获得最快的速度，然而并不会告诉你到底发生了什么。

一个有趣的分析例子

大约一年前，Linux内核开始使用一个特殊的GCC标识用来告诉编译器避免优化掉无用的空指针。原因代码如下（有修改）：

static void __devexit agnx_pci_remove (struct pci_dev *pdev)
{
  struct ieee80211_hw *dev = pci_get_drvdata(pdev);
  struct agnx_priv *priv = dev->priv; 

  if (!dev) return;

  ... do stuff using dev ...
}

这段代码是为了获取一个device结构体的指针，检查是否为空，然后使用。

但是这里有一个问题！在这个函数中，这个指针在检查是否为空之前就已经进行了引用。

这导致会产生优化的编译器进行下面的分析：

1. dev == NULL:无责任
2. dev != NULL:检查是否为空，一定返回否。因此，此判断语句无意义，可能会被删除。

在两种情况下，判空语句都是无用的，检查语句被删除，造成了安全漏洞的隐患。

当然这里的问题在于在未检查情况下就引用了指针所指向的结构体，所以只需要将检查语句放到上面就可以。不过这得需要这种语句被人工或者使用工具发现，所以如果告诉编译器一些保守方式更好。

有undefined behavior的生活

长期的，不安全的编程语言并不会被mainstream开发者所使用，而是仅将其应用在需要高性能以及低资源的情况下。同时，解决undefined behavior不是完全的直接所以patchwork方法似乎是最好的方法：

• 开启编译器警告，最好使用多种编译器
• 使用静态分析器（比如说Clang's，Coverity,etc..)来获取更多警告
• 使用编译器支持的动态检查，如gcc的-ftrapv标志产生能够使带符号整型溢出时自陷
• 使用类似Valgrind来获得更多的动态检查
• 当函数是类型二时，使用文档记录他们的前提条件以及后续条件
• 使用断言来确认函数的前提条件以及后续条件满足
• 使用高质量的数据结构库（特别是在C++中）

基本的：万分小心，使用优秀的工具，尽力做到最好。

1.内核路由

主要参考了《Understanding Linux Network Internals》

从此图可以看出：

• PF_PACKET处于网络层，与IP协议在同一层
• PF_PACKET通过socket与内核建立通信
• ptype_base包含了各种协议的回调函数(func函数)
• 当链路层（也就是设备驱动，位于drivers/net下）完成接受frame的工作后，将其数据封装到skbuff中，然后轮询ptype_base中的各种协议，然后调用deliver_skb函数，将skb传给上层协议。
• 分析linux转发与openflow使用的PF_PACKET类型的socket主要需要研究两个协议之间的差别
• PF_PACKET类型socket文件位于net/packet/Af_packet.c中
• IP协议位于net/ipv4

此处只讨论旧网络API，NAPI主要解决传输速率较高时，采用轮询+中断方式，与我们要分析的问题关系不大。

驱动程序注册完中断之后，当有包到达时，收到中断，初始化skb然后触发内核softirq（软中断），软中断由

open_softirq(NET_TX_SOFTIRQ, net_tx_action, NULL);

open_softirq(NET_RX_SOFTIRQ, net_rx_action, NULL);

注册。

在软中断中，调用process_backlog（初始化为名为poll的回调函数）。

process_backlog会取出其中的skbuff然后调用netif_receive_skb来处理此skbuff。

在netif_receive_skb中，

list_for_each_entry_rcu(ptype, &ptype_all, list) {
    if (ptype->dev == null_or_orig || ptype->dev == skb->dev ||
        ptype->dev == orig_dev) {
        if (pt_prev)
            ret = deliver_skb(skb, pt_prev, orig_dev);
        pt_prev = ptype;
    }
}

对于ptype_all中的所有协议都调用此协议的func函数，来处理skbuff。
问题：为何此处使用pt_prev?而不是 ptype?

type = skb->protocol;
list_for_each_entry_rcu(ptype,
        &ptype_base[ntohs(type) & PTYPE_HASH_MASK], list) {
    if (ptype->type == type && (ptype->dev == null_or_orig ||
         ptype->dev == skb->dev || ptype->dev == orig_dev ||
         ptype->dev == orig_or_bond)) {
        if (pt_prev)
            ret = deliver_skb(skb, pt_prev, orig_dev);
        pt_prev = ptype;
    }
}

对于ptype_base同样处理。

由下图可以看到，对于每个协议都拷贝了一份skbuff，然后再调用func回调函数。

static inline int deliver_skb(struct sk_buff *skb,
                  struct packet_type *pt_prev,
                  struct net_device *orig_dev)
{
    atomic_inc(&skb->users);
    return pt_prev->func(skb, skb->dev, pt_prev, orig_dev);
}

这里其实只是通过skb->users加一来计算引用。拷贝则由相应的协议回调函数完成。

协议由packet_type表示，通过void dev_add_pack(struct packet_type *pt)注册。

dev_add_pack区分type(ETH_P_ALL | 其他)，分别添加到ptype_all与ptype_base中。

对于IP协议，调用的是ip_rev，然后进行路由或者传递给上层等工作。

下面主要涉及Openflow使用的socket(AF_PACKET)。

2.Openflow处理包

先看看openflow中对socket的使用，在连接switch与host（即除掉连接nox的连接）方面，使用netdev来封装。

int netdev_fd;              /* Network device. */
int tap_fd;                 /* TAP character device, if any, otherwise the
                             * network device. */

其中netdev_fd就是保存了AF_PACKET类型的socket的文件描述符（file descriptor），tap字符设备主要是用来实现点对点的虚拟字符设备（TUN/TAP虚拟网络设备为用户空间程序提供了网络数据包的发送和接收能力）。

然后在do_open_netdev中创建socket。

netdev_fd = socket(PF_PACKET, SOCK_RAW,
                   htons(ethertype == NETDEV_ETH_TYPE_NONE ? 0
                         : ethertype == NETDEV_ETH_TYPE_ANY ? ETH_P_ALL
                         : ethertype == NETDEV_ETH_TYPE_802_2 ? ETH_P_802_2
                         : ethertype));

在轮询中调用了接收包的函数netdev_recv（netdev_recv_wait为阻塞）

if (!strncmp(netdev->name, "tap", 3)) {
    do {
        n_bytes = read(netdev->tap_fd, ofpbuf_tail(buffer),
                       (ssize_t)ofpbuf_tailroom(buffer));
    } while (n_bytes < 0 && errno == EINTR);
}
else {
    do {
        n_bytes = recvfrom(netdev->tap_fd, ofpbuf_tail(buffer),
                           (ssize_t)ofpbuf_tailroom(buffer), 0,
                           (struct sockaddr *)&sll, &sll_len);
    } while (n_bytes < 0 && errno == EINTR);
}

接收的数据保存到buffer中，再进行后续的提取包头，查flow表，转发等

netdev->queue_fd[0] = netdev->tap_fd; （在do_open_netdev函数中)

n_bytes = write(netdev->queue_fd[class_id], buffer->data, buffer->size); （在netdev_send函数中）

 

3.二者之间的联系

4.references

I'm trying hard to learn compiler by reading the Dragon Book and manual of Bison. No previous experience in formal language and automate machine. It's pretty disappointing when understanding the theories. Get prepared for some projects I may come up later for practice. Goals: Understand the theories and read the yacc file of Swig. LR parse: a paser that read input from left to right, also termed as LR(k) where k refers to number of unconsumed "look ahead"(looking ahead a few more input items before making a cost effective decision) input symbols that are used in making parsing decisions. LALR: grammer which requires no more than one symbol of lookahead Bison: 1.Three ways for represent terminal symbols.

• Token type defined in bison file.
• one character literal
• a C string constant

2.Semantic value: all the rest of the information about the meaning of the token. 3.Semantic actions: produce some output based on the input. The action is made up of C statements. 4.%glr-parse stands for GLR(Generalized LR) 5.Overall layout of a Bison grammar:

%{
Prologue
%}

Bison declarations

%%
Grammar rules
%%

Epilogue