[kaffe] CVS kaffe (guilhem): Race fix in hashResize/hashtable.
Kaffe CVS
cvs-commits at kaffe.org
Sat May 7 03:39:59 PDT 2005
PatchSet 6449
Date: 2005/05/07 10:35:14
Author: guilhem
Branch: HEAD
Tag: (none)
Log:
Race fix in hashResize/hashtable.
Members:
ChangeLog:1.3977->1.3978
kaffe/kaffevm/hashtab.c:INITIAL->1.17
Index: kaffe/ChangeLog
diff -u kaffe/ChangeLog:1.3977 kaffe/ChangeLog:1.3978
--- kaffe/ChangeLog:1.3977 Sat May 7 09:00:16 2005
+++ kaffe/ChangeLog Sat May 7 10:35:14 2005
@@ -1,3 +1,9 @@
+2005-05-07 Guilhem Lavaux <guilhem at kaffe.org>
+
+ * kaffe/kaffevm/hashtab.c
+ (hashResize): Reordered tab update to prevent race conditions during
+ the deallocation.
+
2005-05-07 Dalibor Topic <robilad at kaffe.org>
* kaffe/kaffevm/systems/unix-jthreads/signal.c (setupSigAltStack),
===================================================================
Checking out kaffe/kaffe/kaffevm/hashtab.c
RCS: /home/cvs/kaffe/kaffe/kaffe/kaffevm/hashtab.c,v
VERS: 1.17
***************
--- /dev/null Sun Aug 4 19:57:58 2002
+++ kaffe/kaffe/kaffevm/hashtab.c Sat May 7 10:39:59 2005
@@ -0,0 +1,274 @@
+/*
+ * hashtab.c
+ *
+ * "Intern" hash table library
+ *
+ * Copyright (c) 1998
+ * Transvirtual Technologies, Inc. All rights reserved.
+ */
+
+#include "config.h"
+#include "debug.h"
+#include "config-std.h"
+#include "config-mem.h"
+#include "gtypes.h"
+#include "gc.h"
+#include "hashtab.h"
+#include "kaffe/jmalloc.h"
+
+/* Initial size */
+#define INITIAL_SIZE 1024
+
+/* When to increase size of hash table */
+#define NEED_RESIZE(tab) (4 * (tab)->count >= 3 * (tab)->size)
+
+/* Generate step from hash. Note that "step" must always be
+ relatively prime to tab->size. */
+#define LIST_STEP(hash) (8 * (hash) + 7)
+
+/* Hashtable structure */
+struct _hashtab {
+ const void **list; /* List of pointers to whatever */
+ int count; /* Number of slots used in the list */
+ int size; /* Total size list; always a power of 2 */
+ compfunc_t comp; /* Comparison function */
+ hashfunc_t hash; /* Hash function */
+ allocfunc_t alloc; /* Allocation function */
+ freefunc_t dealloc; /* Free function */
+};
+
+/* Internal functions */
+static int hashFindSlot(hashtab_t, const void *ptr);
+static hashtab_t hashResize(hashtab_t tab);
+
+/* Indicates a deleted pointer */
+static const void *const DELETED = (const void *)&DELETED;
+
+/*
+ * Create a new hashtable
+ */
+hashtab_t
+hashInit(hashfunc_t hash, compfunc_t comp, allocfunc_t alloc, freefunc_t dealloc)
+{
+ hashtab_t tab;
+
+ /* Use specified alloc function if one is given, fall back to KFREE */
+ if (alloc == 0) {
+ tab = KCALLOC(1, sizeof(*tab));
+ } else {
+ tab = alloc(sizeof(*tab));
+ }
+ if (tab == 0) {
+ return (NULL);
+ }
+ tab->hash = hash;
+ tab->comp = comp;
+ tab->alloc = alloc;
+ tab->dealloc = dealloc;
+ /* start out with initial size */
+ return (hashResize(tab));
+}
+
+/*
+ * Destroy a hash table.
+ */
+void
+hashDestroy(hashtab_t tab)
+{
+ int k;
+
+ /* Remove all entries in the table */
+ for (k = 0; k < tab->size; k++) {
+ if (tab->list[k] != NULL && tab->list[k] != DELETED) {
+ hashRemove(tab, tab->list[k]);
+ }
+ }
+
+ /* Nuke the table */
+ if (tab->dealloc) {
+ tab->dealloc(tab->list);
+ tab->dealloc(tab);
+ } else {
+ KFREE(tab->list);
+ KFREE(tab);
+ }
+}
+
+/*
+ * Add an entry to the hash table. It's OK if the entry is already there,
+ * or is equal to something that is already there. This returns the
+ * matching pointer that is actually in the table.
+ */
+const void *
+hashAdd(hashtab_t tab, const void *ptr)
+{
+ int i;
+ const void *rtn;
+
+ if (NEED_RESIZE(tab)) {
+ if (hashResize(tab) == 0) {
+ /* XXX OutOfMemoryError? */
+ return (NULL);
+ }
+ }
+ i = hashFindSlot(tab, ptr);
+ assert(i != -1);
+ if (tab->list[i] == NULL || tab->list[i] == DELETED) {
+ tab->list[i] = ptr;
+ tab->count++;
+ }
+ rtn = tab->list[i];
+
+ return(rtn);
+}
+
+/*
+ * Remove a pointer. If the pointer is not itself in the table,
+ * we don't remove it.
+ */
+void
+hashRemove(hashtab_t tab, const void *ptr)
+{
+ int i;
+
+ i = hashFindSlot(tab, ptr);
+ assert(i != -1);
+ if (tab->list[i] != NULL
+ && tab->list[i] != DELETED
+ && tab->list[i] == ptr) {
+ tab->count--;
+ tab->list[i] = DELETED;
+ }
+}
+
+/*
+ * Find a matching pointer in the table.
+ */
+const void *
+hashFind(hashtab_t tab, const void *ptr)
+{
+ int i;
+ const void *rtn;
+
+ i = hashFindSlot(tab, ptr);
+ assert(i != -1);
+ rtn = (tab->list[i] == DELETED) ?
+ NULL : tab->list[i];
+
+ return(rtn);
+}
+
+/*
+ * Find if an equal pointer is already in the table. If found,
+ * return it; otherwise return a free slot for it.
+ */
+static int
+hashFindSlot(hashtab_t tab, const void *ptr)
+{
+ const int hash = (*tab->hash)(ptr);
+ const int startIndex = hash & (tab->size - 1);
+ const int step = LIST_STEP(hash);
+ int i, deletedIndex = -1;
+
+ /* Sanity check */
+ if (ptr == NULL || ptr == DELETED) {
+ return(-1);
+ }
+
+ /* Find slot */
+ i = startIndex;
+ for (;;) {
+ const void **const ptr2 = &tab->list[i];
+
+ if (*ptr2 == NULL) {
+ return (deletedIndex >= 0) ? deletedIndex : i;
+ }
+ if (*ptr2 == DELETED) {
+ if (deletedIndex == -1) {
+ deletedIndex = i;
+ }
+ } else if (*ptr2 == ptr || (*tab->comp)(ptr, *ptr2) == 0) {
+ return(i);
+ }
+ i = (i + step) & (tab->size - 1);
+
+ /* Check for looping all the way through the table */
+ if (i == startIndex) {
+ if (deletedIndex >= 0) {
+ return(deletedIndex);
+ }
+ assert(!"hashFindSlot: no slot!");
+ }
+ }
+}
+
+/*
+ * Make the table bigger.
+ * Return the new table or null if the allocation failed.
+ *
+ * It is okay to remove entries from the table while the allocation
+ * function is invoked.
+ */
+static hashtab_t
+hashResize(hashtab_t tab)
+{
+ const int newSize = (tab->size > 0) ? (tab->size * 2) : INITIAL_SIZE;
+ const void **newList;
+ const void **oldList;
+ int i;
+
+ /* Get a bigger list */
+ if (tab->alloc) {
+ newList = tab->alloc(newSize * sizeof(*newList));
+ } else {
+ newList = KCALLOC(newSize, sizeof(*newList));
+ }
+
+ /* It is possible that the table no longer needs resizing, for
+ * instance because a garbage collection happened and removed
+ * entries, for instance when uninterning strings.
+ */
+ if (!NEED_RESIZE(tab)) {
+ if (tab->dealloc) {
+ tab->dealloc(newList);
+ } else {
+ KFREE(newList);
+ }
+ return (tab);
+ }
+
+ if (newList == NULL) {
+ return (NULL);
+ }
+
+ /* Rehash old list contents into new list */
+ for (i = tab->size - 1; i >= 0; i--) {
+ const void *ptr = tab->list[i];
+
+ if (ptr != NULL && ptr != DELETED) {
+ const int hash = (*tab->hash)(ptr);
+ const int step = LIST_STEP(hash);
+ int j;
+
+ for (j = hash & (newSize - 1);
+ newList[j] != NULL;
+ j = (j + step) & (newSize - 1));
+ newList[j] = ptr;
+ }
+ }
+
+ /* Update table. The operation is atomic as the lock
+ * is held by the owner of the hashtable.
+ */
+ oldList = tab->list;
+ tab->list = newList;
+ tab->size = newSize;
+
+ /* Free the old table */
+ if (tab->dealloc) {
+ tab->dealloc(oldList);
+ } else {
+ KFREE(oldList);
+ }
+ return (tab);
+}
More information about the kaffe
mailing list