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