!standard 3.9(26/2) 11-03-31 AC95-00217/01 !class confirmation 11-03-31 !status received no action 11-03-31 !status received 11-03-18 !subject Locking of tags table !summary !appendix From: Bob Duff Sent: Friday, March 18, 2011 6:59 PM Please don't think we need to address this for Ada 2012 (if it's a problem at all)! 3.9 says: Implementation Permissions 26/2 {AI95-00260-02} {AI95-00279-01} The implementation of Internal_Tag and Descendant_Tag may raise Tag_Error if no specific type corresponding to the string External passed as a parameter exists in the partition at the time the function is called, or if there is no such type whose innermost master is a master of the point of the function call. 26.a/2 Reason: {AI95-00260-02} {AI95-00279-01} {AI95-00344-01} Locking would be required to ensure that the mapping of strings to tags never returned tags of types which no longer exist, because types can cease to exist (because they belong to another task, as described above) during the execution of these operations. Moreover, even if these functions did use locking, that would not prevent the type from ceasing to exist at the instant that the function returned. Thus, we do not require the overhead of locking; hence the word "may" in this rule. I don't understand that comment about locking. It seems like Ada.Tags needs to contain a hash table (or something) mapping strings to tags, and that mapping needs to be locked. Consider: with Ada.Tags; use Ada.Tags; package P is pragma Elaborate_Body; type T1 is tagged null record; end P; package body P is task T; task body T is begin ... Internal_Tag (T1'Tag) ... -- reads the mapping end T; end P; with P; -- so the task gets activated before elaborating T2 package P2 is type T2 is tagged null record; -- writes the mapping end P2; with P, P2; procedure Main is begin null; end Main; Task T is reading the hash table in Ada.Tags at the same time as the env task is writing it (while elaborating T2). So why does that AARM note claim that locking is unnecessary? There are no nested tagged types in this example! And why would we care? Locking wouldn't be a big efficiency problem, as far as I can see. *************************************************************** From: Randy Brukardt Sent: Friday, March 18, 2011 7:51 PM > Please don't think we need to address this for Ada 2012 (if it's a > problem at all)! There's nothing to address, so far as I can tell. > 3.9 says: ... > I don't understand that comment about locking. You ought to read AI95-00279-1, it describes this in more detail. > It seems like Ada.Tags needs to contain a hash table (or > something) mapping strings to tags, Yes. > and that mapping needs to be locked. No. > Consider: ... > Task T is reading the hash table in Ada.Tags at the same time as the > env task is writing it (while elaborating T2). So why does that AARM > note claim that locking is unnecessary? Because it is unnecessary. There are two realistic ways to implement these tag tables. One is to use some sort of registration/deregistration scheme for tags; these would be called at the freezing point of the type, and when it ceases to exist. Such an implementation would probably require locking. But it has the advantage of not having entries for any non-created types. But the standard always intended that the tag table could be created statically (at link time). That however, brings up the problem of dealing with uncreated types. The point of this rule is to ensure that an implementation need do no more than associate a single Boolean flag with each entry as to whether it is created or not in order to be able to raise Tag_Error as needed. Furthermore, for a library level tagged type, that flag can only change value once (from False - not created to True - created) as such types are never destroyed until the program has completed (and completed finalization). As such, the flags can be treated as Atomic components [although it probably would be OK to use a Volatile packed implementation] and no locking is needed to deal with them. Since the hash table itself is a static constant that never changes during the program, and no locking is needed to deal with the creation flags, no locking is needed at all to implement this feature. It should be noted that these rules also allow the dynamic version of the hash table. I think it is arguable that the Ada 95 version of these rules did not allow a dynamic registration scheme for these tags. (I surely never considered one for Janus/Ada prior to working on AI95-00279-1 -- I didn't think it was allowed by the rules. I probably would have implemented this long ago had I known that it was OK.) Since the intent was that such an implementation be allowed, we needed the rules to match that. (But, as noted, such an implementation requires locking.) > There are no nested tagged types in this example! > > And why would we care? Locking wouldn't be a big efficiency problem, > as far as I can see. Locking involves the task supervisor, even in programs that don't use any tasking. For Janus/Ada at least, locking requires some mechanism to trigger a context switch if a lock is closed (else the program will loop forever waiting for a lock that would not ever become open, since tasking is non-preemptive in most of our targets). That of course requires dragging in the task supervisor. Janus/Ada was designed from the ground up for storage minimization, so the task supervisor is only included in programs that need it. Since it is around 48K in size (or 3 times the minimum program size that doesn't use it), this can be a big deal. Also, keep in mind that there is a lot of work going into lock-free algorithms these days. I don't think we want to be forcing locking -- anywhere -- if we don't have to. *************************************************************** From: Bob Duff Sent: Friday, March 18, 2011 8:32 PM > There's nothing to address, so far as I can tell. Well, you addressed my question. Thanks! Right, there's apparently no language issue to address. > Locking involves the task supervisor, even in programs that don't use > any tasking. Some implementations allow protected objects without dragging in tasking support. AdaMagic is one. GNAT is not. But I think GNAT has some other way of locking that won't drag in tasking. Anyway, thanks for the explanation, and the AI pointer. *************************************************************** From: Robert Dewar Sent: Saturday, March 19, 2011 10:27 AM > Some implementations allow protected objects without dragging in > tasking support. AdaMagic is one. GNAT is not. But I think GNAT has > some other way of locking that won't drag in tasking. Yes it does *************************************************************** From: Tucker Taft Sent: Saturday, March 19, 2011 10:55 AM This is a problem that can definitely be handled with lock-free synchronization in many implementations, given the very constrained way registration of tags takes place. *************************************************************** From: Bob Duff Sent: Saturday, March 19, 2011 11:17 AM Right. But this assumes that "library level" means "lives forever" (i.e. until the Ada world is destroyed on process exit). But in GNAT we're trying to do some sort of unloading of dynamically linked libraries, which I don't fully understand. I just mention this for interest -- there's no ARG action wanted here. ***************************************************************