!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.

***************************************************************