]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfscommon/Misc/FileExtentMapping.c
projects / apple / xnu.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
xnu-517.12.7.tar.gz
[apple/xnu.git] / bsd / hfs / hfscommon / Misc / FileExtentMapping.c
1 /*
2 * Copyright (c) 2000-2003 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 <sys/malloc.h>
163
164 /*
165 ============================================================
166 Public (Exported) Routines:
167 ============================================================
168 DeAllocFile Deallocate all disk space allocated to a specified file.
169 Both forks are deallocated.
170
171 ExtendFileC Allocate more space to a given file.
172
173 CompareExtentKeys
174 Compare two extents file keys (a search key and a trial
175 key). Used by the BTree manager when searching for,
176 adding, or deleting keys in the extents file of an HFS
177 volume.
178
179 CompareExtentKeysPlus
180 Compare two extents file keys (a search key and a trial
181 key). Used by the BTree manager when searching for,
182 adding, or deleting keys in the extents file of an HFS+
183 volume.
184
185 MapFileBlockC Convert (map) an offset within a given file into a
186 physical disk address.
187
188 TruncateFileC Truncates the disk space allocated to a file. The file
189 space is truncated to a specified new physical EOF, rounded
190 up to the next allocation block boundry. There is an option
191 to truncate to the end of the extent containing the new EOF.
192
193 FlushExtentFile
194 Flush the extents file for a given volume.
195
196 GrowParallelFCBs
197 Make sure the parallel FCB entries are big enough to support
198 the HFS+ ExtentRecord. If not, the array is grown and the
199 pre-existing data copied over.
200
201 AdjustEOF
202 Copy EOF, physical length, and extent records from one FCB
203 to all other FCBs for that fork. This is used when a file is
204 grown or shrunk as the result of a Write, SetEOF, or Allocate.
205
206 MapLogicalToPhysical
207 Map some position in a file to a volume block number. Also
208 returns the number of contiguous bytes that are mapped there.
209 This is a queued HFSDispatch call that does the equivalent of
210 MapFileBlockC, using a parameter block.
211
212 ============================================================
213 Internal Routines:
214 ============================================================
215 FindExtentRecord
216 Search the extents BTree for a particular extent record.
217 SearchExtentFile
218 Search the FCB and extents file for an extent record that
219 contains a given file position (in bytes).
220 SearchExtentRecord
221 Search a given extent record to see if it contains a given
222 file position (in bytes). Used by SearchExtentFile.
223 ReleaseExtents
224 Deallocate all allocation blocks in all extents of an extent
225 data record.
226 TruncateExtents
227 Deallocate blocks and delete extent records for all allocation
228 blocks beyond a certain point in a file. The starting point
229 must be the first file allocation block for some extent record
230 for the file.
231 DeallocateFork
232 Deallocate all allocation blocks belonging to a given fork.
233 UpdateExtentRecord
234 If the extent record came from the extents file, write out
235 the updated record; otherwise, copy the updated record into
236 the FCB resident extent record. If the record has no extents,
237 and was in the extents file, then delete the record instead.
238 */
239
240 static const SInt64 kTwoGigabytes = 0x80000000LL;
241
242 enum
243 {
244 kDataForkType = 0,
245 kResourceForkType = 0xFF,
246
247 kPreviousRecord = -1
248 };
249
250
251 static OSErr HFSPlusToHFSExtents(
252 const HFSPlusExtentRecord oldExtents,
253 HFSExtentRecord newExtents);
254
255 static OSErr FindExtentRecord(
256 const ExtendedVCB *vcb,
257 UInt8 forkType,
258 UInt32 fileID,
259 UInt32 startBlock,
260 Boolean allowPrevious,
261 HFSPlusExtentKey *foundKey,
262 HFSPlusExtentRecord foundData,
263 UInt32 *foundHint);
264
265 static OSErr DeleteExtentRecord(
266 const ExtendedVCB *vcb,
267 UInt8 forkType,
268 UInt32 fileID,
269 UInt32 startBlock);
270
271 static OSErr CreateExtentRecord(
272 const ExtendedVCB *vcb,
273 HFSPlusExtentKey *key,
274 HFSPlusExtentRecord extents,
275 UInt32 *hint);
276
277
278 static OSErr GetFCBExtentRecord(
279 const FCB *fcb,
280 HFSPlusExtentRecord extents);
281
282 static OSErr SearchExtentFile(
283 const ExtendedVCB *vcb,
284 const FCB *fcb,
285 SInt64 filePosition,
286 HFSPlusExtentKey *foundExtentKey,
287 HFSPlusExtentRecord foundExtentData,
288 UInt32 *foundExtentDataIndex,
289 UInt32 *extentBTreeHint,
290 UInt32 *endingFABNPlusOne );
291
292 static OSErr SearchExtentRecord(
293 const ExtendedVCB *vcb,
294 UInt32 searchFABN,
295 const HFSPlusExtentRecord extentData,
296 UInt32 extentDataStartFABN,
297 UInt32 *foundExtentDataOffset,
298 UInt32 *endingFABNPlusOne,
299 Boolean *noMoreExtents);
300
301 static OSErr ReleaseExtents(
302 ExtendedVCB *vcb,
303 const HFSPlusExtentRecord extentRecord,
304 UInt32 *numReleasedAllocationBlocks,
305 Boolean *releasedLastExtent);
306
307 static OSErr DeallocateFork(
308 ExtendedVCB *vcb,
309 HFSCatalogNodeID fileID,
310 UInt8 forkType,
311 HFSPlusExtentRecord catalogExtents,
312 Boolean * recordDeleted);
313
314 static OSErr TruncateExtents(
315 ExtendedVCB *vcb,
316 UInt8 forkType,
317 UInt32 fileID,
318 UInt32 startBlock,
319 Boolean * recordDeleted);
320
321 static OSErr UpdateExtentRecord (
322 const ExtendedVCB *vcb,
323 FCB *fcb,
324 const HFSPlusExtentKey *extentFileKey,
325 const HFSPlusExtentRecord extentData,
326 UInt32 extentBTreeHint);
327
328 static Boolean ExtentsAreIntegral(
329 const HFSPlusExtentRecord extentRecord,
330 UInt32 mask,
331 UInt32 *blocksChecked,
332 Boolean *checkedLastExtent);
333
334 //_________________________________________________________________________________
335 //
336 // Routine: FindExtentRecord
337 //
338 // Purpose: Search the extents BTree for an extent record matching the given
339 // FileID, fork, and starting file allocation block number.
340 //
341 // Inputs:
342 // vcb Volume to search
343 // forkType 0 = data fork, -1 = resource fork
344 // fileID File's FileID (CatalogNodeID)
345 // startBlock Starting file allocation block number
346 // allowPrevious If the desired record isn't found and this flag is set,
347 // then see if the previous record belongs to the same fork.
348 // If so, then return it.
349 //
350 // Outputs:
351 // foundKey The key data for the record actually found
352 // foundData The extent record actually found (NOTE: on an HFS volume, the
353 // fourth entry will be zeroes.
354 // foundHint The BTree hint to find the node again
355 //_________________________________________________________________________________
356 static OSErr FindExtentRecord(
357 const ExtendedVCB *vcb,
358 UInt8 forkType,
359 UInt32 fileID,
360 UInt32 startBlock,
361 Boolean allowPrevious,
362 HFSPlusExtentKey *foundKey,
363 HFSPlusExtentRecord foundData,
364 UInt32 *foundHint)
365 {
366 FCB * fcb;
367 BTreeIterator *btIterator;
368 FSBufferDescriptor btRecord;
369 OSErr err;
370 UInt16 btRecordSize;
371
372 err = noErr;
373 if (foundHint)
374 *foundHint = 0;
375 fcb = GetFileControlBlock(vcb->extentsRefNum);
376
377 MALLOC(btIterator, BTreeIterator *, sizeof(*btIterator), M_TEMP, M_WAITOK);
378 bzero(btIterator, sizeof(*btIterator));
379
380 if (vcb->vcbSigWord == kHFSSigWord) {
381 HFSExtentKey * extentKeyPtr;
382 HFSExtentRecord extentData;
383
384 extentKeyPtr = (HFSExtentKey*) &btIterator->key;
385 extentKeyPtr->keyLength = kHFSExtentKeyMaximumLength;
386 extentKeyPtr->forkType = forkType;
387 extentKeyPtr->fileID = fileID;
388 extentKeyPtr->startBlock = startBlock;
389
390 btRecord.bufferAddress = &extentData;
391 btRecord.itemSize = sizeof(HFSExtentRecord);
392 btRecord.itemCount = 1;
393
394 err = BTSearchRecord(fcb, btIterator, &btRecord, &btRecordSize, btIterator);
395
396 if (err == btNotFound && allowPrevious) {
397 err = BTIterateRecord(fcb, kBTreePrevRecord, btIterator, &btRecord, &btRecordSize);
398
399 // A previous record may not exist, so just return btNotFound (like we would if
400 // it was for the wrong file/fork).
401 if (err == (OSErr) fsBTStartOfIterationErr) //¥¥ fsBTStartOfIterationErr is type unsigned long
402 err = btNotFound;
403
404 if (err == noErr) {
405 // Found a previous record. Does it belong to the same fork of the same file?
406 if (extentKeyPtr->fileID != fileID || extentKeyPtr->forkType != forkType)
407 err = btNotFound;
408 }
409 }
410
411 if (err == noErr) {
412 UInt16 i;
413
414 // Copy the found key back for the caller
415 if (foundKey) {
416 foundKey->keyLength = kHFSPlusExtentKeyMaximumLength;
417 foundKey->forkType = extentKeyPtr->forkType;
418 foundKey->pad = 0;
419 foundKey->fileID = extentKeyPtr->fileID;
420 foundKey->startBlock = extentKeyPtr->startBlock;
421 }
422 // Copy the found data back for the caller
423 foundData[0].startBlock = extentData[0].startBlock;
424 foundData[0].blockCount = extentData[0].blockCount;
425 foundData[1].startBlock = extentData[1].startBlock;
426 foundData[1].blockCount = extentData[1].blockCount;
427 foundData[2].startBlock = extentData[2].startBlock;
428 foundData[2].blockCount = extentData[2].blockCount;
429
430 for (i = 3; i < kHFSPlusExtentDensity; ++i)
431 {
432 foundData[i].startBlock = 0;
433 foundData[i].blockCount = 0;
434 }
435 }
436 }
437 else { // HFS Plus volume
438 HFSPlusExtentKey * extentKeyPtr;
439 HFSPlusExtentRecord extentData;
440
441 extentKeyPtr = (HFSPlusExtentKey*) &btIterator->key;
442 extentKeyPtr->keyLength = kHFSPlusExtentKeyMaximumLength;
443 extentKeyPtr->forkType = forkType;
444 extentKeyPtr->pad = 0;
445 extentKeyPtr->fileID = fileID;
446 extentKeyPtr->startBlock = startBlock;
447
448 btRecord.bufferAddress = &extentData;
449 btRecord.itemSize = sizeof(HFSPlusExtentRecord);
450 btRecord.itemCount = 1;
451
452 err = BTSearchRecord(fcb, btIterator, &btRecord, &btRecordSize, btIterator);
453
454 if (err == btNotFound && allowPrevious) {
455 err = BTIterateRecord(fcb, kBTreePrevRecord, btIterator, &btRecord, &btRecordSize);
456
457 // A previous record may not exist, so just return btNotFound (like we would if
458 // it was for the wrong file/fork).
459 if (err == (OSErr) fsBTStartOfIterationErr) //¥¥ fsBTStartOfIterationErr is type unsigned long
460 err = btNotFound;
461
462 if (err == noErr) {
463 // Found a previous record. Does it belong to the same fork of the same file?
464 if (extentKeyPtr->fileID != fileID || extentKeyPtr->forkType != forkType)
465 err = btNotFound;
466 }
467 }
468
469 if (err == noErr) {
470 // Copy the found key back for the caller
471 if (foundKey)
472 BlockMoveData(extentKeyPtr, foundKey, sizeof(HFSPlusExtentKey));
473 // Copy the found data back for the caller
474 BlockMoveData(&extentData, foundData, sizeof(HFSPlusExtentRecord));
475 }
476 }
477
478 if (foundHint)
479 *foundHint = btIterator->hint.nodeNum;
480 FREE(btIterator, M_TEMP);
481 return err;
482 }
483
484
485
486 static OSErr CreateExtentRecord(
487 const ExtendedVCB *vcb,
488 HFSPlusExtentKey *key,
489 HFSPlusExtentRecord extents,
490 UInt32 *hint)
491 {
492 BTreeIterator * btIterator;
493 FSBufferDescriptor btRecord;
494 UInt16 btRecordSize;
495 OSErr err;
496
497 err = noErr;
498 *hint = 0;
499
500 MALLOC(btIterator, BTreeIterator *, sizeof(*btIterator), M_TEMP, M_WAITOK);
501 bzero(btIterator, sizeof(*btIterator));
502
503 if (vcb->vcbSigWord == kHFSSigWord) {
504 HFSExtentKey * keyPtr;
505 HFSExtentRecord data;
506
507 btRecordSize = sizeof(HFSExtentRecord);
508 btRecord.bufferAddress = &data;
509 btRecord.itemSize = btRecordSize;
510 btRecord.itemCount = 1;
511
512 keyPtr = (HFSExtentKey*) &btIterator->key;
513 keyPtr->keyLength = kHFSExtentKeyMaximumLength;
514 keyPtr->forkType = key->forkType;
515 keyPtr->fileID = key->fileID;
516 keyPtr->startBlock = key->startBlock;
517
518 err = HFSPlusToHFSExtents(extents, data);
519 }
520 else { // HFS Plus volume
521 btRecordSize = sizeof(HFSPlusExtentRecord);
522 btRecord.bufferAddress = extents;
523 btRecord.itemSize = btRecordSize;
524 btRecord.itemCount = 1;
525
526 BlockMoveData(key, &btIterator->key, sizeof(HFSPlusExtentKey));
527 }
528
529 if (err == noErr)
530 err = BTInsertRecord(GetFileControlBlock(vcb->extentsRefNum), btIterator, &btRecord, btRecordSize);
531
532 if (err == noErr)
533 *hint = btIterator->hint.nodeNum;
534
535 (void) BTFlushPath(GetFileControlBlock(vcb->extentsRefNum));
536
537 FREE(btIterator, M_TEMP);
538 return err;
539 }
540
541
542 static OSErr DeleteExtentRecord(
543 const ExtendedVCB *vcb,
544 UInt8 forkType,
545 UInt32 fileID,
546 UInt32 startBlock)
547 {
548 BTreeIterator * btIterator;
549 OSErr err;
550
551 err = noErr;
552
553 MALLOC(btIterator, BTreeIterator *, sizeof(*btIterator), M_TEMP, M_WAITOK);
554 bzero(btIterator, sizeof(*btIterator));
555
556 if (vcb->vcbSigWord == kHFSSigWord) {
557 HFSExtentKey * keyPtr;
558
559 keyPtr = (HFSExtentKey*) &btIterator->key;
560 keyPtr->keyLength = kHFSExtentKeyMaximumLength;
561 keyPtr->forkType = forkType;
562 keyPtr->fileID = fileID;
563 keyPtr->startBlock = startBlock;
564 }
565 else { // HFS Plus volume
566 HFSPlusExtentKey * keyPtr;
567
568 keyPtr = (HFSPlusExtentKey*) &btIterator->key;
569 keyPtr->keyLength = kHFSPlusExtentKeyMaximumLength;
570 keyPtr->forkType = forkType;
571 keyPtr->pad = 0;
572 keyPtr->fileID = fileID;
573 keyPtr->startBlock = startBlock;
574 }
575
576 err = BTDeleteRecord(GetFileControlBlock(vcb->extentsRefNum), btIterator);
577 (void) BTFlushPath(GetFileControlBlock(vcb->extentsRefNum));
578
579 FREE(btIterator, M_TEMP);
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 __private_extern__
608 OSErr MapFileBlockC (
609 ExtendedVCB *vcb, // volume that file resides on
610 FCB *fcb, // FCB of file
611 size_t numberOfBytes, // number of contiguous bytes desired
612 off_t offset, // starting offset within file (in bytes)
613 daddr_t *startSector, // first sector (NOT an allocation block)
614 size_t *availableBytes) // number of contiguous bytes (up to numberOfBytes)
615 {
616 OSErr err;
617 UInt32 allocBlockSize; // Size of the volume's allocation block
618 UInt32 sectorSize;
619 HFSPlusExtentKey foundKey;
620 HFSPlusExtentRecord foundData;
621 UInt32 foundIndex;
622 UInt32 hint;
623 UInt32 firstFABN; // file allocation block of first block in found extent
624 UInt32 nextFABN; // file allocation block of block after end of found extent
625 off_t dataEnd; // (offset) end of range that is contiguous
626 UInt32 sectorsPerBlock; // Number of sectors per allocation block
627 UInt32 startBlock; // volume allocation block corresponding to firstFABN
628 daddr_t temp;
629 off_t tmpOff;
630
631 allocBlockSize = vcb->blockSize;
632 sectorSize = VCBTOHFS(vcb)->hfs_phys_block_size;
633
634 err = SearchExtentFile(vcb, fcb, offset, &foundKey, foundData, &foundIndex, &hint, &nextFABN);
635 if (err == noErr) {
636 startBlock = foundData[foundIndex].startBlock;
637 firstFABN = nextFABN - foundData[foundIndex].blockCount;
638 }
639
640 if (err != noErr)
641 {
642 return err;
643 }
644
645 //
646 // Determine the end of the available space. It will either be the end of the extent,
647 // or the file's PEOF, whichever is smaller.
648 //
649 dataEnd = (off_t)((off_t)(nextFABN) * (off_t)(allocBlockSize)); // Assume valid data through end of this extent
650 if (((off_t)fcb->ff_blocks * (off_t)allocBlockSize) < dataEnd) // Is PEOF shorter?
651 dataEnd = (off_t)fcb->ff_blocks * (off_t)allocBlockSize; // Yes, so only map up to PEOF
652
653 // Compute the number of sectors in an allocation block
654 sectorsPerBlock = allocBlockSize / sectorSize; // sectors per allocation block
655
656 //
657 // Compute the absolute sector number that contains the offset of the given file
658 // offset in sectors from start of the extent +
659 // offset in sectors from start of allocation block space
660 //
661 temp = (daddr_t)((offset - (off_t)((off_t)(firstFABN) * (off_t)(allocBlockSize)))/sectorSize);
662 temp += startBlock * sectorsPerBlock;
663
664 /* Add in any volume offsets */
665 if (vcb->vcbSigWord == kHFSPlusSigWord)
666 temp += vcb->hfsPlusIOPosOffset / sectorSize;
667 else
668 temp += vcb->vcbAlBlSt;
669
670 // Return the desired sector for file position "offset"
671 *startSector = temp;
672
673 //
674 // Determine the number of contiguous bytes until the end of the extent
675 // (or the amount they asked for, whichever comes first).
676 //
677 if (availableBytes)
678 {
679 tmpOff = dataEnd - offset;
680 if (tmpOff > (off_t)(numberOfBytes))
681 *availableBytes = numberOfBytes; // more there than they asked for, so pin the output
682 else
683 *availableBytes = tmpOff;
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 __private_extern__
822 OSErr FlushExtentFile( ExtendedVCB *vcb )
823 {
824 FCB * fcb;
825 OSErr err;
826
827 fcb = GetFileControlBlock(vcb->extentsRefNum);
828 err = BTFlushPath(fcb);
829 if ( err == noErr )
830 {
831 // If the FCB for the extent "file" is dirty, mark the VCB as dirty.
832
833 if (FTOC(fcb)->c_flag & C_MODIFIED)
834 {
835 MarkVCBDirty( vcb );
836 // err = FlushVolumeControlBlock( vcb );
837 }
838 }
839
840 return( err );
841 }
842
843
844 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
845 // Routine: CompareExtentKeys
846 //
847 // Function: Compares two extent file keys (a search key and a trial key) for
848 // an HFS volume.
849 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
850
851 __private_extern__
852 SInt32 CompareExtentKeys( const HFSExtentKey *searchKey, const HFSExtentKey *trialKey )
853 {
854 SInt32 result; // ± 1
855
856 #if DEBUG_BUILD
857 if (searchKey->keyLength != kHFSExtentKeyMaximumLength)
858 DebugStr("\pHFS: search Key is wrong length");
859 if (trialKey->keyLength != kHFSExtentKeyMaximumLength)
860 DebugStr("\pHFS: trial Key is wrong length");
861 #endif
862
863 result = -1; // assume searchKey < trialKey
864
865 if (searchKey->fileID == trialKey->fileID) {
866 //
867 // FileNum's are equal; compare fork types
868 //
869 if (searchKey->forkType == trialKey->forkType) {
870 //
871 // Fork types are equal; compare allocation block number
872 //
873 if (searchKey->startBlock == trialKey->startBlock) {
874 //
875 // Everything is equal
876 //
877 result = 0;
878 }
879 else {
880 //
881 // Allocation block numbers differ; determine sign
882 //
883 if (searchKey->startBlock > trialKey->startBlock)
884 result = 1;
885 }
886 }
887 else {
888 //
889 // Fork types differ; determine sign
890 //
891 if (searchKey->forkType > trialKey->forkType)
892 result = 1;
893 }
894 }
895 else {
896 //
897 // FileNums differ; determine sign
898 //
899 if (searchKey->fileID > trialKey->fileID)
900 result = 1;
901 }
902
903 return( result );
904 }
905
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: CompareExtentKeysPlus
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 __private_extern__
916 SInt32 CompareExtentKeysPlus( const HFSPlusExtentKey *searchKey, const HFSPlusExtentKey *trialKey )
917 {
918 SInt32 result; // ± 1
919
920 #if DEBUG_BUILD
921 if (searchKey->keyLength != kHFSPlusExtentKeyMaximumLength)
922 DebugStr("\pHFS: search Key is wrong length");
923 if (trialKey->keyLength != kHFSPlusExtentKeyMaximumLength)
924 DebugStr("\pHFS: trial Key is wrong length");
925 #endif
926
927 result = -1; // assume searchKey < trialKey
928
929 if (searchKey->fileID == trialKey->fileID) {
930 //
931 // FileNum's are equal; compare fork types
932 //
933 if (searchKey->forkType == trialKey->forkType) {
934 //
935 // Fork types are equal; compare allocation block number
936 //
937 if (searchKey->startBlock == trialKey->startBlock) {
938 //
939 // Everything is equal
940 //
941 result = 0;
942 }
943 else {
944 //
945 // Allocation block numbers differ; determine sign
946 //
947 if (searchKey->startBlock > trialKey->startBlock)
948 result = 1;
949 }
950 }
951 else {
952 //
953 // Fork types differ; determine sign
954 //
955 if (searchKey->forkType > trialKey->forkType)
956 result = 1;
957 }
958 }
959 else {
960 //
961 // FileNums differ; determine sign
962 //
963 if (searchKey->fileID > trialKey->fileID)
964 result = 1;
965 }
966
967 return( result );
968 }
969
970 /*
971 * Add a file extent to a file.
972 *
973 * Used by hfs_extendfs to extend the volume allocation bitmap file.
974 *
975 */
976 __private_extern__
977 int
978 AddFileExtent(ExtendedVCB *vcb, FCB *fcb, UInt32 startBlock, UInt32 blockCount)
979 {
980 HFSPlusExtentKey foundKey;
981 HFSPlusExtentRecord foundData;
982 UInt32 foundIndex;
983 UInt32 hint;
984 UInt32 nextBlock;
985 SInt64 peof;
986 int i;
987 int error;
988
989 peof = (SInt64)(fcb->ff_blocks + blockCount) * (SInt64)vcb->blockSize;
990
991 error = SearchExtentFile(vcb, fcb, peof-1, &foundKey, foundData, &foundIndex, &hint, &nextBlock);
992 if (error != fxRangeErr)
993 return (EBUSY);
994
995 /*
996 * Add new extent. See if there is room in the current record.
997 */
998 if (foundData[foundIndex].blockCount != 0)
999 ++foundIndex;
1000 if (foundIndex == kHFSPlusExtentDensity) {
1001 /*
1002 * Existing record is full so create a new one.
1003 */
1004 foundKey.keyLength = kHFSPlusExtentKeyMaximumLength;
1005 foundKey.forkType = kDataForkType;
1006 foundKey.pad = 0;
1007 foundKey.fileID = FTOC(fcb)->c_fileid;
1008 foundKey.startBlock = nextBlock;
1009
1010 foundData[0].startBlock = startBlock;
1011 foundData[0].blockCount = blockCount;
1012
1013 /* zero out remaining extents. */
1014 for (i = 1; i < kHFSPlusExtentDensity; ++i) {
1015 foundData[i].startBlock = 0;
1016 foundData[i].blockCount = 0;
1017 }
1018
1019 foundIndex = 0;
1020
1021 error = CreateExtentRecord(vcb, &foundKey, foundData, &hint);
1022 if (error == fxOvFlErr)
1023 error = dskFulErr;
1024 } else {
1025 /*
1026 * Add a new extent into existing record.
1027 */
1028 foundData[foundIndex].startBlock = startBlock;
1029 foundData[foundIndex].blockCount = blockCount;
1030 error = UpdateExtentRecord(vcb, fcb, &foundKey, foundData, hint);
1031 }
1032 (void) FlushExtentFile(vcb);
1033
1034 return (error);
1035 }
1036
1037
1038 //_________________________________________________________________________________
1039 //
1040 // Routine: Extendfile
1041 //
1042 // Function: Extends the disk space allocated to a file.
1043 //
1044 // Input: A2.L - VCB pointer
1045 // A1.L - pointer to FCB array
1046 // D1.W - file refnum
1047 // D3.B - option flags
1048 // kEFContigMask - force contiguous allocation
1049 // kEFAllMask - allocate all requested bytes or none
1050 // NOTE: You may not set both options.
1051 // D4.L - number of additional bytes to allocate
1052 //
1053 // Output: D0.W - result code
1054 // 0 = ok
1055 // -n = IO error
1056 // D6.L - number of bytes allocated
1057 //
1058 // Called by: FileAloc,FileWrite,SetEof
1059 //
1060 // Note: ExtendFile updates the PEOF in the FCB.
1061 //_________________________________________________________________________________
1062
1063 __private_extern__
1064 OSErr ExtendFileC (
1065 ExtendedVCB *vcb, // volume that file resides on
1066 FCB *fcb, // FCB of file to truncate
1067 SInt64 bytesToAdd, // number of bytes to allocate
1068 UInt32 blockHint, // desired starting allocation block
1069 UInt32 flags, // EFContig and/or EFAll
1070 SInt64 *actualBytesAdded) // number of bytes actually allocated
1071 {
1072 OSErr err;
1073 UInt32 volumeBlockSize;
1074 SInt64 blocksToAdd;
1075 SInt64 bytesThisExtent;
1076 HFSPlusExtentKey foundKey;
1077 HFSPlusExtentRecord foundData;
1078 UInt32 foundIndex;
1079 UInt32 hint;
1080 UInt32 nextBlock;
1081 UInt32 startBlock;
1082 Boolean allOrNothing;
1083 Boolean forceContig;
1084 Boolean wantContig;
1085 Boolean useMetaZone;
1086 Boolean needsFlush;
1087 UInt32 actualStartBlock;
1088 UInt32 actualNumBlocks;
1089 UInt32 numExtentsPerRecord;
1090 SInt64 maximumBytes;
1091 SInt64 peof;
1092 UInt32 prevblocks;
1093
1094
1095 needsFlush = false;
1096 *actualBytesAdded = 0;
1097 volumeBlockSize = vcb->blockSize;
1098 allOrNothing = ((flags & kEFAllMask) != 0);
1099 forceContig = ((flags & kEFContigMask) != 0);
1100 prevblocks = fcb->ff_blocks;
1101
1102 if (vcb->vcbSigWord == kHFSPlusSigWord)
1103 numExtentsPerRecord = kHFSPlusExtentDensity;
1104 else
1105 numExtentsPerRecord = kHFSExtentDensity;
1106
1107 //
1108 // Make sure the request and new PEOF are less than 2GB if HFS.
1109 //
1110 if (vcb->vcbSigWord == kHFSSigWord) {
1111 if (bytesToAdd >= kTwoGigabytes)
1112 goto Overflow;
1113 if ((((SInt64)fcb->ff_blocks * (SInt64)volumeBlockSize) + bytesToAdd) >= kTwoGigabytes)
1114 goto Overflow;
1115 }
1116 //
1117 // Determine how many blocks need to be allocated.
1118 // Round up the number of desired bytes to add.
1119 //
1120 blocksToAdd = howmany(bytesToAdd, volumeBlockSize);
1121 bytesToAdd = (SInt64)((SInt64)blocksToAdd * (SInt64)volumeBlockSize);
1122
1123 /*
1124 * For deferred allocations just reserve the blocks.
1125 */
1126 if ((flags & kEFDeferMask)
1127 && (vcb->vcbSigWord == kHFSPlusSigWord)
1128 && (bytesToAdd < (SInt64)HFS_MAX_DEFERED_ALLOC)
1129 && (blocksToAdd < hfs_freeblks(VCBTOHFS(vcb), 1))) {
1130 fcb->ff_unallocblocks += blocksToAdd;
1131 vcb->loanedBlocks += blocksToAdd;
1132 FTOC(fcb)->c_blocks += blocksToAdd;
1133 fcb->ff_blocks += blocksToAdd;
1134
1135 FTOC(fcb)->c_flag |= C_MODIFIED | C_FORCEUPDATE;
1136 *actualBytesAdded = bytesToAdd;
1137 return (0);
1138 }
1139 /*
1140 * Give back any unallocated blocks before doing real allocations.
1141 */
1142 if (fcb->ff_unallocblocks > 0) {
1143 blocksToAdd += fcb->ff_unallocblocks;
1144 bytesToAdd = (SInt64)blocksToAdd * (SInt64)volumeBlockSize;
1145
1146 vcb->loanedBlocks -= fcb->ff_unallocblocks;
1147 FTOC(fcb)->c_blocks -= fcb->ff_unallocblocks;
1148 fcb->ff_blocks -= fcb->ff_unallocblocks;
1149 fcb->ff_unallocblocks = 0;
1150 }
1151
1152 //
1153 // If the file's clump size is larger than the allocation block size,
1154 // then set the maximum number of bytes to the requested number of bytes
1155 // rounded up to a multiple of the clump size.
1156 //
1157 if ((vcb->vcbClpSiz > volumeBlockSize)
1158 && (bytesToAdd < (SInt64)HFS_MAX_DEFERED_ALLOC)
1159 && (flags & kEFNoClumpMask) == 0) {
1160 maximumBytes = (SInt64)howmany(bytesToAdd, vcb->vcbClpSiz);
1161 maximumBytes *= vcb->vcbClpSiz;
1162 } else {
1163 maximumBytes = bytesToAdd;
1164 }
1165
1166 //
1167 // Compute new physical EOF, rounded up to a multiple of a block.
1168 //
1169 if ((vcb->vcbSigWord == kHFSSigWord) && ((((SInt64)fcb->ff_blocks * (SInt64)volumeBlockSize) + bytesToAdd) >= kTwoGigabytes)) // Too big?
1170 if (allOrNothing) // Yes, must they have it all?
1171 goto Overflow; // Yes, can't have it
1172 else {
1173 --blocksToAdd; // No, give give 'em one block less
1174 bytesToAdd -= volumeBlockSize;
1175 }
1176
1177 //
1178 // If allocation is all-or-nothing, make sure there are
1179 // enough free blocks on the volume (quick test).
1180 //
1181 if (allOrNothing &&
1182 (blocksToAdd > hfs_freeblks(VCBTOHFS(vcb), flags & kEFReserveMask))) {
1183 err = dskFulErr;
1184 goto ErrorExit;
1185 }
1186
1187 //
1188 // See if there are already enough blocks allocated to the file.
1189 //
1190 peof = ((SInt64)fcb->ff_blocks * (SInt64)volumeBlockSize) + bytesToAdd; // potential new PEOF
1191 err = SearchExtentFile(vcb, fcb, peof-1, &foundKey, foundData, &foundIndex, &hint, &nextBlock);
1192 if (err == noErr) {
1193 // Enough blocks are already allocated. Just update the FCB to reflect the new length.
1194 fcb->ff_blocks = peof / volumeBlockSize;
1195 FTOC(fcb)->c_blocks += (bytesToAdd / volumeBlockSize);
1196 FTOC(fcb)->c_flag |= C_MODIFIED | C_FORCEUPDATE;
1197 goto Exit;
1198 }
1199 if (err != fxRangeErr) // Any real error?
1200 goto ErrorExit; // Yes, so exit immediately
1201
1202 //
1203 // Adjust the PEOF to the end of the last extent.
1204 //
1205 peof = (SInt64)((SInt64)nextBlock * (SInt64)volumeBlockSize); // currently allocated PEOF
1206 bytesThisExtent = (SInt64)(nextBlock - fcb->ff_blocks) * (SInt64)volumeBlockSize;
1207 if (bytesThisExtent != 0) {
1208 fcb->ff_blocks = nextBlock;
1209 FTOC(fcb)->c_blocks += (bytesThisExtent / volumeBlockSize);
1210 FTOC(fcb)->c_flag |= C_MODIFIED;
1211 bytesToAdd -= bytesThisExtent;
1212 }
1213
1214 //
1215 // Allocate some more space.
1216 //
1217 // First try a contiguous allocation (of the whole amount).
1218 // If that fails, get whatever we can.
1219 // If forceContig, then take whatever we got
1220 // else, keep getting bits and pieces (non-contig)
1221 err = noErr;
1222 wantContig = true;
1223 useMetaZone = flags & kEFMetadataMask;
1224 vcb->vcbFreeExtCnt = 0; /* For now, force rebuild of free extent list */
1225 do {
1226 if (blockHint != 0)
1227 startBlock = blockHint;
1228 else
1229 startBlock = foundData[foundIndex].startBlock + foundData[foundIndex].blockCount;
1230
1231 /* Force reserve checking if requested. */
1232 if (flags & kEFReserveMask) {
1233 SInt64 availbytes;
1234
1235 actualNumBlocks = 0;
1236 actualStartBlock = 0;
1237
1238 availbytes = (SInt64)hfs_freeblks(VCBTOHFS(vcb), 1) *
1239 (SInt64)volumeBlockSize;
1240 if (availbytes <= 0) {
1241 err = dskFulErr;
1242 } else {
1243 if (wantContig && (availbytes < bytesToAdd))
1244 err = dskFulErr;
1245 else {
1246 err = BlockAllocate(
1247 vcb,
1248 startBlock,
1249 howmany(MIN(bytesToAdd, availbytes), volumeBlockSize),
1250 howmany(MIN(maximumBytes, availbytes), volumeBlockSize),
1251 wantContig,
1252 useMetaZone,
1253 &actualStartBlock,
1254 &actualNumBlocks);
1255 }
1256 }
1257 } else {
1258 err = BlockAllocate(vcb, startBlock, howmany(bytesToAdd, volumeBlockSize),
1259 howmany(maximumBytes, volumeBlockSize), wantContig, useMetaZone,
1260 &actualStartBlock, &actualNumBlocks);
1261 }
1262 if (err == dskFulErr) {
1263 if (forceContig)
1264 break; // AllocContig failed because not enough contiguous space
1265 if (wantContig) {
1266 // Couldn't get one big chunk, so get whatever we can.
1267 err = noErr;
1268 wantContig = false;
1269 continue;
1270 }
1271 if (actualNumBlocks != 0)
1272 err = noErr;
1273 if (useMetaZone == 0) {
1274 /* Couldn't get anything so dip into metadat zone */
1275 err = noErr;
1276 useMetaZone = 1;
1277 continue;
1278 }
1279 }
1280 if (err == noErr) {
1281 if (actualNumBlocks != 0) {
1282 // this catalog entry *must* get forced to disk when
1283 // hfs_update() is called
1284 FTOC(fcb)->c_flag |= C_FORCEUPDATE;
1285 }
1286
1287 // Add the new extent to the existing extent record, or create a new one.
1288 if ((actualStartBlock == startBlock) && (blockHint == 0)) {
1289 // We grew the file's last extent, so just adjust the number of blocks.
1290 foundData[foundIndex].blockCount += actualNumBlocks;
1291 err = UpdateExtentRecord(vcb, fcb, &foundKey, foundData, hint);
1292 if (err != noErr) break;
1293 }
1294 else {
1295 UInt16 i;
1296
1297 // Need to add a new extent. See if there is room in the current record.
1298 if (foundData[foundIndex].blockCount != 0) // Is current extent free to use?
1299 ++foundIndex; // No, so use the next one.
1300 if (foundIndex == numExtentsPerRecord) {
1301 // This record is full. Need to create a new one.
1302 if (FTOC(fcb)->c_fileid == kHFSExtentsFileID) {
1303 (void) BlockDeallocate(vcb, actualStartBlock, actualNumBlocks);
1304 err = dskFulErr; // Oops. Can't extend extents file past first record.
1305 break;
1306 }
1307
1308 foundKey.keyLength = kHFSPlusExtentKeyMaximumLength;
1309 if (FORK_IS_RSRC(fcb))
1310 foundKey.forkType = kResourceForkType;
1311 else
1312 foundKey.forkType = kDataForkType;
1313 foundKey.pad = 0;
1314 foundKey.fileID = FTOC(fcb)->c_fileid;
1315 foundKey.startBlock = nextBlock;
1316
1317 foundData[0].startBlock = actualStartBlock;
1318 foundData[0].blockCount = actualNumBlocks;
1319
1320 // zero out remaining extents...
1321 for (i = 1; i < kHFSPlusExtentDensity; ++i)
1322 {
1323 foundData[i].startBlock = 0;
1324 foundData[i].blockCount = 0;
1325 }
1326
1327 foundIndex = 0;
1328
1329 err = CreateExtentRecord(vcb, &foundKey, foundData, &hint);
1330 if (err == fxOvFlErr) {
1331 // We couldn't create an extent record because extents B-tree
1332 // couldn't grow. Dellocate the extent just allocated and
1333 // return a disk full error.
1334 (void) BlockDeallocate(vcb, actualStartBlock, actualNumBlocks);
1335 err = dskFulErr;
1336 }
1337 if (err != noErr) break;
1338
1339 needsFlush = true; // We need to update the B-tree header
1340 }
1341 else {
1342 // Add a new extent into this record and update.
1343 foundData[foundIndex].startBlock = actualStartBlock;
1344 foundData[foundIndex].blockCount = actualNumBlocks;
1345 err = UpdateExtentRecord(vcb, fcb, &foundKey, foundData, hint);
1346 if (err != noErr) break;
1347 }
1348 }
1349
1350 // Figure out how many bytes were actually allocated.
1351 // NOTE: BlockAllocate could have allocated more than we asked for.
1352 // Don't set the PEOF beyond what our client asked for.
1353 nextBlock += actualNumBlocks;
1354 bytesThisExtent = (SInt64)((SInt64)actualNumBlocks * (SInt64)volumeBlockSize);
1355 if (bytesThisExtent > bytesToAdd) {
1356 bytesToAdd = 0;
1357 }
1358 else {
1359 bytesToAdd -= bytesThisExtent;
1360 maximumBytes -= bytesThisExtent;
1361 }
1362 fcb->ff_blocks += (bytesThisExtent / volumeBlockSize);
1363 FTOC(fcb)->c_blocks += (bytesThisExtent / volumeBlockSize);
1364 FTOC(fcb)->c_flag |= C_MODIFIED | C_FORCEUPDATE;
1365
1366 // If contiguous allocation was requested, then we've already got one contiguous
1367 // chunk. If we didn't get all we wanted, then adjust the error to disk full.
1368 if (forceContig) {
1369 if (bytesToAdd != 0)
1370 err = dskFulErr;
1371 break; // We've already got everything that's contiguous
1372 }
1373 }
1374 } while (err == noErr && bytesToAdd);
1375
1376 ErrorExit:
1377 Exit:
1378 if (VCBTOHFS(vcb)->hfs_flags & HFS_METADATA_ZONE) {
1379 /* Keep the roving allocator out of the metadata zone. */
1380 if (vcb->nextAllocation >= VCBTOHFS(vcb)->hfs_metazone_start &&
1381 vcb->nextAllocation <= VCBTOHFS(vcb)->hfs_metazone_end) {
1382 vcb->nextAllocation = VCBTOHFS(vcb)->hfs_metazone_end + 1;
1383 }
1384 }
1385 *actualBytesAdded = (SInt64)(fcb->ff_blocks - prevblocks) * (SInt64)volumeBlockSize;
1386
1387 if (needsFlush)
1388 (void) FlushExtentFile(vcb);
1389
1390 return err;
1391
1392 Overflow:
1393 err = fileBoundsErr;
1394 goto ErrorExit;
1395 }
1396
1397
1398
1399 //_________________________________________________________________________________
1400 //
1401 // Routine: TruncateFileC
1402 //
1403 // Function: Truncates the disk space allocated to a file. The file space is
1404 // truncated to a specified new PEOF rounded up to the next allocation
1405 // block boundry. If the 'TFTrunExt' option is specified, the file is
1406 // truncated to the end of the extent containing the new PEOF.
1407 //
1408 // Input: A2.L - VCB pointer
1409 // A1.L - pointer to FCB array
1410 // D1.W - file refnum
1411 // D2.B - option flags
1412 // TFTrunExt - truncate to the extent containing new PEOF
1413 // D3.L - new PEOF
1414 //
1415 // Output: D0.W - result code
1416 // 0 = ok
1417 // -n = IO error
1418 //
1419 // Note: TruncateFile updates the PEOF in the FCB.
1420 //_________________________________________________________________________________
1421
1422 __private_extern__
1423 OSErr TruncateFileC (
1424 ExtendedVCB *vcb, // volume that file resides on
1425 FCB *fcb, // FCB of file to truncate
1426 SInt64 peof, // new physical size for file
1427 Boolean truncateToExtent) // if true, truncate to end of extent containing newPEOF
1428 {
1429 OSErr err;
1430 UInt32 nextBlock; // next file allocation block to consider
1431 UInt32 startBlock; // Physical (volume) allocation block number of start of a range
1432 UInt32 physNumBlocks; // Number of allocation blocks in file (according to PEOF)
1433 UInt32 numBlocks;
1434 HFSPlusExtentKey key; // key for current extent record; key->keyLength == 0 if FCB's extent record
1435 UInt32 hint; // BTree hint corresponding to key
1436 HFSPlusExtentRecord extentRecord;
1437 UInt32 extentIndex;
1438 UInt32 extentNextBlock;
1439 UInt32 numExtentsPerRecord;
1440 SInt64 temp64;
1441 UInt8 forkType;
1442 Boolean extentChanged; // true if we actually changed an extent
1443 Boolean recordDeleted; // true if an extent record got deleted
1444
1445
1446 recordDeleted = false;
1447
1448 if (vcb->vcbSigWord == kHFSPlusSigWord)
1449 numExtentsPerRecord = kHFSPlusExtentDensity;
1450 else
1451 numExtentsPerRecord = kHFSExtentDensity;
1452
1453 if (FORK_IS_RSRC(fcb))
1454 forkType = kResourceForkType;
1455 else
1456 forkType = kDataForkType;
1457
1458 temp64 = fcb->ff_blocks;
1459 physNumBlocks = (UInt32)temp64;
1460
1461 //
1462 // Round newPEOF up to a multiple of the allocation block size. If new size is
1463 // two gigabytes or more, then round down by one allocation block (??? really?
1464 // shouldn't that be an error?).
1465 //
1466 nextBlock = howmany(peof, vcb->blockSize); // number of allocation blocks to remain in file
1467 peof = (SInt64)((SInt64)nextBlock * (SInt64)vcb->blockSize); // number of bytes in those blocks
1468 if ((vcb->vcbSigWord == kHFSSigWord) && (peof >= kTwoGigabytes)) {
1469 #if DEBUG_BUILD
1470 DebugStr("\pHFS: Trying to truncate a file to 2GB or more");
1471 #endif
1472 err = fileBoundsErr;
1473 goto ErrorExit;
1474 }
1475
1476 //
1477 // Update FCB's length
1478 //
1479 /*
1480 * XXX Any errors could cause ff_blocks and c_blocks to get out of sync...
1481 */
1482 numBlocks = peof / vcb->blockSize;
1483 FTOC(fcb)->c_blocks -= (fcb->ff_blocks - numBlocks);
1484 fcb->ff_blocks = numBlocks;
1485
1486 // this catalog entry is modified and *must* get forced
1487 // to disk when hfs_update() is called
1488 FTOC(fcb)->c_flag |= C_MODIFIED | C_FORCEUPDATE;
1489
1490 //
1491 // If the new PEOF is 0, then truncateToExtent has no meaning (we should always deallocate
1492 // all storage).
1493 //
1494 if (peof == 0) {
1495 int i;
1496
1497 // Deallocate all the extents for this fork
1498 err = DeallocateFork(vcb, FTOC(fcb)->c_fileid, forkType, fcb->fcbExtents, &recordDeleted);
1499 if (err != noErr) goto ErrorExit; // got some error, so return it
1500
1501 // Update the catalog extent record (making sure it's zeroed out)
1502 if (err == noErr) {
1503 for (i=0; i < kHFSPlusExtentDensity; i++) {
1504 fcb->fcbExtents[i].startBlock = 0;
1505 fcb->fcbExtents[i].blockCount = 0;
1506 }
1507 }
1508 goto Done;
1509 }
1510
1511 //
1512 // Find the extent containing byte (peof-1). This is the last extent we'll keep.
1513 // (If truncateToExtent is true, we'll keep the whole extent; otherwise, we'll only
1514 // keep up through peof). The search will tell us how many allocation blocks exist
1515 // in the found extent plus all previous extents.
1516 //
1517 err = SearchExtentFile(vcb, fcb, peof-1, &key, extentRecord, &extentIndex, &hint, &extentNextBlock);
1518 if (err != noErr) goto ErrorExit;
1519
1520 extentChanged = false; // haven't changed the extent yet
1521
1522 if (!truncateToExtent) {
1523 //
1524 // Shorten this extent. It may be the case that the entire extent gets
1525 // freed here.
1526 //
1527 numBlocks = extentNextBlock - nextBlock; // How many blocks in this extent to free up
1528 if (numBlocks != 0) {
1529 // Compute first volume allocation block to free
1530 startBlock = extentRecord[extentIndex].startBlock + extentRecord[extentIndex].blockCount - numBlocks;
1531 // Free the blocks in bitmap
1532 err = BlockDeallocate(vcb, startBlock, numBlocks);
1533 if (err != noErr) goto ErrorExit;
1534 // Adjust length of this extent
1535 extentRecord[extentIndex].blockCount -= numBlocks;
1536 // If extent is empty, set start block to 0
1537 if (extentRecord[extentIndex].blockCount == 0)
1538 extentRecord[extentIndex].startBlock = 0;
1539 // Remember that we changed the extent record
1540 extentChanged = true;
1541 }
1542 }
1543
1544 //
1545 // Now move to the next extent in the record, and set up the file allocation block number
1546 //
1547 nextBlock = extentNextBlock; // Next file allocation block to free
1548 ++extentIndex; // Its index within the extent record
1549
1550 //
1551 // Release all following extents in this extent record. Update the record.
1552 //
1553 while (extentIndex < numExtentsPerRecord && extentRecord[extentIndex].blockCount != 0) {
1554 numBlocks = extentRecord[extentIndex].blockCount;
1555 // Deallocate this extent
1556 err = BlockDeallocate(vcb, extentRecord[extentIndex].startBlock, numBlocks);
1557 if (err != noErr) goto ErrorExit;
1558 // Update next file allocation block number
1559 nextBlock += numBlocks;
1560 // Zero out start and length of this extent to delete it from record
1561 extentRecord[extentIndex].startBlock = 0;
1562 extentRecord[extentIndex].blockCount = 0;
1563 // Remember that we changed an extent
1564 extentChanged = true;
1565 // Move to next extent in record
1566 ++extentIndex;
1567 }
1568
1569 //
1570 // If any of the extents in the current record were changed, then update that
1571 // record (in the FCB, or extents file).
1572 //
1573 if (extentChanged) {
1574 err = UpdateExtentRecord(vcb, fcb, &key, extentRecord, hint);
1575 if (err != noErr) goto ErrorExit;
1576 }
1577
1578 //
1579 // If there are any following allocation blocks, then we need
1580 // to seach for their extent records and delete those allocation
1581 // blocks.
1582 //
1583 if (nextBlock < physNumBlocks)
1584 err = TruncateExtents(vcb, forkType, FTOC(fcb)->c_fileid, nextBlock, &recordDeleted);
1585
1586 Done:
1587 ErrorExit:
1588
1589 if (recordDeleted)
1590 (void) FlushExtentFile(vcb);
1591
1592 return err;
1593 }
1594
1595
1596 /*
1597 * HFS Plus only
1598 *
1599 */
1600 __private_extern__
1601 OSErr HeadTruncateFile (
1602 ExtendedVCB *vcb,
1603 FCB *fcb,
1604 UInt32 headblks)
1605 {
1606 HFSPlusExtentRecord extents;
1607 HFSPlusExtentRecord tailExtents;
1608 HFSCatalogNodeID fileID;
1609 UInt8 forkType;
1610 UInt32 blkcnt;
1611 UInt32 startblk;
1612 UInt32 blksfreed;
1613 int i, j;
1614 int error;
1615
1616
1617 if (vcb->vcbSigWord != kHFSPlusSigWord)
1618 return (-1);
1619
1620 forkType = FORK_IS_RSRC(fcb) ? kResourceForkType : kDataForkType;
1621 fileID = FTOC(fcb)->c_fileid;
1622 bzero(tailExtents, sizeof(tailExtents));
1623
1624 blksfreed = 0;
1625 startblk = 0;
1626
1627 /*
1628 * Process catalog resident extents
1629 */
1630 for (i = 0, j = 0; i < kHFSPlusExtentDensity; ++i) {
1631 blkcnt = fcb->fcbExtents[i].blockCount;
1632 if (blkcnt == 0)
1633 break; /* end of extents */
1634
1635 if (blksfreed < headblks) {
1636 error = BlockDeallocate(vcb, fcb->fcbExtents[i].startBlock, blkcnt);
1637 /*
1638 * Any errors after the first BlockDeallocate
1639 * must be ignored so we can put the file in
1640 * a known state.
1641 */
1642 if (error ) {
1643 if (i == 0)
1644 goto ErrorExit; /* uh oh */
1645 else {
1646 error = 0;
1647 printf("HeadTruncateFile: problems deallocating %s (%d)\n",
1648 FTOC(fcb)->c_desc.cd_nameptr ? FTOC(fcb)->c_desc.cd_nameptr : "", error);
1649 }
1650 }
1651
1652 blksfreed += blkcnt;
1653 fcb->fcbExtents[i].startBlock = 0;
1654 fcb->fcbExtents[i].blockCount = 0;
1655 } else {
1656 tailExtents[j].startBlock = fcb->fcbExtents[i].startBlock;
1657 tailExtents[j].blockCount = blkcnt;
1658 ++j;
1659 }
1660 startblk += blkcnt;
1661 }
1662
1663 if (blkcnt == 0)
1664 goto CopyExtents;
1665
1666 /*
1667 * Process overflow extents
1668 */
1669 for (;;) {
1670 UInt32 extblks;
1671
1672 error = FindExtentRecord(vcb, forkType, fileID, startblk, false, NULL, extents, NULL);
1673 if (error) {
1674 /*
1675 * Any errors after the first BlockDeallocate
1676 * must be ignored so we can put the file in
1677 * a known state.
1678 */
1679 if (error != btNotFound)
1680 printf("HeadTruncateFile: problems finding extents %s (%d)\n",
1681 FTOC(fcb)->c_desc.cd_nameptr ? FTOC(fcb)->c_desc.cd_nameptr : "", error);
1682 error = 0;
1683 break;
1684 }
1685
1686 for(i = 0, extblks = 0; i < kHFSPlusExtentDensity; ++i) {
1687 blkcnt = extents[i].blockCount;
1688 if (blkcnt == 0)
1689 break; /* end of extents */
1690
1691 if (blksfreed < headblks) {
1692 error = BlockDeallocate(vcb, extents[i].startBlock, blkcnt);
1693 if (error) {
1694 printf("HeadTruncateFile: problems deallocating %s (%d)\n",
1695 FTOC(fcb)->c_desc.cd_nameptr ? FTOC(fcb)->c_desc.cd_nameptr : "", error);
1696 error = 0;
1697 }
1698 blksfreed += blkcnt;
1699 } else {
1700 tailExtents[j].startBlock = extents[i].startBlock;
1701 tailExtents[j].blockCount = blkcnt;
1702 ++j;
1703 }
1704 extblks += blkcnt;
1705 }
1706
1707 error = DeleteExtentRecord(vcb, forkType, fileID, startblk);
1708 if (error) {
1709 printf("HeadTruncateFile: problems deallocating %s (%d)\n",
1710 FTOC(fcb)->c_desc.cd_nameptr ? FTOC(fcb)->c_desc.cd_nameptr : "", error);
1711 error = 0;
1712 }
1713
1714 if (blkcnt == 0)
1715 break; /* all done */
1716
1717 startblk += extblks;
1718 }
1719
1720 CopyExtents:
1721 if (blksfreed) {
1722 bcopy(tailExtents, fcb->fcbExtents, sizeof(tailExtents));
1723 blkcnt = fcb->ff_blocks - headblks;
1724 FTOC(fcb)->c_blocks -= blkcnt;
1725 fcb->ff_blocks = blkcnt;
1726
1727 FTOC(fcb)->c_flag |= C_CHANGE | C_FORCEUPDATE;
1728
1729 (void) FlushExtentFile(vcb);
1730 }
1731
1732 ErrorExit:
1733 return MacToVFSError(error);
1734 }
1735
1736
1737
1738 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
1739 // Routine: SearchExtentRecord (was XRSearch)
1740 //
1741 // Function: Searches extent record for the extent mapping a given file
1742 // allocation block number (FABN).
1743 //
1744 // Input: searchFABN - desired FABN
1745 // extentData - pointer to extent data record (xdr)
1746 // extentDataStartFABN - beginning FABN for extent record
1747 //
1748 // Output: foundExtentDataOffset - offset to extent entry within xdr
1749 // result = noErr, offset to extent mapping desired FABN
1750 // result = FXRangeErr, offset to last extent in record
1751 // endingFABNPlusOne - ending FABN +1
1752 // noMoreExtents - True if the extent was not found, and the
1753 // extent record was not full (so don't bother
1754 // looking in subsequent records); false otherwise.
1755 //
1756 // Result: noErr = ok
1757 // FXRangeErr = desired FABN > last mapped FABN in record
1758 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
1759
1760 static OSErr SearchExtentRecord(
1761 const ExtendedVCB *vcb,
1762 UInt32 searchFABN,
1763 const HFSPlusExtentRecord extentData,
1764 UInt32 extentDataStartFABN,
1765 UInt32 *foundExtentIndex,
1766 UInt32 *endingFABNPlusOne,
1767 Boolean *noMoreExtents)
1768 {
1769 OSErr err = noErr;
1770 UInt32 extentIndex;
1771 UInt32 numberOfExtents;
1772 UInt32 numAllocationBlocks;
1773 Boolean foundExtent;
1774
1775 *endingFABNPlusOne = extentDataStartFABN;
1776 *noMoreExtents = false;
1777 foundExtent = false;
1778
1779 if (vcb->vcbSigWord == kHFSPlusSigWord)
1780 numberOfExtents = kHFSPlusExtentDensity;
1781 else
1782 numberOfExtents = kHFSExtentDensity;
1783
1784 for( extentIndex = 0; extentIndex < numberOfExtents; ++extentIndex )
1785 {
1786
1787 // Loop over the extent record and find the search FABN.
1788
1789 numAllocationBlocks = extentData[extentIndex].blockCount;
1790 if ( numAllocationBlocks == 0 )
1791 {
1792 break;
1793 }
1794
1795 *endingFABNPlusOne += numAllocationBlocks;
1796
1797 if( searchFABN < *endingFABNPlusOne )
1798 {
1799 // Found the extent.
1800 foundExtent = true;
1801 break;
1802 }
1803 }
1804
1805 if( foundExtent )
1806 {
1807 // Found the extent. Note the extent offset
1808 *foundExtentIndex = extentIndex;
1809 }
1810 else
1811 {
1812 // Did not find the extent. Set foundExtentDataOffset accordingly
1813 if( extentIndex > 0 )
1814 {
1815 *foundExtentIndex = extentIndex - 1;
1816 }
1817 else
1818 {
1819 *foundExtentIndex = 0;
1820 }
1821
1822 // If we found an empty extent, then set noMoreExtents.
1823 if (extentIndex < numberOfExtents)
1824 *noMoreExtents = true;
1825
1826 // Finally, return an error to the caller
1827 err = fxRangeErr;
1828 }
1829
1830 return( err );
1831 }
1832
1833 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
1834 // Routine: SearchExtentFile (was XFSearch)
1835 //
1836 // Function: Searches extent file (including the FCB resident extent record)
1837 // for the extent mapping a given file position.
1838 //
1839 // Input: vcb - VCB pointer
1840 // fcb - FCB pointer
1841 // filePosition - file position (byte address)
1842 //
1843 // Output: foundExtentKey - extent key record (xkr)
1844 // If extent was found in the FCB's resident extent record,
1845 // then foundExtentKey->keyLength will be set to 0.
1846 // foundExtentData - extent data record(xdr)
1847 // foundExtentIndex - index to extent entry in xdr
1848 // result = 0, offset to extent mapping desired FABN
1849 // result = FXRangeErr, offset to last extent in record
1850 // (i.e., kNumExtentsPerRecord-1)
1851 // extentBTreeHint - BTree hint for extent record
1852 // kNoHint = Resident extent record
1853 // endingFABNPlusOne - ending FABN +1
1854 //
1855 // Result:
1856 // noErr Found an extent that contains the given file position
1857 // FXRangeErr Given position is beyond the last allocated extent
1858 // (other) (some other internal I/O error)
1859 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
1860
1861 static OSErr SearchExtentFile(
1862 const ExtendedVCB *vcb,
1863 const FCB *fcb,
1864 SInt64 filePosition,
1865 HFSPlusExtentKey *foundExtentKey,
1866 HFSPlusExtentRecord foundExtentData,
1867 UInt32 *foundExtentIndex,
1868 UInt32 *extentBTreeHint,
1869 UInt32 *endingFABNPlusOne )
1870 {
1871 OSErr err;
1872 UInt32 filePositionBlock;
1873 SInt64 temp64;
1874 Boolean noMoreExtents;
1875
1876 temp64 = filePosition / (SInt64)vcb->blockSize;
1877 filePositionBlock = (UInt32)temp64;
1878
1879 bcopy ( fcb->fcbExtents, foundExtentData, sizeof(HFSPlusExtentRecord));
1880
1881 // Search the resident FCB first.
1882 err = SearchExtentRecord( vcb, filePositionBlock, foundExtentData, 0,
1883 foundExtentIndex, endingFABNPlusOne, &noMoreExtents );
1884
1885 if( err == noErr ) {
1886 // Found the extent. Set results accordingly
1887 *extentBTreeHint = kNoHint; // no hint, because not in the BTree
1888 foundExtentKey->keyLength = 0; // 0 = the FCB itself
1889
1890 goto Exit;
1891 }
1892
1893 // Didn't find extent in FCB. If FCB's extent record wasn't full, there's no point
1894 // in searching the extents file. Note that SearchExtentRecord left us pointing at
1895 // the last valid extent (or the first one, if none were valid). This means we need
1896 // to fill in the hint and key outputs, just like the "if" statement above.
1897 if ( noMoreExtents ) {
1898 *extentBTreeHint = kNoHint; // no hint, because not in the BTree
1899 foundExtentKey->keyLength = 0; // 0 = the FCB itself
1900 err = fxRangeErr; // There are no more extents, so must be beyond PEOF
1901 goto Exit;
1902 }
1903
1904 //
1905 // Find the desired record, or the previous record if it is the same fork
1906 //
1907 err = FindExtentRecord(vcb, FORK_IS_RSRC(fcb) ? kResourceForkType : kDataForkType,
1908 FTOC(fcb)->c_fileid, filePositionBlock, true, foundExtentKey, foundExtentData, extentBTreeHint);
1909
1910 if (err == btNotFound) {
1911 //
1912 // If we get here, the desired position is beyond the extents in the FCB, and there are no extents
1913 // in the extents file. Return the FCB's extents and a range error.
1914 //
1915 *extentBTreeHint = kNoHint;
1916 foundExtentKey->keyLength = 0;
1917 err = GetFCBExtentRecord(fcb, foundExtentData);
1918 // Note: foundExtentIndex and endingFABNPlusOne have already been set as a result of the very
1919 // first SearchExtentRecord call in this function (when searching in the FCB's extents, and
1920 // we got a range error).
1921
1922 return fxRangeErr;
1923 }
1924
1925 //
1926 // If we get here, there was either a BTree error, or we found an appropriate record.
1927 // If we found a record, then search it for the correct index into the extents.
1928 //
1929 if (err == noErr) {
1930 // Find appropriate index into extent record
1931 err = SearchExtentRecord(vcb, filePositionBlock, foundExtentData, foundExtentKey->startBlock,
1932 foundExtentIndex, endingFABNPlusOne, &noMoreExtents);
1933 }
1934
1935 Exit:
1936 return err;
1937 }
1938
1939
1940
1941 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
1942 // Routine: UpdateExtentRecord
1943 //
1944 // Function: Write new extent data to an existing extent record with a given key.
1945 // If all of the extents are empty, and the extent record is in the
1946 // extents file, then the record is deleted.
1947 //
1948 // Input: vcb - the volume containing the extents
1949 // fcb - the file that owns the extents
1950 // extentFileKey - pointer to extent key record (xkr)
1951 // If the key length is 0, then the extents are actually part
1952 // of the catalog record, stored in the FCB.
1953 // extentData - pointer to extent data record (xdr)
1954 // extentBTreeHint - hint for given key, or kNoHint
1955 //
1956 // Result: noErr = ok
1957 // (other) = error from BTree
1958 //\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b\8b
1959
1960 static OSErr UpdateExtentRecord (
1961 const ExtendedVCB *vcb,
1962 FCB *fcb,
1963 const HFSPlusExtentKey *extentFileKey,
1964 const HFSPlusExtentRecord extentData,
1965 UInt32 extentBTreeHint)
1966 {
1967 OSErr err = noErr;
1968
1969 if (extentFileKey->keyLength == 0) { // keyLength == 0 means the FCB's extent record
1970 BlockMoveData(extentData, fcb->fcbExtents, sizeof(HFSPlusExtentRecord));
1971 FTOC(fcb)->c_flag |= C_MODIFIED;
1972 }
1973 else {
1974 BTreeIterator * btIterator;
1975 FSBufferDescriptor btRecord;
1976 UInt16 btRecordSize;
1977 FCB * btFCB;
1978
1979 //
1980 // Need to find and change a record in Extents BTree
1981 //
1982 btFCB = GetFileControlBlock(vcb->extentsRefNum);
1983
1984 MALLOC(btIterator, BTreeIterator *, sizeof(*btIterator), M_TEMP, M_WAITOK);
1985 bzero(btIterator, sizeof(*btIterator));
1986
1987 if (vcb->vcbSigWord == kHFSSigWord) {
1988 HFSExtentKey * key; // Actual extent key used on disk in HFS
1989 HFSExtentRecord foundData; // The extent data actually found
1990
1991 key = (HFSExtentKey*) &btIterator->key;
1992 key->keyLength = kHFSExtentKeyMaximumLength;
1993 key->forkType = extentFileKey->forkType;
1994 key->fileID = extentFileKey->fileID;
1995 key->startBlock = extentFileKey->startBlock;
1996
1997 btIterator->hint.index = 0;
1998 btIterator->hint.nodeNum = extentBTreeHint;
1999
2000 btRecord.bufferAddress = &foundData;
2001 btRecord.itemSize = sizeof(HFSExtentRecord);
2002 btRecord.itemCount = 1;
2003
2004 err = BTSearchRecord(btFCB, btIterator, &btRecord, &btRecordSize, btIterator);
2005
2006 if (err == noErr)
2007 err = HFSPlusToHFSExtents(extentData, (HFSExtentDescriptor *)&foundData);
2008
2009 if (err == noErr)
2010 err = BTReplaceRecord(btFCB, btIterator, &btRecord, btRecordSize);
2011 (void) BTFlushPath(btFCB);
2012 }
2013 else { // HFS Plus volume
2014 HFSPlusExtentRecord foundData; // The extent data actually found
2015
2016 BlockMoveData(extentFileKey, &btIterator->key, sizeof(HFSPlusExtentKey));
2017
2018 btIterator->hint.index = 0;
2019 btIterator->hint.nodeNum = extentBTreeHint;
2020
2021 btRecord.bufferAddress = &foundData;
2022 btRecord.itemSize = sizeof(HFSPlusExtentRecord);
2023 btRecord.itemCount = 1;
2024
2025 err = BTSearchRecord(btFCB, btIterator, &btRecord, &btRecordSize, btIterator);
2026
2027 if (err == noErr) {
2028 BlockMoveData(extentData, &foundData, sizeof(HFSPlusExtentRecord));
2029 err = BTReplaceRecord(btFCB, btIterator, &btRecord, btRecordSize);
2030 }
2031 (void) BTFlushPath(btFCB);
2032 }
2033 FREE(btIterator, M_TEMP);
2034 }
2035
2036 return err;
2037 }
2038
2039
2040
2041
2042 static OSErr HFSPlusToHFSExtents(
2043 const HFSPlusExtentRecord oldExtents,
2044 HFSExtentRecord newExtents)
2045 {
2046 OSErr err;
2047
2048 err = noErr;
2049
2050 // copy the first 3 extents
2051 newExtents[0].startBlock = oldExtents[0].startBlock;
2052 newExtents[0].blockCount = oldExtents[0].blockCount;
2053 newExtents[1].startBlock = oldExtents[1].startBlock;
2054 newExtents[1].blockCount = oldExtents[1].blockCount;
2055 newExtents[2].startBlock = oldExtents[2].startBlock;
2056 newExtents[2].blockCount = oldExtents[2].blockCount;
2057
2058 #if DEBUG_BUILD
2059 if (oldExtents[3].startBlock || oldExtents[3].blockCount) {
2060 DebugStr("\pExtentRecord with > 3 extents is invalid for HFS");
2061 err = fsDSIntErr;
2062 }
2063 #endif
2064
2065 return err;
2066 }
2067
2068
2069
2070
2071 static OSErr GetFCBExtentRecord(
2072 const FCB *fcb,
2073 HFSPlusExtentRecord extents)
2074 {
2075
2076 BlockMoveData(fcb->fcbExtents, extents, sizeof(HFSPlusExtentRecord));
2077
2078 return noErr;
2079 }
2080
2081
2082 //_________________________________________________________________________________
2083 //
2084 // Routine: ExtentsAreIntegral
2085 //
2086 // Purpose: Ensure that each extent can hold an integral number of nodes
2087 // Called by the NodesAreContiguous function
2088 //_________________________________________________________________________________
2089
2090 static Boolean ExtentsAreIntegral(
2091 const HFSPlusExtentRecord extentRecord,
2092 UInt32 mask,
2093 UInt32 *blocksChecked,
2094 Boolean *checkedLastExtent)
2095 {
2096 UInt32 blocks;
2097 UInt32 extentIndex;
2098
2099 *blocksChecked = 0;
2100 *checkedLastExtent = false;
2101
2102 for(extentIndex = 0; extentIndex < kHFSPlusExtentDensity; extentIndex++)
2103 {
2104 blocks = extentRecord[extentIndex].blockCount;
2105
2106 if ( blocks == 0 )
2107 {
2108 *checkedLastExtent = true;
2109 break;
2110 }
2111
2112 *blocksChecked += blocks;
2113
2114 if (blocks & mask)
2115 return false;
2116 }
2117
2118 return true;
2119 }
2120
2121
2122 //_________________________________________________________________________________
2123 //
2124 // Routine: NodesAreContiguous
2125 //
2126 // Purpose: Ensure that all b-tree nodes are contiguous on disk
2127 // Called by BTOpenPath during volume mount
2128 //_________________________________________________________________________________
2129
2130 __private_extern__
2131 Boolean NodesAreContiguous(
2132 ExtendedVCB *vcb,
2133 FCB *fcb,
2134 UInt32 nodeSize)
2135 {
2136 UInt32 mask;
2137 UInt32 startBlock;
2138 UInt32 blocksChecked;
2139 UInt32 hint;
2140 HFSPlusExtentKey key;
2141 HFSPlusExtentRecord extents;
2142 OSErr result;
2143 Boolean lastExtentReached;
2144
2145
2146 if (vcb->blockSize >= nodeSize)
2147 return TRUE;
2148
2149 mask = (nodeSize / vcb->blockSize) - 1;
2150
2151 // check the local extents
2152 (void) GetFCBExtentRecord(fcb, extents);
2153 if ( !ExtentsAreIntegral(extents, mask, &blocksChecked, &lastExtentReached) )
2154 return FALSE;
2155
2156 if (lastExtentReached || (SInt64)((SInt64)blocksChecked * (SInt64)vcb->blockSize) >= fcb->ff_size)
2157 return TRUE;
2158
2159 startBlock = blocksChecked;
2160
2161 // check the overflow extents (if any)
2162 while ( !lastExtentReached )
2163 {
2164 result = FindExtentRecord(vcb, kDataForkType, fcb->ff_cp->c_fileid, startBlock, FALSE, &key, extents, &hint);
2165 if (result) break;
2166
2167 if ( !ExtentsAreIntegral(extents, mask, &blocksChecked, &lastExtentReached) )
2168 return FALSE;
2169
2170 startBlock += blocksChecked;
2171 }
2172
2173 return TRUE;
2174 }
2175
mirror of XNU