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


c5007ac7f0e6db3c08cf547127768d4149cab03b
[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 UInt32 i;
900 UInt32 foundBlocks;
901 UInt32 newStartBlock, newBlockCount;
902
903 if (vcb->vcbFreeExtCnt == 0)
904 return dskFulErr;
905
906 // Just grab up to maxBlocks of the first (largest) free exent.
907 *actualStartBlock = vcb->vcbFreeExt[0].startBlock;
908 foundBlocks = vcb->vcbFreeExt[0].blockCount;
909 if (foundBlocks > maxBlocks)
910 foundBlocks = maxBlocks;
911 *actualNumBlocks = foundBlocks;
912
913 // Adjust the start and length of that extent.
914 newStartBlock = vcb->vcbFreeExt[0].startBlock + foundBlocks;
915 newBlockCount = vcb->vcbFreeExt[0].blockCount - foundBlocks;
916
917 // The first extent might not be the largest anymore. Bubble up any
918 // (now larger) extents to the top of the list.
919 for (i=1; i<vcb->vcbFreeExtCnt; ++i)
920 {
921 if (vcb->vcbFreeExt[i].blockCount > newBlockCount)
922 {
923 vcb->vcbFreeExt[i-1].startBlock = vcb->vcbFreeExt[i].startBlock;
924 vcb->vcbFreeExt[i-1].blockCount = vcb->vcbFreeExt[i].blockCount;
925 }
926 else
927 {
928 break;
929 }
930 }
931
932 // If this is now the smallest known free extent, then it might be smaller than
933 // other extents we didn't keep track of. So, just forget about this extent.
934 // After the previous loop, (i-1) is the index of the extent we just allocated from.
935 if (i == vcb->vcbFreeExtCnt)
936 {
937 // It's now the smallest extent, so forget about it
938 --vcb->vcbFreeExtCnt;
939 }
940 else
941 {
942 // It's not the smallest, so store it in its proper place
943 vcb->vcbFreeExt[i-1].startBlock = newStartBlock;
944 vcb->vcbFreeExt[i-1].blockCount = newBlockCount;
945 }
946
947 // sanity check
948 if ((*actualStartBlock + *actualNumBlocks) > vcb->totalBlocks)
949 panic("BlockAllocateKnown: allocation overflow on \"%s\"", vcb->vcbVN);
950
951 //
952 // Now mark the found extent in the bitmap
953 //
954 return BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks);
955 }
956
957
958
959 /*
960 _______________________________________________________________________
961
962 Routine: BlockMarkAllocated
963
964 Function: Mark a contiguous group of blocks as allocated (set in the
965 bitmap). It assumes those bits are currently marked
966 deallocated (clear in the bitmap).
967
968 Inputs:
969 vcb Pointer to volume where space is to be allocated
970 startingBlock First block number to mark as allocated
971 numBlocks Number of blocks to mark as allocated
972 _______________________________________________________________________
973 */
974 __private_extern__
975 OSErr BlockMarkAllocated(
976 ExtendedVCB *vcb,
977 UInt32 startingBlock,
978 register UInt32 numBlocks)
979 {
980 OSErr err;
981 register UInt32 *currentWord; // Pointer to current word within bitmap block
982 register UInt32 wordsLeft; // Number of words left in this bitmap block
983 register UInt32 bitMask; // Word with given bits already set (ready to OR in)
984 UInt32 firstBit; // Bit index within word of first bit to allocate
985 UInt32 numBits; // Number of bits in word to allocate
986 UInt32 *buffer = NULL;
987 UInt32 blockRef;
988 UInt32 bitsPerBlock;
989 UInt32 wordsPerBlock;
990 // XXXdbg
991 struct hfsmount *hfsmp = VCBTOHFS(vcb);
992
993
994 //
995 // Pre-read the bitmap block containing the first word of allocation
996 //
997
998 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
999 if (err != noErr) goto Exit;
1000 //
1001 // Initialize currentWord, and wordsLeft.
1002 //
1003 {
1004 UInt32 wordIndexInBlock;
1005
1006 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
1007 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1008
1009 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
1010 currentWord = buffer + wordIndexInBlock;
1011 wordsLeft = wordsPerBlock - wordIndexInBlock;
1012 }
1013
1014 // XXXdbg
1015 if (hfsmp->jnl) {
1016 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1017 }
1018
1019 //
1020 // If the first block to allocate doesn't start on a word
1021 // boundary in the bitmap, then treat that first word
1022 // specially.
1023 //
1024
1025 firstBit = startingBlock % kBitsPerWord;
1026 if (firstBit != 0) {
1027 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit
1028 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word
1029 if (numBits > numBlocks) {
1030 numBits = numBlocks; // entire allocation is inside this one word
1031 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last
1032 }
1033 #if DEBUG_BUILD
1034 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1035 panic("BlockMarkAllocated: blocks already allocated!");
1036 }
1037 #endif
1038 *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap
1039 numBlocks -= numBits; // adjust number of blocks left to allocate
1040
1041 ++currentWord; // move to next word
1042 --wordsLeft; // one less word left in this block
1043 }
1044
1045 //
1046 // Allocate whole words (32 blocks) at a time.
1047 //
1048
1049 bitMask = kAllBitsSetInWord; // put this in a register for 68K
1050 while (numBlocks >= kBitsPerWord) {
1051 if (wordsLeft == 0) {
1052 // Read in the next bitmap block
1053 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1054
1055 buffer = NULL;
1056 err = ReleaseBitmapBlock(vcb, blockRef, true);
1057 if (err != noErr) goto Exit;
1058
1059 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1060 if (err != noErr) goto Exit;
1061
1062 // XXXdbg
1063 if (hfsmp->jnl) {
1064 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1065 }
1066
1067 // Readjust currentWord and wordsLeft
1068 currentWord = buffer;
1069 wordsLeft = wordsPerBlock;
1070 }
1071 #if DEBUG_BUILD
1072 if (*currentWord != 0) {
1073 panic("BlockMarkAllocated: blocks already allocated!");
1074 }
1075 #endif
1076 *currentWord = SWAP_BE32 (bitMask);
1077 numBlocks -= kBitsPerWord;
1078
1079 ++currentWord; // move to next word
1080 --wordsLeft; // one less word left in this block
1081 }
1082
1083 //
1084 // Allocate any remaining blocks.
1085 //
1086
1087 if (numBlocks != 0) {
1088 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits
1089 if (wordsLeft == 0) {
1090 // Read in the next bitmap block
1091 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1092
1093 buffer = NULL;
1094 err = ReleaseBitmapBlock(vcb, blockRef, true);
1095 if (err != noErr) goto Exit;
1096
1097 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1098 if (err != noErr) goto Exit;
1099
1100 // XXXdbg
1101 if (hfsmp->jnl) {
1102 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1103 }
1104
1105 // Readjust currentWord and wordsLeft
1106 currentWord = buffer;
1107 wordsLeft = wordsPerBlock;
1108 }
1109 #if DEBUG_BUILD
1110 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1111 panic("BlockMarkAllocated: blocks already allocated!");
1112 }
1113 #endif
1114 *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap
1115
1116 // No need to update currentWord or wordsLeft
1117 }
1118
1119 Exit:
1120
1121 if (buffer)
1122 (void)ReleaseBitmapBlock(vcb, blockRef, true);
1123
1124 return err;
1125 }
1126
1127
1128 /*
1129 _______________________________________________________________________
1130
1131 Routine: BlockMarkFree
1132
1133 Function: Mark a contiguous group of blocks as free (clear in the
1134 bitmap). It assumes those bits are currently marked
1135 allocated (set in the bitmap).
1136
1137 Inputs:
1138 vcb Pointer to volume where space is to be freed
1139 startingBlock First block number to mark as freed
1140 numBlocks Number of blocks to mark as freed
1141 _______________________________________________________________________
1142 */
1143 __private_extern__
1144 OSErr BlockMarkFree(
1145 ExtendedVCB *vcb,
1146 UInt32 startingBlock,
1147 register UInt32 numBlocks)
1148 {
1149 OSErr err;
1150 register UInt32 *currentWord; // Pointer to current word within bitmap block
1151 register UInt32 wordsLeft; // Number of words left in this bitmap block
1152 register UInt32 bitMask; // Word with given bits already set (ready to OR in)
1153 UInt32 firstBit; // Bit index within word of first bit to allocate
1154 UInt32 numBits; // Number of bits in word to allocate
1155 UInt32 *buffer = NULL;
1156 UInt32 blockRef;
1157 UInt32 bitsPerBlock;
1158 UInt32 wordsPerBlock;
1159 // XXXdbg
1160 struct hfsmount *hfsmp = VCBTOHFS(vcb);
1161
1162 if (startingBlock + numBlocks > vcb->totalBlocks) {
1163 panic("hfs: block mark free: trying to free non-existent blocks (%d %d %d)\n",
1164 startingBlock, numBlocks, vcb->totalBlocks);
1165 }
1166
1167
1168 //
1169 // Pre-read the bitmap block containing the first word of allocation
1170 //
1171
1172 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1173 if (err != noErr) goto Exit;
1174 // XXXdbg
1175 if (hfsmp->jnl) {
1176 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1177 }
1178
1179 //
1180 // Initialize currentWord, and wordsLeft.
1181 //
1182 {
1183 UInt32 wordIndexInBlock;
1184
1185 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
1186 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1187
1188 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
1189 currentWord = buffer + wordIndexInBlock;
1190 wordsLeft = wordsPerBlock - wordIndexInBlock;
1191 }
1192
1193 //
1194 // If the first block to free doesn't start on a word
1195 // boundary in the bitmap, then treat that first word
1196 // specially.
1197 //
1198
1199 firstBit = startingBlock % kBitsPerWord;
1200 if (firstBit != 0) {
1201 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit
1202 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word
1203 if (numBits > numBlocks) {
1204 numBits = numBlocks; // entire allocation is inside this one word
1205 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last
1206 }
1207 if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
1208 goto Corruption;
1209 }
1210 *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap
1211 numBlocks -= numBits; // adjust number of blocks left to free
1212
1213 ++currentWord; // move to next word
1214 --wordsLeft; // one less word left in this block
1215 }
1216
1217 //
1218 // Free whole words (32 blocks) at a time.
1219 //
1220
1221 while (numBlocks >= kBitsPerWord) {
1222 if (wordsLeft == 0) {
1223 // Read in the next bitmap block
1224 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1225
1226 buffer = NULL;
1227 err = ReleaseBitmapBlock(vcb, blockRef, true);
1228 if (err != noErr) goto Exit;
1229
1230 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1231 if (err != noErr) goto Exit;
1232
1233 // XXXdbg
1234 if (hfsmp->jnl) {
1235 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1236 }
1237
1238 // Readjust currentWord and wordsLeft
1239 currentWord = buffer;
1240 wordsLeft = wordsPerBlock;
1241 }
1242 if (*currentWord != SWAP_BE32 (kAllBitsSetInWord)) {
1243 goto Corruption;
1244 }
1245 *currentWord = 0; // clear the entire word
1246 numBlocks -= kBitsPerWord;
1247
1248 ++currentWord; // move to next word
1249 --wordsLeft; // one less word left in this block
1250 }
1251
1252 //
1253 // Free any remaining blocks.
1254 //
1255
1256 if (numBlocks != 0) {
1257 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits
1258 if (wordsLeft == 0) {
1259 // Read in the next bitmap block
1260 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1261
1262 buffer = NULL;
1263 err = ReleaseBitmapBlock(vcb, blockRef, true);
1264 if (err != noErr) goto Exit;
1265
1266 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1267 if (err != noErr) goto Exit;
1268
1269 // XXXdbg
1270 if (hfsmp->jnl) {
1271 journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
1272 }
1273
1274 // Readjust currentWord and wordsLeft
1275 currentWord = buffer;
1276 wordsLeft = wordsPerBlock;
1277 }
1278 if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
1279 goto Corruption;
1280 }
1281 *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap
1282
1283 // No need to update currentWord or wordsLeft
1284 }
1285
1286 Exit:
1287
1288 if (buffer)
1289 (void)ReleaseBitmapBlock(vcb, blockRef, true);
1290
1291 return err;
1292
1293 Corruption:
1294 #if DEBUG_BUILD
1295 panic("BlockMarkFree: blocks not allocated!");
1296 #else
1297 printf("hfs: WARNING - blocks on volume %s not allocated!\n", vcb->vcbVN);
1298 vcb->vcbAtrb |= kHFSVolumeInconsistentMask;
1299 MarkVCBDirty(vcb);
1300 err = EIO;
1301 goto Exit;
1302 #endif
1303 }
1304
1305
1306 /*
1307 _______________________________________________________________________
1308
1309 Routine: BlockFindContiguous
1310
1311 Function: Find a contiguous range of blocks that are free (bits
1312 clear in the bitmap). If a contiguous range of the
1313 minimum size can't be found, an error will be returned.
1314
1315 Inputs:
1316 vcb Pointer to volume where space is to be allocated
1317 startingBlock Preferred first block of range
1318 endingBlock Last possible block in range + 1
1319 minBlocks Minimum number of blocks needed. Must be > 0.
1320 maxBlocks Maximum (ideal) number of blocks desired
1321 useMetaZone OK to dip into metadata allocation zone
1322
1323 Outputs:
1324 actualStartBlock First block of range found, or 0 if error
1325 actualNumBlocks Number of blocks found, or 0 if error
1326
1327 Returns:
1328 noErr Found at least minBlocks contiguous
1329 dskFulErr No contiguous space found, or all less than minBlocks
1330 _______________________________________________________________________
1331 */
1332
1333 static OSErr BlockFindContiguous(
1334 ExtendedVCB *vcb,
1335 UInt32 startingBlock,
1336 UInt32 endingBlock,
1337 UInt32 minBlocks,
1338 UInt32 maxBlocks,
1339 Boolean useMetaZone,
1340 UInt32 *actualStartBlock,
1341 UInt32 *actualNumBlocks)
1342 {
1343 OSErr err;
1344 register UInt32 currentBlock; // Block we're currently looking at.
1345 UInt32 firstBlock; // First free block in current extent.
1346 UInt32 stopBlock; // If we get to this block, stop searching for first free block.
1347 UInt32 foundBlocks; // Number of contiguous free blocks in current extent.
1348 UInt32 *buffer = NULL;
1349 register UInt32 *currentWord;
1350 register UInt32 bitMask;
1351 register UInt32 wordsLeft;
1352 register UInt32 tempWord;
1353 UInt32 blockRef;
1354 UInt32 wordsPerBlock;
1355
1356 /*
1357 * When we're skipping the metadata zone and the start/end
1358 * range overlaps with the metadata zone then adjust the
1359 * start to be outside of the metadata zone. If the range
1360 * is entirely inside the metadata zone then we can deny the
1361 * request (dskFulErr).
1362 */
1363 if (!useMetaZone && (vcb->hfs_flags & HFS_METADATA_ZONE)) {
1364 if (startingBlock <= vcb->hfs_metazone_end) {
1365 if (endingBlock > (vcb->hfs_metazone_end + 2))
1366 startingBlock = vcb->hfs_metazone_end + 1;
1367 else
1368 goto DiskFull;
1369 }
1370 }
1371
1372 if ((endingBlock - startingBlock) < minBlocks)
1373 {
1374 // The set of blocks we're checking is smaller than the minimum number
1375 // of blocks, so we couldn't possibly find a good range.
1376 goto DiskFull;
1377 }
1378
1379 stopBlock = endingBlock - minBlocks + 1;
1380 currentBlock = startingBlock;
1381 firstBlock = 0;
1382
1383 /*
1384 * Skip over metadata blocks.
1385 */
1386 if (!useMetaZone)
1387 currentBlock = NextBitmapBlock(vcb, currentBlock);
1388
1389 //
1390 // Pre-read the first bitmap block.
1391 //
1392 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1393 if ( err != noErr ) goto ErrorExit;
1394
1395 //
1396 // Figure out where currentBlock is within the buffer.
1397 //
1398 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1399
1400 wordsLeft = (currentBlock / kBitsPerWord) & (wordsPerBlock-1); // Current index into buffer
1401 currentWord = buffer + wordsLeft;
1402 wordsLeft = wordsPerBlock - wordsLeft;
1403
1404 do
1405 {
1406 foundBlocks = 0;
1407
1408 //============================================================
1409 // Look for a free block, skipping over allocated blocks.
1410 //============================================================
1411
1412 //
1413 // Check an initial partial word (if any)
1414 //
1415 bitMask = currentBlock & kBitsWithinWordMask;
1416 if (bitMask)
1417 {
1418 tempWord = SWAP_BE32(*currentWord); // Fetch the current word only once
1419 bitMask = kHighBitInWordMask >> bitMask;
1420 while (tempWord & bitMask)
1421 {
1422 bitMask >>= 1;
1423 ++currentBlock;
1424 }
1425
1426 // Did we find an unused bit (bitMask != 0), or run out of bits (bitMask == 0)?
1427 if (bitMask)
1428 goto FoundUnused;
1429
1430 // Didn't find any unused bits, so we're done with this word.
1431 ++currentWord;
1432 --wordsLeft;
1433 }
1434
1435 //
1436 // Check whole words
1437 //
1438 while (currentBlock < stopBlock)
1439 {
1440 // See if it's time to read another block.
1441 if (wordsLeft == 0)
1442 {
1443 buffer = NULL;
1444 err = ReleaseBitmapBlock(vcb, blockRef, false);
1445 if (err != noErr) goto ErrorExit;
1446
1447 /*
1448 * Skip over metadata blocks.
1449 */
1450 if (!useMetaZone) {
1451 currentBlock = NextBitmapBlock(vcb, currentBlock);
1452 if (currentBlock >= stopBlock) {
1453 goto LoopExit;
1454 }
1455 }
1456
1457 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1458 if ( err != noErr ) goto ErrorExit;
1459
1460 currentWord = buffer;
1461 wordsLeft = wordsPerBlock;
1462 }
1463
1464 // See if any of the bits are clear
1465 if ((tempWord = SWAP_BE32(*currentWord)) + 1) // non-zero if any bits were clear
1466 {
1467 // Figure out which bit is clear
1468 bitMask = kHighBitInWordMask;
1469 while (tempWord & bitMask)
1470 {
1471 bitMask >>= 1;
1472 ++currentBlock;
1473 }
1474
1475 break; // Found the free bit; break out to FoundUnused.
1476 }
1477
1478 // Keep looking at the next word
1479 currentBlock += kBitsPerWord;
1480 ++currentWord;
1481 --wordsLeft;
1482 }
1483
1484 FoundUnused:
1485 // Make sure the unused bit is early enough to use
1486 if (currentBlock >= stopBlock)
1487 {
1488 break;
1489 }
1490
1491 // Remember the start of the extent
1492 firstBlock = currentBlock;
1493
1494 //============================================================
1495 // Count the number of contiguous free blocks.
1496 //============================================================
1497
1498 //
1499 // Check an initial partial word (if any)
1500 //
1501 bitMask = currentBlock & kBitsWithinWordMask;
1502 if (bitMask)
1503 {
1504 tempWord = SWAP_BE32(*currentWord); // Fetch the current word only once
1505 bitMask = kHighBitInWordMask >> bitMask;
1506 while (bitMask && !(tempWord & bitMask))
1507 {
1508 bitMask >>= 1;
1509 ++currentBlock;
1510 }
1511
1512 // Did we find a used bit (bitMask != 0), or run out of bits (bitMask == 0)?
1513 if (bitMask)
1514 goto FoundUsed;
1515
1516 // Didn't find any used bits, so we're done with this word.
1517 ++currentWord;
1518 --wordsLeft;
1519 }
1520
1521 //
1522 // Check whole words
1523 //
1524 while (currentBlock < endingBlock)
1525 {
1526 // See if it's time to read another block.
1527 if (wordsLeft == 0)
1528 {
1529 buffer = NULL;
1530 err = ReleaseBitmapBlock(vcb, blockRef, false);
1531 if (err != noErr) goto ErrorExit;
1532
1533 /*
1534 * Skip over metadata blocks.
1535 */
1536 if (!useMetaZone) {
1537 UInt32 nextBlock;
1538
1539 nextBlock = NextBitmapBlock(vcb, currentBlock);
1540 if (nextBlock != currentBlock) {
1541 goto LoopExit; /* allocation gap, so stop */
1542 }
1543 }
1544
1545 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1546 if ( err != noErr ) goto ErrorExit;
1547
1548 currentWord = buffer;
1549 wordsLeft = wordsPerBlock;
1550 }
1551
1552 // See if any of the bits are set
1553 if ((tempWord = SWAP_BE32(*currentWord)) != 0)
1554 {
1555 // Figure out which bit is set
1556 bitMask = kHighBitInWordMask;
1557 while (!(tempWord & bitMask))
1558 {
1559 bitMask >>= 1;
1560 ++currentBlock;
1561 }
1562
1563 break; // Found the used bit; break out to FoundUsed.
1564 }
1565
1566 // Keep looking at the next word
1567 currentBlock += kBitsPerWord;
1568 ++currentWord;
1569 --wordsLeft;
1570
1571 // If we found at least maxBlocks, we can quit early.
1572 if ((currentBlock - firstBlock) >= maxBlocks)
1573 break;
1574 }
1575
1576 FoundUsed:
1577 // Make sure we didn't run out of bitmap looking for a used block.
1578 // If so, pin to the end of the bitmap.
1579 if (currentBlock > endingBlock)
1580 currentBlock = endingBlock;
1581
1582 // Figure out how many contiguous free blocks there were.
1583 // Pin the answer to maxBlocks.
1584 foundBlocks = currentBlock - firstBlock;
1585 if (foundBlocks > maxBlocks)
1586 foundBlocks = maxBlocks;
1587 if (foundBlocks >= minBlocks)
1588 break; // Found what we needed!
1589
1590 // This free chunk wasn't big enough. Try inserting it into the free extent cache in case
1591 // the allocation wasn't forced contiguous.
1592 tempWord = vcb->vcbFreeExtCnt;
1593 if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].blockCount < foundBlocks)
1594 --tempWord;
1595 if (tempWord < kMaxFreeExtents)
1596 {
1597 // We're going to add this extent. Bubble any smaller extents down in the list.
1598 while (tempWord && vcb->vcbFreeExt[tempWord-1].blockCount < foundBlocks)
1599 {
1600 vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1];
1601 --tempWord;
1602 }
1603 vcb->vcbFreeExt[tempWord].startBlock = firstBlock;
1604 vcb->vcbFreeExt[tempWord].blockCount = foundBlocks;
1605
1606 if (vcb->vcbFreeExtCnt < kMaxFreeExtents)
1607 ++vcb->vcbFreeExtCnt;
1608 }
1609 } while (currentBlock < stopBlock);
1610 LoopExit:
1611
1612 // Return the outputs.
1613 if (foundBlocks < minBlocks)
1614 {
1615 DiskFull:
1616 err = dskFulErr;
1617 ErrorExit:
1618 *actualStartBlock = 0;
1619 *actualNumBlocks = 0;
1620 }
1621 else
1622 {
1623 err = noErr;
1624 *actualStartBlock = firstBlock;
1625 *actualNumBlocks = foundBlocks;
1626 }
1627
1628 if (buffer)
1629 (void) ReleaseBitmapBlock(vcb, blockRef, false);
1630
1631 return err;
1632 }
1633
1634 /*
1635 * Test to see if any blocks in a range are allocated.
1636 *
1637 * The journal or allocation file lock must be held.
1638 */
1639 __private_extern__
1640 int
1641 hfs_isallocated(struct hfsmount *hfsmp, u_long startingBlock, u_long numBlocks)
1642 {
1643 UInt32 *currentWord; // Pointer to current word within bitmap block
1644 UInt32 wordsLeft; // Number of words left in this bitmap block
1645 UInt32 bitMask; // Word with given bits already set (ready to test)
1646 UInt32 firstBit; // Bit index within word of first bit to allocate
1647 UInt32 numBits; // Number of bits in word to allocate
1648 UInt32 *buffer = NULL;
1649 UInt32 blockRef;
1650 UInt32 bitsPerBlock;
1651 UInt32 wordsPerBlock;
1652 int inuse = 0;
1653 int error;
1654
1655 /*
1656 * Pre-read the bitmap block containing the first word of allocation
1657 */
1658 error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef);
1659 if (error)
1660 return (error);
1661
1662 /*
1663 * Initialize currentWord, and wordsLeft.
1664 */
1665 {
1666 UInt32 wordIndexInBlock;
1667
1668 bitsPerBlock = hfsmp->vcbVBMIOSize * kBitsPerByte;
1669 wordsPerBlock = hfsmp->vcbVBMIOSize / kBytesPerWord;
1670
1671 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
1672 currentWord = buffer + wordIndexInBlock;
1673 wordsLeft = wordsPerBlock - wordIndexInBlock;
1674 }
1675
1676 /*
1677 * First test any non word aligned bits.
1678 */
1679 firstBit = startingBlock % kBitsPerWord;
1680 if (firstBit != 0) {
1681 bitMask = kAllBitsSetInWord >> firstBit;
1682 numBits = kBitsPerWord - firstBit;
1683 if (numBits > numBlocks) {
1684 numBits = numBlocks;
1685 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits));
1686 }
1687 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1688 inuse = 1;
1689 goto Exit;
1690 }
1691 numBlocks -= numBits;
1692 ++currentWord;
1693 --wordsLeft;
1694 }
1695
1696 /*
1697 * Test whole words (32 blocks) at a time.
1698 */
1699 while (numBlocks >= kBitsPerWord) {
1700 if (wordsLeft == 0) {
1701 /* Read in the next bitmap block. */
1702 startingBlock += bitsPerBlock;
1703
1704 buffer = NULL;
1705 error = ReleaseBitmapBlock(hfsmp, blockRef, false);
1706 if (error) goto Exit;
1707
1708 error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef);
1709 if (error) goto Exit;
1710
1711 /* Readjust currentWord and wordsLeft. */
1712 currentWord = buffer;
1713 wordsLeft = wordsPerBlock;
1714 }
1715 if (*currentWord != 0) {
1716 inuse = 1;
1717 goto Exit;
1718 }
1719 numBlocks -= kBitsPerWord;
1720 ++currentWord;
1721 --wordsLeft;
1722 }
1723
1724 /*
1725 * Test any remaining blocks.
1726 */
1727 if (numBlocks != 0) {
1728 bitMask = ~(kAllBitsSetInWord >> numBlocks);
1729 if (wordsLeft == 0) {
1730 /* Read in the next bitmap block */
1731 startingBlock += bitsPerBlock;
1732
1733 buffer = NULL;
1734 error = ReleaseBitmapBlock(hfsmp, blockRef, false);
1735 if (error) goto Exit;
1736
1737 error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef);
1738 if (error) goto Exit;
1739
1740 currentWord = buffer;
1741 wordsLeft = wordsPerBlock;
1742 }
1743 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1744 inuse = 1;
1745 goto Exit;
1746 }
1747 }
1748 Exit:
1749 if (buffer) {
1750 (void)ReleaseBitmapBlock(hfsmp, blockRef, false);
1751 }
1752 return (inuse);
1753 }
1754
1755
mirror of XNU