SMP: ISR disable/enable vs. mutual exclustion

Wed Aug 28 14:31:02 UTC 2013

Hello All,

I want to express my two cents even that I cannot find time
to do more than chin-wag, sorry too many other project
required for university an company stay in a operation.

The containers basic API should be without locking.
You usually need something like atomic extract from one list
and insert to the other list. And you waste additional
locking in list remove/insert when you have to provide
lock to make operations sequence atomic.
There is usually good/natural place where lock belongs
in such cases. Or you do not want to use IRQ+spin-lock
there but whole sequence is protected by mutex (should be
with priority inheritance for each case).

This is how Linux kernel defines containers and data structures
too. Problem is that it is really very hard to switch
to unlocked containers when code in some places and sequences
depends on locking in containers.

On the other hand there are mechanism which can belong
to some containers variants or can require containers
implementation support. Linux is moving now from locking
to RCU (read-copy update)[*1] mechanism for heavily accessed
data where reads prevails and some short time work
with old copy is allowed or can be detected by other mechanism.
The interration over list requires use of barriers and single
next pointer access ins such case. So there is separate list next
function variant for this case.

So my suggestion is to define lists unprotected and use them
as such in new code. There can be protected variant for legacy
users but not for critical/core code.

I have same concerns with RTEMS red-black trees from beginning.
But I was not able to provide better code and was happy things
move forward.

As for red-black trees: I really like much Daniel Santos's
Generic Red-Black Trees API proposed for Linux kernel.
It is more demanding on compiler than my user pace/RTEMS
used uLUt AVL, but it has great API and new RTEMS releases
has not such problems to be compiled with very old toolchains.
RTEMS toolchains moves forward with versions.

So I suggest to look at that proposal even that it is not
used by Linux kernel yet

  http://thread.gmane.org/gmane.linux.kernel/1367138/focus=1367138

I think that wrappers code license would not be problem to
get from Daniel with RTEMS GPL exception. Base RB insert, balance
has to be taken from actual RTEMS or other license compatible
source.

Preparation of similar API for lists would not take much time
as well. It would be straightforward to follow same model.
He has done massive testing that proposal overhead is zero
for most of/all architectures when recent GCC is used.
It results in some instruction level overhead when older GCC
is used. Type safety has zero size tree node and root structures
overhead. Overhead of actual RTEMS RB tree is higher even
for unlocked version due to functions indirection.

[*1] RCU is available under GPL and LGPL licenses and IBM
pattents are pledged for such use. Use of RCU idea and even more
of code with RTEMS exception would require to ask RCU maintainer/
author Paul E. McKenney. On the other hand, RCU has usually
some memory overhead and its gain is critical for big
SMP machines with NUMA architecture. As I consider RTEMS
as more targetted to smaller systems and more deterministic
behavior, I think that RCU is not on the table for longer time there.

Thanks much to Sebastian for his huge amount of work
and best wishes to RTEMS and developers,

                 Pavel

On Wednesday 28 of August 2013 00:44:58 Chris Johns wrote:
> Sebastian Huber wrote:
> > On 2013-08-27 01:26, Chris Johns wrote:
> >> Sebastian Huber wrote:
> >>> On 2013-08-24 04:10, Chris Johns wrote:
> >>>>> Thus the normal extract operation is not available on SMP. An extract
> >>>>> variant which needs also the chain control as a parameter must be
> >>>>> used.
> >>>>
> >>>> I think a node may need a back pointer to the chain control that
> >>>> contains a
> >>>> lock. I suspect we cannot have a single score chain control structure
> >>>> for both
> >>>> protected and unprotected operations and support the current extract.
> >>>> I have
> >>>> not looked at all the uses of extract in the code so I do not know if
> >>>> the chain
> >>>> control is available and even it is I think the node should handle
> >>>> this.
> >>>
> >>> In order to use the back pointer you have to lock the chain, so this
> >>> cannot be used. You have to know on which chain the node is.
> >>
> >> Yes you are correct. Should the locking be something the user of the
> >> chains
> >> should manage ? The chains is starting to become more and more complex.
> >
> > On single processor configuration the locking is done by the chains (ISR
> > disable/enable) so I think there is no way out.
>
> The RTEMS chains has protected, unprotected and now explicit and I am
> starting to wonder if the API has become too complicated for users with
> too many choices. Some choices work with SMP other do not. We really
> should have one version that works in all cases however this means
> breaking the existing API. On the other hand anyone not using the
> explicit API will break when moving code to an SMP target and only finds
> out once they move or try. They may have made design choices without
> being aware of the differences and possible issues. The one related to
> this change is the need to have the chain control available when
> extracting a node. This is a big difference.
>
> I understand the migration and the need not to break an API however I am
> asking the question about the complexity of the API and if we should
> review what it is doing. With this change where you need the control
> chain to extract the node you have some data following the node and that
> could contain the lock and I suspect in a number of cases will contain a
> lock. I also wonder if the user of the chain can manage the locking
> better in some cases than letting the chain do it. The locking was fast
> before and now it is not as fast changing the dynamic.
>
> Extending the API makes sense now and from a kernel change point of view
> however I am not convinced of the long term benefit when all the current
> rapid change settles and is forgotten.
>
> > Please have a look at the patch here:
> >
> > https://www.rtems.org/pipermail/rtems-devel/2013-August/004370.html
> >
> > I had to add rtems_chain_explicit_extract() and
> > rtems_chain_explicit_insert() routines.
>
> I understand the reason you have added the extra call. We either need to
> break the existing API or extend the current one. Having two APIs is not
> helpful to users and we need just one. If there is an agree path to one
> API I would be happier. It could be a warning for non-SMP that the API
> will change.
>
> Chris
> _______________________________________________
> rtems-devel mailing list
> rtems-devel at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel