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