X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/ff6e181ae92fc6f1e89841290f461d1f2f9badd9..7e41aa883dd258f888d0470250eead40a53ef1f5:/bsd/hfs/rangelist.c diff --git a/bsd/hfs/rangelist.c b/bsd/hfs/rangelist.c index a69f16f0d..81b384c48 100644 --- a/bsd/hfs/rangelist.c +++ b/bsd/hfs/rangelist.c @@ -1,14 +1,19 @@ /* - * Copyright (c) 2001 Apple Computer, Inc. All rights reserved. + * Copyright (c) 2001-2014 Apple Inc. All rights reserved. * - * @APPLE_LICENSE_HEADER_START@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ * * This file contains Original Code and/or Modifications of Original Code * as defined in and that are subject to the Apple Public Source License * Version 2.0 (the 'License'). You may not use this file except in - * compliance with the License. Please obtain a copy of the License at - * http://www.opensource.apple.com/apsl/ and read it before using this - * file. + * compliance with the License. The rights granted to you under the License + * may not be used to create, or enable the creation or redistribution of, + * unlawful or unlicensed copies of an Apple operating system, or to + * circumvent, violate, or enable the circumvention or violation of, any + * terms of an Apple operating system software license agreement. + * + * Please obtain a copy of the License at + * http://www.opensource.apple.com/apsl/ and read it before using this file. * * The Original Code and all software distributed under the License are * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER @@ -18,14 +23,20 @@ * Please see the License for the specific language governing rights and * limitations under the License. * - * @APPLE_LICENSE_HEADER_END@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ */ +#if HFS + #include #include #include #include +#if !RANGELIST_TEST +#include +#endif + #include "rangelist.h" 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); @@ -38,17 +49,13 @@ static void rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *ra static void rl_verify(struct rl_head *rangelist) { struct rl_entry *entry; + struct rl_entry *next; off_t limit = 0; - if (CIRCLEQ_EMPTY(rangelist)) return; - entry = CIRCLEQ_FIRST(rangelist); - while (1) { - if (CIRCLEQ_NEXT(entry, rl_link) == entry) panic("rl_verify: circular rangelist?!"); - if ((limit > 0) && (entry->rl_start <= limit)) panic("rl_verify: bad entry start?!"); - if (entry->rl_end < entry->rl_start) panic("rl_verify: bad entry end?!"); + TAILQ_FOREACH_SAFE(rangelist, entry, rl_link, next) { + if ((limit > 0) && (entry->rl_start <= limit)) panic("hfs: rl_verify: bad entry start?!"); + if (entry->rl_end < entry->rl_start) panic("hfs: rl_verify: bad entry end?!"); limit = entry->rl_end; - if (entry == CIRCLEQ_LAST(rangelist)) return; - entry = CIRCLEQ_NEXT(entry, rl_link); }; } #endif @@ -61,11 +68,9 @@ rl_verify(struct rl_head *rangelist) { void rl_init(struct rl_head *rangelist) { - CIRCLEQ_INIT(rangelist); + TAILQ_INIT(rangelist); } - - /* * Add a range to the list */ @@ -77,7 +82,7 @@ rl_add(off_t start, off_t end, struct rl_head *rangelist) enum rl_overlaptype ovcase; #ifdef RL_DIAGNOSTIC - if (end < start) panic("rl_add: end < start?!"); + if (end < start) panic("hfs: rl_add: end < start?!"); #endif ovcase = rl_scan(rangelist, start, end, &overlap); @@ -94,20 +99,18 @@ rl_add(off_t start, off_t end, struct rl_head *rangelist) switch (ovcase) { case RL_NOOVERLAP: /* 0: no overlap */ /* - * If the list was empty 'prev' is undisturbed and 'overlap' == NULL; - * if the search hit a non-overlapping entry PAST the start of the - * new range, 'prev' points to ITS predecessor, and 'overlap' points - * to that entry: - */ + * overlap points to the entry we should insert before, or + * if NULL, we should insert at the end. + */ MALLOC(range, struct rl_entry *, sizeof(*range), M_TEMP, M_WAITOK); range->rl_start = start; range->rl_end = end; /* Link in the new range: */ if (overlap) { - CIRCLEQ_INSERT_AFTER(rangelist, overlap, range, rl_link); + TAILQ_INSERT_BEFORE(overlap, range, rl_link); } else { - CIRCLEQ_INSERT_HEAD(rangelist, range, rl_link); + TAILQ_INSERT_TAIL(rangelist, range, rl_link); } /* Check to see if any ranges can be combined (possibly including the immediately @@ -167,22 +170,22 @@ void rl_remove(off_t start, off_t end, struct rl_head *rangelist) { struct rl_entry *range, *next_range, *overlap, *splitrange; - int ovcase, moretotest; + int ovcase; #ifdef RL_DIAGNOSTIC - if (end < start) panic("rl_remove: end < start?!"); + if (end < start) panic("hfs: rl_remove: end < start?!"); #endif - if (CIRCLEQ_EMPTY(rangelist)) { + if (TAILQ_EMPTY(rangelist)) { return; }; - - range = CIRCLEQ_FIRST(rangelist); + + range = TAILQ_FIRST(rangelist); while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range))) { switch (ovcase) { case RL_MATCHINGOVERLAP: /* 1: overlap == range */ - CIRCLEQ_REMOVE(rangelist, overlap, rl_link); + TAILQ_REMOVE(rangelist, overlap, rl_link); FREE(overlap, M_TEMP); break; @@ -208,33 +211,26 @@ rl_remove(off_t start, off_t end, struct rl_head *rangelist) /* * Now link the new entry into the range list after the range from which it was split: */ - CIRCLEQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link); + TAILQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link); break; case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */ - moretotest = (overlap != CIRCLEQ_LAST(rangelist)); -#ifdef RL_DIAGNOSTIC - if (CIRCLEQ_NEXT(overlap, rl_link) == overlap) panic("rl_remove: circular range list?!"); -#endif - next_range = CIRCLEQ_NEXT(overlap, rl_link); /* Check before discarding overlap entry */ - CIRCLEQ_REMOVE(rangelist, overlap, rl_link); + /* Check before discarding overlap entry */ + next_range = TAILQ_NEXT(overlap, rl_link); + TAILQ_REMOVE(rangelist, overlap, rl_link); FREE(overlap, M_TEMP); - if (moretotest) { + if (next_range) { range = next_range; continue; }; break; case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */ - moretotest = (overlap != CIRCLEQ_LAST(rangelist)); overlap->rl_end = start - 1; - if (moretotest) { -#ifdef RL_DIAGNOSTIC - if (CIRCLEQ_NEXT(overlap, rl_link) == overlap) panic("rl_remove: circular range list?!"); -#endif - range = CIRCLEQ_NEXT(overlap, rl_link); + range = TAILQ_NEXT(overlap, rl_link); + if (range) { continue; - }; + } break; case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */ @@ -263,16 +259,53 @@ rl_scan(struct rl_head *rangelist, off_t start, off_t end, struct rl_entry **overlap) { - - if (CIRCLEQ_EMPTY(rangelist)) { - *overlap = NULL; - return RL_NOOVERLAP; - }; - - return rl_scan_from(rangelist, start, end, overlap, CIRCLEQ_FIRST(rangelist)); + + return rl_scan_from(rangelist, start, end, overlap, TAILQ_FIRST(rangelist)); } +enum rl_overlaptype +rl_overlap(const struct rl_entry *range, off_t start, off_t end) +{ + /* + * OK, check for overlap + * + * Six cases: + * 0) no overlap (RL_NOOVERLAP) + * 1) overlap == range (RL_MATCHINGOVERLAP) + * 2) overlap contains range (RL_OVERLAPCONTAINSRANGE) + * 3) range contains overlap (RL_OVERLAPISCONTAINED) + * 4) overlap starts before range (RL_OVERLAPSTARTSBEFORE) + * 5) overlap ends after range (RL_OVERLAPENDSAFTER) + */ + if (start > range->rl_end || range->rl_start > end) { + /* Case 0 (RL_NOOVERLAP) */ + return RL_NOOVERLAP; + } + + if (range->rl_start == start && range->rl_end == end) { + /* Case 1 (RL_MATCHINGOVERLAP) */ + return RL_MATCHINGOVERLAP; + } + + if (range->rl_start <= start && range->rl_end >= end) { + /* Case 2 (RL_OVERLAPCONTAINSRANGE) */ + return RL_OVERLAPCONTAINSRANGE; + } + if (start <= range->rl_start && end >= range->rl_end) { + /* Case 3 (RL_OVERLAPISCONTAINED) */ + return RL_OVERLAPISCONTAINED; + } + + if (range->rl_start < start && range->rl_end < end) { + /* Case 4 (RL_OVERLAPSTARTSBEFORE) */ + return RL_OVERLAPSTARTSBEFORE; + } + + /* Case 5 (RL_OVERLAPENDSAFTER) */ + // range->rl_start > start && range->rl_end > end + return RL_OVERLAPENDSAFTER; +} /* * Walk the list of ranges for an entry to @@ -282,119 +315,50 @@ rl_scan(struct rl_head *rangelist, * There may be more than one. */ static enum rl_overlaptype -rl_scan_from(struct rl_head *rangelist, +rl_scan_from(struct rl_head *rangelist __unused, off_t start, off_t end, struct rl_entry **overlap, - struct rl_entry *range) + struct rl_entry *range) { - if (CIRCLEQ_EMPTY(rangelist)) { - *overlap = NULL; - return RL_NOOVERLAP; - }; - #ifdef RL_DIAGNOSTIC - rl_verify(rangelist); + rl_verify(rangelist); #endif - *overlap = range; - - while (1) { - /* - * OK, check for overlap - * - * Six cases: - * 0) no overlap (RL_NOOVERLAP) - * 1) overlap == range (RL_MATCHINGOVERLAP) - * 2) overlap contains range (RL_OVERLAPCONTAINSRANGE) - * 3) range contains overlap (RL_OVERLAPISCONTAINED) - * 4) overlap starts before range (RL_OVERLAPSTARTSBEFORE) - * 5) overlap ends after range (RL_OVERLAPENDSAFTER) - */ - if (((range->rl_end != RL_INFINITY) && (start > range->rl_end)) || - ((end != RL_INFINITY) && (range->rl_start > end))) { - /* Case 0 (RL_NOOVERLAP), at least with the current entry: */ - if ((end != RL_INFINITY) && (range->rl_start > end)) { - return RL_NOOVERLAP; - }; - - /* Check the other entries in the list: */ - if (range == CIRCLEQ_LAST(rangelist)) { - return RL_NOOVERLAP; - }; -#ifdef RL_DIAGNOSTIC - if (CIRCLEQ_NEXT(range, rl_link) == range) panic("rl_scan_from: circular range list?!"); -#endif - *overlap = range = CIRCLEQ_NEXT(range, rl_link); - continue; - } - - if ((range->rl_start == start) && (range->rl_end == end)) { - /* Case 1 (RL_MATCHINGOVERLAP) */ - return RL_MATCHINGOVERLAP; - } - - if ((range->rl_start <= start) && - (end != RL_INFINITY) && - ((range->rl_end >= end) || (range->rl_end == RL_INFINITY))) { - /* Case 2 (RL_OVERLAPCONTAINSRANGE) */ - return RL_OVERLAPCONTAINSRANGE; - } - - if ((start <= range->rl_start) && - ((end == RL_INFINITY) || - ((range->rl_end != RL_INFINITY) && (end >= range->rl_end)))) { - /* Case 3 (RL_OVERLAPISCONTAINED) */ - return RL_OVERLAPISCONTAINED; - } - - if ((range->rl_start < start) && - ((range->rl_end >= start) || (range->rl_end == RL_INFINITY))) { - /* Case 4 (RL_OVERLAPSTARTSBEFORE) */ - return RL_OVERLAPSTARTSBEFORE; - } - - if ((range->rl_start > start) && - (end != RL_INFINITY) && - ((range->rl_end > end) || (range->rl_end == RL_INFINITY))) { - /* Case 5 (RL_OVERLAPENDSAFTER) */ - return RL_OVERLAPENDSAFTER; + while (range) { + enum rl_overlaptype ot = rl_overlap(range, start, end); + + if (ot != RL_NOOVERLAP || range->rl_start > end) { + *overlap = range; + return ot; } - /* Control should never reach here... */ -#ifdef RL_DIAGNOSTIC - panic("rl_scan_from: unhandled overlap condition?!"); -#endif + range = TAILQ_NEXT(range, rl_link); } - + + *overlap = NULL; return RL_NOOVERLAP; } static void rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range) { - struct rl_entry *next_range; - - while (1) { - if (range == CIRCLEQ_LAST(rangelist)) return; - -#ifdef RL_DIAGNOSTIC - if (CIRCLEQ_NEXT(range, rl_link) == range) panic("rl_collapse_forwards: circular range list?!"); -#endif - next_range = CIRCLEQ_NEXT(range, rl_link); - if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return; + struct rl_entry *next_range; + + while ((next_range = TAILQ_NEXT(range, rl_link))) { + if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return; - /* Expand this range to include the next range: */ - range->rl_end = next_range->rl_end; - - /* Remove the now covered range from the list: */ - CIRCLEQ_REMOVE(rangelist, next_range, rl_link); - FREE(next_range, M_TEMP); + /* Expand this range to include the next range: */ + range->rl_end = next_range->rl_end; + + /* Remove the now covered range from the list: */ + TAILQ_REMOVE(rangelist, next_range, rl_link); + FREE(next_range, M_TEMP); #ifdef RL_DIAGNOSTIC rl_verify(rangelist); #endif - }; + }; } @@ -403,14 +367,8 @@ static void rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) { struct rl_entry *prev_range; - while (1) { - if (range == CIRCLEQ_FIRST(rangelist)) return; - -#ifdef RL_DIAGNOSTIC - if (CIRCLEQ_PREV(range, rl_link) == range) panic("rl_collapse_backwards: circular range list?!"); -#endif - prev_range = CIRCLEQ_PREV(range, rl_link); - if (prev_range->rl_end < range->rl_start - 1) { + while ((prev_range = TAILQ_PREV(range, rl_head, rl_link))) { + if (prev_range->rl_end < range->rl_start -1) { #ifdef RL_DIAGNOSTIC rl_verify(rangelist); #endif @@ -421,7 +379,7 @@ rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) { range->rl_start = prev_range->rl_start; /* Remove the now covered range from the list: */ - CIRCLEQ_REMOVE(rangelist, prev_range, rl_link); + TAILQ_REMOVE(rangelist, prev_range, rl_link); FREE(prev_range, M_TEMP); }; } @@ -434,3 +392,79 @@ rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range) rl_collapse_forwards(rangelist, range); rl_collapse_backwards(rangelist, range); } + +void rl_remove_all(struct rl_head *rangelist) +{ + struct rl_entry *r, *nextr; + TAILQ_FOREACH_SAFE(r, rangelist, rl_link, nextr) + FREE(r, M_TEMP); + TAILQ_INIT(rangelist); +} + +/* + * In the case where b is contained by a, we return the the largest part + * remaining. The result is stored in a. + */ +void rl_subtract(struct rl_entry *a, const struct rl_entry *b) +{ + switch (rl_overlap(b, a->rl_start, a->rl_end)) { + case RL_MATCHINGOVERLAP: + case RL_OVERLAPCONTAINSRANGE: + a->rl_end = a->rl_start - 1; + break; + case RL_OVERLAPISCONTAINED: + // Keep the bigger part + if (b->rl_start - a->rl_start >= a->rl_end - b->rl_end) { + // Keep left + a->rl_end = b->rl_start - 1; + } else { + // Keep right + a->rl_start = b->rl_end + 1; + } + break; + case RL_OVERLAPSTARTSBEFORE: + a->rl_start = b->rl_end + 1; + break; + case RL_OVERLAPENDSAFTER: + a->rl_end = b->rl_start - 1; + break; + case RL_NOOVERLAP: + break; + } +} + +#else /* not HFS - temp workaround until 4277828 is fixed */ +/* stubs for exported routines that aren't present when we build kernel without HFS */ + +#include + +void rl_add(off_t start, off_t end, void *rangelist); +void rl_init(void *rangelist); +void rl_remove(off_t start, off_t end, void *rangelist); +int rl_scan(void *rangelist, off_t start, off_t end, void **overlap); + +void rl_add(__unused off_t start, __unused off_t end, __unused void *rangelist) +{ + return; +} + +void rl_init(__unused void *rangelist) +{ + return; +} + +void rl_remove(__unused off_t start, __unused off_t end, __unused void *rangelist) +{ + return; +} + +int rl_scan(__unused void *rangelist, __unused off_t start, __unused off_t end, __unused void **overlap) +{ + return(0); +} + +void rl_remove_all(struct rl_head *rangelist) +{ +} + +#endif /* HFS */