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