git.saurik.com Git - apple/hfs.git/blame_incremental - livefiles_hfs_plugin/lf_hfs_btrees

... / ...

Commit	Line	Data
	1	//
	2	// lf_hfs_btrees_internal.h
	3	// livefiles_hfs
	4	//
	5	// Created by Yakov Ben Zaken on 22/03/2018.
	6	//
	7
	8	#ifndef lf_hfs_btrees_internal_h
	9	#define lf_hfs_btrees_internal_h
	10
	11	#include "lf_hfs_file_mgr_internal.h"
	12
	13	enum {
	14	fsBTInvalidHeaderErr = btBadHdr,
	15	fsBTBadRotateErr = dsBadRotate,
	16	fsBTInvalidNodeErr = btBadNode,
	17	fsBTRecordTooLargeErr = btNoFit,
	18	fsBTRecordNotFoundErr = btNotFound,
	19	fsBTDuplicateRecordErr = btExists,
	20	fsBTFullErr = btNoSpaceAvail,
	21
	22	fsBTInvalidFileErr = ERR_BASE + 0x0302, /* no BTreeCB has been allocated for fork*/
	23	fsBTrFileAlreadyOpenErr = ERR_BASE + 0x0303,
	24	fsBTInvalidIteratorErr = ERR_BASE + 0x0308,
	25	fsBTEmptyErr = ERR_BASE + 0x030A,
	26	fsBTNoMoreMapNodesErr = ERR_BASE + 0x030B,
	27	fsBTBadNodeSize = ERR_BASE + 0x030C,
	28	fsBTBadNodeType = ERR_BASE + 0x030D,
	29	fsBTInvalidKeyLengthErr = ERR_BASE + 0x030E,
	30	fsBTStartOfIterationErr = ERR_BASE + 0x0353,
	31	fsBTEndOfIterationErr = ERR_BASE + 0x0354,
	32	fsBTUnknownVersionErr = ERR_BASE + 0x0355,
	33	fsBTTreeTooDeepErr = ERR_BASE + 0x0357,
	34	fsIteratorExitedScopeErr = ERR_BASE + 0x0A02, /* iterator exited the scope*/
	35	fsIteratorScopeExceptionErr = ERR_BASE + 0x0A03, /* iterator is undefined due to error or movement of scope locality*/
	36	fsUnknownIteratorMovementErr = ERR_BASE + 0x0A04, /* iterator movement is not defined*/
	37	fsInvalidIterationMovmentErr = ERR_BASE + 0x0A05, /* iterator movement is invalid in current context*/
	38	fsClientIDMismatchErr = ERR_BASE + 0x0A06, /* wrong client process ID*/
	39	fsEndOfIterationErr = ERR_BASE + 0x0A07, /* there were no objects left to return on iteration*/
	40	fsBTTimeOutErr = ERR_BASE + 0x0A08 /* BTree scan interrupted -- no time left for physical I/O */
	41	};
	42
	43	typedef struct {
	44	void *buffer;
	45	void *blockHeader;
	46	daddr64_t blockNum; /* logical block number (used by hfs_swap_BTNode) */
	47	ByteCount blockSize;
	48	Boolean blockReadFromDisk;
	49	Byte isModified; // XXXdbg - for journaling
	50	Byte reserved[2];
	51
	52	} BlockDescriptor, *BlockDescPtr;
	53
	54
	55	typedef struct {
	56	void * bufferAddress;
	57	ByteCount itemSize;
	58	ItemCount itemCount;
	59
	60	} FSBufferDescriptor, *FSBufferDescriptorPtr;
	61
	62
	63	/*
	64	Fork Level Access Method Block get options
	65	*/
	66	enum {
	67	kGetBlock = 0x00000000,
	68	kGetBlockHint = 0x00000001, // if set, the block is being looked up using hint
	69	kForceReadBlock = 0x00000002, // how does this relate to Read/Verify? Do we need this?
	70	kGetEmptyBlock = 0x00000008
	71	};
	72	typedef u_int32_t GetBlockOptions;
	73
	74	/*
	75	Fork Level Access Method Block release options
	76	*/
	77	enum {
	78	kReleaseBlock = 0x00000000,
	79	kForceWriteBlock = 0x00000001,
	80	kMarkBlockDirty = 0x00000002,
	81	kTrashBlock = 0x00000004,
	82	kLockTransaction = 0x00000100
	83	};
	84	typedef u_int32_t ReleaseBlockOptions;
	85
	86	typedef u_int64_t FSSize;
	87	typedef u_int32_t ForkBlockNumber;
	88
	89	/*============================================================================
	90	Fork Level Buffered I/O Access Method
	91	============================================================================*/
	92
	93	typedef OSStatus (* GetBlockProcPtr) (FileReference fileRefNum,
	94	uint64_t blockNum,
	95	GetBlockOptions options,
	96	BlockDescriptor *block );
	97
	98
	99	typedef OSStatus (* ReleaseBlockProcPtr) (FileReference fileRefNum,
	100	BlockDescPtr blockPtr,
	101	ReleaseBlockOptions options );
	102
	103	typedef OSStatus (* SetEndOfForkProcPtr) (FileReference fileRefNum,
	104	FSSize minEOF,
	105	FSSize maxEOF );
	106
	107	typedef OSStatus (* SetBlockSizeProcPtr) (FileReference fileRefNum,
	108	ByteCount blockSize,
	109	ItemCount minBlockCount );
	110
	111	OSStatus SetEndOfForkProc ( FileReference fileRefNum, FSSize minEOF, FSSize maxEOF );
	112
	113
	114	/*
	115	B*Tree Information Version
	116	*/
	117	enum BTreeInformationVersion{
	118	kBTreeInfoVersion = 0
	119	};
	120
	121	/*
	122	B*Tree Iteration Operation Constants
	123	*/
	124	enum BTreeIterationOperations{
	125	kBTreeFirstRecord,
	126	kBTreeNextRecord,
	127	kBTreePrevRecord,
	128	kBTreeLastRecord,
	129	kBTreeCurrentRecord
	130	};
	131	typedef u_int16_t BTreeIterationOperation;
	132
	133
	134	/*
	135	Btree types: 0 is HFS CAT/EXT file, 1~127 are AppleShare B*Tree files, 128~254 unused
	136	hfsBtreeType EQU 0 ; control file
	137	validBTType EQU $80 ; user btree type starts from 128
	138	userBT1Type EQU $FF ; 255 is our Btree type. Used by BTInit and BTPatch
	139	*/
	140	enum BTreeTypes{
	141	kHFSBTreeType = 0, // control file
	142	kUserBTreeType = 128, // user btree type starts from 128
	143	kReservedBTreeType = 255 //
	144	};
	145
	146	#define kBTreeHeaderUserBytes 128
	147
	148	/* B-tree structures */
	149
	150	enum {
	151	kMaxKeyLength = 520
	152	};
	153
	154	typedef union {
	155	u_int8_t length8;
	156	u_int16_t length16;
	157	u_int8_t rawData [kMaxKeyLength+2];
	158
	159	} BTreeKey, *BTreeKeyPtr;
	160
	161	/* BTNodeDescriptor -- Every B-tree node starts with these fields. */
	162	typedef struct {
	163	u_int32_t fLink; /* next node at this level*/
	164	u_int32_t bLink; /* previous node at this level*/
	165	int8_t kind; /* kind of node (leaf, index, header, map)*/
	166	u_int8_t height; /* zero for header, map; child is one more than parent*/
	167	u_int16_t numRecords; /* number of records in this node*/
	168	u_int16_t reserved; /* reserved - initialized as zero */
	169
	170	} __attribute__((aligned(2), packed)) BTNodeDescriptor;
	171
	172	/* Constants for BTNodeDescriptor kind */
	173	enum {
	174	kBTLeafNode = -1,
	175	kBTIndexNode = 0,
	176	kBTHeaderNode = 1,
	177	kBTMapNode = 2
	178	};
	179
	180	/* BTHeaderRec -- The first record of a B-tree header node */
	181	typedef struct {
	182	u_int16_t treeDepth; /* maximum height (usually leaf nodes) */
	183	u_int32_t rootNode; /* node number of root node */
	184	u_int32_t leafRecords; /* number of leaf records in all leaf nodes */
	185	u_int32_t firstLeafNode; /* node number of first leaf node */
	186	u_int32_t lastLeafNode; /* node number of last leaf node */
	187	u_int16_t nodeSize; /* size of a node, in bytes */
	188	u_int16_t maxKeyLength; /* reserved */
	189	u_int32_t totalNodes; /* total number of nodes in tree */
	190	u_int32_t freeNodes; /* number of unused (free) nodes in tree */
	191	u_int16_t reserved1; /* unused */
	192	u_int32_t clumpSize; /* reserved */
	193	u_int8_t btreeType; /* reserved */
	194	u_int8_t keyCompareType; /* Key string Comparison Type */
	195	u_int32_t attributes; /* persistent attributes about the tree */
	196	u_int32_t reserved3[16]; /* reserved */
	197
	198	} __attribute__((aligned(2), packed)) BTHeaderRec;
	199
	200	/* Constants for BTHeaderRec attributes */
	201	enum {
	202	kBTBadCloseMask = 0x00000001, /* reserved */
	203	kBTBigKeysMask = 0x00000002, /* key length field is 16 bits */
	204	kBTVariableIndexKeysMask = 0x00000004 /* keys in index nodes are variable length */
	205	};
	206
	207	/*
	208	BTreeInfoRec Structure - for BTGetInformation
	209	*/
	210	typedef struct {
	211	u_int16_t version;
	212	u_int16_t nodeSize;
	213	u_int16_t maxKeyLength;
	214	u_int16_t treeDepth;
	215	u_int32_t lastfsync; /* Last time that this was fsynced */
	216	ItemCount numRecords;
	217	ItemCount numNodes;
	218	ItemCount numFreeNodes;
	219	u_int8_t keyCompareType;
	220	u_int8_t reserved[3];
	221	} BTreeInfoRec, *BTreeInfoRecPtr;
	222
	223	/*
	224	BTreeHint can never be exported to the outside. Use u_int32_t BTreeHint[4],
	225	u_int8_t BTreeHint[16], etc.
	226	*/
	227	typedef struct {
	228	ItemCount writeCount;
	229	u_int32_t nodeNum; // node the key was last seen in
	230	u_int16_t index; // index then key was last seen at
	231	u_int16_t reserved1;
	232	u_int32_t reserved2;
	233	} BTreeHint, *BTreeHintPtr;
	234
	235	/*
	236	BTree Iterator
	237	*/
	238	typedef struct {
	239	BTreeHint hint;
	240	u_int16_t version;
	241	u_int16_t reserved;
	242	u_int32_t hitCount; // Total number of leaf records hit
	243	u_int32_t maxLeafRecs; // Max leaf records over iteration
	244	BTreeKey key;
	245	} BTreeIterator, *BTreeIteratorPtr;
	246
	247
	248	/*============================================================================
	249	B*Tree SPI
	250	============================================================================*/
	251
	252	/*
	253	Key Comparison Function ProcPtr Type - for BTOpenPath
	254	*/
	255	//typedef int32_t (* KeyCompareProcPtr)(BTreeKeyPtr a, BTreeKeyPtr b);
	256
	257
	258	typedef int32_t (* IterateCallBackProcPtr)(BTreeKeyPtr key, void * record, void * state);
	259
	260	OSStatus BTOpenPath (FCB *filePtr, KeyCompareProcPtr keyCompareProc);
	261
	262	OSStatus BTClosePath (FCB *filePtr );
	263
	264
	265	OSStatus BTSearchRecord (FCB *filePtr,
	266	BTreeIterator *searchIterator,
	267	FSBufferDescriptor *btRecord,
	268	u_int16_t *recordLen,
	269	BTreeIterator *resultIterator );
	270
	271	OSStatus BTIterateRecord (FCB *filePtr,
	272	BTreeIterationOperation operation,
	273	BTreeIterator *iterator,
	274	FSBufferDescriptor *btRecord,
	275	u_int16_t *recordLen );
	276
	277
	278	OSStatus BTIterateRecords (FCB *filePtr,
	279	BTreeIterationOperation operation,
	280	BTreeIterator *iterator,
	281	IterateCallBackProcPtr callBackProc,
	282	void *callBackState);
	283
	284	OSStatus BTInsertRecord (FCB *filePtr,
	285	BTreeIterator *iterator,
	286	FSBufferDescriptor *btrecord,
	287	u_int16_t recordLen );
	288
	289	OSStatus BTReplaceRecord (FCB *filePtr,
	290	BTreeIterator *iterator,
	291	FSBufferDescriptor *btRecord,
	292	u_int16_t recordLen );
	293
	294	OSStatus BTUpdateRecord (FCB *filePtr,
	295	BTreeIterator *iterator,
	296	IterateCallBackProcPtr callBackProc,
	297	void *callBackState );
	298
	299	OSStatus BTDeleteRecord (FCB *filePtr,
	300	BTreeIterator *iterator );
	301
	302	OSStatus BTGetInformation (FCB *filePtr,
	303	u_int16_t vers,
	304	BTreeInfoRec *info );
	305
	306	OSStatus BTIsDirty (FCB *filePtr);
	307
	308	OSStatus BTFlushPath (FCB *filePtr);
	309
	310	OSStatus BTReloadData (FCB *filePtr);
	311
	312	OSStatus BTInvalidateHint (BTreeIterator *iterator );
	313
	314	OSStatus BTGetLastSync (FCB *filePtr,
	315	u_int32_t *lastfsync );
	316
	317	OSStatus BTSetLastSync (FCB *filePtr,
	318	u_int32_t lastfsync );
	319
	320	OSStatus BTHasContiguousNodes(FCB *filePtr);
	321
	322	OSStatus BTGetUserData(FCB filePtr, void dataPtr, int dataSize);
	323
	324	OSStatus BTSetUserData(FCB filePtr, void dataPtr, int dataSize);
	325
	326	/* B-tree node reserve routines. */
	327	void BTReserveSetup(void);
	328
	329	int BTReserveSpace(FCB file, int operations, void data);
	330
	331	int BTReleaseReserve(FCB file, void data);
	332
	333	int BTZeroUnusedNodes(FCB *file);
	334
	335
	336	#endif /* lf_hfs_btrees_internal_h */