sys/kern/subr_rangeset.c

   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