Added lock-free single linked list implementation
Only supports lock-free insertion for now, can not delete element or traverse the list at the same time.
This commit is contained in:
parent
2720667566
commit
5bfe6126f8
|
|
@ -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__ */
|
||||
|
|
@ -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
|
||||
|
|
|
|||
|
|
@ -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;
|
||||
}
|
||||
|
|
@ -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);
|
||||
}
|
||||
|
|
@ -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")
|
||||
|
|
|
|||
Loading…
Reference in New Issue