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