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


7a6417dd726310a70918cdfefe1efc46b262effb
[apple/xnu.git] / bsd / hfs / hfscommon / Misc / VolumeAllocation.c
1 /*
2 * Copyright (c) 2000 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-2000 by Apple Computer, Inc., all rights reserved.
30
31 File Ownership:
32
33 DRI: Mark Day
34
35 Other Contact: Greg Parks
36
37 Technology: HFS+
38
39 Writers:
40
41 (djb) Don Brady
42 (DSH) Deric Horn
43 (msd) Mark Day
44
45 Change History (most recent first):
46 <MacOSX> 1/22/2000 djb Removed unused BlockCheck and BlockVerifyAllocated routines.
47 <MacOSX> 4/27/98 djb Remove references to unused/legacy vcbFreeBks.
48 <MacOSX> 4/27/98 djb Remove unneccessary DebugStr in BlockVerifyAllocated.
49 <MacOSX> 4/17/98 djb Add VCB locking.
50 <MacOSX> 4/13/98 djb Add RequireFileLock checking to ReadBitmapBlock.
51 <MacOSX> 3/31/98 djb Sync up with final HFSVolumes.h header file.
52
53 <12> 1 0/31/97 DSH Modify BlockVerifyAllocated() so DFA can call without actually
54 writing to the disk.
55 <CS11> 10/20/97 msd The way BlockAllocate rounds up to a multiple of the clump size
56 is wrong. ExtendFileC should do the round-up and pass the result
57 into BlockAllocate. Removed the fcb parameter to BlockAllocate;
58 added a bytesMaximum parameter.
59 <CS10> 10/17/97 msd Conditionalize DebugStrs.
60 <CS9> 9/4/97 djb Add logging to BlockAllocate.
61 <CS8> 9/4/97 msd Add a histogram of allocation sizes. Use DEBUG_BUILD instead of
62 VSM_DEBUG to generate DebugStr messages.
63 <CS7> 8/14/97 msd Bug 1662332. Don't mark blocks dirty in UpdateFreeCount. In
64 BlockVerifyAllocated, only mark blocks dirty if they've actually
65 changed.
66 <CS6> 7/16/97 DSH FilesInternal.i renamed FileMgrInternal.i to avoid name
67 collision
68 <CS5> 7/8/97 DSH Loading PrecompiledHeaders from define passed in on C line
69 <CS4> 6/12/97 msd Export BlockAllocateAny and UpdateVCBFreeBlks.
70 <3> 5/8/97 DSH Added comments and ascii diagram of new BlockFindContiguous()
71 algorithm.
72 <2> 5/7/97 DSH New faster BlockFindContiguous algorithm. It searches backwards
73 until a dirty bit is found instead of forwards.
74 <CS1> 4/25/97 djb first checked in
75
76 <HFS21> 4/14/97 msd Fix UpdateVCBFreeBlks so free space calculation doesn't overflow
77 on volumes bigger than 4GB.
78 <HFS20> 4/4/97 djb Get in sync with volume format changes.
79 <HFS19> 1/27/97 msd Speed up BlockCheck and UpdateFreeCount. Removed DebugStr from
80 BlockCheck; there are now DebugStr's in BlockVerifyAllocated,
81 before the bitmap gets fixed (so potential problems can be
82 debugged easier). Adjusted comments about internal routines.
83 Changed names of "Fast" routines back to their original names
84 (since the originals are now removed).
85 <HFS18> 1/24/97 msd Speed up allocation and deallocation.
86 <HFS17> 1/21/97 msd Add instrumentation for function entry/exit. BlockAllocate and
87 ReadBitMapBlock use the event tag to log bytes requested and
88 block number (respectively).
89 <HFS16> 1/15/97 djb Add HFS+ supprt to BlockCheck (for MountCheck).
90 <HFS15> 1/13/97 DSH Use vcb->nextAllocation instead of vcbAllocPtr.
91 <HFS14> 1/9/97 djb UpdateVCBFreeBlks is not converting correctly.
92 <HFS13> 1/6/97 djb Use vcb's allocationsRefNum to access allocation file.
93 <HFS12> 1/2/97 DSH Added UpdateVCBFreeBlks() to update vcbFreeBks whenever we
94 update vcb->freeblocks.
95 <HFS11> 12/19/96 DSH All refs to VCB are now refs to ExtendedVCB
96 <HFS10> 12/12/96 msd DivideAndRoundUp should not be declared as static.
97 <HFS9> 12/10/96 msd Check PRAGMA_LOAD_SUPPORTED before loading precompiled headers.
98 <HFS8> 12/4/96 DSH PrecompiledHeaders
99 <HFS7> 11/27/96 djb Added AllocateFreeSpace for HFS wrapper support.
100 <HFS6> 11/27/96 msd Changed ReadBitmapBlock to read from HFS+ allocation file.
101 Temporarily uses the vcbVBMSt field of the VCB as the allocation
102 file's refnum until extended VCB changes are checked in.
103 <HFS5> 11/26/96 msd VSM and FileExtentMapping routines use FCB instead of FCBRec.
104 <HFS4> 11/20/96 DSH Changed a parameter in GetBlock_glue, so I also changed the
105 caller.
106 <HFS3> 11/20/96 msd Include FilesInternal.h. Remove definition of MarkVCBDirty
107 (since it is now in FilesInternal.h).
108 <HFS2> 11/12/96 msd Need to bound allocations to be within the last allocation block
109 of the volume (function AllocateAt).
110 <HFS1> 11/11/96 msd first checked in
111 */
112
113 /*
114 Public routines:
115 BlockAllocate
116 Allocate space on a volume. Can allocate space contiguously.
117 If not contiguous, then allocation may be less than what was
118 asked for. Returns the starting block number, and number of
119 blocks. (Will only do a single extent???)
120 BlockDeallocate
121 Deallocate a contiguous run of allocation blocks.
122 UpdateFreeCount
123 Computes the number of free allocation blocks on a volume.
124 The vcb's free block count is updated.
125
126 AllocateFreeSpace
127 Allocates all the remaining free space (used for embedding HFS+ volumes).
128
129 BlockAllocateAny
130 Find and allocate a contiguous range of blocks up to a given size. The
131 first range of contiguous free blocks found are allocated, even if there
132 are fewer blocks than requested (and even if a contiguous range of blocks
133 of the given size exists elsewhere).
134
135 UpdateVCBFreeBlks
136 Given an ExtenddVCB, calculate the vcbFreeBks value
137 so that vcbFreeBks*vcbAlBlkSiz == freeBlocks*blockSize.
138
139 Internal routines:
140 BlockMarkFree
141 Mark a contiguous range of blocks as free. The corresponding
142 bits in the volume bitmap will be cleared.
143 BlockMarkAllocated
144 Mark a contiguous range of blocks as allocated. The cor-
145 responding bits in the volume bitmap are set. Also tests to see
146 if any of the blocks were previously unallocated.
147 FindContiguous
148 Find a contiguous range of blocks of a given size. The caller
149 specifies where to begin the search (by block number). The
150 block number of the first block in the range is returned.
151 BlockAllocateContig
152 Find and allocate a contiguous range of blocks of a given size. If
153 a contiguous range of free blocks of the given size isn't found, then
154 the allocation fails (i.e. it is "all or nothing").
155 ReadBitmapBlock
156 Given an allocation block number, read the bitmap block that
157 contains that allocation block into a caller-supplied buffer.
158 */
159
160 #include "../../hfs_macos_defs.h"
161
162 #include <sys/types.h>
163 #include <sys/buf.h>
164 #include <sys/systm.h>
165
166 #include "../../hfs.h"
167 #include "../../hfs_dbg.h"
168 #include "../../hfs_format.h"
169 #include "../../hfs_endian.h"
170
171 #include "../headers/FileMgrInternal.h"
172
173 #include "../headers/HFSInstrumentation.h"
174
175 #define EXPLICIT_BUFFER_RELEASES 1
176
177 enum {
178 kBitsPerByte = 8,
179 kBitsPerWord = 32,
180 kWordsPerBlock = 128,
181 kBytesPerBlock = 512,
182 kBitsPerBlock = 4096,
183
184 kBitsWithinWordMask = kBitsPerWord-1,
185 kBitsWithinBlockMask = kBitsPerBlock-1,
186 kWordsWithinBlockMask = kWordsPerBlock-1,
187
188 kExtentsPerRecord = 3
189 };
190
191 #define kLowBitInWordMask 0x00000001ul
192 #define kHighBitInWordMask 0x80000000ul
193 #define kAllBitsSetInWord 0xFFFFFFFFul
194
195
196 static OSErr ReadBitmapBlock(
197 ExtendedVCB *vcb,
198 UInt32 block,
199 UInt32 **buffer);
200
201 static OSErr BlockAllocateContig(
202 ExtendedVCB *vcb,
203 UInt32 startingBlock,
204 UInt32 minBlocks,
205 UInt32 maxBlocks,
206 UInt32 *actualStartBlock,
207 UInt32 *actualNumBlocks);
208
209 static OSErr BlockFindContiguous(
210 ExtendedVCB *vcb,
211 UInt32 startingBlock,
212 UInt32 endingBlock,
213 UInt32 minBlocks,
214 UInt32 maxBlocks,
215 UInt32 *actualStartBlock,
216 UInt32 *actualNumBlocks);
217
218 static OSErr BlockMarkAllocated(
219 ExtendedVCB *vcb,
220 UInt32 startingBlock,
221 UInt32 numBlocks);
222
223 static OSErr BlockMarkFree(
224 ExtendedVCB *vcb,
225 UInt32 startingBlock,
226 UInt32 numBlocks);
227
228
229 /*
230 ;________________________________________________________________________________
231 ;
232 ; Routine: BlkAlloc
233 ;
234 ; Function: Allocate space on a volume. If contiguous allocation is requested,
235 ; at least the requested number of bytes will be allocated or an
236 ; error will be returned. If contiguous allocation is not forced,
237 ; the space will be allocated at the first free fragment following
238 ; the requested starting allocation block. If there is not enough
239 ; room there, a block of less than the requested size will be
240 ; allocated.
241 ;
242 ; If the requested starting block is 0 (for new file allocations),
243 ; the volume's allocation block pointer will be used as a starting
244 ; point.
245 ;
246 ; All requests will be rounded up to the next highest clump size, as
247 ; indicated in the file's FCB.
248 ;
249 ; Input Arguments:
250 ; vcb - Pointer to ExtendedVCB for the volume to allocate space on
251 ; fcb - Pointer to FCB for the file for which storage is being allocated
252 ; startingBlock - Preferred starting allocation block, 0 = no preference
253 ; forceContiguous - Force contiguous flag - if bit 0 set (NE), allocation is contiguous
254 ; or an error is returned
255 ; bytesRequested - Number of bytes requested. If the allocation is non-contiguous,
256 ; less than this may actually be allocated
257 ; bytesMaximum - The maximum number of bytes to allocate. If there is additional free
258 ; space after bytesRequested, then up to bytesMaximum bytes should really
259 ; be allocated. (Used by ExtendFileC to round up allocations to a multiple
260 ; of the file's clump size.)
261 ;
262 ; Output:
263 ; (result) - Error code, zero for successful allocation
264 ; *startBlock - Actual starting allocation block
265 ; *actualBlocks - Actual number of allocation blocks allocated
266 ;
267 ; Side effects:
268 ; The volume bitmap is read and updated; the volume bitmap cache may be changed.
269 ;
270 ; Modification history:
271 ; <06Oct85> PWD Changed to check for errors after calls to ReadBM and NextWord
272 ; Relocated call to MarkBlock in allocation loop
273 ; Changed to call NextBit
274 ; <21Oct85> PWD Changed to check VCBFreeBks before attempting to allocate any block.
275 ; Speed up scan for free space by checking for all 1's.
276 ;________________________________________________________________________________
277 */
278
279 OSErr BlockAllocate (
280 ExtendedVCB *vcb, /* which volume to allocate space on */
281 UInt32 startingBlock, /* preferred starting block, or 0 for no preference */
282 SInt64 bytesRequested, /* desired number of BYTES to allocate */
283 SInt64 bytesMaximum, /* maximum number of bytes to allocate */
284 Boolean forceContiguous, /* non-zero to force contiguous allocation and to force */
285 /* bytesRequested bytes to actually be allocated */
286 UInt32 *actualStartBlock, /* actual first block of allocation */
287 UInt32 *actualNumBlocks) /* number of blocks actually allocated; if forceContiguous */
288 /* was zero, then this may represent fewer than bytesRequested */
289 /* bytes */
290 {
291 OSErr err;
292 UInt32 minBlocks; // minimum number of allocation blocks requested
293 UInt32 maxBlocks; // number of allocation blocks requested, rounded to clump size
294 Boolean updateAllocPtr = false; // true if nextAllocation needs to be updated
295
296 LogStartTime(kTraceBlockAllocate);
297
298 #if HFSInstrumentation
299 InstSplitHistogramClassRef histogram;
300 InstTraceClassRef trace;
301 InstEventTag eventTag;
302
303 err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:BlockAllocate", 'hfs+', kInstEnableClassMask, &trace);
304 if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
305
306 err = InstCreateSplitHistogramClass(kInstRootClassRef, "HFS:VSM:BlockAllocate size", 0, 512, 16384, 262144, 16384,
307 kInstEnableClassMask, &histogram);
308 if (err != noErr) DebugStr("\pError from InstCreateHistogramClass");
309
310 eventTag = bytesRequested; // a cheap way to get bytesRequested into the log
311 InstLogTraceEvent( trace, eventTag, kInstStartEvent);
312 InstUpdateHistogram( histogram, bytesRequested, 1);
313 #endif
314
315 //
316 // Initialize outputs in case we get an error
317 //
318 *actualStartBlock = 0;
319 *actualNumBlocks = 0;
320
321 //
322 // Compute the number of allocation blocks requested, and maximum
323 //
324 minBlocks = FileBytesToBlocks(bytesRequested, vcb->blockSize);
325 maxBlocks = FileBytesToBlocks(bytesMaximum, vcb->blockSize);
326
327 //
328 // If the disk is already full, don't bother.
329 //
330 if (vcb->freeBlocks == 0) {
331 err = dskFulErr;
332 goto Exit;
333 }
334 if (forceContiguous && vcb->freeBlocks < minBlocks) {
335 err = dskFulErr;
336 goto Exit;
337 }
338
339 //
340 // If caller didn't specify a starting block number, then use the volume's
341 // next block to allocate from.
342 //
343 if (startingBlock == 0) {
344 VCB_LOCK(vcb);
345 startingBlock = vcb->nextAllocation;
346 VCB_UNLOCK(vcb);
347 updateAllocPtr = true;
348 }
349
350 //
351 // If the request must be contiguous, then find a sequence of free blocks
352 // that is long enough. Otherwise, find the first free block.
353 //
354 if (forceContiguous) {
355 err = BlockAllocateContig(vcb, startingBlock, minBlocks, maxBlocks, actualStartBlock, actualNumBlocks);
356 } else {
357 err = BlockAllocateAny(vcb, startingBlock, vcb->totalBlocks, maxBlocks, actualStartBlock, actualNumBlocks);
358 if (err == dskFulErr) {
359 err = BlockAllocateAny(vcb, 0, startingBlock, maxBlocks, actualStartBlock, actualNumBlocks);
360 };
361 }
362
363 if (err == noErr) {
364 //
365 // If we used the volume's roving allocation pointer, then we need to update it.
366 // Adding in the length of the current allocation might reduce the next allocate
367 // call by avoiding a re-scan of the already allocated space. However, the clump
368 // just allocated can quite conceivably end up being truncated or released when
369 // the file is closed or its EOF changed. Leaving the allocation pointer at the
370 // start of the last allocation will avoid unnecessary fragmentation in this case.
371 //
372 VCB_LOCK(vcb);
373
374 if (updateAllocPtr)
375 vcb->nextAllocation = *actualStartBlock;
376
377 //
378 // Update the number of free blocks on the volume
379 //
380 vcb->freeBlocks -= *actualNumBlocks;
381 VCB_UNLOCK(vcb);
382
383 UpdateVCBFreeBlks( vcb );
384 MarkVCBDirty(vcb);
385 }
386
387 Exit:
388
389 #if HFSInstrumentation
390 InstLogTraceEvent( trace, eventTag, kInstEndEvent);
391 #endif
392 LogEndTime(kTraceBlockAllocate, err);
393
394 return err;
395 }
396
397
398 /*
399 ;________________________________________________________________________________
400 ;
401 ; Routine: UpdateVCBFreeBlks
402 ;
403 ; Function: Whenever the freeBlocks field in the ExtendedVCB is updated,
404 ; we must also recalculate the (UInt16) vcbFreeBks field in the
405 ; traditional HFS VCB structure.
406 ;
407 ; Input Arguments:
408 ; vcb - Pointer to ExtendedVCB for the volume to free space on
409 ;________________________________________________________________________________
410 */
411 void UpdateVCBFreeBlks( ExtendedVCB *vcb )
412 {
413 #if DEBUG_BUILD
414 if ( vcb->vcbSigWord == kHFSSigWord && vcb->freeBlocks > 0xFFFF )
415 DebugStr("\p UpdateVCBFreeBlks: freeBlocks overflow!");
416 #endif
417 }
418
419
420 /*
421 ;________________________________________________________________________________
422 ;
423 ; Routine: BlkDealloc
424 ;
425 ; Function: Update the bitmap to deallocate a run of disk allocation blocks
426 ;
427 ; Input Arguments:
428 ; vcb - Pointer to ExtendedVCB for the volume to free space on
429 ; firstBlock - First allocation block to be freed
430 ; numBlocks - Number of allocation blocks to free up (must be > 0!)
431 ;
432 ; Output:
433 ; (result) - Result code
434 ;
435 ; Side effects:
436 ; The volume bitmap is read and updated; the volume bitmap cache may be changed.
437 ;
438 ; Modification history:
439 ;
440 ; <06Oct85> PWD Changed to check for error after calls to ReadBM and NextWord
441 ; Now calls NextBit to read successive bits from the bitmap
442 ;________________________________________________________________________________
443 */
444
445 OSErr BlockDeallocate (
446 ExtendedVCB *vcb, // Which volume to deallocate space on
447 UInt32 firstBlock, // First block in range to deallocate
448 UInt32 numBlocks) // Number of contiguous blocks to deallocate
449 {
450 OSErr err;
451
452 #if HFSInstrumentation
453 InstTraceClassRef trace;
454 InstEventTag eventTag;
455
456 err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:BlockDeallocate", 'hfs+', kInstEnableClassMask, &trace);
457 if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
458
459 eventTag = InstCreateEventTag();
460 InstLogTraceEvent( trace, eventTag, kInstStartEvent);
461 #endif
462
463 //
464 // If no blocks to deallocate, then exit early
465 //
466 if (numBlocks == 0) {
467 err = noErr;
468 goto Exit;
469 }
470
471 //
472 // Call internal routine to free the sequence of blocks
473 //
474 err = BlockMarkFree(vcb, firstBlock, numBlocks);
475 if (err)
476 goto Exit;
477
478 //
479 // Update the volume's free block count, and mark the VCB as dirty.
480 //
481 VCB_LOCK(vcb);
482 vcb->freeBlocks += numBlocks;
483 VCB_UNLOCK(vcb);
484 UpdateVCBFreeBlks( vcb );
485 MarkVCBDirty(vcb);
486
487 Exit:
488
489 #if HFSInstrumentation
490 InstLogTraceEvent( trace, eventTag, kInstEndEvent);
491 #endif
492
493 return err;
494 }
495
496
497 /*
498 ;_______________________________________________________________________
499 ;
500 ; Routine: UpdateFree
501 ; Arguments: vcb -- ExtendedVCB for volume
502 ;
503 ; Called By: MountVol
504 ; Function: This routine is used as part of the MountVol consistency check
505 ; to figure out the number of free allocation blocks in the volume.
506 ;
507 ; Modification History:
508 ; <08Sep85> LAK New today.
509 ; <06Oct85> PWD Added explicit check for errors after calls to ReadBM, NextWord
510 ; Now calls NextBit.
511 ;_______________________________________________________________________
512 */
513
514 OSErr UpdateFreeCount (
515 ExtendedVCB *vcb) // Volume whose free block count should be updated
516 {
517 OSErr err;
518 register UInt32 wordsLeft; // Number of words left in this bitmap block
519 register UInt32 numBlocks; // Number of blocks left to scan
520 register UInt32 freeCount; // Running count of free blocks found so far
521 register UInt32 temp;
522 UInt32 blockNum; // Block number of first block in this bitmap block
523 UInt32 *buffer = NULL; // Pointer to bitmap block
524 register UInt32 *currentWord; // Pointer to current word in bitmap block
525
526 #if HFSInstrumentation
527 InstTraceClassRef trace;
528 InstEventTag eventTag;
529
530 err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:UpdateFreeCount", 'hfs+', kInstEnableClassMask, &trace);
531 if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
532
533 eventTag = InstCreateEventTag();
534 InstLogTraceEvent( trace, eventTag, kInstStartEvent);
535 #endif
536
537 //
538 // Pre-read the first bitmap block
539 //
540
541 err = ReadBitmapBlock(vcb, 0, &buffer);
542 if (err != noErr) goto Exit;
543
544 //
545 // Initialize buffer stuff
546 //
547 currentWord = buffer;
548 wordsLeft = kWordsPerBlock;
549 numBlocks = vcb->totalBlocks;
550 freeCount = 0;
551 blockNum = 0;
552
553 //
554 // Scan whole words first
555 //
556
557 while (numBlocks >= kBitsPerWord) {
558 // See if it's time to move to the next bitmap block
559 if (wordsLeft == 0) {
560 // Read in the next bitmap block
561 blockNum += kBitsPerBlock; // generate a block number in the next bitmap block
562
563 #if EXPLICIT_BUFFER_RELEASES
564 err = RelBlock_glue((Ptr)buffer, rbDefault);
565 if (err != noErr) goto Exit;
566 buffer = NULL;
567 #endif
568 err = ReadBitmapBlock(vcb, blockNum, &buffer);
569 if (err != noErr) goto Exit;
570
571 // Readjust currentWord, wordsLeft
572 currentWord = buffer;
573 wordsLeft = kWordsPerBlock;
574 }
575
576 // We count free blocks by inverting the word in the bitmap and counting set bits.
577 temp = ~(*currentWord);
578 while (temp) {
579 ++freeCount;
580 temp &= temp-1; // this clears least significant bit that is currently set
581 }
582
583 numBlocks -= kBitsPerWord;
584 ++currentWord; // move to next word
585 --wordsLeft; // one less word left in this block
586 }
587
588 //
589 // Check any remaining blocks.
590 //
591
592 if (numBlocks != 0) {
593 if (wordsLeft == 0) {
594 // Read in the next bitmap block
595 blockNum += kBitsPerBlock; // generate a block number in the next bitmap block
596
597 #if EXPLICIT_BUFFER_RELEASES
598 err = RelBlock_glue((Ptr)buffer, rbDefault);
599 if (err != noErr) goto Exit;
600 buffer = NULL;
601 #endif
602 err = ReadBitmapBlock(vcb, blockNum, &buffer);
603 if (err != noErr) goto Exit;
604
605 // Readjust currentWord, wordsLeft
606 currentWord = buffer;
607 wordsLeft = kWordsPerBlock;
608 }
609
610 // We count free blocks by inverting the word in the bitmap and counting set bits.
611 temp = SWAP_BE32 (~(*currentWord));
612 while (numBlocks != 0) {
613 if (temp & kHighBitInWordMask)
614 ++freeCount;
615 temp <<= 1;
616 --numBlocks;
617 }
618 }
619
620 VCB_LOCK(vcb);
621 vcb->freeBlocks = freeCount;
622 VCB_UNLOCK(vcb);
623 UpdateVCBFreeBlks( vcb );
624
625 Exit:
626
627 #if EXPLICIT_BUFFER_RELEASES
628 if (buffer) {
629 (void)RelBlock_glue((Ptr)buffer, rbDefault); /* Ignore any additional errors */
630 };
631 #endif
632
633 #if HFSInstrumentation
634 InstLogTraceEvent( trace, eventTag, kInstEndEvent);
635 #endif
636
637 return err;
638 }
639
640
641
642 /*
643 ;_______________________________________________________________________
644 ;
645 ; Routine: AllocateFreeSpace
646 ; Arguments: vcb -- ExtendedVCB for volume
647 ;
648 ; Called By: HFSDiskInitComponent
649 ; Function: This routine is used as part of DiskInit to create an
650 ; embedded HFS+ volume.
651 ;
652 ; Note: Assumes that the free space is contiguous (true for a freshly erased disk)
653 ;_______________________________________________________________________
654 */
655
656 OSErr AllocateFreeSpace (
657 ExtendedVCB *vcb, // Volume whose free space is about to be expropriated
658 UInt32 *startBlock, // return where free space starts
659 UInt32 *actualBlocks) // return the number of blocks in free space
660 {
661 OSErr err;
662
663 err = BlockAllocateAny(vcb, 0, vcb->totalBlocks, vcb->freeBlocks, startBlock, actualBlocks);
664
665 if (err == noErr) {
666 VCB_LOCK(vcb);
667 vcb->freeBlocks = 0; // sorry, no more blocks left!
668 VCB_UNLOCK(vcb);
669 MarkVCBDirty(vcb);
670 }
671
672 return err;
673 }
674
675 /*
676 ;_______________________________________________________________________
677 ;
678 ; Routine: FileBytesToBlocks
679 ;
680 ; Function: Divide numerator by denominator, rounding up the result if there
681 ; was a remainder. This is frequently used for computing the number
682 ; of whole and/or partial blocks used by some count of bytes.
683 ; Actuall divides a 64 bit by a 32 bit into a 32bit result
684 ;
685 ; CAREFULL!!! THIS CAN CAUSE OVERFLOW....USER BEWARE!!!
686 ;_______________________________________________________________________
687 */
688 UInt32 FileBytesToBlocks(
689 SInt64 numerator,
690 UInt32 denominator)
691 {
692 UInt32 quotient;
693
694 quotient = (UInt32)(numerator / denominator);
695 if (quotient * denominator != numerator)
696 quotient++;
697
698 return quotient;
699 }
700
701
702
703 /*
704 ;_______________________________________________________________________
705 ;
706 ; Routine: ReadBitmapBlock
707 ;
708 ; Function: Read in a bitmap block corresponding to a given allocation
709 ; block. Return a pointer to the bitmap block.
710 ;
711 ; Inputs:
712 ; vcb -- Pointer to ExtendedVCB
713 ; block -- Allocation block whose bitmap block is desired
714 ;
715 ; Outputs:
716 ; buffer -- Pointer to bitmap block corresonding to "block"
717 ;_______________________________________________________________________
718 */
719 static OSErr ReadBitmapBlock(
720 ExtendedVCB *vcb,
721 UInt32 block,
722 UInt32 **buffer)
723 {
724 OSErr err;
725
726 #if HFSInstrumentation
727 InstTraceClassRef trace;
728 InstEventTag eventTag;
729
730 err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:ReadBitmapBlock", 'hfs+', kInstEnableClassMask, &trace);
731 if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
732
733 eventTag = block; // a cheap way to get the block number into the log
734 InstLogTraceEvent( trace, eventTag, kInstStartEvent);
735 #endif
736
737 err = noErr;
738
739 REQUIRE_FILE_LOCK(vcb->extentsRefNum, false); /* bitmap blocks are covered by the Extents B-tree lock */
740
741 if (vcb->vcbSigWord == kHFSSigWord) {
742 //
743 // HFS: Turn block number into physical block offset within the
744 // bitmap, and then the physical block within the volume.
745 //
746 block /= kBitsPerBlock; // block offset within bitmap
747 block += vcb->vcbVBMSt; // block within whole volume
748 }
749 else {
750 FCB *allocFile;
751 daddr_t startBlock;
752 size_t availableBytes;
753
754 //
755 // HFS+: Read from allocation file. We simply convert the block number into a byte
756 // offset within the allocation file and then determine which block that byte is in.
757 //
758 allocFile = GetFileControlBlock(vcb->allocationsRefNum);
759
760 //
761 // Find out which physical block holds byte #offset in allocation file. Note that we
762 // map only 1 byte (the one we asked for).
763 //
764 err = MapFileBlockC(vcb, allocFile, (size_t)1, (off_t)(block/kBitsPerByte), &startBlock, &availableBytes);
765 block = startBlock;
766 }
767
768 if (err == noErr) {
769 err = GetBlock_glue(
770 #if EXPLICIT_BUFFER_RELEASES
771 0, // No options
772 #else
773 gbReleaseMask, // Release block immediately. We only work on one
774 // block at a time. Call MarkBlock later if dirty.
775 #endif
776 block, // Physical block on volume
777 (Ptr *) buffer, // A place to return the buffer pointer
778 kNoFileReference, // Not a file read
779 vcb); // Volume to read from
780 }
781
782 #if HFSInstrumentation
783 InstLogTraceEvent( trace, eventTag, kInstEndEvent);
784 #endif
785
786 return err;
787 }
788
789
790
791 /*
792 _______________________________________________________________________
793
794 Routine: BlockAllocateContig
795
796 Function: Allocate a contiguous group of allocation blocks. The
797 allocation is all-or-nothing. The caller guarantees that
798 there are enough free blocks (though they may not be
799 contiguous, in which case this call will fail).
800
801 Inputs:
802 vcb Pointer to volume where space is to be allocated
803 startingBlock Preferred first block for allocation
804 minBlocks Minimum number of contiguous blocks to allocate
805 maxBlocks Maximum number of contiguous blocks to allocate
806
807 Outputs:
808 actualStartBlock First block of range allocated, or 0 if error
809 actualNumBlocks Number of blocks allocated, or 0 if error
810 _______________________________________________________________________
811 */
812 static OSErr BlockAllocateContig(
813 ExtendedVCB *vcb,
814 UInt32 startingBlock,
815 UInt32 minBlocks,
816 UInt32 maxBlocks,
817 UInt32 *actualStartBlock,
818 UInt32 *actualNumBlocks)
819 {
820 OSErr err;
821
822 //
823 // Find a contiguous group of blocks at least minBlocks long.
824 // Determine the number of contiguous blocks available (up
825 // to maxBlocks).
826 //
827 err = BlockFindContiguous(vcb, startingBlock, vcb->totalBlocks, minBlocks, maxBlocks,
828 actualStartBlock, actualNumBlocks);
829 if (err == dskFulErr) {
830 //\80\80 Should constrain the endingBlock here, so we don't bother looking for ranges
831 //\80\80 that start after startingBlock, since we already checked those.
832 err = BlockFindContiguous(vcb, 0, vcb->totalBlocks, minBlocks, maxBlocks,
833 actualStartBlock, actualNumBlocks);
834 }
835 if (err != noErr) goto Exit;
836
837 //
838 // Now mark those blocks allocated.
839 //
840 err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks);
841
842 Exit:
843 if (err != noErr) {
844 *actualStartBlock = 0;
845 *actualNumBlocks = 0;
846 }
847
848 return err;
849 }
850
851 extern OSErr LookupBufferMapping(caddr_t bufferAddress, struct buf **bpp, int *mappingIndexPtr);
852
853 /*
854 _______________________________________________________________________
855
856 Routine: BlockAllocateAny
857
858 Function: Allocate one or more allocation blocks. If there are fewer
859 free blocks than requested, all free blocks will be
860 allocated. The caller guarantees that there is at least
861 one free block.
862
863 Inputs:
864 vcb Pointer to volume where space is to be allocated
865 startingBlock Preferred first block for allocation
866 endingBlock Last block to check + 1
867 maxBlocks Maximum number of contiguous blocks to allocate
868
869 Outputs:
870 actualStartBlock First block of range allocated, or 0 if error
871 actualNumBlocks Number of blocks allocated, or 0 if error
872 _______________________________________________________________________
873 */
874 OSErr BlockAllocateAny(
875 ExtendedVCB *vcb,
876 UInt32 startingBlock,
877 register UInt32 endingBlock,
878 UInt32 maxBlocks,
879 UInt32 *actualStartBlock,
880 UInt32 *actualNumBlocks)
881 {
882 OSErr err;
883 register UInt32 block; // current block number
884 register UInt32 currentWord; // Pointer to current word within bitmap block
885 register UInt32 bitMask; // Word with given bits already set (ready to OR in)
886 register UInt32 wordsLeft; // Number of words left in this bitmap block
887 UInt32 *buffer = NULL;
888 UInt32 *currCache = NULL;
889
890 #if HFS_DIAGNOSTIC
891 struct buf *bp = NULL;
892 int mappingEntry;
893 #endif
894
895 // Since this routine doesn't wrap around
896 if (maxBlocks > (endingBlock - startingBlock)) {
897 maxBlocks = endingBlock - startingBlock;
898 }
899
900 DBG_TREE (("\nAllocating starting at %ld, maxblocks %ld\n", startingBlock, maxBlocks));
901 //
902 // Pre-read the first bitmap block
903 //
904 err = ReadBitmapBlock(vcb, startingBlock, &currCache);
905 DBG_TREE (("\n1. Read bit map at %ld, buffer is 0x%x\n", startingBlock, (int)currCache));
906 if (err != noErr) goto Exit;
907 buffer = currCache;
908 MarkBlock_glue((Ptr) currCache); // this block will be dirty
909 DBG_ASSERT(! LookupBufferMapping((caddr_t)currCache, &bp, &mappingEntry));
910
911 //
912 // Set up the current position within the block
913 //
914 {
915 UInt32 wordIndexInBlock;
916
917 wordIndexInBlock = (startingBlock & kBitsWithinBlockMask) / kBitsPerWord;
918 buffer += wordIndexInBlock;
919 wordsLeft = kWordsPerBlock - wordIndexInBlock;
920 currentWord = SWAP_BE32 (*buffer);
921 bitMask = kHighBitInWordMask >> (startingBlock & kBitsWithinWordMask);
922 }
923
924 //
925 // Find the first unallocated block
926 //
927 block=startingBlock;
928 while (block < endingBlock) {
929 if ((currentWord & bitMask) == 0)
930 break;
931
932 // Next bit
933 ++block;
934 bitMask >>= 1;
935 if (bitMask == 0) {
936 // Next word
937 bitMask = kHighBitInWordMask;
938 ++buffer;
939
940 if (--wordsLeft == 0) {
941 // Next block
942 #if EXPLICIT_BUFFER_RELEASES
943 DBG_ASSERT(! LookupBufferMapping((caddr_t)currCache, &bp, &mappingEntry));
944 err = RelBlock_glue((Ptr)currCache, rbDefault);
945 if (err != noErr) goto Exit;
946 buffer = currCache = NULL;
947 #endif
948 err = ReadBitmapBlock(vcb, block, &currCache);
949 if (err != noErr) goto Exit;
950 buffer = currCache;
951 DBG_TREE (("\n2. Read bit map at %ld, buffer is 0x%x\n", block, (int)currCache));
952 DBG_ASSERT(! LookupBufferMapping((caddr_t)currCache, &bp, &mappingEntry));
953 MarkBlock_glue((Ptr) currCache); // this block will be dirty
954
955 wordsLeft = kWordsPerBlock;
956 }
957
958 currentWord = SWAP_BE32 (*buffer);
959 }
960 }
961
962 // Did we get to the end of the bitmap before finding a free block?
963 // If so, then couldn't allocate anything.
964 if (block == endingBlock) {
965 err = dskFulErr;
966 goto Exit;
967 }
968
969 // Return the first block in the allocated range
970 *actualStartBlock = block;
971
972 // If we could get the desired number of blocks before hitting endingBlock,
973 // then adjust endingBlock so we won't keep looking. Ideally, the comparison
974 // would be (block + maxBlocks) < endingBlock, but that could overflow. The
975 // comparison below yields identical results, but without overflow.
976 if (block < (endingBlock-maxBlocks)) {
977 endingBlock = block + maxBlocks; // if we get this far, we've found enough
978 }
979
980 //
981 // Allocate all of the consecutive blocks
982 //
983 while ((currentWord & bitMask) == 0) {
984 // Allocate this block
985 currentWord |= bitMask;
986
987 // Move to the next block. If no more, then exit.
988 ++block;
989 if (block == endingBlock)
990 break;
991
992 // Next bit
993 bitMask >>= 1;
994 if (bitMask == 0) {
995 *buffer = SWAP_BE32 (currentWord); // update value in bitmap
996
997 // Next word
998 bitMask = kHighBitInWordMask;
999 ++buffer;
1000
1001 if (--wordsLeft == 0) {
1002 // Next block
1003 #if EXPLICIT_BUFFER_RELEASES
1004 DBG_ASSERT(! LookupBufferMapping((caddr_t)currCache, &bp, &mappingEntry));
1005 err = RelBlock_glue((Ptr)currCache, rbDefault);
1006 if (err != noErr) goto Exit;
1007 buffer = currCache = NULL;
1008 #endif
1009 err = ReadBitmapBlock(vcb, block, &currCache);
1010 if (err != noErr) goto Exit;
1011 buffer = currCache;
1012 DBG_TREE (("\n3. Read bit map at %ld, buffer is 0x%x\n", block, (int)currCache));
1013 DBG_ASSERT(! LookupBufferMapping((caddr_t)currCache, &bp, &mappingEntry));
1014 MarkBlock_glue((Ptr) currCache); // this block will be dirty
1015
1016 wordsLeft = kWordsPerBlock;
1017 }
1018
1019 currentWord = SWAP_BE32 (*buffer);
1020 }
1021 }
1022 *buffer = SWAP_BE32 (currentWord); // update the last change
1023
1024 Exit:
1025 if (err == noErr) {
1026 *actualNumBlocks = block - *actualStartBlock;
1027 }
1028 else {
1029 *actualStartBlock = 0;
1030 *actualNumBlocks = 0;
1031 }
1032
1033 #if EXPLICIT_BUFFER_RELEASES
1034 if (currCache) {
1035 DBG_ASSERT(! LookupBufferMapping((caddr_t)currCache, &bp, &mappingEntry));
1036 (void)RelBlock_glue((Ptr)currCache, rbDefault); /* Ignore any additional errors */
1037 };
1038 #endif
1039
1040 return err;
1041 }
1042
1043
1044
1045 /*
1046 _______________________________________________________________________
1047
1048 Routine: BlockMarkAllocated
1049
1050 Function: Mark a contiguous group of blocks as allocated (set in the
1051 bitmap). It assumes those bits are currently marked
1052 deallocated (clear in the bitmap).
1053
1054 Inputs:
1055 vcb Pointer to volume where space is to be allocated
1056 startingBlock First block number to mark as allocated
1057 numBlocks Number of blocks to mark as allocated
1058 _______________________________________________________________________
1059 */
1060 static OSErr BlockMarkAllocated(
1061 ExtendedVCB *vcb,
1062 UInt32 startingBlock,
1063 register UInt32 numBlocks)
1064 {
1065 OSErr err;
1066 register UInt32 *currentWord; // Pointer to current word within bitmap block
1067 register UInt32 wordsLeft; // Number of words left in this bitmap block
1068 register UInt32 bitMask; // Word with given bits already set (ready to OR in)
1069 UInt32 firstBit; // Bit index within word of first bit to allocate
1070 UInt32 numBits; // Number of bits in word to allocate
1071 UInt32 *buffer = NULL;
1072
1073 #if HFSInstrumentation
1074 InstTraceClassRef trace;
1075 InstEventTag eventTag;
1076
1077 err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:BlockMarkAllocated", 'hfs+', kInstEnableClassMask, &trace);
1078 if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
1079
1080 eventTag = InstCreateEventTag();
1081 InstLogTraceEvent( trace, eventTag, kInstStartEvent);
1082 #endif
1083
1084 //
1085 // Pre-read the bitmap block containing the first word of allocation
1086 //
1087
1088 err = ReadBitmapBlock(vcb, startingBlock, &buffer);
1089 if (err != noErr) goto Exit;
1090 MarkBlock_glue((Ptr) buffer); // this block will be dirty
1091
1092 //
1093 // Initialize currentWord, and wordsLeft.
1094 //
1095 {
1096 UInt32 wordIndexInBlock;
1097
1098 wordIndexInBlock = (startingBlock & kBitsWithinBlockMask) / kBitsPerWord;
1099 currentWord = buffer + wordIndexInBlock;
1100 wordsLeft = kWordsPerBlock - wordIndexInBlock;
1101 }
1102
1103 //
1104 // If the first block to allocate doesn't start on a word
1105 // boundary in the bitmap, then treat that first word
1106 // specially.
1107 //
1108
1109 firstBit = startingBlock % kBitsPerWord;
1110 if (firstBit != 0) {
1111 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit
1112 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word
1113 if (numBits > numBlocks) {
1114 numBits = numBlocks; // entire allocation is inside this one word
1115 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last
1116 }
1117 #if DEBUG_BUILD
1118 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1119 DebugStr("\pFATAL: blocks already allocated!");
1120 //err = fsDSIntErr;
1121 //goto Exit;
1122 }
1123 #endif
1124 *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap
1125 numBlocks -= numBits; // adjust number of blocks left to allocate
1126
1127 ++currentWord; // move to next word
1128 --wordsLeft; // one less word left in this block
1129 }
1130
1131 //
1132 // Allocate whole words (32 blocks) at a time.
1133 //
1134
1135 bitMask = kAllBitsSetInWord; // put this in a register for 68K
1136 while (numBlocks >= kBitsPerWord) {
1137 if (wordsLeft == 0) {
1138 // Read in the next bitmap block
1139 startingBlock += kBitsPerBlock; // generate a block number in the next bitmap block
1140
1141 #if EXPLICIT_BUFFER_RELEASES
1142 err = RelBlock_glue((Ptr)buffer, rbDefault);
1143 if (err != noErr) goto Exit;
1144 buffer = NULL;
1145 #endif
1146 err = ReadBitmapBlock(vcb, startingBlock, &buffer);
1147 if (err != noErr) goto Exit;
1148 MarkBlock_glue((Ptr) buffer); // this block will be dirty
1149
1150 // Readjust currentWord and wordsLeft
1151 currentWord = buffer;
1152 wordsLeft = kWordsPerBlock;
1153 }
1154 #if DEBUG_BUILD
1155 if (*currentWord != 0) {
1156 DebugStr("\pFATAL: blocks already allocated!");
1157 //err = fsDSIntErr;
1158 //goto Exit;
1159 }
1160 #endif
1161 *currentWord = SWAP_BE32 (bitMask);
1162 numBlocks -= kBitsPerWord;
1163
1164 ++currentWord; // move to next word
1165 --wordsLeft; // one less word left in this block
1166 }
1167
1168 //
1169 // Allocate any remaining blocks.
1170 //
1171
1172 if (numBlocks != 0) {
1173 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits
1174 if (wordsLeft == 0) {
1175 // Read in the next bitmap block
1176 startingBlock += kBitsPerBlock; // generate a block number in the next bitmap block
1177
1178 #if EXPLICIT_BUFFER_RELEASES
1179 err = RelBlock_glue((Ptr)buffer, rbDefault);
1180 if (err != noErr) goto Exit;
1181 buffer = NULL;
1182 #endif
1183 err = ReadBitmapBlock(vcb, startingBlock, &buffer);
1184 if (err != noErr) goto Exit;
1185 MarkBlock_glue((Ptr) buffer); // this block will be dirty
1186
1187 // Readjust currentWord and wordsLeft
1188 currentWord = buffer;
1189 wordsLeft = kWordsPerBlock;
1190 }
1191 #if DEBUG_BUILD
1192 if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
1193 DebugStr("\pFATAL: blocks already allocated!");
1194 //err = fsDSIntErr;
1195 //goto Exit;
1196 }
1197 #endif
1198 *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap
1199
1200 // No need to update currentWord or wordsLeft
1201 }
1202
1203 Exit:
1204
1205 #if EXPLICIT_BUFFER_RELEASES
1206 if (buffer) {
1207 (void)RelBlock_glue((Ptr)buffer, rbDefault); /* Ignore any additional errors */
1208 };
1209 #endif
1210
1211 #if HFSInstrumentation
1212 InstLogTraceEvent( trace, eventTag, kInstEndEvent);
1213 #endif
1214
1215 return err;
1216 }
1217
1218
1219
1220 /*
1221 _______________________________________________________________________
1222
1223 Routine: BlockMarkFree
1224
1225 Function: Mark a contiguous group of blocks as free (clear in the
1226 bitmap). It assumes those bits are currently marked
1227 allocated (set in the bitmap).
1228
1229 Inputs:
1230 vcb Pointer to volume where space is to be freed
1231 startingBlock First block number to mark as freed
1232 numBlocks Number of blocks to mark as freed
1233 _______________________________________________________________________
1234 */
1235 static OSErr BlockMarkFree(
1236 ExtendedVCB *vcb,
1237 UInt32 startingBlock,
1238 register UInt32 numBlocks)
1239 {
1240 OSErr err;
1241 register UInt32 *currentWord; // Pointer to current word within bitmap block
1242 register UInt32 wordsLeft; // Number of words left in this bitmap block
1243 register UInt32 bitMask; // Word with given bits already set (ready to OR in)
1244 UInt32 firstBit; // Bit index within word of first bit to allocate
1245 UInt32 numBits; // Number of bits in word to allocate
1246 UInt32 *buffer = NULL;
1247
1248 #if HFSInstrumentation
1249 InstTraceClassRef trace;
1250 InstEventTag eventTag;
1251
1252 err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:BlockMarkFree", 'hfs+', kInstEnableClassMask, &trace);
1253 if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
1254
1255 eventTag = InstCreateEventTag();
1256 InstLogTraceEvent( trace, eventTag, kInstStartEvent);
1257 #endif
1258
1259 //
1260 // Pre-read the bitmap block containing the first word of allocation
1261 //
1262
1263 err = ReadBitmapBlock(vcb, startingBlock, &buffer);
1264 if (err != noErr) goto Exit;
1265 MarkBlock_glue((Ptr) buffer); // this block will be dirty
1266
1267 //
1268 // Initialize currentWord, and wordsLeft.
1269 //
1270 {
1271 UInt32 wordIndexInBlock;
1272
1273 wordIndexInBlock = (startingBlock & kBitsWithinBlockMask) / kBitsPerWord;
1274 currentWord = buffer + wordIndexInBlock;
1275 wordsLeft = kWordsPerBlock - wordIndexInBlock;
1276 }
1277
1278 //
1279 // If the first block to free doesn't start on a word
1280 // boundary in the bitmap, then treat that first word
1281 // specially.
1282 //
1283
1284 firstBit = startingBlock % kBitsPerWord;
1285 if (firstBit != 0) {
1286 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit
1287 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word
1288 if (numBits > numBlocks) {
1289 numBits = numBlocks; // entire allocation is inside this one word
1290 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last
1291 }
1292 #if DEBUG_BUILD
1293 if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
1294 DebugStr("\pFATAL: blocks not allocated!");
1295 //err = fsDSIntErr;
1296 //goto Exit;
1297 }
1298 #endif
1299 *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap
1300 numBlocks -= numBits; // adjust number of blocks left to free
1301
1302 ++currentWord; // move to next word
1303 --wordsLeft; // one less word left in this block
1304 }
1305
1306 //
1307 // Allocate whole words (32 blocks) at a time.
1308 //
1309
1310 while (numBlocks >= kBitsPerWord) {
1311 if (wordsLeft == 0) {
1312 // Read in the next bitmap block
1313 startingBlock += kBitsPerBlock; // generate a block number in the next bitmap block
1314
1315 #if EXPLICIT_BUFFER_RELEASES
1316 err = RelBlock_glue((Ptr)buffer, rbDefault);
1317 if (err != noErr) goto Exit;
1318 buffer = NULL;
1319 #endif
1320 err = ReadBitmapBlock(vcb, startingBlock, &buffer);
1321 if (err != noErr) goto Exit;
1322 MarkBlock_glue((Ptr) buffer); // this block will be dirty
1323
1324 // Readjust currentWord and wordsLeft
1325 currentWord = buffer;
1326 wordsLeft = kWordsPerBlock;
1327 }
1328
1329 #if DEBUG_BUILD
1330 if (*currentWord != SWAP_BE32 (kAllBitsSetInWord)) {
1331 DebugStr("\pFATAL: blocks not allocated!");
1332 //err = fsDSIntErr;
1333 //goto Exit;
1334 }
1335 #endif
1336 *currentWord = 0; // clear the entire word
1337 numBlocks -= kBitsPerWord;
1338
1339 ++currentWord; // move to next word
1340 --wordsLeft; // one less word left in this block
1341 }
1342
1343 //
1344 // Allocate any remaining blocks.
1345 //
1346
1347 if (numBlocks != 0) {
1348 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits
1349 if (wordsLeft == 0) {
1350 // Read in the next bitmap block
1351 startingBlock += kBitsPerBlock; // generate a block number in the next bitmap block
1352
1353 #if EXPLICIT_BUFFER_RELEASES
1354 err = RelBlock_glue((Ptr)buffer, rbDefault);
1355 if (err != noErr) goto Exit;
1356 buffer = NULL;
1357 #endif
1358 err = ReadBitmapBlock(vcb, startingBlock, &buffer);
1359 if (err != noErr) goto Exit;
1360 MarkBlock_glue((Ptr) buffer); // this block will be dirty
1361
1362 // Readjust currentWord and wordsLeft
1363 currentWord = buffer;
1364 wordsLeft = kWordsPerBlock;
1365 }
1366 #if DEBUG_BUILD
1367 if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
1368 DebugStr("\pFATAL: blocks not allocated!");
1369 //err = fsDSIntErr;
1370 //goto Exit;
1371 }
1372 #endif
1373 *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap
1374
1375 // No need to update currentWord or wordsLeft
1376 }
1377
1378 Exit:
1379
1380 #if EXPLICIT_BUFFER_RELEASES
1381 if (buffer) {
1382 (void)RelBlock_glue((Ptr)buffer, rbDefault); /* Ignore any additional errors */
1383 };
1384 #endif
1385
1386 #if HFSInstrumentation
1387 InstLogTraceEvent( trace, eventTag, kInstEndEvent);
1388 #endif
1389
1390 return err;
1391 }
1392
1393
1394 /*
1395 _______________________________________________________________________
1396
1397 Routine: BlockFindContiguous
1398
1399 Function: Find a contiguous range of blocks that are free (bits
1400 clear in the bitmap). If a contiguous range of the
1401 minimum size can't be found, an error will be returned.
1402
1403 \80\80 It would be nice if we could skip over whole words
1404 \80\80 with all bits set.
1405
1406 \80\80 When we find a bit set, and are about to set freeBlocks
1407 \80\80 to 0, we should check to see whether there are still
1408 \80\80 minBlocks bits left in the bitmap.
1409
1410 Inputs:
1411 vcb Pointer to volume where space is to be allocated
1412 startingBlock Preferred first block of range
1413 endingBlock Last possible block in range + 1
1414 minBlocks Minimum number of blocks needed. Must be > 0.
1415 maxBlocks Maximum (ideal) number of blocks desired
1416
1417 Outputs:
1418 actualStartBlock First block of range found, or 0 if error
1419 actualNumBlocks Number of blocks found, or 0 if error
1420 _______________________________________________________________________
1421 */
1422 /*
1423 _________________________________________________________________________________________
1424 (DSH) 5/8/97 Description of BlockFindContiguous() algorithm
1425 Finds a contiguous range of free blocks by searching back to front. This
1426 allows us to skip ranges of bits knowing that they are not candidates for
1427 a match because they are too small. The below ascii diagrams illustrate
1428 the algorithm in action.
1429
1430 Representation of a piece of a volume bitmap file
1431 If BlockFindContiguous() is called with minBlocks == 10, maxBlocks == 20
1432
1433
1434 Fig. 1 initialization of variables, "<--" represents direction of travel
1435
1436 startingBlock (passed in)
1437 |
1438 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1439 | <--|
1440 stopBlock currentBlock freeBlocks == 0
1441 countedFreeBlocks == 0
1442
1443 Fig. 2 dirty bit found
1444
1445 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1446 | |
1447 stopBlock currentBlock freeBlocks == 3
1448 countedFreeBlocks == 0
1449
1450 Fig. 3 reset variables to search for remainder of minBlocks
1451
1452 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1453 |_________________| | |
1454 Unsearched stopBlock currentBlock freeBlocks == 0
1455 countedFreeBlocks == 3
1456
1457 Fig. 4 minBlocks contiguous blocks found, *actualStartBlock is set
1458
1459 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1460 |_________________| |
1461 Unsearched stopBlock freeBlocks == 7
1462 currentBlock countedFreeBlocks == 3
1463
1464 Fig. 5 Now run it forwards trying to accumalate up to maxBlocks if possible
1465
1466 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1467 |_________________| | -->
1468 Unsearched currentBlock
1469 *actualNumBlocks == 10
1470
1471 Fig. 6 Dirty bit is found, return actual number of contiguous blocks found
1472
1473 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1474 |_________________| |
1475 Unsearched currentBlock
1476 *actualNumBlocks == 16
1477 _________________________________________________________________________________________
1478 */
1479
1480 static OSErr BlockFindContiguous(
1481 ExtendedVCB *vcb,
1482 UInt32 startingBlock,
1483 register UInt32 endingBlock,
1484 UInt32 minBlocks,
1485 UInt32 maxBlocks,
1486 UInt32 *actualStartBlock,
1487 UInt32 *actualNumBlocks)
1488 {
1489 OSErr err;
1490 register UInt32 bitMask; // mask of bit within word for currentBlock
1491 register UInt32 tempWord; // bitmap word currently being examined
1492 register UInt32 freeBlocks; // number of contiguous free blocks so far
1493 register UInt32 currentBlock; // block number we're currently examining
1494 UInt32 wordsLeft; // words remaining in bitmap block
1495 UInt32 *buffer = NULL;
1496 register UInt32 *currentWord;
1497
1498 UInt32 stopBlock; // when all blocks until stopBlock are free, we found enough
1499 UInt32 countedFreeBlocks; // how many contiguous free block behind stopBlock
1500 UInt32 currentSector; // which allocations file sector
1501
1502 #if HFSInstrumentation
1503 InstTraceClassRef trace;
1504 InstEventTag eventTag;
1505
1506 err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:BlockFindContiguous", 'hfs+', kInstEnableClassMask, &trace);
1507 if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
1508
1509 eventTag = InstCreateEventTag();
1510 InstLogTraceEvent( trace, eventTag, kInstStartEvent);
1511 #endif
1512
1513 if ((endingBlock - startingBlock) < minBlocks) {
1514 // The set of blocks we're checking is smaller than the minimum number
1515 // of blocks, so we couldn't possibly find a good range.
1516 err = dskFulErr;
1517 goto Exit;
1518 }
1519
1520 // Search for min blocks from back to front.
1521 // If min blocks is found, advance the allocation pointer up to max blocks
1522
1523 //
1524 // Pre-read the bitmap block containing currentBlock
1525 //
1526 stopBlock = startingBlock;
1527 currentBlock = startingBlock + minBlocks - 1; // (-1) to include startingBlock
1528
1529 err = ReadBitmapBlock( vcb, currentBlock, &buffer );
1530 if ( err != noErr ) goto Exit;
1531
1532 //
1533 // Init buffer, currentWord, wordsLeft, and bitMask
1534 //
1535 {
1536 UInt32 wordIndexInBlock;
1537
1538 wordIndexInBlock = ( currentBlock & kBitsWithinBlockMask ) / kBitsPerWord;
1539 currentWord = buffer + wordIndexInBlock;
1540
1541 wordsLeft = wordIndexInBlock;
1542 tempWord = SWAP_BE32 (*currentWord);
1543 bitMask = kHighBitInWordMask >> ( currentBlock & kBitsWithinWordMask );
1544 currentSector = currentBlock / kBitsPerBlock;
1545 }
1546
1547 //
1548 // Look for maxBlocks free blocks. If we find an allocated block,
1549 // see if we've found minBlocks.
1550 //
1551 freeBlocks = 0;
1552 countedFreeBlocks = 0;
1553
1554 while ( currentBlock >= stopBlock )
1555 {
1556 // Check current bit
1557 if ((tempWord & bitMask) == 0)
1558 {
1559 ++freeBlocks;
1560 }
1561 else // Used bitmap block found
1562 {
1563 if ( ( freeBlocks + countedFreeBlocks ) >= minBlocks )
1564 {
1565 break; // Found enough
1566 }
1567 else
1568 {
1569 // We found a dirty bit, so we want to check if the next (minBlocks-freeBlocks) blocks
1570 // are free beyond what we have already checked. At Fig.2 setting up for Fig.3
1571
1572 stopBlock = currentBlock + 1 + freeBlocks; // Advance stop condition
1573 currentBlock += minBlocks;
1574 if ( currentBlock >= endingBlock ) break;
1575 countedFreeBlocks = freeBlocks;
1576 freeBlocks = 0; // Not enough; look for another range
1577
1578 if ( currentSector != currentBlock / kBitsPerBlock )
1579 {
1580 #if EXPLICIT_BUFFER_RELEASES
1581 err = RelBlock_glue((Ptr)buffer, rbDefault);
1582 if (err != noErr) goto Exit;
1583 buffer = NULL;
1584 #endif
1585 err = ReadBitmapBlock( vcb, currentBlock, &buffer );
1586 if (err != noErr) goto Exit;
1587 currentSector = currentBlock / kBitsPerBlock;
1588 }
1589
1590 wordsLeft = ( currentBlock & kBitsWithinBlockMask ) / kBitsPerWord;
1591 currentWord = buffer + wordsLeft;
1592 tempWord = SWAP_BE32 (*currentWord);
1593 bitMask = kHighBitInWordMask >> ( currentBlock & kBitsWithinWordMask );
1594
1595 continue; // Back to the while loop
1596 }
1597 }
1598
1599 // Move to next bit
1600 --currentBlock;
1601 bitMask <<= 1;
1602 if (bitMask == 0) // On a word boundry, start masking words
1603 {
1604 bitMask = kLowBitInWordMask;
1605
1606 // Move to next word
1607 NextWord:
1608 if ( wordsLeft != 0 )
1609 {
1610 --currentWord;
1611 --wordsLeft;
1612 }
1613 else
1614 {
1615 // Read in the next bitmap block
1616 #if EXPLICIT_BUFFER_RELEASES
1617 err = RelBlock_glue((Ptr)buffer, rbDefault);
1618 if (err != noErr) goto Exit;
1619 buffer = NULL;
1620 #endif
1621 err = ReadBitmapBlock( vcb, currentBlock, &buffer );
1622 if (err != noErr) goto Exit;
1623
1624 // Adjust currentWord, wordsLeft, currentSector
1625 currentSector = currentBlock / kBitsPerBlock;
1626 currentWord = buffer + kWordsPerBlock - 1; // Last word in buffer
1627 wordsLeft = kWordsPerBlock - 1;
1628 }
1629
1630 tempWord = SWAP_BE32 (*currentWord); // Grab the current word
1631
1632 //
1633 // If we found a whole word of free blocks, quickly skip over it.
1634 // NOTE: we could actually go beyond the end of the bitmap if the
1635 // number of allocation blocks on the volume is not a multiple of
1636 // 32. If this happens, we'll adjust currentBlock and freeBlocks
1637 // after the loop.
1638 //
1639 if ( tempWord == 0 )
1640 {
1641 freeBlocks += kBitsPerWord;
1642 currentBlock -= kBitsPerWord;
1643 if ( freeBlocks + countedFreeBlocks >= minBlocks )
1644 break; // Found enough
1645 goto NextWord;
1646 }
1647 }
1648 }
1649
1650 if ( freeBlocks + countedFreeBlocks < minBlocks )
1651 {
1652 *actualStartBlock = 0;
1653 *actualNumBlocks = 0;
1654 err = dskFulErr;
1655 goto Exit;
1656 }
1657
1658 //
1659 // When we get here, we know we've found minBlocks continuous space.
1660 // At Fig.4, setting up for Fig.5
1661 // From here we do a forward search accumalating additional free blocks.
1662 //
1663
1664 *actualNumBlocks = minBlocks;
1665 *actualStartBlock = stopBlock - countedFreeBlocks; // ActualStartBlock is set to return to the user
1666 currentBlock = *actualStartBlock + minBlocks; // Right after found free space
1667
1668 // Now lets see if we can run the actualNumBlocks number all the way up to maxBlocks
1669 if ( currentSector != currentBlock / kBitsPerBlock )
1670 {
1671 #if EXPLICIT_BUFFER_RELEASES
1672 err = RelBlock_glue((Ptr)buffer, rbDefault);
1673 if (err != noErr) goto Exit;
1674 buffer = NULL;
1675 #endif
1676 err = ReadBitmapBlock( vcb, currentBlock, &buffer );
1677 if (err != noErr)
1678 {
1679 err = noErr; // We already found the space
1680 goto Exit;
1681 }
1682
1683 currentSector = currentBlock / kBitsPerBlock;
1684 }
1685
1686 //
1687 // Init buffer, currentWord, wordsLeft, and bitMask
1688 //
1689 {
1690 UInt32 wordIndexInBlock;
1691
1692 wordIndexInBlock = (currentBlock & kBitsWithinBlockMask) / kBitsPerWord;
1693 currentWord = buffer + wordIndexInBlock;
1694 tempWord = SWAP_BE32 (*currentWord);
1695 wordsLeft = kWordsPerBlock - wordIndexInBlock;
1696 bitMask = kHighBitInWordMask >> (currentBlock & kBitsWithinWordMask);
1697 }
1698
1699 if ( *actualNumBlocks < maxBlocks )
1700 {
1701 while ( currentBlock < endingBlock )
1702 {
1703
1704 if ( (tempWord & bitMask) == 0 )
1705 {
1706 *actualNumBlocks += 1;
1707
1708 if ( *actualNumBlocks == maxBlocks )
1709 break;
1710 }
1711 else
1712 {
1713 break;
1714 }
1715
1716 // Move to next bit
1717 ++currentBlock;
1718 bitMask >>= 1;
1719 if (bitMask == 0)
1720 {
1721 bitMask = kHighBitInWordMask;
1722 ++currentWord;
1723
1724 if ( --wordsLeft == 0)
1725 {
1726 #if EXPLICIT_BUFFER_RELEASES
1727 err = RelBlock_glue((Ptr)buffer, rbDefault);
1728 if (err != noErr) goto Exit;
1729 buffer = NULL;
1730 #endif
1731 err = ReadBitmapBlock(vcb, currentBlock, &buffer);
1732 if (err != noErr) break;
1733
1734 // Adjust currentWord, wordsLeft
1735 currentWord = buffer;
1736 wordsLeft = kWordsPerBlock;
1737 }
1738 tempWord = SWAP_BE32 (*currentWord); // grab the current word
1739 }
1740 }
1741 }
1742
1743 Exit:
1744
1745 #if EXPLICIT_BUFFER_RELEASES
1746 if (buffer) {
1747 (void)RelBlock_glue((Ptr)buffer, rbDefault); /* Ignore any additional errors */
1748 };
1749 #endif
1750
1751 #if HFSInstrumentation
1752 InstLogTraceEvent( trace, eventTag, kInstEndEvent);
1753 #endif
1754
1755 return err;
1756 }
1757
1758
mirror of XNU