core/rangelist.c

   1 /*
   2  * Copyright (c) 2001-2015 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 #include <sys/param.h>
  30 #include <mach/boolean.h>
  31 #include <sys/time.h>
  32 #include <sys/malloc.h>
  33
  34 #if !RANGELIST_TEST
  35 #include <kern/debug.h>
  36 #include "hfs.h"
  37 #endif
  38
  39 #include "rangelist.h"
  40
  41 static enum rl_overlaptype rl_scan_from(struct rl_head *rangelist, off_t start, off_t end, struct rl_entry **overlap, struct rl_entry *range);
  42 static void rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range);
  43 static void rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range);
  44 static void rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range);
  45
  46
  47 #ifdef RL_DIAGNOSTIC
  48 static void
  49 rl_verify(struct rl_head *rangelist) {
  50         struct rl_entry *entry;
  51         struct rl_entry *next;
  52         off_t limit = 0;
  53
  54         TAILQ_FOREACH_SAFE(rangelist, entry, rl_link, next) {
  55                 if ((limit > 0) && (entry->rl_start <= limit)) panic("hfs: rl_verify: bad entry start?!");
  56                 if (entry->rl_end < entry->rl_start) panic("hfs: rl_verify: bad entry end?!");
  57                 limit = entry->rl_end;
  58         };
  59 }
  60 #endif
  61
  62
  63
  64 /*
  65  * Initialize a range list head
  66  */
  67 void
  68 rl_init(struct rl_head *rangelist)
  69 {
  70     TAILQ_INIT(rangelist);
  71 }
  72
  73 /*
  74  * Add a range to the list
  75  */
  76 void
  77 rl_add(off_t start, off_t end, struct rl_head *rangelist)
  78 {
  79         struct rl_entry *range;
  80         struct rl_entry *overlap;
  81         enum rl_overlaptype ovcase;
  82
  83 #ifdef RL_DIAGNOSTIC
  84         if (end < start) panic("hfs: rl_add: end < start?!");
  85 #endif
  86
  87         ovcase = rl_scan(rangelist, start, end, &overlap);
  88
  89         /*
  90          * Six cases:
  91          *      0) no overlap
  92          *      1) overlap == range
  93          *      2) overlap contains range
  94          *      3) range contains overlap
  95          *      4) overlap starts before range
  96          *      5) overlap ends after range
  97          */
  98         switch (ovcase) {
  99                 case RL_NOOVERLAP: /* 0: no overlap */
 100                         /*
 101                          * overlap points to the entry we should insert before, or
 102                          * if NULL, we should insert at the end.
 103                          */
 104                         range = hfs_malloc(sizeof(*range));
 105                         range->rl_start = start;
 106                         range->rl_end = end;
 107
 108                         /* Link in the new range: */
 109                         if (overlap) {
 110                                 TAILQ_INSERT_BEFORE(overlap, range, rl_link);
 111                         } else {
 112                                 TAILQ_INSERT_TAIL(rangelist, range, rl_link);
 113                         }
 114
 115                         /* Check to see if any ranges can be combined (possibly including the immediately
 116                            preceding range entry)
 117                          */
 118                         rl_collapse_neighbors(rangelist, range);
 119                         break;
 120
 121                 case RL_MATCHINGOVERLAP: /* 1: overlap == range */
 122                 case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range */
 123                         break;
 124
 125                 case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
 126                         /*
 127                          * Replace the overlap with the new, larger range:
 128                          */
 129                         overlap->rl_start = start;
 130                         overlap->rl_end = end;
 131                         rl_collapse_neighbors(rangelist, overlap);
 132                         break;
 133
 134                 case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
 135                         /*
 136                          * Expand the overlap area to cover the new range:
 137                          */
 138                         overlap->rl_end = end;
 139                         rl_collapse_forwards(rangelist, overlap);
 140                         break;
 141
 142                 case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
 143                         /*
 144                          * Expand the overlap area to cover the new range:
 145                          */
 146                         overlap->rl_start = start;
 147                         rl_collapse_backwards(rangelist, overlap);
 148                         break;
 149         }
 150
 151 #ifdef RL_DIAGNOSTIC
 152         rl_verify(rangelist);
 153 #endif
 154 }
 155
 156
 157
 158 /*
 159  * Remove a range from a range list.
 160  *
 161  * Generally, find the range (or an overlap to that range)
 162  * and remove it (or shrink it), then wakeup anyone we can.
 163  */
 164 void
 165 rl_remove(off_t start, off_t end, struct rl_head *rangelist)
 166 {
 167         struct rl_entry *range, *next_range, *overlap, *splitrange;
 168         int ovcase;
 169
 170 #ifdef RL_DIAGNOSTIC
 171         if (end < start) panic("hfs: rl_remove: end < start?!");
 172 #endif
 173
 174         if (TAILQ_EMPTY(rangelist)) {
 175                 return;
 176         };
 177
 178         range = TAILQ_FIRST(rangelist);
 179         while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range))) {
 180                 switch (ovcase) {
 181
 182                 case RL_MATCHINGOVERLAP: /* 1: overlap == range */
 183                         TAILQ_REMOVE(rangelist, overlap, rl_link);
 184                         hfs_free(overlap, sizeof(*overlap));
 185                         break;
 186
 187                 case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range: split it */
 188                         if (overlap->rl_start == start) {
 189                                 overlap->rl_start = end + 1;
 190                                 break;
 191                         };
 192
 193                         if (overlap->rl_end == end) {
 194                                 overlap->rl_end = start - 1;
 195                                 break;
 196                         };
 197
 198                         /*
 199                         * Make a new range consisting of the last part of the encompassing range
 200                         */
 201                         splitrange = hfs_malloc(sizeof *splitrange);
 202                         splitrange->rl_start = end + 1;
 203                         splitrange->rl_end = overlap->rl_end;
 204                         overlap->rl_end = start - 1;
 205
 206                         /*
 207                         * Now link the new entry into the range list after the range from which it was split:
 208                         */
 209                         TAILQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
 210                         break;
 211
 212                 case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
 213                         /* Check before discarding overlap entry */
 214                         next_range = TAILQ_NEXT(overlap, rl_link);
 215                         TAILQ_REMOVE(rangelist, overlap, rl_link);
 216                         hfs_free(overlap, sizeof(*overlap));
 217                         if (next_range) {
 218                                 range = next_range;
 219                                 continue;
 220                         };
 221                         break;
 222
 223                 case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
 224                         overlap->rl_end = start - 1;
 225                         range = TAILQ_NEXT(overlap, rl_link);
 226                         if (range) {
 227                                 continue;
 228                         }
 229                         break;
 230
 231                 case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
 232                         overlap->rl_start = (end == RL_INFINITY ? RL_INFINITY : end + 1);
 233                         break;
 234                 }
 235                 break;
 236         }
 237
 238 #ifdef RL_DIAGNOSTIC
 239         rl_verify(rangelist);
 240 #endif
 241 }
 242
 243
 244
 245 /*
 246  * Scan a range list for an entry in a specified range (if any):
 247  *
 248  * NOTE: this returns only the FIRST overlapping range.
 249  *           There may be more than one.
 250  */
 251
 252 enum rl_overlaptype
 253 rl_scan(struct rl_head *rangelist,
 254                 off_t start,
 255                 off_t end,
 256                 struct rl_entry **overlap) {
 257
 258         return rl_scan_from(rangelist, start, end, overlap, TAILQ_FIRST(rangelist));
 259 }
 260
 261 enum rl_overlaptype
 262 rl_overlap(const struct rl_entry *range, off_t start, off_t end)
 263 {
 264         /*
 265          * OK, check for overlap
 266          *
 267          * Six cases:
 268          *      0) no overlap (RL_NOOVERLAP)
 269          *      1) overlap == range (RL_MATCHINGOVERLAP)
 270          *      2) overlap contains range (RL_OVERLAPCONTAINSRANGE)
 271          *      3) range contains overlap (RL_OVERLAPISCONTAINED)
 272          *      4) overlap starts before range (RL_OVERLAPSTARTSBEFORE)
 273          *      5) overlap ends after range (RL_OVERLAPENDSAFTER)
 274          */
 275         if (start > range->rl_end || range->rl_start > end) {
 276                 /* Case 0 (RL_NOOVERLAP) */
 277                 return RL_NOOVERLAP;
 278         }
 279
 280         if (range->rl_start == start && range->rl_end == end) {
 281                 /* Case 1 (RL_MATCHINGOVERLAP) */
 282                 return RL_MATCHINGOVERLAP;
 283         }
 284
 285         if (range->rl_start <= start && range->rl_end >= end) {
 286                 /* Case 2 (RL_OVERLAPCONTAINSRANGE) */
 287                 return RL_OVERLAPCONTAINSRANGE;
 288         }
 289
 290         if (start <= range->rl_start && end >= range->rl_end) {
 291                 /* Case 3 (RL_OVERLAPISCONTAINED) */
 292                 return RL_OVERLAPISCONTAINED;
 293         }
 294
 295         if (range->rl_start < start && range->rl_end < end) {
 296                 /* Case 4 (RL_OVERLAPSTARTSBEFORE) */
 297                 return RL_OVERLAPSTARTSBEFORE;
 298         }
 299
 300         /* Case 5 (RL_OVERLAPENDSAFTER) */
 301         // range->rl_start > start && range->rl_end > end
 302         return RL_OVERLAPENDSAFTER;
 303 }
 304
 305 /*
 306  * Walk the list of ranges for an entry to
 307  * find an overlapping range (if any).
 308  *
 309  * NOTE: this returns only the FIRST overlapping range.
 310  *           There may be more than one.
 311  */
 312 static enum rl_overlaptype
 313 rl_scan_from(struct rl_head *rangelist __unused,
 314                          off_t start,
 315                          off_t end,
 316                          struct rl_entry **overlap,
 317                          struct rl_entry *range)
 318 {
 319 #ifdef RL_DIAGNOSTIC
 320         rl_verify(rangelist);
 321 #endif
 322
 323         while (range) {
 324                 enum rl_overlaptype ot = rl_overlap(range, start, end);
 325
 326                 if (ot != RL_NOOVERLAP || range->rl_start > end) {
 327                         *overlap = range;
 328                         return ot;
 329                 }
 330
 331                 range = TAILQ_NEXT(range, rl_link);
 332         }
 333
 334         *overlap = NULL;
 335         return RL_NOOVERLAP;
 336 }
 337
 338
 339 static void
 340 rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range) {
 341         struct rl_entry *next_range;
 342
 343         while ((next_range = TAILQ_NEXT(range, rl_link))) {
 344                 if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;
 345
 346                 /* Expand this range to include the next range: */
 347                 range->rl_end = next_range->rl_end;
 348
 349                 /* Remove the now covered range from the list: */
 350                 TAILQ_REMOVE(rangelist, next_range, rl_link);
 351                 hfs_free(next_range, sizeof(*next_range));
 352
 353 #ifdef RL_DIAGNOSTIC
 354                 rl_verify(rangelist);
 355 #endif
 356         };
 357 }
 358
 359
 360
 361 static void
 362 rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) {
 363     struct rl_entry *prev_range;
 364
 365                 while ((prev_range = TAILQ_PREV(range, rl_head, rl_link))) {
 366                         if (prev_range->rl_end < range->rl_start -1) {
 367 #ifdef RL_DIAGNOSTIC
 368                         rl_verify(rangelist);
 369 #endif
 370                 return;
 371         };
 372
 373         /* Expand this range to include the previous range: */
 374         range->rl_start = prev_range->rl_start;
 375
 376         /* Remove the now covered range from the list: */
 377         TAILQ_REMOVE(rangelist, prev_range, rl_link);
 378         hfs_free(prev_range, sizeof(*prev_range));
 379     };
 380 }
 381
 382
 383
 384 static void
 385 rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range)
 386 {
 387     rl_collapse_forwards(rangelist, range);
 388     rl_collapse_backwards(rangelist, range);
 389 }
 390
 391 void rl_remove_all(struct rl_head *rangelist)
 392 {
 393         struct rl_entry *r, *nextr;
 394         TAILQ_FOREACH_SAFE(r, rangelist, rl_link, nextr)
 395                 hfs_free(r, sizeof(*r));
 396         TAILQ_INIT(rangelist);
 397 }
 398
 399 /*
 400  * In the case where b is contained by a, we return the the largest part
 401  * remaining.  The result is stored in a.
 402  */
 403 void rl_subtract(struct rl_entry *a, const struct rl_entry *b)
 404 {
 405         switch (rl_overlap(b, a->rl_start, a->rl_end)) {
 406                 case RL_MATCHINGOVERLAP:
 407                 case RL_OVERLAPCONTAINSRANGE:
 408                         a->rl_end = a->rl_start - 1;
 409                         break;
 410                 case RL_OVERLAPISCONTAINED:
 411                         // Keep the bigger part
 412                         if (b->rl_start - a->rl_start >= a->rl_end - b->rl_end) {
 413                                 // Keep left
 414                                 a->rl_end = b->rl_start - 1;
 415                         } else {
 416                                 // Keep right
 417                                 a->rl_start = b->rl_end + 1;
 418                         }
 419                         break;
 420                 case RL_OVERLAPSTARTSBEFORE:
 421                         a->rl_start = b->rl_end + 1;
 422                         break;
 423                 case RL_OVERLAPENDSAFTER:
 424                         a->rl_end = b->rl_start - 1;
 425                         break;
 426                 case RL_NOOVERLAP:
 427                         break;
 428         }
 429 }