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 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         uint64_t *r1;
 100
 101         rangeset_check(rs);
 102         r1 = pctrie_lookup_le(&rs->rs_trie, end);
 103         if (r1 != NULL) {
 104                 r = __containerof(r1, struct rs_el, re_start);
 105                 if (r->re_end > start)
 106                         return (false);
 107         }
 108         return (true);
 109 }
 110
 111 int
 112 rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end,
 113     void *data)
 114 {
 115         struct rs_el *r;
 116         int error;
 117
 118         rangeset_check(rs);
 119         error = rangeset_remove(rs, start, end);
 120         if (error != 0)
 121                 return (error);
 122         r = data;
 123         r->re_start = start;
 124         r->re_end = end;
 125         error = pctrie_insert(&rs->rs_trie, &r->re_start, rs_node_alloc);
 126         rangeset_check(rs);
 127         return (error);
 128 }
 129
 130 int
 131 rangeset_remove_pred(struct rangeset *rs, uint64_t start, uint64_t end,
 132     rs_pred_t pred)
 133 {
 134         struct rs_el *r, *rn;
 135         uint64_t *r1;
 136         int error;
 137
 138         rangeset_check(rs);
 139         error = 0;
 140         for (; end > 0 && start < end;) {
 141                 r1 = pctrie_lookup_le(&rs->rs_trie, end - 1);
 142                 if (r1 == NULL)
 143                         break;
 144                 r = __containerof(r1, struct rs_el, re_start);
 145
 146                 /*
 147                  * ------============================--|-------|----
 148                  *       rs                        re  s       e
 149                  */
 150                 if (r->re_end <= start)
 151                         break;
 152
 153                 if (r->re_end <= end) {
 154                         if (r->re_start < start) {
 155                                 /*
 156                                  * ------========|==============-------|----
 157                                  *       rs      s            re       e
 158                                  */
 159                                 if (pred(rs->rs_data_ctx, r))
 160                                         r->re_end = start;
 161                                 break;
 162                         }
 163
 164                         /*
 165                          * ------|--------===================----------|----
 166                          *       s        rs               re          e
 167                          */
 168                         end = r->re_start;
 169                         if (pred(rs->rs_data_ctx, r)) {
 170                                 pctrie_remove(&rs->rs_trie, r->re_start,
 171                                     rs_node_free);
 172                                 rs->rs_free_data(rs->rs_data_ctx, r);
 173                         }
 174                         continue;
 175                 }
 176
 177                 /*
 178                  * ------|--------====================|==========----
 179                  *       s        rs                  e         re
 180                  */
 181                 if (r->re_start >= start) {
 182                         if (pred(rs->rs_data_ctx, r)) {
 183                                 pctrie_remove(&rs->rs_trie, r->re_start,
 184                                     rs_node_free);
 185                                 r->re_start = end;
 186                                 error = pctrie_insert(&rs->rs_trie,
 187                                     &r->re_start, rs_node_alloc);
 188                                 /*
 189                                  * The insert above must succeed
 190                                  * because rs_node zone is marked
 191                                  * nofree and we freed one element
 192                                  * just before.
 193                                  */
 194                                 MPASS(error == 0);
 195                         } else {
 196                                 end = r->re_start;
 197                         }
 198                         continue;
 199                 }
 200
 201                 /*
 202                  * ------=========|===================|==========----
 203                  *       rs       s                   e         re
 204                  */
 205                 if (pred(rs->rs_data_ctx, r)) {
 206                         /*
 207                          * Split.  Can only happen once, and then if
 208                          * any allocation fails, the rangeset is kept
 209                          * intact.
 210                          */
 211                         rn = rs->rs_dup_data(rs->rs_data_ctx, r);
 212                         if (rn == NULL) {
 213                                 error = ENOMEM;
 214                                 break;
 215                         }
 216                         rn->re_start = end;
 217                         rn->re_end = r->re_end;
 218                         error = pctrie_insert(&rs->rs_trie, &rn->re_start,
 219                             rs_node_alloc);
 220                         if (error != 0) {
 221                                 rs->rs_free_data(rs->rs_data_ctx, rn);
 222                                 break;
 223                         }
 224                         r->re_end = start;
 225                 }
 226                 break;
 227         }
 228         rangeset_check(rs);
 229         return (error);
 230 }
 231
 232 static bool
 233 rangeset_true_pred(void *ctx __unused, void *r __unused)
 234 {
 235
 236         return (true);
 237 }
 238
 239 int
 240 rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end)
 241 {
 242
 243         return (rangeset_remove_pred(rs, start, end, rangeset_true_pred));
 244 }
 245
 246 void
 247 rangeset_remove_all(struct rangeset *rs)
 248 {
 249         struct rs_el *r;
 250         uint64_t *r1;
 251
 252         for (;;) {
 253                 r1 = pctrie_lookup_ge(&rs->rs_trie, 0);
 254                 if (r1 == NULL)
 255                         break;
 256                 r = __containerof(r1, struct rs_el, re_start);
 257                 pctrie_remove(&rs->rs_trie, r->re_start, rs_node_free);
 258                 rs->rs_free_data(rs->rs_data_ctx, r);
 259         }
 260 }
 261
 262 void *
 263 rangeset_lookup(struct rangeset *rs, uint64_t place)
 264 {
 265         struct rs_el *r;
 266         uint64_t *r1;
 267
 268         rangeset_check(rs);
 269         r1 = pctrie_lookup_le(&rs->rs_trie, place);
 270         if (r1 == NULL)
 271                 return (NULL);
 272         r = __containerof(r1, struct rs_el, re_start);
 273         if (r->re_end <= place)
 274                 return (NULL);
 275         return (r);
 276 }
 277
 278 int
 279 rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs)
 280 {
 281         struct rs_el *src_r, *dst_r;
 282         uint64_t cursor, *r1;
 283         int error;
 284
 285         MPASS(pctrie_is_empty(&dst_rs->rs_trie));
 286         rangeset_check(src_rs);
 287         MPASS(dst_rs->rs_dup_data == src_rs->rs_dup_data);
 288
 289         error = 0;
 290         for (cursor = 0;; cursor = src_r->re_start + 1) {
 291                 r1 = pctrie_lookup_ge(&src_rs->rs_trie, cursor);
 292                 if (r1 == NULL)
 293                         break;
 294                 src_r = __containerof(r1, struct rs_el, re_start);
 295                 dst_r = dst_rs->rs_dup_data(dst_rs->rs_data_ctx, src_r);
 296                 if (dst_r == NULL) {
 297                         error = ENOMEM;
 298                         break;
 299                 }
 300                 error = pctrie_insert(&dst_rs->rs_trie, &dst_r->re_start,
 301                     rs_node_alloc);
 302                 if (error != 0)
 303                         break;
 304         }
 305         if (error != 0)
 306                 rangeset_remove_all(dst_rs);
 307         return (error);
 308 }
 309
 310 #ifdef DIAGNOSTIC
 311 static void
 312 rangeset_check(struct rangeset *rs)
 313 {
 314         struct rs_el *r, *rp;
 315         uint64_t cursor, *r1;
 316
 317         for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) {
 318                 r1 = pctrie_lookup_ge(&rs->rs_trie, cursor);
 319                 if (r1 == NULL)
 320                         break;
 321                 r = __containerof(r1, struct rs_el, re_start);
 322                 KASSERT(r->re_start < r->re_end,
 323                     ("invalid interval rs %p elem %p (%#jx, %#jx)",
 324                     rs, r, (uintmax_t)r->re_start,  (uintmax_t)r->re_end));
 325                 if (rp != NULL) {
 326                         KASSERT(rp->re_end <= r->re_start,
 327                             ("non-ascending neighbors rs %p "
 328                             "prev elem %p (%#jx, %#jx) elem %p (%#jx, %#jx)",
 329                             rs, rp,  (uintmax_t)rp->re_start,
 330                             (uintmax_t)rp->re_end, r,  (uintmax_t)r->re_start,
 331                             (uintmax_t)r->re_end));
 332                 }
 333         }
 334 }
 335 #endif
 336
 337 #include "opt_ddb.h"
 338 #ifdef DDB
 339 #include <sys/kernel.h>
 340 #include <ddb/ddb.h>
 341
 342 DB_SHOW_COMMAND(rangeset, rangeset_show_fn)
 343 {
 344         struct rangeset *rs;
 345         struct rs_el *r;
 346         uint64_t cursor, *r1;
 347
 348         if (!have_addr) {
 349                 db_printf("show rangeset addr\n");
 350                 return;
 351         }
 352
 353         rs = (struct rangeset *)addr;
 354         db_printf("rangeset %p\n", rs);
 355         for (cursor = 0;; cursor = r->re_start + 1) {
 356                 r1 = pctrie_lookup_ge(&rs->rs_trie, cursor);
 357                 if (r1 == NULL)
 358                         break;
 359                 r = __containerof(r1, struct rs_el, re_start);
 360                 db_printf("  el %p start %#jx end %#jx\n",
 361                     r, r->re_start, r->re_end);
 362         }
 363 }
 364 #endif