社内コードコンペ - お題:最速な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; } }
トラックバックURL
この記事へのコメント
http://www.isoc.org/inet2001/CD_proceedings/7/smart.pdf