1/*-
2 * Copyright (c) 2020 Mellanox Technologies, Ltd.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice unmodified, this list of conditions, and the following
10 *    disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include <sys/cdefs.h>
28#include <linux/xarray.h>
29
30#include <vm/vm_pageout.h>
31
32/*
33 * Linux' XArray allows to store a NULL pointer as a value. xa_load() would
34 * return NULL for both an unused index and an index set to NULL. But it
35 * impacts xa_alloc() which needs to find the next available index.
36 *
37 * However, our implementation relies on a radix tree (see `linux_radix.c`)
38 * which does not accept NULL pointers as values. I'm not sure this is a
39 * limitation or a feature, so to work around this, a NULL value is replaced by
40 * `NULL_VALUE`, an unlikely address, when we pass it to linux_radix.
41 */
42#define	NULL_VALUE	(void *)0x1
43
44/*
45 * This function removes the element at the given index and returns
46 * the pointer to the removed element, if any.
47 */
48void *
49__xa_erase(struct xarray *xa, uint32_t index)
50{
51	void *retval;
52
53	XA_ASSERT_LOCKED(xa);
54
55	retval = radix_tree_delete(&xa->root, index);
56	if (retval == NULL_VALUE)
57		retval = NULL;
58
59	return (retval);
60}
61
62void *
63xa_erase(struct xarray *xa, uint32_t index)
64{
65	void *retval;
66
67	xa_lock(xa);
68	retval = __xa_erase(xa, index);
69	xa_unlock(xa);
70
71	return (retval);
72}
73
74/*
75 * This function returns the element pointer at the given index. A
76 * value of NULL is returned if the element does not exist.
77 */
78void *
79xa_load(struct xarray *xa, uint32_t index)
80{
81	void *retval;
82
83	xa_lock(xa);
84	retval = radix_tree_lookup(&xa->root, index);
85	xa_unlock(xa);
86
87	if (retval == NULL_VALUE)
88		retval = NULL;
89
90	return (retval);
91}
92
93/*
94 * This is an internal function used to sleep until more memory
95 * becomes available.
96 */
97static void
98xa_vm_wait_locked(struct xarray *xa)
99{
100	xa_unlock(xa);
101	vm_wait(NULL);
102	xa_lock(xa);
103}
104
105/*
106 * This function iterates the xarray until it finds a free slot where
107 * it can insert the element pointer to by "ptr". It starts at the
108 * index pointed to by "pindex" and updates this value at return. The
109 * "mask" argument defines the maximum index allowed, inclusivly, and
110 * must be a power of two minus one value. The "gfp" argument
111 * basically tells if we can wait for more memory to become available
112 * or not. This function returns zero upon success or a negative error
113 * code on failure. A typical error code is -ENOMEM which means either
114 * the xarray is full, or there was not enough internal memory
115 * available to complete the radix tree insertion.
116 */
117int
118__xa_alloc(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, gfp_t gfp)
119{
120	int retval;
121
122	XA_ASSERT_LOCKED(xa);
123
124	/* mask should allow to allocate at least one item */
125	MPASS(mask > ((xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0));
126
127	/* mask can be any power of two value minus one */
128	MPASS((mask & (mask + 1)) == 0);
129
130	*pindex = (xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0;
131	if (ptr == NULL)
132		ptr = NULL_VALUE;
133retry:
134	retval = radix_tree_insert(&xa->root, *pindex, ptr);
135
136	switch (retval) {
137	case -EEXIST:
138		if (likely(*pindex != mask)) {
139			(*pindex)++;
140			goto retry;
141		}
142		retval = -ENOMEM;
143		break;
144	case -ENOMEM:
145		if (likely(gfp & M_WAITOK)) {
146			xa_vm_wait_locked(xa);
147			goto retry;
148		}
149		break;
150	default:
151		break;
152	}
153	return (retval);
154}
155
156int
157xa_alloc(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, gfp_t gfp)
158{
159	int retval;
160
161	if (ptr == NULL)
162		ptr = NULL_VALUE;
163
164	xa_lock(xa);
165	retval = __xa_alloc(xa, pindex, ptr, mask, gfp);
166	xa_unlock(xa);
167
168	return (retval);
169}
170
171/*
172 * This function works the same like the "xa_alloc" function, except
173 * it wraps the next index value to zero when there are no entries
174 * left at the end of the xarray searching for a free slot from the
175 * beginning of the array. If the xarray is full -ENOMEM is returned.
176 */
177int
178__xa_alloc_cyclic(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask,
179    uint32_t *pnext_index, gfp_t gfp)
180{
181	int retval;
182	int timeout = 1;
183
184	XA_ASSERT_LOCKED(xa);
185
186	/* mask should allow to allocate at least one item */
187	MPASS(mask > ((xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0));
188
189	/* mask can be any power of two value minus one */
190	MPASS((mask & (mask + 1)) == 0);
191
192	*pnext_index = (xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0;
193	if (ptr == NULL)
194		ptr = NULL_VALUE;
195retry:
196	retval = radix_tree_insert(&xa->root, *pnext_index, ptr);
197
198	switch (retval) {
199	case -EEXIST:
200		if (unlikely(*pnext_index == mask) && !timeout--) {
201			retval = -ENOMEM;
202			break;
203		}
204		(*pnext_index)++;
205		(*pnext_index) &= mask;
206		if (*pnext_index == 0 && (xa->flags & XA_FLAGS_ALLOC1) != 0)
207			(*pnext_index)++;
208		goto retry;
209	case -ENOMEM:
210		if (likely(gfp & M_WAITOK)) {
211			xa_vm_wait_locked(xa);
212			goto retry;
213		}
214		break;
215	default:
216		break;
217	}
218	*pindex = *pnext_index;
219
220	return (retval);
221}
222
223int
224xa_alloc_cyclic(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask,
225    uint32_t *pnext_index, gfp_t gfp)
226{
227	int retval;
228
229	xa_lock(xa);
230	retval = __xa_alloc_cyclic(xa, pindex, ptr, mask, pnext_index, gfp);
231	xa_unlock(xa);
232
233	return (retval);
234}
235
236/*
237 * This function tries to insert an element at the given index. The
238 * "gfp" argument basically decides of this function can sleep or not
239 * trying to allocate internal memory for its radix tree.  The
240 * function returns an error code upon failure. Typical error codes
241 * are element exists (-EEXIST) or out of memory (-ENOMEM).
242 */
243int
244__xa_insert(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp)
245{
246	int retval;
247
248	XA_ASSERT_LOCKED(xa);
249	if (ptr == NULL)
250		ptr = NULL_VALUE;
251retry:
252	retval = radix_tree_insert(&xa->root, index, ptr);
253
254	switch (retval) {
255	case -ENOMEM:
256		if (likely(gfp & M_WAITOK)) {
257			xa_vm_wait_locked(xa);
258			goto retry;
259		}
260		break;
261	default:
262		break;
263	}
264	return (retval);
265}
266
267int
268xa_insert(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp)
269{
270	int retval;
271
272	xa_lock(xa);
273	retval = __xa_insert(xa, index, ptr, gfp);
274	xa_unlock(xa);
275
276	return (retval);
277}
278
279/*
280 * This function updates the element at the given index and returns a
281 * pointer to the old element. The "gfp" argument basically decides of
282 * this function can sleep or not trying to allocate internal memory
283 * for its radix tree. The function returns an XA_ERROR() pointer code
284 * upon failure. Code using this function must always check if the
285 * return value is an XA_ERROR() code before using the returned value.
286 */
287void *
288__xa_store(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp)
289{
290	int retval;
291
292	XA_ASSERT_LOCKED(xa);
293	if (ptr == NULL)
294		ptr = NULL_VALUE;
295retry:
296	retval = radix_tree_store(&xa->root, index, &ptr);
297
298	switch (retval) {
299	case 0:
300		if (ptr == NULL_VALUE)
301			ptr = NULL;
302		break;
303	case -ENOMEM:
304		if (likely(gfp & M_WAITOK)) {
305			xa_vm_wait_locked(xa);
306			goto retry;
307		}
308		ptr = XA_ERROR(retval);
309		break;
310	default:
311		ptr = XA_ERROR(retval);
312		break;
313	}
314	return (ptr);
315}
316
317void *
318xa_store(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp)
319{
320	void *retval;
321
322	xa_lock(xa);
323	retval = __xa_store(xa, index, ptr, gfp);
324	xa_unlock(xa);
325
326	return (retval);
327}
328
329/*
330 * This function initialize an xarray structure.
331 */
332void
333xa_init_flags(struct xarray *xa, uint32_t flags)
334{
335	memset(xa, 0, sizeof(*xa));
336
337	mtx_init(&xa->mtx, "lkpi-xarray", NULL, MTX_DEF | MTX_RECURSE);
338	xa->root.gfp_mask = GFP_NOWAIT;
339	xa->flags = flags;
340}
341
342/*
343 * This function destroys an xarray structure and all its internal
344 * memory and locks.
345 */
346void
347xa_destroy(struct xarray *xa)
348{
349	struct radix_tree_iter iter;
350	void **ppslot;
351
352	radix_tree_for_each_slot(ppslot, &xa->root, &iter, 0)
353		radix_tree_iter_delete(&xa->root, &iter, ppslot);
354	mtx_destroy(&xa->mtx);
355}
356
357/*
358 * This function checks if an xarray is empty or not.
359 * It returns true if empty, else false.
360 */
361bool
362__xa_empty(struct xarray *xa)
363{
364	struct radix_tree_iter iter = {};
365	void **temp;
366
367	XA_ASSERT_LOCKED(xa);
368
369	return (!radix_tree_iter_find(&xa->root, &iter, &temp));
370}
371
372bool
373xa_empty(struct xarray *xa)
374{
375	bool retval;
376
377	xa_lock(xa);
378	retval = __xa_empty(xa);
379	xa_unlock(xa);
380
381	return (retval);
382}
383
384/*
385 * This function returns the next valid xarray entry based on the
386 * index given by "pindex". The valued pointed to by "pindex" is
387 * updated before return.
388 */
389void *
390__xa_next(struct xarray *xa, unsigned long *pindex, bool not_first)
391{
392	struct radix_tree_iter iter = { .index = *pindex };
393	void **ppslot;
394	void *retval;
395	bool found;
396
397	XA_ASSERT_LOCKED(xa);
398
399	if (not_first) {
400		/* advance to next index, if any */
401		iter.index++;
402		if (iter.index == 0)
403			return (NULL);
404	}
405
406	found = radix_tree_iter_find(&xa->root, &iter, &ppslot);
407	if (likely(found)) {
408		retval = *ppslot;
409		if (retval == NULL_VALUE)
410			retval = NULL;
411		*pindex = iter.index;
412	} else {
413		retval = NULL;
414	}
415	return (retval);
416}
417
418void *
419xa_next(struct xarray *xa, unsigned long *pindex, bool not_first)
420{
421	void *retval;
422
423	xa_lock(xa);
424	retval = __xa_next(xa, pindex, not_first);
425	xa_unlock(xa);
426
427	return (retval);
428}
429