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