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