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 32 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 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 79 HTree::~HTree() 80 { 81 } 82 83 84 status_t 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 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 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 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 211 HTree::_MD4F(uint32 x, uint32 y, uint32 z) 212 { 213 return z ^ (x & (y ^ z)); 214 } 215 216 217 /*inline*/ uint32 218 HTree::_MD4G(uint32 x, uint32 y, uint32 z) 219 { 220 return (x & y) + ((x ^ y) & z); 221 } 222 223 224 /*inline*/ uint32 225 HTree::_MD4H(uint32 x, uint32 y, uint32 z) 226 { 227 return x ^ y ^ z; 228 } 229 230 231 /*inline*/ void 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 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 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 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 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 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 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