Re: Question from Russells Spinlocks

Re: Question from Russells Spinlocks

[kernel-stuff]

Spinlocks are used in situations where multiple threads contend for a lock and they can possibly run on more than one CPU. Example - Thread A is executing on CPU-A, Thread B in executing on CPU-B. They contend for a lock L1.  A acquires the lock first. B tries (on CPU-B) to acquire the lock L1 and finds it is not free - so it just spins (executes a no-op kind of loop ) until Thread A relinquishes the lock L1. 
Spinlocks are used in cases where the operation performed under a lock is short one - takes very less time. In these type of cases, spinning is less costlier than sleeping which involves scheduler overhead.
So if we take out CPU-B from the above equation - there is no chance for Thread B to execute to contend for lock L1 without thread A going to sleep. That's why spinlocks are useless on 1 CPU machine.

 The comment about  atomic_t - It is due to the fact that some ( IA-32 for e.g.) architectures guarantees atomicity of integer operations for only 24 bits. So you could possibly manipulate only 24 out of the 32 bits atomically - that's the hardware guarantee. The comments reflect this fact. (Pointers are 32bits on IA32 so it applies to pointer as well.)

Correct me if I am wrong :) !

Parag


> 
> Hello there,
> 
>     I was reading Russell's guide on spinlocks, and I have some 
> questions regarding it.
> 
> 
>     Question-->    Russell says that in case of non-SMP machines 
> spinlocks don't exist _at_ALL_. Well they should do something don't they 
> like disable interrupts and premptations. I checked linux/spinlock well 
> they DO NOT do anything atleast not when DEBUG_SPINLOCKS == 0. My 
> understanding is that since they aren't used anywhere outside kernel and 
> drivers(?), they can't be prempted. At least that is what I have read.
> 
> 
> What does the comment about gcc while defining atomic_t signify?
>              --> What about the comment about the limit of 24 bits on 
> atomic_t?    
>              a)    Atomic operations on integers are guranteed only if 
> there value can be stored in 24 bits.
>              b)    Atomic operations are guranteed only if the pointer 
> has 8 MSbits set zero.
> 
> 
> -- 
> Imanpreet Singh Arora
> 
> Even if you are on the right track you are going to get runover if you just sit 
> there.
> 	-- Will Rogers
> 
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: Question from Russells Spinlocks

[Robert Love]

On Thu, 2004-12-09 at 21:15 +0000, kernel-stuff@comcast.net wrote:

This part is incorrect (and horribly wrapped):

>  The comment about  atomic_t - It is due to the fact that some ( IA-32 for e.g.) architectures guarantees atomicity of integer operations for only 24 bits. So you could possibly manipulate only 24 out of the 32 bits atomically - that's the hardware guarantee. The comments reflect this fact. (Pointers are 32bits on IA32 so it applies to pointer as well.)

The reason for the 24-bit limit on atomic_t is because SPARC32's
implementation of atomic operations was limited to 24-bits per atomic
integer, because the architecture provides very minimal atomic support,
we had to embed a byte-sized lock in the word.  This limited SPARC32's
atomic integer to 24 usable bits.  The other architectures can, of
course, hold the full 32-bits but to be compatible code must assume the
24-bit limit.

Although this was fixed recently in 2.6 so it actually no longer
applies.

	Robert Love

Re: Question from Russells Spinlocks

[Parag Warudkar]

Robert Love wrote:

>On Thu, 2004-12-09 at 21:15 +0000, kernel-stuff@comcast.net wrote:
>
>This part is incorrect (and horribly wrapped):
>
>  
>
>> The comment about  atomic_t - It is due to the fact that some ( IA-32 for e.g.) architectures guarantees atomicity of integer operations for only 24 bits. So you could possibly manipulate only 24 out of the 32 bits atomically - that's the hardware guarantee. The comments reflect this fact. (Pointers are 32bits on IA32 so it applies to pointer as well.)
>>    
>>
>
>The reason for the 24-bit limit on atomic_t is because SPARC32's
>implementation of atomic operations was limited to 24-bits per atomic
>integer, because the architecture provides very minimal atomic support,
>we had to embed a byte-sized lock in the word.  This limited SPARC32's
>atomic integer to 24 usable bits.  The other architectures can, of
>course, hold the full 32-bits but to be compatible code must assume the
>24-bit limit.
>
>Although this was fixed recently in 2.6 so it actually no longer
>applies.
>  
>
Yes - I understand it better now. Thanks!

Parag

Re: Question from Russells Spinlocks

[Anton Altaparmakov]

On Thu, 9 Dec 2004 kernel-stuff@comcast.net wrote:
> Spinlocks are used in situations where multiple threads contend for a 
> lock and they can possibly run on more than one CPU. Example - Thread A 
> is executing on CPU-A, Thread B in executing on CPU-B. They contend for 
> a lock L1.  A acquires the lock first. B tries (on CPU-B) to acquire the 
> lock L1 and finds it is not free - so it just spins (executes a no-op 
> kind of loop ) until Thread A relinquishes the lock L1. Spinlocks are 
> used in cases where the operation performed under a lock is short one - 
> takes very less time. In these type of cases, spinning is less costlier 
> than sleeping which involves scheduler overhead. So if we take out CPU-B 
> from the above equation - there is no chance for Thread B to execute to 
> contend for lock L1 without thread A going to sleep. That's why 
> spinlocks are useless on 1 CPU machine.

Your last sentence is incorrect.  Spinlocks on 1 CPU machines still need 
to disable preemption (assuming preemption is compiled in obviously, if 
not then indeed you are right).  Otherwise preemption could take place in 
the middle of a data manipulation and you would still have the same race 
as you described with two cpus working concurrently.  Except that with 
preemption it is only logical concurrence not actual physical concurrence.

Best regards,

	Anton

>  The comment about atomic_t - It is due to the fact that some ( IA-32 
> for e.g.) architectures guarantees atomicity of integer operations for 
> only 24 bits. So you could possibly manipulate only 24 out of the 32 
> bits atomically - that's the hardware guarantee. The comments reflect 
> this fact. (Pointers are 32bits on IA32 so it applies to pointer as 
> well.)
> 
> Correct me if I am wrong :) !
> 
> Parag
> 
> 
> > 
> > Hello there,
> > 
> >     I was reading Russell's guide on spinlocks, and I have some 
> > questions regarding it.
> > 
> > 
> >     Question-->    Russell says that in case of non-SMP machines 
> > spinlocks don't exist _at_ALL_. Well they should do something don't they 
> > like disable interrupts and premptations. I checked linux/spinlock well 
> > they DO NOT do anything atleast not when DEBUG_SPINLOCKS == 0. My 
> > understanding is that since they aren't used anywhere outside kernel and 
> > drivers(?), they can't be prempted. At least that is what I have read.
> > 
> > 
> > What does the comment about gcc while defining atomic_t signify?
> >              --> What about the comment about the limit of 24 bits on 
> > atomic_t?    
> >              a)    Atomic operations on integers are guranteed only if 
> > there value can be stored in 24 bits.
> >              b)    Atomic operations are guranteed only if the pointer 
> > has 8 MSbits set zero.

-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer / IRC: #ntfs on irc.freenode.net
WWW: http://linux-ntfs.sf.net/ & http://www-stu.christs.cam.ac.uk/~aia21/

Re: Question from Russells Spinlocks

[Jeff V. Merkey]

Anton Altaparmakov wrote:

>
>
>Your last sentence is incorrect.  Spinlocks on 1 CPU machines still need 
>to disable preemption (assuming preemption is compiled in obviously, if 
>not then indeed you are right).  Otherwise preemption could take place in 
>the middle of a data manipulation and you would still have the same race 
>as you described with two cpus working concurrently.  Except that with 
>preemption it is only logical concurrence not actual physical concurrence.
>
>Best regards,
>
>	Anton
>
>  
>

Anton is correct in his analysis.

Jeff

Re: Question from Russells Spinlocks

[Parag Warudkar]

Anton Altaparmakov wrote:

>On Thu, 9 Dec 2004 kernel-stuff@comcast.net wrote:
>  
>
>>Spinlocks are used in situations where multiple threads contend for a 
>>lock and they can possibly run on more than one CPU. Example - Thread A 
>>is executing on CPU-A, Thread B in executing on CPU-B. They contend for 
>>a lock L1.  A acquires the lock first. B tries (on CPU-B) to acquire the 
>>lock L1 and finds it is not free - so it just spins (executes a no-op 
>>kind of loop ) until Thread A relinquishes the lock L1. Spinlocks are 
>>used in cases where the operation performed under a lock is short one - 
>>takes very less time. In these type of cases, spinning is less costlier 
>>than sleeping which involves scheduler overhead. So if we take out CPU-B 
>>from the above equation - there is no chance for Thread B to execute to 
>>contend for lock L1 without thread A going to sleep. That's why 
>>spinlocks are useless on 1 CPU machine.
>>    
>>
>
>Your last sentence is incorrect.  Spinlocks on 1 CPU machines still need 
>to disable preemption (assuming preemption is compiled in obviously, if 
>not then indeed you are right).  Otherwise preemption could take place in 
>the middle of a data manipulation and you would still have the same race 
>as you described with two cpus working concurrently.  Except that with 
>preemption it is only logical concurrence not actual physical concurrence.
>  
>
I didn't take pre-emption into account. Although I would not have 
readily thought about the need to disable Pre-emption even if I had 
considered it  :-) So thanks for the correction!

Parag

Question from Russells Spinlocks

[Imanpreet Singh Arora]

Hello there,

    I was reading Russell's guide on spinlocks, and I have some 
questions regarding it.


    Question-->    Russell says that in case of non-SMP machines 
spinlocks don't exist _at_ALL_. Well they should do something don't they 
like disable interrupts and premptations. I checked linux/spinlock well 
they DO NOT do anything atleast not when DEBUG_SPINLOCKS == 0. My 
understanding is that since they aren't used anywhere outside kernel and 
drivers(?), they can't be prempted. At least that is what I have read.


What does the comment about gcc while defining atomic_t signify?
             --> What about the comment about the limit of 24 bits on 
atomic_t?    
             a)    Atomic operations on integers are guranteed only if 
there value can be stored in 24 bits.
             b)    Atomic operations are guranteed only if the pointer 
has 8 MSbits set zero.


-- 
Imanpreet Singh Arora

Even if you are on the right track you are going to get runover if you just sit there.
	-- Will Rogers

Re: Question from Russells Spinlocks

[Brian Gerst]

Imanpreet Singh Arora wrote:
> 
> Hello there,
> 
>    I was reading Russell's guide on spinlocks, and I have some questions 
> regarding it.
> 
> 
>    Question-->    Russell says that in case of non-SMP machines 
> spinlocks don't exist _at_ALL_. Well they should do something don't they 
> like disable interrupts and premptations. I checked linux/spinlock well 
> they DO NOT do anything atleast not when DEBUG_SPINLOCKS == 0. My 
> understanding is that since they aren't used anywhere outside kernel and 
> drivers(?), they can't be prempted. At least that is what I have read.
> 

On UP kernels, the spinlock operations that include interrupt 
manipulations still affect interrupts.  It's only the actual lock 
portion that becomes a no-op.

> 
> What does the comment about gcc while defining atomic_t signify?
>             --> What about the comment about the limit of 24 bits on 
> atomic_t?                a)    Atomic operations on integers are 
> guranteed only if there value can be stored in 24 bits.
>             b)    Atomic operations are guranteed only if the pointer 
> has 8 MSbits set zero.
> 
> 

In 2.6, the 24-bit limit is no longer valid.  atomic_t variables are a 
full 32 bits on all arches now.

--
				Brian Gerst

Re: Question from Russells Spinlocks

[William Lee Irwin III]

Imanpreet Singh Arora wrote:
[...]

On Thu, Dec 09, 2004 at 04:53:22PM -0500, Brian Gerst wrote:
> In 2.6, the 24-bit limit is no longer valid.  atomic_t variables are a 
> full 32 bits on all arches now.

31 bits? They're signed IIRC.


-- wli