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


92ae16ad6fb38034e3f6b557b3c35dc2da2e4a46
[apple/xnu.git] / bsd / hfs / hfscommon / Misc / FileExtentMapping.c
1 /*
2 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * The contents of this file constitute Original Code as defined in and
7 * are subject to the Apple Public Source License Version 1.1 (the
8 * "License"). You may not use this file except in compliance with the
9 * License. Please obtain a copy of the License at
10 * http://www.apple.com/publicsource and read it before using this file.
11 *
12 * This Original Code and all software distributed under the License are
13 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17 * License for the specific language governing rights and limitations
18 * under the License.
19 *
20 * @APPLE_LICENSE_HEADER_END@
21 */
22 /*
23 File: FileExtentMapping.c
24
25 Contains: xxx put contents here xxx
26
27 Version: HFS Plus 1.0
28
29 Written by: Dave Heller, Mark Day
30
31 Copyright: © 1996-1999 by Apple Computer, Inc., all rights reserved.
32
33 File Ownership:
34
35 DRI: Mark Day
36
37 Other Contact: xxx put other contact here xxx
38
39 Technology: xxx put technology here xxx
40
41 Writers:
42
43 (DSH) Deric Horn
44 (msd) Mark Day
45 (djb) Don Brady
46
47 Change History (most recent first):
48 <MacOSX> 9/9/99 djb Fix fcbModifiedMask flag testing logic.
49 <MacOSX> 8/25/98 djb Flush extents b-tree header if dirty (2371088).
50 <MacOSX> 6/30/98 djb Add functions NodesAreContiguous and ExtentsAreIntegral (for radar #2249539).
51 <MacOSX> 6/23/98 djb Changed DeallocFile to DeleteFile which now deletes the catalog record.
52 Fixed UpdateExtentRecord to pass correct fcb to Btree routines. Fixed
53 hfs+ bug in CreateExtentRecord (double dereference).
54 <MacOSX> 5/20/98 djb In ExtendFileC don't lie about the peof! (radar #2230094).
55 <MacOSX> 4/17/98 djb Add VCB locking.
56 <MacOSX> 4/2/98 djb Switch over to real BTree interface (no more BTreeWrapper.c).
57 <MacOSX> 3/31/98 djb Sync up with final HFSVolumes.h header file.
58
59 <CS24> 1/23/98 msd Bug 2208024: AllocContig is actually allocating one extent even
60 though there is not enough contiguous space.
61 <CS23> 12/2/97 DSH GetFCBExtentRecord no longer static so DFA can use it.
62 <CS22> 10/20/97 msd When allocating more space for a file, do the clump size
63 calculations in ExtendFileC, not BlockAllocate. Undo change from
64 <CS18>.
65 <CS21> 10/17/97 msd Conditionalize DebugStrs.
66 <CS20> 10/16/97 msd Simplify the code path for MapFileBlockC (logical to physical
67 block mapping) in the typical case where the file isn't
68 fragmented so badly that it has extents in the extents B-tree.
69 Simplified some of the calculations for all cases.
70 <CS19> 10/13/97 DSH FindExtentRecord & DeleteExtentRecord are also being used by DFA
71 no longer static.
72 <CS18> 10/6/97 msd When extending a file, set the physical EOF to include any extra
73 space allocated due to a file's clump size.
74 <CS17> 9/19/97 msd Remove the MapLogicalToPhysical SPI. It was never used and is
75 not being tested anyway.
76 <CS16> 9/5/97 msd In CompareExtentKeys and CompareExtentKeysPlus, use the symbolic
77 constants for key length. Don't DebugStr unless DEBUG_BUILD is
78 set.
79 <CS15> 7/24/97 djb Add instrumentation to MapFileBlockC
80 <CS14> 7/16/97 DSH FilesInternal.i renamed FileMgrInternal.i to avoid name
81 collision
82 <CS13> 7/15/97 DSH AdjEOF() mark the FCB as modified. (1664389)
83 <CS12> 7/8/97 DSH Loading PrecompiledHeaders from define passed in on C line
84 <CS11> 7/3/97 msd Bug #1663518. Remove DebugStr when setting the FCB extent record
85 for a volume control file.
86 <CS10> 6/27/97 msd Moved enum kFirstFileRefnum to FilesInternal.
87 <CS9> 6/24/97 djb Include "CatalogPrivate.h"
88 <CS8> 6/16/97 msd Finish implementation of CreateLargeFile SPI.
89 <CS7> 6/12/97 msd Add stub for CreateLargeFile SPI.
90 <CS6> 6/5/97 msd Add MapLogicalToPhysical.
91 <CS5> 6/2/97 msd In TruncateFileC, don't update the extent record unless it was
92 actually changed (prevents extra updates when truncating to the
93 end of the extent, and it is the last extent of the file.) Added
94 an AdjustEOF routine called by the assembly AdjEOF routine. It
95 copies the EOF, physical length, and extent information from one
96 FCB to all other FCBs for that fork.
97 <CS4> 5/20/97 DSH Removed const declaration in MapFileBlocC, const is benign when
98 passing by value, and SC requires it to match prototype.
99 <CS3> 5/15/97 msd Change enum kResourceForkType from -1 to 0xFF since it is now
100 unsigned. Change all forkType parameters to UInt8.
101 <CS2> 5/7/97 msd When checking for an unused extent descriptor, check the length,
102 not the starting block.
103 <CS1> 4/24/97 djb first checked in
104 <HFS25> 4/11/97 DSH use extended VCB fields catalogRefNum, and extentsRefNum.
105 <HFS24> 4/4/97 djb Get in sync with volume format changes.
106 <HFS23> 3/17/97 DSH Casting to compile with SC.
107 <HFS22> 2/26/97 msd Add instrumentation in ExtendFileC and TruncateFileC. In
108 CompareExtentKeys and CompareExtentKeysPlus, make sure the key
109 lengths are correct.
110 <HFS21> 2/5/97 msd The comparison with fsBTStartOfIterationErr didn't work because
111 the enum is an unsigned long; it is now casted to an OSErr
112 before comparing.
113 <HFS20> 1/31/97 msd In FindExtentRecord, turn an fsBTStartOfIterationErr error into
114 btNotFound.
115 <HFS19> 1/28/97 msd Fixed bug in MapFileBlockC where it returned the wrong number of
116 bytes available at the given block number. This could
117 potentially cause programs to read or write over other files.
118 <HFS18> 1/16/97 djb Extent key compare procs now return SInt32. Fixed
119 UpdateExtentRecord - it was passing a pointer to an ExtentKey
120 pointer.
121 <HFS17> 1/10/97 msd Change TruncateFileC to call DellocateFork when the new PEOF is
122 0. Fixes a fxRangeErr returned when no extents existed.
123 <HFS16> 1/6/97 msd Previous change prevents extent records from being removed if
124 the files new PEOF is in the local (FCB/catalog) extents.
125 <HFS15> 1/3/97 djb Temp fix in TruncateFileC to prevent unwanted calls to
126 TruncateExtents.
127 <HFS14> 12/23/96 msd Previous change to SearchExtentFile didn't set up the outputs
128 for hint and key when the FCB extent record wasn't full.
129 <HFS13> 12/20/96 msd In SearchExtentFile, don't bother searching the extents file if
130 the FCB's extent record wasn't full, or if the FCB was for the
131 extents file itself. Modified SearchExtentRecord to return a
132 Boolean to indicate that the record was not full.
133 <HFS12> 12/19/96 DSH Changed refs from VCB to ExtendedVCB
134 <HFS11> 12/19/96 djb Updated for new B-tree Manager interface.
135 <HFS10> 12/12/96 djb Really use new SPI for GetCatalogNode.
136 <HFS9> 12/12/96 djb Use new Catalog SPI for GetCatalogNode. Added Mark's changes to
137 MapFileBlockC.
138 <HFS8> 12/11/96 msd TruncateFileC must always release extents, even if PEOF hasn't
139 changed (since allocation may have been rounded up due to clump
140 size).
141 <HFS7> 12/10/96 msd Check PRAGMA_LOAD_SUPPORTED before loading precompiled headers.
142 <HFS6> 12/4/96 DSH Precompiled headers
143 <HFS5> 11/26/96 msd Add an exported routine to grow the parallel FCB table to
144 accomodate the HFS+ ExtentRecord.
145 <HFS4> 11/26/96 msd Convert internal routines to use ExtentKey and ExtentRecord
146 (instead of the raw HFS structures).
147 <HFS3> 11/21/96 msd Added CompareExtentKeysPlus().
148 <HFS2> 11/20/96 msd Finish porting FXM to C.
149 <HFS1> 11/6/96 DKH first checked in
150
151 */
152
153
154 #include "../../hfs.h"
155 #include "../../hfs_format.h"
156 #include "../../hfs_endian.h"
157
158 #include "../headers/FileMgrInternal.h"
159 #include "../headers/BTreesInternal.h"
160 #include "../headers/CatalogPrivate.h" // calling a private catalog routine (LocateCatalogNode)
161
162 #include "../headers/HFSInstrumentation.h"
163
164 #include <sys/malloc.h>
165
166 /*
167 ============================================================
168 Public (Exported) Routines:
169 ============================================================
170 DeAllocFile Deallocate all disk space allocated to a specified file.
171 Both forks are deallocated.
172
173 ExtendFileC Allocate more space to a given file.
174
175 CompareExtentKeys
176 Compare two extents file keys (a search key and a trial
177 key). Used by the BTree manager when searching for,
178 adding, or deleting keys in the extents file of an HFS
179 volume.
180
181 CompareExtentKeysPlus
182 Compare two extents file keys (a search key and a trial
183 key). Used by the BTree manager when searching for,
184 adding, or deleting keys in the extents file of an HFS+
185 volume.
186
187 MapFileBlockC Convert (map) an offset within a given file into a
188 physical disk address.
189
190 TruncateFileC Truncates the disk space allocated to a file. The file
191 space is truncated to a specified new physical EOF, rounded
192 up to the next allocation block boundry. There is an option
193 to truncate to the end of the extent containing the new EOF.
194
195 FlushExtentFile
196 Flush the extents file for a given volume.
197
198 GrowParallelFCBs
199 Make sure the parallel FCB entries are big enough to support
200 the HFS+ ExtentRecord. If not, the array is grown and the
201 pre-existing data copied over.
202
203 AdjustEOF
204 Copy EOF, physical length, and extent records from one FCB
205 to all other FCBs for that fork. This is used when a file is
206 grown or shrunk as the result of a Write, SetEOF, or Allocate.
207
208 MapLogicalToPhysical
209 Map some position in a file to a volume block number. Also
210 returns the number of contiguous bytes that are mapped there.
211 This is a queued HFSDispatch call that does the equivalent of
212 MapFileBlockC, using a parameter block.
213
214 ============================================================
215 Internal Routines:
216 ============================================================
217 FindExtentRecord
218 Search the extents BTree for a particular extent record.
219 SearchExtentFile
220 Search the FCB and extents file for an extent record that
221 contains a given file position (in bytes).
222 SearchExtentRecord
223 Search a given extent record to see if it contains a given
224 file position (in bytes). Used by SearchExtentFile.
225 ReleaseExtents
226 Deallocate all allocation blocks in all extents of an extent
227 data record.
228 TruncateExtents
229 Deallocate blocks and delete extent records for all allocation
230 blocks beyond a certain point in a file. The starting point
231 must be the first file allocation block for some extent record
232 for the file.
233 DeallocateFork
234 Deallocate all allocation blocks belonging to a given fork.
235 UpdateExtentRecord
236 If the extent record came from the extents file, write out
237 the updated record; otherwise, copy the updated record into
238 the FCB resident extent record. If the record has no extents,
239 and was in the extents file, then delete the record instead.
240 */
241
242 enum
243 {
244 kTwoGigabytes = (UInt32) 0x80000000,
245
246 kDataForkType = 0,
247 kResourceForkType = 0xFF,
248
249 kPreviousRecord = -1,
250
251 kSectorSize = 512 // Size of a physical sector
252 };
253
254 void HFSToHFSPlusExtents(
255 const HFSExtentRecord oldExtents,
256 HFSPlusExtentRecord newExtents);
257
258 OSErr HFSPlusToHFSExtents(
259 const HFSPlusExtentRecord oldExtents,
260 HFSExtentRecord newExtents);
261
262 OSErr FindExtentRecord(
263 const ExtendedVCB *vcb,
264 UInt8 forkType,
265 UInt32 fileID,
266 UInt32 startBlock,
267 Boolean allowPrevious,
268 HFSPlusExtentKey *foundKey,
269 HFSPlusExtentRecord foundData,
270 UInt32 *foundHint);
271
272 OSErr DeleteExtentRecord(
273 const ExtendedVCB *vcb,
274 UInt8 forkType,
275 UInt32 fileID,
276 UInt32 startBlock);
277
278 static OSErr CreateExtentRecord(
279 const ExtendedVCB *vcb,
280 HFSPlusExtentKey *key,
281 HFSPlusExtentRecord extents,
282 UInt32 *hint);
283
284
285 OSErr GetFCBExtentRecord(
286 const FCB *fcb,
287 HFSPlusExtentRecord extents);
288
289 static OSErr SearchExtentFile(
290 const ExtendedVCB *vcb,
291 const FCB *fcb,
292 SInt64 filePosition,
293 HFSPlusExtentKey *foundExtentKey,
294 HFSPlusExtentRecord foundExtentData,
295 UInt32 *foundExtentDataIndex,
296 UInt32 *extentBTreeHint,
297 UInt32 *endingFABNPlusOne );
298
299 static OSErr SearchExtentRecord(
300 const ExtendedVCB *vcb,
301 UInt32 searchFABN,
302 const HFSPlusExtentRecord extentData,
303 UInt32 extentDataStartFABN,
304 UInt32 *foundExtentDataOffset,
305 UInt32 *endingFABNPlusOne,
306 Boolean *noMoreExtents);
307
308 static OSErr ReleaseExtents(
309 ExtendedVCB *vcb,
310 const HFSPlusExtentRecord extentRecord,
311 UInt32 *numReleasedAllocationBlocks,
312 Boolean *releasedLastExtent);
313
314 static OSErr DeallocateFork(
315 ExtendedVCB *vcb,
316 HFSCatalogNodeID fileID,
317 UInt8 forkType,
318 HFSPlusExtentRecord catalogExtents,
319 Boolean * recordDeleted);
320
321 static OSErr TruncateExtents(
322 ExtendedVCB *vcb,
323 UInt8 forkType,
324 UInt32 fileID,
325 UInt32 startBlock,
326 Boolean * recordDeleted);
327
328 static OSErr UpdateExtentRecord (
329 const ExtendedVCB *vcb,
330 FCB *fcb,
331 const HFSPlusExtentKey *extentFileKey,
332 const HFSPlusExtentRecord extentData,
333 UInt32 extentBTreeHint);
334
335 static OSErr MapFileBlockFromFCB(
336 const ExtendedVCB *vcb,
337 const FCB *fcb,
338 SInt64 offset, // Desired offset in bytes from start of file
339 UInt32 *firstFABN, // FABN of first block of found extent
340 UInt32 *firstBlock, // Corresponding allocation block number
341 UInt32 *nextFABN); // FABN of block after end of extent
342
343 static Boolean ExtentsAreIntegral(
344 const HFSPlusExtentRecord extentRecord,
345 UInt32 mask,
346 UInt32 *blocksChecked,
347 Boolean *checkedLastExtent);
348
349 //_________________________________________________________________________________
350 //
351 // Routine: FindExtentRecord
352 //
353 // Purpose: Search the extents BTree for an extent record matching the given
354 // FileID, fork, and starting file allocation block number.
355 //
356 // Inputs:
357 // vcb Volume to search
358 // forkType 0 = data fork, -1 = resource fork
359 // fileID File's FileID (CatalogNodeID)
360 // startBlock Starting file allocation block number
361 // allowPrevious If the desired record isn't found and this flag is set,
362 // then see if the previous record belongs to the same fork.
363 // If so, then return it.
364 //
365 // Outputs:
366 // foundKey The key data for the record actually found
367 // foundData The extent record actually found (NOTE: on an HFS volume, the
368 // fourth entry will be zeroes.
369 // foundHint The BTree hint to find the node again
370 //_________________________________________________________________________________
371 OSErr FindExtentRecord(
372 const ExtendedVCB *vcb,
373 UInt8 forkType,
374 UInt32 fileID,
375 UInt32 startBlock,
376 Boolean allowPrevious,
377 HFSPlusExtentKey *foundKey,
378 HFSPlusExtentRecord foundData,
379 UInt32 *foundHint)
380 {
381 FCB * fcb;
382 BTreeIterator btIterator;
383 FSBufferDescriptor btRecord;
384 OSErr err;
385 UInt16 btRecordSize;
386
387 err = noErr;
388 *foundHint = 0;
389 fcb = GetFileControlBlock(vcb->extentsRefNum);
390
391 (void) BTInvalidateHint(&btIterator);
392
393 if (vcb->vcbSigWord == kHFSSigWord) {
394 HFSExtentKey * extentKeyPtr;
395 HFSExtentRecord extentData;
396
397 extentKeyPtr = (HFSExtentKey*) &btIterator.key;
398 extentKeyPtr->keyLength = kHFSExtentKeyMaximumLength;
399 extentKeyPtr->forkType = forkType;
400 extentKeyPtr->fileID = fileID;
401 extentKeyPtr->startBlock = startBlock;
402
403 btRecord.bufferAddress = &extentData;
404 btRecord.itemSize = sizeof(HFSExtentRecord);
405 btRecord.itemCount = 1;
406
407 err = BTSearchRecord(fcb, &btIterator, kInvalidMRUCacheKey, &btRecord, &btRecordSize, &btIterator);
408
409 if (err == btNotFound && allowPrevious) {
410 err = BTIterateRecord(fcb, kBTreePrevRecord, &btIterator, &btRecord, &btRecordSize);
411
412 // A previous record may not exist, so just return btNotFound (like we would if
413 // it was for the wrong file/fork).
414 if (err == (OSErr) fsBTStartOfIterationErr) //¥¥ fsBTStartOfIterationErr is type unsigned long
415 err = btNotFound;
416
417 if (err == noErr) {
418 // Found a previous record. Does it belong to the same fork of the same file?
419 if (extentKeyPtr->fileID != fileID || extentKeyPtr->forkType != forkType)
420 err = btNotFound;
421 }
422 }
423
424 if (err == noErr) {
425 UInt16 i;
426
427 // Copy the found key back for the caller
428 foundKey->keyLength = kHFSPlusExtentKeyMaximumLength;
429 foundKey->forkType = extentKeyPtr->forkType;
430 foundKey->pad = 0;
431 foundKey->fileID = extentKeyPtr->fileID;
432 foundKey->startBlock = extentKeyPtr->startBlock;
433
434 // Copy the found data back for the caller
435 foundData[0].startBlock = extentData[0].startBlock;
436 foundData[0].blockCount = extentData[0].blockCount;
437 foundData[1].startBlock = extentData[1].startBlock;
438 foundData[1].blockCount = extentData[1].blockCount;
439 foundData[2].startBlock = extentData[2].startBlock;
440 foundData[2].blockCount = extentData[2].blockCount;
441
442 for (i = 3; i < kHFSPlusExtentDensity; ++i)
443 {
444 foundData[i].startBlock = 0;
445 foundData[i].blockCount = 0;
446 }
447 }
448 }
449 else { // HFS Plus volume
450 HFSPlusExtentKey * extentKeyPtr;
451 HFSPlusExtentRecord extentData;
452
453 extentKeyPtr = (HFSPlusExtentKey*) &btIterator.key;
454 extentKeyPtr->keyLength = kHFSPlusExtentKeyMaximumLength;
455 extentKeyPtr->forkType = forkType;
456 extentKeyPtr->pad = 0;
457 extentKeyPtr->fileID = fileID;
458 extentKeyPtr->startBlock = startBlock;
459
460 btRecord.bufferAddress = &extentData;
461 btRecord.itemSize = sizeof(HFSPlusExtentRecord);
462 btRecord.itemCount = 1;
463
464 err = BTSearchRecord(fcb, &btIterator, kInvalidMRUCacheKey, &btRecord, &btRecordSize, &btIterator);
465
466 if (err == btNotFound && allowPrevious) {
467 err = BTIterateRecord(fcb, kBTreePrevRecord, &btIterator, &btRecord, &btRecordSize);
468
469 // A previous record may not exist, so just return btNotFound (like we would if
470 // it was for the wrong file/fork).
471 if (err == (OSErr) fsBTStartOfIterationErr) //¥¥ fsBTStartOfIterationErr is type unsigned long
472 err = btNotFound;
473
474 if (err == noErr) {
475 // Found a previous record. Does it belong to the same fork of the same file?
476 if (extentKeyPtr->fileID != fileID || extentKeyPtr->forkType != forkType)
477 err = btNotFound;
478 }
479 }
480
481 if (err == noErr) {
482 // Copy the found key back for the caller
483 BlockMoveData(extentKeyPtr, foundKey, sizeof(HFSPlusExtentKey));
484 // Copy the found data back for the caller
485 BlockMoveData(&extentData, foundData, sizeof(HFSPlusExtentRecord));
486 }
487 }
488
489 *foundHint = btIterator.hint.nodeNum;
490 return err;
491 }
492
493
494
495 static OSErr CreateExtentRecord(
496 const ExtendedVCB *vcb,
497 HFSPlusExtentKey *key,
498 HFSPlusExtentRecord extents,
499 UInt32 *hint)
500 {
501 BTreeIterator btIterator;
502 FSBufferDescriptor btRecord;
503 UInt16 btRecordSize;
504 OSErr err;
505
506 err = noErr;
507 *hint = 0;
508 (void) BTInvalidateHint(&btIterator);
509
510 if (vcb->vcbSigWord == kHFSSigWord) {
511 HFSExtentKey * keyPtr;
512 HFSExtentRecord data;
513
514 btRecordSize = sizeof(HFSExtentRecord);
515 btRecord.bufferAddress = &data;
516 btRecord.itemSize = btRecordSize;
517 btRecord.itemCount = 1;
518
519 keyPtr = (HFSExtentKey*) &btIterator.key;
520 keyPtr->keyLength = kHFSExtentKeyMaximumLength;
521 keyPtr->forkType = key->forkType;
522 keyPtr->fileID = key->fileID;
523 keyPtr->startBlock = key->startBlock;
524
525 err = HFSPlusToHFSExtents(extents, data);
526 }
527 else { // HFS Plus volume
528 btRecordSize = sizeof(HFSPlusExtentRecord);
529 btRecord.bufferAddress = extents;
530 btRecord.itemSize = btRecordSize;
531 btRecord.itemCount = 1;
532
533 BlockMoveData(key, &btIterator.key, sizeof(HFSPlusExtentKey));
534 }
535
536 if (err == noErr)
537 err = BTInsertRecord(GetFileControlBlock(vcb->extentsRefNum), &btIterator, &btRecord, btRecordSize);
538
539 if (err == noErr)
540 *hint = btIterator.hint.nodeNum;
541
542 return err;
543 }
544
545
546 OSErr DeleteExtentRecord(
547 const ExtendedVCB *vcb,
548 UInt8 forkType,
549 UInt32 fileID,
550 UInt32 startBlock)
551 {
552 BTreeIterator btIterator;
553 OSErr err;
554
555 err = noErr;
556 (void) BTInvalidateHint(&btIterator);
557
558 if (vcb->vcbSigWord == kHFSSigWord) {
559 HFSExtentKey * keyPtr;
560
561 keyPtr = (HFSExtentKey*) &btIterator.key;
562 keyPtr->keyLength = kHFSExtentKeyMaximumLength;
563 keyPtr->forkType = forkType;
564 keyPtr->fileID = fileID;
565 keyPtr->startBlock = startBlock;
566 }
567 else { // HFS Plus volume
568 HFSPlusExtentKey * keyPtr;
569
570 keyPtr = (HFSPlusExtentKey*) &btIterator.key;
571 keyPtr->keyLength = kHFSPlusExtentKeyMaximumLength;
572 keyPtr->forkType = forkType;
573 keyPtr->pad = 0;
574 keyPtr->fileID = fileID;
575 keyPtr->startBlock = startBlock;
576 }
577
578 err = BTDeleteRecord(GetFileControlBlock(vcb->extentsRefNum), &btIterator);
579
580 return err;
581 }
582
583
584
585 //_________________________________________________________________________________
586 //
587 // Routine: MapFileBlock
588 //
589 // Function: Maps a file position into a physical disk address.
590 //
591 // Input: A2.L - VCB pointer
592 // (A1,D1.W) - FCB pointer
593 // D4.L - number of bytes desired
594 // D5.L - file position (byte address)
595 //
596 // Output: D3.L - physical start block
597 // D6.L - number of contiguous bytes available (up to D4 bytes)
598 // D0.L - result code <01Oct85>
599 // 0 = ok
600 // FXRangeErr = file position beyond mapped range <17Oct85>
601 // FXOvFlErr = extents file overflow <17Oct85>
602 // other = error <17Oct85>
603 //
604 // Called By: Log2Phys (read/write in place), Cache (map a file block).
605 //_________________________________________________________________________________
606
607 OSErr MapFileBlockC (
608 ExtendedVCB *vcb, // volume that file resides on
609 FCB *fcb, // FCB of file
610 size_t numberOfBytes, // number of contiguous bytes desired
611 off_t offset, // starting offset within file (in bytes)
612 daddr_t *startSector, // first 512-byte sector (NOT an allocation block)
613 size_t *availableBytes) // number of contiguous bytes (up to numberOfBytes)
614 {
615 OSErr err;
616 UInt32 allocBlockSize; // Size of the volume's allocation block
617 HFSPlusExtentKey foundKey;
618 HFSPlusExtentRecord foundData;
619 UInt32 foundIndex;
620 UInt32 hint;
621 UInt32 firstFABN; // file allocation block of first block in found extent
622 UInt32 nextFABN; // file allocation block of block after end of found extent
623 off_t dataEnd; // (offset) end of range that is contiguous
624 UInt32 sectorsPerBlock; // Number of sectors per allocation block
625 UInt32 startBlock; // volume allocation block corresponding to firstFABN
626 daddr_t temp;
627 off_t tmpOff;
628
629
630 LogStartTime(kTraceMapFileBlock);
631
632 allocBlockSize = vcb->blockSize;
633
634 err = MapFileBlockFromFCB(vcb, fcb, offset, &firstFABN, &startBlock, &nextFABN);
635 if (err != noErr) {
636 err = SearchExtentFile(vcb, fcb, offset, &foundKey, foundData, &foundIndex, &hint, &nextFABN);
637 if (err == noErr) {
638 startBlock = foundData[foundIndex].startBlock;
639 firstFABN = nextFABN - foundData[foundIndex].blockCount;
640 }
641 }
642
643 if (err != noErr)
644 {
645 LogEndTime(kTraceMapFileBlock, err);
646
647 return err;
648 }
649
650 //
651 // Determine the end of the available space. It will either be the end of the extent,
652 // or the file's PEOF, whichever is smaller.
653 //
654 dataEnd = (off_t)((off_t)(nextFABN) * (off_t)(allocBlockSize)); // Assume valid data through end of this extent
655 if (fcb->fcbPLen < dataEnd) // Is PEOF shorter?
656 dataEnd = fcb->fcbPLen; // Yes, so only map up to PEOF
657
658 // Compute the number of sectors in an allocation block
659 sectorsPerBlock = allocBlockSize / kSectorSize; // sectors per allocation block
660
661 //
662 // Compute the absolute sector number that contains the offset of the given file
663 //
664 temp = (daddr_t)((offset - (off_t)((off_t)(firstFABN) * (off_t)(allocBlockSize)))/kSectorSize); // offset in sectors from start of the extent
665 temp += startBlock * sectorsPerBlock; // offset in sectors from start of allocation block space
666 if (vcb->vcbSigWord == kHFSPlusSigWord)
667 temp += vcb->hfsPlusIOPosOffset/512; /* offset inside wrapper */
668 else
669 temp += vcb->vcbAlBlSt; /* offset in sectors from start of volume */
670
671 // Return the desired sector for file position "offset"
672 *startSector = temp;
673
674 //
675 // Determine the number of contiguous bytes until the end of the extent
676 // (or the amount they asked for, whichever comes first).
677 //
678 tmpOff = dataEnd - offset;
679 if (tmpOff > (off_t)(numberOfBytes))
680 *availableBytes = numberOfBytes; // more there than they asked for, so pin the output
681 else
682 *availableBytes = tmpOff;
683 LogEndTime(kTraceMapFileBlock, noErr);
684
685 return noErr;
686 }
687
688
689 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
690 // Routine: ReleaseExtents
691 //
692 // Function: Release the extents of a single extent data record.
693 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
694
695 static OSErr ReleaseExtents(
696 ExtendedVCB *vcb,
697 const HFSPlusExtentRecord extentRecord,
698 UInt32 *numReleasedAllocationBlocks,
699 Boolean *releasedLastExtent)
700 {
701 UInt32 extentIndex;
702 UInt32 numberOfExtents;
703 OSErr err = noErr;
704
705 *numReleasedAllocationBlocks = 0;
706 *releasedLastExtent = false;
707
708 if (vcb->vcbSigWord == kHFSPlusSigWord)
709 numberOfExtents = kHFSPlusExtentDensity;
710 else
711 numberOfExtents = kHFSExtentDensity;
712
713 for( extentIndex = 0; extentIndex < numberOfExtents; extentIndex++)
714 {
715 UInt32 numAllocationBlocks;
716
717 // Loop over the extent record and release the blocks associated with each extent.
718
719 numAllocationBlocks = extentRecord[extentIndex].blockCount;
720 if ( numAllocationBlocks == 0 )
721 {
722 *releasedLastExtent = true;
723 break;
724 }
725
726 err = BlockDeallocate( vcb, extentRecord[extentIndex].startBlock, numAllocationBlocks );
727 if ( err != noErr )
728 break;
729
730 *numReleasedAllocationBlocks += numAllocationBlocks; // bump FABN to beg of next extent
731 }
732
733 return( err );
734 }
735
736
737
738 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
739 // Routine: TruncateExtents
740 //
741 // Purpose: Delete extent records whose starting file allocation block number
742 // is greater than or equal to a given starting block number. The
743 // allocation blocks represented by the extents are deallocated.
744 //
745 // Inputs:
746 // vcb Volume to operate on
747 // fileID Which file to operate on
748 // startBlock Starting file allocation block number for first extent
749 // record to delete.
750 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
751
752 static OSErr TruncateExtents(
753 ExtendedVCB *vcb,
754 UInt8 forkType,
755 UInt32 fileID,
756 UInt32 startBlock,
757 Boolean * recordDeleted)
758 {
759 OSErr err;
760 UInt32 numberExtentsReleased;
761 Boolean releasedLastExtent;
762 UInt32 hint;
763 HFSPlusExtentKey key;
764 HFSPlusExtentRecord extents;
765
766 while (true) {
767 err = FindExtentRecord(vcb, forkType, fileID, startBlock, false, &key, extents, &hint);
768 if (err != noErr) {
769 if (err == btNotFound)
770 err = noErr;
771 break;
772 }
773
774 err = ReleaseExtents( vcb, extents, &numberExtentsReleased, &releasedLastExtent );
775 if (err != noErr) break;
776
777 err = DeleteExtentRecord(vcb, forkType, fileID, startBlock);
778 if (err != noErr) break;
779
780 *recordDeleted = true;
781 startBlock += numberExtentsReleased;
782 }
783
784 return err;
785 }
786
787
788
789 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
790 // Routine: DeallocateFork
791 //
792 // Function: De-allocates all disk space allocated to a specified fork.
793 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
794
795 static OSErr DeallocateFork(
796 ExtendedVCB *vcb,
797 HFSCatalogNodeID fileID,
798 UInt8 forkType,
799 HFSPlusExtentRecord catalogExtents,
800 Boolean * recordDeleted) /* true if a record was deleted */
801 {
802 OSErr err;
803 UInt32 numReleasedAllocationBlocks;
804 Boolean releasedLastExtent;
805
806 // Release the catalog extents
807 err = ReleaseExtents( vcb, catalogExtents, &numReleasedAllocationBlocks, &releasedLastExtent );
808 // Release the extra extents, if present
809 if (err == noErr && !releasedLastExtent)
810 err = TruncateExtents(vcb, forkType, fileID, numReleasedAllocationBlocks, recordDeleted);
811
812 return( err );
813 }
814
815 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
816 // Routine: FlushExtentFile
817 //
818 // Function: Flushes the extent file for a specified volume
819 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
820
821 OSErr FlushExtentFile( ExtendedVCB *vcb )
822 {
823 FCB * fcb;
824 OSErr err;
825
826 fcb = GetFileControlBlock(vcb->extentsRefNum);
827 err = BTFlushPath(fcb);
828 if ( err == noErr )
829 {
830 // If the FCB for the extent "file" is dirty, mark the VCB as dirty.
831
832 if ((fcb->fcbFlags & fcbModifiedMask) != 0)
833 {
834 MarkVCBDirty( vcb );
835 err = FlushVolumeControlBlock( vcb );
836 }
837 }
838
839 return( err );
840 }
841
842 //-------------------------------------------------------------------------------
843 // Routine: DeleteFile
844 //
845 // Function: De-allocates all disk space allocated to a specified file
846 // including the space used by the catalog (ie the catalog record).
847 // The space occupied by both forks is also deallocated.
848 //
849 //-------------------------------------------------------------------------------
850
851 OSErr DeleteFile( ExtendedVCB *vcb, HFSCatalogNodeID parDirID, ConstUTF8Param catalogName, UInt32 catalogHint )
852 {
853 OSErr err;
854 OSErr errDF, errRF;
855 CatalogNodeData catalogData;
856 Boolean recordDeleted;
857
858 recordDeleted = false;
859
860 INIT_CATALOGDATA(&catalogData, kCatNameNoCopyName);
861
862 // Find catalog data in catalog
863 err = GetCatalogNode( vcb, parDirID, catalogName, kUndefinedStrLen, catalogHint, &catalogData, &catalogHint);
864 if( err != noErr )
865 goto Exit;
866
867
868 // Check to make sure record is for a file
869 if ( catalogData.cnd_type != kCatalogFileNode )
870 {
871 err = notAFileErr;
872 goto Exit;
873 }
874
875 //
876 // Always delete the Catalog record first (to minimize disk corruption)
877 //
878 err = DeleteCatalogNode(vcb, parDirID, catalogName, catalogHint);
879 if( err != noErr )
880 goto Exit;
881
882 //
883 // Note: we don't report errors from DeallocateFork since the
884 // file no longer exists (since DeleteCatalogNode succeeded).
885 // Any errors mean that there are possibly some orphaned disk
886 // blocks but from the clients perspective the file was deleted.
887 //
888
889 // Deallocate data fork extents
890 errDF = DeallocateFork( vcb, catalogData.cnd_nodeID, kDataForkType,
891 catalogData.cnd_datafork.extents, &recordDeleted );
892
893 // Deallocate resource fork extents
894 errRF = DeallocateFork( vcb, catalogData.cnd_nodeID, kResourceForkType,
895 catalogData.cnd_rsrcfork.extents, &recordDeleted );
896
897 if (recordDeleted)
898 err = FlushExtentFile( vcb );
899
900 CLEAN_CATALOGDATA(&catalogData);
901 return (errDF ? errDF : (errRF ? errRF : err));
902 Exit:
903
904 CLEAN_CATALOGDATA(&catalogData);
905 return( err );
906 }
907
908 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
909 // Routine: CompareExtentKeys
910 //
911 // Function: Compares two extent file keys (a search key and a trial key) for
912 // an HFS volume.
913 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
914
915 SInt32 CompareExtentKeys( const HFSExtentKey *searchKey, const HFSExtentKey *trialKey )
916 {
917 SInt32 result; // ± 1
918
919 #if DEBUG_BUILD
920 if (searchKey->keyLength != kHFSExtentKeyMaximumLength)
921 DebugStr("\pHFS: search Key is wrong length");
922 if (trialKey->keyLength != kHFSExtentKeyMaximumLength)
923 DebugStr("\pHFS: trial Key is wrong length");
924 #endif
925
926 result = -1; // assume searchKey < trialKey
927
928 if (searchKey->fileID == trialKey->fileID) {
929 //
930 // FileNum's are equal; compare fork types
931 //
932 if (searchKey->forkType == trialKey->forkType) {
933 //
934 // Fork types are equal; compare allocation block number
935 //
936 if (searchKey->startBlock == trialKey->startBlock) {
937 //
938 // Everything is equal
939 //
940 result = 0;
941 }
942 else {
943 //
944 // Allocation block numbers differ; determine sign
945 //
946 if (searchKey->startBlock > trialKey->startBlock)
947 result = 1;
948 }
949 }
950 else {
951 //
952 // Fork types differ; determine sign
953 //
954 if (searchKey->forkType > trialKey->forkType)
955 result = 1;
956 }
957 }
958 else {
959 //
960 // FileNums differ; determine sign
961 //
962 if (searchKey->fileID > trialKey->fileID)
963 result = 1;
964 }
965
966 return( result );
967 }
968
969
970
971 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
972 // Routine: CompareExtentKeysPlus
973 //
974 // Function: Compares two extent file keys (a search key and a trial key) for
975 // an HFS volume.
976 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
977
978 SInt32 CompareExtentKeysPlus( const HFSPlusExtentKey *searchKey, const HFSPlusExtentKey *trialKey )
979 {
980 SInt32 result; // ± 1
981
982 #if DEBUG_BUILD
983 if (searchKey->keyLength != kHFSPlusExtentKeyMaximumLength)
984 DebugStr("\pHFS: search Key is wrong length");
985 if (trialKey->keyLength != kHFSPlusExtentKeyMaximumLength)
986 DebugStr("\pHFS: trial Key is wrong length");
987 #endif
988
989 result = -1; // assume searchKey < trialKey
990
991 if (searchKey->fileID == trialKey->fileID) {
992 //
993 // FileNum's are equal; compare fork types
994 //
995 if (searchKey->forkType == trialKey->forkType) {
996 //
997 // Fork types are equal; compare allocation block number
998 //
999 if (searchKey->startBlock == trialKey->startBlock) {
1000 //
1001 // Everything is equal
1002 //
1003 result = 0;
1004 }
1005 else {
1006 //
1007 // Allocation block numbers differ; determine sign
1008 //
1009 if (searchKey->startBlock > trialKey->startBlock)
1010 result = 1;
1011 }
1012 }
1013 else {
1014 //
1015 // Fork types differ; determine sign
1016 //
1017 if (searchKey->forkType > trialKey->forkType)
1018 result = 1;
1019 }
1020 }
1021 else {
1022 //
1023 // FileNums differ; determine sign
1024 //
1025 if (searchKey->fileID > trialKey->fileID)
1026 result = 1;
1027 }
1028
1029 return( result );
1030 }
1031
1032
1033
1034 //_________________________________________________________________________________
1035 //
1036 // Routine: Extendfile
1037 //
1038 // Function: Extends the disk space allocated to a file.
1039 //
1040 // Input: A2.L - VCB pointer
1041 // A1.L - pointer to FCB array
1042 // D1.W - file refnum
1043 // D3.B - option flags
1044 // kEFContigMask - force contiguous allocation
1045 // kEFAllMask - allocate all requested bytes or none
1046 // NOTE: You may not set both options.
1047 // D4.L - number of additional bytes to allocate
1048 //
1049 // Output: D0.W - result code
1050 // 0 = ok
1051 // -n = IO error
1052 // D6.L - number of bytes allocated
1053 //
1054 // Called by: FileAloc,FileWrite,SetEof
1055 //
1056 // Note: ExtendFile updates the PEOF in the FCB.
1057 //_________________________________________________________________________________
1058
1059 OSErr ExtendFileC (
1060 ExtendedVCB *vcb, // volume that file resides on
1061 FCB *fcb, // FCB of file to truncate
1062 SInt64 bytesToAdd, // number of bytes to allocate
1063 UInt32 flags, // EFContig and/or EFAll
1064 SInt64 *actualBytesAdded) // number of bytes actually allocated
1065 {
1066 OSErr err;
1067 UInt32 volumeBlockSize;
1068 SInt64 blocksToAdd;
1069 SInt64 bytesThisExtent;
1070 HFSPlusExtentKey foundKey;
1071 HFSPlusExtentRecord foundData;
1072 UInt32 foundIndex;
1073 UInt32 hint;
1074 UInt32 nextBlock;
1075 UInt32 startBlock;
1076 Boolean allOrNothing;
1077 Boolean forceContig;
1078 Boolean wantContig;
1079 Boolean needsFlush;
1080 UInt32 actualStartBlock;
1081 UInt32 actualNumBlocks;
1082 UInt32 numExtentsPerRecord;
1083 SInt64 maximumBytes;
1084 SInt64 peof;
1085 SInt64 previousPEOF;
1086
1087
1088 #if HFSInstrumentation
1089 InstTraceClassRef trace;
1090 InstEventTag eventTag;
1091 InstDataDescriptorRef traceDescriptor;
1092 FSVarsRec *fsVars = (FSVarsRec *) LMGetFSMVars();
1093
1094 traceDescriptor = (InstDataDescriptorRef) fsVars->later[2];
1095
1096 err = InstCreateTraceClass(kInstRootClassRef, "HFS:Extents:ExtendFileC", 'hfs+', kInstEnableClassMask, &trace);
1097 if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
1098
1099 eventTag = InstCreateEventTag();
1100 InstLogTraceEvent( trace, eventTag, kInstStartEvent);
1101 #endif
1102
1103 needsFlush = false;
1104 *actualBytesAdded = 0;
1105 volumeBlockSize = vcb->blockSize;
1106 allOrNothing = ((flags & kEFAllMask) != 0);
1107 forceContig = ((flags & kEFContigMask) != 0);
1108 previousPEOF = fcb->fcbPLen;
1109
1110 if (vcb->vcbSigWord == kHFSPlusSigWord)
1111 numExtentsPerRecord = kHFSPlusExtentDensity;
1112 else
1113 numExtentsPerRecord = kHFSExtentDensity;
1114
1115 //
1116 // Make sure the request and new PEOF are less than 2GB if HFS.
1117 //
1118 if (vcb->vcbSigWord == kHFSSigWord) {
1119 if (bytesToAdd >= kTwoGigabytes)
1120 goto Overflow;
1121 if ((fcb->fcbPLen + bytesToAdd) >= kTwoGigabytes)
1122 goto Overflow;
1123 }
1124 //
1125 // Determine how many blocks need to be allocated.
1126 // Round up the number of desired bytes to add.
1127 //
1128 blocksToAdd = FileBytesToBlocks(bytesToAdd, volumeBlockSize);
1129 bytesToAdd = (SInt64)((SInt64)blocksToAdd * (SInt64)volumeBlockSize);
1130
1131 //
1132 // If the file's clump size is larger than the allocation block size,
1133 // then set the maximum number of bytes to the requested number of bytes
1134 // rounded up to a multiple of the clump size.
1135 //
1136 if (fcb->fcbClmpSize > volumeBlockSize) {
1137 maximumBytes = (SInt64)FileBytesToBlocks(bytesToAdd, fcb->fcbClmpSize);
1138 maximumBytes *= fcb->fcbClmpSize;
1139 }
1140 else {
1141 maximumBytes = bytesToAdd;
1142 }
1143
1144 //
1145 // Compute new physical EOF, rounded up to a multiple of a block.
1146 //
1147 if ((vcb->vcbSigWord == kHFSSigWord) && ((fcb->fcbPLen + bytesToAdd) >= (SInt64) kTwoGigabytes)) // Too big?
1148 if (allOrNothing) // Yes, must they have it all?
1149 goto Overflow; // Yes, can't have it
1150 else {
1151 --blocksToAdd; // No, give give 'em one block less
1152 bytesToAdd -= volumeBlockSize;
1153 }
1154
1155 //
1156 // If allocation is all-or-nothing, make sure there are
1157 // enough free blocks on the volume (quick test).
1158 //
1159 if (allOrNothing && (blocksToAdd > (SInt64)vcb->freeBlocks)) {
1160 err = dskFulErr;
1161 goto ErrorExit;
1162 }
1163
1164 //
1165 // See if there are already enough blocks allocated to the file.
1166 //
1167 peof = fcb->fcbPLen + bytesToAdd; // potential new PEOF
1168 err = SearchExtentFile(vcb, fcb, peof-1, &foundKey, foundData, &foundIndex, &hint, &nextBlock);
1169 if (err == noErr) {
1170 // Enough blocks are already allocated. Just update the FCB to reflect the new length.
1171 fcb->fcbPLen = peof;
1172 H_EXTENDSIZE(fcb, bytesToAdd);
1173 fcb->fcbFlags |= fcbModifiedMask;
1174 goto Exit;
1175 }
1176 if (err != fxRangeErr) // Any real error?
1177 goto ErrorExit; // Yes, so exit immediately
1178
1179 //
1180 // Adjust the PEOF to the end of the last extent.
1181 //
1182 peof = (SInt64)((SInt64)nextBlock * (SInt64)volumeBlockSize); // currently allocated PEOF
1183 bytesThisExtent = peof - fcb->fcbPLen;
1184 if (bytesThisExtent != 0) {
1185 fcb->fcbPLen = peof;
1186 H_EXTENDSIZE(fcb, bytesThisExtent);
1187 fcb->fcbFlags |= fcbModifiedMask;
1188 bytesToAdd -= bytesThisExtent;
1189 }
1190
1191 //
1192 // Allocate some more space.
1193 //
1194 // First try a contiguous allocation (of the whole amount).
1195 // If that fails, get whatever we can.
1196 // If forceContig, then take whatever we got
1197 // else, keep getting bits and pieces (non-contig)
1198 err = noErr;
1199 wantContig = true;
1200 do {
1201 startBlock = foundData[foundIndex].startBlock + foundData[foundIndex].blockCount;
1202 err = BlockAllocate(vcb, startBlock, bytesToAdd, maximumBytes, wantContig, &actualStartBlock, &actualNumBlocks);
1203 if (err == dskFulErr) {
1204 if (forceContig)
1205 break; // AllocContig failed because not enough contiguous space
1206 if (wantContig) {
1207 // Couldn't get one big chunk, so get whatever we can.
1208 err = noErr;
1209 wantContig = false;
1210 continue;
1211 }
1212 if (actualNumBlocks != 0)
1213 err = noErr;
1214 }
1215 if (err == noErr) {
1216 #if HFSInstrumentation
1217 {
1218 struct {
1219 UInt32 fileID;
1220 UInt32 start;
1221 UInt32 count;
1222 UInt32 fabn;
1223 } x;
1224
1225 x.fileID = H_FILEID(fcb);
1226 x.start = actualStartBlock;
1227 x.count = actualNumBlocks;
1228 x.fabn = nextBlock;
1229
1230 InstLogTraceEventWithDataStructure( trace, eventTag, kInstMiddleEvent, traceDescriptor,
1231 (UInt8 *) &x, sizeof(x));
1232 }
1233 #endif
1234 // Add the new extent to the existing extent record, or create a new one.
1235 if (actualStartBlock == startBlock) {
1236 // We grew the file's last extent, so just adjust the number of blocks.
1237 foundData[foundIndex].blockCount += actualNumBlocks;
1238 err = UpdateExtentRecord(vcb, fcb, &foundKey, foundData, hint);
1239 if (err != noErr) break;
1240 }
1241 else {
1242 UInt16 i;
1243
1244 // Need to add a new extent. See if there is room in the current record.
1245 if (foundData[foundIndex].blockCount != 0) // Is current extent free to use?
1246 ++foundIndex; // No, so use the next one.
1247 if (foundIndex == numExtentsPerRecord) {
1248 // This record is full. Need to create a new one.
1249 if (H_FILEID(fcb) == kHFSExtentsFileID) {
1250 err = fxOvFlErr; // Oops. Can't extend extents file (?? really ??)
1251 break;
1252 }
1253
1254 foundKey.keyLength = kHFSPlusExtentKeyMaximumLength;
1255 if (fcb->fcbFlags & fcbResourceMask)
1256 foundKey.forkType = kResourceForkType;
1257 else
1258 foundKey.forkType = kDataForkType;
1259 foundKey.pad = 0;
1260 foundKey.fileID = H_FILEID(fcb);
1261 foundKey.startBlock = nextBlock;
1262
1263 foundData[0].startBlock = actualStartBlock;
1264 foundData[0].blockCount = actualNumBlocks;
1265
1266 // zero out remaining extents...
1267 for (i = 1; i < kHFSPlusExtentDensity; ++i)
1268 {
1269 foundData[i].startBlock = 0;
1270 foundData[i].blockCount = 0;
1271 }
1272
1273 foundIndex = 0;
1274
1275 err = CreateExtentRecord(vcb, &foundKey, foundData, &hint);
1276 if (err == fxOvFlErr) {
1277 // We couldn't create an extent record because extents B-tree
1278 // couldn't grow. Dellocate the extent just allocated and
1279 // return a disk full error.
1280 (void) BlockDeallocate(vcb, actualStartBlock, actualNumBlocks);
1281 err = dskFulErr;
1282 }
1283 if (err != noErr) break;
1284
1285 needsFlush = true; // We need to update the B-tree header
1286 }
1287 else {
1288 // Add a new extent into this record and update.
1289 foundData[foundIndex].startBlock = actualStartBlock;
1290 foundData[foundIndex].blockCount = actualNumBlocks;
1291 err = UpdateExtentRecord(vcb, fcb, &foundKey, foundData, hint);
1292 if (err != noErr) break;
1293 }
1294 }
1295
1296 // Figure out how many bytes were actually allocated.
1297 // NOTE: BlockAllocate could have allocated more than we asked for.
1298 // Don't set the PEOF beyond what our client asked for.
1299 nextBlock += actualNumBlocks;
1300 bytesThisExtent = (SInt64)((SInt64)actualNumBlocks * (SInt64)volumeBlockSize);
1301 if (bytesThisExtent > bytesToAdd) {
1302 bytesToAdd = 0;
1303 }
1304 else {
1305 bytesToAdd -= bytesThisExtent;
1306 maximumBytes -= bytesThisExtent;
1307 }
1308 fcb->fcbPLen += bytesThisExtent;
1309 H_EXTENDSIZE(fcb, bytesThisExtent);
1310 fcb->fcbFlags |= fcbModifiedMask;
1311
1312 // If contiguous allocation was requested, then we've already got one contiguous
1313 // chunk. If we didn't get all we wanted, then adjust the error to disk full.
1314 if (forceContig) {
1315 if (bytesToAdd != 0)
1316 err = dskFulErr;
1317 break; // We've already got everything that's contiguous
1318 }
1319 }
1320 } while (err == noErr && bytesToAdd);
1321
1322 ErrorExit:
1323 Exit:
1324 *actualBytesAdded = fcb->fcbPLen - previousPEOF;
1325
1326 if (needsFlush)
1327 (void) FlushExtentFile(vcb);
1328
1329 #if HFSInstrumentation
1330 InstLogTraceEvent( trace, eventTag, kInstEndEvent);
1331 #endif
1332
1333 return err;
1334
1335 Overflow:
1336 err = fileBoundsErr;
1337 goto ErrorExit;
1338 }
1339
1340
1341
1342 //_________________________________________________________________________________
1343 //
1344 // Routine: TruncateFileC
1345 //
1346 // Function: Truncates the disk space allocated to a file. The file space is
1347 // truncated to a specified new PEOF rounded up to the next allocation
1348 // block boundry. If the 'TFTrunExt' option is specified, the file is
1349 // truncated to the end of the extent containing the new PEOF.
1350 //
1351 // Input: A2.L - VCB pointer
1352 // A1.L - pointer to FCB array
1353 // D1.W - file refnum
1354 // D2.B - option flags
1355 // TFTrunExt - truncate to the extent containing new PEOF
1356 // D3.L - new PEOF
1357 //
1358 // Output: D0.W - result code
1359 // 0 = ok
1360 // -n = IO error
1361 //
1362 // Note: TruncateFile updates the PEOF in the FCB.
1363 //_________________________________________________________________________________
1364
1365 OSErr TruncateFileC (
1366 ExtendedVCB *vcb, // volume that file resides on
1367 FCB *fcb, // FCB of file to truncate
1368 SInt64 peof, // new physical size for file
1369 Boolean truncateToExtent) // if true, truncate to end of extent containing newPEOF
1370 {
1371 OSErr err;
1372 UInt32 nextBlock; // next file allocation block to consider
1373 UInt32 startBlock; // Physical (volume) allocation block number of start of a range
1374 UInt32 physNumBlocks; // Number of allocation blocks in file (according to PEOF)
1375 UInt32 numBlocks;
1376 HFSPlusExtentKey key; // key for current extent record; key->keyLength == 0 if FCB's extent record
1377 UInt32 hint; // BTree hint corresponding to key
1378 HFSPlusExtentRecord extentRecord;
1379 UInt32 extentIndex;
1380 UInt32 extentNextBlock;
1381 UInt32 numExtentsPerRecord;
1382 SInt64 temp64;
1383 UInt8 forkType;
1384 Boolean extentChanged; // true if we actually changed an extent
1385 Boolean recordDeleted; // true if an extent record got deleted
1386
1387 #if HFSInstrumentation
1388 InstTraceClassRef trace;
1389 InstEventTag eventTag;
1390 InstDataDescriptorRef traceDescriptor;
1391 FSVarsRec *fsVars = (FSVarsRec *) LMGetFSMVars();
1392
1393 traceDescriptor = (InstDataDescriptorRef) fsVars->later[2];
1394
1395 err = InstCreateTraceClass(kInstRootClassRef, "HFS:Extents:TruncateFileC", 'hfs+', kInstEnableClassMask, &trace);
1396 if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
1397
1398 eventTag = InstCreateEventTag();
1399 InstLogTraceEvent( trace, eventTag, kInstStartEvent);
1400 #endif
1401
1402 recordDeleted = false;
1403
1404 if (vcb->vcbSigWord == kHFSPlusSigWord)
1405 numExtentsPerRecord = kHFSPlusExtentDensity;
1406 else
1407 numExtentsPerRecord = kHFSExtentDensity;
1408
1409 if (fcb->fcbFlags & fcbResourceMask)
1410 forkType = kResourceForkType;
1411 else
1412 forkType = kDataForkType;
1413
1414 temp64 = fcb->fcbPLen / (SInt64)vcb->blockSize; // number of allocation blocks currently in file
1415 physNumBlocks = (UInt32)temp64;
1416
1417 //
1418 // Round newPEOF up to a multiple of the allocation block size. If new size is
1419 // two gigabytes or more, then round down by one allocation block (??? really?
1420 // shouldn't that be an error?).
1421 //
1422 nextBlock = FileBytesToBlocks(peof, vcb->blockSize); // number of allocation blocks to remain in file
1423 peof = (SInt64)((SInt64)nextBlock * (SInt64)vcb->blockSize); // number of bytes in those blocks
1424 if ((vcb->vcbSigWord == kHFSSigWord) && (peof >= (UInt32) kTwoGigabytes)) {
1425 #if DEBUG_BUILD
1426 DebugStr("\pHFS: Trying to truncate a file to 2GB or more");
1427 #endif
1428 err = fileBoundsErr;
1429 goto ErrorExit;
1430 }
1431
1432 //
1433 // Update FCB's length
1434 //
1435 H_TRUNCSIZE(fcb, fcb->fcbPLen - peof);
1436 fcb->fcbPLen = peof;
1437 fcb->fcbFlags |= fcbModifiedMask;
1438
1439 //
1440 // If the new PEOF is 0, then truncateToExtent has no meaning (we should always deallocate
1441 // all storage).
1442 //
1443 if (peof == 0) {
1444 int i;
1445
1446 // Deallocate all the extents for this fork
1447 err = DeallocateFork(vcb, H_FILEID(fcb), forkType, fcb->fcbExtents, &recordDeleted);
1448 if (err != noErr) goto ErrorExit; // got some error, so return it
1449
1450 // Update the catalog extent record (making sure it's zeroed out)
1451 if (err == noErr) {
1452 for (i=0; i < kHFSPlusExtentDensity; i++) {
1453 fcb->fcbExtents[i].startBlock = 0;
1454 fcb->fcbExtents[i].blockCount = 0;
1455 }
1456 }
1457 goto Done;
1458 }
1459
1460 //
1461 // Find the extent containing byte (peof-1). This is the last extent we'll keep.
1462 // (If truncateToExtent is true, we'll keep the whole extent; otherwise, we'll only
1463 // keep up through peof). The search will tell us how many allocation blocks exist
1464 // in the found extent plus all previous extents.
1465 //
1466 err = SearchExtentFile(vcb, fcb, peof-1, &key, extentRecord, &extentIndex, &hint, &extentNextBlock);
1467 if (err != noErr) goto ErrorExit;
1468
1469 extentChanged = false; // haven't changed the extent yet
1470
1471 if (!truncateToExtent) {
1472 //
1473 // Shorten this extent. It may be the case that the entire extent gets
1474 // freed here.
1475 //
1476 numBlocks = extentNextBlock - nextBlock; // How many blocks in this extent to free up
1477 if (numBlocks != 0) {
1478 // Compute first volume allocation block to free
1479 startBlock = extentRecord[extentIndex].startBlock + extentRecord[extentIndex].blockCount - numBlocks;
1480 // Free the blocks in bitmap
1481 err = BlockDeallocate(vcb, startBlock, numBlocks);
1482 if (err != noErr) goto ErrorExit;
1483 // Adjust length of this extent
1484 extentRecord[extentIndex].blockCount -= numBlocks;
1485 // If extent is empty, set start block to 0
1486 if (extentRecord[extentIndex].blockCount == 0)
1487 extentRecord[extentIndex].startBlock = 0;
1488 // Remember that we changed the extent record
1489 extentChanged = true;
1490 }
1491 }
1492
1493 //
1494 // Now move to the next extent in the record, and set up the file allocation block number
1495 //
1496 nextBlock = extentNextBlock; // Next file allocation block to free
1497 ++extentIndex; // Its index within the extent record
1498
1499 //
1500 // Release all following extents in this extent record. Update the record.
1501 //
1502 while (extentIndex < numExtentsPerRecord && extentRecord[extentIndex].blockCount != 0) {
1503 numBlocks = extentRecord[extentIndex].blockCount;
1504 // Deallocate this extent
1505 err = BlockDeallocate(vcb, extentRecord[extentIndex].startBlock, numBlocks);
1506 if (err != noErr) goto ErrorExit;
1507 // Update next file allocation block number
1508 nextBlock += numBlocks;
1509 // Zero out start and length of this extent to delete it from record
1510 extentRecord[extentIndex].startBlock = 0;
1511 extentRecord[extentIndex].blockCount = 0;
1512 // Remember that we changed an extent
1513 extentChanged = true;
1514 // Move to next extent in record
1515 ++extentIndex;
1516 }
1517
1518 //
1519 // If any of the extents in the current record were changed, then update that
1520 // record (in the FCB, or extents file).
1521 //
1522 if (extentChanged) {
1523 err = UpdateExtentRecord(vcb, fcb, &key, extentRecord, hint);
1524 if (err != noErr) goto ErrorExit;
1525 }
1526
1527 //
1528 // If there are any following allocation blocks, then we need
1529 // to seach for their extent records and delete those allocation
1530 // blocks.
1531 //
1532 if (nextBlock < physNumBlocks)
1533 err = TruncateExtents(vcb, forkType, H_FILEID(fcb), nextBlock, &recordDeleted);
1534
1535 Done:
1536 ErrorExit:
1537
1538 if (recordDeleted)
1539 (void) FlushExtentFile(vcb);
1540
1541 #if HFSInstrumentation
1542 InstLogTraceEvent( trace, eventTag, kInstEndEvent);
1543 #endif
1544
1545 return err;
1546 }
1547
1548
1549
1550 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
1551 // Routine: SearchExtentRecord (was XRSearch)
1552 //
1553 // Function: Searches extent record for the extent mapping a given file
1554 // allocation block number (FABN).
1555 //
1556 // Input: searchFABN - desired FABN
1557 // extentData - pointer to extent data record (xdr)
1558 // extentDataStartFABN - beginning FABN for extent record
1559 //
1560 // Output: foundExtentDataOffset - offset to extent entry within xdr
1561 // result = noErr, offset to extent mapping desired FABN
1562 // result = FXRangeErr, offset to last extent in record
1563 // endingFABNPlusOne - ending FABN +1
1564 // noMoreExtents - True if the extent was not found, and the
1565 // extent record was not full (so don't bother
1566 // looking in subsequent records); false otherwise.
1567 //
1568 // Result: noErr = ok
1569 // FXRangeErr = desired FABN > last mapped FABN in record
1570 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
1571
1572 static OSErr SearchExtentRecord(
1573 const ExtendedVCB *vcb,
1574 UInt32 searchFABN,
1575 const HFSPlusExtentRecord extentData,
1576 UInt32 extentDataStartFABN,
1577 UInt32 *foundExtentIndex,
1578 UInt32 *endingFABNPlusOne,
1579 Boolean *noMoreExtents)
1580 {
1581 OSErr err = noErr;
1582 UInt32 extentIndex;
1583 UInt32 numberOfExtents;
1584 UInt32 numAllocationBlocks;
1585 Boolean foundExtent;
1586
1587 *endingFABNPlusOne = extentDataStartFABN;
1588 *noMoreExtents = false;
1589 foundExtent = false;
1590
1591 if (vcb->vcbSigWord == kHFSPlusSigWord)
1592 numberOfExtents = kHFSPlusExtentDensity;
1593 else
1594 numberOfExtents = kHFSExtentDensity;
1595
1596 for( extentIndex = 0; extentIndex < numberOfExtents; ++extentIndex )
1597 {
1598
1599 // Loop over the extent record and find the search FABN.
1600
1601 numAllocationBlocks = extentData[extentIndex].blockCount;
1602 if ( numAllocationBlocks == 0 )
1603 {
1604 break;
1605 }
1606
1607 *endingFABNPlusOne += numAllocationBlocks;
1608
1609 if( searchFABN < *endingFABNPlusOne )
1610 {
1611 // Found the extent.
1612 foundExtent = true;
1613 break;
1614 }
1615 }
1616
1617 if( foundExtent )
1618 {
1619 // Found the extent. Note the extent offset
1620 *foundExtentIndex = extentIndex;
1621 }
1622 else
1623 {
1624 // Did not find the extent. Set foundExtentDataOffset accordingly
1625 if( extentIndex > 0 )
1626 {
1627 *foundExtentIndex = extentIndex - 1;
1628 }
1629 else
1630 {
1631 *foundExtentIndex = 0;
1632 }
1633
1634 // If we found an empty extent, then set noMoreExtents.
1635 if (extentIndex < numberOfExtents)
1636 *noMoreExtents = true;
1637
1638 // Finally, return an error to the caller
1639 err = fxRangeErr;
1640 }
1641
1642 return( err );
1643 }
1644
1645 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
1646 // Routine: SearchExtentFile (was XFSearch)
1647 //
1648 // Function: Searches extent file (including the FCB resident extent record)
1649 // for the extent mapping a given file position.
1650 //
1651 // Input: vcb - VCB pointer
1652 // fcb - FCB pointer
1653 // filePosition - file position (byte address)
1654 //
1655 // Output: foundExtentKey - extent key record (xkr)
1656 // If extent was found in the FCB's resident extent record,
1657 // then foundExtentKey->keyLength will be set to 0.
1658 // foundExtentData - extent data record(xdr)
1659 // foundExtentIndex - index to extent entry in xdr
1660 // result = 0, offset to extent mapping desired FABN
1661 // result = FXRangeErr, offset to last extent in record
1662 // (i.e., kNumExtentsPerRecord-1)
1663 // extentBTreeHint - BTree hint for extent record
1664 // kNoHint = Resident extent record
1665 // endingFABNPlusOne - ending FABN +1
1666 //
1667 // Result:
1668 // noErr Found an extent that contains the given file position
1669 // FXRangeErr Given position is beyond the last allocated extent
1670 // (other) (some other internal I/O error)
1671 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
1672
1673 static OSErr SearchExtentFile(
1674 const ExtendedVCB *vcb,
1675 const FCB *fcb,
1676 SInt64 filePosition,
1677 HFSPlusExtentKey *foundExtentKey,
1678 HFSPlusExtentRecord foundExtentData,
1679 UInt32 *foundExtentIndex,
1680 UInt32 *extentBTreeHint,
1681 UInt32 *endingFABNPlusOne )
1682 {
1683 OSErr err;
1684 UInt32 filePositionBlock;
1685 SInt64 temp64;
1686 Boolean noMoreExtents;
1687
1688 temp64 = filePosition / (SInt64)vcb->blockSize;
1689 filePositionBlock = (UInt32)temp64;
1690
1691 bcopy ( fcb->fcbExtents, foundExtentData, sizeof(HFSPlusExtentRecord));
1692
1693 // Search the resident FCB first.
1694 err = SearchExtentRecord( vcb, filePositionBlock, foundExtentData, 0,
1695 foundExtentIndex, endingFABNPlusOne, &noMoreExtents );
1696
1697 if( err == noErr ) {
1698 // Found the extent. Set results accordingly
1699 *extentBTreeHint = kNoHint; // no hint, because not in the BTree
1700 foundExtentKey->keyLength = 0; // 0 = the FCB itself
1701
1702 goto Exit;
1703 }
1704
1705 // Didn't find extent in FCB. If FCB's extent record wasn't full, there's no point
1706 // in searching the extents file. Note that SearchExtentRecord left us pointing at
1707 // the last valid extent (or the first one, if none were valid). This means we need
1708 // to fill in the hint and key outputs, just like the "if" statement above.
1709 if ( noMoreExtents ) {
1710 *extentBTreeHint = kNoHint; // no hint, because not in the BTree
1711 foundExtentKey->keyLength = 0; // 0 = the FCB itself
1712 err = fxRangeErr; // There are no more extents, so must be beyond PEOF
1713 goto Exit;
1714 }
1715
1716 //
1717 // Find the desired record, or the previous record if it is the same fork
1718 //
1719 err = FindExtentRecord(vcb, (fcb->fcbFlags & fcbResourceMask) ? kResourceForkType : kDataForkType,
1720 H_FILEID(fcb), filePositionBlock, true, foundExtentKey, foundExtentData, extentBTreeHint);
1721
1722 if (err == btNotFound) {
1723 //
1724 // If we get here, the desired position is beyond the extents in the FCB, and there are no extents
1725 // in the extents file. Return the FCB's extents and a range error.
1726 //
1727 *extentBTreeHint = kNoHint;
1728 foundExtentKey->keyLength = 0;
1729 err = GetFCBExtentRecord(fcb, foundExtentData);
1730 // Note: foundExtentIndex and endingFABNPlusOne have already been set as a result of the very
1731 // first SearchExtentRecord call in this function (when searching in the FCB's extents, and
1732 // we got a range error).
1733
1734 return fxRangeErr;
1735 }
1736
1737 //
1738 // If we get here, there was either a BTree error, or we found an appropriate record.
1739 // If we found a record, then search it for the correct index into the extents.
1740 //
1741 if (err == noErr) {
1742 // Find appropriate index into extent record
1743 err = SearchExtentRecord(vcb, filePositionBlock, foundExtentData, foundExtentKey->startBlock,
1744 foundExtentIndex, endingFABNPlusOne, &noMoreExtents);
1745 }
1746
1747 Exit:
1748 return err;
1749 }
1750
1751
1752
1753 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
1754 // Routine: UpdateExtentRecord
1755 //
1756 // Function: Write new extent data to an existing extent record with a given key.
1757 // If all of the extents are empty, and the extent record is in the
1758 // extents file, then the record is deleted.
1759 //
1760 // Input: vcb - the volume containing the extents
1761 // fcb - the file that owns the extents
1762 // extentFileKey - pointer to extent key record (xkr)
1763 // If the key length is 0, then the extents are actually part
1764 // of the catalog record, stored in the FCB.
1765 // extentData - pointer to extent data record (xdr)
1766 // extentBTreeHint - hint for given key, or kNoHint
1767 //
1768 // Result: noErr = ok
1769 // (other) = error from BTree
1770 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
1771
1772 static OSErr UpdateExtentRecord (
1773 const ExtendedVCB *vcb,
1774 FCB *fcb,
1775 const HFSPlusExtentKey *extentFileKey,
1776 const HFSPlusExtentRecord extentData,
1777 UInt32 extentBTreeHint)
1778 {
1779 BTreeIterator btIterator;
1780 FSBufferDescriptor btRecord;
1781 UInt16 btRecordSize;
1782 FCB * btFCB;
1783 OSErr err = noErr;
1784
1785 if (extentFileKey->keyLength == 0) { // keyLength == 0 means the FCB's extent record
1786 BlockMoveData(extentData, fcb->fcbExtents, sizeof(HFSPlusExtentRecord));
1787 fcb->fcbFlags |= fcbModifiedMask;
1788 }
1789 else {
1790 //
1791 // Need to find and change a record in Extents BTree
1792 //
1793 btFCB = GetFileControlBlock(vcb->extentsRefNum);
1794
1795 if (vcb->vcbSigWord == kHFSSigWord) {
1796 HFSExtentKey * key; // Actual extent key used on disk in HFS
1797 HFSExtentRecord foundData; // The extent data actually found
1798
1799 key = (HFSExtentKey*) &btIterator.key;
1800 key->keyLength = kHFSExtentKeyMaximumLength;
1801 key->forkType = extentFileKey->forkType;
1802 key->fileID = extentFileKey->fileID;
1803 key->startBlock = extentFileKey->startBlock;
1804
1805 btIterator.hint.index = 0;
1806 btIterator.hint.nodeNum = extentBTreeHint;
1807
1808 btRecord.bufferAddress = &foundData;
1809 btRecord.itemSize = sizeof(HFSExtentRecord);
1810 btRecord.itemCount = 1;
1811
1812 err = BTSearchRecord(btFCB, &btIterator, kInvalidMRUCacheKey, &btRecord,
1813 &btRecordSize, &btIterator);
1814
1815 if (err == noErr)
1816 err = HFSPlusToHFSExtents(extentData, (HFSExtentDescriptor *)&foundData);
1817
1818 if (err == noErr)
1819 err = BTReplaceRecord(btFCB, &btIterator, &btRecord, btRecordSize);
1820 }
1821 else { // HFS Plus volume
1822 HFSPlusExtentRecord foundData; // The extent data actually found
1823
1824 BlockMoveData(extentFileKey, &btIterator.key, sizeof(HFSPlusExtentKey));
1825
1826 btIterator.hint.index = 0;
1827 btIterator.hint.nodeNum = extentBTreeHint;
1828
1829 btRecord.bufferAddress = &foundData;
1830 btRecord.itemSize = sizeof(HFSPlusExtentRecord);
1831 btRecord.itemCount = 1;
1832
1833 err = BTSearchRecord(btFCB, &btIterator, kInvalidMRUCacheKey, &btRecord,
1834 &btRecordSize, &btIterator);
1835
1836 if (err == noErr) {
1837 BlockMoveData(extentData, &foundData, sizeof(HFSPlusExtentRecord));
1838 err = BTReplaceRecord(btFCB, &btIterator, &btRecord, btRecordSize);
1839 }
1840 }
1841 }
1842
1843 return err;
1844 }
1845
1846
1847
1848 void HFSToHFSPlusExtents(
1849 const HFSExtentRecord oldExtents,
1850 HFSPlusExtentRecord newExtents)
1851 {
1852 UInt32 i;
1853
1854 // copy the first 3 extents
1855 newExtents[0].startBlock = oldExtents[0].startBlock;
1856 newExtents[0].blockCount = oldExtents[0].blockCount;
1857 newExtents[1].startBlock = oldExtents[1].startBlock;
1858 newExtents[1].blockCount = oldExtents[1].blockCount;
1859 newExtents[2].startBlock = oldExtents[2].startBlock;
1860 newExtents[2].blockCount = oldExtents[2].blockCount;
1861
1862 // zero out the remaining ones
1863 for (i = 3; i < kHFSPlusExtentDensity; ++i)
1864 {
1865 newExtents[i].startBlock = 0;
1866 newExtents[i].blockCount = 0;
1867 }
1868 }
1869
1870
1871
1872 OSErr HFSPlusToHFSExtents(
1873 const HFSPlusExtentRecord oldExtents,
1874 HFSExtentRecord newExtents)
1875 {
1876 OSErr err;
1877
1878 err = noErr;
1879
1880 // copy the first 3 extents
1881 newExtents[0].startBlock = oldExtents[0].startBlock;
1882 newExtents[0].blockCount = oldExtents[0].blockCount;
1883 newExtents[1].startBlock = oldExtents[1].startBlock;
1884 newExtents[1].blockCount = oldExtents[1].blockCount;
1885 newExtents[2].startBlock = oldExtents[2].startBlock;
1886 newExtents[2].blockCount = oldExtents[2].blockCount;
1887
1888 #if DEBUG_BUILD
1889 if (oldExtents[3].startBlock || oldExtents[3].blockCount) {
1890 DebugStr("\pExtentRecord with > 3 extents is invalid for HFS");
1891 err = fsDSIntErr;
1892 }
1893 #endif
1894
1895 return err;
1896 }
1897
1898
1899
1900
1901 OSErr GetFCBExtentRecord(
1902 const FCB *fcb,
1903 HFSPlusExtentRecord extents)
1904 {
1905
1906 BlockMoveData(fcb->fcbExtents, extents, sizeof(HFSPlusExtentRecord));
1907
1908 return noErr;
1909 }
1910
1911
1912
1913 //ÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑ
1914 // Routine: MapFileBlockFromFCB
1915 //
1916 // Function: Determine if the given file offset is within the set of extents
1917 // stored in the FCB. If so, return the file allocation
1918 // block number of the start of the extent, volume allocation block number
1919 // of the start of the extent, and file allocation block number immediately
1920 // following the extent.
1921 //
1922 // Input: vcb - the volume containing the extents
1923 // fcb - the file that owns the extents
1924 // offset - desired offset in bytes
1925 //
1926 // Output: firstFABN - file alloc block number of start of extent
1927 // firstBlock - volume alloc block number of start of extent
1928 // nextFABN - file alloc block number of next extent
1929 //
1930 // Result: noErr = ok
1931 // fxRangeErr = beyond FCB's extents
1932 //ÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑ
1933 static OSErr MapFileBlockFromFCB(
1934 const ExtendedVCB *vcb,
1935 const FCB *fcb,
1936 SInt64 offset, // Desired offset in bytes from start of file
1937 UInt32 *firstFABN, // FABN of first block of found extent
1938 UInt32 *firstBlock, // Corresponding allocation block number
1939 UInt32 *nextFABN) // FABN of block after end of extent
1940 {
1941 UInt32 index;
1942 UInt32 offsetBlocks;
1943 SInt64 temp64;
1944
1945 temp64 = offset / (SInt64)vcb->blockSize;
1946 offsetBlocks = (UInt32)temp64;
1947
1948 if (vcb->vcbSigWord == kHFSSigWord) {
1949 /* XXX SER Do we need to test for overflow values ??? */
1950 UInt16 blockCount;
1951 UInt16 currentFABN;
1952
1953 currentFABN = 0;
1954
1955 for (index=0; index<kHFSExtentDensity; index++) {
1956
1957 blockCount = fcb->fcbExtents[index].blockCount;
1958
1959 if (blockCount == 0)
1960 return fxRangeErr; // ran out of extents!
1961
1962 // Is it in this extent?
1963 if (offsetBlocks < blockCount) {
1964 *firstFABN = currentFABN;
1965 *firstBlock = fcb->fcbExtents[index].startBlock;
1966 currentFABN += blockCount; // faster to add these as UInt16 first, then extend to UInt32
1967 *nextFABN = currentFABN;
1968 return noErr; // found the right extent
1969 }
1970
1971 // Not in current extent, so adjust counters and loop again
1972 offsetBlocks -= blockCount;
1973 currentFABN += blockCount;
1974 }
1975 }
1976 else {
1977 UInt32 blockCount;
1978 UInt32 currentFABN;
1979
1980 currentFABN = 0;
1981
1982 for (index=0; index<kHFSPlusExtentDensity; index++) {
1983
1984 blockCount = fcb->fcbExtents[index].blockCount;
1985
1986 if (blockCount == 0)
1987 return fxRangeErr; // ran out of extents!
1988
1989 // Is it in this extent?
1990 if (offsetBlocks < blockCount) {
1991 *firstFABN = currentFABN;
1992 *firstBlock = fcb->fcbExtents[index].startBlock;
1993 *nextFABN = currentFABN + blockCount;
1994 return noErr; // found the right extent
1995 }
1996
1997 // Not in current extent, so adjust counters and loop again
1998 offsetBlocks -= blockCount;
1999 currentFABN += blockCount;
2000 }
2001 }
2002
2003 // If we fall through here, the extent record was full, but the offset was
2004 // beyond those extents.
2005
2006 return fxRangeErr;
2007 }
2008
2009
2010 //_________________________________________________________________________________
2011 //
2012 // Routine: ExtentsAreIntegral
2013 //
2014 // Purpose: Ensure that each extent can hold an integral number of nodes
2015 // Called by the NodesAreContiguous function
2016 //_________________________________________________________________________________
2017
2018 static Boolean ExtentsAreIntegral(
2019 const HFSPlusExtentRecord extentRecord,
2020 UInt32 mask,
2021 UInt32 *blocksChecked,
2022 Boolean *checkedLastExtent)
2023 {
2024 UInt32 blocks;
2025 UInt32 extentIndex;
2026
2027 *blocksChecked = 0;
2028 *checkedLastExtent = false;
2029
2030 for(extentIndex = 0; extentIndex < kHFSPlusExtentDensity; extentIndex++)
2031 {
2032 blocks = extentRecord[extentIndex].blockCount;
2033
2034 if ( blocks == 0 )
2035 {
2036 *checkedLastExtent = true;
2037 break;
2038 }
2039
2040 *blocksChecked += blocks;
2041
2042 if (blocks & mask)
2043 return false;
2044 }
2045
2046 return true;
2047 }
2048
2049
2050 //_________________________________________________________________________________
2051 //
2052 // Routine: NodesAreContiguous
2053 //
2054 // Purpose: Ensure that all b-tree nodes are contiguous on disk
2055 // Called by BTOpenPath during volume mount
2056 //_________________________________________________________________________________
2057
2058 Boolean NodesAreContiguous(
2059 ExtendedVCB *vcb,
2060 FCB *fcb,
2061 UInt32 nodeSize)
2062 {
2063 UInt32 mask;
2064 UInt32 startBlock;
2065 UInt32 blocksChecked;
2066 UInt32 hint;
2067 HFSPlusExtentKey key;
2068 HFSPlusExtentRecord extents;
2069 OSErr result;
2070 Boolean lastExtentReached;
2071
2072
2073 if (vcb->blockSize >= nodeSize)
2074 return TRUE;
2075
2076 mask = (nodeSize / vcb->blockSize) - 1;
2077
2078 // check the local extents
2079 (void) GetFCBExtentRecord(fcb, extents);
2080 if ( !ExtentsAreIntegral(extents, mask, &blocksChecked, &lastExtentReached) )
2081 return FALSE;
2082
2083 if (lastExtentReached || (SInt64)((SInt64)blocksChecked * (SInt64)vcb->blockSize) >= fcb->fcbPLen)
2084 return TRUE;
2085
2086 startBlock = blocksChecked;
2087
2088 // check the overflow extents (if any)
2089 while ( !lastExtentReached )
2090 {
2091 result = FindExtentRecord(vcb, kDataForkType, H_FILEID(fcb), startBlock, FALSE, &key, extents, &hint);
2092 if (result) break;
2093
2094 if ( !ExtentsAreIntegral(extents, mask, &blocksChecked, &lastExtentReached) )
2095 return FALSE;
2096
2097 startBlock += blocksChecked;
2098 }
2099
2100 return TRUE;
2101 }
2102
mirror of XNU