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