aboutsummaryrefslogtreecommitdiff
path: root/util
diff options
context:
space:
mode:
authorEmilio G. Cota <cota@braap.org>2018-08-15 15:00:48 -0400
committerRichard Henderson <richard.henderson@linaro.org>2018-09-26 08:55:54 -0700
commit69d55e9cc28dc2f1e2f2426d2a43f2d10db76f29 (patch)
tree2e997d31cc122f7dcb59d2985ae299251a5590a5 /util
parente2f07efadd15c045bca42661c07b0557c8250e24 (diff)
downloadqemu-69d55e9cc28dc2f1e2f2426d2a43f2d10db76f29.zip
qemu-69d55e9cc28dc2f1e2f2426d2a43f2d10db76f29.tar.gz
qemu-69d55e9cc28dc2f1e2f2426d2a43f2d10db76f29.tar.bz2
qht: add qht_iter_remove
This currently has no users, but the use case is so common that I think we must support it. Note that without the appended we cannot safely remove a set of elements; a 2-step approach (i.e. qht_iter first, keep track of the to-be-deleted elements, and then a bunch of qht_remove calls) would be racy, since between the iteration and the removals other threads might insert additional elements. Reviewed-by: Alex Bennée <alex.bennee@linaro.org> Signed-off-by: Emilio G. Cota <cota@braap.org> Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
Diffstat (limited to 'util')
-rw-r--r--util/qht.c74
1 files changed, 66 insertions, 8 deletions
diff --git a/util/qht.c b/util/qht.c
index 28d9273..c190e89 100644
--- a/util/qht.c
+++ b/util/qht.c
@@ -89,6 +89,19 @@
#define QHT_BUCKET_ENTRIES 4
#endif
+enum qht_iter_type {
+ QHT_ITER_VOID, /* do nothing; use retvoid */
+ QHT_ITER_RM, /* remove element if retbool returns true */
+};
+
+struct qht_iter {
+ union {
+ qht_iter_func_t retvoid;
+ qht_iter_bool_func_t retbool;
+ } f;
+ enum qht_iter_type type;
+};
+
/*
* Do _not_ use qemu_mutex_[try]lock directly! Use these macros, otherwise
* the profiler (QSP) will deadlock.
@@ -733,9 +746,10 @@ bool qht_remove(struct qht *ht, const void *p, uint32_t hash)
return ret;
}
-static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *b,
- qht_iter_func_t func, void *userp)
+static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *head,
+ const struct qht_iter *iter, void *userp)
{
+ struct qht_bucket *b = head;
int i;
do {
@@ -743,7 +757,25 @@ static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *b,
if (b->pointers[i] == NULL) {
return;
}
- func(ht, b->pointers[i], b->hashes[i], userp);
+ switch (iter->type) {
+ case QHT_ITER_VOID:
+ iter->f.retvoid(ht, b->pointers[i], b->hashes[i], userp);
+ break;
+ case QHT_ITER_RM:
+ if (iter->f.retbool(ht, b->pointers[i], b->hashes[i], userp)) {
+ /* replace i with the last valid element in the bucket */
+ seqlock_write_begin(&head->sequence);
+ qht_bucket_remove_entry(b, i);
+ seqlock_write_end(&head->sequence);
+ qht_bucket_debug__locked(b);
+ /* reevaluate i, since it just got replaced */
+ i--;
+ continue;
+ }
+ break;
+ default:
+ g_assert_not_reached();
+ }
}
b = b->next;
} while (b);
@@ -751,26 +783,48 @@ static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *b,
/* call with all of the map's locks held */
static inline void qht_map_iter__all_locked(struct qht *ht, struct qht_map *map,
- qht_iter_func_t func, void *userp)
+ const struct qht_iter *iter,
+ void *userp)
{
size_t i;
for (i = 0; i < map->n_buckets; i++) {
- qht_bucket_iter(ht, &map->buckets[i], func, userp);
+ qht_bucket_iter(ht, &map->buckets[i], iter, userp);
}
}
-void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp)
+static inline void
+do_qht_iter(struct qht *ht, const struct qht_iter *iter, void *userp)
{
struct qht_map *map;
map = atomic_rcu_read(&ht->map);
qht_map_lock_buckets(map);
/* Note: ht here is merely for carrying ht->mode; ht->map won't be read */
- qht_map_iter__all_locked(ht, map, func, userp);
+ qht_map_iter__all_locked(ht, map, iter, userp);
qht_map_unlock_buckets(map);
}
+void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp)
+{
+ const struct qht_iter iter = {
+ .f.retvoid = func,
+ .type = QHT_ITER_VOID,
+ };
+
+ do_qht_iter(ht, &iter, userp);
+}
+
+void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp)
+{
+ const struct qht_iter iter = {
+ .f.retbool = func,
+ .type = QHT_ITER_RM,
+ };
+
+ do_qht_iter(ht, &iter, userp);
+}
+
static void qht_map_copy(struct qht *ht, void *p, uint32_t hash, void *userp)
{
struct qht_map *new = userp;
@@ -787,6 +841,10 @@ static void qht_map_copy(struct qht *ht, void *p, uint32_t hash, void *userp)
static void qht_do_resize_reset(struct qht *ht, struct qht_map *new, bool reset)
{
struct qht_map *old;
+ const struct qht_iter iter = {
+ .f.retvoid = qht_map_copy,
+ .type = QHT_ITER_VOID,
+ };
old = ht->map;
qht_map_lock_buckets(old);
@@ -801,7 +859,7 @@ static void qht_do_resize_reset(struct qht *ht, struct qht_map *new, bool reset)
}
g_assert(new->n_buckets != old->n_buckets);
- qht_map_iter__all_locked(ht, old, qht_map_copy, new);
+ qht_map_iter__all_locked(ht, old, &iter, new);
qht_map_debug__all_locked(new);
atomic_rcu_set(&ht->map, new);