[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PATCH 06/22] qht: return existing entry when qht_insert fa
From: |
Emilio G. Cota |
Subject: |
[Qemu-devel] [PATCH 06/22] qht: return existing entry when qht_insert fails |
Date: |
Mon, 7 Aug 2017 19:52:22 -0400 |
The meaning of "existing" is now changed to "matches in hash and
ht->cmp result". This is saner than just checking the pointer value.
Note that we now return NULL on insertion success, or the existing
pointer on failure. We can do this because NULL pointers are not
allowed to be inserted in QHT.
Suggested-by: Richard Henderson <address@hidden>
Signed-off-by: Emilio G. Cota <address@hidden>
---
include/qemu/qht.h | 7 ++++---
tests/qht-bench.c | 4 ++--
tests/test-qht.c | 5 ++++-
util/qht.c | 17 +++++++++--------
4 files changed, 19 insertions(+), 14 deletions(-)
diff --git a/include/qemu/qht.h b/include/qemu/qht.h
index dd512bf..c320cb6 100644
--- a/include/qemu/qht.h
+++ b/include/qemu/qht.h
@@ -77,10 +77,11 @@ void qht_destroy(struct qht *ht);
* In case of successful operation, smp_wmb() is implied before the pointer is
* inserted into the hash table.
*
- * Returns true on success.
- * Returns false if the @address@hidden pair already exists in the hash table.
+ * On success, returns NULL.
+ * On failure, returns the pointer from an entry that is equivalent (i.e.
+ * ht->cmp matches and the hash is the same) to @address@hidden
*/
-bool qht_insert(struct qht *ht, void *p, uint32_t hash);
+void *qht_insert(struct qht *ht, void *p, uint32_t hash);
/**
* qht_lookup_custom - Look up a pointer using a custom comparison function.
diff --git a/tests/qht-bench.c b/tests/qht-bench.c
index c94ac25..6c2eb8e 100644
--- a/tests/qht-bench.c
+++ b/tests/qht-bench.c
@@ -163,7 +163,7 @@ static void do_rw(struct thread_info *info)
bool written = false;
if (qht_lookup(&ht, p, hash) == NULL) {
- written = qht_insert(&ht, p, hash);
+ written = !qht_insert(&ht, p, hash);
}
if (written) {
stats->in++;
@@ -322,7 +322,7 @@ static void htable_init(void)
r = xorshift64star(r);
p = &keys[r & (init_range - 1)];
hash = h(*p);
- if (qht_insert(&ht, p, hash)) {
+ if (!qht_insert(&ht, p, hash)) {
break;
}
retries++;
diff --git a/tests/test-qht.c b/tests/test-qht.c
index f8f2886..7164ae4 100644
--- a/tests/test-qht.c
+++ b/tests/test-qht.c
@@ -27,11 +27,14 @@ static void insert(int a, int b)
for (i = a; i < b; i++) {
uint32_t hash;
+ void *existing;
arr[i] = i;
hash = i;
- qht_insert(&ht, &arr[i], hash);
+ g_assert_true(!qht_insert(&ht, &arr[i], hash));
+ existing = qht_insert(&ht, &arr[i], hash);
+ g_assert_true(existing == &arr[i]);
}
}
diff --git a/util/qht.c b/util/qht.c
index b69457d..90ecfca 100644
--- a/util/qht.c
+++ b/util/qht.c
@@ -510,9 +510,9 @@ void *qht_lookup(struct qht *ht, const void *userp,
uint32_t hash)
}
/* call with head->lock held */
-static bool qht_insert__locked(struct qht *ht, struct qht_map *map,
- struct qht_bucket *head, void *p, uint32_t hash,
- bool *needs_resize)
+static void *qht_insert__locked(struct qht *ht, struct qht_map *map,
+ struct qht_bucket *head, void *p, uint32_t
hash,
+ bool *needs_resize)
{
struct qht_bucket *b = head;
struct qht_bucket *prev = NULL;
@@ -522,8 +522,9 @@ static bool qht_insert__locked(struct qht *ht, struct
qht_map *map,
do {
for (i = 0; i < QHT_BUCKET_ENTRIES; i++) {
if (b->pointers[i]) {
- if (unlikely(b->pointers[i] == p)) {
- return false;
+ if (unlikely(b->hashes[i] == hash &&
+ ht->cmp(b->pointers[i], p))) {
+ return b->pointers[i];
}
} else {
goto found;
@@ -552,7 +553,7 @@ static bool qht_insert__locked(struct qht *ht, struct
qht_map *map,
atomic_set(&b->hashes[i], hash);
atomic_set(&b->pointers[i], p);
seqlock_write_end(&head->sequence);
- return true;
+ return NULL;
}
static __attribute__((noinline)) void qht_grow_maybe(struct qht *ht)
@@ -576,12 +577,12 @@ static __attribute__((noinline)) void
qht_grow_maybe(struct qht *ht)
qemu_mutex_unlock(&ht->lock);
}
-bool qht_insert(struct qht *ht, void *p, uint32_t hash)
+void *qht_insert(struct qht *ht, void *p, uint32_t hash)
{
struct qht_bucket *b;
struct qht_map *map;
bool needs_resize = false;
- bool ret;
+ void *ret;
/* NULL pointers are not supported */
qht_debug_assert(p);
--
2.7.4
- [Qemu-devel] [PATCH 02/22] linux-user: fix 'finshed' typo in comment, (continued)
- [Qemu-devel] [PATCH 02/22] linux-user: fix 'finshed' typo in comment, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 03/22] translate-all: fix 'consisits' typo in comment, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 09/22] translate-all: introduce iterator macros for tagged TB lists, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 01/22] disas/arm: fix 'instuction' typo in comment, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 04/22] qht: fix kernel-doc markup in qht.h, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 11/22] translate-all: exit from tb_phys_invalidate if qht_remove fails, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 08/22] tcg: move tb_ctx.tb_phys_invalidate_count to tcg_ctx, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 13/22] translate-all: remove hole in PageDesc, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 12/22] translate-all: make l1_map lockless, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 05/22] qht: require a default comparison function, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 06/22] qht: return existing entry when qht_insert fails,
Emilio G. Cota <=
- [Qemu-devel] [PATCH 15/22] translate-all: move tb_invalidate_phys_page_range up in the file, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 10/22] translate-all: iterate over TBs in a page with page_for_each_tb, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 17/22] translate-all: discard TB when tb_link_page returns an existing matching TB, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 16/22] translate-all: use per-page locking in !user-mode, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 07/22] tcg: track TBs with per-region BST's, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 14/22] translate-all: work page-by-page in tb_invalidate_phys_range_1, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 18/22] translate-all: protect TB jumps with a per-destination-TB lock, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 20/22] exec: remove tb_lock from notdirty_mem_write, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 19/22] cputlb: remove tb_lock from tlb_flush functions, Emilio G. Cota, 2017/08/07
- [Qemu-devel] [PATCH 21/22] translate-all: remove tb_lock mention from cpu_restore_state_from_tb, Emilio G. Cota, 2017/08/07