1 /* 2 cache.c -- Generic cache routines. 3 Copyright (C) 2003 Roy Keene 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 2 of the License, or 8 (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 email: tcpcgi@rkeene.org 20 21 */ 22 23 /* 24 * Generic cache routines -- designed for the LAN Block Device, but 25 * should be usable for almost anything (hopefully). 26 */ 27 28 29 #include <sys/types.h> 30 #include <unistd.h> 31 #include <stdlib.h> 32 #include <string.h> 33 #include <stdio.h> 34 #include <time.h> 35 #include "cache.h" 36 37 #ifndef MIN 38 #define MIN(x,y) ((x)<(y)?(x):(y)) 39 #endif 40 41 /* 42 * Internal only. 43 */ 44 static uint32_t cache_hash(unsigned char *key, uint8_t keylen) { 45 uint32_t i,h=0,g; 46 47 for (i=0;i<keylen;i++) { 48 h = (h << 4) + key[i]; 49 if ((g = (h & 0xf0000000))) h ^= (g >> 24); 50 h &= ~g; 51 } 52 53 return(h); 54 } 55 56 /* 57 * Internal only. 58 */ 59 static cachei_t *cache_find_i(cache_t *c, uint32_t hashkey, void *key, uint8_t keylen) { 60 time_t ctime; 61 uint8_t keylenmin; 62 cachei_t *cur, *del; 63 64 if (!c) return(NULL); 65 66 ctime=time(NULL); 67 /* Compute location based on hash of key value. */ 68 cur=c->hashtable[hashkey]; 69 while (cur) { 70 if (ctime>cur->expires && cur->expires!=0) { 71 del=cur; 72 cur=cur->_next; 73 /* Move the pointers around before we delete things. */ 74 if (del->_next) del->_next->_prev=del->_prev; 75 if (del->_prev) { 76 del->_prev->_next=del->_next; 77 } else { 78 c->hashtable[hashkey]=del->_next; 79 } 80 if (!del->_next && !del->_prev) c->hashtable[hashkey]=NULL; 81 if (del->cleanup) del->cleanup(del, del->key, del->keylen); 82 /* Noone should be referencing us now, delete. */ 83 free(del); 84 continue; 85 } 86 keylenmin=MIN(cur->keylen, keylen); 87 if (memcmp(key, cur->key, keylenmin)!=0 || keylen!=cur->keylen) { 88 cur=cur->_next; 89 } else { 90 break; 91 } 92 } 93 return(cur); 94 } 95 96 /* 97 * cache_t *cache_create( 98 * int num Size of hash table to create. 99 * ); 100 */ 101 cache_t *cache_create(int num) { 102 cache_t *ret; 103 104 ret=malloc(sizeof(cache_t)); 105 if ((ret->hashtable=calloc(num, sizeof(cachei_t *)))==NULL) { 106 return(NULL); 107 } 108 ret->hashsize=num; 109 return(ret); 110 } 111 112 /* 113 * int cache_destroy( 114 * cache_t *c Cache object to destroy. 115 * ); 116 */ 117 int cache_destroy(cache_t *c) { 118 cachei_t *cur, *del; 119 int i; 120 121 if (!c) return(0); 122 if (!c->hashtable) return(0); 123 124 for (i=0;i<(c->hashsize);i++) { 125 cur=c->hashtable[i]; 126 while (cur) { 127 del=cur; 128 cur=cur->_next; 129 if (del->cleanup) del->cleanup(del->data, del->key, del->keylen); 130 free(del); 131 } 132 } 133 134 free(c->hashtable); 135 free(c); 136 return(1); 137 } 138 139 #if defined(DEBUG) || defined(CACHE_DEBUG) 140 /* 141 * void cache_print( 142 * cache_t *c Cache object 143 * ); 144 * Notes: 145 * This function dumps a representation of the hash table to stdout. 146 */ 147 void cache_print(cache_t *c) { 148 cachei_t *cur; 149 int i; 150 151 if (!c) return; 152 153 for (i=0;i<(c->hashsize);i++) { 154 printf("%p[%i]=", c, i); 155 cur=c->hashtable[i]; 156 while (cur) { 157 printf("%p{\"%s\",%i} -> ", cur, (char *) cur->key, cur->keylen); 158 cur=cur->_next; 159 } 160 printf("NULL\n"); 161 } 162 return; 163 } 164 #endif 165 166 /* 167 * cache_add( 168 * cache_t *c Cache to operate on. 169 * void *key Key to used to reference data. 170 * uint8_t keylen Size of the key. 171 * void *data Data to add 172 * uint32_t datalen Size of data 173 * ); 174 * Return value: 175 * NULL if no previous value was found 176 * (void *) to data being replaced with the new value. 177 * 178 */ 179 void *cache_add(cache_t *c, void *key, uint8_t keylen, void *data, uint32_t datalen, time_t ttl, void *cleanup) { 180 uint32_t hashkey; 181 cachei_t *cur=NULL, *ocur, *new; 182 void *ret; 183 184 if (!c) return(NULL); 185 186 /* Compute location based on hash of key value. */ 187 hashkey=(cache_hash(key, keylen))%(c->hashsize); 188 ocur=c->hashtable[hashkey]; 189 190 cur=cache_find_i(c, hashkey, key, keylen); 191 192 if (cur) { 193 /* Found... do what? Save the old data (to return) 194 * and replace the data field, then return the old. 195 */ 196 ret=cur->data; 197 cur->data=data; 198 cur->datalen=datalen; 199 cur->expires=(ttl)?(time(NULL)+ttl):(0); 200 new->cleanup=cleanup; 201 return(ret); 202 } 203 204 /* NOTFOUND=add it */ 205 if ((new=malloc(sizeof(cachei_t)))==NULL) return(NULL); 206 new->_next=ocur; 207 new->_prev=NULL; 208 new->data=data; 209 new->key=key; 210 new->datalen=datalen; 211 new->keylen=keylen; 212 new->expires=(ttl)?(time(NULL)+ttl):(0); 213 new->cleanup=cleanup; 214 c->hashtable[hashkey]=new; 215 if (ocur) ocur->_prev=new; 216 return(NULL); 217 } 218 219 /* 220 * void *cache_delete( 221 * cache_t *c Cache object to operate on. 222 * void *key Key to entry in cache object. 223 * uint8_t keylen Size of the key. 224 * uint32_t *datalen Length of data being returned, 225 * if provided when _add()'d, may 226 * be NULL. 227 * int cleanup If (TRUE) then call the cleanup 228 * function for the data, otherwise 229 * don't. 230 * ); 231 * Return value: 232 * Fail: 233 * NULL if not found, and *datalen is set to (~0ULL) (all bits 234 * set). 235 * Success: 236 * Otherwise, data provided is returned and datalen is set to 237 * added value, if it's not NULL (this data may no longer be 238 * useful if cleanup is set to TRUE.) 239 * 240 */ 241 void *cache_delete(cache_t *c, void *key, uint8_t keylen, uint32_t *datalen, int cleanup) { 242 uint32_t hashkey; 243 cachei_t *cur; 244 void *ret; 245 246 if (!c) return(NULL); 247 248 /* Compute location based on hash of key value. */ 249 hashkey=(cache_hash(key, keylen))%(c->hashsize); 250 cur=cache_find_i(c, hashkey, key, keylen); 251 252 /* If not found, abort the deletion operation. */ 253 if (!cur) { 254 if (datalen) *datalen=(uint32_t) (~0ULL); 255 return(NULL); 256 } 257 258 if (datalen) *datalen=cur->datalen; 259 ret=cur->data; 260 261 /* Move the pointers around before we delete things. */ 262 if (cur->_next) cur->_next->_prev=cur->_prev; 263 if (cur->_prev) { 264 cur->_prev->_next=cur->_next; 265 } else { 266 c->hashtable[hashkey]=cur->_next; 267 } 268 if (!cur->_next && !cur->_prev) c->hashtable[hashkey]=NULL; 269 270 if (cleanup && cur->cleanup) cur->cleanup(cur->data, cur->key, cur->keylen); 271 272 /* Noone should be referencing us now, delete. */ 273 free(cur); 274 275 return(ret); 276 } 277 278 /* 279 * void *cache_find( 280 * cache_t *c Cache object to operate on. 281 * void *key Key to entry in cache object. 282 * uint8_t keylen Size of the key. 283 * uint32_t *datalen Length of data being returned, 284 * if provided when _add()'d, may 285 * be NULL. 286 * ); 287 * Return value: 288 * Fail: 289 * NULL if not found, and *datalen is set to (~0ULL) (all bits 290 * set). 291 * Success: 292 * Otherwise, data provided is returned and datalen is set to 293 * added value, if it's not NULL. 294 * 295 */ 296 void *cache_find(cache_t *c, void *key, uint8_t keylen, uint32_t *datalen) { 297 uint32_t hashkey; 298 cachei_t *cur; 299 void *ret; 300 301 if (!c) return(NULL); 302 303 hashkey=(cache_hash(key, keylen))%(c->hashsize); 304 cur=cache_find_i(c, hashkey, key, keylen); 305 if (!cur) { 306 if (datalen) *datalen=(uint32_t) (~0ULL); 307 return(NULL); 308 } 309 if (datalen) *datalen=cur->datalen; 310 ret=cur->data; 311 return(ret); 312 } 313 314 #define ARRAY_TO_COMMA4(x) ((char) (((x)>>24)&0xff)),((char) (((x)>>16)&0xff)),((char) (((x)>>8)&0xff)),((char) ((x)&0xff)) 315 /* 316 * int cache_save( 317 * cache_t *c Cache object to save. 318 * FILE *fp FILE object to save to (see note #4) 319 * int fd File descriptor to save to (see note #4) 320 * ); 321 * Return value: 322 * Number of items saved, -1 on error. 323 * *** NOTES *** 324 * 1. This assumes time() returns a 32bit integer! This will need to changed by Feb 2038. 325 * 2. The cleanup() function will be lost, and the data will be automatically cleaned up. 326 * 3. This REQUIRES the datalen field to be accurate. 327 * 4. If `fp' is NULL then `fd' is used, otherwise `fp' is used. 328 */ 329 int cache_save(cache_t *c, FILE *fp, int fd) { 330 cachei_t *cur; 331 FILE *fdfp; 332 int i,cnt=0; 333 334 if (!c) return(0); 335 336 if (fp) { 337 fdfp=fp; 338 } else { 339 fdfp=fdopen(fd, "w"); 340 } 341 342 /* Put our magic at the beginning of the file. */ 343 fprintf(fdfp, "rkc%c", 0); 344 fprintf(fdfp, "%c%c%c%c", ARRAY_TO_COMMA4(c->hashsize)); 345 346 for (i=0;i<(c->hashsize);i++) { 347 cur=c->hashtable[i]; 348 while (cur) { 349 /* If our datalen is non-sense, fix it. */ 350 if (cur->data==NULL && cur->datalen!=0) cur->datalen=0; 351 fprintf(fdfp, "%c%c%c%c%c%c%c%c%c", cur->keylen, ARRAY_TO_COMMA4(cur->datalen), ARRAY_TO_COMMA4((uint32_t) cur->expires)); 352 if (fwrite(cur->key, cur->keylen, 1, fdfp)<0) return(-1); 353 if (cur->data) { 354 if (fwrite(cur->data, cur->datalen, 1, fdfp)<0) return(-1); 355 } 356 cur=cur->_next; 357 cnt++; 358 } 359 } 360 fprintf(fdfp, "%c%c%c%c%c", 0x0, 0xff, 0xff, 0xff, 0xff); 361 return(cnt); 362 } 363 364 #ifndef ARRAY_TO_INT32 365 #define ARRAY_TO_INT32(x, y) ((((uint32_t) x[(y)])<<24) | (((uint32_t) x[(y)+1])<<16) | (((uint32_t) x[(y)+2])<<8) | (((uint32_t) x[(y)+3]))) 366 #endif 367 /* 368 * cache_t *cache_load( 369 * FILE *fp FILE object to load from (see note#2). 370 * int fd File descriptor to load from (see note #2). 371 * ); 372 * Return value: 373 * Returns the cache_t object or NULL on error. 374 * *** NOTES *** 375 * 1. This assumes time() returns a 32bit integer! This will need to changed by Feb 2038. 376 * 2. If `fp' is NULL then `fd' is used, otherwise `fp' is used. 377 */ 378 cache_t *cache_load(FILE *fp, int fd) { 379 cache_t *ret=NULL; 380 FILE *fdfp; 381 void *key, *data; 382 char magic[4]; 383 unsigned char ui32c[4]; 384 uint32_t hashsize, datalen; 385 uint8_t keylen; 386 time_t expires, ctime, ttl; 387 388 if (fp) { 389 fdfp=fp; 390 } else { 391 fdfp=fdopen(fd, "r"); 392 } 393 394 ctime=time(NULL); 395 fread(&magic, sizeof(magic), 1, fdfp); 396 if (memcmp(magic, "rkc\0", 4)!=0) return(NULL); 397 fread(&ui32c, sizeof(ui32c), 1, fdfp); /* hashsize */ 398 hashsize=ARRAY_TO_INT32(ui32c, 0); 399 /* Create the cache hash table. */ 400 ret=cache_create(hashsize); 401 if (!ret) { 402 return(NULL); /* We've read a bit of data, should we lseek() backwards, SEEK_CUR -8 ? */ 403 } 404 405 while (!feof(fdfp)) { 406 fread(&keylen, sizeof(uint8_t), 1, fdfp); /* keylen */ 407 fread(&ui32c, sizeof(ui32c), 1, fdfp); /* datalen */ 408 datalen=ARRAY_TO_INT32(ui32c, 0); 409 fread(&ui32c, sizeof(ui32c), 1, fdfp); /* expires */ 410 expires=(time_t) ARRAY_TO_INT32(ui32c, 0); 411 if (keylen==0 && datalen==0xffffffff) break; /* This is our EOF sequence. */ 412 if ((key=malloc(keylen))==NULL) continue; 413 if ((data=malloc(datalen))==NULL) { free(key); continue; } 414 fread(key, keylen, 1, fdfp); /* key */ 415 fread(data, datalen, 1, fdfp); /* data */ 416 /* Add the entry. */ 417 ttl=(expires-ctime); 418 if (ttl<=0) continue; /* No sense in adding an expired entry. */ 419 cache_add(ret, key, keylen, data, datalen, ttl, free); 420 } 421 422 return(ret); 423 } |