Re: [ECOS] atomic singly linked lists

[Nick Garnett <nickg at redhat dot com>]

"Andre Asselin" <asselin@us.ibm.com> writes:

> Nick Garnett writes:
> 
> >Yep. I'm a big fan of lock-free synchronization techniques. I would
> >have liked to see them used more in eCos. One reason for not using
> >these much is that anything that eCos provides has to work on all the
> >platforms we support. Not all have support for the compare-and-swap
> >(or LL/SC) operation this needs. Having to implement it by disabling
> >interrupts is somewhat less compelling.
> 
> You don't necessarily have to disable interrupts on architectures that
> don't support an atomic compare and exchange instruction.  One
> implementation of the list class can use atomic operations for those HALs
> that support it, and another implementation could have a spinlock with an
> ordinary list head pointer for those HALs that don't.  The latter
> implementation would just fall back to using a spinlock to protect the
> list, in which case, you'd only disable DSRs, not interrupts.

Of course, most architectures that have the support for spinlocks
would probably also have support for compare-and-swap. LL/SC can do
both. I guess there might be architectures that only have
test-and-set, but I cannot think of any at present.

Also, the scheduler lock, which disables DSRs, is somewhat more
expensive than disabling interrupts. This is because when it is
released, the scheduler must go and look for DSRs to run and threads
to schedule.

> 
> >Of course there is nothing to stop you implementing such operations in
> >your own code, if your platform has the necessary support.
> >Particularly if you are writing drivers for your own hardware.
> 
> Agreed.
> 
> BTW, do you have any comments on the cyg_spinlock issue I posted
> (http://sources.redhat.com/ml/ecos-discuss/2001-08/msg00893.html)?
> 

I must have missed that originally:

> I was looking at the new cyg_spinlock stuff in the kernel, and noticed that
> the uniprocessor version of the functions don't disable scheduling or block
> DSRs when a lock is acquired.  In order for spinlocks to be useful, they
> need to be able to lock between DSRs and "thread" level code (think of a
> producer/consumer model for example).  On a uniprocessor machine, that
> means the scheduler and DSR dispatching need to be disabled while any lock
> is acquired.  On an MP machine, scheduling and DSR dispatching would be
> disabled on the CPU that acquires the spinlock, and other CPUs would use
> the spin mechanics to synchronize against the CPU that owns the lock.

To keep things simple I took the approach that the basic spinlock
would not make any statement about safety with respect to interrupts
and DSRs. It only functions to provide synchronization between
CPUs.

If the user needs interrupt-safety he can use the *_intsave()
variants, which blocks all local preemption. I guess there could also
be *_schedlock() variants that would behave as you suggest. But given
the relative cost of the scheduler lock mentioned above, and the
intention that the spinlocks should only be held for very brief
lengths of time, this did not seen necessary. Also, the scheduler lock
is global to all CPUs, since it protects shared data, and so is less
useful for very low level synchronization purposes.

> 
> On a related topic, I think it would be extremely nice while making SMP
> enhancements to extend the DSR mechanism to be a general purpose (ala NT's
> equivalent DPCs).  This would allow you to define DSRs for any old purpose
> and be able to queue them whenever you wanted.  In an SMP environment, this
> can allow better parallelism.
> 

I have thought about this, and decided that I prefer to keep the
system as simple as possible. Once DSRs become a general purpose
mechanism you get into questions of prioritizing them and priority
inversion rears its ugly head. This is a can of worms I prefer not to
open. Anything more complex than what DSRs currently do is probably
best done in threads, where it can be scheduled properly.

Again, there is nothing to stop anyone implementing their own DSR-like
mechanism that is serviced by a high priority thread.


-- 
Nick Garnett, eCos Kernel Architect
Red Hat, Cambridge, UK