Since we're talking about synchronization again, I think this is a problem that should be addressed.

As a general rule, we should make sure that pointers to variables of a synchronized class do not escape the (synchronized) member functions. Otherwise someone else will have non-synchronized access to them.

The problem is defining what is protected by the lock. Well, I don't think it's really a problem. Anything not explicitly declared shared should be protected by the lock. For instance, if you have this field:

	shared(int)*[] data;

then the 'int' part is shared and can be visible from elsewhere, but any reference to the '*[]' part should be accessible only through synchronization and not allowed to escape outside a synchronization block (or a synchronized function).

So let's take a look at an example. I've made a class with a simple data structure with some data manipulation functions to evaluate what various designs could allow and disallow:

	synchronized class A {
		shared(int)*[] data;

		void initialize() {
			data = new shared(int)*[10];
			foreach (d; data) {
				d = new shared(int);
				*d = random();
			}
		}

		void sortByPointer() {
			sort!"a > b"(data);
		}

		void sortByInteger() {
			sort!"*a > *b"(data);
		}

		shared(int)* getOneOfThem() {
			return data[0];
			// ok: *data[0] is not protected by the lock
			// so it can escape.
		}
	}

How can this work for sort? Sort receives an argument of type shared(int)*[], but how can it guaranty that no pointer will escape the function?

I'd like to have a way to call sort safely, but I'm under the impression that it's not possible without adding a lot of things to the type system (lent with ownership or scope restrictions). Any idea?


-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/

Le 2010-01-30 ? 9:57, Michel Fortin a ?crit :

> Since we're talking about synchronization again, I think this is a problem that should be addressed.

(Replying to myself)

Robert's comment in the other thread makes me realize I've skipped over something important in my previous message: fields inside a synchronized object shouldn't 'shared'. Despite being usable from many threads due to synchronization, they behave much more like thread-local fields where the thread they belong to changes depending on who holds the lock.

So what I'm proposing is that a synchronized object contains non-shared fields unless explicitly marked shared. Those fields wouldn't be accessible from anywhere except inside a synchronized block. Inside a synchronized block they are accessible and treated as thread-local.

The only thing lacking is a way to avoid them from escaping when passing them to functions. If we deem it necessary, we could add a type modifier for that (although it probably won't enough by itself).

But as long as the programmer doesn't let those references escape, things will run smoothly. I think having fined-grained controls over what is protected by the lock and what will use atomic operations is a necessity if you want to achieve decent performances.

More examples:

	synchronized class SyncObject {
		shared(int)*[] data;
		// only the last part can be shared,
		// the rest is protected by the object's lock.

		SyncObject next;
		// the reference is protected by the object's lock,
		// but the object itself can be shared since it is synchronized.

		char[] buffer;
		// the whole thing is protected by the object's lock.

		SomeStruct s;
		// s.a is protected by the object's lock.
		// s.b is shared as per struct's definition.
		// s.test() is callable under the object's lock.
	}

	struct SomeStruct {
		int a;
		shared(int) b;

		void test() {
			a += 1;
			b += 1; // this one is always atomic.
		}
	}


-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/

On Sat, 30 Jan 2010 15:30:04 -0500, Michel Fortin <michel.fortin at michelf.com> wrote:

> Le 2010-01-30 ? 9:57, Michel Fortin a ?crit :
>
>> Since we're talking about synchronization again, I think this is a problem that should be addressed.
>
> (Replying to myself)
>
> Robert's comment in the other thread makes me realize I've skipped over something important in my previous message: fields inside a synchronized object shouldn't 'shared'. Despite being usable from many threads due to synchronization, they behave much more like thread-local fields where the thread they belong to changes depending on who holds the lock.

I assume this is only for value types and not references.

> So what I'm proposing is that a synchronized object contains non-shared fields unless explicitly marked shared. Those fields wouldn't be accessible from anywhere except inside a synchronized block. Inside a synchronized block they are accessible and treated as thread-local.

Except shared functions can return thread-local objects, which will cause escapes in the model. And class instance A could give references to class instance B, resulting in an escape.

> The only thing lacking is a way to avoid them from escaping when passing them to functions. If we deem it necessary, we could add a type modifier for that (although it probably won't enough by itself).

The type modifier you are looking for is called 'owned'. Bartosz went into
some detail of it on his blog. From a runtime perspective, owned objects
are all protected by a common mutex, and are therefore shared objects.
 From a compile time perspective, it provides the ability to optimize away
some recursive locks, etc.

> But as long as the programmer doesn't let those references escape, things will run smoothly. I think having fined-grained controls over what is protected by the lock and what will use atomic operations is a necessity if you want to achieve decent performances.
>
> More examples:
>
> 	synchronized class SyncObject {
> 		shared(int)*[] data;
> 		// only the last part can be shared,
> 		// the rest is protected by the object's lock.
>
> 		SyncObject next;
> 		// the reference is protected by the object's lock,
> 		// but the object itself can be shared since it is synchronized.
>
> 		char[] buffer;
> 		// the whole thing is protected by the object's lock.
>
> 		SomeStruct s;
> 		// s.a is protected by the object's lock.
> 		// s.b is shared as per struct's definition.
> 		// s.test() is callable under the object's lock.
> 	}
>
> 	struct SomeStruct {
> 		int a;
> 		shared(int) b;
>
> 		void test() {
> 			a += 1;
> 			b += 1; // this one is always atomic.
> 		}
> 	}
>
>

Le 2010-01-30 ? 17:25, Robert Jacques a ?crit :

> On Sat, 30 Jan 2010 15:30:04 -0500, Michel Fortin <michel.fortin at michelf.com> wrote:
> 
>> Robert's comment in the other thread makes me realize I've skipped over something important in my previous message: fields inside a synchronized object shouldn't 'shared'. Despite being usable from many threads due to synchronization, they behave much more like thread-local fields where the thread they belong to changes depending on who holds the lock.
> 
> I assume this is only for value types and not references.

This applies to both value types and reference types. The idea is that they aren't 'shared', but they are also not accessible at all outside of a synchronized block... More below.


>> The only thing lacking is a way to avoid them from escaping when passing them to functions. If we deem it necessary, we could add a type modifier for that (although it probably won't enough by itself).
> 
> The type modifier you are looking for is called 'owned'. Bartosz went into some detail of it on his blog. From a runtime perspective, owned objects are all protected by a common mutex, and are therefore shared objects. From a compile time perspective, it provides the ability to optimize away some recursive locks, etc.

There are multiple ways to ensure correctness at this level. Either you propagate the owner with the type of the variable, as Bartosz proposed, or you propagate assignment constrains as I suggested even before that when talking about 'scope' with Andrei on the forum.

But...

The thing is that I'm trying to make a best effort to have something with reasonable performance and simplicity without introducing a type modifier. Andrei and Walter aren't too keen on adding a type modifier, so I think it's a good idea to push a concept without one as far as possible.

I'm perfectly aware that without adding proper support in the type system there will always be loopholes. I think having these loopholes is a more acceptable solution than forcing all referenced data to be shared and use atomic operations (as Andrei suggested some time ago).

For instance, if your class provides a synchronized interface to a tree data structure, you need synchronized to affect the whole tree. Using atomic operations everywhere in the tree is not going to be acceptable. Not only it'll give you poor performance, but it also doesn't add any safety: if somehow a pointer escapes and someone gains access to some part of the tree without holding the lock, you'll get a race in the program's logic because the algorithm manipulating the tree under the lock doesn't expect that.

So either the type system enforce that some variables are accessed only through their lock, or it lets the programmer in charge of doing that.

-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/

On Sat, 30 Jan 2010 18:25:33 -0500, Michel Fortin <michel.fortin at michelf.com> wrote:
> Le 2010-01-30 ? 17:25, Robert Jacques a ?crit :
>
>> On Sat, 30 Jan 2010 15:30:04 -0500, Michel Fortin <michel.fortin at michelf.com> wrote:
>>
>>> Robert's comment in the other thread makes me realize I've skipped over something important in my previous message: fields inside a synchronized object shouldn't 'shared'. Despite being usable from many threads due to synchronization, they behave much more like thread-local fields where the thread they belong to changes depending on who holds the lock.
>>
>> I assume this is only for value types and not references.
>
> This applies to both value types and reference types. The idea is that they aren't 'shared', but they are also not accessible at all outside of a synchronized block... More below.
>
>
>>> The only thing lacking is a way to avoid them from escaping when passing them to functions. If we deem it necessary, we could add a type modifier for that (although it probably won't enough by itself).
>>
>> The type modifier you are looking for is called 'owned'. Bartosz went into some detail of it on his blog. From a runtime perspective, owned objects are all protected by a common mutex, and are therefore shared objects. From a compile time perspective, it provides the ability to optimize away some recursive locks, etc.
>
> There are multiple ways to ensure correctness at this level. Either you propagate the owner with the type of the variable, as Bartosz proposed, or you propagate assignment constrains as I suggested even before that when talking about 'scope' with Andrei on the forum.
>
> But...
>
> The thing is that I'm trying to make a best effort to have something with reasonable performance and simplicity without introducing a type modifier. Andrei and Walter aren't too keen on adding a type modifier, so I think it's a good idea to push a concept without one as far as possible.
>
> I'm perfectly aware that without adding proper support in the type system there will always be loopholes. I think having these loopholes is a more acceptable solution than forcing all referenced data to be shared and use atomic operations (as Andrei suggested some time ago).
>
> For instance, if your class provides a synchronized interface to a tree data structure, you need synchronized to affect the whole tree. Using atomic operations everywhere in the tree is not going to be acceptable. Not only it'll give you poor performance, but it also doesn't add any safety: if somehow a pointer escapes and someone gains access to some part of the tree without holding the lock, you'll get a race in the program's logic because the algorithm manipulating the tree under the lock doesn't expect that.
>
> So either the type system enforce that some variables are accessed only through their lock, or it lets the programmer in charge of doing that.

I understand your concerns and share them. It's why I've supported and proposed different ownership type systems that address these issues. The problem is that your proposal is effectively re-creating either a lent or owned type poorly. At this point, since we are not going to get ownership types, I'd much rather have something safe and allow the gurus to cast stuff away as needed then to have a situation where there are loop-holes you could drive a Mac truck through. Honestly, I've read enough horror stories of threading gurus getting it wrong and of software killing people to prefer being safe to being sorry.

On that note, although I heard there were problems with owned/lent/unique, I never heard exactly what they were. Does anyone know what the particular issues were?

Le 2010-01-31 ? 0:54, Robert Jacques a ?crit :

> I understand your concerns and share them. It's why I've supported and proposed different ownership type systems that address these issues. The problem is that your proposal is effectively re-creating either a lent or owned type poorly. At this point, since we are not going to get ownership types, I'd much rather have something safe and allow the gurus to cast stuff away as needed then to have a situation where there are loop-holes you could drive a Mac truck through. Honestly, I've read enough horror stories of threading gurus getting it wrong and of software killing people to prefer being safe to being sorry.

We have to strike a balance somewhere. We can design something simple, safe, and unusable; we can design something complex, safe, and usable; or we can design something simple, not entirely safe, and usable. There's a compromise to draw somewhere. If you want full safety, the type system has to cope with it. If it doesn't you're restricting synchronization to small trivial cases.

I'm a proponent of full safety too, and it's easy to add safety to my proposal: just add 'lent'. Well, adding 'lent' isn't necessarily easy, but it's all you need to plug the hole in my proposal.


> On that note, although I heard there were problems with owned/lent/unique, I never heard exactly what they were. Does anyone know what the particular issues were?

I think in Bartosz terminology 'owned' is a type modifier meant to say that some variable is protected by a particular mutex. 'owned' should be see as 'owned by X', where X is the particular mutex protecting a variable. Owned is a parametrized type modifier.

In my proposal, all non-shared fields in a class are implicitly owned by the class while 'shared' variable are not owned.

What 'lent' means is that you temporarily give access to a variable to a function. No reference can escape from this variable beyond the lifetime of the function. In general you need to propagate the owner's information with lent too. For instance if you're implementing a swap function, you must ensure the owner of the data referenced by the two swapped values is the same.

Something 'unique' is accessible through only one reference in the whole program, it is guarantied to have no aliasing. With 'lent' you can lend a unique reference to a function: you know once it returns your reference is still unique. As long as this 'unique' property holds, you can safely *move* the reference between threads. As long as the unique reference is kept thread-local you can access it without atomic operations or locks. 'unique' can be seen as a temporary state as you can safely move it to immutable, mutable, shared, etc.

Andrei wants to implement unique as a template, but it'll be very limited without 'lent'. If I remember well, there's no general Unique template, just a UniqueArray for arrays of primitive types. Arrays of structs would allow taking the address of struct members and create aliasing.


-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/

On Sun, 31 Jan 2010 07:51:58 -0500, Michel Fortin <michel.fortin at michelf.com> wrote:
> Le 2010-01-31 ? 0:54, Robert Jacques a ?crit :
>
>> I understand your concerns and share them. It's why I've supported and proposed different ownership type systems that address these issues. The problem is that your proposal is effectively re-creating either a lent or owned type poorly. At this point, since we are not going to get ownership types, I'd much rather have something safe and allow the gurus to cast stuff away as needed then to have a situation where there are loop-holes you could drive a Mac truck through. Honestly, I've read enough horror stories of threading gurus getting it wrong and of software killing people to prefer being safe to being sorry.
>
> We have to strike a balance somewhere. We can design something simple, safe, and unusable; we can design something complex, safe, and usable; or we can design something simple, not entirely safe, and usable. There's a compromise to draw somewhere. If you want full safety, the type system has to cope with it. If it doesn't you're restricting synchronization to small trivial cases.

First, I don't believe that their is any significant performance difference between your proposed method and the current simple and safe method. Indeed, both are prone to taking numerous recursive mutexes. At worst, simple/safe results in taking uncontested mutexes, which can be very cheap (i.e. thin-locks, etc).

Second, your proposed method, doesn't seem to address the two largest safety issues: two instances of the same class interacting with each other and the current module system. Also, it appears, at first reading, to have the same benefits and limitations as the scope keyword. Please feel free to elaborate on something if I've misunderstood.

Third, I would argue that a some-what safe system is just as unusable, if not more so, than a slow solution. Until you can legitimately take down the 'here be dragons' sign, you'll have all the problems of threading today. And even PhDs can't get shared-state threading right today. Which is why every single article/books/blog on concurrency says to avoid shared-state like the plague.

> I'm a proponent of full safety too, and it's easy to add safety to my proposal: just add 'lent'. Well, adding 'lent' isn't necessarily easy, but it's all you need to plug the hole in my proposal.

As I've pointed out above, there are several holes with your proposal (as I understand it). Simply, without banning assignment, which is unusable, or going to 'owned by X', you'll be left with some major flaws.

>> On that note, although I heard there were problems with owned/lent/unique, I never heard exactly what they were. Does anyone know what the particular issues were?
>
> I think in Bartosz terminology 'owned' is a type modifier meant to say that some variable is protected by a particular mutex. 'owned' should be see as 'owned by X', where X is the particular mutex protecting a variable. Owned is a parametrized type modifier.

Yes.

> In my proposal, all non-shared fields in a class are implicitly owned by the class while 'shared' variable are not owned.

This would require modification to the type system, i.e. the addition of owned to the language.

> What 'lent' means is that you temporarily give access to a variable to a function. No reference can escape from this variable beyond the lifetime of the function. In general you need to propagate the owner's information with lent too. For instance if you're implementing a swap function, you must ensure the owner of the data referenced by the two swapped values is the same.

Yes and no. Yes, a lent object isn't allowed to be kept by the callee, but ownership information isn't required to be propagated to achieve these guarantees. Indeed it can't be for several practical reasons (mostly to do with the build system and the combinatorial increase in types). As for your swap example, I'll say that giving a borrowed item to an unknown third party and not back to the original owner is very much a violation of the whole lend/borrow paradigm.

> Something 'unique' is accessible through only one reference in the whole program, it is guarantied to have no aliasing. With 'lent' you can lend a unique reference to a function: you know once it returns your reference is still unique. As long as this 'unique' property holds, you can safely *move* the reference between threads. As long as the unique reference is kept thread-local you can access it without atomic operations or locks. 'unique' can be seen as a temporary state as you can safely move it to immutable, mutable, shared, etc.
>
> Andrei wants to implement unique as a template, but it'll be very limited without 'lent'. If I remember well, there's no general Unique template, just a UniqueArray for arrays of primitive types. Arrays of structs would allow taking the address of struct members and create aliasing.

True.

On Sun, Jan 31, 2010 at 7:51 AM, Michel Fortin <michel.fortin at michelf.com>wrote: ...

>
> Something 'unique' is accessible through only one reference in the whole program, it is guarantied to have no aliasing. With 'lent' you can lend a unique reference to a function: you know once it returns your reference is still unique. As long as this 'unique' property holds, you can safely *move* the reference between threads. As long as the unique reference is kept thread-local you can access it without atomic operations or locks. 'unique' can be seen as a temporary state as you can safely move it to immutable, mutable, shared, etc.
>
> Andrei wants to implement unique as a template, but it'll be very limited without 'lent'. If I remember well, there's no general Unique template, just a UniqueArray for arrays of primitive types. Arrays of structs would allow taking the address of struct members and create aliasing.
>

I want to point out that this is only true if there is a memory barrier at the point of lending.  If object X belongs uniquely to thread 1, and it gets lent to thread 2, a memory barrier should happen at this point.  There are several cases where you can get hurt if this is not done:

1. The object might have been owned by thread 2, then given to thread 1, which modified it, then returned to thread 2.  In this case, the second transfer is problematic because there might be a cached copy of the original in thread 2's L1 or L2 cache.

2. The object might have been in the same cache line with another object that was modified, causing unintentional caching, and thus snapshotting a previous version of the object's state.

3. Some other code might have fiddled with the object even though it is 'unique' -- for example, the global garbage collector might have been run by thread 2, causing thread 2 to "see" a bunch of things that thread 1 thinks it uniquely owns.  This is going to be garbage collector design dependent, e.g. the GC might always do a memory barrier just before returning control to the user, in which case, no problem.

The unique concept is a good thing but care must be taken -- I think Andrei's template version of the unique concept should be perfectly safe due to the fact that it does a copy.  It would be more efficient if a memory barrier could be used but that doesn't help with the analytical problem (making sure the old thread doesn't have a pointer stuck somewhere.)

I just wanted to knock down what I think is a dangerous idea that some people might have inferred from the discussion on 'unique' -- that thread X cannot have cached something if it was never 'seen' by thread X before.  For that matter, I'm not sure but without hard thread affinity, the CPU might have a cached version of something even if it the 'thread' never saw it because the last thread to run there saw it.  (Or does thread switching always incur a memory barrier -- I don't know much about how that is usually done.)

Kevin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/dmd-concurrency/attachments/20100131/f93830fa/attachment.htm>

Le 2010-01-31 ? 11:39, Robert Jacques a ?crit :

> On Sun, 31 Jan 2010 07:51:58 -0500, Michel Fortin <michel.fortin at michelf.com> wrote:
>> We have to strike a balance somewhere. We can design something simple, safe, and unusable; we can design something complex, safe, and usable; or we can design something simple, not entirely safe, and usable. There's a compromise to draw somewhere. If you want full safety, the type system has to cope with it. If it doesn't you're restricting synchronization to small trivial cases.
> 
> First, I don't believe that their is any significant performance difference between your proposed method and the current simple and safe method. Indeed, both are prone to taking numerous recursive mutexes. At worst, simple/safe results in taking uncontested mutexes, which can be very cheap (i.e. thin-locks, etc).

I'm looking at the case where I have one object, thus one mutex, to protect a data structure. I think this is a pretty typical use case for synchronization. We probably aren't talking about the same thing.

Let's look a this from another angle.

I started this thread asking the question "What is protected by synchronization?". I think before looking for solutions we need to clearly identify the need. For instance, I think a lock need to easily protect a data structure like this one:

	struct Node(T) {
		Node* left;
		Node* right
		T value;
	}

	class TreeMap(T) {
		Node!(T)* root;
		...
	}

In the above case, no one should access access the content of the map (the whole tree) without holding the TreeMap's lock, otherwise races might ensue. Those races might happen at the cache-line level in the hardware, but could also happen algorithmic level if two threads try to manipulate the nodes at the same time.

This is the need. Can we agree this is a typical use case we want to address?

-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/

Le 2010-01-31 ? 11:39, Robert Jacques a ?crit :

> Third, I would argue that a some-what safe system is just as unusable, if not more so, than a slow solution. Until you can legitimately take down the 'here be dragons' sign, you'll have all the problems of threading today. And even PhDs can't get shared-state threading right today. Which is why every single article/books/blog on concurrency says to avoid shared-state like the plague.

Actually that's a very strong argument against having synchronization as a language primitive. Perhaps indeed if we can't make the synchronization primitives powerful enough to support the typical use case decently while keeping everything safe we should just remove synchronization from the language.


-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/