pxys2-2.0.0/ipcache/ipcache.c

/* Copyright (C) 2003 Stephane Thiell
 *
 * This file is part of pxyservd (from pxys)
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 */
#define RCSID "$Id"

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "ipcache.h"

#include <peak/peak.h>

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#ifdef IPCACHE_TEST
#include <arpa/inet.h>
#endif

struct __ipcache_in4_entry
  {
  struct __ipcache_in4_entry *next;
  struct in_addr key;
  int lru_ring_refcnt;
  time_t ts;
  char data[0]; /* append optional data here */
  };

typedef struct __ipcache_in4_entry hentry4;

struct __ipcache_in6_entry
  {
  struct __ipcache_in6_entry *next;
  struct in6_addr key;
  int lru_ring_refcnt;
  time_t ts;
  char data[0]; /* append optional data here */
  };

typedef struct __ipcache_in6_entry hentry6;

typedef struct __ipcache_lru_ring *ipcache_lru_ring_t;

struct __ipcache
  {
  int buckets;
  int count;
  int maxcount;
  size_t datasize;
  int flags;
  peak_mem_pool mem_pool;
  union
    {
    struct __ipcache_in4_entry **v4;
    struct __ipcache_in6_entry **v6;
    } table;
  ipcache_lru_ring_t lru_ring;
  };

typedef void (*ipcache_lru_ring_release_func)(ipcache_t cp, void *obj);

struct __ipcache_lru_ring
  {
  int size;
  int count;
  int pos_start;
  int pos_end;
  ipcache_t cache;
  void **address;
  ipcache_lru_ring_release_func rel_fun;
  };

static uint32_t hashfun_in4(const struct in_addr *addrptr);
static uint32_t hashfun_in6(const struct in6_addr *addrptr);

static int ipcache_hash_remove_in4(ipcache_t cp, struct in_addr *addr);
static int ipcache_hash_remove_in6(ipcache_t cp, struct in6_addr *addr);
static void ipcache_release_in4(ipcache_t cp, hentry4 *e);
static int ipcache_dispose_in4(ipcache_t cp, hentry4 *e);
static void ipcache_release_in6(ipcache_t cp, hentry6 *e);
static int ipcache_dispose_in6(ipcache_t cp, hentry6 *e);

static ipcache_lru_ring_t ipcache_lru_ring_create(ipcache_t cp, size_t size,
                                 ipcache_lru_ring_release_func rel_fun);
static void ipcache_lru_ring_dispose(ipcache_lru_ring_t ring);
static void ipcache_lru_ring_add(ipcache_lru_ring_t ring, void *obj);
static int ipcache_lru_ring_clear(ipcache_lru_ring_t ring);

#ifdef IPCACHE_TEST
static int coll;
static int llen;
#endif

static uint32_t
hashfun_in4(const struct in_addr *addrptr)
  {
  return (uint32_t)addrptr->s_addr;
  }

static uint32_t
hashfun_in6(const struct in6_addr *addrptr)
  {
  const u_char *key = (u_char *)addrptr;
  uint32_t h = 0;
  
#define HASH4 \
  h = h * 33 + *key++; \
  h = h * 33 + *key++; \
  h = h * 33 + *key++; \
  h = h * 33 + *key++
  
  HASH4;
  HASH4;
  HASH4;
  HASH4;
  
  return (h);
  }

ipcache_t
ipcache_create_in4(int size, size_t datasize)
  {
  int pos;
  ipcache_t cp = (ipcache_t)peak_allocate(sizeof(struct __ipcache));
  cp->buckets = size;
  cp->count = 0;
  cp->maxcount = size;
  cp->datasize = datasize;
  cp->flags = 0;
  cp->mem_pool = peak_mem_pool_create(sizeof(hentry4) + cp->datasize, 0);
  cp->table.v4 = (hentry4 **)peak_allocate(sizeof(hentry4 *) * cp->buckets);
  
  for (pos = cp->buckets; pos--; )
    cp->table.v4[pos] = NULL;
  
  cp->lru_ring = ipcache_lru_ring_create(cp, size,
                         (ipcache_lru_ring_release_func)ipcache_release_in4);
  
  return cp;
  }

ipcache_t
ipcache_create_in6(int size, size_t datasize)
  {
  int pos;
  ipcache_t cp = (ipcache_t)peak_allocate(sizeof(struct __ipcache));
  cp->buckets = size;
  cp->count = 0;
  cp->maxcount = size;
  cp->datasize = datasize;
  cp->flags = 1;
  cp->mem_pool = peak_mem_pool_create(sizeof(hentry6) + cp->datasize, 0);
  cp->table.v6 = (hentry6 **)peak_allocate(sizeof(hentry6 *) * cp->buckets);
  
  for (pos = cp->buckets; pos--; )
    cp->table.v6[pos] = NULL;
  
  cp->lru_ring = ipcache_lru_ring_create(cp, size,
                         (ipcache_lru_ring_release_func)ipcache_release_in6);
  
  return cp;
  }

void
ipcache_dispose(ipcache_t cp)
  {
  ipcache_lru_ring_dispose(cp->lru_ring);
  peak_release(cp->mem_pool);
  peak_deallocate((void *)cp->table.v4);
  peak_deallocate(cp);
  }

int
ipcache_clear(ipcache_t cp)
  {
  int result = ipcache_lru_ring_clear(cp->lru_ring);
  assert (cp->count == 0);
  return result;
  }

void
ipcache_add_in4(ipcache_t cp, const struct in_addr *addr, time_t t,
                const void *data)
  {
  hentry4 *e;
  uint32_t slot = hashfun_in4(addr) % cp->buckets;
  
  for (e = cp->table.v4[slot]; e; e = e->next)
    {
    if (e->key.s_addr == addr->s_addr)
      {
      e->lru_ring_refcnt++;
      e->ts = t;
      ipcache_lru_ring_add(cp->lru_ring, e);
      return;
      }
    }
  
  e = (hentry4 *)peak_mem_pool_new(cp->mem_pool);
  e->key = *addr;
  e->lru_ring_refcnt = 0;
  e->ts = t;
  if (cp->datasize > 0)
    memcpy(e->data, data, cp->datasize);
  
  e->next = cp->table.v4[slot];

#ifdef IPCACHE_TEST
  if (e->next != NULL)
    {
    int cnt;
    hentry4 *ti = e;
    coll++;
    for (cnt = 0; ti->next != NULL; ti = ti->next)
      cnt++;
    if (cnt > llen)
      llen = cnt;
    }
#endif
  cp->table.v4[slot] = e;
  cp->count++;
  
  e->lru_ring_refcnt++;
  ipcache_lru_ring_add(cp->lru_ring, e);
  }

void
ipcache_add_in6(ipcache_t cp, const struct in6_addr *addr, time_t t,
                const void *data)
  {
  hentry6 *e;
  uint32_t slot = hashfun_in6(addr) % cp->buckets;
  
  for (e = cp->table.v6[slot]; e; e = e->next)
    {
    if (memcmp(&e->key, addr, sizeof(struct in6_addr)) == 0)
      {
      e->lru_ring_refcnt++;
      e->ts = t;
      ipcache_lru_ring_add(cp->lru_ring, e);
      return;
      }
    }
  
  e = (hentry6 *)peak_mem_pool_new(cp->mem_pool);
  e->key = *addr;
  e->lru_ring_refcnt = 0;
  e->ts = t;
  
  if (cp->datasize > 0)
    memcpy(e->data, data, cp->datasize);
  e->next = cp->table.v6[slot];
  cp->table.v6[slot] = e;
  cp->count++;
    
  e->lru_ring_refcnt++;
  ipcache_lru_ring_add(cp->lru_ring, e);
  }

int
ipcache_invalidate_in4(ipcache_t cp, const struct in_addr *addr)
  {
  hentry4 *e;
  uint32_t slot = hashfun_in4(addr) % cp->buckets;
  
  for (e = cp->table.v4[slot]; e; e = e->next)
    {
    if (e->key.s_addr == addr->s_addr && e->ts != 0)
      {
      printf("ipcache_invalidate_in4: found!\n");
      e->ts = 0;
      return 0;
      }
    }
  printf("ipcache_invalidate_in4: not found!\n");
  return -1;
  }

int
ipcache_invalidate_in6(ipcache_t cp, const struct in6_addr *addr)
  {
  hentry6 *e;
  uint32_t slot = hashfun_in6(addr) % cp->buckets;
    
  for (e = cp->table.v6[slot]; e; e = e->next)
    {
    if (memcmp(&e->key, addr, sizeof(struct in6_addr)) == 0
        && e->ts != 0)
      {
      e->ts = 0;
      return 0;
      }
    }
  return -1;
  }

static int
ipcache_hash_remove_in4(ipcache_t cp, struct in_addr *addr)
  {
  hentry4 **e, *kill;
  uint32_t slot = hashfun_in4(addr) % cp->buckets;
  
  for (e = &cp->table.v4[slot]; *e; e = &((*e)->next))
    {
    if ((*e)->key.s_addr == addr->s_addr)
      {
      cp->count--;
      kill = *e;
      *e = (*e)->next;
      peak_mem_pool_delete(cp->mem_pool, kill);
      return 0;
      }
    }
  return -1;
  }

static int
ipcache_hash_remove_in6(ipcache_t cp, struct in6_addr *addr)
  {
  hentry6 **e, *kill;
  uint32_t slot = hashfun_in6(addr) % cp->buckets;
  
  for (e = &cp->table.v6[slot]; *e; e = &((*e)->next))
    {
    if (memcmp(&(*e)->key, addr, sizeof(struct in6_addr)) == 0)
      {
      cp->count--;
      kill = *e;
      *e = (*e)->next;
      peak_mem_pool_delete(cp->mem_pool, kill);
      return 0;
      }
    }
  return -1;
  }


static void
ipcache_release_in4(ipcache_t cp, hentry4 *e)
  {
  int err;
  
  assert(e->lru_ring_refcnt > 0);
  
  if (!--e->lru_ring_refcnt)
    {
    err = ipcache_dispose_in4(cp, e);
    assert (err == 0);
    }
  }

static int
ipcache_dispose_in4(ipcache_t cp, hentry4 *e)
  {
  return ipcache_hash_remove_in4(cp, &e->key);
  }

static void
ipcache_release_in6(ipcache_t cp, hentry6 *e)
  {
  int err;
  
  assert(e->lru_ring_refcnt > 0);
  
  if (!--e->lru_ring_refcnt)
    {
    err = ipcache_dispose_in6(cp, e);
    assert (err == 0);
    }
  }

static int
ipcache_dispose_in6(ipcache_t cp, hentry6 *e)
  {
  return ipcache_hash_remove_in6(cp, &e->key);
  }

time_t
ipcache_find_in4(ipcache_t cp, const struct in_addr *addr, void **od)
  {
  hentry4 *e;
  uint32_t slot = hashfun_in4(addr) % cp->buckets;
  
  for (e = cp->table.v4[slot]; e; e = e->next)
    if (e->key.s_addr == addr->s_addr)
      {
      if (od && cp->datasize)
        *od = e->data;
      return e->ts;
      }
  
  return 0;
  }

time_t
ipcache_find_in6(ipcache_t cp, const struct in6_addr *addr, void **od)
  {
  hentry6 *e;
  uint32_t slot = hashfun_in6(addr) % cp->buckets;
  
  for (e = cp->table.v6[slot]; e; e = e->next)
    if (memcmp(&e->key, addr, sizeof(struct in6_addr)) == 0)
      {
      if (od && cp->datasize)
        *od = e->data;
      return e->ts;
      }
  
  return 0;
  }

size_t
ipcache_get_count(ipcache_t cp)
  {
  return cp->lru_ring->count;
  }

/**************** Associated internal LRU Ring *****************/

static ipcache_lru_ring_t
ipcache_lru_ring_create(ipcache_t cp, size_t size,
                        ipcache_lru_ring_release_func rel_fun)
  {
  ipcache_lru_ring_t ring =
    (ipcache_lru_ring_t)peak_allocate(sizeof(struct __ipcache_lru_ring));
  ring->size = size;
  ring->count = 0;
  ring->address = (void **)peak_allocate(sizeof(void *) * ring->size);
  ring->pos_start = 0;
  ring->pos_end = -1;
  ring->cache = cp;
  ring->rel_fun = rel_fun;
  return ring;
  }

static void
ipcache_lru_ring_dispose(ipcache_lru_ring_t ring)
  {
  peak_deallocate(ring->address);
  peak_deallocate(ring);
  }

static void
ipcache_lru_ring_add(ipcache_lru_ring_t ring, void *obj)
  {
  if (++ring->pos_end >= ring->size)
    ring->pos_end = 0;
  
  if (ring->count >= ring->size)
    {
    assert (ring->pos_end == ring->pos_start);
    assert (ring->count == ring->size);
    
    (*ring->rel_fun)(ring->cache, ring->address[ring->pos_end]);
    
    if (++ring->pos_start >= ring->size)
      ring->pos_start = 0;
    }
  else
    ring->count++;
  
  ring->address[ring->pos_end] = obj;
  }

static int
ipcache_lru_ring_clear(ipcache_lru_ring_t ring)
  {
  int result = ring->count;
  
  while (ring->count > 0)
    {
    (*ring->rel_fun)(ring->cache, ring->address[ring->pos_start]);
    if (++ring->pos_start >= ring->size)
      ring->pos_start = 0;
    ring->count--;
    }
  assert(ring->pos_start == ring->pos_end);
  
  return result;
  }

/************************ Special cleanup ************************/

size_t
ipcache_cleanup(ipcache_t cp, time_t expire_ts)
  {
  ipcache_lru_ring_t ring = cp->lru_ring;
  size_t count = 0;
  
  if (cp->flags & 1) /* ipv6 */
    {
    hentry6 *e6;
    
    for (e6 = (hentry6 *)ring->address[ring->pos_start];
         ring->count > 0 && e6->ts <= expire_ts;
         e6 = (hentry6 *)ring->address[ring->pos_start])
      {
      (*ring->rel_fun)(ring->cache, ring->address[ring->pos_start]);
      if (++ring->pos_start >= ring->size)
        ring->pos_start = 0;
      ring->count--;
      count++;
      }
    }
  else
    {
    hentry4 *e4;
    
    for (e4 = (hentry4 *)ring->address[ring->pos_start];
         ring->count > 0 && e4->ts <= expire_ts;
         e4 = (hentry4 *)ring->address[ring->pos_start])
      {
      (*ring->rel_fun)(ring->cache, ring->address[ring->pos_start]);
      if (++ring->pos_start >= ring->size)
        ring->pos_start = 0;
      ring->count--;
      count++;
      }
    }
  return count;
  }


/************************ Cache storage ************************/

typedef struct __ipcache_file_header
  {
  uint32_t sig;             // file signature
  int32_t last_update;      // file last update time
  uint32_t sizeof_entry;    // size of an entry in bytes
  uint32_t count;           // number of entries
  } ipcache_file_header;

typedef struct __ipcache_file_entry4
  {
  struct in_addr addr;
  time_t ts;
  char data[0];
  } ipcache_file_entry4;

typedef struct __ipcache_file_entry6
  {
  struct in6_addr addr;
  time_t ts;
  char data[0];
  } ipcache_file_entry6;


#define SWAP_NMEMB 16

int
ipcache_swapin(ipcache_t cp, const char *file, uint32_t sig)
  {
  int res = -1;
  FILE *fp;
  ipcache_file_header head;
  ipcache_file_entry4 *e4p, *e4p2;
  ipcache_file_entry6 *e6p, *e6p2;
  size_t size, i, n;
  uint32_t cnt = 0;
  
  if ((fp = fopen(file, "r"))  == NULL)
    return res;
  
  if (fread(&head, sizeof(head), 1, fp) < 1 || (head.sig != sig))
    goto swapin_failure;
  
  if (cp->flags & 1)
    {
    size = sizeof(ipcache_file_entry6) + cp->datasize;
    if (head.sizeof_entry != size)
      goto swapin_failure;
    
    e6p = (ipcache_file_entry6 *)peak_allocate(size * SWAP_NMEMB);
    
    while ((n = fread(e6p, size, SWAP_NMEMB, fp)) > 0)
      for (i = 0, e6p2 = e6p; i < n; i++, cnt++, ((char*)e6p2) += size)
        ipcache_add_in6(cp, &e6p2->addr, e6p2->ts, e6p2->data);
    
    peak_deallocate(e6p);
    }
  else
    {
    size = sizeof(ipcache_file_entry4) + cp->datasize;
    if (head.sizeof_entry != size)
      goto swapin_failure;
    
    e4p = (ipcache_file_entry4 *)peak_allocate(size * SWAP_NMEMB);
    
    while ((n = fread(e4p, size, SWAP_NMEMB, fp)) > 0)
      for (i = 0, e4p2 = e4p; i < n; i++, cnt++, ((char *)e4p2) += size)
        ipcache_add_in4(cp, &e4p2->addr, e4p2->ts, e4p2->data);
    
    peak_deallocate(e4p);
    }
  
  if (head.count == cnt)
    res = 0; /* success */
  
swapin_failure:
  fclose(fp);
  return res;
  }

int
ipcache_swapout(ipcache_t cp, const char *file, uint32_t sig)
  {
  int res = -1;
  FILE *fp;
  ipcache_file_header head;
  ipcache_lru_ring_t ring = cp->lru_ring;
  size_t size;
  int i, pos;
  
  if ((fp = fopen(file, "w"))  == NULL)
    return res;
  
  size = (cp->flags & 1) ? sizeof(ipcache_file_entry6)
                         : sizeof(ipcache_file_entry4);
  size += cp->datasize;
  
  head.sig = sig;
  head.last_update = peak_time();
  head.sizeof_entry = size;
  head.count = ring->count;
  
  if (fwrite(&head, sizeof(head), 1, fp) < 1)
    goto swapout_failure;
  
  if (cp->flags & 1) /* ipv6 */
    {
    ipcache_file_entry6 *fe6p = 
      (ipcache_file_entry6 *)peak_allocate(size);
    hentry6 *he6p;
    
    for (i = ring->count, pos = ring->pos_start; i > 0; i--)
      {
      he6p = (hentry6 *)ring->address[pos];
      fe6p->addr = he6p->key;
      fe6p->ts = he6p->ts;
      if (cp->datasize > 0)
        memcpy(fe6p->data, he6p->data, cp->datasize);
      if (fwrite(fe6p, size, 1, fp) < 1)
        goto swapout_failure;
      
      if (++pos >= ring->size)
        pos = 0;
      }
    peak_deallocate(fe6p);
    }
  else
    {
    ipcache_file_entry4 *fe4p =
      (ipcache_file_entry4 *)peak_allocate(size);
    hentry4 *he4p;
    
    for (i = ring->count, pos = ring->pos_start; i > 0; i--)
      {
      he4p = (hentry4 *)ring->address[pos];
      fe4p->addr = he4p->key;
      fe4p->ts = he4p->ts;
      if (cp->datasize > 0)
        memcpy(fe4p->data, he4p->data, cp->datasize);
      if (fwrite(fe4p, size, 1, fp) < 1)
        goto swapout_failure;
      
      if (++pos >= ring->size)
        pos = 0;
      }
    peak_deallocate(fe4p);
    }
  res = 0;
swapout_failure:
  fclose(fp);
  return res;
  }


/* Test */

#ifdef IPCACHE_TEST
int
main(int argc, char *argv[])
  {
  ipcache_t cache = ipcache_create_in4(CACHESIZE, 0);
  struct in_addr addr;
  int i, j, res;
  int found = 0, loaded = 0;
  FILE *fp;
  char buf[32];
  struct in_addr *randips = malloc(sizeof(struct in_addr) * LOOPS);
  
  fp = fopen("urandip.txt", "r");
  assert(fp);

  i = 0;
  while(fgets(buf, sizeof(buf), fp))
    {
    buf[strlen(buf)-1] = '\0';
    randips[i++].s_addr = inet_addr(buf);
    loaded++;
    }
  
  for (j = 0; i < LOOPS; i++, j++)
    {
    randips[i] = randips[j];
    randips[i].s_addr += 2;
    }
  fclose(fp);
  
  for (i = 0; i < LOOPS; i++)
    {
    addr = randips[i];
    if (ipcache_find_in4(cache, &addr, NULL) != 0)
      found++;
    
    ipcache_add_in4(cache, &addr, peak_time(), NULL);
    }
  
#if CACHESIZE >= LOOPS
  for (i = 0; i < LOOPS; i++)
    {
    addr = randips[i];
    assert (ipcache_find_in4(cache, &addr, NULL) != 0);
    }
#endif
  printf("coll=%d loaded=%d %f%% found=%d llen=%d\n", coll, loaded,
         100.0 - (100.0 * (double)coll/(double)(LOOPS-found)), found, llen);
  
  printf("swapout...\n");
  res = ipcache_swapout(cache, "test.cache", 42);
  assert(res == 0);
  ipcache_dispose(cache);
  cache = ipcache_create_in4(CACHESIZE, 0);
  printf("swapin...\n");
  res = ipcache_swapin(cache, "test.cache", 42);
  assert(res == 0);
#if CACHESIZE >= LOOPS
  printf("recovery test...");
  for (i = 0; i < LOOPS; i++)
    {
    addr = randips[i];
    assert (ipcache_find_in4(cache, &addr, NULL) != 0);
    }
#endif
  printf("ok\n");
  return 0;
  }
#endif /* IPCACHE_TEST */
Revision:	3252
Committed:	Wed Apr 2 20:41:43 2014 UTC (10 years ago) by michael
Content type:	text/x-csrc
File size:	17609 byte(s)
Log Message:	- Imported pxys2-2.0.0
#	User	Rev	Content
1	michael	3252	/* Copyright (C) 2003 Stephane Thiell
2			*
3			* This file is part of pxyservd (from pxys)
4			*
5			* This program is free software; you can redistribute it and/or
6			* modify it under the terms of the GNU General Public License
7			* as published by the Free Software Foundation; either version 2
8			* of the License, or (at your option) any later version.
9			*
10			* This program is distributed in the hope that it will be useful,
11			* but WITHOUT ANY WARRANTY; without even the implied warranty of
12			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13			* GNU General Public License for more details.
14			*
15			* You should have received a copy of the GNU General Public License
16			* along with this program; if not, write to the Free Software
17			* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18			*
19			*/
20			#define RCSID "$Id"
21
22			#ifdef HAVE_CONFIG_H
23			#include "config.h"
24			#endif
25
26			#include "ipcache.h"
27
28			#include <peak/peak.h>
29
30			#include <assert.h>
31			#include <stdio.h>
32			#include <stdlib.h>
33			#include <string.h>
34			#include <time.h>
35			#include <unistd.h>
36			#ifdef IPCACHE_TEST
37			#include <arpa/inet.h>
38			#endif
39
40			struct __ipcache_in4_entry
41			{
42			struct __ipcache_in4_entry *next;
43			struct in_addr key;
44			int lru_ring_refcnt;
45			time_t ts;
46			char data[0]; /* append optional data here */
47			};
48
49			typedef struct __ipcache_in4_entry hentry4;
50
51			struct __ipcache_in6_entry
52			{
53			struct __ipcache_in6_entry *next;
54			struct in6_addr key;
55			int lru_ring_refcnt;
56			time_t ts;
57			char data[0]; /* append optional data here */
58			};
59
60			typedef struct __ipcache_in6_entry hentry6;
61
62			typedef struct __ipcache_lru_ring *ipcache_lru_ring_t;
63
64			struct __ipcache
65			{
66			int buckets;
67			int count;
68			int maxcount;
69			size_t datasize;
70			int flags;
71			peak_mem_pool mem_pool;
72			union
73			{
74			struct __ipcache_in4_entry **v4;
75			struct __ipcache_in6_entry **v6;
76			} table;
77			ipcache_lru_ring_t lru_ring;
78			};
79
80			typedef void (ipcache_lru_ring_release_func)(ipcache_t cp, void obj);
81
82			struct __ipcache_lru_ring
83			{
84			int size;
85			int count;
86			int pos_start;
87			int pos_end;
88			ipcache_t cache;
89			void **address;
90			ipcache_lru_ring_release_func rel_fun;
91			};
92
93			static uint32_t hashfun_in4(const struct in_addr *addrptr);
94			static uint32_t hashfun_in6(const struct in6_addr *addrptr);
95
96			static int ipcache_hash_remove_in4(ipcache_t cp, struct in_addr *addr);
97			static int ipcache_hash_remove_in6(ipcache_t cp, struct in6_addr *addr);
98			static void ipcache_release_in4(ipcache_t cp, hentry4 *e);
99			static int ipcache_dispose_in4(ipcache_t cp, hentry4 *e);
100			static void ipcache_release_in6(ipcache_t cp, hentry6 *e);
101			static int ipcache_dispose_in6(ipcache_t cp, hentry6 *e);
102
103			static ipcache_lru_ring_t ipcache_lru_ring_create(ipcache_t cp, size_t size,
104			ipcache_lru_ring_release_func rel_fun);
105			static void ipcache_lru_ring_dispose(ipcache_lru_ring_t ring);
106			static void ipcache_lru_ring_add(ipcache_lru_ring_t ring, void *obj);
107			static int ipcache_lru_ring_clear(ipcache_lru_ring_t ring);
108
109			#ifdef IPCACHE_TEST
110			static int coll;
111			static int llen;
112			#endif
113
114			static uint32_t
115			hashfun_in4(const struct in_addr *addrptr)
116			{
117			return (uint32_t)addrptr->s_addr;
118			}
119
120			static uint32_t
121			hashfun_in6(const struct in6_addr *addrptr)
122			{
123			const u_char key = (u_char )addrptr;
124			uint32_t h = 0;
125
126			#define HASH4 \
127			h = h * 33 + *key++; \
128			h = h * 33 + *key++; \
129			h = h * 33 + *key++; \
130			h = h * 33 + *key++
131
132			HASH4;
133			HASH4;
134			HASH4;
135			HASH4;
136
137			return (h);
138			}
139
140			ipcache_t
141			ipcache_create_in4(int size, size_t datasize)
142			{
143			int pos;
144			ipcache_t cp = (ipcache_t)peak_allocate(sizeof(struct __ipcache));
145			cp->buckets = size;
146			cp->count = 0;
147			cp->maxcount = size;
148			cp->datasize = datasize;
149			cp->flags = 0;
150			cp->mem_pool = peak_mem_pool_create(sizeof(hentry4) + cp->datasize, 0);
151			cp->table.v4 = (hentry4 *)peak_allocate(sizeof(hentry4 ) * cp->buckets);
152
153			for (pos = cp->buckets; pos--; )
154			cp->table.v4[pos] = NULL;
155
156			cp->lru_ring = ipcache_lru_ring_create(cp, size,
157			(ipcache_lru_ring_release_func)ipcache_release_in4);
158
159			return cp;
160			}
161
162			ipcache_t
163			ipcache_create_in6(int size, size_t datasize)
164			{
165			int pos;
166			ipcache_t cp = (ipcache_t)peak_allocate(sizeof(struct __ipcache));
167			cp->buckets = size;
168			cp->count = 0;
169			cp->maxcount = size;
170			cp->datasize = datasize;
171			cp->flags = 1;
172			cp->mem_pool = peak_mem_pool_create(sizeof(hentry6) + cp->datasize, 0);
173			cp->table.v6 = (hentry6 *)peak_allocate(sizeof(hentry6 ) * cp->buckets);
174
175			for (pos = cp->buckets; pos--; )
176			cp->table.v6[pos] = NULL;
177
178			cp->lru_ring = ipcache_lru_ring_create(cp, size,
179			(ipcache_lru_ring_release_func)ipcache_release_in6);
180
181			return cp;
182			}
183
184			void
185			ipcache_dispose(ipcache_t cp)
186			{
187			ipcache_lru_ring_dispose(cp->lru_ring);
188			peak_release(cp->mem_pool);
189			peak_deallocate((void *)cp->table.v4);
190			peak_deallocate(cp);
191			}
192
193			int
194			ipcache_clear(ipcache_t cp)
195			{
196			int result = ipcache_lru_ring_clear(cp->lru_ring);
197			assert (cp->count == 0);
198			return result;
199			}
200
201			void
202			ipcache_add_in4(ipcache_t cp, const struct in_addr *addr, time_t t,
203			const void *data)
204			{
205			hentry4 *e;
206			uint32_t slot = hashfun_in4(addr) % cp->buckets;
207
208			for (e = cp->table.v4[slot]; e; e = e->next)
209			{
210			if (e->key.s_addr == addr->s_addr)
211			{
212			e->lru_ring_refcnt++;
213			e->ts = t;
214			ipcache_lru_ring_add(cp->lru_ring, e);
215			return;
216			}
217			}
218
219			e = (hentry4 *)peak_mem_pool_new(cp->mem_pool);
220			e->key = *addr;
221			e->lru_ring_refcnt = 0;
222			e->ts = t;
223			if (cp->datasize > 0)
224			memcpy(e->data, data, cp->datasize);
225
226			e->next = cp->table.v4[slot];
227
228			#ifdef IPCACHE_TEST
229			if (e->next != NULL)
230			{
231			int cnt;
232			hentry4 *ti = e;
233			coll++;
234			for (cnt = 0; ti->next != NULL; ti = ti->next)
235			cnt++;
236			if (cnt > llen)
237			llen = cnt;
238			}
239			#endif
240			cp->table.v4[slot] = e;
241			cp->count++;
242
243			e->lru_ring_refcnt++;
244			ipcache_lru_ring_add(cp->lru_ring, e);
245			}
246
247			void
248			ipcache_add_in6(ipcache_t cp, const struct in6_addr *addr, time_t t,
249			const void *data)
250			{
251			hentry6 *e;
252			uint32_t slot = hashfun_in6(addr) % cp->buckets;
253
254			for (e = cp->table.v6[slot]; e; e = e->next)
255			{
256			if (memcmp(&e->key, addr, sizeof(struct in6_addr)) == 0)
257			{
258			e->lru_ring_refcnt++;
259			e->ts = t;
260			ipcache_lru_ring_add(cp->lru_ring, e);
261			return;
262			}
263			}
264
265			e = (hentry6 *)peak_mem_pool_new(cp->mem_pool);
266			e->key = *addr;
267			e->lru_ring_refcnt = 0;
268			e->ts = t;
269
270			if (cp->datasize > 0)
271			memcpy(e->data, data, cp->datasize);
272			e->next = cp->table.v6[slot];
273			cp->table.v6[slot] = e;
274			cp->count++;
275
276			e->lru_ring_refcnt++;
277			ipcache_lru_ring_add(cp->lru_ring, e);
278			}
279
280			int
281			ipcache_invalidate_in4(ipcache_t cp, const struct in_addr *addr)
282			{
283			hentry4 *e;
284			uint32_t slot = hashfun_in4(addr) % cp->buckets;
285
286			for (e = cp->table.v4[slot]; e; e = e->next)
287			{
288			if (e->key.s_addr == addr->s_addr && e->ts != 0)
289			{
290			printf("ipcache_invalidate_in4: found!\n");
291			e->ts = 0;
292			return 0;
293			}
294			}
295			printf("ipcache_invalidate_in4: not found!\n");
296			return -1;
297			}
298
299			int
300			ipcache_invalidate_in6(ipcache_t cp, const struct in6_addr *addr)
301			{
302			hentry6 *e;
303			uint32_t slot = hashfun_in6(addr) % cp->buckets;
304
305			for (e = cp->table.v6[slot]; e; e = e->next)
306			{
307			if (memcmp(&e->key, addr, sizeof(struct in6_addr)) == 0
308			&& e->ts != 0)
309			{
310			e->ts = 0;
311			return 0;
312			}
313			}
314			return -1;
315			}
316
317			static int
318			ipcache_hash_remove_in4(ipcache_t cp, struct in_addr *addr)
319			{
320			hentry4 *e, kill;
321			uint32_t slot = hashfun_in4(addr) % cp->buckets;
322
323			for (e = &cp->table.v4[slot]; e; e = &((e)->next))
324			{
325			if ((*e)->key.s_addr == addr->s_addr)
326			{
327			cp->count--;
328			kill = *e;
329			e = (e)->next;
330			peak_mem_pool_delete(cp->mem_pool, kill);
331			return 0;
332			}
333			}
334			return -1;
335			}
336
337			static int
338			ipcache_hash_remove_in6(ipcache_t cp, struct in6_addr *addr)
339			{
340			hentry6 *e, kill;
341			uint32_t slot = hashfun_in6(addr) % cp->buckets;
342
343			for (e = &cp->table.v6[slot]; e; e = &((e)->next))
344			{
345			if (memcmp(&(*e)->key, addr, sizeof(struct in6_addr)) == 0)
346			{
347			cp->count--;
348			kill = *e;
349			e = (e)->next;
350			peak_mem_pool_delete(cp->mem_pool, kill);
351			return 0;
352			}
353			}
354			return -1;
355			}
356
357
358			static void
359			ipcache_release_in4(ipcache_t cp, hentry4 *e)
360			{
361			int err;
362
363			assert(e->lru_ring_refcnt > 0);
364
365			if (!--e->lru_ring_refcnt)
366			{
367			err = ipcache_dispose_in4(cp, e);
368			assert (err == 0);
369			}
370			}
371
372			static int
373			ipcache_dispose_in4(ipcache_t cp, hentry4 *e)
374			{
375			return ipcache_hash_remove_in4(cp, &e->key);
376			}
377
378			static void
379			ipcache_release_in6(ipcache_t cp, hentry6 *e)
380			{
381			int err;
382
383			assert(e->lru_ring_refcnt > 0);
384
385			if (!--e->lru_ring_refcnt)
386			{
387			err = ipcache_dispose_in6(cp, e);
388			assert (err == 0);
389			}
390			}
391
392			static int
393			ipcache_dispose_in6(ipcache_t cp, hentry6 *e)
394			{
395			return ipcache_hash_remove_in6(cp, &e->key);
396			}
397
398			time_t
399			ipcache_find_in4(ipcache_t cp, const struct in_addr addr, void *od)
400			{
401			hentry4 *e;
402			uint32_t slot = hashfun_in4(addr) % cp->buckets;
403
404			for (e = cp->table.v4[slot]; e; e = e->next)
405			if (e->key.s_addr == addr->s_addr)
406			{
407			if (od && cp->datasize)
408			*od = e->data;
409			return e->ts;
410			}
411
412			return 0;
413			}
414
415			time_t
416			ipcache_find_in6(ipcache_t cp, const struct in6_addr addr, void *od)
417			{
418			hentry6 *e;
419			uint32_t slot = hashfun_in6(addr) % cp->buckets;
420
421			for (e = cp->table.v6[slot]; e; e = e->next)
422			if (memcmp(&e->key, addr, sizeof(struct in6_addr)) == 0)
423			{
424			if (od && cp->datasize)
425			*od = e->data;
426			return e->ts;
427			}
428
429			return 0;
430			}
431
432			size_t
433			ipcache_get_count(ipcache_t cp)
434			{
435			return cp->lru_ring->count;
436			}
437
438			/************** Associated internal LRU Ring ***************/
439
440			static ipcache_lru_ring_t
441			ipcache_lru_ring_create(ipcache_t cp, size_t size,
442			ipcache_lru_ring_release_func rel_fun)
443			{
444			ipcache_lru_ring_t ring =
445			(ipcache_lru_ring_t)peak_allocate(sizeof(struct __ipcache_lru_ring));
446			ring->size = size;
447			ring->count = 0;
448			ring->address = (void *)peak_allocate(sizeof(void ) * ring->size);
449			ring->pos_start = 0;
450			ring->pos_end = -1;
451			ring->cache = cp;
452			ring->rel_fun = rel_fun;
453			return ring;
454			}
455
456			static void
457			ipcache_lru_ring_dispose(ipcache_lru_ring_t ring)
458			{
459			peak_deallocate(ring->address);
460			peak_deallocate(ring);
461			}
462
463			static void
464			ipcache_lru_ring_add(ipcache_lru_ring_t ring, void *obj)
465			{
466			if (++ring->pos_end >= ring->size)
467			ring->pos_end = 0;
468
469			if (ring->count >= ring->size)
470			{
471			assert (ring->pos_end == ring->pos_start);
472			assert (ring->count == ring->size);
473
474			(*ring->rel_fun)(ring->cache, ring->address[ring->pos_end]);
475
476			if (++ring->pos_start >= ring->size)
477			ring->pos_start = 0;
478			}
479			else
480			ring->count++;
481
482			ring->address[ring->pos_end] = obj;
483			}
484
485			static int
486			ipcache_lru_ring_clear(ipcache_lru_ring_t ring)
487			{
488			int result = ring->count;
489
490			while (ring->count > 0)
491			{
492			(*ring->rel_fun)(ring->cache, ring->address[ring->pos_start]);
493			if (++ring->pos_start >= ring->size)
494			ring->pos_start = 0;
495			ring->count--;
496			}
497			assert(ring->pos_start == ring->pos_end);
498
499			return result;
500			}
501
502			/********************** Special cleanup **********************/
503
504			size_t
505			ipcache_cleanup(ipcache_t cp, time_t expire_ts)
506			{
507			ipcache_lru_ring_t ring = cp->lru_ring;
508			size_t count = 0;
509
510			if (cp->flags & 1) /* ipv6 */
511			{
512			hentry6 *e6;
513
514			for (e6 = (hentry6 *)ring->address[ring->pos_start];
515			ring->count > 0 && e6->ts <= expire_ts;
516			e6 = (hentry6 *)ring->address[ring->pos_start])
517			{
518			(*ring->rel_fun)(ring->cache, ring->address[ring->pos_start]);
519			if (++ring->pos_start >= ring->size)
520			ring->pos_start = 0;
521			ring->count--;
522			count++;
523			}
524			}
525			else
526			{
527			hentry4 *e4;
528
529			for (e4 = (hentry4 *)ring->address[ring->pos_start];
530			ring->count > 0 && e4->ts <= expire_ts;
531			e4 = (hentry4 *)ring->address[ring->pos_start])
532			{
533			(*ring->rel_fun)(ring->cache, ring->address[ring->pos_start]);
534			if (++ring->pos_start >= ring->size)
535			ring->pos_start = 0;
536			ring->count--;
537			count++;
538			}
539			}
540			return count;
541			}
542
543
544			/********************** Cache storage **********************/
545
546			typedef struct __ipcache_file_header
547			{
548			uint32_t sig; // file signature
549			int32_t last_update; // file last update time
550			uint32_t sizeof_entry; // size of an entry in bytes
551			uint32_t count; // number of entries
552			} ipcache_file_header;
553
554			typedef struct __ipcache_file_entry4
555			{
556			struct in_addr addr;
557			time_t ts;
558			char data[0];
559			} ipcache_file_entry4;
560
561			typedef struct __ipcache_file_entry6
562			{
563			struct in6_addr addr;
564			time_t ts;
565			char data[0];
566			} ipcache_file_entry6;
567
568
569			#define SWAP_NMEMB 16
570
571			int
572			ipcache_swapin(ipcache_t cp, const char *file, uint32_t sig)
573			{
574			int res = -1;
575			FILE *fp;
576			ipcache_file_header head;
577			ipcache_file_entry4 e4p, e4p2;
578			ipcache_file_entry6 e6p, e6p2;
579			size_t size, i, n;
580			uint32_t cnt = 0;
581
582			if ((fp = fopen(file, "r")) == NULL)
583			return res;
584
585			if (fread(&head, sizeof(head), 1, fp) < 1 \|\| (head.sig != sig))
586			goto swapin_failure;
587
588			if (cp->flags & 1)
589			{
590			size = sizeof(ipcache_file_entry6) + cp->datasize;
591			if (head.sizeof_entry != size)
592			goto swapin_failure;
593
594			e6p = (ipcache_file_entry6 )peak_allocate(size SWAP_NMEMB);
595
596			while ((n = fread(e6p, size, SWAP_NMEMB, fp)) > 0)
597			for (i = 0, e6p2 = e6p; i < n; i++, cnt++, ((char*)e6p2) += size)
598			ipcache_add_in6(cp, &e6p2->addr, e6p2->ts, e6p2->data);
599
600			peak_deallocate(e6p);
601			}
602			else
603			{
604			size = sizeof(ipcache_file_entry4) + cp->datasize;
605			if (head.sizeof_entry != size)
606			goto swapin_failure;
607
608			e4p = (ipcache_file_entry4 )peak_allocate(size SWAP_NMEMB);
609
610			while ((n = fread(e4p, size, SWAP_NMEMB, fp)) > 0)
611			for (i = 0, e4p2 = e4p; i < n; i++, cnt++, ((char *)e4p2) += size)
612			ipcache_add_in4(cp, &e4p2->addr, e4p2->ts, e4p2->data);
613
614			peak_deallocate(e4p);
615			}
616
617			if (head.count == cnt)
618			res = 0; /* success */
619
620			swapin_failure:
621			fclose(fp);
622			return res;
623			}
624
625			int
626			ipcache_swapout(ipcache_t cp, const char *file, uint32_t sig)
627			{
628			int res = -1;
629			FILE *fp;
630			ipcache_file_header head;
631			ipcache_lru_ring_t ring = cp->lru_ring;
632			size_t size;
633			int i, pos;
634
635			if ((fp = fopen(file, "w")) == NULL)
636			return res;
637
638			size = (cp->flags & 1) ? sizeof(ipcache_file_entry6)
639			: sizeof(ipcache_file_entry4);
640			size += cp->datasize;
641
642			head.sig = sig;
643			head.last_update = peak_time();
644			head.sizeof_entry = size;
645			head.count = ring->count;
646
647			if (fwrite(&head, sizeof(head), 1, fp) < 1)
648			goto swapout_failure;
649
650			if (cp->flags & 1) /* ipv6 */
651			{
652			ipcache_file_entry6 *fe6p =
653			(ipcache_file_entry6 *)peak_allocate(size);
654			hentry6 *he6p;
655
656			for (i = ring->count, pos = ring->pos_start; i > 0; i--)
657			{
658			he6p = (hentry6 *)ring->address[pos];
659			fe6p->addr = he6p->key;
660			fe6p->ts = he6p->ts;
661			if (cp->datasize > 0)
662			memcpy(fe6p->data, he6p->data, cp->datasize);
663			if (fwrite(fe6p, size, 1, fp) < 1)
664			goto swapout_failure;
665
666			if (++pos >= ring->size)
667			pos = 0;
668			}
669			peak_deallocate(fe6p);
670			}
671			else
672			{
673			ipcache_file_entry4 *fe4p =
674			(ipcache_file_entry4 *)peak_allocate(size);
675			hentry4 *he4p;
676
677			for (i = ring->count, pos = ring->pos_start; i > 0; i--)
678			{
679			he4p = (hentry4 *)ring->address[pos];
680			fe4p->addr = he4p->key;
681			fe4p->ts = he4p->ts;
682			if (cp->datasize > 0)
683			memcpy(fe4p->data, he4p->data, cp->datasize);
684			if (fwrite(fe4p, size, 1, fp) < 1)
685			goto swapout_failure;
686
687			if (++pos >= ring->size)
688			pos = 0;
689			}
690			peak_deallocate(fe4p);
691			}
692			res = 0;
693			swapout_failure:
694			fclose(fp);
695			return res;
696			}
697
698
699
700			/* Test */
701
702			#ifdef IPCACHE_TEST
703			int
704			main(int argc, char *argv[])
705			{
706			ipcache_t cache = ipcache_create_in4(CACHESIZE, 0);
707			struct in_addr addr;
708			int i, j, res;
709			int found = 0, loaded = 0;
710			FILE *fp;
711			char buf[32];
712			struct in_addr randips = malloc(sizeof(struct in_addr) LOOPS);
713
714			fp = fopen("urandip.txt", "r");
715			assert(fp);
716
717			i = 0;
718			while(fgets(buf, sizeof(buf), fp))
719			{
720			buf[strlen(buf)-1] = '\0';
721			randips[i++].s_addr = inet_addr(buf);
722			loaded++;
723			}
724
725			for (j = 0; i < LOOPS; i++, j++)
726			{
727			randips[i] = randips[j];
728			randips[i].s_addr += 2;
729			}
730			fclose(fp);
731
732			for (i = 0; i < LOOPS; i++)
733			{
734			addr = randips[i];
735			if (ipcache_find_in4(cache, &addr, NULL) != 0)
736			found++;
737
738			ipcache_add_in4(cache, &addr, peak_time(), NULL);
739			}
740
741			#if CACHESIZE >= LOOPS
742			for (i = 0; i < LOOPS; i++)
743			{
744			addr = randips[i];
745			assert (ipcache_find_in4(cache, &addr, NULL) != 0);
746			}
747			#endif
748			printf("coll=%d loaded=%d %f%% found=%d llen=%d\n", coll, loaded,
749			100.0 - (100.0 * (double)coll/(double)(LOOPS-found)), found, llen);
750
751			printf("swapout...\n");
752			res = ipcache_swapout(cache, "test.cache", 42);
753			assert(res == 0);
754			ipcache_dispose(cache);
755			cache = ipcache_create_in4(CACHESIZE, 0);
756			printf("swapin...\n");
757			res = ipcache_swapin(cache, "test.cache", 42);
758			assert(res == 0);
759			#if CACHESIZE >= LOOPS
760			printf("recovery test...");
761			for (i = 0; i < LOOPS; i++)
762			{
763			addr = randips[i];
764			assert (ipcache_find_in4(cache, &addr, NULL) != 0);
765			}
766			#endif
767			printf("ok\n");
768			return 0;
769			}
770			#endif /* IPCACHE_TEST */