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