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


ae4fccf6f0bc38097538ef81945c4e331d1303b6
[apple/xnu.git] / bsd / hfs / hfscommon / Misc / VolumeAllocation.c
1 /*
2 * Copyright (c) 2000-2002 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 UInt32 *actualStartBlock,
122 UInt32 *actualNumBlocks);
123
124 static OSErr BlockAllocateContig(
125 ExtendedVCB *vcb,
126 UInt32 startingBlock,
127 UInt32 minBlocks,
128 UInt32 maxBlocks,
129 UInt32 *actualStartBlock,
130 UInt32 *actualNumBlocks);
131
132 static OSErr BlockFindContiguous(
133 ExtendedVCB *vcb,
134 UInt32 startingBlock,
135 UInt32 endingBlock,
136 UInt32 minBlocks,
137 UInt32 maxBlocks,
138 UInt32 *actualStartBlock,
139 UInt32 *actualNumBlocks);
140
141 static OSErr BlockMarkAllocated(
142 ExtendedVCB *vcb,
143 UInt32 startingBlock,
144 UInt32 numBlocks);
145
146 static OSErr BlockMarkFree(
147 ExtendedVCB *vcb,
148 UInt32 startingBlock,
149 UInt32 numBlocks);
150
151 static OSErr BlockAllocateKnown(
152 ExtendedVCB *vcb,
153 UInt32 maxBlocks,
154 UInt32 *actualStartBlock,
155 UInt32 *actualNumBlocks);
156
157
158 /*
159 ;________________________________________________________________________________
160 ;
161 ; Routine: BlkAlloc
162 ;
163 ; Function: Allocate space on a volume. If contiguous allocation is requested,
164 ; at least the requested number of bytes will be allocated or an
165 ; error will be returned. If contiguous allocation is not forced,
166 ; the space will be allocated at the first free fragment following
167 ; the requested starting allocation block. If there is not enough
168 ; room there, a block of less than the requested size will be
169 ; allocated.
170 ;
171 ; If the requested starting block is 0 (for new file allocations),
172 ; the volume's allocation block pointer will be used as a starting
173 ; point.
174 ;
175 ; All requests will be rounded up to the next highest clump size, as
176 ; indicated in the file's FCB.
177 ;
178 ; Input Arguments:
179 ; vcb - Pointer to ExtendedVCB for the volume to allocate space on
180 ; fcb - Pointer to FCB for the file for which storage is being allocated
181 ; startingBlock - Preferred starting allocation block, 0 = no preference
182 ; forceContiguous - Force contiguous flag - if bit 0 set (NE), allocation is contiguous
183 ; or an error is returned
184 ; bytesRequested - Number of bytes requested. If the allocation is non-contiguous,
185 ; less than this may actually be allocated
186 ; bytesMaximum - The maximum number of bytes to allocate. If there is additional free
187 ; space after bytesRequested, then up to bytesMaximum bytes should really
188 ; be allocated. (Used by ExtendFileC to round up allocations to a multiple
189 ; of the file's clump size.)
190 ;
191 ; Output:
192 ; (result) - Error code, zero for successful allocation
193 ; *startBlock - Actual starting allocation block
194 ; *actualBlocks - Actual number of allocation blocks allocated
195 ;
196 ; Side effects:
197 ; The volume bitmap is read and updated; the volume bitmap cache may be changed.
198 ;________________________________________________________________________________
199 */
200
201 OSErr BlockAllocate (
202 ExtendedVCB *vcb, /* which volume to allocate space on */
203 UInt32 startingBlock, /* preferred starting block, or 0 for no preference */
204 SInt64 bytesRequested, /* desired number of BYTES to allocate */
205 SInt64 bytesMaximum, /* maximum number of bytes to allocate */
206 Boolean forceContiguous, /* non-zero to force contiguous allocation and to force */
207 /* bytesRequested bytes to actually be allocated */
208 UInt32 *actualStartBlock, /* actual first block of allocation */
209 UInt32 *actualNumBlocks) /* number of blocks actually allocated; if forceContiguous */
210 /* was zero, then this may represent fewer than bytesRequested */
211 /* bytes */
212 {
213 OSErr err;
214 UInt32 minBlocks; // minimum number of allocation blocks requested
215 UInt32 maxBlocks; // number of allocation blocks requested, rounded to clump size
216 Boolean updateAllocPtr = false; // true if nextAllocation needs to be updated
217
218 //
219 // Initialize outputs in case we get an error
220 //
221 *actualStartBlock = 0;
222 *actualNumBlocks = 0;
223
224 //
225 // Compute the number of allocation blocks requested, and maximum
226 //
227 minBlocks = FileBytesToBlocks(bytesRequested, vcb->blockSize);
228 maxBlocks = FileBytesToBlocks(bytesMaximum, vcb->blockSize);
229
230 //
231 // If the disk is already full, don't bother.
232 //
233 if (hfs_freeblks(VCBTOHFS(vcb), 0) == 0) {
234 err = dskFulErr;
235 goto Exit;
236 }
237 if (forceContiguous && hfs_freeblks(VCBTOHFS(vcb), 0) < minBlocks) {
238 err = dskFulErr;
239 goto Exit;
240 }
241
242 //
243 // If caller didn't specify a starting block number, then use the volume's
244 // next block to allocate from.
245 //
246 if (startingBlock == 0) {
247 VCB_LOCK(vcb);
248 startingBlock = vcb->nextAllocation;
249 VCB_UNLOCK(vcb);
250 updateAllocPtr = true;
251 }
252
253 //
254 // If the request must be contiguous, then find a sequence of free blocks
255 // that is long enough. Otherwise, find the first free block.
256 //
257 if (forceContiguous) {
258 err = BlockAllocateContig(vcb, startingBlock, minBlocks, maxBlocks, actualStartBlock, actualNumBlocks);
259 /*
260 * If we allocated from a new position then
261 * also update the roving allocatior.
262 */
263 if ((err == noErr) && (*actualStartBlock > startingBlock))
264 vcb->nextAllocation = *actualStartBlock;
265 } else {
266 /*
267 * Scan the bitmap once, gather the N largest free extents, then
268 * allocate from these largest extents. Repeat as needed until
269 * we get all the space we needed. We could probably build up
270 * that list when the higher level caller tried (and failed) a
271 * contiguous allocation first.
272 */
273 err = BlockAllocateKnown(vcb, maxBlocks, actualStartBlock, actualNumBlocks);
274 if (err == dskFulErr)
275 err = BlockAllocateAny(vcb, startingBlock, vcb->totalBlocks, maxBlocks, actualStartBlock, actualNumBlocks);
276 if (err == dskFulErr)
277 err = BlockAllocateAny(vcb, 0, startingBlock, maxBlocks, actualStartBlock, actualNumBlocks);
278 }
279
280 if (err == noErr) {
281 //
282 // If we used the volume's roving allocation pointer, then we need to update it.
283 // Adding in the length of the current allocation might reduce the next allocate
284 // call by avoiding a re-scan of the already allocated space. However, the clump
285 // just allocated can quite conceivably end up being truncated or released when
286 // the file is closed or its EOF changed. Leaving the allocation pointer at the
287 // start of the last allocation will avoid unnecessary fragmentation in this case.
288 //
289 VCB_LOCK(vcb);
290
291 if (updateAllocPtr)
292 vcb->nextAllocation = *actualStartBlock;
293
294 //
295 // Update the number of free blocks on the volume
296 //
297 vcb->freeBlocks -= *actualNumBlocks;
298 VCB_UNLOCK(vcb);
299
300 MarkVCBDirty(vcb);
301 }
302
303 Exit:
304
305 return err;
306 }
307
308
309 /*
310 ;________________________________________________________________________________
311 ;
312 ; Routine: BlkDealloc
313 ;
314 ; Function: Update the bitmap to deallocate a run of disk allocation blocks
315 ;
316 ; Input Arguments:
317 ; vcb - Pointer to ExtendedVCB for the volume to free space on
318 ; firstBlock - First allocation block to be freed
319 ; numBlocks - Number of allocation blocks to free up (must be > 0!)
320 ;
321 ; Output:
322 ; (result) - Result code
323 ;
324 ; Side effects:
325 ; The volume bitmap is read and updated; the volume bitmap cache may be changed.
326 ;________________________________________________________________________________
327 */
328
329 OSErr BlockDeallocate (
330 ExtendedVCB *vcb, // Which volume to deallocate space on
331 UInt32 firstBlock, // First block in range to deallocate
332 UInt32 numBlocks) // Number of contiguous blocks to deallocate
333 {
334 OSErr err;
335
336 //
337 // If no blocks to deallocate, then exit early
338 //
339 if (numBlocks == 0) {
340 err = noErr;
341 goto Exit;
342 }
343
344 //
345 // Call internal routine to free the sequence of blocks
346 //
347 err = BlockMarkFree(vcb, firstBlock, numBlocks);
348 if (err)
349 goto Exit;
350
351 //
352 // Update the volume's free block count, and mark the VCB as dirty.
353 //
354 VCB_LOCK(vcb);
355 vcb->freeBlocks += numBlocks;
356 if (vcb->nextAllocation == (firstBlock + numBlocks))
357 vcb->nextAllocation -= numBlocks;
358 VCB_UNLOCK(vcb);
359 MarkVCBDirty(vcb);
360
361 Exit:
362
363 return err;
364 }
365
366
367 /*
368 ;_______________________________________________________________________
369 ;
370 ; Routine: FileBytesToBlocks
371 ;
372 ; Function: Divide numerator by denominator, rounding up the result if there
373 ; was a remainder. This is frequently used for computing the number
374 ; of whole and/or partial blocks used by some count of bytes.
375 ; Actuall divides a 64 bit by a 32 bit into a 32bit result
376 ;
377 ; CAREFULL!!! THIS CAN CAUSE OVERFLOW....USER BEWARE!!!
378 ;_______________________________________________________________________
379 */
380 UInt32 FileBytesToBlocks(
381 SInt64 numerator,
382 UInt32 denominator)
383 {
384 UInt32 quotient;
385
386 quotient = (UInt32)(numerator / denominator);
387 if (quotient * denominator != numerator)
388 quotient++;
389
390 return quotient;
391 }
392
393
394
395 /*
396 ;_______________________________________________________________________
397 ;
398 ; Routine: ReadBitmapBlock
399 ;
400 ; Function: Read in a bitmap block corresponding to a given allocation
401 ; block (bit). Return a pointer to the bitmap block.
402 ;
403 ; Inputs:
404 ; vcb -- Pointer to ExtendedVCB
405 ; bit -- Allocation block whose bitmap block is desired
406 ;
407 ; Outputs:
408 ; buffer -- Pointer to bitmap block corresonding to "block"
409 ; blockRef
410 ;_______________________________________________________________________
411 */
412 static OSErr ReadBitmapBlock(
413 ExtendedVCB *vcb,
414 UInt32 bit,
415 UInt32 **buffer,
416 UInt32 *blockRef)
417 {
418 OSErr err;
419 struct buf *bp = NULL;
420 struct vnode *vp = NULL;
421 UInt32 block;
422 UInt32 blockSize;
423
424 /*
425 * volume bitmap blocks are protected by the Extents B-tree lock
426 */
427 REQUIRE_FILE_LOCK(vcb->extentsRefNum, false);
428
429 blockSize = (UInt32)vcb->vcbVBMIOSize;
430 block = bit / (blockSize * kBitsPerByte);
431
432 if (vcb->vcbSigWord == kHFSPlusSigWord) {
433 vp = vcb->allocationsRefNum; /* use allocation file vnode */
434
435 } else /* hfs */ {
436 vp = VCBTOHFS(vcb)->hfs_devvp; /* use device I/O vnode */
437 block += vcb->vcbVBMSt; /* map to physical block */
438 }
439
440 err = meta_bread(vp, block, blockSize, NOCRED, &bp);
441
442 if (bp) {
443 if (err) {
444 brelse(bp);
445 *blockRef = NULL;
446 *buffer = NULL;
447 } else {
448 *blockRef = (UInt32)bp;
449 *buffer = (UInt32 *)bp->b_data;
450 }
451 }
452
453 return err;
454 }
455
456
457 /*
458 ;_______________________________________________________________________
459 ;
460 ; Routine: ReleaseBitmapBlock
461 ;
462 ; Function: Relase a bitmap block.
463 ;
464 ; Inputs:
465 ; vcb
466 ; blockRef
467 ; dirty
468 ;_______________________________________________________________________
469 */
470 static OSErr ReleaseBitmapBlock(
471 ExtendedVCB *vcb,
472 UInt32 blockRef,
473 Boolean dirty)
474 {
475 struct buf *bp = (struct buf *)blockRef;
476
477 if (bp) {
478 if (dirty) {
479 bdwrite(bp);
480 } else {
481 brelse(bp);
482 }
483 }
484
485 return (0);
486 }
487
488
489 /*
490 _______________________________________________________________________
491
492 Routine: BlockAllocateContig
493
494 Function: Allocate a contiguous group of allocation blocks. The
495 allocation is all-or-nothing. The caller guarantees that
496 there are enough free blocks (though they may not be
497 contiguous, in which case this call will fail).
498
499 Inputs:
500 vcb Pointer to volume where space is to be allocated
501 startingBlock Preferred first block for allocation
502 minBlocks Minimum number of contiguous blocks to allocate
503 maxBlocks Maximum number of contiguous blocks to allocate
504
505 Outputs:
506 actualStartBlock First block of range allocated, or 0 if error
507 actualNumBlocks Number of blocks allocated, or 0 if error
508 _______________________________________________________________________
509 */
510 static OSErr BlockAllocateContig(
511 ExtendedVCB *vcb,
512 UInt32 startingBlock,
513 UInt32 minBlocks,
514 UInt32 maxBlocks,
515 UInt32 *actualStartBlock,
516 UInt32 *actualNumBlocks)
517 {
518 OSErr err;
519
520 //
521 // Find a contiguous group of blocks at least minBlocks long.
522 // Determine the number of contiguous blocks available (up
523 // to maxBlocks).
524 //
525
526 /*
527 * NOTE: If the only contiguous free extent of at least minBlocks
528 * crosses startingBlock (i.e. starts before, ends after), then we
529 * won't find it. Earlier versions *did* find this case by letting
530 * the second search look past startingBlock by minBlocks. But
531 * with the free extent cache, this can lead to duplicate entries
532 * in the cache, causing the same blocks to be allocated twice.
533 */
534 err = BlockFindContiguous(vcb, startingBlock, vcb->totalBlocks, minBlocks, maxBlocks,
535 actualStartBlock, actualNumBlocks);
536 if (err == dskFulErr && startingBlock != 0) {
537 /*
538 * Constrain the endingBlock so we don't bother looking for ranges
539 * that would overlap those found in the previous call.
540 */
541 err = BlockFindContiguous(vcb, 0, startingBlock, minBlocks, maxBlocks,
542 actualStartBlock, actualNumBlocks);
543 }
544 if (err != noErr) goto Exit;
545
546 //
547 // Now mark those blocks allocated.
548 //
549 err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks);
550
551 Exit:
552 if (err != noErr) {
553 *actualStartBlock = 0;
554 *actualNumBlocks = 0;
555 }
556
557 return err;
558 }
559
560 /*
561 _______________________________________________________________________
562
563 Routine: BlockAllocateAny
564
565 Function: Allocate one or more allocation blocks. If there are fewer
566 free blocks than requested, all free blocks will be
567 allocated. The caller guarantees that there is at least
568 one free block.
569
570 Inputs:
571 vcb Pointer to volume where space is to be allocated
572 startingBlock Preferred first block for allocation
573 endingBlock Last block to check + 1
574 maxBlocks Maximum number of contiguous blocks to allocate
575
576 Outputs:
577 actualStartBlock First block of range allocated, or 0 if error
578 actualNumBlocks Number of blocks allocated, or 0 if error
579 _______________________________________________________________________
580 */
581 static OSErr BlockAllocateAny(
582 ExtendedVCB *vcb,
583 UInt32 startingBlock,
584 register UInt32 endingBlock,
585 UInt32 maxBlocks,
586 UInt32 *actualStartBlock,
587 UInt32 *actualNumBlocks)
588 {
589 OSErr err;
590 register UInt32 block; // current block number
591 register UInt32 currentWord; // Pointer to current word within bitmap block
592 register UInt32 bitMask; // Word with given bits already set (ready to OR in)
593 register UInt32 wordsLeft; // Number of words left in this bitmap block
594 UInt32 *buffer = NULL;
595 UInt32 *currCache = NULL;
596 UInt32 blockRef;
597 UInt32 bitsPerBlock;
598 UInt32 wordsPerBlock;
599 Boolean dirty = false;
600
601 // Since this routine doesn't wrap around
602 if (maxBlocks > (endingBlock - startingBlock)) {
603 maxBlocks = endingBlock - startingBlock;
604 }
605
606 //
607 // Pre-read the first bitmap block
608 //
609 err = ReadBitmapBlock(vcb, startingBlock, &currCache, &blockRef);
610 if (err != noErr) goto Exit;
611 buffer = currCache;
612
613 //
614 // Set up the current position within the block
615 //
616 {
617 UInt32 wordIndexInBlock;
618
619 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
620 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
621
622 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
623 buffer += wordIndexInBlock;
624 wordsLeft = wordsPerBlock - wordIndexInBlock;
625 currentWord = SWAP_BE32 (*buffer);
626 bitMask = kHighBitInWordMask >> (startingBlock & kBitsWithinWordMask);
627 }
628
629 //
630 // Find the first unallocated block
631 //
632 block=startingBlock;
633 while (block < endingBlock) {
634 if ((currentWord & bitMask) == 0)
635 break;
636
637 // Next bit
638 ++block;
639 bitMask >>= 1;
640 if (bitMask == 0) {
641 // Next word
642 bitMask = kHighBitInWordMask;
643 ++buffer;
644
645 if (--wordsLeft == 0) {
646 // Next block
647 buffer = currCache = NULL;
648 err = ReleaseBitmapBlock(vcb, blockRef, false);
649 if (err != noErr) goto Exit;
650
651 err = ReadBitmapBlock(vcb, block, &currCache, &blockRef);
652 if (err != noErr) goto Exit;
653 buffer = currCache;
654
655 wordsLeft = wordsPerBlock;
656 }
657
658 currentWord = SWAP_BE32 (*buffer);
659 }
660 }
661
662 // Did we get to the end of the bitmap before finding a free block?
663 // If so, then couldn't allocate anything.
664 if (block == endingBlock) {
665 err = dskFulErr;
666 goto Exit;
667 }
668
669 // Return the first block in the allocated range
670 *actualStartBlock = block;
671 dirty = true;
672
673 // If we could get the desired number of blocks before hitting endingBlock,
674 // then adjust endingBlock so we won't keep looking. Ideally, the comparison
675 // would be (block + maxBlocks) < endingBlock, but that could overflow. The
676 // comparison below yields identical results, but without overflow.
677 if (block < (endingBlock-maxBlocks)) {
678 endingBlock = block + maxBlocks; // if we get this far, we've found enough
679 }
680
681 //
682 // Allocate all of the consecutive blocks
683 //
684 while ((currentWord & bitMask) == 0) {
685 // Allocate this block
686 currentWord |= bitMask;
687
688 // Move to the next block. If no more, then exit.
689 ++block;
690 if (block == endingBlock)
691 break;
692
693 // Next bit
694 bitMask >>= 1;
695 if (bitMask == 0) {
696 *buffer = SWAP_BE32 (currentWord); // update value in bitmap
697
698 // Next word
699 bitMask = kHighBitInWordMask;
700 ++buffer;
701
702 if (--wordsLeft == 0) {
703 // Next block
704 buffer = currCache = NULL;
705 err = ReleaseBitmapBlock(vcb, blockRef, true);
706 if (err != noErr) goto Exit;
707
708 err = ReadBitmapBlock(vcb, block, &currCache, &blockRef);
709 if (err != noErr) goto Exit;
710 buffer = currCache;
711
712 wordsLeft = wordsPerBlock;
713 }
714
715 currentWord = SWAP_BE32 (*buffer);
716 }
717 }
718 *buffer = SWAP_BE32 (currentWord); // update the last change
719
720 Exit:
721 if (err == noErr) {
722 *actualNumBlocks = block - *actualStartBlock;
723 }
724 else {
725 *actualStartBlock = 0;
726 *actualNumBlocks = 0;
727 }
728
729 if (currCache)
730 (void) ReleaseBitmapBlock(vcb, blockRef, dirty);
731
732 return err;
733 }
734
735
736 /*
737 _______________________________________________________________________
738
739 Routine: BlockAllocateKnown
740
741 Function: Try to allocate space from known free space in the free
742 extent cache.
743
744 Inputs:
745 vcb Pointer to volume where space is to be allocated
746 maxBlocks Maximum number of contiguous blocks to allocate
747
748 Outputs:
749 actualStartBlock First block of range allocated, or 0 if error
750 actualNumBlocks Number of blocks allocated, or 0 if error
751
752 Returns:
753 dskFulErr Free extent cache is empty
754 _______________________________________________________________________
755 */
756 static OSErr BlockAllocateKnown(
757 ExtendedVCB *vcb,
758 UInt32 maxBlocks,
759 UInt32 *actualStartBlock,
760 UInt32 *actualNumBlocks)
761 {
762 UInt32 i;
763 UInt32 foundBlocks;
764 UInt32 newStartBlock, newBlockCount;
765
766 if (vcb->vcbFreeExtCnt == 0)
767 return dskFulErr;
768
769 // Just grab up to maxBlocks of the first (largest) free exent.
770 *actualStartBlock = vcb->vcbFreeExt[0].startBlock;
771 foundBlocks = vcb->vcbFreeExt[0].blockCount;
772 if (foundBlocks > maxBlocks)
773 foundBlocks = maxBlocks;
774 *actualNumBlocks = foundBlocks;
775
776 // Adjust the start and length of that extent.
777 newStartBlock = vcb->vcbFreeExt[0].startBlock + foundBlocks;
778 newBlockCount = vcb->vcbFreeExt[0].blockCount - foundBlocks;
779
780 // The first extent might not be the largest anymore. Bubble up any
781 // (now larger) extents to the top of the list.
782 for (i=1; i<vcb->vcbFreeExtCnt; ++i)
783 {
784 if (vcb->vcbFreeExt[i].blockCount > newBlockCount)
785 {
786 vcb->vcbFreeExt[i-1].startBlock = vcb->vcbFreeExt[i].startBlock;
787 vcb->vcbFreeExt[i-1].blockCount = vcb->vcbFreeExt[i].blockCount;
788 }
789 else
790 {
791 break;
792 }
793 }
794
795 // If this is now the smallest known free extent, then it might be smaller than
796 // other extents we didn't keep track of. So, just forget about this extent.
797 // After the previous loop, (i-1) is the index of the extent we just allocated from.
798 if (i == vcb->vcbFreeExtCnt)
799 {
800 // It's now the smallest extent, so forget about it
801 --vcb->vcbFreeExtCnt;
802 }
803 else
804 {
805 // It's not the smallest, so store it in its proper place
806 vcb->vcbFreeExt[i-1].startBlock = newStartBlock;
807 vcb->vcbFreeExt[i-1].blockCount = newBlockCount;
808 }
809
810 //
811 // Now mark the found extent in the bitmap
812 //
813 return BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks);
814 }
815
816
817
818 /*
819 _______________________________________________________________________
820
821 Routine: BlockMarkAllocated
822
823 Function: Mark a contiguous group of blocks as allocated (set in the
824 bitmap). It assumes those bits are currently marked
825 deallocated (clear in the bitmap).
826
827 Inputs:
828 vcb Pointer to volume where space is to be allocated
829 startingBlock First block number to mark as allocated
830 numBlocks Number of blocks to mark as allocated
831 _______________________________________________________________________
832 */
833 static OSErr BlockMarkAllocated(
834 ExtendedVCB *vcb,
835 UInt32 startingBlock,
836 register UInt32 numBlocks)
837 {
838 OSErr err;
839 register UInt32 *currentWord; // Pointer to current word within bitmap block
840 register UInt32 wordsLeft; // Number of words left in this bitmap block
841 register UInt32 bitMask; // Word with given bits already set (ready to OR in)
842 UInt32 firstBit; // Bit index within word of first bit to allocate
843 UInt32 numBits; // Number of bits in word to allocate
844 UInt32 *buffer = NULL;
845 UInt32 blockRef;
846 UInt32 bitsPerBlock;
847 UInt32 wordsPerBlock;
848
849 //
850 // Pre-read the bitmap block containing the first word of allocation
851 //
852
853 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
854 if (err != noErr) goto Exit;
855 //
856 // Initialize currentWord, and wordsLeft.
857 //
858 {
859 UInt32 wordIndexInBlock;
860
861 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
862 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
863
864 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
865 currentWord = buffer + wordIndexInBlock;
866 wordsLeft = wordsPerBlock - wordIndexInBlock;
867 }
868
869 //
870 // If the first block to allocate doesn't start on a word
871 // boundary in the bitmap, then treat that first word
872 // specially.
873 //
874
875 firstBit = startingBlock % kBitsPerWord;
876 if (firstBit != 0) {
877 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit
878 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word
879 if (numBits > numBlocks) {
880 numBits = numBlocks; // entire allocation is inside this one word
881 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last
882 }
883 #if DEBUG_BUILD
884 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
885 panic("BlockMarkAllocated: blocks already allocated!");
886 }
887 #endif
888 *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap
889 numBlocks -= numBits; // adjust number of blocks left to allocate
890
891 ++currentWord; // move to next word
892 --wordsLeft; // one less word left in this block
893 }
894
895 //
896 // Allocate whole words (32 blocks) at a time.
897 //
898
899 bitMask = kAllBitsSetInWord; // put this in a register for 68K
900 while (numBlocks >= kBitsPerWord) {
901 if (wordsLeft == 0) {
902 // Read in the next bitmap block
903 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
904
905 buffer = NULL;
906 err = ReleaseBitmapBlock(vcb, blockRef, true);
907 if (err != noErr) goto Exit;
908
909 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
910 if (err != noErr) goto Exit;
911
912 // Readjust currentWord and wordsLeft
913 currentWord = buffer;
914 wordsLeft = wordsPerBlock;
915 }
916 #if DEBUG_BUILD
917 if (*currentWord != 0) {
918 panic("BlockMarkAllocated: blocks already allocated!");
919 }
920 #endif
921 *currentWord = SWAP_BE32 (bitMask);
922 numBlocks -= kBitsPerWord;
923
924 ++currentWord; // move to next word
925 --wordsLeft; // one less word left in this block
926 }
927
928 //
929 // Allocate any remaining blocks.
930 //
931
932 if (numBlocks != 0) {
933 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits
934 if (wordsLeft == 0) {
935 // Read in the next bitmap block
936 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
937
938 buffer = NULL;
939 err = ReleaseBitmapBlock(vcb, blockRef, true);
940 if (err != noErr) goto Exit;
941
942 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
943 if (err != noErr) goto Exit;
944
945 // Readjust currentWord and wordsLeft
946 currentWord = buffer;
947 wordsLeft = wordsPerBlock;
948 }
949 #if DEBUG_BUILD
950 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
951 panic("BlockMarkAllocated: blocks already allocated!");
952 }
953 #endif
954 *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap
955
956 // No need to update currentWord or wordsLeft
957 }
958
959 Exit:
960
961 if (buffer)
962 (void)ReleaseBitmapBlock(vcb, blockRef, true);
963
964 return err;
965 }
966
967
968 /*
969 _______________________________________________________________________
970
971 Routine: BlockMarkFree
972
973 Function: Mark a contiguous group of blocks as free (clear in the
974 bitmap). It assumes those bits are currently marked
975 allocated (set in the bitmap).
976
977 Inputs:
978 vcb Pointer to volume where space is to be freed
979 startingBlock First block number to mark as freed
980 numBlocks Number of blocks to mark as freed
981 _______________________________________________________________________
982 */
983 static OSErr BlockMarkFree(
984 ExtendedVCB *vcb,
985 UInt32 startingBlock,
986 register UInt32 numBlocks)
987 {
988 OSErr err;
989 register UInt32 *currentWord; // Pointer to current word within bitmap block
990 register UInt32 wordsLeft; // Number of words left in this bitmap block
991 register UInt32 bitMask; // Word with given bits already set (ready to OR in)
992 UInt32 firstBit; // Bit index within word of first bit to allocate
993 UInt32 numBits; // Number of bits in word to allocate
994 UInt32 *buffer = NULL;
995 UInt32 blockRef;
996 UInt32 bitsPerBlock;
997 UInt32 wordsPerBlock;
998
999 //
1000 // Pre-read the bitmap block containing the first word of allocation
1001 //
1002
1003 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1004 if (err != noErr) goto Exit;
1005 //
1006 // Initialize currentWord, and wordsLeft.
1007 //
1008 {
1009 UInt32 wordIndexInBlock;
1010
1011 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
1012 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1013
1014 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
1015 currentWord = buffer + wordIndexInBlock;
1016 wordsLeft = wordsPerBlock - wordIndexInBlock;
1017 }
1018
1019 //
1020 // If the first block to free doesn't start on a word
1021 // boundary in the bitmap, then treat that first word
1022 // specially.
1023 //
1024
1025 firstBit = startingBlock % kBitsPerWord;
1026 if (firstBit != 0) {
1027 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit
1028 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word
1029 if (numBits > numBlocks) {
1030 numBits = numBlocks; // entire allocation is inside this one word
1031 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last
1032 }
1033 #if DEBUG_BUILD
1034 if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
1035 panic("BlockMarkFree: blocks not allocated!");
1036 }
1037 #endif
1038 *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap
1039 numBlocks -= numBits; // adjust number of blocks left to free
1040
1041 ++currentWord; // move to next word
1042 --wordsLeft; // one less word left in this block
1043 }
1044
1045 //
1046 // Free whole words (32 blocks) at a time.
1047 //
1048
1049 while (numBlocks >= kBitsPerWord) {
1050 if (wordsLeft == 0) {
1051 // Read in the next bitmap block
1052 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1053
1054 buffer = NULL;
1055 err = ReleaseBitmapBlock(vcb, blockRef, true);
1056 if (err != noErr) goto Exit;
1057
1058 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1059 if (err != noErr) goto Exit;
1060
1061 // Readjust currentWord and wordsLeft
1062 currentWord = buffer;
1063 wordsLeft = wordsPerBlock;
1064 }
1065
1066 #if DEBUG_BUILD
1067 if (*currentWord != SWAP_BE32 (kAllBitsSetInWord)) {
1068 panic("BlockMarkFree: blocks not allocated!");
1069 }
1070 #endif
1071 *currentWord = 0; // clear the entire word
1072 numBlocks -= kBitsPerWord;
1073
1074 ++currentWord; // move to next word
1075 --wordsLeft; // one less word left in this block
1076 }
1077
1078 //
1079 // Free 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 // Readjust currentWord and wordsLeft
1096 currentWord = buffer;
1097 wordsLeft = wordsPerBlock;
1098 }
1099 #if DEBUG_BUILD
1100 if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
1101 panic("BlockMarkFree: blocks not allocated!");
1102 }
1103 #endif
1104 *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap
1105
1106 // No need to update currentWord or wordsLeft
1107 }
1108
1109 Exit:
1110
1111 if (buffer)
1112 (void)ReleaseBitmapBlock(vcb, blockRef, true);
1113
1114 return err;
1115 }
1116
1117
1118 /*
1119 _______________________________________________________________________
1120
1121 Routine: BlockFindContiguous
1122
1123 Function: Find a contiguous range of blocks that are free (bits
1124 clear in the bitmap). If a contiguous range of the
1125 minimum size can't be found, an error will be returned.
1126
1127 Inputs:
1128 vcb Pointer to volume where space is to be allocated
1129 startingBlock Preferred first block of range
1130 endingBlock Last possible block in range + 1
1131 minBlocks Minimum number of blocks needed. Must be > 0.
1132 maxBlocks Maximum (ideal) number of blocks desired
1133
1134 Outputs:
1135 actualStartBlock First block of range found, or 0 if error
1136 actualNumBlocks Number of blocks found, or 0 if error
1137
1138 Returns:
1139 noErr Found at least minBlocks contiguous
1140 dskFulErr No contiguous space found, or all less than minBlocks
1141 _______________________________________________________________________
1142 */
1143
1144 static OSErr BlockFindContiguous(
1145 ExtendedVCB *vcb,
1146 UInt32 startingBlock,
1147 UInt32 endingBlock,
1148 UInt32 minBlocks,
1149 UInt32 maxBlocks,
1150 UInt32 *actualStartBlock,
1151 UInt32 *actualNumBlocks)
1152 {
1153 OSErr err;
1154 register UInt32 currentBlock; // Block we're currently looking at.
1155 UInt32 firstBlock; // First free block in current extent.
1156 UInt32 stopBlock; // If we get to this block, stop searching for first free block.
1157 UInt32 foundBlocks; // Number of contiguous free blocks in current extent.
1158 UInt32 *buffer = NULL;
1159 register UInt32 *currentWord;
1160 register UInt32 bitMask;
1161 register UInt32 wordsLeft;
1162 register UInt32 tempWord;
1163 UInt32 blockRef;
1164 UInt32 wordsPerBlock;
1165
1166 if ((endingBlock - startingBlock) < minBlocks)
1167 {
1168 // The set of blocks we're checking is smaller than the minimum number
1169 // of blocks, so we couldn't possibly find a good range.
1170 goto DiskFull;
1171 }
1172
1173 stopBlock = endingBlock - minBlocks + 1;
1174 currentBlock = startingBlock;
1175 firstBlock = 0;
1176
1177 //
1178 // Pre-read the first bitmap block.
1179 //
1180 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1181 if ( err != noErr ) goto ErrorExit;
1182
1183 //
1184 // Figure out where currentBlock is within the buffer.
1185 //
1186 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1187
1188 wordsLeft = (startingBlock / kBitsPerWord) & (wordsPerBlock-1); // Current index into buffer
1189 currentWord = buffer + wordsLeft;
1190 wordsLeft = wordsPerBlock - wordsLeft;
1191
1192 do
1193 {
1194 foundBlocks = 0;
1195
1196 //============================================================
1197 // Look for a free block, skipping over allocated blocks.
1198 //============================================================
1199
1200 //
1201 // Check an initial partial word (if any)
1202 //
1203 bitMask = currentBlock & kBitsWithinWordMask;
1204 if (bitMask)
1205 {
1206 tempWord = SWAP_BE32(*currentWord); // Fetch the current word only once
1207 bitMask = kHighBitInWordMask >> bitMask;
1208 while (tempWord & bitMask)
1209 {
1210 bitMask >>= 1;
1211 ++currentBlock;
1212 }
1213
1214 // Did we find an unused bit (bitMask != 0), or run out of bits (bitMask == 0)?
1215 if (bitMask)
1216 goto FoundUnused;
1217
1218 // Didn't find any unused bits, so we're done with this word.
1219 ++currentWord;
1220 --wordsLeft;
1221 }
1222
1223 //
1224 // Check whole words
1225 //
1226 while (currentBlock < stopBlock)
1227 {
1228 // See if it's time to read another block.
1229 if (wordsLeft == 0)
1230 {
1231 buffer = NULL;
1232 err = ReleaseBitmapBlock(vcb, blockRef, false);
1233 if (err != noErr) goto ErrorExit;
1234
1235 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1236 if ( err != noErr ) goto ErrorExit;
1237
1238 currentWord = buffer;
1239 wordsLeft = wordsPerBlock;
1240 }
1241
1242 // See if any of the bits are clear
1243 if ((tempWord = SWAP_BE32(*currentWord)) + 1) // non-zero if any bits were clear
1244 {
1245 // Figure out which bit is clear
1246 bitMask = kHighBitInWordMask;
1247 while (tempWord & bitMask)
1248 {
1249 bitMask >>= 1;
1250 ++currentBlock;
1251 }
1252
1253 break; // Found the free bit; break out to FoundUnused.
1254 }
1255
1256 // Keep looking at the next word
1257 currentBlock += kBitsPerWord;
1258 ++currentWord;
1259 --wordsLeft;
1260 }
1261
1262 FoundUnused:
1263 // Make sure the unused bit is early enough to use
1264 if (currentBlock >= stopBlock)
1265 {
1266 break;
1267 }
1268
1269 // Remember the start of the extent
1270 firstBlock = currentBlock;
1271
1272 //============================================================
1273 // Count the number of contiguous free blocks.
1274 //============================================================
1275
1276 //
1277 // Check an initial partial word (if any)
1278 //
1279 bitMask = currentBlock & kBitsWithinWordMask;
1280 if (bitMask)
1281 {
1282 tempWord = SWAP_BE32(*currentWord); // Fetch the current word only once
1283 bitMask = kHighBitInWordMask >> bitMask;
1284 while (bitMask && !(tempWord & bitMask))
1285 {
1286 bitMask >>= 1;
1287 ++currentBlock;
1288 }
1289
1290 // Did we find a used bit (bitMask != 0), or run out of bits (bitMask == 0)?
1291 if (bitMask)
1292 goto FoundUsed;
1293
1294 // Didn't find any used bits, so we're done with this word.
1295 ++currentWord;
1296 --wordsLeft;
1297 }
1298
1299 //
1300 // Check whole words
1301 //
1302 while (currentBlock < endingBlock)
1303 {
1304 // See if it's time to read another block.
1305 if (wordsLeft == 0)
1306 {
1307 buffer = NULL;
1308 err = ReleaseBitmapBlock(vcb, blockRef, false);
1309 if (err != noErr) goto ErrorExit;
1310
1311 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1312 if ( err != noErr ) goto ErrorExit;
1313
1314 currentWord = buffer;
1315 wordsLeft = wordsPerBlock;
1316 }
1317
1318 // See if any of the bits are set
1319 if ((tempWord = SWAP_BE32(*currentWord)) != 0)
1320 {
1321 // Figure out which bit is set
1322 bitMask = kHighBitInWordMask;
1323 while (!(tempWord & bitMask))
1324 {
1325 bitMask >>= 1;
1326 ++currentBlock;
1327 }
1328
1329 break; // Found the used bit; break out to FoundUsed.
1330 }
1331
1332 // Keep looking at the next word
1333 currentBlock += kBitsPerWord;
1334 ++currentWord;
1335 --wordsLeft;
1336
1337 // If we found at least maxBlocks, we can quit early.
1338 if ((currentBlock - firstBlock) >= maxBlocks)
1339 break;
1340 }
1341
1342 FoundUsed:
1343 // Make sure we didn't run out of bitmap looking for a used block.
1344 // If so, pin to the end of the bitmap.
1345 if (currentBlock > endingBlock)
1346 currentBlock = endingBlock;
1347
1348 // Figure out how many contiguous free blocks there were.
1349 // Pin the answer to maxBlocks.
1350 foundBlocks = currentBlock - firstBlock;
1351 if (foundBlocks > maxBlocks)
1352 foundBlocks = maxBlocks;
1353 if (foundBlocks >= minBlocks)
1354 break; // Found what we needed!
1355
1356 // This free chunk wasn't big enough. Try inserting it into the free extent cache in case
1357 // the allocation wasn't forced contiguous.
1358 tempWord = vcb->vcbFreeExtCnt;
1359 if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].blockCount < foundBlocks)
1360 --tempWord;
1361 if (tempWord < kMaxFreeExtents)
1362 {
1363 // We're going to add this extent. Bubble any smaller extents down in the list.
1364 while (tempWord && vcb->vcbFreeExt[tempWord-1].blockCount < foundBlocks)
1365 {
1366 vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1];
1367 --tempWord;
1368 }
1369 vcb->vcbFreeExt[tempWord].startBlock = firstBlock;
1370 vcb->vcbFreeExt[tempWord].blockCount = foundBlocks;
1371
1372 if (vcb->vcbFreeExtCnt < kMaxFreeExtents)
1373 ++vcb->vcbFreeExtCnt;
1374 }
1375 } while (currentBlock < stopBlock);
1376
1377
1378 // Return the outputs.
1379 if (foundBlocks < minBlocks)
1380 {
1381 DiskFull:
1382 err = dskFulErr;
1383 ErrorExit:
1384 *actualStartBlock = 0;
1385 *actualNumBlocks = 0;
1386 }
1387 else
1388 {
1389 err = noErr;
1390 *actualStartBlock = firstBlock;
1391 *actualNumBlocks = foundBlocks;
1392 }
1393
1394 if (buffer)
1395 (void) ReleaseBitmapBlock(vcb, blockRef, false);
1396
1397 return err;
1398 }
1399
1400
mirror of XNU