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