1238106Sdes/* 2238106Sdes * util/storage/lruhash.c - hashtable, hash function, LRU keeping. 3238106Sdes * 4238106Sdes * Copyright (c) 2007, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * This software is open source. 7238106Sdes * 8238106Sdes * Redistribution and use in source and binary forms, with or without 9238106Sdes * modification, are permitted provided that the following conditions 10238106Sdes * are met: 11238106Sdes * 12238106Sdes * Redistributions of source code must retain the above copyright notice, 13238106Sdes * this list of conditions and the following disclaimer. 14238106Sdes * 15238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 16238106Sdes * this list of conditions and the following disclaimer in the documentation 17238106Sdes * and/or other materials provided with the distribution. 18238106Sdes * 19238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 20238106Sdes * be used to endorse or promote products derived from this software without 21238106Sdes * specific prior written permission. 22238106Sdes * 23238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24269257Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25269257Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26269257Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27269257Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28269257Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29269257Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30269257Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31269257Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32269257Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33269257Sdes * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34238106Sdes */ 35238106Sdes 36238106Sdes/** 37238106Sdes * \file 38238106Sdes * 39238106Sdes * This file contains a hashtable with LRU keeping of entries. 40238106Sdes * 41238106Sdes */ 42238106Sdes 43238106Sdes#include "config.h" 44238106Sdes#include "util/storage/lruhash.h" 45238106Sdes#include "util/fptr_wlist.h" 46238106Sdes 47238106Sdesvoid 48238106Sdesbin_init(struct lruhash_bin* array, size_t size) 49238106Sdes{ 50238106Sdes size_t i; 51238106Sdes#ifdef THREADS_DISABLED 52238106Sdes (void)array; 53238106Sdes#endif 54238106Sdes for(i=0; i<size; i++) { 55238106Sdes lock_quick_init(&array[i].lock); 56238106Sdes lock_protect(&array[i].lock, &array[i], 57238106Sdes sizeof(struct lruhash_bin)); 58238106Sdes } 59238106Sdes} 60238106Sdes 61238106Sdesstruct lruhash* 62238106Sdeslruhash_create(size_t start_size, size_t maxmem, lruhash_sizefunc_t sizefunc, 63238106Sdes lruhash_compfunc_t compfunc, lruhash_delkeyfunc_t delkeyfunc, 64238106Sdes lruhash_deldatafunc_t deldatafunc, void* arg) 65238106Sdes{ 66238106Sdes struct lruhash* table = (struct lruhash*)calloc(1, 67238106Sdes sizeof(struct lruhash)); 68238106Sdes if(!table) 69238106Sdes return NULL; 70238106Sdes lock_quick_init(&table->lock); 71238106Sdes table->sizefunc = sizefunc; 72238106Sdes table->compfunc = compfunc; 73238106Sdes table->delkeyfunc = delkeyfunc; 74238106Sdes table->deldatafunc = deldatafunc; 75238106Sdes table->cb_arg = arg; 76238106Sdes table->size = start_size; 77238106Sdes table->size_mask = (int)(start_size-1); 78238106Sdes table->lru_start = NULL; 79238106Sdes table->lru_end = NULL; 80238106Sdes table->num = 0; 81238106Sdes table->space_used = 0; 82238106Sdes table->space_max = maxmem; 83238106Sdes table->array = calloc(table->size, sizeof(struct lruhash_bin)); 84238106Sdes if(!table->array) { 85238106Sdes lock_quick_destroy(&table->lock); 86238106Sdes free(table); 87238106Sdes return NULL; 88238106Sdes } 89238106Sdes bin_init(table->array, table->size); 90238106Sdes lock_protect(&table->lock, table, sizeof(*table)); 91238106Sdes lock_protect(&table->lock, table->array, 92238106Sdes table->size*sizeof(struct lruhash_bin)); 93238106Sdes return table; 94238106Sdes} 95238106Sdes 96238106Sdesvoid 97238106Sdesbin_delete(struct lruhash* table, struct lruhash_bin* bin) 98238106Sdes{ 99238106Sdes struct lruhash_entry* p, *np; 100238106Sdes void *d; 101238106Sdes if(!bin) 102238106Sdes return; 103238106Sdes lock_quick_destroy(&bin->lock); 104238106Sdes p = bin->overflow_list; 105238106Sdes bin->overflow_list = NULL; 106238106Sdes while(p) { 107238106Sdes np = p->overflow_next; 108238106Sdes d = p->data; 109238106Sdes (*table->delkeyfunc)(p->key, table->cb_arg); 110238106Sdes (*table->deldatafunc)(d, table->cb_arg); 111238106Sdes p = np; 112238106Sdes } 113238106Sdes} 114238106Sdes 115238106Sdesvoid 116238106Sdesbin_split(struct lruhash* table, struct lruhash_bin* newa, 117238106Sdes int newmask) 118238106Sdes{ 119238106Sdes size_t i; 120238106Sdes struct lruhash_entry *p, *np; 121238106Sdes struct lruhash_bin* newbin; 122238106Sdes /* move entries to new table. Notice that since hash x is mapped to 123238106Sdes * bin x & mask, and new mask uses one more bit, so all entries in 124238106Sdes * one bin will go into the old bin or bin | newbit */ 125238106Sdes#ifndef THREADS_DISABLED 126238106Sdes int newbit = newmask - table->size_mask; 127238106Sdes#endif 128238106Sdes /* so, really, this task could also be threaded, per bin. */ 129238106Sdes /* LRU list is not changed */ 130238106Sdes for(i=0; i<table->size; i++) 131238106Sdes { 132238106Sdes lock_quick_lock(&table->array[i].lock); 133238106Sdes p = table->array[i].overflow_list; 134238106Sdes /* lock both destination bins */ 135238106Sdes lock_quick_lock(&newa[i].lock); 136238106Sdes lock_quick_lock(&newa[newbit|i].lock); 137238106Sdes while(p) { 138238106Sdes np = p->overflow_next; 139238106Sdes /* link into correct new bin */ 140238106Sdes newbin = &newa[p->hash & newmask]; 141238106Sdes p->overflow_next = newbin->overflow_list; 142238106Sdes newbin->overflow_list = p; 143238106Sdes p=np; 144238106Sdes } 145238106Sdes lock_quick_unlock(&newa[i].lock); 146238106Sdes lock_quick_unlock(&newa[newbit|i].lock); 147238106Sdes lock_quick_unlock(&table->array[i].lock); 148238106Sdes } 149238106Sdes} 150238106Sdes 151238106Sdesvoid 152238106Sdeslruhash_delete(struct lruhash* table) 153238106Sdes{ 154238106Sdes size_t i; 155238106Sdes if(!table) 156238106Sdes return; 157238106Sdes /* delete lock on hashtable to force check its OK */ 158238106Sdes lock_quick_destroy(&table->lock); 159238106Sdes for(i=0; i<table->size; i++) 160238106Sdes bin_delete(table, &table->array[i]); 161238106Sdes free(table->array); 162238106Sdes free(table); 163238106Sdes} 164238106Sdes 165238106Sdesvoid 166238106Sdesbin_overflow_remove(struct lruhash_bin* bin, struct lruhash_entry* entry) 167238106Sdes{ 168238106Sdes struct lruhash_entry* p = bin->overflow_list; 169238106Sdes struct lruhash_entry** prevp = &bin->overflow_list; 170238106Sdes while(p) { 171238106Sdes if(p == entry) { 172238106Sdes *prevp = p->overflow_next; 173238106Sdes return; 174238106Sdes } 175238106Sdes prevp = &p->overflow_next; 176238106Sdes p = p->overflow_next; 177238106Sdes } 178238106Sdes} 179238106Sdes 180238106Sdesvoid 181238106Sdesreclaim_space(struct lruhash* table, struct lruhash_entry** list) 182238106Sdes{ 183238106Sdes struct lruhash_entry* d; 184238106Sdes struct lruhash_bin* bin; 185238106Sdes log_assert(table); 186238106Sdes /* does not delete MRU entry, so table will not be empty. */ 187238106Sdes while(table->num > 1 && table->space_used > table->space_max) { 188238106Sdes /* notice that since we hold the hashtable lock, nobody 189238106Sdes can change the lru chain. So it cannot be deleted underneath 190238106Sdes us. We still need the hashbin and entry write lock to make 191238106Sdes sure we flush all users away from the entry. 192238106Sdes which is unlikely, since it is LRU, if someone got a rdlock 193238106Sdes it would be moved to front, but to be sure. */ 194238106Sdes d = table->lru_end; 195238106Sdes /* specialised, delete from end of double linked list, 196238106Sdes and we know num>1, so there is a previous lru entry. */ 197238106Sdes log_assert(d && d->lru_prev); 198238106Sdes table->lru_end = d->lru_prev; 199238106Sdes d->lru_prev->lru_next = NULL; 200238106Sdes /* schedule entry for deletion */ 201238106Sdes bin = &table->array[d->hash & table->size_mask]; 202238106Sdes table->num --; 203238106Sdes lock_quick_lock(&bin->lock); 204238106Sdes bin_overflow_remove(bin, d); 205238106Sdes d->overflow_next = *list; 206238106Sdes *list = d; 207238106Sdes lock_rw_wrlock(&d->lock); 208238106Sdes table->space_used -= table->sizefunc(d->key, d->data); 209238106Sdes if(table->markdelfunc) 210238106Sdes (*table->markdelfunc)(d->key); 211238106Sdes lock_rw_unlock(&d->lock); 212238106Sdes lock_quick_unlock(&bin->lock); 213238106Sdes } 214238106Sdes} 215238106Sdes 216238106Sdesstruct lruhash_entry* 217238106Sdesbin_find_entry(struct lruhash* table, 218238106Sdes struct lruhash_bin* bin, hashvalue_t hash, void* key) 219238106Sdes{ 220238106Sdes struct lruhash_entry* p = bin->overflow_list; 221238106Sdes while(p) { 222238106Sdes if(p->hash == hash && table->compfunc(p->key, key) == 0) 223238106Sdes return p; 224238106Sdes p = p->overflow_next; 225238106Sdes } 226238106Sdes return NULL; 227238106Sdes} 228238106Sdes 229238106Sdesvoid 230238106Sdestable_grow(struct lruhash* table) 231238106Sdes{ 232238106Sdes struct lruhash_bin* newa; 233238106Sdes int newmask; 234238106Sdes size_t i; 235238106Sdes if(table->size_mask == (int)(((size_t)-1)>>1)) { 236238106Sdes log_err("hash array malloc: size_t too small"); 237238106Sdes return; 238238106Sdes } 239238106Sdes /* try to allocate new array, if not fail */ 240238106Sdes newa = calloc(table->size*2, sizeof(struct lruhash_bin)); 241238106Sdes if(!newa) { 242238106Sdes log_err("hash grow: malloc failed"); 243238106Sdes /* continue with smaller array. Though its slower. */ 244238106Sdes return; 245238106Sdes } 246238106Sdes bin_init(newa, table->size*2); 247238106Sdes newmask = (table->size_mask << 1) | 1; 248238106Sdes bin_split(table, newa, newmask); 249238106Sdes /* delete the old bins */ 250238106Sdes lock_unprotect(&table->lock, table->array); 251238106Sdes for(i=0; i<table->size; i++) { 252238106Sdes lock_quick_destroy(&table->array[i].lock); 253238106Sdes } 254238106Sdes free(table->array); 255238106Sdes 256238106Sdes table->size *= 2; 257238106Sdes table->size_mask = newmask; 258238106Sdes table->array = newa; 259238106Sdes lock_protect(&table->lock, table->array, 260238106Sdes table->size*sizeof(struct lruhash_bin)); 261238106Sdes return; 262238106Sdes} 263238106Sdes 264238106Sdesvoid 265238106Sdeslru_front(struct lruhash* table, struct lruhash_entry* entry) 266238106Sdes{ 267238106Sdes entry->lru_prev = NULL; 268238106Sdes entry->lru_next = table->lru_start; 269238106Sdes if(!table->lru_start) 270238106Sdes table->lru_end = entry; 271238106Sdes else table->lru_start->lru_prev = entry; 272238106Sdes table->lru_start = entry; 273238106Sdes} 274238106Sdes 275238106Sdesvoid 276238106Sdeslru_remove(struct lruhash* table, struct lruhash_entry* entry) 277238106Sdes{ 278238106Sdes if(entry->lru_prev) 279238106Sdes entry->lru_prev->lru_next = entry->lru_next; 280238106Sdes else table->lru_start = entry->lru_next; 281238106Sdes if(entry->lru_next) 282238106Sdes entry->lru_next->lru_prev = entry->lru_prev; 283238106Sdes else table->lru_end = entry->lru_prev; 284238106Sdes} 285238106Sdes 286238106Sdesvoid 287238106Sdeslru_touch(struct lruhash* table, struct lruhash_entry* entry) 288238106Sdes{ 289238106Sdes log_assert(table && entry); 290238106Sdes if(entry == table->lru_start) 291238106Sdes return; /* nothing to do */ 292238106Sdes /* remove from current lru position */ 293238106Sdes lru_remove(table, entry); 294238106Sdes /* add at front */ 295238106Sdes lru_front(table, entry); 296238106Sdes} 297238106Sdes 298238106Sdesvoid 299238106Sdeslruhash_insert(struct lruhash* table, hashvalue_t hash, 300238106Sdes struct lruhash_entry* entry, void* data, void* cb_arg) 301238106Sdes{ 302238106Sdes struct lruhash_bin* bin; 303238106Sdes struct lruhash_entry* found, *reclaimlist=NULL; 304238106Sdes size_t need_size; 305238106Sdes fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc)); 306238106Sdes fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc)); 307238106Sdes fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc)); 308238106Sdes fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc)); 309238106Sdes fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc)); 310238106Sdes need_size = table->sizefunc(entry->key, data); 311238106Sdes if(cb_arg == NULL) cb_arg = table->cb_arg; 312238106Sdes 313238106Sdes /* find bin */ 314238106Sdes lock_quick_lock(&table->lock); 315238106Sdes bin = &table->array[hash & table->size_mask]; 316238106Sdes lock_quick_lock(&bin->lock); 317238106Sdes 318238106Sdes /* see if entry exists already */ 319238106Sdes if(!(found=bin_find_entry(table, bin, hash, entry->key))) { 320238106Sdes /* if not: add to bin */ 321238106Sdes entry->overflow_next = bin->overflow_list; 322238106Sdes bin->overflow_list = entry; 323238106Sdes lru_front(table, entry); 324238106Sdes table->num++; 325238106Sdes table->space_used += need_size; 326238106Sdes } else { 327238106Sdes /* if so: update data - needs a writelock */ 328238106Sdes table->space_used += need_size - 329238106Sdes (*table->sizefunc)(found->key, found->data); 330238106Sdes (*table->delkeyfunc)(entry->key, cb_arg); 331238106Sdes lru_touch(table, found); 332238106Sdes lock_rw_wrlock(&found->lock); 333238106Sdes (*table->deldatafunc)(found->data, cb_arg); 334238106Sdes found->data = data; 335238106Sdes lock_rw_unlock(&found->lock); 336238106Sdes } 337238106Sdes lock_quick_unlock(&bin->lock); 338238106Sdes if(table->space_used > table->space_max) 339238106Sdes reclaim_space(table, &reclaimlist); 340238106Sdes if(table->num >= table->size) 341238106Sdes table_grow(table); 342238106Sdes lock_quick_unlock(&table->lock); 343238106Sdes 344238106Sdes /* finish reclaim if any (outside of critical region) */ 345238106Sdes while(reclaimlist) { 346238106Sdes struct lruhash_entry* n = reclaimlist->overflow_next; 347238106Sdes void* d = reclaimlist->data; 348238106Sdes (*table->delkeyfunc)(reclaimlist->key, cb_arg); 349238106Sdes (*table->deldatafunc)(d, cb_arg); 350238106Sdes reclaimlist = n; 351238106Sdes } 352238106Sdes} 353238106Sdes 354238106Sdesstruct lruhash_entry* 355238106Sdeslruhash_lookup(struct lruhash* table, hashvalue_t hash, void* key, int wr) 356238106Sdes{ 357238106Sdes struct lruhash_entry* entry; 358238106Sdes struct lruhash_bin* bin; 359238106Sdes fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc)); 360238106Sdes 361238106Sdes lock_quick_lock(&table->lock); 362238106Sdes bin = &table->array[hash & table->size_mask]; 363238106Sdes lock_quick_lock(&bin->lock); 364238106Sdes if((entry=bin_find_entry(table, bin, hash, key))) 365238106Sdes lru_touch(table, entry); 366238106Sdes lock_quick_unlock(&table->lock); 367238106Sdes 368238106Sdes if(entry) { 369238106Sdes if(wr) { lock_rw_wrlock(&entry->lock); } 370238106Sdes else { lock_rw_rdlock(&entry->lock); } 371238106Sdes } 372238106Sdes lock_quick_unlock(&bin->lock); 373238106Sdes return entry; 374238106Sdes} 375238106Sdes 376238106Sdesvoid 377238106Sdeslruhash_remove(struct lruhash* table, hashvalue_t hash, void* key) 378238106Sdes{ 379238106Sdes struct lruhash_entry* entry; 380238106Sdes struct lruhash_bin* bin; 381238106Sdes void *d; 382238106Sdes fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc)); 383238106Sdes fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc)); 384238106Sdes fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc)); 385238106Sdes fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc)); 386238106Sdes fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc)); 387238106Sdes 388238106Sdes lock_quick_lock(&table->lock); 389238106Sdes bin = &table->array[hash & table->size_mask]; 390238106Sdes lock_quick_lock(&bin->lock); 391238106Sdes if((entry=bin_find_entry(table, bin, hash, key))) { 392238106Sdes bin_overflow_remove(bin, entry); 393238106Sdes lru_remove(table, entry); 394238106Sdes } else { 395238106Sdes lock_quick_unlock(&table->lock); 396238106Sdes lock_quick_unlock(&bin->lock); 397238106Sdes return; 398238106Sdes } 399238106Sdes table->num--; 400238106Sdes table->space_used -= (*table->sizefunc)(entry->key, entry->data); 401238106Sdes lock_quick_unlock(&table->lock); 402238106Sdes lock_rw_wrlock(&entry->lock); 403238106Sdes if(table->markdelfunc) 404238106Sdes (*table->markdelfunc)(entry->key); 405238106Sdes lock_rw_unlock(&entry->lock); 406238106Sdes lock_quick_unlock(&bin->lock); 407238106Sdes /* finish removal */ 408238106Sdes d = entry->data; 409238106Sdes (*table->delkeyfunc)(entry->key, table->cb_arg); 410238106Sdes (*table->deldatafunc)(d, table->cb_arg); 411238106Sdes} 412238106Sdes 413238106Sdes/** clear bin, respecting locks, does not do space, LRU */ 414238106Sdesstatic void 415238106Sdesbin_clear(struct lruhash* table, struct lruhash_bin* bin) 416238106Sdes{ 417238106Sdes struct lruhash_entry* p, *np; 418238106Sdes void *d; 419238106Sdes lock_quick_lock(&bin->lock); 420238106Sdes p = bin->overflow_list; 421238106Sdes while(p) { 422238106Sdes lock_rw_wrlock(&p->lock); 423238106Sdes np = p->overflow_next; 424238106Sdes d = p->data; 425238106Sdes if(table->markdelfunc) 426238106Sdes (*table->markdelfunc)(p->key); 427238106Sdes lock_rw_unlock(&p->lock); 428238106Sdes (*table->delkeyfunc)(p->key, table->cb_arg); 429238106Sdes (*table->deldatafunc)(d, table->cb_arg); 430238106Sdes p = np; 431238106Sdes } 432238106Sdes bin->overflow_list = NULL; 433238106Sdes lock_quick_unlock(&bin->lock); 434238106Sdes} 435238106Sdes 436238106Sdesvoid 437238106Sdeslruhash_clear(struct lruhash* table) 438238106Sdes{ 439238106Sdes size_t i; 440238106Sdes if(!table) 441238106Sdes return; 442238106Sdes fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc)); 443238106Sdes fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc)); 444238106Sdes fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc)); 445238106Sdes 446238106Sdes lock_quick_lock(&table->lock); 447238106Sdes for(i=0; i<table->size; i++) { 448238106Sdes bin_clear(table, &table->array[i]); 449238106Sdes } 450238106Sdes table->lru_start = NULL; 451238106Sdes table->lru_end = NULL; 452238106Sdes table->num = 0; 453238106Sdes table->space_used = 0; 454238106Sdes lock_quick_unlock(&table->lock); 455238106Sdes} 456238106Sdes 457238106Sdesvoid 458238106Sdeslruhash_status(struct lruhash* table, const char* id, int extended) 459238106Sdes{ 460238106Sdes lock_quick_lock(&table->lock); 461238106Sdes log_info("%s: %u entries, memory %u / %u", 462238106Sdes id, (unsigned)table->num, (unsigned)table->space_used, 463238106Sdes (unsigned)table->space_max); 464238106Sdes log_info(" itemsize %u, array %u, mask %d", 465238106Sdes (unsigned)(table->num? table->space_used/table->num : 0), 466238106Sdes (unsigned)table->size, table->size_mask); 467238106Sdes if(extended) { 468238106Sdes size_t i; 469238106Sdes int min=(int)table->size*2, max=-2; 470238106Sdes for(i=0; i<table->size; i++) { 471238106Sdes int here = 0; 472238106Sdes struct lruhash_entry *en; 473238106Sdes lock_quick_lock(&table->array[i].lock); 474238106Sdes en = table->array[i].overflow_list; 475238106Sdes while(en) { 476238106Sdes here ++; 477238106Sdes en = en->overflow_next; 478238106Sdes } 479238106Sdes lock_quick_unlock(&table->array[i].lock); 480238106Sdes if(extended >= 2) 481238106Sdes log_info("bin[%d] %d", (int)i, here); 482238106Sdes if(here > max) max = here; 483238106Sdes if(here < min) min = here; 484238106Sdes } 485238106Sdes log_info(" bin min %d, avg %.2lf, max %d", min, 486238106Sdes (double)table->num/(double)table->size, max); 487238106Sdes } 488238106Sdes lock_quick_unlock(&table->lock); 489238106Sdes} 490238106Sdes 491238106Sdessize_t 492238106Sdeslruhash_get_mem(struct lruhash* table) 493238106Sdes{ 494238106Sdes size_t s; 495238106Sdes lock_quick_lock(&table->lock); 496238106Sdes s = sizeof(struct lruhash) + table->space_used; 497238106Sdes#ifdef USE_THREAD_DEBUG 498238106Sdes if(table->size != 0) { 499238106Sdes size_t i; 500238106Sdes for(i=0; i<table->size; i++) 501238106Sdes s += sizeof(struct lruhash_bin) + 502238106Sdes lock_get_mem(&table->array[i].lock); 503238106Sdes } 504238106Sdes#else /* no THREAD_DEBUG */ 505238106Sdes if(table->size != 0) 506238106Sdes s += (table->size)*(sizeof(struct lruhash_bin) + 507238106Sdes lock_get_mem(&table->array[0].lock)); 508238106Sdes#endif 509238106Sdes lock_quick_unlock(&table->lock); 510238106Sdes s += lock_get_mem(&table->lock); 511238106Sdes return s; 512238106Sdes} 513238106Sdes 514238106Sdesvoid 515238106Sdeslruhash_setmarkdel(struct lruhash* table, lruhash_markdelfunc_t md) 516238106Sdes{ 517238106Sdes lock_quick_lock(&table->lock); 518238106Sdes table->markdelfunc = md; 519238106Sdes lock_quick_unlock(&table->lock); 520238106Sdes} 521238106Sdes 522238106Sdesvoid 523238106Sdeslruhash_traverse(struct lruhash* h, int wr, 524238106Sdes void (*func)(struct lruhash_entry*, void*), void* arg) 525238106Sdes{ 526238106Sdes size_t i; 527238106Sdes struct lruhash_entry* e; 528238106Sdes 529238106Sdes lock_quick_lock(&h->lock); 530238106Sdes for(i=0; i<h->size; i++) { 531238106Sdes lock_quick_lock(&h->array[i].lock); 532238106Sdes for(e = h->array[i].overflow_list; e; e = e->overflow_next) { 533238106Sdes if(wr) { 534238106Sdes lock_rw_wrlock(&e->lock); 535238106Sdes } else { 536238106Sdes lock_rw_rdlock(&e->lock); 537238106Sdes } 538238106Sdes (*func)(e, arg); 539238106Sdes lock_rw_unlock(&e->lock); 540238106Sdes } 541238106Sdes lock_quick_unlock(&h->array[i].lock); 542238106Sdes } 543238106Sdes lock_quick_unlock(&h->lock); 544238106Sdes} 545