extent.c revision 252b7363690e71bfd01517d6b348a5996d98ac7f
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#include "ss/ss.h" 31 32/* 33 * Definitions to be dropped in lib/ext2fs/ext2fs.h 34 */ 35 36/* 37 * Private definitions 38 */ 39 40struct extent_path { 41 char *buf; 42 int entries; 43 int max_entries; 44 int left; 45 int visit_num; 46 int flags; 47 blk64_t end_blk; 48 void *curr; 49}; 50 51 52struct ext2_extent_handle { 53 errcode_t magic; 54 ext2_filsys fs; 55 ext2_ino_t ino; 56 struct ext2_inode *inode; 57 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 eh->eh_magic, eh->eh_entries, eh->eh_max, eh->eh_depth, 78 eh->eh_generation); 79} 80 81static void dbg_show_index(struct ext3_extent_idx *ix) 82{ 83 printf("index: block=%u leaf=%u leaf_hi=%u unused=%u\n", 84 ix->ei_block, ix->ei_leaf, ix->ei_leaf_hi, ix->ei_unused); 85} 86 87static void dbg_show_extent(struct ext3_extent *ex) 88{ 89 printf("extent: block=%u-%u len=%u start=%u start_hi=%u\n", 90 ex->ee_block, ex->ee_block + ex->ee_len - 1, 91 ex->ee_len, ex->ee_start, ex->ee_start_hi); 92} 93 94static void dbg_print_extent(char *desc, struct ext2fs_extent *extent) 95{ 96 if (desc) 97 printf("%s: ", desc); 98 printf("extent: lblk %llu--%llu, len %lu, pblk %llu, flags: ", 99 extent->e_lblk, extent->e_lblk + extent->e_len - 1, 100 extent->e_len, extent->e_pblk); 101 if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF) 102 fputs("LEAF ", stdout); 103 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) 104 fputs("UNINIT ", stdout); 105 if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT) 106 fputs("2ND_VISIT ", stdout); 107 if (!extent->e_flags) 108 fputs("(none)", stdout); 109 fputc('\n', stdout); 110 111} 112 113#define dbg_printf(fmt, args...) printf(fmt, ## args) 114#else 115#define dbg_show_header(eh) do { } while (0) 116#define dbg_show_index(ix) do { } while (0) 117#define dbg_show_extent(ex) do { } while (0) 118#define dbg_print_extent(desc, ex) do { } while (0) 119#define dbg_printf(fmt, args...) do { } while (0) 120#endif 121 122/* 123 * Verify the extent header as being sane 124 */ 125errcode_t ext2fs_extent_header_verify(void *ptr, int size) 126{ 127 int eh_max, entry_size; 128 struct ext3_extent_header *eh = ptr; 129 130 dbg_show_header(eh); 131 if (ext2fs_le16_to_cpu(eh->eh_magic) != EXT3_EXT_MAGIC) 132 return EXT2_ET_EXTENT_HEADER_BAD; 133 if (ext2fs_le16_to_cpu(eh->eh_entries) > ext2fs_le16_to_cpu(eh->eh_max)) 134 return EXT2_ET_EXTENT_HEADER_BAD; 135 if (eh->eh_depth == 0) 136 entry_size = sizeof(struct ext3_extent); 137 else 138 entry_size = sizeof(struct ext3_extent_idx); 139 140 eh_max = (size - sizeof(*eh)) / entry_size; 141 /* Allow two extent-sized items at the end of the block, for 142 * ext4_extent_tail with checksum in the future. */ 143 if ((ext2fs_le16_to_cpu(eh->eh_max) > eh_max) || 144 (ext2fs_le16_to_cpu(eh->eh_max) < (eh_max - 2))) 145 return EXT2_ET_EXTENT_HEADER_BAD; 146 147 return 0; 148} 149 150 151/* 152 * Begin functions to handle an inode's extent information 153 */ 154 155extern void ext2fs_extent_free(ext2_extent_handle_t handle) 156{ 157 int i; 158 159 if (!handle) 160 return; 161 162 if (handle->inode) 163 ext2fs_free_mem(&handle->inode); 164 if (handle->path) { 165 for (i=1; i < handle->max_depth; i++) { 166 if (handle->path[i].buf) 167 ext2fs_free_mem(&handle->path[i].buf); 168 } 169 ext2fs_free_mem(&handle->path); 170 } 171 ext2fs_free_mem(&handle); 172} 173 174extern errcode_t ext2fs_extent_open(ext2_filsys fs, ext2_ino_t ino, 175 ext2_extent_handle_t *ret_handle) 176{ 177 struct ext2_extent_handle *handle; 178 errcode_t retval; 179 int isize = EXT2_INODE_SIZE(fs->super); 180 struct ext3_extent_header *eh; 181 struct ext3_extent_idx *ix; 182 183 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 184 185 if ((ino == 0) || (ino > fs->super->s_inodes_count)) 186 return EXT2_ET_BAD_INODE_NUM; 187 188 retval = ext2fs_get_mem(sizeof(struct ext2_extent_handle), &handle); 189 if (retval) 190 return retval; 191 memset(handle, 0, sizeof(struct ext2_extent_handle)); 192 193 retval = ext2fs_get_mem(isize, &handle->inode); 194 if (retval) 195 goto errout; 196 197 handle->ino = ino; 198 handle->fs = fs; 199 200 retval = ext2fs_read_inode_full(fs, ino, handle->inode, isize); 201 if (retval) 202 goto errout; 203 204 if (!(handle->inode->i_flags & EXT4_EXTENTS_FL)) 205 return EXT2_ET_INODE_NOT_EXTENT; 206 207 eh = (struct ext3_extent_header *) &handle->inode->i_block; 208 209 retval = ext2fs_extent_header_verify(eh, sizeof(handle->inode->i_block)); 210 if (retval) 211 return (retval); 212 213 handle->max_depth = ext2fs_le16_to_cpu(eh->eh_depth); 214 handle->type = ext2fs_le16_to_cpu(eh->eh_magic); 215 216 retval = ext2fs_get_mem(((handle->max_depth+1) * 217 sizeof(struct extent_path)), 218 &handle->path); 219 memset(handle->path, 0, 220 (handle->max_depth+1) * sizeof(struct extent_path)); 221 handle->path[0].buf = (char *) handle->inode->i_block; 222 223 handle->path[0].left = handle->path[0].entries = 224 ext2fs_le16_to_cpu(eh->eh_entries); 225 handle->path[0].max_entries = ext2fs_le16_to_cpu(eh->eh_max); 226 handle->path[0].curr = 0; 227 handle->path[0].end_blk = 228 ((((__u64) handle->inode->i_size_high << 32) + 229 handle->inode->i_size + (fs->blocksize - 1)) 230 >> EXT2_BLOCK_SIZE_BITS(fs->super)); 231 handle->path[0].visit_num = 1; 232 handle->level = 0; 233 handle->magic = EXT2_ET_MAGIC_EXTENT_HANDLE; 234 235 *ret_handle = handle; 236 return 0; 237 238errout: 239 ext2fs_extent_free(handle); 240 return retval; 241} 242 243/* 244 * This function is responsible for (optionally) moving through the 245 * extent tree and then returning the current extent 246 */ 247errcode_t ext2fs_extent_get(ext2_extent_handle_t handle, 248 int flags, struct ext2fs_extent *extent) 249{ 250 struct extent_path *path, *newpath; 251 struct ext3_extent_header *eh; 252 struct ext3_extent_idx *ix = 0; 253 struct ext3_extent *ex; 254 errcode_t retval; 255 blk_t blk; 256 blk64_t end_blk; 257 int orig_op, op; 258 259 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 260 261 if (!handle->path) 262 return EXT2_ET_NO_CURRENT_NODE; 263 264 orig_op = op = flags & EXT2_EXTENT_MOVE_MASK; 265 266retry: 267 path = handle->path + handle->level; 268 if ((orig_op == EXT2_EXTENT_NEXT) || 269 (orig_op == EXT2_EXTENT_NEXT_LEAF)) { 270 if (handle->level < handle->max_depth) { 271 /* interior node */ 272 if (path->visit_num == 0) { 273 path->visit_num++; 274 op = EXT2_EXTENT_DOWN; 275 } else if (path->left > 0) 276 op = EXT2_EXTENT_NEXT_SIB; 277 else if (handle->level > 0) 278 op = EXT2_EXTENT_UP; 279 else 280 return EXT2_ET_EXTENT_NO_NEXT; 281 } else { 282 /* leaf node */ 283 if (path->left > 0) 284 op = EXT2_EXTENT_NEXT_SIB; 285 else if (handle->level > 0) 286 op = EXT2_EXTENT_UP; 287 else 288 return EXT2_ET_EXTENT_NO_NEXT; 289 } 290 if (op != EXT2_EXTENT_NEXT_SIB) { 291 dbg_printf("<<<< OP = %s\n", 292 (op == EXT2_EXTENT_DOWN) ? "down" : 293 ((op == EXT2_EXTENT_UP) ? "up" : "unknown")); 294 } 295 } 296 297 if ((orig_op == EXT2_EXTENT_PREV) || 298 (orig_op == EXT2_EXTENT_PREV_LEAF)) { 299 if (handle->level < handle->max_depth) { 300 /* interior node */ 301 if (path->visit_num > 0 ) { 302 /* path->visit_num = 0; */ 303 op = EXT2_EXTENT_DOWN_AND_LAST; 304 } else if (path->left < path->entries-1) 305 op = EXT2_EXTENT_PREV_SIB; 306 else if (handle->level > 0) 307 op = EXT2_EXTENT_UP; 308 else 309 return EXT2_ET_EXTENT_NO_PREV; 310 } else { 311 /* leaf node */ 312 if (path->left < path->entries-1) 313 op = EXT2_EXTENT_PREV_SIB; 314 else if (handle->level > 0) 315 op = EXT2_EXTENT_UP; 316 else 317 return EXT2_ET_EXTENT_NO_PREV; 318 } 319 if (op != EXT2_EXTENT_PREV_SIB) { 320 dbg_printf("<<<< OP = %s\n", 321 (op == EXT2_EXTENT_DOWN_AND_LAST) ? "down/last" : 322 ((op == EXT2_EXTENT_UP) ? "up" : "unknown")); 323 } 324 } 325 326 if (orig_op == EXT2_EXTENT_LAST_LEAF) { 327 if ((handle->level < handle->max_depth) && 328 (path->left == 0)) 329 op = EXT2_EXTENT_DOWN; 330 else 331 op = EXT2_EXTENT_LAST_SIB; 332 dbg_printf("<<<< OP = %s\n", 333 (op == EXT2_EXTENT_DOWN) ? "down" : "last_sib"); 334 } 335 336 switch (op) { 337 case EXT2_EXTENT_CURRENT: 338 ix = path->curr; 339 break; 340 case EXT2_EXTENT_ROOT: 341 handle->level = 0; 342 path = handle->path + handle->level; 343 case EXT2_EXTENT_FIRST_SIB: 344 path->left = path->entries; 345 path->curr = 0; 346 case EXT2_EXTENT_NEXT_SIB: 347 if (path->left <= 0) 348 return EXT2_ET_EXTENT_NO_NEXT; 349 if (path->curr) { 350 ix = path->curr; 351 ix++; 352 } else { 353 eh = (struct ext3_extent_header *) path->buf; 354 ix = EXT_FIRST_INDEX(eh); 355 } 356 path->left--; 357 path->curr = ix; 358 path->visit_num = 0; 359 break; 360 case EXT2_EXTENT_PREV_SIB: 361 if (!path->curr || 362 path->left+1 >= path->entries) 363 return EXT2_ET_EXTENT_NO_PREV; 364 ix = path->curr; 365 ix--; 366 path->curr = ix; 367 path->left++; 368 if (handle->level < handle->max_depth) 369 path->visit_num = 1; 370 break; 371 case EXT2_EXTENT_LAST_SIB: 372 eh = (struct ext3_extent_header *) path->buf; 373 path->curr = EXT_LAST_EXTENT(eh); 374 ix = path->curr; 375 path->left = 0; 376 path->visit_num = 0; 377 break; 378 case EXT2_EXTENT_UP: 379 if (handle->level <= 0) 380 return EXT2_ET_EXTENT_NO_UP; 381 handle->level--; 382 path--; 383 ix = path->curr; 384 if ((orig_op == EXT2_EXTENT_PREV) || 385 (orig_op == EXT2_EXTENT_PREV_LEAF)) 386 path->visit_num = 0; 387 break; 388 case EXT2_EXTENT_DOWN: 389 case EXT2_EXTENT_DOWN_AND_LAST: 390 if (!path->curr ||(handle->level >= handle->max_depth)) 391 return EXT2_ET_EXTENT_NO_DOWN; 392 393 ix = path->curr; 394 newpath = path + 1; 395 if (!newpath->buf) { 396 retval = ext2fs_get_mem(handle->fs->blocksize, 397 &newpath->buf); 398 if (retval) 399 return retval; 400 } 401 blk = ext2fs_le32_to_cpu(ix->ei_leaf) + 402 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32); 403 if ((handle->fs->flags & EXT2_FLAG_IMAGE_FILE) && 404 (handle->fs->io != handle->fs->image_io)) 405 memset(newpath->buf, 0, handle->fs->blocksize); 406 else { 407 retval = io_channel_read_blk(handle->fs->io, 408 blk, 1, newpath->buf); 409 if (retval) 410 return retval; 411 } 412 handle->level++; 413 414 eh = (struct ext3_extent_header *) newpath->buf; 415 416 retval = ext2fs_extent_header_verify(eh, handle->fs->blocksize); 417 if (retval) 418 return retval; 419 420 newpath->left = newpath->entries = 421 ext2fs_le16_to_cpu(eh->eh_entries); 422 newpath->max_entries = ext2fs_le16_to_cpu(eh->eh_max); 423 424 if (path->left > 0) { 425 ix++; 426 newpath->end_blk = ext2fs_le32_to_cpu(ix->ei_block); 427 } else 428 newpath->end_blk = path->end_blk; 429 430 path = newpath; 431 if (op == EXT2_EXTENT_DOWN) { 432 ix = EXT_FIRST_INDEX((struct ext3_extent_header *) eh); 433 path->curr = ix; 434 path->left = path->entries - 1; 435 path->visit_num = 0; 436 } else { 437 ix = EXT_LAST_INDEX((struct ext3_extent_header *) eh); 438 path->curr = ix; 439 path->left = 0; 440 if (handle->level < handle->max_depth) 441 path->visit_num = 1; 442 } 443 444 dbg_printf("Down to level %d/%d, end_blk=%llu\n", 445 handle->level, handle->max_depth, 446 path->end_blk); 447 448 break; 449 default: 450 return EXT2_ET_OP_NOT_SUPPORTED; 451 } 452 453 if (!ix) 454 return EXT2_ET_NO_CURRENT_NODE; 455 456 extent->e_flags = 0; 457 dbg_printf("(Left %d)\n", path->left); 458 459 if (handle->level == handle->max_depth) { 460 ex = (struct ext3_extent *) ix; 461 462 extent->e_pblk = ext2fs_le32_to_cpu(ex->ee_start) + 463 ((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32); 464 extent->e_lblk = ext2fs_le32_to_cpu(ex->ee_block); 465 extent->e_len = ext2fs_le16_to_cpu(ex->ee_len); 466 extent->e_flags = EXT2_EXTENT_FLAGS_LEAF; 467 if (extent->e_len > EXT_INIT_MAX_LEN) { 468 extent->e_len -= EXT_INIT_MAX_LEN; 469 extent->e_flags = EXT2_EXTENT_FLAGS_UNINIT; 470 } 471 } else { 472 extent->e_pblk = ext2fs_le32_to_cpu(ix->ei_leaf) + 473 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32); 474 extent->e_lblk = ext2fs_le32_to_cpu(ix->ei_block); 475 if (path->left > 0) { 476 ix++; 477 end_blk = ext2fs_le32_to_cpu(ix->ei_block); 478 } else 479 end_blk = path->end_blk; 480 481 extent->e_len = end_blk - extent->e_lblk; 482 } 483 if (path->visit_num) 484 extent->e_flags |= EXT2_EXTENT_FLAGS_SECOND_VISIT; 485 486 if (((orig_op == EXT2_EXTENT_NEXT_LEAF) || 487 (orig_op == EXT2_EXTENT_PREV_LEAF)) && 488 (handle->level != handle->max_depth)) 489 goto retry; 490 491 if ((orig_op == EXT2_EXTENT_LAST_LEAF) && 492 ((handle->level != handle->max_depth) || 493 (path->left != 0))) 494 goto retry; 495 496 return 0; 497} 498 499static errcode_t update_path(ext2_extent_handle_t handle) 500{ 501 struct extent_path *path; 502 blk64_t blk; 503 errcode_t retval; 504 struct ext3_extent_idx *ix; 505 506 if (handle->level == 0) { 507 retval = ext2fs_write_inode_full(handle->fs, handle->ino, 508 handle->inode, EXT2_INODE_SIZE(handle->fs->super)); 509 } else { 510 ix = handle->path[handle->level - 1].curr; 511 blk = ext2fs_le32_to_cpu(ix->ei_leaf) + 512 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32); 513 514 retval = io_channel_write_blk(handle->fs->io, 515 blk, 1, handle->path[handle->level].buf); 516 } 517 return retval; 518} 519 520errcode_t ext2fs_extent_save_path(ext2_extent_handle_t handle, 521 ext2_extent_path_t *ret_path) 522{ 523 ext2_extent_path_t save_path; 524 struct ext2fs_extent extent; 525 struct ext2_extent_info info; 526 errcode_t retval; 527 528 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 529 if (retval) 530 return retval; 531 532 retval = ext2fs_extent_get_info(handle, &info); 533 if (retval) 534 return retval; 535 536 retval = ext2fs_get_mem(sizeof(struct ext2_extent_path), &save_path); 537 if (retval) 538 return retval; 539 memset(save_path, 0, sizeof(struct ext2_extent_path)); 540 541 save_path->magic = EXT2_ET_MAGIC_EXTENT_PATH; 542 save_path->leaf_height = info.max_depth - info.curr_level - 1; 543 save_path->lblk = extent.e_lblk; 544 545 *ret_path = save_path; 546 return 0; 547} 548 549errcode_t ext2fs_extent_free_path(ext2_extent_path_t path) 550{ 551 EXT2_CHECK_MAGIC(path, EXT2_ET_MAGIC_EXTENT_PATH); 552 553 ext2fs_free_mem(&path); 554 return 0; 555} 556 557static errcode_t extent_goto(ext2_extent_handle_t handle, 558 int leaf_level, blk64_t blk) 559{ 560 struct ext2fs_extent extent, next; 561 errcode_t retval; 562 563 retval = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent); 564 if (retval) 565 return retval; 566 567 dbg_print_extent("root", &extent); 568 while (1) { 569 if (handle->level - leaf_level == handle->max_depth) { 570 if ((blk >= extent.e_lblk) && 571 (blk < extent.e_lblk + extent.e_len)) 572 return 0; 573 if (blk < extent.e_lblk) 574 return EXT2_ET_EXTENT_NOT_FOUND; 575 retval = ext2fs_extent_get(handle, 576 EXT2_EXTENT_NEXT_SIB, 577 &extent); 578 if (retval == EXT2_ET_EXTENT_NO_NEXT) 579 return EXT2_ET_EXTENT_NOT_FOUND; 580 if (retval) 581 return retval; 582 continue; 583 } 584 585 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_SIB, 586 &extent); 587 if (retval == EXT2_ET_EXTENT_NO_NEXT) 588 goto go_down; 589 if (retval) 590 return retval; 591 592 dbg_print_extent("next", &extent); 593 if (blk == extent.e_lblk) 594 goto go_down; 595 if (blk > extent.e_lblk) 596 continue; 597 598 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_SIB, 599 &extent); 600 if (retval) 601 return retval; 602 603 dbg_print_extent("prev", &extent); 604 605 go_down: 606 retval = ext2fs_extent_get(handle, EXT2_EXTENT_DOWN, 607 &extent); 608 if (retval) 609 return retval; 610 611 dbg_print_extent("down", &extent); 612 } 613} 614 615errcode_t ext2fs_extent_goto(ext2_extent_handle_t handle, 616 blk64_t blk) 617{ 618 return extent_goto(handle, 0, blk); 619} 620 621errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle, int flags, 622 struct ext2fs_extent *extent) 623{ 624 struct extent_path *path; 625 struct ext3_extent_idx *ix; 626 struct ext3_extent *ex; 627 628 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 629 630 if (!(handle->fs->flags & EXT2_FLAG_RW)) 631 return EXT2_ET_RO_FILSYS; 632 633 if (!handle->path) 634 return EXT2_ET_NO_CURRENT_NODE; 635 636 path = handle->path + handle->level; 637 if (!path->curr) 638 return EXT2_ET_NO_CURRENT_NODE; 639 640 if (handle->level == handle->max_depth) { 641 ex = path->curr; 642 643 ex->ee_block = ext2fs_cpu_to_le32(extent->e_lblk); 644 ex->ee_start = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF); 645 ex->ee_start_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32); 646 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len); 647 } else { 648 ix = path->curr; 649 650 ix->ei_leaf = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF); 651 ix->ei_leaf_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32); 652 ix->ei_block = ext2fs_cpu_to_le32(extent->e_lblk); 653 ix->ei_unused = 0; 654 } 655 update_path(handle); 656 return 0; 657} 658 659errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags, 660 struct ext2fs_extent *extent) 661{ 662 struct extent_path *path; 663 struct ext3_extent_idx *ix; 664 struct ext3_extent_header *eh; 665 errcode_t retval; 666 667 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 668 669 if (!(handle->fs->flags & EXT2_FLAG_RW)) 670 return EXT2_ET_RO_FILSYS; 671 672 if (!handle->path) 673 return EXT2_ET_NO_CURRENT_NODE; 674 675 path = handle->path + handle->level; 676 677 if (path->entries >= path->max_entries) 678 return EXT2_ET_CANT_INSERT_EXTENT; 679 680 eh = (struct ext3_extent_header *) path->buf; 681 if (path->curr) { 682 ix = path->curr; 683 if (flags & EXT2_EXTENT_INSERT_AFTER) { 684 ix++; 685 path->left--; 686 } 687 } else 688 ix = EXT_FIRST_INDEX(eh); 689 690 path->curr = ix; 691 692 if (path->left > 0) 693 memmove(ix + 1, ix, 694 (path->left+1) * sizeof(struct ext3_extent_idx)); 695 path->left++; 696 path->entries++; 697 698 eh = (struct ext3_extent_header *) path->buf; 699 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 700 701 retval = ext2fs_extent_replace(handle, 0, extent); 702 if (retval) 703 goto errout; 704 705 retval = update_path(handle); 706 if (retval) 707 goto errout; 708 709 return 0; 710 711errout: 712 ext2fs_extent_delete(handle, 0); 713 return retval; 714} 715 716errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags) 717{ 718 struct extent_path *path; 719 char *cp; 720 struct ext3_extent_header *eh; 721 errcode_t retval; 722 723 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 724 725 if (!(handle->fs->flags & EXT2_FLAG_RW)) 726 return EXT2_ET_RO_FILSYS; 727 728 if (!handle->path) 729 return EXT2_ET_NO_CURRENT_NODE; 730 731 path = handle->path + handle->level; 732 if (!path->curr) 733 return EXT2_ET_NO_CURRENT_NODE; 734 735 cp = path->curr; 736 737 if (path->left) { 738 memmove(cp, cp + sizeof(struct ext3_extent_idx), 739 path->left * sizeof(struct ext3_extent_idx)); 740 path->left--; 741 } else { 742 struct ext3_extent_idx *ix = path->curr; 743 ix--; 744 path->curr = ix; 745 } 746 path->entries--; 747 if (path->entries == 0) 748 path->curr = 0; 749 750 eh = (struct ext3_extent_header *) path->buf; 751 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 752 753 retval = update_path(handle); 754 755 return retval; 756} 757 758errcode_t ext2fs_extent_get_info(ext2_extent_handle_t handle, 759 struct ext2_extent_info *info) 760{ 761 struct extent_path *path; 762 struct ext3_extent_idx *ix; 763 struct ext3_extent *ex; 764 765 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 766 767 memset(info, 0, sizeof(struct ext2_extent_info)); 768 769 path = handle->path + handle->level; 770 if (path) { 771 if (path->curr) 772 info->curr_entry = ((char *) path->curr - path->buf) / 773 sizeof(struct ext3_extent_idx); 774 else 775 info->curr_entry = 0; 776 info->num_entries = path->entries; 777 info->max_entries = path->max_entries; 778 info->bytes_avail = (path->max_entries - path->entries) * 779 sizeof(struct ext3_extent); 780 } 781 782 info->curr_level = handle->level; 783 info->max_depth = handle->max_depth; 784 info->max_lblk = ((__u64) 1 << 32) - 1; 785 info->max_pblk = ((__u64) 1 << 48) - 1; 786 info->max_len = (1UL << 15); 787 info->max_uninit_len = (1UL << 15) - 1; 788 789 return 0; 790} 791 792#ifdef DEBUG 793 794#include "debugfs.h" 795 796/* 797 * Hook in new commands into debugfs 798 */ 799char *debug_prog_name = "tst_extents"; 800extern ss_request_table extent_cmds; 801ss_request_table *extra_cmds = &extent_cmds; 802 803ext2_ino_t current_ino = 0; 804ext2_extent_handle_t current_handle; 805 806void do_inode(int argc, char *argv[]) 807{ 808 ext2_ino_t inode; 809 int i; 810 struct ext3_extent_header *eh; 811 errcode_t retval; 812 813 if (check_fs_open(argv[0])) 814 return; 815 816 if (argc == 1) { 817 if (current_ino) 818 printf("Current inode is %d\n", current_ino); 819 else 820 printf("No current inode\n"); 821 return; 822 } 823 824 if (common_inode_args_process(argc, argv, &inode, 0)) { 825 return; 826 } 827 828 current_ino = 0; 829 830 retval = ext2fs_extent_open(current_fs, inode, ¤t_handle); 831 if (retval) { 832 com_err(argv[1], retval, "while opening extent handle"); 833 return; 834 } 835 836 current_ino = inode; 837 838 printf("Loaded inode %d\n", current_ino); 839 840 return; 841} 842 843void generic_goto_node(char *cmd_name, int op) 844{ 845 struct ext2fs_extent extent; 846 errcode_t retval; 847 848 if (check_fs_open(cmd_name)) 849 return; 850 851 if (!current_handle) { 852 com_err(cmd_name, 0, "Extent handle not open"); 853 return; 854 } 855 856 retval = ext2fs_extent_get(current_handle, op, &extent); 857 if (retval) { 858 com_err(cmd_name, retval, 0); 859 return; 860 } 861 dbg_print_extent(0, &extent); 862} 863 864void do_current_node(int argc, char *argv[]) 865{ 866 generic_goto_node(argv[0], EXT2_EXTENT_CURRENT); 867} 868 869void do_root_node(int argc, char *argv[]) 870{ 871 generic_goto_node(argv[0], EXT2_EXTENT_ROOT); 872} 873 874void do_last_leaf(int argc, char *argv[]) 875{ 876 generic_goto_node(argv[0], EXT2_EXTENT_LAST_LEAF); 877} 878 879void do_first_sib(int argc, char *argv[]) 880{ 881 generic_goto_node(argv[0], EXT2_EXTENT_FIRST_SIB); 882} 883 884void do_last_sib(int argc, char *argv[]) 885{ 886 generic_goto_node(argv[0], EXT2_EXTENT_LAST_SIB); 887} 888 889void do_next_sib(int argc, char *argv[]) 890{ 891 generic_goto_node(argv[0], EXT2_EXTENT_NEXT_SIB); 892} 893 894void do_prev_sib(int argc, char *argv[]) 895{ 896 generic_goto_node(argv[0], EXT2_EXTENT_PREV_SIB); 897} 898 899void do_next_leaf(int argc, char *argv[]) 900{ 901 generic_goto_node(argv[0], EXT2_EXTENT_NEXT_LEAF); 902} 903 904void do_prev_leaf(int argc, char *argv[]) 905{ 906 generic_goto_node(argv[0], EXT2_EXTENT_PREV_LEAF); 907} 908 909void do_next(int argc, char *argv[]) 910{ 911 generic_goto_node(argv[0], EXT2_EXTENT_NEXT); 912} 913 914void do_prev(int argc, char *argv[]) 915{ 916 generic_goto_node(argv[0], EXT2_EXTENT_PREV); 917} 918 919void do_up(int argc, char *argv[]) 920{ 921 generic_goto_node(argv[0], EXT2_EXTENT_UP); 922} 923 924void do_down(int argc, char *argv[]) 925{ 926 generic_goto_node(argv[0], EXT2_EXTENT_DOWN); 927} 928 929void do_delete_node(int argc, char *argv[]) 930{ 931 errcode_t retval; 932 int err; 933 934 if (check_fs_read_write(argv[0])) 935 return; 936 937 retval = ext2fs_extent_delete(current_handle, 0); 938 if (retval) { 939 com_err(argv[0], retval, 0); 940 return; 941 } 942 do_current_node(argc, argv); 943} 944 945void do_replace_node(int argc, char *argv[]) 946{ 947 errcode_t retval; 948 struct ext2fs_extent extent; 949 int err; 950 951 if (check_fs_read_write(argv[0])) 952 return; 953 954 if (argc != 4) { 955 fprintf(stderr, "usage: %s <lblk> <len> <pblk>\n", argv[0]); 956 return; 957 } 958 959 extent.e_lblk = parse_ulong(argv[1], argv[0], 960 "logical block", &err); 961 if (err) 962 return; 963 964 extent.e_len = parse_ulong(argv[2], argv[0], 965 "logical block", &err); 966 if (err) 967 return; 968 969 extent.e_pblk = parse_ulong(argv[3], argv[0], 970 "logical block", &err); 971 if (err) 972 return; 973 974 retval = ext2fs_extent_replace(current_handle, 0, &extent); 975 if (retval) { 976 com_err(argv[0], retval, 0); 977 return; 978 } 979 do_current_node(argc, argv); 980} 981 982void do_insert_node(int argc, char *argv[]) 983{ 984 errcode_t retval; 985 struct ext2fs_extent extent; 986 char *cmd; 987 int err; 988 int flags = 0; 989 990 if (check_fs_read_write(argv[0])) 991 return; 992 993 cmd = argv[0]; 994 995 if (argc > 2 && !strcmp(argv[1], "--after")) { 996 argc--; 997 argv++; 998 flags |= EXT2_EXTENT_INSERT_AFTER; 999 } 1000 1001 if (argc != 4) { 1002 fprintf(stderr, "usage: %s <lblk> <len> <pblk>\n", cmd); 1003 return; 1004 } 1005 1006 extent.e_lblk = parse_ulong(argv[1], cmd, 1007 "logical block", &err); 1008 if (err) 1009 return; 1010 1011 extent.e_len = parse_ulong(argv[2], cmd, 1012 "length", &err); 1013 if (err) 1014 return; 1015 1016 extent.e_pblk = parse_ulong(argv[3], cmd, 1017 "pysical block", &err); 1018 if (err) 1019 return; 1020 1021 retval = ext2fs_extent_insert(current_handle, flags, &extent); 1022 if (retval) { 1023 com_err(cmd, retval, 0); 1024 return; 1025 } 1026 do_current_node(argc, argv); 1027} 1028 1029void do_print_all(int argc, char **argv) 1030{ 1031 struct ext2fs_extent extent; 1032 errcode_t retval; 1033 errcode_t end_err = EXT2_ET_EXTENT_NO_NEXT; 1034 int op = EXT2_EXTENT_NEXT; 1035 int first_op = EXT2_EXTENT_ROOT; 1036 1037 1038 if (check_fs_open(argv[0])) 1039 return; 1040 1041 if (!current_handle) { 1042 com_err(argv[0], 0, "Extent handle not open"); 1043 return; 1044 } 1045 1046 if (argc > 2) { 1047 print_usage: 1048 fprintf(stderr, 1049 "Usage: %s [--leaf-only|--reverse|--reverse-leaf]\n", 1050 argv[0]); 1051 return; 1052 } 1053 1054 if (argc == 2) { 1055 if (!strcmp(argv[1], "--leaf-only")) 1056 op = EXT2_EXTENT_NEXT_LEAF; 1057 else if (!strcmp(argv[1], "--reverse")) { 1058 op = EXT2_EXTENT_PREV; 1059 first_op = EXT2_EXTENT_LAST_LEAF; 1060 end_err = EXT2_ET_EXTENT_NO_PREV; 1061 } else if (!strcmp(argv[1], "--reverse-leaf")) { 1062 op = EXT2_EXTENT_PREV_LEAF; 1063 first_op = EXT2_EXTENT_LAST_LEAF; 1064 end_err = EXT2_ET_EXTENT_NO_PREV; 1065 } else 1066 goto print_usage; 1067 } 1068 1069 retval = ext2fs_extent_get(current_handle, first_op, &extent); 1070 if (retval) { 1071 com_err(argv[0], retval, 0); 1072 return; 1073 } 1074 dbg_print_extent(0, &extent); 1075 1076 while (1) { 1077 retval = ext2fs_extent_get(current_handle, op, &extent); 1078 if (retval == end_err) 1079 break; 1080 1081 if (retval) { 1082 com_err(argv[0], retval, 0); 1083 return; 1084 } 1085 dbg_print_extent(0, &extent); 1086 } 1087} 1088 1089void do_info(int argc, char **argv) 1090{ 1091 struct ext2_extent_info info; 1092 errcode_t retval; 1093 1094 if (check_fs_open(argv[0])) 1095 return; 1096 1097 if (!current_handle) { 1098 com_err(argv[0], 0, "Extent handle not open"); 1099 return; 1100 } 1101 1102 retval = ext2fs_extent_get_info(current_handle, &info); 1103 if (retval) { 1104 com_err(argv[0], retval, 0); 1105 return; 1106 } 1107 1108 printf("Current handle location: %d/%d (max: %d, bytes %d), level %d/%d\n", 1109 info.curr_entry, info.num_entries, info.max_entries, 1110 info.bytes_avail, info.curr_level, info.max_depth); 1111 printf("\tmax lblk: %llu, max pblk: %llu\n", info.max_lblk, 1112 info.max_pblk); 1113 printf("\tmax_len: %u, max_uninit_len: %u\n", info.max_len, 1114 info.max_uninit_len); 1115} 1116 1117void do_goto_block(int argc, char **argv) 1118{ 1119 struct ext2fs_extent extent; 1120 errcode_t retval; 1121 int op = EXT2_EXTENT_NEXT_LEAF; 1122 blk_t blk; 1123 1124 if (check_fs_open(argv[0])) 1125 return; 1126 1127 if (!current_handle) { 1128 com_err(argv[0], 0, "Extent handle not open"); 1129 return; 1130 } 1131 1132 if (argc != 2) { 1133 fprintf(stderr, "%s block\n", argv[0]); 1134 return; 1135 } 1136 1137 if (strtoblk(argv[0], argv[1], &blk)) 1138 return; 1139 1140 retval = ext2fs_extent_goto(current_handle, (blk64_t) blk); 1141 if (retval) { 1142 com_err(argv[0], retval, "while trying to go to block %lu", 1143 blk); 1144 return; 1145 } 1146 1147 generic_goto_node(argv[0], EXT2_EXTENT_CURRENT); 1148} 1149#endif 1150 1151