Smalltalk › Squeak › Squeak VM

Where to get Monitor implementation based on primitives?

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

47 messages Options

123

Denis Kudriashov

Re: Where to get Monitor implementation based on primitives?

Hello.

I publish slice 17373.

I introduce LockOwnership class which implements VM primitives as:
- acquire
- tryAcquire
- release
(It comment saves copyright from CriticalSection)

Mutext uses it as ownership instance variable to implement critical methods correctly:
- critical:
- critical:ifLocked:
- critical:ifError:
- critical:ifCurtailed:

For the integration process old Mutex instance variables are not removed. So loading this code should not broke current Mutex instances. But when we integrate it Mutex will have only variable ownership.

If you look critical implementation you will understand why I not like semantic of primitives. it should be inverted in future. #acquire should return true when ownership is acquired right now.

Process>>terminate now detects waiting on LockOwnership and ask it to handle wait termination.Then LockOwnership inject right value into lock state variable. Such variables should be marked with special pragma
<lockAt: #ownershipVariableName tracksStateAt: 1> "index of local variable"
Method can contain mulpible pragmas to reference all ownerships in method. ReadWriteLock for example needs this.

2016-01-11 13:30 GMT+01:00 Henrik Johansen <[hidden email]>:

On 08 Jan 2016, at 4:25 , Ben Coman <[hidden email]> wrote:

On Fri, Jan 8, 2016 at 9:39 PM, Ben Coman <[hidden email]> wrote:
On Fri, Jan 8, 2016 at 5:42 PM, stephane ducasse
<[hidden email]> wrote:

I have a (stupid) question.
Is the code running without the primitives?
Are the code below the primitives correct?
I asked that because we can have 100 eyes and brains on the smalltalk level and far less on the VM primitive level.

Because:
1. Concurrency bugs can be subtle and the *exact* conditions can be
hard to reproduce for debugging. For example, the solution to a
couple of problems with Delay [1] [2] were solved by moving away from
Semaphore>>critical: to use signalling.

2. The in-image atomicity of determining whether a signal was actually
consumed or not during process suspension/termination is awkward. Its
seems hard to *really* know for sure it right (but I haven't looked in
depth into Denis' latest proposals.)

3. The existing in-image implementation of Semaphore>>critical messes
around in Process>>terminate in a *special* way that is not easy for
those 100 eyes to understand. For example, I personally am not
comfortable with understanding how the special Semaphore handling in
Process>>terminate works, but I can easily follow how
primitiveEnterCriticalSection just looking at the code [3].

Points 2 & 3 might possibly be addressed by having new primitiveWaitReturned
*always* return true, so if the process is terminated while waiting,
the assignment to signalConsumed doesn't occur...

critical: mutuallyExcludedBlock
   signalConsumed := false.
   [
       signalConsumed := self primitiveWaitReturned.
       blockValue := mutuallyExcludedBlock value
   ] ensure: [ signalConsumed ifTrue: [self signal] ].
   ^blockValue

where primitiveWait (https://git.io/vuDjd) is copied
and (just guessing) the marked line added...

primitiveWaitReturned
     | sema excessSignals activeProc inInterpreter |
     sema := self stackTop. "rcvr"
"==>>" self pop: argumentCount + 1 thenPush: objectMemory trueObject. "<<=="
    excessSignals := self fetchInteger: ExcessSignalsIndex ofObject: sema.
     excessSignals > 0
         ifTrue:
           [self storeInteger: ExcessSignalsIndex
                       ofObject: sema
                       withValue: excessSignals - 1]
         ifFalse:
           inInterpreter := instructionPointer >= objectMemory startOfMemory.
           activeProc := self activeProcess.
           self addLastLink: activeProc toList: sema.
           self transferTo: self wakeHighestPriority from: CSWait.
           self
forProcessPrimitiveReturnToExecutivePostContextSwitch: inInterpreter]

which I guess could be added quickly if Esteban could compile the
latest pharo-spur-vm ;)

cheers -ben

Won't work, there's no guarantee thread has actually ran and signalConsumed been assigned the primitive result after Semaphore resumed the waiting thread, before a higher priority thread runs and terminates it. (which is exactly the case handled by special code in #terminate)

Cheers,
Henry

Denis Kudriashov

Re: Where to get Monitor implementation based on primitives?

Eliot I found that there are no methods for simulation code (if it right name for it). So stepping over new primitives failed (which is infinite recursion for Pharo case)

Context>>doPrimitive: primitiveIndex method: meth receiver: aReceiver args: arguments

...

"Mutex>>primitiveEnterCriticalSection

Mutex>>primitiveTestAndSetOwnershipOfCriticalSection"

(primitiveIndex = 186 or: [primitiveIndex = 187]) ifTrue:

[| active effective |

active := Processor activeProcess.

effective := active effectiveProcess.

"active == effective"

value := primitiveIndex = 186

ifTrue: [aReceiver primitiveEnterCriticalSectionOnBehalfOf: effective]

ifFalse: [aReceiver primitiveTestAndSetOwnershipOfCriticalSectionOnBehalfOf: effective].

^(self isPrimFailToken: value)

ifTrue: [value]

ifFalse: [self push: value]].

How this methods should be implemented?

2016-01-11 13:59 GMT+01:00 Denis Kudriashov <[hidden email]>:

Hello.
I publish slice 17373.

I introduce LockOwnership class which implements VM primitives as:
- acquire
- tryAcquire
- release
(It comment saves copyright from CriticalSection)

Mutext uses it as ownership instance variable to implement critical methods correctly:
- critical:
- critical:ifLocked:
- critical:ifError:
- critical:ifCurtailed:

For the integration process old Mutex instance variables are not removed. So loading this code should not broke current Mutex instances. But when we integrate it Mutex will have only variable ownership.

If you look critical implementation you will understand why I not like semantic of primitives. it should be inverted in future. #acquire should return true when ownership is acquired right now.

Process>>terminate now detects waiting on LockOwnership and ask it to handle wait termination.Then LockOwnership inject right value into lock state variable. Such variables should be marked with special pragma
    <lockAt: #ownershipVariableName tracksStateAt: 1> "index of local variable"
Method can contain mulpible pragmas to reference all ownerships in method. ReadWriteLock for example needs this.

2016-01-11 13:30 GMT+01:00 Henrik Johansen <[hidden email]>:

On 08 Jan 2016, at 4:25 , Ben Coman <[hidden email]> wrote:

On Fri, Jan 8, 2016 at 9:39 PM, Ben Coman <[hidden email]> wrote:
On Fri, Jan 8, 2016 at 5:42 PM, stephane ducasse
<[hidden email]> wrote:

I have a (stupid) question.
Is the code running without the primitives?
Are the code below the primitives correct?
I asked that because we can have 100 eyes and brains on the smalltalk level and far less on the VM primitive level.

Because:
1. Concurrency bugs can be subtle and the *exact* conditions can be
hard to reproduce for debugging. For example, the solution to a
couple of problems with Delay [1] [2] were solved by moving away from
Semaphore>>critical: to use signalling.

2. The in-image atomicity of determining whether a signal was actually
consumed or not during process suspension/termination is awkward. Its
seems hard to *really* know for sure it right (but I haven't looked in
depth into Denis' latest proposals.)

3. The existing in-image implementation of Semaphore>>critical messes
around in Process>>terminate in a *special* way that is not easy for
those 100 eyes to understand. For example, I personally am not
comfortable with understanding how the special Semaphore handling in
Process>>terminate works, but I can easily follow how
primitiveEnterCriticalSection just looking at the code [3].

Points 2 & 3 might possibly be addressed by having new primitiveWaitReturned
*always* return true, so if the process is terminated while waiting,
the assignment to signalConsumed doesn't occur...

critical: mutuallyExcludedBlock
   signalConsumed := false.
   [
       signalConsumed := self primitiveWaitReturned.
       blockValue := mutuallyExcludedBlock value
   ] ensure: [ signalConsumed ifTrue: [self signal] ].
   ^blockValue

where primitiveWait (https://git.io/vuDjd) is copied
and (just guessing) the marked line added...

primitiveWaitReturned
     | sema excessSignals activeProc inInterpreter |
     sema := self stackTop. "rcvr"
"==>>" self pop: argumentCount + 1 thenPush: objectMemory trueObject. "<<=="
    excessSignals := self fetchInteger: ExcessSignalsIndex ofObject: sema.
     excessSignals > 0
         ifTrue:
           [self storeInteger: ExcessSignalsIndex
                       ofObject: sema
                       withValue: excessSignals - 1]
         ifFalse:
           inInterpreter := instructionPointer >= objectMemory startOfMemory.
           activeProc := self activeProcess.
           self addLastLink: activeProc toList: sema.
           self transferTo: self wakeHighestPriority from: CSWait.
           self
forProcessPrimitiveReturnToExecutivePostContextSwitch: inInterpreter]

which I guess could be added quickly if Esteban could compile the
latest pharo-spur-vm ;)

cheers -ben

Won't work, there's no guarantee thread has actually ran and signalConsumed been assigned the primitive result after Semaphore resumed the waiting thread, before a higher priority thread runs and terminates it. (which is exactly the case handled by special code in #terminate)

Cheers,
Henry

Denis Kudriashov

Re: Where to get Monitor implementation based on primitives?

I write it such way:

primitiveEnterCriticalSectionOnBehalfOf: activeProcess

[owningProcess ifNil:

[owningProcess := activeProcess.

^false].

owningProcess = activeProcess ifTrue:

[^true].

self addLast: Processor activeProcess.

activeProcess suspend] valueUnpreemptively

primitiveTestAndSetOwnershipOfCriticalSectionOnBehalfOf: activeProcess

[owningProcess ifNil:

[owningProcess := activeProcess.

^false].

owningProcess = activeProcess ifTrue: [^true].

^nil] valueUnpreemptively

2016-01-11 14:58 GMT+01:00 Denis Kudriashov <[hidden email]>:

Eliot I found that there are no methods for simulation code (if it right name for it). So stepping over new primitives failed (which is infinite recursion for Pharo case)

Context>>doPrimitive: primitiveIndex method: meth receiver: aReceiver args: arguments
...
"Mutex>>primitiveEnterCriticalSection
Mutex>>primitiveTestAndSetOwnershipOfCriticalSection"
(primitiveIndex = 186 or: [primitiveIndex = 187]) ifTrue:
[| active effective |
active := Processor activeProcess.
effective := active effectiveProcess.
"active == effective"
value := primitiveIndex = 186
ifTrue: [aReceiver primitiveEnterCriticalSectionOnBehalfOf: effective]
ifFalse: [aReceiver primitiveTestAndSetOwnershipOfCriticalSectionOnBehalfOf: effective].
^(self isPrimFailToken: value)
ifTrue: [value]
ifFalse: [self push: value]].

How this methods should be implemented?

2016-01-11 13:59 GMT+01:00 Denis Kudriashov <[hidden email]>:
Hello.
I publish slice 17373.

I introduce LockOwnership class which implements VM primitives as:
- acquire
- tryAcquire
- release
(It comment saves copyright from CriticalSection)

Mutext uses it as ownership instance variable to implement critical methods correctly:
- critical:
- critical:ifLocked:
- critical:ifError:
- critical:ifCurtailed:

For the integration process old Mutex instance variables are not removed. So loading this code should not broke current Mutex instances. But when we integrate it Mutex will have only variable ownership.

If you look critical implementation you will understand why I not like semantic of primitives. it should be inverted in future. #acquire should return true when ownership is acquired right now.

Process>>terminate now detects waiting on LockOwnership and ask it to handle wait termination.Then LockOwnership inject right value into lock state variable. Such variables should be marked with special pragma
    <lockAt: #ownershipVariableName tracksStateAt: 1> "index of local variable"
Method can contain mulpible pragmas to reference all ownerships in method. ReadWriteLock for example needs this.

2016-01-11 13:30 GMT+01:00 Henrik Johansen <[hidden email]>:

On 08 Jan 2016, at 4:25 , Ben Coman <[hidden email]> wrote:

On Fri, Jan 8, 2016 at 9:39 PM, Ben Coman <[hidden email]> wrote:
On Fri, Jan 8, 2016 at 5:42 PM, stephane ducasse
<[hidden email]> wrote:

I have a (stupid) question.
Is the code running without the primitives?
Are the code below the primitives correct?
I asked that because we can have 100 eyes and brains on the smalltalk level and far less on the VM primitive level.

Because:
1. Concurrency bugs can be subtle and the *exact* conditions can be
hard to reproduce for debugging. For example, the solution to a
couple of problems with Delay [1] [2] were solved by moving away from
Semaphore>>critical: to use signalling.

2. The in-image atomicity of determining whether a signal was actually
consumed or not during process suspension/termination is awkward. Its
seems hard to *really* know for sure it right (but I haven't looked in
depth into Denis' latest proposals.)

3. The existing in-image implementation of Semaphore>>critical messes
around in Process>>terminate in a *special* way that is not easy for
those 100 eyes to understand. For example, I personally am not
comfortable with understanding how the special Semaphore handling in
Process>>terminate works, but I can easily follow how
primitiveEnterCriticalSection just looking at the code [3].

Points 2 & 3 might possibly be addressed by having new primitiveWaitReturned
*always* return true, so if the process is terminated while waiting,
the assignment to signalConsumed doesn't occur...

critical: mutuallyExcludedBlock
   signalConsumed := false.
   [
       signalConsumed := self primitiveWaitReturned.
       blockValue := mutuallyExcludedBlock value
   ] ensure: [ signalConsumed ifTrue: [self signal] ].
   ^blockValue

where primitiveWait (https://git.io/vuDjd) is copied
and (just guessing) the marked line added...

primitiveWaitReturned
     | sema excessSignals activeProc inInterpreter |
     sema := self stackTop. "rcvr"
"==>>" self pop: argumentCount + 1 thenPush: objectMemory trueObject. "<<=="
    excessSignals := self fetchInteger: ExcessSignalsIndex ofObject: sema.
     excessSignals > 0
         ifTrue:
           [self storeInteger: ExcessSignalsIndex
                       ofObject: sema
                       withValue: excessSignals - 1]
         ifFalse:
           inInterpreter := instructionPointer >= objectMemory startOfMemory.
           activeProc := self activeProcess.
           self addLastLink: activeProc toList: sema.
           self transferTo: self wakeHighestPriority from: CSWait.
           self
forProcessPrimitiveReturnToExecutivePostContextSwitch: inInterpreter]

which I guess could be added quickly if Esteban could compile the
latest pharo-spur-vm ;)

cheers -ben

Won't work, there's no guarantee thread has actually ran and signalConsumed been assigned the primitive result after Semaphore resumed the waiting thread, before a higher priority thread runs and terminates it. (which is exactly the case handled by special code in #terminate)

Cheers,
Henry

Ben Coman

Re: Where to get Monitor implementation based on primitives?

In reply to this post by Denis Kudriashov

On Mon, Jan 11, 2016 at 9:58 PM, Denis Kudriashov <[hidden email]> wrote:

>
> Eliot I found that there are no methods for simulation code (if it right name for it). So stepping over new primitives failed (which is infinite recursion for Pharo case)
>
> Context>>doPrimitive: primitiveIndex method: meth receiver: aReceiver args: arguments
> ...
> "Mutex>>primitiveEnterCriticalSection
> Mutex>>primitiveTestAndSetOwnershipOfCriticalSection"
> (primitiveIndex = 186 or: [primitiveIndex = 187]) ifTrue:
> [| active effective |
> active := Processor activeProcess.
> effective := active effectiveProcess.
> "active == effective"
> value := primitiveIndex = 186
> ifTrue: [aReceiver primitiveEnterCriticalSectionOnBehalfOf: effective]
> ifFalse: [aReceiver primitiveTestAndSetOwnershipOfCriticalSectionOnBehalfOf: effective].
> ^(self isPrimFailToken: value)
> ifTrue: [value]
> ifFalse: [self push: value]].
>
> How this methods should be implemented?
>
> 2016-01-11 13:59 GMT+01:00 Denis Kudriashov <[hidden email]>:
>>
>> Hello.
>> I publish slice 17373.
>>
>> I introduce LockOwnership class which implements VM primitives as:
>> - acquire
>> - tryAcquire
>> - release
>> (It comment saves copyright from CriticalSection)

I don't think that is proper. The code is the same, just some names
have changed. I'll bet the primitives were funded by 3DICC too, so
credit where credit is due.
cheers -ben

Denis Kudriashov

Re: Where to get Monitor implementation based on primitives?

2016-01-11 17:47 GMT+01:00 Ben Coman <[hidden email]>:

>> (It comment saves copyright from CriticalSection)

I don't think that is proper. The code is the same, just some names
have changed. I'll bet the primitives were funded by 3DICC too, so
credit where credit is due.

But copyright is mentioned in class comment

Frank Shearar-3

Re: Where to get Monitor implementation based on primitives?

In reply to this post by Eliot Miranda-2

On 7 January 2016 at 17:12, Eliot Miranda <[hidden email]> wrote:

> Hi Denis, Hi Clément, Hi Frank,
>
> On Thu, Jan 7, 2016 at 5:34 AM, Clément Bera <[hidden email]> wrote:
>>
>> Hello,
>>
>> Eliot, please, you told me you had the code and Denis is interested.
>>
>> It uses 3 primitives for performance.
>
>
> Forgive the delay. I thought it proper to ask permission since the code was
> written while I was at Qwaq. I'm attaching the code in a fairly raw state,
> see the attached. The code is MIT, but copyright 3DICC.
>
> It is a plugin replacement for Squeak's Mutex, and with a little ingenuity
> could be a replacement for Squeak's Monitor. It is quicker because it uses
> three new primitives to manage entering a critical section and setting the
> owner, exiting the critical section and releasing the owner, and testing if
> a critical section, entering if the section is unowned. The use of the
> primitives means fewer block activations and ensure: blocks in entering and
> exiting the critical section, and that's the actual cause of the speed-up.
>
> You can benchmark the code as is. Here are some results on 32-bit Spur, on
> my 2.2GHz Core i7
>
> {Mutex new. Monitor new. CriticalSection new} collect:
> [:cs| | n |
> n := 0.
> [cs critical: [n := n + 1]. cs critical: [n := n + 1]. cs critical: [n := n
> + 1]. cs critical: [n := n + 1]. cs critical: [n := n + 1].
> cs critical: [n := n - 1]. cs critical: [n := n - 1]. cs critical: [n := n -
> 1]. cs critical: [n := n - 1]. cs critical: [n := n - 1].
> n ] bench]
>
> {Mutex new. Monitor new. CriticalSection new} collect:
> [:cs| | n |
> n := 0.
> cs class name, ' -> ',
> [cs critical: [n := n + 1]. cs critical: [n := n + 1]. cs critical: [n := n
> + 1]. cs critical: [n := n + 1]. cs critical: [n := n + 1].
> cs critical: [n := n - 1]. cs critical: [n := n - 1]. cs critical: [n := n -
> 1]. cs critical: [n := n - 1]. cs critical: [n := n - 1].
> n ] bench]
>
> #( 'Mutex -> 440,000 per second. 2.27 microseconds per run.'
> 'Monitor -> 688,000 per second. 1.45 microseconds per run.'
> 'CriticalSection -> 1,110,000 per second. 900 nanoseconds per run.')
>
> Replacement is probably trivial; rename Mutex to OldMutex, rename
> CriticalSection to Mutex, recompile. But there are lots of mutexes in the
> system and these are potentially owned. Transforming unowned ones is
> trivial, but transforming owned ones is, I think, impossible. But at least
> in my system there are no owned mutexes or monitors.
>
> Frank (or anyone else), would you be interested in creating a replacement
> for Squeak's Monitor based on CriticalSection?

It sounds like an interesting problem. I watched the thread unfold and
I'm still not massively clear on what is required though? (Apologies
for the delay in responding: my cup overfloweth at the moment, but
should resume normal levels in a month or so.)

frank

Ben Coman

Re: Where to get Monitor implementation based on primitives?

In reply to this post by Eliot Miranda-2

On Fri, Jan 8, 2016 at 1:20 AM, Eliot Miranda <[hidden email]> wrote:

>>
>> On Thu, Jan 7, 2016 at 5:34 AM, Clément Bera <[hidden email]> wrote:
>>>
>>> Eliot, please, you told me you had the code and Denis is interested.
>>> It uses 3 primitives for performance.
>>
>> Here are the two business methods:
>> CriticalSection methods for mutual exclusion
>> critical: aBlock
>> "Evaluate aBlock protected by the receiver."
>> ^self primitiveEnterCriticalSection
>> ifTrue: [aBlock value]
>> ifFalse: [aBlock ensure: [self primitiveExitCriticalSection]]
>>
>> critical: aBlock ifLocked: lockedBlock
>> "Answer the evaluation of aBlock protected by the receiver. If it is already in a critical
>> section on behalf of some other process answer the evaluation of lockedBlock."
>> ^self primitiveTestAndSetOwnershipOfCriticalSection
>> ifNil: [lockedBlock value]
>> ifNotNil:[:alreadyOwner|
>> alreadyOwner
>> ifTrue: [aBlock value]
>> ifFalse: [aBlock ensure: [self primitiveExitCriticalSection]]]
>>
>> and the primitives:
>> primitiveEnterCriticalSection
>> primitiveExitCriticalSection
>> primitiveTestAndSetOwnershipOfCriticalSection

Reading this vm code...

primitiveExitCriticalSection
| criticalSection owningProcessIndex owningProcess |
criticalSection := self stackTop. "rcvr"
owningProcessIndex := ExcessSignalsIndex.
(self isEmptyList: criticalSection)
ifTrue:
[objectMemory storePointerUnchecked: owningProcessIndex
ofObject: criticalSection
withValue: objectMemory nilObject]
ifFalse:
[owningProcess := self removeFirstLinkOfList: criticalSection.
objectMemory storePointerUnchecked: owningProcessIndex
ofObject: criticalSection
withValue: owningProcess.
self resume: owningProcess preemptedYieldingIf: preemptionYields]

I suspect a problem since it does not check it is the owningProcess
before setting owningProcess to nil. AFAIK, only the owning process
should be able to release the mutex. To demonstrate, evaluating the
following...

Transcript clear.
cs := CriticalSection new.
sync := Semaphore new.
b1 :=
[ Transcript crShow: '1A'.
cs primitiveEnterCriticalSection.
sync wait.
Transcript crShow: '1B'.
cs primitiveExitCriticalSection. ].
b2 :=
[ Transcript crShow: '2A'.
cs primitiveEnterCriticalSection.
Transcript crShow: '2B'.
cs primitiveExitCriticalSection. ].
b3 :=
[ Transcript crShow: '3A'.
cs primitiveExitCriticalSection.
cs primitiveEnterCriticalSection.
Transcript crShow: '3B'. ].
[ b1 newProcess resume.
b2 newProcess resume.
2 second wait.
sync signal. ] fork

correctly produces...
1A
2A
"pauses here"
1B
2B

but if the last forked block replaces b2 with b3...
[ b1 newProcess resume.
b3 newProcess resume.
2 second wait.
sync signal. ] fork

it produces incorrectly result...

1A
3A
3B
"pauses here"
1B

I believe the "cs primitiveExitCriticalSection" in b3 should raise an error.
Thus primitiveExitCriticalSection might be...

primitiveExitCriticalSection
argumentCount > 0
ifTrue:
[ criticalSection := self stackValue: 1. "rcvr"
activeProc := self stackTop ]
ifFalse:
[ criticalSection := self stackTop. "rcvr"
activeProc := self activeProcess ].
owningProcessIndex := ExcessSignalsIndex.
owningProcess := objectMemory fetchPointer: owningProcessIndex
ofObject: criticalSection.
owningProcess = activeProc ifFalse: self primitiveFail. "<==!!!"
(self isEmptyList: criticalSection)
ifTrue:
[ objectMemory
storePointerUnchecked: owningProcessIndex
ofObject: criticalSection
withValue: objectMemory nilObject]
ifFalse:
[ owningProcess := self removeFirstLinkOfList: criticalSection.
objectMemory
storePointerUnchecked: owningProcessIndex
ofObject: criticalSection
withValue: owningProcess.
self resume: owningProcess preemptedYieldingIf: preemptionYields ]

Now I've inserted the additional check without completely
understanding the code around it. I've been contemplating (self
isEmptyList: criticalSection) off and on for a couple of days and I'm
stumped. I only guess it has something to do with a process being
suspended while inside the critical section.

Also I guess the ( argumentCount > 0) is so it can be used from the debugger ??

cheers -ben

Denis Kudriashov

Re: Where to get Monitor implementation based on primitives?

Hi.

2016-01-17 17:47 GMT+01:00 Ben Coman <[hidden email]>:

I suspect a problem since it does not check it is the owningProcess
before setting owningProcess to nil. AFAIK, only the owning process
should be able to release the mutex.

Yes. But it is not mutex. It is more abstract thing which allow implement mutex and other concurrency stuff (like ReadWriteLock). That's why I rename CriticalSection to LockOwnership in my proposals. It only contains primitives and no high level methods like #critical:.

Eliot Miranda-2

Re: Where to get Monitor implementation based on primitives?

Hi Denis,

On Jan 17, 2016, at 9:01 AM, Denis Kudriashov <[hidden email]> wrote:

Hi.

2016-01-17 17:47 GMT+01:00 Ben Coman <[hidden email]>:
I suspect a problem since it does not check it is the owningProcess
before setting owningProcess to nil. AFAIK, only the owning process
should be able to release the mutex.

Yes. But it is not mutex. It is more abstract thing which allow implement mutex and other concurrency stuff (like ReadWriteLock). That's why I rename CriticalSection to LockOwnership in my proposals. It only contains primitives and no high level methods like #critical:.

Sounds good. Now would be a good time to submit your preferred versions of the primitives which answer the values that make for more natural variable names. I'm about to release new VMs, including a 64-bit Spur JIT. So I could include the new primitives.

Denis Kudriashov

Re: Where to get Monitor implementation based on primitives?

2016-01-17 18:09 GMT+01:00 Eliot Miranda <[hidden email]>:

Sounds good. Now would be a good time to submit your preferred versions of the primitives which answer the values that make for more natural variable names. I'm about to release new VMs, including a 64-bit Spur JIT. So I could include the new primitives.

This is excellent news Eliot! And new primitives will be nice addition.

Ben Coman

Re: Where to get Monitor implementation based on primitives?

In reply to this post by Eliot Miranda-2

On Mon, Jan 18, 2016 at 1:09 AM, Eliot Miranda <[hidden email]> wrote:

>
> Hi Denis,
>
> On Jan 17, 2016, at 9:01 AM, Denis Kudriashov <[hidden email]> wrote:
>
> Hi.
>
> 2016-01-17 17:47 GMT+01:00 Ben Coman <[hidden email]>:
>>
>> I suspect a problem since it does not check it is the owningProcess
>> before setting owningProcess to nil. AFAIK, only the owning process
>> should be able to release the mutex.
>
>
> Yes. But it is not mutex. It is more abstract thing which allow implement mutex and other concurrency stuff (like ReadWriteLock). That's why I rename CriticalSection to LockOwnership in my proposals.

I find LockOwnership a bit cumbersome. I guess you don't want just
Lock but to include the sense of ownership. Would you consider one of
these...
* Locker "A person or thing that does an action indicated by the
root verb" [1]
* Lockee "Less commonly added to verbs to form words meaning a
person or thing that is the subject of that verb (ie, who or that does
an action), especially where a passive sense of the verb is implied."
[2]
* OwnLock
* OwnedLock

[1] https://en.wiktionary.org/wiki/-er#Suffix
[2] https://en.wiktionary.org/wiki/-ee#Suffix

cheers -ben

> It only contains primitives and no high level methods like #critical:.
>
>
> Sounds good. Now would be a good time to submit your preferred versions of the primitives which answer the values that make for more natural variable names. I'm about to release new VMs, including a 64-bit Spur JIT. So I could include the new primitives.
>

Eliot Miranda-2

Re: Where to get Monitor implementation based on primitives?

In reply to this post by Denis Kudriashov

Hi Denis,

On Mon, Jan 11, 2016 at 5:58 AM, Denis Kudriashov <[hidden email]> wrote:

Eliot I found that there are no methods for simulation code (if it right name for it). So stepping over new primitives failed (which is infinite recursion for Pharo case)

Find the Squeak code attached. Merge it with the Pharo code (renaming ContextPart to COntext of course; something we'll do in Squeak eventually :-) )..

Context>>doPrimitive: primitiveIndex method: meth receiver: aReceiver args: arguments
...
"Mutex>>primitiveEnterCriticalSection
Mutex>>primitiveTestAndSetOwnershipOfCriticalSection"
(primitiveIndex = 186 or: [primitiveIndex = 187]) ifTrue:
[| active effective |
active := Processor activeProcess.
effective := active effectiveProcess.
"active == effective"
value := primitiveIndex = 186
ifTrue: [aReceiver primitiveEnterCriticalSectionOnBehalfOf: effective]
ifFalse: [aReceiver primitiveTestAndSetOwnershipOfCriticalSectionOnBehalfOf: effective].
^(self isPrimFailToken: value)
ifTrue: [value]
ifFalse: [self push: value]].

How this methods should be implemented?

2016-01-11 13:59 GMT+01:00 Denis Kudriashov <[hidden email]>:
Hello.
I publish slice 17373.

I introduce LockOwnership class which implements VM primitives as:
- acquire
- tryAcquire
- release
(It comment saves copyright from CriticalSection)

Mutext uses it as ownership instance variable to implement critical methods correctly:
- critical:
- critical:ifLocked:
- critical:ifError:
- critical:ifCurtailed:

For the integration process old Mutex instance variables are not removed. So loading this code should not broke current Mutex instances. But when we integrate it Mutex will have only variable ownership.

If you look critical implementation you will understand why I not like semantic of primitives. it should be inverted in future. #acquire should return true when ownership is acquired right now.

Process>>terminate now detects waiting on LockOwnership and ask it to handle wait termination.Then LockOwnership inject right value into lock state variable. Such variables should be marked with special pragma
    <lockAt: #ownershipVariableName tracksStateAt: 1> "index of local variable"
Method can contain mulpible pragmas to reference all ownerships in method. ReadWriteLock for example needs this.

2016-01-11 13:30 GMT+01:00 Henrik Johansen <[hidden email]>:

On 08 Jan 2016, at 4:25 , Ben Coman <[hidden email]> wrote:

On Fri, Jan 8, 2016 at 9:39 PM, Ben Coman <[hidden email]> wrote:
On Fri, Jan 8, 2016 at 5:42 PM, stephane ducasse
<[hidden email]> wrote:

I have a (stupid) question.
Is the code running without the primitives?
Are the code below the primitives correct?
I asked that because we can have 100 eyes and brains on the smalltalk level and far less on the VM primitive level.

Because:
1. Concurrency bugs can be subtle and the *exact* conditions can be
hard to reproduce for debugging. For example, the solution to a
couple of problems with Delay [1] [2] were solved by moving away from
Semaphore>>critical: to use signalling.

2. The in-image atomicity of determining whether a signal was actually
consumed or not during process suspension/termination is awkward. Its
seems hard to *really* know for sure it right (but I haven't looked in
depth into Denis' latest proposals.)

3. The existing in-image implementation of Semaphore>>critical messes
around in Process>>terminate in a *special* way that is not easy for
those 100 eyes to understand. For example, I personally am not
comfortable with understanding how the special Semaphore handling in
Process>>terminate works, but I can easily follow how
primitiveEnterCriticalSection just looking at the code [3].

Points 2 & 3 might possibly be addressed by having new primitiveWaitReturned
*always* return true, so if the process is terminated while waiting,
the assignment to signalConsumed doesn't occur...

critical: mutuallyExcludedBlock
   signalConsumed := false.
   [
       signalConsumed := self primitiveWaitReturned.
       blockValue := mutuallyExcludedBlock value
   ] ensure: [ signalConsumed ifTrue: [self signal] ].
   ^blockValue

where primitiveWait (https://git.io/vuDjd) is copied
and (just guessing) the marked line added...

primitiveWaitReturned
     | sema excessSignals activeProc inInterpreter |
     sema := self stackTop. "rcvr"
"==>>" self pop: argumentCount + 1 thenPush: objectMemory trueObject. "<<=="
    excessSignals := self fetchInteger: ExcessSignalsIndex ofObject: sema.
     excessSignals > 0
         ifTrue:
           [self storeInteger: ExcessSignalsIndex
                       ofObject: sema
                       withValue: excessSignals - 1]
         ifFalse:
           inInterpreter := instructionPointer >= objectMemory startOfMemory.
           activeProc := self activeProcess.
           self addLastLink: activeProc toList: sema.
           self transferTo: self wakeHighestPriority from: CSWait.
           self
forProcessPrimitiveReturnToExecutivePostContextSwitch: inInterpreter]

which I guess could be added quickly if Esteban could compile the
latest pharo-spur-vm ;)

cheers -ben

Won't work, there's no guarantee thread has actually ran and signalConsumed been assigned the primitive result after Semaphore resumed the waiting thread, before a higher priority thread runs and terminates it. (which is exactly the case handled by special code in #terminate)

Cheers,
Henry

_,,,^..^,,,_

best, Eliot

ContextPart-doPrimitivemethodreceiverargs.st (5K) Download Attachment

Eliot Miranda-2

Re: Where to get Monitor implementation based on primitives?

Hi Denis,

ignore this: I'm confused. I will catch up soon :-/

On Sun, Jan 17, 2016 at 11:52 AM, Eliot Miranda <[hidden email]> wrote:

Hi Denis,

On Mon, Jan 11, 2016 at 5:58 AM, Denis Kudriashov <[hidden email]> wrote:

Eliot I found that there are no methods for simulation code (if it right name for it). So stepping over new primitives failed (which is infinite recursion for Pharo case)

Find the Squeak code attached. Merge it with the Pharo code (renaming ContextPart to COntext of course; something we'll do in Squeak eventually :-) )..

Context>>doPrimitive: primitiveIndex method: meth receiver: aReceiver args: arguments
...
"Mutex>>primitiveEnterCriticalSection
Mutex>>primitiveTestAndSetOwnershipOfCriticalSection"
(primitiveIndex = 186 or: [primitiveIndex = 187]) ifTrue:
[| active effective |
active := Processor activeProcess.
effective := active effectiveProcess.
"active == effective"
value := primitiveIndex = 186
ifTrue: [aReceiver primitiveEnterCriticalSectionOnBehalfOf: effective]
ifFalse: [aReceiver primitiveTestAndSetOwnershipOfCriticalSectionOnBehalfOf: effective].
^(self isPrimFailToken: value)
ifTrue: [value]
ifFalse: [self push: value]].

How this methods should be implemented?

2016-01-11 13:59 GMT+01:00 Denis Kudriashov <[hidden email]>:
Hello.
I publish slice 17373.

I introduce LockOwnership class which implements VM primitives as:
- acquire
- tryAcquire
- release
(It comment saves copyright from CriticalSection)

Mutext uses it as ownership instance variable to implement critical methods correctly:
- critical:
- critical:ifLocked:
- critical:ifError:
- critical:ifCurtailed:

For the integration process old Mutex instance variables are not removed. So loading this code should not broke current Mutex instances. But when we integrate it Mutex will have only variable ownership.

If you look critical implementation you will understand why I not like semantic of primitives. it should be inverted in future. #acquire should return true when ownership is acquired right now.

Process>>terminate now detects waiting on LockOwnership and ask it to handle wait termination.Then LockOwnership inject right value into lock state variable. Such variables should be marked with special pragma
    <lockAt: #ownershipVariableName tracksStateAt: 1> "index of local variable"
Method can contain mulpible pragmas to reference all ownerships in method. ReadWriteLock for example needs this.

2016-01-11 13:30 GMT+01:00 Henrik Johansen <[hidden email]>:

On 08 Jan 2016, at 4:25 , Ben Coman <[hidden email]> wrote:

On Fri, Jan 8, 2016 at 9:39 PM, Ben Coman <[hidden email]> wrote:
On Fri, Jan 8, 2016 at 5:42 PM, stephane ducasse
<[hidden email]> wrote:

I have a (stupid) question.
Is the code running without the primitives?
Are the code below the primitives correct?
I asked that because we can have 100 eyes and brains on the smalltalk level and far less on the VM primitive level.

Because:
1. Concurrency bugs can be subtle and the *exact* conditions can be
hard to reproduce for debugging. For example, the solution to a
couple of problems with Delay [1] [2] were solved by moving away from
Semaphore>>critical: to use signalling.

2. The in-image atomicity of determining whether a signal was actually
consumed or not during process suspension/termination is awkward. Its
seems hard to *really* know for sure it right (but I haven't looked in
depth into Denis' latest proposals.)

3. The existing in-image implementation of Semaphore>>critical messes
around in Process>>terminate in a *special* way that is not easy for
those 100 eyes to understand. For example, I personally am not
comfortable with understanding how the special Semaphore handling in
Process>>terminate works, but I can easily follow how
primitiveEnterCriticalSection just looking at the code [3].

Points 2 & 3 might possibly be addressed by having new primitiveWaitReturned
*always* return true, so if the process is terminated while waiting,
the assignment to signalConsumed doesn't occur...

critical: mutuallyExcludedBlock
   signalConsumed := false.
   [
       signalConsumed := self primitiveWaitReturned.
       blockValue := mutuallyExcludedBlock value
   ] ensure: [ signalConsumed ifTrue: [self signal] ].
   ^blockValue

where primitiveWait (https://git.io/vuDjd) is copied
and (just guessing) the marked line added...

primitiveWaitReturned
     | sema excessSignals activeProc inInterpreter |
     sema := self stackTop. "rcvr"
"==>>" self pop: argumentCount + 1 thenPush: objectMemory trueObject. "<<=="
    excessSignals := self fetchInteger: ExcessSignalsIndex ofObject: sema.
     excessSignals > 0
         ifTrue:
           [self storeInteger: ExcessSignalsIndex
                       ofObject: sema
                       withValue: excessSignals - 1]
         ifFalse:
           inInterpreter := instructionPointer >= objectMemory startOfMemory.
           activeProc := self activeProcess.
           self addLastLink: activeProc toList: sema.
           self transferTo: self wakeHighestPriority from: CSWait.
           self
forProcessPrimitiveReturnToExecutivePostContextSwitch: inInterpreter]

which I guess could be added quickly if Esteban could compile the
latest pharo-spur-vm ;)

cheers -ben

Won't work, there's no guarantee thread has actually ran and signalConsumed been assigned the primitive result after Semaphore resumed the waiting thread, before a higher priority thread runs and terminates it. (which is exactly the case handled by special code in #terminate)

Cheers,
Henry

_,,,^..^,,,_
best, Eliot

_,,,^..^,,,_

best, Eliot

Eliot Miranda-2

Re: Where to get Monitor implementation based on primitives?

In reply to this post by Denis Kudriashov

Thanks Denis,

On Mon, Jan 11, 2016 at 6:54 AM, Denis Kudriashov <[hidden email]> wrote:

I write it such way:

primitiveEnterCriticalSectionOnBehalfOf: activeProcess
[owningProcess ifNil:
[owningProcess := activeProcess.
^false].
owningProcess = activeProcess ifTrue:
[^true].
self addLast: Processor activeProcess.
activeProcess suspend] valueUnpreemptively

primitiveTestAndSetOwnershipOfCriticalSectionOnBehalfOf: activeProcess
[owningProcess ifNil:
[owningProcess := activeProcess.
^false].
owningProcess = activeProcess ifTrue: [^true].
^nil] valueUnpreemptively

This looks good. Do you have methods you've written? I'd like to use yours as they have your time stamp.

2016-01-11 14:58 GMT+01:00 Denis Kudriashov <[hidden email]>:
Eliot I found that there are no methods for simulation code (if it right name for it). So stepping over new primitives failed (which is infinite recursion for Pharo case)

Context>>doPrimitive: primitiveIndex method: meth receiver: aReceiver args: arguments
...
"Mutex>>primitiveEnterCriticalSection
Mutex>>primitiveTestAndSetOwnershipOfCriticalSection"
(primitiveIndex = 186 or: [primitiveIndex = 187]) ifTrue:
[| active effective |
active := Processor activeProcess.
effective := active effectiveProcess.
"active == effective"
value := primitiveIndex = 186
ifTrue: [aReceiver primitiveEnterCriticalSectionOnBehalfOf: effective]
ifFalse: [aReceiver primitiveTestAndSetOwnershipOfCriticalSectionOnBehalfOf: effective].
^(self isPrimFailToken: value)
ifTrue: [value]
ifFalse: [self push: value]].

How this methods should be implemented?

2016-01-11 13:59 GMT+01:00 Denis Kudriashov <[hidden email]>:
Hello.
I publish slice 17373.

I introduce LockOwnership class which implements VM primitives as:
- acquire
- tryAcquire
- release
(It comment saves copyright from CriticalSection)

Mutext uses it as ownership instance variable to implement critical methods correctly:
- critical:
- critical:ifLocked:
- critical:ifError:
- critical:ifCurtailed:

For the integration process old Mutex instance variables are not removed. So loading this code should not broke current Mutex instances. But when we integrate it Mutex will have only variable ownership.

If you look critical implementation you will understand why I not like semantic of primitives. it should be inverted in future. #acquire should return true when ownership is acquired right now.

Process>>terminate now detects waiting on LockOwnership and ask it to handle wait termination.Then LockOwnership inject right value into lock state variable. Such variables should be marked with special pragma
    <lockAt: #ownershipVariableName tracksStateAt: 1> "index of local variable"
Method can contain mulpible pragmas to reference all ownerships in method. ReadWriteLock for example needs this.

2016-01-11 13:30 GMT+01:00 Henrik Johansen <[hidden email]>:

On 08 Jan 2016, at 4:25 , Ben Coman <[hidden email]> wrote:

On Fri, Jan 8, 2016 at 9:39 PM, Ben Coman <[hidden email]> wrote:
On Fri, Jan 8, 2016 at 5:42 PM, stephane ducasse
<[hidden email]> wrote:

I have a (stupid) question.
Is the code running without the primitives?
Are the code below the primitives correct?
I asked that because we can have 100 eyes and brains on the smalltalk level and far less on the VM primitive level.

Because:
1. Concurrency bugs can be subtle and the *exact* conditions can be
hard to reproduce for debugging. For example, the solution to a
couple of problems with Delay [1] [2] were solved by moving away from
Semaphore>>critical: to use signalling.

2. The in-image atomicity of determining whether a signal was actually
consumed or not during process suspension/termination is awkward. Its
seems hard to *really* know for sure it right (but I haven't looked in
depth into Denis' latest proposals.)

3. The existing in-image implementation of Semaphore>>critical messes
around in Process>>terminate in a *special* way that is not easy for
those 100 eyes to understand. For example, I personally am not
comfortable with understanding how the special Semaphore handling in
Process>>terminate works, but I can easily follow how
primitiveEnterCriticalSection just looking at the code [3].

Points 2 & 3 might possibly be addressed by having new primitiveWaitReturned
*always* return true, so if the process is terminated while waiting,
the assignment to signalConsumed doesn't occur...

critical: mutuallyExcludedBlock
   signalConsumed := false.
   [
       signalConsumed := self primitiveWaitReturned.
       blockValue := mutuallyExcludedBlock value
   ] ensure: [ signalConsumed ifTrue: [self signal] ].
   ^blockValue

where primitiveWait (https://git.io/vuDjd) is copied
and (just guessing) the marked line added...

primitiveWaitReturned
     | sema excessSignals activeProc inInterpreter |
     sema := self stackTop. "rcvr"
"==>>" self pop: argumentCount + 1 thenPush: objectMemory trueObject. "<<=="
    excessSignals := self fetchInteger: ExcessSignalsIndex ofObject: sema.
     excessSignals > 0
         ifTrue:
           [self storeInteger: ExcessSignalsIndex
                       ofObject: sema
                       withValue: excessSignals - 1]
         ifFalse:
           inInterpreter := instructionPointer >= objectMemory startOfMemory.
           activeProc := self activeProcess.
           self addLastLink: activeProc toList: sema.
           self transferTo: self wakeHighestPriority from: CSWait.
           self
forProcessPrimitiveReturnToExecutivePostContextSwitch: inInterpreter]

which I guess could be added quickly if Esteban could compile the
latest pharo-spur-vm ;)

cheers -ben

Won't work, there's no guarantee thread has actually ran and signalConsumed been assigned the primitive result after Semaphore resumed the waiting thread, before a higher priority thread runs and terminates it. (which is exactly the case handled by special code in #terminate)

Cheers,
Henry

_,,,^..^,,,_

best, Eliot

Denis Kudriashov

Re: Where to get Monitor implementation based on primitives?

2016-01-17 20:58 GMT+01:00 Eliot Miranda <[hidden email]>:

Thanks Denis,

On Mon, Jan 11, 2016 at 6:54 AM, Denis Kudriashov <[hidden email]> wrote:

I write it such way:

primitiveEnterCriticalSectionOnBehalfOf: activeProcess
[owningProcess ifNil:
[owningProcess := activeProcess.
^false].
owningProcess = activeProcess ifTrue:
[^true].
self addLast: Processor activeProcess.
activeProcess suspend] valueUnpreemptively

primitiveTestAndSetOwnershipOfCriticalSectionOnBehalfOf: activeProcess
[owningProcess ifNil:
[owningProcess := activeProcess.
^false].
owningProcess = activeProcess ifTrue: [^true].
^nil] valueUnpreemptively

This looks good. Do you have methods you've written? I'd like to use yours as they have your time stamp.

I only added it to renamed class LockOwnership (attached). So you can only copy it to original class which will reset timestamps

LockOwnership.st (9K) Download Attachment

Denis Kudriashov

Re: Where to get Monitor implementation based on primitives?

In reply to this post by Ben Coman

2016-01-17 19:10 GMT+01:00 Ben Coman <[hidden email]>:

I find LockOwnership a bit cumbersome. I guess you don't want just
Lock but to include the sense of ownership. Would you consider one of
these...
* Locker "A person or thing that does an action indicated by the
root verb" [1]
* Lockee "Less commonly added to verbs to form words meaning a
person or thing that is the subject of that verb (ie, who or that does
an action), especially where a passive sense of the verb is implied."
[2]
* OwnLock
* OwnedLock

To choose better class name we should take into account how we will use it.

Could you suggest names for #acquire and #release in context of your class name?

("locker acquire" is not good)

If people think that simple Lock is good for this purpose we can use it.

KenDickey

Re: Where to get Monitor implementation based on primitives?

On Mon, 18 Jan 2016 11:22:15 +0100
Denis Kudriashov <[hidden email]> wrote:

> To choose better class name we should take into account how we will use it.
> Could you suggest names for #acquire and #release in context of your class
> name?
> ("locker acquire" is not good)
>
> If people think that simple Lock is good for this purpose we can use it.

Perhaps better to think of an "access permission" than a "lock"

uniqueAccess acquire

accessPermission acquire

...?
-KenD

-KenD

Denis Kudriashov

Re: Where to get Monitor implementation based on primitives?

2016-01-18 17:06 GMT+01:00 KenD <[hidden email]>:

Perhaps better to think of an "access permission" than a "lock"

uniqueAccess acquire

accessPermission acquire

...?

It is interesting.

But I don't know how to make conclusion. Maybe on Sprint I can discuss it with more people

Ben Coman

Re: Where to get Monitor implementation based on primitives?

In reply to this post by Denis Kudriashov

On Mon, Jan 18, 2016 at 6:22 PM, Denis Kudriashov <[hidden email]> wrote:

>
>
> 2016-01-17 19:10 GMT+01:00 Ben Coman <[hidden email]>:
>>
>> I find LockOwnership a bit cumbersome. I guess you don't want just
>> Lock but to include the sense of ownership. Would you consider one of
>> these...
>> * Locker "A person or thing that does an action indicated by the
>> root verb" [1]
>> * Lockee "Less commonly added to verbs to form words meaning a
>> person or thing that is the subject of that verb (ie, who or that does
>> an action), especially where a passive sense of the verb is implied."
>> [2]
>> * OwnLock
>> * OwnedLock
>
>
> To choose better class name we should take into account how we will use it.
> Could you suggest names for #acquire and #release in context of your class name?
> ("locker acquire" is not good)

You're right. I didn't think it through. I don't have any good
alternative message names.

>
> If people think that simple Lock is good for this purpose we can use it.

I think Lock is probably okay but survey a few more opinions. However
a generic lock as introduced in most CS lessons that turned up in
searches don't have an owner, so maybe my last suggestion OwnedLock is
also. For example...
lock := OwnedLock new.
lock aquire

cheers -ben

Ben Coman

Re: Where to get Monitor implementation based on primitives?

In reply to this post by KenDickey

On Tue, Jan 19, 2016 at 12:06 AM, KenD <[hidden email]> wrote:

>
> On Mon, 18 Jan 2016 11:22:15 +0100
> Denis Kudriashov <[hidden email]> wrote:
>
>> To choose better class name we should take into account how we will use it.
>> Could you suggest names for #acquire and #release in context of your class
>> name?
>> ("locker acquire" is not good)
>>
>> If people think that simple Lock is good for this purpose we can use it.
>
>
> Perhaps better to think of an "access permission" than a "lock"
>
> uniqueAccess acquire

Maybe. Except when I think of uniqueXXX what comes to mind is the
Singleton pattern.

>
> accessPermission acquire

I think this is a stretch, and invokes thoughts of security and file access.

cheers -ben

123