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 * $FreeBSD: stable/11/sys/compat/linuxkpi/common/include/linux/xarray.h 367557 2020-11-10 13:13:37Z hselasky $
27 */
28#ifndef	_LINUX_XARRAY_H_
29#define	_LINUX_XARRAY_H_
30
31#include <linux/gfp.h>
32#include <linux/radix-tree.h>
33#include <linux/err.h>
34
35#include <sys/lock.h>
36#include <sys/mutex.h>
37
38#define	XA_LIMIT(min, max) \
39    ({ CTASSERT((min) == 0); (uint32_t)(max); })
40
41#define	XA_FLAGS_ALLOC (1U << 0)
42#define	XA_FLAGS_LOCK_IRQ (1U << 1)
43
44#define	XA_ERROR(x) \
45	ERR_PTR(x)
46
47#define	xa_limit_32b XA_LIMIT(0, 0xFFFFFFFF)
48
49#define	XA_ASSERT_LOCKED(xa) mtx_assert(&(xa)->mtx, MA_OWNED)
50#define	xa_lock(xa) mtx_lock(&(xa)->mtx)
51#define	xa_unlock(xa) mtx_unlock(&(xa)->mtx)
52
53struct xarray {
54	struct radix_tree_root root;
55	struct mtx mtx;		/* internal mutex */
56};
57
58/*
59 * Extensible arrays API implemented as a wrapper
60 * around the radix tree implementation.
61 */
62void *xa_erase(struct xarray *, uint32_t);
63void *xa_load(struct xarray *, uint32_t);
64int xa_alloc(struct xarray *, uint32_t *, void *, uint32_t, gfp_t);
65int xa_alloc_cyclic(struct xarray *, uint32_t *, void *, uint32_t, uint32_t *, gfp_t);
66int xa_insert(struct xarray *, uint32_t, void *, gfp_t);
67void *xa_store(struct xarray *, uint32_t, void *, gfp_t);
68void xa_init_flags(struct xarray *, uint32_t);
69bool xa_empty(struct xarray *);
70void xa_destroy(struct xarray *);
71void *xa_next(struct xarray *, unsigned long *, bool);
72
73#define	xa_for_each(xa, index, entry) \
74	for ((entry) = NULL, (index) = 0; \
75	     ((entry) = xa_next(xa, &index, (entry) != NULL)) != NULL; )
76
77/*
78 * Unlocked version of functions above.
79 */
80void *__xa_erase(struct xarray *, uint32_t);
81int __xa_alloc(struct xarray *, uint32_t *, void *, uint32_t, gfp_t);
82int __xa_alloc_cyclic(struct xarray *, uint32_t *, void *, uint32_t, uint32_t *, gfp_t);
83int __xa_insert(struct xarray *, uint32_t, void *, gfp_t);
84void *__xa_store(struct xarray *, uint32_t, void *, gfp_t);
85bool __xa_empty(struct xarray *);
86void *__xa_next(struct xarray *, unsigned long *, bool);
87
88static inline int
89xa_err(void *ptr)
90{
91	return (PTR_ERR_OR_ZERO(ptr));
92}
93
94static inline void
95xa_init(struct xarray *xa)
96{
97	xa_init_flags(xa, 0);
98}
99
100#endif		/* _LINUX_XARRAY_H_ */
101