Re: better atomics

On Wed, Oct 16, 2013 at 12:52 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>> I have a related problem, which is that some code I'm currently
>> working on vis-a-vis parallelism can run lock-free on platforms with
>> atomic 8 bit assignment but needs a spinlock or two elsewhere. So I'd
>> want to use pg_atomic_store_u64(), but I'd also need a clean way to
>> test, at compile time, whether it's available.
>
> Yes, definitely. There should be a couple of #defines that declare
> whether non-prerequisite options are supported. I'd guess we want at least:
> * 8byte math
> * 16byte compare_and_swap

I'm not terribly excited about relying on 16-byte CAS, but I agree
that 8-byte math, at least, is important. I've not been successful in
finding any evidence that gcc has preprocessor symbols to tell us
about the properties of 8-byte loads and stores. The closest thing
that I found is:

http://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

That page provides intrinsics for 8-byte atomic loads and stores,
among other things. But it seems that the only method for determining
whether they work on a particular target is to compile a test program
and see whether it complains about __atomic_load_n and/or
__atomic_store_n being unresolved symbols. I suppose we could add a
configure test for that. Yuck.

Anyone have a better idea?

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 2013-10-28 14:10:48 -0400, Robert Haas wrote:
> On Wed, Oct 16, 2013 at 12:52 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> >> I have a related problem, which is that some code I'm currently
> >> working on vis-a-vis parallelism can run lock-free on platforms with
> >> atomic 8 bit assignment but needs a spinlock or two elsewhere. So I'd
> >> want to use pg_atomic_store_u64(), but I'd also need a clean way to
> >> test, at compile time, whether it's available.
> >
> > Yes, definitely. There should be a couple of #defines that declare
> > whether non-prerequisite options are supported. I'd guess we want at least:
> > * 8byte math
> > * 16byte compare_and_swap
>
> I'm not terribly excited about relying on 16-byte CAS, but I agree
> that 8-byte math, at least, is important. I've not been successful in
> finding any evidence that gcc has preprocessor symbols to tell us
> about the properties of 8-byte loads and stores. The closest thing
> that I found is:

I am talking about making 16byte CAS explicitly optional though? I think
if code wants to optionally make use of it (e.g. on x86 where it's been
available basically forever) that's fine. It just has to be optional.
Or are you saying you're simply not interested in 16byte CAS generally?

Same thing for 8byte math - there's no chance that that is going to be
supported over all platforms anytime soon, so it has to be optional.

> http://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html
>
> That page provides intrinsics for 8-byte atomic loads and stores,
> among other things. But it seems that the only method for determining
> whether they work on a particular target is to compile a test program
> and see whether it complains about __atomic_load_n and/or
> __atomic_store_n being unresolved symbols. I suppose we could add a
> configure test for that. Yuck.

Well, that's pretty easy to integrate into configure - and works on
crossbuilds. So I think that'd be ok.

But I actually think this is going to be a manual thing, atomic 8byte
math will fall back to kernel emulation on several targets, so we
probably want some defines to explicitly declare it supported on targets
where that's not the case.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Mon, Oct 28, 2013 at 2:19 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>> I'm not terribly excited about relying on 16-byte CAS, but I agree
>> that 8-byte math, at least, is important. I've not been successful in
>> finding any evidence that gcc has preprocessor symbols to tell us
>> about the properties of 8-byte loads and stores. The closest thing
>> that I found is:
>
> I am talking about making 16byte CAS explicitly optional though? I think
> if code wants to optionally make use of it (e.g. on x86 where it's been
> available basically forever) that's fine. It just has to be optional.
> Or are you saying you're simply not interested in 16byte CAS generally?

I am just not interested in it generally. Relying on too many OS or
architecture-specific primitives has several disadvantages. It's
going to be a nuisance on more obscure platforms where they may or may
not be supported and may or may not work right even if supported.
Even once we get things working right everywhere, it'll mean that
performance may suffer on non-mainstream platforms. And I think in
many cases it may suggest that we're using an architecture-specific
quirk to work around a fundamental problem with our algorithms. I'm
more or less convinced of the need for 8-byte atomic reads and writes,
test-and-set, 8-byte compare-and-swap, and 8-byte fetch-and-add. But
beyond that I'm less sold. Most of the academic papers I've read on
implementing lock-free or highly-parallel constructs attempt to
confine themselves to 8-byte operations with 8-byte compare-and-swap,
and I'm a bit disposed to think we ought to try to hew to that as
well. I'm not dead set against going further, but I lean against it,
for all of the reasons mentioned above.

> Same thing for 8byte math - there's no chance that that is going to be
> supported over all platforms anytime soon, so it has to be optional.

Agreed.

>> http://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html
>>
>> That page provides intrinsics for 8-byte atomic loads and stores,
>> among other things. But it seems that the only method for determining
>> whether they work on a particular target is to compile a test program
>> and see whether it complains about __atomic_load_n and/or
>> __atomic_store_n being unresolved symbols. I suppose we could add a
>> configure test for that. Yuck.
>
> Well, that's pretty easy to integrate into configure - and works on
> crossbuilds. So I think that'd be ok.
>
> But I actually think this is going to be a manual thing, atomic 8byte
> math will fall back to kernel emulation on several targets, so we
> probably want some defines to explicitly declare it supported on targets
> where that's not the case.

Hmm, OK. I had not come across such cases. There are architectures
where it Just Works (like x64_64), architectures where you can make it
work by using special instructions (like x86), and (presumably)
architectures where it doesn't work at all. Places where it works
using really slow kernel emulation are yet another category to worry
about. Unfortunately, I have not found any good source that describes
which architectures fall into which category. Without that, pulling
this together seems intimidating, unless we just declare it working
for x86_64, disable it everywhere else, and wait for people running on
other architectures to complain.

I wonder whether it'd be safe to assume that any machine where
pointers are 8 bytes has 8-byte atomic loads and stores. I bet there
is a counterexample somewhere. :-(

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 2013-10-28 15:02:41 -0400, Robert Haas wrote:
> On Mon, Oct 28, 2013 at 2:19 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> >> I'm not terribly excited about relying on 16-byte CAS, but I agree
> >> that 8-byte math, at least, is important. I've not been successful in
> >> finding any evidence that gcc has preprocessor symbols to tell us
> >> about the properties of 8-byte loads and stores. The closest thing
> >> that I found is:
> >
> > I am talking about making 16byte CAS explicitly optional though? I think
> > if code wants to optionally make use of it (e.g. on x86 where it's been
> > available basically forever) that's fine. It just has to be optional.
> > Or are you saying you're simply not interested in 16byte CAS generally?
>
> I am just not interested in it generally. Relying on too many OS or
> architecture-specific primitives has several disadvantages. It's
> going to be a nuisance on more obscure platforms where they may or may
> not be supported and may or may not work right even if supported.
> Even once we get things working right everywhere, it'll mean that
> performance may suffer on non-mainstream platforms.

But it'll suffer against the *increased* performance on modern
platforms, it shouldn't suffer noticeably against the previous
performance on the older platform if we're doing our homework...

> Most of the academic papers I've read on
> implementing lock-free or highly-parallel constructs attempt to
> confine themselves to 8-byte operations with 8-byte compare-and-swap,
> and I'm a bit disposed to think we ought to try to hew to that as
> well. I'm not dead set against going further, but I lean against it,
> for all of the reasons mentioned above.

I think there are quite some algorithms relying on 16byte CAS, that's
why I was thinking about it at all. I think it's easier to add support
for it in the easier trawl through the compilers, but I won't argue much
for it otherwise for now.

> > But I actually think this is going to be a manual thing, atomic 8byte
> > math will fall back to kernel emulation on several targets, so we
> > probably want some defines to explicitly declare it supported on targets
> > where that's not the case.
>
> Hmm, OK. I had not come across such cases.

E.g. ARM/linux which we probably cannot ignore.

> Places where it works
> using really slow kernel emulation are yet another category to worry
> about. Unfortunately, I have not found any good source that describes
> which architectures fall into which category. Without that, pulling
> this together seems intimidating, unless we just declare it working
> for x86_64, disable it everywhere else, and wait for people running on
> other architectures to complain.

Yes, I think whitelisting targs is a sensible approach here. I am pretty
sure we can do better than just x86-64, but that's easily doable in an
incremental fashion.

> I wonder whether it'd be safe to assume that any machine where
> pointers are 8 bytes has 8-byte atomic loads and stores. I bet there
> is a counterexample somewhere. :-(

Sparc64 :(.

Btw, could you quickly give some keywords what you're thinking about
making lockless?
I mainly am thinking about lwlocks and buffer pins so far. Nothing
really ambitious.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Mon, Oct 28, 2013 at 3:32 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>> I wonder whether it'd be safe to assume that any machine where
>> pointers are 8 bytes has 8-byte atomic loads and stores. I bet there
>> is a counterexample somewhere. :-(
>
> Sparc64 :(.
>
> Btw, could you quickly give some keywords what you're thinking about
> making lockless?
> I mainly am thinking about lwlocks and buffer pins so far. Nothing
> really ambitious.

Well, I was going to use it for some code I'm working on for
parallelism, but I just tested the overhead of a spinlock, and it was
zero, possibly negative. So I may not have an immediate application.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 28.10.2013 21:32, Andres Freund wrote:
> On 2013-10-28 15:02:41 -0400, Robert Haas wrote:
>> Most of the academic papers I've read on
>> implementing lock-free or highly-parallel constructs attempt to
>> confine themselves to 8-byte operations with 8-byte compare-and-swap,
>> and I'm a bit disposed to think we ought to try to hew to that as
>> well. I'm not dead set against going further, but I lean against it,
>> for all of the reasons mentioned above.
>
> I think there are quite some algorithms relying on 16byte CAS, that's
> why I was thinking about it at all. I think it's easier to add support
> for it in the easier trawl through the compilers, but I won't argue much
> for it otherwise for now.

Many algorithms require a 2*(pointer width) CAS instruction. On 64-bit
platforms that's 16 bytes, but on 32-bit platforms an 8 byte version
will suffice.

- Heikki

Heikki Linnakangas <hlinnakangas(at)vmware(dot)com> writes:
> On 28.10.2013 21:32, Andres Freund wrote:
>> I think there are quite some algorithms relying on 16byte CAS, that's
>> why I was thinking about it at all. I think it's easier to add support
>> for it in the easier trawl through the compilers, but I won't argue much
>> for it otherwise for now.

> Many algorithms require a 2*(pointer width) CAS instruction. On 64-bit
> platforms that's 16 bytes, but on 32-bit platforms an 8 byte version
> will suffice.

You're both just handwaving. How many is "many", and which ones might
we actually have enough use for to justify dealing with such a dependency?
I don't think we should buy into this without some pretty concrete
justification.

regards, tom lane

On 2013-10-28 16:06:47 -0400, Tom Lane wrote:
> Heikki Linnakangas <hlinnakangas(at)vmware(dot)com> writes:
> > On 28.10.2013 21:32, Andres Freund wrote:
> >> I think there are quite some algorithms relying on 16byte CAS, that's
> >> why I was thinking about it at all. I think it's easier to add support
> >> for it in the easier trawl through the compilers, but I won't argue much
> >> for it otherwise for now.
>
> > Many algorithms require a 2*(pointer width) CAS instruction. On 64-bit
> > platforms that's 16 bytes, but on 32-bit platforms an 8 byte version
> > will suffice.
>
> You're both just handwaving. How many is "many", and which ones might
> we actually have enough use for to justify dealing with such a dependency?
> I don't think we should buy into this without some pretty concrete
> justification.

Well, I don't think either of us is suggesting to make it required. But
it's going to be painful to go through the list of compilers repeatedly
instead of just adding all operations at one. I am willing to do that
for several compilers once, but I don't want to do it in each and every
feature submission using another atomic op.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Andres Freund <andres(at)2ndquadrant(dot)com> writes:
> On 2013-10-28 16:06:47 -0400, Tom Lane wrote:
>> You're both just handwaving. How many is "many", and which ones might
>> we actually have enough use for to justify dealing with such a dependency?
>> I don't think we should buy into this without some pretty concrete
>> justification.

> Well, I don't think either of us is suggesting to make it required. But
> it's going to be painful to go through the list of compilers repeatedly
> instead of just adding all operations at one. I am willing to do that
> for several compilers once, but I don't want to do it in each and every
> feature submission using another atomic op.

Basically I'm arguing that that choice is backwards. We should decide
first what the list of supported atomics is going to be, and each and
every element of that list has to have a convincing concrete argument
why we need to support it. Not "we might want this someday". Because
when someday comes, that's when we'd be paying the price of finding out
which platforms actually support the primitive correctly and with what
performance. Or if someday never comes, we're not ahead either.

Or if you like: no matter what you do, the first feature submission
that makes use of a given atomic op is going to suffer pain. I don't
want to still be suffering that pain two or three years out. The shorter
the list of allowed atomic ops, the sooner we'll be done with debugging
them.

regards, tom lane

On 2013-10-28 16:29:35 -0400, Tom Lane wrote:
> Andres Freund <andres(at)2ndquadrant(dot)com> writes:
> > On 2013-10-28 16:06:47 -0400, Tom Lane wrote:
> >> You're both just handwaving. How many is "many", and which ones might
> >> we actually have enough use for to justify dealing with such a dependency?
> >> I don't think we should buy into this without some pretty concrete
> >> justification.
>
> > Well, I don't think either of us is suggesting to make it required. But
> > it's going to be painful to go through the list of compilers repeatedly
> > instead of just adding all operations at one. I am willing to do that
> > for several compilers once, but I don't want to do it in each and every
> > feature submission using another atomic op.
>
> Basically I'm arguing that that choice is backwards. We should decide
> first what the list of supported atomics is going to be, and each and
> every element of that list has to have a convincing concrete argument
> why we need to support it.

The list I have previously suggested was:

* pg_atomic_load_u32(uint32 *)
* uint32 pg_atomic_store_u32(uint32 *)

To be able to write code without spreading volatiles all over while
making it very clear that that part of the code is worthy of attention.

* uint32 pg_atomic_exchange_u32(uint32 *ptr, uint32 val)
* bool pg_atomic_compare_exchange_u32(uint32 *ptr, uint32 *expected, uint32 newval)

Used in most lockfree algorithms, can be used to provide fallbacks for
when any of the other 32bit operations is not implemented for a platform
(so it's easier to bring up a platform).
E.g. used in in the wait-free LW_SHARED patch.

* uint32 pg_atomic_fetch_add_u32(uint32 *ptr, uint32 add)

Plain math.
E.g. used in in the wait-free LW_SHARED patch.

* uint32 pg_atomic_fetch_and_u32(uint32 *ptr, uint32 add)
* uint32 pg_atomic_fetch_or_u32(uint32 *ptr, uint32 add)

Useful for (un-)setting flags atomically. Needed for (my approach to)
spinlock-less Pin/UnpinBuffer.

* u64 variants of the above

lockfree list manipulation need at least pointer width operations of at
least compare_exchange().

I *personally* don't have a case for 8byte math yet, but I am pretty
sure parallel sort might be interested in it.

* bool pg_atomic_test_set(void *ptr)
* void pg_atomic_clear(void *ptr)

Can be used as the implementation for spinlocks based on compiler
intrinsics if no native implementation is existing. Makes it easier to
bring up new platforms.

Wrappers around the above:
* uint32 pg_atomic_fetch_sub_u32(uint32 *ptr, uint32 add)
Generic wrapper that imo makes the code easier to read. No
per-platform/compiler overhead.

* pg_atomic_add_until_u32(uint32 *ptr, uint32 val, uint32 limit)
Useful for managing refcounts like pin counts.

* pg_atomic_(add|sub|and|or)_fetch_u32()
Generic wrappers for more legible code. No
per-platform/compiler overhead.

* pg_atomic_compare_and_swap_128()

Many algorithms are faster (e.g. some lockless hashtables, which'd be
great for the buffer mapping) when a double-pointer-width CAS is
available, but also work with an pointer-width CAS in a less efficient
manner.

> Or if you like: no matter what you do, the first feature submission
> that makes use of a given atomic op is going to suffer pain. I don't
> want to still be suffering that pain two or three years out. The shorter
> the list of allowed atomic ops, the sooner we'll be done with debugging
> them.

Yea. As, partially, even evidenced by this discussion ;).

Which would you like to see go?

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Hi,

(Coming back to this now)

On 2013-10-28 21:55:22 +0100, Andres Freund wrote:
> The list I have previously suggested was:
>
> * pg_atomic_load_u32(uint32 *)
> * uint32 pg_atomic_store_u32(uint32 *)
>
> To be able to write code without spreading volatiles all over while
> making it very clear that that part of the code is worthy of attention.
>
> * uint32 pg_atomic_exchange_u32(uint32 *ptr, uint32 val)
> * bool pg_atomic_compare_exchange_u32(uint32 *ptr, uint32 *expected, uint32 newval)

So what I've previously proposed did use plain types for the
to-be-manipulated atomic integers. I am not sure about that anymore
though, C11 includes support for atomic operations, but it assumes that
the to-be-manipulated variable is of a special "atomic" type. While I am
not propose that we try to emulate C11's API completely (basically
impossible as it uses type agnostic functions, it also exposes too
much), it seems to make sense to allow PG's atomics to be implemented by
C11's.

The API is described at: http://en.cppreference.com/w/c/atomic

The fundamental difference to what I've suggested so far is that the
atomic variable isn't a plain integer/type but a distinct datatype that
can *only* be manipulated via the atomic operators. That has the nice
property that it cannot be accidentally manipulated via plain operators.

E.g. it wouldn't be
uint32 pg_atomic_fetch_add_u32(uint32 *ptr, uint32 add_);
but
uint32 pg_atomic_fetch_add_u32(pg_atomic_uint32 *ptr, uint32 add_);

where, for now, atomic_uint32 is something like:
typedef struct pg_atomic_uint32
{
volatile uint32 value;
} pg_atomic_uint32;
a future C11 implementation would just typedef C11's respective atomic
type to pg_atomic_uint32.

Comments?

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Tue, Nov 5, 2013 at 10:51 AM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> Hi,
>
> (Coming back to this now)
>
> On 2013-10-28 21:55:22 +0100, Andres Freund wrote:
>> The list I have previously suggested was:
>>
>> * pg_atomic_load_u32(uint32 *)
>> * uint32 pg_atomic_store_u32(uint32 *)
>>
>> To be able to write code without spreading volatiles all over while
>> making it very clear that that part of the code is worthy of attention.
>>
>> * uint32 pg_atomic_exchange_u32(uint32 *ptr, uint32 val)
>> * bool pg_atomic_compare_exchange_u32(uint32 *ptr, uint32 *expected, uint32 newval)
>
> So what I've previously proposed did use plain types for the
> to-be-manipulated atomic integers. I am not sure about that anymore
> though, C11 includes support for atomic operations, but it assumes that
> the to-be-manipulated variable is of a special "atomic" type. While I am
> not propose that we try to emulate C11's API completely (basically
> impossible as it uses type agnostic functions, it also exposes too
> much), it seems to make sense to allow PG's atomics to be implemented by
> C11's.
>
> The API is described at: http://en.cppreference.com/w/c/atomic
>
> The fundamental difference to what I've suggested so far is that the
> atomic variable isn't a plain integer/type but a distinct datatype that
> can *only* be manipulated via the atomic operators. That has the nice
> property that it cannot be accidentally manipulated via plain operators.
>
> E.g. it wouldn't be
> uint32 pg_atomic_fetch_add_u32(uint32 *ptr, uint32 add_);
> but
> uint32 pg_atomic_fetch_add_u32(pg_atomic_uint32 *ptr, uint32 add_);
>
> where, for now, atomic_uint32 is something like:
> typedef struct pg_atomic_uint32
> {
> volatile uint32 value;
> } pg_atomic_uint32;
> a future C11 implementation would just typedef C11's respective atomic
> type to pg_atomic_uint32.
>
> Comments?

Sadly, I don't have a clear feeling for how well or poorly that's
going to work out.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, Nov 5, 2013 at 5:51 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> So what I've previously proposed did use plain types for the
> to-be-manipulated atomic integers. I am not sure about that anymore
> though, C11 includes support for atomic operations, but it assumes that
> the to-be-manipulated variable is of a special "atomic" type. While I am
> not propose that we try to emulate C11's API completely (basically
> impossible as it uses type agnostic functions, it also exposes too
> much), it seems to make sense to allow PG's atomics to be implemented by
> C11's.
>
> The API is described at: http://en.cppreference.com/w/c/atomic
>
> The fundamental difference to what I've suggested so far is that the
> atomic variable isn't a plain integer/type but a distinct datatype that
> can *only* be manipulated via the atomic operators. That has the nice
> property that it cannot be accidentally manipulated via plain operators.
>
> E.g. it wouldn't be
> uint32 pg_atomic_fetch_add_u32(uint32 *ptr, uint32 add_);
> but
> uint32 pg_atomic_fetch_add_u32(pg_atomic_uint32 *ptr, uint32 add_);
>
> where, for now, atomic_uint32 is something like:
> typedef struct pg_atomic_uint32
> {
> volatile uint32 value;
> } pg_atomic_uint32;
> a future C11 implementation would just typedef C11's respective atomic
> type to pg_atomic_uint32.
>
> Comments?

C11 atomics need to be initialized through atomic_init(), so a simple
typedef will not be correct here. Also, C11 atomics are designed to
have the compiler take care of memory barriers - so they might not
always be a perfect match to our API's, or any API implementable
without compiler support.

However I'm mildly supportive on having a separate type for variables
accessed by atomics. It can result in some unnecessary code churn, but
in general if an atomic access to a variable is added, then all other
accesses to it need to be audited for memory barriers, even if they
were previously correctly synchronized by a lock.

I guess the best approach for deciding would be to try to convert a
couple of the existing unlocked accesses to the API and see what the
patch looks like.

Regards,
Ants Aasma
--
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de

On 2013-11-06 16:48:17 +0200, Ants Aasma wrote:
> C11 atomics need to be initialized through atomic_init(), so a simple
> typedef will not be correct here. Also, C11 atomics are designed to
> have the compiler take care of memory barriers - so they might not
> always be a perfect match to our API's, or any API implementable
> without compiler support.

Yea, I think we'll always need to have our layer above C11 atomics, but
it still will be useful to allow them to be used to implement our
atomics.

FWIW, I find the requirement for atomic_init() really, really
annoying. Not that that will change anything ;)

> However I'm mildly supportive on having a separate type for variables
> accessed by atomics. It can result in some unnecessary code churn, but
> in general if an atomic access to a variable is added, then all other
> accesses to it need to be audited for memory barriers, even if they
> were previously correctly synchronized by a lock.

Ok, that's what I am writing right now.

> I guess the best approach for deciding would be to try to convert a
> couple of the existing unlocked accesses to the API and see what the
> patch looks like.

I don't think there really exist any interesting ones? I am using my
lwlock reimplementation as a testbed so far.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Wed, Nov 6, 2013 at 4:54 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> FWIW, I find the requirement for atomic_init() really, really
> annoying. Not that that will change anything ;)

Me too, but I guess this allows them to emulate atomics on platforms
that don't have native support. Whether that is a good idea is a
separate question.

>> However I'm mildly supportive on having a separate type for variables
>> accessed by atomics. It can result in some unnecessary code churn, but
>> in general if an atomic access to a variable is added, then all other
>> accesses to it need to be audited for memory barriers, even if they
>> were previously correctly synchronized by a lock.
>
> Ok, that's what I am writing right now.
>
>> I guess the best approach for deciding would be to try to convert a
>> couple of the existing unlocked accesses to the API and see what the
>> patch looks like.
>
> I don't think there really exist any interesting ones? I am using my
> lwlock reimplementation as a testbed so far.

BufferDesc management in src/backend/storage/buffer/bufmgr.c.
The seqlock like thing used to provide consistent reads from
PgBackendStatus src/backend/postmaster/pgstat.c (this code looks like
it's broken on weakly ordered machines)
The unlocked reads that are done from various procarray variables.
The XLogCtl accesses in xlog.c.

IMO the volatile keyword should be confined to the code actually
implementing atomics, locking. The "use volatile pointer to prevent
code rearrangement" comment is evil. If there are data races in the
code, they need comments pointing this out and probably memory
barriers too. If there are no data races, then the volatile
declaration is useless and a pessimization. Currently it's more of a
catch all "here be dragons" declaration for data structures.

Regards,
Ants Aasma
--
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de

On 2013-11-06 08:15:59 -0500, Robert Haas wrote:
> > The API is described at: http://en.cppreference.com/w/c/atomic
> >
> > The fundamental difference to what I've suggested so far is that the
> > atomic variable isn't a plain integer/type but a distinct datatype that
> > can *only* be manipulated via the atomic operators. That has the nice
> > property that it cannot be accidentally manipulated via plain operators.
> >
> > E.g. it wouldn't be
> > uint32 pg_atomic_fetch_add_u32(uint32 *ptr, uint32 add_);
> > but
> > uint32 pg_atomic_fetch_add_u32(pg_atomic_uint32 *ptr, uint32 add_);
> >
> > where, for now, atomic_uint32 is something like:
> > typedef struct pg_atomic_uint32
> > {
> > volatile uint32 value;
> > } pg_atomic_uint32;
> > a future C11 implementation would just typedef C11's respective atomic
> > type to pg_atomic_uint32.
> >
> > Comments?
>
> Sadly, I don't have a clear feeling for how well or poorly that's
> going to work out.

I've implemented it that way and it imo looks sensible. I dislike the
pg_atomic_init_(flag|u32|u64) calls that are forced on us by wanting to
be compatible with C11, but I think that doesn't end up being too bad.

So, attached is a very first draft of an atomics implementation. There's
lots to be done, but this is how I think it should roughly look like and
what things we should implement in the beginning.
The API should be understandable from looking at
src/include/storage/atomics.h

I haven't tested the IBM xlc, HPUX IA64 acc, Sunpro fallback at all, but
the important part is that those provide the necessary tools to
implement everything. Also, even the gcc implementation falls back to
compare_and_swap() based implementations for the operations, but that
shouldn't matter for now. I haven't looked for other compilers yet.

Questions:
* Fundamental issues with the API?
* should we split of compiler/arch specific parts of into include/ports
or such? -0.5 from me.
* should we add src/include/storage/atomics subdirectory? +0.5 from me.
* Do we really want to continue to cater to compilers not supporting
PG_USE_INLINE? I've tried to add support for them, but it does make
things considerably more #ifdef-y.
Afaik it's only HPUX's acc that has problems, and it seems to work but
generate warnings, so maybe that's ok?
* Which additional compilers do we want to support? icc (might be gcc
compatible)?

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 2013-11-06 17:47:45 +0200, Ants Aasma wrote:
> On Wed, Nov 6, 2013 at 4:54 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> > FWIW, I find the requirement for atomic_init() really, really
> > annoying. Not that that will change anything ;)
>
> Me too, but I guess this allows them to emulate atomics on platforms
> that don't have native support. Whether that is a good idea is a
> separate question.

Since static initialization is supported that would require quite some
dirty hacks, but well, we're talking about compiler makers ;)

> > I don't think there really exist any interesting ones? I am using my
> > lwlock reimplementation as a testbed so far.
>
> BufferDesc management in src/backend/storage/buffer/bufmgr.c.
> The unlocked reads that are done from various procarray variables.
> The XLogCtl accesses in xlog.c.

Those are actually only modified under spinlocks afair, so there isn't
too much interesting happening. But yes, it'd be better if we used more
explicit means to manipulate/query them.

> The seqlock like thing used to provide consistent reads from
> PgBackendStatus src/backend/postmaster/pgstat.c (this code looks like
> it's broken on weakly ordered machines)

Whoa. Never noticed that bit. The consequences of races are quite low,
but still...

> IMO the volatile keyword should be confined to the code actually
> implementing atomics, locking. The "use volatile pointer to prevent
> code rearrangement" comment is evil. If there are data races in the
> code, they need comments pointing this out and probably memory
> barriers too. If there are no data races, then the volatile
> declaration is useless and a pessimization. Currently it's more of a
> catch all "here be dragons" declaration for data structures.

Agreed. But I don't think we can replace them all at once. Or well, I
won't ;)

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 2013-11-06 17:24:57 +0100, Andres Freund wrote:
> Questions:
> * Do we really want to continue to cater to compilers not supporting
> PG_USE_INLINE? I've tried to add support for them, but it does make
> things considerably more #ifdef-y.
> Afaik it's only HPUX's acc that has problems, and it seems to work but
> generate warnings, so maybe that's ok?

Maybe we can simply silence that specific warning for HPUX when using
aC++ like in the attached patch? It's not like somebody really looks at
those anyway given how bleaty it is.
Or we can just generally remove the "quiet inline" check.

I haven't tested the patch since I don't have a HPUX machine but that's the option to use according to
http://h21007.www2.hp.com/portal/download/files/unprot/aCxx/Online_Help/options.htm#opt+Wargs

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Hi,

Instead of de-supporting platforms that don't have CAS support or
providing parallel implementations we could relatively easily build a
spinlock based fallback using the already existing requirement for
tas().
Something like an array of 16 spinlocks, indexed by a more advanced
version of ((char *)(&atomics) >> sizeof(char *)) % 16. The platforms
that would fallback aren't that likely to be used under heavy
concurrency, so the price for that shouldn't be too high.

The only real problem with that would be that we'd need to remove the
spinnlock fallback for barriers, but that seems to be pretty much
disliked.

Thoughts?

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Mon, Nov 11, 2013 at 1:57 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> Instead of de-supporting platforms that don't have CAS support or
> providing parallel implementations we could relatively easily build a
> spinlock based fallback using the already existing requirement for
> tas().
> Something like an array of 16 spinlocks, indexed by a more advanced
> version of ((char *)(&atomics) >> sizeof(char *)) % 16. The platforms
> that would fallback aren't that likely to be used under heavy
> concurrency, so the price for that shouldn't be too high.
>
> The only real problem with that would be that we'd need to remove the
> spinnlock fallback for barriers, but that seems to be pretty much
> disliked.

I think this is worth considering. I'm not too clear what to do about
the barriers problem, though. I feel like we've dug ourselves into a
bit of a hole, there, and I'm not sure I understand the issues well
enough to dig us back out of it.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 2013-11-12 13:21:30 -0500, Robert Haas wrote:
> > The only real problem with that would be that we'd need to remove the
> > spinnlock fallback for barriers, but that seems to be pretty much
> > disliked.
>
> I think this is worth considering.

Ok, cool. The prototype patch I have for that is pretty small, so it doesn't
look too bad.

What currently scares me is the amount of code I have to write that I can't
test... I really can't see me being able to provide a patch that doesn't
require some buildfarm cycles to really work on all platforms.

> I'm not too clear what to do about
> the barriers problem, though. I feel like we've dug ourselves into a
> bit of a hole, there, and I'm not sure I understand the issues well
> enough to dig us back out of it.

I think any platform where we aren't able to provide a proper compiler/memory
barrier will also have broken spinlock relase semantics (as in missing release
memory barrier). So arguably removing the fallback is a good idea anyway.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services