Global Lock-Free Proxy Collector Anchor Scheme...
Chris Thomasson
http://home.comcast.net/~vzoom/demos/pc_sample.c
#define PDR_HASH_DEPTH() 128
#define PDR_DEPTH() (PDR_HASH_DEPTH() + 1)
static pc_t pxy_master[PDR_DEPTH()];
#define PXY_HASHPTR(__ptr) \
(((ptrdiff_t)(__ptr)) % PDR_HASH_DEPTH())
#define PXY_MASTER_HASH(__ptr) \
(&pxy_master[PXY_HASHPTR(__ptr)])
static user_collection_t g_col1;
static user_collection_t g_col2;
static user_collection_t g_col3;
void user_collection_iterate(user_collection_t* const _this) {
pc_t *master = PXY_MASTER_HASH(_this);
pc_deferred_t *pcd = pc_inc(master);
/* iterate read-only _this */
pc_dec(pcd);
}
void user_collection_defer(void *state) {
user_collection_node_t* const _this = state;
user_collection_node_free(_this);
}
void user_collection_pop(user_collection_t* const _this) {
user_collection_node_t *node;
pc_t *master = PXY_MASTER_HASH(_this);
global_hash_lock(_this);
/* pop node from _this into node */
global_hash_unlock(_this);
pc_defer(master, user_collection_defer, node);
}
void reader_threads() {
for(;;) {
user_collection_iterate(&g_col1);
user_collection_iterate(&g_col2);
user_collection_iterate(&g_col3);
}
}
void writer_remove_threads() {
for(;;) {
user_collection_pop(&g_col1);
user_collection_pop(&g_col2);
user_collection_pop(&g_col3);
}
}
/* writer add threads removed for brevity. Hint, you can take a proxy
reference for writer algorithms... */
Any thoughts?
;^)
Ulrich Kroemer
> Can you please stop to post code?
> Even more undocumented code?
this is a programming news group. and if you don't like to read code you
don't have to.
i'm quite happy about it, because even undocumented, you can gain some
insights.
David Hopwood
> Elcaro Nosille wrote:
>
>> Can you please stop to post code?
>> Even more undocumented code?
... and incomplete, and very often buggy.
> this is a programming news group. and if you don't like to read code you
> don't have to.
> i'm quite happy about it, because even undocumented, you can gain some
> insights.
Not really. I agree with Elcaro: Usenet isn't the right forum to post
undocumented code. Most of what Chris Thomasson (and several others) post
here would be better suited to a blog.
--
David Hopwood <david....@industrial-designers.co.uk>
Chris Thomasson
news:lMudnbZg-IZmi8fb...@comcast.com...
> Using pc_sample.c:
>
>
> http://home.comcast.net/~vzoom/demos/pc_sample.c
quick comments:
/* 'pc_inc' atomically acquires a strong reference from
the 'master' proxy achor */
extern "C" pc_deferred_t* pc_inc(pc_t *master);
/* 'pc_dec' atomically decrements a basic reference from
'defer' */
extern "C" void pc_dec(pc_deferred_t *defer);
/*
these functions can be logically renamed...
*/
typedef pc_deferred_t read_ticket_t;
#define read_acquire_ticket pc_inc
#define read_release_ticket pc_dec
/* or... */
#define read_lock read_acquire_ticket
#define read_unlock read_acquire_ticket
/* read_lock returns a reference to the rw-lock, this reference is passed to
read_unlock in order to unlock the previous read access */
/* 'pc_defer' atomically schedules a 'callback' to be called with the
'state', ONLY when 'state' is no longer being referenced by ANY read-side
critical-sections wrt any thread(s) participating in parallel 'read_lock' /
'read_unlock' functions... */
extern "C" void pc_defer(pc_t *master, void (*callback) (void*), void
*state);
/* this can be refined */
#define sched_write_only_when_no_readers pc_defer
/* the PATTERN */
static pc_t pg_lock; /* init with pc_alloc; look in pc_sample.c */
/* free with pc_free */
/* readers */
read_ticket_t *myticket = read_lock(&pg_lock);
/* read-only access to dynamic-linked node-based list */
read_unlock(myticket);
/* quiescent */
extern "C" void my_alone_time(void *state) {
/* state is free to be freed! ;^) */
}
/* writer removers*/
your_node_t *node = 0;
lock_your_mutex_for_your_collection(...);
/* node = try to pop a node */
unlock_your_mutex_for_your_collection(...);
if (node) {
sched_write_only_when_no_readers(&pg_lock, my_alone_time, node);
}
/* writer adders*/
your_node_t *node = your_node_alloc(...);
lock_your_mutex_for_your_collection(...);
/* push the node */
unlock_your_mutex_for_your_collection(...);
There, is that better at all?
If not, please tell me where your having problems understanding any of it?
Chris Thomasson
> "Chris Thomasson" <cri...@comcast.net> wrote in message
> news:lMudnbZg-IZmi8fb...@comcast.com...
>> Using pc_sample.c:
>>
>>
>> http://home.comcast.net/~vzoom/demos/pc_sample.c
>
> quick comments:
>
>
> /* 'pc_inc' atomically acquires a strong reference from
> the 'master' proxy achor */
> extern "C" pc_deferred_t* pc_inc(pc_t *master);
>
>
>
> /* 'pc_dec' atomically decrements a basic reference from
> 'defer' */
> extern "C" void pc_dec(pc_deferred_t *defer);
>
> /*
> these functions can be logically renamed...
> */
>
>
> typedef pc_deferred_t read_ticket_t;
>
> #define read_acquire_ticket pc_inc
> #define read_release_ticket pc_dec
>
>
> /* or... */
>
>
> #define read_lock read_acquire_ticket
> #define read_unlock read_acquire_ticket
^^^^^^^^^^^^^^^^
#define read_unlock read_release_ticket
of course!
Chris Thomasson
acquiring a master proxy reference is analogous to a read-lock. You can do a
read-only iteration of your dynamic node-based collection. When your done,
you release the deferred reference you received from the master; this is the
read-unlock.
The write-lock can be you own custom mutex, or POSIX Mutex... Whatever.
You use your mutex of choice to pop or add a node to your own dynamic
node-based collections.
If you decide to pop an node, and want to free that node when no readers are
accessing it, you use pc_defer. You defer the destruction of the node when
there are no reader threads!
PDR = PCOW Deferred Destruction
PCOW = Partial COW
COW= Copy-On-Write!
...
Dmitriy Vyukov
> PDR = PCOW Deferred Destruction
Deferred Reclamation?
Dmitriy V'jukov
Dmitriy Vyukov
designers.co.uk> wrote:
> Not really. I agree with Elcaro: Usenet isn't the right forum to post
> undocumented code. Most of what Chris Thomasson (and several others) post
> here would be better suited to a blog.
Chris offer to you the most advanced high tech in the world that very
few people around the world can create. And very few of those people
post such code to public. And comments don't help here at all, or it
must be some papers of hundreds of pages with pictures and graphs...
So Chris can join those people who don't post such code to public...
It is yours choice...
You really can't find such code anywhere else... So let it would be
undocumented then it would not be at all. This is my opinion.
Dmitriy V'jukov
Chris Thomasson
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1180420919.9...@r19g2000prf.googlegroups.com...
> On May 29, 9:24 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> PDR = PCOW Deferred Destruction
>
> Deferred Reclamation?
Yup. :^)
Dmitriy Vyukov
> Using pc_sample.c:
> /* Hint, you can take a proxy reference for writer algorithms... */
Are you mean that writer threads can call pc_inc/pc_dec like readers
to work concurrently? I.e. several writer threads can modify data
structure concurrently by means of some lock-free algorithm?
>
> Any thoughts?
>
> ;^)
Now I understand the PDR with global hash table!
You don't use proxy for holding some object at all, you use proxy only
for reclamation of unnecessary nodes. I always think about PDR on the
other hand. I use PDR for holding some object such that writers can
replace that object and readers can get this object *from* proxy.
So pc_inc/pc_dec doesn't actually acquire any object, they just
"freeze" and defer node deletion! Cool!
PDR used in that way outperforms SMR in sense that one don't have to
pin every used node by hazard pointer, one can pin the whole structure
by only one atomic RMW. If I get you right.
Dmitriy V'jukov
Joe Seigh
PDR doesn't refer to a specific algorithm. It's a form of memory management
used in a common lock-free design pattern (the PCOW in PDR). There's a variation
of that called proxy collectors of which Paul McKenney, Maged Michael, Chris, and
myself have done a few versions.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Chris Thomasson
news:465c804b$0$10200$9b4e...@newsspool4.arcor-online.net...
> Dmitriy Vyukov schrieb:
>
>> Chris offer to you the most advanced high tech in the
>> world that very few people around the world can create.
>
> There's enough documentation on lock-free Code around and you can
> create your own lock-free algorithms with little effort.
Little effort?
;^)
>
>> And very few of those people post such code to public. And comments
>> don't help here at all, or it must be some papers of hundreds of
>> pages with pictures and graphs.
>
> Chris posts his buggy undocumented code every few days and this doesn't
> help anyone.
Fuc^ you.
Chris Thomasson
>> help anyone.
>
> Fuc^ you.
Sorry for that juvenile crap attitude...
Just out of curiosity...
How many of you see thin as absolutely NOO help at ALLL
???
Ian Collins
> Ulrich Kroemer > wrote:
>> Elcaro Nosille wrote:
>>
>>> Can you please stop to post code?
>>> Even more undocumented code?
>
>
>> this is a programming news group. and if you don't like to read code you
>> don't have to.
>> i'm quite happy about it, because even undocumented, you can gain some
>> insights.
>
> Not really. I agree with Elcaro: Usenet isn't the right forum to post
> undocumented code. Most of what Chris Thomasson (and several others) post
> here would be better suited to a blog.
>
This used to be an interesting group for the general discussion of
threaded programming, with a diverse mix of questions and insightful
answers.
It is now almost a one man lock-free splatter fest. Either a new
lock-free group or a blog would be a more appropriate place.
--
Ian Collins.
Chris Thomasson
> On May 28, 3:43 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>> Using pc_sample.c:
>
>> /* Hint, you can take a proxy reference for writer algorithms... */
>
> Are you mean that writer threads can call pc_inc/pc_dec like readers
> to work concurrently? I.e. several writer threads can modify data
> structure concurrently by means of some lock-free algorithm?
>
>>
>> Any thoughts?
>>
>> ;^)
>
> Now I understand the PDR with global hash table!
Indeed.
> You don't use proxy for holding some object at all, you use proxy only
> for reclamation of unnecessary nodes.
Right.
> I always think about PDR on the other hand.
I noticed. I mention this wrt your algorithm focus on single object. Still,
your algorithm works.
> I use PDR for holding some object such that writers can
> replace that object and readers can get this object *from* proxy.
Yes. I completely understand. I read your code in detail.
> So pc_inc/pc_dec doesn't actually acquire any object, they just
> "freeze" and defer node deletion! Cool!
Bingo! ;^)
Freeze... Well, that moment in time, is tracked in the generation pool
"so-to-speak"... So, your totally correct in a sense.
> PDR used in that way outperforms SMR in sense that one don't have to
> pin every used node by hazard pointer, one can pin the whole structure
> by only one atomic RMW. If I get you right.
Exatcly.
!
Chris Thomasson
I was thinking C++ for some reason.
Chris Thomasson
news:NJC6i.20734$4a.1...@fe3.news.blueyonder.co.uk...
Humm... Perhaps.
Dmitriy Vyukov
wrote:
> "most advanced high tech" - LOL.
> There's enough documentation on lock-free Code around and you can
> create your own lock-free algorithms with little effort.
LROTF
> Chris posts his buggy undocumented code every few days and this doesn't
> help anyone.
Speak for oneself
Dmitriy V'jukov
Dmitriy Vyukov
> It is now almost a one man lock-free splatter fest. Either a new
> lock-free group or a blog would be a more appropriate place.
I create dedicated group for lock-free tech:
http://groups.google.com/group/lock-free/topics
So all interested people are welcome to post/comment some thoughts/
ideas/algos related to lock-free tech to this new group.
Dmitriy V'jukov
Dmitriy Vyukov
> I noticed. I mention this wrt your algorithm focus on single object. Still,
> your algorithm works.
My algorithm is very close per se to your pc_sample and Joe Seigh
atomic_ptr. So I am sure that the same back-link mechanism can be
plugged into my algorithm. And vice versa pc_sample and atomic_ptr can
work only on xadd primitive like my algo.
BTW. I don't know what it's all about and I am not well-informed about
this field. But. Joe Seigh said some time ago that there are some
patents related to PDR and atomic_ptr. Can such improvement
((atomic_cas -> atomic_add) and hence (lock-free -> wait-free)) be a
blocking patent?
Dmitriy V'jukov
Dmitriy Vyukov
> PDR doesn't refer to a specific algorithm. It's a form of memory management
> used in a common lock-free design pattern (the PCOW in PDR). There's a variation
> of that called proxy collectors of which Paul McKenney, Maged Michael, Chris, and
> myself have done a few versions.
What things from my post refer only to Chris Thomasson's
implementation and not refer to PDR as a whole?
I didn't see papers on PDR by Paul McKenney and Maged Michael... It
seems that they call this differently. Can you provide some links?
Dmitriy V'jukov
Dmitriy Vyukov
> PDR doesn't refer to a specific algorithm. It's a form of memory management
> used in a common lock-free design pattern (the PCOW in PDR). There's a variation
> of that called proxy collectors of which Paul McKenney, Maged Michael, Chris, and
> myself have done a few versions.
What things from my post refer only to Chris Thomasson's
Steve Watt
Most of us don't use google groups to read USENET. One person
complaining about discussion of lock-free techniques is not enough to
move the discussion elsewhere. I find it interesting, even if I don't
use lock-free techniques that often -- but when I do, I currently know
where to look.
--
Steve Watt KD6GGD PP-ASEL-IA ICBM: 121W 56' 57.5" / 37N 20' 15.3"
Internet: steve @ Watt.COM Whois: SW32-ARIN
Free time? There's no such thing. It just comes in varying prices...
Joe Seigh
You can try some of the links in the references section here
http://atomic-ptr-plus.sourceforge.net/
Most papers only use the term for their own algorithms, not
a general term. So
RCU for Paul McKenney's stuff
SMR (safe memory relamation?) hazard pointers for Maged Michael's stuff
ROP (repeat offender problem) for Herlihy's stuff
Joe Seigh
It would have to have a fairly dramatic advantage over the CAS
version to make it worthwhile from an individual point of view.
For companies the patents don't have to be that good to have
value as part of a patent porfolio.
And I think there a few ways of packing an address and count into
a word out there, so you have to demonstrate novelty and non-obviousness
there. Just being different wouldn't be enough in of itself.
Ian Collins
> In article <1180553466.5...@g37g2000prf.googlegroups.com>,
> Dmitriy Vyukov <dvy...@gmail.com> wrote:
>> On May 30, 8:58 am, Ian Collins <ian-n...@hotmail.com> wrote:
>>
>>> It is now almost a one man lock-free splatter fest. Either a new
>>> lock-free group or a blog would be a more appropriate place.
>>
>> I create dedicated group for lock-free tech:
>>
>> http://groups.google.com/group/lock-free/topics
>>
>> So all interested people are welcome to post/comment some thoughts/
>> ideas/algos related to lock-free tech to this new group.
>
> Most of us don't use google groups to read USENET. One person
> complaining about discussion of lock-free techniques is not enough to
> move the discussion elsewhere. I find it interesting, even if I don't
> use lock-free techniques that often -- but when I do, I currently know
> where to look.
It wasn't the topic or the discussion, but the deluge of incomplete code
and postings that I have a problem with.
I too find lock free an interesting topic.
--
Ian Collins.
Joe Seigh
> Steve Watt schrieb:
>
>> Most of us don't use google groups to read USENET. One person
>> complaining about discussion of lock-free techniques is not
>> enough to move the discussion elsewhere.
> And I'll bet Chris doesn't understand the limited relevance of lock-free
> progamming (f.e. lock-free code is unsuitable for most producer-consumer
> -patterns) and hasn't ever worked on a larger project.
Most of the lock-free stuff I've seen here has been promoted as a
solution to the reader/writer problem with the writer part using
conventional locking. This application of lock-free will be important
because in most cases conventional rwlocks will not scale very well.
You can disagree on that latter point and are welcome to try and convice
Linus that Linux would be better off with conventional rwlocks instead
of RCU but I suspect you'd be laughed off of LKML.
I did do a lock-free FIFO queue implementation using STM compared
against Java's adaption of Michael and Scott's lock-free FIFO queue.
A comparison of lock-free AVL or red-black trees would have been
better from a reader/writer point of view but no one's done any
Java implemetations yet. The STM version did a lot worse because
of higher memory usage. If you subtracted out the GC the execution
times were fairly close. Of course using hash maps a lot didn't help
things too much. But that's about as close as I've gotten to
a pure lock-free producer/consumer solution.
It would be nice if in general there was a lot more large project
experience out there besides Linux and a few other things. The
problem is it takes disapline to do locking properly let alone
lock-free. If you can't do the former right, you certainly can't
do the latter right. Let's say there's a lot of faith based
multi-threading out there. :)
Dmitriy Vyukov
> It would have to have a fairly dramatic advantage over the CAS
> version to make it worthwhile from an individual point of view.
> For companies the patents don't have to be that good to have
> value as part of a patent porfolio.
>
> And I think there a few ways of packing an address and count into
> a word out there, so you have to demonstrate novelty and non-obviousness
> there. Just being different wouldn't be enough in of itself.
I better read some articles on this first before asking more stupid
questions :)
Dmitriy V'jukov
Dmitriy Vyukov
wrote:
> lock-free code is unsuitable for most producer-consumer patterns
What are you mean? Can you explain more detailed?
Dmitriy V'jukov
Szabolcs Ferenczi
wrote:
> >> lock-free code is unsuitable for most producer-consumer patterns
> > What are you mean? Can you explain more detailed?
>
> is empty. But this is necessary in most producer/consumer-patterns.
Yes, good point. Lock-free algorithms can be applied for the short
term scheduling and, obviously, they are not applicable for the long
term scheduling of the processes, which is the case in the producer-
consumer pattern. However,lock-free maniacs do not see the point.
Best Regards,
Szabolcs
Dmitriy Vyukov
wrote:
> lock-free code is unsuitable for most producer-consumer patterns
What are you mean? Can you explain more detailed?
Dmitriy V'jukov
Dmitriy Vyukov
wrote:
> > With lock-free algorithms it isn't possible to block whenn a FIFO-queue
> > is empty. But this is necessary in most producer/consumer-patterns.
>
> Yes, good point. Lock-free algorithms can be applied for the short
> term scheduling and, obviously, they are not applicable for the long
> term scheduling of the processes, which is the case in the producer-
> consumer pattern. However,lock-free maniacs do not see the point.
You can build blocking behavior on top of any lock-free queue as you
do with lock-based queue. There is completely no difference. What's
the problem?
For example you can look at this library:
http://appcore.home.comcast.net/
(see ac_eventcount_algo1/ac_queue_spsc components)
Btw with blocking behavior you don't get any additional overhead while
queue is not emppy.
Dmitriy V'jukov
Szabolcs Ferenczi
> You can build blocking behavior on top of any lock-free queue as you
> do with lock-based queue. There is completely no difference. What's
> the problem?
The problem is that you offer an interface on a shared resource in a
multi-threaded environment that returns 0 if the shared resource is
not in an appropriate status at the moment of the attempt. It is not
in conformance with the basic principles of multi-threading.
Yes, you can build an interface on top of it, of course, and you have
to do so as well.
Best Regards,
Szabolcs
Dmitriy Vyukov
> You can try some of the links in the references section herehttp://atomic-ptr-plus.sourceforge.net/
>
> Most papers only use the term for their own algorithms, not
> a general term. So
> RCU for Paul McKenney's stuff
> SMR (safe memory relamation?) hazard pointers for Maged Michael's stuff
> ROP (repeat offender problem) for Herlihy's stuff
And what is the name of algorithm that is used in your atomic_ptr and
Chris pc_sample ?
It looks as PDR is wrong term if I want to refer to those particular
algorithms...
Dmitriy V'jukov
Joe Seigh
PDR is more of a multi-threading design pattern. atomic_ptr is
atomically thread-safe lock-free reference counting. I think
I called it differential reference counting at one point.
Another way to do atomically thread-safe lock-free reference counting
is to use some other PDR scheme to manage the reference counts so
they can be safely incremented. You'll see atomic decrements if not
zero with these. Examples are rcu_ref in the Linux kernel or using
RCU+SMR.
It may seem redundant to use PDR to manage a reference count but
it usually complimentary to the PDR scheme. RCU is really only
good for short term references. Refcounting handles the longer
term non-local references in global storage. SMR hazard pointers
have a per pointer overhead in polling so you want to keep the
number of hazard pointers fairly low.
Chris Thomasson
news:465f4441$0$23137$9b4e...@newsspool1.arcor-online.net...
>>> lock-free code is unsuitable for most producer-consumer patterns
>
>> What are you mean? Can you explain more detailed?
>
> is empty.
WRONG!!!
Ever read anything about an eventcount!?
;^/
Chris Thomasson
Thank you for that Dmitriy.
I have just got to a point where I can read this group and my e-mail; well,
I have been very busy!
Work does suck sometimes!
;^(
It will take me a day or two to absorb all of the posts that have
accumulated since I last read this group!
...
I am still alive!
lol... ;^)
Chris Thomasson
news:1180729862.7...@p47g2000hsd.googlegroups.com...
Well, eventcounts can be used like condition variables. The predicate for
the eventcount can be as complex as you want it to be...
Chris Thomasson
> Steve Watt schrieb:
>
>> Most of us don't use google groups to read USENET. One person
>> complaining about discussion of lock-free techniques is not
>> enough to move the discussion elsewhere.
>
I am typing that code in on the newsreader 95% of the time. Would you prefer
I stop doing that altogether? Or just reduce the frequency?
Chris Thomasson
Okay, you can use your own mutexs in the writer-side of the lock-free PDR
reader pattern; pc_sample included.
/* Producers */
You have to execute at least a #StoreStore barrier BEFORE you make ANY node
visible in your custom link-based dynamic collections...
e.g.:
your_node_t *node = create_your_node();
lock_your_mutex();
/* establish the links in your node */
/* e.g.: node->next = lifo->front; */
membar #StoreStore
/* link you node, thereby making it visible */
/* e.g.: lifo->front = node; */
unlock_your_mutex();
/* Consumers */
/* create an atomic load function with data-dependant load-dependency */
#define read_your_node atomic_load_depends
/* lock-free read-only iteration of your collection *'/
your_node_t *node = read_your_node(&lifo);
while(node) {
your_node_t *next = read_your_node(&node->next);
read_only(node);
node = next;
}
You need the #StoreStore in the producer BEFORE you make any node visible to
the shared collection in order to make sure that the node's
configuration/initialization's are all visible to any potential readers.
You need the load-depends in the consumer in order to make sure the your
load occurs after the stores...
Just like RCU.
Chris Thomasson
news:lr2dnZGqurlMh_jb...@comcast.com...
> Here is some more quick technical info...
>
>
> Okay, you can use your own mutexs in the writer-side of the lock-free PDR
> reader pattern; pc_sample included.
>
>
> /* Producers */
>
> You have to execute at least a #StoreStore barrier BEFORE you make ANY
> node visible in your custom link-based dynamic collections...
Believe it or not, there is a patented method for this which turns out to be
100% compatible with POSIX:
http://groups.google.com/group/comp.programming.threads/msg/b7814ee86cd4b54d
IMHO, that's pretty neat and convenient.
Chris Thomasson
>
>
> Okay, you can use your own mutexs in the writer-side of the lock-free PDR
> reader pattern; pc_sample included.
>
>
> /* Producers */
>
> You have to execute at least a #StoreStore barrier BEFORE you make ANY
> node visible in your custom link-based dynamic collections...
https://coolthreads.dev.java.net/servlets/ProjectForumMessageView?forumID=1797&messageID=11068
Dmitriy Vyukov
> Believe it or not, there is a patented method for this which turns out to be
> 100% compatible with POSIX:
http://groups.google.com/group/comp.programming.threads/msg/b7814ee86...
> IMHO, that's pretty neat and convenient.
Earlier you write that it is 99.99% POSIX compatible, because of dd-
loads, so you obtain this 0.01% of POSIX compatibility? :)
Dmitriy V'jukov
Dmitriy Vyukov
> PDR is more of a multi-threading design pattern. atomic_ptr is
> atomically thread-safe lock-free reference counting. I think
> I called it differential reference counting at one point.
Term atomically_thread_safe_lock_free_reference_counting loses a
little to terms like RCU/SMR/ROP... :)
differential reference counting - is better... hmm... DRC...
> Another way to do atomically thread-safe lock-free reference counting
> is to use some other PDR scheme to manage the reference counts so
> they can be safely incremented. You'll see atomic decrements if not
> zero with these. Examples are rcu_ref in the Linux kernel or using
> RCU+SMR.
In such scheme, if counter drops to zero I must defer object deletion
with SMR (for example), and then, when SMR says that object can be
deleted I must check counter again, and if counter is not zero, don't
delete the object. Am I right?
> RCU is really only
> good for short term references. Refcounting handles the longer
> term non-local references in global storage.
But atomic_ptr and pc_sample don't handle long term references well,
because of back-link list. I.e. if one object in back-link list would
not be deleted very long time, then all "newer" objects would not be
deleted too...
> SMR hazard pointers...
Are there other worthwhile techniques?
For now it seems that there is no good choice of techniques. And all
of them have some limitations. Or they can handle only short term
references (RCU), or they can handle bounded number of references
(SMR), or they have too big overheads (reference counting)...
Chris Thomasson claims that vZOOM can handle unbounded number of
objects *and* good for long term references *and* have zero overheads
on reader side...
Dmitriy V'jukov
Chris Thomasson
Oh SHIT!
I forgot that .01%! ;^(...
Well, the 'writer-side' is 100% POSIX compatible, the 'reader-side' need
dd-loads which are supported on virtually everywhere.
'fortunately for me, that .01% currently represents the Alpha only...'
Does that clear "some" things up?
Dmitriy Vyukov
> > Earlier you write that it is 99.99% POSIX compatible, because of dd-
> > loads, so you obtain this 0.01% of POSIX compatibility? :)
>
> Oh SHIT!
>
> I forgot that .01%! ;^(...
>
> Well, the 'writer-side' is 100% POSIX compatible, the 'reader-side' need
> dd-loads which are supported on virtually everywhere.
btw afaik POSIX prohibit any access to memory location while other
thread is modifying this memory location... so lock-free reader
pattern based on vZOOM is 0% POSIX compatible. It is just relying on
POSIX threads primitives...
Dmitriy V'jukov
Joe Seigh
> On 5 , 05:46, Joe Seigh <jseigh...@xemaps.com> wrote:
>
>
>>Another way to do atomically thread-safe lock-free reference counting
>>is to use some other PDR scheme to manage the reference counts so
>>they can be safely incremented. You'll see atomic decrements if not
>>zero with these. Examples are rcu_ref in the Linux kernel or using
>>RCU+SMR.
>
>
> In such scheme, if counter drops to zero I must defer object deletion
> with SMR (for example), and then, when SMR says that object can be
> deleted I must check counter again, and if counter is not zero, don't
> delete the object. Am I right?
>
>
just loaded from got deleted. So it does not increment the refcount
and instead reloads the new pointer value and tries that. PDR
ensures that all readers have finished with all that before deleting
the old object plus its refcount.
>
>
>>RCU is really only
>>good for short term references. Refcounting handles the longer
>>term non-local references in global storage.
>
>
> But atomic_ptr and pc_sample don't handle long term references well,
> because of back-link list. I.e. if one object in back-link list would
> not be deleted very long time, then all "newer" objects would not be
> deleted too...
>
collecting using atomic_ptr. appc on my sourceforge site.
Chris Thomasson
> On 5 , 05:46, Joe Seigh <jseigh...@xemaps.com> wrote:
>
>> PDR is more of a multi-threading design pattern. atomic_ptr is
>> atomically thread-safe lock-free reference counting. I think
>> I called it differential reference counting at one point.
> differential reference counting - is better... hmm... DRC...
>
>
>> Another way to do atomically thread-safe lock-free reference counting
>> is to use some other PDR scheme to manage the reference counts so
>> they can be safely incremented. You'll see atomic decrements if not
>> zero with these. Examples are rcu_ref in the Linux kernel or using
>> RCU+SMR.
>
> In such scheme, if counter drops to zero I must defer object deletion
> with SMR (for example), and then, when SMR says that object can be
> deleted I must check counter again, and if counter is not zero, don't
> delete the object. Am I right?
Not exactly; I think you can get a race-condition if you go that route...
Anyway, I have full-blown working example of this in AppCore:
http://appcore.home.comcast.net/appcore/include/cpu/i686/ac_i686_lfgc_refcount_h.html
ac_i686_lfgc_refcount_addref == atomic acquire
ac_i686_lfgc_refcount_release == atomic release
For atomic acquire you must get a SMR reference first, and then you only
increment the reference counter IF the its 'greater' than 0... If the count
is indeed 'greater' than 0, well you can increment the counter and release
the SMR reference. After you do all of that, then you own a reference. If
the counter was less than 1, you do not increment anything and just drop the
SMR reference and return NULL to the caller... CAS is used to conditionally
increment the counter. For atomic release you defer to SMR when count drop
to zero. When SMR says object can be deleted, you can just delete... IMHO,
using SMR/RCU for atomic reference counting is overkill.
>> RCU is really only
>> good for short term references. Refcounting handles the longer
>> term non-local references in global storage.
>
> But atomic_ptr and pc_sample don't handle long term references well,
> because of back-link list. I.e. if one object in back-link list would
> not be deleted very long time, then all "newer" objects would not be
> deleted too...
Correct.
>> SMR hazard pointers...
>
> Are there other worthwhile techniques?
>
> For now it seems that there is no good choice of techniques. And all
> of them have some limitations. Or they can handle only short term
> references (RCU), or they can handle bounded number of references
> (SMR), or they have too big overheads (reference counting)...
>
> Chris Thomasson claims that vZOOM can handle unbounded number of
> objects *and* good for long term references *and* have zero overheads
> on reader side...
Yes: vZOOM can indeed handle unbounded references with *zero-overheads. A
reference that is held for a long time will not hold up the destruction of
other objects.
With vZOOM you can acquire a so-called "persistent" reference to an object
that you expect to hold for a long time. On the flip side, you can acquire
"non-persistent" reference to an object that you expect to hold for only a
short time...
*-
This means that there are no interlocked RMW and/or membar instructions
required to acquire or release a "persistent" or "non-persistent" reference
to a shared data-structure(s).
Chris Thomasson
Well, I use POSIX to publish an object:
1. vzoom = pthread_getspecific(...)
2. alloc new node
3. lock your_collection->lock
4. init/config new node
5. unlock vzoom->memory_lock
6. lock vzoom->memory_lock
7. make new node visible to readers
8. unlock your_collection->lock
The standard guarantees that the following works:
1. Step 4 can't sink below step 5
2. Step 7 can't rise above step 6
That's all I need in order to make vZOOM work wrt the writer-side. In other
words, POSIX guarantees me that the object will be fully visible before a
reader gets a chance to see it. However, your point is a good one. I guess I
should say that vZOOM can work perfectly with POSIX on the writer-side, and
the reader-side is an implementation detail.
Dmitriy Vyukov
> > In such scheme, if counter drops to zero I must defer object deletion
> > with SMR (for example), and then, when SMR says that object can be
> > deleted I must check counter again, and if counter is not zero, don't
> > delete the object. Am I right?
>
> If the reader sees a refcount of zero, it means the global pointer it
> just loaded from got deleted. So it does not increment the refcount
> and instead reloads the new pointer value and tries that. PDR
> ensures that all readers have finished with all that before deleting
> the old object plus its refcount.
Yes, I am foolish here.
Additional PDR here just to ensure that counter itself will not be
deleted right under threads very nose.
> atomic_ptr doesn't have a back link list. You're thinking of a proxy
> collecting using atomic_ptr. appc on my sourceforge site.
And I am foolish here too.
Dmitriy V'jukov
Dmitriy Vyukov
> Not exactly; I think you can get a race-condition if you go that route...
> For atomic acquire you must get a SMR reference first, and then you only
> increment the reference counter IF the its 'greater' than 0... If the count
> is indeed 'greater' than 0, well you can increment the counter and release
> the SMR reference. After you do all of that, then you own a reference. If
> the counter was less than 1, you do not increment anything and just drop the
> SMR reference and return NULL to the caller... CAS is used to conditionally
> increment the counter. For atomic release you defer to SMR when count drop
> to zero. When SMR says object can be deleted, you can just delete... IMHO,
> using SMR/RCU for atomic reference counting is overkill.
Yes, I am foolish here.
Additional PDR here just to ensure that counter itself will not be
deleted right under threads very nose.
Dmitriy V'jukov
Dmitriy Vyukov
> That's all I need in order to make vZOOM work wrt the writer-side. In other
> words, POSIX guarantees me that the object will be fully visible before a
> reader gets a chance to see it.
Afaik NOT
POSIX would guarantee this if you use something like rw-mutex. I.e.
readers must issue mutex_acquire to ensure correct visibility. Think
of memory barrier duality - and writer *and* reader must issue
corresponding membar to ensure correct memory visibility in common
case. I understand that in your case this will work, but afaik POSIX
doesn't garantee it.
Dmitriy V'jukov
Chris Thomasson
> Yes: vZOOM can indeed handle unbounded references with *zero-overheads. A
> reference that is held for a long time will not hold up the destruction of
> other objects.
There is a caveat to this... Hash collisions can force multiple objects to
share the same counter... So, if object A-B map to per-thread counter C, and
object A keeps it reference for long time, well, object B will stay around
until object A drops...
The hash collision thing can be reduced by using large per-thread arrays of
counters... Perhaps, a hundred-thousand counters per-thread, or a clever
hashing algorithm...
Chris Thomasson
> On 5 , 14:48, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> That's all I need in order to make vZOOM work wrt the writer-side. In
>> other
>> words, POSIX guarantees me that the object will be fully visible before a
>> reader gets a chance to see it.
>
> Afaik NOT
> POSIX would guarantee this if you use something like rw-mutex. I.e.
Okay. Humm, this can start to get interesting here... I think I will start
this off here:
GIVEN:
1. vzoom = pthread_getspecific(...)
2. alloc new node
3. lock your_collection->lock
4. init/config new node
5. unlock vzoom->memory_lock
6. lock vzoom->memory_lock
7. make new node visible to readers
8. unlock your_collection->lock
AFAICT POSIX explicitly states that:
1. Step 4 can't sink below step 5
2. Step 7 can't rise above step 6
Well, do you agree? I sure do think that POSIX says this... Humm... Perhaps
David Butenhof can help clarify some of this...
Dmitriy Vyukov
> 1. vzoom = pthread_getspecific(...)
> 2. alloc new node
> 3. lock your_collection->lock
> 4. init/config new node
> 5. unlock vzoom->memory_lock
> 6. lock vzoom->memory_lock
> 7. make new node visible to readers
> 8. unlock your_collection->lock
>
> AFAICT POSIX explicitly states that:
>
> 1. Step 4 can't sink below step 5
> 2. Step 7 can't rise above step 6
>
> Well, do you agree?
Yes, I agree.
But afaik POSIX doesn't guarantee that other threads (that don't use
mutexes) will see step 4 before step 7.
First reason for this, authors of POSIX see on Alpha too.
Second reason, you have data dependency here, but there can
modifications to arbitrary memory locations, and in this case you need
explicit memory barriers for writer *and* for reader too. So POSIX
cannot guarantee that something will be visible w/o acquiring a mutex.
I am not sure if POSIX introduces term "data-dependency" at all...
Dmitriy V'jukov
Dmitriy Vyukov
> Yes, I agree.
> But afaik POSIX doesn't guarantee that other threads (that don't use
> mutexes) will see step 4 before step 7.
I don't understand yet, whether client thread is blocked or not while
the polling thread examining client thread's prefs[] array. But if
client thread is not blocked while the polling thread examining client
thread's prefs[] array, this is not POSIX compatible too. Because the
polling thread reads memory that another thread concurrently modify.
It seems that if you have just "a bit of lock-free", the solution is
not POSIX compatible at all...
Dmitriy V'jukov
Chris Thomasson
The polling thread is a implementation detail. The user need not know about
this. I want the user environment to be compatiable with POSIX. Therefore, I
can allow the user to use POSIX mutexs on the writer-side of the lock-free
reader-pattern... And, data-dependant loads for the reader side.
Chris Thomasson
> On Jun 5, 3:10 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> 1. vzoom = pthread_getspecific(...)
>> 2. alloc new node
>> 3. lock your_collection->lock
>> 4. init/config new node
>> 5. unlock vzoom->memory_lock
>> 6. lock vzoom->memory_lock
>> 7. make new node visible to readers
>> 8. unlock your_collection->lock
>>
>> AFAICT POSIX explicitly states that:
>>
>> 1. Step 4 can't sink below step 5
>> 2. Step 7 can't rise above step 6
>>
>> Well, do you agree?
>
> Yes, I agree.
> But afaik POSIX doesn't guarantee that other threads (that don't use
> mutexes) will see step 4 before step 7.
> I am not sure if POSIX introduces term "data-dependency" at all...
It does not. I am ONLY concerned with the POSIX guarantees wrt mutexs. I
need the rules:
>> 1. Step 4 can't sink below step 5
>> 2. Step 7 can't rise above step 6
To hold for the writer(s). I want the configuration of the node to be
visible before I publish a pointer.
The reader use data-dependant loads. This is an implementation detail in the
form of a externally assembled per-architecture library.
Dmitriy Vyukov
> It does not. I am ONLY concerned with the POSIX guarantees wrt mutexs. I
> need the rules:
>
> >> 1. Step 4 can't sink below step 5
> >> 2. Step 7 can't rise above step 6
>
> To hold for the writer(s). I want the configuration of the node to be
> visible before I publish a pointer.
>
> The reader use data-dependant loads. This is an implementation detail in the
> form of a externally assembled per-architecture library.
Then why not to use store_store_membar() instead of:
5. unlock vzoom->memory_lock
6. lock vzoom->memory_lock
?
store_store_membar() would be implementation detail in the
form of a externally assembled per-architecture library too.
This would guarantee:
Step 4 can't sink below step 7
And this must be faster. NOP on x86 for example.
Dmitriy V'jukov
Dmitriy Vyukov
> It does not. I am ONLY concerned with the POSIX guarantees wrt mutexs. I
> need the rules:
An note that user would have to cope with lock-free sh#t anyway.
Because data-dependant loads don't solve all problems. Just for
example, writer can insert/remove node and increment/decrement size
variable. Reader still have to cope with inconsistent state of data
structure.
Dmitriy V'jukov
Chris Thomasson
> On 7 , 04:23, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> It does not. I am ONLY concerned with the POSIX guarantees wrt mutexs. I
>> need the rules:
>> The reader use data-dependant loads. This is an implementation detail in
>> the
>> form of a externally assembled per-architecture library.
>
> Then why not to use store_store_membar() instead of:
> 5. unlock vzoom->memory_lock
> 6. lock vzoom->memory_lock
> ?
>
> store_store_membar() would be implementation detail in the
> form of a externally assembled per-architecture library too.
[...]
Well, I make sure to use POSIX whenever I can. IMHO, it tends to make things
easier to port to various architectures, even the ones I have not worked
with...
As for the per-arch lib, I can get away with implementing and exporting two
extern "C" functions: atomic swap and atomic load. That's fairly portable.
Humm, I wanted to be as minimalist as I could. It makes things much
easier...
Chris Thomasson
Indeed; the user will have to learn the various forms of the lock-free
reader pattern. You can incorporate versioning techniques on the reader-side
if you need that. Of course, adding new stuff to the reader-side of the
algorithm can have a direct negative effect on its scalability attributes in
general...