[apple/xnu.git] / bsd / hfs / hfscommon / Misc / FileExtentMapping.c

/*
 * Copyright (c) 2000-2008 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 * 
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */


#include "../../hfs.h"
#include "../../hfs_format.h"
#include "../../hfs_endian.h"

#include "../headers/FileMgrInternal.h"
#include "../headers/BTreesInternal.h"

#include <sys/malloc.h>
 
/*
============================================================
Public (Exported) Routines:
============================================================

	ExtendFileC		Allocate more space to a given file.

	CompareExtentKeys
					Compare two extents file keys (a search key and a trial
					key).  Used by the BTree manager when searching for,
					adding, or deleting keys in the extents file of an HFS
					volume.
					
	CompareExtentKeysPlus
					Compare two extents file keys (a search key and a trial
					key).  Used by the BTree manager when searching for,
					adding, or deleting keys in the extents file of an HFS+
					volume.
					
	MapFileBlockC	Convert (map) an offset within a given file into a
					physical disk address.
					
	TruncateFileC	Truncates the disk space allocated to a file.  The file
					space is truncated to a specified new physical EOF, rounded
					up to the next allocation block boundry.  There is an option
					to truncate to the end of the extent containing the new EOF.
	
	FlushExtentFile
					Flush the extents file for a given volume.


============================================================
Internal Routines:
============================================================
	FindExtentRecord
					Search the extents BTree for a particular extent record.
	SearchExtentFile
					Search the FCB and extents file for an extent record that
					contains a given file position (in bytes).
	SearchExtentRecord
					Search a given extent record to see if it contains a given
					file position (in bytes).  Used by SearchExtentFile.
	ReleaseExtents
					Deallocate all allocation blocks in all extents of an extent
					data record.
	TruncateExtents
					Deallocate blocks and delete extent records for all allocation
					blocks beyond a certain point in a file.  The starting point
					must be the first file allocation block for some extent record
					for the file.
	DeallocateFork
					Deallocate all allocation blocks belonging to a given fork.
	UpdateExtentRecord
					If the extent record came from the extents file, write out
					the updated record; otherwise, copy the updated record into
					the FCB resident extent record.  If the record has no extents,
					and was in the extents file, then delete the record instead.
*/

static const int64_t kTwoGigabytes = 0x80000000LL;

enum
{
	kDataForkType			= 0,
	kResourceForkType		= 0xFF,
	
	kPreviousRecord			= -1
};


static OSErr HFSPlusToHFSExtents(
	const HFSPlusExtentRecord	oldExtents,
	HFSExtentRecord				newExtents);

static OSErr FindExtentRecord(
	const ExtendedVCB		*vcb,
	u_int8_t				forkType,
	u_int32_t				fileID,
	u_int32_t				startBlock,
	Boolean					allowPrevious,
	HFSPlusExtentKey		*foundKey,
	HFSPlusExtentRecord		foundData,
	u_int32_t				*foundHint);

static OSErr DeleteExtentRecord(
	const ExtendedVCB		*vcb,
	u_int8_t				forkType,
	u_int32_t				fileID,
	u_int32_t				startBlock);

static OSErr CreateExtentRecord(
	ExtendedVCB		*vcb,
	HFSPlusExtentKey		*key,
	HFSPlusExtentRecord		extents,
	u_int32_t				*hint);


static OSErr GetFCBExtentRecord(
	const FCB				*fcb,
	HFSPlusExtentRecord		extents);

static OSErr SearchExtentFile(
	ExtendedVCB		*vcb,
	const FCB	 			*fcb,
	int64_t 				filePosition,
	HFSPlusExtentKey		*foundExtentKey,
	HFSPlusExtentRecord		foundExtentData,
	u_int32_t				*foundExtentDataIndex,
	u_int32_t				*extentBTreeHint,
	u_int32_t				*endingFABNPlusOne );

static OSErr SearchExtentRecord(
	ExtendedVCB		*vcb,
	u_int32_t				searchFABN,
	const HFSPlusExtentRecord	extentData,
	u_int32_t				extentDataStartFABN,
	u_int32_t				*foundExtentDataOffset,
	u_int32_t				*endingFABNPlusOne,
	Boolean					*noMoreExtents);

static OSErr ReleaseExtents(
	ExtendedVCB				*vcb,
	const HFSPlusExtentRecord	extentRecord,
	u_int32_t				*numReleasedAllocationBlocks,
	Boolean 				*releasedLastExtent);

static OSErr DeallocateFork(
	ExtendedVCB 		*vcb,
	HFSCatalogNodeID	fileID,
	u_int8_t			forkType,
	HFSPlusExtentRecord	catalogExtents,
	Boolean *		recordDeleted);

static OSErr TruncateExtents(
	ExtendedVCB			*vcb,
	u_int8_t			forkType,
	u_int32_t			fileID,
	u_int32_t			startBlock,
	Boolean *			recordDeleted);

static OSErr UpdateExtentRecord (
	ExtendedVCB		*vcb,
	FCB						*fcb,
	const HFSPlusExtentKey	*extentFileKey,
	const HFSPlusExtentRecord	extentData,
	u_int32_t					extentBTreeHint);

static Boolean ExtentsAreIntegral(
	const HFSPlusExtentRecord extentRecord,
	u_int32_t	mask,
	u_int32_t	*blocksChecked,
	Boolean		*checkedLastExtent);

//_________________________________________________________________________________
//
//	Routine:	FindExtentRecord
//
//	Purpose:	Search the extents BTree for an extent record matching the given
//				FileID, fork, and starting file allocation block number.
//
//	Inputs:
//		vcb				Volume to search
//		forkType		0 = data fork, -1 = resource fork
//		fileID			File's FileID (CatalogNodeID)
//		startBlock		Starting file allocation block number
//		allowPrevious	If the desired record isn't found and this flag is set,
//						then see if the previous record belongs to the same fork.
//						If so, then return it.
//
//	Outputs:
//		foundKey	The key data for the record actually found
//		foundData	The extent record actually found (NOTE: on an HFS volume, the
//					fourth entry will be zeroes.
//		foundHint	The BTree hint to find the node again
//_________________________________________________________________________________
static OSErr FindExtentRecord(
	const ExtendedVCB	*vcb,
	u_int8_t			forkType,
	u_int32_t			fileID,
	u_int32_t			startBlock,
	Boolean				allowPrevious,
	HFSPlusExtentKey	*foundKey,
	HFSPlusExtentRecord	foundData,
	u_int32_t			*foundHint)
{
	FCB *				fcb;
	BTreeIterator		btIterator;
	FSBufferDescriptor	btRecord;
	OSErr				err;
	u_int16_t			btRecordSize;
	
	err = noErr;
	if (foundHint)
		*foundHint = 0;
	fcb = GetFileControlBlock(vcb->extentsRefNum);
	
	bzero(&btIterator, sizeof(btIterator));

	if (vcb->vcbSigWord == kHFSSigWord) {
		HFSExtentKey *		extentKeyPtr;
		HFSExtentRecord		extentData;

		extentKeyPtr = (HFSExtentKey*) &btIterator.key;
		extentKeyPtr->keyLength	= kHFSExtentKeyMaximumLength;
		extentKeyPtr->forkType = forkType;
		extentKeyPtr->fileID = fileID;
		extentKeyPtr->startBlock = startBlock;
		
		btRecord.bufferAddress = &extentData;
		btRecord.itemSize = sizeof(HFSExtentRecord);
		btRecord.itemCount = 1;

		err = BTSearchRecord(fcb, &btIterator, &btRecord, &btRecordSize, &btIterator);

		if (err == btNotFound && allowPrevious) {
			err = BTIterateRecord(fcb, kBTreePrevRecord, &btIterator, &btRecord, &btRecordSize);

			//	A previous record may not exist, so just return btNotFound (like we would if
			//	it was for the wrong file/fork).
Commit	Line	Data
1c79356b	1	/*
b0d623f7	2	* Copyright (c) 2000-2008 Apple Inc. All rights reserved.
5d5c5d0d	3	*
2d21ac55	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
1c79356b	5	*
2d21ac55 A	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.
8f6c56a5	14	*
2d21ac55 A	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
8f6c56a5 A	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
8f6c56a5 A	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
2d21ac55 A	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.
8f6c56a5	25	*
2d21ac55	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
1c79356b	27	*/
1c79356b A	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"
1c79356b	36
1c79356b A	37	#include <sys/malloc.h>
	38
	39	/*
	40	============================================================
	41	Public (Exported) Routines:
	42	============================================================
1c79356b A	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
1c79356b	69
1c79356b	70
1c79356b A	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
2d21ac55	100	static const int64_t kTwoGigabytes = 0x80000000LL;
9bccf70c	101
1c79356b A	102	enum
1c79356b A	103	{
1c79356b A	104	kDataForkType = 0,
	105	kResourceForkType = 0xFF,
	106
d52fe63f	107	kPreviousRecord = -1
1c79356b A	108	};
1c79356b A	109
1c79356b	110
55e303ae	111	static OSErr HFSPlusToHFSExtents(
1c79356b A	112	const HFSPlusExtentRecord oldExtents,
	113	HFSExtentRecord newExtents);
	114
55e303ae	115	static OSErr FindExtentRecord(
1c79356b	116	const ExtendedVCB *vcb,
2d21ac55 A	117	u_int8_t forkType,
	118	u_int32_t fileID,
	119	u_int32_t startBlock,
1c79356b A	120	Boolean allowPrevious,
	121	HFSPlusExtentKey *foundKey,
	122	HFSPlusExtentRecord foundData,
2d21ac55	123	u_int32_t *foundHint);
1c79356b	124
55e303ae	125	static OSErr DeleteExtentRecord(
1c79356b	126	const ExtendedVCB *vcb,
2d21ac55 A	127	u_int8_t forkType,
	128	u_int32_t fileID,
	129	u_int32_t startBlock);
1c79356b A	130
1c79356b A	131	static OSErr CreateExtentRecord(
91447636	132	ExtendedVCB *vcb,
1c79356b A	133	HFSPlusExtentKey *key,
1c79356b A	134	HFSPlusExtentRecord extents,
2d21ac55	135	u_int32_t *hint);
1c79356b A	136
1c79356b A	137
55e303ae	138	static OSErr GetFCBExtentRecord(
1c79356b A	139	const FCB *fcb,
	140	HFSPlusExtentRecord extents);
	141
	142	static OSErr SearchExtentFile(
91447636	143	ExtendedVCB *vcb,
1c79356b	144	const FCB *fcb,
2d21ac55	145	int64_t filePosition,
1c79356b A	146	HFSPlusExtentKey *foundExtentKey,
1c79356b A	147	HFSPlusExtentRecord foundExtentData,
2d21ac55 A	148	u_int32_t *foundExtentDataIndex,
	149	u_int32_t *extentBTreeHint,
	150	u_int32_t *endingFABNPlusOne );
1c79356b A	151
1c79356b A	152	static OSErr SearchExtentRecord(
91447636	153	ExtendedVCB *vcb,
2d21ac55	154	u_int32_t searchFABN,
1c79356b	155	const HFSPlusExtentRecord extentData,
2d21ac55 A	156	u_int32_t extentDataStartFABN,
	157	u_int32_t *foundExtentDataOffset,
	158	u_int32_t *endingFABNPlusOne,
1c79356b A	159	Boolean *noMoreExtents);
	160
	161	static OSErr ReleaseExtents(
	162	ExtendedVCB *vcb,
	163	const HFSPlusExtentRecord extentRecord,
2d21ac55	164	u_int32_t *numReleasedAllocationBlocks,
1c79356b A	165	Boolean *releasedLastExtent);
	166
	167	static OSErr DeallocateFork(
	168	ExtendedVCB *vcb,
	169	HFSCatalogNodeID fileID,
2d21ac55	170	u_int8_t forkType,
1c79356b A	171	HFSPlusExtentRecord catalogExtents,
	172	Boolean * recordDeleted);
	173
	174	static OSErr TruncateExtents(
	175	ExtendedVCB *vcb,
2d21ac55 A	176	u_int8_t forkType,
	177	u_int32_t fileID,
	178	u_int32_t startBlock,
1c79356b A	179	Boolean * recordDeleted);
	180
	181	static OSErr UpdateExtentRecord (
91447636	182	ExtendedVCB *vcb,
1c79356b A	183	FCB *fcb,
	184	const HFSPlusExtentKey *extentFileKey,
	185	const HFSPlusExtentRecord extentData,
2d21ac55	186	u_int32_t extentBTreeHint);
1c79356b	187
1c79356b A	188	static Boolean ExtentsAreIntegral(
1c79356b A	189	const HFSPlusExtentRecord extentRecord,
2d21ac55 A	190	u_int32_t mask,
2d21ac55 A	191	u_int32_t *blocksChecked,
1c79356b A	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	//_________________________________________________________________________________
55e303ae	216	static OSErr FindExtentRecord(
1c79356b	217	const ExtendedVCB *vcb,
2d21ac55 A	218	u_int8_t forkType,
	219	u_int32_t fileID,
	220	u_int32_t startBlock,
1c79356b A	221	Boolean allowPrevious,
	222	HFSPlusExtentKey *foundKey,
	223	HFSPlusExtentRecord foundData,
2d21ac55	224	u_int32_t *foundHint)
1c79356b A	225	{
1c79356b A	226	FCB * fcb;
b0d623f7	227	BTreeIterator btIterator;
1c79356b A	228	FSBufferDescriptor btRecord;
1c79356b A	229	OSErr err;
2d21ac55	230	u_int16_t btRecordSize;
1c79356b A	231
1c79356b A	232	err = noErr;
55e303ae A	233	if (foundHint)
55e303ae A	234	*foundHint = 0;
1c79356b A	235	fcb = GetFileControlBlock(vcb->extentsRefNum);
1c79356b A	236
b0d623f7	237	bzero(&btIterator, sizeof(btIterator));
1c79356b A	238
	239	if (vcb->vcbSigWord == kHFSSigWord) {
	240	HFSExtentKey * extentKeyPtr;
	241	HFSExtentRecord extentData;
	242
b0d623f7	243	extentKeyPtr = (HFSExtentKey*) &btIterator.key;
1c79356b A	244	extentKeyPtr->keyLength = kHFSExtentKeyMaximumLength;
	245	extentKeyPtr->forkType = forkType;
	246	extentKeyPtr->fileID = fileID;
	247	extentKeyPtr->startBlock = startBlock;
	248
	249	btRecord.bufferAddress = &extentData;
	250	btRecord.itemSize = sizeof(HFSExtentRecord);
	251	btRecord.itemCount = 1;
	252
b0d623f7	253	err = BTSearchRecord(fcb, &btIterator, &btRecord, &btRecordSize, &btIterator);
1c79356b A	254
1c79356b A	255	if (err == btNotFound && allowPrevious) {
b0d623f7	256	err = BTIterateRecord(fcb, kBTreePrevRecord, &btIterator, &btRecord, &btRecordSize);
1c79356b A	257
	258	// A previous record may not exist, so just return btNotFound (like we would if
	259	// it was for the wrong file/fork).
	260