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 133 xa_err(void *ptr) 134 { 135 return (PTR_ERR_OR_ZERO(ptr)); 136 } 137 138 static inline void 139 xa_init(struct xarray *xa) 140 { 141 xa_init_flags(xa, 0); 142 } 143 144 static inline void * 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 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 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