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