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