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