/usr/src/sbin/unwind/libunbound/util/storage/lruhash.c

Bug Summary

File:	src/sbin/unwind/libunbound/util/storage/lruhash.c
Warning:	line 201, column 25 Access to field 'lru_next' results in a dereference of a null pointer (loaded from field 'lru_prev')

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.4 -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name lruhash.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/sbin/unwind/obj -resource-dir /usr/local/llvm16/lib/clang/16 -I /usr/src/sbin/unwind -I /usr/src/sbin/unwind -I /usr/src/sbin/unwind/libunbound/libunbound -I /usr/src/sbin/unwind/libunbound -internal-isystem /usr/local/llvm16/lib/clang/16/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/sbin/unwind/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fcf-protection=branch -fno-jump-tables -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/scan/2024-01-11-140451-98009-1 -x c /usr/src/sbin/unwind/libunbound/util/storage/lruhash.c

1/*
* util/storage/lruhash.c - hashtable, hash function, LRU keeping.
*
* Copyright (c) 2007, NLnet Labs. All rights reserved.
*
* This software is open source.
* 
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 
* Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* 
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
* 
* Neither the name of the NLNET LABS nor the names of its contributors may
* be used to endorse or promote products derived from this software without
* specific prior written permission.
* 
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

36/**
* \file
*
* This file contains a hashtable with LRU keeping of entries.
*
*/

43#include "config.h"
44#include "util/storage/lruhash.h"
45#include "util/fptr_wlist.h"

47void
48bin_init(struct lruhash_bin* array, size_t size)
49{
size_t i;
51#ifdef THREADS_DISABLED1
(void)array;
53#endif
for(i=0; i<size; i++) {
lock_quick_init(&array[i].lock);
lock_protect(&array[i].lock, &array[i], 
	sizeof(struct lruhash_bin));
}
59}

61struct lruhash* 
62lruhash_create(size_t start_size, size_t maxmem,
lruhash_sizefunc_type sizefunc, lruhash_compfunc_type compfunc,
lruhash_delkeyfunc_type delkeyfunc,
lruhash_deldatafunc_type deldatafunc, void* arg)
66{
struct lruhash* table = (struct lruhash*)calloc(1, 
sizeof(struct lruhash));
if(!table)
return NULL((void *)0);
lock_quick_init(&table->lock);
table->sizefunc = sizefunc;
table->compfunc = compfunc;
table->delkeyfunc = delkeyfunc;
table->deldatafunc = deldatafunc;
table->cb_arg = arg;
table->size = start_size;
table->size_mask = (int)(start_size-1);
table->lru_start = NULL((void *)0);
table->lru_end = NULL((void *)0);
table->num = 0;
table->space_used = 0;
table->space_max = maxmem;
table->max_collisions = 0;
table->array = calloc(table->size, sizeof(struct lruhash_bin));
if(!table->array) {
lock_quick_destroy(&table->lock);
free(table);
return NULL((void *)0);
}
bin_init(table->array, table->size);
lock_protect(&table->lock, table, sizeof(*table));
lock_protect(&table->lock, table->array, 
table->size*sizeof(struct lruhash_bin));
return table;
96}

98void 
99bin_delete(struct lruhash* table, struct lruhash_bin* bin)
100{
struct lruhash_entry* p, *np;
void *d;
if(!bin)
return;
lock_quick_destroy(&bin->lock);
p = bin->overflow_list;
bin->overflow_list = NULL((void *)0);
while(p) {
np = p->overflow_next;
d = p->data;
(*table->delkeyfunc)(p->key, table->cb_arg);
(*table->deldatafunc)(d, table->cb_arg);
p = np;
}
115}

117void 
118bin_split(struct lruhash* table, struct lruhash_bin* newa, 
int newmask)
120{
size_t i;
struct lruhash_entry *p, *np;
struct lruhash_bin* newbin;
/* move entries to new table. Notice that since hash x is mapped to
* bin x & mask, and new mask uses one more bit, so all entries in
* one bin will go into the old bin or bin | newbit */
127#ifndef THREADS_DISABLED1
int newbit = newmask - table->size_mask;
129#endif
/* so, really, this task could also be threaded, per bin. */
/* LRU list is not changed */
for(i=0; i<table->size; i++)
{
lock_quick_lock(&table->array[i].lock);
p = table->array[i].overflow_list;
/* lock both destination bins */
lock_quick_lock(&newa[i].lock);
lock_quick_lock(&newa[newbit|i].lock);
while(p) {
	np = p->overflow_next;
	/* link into correct new bin */
	newbin = &newa[p->hash & newmask];
	p->overflow_next = newbin->overflow_list;
	newbin->overflow_list = p;
	p=np;
}
lock_quick_unlock(&newa[i].lock);
lock_quick_unlock(&newa[newbit|i].lock);
lock_quick_unlock(&table->array[i].lock);
}
151}

153void 
154lruhash_delete(struct lruhash* table)
155{
size_t i;
if(!table)
return;
/* delete lock on hashtable to force check its OK */
lock_quick_destroy(&table->lock);
for(i=0; i<table->size; i++)
bin_delete(table, &table->array[i]);
free(table->array);
free(table);
165}

167void 
168bin_overflow_remove(struct lruhash_bin* bin, struct lruhash_entry* entry)
169{
struct lruhash_entry* p = bin->overflow_list;
struct lruhash_entry** prevp = &bin->overflow_list;
while(p) {
if(p == entry) {
	*prevp = p->overflow_next;
	return;
}
prevp = &p->overflow_next;
p = p->overflow_next;
}
180}

182void 
183reclaim_space(struct lruhash* table, struct lruhash_entry** list)
184{
struct lruhash_entry* d;
struct lruhash_bin* bin;
log_assert(table);
/* does not delete MRU entry, so table will not be empty. */
while(table->num > 1 && table->space_used15.1
Field 'space_used' is > field 'space_max'
 > table->space_max) {
15
←
Assuming field 'num' is > 1→
16
←
Loop condition is true.  Entering loop body→
/* notice that since we hold the hashtable lock, nobody
   can change the lru chain. So it cannot be deleted underneath
   us. We still need the hashbin and entry write lock to make 
   sure we flush all users away from the entry. 
   which is unlikely, since it is LRU, if someone got a rdlock
   it would be moved to front, but to be sure. */
d = table->lru_end;
/* specialised, delete from end of double linked list,
   and we know num>1, so there is a previous lru entry. */
log_assert(d && d->lru_prev);
table->lru_end = d->lru_prev;
d->lru_prev->lru_next = NULL((void *)0);
17
←
Access to field 'lru_next' results in a dereference of a null pointer (loaded from field 'lru_prev')
/* schedule entry for deletion */
bin = &table->array[d->hash & table->size_mask];
table->num --;
lock_quick_lock(&bin->lock);
bin_overflow_remove(bin, d);
d->overflow_next = *list;
*list = d;
lock_rw_wrlock(&d->lock);
table->space_used -= table->sizefunc(d->key, d->data);
if(table->markdelfunc)
	(*table->markdelfunc)(d->key);
lock_rw_unlock(&d->lock);
lock_quick_unlock(&bin->lock);
}
216}

218struct lruhash_entry* 
219bin_find_entry(struct lruhash* table, 
struct lruhash_bin* bin, hashvalue_type hash, void* key, size_t* collisions)
221{
size_t c = 0;
struct lruhash_entry* p = bin->overflow_list;
while(p) {
if(p->hash == hash && table->compfunc(p->key, key) == 0)
	break;
c++;
p = p->overflow_next;
}
if (collisions != NULL((void *)0))
*collisions = c;
return p;
233}

235void 
236table_grow(struct lruhash* table)
237{
struct lruhash_bin* newa;
int newmask;
size_t i;
if(table->size_mask == (int)(((size_t)-1)>>1)) {
log_err("hash array malloc: size_t too small");
return;
}
/* try to allocate new array, if not fail */
newa = calloc(table->size*2, sizeof(struct lruhash_bin));
if(!newa) {
log_err("hash grow: malloc failed");
/* continue with smaller array. Though its slower. */
return;
}
bin_init(newa, table->size*2);
newmask = (table->size_mask << 1) | 1;
bin_split(table, newa, newmask);
/* delete the old bins */
lock_unprotect(&table->lock, table->array);
for(i=0; i<table->size; i++) {
lock_quick_destroy(&table->array[i].lock);
}
free(table->array);

table->size *= 2;
table->size_mask = newmask;
table->array = newa;
lock_protect(&table->lock, table->array, 
table->size*sizeof(struct lruhash_bin));
return;
268}

270void 
271lru_front(struct lruhash* table, struct lruhash_entry* entry)
272{
entry->lru_prev = NULL((void *)0);
6
←
Null pointer value stored to field 'lru_prev'→
entry->lru_next = table->lru_start;
if(!table->lru_start)
7
←
Assuming field 'lru_start' is null→
8
←
Taking true branch→
table->lru_end = entry;
else	table->lru_start->lru_prev = entry;
table->lru_start = entry;
279}

281void 
282lru_remove(struct lruhash* table, struct lruhash_entry* entry)
283{
if(entry->lru_prev)
entry->lru_prev->lru_next = entry->lru_next;
else	table->lru_start = entry->lru_next;
if(entry->lru_next)
entry->lru_next->lru_prev = entry->lru_prev;
else	table->lru_end = entry->lru_prev;
290}

292void 
293lru_touch(struct lruhash* table, struct lruhash_entry* entry)
294{
log_assert(table && entry);
if(entry == table->lru_start)
return; /* nothing to do */
/* remove from current lru position */
lru_remove(table, entry);
/* add at front */
lru_front(table, entry);
302}

304void 
305lruhash_insert(struct lruhash* table, hashvalue_type hash,
      struct lruhash_entry* entry, void* data, void* cb_arg)
307{
struct lruhash_bin* bin;
struct lruhash_entry* found, *reclaimlist=NULL((void *)0);
size_t need_size;
size_t collisions;
fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
need_size = table->sizefunc(entry->key, data);
if(cb_arg == NULL((void *)0)) cb_arg = table->cb_arg;

/* find bin */
lock_quick_lock(&table->lock);
bin = &table->array[hash & table->size_mask];
lock_quick_lock(&bin->lock);

/* see if entry exists already */
if(!(found=bin_find_entry(table, bin, hash, entry->key, &collisions))) {
/* if not: add to bin */
entry->overflow_next = bin->overflow_list;
bin->overflow_list = entry;
lru_front(table, entry);
table->num++;
if (table->max_collisions < collisions)
	table->max_collisions = collisions;
table->space_used += need_size;
} else {
/* if so: update data - needs a writelock */
table->space_used += need_size -
	(*table->sizefunc)(found->key, found->data);
(*table->delkeyfunc)(entry->key, cb_arg);
lru_touch(table, found);
lock_rw_wrlock(&found->lock);
(*table->deldatafunc)(found->data, cb_arg);
found->data = data;
lock_rw_unlock(&found->lock);
}
lock_quick_unlock(&bin->lock);
if(table->space_used > table->space_max)
reclaim_space(table, &reclaimlist);
if(table->num >= table->size)
table_grow(table);
lock_quick_unlock(&table->lock);

/* finish reclaim if any (outside of critical region) */
while(reclaimlist) {
struct lruhash_entry* n = reclaimlist->overflow_next;
void* d = reclaimlist->data;
(*table->delkeyfunc)(reclaimlist->key, cb_arg);
(*table->deldatafunc)(d, cb_arg);
reclaimlist = n;
}
361}

363struct lruhash_entry* 
364lruhash_lookup(struct lruhash* table, hashvalue_type hash, void* key, int wr)
365{
struct lruhash_entry* entry;
struct lruhash_bin* bin;
fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));

lock_quick_lock(&table->lock);
bin = &table->array[hash & table->size_mask];
lock_quick_lock(&bin->lock);
if((entry=bin_find_entry(table, bin, hash, key, NULL((void *)0))))
lru_touch(table, entry);
lock_quick_unlock(&table->lock);

if(entry) {
if(wr)	{ lock_rw_wrlock(&entry->lock); }
else	{ lock_rw_rdlock(&entry->lock); }
}
lock_quick_unlock(&bin->lock);
return entry;
383}

385void 
386lruhash_remove(struct lruhash* table, hashvalue_type hash, void* key)
387{
struct lruhash_entry* entry;
struct lruhash_bin* bin;
void *d;
fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));

lock_quick_lock(&table->lock);
bin = &table->array[hash & table->size_mask];
lock_quick_lock(&bin->lock);
if((entry=bin_find_entry(table, bin, hash, key, NULL((void *)0)))) {
bin_overflow_remove(bin, entry);
lru_remove(table, entry);
} else {
lock_quick_unlock(&table->lock);
lock_quick_unlock(&bin->lock);
return;
}
table->num--;
table->space_used -= (*table->sizefunc)(entry->key, entry->data);	
lock_rw_wrlock(&entry->lock);
if(table->markdelfunc)
(*table->markdelfunc)(entry->key);
lock_rw_unlock(&entry->lock);
lock_quick_unlock(&bin->lock);
lock_quick_unlock(&table->lock);
/* finish removal */
d = entry->data;
(*table->delkeyfunc)(entry->key, table->cb_arg);
(*table->deldatafunc)(d, table->cb_arg);
420}

422/** clear bin, respecting locks, does not do space, LRU */
423static void
424bin_clear(struct lruhash* table, struct lruhash_bin* bin)
425{
struct lruhash_entry* p, *np;
void *d;
lock_quick_lock(&bin->lock);
p = bin->overflow_list; 
while(p) {
lock_rw_wrlock(&p->lock);
np = p->overflow_next;
d = p->data;
if(table->markdelfunc)
	(*table->markdelfunc)(p->key);
lock_rw_unlock(&p->lock);
(*table->delkeyfunc)(p->key, table->cb_arg);
(*table->deldatafunc)(d, table->cb_arg);
p = np;
}
bin->overflow_list = NULL((void *)0);
lock_quick_unlock(&bin->lock);
443}

445void
446lruhash_clear(struct lruhash* table)
447{
size_t i;
if(!table)
return;
fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));

lock_quick_lock(&table->lock);
for(i=0; i<table->size; i++) {
bin_clear(table, &table->array[i]);
}
table->lru_start = NULL((void *)0);
table->lru_end = NULL((void *)0);
table->num = 0;
table->space_used = 0;
lock_quick_unlock(&table->lock);
464}

466void 
467lruhash_status(struct lruhash* table, const char* id, int extended)
468{
lock_quick_lock(&table->lock);
log_info("%s: %u entries, memory %u / %u",
id, (unsigned)table->num, (unsigned)table->space_used,
(unsigned)table->space_max);
log_info("  itemsize %u, array %u, mask %d",
(unsigned)(table->num? table->space_used/table->num : 0),
(unsigned)table->size, table->size_mask);
if(extended) {
size_t i;
int min=(int)table->size*2, max=-2;
for(i=0; i<table->size; i++) {
	int here = 0;
	struct lruhash_entry *en;
	lock_quick_lock(&table->array[i].lock);
	en = table->array[i].overflow_list;
	while(en) {
		here ++;
		en = en->overflow_next;
	}
	lock_quick_unlock(&table->array[i].lock);
	if(extended >= 2)
		log_info("bin[%d] %d", (int)i, here);
	if(here > max) max = here;
	if(here < min) min = here;
}
log_info("  bin min %d, avg %.2lf, max %d", min, 
	(double)table->num/(double)table->size, max);
}
lock_quick_unlock(&table->lock);
498}

500size_t
501lruhash_get_mem(struct lruhash* table)
502{
size_t s;
lock_quick_lock(&table->lock);
s = sizeof(struct lruhash) + table->space_used;
506#ifdef USE_THREAD_DEBUG
if(table->size != 0) {
size_t i;
for(i=0; i<table->size; i++)
	s += sizeof(struct lruhash_bin) + 
		lock_get_mem(&table->array[i].lock)(0);
}
513#else /* no THREAD_DEBUG */
if(table->size != 0)
s += (table->size)*(sizeof(struct lruhash_bin) + 
	lock_get_mem(&table->array[0].lock)(0));
517#endif
lock_quick_unlock(&table->lock);
s += lock_get_mem(&table->lock)(0);
return s;
521}

523void 
524lruhash_setmarkdel(struct lruhash* table, lruhash_markdelfunc_type md)
525{
lock_quick_lock(&table->lock);
table->markdelfunc = md;
lock_quick_unlock(&table->lock);
529}

531void 
532lruhash_traverse(struct lruhash* h, int wr, 
void (*func)(struct lruhash_entry*, void*), void* arg)
534{
size_t i;
struct lruhash_entry* e;

lock_quick_lock(&h->lock);
for(i=0; i<h->size; i++) {
lock_quick_lock(&h->array[i].lock);
for(e = h->array[i].overflow_list; e; e = e->overflow_next) {
	if(wr) {
		lock_rw_wrlock(&e->lock);
	} else {
		lock_rw_rdlock(&e->lock);
	}
	(*func)(e, arg);
	lock_rw_unlock(&e->lock);
}
lock_quick_unlock(&h->array[i].lock);
}
lock_quick_unlock(&h->lock);
553}

555/*
* Demote: the opposite of touch, move an entry to the bottom
* of the LRU pile.
*/

560void
561lru_demote(struct lruhash* table, struct lruhash_entry* entry)
562{
log_assert(table && entry);
if (entry == table->lru_end)
return; /* nothing to do */
/* remove from current lru position */
lru_remove(table, entry);
/* add at end */
entry->lru_next = NULL((void *)0);
entry->lru_prev = table->lru_end;

if (table->lru_end == NULL((void *)0))
{
table->lru_start = entry;
}
else
{
table->lru_end->lru_next = entry;
}
table->lru_end = entry;
581}

583struct lruhash_entry*
584lruhash_insert_or_retrieve(struct lruhash* table, hashvalue_type hash,
struct lruhash_entry* entry, void* data, void* cb_arg)
586{
struct lruhash_bin* bin;
struct lruhash_entry* found, *reclaimlist = NULL((void *)0);
size_t need_size;
size_t collisions;
fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
need_size = table->sizefunc(entry->key, data);
if (cb_arg == NULL((void *)0)) cb_arg = table->cb_arg;
1
Assuming 'cb_arg' is not equal to NULL→
2
←
Taking false branch→

/* find bin */
lock_quick_lock(&table->lock);
bin = &table->array[hash & table->size_mask];
lock_quick_lock(&bin->lock);

/* see if entry exists already */
if ((found = bin_find_entry(table, bin, hash, entry->key, &collisions)) != NULL((void *)0)) {
3
←
Assuming the condition is false→
4
←
Taking false branch→
/* if so: keep the existing data - acquire a writelock */
lock_rw_wrlock(&found->lock);
}
else
{
/* if not: add to bin */
entry->overflow_next = bin->overflow_list;
bin->overflow_list = entry;
lru_front(table, entry);
5
←
Calling 'lru_front'→
9
←
Returning from 'lru_front'→
table->num++;
if (table->max_collisions < collisions)
10
←
Assuming 'collisions' is <= field 'max_collisions'→
11
←
Taking false branch→
	table->max_collisions = collisions;
table->space_used += need_size;
/* return the entry that was presented, and lock it */
found = entry;
lock_rw_wrlock(&found->lock);
}
lock_quick_unlock(&bin->lock);
if (table->space_used > table->space_max)
12
←
Assuming field 'space_used' is > field 'space_max'→
13
←
Taking true branch→
reclaim_space(table, &reclaimlist);
14
←
Calling 'reclaim_space'→
if (table->num >= table->size)
table_grow(table);
lock_quick_unlock(&table->lock);

/* finish reclaim if any (outside of critical region) */
while (reclaimlist) {
struct lruhash_entry* n = reclaimlist->overflow_next;
void* d = reclaimlist->data;
(*table->delkeyfunc)(reclaimlist->key, cb_arg);
(*table->deldatafunc)(d, cb_arg);
reclaimlist = n;
}

/* return the entry that was selected */
return found;
641}
