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