2 * Copyright (c) 2023 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * 3. Neither the name of The DragonFly Project nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific, prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * DragonFly implementation of the FreeBSD sleepq*() API. FreeBSD's sleepq*()
36 * API differs from our tsleep*() API in several major ways.
38 * ONLY USE THIS FOR FREEBSD COMPATIBILITY, E.G. THE LINUX KPI
40 * - Explicit interlock via sleepq_lock(wchan)
41 * - Single global wchan hash table
42 * - Explicit blocking counts
43 * - Expects all blockers on the same wchan to be of the same type
45 * In addition, the API calls have a ton of unnecessary redundancy which
46 * creates problems with using on-stack structures for things. To make
47 * ends meat, DragonFly records information in the thread structure and
48 * only enacts the actual operation when the thread issues a *wait*() API
49 * call. Only the spin interlock is handled in real-time.
54 #include <sys/cdefs.h>
55 #include <sys/param.h>
56 #include <sys/systm.h>
59 #include <sys/malloc.h>
60 #include <sys/queue.h>
61 #include <sys/sleepqueue.h>
62 #include <sys/objcache.h>
63 #include <sys/sysctl.h>
67 #include <machine/atomic.h>
73 #include <sys/signal2.h>
74 #include <sys/thread2.h>
75 #include <sys/spinlock2.h>
76 #include <sys/mutex2.h>
78 #include <vm/vm_extern.h>
80 #define SLEEPQ_HSIZE 1024
81 #define SLEEPQ_HMASK (SLEEPQ_HSIZE - 1)
82 #define SLEEPQ_HASH(wchan) ((((uintptr_t)(wchan) >> 10) ^ \
83 ((uintptr_t)(wchan) & SLEEPQ_HMASK)))
85 #define SLEEPQ_LOOKUP(wchan) &sleepq_chains[SLEEPQ_HASH(wchan)]
86 #define SLEEPQ_NRQUEUES 2
87 #define SLEEPQ_FREEPERSLOT 4
89 struct sleepqueue_wchan
;
91 struct sleepqueue_chain
{
92 struct spinlock sc_spin
;
93 TAILQ_HEAD(, sleepqueue_wchan
) sc_wchead
;
97 struct sleepqueue_wchan
{
98 TAILQ_ENTRY(sleepqueue_wchan
) wc_entry
;
100 struct sleepqueue_chain
*wc_sc
;
103 u_int wc_blocked
[SLEEPQ_NRQUEUES
];
106 static struct sleepqueue_chain sleepq_chains
[SLEEPQ_HSIZE
];
107 static MALLOC_DEFINE(M_SLEEPQ
, "sleepq", "fbsd sleepq api");
108 static struct objcache
*sleepq_wc_cache
;
111 * Return existing wchan, assert not NULL.
114 struct sleepqueue_wchan
*
115 sleepq_wclookup(const void *wchan
)
117 struct sleepqueue_chain
*sc
;
118 struct sleepqueue_wchan
*wc
;
120 sc
= SLEEPQ_LOOKUP(wchan
);
121 KKASSERT(spin_held(&sc
->sc_spin
));
122 TAILQ_FOREACH(wc
, &sc
->sc_wchead
, wc_entry
) {
123 if (wc
->wc_wchan
== wchan
)
126 panic("sleepq_wclookup: wchan %p not found\n", wc
);
128 return NULL
; /* not reached */
132 * Early initialization of sleep queues
135 init_sleepqueues(void)
139 for (i
= 0; i
< SLEEPQ_HSIZE
; ++i
) {
140 spin_init(&sleepq_chains
[i
].sc_spin
, "sleepq");
141 TAILQ_INIT(&sleepq_chains
[i
].sc_wchead
);
143 /*thread0.td_sleepqueue = sleepq_alloc();*/
145 sleepq_wc_cache
= objcache_create_simple(M_SLEEPQ
,
146 sizeof(struct sleepqueue_wchan
));
149 SYSINIT(sysinit_sleepqueues
, SI_BOOT2_LWKT_INIT
, SI_ORDER_SECOND
,
150 init_sleepqueues
, NULL
);
153 * DragonFlyBSD Interface Functions
155 * Setup and teardown sleepq related thread structures
157 * sleepq_alloc() - not applicable
158 * sleepq_free() - not applicable
161 sleepq_setup_thread(struct thread
*td
)
166 sleepq_teardown_thread(struct thread
*td
)
171 * Lock the wchan, creating the structure if necessary. Returns with
172 * the spin-lock held.
174 * Also used as an interlock, so we need to actually lock something here.
177 sleepq_lock(const void *wchan
)
179 struct sleepqueue_chain
*sc
;
180 struct sleepqueue_wchan
*wc
;
182 sc
= SLEEPQ_LOOKUP(wchan
);
183 spin_lock(&sc
->sc_spin
);
187 * Look for the wchan, if not found then allocate one from
188 * the existing in-list cache if available.
190 TAILQ_FOREACH(wc
, &sc
->sc_wchead
, wc_entry
) {
191 if (wc
->wc_wchan
== wchan
) {
195 if (wc
->wc_wchan
== NULL
) {
196 wc
->wc_wchan
= wchan
;
204 * Not found and no free entries available, allocate
205 * a new, free wc, then relock and repeat the search.
207 spin_unlock(&sc
->sc_spin
);
208 wc
= objcache_get(sleepq_wc_cache
, M_WAITOK
);
209 KKASSERT(wc
->wc_wchan
== NULL
&& wc
->wc_refs
== 0);
211 spin_lock(&sc
->sc_spin
);
212 TAILQ_INSERT_TAIL(&sc
->sc_wchead
, wc
, wc_entry
);
219 * Unlock the sleep queue chain associated with a given wait channel.
222 sleepq_release(const void *wchan
)
224 struct sleepqueue_chain
*sc
;
225 struct sleepqueue_wchan
*wc
;
227 wc
= sleepq_wclookup(wchan
);
229 KKASSERT(wc
->wc_refs
> 0);
230 if (--wc
->wc_refs
== 0) {
231 /* just sanity-check one for brevity */
232 KKASSERT(wc
->wc_blocked
[0] == 0);
238 spin_unlock(&sc
->sc_spin
);
242 * Place the current thread on the specified wait channel and sub-queue.
244 * The caller must be holding the wchan lock and it will remain locked
245 * on return. The caller must follow-up with a sleepq_*wait*() call.
247 * If INVARIANTS is enabled, then it associates the passed in lock with
248 * the sleepq to make sure it is held when that sleep queue is woken up
249 * (XXX not implemented)
252 sleepq_add(const void *wchan
, struct lock_object
*lock
, const char *wmesg
,
253 int flags
, int queue
)
255 struct sleepqueue_wchan
*wc
;
260 * Locate the wc (also asserts that the lock is held). Bump
261 * wc->wc_refs and wc->wc_blocked[queue] to indicate that the
262 * thread has been placed on the sleepq.
264 wc
= sleepq_wclookup(wchan
);
266 ++wc
->wc_blocked
[queue
];
267 wc
->wc_type
= flags
& SLEEPQ_TYPE
;
270 * tsleep_interlock() sets TDF_TSLEEPQ, sets td_wchan, and td_wdomain,
271 * and places the thread on the appropriate sleepq.
274 td
->td_wmesg
= wmesg
;
275 domain
= PDOMAIN_FBSD0
+ queue
* PDOMAIN_FBSDINC
;
276 tsleep_interlock(wchan
, domain
);
279 * Clear timeout to discern a possible later sleepq_set_timeout_sbt()
284 td
->td_sqqueue
= queue
;
288 * Set a timeout for the thread after it has been added to a wait channel.
291 sleepq_set_timeout_sbt(const void *wchan
, sbintime_t sbt
, sbintime_t pr
,
294 struct sleepqueue_wchan
*wc
;
299 KKASSERT(wc
&& wc
->wc_wchan
== wchan
);
300 td
->td_sqtimo
= sbticks
+ sbt
;
304 * Return the number of actual sleepers for the specified queue.
306 * Caller must be holding the wchan locked
309 sleepq_sleepcnt(const void *wchan
, int queue
)
311 struct sleepqueue_wchan
*wc
;
313 wc
= sleepq_wclookup(wchan
);
314 return (wc
->wc_blocked
[queue
]);
319 _sleepq_wait_begin(struct thread
*td
, struct sleepqueue_chain
*sc
,
320 struct sleepqueue_wchan
*wc
, sbintime_t timo
, int tflags
)
325 spin_unlock(&sc
->sc_spin
);
327 domain
= PDOMAIN_FBSD0
+ td
->td_sqqueue
* PDOMAIN_FBSDINC
;
331 ret
= tsleep(td
->td_wchan
, tflags
, td
->td_wmesg
, timo
);
336 ret
= tsleep(td
->td_wchan
, tflags
, td
->td_wmesg
, 0);
343 * Wait for completion
347 _sleepq_wait_complete(struct thread
*td
, struct sleepqueue_chain
*sc
,
348 struct sleepqueue_wchan
*wc
)
350 struct sleepqueue_wchan
*wcn
;
353 spin_lock(&sc
->sc_spin
);
354 --wc
->wc_blocked
[td
->td_sqqueue
];
355 if (--wc
->wc_refs
== 0) {
359 if (sc
->sc_free_count
<= SLEEPQ_FREEPERSLOT
) {
360 wcn
= TAILQ_NEXT(wc
, wc_entry
);
361 if (wcn
&& wcn
->wc_wchan
) {
362 TAILQ_REMOVE(&sc
->sc_wchead
, wc
, wc_entry
);
363 TAILQ_INSERT_TAIL(&sc
->sc_wchead
, wc
, wc_entry
);
365 spin_unlock(&sc
->sc_spin
);
368 TAILQ_REMOVE(&sc
->sc_wchead
, wc
, wc_entry
);
369 spin_unlock(&sc
->sc_spin
);
370 objcache_put(sleepq_wc_cache
, wc
);
373 spin_unlock(&sc
->sc_spin
);
378 * Various combinations of wait until unblocked, with and without
379 * signaling and timeouts.
381 * The wchan lock must be held by the caller and will be released upon
384 * NOTE: tsleep_interlock() was already issued by sleepq_add().
387 sleepq_wait(const void *wchan
, int pri
)
389 struct sleepqueue_chain
*sc
;
390 struct sleepqueue_wchan
*wc
;
395 KKASSERT(wc
!= NULL
&& wc
->wc_wchan
== wchan
);
398 (void)_sleepq_wait_begin(td
, sc
, wc
, 0, PINTERLOCKED
);
399 _sleepq_wait_complete(td
, sc
, wc
);
403 sleepq_wait_sig(const void *wchan
, int pri
)
405 struct sleepqueue_chain
*sc
;
406 struct sleepqueue_wchan
*wc
;
412 KKASSERT(wc
!= NULL
&& wc
->wc_wchan
== wchan
);
415 ret
= _sleepq_wait_begin(td
, sc
, wc
, 0, PINTERLOCKED
| PCATCH
);
416 _sleepq_wait_complete(td
, sc
, wc
);
422 sleepq_timedwait(const void *wchan
, int pri
)
424 struct sleepqueue_chain
*sc
;
425 struct sleepqueue_wchan
*wc
;
431 KKASSERT(wc
!= NULL
&& wc
->wc_wchan
== wchan
);
434 ret
= _sleepq_wait_begin(td
, sc
, wc
, td
->td_sqtimo
, PINTERLOCKED
);
435 _sleepq_wait_complete(td
, sc
, wc
);
441 sleepq_timedwait_sig(const void *wchan
, int pri
)
443 struct sleepqueue_chain
*sc
;
444 struct sleepqueue_wchan
*wc
;
450 KKASSERT(wc
!= NULL
&& wc
->wc_wchan
== wchan
);
453 ret
= _sleepq_wait_begin(td
, sc
, wc
, td
->td_sqtimo
,
454 PINTERLOCKED
| PCATCH
);
455 _sleepq_wait_complete(td
, sc
, wc
);
461 * Returns the type of sleepqueue given a waitchannel. Returns 0 if
462 * sleepq_add() has not been called no the wchan.
464 * wchan must be locked.
467 sleepq_type(const void *wchan
)
469 struct sleepqueue_wchan
*wc
;
472 wc
= sleepq_wclookup(wchan
);
479 * Wakeup one thread sleeping on a wait channel.
481 * DragonFly: Presumably callers also deal with multiple wakeups,
482 * our wakeup_domaoin_one() function is a bit non-deterministic.
484 * Nominally returns whether the swapper should be woken up which
485 * is not applicable to DragonFlyBSD.
488 sleepq_signal(const void *wchan
, int flags
, int pri
, int queue
)
492 domain
= PDOMAIN_FBSD0
+ queue
* PDOMAIN_FBSDINC
;
493 wakeup_domain_one(wchan
, domain
);
499 * Resume everything sleeping on the specified wait channel and queue.
501 * Nominally returns whether the swapper should be woken up which is not
502 * applicable to DragonFlyBSD.
505 sleepq_broadcast(const void *wchan
, int flags
, int pri
, int queue
)
509 domain
= PDOMAIN_FBSD0
+ queue
* PDOMAIN_FBSDINC
;
510 wakeup_domain(wchan
, domain
);