1/*-
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright (c) 2010 David Xu <davidxu@freebsd.org>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice unmodified, this list of conditions, and the following
12 *    disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#include <stdlib.h>
30#include "thr_private.h"
31
32#define HASHSHIFT	9
33#define HASHSIZE	(1 << HASHSHIFT)
34#define SC_HASH(wchan) ((unsigned)				\
35	((((uintptr_t)(wchan) >> 3)				\
36	^ ((uintptr_t)(wchan) >> (HASHSHIFT + 3)))		\
37	& (HASHSIZE - 1)))
38#define SC_LOOKUP(wc)	&sc_table[SC_HASH(wc)]
39
40struct sleepqueue_chain {
41	struct umutex		sc_lock;
42	int			sc_enqcnt;
43	LIST_HEAD(, sleepqueue) sc_queues;
44	int			sc_type;
45};
46
47static struct sleepqueue_chain  sc_table[HASHSIZE];
48
49void
50_sleepq_init(void)
51{
52	int	i;
53
54	for (i = 0; i < HASHSIZE; ++i) {
55		LIST_INIT(&sc_table[i].sc_queues);
56		_thr_umutex_init(&sc_table[i].sc_lock);
57	}
58}
59
60struct sleepqueue *
61_sleepq_alloc(void)
62{
63	struct sleepqueue *sq;
64
65	sq = calloc(1, sizeof(struct sleepqueue));
66	TAILQ_INIT(&sq->sq_blocked);
67	SLIST_INIT(&sq->sq_freeq);
68	return (sq);
69}
70
71void
72_sleepq_free(struct sleepqueue *sq)
73{
74	free(sq);
75}
76
77void
78_sleepq_lock(void *wchan)
79{
80	struct pthread *curthread = _get_curthread();
81	struct sleepqueue_chain *sc;
82
83	sc = SC_LOOKUP(wchan);
84	THR_LOCK_ACQUIRE_SPIN(curthread, &sc->sc_lock);
85}
86
87void
88_sleepq_unlock(void *wchan)
89{
90	struct sleepqueue_chain *sc;
91	struct pthread *curthread = _get_curthread();
92
93	sc = SC_LOOKUP(wchan);
94	THR_LOCK_RELEASE(curthread, &sc->sc_lock);
95}
96
97static inline struct sleepqueue *
98lookup(struct sleepqueue_chain *sc, void *wchan)
99{
100	struct sleepqueue *sq;
101
102	LIST_FOREACH(sq, &sc->sc_queues, sq_hash)
103		if (sq->sq_wchan == wchan)
104			return (sq);
105	return (NULL);
106}
107
108struct sleepqueue *
109_sleepq_lookup(void *wchan)
110{
111	return (lookup(SC_LOOKUP(wchan), wchan));
112}
113
114void
115_sleepq_add(void *wchan, struct pthread *td)
116{
117	struct sleepqueue_chain *sc;
118	struct sleepqueue *sq;
119
120	sc = SC_LOOKUP(wchan);
121	sq = lookup(sc, wchan);
122	if (sq != NULL) {
123		SLIST_INSERT_HEAD(&sq->sq_freeq, td->sleepqueue, sq_flink);
124	} else {
125		sq = td->sleepqueue;
126		LIST_INSERT_HEAD(&sc->sc_queues, sq, sq_hash);
127		sq->sq_wchan = wchan;
128		/* sq->sq_type = type; */
129	}
130	td->sleepqueue = NULL;
131	td->wchan = wchan;
132	if (((++sc->sc_enqcnt << _thr_queuefifo) & 0xff) != 0)
133		TAILQ_INSERT_HEAD(&sq->sq_blocked, td, wle);
134	else
135		TAILQ_INSERT_TAIL(&sq->sq_blocked, td, wle);
136}
137
138int
139_sleepq_remove(struct sleepqueue *sq, struct pthread *td)
140{
141	int rc;
142
143	TAILQ_REMOVE(&sq->sq_blocked, td, wle);
144	if (TAILQ_EMPTY(&sq->sq_blocked)) {
145		LIST_REMOVE(sq, sq_hash);
146		td->sleepqueue = sq;
147		rc = 0;
148	} else {
149		td->sleepqueue = SLIST_FIRST(&sq->sq_freeq);
150		SLIST_REMOVE_HEAD(&sq->sq_freeq, sq_flink);
151		rc = 1;
152	}
153	td->wchan = NULL;
154	return (rc);
155}
156
157void
158_sleepq_drop(struct sleepqueue *sq,
159	void (*cb)(struct pthread *, void *arg), void *arg)
160{
161	struct pthread *td;
162	struct sleepqueue *sq2;
163
164	td = TAILQ_FIRST(&sq->sq_blocked);
165	if (td == NULL)
166		return;
167	LIST_REMOVE(sq, sq_hash);
168	TAILQ_REMOVE(&sq->sq_blocked, td, wle);
169	if (cb != NULL)
170		cb(td, arg);
171	td->sleepqueue = sq;
172	td->wchan = NULL;
173	sq2 = SLIST_FIRST(&sq->sq_freeq);
174	TAILQ_FOREACH(td, &sq->sq_blocked, wle) {
175		if (cb != NULL)
176			cb(td, arg);
177		td->sleepqueue = sq2;
178		td->wchan = NULL;
179		sq2 = SLIST_NEXT(sq2, sq_flink);
180	}
181	TAILQ_INIT(&sq->sq_blocked);
182	SLIST_INIT(&sq->sq_freeq);
183}
184