Re: preemption across processors
On 29-May-2002 Seigo Tanimura wrote:
>>> And the p4 depot
>>>
>>> //depot/user/tanimura/ippreempt/...
>>>
>>> The patch is for only i386 at the moment.
>>>
>>> The following is the brief description of the patch:
>
> jhb> I would prefer that this was hung off the preemption stuff I've already done
> jhb> rather than reinventing it. I would also prefer that we get a preemptive
> jhb> kernel w/o this done stable before adding extra complication.
>
> Or I can integrate your work in //depot/user/jhb/preemption/... into
> //depot/user/tanimura/ippreempt/... .
I think we should do the more cautious step first.
>>> Miscellaneous stuff:
>>>
>>> If a thread spins for an adaptive mutex, propagate its priority to the
>>> owner thread of the mutex. This prevents preemption of the owner
>>> thread by a thread with the priority in between the owner thread and
>>> the spinning thread.
>
> jhb> Ewww, I'd rather avoid this if possible. This is just an optimization,
> jhb> but it would depend on how complicated this makes the mutex code to see
> jhb> if it's worth it or not.
>
> The owner thread of an adaptive mutex never lowers its priority until
> it releases the mutex. We should thus bump the priority of the owner
> thread not during but just before spinning. However, it is difficult
> to know if the current thread can spin prior to calling
> _obtain_lock().
>
> In addition, I would say that spinning can be done even more
> efficiently. At the moment, we try an atomic test-and-set
> instruction in each spin. As another thread holds the mutex, we are
> likely to execute an expensive test-and-set instruction quite a lot of
> times.
>
> Maybe we can solve both of the issues above by roughly checking if a
> thread can keep spinning without acquiring any locks, in the similar
> way as we do for a spin mutex. First, test the following conditions:
>
> - The owner of the mutex has not changed.
> - The owner is on a processor.
>
> If both of the conditions satisfy, keep spinning. Otherwise, try
> test-and-set. The pseudo-code would look like this:
>
>
> while (!_obtain_lock(m, td)) {
> mtx_lock_spin(&sched_lock);
>
> if (unowned(m)) {
> mutex_unlock_spin(&sched_lock);
> continue;
> }
>
> owner = mtx_owner(m);
> if (oncpu(owner)) {
You can not treat owner as valid unless you hold sched_lock() and
MTX_CONTESTED is set in m->mtx_lock. Thus, the value can go stale
and you could potentially be dereferencing an invalid pointer below.
> /* Spin without holding sched_lock. */
> critical_enter();
> mtx_unlock_spin(&sched_lock);
The critical section here would not be necessary I think, but you can't
read owner's value and know it is not stale if you don't hold sched_lock.
(Eventually to be replaced with a turnstile chain lock.)
One thing we might be able to do better is to change the code in the
adaptive spinning test to wait for mtx_lock to change before trying the
test-and-set again, this is a fairly simple change that isn't very hard
to do.
--
John Baldwin <[EMAIL PROTECTED]> <>< http://www.FreeBSD.org/~jhb/
"Power Users Use the Power to Serve!" - http://www.FreeBSD.org/
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message
Re: preemption across processors
On Wed, 29 May 2002 16:13:13 +0900, Seigo Tanimura <[EMAIL PROTECTED]> said: tanimura> Maybe we can solve both of the issues above by roughly checking if a tanimura> thread can keep spinning without acquiring any locks, in the similar tanimura> way as we do for a spin mutex. First, test the following conditions: tanimura> - The owner of the mutex has not changed. tanimura> - The owner is on a processor. - The priority of the curent thread has not changed. If some other thread spins for a mutex held by the current thread, we may have to propagate the priority of the other thread. -- Seigo Tanimura <[EMAIL PROTECTED]> <[EMAIL PROTECTED]> To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: preemption across processors
On Tue, 28 May 2002 14:56:04 -0400 (EDT),
John Baldwin <[EMAIL PROTECTED]> said:
>> The prototype patch is at:
>>
>> http://people.FreeBSD.org/~tanimura/patches/ippreempt.diff.gz
>>
>> And the p4 depot
>>
>> //depot/user/tanimura/ippreempt/...
>>
>> The patch is for only i386 at the moment.
>>
>> The following is the brief description of the patch:
jhb> I would prefer that this was hung off the preemption stuff I've already done
jhb> rather than reinventing it. I would also prefer that we get a preemptive
jhb> kernel w/o this done stable before adding extra complication.
Or I can integrate your work in //depot/user/jhb/preemption/... into
//depot/user/tanimura/ippreempt/... .
>> Miscellaneous stuff:
>>
>> If a thread spins for an adaptive mutex, propagate its priority to the
>> owner thread of the mutex. This prevents preemption of the owner
>> thread by a thread with the priority in between the owner thread and
>> the spinning thread.
jhb> Ewww, I'd rather avoid this if possible. This is just an optimization,
jhb> but it would depend on how complicated this makes the mutex code to see
jhb> if it's worth it or not.
The owner thread of an adaptive mutex never lowers its priority until
it releases the mutex. We should thus bump the priority of the owner
thread not during but just before spinning. However, it is difficult
to know if the current thread can spin prior to calling
_obtain_lock().
In addition, I would say that spinning can be done even more
efficiently. At the moment, we try an atomic test-and-set
instruction in each spin. As another thread holds the mutex, we are
likely to execute an expensive test-and-set instruction quite a lot of
times.
Maybe we can solve both of the issues above by roughly checking if a
thread can keep spinning without acquiring any locks, in the similar
way as we do for a spin mutex. First, test the following conditions:
- The owner of the mutex has not changed.
- The owner is on a processor.
If both of the conditions satisfy, keep spinning. Otherwise, try
test-and-set. The pseudo-code would look like this:
while (!_obtain_lock(m, td)) {
mtx_lock_spin(&sched_lock);
if (unowned(m)) {
mutex_unlock_spin(&sched_lock);
continue;
}
owner = mtx_owner(m);
if (oncpu(owner)) {
bump_priority(owner, td);
/* Spin without holding sched_lock. */
critical_enter();
mtx_unlock_spin(&sched_lock);
while (owner == mtx_owner(m) && oncpu(owner)) {
/* Handle interrupts. */
critical_exit();
/* Spin. */
critical_enter();
}
critical_exit();
continue;
}
sleep(td);
mutex_unlock_spin(&sched_lock);
}
The code above does not use any test-and-set instructions, nor does it
keep bumping the priority of the owner during spinning.
--
Seigo Tanimura <[EMAIL PROTECTED]> <[EMAIL PROTECTED]>
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message
Re: preemption across processors
> The prototype patch is at: > > http://people.FreeBSD.org/~tanimura/patches/ippreempt.diff.gz > > And the p4 depot > > //depot/user/tanimura/ippreempt/... > > The patch is for only i386 at the moment. > > The following is the brief description of the patch: I would prefer that this was hung off the preemption stuff I've already done rather than reinventing it. I would also prefer that we get a preemptive kernel w/o this done stable before adding extra complication. > Miscellaneous stuff: > > If a thread spins for an adaptive mutex, propagate its priority to the > owner thread of the mutex. This prevents preemption of the owner > thread by a thread with the priority in between the owner thread and > the spinning thread. Ewww, I'd rather avoid this if possible. This is just an optimization, but it would depend on how complicated this makes the mutex code to see if it's worth it or not. -- John Baldwin <[EMAIL PROTECTED]> <>< http://www.FreeBSD.org/~jhb/ "Power Users Use the Power to Serve!" - http://www.FreeBSD.org/ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: preemption across processors
On Wed, 15 May 2002 08:21:46 -0400 (EDT),
John Baldwin <[EMAIL PROTECTED]> said:
jhb> On 15-May-2002 Seigo Tanimura wrote:
>> Currently, a new runnable thread cannot preempt the thread on any
>> processor other than the thread that called mi_switch(). For
>> instance, we do something like the following in _mtx_unlock_sleep():
>>
>> --- v --- _mtx_unlock_sleep() --- v ---
>> setrunqueue(th_waken_up);
>> if (curthread->preemptable && th_waken_up->priority < curthread->priority) {
>> setrunqueue(curthread);
>> mi_switch();
>> }
>> --- ^ --- _mtx_unlock_sleep() --- ^ ---
>>
>> If the priority of curthread is higher than th_waken_up, we cannot run
>> it immediately even if there is another processor running a thread
>> with a priority lower than th_waken_up. th_waken_up should preempt
>> that processor, or we would end up with a priority inversion.
>>
>> Maybe we have to dispatch a runnable thread to the processor running
>> a thread with the lowest priority. Solaris seems to take the
>> following steps to do that:
>>
>> 1. If a new thread has slept for longer than 3/100 seconds (this
>> should be tunable), linearly search the processor running a thread
>> with the lowest priority. Otherwise, choose the processor that ran
>> the new thread most recently.
>>
>> 2. Make an inter-processor interrupt to the processor chosen in 1.
>>
>> 3. The chosen processor puts its current thread back to the dispatch
>> queue and performs a context switch to run the new thread.
>>
>> Above is only a rough sketch. We have to watch out for a race of
>> inter-processor interrupts and a processor entering a critical section.
>>
>> If no one is working on preemption across processors, I would like to
>> see if I can do that.
jhb> I actually think that the little gain this brings isn't worth the extra
jhb> effort involved personally. We don't have to get things perfect, getting
jhb> them reasonably close is good enough for some things. However, that is
jhb> only my opinion. If the code to support this is relatively clean and
jhb> simple with low-impact in the normal case then I would support it. However,
jhb> there are several tricky race conditions here so I'm not sure it can be
jhb> done simply.
The prototype patch is at:
http://people.FreeBSD.org/~tanimura/patches/ippreempt.diff.gz
And the p4 depot
//depot/user/tanimura/ippreempt/...
The patch is for only i386 at the moment.
The following is the brief description of the patch:
--- v --- Description --- v ---
Overview:
setrunqueue() finds for a newly runnable thread the processor running
the thread with the lowest priority by chooseprocessor(). setrunqueue()
then marks the priority of the new thread on the processor chosen for
preemption.
If the processor chosen is not the current processor, setrunqueue()
notifies the processor by making a preemption IPI to the processor
chosen, where the IPI handler calls dispatchthread(). If the current
processor is chosen for preemption, setrunqueue() directly calls
dispatchthread().
dispatchthread() grabs the thread with the highest priority from the
run queue. If the current thread is running and has a higher priority
than the thread grabbed, dispatchthread() returns. Otherwise,
dispatchthread() puts the current thread back to the run queue (if it
is not an idle thread) and switches to the thread grabbed. If the
current thread is going to sleep, (i.e. its state is SSLEEP, SSTOP,
etc.) we always switch to the thread grabbed.
Implementation:
Call dispatchthread() instead of mi_switch() in msleep(), cv_*wait*(),
etc. in order to give up the current processor.
setrunqueue() no longer requires maybe_resched() in wakeup() and the
preemption check in _mtx_unlock_sleep(). If it is not appropriate to
preempt the current processor, call setrunqueue() in a critical
section. Note that setrunqueue() may dispatch the thread passed to a
processor other than the current one.
Miscellaneous stuff:
If a thread spins for an adaptive mutex, propagate its priority to the
owner thread of the mutex. This prevents preemption of the owner
thread by a thread with the priority in between the owner thread and
the spinning thread.
In order to make a space in the IPI priority for a preemption IPI,
raise the IPI priority of Xcpustop and Xinvltlb by one.
An idle processor no longer has to check whether or not there is a
runnable thread. Halt an idle processor in an SMP kernel as in a UP
kernel.
--- ^ --- Description --- ^ ---
The time taken for configuring, depending, compiling and linking a
GENERIC kernel was measured by time(1) for the vanilla kernel and the
patched one. Both of the kernels omit INVARIANTS, INVARIANT_SUPPORT
and WITNESS*.
RE: preemption across processors
On 15-May-2002 Seigo Tanimura wrote:
> Currently, a new runnable thread cannot preempt the thread on any
> processor other than the thread that called mi_switch(). For
> instance, we do something like the following in _mtx_unlock_sleep():
>
> --- v --- _mtx_unlock_sleep() --- v ---
> setrunqueue(th_waken_up);
> if (curthread->preemptable && th_waken_up->priority < curthread->priority) {
> setrunqueue(curthread);
> mi_switch();
> }
> --- ^ --- _mtx_unlock_sleep() --- ^ ---
>
> If the priority of curthread is higher than th_waken_up, we cannot run
> it immediately even if there is another processor running a thread
> with a priority lower than th_waken_up. th_waken_up should preempt
> that processor, or we would end up with a priority inversion.
>
> Maybe we have to dispatch a runnable thread to the processor running
> a thread with the lowest priority. Solaris seems to take the
> following steps to do that:
>
> 1. If a new thread has slept for longer than 3/100 seconds (this
>should be tunable), linearly search the processor running a thread
>with the lowest priority. Otherwise, choose the processor that ran
>the new thread most recently.
>
> 2. Make an inter-processor interrupt to the processor chosen in 1.
>
> 3. The chosen processor puts its current thread back to the dispatch
>queue and performs a context switch to run the new thread.
>
> Above is only a rough sketch. We have to watch out for a race of
> inter-processor interrupts and a processor entering a critical section.
>
> If no one is working on preemption across processors, I would like to
> see if I can do that.
I actually think that the little gain this brings isn't worth the extra
effort involved personally. We don't have to get things perfect, getting
them reasonably close is good enough for some things. However, that is
only my opinion. If the code to support this is relatively clean and
simple with low-impact in the normal case then I would support it. However,
there are several tricky race conditions here so I'm not sure it can be
done simply.
--
John Baldwin <[EMAIL PROTECTED]> <>< http://www.FreeBSD.org/~jhb/
"Power Users Use the Power to Serve!" - http://www.FreeBSD.org/
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message
preemption across processors
Currently, a new runnable thread cannot preempt the thread on any
processor other than the thread that called mi_switch(). For
instance, we do something like the following in _mtx_unlock_sleep():
--- v --- _mtx_unlock_sleep() --- v ---
setrunqueue(th_waken_up);
if (curthread->preemptable && th_waken_up->priority < curthread->priority) {
setrunqueue(curthread);
mi_switch();
}
--- ^ --- _mtx_unlock_sleep() --- ^ ---
If the priority of curthread is higher than th_waken_up, we cannot run
it immediately even if there is another processor running a thread
with a priority lower than th_waken_up. th_waken_up should preempt
that processor, or we would end up with a priority inversion.
Maybe we have to dispatch a runnable thread to the processor running
a thread with the lowest priority. Solaris seems to take the
following steps to do that:
1. If a new thread has slept for longer than 3/100 seconds (this
should be tunable), linearly search the processor running a thread
with the lowest priority. Otherwise, choose the processor that ran
the new thread most recently.
2. Make an inter-processor interrupt to the processor chosen in 1.
3. The chosen processor puts its current thread back to the dispatch
queue and performs a context switch to run the new thread.
Above is only a rough sketch. We have to watch out for a race of
inter-processor interrupts and a processor entering a critical section.
If no one is working on preemption across processors, I would like to
see if I can do that.
Thanks.
--
Seigo Tanimura <[EMAIL PROTECTED]> <[EMAIL PROTECTED]>
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message
