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


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