From 34b3f359c81e6400c9b451e49bf9dfaef7963509 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 23 Jun 2013 14:16:45 -0400 Subject: [PATCH] doc/examples: cds_lfht_add_replace Signed-off-by: Mathieu Desnoyers --- .gitignore | 1 + doc/examples/Makefile.am | 2 + doc/examples/rculfhash/Makefile | 2 + .../rculfhash/Makefile.cds_lfht_add_replace | 22 +++ doc/examples/rculfhash/cds_lfht_add_replace.c | 147 ++++++++++++++++++ doc/examples/rculfhash/cds_lfht_add_unique.c | 5 +- doc/examples/rculfhash/cds_lfht_del.c | 14 ++ 7 files changed, 191 insertions(+), 2 deletions(-) create mode 100644 doc/examples/rculfhash/Makefile.cds_lfht_add_replace create mode 100644 doc/examples/rculfhash/cds_lfht_add_replace.c diff --git a/.gitignore b/.gitignore index 0286f0a..9767ac3 100644 --- a/.gitignore +++ b/.gitignore @@ -108,6 +108,7 @@ doc/examples/lfstack/cds_lfs_pop_all_blocking doc/examples/rculfhash/cds_lfht_add doc/examples/rculfhash/cds_lfht_add_unique +doc/examples/rculfhash/cds_lfht_add_replace doc/examples/rculfhash/cds_lfht_del #automake diff --git a/doc/examples/Makefile.am b/doc/examples/Makefile.am index 60848e9..bf19016 100644 --- a/doc/examples/Makefile.am +++ b/doc/examples/Makefile.am @@ -98,9 +98,11 @@ dist_doc_examples_rculfhash_DATA = \ rculfhash/jhash.h \ rculfhash/Makefile.cds_lfht_add \ rculfhash/Makefile.cds_lfht_add_unique \ + rculfhash/Makefile.cds_lfht_add_replace \ rculfhash/Makefile.cds_lfht_del \ rculfhash/cds_lfht_add.c \ rculfhash/cds_lfht_add_unique.c \ + rculfhash/cds_lfht_add_replace.c \ rculfhash/cds_lfht_del.c if NO_SHARED diff --git a/doc/examples/rculfhash/Makefile b/doc/examples/rculfhash/Makefile index 009aa7c..52da737 100644 --- a/doc/examples/rculfhash/Makefile +++ b/doc/examples/rculfhash/Makefile @@ -14,10 +14,12 @@ all: $(MAKE) -f Makefile.cds_lfht_add $(MAKE) -f Makefile.cds_lfht_add_unique + $(MAKE) -f Makefile.cds_lfht_add_replace $(MAKE) -f Makefile.cds_lfht_del .PHONY: clean clean: $(MAKE) -f Makefile.cds_lfht_add clean $(MAKE) -f Makefile.cds_lfht_add_unique clean + $(MAKE) -f Makefile.cds_lfht_add_replace clean $(MAKE) -f Makefile.cds_lfht_del clean diff --git a/doc/examples/rculfhash/Makefile.cds_lfht_add_replace b/doc/examples/rculfhash/Makefile.cds_lfht_add_replace new file mode 100644 index 0000000..dcd253a --- /dev/null +++ b/doc/examples/rculfhash/Makefile.cds_lfht_add_replace @@ -0,0 +1,22 @@ +# Copyright (C) 2013 Mathieu Desnoyers +# +# THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED +# OR IMPLIED. ANY USE IS AT YOUR OWN RISK. +# +# Permission is hereby granted to use or copy this program for any +# purpose, provided the above notices are retained on all copies. +# Permission to modify the code and to distribute modified code is +# granted, provided the above notices are retained, and a notice that +# the code was modified is included with the above copyright notice. +# +# This makefile is purposefully kept simple to support GNU and BSD make. + +EXAMPLE_NAME = cds_lfht_add_replace + +SOURCES = $(EXAMPLE_NAME).c +DEPS = jhash.h +OBJECTS = $(EXAMPLE_NAME).o +BINARY = $(EXAMPLE_NAME) +LIBS = -lurcu-cds -lurcu + +include ../Makefile.examples.template diff --git a/doc/examples/rculfhash/cds_lfht_add_replace.c b/doc/examples/rculfhash/cds_lfht_add_replace.c new file mode 100644 index 0000000..62de40c --- /dev/null +++ b/doc/examples/rculfhash/cds_lfht_add_replace.c @@ -0,0 +1,147 @@ +/* + * Copyright (C) 2013 Mathieu Desnoyers + * + * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED + * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. + * + * Permission is hereby granted to use or copy this program for any + * purpose, provided the above notices are retained on all copies. + * Permission to modify the code and to distribute modified code is + * granted, provided the above notices are retained, and a notice that + * the code was modified is included with the above copyright notice. + * + * This example shows how to add nodes into a RCU lock-free hash table + * with cds_lfht_add_replace(), which replaces existing nodes with the + * same key if found. + * We use a "seqnum" field to show which node is staying in the hash + * table. This hash table requires using a RCU scheme. + */ + +#include +#include +#include + +#include /* RCU flavor */ +#include /* RCU Lock-free hash table */ +#include /* For CAA_ARRAY_SIZE */ +#include "jhash.h" /* Example hash function */ + +/* + * Nodes populated into the hash table. + */ +struct mynode { + int value; /* Node content */ + int seqnum; /* Our node sequence number */ + struct cds_lfht_node node; /* Chaining in hash table */ + struct rcu_head rcu_head; /* For call_rcu() */ +}; + +static +int match(struct cds_lfht_node *ht_node, const void *_key) +{ + struct mynode *node = + caa_container_of(ht_node, struct mynode, node); + const unsigned int *key = _key; + + return *key == node->value; +} + +static +void free_node(struct rcu_head *head) +{ + struct mynode *node = caa_container_of(head, struct mynode, rcu_head); + + free(node); +} + +int main(int argc, char **argv) +{ + int values[] = { -5, 42, 42, 36, 24, }; /* 42 is duplicated */ + struct cds_lfht *ht; /* Hash table */ + unsigned int i; + int ret = 0, seqnum = 0; + uint32_t seed; + struct cds_lfht_iter iter; /* For iteration on hash table */ + struct cds_lfht_node *ht_node; + struct mynode *node; + + /* + * Each thread need using RCU read-side need to be explicitly + * registered. + */ + rcu_register_thread(); + + /* Use time as seed for hash table hashing. */ + seed = (uint32_t) time(NULL); + + /* + * Allocate hash table. + */ + ht = cds_lfht_new(1, 1, 0, + CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, + NULL); + if (!ht) { + printf("Error allocating hash table\n"); + ret = -1; + goto end; + } + + /* + * Add nodes to hash table. + */ + for (i = 0; i < CAA_ARRAY_SIZE(values); i++) { + unsigned long hash; + int value; + + node = malloc(sizeof(*node)); + if (!node) { + ret = -1; + goto end; + } + + cds_lfht_node_init(&node->node); + value = values[i]; + node->value = value; + node->seqnum = seqnum++; + hash = jhash(&value, sizeof(value), seed); + + /* + * cds_lfht_add() needs to be called from RCU read-side + * critical section. + */ + rcu_read_lock(); + ht_node = cds_lfht_add_replace(ht, hash, match, &value, + &node->node); + if (ht_node) { + struct mynode *ret_node = + caa_container_of(ht_node, struct mynode, node); + + printf("Replaced node (key: %d, seqnum: %d) by (key: %d, seqnum: %d)\n", + ret_node->value, ret_node->seqnum, + node->value, node->seqnum); + call_rcu(&ret_node->rcu_head, free_node); + } else { + printf("Add (key: %d, seqnum: %d)\n", + node->value, node->seqnum); + } + rcu_read_unlock(); + } + + /* + * Iterate over each hash table node. Those will appear in + * random order, depending on the hash seed. Iteration needs to + * be performed within RCU read-side critical section. + */ + printf("hash table content (random order):"); + rcu_read_lock(); + cds_lfht_for_each_entry(ht, &iter, node, node) { + printf(" (key: %d, seqnum: %d)", + node->value, node->seqnum); + } + rcu_read_unlock(); + printf("\n"); + +end: + rcu_unregister_thread(); + return ret; +} diff --git a/doc/examples/rculfhash/cds_lfht_add_unique.c b/doc/examples/rculfhash/cds_lfht_add_unique.c index ec594c8..f1a7631 100644 --- a/doc/examples/rculfhash/cds_lfht_add_unique.c +++ b/doc/examples/rculfhash/cds_lfht_add_unique.c @@ -33,6 +33,7 @@ struct mynode { struct cds_lfht_node node; /* Chaining in hash table */ }; +static int match(struct cds_lfht_node *ht_node, const void *_key) { struct mynode *node = @@ -113,11 +114,11 @@ int main(int argc, char **argv) * match. It did not add the new node to the * hash table, so we can free it on the spot. */ - printf("Not adding duplicate key: %d, seqnum: %d\n", + printf("Not adding duplicate (key: %d, seqnum: %d)\n", node->value, node->seqnum); free(node); } else { - printf("Add key: %d, seqnum: %d\n", + printf("Add (key: %d, seqnum: %d)\n", node->value, node->seqnum); } rcu_read_unlock(); diff --git a/doc/examples/rculfhash/cds_lfht_del.c b/doc/examples/rculfhash/cds_lfht_del.c index d5a7264..4bcf15c 100644 --- a/doc/examples/rculfhash/cds_lfht_del.c +++ b/doc/examples/rculfhash/cds_lfht_del.c @@ -32,6 +32,7 @@ struct mynode { struct rcu_head rcu_head; /* For call_rcu() */ }; +static int match(struct cds_lfht_node *ht_node, const void *_key) { struct mynode *node = @@ -41,6 +42,14 @@ int match(struct cds_lfht_node *ht_node, const void *_key) return *key == node->value; } +static +void free_node(struct rcu_head *head) +{ + struct mynode *node = caa_container_of(head, struct mynode, rcu_head); + + free(node); +} + int main(int argc, char **argv) { int values[] = { -5, 42, 42, 36, 24, }; /* 42 is duplicated */ @@ -132,6 +141,11 @@ int main(int argc, char **argv) ret = cds_lfht_del(ht, ht_node); if (ret) { printf(" (concurrently deleted)"); + } else { + struct mynode *del_node = + caa_container_of(ht_node, + struct mynode, node); + call_rcu(&del_node->rcu_head, free_node); } } else { printf(" (not found)"); -- 2.34.1