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