1 /* 2 * extent.c --- routines to implement extents support 3 * 4 * Copyright (C) 2007 Theodore Ts'o. 5 * 6 * %Begin-Header% 7 * This file may be redistributed under the terms of the GNU Library 8 * General Public License, version 2. 9 * %End-Header% 10 */ 11 12 #include <stdio.h> 13 #include <string.h> 14 #if HAVE_UNISTD_H 15 #include <unistd.h> 16 #endif 17 #if HAVE_ERRNO_H 18 #include <errno.h> 19 #endif 20 #if HAVE_SYS_STAT_H 21 #include <sys/stat.h> 22 #endif 23 #if HAVE_SYS_TYPES_H 24 #include <sys/types.h> 25 #endif 26 27 #include "ext2_fs.h" 28 #include "ext2fsP.h" 29 #include "e2image.h" 30 31 /* 32 * Definitions to be dropped in lib/ext2fs/ext2fs.h 33 */ 34 35 /* 36 * Private definitions 37 */ 38 39 struct extent_path { 40 char *buf; 41 int entries; 42 int max_entries; 43 int left; 44 int visit_num; 45 int flags; 46 blk64_t end_blk; 47 void *curr; 48 }; 49 50 51 struct ext2_extent_handle { 52 errcode_t magic; 53 ext2_filsys fs; 54 ext2_ino_t ino; 55 struct ext2_inode *inode; 56 struct ext2_inode inodebuf; 57 int type; 58 int level; 59 int max_depth; 60 struct extent_path *path; 61 }; 62 63 struct ext2_extent_path { 64 errcode_t magic; 65 int leaf_height; 66 blk64_t lblk; 67 }; 68 69 /* 70 * Useful Debugging stuff 71 */ 72 73 #ifdef DEBUG 74 static void dbg_show_header(struct ext3_extent_header *eh) 75 { 76 printf("header: magic=%x entries=%u max=%u depth=%u generation=%u\n", 77 ext2fs_le16_to_cpu(eh->eh_magic), 78 ext2fs_le16_to_cpu(eh->eh_entries), 79 ext2fs_le16_to_cpu(eh->eh_max), 80 ext2fs_le16_to_cpu(eh->eh_depth), 81 ext2fs_le32_to_cpu(eh->eh_generation)); 82 } 83 84 static void dbg_show_index(struct ext3_extent_idx *ix) 85 { 86 printf("index: block=%u leaf=%u leaf_hi=%u unused=%u\n", 87 ext2fs_le32_to_cpu(ix->ei_block), 88 ext2fs_le32_to_cpu(ix->ei_leaf), 89 ext2fs_le16_to_cpu(ix->ei_leaf_hi), 90 ext2fs_le16_to_cpu(ix->ei_unused)); 91 } 92 93 static void dbg_show_extent(struct ext3_extent *ex) 94 { 95 printf("extent: block=%u-%u len=%u start=%u start_hi=%u\n", 96 ext2fs_le32_to_cpu(ex->ee_block), 97 ext2fs_le32_to_cpu(ex->ee_block) + 98 ext2fs_le16_to_cpu(ex->ee_len) - 1, 99 ext2fs_le16_to_cpu(ex->ee_len), 100 ext2fs_le32_to_cpu(ex->ee_start), 101 ext2fs_le16_to_cpu(ex->ee_start_hi)); 102 } 103 104 static void dbg_print_extent(char *desc, struct ext2fs_extent *extent) 105 { 106 if (desc) 107 printf("%s: ", desc); 108 printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ", 109 extent->e_lblk, extent->e_lblk + extent->e_len - 1, 110 extent->e_len, extent->e_pblk); 111 if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF) 112 fputs("LEAF ", stdout); 113 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) 114 fputs("UNINIT ", stdout); 115 if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT) 116 fputs("2ND_VISIT ", stdout); 117 if (!extent->e_flags) 118 fputs("(none)", stdout); 119 fputc('\n', stdout); 120 121 } 122 123 #else 124 #define dbg_show_header(eh) do { } while (0) 125 #define dbg_show_index(ix) do { } while (0) 126 #define dbg_show_extent(ex) do { } while (0) 127 #define dbg_print_extent(desc, ex) do { } while (0) 128 #endif 129 130 /* 131 * Verify the extent header as being sane 132 */ 133 errcode_t ext2fs_extent_header_verify(void *ptr, int size) 134 { 135 int eh_max, entry_size; 136 struct ext3_extent_header *eh = ptr; 137 138 dbg_show_header(eh); 139 if (ext2fs_le16_to_cpu(eh->eh_magic) != EXT3_EXT_MAGIC) 140 return EXT2_ET_EXTENT_HEADER_BAD; 141 if (ext2fs_le16_to_cpu(eh->eh_entries) > ext2fs_le16_to_cpu(eh->eh_max)) 142 return EXT2_ET_EXTENT_HEADER_BAD; 143 if (eh->eh_depth == 0) 144 entry_size = sizeof(struct ext3_extent); 145 else 146 entry_size = sizeof(struct ext3_extent_idx); 147 148 eh_max = (size - sizeof(*eh)) / entry_size; 149 /* Allow two extent-sized items at the end of the block, for 150 * ext4_extent_tail with checksum in the future. */ 151 if ((ext2fs_le16_to_cpu(eh->eh_max) > eh_max) || 152 (ext2fs_le16_to_cpu(eh->eh_max) < (eh_max - 2))) 153 return EXT2_ET_EXTENT_HEADER_BAD; 154 155 return 0; 156 } 157 158 159 /* 160 * Begin functions to handle an inode's extent information 161 */ 162 void ext2fs_extent_free(ext2_extent_handle_t handle) 163 { 164 int i; 165 166 if (!handle) 167 return; 168 169 if (handle->path) { 170 for (i=1; i <= handle->max_depth; i++) { 171 if (handle->path[i].buf) 172 ext2fs_free_mem(&handle->path[i].buf); 173 } 174 ext2fs_free_mem(&handle->path); 175 } 176 ext2fs_free_mem(&handle); 177 } 178 179 errcode_t ext2fs_extent_open(ext2_filsys fs, ext2_ino_t ino, 180 ext2_extent_handle_t *ret_handle) 181 { 182 return ext2fs_extent_open2(fs, ino, NULL, ret_handle); 183 } 184 185 errcode_t ext2fs_extent_open2(ext2_filsys fs, ext2_ino_t ino, 186 struct ext2_inode *inode, 187 ext2_extent_handle_t *ret_handle) 188 { 189 struct ext2_extent_handle *handle; 190 errcode_t retval; 191 int i; 192 struct ext3_extent_header *eh; 193 194 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 195 196 if (!inode) 197 if ((ino == 0) || (ino > fs->super->s_inodes_count)) 198 return EXT2_ET_BAD_INODE_NUM; 199 200 retval = ext2fs_get_mem(sizeof(struct ext2_extent_handle), &handle); 201 if (retval) 202 return retval; 203 memset(handle, 0, sizeof(struct ext2_extent_handle)); 204 205 handle->ino = ino; 206 handle->fs = fs; 207 208 if (inode) { 209 handle->inode = inode; 210 } else { 211 handle->inode = &handle->inodebuf; 212 retval = ext2fs_read_inode(fs, ino, handle->inode); 213 if (retval) 214 goto errout; 215 } 216 217 eh = (struct ext3_extent_header *) &handle->inode->i_block[0]; 218 219 for (i=0; i < EXT2_N_BLOCKS; i++) 220 if (handle->inode->i_block[i]) 221 break; 222 if (i >= EXT2_N_BLOCKS) { 223 eh->eh_magic = ext2fs_cpu_to_le16(EXT3_EXT_MAGIC); 224 eh->eh_depth = 0; 225 eh->eh_entries = 0; 226 i = (sizeof(handle->inode->i_block) - sizeof(*eh)) / 227 sizeof(struct ext3_extent); 228 eh->eh_max = ext2fs_cpu_to_le16(i); 229 handle->inode->i_flags |= EXT4_EXTENTS_FL; 230 } 231 232 if (!(handle->inode->i_flags & EXT4_EXTENTS_FL)) { 233 retval = EXT2_ET_INODE_NOT_EXTENT; 234 goto errout; 235 } 236 237 retval = ext2fs_extent_header_verify(eh, sizeof(handle->inode->i_block)); 238 if (retval) 239 goto errout; 240 241 handle->max_depth = ext2fs_le16_to_cpu(eh->eh_depth); 242 handle->type = ext2fs_le16_to_cpu(eh->eh_magic); 243 244 retval = ext2fs_get_mem(((handle->max_depth+1) * 245 sizeof(struct extent_path)), 246 &handle->path); 247 memset(handle->path, 0, 248 (handle->max_depth+1) * sizeof(struct extent_path)); 249 handle->path[0].buf = (char *) handle->inode->i_block; 250 251 handle->path[0].left = handle->path[0].entries = 252 ext2fs_le16_to_cpu(eh->eh_entries); 253 handle->path[0].max_entries = ext2fs_le16_to_cpu(eh->eh_max); 254 handle->path[0].curr = 0; 255 handle->path[0].end_blk = 256 (EXT2_I_SIZE(handle->inode) + fs->blocksize - 1) >> 257 EXT2_BLOCK_SIZE_BITS(fs->super); 258 handle->path[0].visit_num = 1; 259 handle->level = 0; 260 handle->magic = EXT2_ET_MAGIC_EXTENT_HANDLE; 261 262 *ret_handle = handle; 263 return 0; 264 265 errout: 266 ext2fs_extent_free(handle); 267 return retval; 268 } 269 270 /* 271 * This function is responsible for (optionally) moving through the 272 * extent tree and then returning the current extent 273 */ 274 errcode_t ext2fs_extent_get(ext2_extent_handle_t handle, 275 int flags, struct ext2fs_extent *extent) 276 { 277 struct extent_path *path, *newpath; 278 struct ext3_extent_header *eh; 279 struct ext3_extent_idx *ix = 0; 280 struct ext3_extent *ex; 281 errcode_t retval; 282 blk64_t blk; 283 blk64_t end_blk; 284 int orig_op, op; 285 286 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 287 288 if (!handle->path) 289 return EXT2_ET_NO_CURRENT_NODE; 290 291 orig_op = op = flags & EXT2_EXTENT_MOVE_MASK; 292 293 retry: 294 path = handle->path + handle->level; 295 if ((orig_op == EXT2_EXTENT_NEXT) || 296 (orig_op == EXT2_EXTENT_NEXT_LEAF)) { 297 if (handle->level < handle->max_depth) { 298 /* interior node */ 299 if (path->visit_num == 0) { 300 path->visit_num++; 301 op = EXT2_EXTENT_DOWN; 302 } else if (path->left > 0) 303 op = EXT2_EXTENT_NEXT_SIB; 304 else if (handle->level > 0) 305 op = EXT2_EXTENT_UP; 306 else 307 return EXT2_ET_EXTENT_NO_NEXT; 308 } else { 309 /* leaf node */ 310 if (path->left > 0) 311 op = EXT2_EXTENT_NEXT_SIB; 312 else if (handle->level > 0) 313 op = EXT2_EXTENT_UP; 314 else 315 return EXT2_ET_EXTENT_NO_NEXT; 316 } 317 if (op != EXT2_EXTENT_NEXT_SIB) { 318 #ifdef DEBUG_GET_EXTENT 319 printf("<<<< OP = %s\n", 320 (op == EXT2_EXTENT_DOWN) ? "down" : 321 ((op == EXT2_EXTENT_UP) ? "up" : "unknown")); 322 #endif 323 } 324 } 325 326 if ((orig_op == EXT2_EXTENT_PREV) || 327 (orig_op == EXT2_EXTENT_PREV_LEAF)) { 328 if (handle->level < handle->max_depth) { 329 /* interior node */ 330 if (path->visit_num > 0 ) { 331 /* path->visit_num = 0; */ 332 op = EXT2_EXTENT_DOWN_AND_LAST; 333 } else if (path->left < path->entries-1) 334 op = EXT2_EXTENT_PREV_SIB; 335 else if (handle->level > 0) 336 op = EXT2_EXTENT_UP; 337 else 338 return EXT2_ET_EXTENT_NO_PREV; 339 } else { 340 /* leaf node */ 341 if (path->left < path->entries-1) 342 op = EXT2_EXTENT_PREV_SIB; 343 else if (handle->level > 0) 344 op = EXT2_EXTENT_UP; 345 else 346 return EXT2_ET_EXTENT_NO_PREV; 347 } 348 if (op != EXT2_EXTENT_PREV_SIB) { 349 #ifdef DEBUG_GET_EXTENT 350 printf("<<<< OP = %s\n", 351 (op == EXT2_EXTENT_DOWN_AND_LAST) ? "down/last" : 352 ((op == EXT2_EXTENT_UP) ? "up" : "unknown")); 353 #endif 354 } 355 } 356 357 if (orig_op == EXT2_EXTENT_LAST_LEAF) { 358 if ((handle->level < handle->max_depth) && 359 (path->left == 0)) 360 op = EXT2_EXTENT_DOWN; 361 else 362 op = EXT2_EXTENT_LAST_SIB; 363 #ifdef DEBUG_GET_EXTENT 364 printf("<<<< OP = %s\n", 365 (op == EXT2_EXTENT_DOWN) ? "down" : "last_sib"); 366 #endif 367 } 368 369 switch (op) { 370 case EXT2_EXTENT_CURRENT: 371 ix = path->curr; 372 break; 373 case EXT2_EXTENT_ROOT: 374 handle->level = 0; 375 path = handle->path + handle->level; 376 /* fallthrough */ 377 case EXT2_EXTENT_FIRST_SIB: 378 path->left = path->entries; 379 path->curr = 0; 380 /* fallthrough */ 381 case EXT2_EXTENT_NEXT_SIB: 382 if (path->left <= 0) 383 return EXT2_ET_EXTENT_NO_NEXT; 384 if (path->curr) { 385 ix = path->curr; 386 ix++; 387 } else { 388 eh = (struct ext3_extent_header *) path->buf; 389 ix = EXT_FIRST_INDEX(eh); 390 } 391 path->left--; 392 path->curr = ix; 393 path->visit_num = 0; 394 break; 395 case EXT2_EXTENT_PREV_SIB: 396 if (!path->curr || 397 path->left+1 >= path->entries) 398 return EXT2_ET_EXTENT_NO_PREV; 399 ix = path->curr; 400 ix--; 401 path->curr = ix; 402 path->left++; 403 if (handle->level < handle->max_depth) 404 path->visit_num = 1; 405 break; 406 case EXT2_EXTENT_LAST_SIB: 407 eh = (struct ext3_extent_header *) path->buf; 408 path->curr = EXT_LAST_EXTENT(eh); 409 ix = path->curr; 410 path->left = 0; 411 path->visit_num = 0; 412 break; 413 case EXT2_EXTENT_UP: 414 if (handle->level <= 0) 415 return EXT2_ET_EXTENT_NO_UP; 416 handle->level--; 417 path--; 418 ix = path->curr; 419 if ((orig_op == EXT2_EXTENT_PREV) || 420 (orig_op == EXT2_EXTENT_PREV_LEAF)) 421 path->visit_num = 0; 422 break; 423 case EXT2_EXTENT_DOWN: 424 case EXT2_EXTENT_DOWN_AND_LAST: 425 if (!path->curr ||(handle->level >= handle->max_depth)) 426 return EXT2_ET_EXTENT_NO_DOWN; 427 428 ix = path->curr; 429 newpath = path + 1; 430 if (!newpath->buf) { 431 retval = ext2fs_get_mem(handle->fs->blocksize, 432 &newpath->buf); 433 if (retval) 434 return retval; 435 } 436 blk = ext2fs_le32_to_cpu(ix->ei_leaf) + 437 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32); 438 if ((handle->fs->flags & EXT2_FLAG_IMAGE_FILE) && 439 (handle->fs->io != handle->fs->image_io)) 440 memset(newpath->buf, 0, handle->fs->blocksize); 441 else { 442 retval = io_channel_read_blk64(handle->fs->io, 443 blk, 1, newpath->buf); 444 if (retval) 445 return retval; 446 } 447 handle->level++; 448 449 eh = (struct ext3_extent_header *) newpath->buf; 450 451 retval = ext2fs_extent_header_verify(eh, handle->fs->blocksize); 452 if (retval) { 453 handle->level--; 454 return retval; 455 } 456 457 newpath->left = newpath->entries = 458 ext2fs_le16_to_cpu(eh->eh_entries); 459 newpath->max_entries = ext2fs_le16_to_cpu(eh->eh_max); 460 461 if (path->left > 0) { 462 ix++; 463 newpath->end_blk = ext2fs_le32_to_cpu(ix->ei_block); 464 } else 465 newpath->end_blk = path->end_blk; 466 467 path = newpath; 468 if (op == EXT2_EXTENT_DOWN) { 469 ix = EXT_FIRST_INDEX((struct ext3_extent_header *) eh); 470 path->curr = ix; 471 path->left = path->entries - 1; 472 path->visit_num = 0; 473 } else { 474 ix = EXT_LAST_INDEX((struct ext3_extent_header *) eh); 475 path->curr = ix; 476 path->left = 0; 477 if (handle->level < handle->max_depth) 478 path->visit_num = 1; 479 } 480 #ifdef DEBUG_GET_EXTENT 481 printf("Down to level %d/%d, end_blk=%llu\n", 482 handle->level, handle->max_depth, 483 path->end_blk); 484 #endif 485 break; 486 default: 487 return EXT2_ET_OP_NOT_SUPPORTED; 488 } 489 490 if (!ix) 491 return EXT2_ET_NO_CURRENT_NODE; 492 493 extent->e_flags = 0; 494 #ifdef DEBUG_GET_EXTENT 495 printf("(Left %d)\n", path->left); 496 #endif 497 498 if (handle->level == handle->max_depth) { 499 ex = (struct ext3_extent *) ix; 500 501 extent->e_pblk = ext2fs_le32_to_cpu(ex->ee_start) + 502 ((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32); 503 extent->e_lblk = ext2fs_le32_to_cpu(ex->ee_block); 504 extent->e_len = ext2fs_le16_to_cpu(ex->ee_len); 505 extent->e_flags |= EXT2_EXTENT_FLAGS_LEAF; 506 if (extent->e_len > EXT_INIT_MAX_LEN) { 507 extent->e_len -= EXT_INIT_MAX_LEN; 508 extent->e_flags |= EXT2_EXTENT_FLAGS_UNINIT; 509 } 510 } else { 511 extent->e_pblk = ext2fs_le32_to_cpu(ix->ei_leaf) + 512 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32); 513 extent->e_lblk = ext2fs_le32_to_cpu(ix->ei_block); 514 if (path->left > 0) { 515 ix++; 516 end_blk = ext2fs_le32_to_cpu(ix->ei_block); 517 } else 518 end_blk = path->end_blk; 519 520 extent->e_len = end_blk - extent->e_lblk; 521 } 522 if (path->visit_num) 523 extent->e_flags |= EXT2_EXTENT_FLAGS_SECOND_VISIT; 524 525 if (((orig_op == EXT2_EXTENT_NEXT_LEAF) || 526 (orig_op == EXT2_EXTENT_PREV_LEAF)) && 527 (handle->level != handle->max_depth)) 528 goto retry; 529 530 if ((orig_op == EXT2_EXTENT_LAST_LEAF) && 531 ((handle->level != handle->max_depth) || 532 (path->left != 0))) 533 goto retry; 534 535 return 0; 536 } 537 538 static errcode_t update_path(ext2_extent_handle_t handle) 539 { 540 blk64_t blk; 541 errcode_t retval; 542 struct ext3_extent_idx *ix; 543 544 if (handle->level == 0) { 545 retval = ext2fs_write_inode(handle->fs, handle->ino, 546 handle->inode); 547 } else { 548 ix = handle->path[handle->level - 1].curr; 549 blk = ext2fs_le32_to_cpu(ix->ei_leaf) + 550 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32); 551 552 retval = io_channel_write_blk64(handle->fs->io, 553 blk, 1, handle->path[handle->level].buf); 554 } 555 return retval; 556 } 557 558 #if 0 559 errcode_t ext2fs_extent_save_path(ext2_extent_handle_t handle, 560 ext2_extent_path_t *ret_path) 561 { 562 ext2_extent_path_t save_path; 563 struct ext2fs_extent extent; 564 struct ext2_extent_info info; 565 errcode_t retval; 566 567 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 568 if (retval) 569 return retval; 570 571 retval = ext2fs_extent_get_info(handle, &info); 572 if (retval) 573 return retval; 574 575 retval = ext2fs_get_mem(sizeof(struct ext2_extent_path), &save_path); 576 if (retval) 577 return retval; 578 memset(save_path, 0, sizeof(struct ext2_extent_path)); 579 580 save_path->magic = EXT2_ET_MAGIC_EXTENT_PATH; 581 save_path->leaf_height = info.max_depth - info.curr_level - 1; 582 save_path->lblk = extent.e_lblk; 583 584 *ret_path = save_path; 585 return 0; 586 } 587 588 errcode_t ext2fs_extent_free_path(ext2_extent_path_t path) 589 { 590 EXT2_CHECK_MAGIC(path, EXT2_ET_MAGIC_EXTENT_PATH); 591 592 ext2fs_free_mem(&path); 593 return 0; 594 } 595 #endif 596 597 /* 598 * Go to the node at leaf_level which contains logical block blk. 599 * 600 * leaf_level is height from the leaf node level, i.e. 601 * leaf_level 0 is at leaf node, leaf_level 1 is 1 above etc. 602 * 603 * If "blk" has no mapping (hole) then handle is left at last 604 * extent before blk. 605 */ 606 errcode_t ext2fs_extent_goto2(ext2_extent_handle_t handle, 607 int leaf_level, blk64_t blk) 608 { 609 struct ext2fs_extent extent; 610 errcode_t retval; 611 612 retval = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent); 613 if (retval) { 614 if (retval == EXT2_ET_EXTENT_NO_NEXT) 615 retval = EXT2_ET_EXTENT_NOT_FOUND; 616 return retval; 617 } 618 619 if (leaf_level > handle->max_depth) { 620 #ifdef DEBUG 621 printf("leaf level %d greater than tree depth %d\n", 622 leaf_level, handle->max_depth); 623 #endif 624 return EXT2_ET_OP_NOT_SUPPORTED; 625 } 626 627 #ifdef DEBUG 628 printf("goto extent ino %u, level %d, %llu\n", handle->ino, 629 leaf_level, blk); 630 #endif 631 632 #ifdef DEBUG_GOTO_EXTENTS 633 dbg_print_extent("root", &extent); 634 #endif 635 while (1) { 636 if (handle->max_depth - handle->level == leaf_level) { 637 /* block is in this &extent */ 638 if ((blk >= extent.e_lblk) && 639 (blk < extent.e_lblk + extent.e_len)) 640 return 0; 641 if (blk < extent.e_lblk) { 642 retval = ext2fs_extent_get(handle, 643 EXT2_EXTENT_PREV_SIB, 644 &extent); 645 return EXT2_ET_EXTENT_NOT_FOUND; 646 } 647 retval = ext2fs_extent_get(handle, 648 EXT2_EXTENT_NEXT_SIB, 649 &extent); 650 if (retval == EXT2_ET_EXTENT_NO_NEXT) 651 return EXT2_ET_EXTENT_NOT_FOUND; 652 if (retval) 653 return retval; 654 continue; 655 } 656 657 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_SIB, 658 &extent); 659 if (retval == EXT2_ET_EXTENT_NO_NEXT) 660 goto go_down; 661 if (retval) 662 return retval; 663 664 #ifdef DEBUG_GOTO_EXTENTS 665 dbg_print_extent("next", &extent); 666 #endif 667 if (blk == extent.e_lblk) 668 goto go_down; 669 if (blk > extent.e_lblk) 670 continue; 671 672 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_SIB, 673 &extent); 674 if (retval) 675 return retval; 676 677 #ifdef DEBUG_GOTO_EXTENTS 678 dbg_print_extent("prev", &extent); 679 #endif 680 681 go_down: 682 retval = ext2fs_extent_get(handle, EXT2_EXTENT_DOWN, 683 &extent); 684 if (retval) 685 return retval; 686 687 #ifdef DEBUG_GOTO_EXTENTS 688 dbg_print_extent("down", &extent); 689 #endif 690 } 691 } 692 693 errcode_t ext2fs_extent_goto(ext2_extent_handle_t handle, 694 blk64_t blk) 695 { 696 return ext2fs_extent_goto2(handle, 0, blk); 697 } 698 699 /* 700 * Traverse back up to root fixing parents of current node as needed. 701 * 702 * If we changed start of first entry in a node, fix parent index start 703 * and so on. 704 * 705 * Safe to call for any position in node; if not at the first entry, 706 * will simply return. 707 */ 708 errcode_t ext2fs_extent_fix_parents(ext2_extent_handle_t handle) 709 { 710 int retval = 0; 711 int orig_height; 712 blk64_t start; 713 struct extent_path *path; 714 struct ext2fs_extent extent; 715 struct ext2_extent_info info; 716 717 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 718 719 if (!(handle->fs->flags & EXT2_FLAG_RW)) 720 return EXT2_ET_RO_FILSYS; 721 722 if (!handle->path) 723 return EXT2_ET_NO_CURRENT_NODE; 724 725 path = handle->path + handle->level; 726 if (!path->curr) 727 return EXT2_ET_NO_CURRENT_NODE; 728 729 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 730 if (retval) 731 goto done; 732 733 /* modified node's start block */ 734 start = extent.e_lblk; 735 736 if ((retval = ext2fs_extent_get_info(handle, &info))) 737 return retval; 738 orig_height = info.max_depth - info.curr_level; 739 740 /* traverse up until index not first, or startblk matches, or top */ 741 while (handle->level > 0 && 742 (path->left == path->entries - 1)) { 743 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent); 744 if (retval) 745 goto done; 746 if (extent.e_lblk == start) 747 break; 748 path = handle->path + handle->level; 749 extent.e_len += (extent.e_lblk - start); 750 extent.e_lblk = start; 751 retval = ext2fs_extent_replace(handle, 0, &extent); 752 if (retval) 753 goto done; 754 update_path(handle); 755 } 756 757 /* put handle back to where we started */ 758 retval = ext2fs_extent_goto2(handle, orig_height, start); 759 done: 760 return retval; 761 } 762 763 errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle, 764 int flags EXT2FS_ATTR((unused)), 765 struct ext2fs_extent *extent) 766 { 767 struct extent_path *path; 768 struct ext3_extent_idx *ix; 769 struct ext3_extent *ex; 770 771 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 772 773 if (!(handle->fs->flags & EXT2_FLAG_RW)) 774 return EXT2_ET_RO_FILSYS; 775 776 if (!handle->path) 777 return EXT2_ET_NO_CURRENT_NODE; 778 779 path = handle->path + handle->level; 780 if (!path->curr) 781 return EXT2_ET_NO_CURRENT_NODE; 782 783 #ifdef DEBUG 784 printf("extent replace: %u ", handle->ino); 785 dbg_print_extent(0, extent); 786 #endif 787 788 if (handle->level == handle->max_depth) { 789 ex = path->curr; 790 791 ex->ee_block = ext2fs_cpu_to_le32(extent->e_lblk); 792 ex->ee_start = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF); 793 ex->ee_start_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32); 794 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) { 795 if (extent->e_len > EXT_UNINIT_MAX_LEN) 796 return EXT2_ET_EXTENT_INVALID_LENGTH; 797 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len + 798 EXT_INIT_MAX_LEN); 799 } else { 800 if (extent->e_len > EXT_INIT_MAX_LEN) 801 return EXT2_ET_EXTENT_INVALID_LENGTH; 802 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len); 803 } 804 } else { 805 ix = path->curr; 806 807 ix->ei_leaf = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF); 808 ix->ei_leaf_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32); 809 ix->ei_block = ext2fs_cpu_to_le32(extent->e_lblk); 810 ix->ei_unused = 0; 811 } 812 update_path(handle); 813 return 0; 814 } 815 816 /* 817 * allocate a new block, move half the current node to it, and update parent 818 * 819 * handle will be left pointing at original record. 820 */ 821 errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle) 822 { 823 errcode_t retval = 0; 824 blk64_t new_node_pblk; 825 blk64_t new_node_start; 826 blk64_t orig_lblk; 827 blk64_t goal_blk = 0; 828 int orig_height; 829 char *block_buf = NULL; 830 struct ext2fs_extent extent; 831 struct extent_path *path, *newpath = 0; 832 struct ext3_extent_header *eh, *neweh; 833 int tocopy; 834 int new_root = 0; 835 struct ext2_extent_info info; 836 837 /* basic sanity */ 838 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 839 840 if (!(handle->fs->flags & EXT2_FLAG_RW)) 841 return EXT2_ET_RO_FILSYS; 842 843 if (!handle->path) 844 return EXT2_ET_NO_CURRENT_NODE; 845 846 #ifdef DEBUG 847 printf("splitting node at level %d\n", handle->level); 848 #endif 849 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 850 if (retval) 851 goto done; 852 853 retval = ext2fs_extent_get_info(handle, &info); 854 if (retval) 855 goto done; 856 857 /* save the position we were originally splitting... */ 858 orig_height = info.max_depth - info.curr_level; 859 orig_lblk = extent.e_lblk; 860 861 /* Is there room in the parent for a new entry? */ 862 if (handle->level && 863 (handle->path[handle->level - 1].entries >= 864 handle->path[handle->level - 1].max_entries)) { 865 866 #ifdef DEBUG 867 printf("parent level %d full; splitting it too\n", 868 handle->level - 1); 869 #endif 870 /* split the parent */ 871 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent); 872 if (retval) 873 goto done; 874 goal_blk = extent.e_pblk; 875 876 retval = ext2fs_extent_node_split(handle); 877 if (retval) 878 goto done; 879 880 /* get handle back to our original split position */ 881 retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk); 882 if (retval) 883 goto done; 884 } 885 886 /* At this point, parent should have room for this split */ 887 path = handle->path + handle->level; 888 if (!path->curr) 889 return EXT2_ET_NO_CURRENT_NODE; 890 891 /* extent header of the current node we'll split */ 892 eh = (struct ext3_extent_header *)path->buf; 893 894 /* splitting root level means moving them all out */ 895 if (handle->level == 0) { 896 new_root = 1; 897 tocopy = ext2fs_le16_to_cpu(eh->eh_entries); 898 retval = ext2fs_get_mem(((handle->max_depth+2) * 899 sizeof(struct extent_path)), 900 &newpath); 901 if (retval) 902 goto done; 903 memset(newpath, 0, 904 ((handle->max_depth+2) * sizeof(struct extent_path))); 905 } else { 906 tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2; 907 } 908 909 #ifdef DEBUG 910 printf("will copy out %d of %d entries at level %d\n", 911 tocopy, ext2fs_le16_to_cpu(eh->eh_entries), 912 handle->level); 913 #endif 914 915 if (!tocopy) { 916 #ifdef DEBUG 917 printf("Nothing to copy to new block!\n"); 918 #endif 919 retval = EXT2_ET_CANT_SPLIT_EXTENT; 920 goto done; 921 } 922 923 /* first we need a new block, or can do nothing. */ 924 block_buf = malloc(handle->fs->blocksize); 925 if (!block_buf) { 926 retval = ENOMEM; 927 goto done; 928 } 929 930 if (!goal_blk) { 931 dgrp_t group = ext2fs_group_of_ino(handle->fs, handle->ino); 932 __u8 log_flex = handle->fs->super->s_log_groups_per_flex; 933 934 if (log_flex) 935 group = group & ~((1 << (log_flex)) - 1); 936 goal_blk = ext2fs_group_first_block2(handle->fs, group); 937 } 938 retval = ext2fs_alloc_block2(handle->fs, goal_blk, block_buf, 939 &new_node_pblk); 940 if (retval) 941 goto done; 942 943 #ifdef DEBUG 944 printf("will copy to new node at block %lu\n", 945 (unsigned long) new_node_pblk); 946 #endif 947 948 /* Copy data into new block buffer */ 949 /* First the header for the new block... */ 950 neweh = (struct ext3_extent_header *) block_buf; 951 memcpy(neweh, eh, sizeof(struct ext3_extent_header)); 952 neweh->eh_entries = ext2fs_cpu_to_le16(tocopy); 953 neweh->eh_max = ext2fs_cpu_to_le16((handle->fs->blocksize - 954 sizeof(struct ext3_extent_header)) / 955 sizeof(struct ext3_extent)); 956 957 /* then the entries for the new block... */ 958 memcpy(EXT_FIRST_INDEX(neweh), 959 EXT_FIRST_INDEX(eh) + 960 (ext2fs_le16_to_cpu(eh->eh_entries) - tocopy), 961 sizeof(struct ext3_extent_idx) * tocopy); 962 963 new_node_start = ext2fs_le32_to_cpu(EXT_FIRST_INDEX(neweh)->ei_block); 964 965 /* ...and write the new node block out to disk. */ 966 retval = io_channel_write_blk64(handle->fs->io, new_node_pblk, 1, 967 block_buf); 968 969 if (retval) 970 goto done; 971 972 /* OK! we've created the new node; now adjust the tree */ 973 974 /* current path now has fewer active entries, we copied some out */ 975 if (handle->level == 0) { 976 memcpy(newpath, path, 977 sizeof(struct extent_path) * (handle->max_depth+1)); 978 handle->path = newpath; 979 newpath = path; 980 path = handle->path; 981 path->entries = 1; 982 path->left = path->max_entries - 1; 983 handle->max_depth++; 984 eh->eh_depth = ext2fs_cpu_to_le16(handle->max_depth); 985 } else { 986 path->entries -= tocopy; 987 path->left -= tocopy; 988 } 989 990 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 991 /* this writes out the node, incl. the modified header */ 992 retval = update_path(handle); 993 if (retval) 994 goto done; 995 996 /* now go up and insert/replace index for new node we created */ 997 if (new_root) { 998 retval = ext2fs_extent_get(handle, EXT2_EXTENT_FIRST_SIB, &extent); 999 if (retval) 1000 goto done; 1001 1002 extent.e_lblk = new_node_start; 1003 extent.e_pblk = new_node_pblk; 1004 extent.e_len = handle->path[0].end_blk - extent.e_lblk; 1005 retval = ext2fs_extent_replace(handle, 0, &extent); 1006 if (retval) 1007 goto done; 1008 } else { 1009 __u32 new_node_length; 1010 1011 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent); 1012 /* will insert after this one; it's length is shorter now */ 1013 new_node_length = new_node_start - extent.e_lblk; 1014 extent.e_len -= new_node_length; 1015 retval = ext2fs_extent_replace(handle, 0, &extent); 1016 if (retval) 1017 goto done; 1018 1019 /* now set up the new extent and insert it */ 1020 extent.e_lblk = new_node_start; 1021 extent.e_pblk = new_node_pblk; 1022 extent.e_len = new_node_length; 1023 retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER, &extent); 1024 if (retval) 1025 goto done; 1026 } 1027 1028 /* get handle back to our original position */ 1029 retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk); 1030 if (retval) 1031 goto done; 1032 1033 /* new node hooked in, so update inode block count (do this here?) */ 1034 handle->inode->i_blocks += (handle->fs->blocksize * 1035 EXT2FS_CLUSTER_RATIO(handle->fs)) / 512; 1036 retval = ext2fs_write_inode(handle->fs, handle->ino, 1037 handle->inode); 1038 if (retval) 1039 goto done; 1040 1041 done: 1042 if (newpath) 1043 ext2fs_free_mem(&newpath); 1044 free(block_buf); 1045 1046 return retval; 1047 } 1048 1049 errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags, 1050 struct ext2fs_extent *extent) 1051 { 1052 struct extent_path *path; 1053 struct ext3_extent_idx *ix; 1054 struct ext3_extent_header *eh; 1055 errcode_t retval; 1056 1057 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1058 1059 if (!(handle->fs->flags & EXT2_FLAG_RW)) 1060 return EXT2_ET_RO_FILSYS; 1061 1062 if (!handle->path) 1063 return EXT2_ET_NO_CURRENT_NODE; 1064 1065 #ifdef DEBUG 1066 printf("extent insert: %u ", handle->ino); 1067 dbg_print_extent(0, extent); 1068 #endif 1069 1070 path = handle->path + handle->level; 1071 1072 if (path->entries >= path->max_entries) { 1073 if (flags & EXT2_EXTENT_INSERT_NOSPLIT) { 1074 return EXT2_ET_CANT_INSERT_EXTENT; 1075 } else { 1076 #ifdef DEBUG 1077 printf("node full (level %d) - splitting\n", 1078 handle->level); 1079 #endif 1080 retval = ext2fs_extent_node_split(handle); 1081 if (retval) 1082 return retval; 1083 path = handle->path + handle->level; 1084 } 1085 } 1086 1087 eh = (struct ext3_extent_header *) path->buf; 1088 if (path->curr) { 1089 ix = path->curr; 1090 if (flags & EXT2_EXTENT_INSERT_AFTER) { 1091 ix++; 1092 path->left--; 1093 } 1094 } else 1095 ix = EXT_FIRST_INDEX(eh); 1096 1097 path->curr = ix; 1098 1099 if (path->left >= 0) 1100 memmove(ix + 1, ix, 1101 (path->left+1) * sizeof(struct ext3_extent_idx)); 1102 path->left++; 1103 path->entries++; 1104 1105 eh = (struct ext3_extent_header *) path->buf; 1106 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 1107 1108 retval = ext2fs_extent_replace(handle, 0, extent); 1109 if (retval) 1110 goto errout; 1111 1112 retval = update_path(handle); 1113 if (retval) 1114 goto errout; 1115 1116 return 0; 1117 1118 errout: 1119 ext2fs_extent_delete(handle, 0); 1120 return retval; 1121 } 1122 1123 /* 1124 * Sets the physical block for a logical file block in the extent tree. 1125 * 1126 * May: map unmapped, unmap mapped, or remap mapped blocks. 1127 * 1128 * Mapping an unmapped block adds a single-block extent. 1129 * 1130 * Unmapping first or last block modifies extent in-place 1131 * - But may need to fix parent's starts too in first-block case 1132 * 1133 * Mapping any unmapped block requires adding a (single-block) extent 1134 * and inserting into proper point in tree. 1135 * 1136 * Modifying (unmapping or remapping) a block in the middle 1137 * of an extent requires splitting the extent. 1138 * - Remapping case requires new single-block extent. 1139 * 1140 * Remapping first or last block adds an extent. 1141 * 1142 * We really need extent adding to be smart about merging. 1143 */ 1144 1145 errcode_t ext2fs_extent_set_bmap(ext2_extent_handle_t handle, 1146 blk64_t logical, blk64_t physical, int flags) 1147 { 1148 errcode_t ec, retval = 0; 1149 int mapped = 1; /* logical is mapped? */ 1150 int orig_height; 1151 int extent_uninit = 0; 1152 int prev_uninit = 0; 1153 int next_uninit = 0; 1154 int new_uninit = 0; 1155 int max_len = EXT_INIT_MAX_LEN; 1156 int has_prev, has_next; 1157 blk64_t orig_lblk; 1158 struct extent_path *path; 1159 struct ext2fs_extent extent, next_extent, prev_extent; 1160 struct ext2fs_extent newextent; 1161 struct ext2_extent_info info; 1162 1163 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1164 1165 #ifdef DEBUG 1166 printf("set_bmap ino %u log %lld phys %lld flags %d\n", 1167 handle->ino, logical, physical, flags); 1168 #endif 1169 1170 if (!(handle->fs->flags & EXT2_FLAG_RW)) 1171 return EXT2_ET_RO_FILSYS; 1172 1173 if (!handle->path) 1174 return EXT2_ET_NO_CURRENT_NODE; 1175 1176 path = handle->path + handle->level; 1177 1178 if (flags & EXT2_EXTENT_SET_BMAP_UNINIT) { 1179 new_uninit = 1; 1180 max_len = EXT_UNINIT_MAX_LEN; 1181 } 1182 1183 /* if (re)mapping, set up new extent to insert */ 1184 if (physical) { 1185 newextent.e_len = 1; 1186 newextent.e_pblk = physical; 1187 newextent.e_lblk = logical; 1188 newextent.e_flags = EXT2_EXTENT_FLAGS_LEAF; 1189 if (new_uninit) 1190 newextent.e_flags |= EXT2_EXTENT_FLAGS_UNINIT; 1191 } 1192 1193 /* special case if the extent tree is completely empty */ 1194 if ((handle->max_depth == 0) && (path->entries == 0)) { 1195 retval = ext2fs_extent_insert(handle, 0, &newextent); 1196 return retval; 1197 } 1198 1199 /* save our original location in the extent tree */ 1200 if ((retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, 1201 &extent))) { 1202 if (retval != EXT2_ET_NO_CURRENT_NODE) 1203 return retval; 1204 memset(&extent, 0, sizeof(extent)); 1205 } 1206 if ((retval = ext2fs_extent_get_info(handle, &info))) 1207 return retval; 1208 orig_height = info.max_depth - info.curr_level; 1209 orig_lblk = extent.e_lblk; 1210 1211 /* go to the logical spot we want to (re/un)map */ 1212 retval = ext2fs_extent_goto(handle, logical); 1213 if (retval) { 1214 if (retval == EXT2_ET_EXTENT_NOT_FOUND) { 1215 retval = 0; 1216 mapped = 0; 1217 if (!physical) { 1218 #ifdef DEBUG 1219 printf("block %llu already unmapped\n", 1220 logical); 1221 #endif 1222 goto done; 1223 } 1224 } else 1225 goto done; 1226 } 1227 1228 /* 1229 * This may be the extent *before* the requested logical, 1230 * if it's currently unmapped. 1231 * 1232 * Get the previous and next leaf extents, if they are present. 1233 */ 1234 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 1235 if (retval) 1236 goto done; 1237 if (extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 1238 extent_uninit = 1; 1239 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_LEAF, &next_extent); 1240 if (retval) { 1241 has_next = 0; 1242 if (retval != EXT2_ET_EXTENT_NO_NEXT) 1243 goto done; 1244 } else { 1245 dbg_print_extent("set_bmap: next_extent", 1246 &next_extent); 1247 has_next = 1; 1248 if (next_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 1249 next_uninit = 1; 1250 } 1251 retval = ext2fs_extent_goto(handle, logical); 1252 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND) 1253 goto done; 1254 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_LEAF, &prev_extent); 1255 if (retval) { 1256 has_prev = 0; 1257 if (retval != EXT2_ET_EXTENT_NO_PREV) 1258 goto done; 1259 } else { 1260 has_prev = 1; 1261 dbg_print_extent("set_bmap: prev_extent", 1262 &prev_extent); 1263 if (prev_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 1264 prev_uninit = 1; 1265 } 1266 retval = ext2fs_extent_goto(handle, logical); 1267 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND) 1268 goto done; 1269 1270 /* check if already pointing to the requested physical */ 1271 if (mapped && (new_uninit == extent_uninit) && 1272 (extent.e_pblk + (logical - extent.e_lblk) == physical)) { 1273 #ifdef DEBUG 1274 printf("physical block (at %llu) unchanged\n", logical); 1275 #endif 1276 goto done; 1277 } 1278 1279 if (!mapped) { 1280 #ifdef DEBUG 1281 printf("mapping unmapped logical block %llu\n", logical); 1282 #endif 1283 if ((logical == extent.e_lblk + extent.e_len) && 1284 (physical == extent.e_pblk + extent.e_len) && 1285 (new_uninit == extent_uninit) && 1286 ((int) extent.e_len < max_len-1)) { 1287 extent.e_len++; 1288 retval = ext2fs_extent_replace(handle, 0, &extent); 1289 } else if ((logical == extent.e_lblk - 1) && 1290 (physical == extent.e_pblk - 1) && 1291 (new_uninit == extent_uninit) && 1292 ((int) extent.e_len < max_len - 1)) { 1293 extent.e_len++; 1294 extent.e_lblk--; 1295 extent.e_pblk--; 1296 retval = ext2fs_extent_replace(handle, 0, &extent); 1297 } else if (has_next && 1298 (logical == next_extent.e_lblk - 1) && 1299 (physical == next_extent.e_pblk - 1) && 1300 (new_uninit == next_uninit) && 1301 ((int) next_extent.e_len < max_len - 1)) { 1302 retval = ext2fs_extent_get(handle, 1303 EXT2_EXTENT_NEXT_LEAF, 1304 &next_extent); 1305 if (retval) 1306 goto done; 1307 next_extent.e_len++; 1308 next_extent.e_lblk--; 1309 next_extent.e_pblk--; 1310 retval = ext2fs_extent_replace(handle, 0, &next_extent); 1311 } else if (logical < extent.e_lblk) 1312 retval = ext2fs_extent_insert(handle, 0, &newextent); 1313 else 1314 retval = ext2fs_extent_insert(handle, 1315 EXT2_EXTENT_INSERT_AFTER, &newextent); 1316 if (retval) 1317 goto done; 1318 retval = ext2fs_extent_fix_parents(handle); 1319 if (retval) 1320 goto done; 1321 } else if ((logical == extent.e_lblk) && (extent.e_len == 1)) { 1322 #ifdef DEBUG 1323 printf("(re/un)mapping only block in extent\n"); 1324 #endif 1325 if (physical) { 1326 retval = ext2fs_extent_replace(handle, 0, &newextent); 1327 } else { 1328 retval = ext2fs_extent_delete(handle, 0); 1329 if (retval) 1330 goto done; 1331 ec = ext2fs_extent_fix_parents(handle); 1332 if (ec != EXT2_ET_NO_CURRENT_NODE) 1333 retval = ec; 1334 } 1335 1336 if (retval) 1337 goto done; 1338 } else if (logical == extent.e_lblk + extent.e_len - 1) { 1339 #ifdef DEBUG 1340 printf("(re/un)mapping last block in extent\n"); 1341 #endif 1342 if (physical) { 1343 if (has_next && 1344 (logical == (next_extent.e_lblk - 1)) && 1345 (physical == (next_extent.e_pblk - 1)) && 1346 (new_uninit == next_uninit) && 1347 ((int) next_extent.e_len < max_len - 1)) { 1348 retval = ext2fs_extent_get(handle, 1349 EXT2_EXTENT_NEXT_LEAF, &next_extent); 1350 if (retval) 1351 goto done; 1352 next_extent.e_len++; 1353 next_extent.e_lblk--; 1354 next_extent.e_pblk--; 1355 retval = ext2fs_extent_replace(handle, 0, 1356 &next_extent); 1357 if (retval) 1358 goto done; 1359 retval = ext2fs_extent_fix_parents(handle); 1360 if (retval) 1361 goto done; 1362 } else 1363 retval = ext2fs_extent_insert(handle, 1364 EXT2_EXTENT_INSERT_AFTER, &newextent); 1365 if (retval) 1366 goto done; 1367 /* Now pointing at inserted extent; move back to prev */ 1368 retval = ext2fs_extent_get(handle, 1369 EXT2_EXTENT_PREV_LEAF, 1370 &extent); 1371 if (retval) 1372 goto done; 1373 } 1374 extent.e_len--; 1375 retval = ext2fs_extent_replace(handle, 0, &extent); 1376 if (retval) 1377 goto done; 1378 } else if (logical == extent.e_lblk) { 1379 #ifdef DEBUG 1380 printf("(re/un)mapping first block in extent\n"); 1381 #endif 1382 if (physical) { 1383 if (has_prev && 1384 (logical == (prev_extent.e_lblk + 1385 prev_extent.e_len)) && 1386 (physical == (prev_extent.e_pblk + 1387 prev_extent.e_len)) && 1388 (new_uninit == prev_uninit) && 1389 ((int) prev_extent.e_len < max_len-1)) { 1390 retval = ext2fs_extent_get(handle, 1391 EXT2_EXTENT_PREV_LEAF, &prev_extent); 1392 if (retval) 1393 goto done; 1394 prev_extent.e_len++; 1395 retval = ext2fs_extent_replace(handle, 0, 1396 &prev_extent); 1397 } else 1398 retval = ext2fs_extent_insert(handle, 1399 0, &newextent); 1400 if (retval) 1401 goto done; 1402 retval = ext2fs_extent_get(handle, 1403 EXT2_EXTENT_NEXT_LEAF, 1404 &extent); 1405 if (retval) 1406 goto done; 1407 } 1408 extent.e_pblk++; 1409 extent.e_lblk++; 1410 extent.e_len--; 1411 retval = ext2fs_extent_replace(handle, 0, &extent); 1412 if (retval) 1413 goto done; 1414 retval = ext2fs_extent_fix_parents(handle); 1415 if (retval) 1416 goto done; 1417 } else { 1418 __u32 orig_length; 1419 1420 #ifdef DEBUG 1421 printf("(re/un)mapping in middle of extent\n"); 1422 #endif 1423 /* need to split this extent; later */ 1424 1425 orig_length = extent.e_len; 1426 1427 /* shorten pre-split extent */ 1428 extent.e_len = (logical - extent.e_lblk); 1429 retval = ext2fs_extent_replace(handle, 0, &extent); 1430 if (retval) 1431 goto done; 1432 /* insert our new extent, if any */ 1433 if (physical) { 1434 /* insert new extent after current */ 1435 retval = ext2fs_extent_insert(handle, 1436 EXT2_EXTENT_INSERT_AFTER, &newextent); 1437 if (retval) 1438 goto done; 1439 } 1440 /* add post-split extent */ 1441 extent.e_pblk += extent.e_len + 1; 1442 extent.e_lblk += extent.e_len + 1; 1443 extent.e_len = orig_length - extent.e_len - 1; 1444 retval = ext2fs_extent_insert(handle, 1445 EXT2_EXTENT_INSERT_AFTER, &extent); 1446 if (retval) 1447 goto done; 1448 } 1449 1450 done: 1451 /* get handle back to its position */ 1452 if (orig_height > handle->max_depth) 1453 orig_height = handle->max_depth; /* In case we shortened the tree */ 1454 ext2fs_extent_goto2(handle, orig_height, orig_lblk); 1455 return retval; 1456 } 1457 1458 errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags) 1459 { 1460 struct extent_path *path; 1461 char *cp; 1462 struct ext3_extent_header *eh; 1463 errcode_t retval = 0; 1464 1465 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1466 1467 if (!(handle->fs->flags & EXT2_FLAG_RW)) 1468 return EXT2_ET_RO_FILSYS; 1469 1470 if (!handle->path) 1471 return EXT2_ET_NO_CURRENT_NODE; 1472 1473 #ifdef DEBUG 1474 { 1475 struct ext2fs_extent extent; 1476 1477 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, 1478 &extent); 1479 if (retval == 0) { 1480 printf("extent delete %u ", handle->ino); 1481 dbg_print_extent(0, &extent); 1482 } 1483 } 1484 #endif 1485 1486 path = handle->path + handle->level; 1487 if (!path->curr) 1488 return EXT2_ET_NO_CURRENT_NODE; 1489 1490 cp = path->curr; 1491 1492 if (path->left) { 1493 memmove(cp, cp + sizeof(struct ext3_extent_idx), 1494 path->left * sizeof(struct ext3_extent_idx)); 1495 path->left--; 1496 } else { 1497 struct ext3_extent_idx *ix = path->curr; 1498 ix--; 1499 path->curr = ix; 1500 } 1501 if (--path->entries == 0) 1502 path->curr = 0; 1503 1504 /* if non-root node has no entries left, remove it & parent ptr to it */ 1505 if (path->entries == 0 && handle->level) { 1506 if (!(flags & EXT2_EXTENT_DELETE_KEEP_EMPTY)) { 1507 struct ext2fs_extent extent; 1508 1509 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, 1510 &extent); 1511 if (retval) 1512 return retval; 1513 1514 retval = ext2fs_extent_delete(handle, flags); 1515 handle->inode->i_blocks -= 1516 (handle->fs->blocksize * 1517 EXT2FS_CLUSTER_RATIO(handle->fs)) / 512; 1518 retval = ext2fs_write_inode(handle->fs, handle->ino, 1519 handle->inode); 1520 ext2fs_block_alloc_stats2(handle->fs, 1521 extent.e_pblk, -1); 1522 } 1523 } else { 1524 eh = (struct ext3_extent_header *) path->buf; 1525 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 1526 if ((path->entries == 0) && (handle->level == 0)) 1527 eh->eh_depth = handle->max_depth = 0; 1528 retval = update_path(handle); 1529 } 1530 return retval; 1531 } 1532 1533 errcode_t ext2fs_extent_get_info(ext2_extent_handle_t handle, 1534 struct ext2_extent_info *info) 1535 { 1536 struct extent_path *path; 1537 1538 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1539 1540 memset(info, 0, sizeof(struct ext2_extent_info)); 1541 1542 path = handle->path + handle->level; 1543 if (path) { 1544 if (path->curr) 1545 info->curr_entry = ((char *) path->curr - path->buf) / 1546 sizeof(struct ext3_extent_idx); 1547 else 1548 info->curr_entry = 0; 1549 info->num_entries = path->entries; 1550 info->max_entries = path->max_entries; 1551 info->bytes_avail = (path->max_entries - path->entries) * 1552 sizeof(struct ext3_extent); 1553 } 1554 1555 info->curr_level = handle->level; 1556 info->max_depth = handle->max_depth; 1557 info->max_lblk = ((__u64) 1 << 32) - 1; 1558 info->max_pblk = ((__u64) 1 << 48) - 1; 1559 info->max_len = (1UL << 15); 1560 info->max_uninit_len = (1UL << 15) - 1; 1561 1562 return 0; 1563 } 1564 1565 #ifdef DEBUG 1566 /* 1567 * Override debugfs's prompt 1568 */ 1569 const char *debug_prog_name = "tst_extents"; 1570 1571 #endif 1572 1573
