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