]> git.saurik.com Git - apple/hfs.git/blame - livefiles_hfs_plugin/lf_hfs_btrees_private.h
projects / apple / hfs.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
hfs-522.100.5.tar.gz
[apple/hfs.git] / livefiles_hfs_plugin / lf_hfs_btrees_private.h
CommitLineData
de8ee011
A		 1//
2// lf_hfs_btrees_private.h
3// livefiles_hfs
4//
5// Created by Yakov Ben Zaken on 22/03/2018.
6//
7
8#ifndef lf_hfs_btrees_private_h
9#define lf_hfs_btrees_private_h
10
11#include "lf_hfs_defs.h"
12#include "lf_hfs_file_mgr_internal.h"
13#include "lf_hfs_btrees_internal.h"
14#include "lf_hfs_logger.h"
15
16/////////////////////////////////// Constants ///////////////////////////////////
17
18#define kBTreeVersion 1
19#define kMaxTreeDepth 16
20
21
22#define kHeaderNodeNum 0
23#define kKeyDescRecord 1
24
25
26// Header Node Record Offsets
27enum {
28 kHeaderRecOffset = 0x000E,
29 kKeyDescRecOffset = 0x0078,
30 kHeaderMapRecOffset = 0x00F8
31};
32
33#define kMinNodeSize (512)
34
35#define kMinRecordSize (6)
36// where is minimum record size enforced?
37
38// miscellaneous BTree constants
39enum {
40 kOffsetSize = 2
41};
42
43// Insert Operations
44typedef enum {
45 kInsertRecord = 0,
46 kReplaceRecord = 1
47} InsertType;
48
49// illegal string attribute bits set in mask
50#define kBadStrAttribMask (0xCF)
51
52
53
54//////////////////////////////////// Macros /////////////////////////////////////
55
56#define M_NodesInMap(mapSize) ((mapSize) << 3)
57
58#define M_ClearBitNum(integer,bitNumber) ((integer) &= (~(1<<(bitNumber))))
59#define M_SetBitNum(integer,bitNumber) ((integer) |= (1<<(bitNumber)))
60#define M_IsOdd(integer) (((integer) & 1) != 0)
61#define M_IsEven(integer) (((integer) & 1) == 0)
62
63#define M_MapRecordSize(nodeSize) (nodeSize - sizeof (BTNodeDescriptor) - 6)
64#define M_HeaderMapRecordSize(nodeSize) (nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8)
65
66#define M_SWAP_BE16_ClearBitNum(integer,bitNumber) ((integer) &= SWAP_BE16(~(1<<(bitNumber))))
67#define M_SWAP_BE16_SetBitNum(integer,bitNumber) ((integer) |= SWAP_BE16(1<<(bitNumber)))
68
69///////////////////////////////////// Types /////////////////////////////////////
70
71typedef struct { // fields specific to BTree CBs
72
73 u_int8_t keyCompareType; /* Key string Comparison Type */
74 u_int8_t btreeType;
75 u_int16_t treeDepth;
76 FileReference fileRefNum; // refNum of btree file
77 KeyCompareProcPtr keyCompareProc;
78 u_int32_t rootNode;
79 u_int32_t leafRecords;
80 u_int32_t firstLeafNode;
81 u_int32_t lastLeafNode;
82 u_int16_t nodeSize;
83 u_int16_t maxKeyLength;
84 u_int32_t totalNodes;
85 u_int32_t freeNodes;
86
87 u_int16_t reserved3; // 4-byte alignment
88
89 // new fields
90 int16_t version;
91 u_int32_t flags; // dynamic flags
92 u_int32_t attributes; // persistent flags
93 u_int32_t writeCount;
94 u_int32_t lastfsync; /* Last time that this was fsynced */
95
96 GetBlockProcPtr getBlockProc;
97 ReleaseBlockProcPtr releaseBlockProc;
98 SetEndOfForkProcPtr setEndOfForkProc;
99
100 // statistical information
101 u_int32_t numGetNodes;
102 u_int32_t numGetNewNodes;
103 u_int32_t numReleaseNodes;
104 u_int32_t numUpdateNodes;
105 u_int32_t numMapNodesRead; // map nodes beyond header node
106 u_int32_t numHintChecks;
107 u_int32_t numPossibleHints; // Looks like a formated hint
108 u_int32_t numValidHints; // Hint used to find correct record.
109 u_int32_t reservedNodes;
110 BTreeIterator iterator; // useable when holding exclusive b-tree lock
111
112#if DEBUG
113 void *madeDirtyBy[2];
114#endif
115
116} BTreeControlBlock, *BTreeControlBlockPtr;
117
118u_int32_t CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key);
119#define CalcKeySize(btcb, key) ( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) )
120
121u_int32_t KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key);
122#define KeyLength(btcb, key) ( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 )
123
124
125typedef enum {
126 kBTHeaderDirty = 0x00000001
127} BTreeFlags;
128
129static inline void M_BTreeHeaderDirty(BTreeControlBlock *bt) {
130#if DEBUG
131 bt->madeDirtyBy[0] = __builtin_return_address(0);
132 bt->madeDirtyBy[1] = __builtin_return_address(1);
133#endif
134 bt->flags |= kBTHeaderDirty;
135}
136
137typedef int8_t *NodeBuffer;
138typedef BlockDescriptor NodeRec, *NodePtr; //remove this someday...
139
140
141//// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree
142
143typedef struct {
144 u_int32_t node; // node number
145 u_int16_t index;
146 u_int16_t reserved; // align size to a power of 2
147
148} TreePathRecord, *TreePathRecordPtr;
149
150typedef TreePathRecord TreePathTable [kMaxTreeDepth];
151
152
153//// InsertKey - used by InsertTree, InsertLevel and InsertNode
154
155typedef struct {
156 BTreeKeyPtr keyPtr;
157 u_int8_t * recPtr;
158 u_int16_t keyLength;
159 u_int16_t recSize;
160 Boolean replacingKey;
161 Boolean skipRotate;
162} InsertKey;
163
164//// For Notational Convenience
165
166typedef BTNodeDescriptor* NodeDescPtr;
167typedef u_int8_t *RecordPtr;
168typedef BTreeKeyPtr KeyPtr;
169
170
171//////////////////////////////////// Globals ////////////////////////////////////
172
173
174//////////////////////////////////// Macros /////////////////////////////////////
175// Exit function on error
176#define M_ExitOnError( result ) do { if ( ( result ) != noErr ) goto ErrorExit; } while(0)
177
178// Test for passed condition and return if true
179#define M_ReturnErrorIf( condition, error ) do { if ( condition ) return( error ); } while(0)
180
181//////////////////////////////// Key Operations /////////////////////////////////
182
183int32_t CompareKeys (BTreeControlBlockPtr btreePtr,
184 KeyPtr searchKey,
185 KeyPtr trialKey );
186
187//////////////////////////////// Map Operations /////////////////////////////////
188
189OSStatus AllocateNode (BTreeControlBlockPtr btreePtr,
190 u_int32_t *nodeNum);
191
192OSStatus FreeNode (BTreeControlBlockPtr btreePtr,
193 u_int32_t nodeNum);
194
195OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr,
196 u_int32_t nodes );
197
198u_int32_t CalcMapBits (BTreeControlBlockPtr btreePtr);
199
200
201void BTUpdateReserve (BTreeControlBlockPtr btreePtr,
202 int nodes);
203
204//////////////////////////////// Misc Operations ////////////////////////////////
205
206u_int16_t CalcKeyRecordSize (u_int16_t keySize,
207 u_int16_t recSize );
208
209OSStatus VerifyHeader (FCB *filePtr,
210 BTHeaderRec *header );
211
212OSStatus UpdateHeader (BTreeControlBlockPtr btreePtr,
213 Boolean forceWrite );
214
215OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
216 BTreeIteratorPtr iterator,
217 BlockDescriptor *left,
218 BlockDescriptor *middle,
219 BlockDescriptor *right,
220 u_int32_t *nodeNum,
221 u_int16_t *index,
222 Boolean *foundRecord );
223
224OSStatus CheckInsertParams (FCB *filePtr,
225 BTreeIterator *iterator,
226 FSBufferDescriptor *record,
227 u_int16_t recordLen );
228
229OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
230 NodeDescPtr nodePtr,
231 BTreeIterator *iterator,
232 FSBufferDescriptor *record,
233 u_int16_t recordLen,
234 Boolean *recordInserted );
235
236OSStatus IsItAHint (BTreeControlBlockPtr btreePtr,
237 BTreeIterator *iterator,
238 Boolean *answer );
239
240OSStatus TreeIsDirty (BTreeControlBlockPtr btreePtr);
241
242//////////////////////////////// Node Operations ////////////////////////////////
243
244//// Node Operations
245
246OSStatus GetNode (BTreeControlBlockPtr btreePtr,
247 u_int32_t nodeNum,
248 u_int32_t flags,
249 NodeRec *returnNodePtr );
250
251/* Flags for GetNode() */
252#define kGetNodeHint 0x1 /* If set, the node is being looked up using a hint */
253
254OSStatus GetLeftSiblingNode (BTreeControlBlockPtr btreePtr,
255 NodeDescPtr node,
256 NodeRec *left );
257
258#define GetLeftSiblingNode(btree,node,left) GetNode ((btree), ((NodeDescPtr)(node))->bLink, 0, (left))
259
260OSStatus GetRightSiblingNode (BTreeControlBlockPtr btreePtr,
261 NodeDescPtr node,
262 NodeRec *right );
263
264#define GetRightSiblingNode(btree,node,right) GetNode ((btree), ((NodeDescPtr)(node))->fLink, 0, (right))
265
266
267OSStatus GetNewNode (BTreeControlBlockPtr btreePtr,
268 u_int32_t nodeNum,
269 NodeRec *returnNodePtr );
270
271OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr,
272 NodePtr nodePtr );
273
274OSStatus TrashNode (BTreeControlBlockPtr btreePtr,
275 NodePtr nodePtr );
276
277OSStatus UpdateNode (BTreeControlBlockPtr btreePtr,
278 NodePtr nodePtr,
279 u_int32_t transactionID,
280 u_int32_t flags );
281
282//// Node Buffer Operations
283
284void ClearNode (BTreeControlBlockPtr btreePtr,
285 NodeDescPtr node );
286
287u_int16_t GetNodeDataSize (BTreeControlBlockPtr btreePtr,
288 NodeDescPtr node );
289
290u_int16_t GetNodeFreeSize (BTreeControlBlockPtr btreePtr,
291 NodeDescPtr node );
292
293
294//// Record Operations
295
296Boolean InsertRecord (BTreeControlBlockPtr btreePtr,
297 NodeDescPtr node,
298 u_int16_t index,
299 RecordPtr recPtr,
300 u_int16_t recSize );
301
302Boolean InsertKeyRecord (BTreeControlBlockPtr btreePtr,
303 NodeDescPtr node,
304 u_int16_t index,
305 KeyPtr keyPtr,
306 u_int16_t keyLength,
307 RecordPtr recPtr,
308 u_int16_t recSize );
309
310void DeleteRecord (BTreeControlBlockPtr btree,
311 NodeDescPtr node,
312 u_int16_t index );
313
314
315Boolean SearchNode (BTreeControlBlockPtr btree,
316 NodeDescPtr node,
317 KeyPtr searchKey,
318 u_int16_t *index );
319
320OSStatus GetRecordByIndex (BTreeControlBlockPtr btree,
321 NodeDescPtr node,
322 u_int16_t index,
323 KeyPtr *keyPtr,
324 u_int8_t * *dataPtr,
325 u_int16_t *dataSize );
326
327u_int8_t * GetRecordAddress (BTreeControlBlockPtr btree,
328 NodeDescPtr node,
329 u_int16_t index );
330
331#define GetRecordAddress(btreePtr,node,index) ((u_int8_t *)(node) + (*(short *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)))
332
333
334u_int16_t GetRecordSize (BTreeControlBlockPtr btree,
335 NodeDescPtr node,
336 u_int16_t index );
337
338u_int32_t GetChildNodeNum (BTreeControlBlockPtr btreePtr,
339 NodeDescPtr nodePtr,
340 u_int16_t index );
341
342void MoveRecordsLeft (u_int8_t * src,
343 u_int8_t * dst,
344 u_int16_t bytesToMove );
345
346#define MoveRecordsLeft(src,dst,bytes) bcopy((src),(dst),(bytes))
347
348void MoveRecordsRight (u_int8_t * src,
349 u_int8_t * dst,
350 u_int16_t bytesToMove );
351
352#define MoveRecordsRight(src,dst,bytes) bcopy((src),(dst),(bytes))
353
354
355//////////////////////////////// Tree Operations ////////////////////////////////
356
357OSStatus SearchTree (BTreeControlBlockPtr btreePtr,
358 BTreeKeyPtr keyPtr,
359 TreePathTable treePathTable,
360 u_int32_t *nodeNum,
361 BlockDescriptor *nodePtr,
362 u_int16_t *index );
363
364OSStatus InsertTree (BTreeControlBlockPtr btreePtr,
365 TreePathTable treePathTable,
366 KeyPtr keyPtr,
367 u_int8_t * recPtr,
368 u_int16_t recSize,
369 BlockDescriptor *targetNode,
370 u_int16_t index,
371 u_int16_t level,
372 Boolean replacingKey,
373 u_int32_t *insertNode );
374
375OSStatus DeleteTree (BTreeControlBlockPtr btreePtr,
376 TreePathTable treePathTable,
377 BlockDescriptor *targetNode,
378 u_int16_t index,
379 u_int16_t level );
380
381
382#endif /* lf_hfs_btrees_private_h */
mirror of hfs