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