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

Cache object: eaa513c685a26f917c486fec8f709901


[ 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.