]> 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.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 extern OSErr LookupBufferMapping(caddr_t bufferAddress, struct buf **bpp, int *mappingIndexPtr);
554
555 /*
556 _______________________________________________________________________
557
558 Routine: BlockAllocateAny
559
560 Function: Allocate one or more allocation blocks. If there are fewer
561 free blocks than requested, all free blocks will be
562 allocated. The caller guarantees that there is at least
563 one free block.
564
565 Inputs:
566 vcb Pointer to volume where space is to be allocated
567 startingBlock Preferred first block for allocation
568 endingBlock Last block to check + 1
569 maxBlocks Maximum number of contiguous blocks to allocate
570
571 Outputs:
572 actualStartBlock First block of range allocated, or 0 if error
573 actualNumBlocks Number of blocks allocated, or 0 if error
574 _______________________________________________________________________
575 */
576 static OSErr BlockAllocateAny(
577 ExtendedVCB *vcb,
578 UInt32 startingBlock,
579 register UInt32 endingBlock,
580 UInt32 maxBlocks,
581 UInt32 *actualStartBlock,
582 UInt32 *actualNumBlocks)
583 {
584 OSErr err;
585 register UInt32 block; // current block number
586 register UInt32 currentWord; // Pointer to current word within bitmap block
587 register UInt32 bitMask; // Word with given bits already set (ready to OR in)
588 register UInt32 wordsLeft; // Number of words left in this bitmap block
589 UInt32 *buffer = NULL;
590 UInt32 *currCache = NULL;
591 UInt32 blockRef;
592 UInt32 bitsPerBlock;
593 UInt32 wordsPerBlock;
594 Boolean dirty = false;
595
596 // Since this routine doesn't wrap around
597 if (maxBlocks > (endingBlock - startingBlock)) {
598 maxBlocks = endingBlock - startingBlock;
599 }
600
601 //
602 // Pre-read the first bitmap block
603 //
604 err = ReadBitmapBlock(vcb, startingBlock, &currCache, &blockRef);
605 if (err != noErr) goto Exit;
606 buffer = currCache;
607
608 //
609 // Set up the current position within the block
610 //
611 {
612 UInt32 wordIndexInBlock;
613
614 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
615 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
616
617 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
618 buffer += wordIndexInBlock;
619 wordsLeft = wordsPerBlock - wordIndexInBlock;
620 currentWord = SWAP_BE32 (*buffer);
621 bitMask = kHighBitInWordMask >> (startingBlock & kBitsWithinWordMask);
622 }
623
624 //
625 // Find the first unallocated block
626 //
627 block=startingBlock;
628 while (block < endingBlock) {
629 if ((currentWord & bitMask) == 0)
630 break;
631
632 // Next bit
633 ++block;
634 bitMask >>= 1;
635 if (bitMask == 0) {
636 // Next word
637 bitMask = kHighBitInWordMask;
638 ++buffer;
639
640 if (--wordsLeft == 0) {
641 // Next block
642 buffer = currCache = NULL;
643 err = ReleaseBitmapBlock(vcb, blockRef, false);
644 if (err != noErr) goto Exit;
645
646 err = ReadBitmapBlock(vcb, block, &currCache, &blockRef);
647 if (err != noErr) goto Exit;
648 buffer = currCache;
649
650 wordsLeft = wordsPerBlock;
651 }
652
653 currentWord = SWAP_BE32 (*buffer);
654 }
655 }
656
657 // Did we get to the end of the bitmap before finding a free block?
658 // If so, then couldn't allocate anything.
659 if (block == endingBlock) {
660 err = dskFulErr;
661 goto Exit;
662 }
663
664 // Return the first block in the allocated range
665 *actualStartBlock = block;
666 dirty = true;
667
668 // If we could get the desired number of blocks before hitting endingBlock,
669 // then adjust endingBlock so we won't keep looking. Ideally, the comparison
670 // would be (block + maxBlocks) < endingBlock, but that could overflow. The
671 // comparison below yields identical results, but without overflow.
672 if (block < (endingBlock-maxBlocks)) {
673 endingBlock = block + maxBlocks; // if we get this far, we've found enough
674 }
675
676 //
677 // Allocate all of the consecutive blocks
678 //
679 while ((currentWord & bitMask) == 0) {
680 // Allocate this block
681 currentWord |= bitMask;
682
683 // Move to the next block. If no more, then exit.
684 ++block;
685 if (block == endingBlock)
686 break;
687
688 // Next bit
689 bitMask >>= 1;
690 if (bitMask == 0) {
691 *buffer = SWAP_BE32 (currentWord); // update value in bitmap
692
693 // Next word
694 bitMask = kHighBitInWordMask;
695 ++buffer;
696
697 if (--wordsLeft == 0) {
698 // Next block
699 buffer = currCache = NULL;
700 err = ReleaseBitmapBlock(vcb, blockRef, true);
701 if (err != noErr) goto Exit;
702
703 err = ReadBitmapBlock(vcb, block, &currCache, &blockRef);
704 if (err != noErr) goto Exit;
705 buffer = currCache;
706
707 wordsLeft = wordsPerBlock;
708 }
709
710 currentWord = SWAP_BE32 (*buffer);
711 }
712 }
713 *buffer = SWAP_BE32 (currentWord); // update the last change
714
715 Exit:
716 if (err == noErr) {
717 *actualNumBlocks = block - *actualStartBlock;
718 }
719 else {
720 *actualStartBlock = 0;
721 *actualNumBlocks = 0;
722 }
723
724 if (currCache)
725 (void) ReleaseBitmapBlock(vcb, blockRef, dirty);
726
727 return err;
728 }
729
730
731 /*
732 _______________________________________________________________________
733
734 Routine: BlockAllocateKnown
735
736 Function: Try to allocate space from known free space in the free
737 extent cache.
738
739 Inputs:
740 vcb Pointer to volume where space is to be allocated
741 maxBlocks Maximum number of contiguous blocks to allocate
742
743 Outputs:
744 actualStartBlock First block of range allocated, or 0 if error
745 actualNumBlocks Number of blocks allocated, or 0 if error
746
747 Returns:
748 dskFulErr Free extent cache is empty
749 _______________________________________________________________________
750 */
751 static OSErr BlockAllocateKnown(
752 ExtendedVCB *vcb,
753 UInt32 maxBlocks,
754 UInt32 *actualStartBlock,
755 UInt32 *actualNumBlocks)
756 {
757 UInt32 i;
758 UInt32 foundBlocks;
759 UInt32 newStartBlock, newBlockCount;
760
761 if (vcb->vcbFreeExtCnt == 0)
762 return dskFulErr;
763
764 // Just grab up to maxBlocks of the first (largest) free exent.
765 *actualStartBlock = vcb->vcbFreeExt[0].startBlock;
766 foundBlocks = vcb->vcbFreeExt[0].blockCount;
767 if (foundBlocks > maxBlocks)
768 foundBlocks = maxBlocks;
769 *actualNumBlocks = foundBlocks;
770
771 // Adjust the start and length of that extent.
772 newStartBlock = vcb->vcbFreeExt[0].startBlock + foundBlocks;
773 newBlockCount = vcb->vcbFreeExt[0].blockCount - foundBlocks;
774
775 // The first extent might not be the largest anymore. Bubble up any
776 // (now larger) extents to the top of the list.
777 for (i=1; i<vcb->vcbFreeExtCnt; ++i)
778 {
779 if (vcb->vcbFreeExt[i].blockCount > newBlockCount)
780 {
781 vcb->vcbFreeExt[i-1].startBlock = vcb->vcbFreeExt[i].startBlock;
782 vcb->vcbFreeExt[i-1].blockCount = vcb->vcbFreeExt[i].blockCount;
783 }
784 else
785 {
786 break;
787 }
788 }
789
790 // If this is now the smallest known free extent, then it might be smaller than
791 // other extents we didn't keep track of. So, just forget about this extent.
792 // After the previous loop, (i-1) is the index of the extent we just allocated from.
793 if (i == vcb->vcbFreeExtCnt)
794 {
795 // It's now the smallest extent, so forget about it
796 --vcb->vcbFreeExtCnt;
797 }
798 else
799 {
800 // It's not the smallest, so store it in its proper place
801 vcb->vcbFreeExt[i-1].startBlock = newStartBlock;
802 vcb->vcbFreeExt[i-1].blockCount = newBlockCount;
803 }
804
805 //
806 // Now mark the found extent in the bitmap
807 //
808 return BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks);
809 }
810
811
812
813 /*
814 _______________________________________________________________________
815
816 Routine: BlockMarkAllocated
817
818 Function: Mark a contiguous group of blocks as allocated (set in the
819 bitmap). It assumes those bits are currently marked
820 deallocated (clear in the bitmap).
821
822 Inputs:
823 vcb Pointer to volume where space is to be allocated
824 startingBlock First block number to mark as allocated
825 numBlocks Number of blocks to mark as allocated
826 _______________________________________________________________________
827 */
828 static OSErr BlockMarkAllocated(
829 ExtendedVCB *vcb,
830 UInt32 startingBlock,
831 register UInt32 numBlocks)
832 {
833 OSErr err;
834 register UInt32 *currentWord; // Pointer to current word within bitmap block
835 register UInt32 wordsLeft; // Number of words left in this bitmap block
836 register UInt32 bitMask; // Word with given bits already set (ready to OR in)
837 UInt32 firstBit; // Bit index within word of first bit to allocate
838 UInt32 numBits; // Number of bits in word to allocate
839 UInt32 *buffer = NULL;
840 UInt32 blockRef;
841 UInt32 bitsPerBlock;
842 UInt32 wordsPerBlock;
843
844 //
845 // Pre-read the bitmap block containing the first word of allocation
846 //
847
848 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
849 if (err != noErr) goto Exit;
850 //
851 // Initialize currentWord, and wordsLeft.
852 //
853 {
854 UInt32 wordIndexInBlock;
855
856 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
857 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
858
859 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
860 currentWord = buffer + wordIndexInBlock;
861 wordsLeft = wordsPerBlock - wordIndexInBlock;
862 }
863
864 //
865 // If the first block to allocate doesn't start on a word
866 // boundary in the bitmap, then treat that first word
867 // specially.
868 //
869
870 firstBit = startingBlock % kBitsPerWord;
871 if (firstBit != 0) {
872 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit
873 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word
874 if (numBits > numBlocks) {
875 numBits = numBlocks; // entire allocation is inside this one word
876 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last
877 }
878 #if DEBUG_BUILD
879 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
880 panic("BlockMarkAllocated: blocks already allocated!");
881 }
882 #endif
883 *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap
884 numBlocks -= numBits; // adjust number of blocks left to allocate
885
886 ++currentWord; // move to next word
887 --wordsLeft; // one less word left in this block
888 }
889
890 //
891 // Allocate whole words (32 blocks) at a time.
892 //
893
894 bitMask = kAllBitsSetInWord; // put this in a register for 68K
895 while (numBlocks >= kBitsPerWord) {
896 if (wordsLeft == 0) {
897 // Read in the next bitmap block
898 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
899
900 buffer = NULL;
901 err = ReleaseBitmapBlock(vcb, blockRef, true);
902 if (err != noErr) goto Exit;
903
904 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
905 if (err != noErr) goto Exit;
906
907 // Readjust currentWord and wordsLeft
908 currentWord = buffer;
909 wordsLeft = wordsPerBlock;
910 }
911 #if DEBUG_BUILD
912 if (*currentWord != 0) {
913 panic("BlockMarkAllocated: blocks already allocated!");
914 }
915 #endif
916 *currentWord = SWAP_BE32 (bitMask);
917 numBlocks -= kBitsPerWord;
918
919 ++currentWord; // move to next word
920 --wordsLeft; // one less word left in this block
921 }
922
923 //
924 // Allocate any remaining blocks.
925 //
926
927 if (numBlocks != 0) {
928 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits
929 if (wordsLeft == 0) {
930 // Read in the next bitmap block
931 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
932
933 buffer = NULL;
934 err = ReleaseBitmapBlock(vcb, blockRef, true);
935 if (err != noErr) goto Exit;
936
937 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
938 if (err != noErr) goto Exit;
939
940 // Readjust currentWord and wordsLeft
941 currentWord = buffer;
942 wordsLeft = wordsPerBlock;
943 }
944 #if DEBUG_BUILD
945 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
946 panic("BlockMarkAllocated: blocks already allocated!");
947 }
948 #endif
949 *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap
950
951 // No need to update currentWord or wordsLeft
952 }
953
954 Exit:
955
956 if (buffer)
957 (void)ReleaseBitmapBlock(vcb, blockRef, true);
958
959 return err;
960 }
961
962
963 /*
964 _______________________________________________________________________
965
966 Routine: BlockMarkFree
967
968 Function: Mark a contiguous group of blocks as free (clear in the
969 bitmap). It assumes those bits are currently marked
970 allocated (set in the bitmap).
971
972 Inputs:
973 vcb Pointer to volume where space is to be freed
974 startingBlock First block number to mark as freed
975 numBlocks Number of blocks to mark as freed
976 _______________________________________________________________________
977 */
978 static OSErr BlockMarkFree(
979 ExtendedVCB *vcb,
980 UInt32 startingBlock,
981 register UInt32 numBlocks)
982 {
983 OSErr err;
984 register UInt32 *currentWord; // Pointer to current word within bitmap block
985 register UInt32 wordsLeft; // Number of words left in this bitmap block
986 register UInt32 bitMask; // Word with given bits already set (ready to OR in)
987 UInt32 firstBit; // Bit index within word of first bit to allocate
988 UInt32 numBits; // Number of bits in word to allocate
989 UInt32 *buffer = NULL;
990 UInt32 blockRef;
991 UInt32 bitsPerBlock;
992 UInt32 wordsPerBlock;
993
994 //
995 // Pre-read the bitmap block containing the first word of allocation
996 //
997
998 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
999 if (err != noErr) goto Exit;
1000 //
1001 // Initialize currentWord, and wordsLeft.
1002 //
1003 {
1004 UInt32 wordIndexInBlock;
1005
1006 bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
1007 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1008
1009 wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
1010 currentWord = buffer + wordIndexInBlock;
1011 wordsLeft = wordsPerBlock - wordIndexInBlock;
1012 }
1013
1014 //
1015 // If the first block to free doesn't start on a word
1016 // boundary in the bitmap, then treat that first word
1017 // specially.
1018 //
1019
1020 firstBit = startingBlock % kBitsPerWord;
1021 if (firstBit != 0) {
1022 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit
1023 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word
1024 if (numBits > numBlocks) {
1025 numBits = numBlocks; // entire allocation is inside this one word
1026 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last
1027 }
1028 #if DEBUG_BUILD
1029 if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
1030 panic("BlockMarkFree: blocks not allocated!");
1031 }
1032 #endif
1033 *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap
1034 numBlocks -= numBits; // adjust number of blocks left to free
1035
1036 ++currentWord; // move to next word
1037 --wordsLeft; // one less word left in this block
1038 }
1039
1040 //
1041 // Free whole words (32 blocks) at a time.
1042 //
1043
1044 while (numBlocks >= kBitsPerWord) {
1045 if (wordsLeft == 0) {
1046 // Read in the next bitmap block
1047 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1048
1049 buffer = NULL;
1050 err = ReleaseBitmapBlock(vcb, blockRef, true);
1051 if (err != noErr) goto Exit;
1052
1053 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1054 if (err != noErr) goto Exit;
1055
1056 // Readjust currentWord and wordsLeft
1057 currentWord = buffer;
1058 wordsLeft = wordsPerBlock;
1059 }
1060
1061 #if DEBUG_BUILD
1062 if (*currentWord != SWAP_BE32 (kAllBitsSetInWord)) {
1063 panic("BlockMarkFree: blocks not allocated!");
1064 }
1065 #endif
1066 *currentWord = 0; // clear the entire word
1067 numBlocks -= kBitsPerWord;
1068
1069 ++currentWord; // move to next word
1070 --wordsLeft; // one less word left in this block
1071 }
1072
1073 //
1074 // Free any remaining blocks.
1075 //
1076
1077 if (numBlocks != 0) {
1078 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits
1079 if (wordsLeft == 0) {
1080 // Read in the next bitmap block
1081 startingBlock += bitsPerBlock; // generate a block number in the next bitmap block
1082
1083 buffer = NULL;
1084 err = ReleaseBitmapBlock(vcb, blockRef, true);
1085 if (err != noErr) goto Exit;
1086
1087 err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
1088 if (err != noErr) goto Exit;
1089
1090 // Readjust currentWord and wordsLeft
1091 currentWord = buffer;
1092 wordsLeft = wordsPerBlock;
1093 }
1094 #if DEBUG_BUILD
1095 if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
1096 panic("BlockMarkFree: blocks not allocated!");
1097 }
1098 #endif
1099 *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap
1100
1101 // No need to update currentWord or wordsLeft
1102 }
1103
1104 Exit:
1105
1106 if (buffer)
1107 (void)ReleaseBitmapBlock(vcb, blockRef, true);
1108
1109 return err;
1110 }
1111
1112
1113 /*
1114 _______________________________________________________________________
1115
1116 Routine: BlockFindContiguous
1117
1118 Function: Find a contiguous range of blocks that are free (bits
1119 clear in the bitmap). If a contiguous range of the
1120 minimum size can't be found, an error will be returned.
1121
1122 Inputs:
1123 vcb Pointer to volume where space is to be allocated
1124 startingBlock Preferred first block of range
1125 endingBlock Last possible block in range + 1
1126 minBlocks Minimum number of blocks needed. Must be > 0.
1127 maxBlocks Maximum (ideal) number of blocks desired
1128
1129 Outputs:
1130 actualStartBlock First block of range found, or 0 if error
1131 actualNumBlocks Number of blocks found, or 0 if error
1132
1133 Returns:
1134 noErr Found at least minBlocks contiguous
1135 dskFulErr No contiguous space found, or all less than minBlocks
1136 _______________________________________________________________________
1137 */
1138
1139 static OSErr BlockFindContiguous(
1140 ExtendedVCB *vcb,
1141 UInt32 startingBlock,
1142 UInt32 endingBlock,
1143 UInt32 minBlocks,
1144 UInt32 maxBlocks,
1145 UInt32 *actualStartBlock,
1146 UInt32 *actualNumBlocks)
1147 {
1148 OSErr err;
1149 register UInt32 currentBlock; // Block we're currently looking at.
1150 UInt32 firstBlock; // First free block in current extent.
1151 UInt32 stopBlock; // If we get to this block, stop searching for first free block.
1152 UInt32 foundBlocks; // Number of contiguous free blocks in current extent.
1153 UInt32 *buffer = NULL;
1154 register UInt32 *currentWord;
1155 register UInt32 bitMask;
1156 register UInt32 wordsLeft;
1157 register UInt32 tempWord;
1158 UInt32 blockRef;
1159 UInt32 wordsPerBlock;
1160
1161 if ((endingBlock - startingBlock) < minBlocks)
1162 {
1163 // The set of blocks we're checking is smaller than the minimum number
1164 // of blocks, so we couldn't possibly find a good range.
1165 goto DiskFull;
1166 }
1167
1168 stopBlock = endingBlock - minBlocks + 1;
1169 currentBlock = startingBlock;
1170
1171 //
1172 // Pre-read the first bitmap block.
1173 //
1174 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1175 if ( err != noErr ) goto ErrorExit;
1176
1177 //
1178 // Figure out where currentBlock is within the buffer.
1179 //
1180 wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
1181
1182 wordsLeft = (startingBlock / kBitsPerWord) & (wordsPerBlock-1); // Current index into buffer
1183 currentWord = buffer + wordsLeft;
1184 wordsLeft = wordsPerBlock - wordsLeft;
1185
1186 do
1187 {
1188 foundBlocks = 0;
1189
1190 //============================================================
1191 // Look for a free block, skipping over allocated blocks.
1192 //============================================================
1193
1194 //
1195 // Check an initial partial word (if any)
1196 //
1197 bitMask = currentBlock & kBitsWithinWordMask;
1198 if (bitMask)
1199 {
1200 tempWord = *currentWord; // Fetch the current word only once
1201 bitMask = kHighBitInWordMask >> bitMask;
1202 while (tempWord & bitMask)
1203 {
1204 bitMask >>= 1;
1205 ++currentBlock;
1206 }
1207
1208 // Did we find an unused bit (bitMask != 0), or run out of bits (bitMask == 0)?
1209 if (bitMask)
1210 goto FoundUnused;
1211
1212 // Didn't find any unused bits, so we're done with this word.
1213 ++currentWord;
1214 --wordsLeft;
1215 }
1216
1217 //
1218 // Check whole words
1219 //
1220 while (currentBlock < stopBlock)
1221 {
1222 // See if it's time to read another block.
1223 if (wordsLeft == 0)
1224 {
1225 buffer = NULL;
1226 err = ReleaseBitmapBlock(vcb, blockRef, false);
1227 if (err != noErr) goto ErrorExit;
1228
1229 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1230 if ( err != noErr ) goto ErrorExit;
1231
1232 currentWord = buffer;
1233 wordsLeft = wordsPerBlock;
1234 }
1235
1236 // See if any of the bits are clear
1237 if ((tempWord=*currentWord) + 1) // non-zero if any bits were clear
1238 {
1239 // Figure out which bit is clear
1240 bitMask = kHighBitInWordMask;
1241 while (tempWord & bitMask)
1242 {
1243 bitMask >>= 1;
1244 ++currentBlock;
1245 }
1246
1247 break; // Found the free bit; break out to FoundUnused.
1248 }
1249
1250 // Keep looking at the next word
1251 currentBlock += kBitsPerWord;
1252 ++currentWord;
1253 --wordsLeft;
1254 }
1255
1256 FoundUnused:
1257 // Make sure the unused bit is early enough to use
1258 if (currentBlock >= stopBlock)
1259 {
1260 break;
1261 }
1262
1263 // Remember the start of the extent
1264 firstBlock = currentBlock;
1265
1266 //============================================================
1267 // Count the number of contiguous free blocks.
1268 //============================================================
1269
1270 //
1271 // Check an initial partial word (if any)
1272 //
1273 bitMask = currentBlock & kBitsWithinWordMask;
1274 if (bitMask)
1275 {
1276 tempWord = *currentWord; // Fetch the current word only once
1277 bitMask = kHighBitInWordMask >> bitMask;
1278 while (bitMask && !(tempWord & bitMask))
1279 {
1280 bitMask >>= 1;
1281 ++currentBlock;
1282 }
1283
1284 // Did we find a used bit (bitMask != 0), or run out of bits (bitMask == 0)?
1285 if (bitMask)
1286 goto FoundUsed;
1287
1288 // Didn't find any used bits, so we're done with this word.
1289 ++currentWord;
1290 --wordsLeft;
1291 }
1292
1293 //
1294 // Check whole words
1295 //
1296 while (currentBlock < endingBlock)
1297 {
1298 // See if it's time to read another block.
1299 if (wordsLeft == 0)
1300 {
1301 buffer = NULL;
1302 err = ReleaseBitmapBlock(vcb, blockRef, false);
1303 if (err != noErr) goto ErrorExit;
1304
1305 err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
1306 if ( err != noErr ) goto ErrorExit;
1307
1308 currentWord = buffer;
1309 wordsLeft = wordsPerBlock;
1310 }
1311
1312 // See if any of the bits are set
1313 if ((tempWord=*currentWord) != 0)
1314 {
1315 // Figure out which bit is set
1316 bitMask = kHighBitInWordMask;
1317 while (!(tempWord & bitMask))
1318 {
1319 bitMask >>= 1;
1320 ++currentBlock;
1321 }
1322
1323 break; // Found the used bit; break out to FoundUsed.
1324 }
1325
1326 // Keep looking at the next word
1327 currentBlock += kBitsPerWord;
1328 ++currentWord;
1329 --wordsLeft;
1330
1331 // If we found at least maxBlocks, we can quit early.
1332 if ((currentBlock - firstBlock) >= maxBlocks)
1333 break;
1334 }
1335
1336 FoundUsed:
1337 // Make sure we didn't run out of bitmap looking for a used block.
1338 // If so, pin to the end of the bitmap.
1339 if (currentBlock > endingBlock)
1340 currentBlock = endingBlock;
1341
1342 // Figure out how many contiguous free blocks there were.
1343 // Pin the answer to maxBlocks.
1344 foundBlocks = currentBlock - firstBlock;
1345 if (foundBlocks > maxBlocks)
1346 foundBlocks = maxBlocks;
1347 if (foundBlocks >= minBlocks)
1348 break; // Found what we needed!
1349
1350 // This free chunk wasn't big enough. Try inserting it into the free extent cache in case
1351 // the allocation wasn't forced contiguous.
1352 tempWord = vcb->vcbFreeExtCnt;
1353 if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].blockCount < foundBlocks)
1354 --tempWord;
1355 if (tempWord < kMaxFreeExtents)
1356 {
1357 // We're going to add this extent. Bubble any smaller extents down in the list.
1358 while (tempWord && vcb->vcbFreeExt[tempWord-1].blockCount < foundBlocks)
1359 {
1360 vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1];
1361 --tempWord;
1362 }
1363 vcb->vcbFreeExt[tempWord].startBlock = firstBlock;
1364 vcb->vcbFreeExt[tempWord].blockCount = foundBlocks;
1365
1366 if (vcb->vcbFreeExtCnt < kMaxFreeExtents)
1367 ++vcb->vcbFreeExtCnt;
1368 }
1369 } while (currentBlock < stopBlock);
1370
1371
1372 // Return the outputs.
1373 if (foundBlocks < minBlocks)
1374 {
1375 DiskFull:
1376 err = dskFulErr;
1377 ErrorExit:
1378 *actualStartBlock = 0;
1379 *actualNumBlocks = 0;
1380 }
1381 else
1382 {
1383 err = noErr;
1384 *actualStartBlock = firstBlock;
1385 *actualNumBlocks = foundBlocks;
1386 }
1387
1388 if (buffer)
1389 (void) ReleaseBitmapBlock(vcb, blockRef, false);
1390
1391 return err;
1392 }
1393
1394
mirror of XNU