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*. The spec of the test machine is: CPU:dual Pentium II 450MHz RAM:256MB HDD:one IDE 2GB Tests were done in the single-user mode immediately after reboot. Make(1) was run with -j16 for compilation and linking by the kernel-depend target. The following results are the average
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