Global Lock-Free Proxy Collector Anchor Scheme...

37 views
Skip to first unread message

Chris Thomasson

unread,
May 27, 2007, 7:43:54 PM5/27/07
to
Using pc_sample.c:


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?

;^)

Message has been deleted

Ulrich Kroemer

unread,
May 28, 2007, 10:58:03 AM5/28/07
to
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.

David Hopwood

unread,
May 28, 2007, 11:40:29 AM5/28/07
to
Ulrich Kroemer > wrote:
> 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

unread,
May 28, 2007, 11:01:27 PM5/28/07
to
"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

/* 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

unread,
May 29, 2007, 1:12:34 AM5/29/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:ytydnb2zhq1YC8bb...@comcast.com...

> "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

unread,
May 29, 2007, 1:24:49 AM5/29/07
to
very similar to read-write locks.

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

unread,
May 29, 2007, 2:42:00 AM5/29/07
to
On May 29, 9:24 am, "Chris Thomasson" <cris...@comcast.net> wrote:

> PDR = PCOW Deferred Destruction

Deferred Reclamation?

Dmitriy V'jukov

Dmitriy Vyukov

unread,
May 29, 2007, 3:02:09 AM5/29/07
to
On May 28, 7:40 pm, David Hopwood <david.hopw...@industrial-
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

unread,
May 29, 2007, 3:37:48 AM5/29/07
to

"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

unread,
May 29, 2007, 4:21:25 AM5/29/07
to
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!
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

unread,
May 29, 2007, 6:16:13 AM5/29/07
to

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.

Message has been deleted

Chris Thomasson

unread,
May 29, 2007, 10:56:12 PM5/29/07
to
"Elcaro Nosille" <Elcaro....@mailinator.com> wrote in message
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.
>
> "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.

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

unread,
May 29, 2007, 10:57:52 PM5/29/07
to
>> Chris posts his buggy undocumented code every few days and this doesn't
>> 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

unread,
May 30, 2007, 12:58:02 AM5/30/07
to
David Hopwood wrote:
> Ulrich Kroemer > wrote:
>> 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.
>
Agreed.

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

unread,
May 30, 2007, 1:43:03 AM5/30/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1180426885.7...@r19g2000prf.googlegroups.com...

> 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

unread,
May 30, 2007, 1:46:47 AM5/30/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:pImdnW-8vJMSSsbb...@comcast.com...

I was thinking C++ for some reason.

Chris Thomasson

unread,
May 30, 2007, 1:51:55 AM5/30/07
to
"David Hopwood" <david....@industrial-designers.co.uk> wrote in message
news:NJC6i.20734$4a.1...@fe3.news.blueyonder.co.uk...
^^^^^^^^^^^^

Humm... Perhaps.

Dmitriy Vyukov

unread,
May 30, 2007, 3:26:31 PM5/30/07
to
On May 29, 11:36 pm, Elcaro Nosille <Elcaro.Nosi...@mailinator.com>
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

unread,
May 30, 2007, 3:31:06 PM5/30/07
to
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.


Dmitriy V'jukov

Dmitriy Vyukov

unread,
May 30, 2007, 3:56:19 PM5/30/07
to
On May 30, 9:43 am, "Chris Thomasson" <cris...@comcast.net> wrote:

> 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

unread,
May 30, 2007, 3:56:36 PM5/30/07
to
On May 29, 2:16 pm, Joe Seigh <jseigh...@xemaps.com> wrote:

> 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

unread,
May 30, 2007, 4:09:57 PM5/30/07
to
On May 29, 2:16 pm, Joe Seigh <jseigh...@xemaps.com> wrote:

> 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

unread,
May 30, 2007, 5:41:11 PM5/30/07
to
In article <1180553466.5...@g37g2000prf.googlegroups.com>,

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

unread,
May 30, 2007, 8:33:58 PM5/30/07
to

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

unread,
May 30, 2007, 8:44:07 PM5/30/07
to

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.

Message has been deleted

Ian Collins

unread,
May 31, 2007, 1:39:22 AM5/31/07
to
Steve Watt wrote:
> 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

unread,
May 31, 2007, 6:08:43 AM5/31/07
to
Elcaro Nosille wrote:
> 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

unread,
May 31, 2007, 2:06:45 PM5/31/07
to
On May 31, 4:44 am, Joe Seigh <jseigh...@xemaps.com> wrote:

> 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

unread,
May 31, 2007, 2:25:59 PM5/31/07
to
On May 31, 9:36 am, Elcaro Nosille <Elcaro.Nosi...@mailinator.com>
wrote:

> lock-free code is unsuitable for most producer-consumer patterns

What are you mean? Can you explain more detailed?


Dmitriy V'jukov


Message has been deleted

Szabolcs Ferenczi

unread,
May 31, 2007, 6:20:44 PM5/31/07
to
On May 31, 11:57 pm, Elcaro Nosille <Elcaro.Nosi...@mailinator.com>

wrote:
> >> lock-free code is unsuitable for most producer-consumer patterns
> > What are you mean? Can you explain more detailed?
>
> 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.

Best Regards,
Szabolcs

Dmitriy Vyukov

unread,
May 31, 2007, 11:24:16 PM5/31/07
to
On May 31, 9:36 am, Elcaro Nosille <Elcaro.Nosi...@mailinator.com>
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

unread,
Jun 1, 2007, 4:19:10 AM6/1/07
to
On Jun 1, 2:20 am, Szabolcs Ferenczi <szabolcs.feren...@gmail.com>
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

unread,
Jun 1, 2007, 4:31:02 PM6/1/07
to
On Jun 1, 10:19 am, Dmitriy Vyukov <dvyu...@gmail.com> wrote:

> 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

unread,
Jun 4, 2007, 1:09:32 PM6/4/07
to
On May 31, 4:33 am, Joe Seigh <jseigh...@xemaps.com> wrote:

> 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

unread,
Jun 4, 2007, 9:46:02 PM6/4/07
to

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

unread,
Jun 5, 2007, 3:54:59 AM6/5/07
to
"Elcaro Nosille" <Elcaro....@mailinator.com> wrote in message
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?
>
> With lock-free algorithms it isn't possible to block whenn a FIFO-queue
> is empty.

WRONG!!!

Ever read anything about an eventcount!?


;^/

Chris Thomasson

unread,
Jun 5, 2007, 3:59:56 AM6/5/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1180685950.4...@z28g2000prd.googlegroups.com...
> queue is not empty.

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

unread,
Jun 5, 2007, 4:04:30 AM6/5/07
to
"Szabolcs Ferenczi" <szabolcs...@gmail.com> wrote in message
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

unread,
Jun 5, 2007, 4:06:27 AM6/5/07
to
"Elcaro Nosille" <Elcaro....@mailinator.com> wrote in message
news:465e5e4b$0$20290$9b4e...@newsspool3.arcor-online.net...
> 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.
>
> The problem is that you can't rely on Chris' code as it is often buggy;

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

unread,
Jun 5, 2007, 4:15:28 AM6/5/07
to
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...

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

unread,
Jun 5, 2007, 4:20:26 AM6/5/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
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

unread,
Jun 5, 2007, 4:25:26 AM6/5/07
to

"Chris Thomasson" <cri...@comcast.net> wrote in message
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...

https://coolthreads.dev.java.net/servlets/ProjectForumMessageView?forumID=1797&messageID=11068

Dmitriy Vyukov

unread,
Jun 5, 2007, 5:32:46 AM6/5/07
to
On 5 , 12:20, "Chris Thomasson" <cris...@comcast.net> wrote:

> 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

unread,
Jun 5, 2007, 5:57:05 AM6/5/07
to
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.

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

unread,
Jun 5, 2007, 6:20:57 AM6/5/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1181035966.1...@w5g2000hsg.googlegroups.com...

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

unread,
Jun 5, 2007, 6:24:06 AM6/5/07
to
On 5 , 14:20, "Chris Thomasson" <cris...@comcast.net> wrote:

> > 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

unread,
Jun 5, 2007, 6:40:37 AM6/5/07
to
Dmitriy Vyukov wrote:
> 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?
>
>
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.

>
>
>>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...
>
atomic_ptr doesn't have a back link list. You're thinking of a proxy
collecting using atomic_ptr. appc on my sourceforge site.

Chris Thomasson

unread,
Jun 5, 2007, 6:39:37 AM6/5/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1181037425.4...@q66g2000hsg.googlegroups.com...

> 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

unread,
Jun 5, 2007, 6:48:32 AM6/5/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1181039046....@p47g2000hsd.googlegroups.com...

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

unread,
Jun 5, 2007, 6:46:56 AM6/5/07
to
On 5 , 14:40, Joe Seigh <jseigh...@xemaps.com> wrote:

> > 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

unread,
Jun 5, 2007, 6:49:23 AM6/5/07
to
On 5 , 14:39, "Chris Thomasson" <cris...@comcast.net> wrote:

> 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

unread,
Jun 5, 2007, 6:57:51 AM6/5/07
to
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.
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

unread,
Jun 5, 2007, 7:04:20 AM6/5/07
to
[...]

> 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

unread,
Jun 5, 2007, 7:10:06 AM6/5/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1181041071.1...@g4g2000hsf.googlegroups.com...

> 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

unread,
Jun 5, 2007, 9:19:01 AM6/5/07
to
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.

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

unread,
Jun 5, 2007, 4:03:33 PM6/5/07
to
On Jun 5, 5:19 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:

> 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

unread,
Jun 6, 2007, 8:19:28 PM6/6/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1181073813.2...@d30g2000prg.googlegroups.com...

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

unread,
Jun 6, 2007, 8:23:24 PM6/6/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1181049541.8...@n15g2000prd.googlegroups.com...

> 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

unread,
Jun 7, 2007, 4:01:46 AM6/7/07
to
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:
>
> >> 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

unread,
Jun 7, 2007, 4:11:12 AM6/7/07
to
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:

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

unread,
Jun 7, 2007, 6:37:13 PM6/7/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1181203306.7...@o5g2000hsb.googlegroups.com...

> 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

unread,
Jun 7, 2007, 7:21:57 PM6/7/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1181203872....@k79g2000hse.googlegroups.com...

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...


Reply all
Reply to author