bsd/hfs/rangelist.c

   1 /*
   2  * Copyright (c) 2001-2014 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 #if HFS
  30
  31 #include <sys/param.h>
  32 #include <mach/boolean.h>
  33 #include <sys/time.h>
  34 #include <sys/malloc.h>
  35
  36 #if !RANGELIST_TEST
  37 #include <kern/debug.h>
  38 #endif
  39
  40 #include "rangelist.h"
  41
  42 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);
  43 static void rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range);
  44 static void rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range);
  45 static void rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range);
  46
  47
  48 #ifdef RL_DIAGNOSTIC
  49 static void
  50 rl_verify(struct rl_head *rangelist) {
  51         struct rl_entry *entry;
  52         struct rl_entry *next;
  53         off_t limit = 0;
  54
  55         TAILQ_FOREACH_SAFE(rangelist, entry, rl_link, next) {
  56                 if ((limit > 0) && (entry->rl_start <= limit)) panic("hfs: rl_verify: bad entry start?!");
  57                 if (entry->rl_end < entry->rl_start) panic("hfs: rl_verify: bad entry end?!");
  58                 limit = entry->rl_end;
  59         };
  60 }
  61 #endif
  62
  63
  64
  65 /*
  66  * Initialize a range list head
  67  */
  68 void
  69 rl_init(struct rl_head *rangelist)
  70 {
  71     TAILQ_INIT(rangelist);
  72 }
  73
  74 /*
  75  * Add a range to the list
  76  */
  77 void
  78 rl_add(off_t start, off_t end, struct rl_head *rangelist)
  79 {
  80         struct rl_entry *range;
  81         struct rl_entry *overlap;
  82         enum rl_overlaptype ovcase;
  83
  84 #ifdef RL_DIAGNOSTIC
  85         if (end < start) panic("hfs: rl_add: end < start?!");
  86 #endif
  87
  88         ovcase = rl_scan(rangelist, start, end, &overlap);
  89
  90         /*
  91          * Six cases:
  92          *      0) no overlap
  93          *      1) overlap == range
  94          *      2) overlap contains range
  95          *      3) range contains overlap
  96          *      4) overlap starts before range
  97          *      5) overlap ends after range
  98          */
  99         switch (ovcase) {
 100                 case RL_NOOVERLAP: /* 0: no overlap */
 101                         /*
 102                          * overlap points to the entry we should insert before, or
 103                          * if NULL, we should insert at the end.
 104                          */
 105                         MALLOC(range, struct rl_entry *, sizeof(*range), M_TEMP, M_WAITOK);
 106                         range->rl_start = start;
 107                         range->rl_end = end;
 108
 109                         /* Link in the new range: */
 110                         if (overlap) {
 111                                 TAILQ_INSERT_BEFORE(overlap, range, rl_link);
 112                         } else {
 113                                 TAILQ_INSERT_TAIL(rangelist, range, rl_link);
 114                         }
 115
 116                         /* Check to see if any ranges can be combined (possibly including the immediately
 117                            preceding range entry)
 118                          */
 119                         rl_collapse_neighbors(rangelist, range);
 120                         break;
 121
 122                 case RL_MATCHINGOVERLAP: /* 1: overlap == range */
 123                 case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range */
 124                         range = overlap; /* for debug output below */
 125                         break;
 126
 127                 case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
 128                         /*
 129                          * Replace the overlap with the new, larger range:
 130                          */
 131                         overlap->rl_start = start;
 132                         overlap->rl_end = end;
 133                         rl_collapse_neighbors(rangelist, overlap);
 134                         range = overlap; /* for debug output below */
 135                         break;
 136
 137                 case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
 138                         /*
 139                          * Expand the overlap area to cover the new range:
 140                          */
 141                         overlap->rl_end = end;
 142                         rl_collapse_forwards(rangelist, overlap);
 143                         range = overlap; /* for debug output below */
 144                         break;
 145
 146                 case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
 147                         /*
 148                          * Expand the overlap area to cover the new range:
 149                          */
 150                         overlap->rl_start = start;
 151                         rl_collapse_backwards(rangelist, overlap);
 152                         range = overlap; /* for debug output below */
 153                         break;
 154         }
 155
 156 #ifdef RL_DIAGNOSTIC
 157         rl_verify(rangelist);
 158 #endif
 159 }
 160
 161
 162
 163 /*
 164  * Remove a range from a range list.
 165  *
 166  * Generally, find the range (or an overlap to that range)
 167  * and remove it (or shrink it), then wakeup anyone we can.
 168  */
 169 void
 170 rl_remove(off_t start, off_t end, struct rl_head *rangelist)
 171 {
 172         struct rl_entry *range, *next_range, *overlap, *splitrange;
 173         int ovcase;
 174
 175 #ifdef RL_DIAGNOSTIC
 176         if (end < start) panic("hfs: rl_remove: end < start?!");
 177 #endif
 178
 179         if (TAILQ_EMPTY(rangelist)) {
 180                 return;
 181         };
 182
 183         range = TAILQ_FIRST(rangelist);
 184         while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range))) {
 185                 switch (ovcase) {
 186
 187                 case RL_MATCHINGOVERLAP: /* 1: overlap == range */
 188                         TAILQ_REMOVE(rangelist, overlap, rl_link);
 189                         FREE(overlap, M_TEMP);
 190                         break;
 191
 192                 case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range: split it */
 193                         if (overlap->rl_start == start) {
 194                                 overlap->rl_start = end + 1;
 195                                 break;
 196                         };
 197
 198                         if (overlap->rl_end == end) {
 199                                 overlap->rl_end = start - 1;
 200                                 break;
 201                         };
 202
 203                         /*
 204                         * Make a new range consisting of the last part of the encompassing range
 205                         */
 206                         MALLOC(splitrange, struct rl_entry *, sizeof *splitrange, M_TEMP, M_WAITOK);
 207                         splitrange->rl_start = end + 1;
 208                         splitrange->rl_end = overlap->rl_end;
 209                         overlap->rl_end = start - 1;
 210
 211                         /*
 212                         * Now link the new entry into the range list after the range from which it was split:
 213                         */
 214                         TAILQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
 215                         break;
 216
 217                 case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
 218                         /* Check before discarding overlap entry */
 219                         next_range = TAILQ_NEXT(overlap, rl_link);
 220                         TAILQ_REMOVE(rangelist, overlap, rl_link);
 221                         FREE(overlap, M_TEMP);
 222                         if (next_range) {
 223                                 range = next_range;
 224                                 continue;
 225                         };
 226                         break;
 227
 228                 case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
 229                         overlap->rl_end = start - 1;
 230                         range = TAILQ_NEXT(overlap, rl_link);
 231                         if (range) {
 232                                 continue;
 233                         }
 234                         break;
 235
 236                 case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
 237                         overlap->rl_start = (end == RL_INFINITY ? RL_INFINITY : end + 1);
 238                         break;
 239                 }
 240                 break;
 241         }
 242
 243 #ifdef RL_DIAGNOSTIC
 244         rl_verify(rangelist);
 245 #endif
 246 }
 247
 248
 249
 250 /*
 251  * Scan a range list for an entry in a specified range (if any):
 252  *
 253  * NOTE: this returns only the FIRST overlapping range.
 254  *           There may be more than one.
 255  */
 256
 257 enum rl_overlaptype
 258 rl_scan(struct rl_head *rangelist,
 259                 off_t start,
 260                 off_t end,
 261                 struct rl_entry **overlap) {
 262
 263         return rl_scan_from(rangelist, start, end, overlap, TAILQ_FIRST(rangelist));
 264 }
 265
 266 enum rl_overlaptype
 267 rl_overlap(const struct rl_entry *range, off_t start, off_t end)
 268 {
 269         /*
 270          * OK, check for overlap
 271          *
 272          * Six cases:
 273          *      0) no overlap (RL_NOOVERLAP)
 274          *      1) overlap == range (RL_MATCHINGOVERLAP)
 275          *      2) overlap contains range (RL_OVERLAPCONTAINSRANGE)
 276          *      3) range contains overlap (RL_OVERLAPISCONTAINED)
 277          *      4) overlap starts before range (RL_OVERLAPSTARTSBEFORE)
 278          *      5) overlap ends after range (RL_OVERLAPENDSAFTER)
 279          */
 280         if (start > range->rl_end || range->rl_start > end) {
 281                 /* Case 0 (RL_NOOVERLAP) */
 282                 return RL_NOOVERLAP;
 283         }
 284
 285         if (range->rl_start == start && range->rl_end == end) {
 286                 /* Case 1 (RL_MATCHINGOVERLAP) */
 287                 return RL_MATCHINGOVERLAP;
 288         }
 289
 290         if (range->rl_start <= start && range->rl_end >= end) {
 291                 /* Case 2 (RL_OVERLAPCONTAINSRANGE) */
 292                 return RL_OVERLAPCONTAINSRANGE;
 293         }
 294
 295         if (start <= range->rl_start && end >= range->rl_end) {
 296                 /* Case 3 (RL_OVERLAPISCONTAINED) */
 297                 return RL_OVERLAPISCONTAINED;
 298         }
 299
 300         if (range->rl_start < start && range->rl_end < end) {
 301                 /* Case 4 (RL_OVERLAPSTARTSBEFORE) */
 302                 return RL_OVERLAPSTARTSBEFORE;
 303         }
 304
 305         /* Case 5 (RL_OVERLAPENDSAFTER) */
 306         // range->rl_start > start && range->rl_end > end
 307         return RL_OVERLAPENDSAFTER;
 308 }
 309
 310 /*
 311  * Walk the list of ranges for an entry to
 312  * find an overlapping range (if any).
 313  *
 314  * NOTE: this returns only the FIRST overlapping range.
 315  *           There may be more than one.
 316  */
 317 static enum rl_overlaptype
 318 rl_scan_from(struct rl_head *rangelist __unused,
 319                          off_t start,
 320                          off_t end,
 321                          struct rl_entry **overlap,
 322                          struct rl_entry *range)
 323 {
 324 #ifdef RL_DIAGNOSTIC
 325         rl_verify(rangelist);
 326 #endif
 327
 328         while (range) {
 329                 enum rl_overlaptype ot = rl_overlap(range, start, end);
 330
 331                 if (ot != RL_NOOVERLAP || range->rl_start > end) {
 332                         *overlap = range;
 333                         return ot;
 334                 }
 335
 336                 range = TAILQ_NEXT(range, rl_link);
 337         }
 338
 339         *overlap = NULL;
 340         return RL_NOOVERLAP;
 341 }
 342
 343
 344 static void
 345 rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range) {
 346         struct rl_entry *next_range;
 347
 348         while ((next_range = TAILQ_NEXT(range, rl_link))) {
 349                 if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;
 350
 351                 /* Expand this range to include the next range: */
 352                 range->rl_end = next_range->rl_end;
 353
 354                 /* Remove the now covered range from the list: */
 355                 TAILQ_REMOVE(rangelist, next_range, rl_link);
 356                 FREE(next_range, M_TEMP);
 357
 358 #ifdef RL_DIAGNOSTIC
 359                 rl_verify(rangelist);
 360 #endif
 361         };
 362 }
 363
 364
 365
 366 static void
 367 rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) {
 368     struct rl_entry *prev_range;
 369
 370                 while ((prev_range = TAILQ_PREV(range, rl_head, rl_link))) {
 371                         if (prev_range->rl_end < range->rl_start -1) {
 372 #ifdef RL_DIAGNOSTIC
 373                         rl_verify(rangelist);
 374 #endif
 375                 return;
 376         };
 377
 378         /* Expand this range to include the previous range: */
 379         range->rl_start = prev_range->rl_start;
 380
 381         /* Remove the now covered range from the list: */
 382         TAILQ_REMOVE(rangelist, prev_range, rl_link);
 383         FREE(prev_range, M_TEMP);
 384     };
 385 }
 386
 387
 388
 389 static void
 390 rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range)
 391 {
 392     rl_collapse_forwards(rangelist, range);
 393     rl_collapse_backwards(rangelist, range);
 394 }
 395
 396 void rl_remove_all(struct rl_head *rangelist)
 397 {
 398         struct rl_entry *r, *nextr;
 399         TAILQ_FOREACH_SAFE(r, rangelist, rl_link, nextr)
 400                 FREE(r, M_TEMP);
 401         TAILQ_INIT(rangelist);
 402 }
 403
 404 /*
 405  * In the case where b is contained by a, we return the the largest part
 406  * remaining.  The result is stored in a.
 407  */
 408 void rl_subtract(struct rl_entry *a, const struct rl_entry *b)
 409 {
 410         switch (rl_overlap(b, a->rl_start, a->rl_end)) {
 411                 case RL_MATCHINGOVERLAP:
 412                 case RL_OVERLAPCONTAINSRANGE:
 413                         a->rl_end = a->rl_start - 1;
 414                         break;
 415                 case RL_OVERLAPISCONTAINED:
 416                         // Keep the bigger part
 417                         if (b->rl_start - a->rl_start >= a->rl_end - b->rl_end) {
 418                                 // Keep left
 419                                 a->rl_end = b->rl_start - 1;
 420                         } else {
 421                                 // Keep right
 422                                 a->rl_start = b->rl_end + 1;
 423                         }
 424                         break;
 425                 case RL_OVERLAPSTARTSBEFORE:
 426                         a->rl_start = b->rl_end + 1;
 427                         break;
 428                 case RL_OVERLAPENDSAFTER:
 429                         a->rl_end = b->rl_start - 1;
 430                         break;
 431                 case RL_NOOVERLAP:
 432                         break;
 433         }
 434 }
 435
 436 #else /* not HFS - temp workaround until 4277828 is fixed */
 437 /* stubs for exported routines that aren't present when we build kernel without HFS */
 438
 439 #include <sys/types.h>
 440
 441 void rl_add(off_t start, off_t end, void *rangelist);
 442 void rl_init(void *rangelist);
 443 void rl_remove(off_t start, off_t end, void *rangelist);
 444 int rl_scan(void *rangelist, off_t start, off_t end, void **overlap);
 445
 446 void rl_add(__unused off_t start, __unused off_t end, __unused void *rangelist)
 447 {
 448         return;
 449 }
 450
 451 void rl_init(__unused void *rangelist)
 452 {
 453         return;
 454 }
 455
 456 void rl_remove(__unused off_t start, __unused off_t end, __unused void *rangelist)
 457 {
 458         return;
 459 }
 460
 461 int rl_scan(__unused void *rangelist, __unused off_t start, __unused off_t end, __unused void **overlap)
 462 {
 463         return(0);
 464 }
 465
 466 void rl_remove_all(struct rl_head *rangelist)
 467 {
 468 }
 469
 470 #endif /* HFS */