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 int type; 57 int level; 58 int max_depth; 59 struct extent_path *path; 60 }; 61 62 struct ext2_extent_path { 63 errcode_t magic; 64 int leaf_height; 65 blk64_t lblk; 66 }; 67 68 /* 69 * Useful Debugging stuff 70 */ 71 72 #ifdef DEBUG 73 static void dbg_show_header(struct ext3_extent_header *eh) 74 { 75 printf("header: magic=%x entries=%u max=%u depth=%u generation=%u\n", 76 ext2fs_le16_to_cpu(eh->eh_magic), 77 ext2fs_le16_to_cpu(eh->eh_entries), 78 ext2fs_le16_to_cpu(eh->eh_max), 79 ext2fs_le16_to_cpu(eh->eh_depth), 80 ext2fs_le32_to_cpu(eh->eh_generation)); 81 } 82 83 static void dbg_show_index(struct ext3_extent_idx *ix) 84 { 85 printf("index: block=%u leaf=%u leaf_hi=%u unused=%u\n", 86 ext2fs_le32_to_cpu(ix->ei_block), 87 ext2fs_le32_to_cpu(ix->ei_leaf), 88 ext2fs_le16_to_cpu(ix->ei_leaf_hi), 89 ext2fs_le16_to_cpu(ix->ei_unused)); 90 } 91 92 static void dbg_show_extent(struct ext3_extent *ex) 93 { 94 printf("extent: block=%u-%u len=%u start=%u start_hi=%u\n", 95 ext2fs_le32_to_cpu(ex->ee_block), 96 ext2fs_le32_to_cpu(ex->ee_block) + 97 ext2fs_le16_to_cpu(ex->ee_len) - 1, 98 ext2fs_le16_to_cpu(ex->ee_len), 99 ext2fs_le32_to_cpu(ex->ee_start), 100 ext2fs_le16_to_cpu(ex->ee_start_hi)); 101 } 102 103 static void dbg_print_extent(char *desc, struct ext2fs_extent *extent) 104 { 105 if (desc) 106 printf("%s: ", desc); 107 printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ", 108 extent->e_lblk, extent->e_lblk + extent->e_len - 1, 109 extent->e_len, extent->e_pblk); 110 if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF) 111 fputs("LEAF ", stdout); 112 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) 113 fputs("UNINIT ", stdout); 114 if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT) 115 fputs("2ND_VISIT ", stdout); 116 if (!extent->e_flags) 117 fputs("(none)", stdout); 118 fputc('\n', stdout); 119 120 } 121 122 #else 123 #define dbg_show_header(eh) do { } while (0) 124 #define dbg_show_index(ix) do { } while (0) 125 #define dbg_show_extent(ex) do { } while (0) 126 #define dbg_print_extent(desc, ex) do { } while (0) 127 #endif 128 129 /* 130 * Verify the extent header as being sane 131 */ 132 errcode_t ext2fs_extent_header_verify(void *ptr, int size) 133 { 134 int eh_max, entry_size; 135 struct ext3_extent_header *eh = ptr; 136 137 dbg_show_header(eh); 138 if (ext2fs_le16_to_cpu(eh->eh_magic) != EXT3_EXT_MAGIC) 139 return EXT2_ET_EXTENT_HEADER_BAD; 140 if (ext2fs_le16_to_cpu(eh->eh_entries) > ext2fs_le16_to_cpu(eh->eh_max)) 141 return EXT2_ET_EXTENT_HEADER_BAD; 142 if (eh->eh_depth == 0) 143 entry_size = sizeof(struct ext3_extent); 144 else 145 entry_size = sizeof(struct ext3_extent_idx); 146 147 eh_max = (size - sizeof(*eh)) / entry_size; 148 /* Allow two extent-sized items at the end of the block, for 149 * ext4_extent_tail with checksum in the future. */ 150 if ((ext2fs_le16_to_cpu(eh->eh_max) > eh_max) || 151 (ext2fs_le16_to_cpu(eh->eh_max) < (eh_max - 2))) 152 return EXT2_ET_EXTENT_HEADER_BAD; 153 154 return 0; 155 } 156 157 158 /* 159 * Begin functions to handle an inode's extent information 160 */ 161 extern void ext2fs_extent_free(ext2_extent_handle_t handle) 162 { 163 int i; 164 165 if (!handle) 166 return; 167 168 if (handle->inode) 169 ext2fs_free_mem(&handle->inode); 170 if (handle->path) { 171 for (i=1; i <= handle->max_depth; i++) { 172 if (handle->path[i].buf) 173 ext2fs_free_mem(&handle->path[i].buf); 174 } 175 ext2fs_free_mem(&handle->path); 176 } 177 ext2fs_free_mem(&handle); 178 } 179 180 extern errcode_t ext2fs_extent_open(ext2_filsys fs, ext2_ino_t ino, 181 ext2_extent_handle_t *ret_handle) 182 { 183 return ext2fs_extent_open2(fs, ino, NULL, ret_handle); 184 } 185 186 extern errcode_t ext2fs_extent_open2(ext2_filsys fs, ext2_ino_t ino, 187 struct ext2_inode *inode, 188 ext2_extent_handle_t *ret_handle) 189 { 190 struct ext2_extent_handle *handle; 191 errcode_t retval; 192 int i; 193 struct ext3_extent_header *eh; 194 195 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 196 197 if (!inode) 198 if ((ino == 0) || (ino > fs->super->s_inodes_count)) 199 return EXT2_ET_BAD_INODE_NUM; 200 201 retval = ext2fs_get_mem(sizeof(struct ext2_extent_handle), &handle); 202 if (retval) 203 return retval; 204 memset(handle, 0, sizeof(struct ext2_extent_handle)); 205 206 retval = ext2fs_get_mem(sizeof(struct ext2_inode), &handle->inode); 207 if (retval) 208 goto errout; 209 210 handle->ino = ino; 211 handle->fs = fs; 212 213 if (inode) { 214 memcpy(handle->inode, inode, sizeof(struct ext2_inode)); 215 } 216 else { 217 retval = ext2fs_read_inode(fs, ino, handle->inode); 218 if (retval) 219 goto errout; 220 } 221 222 eh = (struct ext3_extent_header *) &handle->inode->i_block[0]; 223 224 for (i=0; i < EXT2_N_BLOCKS; i++) 225 if (handle->inode->i_block[i]) 226 break; 227 if (i >= EXT2_N_BLOCKS) { 228 eh->eh_magic = ext2fs_cpu_to_le16(EXT3_EXT_MAGIC); 229 eh->eh_depth = 0; 230 eh->eh_entries = 0; 231 i = (sizeof(handle->inode->i_block) - sizeof(*eh)) / 232 sizeof(struct ext3_extent); 233 eh->eh_max = ext2fs_cpu_to_le16(i); 234 handle->inode->i_flags |= EXT4_EXTENTS_FL; 235 } 236 237 if (!(handle->inode->i_flags & EXT4_EXTENTS_FL)) { 238 retval = EXT2_ET_INODE_NOT_EXTENT; 239 goto errout; 240 } 241 242 retval = ext2fs_extent_header_verify(eh, sizeof(handle->inode->i_block)); 243 if (retval) 244 goto errout; 245 246 handle->max_depth = ext2fs_le16_to_cpu(eh->eh_depth); 247 handle->type = ext2fs_le16_to_cpu(eh->eh_magic); 248 249 retval = ext2fs_get_mem(((handle->max_depth+1) * 250 sizeof(struct extent_path)), 251 &handle->path); 252 memset(handle->path, 0, 253 (handle->max_depth+1) * sizeof(struct extent_path)); 254 handle->path[0].buf = (char *) handle->inode->i_block; 255 256 handle->path[0].left = handle->path[0].entries = 257 ext2fs_le16_to_cpu(eh->eh_entries); 258 handle->path[0].max_entries = ext2fs_le16_to_cpu(eh->eh_max); 259 handle->path[0].curr = 0; 260 handle->path[0].end_blk = 261 ((((__u64) handle->inode->i_size_high << 32) + 262 handle->inode->i_size + (fs->blocksize - 1)) 263 >> EXT2_BLOCK_SIZE_BITS(fs->super)); 264 handle->path[0].visit_num = 1; 265 handle->level = 0; 266 handle->magic = EXT2_ET_MAGIC_EXTENT_HANDLE; 267 268 *ret_handle = handle; 269 return 0; 270 271 errout: 272 ext2fs_extent_free(handle); 273 return retval; 274 } 275 276 /* 277 * This function is responsible for (optionally) moving through the 278 * extent tree and then returning the current extent 279 */ 280 errcode_t ext2fs_extent_get(ext2_extent_handle_t handle, 281 int flags, struct ext2fs_extent *extent) 282 { 283 struct extent_path *path, *newpath; 284 struct ext3_extent_header *eh; 285 struct ext3_extent_idx *ix = 0; 286 struct ext3_extent *ex; 287 errcode_t retval; 288 blk_t blk; 289 blk64_t end_blk; 290 int orig_op, op; 291 292 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 293 294 if (!handle->path) 295 return EXT2_ET_NO_CURRENT_NODE; 296 297 orig_op = op = flags & EXT2_EXTENT_MOVE_MASK; 298 299 retry: 300 path = handle->path + handle->level; 301 if ((orig_op == EXT2_EXTENT_NEXT) || 302 (orig_op == EXT2_EXTENT_NEXT_LEAF)) { 303 if (handle->level < handle->max_depth) { 304 /* interior node */ 305 if (path->visit_num == 0) { 306 path->visit_num++; 307 op = EXT2_EXTENT_DOWN; 308 } else if (path->left > 0) 309 op = EXT2_EXTENT_NEXT_SIB; 310 else if (handle->level > 0) 311 op = EXT2_EXTENT_UP; 312 else 313 return EXT2_ET_EXTENT_NO_NEXT; 314 } else { 315 /* leaf node */ 316 if (path->left > 0) 317 op = EXT2_EXTENT_NEXT_SIB; 318 else if (handle->level > 0) 319 op = EXT2_EXTENT_UP; 320 else 321 return EXT2_ET_EXTENT_NO_NEXT; 322 } 323 if (op != EXT2_EXTENT_NEXT_SIB) { 324 #ifdef DEBUG_GET_EXTENT 325 printf("<<<< OP = %s\n", 326 (op == EXT2_EXTENT_DOWN) ? "down" : 327 ((op == EXT2_EXTENT_UP) ? "up" : "unknown")); 328 #endif 329 } 330 } 331 332 if ((orig_op == EXT2_EXTENT_PREV) || 333 (orig_op == EXT2_EXTENT_PREV_LEAF)) { 334 if (handle->level < handle->max_depth) { 335 /* interior node */ 336 if (path->visit_num > 0 ) { 337 /* path->visit_num = 0; */ 338 op = EXT2_EXTENT_DOWN_AND_LAST; 339 } else if (path->left < path->entries-1) 340 op = EXT2_EXTENT_PREV_SIB; 341 else if (handle->level > 0) 342 op = EXT2_EXTENT_UP; 343 else 344 return EXT2_ET_EXTENT_NO_PREV; 345 } else { 346 /* leaf node */ 347 if (path->left < path->entries-1) 348 op = EXT2_EXTENT_PREV_SIB; 349 else if (handle->level > 0) 350 op = EXT2_EXTENT_UP; 351 else 352 return EXT2_ET_EXTENT_NO_PREV; 353 } 354 if (op != EXT2_EXTENT_PREV_SIB) { 355 #ifdef DEBUG_GET_EXTENT 356 printf("<<<< OP = %s\n", 357 (op == EXT2_EXTENT_DOWN_AND_LAST) ? "down/last" : 358 ((op == EXT2_EXTENT_UP) ? "up" : "unknown")); 359 #endif 360 } 361 } 362 363 if (orig_op == EXT2_EXTENT_LAST_LEAF) { 364 if ((handle->level < handle->max_depth) && 365 (path->left == 0)) 366 op = EXT2_EXTENT_DOWN; 367 else 368 op = EXT2_EXTENT_LAST_SIB; 369 #ifdef DEBUG_GET_EXTENT 370 printf("<<<< OP = %s\n", 371 (op == EXT2_EXTENT_DOWN) ? "down" : "last_sib"); 372 #endif 373 } 374 375 switch (op) { 376 case EXT2_EXTENT_CURRENT: 377 ix = path->curr; 378 break; 379 case EXT2_EXTENT_ROOT: 380 handle->level = 0; 381 path = handle->path + handle->level; 382 case EXT2_EXTENT_FIRST_SIB: 383 path->left = path->entries; 384 path->curr = 0; 385 case EXT2_EXTENT_NEXT_SIB: 386 if (path->left <= 0) 387 return EXT2_ET_EXTENT_NO_NEXT; 388 if (path->curr) { 389 ix = path->curr; 390 ix++; 391 } else { 392 eh = (struct ext3_extent_header *) path->buf; 393 ix = EXT_FIRST_INDEX(eh); 394 } 395 path->left--; 396 path->curr = ix; 397 path->visit_num = 0; 398 break; 399 case EXT2_EXTENT_PREV_SIB: 400 if (!path->curr || 401 path->left+1 >= path->entries) 402 return EXT2_ET_EXTENT_NO_PREV; 403 ix = path->curr; 404 ix--; 405 path->curr = ix; 406 path->left++; 407 if (handle->level < handle->max_depth) 408 path->visit_num = 1; 409 break; 410 case EXT2_EXTENT_LAST_SIB: 411 eh = (struct ext3_extent_header *) path->buf; 412 path->curr = EXT_LAST_EXTENT(eh); 413 ix = path->curr; 414 path->left = 0; 415 path->visit_num = 0; 416 break; 417 case EXT2_EXTENT_UP: 418 if (handle->level <= 0) 419 return EXT2_ET_EXTENT_NO_UP; 420 handle->level--; 421 path--; 422 ix = path->curr; 423 if ((orig_op == EXT2_EXTENT_PREV) || 424 (orig_op == EXT2_EXTENT_PREV_LEAF)) 425 path->visit_num = 0; 426 break; 427 case EXT2_EXTENT_DOWN: 428 case EXT2_EXTENT_DOWN_AND_LAST: 429 if (!path->curr ||(handle->level >= handle->max_depth)) 430 return EXT2_ET_EXTENT_NO_DOWN; 431 432 ix = path->curr; 433 newpath = path + 1; 434 if (!newpath->buf) { 435 retval = ext2fs_get_mem(handle->fs->blocksize, 436 &newpath->buf); 437 if (retval) 438 return retval; 439 } 440 blk = ext2fs_le32_to_cpu(ix->ei_leaf) + 441 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32); 442 if ((handle->fs->flags & EXT2_FLAG_IMAGE_FILE) && 443 (handle->fs->io != handle->fs->image_io)) 444 memset(newpath->buf, 0, handle->fs->blocksize); 445 else { 446 retval = io_channel_read_blk(handle->fs->io, 447 blk, 1, newpath->buf); 448 if (retval) 449 return retval; 450 } 451 handle->level++; 452 453 eh = (struct ext3_extent_header *) newpath->buf; 454 455 retval = ext2fs_extent_header_verify(eh, handle->fs->blocksize); 456 if (retval) { 457 handle->level--; 458 return retval; 459 } 460 461 newpath->left = newpath->entries = 462 ext2fs_le16_to_cpu(eh->eh_entries); 463 newpath->max_entries = ext2fs_le16_to_cpu(eh->eh_max); 464 465 if (path->left > 0) { 466 ix++; 467 newpath->end_blk = ext2fs_le32_to_cpu(ix->ei_block); 468 } else 469 newpath->end_blk = path->end_blk; 470 471 path = newpath; 472 if (op == EXT2_EXTENT_DOWN) { 473 ix = EXT_FIRST_INDEX((struct ext3_extent_header *) eh); 474 path->curr = ix; 475 path->left = path->entries - 1; 476 path->visit_num = 0; 477 } else { 478 ix = EXT_LAST_INDEX((struct ext3_extent_header *) eh); 479 path->curr = ix; 480 path->left = 0; 481 if (handle->level < handle->max_depth) 482 path->visit_num = 1; 483 } 484 #ifdef DEBUG_GET_EXTENT 485 printf("Down to level %d/%d, end_blk=%llu\n", 486 handle->level, handle->max_depth, 487 path->end_blk); 488 #endif 489 break; 490 default: 491 return EXT2_ET_OP_NOT_SUPPORTED; 492 } 493 494 if (!ix) 495 return EXT2_ET_NO_CURRENT_NODE; 496 497 extent->e_flags = 0; 498 #ifdef DEBUG_GET_EXTENT 499 printf("(Left %d)\n", path->left); 500 #endif 501 502 if (handle->level == handle->max_depth) { 503 ex = (struct ext3_extent *) ix; 504 505 extent->e_pblk = ext2fs_le32_to_cpu(ex->ee_start) + 506 ((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32); 507 extent->e_lblk = ext2fs_le32_to_cpu(ex->ee_block); 508 extent->e_len = ext2fs_le16_to_cpu(ex->ee_len); 509 extent->e_flags |= EXT2_EXTENT_FLAGS_LEAF; 510 if (extent->e_len > EXT_INIT_MAX_LEN) { 511 extent->e_len -= EXT_INIT_MAX_LEN; 512 extent->e_flags |= EXT2_EXTENT_FLAGS_UNINIT; 513 } 514 } else { 515 extent->e_pblk = ext2fs_le32_to_cpu(ix->ei_leaf) + 516 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32); 517 extent->e_lblk = ext2fs_le32_to_cpu(ix->ei_block); 518 if (path->left > 0) { 519 ix++; 520 end_blk = ext2fs_le32_to_cpu(ix->ei_block); 521 } else 522 end_blk = path->end_blk; 523 524 extent->e_len = end_blk - extent->e_lblk; 525 } 526 if (path->visit_num) 527 extent->e_flags |= EXT2_EXTENT_FLAGS_SECOND_VISIT; 528 529 if (((orig_op == EXT2_EXTENT_NEXT_LEAF) || 530 (orig_op == EXT2_EXTENT_PREV_LEAF)) && 531 (handle->level != handle->max_depth)) 532 goto retry; 533 534 if ((orig_op == EXT2_EXTENT_LAST_LEAF) && 535 ((handle->level != handle->max_depth) || 536 (path->left != 0))) 537 goto retry; 538 539 return 0; 540 } 541 542 static errcode_t update_path(ext2_extent_handle_t handle) 543 { 544 blk64_t blk; 545 errcode_t retval; 546 struct ext3_extent_idx *ix; 547 548 if (handle->level == 0) { 549 retval = ext2fs_write_inode(handle->fs, handle->ino, 550 handle->inode); 551 } else { 552 ix = handle->path[handle->level - 1].curr; 553 blk = ext2fs_le32_to_cpu(ix->ei_leaf) + 554 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32); 555 556 retval = io_channel_write_blk(handle->fs->io, 557 blk, 1, handle->path[handle->level].buf); 558 } 559 return retval; 560 } 561 562 #if 0 563 errcode_t ext2fs_extent_save_path(ext2_extent_handle_t handle, 564 ext2_extent_path_t *ret_path) 565 { 566 ext2_extent_path_t save_path; 567 struct ext2fs_extent extent; 568 struct ext2_extent_info info; 569 errcode_t retval; 570 571 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 572 if (retval) 573 return retval; 574 575 retval = ext2fs_extent_get_info(handle, &info); 576 if (retval) 577 return retval; 578 579 retval = ext2fs_get_mem(sizeof(struct ext2_extent_path), &save_path); 580 if (retval) 581 return retval; 582 memset(save_path, 0, sizeof(struct ext2_extent_path)); 583 584 save_path->magic = EXT2_ET_MAGIC_EXTENT_PATH; 585 save_path->leaf_height = info.max_depth - info.curr_level - 1; 586 save_path->lblk = extent.e_lblk; 587 588 *ret_path = save_path; 589 return 0; 590 } 591 592 errcode_t ext2fs_extent_free_path(ext2_extent_path_t path) 593 { 594 EXT2_CHECK_MAGIC(path, EXT2_ET_MAGIC_EXTENT_PATH); 595 596 ext2fs_free_mem(&path); 597 return 0; 598 } 599 #endif 600 601 /* 602 * Go to the node at leaf_level which contains logical block blk. 603 * 604 * leaf_level is height from the leaf node level, i.e. 605 * leaf_level 0 is at leaf node, leaf_level 1 is 1 above etc. 606 * 607 * If "blk" has no mapping (hole) then handle is left at last 608 * extent before blk. 609 */ 610 static errcode_t extent_goto(ext2_extent_handle_t handle, 611 int leaf_level, blk64_t blk) 612 { 613 struct ext2fs_extent extent; 614 errcode_t retval; 615 616 retval = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent); 617 if (retval) { 618 if (retval == EXT2_ET_EXTENT_NO_NEXT) 619 retval = EXT2_ET_EXTENT_NOT_FOUND; 620 return retval; 621 } 622 623 if (leaf_level > handle->max_depth) { 624 #ifdef DEBUG 625 printf("leaf level %d greater than tree depth %d\n", 626 leaf_level, handle->max_depth); 627 #endif 628 return EXT2_ET_OP_NOT_SUPPORTED; 629 } 630 631 #ifdef DEBUG 632 printf("goto extent ino %u, level %d, %llu\n", handle->ino, 633 leaf_level, blk); 634 #endif 635 636 #ifdef DEBUG_GOTO_EXTENTS 637 dbg_print_extent("root", &extent); 638 #endif 639 while (1) { 640 if (handle->max_depth - handle->level == leaf_level) { 641 /* block is in this &extent */ 642 if ((blk >= extent.e_lblk) && 643 (blk < extent.e_lblk + extent.e_len)) 644 return 0; 645 if (blk < extent.e_lblk) { 646 retval = ext2fs_extent_get(handle, 647 EXT2_EXTENT_PREV_SIB, 648 &extent); 649 return EXT2_ET_EXTENT_NOT_FOUND; 650 } 651 retval = ext2fs_extent_get(handle, 652 EXT2_EXTENT_NEXT_SIB, 653 &extent); 654 if (retval == EXT2_ET_EXTENT_NO_NEXT) 655 return EXT2_ET_EXTENT_NOT_FOUND; 656 if (retval) 657 return retval; 658 continue; 659 } 660 661 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_SIB, 662 &extent); 663 if (retval == EXT2_ET_EXTENT_NO_NEXT) 664 goto go_down; 665 if (retval) 666 return retval; 667 668 #ifdef DEBUG_GOTO_EXTENTS 669 dbg_print_extent("next", &extent); 670 #endif 671 if (blk == extent.e_lblk) 672 goto go_down; 673 if (blk > extent.e_lblk) 674 continue; 675 676 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_SIB, 677 &extent); 678 if (retval) 679 return retval; 680 681 #ifdef DEBUG_GOTO_EXTENTS 682 dbg_print_extent("prev", &extent); 683 #endif 684 685 go_down: 686 retval = ext2fs_extent_get(handle, EXT2_EXTENT_DOWN, 687 &extent); 688 if (retval) 689 return retval; 690 691 #ifdef DEBUG_GOTO_EXTENTS 692 dbg_print_extent("down", &extent); 693 #endif 694 } 695 } 696 697 errcode_t ext2fs_extent_goto(ext2_extent_handle_t handle, 698 blk64_t blk) 699 { 700 return extent_goto(handle, 0, blk); 701 } 702 703 /* 704 * Traverse back up to root fixing parents of current node as needed. 705 * 706 * If we changed start of first entry in a node, fix parent index start 707 * and so on. 708 * 709 * Safe to call for any position in node; if not at the first entry, 710 * will simply return. 711 */ 712 static errcode_t ext2fs_extent_fix_parents(ext2_extent_handle_t handle) 713 { 714 int retval = 0; 715 blk64_t start; 716 struct extent_path *path; 717 struct ext2fs_extent extent; 718 719 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 720 721 if (!(handle->fs->flags & EXT2_FLAG_RW)) 722 return EXT2_ET_RO_FILSYS; 723 724 if (!handle->path) 725 return EXT2_ET_NO_CURRENT_NODE; 726 727 path = handle->path + handle->level; 728 if (!path->curr) 729 return EXT2_ET_NO_CURRENT_NODE; 730 731 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 732 if (retval) 733 goto done; 734 735 /* modified node's start block */ 736 start = extent.e_lblk; 737 738 /* traverse up until index not first, or startblk matches, or top */ 739 while (handle->level > 0 && 740 (path->left == path->entries - 1)) { 741 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent); 742 if (retval) 743 goto done; 744 if (extent.e_lblk == start) 745 break; 746 path = handle->path + handle->level; 747 extent.e_len += (extent.e_lblk - start); 748 extent.e_lblk = start; 749 retval = ext2fs_extent_replace(handle, 0, &extent); 750 if (retval) 751 goto done; 752 update_path(handle); 753 } 754 755 /* put handle back to where we started */ 756 retval = ext2fs_extent_goto(handle, start); 757 done: 758 return retval; 759 } 760 761 errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle, 762 int flags EXT2FS_ATTR((unused)), 763 struct ext2fs_extent *extent) 764 { 765 struct extent_path *path; 766 struct ext3_extent_idx *ix; 767 struct ext3_extent *ex; 768 769 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 770 771 if (!(handle->fs->flags & EXT2_FLAG_RW)) 772 return EXT2_ET_RO_FILSYS; 773 774 if (!handle->path) 775 return EXT2_ET_NO_CURRENT_NODE; 776 777 path = handle->path + handle->level; 778 if (!path->curr) 779 return EXT2_ET_NO_CURRENT_NODE; 780 781 #ifdef DEBUG 782 printf("extent replace: %u ", handle->ino); 783 dbg_print_extent(0, extent); 784 #endif 785 786 if (handle->level == handle->max_depth) { 787 ex = path->curr; 788 789 ex->ee_block = ext2fs_cpu_to_le32(extent->e_lblk); 790 ex->ee_start = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF); 791 ex->ee_start_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32); 792 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) { 793 if (extent->e_len > EXT_UNINIT_MAX_LEN) 794 return EXT2_ET_EXTENT_INVALID_LENGTH; 795 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len + 796 EXT_INIT_MAX_LEN); 797 } else { 798 if (extent->e_len > EXT_INIT_MAX_LEN) 799 return EXT2_ET_EXTENT_INVALID_LENGTH; 800 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len); 801 } 802 } else { 803 ix = path->curr; 804 805 ix->ei_leaf = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF); 806 ix->ei_leaf_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32); 807 ix->ei_block = ext2fs_cpu_to_le32(extent->e_lblk); 808 ix->ei_unused = 0; 809 } 810 update_path(handle); 811 return 0; 812 } 813 814 /* 815 * allocate a new block, move half the current node to it, and update parent 816 * 817 * handle will be left pointing at original record. 818 */ 819 static errcode_t extent_node_split(ext2_extent_handle_t handle) 820 { 821 errcode_t retval = 0; 822 blk_t new_node_pblk; 823 blk64_t new_node_start; 824 blk64_t orig_lblk; 825 blk64_t goal_blk = 0; 826 int orig_height; 827 char *block_buf = NULL; 828 struct ext2fs_extent extent; 829 struct extent_path *path, *newpath = 0; 830 struct ext3_extent_header *eh, *neweh; 831 int tocopy; 832 int new_root = 0; 833 struct ext2_extent_info info; 834 835 /* basic sanity */ 836 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 837 838 if (!(handle->fs->flags & EXT2_FLAG_RW)) 839 return EXT2_ET_RO_FILSYS; 840 841 if (!handle->path) 842 return EXT2_ET_NO_CURRENT_NODE; 843 844 #ifdef DEBUG 845 printf("splitting node at level %d\n", handle->level); 846 #endif 847 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 848 if (retval) 849 goto done; 850 851 retval = ext2fs_extent_get_info(handle, &info); 852 if (retval) 853 goto done; 854 855 /* save the position we were originally splitting... */ 856 orig_height = info.max_depth - info.curr_level; 857 orig_lblk = extent.e_lblk; 858 859 /* Is there room in the parent for a new entry? */ 860 if (handle->level && 861 (handle->path[handle->level - 1].entries >= 862 handle->path[handle->level - 1].max_entries)) { 863 864 #ifdef DEBUG 865 printf("parent level %d full; splitting it too\n", 866 handle->level - 1); 867 #endif 868 /* split the parent */ 869 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent); 870 if (retval) 871 goto done; 872 goal_blk = extent.e_pblk; 873 874 retval = extent_node_split(handle); 875 if (retval) 876 goto done; 877 878 /* get handle back to our original split position */ 879 retval = extent_goto(handle, orig_height, orig_lblk); 880 if (retval) 881 goto done; 882 } 883 884 /* At this point, parent should have room for this split */ 885 path = handle->path + handle->level; 886 if (!path->curr) 887 return EXT2_ET_NO_CURRENT_NODE; 888 889 /* extent header of the current node we'll split */ 890 eh = (struct ext3_extent_header *)path->buf; 891 892 /* splitting root level means moving them all out */ 893 if (handle->level == 0) { 894 new_root = 1; 895 tocopy = ext2fs_le16_to_cpu(eh->eh_entries); 896 retval = ext2fs_get_mem(((handle->max_depth+2) * 897 sizeof(struct extent_path)), 898 &newpath); 899 if (retval) 900 goto done; 901 memset(newpath, 0, 902 ((handle->max_depth+2) * sizeof(struct extent_path))); 903 } else { 904 tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2; 905 } 906 907 #ifdef DEBUG 908 printf("will copy out %d of %d entries at level %d\n", 909 tocopy, ext2fs_le16_to_cpu(eh->eh_entries), 910 handle->level); 911 #endif 912 913 if (!tocopy) { 914 #ifdef DEBUG 915 printf("Nothing to copy to new block!\n"); 916 #endif 917 retval = EXT2_ET_CANT_SPLIT_EXTENT; 918 goto done; 919 } 920 921 /* first we need a new block, or can do nothing. */ 922 block_buf = malloc(handle->fs->blocksize); 923 if (!block_buf) { 924 retval = ENOMEM; 925 goto done; 926 } 927 928 if (!goal_blk) { 929 dgrp_t group = ext2fs_group_of_ino(handle->fs, handle->ino); 930 __u8 log_flex = handle->fs->super->s_log_groups_per_flex; 931 932 if (log_flex) 933 group = group & ~((1 << (log_flex)) - 1); 934 goal_blk = (group * handle->fs->super->s_blocks_per_group) + 935 handle->fs->super->s_first_data_block; 936 } 937 retval = ext2fs_alloc_block(handle->fs, (blk_t) goal_blk, block_buf, 938 &new_node_pblk); 939 if (retval) 940 goto done; 941 942 #ifdef DEBUG 943 printf("will copy to new node at block %lu\n", 944 (unsigned long) new_node_pblk); 945 #endif 946 947 /* Copy data into new block buffer */ 948 /* First the header for the new block... */ 949 neweh = (struct ext3_extent_header *) block_buf; 950 memcpy(neweh, eh, sizeof(struct ext3_extent_header)); 951 neweh->eh_entries = ext2fs_cpu_to_le16(tocopy); 952 neweh->eh_max = ext2fs_cpu_to_le16((handle->fs->blocksize - 953 sizeof(struct ext3_extent_header)) / 954 sizeof(struct ext3_extent)); 955 956 /* then the entries for the new block... */ 957 memcpy(EXT_FIRST_INDEX(neweh), 958 EXT_FIRST_INDEX(eh) + 959 (ext2fs_le16_to_cpu(eh->eh_entries) - tocopy), 960 sizeof(struct ext3_extent_idx) * tocopy); 961 962 new_node_start = ext2fs_le32_to_cpu(EXT_FIRST_INDEX(neweh)->ei_block); 963 964 /* ...and write the new node block out to disk. */ 965 retval = io_channel_write_blk(handle->fs->io, new_node_pblk, 1, block_buf); 966 967 if (retval) 968 goto done; 969 970 /* OK! we've created the new node; now adjust the tree */ 971 972 /* current path now has fewer active entries, we copied some out */ 973 if (handle->level == 0) { 974 memcpy(newpath, path, 975 sizeof(struct extent_path) * (handle->max_depth+1)); 976 handle->path = newpath; 977 newpath = path; 978 path = handle->path; 979 path->entries = 1; 980 path->left = path->max_entries - 1; 981 handle->max_depth++; 982 eh->eh_depth = ext2fs_cpu_to_le16(handle->max_depth); 983 } else { 984 path->entries -= tocopy; 985 path->left -= tocopy; 986 } 987 988 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 989 /* this writes out the node, incl. the modified header */ 990 retval = update_path(handle); 991 if (retval) 992 goto done; 993 994 /* now go up and insert/replace index for new node we created */ 995 if (new_root) { 996 retval = ext2fs_extent_get(handle, EXT2_EXTENT_FIRST_SIB, &extent); 997 if (retval) 998 goto done; 999 1000 extent.e_lblk = new_node_start; 1001 extent.e_pblk = new_node_pblk; 1002 extent.e_len = handle->path[0].end_blk - extent.e_lblk; 1003 retval = ext2fs_extent_replace(handle, 0, &extent); 1004 if (retval) 1005 goto done; 1006 } else { 1007 __u32 new_node_length; 1008 1009 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent); 1010 /* will insert after this one; it's length is shorter now */ 1011 new_node_length = new_node_start - extent.e_lblk; 1012 extent.e_len -= new_node_length; 1013 retval = ext2fs_extent_replace(handle, 0, &extent); 1014 if (retval) 1015 goto done; 1016 1017 /* now set up the new extent and insert it */ 1018 extent.e_lblk = new_node_start; 1019 extent.e_pblk = new_node_pblk; 1020 extent.e_len = new_node_length; 1021 retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER, &extent); 1022 if (retval) 1023 goto done; 1024 } 1025 1026 /* get handle back to our original position */ 1027 retval = extent_goto(handle, orig_height, orig_lblk); 1028 if (retval) 1029 goto done; 1030 1031 /* new node hooked in, so update inode block count (do this here?) */ 1032 handle->inode->i_blocks += handle->fs->blocksize / 512; 1033 retval = ext2fs_write_inode(handle->fs, handle->ino, 1034 handle->inode); 1035 if (retval) 1036 goto done; 1037 1038 done: 1039 if (newpath) 1040 ext2fs_free_mem(&newpath); 1041 free(block_buf); 1042 1043 return retval; 1044 } 1045 1046 errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags, 1047 struct ext2fs_extent *extent) 1048 { 1049 struct extent_path *path; 1050 struct ext3_extent_idx *ix; 1051 struct ext3_extent_header *eh; 1052 errcode_t retval; 1053 1054 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1055 1056 if (!(handle->fs->flags & EXT2_FLAG_RW)) 1057 return EXT2_ET_RO_FILSYS; 1058 1059 if (!handle->path) 1060 return EXT2_ET_NO_CURRENT_NODE; 1061 1062 #ifdef DEBUG 1063 printf("extent insert: %u ", handle->ino); 1064 dbg_print_extent(0, extent); 1065 #endif 1066 1067 path = handle->path + handle->level; 1068 1069 if (path->entries >= path->max_entries) { 1070 if (flags & EXT2_EXTENT_INSERT_NOSPLIT) { 1071 return EXT2_ET_CANT_INSERT_EXTENT; 1072 } else { 1073 #ifdef DEBUG 1074 printf("node full (level %d) - splitting\n", 1075 handle->level); 1076 #endif 1077 retval = extent_node_split(handle); 1078 if (retval) 1079 return retval; 1080 path = handle->path + handle->level; 1081 } 1082 } 1083 1084 eh = (struct ext3_extent_header *) path->buf; 1085 if (path->curr) { 1086 ix = path->curr; 1087 if (flags & EXT2_EXTENT_INSERT_AFTER) { 1088 ix++; 1089 path->left--; 1090 } 1091 } else 1092 ix = EXT_FIRST_INDEX(eh); 1093 1094 path->curr = ix; 1095 1096 if (path->left >= 0) 1097 memmove(ix + 1, ix, 1098 (path->left+1) * sizeof(struct ext3_extent_idx)); 1099 path->left++; 1100 path->entries++; 1101 1102 eh = (struct ext3_extent_header *) path->buf; 1103 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 1104 1105 retval = ext2fs_extent_replace(handle, 0, extent); 1106 if (retval) 1107 goto errout; 1108 1109 retval = update_path(handle); 1110 if (retval) 1111 goto errout; 1112 1113 return 0; 1114 1115 errout: 1116 ext2fs_extent_delete(handle, 0); 1117 return retval; 1118 } 1119 1120 /* 1121 * Sets the physical block for a logical file block in the extent tree. 1122 * 1123 * May: map unmapped, unmap mapped, or remap mapped blocks. 1124 * 1125 * Mapping an unmapped block adds a single-block extent. 1126 * 1127 * Unmapping first or last block modifies extent in-place 1128 * - But may need to fix parent's starts too in first-block case 1129 * 1130 * Mapping any unmapped block requires adding a (single-block) extent 1131 * and inserting into proper point in tree. 1132 * 1133 * Modifying (unmapping or remapping) a block in the middle 1134 * of an extent requires splitting the extent. 1135 * - Remapping case requires new single-block extent. 1136 * 1137 * Remapping first or last block adds an extent. 1138 * 1139 * We really need extent adding to be smart about merging. 1140 */ 1141 1142 errcode_t ext2fs_extent_set_bmap(ext2_extent_handle_t handle, 1143 blk64_t logical, blk64_t physical, int flags) 1144 { 1145 errcode_t ec, retval = 0; 1146 int mapped = 1; /* logical is mapped? */ 1147 int orig_height; 1148 int extent_uninit = 0; 1149 int prev_uninit = 0; 1150 int next_uninit = 0; 1151 int new_uninit = 0; 1152 int max_len = EXT_INIT_MAX_LEN; 1153 int has_prev, has_next; 1154 blk64_t orig_lblk; 1155 struct extent_path *path; 1156 struct ext2fs_extent extent, next_extent, prev_extent; 1157 struct ext2fs_extent newextent; 1158 struct ext2_extent_info info; 1159 1160 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1161 1162 #ifdef DEBUG 1163 printf("set_bmap ino %u log %lld phys %lld flags %d\n", 1164 handle->ino, logical, physical, flags); 1165 #endif 1166 1167 if (!(handle->fs->flags & EXT2_FLAG_RW)) 1168 return EXT2_ET_RO_FILSYS; 1169 1170 if (!handle->path) 1171 return EXT2_ET_NO_CURRENT_NODE; 1172 1173 path = handle->path + handle->level; 1174 1175 if (flags & EXT2_EXTENT_SET_BMAP_UNINIT) { 1176 new_uninit = 1; 1177 max_len = EXT_UNINIT_MAX_LEN; 1178 } 1179 1180 /* if (re)mapping, set up new extent to insert */ 1181 if (physical) { 1182 newextent.e_len = 1; 1183 newextent.e_pblk = physical; 1184 newextent.e_lblk = logical; 1185 newextent.e_flags = EXT2_EXTENT_FLAGS_LEAF; 1186 if (new_uninit) 1187 newextent.e_flags |= EXT2_EXTENT_FLAGS_UNINIT; 1188 } 1189 1190 /* special case if the extent tree is completely empty */ 1191 if ((handle->max_depth == 0) && (path->entries == 0)) { 1192 retval = ext2fs_extent_insert(handle, 0, &newextent); 1193 return retval; 1194 } 1195 1196 /* save our original location in the extent tree */ 1197 if ((retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, 1198 &extent))) { 1199 if (retval != EXT2_ET_NO_CURRENT_NODE) 1200 return retval; 1201 memset(&extent, 0, sizeof(extent)); 1202 } 1203 if ((retval = ext2fs_extent_get_info(handle, &info))) 1204 return retval; 1205 orig_height = info.max_depth - info.curr_level; 1206 orig_lblk = extent.e_lblk; 1207 1208 /* go to the logical spot we want to (re/un)map */ 1209 retval = ext2fs_extent_goto(handle, logical); 1210 if (retval) { 1211 if (retval == EXT2_ET_EXTENT_NOT_FOUND) { 1212 retval = 0; 1213 mapped = 0; 1214 if (!physical) { 1215 #ifdef DEBUG 1216 printf("block %llu already unmapped\n", 1217 logical); 1218 #endif 1219 goto done; 1220 } 1221 } else 1222 goto done; 1223 } 1224 1225 /* 1226 * This may be the extent *before* the requested logical, 1227 * if it's currently unmapped. 1228 * 1229 * Get the previous and next leaf extents, if they are present. 1230 */ 1231 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 1232 if (retval) 1233 goto done; 1234 if (extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 1235 extent_uninit = 1; 1236 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_LEAF, &next_extent); 1237 if (retval) { 1238 has_next = 0; 1239 if (retval != EXT2_ET_EXTENT_NO_NEXT) 1240 goto done; 1241 } else { 1242 dbg_print_extent("set_bmap: next_extent", 1243 &next_extent); 1244 has_next = 1; 1245 if (next_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 1246 next_uninit = 1; 1247 } 1248 retval = ext2fs_extent_goto(handle, logical); 1249 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND) 1250 goto done; 1251 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_LEAF, &prev_extent); 1252 if (retval) { 1253 has_prev = 0; 1254 if (retval != EXT2_ET_EXTENT_NO_PREV) 1255 goto done; 1256 } else { 1257 has_prev = 1; 1258 dbg_print_extent("set_bmap: prev_extent", 1259 &prev_extent); 1260 if (prev_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 1261 prev_uninit = 1; 1262 } 1263 retval = ext2fs_extent_goto(handle, logical); 1264 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND) 1265 goto done; 1266 1267 /* check if already pointing to the requested physical */ 1268 if (mapped && (new_uninit == extent_uninit) && 1269 (extent.e_pblk + (logical - extent.e_lblk) == physical)) { 1270 #ifdef DEBUG 1271 printf("physical block (at %llu) unchanged\n", logical); 1272 #endif 1273 goto done; 1274 } 1275 1276 if (!mapped) { 1277 #ifdef DEBUG 1278 printf("mapping unmapped logical block %llu\n", logical); 1279 #endif 1280 if ((logical == extent.e_lblk + extent.e_len) && 1281 (physical == extent.e_pblk + extent.e_len) && 1282 (new_uninit == extent_uninit) && 1283 ((int) extent.e_len < max_len-1)) { 1284 extent.e_len++; 1285 retval = ext2fs_extent_replace(handle, 0, &extent); 1286 } else if ((logical == extent.e_lblk - 1) && 1287 (physical == extent.e_pblk - 1) && 1288 (new_uninit == extent_uninit) && 1289 ((int) extent.e_len < max_len - 1)) { 1290 extent.e_len++; 1291 extent.e_lblk--; 1292 extent.e_pblk--; 1293 retval = ext2fs_extent_replace(handle, 0, &extent); 1294 } else if (has_next && 1295 (logical == next_extent.e_lblk - 1) && 1296 (physical == next_extent.e_pblk - 1) && 1297 (new_uninit == next_uninit) && 1298 ((int) next_extent.e_len < max_len - 1)) { 1299 retval = ext2fs_extent_get(handle, 1300 EXT2_EXTENT_NEXT_LEAF, 1301 &next_extent); 1302 if (retval) 1303 goto done; 1304 next_extent.e_len++; 1305 next_extent.e_lblk--; 1306 next_extent.e_pblk--; 1307 retval = ext2fs_extent_replace(handle, 0, &next_extent); 1308 } else if (logical < extent.e_lblk) 1309 retval = ext2fs_extent_insert(handle, 0, &newextent); 1310 else 1311 retval = ext2fs_extent_insert(handle, 1312 EXT2_EXTENT_INSERT_AFTER, &newextent); 1313 if (retval) 1314 goto done; 1315 retval = ext2fs_extent_fix_parents(handle); 1316 if (retval) 1317 goto done; 1318 } else if ((logical == extent.e_lblk) && (extent.e_len == 1)) { 1319 #ifdef DEBUG 1320 printf("(re/un)mapping only block in extent\n"); 1321 #endif 1322 if (physical) { 1323 retval = ext2fs_extent_replace(handle, 0, &newextent); 1324 } else { 1325 retval = ext2fs_extent_delete(handle, 0); 1326 if (retval) 1327 goto done; 1328 ec = ext2fs_extent_fix_parents(handle); 1329 if (ec != EXT2_ET_NO_CURRENT_NODE) 1330 retval = ec; 1331 } 1332 1333 if (retval) 1334 goto done; 1335 } else if (logical == extent.e_lblk + extent.e_len - 1) { 1336 #ifdef DEBUG 1337 printf("(re/un)mapping last block in extent\n"); 1338 #endif 1339 if (physical) { 1340 if (has_next && 1341 (logical == (next_extent.e_lblk - 1)) && 1342 (physical == (next_extent.e_pblk - 1)) && 1343 (new_uninit == next_uninit) && 1344 ((int) next_extent.e_len < max_len - 1)) { 1345 retval = ext2fs_extent_get(handle, 1346 EXT2_EXTENT_NEXT_LEAF, &next_extent); 1347 if (retval) 1348 goto done; 1349 next_extent.e_len++; 1350 next_extent.e_lblk--; 1351 next_extent.e_pblk--; 1352 retval = ext2fs_extent_replace(handle, 0, 1353 &next_extent); 1354 if (retval) 1355 goto done; 1356 } else 1357 retval = ext2fs_extent_insert(handle, 1358 EXT2_EXTENT_INSERT_AFTER, &newextent); 1359 if (retval) 1360 goto done; 1361 /* Now pointing at inserted extent; move back to prev */ 1362 retval = ext2fs_extent_get(handle, 1363 EXT2_EXTENT_PREV_LEAF, 1364 &extent); 1365 if (retval) 1366 goto done; 1367 } 1368 extent.e_len--; 1369 retval = ext2fs_extent_replace(handle, 0, &extent); 1370 if (retval) 1371 goto done; 1372 } else if (logical == extent.e_lblk) { 1373 #ifdef DEBUG 1374 printf("(re/un)mapping first block in extent\n"); 1375 #endif 1376 if (physical) { 1377 if (has_prev && 1378 (logical == (prev_extent.e_lblk + 1379 prev_extent.e_len)) && 1380 (physical == (prev_extent.e_pblk + 1381 prev_extent.e_len)) && 1382 (new_uninit == prev_uninit) && 1383 ((int) prev_extent.e_len < max_len-1)) { 1384 retval = ext2fs_extent_get(handle, 1385 EXT2_EXTENT_PREV_LEAF, &prev_extent); 1386 if (retval) 1387 goto done; 1388 prev_extent.e_len++; 1389 retval = ext2fs_extent_replace(handle, 0, 1390 &prev_extent); 1391 } else 1392 retval = ext2fs_extent_insert(handle, 1393 0, &newextent); 1394 if (retval) 1395 goto done; 1396 retval = ext2fs_extent_get(handle, 1397 EXT2_EXTENT_NEXT_LEAF, 1398 &extent); 1399 if (retval) 1400 goto done; 1401 } 1402 extent.e_pblk++; 1403 extent.e_lblk++; 1404 extent.e_len--; 1405 retval = ext2fs_extent_replace(handle, 0, &extent); 1406 if (retval) 1407 goto done; 1408 } else { 1409 __u32 orig_length; 1410 1411 #ifdef DEBUG 1412 printf("(re/un)mapping in middle of extent\n"); 1413 #endif 1414 /* need to split this extent; later */ 1415 1416 orig_length = extent.e_len; 1417 1418 /* shorten pre-split extent */ 1419 extent.e_len = (logical - extent.e_lblk); 1420 retval = ext2fs_extent_replace(handle, 0, &extent); 1421 if (retval) 1422 goto done; 1423 /* insert our new extent, if any */ 1424 if (physical) { 1425 /* insert new extent after current */ 1426 retval = ext2fs_extent_insert(handle, 1427 EXT2_EXTENT_INSERT_AFTER, &newextent); 1428 if (retval) 1429 goto done; 1430 } 1431 /* add post-split extent */ 1432 extent.e_pblk += extent.e_len + 1; 1433 extent.e_lblk += extent.e_len + 1; 1434 extent.e_len = orig_length - extent.e_len - 1; 1435 retval = ext2fs_extent_insert(handle, 1436 EXT2_EXTENT_INSERT_AFTER, &extent); 1437 if (retval) 1438 goto done; 1439 } 1440 1441 done: 1442 /* get handle back to its position */ 1443 if (orig_height > handle->max_depth) 1444 orig_height = handle->max_depth; /* In case we shortened the tree */ 1445 extent_goto(handle, orig_height, orig_lblk); 1446 return retval; 1447 } 1448 1449 errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags) 1450 { 1451 struct extent_path *path; 1452 char *cp; 1453 struct ext3_extent_header *eh; 1454 errcode_t retval = 0; 1455 1456 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1457 1458 if (!(handle->fs->flags & EXT2_FLAG_RW)) 1459 return EXT2_ET_RO_FILSYS; 1460 1461 if (!handle->path) 1462 return EXT2_ET_NO_CURRENT_NODE; 1463 1464 #ifdef DEBUG 1465 { 1466 struct ext2fs_extent extent; 1467 1468 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, 1469 &extent); 1470 if (retval == 0) { 1471 printf("extent delete %u ", handle->ino); 1472 dbg_print_extent(0, &extent); 1473 } 1474 } 1475 #endif 1476 1477 path = handle->path + handle->level; 1478 if (!path->curr) 1479 return EXT2_ET_NO_CURRENT_NODE; 1480 1481 cp = path->curr; 1482 1483 if (path->left) { 1484 memmove(cp, cp + sizeof(struct ext3_extent_idx), 1485 path->left * sizeof(struct ext3_extent_idx)); 1486 path->left--; 1487 } else { 1488 struct ext3_extent_idx *ix = path->curr; 1489 ix--; 1490 path->curr = ix; 1491 } 1492 if (--path->entries == 0) 1493 path->curr = 0; 1494 1495 /* if non-root node has no entries left, remove it & parent ptr to it */ 1496 if (path->entries == 0 && handle->level) { 1497 if (!(flags & EXT2_EXTENT_DELETE_KEEP_EMPTY)) { 1498 struct ext2fs_extent extent; 1499 1500 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, 1501 &extent); 1502 if (retval) 1503 return retval; 1504 1505 retval = ext2fs_extent_delete(handle, flags); 1506 handle->inode->i_blocks -= handle->fs->blocksize / 512; 1507 retval = ext2fs_write_inode(handle->fs, handle->ino, 1508 handle->inode); 1509 ext2fs_block_alloc_stats(handle->fs, extent.e_pblk, -1); 1510 } 1511 } else { 1512 eh = (struct ext3_extent_header *) path->buf; 1513 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 1514 if ((path->entries == 0) && (handle->level == 0)) 1515 eh->eh_depth = handle->max_depth = 0; 1516 retval = update_path(handle); 1517 } 1518 return retval; 1519 } 1520 1521 errcode_t ext2fs_extent_get_info(ext2_extent_handle_t handle, 1522 struct ext2_extent_info *info) 1523 { 1524 struct extent_path *path; 1525 1526 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1527 1528 memset(info, 0, sizeof(struct ext2_extent_info)); 1529 1530 path = handle->path + handle->level; 1531 if (path) { 1532 if (path->curr) 1533 info->curr_entry = ((char *) path->curr - path->buf) / 1534 sizeof(struct ext3_extent_idx); 1535 else 1536 info->curr_entry = 0; 1537 info->num_entries = path->entries; 1538 info->max_entries = path->max_entries; 1539 info->bytes_avail = (path->max_entries - path->entries) * 1540 sizeof(struct ext3_extent); 1541 } 1542 1543 info->curr_level = handle->level; 1544 info->max_depth = handle->max_depth; 1545 info->max_lblk = ((__u64) 1 << 32) - 1; 1546 info->max_pblk = ((__u64) 1 << 48) - 1; 1547 info->max_len = (1UL << 15); 1548 info->max_uninit_len = (1UL << 15) - 1; 1549 1550 return 0; 1551 } 1552 1553 #ifdef DEBUG 1554 1555 #include "ss/ss.h" 1556 1557 #include "debugfs.h" 1558 1559 /* 1560 * Hook in new commands into debugfs 1561 */ 1562 const char *debug_prog_name = "tst_extents"; 1563 extern ss_request_table extent_cmds; 1564 ss_request_table *extra_cmds = &extent_cmds; 1565 1566 ext2_ino_t current_ino = 0; 1567 ext2_extent_handle_t current_handle; 1568 1569 int common_extent_args_process(int argc, char *argv[], int min_argc, 1570 int max_argc, const char *cmd, 1571 const char *usage, int flags) 1572 { 1573 if (common_args_process(argc, argv, min_argc, max_argc, cmd, 1574 usage, flags)) 1575 return 1; 1576 1577 if (!current_handle) { 1578 com_err(cmd, 0, "Extent handle not open"); 1579 return 1; 1580 } 1581 return 0; 1582 } 1583 1584 void do_inode(int argc, char *argv[]) 1585 { 1586 ext2_ino_t inode; 1587 int i; 1588 struct ext3_extent_header *eh; 1589 errcode_t retval; 1590 1591 if (check_fs_open(argv[0])) 1592 return; 1593 1594 if (argc == 1) { 1595 if (current_ino) 1596 printf("Current inode is %d\n", current_ino); 1597 else 1598 printf("No current inode\n"); 1599 return; 1600 } 1601 1602 if (common_inode_args_process(argc, argv, &inode, 0)) { 1603 return; 1604 } 1605 1606 current_ino = 0; 1607 1608 retval = ext2fs_extent_open(current_fs, inode, ¤t_handle); 1609 if (retval) { 1610 com_err(argv[1], retval, "while opening extent handle"); 1611 return; 1612 } 1613 1614 current_ino = inode; 1615 1616 printf("Loaded inode %d\n", current_ino); 1617 1618 return; 1619 } 1620 1621 void generic_goto_node(char *cmd_name, int op) 1622 { 1623 struct ext2fs_extent extent; 1624 errcode_t retval; 1625 1626 if (check_fs_open(cmd_name)) 1627 return; 1628 1629 if (!current_handle) { 1630 com_err(cmd_name, 0, "Extent handle not open"); 1631 return; 1632 } 1633 1634 retval = ext2fs_extent_get(current_handle, op, &extent); 1635 if (retval) { 1636 com_err(cmd_name, retval, 0); 1637 return; 1638 } 1639 dbg_print_extent(0, &extent); 1640 } 1641 1642 void do_current_node(int argc, char *argv[]) 1643 { 1644 generic_goto_node(argv[0], EXT2_EXTENT_CURRENT); 1645 } 1646 1647 void do_root_node(int argc, char *argv[]) 1648 { 1649 generic_goto_node(argv[0], EXT2_EXTENT_ROOT); 1650 } 1651 1652 void do_last_leaf(int argc, char *argv[]) 1653 { 1654 generic_goto_node(argv[0], EXT2_EXTENT_LAST_LEAF); 1655 } 1656 1657 void do_first_sib(int argc, char *argv[]) 1658 { 1659 generic_goto_node(argv[0], EXT2_EXTENT_FIRST_SIB); 1660 } 1661 1662 void do_last_sib(int argc, char *argv[]) 1663 { 1664 generic_goto_node(argv[0], EXT2_EXTENT_LAST_SIB); 1665 } 1666 1667 void do_next_sib(int argc, char *argv[]) 1668 { 1669 generic_goto_node(argv[0], EXT2_EXTENT_NEXT_SIB); 1670 } 1671 1672 void do_prev_sib(int argc, char *argv[]) 1673 { 1674 generic_goto_node(argv[0], EXT2_EXTENT_PREV_SIB); 1675 } 1676 1677 void do_next_leaf(int argc, char *argv[]) 1678 { 1679 generic_goto_node(argv[0], EXT2_EXTENT_NEXT_LEAF); 1680 } 1681 1682 void do_prev_leaf(int argc, char *argv[]) 1683 { 1684 generic_goto_node(argv[0], EXT2_EXTENT_PREV_LEAF); 1685 } 1686 1687 void do_next(int argc, char *argv[]) 1688 { 1689 generic_goto_node(argv[0], EXT2_EXTENT_NEXT); 1690 } 1691 1692 void do_prev(int argc, char *argv[]) 1693 { 1694 generic_goto_node(argv[0], EXT2_EXTENT_PREV); 1695 } 1696 1697 void do_up(int argc, char *argv[]) 1698 { 1699 generic_goto_node(argv[0], EXT2_EXTENT_UP); 1700 } 1701 1702 void do_down(int argc, char *argv[]) 1703 { 1704 generic_goto_node(argv[0], EXT2_EXTENT_DOWN); 1705 } 1706 1707 void do_delete_node(int argc, char *argv[]) 1708 { 1709 errcode_t retval; 1710 int err; 1711 1712 if (common_extent_args_process(argc, argv, 1, 1, "delete_node", 1713 "", CHECK_FS_RW | CHECK_FS_BITMAPS)) 1714 return; 1715 1716 retval = ext2fs_extent_delete(current_handle, 0); 1717 if (retval) { 1718 com_err(argv[0], retval, 0); 1719 return; 1720 } 1721 if (current_handle->path && current_handle->path[0].curr) 1722 do_current_node(argc, argv); 1723 } 1724 1725 void do_replace_node(int argc, char *argv[]) 1726 { 1727 const char *usage = "[--uninit] <lblk> <len> <pblk>"; 1728 errcode_t retval; 1729 struct ext2fs_extent extent; 1730 int err; 1731 1732 if (common_extent_args_process(argc, argv, 3, 5, "replace_node", 1733 usage, CHECK_FS_RW | CHECK_FS_BITMAPS)) 1734 return; 1735 1736 extent.e_flags = 0; 1737 1738 if (!strcmp(argv[1], "--uninit")) { 1739 argc--; 1740 argv++; 1741 extent.e_flags |= EXT2_EXTENT_FLAGS_UNINIT; 1742 } 1743 1744 if (argc != 4) { 1745 fprintf(stderr, "Usage: %s %s\n", argv[0], usage); 1746 return; 1747 } 1748 1749 extent.e_lblk = parse_ulong(argv[1], argv[0], "logical block", &err); 1750 if (err) 1751 return; 1752 1753 extent.e_len = parse_ulong(argv[2], argv[0], "logical block", &err); 1754 if (err) 1755 return; 1756 1757 extent.e_pblk = parse_ulong(argv[3], argv[0], "logical block", &err); 1758 if (err) 1759 return; 1760 1761 retval = ext2fs_extent_replace(current_handle, 0, &extent); 1762 if (retval) { 1763 com_err(argv[0], retval, 0); 1764 return; 1765 } 1766 do_current_node(argc, argv); 1767 } 1768 1769 void do_split_node(int argc, char *argv[]) 1770 { 1771 errcode_t retval; 1772 struct ext2fs_extent extent; 1773 int err; 1774 1775 if (common_extent_args_process(argc, argv, 1, 1, "split_node", 1776 "", CHECK_FS_RW | CHECK_FS_BITMAPS)) 1777 return; 1778 1779 retval = extent_node_split(current_handle); 1780 if (retval) { 1781 com_err(argv[0], retval, 0); 1782 return; 1783 } 1784 do_current_node(argc, argv); 1785 } 1786 1787 void do_insert_node(int argc, char *argv[]) 1788 { 1789 const char *usage = "[--after] [--uninit] <lblk> <len> <pblk>"; 1790 errcode_t retval; 1791 struct ext2fs_extent extent; 1792 char *cmd; 1793 int err; 1794 int flags = 0; 1795 1796 if (common_extent_args_process(argc, argv, 3, 6, "insert_node", 1797 usage, CHECK_FS_RW | CHECK_FS_BITMAPS)) 1798 return; 1799 1800 cmd = argv[0]; 1801 1802 extent.e_flags = 0; 1803 1804 while (argc > 2) { 1805 if (!strcmp(argv[1], "--after")) { 1806 argc--; 1807 argv++; 1808 flags |= EXT2_EXTENT_INSERT_AFTER; 1809 continue; 1810 } 1811 if (!strcmp(argv[1], "--uninit")) { 1812 argc--; 1813 argv++; 1814 extent.e_flags |= EXT2_EXTENT_FLAGS_UNINIT; 1815 continue; 1816 } 1817 break; 1818 } 1819 1820 if (argc != 4) { 1821 fprintf(stderr, "usage: %s %s\n", cmd, usage); 1822 return; 1823 } 1824 1825 extent.e_lblk = parse_ulong(argv[1], cmd, 1826 "logical block", &err); 1827 if (err) 1828 return; 1829 1830 extent.e_len = parse_ulong(argv[2], cmd, 1831 "length", &err); 1832 if (err) 1833 return; 1834 1835 extent.e_pblk = parse_ulong(argv[3], cmd, 1836 "pysical block", &err); 1837 if (err) 1838 return; 1839 1840 retval = ext2fs_extent_insert(current_handle, flags, &extent); 1841 if (retval) { 1842 com_err(cmd, retval, 0); 1843 return; 1844 } 1845 do_current_node(argc, argv); 1846 } 1847 1848 void do_set_bmap(int argc, char **argv) 1849 { 1850 const char *usage = "[--uninit] <lblk> <pblk>"; 1851 errcode_t retval; 1852 blk_t logical; 1853 blk_t physical; 1854 char *cmd = argv[0]; 1855 int flags = 0; 1856 int err; 1857 1858 if (common_extent_args_process(argc, argv, 3, 5, "set_bmap", 1859 usage, CHECK_FS_RW | CHECK_FS_BITMAPS)) 1860 return; 1861 1862 if (argc > 2 && !strcmp(argv[1], "--uninit")) { 1863 argc--; 1864 argv++; 1865 flags |= EXT2_EXTENT_SET_BMAP_UNINIT; 1866 } 1867 1868 if (argc != 3) { 1869 fprintf(stderr, "Usage: %s %s\n", cmd, usage); 1870 return; 1871 } 1872 1873 logical = parse_ulong(argv[1], cmd, 1874 "logical block", &err); 1875 if (err) 1876 return; 1877 1878 physical = parse_ulong(argv[2], cmd, 1879 "physical block", &err); 1880 if (err) 1881 return; 1882 1883 retval = ext2fs_extent_set_bmap(current_handle, logical, 1884 (blk64_t) physical, flags); 1885 if (retval) { 1886 com_err(cmd, retval, 0); 1887 return; 1888 } 1889 if (current_handle->path && current_handle->path[0].curr) 1890 do_current_node(argc, argv); 1891 } 1892 1893 void do_print_all(int argc, char **argv) 1894 { 1895 const char *usage = "[--leaf-only|--reverse|--reverse-leaf]"; 1896 struct ext2fs_extent extent; 1897 errcode_t retval; 1898 errcode_t end_err = EXT2_ET_EXTENT_NO_NEXT; 1899 int op = EXT2_EXTENT_NEXT; 1900 int first_op = EXT2_EXTENT_ROOT; 1901 1902 1903 if (common_extent_args_process(argc, argv, 1, 2, "print_all", 1904 usage, 0)) 1905 return; 1906 1907 if (argc == 2) { 1908 if (!strcmp(argv[1], "--leaf-only")) 1909 op = EXT2_EXTENT_NEXT_LEAF; 1910 else if (!strcmp(argv[1], "--reverse")) { 1911 op = EXT2_EXTENT_PREV; 1912 first_op = EXT2_EXTENT_LAST_LEAF; 1913 end_err = EXT2_ET_EXTENT_NO_PREV; 1914 } else if (!strcmp(argv[1], "--reverse-leaf")) { 1915 op = EXT2_EXTENT_PREV_LEAF; 1916 first_op = EXT2_EXTENT_LAST_LEAF; 1917 end_err = EXT2_ET_EXTENT_NO_PREV; 1918 } else { 1919 fprintf(stderr, "Usage: %s %s\n", argv[0], usage); 1920 return; 1921 } 1922 } 1923 1924 retval = ext2fs_extent_get(current_handle, first_op, &extent); 1925 if (retval) { 1926 com_err(argv[0], retval, 0); 1927 return; 1928 } 1929 dbg_print_extent(0, &extent); 1930 1931 while (1) { 1932 retval = ext2fs_extent_get(current_handle, op, &extent); 1933 if (retval == end_err) 1934 break; 1935 1936 if (retval) { 1937 com_err(argv[0], retval, 0); 1938 return; 1939 } 1940 dbg_print_extent(0, &extent); 1941 } 1942 } 1943 1944 void do_info(int argc, char **argv) 1945 { 1946 struct ext2fs_extent extent; 1947 struct ext2_extent_info info; 1948 errcode_t retval; 1949 1950 if (common_extent_args_process(argc, argv, 1, 1, "info", "", 0)) 1951 return; 1952 1953 retval = ext2fs_extent_get_info(current_handle, &info); 1954 if (retval) { 1955 com_err(argv[0], retval, 0); 1956 return; 1957 } 1958 1959 retval = ext2fs_extent_get(current_handle, 1960 EXT2_EXTENT_CURRENT, &extent); 1961 if (retval) { 1962 com_err(argv[0], retval, 0); 1963 return; 1964 } 1965 1966 dbg_print_extent(0, &extent); 1967 1968 printf("Current handle location: %d/%d (max: %d, bytes %d), level %d/%d\n", 1969 info.curr_entry, info.num_entries, info.max_entries, 1970 info.bytes_avail, info.curr_level, info.max_depth); 1971 printf("\tmax lblk: %llu, max pblk: %llu\n", info.max_lblk, 1972 info.max_pblk); 1973 printf("\tmax_len: %u, max_uninit_len: %u\n", info.max_len, 1974 info.max_uninit_len); 1975 } 1976 1977 void do_goto_block(int argc, char **argv) 1978 { 1979 struct ext2fs_extent extent; 1980 errcode_t retval; 1981 int op = EXT2_EXTENT_NEXT_LEAF; 1982 blk_t blk; 1983 int level = 0; 1984 1985 if (common_extent_args_process(argc, argv, 2, 3, "goto_block", 1986 "block [level]", 0)) 1987 return; 1988 1989 if (strtoblk(argv[0], argv[1], &blk)) 1990 return; 1991 1992 if (argc == 3) 1993 if (strtoblk(argv[0], argv[2], &level)) 1994 return; 1995 1996 retval = extent_goto(current_handle, level, (blk64_t) blk); 1997 1998 if (retval) { 1999 com_err(argv[0], retval, 2000 "while trying to go to block %u, level %d", 2001 blk, level); 2002 return; 2003 } 2004 2005 generic_goto_node(argv[0], EXT2_EXTENT_CURRENT); 2006 } 2007 #endif 2008 2009
