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 "CachedBlock.h"
11 #include "HTree.h"
12
13 #include <new>
14 #include <string.h>
15
16 #include "HTreeEntryIterator.h"
17 #include "Inode.h"
18 #include "Volume.h"
19
20
21 //#define COLLISION_TEST
22
23 //#define TRACE_EXT2
24 #ifdef TRACE_EXT2
25 # define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
26 #else
27 # define TRACE(x...) ;
28 #endif
29
30
31 bool
IsValid() const32 HTreeRoot::IsValid() const
33 {
34 if (reserved != 0)
35 return false;
36 if (hash_version != HTREE_HASH_LEGACY
37 && hash_version != HTREE_HASH_HALF_MD4
38 && hash_version != HTREE_HASH_TEA)
39 return false;
40 if (root_info_length != 8)
41 return false;
42 if (indirection_levels > 1)
43 return false;
44
45 // TODO: Maybe we should check the false directory entries too?
46
47 return true;
48 }
49
50
HTree(Volume * volume,Inode * directory)51 HTree::HTree(Volume* volume, Inode* directory)
52 :
53 fDirectory(directory),
54 fHashVersion(HTREE_HASH_LEGACY),
55 fRootEntry(NULL)
56 {
57 fBlockSize = volume->BlockSize();
58 fIndexed = directory->IsIndexed();
59
60 ext2_super_block superBlock = volume->SuperBlock();
61 fHashSeed[0] = superBlock.HashSeed(0);
62 fHashSeed[1] = superBlock.HashSeed(1);
63 fHashSeed[2] = superBlock.HashSeed(2);
64 fHashSeed[3] = superBlock.HashSeed(3);
65
66 TRACE("HTree::HTree() %" B_PRIx32 " %" B_PRIx32 " %" B_PRIx32 " %" B_PRIx32
67 "\n", fHashSeed[0], fHashSeed[1], fHashSeed[2], fHashSeed[3]);
68
69 if (fHashSeed[0] == 0 && fHashSeed[1] == 0 && fHashSeed[2] == 0
70 && fHashSeed[3] == 0) {
71 fHashSeed[0] = 0x67452301;
72 fHashSeed[1] = 0xefcdab89;
73 fHashSeed[2] = 0x98badcfe;
74 fHashSeed[3] = 0x10325476;
75 }
76 }
77
78
~HTree()79 HTree::~HTree()
80 {
81 }
82
83
84 status_t
PrepareForHash()85 HTree::PrepareForHash()
86 {
87 fsblock_t blockNum;
88 status_t status = fDirectory->FindBlock(0, blockNum);
89 if (status != B_OK)
90 return status;
91
92 CachedBlock cached(fDirectory->GetVolume());
93 HTreeRoot* root = (HTreeRoot*)cached.SetTo(blockNum);
94 if (root == NULL)
95 return B_IO_ERROR;
96 if (!root->IsValid())
97 return B_BAD_DATA;
98
99 fHashVersion = root->hash_version;
100
101 return B_OK;
102 }
103
104
105 status_t
Lookup(const char * name,DirectoryIterator ** iterator)106 HTree::Lookup(const char* name, DirectoryIterator** iterator)
107 {
108 TRACE("HTree::Lookup()\n");
109 if (!fIndexed || (name[0] == '.'
110 && (name[1] == '\0' || (name[1] == '.' && name[2] == '\0')))) {
111 // No HTree support or looking for trivial directories
112 return _FallbackToLinearIteration(iterator);
113 }
114
115 fsblock_t blockNum;
116 status_t status = fDirectory->FindBlock(0, blockNum);
117 if (status != B_OK)
118 return _FallbackToLinearIteration(iterator);
119
120 CachedBlock cached(fDirectory->GetVolume());
121 HTreeRoot* root = (HTreeRoot*)cached.SetTo(blockNum);
122 if (root == NULL || !root->IsValid())
123 return _FallbackToLinearIteration(iterator);
124
125 fHashVersion = root->hash_version;
126
127 size_t _nameLength = strlen(name);
128 uint8 nameLength = _nameLength >= 256 ? 255 : (uint8)_nameLength;
129
130 uint32 hash = Hash(name, nameLength);
131
132 off_t start = (off_t)root->root_info_length
133 + 2 * (sizeof(HTreeFakeDirEntry) + 4);
134
135 fRootEntryDeleter.Unset();
136
137 fRootEntry = new(std::nothrow) HTreeEntryIterator(start, fDirectory);
138 if (fRootEntry == NULL)
139 return B_NO_MEMORY;
140
141 fRootEntryDeleter.SetTo(fRootEntry);
142
143 status = fRootEntry->Init();
144 if (status != B_OK)
145 return status;
146
147 bool detachRoot = false;
148 status = fRootEntry->Lookup(hash, (uint32)root->indirection_levels,
149 iterator, detachRoot);
150 TRACE("HTree::Lookup(): detach root: %c\n", detachRoot ? 't' : 'f');
151
152 if (detachRoot)
153 fRootEntryDeleter.Detach();
154
155 return status;
156 }
157
158
159 uint32
Hash(const char * name,uint8 length)160 HTree::Hash(const char* name, uint8 length)
161 {
162 uint32 hash;
163
164 #ifndef COLLISION_TEST
165 switch (fHashVersion) {
166 case HTREE_HASH_LEGACY:
167 hash = _HashLegacy(name, length);
168 break;
169 case HTREE_HASH_HALF_MD4:
170 hash = _HashHalfMD4(name, length);
171 break;
172 case HTREE_HASH_TEA:
173 hash = _HashTEA(name, length);
174 break;
175 default:
176 panic("Hash verification succeeded but then failed?");
177 hash = 0;
178 };
179 #else
180 hash = 0;
181 #endif
182
183 TRACE("HTree::_Hash(): filename hash 0x%" B_PRIx32 "\n", hash);
184
185 return hash & ~1;
186 }
187
188
189 uint32
_HashLegacy(const char * name,uint8 length)190 HTree::_HashLegacy(const char* name, uint8 length)
191 {
192 TRACE("HTree::_HashLegacy()\n");
193 uint32 hash = 0x12a3fe2d;
194 uint32 previous = 0x37abe8f9;
195
196 for (; length > 0; --length, ++name) {
197 uint32 next = previous + (hash ^ (*name * 7152373));
198
199 if ((next & 0x80000000) != 0)
200 next -= 0x7fffffff;
201
202 previous = hash;
203 hash = next;
204 }
205
206 return hash << 1;
207 }
208
209
210 /*inline*/ uint32
_MD4F(uint32 x,uint32 y,uint32 z)211 HTree::_MD4F(uint32 x, uint32 y, uint32 z)
212 {
213 return z ^ (x & (y ^ z));
214 }
215
216
217 /*inline*/ uint32
_MD4G(uint32 x,uint32 y,uint32 z)218 HTree::_MD4G(uint32 x, uint32 y, uint32 z)
219 {
220 return (x & y) + ((x ^ y) & z);
221 }
222
223
224 /*inline*/ uint32
_MD4H(uint32 x,uint32 y,uint32 z)225 HTree::_MD4H(uint32 x, uint32 y, uint32 z)
226 {
227 return x ^ y ^ z;
228 }
229
230
231 /*inline*/ void
_MD4RotateVars(uint32 & a,uint32 & b,uint32 & c,uint32 & d)232 HTree::_MD4RotateVars(uint32& a, uint32& b, uint32& c, uint32& d)
233 {
234 uint32 oldD = d;
235 d = c;
236 c = b;
237 b = a;
238 a = oldD;
239 }
240
241
242 void
_HalfMD4Transform(uint32 buffer[4],uint32 blocks[8])243 HTree::_HalfMD4Transform(uint32 buffer[4], uint32 blocks[8])
244 {
245 uint32 a, b, c, d;
246 a = buffer[0];
247 b = buffer[1];
248 c = buffer[2];
249 d = buffer[3];
250
251 // Round 1
252 uint32 shifts[4] = { 3, 7, 11, 19 };
253
254 for (int i = 0; i < 8; ++i) {
255 a += _MD4F(b, c, d) + blocks[i];
256 uint32 shift = shifts[i % 4];
257 a = (a << shift) | (a >> (32 - shift));
258
259 _MD4RotateVars(a, b, c, d);
260 }
261
262 // Round 2
263 shifts[1] = 5;
264 shifts[2] = 9;
265 shifts[3] = 13;
266
267 for (int j = 1; j >= 0; --j) {
268 for (int i = j; i < 8; i += 2) {
269 a += _MD4G(b, c, d) + blocks[i] + 013240474631UL;
270 uint32 shift = shifts[i / 2];
271 a = (a << shift) | (a >> (32 - shift));
272
273 _MD4RotateVars(a, b, c, d);
274 }
275 }
276
277 // Round 3
278 shifts[1] = 9;
279 shifts[2] = 11;
280 shifts[3] = 15;
281
282 for (int i = 0; i < 4; ++i) {
283 a += _MD4H(b, c, d) + blocks[3 - i] + 015666365641UL;
284 uint32 shift = shifts[i * 2 % 4];
285 a = (a << shift) | (a >> (32 - shift));
286
287 _MD4RotateVars(a, b, c, d);
288
289 a += _MD4H(b, c, d) + blocks[7 - i] + 015666365641UL;
290 shift = shifts[(i * 2 + 1) % 4];
291 a = (a << shift) | (a >> (32 - shift));
292
293 _MD4RotateVars(a, b, c, d);
294 }
295
296 buffer[0] += a;
297 buffer[1] += b;
298 buffer[2] += c;
299 buffer[3] += d;
300 }
301
302
303 uint32
_HashHalfMD4(const char * name,uint8 _length)304 HTree::_HashHalfMD4(const char* name, uint8 _length)
305 {
306 TRACE("HTree::_HashHalfMD4()\n");
307 uint32 buffer[4];
308 int32 length = _length;
309
310 buffer[0] = fHashSeed[0];
311 buffer[1] = fHashSeed[1];
312 buffer[2] = fHashSeed[2];
313 buffer[3] = fHashSeed[3];
314
315 for (; length > 0; length -= 32) {
316 uint32 blocks[8];
317
318 _PrepareBlocksForHash(name, (uint32)length, blocks, 8);
319 _HalfMD4Transform(buffer, blocks);
320
321 name += 32;
322 }
323
324 return buffer[1];
325 }
326
327
328 void
_TEATransform(uint32 buffer[4],uint32 blocks[4])329 HTree::_TEATransform(uint32 buffer[4], uint32 blocks[4])
330 {
331 uint32 x, y;
332 x = buffer[0];
333 y = buffer[1];
334
335 uint32 a, b, c, d;
336 a = blocks[0];
337 b = blocks[1];
338 c = blocks[2];
339 d = blocks[3];
340
341 uint32 sum = 0;
342
343 for (int i = 16; i > 0; --i) {
344 sum += 0x9E3779B9;
345 x += ((y << 4) + a) ^ (y + sum) ^ ((y >> 5) + b);
346 y += ((x << 4) + c) ^ (x + sum) ^ ((x >> 5) + d);
347 }
348
349 buffer[0] += x;
350 buffer[1] += y;
351 }
352
353
354 uint32
_HashTEA(const char * name,uint8 _length)355 HTree::_HashTEA(const char* name, uint8 _length)
356 {
357 TRACE("HTree::_HashTEA()\n");
358 uint32 buffer[4];
359 int32 length = _length;
360
361 buffer[0] = fHashSeed[0];
362 buffer[1] = fHashSeed[1];
363 buffer[2] = fHashSeed[2];
364 buffer[3] = fHashSeed[3];
365
366 for (; length > 0; length -= 16) {
367 uint32 blocks[4];
368
369 _PrepareBlocksForHash(name, (uint32)length, blocks, 4);
370 TRACE("_HashTEA %" B_PRIx32 " %" B_PRIx32 " %" B_PRIx32 "\n",
371 blocks[0], blocks[1], blocks[2]);
372 _TEATransform(buffer, blocks);
373
374 name += 16;
375 }
376
377 return buffer[0];
378 }
379
380
381 void
_PrepareBlocksForHash(const char * string,uint32 length,uint32 * blocks,uint32 numBlocks)382 HTree::_PrepareBlocksForHash(const char* string, uint32 length, uint32* blocks,
383 uint32 numBlocks)
384 {
385 uint32 padding = length;
386 padding |= padding << 8;
387 padding |= padding << 16;
388
389 uint32 numBytes = numBlocks * 4;
390 if (length > numBytes)
391 length = numBytes;
392
393 uint32 completeIterations = length / 4;
394
395 for (uint32 i = 0; i < completeIterations; ++i) {
396 uint32 value = (padding << 8) + *(string++);
397 value = (value << 8) + *(string++);
398 value = (value << 8) + *(string++);
399 value = (value << 8) + *(string++);
400 blocks[i] = value;
401 }
402
403 if (completeIterations < numBlocks) {
404 uint32 remainingBytes = length % 4;
405
406 uint32 value = padding;
407 for (uint32 i = 0; i < remainingBytes; ++i)
408 value = (value << 8) + *(string++);
409
410 blocks[completeIterations] = value;
411
412 for (uint32 i = completeIterations + 1; i < numBlocks; ++i)
413 blocks[i] = padding;
414 }
415 }
416
417
418 /*inline*/ status_t
_FallbackToLinearIteration(DirectoryIterator ** iterator)419 HTree::_FallbackToLinearIteration(DirectoryIterator** iterator)
420 {
421 *iterator = new(std::nothrow) DirectoryIterator(fDirectory);
422
423 return *iterator == NULL ? B_NO_MEMORY : B_OK;
424 }
425
426