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