2008年07月29日

社内コードコンペ - お題:最速なCIDRブロックマッチ判定 〜 ひろせの場合 - IP::CountryとAPRを使ってみた 〜

はてなブックマークに登録

突然始まった社内コードコンペ

ある晴れた日のことです。 「とあるIPアドレスが、 予め与えられている複数のCIDRブロックのどれかに含まれるかどうか」、 を判定するロジックを書こうとしていました。

どうせならばと、いくつか違った方法で実装してみてベンチマークをとって最良のものを採用しようと思い、いく通りかの実装方法を考えてみました。この方法は速そうだけどメモリ消費が多そうとか、この方法は明らかに遅いけど一応実装してみるかーなどなど。

ってなことを社内IRCであーでもないこーでもないとひとりつぶやきながらコードを書いていたところ、案の定、興味を持った何人かが釣れました。フフフ。

そんな流れで釣れたエンジニアを巻き込んで、お題についてコードを書いて競う社内コードコンペがはじまりました(ちなみに、優勝賞品はカレーです)。

お題自体はそれほど複雑なものではないのですが、書く人によって意外と趣向が違ったりしておもしろかったので、 本エントリも含めこれから何回かにわけて、参加者自らが自分のコードの解説や自慢をするエントリをお届けしたいなと思います。

お題

まず、お題についてまとめておきます。

  • 『グループ』は複数のCIDRブロックから成り立っています
  • 『グループ』は複数あります
  • とあるIPアドレスが、どの『グループ』に所属するかを、当該グループのいずれかのCIDRブロックに含まれるかどうかで判断する、というのがお題です。
  • もし、グループを越えて含まれるCIDRブロックが複数ある場合は、よりネットマスクが長いものを採用します。
  • ベンチマークでは、CIDRマッチ処理の部分のみを計測対象とし、初期化処理は測定対象には入れません

具体例はこんな感じです。

2つのファイル、yaoyaとsakanayaがあり中身はこうだとします。

$ cat yaoya
172.16.0.0/16

$ cat sakanaya
10.0.1.0/24
10.1.1.0/24
10.2.1.0/24

そして、検査対象のIPアドレスが10.1.1.1だとします。

このIPアドレスは、sakanayaの2つめのCIDRの10.1.1.0/24に含まれるので、グループsakanayaに属している、ということになります。

本データでは、グループ数が20個程度、総CIDRブロック数が270個程度です。つまり、それほど大きなデータではありません。


このコードのウリ

というわけで、第1回はひろせのコードです。こんにちは。

モットーはいかにコードを書かないで済ますかwで、既存の実装の流用やライブラリを使って書いてみました。

最初にお伝えしておくと、わたしのコードがいちばん遅かったです。壊滅的に遅かったです。次回以降はびゅんびゅんに速いコードが出てきますので、今回は導入程度と思っていただき、おもしろげなコードは次回以降にご期待ください。

コード解説

今回は2種類紹介します。APRを使ったものと、IP::Countryのコードを流用したものです。

共通部分

まずは共通部分のコードを。次回以降もこの部分は共通です。

cidr_initialize()で初期化処理をして、cidr_lookup()でマッチ判定をやります。 cidr_loopupには、コマンドの引数で指定されたIPアドレスをstruct in_addrに変換して渡しています。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <sys/socket.h>
#include <netinet/in.h>

#include <arpa/inet.h>

void  cidr_initialize();
char *cidr_lookup(void *ipaddr, int len);

int main(int argc, char *argv[]) {
  int i, j;
  int nipaddr = argc - 1;
  char *label;
  struct in_addr addrs[nipaddr];

  if (argc < 2) {
    fprintf(stderr, "missing argument\n");
    return -1;
  }

  nipaddr = argc - 1;
  for (i=0; i<nipaddr; i++) {
    int ret = inet_aton(argv[i+1], addrs+i);
    if (!ret) {
      fprintf(stderr, "bad address: %s", argv[i+1]);
      return -2;
    }
  }

  cidr_initialize();
  for (j=0; j<nipaddr; j++) {
    label = cidr_lookup((void *)&addrs[j].s_addr, 4);
    printf("result: %s = %s\n", argv[j+1], label);
  }

  return 0;
}

 

その1 APRのapr_ipsubnet_test

長いわりには見るところが少ないので、コードは末尾に掲載します。

初期化関数のcidr_initialize()では、CIDRのデータファイル群を読んで、APRの関数apr_ipsubnet_create()でcidrlist[]を用意しています。

判定関数のcidr_loopup()では、cidrlist[]のそれぞれについて、マッチするかどうかapr_ipsubnet_test()を使って判定しています。

このあたりの処理は、実はApacheのAllowやDenyディレクティブで、CIDRブロックが指定された場合のと同じです。

さてさて、このコードはかなり遅いです。
APRのAPIを使う以上、初期化処理などが必要なのは仕方ないのですが、それよりなにより判定処理がリニアなので、CIDRブロックの数が多くなればなるほど遅くなるのは火を見るより明らかです。

なのでこのコードは、最速を目指しているのではなく、比較用にApacheのAllow, Denyと同じ実装のものを用意してみた、といった位置づけと思ってください。

参考:

 

その2 IP::Country

お次は、PerlのモジュールであるIP::Countryからロジックを拝借したものです。

IP::Countryは、IPアドレス帯と国名の対応データベースを元に、とあるIPアドレスがどの国に割り当てられているかという情報を返すものなのですが、これのデータを差し換えて、今回のお題に使っちゃおうというのが魂胆です。

さて、IP::CountryにはIP::Country::Fastというものが含まれていて、これはどんな処理をするかというと、CIDRを(最大で)32bitのビットの並びとしてみて、0と1で二分木を構築しておきます。で、判定処理をするときは、この二分木を辿ってリーフから国名を取り出します。

末尾にベンチマークの結果を掲載しますが、APRのに比べると段違いで速いです。 採用するのはこのコードでいいかなーと思っていたのですが、コンペ参加者によりこの記録はあっさりと抜かれることとなります...

参考:

おわりに

今回のコードはなんのヒネリもなく、面白味という点ではちょっと物足りなかったのではないかと思います。が、今回は導入ということでご容赦いただき、次回以降にご期待いただければ!と思います。

ベンチマーク

5つのとあるIPアドレスのそれぞれについてどのグループに属するか判定する、という処理を5,000,000回実行したときの総所要時間(elapsed)と1回の判定に要した時間の平均(average)です。

ベンチマークは、同じハードウエアのx86とx86_64の環境の2つでとりました。

x86

name        elapsed[sec]  average[usec]
========================================
ip-country  3.739187      0.149567
apr        59.379924      2.375197

x86_64

name        elapsed[sec]  average[usec]
========================================
ip-country  0.664034      0.026561
apr        52.340651      2.093626

コード

APR

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>

#include <sys/time.h>

#include <assert.h>

#include <dirent.h>
#include <fcntl.h>
#include <sys/stat.h>

#include <sys/types.h>
#include <libgen.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#include <apr_general.h>

#include <apr_pools.h>
#include <apr_network_io.h>
#include <apr_strings.h>

#define DBDIR "../data"

apr_pool_t     *pool;
apr_ipsubnet_t *cidrlist[512];
char           *typelist[512];
int             ncidr = 0;

char *cidr_lookup(u_long *ipaddr, int len) {
  apr_sockaddr_t *sa;
  apr_status_t rv;
  struct in_addr in;
  char *ipstr;
  int j;

  if (len != 4)
    return NULL;

  in.s_addr = (unsigned long int)*ipaddr;
  ipstr = inet_ntoa(in);

  rv = apr_sockaddr_info_get(&sa,
                             ipstr,
                             APR_UNSPEC,
                             0,
                             APR_IPV4_ADDR_OK,
                             pool
                             );
  if (rv != APR_SUCCESS) {
    printf("%s\n", "apr_sockaddr_info_get: no APR_SUCCESS");
    return NULL;
  }

  for (j=0; j<ncidr; j++) {
    if (apr_ipsubnet_test(cidrlist[j], sa)) {
      return typelist[j];
    }
  }

  apr_pool_clear(pool);
  return NULL;
}

int initsort()
{
  int i;
  int j;
  apr_ipsubnet_t *tmpc;
  char *tmpt;

  for (i=0; i<ncidr; i++) {
    for (j=i+1;j<ncidr; j++) {
      if (cidrlist[i] < cidrlist[j]) {
        tmpc = cidrlist[i];
        cidrlist[i] = cidrlist[j];
        cidrlist[j] = tmpc;

        tmpt = typelist[i];
        typelist[i] = typelist[j];
        typelist[j] = tmpt;
      }
    }
  }

  return 0;
}

int initread(int fd, char *type)
{
  int  r;
  char buff[256];
  char *p = buff;
  char ip[64];
  char mask[3];
  apr_status_t rv;

  while((r=read(fd,p,1)) != 0){
    if(r == -1)
      return(-1);
    if(*p == '#')
      *p = 0;
    if(*p == '/')
      *p = ' ';
    if(*p == '\r')
      *p = 0;
    if(*p == '\n'){
      *p = 0;
      strcpy(mask,"32");
      if(sscanf(buff,"%s%s", ip, mask) < 1){
        /***** not ip addr ******/
        if(buff[0]){
          fprintf(stderr,"read error: %s(%s)\n",buff,ip);
        }
      }else{
        rv = apr_ipsubnet_create( &cidrlist[ncidr], ip, mask, pool );
        if(APR_STATUS_IS_EINVAL(rv)) {
          /* looked nothing like an IP address */
          printf("%s\n", "An IP address was expected");
          return -1;
        }
        else if (rv != APR_SUCCESS) {
          printf("%s [%s/%s]\n", "apr_ipsubnet_create: not APR_SUCCESS",ip,mask);
          return -1;
        }

        typelist[ncidr] = type;
        ncidr++;
      }
      p = buff;
      continue;
    }
    p++;
  }
  return(0);
}

char *alloctype(char *name)
{
  char *type;
  char *base;
  char path[PATH_MAX];
  strcpy(path, name);
  base=basename(path);
  type=malloc(strlen(base)+1);
  strcpy(type,base);
  return(type);
}

void cidr_initialize() {
  int  f;
  DIR *d;
  char path[PATH_MAX];
  struct dirent *e;
  struct stat   st;
  apr_status_t rv;

  rv = apr_initialize();
  if (rv != APR_SUCCESS) {
    assert(0);
    return;
  }
  apr_pool_create(&pool, NULL);

  if((d=opendir(DBDIR)) != 0){
    while((e=readdir(d)) != 0){
      sprintf(path,"%s/%s", DBDIR, e->d_name);

      if(stat(path, &st) != 0)
        continue;
      if(!S_ISREG(st.st_mode))
        continue;

      f = open(path, O_RDONLY);
      if(f == -1){
        fprintf(stderr,"file open error %s\n", path);
      }else{
        initread(f,alloctype(path));
        close(f);
      }
    }
  }

  initsort();
}

IP::Country

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>

#include <sys/time.h>
#include <errno.h>

#include <sys/stat.h>
#include <fcntl.h>
#include <sys/mman.h>

#include <arpa/inet.h>
#include <string.h>

#define CC_MAX	256	/* # of countries */

char *cc[CC_MAX];
u_char *ip_db;
u_char *cc_db;

int inet_ntocc(u_char *ip_db, u_long inet_n) {
  /*
    FORMATTING OF EACH NODE IN $ip_db
    bit0 - true if this is a country code, false if this
    is a jump to the next node

    country codes:
    bit1 - true if the country code is stored in bits 2-7
    of this byte, false if the country code is
    stored in bits 0-7 of the next byte
    bits 2-7 or bits 0-7 of next byte contain country code

    jumps:
    bytes 0-3 jump distance (only first byte used if
    distance < 64)
  */
  u_long mask = (1 << 31);
  const u_long bit0 = 0x80;
  const u_long bit1 = 0x40;
  int pos = 4;
  u_char byte_zero = ip_db[pos];
  /* loop through bits of IP address */
  while (mask) {
    if (inet_n & mask) {
      /* bit[$i] is set [binary one]
         - jump to next node
         (start of child[1] node) */
      if (byte_zero & bit1) {
        pos = pos + 1 + (byte_zero ^ bit1);
      } else {
        pos = pos + 3 + ((ip_db[pos] << 8 | ip_db[pos+1]) << 8
                         | ip_db[pos+2]);
      }
    } else {
      if (byte_zero & bit1) {
        pos = pos + 1;
      } else {
        pos = pos + 3;
      }
    }
    /*
      all terminal nodes of the tree start with zeroth bit
      set to zero. the first bit can then be used to indicate
      whether we're using the first or second byte to store the
      country code */
    byte_zero = ip_db[pos];
    if (byte_zero & bit0) {
      if (byte_zero & bit1) {
        /* unpopular country code - stored in second byte */
        return ip_db[pos+1];
      } else {
        /* popular country code - stored in bits 2-7
           (we already know that bit 1 is not set, so
           just need to unset bit 1) */
        return byte_zero ^ bit0;
      }
    }
    mask = (mask >> 1);
  }
  return -1;
}

u_char *getdb(char *file, int *fdp, int *lenp) {
  char path[PATH_MAX+1];
  int fd;
  struct stat st;
  int length;
  u_char *db;
  snprintf(path, PATH_MAX, "%s/%s", ".", file);
  path[PATH_MAX] = '\0';
  fd = open(path, O_RDONLY);
  if (fd < 0) {
    fprintf(stderr, "Can't open: %s err=%d\n", path, errno);
    exit(1);
  }
  if (fdp) *fdp = fd;
  if (fstat(fd, &st) < 0) {
    fprintf(stderr, "Can't stat: %s fd=%d err=%d\n", path, fd, errno);
    exit(1);
  }
  length = st.st_size;
  if (lenp) *lenp = length;
  db = (u_char*)mmap((void*)0, length, PROT_READ, MAP_SHARED, fd, 0);
  if (db == MAP_FAILED) {
    fprintf(stderr, "Can't map: %s fd=%d len=%d err=%d\n",
            path, fd, length, errno);
    exit(1);
  }
  return db;
}

char *cidr_lookup(u_long *ipaddr, int len) {
  int c;

  if (len != 4)
    return NULL;

  c = inet_ntocc(ip_db, ntohl(*ipaddr));

  if (c < 0) {
    return NULL;
  } else {
    return cc[c];
  }
}

void cidr_initialize() {
  u_char *p;
  int cc_len;

  ip_db = getdb("ip.gif", NULL, NULL);
  cc_db = getdb("cc.gif", NULL, &cc_len);

  for (p=cc_db; p<cc_db+cc_len;) {
    u_char c = *p++;
    u_char l = *p++;
    if (strncmp((char *)p, "--", l) == 0
        || strncmp((char *)p, "**", l) == 0) {
      cc[c] = NULL;
    } else {
      cc[c] = calloc(1, l+1);
      memcpy(cc[c], p, l);
    }
    p += l;
  }
}

klab_gijutsu2 at 08:00│Comments(1)TrackBack(0)開発 | codecompe

トラックバックURL

この記事へのコメント

1. Posted by Kenji JJ1BDX   2008年07月29日 12:15
これって基本的な経路制御問題ですよね.古い論文ですが,こんなのが参考になるかもしれません.

http://www.isoc.org/inet2001/CD_proceedings/7/smart.pdf

この記事にコメントする

名前:
URL:
  情報を記憶: 評価: 顔   
 
 
 
Blog内検索
Archives
このブログについて
DSASとは、KLab が構築し運用しているコンテンツサービス用のLinuxベースのインフラです。現在5ヶ所のデータセンタにて構築し、運用していますが、我々はDSASをより使いやすく、より安全に、そしてより省力で運用できることを目指して、日々改良に勤しんでいます。
このブログでは、そんな DSAS で使っている技術の紹介や、実験してみた結果の報告、トラブルに巻き込まれた時の経験談など、広く深く、色々な話題を織りまぜて紹介していきたいと思います。
最新コメント