1/*-
2 * Copyright (c) 2010 Isilon Systems, Inc.
3 * Copyright (c) 2010 iX Systems, Inc.
4 * Copyright (c) 2010 Panasas, Inc.
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/param.h>
30#include <sys/systm.h>
31#include <sys/malloc.h>
32#include <sys/kernel.h>
33#include <sys/sysctl.h>
34#include <sys/lock.h>
35#include <sys/mutex.h>
36
37#include <machine/stdarg.h>
38
39#include <linux/bitops.h>
40#include <linux/kobject.h>
41#include <linux/slab.h>
42#include <linux/idr.h>
43#include <linux/err.h>
44
45/*
46 * IDR Implementation.
47 *
48 * This is quick and dirty and not as re-entrant as the linux version
49 * however it should be fairly fast.  It is basically a radix tree with
50 * a builtin bitmap for allocation.
51 */
52static MALLOC_DEFINE(M_IDR, "idr", "Linux IDR compat");
53
54static inline int
55idr_max(struct idr *idr)
56{
57	return (1 << (idr->layers * IDR_BITS)) - 1;
58}
59
60static inline int
61idr_pos(int id, int layer)
62{
63	return (id >> (IDR_BITS * layer)) & IDR_MASK;
64}
65
66void
67idr_init(struct idr *idr)
68{
69	bzero(idr, sizeof(*idr));
70	mtx_init(&idr->lock, "idr", NULL, MTX_DEF);
71}
72
73/* Only frees cached pages. */
74void
75idr_destroy(struct idr *idr)
76{
77	struct idr_layer *il, *iln;
78
79	mtx_lock(&idr->lock);
80	for (il = idr->free; il != NULL; il = iln) {
81		iln = il->ary[0];
82		free(il, M_IDR);
83	}
84	mtx_unlock(&idr->lock);
85}
86
87static void
88idr_remove_layer(struct idr_layer *il, int layer)
89{
90	int i;
91
92	if (il == NULL)
93		return;
94	if (layer == 0) {
95		free(il, M_IDR);
96		return;
97	}
98	for (i = 0; i < IDR_SIZE; i++)
99		if (il->ary[i])
100			idr_remove_layer(il->ary[i], layer - 1);
101}
102
103void
104idr_remove_all(struct idr *idr)
105{
106
107	mtx_lock(&idr->lock);
108	idr_remove_layer(idr->top, idr->layers - 1);
109	idr->top = NULL;
110	idr->layers = 0;
111	mtx_unlock(&idr->lock);
112}
113
114void
115idr_remove(struct idr *idr, int id)
116{
117	struct idr_layer *il;
118	int layer;
119	int idx;
120
121	id &= MAX_ID_MASK;
122	mtx_lock(&idr->lock);
123	il = idr->top;
124	layer = idr->layers - 1;
125	if (il == NULL || id > idr_max(idr)) {
126		mtx_unlock(&idr->lock);
127		return;
128	}
129	/*
130	 * Walk down the tree to this item setting bitmaps along the way
131	 * as we know at least one item will be free along this path.
132	 */
133	while (layer && il) {
134		idx = idr_pos(id, layer);
135		il->bitmap |= 1 << idx;
136		il = il->ary[idx];
137		layer--;
138	}
139	idx = id & IDR_MASK;
140	/*
141	 * At this point we've set free space bitmaps up the whole tree.
142	 * We could make this non-fatal and unwind but linux dumps a stack
143	 * and a warning so I don't think it's necessary.
144	 */
145	if (il == NULL || (il->bitmap & (1 << idx)) != 0)
146		panic("idr_remove: Item %d not allocated (%p, %p)\n",
147		    id, idr, il);
148	il->ary[idx] = NULL;
149	il->bitmap |= 1 << idx;
150	mtx_unlock(&idr->lock);
151	return;
152}
153
154void *
155idr_replace(struct idr *idr, void *ptr, int id)
156{
157	struct idr_layer *il;
158	void *res;
159	int layer;
160	int idx;
161
162	res = ERR_PTR(-EINVAL);
163	id &= MAX_ID_MASK;
164	mtx_lock(&idr->lock);
165	il = idr->top;
166	layer = idr->layers - 1;
167	if (il == NULL || id > idr_max(idr))
168		goto out;
169	while (layer && il) {
170		il = il->ary[idr_pos(id, layer)];
171		layer--;
172	}
173	idx = id & IDR_MASK;
174	/*
175	 * Replace still returns an error if the item was not allocated.
176	 */
177	if (il != NULL && (il->bitmap & (1 << idx)) != 0) {
178		res = il->ary[idx];
179		il->ary[idx] = ptr;
180	}
181out:
182	mtx_unlock(&idr->lock);
183	return (res);
184}
185
186void *
187idr_find(struct idr *idr, int id)
188{
189	struct idr_layer *il;
190	void *res;
191	int layer;
192
193	res = NULL;
194	id &= MAX_ID_MASK;
195	mtx_lock(&idr->lock);
196	il = idr->top;
197	layer = idr->layers - 1;
198	if (il == NULL || id > idr_max(idr))
199		goto out;
200	while (layer && il) {
201		il = il->ary[idr_pos(id, layer)];
202		layer--;
203	}
204	if (il != NULL)
205		res = il->ary[id & IDR_MASK];
206out:
207	mtx_unlock(&idr->lock);
208	return (res);
209}
210
211int
212idr_pre_get(struct idr *idr, gfp_t gfp_mask)
213{
214	struct idr_layer *il, *iln;
215	struct idr_layer *head;
216	int need;
217
218	mtx_lock(&idr->lock);
219	for (;;) {
220		need = idr->layers + 1;
221		for (il = idr->free; il != NULL; il = il->ary[0])
222			need--;
223		mtx_unlock(&idr->lock);
224		if (need == 0)
225			break;
226		for (head = NULL; need; need--) {
227			iln = malloc(sizeof(*il), M_IDR, M_ZERO | gfp_mask);
228			if (iln == NULL)
229				break;
230			bitmap_fill(&iln->bitmap, IDR_SIZE);
231			if (head != NULL) {
232				il->ary[0] = iln;
233				il = iln;
234			} else
235				head = il = iln;
236		}
237		if (head == NULL)
238			return (0);
239		mtx_lock(&idr->lock);
240		il->ary[0] = idr->free;
241		idr->free = head;
242	}
243	return (1);
244}
245
246static inline struct idr_layer *
247idr_get(struct idr *idr)
248{
249	struct idr_layer *il;
250
251	il = idr->free;
252	if (il) {
253		idr->free = il->ary[0];
254		il->ary[0] = NULL;
255		return (il);
256	}
257	il = malloc(sizeof(*il), M_IDR, M_ZERO | M_NOWAIT);
258	bitmap_fill(&il->bitmap, IDR_SIZE);
259	return (il);
260}
261
262/*
263 * Could be implemented as get_new_above(idr, ptr, 0, idp) but written
264 * first for simplicity sake.
265 */
266int
267idr_get_new(struct idr *idr, void *ptr, int *idp)
268{
269	struct idr_layer *stack[MAX_LEVEL];
270	struct idr_layer *il;
271	int error;
272	int layer;
273	int idx;
274	int id;
275
276	error = -EAGAIN;
277	mtx_lock(&idr->lock);
278	/*
279	 * Expand the tree until there is free space.
280	 */
281	if (idr->top == NULL || idr->top->bitmap == 0) {
282		if (idr->layers == MAX_LEVEL + 1) {
283			error = -ENOSPC;
284			goto out;
285		}
286		il = idr_get(idr);
287		if (il == NULL)
288			goto out;
289		il->ary[0] = idr->top;
290		if (idr->top)
291			il->bitmap &= ~1;
292		idr->top = il;
293		idr->layers++;
294	}
295	il = idr->top;
296	id = 0;
297	/*
298	 * Walk the tree following free bitmaps, record our path.
299	 */
300	for (layer = idr->layers - 1;; layer--) {
301		stack[layer] = il;
302		idx = ffsl(il->bitmap);
303		if (idx == 0)
304			panic("idr_get_new: Invalid leaf state (%p, %p)\n",
305			    idr, il);
306		idx--;
307		id |= idx << (layer * IDR_BITS);
308		if (layer == 0)
309			break;
310		if (il->ary[idx] == NULL) {
311			il->ary[idx] = idr_get(idr);
312			if (il->ary[idx] == NULL)
313				goto out;
314		}
315		il = il->ary[idx];
316	}
317	/*
318	 * Allocate the leaf to the consumer.
319	 */
320	il->bitmap &= ~(1 << idx);
321	il->ary[idx] = ptr;
322	*idp = id;
323	/*
324	 * Clear bitmaps potentially up to the root.
325	 */
326	while (il->bitmap == 0 && ++layer < idr->layers) {
327		il = stack[layer];
328		il->bitmap &= ~(1 << idr_pos(id, layer));
329	}
330	error = 0;
331out:
332	mtx_unlock(&idr->lock);
333#ifdef INVARIANTS
334	if (error == 0 && idr_find(idr, id) != ptr) {
335		panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n",
336		    idr, id, ptr);
337	}
338#endif
339	return (error);
340}
341
342int
343idr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp)
344{
345	struct idr_layer *stack[MAX_LEVEL];
346	struct idr_layer *il;
347	int error;
348	int layer;
349	int idx, sidx;
350	int id;
351
352	error = -EAGAIN;
353	mtx_lock(&idr->lock);
354	/*
355	 * Compute the layers required to support starting_id and the mask
356	 * at the top layer.
357	 */
358restart:
359	idx = starting_id;
360	layer = 0;
361	while (idx & ~IDR_MASK) {
362		layer++;
363		idx >>= IDR_BITS;
364	}
365	if (layer == MAX_LEVEL + 1) {
366		error = -ENOSPC;
367		goto out;
368	}
369	/*
370	 * Expand the tree until there is free space at or beyond starting_id.
371	 */
372	while (idr->layers <= layer ||
373	    idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) {
374		if (idr->layers == MAX_LEVEL + 1) {
375			error = -ENOSPC;
376			goto out;
377		}
378		il = idr_get(idr);
379		if (il == NULL)
380			goto out;
381		il->ary[0] = idr->top;
382		if (idr->top && idr->top->bitmap == 0)
383			il->bitmap &= ~1;
384		idr->top = il;
385		idr->layers++;
386	}
387	il = idr->top;
388	id = 0;
389	/*
390	 * Walk the tree following free bitmaps, record our path.
391	 */
392	for (layer = idr->layers - 1;; layer--) {
393		stack[layer] = il;
394		sidx = idr_pos(starting_id, layer);
395		/* Returns index numbered from 0 or size if none exists. */
396		idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx);
397		if (idx == IDR_SIZE && sidx == 0)
398			panic("idr_get_new: Invalid leaf state (%p, %p)\n",
399			    idr, il);
400		/*
401		 * We may have walked a path where there was a free bit but
402		 * it was lower than what we wanted.  Restart the search with
403		 * a larger starting id.  id contains the progress we made so
404		 * far.  Search the leaf one above this level.  This may
405		 * restart as many as MAX_LEVEL times but that is expected
406		 * to be rare.
407		 */
408		if (idx == IDR_SIZE) {
409			starting_id = id + (1 << (layer+1 * IDR_BITS));
410			goto restart;
411		}
412		if (idx > sidx)
413			starting_id = 0;	/* Search the whole subtree. */
414		id |= idx << (layer * IDR_BITS);
415		if (layer == 0)
416			break;
417		if (il->ary[idx] == NULL) {
418			il->ary[idx] = idr_get(idr);
419			if (il->ary[idx] == NULL)
420				goto out;
421		}
422		il = il->ary[idx];
423	}
424	/*
425	 * Allocate the leaf to the consumer.
426	 */
427	il->bitmap &= ~(1 << idx);
428	il->ary[idx] = ptr;
429	*idp = id;
430	/*
431	 * Clear bitmaps potentially up to the root.
432	 */
433	while (il->bitmap == 0 && ++layer < idr->layers) {
434		il = stack[layer];
435		il->bitmap &= ~(1 << idr_pos(id, layer));
436	}
437	error = 0;
438out:
439	mtx_unlock(&idr->lock);
440#ifdef INVARIANTS
441	if (error == 0 && idr_find(idr, id) != ptr) {
442		panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n",
443		    idr, id, ptr);
444	}
445#endif
446	return (error);
447}
448