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