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