kk Blog —— 通用基础

SBT -- poj2828

2012-01-16 21:34:00

#include <stdio.h>
#include <algorithm>
#include <iostream>

#define N 4000005
using namespace std;

int tol=0;
struct SBT
{
	int left,right;
	int key;
	int size;
	void init()
	{
	    left=right=0;
	    size=1;
	}
}T[N];

void R_Rotate(int &t)//右旋
{
	int k=T[t].left;
	T[t].left=T[k].right;
	T[k].right=t;
	T[k].size=T[t].size;
	T[t].size=T[T[t].left].size+T[T[t].right].size+1;
	t=k;
	return ;
}
void L_Rotate(int &t)//左旋
{
	int k=T[t].right;
	T[t].right=T[k].left;
	T[k].left=t;
	T[k].size=T[t].size;
	T[t].size=T[T[t].left].size+T[T[t].right].size+1;
	t=k;
}
void Maintain(int &t,bool flag)//维护，SBT精华之所在
{
	if(flag==false)
	{
	    if(T[T[T[t].left].left].size>T[T[t].right].size)
	        R_Rotate(t);
	    else if(T[T[T[t].left].right].size>T[T[t].right].size)
	    {
	        L_Rotate(T[t].left);
	        R_Rotate(t);
	    }
	    else
	        return ;
	}
	else
	{
	    if(T[T[T[t].right].right].size>T[T[t].left].size)
	        L_Rotate(t);
	    else if(T[T[T[t].right].left].size>T[T[t].left].size)
	    {
	        R_Rotate(T[t].right);
	        L_Rotate(t);
	    }
	    else
	        return ;
	}
	Maintain(T[t].left,false);
	Maintain(T[t].right,true);
	Maintain(t,false);
	Maintain(t,true);
}
void Insert(int &t,int v)//插入
{
	if(t==0)
	{
	    t=++tol;
	    T[t].init();
	    T[t].key=v;
	}
	else
	{
	    T[t].size++;
	    if(v<T[t].key)
	        Insert(T[t].left,v);
	    else
	        Insert(T[t].right,v);
	    Maintain(t,v>=T[t].key);
	}
}
int Delete(int &t,int v)//删除
{
	if(!t)
	    return 0;
	T[t].size--;
	if(v==T[t].key||v<T[t].key&&!T[t].left||v>T[t].key&&!T[t].right)
	{
	    if(T[t].left&&T[t].right)
	    {
	        int p=Delete(T[t].left,v+1);
	        T[t].key=T[p].key;
	        return p;
	    }
	    else
	    {
	        int p=t;
	        t=T[t].left+T[t].right;
	        return p;
	    }
	}
	else
	    return Delete(v<T[t].key?T[t].left:T[t].right,v);
}
int Find_k(int t,int k)//找出第k大数
{
   if(k<=T[T[t].left].size)
	    return Find_k(T[t].left,k);
	else if(k>T[T[t].left].size+1)
	    return Find_k(T[t].right,k-T[T[t].left].size-1);
	return T[t].key;
}
int Getmin(int t)//取最小值
{
	while(T[t].left)
	    t=T[t].left;
	return t;
}
int Getmax(int t)//取最大值
{
	while(T[t].right)
	    t=T[t].right;
	return t;
}
int Rank(int t,int key)//排名其实就是它的左子树的size+1
{
	if(t==0)
	    return 0;
	if(key<=T[t].key)
	    return Rank(T[t].left,key);
	else
	    return T[T[t].left].size+1+Rank(T[t].right,key);
}
int eRank(int t,int key)//倒过来排名
{
	if(t==0)
	    return 0;
	if(key>=T[t].key)
	    return eRank(T[t].right,key);
	else
	    return T[T[t].right].size+1+eRank(T[t].left,key);
}

int Exist(int t,int x)//判断这个节点是否存在
{
	if(t==0)
	    return 0;
	if(x<T[t].key)
	    return Exist(T[t].left,x);
	else if(x==T[t].key)
	    return 1;
	else
	    return Exist(T[t].right,x);
}
int Count(int t,int x)//统计出现次数
{
	if(!Exist(t,x))
	    return 0;
	else
	    return Rank(t,x+1)-Rank(t,x);
}
int Pred(int t,int v)//返回比v小的最大的数
{
	if(t==0)
	    return v;
	else if(v>T[t].key)
	{
	    int ret=Pred(T[t].right,v);
	    if(ret==v)
	        return T[t].key;
	    return ret;
	}
	else
	    return Pred(T[t].left,v);
}
int Succ(int t,int v)//返回比v大的最小的数
{
	if(t==0)
	    return v;
	else if(v<T[t].key)
	{
	    int ret=Succ(T[t].left,v);
	    if(ret==v)
	        return T[t].key;
	    return ret;
	}
	else
	    return Succ(T[t].right,v);
}

////////////////////////

int n,m, a[200009], b[200009], c[200009];

void dfs(int root)
{
	if(root == 0) return;
	dfs(T[root].left);
	if(m > 0) printf(" ");
	printf("%d", T[root].key);
	m++;
	dfs(T[root].right);
}

int main()
{
	int i,j,k;
	int root;
	
	while(scanf("%d", &n) != EOF)
	{
	    tol = 0;
	root = 0;
	    for(i=1;i<=n;i++)
	{
	        scanf("%d %d", &a[i], &b[i]);
	    Insert(root, i);
	}
	for(i=n;i>0;i--)
	{
	    k = Find_k(root, a[i]+1);
	    c[k] = b[i];
	    Delete(root, k);
	}
	for(i=1;i<n;i++) printf("%d ", c[i]);
	printf("%d\n", c[i]);
	m = 0;
	dfs(root);
	}
	return 0;
}

strace跟踪系统调用和信号

2011-12-09 00:16:00

strace 用来截取程序发出的系统调用并将其显示出来。被 strace 跟踪的程序，可以是从 strace 命令运行的，也可以是系统上已经运行的进程。strace 是调试汇编语言和高级语言程序时价值无法估量的工具。

为了简单起见(不让 strace 输出太多内容)，这里使用 strace 截取 http://www.groad.net/bbs/read.php?tid-2622.html 中“系统调用返回值“ 里的示例程序：

$ strace ./syscall2
execve("./syscall2", ["./syscall2"], [/* 43 vars */]) = 0
getpid()                                = 2467
getuid()                                = 1000
getgid()                                = 1000
_exit(0)                                = ?

上面，左侧一列显示了系统调用名称，右侧显示系统调用生成的返回值。

高级 strace 参数：

参数       描述
-c        统计每个系统调用的时间、调用和错误
-d        显示 strace 的一些调试输出
-e        指定输出的过滤表达式
-f        在创建子进程的时候跟踪它们
-ff       如果写入到输出文件，则把每个子进程写入到单独的文件中
-i        显示执行系统调用时的指令指针
-o        把输出写入到指定文件
-p        附加到由PID指定的现有进程
-q        抑制关于附加和分离的消息
-r        对每个系统调用显示一个相对的时间戳
-t        把时间添加到每一行
-tt       把时间添加到每一行，包括微秒
-ttt      添加epoch形式的时间(从1970年1月1日开始的秒数)，包括微秒
-T        显示每个系统调用花费的时间
-v        显示系统调用信息的不经省略版本(详细的)
-x        以十六进制格式显示所有非ASCII字符
-xx       以十六进制格式显示所有字符串

其中，-e 参数很方便，因为它可以用于只显示系统调用的子集，而不是全部。-e 参数格式为：
trace=call_list
上面，call_list 是系统调用清单。如上面的程序，如果我们只希望看到系统调用 getuid 和 getgid，那么可以：

$ strace -e trace=getpid,getgid ./syscall2
getpid()                                = 2653
getgid()                                = 1000

注意，上面的 getpid 和 getgid 之间以逗号相隔，不能再有其它符号，包括空格。

使用 -o 参数可以将结果导出到一个文件中，如将跟踪 id 这个命令时，可以：

$ strace -o outfile id
uid=1000(beyes) gid=1000(beyes) 组=4(adm),20(dialout),24(cdrom),46(plugdev),105(lpadmin),119(admin),122(sambashare),1000(beyes)

从输出看出，id 指令也运行了，并在当前目录下生成 outfile 文件，在 outfile 文件里，列出了 id 指令所调用的系统调用。这些系统调用非常多，总共有278次之多。为了帮助组织这些调用信息，我们尝试使用 -c 参数，这时结果会按照时间排列调用：

$ strace -c id
uid=1000(beyes) gid=1000(beyes) 组=4(adm),20(dialout),24(cdrom),46(plugdev),105(lpadmin),119(admin),122(sambashare),1000(beyes)
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
  -nan    0.000000           0        17           read
  -nan    0.000000           0         1           write
  -nan    0.000000           0        44         3 open
  -nan    0.000000           0        47           close
  -nan    0.000000           0         1           execve
  -nan    0.000000           0         9         9 access
  -nan    0.000000           0         3           brk
  -nan    0.000000           0        18           munmap
  -nan    0.000000           0        10           mprotect
  -nan    0.000000           0        20           _llseek
  -nan    0.000000           0        51           mmap2
  -nan    0.000000           0        40           fstat64
  -nan    0.000000           0         1           getuid32
  -nan    0.000000           0         1           getgid32
  -nan    0.000000           0         1           geteuid32
  -nan    0.000000           0         1           getegid32
  -nan    0.000000           0         2           getgroups32
  -nan    0.000000           0         1           fcntl64
  -nan    0.000000           0         1           set_thread_area
  -nan    0.000000           0         1           statfs64
  -nan    0.000000           0         4           socket
  -nan    0.000000           0         4         4 connect
------ ----------- ----------- --------- --------- ----------------
100.00    0.000000                   278        16 total

从上面的输出结果可以看到，调用 open 时发生了 3 次错误，调用 connect 时发生了 4 次错误。为了进一步跟踪这些错误，可以将它们单独挑选出来：

$ strace -e trace=open,connect id
open("/etc/ld.so.cache", O_RDONLY)      = 3
open("/lib/libselinux.so.1", O_RDONLY)  = 3
open("/lib/tls/i686/cmov/libc.so.6", O_RDONLY) = 3
open("/lib/tls/i686/cmov/libdl.so.2", O_RDONLY) = 3
open("/proc/filesystems", O_RDONLY|O_LARGEFILE) = 3
open("/proc/filesystems", O_RDONLY|O_LARGEFILE) = 3
open("/usr/lib/locale/locale-archive", O_RDONLY|O_LARGEFILE) = -1 ENOENT (No such file or directory)
open("/usr/share/locale/locale.alias", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_IDENTIFICATION", O_RDONLY) = 3
open("/usr/lib/gconv/gconv-modules.cache", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_MEASUREMENT", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_TELEPHONE", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_ADDRESS", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_NAME", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_PAPER", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_MESSAGES", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_MESSAGES/SYS_LC_MESSAGES", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_MONETARY", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_COLLATE", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_TIME", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_NUMERIC", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_CTYPE", O_RDONLY) = 3
open("/usr/share/locale/zh_CN/LC_MESSAGES/coreutils.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/usr/share/locale/zh/LC_MESSAGES/coreutils.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/usr/share/locale-langpack/zh_CN/LC_MESSAGES/coreutils.mo", O_RDONLY) = 3
connect(3, {sa_family=AF_FILE, path="/var/run/nscd/socket"}, 110) = -1 ENOENT (No such file or directory)
connect(3, {sa_family=AF_FILE, path="/var/run/nscd/socket"}, 110) = -1 ENOENT (No such file or directory)
open("/etc/nsswitch.conf", O_RDONLY)    = 3
open("/etc/ld.so.cache", O_RDONLY)      = 3
open("/lib/tls/i686/cmov/libnss_compat.so.2", O_RDONLY) = 3
open("/lib/tls/i686/cmov/libnsl.so.1", O_RDONLY) = 3
open("/etc/ld.so.cache", O_RDONLY)      = 3
open("/lib/tls/i686/cmov/libnss_nis.so.2", O_RDONLY) = 3
open("/lib/tls/i686/cmov/libnss_files.so.2", O_RDONLY) = 3
open("/etc/passwd", O_RDONLY|O_CLOEXEC) = 3
connect(3, {sa_family=AF_FILE, path="/var/run/nscd/socket"}, 110) = -1 ENOENT (No such file or directory)
connect(3, {sa_family=AF_FILE, path="/var/run/nscd/socket"}, 110) = -1 ENOENT (No such file or directory)
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/proc/sys/kernel/ngroups_max", O_RDONLY) = 3
open("/proc/sys/kernel/ngroups_max", O_RDONLY) = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
uid=1000(beyes) gid=1000(beyes) 组=4(adm),20(dialout),24(cdrom),46(plugdev),105(lpadmin),119(admin),122(sambashare),1000(beyes)

从输出结果(红色加亮部分)可以知道错误在哪里了。

附加到正在运行的程序

strace 的另一个非常好的特性是监视已经运行在系统上的程序的能力。-p 参数可以把 strace 附加到一个 PID 并且捕获系统调用。下面程序可以在后台运行，并且这个程序将维持运行一段时间，在此期间我们用 strace 来捕获它。
程序代码：

	.section.data
timespec:
	.int5,0
output:
	.ascii"This is a test/n"
output_end:
	.equlen,output_end-output

.section.bss
	.lcommrem,8

.section.text
.global_start
_start:
	nop
	movl$10,%ecx

loop1:
	pushl%ecx
	movl$4,%eax
	movl$1,%ebx
	movl$output,%ecx
	movl$len,%edx
	int$0x80

	movl$162,%eax
	movl$timespec,%ebx
	movl$rem,%ecx
	int$0x80
	popl%ecx
	looploop1

	movl$1,%eax
	movl$0,%ebx
	int$0x80

程序中使用了 nanosleep() 这个系统调用函数。在一个终端里后台运行这个函数：

./nanostrace &

然后使用 ps 命令得到此进程的 PID 值，接着可以用 strace 来跟踪了：

$ strace -p 3069
Process 3069 attached - interrupt to quit
restart_syscall(<... resuming interrupted call ...>) = 0
write(1, "This is a test/n", 15)        = 15
nanosleep({5, 0}, 0x80490d0)            = 0
write(1, "This is a test/n", 15)        = 15
nanosleep({5, 0}, 0x80490d0)            = 0
write(1, "This is a test/n", 15)        = 15
nanosleep({5, 0}, 0x80490d0)            = 0
write(1, "This is a test/n", 15)        = 15
nanosleep({5, 0}, 0x80490d0)            = 0
_exit(0)                                = ?

由上可见，程序中使用了 write, nanosleep, exit 3个系统调用。

最简单点对点通信样例

2011-12-08 16:22:00

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <unistd.h>
#include <arpa/inet.h>
#define MAXLINE 4096

#include <sys/ioctl.h>
#include <net/if.h>
#include <net/if_arp.h>

#include <pthread.h>

int send_to_port = 6667;
int self_port = 6666;

void *get(void *data)
{
	int listenfd, connfd;
	struct sockaddr_in servaddr;

	if( (listenfd = socket(AF_INET, SOCK_STREAM, 0)) == -1 ) {
		printf("create socket error: %s(errno: %d)\n",strerror(errno),errno);
		return 0;
	}

	memset(&servaddr, 0, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
	servaddr.sin_port = htons(self_port);

	if( bind(listenfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1) {
		printf("bind socket error: %s(errno: %d)\n",strerror(errno),errno);
		return 0;
	}

	if( listen(listenfd, 10) == -1) {
		printf("listen socket error: %s(errno: %d)\n",strerror(errno),errno);
		return 0;
	}

	char buff[4096];
	int n;
	while(1)
	{
		if( (connfd = accept(listenfd, (struct sockaddr*)NULL, NULL)) == -1) {
			printf("accept socket error: %s(errno: %d)",strerror(errno),errno);
			return 0;
		}
		n = recv(connfd, buff, MAXLINE, 0);
		buff[n] = '\0';
		printf("recv msg from server: %s", buff);

		close(connfd);
	}
	return 0;
}

char server_addr[333];

void *sent(void *data)
{
	int sockfd, n;
	struct sockaddr_in servaddr;
	char sendline[4096];

	while(1)
	{
		fgets(sendline, 4096, stdin);
		
		if( (sockfd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
			printf("create socket error: %s(errno: %d)\n", strerror(errno),errno);
			return 0;
		}

		memset(&servaddr, 0, sizeof(servaddr));
		servaddr.sin_family = AF_INET;
		servaddr.sin_port = htons(send_to_port);
		if( inet_pton(AF_INET, server_addr, &servaddr.sin_addr) <= 0) {
			printf("inet_pton error for %s\n", server_addr);
			return 0;
		}

		if( connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) < 0) {
			printf("connect error: %s(errno: %d)\n",strerror(errno),errno);
			return 0;
		}

		if( send(sockfd, sendline, strlen(sendline), 0) < 0) {
			printf("send msg error: %s(errno: %d)\n", strerror(errno), errno);
		}
		close(sockfd);
	}
	return 0;
}

int main(int argc, char** argv)
{
	if( argc != 2) {
		printf("usage: ./client <ip_address>\n");
		return 0;
	}
	strcpy(server_addr, argv[1]);

	pthread_t th1, th2;
	void *retval;
	pthread_create(&th1, NULL, get, 0);
	pthread_create(&th2, NULL, sent, 0);
	pthread_join(th1, &retval);
	pthread_join(th2, &retval);
	return 0;
}

编译：g++ client.cpp -o client -lpthread
运行：./client xx.xx.xx.xx

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <unistd.h>
#include <arpa/inet.h>
#define MAXLINE 4096

#include <sys/ioctl.h>
#include <net/if.h>
#include <net/if_arp.h>

#include <pthread.h>

int send_to_port = 6666;
int self_port = 6667;

void *get(void *data)
{
	int listenfd, connfd;
	struct sockaddr_in servaddr;

	if( (listenfd = socket(AF_INET, SOCK_STREAM, 0)) == -1 ) {
		printf("create socket error: %s(errno: %d)\n",strerror(errno),errno);
		return 0;
	}

	memset(&servaddr, 0, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
	servaddr.sin_port = htons(self_port);

	if( bind(listenfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1) {
		printf("bind socket error: %s(errno: %d)\n",strerror(errno),errno);
		return 0;
	}

	if( listen(listenfd, 10) == -1) {
		printf("listen socket error: %s(errno: %d)\n",strerror(errno),errno);
		return 0;
	}

	char buff[4096];
	int n;
	while(1)
	{
		if( (connfd = accept(listenfd, (struct sockaddr*)NULL, NULL)) == -1) {
			printf("accept socket error: %s(errno: %d)",strerror(errno),errno);
			return 0;
		}
		n = recv(connfd, buff, MAXLINE, 0);
		buff[n] = '\0';
		printf("recv msg from client: %s", buff);

		close(connfd);
	}
	return 0;
}

char server_addr[333];

void *sent(void *data)
{
	int sockfd, n;
	struct sockaddr_in servaddr;
	char sendline[4096];

	while(1)
	{
		fgets(sendline, 4096, stdin);

		if( (sockfd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
			printf("create socket error: %s(errno: %d)\n", strerror(errno),errno);
			return 0;
		}

		memset(&servaddr, 0, sizeof(servaddr));
		servaddr.sin_family = AF_INET;
		servaddr.sin_port = htons(send_to_port);
		if( inet_pton(AF_INET, server_addr, &servaddr.sin_addr) <= 0) {
			printf("inet_pton error for %s\n", server_addr);
			return 0;
		}

		if( connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) < 0) {
			printf("connect error: %s(errno: %d)\n",strerror(errno),errno);
			return 0;
		}

		if( send(sockfd, sendline, strlen(sendline), 0) < 0) {
			printf("send msg error: %s(errno: %d)\n", strerror(errno), errno);
		}
		close(sockfd);
	}
	return 0;
}

int main(int argc, char** argv)
{
	if( argc != 2) {
		printf("usage: ./server <ip_address>\n");
		return 0;
	}
	strcpy(server_addr, argv[1]);

	pthread_t th1, th2;
	void *retval;
	pthread_create(&th1, NULL, get, 0);
	pthread_create(&th2, NULL, sent, 0);
	pthread_join(th1, &retval);
	pthread_join(th2, &retval);
	return 0;
}

编译：g++ server.cpp -o server -lpthread
运行：./server xx.xx.xx.xx

Linux Socket编程

2011-12-02 15:33:00

本文的主要内容如下：

1、网络中进程之间如何通信？
2、Socket是什么？
3、socket的基本操作
	3.1、socket()函数
	3.2、bind()函数
	3.3、listen()、connect()函数
	3.4、accept()函数
	3.5、read()、write()函数等
	3.6、close()函数
4、socket中TCP的三次握手建立连接详解
5、socket中TCP的四次握手释放连接详解
6、一个例子（实践一下）

1、网络中进程之间如何通信？

本地的进程间通信（IPC）有很多种方式，但可以总结为下面4类：

消息传递（管道、FIFO、消息队列）
同步（互斥量、条件变量、读写锁、文件和写记录锁、信号量）
共享内存（匿名的和具名的）
远程过程调用（Solaris门和Sun RPC）

但这些都不是本文的主题！我们要讨论的是网络中进程之间如何通信？首要解决的问题是如何唯一标识一个进程，否则通信无从谈起！在本地可以通过进程PID来唯一标识一个进程，但是在网络中这是行不通的。

其实TCP/IP协议族已经帮我们解决了这个问题，网络层的“ip地址”可以唯一标识网络中的主机，而传输层的“协议+端口”可以唯一标识主机中的应用程序（进程）。这样利用三元组（ip地址，协议，端口）就可以标识网络的进程了，网络中的进程通信就可以利用这个标志与其它进程进行交互。

使用TCP/IP协议的应用程序通常采用应用编程接口：UNIX BSD的套接字（socket）和UNIX System V的TLI（已经被淘汰），来实现网络进程之间的通信。就目前而言，几乎所有的应用程序都是采用socket，而现在又是网络时代，网络中进程通信是无处不在，这就是我为什么说“一切皆socket”。

2、什么是Socket？

上面我们已经知道网络中的进程是通过socket来通信的，那什么是socket呢？socket起源于Unix，而Unix/Linux基本哲学之一就是“一切皆文件”，都可以用“打开open –> 读写write/read –> 关闭close”模式来操作。

我的理解就是Socket就是该模式的一个实现，socket即是一种特殊的文件，一些socket函数就是对其进行的操作（读/写IO、打开、关闭），这些函数我们在后面进行介绍。

socket一词的起源
在组网领域的首次使用是在1970年2月12日发布的文献IETF RFC33中发现的，撰写者为Stephen Carr、Steve Crocker和Vint Cerf。
根据美国计算机历史博物馆的记载，Croker写道：“命名空间的元素都可称为套接字接口。
一个套接字接口构成一个连接的一端，而一个连接可完全由一对套接字接口规定。”
计算机历史博物馆补充道：“这比BSD的套接字接口定义早了大约12年。”

3、socket的基本操作

既然socket是“open—write/read—close”模式的一种实现，那么socket就提供了这些操作对应的函数接口。下面以TCP为例，介绍几个基本的socket接口函数。

3.1、socket()函数intsocket(int domain, int type, int protocol);

socket函数对应于普通文件的打开操作。普通文件的打开操作返回一个文件描述字，而socket()用于创建一个socket描述符（socket descriptor），它唯一标识一个socket。

这个socket描述字跟文件描述字一样，后续的操作都有用到它，把它作为参数，通过它来进行一些读写操作。

正如可以给fopen的传入不同参数值，以打开不同的文件。创建socket的时候，也可以指定不同的参数创建不同的socket描述符，socket函数的三个参数分别为：

domain：即协议域，又称为协议族（family）。
常用的协议族有，AF_INET、AF_INET6、AF_LOCAL（或称AF_UNIX，Unix域socket）、AF_ROUTE等等。
协议族决定了socket的地址类型，在通信中必须采用对应的地址，
如AF_INET决定了要用ipv4地址（32位的）与端口号（16位的）的组合、AF_UNIX决定了要用一个绝对路径名作为地址。
type：指定socket类型。常用的socket类型有，
SOCK_STREAM、SOCK_DGRAM、SOCK_RAW、SOCK_PACKET、SOCK_SEQPACKET等等（socket的类型有哪些？）。
protocol：故名思意，就是指定协议。常用的协议有，IPPROTO_TCP、IPPTOTO_UDP、IPPROTO_SCTP、IPPROTO_TIPC等，
它们分别对应TCP传输协议、UDP传输协议、STCP传输协议、TIPC传输协议（这个协议我将会单独开篇讨论！）。 

注意：并不是上面的type和protocol可以随意组合的，如SOCK_STREAM不可以跟IPPROTO_UDP组合。
当protocol为0时，会自动选择type类型对应的默认协议。
当我们调用socket创建一个socket时，返回的socket描述字它存在于协议族（address family，AF_XXX）空间中，但没有一个具体的地址。如果想要给它赋值一个地址，就必须调用bind()函数，否则就当调用connect()、listen()时系统会自动随机分配一个端口。

3.2、bind()函数

正如上面所说bind()函数把一个地址族中的特定地址赋给socket。
例如对应AF_INET、AF_INET6就是把一个ipv4或ipv6地址和端口号组合赋给socket。
intbind(int sockfd, conststruct sockaddr *addr, socklen_t addrlen);
函数的三个参数分别为：

sockfd：即socket描述字，它是通过socket()函数创建了，唯一标识一个socket。
bind()函数就是将给这个描述字绑定一个名字。
addr：一个conststruct sockaddr *指针，指向要绑定给sockfd的协议地址。
这个地址结构根据地址创建socket时的地址协议族的不同而不同，如ipv4对应的是：
struct sockaddr_in {
	sa_family_t sin_family; /* address family: AF_INET */
	in_port_t sin_port; /* port in network byte order */
	struct in_addr sin_addr; /* internet address */
};/* Internet address. */
struct in_addr {
	uint32_t s_addr; /* address in network byte order */
};
ipv6对应的是：
struct sockaddr_in6 {
	sa_family_t sin6_family; /* AF_INET6 */
	in_port_t sin6_port; /* port number */
	uint32_t sin6_flowinfo; /* IPv6 flow information */
	struct in6_addr sin6_addr; /* IPv6 address */
	uint32_t sin6_scope_id; /* Scope ID (new in 2.4) */
};
struct in6_addr {
	unsignedchar s6_addr[16]; /* IPv6 address */
};
Unix域对应的是：
#define UNIX_PATH_MAX 108
struct sockaddr_un {
	sa_family_t sun_family; /* AF_UNIX */
	char sun_path[UNIX_PATH_MAX]; /* pathname */
};
addrlen：对应的是地址的长度。 

通常服务器在启动的时候都会绑定一个众所周知的地址（如ip地址+端口号），用于提供服务，客户就可以通过它来接连服务器；而客户端就不用指定，有系统自动分配一个端口号和自身的ip地址组合。

这就是为什么通常服务器端在listen之前会调用bind()，而客户端就不会调用，而是在connect()时由系统随机生成一个。

网络字节序与主机字节序

主机字节序就是我们平常说的大端和小端模式：不同的CPU有不同的字节序类型，这些字节序是指整数在内存中保存的顺序，这个叫做主机序。引用标准的Big-Endian和Little-Endian的定义如下：
　　a) Little-Endian就是低位字节排放在内存的低地址端，高位字节排放在内存的高地址端。
　　b) Big-Endian就是高位字节排放在内存的低地址端，低位字节排放在内存的高地址端。

网络字节序：4个字节的32 bit值以下面的次序传输：首先是0～7bit，其次8～15bit，然后16～23bit，最后是24~31bit。
这种传输次序称作大端字节序。由于TCP/IP首部中所有的二进制整数在网络中传输时都要求以这种次序，因此它又称作网络字节序。
字节序，顾名思义字节的顺序，就是大于一个字节类型的数据在内存中的存放顺序，一个字节的数据没有顺序的问题了。

所以：在将一个地址绑定到socket的时候，请先将主机字节序转换成为网络字节序，而不要假定主机字节序跟网络字节序一样使用的是Big-Endian。由于这个问题曾引发过血案！公司项目代码中由于存在这个问题，导致了很多莫名其妙的问题，所以请谨记对主机字节序不要做任何假定，务必将其转化为网络字节序再赋给socket。

3.3、listen()、connect()函数

如果作为一个服务器，在调用socket()、bind()之后就会调用listen()来监听这个socket，如果客户端这时调用connect()发出连接请求，服务器端就会接收到这个请求。

intlisten(int sockfd, int backlog);intconnect(int sockfd, conststruct sockaddr *addr, socklen_t addrlen);

listen函数的第一个参数即为要监听的socket描述字，第二个参数为相应socket可以排队的最大连接个数。socket()函数创建的socket默认是一个主动类型的，listen函数将socket变为被动类型的，等待客户的连接请求。
connect函数的第一个参数即为客户端的socket描述字，第二参数为服务器的socket地址，第三个参数为socket地址的长度。客户端通过调用connect函数来建立与TCP服务器的连接。

3.4、accept()函数

TCP服务器端依次调用socket()、bind()、listen()之后，就会监听指定的socket地址了。TCP客户端依次调用socket()、connect()之后就想TCP服务器发送了一个连接请求。TCP服务器监听到这个请求之后，就会调用accept()函数取接收请求，这样连接就建立好了。之后就可以开始网络I/O操作了，即类同于普通文件的读写I/O操作。

intaccept(int sockfd, struct sockaddr *addr, socklen_t *addrlen);

accept函数的第一个参数为服务器的socket描述字，第二个参数为指向struct sockaddr *的指针，用于返回客户端的协议地址，第三个参数为协议地址的长度。如果accpet成功，那么其返回值是由内核自动生成的一个全新的描述字，代表与返回客户的TCP连接。

注意：accept的第一个参数为服务器的socket描述字，是服务器开始调用socket()函数生成的，称为监听socket描述字；而accept函数返回的是已连接的socket描述字。一个服务器通常通常仅仅只创建一个监听socket描述字，它在该服务器的生命周期内一直存在。内核为每个由服务器进程接受的客户连接创建了一个已连接socket描述字，当服务器完成了对某个客户的服务，相应的已连接socket描述字就被关闭。

3.5、read()、write()等函数

万事具备只欠东风，至此服务器与客户已经建立好连接了。可以调用网络I/O进行读写操作了，即实现了网咯中不同进程之间的通信！网络I/O操作有下面几组：

read()/write()
recv()/send()
readv()/writev()
recvmsg()/sendmsg()
recvfrom()/sendto()

我推荐使用recvmsg()/sendmsg()函数，这两个函数是最通用的I/O函数，实际上可以把上面的其它函数都替换成这两个函数。它们的声明如下：

#include <unistd.h>
ssize_t read(int fd, void *buf, size_t count);
ssize_t write(int fd, constvoid *buf, size_t count);
#include <sys/types.h>
#include <sys/socket.h>
ssize_t send(int sockfd, constvoid *buf, size_t len, int flags);
ssize_t recv(int sockfd, void *buf, size_t len, int flags);
ssize_t sendto(int sockfd, constvoid *buf, size_t len, int flags, conststruct sockaddr *dest_addr, socklen_t addrlen);
ssize_t recvfrom(int sockfd, void *buf, size_t len, int flags, struct sockaddr *src_addr, socklen_t *addrlen);
ssize_t sendmsg(int sockfd, conststruct msghdr *msg, int flags);
ssize_t recvmsg(int sockfd, struct msghdr *msg, int flags);

read函数是负责从fd中读取内容.当读成功时，read返回实际所读的字节数，如果返回的值是0表示已经读到文件的结束了，小于0表示出现了错误。如果错误为EINTR说明读是由中断引起的，如果是ECONNREST表示网络连接出了问题。

write函数将buf中的nbytes字节内容写入文件描述符fd.成功时返回写的字节数。失败时返回-1，并设置errno变量。

在网络程序中，当我们向套接字文件描述符写时有俩种可能。1)write的返回值大于0，表示写了部分或者是全部的数据。2) 返回的值小于0，此时出现了错误。我们要根据错误类型来处理。如果错误为EINTR表示在写的时候出现了中断错误。如果为EPIPE表示网络连接出现了问题(对方已经关闭了连接)。

其它的我就不一一介绍这几对I/O函数了，具体参见man文档或者baidu、Google，下面的例子中将使用到send/recv。

3.6、close()函数

在服务器与客户端建立连接之后，会进行一些读写操作，完成了读写操作就要关闭相应的socket描述字，好比操作完打开的文件要调用fclose关闭打开的文件。

#include <unistd.h>
int close(int fd);

close一个TCP socket的缺省行为时把该socket标记为以关闭，然后立即返回到调用进程。该描述字不能再由调用进程使用，也就是说不能再作为read或write的第一个参数。注意：close操作只是使相应socket描述字的引用计数-1，只有当引用计数为0的时候，才会触发TCP客户端向服务器发送终止连接请求。

4、socket中TCP的三次握手建立连接详解

我们知道tcp建立连接要进行“三次握手”，即交换三个分组。大致流程如下：

客户端向服务器发送一个SYN J
服务器向客户端响应一个SYN K，并对SYN J进行确认ACK J+1
客户端再想服务器发一个确认ACK K+1 

只有就完了三次握手，但是这个三次握手发生在socket的那几个函数中呢？请看下图：

图1、socket中发送的TCP三次握手

从图中可以看出，当客户端调用connect时，触发了连接请求，向服务器发送了SYN J包，这时connect进入阻塞状态；
服务器监听到连接请求，即收到SYN J包，调用accept函数接收请求向客户端发送SYN K ，ACK J+1，这时accept进入阻塞状态；
客户端收到服务器的SYN K ，ACK J+1之后，这时connect返回，并对SYN K进行确认；
服务器收到ACK K+1时，accept返回，至此三次握手完毕，连接建立。
总结：客户端的connect在三次握手的第二个次返回，而服务器端的accept在三次握手的第三次返回。

5、socket中TCP的四次握手释放连接详解

上面介绍了socket中TCP的三次握手建立过程，及其涉及的socket函数。现在我们介绍socket中的四次握手释放连接的过程，请看下图：

图2、socket中发送的TCP四次握手

图示过程如下：

某个应用进程首先调用close主动关闭连接，这时TCP发送一个FIN M；
另一端接收到FIN M之后，执行被动关闭，对这个FIN进行确认。它的接收也作为文件结束符传递给应用进程，
因为FIN的接收意味着应用进程在相应的连接上再也接收不到额外数据；
一段时间之后，接收到文件结束符的应用进程调用close关闭它的socket。这导致它的TCP也发送一个FIN N；
接收到这个FIN的源发送端TCP对它进行确认。

这样每个方向上都有一个FIN和ACK。

6、一个例子（实践一下）

说了这么多了，动手实践一下。下面编写一个简单的服务器、客户端（使用TCP）——服务器端一直监听本机的6666号端口，如果收到连接请求，将接收请求并接收客户端发来的消息；客户端与服务器端建立连接并发送一条消息。

服务器端代码：

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

#define MAXLINE 4096

int main(int argc, char** argv)
{
	int listenfd, connfd;
	struct sockaddr_in servaddr;
	char buff[4096];
	int n;

	if ((listenfd = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
		printf("create socket error: %s(errno: %d)\n", strerror(errno), errno);
		exit(0);
	}
	memset(&servaddr, 0, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
	servaddr.sin_port = htons(6666);
	if (bind(listenfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1) {
		printf("bind socket error: %s(errno: %d)\n", strerror(errno), errno);
		exit(0);
	}
	if (listen(listenfd, 10) == -1) {
		printf("listen socket error: %s(errno: %d)\n", strerror(errno), errno);
		exit(0);
	}
	printf("======waiting for client's request======\n");
	while (1) {
		if ((connfd = accept(listenfd, (struct sockaddr*)NULL, NULL)) == -1){
			printf("accept socket error: %s(errno: %d)", strerror(errno), errno);
			continue;
		}

		n = recv(connfd, buff, MAXLINE, 0);
		buff[n] ='\0';
		printf("recv msg from client: %s\n", buff);
		close(connfd);
	}
	close(listenfd);
	return 0;
}

客户端代码：

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

#define MAXLINE 4096

int main(int argc, char** argv)
{
	int sockfd, n;
	char recvline[4096], sendline[4096];
	struct sockaddr_in servaddr;
	if (argc != 2) {
		printf("usage: ./client <ipaddress>\n");
		exit(0);
	}
	if ((sockfd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
		printf("create socket error: %s(errno: %d)\n", strerror(errno), errno);
		exit(0);
	}
	memset(&servaddr, 0, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_port = htons(6666);
	if (inet_pton(AF_INET, argv[1], &servaddr.sin_addr) <= 0) {
		printf("inet_pton error for %s\n", argv[1]);
		exit(0);
	}
	if (connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) < 0) {
		printf("connect error: %s(errno: %d)\n", strerror(errno), errno);
		exit(0);
	}
	printf("send msg to server: \n");
	fgets(sendline, 4096, stdin);
	if (send(sockfd, sendline, strlen(sendline), 0) < 0) {
		printf("send msg error: %s(errno: %d)\n", strerror(errno), errno);
		exit(0);
	}
	close(sockfd);
	return 0;
}

当然上面的代码很简单，也有很多缺点，这就只是简单的演示socket的基本函数使用。其实不管有多复杂的网络程序，都使用的这些基本函数。上面的服务器使用的是迭代模式的，即只有处理完一个客户端请求才会去处理下一个客户端的请求，这样的服务器处理能力是很弱的，现实中的服务器都需要有并发处理能力！为了需要并发处理，服务器需要fork()一个新的进程或者线程去处理请求等。

——本文只是介绍了简单的socket编程。更为复杂的需要自己继续深入。

使用内存作Linux下的临时文件夹

2011-12-02 15:30:00

从理论上来说，内存的读写速度是硬盘的几十倍，性能应该会有所提升

在一些访问量比较高的系统上，通过把一些频繁访问的文件，比如session 放入内存中，能够减少很多的iowait，大大提高服务器的性能

在/etc/fstab中加入一行：

none /tmp tmpfs defaults 0 0

重启后生效

或者在/etc/rc.local中加入

mount tmpfs /tmp -t tmpfs -o size=128m

其中size=128m 表示/tmp最大能用128m
或

mount tmpfs /tmp -t tmpfs

不限制大小，这种情况可以用到2G内存，用 df -h 可以看到

tmpfs                 2.0G   48M  2.0G   3% /tmp

注：不管哪种方式，只要linux重启，/tmp下的文件全部消失

另外，在一个正在运行的系统上运行 mount tmpfs /tmp -t tmpfs 会导致 /tmp下原来的所有文件都会被“覆盖”掉，之所以加个“”，因为这种覆盖只是暂时的，如果 umount /tmp的话，原来的文件还能再访问。

因为这些文件会被“覆盖”，比如原来的session mysql.sock等文件就不能访问了，用户的登陆信息就会丢失，mysql数据库也无法连接了(如果mysql.sock位于/tmp下的话)。正确的做法是，先把/tmp下的所有文件临时mv到一个别的目录，mount tmpfs之后，再mv回来

← Older Blog Archives Newer →