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 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 * 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 */ 167void 168rl_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 255enum rl_overlaptype 256rl_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 */ 278static enum rl_overlaptype 279rl_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 364static void 365rl_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 386static void 387rl_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 409static void 410rl_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 416void 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 429void rl_add(off_t start, off_t end, void *rangelist); 430void rl_init(void *rangelist); 431void rl_remove(off_t start, off_t end, void *rangelist); 432int rl_scan(void *rangelist, off_t start, off_t end, void **overlap); 433 434void rl_add(__unused off_t start, __unused off_t end, __unused void *rangelist) 435{ 436 return; 437} 438 439void rl_init(__unused void *rangelist) 440{ 441 return; 442} 443 444void rl_remove(__unused off_t start, __unused off_t end, __unused void *rangelist) 445{ 446 return; 447} 448 449int rl_scan(__unused void *rangelist, __unused off_t start, __unused off_t end, __unused void **overlap) 450{ 451 return(0); 452} 453 454void rl_remove_all(struct rl_head *rangelist) 455{ 456} 457 458#endif /* HFS */ 459