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)->xa_lock, MA_OWNED)
53 #define xa_lock(xa) mtx_lock(&(xa)->xa_lock)
54 #define xa_unlock(xa) mtx_unlock(&(xa)->xa_lock)
55
56 struct xarray {
57 struct radix_tree_root xa_head;
58 struct mtx xa_lock; /* internal mutex */
59 uint32_t xa_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_alloc_cyclic_irq(struct xarray *, uint32_t *, void *, uint32_t, uint32_t *, gfp_t);
71 int xa_insert(struct xarray *, uint32_t, void *, gfp_t);
72 void *xa_store(struct xarray *, uint32_t, void *, gfp_t);
73 void xa_init_flags(struct xarray *, uint32_t);
74 bool xa_empty(struct xarray *);
75 void xa_destroy(struct xarray *);
76 void *xa_next(struct xarray *, unsigned long *, bool);
77
78 #define xa_for_each(xa, index, entry) \
79 for ((entry) = NULL, (index) = 0; \
80 ((entry) = xa_next(xa, &index, (entry) != NULL)) != NULL; )
81
82 /*
83 * Unlocked version of functions above.
84 */
85 void *__xa_erase(struct xarray *, uint32_t);
86 int __xa_alloc(struct xarray *, uint32_t *, void *, uint32_t, gfp_t);
87 int __xa_alloc_cyclic(struct xarray *, uint32_t *, void *, uint32_t, uint32_t *, gfp_t);
88 int __xa_insert(struct xarray *, uint32_t, void *, gfp_t);
89 void *__xa_store(struct xarray *, uint32_t, void *, gfp_t);
90 bool __xa_empty(struct xarray *);
91 void *__xa_next(struct xarray *, unsigned long *, bool);
92
93 #define xa_store_irq(xa, index, ptr, gfp) \
94 xa_store((xa), (index), (ptr), (gfp))
95
96 #define xa_erase_irq(xa, index) \
97 xa_erase((xa), (index))
98
99 #define xa_lock_irq(xa) xa_lock(xa)
100 #define xa_unlock_irq(xa) xa_unlock(xa)
101
102 #define xa_lock_irqsave(xa, flags) \
103 do { \
104 xa_lock((xa)); \
105 flags = 0; \
106 } while (0)
107
108 #define xa_unlock_irqrestore(xa, flags) \
109 do { \
110 xa_unlock((xa)); \
111 flags == 0; \
112 } while (0)
113
114 static inline int
xa_err(void * ptr)115 xa_err(void *ptr)
116 {
117 return (PTR_ERR_OR_ZERO(ptr));
118 }
119
120 static inline void
xa_init(struct xarray * xa)121 xa_init(struct xarray *xa)
122 {
123 xa_init_flags(xa, 0);
124 }
125
126 static inline void *
xa_mk_value(unsigned long v)127 xa_mk_value(unsigned long v)
128 {
129 unsigned long r = (v << 1) | 1;
130
131 return ((void *)r);
132 }
133
134 static inline bool
xa_is_value(const void * e)135 xa_is_value(const void *e)
136 {
137 unsigned long v = (unsigned long)e;
138
139 return (v & 1);
140 }
141
142 static inline unsigned long
xa_to_value(const void * e)143 xa_to_value(const void *e)
144 {
145 unsigned long v = (unsigned long)e;
146
147 return (v >> 1);
148 }
149 #endif /* _LINUXKPI_LINUX_XARRAY_H_ */
150