/usr/src/usr.sbin/unbound/util/storage/lruhash.c

Bug Summary

File:	src/usr.sbin/unbound/util/storage/lruhash.c
Warning:	line 200, 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.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name lruhash.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -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 -fno-rounding-math -mconstructor-aliases -munwind-tables -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/usr.sbin/unbound/obj -resource-dir /usr/local/lib/clang/13.0.0 -I . -I /usr/src/usr.sbin/unbound -D SRCDIR=/usr/src/usr.sbin/unbound -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/usr.sbin/unbound/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -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/vmm/scan-build/2022-01-12-194120-40624-1 -x c /usr/src/usr.sbin/unbound/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->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;
95}

97void 
98bin_delete(struct lruhash* table, struct lruhash_bin* bin)
99{
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;
}
114}

116void 
117bin_split(struct lruhash* table, struct lruhash_bin* newa, 
int newmask)
119{
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 */
126#ifndef THREADS_DISABLED1
int newbit = newmask - table->size_mask;
128#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);
}
150}

152void 
153lruhash_delete(struct lruhash* table)
154{
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);
164}

166void 
167bin_overflow_remove(struct lruhash_bin* bin, struct lruhash_entry* entry)
168{
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;
}
179}

181void 
182reclaim_space(struct lruhash* table, struct lruhash_entry** list)
183{
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_used13.1
Field 'space_used' is > field 'space_max'
 > table->space_max) {
13
←
Assuming field 'num' is > 1→
14
←
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);
15
←
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);
}
215}

217struct lruhash_entry* 
218bin_find_entry(struct lruhash* table, 
struct lruhash_bin* bin, hashvalue_type hash, void* key)
220{
struct lruhash_entry* p = bin->overflow_list;
while(p) {
if(p->hash == hash && table->compfunc(p->key, key) == 0)
	return p;
p = p->overflow_next;
}
return NULL((void*)0);
228}

230void 
231table_grow(struct lruhash* table)
232{
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;
263}

265void 
266lru_front(struct lruhash* table, struct lruhash_entry* entry)
267{
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;
274}

276void 
277lru_remove(struct lruhash* table, struct lruhash_entry* entry)
278{
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;
285}

287void 
288lru_touch(struct lruhash* table, struct lruhash_entry* entry)
289{
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);
297}

299void 
300lruhash_insert(struct lruhash* table, hashvalue_type hash,
      struct lruhash_entry* entry, void* data, void* cb_arg)
302{
struct lruhash_bin* bin;
struct lruhash_entry* found, *reclaimlist=NULL((void*)0);
size_t need_size;
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))) {
/* if not: add to bin */
entry->overflow_next = bin->overflow_list;
bin->overflow_list = entry;
lru_front(table, entry);
table->num++;
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;
}
353}

355struct lruhash_entry* 
356lruhash_lookup(struct lruhash* table, hashvalue_type hash, void* key, int wr)
357{
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)))
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;
375}

377void 
378lruhash_remove(struct lruhash* table, hashvalue_type hash, void* key)
379{
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))) {
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);
412}

414/** clear bin, respecting locks, does not do space, LRU */
415static void
416bin_clear(struct lruhash* table, struct lruhash_bin* bin)
417{
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);
435}

437void
438lruhash_clear(struct lruhash* table)
439{
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);
456}

458void 
459lruhash_status(struct lruhash* table, const char* id, int extended)
460{
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);
490}

492size_t
493lruhash_get_mem(struct lruhash* table)
494{
size_t s;
lock_quick_lock(&table->lock);
s = sizeof(struct lruhash) + table->space_used;
498#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);
}
505#else /* no THREAD_DEBUG */
if(table->size != 0)
s += (table->size)*(sizeof(struct lruhash_bin) + 
	lock_get_mem(&table->array[0].lock)(0));
509#endif
lock_quick_unlock(&table->lock);
s += lock_get_mem(&table->lock)(0);
return s;
513}

515void 
516lruhash_setmarkdel(struct lruhash* table, lruhash_markdelfunc_type md)
517{
lock_quick_lock(&table->lock);
table->markdelfunc = md;
lock_quick_unlock(&table->lock);
521}

523void 
524lruhash_traverse(struct lruhash* h, int wr, 
void (*func)(struct lruhash_entry*, void*), void* arg)
526{
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);
545}

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

552void
553lru_demote(struct lruhash* table, struct lruhash_entry* entry)
554{
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;
573}

575struct lruhash_entry*
576lruhash_insert_or_retrieve(struct lruhash* table, hashvalue_type hash,
struct lruhash_entry* entry, void* data, void* cb_arg)
578{
struct lruhash_bin* bin;
struct lruhash_entry* found, *reclaimlist = NULL((void*)0);
size_t need_size;
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)) != 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++;
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)
10
←
Assuming field 'space_used' is > field 'space_max'→
11
←
Taking true branch→
reclaim_space(table, &reclaimlist);
12
←
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;
630}
