sys/kern/subr_rangeset.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2019 The FreeBSD Foundation
   5  * All rights reserved.
   6  *
   7  * This software was developed by Konstantin Belousov <kib@FreeBSD.org>
   8  * under sponsorship from the FreeBSD Foundation.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  29  * SUCH DAMAGE.
  30  */
  31
  32 #include <sys/cdefs.h>
  33 __FBSDID("$FreeBSD$");
  34
  35 #include <sys/param.h>
  36 #include <sys/kernel.h>
  37 #include <sys/lock.h>
  38 #include <sys/pctrie.h>
  39 #include <sys/rangeset.h>
  40 #include <vm/uma.h>
  41
  42 #ifdef DIAGNOSTIC
  43 static void rangeset_check(struct rangeset *rs);
  44 #else
  45 #define rangeset_check(rs)
  46 #endif
  47
  48 static uma_zone_t rs_node_zone;
  49
  50 static void
  51 rs_rangeset_init(void *arg __unused)
  52 {
  53
  54         rs_node_zone = uma_zcreate("rangeset pctrie nodes",
  55             pctrie_node_size(), NULL, NULL, pctrie_zone_init, NULL,
  56             UMA_ALIGN_PTR, 0);
  57 }
  58 SYSINIT(rs, SI_SUB_LOCK, SI_ORDER_ANY, rs_rangeset_init, NULL);
  59
  60 static void *
  61 rs_node_alloc(struct pctrie *ptree)
  62 {
  63         struct rangeset *rs;
  64
  65         rs = __containerof(ptree, struct rangeset, rs_trie);
  66         return (uma_zalloc(rs_node_zone, rs->rs_alloc_flags));
  67 }
  68
  69 static void
  70 rs_node_free(struct pctrie *ptree __unused, void *node)
  71 {
  72
  73         uma_zfree(rs_node_zone, node);
  74 }
  75
  76 void
  77 rangeset_init(struct rangeset *rs, rs_dup_data_t dup_data,
  78     rs_free_data_t free_data, void *data_ctx, u_int alloc_flags)
  79 {
  80
  81         pctrie_init(&rs->rs_trie);
  82         rs->rs_dup_data = dup_data;
  83         rs->rs_free_data = free_data;
  84         rs->rs_data_ctx = data_ctx;
  85         rs->rs_alloc_flags = alloc_flags;
  86 }
  87
  88 void
  89 rangeset_fini(struct rangeset *rs)
  90 {
  91
  92         rangeset_check(rs);
  93         rangeset_remove_all(rs);
  94 }
  95
  96 bool
  97 rangeset_check_empty(struct rangeset *rs, uint64_t start, uint64_t end)
  98 {
  99         struct rs_el *r;
 100         uint64_t *r1;
 101
 102         rangeset_check(rs);
 103         r1 = pctrie_lookup_le(&rs->rs_trie, end);
 104         if (r1 != NULL) {
 105                 r = __containerof(r1, struct rs_el, re_start);
 106                 if (r->re_end > start)
 107                         return (false);
 108         }
 109         return (true);
 110 }
 111
 112 int
 113 rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end,
 114     void *data)
 115 {
 116         struct rs_el *r;
 117         int error;
 118
 119         rangeset_check(rs);
 120         error = rangeset_remove(rs, start, end);
 121         if (error != 0)
 122                 return (error);
 123         r = data;
 124         r->re_start = start;
 125         r->re_end = end;
 126         error = pctrie_insert(&rs->rs_trie, &r->re_start, rs_node_alloc);
 127         rangeset_check(rs);
 128         return (error);
 129 }
 130
 131 int
 132 rangeset_remove_pred(struct rangeset *rs, uint64_t start, uint64_t end,
 133     rs_pred_t pred)
 134 {
 135         struct rs_el *r, *rn;
 136         uint64_t *r1;
 137         int error;
 138
 139         rangeset_check(rs);
 140         error = 0;
 141         for (; end > 0 && start < end;) {
 142                 r1 = pctrie_lookup_le(&rs->rs_trie, end - 1);
 143                 if (r1 == NULL)
 144                         break;
 145                 r = __containerof(r1, struct rs_el, re_start);
 146
 147                 /*
 148                  * ------============================--|-------|----
 149                  *       rs                        re  s       e
 150                  */
 151                 if (r->re_end <= start)
 152                         break;
 153
 154                 if (r->re_end <= end) {
 155                         if (r->re_start < start) {
 156                                 /*
 157                                  * ------========|==============-------|----
 158                                  *       rs      s            re       e
 159                                  */
 160                                 if (pred(rs->rs_data_ctx, r))
 161                                         r->re_end = start;
 162                                 break;
 163                         }
 164
 165                         /*
 166                          * ------|--------===================----------|----
 167                          *       s        rs               re          e
 168                          */
 169                         end = r->re_start;
 170                         if (pred(rs->rs_data_ctx, r)) {
 171                                 pctrie_remove(&rs->rs_trie, r->re_start,
 172                                     rs_node_free);
 173                                 rs->rs_free_data(rs->rs_data_ctx, r);
 174                         }
 175                         continue;
 176                 }
 177
 178                 /*
 179                  * ------|--------====================|==========----
 180                  *       s        rs                  e         re
 181                  */
 182                 if (r->re_start >= start) {
 183                         if (pred(rs->rs_data_ctx, r)) {
 184                                 pctrie_remove(&rs->rs_trie, r->re_start,
 185                                     rs_node_free);
 186                                 r->re_start = end;
 187                                 error = pctrie_insert(&rs->rs_trie,
 188                                     &r->re_start, rs_node_alloc);
 189                                 /*
 190                                  * The insert above must succeed
 191                                  * because rs_node zone is marked
 192                                  * nofree and we freed one element
 193                                  * just before.
 194                                  */
 195                                 MPASS(error == 0);
 196                         } else {
 197                                 end = r->re_start;
 198                         }
 199                         continue;
 200                 }
 201
 202                 /*
 203                  * ------=========|===================|==========----
 204                  *       rs       s                   e         re
 205                  */
 206                 if (pred(rs->rs_data_ctx, r)) {
 207                         /*
 208                          * Split.  Can only happen once, and then if
 209                          * any allocation fails, the rangeset is kept
 210                          * intact.
 211                          */
 212                         rn = rs->rs_dup_data(rs->rs_data_ctx, r);
 213                         if (rn == NULL) {
 214                                 error = ENOMEM;
 215                                 break;
 216                         }
 217                         rn->re_start = end;
 218                         rn->re_end = r->re_end;
 219                         error = pctrie_insert(&rs->rs_trie, &rn->re_start,
 220                             rs_node_alloc);
 221                         if (error != 0) {
 222                                 rs->rs_free_data(rs->rs_data_ctx, rn);
 223                                 break;
 224                         }
 225                         r->re_end = start;
 226                 }
 227                 break;
 228         }
 229         rangeset_check(rs);
 230         return (error);
 231 }
 232
 233 static bool
 234 rangeset_true_pred(void *ctx __unused, void *r __unused)
 235 {
 236
 237         return (true);
 238 }
 239
 240 int
 241 rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end)
 242 {
 243
 244         return (rangeset_remove_pred(rs, start, end, rangeset_true_pred));
 245 }
 246
 247 void
 248 rangeset_remove_all(struct rangeset *rs)
 249 {
 250         struct rs_el *r;
 251         uint64_t *r1;
 252
 253         for (;;) {
 254                 r1 = pctrie_lookup_ge(&rs->rs_trie, 0);
 255                 if (r1 == NULL)
 256                         break;
 257                 r = __containerof(r1, struct rs_el, re_start);
 258                 pctrie_remove(&rs->rs_trie, r->re_start, rs_node_free);
 259                 rs->rs_free_data(rs->rs_data_ctx, r);
 260         }
 261 }
 262
 263 void *
 264 rangeset_lookup(struct rangeset *rs, uint64_t place)
 265 {
 266         struct rs_el *r;
 267         uint64_t *r1;
 268
 269         rangeset_check(rs);
 270         r1 = pctrie_lookup_le(&rs->rs_trie, place);
 271         if (r1 == NULL)
 272                 return (NULL);
 273         r = __containerof(r1, struct rs_el, re_start);
 274         if (r->re_end <= place)
 275                 return (NULL);
 276         return (r);
 277 }
 278
 279 int
 280 rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs)
 281 {
 282         struct rs_el *src_r, *dst_r;
 283         uint64_t cursor, *r1;
 284         int error;
 285
 286         MPASS(pctrie_is_empty(&dst_rs->rs_trie));
 287         rangeset_check(src_rs);
 288         MPASS(dst_rs->rs_dup_data == src_rs->rs_dup_data);
 289
 290         error = 0;
 291         for (cursor = 0;; cursor = src_r->re_start + 1) {
 292                 r1 = pctrie_lookup_ge(&src_rs->rs_trie, cursor);
 293                 if (r1 == NULL)
 294                         break;
 295                 src_r = __containerof(r1, struct rs_el, re_start);
 296                 dst_r = dst_rs->rs_dup_data(dst_rs->rs_data_ctx, src_r);
 297                 if (dst_r == NULL) {
 298                         error = ENOMEM;
 299                         break;
 300                 }
 301                 error = pctrie_insert(&dst_rs->rs_trie, &dst_r->re_start,
 302                     rs_node_alloc);
 303                 if (error != 0)
 304                         break;
 305         }
 306         if (error != 0)
 307                 rangeset_remove_all(dst_rs);
 308         return (error);
 309 }
 310
 311 #ifdef DIAGNOSTIC
 312 static void
 313 rangeset_check(struct rangeset *rs)
 314 {
 315         struct rs_el *r, *rp;
 316         uint64_t cursor, *r1;
 317
 318         for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) {
 319                 r1 = pctrie_lookup_ge(&rs->rs_trie, cursor);
 320                 if (r1 == NULL)
 321                         break;
 322                 r = __containerof(r1, struct rs_el, re_start);
 323                 KASSERT(r->re_start < r->re_end,
 324                     ("invalid interval rs %p elem %p (%#jx, %#jx)",
 325                     rs, r, (uintmax_t)r->re_start,  (uintmax_t)r->re_end));
 326                 if (rp != NULL) {
 327                         KASSERT(rp->re_end <= r->re_start,
 328                             ("non-ascending neighbors rs %p "
 329                             "prev elem %p (%#jx, %#jx) elem %p (%#jx, %#jx)",
 330                             rs, rp,  (uintmax_t)rp->re_start,
 331                             (uintmax_t)rp->re_end, r,  (uintmax_t)r->re_start,
 332                             (uintmax_t)r->re_end));
 333                 }
 334         }
 335 }
 336 #endif
 337
 338 #include "opt_ddb.h"
 339 #ifdef DDB
 340 #include <sys/kernel.h>
 341 #include <ddb/ddb.h>
 342
 343 DB_SHOW_COMMAND(rangeset, rangeset_show_fn)
 344 {
 345         struct rangeset *rs;
 346         struct rs_el *r;
 347         uint64_t cursor, *r1;
 348
 349         if (!have_addr) {
 350                 db_printf("show rangeset addr\n");
 351                 return;
 352         }
 353
 354         rs = (struct rangeset *)addr;
 355         db_printf("rangeset %p\n", rs);
 356         for (cursor = 0;; cursor = r->re_start + 1) {
 357                 r1 = pctrie_lookup_ge(&rs->rs_trie, cursor);
 358                 if (r1 == NULL)
 359                         break;
 360                 r = __containerof(r1, struct rs_el, re_start);
 361                 db_printf("  el %p start %#jx end %#jx\n",
 362                     r, r->re_start, r->re_end);
 363         }
 364 }
 365 #endif