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