Message ID | 20180817232923.28899-3-cota@braap.org |
---|---|
State | New |
Headers | show |
Series | qht improvements for 3.1 | expand |
Emilio G. Cota <cota@braap.org> writes: > 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. > > Signed-off-by: Emilio G. Cota <cota@braap.org> > --- > include/qemu/qht.h | 19 ++++++++++++ > util/qht.c | 74 +++++++++++++++++++++++++++++++++++++++++----- > 2 files changed, 85 insertions(+), 8 deletions(-) > > diff --git a/include/qemu/qht.h b/include/qemu/qht.h > index 1fb9116fa0..91bc9b00cf 100644 > --- a/include/qemu/qht.h > +++ b/include/qemu/qht.h > @@ -44,6 +44,8 @@ struct qht_stats { > > typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp); > typedef void (*qht_iter_func_t)(struct qht *ht, void *p, uint32_t h, void *up); > +typedef bool (*qht_iter_bool_func_t)(struct qht *ht, void *p, uint32_t h, > + void *up); > > #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */ > > @@ -178,9 +180,26 @@ bool qht_resize(struct qht *ht, size_t n_elems); > * > * Each time it is called, user-provided @func is passed a pointer-hash pair, > * plus @userp. > + * > + * Note: @ht cannot be accessed from @func I'm confused by this comment. If @ht cannot be accessed (or shouldn't be accessed) from @func then why are we passing it? > + * See also: qht_iter_remove() > */ > void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp); > > +/** > + * qht_iter_remove - Iterate over a QHT, optionally removing entries > + * @ht: QHT to be iterated over > + * @func: function to be called for each entry in QHT > + * @userp: additional pointer to be passed to @func > + * > + * Each time it is called, user-provided @func is passed a pointer-hash pair, > + * plus @userp. If @func returns true, the pointer-hash pair is removed. > + * > + * Note: @ht cannot be accessed from @func > + * See also: qht_iter() > + */ > +void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp); > + > /** > * qht_statistics_init - Gather statistics from a QHT > * @ht: QHT to gather statistics from > diff --git a/util/qht.c b/util/qht.c > index 7b57b50a24..caec53dd0e 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; > +}; > + > /* > * Note: reading partially-updated pointers in @pointers could lead to > * segfaults. We thus access them with atomic_read/set; this guarantees > @@ -706,9 +719,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 { > @@ -716,7 +730,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); > @@ -724,26 +756,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; > @@ -760,6 +814,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); > @@ -774,7 +832,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); Otherwise: Reviewed-by: Alex Bennée <alex.bennee@linaro.org> -- Alex Bennée
On Fri, Sep 07, 2018 at 15:51:12 +0100, Alex Bennée wrote: > > Emilio G. Cota <cota@braap.org> writes: > > > 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. > > > > Signed-off-by: Emilio G. Cota <cota@braap.org> > > --- > > include/qemu/qht.h | 19 ++++++++++++ > > util/qht.c | 74 +++++++++++++++++++++++++++++++++++++++++----- > > 2 files changed, 85 insertions(+), 8 deletions(-) > > > > diff --git a/include/qemu/qht.h b/include/qemu/qht.h > > index 1fb9116fa0..91bc9b00cf 100644 > > --- a/include/qemu/qht.h > > +++ b/include/qemu/qht.h > > @@ -44,6 +44,8 @@ struct qht_stats { > > > > typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp); > > typedef void (*qht_iter_func_t)(struct qht *ht, void *p, uint32_t h, void *up); > > +typedef bool (*qht_iter_bool_func_t)(struct qht *ht, void *p, uint32_t h, > > + void *up); > > > > #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */ > > > > @@ -178,9 +180,26 @@ bool qht_resize(struct qht *ht, size_t n_elems); > > * > > * Each time it is called, user-provided @func is passed a pointer-hash pair, > > * plus @userp. > > + * > > + * Note: @ht cannot be accessed from @func > > I'm confused by this comment. If @ht cannot be accessed (or shouldn't be > accessed) from @func then why are we passing it? We could probably do without. My original thinking was to pass the *ht to tell the iter function which ht his k-v pair comes from. But that's not a common use case, so we should remove it to simplify the interface. I think the comment is important right now; note that we can't even perform a lookup from the callback without deadlock. So I'll take your R-b for this patch and remove the *ht in another patch. Thanks, Emilio
diff --git a/include/qemu/qht.h b/include/qemu/qht.h index 1fb9116fa0..91bc9b00cf 100644 --- a/include/qemu/qht.h +++ b/include/qemu/qht.h @@ -44,6 +44,8 @@ struct qht_stats { typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp); typedef void (*qht_iter_func_t)(struct qht *ht, void *p, uint32_t h, void *up); +typedef bool (*qht_iter_bool_func_t)(struct qht *ht, void *p, uint32_t h, + void *up); #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */ @@ -178,9 +180,26 @@ bool qht_resize(struct qht *ht, size_t n_elems); * * Each time it is called, user-provided @func is passed a pointer-hash pair, * plus @userp. + * + * Note: @ht cannot be accessed from @func + * See also: qht_iter_remove() */ void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp); +/** + * qht_iter_remove - Iterate over a QHT, optionally removing entries + * @ht: QHT to be iterated over + * @func: function to be called for each entry in QHT + * @userp: additional pointer to be passed to @func + * + * Each time it is called, user-provided @func is passed a pointer-hash pair, + * plus @userp. If @func returns true, the pointer-hash pair is removed. + * + * Note: @ht cannot be accessed from @func + * See also: qht_iter() + */ +void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp); + /** * qht_statistics_init - Gather statistics from a QHT * @ht: QHT to gather statistics from diff --git a/util/qht.c b/util/qht.c index 7b57b50a24..caec53dd0e 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; +}; + /* * Note: reading partially-updated pointers in @pointers could lead to * segfaults. We thus access them with atomic_read/set; this guarantees @@ -706,9 +719,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 { @@ -716,7 +730,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); @@ -724,26 +756,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; @@ -760,6 +814,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); @@ -774,7 +832,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);
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. Signed-off-by: Emilio G. Cota <cota@braap.org> --- include/qemu/qht.h | 19 ++++++++++++ util/qht.c | 74 +++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 85 insertions(+), 8 deletions(-)