cache.c

   1 #include "alloc.h"
   2 #include "byte.h"
   3 #include "uint32.h"
   4 #include "exit.h"
   5 #include "tai.h"
   6 #include "cache.h"
   7
   8 uint64 cache_motion = 0;
   9
  10 static char *x = 0;
  11 static uint32 size;
  12 static uint32 hsize;
  13 static uint32 writer;
  14 static uint32 oldest;
  15 static uint32 unused;
  16
  17 /*
  18 100 <= size <= 1000000000.
  19 4 <= hsize <= size/16.
  20 hsize is a power of 2.
  21
  22 hsize <= writer <= oldest <= unused <= size.
  23 If oldest == unused then unused == size.
  24
  25 x is a hash table with the following structure:
  26 x[0...hsize-1]: hsize/4 head links.
  27 x[hsize...writer-1]: consecutive entries, newest entry on the right.
  28 x[writer...oldest-1]: free space for new entries.
  29 x[oldest...unused-1]: consecutive entries, oldest entry on the left.
  30 x[unused...size-1]: unused.
  31
  32 Each hash bucket is a linked list containing the following items:
  33 the head link, the newest entry, the second-newest entry, etc.
  34 Each link is a 4-byte number giving the xor of
  35 the positions of the adjacent items in the list.
  36
  37 Entries are always inserted immediately after the head and removed at the tail.
  38
  39 Each entry contains the following information:
  40 4-byte link; 4-byte keylen; 4-byte datalen; 8-byte expire time; key; data.
  41 */
  42
  43 #define MAXKEYLEN 1000
  44 #define MAXDATALEN 1000000
  45
  46 static void cache_impossible(void)
  47 {
  48   _exit(111);
  49 }
  50
  51 static void set4(uint32 pos,uint32 u)
  52 {
  53   if (pos > size - 4) cache_impossible();
  54   uint32_pack(x + pos,u);
  55 }
  56
  57 static uint32 get4(uint32 pos)
  58 {
  59   uint32 result;
  60   if (pos > size - 4) cache_impossible();
  61   uint32_unpack(x + pos,&result);
  62   return result;
  63 }
  64
  65 static unsigned int hash(const char *key,unsigned int keylen)
  66 {
  67   unsigned int result = 5381;
  68
  69   while (keylen) {
  70     result = (result << 5) + result;
  71     result ^= (unsigned char) *key;
  72     ++key;
  73     --keylen;
  74   }
  75   result <<= 2;
  76   result &= hsize - 4;
  77   return result;
  78 }
  79
  80 char *cache_get(const char *key,unsigned int keylen,unsigned int *datalen,uint32 *ttl)
  81 {
  82   struct tai expire;
  83   struct tai now;
  84   uint32 pos;
  85   uint32 prevpos;
  86   uint32 nextpos;
  87   uint32 u;
  88   unsigned int loop;
  89   double d;
  90
  91   if (!x) return 0;
  92   if (keylen > MAXKEYLEN) return 0;
  93
  94   prevpos = hash(key,keylen);
  95   pos = get4(prevpos);
  96   loop = 0;
  97
  98   while (pos) {
  99     if (get4(pos + 4) == keylen) {
 100       if (pos + 20 + keylen > size) cache_impossible();
 101       if (byte_equal(key,keylen,x + pos + 20)) {
 102         tai_unpack(x + pos + 12,&expire);
 103         tai_now(&now);
 104         if (tai_less(&expire,&now)) return 0;
 105
 106         tai_sub(&expire,&expire,&now);
 107         d = tai_approx(&expire);
 108         if (d > 604800) d = 604800;
 109         *ttl = d;
 110
 111         u = get4(pos + 8);
 112         if (u > size - pos - 20 - keylen) cache_impossible();
 113         *datalen = u;
 114
 115         return x + pos + 20 + keylen;
 116       }
 117     }
 118     nextpos = prevpos ^ get4(pos);
 119     prevpos = pos;
 120     pos = nextpos;
 121     if (++loop > 100) return 0; /* to protect against hash flooding */
 122   }
 123
 124   return 0;
 125 }
 126
 127 void cache_set(const char *key,unsigned int keylen,const char *data,unsigned int datalen,uint32 ttl)
 128 {
 129   struct tai now;
 130   struct tai expire;
 131   unsigned int entrylen;
 132   unsigned int keyhash;
 133   uint32 pos;
 134
 135   if (!x) return;
 136   if (keylen > MAXKEYLEN) return;
 137   if (datalen > MAXDATALEN) return;
 138
 139   if (!ttl) return;
 140   if (ttl > 604800) ttl = 604800;
 141
 142   entrylen = keylen + datalen + 20;
 143
 144   while (writer + entrylen > oldest) {
 145     if (oldest == unused) {
 146       if (writer <= hsize) return;
 147       unused = writer;
 148       oldest = hsize;
 149       writer = hsize;
 150     }
 151
 152     pos = get4(oldest);
 153     set4(pos,get4(pos) ^ oldest);
 154
 155     oldest += get4(oldest + 4) + get4(oldest + 8) + 20;
 156     if (oldest > unused) cache_impossible();
 157     if (oldest == unused) {
 158       unused = size;
 159       oldest = size;
 160     }
 161   }
 162
 163   keyhash = hash(key,keylen);
 164
 165   tai_now(&now);
 166   tai_uint(&expire,ttl);
 167   tai_add(&expire,&expire,&now);
 168
 169   pos = get4(keyhash);
 170   if (pos)
 171     set4(pos,get4(pos) ^ keyhash ^ writer);
 172   set4(writer,pos ^ keyhash);
 173   set4(writer + 4,keylen);
 174   set4(writer + 8,datalen);
 175   tai_pack(x + writer + 12,&expire);
 176   byte_copy(x + writer + 20,keylen,key);
 177   byte_copy(x + writer + 20 + keylen,datalen,data);
 178
 179   set4(keyhash,writer);
 180   writer += entrylen;
 181   cache_motion += entrylen;
 182 }
 183
 184 int cache_init(unsigned int cachesize)
 185 {
 186   if (x) {
 187     alloc_free(x);
 188     x = 0;
 189   }
 190
 191   if (cachesize > 1000000000) cachesize = 1000000000;
 192   if (cachesize < 100) cachesize = 100;
 193   size = cachesize;
 194
 195   hsize = 4;
 196   while (hsize <= (size >> 5)) hsize <<= 1;
 197
 198   x = alloc(size);
 199   if (!x) return 0;
 200   byte_zero(x,size);
 201
 202   writer = hsize;
 203   oldest = size;
 204   unused = size;
 205
 206   return 1;
 207 }