Changeset beb9336 in mainline for uspace/lib/ext4/libext4_extent.c
- Timestamp:
- 2012-08-24T14:07:52Z (12 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 041ab64
- Parents:
- bd29f9c9 (diff), db81577 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/ext4/libext4_extent.c
rbd29f9c9 rbeb9336 29 29 /** @addtogroup libext4 30 30 * @{ 31 */ 32 31 */ 33 32 /** 34 * @file 35 * @brief 33 * @file libext4_extent.c 34 * @brief Ext4 extent structures operations. 36 35 */ 37 36 … … 43 42 /** Get logical number of the block covered by extent. 44 43 * 45 * @param extent extent to load number from 46 * @return logical number of the first block covered by extent 44 * @param extent Extent to load number from 45 * 46 * @return Logical number of the first block covered by extent 47 * 47 48 */ 48 49 uint32_t ext4_extent_get_first_block(ext4_extent_t *extent) … … 53 54 /** Set logical number of the first block covered by extent. 54 55 * 55 * @param extent extent to set number to 56 * @param iblock logical number of the first block covered by extent 56 * @param extent Extent to set number to 57 * @param iblock Logical number of the first block covered by extent 58 * 57 59 */ 58 60 void ext4_extent_set_first_block(ext4_extent_t *extent, uint32_t iblock) … … 63 65 /** Get number of blocks covered by extent. 64 66 * 65 * @param extent extent to load count from 66 * @return number of blocks covered by extent 67 * @param extent Extent to load count from 68 * 69 * @return Number of blocks covered by extent 70 * 67 71 */ 68 72 uint16_t ext4_extent_get_block_count(ext4_extent_t *extent) … … 73 77 /** Set number of blocks covered by extent. 74 78 * 75 * @param extent extent to load count from 76 * @param count number of blocks covered by extent 79 * @param extent Extent to load count from 80 * @param count Number of blocks covered by extent 81 * 77 82 */ 78 83 void ext4_extent_set_block_count(ext4_extent_t *extent, uint16_t count) … … 83 88 /** Get physical number of the first block covered by extent. 84 89 * 85 * @param extent extent to load number 86 * @return physical number of the first block covered by extent 90 * @param extent Extent to load number 91 * 92 * @return Physical number of the first block covered by extent 93 * 87 94 */ 88 95 uint64_t ext4_extent_get_start(ext4_extent_t *extent) 89 96 { 90 97 return ((uint64_t)uint16_t_le2host(extent->start_hi)) << 32 | 91 98 ((uint64_t)uint32_t_le2host(extent->start_lo)); 92 99 } 93 100 94 101 /** Set physical number of the first block covered by extent. 95 102 * 96 * @param extent extent to load number 97 * @param fblock physical number of the first block covered by extent 103 * @param extent Extent to load number 104 * @param fblock Physical number of the first block covered by extent 105 * 98 106 */ 99 107 void ext4_extent_set_start(ext4_extent_t *extent, uint64_t fblock) … … 105 113 /** Get logical number of the block covered by extent index. 106 114 * 107 * @param index extent index to load number from 108 * @return logical number of the first block covered by extent index 115 * @param index Extent index to load number from 116 * 117 * @return Logical number of the first block covered by extent index 118 * 109 119 */ 110 120 uint32_t ext4_extent_index_get_first_block(ext4_extent_index_t *index) … … 115 125 /** Set logical number of the block covered by extent index. 116 126 * 117 * @param index extent index to set number to 118 * @param iblock logical number of the first block covered by extent index 127 * @param index Extent index to set number to 128 * @param iblock Logical number of the first block covered by extent index 129 * 119 130 */ 120 131 void ext4_extent_index_set_first_block(ext4_extent_index_t *index, 121 132 uint32_t iblock) 122 133 { 123 134 index->first_block = host2uint32_t_le(iblock); … … 126 137 /** Get physical number of block where the child node is located. 127 138 * 128 * @param index extent index to load number from 129 * @return physical number of the block with child node 139 * @param index Extent index to load number from 140 * 141 * @return Physical number of the block with child node 142 * 130 143 */ 131 144 uint64_t ext4_extent_index_get_leaf(ext4_extent_index_t *index) 132 145 { 133 return ((uint64_t) uint16_t_le2host(index->leaf_hi)) << 32 |134 146 return ((uint64_t) uint16_t_le2host(index->leaf_hi)) << 32 | 147 ((uint64_t)uint32_t_le2host(index->leaf_lo)); 135 148 } 136 149 137 150 /** Set physical number of block where the child node is located. 138 151 * 139 * @param index extent index to set number to 140 * @param fblock physical number of the block with child node 152 * @param index Extent index to set number to 153 * @param fblock Ohysical number of the block with child node 154 * 141 155 */ 142 156 void ext4_extent_index_set_leaf(ext4_extent_index_t *index, uint64_t fblock) 143 157 { 144 158 index->leaf_lo = host2uint32_t_le((fblock << 32) >> 32); 145 index->leaf_hi = host2uint16_t_le((uint16_t) (fblock >> 32));159 index->leaf_hi = host2uint16_t_le((uint16_t) (fblock >> 32)); 146 160 } 147 161 148 162 /** Get magic value from extent header. 149 163 * 150 * @param header extent header to load value from 151 * @return magic value of extent header 164 * @param header Extent header to load value from 165 * 166 * @return Magic value of extent header 167 * 152 168 */ 153 169 uint16_t ext4_extent_header_get_magic(ext4_extent_header_t *header) … … 158 174 /** Set magic value to extent header. 159 175 * 160 * @param header extent header to set value to 161 * @param magic magic value of extent header 176 * @param header Extent header to set value to 177 * @param magic Magic value of extent header 178 * 162 179 */ 163 180 void ext4_extent_header_set_magic(ext4_extent_header_t *header, uint16_t magic) … … 168 185 /** Get number of entries from extent header 169 186 * 170 * @param header extent header to get value from 171 * @return number of entries covered by extent header 187 * @param header Extent header to get value from 188 * 189 * @return Number of entries covered by extent header 190 * 172 191 */ 173 192 uint16_t ext4_extent_header_get_entries_count(ext4_extent_header_t *header) … … 178 197 /** Set number of entries to extent header 179 198 * 180 * @param header extent header to set value to 181 * @param count number of entries covered by extent header 199 * @param header Extent header to set value to 200 * @param count Number of entries covered by extent header 201 * 182 202 */ 183 203 void ext4_extent_header_set_entries_count(ext4_extent_header_t *header, 184 204 uint16_t count) 185 205 { 186 206 header->entries_count = host2uint16_t_le(count); … … 189 209 /** Get maximum number of entries from extent header 190 210 * 191 * @param header extent header to get value from 192 * @return maximum number of entries covered by extent header 211 * @param header Extent header to get value from 212 * 213 * @return Maximum number of entries covered by extent header 214 * 193 215 */ 194 216 uint16_t ext4_extent_header_get_max_entries_count(ext4_extent_header_t *header) … … 199 221 /** Set maximum number of entries to extent header 200 222 * 201 * @param header extent header to set value to 202 * @param max_count maximum number of entries covered by extent header 223 * @param header Extent header to set value to 224 * @param max_count Maximum number of entries covered by extent header 225 * 203 226 */ 204 227 void ext4_extent_header_set_max_entries_count(ext4_extent_header_t *header, 205 228 uint16_t max_count) 206 229 { 207 230 header->max_entries_count = host2uint16_t_le(max_count); … … 210 233 /** Get depth of extent subtree. 211 234 * 212 * @param header extent header to get value from 213 * @return depth of extent subtree 235 * @param header Extent header to get value from 236 * 237 * @return Depth of extent subtree 238 * 214 239 */ 215 240 uint16_t ext4_extent_header_get_depth(ext4_extent_header_t *header) … … 220 245 /** Set depth of extent subtree. 221 246 * 222 * @param header extent header to set value to 223 * @param depth depth of extent subtree 247 * @param header Extent header to set value to 248 * @param depth Depth of extent subtree 249 * 224 250 */ 225 251 void ext4_extent_header_set_depth(ext4_extent_header_t *header, uint16_t depth) … … 230 256 /** Get generation from extent header 231 257 * 232 * @param header extent header to get value from 233 * @return generation 258 * @param header Extent header to get value from 259 * 260 * @return Generation 261 * 234 262 */ 235 263 uint32_t ext4_extent_header_get_generation(ext4_extent_header_t *header) … … 240 268 /** Set generation to extent header 241 269 * 242 * @param header extent header to set value to 243 * @param generation generation 270 * @param header Extent header to set value to 271 * @param generation Generation 272 * 244 273 */ 245 274 void ext4_extent_header_set_generation(ext4_extent_header_t *header, 246 275 uint32_t generation) 247 276 { 248 277 header->generation = host2uint32_t_le(generation); … … 251 280 /** Binary search in extent index node. 252 281 * 253 * @param header extent header of index node 254 * @param index output value - found index will be set here 255 * @param iblock logical block number to find in index node 282 * @param header Extent header of index node 283 * @param index Output value - found index will be set here 284 * @param iblock Logical block number to find in index node 285 * 256 286 */ 257 287 static void ext4_extent_binsearch_idx(ext4_extent_header_t *header, 258 ext4_extent_index_t **index, uint32_t iblock) 259 { 260 ext4_extent_index_t *r, *l, *m; 261 262 uint16_t entries_count = ext4_extent_header_get_entries_count(header); 263 288 ext4_extent_index_t **index, uint32_t iblock) 289 { 290 ext4_extent_index_t *r; 291 ext4_extent_index_t *l; 292 ext4_extent_index_t *m; 293 294 uint16_t entries_count = 295 ext4_extent_header_get_entries_count(header); 296 264 297 /* Initialize bounds */ 265 298 l = EXT4_EXTENT_FIRST_INDEX(header) + 1; 266 299 r = EXT4_EXTENT_FIRST_INDEX(header) + entries_count - 1; 267 300 268 301 /* Do binary search */ 269 302 while (l <= r) { 270 303 m = l + (r - l) / 2; 271 304 uint32_t first_block = ext4_extent_index_get_first_block(m); 272 if (iblock < first_block) {273 r = m - 1;274 } else {275 l = m + 1;276 }277 } 278 305 306 if (iblock < first_block) 307 r = m - 1; 308 else 309 l = m + 1; 310 } 311 279 312 /* Set output value */ 280 313 *index = l - 1; … … 282 315 283 316 /** Binary search in extent leaf node. 284 * @param header extent header of leaf node 285 * @param extent output value - found extent will be set here, 286 * or NULL if node is empty 287 * @param iblock logical block number to find in leaf node 317 * 318 * @param header Extent header of leaf node 319 * @param extent Output value - found extent will be set here, 320 * or NULL if node is empty 321 * @param iblock Logical block number to find in leaf node 288 322 * 289 323 */ 290 324 static void ext4_extent_binsearch(ext4_extent_header_t *header, 291 ext4_extent_t **extent, uint32_t iblock) 292 { 293 ext4_extent_t *r, *l, *m; 294 295 uint16_t entries_count = ext4_extent_header_get_entries_count(header); 296 325 ext4_extent_t **extent, uint32_t iblock) 326 { 327 ext4_extent_t *r; 328 ext4_extent_t *l; 329 ext4_extent_t *m; 330 331 uint16_t entries_count = 332 ext4_extent_header_get_entries_count(header); 333 297 334 if (entries_count == 0) { 298 335 /* this leaf is empty */ … … 300 337 return; 301 338 } 302 339 303 340 /* Initialize bounds */ 304 341 l = EXT4_EXTENT_FIRST(header) + 1; 305 342 r = EXT4_EXTENT_FIRST(header) + entries_count - 1; 306 343 307 344 /* Do binary search */ 308 345 while (l <= r) { 309 346 m = l + (r - l) / 2; 310 347 uint32_t first_block = ext4_extent_get_first_block(m); 311 if (iblock < first_block) {312 r = m - 1;313 } else {314 l = m + 1;315 }316 } 317 348 349 if (iblock < first_block) 350 r = m - 1; 351 else 352 l = m + 1; 353 } 354 318 355 /* Set output value */ 319 356 *extent = l - 1; … … 324 361 * There is no need to save path in the tree during this algorithm. 325 362 * 326 * @param inode_ref i-node to load block from327 * @param iblock logical block number to find328 * @param fblock output value for physical block number329 * @return error code330 * /331 int ext4_extent_find_block(ext4_inode_ref_t *inode_ref, 332 uint32_t iblock, uint32_t *fblock) 333 { 334 int rc; 335 363 * @param inode_ref I-node to load block from 364 * @param iblock Logical block number to find 365 * @param fblock Output value for physical block number 366 * 367 * @return Error code 368 * 369 */ 370 int ext4_extent_find_block(ext4_inode_ref_t *inode_ref, uint32_t iblock, 371 uint32_t *fblock) 372 { 336 373 /* Compute bound defined by i-node size */ 337 uint64_t inode_size = ext4_inode_get_size(338 339 340 uint32_t block_size = ext4_superblock_get_block_size(341 342 374 uint64_t inode_size = 375 ext4_inode_get_size(inode_ref->fs->superblock, inode_ref->inode); 376 377 uint32_t block_size = 378 ext4_superblock_get_block_size(inode_ref->fs->superblock); 379 343 380 uint32_t last_idx = (inode_size - 1) / block_size; 344 381 345 382 /* Check if requested iblock is not over size of i-node */ 346 383 if (iblock > last_idx) { … … 348 385 return EOK; 349 386 } 350 351 block_t *block = NULL;352 387 388 block_t *block = NULL; 389 353 390 /* Walk through extent tree */ 354 ext4_extent_header_t *header = ext4_inode_get_extent_header(inode_ref->inode); 355 391 ext4_extent_header_t *header = 392 ext4_inode_get_extent_header(inode_ref->inode); 393 356 394 while (ext4_extent_header_get_depth(header) != 0) { 357 358 395 /* Search index in node */ 359 396 ext4_extent_index_t *index; 360 397 ext4_extent_binsearch_idx(header, &index, iblock); 361 398 362 399 /* Load child node and set values for the next iteration */ 363 400 uint64_t child = ext4_extent_index_get_leaf(index); 364 365 if (block != NULL) {401 402 if (block != NULL) 366 403 block_put(block); 367 }368 369 rc = block_get(&block, inode_ref->fs->device, child,BLOCK_FLAGS_NONE);370 if (rc != EOK) {404 405 int rc = block_get(&block, inode_ref->fs->device, child, 406 BLOCK_FLAGS_NONE); 407 if (rc != EOK) 371 408 return rc; 372 } 373 409 374 410 header = (ext4_extent_header_t *)block->data; 375 411 } 376 412 377 413 /* Search extent in the leaf block */ 378 414 ext4_extent_t* extent = NULL; 379 415 ext4_extent_binsearch(header, &extent, iblock); 380 416 381 417 /* Prevent empty leaf */ 382 418 if (extent == NULL) { 383 419 *fblock = 0; 384 420 } else { 385 386 421 /* Compute requested physical block address */ 387 422 uint32_t phys_block; 388 423 uint32_t first = ext4_extent_get_first_block(extent); 389 424 phys_block = ext4_extent_get_start(extent) + iblock - first; 390 425 391 426 *fblock = phys_block; 392 427 } 393 428 394 429 /* Cleanup */ 395 if (block != NULL) {430 if (block != NULL) 396 431 block_put(block); 397 } 398 432 399 433 return EOK; 400 434 } 401 402 435 403 436 /** Find extent for specified iblock. … … 406 439 * saving the path through the tree for possible future modifications. 407 440 * 408 * @param inode_ref i-node to read extent tree from409 * @param iblock iblock to find extent for410 * @param ret_path output value for loaded path from extent tree411 * @return error code412 * /413 static int ext4_extent_find_extent(ext4_inode_ref_t *inode_ref, 414 uint32_t iblock, ext4_extent_path_t **ret_path) 415 { 416 int rc; 417 441 * @param inode_ref I-node to read extent tree from 442 * @param iblock Iblock to find extent for 443 * @param ret_path Output value for loaded path from extent tree 444 * 445 * @return Error code 446 * 447 */ 448 static int ext4_extent_find_extent(ext4_inode_ref_t *inode_ref, uint32_t iblock, 449 ext4_extent_path_t **ret_path) 450 { 418 451 ext4_extent_header_t *eh = 419 420 452 ext4_inode_get_extent_header(inode_ref->inode); 453 421 454 uint16_t depth = ext4_extent_header_get_depth(eh); 422 455 423 456 ext4_extent_path_t *tmp_path; 424 457 425 458 /* Added 2 for possible tree growing */ 426 459 tmp_path = malloc(sizeof(ext4_extent_path_t) * (depth + 2)); 427 if (tmp_path == NULL) {460 if (tmp_path == NULL) 428 461 return ENOMEM; 429 } 430 462 431 463 /* Initialize structure for algorithm start */ 432 464 tmp_path[0].block = inode_ref->block; 433 465 tmp_path[0].header = eh; 434 466 435 467 /* Walk through the extent tree */ 436 468 uint16_t pos = 0; 469 int rc; 437 470 while (ext4_extent_header_get_depth(eh) != 0) { 438 439 471 /* Search index in index node by iblock */ 440 ext4_extent_binsearch_idx(tmp_path[pos].header, &tmp_path[pos].index, iblock); 441 472 ext4_extent_binsearch_idx(tmp_path[pos].header, 473 &tmp_path[pos].index, iblock); 474 442 475 tmp_path[pos].depth = depth; 443 476 tmp_path[pos].extent = NULL; 444 477 445 478 assert(tmp_path[pos].index != NULL); 446 479 447 480 /* Load information for the next iteration */ 448 481 uint64_t fblock = ext4_extent_index_get_leaf(tmp_path[pos].index); 449 482 450 483 block_t *block; 451 rc = block_get(&block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NONE); 452 if (rc != EOK) { 484 rc = block_get(&block, inode_ref->fs->device, fblock, 485 BLOCK_FLAGS_NONE); 486 if (rc != EOK) 453 487 goto cleanup; 454 } 455 488 456 489 pos++; 457 490 458 491 eh = (ext4_extent_header_t *)block->data; 459 492 tmp_path[pos].block = block; 460 493 tmp_path[pos].header = eh; 461 462 } 463 494 } 495 464 496 tmp_path[pos].depth = 0; 465 497 tmp_path[pos].extent = NULL; 466 498 tmp_path[pos].index = NULL; 467 468 499 500 /* Find extent in the leaf node */ 469 501 ext4_extent_binsearch(tmp_path[pos].header, &tmp_path[pos].extent, iblock); 470 471 502 *ret_path = tmp_path; 472 503 473 504 return EOK; 474 505 475 506 cleanup: 476 /* Put loaded blocks 507 /* 508 * Put loaded blocks 477 509 * From 1: 0 is a block with inode data 478 510 */ 479 511 for (uint16_t i = 1; i < tmp_path->depth; ++i) { 480 if (tmp_path[i].block) {512 if (tmp_path[i].block) 481 513 block_put(tmp_path[i].block); 482 } 483 } 484 514 } 515 485 516 /* Destroy temporary data structure */ 486 517 free(tmp_path); 487 518 488 519 return rc; 489 520 } … … 491 522 /** Release extent and all data blocks covered by the extent. 492 523 * 493 * @param inode_ref i-node to release extent and block from494 * @param extent extent to release495 * @return error code496 * /497 static int ext4_extent_release( 498 ext4_inode_ref_t *inode_ref, ext4_extent_t *extent) 499 { 500 int rc; 501 524 * @param inode_ref I-node to release extent and block from 525 * @param extent Extent to release 526 * 527 * @return Error code 528 * 529 */ 530 static int ext4_extent_release(ext4_inode_ref_t *inode_ref, 531 ext4_extent_t *extent) 532 { 502 533 /* Compute number of the first physical block to release */ 503 534 uint64_t start = ext4_extent_get_start(extent); 504 535 uint16_t block_count = ext4_extent_get_block_count(extent); 505 506 rc = ext4_balloc_free_blocks(inode_ref, start, block_count); 507 if (rc != EOK) { 508 return rc; 509 } 510 511 return EOK; 536 537 return ext4_balloc_free_blocks(inode_ref, start, block_count); 512 538 } 513 539 … … 517 543 * the node. In the leaf node all extents will be released. 518 544 * 519 * @param inode_ref i-node where the branch is released 520 * @param index index in the non-leaf node to be released 521 * with the whole subtree 522 * @return error code 545 * @param inode_ref I-node where the branch is released 546 * @param index Index in the non-leaf node to be released 547 * with the whole subtree 548 * 549 * @return Error code 550 * 523 551 */ 524 552 static int ext4_extent_release_branch(ext4_inode_ref_t *inode_ref, 525 553 ext4_extent_index_t *index) 526 554 { 527 int rc;528 555 uint32_t fblock = ext4_extent_index_get_leaf(index); 556 529 557 block_t* block; 530 531 uint32_t fblock = ext4_extent_index_get_leaf(index); 532 533 rc = block_get(&block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NONE); 534 if (rc != EOK) { 558 int rc = block_get(&block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NONE); 559 if (rc != EOK) 535 560 return rc; 536 } 537 561 538 562 ext4_extent_header_t *header = block->data; 539 563 540 564 if (ext4_extent_header_get_depth(header)) { 541 542 565 /* The node is non-leaf, do recursion */ 543 544 566 ext4_extent_index_t *idx = EXT4_EXTENT_FIRST_INDEX(header); 545 567 546 568 /* Release all subbranches */ 547 for (uint32_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i, ++idx) { 569 for (uint32_t i = 0; 570 i < ext4_extent_header_get_entries_count(header); 571 ++i, ++idx) { 548 572 rc = ext4_extent_release_branch(inode_ref, idx); 549 if (rc != EOK) {573 if (rc != EOK) 550 574 return rc; 551 }552 575 } 553 576 } else { 554 555 577 /* Leaf node reached */ 556 578 ext4_extent_t *ext = EXT4_EXTENT_FIRST(header); 557 579 558 580 /* Release all extents and stop recursion */ 559 560 for (uint32_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i, ++ext) { 581 for (uint32_t i = 0; 582 i < ext4_extent_header_get_entries_count(header); 583 ++i, ++ext) { 561 584 rc = ext4_extent_release(inode_ref, ext); 562 if (rc != EOK) {585 if (rc != EOK) 563 586 return rc; 564 }565 587 } 566 588 } 567 589 568 590 /* Release data block where the node was stored */ 569 591 570 592 rc = block_put(block); 571 if (rc != EOK) {593 if (rc != EOK) 572 594 return rc; 573 } 574 595 575 596 ext4_balloc_free_block(inode_ref, fblock); 576 597 577 598 return EOK; 578 599 } … … 580 601 /** Release all data blocks starting from specified logical block. 581 602 * 582 * @param inode_ref i-node to release blocks from 583 * @param iblock_from first logical block to release 603 * @param inode_ref I-node to release blocks from 604 * @param iblock_from First logical block to release 605 * 584 606 */ 585 607 int ext4_extent_release_blocks_from(ext4_inode_ref_t *inode_ref, 586 uint32_t iblock_from) 587 { 588 int rc = EOK; 589 608 uint32_t iblock_from) 609 { 590 610 /* Find the first extent to modify */ 591 611 ext4_extent_path_t *path; 592 rc = ext4_extent_find_extent(inode_ref, iblock_from, &path);593 if (rc != EOK) {612 int rc = ext4_extent_find_extent(inode_ref, iblock_from, &path); 613 if (rc != EOK) 594 614 return rc; 595 } 596 615 597 616 /* Jump to last item of the path (extent) */ 598 617 ext4_extent_path_t *path_ptr = path; 599 while (path_ptr->depth != 0) {618 while (path_ptr->depth != 0) 600 619 path_ptr++; 601 } 602 620 603 621 assert(path_ptr->extent != NULL); 604 622 605 623 /* First extent maybe released partially */ 606 uint32_t first_iblock = ext4_extent_get_first_block(path_ptr->extent); 607 uint32_t first_fblock = ext4_extent_get_start(path_ptr->extent) + iblock_from - first_iblock; 608 609 624 uint32_t first_iblock = 625 ext4_extent_get_first_block(path_ptr->extent); 626 uint32_t first_fblock = 627 ext4_extent_get_start(path_ptr->extent) + iblock_from - first_iblock; 628 610 629 uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent); 611 612 uint16_t delete_count = block_count - (613 614 630 631 uint16_t delete_count = block_count - 632 (ext4_extent_get_start(path_ptr->extent) - first_fblock); 633 615 634 /* Release all blocks */ 616 635 rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count); 617 if (rc != EOK) {636 if (rc != EOK) 618 637 goto cleanup; 619 } 620 638 621 639 /* Correct counter */ 622 640 block_count -= delete_count; 623 641 ext4_extent_set_block_count(path_ptr->extent, block_count); 624 642 625 643 /* Initialize the following loop */ 626 uint16_t entries = ext4_extent_header_get_entries_count(path_ptr->header); 644 uint16_t entries = 645 ext4_extent_header_get_entries_count(path_ptr->header); 627 646 ext4_extent_t *tmp_ext = path_ptr->extent + 1; 628 647 ext4_extent_t *stop_ext = EXT4_EXTENT_FIRST(path_ptr->header) + entries; 629 648 630 649 /* If first extent empty, release it */ 631 if (block_count == 0) {650 if (block_count == 0) 632 651 entries--; 633 } 634 652 635 653 /* Release all successors of the first extent in the same node */ 636 654 while (tmp_ext < stop_ext) { 637 655 first_fblock = ext4_extent_get_start(tmp_ext); 638 656 delete_count = ext4_extent_get_block_count(tmp_ext); 639 657 640 658 rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count); 641 if (rc != EOK) {659 if (rc != EOK) 642 660 goto cleanup; 643 } 644 661 645 662 entries--; 646 663 tmp_ext++; 647 664 } 648 665 649 666 ext4_extent_header_set_entries_count(path_ptr->header, entries); 650 667 path_ptr->block->dirty = true; 651 668 652 669 /* If leaf node is empty, parent entry must be modified */ 653 670 bool remove_parent_record = false; 654 671 655 672 /* Don't release root block (including inode data) !!! */ 656 673 if ((path_ptr != path) && (entries == 0)) { 657 674 rc = ext4_balloc_free_block(inode_ref, path_ptr->block->lba); 658 if (rc != EOK) {675 if (rc != EOK) 659 676 goto cleanup; 660 }677 661 678 remove_parent_record = true; 662 679 } 663 680 664 681 /* Jump to the parent */ 665 682 --path_ptr; 666 683 667 684 /* Release all successors in all tree levels */ 668 685 while (path_ptr >= path) { … … 670 687 ext4_extent_index_t *index = path_ptr->index + 1; 671 688 ext4_extent_index_t *stop = 672 673 689 EXT4_EXTENT_FIRST_INDEX(path_ptr->header) + entries; 690 674 691 /* Correct entries count because of changes in the previous iteration */ 675 if (remove_parent_record) {692 if (remove_parent_record) 676 693 entries--; 677 } 678 694 679 695 /* Iterate over all entries and release the whole subtrees */ 680 696 while (index < stop) { 681 697 rc = ext4_extent_release_branch(inode_ref, index); 682 if (rc != EOK) {698 if (rc != EOK) 683 699 goto cleanup; 684 }700 685 701 ++index; 686 702 --entries; 687 703 } 688 704 689 705 ext4_extent_header_set_entries_count(path_ptr->header, entries); 690 706 path_ptr->block->dirty = true; 691 707 692 708 /* Free the node if it is empty */ 693 709 if ((entries == 0) && (path_ptr != path)) { 694 710 rc = ext4_balloc_free_block(inode_ref, path_ptr->block->lba); 695 if (rc != EOK) {711 if (rc != EOK) 696 712 goto cleanup; 697 } 698 713 699 714 /* Mark parent to be checked */ 700 715 remove_parent_record = true; 701 } else {716 } else 702 717 remove_parent_record = false; 703 } 704 718 705 719 --path_ptr; 706 720 } 707 708 721 709 722 cleanup: 710 /* Put loaded blocks 723 /* 724 * Put loaded blocks 711 725 * starting from 1: 0 is a block with inode data 712 726 */ 713 727 for (uint16_t i = 1; i <= path->depth; ++i) { 714 if (path[i].block) {728 if (path[i].block) 715 729 block_put(path[i].block); 716 } 717 } 718 730 } 731 719 732 /* Destroy temporary data structure */ 720 733 free(path); 721 734 722 735 return rc; 723 736 } 724 737 725 726 738 /** Append new extent to the i-node and do some splitting if necessary. 727 739 * 728 * @param inode_ref i-node to append extent to 729 * @param path path in the extent tree for possible splitting 730 * @param last_path_item input/output parameter for pointer to the last 731 * valid item in the extent tree path 732 * @param iblock logical index of block to append extent for 733 * @return error code 740 * @param inode_ref I-node to append extent to 741 * @param path Path in the extent tree for possible splitting 742 * @param last_path_item Input/output parameter for pointer to the last 743 * valid item in the extent tree path 744 * @param iblock Logical index of block to append extent for 745 * 746 * @return Error code 747 * 734 748 */ 735 749 static int ext4_extent_append_extent(ext4_inode_ref_t *inode_ref, 736 ext4_extent_path_t *path, uint32_t iblock) 737 { 738 int rc; 739 750 ext4_extent_path_t *path, uint32_t iblock) 751 { 740 752 ext4_extent_path_t *path_ptr = path + path->depth; 741 753 742 754 uint32_t block_size = 743 744 755 ext4_superblock_get_block_size(inode_ref->fs->superblock); 756 745 757 /* Start splitting */ 746 758 while (path_ptr > path) { 747 748 uint16_t entries = ext4_extent_header_get_entries_count(path_ptr->header); 749 uint16_t limit = ext4_extent_header_get_max_entries_count(path_ptr->header); 750 759 uint16_t entries = 760 ext4_extent_header_get_entries_count(path_ptr->header); 761 uint16_t limit = 762 ext4_extent_header_get_max_entries_count(path_ptr->header); 763 751 764 if (entries == limit) { 752 753 765 /* Full node - allocate block for new one */ 754 766 uint32_t fblock; 755 rc = ext4_balloc_alloc_block(inode_ref, &fblock);756 if (rc != EOK) {767 int rc = ext4_balloc_alloc_block(inode_ref, &fblock); 768 if (rc != EOK) 757 769 return rc; 758 } 759 770 760 771 block_t *block; 761 rc = block_get(&block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NOREAD); 772 rc = block_get(&block, inode_ref->fs->device, fblock, 773 BLOCK_FLAGS_NOREAD); 762 774 if (rc != EOK) { 763 775 ext4_balloc_free_block(inode_ref, fblock); 764 776 return rc; 765 777 } 766 778 767 779 /* Put back not modified old block */ 768 780 block_put(path_ptr->block); 769 781 770 782 /* Initialize newly allocated block and remember it */ 771 783 memset(block->data, 0, block_size); 772 784 path_ptr->block = block; 773 785 774 786 /* Update pointers in extent path structure */ 775 787 path_ptr->header = block->data; … … 779 791 ext4_extent_index_set_leaf(path_ptr->index, (path_ptr + 1)->block->lba); 780 792 limit = (block_size - sizeof(ext4_extent_header_t)) / 781 793 sizeof(ext4_extent_index_t); 782 794 } else { 783 795 path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header); 784 796 ext4_extent_set_first_block(path_ptr->extent, iblock); 785 797 limit = (block_size - sizeof(ext4_extent_header_t)) / 786 798 sizeof(ext4_extent_t); 787 799 } 788 800 789 801 /* Initialize on-disk structure (header) */ 790 802 ext4_extent_header_set_entries_count(path_ptr->header, 1); … … 793 805 ext4_extent_header_set_depth(path_ptr->header, path_ptr->depth); 794 806 ext4_extent_header_set_generation(path_ptr->header, 0); 795 807 796 808 path_ptr->block->dirty = true; 797 809 798 810 /* Jump to the preceeding item */ 799 811 path_ptr--; 800 801 812 } else { 802 803 813 /* Node with free space */ 804 814 if (path_ptr->depth) { … … 810 820 ext4_extent_set_first_block(path_ptr->extent, iblock); 811 821 } 812 822 813 823 ext4_extent_header_set_entries_count(path_ptr->header, entries + 1); 814 824 path_ptr->block->dirty = true; 815 825 816 826 /* No more splitting needed */ 817 827 return EOK; 818 828 } 819 820 } 821 829 } 830 822 831 assert(path_ptr == path); 823 832 824 833 /* Should be the root split too? */ 825 834 826 835 uint16_t entries = ext4_extent_header_get_entries_count(path->header); 827 836 uint16_t limit = ext4_extent_header_get_max_entries_count(path->header); 828 837 829 838 if (entries == limit) { 830 831 839 uint32_t new_fblock; 832 rc = ext4_balloc_alloc_block(inode_ref, &new_fblock);833 if (rc != EOK) {840 int rc = ext4_balloc_alloc_block(inode_ref, &new_fblock); 841 if (rc != EOK) 834 842 return rc; 835 } 836 843 837 844 block_t *block; 838 rc = block_get(&block, inode_ref->fs->device, 839 new_fblock,BLOCK_FLAGS_NOREAD);840 if (rc != EOK) {845 rc = block_get(&block, inode_ref->fs->device, new_fblock, 846 BLOCK_FLAGS_NOREAD); 847 if (rc != EOK) 841 848 return rc; 842 } 843 849 844 850 /* Initialize newly allocated block */ 845 851 memset(block->data, 0, block_size); 846 852 847 853 /* Move data from root to the new block */ 848 854 memcpy(block->data, inode_ref->inode->blocks, 849 850 851 / / Data block initialized !!!852 855 EXT4_INODE_BLOCKS * sizeof(uint32_t)); 856 857 /* Data block is initialized */ 858 853 859 block_t *root_block = path->block; 854 860 uint16_t root_depth = path->depth; 855 861 ext4_extent_header_t *root_header = path->header; 856 862 857 863 /* Make space for tree growing */ 858 864 ext4_extent_path_t *new_root = path; 859 865 ext4_extent_path_t *old_root = path + 1; 860 866 861 867 size_t nbytes = sizeof(ext4_extent_path_t) * (path->depth + 1); 862 868 memmove(old_root, new_root, nbytes); 863 869 memset(new_root, 0, sizeof(ext4_extent_path_t)); 864 870 865 871 /* Update old root structure */ 866 872 old_root->block = block; 867 873 old_root->header = (ext4_extent_header_t *)block->data; 868 874 869 875 /* Add new entry and update limit for entries */ 870 876 if (old_root->depth) { 871 877 limit = (block_size - sizeof(ext4_extent_header_t)) / 872 878 sizeof(ext4_extent_index_t); 873 879 old_root->index = EXT4_EXTENT_FIRST_INDEX(old_root->header) + entries; 874 880 ext4_extent_index_set_first_block(old_root->index, iblock); … … 877 883 } else { 878 884 limit = (block_size - sizeof(ext4_extent_header_t)) / 879 885 sizeof(ext4_extent_t); 880 886 old_root->extent = EXT4_EXTENT_FIRST(old_root->header) + entries; 881 887 ext4_extent_set_first_block(old_root->extent, iblock); 882 888 old_root->index = NULL; 883 889 } 890 884 891 ext4_extent_header_set_entries_count(old_root->header, entries + 1); 885 892 ext4_extent_header_set_max_entries_count(old_root->header, limit); 886 893 887 894 old_root->block->dirty = true; 888 895 889 896 /* Re-initialize new root metadata */ 890 897 new_root->depth = root_depth + 1; … … 893 900 new_root->extent = NULL; 894 901 new_root->index = EXT4_EXTENT_FIRST_INDEX(new_root->header); 895 902 896 903 ext4_extent_header_set_depth(new_root->header, new_root->depth); 897 904 898 905 /* Create new entry in root */ 899 906 ext4_extent_header_set_entries_count(new_root->header, 1); 900 907 ext4_extent_index_set_first_block(new_root->index, 0); 901 908 ext4_extent_index_set_leaf(new_root->index, new_fblock); 902 909 903 910 new_root->block->dirty = true; 904 905 911 } else { 906 907 912 if (path->depth) { 908 913 path->index = EXT4_EXTENT_FIRST_INDEX(path->header) + entries; … … 913 918 ext4_extent_set_first_block(path->extent, iblock); 914 919 } 915 920 916 921 ext4_extent_header_set_entries_count(path->header, entries + 1); 917 922 path->block->dirty = true; 918 923 } 919 924 920 925 return EOK; 921 926 } … … 927 932 * It includes possible extent tree modifications (splitting). 928 933 *< 929 * @param inode_ref i-node to append block to930 * @param iblock output logical number of newly allocated block931 * @param fblock output physical block address of newly allocated block932 * @return error code933 * /934 int ext4_extent_append_block(ext4_inode_ref_t *inode_ref, 935 uint32_t *iblock, uint32_t *fblock, bool update_size) 936 { 937 int rc = EOK; 938 934 * @param inode_ref I-node to append block to 935 * @param iblock Output logical number of newly allocated block 936 * @param fblock Output physical block address of newly allocated block 937 * 938 * @return Error code 939 * 940 */ 941 int ext4_extent_append_block(ext4_inode_ref_t *inode_ref, uint32_t *iblock, 942 uint32_t *fblock, bool update_size) 943 { 939 944 ext4_superblock_t *sb = inode_ref->fs->superblock; 940 945 uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode); 941 946 uint32_t block_size = ext4_superblock_get_block_size(sb); 942 947 943 948 /* Calculate number of new logical block */ 944 949 uint32_t new_block_idx = 0; 945 950 if (inode_size > 0) { 946 if ((inode_size % block_size) != 0) {951 if ((inode_size % block_size) != 0) 947 952 inode_size += block_size - (inode_size % block_size); 948 }953 949 954 new_block_idx = inode_size / block_size; 950 955 } 951 956 952 957 /* Load the nearest leaf (with extent) */ 953 958 ext4_extent_path_t *path; 954 rc = ext4_extent_find_extent(inode_ref, new_block_idx, &path);955 if (rc != EOK) {959 int rc = ext4_extent_find_extent(inode_ref, new_block_idx, &path); 960 if (rc != EOK) 956 961 return rc; 957 } 958 962 959 963 /* Jump to last item of the path (extent) */ 960 964 ext4_extent_path_t *path_ptr = path; 961 while (path_ptr->depth != 0) {965 while (path_ptr->depth != 0) 962 966 path_ptr++; 963 } 964 967 965 968 /* Add new extent to the node if not present */ 966 if (path_ptr->extent == NULL) {969 if (path_ptr->extent == NULL) 967 970 goto append_extent; 968 } 969 971 970 972 uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent); 971 973 uint16_t block_limit = (1 << 15); 972 974 973 975 uint32_t phys_block = 0; 974 976 if (block_count < block_limit) { 975 976 977 /* There is space for new block in the extent */ 977 978 978 if (block_count == 0) { 979 980 979 /* Existing extent is empty */ 981 982 980 rc = ext4_balloc_alloc_block(inode_ref, &phys_block); 983 if (rc != EOK) {981 if (rc != EOK) 984 982 goto finish; 985 } 986 983 987 984 /* Initialize extent */ 988 985 ext4_extent_set_first_block(path_ptr->extent, new_block_idx); 989 986 ext4_extent_set_start(path_ptr->extent, phys_block); 990 987 ext4_extent_set_block_count(path_ptr->extent, 1); 991 988 992 989 /* Update i-node */ 993 990 if (update_size) { … … 995 992 inode_ref->dirty = true; 996 993 } 997 994 998 995 path_ptr->block->dirty = true; 999 996 1000 997 goto finish; 1001 998 } else { 1002 1003 999 /* Existing extent contains some blocks */ 1004 1005 1000 phys_block = ext4_extent_get_start(path_ptr->extent); 1006 1001 phys_block += ext4_extent_get_block_count(path_ptr->extent); 1007 1002 1008 1003 /* Check if the following block is free for allocation */ 1009 1004 bool free; 1010 1005 rc = ext4_balloc_try_alloc_block(inode_ref, phys_block, &free); 1011 if (rc != EOK) {1006 if (rc != EOK) 1012 1007 goto finish; 1013 } 1014 1015 if (! free) { 1016 /* target is not free, new block must be appended to new extent */ 1008 1009 if (!free) { 1010 /* Target is not free, new block must be appended to new extent */ 1017 1011 goto append_extent; 1018 1012 } 1019 1020 1013 1021 1014 /* Update extent */ 1022 1015 ext4_extent_set_block_count(path_ptr->extent, block_count + 1); 1023 1016 1024 1017 /* Update i-node */ 1025 1018 if (update_size) { … … 1027 1020 inode_ref->dirty = true; 1028 1021 } 1029 1022 1030 1023 path_ptr->block->dirty = true; 1031 1024 1032 1025 goto finish; 1033 1026 } 1034 1027 } 1035 1036 /* Append new extent to the tree */ 1028 1029 1037 1030 append_extent: 1038 1031 /* Append new extent to the tree */ 1039 1032 phys_block = 0; 1040 1033 1041 1034 /* Allocate new data block */ 1042 1035 rc = ext4_balloc_alloc_block(inode_ref, &phys_block); 1043 if (rc != EOK) {1036 if (rc != EOK) 1044 1037 goto finish; 1045 } 1046 1038 1047 1039 /* Append extent for new block (includes tree splitting if needed) */ 1048 1040 rc = ext4_extent_append_extent(inode_ref, path, new_block_idx); … … 1051 1043 goto finish; 1052 1044 } 1053 1045 1054 1046 uint32_t tree_depth = ext4_extent_header_get_depth(path->header); 1055 1047 path_ptr = path + tree_depth; 1056 1048 1057 1049 /* Initialize newly created extent */ 1058 1050 ext4_extent_set_block_count(path_ptr->extent, 1); 1059 1051 ext4_extent_set_first_block(path_ptr->extent, new_block_idx); 1060 1052 ext4_extent_set_start(path_ptr->extent, phys_block); 1061 1053 1062 1054 /* Update i-node */ 1063 1055 if (update_size) { … … 1065 1057 inode_ref->dirty = true; 1066 1058 } 1067 1059 1068 1060 path_ptr->block->dirty = true; 1069 1070 1061 1071 1062 finish: 1072 1063 /* Set return values */ 1073 1064 *iblock = new_block_idx; 1074 1065 *fblock = phys_block; 1075 1076 /* Put loaded blocks 1066 1067 /* 1068 * Put loaded blocks 1077 1069 * starting from 1: 0 is a block with inode data 1078 1070 */ 1079 1071 for (uint16_t i = 1; i <= path->depth; ++i) { 1080 if (path[i].block) {1072 if (path[i].block) 1081 1073 block_put(path[i].block); 1082 } 1083 } 1084 1074 } 1075 1085 1076 /* Destroy temporary data structure */ 1086 1077 free(path); 1087 1078 1088 1079 return rc; 1089 1080 } … … 1091 1082 /** 1092 1083 * @} 1093 */ 1084 */
Note:
See TracChangeset
for help on using the changeset viewer.