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