RE: [PATCH][RFC] Remove volatile from data members in libstdc++

["Boehm, Hans" <hans dot boehm at hp dot com>]

Looking more carefully at the rope sources, I think the following are
true:

1) Rope usually uses reference counts, as it always did.

2) Once upon a time (around 2.95 and shortly thereafter), it did this
reasonably intelligently on a few platforms (Irix and win32, mostly) by
using atomic operations.  It used pthread locks on Linux.  The refcount
field was not volatile.  This was probably officially incorrect, since
it did some refcount == 1 tests outside a lock.  (The logic is such that
once you see refcount==1, it's guaranteed to stay that way.  Thus it
probably worked in all cases, but it clearly violated pthread rules.)

3) It appears that at some later point the use of atomic operations was
dropped, and it now always uses locks?  This strikes me as a serious
mistake, since my recollection is that performance drops through the
floor when you do that.  It really needed to use atomic operations on
more platforms, not fewer.

4) At some point atomicity.h was added.  It operates on volatiles.  It
has to, since it doesn't provide an atomic read operation, and I suspect
a bunch of clients read the values directly.  Thus if it didn't operate
on volatiles it might actually yield incorrect results on common
platforms; this way it's not in any sense standard conforming, but
probably works.

5) At some point the rope reference count field became volatile.  This
is the right thing, since it should be using atomicity.h, and the type
of the reference count field should be changed suitably.  It's also
perhaps the right thing since the refcount==1 tests are still carried
out without a lock.  But it wasn't carried far enough.

6) Eventually this should use something like atomic<intptr_t>, if/when
that makes it into the standard.  At that point, the volatiles should
probably disappear, and all accesses, including the ref_count == 1
tests, should use the proper accessors.  Currently I believe the proper
accessors don't exist, so volatile is the best we can do.
(I noticed that on my IA64/Debian box atomicity.h operates on ints,
which seems wrong for general reference counts without an overflow
check.  A pointer-sized int seems more appropriate.  Is there an
alternative I overlooked?)

Changing the rope reference counts to any form of atomics would be a
great improvement.

Hans

> -----Original Message-----
> From: Richard Guenther [mailto:rguenther@suse.de] 
> Sent: Tuesday, July 11, 2006 3:08 AM
> To: Boehm, Hans
> Cc: Paolo Carlini; gcc-patches@gcc.gnu.org; libstdc++@gcc.gnu.org
> Subject: RE: [PATCH][RFC] Remove volatile from data members 
> in libstdc++
> 
> On Mon, 10 Jul 2006, Boehm, Hans wrote:
> 
> > It's been a long time ...
> > 
> > Looking at rope, the volatile declarations in front of 
> __tmp make no 
> > sense to me, though I probably put them there.
> > 
> > The ones in front of _M_ref_count are trickier.  These are accessed 
> > outside a lock in some cases.  (The lock may not even exist 
> if atomic 
> > updates are used.)  I think there is currently no way to do this 
> > correctly.  The accesses should use some sort of "load 
> atomically w.r.t.
> > threads and do not cache" primitive, but I don't think we currently 
> > have that.  (There is an effort to fix this in the C++ standards 
> > committee, see 
> > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2047.html)
> >
> > Given that volatile generally has that effect, my 
> inclination would be 
> > to leave it for now.
> 
> It does not.  libstdc++ has atomic primitives that should be 
> used for _M_ref_count if that is required.
> 
> > In my view, the real problem here is that we have to cheat, because 
> > reference counting with locks is too slow.  But we don't have 
> > sufficient primitives to cheat correctly.
> 
> Cheating is no solution - the hardware is part of the player 
> wrt atomicity, not only compiler optimizations.  So, if 
> _M_ref_count shall be updated atomically and not cached you 
> need _M_ref_count being an atomic type, use atomic primitives 
> to decrement it.
> 
> > I don't think I directly wrote either of the allocators under 
> > discussion here.  I'm not sure there's a good reason for 
> the volatile 
> > declarations in pool_allocator, and it may be safe to remove them.  
> > The question is whether the free_list entries are ever 
> updated without 
> > a lock, relying on the atomicity of the underlying hardware 
> > instructions.  It looks to me like the answer is probably no, but I 
> > cannot reconstruct the original reason for the 
> declarations.  (Again, 
> > even if they are updated without a lock, "volatile" isn't the right 
> > tool.  But we don't have the right tool.
> > 
> > For mt_allocator.h, I would definitely try to contact the original 
> > authors, at least if this is viewed as important.
> > 
> > My real inclination would be to remove the volatile 
> declarations for 
> > __tmp in the rope implementation, and leave the rest of 
> this until it 
> > becomes clear what C++0X has to say about atomic 
> operations, at which 
> > point a lot of this will have to be looked at carefully.
> 
> Well, I raised this topic (again) because _if_ the volatiles 
> are there for a (wrong) reason, there are latent bugs in the 
> allocators and rope.
> Because volatile cannot do anything to improve locking or 
> serialization other than maybe make the compiler emit useless 
> loads and stores.
> 
> Richard.
> 
> --
> Richard Guenther <rguenther@suse.de>
> Novell / SUSE Labs
>