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