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