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