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/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 void
 236 rangeset_remove_all(struct rangeset *rs)
 237 {
 238         struct rs_el *r;
 239
 240         for (;;) {
 241                 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, 0);
 242                 if (r == NULL)
 243                         break;
 244                 RANGESET_PCTRIE_REMOVE(&rs->rs_trie, r->re_start);
 245                 rs->rs_free_data(rs->rs_data_ctx, r);
 246         }
 247 }
 248
 249 void *
 250 rangeset_lookup(struct rangeset *rs, uint64_t place)
 251 {
 252         struct rs_el *r;
 253
 254         rangeset_check(rs);
 255         r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, place);
 256         if (r == NULL)
 257                 return (NULL);
 258         if (r->re_end <= place)
 259                 return (NULL);
 260         return (r);
 261 }
 262
 263 int
 264 rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs)
 265 {
 266         struct rs_el *src_r, *dst_r;
 267         uint64_t cursor;
 268         int error;
 269
 270         MPASS(pctrie_is_empty(&dst_rs->rs_trie));
 271         rangeset_check(src_rs);
 272         MPASS(dst_rs->rs_dup_data == src_rs->rs_dup_data);
 273
 274         error = 0;
 275         for (cursor = 0;; cursor = src_r->re_start + 1) {
 276                 src_r = RANGESET_PCTRIE_LOOKUP_GE(&src_rs->rs_trie, cursor);
 277                 if (src_r == NULL)
 278                         break;
 279                 dst_r = dst_rs->rs_dup_data(dst_rs->rs_data_ctx, src_r);
 280                 if (dst_r == NULL) {
 281                         error = ENOMEM;
 282                         break;
 283                 }
 284                 error = RANGESET_PCTRIE_INSERT(&dst_rs->rs_trie, dst_r);
 285                 if (error != 0)
 286                         break;
 287         }
 288         if (error != 0)
 289                 rangeset_remove_all(dst_rs);
 290         return (error);
 291 }
 292
 293 #ifdef DIAGNOSTIC
 294 static void
 295 rangeset_check(struct rangeset *rs)
 296 {
 297         struct rs_el *r, *rp;
 298         uint64_t cursor;
 299
 300         for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) {
 301                 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor);
 302                 if (r == NULL)
 303                         break;
 304                 KASSERT(r->re_start < r->re_end,
 305                     ("invalid interval rs %p elem %p (%#jx, %#jx)",
 306                     rs, r, (uintmax_t)r->re_start,  (uintmax_t)r->re_end));
 307                 if (rp != NULL) {
 308                         KASSERT(rp->re_end <= r->re_start,
 309                             ("non-ascending neighbors rs %p "
 310                             "prev elem %p (%#jx, %#jx) elem %p (%#jx, %#jx)",
 311                             rs, rp,  (uintmax_t)rp->re_start,
 312                             (uintmax_t)rp->re_end, r,  (uintmax_t)r->re_start,
 313                             (uintmax_t)r->re_end));
 314                 }
 315         }
 316 }
 317 #endif
 318
 319 #include "opt_ddb.h"
 320 #ifdef DDB
 321 #include <sys/kernel.h>
 322 #include <ddb/ddb.h>
 323
 324 DB_SHOW_COMMAND(rangeset, rangeset_show_fn)
 325 {
 326         struct rangeset *rs;
 327         struct rs_el *r;
 328         uint64_t cursor;
 329
 330         if (!have_addr) {
 331                 db_printf("show rangeset addr\n");
 332                 return;
 333         }
 334
 335         rs = (struct rangeset *)addr;
 336         db_printf("rangeset %p\n", rs);
 337         for (cursor = 0;; cursor = r->re_start + 1) {
 338                 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor);
 339                 if (r == NULL)
 340                         break;
 341                 db_printf("  el %p start %#jx end %#jx\n",
 342                     r, r->re_start, r->re_end);
 343         }
 344 }
 345 #endif