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_LIMIT(min, max) \
38 ({ CTASSERT((min) == 0); (uint32_t)(max); })
39
40 #define XA_FLAGS_ALLOC (1U << 0)
41 #define XA_FLAGS_LOCK_IRQ (1U << 1)
42 #define XA_FLAGS_ALLOC1 (1U << 2)
43
44 #define XA_ERROR(x) \
45 ERR_PTR(x)
46
47 #define xa_is_err(x) \
48 IS_ERR(x)
49
50 #define xa_limit_32b XA_LIMIT(0, 0xFFFFFFFF)
51
52 #define XA_ASSERT_LOCKED(xa) mtx_assert(&(xa)->mtx, MA_OWNED)
53 #define xa_lock(xa) mtx_lock(&(xa)->mtx)
54 #define xa_unlock(xa) mtx_unlock(&(xa)->mtx)
55
56 struct xarray {
57 struct radix_tree_root root;
58 struct mtx mtx; /* internal mutex */
59 uint32_t flags; /* see XA_FLAGS_XXX */
60 };
61
62 /*
63 * Extensible arrays API implemented as a wrapper
64 * around the radix tree implementation.
65 */
66 void *xa_erase(struct xarray *, uint32_t);
67 void *xa_load(struct xarray *, uint32_t);
68 int xa_alloc(struct xarray *, uint32_t *, void *, uint32_t, gfp_t);
69 int xa_alloc_cyclic(struct xarray *, uint32_t *, void *, uint32_t, uint32_t *, gfp_t);
70 int xa_insert(struct xarray *, uint32_t, void *, gfp_t);
71 void *xa_store(struct xarray *, uint32_t, void *, gfp_t);
72 void xa_init_flags(struct xarray *, uint32_t);
73 bool xa_empty(struct xarray *);
74 void xa_destroy(struct xarray *);
75 void *xa_next(struct xarray *, unsigned long *, bool);
76
77 #define xa_for_each(xa, index, entry) \
78 for ((entry) = NULL, (index) = 0; \
79 ((entry) = xa_next(xa, &index, (entry) != NULL)) != NULL; )
80
81 /*
82 * Unlocked version of functions above.
83 */
84 void *__xa_erase(struct xarray *, uint32_t);
85 int __xa_alloc(struct xarray *, uint32_t *, void *, uint32_t, gfp_t);
86 int __xa_alloc_cyclic(struct xarray *, uint32_t *, void *, uint32_t, uint32_t *, gfp_t);
87 int __xa_insert(struct xarray *, uint32_t, void *, gfp_t);
88 void *__xa_store(struct xarray *, uint32_t, void *, gfp_t);
89 bool __xa_empty(struct xarray *);
90 void *__xa_next(struct xarray *, unsigned long *, bool);
91
92 #define xa_store_irq(xa, index, ptr, gfp) \
93 xa_store((xa), (index), (ptr), (gfp))
94
95 #define xa_erase_irq(xa, index) \
96 xa_erase((xa), (index))
97
98 #define xa_lock_irq(xa) xa_lock(xa)
99 #define xa_unlock_irq(xa) xa_unlock(xa)
100
101 #define xa_lock_irqsave(xa, flags) \
102 do { \
103 xa_lock((xa)); \
104 flags = 0; \
105 } while (0)
106
107 #define xa_unlock_irqrestore(xa, flags) \
108 do { \
109 xa_unlock((xa)); \
110 flags == 0; \
111 } while (0)
112
113 static inline int
xa_err(void * ptr)114 xa_err(void *ptr)
115 {
116 return (PTR_ERR_OR_ZERO(ptr));
117 }
118
119 static inline void
xa_init(struct xarray * xa)120 xa_init(struct xarray *xa)
121 {
122 xa_init_flags(xa, 0);
123 }
124
125 static inline void *
xa_mk_value(unsigned long v)126 xa_mk_value(unsigned long v)
127 {
128 unsigned long r = (v << 1) | 1;
129
130 return ((void *)r);
131 }
132
133 static inline bool
xa_is_value(const void * e)134 xa_is_value(const void *e)
135 {
136 unsigned long v = (unsigned long)e;
137
138 return (v & 1);
139 }
140
141 static inline unsigned long
xa_to_value(const void * e)142 xa_to_value(const void *e)
143 {
144 unsigned long v = (unsigned long)e;
145
146 return (v >> 1);
147 }
148 #endif /* _LINUXKPI_LINUX_XARRAY_H_ */
149