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

/*
 * Copyright (c) 2000-2014 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>
#include <sys/vnode_internal.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.

	SearchExtentFile
					Search the FCB and extents file for an extent record that
					contains a given file position (in bytes).


============================================================
Internal Routines:
============================================================
	FindExtentRecord
					Search the extents BTree for a particular extent record.
	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.
*/

#if CONFIG_HFS_STD
static const int64_t kTwoGigabytes = 0x80000000LL;
#endif

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


#if CONFIG_HFS_STD
static OSErr HFSPlusToHFSExtents(
	const HFSPlusExtentRecord	oldExtents,
	HFSExtentRecord				newExtents);
#endif

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 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,
	int				deleted,
	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;
	struct BTreeIterator *btIterator = NULL;
	FSBufferDescriptor	btRecord;
	OSErr				err;
	u_int16_t			btRecordSize;
	
	err = noErr;
	if (foundHint)
		*foundHint = 0;
	fcb = GetFileControlBlock(vcb->extentsRefNum);

	MALLOC (btIterator, struct BTreeIterator*, sizeof(struct BTreeIterator), M_TEMP, M_WAITOK);
	if (btIterator == NULL) {
		return memFullErr;  // translates to ENOMEM
	}
	bzero(btIterator, sizeof(*btIterator));

	/* HFS Plus / HFSX */
	if (vcb->vcbSigWord != kHFSSigWord) {
		HFSPlusExtentKey *	extentKeyPtr;
		HFSPlusExtentRecord	extentData;

		extentKeyPtr = (HFSPlusExtentKey*) &btIterator->key;
		extentKeyPtr->keyLength	 = kHFSPlusExtentKeyMaximumLength;
		extentKeyPtr->forkType	 = forkType;
		extentKeyPtr->pad		 = 0;
		extentKeyPtr->fileID	 = fileID;
		extentKeyPtr->startBlock = startBlock;
		
		btRecord.bufferAddress = &extentData;
		btRecord.itemSize = sizeof(HFSPlusExtentRecord);
		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	/*
3e170ce0	2	* Copyright (c) 2000-2014 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	37	#include <sys/malloc.h>
3e170ce0	38	#include <sys/vnode_internal.h>
1c79356b A	39
	40	/*
	41	============================================================
	42	Public (Exported) Routines:
	43	============================================================
1c79356b A	44
	45	ExtendFileC Allocate more space to a given file.
	46
	47	CompareExtentKeys
	48	Compare two extents file keys (a search key and a trial
	49	key). Used by the BTree manager when searching for,
	50	adding, or deleting keys in the extents file of an HFS
	51	volume.
	52
	53	CompareExtentKeysPlus
	54	Compare two extents file keys (a search key and a trial
	55	key). Used by the BTree manager when searching for,
	56	adding, or deleting keys in the extents file of an HFS+
	57	volume.
	58
	59	MapFileBlockC Convert (map) an offset within a given file into a
	60	physical disk address.
	61
	62	TruncateFileC Truncates the disk space allocated to a file. The file
	63	space is truncated to a specified new physical EOF, rounded
	64	up to the next allocation block boundry. There is an option
	65	to truncate to the end of the extent containing the new EOF.
	66
	67	FlushExtentFile
	68	Flush the extents file for a given volume.
	69
3e170ce0 A	70	SearchExtentFile
	71	Search the FCB and extents file for an extent record that
	72	contains a given file position (in bytes).
1c79356b	73
1c79356b A	74
	75	============================================================
	76	Internal Routines:
	77	============================================================
	78	FindExtentRecord
	79	Search the extents BTree for a particular extent record.
1c79356b A	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
fe8ab488	100	#if CONFIG_HFS_STD
2d21ac55	101	static const int64_t kTwoGigabytes = 0x80000000LL;
fe8ab488	102	#endif
9bccf70c	103
1c79356b A	104	enum
1c79356b A	105	{
1c79356b A	106	kDataForkType = 0,
	107	kResourceForkType = 0xFF,
	108
d52fe63f	109	kPreviousRecord = -1
1c79356b A	110	};
1c79356b A	111
1c79356b	112
39236c6e	113	#if CONFIG_HFS_STD
55e303ae	114	static OSErr HFSPlusToHFSExtents(
1c79356b A	115	const HFSPlusExtentRecord oldExtents,
1c79356b A	116	HFSExtentRecord newExtents);
39236c6e	117	#endif
1c79356b	118
55e303ae	119	static OSErr FindExtentRecord(
1c79356b	120	const ExtendedVCB *vcb,
2d21ac55 A	121	u_int8_t forkType,
	122	u_int32_t fileID,
	123	u_int32_t startBlock,
1c79356b A	124	Boolean allowPrevious,
	125	HFSPlusExtentKey *foundKey,
	126	HFSPlusExtentRecord foundData,
2d21ac55	127	u_int32_t *foundHint);
1c79356b	128
55e303ae	129	static OSErr DeleteExtentRecord(
1c79356b	130	const ExtendedVCB *vcb,
2d21ac55 A	131	u_int8_t forkType,
	132	u_int32_t fileID,
	133	u_int32_t startBlock);
1c79356b A	134
1c79356b A	135	static OSErr CreateExtentRecord(
91447636	136	ExtendedVCB *vcb,
1c79356b A	137	HFSPlusExtentKey *key,
1c79356b A	138	HFSPlusExtentRecord extents,
2d21ac55	139	u_int32_t *hint);
1c79356b A	140
1c79356b A	141
55e303ae	142	static OSErr GetFCBExtentRecord(
1c79356b A	143	const FCB *fcb,
	144	HFSPlusExtentRecord extents);
	145
1c79356b	146	static OSErr SearchExtentRecord(
91447636	147	ExtendedVCB *vcb,
2d21ac55	148	u_int32_t searchFABN,
1c79356b	149	const HFSPlusExtentRecord extentData,
2d21ac55 A	150	u_int32_t extentDataStartFABN,
	151	u_int32_t *foundExtentDataOffset,
	152	u_int32_t *endingFABNPlusOne,
1c79356b A	153	Boolean *noMoreExtents);
	154
	155	static OSErr ReleaseExtents(
	156	ExtendedVCB *vcb,
	157	const HFSPlusExtentRecord extentRecord,
2d21ac55	158	u_int32_t *numReleasedAllocationBlocks,
1c79356b A	159	Boolean *releasedLastExtent);
	160
	161	static OSErr DeallocateFork(
	162	ExtendedVCB *vcb,
	163	HFSCatalogNodeID fileID,
2d21ac55	164	u_int8_t forkType,
1c79356b A	165	HFSPlusExtentRecord catalogExtents,
	166	Boolean * recordDeleted);
	167
	168	static OSErr TruncateExtents(
	169	ExtendedVCB *vcb,
2d21ac55 A	170	u_int8_t forkType,
	171	u_int32_t fileID,
	172	u_int32_t startBlock,
1c79356b A	173	Boolean * recordDeleted);
	174
	175	static OSErr UpdateExtentRecord (
91447636	176	ExtendedVCB *vcb,
6d2010ae A	177	FCB *fcb,
6d2010ae A	178	int deleted,
1c79356b A	179	const HFSPlusExtentKey *extentFileKey,
1c79356b A	180	const HFSPlusExtentRecord extentData,
2d21ac55	181	u_int32_t extentBTreeHint);
1c79356b	182
1c79356b A	183	static Boolean ExtentsAreIntegral(
1c79356b A	184	const HFSPlusExtentRecord extentRecord,
2d21ac55 A	185	u_int32_t mask,
2d21ac55 A	186	u_int32_t *blocksChecked,
1c79356b A	187	Boolean *checkedLastExtent);
	188
	189	//_________________________________________________________________________________
	190	//
	191	// Routine: FindExtentRecord
	192	//
	193	// Purpose: Search the extents BTree for an extent record matching the given
	194	// FileID, fork, and starting file allocation block number.
	195	//
	196	// Inputs:
	197	// vcb Volume to search
	198	// forkType 0 = data fork, -1 = resource fork
	199	// fileID File's FileID (CatalogNodeID)
	200	// startBlock Starting file allocation block number
	201	// allowPrevious If the desired record isn't found and this flag is set,
	202	// then see if the previous record belongs to the same fork.
	203	// If so, then return it.
	204	//
	205	// Outputs:
	206	// foundKey The key data for the record actually found
	207	// foundData The extent record actually found (NOTE: on an HFS volume, the
	208	// fourth entry will be zeroes.
	209	// foundHint The BTree hint to find the node again
	210	//_________________________________________________________________________________
55e303ae	211	static OSErr FindExtentRecord(
1c79356b	212	const ExtendedVCB *vcb,
2d21ac55 A	213	u_int8_t forkType,
	214	u_int32_t fileID,
	215	u_int32_t startBlock,
1c79356b A	216	Boolean allowPrevious,
	217	HFSPlusExtentKey *foundKey,
	218	HFSPlusExtentRecord foundData,
2d21ac55	219	u_int32_t *foundHint)
1c79356b A	220	{
1c79356b A	221	FCB * fcb;
316670eb	222	struct BTreeIterator *btIterator = NULL;
1c79356b A	223	FSBufferDescriptor btRecord;
1c79356b A	224	OSErr err;
2d21ac55	225	u_int16_t btRecordSize;
1c79356b A	226
1c79356b A	227	err = noErr;
55e303ae A	228	if (foundHint)
55e303ae A	229	*foundHint = 0;
1c79356b	230	fcb = GetFileControlBlock(vcb->extentsRefNum);
316670eb A	231
	232	MALLOC (btIterator, struct BTreeIterator*, sizeof(struct BTreeIterator), M_TEMP, M_WAITOK);
	233	if (btIterator == NULL) {
	234	return memFullErr; // translates to ENOMEM
	235	}
	236	bzero(btIterator, sizeof(*btIterator));
1c79356b	237
39236c6e A	238	/* HFS Plus / HFSX */
	239	if (vcb->vcbSigWord != kHFSSigWord) {
	240	HFSPlusExtentKey * extentKeyPtr;
	241	HFSPlusExtentRecord extentData;
1c79356b	242
39236c6e A	243	extentKeyPtr = (HFSPlusExtentKey*) &btIterator->key;
	244	extentKeyPtr->keyLength = kHFSPlusExtentKeyMaximumLength;
	245	extentKeyPtr->forkType = forkType;
	246	extentKeyPtr->pad = 0;
	247	extentKeyPtr->fileID = fileID;
1c79356b A	248	extentKeyPtr->startBlock = startBlock;
	249
	250	btRecord.bufferAddress = &extentData;
39236c6e	251	btRecord.itemSize = sizeof(HFSPlusExtentRecord);
1c79356b A	252	btRecord.itemCount = 1;
1c79356b A	253
316670eb	254	err = BTSearchRecord(fcb, btIterator, &btRecord, &btRecordSize, btIterator);
1c79356b A	255
1c79356b A	256	if (err == btNotFound && allowPrevious) {
316670eb	257	err = BTIterateRecord(fcb, kBTreePrevRecord, btIterator, &btRecord, &btRecordSize);
1c79356b A	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