Re: CRIS atomics revisited 4/4: give up on alignment of atomic data, RFC for is_lock_free hook

[Hans-Peter Nilsson <hans-peter dot nilsson at axis dot com>]

> From: Andrew MacLeod <amacleod@redhat.com>
> Date: Tue, 17 Jul 2012 14:24:48 +0200

> On 07/15/2012 11:49 PM, Hans-Peter Nilsson wrote:
> > Well, give up by default that is, and fix it up in a helper
> > function in glibc to hold a global byte-sized atomic lock for
> > the duration.  (Sorry!)  Yes, this means that
> > fold_builtin_atomic_always_lock_free is wrong.  It knows about
> > alignment in general but doesn't handle the case where the
> > default alignment of the underlying type is too small for atomic
> > accesses, and should probably be augmented by a target hook,
> > alternatively, change the allow_libcall argument in the call to
> > can_compare_and_swap_p to false.  I guess I should open a PR for
> > this and add a test-case.  Later.
> 
> I set it up to eventually handle alignment issues, but didn't really 
> know any details of what to do when, or how.  Input was rather lacking 
> at the time and there was a time crunch, so I just punted on it in 4.7 
> at the tree level and targets did their own thing.

Most (all but mine :) seem happy to provide naturally-aligned
types and promising to never access non-naturally-aligned data
so not much they need to do...  Not sure if the i386 ABI (or
e.g. xchg and similar insns in the CPU) promises or requires
that all data (ints) are aligned or if something is nominally
required.

>  The library idea was 
> new enough that the standards guys couldnt/wouldn't give me a straight 
> answer since it hadn't really been thought through I don't think.  My 
> apologies if I misrepresent anyone there :-)
> 
> The basic problem you are dealing with is a 4 byte object that is not 
> aligned properly, so the  lock-free instructions don't work on it., but 
> 'always_lock_free' says "yes, that type is lock free". Then in the 
> library,

(The library here meaning the atomicity implementation, not
e.g. libstdc++.  I assume you don't mean libatomic, which seems
to be intended just as a fallback for targets and sizes
unsupported by core gcc, so they're guaranteed to not be
lock-free.)

> its implemented via a lock?  Is that approximately it?  or is 
> there an additional issue?

That's pretty much it...  except it'd be better letting the
target decorate the intended atomic type, e.g. with alignment
attributes.  See suggestion last.  Decoration is in place for
_Atomic_word but I can't tell how _Atomic_word relates to the
issues here.  Is _Atomic_word just obsolete?

> The original intention was that  __atomic{is,always}_lock_free takes the 
> size and a pointer to the object, and the alignment of the pointer 
> object would be checked at compile time to see if it is always 
> compatible with size.

The alignment of the pointed-to *object* can't be checked at
compile-time.  As GCC is pretty bad at alignment, taking on the
task of trying to make a difference for different *types* seems
non-trivial.  All you can hope for is telling apart the size of
the objects.

Alignment of objects *can* be checked at run-time from within
the current __atomic_is_lock_free API, and apparently that's the
intention in the core gcc implementation, but the last few
details aren't there or are wrong.

> (so a char pointer to a 4 byte object would fail 
> that test). which would means 'always_lock_free' should return false, 
> and in turn a call to 'is_lock_free' would generate a library call and 
> check the alignment at runtime of the object to determine what to do.    

For the record, is_lock_free in libstdc++ calls
__atomic_is_lock_free, which is per-instance at the API level.
I don't see usage of __atomic_always_lock_free in libstdc++.
(I see it in libatomic/glfree.c:libat_is_free, but dominated by
a check for natural alignment of the pointer instance with
failure yielding false, bravo.)

Not using __atomic_always_lock_free is probably wrong, it seems
it should call __atomic_always_lock_free if I understand
/path/to/trunk/libstdc++-v3/doc/html/ext/lwg-closed.html#1146
correctly (the link to www.open-std.org there is dead).  Can
this be confirmed?  Still wouldn't work of course - the target
can't doesn't have a say in the __atomic_always_lock_free
implementation.

> The library implementation of all the other __atomic operations would 
> check 'is_lock_free' to see whether they need to use a lock, or whether 
> they can use available lock-free sequences/syscalls.

(You must mean libstdc++ here which is slightly confusing with
the use of "__atomic_" which for me implies the gcc
implementation.)

> Some confusion around the standard surfaced and the intention from the 
> standard point of view appeared to be that 'is_lock_free' should be true 
> or false ALL the time for a given type.

And there's confusion all around telling apart atomic access
from *lock-free* atomic access. :-)  Witness
__GCC_ATOMIC_INT_LOCK_FREE and the md.texi note: "For the
purposes of C++11 @code{std::atomic::is_lock_free}, it is
assumed that these library calls do @emph{not} use any kind of
interruptable locking".

Come to think of it, what is "interruptable locking"?
(More STFW hits for "interruptible locking" FWIW.)
I don't remember in which of the search hits I read it, but I
came to the conclusion that if there exists a place where a
signal can hit a thread such that *other* threads would be
halted, then operations are not lock-free.  (For example if you
single-step for a thread accessing an object in gdb, at no point
should it be possible for other threads to hang "spinning" while
trying to do atomic access on the object.)

I can imagine a more weasly-worded definition, but then I
wouldn't see the difference between an instruction locking a
word or a cache-line (excluding other threads and possibly
memory-accessing machinery) while performing the atomicity, to
that of a library function acquiring a common misalignment-lock
for the duration of the atomic operation.

>    This possibly is related to 
> the separation of gcc's built-ins from the implementation details of the 
> standard  (ie the standard uses the built-ins but only with aligned 

"the standard" meaning libstdc++ I presume.
Let's try and avoid confusing gcc core atomics with libstdc++
needs; let's say gcc and libstdc++.

> objects, but those built-ins can also still be used outside the standard 
> in more chaotic ways)

You mean libstdc++ applies is_atomic only to _Atomic_word
things? ...looking... no, IIUC.  Is this confusion important?

> So in the end, i wasn't sure what to do and ran out of time.  Making it 
> better for 4.8 would be goodness.  Is there a fatal flaw in the original 
> (unimplemented) intention?  if so, can it be fixed without changing the API?

Which API?

The gcc builtins API to "user" source code (i.e. to libstdc++)?
Sure.  Some values may change; __GCC_ATOMIC_INT_LOCK_FREE would
be 1 ("no...?"), not 2 ("Sure!").  (Weird that 0 isn't used, but
you probably already noticed that. :)

The libstdc++ API to its users?  Sure, but it seems the
libstdc++ code should be changed to use
__atomic_always_lock_free (see above).

The gcc target back-end API?  Maybe... but only of code is
changed to default to return false for __atomic_always_lock_free
and __atomic_is_lock_free, when the underlying type has less
than natural alignment (don't confuse this with comparing
against the *default* alignment, that confusion is already
implemented).  For __atomic_is_lock_free, a new hook, maybe even
a target MD pattern, is recommended to avoid having to err on
the safe side.  Or shorter, for __atomic_is_lock_free, change it
to do what's in libatomic/glfree.c:libat_is_free.

An improvement affecting all APIs would be a (new) __attribute__
((__atomic_lock_free__)), where the target gets to add things
like alignment to make lock-free atomicity certain to the
object, or make compilation fail.

> Any PR's you open related this this, copy me on them and I'll try to get 
> them addressed.

Thanks in advance.  I'm not too well-versed with trees, or I
might have a try at presumed one-liners.

brgds, H-P