From 474190bf1a9025850c14aa67eb88ba9815bb74f4 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sat, 22 Jun 2013 12:06:00 -0400 Subject: [PATCH] doc/examples: hlist Signed-off-by: Mathieu Desnoyers --- .gitignore | 5 + doc/examples/Makefile.am | 15 ++- doc/examples/hlist/Makefile | 25 +++++ .../hlist/Makefile.cds_hlist_add_head_rcu | 21 +++++ doc/examples/hlist/Makefile.cds_hlist_del_rcu | 21 +++++ .../Makefile.cds_hlist_for_each_entry_rcu | 21 +++++ .../hlist/Makefile.cds_hlist_for_each_rcu | 21 +++++ doc/examples/hlist/cds_hlist_add_head_rcu.c | 64 +++++++++++++ doc/examples/hlist/cds_hlist_del_rcu.c | 90 ++++++++++++++++++ .../hlist/cds_hlist_for_each_entry_rcu.c | 84 +++++++++++++++++ doc/examples/hlist/cds_hlist_for_each_rcu.c | 91 +++++++++++++++++++ 11 files changed, 457 insertions(+), 1 deletion(-) create mode 100644 doc/examples/hlist/Makefile create mode 100644 doc/examples/hlist/Makefile.cds_hlist_add_head_rcu create mode 100644 doc/examples/hlist/Makefile.cds_hlist_del_rcu create mode 100644 doc/examples/hlist/Makefile.cds_hlist_for_each_entry_rcu create mode 100644 doc/examples/hlist/Makefile.cds_hlist_for_each_rcu create mode 100644 doc/examples/hlist/cds_hlist_add_head_rcu.c create mode 100644 doc/examples/hlist/cds_hlist_del_rcu.c create mode 100644 doc/examples/hlist/cds_hlist_for_each_entry_rcu.c create mode 100644 doc/examples/hlist/cds_hlist_for_each_rcu.c diff --git a/.gitignore b/.gitignore index 58c9ba3..f9ab327 100644 --- a/.gitignore +++ b/.gitignore @@ -82,6 +82,11 @@ doc/examples/list/cds_list_for_each_rcu doc/examples/list/cds_list_for_each_entry_rcu doc/examples/list/cds_list_replace_rcu +doc/examples/hlist/cds_hlist_add_head_rcu +doc/examples/hlist/cds_hlist_del_rcu +doc/examples/hlist/cds_hlist_for_each_rcu +doc/examples/hlist/cds_hlist_for_each_entry_rcu + doc/examples/wfcqueue/cds_wfcq_enqueue doc/examples/wfcqueue/cds_wfcq_dequeue doc/examples/wfcqueue/cds_wfcq_splice diff --git a/doc/examples/Makefile.am b/doc/examples/Makefile.am index 9471957..d516bb6 100644 --- a/doc/examples/Makefile.am +++ b/doc/examples/Makefile.am @@ -26,6 +26,19 @@ dist_doc_examples_list_DATA = \ list/cds_list_for_each_entry_rcu.c \ list/cds_list_replace_rcu.c +doc_examples_hlistdir = ${doc_examplesdir}/hlist + +dist_doc_examples_hlist_DATA = \ + hlist/Makefile \ + hlist/Makefile.cds_hlist_add_head_rcu \ + hlist/Makefile.cds_hlist_del_rcu \ + hlist/Makefile.cds_hlist_for_each_rcu \ + hlist/Makefile.cds_hlist_for_each_entry_rcu \ + hlist/cds_hlist_add_head_rcu.c \ + hlist/cds_hlist_del_rcu.c \ + hlist/cds_hlist_for_each_rcu.c \ + hlist/cds_hlist_for_each_entry_rcu.c + doc_examples_wfcqueuedir = ${doc_examplesdir}/wfcqueue dist_doc_examples_wfcqueue_DATA = \ @@ -63,7 +76,7 @@ if NO_SHARED # Don't build examples if shared libraries support was explicitly # disabled. else -SUBDIRS_PROXY = qsbr-minimal list wfcqueue wfstack +SUBDIRS_PROXY = qsbr-minimal list hlist wfcqueue wfstack lfstack all-local: for subdir in $(SUBDIRS_PROXY); do \ diff --git a/doc/examples/hlist/Makefile b/doc/examples/hlist/Makefile new file mode 100644 index 0000000..d705dac --- /dev/null +++ b/doc/examples/hlist/Makefile @@ -0,0 +1,25 @@ +# 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. + +all: + $(MAKE) -f Makefile.cds_hlist_add_head_rcu + $(MAKE) -f Makefile.cds_hlist_del_rcu + $(MAKE) -f Makefile.cds_hlist_for_each_rcu + $(MAKE) -f Makefile.cds_hlist_for_each_entry_rcu + +.PHONY: clean +clean: + $(MAKE) -f Makefile.cds_hlist_add_head_rcu clean + $(MAKE) -f Makefile.cds_hlist_del_rcu clean + $(MAKE) -f Makefile.cds_hlist_for_each_rcu clean + $(MAKE) -f Makefile.cds_hlist_for_each_entry_rcu clean diff --git a/doc/examples/hlist/Makefile.cds_hlist_add_head_rcu b/doc/examples/hlist/Makefile.cds_hlist_add_head_rcu new file mode 100644 index 0000000..f1bf7d7 --- /dev/null +++ b/doc/examples/hlist/Makefile.cds_hlist_add_head_rcu @@ -0,0 +1,21 @@ +# 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_hlist_add_head_rcu + +SOURCES = $(EXAMPLE_NAME).c +OBJECTS = $(EXAMPLE_NAME).o +BINARY = $(EXAMPLE_NAME) +LIBS = -lurcu + +include ../Makefile.examples.template diff --git a/doc/examples/hlist/Makefile.cds_hlist_del_rcu b/doc/examples/hlist/Makefile.cds_hlist_del_rcu new file mode 100644 index 0000000..642b04d --- /dev/null +++ b/doc/examples/hlist/Makefile.cds_hlist_del_rcu @@ -0,0 +1,21 @@ +# 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_hlist_del_rcu + +SOURCES = $(EXAMPLE_NAME).c +OBJECTS = $(EXAMPLE_NAME).o +BINARY = $(EXAMPLE_NAME) +LIBS = -lurcu + +include ../Makefile.examples.template diff --git a/doc/examples/hlist/Makefile.cds_hlist_for_each_entry_rcu b/doc/examples/hlist/Makefile.cds_hlist_for_each_entry_rcu new file mode 100644 index 0000000..035ecbf --- /dev/null +++ b/doc/examples/hlist/Makefile.cds_hlist_for_each_entry_rcu @@ -0,0 +1,21 @@ +# 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_hlist_for_each_entry_rcu + +SOURCES = $(EXAMPLE_NAME).c +OBJECTS = $(EXAMPLE_NAME).o +BINARY = $(EXAMPLE_NAME) +LIBS = -lurcu + +include ../Makefile.examples.template diff --git a/doc/examples/hlist/Makefile.cds_hlist_for_each_rcu b/doc/examples/hlist/Makefile.cds_hlist_for_each_rcu new file mode 100644 index 0000000..23d0a0c --- /dev/null +++ b/doc/examples/hlist/Makefile.cds_hlist_for_each_rcu @@ -0,0 +1,21 @@ +# 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_hlist_for_each_rcu + +SOURCES = $(EXAMPLE_NAME).c +OBJECTS = $(EXAMPLE_NAME).o +BINARY = $(EXAMPLE_NAME) +LIBS = -lurcu + +include ../Makefile.examples.template diff --git a/doc/examples/hlist/cds_hlist_add_head_rcu.c b/doc/examples/hlist/cds_hlist_add_head_rcu.c new file mode 100644 index 0000000..12161d1 --- /dev/null +++ b/doc/examples/hlist/cds_hlist_add_head_rcu.c @@ -0,0 +1,64 @@ +/* + * 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 into a non-circular linked-list safely + * against concurrent RCU traversals. + */ + +#include + +#include /* Userspace RCU flavor */ +#include /* RCU hlist */ +#include /* For CAA_ARRAY_SIZE */ + +/* + * Nodes populated into the list. + */ +struct mynode { + int value; /* Node content */ + struct cds_hlist_node node; /* Linked-list chaining */ +}; + +int main(int argc, char **argv) +{ + int values[] = { -5, 42, 36, 24, }; + CDS_HLIST_HEAD(mylist); /* Defines an empty hlist head */ + unsigned int i; + int ret = 0; + struct mynode *node; + + /* + * Adding nodes to the linked-list. Safe against concurrent + * RCU traversals, require mutual exclusion with list updates. + */ + for (i = 0; i < CAA_ARRAY_SIZE(values); i++) { + node = malloc(sizeof(*node)); + if (!node) { + ret = -1; + goto end; + } + node->value = values[i]; + cds_hlist_add_head_rcu(&node->node, &mylist); + } + + /* + * Just show the list content. This is _not_ an RCU-safe + * iteration on the list. + */ + printf("mylist content:"); + cds_hlist_for_each_entry_2(node, &mylist, node) { + printf(" %d", node->value); + } + printf("\n"); +end: + return ret; +} diff --git a/doc/examples/hlist/cds_hlist_del_rcu.c b/doc/examples/hlist/cds_hlist_del_rcu.c new file mode 100644 index 0000000..1995b21 --- /dev/null +++ b/doc/examples/hlist/cds_hlist_del_rcu.c @@ -0,0 +1,90 @@ +/* + * 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 remove from a non-circular linked-list + * safely against concurrent RCU traversals. + */ + +#include + +#include /* Userspace RCU flavor */ +#include /* RCU hlist */ +#include /* For CAA_ARRAY_SIZE */ + +/* + * Nodes populated into the list. + */ +struct mynode { + int value; /* Node content */ + struct cds_hlist_node node; /* Linked-list chaining */ + struct rcu_head rcu_head; /* For call_rcu() */ +}; + +static +void free_node_rcu(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, 36, 24, }; + CDS_HLIST_HEAD(mylist); /* Defines an empty hlist head */ + unsigned int i; + int ret = 0; + struct mynode *node, *n; + + /* + * Adding nodes to the linked-list. Safe against concurrent + * RCU traversals, require mutual exclusion with list updates. + */ + for (i = 0; i < CAA_ARRAY_SIZE(values); i++) { + node = malloc(sizeof(*node)); + if (!node) { + ret = -1; + goto end; + } + node->value = values[i]; + cds_hlist_add_head_rcu(&node->node, &mylist); + } + + /* + * Removing all positive values. Safe against concurrent RCU + * traversals, require mutual exclusion with list updates. + * Notice the "safe" iteration: it is safe against removal of + * nodes as we iterate on the list. + */ + cds_hlist_for_each_entry_safe_2(node, n, &mylist, node) { + if (node->value > 0) { + cds_hlist_del_rcu(&node->node); + /* + * We can only reclaim memory after a grace + * period has passed after cds_hlist_del_rcu(). + */ + call_rcu(&node->rcu_head, free_node_rcu); + } + } + + /* + * Just show the list content. This is _not_ an RCU-safe + * iteration on the list. + */ + printf("mylist content:"); + cds_hlist_for_each_entry_2(node, &mylist, node) { + printf(" %d", node->value); + } + printf("\n"); +end: + return ret; +} diff --git a/doc/examples/hlist/cds_hlist_for_each_entry_rcu.c b/doc/examples/hlist/cds_hlist_for_each_entry_rcu.c new file mode 100644 index 0000000..f6b744a --- /dev/null +++ b/doc/examples/hlist/cds_hlist_for_each_entry_rcu.c @@ -0,0 +1,84 @@ +/* + * 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 do a non-circular RCU linked list + * traversal, safely against concurrent RCU updates. + */ + +#include + +#include /* Userspace RCU flavor */ +#include /* RCU hlist */ +#include /* For CAA_ARRAY_SIZE */ + +/* + * Nodes populated into the list. + */ +struct mynode { + int value; /* Node content */ + struct cds_hlist_node node; /* Linked-list chaining */ +}; + +int main(int argc, char **argv) +{ + int values[] = { -5, 42, 36, 24, }; + CDS_HLIST_HEAD(mylist); /* Defines an empty hlist head */ + unsigned int i; + int ret = 0; + struct mynode *node; + + /* + * Each thread need using RCU read-side need to be explicitly + * registered. + */ + rcu_register_thread(); + + /* + * Adding nodes to the linked-list. Safe against concurrent + * RCU traversals, require mutual exclusion with list updates. + */ + for (i = 0; i < CAA_ARRAY_SIZE(values); i++) { + node = malloc(sizeof(*node)); + if (!node) { + ret = -1; + goto end; + } + node->value = values[i]; + cds_hlist_add_head_rcu(&node->node, &mylist); + } + + /* + * RCU-safe iteration on the list. + */ + printf("mylist content:"); + + /* + * Surround the RCU read-side critical section with rcu_read_lock() + * and rcu_read_unlock(). + */ + rcu_read_lock(); + + /* + * This traversal can be performed concurrently with RCU + * updates. + */ + cds_hlist_for_each_entry_rcu_2(node, &mylist, node) { + printf(" %d", node->value); + } + + rcu_read_unlock(); + + printf("\n"); +end: + rcu_unregister_thread(); + return ret; +} diff --git a/doc/examples/hlist/cds_hlist_for_each_rcu.c b/doc/examples/hlist/cds_hlist_for_each_rcu.c new file mode 100644 index 0000000..47baa0e --- /dev/null +++ b/doc/examples/hlist/cds_hlist_for_each_rcu.c @@ -0,0 +1,91 @@ +/* + * 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 do a non-circular RCU linked list + * traversal, safely against concurrent RCU updates. + * cds_hlist_for_each_rcu() iterates on struct cds_hlist_node, and thus, + * either caa_container_of() or cds_hlist_entry() are needed to access + * the container structure. + */ + +#include + +#include /* Userspace RCU flavor */ +#include /* RCU hlist */ +#include /* For CAA_ARRAY_SIZE */ + +/* + * Nodes populated into the list. + */ +struct mynode { + int value; /* Node content */ + struct cds_hlist_node node; /* Linked-list chaining */ +}; + +int main(int argc, char **argv) +{ + int values[] = { -5, 42, 36, 24, }; + CDS_HLIST_HEAD(mylist); /* Defines an empty hlist head */ + unsigned int i; + int ret = 0; + struct cds_hlist_node *pos; + + /* + * Each thread need using RCU read-side need to be explicitly + * registered. + */ + rcu_register_thread(); + + /* + * Adding nodes to the linked-list. Safe against concurrent + * RCU traversals, require mutual exclusion with list updates. + */ + for (i = 0; i < CAA_ARRAY_SIZE(values); i++) { + struct mynode *node; + + node = malloc(sizeof(*node)); + if (!node) { + ret = -1; + goto end; + } + node->value = values[i]; + cds_hlist_add_head_rcu(&node->node, &mylist); + } + + /* + * RCU-safe iteration on the list. + */ + printf("mylist content:"); + + /* + * Surround the RCU read-side critical section with rcu_read_lock() + * and rcu_read_unlock(). + */ + rcu_read_lock(); + + /* + * This traversal can be performed concurrently with RCU + * updates. + */ + cds_hlist_for_each_rcu(pos, &mylist) { + struct mynode *node = cds_hlist_entry(pos, struct mynode, node); + + printf(" %d", node->value); + } + + rcu_read_unlock(); + + printf("\n"); +end: + rcu_unregister_thread(); + return ret; +} -- 2.34.1