On 1 Jul 2026, at 15:58, Eli Britstein wrote:
> From: Gaetan Rivet <[email protected]>
>
> Add a reference-counted key-value map.
>
> Duplicates take a reference on the original entry within the map,
> leaving it in place. To be able to execute an entry creation after
> determining whether it is already present or not in the map,
> store relevant initialization and de-initialization functions.
>
> Signed-off-by: Gaetan Rivet <[email protected]>
> Co-authored-by: Eli Britstein <[email protected]>
> Signed-off-by: Eli Britstein <[email protected]>
Hi Eli,
A bit late, but I was catching up on reviews before the branch
creation for OVS 4.0, which was done last week. Now I have time
for reviewing this series.
Find some small comments below, but with those fixed this patch
looks good to me.
//Eelco
PS: I'll be on PTO for a couple of weeks starting the 30th of this
month. My plan is to review my part before I go, and hopefully
David has some time to review the DPDK-specific parts he commented
on in v4.
[...]
>
> +static inline bool
> +ovs_refcount_unref_if_not_last(struct ovs_refcount *refcount)
> +{
> + unsigned int count;
Alignment is off in this function, should be 4 characters not 6.
> +
> + atomic_read_explicit(&refcount->count, &count,
> + memory_order_acquire);
> + ovs_assert(count > 0);
> + while (count > 1) {
> + if (atomic_compare_exchange_weak_explicit(
> + &refcount->count, &count, count - 1,
> + memory_order_release, memory_order_relaxed)) {
> + return true;
> + }
> + }
> + return false;
> + }
Zero spaces needed before closing branch.
[...]
> diff --git a/lib/refmap.h b/lib/refmap.h
> new file mode 100644
> index 000000000..05ef348e0
> --- /dev/null
> +++ b/lib/refmap.h
> @@ -0,0 +1,163 @@
> +/*
> + * Copyright (c) 2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
> + *
> + * Licensed under the Apache License, Version 2.0 (the "License");
> + * you may not use this file except in compliance with the License.
> + * You may obtain a copy of the License at:
> + *
> + * http://www.apache.org/licenses/LICENSE-2.0
> + *
> + * Unless required by applicable law or agreed to in writing, software
> + * distributed under the License is distributed on an "AS IS" BASIS,
> + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
> + * See the License for the specific language governing permissions and
> + * limitations under the License.
> + */
> +
> +#ifndef REFMAP_H
> +#define REFMAP_H
> +
> +#include <stdbool.h>
> +#include <stddef.h>
> +#include <stdint.h>
> +
> +#include "cmap.h"
> +
> +#include "openvswitch/dynamic-string.h"
> +
> +/*
> + * Reference map
> + * =============
> + *
> + * This key-value store acts like a regular concurrent hashmap,
> + * except that insertion takes a reference on the value if already
> + * present.
> + * The key provided must be fully initialized, including potential pad bytes.
> + *
> + * As the value creation is dependent on it being already present
> + * within the structure and the user cannot predict that, this structure
> + * requires definitions for value_init and value_uninit functions,
> + * that will be called only at creation (first reference taken) and
> + * destruction (last reference released).
> + *
> + * Example:
> + * 1. struct key key;
> + * 2. memset(&key, 0, sizeof key);
> + * 3. refmap_create()
> + * 4. value = refmap_ref(key);
> + * Since it's the first reference for <key>, value_init is called.
> + * 5. refmap_ref(key);
> + * This is not the first reference for <key>. Only ref-count is updated.
> + * 6. refmap_unref(value);
> + * This is not the last reference released. Only ref-count is updated.
> + * 7. refmap_unref(value);
> + * This is the last reference released. value_uninit is immediately
> + * called, while the value memory is freed after RCU grace period.
> + *
> + * Thread safety
> + * =============
> + *
> + * MT-unsafe:
> + * * refmap_create
> + * * refmap_destroy
> + *
> + * MT-safe:
> + * * REFMAP_FOR_EACH
> + * * refmap_ref
> + * * refmap_try_ref
> + * * refmap_try_ref_value
> + * * refmap_unref
> + *
> + * Callback constraints
> + * ====================
> + *
> + * value_init() and value_uninit() are invoked while holding the map's
> + * internal mutex. They must not call back into any refmap API on the
> + * same map as that would deadlock.
> + *
Maybe also add something like this for clarity?
* For a given key, value_uninit() for the old entry is guaranteed to
* complete before value_init() for a replacement entry begins. It is
* therefore safe for callbacks to manage external resources tied to
* the key (hardware table entries, file descriptors, etc.) without
* additional synchronization.
> + */
> +
> +struct refmap;
> +
> +/* Called once on a newly created 'value', i.e. when the first
> + * reference is taken. */
> +typedef int (*refmap_value_init)(void *value, void *arg);
> +
> +/* Called once on the last dereference to value. */
> +typedef void (*refmap_value_uninit)(void *value);
> +
> +/* Format a (key, value) tuple in 's'. This is an optional (can be NULL)
Double space between sentences. So "in 's'. This is".
> + * callback, used for debug log purposes.
> + */
> +typedef struct ds *(*refmap_value_format)(struct ds *s, void *key,
> + void *value);
> +
> +/* Iterator context for REFMAP_FOR_EACH. */
> +struct refmap_iter {
> + struct refmap *rfm;
> + struct cmap_cursor cursor;
> + void *prev_value;
> +};
> +
> +/* Helper for REFMAP_FOR_EACH: advances to the next entry, holding a ref for
> + * the current value (released on the next call or when iteration ends).
> + * Returns true if VALUE and KEY were set, false when iteration is done. */
> +bool refmap_iter_next(struct refmap_iter *, void **value, void **key);
> +
> +/* Iterates KEY/VALUE (void *) over REFMAP. A reference is held for each
> loop
> + * body and released after the body runs. If you break out of the loop, call
> + * refmap_unref(REFMAP, VALUE) on the current VALUE. */
> +#define REFMAP_FOR_EACH(VALUE, KEY, REFMAP) \
> + for (struct refmap_iter refmap_iter__ = { (REFMAP), {0}, NULL }; \
> + refmap_iter_next(&refmap_iter__, &(VALUE), &(KEY)); \
> + )
> +
> +/* Allocate and return a map handle.
> + *
> + * The user must ensure the 'key' is fully initialized, including potential
> + * pad bytes.
> + */
> +struct refmap *refmap_create(const char *name,
> + size_t key_size,
> + size_t value_size,
> + refmap_value_init,
> + refmap_value_uninit,
> + refmap_value_format);
> +
> +/* Frees the map memory.
> + *
> + * WARNING: The caller MUST ensure the map is empty before calling
> + * refmap_destroy(). If the map contains remaining elements, their
> + * values will NOT have value_uninit() called, which will leak any
> + * resources managed by those values (file descriptors, allocated
> + * memory, etc.). The node memory will be freed but resource cleanup
> + * will not occur.
> + *
> + * refmap_destroy() is MT-unsafe. It MUST NOT be called while any other
> + * thread might be accessing the refmap, even through MT-safe operations like
> + * REFMAP_FOR_EACH or refmap_try_ref().
> + */
Preference is for new multi-line comments to end on the same line.
> +void refmap_destroy(struct refmap *);
> +
> +/* The "ref" functions, including refmap_try_ref() take a reference for the
> + * value upon success. It's the user's responsibility to unref it.
> + */
Same here, and some more below. Please fix this up in all patches,
unless it's in an existing file where most of the existing comments
do end on a new line.
> +void *refmap_try_ref(struct refmap *, void *key);
> +void *refmap_ref(struct refmap *, void *key, void *arg);
> +bool refmap_try_ref_value(struct refmap *, void *value);
> +
> +void *refmap_key_from_value(struct refmap *, void *value);
> +
> +/* Return 'true' if it was the last 'value' dereference and
> + * 'value_uninit' has been called. */
> +bool refmap_unref(struct refmap *, void *value);
> +
> +/* refmap_value_refcount_read() returns the node's ref-count (including the
> + * reference implied by refmap_ref()) at the moment of the read, but may no
> + * longer be by the time you receive the value. This makes it unsuitable for
> + * logic decisions and only useful for debug logging.
> + */
> +unsigned int
> +refmap_value_refcount_read(struct refmap *, void *value);
> +
> +#endif /* REFMAP_H */
[...]
> diff --git a/tests/test-refmap.c b/tests/test-refmap.c
> new file mode 100644
> index 000000000..0f2b5b4f9
> --- /dev/null
> +++ b/tests/test-refmap.c
[...]
> +/* value_init failure: refmap_ref returns NULL, no entry is inserted, no
> + * value_uninit; a later successful ref on the same key still works. */
> +static void
> +check_value_init_fail(void)
> +{
> + struct value_init_fail_ctx ctx;
> + uint32_t status = 0;
> + struct value *value;
> + struct refmap *rfm;
> + struct key key;
> +
> + memset(&key, 0, sizeof key);
> + ctx = (struct value_init_fail_ctx) {
> + .should_fail = true,
> + .ptr = &status,
> + };
> +
> + rfm = refmap_create("value-init-fail", sizeof key, sizeof(struct value),
> + value_init_maybe_fail, value_uninit, NULL);
> + ovs_assert(rfm);
> +
> + ovs_assert(!refmap_ref(rfm, &key, &ctx));
> + ovs_assert(status == 0);
> + ovs_assert(!refmap_try_ref(rfm, &key));
> + check_refmap(rfm, NULL, 0);
> +
> + ctx.should_fail = false;
> + value = refmap_ref(rfm, &key, &ctx);
> + ovs_assert(value);
> + ovs_assert(status == 1);
> + ovs_assert(value->hdl == &status);
> + check_refmap(rfm, (struct value **) &value, 1);
> +
> + refmap_unref(rfm, value);
> + ovs_assert(status == 2);
> + ovs_assert(!refmap_try_ref(rfm, &key));
> + check_refmap(rfm, NULL, 0);
> +
> + refmap_destroy(rfm);
> +}
> +
> +/* If an object for a key is going down and another thread tries to ref the
> + * same key, a broken implementation could insert a replacement and run
> + * value_init before value_uninit on the old object has finished.
> + * value_lifecycle_state and tear_down_order_{value_init,value_uninit} detect
> + * that overlap.
> + */
End comment on the previous line.
> +static void
> +check_value_init_uninit_order(void)
> +{
> + struct try_ref_race_ctx race_ctx;
> + uint32_t arg_val = 0;
> + struct refmap *rfm;
> + unsigned int state;
> + pthread_t worker;
> + struct arg arg = { .ptr = &arg_val };
> +
> + atomic_init(&value_lifecycle_state, VALUE_LIFECYCLE_IDLE);
> +
> + rfm = refmap_create("init-uninit-order", sizeof(struct key),
> + sizeof(struct value), tear_down_order_value_init,
> + tear_down_order_value_uninit, NULL);
> + ovs_assert(rfm);
> +
> + memset(&race_ctx.key, 0, sizeof race_ctx.key);
> + race_ctx.key.idx = 0;
> + race_ctx.rfm = rfm;
> + atomic_init(&race_ctx.stop, false);
> +
> + worker = ovs_thread_create("init-uninit-order", try_ref_racer,
> &race_ctx);
> +
> + for (int i = 0; i < 10000; i++) {
> + void *value;
> +
> + arg_val = 0;
> + value = refmap_ref(rfm, &race_ctx.key, &arg);
> + refmap_unref(rfm, value);
> + }
> +
> + atomic_store(&race_ctx.stop, true);
> + xpthread_join(worker, NULL);
> +
> + check_refmap(rfm, NULL, 0);
> + atomic_read(&value_lifecycle_state, &state);
> + ovs_assert(state == VALUE_LIFECYCLE_IDLE);
> +
> + refmap_destroy(rfm);
> +}
[...]
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
