]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfscommon/Misc/VolumeAllocation.c
projects / apple / xnu.git / blob
? search:


cef473b5eaf93580d96fa199e90d273a3dd2287b
[apple/xnu.git] / bsd / hfs / hfscommon / Misc / VolumeAllocation.c
1 /*
2 * Copyright (c) 2000-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 File: VolumeAllocation.c
30
31 Contains: Routines for accessing and modifying the volume bitmap.
32
33 Version: HFS Plus 1.0
34
35 Copyright: © 1996-2001 by Apple Computer, Inc., all rights reserved.
36
37 */
38
39 /*
40 Public routines:
41 BlockAllocate
42 Allocate space on a volume. Can allocate space contiguously.
43 If not contiguous, then allocation may be less than what was
44 asked for. Returns the starting block number, and number of
45 blocks. (Will only do a single extent???)
46 BlockDeallocate
47 Deallocate a contiguous run of allocation blocks.
48
49 invalidate_free_extent_cache Invalidate free extent cache for a given volume.
50
51 Internal routines:
52 BlockMarkFree
53 Mark a contiguous range of blocks as free. The corresponding
54 bits in the volume bitmap will be cleared.
55 BlockMarkAllocated
56 Mark a contiguous range of blocks as allocated. The cor-
57 responding bits in the volume bitmap are set. Also tests to see
58 if any of the blocks were previously unallocated.
59 FindContiguous
60 Find a contiguous range of blocks of a given size. The caller
61 specifies where to begin the search (by block number). The
62 block number of the first block in the range is returned.
63 BlockAllocateAny
64 Find and allocate a contiguous range of blocks up to a given size. The
65 first range of contiguous free blocks found are allocated, even if there
66 are fewer blocks than requested (and even if a contiguous range of blocks
67 of the given size exists elsewhere).
68 BlockAllocateContig
69 Find and allocate a contiguous range of blocks of a given size. If
70 a contiguous range of free blocks of the given size isn't found, then
71 the allocation fails (i.e. it is "all or nothing").
72
73 BlockAllocateKnown
74 Try to allocate space from known free space in the volume's
75 free extent cache.
76
77 ReadBitmapBlock
78 Given an allocation block number, read the bitmap block that
79 contains that allocation block into a caller-supplied buffer.
80
81 ReleaseBitmapBlock
82 Release a bitmap block back into the buffer cache.
83 */
84
85 #include "../../hfs_macos_defs.h"
86
87 #include <sys/types.h>
88 #include <sys/buf.h>
89 #include <sys/systm.h>
90 #include <sys/disk.h>
91
92 #include "../../hfs.h"
93 #include "../../hfs_dbg.h"
94 #include "../../hfs_format.h"
95 #include "../../hfs_endian.h"
96
97 #include "../headers/FileMgrInternal.h"
98
99
100 enum {
101 kBytesPerWord = 4,
102 kBitsPerByte = 8,
103 kBitsPerWord = 32,
104
105 kBitsWithinWordMask = kBitsPerWord-1
106 };
107
108 #define kLowBitInWordMask 0x00000001ul
109 #define kHighBitInWordMask 0x80000000ul
110 #define kAllBitsSetInWord 0xFFFFFFFFul
111
112
113 static OSErr ReadBitmapBlock(
114 ExtendedVCB *vcb,
115 u_int32_t bit,
116 u_int32_t **buffer,
117 uintptr_t *blockRef);
118
119 static OSErr ReleaseBitmapBlock(
120 ExtendedVCB *vcb,
121 uintptr_t blockRef,
122 Boolean dirty);
123
124 static OSErr BlockAllocateAny(
125 ExtendedVCB *vcb,
126 u_int32_t startingBlock,
127 u_int32_t endingBlock,
128 u_int32_t maxBlocks,
129 Boolean useMetaZone,
130 u_int32_t *actualStartBlock,
131 u_int32_t *actualNumBlocks);
132
133 static OSErr BlockAllocateContig(
134 ExtendedVCB *vcb,
135 u_int32_t startingBlock,
136 u_int32_t minBlocks,
137 u_int32_t maxBlocks,
138 Boolean useMetaZone,
139 u_int32_t *actualStartBlock,
140 u_int32_t *actualNumBlocks);
141
142 static OSErr BlockFindContiguous(
143 ExtendedVCB *vcb,
144 u_int32_t startingBlock,
145 u_int32_t endingBlock,
146 u_int32_t minBlocks,
147 u_int32_t maxBlocks,
148 Boolean useMetaZone,
149 u_int32_t *actualStartBlock,
150 u_int32_t *actualNumBlocks);
151
152 static OSErr BlockAllocateKnown(
153 ExtendedVCB *vcb,
154 u_int32_t maxBlocks,
155 u_int32_t *actualStartBlock,
156 u_int32_t *actualNumBlocks);
157
158 static int free_extent_cache_active(
159 ExtendedVCB *vcb);
160
161 /*
162 ;________________________________________________________________________________
163 ;
164 ; Routine: BlkAlloc
165 ;
166 ; Function: Allocate space on a volume. If contiguous allocation is requested,
167 ; at least the requested number of bytes will be allocated or an
168 ; error will be returned. If contiguous allocation is not forced,
169 ; the space will be allocated at the first free fragment following
170 ; the requested starting allocation block. If there is not enough
171 ; room there, a block of less than the requested size will be
172 ; allocated.
173 ;
174 ; If the requested starting block is 0 (for new file allocations),
175 ; the volume's allocation block pointer will be used as a starting
176 ; point.
177 ;
178 ; Input Arguments:
179 ; vcb - Pointer to ExtendedVCB for the volume to allocate space on
180 ; fcb - Pointer to FCB for the file for which storage is being allocated
181 ; startingBlock - Preferred starting allocation block, 0 = no preference
182 ; forceContiguous - Force contiguous flag - if bit 0 set (NE), allocation is contiguous
183 ; or an error is returned
184 ; useMetaZone -
185 ; minBlocks - Number of blocks requested. If the allocation is non-contiguous,
186 ; less than this may actually be allocated
187 ; maxBlocks - The maximum number of blocks to allocate. If there is additional free
188 ; space after bytesRequested, then up to maxBlocks bytes should really
189 ; be allocated. (Used by ExtendFileC to round up allocations to a multiple
190 ; of the file's clump size.)
191 ;
192 ; Output:
193 ; (result) - Error code, zero for successful allocation
194 ; *startBlock - Actual starting allocation block
195 ; *actualBlocks - Actual number of allocation blocks allocated
196 ;
197 ; Side effects:
198 ; The volume bitmap is read and updated; the volume bitmap cache may be changed.
199 ;________________________________________________________________________________
200 */
201 static void
202 sanity_check_free_ext(__unused ExtendedVCB *vcb, __unused int check_allocated)
203 {
204 #if DEBUG
205 u_int32_t i, j;
206
207 for(i=0; i < vcb->vcbFreeExtCnt; i++) {
208 u_int32_t start, nblocks;
209
210 start = vcb->vcbFreeExt[i].startBlock;
211 nblocks = vcb->vcbFreeExt[i].blockCount;
212
213
214 if (nblocks == 0) {
215 panic("hfs: %p: slot %d in the free extent array had a zero count (%d)\n", vcb, i, start);
216 }
217
218 if (check_allocated && hfs_isallocated(vcb, start, nblocks)) {
219 panic("hfs: %p: slot %d in the free extent array is bad (%d / %d)\n",
220 vcb, i, start, nblocks);
221 }
222
223 for(j=i+1; j < vcb->vcbFreeExtCnt; j++) {
224 if (start == vcb->vcbFreeExt[j].startBlock) {
225 panic("hfs: %p: slot %d/%d are dups?! (%d / %d ; %d / %d)\n",
226 vcb, i, j, start, nblocks, vcb->vcbFreeExt[i].startBlock,
227 vcb->vcbFreeExt[i].blockCount);
228 }
229 }
230 }
231 #endif
232 }
233
234
235 __private_extern__
236 OSErr BlockAllocate (
237 ExtendedVCB *vcb, /* which volume to allocate space on */
238 u_int32_t startingBlock, /* preferred starting block, or 0 for no preference */
239 u_int32_t minBlocks, /* desired number of blocks to allocate */
240 u_int32_t maxBlocks, /* maximum number of blocks to allocate */
241 Boolean forceContiguous, /* non-zero to force contiguous allocation and to force */
242 /* minBlocks bytes to actually be allocated */
243
244 Boolean useMetaZone,
245 u_int32_t *actualStartBlock, /* actual first block of allocation */
246 u_int32_t *actualNumBlocks) /* number of blocks actually allocated; if forceContiguous */
247 /* was zero, then this may represent fewer than minBlocks */
248 {
249 u_int32_t freeBlocks;
250 OSErr err;
251 Boolean updateAllocPtr = false; // true if nextAllocation needs to be updated
252
253 //
254 // Initialize outputs in case we get an error
255 //
256 *actualStartBlock = 0;
257 *actualNumBlocks = 0;
258 freeBlocks = hfs_freeblks(VCBTOHFS(vcb), 0);
259
260 //
261 // If the disk is already full, don't bother.
262 //
263 if (freeBlocks == 0) {
264 err = dskFulErr;
265 goto Exit;
266 }
267 if (forceContiguous && freeBlocks < minBlocks) {
268 err = dskFulErr;
269 goto Exit;
270 }
271 /*
272 * Clip if necessary so we don't over-subscribe the free blocks.
273 */
274 if (minBlocks > freeBlocks) {
275 minBlocks = freeBlocks;
276 }
277 if (maxBlocks > freeBlocks) {
278 maxBlocks = freeBlocks;
279 }
280
281 //
282 // If caller didn't specify a starting block number, then use the volume's
283 // next block to allocate from.
284 //
285 if (startingBlock == 0) {
286 HFS_MOUNT_LOCK(vcb, TRUE);
287 if (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE) {
288 startingBlock = vcb->sparseAllocation;
289 } else {
290 startingBlock = vcb->nextAllocation;
291 }
292 HFS_MOUNT_UNLOCK(vcb, TRUE);
293 updateAllocPtr = true;
294 }
295 if (startingBlock >= vcb->allocLimit) {
296 startingBlock = 0; /* overflow so start at beginning */
297 }
298
299 //
300 // If the request must be contiguous, then find a sequence of free blocks
301 // that is long enough. Otherwise, find the first free block.
302 //
303 if (forceContiguous) {
304 err = BlockAllocateContig(vcb, startingBlock, minBlocks, maxBlocks,
305 useMetaZone, actualStartBlock, actualNumBlocks);
306 /*
307 * If we allocated from a new position then
308 * also update the roving allocator.
309 */
310 if ((err == noErr) &&
311 (*actualStartBlock > startingBlock) &&
312 ((*actualStartBlock < VCBTOHFS(vcb)->hfs_metazone_start) ||
313 (*actualStartBlock > VCBTOHFS(vcb)->hfs_metazone_end))) {
314
315 updateAllocPtr = true;
316 }
317 } else {
318 /*
319 * Scan the bitmap once, gather the N largest free extents, then
320 * allocate from these largest extents. Repeat as needed until
321 * we get all the space we needed. We could probably build up
322 * that list when the higher level caller tried (and failed) a
323 * contiguous allocation first.
324 */
325 err = BlockAllocateKnown(vcb, maxBlocks, actualStartBlock, actualNumBlocks);
326 if (err == dskFulErr)
327 err = BlockAllocateAny(vcb, startingBlock, vcb->allocLimit,
328 maxBlocks, useMetaZone, actualStartBlock,
329 actualNumBlocks);
330 if (err == dskFulErr)
331 err = BlockAllocateAny(vcb, 1, startingBlock, maxBlocks,
332 useMetaZone, actualStartBlock,
333 actualNumBlocks);
334 }
335
336 Exit:
337 // if we actually allocated something then go update the
338 // various bits of state that we maintain regardless of
339 // whether there was an error (i.e. partial allocations
340 // still need to update things like the free block count).
341 //
342 if (*actualNumBlocks != 0) {
343 int i,j;
344
345 //
346 // If we used the volume's roving allocation pointer, then we need to update it.
347 // Adding in the length of the current allocation might reduce the next allocate
348 // call by avoiding a re-scan of the already allocated space. However, the clump
349 // just allocated can quite conceivably end up being truncated or released when
350 // the file is closed or its EOF changed. Leaving the allocation pointer at the
351 // start of the last allocation will avoid unnecessary fragmentation in this case.
352 //
353 HFS_MOUNT_LOCK(vcb, TRUE);
354
355 if (vcb->vcbFreeExtCnt == 0 && vcb->hfs_freed_block_count == 0) {
356 vcb->sparseAllocation = *actualStartBlock;
357 }
358 if (*actualNumBlocks < vcb->hfs_freed_block_count) {
359 vcb->hfs_freed_block_count -= *actualNumBlocks;
360 } else {
361 vcb->hfs_freed_block_count = 0;
362 }
363
364 if (updateAllocPtr &&
365 ((*actualStartBlock < VCBTOHFS(vcb)->hfs_metazone_start) ||
366 (*actualStartBlock > VCBTOHFS(vcb)->hfs_metazone_end))) {
367 HFS_UPDATE_NEXT_ALLOCATION(vcb, *actualStartBlock);
368 }
369
370 for(i=0; i < (int)vcb->vcbFreeExtCnt; i++) {
371 u_int32_t start, end;
372
373 start = vcb->vcbFreeExt[i].startBlock;
374 end = start + vcb->vcbFreeExt[i].blockCount;
375
376 if ( (*actualStartBlock >= start && *actualStartBlock < end)
377 || ((*actualStartBlock + *actualNumBlocks) > start && *actualStartBlock < start)) {
378
379 for(j=i; j < (int)vcb->vcbFreeExtCnt-1; j++) {
380 vcb->vcbFreeExt[j] = vcb->vcbFreeExt[j+1];
381 }
382
383 vcb->vcbFreeExtCnt--;
384 i--; // so we'll check the guy we just copied down...
385
386 // keep looping because we may have invalidated more
387 // than one entry in the array
388 }
389 }
390
391 //
392 // Update the number of free blocks on the volume
393 //
394 vcb->freeBlocks -= *actualNumBlocks;
395 MarkVCBDirty(vcb);
396 HFS_MOUNT_UNLOCK(vcb, TRUE);
397
398 sanity_check_free_ext(vcb, 1);
399
400 hfs_generate_volume_notifications(VCBTOHFS(vcb));
401 }
402
403 return err;
404 }
405
406
407 /*
408 ;________________________________________________________________________________
409 ;
410 ; Routine: BlkDealloc
411 ;
412 ; Function: Update the bitmap to deallocate a run of disk allocation blocks
413 ;
414 ; Input Arguments:
415 ; vcb - Pointer to ExtendedVCB for the volume to free space on
416 ; firstBlock - First allocation block to be freed
417 ; numBlocks - Number of allocation blocks to free up (must be > 0!)
418 ;
419 ; Output:
420 ; (result) - Result code
421 ;
422 ; Side effects:
423 ; The volume bitmap is read and updated; the volume bitmap cache may be changed.
424 ;________________________________________________________________________________
425 */
426
427 __private_extern__
428 OSErr BlockDeallocate (
429 ExtendedVCB *vcb, // Which volume to deallocate space on
430 u_int32_t firstBlock, // First block in range to deallocate
431 u_int32_t numBlocks) // Number of contiguous blocks to deallocate
432 {
433 OSErr err;
434 u_int32_t tempWord;
435
436 //
437 // If no blocks to deallocate, then exit early
438 //
439 if (numBlocks == 0) {
440 err = noErr;
441 goto Exit;
442 }
443
444 //
445 // Call internal routine to free the sequence of blocks
446 //
447 err = BlockMarkFree(vcb, firstBlock, numBlocks);
448 if (err)
449 goto Exit;
450
451 //
452 // Update the volume's free block count, and mark the VCB as dirty.
453 //
454 HFS_MOUNT_LOCK(vcb, TRUE);
455 vcb->freeBlocks += numBlocks;
456 vcb->hfs_freed_block_count += numBlocks;
457 if (firstBlock < vcb->sparseAllocation) {
458 vcb->sparseAllocation = firstBlock;
459 }
460
461 if (vcb->nextAllocation == (firstBlock + numBlocks)) {
462 HFS_UPDATE_NEXT_ALLOCATION(vcb, (vcb->nextAllocation - numBlocks));
463 }
464
465 if (free_extent_cache_active(vcb) == 0) {
466 goto skip_cache;
467 }
468
469 tempWord = vcb->vcbFreeExtCnt;
470 // Add this free chunk to the free extent list
471 if (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE) {
472 // Sorted by start block
473 if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].startBlock > firstBlock)
474 --tempWord;
475 if (tempWord < kMaxFreeExtents)
476 {
477 // We're going to add this extent. Bubble any smaller extents down in the list.
478 while (tempWord && vcb->vcbFreeExt[tempWord-1].startBlock > firstBlock)
479 {
480 vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1];
481 if (vcb->vcbFreeExt[tempWord].startBlock < vcb->sparseAllocation) {
482 vcb->sparseAllocation = vcb->vcbFreeExt[tempWord].startBlock;
483 }
484 --tempWord;
485 }
486 vcb->vcbFreeExt[tempWord].startBlock = firstBlock;
487 vcb->vcbFreeExt[tempWord].blockCount = numBlocks;
488
489 if (vcb->vcbFreeExtCnt < kMaxFreeExtents) {
490 ++vcb->vcbFreeExtCnt;
491 }
492 }
493 } else {
494 // Sorted by num blocks
495 if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].blockCount < numBlocks)
496 --tempWord;
497 if (tempWord < kMaxFreeExtents)
498 {
499 // We're going to add this extent. Bubble any smaller extents down in the list.
500 while (tempWord && vcb->vcbFreeExt[tempWord-1].blockCount < numBlocks)
501 {
502 vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1];
503 if (vcb->vcbFreeExt[tempWord].startBlock < vcb->sparseAllocation) {
504 vcb->sparseAllocation = vcb->vcbFreeExt[tempWord].startBlock;
505 }
506 --tempWord;
507 }
508 vcb->vcbFreeExt[tempWord].startBlock = firstBlock;
509 vcb->vcbFreeExt[tempWord].blockCount = numBlocks;
510
511 if (vcb->vcbFreeExtCnt < kMaxFreeExtents) {
512 ++vcb->vcbFreeExtCnt;
513 }
514 }
515 }
516
517 skip_cache:
518 MarkVCBDirty(vcb);
519 HFS_MOUNT_UNLOCK(vcb, TRUE);
520
521 sanity_check_free_ext(vcb, 1);
522
523 hfs_generate_volume_notifications(VCBTOHFS(vcb));
524 Exit:
525
526 return err;
527 }
528
529
530 u_int8_t freebitcount[16] = {
531 4, 3, 3, 2, 3, 2, 2, 1, /* 0 1 2 3 4 5 6 7 */
532 3, 2, 2, 1, 2, 1, 1, 0, /* 8 9 A B C D E F */
533 };
534
535 __private_extern__
536 u_int32_t
537 MetaZoneFreeBlocks(ExtendedVCB *vcb)
538 {
539 u_int32_t freeblocks;
540 u_int32_t *currCache;
541 uintptr_t blockRef;
542 u_int32_t bit;
543 u_int32_t lastbit;
544 int bytesleft;
545 int bytesperblock;
546 u_int8_t byte;
547 u_int8_t *buffer;
548
549 blockRef = 0;
550 bytesleft = freeblocks = 0;
551 buffer = NULL;
552 bit = VCBTOHFS(vcb)->hfs_metazone_start;
553 if (bit == 1)
554 bit = 0;
555
556 lastbit = VCBTOHFS(vcb)->hfs_metazone_end;
557 bytesperblock = vcb->vcbVBMIOSize;
558
559 /*
560 * Count all the bits from bit to lastbit.
561 */
562 while (bit < lastbit) {
563 /*
564 * Get next bitmap block.
565 */
566 if (bytesleft == 0) {
567 if (blockRef) {
568 (void) ReleaseBitmapBlock(vcb, blockRef, false);
569 blockRef = 0;
570 }
571 if (ReadBitmapBlock(vcb, bit, &currCache, &blockRef) != 0) {
572 return (0);
573 }
574 buffer = (u_int8_t *)currCache;
575 bytesleft = bytesperblock;
576 }
577 byte = *buffer++;
578 freeblocks += freebitcount[byte & 0x0F];
579 freeblocks += freebitcount[(byte >> 4) & 0x0F];
580 bit += kBitsPerByte;
581 --bytesleft;
582 }
583 if (blockRef)
584 (void) ReleaseBitmapBlock(vcb, blockRef, false);
585
586 return (freeblocks);
587 }
588
589
590 /*
591 * Obtain the next allocation block (bit) that's
592 * outside the metadata allocation zone.
593 */
594 static u_int32_t NextBitmapBlock(
595 ExtendedVCB *vcb,
596 u_int32_t bit)
597 {
598 struct hfsmount *hfsmp = VCBTOHFS(vcb);
599
600 if ((hfsmp->hfs_flags & HFS_METADATA_ZONE) == 0)
601 return (bit);
602 /*
603 * Skip over metadata allocation zone.
604 */
605 if ((bit >= hfsmp->hfs_metazone_start) &&
606 (bit <= hfsmp->hfs_metazone_end)) {
607 bit = hfsmp->hfs_metazone_end + 1;
608 }
609 return (bit);
610 }
611
612
613 /*
614 ;_______________________________________________________________________
615 ;
616 ; Routine: ReadBitmapBlock
617 ;
618 ; Function: Read in a bitmap block corresponding to a given allocation
619 ; block (bit). Return a pointer to the bitmap block.
620 ;
621 ; Inputs:
622 ; vcb -- Pointer to ExtendedVCB
623 ; bit -- Allocation block whose bitmap block is desired
624 ;
625 ; Outputs:
626 ; buffer -- Pointer to bitmap block corresonding to "block"
627 ; blockRef
628 ;_______________________________________________________________________
629 */
630 static OSErr ReadBitmapBlock(
631 ExtendedVCB *vcb,
632 u_int32_t bit,
633 u_int32_t **buffer,
634 uintptr_t *blockRef)
635 {
636 OSErr err;
637 struct buf *bp = NULL;
638 struct vnode *vp = NULL;
639 daddr64_t block;
640 u_int32_t blockSize;
641
642 /*
643 * volume bitmap blocks are protected by the allocation file lock
644 */
645 REQUIRE_FILE_LOCK(vcb->hfs_allocation_vp, false);
646
647 blockSize = (u_int32_t)vcb->vcbVBMIOSize;
648 block = (daddr64_t)(bit / (blockSize * kBitsPerByte));
649
650 if (vcb->vcbSigWord == kHFSPlusSigWord) {
651 vp = vcb->hfs_allocation_vp; /* use allocation file vnode */
652
653 } else /* hfs */ {
654 vp = VCBTOHFS(vcb)->hfs_devvp; /* use device I/O vnode */
655 block += vcb->vcbVBMSt; /* map to physical block */
656 }
657
658 err = (int)buf_meta_bread(vp, block, blockSize, NOCRED, &bp);
659
660 if (bp) {
661 if (err) {
662 buf_brelse(bp);
663 *blockRef = 0;
664 *buffer = NULL;
665 } else {
666 *blockRef = (uintptr_t)bp;
667 *buffer = (u_int32_t *)buf_dataptr(bp);
668 }
669 }
670
671 return err;
672 }
673
674
675 /*
676 ;_______________________________________________________________________
677 ;
678 ; Routine: ReleaseBitmapBlock
679 ;
680 ; Function: Relase a bitmap block.
681 ;
682 ; Inputs:
683 ; vcb
684 ; blockRef
685 ; dirty
686 ;_______________________________________________________________________
687 */
688 static OSErr ReleaseBitmapBlock(
689 ExtendedVCB *vcb,
690 uintptr_t blockRef,
691 Boolean dirty)
692 {
693 struct buf *bp = (struct buf *)blockRef;
694
695 if (blockRef == 0) {
696 if (dirty)
697 panic("hfs: ReleaseBitmapBlock: missing bp");
698 return (0);
699 }
700
701 if (bp) {
702 if (dirty) {
703 // XXXdbg
704 struct hfsmount *hfsmp = VCBTOHFS(vcb);
705
706 if (hfsmp->jnl) {
707 journal_modify_block_end(hfsmp->jnl, bp, NULL, NULL);
708 } else {
709 buf_bdwrite(bp);
710 }
711 } else {
712 buf_brelse(bp);
713 }
714 }
715
716 return (0);
717 }
718
719
720 /*
721 _______________________________________________________________________
722
723 Routine: BlockAllocateContig
724
725 Function: Allocate a contiguous group of allocation blocks. The
726 allocation is all-or-nothing. The caller guarantees that
727 there are enough free blocks (though they may not be
728 contiguous, in which case this call will fail).
729
730 Inputs:
731 vcb Pointer to volume where space is to be allocated
732 startingBlock Preferred first block for allocation
733 minBlocks Minimum number of contiguous blocks to allocate
734 maxBlocks Maximum number of contiguous blocks to allocate
735 useMetaZone
736
737 Outputs:
738 actualStartBlock First block of range allocated, or 0 if error
739 actualNumBlocks Number of blocks allocated, or 0 if error
740 _______________________________________________________________________
741 */
742 static OSErr BlockAllocateContig(
743 ExtendedVCB *vcb,
744 u_int32_t startingBlock,
745 u_int32_t minBlocks,
746 u_int32_t maxBlocks,
747 Boolean useMetaZone,
748 u_int32_t *actualStartBlock,
749 u_int32_t *actualNumBlocks)
750 {
751 OSErr err;
752
753 //
754 // Find a contiguous group of blocks at least minBlocks long.
755 // Determine the number of contiguous blocks available (up
756 // to maxBlocks).
757 //
758
759 /*
760 * NOTE: If the only contiguous free extent of at least minBlocks
761 * crosses startingBlock (i.e. starts before, ends after), then we
762 * won't find it. Earlier versions *did* find this case by letting
763 * the second search look past startingBlock by minBlocks. But
764 * with the free extent cache, this can lead to duplicate entries
765 * in the cache, causing the same blocks to be allocated twice.
766 */
767 err = BlockFindContiguous(vcb, startingBlock, vcb->allocLimit, minBlocks,
768 maxBlocks, useMetaZone, actualStartBlock, actualNumBlocks);
769 if (err == dskFulErr && startingBlock != 0) {
770 /*
771 * Constrain the endingBlock so we don't bother looking for ranges
772 * that would overlap those found in the previous call.
773 */
774 err = BlockFindContiguous(vcb, 1, startingBlock, minBlocks, maxBlocks,
775 useMetaZone, actualStartBlock, actualNumBlocks);
776 }
777 //
778 // Now mark those blocks allocated.
779 //
780 if (err == noErr)
781 err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks);
782
783 return err;
784 }
785
786 /*
787 _______________________________________________________________________
788
789 Routine: BlockAllocateAny
790
791 Function: Allocate one or more allocation blocks. If there are fewer
792 free blocks than requested, all free blocks will be
793 allocated. The caller guarantees that there is at least
794 one free block.
795
796 Inputs:
797 vcb Pointer to volume where space is to be allocated
798 startingBlock Preferred first block for allocation
799 endingBlock Last block to check + 1
800 maxBlocks Maximum number of contiguous blocks to allocate
801 useMetaZone
802
803 Outputs:
804 actualStartBlock First block of range allocated, or 0 if error
805 actualNumBlocks Number of blocks allocated, or 0 if error
806 _______________________________________________________________________
807 */
808 static OSErr BlockAllocateAny(
809 ExtendedVCB *vcb,
810 u_int32_t startingBlock,
811 register u_int32_t endingBlock,
812 u_int32_t maxBlocks,
813 Boolean useMetaZone,
814 u_int32_t *actualStartBlock,
815 u_int32_t *actualNumBlocks)
816 {
817 OSErr err;
818 register u_int32_t block; // current block number
819 register u_int32_t currentWord; // Pointer to current word within bitmap block
820 register u_int32_t bitMask; // Word with given bits already set (ready to OR in)
821 register u_int32_t wordsLeft; // Number of words left in this bitmap block
822 u_int32_t *buffer = NULL;
823 u_int32_t *currCache = NULL;
824 uintptr_t blockRef;
825 u_int32_t bitsPerBlock;
826 u_int32_t wordsPerBlock;
827 Boolean dirty = false;
828 struct hfsmount *hfsmp = VCBTOHFS(vcb);
829
830 /*
831 * When we're skipping the metadata zone and the start/end
832 * range overlaps with the metadata zone then adjust the
833 * start to be outside of the metadata zone. If the range
834 * is entirely inside the metadata zone then we can deny the
835 * request (dskFulErr).
836 */
837 if (!useMetaZone && (vcb->hfs_flags & HFS_METADATA_ZONE)) {
838 if (startingBlock <= vcb->hfs_metazone_end) {
839 if (endingBlock > (vcb->hfs_metazone_end + 2))
840 startingBlock = vcb->hfs_metazone_end + 1;
841 else {
842 err = dskFulErr;
843 goto Exit;
844 }
845 }
846 }
847
848 // Since this routine doesn't wrap around
849 if (maxBlocks > (endingBlock - startingBlock)) {
850 maxBlocks = endingBlock - startingBlock;
851 }
852
853 //
854 // Pre-read the first bitmap block
855 //
856 err = ReadBitmapBlock(vcb, startingBlock, &currCache, &blockRef);
857 if (err != noErr) goto Exit;
858 buffer = currCache;
859
860 //
861 // Set up the current position within the block
862 //
863 {
864 u_int32_t wordIndexInBlock;
865
866 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
867 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
868
869 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
870 buffer += wordIndexInBlock;
871 wordsLeft = wordsPerBlock - wordIndexInBlock;
872 currentWord = SWAP_BE32 (*buffer);
873 bitMask = kHighBitInWordMask >> (startingBlock & kBitsWithinWordMask);
874 }
875
876 //
877 // Find the first unallocated block
878 //
879 block=startingBlock;
880 while (block < endingBlock) {
881 if ((currentWord & bitMask) == 0)
882 break;
883
884 // Next bit
885 ++block;
886 bitMask >>= 1;
887 if (bitMask == 0) {
888 // Next word
889 bitMask = kHighBitInWordMask;
890 ++buffer;
891
892 if (--wordsLeft == 0) {
893 // Next block
894 buffer = currCache = NULL;
895 err = ReleaseBitmapBlock(vcb, blockRef, false);
896 if (err != noErr) goto Exit;
897
898 /*
899 * Skip over metadata blocks.
900 */
901 if (!useMetaZone) {
902 block = NextBitmapBlock(vcb, block);
903 }
904 if (block >= endingBlock) {
905 err = dskFulErr;
906 goto Exit;
907 }
908
909 err = ReadBitmapBlock(vcb, block, &currCache, &blockRef);
910 if (err != noErr) goto Exit;
911 buffer = currCache;
912
913 wordsLeft = wordsPerBlock;
914 }
915 currentWord = SWAP_BE32 (*buffer);
916 }
917 }
918
919 // Did we get to the end of the bitmap before finding a free block?
920 // If so, then couldn't allocate anything.
921 if (block >= endingBlock) {
922 err = dskFulErr;
923 goto Exit;
924 }
925
926 // Return the first block in the allocated range
927 *actualStartBlock = block;
928 dirty = true;
929
930 // If we could get the desired number of blocks before hitting endingBlock,
931 // then adjust endingBlock so we won't keep looking. Ideally, the comparison
932 // would be (block + maxBlocks) < endingBlock, but that could overflow. The
933 // comparison below yields identical results, but without overflow.
934 if (block < (endingBlock-maxBlocks)) {
935 endingBlock = block + maxBlocks; // if we get this far, we've found enough
936 }
937
938 // XXXdbg
939 if (hfsmp->jnl) {
940 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
941 }
942
943 //
944 // Allocate all of the consecutive blocks
945 //
946 while ((currentWord & bitMask) == 0) {
947 // Allocate this block
948 currentWord |= bitMask;
949
950 // Move to the next block. If no more, then exit.
951 ++block;
952 if (block == endingBlock)
953 break;
954
955 // Next bit
956 bitMask >>= 1;
957 if (bitMask == 0) {
958 *buffer = SWAP_BE32 (currentWord); // update value in bitmap
959
960 // Next word
961 bitMask = kHighBitInWordMask;
962 ++buffer;
963
964 if (--wordsLeft == 0) {
965 // Next block
966 buffer = currCache = NULL;
967 err = ReleaseBitmapBlock(vcb, blockRef, true);
968 if (err != noErr) goto Exit;
969
970 /*
971 * Skip over metadata blocks.
972 */
973 if (!useMetaZone) {
974 u_int32_t nextBlock;
975
976 nextBlock = NextBitmapBlock(vcb, block);
977 if (nextBlock != block) {
978 goto Exit; /* allocation gap, so stop */
979 }
980 }
981
982 err = ReadBitmapBlock(vcb, block, &currCache, &blockRef);
983 if (err != noErr) goto Exit;
984 buffer = currCache;
985
986 // XXXdbg
987 if (hfsmp->jnl) {
988 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
989 }
990
991 wordsLeft = wordsPerBlock;
992 }
993
994 currentWord = SWAP_BE32 (*buffer);
995 }
996 }
997 *buffer = SWAP_BE32 (currentWord); // update the last change
998
999 Exit:
1000 if (err == noErr) {
1001 *actualNumBlocks = block - *actualStartBlock;
1002
1003 // sanity check
1004 if ((*actualStartBlock + *actualNumBlocks) > vcb->allocLimit)
1005 panic("hfs: BlockAllocateAny: allocation overflow on \"%s\"", vcb->vcbVN);
1006 }
1007 else {
1008 *actualStartBlock = 0;
1009 *actualNumBlocks = 0;
1010 }
1011
1012 if (currCache)
1013 (void) ReleaseBitmapBlock(vcb, blockRef, dirty);
1014
1015 return err;
1016 }
1017
1018
1019 /*
1020 _______________________________________________________________________
1021
1022 Routine: BlockAllocateKnown
1023
1024 Function: Try to allocate space from known free space in the free
1025 extent cache.
1026
1027 Inputs:
1028 vcb Pointer to volume where space is to be allocated
1029 maxBlocks Maximum number of contiguous blocks to allocate
1030
1031 Outputs:
1032 actualStartBlock First block of range allocated, or 0 if error
1033 actualNumBlocks Number of blocks allocated, or 0 if error
1034
1035 Returns:
1036 dskFulErr Free extent cache is empty
1037 _______________________________________________________________________
1038 */
1039
1040 static OSErr BlockAllocateKnown(
1041 ExtendedVCB *vcb,
1042 u_int32_t maxBlocks,
1043 u_int32_t *actualStartBlock,
1044 u_int32_t *actualNumBlocks)
1045 {
1046 OSErr err;
1047 u_int32_t i;
1048 u_int32_t foundBlocks;
1049 u_int32_t newStartBlock, newBlockCount;
1050
1051 HFS_MOUNT_LOCK(vcb, TRUE);
1052 if (free_extent_cache_active(vcb) == 0 ||
1053 vcb->vcbFreeExtCnt == 0 ||
1054 vcb->vcbFreeExt[0].blockCount == 0) {
1055 HFS_MOUNT_UNLOCK(vcb, TRUE);
1056 return dskFulErr;
1057 }
1058 HFS_MOUNT_UNLOCK(vcb, TRUE);
1059
1060 // Just grab up to maxBlocks of the first (largest) free exent.
1061 *actualStartBlock = vcb->vcbFreeExt[0].startBlock;
1062 foundBlocks = vcb->vcbFreeExt[0].blockCount;
1063 if (foundBlocks > maxBlocks)
1064 foundBlocks = maxBlocks;
1065 *actualNumBlocks = foundBlocks;
1066
1067 if (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE) {
1068 // since sparse volumes keep the free extent list sorted by starting
1069 // block number, the list won't get re-ordered, it may only shrink
1070 //
1071 vcb->vcbFreeExt[0].startBlock += foundBlocks;
1072 vcb->vcbFreeExt[0].blockCount -= foundBlocks;
1073 if (vcb->vcbFreeExt[0].blockCount == 0) {
1074 for(i=1; i < vcb->vcbFreeExtCnt; i++) {
1075 vcb->vcbFreeExt[i-1] = vcb->vcbFreeExt[i];
1076 }
1077 vcb->vcbFreeExtCnt--;
1078 }
1079
1080 goto done;
1081 }
1082
1083 // Adjust the start and length of that extent.
1084 newStartBlock = vcb->vcbFreeExt[0].startBlock + foundBlocks;
1085 newBlockCount = vcb->vcbFreeExt[0].blockCount - foundBlocks;
1086
1087
1088 // The first extent might not be the largest anymore. Bubble up any
1089 // (now larger) extents to the top of the list.
1090 for (i=1; i<vcb->vcbFreeExtCnt; ++i)
1091 {
1092 if (vcb->vcbFreeExt[i].blockCount > newBlockCount)
1093 {
1094 vcb->vcbFreeExt[i-1].startBlock = vcb->vcbFreeExt[i].startBlock;
1095 vcb->vcbFreeExt[i-1].blockCount = vcb->vcbFreeExt[i].blockCount;
1096 }
1097 else
1098 {
1099 break;
1100 }
1101 }
1102
1103 // If this is now the smallest known free extent, then it might be smaller than
1104 // other extents we didn't keep track of. So, just forget about this extent.
1105 // After the previous loop, (i-1) is the index of the extent we just allocated from.
1106 if (newBlockCount == 0)
1107 {
1108 // then just reduce the number of free extents since this guy got deleted
1109 --vcb->vcbFreeExtCnt;
1110 }
1111 else
1112 {
1113 // It's not the smallest, so store it in its proper place
1114 vcb->vcbFreeExt[i-1].startBlock = newStartBlock;
1115 vcb->vcbFreeExt[i-1].blockCount = newBlockCount;
1116 }
1117
1118 done:
1119 // sanity check
1120 if ((*actualStartBlock + *actualNumBlocks) > vcb->allocLimit)
1121 {
1122 printf ("hfs: BlockAllocateKnown() found allocation overflow on \"%s\"", vcb->vcbVN);
1123 hfs_mark_volume_inconsistent(vcb);
1124 *actualStartBlock = 0;
1125 *actualNumBlocks = 0;
1126 err = EIO;
1127 }
1128 else
1129 {
1130 //
1131 // Now mark the found extent in the bitmap
1132 //
1133 err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks);
1134 }
1135
1136 sanity_check_free_ext(vcb, 1);
1137
1138 return err;
1139 }
1140
1141
1142
1143 /*
1144 _______________________________________________________________________
1145
1146 Routine: BlockMarkAllocated
1147
1148 Function: Mark a contiguous group of blocks as allocated (set in the
1149 bitmap). It assumes those bits are currently marked
1150 deallocated (clear in the bitmap).
1151
1152 Inputs:
1153 vcb Pointer to volume where space is to be allocated
1154 startingBlock First block number to mark as allocated
1155 numBlocks Number of blocks to mark as allocated
1156 _______________________________________________________________________
1157 */
1158 __private_extern__
1159 OSErr BlockMarkAllocated(
1160 ExtendedVCB *vcb,
1161 u_int32_t startingBlock,
1162 register u_int32_t numBlocks)
1163 {
1164 OSErr err;
1165 register u_int32_t *currentWord; // Pointer to current word within bitmap block
1166 register u_int32_t wordsLeft; // Number of words left in this bitmap block
1167 register u_int32_t bitMask; // Word with given bits already set (ready to OR in)
1168 u_int32_t firstBit; // Bit index within word of first bit to allocate
1169 u_int32_t numBits; // Number of bits in word to allocate
1170 u_int32_t *buffer = NULL;
1171 uintptr_t blockRef;
1172 u_int32_t bitsPerBlock;
1173 u_int32_t wordsPerBlock;
1174 // XXXdbg
1175 struct hfsmount *hfsmp = VCBTOHFS(vcb);
1176
1177
1178 //
1179 // Pre-read the bitmap block containing the first word of allocation
1180 //
1181
1182 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1183 if (err != noErr) goto Exit;
1184 //
1185 // Initialize currentWord, and wordsLeft.
1186 //
1187 {
1188 u_int32_t wordIndexInBlock;
1189
1190 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
1191 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1192
1193 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
1194 currentWord = buffer + wordIndexInBlock;
1195 wordsLeft = wordsPerBlock - wordIndexInBlock;
1196 }
1197
1198 // XXXdbg
1199 if (hfsmp->jnl) {
1200 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1201 }
1202
1203 //
1204 // If the first block to allocate doesn't start on a word
1205 // boundary in the bitmap, then treat that first word
1206 // specially.
1207 //
1208
1209 firstBit = startingBlock % kBitsPerWord;
1210 if (firstBit != 0) {
1211 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit
1212 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word
1213 if (numBits > numBlocks) {
1214 numBits = numBlocks; // entire allocation is inside this one word
1215 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last
1216 }
1217 #if DEBUG_BUILD
1218 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1219 panic("hfs: BlockMarkAllocated: blocks already allocated!");
1220 }
1221 #endif
1222 *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap
1223 numBlocks -= numBits; // adjust number of blocks left to allocate
1224
1225 ++currentWord; // move to next word
1226 --wordsLeft; // one less word left in this block
1227 }
1228
1229 //
1230 // Allocate whole words (32 blocks) at a time.
1231 //
1232
1233 bitMask = kAllBitsSetInWord; // put this in a register for 68K
1234 while (numBlocks >= kBitsPerWord) {
1235 if (wordsLeft == 0) {
1236 // Read in the next bitmap block
1237 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1238
1239 buffer = NULL;
1240 err = ReleaseBitmapBlock(vcb, blockRef, true);
1241 if (err != noErr) goto Exit;
1242
1243 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1244 if (err != noErr) goto Exit;
1245
1246 // XXXdbg
1247 if (hfsmp->jnl) {
1248 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1249 }
1250
1251 // Readjust currentWord and wordsLeft
1252 currentWord = buffer;
1253 wordsLeft = wordsPerBlock;
1254 }
1255 #if DEBUG_BUILD
1256 if (*currentWord != 0) {
1257 panic("hfs: BlockMarkAllocated: blocks already allocated!");
1258 }
1259 #endif
1260 *currentWord = SWAP_BE32 (bitMask);
1261 numBlocks -= kBitsPerWord;
1262
1263 ++currentWord; // move to next word
1264 --wordsLeft; // one less word left in this block
1265 }
1266
1267 //
1268 // Allocate any remaining blocks.
1269 //
1270
1271 if (numBlocks != 0) {
1272 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits
1273 if (wordsLeft == 0) {
1274 // Read in the next bitmap block
1275 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1276
1277 buffer = NULL;
1278 err = ReleaseBitmapBlock(vcb, blockRef, true);
1279 if (err != noErr) goto Exit;
1280
1281 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1282 if (err != noErr) goto Exit;
1283
1284 // XXXdbg
1285 if (hfsmp->jnl) {
1286 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1287 }
1288
1289 // Readjust currentWord and wordsLeft
1290 currentWord = buffer;
1291 wordsLeft = wordsPerBlock;
1292 }
1293 #if DEBUG_BUILD
1294 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1295 panic("hfs: BlockMarkAllocated: blocks already allocated!");
1296 }
1297 #endif
1298 *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap
1299
1300 // No need to update currentWord or wordsLeft
1301 }
1302
1303 Exit:
1304
1305 if (buffer)
1306 (void)ReleaseBitmapBlock(vcb, blockRef, true);
1307
1308 return err;
1309 }
1310
1311
1312 /*
1313 _______________________________________________________________________
1314
1315 Routine: BlockMarkFree
1316
1317 Function: Mark a contiguous group of blocks as free (clear in the
1318 bitmap). It assumes those bits are currently marked
1319 allocated (set in the bitmap).
1320
1321 Inputs:
1322 vcb Pointer to volume where space is to be freed
1323 startingBlock First block number to mark as freed
1324 numBlocks Number of blocks to mark as freed
1325 _______________________________________________________________________
1326 */
1327 __private_extern__
1328 OSErr BlockMarkFree(
1329 ExtendedVCB *vcb,
1330 u_int32_t startingBlock,
1331 register u_int32_t numBlocks)
1332 {
1333 OSErr err;
1334 register u_int32_t *currentWord; // Pointer to current word within bitmap block
1335 register u_int32_t wordsLeft; // Number of words left in this bitmap block
1336 register u_int32_t bitMask; // Word with given bits already set (ready to OR in)
1337 u_int32_t firstBit; // Bit index within word of first bit to allocate
1338 u_int32_t numBits; // Number of bits in word to allocate
1339 u_int32_t *buffer = NULL;
1340 uintptr_t blockRef;
1341 u_int32_t bitsPerBlock;
1342 u_int32_t wordsPerBlock;
1343 // XXXdbg
1344 struct hfsmount *hfsmp = VCBTOHFS(vcb);
1345 dk_discard_t discard;
1346
1347 /*
1348 * NOTE: We use vcb->totalBlocks instead of vcb->allocLimit because we
1349 * need to be able to free blocks being relocated during hfs_truncatefs.
1350 */
1351 if (startingBlock + numBlocks > vcb->totalBlocks) {
1352 printf ("hfs: BlockMarkFree() trying to free non-existent blocks starting at %u (numBlock=%u) on volume %s\n", startingBlock, numBlocks, vcb->vcbVN);
1353 hfs_mark_volume_inconsistent(vcb);
1354 err = EIO;
1355 goto Exit;
1356 }
1357
1358 memset(&discard, 0, sizeof(dk_discard_t));
1359 discard.offset = (uint64_t)startingBlock * (uint64_t)vcb->blockSize;
1360 discard.length = (uint64_t)numBlocks * (uint64_t)vcb->blockSize;
1361
1362
1363 //
1364 // Pre-read the bitmap block containing the first word of allocation
1365 //
1366
1367 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1368 if (err != noErr) goto Exit;
1369 // XXXdbg
1370 if (hfsmp->jnl) {
1371 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1372 }
1373
1374 //
1375 // Initialize currentWord, and wordsLeft.
1376 //
1377 {
1378 u_int32_t wordIndexInBlock;
1379
1380 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
1381 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1382
1383 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
1384 currentWord = buffer + wordIndexInBlock;
1385 wordsLeft = wordsPerBlock - wordIndexInBlock;
1386 }
1387
1388 //
1389 // If the first block to free doesn't start on a word
1390 // boundary in the bitmap, then treat that first word
1391 // specially.
1392 //
1393
1394 firstBit = startingBlock % kBitsPerWord;
1395 if (firstBit != 0) {
1396 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit
1397 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word
1398 if (numBits > numBlocks) {
1399 numBits = numBlocks; // entire allocation is inside this one word
1400 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last
1401 }
1402 if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
1403 goto Corruption;
1404 }
1405 *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap
1406 numBlocks -= numBits; // adjust number of blocks left to free
1407
1408 ++currentWord; // move to next word
1409 --wordsLeft; // one less word left in this block
1410 }
1411
1412 //
1413 // Free whole words (32 blocks) at a time.
1414 //
1415
1416 while (numBlocks >= kBitsPerWord) {
1417 if (wordsLeft == 0) {
1418 // Read in the next bitmap block
1419 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1420
1421 buffer = NULL;
1422 err = ReleaseBitmapBlock(vcb, blockRef, true);
1423 if (err != noErr) goto Exit;
1424
1425 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1426 if (err != noErr) goto Exit;
1427
1428 // XXXdbg
1429 if (hfsmp->jnl) {
1430 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1431 }
1432
1433 // Readjust currentWord and wordsLeft
1434 currentWord = buffer;
1435 wordsLeft = wordsPerBlock;
1436 }
1437 if (*currentWord != SWAP_BE32 (kAllBitsSetInWord)) {
1438 goto Corruption;
1439 }
1440 *currentWord = 0; // clear the entire word
1441 numBlocks -= kBitsPerWord;
1442
1443 ++currentWord; // move to next word
1444 --wordsLeft; // one less word left in this block
1445 }
1446
1447 //
1448 // Free any remaining blocks.
1449 //
1450
1451 if (numBlocks != 0) {
1452 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits
1453 if (wordsLeft == 0) {
1454 // Read in the next bitmap block
1455 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1456
1457 buffer = NULL;
1458 err = ReleaseBitmapBlock(vcb, blockRef, true);
1459 if (err != noErr) goto Exit;
1460
1461 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1462 if (err != noErr) goto Exit;
1463
1464 // XXXdbg
1465 if (hfsmp->jnl) {
1466 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1467 }
1468
1469 // Readjust currentWord and wordsLeft
1470 currentWord = buffer;
1471 wordsLeft = wordsPerBlock;
1472 }
1473 if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
1474 goto Corruption;
1475 }
1476 *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap
1477
1478 // No need to update currentWord or wordsLeft
1479 }
1480
1481 Exit:
1482
1483 if (buffer)
1484 (void)ReleaseBitmapBlock(vcb, blockRef, true);
1485
1486 if (err == noErr) {
1487 // it doesn't matter if this fails, it's just informational anyway
1488 VNOP_IOCTL(vcb->hfs_devvp, DKIOCDISCARD, (caddr_t)&discard, 0, vfs_context_kernel());
1489 }
1490
1491
1492 return err;
1493
1494 Corruption:
1495 #if DEBUG_BUILD
1496 panic("hfs: BlockMarkFree: blocks not allocated!");
1497 #else
1498 printf ("hfs: BlockMarkFree() trying to free unallocated blocks on volume %s\n", vcb->vcbVN);
1499 hfs_mark_volume_inconsistent(vcb);
1500 err = EIO;
1501 goto Exit;
1502 #endif
1503 }
1504
1505
1506 /*
1507 _______________________________________________________________________
1508
1509 Routine: BlockFindContiguous
1510
1511 Function: Find a contiguous range of blocks that are free (bits
1512 clear in the bitmap). If a contiguous range of the
1513 minimum size can't be found, an error will be returned.
1514
1515 Inputs:
1516 vcb Pointer to volume where space is to be allocated
1517 startingBlock Preferred first block of range
1518 endingBlock Last possible block in range + 1
1519 minBlocks Minimum number of blocks needed. Must be > 0.
1520 maxBlocks Maximum (ideal) number of blocks desired
1521 useMetaZone OK to dip into metadata allocation zone
1522
1523 Outputs:
1524 actualStartBlock First block of range found, or 0 if error
1525 actualNumBlocks Number of blocks found, or 0 if error
1526
1527 Returns:
1528 noErr Found at least minBlocks contiguous
1529 dskFulErr No contiguous space found, or all less than minBlocks
1530 _______________________________________________________________________
1531 */
1532
1533 static OSErr BlockFindContiguous(
1534 ExtendedVCB *vcb,
1535 u_int32_t startingBlock,
1536 u_int32_t endingBlock,
1537 u_int32_t minBlocks,
1538 u_int32_t maxBlocks,
1539 Boolean useMetaZone,
1540 u_int32_t *actualStartBlock,
1541 u_int32_t *actualNumBlocks)
1542 {
1543 OSErr err;
1544 register u_int32_t currentBlock; // Block we're currently looking at.
1545 u_int32_t firstBlock; // First free block in current extent.
1546 u_int32_t stopBlock; // If we get to this block, stop searching for first free block.
1547 u_int32_t foundBlocks; // Number of contiguous free blocks in current extent.
1548 u_int32_t *buffer = NULL;
1549 register u_int32_t *currentWord;
1550 register u_int32_t bitMask;
1551 register u_int32_t wordsLeft;
1552 register u_int32_t tempWord;
1553 uintptr_t blockRef;
1554 u_int32_t wordsPerBlock;
1555 u_int32_t j, updated_free_extents = 0, really_add;
1556
1557 /*
1558 * When we're skipping the metadata zone and the start/end
1559 * range overlaps with the metadata zone then adjust the
1560 * start to be outside of the metadata zone. If the range
1561 * is entirely inside the metadata zone then we can deny the
1562 * request (dskFulErr).
1563 */
1564 if (!useMetaZone && (vcb->hfs_flags & HFS_METADATA_ZONE)) {
1565 if (startingBlock <= vcb->hfs_metazone_end) {
1566 if (endingBlock > (vcb->hfs_metazone_end + 2))
1567 startingBlock = vcb->hfs_metazone_end + 1;
1568 else
1569 goto DiskFull;
1570 }
1571 }
1572
1573 if ((endingBlock - startingBlock) < minBlocks)
1574 {
1575 // The set of blocks we're checking is smaller than the minimum number
1576 // of blocks, so we couldn't possibly find a good range.
1577 goto DiskFull;
1578 }
1579
1580 stopBlock = endingBlock - minBlocks + 1;
1581 currentBlock = startingBlock;
1582 firstBlock = 0;
1583
1584 /*
1585 * Skip over metadata blocks.
1586 */
1587 if (!useMetaZone)
1588 currentBlock = NextBitmapBlock(vcb, currentBlock);
1589
1590 //
1591 // Pre-read the first bitmap block.
1592 //
1593 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1594 if ( err != noErr ) goto ErrorExit;
1595
1596 //
1597 // Figure out where currentBlock is within the buffer.
1598 //
1599 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1600
1601 wordsLeft = (currentBlock / kBitsPerWord) & (wordsPerBlock-1); // Current index into buffer
1602 currentWord = buffer + wordsLeft;
1603 wordsLeft = wordsPerBlock - wordsLeft;
1604
1605 do
1606 {
1607 foundBlocks = 0;
1608
1609 //============================================================
1610 // Look for a free block, skipping over allocated blocks.
1611 //============================================================
1612
1613 //
1614 // Check an initial partial word (if any)
1615 //
1616 bitMask = currentBlock & kBitsWithinWordMask;
1617 if (bitMask)
1618 {
1619 tempWord = SWAP_BE32(*currentWord); // Fetch the current word only once
1620 bitMask = kHighBitInWordMask >> bitMask;
1621 while (tempWord & bitMask)
1622 {
1623 bitMask >>= 1;
1624 ++currentBlock;
1625 }
1626
1627 // Did we find an unused bit (bitMask != 0), or run out of bits (bitMask == 0)?
1628 if (bitMask)
1629 goto FoundUnused;
1630
1631 // Didn't find any unused bits, so we're done with this word.
1632 ++currentWord;
1633 --wordsLeft;
1634 }
1635
1636 //
1637 // Check whole words
1638 //
1639 while (currentBlock < stopBlock)
1640 {
1641 // See if it's time to read another block.
1642 if (wordsLeft == 0)
1643 {
1644 buffer = NULL;
1645 err = ReleaseBitmapBlock(vcb, blockRef, false);
1646 if (err != noErr) goto ErrorExit;
1647
1648 /*
1649 * Skip over metadata blocks.
1650 */
1651 if (!useMetaZone) {
1652 currentBlock = NextBitmapBlock(vcb, currentBlock);
1653 if (currentBlock >= stopBlock) {
1654 goto LoopExit;
1655 }
1656 }
1657
1658 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1659 if ( err != noErr ) goto ErrorExit;
1660
1661 currentWord = buffer;
1662 wordsLeft = wordsPerBlock;
1663 }
1664
1665 // See if any of the bits are clear
1666 if ((tempWord = SWAP_BE32(*currentWord)) + 1) // non-zero if any bits were clear
1667 {
1668 // Figure out which bit is clear
1669 bitMask = kHighBitInWordMask;
1670 while (tempWord & bitMask)
1671 {
1672 bitMask >>= 1;
1673 ++currentBlock;
1674 }
1675
1676 break; // Found the free bit; break out to FoundUnused.
1677 }
1678
1679 // Keep looking at the next word
1680 currentBlock += kBitsPerWord;
1681 ++currentWord;
1682 --wordsLeft;
1683 }
1684
1685 FoundUnused:
1686 // Make sure the unused bit is early enough to use
1687 if (currentBlock >= stopBlock)
1688 {
1689 break;
1690 }
1691
1692 // Remember the start of the extent
1693 firstBlock = currentBlock;
1694
1695 //============================================================
1696 // Count the number of contiguous free blocks.
1697 //============================================================
1698
1699 //
1700 // Check an initial partial word (if any)
1701 //
1702 bitMask = currentBlock & kBitsWithinWordMask;
1703 if (bitMask)
1704 {
1705 tempWord = SWAP_BE32(*currentWord); // Fetch the current word only once
1706 bitMask = kHighBitInWordMask >> bitMask;
1707 while (bitMask && !(tempWord & bitMask))
1708 {
1709 bitMask >>= 1;
1710 ++currentBlock;
1711 }
1712
1713 // Did we find a used bit (bitMask != 0), or run out of bits (bitMask == 0)?
1714 if (bitMask)
1715 goto FoundUsed;
1716
1717 // Didn't find any used bits, so we're done with this word.
1718 ++currentWord;
1719 --wordsLeft;
1720 }
1721
1722 //
1723 // Check whole words
1724 //
1725 while (currentBlock < endingBlock)
1726 {
1727 // See if it's time to read another block.
1728 if (wordsLeft == 0)
1729 {
1730 buffer = NULL;
1731 err = ReleaseBitmapBlock(vcb, blockRef, false);
1732 if (err != noErr) goto ErrorExit;
1733
1734 /*
1735 * Skip over metadata blocks.
1736 */
1737 if (!useMetaZone) {
1738 u_int32_t nextBlock;
1739
1740 nextBlock = NextBitmapBlock(vcb, currentBlock);
1741 if (nextBlock != currentBlock) {
1742 goto LoopExit; /* allocation gap, so stop */
1743 }
1744 }
1745
1746 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1747 if ( err != noErr ) goto ErrorExit;
1748
1749 currentWord = buffer;
1750 wordsLeft = wordsPerBlock;
1751 }
1752
1753 // See if any of the bits are set
1754 if ((tempWord = SWAP_BE32(*currentWord)) != 0)
1755 {
1756 // Figure out which bit is set
1757 bitMask = kHighBitInWordMask;
1758 while (!(tempWord & bitMask))
1759 {
1760 bitMask >>= 1;
1761 ++currentBlock;
1762 }
1763
1764 break; // Found the used bit; break out to FoundUsed.
1765 }
1766
1767 // Keep looking at the next word
1768 currentBlock += kBitsPerWord;
1769 ++currentWord;
1770 --wordsLeft;
1771
1772 // If we found at least maxBlocks, we can quit early.
1773 if ((currentBlock - firstBlock) >= maxBlocks)
1774 break;
1775 }
1776
1777 FoundUsed:
1778 // Make sure we didn't run out of bitmap looking for a used block.
1779 // If so, pin to the end of the bitmap.
1780 if (currentBlock > endingBlock)
1781 currentBlock = endingBlock;
1782
1783 // Figure out how many contiguous free blocks there were.
1784 // Pin the answer to maxBlocks.
1785 foundBlocks = currentBlock - firstBlock;
1786 if (foundBlocks > maxBlocks)
1787 foundBlocks = maxBlocks;
1788 if (foundBlocks >= minBlocks)
1789 break; // Found what we needed!
1790
1791 HFS_MOUNT_LOCK(vcb, TRUE);
1792 if (free_extent_cache_active(vcb) == 0) {
1793 HFS_MOUNT_UNLOCK(vcb, TRUE);
1794 goto skip_cache;
1795 }
1796 HFS_MOUNT_UNLOCK(vcb, TRUE);
1797
1798 // This free chunk wasn't big enough. Try inserting it into the free extent cache in case
1799 // the allocation wasn't forced contiguous.
1800 really_add = 0;
1801 for(j=0; j < vcb->vcbFreeExtCnt; j++) {
1802 u_int32_t start, end;
1803
1804 start = vcb->vcbFreeExt[j].startBlock;
1805 end = start + vcb->vcbFreeExt[j].blockCount;
1806
1807 if ( (firstBlock >= start && firstBlock < end)
1808 || ((firstBlock + foundBlocks) > start && firstBlock < start)) {
1809
1810 // there's overlap with an existing entry so do not add this
1811 break;
1812 }
1813
1814 }
1815
1816 if (j >= vcb->vcbFreeExtCnt) {
1817 really_add = 1;
1818 }
1819
1820 tempWord = vcb->vcbFreeExtCnt;
1821 if (really_add && (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE)) {
1822 // Sorted by starting block
1823 if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].startBlock > firstBlock)
1824 --tempWord;
1825 if (tempWord < kMaxFreeExtents)
1826 {
1827 // We're going to add this extent. Bubble any smaller extents down in the list.
1828 while (tempWord && vcb->vcbFreeExt[tempWord-1].startBlock > firstBlock)
1829 {
1830 vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1];
1831 --tempWord;
1832 }
1833 vcb->vcbFreeExt[tempWord].startBlock = firstBlock;
1834 vcb->vcbFreeExt[tempWord].blockCount = foundBlocks;
1835
1836 if (vcb->vcbFreeExtCnt < kMaxFreeExtents) {
1837 ++vcb->vcbFreeExtCnt;
1838 }
1839 updated_free_extents = 1;
1840 }
1841 } else if (really_add) {
1842 // Sorted by blockCount
1843 if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].blockCount < foundBlocks)
1844 --tempWord;
1845 if (tempWord < kMaxFreeExtents)
1846 {
1847 // We're going to add this extent. Bubble any smaller extents down in the list.
1848 while (tempWord && vcb->vcbFreeExt[tempWord-1].blockCount < foundBlocks)
1849 {
1850 vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1];
1851 --tempWord;
1852 }
1853 vcb->vcbFreeExt[tempWord].startBlock = firstBlock;
1854 vcb->vcbFreeExt[tempWord].blockCount = foundBlocks;
1855
1856 if (vcb->vcbFreeExtCnt < kMaxFreeExtents) {
1857 ++vcb->vcbFreeExtCnt;
1858 }
1859 updated_free_extents = 1;
1860 }
1861 }
1862 skip_cache:
1863 sanity_check_free_ext(vcb, 0);
1864
1865 } while (currentBlock < stopBlock);
1866 LoopExit:
1867
1868 // Return the outputs.
1869 if (foundBlocks < minBlocks)
1870 {
1871 DiskFull:
1872 err = dskFulErr;
1873 ErrorExit:
1874 *actualStartBlock = 0;
1875 *actualNumBlocks = 0;
1876 }
1877 else
1878 {
1879 err = noErr;
1880 *actualStartBlock = firstBlock;
1881 *actualNumBlocks = foundBlocks;
1882 /*
1883 * Sanity check for overflow
1884 */
1885 if ((firstBlock + foundBlocks) > vcb->allocLimit) {
1886 panic("hfs: blk allocation overflow on \"%s\" sb:0x%08x eb:0x%08x cb:0x%08x fb:0x%08x stop:0x%08x min:0x%08x found:0x%08x",
1887 vcb->vcbVN, startingBlock, endingBlock, currentBlock,
1888 firstBlock, stopBlock, minBlocks, foundBlocks);
1889 }
1890 }
1891
1892 if (updated_free_extents && (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE)) {
1893 int i;
1894 u_int32_t min_start = vcb->totalBlocks;
1895
1896 // set the nextAllocation pointer to the smallest free block number
1897 // we've seen so on the next mount we won't rescan unnecessarily
1898 for(i=0; i < (int)vcb->vcbFreeExtCnt; i++) {
1899 if (vcb->vcbFreeExt[i].startBlock < min_start) {
1900 min_start = vcb->vcbFreeExt[i].startBlock;
1901 }
1902 }
1903 if (min_start != vcb->totalBlocks) {
1904 if (min_start < vcb->nextAllocation) {
1905 vcb->nextAllocation = min_start;
1906 }
1907 if (min_start < vcb->sparseAllocation) {
1908 vcb->sparseAllocation = min_start;
1909 }
1910 }
1911 }
1912
1913 if (buffer)
1914 (void) ReleaseBitmapBlock(vcb, blockRef, false);
1915
1916 sanity_check_free_ext(vcb, 1);
1917
1918 return err;
1919 }
1920
1921 /*
1922 * Test to see if any blocks in a range are allocated.
1923 *
1924 * The journal or allocation file lock must be held.
1925 */
1926 __private_extern__
1927 int
1928 hfs_isallocated(struct hfsmount *hfsmp, u_int32_t startingBlock, u_int32_t numBlocks)
1929 {
1930 u_int32_t *currentWord; // Pointer to current word within bitmap block
1931 u_int32_t wordsLeft; // Number of words left in this bitmap block
1932 u_int32_t bitMask; // Word with given bits already set (ready to test)
1933 u_int32_t firstBit; // Bit index within word of first bit to allocate
1934 u_int32_t numBits; // Number of bits in word to allocate
1935 u_int32_t *buffer = NULL;
1936 uintptr_t blockRef;
1937 u_int32_t bitsPerBlock;
1938 u_int32_t wordsPerBlock;
1939 int inuse = 0;
1940 int error;
1941
1942 /*
1943 * Pre-read the bitmap block containing the first word of allocation
1944 */
1945 error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef);
1946 if (error)
1947 return (error);
1948
1949 /*
1950 * Initialize currentWord, and wordsLeft.
1951 */
1952 {
1953 u_int32_t wordIndexInBlock;
1954
1955 bitsPerBlock = hfsmp->vcbVBMIOSize * kBitsPerByte;
1956 wordsPerBlock = hfsmp->vcbVBMIOSize / kBytesPerWord;
1957
1958 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
1959 currentWord = buffer + wordIndexInBlock;
1960 wordsLeft = wordsPerBlock - wordIndexInBlock;
1961 }
1962
1963 /*
1964 * First test any non word aligned bits.
1965 */
1966 firstBit = startingBlock % kBitsPerWord;
1967 if (firstBit != 0) {
1968 bitMask = kAllBitsSetInWord >> firstBit;
1969 numBits = kBitsPerWord - firstBit;
1970 if (numBits > numBlocks) {
1971 numBits = numBlocks;
1972 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits));
1973 }
1974 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1975 inuse = 1;
1976 goto Exit;
1977 }
1978 numBlocks -= numBits;
1979 ++currentWord;
1980 --wordsLeft;
1981 }
1982
1983 /*
1984 * Test whole words (32 blocks) at a time.
1985 */
1986 while (numBlocks >= kBitsPerWord) {
1987 if (wordsLeft == 0) {
1988 /* Read in the next bitmap block. */
1989 startingBlock += bitsPerBlock;
1990
1991 buffer = NULL;
1992 error = ReleaseBitmapBlock(hfsmp, blockRef, false);
1993 if (error) goto Exit;
1994
1995 error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef);
1996 if (error) goto Exit;
1997
1998 /* Readjust currentWord and wordsLeft. */
1999 currentWord = buffer;
2000 wordsLeft = wordsPerBlock;
2001 }
2002 if (*currentWord != 0) {
2003 inuse = 1;
2004 goto Exit;
2005 }
2006 numBlocks -= kBitsPerWord;
2007 ++currentWord;
2008 --wordsLeft;
2009 }
2010
2011 /*
2012 * Test any remaining blocks.
2013 */
2014 if (numBlocks != 0) {
2015 bitMask = ~(kAllBitsSetInWord >> numBlocks);
2016 if (wordsLeft == 0) {
2017 /* Read in the next bitmap block */
2018 startingBlock += bitsPerBlock;
2019
2020 buffer = NULL;
2021 error = ReleaseBitmapBlock(hfsmp, blockRef, false);
2022 if (error) goto Exit;
2023
2024 error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef);
2025 if (error) goto Exit;
2026
2027 currentWord = buffer;
2028 wordsLeft = wordsPerBlock;
2029 }
2030 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
2031 inuse = 1;
2032 goto Exit;
2033 }
2034 }
2035 Exit:
2036 if (buffer) {
2037 (void)ReleaseBitmapBlock(hfsmp, blockRef, false);
2038 }
2039 return (inuse);
2040 }
2041
2042 /* Invalidate free extent cache for a given volume.
2043 * This cache is invalidated and disabled when a volume is being resized
2044 * (via hfs_trucatefs() or hfs_extendefs()).
2045 *
2046 * Returns: Nothing
2047 */
2048 void invalidate_free_extent_cache(ExtendedVCB *vcb)
2049 {
2050 u_int32_t i;
2051
2052 HFS_MOUNT_LOCK(vcb, TRUE);
2053 for (i = 0; i < vcb->vcbFreeExtCnt; i++) {
2054 vcb->vcbFreeExt[i].startBlock = 0;
2055 vcb->vcbFreeExt[i].blockCount = 0;
2056 }
2057 vcb->vcbFreeExtCnt = 0;
2058 HFS_MOUNT_UNLOCK(vcb, TRUE);
2059
2060 return;
2061 }
2062
2063 /* Check whether free extent cache is active or not.
2064 * This cache is invalidated and disabled when a volume is being resized
2065 * (via hfs_trucatefs() or hfs_extendefs()).
2066 *
2067 * This function assumes that the caller is holding the lock on
2068 * the mount point.
2069 *
2070 * Returns: 0 if the cache is not active,
2071 * 1 if the cache is active.
2072 */
2073 static int free_extent_cache_active(ExtendedVCB *vcb)
2074 {
2075 int retval = 1;
2076
2077 if (vcb->hfs_flags & HFS_RESIZE_IN_PROGRESS) {
2078 retval = 0;
2079 }
2080 return retval;
2081 }
mirror of XNU