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