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
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 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)?

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

No idea how it is done, but it definitely works in C#. I use it a lot. For 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
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.

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 use it a lot in C# which has reentrant write locks. -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.

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


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.


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.


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)

obtain a write lock, then the caller must beware that another thread may have written /during/ the upgrade.

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 next sibling parent 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
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.


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, 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 "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.


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 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 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
prev sibling next sibling 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:
 

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

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 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
prev sibling 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 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
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 next 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 "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
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
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
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 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 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?

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 "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
prev sibling next sibling parent "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
prev sibling 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 next 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
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 next sibling parent "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
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 "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 "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
parent "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
prev sibling next sibling 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