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