Hey Pavel, I spent a couple hours trying to hack together a version of Daniel's approach in RTEMS. I think there might be a fundamental problem that RTEMS compiles the rbtree code into score library (libscore.a). I think this means that the compiler cannot inline comparison hooks within the score insert/search rbtree routines. Perhaps I misunderstood the approach and should try again later, but I don't have time right now.
-Gedare On Wed, Aug 28, 2013 at 1:02 PM, Gedare Bloom <ged...@rtems.org> wrote: > Thanks Pavel. More below. > > On Wed, Aug 28, 2013 at 10:31 AM, Pavel Pisa <ppisa4li...@pikron.com> wrote: >> 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). >> > I tend to agree. Let the "user" of the data structure handle the > locking around it at least for RTEMS core code. But this means right > now going through all of RTEMS core and replacing chain_xxx with > chain_xxx_unprotected. > > Conversely, we make all the functions unprotected by default and > introduce "_protected" variants for the API layer. > >> 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. >> > The big problem for RTEMS is the exposure of chains through the user API. > >> 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. >> > His approach looks really neat, although the performance is tightly > tied to gcc. I'm not a huge fan of relying on CPP for code generation, > but if the performance/programmability tradeoff is good I think it is > worth considering. (Heavy CPP usage is one reason I do not like the > BSD tree.h approach, which uses macros to generate type-specific > red-black or splay trees.) > > Even if we cannot get Daniel's wrappers code directly, I think the > idea could be recreated in the RTEMS RBTree code base with some > effort. RTEMS RBTree uses the compare function as an indirection > already. I wonder if we can start with upgrading the current RBTree to > use this new approach of an "initializer struct" and then consider > enhancements such as locking, and "find_near/insert_near" functions > which I have implemented but did not commit. > > I suppose the new approach could also be used to offer indirection for > locking? Daniel's method does not, because Linux does not require > it... > >> 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. >> > I agree, we do not need to think too much about RCU. Especially > because the patent + license issue is a concern. > >> 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@rtems.org >>> http://www.rtems.org/mailman/listinfo/rtems-devel >> _______________________________________________ >> rtems-devel mailing list >> rtems-devel@rtems.org >> http://www.rtems.org/mailman/listinfo/rtems-devel _______________________________________________ rtems-devel mailing list rtems-devel@rtems.org http://www.rtems.org/mailman/listinfo/rtems-devel
