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 #ifndef _LINUXKPI_LINUX_XARRAY_H_
27 #define _LINUXKPI_LINUX_XARRAY_H_
28
29 #include <linux/gfp.h>
30 #include <linux/radix-tree.h>
31 #include <linux/err.h>
32 #include <linux/kconfig.h>
33
34 #include <sys/lock.h>
35 #include <sys/mutex.h>
36
37 #define XA_FLAGS_ALLOC (1U << 0)
38 #define XA_FLAGS_LOCK_IRQ (1U << 1)
39 #define XA_FLAGS_ALLOC1 (1U << 2)
40
41 #define XA_ERROR(x) \
42 ERR_PTR(x)
43
44 #define xa_is_err(x) \
45 IS_ERR(x)
46
47 #define XA_ASSERT_LOCKED(xa) mtx_assert(&(xa)->xa_lock, MA_OWNED)
48 #define xa_lock(xa) mtx_lock(&(xa)->xa_lock)
49 #define xa_unlock(xa) mtx_unlock(&(xa)->xa_lock)
50
51 struct xarray {
52 struct radix_tree_root xa_head;
53 struct mtx xa_lock; /* internal mutex */
54 uint32_t xa_flags; /* see XA_FLAGS_XXX */
55 };
56
57 #define DEFINE_XARRAY_FLAGS(name, flags) \
58 struct xarray name = { \
59 .xa_head.gfp_mask = GFP_NOWAIT, \
60 .xa_flags = flags, \
61 }; \
62 MTX_SYSINIT(name ## _mtx, &name.xa_lock, \
63 "linuxkpi_DEFINE_XARRAY(" #name ")", \
64 MTX_DEF | MTX_RECURSE)
65
66 #define DEFINE_XARRAY(name) DEFINE_XARRAY_FLAGS(name, 0)
67 #define DEFINE_XARRAY_ALLOC(name) DEFINE_XARRAY_FLAGS(name, XA_FLAGS_ALLOC)
68
69 struct xa_limit {
70 uint32_t max;
71 uint32_t min;
72 };
73
74 #define XA_LIMIT(min_, max_) (struct xa_limit){ .min = (min_), .max = (max_) }
75
76 #define xa_limit_16b XA_LIMIT(0, USHRT_MAX)
77 #define xa_limit_31b XA_LIMIT(0, INT_MAX)
78 #define xa_limit_32b XA_LIMIT(0, UINT_MAX)
79
80 /*
81 * Extensible arrays API implemented as a wrapper
82 * around the radix tree implementation.
83 */
84 void *xa_erase(struct xarray *, uint32_t);
85 void *xa_load(struct xarray *, uint32_t);
86 int xa_alloc(struct xarray *, uint32_t *, void *, struct xa_limit, gfp_t);
87 int xa_alloc_cyclic(struct xarray *, uint32_t *, void *, struct xa_limit, uint32_t *, gfp_t);
88 int xa_alloc_cyclic_irq(struct xarray *, uint32_t *, void *, struct xa_limit, uint32_t *, gfp_t);
89 int xa_insert(struct xarray *, uint32_t, void *, gfp_t);
90 void *xa_store(struct xarray *, uint32_t, void *, gfp_t);
91 void xa_init_flags(struct xarray *, uint32_t);
92 bool xa_empty(struct xarray *);
93 void xa_destroy(struct xarray *);
94 void *xa_next(struct xarray *, unsigned long *, bool);
95
96 #define xa_for_each(xa, index, entry) \
97 for ((entry) = NULL, (index) = 0; \
98 ((entry) = xa_next(xa, &index, (entry) != NULL)) != NULL; )
99
100 /*
101 * Unlocked version of functions above.
102 */
103 void *__xa_erase(struct xarray *, uint32_t);
104 int __xa_alloc(struct xarray *, uint32_t *, void *, struct xa_limit, gfp_t);
105 int __xa_alloc_cyclic(struct xarray *, uint32_t *, void *, struct xa_limit, uint32_t *, gfp_t);
106 int __xa_insert(struct xarray *, uint32_t, void *, gfp_t);
107 void *__xa_store(struct xarray *, uint32_t, void *, gfp_t);
108 bool __xa_empty(struct xarray *);
109 void *__xa_next(struct xarray *, unsigned long *, bool);
110
111 #define xa_insert_irq(xa, index, ptr, gfp) \
112 xa_insert((xa), (index), (ptr), (gfp))
113
114 #define xa_store_irq(xa, index, ptr, gfp) \
115 xa_store((xa), (index), (ptr), (gfp))
116
117 #define xa_erase_irq(xa, index) \
118 xa_erase((xa), (index))
119
120 #define xa_lock_irq(xa) xa_lock(xa)
121 #define xa_unlock_irq(xa) xa_unlock(xa)
122
123 #define xa_lock_irqsave(xa, flags) \
124 do { \
125 xa_lock((xa)); \
126 flags = 0; \
127 } while (0)
128
129 #define xa_unlock_irqrestore(xa, flags) \
130 do { \
131 xa_unlock((xa)); \
132 flags == 0; \
133 } while (0)
134
135 static inline int
xa_err(void * ptr)136 xa_err(void *ptr)
137 {
138 return (PTR_ERR_OR_ZERO(ptr));
139 }
140
141 static inline void
xa_init(struct xarray * xa)142 xa_init(struct xarray *xa)
143 {
144 xa_init_flags(xa, 0);
145 }
146
147 static inline void *
xa_mk_value(unsigned long v)148 xa_mk_value(unsigned long v)
149 {
150 unsigned long r = (v << 1) | 1;
151
152 return ((void *)r);
153 }
154
155 static inline bool
xa_is_value(const void * e)156 xa_is_value(const void *e)
157 {
158 unsigned long v = (unsigned long)e;
159
160 return (v & 1);
161 }
162
163 static inline unsigned long
xa_to_value(const void * e)164 xa_to_value(const void *e)
165 {
166 unsigned long v = (unsigned long)e;
167
168 return (v >> 1);
169 }
170 #endif /* _LINUXKPI_LINUX_XARRAY_H_ */
171