kernel - Fix devfs bitmap races for pty and other devices
[dragonfly.git] / sys / vfs / devfs / devfs_helper.c
1 /*
2  * Copyright (c) 2009-2019 The DragonFly Project.  All rights reserved.
3  *
4  * This code is derived from software contributed to The DragonFly Project
5  * by Alex Hornung <ahornung@gmail.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 #include <sys/param.h>
35 #include <sys/systm.h>
36 #include <sys/kernel.h>
37 #include <sys/types.h>
38 #include <machine/limits.h>
39 #include <sys/devfs.h>
40
41 MALLOC_DECLARE(M_DEVFS);
42
43 /*
44  * Locallized lock to ensure the integrity of the bitmap/cloning
45  * code.  Callers using chk/set sequences must still check for races
46  * or have their own locks.
47  *
48  * We use a recursive lock only to allow *_get() to call *_set().
49  */
50 static struct lock devfs_bitmap_lock =
51         LOCK_INITIALIZER("dbmap", 0, LK_CANRECURSE);
52
53 /*
54  * DEVFS clone bitmap functions
55  */
56 void
57 devfs_clone_bitmap_init(struct devfs_bitmap *bitmap)
58 {
59         bitmap->chunks = DEVFS_BITMAP_INITIAL_SIZE;
60         bitmap->bitmap = kmalloc(bitmap->chunks * sizeof(u_long),
61                                  M_DEVFS, M_WAITOK);
62         memset(bitmap->bitmap, -1, bitmap->chunks * sizeof(u_long));
63 }
64
65
66 void
67 devfs_clone_bitmap_uninit(struct devfs_bitmap *bitmap)
68 {
69         kfree(bitmap->bitmap, M_DEVFS);
70 }
71
72 /*
73  * Extend the bitmap past (not just up to) 'newchunks' chunks.  While
74  * probably not necessary, we go a little further and give ourselves
75  * one extra chunk's worth of bitmap beyond what is required.
76  */
77 static void
78 devfs_clone_bitmap_extend(struct devfs_bitmap *bitmap, int newchunks)
79 {
80         int oldchunks = bitmap->chunks;
81
82         bitmap->chunks = newchunks + 2;
83         bitmap->bitmap = krealloc(bitmap->bitmap,
84                                   sizeof(u_long) * bitmap->chunks,
85                                   M_DEVFS, M_WAITOK);
86         memset(bitmap->bitmap + oldchunks, -1,
87                sizeof(u_long) * (bitmap->chunks - oldchunks));
88 }
89
90 /*
91  * This helper function determines the next available free unit in the
92  * bitmap, extending the bitmap if necessary.  It cannot fail.
93  */
94 static int
95 devfs_clone_bitmap_fff(struct devfs_bitmap *bitmap)
96 {
97         u_long curbitmap;
98         int bit, i;
99         int chunks;
100
101         chunks = bitmap->chunks;
102
103         for (i = 0; i < chunks + 1; i++) {
104                 if (i == chunks)
105                         devfs_clone_bitmap_extend(bitmap, i);
106                 curbitmap = bitmap->bitmap[i];
107
108                 if (curbitmap) {
109                         curbitmap &= (~curbitmap)+1;
110                         for (bit = 1; curbitmap != 1; bit++)
111                                 curbitmap >>= 1;
112
113                         return (bit - 1 + (i << 3) * sizeof(curbitmap));
114                 }
115         }
116
117         /*
118          * NOT REACHED
119          */
120         panic("devfs_clone_bitmap_fff");
121         return -1;
122 }
123
124 /*
125  * Caller wants to know if the specified unit has been allocated
126  * or not.  Return 0, indicating that it has not been allocated.
127  *
128  * Caller must hold a lock to prevent chk-to-set races.  Devfs also
129  * obtains a temporary lock, juse in case, to ensure structural
130  * integrity.
131  *
132  * (the bitmap implements 0=allocated, 1=not-allocated but the
133  * return value is inverted).
134  */
135 int
136 devfs_clone_bitmap_chk(struct devfs_bitmap *bitmap, int unit)
137 {
138         int chunk;
139         int res;
140
141         chunk = unit / (sizeof(u_long) * 8);
142         unit -= chunk * (sizeof(u_long) * 8);
143
144         lockmgr(&devfs_bitmap_lock, LK_EXCLUSIVE);
145         if (chunk >= bitmap->chunks) {
146                 lockmgr(&devfs_bitmap_lock, LK_RELEASE);
147                 return 0;               /* device does not exist */
148         }
149         res = !((bitmap->bitmap[chunk]) & (1UL << unit));
150         lockmgr(&devfs_bitmap_lock, LK_RELEASE);
151
152         return res;
153 }
154
155 /*
156  * Unconditionally mark the specified unit as allocated in the bitmap.
157  *
158  * Caller must hold a lock to prevent chk-to-set races, or otherwise
159  * check for a return value < 0 from this routine.  If the unit had
160  * never been allocated in the past, a token lock might not be sufficient
161  * to avoid races (if this function must extend the bitmap it could block
162  * temporary in kmalloc()).
163  *
164  * devfs acquires a temporary lock to ensure structural integrity.
165  *
166  * If the bit is already clear (indicating that the unit is already
167  * allocated), return -1.  Otherwise return 0.
168  */
169 int
170 devfs_clone_bitmap_set(struct devfs_bitmap *bitmap, int unit)
171 {
172         int chunk;
173         int res;
174
175         chunk = unit / (sizeof(u_long) * 8);
176         unit -= chunk * (sizeof(u_long) * 8);
177
178         lockmgr(&devfs_bitmap_lock, LK_EXCLUSIVE);
179         if (chunk >= bitmap->chunks)
180                 devfs_clone_bitmap_extend(bitmap, chunk);
181         if (bitmap->bitmap[chunk] & (1UL << unit)) {
182                 bitmap->bitmap[chunk] &= ~(1UL << unit);
183                 res = 0;
184         } else {
185                 res = -1;
186         }
187         lockmgr(&devfs_bitmap_lock, LK_RELEASE);
188
189         return res;
190 }
191
192 /*
193  * Unconditionally deallocate a unit number.  Caller must synchronize any
194  * destroy_dev()'s the device called before clearing the bitmap bit to
195  * avoid races against a new clone.
196  */
197 void
198 devfs_clone_bitmap_put(struct devfs_bitmap *bitmap, int unit)
199 {
200         int chunk;
201
202         devfs_config();
203
204         chunk = unit / (sizeof(u_long) * 8);
205         unit -= chunk * (sizeof(u_long) * 8);
206
207         lockmgr(&devfs_bitmap_lock, LK_EXCLUSIVE);
208         if (chunk < bitmap->chunks)
209                 bitmap->bitmap[chunk] |= (1UL << unit);
210         lockmgr(&devfs_bitmap_lock, LK_RELEASE);
211 }
212
213 /*
214  * Conditionally allocate a unit from the bitmap.  Returns -1 if no
215  * more units are available.
216  *
217  * Caller must hold a lock to avoid bitmap races.  Since *_fff() below
218  * pre-extends the bitmap as necessary, a token lock is sufficient.
219  */
220 int
221 devfs_clone_bitmap_get(struct devfs_bitmap *bitmap, int limit)
222 {
223         int unit;
224
225         lockmgr(&devfs_bitmap_lock, LK_EXCLUSIVE);
226         unit = devfs_clone_bitmap_fff(bitmap);
227         if (limit > 0 && unit > limit) {
228                 unit = -1;
229         } else {
230                 devfs_clone_bitmap_set(bitmap, unit);
231         }
232         lockmgr(&devfs_bitmap_lock, LK_RELEASE);
233
234         return unit;
235 }