天泣記

2007-03-03 (Sat)

#1

続き。

こういうことを考えつつ escape というライブラリ を作っているが、必ずしも考えたことがすべて実装されているわけではない。将来的に実装可能であることは考慮しているが。

しかし、アンエスケープは判断が難しい。HTML (や IRI) を考えると、Unicode が出てくるが,それをどう扱うかが厄介。

HTree::Text では $KCODE に従うよう変換していてそれはそれで正しいのだが、escape でもそうするには文字コード変換まわりのコードが必要になる。

とりあえず 7bit ASCII だけ扱うか?

2007-03-05 (Mon)

#1

はじめてのバイナリコード生成

#include <stdio.h>

int main()
{ 
  char buf[1024];

  buf[0] = 0xc3; /* ret */
  ((void (*)(void))buf)();
  return 0;
} 

2007-03-08 (Thu)

#1 [escape] CSS の url [CODE blog]

CSS には URI を指定する url(...) というのがある。これは background-image とかに使うやつで、 url(http://...) とか、url("http://...") とか、url('http://...') などと書く。

これの、エスケープ事情はどうなのかを調べた。すると、URL 内のカンマをエスケープしなければならないといけないという記述があって、疑問を持った。

まず、CSS1 である。

http://www.w3.org/TR/CSS1#url

Parentheses, commas, whitespace characters, single quotes (') and
double quotes (") appearing in a URL must be escaped with a backslash:
'\(', '\)', '\,'.

url(...) は括弧で区切られているから、括弧をエスケープしないといけないというのは分かる。空白はそもそも URI には使えないはずだからエスケープについて記述する必要はないはずであるが、害はない。シングルクォート、ダブルクォートはそれらを区切りとして使うかどうかに関係するので、これも分かる。

しかし、カンマをエスケープする理由が分からない。

次に、CSS2 を調べてみた。

http://www.w3.org/TR/CSS21/syndata.html#uri

Some characters appearing in an unquoted URI, such as parentheses,
commas, whitespace characters, single quotes (') and double quotes ("),
must be escaped with a backslash so that the resulting URI value is a URI token:
'\(', '\)', '\,'.

すると、カンマをエスケープするという記述は依然としてあるものの、URI が unquoted と修飾されている。

つまり、エスケープ対象の意図は url(http://example.org/foo,bar) などであって、推測すると、url() の引数が 2つにみなせるようなものを禁止し、将来的に引数を増やすことを可能とするように思える。

ただ、付録の字句解析器では、カンマを許しているのが気になる。

http://www.w3.org/TR/CSS21/grammar.html#q2

url             ([!#$%&*-~]|{nonascii}|{escape})*
s               [ \t\r\n\f]+
w               {s}?
...

"url("{w}{url}{w}")"    {return URI;}

2007-03-11 (Sun)

#1

以前から、どうも /dev/poll, kqueue, epoll の速さというのがどこに起因しているのかいまひとつ納得できていなかったのだが、ふと実装して確かめてみようという気になった。

で、select, poll, epoll (level trigger), epoll (edge trigger) で簡単な non-forking echo server を書いてみた。

で、分かったことは、今となっては考えれば明らかという気もするのだが、よーするにこれはオーダの問題なのだ。

select, poll は fd の総数に比例したコストがかかるのに対し、/dev/poll, kqueue, epoll は報告される fd の数に比例したコストしかかからない。

たとえば、n本のコネクションが同時に張られるとすると、サーバ側では少なくとも accept を n回行わなければならない。ここで、各 accept 毎に select や poll が行われるとすると、例によって O(n**2) になる。epoll などでは、O(n) で済む。

以前はなんとなく、別に fd をスキャンするくらいそんなに遅くないんじゃないか、という感覚だったので納得がいかなかったのだが、オーダが変わるとなればすんなりと納得がいく。

ただ、せっかく書いたんだから測定してみよう、と思ったのだが、あまりきれいなデータがとれない。

うぅむ。まだこれが支配的なところまではいってないのか?

と、思ったがそれなりにとれた。

#2

select-echo.c:

#define MAXNUMFD 10000

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

void set_nonblock(int fd)
{
  int flags;
  int ret;

  flags = fcntl(fd, F_GETFL);
  if (flags == -1) { perror("F_GETFL"); exit(1); }
  flags |= O_NONBLOCK;
  ret = fcntl(fd, F_SETFL, flags);
  if (ret == -1) { perror("F_SETFL"); exit(1); }
}

#define BUF_SIZE 4096
typedef struct {
  int beg;
  int end;
  char buf[BUF_SIZE];
} conn_t;

conn_t *conns[MAXNUMFD];

int main(int argc, char **argv)
{
  int port;
  int ret;
  int serv;
  struct sockaddr_in serv_addr;
  struct sockaddr_in clnt_addr;
  socklen_t clnt_addrlen;
  int nfds_in;
  fd_set rfds_in, rfds_out;
  fd_set wfds_in, wfds_out;
  int fd;
  ssize_t ssize;
  struct sigaction sigact;

  int sigaction(int signum, const struct sigaction *act, struct sigaction *oldact);
  sigact.sa_handler = SIG_IGN;
  sigact.sa_flags = 0;
  ret = sigaction(SIGPIPE, &sigact, NULL);
  if (ret == -1) { perror("sigaction"); exit(1); }

  port = atoi(argv[1]);

  serv = socket(AF_INET, SOCK_STREAM, 0);
  if (serv == -1) { perror("socket"); exit(1); }

  set_nonblock(serv);

  serv_addr.sin_family = AF_INET;
  serv_addr.sin_port = htons(port);
  serv_addr.sin_addr.s_addr = INADDR_ANY;

  ret = bind(serv, (const struct sockaddr *)&serv_addr, sizeof(serv_addr));
  if (ret == -1) { perror("bind"); exit(1); }

  ret = listen(serv, 4);
  if (ret == -1) { perror("listen"); exit(1); }

  FD_ZERO(&rfds_in);
  FD_SET(serv, &rfds_in);
  nfds_in = serv+1;

  FD_ZERO(&wfds_in);

  for (;;) {
    memcpy((void*)&rfds_out, (void*)&rfds_in, sizeof(fd_set));
    memcpy((void*)&wfds_out, (void*)&wfds_in, sizeof(fd_set));
    ret = select(nfds_in, &rfds_out, &wfds_out, NULL, NULL);
    if (ret == -1) { perror("select"); exit(1); }

    if (FD_ISSET(serv, &rfds_out)) {
      conn_t *conn;
      clnt_addrlen = sizeof(clnt_addr);
      fd = accept(serv, (struct sockaddr *)&clnt_addr, &clnt_addrlen);
      if (fd == -1) { perror("accept"); exit(1); }
      set_nonblock(fd);
      conn = (conn_t *)malloc(sizeof(conn_t));
      if (conn == NULL) { perror("malloc"); exit(1); }
      conn->beg = 0;
      conn->end = 0;
      conns[fd] = conn;
      FD_SET(fd, &rfds_in);
      if (nfds_in <= fd) nfds_in = fd+1;
      FD_CLR(serv, &rfds_out);
    }

    for (fd = 0; fd < nfds_in; fd++) {
      if (FD_ISSET(fd, &rfds_out)) {
        conn_t *conn = conns[fd];
        ssize = read(fd, conn->buf, BUF_SIZE);
        if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
        if (ssize == -1) { perror("read"); exit(1); }
        if (ssize == 0) {
finish_connection:
          ret = close(fd);
          if (ret == -1) { perror("close"); exit(1); }
          FD_CLR(fd, &rfds_in);
          FD_CLR(fd, &wfds_in);
          free(conns[fd]);
          conns[fd] = NULL;
        }
        else {
          conn->beg = 0;
          conn->end = ssize;
          FD_CLR(fd, &rfds_in);
          FD_SET(fd, &wfds_in);
        }
      }
      else if (FD_ISSET(fd, &wfds_out)) {
        conn_t *conn = conns[fd];
        size_t count = conn->end-conn->beg;
        ssize = write(fd, conn->buf+conn->beg, count);
        if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
        if (ssize == -1 && errno == EPIPE) { goto finish_connection; }
        if (ssize == -1 && errno == EAGAIN) {
          continue;
        }
        if (ssize == -1) { perror("write"); exit(1); }
        conn->beg += ssize;
        if (conn->beg == conn->end) {
          conn->beg = conn->end = 0;
          FD_CLR(fd, &wfds_in);
          FD_SET(fd, &rfds_in);
        }
      }
    }
  }
}

FD_SETSIZE はユーザレベルでどうにかなることが多いがここでは気にしていない。

#3

poll-echo.c:

#define MAXNUMFD 10000

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

void set_nonblock(int fd)
{
  int flags;
  int ret;

  flags = fcntl(fd, F_GETFL);
  if (flags == -1) { perror("F_GETFL"); exit(1); }
  flags |= O_NONBLOCK;
  ret = fcntl(fd, F_SETFL, flags);
  if (ret == -1) { perror("F_SETFL"); exit(1); }
}

#define BUF_SIZE 4096
typedef struct {
  int beg;
  int end;
  char buf[BUF_SIZE];
} conn_t;

conn_t *conns[MAXNUMFD];

int main(int argc, char **argv)
{
  int port;
  int ret;
  int serv;
  struct sockaddr_in serv_addr;
  struct sockaddr_in clnt_addr;
  socklen_t clnt_addrlen;
  nfds_t nfds;
  struct pollfd pfds[MAXNUMFD];
  int fd;
  ssize_t ssize;
  struct sigaction sigact;
  int i;

  int sigaction(int signum, const struct sigaction *act, struct sigaction *oldact);
  sigact.sa_handler = SIG_IGN;
  sigact.sa_flags = 0;
  ret = sigaction(SIGPIPE, &sigact, NULL);
  if (ret == -1) { perror("sigaction"); exit(1); }

  port = atoi(argv[1]);

  serv = socket(AF_INET, SOCK_STREAM, 0);
  if (serv == -1) { perror("socket"); exit(1); }

  set_nonblock(serv);

  serv_addr.sin_family = AF_INET;
  serv_addr.sin_port = htons(port);
  serv_addr.sin_addr.s_addr = INADDR_ANY;

  ret = bind(serv, (const struct sockaddr *)&serv_addr, sizeof(serv_addr));
  if (ret == -1) { perror("bind"); exit(1); }

  ret = listen(serv, 4);
  if (ret == -1) { perror("listen"); exit(1); }

  pfds[0].fd = serv;
  pfds[0].events = POLLIN;
  nfds = 1;

  for (;;) {
    ret = poll(pfds, nfds, -1);
    if (ret == -1 && errno == EINTR) { continue; }
    if (ret == -1) { perror("poll"); exit(1); }

    if (pfds[0].revents & POLLIN) {
      conn_t *conn;
      clnt_addrlen = sizeof(clnt_addr);
      fd = accept(serv, (struct sockaddr *)&clnt_addr, &clnt_addrlen);
      if (fd == -1) { perror("accept"); exit(1); }
      set_nonblock(fd);
      conn = (conn_t *)malloc(sizeof(conn_t));
      if (conn == NULL) { perror("malloc"); exit(1); }
      conn->beg = 0;
      conn->end = 0;
      conns[fd] = conn;
      pfds[nfds].fd = fd;
      pfds[nfds].events = POLLIN;
      pfds[nfds].revents = 0;
      nfds++;
    }

    for (i = 1; i < nfds; i++) {
rescan:
      fd = pfds[i].fd;
      if (pfds[i].revents & POLLIN) {
        conn_t *conn = conns[fd];
        ssize = read(fd, conn->buf, BUF_SIZE);
        if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
        if (ssize == -1) { perror("read"); exit(1); }
        if (ssize == 0) {
finish_connection:
          ret = close(fd);
          if (ret == -1) { perror("close"); exit(1); }
          free(conns[fd]);
          conns[fd] = NULL;
          if (i == nfds-1) {
            nfds--;
            break;
          }
          else {
            pfds[i] = pfds[nfds-1];
            nfds--;
            goto rescan;
          }
        }
        else {
          conn->beg = 0;
          conn->end = ssize;
          pfds[i].events = POLLOUT;
        }
      }
      else if (pfds[i].revents & POLLOUT) {
        conn_t *conn = conns[fd];
        size_t count = conn->end-conn->beg;
        ssize = write(fd, conn->buf+conn->beg, count);
        if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
        if (ssize == -1 && errno == EPIPE) { goto finish_connection; }
        if (ssize == -1 && errno == EAGAIN) {
          continue;
        }
        if (ssize == -1) { perror("write"); exit(1); }
        conn->beg += ssize;
        if (conn->beg == conn->end) {
          conn->beg = conn->end = 0;
          pfds[i].events = POLLIN;
        }
      }
      else if (pfds[i].revents & (POLLERR|POLLHUP)) {
        goto finish_connection;
      }
    }
  }
}
#4

epoll-lt-echo.c:

#define MAXNUMFD 10000

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

void set_nonblock(int fd)
{
  int flags;
  int ret;

  flags = fcntl(fd, F_GETFL);
  if (flags == -1) { perror("F_GETFL"); exit(1); }
  flags |= O_NONBLOCK;
  ret = fcntl(fd, F_SETFL, flags);
  if (ret == -1) { perror("F_SETFL"); exit(1); }
}

#define BUF_SIZE 4096
typedef struct {
  int beg;
  int end;
  char buf[BUF_SIZE];
} conn_t;

conn_t *conns[MAXNUMFD];

int main(int argc, char **argv)
{
  int port;
  int ret;
  int serv;
  struct sockaddr_in serv_addr;
  struct sockaddr_in clnt_addr;
  socklen_t clnt_addrlen;
  nfds_t nfds_out;
  int epfd;
  struct epoll_event epev;
  struct epoll_event epevs[MAXNUMFD];
  int fd;
  ssize_t ssize;
  struct sigaction sigact;
  int i;

  int sigaction(int signum, const struct sigaction *act, struct sigaction *oldact);
  sigact.sa_handler = SIG_IGN;
  sigact.sa_flags = 0;
  ret = sigaction(SIGPIPE, &sigact, NULL);
  if (ret == -1) { perror("sigaction"); exit(1); }

  port = atoi(argv[1]);

  serv = socket(AF_INET, SOCK_STREAM, 0);
  if (serv == -1) { perror("socket"); exit(1); }

  set_nonblock(serv);

  serv_addr.sin_family = AF_INET;
  serv_addr.sin_port = htons(port);
  serv_addr.sin_addr.s_addr = INADDR_ANY;

  ret = bind(serv, (const struct sockaddr *)&serv_addr, sizeof(serv_addr));
  if (ret == -1) { perror("bind"); exit(1); }

  ret = listen(serv, 4);
  if (ret == -1) { perror("listen"); exit(1); }

  epfd = epoll_create(MAXNUMFD);
  if (epfd == -1) { perror("epoll_create"); exit(1); }

  memset(&epev, 0, sizeof(epev));
  epev.events = EPOLLIN;
  epev.data.fd = serv;
  ret = epoll_ctl(epfd, EPOLL_CTL_ADD, serv, &epev);
  if (ret == -1) { perror("epoll_ctl(serv)"); exit(1); }

  for (;;) {
    ret = epoll_wait(epfd, epevs, MAXNUMFD, -1);
    if (ret == -1 && errno == EINTR) { continue; }
    if (ret == -1) { perror("epoll_wait"); exit(1); }
    nfds_out = ret;

    for (i = 0; i < nfds_out; i++) {
      if (epevs[i].data.fd == serv) {
        if (epevs[i].events & EPOLLIN) {
          conn_t *conn;
          clnt_addrlen = sizeof(clnt_addr);
          fd = accept(serv, (struct sockaddr *)&clnt_addr, &clnt_addrlen);
          if (fd == -1) { perror("accept"); exit(1); }
          set_nonblock(fd);
          conn = (conn_t *)malloc(sizeof(conn_t));
          if (conn == NULL) { perror("malloc"); exit(1); }
          conn->beg = 0;
          conn->end = 0;
          conns[fd] = conn;
          epev.events = EPOLLIN;
          epev.data.fd = fd;
          ret = epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &epev);
          if (ret == -1) { perror("epoll_ctl(fd)"); exit(1); }
        }
      }
      else {
        fd = epevs[i].data.fd;
        if (epevs[i].events & EPOLLIN) {
          conn_t *conn = conns[fd];
          ssize = read(fd, conn->buf, BUF_SIZE);
          if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
          if (ssize == -1) { perror("read"); exit(1); }
          if (ssize == 0) {
finish_connection:
            ret = close(fd);
            if (ret == -1) { perror("close"); exit(1); }
            free(conns[fd]);
            conns[fd] = NULL;
          }
          else {
            conn->beg = 0;
            conn->end = ssize;
            epev.events = EPOLLOUT;
            epev.data.fd = fd;
            ret = epoll_ctl(epfd, EPOLL_CTL_MOD, fd, &epev);
            if (ret == -1) { perror("epoll_ctl(EPOLLOUT)"); exit(1); }
          }
        }
        else if (epevs[i].events & EPOLLOUT) {
          conn_t *conn = conns[fd];
          size_t count = conn->end-conn->beg;
          ssize = write(fd, conn->buf+conn->beg, count);
          if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
          if (ssize == -1 && errno == EPIPE) { goto finish_connection; }
          if (ssize == -1 && errno == EAGAIN) {
            continue;
          }
          if (ssize == -1) { perror("write"); exit(1); }
          conn->beg += ssize;
          if (conn->beg == conn->end) {
            conn->beg = conn->end = 0;
            epev.events = EPOLLIN;
            epev.data.fd = fd;
            ret = epoll_ctl(epfd, EPOLL_CTL_MOD, fd, &epev);
            if (ret == -1) { perror("epoll_ctl(EPOLLIN)"); exit(1); }
          }
        }
        else if (epevs[i].events & (EPOLLERR|EPOLLHUP)) {
          goto finish_connection;
        }
      }
    }
  }
}
#5

epoll-et-echo.c:

#define MAXNUMFD 10000

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

void set_nonblock(int fd)
{
  int flags;
  int ret;

  flags = fcntl(fd, F_GETFL);
  if (flags == -1) { perror("F_GETFL"); exit(1); }
  flags |= O_NONBLOCK;
  ret = fcntl(fd, F_SETFL, flags);
  if (ret == -1) { perror("F_SETFL"); exit(1); }
}

#define BUF_SIZE 4096
typedef struct {
  int beg;
  int end;
  char buf[BUF_SIZE];
} conn_t;

conn_t *conns[MAXNUMFD];

int main(int argc, char **argv)
{
  int port;
  int ret;
  int serv;
  struct sockaddr_in serv_addr;
  struct sockaddr_in clnt_addr;
  socklen_t clnt_addrlen;
  nfds_t nfds_out;
  int epfd;
  struct epoll_event epev;
  struct epoll_event epevs[MAXNUMFD];
  int fd;
  ssize_t ssize;
  struct sigaction sigact;
  int i;

  int sigaction(int signum, const struct sigaction *act, struct sigaction *oldact);
  sigact.sa_handler = SIG_IGN;
  sigact.sa_flags = 0;
  ret = sigaction(SIGPIPE, &sigact, NULL);
  if (ret == -1) { perror("sigaction"); exit(1); }

  port = atoi(argv[1]);

  serv = socket(AF_INET, SOCK_STREAM, 0);
  if (serv == -1) { perror("socket"); exit(1); }

  set_nonblock(serv);

  serv_addr.sin_family = AF_INET;
  serv_addr.sin_port = htons(port);
  serv_addr.sin_addr.s_addr = INADDR_ANY;

  ret = bind(serv, (const struct sockaddr *)&serv_addr, sizeof(serv_addr));
  if (ret == -1) { perror("bind"); exit(1); }

  ret = listen(serv, 4);
  if (ret == -1) { perror("listen"); exit(1); }

  epfd = epoll_create(MAXNUMFD);
  if (epfd == -1) { perror("epoll_create"); exit(1); }

  memset(&epev, 0, sizeof(epev));
  epev.events = EPOLLIN;
  epev.data.fd = serv;
  ret = epoll_ctl(epfd, EPOLL_CTL_ADD, serv, &epev);
  if (ret == -1) { perror("epoll_ctl(serv)"); exit(1); }

  for (;;) {
    ret = epoll_wait(epfd, epevs, MAXNUMFD, -1);
    if (ret == -1 && errno == EINTR) { continue; }
    if (ret == -1) { perror("epoll_wait"); exit(1); }
    nfds_out = ret;

    for (i = 0; i < nfds_out; i++) {
      if (epevs[i].data.fd == serv) {
        if (epevs[i].events & EPOLLIN) {
          conn_t *conn;
          clnt_addrlen = sizeof(clnt_addr);
          fd = accept(serv, (struct sockaddr *)&clnt_addr, &clnt_addrlen);
          if (fd == -1) { perror("accept"); exit(1); }
          set_nonblock(fd);
          conn = (conn_t *)malloc(sizeof(conn_t));
          if (conn == NULL) { perror("malloc"); exit(1); }
          conn->beg = 0;
          conn->end = 0;
          conns[fd] = conn;
          epev.events = EPOLLIN|EPOLLOUT|EPOLLET;
          epev.data.fd = fd;
          ret = epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &epev);
          if (ret == -1) { perror("epoll_ctl(fd)"); exit(1); }
        }
      }
      else {
        conn_t *conn;
        fd = epevs[i].data.fd;
        conn = conns[fd];
        if (epevs[i].events & (EPOLLERR|EPOLLHUP)) {
finish_connection:
          ret = close(fd);
          if (ret == -1) { perror("close"); exit(1); }
          free(conns[fd]);
          conns[fd] = NULL;
        }
        else {
          int read_again = 1;
          if (conn->beg != conn->end && !(epevs[i].events & EPOLLOUT)) goto finish_copyloop;
          if (conn->beg == conn->end && !(epevs[i].events & EPOLLIN)) goto finish_copyloop;
          for (;;) {
            if (conn->beg != conn->end) {
              size_t count = conn->end-conn->beg;
              ssize = write(fd, conn->buf+conn->beg, count);
              if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
              if (ssize == -1 && errno == EPIPE) { goto finish_connection; }
              if (ssize == -1 && errno == EAGAIN) { goto finish_copyloop; }
              if (ssize == -1) { perror("write"); exit(1); }
              conn->beg += ssize;
              if (ssize < count) { goto finish_copyloop; }
            }
            if (!read_again) { goto finish_copyloop; }
            ssize = read(fd, conn->buf, BUF_SIZE);
            if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
            if (ssize == -1 && errno == EAGAIN) { goto finish_copyloop; }
            if (ssize == -1) { perror("read"); exit(1); }
            if (ssize == 0) { goto finish_connection; }
            else {
              conn->beg = 0;
              conn->end = ssize;
              if (ssize < BUF_SIZE) read_again = 0;
            }
          }
finish_copyloop:;
        }
      }
    }
  }
}

ここでは、epoll で見付けた fd に対し、処理が EAGAIN とかでとぎれるまでいっきにやっている。クライアントが速くてとぎれなかったら DoS になっちゃう気がするがそこは無視している。

とぎれるまでやるのはエッジトリガで fd を再度報告させるためだが、DoS を避けるにはそこまでやらなくてもいいようにしないといけなくて、そうすると epoll が報告してくれないので、報告がなくても続きを行う仕掛けが必要になる。

あと、エッジトリガの利点は epoll_ctl を途中で呼び出さなくていいことだと思うのだが、それはどのくらい効くのだろう。

2007-03-12 (Mon)

#1

なんか、ssh がときおり切れるので、調べてみた。

ここで、「ssh が切れる」というのは、手元のマシンから ssh で外部のマシンにつなぎ、長くとも 1分間隔でトラフィックがある状態で、ssh が唐突に終了する、というものである。

なお、そのときに、他の ssh が同時に切れるわけではない。

調べてみると、手元のマシンでも、外のマシンでも、切れるタイミングで ssh が ECONNRESET エラーを検出していることが (strace で) 観測された。

さらに調べてみると、両端でパケットを観察すると、たしかに RST パケットが到着していることが (tcpdump で) 分かった。

しかし、両端どちらでも RST パケットを送り出していることは観察できなかった。

つまり、相手が送ったわけではない RST パケットが、なぜか発生して届き、ssh が死ぬのである。

両端が問題ないとすれば、間が問題で、まず怪しいのはルータである。

ルータのログをみると細かいことは記録されていない感じなので、とりあえず接続をやり直してみると、直った感じ。

#2

ちょっと前に、以下のコードを見た。

<URL:http://alohakun.blog7.fc2.com/blog-entry-683.html>

int main(){
  int (*simple_func)(void) = (void *)"\xb8\x7b\x00\x00\x00\xC3";
  return simple_func();
}

まぁ、どうということもないコードである、とは口が裂けてもいえないコードである。

ところで、C では、文字列リテラルを連結できる。従って、次のように書いても良い。

int main(){
  int (*simple_func)(void) = (void *)"\xb8\x7b\x00\x00\x00" "\xc3";
  return simple_func();
}

また、マクロにしても良い。

#define MOV_0x7b_to_EAX "\xb8\x7b\x00\x00\x00"
#define RET "\xc3"

int main(){
  int (*simple_func)(void) = (void *) MOV_0x7b_to_EAX RET;
  return simple_func();
}

オペランドを引数にしちゃったり。

#define MOV_to_EAX(arg) "\xb8" arg
#define RET "\xc3"

int main(){
  int (*simple_func)(void) = (void *) MOV_to_EAX("\x7b\x00\x00\x00") RET;
  return simple_func();
}

引数を文字列じゃなくて書けるようにしてみよう。

#define MOV_to_EAX(n7,n6,n5,n4,n3,n2,n1,n0) "\xb8" BYTE(n1,n0) BYTE(n3,n2) BYTE(n5,n4) BYTE(n7,n6)
#define RET "\xc3"

#define BYTE(hi,lo) BYTEX(hi,lo)
#define BYTEX(hi,lo) BYTE_##hi##lo
#define BYTE_00 "\x00"
...
#define BYTE_ff "\xff"

int main(){
  int (*simple_func)(void) = (void *) MOV_to_EAX(0,0,0,0,0,0,7,b) RET;
  return simple_func();
}

こんなかんじでプリプロセッサでアセンブラを作るとしたら、どこまでできるだろう?

トークン連結を使うとプリプロセッサ内で表引きによりビット演算が実現できそうだから、それなりなところまでいくような気がするのだが。

#3

プリプロセッサによる単純なビット演算はたとえば次のように実現できる。

% cat t.c
#define AND(a,b) XAND(a,b)
#define XAND(a,b) AND_##a##_##b
#define AND_0_0 0
#define AND_0_1 0
#define AND_1_0 0
#define AND_1_1 1

#define XOR(a,b) XXOR(a,b)
#define XXOR(a,b) XOR_##a##_##b
#define XOR_0_0 0
#define XOR_0_1 1
#define XOR_1_0 1
#define XOR_1_1 0

XOR(0,0)
XOR(0,1)
XOR(XOR(1,0),1)
XOR(XOR(0,1),XOR(1,0))

#define ADD(a,b) XADD(AND(a,b),XOR(a,b))
#define XADD(c,d) XXADD(c,d)
#define XXADD(c,d) c ## d

ADD(1,1)
% gcc -E t.c
# 1 "t.c"
# 1 "<built-in>"
# 1 "<command line>"
# 1 "t.c"
# 15 "t.c"
0
1
0
0





10

XOR を計算したり、1+1 が 2進で 10 であることが計算できている。

2007-03-13 (Tue)

#1

epoll とかをもうちょっとまともに測定してみる。

たくさん connect するだけで問題が発生するはずなので、それだけのプログラムを作ってみる。

で、測ってみると、どうも n**2 っぽくならない。うぅむ。理解したと思ったのは間違っていたか?

select も poll も折れ線である。曲線にならない。1700 回 connect するあたりまでは順調なのだが、そこからは定期的に数秒の待ちが入る。(select の FD_SETSIZE 越えを実装したので select も測定できるようになった)

strace で観察すると、select/poll のところで待っている。

time で測ると sys time が大半である。

とすると kernel の中で何をやっているかが問題である。

select/poll が、毎回遅いというのであればそれはそれで分かるのだが、毎回は遅くならず、定期的に遅くなるというのが疑問である。

この定期的というのの周期がどうも listen の backlog と関係しているようで、大きくすると周期がのびる。これの理由が分からない。

2007-03-14 (Wed)

#1

レベルトリガとエッジトリガ、ブロッキングI/OとノンブロッキングI/O の組合せは 2*2=4 種類あるわけだが、そのうち、エッジトリガとブロッキングI/O の組合せは使用不能である。

残り 3種類は使用可能だが、なんというか 3種類というのは座りが悪い。

2007-03-15 (Thu)

#1

g新部さんの助けを借りて、変な挙動の原因を見付ける。

その原因を避けられるように測定してみると... select, poll できれいに O(n**2) の曲線がとれた。

epoll では O(n) の直線なので、でかいところでは桁違いの速度差になる。

(echo サーバに connect だけたくさんして経過時間を測っているので O(n**2), O(n) であるが、コネクションの受け付けひとつあたりの select, poll の時間は O(n), epoll の時間は O(1) になる)

fd が 1000個くらいまでなら select, poll でも遅いけどどうにかって感じだが、10000個になると 2桁違う。

C10K 問題がオーダの違いだという理解は正しかった。

まぁ、ついでにいえば、C1K でも C100K でもなく C10K であるというのはそのあたりで問題が我慢できなくなるということか。

#2

O(n**2) なのが以下のグラフである。横軸がコネクション数で縦軸がそのコネクションを accept するまでにかかった (テスト起動時からの) 時間である。accept というラベルは比較のためのもので、select の類をせずに単に繰り返し accept した場合である。

累積時間

ミクロなところをみるために、上記のデータで、隣接する時間の差をプロットしてみると次のようになる。select と poll がコネクションの数に比例して時間がかかっているのがわかる。

コネクション一本あたりの時間

2007-03-16 (Fri)

#1

測定に使ったソースをあげる。

どれもそうなのだが、select/poll/epoll の処理時間を測るには、まず、それらがブロックしないようにする必要がある。ブロックしちゃったら、処理にかかった時間と新しいデータがくるのを待っていた時間が加算されてしまう。

また、listen しているソケットの backlog があふれないようにしたい。backlog があふれると、クライアント側の処理が滞るのでうまく測定できない。(ここのところが最初にうまく測定できなかった原因であった。ノンブロッキング connect を使えば滞ることはなくなるが、そうするとどういう頻度で接続すればいいか分からない。)

理想は、select/poll/epoll したときに一本のコネクションの接続がカーネルレベルで完了していることである。select/poll/epoll が即座にそれを報告して、accept する、というのを繰り返す場合を測定したい。

しかし、そんなふうなうまい速度でコネクションを張るクライアントを書ける気はしない。とくに、select/poll の場合は保持しているコネクションの数に比例して速度が変化するわけで、その速度変化を測定したいのであるが、その速度変化に応じてコネクションを張る速度を変えるなんて無理である。

で、考え付いたのが、サーバ自身が、select/poll/epoll の直前に自分自身に向けてコネクションを張るというものである。なんというかひどく特殊な条件になってしまっているが、測定したいものを測定するにはしょうがない。

#2

evloop.c:

#include <unistd.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>
#include <signal.h>

void set_nonblock(int fd)
{   
  int flags;
  int ret;

  flags = fcntl(fd, F_GETFL);
  if (flags == -1) { perror("F_GETFL"); exit(1); }
  flags |= O_NONBLOCK;
  ret = fcntl(fd, F_SETFL, flags);
  if (ret == -1) { perror("F_SETFL"); exit(1); }
}

void report(int n)
{ 
  static struct timeval t0, t1;
  static int initialized = 0;
  int ret;
  struct timeval t2;
  long d1, d1sub;
  long d2, d2sub;
  if (!initialized) {
    ret = gettimeofday(&t0, NULL);
    if (ret == -1) { perror("gettimeofday"); exit(1); }
    t1 = t0;
    initialized = 1;
  }

  ret = gettimeofday(&t2, NULL);
  if (ret == -1) { perror("gettimeofday"); exit(1); }

  d1 = t2.tv_sec-t1.tv_sec;
  d1sub = t2.tv_usec-t1.tv_usec;
  if (d1sub < 0) {
    d1sub += 1000000;
    d1 -= 1;
  }

  d2 = t2.tv_sec-t0.tv_sec;
  d2sub = t2.tv_usec-t0.tv_usec;
  if (d2sub < 0) {
    d2sub += 1000000;
    d2 -= 1;
  }

  printf("%d %ld.%06ld %ld.%06ld\n", n, d2, d2sub, d1, d1sub);
  fflush(stdout);
  t1 = t2;
}

void ignore_sigpipe(void)
{
  struct sigaction sigact;
  int ret;
  sigact.sa_handler = SIG_IGN;
  sigact.sa_flags = 0;
  ret = sigaction(SIGPIPE, &sigact, NULL);
  if (ret == -1) { perror("sigaction"); exit(1); }
}

#define BUF_SIZE 4096
typedef struct {
  int beg;
  int end;
  char buf[BUF_SIZE];
} conn_t; 
#3

accept.c:

#define MAXNUMFD 100000

#include "evloop.c"
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <sys/select.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <errno.h>
#include <signal.h>
#include <sys/time.h>
#include <time.h>

conn_t *conns[MAXNUMFD];

int main(int argc, char **argv)
{
  int port;
  int ret;
  int serv;
  struct sockaddr_in serv_addr;
  struct sockaddr_in clnt_addr;
  socklen_t clnt_addrlen;
  int fd;
  int numaccept;
  struct sockaddr_in target_addr;
    socklen_t socklen;

  ignore_sigpipe();

  serv = socket(AF_INET, SOCK_STREAM, 0);
  if (serv == -1) { perror("socket"); exit(1); }

  /*set_nonblock(serv);*/

  serv_addr.sin_family = AF_INET;
  serv_addr.sin_port = htons(0);
  serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);

  ret = bind(serv, (const struct sockaddr *)&serv_addr, sizeof(serv_addr));
  if (ret == -1) { perror("bind"); exit(1); }

  socklen = sizeof(serv_addr);
  ret = getsockname(serv, (struct sockaddr *)&serv_addr, &socklen);
  if (ret == -1) { perror("getsockname"); exit(1); }

  port = ntohs(serv_addr.sin_port);

  ret = listen(serv, 128);
  if (ret == -1) { perror("listen"); exit(1); }

  target_addr.sin_family = AF_INET;
  target_addr.sin_port = htons(port);
  target_addr.sin_addr.s_addr = htonl(INADDR_LOOPBACK);

  numaccept = 0;
  for (;;) {
    {
      int c;
      c = socket(AF_INET, SOCK_STREAM, 0);
      if (c == -1) { perror("socket"); exit(1); }
      ret = connect(c, (const  struct sockaddr *)&target_addr, sizeof(target_addr));
      if (ret == -1) { perror("connect"); exit(1); }
    }
    clnt_addrlen = sizeof(clnt_addr);
    fd = accept(serv, (struct sockaddr *)&clnt_addr, &clnt_addrlen);
    if (fd == -1) { perror("accept"); exit(1); }
    report(numaccept++);
    if (MAXNUMFD <= fd) { fprintf(stderr, "too many fds: %d\n", fd); exit(1); }
  }
}
#4

select.c

#define MAXNUMFD 100000

#include "evloop.c"
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <sys/select.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <errno.h>
#include <signal.h>
#include <sys/time.h>
#include <time.h>

typedef union {
  fd_set set;
  char dummy[MAXNUMFD/8+8];
} fd_set2;

conn_t *conns[MAXNUMFD];

int main(int argc, char **argv)
{
  int port;
  int ret;
  int serv;
  struct sockaddr_in serv_addr;
  struct sockaddr_in clnt_addr;
  socklen_t clnt_addrlen;
  int nfds_in;
  fd_set2 rfds_in, rfds_out;
  fd_set2 wfds_in, wfds_out;
  int fd;
  ssize_t ssize;
  int numaccept;
  struct sockaddr_in target_addr;
  socklen_t socklen;

  ignore_sigpipe();

  serv = socket(AF_INET, SOCK_STREAM, 0);
  if (serv == -1) { perror("socket"); exit(1); }

  set_nonblock(serv);

  serv_addr.sin_family = AF_INET;
  serv_addr.sin_port = htons(0);
  serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);

  ret = bind(serv, (const struct sockaddr *)&serv_addr, sizeof(serv_addr));
  if (ret == -1) { perror("bind"); exit(1); }

  socklen = sizeof(serv_addr);
  ret = getsockname(serv, (struct sockaddr *)&serv_addr, &socklen);
  if (ret == -1) { perror("getsockname"); exit(1); }

  port = ntohs(serv_addr.sin_port);

  ret = listen(serv, 128);
  if (ret == -1) { perror("listen"); exit(1); }

  memset(&rfds_in, 0, sizeof(fd_set2));
  FD_ZERO(&rfds_in.set);
  FD_SET(serv, &rfds_in.set);
  nfds_in = serv+1;

  memset(&wfds_in, 0, sizeof(fd_set2));
  FD_ZERO(&wfds_in.set);

  target_addr.sin_family = AF_INET;
  target_addr.sin_port = htons(port);
  target_addr.sin_addr.s_addr = htonl(INADDR_LOOPBACK);

  numaccept = 0;
  for (;;) {
    {
      int c;
      c = socket(AF_INET, SOCK_STREAM, 0);
      if (c == -1) { perror("socket"); exit(1); }
      ret = connect(c, (const  struct sockaddr *)&target_addr, sizeof(target_addr));
      if (ret == -1) { perror("connect"); exit(1); }
    }
    memcpy((void*)&rfds_out, (void*)&rfds_in, sizeof(fd_set2));
    memcpy((void*)&wfds_out, (void*)&wfds_in, sizeof(fd_set2));
    ret = select(nfds_in, &rfds_out.set, &wfds_out.set, NULL, NULL);
    if (ret == -1) { perror("select"); exit(1); }

    if (FD_ISSET(serv, &rfds_out.set)) {
      conn_t *conn;
      clnt_addrlen = sizeof(clnt_addr);
      fd = accept(serv, (struct sockaddr *)&clnt_addr, &clnt_addrlen);
      if (fd == -1) { perror("accept"); exit(1); }
      report(numaccept++);
      if (MAXNUMFD <= fd) { fprintf(stderr, "too many fds: %d\n", fd); exit(1); }
      set_nonblock(fd);
      conn = (conn_t *)malloc(sizeof(conn_t));
      if (conn == NULL) { perror("malloc"); exit(1); }
      conn->beg = 0;
      conn->end = 0;
      conns[fd] = conn;
      FD_SET(fd, &rfds_in.set);
      if (nfds_in <= fd) nfds_in = fd+1;
      FD_CLR(serv, &rfds_out.set);
    }

    for (fd = 0; fd < nfds_in; fd++) {
      if (FD_ISSET(fd, &rfds_out.set)) {
        conn_t *conn = conns[fd];
        ssize = read(fd, conn->buf, BUF_SIZE);
        if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
        if (ssize == -1) { perror("read"); exit(1); }
        if (ssize == 0) {
finish_connection:
          ret = close(fd);
          if (ret == -1) { perror("close"); exit(1); }
          FD_CLR(fd, &rfds_in.set);
          FD_CLR(fd, &wfds_in.set);
          free(conns[fd]);
          conns[fd] = NULL;
        }
        else {
          conn->beg = 0;
          conn->end = ssize;
          FD_CLR(fd, &rfds_in.set);
          FD_SET(fd, &wfds_in.set);
        }
      }
      else if (FD_ISSET(fd, &wfds_out.set)) {
        conn_t *conn = conns[fd];
        size_t count = conn->end-conn->beg;
        ssize = write(fd, conn->buf+conn->beg, count);
        if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
        if (ssize == -1 && errno == EPIPE) { goto finish_connection; }
        if (ssize == -1 && errno == EAGAIN) {
          continue;
        }
        if (ssize == -1) { perror("write"); exit(1); }
        conn->beg += ssize;
        if (conn->beg == conn->end) {
          conn->beg = conn->end = 0;
          FD_CLR(fd, &wfds_in.set);
          FD_SET(fd, &rfds_in.set);
        }
      }
    }
  }
}
#5

poll.c:

#define MAXNUMFD 100000

#include "evloop.c"
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <poll.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <errno.h>
#include <signal.h>
#include <sys/time.h>
#include <time.h>

conn_t *conns[MAXNUMFD];

int main(int argc, char **argv)
{
  int port;
  int ret;
  int serv;
  struct sockaddr_in serv_addr;
  struct sockaddr_in clnt_addr;
  socklen_t clnt_addrlen;
  nfds_t nfds;
  struct pollfd pfds[MAXNUMFD];
  int fd;
  ssize_t ssize;
  int i;
  int numaccept;
  struct sockaddr_in target_addr;
  socklen_t socklen;

  ignore_sigpipe();

  serv = socket(AF_INET, SOCK_STREAM, 0);
  if (serv == -1) { perror("socket"); exit(1); }

  set_nonblock(serv);

  serv_addr.sin_family = AF_INET;
  serv_addr.sin_port = htons(0);
  serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);

  ret = bind(serv, (const struct sockaddr *)&serv_addr, sizeof(serv_addr));
  if (ret == -1) { perror("bind"); exit(1); }

  socklen = sizeof(serv_addr);
  ret = getsockname(serv, (struct sockaddr *)&serv_addr, &socklen);
  if (ret == -1) { perror("getsockname"); exit(1); }

  port = ntohs(serv_addr.sin_port);

  ret = listen(serv, 128);
  if (ret == -1) { perror("listen"); exit(1); }

  pfds[0].fd = serv;
  pfds[0].events = POLLIN;
  nfds = 1;

  target_addr.sin_family = AF_INET;
  target_addr.sin_port = htons(port);
  target_addr.sin_addr.s_addr = htonl(INADDR_LOOPBACK);

  numaccept = 0;
  for (;;) {
    {
      int c;
      c = socket(AF_INET, SOCK_STREAM, 0);
      if (c == -1) { perror("socket"); exit(1); }
      ret = connect(c, (const  struct sockaddr *)&target_addr, sizeof(target_addr));
      if (ret == -1) { perror("connect"); exit(1); }
    }
    ret = poll(pfds, nfds, -1);
    if (ret == -1 && errno == EINTR) { continue; }
    if (ret == -1) { perror("poll"); exit(1); }

    if (pfds[0].revents & POLLIN) {
      conn_t *conn;
      clnt_addrlen = sizeof(clnt_addr);
      fd = accept(serv, (struct sockaddr *)&clnt_addr, &clnt_addrlen);
      if (fd == -1) { perror("accept"); exit(1); }
      report(numaccept++);
      if (MAXNUMFD <= fd) { fprintf(stderr, "too many fds: %d\n", fd); exit(1); }
      set_nonblock(fd);
      conn = (conn_t *)malloc(sizeof(conn_t));
      if (conn == NULL) { perror("malloc"); exit(1); }
      conn->beg = 0;
      conn->end = 0;
      conns[fd] = conn;
      pfds[nfds].fd = fd;
      pfds[nfds].events = POLLIN;
      pfds[nfds].revents = 0;
      nfds++;
    }

    for (i = 1; i < nfds; i++) {
rescan:
      fd = pfds[i].fd;
      if (pfds[i].revents & POLLIN) {
        conn_t *conn = conns[fd];
        ssize = read(fd, conn->buf, BUF_SIZE);
        if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
        if (ssize == -1) { perror("read"); exit(1); }
        if (ssize == 0) {
finish_connection:
          ret = close(fd);
          if (ret == -1) { perror("close"); exit(1); }
          free(conns[fd]);
          conns[fd] = NULL;
          if (i == nfds-1) {
            nfds--;
            break;
          }
          else {
            pfds[i] = pfds[nfds-1];
            nfds--;
            goto rescan;
          }
        }
        else {
          conn->beg = 0;
          conn->end = ssize;
          pfds[i].events = POLLOUT;
        }
      }
      else if (pfds[i].revents & POLLOUT) {
        conn_t *conn = conns[fd];
        size_t count = conn->end-conn->beg;
        ssize = write(fd, conn->buf+conn->beg, count);
        if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
        if (ssize == -1 && errno == EPIPE) { goto finish_connection; }
        if (ssize == -1 && errno == EAGAIN) {
          continue;
        }
        if (ssize == -1) { perror("write"); exit(1); }
        conn->beg += ssize;
        if (conn->beg == conn->end) {
          conn->beg = conn->end = 0;
          pfds[i].events = POLLIN;
        }
      }
      else if (pfds[i].revents & (POLLERR|POLLHUP)) {
        goto finish_connection;
      }
    }
  }
}
#6

epoll.c (level trigger):

#define MAXNUMFD 100000

#include "evloop.c"
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <poll.h>
#include <sys/epoll.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <errno.h>
#include <signal.h>
#include <sys/time.h>
#include <time.h>

conn_t *conns[MAXNUMFD];

int main(int argc, char **argv)
{
  int port;
  int ret;
  int serv;
  struct sockaddr_in serv_addr;
  struct sockaddr_in clnt_addr;
  socklen_t clnt_addrlen;
  nfds_t nfds_out;
  int epfd;
  struct epoll_event epev;
  struct epoll_event epevs[MAXNUMFD];
  int fd;
  ssize_t ssize;
  int i;
  int numaccept;
  struct sockaddr_in target_addr;
  socklen_t socklen;

  ignore_sigpipe();

  serv = socket(AF_INET, SOCK_STREAM, 0);
  if (serv == -1) { perror("socket"); exit(1); }

  set_nonblock(serv);

  serv_addr.sin_family = AF_INET;
  serv_addr.sin_port = htons(0);
  serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);

  ret = bind(serv, (const struct sockaddr *)&serv_addr, sizeof(serv_addr));
  if (ret == -1) { perror("bind"); exit(1); }

  socklen = sizeof(serv_addr);
  ret = getsockname(serv, (struct sockaddr *)&serv_addr, &socklen);
  if (ret == -1) { perror("getsockname"); exit(1); }

  port = ntohs(serv_addr.sin_port);

  ret = listen(serv, 128);
  if (ret == -1) { perror("listen"); exit(1); }

  epfd = epoll_create(MAXNUMFD);
  if (epfd == -1) { perror("epoll_create"); exit(1); }

  memset(&epev, 0, sizeof(epev));
  epev.events = EPOLLIN;
  epev.data.fd = serv;
  ret = epoll_ctl(epfd, EPOLL_CTL_ADD, serv, &epev);
  if (ret == -1) { perror("epoll_ctl(serv)"); exit(1); }

  target_addr.sin_family = AF_INET;
  target_addr.sin_port = htons(port);
  target_addr.sin_addr.s_addr = htonl(INADDR_LOOPBACK);

  numaccept = 0;
  for (;;) {
    {
      int c;
      c = socket(AF_INET, SOCK_STREAM, 0);
      if (c == -1) { perror("socket"); exit(1); }
      ret = connect(c, (const  struct sockaddr *)&target_addr, sizeof(target_addr));
      if (ret == -1) { perror("connect"); exit(1); }
    }
    ret = epoll_wait(epfd, epevs, MAXNUMFD, -1);
    if (ret == -1 && errno == EINTR) { continue; }
    if (ret == -1) { perror("epoll_wait"); exit(1); }
    nfds_out = ret;

    for (i = 0; i < nfds_out; i++) {
      if (epevs[i].data.fd == serv) {
        if (epevs[i].events & EPOLLIN) {
          conn_t *conn;
          clnt_addrlen = sizeof(clnt_addr);
          fd = accept(serv, (struct sockaddr *)&clnt_addr, &clnt_addrlen);
          report(numaccept++);
          if (fd == -1) { perror("accept"); exit(1); }
          if (MAXNUMFD <= fd) { fprintf(stderr, "too many fds: %d\n", fd); exit(1); }
          set_nonblock(fd);
          conn = (conn_t *)malloc(sizeof(conn_t));
          if (conn == NULL) { perror("malloc"); exit(1); }
          conn->beg = 0;
          conn->end = 0;
          conns[fd] = conn;
          epev.events = EPOLLIN;
          epev.data.fd = fd;
          ret = epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &epev);
          if (ret == -1) { perror("epoll_ctl(fd)"); exit(1); }
        }
      }
      else {
        fd = epevs[i].data.fd;
        if (epevs[i].events & EPOLLIN) {
          conn_t *conn = conns[fd];
          ssize = read(fd, conn->buf, BUF_SIZE);
          if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
          if (ssize == -1) { perror("read"); exit(1); }
          if (ssize == 0) {
finish_connection:
            ret = close(fd);
            if (ret == -1) { perror("close"); exit(1); }
            free(conns[fd]);
            conns[fd] = NULL;
          }
          else {
            conn->beg = 0;
            conn->end = ssize;
            epev.events = EPOLLOUT;
            epev.data.fd = fd;
            ret = epoll_ctl(epfd, EPOLL_CTL_MOD, fd, &epev);
            if (ret == -1) { perror("epoll_ctl(EPOLLOUT)"); exit(1); }
          }
        }
        else if (epevs[i].events & EPOLLOUT) {
          conn_t *conn = conns[fd];
          size_t count = conn->end-conn->beg;
          ssize = write(fd, conn->buf+conn->beg, count);
          if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
          if (ssize == -1 && errno == EPIPE) { goto finish_connection; }
          if (ssize == -1 && errno == EAGAIN) {
            continue;
          }
          if (ssize == -1) { perror("write"); exit(1); }
          conn->beg += ssize;
          if (conn->beg == conn->end) {
            conn->beg = conn->end = 0;
            epev.events = EPOLLIN;
            epev.data.fd = fd;
            ret = epoll_ctl(epfd, EPOLL_CTL_MOD, fd, &epev);
            if (ret == -1) { perror("epoll_ctl(EPOLLIN)"); exit(1); }
          }
        }
        else if (epevs[i].events & (EPOLLERR|EPOLLHUP)) {
          goto finish_connection;
        }
      }
    }
  }
}
#7

epoll.c (edge trigger):

#define MAXNUMFD 100000

#include "evloop.c"
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <poll.h>
#include <sys/epoll.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <errno.h>
#include <signal.h>
#include <sys/time.h>
#include <time.h>

conn_t *conns[MAXNUMFD];

int main(int argc, char **argv)
{
  int port;
  int ret;
  int serv;
  struct sockaddr_in serv_addr;
  struct sockaddr_in clnt_addr;
  socklen_t clnt_addrlen;
  nfds_t nfds_out;
  int epfd;
  struct epoll_event epev;
  struct epoll_event epevs[MAXNUMFD];
  int fd;
  ssize_t ssize;
  int i;
  int numaccept;
  struct sockaddr_in target_addr;
  socklen_t socklen;

  ignore_sigpipe();

  serv = socket(AF_INET, SOCK_STREAM, 0);
  if (serv == -1) { perror("socket"); exit(1); }

  set_nonblock(serv);

  serv_addr.sin_family = AF_INET;
  serv_addr.sin_port = htons(0);
  serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);

  ret = bind(serv, (const struct sockaddr *)&serv_addr, sizeof(serv_addr));
  if (ret == -1) { perror("bind"); exit(1); }

  socklen = sizeof(serv_addr);
  ret = getsockname(serv, (struct sockaddr *)&serv_addr, &socklen);
  if (ret == -1) { perror("getsockname"); exit(1); }

  port = ntohs(serv_addr.sin_port);

  ret = listen(serv, 128);
  if (ret == -1) { perror("listen"); exit(1); }

  epfd = epoll_create(MAXNUMFD);
  if (epfd == -1) { perror("epoll_create"); exit(1); }

  memset(&epev, 0, sizeof(epev));
  epev.events = EPOLLIN;
  epev.data.fd = serv;
  ret = epoll_ctl(epfd, EPOLL_CTL_ADD, serv, &epev);
  if (ret == -1) { perror("epoll_ctl(serv)"); exit(1); }

  target_addr.sin_family = AF_INET;
  target_addr.sin_port = htons(port);
  target_addr.sin_addr.s_addr = htonl(INADDR_LOOPBACK);

  numaccept = 0;
  for (;;) {
    {
      int c;
      c = socket(AF_INET, SOCK_STREAM, 0);
      if (c == -1) { perror("socket"); exit(1); }
      ret = connect(c, (const  struct sockaddr *)&target_addr, sizeof(target_addr));
      if (ret == -1) { perror("connect"); exit(1); }
    }
    ret = epoll_wait(epfd, epevs, MAXNUMFD, -1);
    if (ret == -1 && errno == EINTR) { continue; }
    if (ret == -1) { perror("epoll_wait"); exit(1); }
    nfds_out = ret;

    for (i = 0; i < nfds_out; i++) {
      if (epevs[i].data.fd == serv) {
        if (epevs[i].events & EPOLLIN) {
          for (;;) {
            conn_t *conn;
            clnt_addrlen = sizeof(clnt_addr);
            fd = accept(serv, (struct sockaddr *)&clnt_addr, &clnt_addrlen);
            if (fd == -1 && errno == EAGAIN) { break; }
            if (fd == -1) { perror("accept"); exit(1); }
            report(numaccept++);
            if (MAXNUMFD <= fd) { fprintf(stderr, "too many fds: %d\n", fd); exit(1); }
            set_nonblock(fd);
            conn = (conn_t *)malloc(sizeof(conn_t));
            if (conn == NULL) { perror("malloc"); exit(1); }
            conn->beg = 0;
            conn->end = 0;
            conns[fd] = conn;
            epev.events = EPOLLIN|EPOLLOUT|EPOLLET;
            epev.data.fd = fd;
            ret = epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &epev);
            if (ret == -1) { perror("epoll_ctl(fd)"); exit(1); }
          }
        }
      }
      else {
        conn_t *conn;
        fd = epevs[i].data.fd;
        conn = conns[fd];
        if (epevs[i].events & (EPOLLERR|EPOLLHUP)) {
finish_connection:
          ret = close(fd);
          if (ret == -1) { perror("close"); exit(1); }
          free(conns[fd]);
          conns[fd] = NULL;
        }
        else {
          int read_again = 1;
          if (conn->beg != conn->end && !(epevs[i].events & EPOLLOUT)) goto finish_copyloop;
          if (conn->beg == conn->end && !(epevs[i].events & EPOLLIN)) goto finish_copyloop;
          for (;;) {
            if (conn->beg != conn->end) {
              size_t count = conn->end-conn->beg;
              ssize = write(fd, conn->buf+conn->beg, count);
              if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
              if (ssize == -1 && errno == EPIPE) { goto finish_connection; }
              if (ssize == -1 && errno == EAGAIN) { goto finish_copyloop; }
              if (ssize == -1) { perror("write"); exit(1); }
              conn->beg += ssize;
              if (ssize < count) { goto finish_copyloop; }
            }
            if (!read_again) { goto finish_copyloop; }
            ssize = read(fd, conn->buf, BUF_SIZE);
            if (ssize == -1 && errno == ECONNRESET) { goto finish_connection; }
            if (ssize == -1 && errno == EAGAIN) { goto finish_copyloop; }
            if (ssize == -1) { perror("read"); exit(1); }
            if (ssize == 0) { goto finish_connection; }
            else {
              conn->beg = 0;
              conn->end = ssize;
              if (ssize < BUF_SIZE) read_again = 0;
            }
          }
finish_copyloop:;
        }
      }
    }
  }
}
#8

ふと、"s_addr = INADDR_LOOPBACK" を検索してみた。

<URL:http://www.google.com/codesearch?hl=en&q=+%22s_addr+%3D+INADDR_LOOPBACK%22&start=60&sa=N>

#9

「UNIXネットワークプログラミング第2版Vol.1」を調べていて、pselect の記述に気がつく。

そーか、pselect ってそう使うのか。signal を race 無しで扱えるんだな。今まで気がついてなかった。

でも GNU/Linux では pselect って glibc で実装されていて race があるんだよなぁ、と思いつつ調べ直すとなんと Linux 2.6.16 で pselect, ppoll が追加されていたらしい。

そんなら pepoll_wait は、というと、提案 はあったようだ。

あー、結局 epoll_pwait という名前で入っているのか。Linux 2.6.19 から、かな。

2007-03-17 (Sat)

#1

epoll のマニュアルに、エッジトリガの場合に、read でバッファが埋まらなかったらカーネルのデータが底をついたことがわかるのでそこまででいい、という話が Q9, A9 に書いてある。

が、socket が half close したときにはそうはいかないということに気がついた。

<URL:http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=415214>

2007-03-18 (Sun)

#1

pselect, ppoll, epoll_pwait に対して、kqueue にはそういうのはあるのか、と思って調べてみると、kqueue のやりかたは違うらしい。

pselect のとりこぼしのない signal 処理は、普段は signal をシグナルマスクで受け付けないでおいて、pselect の中だけで signal を受け付ける、というものである。こうすると pselect 起動直前のレースコンディションをつぶして、signal が届いたのにブロックしちゃうということを防げる。

それに対し、kqueue のやりかたは、シグナルハンドラを SIG_IGN にしておいて、kevent の中だけで signal を受け付ける、というものである。

どちらも普段は無視しておいて、I/O 待ちのところで検出するのは同じだが、無視する方法が違うので、kqueue でシグナルマスクを指定する必要はないようだ。

2007-03-19 (Mon)

#1

エッジトリガでは、epoll と epoll の間に EAGAIN になるまで処理をすることを強いられる。

さて、レベルトリガでも、EAGAIN になるまで処理していけない理由はない。

EAGAIN になるまで処理をするというのは、カーネルレベルのバッファを限界まで使うということである。読み込みバッファが空になるか、書き込みバッファが満杯になるところまで処理をすることになる。

さて、こうしたときに性能はどうなるだろう?

考えてみると、もし、アプリケーションのバッファをカーネルのバッファよりも大きくしておけば、EAGAIN になるまでやらなくても、1回 read/write すれば同じだけ転送できるはずである。

そうすると疑問は、バッファのサイズと性能はどう関係するか、というように変わる。

epoll は性質が面白くないので、select について考えよう。

select は fd 数に比例した時間がかかるので、充分に fd 数が多ければ、その時間が支配的になる。そして、その時間に到着したデータがカーネルのバッファを満杯にするとすれば、満杯になった以降、select が終わるまではネットワーク資源を利用できない。つまり、バンド幅を利用し尽くせないことになる。ここで select の時間が支配的であるとしたので、イベントループを一回りする中で、ほとんどの時間は select に費される。そして、ひとまわりする毎に処理できるのは、バッファの大きさのデータである。バッファの大きさが固定だとすると、fd 数に反比例して性能が落ちていく。

また、fd数が少なく、select にかかる時間が無視できて、CPU がネットワークのバンド幅に追い付けるのであれば、サーバはネットワークのバンド幅を利用し尽くすことができ、また、それが性能の上限となるので、バッファサイズには依存しない。

とすると、転送速度は、fd数が少ないときはネットワーク性能で一定であり、fd数が多くなってくると反比例して落ちていく、という理屈になる。

で、測ってみるとそうなった。コネクションを張る数を変化させ、ひとつのコネクションで転送速度を測ってみた。

コネクション増加に対する性能低下

バッファサイズは 4K のものと、EAGAIN まで行う (カーネルのバッファを全部使う) ものを用意し、また、ネットワークのバンド幅は、ちょうど 10M のハブがあったのでそれと 100M で比較した。

バッファサイズの違いは、やはり反比例して性能が落ちていくところにしか効いていない。fd が小さいときはバッファサイズにかかわらず同じ性能である。

また、バンド幅の違いは、性能の上限に効いており、反比例していくところの曲線には影響を与えない。実際、バッファが 4K のときの 2つの曲線は、10M と 100M で重なっている。

2007-03-21 (Wed)

#1

うぅむ。性能低下の測定は、変だったようだ。

クライアント側のボトルネックが出ていたかんじ。

2007-03-28 (Wed)

#1

いろいろと測っていると... Kernel panic

Kernel panic にならずにうんともすんともいわなくなることもある。

また、コネクションの片方が ESTABLISHED のまま、もう一方が跡形もなく消えるとか。

うぅむ。Out of socket memory なあたりは危ないか?

とりあえず linux を 2.6.20.4 にしてみよう。(いままでは 2.6.17.11 だった)

2007-03-29 (Thu)

#1

2.6.20.4 にしても Kernel panic がおこる。

とりあえずメッセージをちゃんと記録するために、serial console を設定する。

で、記録したのが以下。

BUG: unable to handle kernel paging request at virtual address 04000000
 printing eip:
c027c23d
*pde = 00000000
Oops: 0002 [#1]
SMP
Modules linked in: ipv6
CPU:    3
EIP:    0060:[<c027c23d>]    Not tainted VLI
EFLAGS: 00010206   (2.6.20.4 #2)
EIP is at skb_clone+0xa1/0x1a4
eax: 04000000   ebx: f2b7611c   ecx: 00000001   edx: 00000000
esi: f2eba080   edi: f2b76080   ebp: f2b76080   esp: f7c45e78
ds: 007b   es: 007b   ss: 0068
Process swapper (pid: 0, ti=f7c44000 task=f7c32a70 task.ti=f7c44000)
Stack: 00000001 f2eba080 f2b76080 00000020 c02a68cf 00000000 00000000 00000000
       00000000 00000000 00000000 00000000 00000020 f2b76080 f2eba080 00000000
       000005a8 c02a883b 00000020 00000001 00000001 c02a1ad7 f2eba080 f7c78000
Call Trace:
 [<c02a68cf>] tcp_transmit_skb+0x68/0x3f5
 [<c02a883b>] tcp_retransmit_skb+0x1d0/0x261
 [<c02a1ad7>] tcp_enter_loss+0x1ac/0x20a
 [<c02aa2c4>] tcp_write_timer+0x0/0xad
 [<c02aa1bd>] tcp_retransmit_timer+0x27a/0x381
 [<c011f8db>] lock_timer_base+0x15/0x2f
 [<c011f975>] __mod_timer+0x80/0x88
 [<c02aa33c>] tcp_write_timer+0x78/0xad
 [<c0120750>] run_timer_softirq+0x10a/0x164
 [<c011c7b6>] __do_softirq+0x60/0xba
 [<c011c841>] do_softirq+0x31/0x35
 [<c010c818>] smp_apic_timer_interrupt+0x71/0x7a
 [<c0103354>] apic_timer_interrupt+0x28/0x30
 [<c0100c00>] default_idle+0x0/0x3f
 [<c0100c2d>] default_idle+0x2d/0x3f
 [<c0100ca0>] cpu_idle+0x5e/0x73
 =======================
Code: 1c 8b 45 20 89 43 20 8b 45 24 89 43 24 8b 45 28 89 43 28 8b 45 28 85 c0 74 04 f0 ff 40 04 8b 45 2c 89 43 2c 8b 45 2c 85 c0 74 03 <f0> ff 00 8d 7b 30 8d 75 30 b9 0c 00 00 00 f3 a5 0f b6 53 74 8b
EIP: [<c027c23d>] skb_clone+0xa1/0x1a4 SS:ESP 0068:f7c45e78
 <0>Kernel panic - not syncing: Fatal exception in interrupt
#2

grub にも serial console の設定を行う。

そして、AC Power Control through USB を使って、電源もリモートから on/off できるようにする。

これで、リモートからでも安心してカーネルをいじれる?

2007-03-30 (Fri)

#1

さて、EIP is at skb_clone+0xa1/0x1a4 と出ているので、問題が skb_clone の中で起きたことは分かる。でも、ソースコードではどこなのかを知りたい。

調べてみると、addr2line でできるらしい... が、できない。カーネルにデバッグ情報がついてなかった。

で、デバッグ情報をつけてコンパイルしなおして再現させた。

[ 2536.039667] Out of socket memory
[ 2536.049415] Out of socket memory 
[ 2536.059164] Out of socket memory 
[ 2542.138445] printk: 1118 messages suppressed.
[ 2542.151689] Out of socket memory
[ 2920.739557] BUG: unable to handle kernel paging request at virtual address 04000000
[ 2920.762826]  printing eip:
[ 2920.770957] c027c34d
[ 2920.777485] *pde = 00000000
[ 2920.785839] Oops: 0002 [#1]
[ 2920.794181] SMP 
[ 2920.799684] Modules linked in: ipv6
[ 2920.810130] CPU:    2
[ 2920.810131] EIP:    0060:[<c027c34d>]    Not tainted VLI
[ 2920.810132] EFLAGS: 00010206   (2.6.20.4 #4)
[ 2920.845568] EIP is at skb_clone+0xa1/0x1a4
[ 2920.857811] eax: 04000000   ebx: f3eb611c   ecx: 00000001   edx: 00000000
[ 2920.878120] esi: f0ef5b80   edi: f3eb6080   ebp: f3eb6080   esp: f7c43d9c
[ 2920.898426] ds: 007b   es: 007b   ss: 0068
[ 2920.910670] Process swapper (pid: 0, ti=f7c42000 task=f7c2b030 task.ti=f7c42000)
[ 2920.932278] Stack: 00000001 f0ef5b80 f3eb6080 00000020 c02a69df ec058980 f0ef5b80 f0ef5b80
[ 2920.957367]        ec058a80 c02a9743 00000020 f0ef5b80 f427cc34 000005a8 f0ef5b80 f3eb6080
[ 2920.982458]        000005a8 c02a8037 00000020 52ca2f90 00000001 00000000 00000001 00000000
[ 2921.007548] Call Trace:
[ 2921.015390]  [<c02a69df>] tcp_transmit_skb+0x68/0x3f5
[ 2921.030511]  [<c02a9743>] tcp_send_ack+0xe6/0xea
[ 2921.044328]  [<c02a8037>] tcp_write_xmit+0x1c3/0x22a
[ 2921.059186]  [<c02a80bc>] __tcp_push_pending_frames+0x1e/0x6f
[ 2921.076383]  [<c02a64d3>] tcp_rcv_state_process+0x7a7/0x7e0
[ 2921.093059]  [<c02ac352>] tcp_v4_do_rcv+0x8e/0xc3
[ 2921.107136]  [<c02ac7de>] tcp_v4_rcv+0x457/0x721
[ 2921.120953]  [<c02949ed>] ip_local_deliver+0x150/0x1f9
[ 2921.136333]  [<c021e865>] e1000_alloc_rx_buffers+0x1d9/0x2a1
[ 2921.153276]  [<c0294e6f>] ip_rcv+0x3d9/0x417
[ 2921.166051]  [<c0281872>] netif_receive_skb+0x215/0x22b
[ 2921.181690]  [<c0281916>] process_backlog+0x8e/0xf4
[ 2921.196287]  [<c0281a0e>] net_rx_action+0x92/0x141
[ 2921.210624]  [<c011c7c6>] __do_softirq+0x60/0xba
[ 2921.224443]  [<c011c851>] do_softirq+0x31/0x35
[ 2921.237738]  [<c0104b0a>] do_IRQ+0x62/0x74
[ 2921.249997]  [<c0103297>] common_interrupt+0x23/0x28
[ 2921.264854]  [<c0100c00>] default_idle+0x0/0x3f
[ 2921.278410]  [<c0100c2d>] default_idle+0x2d/0x3f
[ 2921.292226]  [<c0100ca0>] cpu_idle+0x5e/0x73
[ 2921.305001]  =======================
[ 2921.315684] Code: 1c 8b 45 20 89 43 20 8b 45 24 89 43 24 8b 45 28 89 43 28 8b 45 28 85 c0 74 04 f0 ff 40 04 8b 45 2c 89 43 2c 8b 45 2c 85 c0 74 03 <f0> ff 00 8d 7b 30 8d 75 30 b9 0c 00 00 00 f3 a5 0f b6 53 74 8b
[ 2921.372861] EIP: [<c027c34d>] skb_clone+0xa1/0x1a4 SS:ESP 0068:f7c43d9c
[ 2921.394029]  <0>Kernel panic - not syncing: Fatal exception in interrupt
[ 2921.415145]

なんとなく printk で時間を表示するオプションもつけたので、先頭に時間が出ている。

それはそれとしてソースコードと行番号に変換する。

% addr2line -e vmlinux c027c34d c02a69df c02a9743 c02a8037 c02a80bc c02a64d3 c02ac352 c02ac7de c02949ed c021e865 c0294e6f c0281872 c0281916 c0281a0e c011c7c6 c011c851 c0104b0a c0103297 c0100c00 c0100c2d c0100ca0
include/asm/atomic.h:96
net/ipv4/tcp_output.c:416
net/ipv4/tcp_output.c:2392
net/ipv4/tcp_output.c:1421
net/ipv4/tcp_output.c:1450
net/ipv4/tcp_input.c:3631
net/ipv4/tcp_ipv4.c:1584
net/ipv4/tcp_ipv4.c:1683
net/ipv4/ip_input.c:237
drivers/net/e1000/e1000_main.c:4591
include/net/dst.h:239
net/core/dev.c:1843
include/asm/atomic.h:109
net/core/dev.c:1925
include/linux/rcupdate.h:129
include/asm/irqflags.h:33
arch/i386/kernel/irq.c:131
??:0
arch/i386/kernel/process.c:103
include/asm/irqflags.h:57
include/asm/thread_info.h:93

これをコールスタックとあわせると以下のとおり。

[<c027c34d>] skb_clone+0xa1/0x1a4                               include/asm/atomic.h:96
[<c02a69df>] tcp_transmit_skb+0x68/0x3f5                        net/ipv4/tcp_output.c:416
[<c02a9743>] tcp_send_ack+0xe6/0xea                             net/ipv4/tcp_output.c:2392
[<c02a8037>] tcp_write_xmit+0x1c3/0x22a                         net/ipv4/tcp_output.c:1421
[<c02a80bc>] __tcp_push_pending_frames+0x1e/0x6f                net/ipv4/tcp_output.c:1450
[<c02a64d3>] tcp_rcv_state_process+0x7a7/0x7e0                  net/ipv4/tcp_input.c:3631
[<c02ac352>] tcp_v4_do_rcv+0x8e/0xc3                            net/ipv4/tcp_ipv4.c:1584
[<c02ac7de>] tcp_v4_rcv+0x457/0x721                             net/ipv4/tcp_ipv4.c:1683
[<c02949ed>] ip_local_deliver+0x150/0x1f9                       net/ipv4/ip_input.c:237
[<c021e865>] e1000_alloc_rx_buffers+0x1d9/0x2a1                 drivers/net/e1000/e1000_main
[<c0294e6f>] ip_rcv+0x3d9/0x417                                 include/net/dst.h:239
[<c0281872>] netif_receive_skb+0x215/0x22b                      net/core/dev.c:1843
[<c0281916>] process_backlog+0x8e/0xf4                          include/asm/atomic.h:109
[<c0281a0e>] net_rx_action+0x92/0x141                           net/core/dev.c:1925
[<c011c7c6>] __do_softirq+0x60/0xba                             include/linux/rcupdate.h:129
[<c011c851>] do_softirq+0x31/0x35                               include/asm/irqflags.h:33
[<c0104b0a>] do_IRQ+0x62/0x74                                   arch/i386/kernel/irq.c:131
[<c0103297>] common_interrupt+0x23/0x28                         ??:0
[<c0100c00>] default_idle+0x0/0x3f                              arch/i386/kernel/process.c:1
[<c0100c2d>] default_idle+0x2d/0x3f                             include/asm/irqflags.h:57
[<c0100ca0>] cpu_idle+0x5e/0x73                                 include/asm/thread_info.h:93

skb_clone なのに include/asm/atomic.h というのは変だが、これは atomic_inc というのがインライン展開されている模様。

gdb で skb_clone を disassemble してみる。

% gdb vmlinux
GNU gdb 6.3-debian
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i386-linux"...disUsing host libthread_db library "/lib/tls/libthread_db.so.1".

(gdb) disassemble skb_clone
Dump of assembler code for function skb_clone:
0xc027c2ac <skb_clone+0>:       push   %ebp
...
0xc027c44f <skb_clone+419>:     ret
End of assembler dump.
(gdb)

よくわからないので、そういえば、objdump でソース込で disassemble できたよな、と思ってやってみる。

% objdump -d -lS --start-address=0xc027c2ac --stop-address=0xc027c450 vmlinux

vmlinux:     file format elf32-i386

Disassembly of section .text:

c027c2ac <skb_clone>:
skb_clone():
net/core/skbuff.c:433
 *      %GFP_ATOMIC.
 */

struct sk_buff *skb_clone(struct sk_buff *skb, gfp_t gfp_mask)
{
c027c2ac:       55                      push   %ebp
c027c2ad:       89 c5                   mov    %eax,%ebp
c027c2af:       57                      push   %edi
c027c2b0:       56                      push   %esi
c027c2b1:       53                      push   %ebx
net/core/skbuff.c:436
        struct sk_buff *n;

        n = skb + 1;
c027c2b2:       8d 98 9c 00 00 00       lea    0x9c(%eax),%ebx
net/core/skbuff.c:437
        if (skb->fclone == SKB_FCLONE_ORIG &&
c027c2b8:       0f b6 40 75             movzbl 0x75(%eax),%eax
c027c2bc:       83 e0 18                and    $0x18,%eax
c027c2bf:       3c 08                   cmp    $0x8,%al
c027c2c1:       75 1a                   jne    c027c2dd <skb_clone+0x31>
c027c2c3:       0f b6 43 75             movzbl 0x75(%ebx),%eax
c027c2c7:       a8 18                   test   $0x18,%al
c027c2c9:       75 12                   jne    c027c2dd <skb_clone+0x31>
...
net/core/skbuff.c:460
        dst_clone(skb->dst);
        C(sp);
c027c340:       8b 45 2c                mov    0x2c(%ebp),%eax
c027c343:       89 43 2c                mov    %eax,0x2c(%ebx)
include/net/xfrm.h:595
};

static inline struct sec_path *
secpath_get(struct sec_path *sp)
{
c027c346:       8b 45 2c                mov    0x2c(%ebp),%eax
include/net/xfrm.h:596
        if (sp)
c027c349:       85 c0                   test   %eax,%eax
c027c34b:       74 03                   je     c027c350 <skb_clone+0xa4>
include/asm/atomic.h:96
 * Atomically increments @v by 1.
 */
static __inline__ void atomic_inc(atomic_t *v)
{
        __asm__ __volatile__(
c027c34d:       f0 ff 00                lock incl (%eax)
include/asm/string.h:226
 * This looks ugly, but the compiler can optimize it totally,
 * as the count is constant.
 */
static __always_inline void * __constant_memcpy(void * to, const void * from, size_t n)
{
c027c350:       8d 7b 30                lea    0x30(%ebx),%edi
c027c353:       8d 75 30                lea    0x30(%ebp),%esi
...
        return n;
c027c445:       89 d8                   mov    %ebx,%eax
net/core/skbuff.c:512
c027c447:       80 4d 74 02             orb    $0x2,0x74(%ebp)
net/core/skbuff.c:515 
}
c027c44b:       5b                      pop    %ebx
c027c44c:       5e                      pop    %esi
c027c44d:       5f                      pop    %edi
c027c44e:       5d                      pop    %ebp
c027c44f:       c3                      ret    
Disassembly of section .init.text:
Disassembly of section .altinstr_replacement:
Disassembly of section .exit.text:

panic になった命令は以下のところである。

c027c34d:       f0 ff 00                lock incl (%eax)

問題は以下のように 04000000 にアクセスできない、というものであった。

[ 2920.739557] BUG: unable to handle kernel paging request at virtual address 04000000

そして、レジスタをみるとちょうど eax が 04000000 である。

[ 2920.857811] eax: 04000000   ebx: f3eb611c   ecx: 00000001   edx: 00000000

とすると、この時点の eax が問題ということが分かる。

そこから上にさかのぼっていくと、ここでの eax はどうもソースでは sp という変数らしい。

include/net/xfrm.h:596
        if (sp)
c027c349:       85 c0                   test   %eax,%eax
c027c34b:       74 03                   je     c027c350 <skb_clone+0xa4>
include/asm/atomic.h:96
 * Atomically increments @v by 1.
 */
static __inline__ void atomic_inc(atomic_t *v)
{
        __asm__ __volatile__(
c027c34d:       f0 ff 00                lock incl (%eax)

if (sp) に対応して test %eax,%eax と書いてあるので、これはどう考えても sp と eax が対応している。

さらに上にさかのぼってソースと突き合わせると、ここのコードが、skb_clone 内の以下のコードの、secpath_get がインライン展開されたものであることが分かる。

dst_clone(skb->dst);
C(sp);
#ifdef CONFIG_INET
        secpath_get(skb->sp);
#endif

とすると、問題は skb->sp が 04000000 になっている、ということである。

あとはそれがどこで起きたかを調べることになる。

2007-03-31 (Sat)

#1

ところで、シリアル接続をまともにつかったのは初めてな気がする。

これにはなぜか苦手意識があったのだが、今回は問題なく動いたので気分が良い。

ついでに勉強しようと思っていろいろと探してみる。

結局、Linux Serial HOWTO がかなり詳しくておもしろかった。(でも、「電圧を味わってみる」の項はどうなんだろうか)


[latest]


田中哲