From a795a9b40f84b84e7462d2e0d8f909ee7b9d2a15 Mon Sep 17 00:00:00 2001 From: espie Date: Mon, 12 May 2014 19:07:37 +0000 Subject: [PATCH] tweak interface to do the right thing, after useful comments from millert@ (mostly use a calloc function to avoid potential integer overflow) --- include/ohash.h | 8 ++++-- lib/libc/ohash/ohash_delete.c | 5 ++-- lib/libc/ohash/ohash_do.c | 23 +++++++++------ lib/libc/ohash/ohash_init.3 | 51 +++++++++++++++++++++++++++++---- lib/libc/ohash/ohash_init.c | 10 +++---- lib/libc/ohash/ohash_interval.3 | 9 ++++-- 6 files changed, 78 insertions(+), 28 deletions(-) diff --git a/include/ohash.h b/include/ohash.h index 71e7ac19724..8c11ba55939 100644 --- a/include/ohash.h +++ b/include/ohash.h @@ -1,6 +1,6 @@ #ifndef OHASH_H #define OHASH_H -/* $OpenBSD: ohash.h,v 1.10 2012/09/23 15:05:23 espie Exp $ */ +/* $OpenBSD: ohash.h,v 1.11 2014/05/12 19:07:37 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -24,16 +24,18 @@ * techniques, and more efficient in most cases. */ +/* user-visible data structure */ struct ohash_info { ptrdiff_t key_offset; void *data; /* user data */ - void *(*halloc)(size_t, void *); - void (*hfree)(void *, size_t, void *); + void *(*calloc)(size_t, size_t, void *); + void (*free)(void *, void *); void *(*alloc)(size_t, void *); }; struct _ohash_record; +/* private structure. It's there just so you can do a sizeof */ struct ohash { struct _ohash_record *t; struct ohash_info info; diff --git a/lib/libc/ohash/ohash_delete.c b/lib/libc/ohash/ohash_delete.c index 12a9c0c368a..c991d05030b 100644 --- a/lib/libc/ohash/ohash_delete.c +++ b/lib/libc/ohash/ohash_delete.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ohash_delete.c,v 1.2 2004/06/22 20:00:16 espie Exp $ */ +/* $OpenBSD: ohash_delete.c,v 1.3 2014/05/12 19:07:37 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -23,8 +23,7 @@ void ohash_delete(struct ohash *h) { - (h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size, - h->info.data); + (h->info.free)(h->t, h->info.data); #ifndef NDEBUG h->t = NULL; #endif diff --git a/lib/libc/ohash/ohash_do.c b/lib/libc/ohash/ohash_do.c index c139fa7ddbb..9caeca0e180 100644 --- a/lib/libc/ohash/ohash_do.c +++ b/lib/libc/ohash/ohash_do.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ohash_do.c,v 1.4 2004/06/22 20:00:16 espie Exp $ */ +/* $OpenBSD: ohash_do.c,v 1.5 2014/05/12 19:07:37 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -17,6 +17,7 @@ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ +#include #include "ohash_int.h" static void ohash_resize(struct ohash *); @@ -25,13 +26,17 @@ static void ohash_resize(struct ohash *h) { struct _ohash_record *n; - unsigned int ns, j; + size_t ns; + unsigned int j; unsigned int i, incr; - if (4 * h->deleted < h->total) - ns = h->size << 1; - else if (3 * h->deleted > 2 * h->total) - ns = h->size >> 1; + if (4 * h->deleted < h->total) { + if (h->size >= (UINT_MAX >> 1U)) + ns = UINT_MAX; + else + ns = h->size << 1U; + } else if (3 * h->deleted > 2 * h->total) + ns = h->size >> 1U; else ns = h->size; if (ns < MINSIZE) @@ -40,7 +45,8 @@ ohash_resize(struct ohash *h) STAT_HASH_EXPAND++; STAT_HASH_SIZE += ns - h->size; #endif - n = (h->info.halloc)(sizeof(struct _ohash_record) * ns, h->info.data); + + n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data); if (!n) return; @@ -57,8 +63,7 @@ ohash_resize(struct ohash *h) n[i].p = h->t[j].p; } } - (h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size, - h->info.data); + (h->info.free)(h->t, h->info.data); h->t = n; h->size = ns; h->total -= h->deleted; diff --git a/lib/libc/ohash/ohash_init.3 b/lib/libc/ohash/ohash_init.3 index fc924acf45f..88ec0bb5df6 100644 --- a/lib/libc/ohash/ohash_init.3 +++ b/lib/libc/ohash/ohash_init.3 @@ -1,4 +1,4 @@ -.\" $OpenBSD: ohash_init.3,v 1.17 2013/06/05 03:39:23 tedu Exp $ +.\" $OpenBSD: ohash_init.3,v 1.18 2014/05/12 19:07:37 espie Exp $ .\" Copyright (c) 1999 Marc Espie .\" .\" Permission to use, copy, modify, and distribute this software for any @@ -13,7 +13,7 @@ .\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF .\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. .\" -.Dd $Mdocdate: June 5 2013 $ +.Dd $Mdocdate: May 12 2014 $ .Dt OHASH_INIT 3 .Os .Sh NAME @@ -69,11 +69,46 @@ initializes the table to store roughly 2 to the power .Fa size elements. .Fa info -holds the position of the key in each record, and two pointers to +is a pointer to a +.Fa struct ohash_info . +.Bd -literal -offset indent +struct ohash_info { + ptrdiff_t key_offset; + void *data; /* user data */ + void *(*calloc)(size_t, size_t, void *); + void (*free)(void *, void *); + void *(*alloc)(size_t, void *); +}; +.Ed +.Pp +The +.Va offset +field holds the position of the key in each record; +the +.Va calloc +and +.Va free +fields are pointers to .Xr calloc 3 and .Xr free 3 Ns -like -functions, to use for managing the table internal storage. +functions, used for managing the table internal storage; +the +.Va alloc +field is only used by the utility function +.Xr ohash_create_entry 3 . +.Pp +Each of these functions are called similarly to their standard counterpart, +but with an extra +.Ft void * +parameter corresponding to the content of the field +.Fa data , +which can be used to communicate specific information to the functions. +.Pp +.Fn ohash_init +stores a copy of those fields internally, so +.Fa info +can be reclaimed after initialization. .Pp .Fn ohash_delete frees storage internal to @@ -177,7 +212,13 @@ Only .Fn ohash_remove and .Fn ohash_delete -may call the user-supplied memory functions. +may call the user-supplied memory functions: +.Bd -literal -offset indent +p = (*info->calloc)(n, sizeof_record, info->data); +/* copy data from old to p */ +(*info->free)(old, info->data); +.Ed +.Pp It is the responsibility of the user memory allocation code to verify that those calls did not fail. .Pp diff --git a/lib/libc/ohash/ohash_init.c b/lib/libc/ohash/ohash_init.c index 4d24fa4be4b..1710b54dfa1 100644 --- a/lib/libc/ohash/ohash_init.c +++ b/lib/libc/ohash/ohash_init.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ohash_init.c,v 1.2 2004/06/22 20:00:16 espie Exp $ */ +/* $OpenBSD: ohash_init.c,v 1.3 2014/05/12 19:07:37 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -31,11 +31,11 @@ ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info) #endif /* Copy info so that caller may free it. */ h->info.key_offset = info->key_offset; - h->info.halloc = info->halloc; - h->info.hfree = info->hfree; + h->info.calloc = info->calloc; + h->info.free = info->free; h->info.alloc = info->alloc; h->info.data = info->data; - h->t = (h->info.halloc)(sizeof(struct _ohash_record) * h->size, - h->info.data); + h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record), + h->info.data); h->total = h->deleted = 0; } diff --git a/lib/libc/ohash/ohash_interval.3 b/lib/libc/ohash/ohash_interval.3 index c96d992b915..7191ddd2c8d 100644 --- a/lib/libc/ohash/ohash_interval.3 +++ b/lib/libc/ohash/ohash_interval.3 @@ -1,4 +1,4 @@ -.\" $OpenBSD: ohash_interval.3,v 1.14 2013/06/05 03:39:23 tedu Exp $ +.\" $OpenBSD: ohash_interval.3,v 1.15 2014/05/12 19:07:37 espie Exp $ .\" Copyright (c) 2001 Marc Espie .\" .\" Permission to use, copy, modify, and distribute this software for any @@ -13,7 +13,7 @@ .\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF .\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. .\" -.Dd $Mdocdate: June 5 2013 $ +.Dd $Mdocdate: May 12 2014 $ .Dt OHASH_INTERVAL 3 .Os .Sh NAME @@ -66,7 +66,10 @@ the alloc field of .Fa info should point to a .Xr malloc 3 Ns -like -function to allocate the storage. +function to allocate the storage: +.Bd -literal -offset indent +p = (*info->alloc)(sz, info->data); +.Ed .Pp .Fn ohash_qlookupi is a wrapper function that simply calls -- 2.20.1