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