1 /*
2 * Copyright 2010, Haiku Inc. All rights reserved.
3 * This file may be used under the terms of the MIT License.
4 *
5 * Authors:
6 * Janito V. Ferreira Filho
7 */
8
9
10 #include "HTreeEntryIterator.h"
11
12 #include <new>
13
14 #include "CachedBlock.h"
15 #include "CRCTable.h"
16 #include "HTree.h"
17 #include "Inode.h"
18
19
20 //#define TRACE_EXT2
21 #ifdef TRACE_EXT2
22 # define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
23 #else
24 # define TRACE(x...) ;
25 #endif
26 #define ERROR(x...) dprintf("\33[34mext2:\33[0m " x)
27
28
HTreeEntryIterator(off_t offset,Inode * directory)29 HTreeEntryIterator::HTreeEntryIterator(off_t offset, Inode* directory)
30 :
31 fDirectory(directory),
32 fVolume(directory->GetVolume()),
33 fHasCollision(false),
34 fLimit(0),
35 fCount(0),
36 fBlockSize(directory->GetVolume()->BlockSize()),
37 fParent(NULL),
38 fChild(NULL)
39 {
40 fInitStatus = fDirectory->FindBlock(offset, fBlockNum);
41
42 if (fInitStatus == B_OK) {
43 fFirstEntry = offset % fBlockSize / sizeof(HTreeEntry);
44 fCurrentEntry = fFirstEntry;
45 }
46
47 TRACE("HTreeEntryIterator::HTreeEntryIterator(): created %p, block %" B_PRIu64 ", "
48 "entry no. %u, parent: %p\n", this, fBlockNum, fCurrentEntry,
49 fParent);
50 }
51
52
HTreeEntryIterator(uint32 block,uint32 blockSize,Inode * directory,HTreeEntryIterator * parent,bool hasCollision)53 HTreeEntryIterator::HTreeEntryIterator(uint32 block, uint32 blockSize,
54 Inode* directory, HTreeEntryIterator* parent, bool hasCollision)
55 :
56 fDirectory(directory),
57 fVolume(directory->GetVolume()),
58 fHasCollision(hasCollision),
59 fLimit(0),
60 fCount(0),
61 fFirstEntry(1),
62 fCurrentEntry(1),
63 fBlockSize(blockSize),
64 fBlockNum(block),
65 fParent(parent),
66 fChild(NULL)
67 {
68 // fCurrentEntry is initialized to 1 to skip the fake directory entry
69 fInitStatus = B_OK;
70
71 TRACE("HTreeEntryIterator::HTreeEntryIterator(): created %p, block %"
72 B_PRIu32 ", parent: %p\n", this, block, fParent);
73 }
74
75
76 status_t
Init()77 HTreeEntryIterator::Init()
78 {
79 TRACE("HTreeEntryIterator::Init() first entry: %u\n",
80 fFirstEntry);
81
82 if (fInitStatus != B_OK)
83 return fInitStatus;
84
85 CachedBlock cached(fVolume);
86 const uint8* block = cached.SetTo(fBlockNum);
87 if (block == NULL) {
88 ERROR("Failed to read htree entry block.\n");
89 fCount = fLimit = 0;
90 return B_IO_ERROR;
91 }
92
93 HTreeCountLimit* countLimit = (HTreeCountLimit*)(
94 &((HTreeEntry*)block)[fFirstEntry]);
95
96 fCount = countLimit->Count();
97 fLimit = countLimit->Limit();
98
99 if (fCount > fLimit) {
100 ERROR("HTreeEntryIterator::Init() bad fCount %u (fLimit %u)\n",
101 fCount, fLimit);
102 fCount = fLimit = 0;
103 return B_ERROR;
104 }
105
106 uint32 maxSize = fBlockSize;
107 if (fVolume->HasMetaGroupChecksumFeature())
108 maxSize -= sizeof(ext2_htree_tail);
109
110 if (fLimit != maxSize / sizeof(HTreeEntry) - fFirstEntry) {
111 ERROR("HTreeEntryIterator::Init() bad fLimit %u should be %" B_PRIu32
112 " at block %" B_PRIu64 "\n", fLimit,
113 (uint32)(maxSize / sizeof(HTreeEntry) - fFirstEntry), fBlockNum);
114 fCount = fLimit = 0;
115 return B_ERROR;
116 }
117
118 TRACE("HTreeEntryIterator::Init() count %u limit %u\n",
119 fCount, fLimit);
120
121 return B_OK;
122 }
123
124
~HTreeEntryIterator()125 HTreeEntryIterator::~HTreeEntryIterator()
126 {
127 TRACE("HTreeEntryIterator::~HTreeEntryIterator(): %p, parent: %p\n", this,
128 fParent);
129 delete fParent;
130 TRACE("HTreeEntryIterator::~HTreeEntryIterator(): Deleted the parent\n");
131 }
132
133
134 status_t
Lookup(uint32 hash,int indirections,DirectoryIterator ** directoryIterator,bool & detachRoot)135 HTreeEntryIterator::Lookup(uint32 hash, int indirections,
136 DirectoryIterator** directoryIterator, bool& detachRoot)
137 {
138 TRACE("HTreeEntryIterator::Lookup()\n");
139
140 if (fCount == 0)
141 return B_ENTRY_NOT_FOUND;
142
143 CachedBlock cached(fVolume);
144 const uint8* block = cached.SetTo(fBlockNum);
145 if (block == NULL) {
146 ERROR("Failed to read htree entry block.\n");
147 // Fallback to linear search
148 *directoryIterator = new(std::nothrow)
149 DirectoryIterator(fDirectory);
150
151 if (*directoryIterator == NULL)
152 return B_NO_MEMORY;
153
154 return B_OK;
155 }
156
157 HTreeEntry* start = (HTreeEntry*)block + fCurrentEntry + 1;
158 HTreeEntry* end = (HTreeEntry*)block + fCount + fFirstEntry - 1;
159 HTreeEntry* middle = start;
160
161 TRACE("HTreeEntryIterator::Lookup() current entry: %u\n",
162 fCurrentEntry);
163 TRACE("HTreeEntryIterator::Lookup() indirections: %d s:%p m:%p e:%p\n",
164 indirections, start, middle, end);
165
166 while (start <= end) {
167 middle = (HTreeEntry*)((end - start) / 2
168 + start);
169
170 TRACE("HTreeEntryIterator::Lookup() indirections: %d s:%p m:%p e:%p\n",
171 indirections, start, middle, end);
172
173 TRACE("HTreeEntryIterator::Lookup() %" B_PRIx32 " %" B_PRIx32 "\n",
174 hash, middle->Hash());
175
176 if (hash >= middle->Hash())
177 start = middle + 1;
178 else
179 end = middle - 1;
180 }
181
182 --start;
183
184 fCurrentEntry = ((uint8*)start - block) / sizeof(HTreeEntry);
185
186 if (indirections == 0) {
187 TRACE("HTreeEntryIterator::Lookup(): Creating an indexed directory "
188 "iterator starting at block: %" B_PRIu32 ", hash: 0x%" B_PRIx32
189 "\n", start->Block(), start->Hash());
190 *directoryIterator = new(std::nothrow)
191 DirectoryIterator(fDirectory, start->Block() * fBlockSize, this);
192
193 if (*directoryIterator == NULL)
194 return B_NO_MEMORY;
195
196 detachRoot = true;
197 return B_OK;
198 }
199
200 TRACE("HTreeEntryIterator::Lookup(): Creating a HTree entry iterator "
201 "starting at block: %" B_PRIu32 ", hash: 0x%" B_PRIx32 "\n",
202 start->Block(), start->Hash());
203 fsblock_t blockNum;
204 status_t status = fDirectory->FindBlock(start->Block() * fBlockSize,
205 blockNum);
206 if (status != B_OK)
207 return status;
208
209 delete fChild;
210
211 fChild = new(std::nothrow) HTreeEntryIterator(blockNum, fBlockSize,
212 fDirectory, this, (start->Hash() & 1) == 1);
213 if (fChild == NULL)
214 return B_NO_MEMORY;
215
216 status = fChild->Init();
217 if (status != B_OK)
218 return status;
219
220 return fChild->Lookup(hash, indirections - 1, directoryIterator,
221 detachRoot);
222 }
223
224
225 status_t
GetNext(uint32 & childBlock)226 HTreeEntryIterator::GetNext(uint32& childBlock)
227 {
228 fCurrentEntry++;
229 TRACE("HTreeEntryIterator::GetNext(): current entry: %u count: %u, "
230 "limit: %u\n", fCurrentEntry, fCount, fLimit);
231 bool endOfBlock = fCurrentEntry >= (fCount + fFirstEntry);
232
233 if (endOfBlock) {
234 TRACE("HTreeEntryIterator::GetNext(): end of entries in the block\n");
235 if (fParent == NULL) {
236 TRACE("HTreeEntryIterator::GetNext(): block was the root block\n");
237 return B_ENTRY_NOT_FOUND;
238 }
239
240 uint32 logicalBlock;
241 status_t status = fParent->GetNext(logicalBlock);
242 if (status != B_OK)
243 return status;
244
245 TRACE("HTreeEntryIterator::GetNext(): moving to next block: %" B_PRIx32
246 "\n", logicalBlock);
247
248 status = fDirectory->FindBlock(logicalBlock * fBlockSize, fBlockNum);
249 if (status != B_OK)
250 return status;
251
252 fFirstEntry = 1; // Skip fake directory entry
253 fCurrentEntry = 1;
254 status = Init();
255 if (status != B_OK)
256 return status;
257
258 fHasCollision = fParent->HasCollision();
259 }
260
261 CachedBlock cached(fVolume);
262 const uint8* block = cached.SetTo(fBlockNum);
263 if (block == NULL)
264 return B_IO_ERROR;
265
266 HTreeEntry* entry = &((HTreeEntry*)block)[fCurrentEntry];
267
268 if (!endOfBlock)
269 fHasCollision = (entry[fCurrentEntry].Hash() & 1) == 1;
270
271 TRACE("HTreeEntryIterator::GetNext(): next block: %" B_PRIu32 "\n",
272 entry->Block());
273
274 childBlock = entry->Block();
275
276 return B_OK;
277 }
278
279
280 uint32
BlocksNeededForNewEntry()281 HTreeEntryIterator::BlocksNeededForNewEntry()
282 {
283 TRACE("HTreeEntryIterator::BlocksNeededForNewEntry(): block num: %"
284 B_PRIu64 ", volume: %p\n", fBlockNum, fVolume);
285 CachedBlock cached(fVolume);
286
287 const uint8* blockData = cached.SetTo(fBlockNum);
288 const HTreeEntry* entries = (const HTreeEntry*)blockData;
289 const HTreeCountLimit* countLimit =
290 (const HTreeCountLimit*)&entries[fFirstEntry];
291
292 uint32 newBlocks = 0;
293 if (countLimit->IsFull()) {
294 newBlocks++;
295
296 if (fParent != NULL)
297 newBlocks += fParent->BlocksNeededForNewEntry();
298 else {
299 // Need a new level
300 HTreeRoot* root = (HTreeRoot*)entries;
301
302 if (root->indirection_levels == 1) {
303 // Maximum supported indirection levels reached
304 return B_DEVICE_FULL;
305 }
306
307 newBlocks++;
308 }
309 }
310
311 return newBlocks;
312 }
313
314
315 status_t
InsertEntry(Transaction & transaction,uint32 hash,off_t blockNum,off_t newBlocksPos,bool hasCollision)316 HTreeEntryIterator::InsertEntry(Transaction& transaction, uint32 hash,
317 off_t blockNum, off_t newBlocksPos, bool hasCollision)
318 {
319 TRACE("HTreeEntryIterator::InsertEntry(): block num: %" B_PRIu64 "\n",
320 fBlockNum);
321 CachedBlock cached(fVolume);
322
323 uint8* blockData = cached.SetToWritable(transaction, fBlockNum);
324 if (blockData == NULL)
325 return B_IO_ERROR;
326
327 HTreeEntry* entries = (HTreeEntry*)blockData;
328
329 HTreeCountLimit* countLimit = (HTreeCountLimit*)&entries[fFirstEntry];
330 uint16 count = countLimit->Count();
331
332 if (count == countLimit->Limit()) {
333 TRACE("HTreeEntryIterator::InsertEntry(): Splitting the node\n");
334 panic("Splitting a HTree node required, but isn't yet fully "
335 "supported\n");
336
337 fsblock_t physicalBlock;
338 status_t status = fDirectory->FindBlock(newBlocksPos, physicalBlock);
339 if (status != B_OK)
340 return status;
341
342 CachedBlock secondCached(fVolume);
343 uint8* secondBlockData = secondCached.SetToWritable(transaction,
344 physicalBlock);
345 if (secondBlockData == NULL)
346 return B_IO_ERROR;
347
348 uint32 maxSize = fBlockSize;
349 if (fVolume->HasMetaGroupChecksumFeature())
350 maxSize -= sizeof(ext2_dir_entry_tail);
351
352 HTreeFakeDirEntry* fakeEntry = (HTreeFakeDirEntry*)secondBlockData;
353 fakeEntry->inode_id = 0; // ?
354 fakeEntry->SetEntryLength(fBlockSize);
355 fakeEntry->name_length = 0;
356 fakeEntry->file_type = 0; // ?
357
358 HTreeEntry* secondBlockEntries = (HTreeEntry*)secondBlockData;
359 memmove(&entries[fFirstEntry + count / 2], &secondBlockEntries[1],
360 (count - count / 2) * sizeof(HTreeEntry));
361 _SetHTreeEntryChecksum(secondBlockData);
362 }
363
364 TRACE("HTreeEntryIterator::InsertEntry(): Inserting node. Count: %u, "
365 "current entry: %u\n", count, fCurrentEntry);
366
367 if (count > 0) {
368 TRACE("HTreeEntryIterator::InsertEntry(): memmove(%u, %u, %u)\n",
369 fCurrentEntry + 2, fCurrentEntry + 1, count + fFirstEntry
370 - fCurrentEntry - 1);
371 memmove(&entries[fCurrentEntry + 2], &entries[fCurrentEntry + 1],
372 (count + fFirstEntry - fCurrentEntry - 1) * sizeof(HTreeEntry));
373 }
374
375 uint32 oldHash = entries[fCurrentEntry].Hash();
376 entries[fCurrentEntry].SetHash(hasCollision ? oldHash | 1 : oldHash & ~1);
377 entries[fCurrentEntry + 1].SetHash((oldHash & 1) == 0 ? hash & ~1
378 : hash | 1);
379 entries[fCurrentEntry + 1].SetBlock(blockNum);
380
381 countLimit->SetCount(count + 1);
382
383 _SetHTreeEntryChecksum(blockData);
384
385 return B_OK;
386 }
387
388
389 ext2_htree_tail*
_HTreeEntryTail(uint8 * block) const390 HTreeEntryIterator::_HTreeEntryTail(uint8* block) const
391 {
392 HTreeEntry* entries = (HTreeEntry*)block;
393 HTreeCountLimit* countLimit = (HTreeCountLimit*)&entries[fFirstEntry];
394 uint16 limit = countLimit->Limit();
395 return (ext2_htree_tail*)(&entries[fFirstEntry + limit]);
396 }
397
398
399 uint32
_Checksum(uint8 * block) const400 HTreeEntryIterator::_Checksum(uint8* block) const
401 {
402 uint32 number = fDirectory->ID();
403 uint32 checksum = calculate_crc32c(fVolume->ChecksumSeed(),
404 (uint8*)&number, sizeof(number));
405 uint32 gen = fDirectory->Node().generation;
406 checksum = calculate_crc32c(checksum, (uint8*)&gen, sizeof(gen));
407 checksum = calculate_crc32c(checksum, block,
408 (fFirstEntry + fCount) * sizeof(HTreeEntry));
409 ext2_htree_tail dummy;
410 checksum = calculate_crc32c(checksum, (uint8*)&dummy, sizeof(dummy));
411 return checksum;
412 }
413
414
415 void
_SetHTreeEntryChecksum(uint8 * block)416 HTreeEntryIterator::_SetHTreeEntryChecksum(uint8* block)
417 {
418 if (fVolume->HasMetaGroupChecksumFeature()) {
419 ext2_htree_tail* tail = _HTreeEntryTail(block);
420 tail->reserved = 0xde00000c;
421 tail->checksum = _Checksum(block);
422 }
423 }
424
425