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