1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 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/cdefs.h> 32 __FBSDID("$FreeBSD$"); 33 34 #include <sys/param.h> 35 #include <sys/kernel.h> 36 #include <sys/lock.h> 37 #include <sys/pctrie.h> 38 #include <sys/rangeset.h> 39 #include <vm/uma.h> 40 41 #ifdef DIAGNOSTIC 42 static void rangeset_check(struct rangeset *rs); 43 #else 44 #define rangeset_check(rs) 45 #endif 46 47 static uma_zone_t rs_node_zone; 48 49 static void 50 rs_rangeset_init(void *arg __unused) 51 { 52 53 rs_node_zone = uma_zcreate("rangeset pctrie nodes", 54 pctrie_node_size(), NULL, NULL, pctrie_zone_init, NULL, 55 UMA_ALIGN_PTR, 0); 56 } 57 SYSINIT(rs, SI_SUB_LOCK, SI_ORDER_ANY, rs_rangeset_init, NULL); 58 59 static void * 60 rs_node_alloc(struct pctrie *ptree) 61 { 62 struct rangeset *rs; 63 64 rs = __containerof(ptree, struct rangeset, rs_trie); 65 return (uma_zalloc(rs_node_zone, rs->rs_alloc_flags)); 66 } 67 68 static void 69 rs_node_free(struct pctrie *ptree __unused, void *node) 70 { 71 72 uma_zfree(rs_node_zone, node); 73 } 74 75 void 76 rangeset_init(struct rangeset *rs, rs_dup_data_t dup_data, 77 rs_free_data_t free_data, void *data_ctx, u_int alloc_flags) 78 { 79 80 pctrie_init(&rs->rs_trie); 81 rs->rs_dup_data = dup_data; 82 rs->rs_free_data = free_data; 83 rs->rs_data_ctx = data_ctx; 84 rs->rs_alloc_flags = alloc_flags; 85 } 86 87 void 88 rangeset_fini(struct rangeset *rs) 89 { 90 91 rangeset_check(rs); 92 rangeset_remove_all(rs); 93 } 94 95 bool 96 rangeset_check_empty(struct rangeset *rs, uint64_t start, uint64_t end) 97 { 98 struct rs_el *r; 99 uint64_t *r1; 100 101 rangeset_check(rs); 102 r1 = pctrie_lookup_le(&rs->rs_trie, end); 103 if (r1 != NULL) { 104 r = __containerof(r1, struct rs_el, re_start); 105 if (r->re_end > start) 106 return (false); 107 } 108 return (true); 109 } 110 111 int 112 rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end, 113 void *data) 114 { 115 struct rs_el *r; 116 int error; 117 118 rangeset_check(rs); 119 error = rangeset_remove(rs, start, end); 120 if (error != 0) 121 return (error); 122 r = data; 123 r->re_start = start; 124 r->re_end = end; 125 error = pctrie_insert(&rs->rs_trie, &r->re_start, rs_node_alloc); 126 rangeset_check(rs); 127 return (error); 128 } 129 130 int 131 rangeset_remove_pred(struct rangeset *rs, uint64_t start, uint64_t end, 132 rs_pred_t pred) 133 { 134 struct rs_el *r, *rn; 135 uint64_t *r1; 136 int error; 137 138 rangeset_check(rs); 139 error = 0; 140 for (; end > 0 && start < end;) { 141 r1 = pctrie_lookup_le(&rs->rs_trie, end - 1); 142 if (r1 == NULL) 143 break; 144 r = __containerof(r1, struct rs_el, re_start); 145 146 /* 147 * ------============================--|-------|---- 148 * rs re s e 149 */ 150 if (r->re_end <= start) 151 break; 152 153 if (r->re_end <= end) { 154 if (r->re_start < start) { 155 /* 156 * ------========|==============-------|---- 157 * rs s re e 158 */ 159 if (pred(rs->rs_data_ctx, r)) 160 r->re_end = start; 161 break; 162 } 163 164 /* 165 * ------|--------===================----------|---- 166 * s rs re e 167 */ 168 end = r->re_start; 169 if (pred(rs->rs_data_ctx, r)) { 170 pctrie_remove(&rs->rs_trie, r->re_start, 171 rs_node_free); 172 rs->rs_free_data(rs->rs_data_ctx, r); 173 } 174 continue; 175 } 176 177 /* 178 * ------|--------====================|==========---- 179 * s rs e re 180 */ 181 if (r->re_start >= start) { 182 if (pred(rs->rs_data_ctx, r)) { 183 pctrie_remove(&rs->rs_trie, r->re_start, 184 rs_node_free); 185 r->re_start = end; 186 error = pctrie_insert(&rs->rs_trie, 187 &r->re_start, rs_node_alloc); 188 /* 189 * The insert above must succeed 190 * because rs_node zone is marked 191 * nofree and we freed one element 192 * just before. 193 */ 194 MPASS(error == 0); 195 } else { 196 end = r->re_start; 197 } 198 continue; 199 } 200 201 /* 202 * ------=========|===================|==========---- 203 * rs s e re 204 */ 205 if (pred(rs->rs_data_ctx, r)) { 206 /* 207 * Split. Can only happen once, and then if 208 * any allocation fails, the rangeset is kept 209 * intact. 210 */ 211 rn = rs->rs_dup_data(rs->rs_data_ctx, r); 212 if (rn == NULL) { 213 error = ENOMEM; 214 break; 215 } 216 rn->re_start = end; 217 rn->re_end = r->re_end; 218 error = pctrie_insert(&rs->rs_trie, &rn->re_start, 219 rs_node_alloc); 220 if (error != 0) { 221 rs->rs_free_data(rs->rs_data_ctx, rn); 222 break; 223 } 224 r->re_end = start; 225 } 226 break; 227 } 228 rangeset_check(rs); 229 return (error); 230 } 231 232 static bool 233 rangeset_true_pred(void *ctx __unused, void *r __unused) 234 { 235 236 return (true); 237 } 238 239 int 240 rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end) 241 { 242 243 return (rangeset_remove_pred(rs, start, end, rangeset_true_pred)); 244 } 245 246 void 247 rangeset_remove_all(struct rangeset *rs) 248 { 249 struct rs_el *r; 250 uint64_t *r1; 251 252 for (;;) { 253 r1 = pctrie_lookup_ge(&rs->rs_trie, 0); 254 if (r1 == NULL) 255 break; 256 r = __containerof(r1, struct rs_el, re_start); 257 pctrie_remove(&rs->rs_trie, r->re_start, rs_node_free); 258 rs->rs_free_data(rs->rs_data_ctx, r); 259 } 260 } 261 262 void * 263 rangeset_lookup(struct rangeset *rs, uint64_t place) 264 { 265 struct rs_el *r; 266 uint64_t *r1; 267 268 rangeset_check(rs); 269 r1 = pctrie_lookup_le(&rs->rs_trie, place); 270 if (r1 == NULL) 271 return (NULL); 272 r = __containerof(r1, struct rs_el, re_start); 273 if (r->re_end <= place) 274 return (NULL); 275 return (r); 276 } 277 278 int 279 rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs) 280 { 281 struct rs_el *src_r, *dst_r; 282 uint64_t cursor, *r1; 283 int error; 284 285 MPASS(pctrie_is_empty(&dst_rs->rs_trie)); 286 rangeset_check(src_rs); 287 MPASS(dst_rs->rs_dup_data == src_rs->rs_dup_data); 288 289 error = 0; 290 for (cursor = 0;; cursor = src_r->re_start + 1) { 291 r1 = pctrie_lookup_ge(&src_rs->rs_trie, cursor); 292 if (r1 == NULL) 293 break; 294 src_r = __containerof(r1, struct rs_el, re_start); 295 dst_r = dst_rs->rs_dup_data(dst_rs->rs_data_ctx, src_r); 296 if (dst_r == NULL) { 297 error = ENOMEM; 298 break; 299 } 300 error = pctrie_insert(&dst_rs->rs_trie, &dst_r->re_start, 301 rs_node_alloc); 302 if (error != 0) 303 break; 304 } 305 if (error != 0) 306 rangeset_remove_all(dst_rs); 307 return (error); 308 } 309 310 #ifdef DIAGNOSTIC 311 static void 312 rangeset_check(struct rangeset *rs) 313 { 314 struct rs_el *r, *rp; 315 uint64_t cursor, *r1; 316 317 for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) { 318 r1 = pctrie_lookup_ge(&rs->rs_trie, cursor); 319 if (r1 == NULL) 320 break; 321 r = __containerof(r1, struct rs_el, re_start); 322 KASSERT(r->re_start < r->re_end, 323 ("invalid interval rs %p elem %p (%#jx, %#jx)", 324 rs, r, (uintmax_t)r->re_start, (uintmax_t)r->re_end)); 325 if (rp != NULL) { 326 KASSERT(rp->re_end <= r->re_start, 327 ("non-ascending neighbors rs %p " 328 "prev elem %p (%#jx, %#jx) elem %p (%#jx, %#jx)", 329 rs, rp, (uintmax_t)rp->re_start, 330 (uintmax_t)rp->re_end, r, (uintmax_t)r->re_start, 331 (uintmax_t)r->re_end)); 332 } 333 } 334 } 335 #endif 336 337 #include "opt_ddb.h" 338 #ifdef DDB 339 #include <sys/kernel.h> 340 #include <ddb/ddb.h> 341 342 DB_SHOW_COMMAND(rangeset, rangeset_show_fn) 343 { 344 struct rangeset *rs; 345 struct rs_el *r; 346 uint64_t cursor, *r1; 347 348 if (!have_addr) { 349 db_printf("show rangeset addr\n"); 350 return; 351 } 352 353 rs = (struct rangeset *)addr; 354 db_printf("rangeset %p\n", rs); 355 for (cursor = 0;; cursor = r->re_start + 1) { 356 r1 = pctrie_lookup_ge(&rs->rs_trie, cursor); 357 if (r1 == NULL) 358 break; 359 r = __containerof(r1, struct rs_el, re_start); 360 db_printf(" el %p start %#jx end %#jx\n", 361 r, r->re_start, r->re_end); 362 } 363 } 364 #endif 365