DouKaku? 2074 raynstard: Cの投稿がなかったので作ってみました。 ...(アクセスログのIPアドレスを逆引き)

Comment detail

Cの投稿がなかったので作ってみました。
夏休み万歳！

ばかでかくなってしまってごめんなさい。
半分くらいはリスト管理です。
並列化はしていませんorz
入力が1つしかないので
シリアルでも十分な性能は出ていると
思いますけど、動作テストしただけだし
大きなログを持っていないのでそのへんは適当です。
マルチスレッドにするのならどこをやるんだろう？
BTREEにして分割検索？

#名前解決ができないと3秒くらい止まってしまうのはうちの環境だけ?

gcc -std=c99 -Wall doukaku039.c -o a

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <memory.h>
#include <string.h>
#include <sys/types.h>
#include <netdb.h>
#include <arpa/inet.h>
#include <netinet/in.h>

#ifdef TEST
#define DPRINTF(fmt, ...) {  printf("#debug(%4d)@%-10s: ", __LINE__, __func__); \
                             printf(fmt, ## __VA_ARGS__); fflush(stdout); }
#else
#define DPRINTF(fmt, ...) { ; }
#endif

typedef struct tagHOSTINFO
{
    struct in_addr addr;
    char IPv4[16+1];
    char hostname[63];
    struct tagHOSTINFO *next;
} HOSTINFO;

typedef struct tagROOTNODE
{
    int                count;
    struct tagHOSTINFO *begin;
    struct tagHOSTINFO *end;
} ROOTNODE;

int compare_IPv4(const HOSTINFO  a, const HOSTINFO  b )
{

    if( a.addr.s_addr < b.addr.s_addr ) return -1;
    if( a.addr.s_addr > b.addr.s_addr ) return  1;
    return 0;
}

int clear_list(const ROOTNODE root)
{
    int n=1;
    HOSTINFO *cursor;
    HOSTINFO *store;
    for( cursor=root.begin; n<=root.count; n ++)
    {
#ifdef TEST
        printf("%2d:[%s] %s\n", n, cursor->IPv4, cursor->hostname);
#endif
        store = cursor;
        cursor = cursor->next;
        free(store);
    }
    free(store);
    return 0;
}

int  addList(ROOTNODE *root, HOSTINFO *before, const HOSTINFO info)
{
    HOSTINFO *item = NULL;
    int      result;

    /* 追加用のキッシュアイテム 作成 */
    DPRINTF("登録(%d):[%s]\n", root->count+1,info.IPv4);
    item = (HOSTINFO *)calloc( 1, sizeof(HOSTINFO) );
    if( item == NULL )
    {
        return -1;
    }
    memcpy(item, &info, sizeof(HOSTINFO));
    item->next = item;

    /* IPアドレスの変換 */
    result = inet_aton( item->IPv4, &item->addr );
    if( result == 0 )
    {
        DPRINTF("IPアドレスの書式不正:[%s]\n", info.IPv4);
        free(item);
        return -1;
    }

#ifdef TEST
    strncpy(item->hostname, "HOSTNAME", sizeof(item->hostname));
#else
    /* ホスト名取得 */
    struct hostent *ent;
    ent = gethostbyaddr((const char *)&item->addr.s_addr, sizeof(item->addr.s_addr), AF_INET);
    if( ent != NULL )
    {
        strncpy(item->hostname, ent->h_name, sizeof(item->hostname));
    }
#endif
    root->count ++; /* キッシュした数*/
    if( root->count == 1 )
    {
        root->begin  = item;
        root->end    = item;
        return 0;
    }


    /* 挿入 before item cursor */
    if( before == NULL )
    {
        /* 先頭へ挿入 */
        item->next = root->begin;
        root->begin     = item;
    }
    else
    {
        if( root->end == before )
        {
            /* 最後尾へ追加 */
            before->next = item;
            root->end = item;
        }
        else
        {
            /* 中間へ挿入 */
            item->next = before->next;
            before->next = item;
        }
    }
    return 0;
}

int find(ROOTNODE *root, HOSTINFO *in)
{
    static HOSTINFO *cache = NULL;

    HOSTINFO *cursor = cache;
    HOSTINFO *before = root->begin;
    HOSTINFO *term   = root->end;
    int      compare_status = 0;

    int      result ;
    int      n ;

    memset(in->hostname, '\0', sizeof(in->hostname));
    result = inet_aton( in->IPv4, &in->addr );
    if( result == 0 )
    {
        DPRINTF("IPアドレスの書式不正:[%s]\n", in->IPv4);
        return 1;
    }

    /* 検索範囲設定 */
    if( root->begin == NULL )
    {
        /* 初めてなので強制的に追加 */
        result = addList(root, NULL, *in);
        if( result == 0 )
        {
            cache = root->begin;
            return find(root, in);
        }
        return 1;
    }
    if( cursor != NULL )
    {
        compare_status = compare_IPv4(*cursor, *in);
        //DPRINTF("a:[%s] / b:[%s] result=[%d]\n",cache->IPv4, in->IPv4, compare_status );
        if( compare_status == 0 )
        {
            /* 前回と同じIPアドレス */
            if( *cursor->hostname == '\0' )
            {
                /* 不明なホスト */
                return 1;
            }
            strncpy(in->hostname, cursor->hostname, sizeof(in->hostname));
            return 0; /* 検索の必要なし */
        }
        else if( compare_status < 0 )
        {
            /* 前回ヒットした位置から終点まで */
            cursor = cursor;
            term   = root->end;
            DPRINTF("前回からの続きで検索:[%s] ～ [%s]\n", cursor->IPv4, term->IPv4);
        }
        else
        {
            /* 先頭から前回ヒットした位置まで */
            cursor = root->begin;
            term   = cursor;
            DPRINTF("先頭から検索:[%s] ～ [%s]\n", cursor->IPv4, term->IPv4);
        }
    }
    else
    {
        cursor = root->begin;
    }

    /* キャッシュ内検索開始 */

    /* 最初に最後尾と比較 */
    compare_status = compare_IPv4(*term, *in);
    if( compare_status == 0 )
    {
        if( *term->hostname == '\0' )
        {
            /* 不明なホスト */
            return 1;
        }
        strncpy(in->hostname, term->hostname, sizeof(in->hostname));
        return 0; /* 検索の必要なし */
    }
    if( compare_status < 0 )
    {
        /* 最後尾よりも大きいので検索する必要なし */
        result = addList(root, term, *in);
        if( result == 0 )
        {
            cache = term;
            return find(root, in);
        }
        return 1;
    }

    /* おおざっぱに検索 */
    before = cursor;
    while( cursor != term )
    {
        compare_status = compare_IPv4(*cursor, *in);
        if( compare_status == 0 )
        {
            /* キャッシュヒット */
            if( *cursor->hostname == '\0' )
            {
                /* 不明なホスト */
                return 1;
            }
            strncpy(in->hostname, cursor->hostname, sizeof(in->hostname));
            cache = cursor;
            return 0;
        }
        if( compare_status > 0 )
        {
            /* SKIPした範囲内のIPアドレス */
            break;
        }
        before = cursor;
        for(n=root->count/10; n>=0 ; n-- )
        {
            cursor = cursor->next;
            if( cursor->next == term ) break;
        }
    } 

    /* SKIPした部分を一つずつ検索 */
    for( cursor = before; before != term ; cursor = cursor->next )
    {
        compare_status = compare_IPv4(*cursor, *in);
        if( compare_status == 0 )
        {
            /* キャッシュヒット */
            if( *cursor->hostname == '\0' )
            {
                /* 不明なホスト */
                return 1;
            }
            strncpy(in->hostname, cursor->hostname, sizeof(in->hostname));
            cache = cursor;
            return 0;
        }
        if( compare_status > 0 )
        {
            /* 初めてのIPアドレス */
            break;
        }
        before = cursor;
    }

    /* 初めてのIPアドレスをキャッシュに登録 */
    if( cursor == before )
    {
        /* 一番小さいので先頭に挿入 */
        before = NULL;
    }
    result = addList(root, before, *in);
    if( result == 0 )
    {
        cache = before;
        return find(root, in);
    }
    return result;
}

int
 convertLog(const char *log_filename)
{
    ROOTNODE root;
    HOSTINFO ip;

    FILE   *fp;
    char   line[2048];
    char   *data;
    size_t length;
    int    result ;
    long   line_count = 0;

    root.begin = NULL;
    root.end   = NULL;

    fp = fopen(log_filename, "rb");
    if( fp == NULL )
    {
        return -1;
    }
    while( fgets(line, sizeof(line), fp) != NULL )
    {
        line_count ++;
        data = strchr(line, ' ');
        if( data == NULL )
        {
            /* 空白無しはおかしい */
            fprintf(stderr, "FILENAME:[%s] LINE:[%ld]\n", log_filename, line_count);
            fclose(fp);
            return -1;
        }
        length = data - line;
        length = (sizeof(ip.IPv4)-1 < length )?sizeof(ip.IPv4)-1:length;
        memset(&ip, 0, sizeof(ip));
        strncpy(ip.IPv4, line, length);
        result = find(&root, &ip);
        if( result == 0 )
        {
            printf("%s%s", ip.hostname, data);
        }
        else
        {
            printf("%s", line);
        }
    }
    fclose(fp);
    clear_list(root);
    return 0;
}

int
 main(int argc, char *argv[])
{

#ifdef TEST
    static ROOTNODE root;
    int result ;
    HOSTINFO ip;

    root.begin = NULL;
    root.end   = NULL;
    int a,b,c,d;
    srand( time(NULL) );
    for( size_t wkA=0; wkA<20; wkA++)
    {
        a = ( rand() * 100 ) & 0xff;
        b = ( rand() * 100 ) & 0xff;
        c = ( rand() * 100 ) & 0xff;
        d = ( rand() * 100 ) & 0xff;
        sprintf(ip.IPv4, "%d.%d.%d.%d", a,b,c,d);
        result = find(&root, &ip);
        printf("result=[%d] / ip=[ %16s ] hostname=[%s]\n", result, ip.IPv4, ip.hostname);
    }
    clear_list(root);
#else
    convertLog(argv[1]);
#endif

    return 0;
}

しまったよく考えたらアクセスログなのだから
昇順固定でなく個数制限付きのラウンドロビンにすれば良かったorz

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq