diff options
| -rw-r--r-- | source/blender/blenlib/BLI_linklist_lockfree.h | 88 | ||||
| -rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 3 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/BLI_linklist_lockfree.c | 91 | ||||
| -rw-r--r-- | tests/gtests/blenlib/BLI_linklist_lockfree_test.cc | 130 | ||||
| -rw-r--r-- | tests/gtests/blenlib/CMakeLists.txt | 1 |
5 files changed, 312 insertions, 1 deletions
diff --git a/source/blender/blenlib/BLI_linklist_lockfree.h b/source/blender/blenlib/BLI_linklist_lockfree.h new file mode 100644 index 00000000000..7e7400361e3 --- /dev/null +++ b/source/blender/blenlib/BLI_linklist_lockfree.h @@ -0,0 +1,88 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * 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. + * + * The Original Code is Copyright (C) 2018 Blender Foundation. + * All rights reserved. + * + * Contributor(s): Sergey Sharybin. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_LINKLIST_LOCKFREE_H__ +#define __BLI_LINKLIST_LOCKFREE_H__ + +/** \file BLI_linklist_lockfree.h + * \ingroup bli + */ + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct LockfreeLinkNode { + struct LockfreeLinkNode *next; + /* NOTE: "Subclass" this structure to add custom-defined data. */ +} LockfreeLinkNode; + +typedef struct LockfreeLinkList { + /* We keep a dummy node at the beginning of the list all the time. + * This allows us to make sure head and tail pointers are always + * valid, and saves from annoying exception cases in insert(). + */ + LockfreeLinkNode dummy_node; + /* NOTE: This fields might point to a dummy node. */ + LockfreeLinkNode *head, *tail; +} LockfreeLinkList; + +typedef void (*LockfreeeLinkNodeFreeFP)(void *link); + +/* ************************************************************************** */ +/* NOTE: These functions are NOT safe for use from threads. */ +/* NOTE: !!! I REPEAT: DO NOT USE THEM WITHOUT EXTERNAL LOCK !!! */ + +/* Make list ready for lock-free access. */ +void BLI_linklist_lockfree_init(LockfreeLinkList *list); + +/* Completely free the whole list, it is NOT re-usable after this. */ +void BLI_linklist_lockfree_free(LockfreeLinkList *list, + LockfreeeLinkNodeFreeFP free_func); + +/* Remove all the elements from the list, keep it usable for further + * inserts. + */ +void BLI_linklist_lockfree_clear(LockfreeLinkList *list, + LockfreeeLinkNodeFreeFP free_func); + + +/* Begin iteration of lock-free linked list, starting with a + * first user=defined node. Will ignore the dummy node. + */ +LockfreeLinkNode *BLI_linklist_lockfree_begin(LockfreeLinkList *list); + + +/* ************************************************************************** */ +/* NOTE: These functions are safe for use from threads. */ + +void BLI_linklist_lockfree_insert(LockfreeLinkList *list, + LockfreeLinkNode *node); + +#ifdef __cplusplus +} +#endif + +#endif /* __BLI_LINKLIST_H__ */ diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 33a8379def5..f8fc2bfdcff 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -50,6 +50,7 @@ set(SRC intern/BLI_kdopbvh.c intern/BLI_kdtree.c intern/BLI_linklist.c + intern/BLI_linklist_lockfree.c intern/BLI_memarena.c intern/BLI_mempool.c intern/DLRB_tree.c @@ -163,7 +164,7 @@ set(SRC BLI_kdtree.h BLI_lasso_2d.h BLI_link_utils.h - BLI_linklist.h + BLI_linklist_lockfree.h BLI_linklist_stack.h BLI_listbase.h BLI_math.h diff --git a/source/blender/blenlib/intern/BLI_linklist_lockfree.c b/source/blender/blenlib/intern/BLI_linklist_lockfree.c new file mode 100644 index 00000000000..c004ddb6b66 --- /dev/null +++ b/source/blender/blenlib/intern/BLI_linklist_lockfree.c @@ -0,0 +1,91 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * 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. + * + * The Original Code is Copyright (C) 2018 Blender Foundation. + * All rights reserved. + * + * Contributor(s): Sergey Sharybin. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/BLI_linklist_lockfree.c + * \ingroup bli + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_linklist_lockfree.h" +#include "BLI_strict_flags.h" + +#include "atomic_ops.h" + +void BLI_linklist_lockfree_init(LockfreeLinkList *list) +{ + list->dummy_node.next = NULL; + list->head = list->tail = &list->dummy_node; +} + +void BLI_linklist_lockfree_free(LockfreeLinkList *list, + LockfreeeLinkNodeFreeFP free_func) +{ + if (free_func != NULL) { + /* NOTE: We start from a first user-added node. */ + LockfreeLinkNode *node = list->head->next; + while (node != NULL) { + LockfreeLinkNode *node_next = node->next; + free_func(node); + node = node_next; + } + } +} + +void BLI_linklist_lockfree_clear(LockfreeLinkList *list, + LockfreeeLinkNodeFreeFP free_func) +{ + BLI_linklist_lockfree_free(list, free_func); + BLI_linklist_lockfree_init(list); +} + +void BLI_linklist_lockfree_insert(LockfreeLinkList *list, + LockfreeLinkNode *node) +{ + /* Based on: + * + * John D. Valois + * Implementing Lock-Free Queues + * + * http://people.csail.mit.edu/bushl2/rpi/portfolio/lockfree-grape/documents/lock-free-linked-lists.pdf + */ + bool keep_working; + LockfreeLinkNode *tail_node; + node->next = NULL; + do { + tail_node = list->tail; + keep_working = + (atomic_cas_ptr((void**)&tail_node->next, NULL, node) != NULL); + if (keep_working) { + atomic_cas_ptr((void**)&list->tail, tail_node, tail_node->next); + } + } while (keep_working); + atomic_cas_ptr((void**)&list->tail, tail_node, node); +} + +LockfreeLinkNode *BLI_linklist_lockfree_begin(LockfreeLinkList *list) +{ + return list->head->next; +} diff --git a/tests/gtests/blenlib/BLI_linklist_lockfree_test.cc b/tests/gtests/blenlib/BLI_linklist_lockfree_test.cc new file mode 100644 index 00000000000..b5b790079d5 --- /dev/null +++ b/tests/gtests/blenlib/BLI_linklist_lockfree_test.cc @@ -0,0 +1,130 @@ +/* Apache License, Version 2.0 */ + +#include "testing/testing.h" + +#include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" +#include "BLI_linklist_lockfree.h" +#include "BLI_task.h" +#include "BLI_threads.h" + + +TEST(LockfreeLinkList, Init) +{ + LockfreeLinkList list; + BLI_linklist_lockfree_init(&list); + EXPECT_EQ(list.head, &list.dummy_node); + EXPECT_EQ(list.tail, &list.dummy_node); + BLI_linklist_lockfree_free(&list, NULL); +} + +TEST(LockfreeLinkList, InsertSingle) +{ + LockfreeLinkList list; + LockfreeLinkNode node; + BLI_linklist_lockfree_init(&list); + BLI_linklist_lockfree_insert(&list, &node); + EXPECT_EQ(list.head, &list.dummy_node); + EXPECT_EQ(list.head->next, &node); + EXPECT_EQ(list.tail, &node); + BLI_linklist_lockfree_free(&list, NULL); +} + +TEST(LockfreeLinkList, InsertMultiple) +{ + static const int num_nodes = 128; + LockfreeLinkList list; + LockfreeLinkNode nodes[num_nodes]; + BLI_linklist_lockfree_init(&list); + /* Insert all the nodes. */ + for (int i = 0; i < num_nodes; ++i) { + BLI_linklist_lockfree_insert(&list, &nodes[i]); + } + /* Check head and tail. */ + EXPECT_EQ(list.head, &list.dummy_node); + EXPECT_EQ(list.tail, &nodes[num_nodes - 1]); + /* Check rest of the nodes. */ + int node_index = 0; + for (LockfreeLinkNode *node = BLI_linklist_lockfree_begin(&list); + node != NULL; + node = node->next, ++node_index) + { + EXPECT_EQ(node, &nodes[node_index]); + if (node_index != num_nodes - 1) { + EXPECT_EQ(node->next, &nodes[node_index + 1]); + } + } + /* Free list. */ + BLI_linklist_lockfree_free(&list, NULL); +} + +namespace { + +struct IndexedNode { + IndexedNode *next; + int index; +}; + +void concurrent_insert(TaskPool *__restrict pool, + void *taskdata, + int /*threadid*/) +{ + LockfreeLinkList *list = (LockfreeLinkList *)BLI_task_pool_userdata(pool); + CHECK_NOTNULL(list); + IndexedNode *node = (IndexedNode *)MEM_mallocN(sizeof(IndexedNode), + "test node"); + node->index = GET_INT_FROM_POINTER(taskdata); + BLI_linklist_lockfree_insert(list, (LockfreeLinkNode *)node); +} + + +} // namespace + +TEST(LockfreeLinkList, InsertMultipleConcurrent) +{ + static const int num_threads = 512; + static const int num_nodes = 655360; + /* Initialize list. */ + LockfreeLinkList list; + BLI_linklist_lockfree_init(&list); + /* Initialize task scheduler and pool. */ + TaskScheduler *scheduler = BLI_task_scheduler_create(num_threads); + TaskPool *pool = BLI_task_pool_create_suspended(scheduler, &list); + /* Push tasks to the pool. */ + for (int i = 0; i < num_nodes; ++i) { + BLI_task_pool_push(pool, + concurrent_insert, + SET_INT_IN_POINTER(i), + false, + TASK_PRIORITY_HIGH); + } + /* Run all the tasks. */ + BLI_threaded_malloc_begin(); + BLI_task_pool_work_and_wait(pool); + BLI_threaded_malloc_end(); + /* Verify we've got all the data properly inserted. */ + EXPECT_EQ(list.head, &list.dummy_node); + bool *visited_nodes = (bool *)MEM_callocN(sizeof(bool) * num_nodes, + "visited nodes"); + /* First, we make sure that none of the nodes are added twice. */ + for (LockfreeLinkNode *node_v = BLI_linklist_lockfree_begin(&list); + node_v != NULL; + node_v = node_v->next) + { + IndexedNode *node = (IndexedNode *)node_v; + EXPECT_GE(node->index, 0); + EXPECT_LT(node->index, num_nodes); + EXPECT_FALSE(visited_nodes[node->index]); + visited_nodes[node->index] = true; + } + /* Then we make sure node was added. */ + for (int node_index = 0; node_index < num_nodes; ++node_index) { + EXPECT_TRUE(visited_nodes[node_index]); + } + MEM_freeN(visited_nodes); + /* Cleanup data. */ + BLI_linklist_lockfree_free(&list, MEM_freeN); + BLI_task_pool_free(pool); + BLI_task_scheduler_free(scheduler); +} diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt index cc1c95bd0fe..a3f62d8a05d 100644 --- a/tests/gtests/blenlib/CMakeLists.txt +++ b/tests/gtests/blenlib/CMakeLists.txt @@ -47,6 +47,7 @@ BLENDER_TEST(BLI_ghash "bf_blenlib") BLENDER_TEST(BLI_hash_mm2a "bf_blenlib") BLENDER_TEST(BLI_heap "bf_blenlib") BLENDER_TEST(BLI_kdopbvh "bf_blenlib") +BLENDER_TEST(BLI_linklist_lockfree "bf_blenlib") BLENDER_TEST(BLI_listbase "bf_blenlib") BLENDER_TEST(BLI_math_base "bf_blenlib") BLENDER_TEST(BLI_math_color "bf_blenlib") |