[lock-free] Simple DWCAS based Proxy Collector, refined... ;^)

[Chris M. Thomasson]

Fwiw Dmitry , I have been 
working with fractals a lot lately, and was wondering if I could still 
program a proxy collector from scratch. Remember my old collector here:

http://webpages.charter.net/appcore/misc/pc_sample_h_v1.html

?

You are using it as an example in Relacy.

Wrt the following code, all of the membars are standalone fence operations 
std::atomic_thread_fence. 
All of the membars in the atomic operations are relaxed. It uses DWCAS for 
the acquire function because I wanted to start out simple. I have also 
replaced a CAS with XCHG in the collect, or mutate function if you will.  So 
far, it works in Relacy. :^)

Here is a link to my code:

https://pastebin.com/raw/RKTLyXWt

___

/* Simple Proxy Collector (DWCAS) - Relacy Version

http://www.1024cores.net/home/relacy-race-detector

Copyright 3/27/2018
___*/


#include 
#include 
#include 


/* Membar Abstraction
___*/
#define ct_mb_relaxed std::memory_order_relaxed
#define ct_mb_acquire std::memory_order_acquire
#define ct_mb_release std::memory_order_release
#define ct_mb_seq_cst std::memory_order_seq_cst
#define ct_mb_fence(mb_membar) std::atomic_thread_fence(mb_membar) 


/* Simple Proxy Collector C++11
___*/
namespace ct { 
namespace proxy {

// User object base
struct object
{
virtual ~object() {}
};


// Proxy node
struct node
{
std::atomic count;
VAR_T(node*) next;
VAR_T(object*) obj;

node(std::intptr_t count_, node* next_, object* obj_)
: count(count_), next(next_), obj(obj_)
{

}

~node()
{

}
};


// DWCAS target
struct anchor
{
std::intptr_t count;
node* head;

anchor()
{

}

anchor(std::intptr_t count_, node* head_)
{
count = count_;
head = head_;
}

bool operator == (anchor const& right) const
{
return count == right.count && head == right.head;
}

anchor operator + (anchor const& right) const
{
anchor res;
res.count = count + right.count;
res.head = right.head;
return res;
}

anchor operator - (anchor const& right) const
{
anchor res;
res.count = count - right.count;
res.head = right.head;
return res;
}
};

std::ostream& operator << (std::ostream& s, anchor const& right)
{
return s << "{" << right.count << "," << right.head << "}";
}


// Collector Logic
struct gc
{
std::atomic head;

gc() : head(anchor{ 0, new node(0, nullptr, nullptr) }) {}

~gc()
{
anchor cmp = head.load(ct_mb_relaxed);
RL_ASSERT(cmp.count > -1);
RL_ASSERT(VAR(cmp.head->next) == nullptr);
prv_dtor(cmp.head);
}

// Drops a reference count on a node
bool prv_release(node* n)
{
std::intptr_t count = n->count.fetch_sub(2, ct_mb_relaxed);
if (count == 3) return true;
return false;
}

// Deletes a node
void prv_dtor(node* n)
{
object* obj = VAR(n->obj);
if (obj != nullptr) delete obj;
delete n;
}

// Dumps backlinked nodes
void prv_dump(node* n)
{
node* cur = VAR(n->next);
VAR(n->next) = nullptr;

// Release and collect in cur LIFO
while (prv_release(cur))
{
ct_mb_fence(ct_mb_acquire);
node* next = VAR(cur->next);
VAR(cur->next) = n;
n = cur;
cur = next;
}

// Destroy cur LIFO
while (n)
{
node* next = VAR(n->next);
prv_dtor(n);
n = next;
}
}

// Collects a node
void prv_collect(node* n)
{
anchor xchg = { 0, n };

ct_mb_fence(ct_mb_release);

// Swap in new node
anchor cmp = head.exchange(xchg, ct_mb_relaxed);

// Backlink
ct_mb_fence(ct_mb_acquire);
VAR(cmp.head->next) = xchg.head;
ct_mb_fence(ct_mb_release);

// Release and mark as collected
std::intptr_t count = cmp.head->count.fetch_add(cmp.count + 1, 
ct_mb_relaxed);

if (count + cmp.count == 0)
{
prv_dump(cmp.head);
}
}


// Acquires current node
node* acquire()
{
anchor cmp = head.load(ct_mb_relaxed);
anchor xchg = {

[lock-free] Re: Simple DWCAS based Proxy Collector, refined... ;^)

[Chris M. Thomasson]

Fwiw, the following is some C++11 code that should compile and run fine on 
systems that support lock-free DWCAS. I like the Relacy code because it 
helps make sure everything is Kosher. And, I like the C++11 code because it 
is an example of a real implementation. Anyway, here is the code:

https://pastebin.com/raw/KAt4nhCj

-- 

--- 
You received this message because you are subscribed to the Google Groups 
"Scalable Synchronization Algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to lock-free+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/lock-free/1e1cc3e9-1b68-431a-8299-c11680f18a56%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.