18f60b1f9b2aafe1ae5e9f32d67d6a3922d3d98d
[dragonfly.git] / sys / kern / kern_mutex.c
1 /*
2  * Copyright (c) 2009 The DragonFly Project.  All rights reserved.
3  *
4  * This code is derived from software contributed to The DragonFly Project
5  * by Matthew Dillon <dillon@backplane.com>
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  *
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
16  *    distribution.
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.
20  *
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
32  * SUCH DAMAGE.
33  */
34 /*
35  * Implement fast persistent locks based on atomic_cmpset_int() with
36  * semantics similar to lockmgr locks but faster and taking up much less
37  * space.  Taken from HAMMER's lock implementation.
38  *
39  * These are meant to complement our LWKT tokens.  Tokens are only held
40  * while the thread is running.  Mutexes can be held across blocking
41  * conditions.
42  *
43  * Most of the support is in sys/mutex[2].h.  We mostly provide backoff
44  * functions here.
45  */
46
47 #include <sys/param.h>
48 #include <sys/systm.h>
49 #include <sys/kernel.h>
50 #include <sys/sysctl.h>
51 #include <sys/thread.h>
52 #include <sys/mutex.h>
53
54 #include <machine/cpufunc.h>
55
56 #include <sys/thread2.h>
57 #include <sys/mutex2.h>
58
59 static __int64_t mtx_contention_count;
60 static __int64_t mtx_collision_count;
61 static __int64_t mtx_wakeup_count;
62
63 SYSCTL_QUAD(_kern, OID_AUTO, mtx_contention_count, CTLFLAG_RW,
64             &mtx_contention_count, 0, "");
65 SYSCTL_QUAD(_kern, OID_AUTO, mtx_collision_count, CTLFLAG_RW,
66             &mtx_collision_count, 0, "");
67 SYSCTL_QUAD(_kern, OID_AUTO, mtx_wakeup_count, CTLFLAG_RW,
68             &mtx_wakeup_count, 0, "");
69
70 /*
71  * Exclusive-lock a mutex, block until acquired.  Recursion is allowed.
72  *
73  * Returns 0 on success, or the tsleep() return code on failure.
74  * An error can only be returned if PCATCH is specified in the flags.
75  */
76 static __inline int
77 __mtx_lock_ex(mtx_t mtx, const char *ident, int flags, int to)
78 {
79         u_int   lock;
80         u_int   nlock;
81         int     error;
82
83         for (;;) {
84                 lock = mtx->mtx_lock;
85                 if (lock == 0) {
86                         nlock = MTX_EXCLUSIVE | 1;
87                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
88                                 mtx->mtx_owner = curthread;
89                                 error = 0;
90                                 break;
91                         }
92                 } else if ((lock & MTX_EXCLUSIVE) &&
93                            mtx->mtx_owner == curthread) {
94                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
95                         nlock = (lock + 1);
96                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
97                                 error = 0;
98                                 break;
99                         }
100                 } else {
101                         nlock = lock | MTX_EXWANTED;
102                         tsleep_interlock(&mtx->mtx_owner, 0);
103                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
104                                 error = tsleep(&mtx->mtx_owner, flags,
105                                                ident, to);
106                                 ++mtx_contention_count;
107                                 if (error) {
108                                         ++mtx_wakeup_count;
109                                         wakeup_one(&mtx->mtx_owner);
110                                         break;
111                                 }
112                         } else {
113                                 tsleep_remove(curthread);
114                         }
115                 }
116                 ++mtx_collision_count;
117         }
118         return (error);
119 }
120
121 int
122 _mtx_lock_ex(mtx_t mtx, const char *ident, int flags, int to)
123 {
124         return(__mtx_lock_ex(mtx, ident, flags, to));
125 }
126
127 int
128 _mtx_lock_ex_quick(mtx_t mtx, const char *ident)
129 {
130         return(__mtx_lock_ex(mtx, ident, 0, 0));
131 }
132
133 /*
134  * Share-lock a mutex, block until acquired.  Recursion is allowed.
135  *
136  * Returns 0 on success, or the tsleep() return code on failure.
137  * An error can only be returned if PCATCH is specified in the flags.
138  */
139 static __inline int
140 __mtx_lock_sh(mtx_t mtx, const char *ident, int flags, int to)
141 {
142         u_int   lock;
143         u_int   nlock;
144         int     error;
145
146         for (;;) {
147                 lock = mtx->mtx_lock;
148                 if ((lock & MTX_EXCLUSIVE) == 0) {
149                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
150                         nlock = lock + 1;
151                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
152                                 error = 0;
153                                 break;
154                         }
155                 } else {
156                         nlock = lock | MTX_SHWANTED;
157                         tsleep_interlock(mtx, 0);
158                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
159                                 error = tsleep(mtx, flags, ident, to);
160                                 if (error)
161                                         break;
162                                 ++mtx_contention_count;
163                         } else {
164                                 tsleep_remove(curthread);
165                         }
166                 }
167                 ++mtx_collision_count;
168         }
169         return (error);
170 }
171
172 int
173 _mtx_lock_sh(mtx_t mtx, const char *ident, int flags, int to)
174 {
175         return (__mtx_lock_sh(mtx, ident, flags, to));
176 }
177
178 int
179 _mtx_lock_sh_quick(mtx_t mtx, const char *ident)
180 {
181         return (__mtx_lock_sh(mtx, ident, 0, 0));
182 }
183
184 void
185 _mtx_spinlock_ex(mtx_t mtx)
186 {
187         u_int   lock;
188         u_int   nlock;
189         int     bb = 1;
190         int     bo;
191
192         for (;;) {
193                 lock = mtx->mtx_lock;
194                 if (lock == 0) {
195                         nlock = MTX_EXCLUSIVE | 1;
196                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
197                                 /* mtx_owner set by caller */
198                                 return;
199                         }
200                 } else if ((lock & MTX_EXCLUSIVE) &&
201                            mtx->mtx_owner == curthread) {
202                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
203                         nlock = (lock + 1);
204                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock))
205                                 return;
206                 } else {
207                         /* MWAIT here */
208                         if (bb < 1000)
209                                 ++bb;
210                         cpu_pause();
211                         for (bo = 0; bo < bb; ++bo)
212                                 ;
213                         ++mtx_contention_count;
214                 }
215                 ++mtx_collision_count;
216         }
217 }
218
219 void
220 _mtx_spinlock_sh(mtx_t mtx)
221 {
222         u_int   lock;
223         u_int   nlock;
224         int     bb = 1;
225         int     bo;
226
227         for (;;) {
228                 lock = mtx->mtx_lock;
229                 if ((lock & MTX_EXCLUSIVE) == 0) {
230                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
231                         nlock = lock + 1;
232                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
233                                 return;
234                 } else {
235                         /* MWAIT here */
236                         if (bb < 1000)
237                                 ++bb;
238                         cpu_pause();
239                         for (bo = 0; bo < bb; ++bo)
240                                 ;
241                         ++mtx_contention_count;
242                 }
243                 ++mtx_collision_count;
244         }
245 }
246
247 int
248 _mtx_lock_ex_try(mtx_t mtx)
249 {
250         u_int   lock;
251         u_int   nlock;
252         int     error = 0;
253
254         for (;;) {
255                 lock = mtx->mtx_lock;
256                 if (lock == 0) {
257                         nlock = MTX_EXCLUSIVE | 1;
258                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
259                                 /* mtx_owner set by caller */
260                                 break;
261                         }
262                 } else if ((lock & MTX_EXCLUSIVE) &&
263                            mtx->mtx_owner == curthread) {
264                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
265                         nlock = (lock + 1);
266                         if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock))
267                                 break;
268                 } else {
269                         error = EAGAIN;
270                         break;
271                 }
272                 ++mtx_collision_count;
273         }
274         return (error);
275 }
276
277 int
278 _mtx_lock_sh_try(mtx_t mtx)
279 {
280         u_int   lock;
281         u_int   nlock;
282         int     error = 0;
283
284         for (;;) {
285                 lock = mtx->mtx_lock;
286                 if ((lock & MTX_EXCLUSIVE) == 0) {
287                         KKASSERT((lock & MTX_MASK) != MTX_MASK);
288                         nlock = lock + 1;
289                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
290                                 break;
291                 } else {
292                         error = EAGAIN;
293                         break;
294                 }
295                 ++mtx_collision_count;
296         }
297         return (error);
298 }
299
300 /*
301  * If the lock is held exclusively it must be owned by the caller.  If the
302  * lock is already a shared lock this operation is a NOP.  A panic will
303  * occur if the lock is not held either shared or exclusive.
304  *
305  * The exclusive count is converted to a shared count.
306  */
307 void
308 _mtx_downgrade(mtx_t mtx)
309 {
310         u_int   lock;
311         u_int   nlock;
312
313         for (;;) {
314                 lock = mtx->mtx_lock;
315                 if ((lock & MTX_EXCLUSIVE) == 0) {
316                         KKASSERT((lock & MTX_MASK) > 0);
317                         break;
318                 }
319                 KKASSERT(mtx->mtx_owner == curthread);
320                 nlock = lock & ~(MTX_EXCLUSIVE | MTX_SHWANTED);
321                 if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
322                         if (lock & MTX_SHWANTED) {
323                                 wakeup(mtx);
324                                 ++mtx_wakeup_count;
325                         }
326                         break;
327                 }
328                 ++mtx_collision_count;
329         }
330 }
331
332 /*
333  * Upgrade a shared lock to an exclusive lock.  The upgrade will fail if
334  * the shared lock has a count other then 1.  Optimize the most likely case
335  * but note that a single cmpset can fail due to WANTED races.
336  *
337  * If the lock is held exclusively it must be owned by the caller and
338  * this function will simply return without doing anything.   A panic will
339  * occur if the lock is held exclusively by someone other then the caller.
340  *
341  * Returns 0 on success, EDEADLK on failure.
342  */
343 int
344 _mtx_upgrade_try(mtx_t mtx)
345 {
346         u_int   lock;
347         u_int   nlock;
348         int     error = 0;
349
350         for (;;) {
351                 lock = mtx->mtx_lock;
352
353                 if ((lock & ~MTX_EXWANTED) == 1) {
354                         nlock = lock | MTX_EXCLUSIVE;
355                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
356                                 mtx->mtx_owner = curthread;
357                                 break;
358                         }
359                 } else if (lock & MTX_EXCLUSIVE) {
360                         KKASSERT(mtx->mtx_owner == curthread);
361                         break;
362                 } else {
363                         error = EDEADLK;
364                         break;
365                 }
366                 ++mtx_collision_count;
367         }
368         return (error);
369 }
370
371 /*
372  * Unlock a lock.  The caller must hold the lock either shared or exclusive.
373  */
374 void
375 _mtx_unlock(mtx_t mtx)
376 {
377         u_int   lock;
378         u_int   nlock;
379
380         for (;;) {
381                 lock = mtx->mtx_lock;
382                 nlock = (lock & (MTX_EXCLUSIVE | MTX_MASK)) - 1;
383                 if (nlock == 0) {
384                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, 0)) {
385                                 if (lock & MTX_SHWANTED) {
386                                         wakeup(mtx);
387                                         ++mtx_wakeup_count;
388                                 }
389                                 if (lock & MTX_EXWANTED) {
390                                         wakeup_one(&mtx->mtx_owner);
391                                         ++mtx_wakeup_count;
392                                 }
393                         }
394                 } else if (nlock == MTX_EXCLUSIVE) {
395                         mtx->mtx_owner = NULL;
396                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, 0)) {
397                                 if (lock & MTX_SHWANTED) {
398                                         wakeup(mtx);
399                                         ++mtx_wakeup_count;
400                                 }
401                                 if (lock & MTX_EXWANTED) {
402                                         wakeup_one(&mtx->mtx_owner);
403                                         ++mtx_wakeup_count;
404                                 }
405                                 break;
406                         }
407                 } else {
408                         nlock = lock - 1;
409                         KKASSERT((nlock & MTX_MASK) != MTX_MASK);
410                         if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
411                                 break;
412                 }
413                 ++mtx_collision_count;
414         }
415 }