X-Git-Url: https://git.lttng.org/?a=blobdiff_plain;f=src%2Fcommon%2Fhashtable%2Fhashtable.c;h=404734f544895a8b9463fe2673136ad75d38e6de;hb=a0377dfefe40662ba7d68617bce6ff467114136c;hp=07210fa8161e63e41a6ea12c061812b27c94d1c8;hpb=efa116c6f19ecdc344a82709e7d919703ec96c45;p=lttng-tools.git diff --git a/src/common/hashtable/hashtable.c b/src/common/hashtable/hashtable.c index 07210fa81..404734f54 100644 --- a/src/common/hashtable/hashtable.c +++ b/src/common/hashtable/hashtable.c @@ -1,22 +1,11 @@ /* - * Copyright (C) 2011 - David Goulet + * Copyright (C) 2011 David Goulet * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License, version 2 only, - * as published by the Free Software Foundation. + * SPDX-License-Identifier: GPL-2.0-only * - * This program is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for - * more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ -#define _GNU_SOURCE -#include +#define _LGPL_SOURCE #include #include #include @@ -27,11 +16,21 @@ #include "hashtable.h" #include "utils.h" +/* seed_lock protects both seed_init and lttng_ht_seed. */ +static pthread_mutex_t seed_lock = PTHREAD_MUTEX_INITIALIZER; +static bool seed_init; unsigned long lttng_ht_seed; static unsigned long min_hash_alloc_size = 1; static unsigned long max_hash_buckets_size = 0; +/* + * Getter/lookup functions need to be called with RCU read-side lock + * held. However, modification functions (add, add_unique, replace, del) + * take the RCU lock internally, so it does not matter whether the + * caller hold the RCU lock or not. + */ + /* * Match function for string node. */ @@ -65,9 +64,39 @@ static int match_u64(struct cds_lfht_node *node, const void *key) return hash_match_key_u64(&match_node->key, (void *) key); } +/* + * Match function for two uint64_t node. + */ +static int match_two_u64(struct cds_lfht_node *node, const void *key) +{ + struct lttng_ht_node_two_u64 *match_node = + caa_container_of(node, struct lttng_ht_node_two_u64, node); + + return hash_match_key_two_u64((void *) &match_node->key, (void *) key); +} + +static inline +const char *lttng_ht_type_str(enum lttng_ht_type type) +{ + switch (type) { + case LTTNG_HT_TYPE_STRING: + return "STRING"; + case LTTNG_HT_TYPE_ULONG: + return "ULONG"; + case LTTNG_HT_TYPE_U64: + return "U64"; + case LTTNG_HT_TYPE_TWO_U64: + return "TWO_U64"; + default: + ERR("Unknown lttng hashtable type %d", type); + abort(); + } +} + /* * Return an allocated lttng hashtable. */ +LTTNG_HIDDEN struct lttng_ht *lttng_ht_new(unsigned long size, int type) { struct lttng_ht *ht; @@ -76,6 +105,13 @@ struct lttng_ht *lttng_ht_new(unsigned long size, int type) if (!size) size = DEFAULT_HT_SIZE; + pthread_mutex_lock(&seed_lock); + if (!seed_init) { + lttng_ht_seed = (unsigned long) time(NULL); + seed_init = true; + } + pthread_mutex_unlock(&seed_lock); + ht = zmalloc(sizeof(*ht)); if (ht == NULL) { PERROR("zmalloc lttng_ht"); @@ -88,7 +124,7 @@ struct lttng_ht *lttng_ht_new(unsigned long size, int type) * There is already an assert in the RCU hashtable code so if the ht is * NULL here there is a *huge* problem. */ - assert(ht->ht); + LTTNG_ASSERT(ht->ht); switch (type) { case LTTNG_HT_TYPE_STRING: @@ -103,13 +139,18 @@ struct lttng_ht *lttng_ht_new(unsigned long size, int type) ht->match_fct = match_u64; ht->hash_fct = hash_key_u64; break; + case LTTNG_HT_TYPE_TWO_U64: + ht->match_fct = match_two_u64; + ht->hash_fct = hash_key_two_u64; + break; default: ERR("Unknown lttng hashtable type %d", type); lttng_ht_destroy(ht); goto error; } - DBG3("Created hashtable size %lu at %p of type %d", size, ht->ht, type); + DBG3("Created hashtable size %lu at %p of type %s", size, ht->ht, + lttng_ht_type_str(type)); return ht; @@ -120,21 +161,23 @@ error: /* * Free a lttng hashtable. */ +LTTNG_HIDDEN void lttng_ht_destroy(struct lttng_ht *ht) { int ret; ret = cds_lfht_destroy(ht->ht, NULL); - assert(!ret); + LTTNG_ASSERT(!ret); free(ht); } /* * Init lttng ht node string. */ +LTTNG_HIDDEN void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key) { - assert(node); + LTTNG_ASSERT(node); node->key = key; cds_lfht_node_init(&node->node); @@ -143,10 +186,11 @@ void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key) /* * Init lttng ht node unsigned long. */ +LTTNG_HIDDEN void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node, unsigned long key) { - assert(node); + LTTNG_ASSERT(node); node->key = key; cds_lfht_node_init(&node->node); @@ -155,50 +199,79 @@ void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node, /* * Init lttng ht node uint64_t. */ +LTTNG_HIDDEN void lttng_ht_node_init_u64(struct lttng_ht_node_u64 *node, uint64_t key) { - assert(node); + LTTNG_ASSERT(node); node->key = key; cds_lfht_node_init(&node->node); } +/* + * Init lttng ht node with two uint64_t. + */ +LTTNG_HIDDEN +void lttng_ht_node_init_two_u64(struct lttng_ht_node_two_u64 *node, + uint64_t key1, uint64_t key2) +{ + LTTNG_ASSERT(node); + + node->key.key1 = key1; + node->key.key2 = key2; + cds_lfht_node_init(&node->node); +} + /* * Free lttng ht node string. */ +LTTNG_HIDDEN void lttng_ht_node_free_str(struct lttng_ht_node_str *node) { - assert(node); + LTTNG_ASSERT(node); free(node); } /* * Free lttng ht node unsigned long. */ +LTTNG_HIDDEN void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node) { - assert(node); + LTTNG_ASSERT(node); free(node); } /* * Free lttng ht node uint64_t. */ +LTTNG_HIDDEN void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node) { - assert(node); + LTTNG_ASSERT(node); + free(node); +} + +/* + * Free lttng ht node two uint64_t. + */ +LTTNG_HIDDEN +void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node) +{ + LTTNG_ASSERT(node); free(node); } /* * Lookup function in hashtable. */ -void lttng_ht_lookup(struct lttng_ht *ht, void *key, +LTTNG_HIDDEN +void lttng_ht_lookup(struct lttng_ht *ht, const void *key, struct lttng_ht_iter *iter) { - assert(ht); - assert(ht->ht); + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed), ht->match_fct, key, &iter->iter); @@ -207,158 +280,218 @@ void lttng_ht_lookup(struct lttng_ht *ht, void *key, /* * Add unique string node to hashtable. */ +LTTNG_HIDDEN void lttng_ht_add_unique_str(struct lttng_ht *ht, struct lttng_ht_node_str *node) { struct cds_lfht_node *node_ptr; - assert(ht); - assert(ht->ht); - assert(node); + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + LTTNG_ASSERT(node); + /* RCU read lock protects from ABA. */ + rcu_read_lock(); node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, lttng_ht_seed), ht->match_fct, node->key, &node->node); - assert(node_ptr == &node->node); + rcu_read_unlock(); + LTTNG_ASSERT(node_ptr == &node->node); } /* * Add string node to hashtable. */ +LTTNG_HIDDEN void lttng_ht_add_str(struct lttng_ht *ht, struct lttng_ht_node_str *node) { - assert(ht); - assert(ht->ht); - assert(node); + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + LTTNG_ASSERT(node); + /* RCU read lock protects from ABA. */ + rcu_read_lock(); cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed), &node->node); + rcu_read_unlock(); } /* * Add unsigned long node to hashtable. */ +LTTNG_HIDDEN void lttng_ht_add_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node) { - assert(ht); - assert(ht->ht); - assert(node); + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + LTTNG_ASSERT(node); + /* RCU read lock protects from ABA. */ + rcu_read_lock(); cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed), &node->node); + rcu_read_unlock(); } /* * Add uint64_t node to hashtable. - */ +LTTNG_HIDDEN void lttng_ht_add_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node) { - assert(ht); - assert(ht->ht); - assert(node); + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + LTTNG_ASSERT(node); + /* RCU read lock protects from ABA. */ + rcu_read_lock(); cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed), &node->node); + rcu_read_unlock(); } /* * Add unique unsigned long node to hashtable. */ +LTTNG_HIDDEN void lttng_ht_add_unique_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node) { struct cds_lfht_node *node_ptr; - assert(ht); - assert(ht->ht); - assert(node); + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + LTTNG_ASSERT(node); + /* RCU read lock protects from ABA. */ + rcu_read_lock(); node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct, (void *) node->key, &node->node); - assert(node_ptr == &node->node); + rcu_read_unlock(); + LTTNG_ASSERT(node_ptr == &node->node); } /* * Add unique uint64_t node to hashtable. */ +LTTNG_HIDDEN void lttng_ht_add_unique_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node) { struct cds_lfht_node *node_ptr; - assert(ht); - assert(ht->ht); - assert(node); + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + LTTNG_ASSERT(node); + /* RCU read lock protects from ABA. */ + rcu_read_lock(); node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct, &node->key, &node->node); - assert(node_ptr == &node->node); + rcu_read_unlock(); + LTTNG_ASSERT(node_ptr == &node->node); +} + +/* + * Add unique two uint64_t node to hashtable. + */ +LTTNG_HIDDEN +void lttng_ht_add_unique_two_u64(struct lttng_ht *ht, + struct lttng_ht_node_two_u64 *node) +{ + struct cds_lfht_node *node_ptr; + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + LTTNG_ASSERT(node); + + /* RCU read lock protects from ABA. */ + rcu_read_lock(); + node_ptr = cds_lfht_add_unique(ht->ht, + ht->hash_fct((void *) &node->key, lttng_ht_seed), ht->match_fct, + (void *) &node->key, &node->node); + rcu_read_unlock(); + LTTNG_ASSERT(node_ptr == &node->node); } /* * Add replace unsigned long node to hashtable. */ +LTTNG_HIDDEN struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node) { struct cds_lfht_node *node_ptr; - assert(ht); - assert(ht->ht); - assert(node); + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + LTTNG_ASSERT(node); + /* RCU read lock protects from ABA. */ + rcu_read_lock(); node_ptr = cds_lfht_add_replace(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct, (void *) node->key, &node->node); + rcu_read_unlock(); if (!node_ptr) { return NULL; } else { return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node); } - assert(node_ptr == &node->node); + LTTNG_ASSERT(node_ptr == &node->node); } /* * Add replace unsigned long node to hashtable. */ +LTTNG_HIDDEN struct lttng_ht_node_u64 *lttng_ht_add_replace_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node) { struct cds_lfht_node *node_ptr; - assert(ht); - assert(ht->ht); - assert(node); + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + LTTNG_ASSERT(node); + /* RCU read lock protects from ABA. */ + rcu_read_lock(); node_ptr = cds_lfht_add_replace(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct, &node->key, &node->node); + rcu_read_unlock(); if (!node_ptr) { return NULL; } else { return caa_container_of(node_ptr, struct lttng_ht_node_u64, node); } - assert(node_ptr == &node->node); + LTTNG_ASSERT(node_ptr == &node->node); } /* * Delete node from hashtable. */ +LTTNG_HIDDEN int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter) { - assert(ht); - assert(ht->ht); - assert(iter); + int ret; + + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + LTTNG_ASSERT(iter); - return cds_lfht_del(ht->ht, iter->iter.node); + /* RCU read lock protects from ABA. */ + rcu_read_lock(); + ret = cds_lfht_del(ht->ht, iter->iter.node); + rcu_read_unlock(); + return ret; } /* * Get first node in the hashtable. */ +LTTNG_HIDDEN void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter) { - assert(ht); - assert(ht->ht); - assert(iter); + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + LTTNG_ASSERT(iter); cds_lfht_first(ht->ht, &iter->iter); } @@ -366,11 +499,12 @@ void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter) /* * Get next node in the hashtable. */ +LTTNG_HIDDEN void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter) { - assert(ht); - assert(ht->ht); - assert(iter); + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + LTTNG_ASSERT(iter); cds_lfht_next(ht->ht, &iter->iter); } @@ -378,15 +512,19 @@ void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter) /* * Return the number of nodes in the hashtable. */ +LTTNG_HIDDEN unsigned long lttng_ht_get_count(struct lttng_ht *ht) { long scb, sca; unsigned long count; - assert(ht); - assert(ht->ht); + LTTNG_ASSERT(ht); + LTTNG_ASSERT(ht->ht); + /* RCU read lock protects from ABA and allows RCU traversal. */ + rcu_read_lock(); cds_lfht_count_nodes(ht->ht, &scb, &count, &sca); + rcu_read_unlock(); return count; } @@ -394,12 +532,13 @@ unsigned long lttng_ht_get_count(struct lttng_ht *ht) /* * Return lttng ht string node from iterator. */ +LTTNG_HIDDEN struct lttng_ht_node_str *lttng_ht_iter_get_node_str( struct lttng_ht_iter *iter) { struct cds_lfht_node *node; - assert(iter); + LTTNG_ASSERT(iter); node = cds_lfht_iter_get_node(&iter->iter); if (!node) { return NULL; @@ -410,12 +549,13 @@ struct lttng_ht_node_str *lttng_ht_iter_get_node_str( /* * Return lttng ht unsigned long node from iterator. */ +LTTNG_HIDDEN struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong( struct lttng_ht_iter *iter) { struct cds_lfht_node *node; - assert(iter); + LTTNG_ASSERT(iter); node = cds_lfht_iter_get_node(&iter->iter); if (!node) { return NULL; @@ -426,12 +566,13 @@ struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong( /* * Return lttng ht unsigned long node from iterator. */ +LTTNG_HIDDEN struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64( struct lttng_ht_iter *iter) { struct cds_lfht_node *node; - assert(iter); + LTTNG_ASSERT(iter); node = cds_lfht_iter_get_node(&iter->iter); if (!node) { return NULL; @@ -440,10 +581,18 @@ struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64( } /* - * lib constructor + * Return lttng ht stream and index id node from iterator. */ -static void __attribute__((constructor)) _init(void) +LTTNG_HIDDEN +struct lttng_ht_node_two_u64 *lttng_ht_iter_get_node_two_u64( + struct lttng_ht_iter *iter) { - /* Init hash table seed */ - lttng_ht_seed = (unsigned long) time(NULL); + struct cds_lfht_node *node; + + LTTNG_ASSERT(iter); + node = cds_lfht_iter_get_node(&iter->iter); + if (!node) { + return NULL; + } + return caa_container_of(node, struct lttng_ht_node_two_u64, node); }