Changeset 38542dc in mainline for uspace/lib/ext4/libext4_directory_index.c
- Timestamp:
- 2012-08-12T18:36:10Z (12 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 49505fe
- Parents:
- b08e7970
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/ext4/libext4_directory_index.c
rb08e7970 r38542dc 29 29 /** @addtogroup libext4 30 30 * @{ 31 */ 32 31 */ 33 32 /** 34 * @file 35 * @brief 33 * @file libext4_directory_index.c 34 * @brief Ext4 directory index operations. 36 35 */ 37 36 … … 40 39 #include <malloc.h> 41 40 #include <sort.h> 42 #include <string.h>43 41 #include "libext4.h" 44 42 … … 52 50 } ext4_dx_sort_entry_t; 53 51 54 55 52 /** Get hash version used in directory index. 56 53 * 57 * @param root_info pointer to root info structure of index 58 * @return hash algorithm version 54 * @param root_info Pointer to root info structure of index 55 * 56 * @return Hash algorithm version 57 * 59 58 */ 60 59 uint8_t ext4_directory_dx_root_info_get_hash_version( 61 60 ext4_directory_dx_root_info_t *root_info) 62 61 { 63 62 return root_info->hash_version; … … 66 65 /** Set hash version, that will be used in directory index. 67 66 * 68 * @param root_info pointer to root info structure of index 69 * @param version hash algorithm version 67 * @param root_info Pointer to root info structure of index 68 * @param version Hash algorithm version 69 * 70 70 */ 71 71 void ext4_directory_dx_root_info_set_hash_version( 72 72 ext4_directory_dx_root_info_t *root_info, uint8_t version) 73 73 { 74 74 root_info->hash_version = version; … … 77 77 /** Get length of root_info structure in bytes. 78 78 * 79 * @param root_info pointer to root info structure of index 80 * @return length of the structure 79 * @param root_info Pointer to root info structure of index 80 * 81 * @return Length of the structure 82 * 81 83 */ 82 84 uint8_t ext4_directory_dx_root_info_get_info_length( 83 85 ext4_directory_dx_root_info_t *root_info) 84 86 { 85 87 return root_info->info_length; … … 88 90 /** Set length of root_info structure in bytes. 89 91 * 90 * @param root_info pointer to root info structure of index 91 * @param info_length length of the structure 92 * @param root_info Pointer to root info structure of index 93 * @param info_length Length of the structure 94 * 92 95 */ 93 96 void ext4_directory_dx_root_info_set_info_length( 94 97 ext4_directory_dx_root_info_t *root_info, uint8_t info_length) 95 98 { 96 99 root_info->info_length = info_length; … … 99 102 /** Get number of indirect levels of HTree. 100 103 * 101 * @param root_info pointer to root info structure of index 102 * @return height of HTree (actually only 0 or 1) 104 * @param root_info Pointer to root info structure of index 105 * 106 * @return Height of HTree (actually only 0 or 1) 107 * 103 108 */ 104 109 uint8_t ext4_directory_dx_root_info_get_indirect_levels( 105 110 ext4_directory_dx_root_info_t *root_info) 106 111 { 107 112 return root_info->indirect_levels; … … 110 115 /** Set number of indirect levels of HTree. 111 116 * 112 * @param root_info pointer to root info structure of index 113 * @param levels height of HTree (actually only 0 or 1) 117 * @param root_info Pointer to root info structure of index 118 * @param levels Height of HTree (actually only 0 or 1) 119 * 114 120 */ 115 121 void ext4_directory_dx_root_info_set_indirect_levels( 116 122 ext4_directory_dx_root_info_t *root_info, uint8_t levels) 117 123 { 118 124 root_info->indirect_levels = levels; … … 121 127 /** Get maximum number of index node entries. 122 128 * 123 * @param countlimit pointer to counlimit structure 124 * @return maximum of entries in node 129 * @param countlimit Pointer to counlimit structure 130 * 131 * @return Maximum of entries in node 132 * 125 133 */ 126 134 uint16_t ext4_directory_dx_countlimit_get_limit( 127 135 ext4_directory_dx_countlimit_t *countlimit) 128 136 { 129 137 return uint16_t_le2host(countlimit->limit); … … 132 140 /** Set maximum number of index node entries. 133 141 * 134 * @param countlimit pointer to counlimit structure 135 * @param limit maximum of entries in node 142 * @param countlimit Pointer to counlimit structure 143 * @param limit Maximum of entries in node 144 * 136 145 */ 137 146 void ext4_directory_dx_countlimit_set_limit( 138 147 ext4_directory_dx_countlimit_t *countlimit, uint16_t limit) 139 148 { 140 149 countlimit->limit = host2uint16_t_le(limit); … … 143 152 /** Get current number of index node entries. 144 153 * 145 * @param countlimit pointer to counlimit structure 146 * @return number of entries in node 154 * @param countlimit Pointer to counlimit structure 155 * 156 * @return Number of entries in node 157 * 147 158 */ 148 159 uint16_t ext4_directory_dx_countlimit_get_count( 149 160 ext4_directory_dx_countlimit_t *countlimit) 150 161 { 151 162 return uint16_t_le2host(countlimit->count); … … 154 165 /** Set current number of index node entries. 155 166 * 156 * @param countlimit pointer to counlimit structure 157 * @param count number of entries in node 167 * @param countlimit Pointer to counlimit structure 168 * @param count Number of entries in node 169 * 158 170 */ 159 171 void ext4_directory_dx_countlimit_set_count( 160 172 ext4_directory_dx_countlimit_t *countlimit, uint16_t count) 161 173 { 162 174 countlimit->count = host2uint16_t_le(count); … … 165 177 /** Get hash value of index entry. 166 178 * 167 * @param entry pointer to index entry 168 * @return hash value 179 * @param entry Pointer to index entry 180 * 181 * @return Hash value 182 * 169 183 */ 170 184 uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *entry) … … 173 187 } 174 188 175 176 189 /** Set hash value of index entry. 177 190 * 178 * @param entry pointer to index entry 179 * @param hash hash value 191 * @param entry Pointer to index entry 192 * @param hash Hash value 193 * 180 194 */ 181 195 void ext4_directory_dx_entry_set_hash(ext4_directory_dx_entry_t *entry, 182 196 uint32_t hash) 183 197 { 184 198 entry->hash = host2uint32_t_le(hash); … … 187 201 /** Get block address where child node is located. 188 202 * 189 * @param entry pointer to index entry 190 * @return block address of child node 203 * @param entry Pointer to index entry 204 * 205 * @return Block address of child node 206 * 191 207 */ 192 208 uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *entry) … … 197 213 /** Set block address where child node is located. 198 214 * 199 * @param entry pointer to index entry 200 * @param block block address of child node 215 * @param entry Pointer to index entry 216 * @param block Block address of child node 217 * 201 218 */ 202 219 void ext4_directory_dx_entry_set_block(ext4_directory_dx_entry_t *entry, 203 220 uint32_t block) 204 221 { 205 222 entry->block = host2uint32_t_le(block); 206 223 } 207 224 208 209 /**************************************************************************/210 211 225 /** Initialize index structure of new directory. 212 226 * 213 * @param dir pointer to directory i-node 214 * @return error code 227 * @param dir Pointer to directory i-node 228 * 229 * @return Error code 230 * 215 231 */ 216 232 int ext4_directory_dx_init(ext4_inode_ref_t *dir) 217 233 { 218 int rc;219 220 234 /* Load block 0, where will be index root located */ 221 235 uint32_t fblock; 222 rc = ext4_filesystem_get_inode_data_block_index(dir, 0, &fblock);223 if (rc != EOK) {224 return rc;225 }226 236 int rc = ext4_filesystem_get_inode_data_block_index(dir, 0, 237 &fblock); 238 if (rc != EOK) 239 return rc; 240 227 241 block_t *block; 228 242 rc = block_get(&block, dir->fs->device, fblock, BLOCK_FLAGS_NONE); 229 if (rc != EOK) { 230 return rc; 231 } 232 243 if (rc != EOK) 244 return rc; 245 233 246 /* Initialize pointers to data structures */ 234 247 ext4_directory_dx_root_t *root = block->data; 235 248 ext4_directory_dx_root_info_t *info = &(root->info); 236 249 237 250 /* Initialize root info structure */ 238 251 uint8_t hash_version = 239 240 252 ext4_superblock_get_default_hash_version(dir->fs->superblock); 253 241 254 ext4_directory_dx_root_info_set_hash_version(info, hash_version); 242 255 ext4_directory_dx_root_info_set_indirect_levels(info, 0); 243 256 ext4_directory_dx_root_info_set_info_length(info, 8); 244 257 245 258 /* Set limit and current number of entries */ 246 259 ext4_directory_dx_countlimit_t *countlimit = 247 (ext4_directory_dx_countlimit_t *)&root->entries;260 (ext4_directory_dx_countlimit_t *) &root->entries; 248 261 ext4_directory_dx_countlimit_set_count(countlimit, 1); 249 250 uint32_t block_size = ext4_superblock_get_block_size(dir->fs->superblock); 251 uint32_t entry_space = block_size - 2 * sizeof(ext4_directory_dx_dot_entry_t) 252 - sizeof(ext4_directory_dx_root_info_t); 262 263 uint32_t block_size = 264 ext4_superblock_get_block_size(dir->fs->superblock); 265 uint32_t entry_space = 266 block_size - 2 * sizeof(ext4_directory_dx_dot_entry_t) - 267 sizeof(ext4_directory_dx_root_info_t); 253 268 uint16_t root_limit = entry_space / sizeof(ext4_directory_dx_entry_t); 254 269 ext4_directory_dx_countlimit_set_limit(countlimit, root_limit); 255 270 256 271 /* Append new block, where will be new entries inserted in the future */ 257 272 uint32_t iblock; … … 261 276 return rc; 262 277 } 263 278 264 279 block_t *new_block; 265 280 rc = block_get(&new_block, dir->fs->device, fblock, BLOCK_FLAGS_NOREAD); … … 268 283 return rc; 269 284 } 270 285 271 286 /* Fill the whole block with empty entry */ 272 287 ext4_directory_entry_ll_t *block_entry = new_block->data; 273 288 ext4_directory_entry_ll_set_entry_length(block_entry, block_size); 274 289 ext4_directory_entry_ll_set_inode(block_entry, 0); 275 290 276 291 new_block->dirty = true; 277 292 rc = block_put(new_block); … … 280 295 return rc; 281 296 } 282 297 283 298 /* Connect new block to the only entry in index */ 284 299 ext4_directory_dx_entry_t *entry = root->entries; 285 300 ext4_directory_dx_entry_set_block(entry, iblock); 286 301 287 302 block->dirty = true; 288 289 rc = block_put(block); 290 if (rc != EOK) { 291 return rc; 292 } 293 294 return EOK; 303 304 return block_put(block); 295 305 } 296 306 297 307 /** Initialize hash info structure necessary for index operations. 298 308 * 299 * @param hinfo pointer to hinfo to be initialized 300 * @param root_block root block (number 0) of index 301 * @param sb pointer to superblock 302 * @param name_len length of name to be computed hash value from 303 * @param name name to be computed hash value from 304 * @return error code 305 */ 306 static int ext4_directory_hinfo_init(ext4_hash_info_t *hinfo, block_t *root_block, 307 ext4_superblock_t *sb, size_t name_len, const char *name) 308 { 309 310 ext4_directory_dx_root_t *root = (ext4_directory_dx_root_t *)root_block->data; 311 312 if (root->info.hash_version != EXT4_HASH_VERSION_TEA && 313 root->info.hash_version != EXT4_HASH_VERSION_HALF_MD4 && 314 root->info.hash_version != EXT4_HASH_VERSION_LEGACY) { 309 * @param hinfo Pointer to hinfo to be initialized 310 * @param root_block Root block (number 0) of index 311 * @param sb Pointer to superblock 312 * @param name_len Length of name to be computed hash value from 313 * @param name Name to be computed hash value from 314 * 315 * @return Error code 316 * 317 */ 318 static int ext4_directory_hinfo_init(ext4_hash_info_t *hinfo, 319 block_t *root_block, ext4_superblock_t *sb, size_t name_len, 320 const char *name) 321 { 322 ext4_directory_dx_root_t *root = 323 (ext4_directory_dx_root_t *) root_block->data; 324 325 if ((root->info.hash_version != EXT4_HASH_VERSION_TEA) && 326 (root->info.hash_version != EXT4_HASH_VERSION_HALF_MD4) && 327 (root->info.hash_version != EXT4_HASH_VERSION_LEGACY)) 315 328 return EXT4_ERR_BAD_DX_DIR; 316 } 317 329 318 330 /* Check unused flags */ 319 if (root->info.unused_flags != 0) {331 if (root->info.unused_flags != 0) 320 332 return EXT4_ERR_BAD_DX_DIR; 321 } 322 333 323 334 /* Check indirect levels */ 324 if (root->info.indirect_levels > 1) {335 if (root->info.indirect_levels > 1) 325 336 return EXT4_ERR_BAD_DX_DIR; 326 } 327 337 328 338 /* Check if node limit is correct */ 329 339 uint32_t block_size = ext4_superblock_get_block_size(sb); … … 331 341 entry_space -= 2 * sizeof(ext4_directory_dx_dot_entry_t); 332 342 entry_space -= sizeof(ext4_directory_dx_root_info_t); 333 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t); 334 335 uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries); 336 if (limit != entry_space) { 337 return EXT4_ERR_BAD_DX_DIR; 338 } 339 340 /* Check hash version and modify if necessary */ 341 hinfo->hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info); 342 if ((hinfo->hash_version <= EXT4_HASH_VERSION_TEA) 343 && (ext4_superblock_has_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) { 343 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t); 344 345 uint16_t limit = ext4_directory_dx_countlimit_get_limit( 346 (ext4_directory_dx_countlimit_t *) &root->entries); 347 if (limit != entry_space) 348 return EXT4_ERR_BAD_DX_DIR; 349 350 /* Check hash version and modify if necessary */ 351 hinfo->hash_version = 352 ext4_directory_dx_root_info_get_hash_version(&root->info); 353 if ((hinfo->hash_version <= EXT4_HASH_VERSION_TEA) && 354 (ext4_superblock_has_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) { 344 355 /* 3 is magic from ext4 linux implementation */ 345 356 hinfo->hash_version += 3; 346 357 } 347 358 348 359 /* Load hash seed from superblock */ 349 360 hinfo->seed = ext4_superblock_get_hash_seed(sb); 350 361 351 362 /* Compute hash value of name */ 352 if (name) {363 if (name) 353 364 ext4_hash_string(hinfo, name_len, name); 354 } 355 365 356 366 return EOK; 357 367 } … … 359 369 /** Walk through index tree and load leaf with corresponding hash value. 360 370 * 361 * @param hinfo initialized hash info structure 362 * @param inode_ref current i-node 363 * @param root_block root block (iblock 0), where is root node located 364 * @param dx_block pointer to leaf node in dx_blocks array 365 * @param dx_blocks array with the whole path from root to leaf 366 * @return error code 371 * @param hinfo Initialized hash info structure 372 * @param inode_ref Current i-node 373 * @param root_block Root block (iblock 0), where is root node located 374 * @param dx_block Pointer to leaf node in dx_blocks array 375 * @param dx_blocks Array with the whole path from root to leaf 376 * 377 * @return Error code 378 * 367 379 */ 368 380 static int ext4_directory_dx_get_leaf(ext4_hash_info_t *hinfo, 369 ext4_inode_ref_t *inode_ref, block_t *root_block, 370 ext4_directory_dx_block_t **dx_block, ext4_directory_dx_block_t *dx_blocks) 371 { 372 int rc; 373 381 ext4_inode_ref_t *inode_ref, block_t *root_block, 382 ext4_directory_dx_block_t **dx_block, ext4_directory_dx_block_t *dx_blocks) 383 { 374 384 ext4_directory_dx_block_t *tmp_dx_block = dx_blocks; 375 376 ext4_directory_dx_root_t *root = (ext4_directory_dx_root_t *)root_block->data; 377 ext4_directory_dx_entry_t *entries = (ext4_directory_dx_entry_t *)&root->entries; 378 379 uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries); 380 uint8_t indirect_level = ext4_directory_dx_root_info_get_indirect_levels(&root->info); 381 385 ext4_directory_dx_root_t *root = 386 (ext4_directory_dx_root_t *) root_block->data; 387 ext4_directory_dx_entry_t *entries = 388 (ext4_directory_dx_entry_t *) &root->entries; 389 390 uint16_t limit = ext4_directory_dx_countlimit_get_limit( 391 (ext4_directory_dx_countlimit_t *) entries); 392 uint8_t indirect_level = 393 ext4_directory_dx_root_info_get_indirect_levels(&root->info); 394 382 395 block_t *tmp_block = root_block; 383 ext4_directory_dx_entry_t *p, *q, *m, *at; 384 396 ext4_directory_dx_entry_t *p; 397 ext4_directory_dx_entry_t *q; 398 ext4_directory_dx_entry_t *m; 399 ext4_directory_dx_entry_t *at; 400 385 401 /* Walk through the index tree */ 386 402 while (true) { 387 388 uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);389 if ((count == 0) || (count > limit)) {403 uint16_t count = ext4_directory_dx_countlimit_get_count( 404 (ext4_directory_dx_countlimit_t *) entries); 405 if ((count == 0) || (count > limit)) 390 406 return EXT4_ERR_BAD_DX_DIR; 391 } 392 393 407 394 408 /* Do binary search in every node */ 395 409 p = entries + 1; 396 410 q = entries + count - 1; 397 411 398 412 while (p <= q) { 399 413 m = p + (q - p) / 2; 400 if (ext4_directory_dx_entry_get_hash(m) > hinfo->hash) {414 if (ext4_directory_dx_entry_get_hash(m) > hinfo->hash) 401 415 q = m - 1; 402 } else {416 else 403 417 p = m + 1; 404 }405 418 } 406 419 407 420 at = p - 1; 408 421 409 422 /* Write results */ 410 423 tmp_dx_block->block = tmp_block; 411 424 tmp_dx_block->entries = entries; 412 425 tmp_dx_block->position = at; 413 426 414 427 /* Is algorithm in the leaf? */ 415 416 417 418 419 420 428 if (indirect_level == 0) { 429 *dx_block = tmp_dx_block; 430 return EOK; 431 } 432 433 /* Goto child node */ 421 434 uint32_t next_block = ext4_directory_dx_entry_get_block(at); 422 423 indirect_level--; 424 425 uint32_t fblock; 426 rc = ext4_filesystem_get_inode_data_block_index( 427 inode_ref, next_block, &fblock); 428 if (rc != EOK) { 429 return rc; 430 } 431 432 rc = block_get(&tmp_block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NONE); 433 if (rc != EOK) { 434 return rc; 435 } 436 435 436 indirect_level--; 437 438 uint32_t fblock; 439 int rc = ext4_filesystem_get_inode_data_block_index(inode_ref, 440 next_block, &fblock); 441 if (rc != EOK) 442 return rc; 443 444 rc = block_get(&tmp_block, inode_ref->fs->device, fblock, 445 BLOCK_FLAGS_NONE); 446 if (rc != EOK) 447 return rc; 448 437 449 entries = ((ext4_directory_dx_node_t *) tmp_block->data)->entries; 438 450 limit = ext4_directory_dx_countlimit_get_limit( 439 (ext4_directory_dx_countlimit_t *)entries);440 441 uint16_t entry_space = ext4_superblock_get_block_size(inode_ref->fs->superblock) 442 - sizeof(ext4_directory_dx_dot_entry_t); 443 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);444 445 451 (ext4_directory_dx_countlimit_t *) entries); 452 453 uint16_t entry_space = 454 ext4_superblock_get_block_size(inode_ref->fs->superblock) - 455 sizeof(ext4_directory_dx_dot_entry_t); 456 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t); 457 446 458 if (limit != entry_space) { 447 459 block_put(tmp_block); 448 460 return EXT4_ERR_BAD_DX_DIR; 449 461 } 450 462 451 463 ++tmp_dx_block; 452 464 } 453 465 454 466 /* Unreachable */ 455 467 return EOK; 456 468 } 457 469 458 459 470 /** Check if the the next block would be checked during entry search. 460 471 * 461 * @param inode_ref directory i-node 462 * @param hash hash value to check 463 * @param dx_block current block 464 * @param dx_blocks aray with path from root to leaf node 465 * @return error code 466 */ 467 static int ext4_directory_dx_next_block(ext4_inode_ref_t *inode_ref, uint32_t hash, 468 ext4_directory_dx_block_t *dx_block, ext4_directory_dx_block_t *dx_blocks) 469 { 470 int rc; 471 472 uint32_t num_handles = 0; 473 ext4_directory_dx_block_t *p = dx_block; 474 475 /* Try to find data block with next bunch of entries */ 476 while (1) { 477 478 p->position++; 479 uint16_t count = ext4_directory_dx_countlimit_get_count( 480 (ext4_directory_dx_countlimit_t *)p->entries); 481 482 if (p->position < p->entries + count) { 483 break; 484 } 485 486 if (p == dx_blocks) { 487 return 0; 488 } 489 490 num_handles++; 491 p--; 492 } 493 494 /* Check hash collision (if not occured - no next block cannot be used) */ 495 uint32_t current_hash = ext4_directory_dx_entry_get_hash(p->position); 496 if ((hash & 1) == 0) { 497 if ((current_hash & ~1) != hash) { 498 return 0; 499 } 500 } 501 502 /* Fill new path */ 503 while (num_handles--) { 504 505 uint32_t block_idx = ext4_directory_dx_entry_get_block(p->position); 506 uint32_t block_addr; 507 rc = ext4_filesystem_get_inode_data_block_index(inode_ref, block_idx, &block_addr); 508 if (rc != EOK) { 509 return rc; 510 } 511 512 block_t *block; 513 rc = block_get(&block, inode_ref->fs->device, block_addr, BLOCK_FLAGS_NONE); 514 if (rc != EOK) { 515 return rc; 516 } 517 518 p++; 519 520 /* Don't forget to put old block (prevent memory leak) */ 521 block_put(p->block); 522 523 p->block = block; 524 p->entries = ((ext4_directory_dx_node_t *) block->data)->entries; 525 p->position = p->entries; 526 } 527 528 return 1; 529 472 * @param inode_ref Directory i-node 473 * @param hash Hash value to check 474 * @param dx_block Current block 475 * @param dx_blocks Array with path from root to leaf node 476 * 477 * @return Error code 478 * 479 */ 480 static int ext4_directory_dx_next_block(ext4_inode_ref_t *inode_ref, 481 uint32_t hash, ext4_directory_dx_block_t *dx_block, 482 ext4_directory_dx_block_t *dx_blocks) 483 { 484 uint32_t num_handles = 0; 485 ext4_directory_dx_block_t *p = dx_block; 486 487 /* Try to find data block with next bunch of entries */ 488 while (true) { 489 p->position++; 490 uint16_t count = ext4_directory_dx_countlimit_get_count( 491 (ext4_directory_dx_countlimit_t *) p->entries); 492 493 if (p->position < p->entries + count) 494 break; 495 496 if (p == dx_blocks) 497 return EOK; 498 499 num_handles++; 500 p--; 501 } 502 503 /* Check hash collision (if not occured - no next block cannot be used) */ 504 uint32_t current_hash = ext4_directory_dx_entry_get_hash(p->position); 505 if ((hash & 1) == 0) { 506 if ((current_hash & ~1) != hash) 507 return 0; 508 } 509 510 /* Fill new path */ 511 while (num_handles--) { 512 uint32_t block_idx = 513 ext4_directory_dx_entry_get_block(p->position); 514 uint32_t block_addr; 515 516 int rc = ext4_filesystem_get_inode_data_block_index(inode_ref, 517 block_idx, &block_addr); 518 if (rc != EOK) 519 return rc; 520 521 block_t *block; 522 rc = block_get(&block, inode_ref->fs->device, block_addr, BLOCK_FLAGS_NONE); 523 if (rc != EOK) 524 return rc; 525 526 p++; 527 528 /* Don't forget to put old block (prevent memory leak) */ 529 block_put(p->block); 530 531 p->block = block; 532 p->entries = ((ext4_directory_dx_node_t *) block->data)->entries; 533 p->position = p->entries; 534 } 535 536 return ENOENT; 530 537 } 531 538 532 539 /** Try to find directory entry using directory index. 533 540 * 534 * @param result output value - if entry will be found, 535 * than will be passed through this parameter 536 * @param inode_ref directory i-node 537 * @param name_len length of name to be found 538 * @param name name to be found 539 * @return error code 541 * @param result Output value - if entry will be found, 542 * than will be passed through this parameter 543 * @param inode_ref Directory i-node 544 * @param name_len Length of name to be found 545 * @param name Name to be found 546 * 547 * @return Error code 548 * 540 549 */ 541 550 int ext4_directory_dx_find_entry(ext4_directory_search_result_t *result, 542 ext4_inode_ref_t *inode_ref, size_t name_len, const char *name) 543 { 544 int rc; 545 551 ext4_inode_ref_t *inode_ref, size_t name_len, const char *name) 552 { 546 553 /* Load direct block 0 (index root) */ 547 554 uint32_t root_block_addr; 548 rc = ext4_filesystem_get_inode_data_block_index(inode_ref, 0, &root_block_addr);549 if (rc != EOK) {550 return rc;551 }552 555 int rc = ext4_filesystem_get_inode_data_block_index(inode_ref, 0, 556 &root_block_addr); 557 if (rc != EOK) 558 return rc; 559 553 560 ext4_filesystem_t *fs = inode_ref->fs; 554 561 555 562 block_t *root_block; 556 rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE);557 if (rc != EOK) {558 return rc;559 }560 563 rc = block_get(&root_block, fs->device, root_block_addr, 564 BLOCK_FLAGS_NONE); 565 if (rc != EOK) 566 return rc; 567 561 568 /* Initialize hash info (compute hash value) */ 562 569 ext4_hash_info_t hinfo; 563 rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, name_len, name); 570 rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, 571 name_len, name); 564 572 if (rc != EOK) { 565 573 block_put(root_block); 566 574 return EXT4_ERR_BAD_DX_DIR; 567 575 } 568 569 /* Hardcoded number 2 means maximum height of index tree, specified in linux driver */ 576 577 /* 578 * Hardcoded number 2 means maximum height of index tree, 579 * specified in the Linux driver. 580 */ 570 581 ext4_directory_dx_block_t dx_blocks[2]; 571 ext4_directory_dx_block_t *dx_block, *tmp; 572 rc = ext4_directory_dx_get_leaf(&hinfo, inode_ref, root_block, &dx_block, dx_blocks); 582 ext4_directory_dx_block_t *dx_block; 583 ext4_directory_dx_block_t *tmp; 584 585 rc = ext4_directory_dx_get_leaf(&hinfo, inode_ref, root_block, 586 &dx_block, dx_blocks); 573 587 if (rc != EOK) { 574 588 block_put(root_block); 575 589 return EXT4_ERR_BAD_DX_DIR; 576 590 } 577 591 578 592 do { 579 593 /* Load leaf block */ 580 uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position); 594 uint32_t leaf_block_idx = 595 ext4_directory_dx_entry_get_block(dx_block->position); 581 596 uint32_t leaf_block_addr; 582 rc = ext4_filesystem_get_inode_data_block_index(inode_ref, leaf_block_idx, &leaf_block_addr); 583 if (rc != EOK) { 584 goto cleanup; 585 } 586 587 block_t *leaf_block; 588 rc = block_get(&leaf_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE); 589 if (rc != EOK) { 597 598 rc = ext4_filesystem_get_inode_data_block_index(inode_ref, 599 leaf_block_idx, &leaf_block_addr); 600 if (rc != EOK) 590 601 goto cleanup; 591 } 592 602 603 block_t *leaf_block; 604 rc = block_get(&leaf_block, fs->device, leaf_block_addr, 605 BLOCK_FLAGS_NONE); 606 if (rc != EOK) 607 goto cleanup; 608 593 609 /* Linear search inside block */ 594 610 ext4_directory_entry_ll_t *res_dentry; 595 rc = ext4_directory_find_in_block(leaf_block, fs->superblock, name_len, name, &res_dentry); 596 611 rc = ext4_directory_find_in_block(leaf_block, fs->superblock, 612 name_len, name, &res_dentry); 613 597 614 /* Found => return it */ 598 615 if (rc == EOK) { … … 601 618 goto cleanup; 602 619 } 603 620 604 621 /* Not found, leave untouched */ 605 622 block_put(leaf_block); 606 607 if (rc != ENOENT) {623 624 if (rc != ENOENT) 608 625 goto cleanup; 609 } 610 626 611 627 /* check if the next block could be checked */ 612 rc = ext4_directory_dx_next_block(inode_ref, hinfo.hash, dx_block, &dx_blocks[0]); 613 if (rc < 0) { 628 rc = ext4_directory_dx_next_block(inode_ref, hinfo.hash, 629 dx_block, &dx_blocks[0]); 630 if (rc < 0) 614 631 goto cleanup; 615 } 616 617 } while (rc == 1); 618 632 } while (rc == ENOENT); 633 619 634 /* Entry not found */ 620 635 rc = ENOENT; 621 636 622 637 cleanup: 623 624 638 /* The whole path must be released (preventing memory leak) */ 625 639 tmp = dx_blocks; 640 626 641 while (tmp <= dx_block) { 627 642 block_put(tmp->block); 628 643 ++tmp; 629 644 } 645 630 646 return rc; 631 647 } … … 635 651 * It can compare two entries by hash value. 636 652 * 637 * @param arg1 first entry 638 * @param arg2 second entry 639 * @param dummy unused parameter, can be NULL 640 * @return classic compare result (0: equal, -1: arg1 < arg2, 1: arg1 > arg2) 653 * @param arg1 First entry 654 * @param arg2 Second entry 655 * @param dummy Unused parameter, can be NULL 656 * 657 * @return Classic compare result 658 * (0: equal, -1: arg1 < arg2, 1: arg1 > arg2) 659 * 641 660 */ 642 661 static int ext4_directory_dx_entry_comparator(void *arg1, void *arg2, void *dummy) … … 644 663 ext4_dx_sort_entry_t *entry1 = arg1; 645 664 ext4_dx_sort_entry_t *entry2 = arg2; 646 647 if (entry1->hash == entry2->hash) {665 666 if (entry1->hash == entry2->hash) 648 667 return 0; 649 } 650 651 if (entry1->hash < entry2->hash) { 668 669 if (entry1->hash < entry2->hash) 652 670 return -1; 653 } else {671 else 654 672 return 1; 655 }656 657 673 } 658 674 … … 661 677 * Note that space for new entry must be checked by caller. 662 678 * 663 * @param index_block block where to insert new entry664 * @param hash hash value covered by child node665 * @param iblock logical number of child block679 * @param index_block Block where to insert new entry 680 * @param hash Hash value covered by child node 681 * @param iblock Logical number of child block 666 682 * 667 683 */ 668 684 static void ext4_directory_dx_insert_entry( 669 685 ext4_directory_dx_block_t *index_block, uint32_t hash, uint32_t iblock) 670 686 { 671 687 ext4_directory_dx_entry_t *old_index_entry = index_block->position; 672 688 ext4_directory_dx_entry_t *new_index_entry = old_index_entry + 1; 673 689 674 690 ext4_directory_dx_countlimit_t *countlimit = 675 (ext4_directory_dx_countlimit_t *)index_block->entries;691 (ext4_directory_dx_countlimit_t *) index_block->entries; 676 692 uint32_t count = ext4_directory_dx_countlimit_get_count(countlimit); 677 693 678 694 ext4_directory_dx_entry_t *start_index = index_block->entries; 679 size_t bytes = (void *) (start_index + count) - (void *)(new_index_entry);680 695 size_t bytes = (void *) (start_index + count) - (void *) (new_index_entry); 696 681 697 memmove(new_index_entry + 1, new_index_entry, bytes); 682 698 683 699 ext4_directory_dx_entry_set_block(new_index_entry, iblock); 684 700 ext4_directory_dx_entry_set_hash(new_index_entry, hash); 685 701 686 702 ext4_directory_dx_countlimit_set_count(countlimit, count + 1); 687 703 688 704 index_block->block->dirty = true; 689 705 } … … 691 707 /** Split directory entries to two parts preventing node overflow. 692 708 * 693 * @param inode_ref directory i-node 694 * @param hinfo hash info 695 * @param old_data_block block with data to be split 696 * @param index_block block where index entries are located 697 * @param new_data_block output value for newly allocated data block 709 * @param inode_ref Directory i-node 710 * @param hinfo Hash info 711 * @param old_data_block Block with data to be split 712 * @param index_block Block where index entries are located 713 * @param new_data_block Output value for newly allocated data block 714 * 698 715 */ 699 716 static int ext4_directory_dx_split_data(ext4_inode_ref_t *inode_ref, 700 701 717 ext4_hash_info_t *hinfo, block_t *old_data_block, 718 ext4_directory_dx_block_t *index_block, block_t **new_data_block) 702 719 { 703 720 int rc = EOK; 704 721 705 722 /* Allocate buffer for directory entries */ 706 723 uint32_t block_size = 707 724 ext4_superblock_get_block_size(inode_ref->fs->superblock); 708 725 void *entry_buffer = malloc(block_size); 709 if (entry_buffer == NULL) {726 if (entry_buffer == NULL) 710 727 return ENOMEM; 711 } 712 728 713 729 /* dot entry has the smallest size available */ 714 uint32_t max_entry_count = block_size / sizeof(ext4_directory_dx_dot_entry_t); 715 730 uint32_t max_entry_count = 731 block_size / sizeof(ext4_directory_dx_dot_entry_t); 732 716 733 /* Allocate sort entry */ 717 ext4_dx_sort_entry_t *sort_array = malloc(max_entry_count * sizeof(ext4_dx_sort_entry_t)); 734 ext4_dx_sort_entry_t *sort_array = 735 malloc(max_entry_count * sizeof(ext4_dx_sort_entry_t)); 718 736 if (sort_array == NULL) { 719 737 free(entry_buffer); 720 738 return ENOMEM; 721 739 } 722 740 723 741 uint32_t idx = 0; 724 742 uint32_t real_size = 0; 725 743 726 744 /* Initialize hinfo */ 727 745 ext4_hash_info_t tmp_hinfo; 728 746 memcpy(&tmp_hinfo, hinfo, sizeof(ext4_hash_info_t)); 729 747 730 748 /* Load all valid entries to the buffer */ 731 749 ext4_directory_entry_ll_t *dentry = old_data_block->data; 732 750 void *entry_buffer_ptr = entry_buffer; 733 751 while ((void *)dentry < old_data_block->data + block_size) { 734 735 752 /* Read only valid entries */ 736 753 if (ext4_directory_entry_ll_get_inode(dentry) != 0) { 737 738 754 uint8_t len = ext4_directory_entry_ll_get_name_length( 739 740 ext4_hash_string(&tmp_hinfo, len, (char *) dentry->name);741 755 inode_ref->fs->superblock, dentry); 756 ext4_hash_string(&tmp_hinfo, len, (char *) dentry->name); 757 742 758 uint32_t rec_len = 8 + len; 743 744 if ((rec_len % 4) != 0) {759 760 if ((rec_len % 4) != 0) 745 761 rec_len += 4 - (rec_len % 4); 746 } 747 762 748 763 memcpy(entry_buffer_ptr, dentry, rec_len); 749 764 750 765 sort_array[idx].dentry = entry_buffer_ptr; 751 766 sort_array[idx].rec_len = rec_len; 752 767 sort_array[idx].hash = tmp_hinfo.hash; 753 768 754 769 entry_buffer_ptr += rec_len; 755 770 real_size += rec_len; 756 771 idx++; 757 772 } 758 759 dentry = (void *)dentry + ext4_directory_entry_ll_get_entry_length(dentry); 760 } 761 773 774 dentry = (void *) dentry + 775 ext4_directory_entry_ll_get_entry_length(dentry); 776 } 777 762 778 /* Sort all entries */ 763 779 qsort(sort_array, idx, sizeof(ext4_dx_sort_entry_t), 764 765 780 ext4_directory_dx_entry_comparator, NULL); 781 766 782 /* Allocate new block for store the second part of entries */ 767 783 uint32_t new_fblock; 768 784 uint32_t new_iblock; 769 rc = ext4_filesystem_append_inode_block(inode_ref, &new_fblock, &new_iblock); 785 rc = ext4_filesystem_append_inode_block(inode_ref, &new_fblock, 786 &new_iblock); 770 787 if (rc != EOK) { 771 788 free(sort_array); … … 773 790 return rc; 774 791 } 775 792 776 793 /* Load new block */ 777 794 block_t *new_data_block_tmp; 778 795 rc = block_get(&new_data_block_tmp, inode_ref->fs->device, 779 796 new_fblock, BLOCK_FLAGS_NOREAD); 780 797 if (rc != EOK) { 781 798 free(sort_array); … … 783 800 return rc; 784 801 } 785 786 /* Distribute entries to two blocks (by size) 802 803 /* 804 * Distribute entries to two blocks (by size) 787 805 * - compute the half 788 806 */ … … 796 814 break; 797 815 } 798 816 799 817 current_size += sort_array[i].rec_len; 800 818 } 801 819 802 820 /* Check hash collision */ 803 821 uint32_t continued = 0; 804 if (new_hash == sort_array[mid-1].hash) {822 if (new_hash == sort_array[mid-1].hash) 805 823 continued = 1; 806 } 807 824 808 825 uint32_t offset = 0; 809 826 void *ptr; 810 827 811 828 /* First part - to the old block */ 812 829 for (uint32_t i = 0; i < mid; ++i) { 813 830 ptr = old_data_block->data + offset; 814 831 memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len); 815 832 816 833 ext4_directory_entry_ll_t *tmp = ptr; 817 if (i < (mid - 1)) { 818 ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len); 819 } else { 820 ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset); 821 } 822 834 if (i < (mid - 1)) 835 ext4_directory_entry_ll_set_entry_length(tmp, 836 sort_array[i].rec_len); 837 else 838 ext4_directory_entry_ll_set_entry_length(tmp, 839 block_size - offset); 840 823 841 offset += sort_array[i].rec_len; 824 842 } 825 843 826 844 /* Second part - to the new block */ 827 845 offset = 0; … … 829 847 ptr = new_data_block_tmp->data + offset; 830 848 memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len); 831 849 832 850 ext4_directory_entry_ll_t *tmp = ptr; 833 if (i < (idx - 1)) { 834 ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len); 835 } else { 836 ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset); 837 } 838 851 if (i < (idx - 1)) 852 ext4_directory_entry_ll_set_entry_length(tmp, 853 sort_array[i].rec_len); 854 else 855 ext4_directory_entry_ll_set_entry_length(tmp, 856 block_size - offset); 857 839 858 offset += sort_array[i].rec_len; 840 859 } 841 860 842 861 /* Do some steps to finish operation */ 843 862 old_data_block->dirty = true; 844 863 new_data_block_tmp->dirty = true; 845 864 846 865 free(sort_array); 847 866 free(entry_buffer); 848 849 ext4_directory_dx_insert_entry(index_block, new_hash + continued, new_iblock); 850 867 868 ext4_directory_dx_insert_entry(index_block, new_hash + continued, 869 new_iblock); 870 851 871 *new_data_block = new_data_block_tmp; 852 872 853 873 return EOK; 854 874 } … … 856 876 /** Split index node and maybe some parent nodes in the tree hierarchy. 857 877 * 858 * @param inode_ref directory i-node 859 * @param dx_blocks array with path from root to leaf node 860 * @param dx_block leaf block to be split if needed 861 * @return error code 878 * @param inode_ref Directory i-node 879 * @param dx_blocks Array with path from root to leaf node 880 * @param dx_block Leaf block to be split if needed 881 * 882 * @return Error code 883 * 862 884 */ 863 885 static int ext4_directory_dx_split_index(ext4_inode_ref_t *inode_ref, 864 886 ext4_directory_dx_block_t *dx_blocks, ext4_directory_dx_block_t *dx_block) 865 887 { 866 int rc;867 868 888 ext4_directory_dx_entry_t *entries; 869 if (dx_block == dx_blocks) { 870 entries = ((ext4_directory_dx_root_t *) dx_block->block->data)->entries; 871 } else { 872 entries = ((ext4_directory_dx_node_t *) dx_block->block->data)->entries; 873 } 874 889 if (dx_block == dx_blocks) 890 entries = 891 ((ext4_directory_dx_root_t *) dx_block->block->data)->entries; 892 else 893 entries = 894 ((ext4_directory_dx_node_t *) dx_block->block->data)->entries; 895 875 896 ext4_directory_dx_countlimit_t *countlimit = 876 (ext4_directory_dx_countlimit_t *)entries; 877 uint16_t leaf_limit = ext4_directory_dx_countlimit_get_limit(countlimit); 878 uint16_t leaf_count = ext4_directory_dx_countlimit_get_count(countlimit); 879 897 (ext4_directory_dx_countlimit_t *) entries; 898 899 uint16_t leaf_limit = 900 ext4_directory_dx_countlimit_get_limit(countlimit); 901 uint16_t leaf_count = 902 ext4_directory_dx_countlimit_get_count(countlimit); 903 880 904 /* Check if is necessary to split index block */ 881 905 if (leaf_limit == leaf_count) { 882 883 unsigned int levels = dx_block - dx_blocks; 884 906 size_t levels = dx_block - dx_blocks; 907 885 908 ext4_directory_dx_entry_t *root_entries = 886 ((ext4_directory_dx_root_t *)dx_blocks[0].block->data)->entries;887 909 ((ext4_directory_dx_root_t *) dx_blocks[0].block->data)->entries; 910 888 911 ext4_directory_dx_countlimit_t *root_countlimit = 889 (ext4_directory_dx_countlimit_t *)root_entries;912 (ext4_directory_dx_countlimit_t *) root_entries; 890 913 uint16_t root_limit = 891 914 ext4_directory_dx_countlimit_get_limit(root_countlimit); 892 915 uint16_t root_count = 893 894 916 ext4_directory_dx_countlimit_get_count(root_countlimit); 917 895 918 /* Linux limitation */ 896 if ((levels > 0) && (root_limit == root_count)) {919 if ((levels > 0) && (root_limit == root_count)) 897 920 return ENOSPC; 898 } 899 921 900 922 /* Add new block to directory */ 901 923 uint32_t new_fblock; 902 924 uint32_t new_iblock; 903 rc = ext4_filesystem_append_inode_block(904 inode_ref,&new_fblock, &new_iblock);905 if (rc != EOK) {925 int rc = ext4_filesystem_append_inode_block(inode_ref, 926 &new_fblock, &new_iblock); 927 if (rc != EOK) 906 928 return rc; 907 } 908 929 909 930 /* load new block */ 910 block_t * 931 block_t *new_block; 911 932 rc = block_get(&new_block, inode_ref->fs->device, 912 913 if (rc != EOK) {933 new_fblock, BLOCK_FLAGS_NOREAD); 934 if (rc != EOK) 914 935 return rc; 915 } 916 936 917 937 ext4_directory_dx_node_t *new_node = new_block->data; 918 938 ext4_directory_dx_entry_t *new_entries = new_node->entries; 919 920 uint32_t block_size = ext4_superblock_get_block_size(921 922 939 940 uint32_t block_size = 941 ext4_superblock_get_block_size(inode_ref->fs->superblock); 942 923 943 /* Split leaf node */ 924 944 if (levels > 0) { 925 926 945 uint32_t count_left = leaf_count / 2; 927 946 uint32_t count_right = leaf_count - count_left; 928 947 uint32_t hash_right = 929 930 948 ext4_directory_dx_entry_get_hash(entries + count_left); 949 931 950 /* Copy data to new node */ 932 951 memcpy((void *) new_entries, (void *) (entries + count_left), 933 934 952 count_right * sizeof(ext4_directory_dx_entry_t)); 953 935 954 /* Initialize new node */ 936 955 ext4_directory_dx_countlimit_t *left_countlimit = 937 (ext4_directory_dx_countlimit_t *)entries;956 (ext4_directory_dx_countlimit_t *) entries; 938 957 ext4_directory_dx_countlimit_t *right_countlimit = 939 (ext4_directory_dx_countlimit_t *)new_entries;940 958 (ext4_directory_dx_countlimit_t *) new_entries; 959 941 960 ext4_directory_dx_countlimit_set_count(left_countlimit, count_left); 942 961 ext4_directory_dx_countlimit_set_count(right_countlimit, count_right); 943 944 uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t); 945 uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t); 962 963 uint32_t entry_space = 964 block_size - sizeof(ext4_fake_directory_entry_t); 965 uint32_t node_limit = 966 entry_space / sizeof(ext4_directory_dx_entry_t); 946 967 ext4_directory_dx_countlimit_set_limit(right_countlimit, node_limit); 947 968 948 969 /* Which index block is target for new entry */ 949 970 uint32_t position_index = (dx_block->position - dx_block->entries); 950 971 if (position_index >= count_left) { 951 952 972 dx_block->block->dirty = true; 953 973 954 974 block_t *block_tmp = dx_block->block; 955 975 dx_block->block = new_block; 956 dx_block->position = new_entries + position_index - count_left; 976 dx_block->position = 977 new_entries + position_index - count_left; 957 978 dx_block->entries = new_entries; 958 979 959 980 new_block = block_tmp; 960 961 981 } 962 982 963 983 /* Finally insert new entry */ 964 984 ext4_directory_dx_insert_entry(dx_blocks, hash_right, new_iblock); 965 985 966 986 return block_put(new_block); 967 968 987 } else { 969 970 988 /* Create second level index */ 971 989 972 990 /* Copy data from root to child block */ 973 991 memcpy((void *) new_entries, (void *) entries, 974 975 992 leaf_count * sizeof(ext4_directory_dx_entry_t)); 993 976 994 ext4_directory_dx_countlimit_t *new_countlimit = 977 (ext4_directory_dx_countlimit_t *)new_entries; 978 979 uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t); 980 uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t); 995 (ext4_directory_dx_countlimit_t *) new_entries; 996 997 uint32_t entry_space = 998 block_size - sizeof(ext4_fake_directory_entry_t); 999 uint32_t node_limit = 1000 entry_space / sizeof(ext4_directory_dx_entry_t); 981 1001 ext4_directory_dx_countlimit_set_limit(new_countlimit, node_limit); 982 1002 983 1003 /* Set values in root node */ 984 1004 ext4_directory_dx_countlimit_t *new_root_countlimit = 985 (ext4_directory_dx_countlimit_t *)entries;986 1005 (ext4_directory_dx_countlimit_t *) entries; 1006 987 1007 ext4_directory_dx_countlimit_set_count(new_root_countlimit, 1); 988 1008 ext4_directory_dx_entry_set_block(entries, new_iblock); 989 990 ((ext4_directory_dx_root_t *)dx_blocks[0].block->data)->info.indirect_levels = 1; 991 1009 1010 ((ext4_directory_dx_root_t *) 1011 dx_blocks[0].block->data)->info.indirect_levels = 1; 1012 992 1013 /* Add new entry to the path */ 993 1014 dx_block = dx_blocks + 1; … … 996 1017 dx_block->block = new_block; 997 1018 } 998 999 } 1000 1019 } 1020 1001 1021 return EOK; 1002 1022 } … … 1004 1024 /** Add new entry to indexed directory 1005 1025 * 1006 * @param parent directory i-node 1007 * @param child i-node to be referenced from directory entry 1008 * @param name name of new directory entry 1009 * @return error code 1026 * @param parent Directory i-node 1027 * @param child I-node to be referenced from directory entry 1028 * @param name Name of new directory entry 1029 * 1030 * @return Error code 1031 * 1010 1032 */ 1011 1033 int ext4_directory_dx_add_entry(ext4_inode_ref_t *parent, 1012 ext4_inode_ref_t *child, const char *name) 1013 { 1014 int rc = EOK; 1034 ext4_inode_ref_t *child, const char *name) 1035 { 1015 1036 int rc2 = EOK; 1016 1017 /* get direct block 0 (index root) */1037 1038 /* Get direct block 0 (index root) */ 1018 1039 uint32_t root_block_addr; 1019 rc = ext4_filesystem_get_inode_data_block_index(parent, 0, &root_block_addr);1020 if (rc != EOK) {1021 return rc;1022 }1023 1040 int rc = ext4_filesystem_get_inode_data_block_index(parent, 0, 1041 &root_block_addr); 1042 if (rc != EOK) 1043 return rc; 1044 1024 1045 ext4_filesystem_t *fs = parent->fs; 1025 1046 1026 1047 block_t *root_block; 1027 rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE);1028 if (rc != EOK) {1029 return rc;1030 }1031 1048 rc = block_get(&root_block, fs->device, root_block_addr, 1049 BLOCK_FLAGS_NONE); 1050 if (rc != EOK) 1051 return rc; 1052 1032 1053 /* Initialize hinfo structure (mainly compute hash) */ 1033 uint32_t name_len = str len(name);1054 uint32_t name_len = str_size(name); 1034 1055 ext4_hash_info_t hinfo; 1035 rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, name_len, name); 1056 rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, 1057 name_len, name); 1036 1058 if (rc != EOK) { 1037 1059 block_put(root_block); 1038 1060 return EXT4_ERR_BAD_DX_DIR; 1039 1061 } 1040 1041 /* Hardcoded number 2 means maximum height of index tree defined in linux */ 1062 1063 /* 1064 * Hardcoded number 2 means maximum height of index 1065 * tree defined in Linux. 1066 */ 1042 1067 ext4_directory_dx_block_t dx_blocks[2]; 1043 ext4_directory_dx_block_t *dx_block, *dx_it; 1044 rc = ext4_directory_dx_get_leaf(&hinfo, parent, root_block, &dx_block, dx_blocks); 1068 ext4_directory_dx_block_t *dx_block; 1069 ext4_directory_dx_block_t *dx_it; 1070 1071 rc = ext4_directory_dx_get_leaf(&hinfo, parent, root_block, 1072 &dx_block, dx_blocks); 1045 1073 if (rc != EOK) { 1046 1074 rc = EXT4_ERR_BAD_DX_DIR; 1047 1075 goto release_index; 1048 1076 } 1049 1050 1077 1051 1078 /* Try to insert to existing data block */ 1052 uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position); 1079 uint32_t leaf_block_idx = 1080 ext4_directory_dx_entry_get_block(dx_block->position); 1053 1081 uint32_t leaf_block_addr; 1054 rc = ext4_filesystem_get_inode_data_block_index(parent, leaf_block_idx, &leaf_block_addr); 1055 if (rc != EOK) { 1056 goto release_index; 1057 } 1058 1059 1060 block_t *target_block; 1061 rc = block_get(&target_block, fs->device, leaf_block_addr,BLOCK_FLAGS_NONE);1062 if (rc != EOK) { 1063 1064 } 1065 1066 /* Check if insert operation passed */ 1067 rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child,name, name_len);1068 if (rc == EOK) { 1069 1070 } 1071 1072 /* Check if there is needed to split index node1073 1074 1082 rc = ext4_filesystem_get_inode_data_block_index(parent, leaf_block_idx, 1083 &leaf_block_addr); 1084 if (rc != EOK) 1085 goto release_index; 1086 1087 block_t *target_block; 1088 rc = block_get(&target_block, fs->device, leaf_block_addr, 1089 BLOCK_FLAGS_NONE); 1090 if (rc != EOK) 1091 goto release_index; 1092 1093 /* Check if insert operation passed */ 1094 rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child, 1095 name, name_len); 1096 if (rc == EOK) 1097 goto release_target_index; 1098 1099 /* 1100 * Check if there is needed to split index node 1101 * (and recursively also parent nodes) 1102 */ 1075 1103 rc = ext4_directory_dx_split_index(parent, dx_blocks, dx_block); 1076 if (rc != EOK) {1104 if (rc != EOK) 1077 1105 goto release_target_index; 1078 } 1079 1106 1080 1107 /* Split entries to two blocks (includes sorting by hash value) */ 1081 1108 block_t *new_block = NULL; 1082 rc = ext4_directory_dx_split_data(parent, &hinfo, target_block, dx_block, &new_block); 1109 rc = ext4_directory_dx_split_data(parent, &hinfo, target_block, 1110 dx_block, &new_block); 1083 1111 if (rc != EOK) { 1084 1112 rc2 = rc; 1085 1113 goto release_target_index; 1086 1114 } 1087 1115 1088 1116 /* Where to save new entry */ 1089 uint32_t new_block_hash = ext4_directory_dx_entry_get_hash(dx_block->position + 1); 1090 if (hinfo.hash >= new_block_hash) { 1091 rc = ext4_directory_try_insert_entry(fs->superblock, new_block, child, name, name_len); 1092 } else { 1093 rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child, name, name_len); 1094 } 1095 1117 uint32_t new_block_hash = 1118 ext4_directory_dx_entry_get_hash(dx_block->position + 1); 1119 if (hinfo.hash >= new_block_hash) 1120 rc = ext4_directory_try_insert_entry(fs->superblock, new_block, 1121 child, name, name_len); 1122 else 1123 rc = ext4_directory_try_insert_entry(fs->superblock, target_block, 1124 child, name, name_len); 1125 1096 1126 /* Cleanup */ 1097 1127 rc = block_put(new_block); 1098 if (rc != EOK) { 1099 return rc; 1100 } 1101 1128 if (rc != EOK) 1129 return rc; 1130 1102 1131 /* Cleanup operations */ 1103 1132 1104 1133 release_target_index: 1105 1106 1134 rc2 = rc; 1107 1135 1108 1136 rc = block_put(target_block); 1109 if (rc != EOK) { 1110 return rc; 1111 } 1112 1137 if (rc != EOK) 1138 return rc; 1139 1113 1140 release_index: 1114 1115 if (rc != EOK) { 1141 if (rc != EOK) 1116 1142 rc2 = rc; 1117 } 1118 1143 1119 1144 dx_it = dx_blocks; 1120 1145 1121 1146 while (dx_it <= dx_block) { 1122 1147 rc = block_put(dx_it->block); 1123 if (rc != EOK) {1148 if (rc != EOK) 1124 1149 return rc; 1125 }1150 1126 1151 dx_it++; 1127 1152 } 1128 1153 1129 1154 return rc2; 1130 1155 } 1131 1132 1156 1133 1157 /** 1134 1158 * @} 1135 */ 1159 */
Note:
See TracChangeset
for help on using the changeset viewer.