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_store_irq(xa, index, ptr, gfp) \
112 xa_store((xa), (index), (ptr), (gfp))
113
114 #define xa_erase_irq(xa, index) \
115 xa_erase((xa), (index))
116
117 #define xa_lock_irq(xa) xa_lock(xa)
118 #define xa_unlock_irq(xa) xa_unlock(xa)
119
120 #define xa_lock_irqsave(xa, flags) \
121 do { \
122 xa_lock((xa)); \
123 flags = 0; \
124 } while (0)
125
126 #define xa_unlock_irqrestore(xa, flags) \
127 do { \
128 xa_unlock((xa)); \
129 flags == 0; \
130 } while (0)
131
132 static inline int
xa_err(void * ptr)133 xa_err(void *ptr)
134 {
135 return (PTR_ERR_OR_ZERO(ptr));
136 }
137
138 static inline void
xa_init(struct xarray * xa)139 xa_init(struct xarray *xa)
140 {
141 xa_init_flags(xa, 0);
142 }
143
144 static inline void *
xa_mk_value(unsigned long v)145 xa_mk_value(unsigned long v)
146 {
147 unsigned long r = (v << 1) | 1;
148
149 return ((void *)r);
150 }
151
152 static inline bool
xa_is_value(const void * e)153 xa_is_value(const void *e)
154 {
155 unsigned long v = (unsigned long)e;
156
157 return (v & 1);
158 }
159
160 static inline unsigned long
xa_to_value(const void * e)161 xa_to_value(const void *e)
162 {
163 unsigned long v = (unsigned long)e;
164
165 return (v >> 1);
166 }
167 #endif /* _LINUXKPI_LINUX_XARRAY_H_ */
168