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