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