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


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