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