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