www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Walter is right about transitive readonly - here's the alternative

reply "Janice Caron" <caron800 googlemail.com> writes:
Walter is right about transitive readonly - but we need something
instead. I believe this is that something!

As other threads have shown, there are a squillion use-cases which
seem to need either transitive const or mutable members. (The two
concepts are to some extent interchangeable).

However, as Walter has pointed out, such declarations make it possible
(...and in fact, easy...) to write thread-unsafe code. If I have
understood the arguments correctly, this is the primary reason why
Walter wants to outlaw them.

So, here's a better alternative. Let's do thread-safety _properly_.

We're going to need three new keywords, and a slightly new way of doing things.

So, let's take this one step at a time...

First off, we introduce a new storage class, whose meaning is
"threadsafe". I'm going to use the keyword "shared" for that. It will
have some very precise rules and features, so I'll explain one thing
at a time.

Let's start with a class, C, defined as follows

 class A
 {
     int x;
     int y;
 }

Nothing new there. Now lets use our new storage class:

 class B
 {
     A a;
     shared A shared_a;
 };

Observe the new keyword shared. The first thing implied by that
keyword is that all of the member variables of shared_a are now
completely hidden, as though the entire contents of A had been
declared private and B were in another module. That means...

 B b;
 int n = b.a.x; /* OK */
 int n = b.a.y; /* OK */
 int n = b.shared_a.x; /* Error */
 int n = b.shared_a.y; /* Error */

You cannot access the member variables of something declared shared -
not even to /read/. To do so is a compile time error. (And I stress,
compile time. It's nice to have your thread-safety ensured at
compile-time).

So how do you read B's shared member variables? Well, that's where the
second new keyword comes in - "readable"

 scope a = readable(b.shared_a);
 int n = a.x; /* OK - reads b.shared_a.x */
 int m = a.y; /* OK - reads b.shared_a.y */

Observe that a is a scope variable. That's because readable obtains a
shared-access mutex, which must be released when a goes out of scope
by any means. The expression "readable(x)" is more or less equivalent
to "new ReadLock!(typeof(x))(x)". In C++, I would overload the ->
operator of the resulting class, but you can't do that in D, which is
why doing this at the language level is a really cool solution.

But you still can't write to b.shared_a.

 a.x = 4; /* Error - a is readonly */
 a.y = 4; /* Error - a is readonly */

To write to b.shared_a, you need the third keyword. You guessed it - "writable".

 scope a = writable(b.shared_a);
 int n = a.x; /* OK - reads b.shared_a.x */
 a.y = n; /* OK - assigns b.shared_a.y */

Again, a is a scope variable. That's because writable obtains an
exclusive-access mutex, which must be released when a goes out of
scope by any means. As with readable, the expression "writable(x)" is
more or less equivalent to "new WriteLock!(typeof(x))(x)". In C++, I
would overload the -> operator of the resulting class, but you can't
do that in D, which, again, is why doing this at the language level is
a cool solution.

To recap...

It is a compile-time error to refer to the member variables of
b.a_shared directly. Instead, you must obtain a second reference to
b.a_shared, using either readable(b) or writable(b), and you can
access the member variables /only/ through those. The locks are scoped
so that the mutexes always get released.

Now

- - - - how does this help with const? - - - -

Because shared variables are threadsafe, it is now harmless regard
them as mutable. This allows to to re-introduce the concept of
"logical constness" to D ... but only in a threadsafe way. Like this:

 class Shape
 {
     shared class Raster raster_s;
     abstract void draw();
 }

 class Rectangle
 {
     int x0, y0, x1, y1;

     void draw()
     {
         scope raster = writable(raster_s);
         raster.drawRectangle(x0,y0,x1,y1);
     }
 }

 const Rectangle r;
 r.draw(); /* OK */

Voila!

There is no longer any need for the keyword "mutable". (Just use
"shared" instead). There is no longer any need for const transitivity.
(Just use "shared" as needed).

- - - - you still need to be careful - - - -

There is no magic bullet to thread-safety. This mechanism does ensure
that multiple threads won't try to access the same variable at the
same time, but what it /won't/ do is prevent deadlocks. It's also
still possible to screw up. For instance - you cannot get a write lock
if you already hold a lock...

 scope a = readable(x);
 scope b = writable(x); /* Error - b is already locked by this thread */

That error is not always detectable by the compiler.

And you have to be aware that other threads may modify shared things
when they're not locked. For example, my lookup-from-file class
becomes

 class Lookup
 {
     shared int[int] map_s;

     int readonly lookup(int key)
     {
         {
             auto map = readable(map_s);
             if (key in map) return map[key];
         }
         {
             auto map = writable(map_s);
             if (key in map) return map[key]; /* pay attention */

             /* read stuff from file and store it in map */

             return map[key];
         }
     }
 }

See how I had to check the cache twice? Once while readable, then
again while writable? That's because, between the unlocking of the
read lock and the locking of the write lock, another thread could have
got in and updated the map.

- - - - conclusion - - - -

This is a viable, threadsafe alternative to both intransitive const
and logical const.

It allows us to build all of the real-world use-cases that have been
suggested a need for intransitive const or logical const.

You get three new keywords:
* shared
* readable
* writable

You have to learn a new discipline to use these features, but it's not that hard
Sep 13 2007
next sibling parent reply Regan Heath <regan netmail.co.nz> writes:
I'm still taking this is, on the surface (my first impression) is that 
it sounds like a good idea.  I do have a couple of comments...

Janice Caron wrote:

 There is no magic bullet to thread-safety. This mechanism does ensure
 that multiple threads won't try to access the same variable at the
 same time, but what it /won't/ do is prevent deadlocks. 


What sort of deadlocks, this sort...

[thread1]
scope a = readable(x);
--context switch here--
scope b = readable(y);

[thread2]
scope b = readable(y);
--or context switch here--
scope a = readable(x);

(caused by a timing issue)

or, this sort:

[thread1]
scope a = readable(x);
scope b = readable(x);  //deadlocks unless locks are re-entrant

(this one occurs in a number of forms, but the basic problem is the same)

Currently "synchronized" in D is reentrant :)


 It's also
 still possible to screw up. For instance - you cannot get a write lock
 if you already hold a lock...
 
  scope a = readable(x);
  scope b = writable(x); /* Error - b is already locked by this thread */


You mean "x is already locked.." :)


 That error is not always detectable by the compiler.


Does it 'break' the system to allow a thread with a read lock to aquire 
a write lock (assuming we block until no other thread has a read lock)?

If one of the goals of this system is to prevent aliasing style 
problems, eg.

int a;
foo(&a,&a);

void foo(int *a, int *b)
{
   if (b == 5) return ;
   *a = 5;
   //oops b == 5 now
}

?

If not then we may be able to handle this case with some clever locking 
routines.

One observation;  as these variables are scoped you know that if you 
already have a read lock then the write lock lifetime is equal to or 
less than the read lock lifetime.

And vice-versa.  So, how about the opposite case:

scope b = writable(x);
scope a = readable(x);

Allowed?  Error?  Can we also handle this case?

I suspect it might be possible to handle it but I am not sure.


 And you have to be aware that other threads may modify shared things
 when they're not locked. 


At first this comment seemed contrary to the whole purpose of your idea, 
that is until I realised you meant "you have to be aware that other 
threads may modify shared things when /you haven't got them locked 
yourself/"

So, just to clarify under your system the only time a shared object may 
change is when it's locked by the thread making the change, correct?


  class Lookup
  {
      shared int[int] map_s;
 
      int readonly lookup(int key)
      {
          {
              auto map = readable(map_s);
              if (key in map) return map[key];
          }
          {
              auto map = writable(map_s);
              if (key in map) return map[key]; /* pay attention */
 
              /* read stuff from file and store it in map */
 
              return map[key];
          }
      }
  }
 
 See how I had to check the cache twice? Once while readable, then
 again while writable? That's because, between the unlocking of the
 read lock and the locking of the write lock, another thread could have
 got in and updated the map.


It would therefore be quite beneficial to allow overlapping/simultaneous 
read/write locks (in a single thread), if at all possible.

It seems like it may be possible to code this idea up as a library 
solution, hmmm...

Regan
Sep 13 2007
next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Regan Heath <regan netmail.co.nz> wrote:

 same time, but what it /won't/ do is prevent deadlocks.


 What sort of deadlocks


I only meant, it's not possible to eliminate all possible source of
deadlocks. (Whereas, it /is/ possible to eliminate all unauthorised
read/write access).


 [thread1]
 scope a = readable(x);
 --context switch here--
 scope b = readable(y);

 [thread2]
 scope b = readable(y);
 --or context switch here--
 scope a = readable(x);


Yep, that looks like a deadlock to me. It is possible to eliminate
this by writing your code differently, but let's not get too
complicated just yet.



 or, this sort:

 [thread1]
 scope a = readable(x);
 scope b = readable(x);  //deadlocks unless locks are re-entrant


Readables would definitely be re-entrant, since multiple read locks
are allowed anyway.



  scope a = readable(x);
  scope b = writable(x); /* Error - b is already locked by this thread */


 You mean "x is already locked.." :)


I guess I did, yes. A pending write lock causes all future lock
requests to wait, until the mutex becomes unlocked. In the above
example, the read lock a will never be released because the scope
rules, so it's a deadlock.



 Does it 'break' the system to allow a thread with a read lock to aquire
 a write lock (assuming we block until no other thread has a read lock)?


Yes. See my Lookup example for how to do it properly. In general, the
way you turn a read lock into a write lock is, you don't. You do this
instead:

(1) Get the read lock; do your test; release the read lock. If you
need to write then
(2) Get the write lock; REPEAT THE TEST; don't write if another thread
got there first.




 If one of the goals of this system is to prevent aliasing style
 problems, eg.

 int a;
 foo(&a,&a);


I see what you mean, but no, it won't fix that. If you try to get two
independent write locks, then you'll deadlock. If you use one write
lock for both parameters, then the aliasing problem is back. No,
that's a problem for "restrict".




 One observation;  as these variables are scoped you know that if you
 already have a read lock then the write lock lifetime is equal to or
 less than the read lock lifetime.

 And vice-versa.  So, how about the opposite case:

 scope b = writable(x);
 scope a = readable(x);

 Allowed?  Error?  Can we also handle this case?


Not allowed. You can't get a read lock until the write lock is
released. But in this case, you don't need to, since writeble implies
readable. Just read x through b.



 So, just to clarify under your system the only time a shared object may
 change is when it's locked by the thread making the change, correct?


Yes.


 It would therefore be quite beneficial to allow overlapping/simultaneous
 read/write locks (in a single thread), if at all possible.


It isn't possible. It just isn't. There are all sorts of weird and
whacky things that can happen if you try. It has to be forbidden.

(Although it /would/ be possible to make write locks reentrant. It
would mean more overhead though).



 It seems like it may be possible to code this idea up as a library
 solution, hmmm...


In C++ it absolutely is, and I have done it. You can code up
Shared<T>, Readable<T> and Writable<T>. It's not too hard either. But
it would be harder in D because you don't have operator arrow, and you
can't overload dot. So, whereas in C++ you can say p->member, a
library solution in D would have to have something like
p.dereference.member, which is not as nice.

But if you get to write the compiler, you can overcome that deficiency
easily! ;-)
Sep 13 2007
prev sibling next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Regan Heath <regan netmail.co.nz> wrote:

 same time, but what it /won't/ do is prevent deadlocks.


 What sort of deadlocks


I only meant, it's not possible to eliminate all possible source of
deadlocks. (Whereas, it /is/ possible to eliminate all unauthorised
read/write access).


 [thread1]
 scope a = readable(x);
 --context switch here--
 scope b = readable(y);

 [thread2]
 scope b = readable(y);
 --or context switch here--
 scope a = readable(x);


Yep, that looks like a deadlock to me. It is possible to eliminate
this by writing your code differently, but let's not get too
complicated just yet.



 or, this sort:

 [thread1]
 scope a = readable(x);
 scope b = readable(x);  //deadlocks unless locks are re-entrant


Readables would definitely be re-entrant, since multiple read locks
are allowed anyway.



  scope a = readable(x);
  scope b = writable(x); /* Error - b is already locked by this thread */


 You mean "x is already locked.." :)


I guess I did, yes. A pending write lock causes all future lock
requests to wait, until the mutex becomes unlocked. In the above
example, the read lock a will never be released because the scope
rules, so it's a deadlock.



 Does it 'break' the system to allow a thread with a read lock to aquire
 a write lock (assuming we block until no other thread has a read lock)?


Yes. See my Lookup example for how to do it properly. In general, the
way you turn a read lock into a write lock is, you don't. You do this
instead:

(1) Get the read lock; do your test; release the read lock. If you
need to write then
(2) Get the write lock; REPEAT THE TEST; don't write if another thread
got there first.




 If one of the goals of this system is to prevent aliasing style
 problems, eg.

 int a;
 foo(&a,&a);


I see what you mean, but no, it won't fix that. If you try to get two
independent write locks, then you'll deadlock. If you use one write
lock for both parameters, then the aliasing problem is back. No,
that's a problem for "restrict".




 One observation;  as these variables are scoped you know that if you
 already have a read lock then the write lock lifetime is equal to or
 less than the read lock lifetime.

 And vice-versa.  So, how about the opposite case:

 scope b = writable(x);
 scope a = readable(x);

 Allowed?  Error?  Can we also handle this case?


Not allowed. You can't get a read lock until the write lock is
released. But in this case, you don't need to, since writeble implies
readable. Just read x through b.



 So, just to clarify under your system the only time a shared object may
 change is when it's locked by the thread making the change, correct?


Yes.


 It would therefore be quite beneficial to allow overlapping/simultaneous
 read/write locks (in a single thread), if at all possible.


It isn't possible. It just isn't. There are all sorts of weird and
whacky things that can happen if you try. It has to be forbidden.

(Although it /would/ be possible to make write locks reentrant. It
would mean more overhead though).



 It seems like it may be possible to code this idea up as a library
 solution, hmmm...


In C++ it absolutely is, and I have done it. You can code up
Shared<T>, Readable<T> and Writable<T>. It's not too hard either. But
it would be harder in D because you don't have operator arrow, and you
can't overload dot. So, whereas in C++ you can say p->member, a
library solution in D would have to have something like
p.dereference.member, which is not as nice.

But if you get to write the compiler, you can overcome that deficiency
easily! ;-)
Sep 13 2007
prev sibling next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Regan Heath <regan netmail.co.nz> wrote:

 [thread1]
 scope a = readable(x);
 --context switch here--
 scope b = readable(y);

 [thread2]
 scope b = readable(y);
 --or context switch here--
 scope a = readable(x);


In fact, this example would not deadlock, because read locks are
non-exclusive. There is absolutely no problem with multiple threads
aquiring them simultaneously. That's the whole point of them.

But if you'd said writable, then it would have been a deadlock.

In general, you just wouldn't do

 shared A a_s;
 shared B b_s;

 scope a = writable(a_s);
 scope b = writable(b_s);

because of the possibility of deadlocks. Instead, you'd do

 struct AB
 {
     A a;
     B b;
 }

 shared AB ab_s;

 scope ab = writable(ab_s);

and then refer to ab.a and ab.b.
Sep 13 2007
prev sibling parent reply Sean Kelly <sean f4.ca> writes:
Regan Heath wrote:

 Does it 'break' the system to allow a thread with a read lock to aquire 
 a write lock (assuming we block until no other thread has a read lock)?


Some read-write locks allow a read lock to be 'upgraded' to a write 
lock, but I never liked the idea.  For one, it complicates the algorithm 
quite a bit.


Sean
Sep 13 2007
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Sean Kelly" wrote

 Regan Heath wrote:

 Does it 'break' the system to allow a thread with a read lock to aquire a 
 write lock (assuming we block until no other thread has a read lock)?


 Some read-write locks allow a read lock to be 'upgraded' to a write lock, 
 but I never liked the idea.  For one, it complicates the algorithm quite a 
 bit.


There is no problem with upgrading, the problem is the assumption that the 
data has not changed since you have obtained the write lock.  Janice's code 
is a good example.  Let's say we change it to:

 class Lookup
 {
     shared int[int] map_s;

     int readonly lookup(int key)
     {
         {
             auto map = readable(map_s);
             if (key in map) return map[key];
         //}  no release of readable lock yet.
         //{
             auto map = writable(map_s);
             //if (key in map) return map[key];  // uncomment this for 
thread safety
             map[key] = readDataFromFile(key);
             return map[key];
         }
     }
 }

And you have 2 threads running, both are simultaneously executing this code. 
If they both have a read lock, and want to upgrade to a write lock, who gets 
it first?  Whoever does, once the first thread has released the lock, the 
second thread now gets the lock AFTER the data is modified.  There's no way 
around it.

Basically, you can *upgrade*, but you can't be certain that the data didn't 
change.  You may be able to do something funky like return a special flag if 
you are the *first* thread to get the upgrade, but I think the added 
overhead is not going to be worth it, and the coder may assume that since 
they upgraded, the data didn't change, until they read the documentation (2 
weeks later after chasing down some obscure thread bug).

BTW, Janice, I like your idea, I think it should be added.

-Steve
Sep 13 2007
next sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 And you have 2 threads running, both are simultaneously executing this code.
 If they both have a read lock, and want to upgrade to a write lock, who gets
 it first?


A write lock cannot be granted until /all/ read-locks are unlocked. If
another thread has a read lock, then that thread has a promise that
the data which the lock protects will not change. That's what a read
lock /means/. So you cannot "upgrade" a read lock into a write lock,
for the reason that multiple threads might simultaneously be trying to
do the same thing, and that would deadlock.
Sep 13 2007
parent Regan Heath <regan netmail.co.nz> writes:
Janice Caron wrote:

 On 9/13/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 And you have 2 threads running, both are simultaneously executing this code.
 If they both have a read lock, and want to upgrade to a write lock, who gets
 it first?


 
 A write lock cannot be granted until /all/ read-locks are unlocked. If
 another thread has a read lock, then that thread has a promise that
 the data which the lock protects will not change. That's what a read
 lock /means/. So you cannot "upgrade" a read lock into a write lock,
 for the reason that multiple threads might simultaneously be trying to
 do the same thing, and that would deadlock.


When I made my suggestion I realised you could not upgrade a read lock 
to a write lock until all other read locks were released.  What I didn't 
realise at the time was that waiting for the other read locks to be 
released introduces the possiblity of a deadlock, as you say.

If you take the idea further i.e. You can detect the situation where all 
read locks are held by threads requesting write locks and you can grant 
it to each in turn.

However, that brings you back to the problem that the 2nd, 3rd, nth 
write lock granted in this situation will be writing over data it hasn't 
seen (during it's read lock phase) so the behaviour is likely to be 
incorrect and therefore a 2nd read/check is still required to determine 
the correct action to take.

Regan
Sep 13 2007
prev sibling next sibling parent Sean Kelly <sean f4.ca> writes:
Steven Schveighoffer wrote:

 "Sean Kelly" wrote

 Regan Heath wrote:

 Does it 'break' the system to allow a thread with a read lock to aquire a 
 write lock (assuming we block until no other thread has a read lock)?


 Some read-write locks allow a read lock to be 'upgraded' to a write lock, 
 but I never liked the idea.  For one, it complicates the algorithm quite a 
 bit.


 
 There is no problem with upgrading, the problem is the assumption that the 
 data has not changed since you have obtained the write lock.  Janice's code 
 is a good example.  Let's say we change it to:
 
  class Lookup
  {
      shared int[int] map_s;
 
      int readonly lookup(int key)
      {
          {
              auto map = readable(map_s);
              if (key in map) return map[key];
          //}  no release of readable lock yet.
          //{
              auto map = writable(map_s);
              //if (key in map) return map[key];  // uncomment this for 
 thread safety
              map[key] = readDataFromFile(key);
              return map[key];
          }
      }
  }
 
 And you have 2 threads running, both are simultaneously executing this code. 
 If they both have a read lock, and want to upgrade to a write lock, who gets 
 it first?  Whoever does, once the first thread has released the lock, the 
 second thread now gets the lock AFTER the data is modified.  There's no way 
 around it.


I think upgradeable read locks only work if the upgrade process can 
fail.  Since two threads hold a read lock in this case, neither thread 
could upgrade to a write lock.  This makes the upgrade process of very 
limited utility IMO, and is another reason why I didn't implement it in 
Tango's ReadWriteLock.


Sean
Sep 13 2007
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Steven Schveighoffer" wrote

 There is no problem with upgrading, the problem is the assumption that the 
 data has not changed since you have obtained the write lock.


I have thought of one other problem:

Without remembering which threads have read locks, you can just use a simple 
reference counter to tell if a object is read-locked.

When "upgrading" becomes possible, then you have to know whether the thread 
you are in holds a read-lock or not.  This means you have to store (probably 
in the mutex itself) a list of all threads that hold the read-lock.  Then 
when you go to do the upgrade, it must check to see if the upgrading thread 
is in the list.  This is at least a O(lg(n)) operation, whereas a reference 
counter is a O(1).

BTW I think you could do reentrant read locks (just increment/decrement the 
reference counter one extra time), and write locks could be reentrant (only 
have to store one thread id, you could even use the same reference counter 
as the read locks).

So the only really "bad" situation is:

readable(o);
writable(o);

This really seems awfully scary.  This really could result in an easy 
deadlock, where code that holds a read lock could call code that eventually 
grabs a write-lock.

I'm thinking now that the best thing is just to use read-write locks, unless 
you really know what you are doing, and own all the code that accesses a 
shared object.

I guess I'll cancel my vote for this as a language feature.  Better left as 
a library feature.  Sorry Janice :(

-Steve
Sep 13 2007
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 Without remembering which threads have read locks, you can just use a simple
 reference counter to tell if a object is read-locked.


My C++ implementation used an atomic counter for read locks, an atomic
counter for (pending) write locks, and an OS mutex.



 When "upgrading" becomes possible, then you have to know whether the thread
 you are in holds a read-lock or not.  This means you have to store (probably
 in the mutex itself) a list of all threads that hold the read-lock.  Then
 when you go to do the upgrade, it must check to see if the upgrading thread
 is in the list.  This is at least a O(lg(n)) operation, whereas a reference
 counter is a O(1).


...and it must do all that ATOMICALLY. Forget it. You'd have to mutex
lock the mutex.

Upgrading just isn't possible in any case - not even in /theory/, let
alone in a given implementation.



 BTW I think you could do reentrant read locks (just increment/decrement the
 reference counter one extra time)


Yes, read locks are inherently re-entrant.



 and write locks could be reentrant (only
 have to store one thread id, you could even use the same reference counter
 as the read locks).


My implementation wasn't re-entrant for write locks. I never found it
necessary. That said, I know that it is possible to make re-entrant
write locks, but probably not by the means that you suggest.




 So the only really "bad" situation is:

 readable(o);
 writable(o);


You cannot get a write lock if you already have a read lock on the
same object. It is impossible. That is a deadlock.



 This really seems awfully scary.  This really could result in an easy
 deadlock, where code that holds a read lock could call code that eventually
 grabs a write-lock.


The trick is not to lock things for longer than you actually need to
access them.

Even without fancy wrappers, that holds true. If you do mutexes
manually, you are expected to release them as soon as you've finished
with them.



 I'm thinking now that the best thing is just to use read-write locks, unless
 you really know what you are doing, and own all the code that accesses a
 shared object.


Ah, but that could lead to even more deadlocks. If a hundred threads
all want to read a resource at the same time,  and we can guarantee
that no one's writing to it at the time,
why not let them?



 I guess I'll cancel my vote for this as a language feature.  Better left as
 a library feature.  Sorry Janice :(


Hehehe.

It cannot be a library feature, because it cannot be implemented in a
library, because to implement it in a library, you'd need transitive
const, or logical const.

:-)
Sep 13 2007
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Janice Caron" wrote

 On 9/13/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 Without remembering which threads have read locks, you can just use a 
 simple
 reference counter to tell if a object is read-locked.


 My C++ implementation used an atomic counter for read locks, an atomic
 counter for (pending) write locks, and an OS mutex.


Using atomic counters, how do you read the write counter, then increment the 
read counter atomically without using the mutex?  I'm assuming that's the 
benefit of having read/write locks.


 When "upgrading" becomes possible, then you have to know whether the 
 thread
 you are in holds a read-lock or not.  This means you have to store 
 (probably
 in the mutex itself) a list of all threads that hold the read-lock.  Then
 when you go to do the upgrade, it must check to see if the upgrading 
 thread
 is in the list.  This is at least a O(lg(n)) operation, whereas a 
 reference
 counter is a O(1).


 ...and it must do all that ATOMICALLY. Forget it. You'd have to mutex
 lock the mutex.

 Upgrading just isn't possible in any case - not even in /theory/, let
 alone in a given implementation.


My point is not to advocate upgrading.  I believe it is possible, even in 
practice, but I don't think I'll ever use it :)


 and write locks could be reentrant (only
 have to store one thread id, you could even use the same reference 
 counter
 as the read locks).


 My implementation wasn't re-entrant for write locks. I never found it
 necessary. That said, I know that it is possible to make re-entrant
 write locks, but probably not by the means that you suggest.



instance, if I have a shared object that has properties, the property access 
function locks the object every time I access the property.  However, 
outside the object, if I want to atomically read many properties, I lock the 
object first, then access the properties, which then re-lock the object. 
Works rather well.


 So the only really "bad" situation is:

 readable(o);
 writable(o);


 You cannot get a write lock if you already have a read lock on the
 same object. It is impossible. That is a deadlock.


I no longer care to argue this point :)


 This really seems awfully scary.  This really could result in an easy
 deadlock, where code that holds a read lock could call code that 
 eventually
 grabs a write-lock.


 The trick is not to lock things for longer than you actually need to
 access them.

 Even without fancy wrappers, that holds true. If you do mutexes
 manually, you are expected to release them as soon as you've finished
 with them.



 I'm thinking now that the best thing is just to use read-write locks, 
 unless
 you really know what you are doing, and own all the code that accesses a
 shared object.


 Ah, but that could lead to even more deadlocks. If a hundred threads
 all want to read a resource at the same time,  and we can guarantee
 that no one's writing to it at the time,
 why not let them?



The issue I see is if you pass the object to another function which has no 
idea whether you have it locked or not, so it might think it's ok to 
write-lock it.  It's something a new programmer could do easily by mistake. 
"oh, I want to call niftyFunction with my locked object, hm... it wants the 
original object, OK, here you go! (deadlocks)."

I'm not saying its a bad feature, or that it's not useful.  I'm just saying 
it's no less error prone than the current mutex system.  A user must use and 
understand the system properly to not get into trouble, just like he must 
use and understand the current read-write locking system.


 I guess I'll cancel my vote for this as a language feature.  Better left 
 as
 a library feature.  Sorry Janice :(


 Hehehe.

 It cannot be a library feature, because it cannot be implemented in a
 library, because to implement it in a library, you'd need transitive
 const, or logical const.


I'm guessing that tango.core.sync.ReadWriteMutex successfully implements it 
using a library.  It'd probably be possible using templates to make wrappers 
as you have suggested.

-Steve
Sep 13 2007
next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 It cannot be a library feature, because it cannot be implemented in a
 library, because to implement it in a library, you'd need transitive
 const, or logical const.


 I'm guessing that tango.core.sync.ReadWriteMutex successfully implements it
 using a library.  It'd probably be possible using templates to make wrappers
 as you have suggested.


You can certainly have mutexes in a library. No problem there. But
what you can't do is put them in a const object and expect them to
work. Not unless Walter explicitly decides to let you.

Remember the goal here is not /just/ to have an easy way to do
mutexes. It's also to allow a workaround for const transitivity.
Walter says const intransitivity (or mutable members) would not be
thread-safe - and he's right. So what we have here in this suggestion
of mine is mutable members which /are/ thread safe. And /that's/ what
you can't do in a library, because you don't have the very thing I
want to achieve!
Sep 13 2007
prev sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 My C++ implementation used an atomic counter for read locks, an atomic
 counter for (pending) write locks, and an OS mutex.


 Using atomic counters, how do you read the write counter, then increment the
 read counter atomically without using the mutex?


You don't have to make the entire process atomic, just the increments
and decrements.

getWriteLock()
{
    atomicIncrement(wcount);
    obtainMutex();
}

releaseWriteLock()
{
    releaseMutex();
    atomicDecrement(wcount);
}

getReadLock()
{
    while (wcount != 0)
    {
        obtainMutex();
        releaseMutex();
    }
    if (atomicIncrement(rcount) == 1)
    {
        obtainMutex();
    }
}

releaseReadLock()
{
    if (atomicDecrement(rcount) == 0)
    {
        releaseMutex();
    }
}

I think that's right. That's from memory. If it's wrong, I can't check
until tomorrow. It looks right to me though.
Sep 13 2007
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Janice Caron" wrote

 getReadLock()
 {
    while (wcount != 0)
    {
        obtainMutex();
        releaseMutex();
    }
    if (atomicIncrement(rcount) == 1)
    {
        obtainMutex();
    }
 }


I understand that this might not be exactly what you have, but I do see a 
chance for a problem here.

Thread 1 and 2 are attempting to read the value, and nobody is writing it. 
Both threads skip the while loop, but then switch out of context to Thread 3 
which write-locks the data.  Thread 1 does the first increment, tries to 
lock the mutex, gets put to sleep.  Thread 2 switches back into context, 
increments the read counter, then proceeds, however thread 3 can write while 
thread 2 is reading.

Not a very likely situation, but of course those types are the worst when it 
comes to multithreaded programming.  Of course, you may have already solved 
this problem :)  but I can't see how you can do it without making the "read 
write counter, if 0 increment read counter, if that is now 1, lock" atomic.

-Steve
Sep 13 2007
prev sibling parent Sean Kelly <sean f4.ca> writes:
Janice Caron wrote:

 On 9/13/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 My C++ implementation used an atomic counter for read locks, an atomic
 counter for (pending) write locks, and an OS mutex.


 Using atomic counters, how do you read the write counter, then increment the
 read counter atomically without using the mutex?


 
 You don't have to make the entire process atomic, just the increments
 and decrements.
 
 getWriteLock()
 {
     atomicIncrement(wcount);
     obtainMutex();
 }
 
 releaseWriteLock()
 {
     releaseMutex();
     atomicDecrement(wcount);
 }
 
 getReadLock()
 {
     while (wcount != 0)
     {
         obtainMutex();
         releaseMutex();
     }
     if (atomicIncrement(rcount) == 1)
     {
         obtainMutex();
     }
 }
 
 releaseReadLock()
 {
     if (atomicDecrement(rcount) == 0)
     {
         releaseMutex();
     }
 }
 
 I think that's right. That's from memory. If it's wrong, I can't check
 until tomorrow. It looks right to me though.


To pick a nit, I think the above code may have some problems.

Scenario 1:

* Thread A acquires a write lock, mutates the protected data, and
   releases the lock.
* Thread B acquires a read lock and stalls.
* Thread C acquires a read lock.

   Here, because wcount is 0, thread C will never call obtainMutex and 
therefore may view bad data.

Scenario 2:

* Thread A acquires a read lock and stalls.
* Thread B attempts to acquire a write lock, increments wcount, and
   blocks on obtainMutex.
* Thread C attempts to acquire a read lock, sees wcount is nonzero and
   blocks on obtainMutex.

   Here, thread C should be allowed to proceed and read the protected 
data but blocks instead.

There may be others as well, but I think the above is sufficient to 
illustrate that multithreaded programming at the typical level (manual 
locking, etc) is really quite difficult and therefore probably not an 
ideal goal for future language development.  I'll admit I do like the 
idea of a programmer declaring intent to read/write data, but I do 
wonder if additional integrated locking is the best way to go about 
solving this particular issue.  Perhaps the basic concept could be 
applied another way?


Sean
Sep 13 2007
prev sibling parent reply Sean Kelly <sean f4.ca> writes:
Janice Caron wrote:

 On 9/13/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 Without remembering which threads have read locks, you can just use a simple
 reference counter to tell if a object is read-locked.


 
 My C++ implementation used an atomic counter for read locks, an atomic
 counter for (pending) write locks, and an OS mutex.


For comparison, my D implementation uses a mutex and two condition 
variables.  The condvars simplify blocking when a write lock is held, etc.


 When "upgrading" becomes possible, then you have to know whether the thread
 you are in holds a read-lock or not.  This means you have to store (probably
 in the mutex itself) a list of all threads that hold the read-lock.  Then
 when you go to do the upgrade, it must check to see if the upgrading thread
 is in the list.  This is at least a O(lg(n)) operation, whereas a reference
 counter is a O(1).




...

 Upgrading just isn't possible in any case - not even in /theory/, let
 alone in a given implementation.


I'm sure it could be done (in fact, POSIX has this feature), but the 
implementation would be a mess and provide marginal gain.


 and write locks could be reentrant (only
 have to store one thread id, you could even use the same reference counter
 as the read locks).


 
 My implementation wasn't re-entrant for write locks. I never found it
 necessary. That said, I know that it is possible to make re-entrant
 write locks, but probably not by the means that you suggest.


It's possible but to do so I think you'd have to maintain a list of 
which threads held which lock.  This doesn't seem terribly efficient, 
and just not worthwhile for something that is of marginal utility.


 So the only really "bad" situation is:

 readable(o);
 writable(o);


 
 You cannot get a write lock if you already have a read lock on the
 same object. It is impossible. That is a deadlock.


Or a read lock if you already have a write lock on something.  Doing so 
would be kind of pointless anyway, and therefore I'd consider it a 
programming error to do so.


Sean
Sep 13 2007
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Sean Kelly" wrote

 My implementation wasn't re-entrant for write locks. I never found it
 necessary. That said, I know that it is possible to make re-entrant
 write locks, but probably not by the means that you suggest.


 It's possible but to do so I think you'd have to maintain a list of which 
 threads held which lock.  This doesn't seem terribly efficient, and just 
 not worthwhile for something that is of marginal utility.


Since write-lock is exclusive, you only need to know a single thread which 
holds the lock.  The thread ID can be stored with the lock, so it is easy to 
tell/efficient.  Basically (in lock() method):

if(locked_id != my_id)
{
  lockSysMutex();
  locked_id = my_id;
  _reentrant++; // initialized to 0
}

and in unlock():

if(--_reentrant == 0)
{
  locked_id = 0;
  unlockSysMutex();
}

I'd disagree that it is of marginal utility ;)  but that's my opinion.  I 


-Steve
Sep 13 2007
parent Sean Kelly <sean f4.ca> writes:
Steven Schveighoffer wrote:

 "Sean Kelly" wrote

 My implementation wasn't re-entrant for write locks. I never found it
 necessary. That said, I know that it is possible to make re-entrant
 write locks, but probably not by the means that you suggest.


 It's possible but to do so I think you'd have to maintain a list of which 
 threads held which lock.  This doesn't seem terribly efficient, and just 
 not worthwhile for something that is of marginal utility.


 
 Since write-lock is exclusive, you only need to know a single thread which 
 holds the lock.  The thread ID can be stored with the lock, so it is easy to 
 tell/efficient.


Hm, good point.  I guess the only complicated bit is upgrading a read 
lock to a write lock, but that's a separate issue.


Sean
Sep 13 2007
prev sibling next sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Sean Kelly <sean f4.ca> wrote:

 Upgrading just isn't possible in any case - not even in /theory/, let
 alone in a given implementation.


 I'm sure it could be done


It certainly can't be done atomically...

Threads 1 and 2 both successfully obtain a read lock.
Thread 1 attempts to upgrade to a write lock. Since thread 2 has a
read lock, it waits.
Thread 2 attempts to upgrade to a write lock. Since thread 1 has a
read lock, it waits.
Deadlock.



 (in fact, POSIX has this feature)


I wonder how. If it's implemented as release the read lock followed by
obtain a write lock, then the caller must beware that another thread
may have written /during/ the upgrade.
Sep 13 2007
parent reply Sean Kelly <sean f4.ca> writes:
Janice Caron wrote:

 On 9/13/07, Sean Kelly <sean f4.ca> wrote:

 Upgrading just isn't possible in any case - not even in /theory/, let
 alone in a given implementation.


 I'm sure it could be done


 
 It certainly can't be done atomically...
 
 Threads 1 and 2 both successfully obtain a read lock.
 Thread 1 attempts to upgrade to a write lock. Since thread 2 has a
 read lock, it waits.
 Thread 2 attempts to upgrade to a write lock. Since thread 1 has a
 read lock, it waits.
 Deadlock.
 
 

 (in fact, POSIX has this feature)


 
 I wonder how. If it's implemented as release the read lock followed by
 obtain a write lock, then the caller must beware that another thread
 may have written /during/ the upgrade.


If I had to guess, I'd say that the upgrade works by ensuring that 
upgrading readers are given precedence when acquiring a write lock, so 
there is no risk of an external writer acquiring the lock if there are 
any readers in the process of upgrading.  Since the POSIX library is 
already explicitly managing the list of waiters rather than relying on 
someone else's mutex/condvar/semaphore/whatever to do so, the additional 
logic may not be a terrible burden.


Sean
Sep 13 2007
parent reply Bruce Adams <tortoise_74 yeah.whoo.co.uk> writes:
Sean Kelly Wrote:


 Janice Caron wrote:

 On 9/13/07, Sean Kelly <sean f4.ca> wrote:

 Upgrading just isn't possible in any case - not even in /theory/, let
 alone in a given implementation.


 I'm sure it could be done


 
 It certainly can't be done atomically...
 
 Threads 1 and 2 both successfully obtain a read lock.
 Thread 1 attempts to upgrade to a write lock. Since thread 2 has a
 read lock, it waits.
 Thread 2 attempts to upgrade to a write lock. Since thread 1 has a
 read lock, it waits.
 Deadlock.
 
 

 (in fact, POSIX has this feature)


 
 I wonder how. If it's implemented as release the read lock followed by
 obtain a write lock, then the caller must beware that another thread
 may have written /during/ the upgrade.


 
 If I had to guess, I'd say that the upgrade works by ensuring that 
 upgrading readers are given precedence when acquiring a write lock, so 
 there is no risk of an external writer acquiring the lock if there are 
 any readers in the process of upgrading.  Since the POSIX library is 
 already explicitly managing the list of waiters rather than relying on 
 someone else's mutex/condvar/semaphore/whatever to do so, the additional 
 logic may not be a terrible burden.
 
 
 Sean


Posix provides this feature for advisory FILE lockiing and not for looking
areas of memory though there is some parallel (especially if you use memory
mapped files). These locks are per process and mediated by the OS rather than
per thread. The fcntl call can fail or the process can be told to wait forever,
inviting deadlock. The POSIX API is very low level and typically needs to be
wrapped up to make it more user friendly.
 
The POSIX threads API is similarly low level but with looser semantics.
It supports several types of lcok:
   normal locks
  recursive locks (where you can relock a mutex you own and must unlock it the
same number of times before it is unlocked).
 error checked locks (unlocking a mutex you don't have locked or relocking one
you do is reported as an error).

I don't think going POSIX is the answer in this case.

However, I do believe the ability to try a lock or specify a timeout is
important. Janice's solution though elegant does not provide support for this.
At minimum a "trylock / islock" is required on which the rest can be built.

I agree with Bill that support for thread-safety should be implemented as a
library. Ideally part of the standard library. I think we're back to
redecorating the christmas tree here.

Regards,

Bruce.
Sep 13 2007
parent Sean Kelly <sean f4.ca> writes:
Bruce Adams wrote:

 Sean Kelly Wrote:
 

 Janice Caron wrote:

 On 9/13/07, Sean Kelly <sean f4.ca> wrote:

 Upgrading just isn't possible in any case - not even in /theory/, let
 alone in a given implementation.


 I'm sure it could be done


 It certainly can't be done atomically...

 Threads 1 and 2 both successfully obtain a read lock.
 Thread 1 attempts to upgrade to a write lock. Since thread 2 has a
 read lock, it waits.
 Thread 2 attempts to upgrade to a write lock. Since thread 1 has a
 read lock, it waits.
 Deadlock.



 (in fact, POSIX has this feature)


 I wonder how. If it's implemented as release the read lock followed by
 obtain a write lock, then the caller must beware that another thread
 may have written /during/ the upgrade.


 If I had to guess, I'd say that the upgrade works by ensuring that 
 upgrading readers are given precedence when acquiring a write lock, so 
 there is no risk of an external writer acquiring the lock if there are 
 any readers in the process of upgrading.  Since the POSIX library is 
 already explicitly managing the list of waiters rather than relying on 
 someone else's mutex/condvar/semaphore/whatever to do so, the additional 
 logic may not be a terrible burden.


 
 Posix provides this feature for advisory FILE lockiing and not for looking
areas of memory though there is some parallel (especially if you use memory
mapped files). These locks are per process and mediated by the OS rather than
per thread. The fcntl call can fail or the process can be told to wait forever,
inviting deadlock. The POSIX API is very low level and typically needs to be
wrapped up to make it more user friendly.


Really?  Where do pthread_rwlock_* fall in this?  I had thought htese 
routines were for thread synchronization.

Regarding pthread_rwlock_*, it turns out I was wrong about the upgrading 
  however.  The approach is to call pthread_rwlock_trywrlock, and this 
will only succeed if no other threads hold either a read or write lock 
but the caller.  This is far more limited than I had remembered.


 I don't think going POSIX is the answer in this case.


Me either, frankly.  Tango's ReadWriteLock doesn't even use the 
pthread_rwlock routines.  I mostly mentioned them because I thought they 
were an example of a read/write lock implementation that supported 
upgrading.


 However, I do believe the ability to try a lock or specify a timeout is
important. Janice's solution though elegant does not provide support for this.
At minimum a "trylock / islock" is required on which the rest can be built.


I /really/ tried to come up with a syntax for integrating trylocks with 
'synchronized', but doing so would have required compiler support and I 
couldn't find a syntax that seemed to fit.  Tango does have tryLock 
calls in its mutex classes however, and some of the primitives allow 
timeouts as well.  The general syntax is:

     auto m = new Mutex;
     if( m.tryLock() ) {
         scope(exit) m.unlock();
         ...
     }

An in-language version would have to be something like:

     synchronized( m.tryLock ) {

     }
     else {

     }


Sean
Sep 13 2007
prev sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Sean Kelly <sean f4.ca> wrote:

 Upgrading just isn't possible in any case - not even in /theory/, let
 alone in a given implementation.


 I'm sure it could be done


It certainly can't be done atomically...

Threads 1 and 2 both successfully obtain a read lock.
Thread 1 attempts to upgrade to a write lock. Since thread 2 has a
read lock, it waits.
Thread 2 attempts to upgrade to a write lock. Since thread 1 has a
read lock, it waits.
Deadlock.



 (in fact, POSIX has this feature)


I wonder how. If it's implemented as release the read lock followed by
obtain a write lock, then the caller must beware that another thread
may have written /during/ the upgrade.
Sep 13 2007
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Janice Caron" wrote

 On 9/13/07, Sean Kelly <sean f4.ca> wrote:

 (in fact, POSIX has this feature)


 I wonder how. If it's implemented as release the read lock followed by
 obtain a write lock, then the caller must beware that another thread
 may have written /during/ the upgrade.


In fact, I think that IS the case.  If you upgrade, and you didn't get it 
first, the lock fails, and you no longer hold the read lock.

The advantage here is that if you ARE the first writer to gain the lock, you 
can avoid the second read to see if anything's changed since you got the 
read lock.

However, I think that is negated by the fact that you will STILL have to 
have code in case you don't get it first.  Not worth it in my opinion.

-Steve
Sep 13 2007
prev sibling next sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Janice Caron wrote:

...


So, does that mean that if I wanted logical constness, but didn't use 
multi-threading at all in my classes with logical constness, I would 
still have to:

   a) write my classes with threading constructs as "shared", 
"readable", and "writable", instead of just putting a mutable member?
   b) have performance penalties because of mutex locking/unlocking?



-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Sep 13 2007
parent "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 Janice Caron wrote:
  >...

 So, does that mean that if I wanted logical constness, but didn't use
 multi-threading at all in my classes with logical constness, I would
 still have to:

    a) write my classes with threading constructs as "shared",
 "readable", and "writable", instead of just putting a mutable member?
    b) have performance penalties because of mutex locking/unlocking?


Yes.

However, if Walter is dead set against logical const, we probably
won't be able to persuade him.

That said, if you code up your program using shared, readable and
writable, then I assume it would be possible to add a compiler switch
to that means "compile single threaded". If that were done, the
compiler could optimise away /all/ of the mutex locking and unlocking,
so the performance hit reduces to zero.

(...but you'd have to link with single-threaded versions of phobos, etc.)
Sep 13 2007
prev sibling next sibling parent Johannes <getridofcrap.johannes.oberg gmail.com> writes:
$.02: I'm a D noob (but I have followed the project in lurk mode for a long
time) so I should probably keep my keyboard shut, but -
can't you call it something else than "shared"? It seems to me that with a
variable that gives you a compile error if you're trying to reach it without
using special commands, the intuitive name isn't "shared". I won't offer a
suggestion for another name though since I'm not well versed in thread
programming.

Otherwise, what you're saying makes good sense to me.
Sep 13 2007
prev sibling next sibling parent reply Christopher Wright <dhasenan gmail.com> writes:
Janice Caron wrote something brilliant:

 We're going to need three new keywords, and a slightly new way of doing things.
 
 So, let's take this one step at a time...
 
  B b;
  int n = b.a.x; /* OK */
  int n = b.a.y; /* OK */
  int n = b.shared_a.x; /* Error */
  int n = b.shared_a.y; /* Error */
 
 You cannot access the member variables of something declared shared -
 not even to /read/. To do so is a compile time error. (And I stress,
 compile time. It's nice to have your thread-safety ensured at
 compile-time).
 
 So how do you read B's shared member variables? Well, that's where the
 second new keyword comes in - "readable"
 
  scope a = readable(b.shared_a);
  int n = a.x; /* OK - reads b.shared_a.x */
  int m = a.y; /* OK - reads b.shared_a.y */
 
  a.x = 4; /* Error - a is readonly */
  a.y = 4; /* Error - a is readonly */
 
 To write to b.shared_a, you need the third keyword. You guessed it -
"writable".
 
  scope a = writable(b.shared_a);
  int n = a.x; /* OK - reads b.shared_a.x */
  a.y = n; /* OK - assigns b.shared_a.y */
 
 Again, a is a scope variable. That's because writable obtains an
 exclusive-access mutex, which must be released when a goes out of
 scope by any means.

 - - - - how does this help with const? - - - -
 
 Because shared variables are threadsafe, it is now harmless regard
 them as mutable. This allows to to re-introduce the concept of
 "logical constness" to D ... but only in a threadsafe way. Like this:
 
  class Shape
  {
      shared class Raster raster_s;
      abstract void draw();
  }
 
  class Rectangle
  {
      int x0, y0, x1, y1;
 
      void draw()
      {
          scope raster = writable(raster_s);
          raster.drawRectangle(x0,y0,x1,y1);
      }
  }
 
  const Rectangle r;
  r.draw(); /* OK */
 
 Voila!


The only thing that concerns me is that now you can make a Rectangle 
class that's not logically const even when it's declared const. That is, 
you could have a class RectangleImplementation that the Rectangle treats 
as a writeable shared object. Then you could have a const Rectangle 
where you can modify its properties at will.

That's a way to provide the 'mutable' keyword, but it's so ugly that I 
would shoot anyone who did that in any code I owned. :P

I'm really in favor of separating logical constness from thread safety. 
And I was thinking that using pure for the thread safety and const for 
everything else was the way to go, but maybe we want a 'threadsafe' 
keyword, too:

  - A pure function is by definition threadsafe and const. There are 
other optimizations that can be made for pure functions. This is what 
Walter is using const for, more or less.
  - A threadsafe function need not be const. (Clearly.)
  - A function that doesn't change anything that anyone can see need not 
be threadsafe (caching, logfiles, everything everyone has posted in the 
past three days).
Sep 13 2007
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Christopher Wright <dhasenan gmail.com> wrote:

 Janice Caron wrote something brilliant:


<grins>


  - A function that doesn't change anything that anyone can see need not
 be threadsafe


This is really the biggie...

If thread safety is a language goal then /everything/ must be
threadsafe, period. No exceptions. None. I think that's what Walter's
aiming at.
Sep 13 2007
parent BCS <ao pathlink.com> writes:
Reply to Janice,


 On 9/13/07, Christopher Wright <dhasenan gmail.com> wrote:
 

 Janice Caron wrote something brilliant:
 


 <grins>
 

 - A function that doesn't change anything that anyone can see need
 not be threadsafe
 


 This is really the biggie...
 
 If thread safety is a language goal then /everything/ must be
 threadsafe, period. No exceptions. None.


No exceptions? what about stack frames? Yes I known that's a little ridicules 
but the only things that /need/ to be thread safe are things that more than 
one thread can view.

Based on that, how about work at the other end with some sort of keyword 
that says "Must not be moved to another thread"? I don't (yet*) know how 
this would be enforced but it's kind of interesting


* I may be, in the near future, working on a project that involves High
assurance 
information flow assertions. The work there might help define what "no
movement" 
would requiter. OTOH having such a concept might make D vary useful in some 
types of programming (multi level secure systems, NSA stuff, etc.)
Sep 13 2007
prev sibling next sibling parent reply Sean Kelly <sean f4.ca> writes:
Janice Caron wrote:

 
 To recap...
 
 It is a compile-time error to refer to the member variables of
 b.a_shared directly. Instead, you must obtain a second reference to
 b.a_shared, using either readable(b) or writable(b), and you can
 access the member variables /only/ through those. The locks are scoped
 so that the mutexes always get released.


What if I only plan to use the class within a single thread and don't 
want to pay for the cost of a lock?  Also, how would this apply to a 
linked-list container?  Would each node have to be shared and thus have 
its own lock, or would the outermost one suffice?


 And you have to be aware that other threads may modify shared things
 when they're not locked. For example, my lookup-from-file class
 becomes
 
  class Lookup
  {
      shared int[int] map_s;
 
      int readonly lookup(int key)
      {
          {
              auto map = readable(map_s);
              if (key in map) return map[key];
          }
          {
              auto map = writable(map_s);
              if (key in map) return map[key]; /* pay attention */
 
              /* read stuff from file and store it in map */
 
              return map[key];
          }
      }
  }
 
 See how I had to check the cache twice? Once while readable, then
 again while writable? That's because, between the unlocking of the
 read lock and the locking of the write lock, another thread could have
 got in and updated the map.


I'll admit I do really like the idea that the programmer's intention is 
made explicit using this approach.  Logical const basically provides 
blanket protection and then gives the programmer a pair of scissors 
which can be used to cut holes in the blanket.  This requires the 
programmer to state explicitly "I plan to read this value" or "I plan to 
write this value" in a way that the compiler can check.  Also, I don't 
know why, but it seems like this may integrate well with transactional 
memory somehow.


Sean
Sep 13 2007
next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Sean Kelly <sean f4.ca> wrote:

 What if I only plan to use the class within a single thread and don't
 want to pay for the cost of a lock?


Interesting question. In C++, I would have said, if you only want
single-threaded, don't bother with thread-safety. It's only an issue
here because it looks like we're being told, you /must/ be
thread-safe.

I think the answer would have to be, write /as if/ multithreaded, and
then compile with a special compiler option (--singlethreaded or
something). That compiler option would throw away all the locking and
reduce it to nothing, so zero performance impact. That would be my
guess, anyway.

Someone else suggested (in another thread, I think) some way of
telling the D compiler "I want to be thread-unsafe" as part of the
D-language itself. I don't know how that would work, but maybe
something like

 unsafe
 {
     /* code */
 }

I don't think Walter would buy it though. I think the compiler option
would be the way to go.



 Also, how would this apply to a
 linked-list container?  Would each node have to be shared and thus have
 its own lock, or would the outermost one suffice?


Things like that are totally up to the class designer, but if you
think of it in old-fashioned terms (manual mutex locking), you'd most
likely want to have one single mutex that controls access to the
entire list. That's what I'd do. You could have smaller granularity if
you want, but I'd go with one per list.

It's not obvious how to express that in code, however! I guess it
would be something like:

class List
{
    void InsertBefore(Node * next, Node * newNode);
    /* etc */
}

shared List shared_list;

scope list = writable(shared_list);
list.insertBefore(next, newNode);

In that example, "this" is being passed around - and it appears
unneccesary. (You'd think insertBefore() could be static) But of
course, it actually /is/ necessary to pass "this" around, because
that's where the mutex is.

There's lots of other ways of doing it, of course. Like I said, it's a
programmers' choice, and you can have as much or as little granularity
with what the share includes as you choose.
Sep 13 2007
prev sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Sean Kelly <sean f4.ca> wrote:

 What if I only plan to use the class within a single thread and don't
 want to pay for the cost of a lock?


I should have added another answer...

Just because a "shared" storage class exists, doesn't mean you have to
use it. If you don't, you'll get thread-unsafe code, but if you don't
care about that, hey ho!

Of course, then you'll have to make everything non-const or it
probably won't compile!
Sep 13 2007
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Janice Caron" wrote

 - - - - you still need to be careful - - - -

 There is no magic bullet to thread-safety. This mechanism does ensure
 that multiple threads won't try to access the same variable at the
 same time, but what it /won't/ do is prevent deadlocks. It's also
 still possible to screw up. For instance - you cannot get a write lock
 if you already hold a lock...

 scope a = readable(x);
 scope b = writable(x); /* Error - b is already locked by this thread */


magic bullet time:

At least for this case, you could put debug-only code in the core 
functionality of the locking code that checks to see if the thread already 
has the object locked.  If it does, throw an exception.

This won't help in the case where two threads deadlock, but there may be 
ways to put debug code in to check those also:

if(object a is locked by thread x && thread x is waiting for object b && I 
have object b locked)
  throw new DeadlockException();

In the release version, the system runs at full speed because this overhead 
is gone.

-Steve
Sep 13 2007
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Steven Schveighoffer" wrote

 This won't help in the case where two threads deadlock, but there may be 
 ways to put debug code in to check those also:

 if(object a is locked by thread x && thread x is waiting for object b && I 
 have object b locked)
  throw new DeadlockException();


Oops, that doesn't work in the case of more than 2 threads and more than 2 
objects.  Nevermind...  magic bullet is a myth :)  but the first one 
definitely will work.

-Steve
Sep 13 2007
prev sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 scope a = readable(x);
 scope b = writable(x); /* Error - b is already locked by this thread */


 magic bullet time:

 At least for this case, you could put debug-only code in the core
 functionality of the locking code that checks to see if the thread already
 has the object locked.  If it does, throw an exception.


That's feasible, but non-trivial. Under the hood, there would have to
have a variable for the thread ID. The runtime cost would be an extra
atomic compare-and-set operation.

But worse, either the thread ID variable would be unused in release
mode, wasting space, or it would be absent in release mode, making the
ABI different, and hence making release and debug object files
mutually unlinkable. Tough choice!
Sep 13 2007
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Janice Caron" wrote

 But worse, either the thread ID variable would be unused in release
 mode, wasting space, or it would be absent in release mode, making the
 ABI different, and hence making release and debug object files
 mutually unlinkable. Tough choice!


Hm... actually, I realize that this isn't the worst part.  The worst part is 
that if you store which threads have a shared object read-locked, then this 
becomes a LIST of threads, since multiple threads can read-lock, and so 
instead of a reference count, you have a dynamic array.  UGH!

nevermind (puts magic bullet back in pocket)

-Steve
Sep 13 2007
prev sibling next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Janice Caron wrote:

 ... - - - - conclusion - - - -
 
 This is a viable, threadsafe alternative to both intransitive const
 and logical const.
 
 It allows us to build all of the real-world use-cases that have been
 suggested a need for intransitive const or logical const.
 
 You get three new keywords:
 * shared
 * readable
 * writable
 
 You have to learn a new discipline to use these features, but it's not that
hard


This proposal seems to me basically like 'synchronized' on steroids. So 
why not just use the word 'synchronized' instead of 'shared'?

If you'll allow me to just give a summary of the proposal, it does two 
main things -- first, it extends 'synchronized'(aka 'shared'), allowing 
you to apply it to values and aggregates.  And secondly it refines the 
notion of synchronized to include a distinction between read-only locks 
and read-write locks.

Your readable/writeable wrappers do indeed sound a lot like RAII mutexes 
I've seen in C++ threading libs.  I disagree that D's lack of operator-> 
makes putting 2-3 new keywords in the language a "cool solution".  A 
cooler solution would be to make D capable of something similar to 
overloading ->.

The readable/writeable distinction seems like it would be a useful 
capability for the current synchronized methods too.  Also the ability 
to apply synchronized on the instance side rather than definition side 
is interesting.

But to me, more mutexes doesn't really seem like the answer to our 
multi-threading problems, since as you point out, it's still really 
trivial to get deadlocks and such.  It seems like this is just and 
expansion on sugary muxtes rather than something that makes 
multithreaded programming fundamentally less error-prone.

It also seems like you could nearly get the same functionality out of 
some kind of smart pointer.
Shared!(T) x; -- a T but no direct access to T or its members is allowed
Readable!(Shared!(T))(x),
Writeable!(Shared!(T))(x) -- RAII types, allowing access to x and its 
members

If it isn't possible to make such a smart pointer in D right now (and it 
isn't) that's what should be fixed.  Then this proposal could be 
implemented as a library.

I just don't see this as a viable replacement for 'const' or 'pure'. 
Though, maybe your purpose is more to provide something that satisfies 
Walter's threading requirements, leaving const free to be a more C++-ish 
thing.  It does seem like a nice way to do mutex programming though.

--bb
Sep 13 2007
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Bill Baxter <dnewsgroup billbaxter.com> wrote:

 why not just use the word 'synchronized' instead of 'shared'?


Mainly because synchronized is already used. For the record,
synchronized T x;

does compile. However, since it is completely equivalent to

 synchrnonized
 {
     T x;
 }

it is completely useless for variable declaration!

A second reason is that it's too damn long. "sync" would be nicer.

A third reason is that it's spelt the American way. I spell it
"synchronised". (That's not a real argument against, I guess, but it
is annoying).

Anyway, I don't get to choose - Walter would have that privelege. I
can only suggest.





 Your readable/writeable wrappers do indeed sound a lot like RAII mutexes
 I've seen in C++ threading libs.


That's almost exactly what they are.



 But to me, more mutexes doesn't really seem like the answer to our
 multi-threading problems, since as you point out, it's still really
 trivial to get deadlocks and such.


Yeah, but hang on. There is /no/ perfect solution. It is /impossible/
to eliminate deadlocks at compile-time.

Multithreading is hard. There's no way round it. But at least we can
make it easy to have everything properly mutex-locked to that nothing
tramples on memory it shouldn't.




 It seems like this is just and
 expansion on sugary muxtes rather than something that makes
 multithreaded programming fundamentally less error-prone.


It's both. It encapsulates a read/write mutex with the thing being
protected, and it employs RAII to ensure mutex unlocking. So, yes, you
could say it's "just" mutexes.

But I would certainly argue that it makes multithreaded programming
less error-prone. (Not sure what "fundamentally" means in this
context). I certainly do use constructs like this in my own code in
C++, and because of that, I can be confident that I'm thread-safe.



 It also seems like you could nearly get the same functionality out of
 some kind of smart pointer.
 Shared!(T) x; -- a T but no direct access to T or its members is allowed
 Readable!(Shared!(T))(x),
 Writeable!(Shared!(T))(x) -- RAII types, allowing access to x and its
 members


Almost. In fact, they're Shared!(T), Readable!(T) and Writeable!(T).
At least, that's how I implemented them in C++.

Only... with nicer syntax.



 If it isn't possible to make such a smart pointer in D right now (and it
 isn't) that's what should be fixed.  Then this proposal could be
 implemented as a library.


No it couldn't. Not in D. Would you care to guess why not?

*Because const is transitive*

There is no way you could put a read/write mutex (which itself needs
to be mutable) into a const structure unless it's done at a language
level, because Walter won't let you.



 I just don't see this as a viable replacement for 'const' or 'pure'.


That's good, because it isn't.



 Though, maybe your purpose is more to provide something that satisfies
 Walter's threading requirements, leaving const free to be a more C++-ish
 thing.


No, const would still be a D-ish thing. If it were a C-ish thing, it
wouldn't be transitive.
Sep 13 2007
next sibling parent Matti Niemenmaa <see_signature for.real.address> writes:
Janice Caron wrote:

 A third reason is that it's spelt the American way. I spell it
 "synchronised". (That's not a real argument against, I guess, but it
 is annoying).


"-ize" is not solely American, see http://en.wikipedia.org/wiki/Oxford_spelling
and http://www.askoxford.com/asktheexperts/faq/aboutspelling/ize

-- 
E-mail address: matti.niemenmaa+news, domain is iki (DOT) fi
Sep 13 2007
prev sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Janice Caron wrote:

 

 If it isn't possible to make such a smart pointer in D right now (and it
 isn't) that's what should be fixed.  Then this proposal could be
 implemented as a library.


 
 No it couldn't. Not in D. Would you care to guess why not?
 
 *Because const is transitive*
 
 There is no way you could put a read/write mutex (which itself needs
 to be mutable) into a const structure unless it's done at a language
 level, because Walter won't let you.
 
 


Erm, you could always cast away the constness of the mutex, so I think 
it's possible. (even if not ideal)

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Sep 13 2007
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/13/07, Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 Erm, you could always cast away the constness of the mutex, so I think
 it's possible. (even if not ideal)


You're right. I hadn't thought of that.

And un-consting a mutex is probably the one place where it's
absolutely safe to do so, no matter that other threads might be
sharing it! Hot dang! That's brilliant!

OK - so it /could/ be implemented as a library function then.

You'd have to unconst not just the mutex, but also the data that the
mutex was protecting. But that's OK too - it's mutex protected. That
could all be built into the smart pointer.

...what a pity D doesn't do smart pointers. Should we start a thread
on that? I must assume that it's been discussed before.

So it would be:

struct A
{
    int x;
}

Shared!(A) shared_a;
{
    scope a = new Readable!(A)(shared_a);
    int n = a.dereference.x;
}
{
    scope a = new Writeable!(A)(shared_a);
    a.derefence.x = 4;
}

There has a be a better syntax than a.dereference.x though, even if we
don't have operator arrow.

Anyway - I think you've cracked it. Nice one!
Sep 13 2007
next sibling parent reply Sean Kelly <sean f4.ca> writes:
Janice Caron wrote:

 
 ...what a pity D doesn't do smart pointers. Should we start a thread
 on that? I must assume that it's been discussed before.


Well be able to do that in 2.0 once struct copy semantics and the like 
are added.  Though the lack of a dot operator overload may complicate 
the syntax a tad.


Sean
Sep 13 2007
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Sean Kelly wrote:

 Though the lack of a dot operator overload may complicate 
 the syntax a tad.


Isn't that what 'alias this' would be for?
Sep 13 2007
parent reply Sean Kelly <sean f4.ca> writes:
Frits van Bommel wrote:

 Sean Kelly wrote:

 Though the lack of a dot operator overload may complicate the syntax a 
 tad.


 
 Isn't that what 'alias this' would be for?


Hrm... so something like this?

     struct SmartPtr( T ) {
         T* val;
         static if( is( T == class ) ||
                    is( T == struct ) )
         alias val this;

         void opAssign( T* v ) {
             val = v;
         }
     }

     struct S {
         void foo() {}
     }

     SmartPtr!(S) p = new S;
     p.foo();


Seems like it would work, huh :-)  I hadn't really thought about 'alias 
this' in this context.


Sean
Sep 13 2007
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Sean Kelly wrote:

 Frits van Bommel wrote:

 Sean Kelly wrote:

 Though the lack of a dot operator overload may complicate the syntax 
 a tad.


 Isn't that what 'alias this' would be for?


 
 Hrm... so something like this?
 
     struct SmartPtr( T ) {
         T* val;
         static if( is( T == class ) ||
                    is( T == struct ) )
         alias val this;
 
         void opAssign( T* v ) {
             val = v;
         }
     }
 
     struct S {
         void foo() {}
     }
 
     SmartPtr!(S) p = new S;
     p.foo();
 
 
 Seems like it would work, huh :-)  I hadn't really thought about 'alias 
 this' in this context.


That is interesting.  But if inheritance is such a great way to 
implement smart pointers, then why isn't it regularly used to implement 
smart pointers in C++?

oh wait... you can't inherit from a pointer in C++.
Or dynamically change your base object.

With copy constructors and destructors this could be a very slick way to 
do smart pointers.  Nice!

--bb
Sep 13 2007
prev sibling next sibling parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Janice Caron wrote:

 
 ....what a pity D doesn't do smart pointers. Should we start a thread
 on that? I must assume that it's been discussed before.
 


Whoa take it easy. I actually like to keep up with the newsgroups, but 
there has been lots of posts lately, and I also have a lot of other 
stuff to do. (and many others should be in the same situation)
Besides, I'm waiting for the videos of the conference to be posted to 
know more about upcoming features and not discuss stuff that has already 
been discussed. In particular the opImplicitCast seems that it may allow 
doing stuff like smart pointers and whatnot.


 Anyway - I think you've cracked it. Nice one!


I have? Well, I actually think other things I (and others) have said are 
far more important (that not having tail const/invariant will suck 
terribly, and that pure functions should be used for multithreading 
safety instead of const/invariant, which was not designed for that).
But I think this round of discussion is coming to an end. We'll have to 
wait until the Inner Circle finishes their next batch of deliberations 
and changes, and presents them to the NG, so that another near-futile 
discussion begins. Oh the joy of the D design process... ^^


-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Sep 13 2007
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Janice Caron" <caron800 googlemail.com> wrote in message 
news:mailman.216.1189723099.16939.digitalmars-d puremagic.com...

 On 9/13/07, Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 Erm, you could always cast away the constness of the mutex, so I think
 it's possible. (even if not ideal)


 You're right. I hadn't thought of that.

 And un-consting a mutex is probably the one place where it's
 absolutely safe to do so, no matter that other threads might be
 sharing it! Hot dang! That's brilliant!


Hm.. The spec says that the result of casting away const and then modifying 
the variable is "undefined."  I take this to mean that the compiler may do 
some optimizations based on the fact that you have a const object, and then 
your code might not behave as you think in some future version of D :(

Although I think it has been suggested by Walter that casting away const is 
acceptable if "you know what you're doing":

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=58383

-Steve
Sep 14 2007
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/14/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 And un-consting a mutex is probably the one place where it's
 absolutely safe to do so, no matter that other threads might be
 sharing it! Hot dang! That's brilliant!


 Hm.. The spec says that the result of casting away const and then modifying
 the variable is "undefined."  I take this to mean that the compiler may do
 some optimizations based on the fact that you have a const object, and then
 your code might not behave as you think in some future version of D :(

 Although I think it has been suggested by Walter that casting away const is
 acceptable if "you know what you're doing":


Well, Walter's only mentioned one problem so far, which is that of an
object which the compiler things is const being shared between
multiple threads. Though strictly speaking overriding const is
undefined, we do, in fact, know what would happen. Thread A would make
a modification, and then thread B would see the change. In some cases
(eg. inserting into a linked list), a thread switch partway through
the change would be disasterous. BUT - if you can ensure that no
matter what thread A does, thread B will never see an invalid state,
then you're sorted. So, it's not undefined because "it might not
work", it's undefined because a particular bad thing might happen. The
way I see it, so long as you're sure that that particular bad thing
won't happen, then either (a) it's OK, or (b) there are other
consideration we haven't been told about.

Are there other things that can go wrong we haven't taken into
account? Who knows.
Sep 14 2007
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Janice Caron" wrote

 On 9/14/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 And un-consting a mutex is probably the one place where it's
 absolutely safe to do so, no matter that other threads might be
 sharing it! Hot dang! That's brilliant!


 Hm.. The spec says that the result of casting away const and then 
 modifying
 the variable is "undefined."  I take this to mean that the compiler may 
 do
 some optimizations based on the fact that you have a const object, and 
 then
 your code might not behave as you think in some future version of D :(

 Although I think it has been suggested by Walter that casting away const 
 is
 acceptable if "you know what you're doing":


 Well, Walter's only mentioned one problem so far, which is that of an
 object which the compiler things is const being shared between
 multiple threads. Though strictly speaking overriding const is
 undefined, we do, in fact, know what would happen. Thread A would make
 a modification, and then thread B would see the change.


That sounds like a definition :)

To me, undefined means "I can't tell you what happens, my compiler is free 
to make assumtions that you cannot anticipate."  What you are describing is 
more like "not recommended".

-Steve
Sep 14 2007
prev sibling parent Jason House <jason.james.house gmail.com> writes:
Janice Caron wrote:

 - - - - conclusion - - - -
 
 This is a viable, threadsafe alternative to both intransitive const
 and logical const.


I like your idea, but I have to disagree with this.  The proposal itself 
still needs some kind of const concept.  How do you enforce something 
which has a read lock is not written to?

I think a proposal that combines this and the latest Walter has 
suggested for const could resolve a lot the current issues that have 
been raised lately.

It sounds to me that if a class contains a shared member that the shared 
member would remain non-const, even if the class reference becomes const 
or invariant.

Other observations:
1. Having a read lock on a variable sounds equivalent to having a scope 
invariant variable.
2. Having a write lock forces only one writer, a concept that is not 
covered by Walter's const proposal.

Since I haven't really seen any motivating use cases for how the new 
const would be used and I don't fully appreciate how Walter's proposed 
design would truly satisfy the requirements, I'll stop my speculative 
language design here.
Sep 18 2007