bsd/hfs/rangelist.c

   1 /*
   2  * Copyright (c) 2001, 2006-2008 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                                 * If the list was empty 'prev' is undisturbed and 'overlap' == NULL;
 101                                 * if the search hit a non-overlapping entry PAST the start of the
 102                                 * new range, 'prev' points to ITS predecessor, and 'overlap' points
 103                                 * to that entry:
 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_AFTER(rangelist, overlap, range, rl_link);
 112                         } else {
 113                                 TAILQ_INSERT_HEAD(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         if (TAILQ_EMPTY(rangelist)) {
 264                 *overlap = NULL;
 265                 return RL_NOOVERLAP;
 266         };
 267
 268         return rl_scan_from(rangelist, start, end, overlap, TAILQ_FIRST(rangelist));
 269 }
 270
 271
 272
 273 /*
 274  * Walk the list of ranges for an entry to
 275  * find an overlapping range (if any).
 276  *
 277  * NOTE: this returns only the FIRST overlapping range.
 278  *           There may be more than one.
 279  */
 280 static enum rl_overlaptype
 281 rl_scan_from(struct rl_head *rangelist,
 282                          off_t start,
 283                          off_t end,
 284                          struct rl_entry **overlap,
 285                         struct rl_entry *range)
 286 {
 287         if (TAILQ_EMPTY(rangelist)) {
 288                 *overlap = NULL;
 289                 return RL_NOOVERLAP;
 290         };
 291
 292 #ifdef RL_DIAGNOSTIC
 293                 rl_verify(rangelist);
 294 #endif
 295
 296         *overlap = range;
 297
 298         while (1) {
 299                 /*
 300                  * OK, check for overlap
 301                  *
 302                  * Six cases:
 303                  *      0) no overlap (RL_NOOVERLAP)
 304                  *      1) overlap == range (RL_MATCHINGOVERLAP)
 305                  *      2) overlap contains range (RL_OVERLAPCONTAINSRANGE)
 306                  *      3) range contains overlap (RL_OVERLAPISCONTAINED)
 307                  *      4) overlap starts before range (RL_OVERLAPSTARTSBEFORE)
 308                  *      5) overlap ends after range (RL_OVERLAPENDSAFTER)
 309                  */
 310                 if (((range->rl_end != RL_INFINITY) && (start > range->rl_end)) ||
 311                         ((end != RL_INFINITY) && (range->rl_start > end))) {
 312                         /* Case 0 (RL_NOOVERLAP), at least with the current entry: */
 313                         if ((end != RL_INFINITY) && (range->rl_start > end)) {
 314                                 return RL_NOOVERLAP;
 315                         };
 316
 317                         range = TAILQ_NEXT(range, rl_link);
 318                         /* Check the other entries in the list: */
 319                         if (range == NULL) {
 320                                 return RL_NOOVERLAP;
 321                         }
 322
 323                         *overlap = range;
 324                         continue;
 325                 }
 326
 327                 if ((range->rl_start == start) && (range->rl_end == end)) {
 328                         /* Case 1 (RL_MATCHINGOVERLAP) */
 329                         return RL_MATCHINGOVERLAP;
 330                 }
 331
 332                 if ((range->rl_start <= start) &&
 333                         (end != RL_INFINITY) &&
 334                         ((range->rl_end >= end) || (range->rl_end == RL_INFINITY))) {
 335                                 /* Case 2 (RL_OVERLAPCONTAINSRANGE) */
 336                         return RL_OVERLAPCONTAINSRANGE;
 337                 }
 338
 339                 if ((start <= range->rl_start) &&
 340                         ((end == RL_INFINITY) ||
 341                          ((range->rl_end != RL_INFINITY) && (end >= range->rl_end)))) {
 342                         /* Case 3 (RL_OVERLAPISCONTAINED) */
 343                         return RL_OVERLAPISCONTAINED;
 344                 }
 345
 346                 if ((range->rl_start < start) &&
 347                         ((range->rl_end >= start) || (range->rl_end == RL_INFINITY))) {
 348                         /* Case 4 (RL_OVERLAPSTARTSBEFORE) */
 349                         return RL_OVERLAPSTARTSBEFORE;
 350                 }
 351
 352                 if ((range->rl_start > start) &&
 353                         (end != RL_INFINITY) &&
 354                         ((range->rl_end > end) || (range->rl_end == RL_INFINITY))) {
 355                         /* Case 5 (RL_OVERLAPENDSAFTER) */
 356                         return RL_OVERLAPENDSAFTER;
 357                 }
 358
 359                 /* Control should never reach here... */
 360 #ifdef RL_DIAGNOSTIC
 361                 panic("hfs: rl_scan_from: unhandled overlap condition?!");
 362 #endif
 363         }
 364
 365         return RL_NOOVERLAP;
 366 }
 367
 368
 369 static void
 370 rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range) {
 371         struct rl_entry *next_range;
 372
 373         while ((next_range = TAILQ_NEXT(range, rl_link))) {
 374                 if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;
 375
 376                 /* Expand this range to include the next range: */
 377                 range->rl_end = next_range->rl_end;
 378
 379                 /* Remove the now covered range from the list: */
 380                 TAILQ_REMOVE(rangelist, next_range, rl_link);
 381                 FREE(next_range, M_TEMP);
 382
 383 #ifdef RL_DIAGNOSTIC
 384                 rl_verify(rangelist);
 385 #endif
 386         };
 387 }
 388
 389
 390
 391 static void
 392 rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) {
 393     struct rl_entry *prev_range;
 394
 395                 while ((prev_range = TAILQ_PREV(range, rl_head, rl_link))) {
 396                         if (prev_range->rl_end < range->rl_start -1) {
 397 #ifdef RL_DIAGNOSTIC
 398                         rl_verify(rangelist);
 399 #endif
 400                 return;
 401         };
 402
 403         /* Expand this range to include the previous range: */
 404         range->rl_start = prev_range->rl_start;
 405
 406         /* Remove the now covered range from the list: */
 407         TAILQ_REMOVE(rangelist, prev_range, rl_link);
 408         FREE(prev_range, M_TEMP);
 409     };
 410 }
 411
 412
 413
 414 static void
 415 rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range)
 416 {
 417     rl_collapse_forwards(rangelist, range);
 418     rl_collapse_backwards(rangelist, range);
 419 }
 420
 421 #else /* not HFS - temp workaround until 4277828 is fixed */
 422 /* stubs for exported routines that aren't present when we build kernel without HFS */
 423
 424 #include <sys/types.h>
 425
 426 void rl_add(off_t start, off_t end, void *rangelist);
 427 void rl_init(void *rangelist);
 428 void rl_remove(off_t start, off_t end, void *rangelist);
 429 int rl_scan(void *rangelist, off_t start, off_t end, void **overlap);
 430
 431 void rl_add(__unused off_t start, __unused off_t end, __unused void *rangelist)
 432 {
 433         return;
 434 }
 435
 436 void rl_init(__unused void *rangelist)
 437 {
 438         return;
 439 }
 440
 441 void rl_remove(__unused off_t start, __unused off_t end, __unused void *rangelist)
 442 {
 443         return;
 444 }
 445
 446 int rl_scan(__unused void *rangelist, __unused off_t start, __unused off_t end, __unused void **overlap)
 447 {
 448         return(0);
 449 }
 450
 451 #endif /* HFS */