As discussed off list I'd like a comment explaining why we need the
free list. Other than that:
Acked-by: Ethan Jackson <et...@nicira.com>
On Mon, Jan 13, 2014 at 11:25 AM, Ben Pfaff <b...@nicira.com> wrote:
> A couple of times I've wanted to create a dynamic data structure that has
> thread-specific data, but I've not been able to do that because
> PTHREAD_KEYS_MAX is so low (POSIX says at least 128, glibc is only a little
> bigger at 1024). This commit introduces a new form of thread-specific data
> that supports a large number of items.
>
> Signed-off-by: Ben Pfaff <b...@nicira.com>
> ---
> lib/ovs-thread.c | 176
> +++++++++++++++++++++++++++++++++++++++++++++++++++++-
> lib/ovs-thread.h | 63 +++++++++++++++++--
> 2 files changed, 233 insertions(+), 6 deletions(-)
>
> diff --git a/lib/ovs-thread.c b/lib/ovs-thread.c
> index d35accb..6e6af98 100644
> --- a/lib/ovs-thread.c
> +++ b/lib/ovs-thread.c
> @@ -1,5 +1,5 @@
> /*
> - * Copyright (c) 2013 Nicira, Inc.
> + * Copyright (c) 2013, 2014 Nicira, Inc.
> *
> * Licensed under the Apache License, Version 2.0 (the "License");
> * you may not use this file except in compliance with the License.
> @@ -134,6 +134,7 @@ XPTHREAD_FUNC2(pthread_join, pthread_t, void **);
>
> typedef void destructor_func(void *);
> XPTHREAD_FUNC2(pthread_key_create, pthread_key_t *, destructor_func *);
> +XPTHREAD_FUNC1(pthread_key_delete, pthread_key_t);
> XPTHREAD_FUNC2(pthread_setspecific, pthread_key_t, const void *);
>
> static void
> @@ -467,3 +468,176 @@ count_cpu_cores(void)
> return n_cores > 0 ? n_cores : 0;
> }
> #endif
> +
> +/* ovsthread_key. */
> +
> +#define L1_SIZE 1024
> +#define L2_SIZE 1024
> +#define MAX_KEYS (L1_SIZE * L2_SIZE)
> +
> +struct ovsthread_key {
> + struct list list_node;
> + unsigned int index;
> + void (*destructor)(void *);
> +};
> +
> +struct ovsthread_key_slots {
> + struct list list_node;
> + void **p1[L1_SIZE];
> +};
> +
> +static pthread_key_t tsd_key;
> +
> +static struct ovs_mutex key_mutex = OVS_MUTEX_INITIALIZER;
> +
> +static struct list inuse_keys OVS_GUARDED_BY(key_mutex)
> + = LIST_INITIALIZER(&inuse_keys);
> +static struct list free_keys OVS_GUARDED_BY(key_mutex)
> + = LIST_INITIALIZER(&free_keys);
> +static unsigned int n_keys OVS_GUARDED_BY(key_mutex);
> +
> +static struct list slots_list OVS_GUARDED_BY(key_mutex)
> + = LIST_INITIALIZER(&slots_list);
> +
> +static void *
> +clear_slot(struct ovsthread_key_slots *slots, unsigned int index)
> +{
> + void **p2 = slots->p1[index / L2_SIZE];
> + if (p2) {
> + void **valuep = &p2[index % L2_SIZE];
> + void *value = *valuep;
> + *valuep = NULL;
> + return value;
> + } else {
> + return NULL;
> + }
> +}
> +
> +static void
> +ovsthread_key_destruct__(void *slots_)
> +{
> + struct ovsthread_key_slots *slots = slots_;
> + struct ovsthread_key *key;
> + unsigned int n;
> + int i;
> +
> + ovs_mutex_lock(&key_mutex);
> + list_remove(&slots->list_node);
> + LIST_FOR_EACH (key, list_node, &inuse_keys) {
> + void *value = clear_slot(slots, key->index);
> + if (value && key->destructor) {
> + key->destructor(value);
> + }
> + }
> + n = n_keys;
> + ovs_mutex_unlock(&key_mutex);
> +
> + for (i = 0; i < n / L2_SIZE; i++) {
> + free(slots->p1[i]);
> + }
> + free(slots);
> +}
> +
> +/* Initializes '*keyp' as a thread-specific data key. The data items are
> + * initially null in all threads.
> + *
> + * If a thread exits with non-null data, then 'destructor', if nonnull, will
> be
> + * called passing the final data value as its argument. 'destructor' must
> not
> + * call any thread-specific data functions in this API.
> + *
> + * This function is similar to xpthread_key_create(). */
> +void
> +ovsthread_key_create(ovsthread_key_t *keyp, void (*destructor)(void *))
> +{
> + static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
> + struct ovsthread_key *key;
> +
> + if (ovsthread_once_start(&once)) {
> + xpthread_key_create(&tsd_key, ovsthread_key_destruct__);
> + ovsthread_once_done(&once);
> + }
> +
> + ovs_mutex_lock(&key_mutex);
> + if (list_is_empty(&free_keys)) {
> + key = xmalloc(sizeof *key);
> + key->index = n_keys++;
> + if (key->index >= MAX_KEYS) {
> + abort();
> + }
> + } else {
> + key = CONTAINER_OF(list_pop_back(&free_keys),
> + struct ovsthread_key, list_node);
> + }
> + list_push_back(&inuse_keys, &key->list_node);
> + key->destructor = destructor;
> + ovs_mutex_unlock(&key_mutex);
> +
> + *keyp = key;
> +}
> +
> +/* Frees 'key'. The destructor supplied to ovsthread_key_create(), if any,
> is
> + * not called.
> + *
> + * This function is similar to xpthread_key_delete(). */
> +void
> +ovsthread_key_delete(ovsthread_key_t key)
> +{
> + struct ovsthread_key_slots *slots;
> +
> + ovs_mutex_lock(&key_mutex);
> +
> + /* Move 'key' from 'inuse_keys' to 'free_keys'. */
> + list_remove(&key->list_node);
> + list_push_back(&free_keys, &key->list_node);
> +
> + /* Clear this slot in all threads. */
> + LIST_FOR_EACH (slots, list_node, &slots_list) {
> + clear_slot(slots, key->index);
> + }
> +
> + ovs_mutex_unlock(&key_mutex);
> +}
> +
> +static void **
> +ovsthread_key_lookup__(const struct ovsthread_key *key)
> +{
> + struct ovsthread_key_slots *slots;
> + void **p2;
> +
> + slots = pthread_getspecific(tsd_key);
> + if (!slots) {
> + slots = xzalloc(sizeof *slots);
> +
> + ovs_mutex_lock(&key_mutex);
> + pthread_setspecific(tsd_key, slots);
> + list_push_back(&slots_list, &slots->list_node);
> + ovs_mutex_unlock(&key_mutex);
> + }
> +
> + p2 = slots->p1[key->index / L2_SIZE];
> + if (!p2) {
> + p2 = xzalloc(L2_SIZE * sizeof *p2);
> + slots->p1[key->index / L2_SIZE] = p2;
> + }
> +
> + return &p2[key->index % L2_SIZE];
> +}
> +
> +/* Sets the value of thread-specific data item 'key', in the current thread,
> to
> + * 'value'.
> + *
> + * This function is similar to pthread_setspecific(). */
> +void
> +ovsthread_setspecific(ovsthread_key_t key, const void *value)
> +{
> + *ovsthread_key_lookup__(key) = CONST_CAST(void *, value);
> +}
> +
> +/* Returns the value of thread-specific data item 'key' in the current
> thread.
> + *
> + * This function is similar to pthread_getspecific(). */
> +void *
> +ovsthread_getspecific(ovsthread_key_t key)
> +{
> + return *ovsthread_key_lookup__(key);
> +}
> diff --git a/lib/ovs-thread.h b/lib/ovs-thread.h
> index a3e2696..8cf2ecc 100644
> --- a/lib/ovs-thread.h
> +++ b/lib/ovs-thread.h
> @@ -1,5 +1,5 @@
> /*
> - * Copyright (c) 2013 Nicira, Inc.
> + * Copyright (c) 2013, 2014 Nicira, Inc.
> *
> * Licensed under the Apache License, Version 2.0 (the "License");
> * you may not use this file except in compliance with the License.
> @@ -127,6 +127,7 @@ void xpthread_cond_broadcast(pthread_cond_t *);
> #endif
>
> void xpthread_key_create(pthread_key_t *, void (*destructor)(void *));
> +void xpthread_key_delete(pthread_key_t);
> void xpthread_setspecific(pthread_key_t, const void *);
>
> void xpthread_create(pthread_t *, pthread_attr_t *, void *(*)(void *), void
> *);
> @@ -134,14 +135,21 @@ void xpthread_join(pthread_t, void **);
>
> /* Per-thread data.
> *
> - * Multiple forms of per-thread data exist, each with its own pluses and
> - * minuses:
> + *
> + * Standard Forms
> + * ==============
> + *
> + * Multiple forms of standard per-thread data exist, each with its own pluses
> + * and minuses. In general, if one of these forms is appropriate, then it's
> a
> + * good idea to use it:
> *
> * - POSIX per-thread data via pthread_key_t is portable to any pthreads
> * implementation, and allows a destructor function to be defined. It
> * only (directly) supports per-thread pointers, which are always
> * initialized to NULL. It requires once-only allocation of a
> - * pthread_key_t value. It is relatively slow.
> + * pthread_key_t value. It is relatively slow. Typically few
> + * "pthread_key_t"s are available (POSIX requires only at least 128,
> + * glibc supplies only 1024).
> *
> * - The thread_local feature newly defined in C11 <threads.h> works with
> * any data type and initializer, and it is fast. thread_local does
> not
> @@ -149,7 +157,8 @@ void xpthread_join(pthread_t, void **);
> * define what happens if one attempts to access a thread_local object
> * from a thread other than the one to which that object belongs.
> There
> * is no provision to call a user-specified destructor when a thread
> - * ends.
> + * ends. Typical implementations allow for an arbitrary amount of
> + * thread_local storage, but statically allocated only.
> *
> * - The __thread keyword is a GCC extension similar to thread_local but
> * with a longer history. __thread is not portable to every GCC
> version
> @@ -166,6 +175,25 @@ void xpthread_join(pthread_t, void **);
> * needs key allocation? yes no no
> * arbitrary initializer? no yes yes
> * cross-thread access? yes no yes
> + * amount available? few arbitrary arbitrary
> + * dynamically allocated? yes no no
> + *
> + *
> + * Extensions
> + * ==========
> + *
> + * OVS provides some extensions and wrappers:
> + *
> + * - In a situation where the performance of thread_local or __thread is
> + * desirable, but portability is required,
> DEFINE_STATIC_PER_THREAD_DATA
> + * and DECLARE_EXTERN_PER_THREAD_DATA/DEFINE_EXTERN_PER_THREAD_DATA may
> + * be appropriate (see below).
> + *
> + * - DEFINE_PER_THREAD_MALLOCED_DATA can be convenient for simple
> + * per-thread malloc()'d buffers.
> + *
> + * - struct ovs_tsd provides an alternative to pthread_key_t that isn't
> + * limited to a small number of keys.
> */
>
> /* For static data, use this macro in a source file:
> @@ -402,6 +430,31 @@ void xpthread_join(pthread_t, void **);
> NAME##_init(); \
> return NAME##_set_unsafe(value); \
> }
> +
> +/* Dynamically allocated thread-specific data with lots of slots.
> + *
> + * pthread_key_t can provide as few as 128 pieces of thread-specific data
> (even
> + * glibc is limited to 1,024). Thus, one must be careful to allocate only a
> + * few keys globally. One cannot, for example, allocate a key for every
> + * instance of a data structure if there might be an arbitrary number of
> those
> + * data structures.
> + *
> + * This API is similar to the pthread one (simply search and replace pthread_
> + * by ovsthread_) but it a much larger limit that can be raised if necessary
> + * (by recompiling). Thus, one may more freely use this form of
> + * thread-specific data.
> + *
> + * Compared to pthread_key_t, ovsthread_key_t has the follow limitations:
> + *
> + * - Destructors must not access thread-specific data (via ovsthread_key).
> + */
> +typedef struct ovsthread_key *ovsthread_key_t;
> +
> +void ovsthread_key_create(ovsthread_key_t *, void (*destructor)(void *));
> +void ovsthread_key_delete(ovsthread_key_t);
> +
> +void ovsthread_setspecific(ovsthread_key_t, const void *);
> +void *ovsthread_getspecific(ovsthread_key_t);
>
> /* Convenient once-only execution.
> *
> --
> 1.7.10.4
>
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
