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

1 //

2 // lf_hfs_btree.h

3 // livefiles_hfs

4 //

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

6 //

8 #ifndef lf_hfs_btree_h

9 #define lf_hfs_btree_h

12 #include "lf_hfs_file_mgr_internal.h"

13 #include "lf_hfs_btrees_internal.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 BTreeControlBlock { // 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 } BTreeControlBlock, *BTreeControlBlockPtr;

116

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

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

119

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

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

122

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

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

144

145 typedef struct {

146 u_int32_t node; // node number

147 u_int16_t index;

148 u_int16_t reserved; // align size to a power of 2

149 } TreePathRecord, *TreePathRecordPtr;

150

151 typedef TreePathRecord TreePathTable [kMaxTreeDepth];

152

153

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

155

156 struct InsertKey {

157 BTreeKeyPtr keyPtr;

158 u_int8_t * recPtr;

159 u_int16_t keyLength;

160 u_int16_t recSize;

161 Boolean replacingKey;

162 Boolean skipRotate;

163 };

164

165 typedef struct InsertKey InsertKey;

166

167

168 //// For Notational Convenience

169

170 typedef BTNodeDescriptor* NodeDescPtr;

171 typedef u_int8_t *RecordPtr;

172 typedef BTreeKeyPtr KeyPtr;

173

174

175 //////////////////////////////////// Globals ////////////////////////////////////

176

177

178 //////////////////////////////////// Macros /////////////////////////////////////

179 // Exit function on error

180 #define M_ExitOnError( result ) do { if ( ( result ) != noErr ) goto ErrorExit; } while(0)

181

182 // Test for passed condition and return if true

183 #define M_ReturnErrorIf( condition, error ) do { if ( condition ) return( error ); } while(0)

184

185 //////////////////////////////// Key Operations /////////////////////////////////

186

187 int32_t CompareKeys (BTreeControlBlockPtr btreePtr,

188 KeyPtr searchKey,

189 KeyPtr trialKey );

190

191 //////////////////////////////// Map Operations /////////////////////////////////

192

193 OSStatus AllocateNode (BTreeControlBlockPtr btreePtr,

194 u_int32_t *nodeNum);

195

196 OSStatus FreeNode (BTreeControlBlockPtr btreePtr,

197 u_int32_t nodeNum);

198

199 OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr,

200 u_int32_t nodes );

201

202 u_int32_t CalcMapBits (BTreeControlBlockPtr btreePtr);

203

204

205 void BTUpdateReserve (BTreeControlBlockPtr btreePtr,

206 int nodes);

207

208 //////////////////////////////// Misc Operations ////////////////////////////////

209

210 u_int16_t CalcKeyRecordSize (u_int16_t keySize,

211 u_int16_t recSize );

212

213 OSStatus VerifyHeader (FCB *filePtr,

214 BTHeaderRec *header );

215

216 OSStatus UpdateHeader (BTreeControlBlockPtr btreePtr,

217 Boolean forceWrite );

218

219 OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,

220 BTreeIteratorPtr iterator,

221 BlockDescriptor *left,

222 BlockDescriptor *middle,

223 BlockDescriptor *right,

224 u_int32_t *nodeNum,

225 u_int16_t *index,

226 Boolean *foundRecord );

227

228 OSStatus CheckInsertParams (FCB *filePtr,

229 BTreeIterator *iterator,

230 FSBufferDescriptor *record,

231 u_int16_t recordLen );

232

233 OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,

234 NodeDescPtr nodePtr,

235 BTreeIterator *iterator,

236 FSBufferDescriptor *record,

237 u_int16_t recordLen,

238 Boolean *recordInserted );

239

240 OSStatus IsItAHint (BTreeControlBlockPtr btreePtr,

241 BTreeIterator *iterator,

242 Boolean *answer );

243

244 extern OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr);

245

246 //////////////////////////////// Node Operations ////////////////////////////////

247

248 //// Node Operations

249

250 OSStatus GetNode (BTreeControlBlockPtr btreePtr,

251 u_int32_t nodeNum,

252 u_int32_t flags,

253 NodeRec *returnNodePtr );

254

255 /* Flags for GetNode() */

256 #define kGetNodeHint 0x1 /* If set, the node is being looked up using a hint */

257

258 OSStatus GetLeftSiblingNode (BTreeControlBlockPtr btreePtr,

259 NodeDescPtr node,

260 NodeRec *left );

261

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

263

264 OSStatus GetRightSiblingNode (BTreeControlBlockPtr btreePtr,

265 NodeDescPtr node,

266 NodeRec *right );

267

268 #define GetRightSiblingNode(btree,node,right) GetNode ((btree), ((NodeDescPtr)(node))->fLink, 0, (right))

269

270

271 OSStatus GetNewNode (BTreeControlBlockPtr btreePtr,

272 u_int32_t nodeNum,

273 NodeRec *returnNodePtr );

274

275 OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr,

276 NodePtr nodePtr );

277

278 OSStatus TrashNode (BTreeControlBlockPtr btreePtr,

279 NodePtr nodePtr );

280

281 OSStatus UpdateNode (BTreeControlBlockPtr btreePtr,

282 NodePtr nodePtr,

283 u_int32_t transactionID,

284 u_int32_t flags );

285

286 //// Node Buffer Operations

287

288 void ClearNode (BTreeControlBlockPtr btreePtr,

289 NodeDescPtr node );

290

291 u_int16_t GetNodeDataSize (BTreeControlBlockPtr btreePtr,

292 NodeDescPtr node );

293

294 u_int16_t GetNodeFreeSize (BTreeControlBlockPtr btreePtr,

295 NodeDescPtr node );

296

297

298 //// Record Operations

299

300 Boolean InsertRecord (BTreeControlBlockPtr btreePtr,

301 NodeDescPtr node,

302 u_int16_t index,

303 RecordPtr recPtr,

304 u_int16_t recSize );

305

306 Boolean InsertKeyRecord (BTreeControlBlockPtr btreePtr,

307 NodeDescPtr node,

308 u_int16_t index,

309 KeyPtr keyPtr,

310 u_int16_t keyLength,

311 RecordPtr recPtr,

312 u_int16_t recSize );

313

314 void DeleteRecord (BTreeControlBlockPtr btree,

315 NodeDescPtr node,

316 u_int16_t index );

317

318

319 Boolean SearchNode (BTreeControlBlockPtr btree,

320 NodeDescPtr node,

321 KeyPtr searchKey,

322 u_int16_t *index );

323

324 OSStatus GetRecordByIndex (BTreeControlBlockPtr btree,

325 NodeDescPtr node,

326 u_int16_t index,

327 KeyPtr *keyPtr,

328 u_int8_t * *dataPtr,

329 u_int16_t *dataSize );

330

331 u_int8_t * GetRecordAddress (BTreeControlBlockPtr btree,

332 NodeDescPtr node,

333 u_int16_t index );

334

335 #define GetRecordAddress(btreePtr,node,index) ((u_int8_t *)(node) + (*(short *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)))

336

337

338 u_int16_t GetRecordSize (BTreeControlBlockPtr btree,

339 NodeDescPtr node,

340 u_int16_t index );

341

342 u_int32_t GetChildNodeNum (BTreeControlBlockPtr btreePtr,

343 NodeDescPtr nodePtr,

344 u_int16_t index );

345

 void        MoveRecordsLeft            (u_int8_t *                 src,

347 u_int8_t * dst,

348 u_int16_t bytesToMove );

349

350 #define MoveRecordsLeft(src,dst,bytes) bcopy((src),(dst),(bytes))

351

 void        MoveRecordsRight        (u_int8_t *                 src,

353 u_int8_t * dst,

354 u_int16_t bytesToMove );

355

356 #define MoveRecordsRight(src,dst,bytes) bcopy((src),(dst),(bytes))

357

358

359 //////////////////////////////// Tree Operations ////////////////////////////////

360

361 OSStatus SearchTree (BTreeControlBlockPtr btreePtr,

362 BTreeKeyPtr keyPtr,

363 TreePathTable treePathTable,

364 u_int32_t *nodeNum,

365 BlockDescriptor *nodePtr,

366 u_int16_t *index );

367

368 OSStatus InsertTree (BTreeControlBlockPtr btreePtr,

369 TreePathTable treePathTable,

370 KeyPtr keyPtr,

371 u_int8_t * recPtr,

372 u_int16_t recSize,

373 BlockDescriptor *targetNode,

374 u_int16_t index,

375 u_int16_t level,

376 Boolean replacingKey,

377 u_int32_t *insertNode );

378

379 OSStatus DeleteTree (BTreeControlBlockPtr btreePtr,

380 TreePathTable treePathTable,

381 BlockDescriptor *targetNode,

382 u_int16_t index,

383 u_int16_t level );

384

385 OSStatus BTFlushPath (FCB *filePtr);

386

387 OSStatus BTSetLastSync (FCB *filePtr,

388 u_int32_t lastsync);

389 #endif /* lf_hfs_btree_h */