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