xref: /netbsd-src/sys/external/bsd/drm2/linux/linux_xa.c (revision 4efeea51c6ca104c9ec5c0747229c0c39926eea7)
1 /*	$NetBSD: linux_xa.c,v 1.4 2024/05/22 15:59:25 riastradh Exp $	*/
2 
3 /*-
4  * Copyright (c) 2021 The NetBSD Foundation, Inc.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
17  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
18  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
20  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26  * POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 #include <sys/cdefs.h>
30 __KERNEL_RCSID(0, "$NetBSD: linux_xa.c,v 1.4 2024/05/22 15:59:25 riastradh Exp $");
31 
32 /*
33  * This is a lame-o implementation of the Linux xarray data type, which
34  * implements a map from 64-bit integers to pointers.  The operations
35  * it supports are designed to be implemented by a radix tree, but
36  * NetBSD's radixtree(9) doesn't quite support them all, and it's a bit
37  * of work to implement them, so this just uses a red/black tree
38  * instead at the cost of some performance in certain types of lookups
39  * (and negative-lookups -- finding a free key).
40  */
41 
42 #include <sys/rbtree.h>
43 
44 #include <linux/xarray.h>
45 
46 struct node {
47 	struct rb_node	n_rb;
48 	uint64_t	n_key;
49 	void		*n_datum;
50 };
51 
52 static int
compare_nodes(void * cookie,const void * va,const void * vb)53 compare_nodes(void *cookie, const void *va, const void *vb)
54 {
55 	const struct node *a = va, *b = vb;
56 
57 	if (a->n_key < b->n_key)
58 		return -1;
59 	if (a->n_key > b->n_key)
60 		return +1;
61 	return 0;
62 }
63 
64 static int
compare_node_key(void * cookie,const void * vn,const void * vk)65 compare_node_key(void *cookie, const void *vn, const void *vk)
66 {
67 	const struct node *n = vn;
68 	const uint64_t *k = vk;
69 
70 	if (n->n_key < *k)
71 		return -1;
72 	if (n->n_key > *k)
73 		return +1;
74 	return 0;
75 }
76 
77 static const rb_tree_ops_t xa_rb_ops = {
78 	.rbto_compare_nodes = compare_nodes,
79 	.rbto_compare_key = compare_node_key,
80 	.rbto_node_offset = offsetof(struct node, n_rb),
81 };
82 
83 const struct xa_limit xa_limit_32b = { .min = 0, .max = UINT32_MAX };
84 
85 void
xa_init_flags(struct xarray * xa,gfp_t gfp)86 xa_init_flags(struct xarray *xa, gfp_t gfp)
87 {
88 
89 	mutex_init(&xa->xa_lock, MUTEX_DEFAULT, IPL_VM);
90 	rb_tree_init(&xa->xa_tree, &xa_rb_ops);
91 	xa->xa_gfp = gfp;
92 }
93 
94 void
xa_destroy(struct xarray * xa)95 xa_destroy(struct xarray *xa)
96 {
97 	struct node *n;
98 
99 	/*
100 	 * Linux allows xa to remain populated on destruction; it is
101 	 * our job to free any internal node structures.
102 	 */
103 	while ((n = RB_TREE_MIN(&xa->xa_tree)) != NULL) {
104 		rb_tree_remove_node(&xa->xa_tree, n);
105 		kmem_free(n, sizeof(*n));
106 	}
107 	mutex_destroy(&xa->xa_lock);
108 }
109 
110 void *
xa_load(struct xarray * xa,unsigned long key)111 xa_load(struct xarray *xa, unsigned long key)
112 {
113 	const uint64_t key64 = key;
114 	struct node *n;
115 
116 	/* XXX pserialize */
117 	mutex_enter(&xa->xa_lock);
118 	n = rb_tree_find_node(&xa->xa_tree, &key64);
119 	mutex_exit(&xa->xa_lock);
120 
121 	return n ? n->n_datum : NULL;
122 }
123 
124 void *
xa_store(struct xarray * xa,unsigned long key,void * datum,gfp_t gfp)125 xa_store(struct xarray *xa, unsigned long key, void *datum, gfp_t gfp)
126 {
127 	struct node *n, *collision, *recollision;
128 
129 	KASSERT(datum != NULL);
130 	KASSERT(((uintptr_t)datum & 0x3) == 0);
131 
132 	n = kmem_zalloc(sizeof(*n), gfp & __GFP_WAIT ? KM_SLEEP : KM_NOSLEEP);
133 	if (n == NULL)
134 		return XA_ERROR(-ENOMEM);
135 	n->n_key = key;
136 	n->n_datum = datum;
137 
138 	mutex_enter(&xa->xa_lock);
139 	collision = rb_tree_insert_node(&xa->xa_tree, n);
140 	if (collision != n) {
141 		rb_tree_remove_node(&xa->xa_tree, n);
142 		recollision = rb_tree_insert_node(&xa->xa_tree, n);
143 		KASSERT(recollision == n);
144 	}
145 	mutex_exit(&xa->xa_lock);
146 
147 	if (collision != n) {
148 		datum = collision->n_datum;
149 		kmem_free(collision, sizeof(*collision));
150 	}
151 	return datum;
152 }
153 
154 int
xa_alloc(struct xarray * xa,uint32_t * idp,void * datum,struct xa_limit limit,gfp_t gfp)155 xa_alloc(struct xarray *xa, uint32_t *idp, void *datum, struct xa_limit limit,
156     gfp_t gfp)
157 {
158 	uint64_t key64 = limit.min;
159 	struct node *n, *n1, *collision __diagused;
160 	int error;
161 
162 	KASSERTMSG(limit.min < limit.max, "min=%"PRIu32" max=%"PRIu32,
163 	    limit.min, limit.max);
164 
165 	n = kmem_zalloc(sizeof(*n), gfp & __GFP_WAIT ? KM_SLEEP : KM_NOSLEEP);
166 	if (n == NULL)
167 		return -ENOMEM;
168 	n->n_datum = datum;
169 
170 	mutex_enter(&xa->xa_lock);
171 	while ((n1 = rb_tree_find_node_geq(&xa->xa_tree, &key64)) != NULL &&
172 	    n1->n_key == key64) {
173 		if (key64 == limit.max) {
174 			error = -EBUSY;
175 			goto out;
176 		}
177 		KASSERT(key64 < UINT32_MAX);
178 		key64++;
179 	}
180 	/* Found a hole -- insert in it.  */
181 	KASSERT(n1 == NULL || n1->n_key > key64);
182 	n->n_key = key64;
183 	collision = rb_tree_insert_node(&xa->xa_tree, n);
184 	KASSERT(collision == n);
185 	error = 0;
186 out:	mutex_exit(&xa->xa_lock);
187 
188 	if (error)
189 		return error;
190 	*idp = key64;
191 	return 0;
192 }
193 
194 void *
xa_find(struct xarray * xa,unsigned long * startp,unsigned long max,unsigned tagmask)195 xa_find(struct xarray *xa, unsigned long *startp, unsigned long max,
196     unsigned tagmask)
197 {
198 	uint64_t key64 = *startp;
199 	struct node *n = NULL;
200 
201 	KASSERT(tagmask == -1);	/* not yet supported */
202 
203 	mutex_enter(&xa->xa_lock);
204 	n = rb_tree_find_node_geq(&xa->xa_tree, &key64);
205 	mutex_exit(&xa->xa_lock);
206 
207 	if (n == NULL || n->n_key > max)
208 		return NULL;
209 
210 	*startp = n->n_key;
211 	return n->n_datum;
212 }
213 
214 void *
xa_find_after(struct xarray * xa,unsigned long * startp,unsigned long max,unsigned tagmask)215 xa_find_after(struct xarray *xa, unsigned long *startp, unsigned long max,
216     unsigned tagmask)
217 {
218 	unsigned long start = *startp + 1;
219 	void *found;
220 
221 	if (start == max)
222 		return NULL;
223 	found = xa_find(xa, &start, max, tagmask);
224 	if (found)
225 		*startp = start;
226 	return found;
227 }
228 
229 void *
xa_erase(struct xarray * xa,unsigned long key)230 xa_erase(struct xarray *xa, unsigned long key)
231 {
232 	uint64_t key64 = key;
233 	struct node *n;
234 	void *datum = NULL;
235 
236 	mutex_enter(&xa->xa_lock);
237 	n = rb_tree_find_node(&xa->xa_tree, &key64);
238 	if (n)
239 		rb_tree_remove_node(&xa->xa_tree, n);
240 	mutex_exit(&xa->xa_lock);
241 
242 	if (n) {
243 		datum = n->n_datum;
244 		kmem_free(n, sizeof(*n));
245 	}
246 	return datum;
247 }
248