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 38static enum rl_overlaptype rl_scan_from(struct rl_head *rangelist, off_t start, off_t end, struct rl_entry **overlap, struct rl_entry *range); 39static void rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range); 40static void rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range); 41static void rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range); 42 43 44#ifdef RL_DIAGNOSTIC 45static void 46rl_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 */ 64void 65rl_init(struct rl_head *rangelist) 66{ 67 TAILQ_INIT(rangelist); 68} 69 70 71 72/* 73 * Add a range to the list 74 */ 75void 76rl_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 */ 169void 170rl_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 257enum rl_overlaptype 258rl_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 */ 280static enum rl_overlaptype 281rl_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 369static void 370rl_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 391static void 392rl_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 414static void 415rl_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 426void rl_add(off_t start, off_t end, void *rangelist); 427void rl_init(void *rangelist); 428void rl_remove(off_t start, off_t end, void *rangelist); 429int rl_scan(void *rangelist, off_t start, off_t end, void **overlap); 430 431void rl_add(__unused off_t start, __unused off_t end, __unused void *rangelist) 432{ 433 return; 434} 435 436void rl_init(__unused void *rangelist) 437{ 438 return; 439} 440 441void rl_remove(__unused off_t start, __unused off_t end, __unused void *rangelist) 442{ 443 return; 444} 445 446int 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 */ 452