1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
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 <sys/cdefs.h>
30 __FBSDID("$FreeBSD: stable/12/lib/libthr/thread/thr_sleepq.c 326219 2017-11-26 02:00:33Z pfg $");
31
32 #include <stdlib.h>
33 #include "thr_private.h"
34
35 #define HASHSHIFT 9
36 #define HASHSIZE (1 << HASHSHIFT)
37 #define SC_HASH(wchan) ((unsigned) \
38 ((((uintptr_t)(wchan) >> 3) \
39 ^ ((uintptr_t)(wchan) >> (HASHSHIFT + 3))) \
40 & (HASHSIZE - 1)))
41 #define SC_LOOKUP(wc) &sc_table[SC_HASH(wc)]
42
43 struct sleepqueue_chain {
44 struct umutex sc_lock;
45 int sc_enqcnt;
46 LIST_HEAD(, sleepqueue) sc_queues;
47 int sc_type;
48 };
49
50 static struct sleepqueue_chain sc_table[HASHSIZE];
51
52 void
_sleepq_init(void)53 _sleepq_init(void)
54 {
55 int i;
56
57 for (i = 0; i < HASHSIZE; ++i) {
58 LIST_INIT(&sc_table[i].sc_queues);
59 _thr_umutex_init(&sc_table[i].sc_lock);
60 }
61 }
62
63 struct sleepqueue *
_sleepq_alloc(void)64 _sleepq_alloc(void)
65 {
66 struct sleepqueue *sq;
67
68 sq = calloc(1, sizeof(struct sleepqueue));
69 TAILQ_INIT(&sq->sq_blocked);
70 SLIST_INIT(&sq->sq_freeq);
71 return (sq);
72 }
73
74 void
_sleepq_free(struct sleepqueue * sq)75 _sleepq_free(struct sleepqueue *sq)
76 {
77 free(sq);
78 }
79
80 void
_sleepq_lock(void * wchan)81 _sleepq_lock(void *wchan)
82 {
83 struct pthread *curthread = _get_curthread();
84 struct sleepqueue_chain *sc;
85
86 sc = SC_LOOKUP(wchan);
87 THR_LOCK_ACQUIRE_SPIN(curthread, &sc->sc_lock);
88 }
89
90 void
_sleepq_unlock(void * wchan)91 _sleepq_unlock(void *wchan)
92 {
93 struct sleepqueue_chain *sc;
94 struct pthread *curthread = _get_curthread();
95
96 sc = SC_LOOKUP(wchan);
97 THR_LOCK_RELEASE(curthread, &sc->sc_lock);
98 }
99
100 static inline struct sleepqueue *
lookup(struct sleepqueue_chain * sc,void * wchan)101 lookup(struct sleepqueue_chain *sc, void *wchan)
102 {
103 struct sleepqueue *sq;
104
105 LIST_FOREACH(sq, &sc->sc_queues, sq_hash)
106 if (sq->sq_wchan == wchan)
107 return (sq);
108 return (NULL);
109 }
110
111 struct sleepqueue *
_sleepq_lookup(void * wchan)112 _sleepq_lookup(void *wchan)
113 {
114 return (lookup(SC_LOOKUP(wchan), wchan));
115 }
116
117 void
_sleepq_add(void * wchan,struct pthread * td)118 _sleepq_add(void *wchan, struct pthread *td)
119 {
120 struct sleepqueue_chain *sc;
121 struct sleepqueue *sq;
122
123 sc = SC_LOOKUP(wchan);
124 sq = lookup(sc, wchan);
125 if (sq != NULL) {
126 SLIST_INSERT_HEAD(&sq->sq_freeq, td->sleepqueue, sq_flink);
127 } else {
128 sq = td->sleepqueue;
129 LIST_INSERT_HEAD(&sc->sc_queues, sq, sq_hash);
130 sq->sq_wchan = wchan;
131 /* sq->sq_type = type; */
132 }
133 td->sleepqueue = NULL;
134 td->wchan = wchan;
135 if (((++sc->sc_enqcnt << _thr_queuefifo) & 0xff) != 0)
136 TAILQ_INSERT_HEAD(&sq->sq_blocked, td, wle);
137 else
138 TAILQ_INSERT_TAIL(&sq->sq_blocked, td, wle);
139 }
140
141 int
_sleepq_remove(struct sleepqueue * sq,struct pthread * td)142 _sleepq_remove(struct sleepqueue *sq, struct pthread *td)
143 {
144 int rc;
145
146 TAILQ_REMOVE(&sq->sq_blocked, td, wle);
147 if (TAILQ_EMPTY(&sq->sq_blocked)) {
148 LIST_REMOVE(sq, sq_hash);
149 td->sleepqueue = sq;
150 rc = 0;
151 } else {
152 td->sleepqueue = SLIST_FIRST(&sq->sq_freeq);
153 SLIST_REMOVE_HEAD(&sq->sq_freeq, sq_flink);
154 rc = 1;
155 }
156 td->wchan = NULL;
157 return (rc);
158 }
159
160 void
_sleepq_drop(struct sleepqueue * sq,void (* cb)(struct pthread *,void * arg),void * arg)161 _sleepq_drop(struct sleepqueue *sq,
162 void (*cb)(struct pthread *, void *arg), void *arg)
163 {
164 struct pthread *td;
165 struct sleepqueue *sq2;
166
167 td = TAILQ_FIRST(&sq->sq_blocked);
168 if (td == NULL)
169 return;
170 LIST_REMOVE(sq, sq_hash);
171 TAILQ_REMOVE(&sq->sq_blocked, td, wle);
172 if (cb != NULL)
173 cb(td, arg);
174 td->sleepqueue = sq;
175 td->wchan = NULL;
176 sq2 = SLIST_FIRST(&sq->sq_freeq);
177 TAILQ_FOREACH(td, &sq->sq_blocked, wle) {
178 if (cb != NULL)
179 cb(td, arg);
180 td->sleepqueue = sq2;
181 td->wchan = NULL;
182 sq2 = SLIST_NEXT(sq2, sq_flink);
183 }
184 TAILQ_INIT(&sq->sq_blocked);
185 SLIST_INIT(&sq->sq_freeq);
186 }
187