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 39 static void rangeset_check(struct rangeset *rs); 40 #else 41 #define rangeset_check(rs) 42 #endif 43 44 static uma_zone_t rs_node_zone; 45 46 static void 47 rs_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 } 54 SYSINIT(rs, SI_SUB_LOCK, SI_ORDER_ANY, rs_rangeset_init, NULL); 55 56 static void * 57 rs_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 65 static void 66 rs_node_free(struct pctrie *ptree __unused, void *node) 67 { 68 69 uma_zfree(rs_node_zone, node); 70 } 71 72 PCTRIE_DEFINE(RANGESET, rs_el, re_start, rs_node_alloc, rs_node_free); 73 74 void 75 rangeset_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 86 void 87 rangeset_fini(struct rangeset *rs) 88 { 89 90 rangeset_check(rs); 91 rangeset_remove_all(rs); 92 } 93 94 bool 95 rangeset_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 104 int 105 rangeset_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 123 int 124 rangeset_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 221 static bool 222 rangeset_true_pred(void *ctx __unused, void *r __unused) 223 { 224 225 return (true); 226 } 227 228 int 229 rangeset_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 235 static void 236 rangeset_remove_leaf(struct rs_el *r, void *rsv) 237 { 238 struct rangeset *rs = rsv; 239 240 rs->rs_free_data(rs->rs_data_ctx, r); 241 } 242 243 void 244 rangeset_remove_all(struct rangeset *rs) 245 { 246 RANGESET_PCTRIE_RECLAIM_CALLBACK(&rs->rs_trie, 247 rangeset_remove_leaf, rs); 248 } 249 250 void * 251 rangeset_containing(struct rangeset *rs, uint64_t place) 252 { 253 struct rs_el *r; 254 255 rangeset_check(rs); 256 r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, place); 257 if (r != NULL && place < r->re_end) 258 return (r); 259 return (NULL); 260 } 261 262 bool 263 rangeset_empty(struct rangeset *rs, uint64_t start, uint64_t end) 264 { 265 struct rs_el *r; 266 267 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, start + 1); 268 return (r == NULL || r->re_start >= end); 269 } 270 271 void * 272 rangeset_beginning(struct rangeset *rs, uint64_t place) 273 { 274 275 rangeset_check(rs); 276 return (RANGESET_PCTRIE_LOOKUP(&rs->rs_trie, place)); 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; 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 src_r = RANGESET_PCTRIE_LOOKUP_GE(&src_rs->rs_trie, cursor); 293 if (src_r == NULL) 294 break; 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 = RANGESET_PCTRIE_INSERT(&dst_rs->rs_trie, dst_r); 301 if (error != 0) 302 break; 303 } 304 if (error != 0) 305 rangeset_remove_all(dst_rs); 306 return (error); 307 } 308 309 #ifdef DIAGNOSTIC 310 static void 311 rangeset_check(struct rangeset *rs) 312 { 313 struct rs_el *r, *rp; 314 uint64_t cursor; 315 316 for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) { 317 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor); 318 if (r == NULL) 319 break; 320 KASSERT(r->re_start < r->re_end, 321 ("invalid interval rs %p elem %p (%#jx, %#jx)", 322 rs, r, (uintmax_t)r->re_start, (uintmax_t)r->re_end)); 323 if (rp != NULL) { 324 KASSERT(rp->re_end <= r->re_start, 325 ("non-ascending neighbors rs %p " 326 "prev elem %p (%#jx, %#jx) elem %p (%#jx, %#jx)", 327 rs, rp, (uintmax_t)rp->re_start, 328 (uintmax_t)rp->re_end, r, (uintmax_t)r->re_start, 329 (uintmax_t)r->re_end)); 330 } 331 } 332 } 333 #endif 334 335 #include "opt_ddb.h" 336 #ifdef DDB 337 #include <sys/kernel.h> 338 #include <ddb/ddb.h> 339 340 DB_SHOW_COMMAND(rangeset, rangeset_show_fn) 341 { 342 struct rangeset *rs; 343 struct rs_el *r; 344 uint64_t cursor; 345 346 if (!have_addr) { 347 db_printf("show rangeset addr\n"); 348 return; 349 } 350 351 rs = (struct rangeset *)addr; 352 db_printf("rangeset %p\n", rs); 353 for (cursor = 0;; cursor = r->re_start + 1) { 354 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor); 355 if (r == NULL) 356 break; 357 db_printf(" el %p start %#jx end %#jx\n", 358 r, r->re_start, r->re_end); 359 } 360 } 361 #endif 362