Home | History | Annotate | Line # | Download | only in kern
vfs_dirhash.c revision 1.5 
      1 /* $NetBSD: vfs_dirhash.c,v 1.5 2008/10/31 15:01:12 reinoud Exp $ */
      2 
      3 /*
      4  * Copyright (c) 2008 Reinoud Zandijk
      5  * All rights reserved.
      6  *
      7  * Redistribution and use in source and binary forms, with or without
      8  * modification, are permitted provided that the following conditions
      9  * are met:
     10  * 1. Redistributions of source code must retain the above copyright
     11  *    notice, this list of conditions and the following disclaimer.
     12  * 2. Redistributions in binary form must reproduce the above copyright
     13  *    notice, this list of conditions and the following disclaimer in the
     14  *    documentation and/or other materials provided with the distribution.
     15  *
     16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     26  *
     27  */
     28 
     29 
     30 #include <sys/cdefs.h>
     31 __KERNEL_RCSID(0, "$NetBSD: vfs_dirhash.c,v 1.5 2008/10/31 15:01:12 reinoud Exp $");
     32 
     33 /* CLEAN UP! */
     34 #include <sys/param.h>
     35 #include <sys/kernel.h>
     36 #include <sys/buf.h>
     37 #include <sys/dirent.h>
     38 #include <sys/hash.h>
     39 #include <sys/mutex.h>
     40 #include <sys/pool.h>
     41 #include <sys/queue.h>
     42 #include <sys/vnode.h>
     43 #include <sys/sysctl.h>
     44 
     45 #include <sys/dirhash.h>
     46 
     47 #if 1
     48 #	define DPRINTF(a) ;
     49 #else
     50 #	define DPRINTF(a) printf(a);
     51 #endif
     52 
     53 
     54 static struct sysctllog *sysctl_log;
     55 static struct pool dirhash_pool;
     56 static struct pool dirhash_entry_pool;
     57 
     58 static kmutex_t dirhashmutex;
     59 static uint32_t maxdirhashsize = DIRHASH_SIZE;
     60 static uint32_t dirhashsize    = 0;
     61 static TAILQ_HEAD(_dirhash, dirhash) dirhash_queue;
     62 
     63 
     64 void
     65 dirhash_init(void)
     66 {
     67 	const struct sysctlnode *rnode, *cnode;
     68 	size_t sz;
     69 	uint32_t max_entries;
     70 
     71 	/* initialise dirhash queue */
     72 	TAILQ_INIT(&dirhash_queue);
     73 
     74 	/* init dirhash pools */
     75 	sz = sizeof(struct dirhash);
     76 	pool_init(&dirhash_pool, sz, 0, 0, 0,
     77 		"dirhpl", NULL, IPL_NONE);
     78 
     79 	sz = sizeof(struct dirhash_entry);
     80 	pool_init(&dirhash_entry_pool, sz, 0, 0, 0,
     81 		"dirhepl", NULL, IPL_NONE);
     82 
     83 	mutex_init(&dirhashmutex, MUTEX_DEFAULT, IPL_NONE);
     84 	max_entries = maxdirhashsize / sz;
     85 	pool_sethiwat(&dirhash_entry_pool, max_entries);
     86 	dirhashsize = 0;
     87 
     88 	/* create sysctl knobs and dials */
     89 	sysctl_log = NULL;
     90 	sysctl_createv(&sysctl_log, 0, NULL, &rnode,
     91 		       CTLFLAG_PERMANENT,
     92 		       CTLTYPE_NODE, "dirhash", NULL,
     93 		       NULL, 0, NULL, 0,
     94 		       CTL_VFS, VFS_GENERIC, CTL_CREATE, CTL_EOL);
     95 	sysctl_createv(&sysctl_log, 0, &rnode, &cnode,
     96 		       CTLFLAG_PERMANENT,
     97 		       CTLTYPE_INT, "memused",
     98 		       SYSCTL_DESCR("current dirhash memory usage"),
     99 		       NULL, 0, &dirhashsize, 0,
    100 		       CTL_CREATE, CTL_EOL);
    101 	sysctl_createv(&sysctl_log, 0, &rnode, &cnode,
    102 		       CTLFLAG_PERMANENT | CTLFLAG_READWRITE,
    103 		       CTLTYPE_INT, "maxmem",
    104 		       SYSCTL_DESCR("maximum dirhash memory usage"),
    105 		       NULL, 0, &maxdirhashsize, 0,
    106 		       CTL_CREATE, CTL_EOL);
    107 }
    108 
    109 
    110 #if 0
    111 void
    112 dirhash_finish(void)
    113 {
    114 	pool_destroy(&dirhash_pool);
    115 	pool_destroy(&dirhash_entry_pool);
    116 
    117 	mutex_destroy(&dirhashmutex);
    118 
    119 	/* sysctl_teardown(&sysctl_log); */
    120 }
    121 #endif
    122 
    123 
    124 /*
    125  * generic dirhash implementation
    126  */
    127 
    128 void
    129 dirhash_purge_entries(struct dirhash *dirh)
    130 {
    131 	struct dirhash_entry *dirh_e;
    132 	uint32_t hashline;
    133 
    134 	if (dirh == NULL)
    135 		return;
    136 
    137 	if (dirh->size == 0)
    138 		return;
    139 
    140 	for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
    141 		dirh_e = LIST_FIRST(&dirh->entries[hashline]);
    142 		while (dirh_e) {
    143 			LIST_REMOVE(dirh_e, next);
    144 			pool_put(&dirhash_entry_pool, dirh_e);
    145 			dirh_e = LIST_FIRST(&dirh->entries[hashline]);
    146 		}
    147 	}
    148 	dirh_e = LIST_FIRST(&dirh->free_entries);
    149 
    150 	while (dirh_e) {
    151 		LIST_REMOVE(dirh_e, next);
    152 		pool_put(&dirhash_entry_pool, dirh_e);
    153 		dirh_e = LIST_FIRST(&dirh->entries[hashline]);
    154 	}
    155 
    156 	dirh->flags &= ~DIRH_COMPLETE;
    157 	dirh->flags |=  DIRH_PURGED;
    158 
    159 	dirhashsize -= dirh->size;
    160 	dirh->size = 0;
    161 }
    162 
    163 
    164 void
    165 dirhash_purge(struct dirhash **dirhp)
    166 {
    167 	struct dirhash *dirh = *dirhp;
    168 
    169 	if (dirh == NULL)
    170 		return;
    171 
    172 	mutex_enter(&dirhashmutex);
    173 	dirhash_purge_entries(dirh);
    174 	TAILQ_REMOVE(&dirhash_queue, dirh, next);
    175 	mutex_exit(&dirhashmutex);
    176 
    177 	pool_put(&dirhash_pool, dirh);
    178 	*dirhp = NULL;
    179 }
    180 
    181 
    182 void
    183 dirhash_get(struct dirhash **dirhp)
    184 {
    185 	struct dirhash *dirh;
    186 	uint32_t hashline;
    187 
    188 
    189 	/* if no dirhash was given, allocate one */
    190 	dirh = *dirhp;
    191 	if (dirh == NULL) {
    192 		dirh = pool_get(&dirhash_pool, PR_WAITOK);
    193 		memset(dirh, 0, sizeof(struct dirhash));
    194 		for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
    195 			LIST_INIT(&dirh->entries[hashline]);
    196 		}
    197 	}
    198 
    199 	/* implement LRU on the dirhash queue */
    200 	mutex_enter(&dirhashmutex);
    201 	if (*dirhp) {
    202 		/* remove from queue to be requeued */
    203 		TAILQ_REMOVE(&dirhash_queue, dirh, next);
    204 	}
    205 	dirh->refcnt++;
    206 	TAILQ_INSERT_HEAD(&dirhash_queue, dirh, next);
    207 	mutex_exit(&dirhashmutex);
    208 
    209 	*dirhp = dirh;
    210 }
    211 
    212 
    213 void
    214 dirhash_put(struct dirhash *dirh)
    215 {
    216 
    217 	mutex_enter(&dirhashmutex);
    218 	dirh->refcnt--;
    219 	mutex_exit(&dirhashmutex);
    220 }
    221 
    222 
    223 void
    224 dirhash_enter(struct dirhash *dirh,
    225 	struct dirent *dirent, uint64_t offset, uint32_t entry_size, int new)
    226 {
    227 	struct dirhash *del_dirh, *prev_dirh;
    228 	struct dirhash_entry *dirh_e;
    229 	uint32_t hashvalue, hashline;
    230 	int entrysize;
    231 
    232 	/* make sure we have a dirhash to work on */
    233 	KASSERT(dirh);
    234 	KASSERT(dirh->refcnt > 0);
    235 
    236 	/* are we trying to re-enter an entry? */
    237 	if (!new && (dirh->flags & DIRH_COMPLETE))
    238 		return;
    239 
    240 	/* calculate our hash */
    241 	hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, HASH32_STR_INIT);
    242 	hashline  = hashvalue & DIRHASH_HASHMASK;
    243 
    244 	/* lookup and insert entry if not there yet */
    245 	LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
    246 		/* check for hash collision */
    247 		if (dirh_e->hashvalue != hashvalue)
    248 			continue;
    249 		if (dirh_e->offset != offset)
    250 			continue;
    251 		/* got it already */
    252 		KASSERT(dirh_e->d_namlen == dirent->d_namlen);
    253 		KASSERT(dirh_e->entry_size == entry_size);
    254 		return;
    255 	}
    256 
    257 	DPRINTF(("dirhash enter %"PRIu64", %d, %d for `%*.*s`\n",
    258 		offset, entry_size, dirent->d_namlen,
    259 		dirent->d_namlen, dirent->d_namlen, dirent->d_name));
    260 
    261 	/* check if entry is in free space list */
    262 	LIST_FOREACH(dirh_e, &dirh->free_entries, next) {
    263 		if (dirh_e->offset == offset) {
    264 			DPRINTF(("\tremoving free entry\n"));
    265 			LIST_REMOVE(dirh_e, next);
    266 			break;
    267 		}
    268 	}
    269 
    270 	/* ensure we are not passing the dirhash limit */
    271 	entrysize = sizeof(struct dirhash_entry);
    272 	if (dirhashsize + entrysize > maxdirhashsize) {
    273 		del_dirh = TAILQ_LAST(&dirhash_queue, _dirhash);
    274 		KASSERT(del_dirh);
    275 		while (dirhashsize + entrysize > maxdirhashsize) {
    276 			/* no use trying to delete myself */
    277 			if (del_dirh == dirh)
    278 				break;
    279 			prev_dirh = TAILQ_PREV(del_dirh, _dirhash, next);
    280 			if (del_dirh->refcnt == 0)
    281 				dirhash_purge_entries(del_dirh);
    282 			del_dirh = prev_dirh;
    283 		}
    284 	}
    285 
    286 	/* add to the hashline */
    287 	dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK);
    288 	memset(dirh_e, 0, sizeof(struct dirhash_entry));
    289 
    290 	dirh_e->hashvalue = hashvalue;
    291 	dirh_e->offset    = offset;
    292 	dirh_e->d_namlen  = dirent->d_namlen;
    293 	dirh_e->entry_size  = entry_size;
    294 
    295 	dirh->size  += sizeof(struct dirhash_entry);
    296 	dirhashsize += sizeof(struct dirhash_entry);
    297 	LIST_INSERT_HEAD(&dirh->entries[hashline], dirh_e, next);
    298 }
    299 
    300 
    301 void
    302 dirhash_enter_freed(struct dirhash *dirh, uint64_t offset,
    303 	uint32_t entry_size)
    304 {
    305 	struct dirhash_entry *dirh_e;
    306 
    307 	/* make sure we have a dirhash to work on */
    308 	KASSERT(dirh);
    309 	KASSERT(dirh->refcnt > 0);
    310 
    311 #ifdef DEBUG
    312 	/* check for double entry of free space */
    313 	LIST_FOREACH(dirh_e, &dirh->free_entries, next) {
    314 		KASSERT(dirh_e->offset != offset);
    315 	}
    316 #endif
    317 
    318 	DPRINTF(("dirhash enter FREED %"PRIu64", %d\n",
    319 		offset, entry_size));
    320 	dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK);
    321 	memset(dirh_e, 0, sizeof(struct dirhash_entry));
    322 
    323 	dirh_e->hashvalue = 0;		/* not relevant */
    324 	dirh_e->offset    = offset;
    325 	dirh_e->d_namlen  = 0;		/* not relevant */
    326 	dirh_e->entry_size  = entry_size;
    327 
    328 	/* XXX it might be preferable to append them at the tail */
    329 	LIST_INSERT_HEAD(&dirh->free_entries, dirh_e, next);
    330 	dirh->size  += sizeof(struct dirhash_entry);
    331 	dirhashsize += sizeof(struct dirhash_entry);
    332 }
    333 
    334 
    335 void
    336 dirhash_remove(struct dirhash *dirh, struct dirent *dirent,
    337 	uint64_t offset, uint32_t entry_size)
    338 {
    339 	struct dirhash_entry *dirh_e;
    340 	uint32_t hashvalue, hashline;
    341 
    342 	DPRINTF(("dirhash remove %"PRIu64", %d for `%*.*s`\n",
    343 		offset, entry_size,
    344 		dirent->d_namlen, dirent->d_namlen, dirent->d_name));
    345 
    346 	/* make sure we have a dirhash to work on */
    347 	KASSERT(dirh);
    348 	KASSERT(dirh->refcnt > 0);
    349 
    350 	/* calculate our hash */
    351 	hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen, HASH32_STR_INIT);
    352 	hashline  = hashvalue & DIRHASH_HASHMASK;
    353 
    354 	/* lookup entry */
    355 	LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
    356 		/* check for hash collision */
    357 		if (dirh_e->hashvalue != hashvalue)
    358 			continue;
    359 		if (dirh_e->offset != offset)
    360 			continue;
    361 
    362 		/* got it! */
    363 		KASSERT(dirh_e->d_namlen == dirent->d_namlen);
    364 		KASSERT(dirh_e->entry_size == entry_size);
    365 		LIST_REMOVE(dirh_e, next);
    366 		dirh->size -= sizeof(struct dirhash_entry);
    367 		dirhashsize -= sizeof(struct dirhash_entry);
    368 
    369 		dirhash_enter_freed(dirh, offset, entry_size);
    370 		return;
    371 	}
    372 
    373 	/* not found! */
    374 	panic("dirhash_remove couldn't find entry in hash table\n");
    375 }
    376 
    377 
    378 /*
    379  * BUGALERT: don't use result longer than needed, never past the node lock.
    380  * Call with NULL *result initially and it will return nonzero if again.
    381  */
    382 int
    383 dirhash_lookup(struct dirhash *dirh, const char *d_name, int d_namlen,
    384 	struct dirhash_entry **result)
    385 {
    386 	struct dirhash_entry *dirh_e;
    387 	uint32_t hashvalue, hashline;
    388 
    389 	/* vnode should be locked */
    390 	//KASSERT(VOP_ISLOCKED(dirh->vnode));
    391 
    392 	/* make sure we have a dirhash to work on */
    393 	KASSERT(dirh);
    394 	KASSERT(dirh->refcnt > 0);
    395 
    396 	/* start where we were */
    397 	if (*result) {
    398 		dirh_e = *result;
    399 
    400 		/* retrieve information to avoid recalculation and advance */
    401 		hashvalue = dirh_e->hashvalue;
    402 		dirh_e = LIST_NEXT(*result, next);
    403 	} else {
    404 		/* calculate our hash and lookup all entries in hashline */
    405 		hashvalue = hash32_strn(d_name, d_namlen, HASH32_STR_INIT);
    406 		hashline  = hashvalue & DIRHASH_HASHMASK;
    407 		dirh_e = LIST_FIRST(&dirh->entries[hashline]);
    408 	}
    409 
    410 	for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) {
    411 		/* check for hash collision */
    412 		if (dirh_e->hashvalue != hashvalue)
    413 			continue;
    414 		if (dirh_e->d_namlen != d_namlen)
    415 			continue;
    416 		/* might have an entry in the cache */
    417 		*result = dirh_e;
    418 		return 1;
    419 	}
    420 
    421 	*result = NULL;
    422 	return 0;
    423 }
    424 
    425 
    426 /*
    427  * BUGALERT: don't use result longer than needed, never past the node lock.
    428  * Call with NULL *result initially and it will return nonzero if again.
    429  */
    430 
    431 int
    432 dirhash_lookup_freed(struct dirhash *dirh, uint32_t min_entrysize,
    433 	struct dirhash_entry **result)
    434 {
    435 	struct dirhash_entry *dirh_e;
    436 
    437 	//KASSERT(VOP_ISLOCKED(dirh->vnode));
    438 
    439 	/* make sure we have a dirhash to work on */
    440 	KASSERT(dirh);
    441 	KASSERT(dirh->refcnt > 0);
    442 
    443 	/* start where we were */
    444 	if (*result) {
    445 		dirh_e = LIST_NEXT(*result, next);
    446 	} else {
    447 		/* lookup all entries that match */
    448 		dirh_e = LIST_FIRST(&dirh->free_entries);
    449 	}
    450 
    451 	for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) {
    452 		/* check for minimum size */
    453 		if (dirh_e->entry_size < min_entrysize)
    454 			continue;
    455 		/* might be a candidate */
    456 		*result = dirh_e;
    457 		return 1;
    458 	}
    459 
    460 	*result = NULL;
    461 	return 0;
    462 }
    463