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 __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