Project about Atomic Operations

[yangwei weiyang]

Hi all:
The project of Atomic Operations seems a very good candidate for
GSOC project. After some investigations i think its mainly goal is to
define a set of atomic operation API and then implement those APIs. As
we know an atomic operation is an operation that will always be
executed without any other process being able to read or change state
that is read or changed during the operation. From the software
perspective a few of the synchronization primitives have
implementations or examples of atomic operation like semaphores,
mutexes , spinlocks and so on. And most of these synchronization
primitives have been supported on the RTEMS. From the hardware
perspective atomic operations mean a single instruction which will
guarantee atomic access. And also the method of atomic operations is
different for single core systems and multicore systems. In the single
core systems we can just disable interrupt simplely to guarentee the
atomic access, but in the multicore systems it does not work. So in
there i think this project is mainly target at multicore support on
RTEMS, right?
About the ConcurrencyKit it provide lots of atomic operations, but
it does not natively support RTEMS. It must be ported to RTEMS. All
the operations supported by ConcurrencyKit should be ported to RTEMS?
i think we can first design the needed atomic operation API and then
implement API referring the ConcurrencyKit. And using the test case of
ConcurrencyKit to test them. What is your opinions about this project,
feel free to give your opinion.

--
Wei Yang
Best Regards

wei.a.yang at gmail.com
_______________________________________________
rtems-users mailing list
rtems...@rtems.org
http://www.rtems.org/mailman/listinfo/rtems-users

[Gedare Bloom]

On Fri, Mar 16, 2012 at 7:45 AM, yangwei weiyang <wei.a...@gmail.com> wrote:
> Hi all:
>    The project of Atomic Operations seems a very good candidate for
> GSOC project. After some investigations i think its mainly goal is to
> define a set of atomic operation API and then implement those APIs. As
> we know an atomic operation is an operation that will always be
> executed without any other process being able to read or change state
> that is read or changed during the operation. From the software
> perspective a few of the synchronization primitives have
> implementations or examples of atomic operation like semaphores,
> mutexes , spinlocks and so on. And most of these synchronization
> primitives have been supported on the RTEMS. From the hardware
> perspective atomic operations mean a single instruction which will
> guarantee atomic access. And also the method of atomic operations is
> different for single core systems and multicore systems. In the single
> core systems we can just disable interrupt simplely to guarentee the
> atomic access, but in the multicore systems it does not work. So in
> there i think this project is mainly target at multicore support on
> RTEMS, right?

Yes, you have the right idea.

>    About the ConcurrencyKit it provide lots of atomic operations, but
> it does not natively support RTEMS. It must be ported to RTEMS. All
> the operations supported by ConcurrencyKit should be ported to RTEMS?

Well, the ck must be tested on a target architecture that RTEMS works
with (x86), and then we should attempt to integrate ck with RTEMS so
that the atomic operations and other parts of ck can be used. One
trick about this project is that we will want the atomic /
synchronization primitives available in the score, so the final
integration of ck would have to be treated with care.

FreeBSD and ConcurrencyKit both provide atomic operations. The FreeBSD
Atomic implementation may cover more RTEMS targets, whereas the
ConcurrencyKit may only have support for one RTEMS target, but ck
provides a number of interesting and useful algorithms that build on
the atomic operations. An advantage of the ck is that it is
self-contained which might make it easier to maintain.

> i think we can first design the needed atomic operation API and then
> implement API referring the ConcurrencyKit. And using the test case of
> ConcurrencyKit to test them. What is your opinions about this project,
> feel free to give your opinion.
>

Yes it might make sense to define an RTEMS-specific atomic operations
API that itself refers to atomic operations provided by another
package such as the ConcurrenyKit or a port of the FreeBSD atomic_xxx
functions.

[Yang Wei]

在 2012-3-17，5:57，Gedare Bloom <ged...@rtems.org> 写道：

> On Fri, Mar 16, 2012 at 7:45 AM, yangwei weiyang <wei.a...@gmail.com> wrote:
>> Hi all:
>> The project of Atomic Operations seems a very good candidate for
>> GSOC project. After some investigations i think its mainly goal is to
>> define a set of atomic operation API and then implement those APIs. As
>> we know an atomic operation is an operation that will always be
>> executed without any other process being able to read or change state
>> that is read or changed during the operation. From the software
>> perspective a few of the synchronization primitives have
>> implementations or examples of atomic operation like semaphores,
>> mutexes , spinlocks and so on. And most of these synchronization
>> primitives have been supported on the RTEMS. From the hardware
>> perspective atomic operations mean a single instruction which will
>> guarantee atomic access. And also the method of atomic operations is
>> different for single core systems and multicore systems. In the single
>> core systems we can just disable interrupt simplely to guarentee the
>> atomic access, but in the multicore systems it does not work. So in
>> there i think this project is mainly target at multicore support on
>> RTEMS, right?
> Yes, you have the right idea.

OK, that means I understand what problem this project will solve and under what environment. It is mainly for the multicore systems in which the atomic operations are mostly relied hardware architecture instruction support. So first we should select a architecture like x86 or ppc which support the atomic operation instruction. Then we should try to integrate the ck into the RTEMS (as gedare said the atomic primitives should be in the score, so we should discuss the detail of this step.). At the same time we should also design and define the atomic primitives API used by RTEMS, this step we can refer the FreeBSD and NetBSD (NetBSD has good support for SMP, so we can spend time investigating its API definition and design). I will write a proposal for this project. f you have any comment, please feel free to contract me.

[Gedare Bloom]

Hi Wei,

You seem to have a fair grasp on the basics of this project. I see a
few basic phases in this project:
1) Design support for atomic operations usable by RTEMS score. This
involves creating an RTEMS internal API for atomic operations that is
not CPU-specific. Because of the varied hw requirements something like
the cache manager might be a good candidate to copy from, for example
something like an Atomic Operations Manager that has a similar
software architecture as the Cache Manager might satisfy our needs.
2) Implement default stubs (nops) for the API.
3) Write simple test code that uses the API (stubs). Tests should run
on all RTEMS targets.
4) Submit code and documentation.
5) Implement the atomic operations for a particular CPU. Document
procedures for implementation.
6) Test.
7) Submit.

With step 5 you might be able to borrow code from FreeBSD or
ConcurrencyKit or some other appropriately-licensed software. If you
keep the ConcurrencyKit/FreeBSD atomic operations implemif you keep
the ConcurrencyKit/FreeBSD atomic operations implementations in mind
as you design the Atomic Operations Manager this step may be
straightforward.entations in mind as you design the Atomic Operations
Manager this step may be straightforward. Once you complete through
step 7 you can also consider how to integrate the full ConcurrencyKit
with the RTEMS Atomic Operations Manager to provide some useful
synchronization tools that use the atomic operations.

-Gedare

[Sebastian Huber]

Hi,

atomic operations are now supported by the recent C and C++ standard. See

http://en.wikipedia.org/wiki/C11_%28C_standard_revision%29
http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/

Why don't we simply use them?

--
Sebastian Huber, embedded brains GmbH

Address : Obere Lagerstr. 30, D-82178 Puchheim, Germany
Phone : +49 89 18 90 80 79-6
Fax : +49 89 18 90 80 79-9
E-Mail : sebasti...@embedded-brains.de
PGP : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

[yangwei weiyang]

Hi Huber:
The atomic operations supported by c and c++ standard is built in
the compiler, like
GCC has some build-in atomic operations functions. you can see
http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html.
But Not all operations are supported by all target processors and
it is designed as a
standard library not for a operation system. So in my opinion we can
refer its implementation
but can use them directly.

Wenjie
Best Regards

2012/3/26 Sebastian Huber <sebasti...@embedded-brains.de>:

--
Wei Yang
Best Regards

wei.a.yang at gmail.com

_______________________________________________

[yangwei weiyang]

2012/3/26 yangwei weiyang <wei.a...@gmail.com>:

> Hi Huber:
>    The atomic operations supported by c and c++ standard is built in
> the compiler, like
> GCC has some build-in atomic operations functions. you can see
>    http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html.
>    But Not all operations are supported by all target processors and
> it is designed as a
> standard library not for a operation system. So in my opinion we can
> refer its implementation
> but can use them directly.

Correct but can not use them directly

[Sebastian Huber]

Hello Wenjie,

I mean not some GCC specific builtins. I mean the C 2011 standard.

[Yang Wei]

Hi Huber,
The implementation of C 2011 standard should also be part of compiler,right? I am not really familiar with its implementation. And the C 2011 support all architecture atomic primitive?

[Sebastian Huber]

On 03/26/2012 04:43 PM, Yang Wei wrote:
> Hi Huber,
> The implementation of C 2011 standard should also be part of compiler,right?

Yes, but the compiler might need help from the operating system.

> I am not really familiar with its implementation. And the C 2011 support all architecture atomic primitive?

The atomic support is optional, but I guess GCC will support it on all main
architectures. Please also have a look in the standard:

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

[Yang Wei]

在 2012-3-26，22:59，Sebastian Huber <sebasti...@embedded-brains.de> 写道：

> On 03/26/2012 04:43 PM, Yang Wei wrote:
>> Hi Huber,
>> The implementation of C 2011 standard should also be part of compiler,right?
>
> Yes, but the compiler might need help from the operating system.

That means the implementation is corresponding to the OS type. With regard with Rtems its implementation should be placed in newlib. But this means the synchronization primitives which is built on the atomic primitives will rely the newlib. I think it is not suitable. Other OS like Linux, FreeBSD, NetBSD all implement its own atomic primitives rather than relying the standard library.

>
>> I am not really familiar with its implementation. And the C 2011 support all architecture atomic primitive?
>
> The atomic support is optional, but I guess GCC will support it on all main architectures. Please also have a look in the standard:
>
> http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
>

Thank you for your reference, huber. It's a very good material. I think we can refer its API definition for atomic primitive, but it is not necessary to implement all its definitions.

[Gedare Bloom]

On Mon, Mar 26, 2012 at 10:59 AM, Sebastian Huber
<sebasti...@embedded-brains.de> wrote:
> On 03/26/2012 04:43 PM, Yang Wei wrote:
>>
>> Hi Huber,
>>     The implementation of C 2011 standard should also be part of
>> compiler,right?
>
>
> Yes, but the compiler might need help from the operating system.
>
>
>> I am not really familiar with its implementation. And the C 2011 support
>> all architecture atomic primitive?
>
>
> The atomic support is optional, but I guess GCC will support it on all main
> architectures.  Please also have a look in the standard:
>
> http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
>

Maybe we should design our API to be at least a superset of what the
compiler must provide for C11 compliance. Target architectures /
compilers that do not support the C11 atomics will need the atomic
operations implemented in assembly language. For targets that are
supported the API will thinly wrap the C-language atomic features and
can share code.

-Gedare

[Sebastian Huber]

On 03/26/2012 05:31 PM, Yang Wei wrote:
> Other OS like Linux, FreeBSD, NetBSD all implement its own atomic primitives rather than relying the standard library.

Other OS were a bit faster than RTEMS. The C standard has this atomic support
since 2011.

[Sebastian Huber]

On 03/26/2012 05:32 PM, Gedare Bloom wrote:
> Maybe we should design our API to be at least a superset of what the
> compiler must provide for C11 compliance. Target architectures /
> compilers that do not support the C11 atomics will need the atomic
> operations implemented in assembly language. For targets that are
> supported the API will thinly wrap the C-language atomic features and
> can share code.

This is reinventing the wheel. I don't see why we need the 100th atomic library.

[Yang Wei]

在 2012-3-26，23:45，Sebastian Huber <sebasti...@embedded-brains.de> 写道：

> On 03/26/2012 05:32 PM, Gedare Bloom wrote:
>> Maybe we should design our API to be at least a superset of what the
>> compiler must provide for C11 compliance. Target architectures /
>> compilers that do not support the C11 atomics will need the atomic
>> operations implemented in assembly language. For targets that are
>> supported the API will thinly wrap the C-language atomic features and
>> can share code.
>
> This is reinventing the wheel. I don't see why we need the 100th atomic library.
>

The C11 support for atomic primitive since 2011. Whether the compiler like gcc has support all the atomic primitives and for all architectures? And Rtems does not use standard library provided by compiler, so we still support all the atomic primitives on the newlib. There are also lots of work to do if we support all the atomic primitives defined by C11 standard

[Thomas Doerfler]

Hi,

I am a bit confused about this discussion. I havn't looked into the
RTEMS/GSOC project related to atomic support, but I agree with Sebastian
that it doesn't make sense to implement an RTEMS-specific atomic API
that would replace the C11 standard API.

What might make sense is to

- develop an API for RTEMS synchronization/kernel services which is ON
TOP of the C11 atomic standard

- develp support routines (maybe in newlib, maybe in RTEMS) that
implements a synchronization function.

Maybe for the discussion the following wiki page might help:

http://gcc.gnu.org/wiki/Atomic

It lists the architectures that GCC directly supports for atomics. All
other architectures (including ARM, M68K) require library support to get
atomic operations to work properly. So at least _this_ would be work
that requires doing.

wkr,

Thomas.

--
--------------------------------------------
Embedded Brains GmbH
Thomas Doerfler Obere Lagerstr. 30
D-82178 Puchheim Germany
email: Thomas....@embedded-brains.de
Phone: +49-89-18908079-2
Fax: +49-89-18908079-9

[Joel Sherrill]

On 03/26/2012 11:00 AM, Yang Wei wrote:

在 2012-3-26，23:45，Sebastian Huber <sebasti...@embedded-brains.de> 写道：

On 03/26/2012 05:32 PM, Gedare Bloom wrote:

Maybe we should design our API to be at least a superset of what the
compiler must provide for C11 compliance. Target architectures /
compilers that do not support the C11 atomics will need the atomic
operations implemented in assembly language. For targets that are
supported the API will thinly wrap the C-language atomic features and
can share code.

This is reinventing the wheel.  I don't see why we need the 100th atomic library.

The C11 support for atomic primitive since 2011. Whether the compiler like gcc has support all the atomic primitives and for all architectures? And Rtems does not use standard library provided by compiler, so we still support all the atomic primitives on the newlib. There are also lots of work to do if we support all the atomic primitives defined by C11 standard

GCC 4.7 is making progress. There is the P99 collection:

http://p99.gforge.inria.fr/p99-html/group__atomic.html

and this:

http://svnweb.freebsd.org/base/head/include/stdatomic.h?view=markup

which claims to support three different types of compilers:

+ Clang 3.1's atomic intrinsics (not released yet)
+ GCC 4.7's atomic intrinsics
+ GCC's __sync interface

I don't know if clang 3.1 has been released but gcc 4.7 has been released
since the description of stdatomic.h was written.

FWIW there is also the small set of TAS, CMP/SWP type operations
used in the shmdr in RTEMS. Updating those would be an appropriate
part of this task.

But in general, my concern for all of this is what are the use cases
from RTEMS perspective.

+ Is it only for SMP or AMP use?

+ MP as in shared memory MP found in RTEMS for years. Kernel locks in [AS]MP?

+ Is there a uniprocessor use case?

Off the top of my head, I have trouble seeing how stdatomic.h
wouldn't be a good starting spot for RTEMS for kernel locking.

If we are generalizing all SMP/CPU interface points, then the
idea of current CPU core is another thing to consider.

-- 
Sebastian Huber, embedded brains GmbH

Address : Obere Lagerstr. 30, D-82178 Puchheim, Germany
Phone   : +49 89 18 90 80 79-6
Fax     : +49 89 18 90 80 79-9
E-Mail  : sebasti...@embedded-brains.de
PGP     : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

_______________________________________________
rtems-users mailing list
rtems...@rtems.org
http://www.rtems.org/mailman/listinfo/rtems-users

-- 
Joel Sherrill, Ph.D.             Director of Research&  Development
joel.s...@OARcorp.com        On-Line Applications Research
Ask me about RTEMS: a free RTOS  Huntsville AL 35805
    Support Available             (256) 722-9985

[Joel Sherrill]

On 03/26/2012 11:19 AM, Thomas Doerfler wrote:
> Hi,
>
> I am a bit confused about this discussion. I havn't looked into the
> RTEMS/GSOC project related to atomic support, but I agree with Sebastian
> that it doesn't make sense to implement an RTEMS-specific atomic API
> that would replace the C11 standard API.
>
> What might make sense is to
>
> - develop an API for RTEMS synchronization/kernel services which is ON
> TOP of the C11 atomic standard
>
> - develp support routines (maybe in newlib, maybe in RTEMS) that
> implements a synchronization function.

I think they are discussed in terms of being libc methods but
in reality are provided by the compiler. GCC 4.7 has initial
support.

> Maybe for the discussion the following wiki page might help:
>
> http://gcc.gnu.org/wiki/Atomic
>
> It lists the architectures that GCC directly supports for atomics. All
> other architectures (including ARM, M68K) require library support to get
> atomic operations to work properly. So at least _this_ would be work
> that requires doing.

Right any atomic implementation done in this project should
be fed upstream to gcc and/or clang. In the case of
gcc, that would require an assignment. I can help with that.
We have had quick turn around on assignments for GSOC students.

This in addition to wrapping RTEMS primitives on top of gcc atomics
which gets us back to something like FreeBSD stdatomics.h. :)

--

Joel Sherrill, Ph.D. Director of Research& Development
joel.s...@OARcorp.com On-Line Applications Research
Ask me about RTEMS: a free RTOS Huntsville AL 35805
Support Available (256) 722-9985

[Sebastian Huber]

On 03/26/2012 06:19 PM, Thomas Doerfler wrote:
> Maybe for the discussion the following wiki page might help:
>
> http://gcc.gnu.org/wiki/Atomic
>
> It lists the architectures that GCC directly supports for atomics. All
> other architectures (including ARM, M68K) require library support to get

> atomic operations to work properly. So at least_this_ would be work
> that requires doing.

The situation on ARM is not yet stable. The main problem with ARM is that only
recent architecture revisions have proper SMP support. See also

http://gcc.gnu.org/ml/gcc/2012-03/msg00083.html

[Ralf Corsepius]

On 03/26/2012 06:19 PM, Thomas Doerfler wrote:

> Hi,
>
> I am a bit confused about this discussion. I havn't looked into the
> RTEMS/GSOC project related to atomic support, but I agree with Sebastian
> that it doesn't make sense to implement an RTEMS-specific atomic API
> that would replace the C11 standard API.

I agree in sofar as C11 could be a promise about an emerging, future
standard.

So far, IMO, C11 is too young to be considered stable and established
standard and to be utilized as foundation of works.

[Remember how long it took until comparable precessors (c89, c99) were
stable and well established. Their implementation timeframes were
measured in decades - I'd be surprised, if c11 would be different]

> What might make sense is to
>
> - develop an API for RTEMS synchronization/kernel services which is ON
> TOP of the C11 atomic standard

One option I see, would be to treat c11-atomics as optional and
conditional and to consider their API as API-template for RTEMS specific
atomics.

This would mean, if C11 should be adopted for RTEMS, I'd recomment
RTEMS to implement an RTEMS-specific wrapper layer, which optionally and
conditionally may utilize c11-atomics as one potential implementation
option underneath.

> - develp support routines (maybe in newlib, maybe in RTEMS) that
> implements a synchronization function.

On a wider scope, I think, one would have to analyse whether c11-atomics
actually meet RTEMS demands and ... whether lowlevel atomic operations
are actually necessary and/or useful, rsp. if some atomics aren't better
implemented on higher levels (e.g. using RTEMS score functions).

At least I would rather avoid any low level, RTEMS-specific (esp. ASM)
atomic operations, because such low level code in longer terms often
turns into a nightmare.

> Maybe for the discussion the following wiki page might help:
>
> http://gcc.gnu.org/wiki/Atomic
>
> It lists the architectures that GCC directly supports for atomics. All
> other architectures (including ARM, M68K) require library support to get
> atomic operations to work properly. So at least _this_ would be work
> that requires doing.

Well, IMO, The state Atomics in GCC currently is in speaks for itself.
It's an Herculanean effort, which not even the GCC folks are able to
implement on the broadness which would actually be required.

Ralf

[Yang Wei]

Yes, it is a little big turn around on assignments for students like me who has almost completed the proposal for this project. Now the period of submitting proposal is beginning, and there are only about ten days for me to complete the proposal. So in my opinion we must determine the direction and the objective of this project as soon as possible. Then I can detail the tasks according to the requirements and modify my proposal in time.

> This in addition to wrapping RTEMS primitives on top of gcc atomics
> which gets us back to something like FreeBSD stdatomics.h. :)

If we using the compiler built in atomic operations support, we can refer the implementation of FreeBSD.

[Yang Wei]

在 2012-3-27，15:27，Ralf Corsepius <ralf.co...@rtems.org> 写道：

On 03/26/2012 06:19 PM, Thomas Doerfler wrote:

Hi,

I am a bit confused about this discussion. I havn't looked into the

RTEMS/GSOC project related to atomic support, but I agree with Sebastian

that it doesn't make sense to implement an RTEMS-specific atomic API

that would replace the C11 standard API.

I agree in sofar as C11 could be a promise about an emerging, future standard.

So far, IMO, C11 is too young to be considered stable and established standard and to be utilized as foundation of works.

[Remember how long it took until comparable precessors (c89, c99) were stable and well established. Their implementation timeframes were measured in decades - I'd be surprised, if c11 would be different]

Really, we should make careful evaluation of the stability of C11 atomic support when it will be used by RTEMS.

What might make sense is to

- develop an API for RTEMS synchronization/kernel services which is ON

TOP of the C11 atomic standard

One option I see, would be to treat c11-atomics as optional and conditional and to consider their API as API-template for RTEMS specific atomics.

This would mean, if C11 should be adopted for RTEMS, I'd recomment RTEMS to implement an RTEMS-specific wrapper layer, which optionally and conditionally may utilize c11-atomics as one potential implementation option underneath.

Yes, I agree with ralf. Firstly we can refer the atomic API definition of C11 and design the compatible API on the RTEMS. And also we do not need implement all the API it supports. At least the atomic primitives on which the synchronization primitives is built should be provided.