1 /*
2 * Copyright 2020, Shubham Bhagat, shubhambhagat111@yahoo.com
3 * All rights reserved. Distributed under the terms of the MIT License.
4 */
5
6
7 #include "BPlusTree.h"
8
9 #include "VerifyHeader.h"
10
11
TreeDirectory(Inode * inode)12 TreeDirectory::TreeDirectory(Inode* inode)
13 :
14 fInode(inode),
15 fInitStatus(B_OK),
16 fRoot(NULL),
17 fExtents(NULL),
18 fCountOfFilledExtents(0),
19 fSingleDirBlock(NULL),
20 fOffsetOfSingleDirBlock(-1),
21 fCurMapIndex(0),
22 fOffset(0),
23 fCurBlockNumber(0)
24 {
25 fRoot = new(std::nothrow) BlockInDataFork;
26 if (fRoot == NULL) {
27 fInitStatus = B_NO_MEMORY;
28 return;
29 }
30
31 fSingleDirBlock = new(std::nothrow) char[fInode->DirBlockSize()];
32 if (fSingleDirBlock == NULL) {
33 fInitStatus = B_NO_MEMORY;
34 return;
35 }
36
37 memcpy((void*)fRoot,
38 DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize()), sizeof(BlockInDataFork));
39
40 for (int i = 0; i < MAX_TREE_DEPTH; i++) {
41 fPathForLeaves[i].blockData = NULL;
42 fPathForData[i].blockData = NULL;
43 }
44 }
45
46
~TreeDirectory()47 TreeDirectory::~TreeDirectory()
48 {
49 delete fRoot;
50 delete[] fExtents;
51 delete[] fSingleDirBlock;
52 }
53
54
55 status_t
InitCheck()56 TreeDirectory::InitCheck()
57 {
58 return fInitStatus;
59 }
60
61
62 uint32
BlockLen()63 TreeDirectory::BlockLen()
64 {
65 return fInode->SizeOfLongBlock();
66 }
67
68
69 size_t
KeySize()70 TreeDirectory::KeySize()
71 {
72 return XFS_KEY_SIZE;
73 }
74
75
76 size_t
PtrSize()77 TreeDirectory::PtrSize()
78 {
79 return XFS_PTR_SIZE;
80 }
81
82
83 size_t
MaxRecordsPossibleRoot()84 TreeDirectory::MaxRecordsPossibleRoot()
85 {
86 size_t lengthOfDataFork = 0;
87 if (fInode->ForkOffset() != 0)
88 lengthOfDataFork = fInode->ForkOffset() << 3;
89 if (fInode->ForkOffset() == 0) {
90 lengthOfDataFork = fInode->GetVolume()->InodeSize()
91 - fInode->CoreInodeSize();
92 }
93
94 lengthOfDataFork -= sizeof(BlockInDataFork);
95 return lengthOfDataFork / (KeySize() + PtrSize());
96 }
97
98
99 size_t
GetPtrOffsetIntoRoot(int pos)100 TreeDirectory::GetPtrOffsetIntoRoot(int pos)
101 {
102 size_t maxRecords = MaxRecordsPossibleRoot();
103 return sizeof(BlockInDataFork) + maxRecords * KeySize()
104 + (pos - 1) * PtrSize();
105 }
106
107
108 size_t
MaxRecordsPossibleNode()109 TreeDirectory::MaxRecordsPossibleNode()
110 {
111 size_t availableSpace = fInode->GetVolume()->BlockSize() - BlockLen();
112 return availableSpace / (KeySize() + PtrSize());
113 }
114
115
116 size_t
GetPtrOffsetIntoNode(int pos)117 TreeDirectory::GetPtrOffsetIntoNode(int pos)
118 {
119 size_t maxRecords = MaxRecordsPossibleNode();
120 return BlockLen() + maxRecords * KeySize() + (pos - 1) * PtrSize();
121 }
122
123
124 TreePointer*
GetPtrFromRoot(int pos)125 TreeDirectory::GetPtrFromRoot(int pos)
126 {
127 return (TreePointer*)
128 ((char*)DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize())
129 + GetPtrOffsetIntoRoot(pos));
130 }
131
132
133 TreePointer*
GetPtrFromNode(int pos,void * buffer)134 TreeDirectory::GetPtrFromNode(int pos, void* buffer)
135 {
136 size_t offsetIntoNode = GetPtrOffsetIntoNode(pos);
137 return (TreePointer*)((char*)buffer + offsetIntoNode);
138 }
139
140
141 TreeKey*
GetKeyFromNode(int pos,void * buffer)142 TreeDirectory::GetKeyFromNode(int pos, void* buffer)
143 {
144 return (TreeKey*)
145 ((char*)buffer + BlockLen() + (pos - 1) * KeySize());
146 }
147
148
149 TreeKey*
GetKeyFromRoot(int pos)150 TreeDirectory::GetKeyFromRoot(int pos)
151 {
152 off_t offset = (pos - 1) * KeySize();
153 char* base = (char*)DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize())
154 + sizeof(BlockInDataFork);
155 return (TreeKey*) (base + offset);
156 }
157
158
159 status_t
SearchOffsetInTreeNode(uint32 offset,TreePointer ** pointer,int pathIndex)160 TreeDirectory::SearchOffsetInTreeNode(uint32 offset,
161 TreePointer** pointer, int pathIndex)
162 {
163 // This is O(MaxRecords). Next is to implement this using upper bound
164 // binary search and get O(log(MaxRecords))
165 *pointer = NULL;
166 TreeKey* offsetKey = NULL;
167 size_t maxRecords = MaxRecordsPossibleNode();
168 for (int i = maxRecords - 1; i >= 0; i--) {
169 offsetKey
170 = GetKeyFromNode(i + 1, (void*)fPathForLeaves[pathIndex].blockData);
171 if (B_BENDIAN_TO_HOST_INT64(*offsetKey) <= offset) {
172 *pointer = GetPtrFromNode(i + 1, (void*)
173 fPathForLeaves[pathIndex].blockData);
174
175 break;
176 }
177 }
178
179 if (offsetKey == NULL || *pointer == NULL)
180 return B_BAD_VALUE;
181
182 return B_OK;
183 }
184
185
186 status_t
SearchAndFillPath(uint32 offset,int type)187 TreeDirectory::SearchAndFillPath(uint32 offset, int type)
188 {
189 TRACE("SearchAndFillPath:\n");
190 PathNode* path;
191 if (type == DATA)
192 path = fPathForData;
193 else if (type == LEAF)
194 path = fPathForLeaves;
195 else
196 return B_BAD_VALUE;
197
198 TreePointer* ptrToNode = NULL;
199 TreeKey* offsetKey = NULL;
200 // Go down the root of the tree first
201 for (int i = fRoot->NumRecords() - 1; i >= 0; i--) {
202 offsetKey = GetKeyFromRoot(i + 1);
203 if (B_BENDIAN_TO_HOST_INT64(*offsetKey) <= offset) {
204 ptrToNode = GetPtrFromRoot(i + 1);
205 break;
206 }
207 }
208 if (ptrToNode == NULL || offsetKey == NULL) {
209 //Corrupt tree
210 return B_BAD_VALUE;
211 }
212
213 // We now have gone down the root and save path if not saved.
214 int level = fRoot->Levels() - 1;
215 Volume* volume = fInode->GetVolume();
216 status_t status;
217 for (int i = 0; i < MAX_TREE_DEPTH && level >= 0; i++, level--) {
218 uint64 requiredBlock = B_BENDIAN_TO_HOST_INT64(*ptrToNode);
219 TRACE("requiredBlock:(%" B_PRIu64 ")\n", requiredBlock);
220 if (path[i].blockNumber == requiredBlock) {
221 // This block already has what we need
222 if (path[i].type == 2)
223 break;
224 status = SearchOffsetInTreeNode(offset, &ptrToNode, i);
225 if (status != B_OK)
226 return status;
227 continue;
228 }
229 // We do not have the block we need
230 ssize_t len;
231 if (level == 0) {
232 // The size of buffer should be the directory block size
233 len = fInode->DirBlockSize();
234 TRACE("path node type:(%" B_PRId32 ")\n", path[i].type);
235 if (path[i].type != 2) {
236 // Size is not directory block size.
237 delete path[i].blockData;
238 path[i].type = 0;
239 path[i].blockData = new(std::nothrow) char[len];
240 if (path[i].blockData == NULL)
241 return B_NO_MEMORY;
242 path[i].type = 2;
243 }
244 uint64 readPos = fInode->FileSystemBlockToAddr(requiredBlock);
245 if (read_pos(volume->Device(), readPos, path[i].blockData, len)
246 != len) {
247 ERROR("FillPath::FillBlockBuffer(): IO Error");
248 return B_IO_ERROR;
249 }
250 path[i].blockNumber = requiredBlock;
251 break;
252 }
253 // The size of buffer should be the block size
254 len = volume->BlockSize();
255 if (path[i].type != 1) {
256 delete path[i].blockData;
257 path[i].type = 0;
258 path[i].blockData = new(std::nothrow) char[len];
259 if (path[i].blockData == NULL)
260 return B_NO_MEMORY;
261 path[i].type = 1;
262 }
263 uint64 readPos = fInode->FileSystemBlockToAddr(requiredBlock);
264 if (read_pos(volume->Device(), readPos, path[i].blockData, len)
265 != len) {
266 ERROR("FillPath::FillBlockBuffer(): IO Error");
267 return B_IO_ERROR;
268 }
269 path[i].blockNumber = requiredBlock;
270 status = SearchOffsetInTreeNode(offset, &ptrToNode, i);
271 if (status != B_OK)
272 return status;
273 }
274
275 return B_OK;
276 }
277
278
279 status_t
GetAllExtents()280 TreeDirectory::GetAllExtents()
281 {
282 xfs_extnum_t noOfExtents = fInode->DataExtentsCount();
283
284 ExtentMapUnwrap* extentsWrapped
285 = new(std::nothrow) ExtentMapUnwrap[noOfExtents];
286 if (extentsWrapped == NULL)
287 return B_NO_MEMORY;
288
289 ArrayDeleter<ExtentMapUnwrap> extentsWrappedDeleter(extentsWrapped);
290
291 Volume* volume = fInode->GetVolume();
292 ssize_t len = volume->BlockSize();
293
294 uint16 levelsInTree = fRoot->Levels();
295 status_t status = fInode->GetNodefromTree(levelsInTree, volume, len,
296 fInode->DirBlockSize(), fSingleDirBlock);
297 if (status != B_OK)
298 return status;
299
300 // We should be at the left most leaf node.
301 // This could be a multilevel node type directory
302 uint64 fileSystemBlockNo;
303 while (1) {
304 // Run till you have leaf blocks to checkout
305 char* leafBuffer = fSingleDirBlock;
306 if (!VerifyHeader<LongBlock>((LongBlock*)leafBuffer, leafBuffer, fInode,
307 0, NULL, XFS_BTREE)) {
308 TRACE("Invalid Long Block");
309 return B_BAD_VALUE;
310 }
311
312 uint32 offset = fInode->SizeOfLongBlock();
313 int numRecs = ((LongBlock*)leafBuffer)->NumRecs();
314
315 for (int i = 0; i < numRecs; i++) {
316 extentsWrapped[fCountOfFilledExtents].first =
317 *(uint64*)(leafBuffer + offset);
318 extentsWrapped[fCountOfFilledExtents].second =
319 *(uint64*)(leafBuffer + offset + sizeof(uint64));
320 offset += sizeof(ExtentMapUnwrap);
321 fCountOfFilledExtents++;
322 }
323
324 fileSystemBlockNo = ((LongBlock*)leafBuffer)->Right();
325 TRACE("Next leaf is at: (%" B_PRIu64 ")\n", fileSystemBlockNo);
326 if (fileSystemBlockNo == (uint64) -1)
327 break;
328 uint64 readPos = fInode->FileSystemBlockToAddr(fileSystemBlockNo);
329 if (read_pos(volume->Device(), readPos, fSingleDirBlock, len)
330 != len) {
331 ERROR("Extent::FillBlockBuffer(): IO Error");
332 return B_IO_ERROR;
333 }
334 }
335 TRACE("Total covered: (%" B_PRIu32 ")\n", fCountOfFilledExtents);
336
337 status = UnWrapExtents(extentsWrapped);
338
339 return status;
340 }
341
342
343 status_t
FillBuffer(char * blockBuffer,int howManyBlocksFurther,ExtentMapEntry * targetMap)344 TreeDirectory::FillBuffer(char* blockBuffer, int howManyBlocksFurther,
345 ExtentMapEntry* targetMap)
346 {
347 TRACE("FILLBUFFER\n");
348 ExtentMapEntry map;
349 if (targetMap == NULL)
350 map = fExtents[fCurMapIndex];
351 if (targetMap != NULL)
352 map = *targetMap;
353
354 if (map.br_state != 0)
355 return B_BAD_VALUE;
356
357 ssize_t len = fInode->DirBlockSize();
358 if (blockBuffer == NULL) {
359 blockBuffer = new(std::nothrow) char[len];
360 if (blockBuffer == NULL)
361 return B_NO_MEMORY;
362 }
363
364 xfs_daddr_t readPos = fInode->FileSystemBlockToAddr(
365 map.br_startblock + howManyBlocksFurther);
366
367 if (read_pos(fInode->GetVolume()->Device(), readPos, blockBuffer, len)
368 != len) {
369 ERROR("TreeDirectory::FillBlockBuffer(): IO Error");
370 return B_IO_ERROR;
371 }
372
373 if (targetMap == NULL) {
374 fSingleDirBlock = blockBuffer;
375 ExtentDataHeader* header = ExtentDataHeader::Create(fInode, fSingleDirBlock);
376 if (header == NULL)
377 return B_NO_MEMORY;
378 if (!VerifyHeader<ExtentDataHeader>(header, fSingleDirBlock, fInode,
379 howManyBlocksFurther, &map, XFS_BTREE)) {
380 ERROR("Invalid Data block");
381 delete header;
382 return B_BAD_VALUE;
383 }
384 delete header;
385 }
386 if (targetMap != NULL) {
387 fSingleDirBlock = blockBuffer;
388 /*
389 This could be leaf or node block perform check for both
390 based on magic number found.
391 */
392 ExtentLeafHeader* leaf = ExtentLeafHeader::Create(fInode, fSingleDirBlock);
393 if (leaf == NULL)
394 return B_NO_MEMORY;
395
396 if ((leaf->Magic() == XFS_DIR2_LEAFN_MAGIC
397 || leaf->Magic() == XFS_DIR3_LEAFN_MAGIC)
398 && !VerifyHeader<ExtentLeafHeader>(leaf, fSingleDirBlock, fInode,
399 howManyBlocksFurther, &map, XFS_BTREE)) {
400 TRACE("Leaf block invalid");
401 delete leaf;
402 return B_BAD_VALUE;
403 }
404 delete leaf;
405 leaf = NULL;
406
407 NodeHeader* node = NodeHeader::Create(fInode, fSingleDirBlock);
408 if (node == NULL)
409 return B_NO_MEMORY;
410
411 if ((node->Magic() == XFS_DA_NODE_MAGIC
412 || node->Magic() == XFS_DA3_NODE_MAGIC)
413 && !VerifyHeader<NodeHeader>(node, fSingleDirBlock, fInode,
414 howManyBlocksFurther, &map, XFS_BTREE)) {
415 TRACE("Node block invalid");
416 delete node;
417 return B_BAD_VALUE;
418 }
419 delete node;
420 }
421 return B_OK;
422 }
423
424
425 int
EntrySize(int len) const426 TreeDirectory::EntrySize(int len) const
427 {
428 int entrySize = sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16);
429 // uint16 is for the tag
430 if (fInode->HasFileTypeField())
431 entrySize += sizeof(uint8);
432
433 return ROUNDUP(entrySize, 8);
434 // rounding off to next greatest multiple of 8
435 }
436
437
438 /*
439 * Throw in the desired block number and get the index of it
440 */
441 status_t
SearchMapInAllExtent(uint64 blockNo,uint32 & mapIndex)442 TreeDirectory::SearchMapInAllExtent(uint64 blockNo, uint32& mapIndex)
443 {
444 ExtentMapEntry map;
445 for (uint32 i = 0; i < fCountOfFilledExtents; i++) {
446 map = fExtents[i];
447 if (map.br_startoff <= blockNo
448 && (blockNo <= map.br_startoff + map.br_blockcount - 1)) {
449 // Map found
450 mapIndex = i;
451 return B_OK;
452 }
453 }
454
455 return B_ENTRY_NOT_FOUND;
456 }
457
458
459 status_t
GetNext(char * name,size_t * length,xfs_ino_t * ino)460 TreeDirectory::GetNext(char* name, size_t* length, xfs_ino_t* ino)
461 {
462 TRACE("TreeDirectory::GetNext\n");
463 status_t status;
464 if (fExtents == NULL) {
465 status = GetAllExtents();
466 if (status != B_OK)
467 return status;
468 }
469 status = FillBuffer(fSingleDirBlock, 0);
470 if (status != B_OK)
471 return status;
472
473 Volume* volume = fInode->GetVolume();
474
475 void* entry; // This could be unused entry so we should check
476 entry = (void*)(fSingleDirBlock + ExtentDataHeader::Size(fInode));
477
478 uint32 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume);
479 if (fOffset != 0 && blockNoFromAddress == fCurBlockNumber) {
480 entry = (void*)(fSingleDirBlock
481 + BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode));
482 // This gets us a little faster to the next entry
483 }
484
485 uint32 curDirectorySize = fInode->Size();
486 ExtentMapEntry& map = fExtents[fCurMapIndex];
487 while (fOffset != curDirectorySize) {
488 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume);
489
490 TRACE("fOffset:(%" B_PRIu64 "), blockNoFromAddress:(%" B_PRIu32 ")\n",
491 fOffset, blockNoFromAddress);
492 if (fCurBlockNumber != blockNoFromAddress
493 && blockNoFromAddress > map.br_startoff
494 && blockNoFromAddress
495 <= map.br_startoff + map.br_blockcount - 1) {
496 // When the block is mapped in the same data
497 // map entry but is not the first block
498 status = FillBuffer(fSingleDirBlock,
499 blockNoFromAddress - map.br_startoff);
500 if (status != B_OK)
501 return status;
502 entry = (void*)(fSingleDirBlock + ExtentDataHeader::Size(fInode));
503 fOffset = fOffset + ExtentDataHeader::Size(fInode);
504 fCurBlockNumber = blockNoFromAddress;
505 } else if (fCurBlockNumber != blockNoFromAddress) {
506 // When the block isn't mapped in the current data map entry
507 uint32 curMapIndex;
508 status = SearchMapInAllExtent(blockNoFromAddress, curMapIndex);
509 if (status != B_OK)
510 return status;
511 fCurMapIndex = curMapIndex;
512 map = fExtents[fCurMapIndex];
513 status = FillBuffer(fSingleDirBlock,
514 blockNoFromAddress - map.br_startoff);
515 if (status != B_OK)
516 return status;
517 entry = (void*)(fSingleDirBlock + ExtentDataHeader::Size(fInode));
518 fOffset = fOffset + ExtentDataHeader::Size(fInode);
519 fCurBlockNumber = blockNoFromAddress;
520 }
521
522 ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry;
523
524 if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) {
525 TRACE("Unused entry found\n");
526 fOffset = fOffset + B_BENDIAN_TO_HOST_INT16(unusedEntry->length);
527 entry = (void*)
528 ((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length));
529 continue;
530 }
531 ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry;
532
533 uint16 currentOffset = (char*)dataEntry - fSingleDirBlock;
534 TRACE("GetNext: fOffset:(%" B_PRIu64 "), currentOffset:(%" B_PRIu16 ")\n",
535 BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode), currentOffset);
536
537 if (BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode) > currentOffset) {
538 entry = (void*)((char*)entry + EntrySize(dataEntry->namelen));
539 continue;
540 }
541
542 if ((size_t)(dataEntry->namelen) >= *length)
543 return B_BUFFER_OVERFLOW;
544
545 fOffset = fOffset + EntrySize(dataEntry->namelen);
546 memcpy(name, dataEntry->name, dataEntry->namelen);
547 name[dataEntry->namelen] = '\0';
548 *length = dataEntry->namelen + 1;
549 *ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber);
550
551 TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "), ino: (%" B_PRIu64 ")\n", name,
552 *length, *ino);
553 return B_OK;
554 }
555
556 return B_ENTRY_NOT_FOUND;
557 }
558
559
560 status_t
UnWrapExtents(ExtentMapUnwrap * extentsWrapped)561 TreeDirectory::UnWrapExtents(ExtentMapUnwrap* extentsWrapped)
562 {
563 fExtents = new(std::nothrow) ExtentMapEntry[fCountOfFilledExtents];
564 if (fExtents == NULL)
565 return B_NO_MEMORY;
566 uint64 first, second;
567
568 for (uint32 i = 0; i < fCountOfFilledExtents; i++) {
569 first = B_BENDIAN_TO_HOST_INT64(extentsWrapped[i].first);
570 second = B_BENDIAN_TO_HOST_INT64(extentsWrapped[i].second);
571 fExtents[i].br_state = first >> 63;
572 fExtents[i].br_startoff = (first & MASK(63)) >> 9;
573 fExtents[i].br_startblock = ((first & MASK(9)) << 43) | (second >> 21);
574 fExtents[i].br_blockcount = second & MASK(21);
575 }
576
577 return B_OK;
578 }
579
580
581 void
FillMapEntry(int num,ExtentMapEntry ** fMap,int type,int pathIndex)582 TreeDirectory::FillMapEntry(int num, ExtentMapEntry** fMap,
583 int type, int pathIndex)
584 {
585 void* pointerToMap;
586 if (type == DATA) {
587 char* base = fPathForData[pathIndex].blockData + BlockLen();
588 off_t offset = num * EXTENT_SIZE;
589 pointerToMap = (void*)(base + offset);
590 } else {
591 char* base = fPathForLeaves[pathIndex].blockData + BlockLen();
592 off_t offset = num * EXTENT_SIZE;
593 pointerToMap = (void*)(base + offset);
594 }
595 uint64 firstHalf = *((uint64*)pointerToMap);
596 uint64 secondHalf = *((uint64*)pointerToMap + 1);
597 //dividing the 128 bits into 2 parts.
598
599 firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf);
600 secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf);
601 (*fMap)->br_state = firstHalf >> 63;
602 (*fMap)->br_startoff = (firstHalf & MASK(63)) >> 9;
603 (*fMap)->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21);
604 (*fMap)->br_blockcount = secondHalf & MASK(21);
605 TRACE("FillMapEntry: startoff:(%" B_PRIu64 "), startblock:(%" B_PRIu64 "),"
606 "blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\n", (*fMap)->br_startoff,
607 (*fMap)->br_startblock,(*fMap)->br_blockcount, (*fMap)->br_state);
608 }
609
610
611 void
SearchForMapInDirectoryBlock(uint64 blockNo,int entries,ExtentMapEntry ** map,int type,int pathIndex)612 TreeDirectory::SearchForMapInDirectoryBlock(uint64 blockNo,
613 int entries, ExtentMapEntry** map, int type, int pathIndex)
614 {
615 TRACE("SearchForMapInDirectoryBlock: blockNo:(%" B_PRIu64 ")\n", blockNo);
616 for (int i = 0; i < entries; i++) {
617 FillMapEntry(i, map, type, pathIndex);
618 if ((*map)->br_startoff <= blockNo
619 && (blockNo <= (*map)->br_startoff + (*map)->br_blockcount - 1)) {
620 // Map found
621 return;
622 }
623 }
624 // Map wasn't found. Some kind of corruption. This is checked by caller.
625 *map = NULL;
626 }
627
628
629 uint32
SearchForHashInNodeBlock(uint32 hashVal)630 TreeDirectory::SearchForHashInNodeBlock(uint32 hashVal)
631 {
632 NodeHeader* header = NodeHeader::Create(fInode, fSingleDirBlock);
633 if (header == NULL)
634 return B_NO_MEMORY;
635 NodeEntry* entry = (NodeEntry*)(fSingleDirBlock + NodeHeader::Size(fInode));
636 int count = header->Count();
637 delete header;
638
639 for (int i = 0; i < count; i++) {
640 if (hashVal <= B_BENDIAN_TO_HOST_INT32(entry[i].hashval))
641 return B_BENDIAN_TO_HOST_INT32(entry[i].before);
642 }
643 return 0;
644 }
645
646
647 status_t
Lookup(const char * name,size_t length,xfs_ino_t * ino)648 TreeDirectory::Lookup(const char* name, size_t length, xfs_ino_t* ino)
649 {
650 TRACE("TreeDirectory: Lookup\n");
651 TRACE("Name: %s\n", name);
652 uint32 hashValueOfRequest = hashfunction(name, length);
653 TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest);
654
655 Volume* volume = fInode->GetVolume();
656 status_t status;
657
658 ExtentMapEntry* targetMap = new(std::nothrow) ExtentMapEntry;
659 if (targetMap == NULL)
660 return B_NO_MEMORY;
661 int pathIndex = -1;
662 uint32 rightOffset = LEAF_STARTOFFSET(volume->BlockLog());
663
664 // In node directories, the "node blocks" had a single level
665 // Here we could have multiple levels. With each iteration of
666 // the loop we go a level lower.
667 while (rightOffset != fOffsetOfSingleDirBlock && 1) {
668 status = SearchAndFillPath(rightOffset, LEAF);
669 if (status != B_OK)
670 return status;
671
672 // The path should now have the Tree Leaf at appropriate level
673 // Find the directory block in the path
674 for (int i = 0; i < MAX_TREE_DEPTH; i++) {
675 if (fPathForLeaves[i].type == 2) {
676 pathIndex = i;
677 break;
678 }
679 }
680 if (pathIndex == -1) {
681 // corrupt tree
682 return B_BAD_VALUE;
683 }
684
685 // Get the node block from directory block
686 // If level is non-zero, reiterate with new "rightOffset"
687 // Else, we are at leaf block, then break
688 LongBlock* curDirBlock
689 = (LongBlock*)fPathForLeaves[pathIndex].blockData;
690
691 if (!VerifyHeader<LongBlock>(curDirBlock, fPathForLeaves[pathIndex].blockData, fInode,
692 0, NULL, XFS_BTREE)) {
693 TRACE("Invalid Long Block");
694 return B_BAD_VALUE;
695 }
696
697 SearchForMapInDirectoryBlock(rightOffset, curDirBlock->NumRecs(),
698 &targetMap, LEAF, pathIndex);
699 if (targetMap == NULL)
700 return B_BAD_VALUE;
701
702 FillBuffer(fSingleDirBlock, rightOffset - targetMap->br_startoff,
703 targetMap);
704 fOffsetOfSingleDirBlock = rightOffset;
705 ExtentLeafHeader* dirBlock = ExtentLeafHeader::Create(fInode, fSingleDirBlock);
706 if (dirBlock == NULL)
707 return B_NO_MEMORY;
708 if (dirBlock->Magic() == XFS_DIR2_LEAFN_MAGIC
709 || dirBlock->Magic() == XFS_DIR3_LEAFN_MAGIC) {
710 // Got the potential leaf. Break.
711 delete dirBlock;
712 break;
713 }
714 if (dirBlock->Magic() == XFS_DA_NODE_MAGIC
715 || dirBlock->Magic() == XFS_DA3_NODE_MAGIC) {
716 rightOffset = SearchForHashInNodeBlock(hashValueOfRequest);
717 if (rightOffset == 0)
718 return B_ENTRY_NOT_FOUND;
719 delete dirBlock;
720 continue;
721 }
722 }
723 // We now have the leaf block that might contain the entry we need.
724 // Else go to the right subling if it might contain it. Else break.
725 while (1) {
726 ExtentLeafHeader* leafHeader
727 = ExtentLeafHeader::Create(fInode, fSingleDirBlock);
728 if (leafHeader == NULL)
729 return B_NO_MEMORY;
730 ExtentLeafEntry* leafEntry
731 = (ExtentLeafEntry*)(fSingleDirBlock + ExtentLeafHeader::Size(fInode));
732
733 int numberOfLeafEntries = leafHeader->Count();
734 TRACE("numberOfLeafEntries:(%" B_PRId32 ")\n", numberOfLeafEntries);
735 int left = 0;
736 int right = numberOfLeafEntries - 1;
737
738 hashLowerBound<ExtentLeafEntry>(leafEntry, left, right, hashValueOfRequest);
739
740 uint32 nextLeaf = leafHeader->Forw();
741 uint32 lastHashVal = B_BENDIAN_TO_HOST_INT32(
742 leafEntry[numberOfLeafEntries - 1].hashval);
743
744 while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval)
745 == hashValueOfRequest) {
746 uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address);
747 if (address == 0) {
748 left++;
749 continue;
750 }
751
752 uint32 dataBlockNumber = BLOCKNO_FROM_ADDRESS(address * 8, volume);
753 uint32 offset = BLOCKOFFSET_FROM_ADDRESS(address * 8, fInode);
754
755 TRACE("BlockNumber:(%" B_PRIu32 "), offset:(%" B_PRIu32 ")\n", dataBlockNumber, offset);
756
757 status = SearchAndFillPath(dataBlockNumber, DATA);
758 int pathIndex = -1;
759 for (int i = 0; i < MAX_TREE_DEPTH; i++) {
760 if (fPathForData[i].type == 2) {
761 pathIndex = i;
762 break;
763 }
764 }
765 if (pathIndex == -1)
766 return B_BAD_VALUE;
767
768 LongBlock* curDirBlock
769 = (LongBlock*)fPathForData[pathIndex].blockData;
770
771 SearchForMapInDirectoryBlock(dataBlockNumber,
772 curDirBlock->NumRecs(), &targetMap, DATA, pathIndex);
773 if (targetMap == NULL)
774 return B_BAD_VALUE;
775
776 FillBuffer(fSingleDirBlock,
777 dataBlockNumber - targetMap->br_startoff, targetMap);
778 fOffsetOfSingleDirBlock = dataBlockNumber;
779
780 TRACE("offset:(%" B_PRIu32 ")\n", offset);
781 ExtentDataEntry* entry
782 = (ExtentDataEntry*)(fSingleDirBlock + offset);
783
784 int retVal = strncmp(name, (char*)entry->name, entry->namelen);
785 if (retVal == 0) {
786 *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber);
787 TRACE("ino:(%" B_PRIu64 ")\n", *ino);
788 return B_OK;
789 }
790 left++;
791 }
792 if (lastHashVal == hashValueOfRequest && nextLeaf != (uint32) -1) {
793 // Go to forward neighbor. We might find an entry there.
794 status = SearchAndFillPath(nextLeaf, LEAF);
795 if (status != B_OK)
796 return status;
797
798 pathIndex = -1;
799 for (int i = 0; i < MAX_TREE_DEPTH; i++) {
800 if (fPathForLeaves[i].type == 2) {
801 pathIndex = i;
802 break;
803 }
804 }
805 if (pathIndex == -1)
806 return B_BAD_VALUE;
807
808 LongBlock* curDirBlock
809 = (LongBlock*)fPathForLeaves[pathIndex].blockData;
810
811 SearchForMapInDirectoryBlock(nextLeaf, curDirBlock->NumRecs(),
812 &targetMap, LEAF, pathIndex);
813 if (targetMap == NULL)
814 return B_BAD_VALUE;
815
816 FillBuffer(fSingleDirBlock,
817 nextLeaf - targetMap->br_startoff, targetMap);
818 fOffsetOfSingleDirBlock = nextLeaf;
819
820 continue;
821 } else {
822 break;
823 }
824 delete leafHeader;
825 }
826 return B_ENTRY_NOT_FOUND;
827 }
828
829
830 uint32
ExpectedMagic(int8 WhichDirectory,Inode * inode)831 LongBlock::ExpectedMagic(int8 WhichDirectory, Inode* inode)
832 {
833 if(inode->Version() == 3)
834 return XFS_BMAP_CRC_MAGIC;
835 else
836 return XFS_BMAP_MAGIC;
837 }
838
839
840 uint32
CRCOffset()841 LongBlock::CRCOffset()
842 {
843 return offsetof(LongBlock, bb_crc);
844 }