Commit | Line | Data |
---|---|---|
dc0d77d7 CE |
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 | } |