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

1 //

2 // lf_hfs_btrees_private.h

3 // livefiles_hfs

4 //

5 // Created by Yakov Ben Zaken on 22/03/2018.

6 //

8 #ifndef lf_hfs_btrees_private_h

9 #define lf_hfs_btrees_private_h

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"

16 /////////////////////////////////// Constants ///////////////////////////////////

18 #define kBTreeVersion 1

19 #define kMaxTreeDepth 16

22 #define kHeaderNodeNum 0

23 #define kKeyDescRecord 1

26 // Header Node Record Offsets

27 enum {

28 kHeaderRecOffset = 0x000E,

29 kKeyDescRecOffset = 0x0078,

30 kHeaderMapRecOffset = 0x00F8

31 };

33 #define kMinNodeSize (512)

35 #define kMinRecordSize (6)

36 // where is minimum record size enforced?

38 // miscellaneous BTree constants

39 enum {

40 kOffsetSize = 2

41 };

43 // Insert Operations

44 typedef enum {

45 kInsertRecord = 0,

46 kReplaceRecord = 1

47 } InsertType;

49 // illegal string attribute bits set in mask

50 #define kBadStrAttribMask (0xCF)

54 //////////////////////////////////// Macros /////////////////////////////////////

56 #define M_NodesInMap(mapSize) ((mapSize) << 3)

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)

63 #define M_MapRecordSize(nodeSize) (nodeSize - sizeof (BTNodeDescriptor) - 6)

64 #define M_HeaderMapRecordSize(nodeSize) (nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8)

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)))

69 ///////////////////////////////////// Types /////////////////////////////////////

71 typedef struct { // fields specific to BTree CBs

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;

87 u_int16_t reserved3; // 4-byte alignment

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 */

96 GetBlockProcPtr getBlockProc;

97 ReleaseBlockProcPtr releaseBlockProc;

98 SetEndOfForkProcPtr setEndOfForkProc;

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

     void                        *madeDirtyBy[2];

114 #endif

115

116 } BTreeControlBlock, *BTreeControlBlockPtr;

117

 u_int32_t CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key);

119 #define CalcKeySize(btcb, key) ( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) )

120

 u_int32_t KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key);

122 #define KeyLength(btcb, key) ( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 )

123

124

125 typedef enum {

126 kBTHeaderDirty = 0x00000001

127 } BTreeFlags;

128

 static inline void M_BTreeHeaderDirty(BTreeControlBlock *bt) {

130 #if DEBUG

     bt->madeDirtyBy[0] = __builtin_return_address(0);

     bt->madeDirtyBy[1] = __builtin_return_address(1);

133 #endif

134 bt->flags |= kBTHeaderDirty;

135 }

136

137 typedef int8_t *NodeBuffer;

138 typedef BlockDescriptor NodeRec, *NodePtr; //remove this someday...

139

140

141 //// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree

142

143 typedef 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

150 typedef TreePathRecord TreePathTable [kMaxTreeDepth];

151

152

153 //// InsertKey - used by InsertTree, InsertLevel and InsertNode

154

155 typedef 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

166 typedef BTNodeDescriptor* NodeDescPtr;

167 typedef u_int8_t *RecordPtr;

168 typedef 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

183 int32_t CompareKeys (BTreeControlBlockPtr btreePtr,

184 KeyPtr searchKey,

185 KeyPtr trialKey );

186

187 //////////////////////////////// Map Operations /////////////////////////////////

188

189 OSStatus AllocateNode (BTreeControlBlockPtr btreePtr,

190 u_int32_t *nodeNum);

191

192 OSStatus FreeNode (BTreeControlBlockPtr btreePtr,

193 u_int32_t nodeNum);

194

195 OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr,

196 u_int32_t nodes );

197

198 u_int32_t CalcMapBits (BTreeControlBlockPtr btreePtr);

199

200

201 void BTUpdateReserve (BTreeControlBlockPtr btreePtr,

202 int nodes);

203

204 //////////////////////////////// Misc Operations ////////////////////////////////

205

206 u_int16_t CalcKeyRecordSize (u_int16_t keySize,

207 u_int16_t recSize );

208

209 OSStatus VerifyHeader (FCB *filePtr,

210 BTHeaderRec *header );

211

212 OSStatus UpdateHeader (BTreeControlBlockPtr btreePtr,

213 Boolean forceWrite );

214

215 OSStatus 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

224 OSStatus CheckInsertParams (FCB *filePtr,

225 BTreeIterator *iterator,

226 FSBufferDescriptor *record,

227 u_int16_t recordLen );

228

229 OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,

230 NodeDescPtr nodePtr,

231 BTreeIterator *iterator,

232 FSBufferDescriptor *record,

233 u_int16_t recordLen,

234 Boolean *recordInserted );

235

236 OSStatus IsItAHint (BTreeControlBlockPtr btreePtr,

237 BTreeIterator *iterator,

238 Boolean *answer );

239

240 OSStatus TreeIsDirty (BTreeControlBlockPtr btreePtr);

241

242 //////////////////////////////// Node Operations ////////////////////////////////

243

244 //// Node Operations

245

246 OSStatus 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

254 OSStatus GetLeftSiblingNode (BTreeControlBlockPtr btreePtr,

255 NodeDescPtr node,

256 NodeRec *left );

257

258 #define GetLeftSiblingNode(btree,node,left) GetNode ((btree), ((NodeDescPtr)(node))->bLink, 0, (left))

259

260 OSStatus 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

267 OSStatus GetNewNode (BTreeControlBlockPtr btreePtr,

268 u_int32_t nodeNum,

269 NodeRec *returnNodePtr );

270

271 OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr,

272 NodePtr nodePtr );

273

274 OSStatus TrashNode (BTreeControlBlockPtr btreePtr,

275 NodePtr nodePtr );

276

277 OSStatus UpdateNode (BTreeControlBlockPtr btreePtr,

278 NodePtr nodePtr,

279 u_int32_t transactionID,

280 u_int32_t flags );

281

282 //// Node Buffer Operations

283

284 void ClearNode (BTreeControlBlockPtr btreePtr,

285 NodeDescPtr node );

286

287 u_int16_t GetNodeDataSize (BTreeControlBlockPtr btreePtr,

288 NodeDescPtr node );

289

290 u_int16_t GetNodeFreeSize (BTreeControlBlockPtr btreePtr,

291 NodeDescPtr node );

292

293

294 //// Record Operations

295

296 Boolean InsertRecord (BTreeControlBlockPtr btreePtr,

297 NodeDescPtr node,

298 u_int16_t index,

299 RecordPtr recPtr,

300 u_int16_t recSize );

301

302 Boolean 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

310 void DeleteRecord (BTreeControlBlockPtr btree,

311 NodeDescPtr node,

312 u_int16_t index );

313

314

315 Boolean SearchNode (BTreeControlBlockPtr btree,

316 NodeDescPtr node,

317 KeyPtr searchKey,

318 u_int16_t *index );

319

320 OSStatus 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

327 u_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

334 u_int16_t GetRecordSize (BTreeControlBlockPtr btree,

335 NodeDescPtr node,

336 u_int16_t index );

337

338 u_int32_t GetChildNodeNum (BTreeControlBlockPtr btreePtr,

339 NodeDescPtr nodePtr,

340 u_int16_t index );

341

 void        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

 void        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

357 OSStatus SearchTree (BTreeControlBlockPtr btreePtr,

358 BTreeKeyPtr keyPtr,

359 TreePathTable treePathTable,

360 u_int32_t *nodeNum,

361 BlockDescriptor *nodePtr,

362 u_int16_t *index );

363

364 OSStatus 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

375 OSStatus 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 */