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