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


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