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