use pandoc

1.introduce

Pandoc is a swiss-army knife for coverting files from one markup format into
another, it can convert documents in markdown to HTML or pdf. To see more, knock
this link

2. use

install missing packages on fedora:

su -c 'yum install texlive-titlesec'
su -c 'yum install texlive-titling'
su -c 'yum install texlive-lastpage'

generate pdf file:

pandoc test.md -o test.pdf

using latex to generate pdf file:

pandoc --latex-engine=xelatex  test.md -o test.pdf

generate pdf file by specify template:

pandoc --latex-engine=xelatex --template=/home/dennis/template.latex test.md -o test.pdf

3.reference

Forking and Threading

##Why?

Sometimes, wo need to write some application, which should do multi task, this
time fork thread or multithread will show in our brain. But which one should we
need exactly, I think we should known them more before make decision.

##what?

History:

Linkers:

##Forking vs threading

From: http://www.geekride.com/fork-forking-vs-threading-thread-linux-kernel/

So, finally after long time, i am able to figure out the difference between forking and threading :)

When i have been surfing around, i see a lots of threads/questions regarding forking and threading, lots of queries which one should be used in the applications. So i wrote this post which could clarify the difference between these two based on which you could decide what you want to use in your application/scripts.

What is Fork/Forking:

Fork is nothing but a new process that looks exactly like the old or the parent process but still it is a different process with different process ID and having it’s own memory. Parent process creates a separate address space for child. Both parent and child process possess the same code segment, but execute independently from each other.

The simplest example of forking is when you run a command on shell in unix/linux. Each time a user issues a command, the shell forks a child process and the task is done.

When a fork system call is issued, a copy of all the pages corresponding to the parent process is created, loaded into a separate memory location by the OS for the child process, but in certain cases, this is not needed. Like in ‘exec’ system calls, there is not need to copy the parent process pages, as execv replaces the address space of the parent process itself.
Few things to note about forking are:

  • The child process will be having it’s own unique process ID.
  • The child process shall have it’s own copy of parent’s file descriptor.
  • File locks set by parent process shall not be inherited by child process.
  • Any semaphores that are open in the parent process shall also be open in the child process.
  • Child process shall have it’s own copy of message queue descriptors of the parents.
  • Child will have it’s own address space and memory.

Fork is universally accepted than thread because of the following reasons:

  • Development is much easier on fork based implementations.
  • Fork based code a more maintainable.
  • Forking is much safer and more secure because each forked process runs in its own virtual address space. If one process crashes or has a buffer overrun, it does not affect any other process at all.
  • Threads code is much harder to debug than fork.
  • Fork are more portable than threads.
  • Forking is faster than threading on single cpu as there are no locking over-heads or context switching.

Some of the applications in which forking is used are: telnetd(freebsd), vsftpd, proftpd, Apache13, Apache2, thttpd, PostgreSQL.

Pitfalls in Fork:

  • In fork, every new process should have it’s own memory/address space, hence a longer startup and stopping time.
  • If you fork, you have two independent processes which need to talk to each other in some way. This inter-process communication is really costly.
  • When the parent exits before the forked child, you will get a ghost process. That is all much easier with a thread. You can end, suspend and resume threads from the parent easily. And if your parent exits suddenly the thread will be ended automatically.
  • In-sufficient storage space could lead the fork system to fail.

What are Threads/Threading:

Threads are Light Weight Processes (LWPs). Traditionally, a thread is just a CPU (and some other minimal state) state with the process containing the remains (data, stack, I/O, signals). Threads require less overhead than “forking” or spawning a new process because the system does not initialize a new system virtual memory space and environment for the process. While most effective on a multiprocessor system where the process flow can be scheduled to run on another processor thus gaining speed through parallel or distributed processing, gains are also found on uniprocessor systems which exploit latency in I/O and other system functions which may halt process execution.

Threads in the same process share:

  • Process instructions
  • Most data
  • open files (descriptors)
  • signals and signal handlers
  • current working directory
  • User and group id

Each thread has a unique:

  • Thread ID
  • set of registers, stack pointer
  • stack for local variables, return addresses
  • signal mask
  • priority
  • Return value: errno

Few things to note about threading are:

  • Thread are most effective on multi-processor or multi-core systems.
  • For thread – only one process/thread table and one scheduler is needed.
  • All threads within a process share the same address space.
  • A thread does not maintain a list of created threads, nor does it know the thread that created it.
  • Threads reduce overhead by sharing fundamental parts.
  • Threads are more effective in memory management because they uses the same memory block of the parent instead of creating new.

Pitfalls in threads:

  • Race conditions: The big loss with threads is that there is no natural protection from having multiple threads working on the same data at the same time without knowing that others are messing with it. This is called race condition. While the code may appear on the screen in the order you wish the code to execute, threads are scheduled by the operating system and are executed at random. It cannot be assumed that threads are executed in the order they are created. They may also execute at different speeds. When threads are executing (racing to complete) they may give unexpected results (race condition). Mutexes and joins must be utilized to achieve a predictable execution order and outcome.
  • Thread safe code: The threaded routines must call functions which are “thread safe”. This means that there are no static or global variables which other threads may clobber or read assuming single threaded operation. If static or global variables are used then mutexes must be applied or the functions must be re-written to avoid the use of these variables. In C, local variables are dynamically allocated on the stack. Therefore, any function that does not use static data or other shared resources is thread-safe. Thread-unsafe functions may be used by only one thread at a time in a program and the uniqueness of the thread must be ensured. Many non-reentrant functions return a pointer to static data. This can be avoided by returning dynamically allocated data or using caller-provided storage. An example of a non-thread safe function is strtok which is also not re-entrant. The “thread safe” version is the re-entrant version strtok_r.

Advantages in threads:

  • Threads share the same memory space hence sharing data between them is really faster means inter-process communication (IPC) is real fast.
  • If properly designed and implemented threads give you more speed because there aint any process level context switching in a multi threaded application.
  • Threads are really fast to start and terminate.

Some of the applications in which threading is used are: MySQL, Firebird, Apache2, MySQL 323

FAQs:

  1. Which should i use in my application ?
    Ans: That depends on a lot of factors. Forking is more heavy-weight than threading, and have a higher startup and shutdown cost. Interprocess communication (IPC) is also harder and slower than interthread communication. Actually threads really win the race when it comes to inter communication. Conversely, whereas if a thread crashes, it takes down all of the other threads in the process, and if a thread has a buffer overrun, it opens up a security hole in all of the threads.
    which would share the same address space with the parent process and they only needed a reduced context switch, which would make the context switch more efficient.

  2. Which one is better, threading or forking ?
    Ans: That is something which totally depends on what you are looking for. Still to answer, In a contemporary Linux (2.6.x) there is not much difference in performance between a context switch of a process/forking compared to a thread (only the MMU stuff is additional for the thread). There is the issue with the shared address space, which means that a faulty pointer in a thread can corrupt memory of the parent process or another thread within the same address space.

  3. What kinds of things should be threaded or multitasked?
    Ans: If you are a programmer and would like to take advantage of multithreading, the natural question is what parts of the program should/ should not be threaded. Here are a few rules of thumb (if you say “yes” to these, have fun!):

  • Are there groups of lengthy operations that don’t necessarily depend on other processing (like painting a window, printing a document, responding to a mouse-click, calculating a spreadsheet column, signal handling, etc.)?
  • Will there be few locks on data (the amount of shared data is identifiable and “small”)?
  • Are you prepared to worry about locking (mutually excluding data regions from other threads), deadlocks (a condition where two COEs have locked data that other is trying to get) and race conditions (a nasty, intractable problem where data is not locked properly and gets corrupted through threaded reads & writes)?
  • Could the task be broken into various “responsibilities”? E.g. Could one thread handle the signals, another handle GUI stuff, etc.?

Conclusions:

  • Whether you have to use threading or forking, totally depends on the requirement of your application.
  • Threads more powerful than events, but power is not something which is always needed.
  • Threads are much harder to program than forking, so only for experts.
  • Use threads mostly for performance-critical applications.

References:

Raspberry Pi

What is it?

The Raspberry Pi is a credit-card-sized single-board computer developed in the
UK by the Raspberry Pi Foundation with the intention of promoting the teaching
of basic computer science in schools.

What it use for?

  • Media streamer
  • Web server
  • video monitor
  • Download tool

What is the show now?

What is more in the future?

Reference

Hacking Linux Kernel

##1. Introduce

  • How to hack the Linux kernel.
  • Stuffs related to Linux kernel development.
  • Useful tools for Linux kernel development.
  • The developing cycle of Linux kernel.

##2. Where is Linux kernel?

##3. Stable Release

  • 2.6.x kernels are maintained by Linus Torvalds.
  • 2.4.x kernels are maintained by Marcelo Tosatt.
  • 2.2.x kernels are maintained by Alan Cox.
  • 2.0.x kernels are maintained by David Weinehall.
  • -stable kernels are maintained by Greg KH.

##4. Patch

  • How to write a patch
  • Apply the patch
  • Patch format

##5. Mailing lists

  • The main list: lkml@vger.kernel.org
  • Read the LKML FAQ before you subscribe.
  • Linux filesystem development: linux-fsdevel@vger. kernel.org
  • linux-netdev: netdev@vger.kernel.org

##6. Advice

  • Alan Cox: “Ignore everyone who tells you kernel hacking is hard, special or
    different. It’s a large program, and bug fixing or driver tweaking can be a
    best starting point. It is however not magic, nor written in a secret language
    that only deep initiates with beards can read.”
  • Be persistent, be patient, please.

##7. module compile
compile dirver “target” for linux-3.10.0-123.el7 :

  • Download kernel code kernel-3.10.0-123.el7.src.rpm
  • rpm -ivh kernel-3.10.0-123.el7.src.rpm
  • cp ~/rpmbuild/SOURCES/linux-3.10.0-123.el7.tar.xz /root/
  • tar xvf linux-3.10.0-123.el7.tar.xz
  • cd /root/linux-3.10.0-123.el7
  • make oldconfig && make prepare
  • make scripts
  • make CONFIG_ISCSI_TARGET=m -C /root/linux-3.10.0-123.el7 M=drivers/target/iscsi

##8. debug
Enable pr_debug macro function:

  • vim /root/linux-3.10.0-123.el7 M=drivers/target/iscsi/Makefile
  • Add code list below:(equal to add #define DEBUG to the file_name.c)

    CFLAGS_iscsi_target_parameters.o := -DDEBUG
    CFLAGS_iscsi_target_seq_pdu_list.o := -DDEBUG
    CFLAGS_iscsi_target_tq.o := -DDEBUG
    CFLAGS_iscsi_target_auth.o := -DDEBUG
    CFLAGS_iscsi_target_datain_values.o := -DDEBUG
    CFLAGS_iscsi_target_device.o := -DDEBUG
    CFLAGS_iscsi_target_erl0.o := -DDEBUG
    CFLAGS_iscsi_target_erl1.o := -DDEBUG
    CFLAGS_iscsi_target_erl2.o := -DDEBUG
    CFLAGS_iscsi_target_login.o := -DDEBUG
    CFLAGS_iscsi_target_nego.o := -DDEBUG
    CFLAGS_iscsi_target_nodeattrib.o := -DDEBUG
    CFLAGS_iscsi_target_tmr.o := -DDEBUG
    CFLAGS_iscsi_target_tpg.o := -DDEBUG
    CFLAGS_iscsi_target_util.o := -DDEBUG
    CFLAGS_iscsi_target.o := -DDEBUG
    CFLAGS_iscsi_target_configfs.o := -DDEBUG
    CFLAGS_iscsi_target_stat.o := -DDEBUG
    CFLAGS_iscsi_target_transport.o := -DDEBUG
    
  • Go the this page for more https://www.kernel.org/doc/local/pr_debug.txt

  • Also, you can using printk(KERN_DEBUG "LIO: get auth from line 140\n"); to your source code.

##Reference:

Linux protocol stack

From http://www.cnblogs.com/image-eye/category/347518.html

网络协议栈0:从一个例子开始

最近因工作需要写一个网卡驱动,晕倒,没有任何网络知识,就写网络驱动!

可是,为了五斗米糊口,不得不从啊

于是,打算从网络协议栈开始,把网络搞一搞。

我们常常知道socket的用法(其实我还没有真正的写过socket代码,常常都是指那些socket高手了^-^),因此,打算从一个常用的实例开始,把网络协议栈整理一下,即把自己的学习经过进行记录,看看菜鸟的轨迹,是如何拐弯,颠簸。

通常的socket编程分两部分吧(错了别怪我,我不是高手),一是client部分,二是server部分,而更通常的情况是我们都以写client的任务为多,因此,从简单下手,当然选择client端开始了。

下面的代码,就是随便一个网站都能搜索到的client端的代码,我就毫不客气的复制了,谁叫我是菜鸟:

#include <stdio.h>
#include <sys/socket.h>
#include <unistd.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <sys/socket.h>
#include <sys/wait.h>
#include <unistd.h>
#include <netdb.h>
#include <time.h>


#define SERVER_PORT 20000 // define the defualt connect port id
#define CLIENT_PORT ((20001+rand())%65536) // define the defualt client port as a random port

#define BUFFER_SIZE 255
#define REUQEST_MESSAGE "welcome to connect the server./n"

void usage(char *name)
{
    printf("usage: %s destinationIpAddr\n",name);
}

int main(int argc, char **argv)
{    
    int clifd,length = 0;
    struct sockaddr_in servaddr,cliaddr;
    socklen_t socklen = sizeof(servaddr);
    char *serv_ip="192.168.1.235";
    char buf[BUFFER_SIZE];

    /*       if (argc < 2)
             {
             usage(argv[0]);
             exit(1);
             }
     */      
    if ((clifd = socket(AF_INET,SOCK_STREAM,0)) < 0)
    {
        printf("create socket error!/n");
        exit(1);
    }
    srand(time(NULL));//initialize random generator
    bzero(&cliaddr,sizeof(cliaddr));
    cliaddr.sin_family = AF_INET;
    cliaddr.sin_port = htons(CLIENT_PORT);
    cliaddr.sin_addr.s_addr = inet_addr("192.168.0.234");//htons(INADDR_ANY);

    bzero(&servaddr,sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    inet_aton(serv_ip/*argv[1]*/,&servaddr.sin_addr);
    servaddr.sin_port = htons(SERVER_PORT);
    //servaddr.sin_addr.s_addr = htons(INADDR_ANY);

    if (bind(clifd,(struct sockaddr*)&cliaddr,sizeof(cliaddr))<0)
    {
        printf("bind to port %d failure!/n",CLIENT_PORT);
        exit(1);
    }

    if (connect(clifd,(struct sockaddr*)&servaddr, socklen) < 0)
    {
        printf("can't connect to %s!/n",/*argv[1]*/serv_ip);
        exit(1);
    }

    length = recv(clifd,buf,BUFFER_SIZE,0);
    if (length < 0)
    {
        printf("error comes when recieve data from server %s!",/*argv[1]*/serv_ip);
        exit(1);
    }
    printf("from server %s :/n/t%s ",/*argv[1]*/serv_ip,buf);
    int rc;
    rc=send(clifd,"some messages",strlen("some messages"),0);
    if(rc < 0)
    {
        printf("error comes when recieve data from server %s!",/*argv[1]*/serv_ip);
        exit(1);
    }
    close(clifd);
    return 0;
}

标准的菜鸟格式,当然,我也是经过了编译,确认了代码的可执行(fedora6下),并且跟服务器交互正常。

一样的三步曲,不一样的曲折。

socket编程,常规的就是

1.socket()

2.bind()

3.connect()

成功之后,就是随意的发送,接收数据了。

只是,上面这三步,干了什么活,就把两个互不相干的IP链接起来,这么牛?

网络协议栈13:Connect函数分解之链路层

Skb_buff数据包从IP层下传到链路层后,链路层开始对数据包进行处理

首先,判断skb_buff数据包是不是不在skb_buff链表中,如果还在(即skb_buff->next!=NULL),则说明上面的处理有问题,代码要避开(人为的避开,代码还是有问题),即不能发送这个数据包,处理方式是,指定发送数据包的设备被指定为NULL,即数据包没有设备真实发送。

第二步,判断是否已知下一跳的MAC地址,即skb->arp=1,如果不是,则需要调用arp_find来查找IP地址对应的MAC地址,如果找不到,则直接返回,不再进行发送。

第三步,前面两步都正常了,则说明数据包正常,此时判断数据是否是刚刚下传的本地数据包,是则把数据包按照优先级的级别再次进行排队,这里分三种优先级,每个优先级都是一个队列,数据包按照相应的优先级被插入对应优先级的队列的尾部。

第四步,从最高优先级队列头部获得一个数据包,这个数据包有可能不是刚刚下传的数据包,如果下传的数据包大于发送的数据包,或者有重传的数据包,则此时获得的数据包就是先前的数据包。

第五步,把刚获得数据包进行发送(调用网卡驱动中的发送函数进行发送,到这里才是网卡驱动工作的开始),如果发送成功,就直接返回了,如果发送不成功,则把这个数据包插入到相应优先级的队列的头部,后面发送时它是相应对了中最先得到发送的数据包。

由于网卡各式各样,没有办法进行抽象,因此,网卡的驱动被开发出来,只需要调用相应的上层函数,再把网卡的功能集合到网络协议栈中,行程完整的协议栈。

其中,第二步中,如果目的端IP对应的MAC地址还没有(或者下一跳),会使用arp_find来查找对应IP地址对应的MAC地址,其大致过程是:

ARP会在本地有一个ARP缓存,所谓的ARP缓存,在实现上采用数组加链表(或者称为队列)的方式,每个 ARP缓存表项由一个 arp_table 结构表示,所以数组中每个元素就指向一个 arp_table 结构类型的链表。对于具体数组元素的寻址由被解析的 IP 地址通过 Hash 算法而得。所以查询 ARP 缓存的过程就可表述为:首先根据被解析 IP地址索引数组中对应元素指向的 arp_table 结构链表,然后遍历该链表,对 IP地址进行匹配,如果查找一个 IP地址精确匹配的表项,则返回该表项,如果没有寻找到,则表示当前 ARP 缓存中没有对应表项,系统此时将创建一个新的 ARP表项,并发出 ARP请求报文,而当前发送的数据包就被缓存到该表项设置的数据包缓存队列中,当接收到 ARP 应答报文时,一方面完成原先表项的创建(硬件地址字段的初始化) ,另一方面将该表项中之前缓存的所有待发送数据包发送出去。结构图如下:

Arp_table结构体如下:

struct arp_table
{
    struct arp_table     *next;            /*next 字段用于 arp_table结构之间的相互串接,构成一个链表。*/
    unsigned long        last_used;        /*last_used 字段表示该表项上次被使用的时间*/
    unsigned int         flags;            /*flags 字段用于维护 ARP 表项的一些标志位,如表项当前所处状态,可以为以后的 ARP 缓存表项的功能扩展做好准备。 */
    unsigned long        ip;               /*ip 字段表示表项所表示映射关系中的 IP地址*/
    unsigned long        mask;             /*mask 字段为对应 IP地址的网络掩码。*/
    unsigned char        ha[MAX_ADDR_LEN]; /*ha 字段表示映射关系中的硬件地址*/
    unsigned char        hlen;             /*hlen 为硬件地址长度*/
    unsigned short       htype;            /*htype 为硬件地址类型*/
    struct device        *dev;             /*dev 字段表示该 ARP 表项绑定的网络设备,对于只有一个网络接口的主机,所有数据包的发送当然只有一个发送通道,但对于具有两个或者更多网络接口的主机,数据包就有多种可能的选择,如果每次发送时都进行发送接口的查询会不必要的增加系统开销,由于数据帧创建中链路层首部的创建都需要进行硬件地址解析,即查询 ARP缓存,所以在 ARP表项中维护一个对应发送接口的指针, 就可以在进行数据帧创建时一并解决通过哪个网络接口发送数据包的问题。另外对于多个网络接口的主机,每个网口都接在不同的网络上,而远端主机只可能属于一个网络,所以我们在进行 ARP 表项创建时可以知道这个主机属于哪个网络,从而初始化接入该网络的网口设备指针。由此可见,ARP 缓存表项中 dev 字段值将来自于路由表项。而路由表项要么是手工配置,要么根据运行路由协议创建,而根据接收路由数据包的网络接口我们可以进行路由表项中网口设备字段的初始化。*/
    struct timer_list    timer;            /*timer 字段用于定时重发 ARP 请求数据包,以防止 ARP 请求未得到响应。*/
    int                  retries;          /*重发次数,当前设置的最大次数为 3,由 ARP_MAX_TRIES 变量表示*/
    struct sk_buff_head  skb;              /*最后一个字段 skb 表示暂时由于 IP 地址到硬件地址的解析未完成而被缓存的数据包队列该字段的具体使用在下文中介绍到相关函数时进行说明。*/   
};

而arp缓存数组定义如下:

#define ARP_TABLE_SIZE  16
#define FULL_ARP_TABLE_SIZE (ARP_TABLE_SIZE+1)
struct arp_table *arp_tables[FULL_ARP_TABLE_SIZE] =
{
    NULL,
};

系统就是通过上述的结构体和数组来管理ARP缓存的

网络协议栈14:Connect函数分解之网卡发送/接收数据流程

链路层经过对数据包的优先级进行排队后,把本次需要发送的数据包从优先级最高的队列的头部抽取出来,并下传给网卡驱动程序的数据发送函数,一般命名为xxx_hard_xmit(),由于硬件各个不同,写法也会各个不同,无法抽象出一个标准的写法,但其流程、目的是不变的,是可以抽像出来的,大致的流程如下:
1.通过设备结构体net_device中的tbusy(transmit busy)来判断网卡现在是否忙,如果等于1,表示网卡在忙,即目前仍然有数据在传输数据,此时是不能传输数据的,而是判断是否超时,如果未超时,则表示网卡正在忙,正在发送数据包,此时直接返回;如果是超时了,则重新初始化相关寄存器,之后设置 tbusy=0,然后继续下面的步骤。
2.设置tbusy = 1,准备传输数据,因为经过这样的设置,下面如果有数据需要发送时,遇到tbusy = 1,就会像重复第一步的判断。
3.硬件开始传输数据包,此时,主要是通过对网卡的寄存器的操作来完成的,一般的,我们会提供需要传送的数据的地址,以及数据的长度,然后经过芯片的寄存器把这些数据发送出去。
4.发送数据是一个for循环进行,一直发送,直到数据发送完才结束。结束发送数据后,就要把刚刚传过来的数据包释放掉,把相关的内存回收,以备后面继续使用。
5.最后,修改设备的一些统计信息,完成本次传输。

到此,connect函数从数据包的层层打包,传输,到最后从网卡上发送出去的流程,就完成了本地的所有传输,此后的数据,经过以太网的转发,送往远端的目的IP地址,此时,connect函数就开始睡眠,等待确认数据从远方传递回来。

Connect函数在等待确认数据的到达,即需要解决的问题是,数据如何从网卡被上传到链路层。这个过程也因为网卡的硬件各个不同,而无法有标准写法,只有一个标准的流程。

1.当网卡接收到了一个完整的数据包后(硬件完成接收,而且是一个完整的数据包,即意味则网卡本身是有buffer的,是可以临时存储数据的),会发生一个中断信号给系统,这个中断信号是系统在启动时,由BIOS记录了跟一个中断处理程序关联到一起的,自然的,下面就是调用这个中断处理程序,来处理中断了。

2.通过设备结构体net_device中的interrupt成员来判断网卡现在是否忙,如果interrupt = 1,表示有其他进程在运行中断处理程序,则退出,否则,继续下面的步骤。

3.设置interrupt = 1,表示本进程在使用中断处理程序,其他的进程暂时不能使用。

4.读取中断状态寄存器,根据状态寄存器判断中断发生的原因。有两种原因,一种是有新的数据包到达,另一种是上次传输的数据已经传输完成。

5.如果有新的数据包到达,则调用接收数据包的子函数来接收数据。

6.如果是上次数据传输完成引起的,则通知协议的上层,修改接口的统计数据,关闭tbusy标志位,为下次传输做准备。

7.关闭标志位interrupt,表示本中断使用完成,现在其他进程可以使用中断处理函数了。

其中的第五步的调用子函数来接收数据的过程大致如下:

1.申请skb缓冲区给准备接收的数据包,用于存储数据包

2.从硬件中读取数据到skb缓冲区

3.调用netif_rx()函数,把数据送往链路层。

4.修改接口的统计数据。

网络协议栈15:网卡接收/发送数据基础知识

网卡本身是有内存的,每个网卡一般都有4K以上的内存,用来发送,接收数据。

数据在从主内存搬到网卡之后,不是立即就能被发送出去的,而是要先在网卡自身的内存中排队,再按照先后顺序发送;同样的,数据从以太网传递到网卡时,网卡也是先把数据存储到自身的内存中,等到收到一帧数据了,再经过中断的方式,告诉主CPU(不是网卡本身的微处理器)把网卡内存的数据读走,而读走后的内存,又被清空,再次被使用,用来接收新的数据,如此循环往复。
而网卡本身的内存,又多是按照256字节为1页的方式,把所有内存分页,之后把这些页组成队列,大致的结构如图:

一般会划分一小部分页面作为发送数据用的,大部分用于接收网络数据,大致如图:

蓝色部分为发送数据用的页面总和,总共只有6个页面用于发送数据(40h~45h);剩余的46h~80h都是接收数据用的,而在接收数据内存中,只有红色部分是有数据的,当接收新的数据时,是向红色部分前面的绿色中的256字节写入数据,同时“把当前指针”移动到+256字节的后面(网卡自动完成),而现在要读的数据,是在“边界指针”那里开始的256字节(紫色部分),下一个要读的数据,是在“下一包指针”的位置开始的256字节,当256字节被读出来了,就变成了重新可以使用的内存,即绿色所表示,而接收数据,就是把可用的内存拿来用,即变成了红色,当数据写到了0x80h后,又从0x46h开始写数据,这样循环,如果数据满了,则网卡就不能再接收数据,必须等待数据被读出去了,才能再继续接收。

下面是一些网卡常用的寄存器:

CR(command register)—命令寄存器

TSR(transmit state register)—发送状态寄存器

ISR(interrupt state register)—-中断状态寄存器

RSR(receive state register)—接收状态寄存器

RCR(receive configure register)—接收配置寄存器

TCR(transmit configure register)—发送配置寄存器

DCR(data configure register)—数据配置寄存器

IMR(interrupt mask register)—中断屏蔽寄存器

NCR(non-coding region)—包发送期间碰撞次数

FIFO(first in first out)

CNTR0(counter register)— 帧同步错总计数器

CNTR1—CRC错总计数器

CNTR2—丢包总计数器

PAR0~5(physical address register)—本地MAC地址

MAR0~7(multiple address register)—多播地址匹配

PSTOP(page stop register)—结束页面寄存器

PSTART(page start register)—开始页面寄存器

BNRY(boundary register)—-边界页寄存器

CURR(current page register)—当前页面寄存器

CLDA0,1(Current Local DMA Address)—当前本地DMA寄存器

TPSR(Transmit page start register)—传送页面开始寄存器

TBCR0,1(transmit byte counter register)—传送字节计数寄存器

CRDA0,1(current remote DMA address)—当前远程DMA寄存器

RSAR0,1(remote start address register)—远程DMA起始地址寄存器

RBCR0,1(remote byte counter register)—远程字节计数寄存器

BPAGE(BROM page register)—BROM页面寄存器

网络协议栈16:connect函数分解之链路层接收数据

Connect函数在发送了数据之后,就进入了休眠等待的状态,等待远方发过来的数据来确认链接是否成功。那么数据是如何从网卡那里传递到链路层?

数据在网卡的内存中,形成了以256字节为1页的环形缓冲链,每当有数据到达,网卡就会发生一个中断信号,告诉CPU已经有数据到达,此时,CPU通过DMA的方式,去读取网卡内存中的数据,并把数据存放在一个专门开辟来接收这个数据包的skb_buff中,之后,就把接收数据的skb_buff进行排列,并且累加所有skb_buff的个数,如果超过一定的数量在排队等待被取走,则后面不能再继续从网卡中读取数据包,以防止系统内存被过度的消耗掉。因此,在数据链路层,skb_buff是被排成一个队列,达到FIFO的目的。

一般接收数据都是在中断中完成,而中断时需要快速的进行处理,以免消耗系统过多的资源,因此,把数据进行队列排队后,就要离开中断处理函数了,此时,需要启动中断程序的后半部来进行剩余的数据的处理。 net_bh()函数是接收中断处理函数的后半部处理函数,其主要的工作是

1.把还在链路层中排队,还没有发送出去的数据包发送送出去(可见发送数据包是很重要的)。

2.把在接收队列中排队的数据包的上层协议类型都找出来,准备把数据发送往对应的协议层(遍历协议类型链表,即struct packet_type所组成的链表,来找到需要发送的数据包所对应的上层协议)。

3.调用相应的上层协议的接收函数来接收数据包。

上层协议的接收函数,是在操作系统初始化的时候,就已经初始化好了,其实就是注册

struct packet_type {
  unsigned short type;       /* This is really htons(ether_type). */
  struct device *dev;
  int (*func) (struct sk_buff *, struct device *, struct packet_type *);
  void *data;
  struct packet_type  *next;
};

这样的结构体(比如static struct packet_type ip_packet_type,static struct packet_type arp_packet_type),其中的func指针所指向的,就是type所确定的协议类型的接收函数,type可取类型如下

#define ETH_P_LOOP  0x0060           /* Ethernet Loopback packet     */
#define ETH_P_ECHO  0x0200           /* Ethernet Echo packet         */
#define ETH_P_PUP   0x0400           /* Xerox PUP packet             */
#define ETH_P_IP    0x0800           /* Internet Protocol packet     */
#define ETH_P_ARP   0x0806           /* Address Resolution packet    */
#define ETH_P_RARP  0x8035           /* Reverse Addr Res packet      */
#define ETH_P_X25   0x0805           /* CCITT X.25                   */
#define ETH_P_ATALK 0x809B           /* Appletalk DDP                */
#define ETH_P_IPX   0x8137           /* IPX over DIX                 */
#define ETH_P_802_3 0x0001           /* Dummy type for 802.3 frames  */
#define ETH_P_AX25  0x0002           /* Dummy protocol id for AX.25  */
#define ETH_P_ALL   0x0003           /* Every packet (be careful!!!) */
#define ETH_P_802_2 0x0004           /* 802.2 frames                 */
#define ETH_P_SNAP  0x0005           /* Internal only                */

网络协议栈17:connect函数分解之网络层接收数据处理

链路层经过对上层协议的检查,把数据包上传到了对应的上层协议层,在这里,就是IP层协议。

数据到达IP层后,IP层需要进行相应的检查,判断后,才决定是否需要把数据上传到上层。下面就是IP层所需要做的事情.

1.首先检测数据包的IP首部是否正确,即对数据包的IP部分的IP首部长度,版本,数据包的大小进行检查,如果符合要求,则继续进行下面的步骤,不符合要求,则释放数据包,直接退出

2.检测IP首部是否包含了选项部分,方法就是查看IP首部的总长度字段是否大于IP首部的长度,如果是,则需要把选项部分解析,这个选项部分会在上传到上层协议时就告知是否有选项的。

3.检测数据包是否是一个分片数据,如果是一个分片数据,则需要分配一个空间,把这个数据包预存起来,同时等待所有数据包的到达后,把所有分片数据重组,才返回这个完整的数据包。如果不是,则直接返回,相当于等待所有分片数据并完成重组。

4.检测是否是多播的数据包,如果是多播的数据包,则再检测这个数据包是否在多播组中,如果是,就接收这个数据包,如果不是,则放弃接收。如何检测本地IP是否是多播组中的一员,主要是遍历当前设备的多播组链表,如当前设备所维护的多播组链表中是有本次传输的目的IP,则表示本IP是多播组的一员,可以接收数据。

5.检测本次数据包对应的上层协议,主要是遍历struct inet_protocol这个链表而得知,因为struct inet_protocol这个链表在系统初始化时,把igmp_protocol / icmp_protocol / udp_protocol / tcp_protocol 等等这些上层协议都链接好,现在只需要遍历,即可找到对以的上层协议,即可调用对应上层协议的接收函数来接收数据,对以connect函数,IP上面的协议就是TCP协议,其所对以的struct inet_protocol结构体:

static struct inet_protocol tcp_protocol = {
    tcp_rcv,     /* TCP handler        */
    NULL,        /* No fragment handler (and won't be for a long time) */
    tcp_err,     /* TCP error control  */
    NULL,        /* next               */
    IPPROTO_TCP, /* protocol ID        */
    0,           /* copy               */
    NULL,        /* data               */
    "TCP"        /* name               */
};

而接收函数就是tcp_rcv(),系统就是调用这个函数来接收IP上传的数据

Face to face office

From http://www.douban.com/note/221426825/

面对面的办公室——纪念艾伦•图灵百年诞辰 1912.6.23-2012.6.23

(载于《上海文化》2012年第5期)

##一、左边的办公室

冯•诺伊曼教授每年换一部新凯迪拉克。早上十点,他把爱车停在帕尔玛物理实验室门口,神采奕奕地走进隔壁数学系的办公室。那时候普林斯顿高等研究院才刚成立,和数学系挤在一幢叫作Fine Hall的楼—— “还不错的楼”。冯•诺伊曼教授总是穿一身笔挺的西装,以免别人把他错当成学生。他太年轻,三十出头,却已经到达了学术顶峰,和五十多岁的物理学家爱因斯坦、数学家维布伦(Oswald Veblen)、数学家亚历山大(James Alexander)一起成了高等研究院最初任命的四位教授。

John von Neumann, 1903-1957

十八岁那年,他犹太裔的父母试图把长子拉出对数学的执迷学些更实际的东西,于是他们达成了妥协,冯•诺伊曼同时在三所大学注册:在苏黎士联邦理工学院(ETH)学习化学工程,每晚完成柏林大学数学专业的作业,在每个学期末回布达佩斯大学参加他从没上过课的数学考试。二十二岁那年他不但从苏黎士联邦理工拿到化学工程学位,还通过了大卫•希尔伯特坐镇的数学博士答辩。整场答辩希尔伯特只问了一个问题:“我从来没见过这么漂亮的晚礼服,你的裁缝是谁?”于是,大家都知道了,希尔伯特钦点的年轻人,不但写了完美的博士论文,还是个翩翩佳公子。

博士毕业后的三年,高产的三年!他在柏林大学和汉堡大学的三年一共发表了二十五篇论文!包括一本八十年后仍然重印的量子力学教科书,可是……对于这个高速前行的天才这些光荣也已经是陈年往事。二十七岁上,纳粹刚刚抬头而美国也恰好走出了大萧条,维布伦代表普林斯顿去欧洲招兵买马,工资开价是冯•诺伊曼在德国挣的八倍还多。踏进美利坚第一天,他打趣地对同行的匈牙利老乡维格纳(Eugene Wigner, 1963年诺贝尔物理学奖)说:“我们该让自己更像美国人。”当即,维格纳改名叫“尤金”(Eugene),冯•诺伊曼改名叫“约翰”(John),和稍微熟一点的人就勾肩搭背地说“你们叫我强尼(Johnny)吧。”

强尼,强尼。强尼•冯•诺伊曼就不着痕迹地混进了满大街都是强尼的美利坚大熔炉,还有谁知道他刚出生时那个卑微的匈牙利名“亚诺斯”(Janos) ?还有谁知道他在德国那几年日耳曼化的“约汉纳”(Johann)? 不过他改了名字,却死活不肯把姓氏里的“冯”去掉。二十几年前他有钱的犹太老爸向行将就木的老皇帝弗朗茨•约瑟夫买了这个贵族称号,于是带着暴发户气息的诺依曼家族就转眼变成了代代相传的贵族冯•诺伊曼,多亏奥匈帝国国库空虚等钱用,否则十足的犹太血统怎么能捐上这个高贵的名头?一到周末冯•诺伊曼肯定请教授们上他宽敞奢侈的大宅喝酒跳舞,宾客盈门杯觥交错, “冯•诺伊曼请客谁不去!”讲出这话,就好象请客做东的是奥匈帝国的某个最尊贵的日耳曼裔公爵。

##二、右边的办公室

冯•诺伊曼教授对面的办公室坐着博士生艾伦•图灵。开朗外向的冯•诺伊曼教授和孤僻紧张的图灵没什么闲话好聊,只知道这个总穿一身乱糟糟运动衫的年轻人前几天差点把自己的那部二手福特车倒车进了卡耐基湖。冯•诺伊曼教授横穿大西洋必买头等舱,常年西装革履,每年换一部崭新的凯迪拉克,略略发福,讨厌运动,有一次妻子想让他学滑雪他恼羞成怒甚至以离婚威胁。与他恰恰相反,博士生图灵则在几个月前坐着末等甲板舱从英国漂到美国。他常年一件套头衫,开一部状况堪忧的二手福特,身材瘦削,热爱运动,是跑赢过奥运会选手的马拉松健将。一到周末,他和同学打垒球比赛,分成两个队,“大英帝国队”对决“叛变殖民地队”。

Alan Turing, 1912-1954

刚来普林斯顿那会儿他不是没试过去交朋友,拥抱新生活,可是上个月当一名卡车司机理所当然地把自己油腻腻的手搭在他肩上直呼其名和他侃大山时,堂堂剑桥大学国王学院的毕业生着实为这种粗鲁的风气吓了一跳。别误会了,他不像冯•诺伊曼教授那样公子派头,他爸爸不过是大英帝国驻印度的一个小公务员,可是英伦岛国的教养让他觉得一个陌生人把脏手搭在你他肩上实在有点亲昵过分。他也讨厌陌生人叫他“艾伦”,还是“图灵先生”更妥当些。除了难以适应美国的新环境,图灵先生还有更糟的问题,在那个年代的体面社会里止于手势和眼神的问题:喏,你知道的,他有点那个……就是那个……那个啊……你晓得我在讲什么啊。

数学天才艾伦•图灵先生是个无可救药的同性恋。

这个无可救药的问题是这样开始的:当图灵还在谢伯恩男校 (Sherborne School )读高中,他认识了比自己高一级的克里斯托弗•马尔孔 (Christopher Morcom)。瘦弱的、过于瘦弱的马尔孔,每个学年都因病长期缺课,可他聪明的头脑竟然使他在偶尔上学的几天能补上所有功课,门门考试成绩第一。是这样毫不费力的聪慧吸引了图灵,而当他更接近马尔孔,惊喜地发现他和自己一样,对科学有着自发而浓厚的兴趣。在马尔孔偶尔上学的日子里,他们坐在相邻的座位听课,又一起去图书馆写作业,以便能不断讨论科学问题:马尔孔说如何在家里搭化学实验室研究碘,图灵说如何手算圆周率到小数点后36位,马尔孔说你知不知道薛定谔的量子力学有趣极了,图灵说你知不知道爱因斯坦的相对论也有趣极了。他们谈梦想,应该做数学家还是物理学家,如何为科学做出真正的贡献……晚钟响了,他们回各自的宿舍睡觉,又在凌晨爬起来站到阳台上用天文望远镜看星星,并写信把观测结果告诉对方:“我从没见过更好的木星。今夜我看到了五个环,甚至能看清中间那个环上的斑。”“我今夜看到了仙女座,但一会儿就消失了。”那个冬天,毕业班的马尔孔已顺利拿到了剑桥三一学院的奖学金。图灵还有一年毕业,马尔孔鼓励他来年报考剑桥,“因为那里的科学最好,而且我能经常看见你。”这句嘉勉说出口不到一个月,一个晴朗的凌晨,图灵起床看见月亮刚巧经过对楼马尔孔的窗户落下。“今晚的月亮格外美。”他写在记事本上预备第二天告诉马尔孔,他还不知道永远不会有那一天了。那个凌晨,克里斯托弗•马尔孔暴病夭折。

落葬日,时年十七岁的图灵怀着巨大的悲痛写信给马尔孔的母亲:

1930年2月15日
亲爱的马尔孔太太,
我因为克里斯而很难过。一年来我们一起学习,我从来没交过像他那么聪明、迷人、又谦卑的朋友。我和他分享了研究的乐趣还有对天文的热爱(这是他引发的),我想他也是这么觉得的。现在,尽管有一部分乐趣因为他的死而消逝了,即使这一切不再因为他而那么有趣,我也要投入尽可能多的精力到研究上,就象他仍然活着。他会希望我这么做的。我深知你此刻的悲痛。
你忠诚的,
艾伦•图灵
又及:如果你能给我一张克里斯的小照片我将十分感激。我愿以此来缅怀他的榜样和成就,督促我更仔细更优秀。我会思念他的面容,他走在我身边时微笑的模样。幸好我保存着他所有的信。

马尔孔死后一年,图灵的未来决定了,他要去剑桥国王学院学数学,就像给马尔孔太太的信里所承诺的,“以此缅怀他的榜样和成就。”这一年中,无数次对马尔孔的哀思恐怕也让他渐渐明白了比友谊更深的感情。是爱情吗?图灵无法回答,也不屑回答。落葬日那封痛切的信,还有这一年来(以及他的余生)为了纪念马尔孔而突飞猛进的学业都说明了这份感情比爱情更高:他在竭尽所能挽留死者。又有谁会为那么美好的感情而惊慌呢?于是图灵坦然接受了,并在余生从未试图遮掩自己的性取向。

##三、希尔伯特的落日

每个清晨和黄昏,图灵习惯一个人沿着河边长跑思考问题。去年夏天,当他还在剑桥国王学院读本科,某次长跑到精疲力竭地躺倒在草地上,斜阳西照,运动让他神思凝聚,他脑中经历了一场风暴,忽然意识到了回答希尔伯特判定问题(Entscheidungsproblem)的办法。他兴奋地一跃而起跑回寝室写下自己的思绪。他的身后,照耀世界数学界三十余年之久的希尔伯特的太阳,终于落山了。

大卫•希尔伯特,那个时代最受尊敬的数学家,凭一己之力使数学走上了更严谨系统的现代之路。1900年,38岁的希尔伯特如一位新任的武林盟主,振臂一呼,四方响应。他在国际数学大会上提出了著名的“二十三个问题”,立即成为了数学界集体奋斗的目标,其中的第八个问题黎曼猜想/哥德巴赫猜想更是成了数学的桂冠。二十八年后,暮年的希尔伯特又提出了三个数理逻辑上的大问题,简单说来这三个问题分别是:1)数学是完备的吗?2)数学是相容的吗?3)数学是可判定的吗?其中的第三问题,即被称作希尔伯特的判定问题。如果说 1900年的二十三个难题洋溢着壮年人的踌躇满志,那么1928年的三个问题已经是一个老人对秩序和条理的向往。希尔伯特十分希望,这三个问题的答案都是肯定的,因为这将使数学建立在完美严谨的逻辑的基石上,作为亘古不变的真理存在。

可惜,这个井井有条的逻辑美梦只做了三年,年轻的奥地利人哥德尔就发表了震惊数学界的哥德尔不完备定理:数学不可能既是完备的又是相容的。这个定理以十分有趣的形式否定了希尔伯特1928年的第一和第二个问题。到1935年夏天,躺在草地上休息的图灵经历了一场头脑风暴,他想到了否定希尔伯特第三个问题的办法:用机器。他想象着一种虚构的“图灵机”,可以从一条无限长的纸带子上的读取命令进行操作,从而模拟人类所可能进行的任何计算过程。图灵证明,我们不能用一个算法来判定一台给定的图灵机是否会停机,所以停机问题是一个无法判定的数学问题,即希尔伯特的第三个命题答案为否。

巧合的是,第二年春天,正当图灵把关于判定问题的论文初稿交给导师纽曼(Max Newman)过目时,大洋彼岸,普林斯顿大学的阿隆佐•邱奇(Alonzo Church)教授——逻辑界数一数二的学者——抢先一步发表了新论文,利用自创的λ演算(lambda calculus)否定了希尔伯特判定问题。看到邱奇如此巧合的论文,导师纽曼顺水推舟写信推荐图灵去做博士生。1936年夏,邱奇的新博士生图灵来到了普林斯顿。

图灵在普林斯顿大学的档案 Firestone Library, Princeton University, June 2012

11月,图灵关于判定问题的论文,即多年后将声名大噪的 On Computable Numbers, with an Application to the Entscheidungsproblem 终于发表,学界反应极其冷淡。12月图灵在普林斯顿数学俱乐部做了关于这篇论文的演讲,听众不足十人。这篇解决了希尔伯特第三个问题的论文为何遭到如此冷遇?有几个原因:其一,哥德尔不完备定理如此有趣奥妙,已经吸引走了学界关于希尔伯特三问题的大部分兴趣;其二,邱奇当年春天的论文已经率先解决了希尔伯特判定问题,虽然图灵的解法天差地别,也比邱奇的解法简洁得多;其三,用“机器”解决数理逻辑问题,实则是此篇论文最闪光的部分,可是过于新颖,不容易被主流学界接受;其四,恐怕也是最重要的原因:和著名教授邱奇比起来,图灵才初出茅庐。他在家书中愤愤说:“只有名人才会吸引听众。(One should have a reputation if one hopes to be listened to.)”

不,不完全如此。至少还有一个人会认真阅读无名小卒的论文。对门办公室的冯•诺伊曼教授——图灵默默仰慕又羞于开口的偶像——不但认真读过这篇论文,还读过所有期刊上的所有论文。他是一本雄心勃勃的百科全书,任何人的任何知识都逃不出他的法眼。图灵的论文一发表,敏锐的冯•诺伊曼已经嗅到了图灵机广阔的远景,他对朋友说,你该去找我对门的图灵,他那篇论文正好可以做这样那样的事。他慷慨地给朋友建议,自己却没亲自找图灵聊聊。他的注意力在有趣的图灵机上停留了一下,又跳到另一个截然不同却同样有趣的问题上:量子力学、流体力学、博弈论……世上千千万的问题都吸引着冯•诺伊曼,他脑中有千千万要实行的计划——图灵机不过是其中一个。

可是,博士生图灵仍然因为这篇论文而给冯•诺伊曼教授留下了印象,两年后图灵从普林斯顿博士毕业,是冯•诺伊曼教授唯一提出了挽留:年薪一千五百美元聘图灵做自己的助手。对于一个年轻的数学家,能师从传奇般的冯•诺伊曼教授是梦寐以求的机遇, 一千五百美元的薪水也比图灵在英国能找到的教职待遇好得多。图灵拿着冯•诺伊曼的聘书在普林斯顿校园里晃荡,理性使他不得不好好考虑这个千载难逢的肥缺,可是啊——英国人图灵吸吸鼻子,鼻子里呼到的空气有点太粗鄙,清清耳朵,耳朵里听到的英语有点太懒散。他走过哥特式的普林斯顿校礼拜堂,那只是更加宏伟古老的剑桥国王学院礼拜堂蹩脚的复制品。礼拜堂的尖顶插入新泽西州的蓝天白云,英国人图灵却没法欣赏这儿的晴空万里,他的目光越到了大西洋彼岸,那里,纳粹的阴云密布欧洲。

1938年夏,博士毕业的图灵忧心忡忡回到英国剑桥,在数学系做一学期才给十英镑的临时教员,教一门听者寥寥的“数学基础”。他将慢慢攀爬学术的梯子,成为教员、讲师、副教授、教授,如果不出意外的话。九个月后,意外降临:纳粹的阴云终于骤降成狂风暴雨,德国入侵波兰,第二次世界大战开始。

##四、Station X. Site Y.

二战的爆发给白金汉郡的布莱切利镇带来了点可喜的新鲜,一万多人连夜从大城市挤火车逃难到这个平庸乏味的小镇,可是不久大部分又挤火车回去了:宁愿被炸弹炸死,也不要在这小地方无聊死。艾伦•图灵却逆着人潮,搬到了这无聊小镇最无聊郊区的一家最最无聊的小旅馆里,每天骑车三英里去镇中心的布莱切利园(Bletchley Park)上一个谁都不知道在瞎搞什么的班,下班回来还自愿给冷冷清清的旅馆酒吧打杂。旅馆老板娘看着这个闲得发慌的小伙直摇头:健健康康的大男人,怎么不去打仗呢?

可是,图灵正在打仗。他的敌人:哑谜。看似死水一潭的布莱切利园,此时已有了军事代号:Station X,保密等级:绝密。这里是英国政府密码学校的驻地,海陆空和军情六处的情报组织各占一隅。几百名工作人员日夜兼程破解德国人的无线电报,为了最大程度保密,大部分职员根本不知道工作的真正目的,除了几个核心解密成员:象棋冠军、填字游戏高手、数学家。二十七岁的图灵很快在这个核心团队里有了绰号:教授(Prof.)。

此时的欧洲上空,无数来自德军的电波正以莫尔斯码的形式穿梭来回。这些莫尔斯码发出前由一种称作“哑谜机”(the Enigma Machine)的加密器加密,在接受方又由同样的“哑谜机”解密。直到二战结束,德军从未怀疑过哑谜机的坚不可摧,所有军种所有级别电报,一律用哑谜机加密,加密电报中放心大胆地沟通了所有军事信息:潜艇位置、军队人数、攻击路线、伤亡报告……

哑谜机

德军的信心源于哑谜机复杂的加密方法。虽然每个军种对商用的哑谜机都略有改进,不过所有哑谜机基本构造相同:键盘、接线板、多个转子、指示灯。当密码操作员在键盘上按下一个字母(比如字母A),电流会通过一个可自行改接的接线板,启动一个或者多个转子转动,同时点亮某个字母指示灯(比如字母L),于是字母A被加密成字母L。哑谜机精巧的设计使得,在下一次按下字母A时,它将被加密成另一个不同的字母(比如字母P)。更巧妙的是,当且仅当发送端和接收端的哑谜机拥有同样的初始设定(同样的接线板、同样的转子排列、同样的转子初始位置),密码L才可以使用接收端的哑谜机还原成A。而对于不知道初始设定的敌方,他们面对的可能情况多达10^114种!

雪上加霜的是,德军每个军种所用的哑谜机略有不同,相对于三个转子的陆军哑谜机,海军五转子的哑谜机要复杂得多。在布莱切利园只有两个人相信这层层加密状如天书的密码可以被破解:一个是布莱切利园的老大,因为“海军电报必须被破解”,否则被德军潜艇战封锁的英国将坐以待毙;另一个是“教授”图灵,因为“如果海军电报能破解,那实在太好玩了”。

“教授”发现,在加密文件中找规律的本质是重复搜索,而搜索是一种机器可以代替人脑的工作。当时,布莱切利园从曾经研究过哑谜机的波兰数学家那里继承了一种叫“炸弹”(Bombe)的原始解密仪器,每一个“炸弹”模仿一个哑谜机的转子,许多“炸弹”相链接来模拟一种哑谜机的初始设定生成可能的电报。简而言之,这是一种穷举搜寻答案的算法,需要遍历所有可能排列,费时费力。图灵洞察到,只要运用几个简单的事实——比如,一个字母的密码不可能是其本身、原始文本中一些字母(比如s)的出现频率一定高于另一些字母(比如x),一些固定词语(比如“元首”)将高频出现——就能大大改进波兰人的笨法子,来快速寻找最有可能的转子设定。用现在的算法语言来说,他将穷举法改良成了贪心算法。贪心算法改进后的“炸弹”对抗五转子的海军哑谜机大获成功。每次一方发出电报后,接受方过几分钟将发一封短电报表示“收讫”。许多回,电波中还未监测到“收讫”电报,图灵的“炸弹”机已经将密码还原成了原文, 可见“炸弹”的解密速度甚至比预知原始设定的接受方都快!布莱切利园自豪地说,德国人真该问“教授”他们的电报到底讲了什么。

可是,随着战争深入,转子更多的哑谜机不断投入运用,最后竟出现了十二转子的密码机。面对十二转子,即使图灵的“炸弹”都需要十几天时间。战场瞬息万变,布莱切利园亟需更快速的机器。很显然,提高速度的关键在于把机械的“炸弹”机改成更快速的电路装置。1943年,在图灵的鼓励下,布莱切利园工程师Tommy Flowers设计了一台叫作Colossus的巨型机器,在战时充裕的经费支持下很快获准建造。

这就是世界上第一台计算机,电子化、数字化、程序化。它由光学在长条纸带上读取电报原文,经过一千五百个真空管的电路计算,将解密结果输出到电传打字机上。1944年6月1日, 经过完善的Colossus二号机抵达布莱切利园。离诺曼底登陆只有五天。

诺曼底登陆,在欧洲开辟第二战场的唯一方法,毋宁是一场豪赌。盟军三百万主力兵力要从海上和空中登陆易守难攻的诺曼底,很可能伤亡惨重。为了保护兵力,盟军的情报网精心编造了一则假情报透露给敌方,希望德军以为在诺曼底将有一次只是“小规模”的军事转移。而德军能不能上当则唯有通过由Colossus解密的德军电报检验。幸亏快速的电子计算机,解密很顺利,德军的电报显示只有一小支部队被派往诺曼底。更幸运的是,电报还详细说明了军事安排、物资转移、军种调遣,德军手中的牌一览无余。

6月6日凌晨三点,Colossus破解了一条德军自诺曼底刚发出的绝望的电报。天啊,天上怎么来了那么多伞兵。

随着这些伞兵安然降落,二战的转折点到来了。

大西洋的另一边,1943年秋。

威斯康辛大学麦迪逊分校数学教授乌拉姆(Stan Ulam)的办公室里闯进了一个女学生。学期只过了一半,她却要求提前完成期末考试,以便“为战争服务”。她坐在办公室的地板上,答完了教授在信封背面临时写下的几道题,然后消失到谁都不知道哪儿去了。

这几天,乌拉姆身边有许多朋友消失了。在食堂认识的同事、物理教授、自己带的研究生,他们打了个 “为战争服务”的假条,就神秘莫测地走了。乌拉姆心里痒痒,写信给自己朋友中人脉最广的冯•诺伊曼,询问有否能为战争服务的工作,他回信了,说自己忙得很,不如在芝加哥火车站见面——他在那里正好有两个小时的转车时间。乌拉姆在站台见到了风风火火的冯•诺伊曼,以及——他身后的两位保镖,这才意识到他朋友正在忙活的事对大战意义重大。冯•诺伊曼神秘地表示:有一件很重要的项目也许能让乌拉姆帮忙,不过他还不能说是什么事,在哪里,有谁。

几周后,乌拉姆收到了一封政府委派信,要求他去新墨西哥州一个小镇。他从来没听说过这荒僻之地,就去图书馆借新墨西哥州地图册。于是他惊喜地发现,在地图册的借书卡上,整齐地排列着之前消失的所有熟人的名字。他们都消失到了这个闻所未闻之地。

火车在一个荒凉的车站停下,黄沙遍野,峭壁陡崖,像时间尽头一样死寂。这里就是Site Y,刚刚起步的研究项目叫Project Y,保密等级:绝密。战争结束后,前者将称为洛斯阿拉莫斯国家实验室(Los Alamos National Laboratory),后者便是鼎鼎大名的曼哈顿计划。在这片萧索瑰丽的沙漠中,聚集了一群活力旺盛的年轻人,平均年龄25岁,第一年,80个新生命诞生。他们的领袖奥本海默38岁,他们的信使冯•诺伊曼39岁。他们的任务:制造摧毁一切活力和生命的超级武器,原子弹。

洛斯阿拉莫斯国家实验室边界的标志

四年前,爱因斯坦和西拉德(Leo Szilard)上书美国总统罗斯福:物理学的推进已经使得通过核裂变获得巨大能量指日可待,只要德国人愿意,他们有知识和能力发明这种武器,美国必须赶在纳粹德国之前掌握核技术。随着美国正式参战,核技术的研究越来越紧迫。一个名字被提出来:罗伯特•奥本海默,聪明果敢,当机立断。另一个名字被提出来:约翰•冯•诺伊曼,因为他已经坐镇另外十几个军事项目上,正好能耳听八路,眼观四方。

冯•诺伊曼教授是军方最喜爱的合作人。作为犹太人他对纳粹嫉恶如仇,为了替关在集中营的朋友报仇他渴望和手段强硬的人合作,醉心各种新式武器。作为数学家,他认为只有当数学有应用价值时,数学才能最快速度发展。少时父亲逼迫之下学习的化学工程意外派上了用场,他很容易明白物理学家和化学家的讨论,再用数学的语言解释给数学家听。他最擅长把一项看似庞大无解的任务庖丁解牛,分拆成小零件委派他人,让底下每个人觉得自己拿到的那部分恰好是最擅长的本职。他是天生的领袖和传令官,坐镇导弹研究实验室、美国数学学会战争委员会、国家防御研究委员会……不像大多数被强制定居在洛斯阿拉莫斯的科研者,他进出自由。日理万机的冯•诺伊曼教授哟,他在普林斯顿、波士顿、费城、华盛顿、芝加哥、洛斯阿拉莫斯实验室、阿伯丁兵器试验中心……全美的战时科研进展他一清二楚,人家刚跟他讲了两句,他就能接上来,“某某在芝加哥也做这事。”“哈佛的某某已经搞出来了。”

曼哈顿计划最大的困难不是制造出核裂变反应,而是控制原子弹的威力。爆炸的冲击波将反复震荡叠加,最终的力量难以预测。曼哈顿计划的高度机密性和核试验的昂贵成本使得大规模试验不可能,而人力又难以计算如此多的非线性方程。如何提高计算能力成了当务之急。

事实上,计算能力这个瓶颈也困扰着其他军方科研项目。于是,1943年,当听说宾夕法尼亚大学的一群工程师为了计算导弹轨道(另一种典型的非线性方程)而开始建造一台名为ENIAC的巨型机器时,冯•诺伊曼立即敏锐地想到:也可以用这机器去计算原子弹冲击波的能量。在他的牵头下,ENIAC建完后第一项测试任务居然不是导弹轨道而成了核弹方程,整个测试将原本几个月的 人力计算缩短到了几天。完成测试他脸色苍白地回到普林斯顿家里倒头睡了十小时,醒来后不吃不喝,久久向妻子吐出一句话:“我们造了一头怪兽。”

怪兽,他指的不是核弹,而是计算机。

看到了ENIAC的广阔前景后,冯•诺伊曼毛遂自荐要做ENIAC的数学顾问,让发明者Presper Eckert和John Mauchly受宠若惊。他们亲自领冯•诺伊曼参观机器,一间两百平米的大房间里,两个工程师指给他看:这里是一万八千根真空管、这里是电源、这里是读卡器、这里是维修站……可是,人家的设计冯•诺伊曼却看得比设计者还清楚,他一回去就写了个105页的报告:“一台计算机的基础组成是:存储器、控制器、运算器、输入输出设备。”至今,世界上的大部分电脑仍在沿用这著名的“冯•诺伊曼结构”。

1945年5月,德国投降,证据显示德国当时的科研进展还未能制造出原子弹。7月,洛斯阿拉莫斯第一颗原子弹试射成功。8月,在新上任的杜鲁门总统的授意下,两颗本为抵御德国人的原子弹投向日本广岛和长崎。9月,日本投降。第二次世界大战结束。

1945年7月16日凌晨,第一颗原子弹Trinity在新墨西哥州试射成功。

##五、MANIAC

在二战的巨大压力下,英美两国独立制造出了最原始的计算机,Colossus和ENIAC。它们惊人的相似:都利用打孔卡输入,都运用真空管计算,都体积庞大,都对二战胜利功勋卓著。二战史学家普遍认为,布莱切利园的工作使欧洲战场缩短了一年半到两年的时间,并直接切断了“沙漠之狐”隆美尔在北非的补给线;而曼哈顿计划则终结了太平洋战场。现在,在这个戏剧性的擂台上,两个核心人物图灵和冯•诺伊曼都决心改进这两台原始机器相似的缺陷:只为专门目的设计,不能储存程序。改进的方向很明显,一如图灵1936年论文所预言的那样,造一台能完成任何目的的图灵通用机。

二战结束了,而冷战的阴影旋即逼近。核威慑成了一扇关不上的门,在间隔重重的美苏关系中,美国很快发现为求自保只能继续扩大核优势。氢弹的研究成为了攻坚关键,而如何提高计算能力又成了重中之重。要造一台好机器!冯•诺伊曼教授对此深信不疑。

在哪里造?就在普林斯顿高等研究院!高等研究院院长面有难色:“我们这儿一直搞纯科学,造这么台大机器有点不像话吧?”“钱哪来?一年十万美金的预算,你得让数学系经费翻三番!”“造了放哪?三间两百平米的大房子,二十四小时引擎折腾,我们这儿可没这样的兵工厂。”鬼精明的冯•诺伊曼笑着对院长说既然这样那就算了,谢谢院长费心,一回头却给哈佛大学、芝加哥大学、IBM轮番写信:“我有兴趣到你那儿工作。”三所机构喜笑颜开,发出了热烈的聘书。好个冯•诺伊曼,姜太公钓鱼,把哈佛的聘书给芝加哥看,把芝加哥的给IBM看,每个机构衬着别人的价码轮番加价,要是能把鼎鼎大名的冯•诺伊曼请到,送个金屋银屋都值!他胜券在握,把哈佛的天价聘书呈给普林斯顿的同事看,伤感地说自己要辞职,教授们联名写信给院长:“失掉冯•诺伊曼将是普林斯顿的悲剧!”那院长也只能咬咬牙:去造你那台要命的机器吧。

1947年在普林斯顿高等研究院开始建造的MANIAC计算机在任何意义上都超过了前任ENIAC。ENIAC用了两万个真空管,MANIAC只用了两千个。ENIAC重达三十吨,MANIAC只有一吨。最关键的是,ENIAC不能贮存程序,每个 不同的任务都需要重新排布电线,而MANIAC可以读取由打孔卡上二进制编码的程序,贮存在存储器中。它是世界上第一台真正的全能自动电子计算机,是后世所有计算机的母型。它完成的诸多军方任务中,最惹眼的是一次耗时60昼夜的计算,其结果证明了氢弹制造的可行性。

1952年科学家们在MANIAC前合影。左五为奥本海默,右一为冯•诺伊曼。

1957届校友Joshua Dranoff,日后成为西北大学化工系教授,在五十年代利用MANIAC完成了他化工博士论文,其中设计了一个用计算机模拟实验结果的步骤。他告诉我,每一天机器运行之前有漫长的检修,技术工拿着一箱电线和真空管爬进MANIAC内部逐一更换坏损零件。各个专业的学生等在实验室外叽叽喳喳地排队签到,他们都想尝尝MANIAC的鲜,在论文里时髦地用计算机做个小项目。1958届校友Jerry Porter,日后成为宾夕法尼亚大学数学系教授,是第一个运用MANIAC完成本科毕业论文的学生。他大三大四时还带领一帮同学负责MANIAC的夜班值勤,他们得盯着示波器屏幕,时刻监测MANIAC宝贵的1024比特随机存储器不被烧坏。这个夜班工作激发了他对计算机的兴趣,日后的学术生涯他专注于计算数学领域。

于是乎,在未受战争破坏的美国,由ENIAC掀起的计算机和电子工程科学搞得风生水起,并很快由IBM公司实现了商业运作。到1960年MANIAC光荣退休被捐赠给史密森尼国家博物馆(Smithsonian)时,全美已经拥有了6000台计算机。

在废墟上的英国,博士生图灵的运气远没那么好。二战后,为保护英国情报网,布莱切利园大部分文件资料被焚烧销毁,其余被归为机密档案。胜利的光荣属于海陆空三军,而布莱切利园的工作人员必须对战时工作保持沉默。头号功臣图灵被授予大英帝国官佐勋章(OBE),可即便他的母亲也只是知道,“他做了点了不起的事情。”

图灵被分配到国家物理实验室工作,迫不及待地想要改进Colossus。 他向实验室提交了一份项目申请,详尽地阐明自己将如何建造一台能贮存程序的计算机,事无巨细地列出所有图纸和经费计划。可是,战时布莱切利园的高效和无节制的战争经费已经让位于战后拖拉的官僚作风和经济危机。过目这份申请的负责人没有一个看出这庞然大物的用处,大部分人甚至不相信计算机可以造出来——可笑可叹,与ENIAC的风光截然不同,为情报服务的Colossus对外界是“不存在”的。图灵甚至不能告诉别人,这台他们认为不可能造的机器已经造出来了。

1948年,受够了国家实验室的官僚作风,图灵跳槽到曼彻斯特大学计算实验室 (Computing Labatory),这里受到美国ENIAC的激励正在建造英国第一台贮存程序式电脑Manchester Mark I。图灵本该大有作为,可是制造这么大一个机器需要和很多人协调,他孤僻的性格很快让同事与之疏远,大部分建议被当作书呆子的意气而姑妄听之。不久,他聊以自慰地发现,造计算机的难点主要是硬件而非数学模型,那还是把琐碎的工程问题留给工程师吧。他呢,他只要能够“想”就行了。想——他开始为一个根本不存在的计算机想一种下象棋的程序。四年后,他会扮演这台虚构的计算机,严格执行自己的程序,和朋友下了一场真正的象棋比赛,每一步耗时半小时。他和朋友下输了,却赢了朋友的妻子一局。对于数学家图灵,即使永远没有计算机的实体,这件事也已经做完了。“想出来”就是“做出来”。

##六、咬了一口的苹果

在曼彻斯特大学,图灵的主要工作仍然是在计算学理论上。1950年,他提出了至今仍广泛使用的“图灵试验”(Turing Test),即让测试者向两个对象——一个为机器一个为自然人——提出一系列问题,如果根据双方的回答,测试者不能辨别孰为机器,则这个机器应被视为有智能的。别有意味的是,图灵在提出这个试验时用了一个精巧的隐喻:假设两个回答者是一男一女,提问方在问出一系列问题后不能判断哪个是女人,则可以认为那个男人也是一个成功的“女人”。

他是在这里影射自己性取向上的差异吗?我们不得而知。可完成论文后没多久,他就在一次散步时结识了十九岁的阿诺德•莫里(Arnold Murray):水泥匠的儿子、惯偷、小混混。这让人不禁想起当年中产富裕的魏尔伦一见钟情地爱上了十六岁的兰波:一个乡下来的野孩子,境遇的极端不同招至强烈的爱欲。如同魏尔伦和兰波一样,图灵的故事也有一个甜蜜的开头和一个毁灭性的结尾:有一天图灵发现自己家中失窃了,他报了案,窃贼是莫里的朋友。于是经过简单的询问,图灵向警方承认了和莫里之间的关系。

在当时的英国,同性恋被列为“不体面罪”(gross indecency)。他的入室盗窃案非但因此不得到法律保护,他反而被送上法庭受审。法官给出了两种惩罚任他选择:坐牢或者化学阉割。当时一些科学研究认为,同性恋源自过剩的雄性欲望,可以通过注射雌激素来抑制。两害相权,图灵选择了后者,因为这样至少能呆在家里继续做数学。他被持续注射雌激素长达一年,导致胸部发育,变声,阳痿。

1954年6月7日,他在家中咬了一口沾有氰化物的毒苹果自杀。

让图灵生命最后两年处境悲惨并最后导致他服毒自杀的“不体面罪”,他当时是极其天真地就在警方面前承认了。他不但口头承认了,还兴冲冲手写了五页花体字的供述。读过这五页纸的警察认为 “像散文一样流畅”(a flowing style, almost like prose)、“虽然有些措词太难读不懂”(beyond them in some of its phraseology)、“他真以为他在做正确的事”(he really believed he was doing the right thing) 。图灵事后告诉朋友,他之所以这么坦白是因为他以为同性恋很快就要合法了,一切都可以摊在台面上谈。

图灵惨死后六十年过去了,这一切还远不能摊在台面上谈,同性恋行为在大部分国家仍受到广泛争议,虽然尊重和合法的呼声在青年一代中越来越高。2009年,英国首相布朗在一份几千人签名请愿书下向这位计算机之父和二战英雄做了官方道歉:“我们很抱歉。你本该被更好对待。(We are sorry. You deserved so much better.)”

为纪念图灵百年诞辰,今年英国发行了一张图灵邮票。

1957年,五十三岁的冯•诺伊曼因骨癌病逝,癌变原因很有可能源自曼哈顿计划的核辐射。军方代表守在他的病床前,以防他在药物作用下泄漏军事机密。生命最后的日子,这个数学天才连简单的加减法都不能做了,却还逐字背诵幼年读过的《浮士德》 给探望的亲友解闷。浮士德,与魔鬼订约而遍历人间百态的大学者,这不正是冯•诺伊曼的一生?

冯•诺伊曼去世后,一切都不同了。曾经那么容易实现的事情,现在却困难重重。继任者们不明白,他到底是怎么搞来那么多钱?怎么招到那么聪明的人?“而且,说到底,我们为什么非得造一台机器呢?”冯•诺伊曼手下忠心耿耿的工程师们还梦想着造一台更好的MANIAC,用晶体管造,稳定性比真空管好得多……可是,这一台机器永远没造。源泉死了,源源不断的活力和创造便停歇了。普林斯顿高等研究院退出了计算机科学最令人激动的发迹史。接下来,将是IBM和MIT的天下。

##七、“告诉他们,我度过了极好的一生。”

回到1939年,大战之前的最后一个学期。

1939年2月13日,剑桥哲学系教授维特根斯坦走进“数学基础”课教室,失望地发现他的学生图灵今天缺席了,于是对班上宣布,因为图灵缺席,“今天的课只是参考性的”——要知道这门课的要旨就是听维特根斯坦和图灵吵架!这位27岁的年轻人刚从普林斯顿大学博士毕业,正在剑桥数学系以临时教员的身份教授一门同样叫作“数学基础”同样听者寥寥的课,不过维特根斯坦的课是关于“数学本质是什么”这个哲学问题,而图灵的课是关于“奠定数学基础的公理是哪些”这个数学问题。在维特根斯坦的课上,他喜欢把所有对数学基础的攻击倾数射向图灵,而图灵也很喜欢针锋相对地反击。两人激烈地争吵,而后发现自己对彼此领域的理解前进了一点。在这个常年一身运动衫、又紧张又内向的年轻人身上,维特根斯坦看到了三十年前的自己:除了思考最基本的问题,这世上没有其他事要做。三十年前,出生于欧洲最富有家族的维特根斯坦也是同样不修边幅地站在逻辑学家罗素面前,他急于从罗素口中知道自己有没有严肃思考最基本问题的才能:如果没有,他就预备去自杀。

而今天,这个与自己惊人相似的年轻人图灵没有来上课 。图灵正骑着掉链子的自行车去“钟屋”(Clock House)——他心爱的克里斯托弗•马尔孔生前最常去的教区教堂。今天是马尔孔去世九年的祭日,马尔孔的父母决定以儿子的名义为教堂捐赠一个小礼拜堂。图灵坐在礼拜堂里参加捐赠仪式,对面的彩色玻璃窗上绘有圣徒克里斯托弗的事迹。亡友死后,彻底的无神论者图灵已经几十次来到这座教堂缅怀十七岁的夜晚,他和他从图书馆回宿舍一路上所谈论的雄心壮志:如何为科学做出真正的贡献。现在,完成了剑桥和普林斯顿的学业,这个雄心已经变得更加具体。他的脑中已经看到了一部精巧的机器,一部能完成所有“可能完成的”任务的机器。这不再仅仅是一台机器,也是对马尔孔的交代。

多年之后,冯•诺伊曼教授会向美国政府保证,世上只需要十五台这样的机器,全部由像自己一样聪明的科学家操作,用以计算最重要的问题:弹道曲线、核反应方程、天文观测。而图灵的愿景在更深的地方:钻研过希尔伯特1928年三个问题的博士生图灵伤感地意识到,数学是不完美的,逻辑是不完美的,哲学是不完美的。即使在最抽象最笼统的意义上,我们仍然永远活在一个不完美的世界里,在这摇晃的地基上我们永远造不出任何完美的事物。我们必须不断修葺改造,在每一次稳固地基的同时试图变得更好。

如果一台完美的机器是不可能的,那么能否造出一台不完美但是像孩童一样不断成长的机器呢?于是,图灵梦想着他的图灵机,那是一种可以不断读取自身修改自身的机器,在许多次失败的尝试后能学习到成功的诀窍。图灵梦想着许多图灵机连接在一起,一台提出问题,许多台都可以回答。可以是任何问题:从弹道曲线到老奶奶的购物清单到家庭旅行的地图路线。可以由任何人操作:从最聪明的科学家到小学肄业生,因为每台图灵机提供答案将经过更多的图灵机甄选。

我们知道,冯•诺伊曼关于世界只需要十五台计算机的断言错了。世界沿着图灵的梦想延展下去,一个扁平的千姿百态的世界。我们知道,图灵的梦想已经那么熟稔地被今天的人类挂在嘴边:互联网、人工智能。

回到1937年,文章一开头描绘的那个早晨。

34岁的犹太裔教授冯•诺伊曼是家财万贯的公子哥,不过他一定是公子哥中最勤奋的一个。他每天五点起床,昨夜他派对宴请的朋友还一个个倒在沙发上打呼噜,他已经在书房里沙沙写了几页论文。九点开早饭,他停止工作走出书房,和留宿的朋友谈笑风生邀请他们下次再来。十点,他的凯迪拉克已经稳稳当当地停在帕尔玛物理实验室前面,他一身标志性的西装地走向相邻的数学楼,继续写论文。

此时25岁的同性恋博士生图灵也已经穿着标志性的破运动衣沿着学校树林跑完了半程马拉松。他在树林里看到了几只英国见不着的颜色鲜艳的青蛙,几朵庞大的蘑菇,暗自好笑了一会儿。他到帕尔玛物理实验室捣鼓了一下自己的业余爱好——制造一台能做乘法的机器——然后穿过天桥走进数学楼,向办公室对门的冯•诺伊曼尴尬地打个照面,继续研究λ演算和图灵机。

那时候,普林斯顿大学的数学楼和物理楼有一座天桥相连。爱因斯坦教授精神很好,每天穿梭天桥许多次在数学和物理之间来回奔跑。那是一个离我们遥远的伟大的科学年代,基础学科之间有许多天桥和地道相通,科学家从一个学科开始挖凿,最后挖到另一个学科的金矿。希尔伯特在世纪之初的著名演讲为几十年内的数学突飞猛进提供了指路牌,爱因斯坦1915年的广义相对论带来了一个崭新的宇宙观,一个个新化学元素接踵而至犹如上天的惊喜。集合论不过半个世纪,拓扑学才三十几年,量子力学二十年……在这个幸福的基础科学的时代,犹太人冯•诺伊曼和同性恋图灵坐在面对面的办公室里,这两种备受歧视的身份将困扰他们一生,可是此时,他们心无旁骛只有一个愿望:做一个数学家、数学家、数学家。

幸福的数学家。


扩展活动:
我的一位学数学的朋友制作的图灵机网站在这里。为之所写的浪漫的使用说明书在这里
向对图灵的一生感兴趣的读者推荐这本科学传记的典范:Alan Turing: The Enigma .
向对哑谜机和布莱切利园感兴趣的读者推荐纪录片World War II Mind of a Code Breaker,在Youtube上有。

本文的写作除参考以下书目,还从1957届校友Joshua Dranoff教授、 1958届校友Jerry Porter教授处得到了宝贵的原始资料。1988届校友W. Barksdale Maynard先生、普林斯顿档案馆的Daniel Linke先生在史料核对上提供了有益的线索。
本文的配图除图灵在普林斯顿的档案那一张系自己拍摄,其余都来自网络。

参考书目:

  • Dyson, George. Turing’s Cathedral: The Origins of the Digital Universe. New York: Pantheon Books, 2012.
  • Hargittai, Istvan. The Martians of Science: Five Physicists Who Changed the Twentieth Century. Oxford: Oxford University Press, 2006.
  • Hodges, Andrew. Alan Turing: the Enigma. New York: Walker & Company, 2000.
  • Macrae, Norman. John von Neumann: The Scientific Genius Who Pioneered the Modern Computer, Game Theory, Nuclear Deterrence, and Much More. Providence, RI: American Mathematical Society, 1999.
  • Monk, Ray. Ludwig Wittgenstein: The Duty of Genius. New York: Penguin Books, 1991.
  • Ulam, S.M.. Adventures of a Mathematician. New York: Charles Scribner’s Sons, 1976.

Opensource projects valued for reading

These days, I felt tired to do any coding. I couldn’t descript the future of it.
So, I tryed to looking something in the Internet, which wasn’t clear enough in
my mind. Then, I found this article Zhihu-Hit me hardly,
maybe a programmer should be like that.

A programmer, who want to improve his/her skills not only one directory, should
read the projects listed as below:

There have published two books, one is Beautiful code,
introduced much beautiful code, and Beautiful Architectures
show lots of valued architectures.

Other link: