1/*-
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright (c) 2019 The FreeBSD Foundation
5 *
6 * This software was developed by Konstantin Belousov <kib@FreeBSD.org>
7 * under sponsorship from the FreeBSD Foundation.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 *    notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 *    notice, this list of conditions and the following disclaimer in the
16 *    documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 */
30
31#include <sys/param.h>
32#include <sys/kernel.h>
33#include <sys/lock.h>
34#include <sys/pctrie.h>
35#include <sys/rangeset.h>
36#include <vm/uma.h>
37
38#ifdef DIAGNOSTIC
39static void rangeset_check(struct rangeset *rs);
40#else
41#define	rangeset_check(rs)
42#endif
43
44static uma_zone_t rs_node_zone;
45
46static void
47rs_rangeset_init(void *arg __unused)
48{
49
50	rs_node_zone = uma_zcreate("rangeset pctrie nodes",
51	    pctrie_node_size(), NULL, NULL, pctrie_zone_init, NULL,
52	    UMA_ALIGN_PTR, 0);
53}
54SYSINIT(rs, SI_SUB_LOCK, SI_ORDER_ANY, rs_rangeset_init, NULL);
55
56static void *
57rs_node_alloc(struct pctrie *ptree)
58{
59	struct rangeset *rs;
60
61	rs = __containerof(ptree, struct rangeset, rs_trie);
62	return (uma_zalloc(rs_node_zone, rs->rs_alloc_flags));
63}
64
65static void
66rs_node_free(struct pctrie *ptree __unused, void *node)
67{
68
69	uma_zfree(rs_node_zone, node);
70}
71
72PCTRIE_DEFINE(RANGESET, rs_el, re_start, rs_node_alloc, rs_node_free);
73
74void
75rangeset_init(struct rangeset *rs, rs_dup_data_t dup_data,
76    rs_free_data_t free_data, void *data_ctx, u_int alloc_flags)
77{
78
79	pctrie_init(&rs->rs_trie);
80	rs->rs_dup_data = dup_data;
81	rs->rs_free_data = free_data;
82	rs->rs_data_ctx = data_ctx;
83	rs->rs_alloc_flags = alloc_flags;
84}
85
86void
87rangeset_fini(struct rangeset *rs)
88{
89
90	rangeset_check(rs);
91	rangeset_remove_all(rs);
92}
93
94bool
95rangeset_check_empty(struct rangeset *rs, uint64_t start, uint64_t end)
96{
97	struct rs_el *r;
98
99	rangeset_check(rs);
100	r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, end);
101	return (r == NULL || r->re_end <= start);
102}
103
104int
105rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end,
106    void *data)
107{
108	struct rs_el *r;
109	int error;
110
111	rangeset_check(rs);
112	error = rangeset_remove(rs, start, end);
113	if (error != 0)
114		return (error);
115	r = data;
116	r->re_start = start;
117	r->re_end = end;
118	error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, r);
119	rangeset_check(rs);
120	return (error);
121}
122
123int
124rangeset_remove_pred(struct rangeset *rs, uint64_t start, uint64_t end,
125    rs_pred_t pred)
126{
127	struct rs_el *r, *rn;
128	int error;
129
130	rangeset_check(rs);
131	error = 0;
132	for (; end > 0 && start < end;) {
133		r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, end - 1);
134		if (r == NULL)
135			break;
136
137		/*
138		 * ------============================--|-------|----
139		 *	 rs    	       	       	   re  s       e
140		 */
141		if (r->re_end <= start)
142			break;
143
144		if (r->re_end <= end) {
145			if (r->re_start < start) {
146				/*
147				 * ------========|==============-------|----
148				 *	 rs    	 s     	      re       e
149				 */
150				if (pred(rs->rs_data_ctx, r))
151					r->re_end = start;
152				break;
153			}
154
155			/*
156			 * ------|--------===================----------|----
157			 *	 s    	  rs   	       	   re          e
158			 */
159			end = r->re_start;
160			if (pred(rs->rs_data_ctx, r)) {
161				RANGESET_PCTRIE_REMOVE(&rs->rs_trie,
162				    r->re_start);
163				rs->rs_free_data(rs->rs_data_ctx, r);
164			}
165			continue;
166		}
167
168		/*
169		 * ------|--------====================|==========----
170		 *	 s    	  rs   	       	      e         re
171		 */
172		if (r->re_start >= start) {
173			if (pred(rs->rs_data_ctx, r)) {
174				RANGESET_PCTRIE_REMOVE(&rs->rs_trie,
175				    r->re_start);
176				r->re_start = end;
177				error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, r);
178				/*
179				 * The insert above must succeed
180				 * because rs_node zone is marked
181				 * nofree and we freed one element
182				 * just before.
183				 */
184				MPASS(error == 0);
185			} else {
186				end = r->re_start;
187			}
188			continue;
189		}
190
191		/*
192		 * ------=========|===================|==========----
193		 *	 rs   	  s    	       	      e         re
194		 */
195		if (pred(rs->rs_data_ctx, r)) {
196			/*
197			 * Split.  Can only happen once, and then if
198			 * any allocation fails, the rangeset is kept
199			 * intact.
200			 */
201			rn = rs->rs_dup_data(rs->rs_data_ctx, r);
202			if (rn == NULL) {
203				error = ENOMEM;
204				break;
205			}
206			rn->re_start = end;
207			rn->re_end = r->re_end;
208			error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, rn);
209			if (error != 0) {
210				rs->rs_free_data(rs->rs_data_ctx, rn);
211				break;
212			}
213			r->re_end = start;
214		}
215		break;
216	}
217	rangeset_check(rs);
218	return (error);
219}
220
221static bool
222rangeset_true_pred(void *ctx __unused, void *r __unused)
223{
224
225	return (true);
226}
227
228int
229rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end)
230{
231
232	return (rangeset_remove_pred(rs, start, end, rangeset_true_pred));
233}
234
235void
236rangeset_remove_all(struct rangeset *rs)
237{
238	struct rs_el *r;
239
240	for (;;) {
241		r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, 0);
242		if (r == NULL)
243			break;
244		RANGESET_PCTRIE_REMOVE(&rs->rs_trie, r->re_start);
245		rs->rs_free_data(rs->rs_data_ctx, r);
246	}
247}
248
249void *
250rangeset_lookup(struct rangeset *rs, uint64_t place)
251{
252	struct rs_el *r;
253
254	rangeset_check(rs);
255	r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, place);
256	if (r == NULL)
257		return (NULL);
258	if (r->re_end <= place)
259		return (NULL);
260	return (r);
261}
262
263int
264rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs)
265{
266	struct rs_el *src_r, *dst_r;
267	uint64_t cursor;
268	int error;
269
270	MPASS(pctrie_is_empty(&dst_rs->rs_trie));
271	rangeset_check(src_rs);
272	MPASS(dst_rs->rs_dup_data == src_rs->rs_dup_data);
273
274	error = 0;
275	for (cursor = 0;; cursor = src_r->re_start + 1) {
276		src_r = RANGESET_PCTRIE_LOOKUP_GE(&src_rs->rs_trie, cursor);
277		if (src_r == NULL)
278			break;
279		dst_r = dst_rs->rs_dup_data(dst_rs->rs_data_ctx, src_r);
280		if (dst_r == NULL) {
281			error = ENOMEM;
282			break;
283		}
284		error = RANGESET_PCTRIE_INSERT(&dst_rs->rs_trie, dst_r);
285		if (error != 0)
286			break;
287	}
288	if (error != 0)
289		rangeset_remove_all(dst_rs);
290	return (error);
291}
292
293#ifdef DIAGNOSTIC
294static void
295rangeset_check(struct rangeset *rs)
296{
297	struct rs_el *r, *rp;
298	uint64_t cursor;
299
300	for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) {
301		r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor);
302		if (r == NULL)
303			break;
304		KASSERT(r->re_start < r->re_end,
305		    ("invalid interval rs %p elem %p (%#jx, %#jx)",
306		    rs, r, (uintmax_t)r->re_start,  (uintmax_t)r->re_end));
307		if (rp != NULL) {
308			KASSERT(rp->re_end <= r->re_start,
309			    ("non-ascending neighbors rs %p "
310			    "prev elem %p (%#jx, %#jx) elem %p (%#jx, %#jx)",
311			    rs, rp,  (uintmax_t)rp->re_start,
312			    (uintmax_t)rp->re_end, r,  (uintmax_t)r->re_start,
313			    (uintmax_t)r->re_end));
314		}
315	}
316}
317#endif
318
319#include "opt_ddb.h"
320#ifdef DDB
321#include <sys/kernel.h>
322#include <ddb/ddb.h>
323
324DB_SHOW_COMMAND(rangeset, rangeset_show_fn)
325{
326	struct rangeset *rs;
327	struct rs_el *r;
328	uint64_t cursor;
329
330	if (!have_addr) {
331		db_printf("show rangeset addr\n");
332		return;
333	}
334
335	rs = (struct rangeset *)addr;
336	db_printf("rangeset %p\n", rs);
337	for (cursor = 0;; cursor = r->re_start + 1) {
338		r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor);
339		if (r == NULL)
340			break;
341		db_printf("  el %p start %#jx end %#jx\n",
342		    r, r->re_start, r->re_end);
343	}
344}
345#endif
346