The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_rangeset.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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

Cache object: 601fc0e385c207ce0143a756daf893f6


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.