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