C언어 해시테이블 구현

해시테이블은 자료가 방대할 때 사용하기 좋다.

 

1. 아이피주소를 해싱한다
2. 해싱한 아이피주소를 해시테이블 크기로 나눈 나머지 값을 구한다
3. 이 때 구한 나머지 값이 바로 이 아이피주소의 키값이다.
4. 해시테이블의 해당 키 위치에 아이피주소 노드를 연결한다.
5. 이를 반복하다보면 아이피주소는 매우 많기 때문에 중복되는 키가 생기는데, 이걸 충돌이라 부른다
6. 충돌이 일어나면, 그 키에 새로운 노드를 만들어 연결하여 아이피주소를 저장한다.
7. 즉 배열에 노드를 저장하는데, 그 노드들은 이중연결리스트의 노드라서 같은 키를 가진 다른 아이피를 저장할 수 있게 된다.

 

0. 해시테이블 구조

사용자가 입력한 크기만큼의 일차원배열을 만든다.

배열에 저장되는 값은 HashTableHead로, 해당 키에 저장된 아이피주소의 개수와 다음노드를 저장할 수 있는 멤버변수를 갖는다.

아이피주소는 해시+나머지 연산 이후 나오는 값의 인덱스를 키로 갖는다.

HashTableNode를 만들어 일차원배열에서 해당 인덱스(==키)에 저장한다.

 

1. 헤더파일

링크드리스트에 사용될 구조체도 함께 선언되어있다.

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <stdint.h>
#include <pthread.h>
#include <time.h>

#define FLOOD_IP_ADDR_LEN 16

typedef struct {
  int32_t tablesize;
  int32_t timelimit;
  int32_t count;
} FloodConfig;


typedef struct _HashTableNode {
  unsigned int srcip;
  int count;
  time_t detecttime;

  struct _HashTableNode *prev;
  struct _HashTableNode *next;
} HashTableNode;

typedef struct {
  int nodecnt;
  HashTableNode *next;
} HashTableHead;

typedef struct {
  HashTableHead *node;
  int tablesize;
  int timelimit;
  int count;
  pthread_mutex_t mutex;
} HashTable;

void initHashTable(HashTable *hashtable, FloodConfig *flood_config);
int isEmptyHashTable(HashTable *hashtable, int key);
HashTableNode* makeTableNode(unsigned int srcip);
HashTableNode* findTargetLocation(HashTable *hashtable, int key, unsigned srcip);
int insertNode(HashTable *hashtable, int key, unsigned int srcip, int isEmpty);
int hashSourceTp(HashTable *hashtable, unsigned int srcip);
int hasSrcIp(unsigned int srcip);
int checkTable(HashTable *hashtable, unsigned int srcip);
#endif

 

2. 소스파일

1) checkTable()

 

이 함수가 hashtable.c 의 메인함수 격이다. detect thread에서는 icmp 프로토콜이 들어왔을 때 이 함수를 호출한다.

int checkTable(HashTable *hashtable, unsigned int srcip) {
  pthread_mutex_lock(&(hashtable->mutex));
  
  uint32_t key = hashSrcIp(srcip) % (hashtable->tablesize);

  int isEmpty = isEmptyHashTable(hashtable, key);

  int insertResult = 0;
  insertResult = insertNode(hashtable, key, srcip, isEmpty);  
 
  pthread_mutex_unlock(&(hashtable->mutex));
  return insertResult;
}

 

2) hashSrcIp(), isEmptyHashTable()

아이피 해싱하여 키를 얻는다.

그리고 그 키를 이용하여 해시테이블의 해당 위치가 비어있는지 판별한다.

uint32_t hashSrcIp (unsigned int srcip) {
  return hash_func4((const char *)&srcip, sizeof(srcip));
}

int isEmptyHashTable(HashTable *hashtable, int key) { 
  return (hashtable->node[key].nodecnt) ? NOT_EMPTY : EMPTY;
}

 

3) insertNode()

해당 키가 비어있다면 이제 들어가는 아이피 노드가 첫 번째 노드이고, 아니라면 다른 노드 뒤에 연결해주면 된다.

int insertNode(HashTable *hashtable, int key, unsigned int srcip, int isEmpty){
  
  if (isEmpty){
    hashtable->node[key].nodecnt = 1; //첫 번째
    hashtable->node[key].next = makeTableNode(srcip);
    hashtable->node[key].next->prev = NULL; //앞 노드는 HEAD이기 때문에 양방향 연결 x 
    return SUCCESS; 
  }


  struct timespec detect_ts, current_ts;
  clock_gettime(CLOCK_REALTIME, &current_ts);

  HashTableNode *target_node = findTargetLocation(hashtable, key, srcip);
  if (!target_node) return FAIL;

  if (target_node->srcip != srcip) { //이 아이피는 리스트에 존재하지 않는다 == 끝에 넣어준다
    hashtable->node[key].nodecnt += 1;
    target_node->next = makeTableNode(srcip);
    target_node->next->prev = target_node; //앞 뒤 연결해줌
    return SUCCESS;
  }
  
  //이 아이피는 리스트에 존재한다
  detect_ts.tv_sec = target_node->detecttime;
  detect_ts.tv_nsec = 0;
  long sec_diff = current_ts.tv_sec - detect_ts.tv_sec;

  if (sec_diff > hashtable->timelimit) { //시간을 체크해봤는데 제한시간이 지났다
    time_t detect_time;
    time(&detect_time);

    target_node->count = 0;
    target_node->detecttime = detect_time;
    return SUCCESS;
  }

  if (sec_diff <= hashtable->timelimit) { //시간을 체크해봤는데 제한시간이 안 지났다
    target_node->count += 1;

    if (target_node->count >= hashtable->count) { //제한 개수가 넘었다면
      hashtable->node[key].nodecnt -= 1;
    
      //내 앞이 헤드이면
      if (target_node->prev == NULL) {
        hashtable->node[key].next = target_node->next;
        if (target_node->next != NULL) 
          target_node->next->prev = NULL;
        free(target_node);
        return FLOOD;
      }
      
      //내 앞에 노드가 있다면
      target_node->prev->next = target_node->next;
      if(target_node->next != NULL) 
        target_node->next->prev = target_node->prev;     
      free(target_node);
      return FLOOD;
    }
    return SUCCESS;
  }
  return FAIL; 
}

 

4) insertNode()에 필요한 함수들

makeTableNode()는 새로운 노드를 만들어 반환하는 함수이다.

findTargetLocation()은 새로운 노드를 넣어야 할 자리의 포인터를 반환하는 함수이다.

HashTableNode* makeTableNode(unsigned int srcip) {
  
  time_t detect_time;
  time(&detect_time);

  HashTableNode *node = (HashTableNode *)malloc(sizeof(HashTableNode));
  if (node == NULL) {
    printf("해시테이블 저장에 문제가 생겼습니다. 프로그램을 종료합니다.\n");
    exit(0);
  }

  node->srcip = srcip;
  node->count = 1;
  node->detecttime = detect_time;
  node->next = NULL;

  return node;
}

HashTableNode* findTargetLocation(HashTable *hashtable, int key, unsigned srcip){
  HashTableNode *node = hashtable->node[key].next;

  while(node != NULL) {
    if (node->srcip == srcip) return node; //그 아이피를 가진 노드를 반환해준다
    if (node->next == NULL) return node; //다음 위치가 null이면 (끝까지 찾은거니까) 이 아이피는 없는 아이피이므로 반환한다.
  }

  node = NULL;
  return node;
}

 

원본 소스 🔽

https://github.com/Hayeon-Lee/IDS/blob/main/hashtable.c

IDS/hashtable.c at main · Hayeon-Lee/IDS

https://github.com/Hayeon-Lee/IDS/blob/main/hashtable.h

IDS/hashtable.h at main · Hayeon-Lee/IDS