CVS log for src/sys/kern/kern_turnstile.c

Up to [cvs.NetBSD.org] / src / sys / kern

Request diff between arbitrary revisions

Keyword substitution: kv
Default branch: MAIN

kern_turnstile.c: Use <sys/lwp.h> explicitly for struct lwp members.

sys/lwp.h: Nix sys/syncobj.h dependency.

Remove it in ddb/db_syncobj.h too.

New sys/wchan.h defines wchan_t so that users need not pull in
sys/syncobj.h to get it.

Sprinkle #include <sys/syncobj.h> in .c files where it is now needed.

Ensure that an LWP that has taken a legitimate wakeup never produces an
error code from sleepq_block().  Then, it's possible to make cv_signal()
work as expected and only ever wake a singular LWP.

Turnstiles: use the syncobj name for ps/top wmesg when sleeping since it's
more informative than "tstile".

Eliminate l->l_biglocks.  Originally I think it had a use but these days a
local variable will do.

- Simplify how priority boost for blocking in kernel is handled.  Rather
  than setting it up at each site where we block, make it a property of
  syncobj_t.  Then, do not hang onto the priority boost until userret(),
  drop it as soon as the LWP is out of the run queue and onto a CPU.
  Holding onto it longer is of questionable benefit.

- This allows two members of lwp_t to be deleted, and mi_userret() to be
  simplified a lot (next step: trim it down to a single conditional).

- While here, constify syncobj_t and de-inline a bunch of small functions
  like lwp_lock() which turn out not to be small after all (I don't know
  why, but atomic_*_relaxed() seem to provoke a compiler shitfit above and
  beyond what volatile does).

Repply this change with a couple of bugs fixed:

- Do away with separate pool_cache for some kernel objects that have no special
  requirements and use the general purpose allocator instead. On one of my
  test systems this makes for a small (~1%) but repeatable reduction in system
  time during builds presumably because it decreases the kernel's cache /
  memory bandwidth footprint a little.
- vfs_lockf: cache a pointer to the uidinfo and put mutex in the data segment.

Back out recent change to replace pool_cache with then general allocator.
Will return to this when I have time again.

- Do away with separate pool_cache for some kernel objects that have no special
  requirements and use the general purpose allocator instead.  On one of my
  test systems this makes for a small (~1%) but repeatable reduction in system
  time during builds presumably because it decreases the kernel's cache /
  memory bandwidth footprint a little.
- vfs_lockf: cache a pointer to the uidinfo and put mutex in the data segment.

kern: KASSERT(A && B) -> KASSERT(A); KASSERT(B)

kern/kern_turnstile.c: Get turnstile0 from sys/sleeptab.h.

sleepq(9): Pass syncobj through to sleepq_block.

Previously the usage pattern was:

sleepq_enter(sq, l, lock);              // locks l
...
sleepq_enqueue(sq, ..., sobj, ...);     // assumes l locked, sets l_syncobj
... (*)
sleepq_block(...);			// unlocks l

As long as l remains locked from sleepq_enter to sleepq_block,
l_syncobj is stable, and sleepq_block uses it via ktrcsw to determine
whether the sleep is on a mutex in order to avoid creating ktrace
context-switch records (which involves allocation which is forbidden
in softint context, while taking and even sleeping for a mutex is
allowed).

However, in turnstile_block, the logic at (*) also involves
turnstile_lendpri, which sometimes unlocks and relocks l.  At that
point, another thread can swoop in and sleepq_remove l, which sets
l_syncobj to sched_syncobj.  If that happens, ktrcsw does what is
forbidden -- tries to allocate a ktrace record for the context
switch.

As an optimization, sleepq_block or turnstile_block could stop early
if it detects that l_syncobj doesn't match -- we've already been
requested to wake up at this point so there's no need to mi_switch.
(And then it would be unnecessary to pass the syncobj through
sleepq_block, because l_syncobj would remain stable.)  But I'll leave
that to another change.

Reported-by: syzbot+8b9d7b066c32dbcdc63b@syzkaller.appspotmail.com

s/grabing/grabbing/ in comments.

kern: Handle l_mutex with atomic_store_release, atomic_load_consume.

- Where the lock is held and known to be correct, no atomic.
- In loops to acquire the lock, use atomic_load_relaxed before we
  restart with atomic_load_consume.

Nix membar_exit.

(Who knows, using atomic_load_consume here might fix bugs on Alpha!)

fix various typos in comments, mainly immediatly/immediately/,
as well shared and recently fixed typos in OpenBSD code by Jonathan Grey.

- Replace pid_table_lock with a lockless lookup covered by pserialize, with
  the "writer" side being pid_table expansion.  The basic idea is that when
  doing an LWP lookup there is usually already a lock held (p->p_lock), or a
  spin mutex that needs to be taken (l->l_mutex), and either can be used to
  get the found LWP stable and confidently determine that all is correct.

- For user processes LSLARVAL implies the same thing as LSIDL ("not visible
  by ID"), and lookup by ID in proc0 doesn't really happen.  In-tree the new
  state should be understood by top(1), the tty subsystem and so on, and
  would attract the attention of 3rd party kernel grovellers in time, so
  remove it and just rely on LSIDL.

Sync with HEAD

Sync with HEAD

Set LW_SINTR earlier so it doesn't pose a problem for doing interruptable
waits with turnstiles (not currently done).

Merge changes from current as of 20200406

TAILQ -> LIST

Change sleepq_t from a TAILQ to a LIST and remove SOBJ_SLEEPQ_FIFO.  Only
select/poll used the FIFO method and that was for collisions which rarely
occur.  Shrinks sleep_t and condvar_t.

Sync with head.

ddb's "show all locks":

- Make the output easier to scan quickly.

- Show every LWP that is blocked on a lock, and the details of the lock.

Just make the turnstile locks statics and avoid the indirect reference
since COHERENCY_UNIT does the right thing in !MP.

Put section attribute for turnstile0 in the correct place.  For LLVM.

Sleep queues & turnstiles:

- Avoid false sharing.
- Make the turnstile hash function more suitable.
- Increase turnstile hash table size.
- Make amends by having only one set of system wide sleep queue hash locks.

sync with head

comments and assertions.
no functional changes.

sync with head

move priority inheritance code to separate functions

These don't need uvm/uvm_extern.h.

Sync with HEAD.

sync with head

Sprinkle __cacheline_aligned and __read_mostly, make some functions static.

sync to netbsd-5

sync with head

turnstile_block: reduce code duplication.

turnstile_block: turn a comment into KASSERTs.

Remove uarea swap-out functionality:

- Addresses the issue described in PR/38828.
- Some simplification in threading and sleepq subsystems.
- Eliminates pmap_collect() and, as a side note, allows pmap optimisations.
- Eliminates XS_CTL_DATA_ONSTACK in scsipi code.
- Avoids few scans on LWP list and thus potentially long holds of proc_lock.
- Cuts ~1.5k lines of code.  Reduces amd64 kernel size by ~4k.
- Removes __SWAP_BROKEN cases.

Tested on x86, mips, acorn32 (thanks <mpumford>) and partly tested on
acorn26 (thanks to <bjh21>).

Discussed on <tech-kern>, reviewed by <ad>.

Pull up following revision(s) (requested by bouyer in ticket #1028):
	sys/kern/kern_turnstile.c: revision 1.25 via patch
PR kern/41923: assertion "cur != owner" failed
In the for(;;) loop of turnstile_block(), the lock owner can change while
cur's lock is released (cur's lock is also the tschain_t's mutex).
Remove the KASSERT about owner being invariant and try to deal with the
fact that the owner can change instead.
http://mail-index.netbsd.org/tech-kern/2009/08/24/msg005957.html
and followups.

sync with head

PR kern/41923: assertion "cur != owner" failed
In the for(;;) loop of turnstile_block(), the lock owner can change while
cur's lock is released (cur's lock is also the tschain_t's mutex).
Remove the KASSERT about owner being invariant and try to deal with the
fact that the owner can change instead.
http://mail-index.netbsd.org/tech-kern/2009/08/24/msg005957.html
and followups.

Sync with HEAD.

Commit is split, to avoid a "too many arguments" protocol error.

sync with head.

Sync with HEAD.

Allocate sleep queue locks with mutex_obj_alloc. Reduces memory usage
on !MP kernels, and reduces false sharing on MP ones.

Sync with HEAD.

Sync with HEAD.

Sync with wrstuden-revivesa-base-2.

turnstile_block(): When an LWP puts its turnstile onto a sync object's
turnstile chain, assert that its turnstile's free list pointer is NULL.

Sync w/ -current. 34 merge conflicts to follow.

sync with head

Sync with HEAD.

Add a comment to turnstile_block:

        * NOTE: if you get a panic in this code block, it is likely that
        * a lock has been destroyed or corrupted while still in use.  Try
        * compiling a kernel with LOCKDEBUG to pinpoint the problem.

Take the mutex pointer and waiters count out of sleepq_t: the values can
be or are maintained elsewhere. Now a sleepq_t is just a TAILQ_HEAD.

sync with head.

sync with head.

Remove clause 3 and 4 from TNF licenses

Add MI code to support in-kernel preemption. Preemption is deferred by
one of the following:

- Holding kernel_lock (indicating that the code is not MT safe).
- Bracketing critical sections with kpreempt_disable/kpreempt_enable.
- Holding the interrupt priority level above IPL_NONE.

Statistics on kernel preemption are reported via event counters, and
where preemption is deferred for some reason, it's also reported via
lockstat. The LWP priority at which preemption is triggered is tuneable
via sysctl.

fix typo in comment

When a timeshared LWP blocks on a turnstile, elevate its priority into the
PRI_KTHREAD range. This is kind of ugly, but needed because of direct handoff
with rwlocks, and because threads that block holding a mutex regularly hold
other locks/resources.

Problem addressed: priority lending works well where a thread blocking on a
turnstile has a high priority level (eg realtime). For timeshared threads
(low priority) it's unlikely to have much effect. In the latter case threads
awoken from a turnstile can and do compete for CPU time with regular waits
like disk I/O. On MP systems this can result in a feedback loop where
threads cannot quickly get access to a resource held by a thread waking from
a turnstile. The waking thread eventually runs when enough of the other
threads block waiting for it, freeing up the CPU. The end result is a lot of
idle time during builds.

Sync with HEAD.

sync with head.

sync with head.

sync with HEAD

Add a boolean parameter to syncobj_t::sobj_unsleep. If true we want the
existing behaviour: the unsleep method unlocks and wakes the swapper if
needs be. If false, the caller is doing a batch operation and will take
care of that later. This is kind of ugly, but it's difficult for the caller
to know which lock to release in some situations.

sync with head.

Sync with HEAD.

Make schedstate_percpu::spc_lwplock an exernally allocated item. Remove
the hacks in sparc/cpu.c to reinitialize it. This should be in its own
cache line but that's another change.

sync with head

sync with HEAD

Sync with HEAD

Start detangling lock.h from intr.h. This is likely to cause short term
breakage, but the mess of dependencies has been regularly breaking the
build recently anyhow.

Sync with HEAD.

Sync with HEAD.

Sync with head.

sync with head

Match the docs: MUTEX_DRIVER/SPIN are now only for porting code written
for Solaris.

Sync with HEAD.

sync with head.

Sync with HEAD

Sync with HEAD.

sync with -HEAD

Merge from vmlocking:

- pool_cache changes.
- Debugger/procfs locking fixes.
- Other minor changes.

sync with HEAD

Sync with HEAD.

Merge scheduler changes from the vmlocking branch. All discussed on
tech-kern:

- Invert priority space so that zero is the lowest priority. Rearrange
  number and type of priority levels into bands. Add new bands like
  'kernel real time'.
- Ignore the priority level passed to tsleep. Compute priority for
  sleep dynamically.
- For SCHED_4BSD, make priority adjustment per-LWP, not per-process.

- Fix interactivity problems under high load. Beacuse soft interrupts
  are being stacked on top of regular LWPs, more often than not aston()
  was being called on a soft interrupt thread instead of a user thread,
  meaning that preemption was not happening on EOI.

- Don't use bool in a couple of data structures. Sub-word writes are not
  always atomic and may clobber other fields in the containing word.

- For SCHED_4BSD, make p_estcpu per thread (l_estcpu). Rework how the
  dynamic priority level is calculated - it's much better behaved now.

- Kill the l_usrpri/l_priority split now that priorities are no longer
  directly assigned by tsleep(). There are three fields describing LWP
  priority:

        l_priority: Dynamic priority calculated by the scheduler.
                This does not change for kernel/realtime threads,
                and always stays within the correct band. Eg for
                timeshared LWPs it never moves out of the user
                priority range. This is basically what l_usrpri
                was before.

        l_inheritedprio: Lent to the LWP due to priority inheritance
                (turnstiles).

        l_kpriority: A boolean value set true the first time an LWP
                sleeps within the kernel. This indicates that the LWP
                should get a priority boost as compensation for blocking.
                lwp_eprio() now does the equivalent of sched_kpri() if
                the flag is set. The flag is cleared in userret().

- Keep track of scheduling class (OTHER, FIFO, RR) in struct lwp, and use
  this to make decisions in a few places where we previously tested for a
  kernel thread.

- Partially fix itimers and usr/sys/intr time accounting in the presence
  of software interrupts.

- Use kthread_create() to create idle LWPs. Move priority definitions
  from the various modules into sys/param.h.

- newlwp -> lwp_create

sync with head.

Update for pool_cache API changes.

Sync with head.

Merge some of the less invasive changes from the vmlocking branch:

- kthread, callout, devsw API changes
- select()/poll() improvements
- miscellaneous MT safety improvements

Repair priority inheritance (broken by the changes to priority levels).

- Increase the number of thread priorities from 128 to 256. How the space
  is set up is to be revisited.
- Implement soft interrupts as kernel threads. A generic implementation
  is provided, with hooks for fast-path MD code that can run the interrupt
  threads over the top of other threads executing in the kernel.
- Split vnode::v_flag into three fields, depending on how the flag is
  locked (by the interlock, by the vnode lock, by the file system).
- Miscellaneous locking fixes and improvements.

Sync with head.

merge yamt-idlelwp branch.  asked by core@.  some ports still needs work.

from doc/BRANCHES:

	idle lwp, and some changes depending on it.

	1. separate context switching and thread scheduling.
	   (cf. gmcgarry_ctxsw)
	2. implement idle lwp.
	3. clean up related MD/MI interfaces.
	4. make scheduler(s) modular.

Assign a per-CPU lock to LWPs as they transition into the ONPROC state.

http://mail-index.netbsd.org/tech-kern/2007/05/06/0003.html

Pull up a change from the vmlocking branch:

- Ensure that LWPs going to sleep are on the sleep queue before releasing
  any interlocks. This is so that calls to turnstile_wakeup will have the
  correct locks held when adjusting priority. Avoids another deadlock.
- Assume that LWPs blocked on a turnstile will never be swapped out.
- LWPs blocking on a turnstile must have kernel priority, as they
  are consuming kernel resources.

- Nuke the seperate scheduler locking scheme for UP kernels - it has been
  at the root of too many bugs.
- Add a LW_BOUND flag that indicates an LWP is bound to a specific CPU.

sched_mutex -> spc_mutex.

sync with head.

- Ensure that that LWPs going to sleep are on the sleep queue and so
  have their syncobj pointer updated, so that calls to turnstile_wakeup
  will have the correct locks held when adjusting the current LWP's
  priority. Avoids another deadlock.
- Assume that LWPs blocked on a turnstile will never be swapped out.
- LWPs blocking on a turnstile must have kernel priority, as they
  are consuming kernel resources.

Sync with head.

turnstile_wakeup: when restoring inherited priority, only lock curlwp
if its lock is sched_mutex. We can arrive here while on a sleep queue
(from eg cv_wait) and so curlwp will already be locked.

Fix UP kernels. Having the different locking scheme for UP/MP is turning
out to be more hassle than it's worth...

sync with head.

Checkpoint:
- Abstract for per-CPU locking of runqueues.
  As a workaround for SCHED_4BSD global runqueue, covered by sched_mutex,
  spc_mutex is a pointer for now. After making SCHED_4BSD runqueues
  per-CPU, it will became a storage mutex.
- suspendsched: Locking is not necessary for cpu_need_resched().
- Remove mutex_spin_exit() prototype in patch.c and LOCK_ASSERT() check
  in runqueue_nextlwp() in sched_4bsd.c to make them compile again.

Sync with head.

Pass an ipl argument to pool_init/POOL_INIT to be used when initializing
the pool's lock.

- sync with head.
- move sched_changepri back to kern_synch.c as it doesn't know PPQ anymore.

typedef pri_t and use it instead of int and u_char.

turnstile_wakeup(): on a !MULTIPROCESSOR kernel the LWP is already locked.

implement priority inheritance.

sync with head.

Add uvm_kick_scheduler() (MP safe) to replace wakeup(&proc0).

Merge newlock2 to head.

- Change syncobj_t::sobj_changepri() to alter both the user priority and
  the effective priority of LWPs. How the effective priority is adjusted
  depends on the type of object.
- Add a couple of comments to sched_kpri() and remrunqueue().

Try to reduce cache line ping-ponging.

- Dump the contents of a lock's turnstile when an error is detected.
- Add a 'show lock' command to DDB.

Rename some functions to better describe what they do.

Checkpoint work in progress.

Checkpoint work in progress.

- Redo LWP locking slightly and fix some races.
- Fix some locking botches.
- Make signal mask / stack per-proc for SA processes.
- Add _lwp_kill().

Add a sleep queue implementation.

Add updated locking primatives.

Use a regular simplelock_t for the turnstile chain lock.

Add a "nextproc" argument to turnstile_wakeup() to selectively
wake up a single thread.  This will allow us to implement direct
handoff of rwlocks.

Make turnstiles actually have two queues (reader and writer).  Users
of turnsitles still don't differentiate between them.

Use <sys/simplelock.h> rather than <sys/lock.h>.

Pass a "pri" argument to turnstile_block(), like we do to ltsleep().
This allows the caller of turnstile_block() to decide what to do about
priority and PCATCH (though we still don't handle PCATCH in turnstiles).

Some suggestions from Bill Sommerfeld:
* Use a pool cache for turnstiles, so you can save the memset().  Add
  some asserts to make sure that inactive turnstiles end up in their
  freshly-constructed state.
* Invalidate p->p_ts before returning p to the proc pool (only done if
  DIAGNOSTIC).
* Fix up some comments in kern_turnstile.c
* Bugfix in turnstile_remque(): typo ("==" should have been "=").

TURNSTILE_CHAIN_UNLOCK(): Don't reference tc_oldspl after releasing
tc_lock.  From Bill Sommerfeld.

First cut implementation of turnstiles, a specialized sleep queue used for
kernel synchronization objects.  A detailed description of turnstiles
can be found in:

	Solaris Internals: Core Kernel Architecture, by Jim Mauro
	   and Richard McDougall, section 3.7.

Note this implementation does not yet implement priority inheritence,
nor does it currently differentiate between reader and writer queues
(though they are provided for in the API).

file kern_turnstile.c was initially added on branch newlock.