extent.c revision 827f45243acc16d3d98332db39d5b4eeadf33a0f
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 "config.h" 13#include <stdio.h> 14#include <string.h> 15#if HAVE_UNISTD_H 16#include <unistd.h> 17#endif 18#if HAVE_ERRNO_H 19#include <errno.h> 20#endif 21#if HAVE_SYS_STAT_H 22#include <sys/stat.h> 23#endif 24#if HAVE_SYS_TYPES_H 25#include <sys/types.h> 26#endif 27 28#include "ext2_fs.h" 29#include "ext2fsP.h" 30#include "e2image.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 struct ext2_inode inodebuf; 58 int type; 59 int level; 60 int max_depth; 61 struct extent_path *path; 62}; 63 64struct ext2_extent_path { 65 errcode_t magic; 66 int leaf_height; 67 blk64_t lblk; 68}; 69 70/* 71 * Useful Debugging stuff 72 */ 73 74#ifdef DEBUG 75static void dbg_show_header(struct ext3_extent_header *eh) 76{ 77 printf("header: magic=%x entries=%u max=%u depth=%u generation=%u\n", 78 ext2fs_le16_to_cpu(eh->eh_magic), 79 ext2fs_le16_to_cpu(eh->eh_entries), 80 ext2fs_le16_to_cpu(eh->eh_max), 81 ext2fs_le16_to_cpu(eh->eh_depth), 82 ext2fs_le32_to_cpu(eh->eh_generation)); 83} 84 85static void dbg_show_index(struct ext3_extent_idx *ix) 86{ 87 printf("index: block=%u leaf=%u leaf_hi=%u unused=%u\n", 88 ext2fs_le32_to_cpu(ix->ei_block), 89 ext2fs_le32_to_cpu(ix->ei_leaf), 90 ext2fs_le16_to_cpu(ix->ei_leaf_hi), 91 ext2fs_le16_to_cpu(ix->ei_unused)); 92} 93 94static void dbg_show_extent(struct ext3_extent *ex) 95{ 96 printf("extent: block=%u-%u len=%u start=%u start_hi=%u\n", 97 ext2fs_le32_to_cpu(ex->ee_block), 98 ext2fs_le32_to_cpu(ex->ee_block) + 99 ext2fs_le16_to_cpu(ex->ee_len) - 1, 100 ext2fs_le16_to_cpu(ex->ee_len), 101 ext2fs_le32_to_cpu(ex->ee_start), 102 ext2fs_le16_to_cpu(ex->ee_start_hi)); 103} 104 105static void dbg_print_extent(char *desc, struct ext2fs_extent *extent) 106{ 107 if (desc) 108 printf("%s: ", desc); 109 printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ", 110 extent->e_lblk, extent->e_lblk + extent->e_len - 1, 111 extent->e_len, extent->e_pblk); 112 if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF) 113 fputs("LEAF ", stdout); 114 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) 115 fputs("UNINIT ", stdout); 116 if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT) 117 fputs("2ND_VISIT ", stdout); 118 if (!extent->e_flags) 119 fputs("(none)", stdout); 120 fputc('\n', stdout); 121 122} 123 124#else 125#define dbg_show_header(eh) do { } while (0) 126#define dbg_show_index(ix) do { } while (0) 127#define dbg_show_extent(ex) do { } while (0) 128#define dbg_print_extent(desc, ex) do { } while (0) 129#endif 130 131/* 132 * Verify the extent header as being sane 133 */ 134errcode_t ext2fs_extent_header_verify(void *ptr, int size) 135{ 136 int eh_max, entry_size; 137 struct ext3_extent_header *eh = ptr; 138 139 dbg_show_header(eh); 140 if (ext2fs_le16_to_cpu(eh->eh_magic) != EXT3_EXT_MAGIC) 141 return EXT2_ET_EXTENT_HEADER_BAD; 142 if (ext2fs_le16_to_cpu(eh->eh_entries) > ext2fs_le16_to_cpu(eh->eh_max)) 143 return EXT2_ET_EXTENT_HEADER_BAD; 144 if (eh->eh_depth == 0) 145 entry_size = sizeof(struct ext3_extent); 146 else 147 entry_size = sizeof(struct ext3_extent_idx); 148 149 eh_max = (size - sizeof(*eh)) / entry_size; 150 /* Allow two extent-sized items at the end of the block, for 151 * ext4_extent_tail with checksum in the future. */ 152 if ((ext2fs_le16_to_cpu(eh->eh_max) > eh_max) || 153 (ext2fs_le16_to_cpu(eh->eh_max) < (eh_max - 2))) 154 return EXT2_ET_EXTENT_HEADER_BAD; 155 156 return 0; 157} 158 159 160/* 161 * Begin functions to handle an inode's extent information 162 */ 163extern void ext2fs_extent_free(ext2_extent_handle_t handle) 164{ 165 int i; 166 167 if (!handle) 168 return; 169 170 if (handle->path) { 171 for (i=1; i <= handle->max_depth; i++) { 172 if (handle->path[i].buf) 173 ext2fs_free_mem(&handle->path[i].buf); 174 } 175 ext2fs_free_mem(&handle->path); 176 } 177 ext2fs_free_mem(&handle); 178} 179 180extern errcode_t ext2fs_extent_open(ext2_filsys fs, ext2_ino_t ino, 181 ext2_extent_handle_t *ret_handle) 182{ 183 return ext2fs_extent_open2(fs, ino, NULL, ret_handle); 184} 185 186extern errcode_t ext2fs_extent_open2(ext2_filsys fs, ext2_ino_t ino, 187 struct ext2_inode *inode, 188 ext2_extent_handle_t *ret_handle) 189{ 190 struct ext2_extent_handle *handle; 191 errcode_t retval; 192 int i; 193 struct ext3_extent_header *eh; 194 195 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 196 197 if (!inode) 198 if ((ino == 0) || (ino > fs->super->s_inodes_count)) 199 return EXT2_ET_BAD_INODE_NUM; 200 201 retval = ext2fs_get_mem(sizeof(struct ext2_extent_handle), &handle); 202 if (retval) 203 return retval; 204 memset(handle, 0, sizeof(struct ext2_extent_handle)); 205 206 handle->ino = ino; 207 handle->fs = fs; 208 209 if (inode) { 210 handle->inode = inode; 211 } else { 212 handle->inode = &handle->inodebuf; 213 retval = ext2fs_read_inode(fs, ino, handle->inode); 214 if (retval) 215 goto errout; 216 } 217 218 eh = (struct ext3_extent_header *) &handle->inode->i_block[0]; 219 220 for (i=0; i < EXT2_N_BLOCKS; i++) 221 if (handle->inode->i_block[i]) 222 break; 223 if (i >= EXT2_N_BLOCKS) { 224 eh->eh_magic = ext2fs_cpu_to_le16(EXT3_EXT_MAGIC); 225 eh->eh_depth = 0; 226 eh->eh_entries = 0; 227 i = (sizeof(handle->inode->i_block) - sizeof(*eh)) / 228 sizeof(struct ext3_extent); 229 eh->eh_max = ext2fs_cpu_to_le16(i); 230 handle->inode->i_flags |= EXT4_EXTENTS_FL; 231 } 232 233 if (!(handle->inode->i_flags & EXT4_EXTENTS_FL)) { 234 retval = EXT2_ET_INODE_NOT_EXTENT; 235 goto errout; 236 } 237 238 retval = ext2fs_extent_header_verify(eh, sizeof(handle->inode->i_block)); 239 if (retval) 240 goto errout; 241 242 handle->max_depth = ext2fs_le16_to_cpu(eh->eh_depth); 243 handle->type = ext2fs_le16_to_cpu(eh->eh_magic); 244 245 retval = ext2fs_get_mem(((handle->max_depth+1) * 246 sizeof(struct extent_path)), 247 &handle->path); 248 memset(handle->path, 0, 249 (handle->max_depth+1) * sizeof(struct extent_path)); 250 handle->path[0].buf = (char *) handle->inode->i_block; 251 252 handle->path[0].left = handle->path[0].entries = 253 ext2fs_le16_to_cpu(eh->eh_entries); 254 handle->path[0].max_entries = ext2fs_le16_to_cpu(eh->eh_max); 255 handle->path[0].curr = 0; 256 handle->path[0].end_blk = 257 (EXT2_I_SIZE(handle->inode) + 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 /* fallthrough */ 378 case EXT2_EXTENT_FIRST_SIB: 379 path->left = path->entries; 380 path->curr = 0; 381 /* fallthrough */ 382 case EXT2_EXTENT_NEXT_SIB: 383 if (path->left <= 0) 384 return EXT2_ET_EXTENT_NO_NEXT; 385 if (path->curr) { 386 ix = path->curr; 387 ix++; 388 } else { 389 eh = (struct ext3_extent_header *) path->buf; 390 ix = EXT_FIRST_INDEX(eh); 391 } 392 path->left--; 393 path->curr = ix; 394 path->visit_num = 0; 395 break; 396 case EXT2_EXTENT_PREV_SIB: 397 if (!path->curr || 398 path->left+1 >= path->entries) 399 return EXT2_ET_EXTENT_NO_PREV; 400 ix = path->curr; 401 ix--; 402 path->curr = ix; 403 path->left++; 404 if (handle->level < handle->max_depth) 405 path->visit_num = 1; 406 break; 407 case EXT2_EXTENT_LAST_SIB: 408 eh = (struct ext3_extent_header *) path->buf; 409 path->curr = EXT_LAST_EXTENT(eh); 410 ix = path->curr; 411 path->left = 0; 412 path->visit_num = 0; 413 break; 414 case EXT2_EXTENT_UP: 415 if (handle->level <= 0) 416 return EXT2_ET_EXTENT_NO_UP; 417 handle->level--; 418 path--; 419 ix = path->curr; 420 if ((orig_op == EXT2_EXTENT_PREV) || 421 (orig_op == EXT2_EXTENT_PREV_LEAF)) 422 path->visit_num = 0; 423 break; 424 case EXT2_EXTENT_DOWN: 425 case EXT2_EXTENT_DOWN_AND_LAST: 426 if (!path->curr ||(handle->level >= handle->max_depth)) 427 return EXT2_ET_EXTENT_NO_DOWN; 428 429 ix = path->curr; 430 newpath = path + 1; 431 if (!newpath->buf) { 432 retval = ext2fs_get_mem(handle->fs->blocksize, 433 &newpath->buf); 434 if (retval) 435 return retval; 436 } 437 blk = ext2fs_le32_to_cpu(ix->ei_leaf) + 438 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32); 439 if ((handle->fs->flags & EXT2_FLAG_IMAGE_FILE) && 440 (handle->fs->io != handle->fs->image_io)) 441 memset(newpath->buf, 0, handle->fs->blocksize); 442 else { 443 retval = io_channel_read_blk64(handle->fs->io, 444 blk, 1, newpath->buf); 445 if (retval) 446 return retval; 447 } 448 handle->level++; 449 450 eh = (struct ext3_extent_header *) newpath->buf; 451 452 retval = ext2fs_extent_header_verify(eh, handle->fs->blocksize); 453 if (retval) { 454 handle->level--; 455 return retval; 456 } 457 458 if (!(handle->fs->flags & EXT2_FLAG_IGNORE_CSUM_ERRORS) && 459 !ext2fs_extent_block_csum_verify(handle->fs, handle->ino, 460 eh)) { 461 handle->level--; 462 return EXT2_ET_EXTENT_CSUM_INVALID; 463 } 464 465 newpath->left = newpath->entries = 466 ext2fs_le16_to_cpu(eh->eh_entries); 467 newpath->max_entries = ext2fs_le16_to_cpu(eh->eh_max); 468 469 if (path->left > 0) { 470 ix++; 471 newpath->end_blk = ext2fs_le32_to_cpu(ix->ei_block); 472 } else 473 newpath->end_blk = path->end_blk; 474 475 path = newpath; 476 if (op == EXT2_EXTENT_DOWN) { 477 ix = EXT_FIRST_INDEX((struct ext3_extent_header *) eh); 478 path->curr = ix; 479 path->left = path->entries - 1; 480 path->visit_num = 0; 481 } else { 482 ix = EXT_LAST_INDEX((struct ext3_extent_header *) eh); 483 path->curr = ix; 484 path->left = 0; 485 if (handle->level < handle->max_depth) 486 path->visit_num = 1; 487 } 488#ifdef DEBUG_GET_EXTENT 489 printf("Down to level %d/%d, end_blk=%llu\n", 490 handle->level, handle->max_depth, 491 path->end_blk); 492#endif 493 break; 494 default: 495 return EXT2_ET_OP_NOT_SUPPORTED; 496 } 497 498 if (!ix) 499 return EXT2_ET_NO_CURRENT_NODE; 500 501 extent->e_flags = 0; 502#ifdef DEBUG_GET_EXTENT 503 printf("(Left %d)\n", path->left); 504#endif 505 506 if (handle->level == handle->max_depth) { 507 ex = (struct ext3_extent *) ix; 508 509 extent->e_pblk = ext2fs_le32_to_cpu(ex->ee_start) + 510 ((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32); 511 extent->e_lblk = ext2fs_le32_to_cpu(ex->ee_block); 512 extent->e_len = ext2fs_le16_to_cpu(ex->ee_len); 513 extent->e_flags |= EXT2_EXTENT_FLAGS_LEAF; 514 if (extent->e_len > EXT_INIT_MAX_LEN) { 515 extent->e_len -= EXT_INIT_MAX_LEN; 516 extent->e_flags |= EXT2_EXTENT_FLAGS_UNINIT; 517 } 518 } else { 519 extent->e_pblk = ext2fs_le32_to_cpu(ix->ei_leaf) + 520 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32); 521 extent->e_lblk = ext2fs_le32_to_cpu(ix->ei_block); 522 if (path->left > 0) { 523 ix++; 524 end_blk = ext2fs_le32_to_cpu(ix->ei_block); 525 } else 526 end_blk = path->end_blk; 527 528 extent->e_len = end_blk - extent->e_lblk; 529 } 530 if (path->visit_num) 531 extent->e_flags |= EXT2_EXTENT_FLAGS_SECOND_VISIT; 532 533 if (((orig_op == EXT2_EXTENT_NEXT_LEAF) || 534 (orig_op == EXT2_EXTENT_PREV_LEAF)) && 535 (handle->level != handle->max_depth)) 536 goto retry; 537 538 if ((orig_op == EXT2_EXTENT_LAST_LEAF) && 539 ((handle->level != handle->max_depth) || 540 (path->left != 0))) 541 goto retry; 542 543 return 0; 544} 545 546static errcode_t update_path(ext2_extent_handle_t handle) 547{ 548 blk64_t blk; 549 errcode_t retval; 550 struct ext3_extent_idx *ix; 551 struct ext3_extent_header *eh; 552 553 if (handle->level == 0) { 554 retval = ext2fs_write_inode(handle->fs, handle->ino, 555 handle->inode); 556 } else { 557 ix = handle->path[handle->level - 1].curr; 558 blk = ext2fs_le32_to_cpu(ix->ei_leaf) + 559 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32); 560 561 /* then update the checksum */ 562 eh = (struct ext3_extent_header *) 563 handle->path[handle->level].buf; 564 retval = ext2fs_extent_block_csum_set(handle->fs, handle->ino, 565 eh); 566 if (retval) 567 return retval; 568 569 retval = io_channel_write_blk64(handle->fs->io, 570 blk, 1, handle->path[handle->level].buf); 571 } 572 return retval; 573} 574 575#if 0 576errcode_t ext2fs_extent_save_path(ext2_extent_handle_t handle, 577 ext2_extent_path_t *ret_path) 578{ 579 ext2_extent_path_t save_path; 580 struct ext2fs_extent extent; 581 struct ext2_extent_info info; 582 errcode_t retval; 583 584 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 585 if (retval) 586 return retval; 587 588 retval = ext2fs_extent_get_info(handle, &info); 589 if (retval) 590 return retval; 591 592 retval = ext2fs_get_mem(sizeof(struct ext2_extent_path), &save_path); 593 if (retval) 594 return retval; 595 memset(save_path, 0, sizeof(struct ext2_extent_path)); 596 597 save_path->magic = EXT2_ET_MAGIC_EXTENT_PATH; 598 save_path->leaf_height = info.max_depth - info.curr_level - 1; 599 save_path->lblk = extent.e_lblk; 600 601 *ret_path = save_path; 602 return 0; 603} 604 605errcode_t ext2fs_extent_free_path(ext2_extent_path_t path) 606{ 607 EXT2_CHECK_MAGIC(path, EXT2_ET_MAGIC_EXTENT_PATH); 608 609 ext2fs_free_mem(&path); 610 return 0; 611} 612#endif 613 614/* 615 * Go to the node at leaf_level which contains logical block blk. 616 * 617 * leaf_level is height from the leaf node level, i.e. 618 * leaf_level 0 is at leaf node, leaf_level 1 is 1 above etc. 619 * 620 * If "blk" has no mapping (hole) then handle is left at last 621 * extent before blk. 622 */ 623errcode_t ext2fs_extent_goto2(ext2_extent_handle_t handle, 624 int leaf_level, blk64_t blk) 625{ 626 struct ext2fs_extent extent; 627 errcode_t retval; 628 629 retval = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent); 630 if (retval) { 631 if (retval == EXT2_ET_EXTENT_NO_NEXT) 632 retval = EXT2_ET_EXTENT_NOT_FOUND; 633 return retval; 634 } 635 636 if (leaf_level > handle->max_depth) { 637#ifdef DEBUG 638 printf("leaf level %d greater than tree depth %d\n", 639 leaf_level, handle->max_depth); 640#endif 641 return EXT2_ET_OP_NOT_SUPPORTED; 642 } 643 644#ifdef DEBUG 645 printf("goto extent ino %u, level %d, %llu\n", handle->ino, 646 leaf_level, blk); 647#endif 648 649#ifdef DEBUG_GOTO_EXTENTS 650 dbg_print_extent("root", &extent); 651#endif 652 while (1) { 653 if (handle->max_depth - handle->level == leaf_level) { 654 /* block is in this &extent */ 655 if ((blk >= extent.e_lblk) && 656 (blk < extent.e_lblk + extent.e_len)) 657 return 0; 658 if (blk < extent.e_lblk) { 659 retval = ext2fs_extent_get(handle, 660 EXT2_EXTENT_PREV_SIB, 661 &extent); 662 return EXT2_ET_EXTENT_NOT_FOUND; 663 } 664 retval = ext2fs_extent_get(handle, 665 EXT2_EXTENT_NEXT_SIB, 666 &extent); 667 if (retval == EXT2_ET_EXTENT_NO_NEXT) 668 return EXT2_ET_EXTENT_NOT_FOUND; 669 if (retval) 670 return retval; 671 continue; 672 } 673 674 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_SIB, 675 &extent); 676 if (retval == EXT2_ET_EXTENT_NO_NEXT) 677 goto go_down; 678 if (retval) 679 return retval; 680 681#ifdef DEBUG_GOTO_EXTENTS 682 dbg_print_extent("next", &extent); 683#endif 684 if (blk == extent.e_lblk) 685 goto go_down; 686 if (blk > extent.e_lblk) 687 continue; 688 689 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_SIB, 690 &extent); 691 if (retval) 692 return retval; 693 694#ifdef DEBUG_GOTO_EXTENTS 695 dbg_print_extent("prev", &extent); 696#endif 697 698 go_down: 699 retval = ext2fs_extent_get(handle, EXT2_EXTENT_DOWN, 700 &extent); 701 if (retval) 702 return retval; 703 704#ifdef DEBUG_GOTO_EXTENTS 705 dbg_print_extent("down", &extent); 706#endif 707 } 708} 709 710errcode_t ext2fs_extent_goto(ext2_extent_handle_t handle, 711 blk64_t blk) 712{ 713 return ext2fs_extent_goto2(handle, 0, blk); 714} 715 716/* 717 * Traverse back up to root fixing parents of current node as needed. 718 * 719 * If we changed start of first entry in a node, fix parent index start 720 * and so on. 721 * 722 * Safe to call for any position in node; if not at the first entry, 723 * will simply return. 724 */ 725errcode_t ext2fs_extent_fix_parents(ext2_extent_handle_t handle) 726{ 727 int retval = 0; 728 int orig_height; 729 blk64_t start; 730 struct extent_path *path; 731 struct ext2fs_extent extent; 732 struct ext2_extent_info info; 733 734 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 735 736 if (!(handle->fs->flags & EXT2_FLAG_RW)) 737 return EXT2_ET_RO_FILSYS; 738 739 if (!handle->path) 740 return EXT2_ET_NO_CURRENT_NODE; 741 742 path = handle->path + handle->level; 743 if (!path->curr) 744 return EXT2_ET_NO_CURRENT_NODE; 745 746 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 747 if (retval) 748 goto done; 749 750 /* modified node's start block */ 751 start = extent.e_lblk; 752 753 if ((retval = ext2fs_extent_get_info(handle, &info))) 754 return retval; 755 orig_height = info.max_depth - info.curr_level; 756 757 /* traverse up until index not first, or startblk matches, or top */ 758 while (handle->level > 0 && 759 (path->left == path->entries - 1)) { 760 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent); 761 if (retval) 762 goto done; 763 if (extent.e_lblk == start) 764 break; 765 path = handle->path + handle->level; 766 extent.e_len += (extent.e_lblk - start); 767 extent.e_lblk = start; 768 retval = ext2fs_extent_replace(handle, 0, &extent); 769 if (retval) 770 goto done; 771 update_path(handle); 772 } 773 774 /* put handle back to where we started */ 775 retval = ext2fs_extent_goto2(handle, orig_height, start); 776done: 777 return retval; 778} 779 780errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle, 781 int flags EXT2FS_ATTR((unused)), 782 struct ext2fs_extent *extent) 783{ 784 struct extent_path *path; 785 struct ext3_extent_idx *ix; 786 struct ext3_extent *ex; 787 788 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 789 790 if (!(handle->fs->flags & EXT2_FLAG_RW)) 791 return EXT2_ET_RO_FILSYS; 792 793 if (!handle->path) 794 return EXT2_ET_NO_CURRENT_NODE; 795 796 path = handle->path + handle->level; 797 if (!path->curr) 798 return EXT2_ET_NO_CURRENT_NODE; 799 800#ifdef DEBUG 801 printf("extent replace: %u ", handle->ino); 802 dbg_print_extent(0, extent); 803#endif 804 805 if (handle->level == handle->max_depth) { 806 ex = path->curr; 807 808 ex->ee_block = ext2fs_cpu_to_le32(extent->e_lblk); 809 ex->ee_start = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF); 810 ex->ee_start_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32); 811 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) { 812 if (extent->e_len > EXT_UNINIT_MAX_LEN) 813 return EXT2_ET_EXTENT_INVALID_LENGTH; 814 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len + 815 EXT_INIT_MAX_LEN); 816 } else { 817 if (extent->e_len > EXT_INIT_MAX_LEN) 818 return EXT2_ET_EXTENT_INVALID_LENGTH; 819 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len); 820 } 821 } else { 822 ix = path->curr; 823 824 ix->ei_leaf = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF); 825 ix->ei_leaf_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32); 826 ix->ei_block = ext2fs_cpu_to_le32(extent->e_lblk); 827 ix->ei_unused = 0; 828 } 829 update_path(handle); 830 return 0; 831} 832 833/* 834 * allocate a new block, move half the current node to it, and update parent 835 * 836 * handle will be left pointing at original record. 837 */ 838errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle) 839{ 840 errcode_t retval = 0; 841 blk64_t new_node_pblk; 842 blk64_t new_node_start; 843 blk64_t orig_lblk; 844 blk64_t goal_blk = 0; 845 int orig_height; 846 char *block_buf = NULL; 847 struct ext2fs_extent extent; 848 struct extent_path *path, *newpath = 0; 849 struct ext3_extent_header *eh, *neweh; 850 int tocopy; 851 int new_root = 0; 852 struct ext2_extent_info info; 853 854 /* basic sanity */ 855 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 856 857 if (!(handle->fs->flags & EXT2_FLAG_RW)) 858 return EXT2_ET_RO_FILSYS; 859 860 if (!handle->path) 861 return EXT2_ET_NO_CURRENT_NODE; 862 863#ifdef DEBUG 864 printf("splitting node at level %d\n", handle->level); 865#endif 866 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 867 if (retval) 868 goto done; 869 870 retval = ext2fs_extent_get_info(handle, &info); 871 if (retval) 872 goto done; 873 874 /* save the position we were originally splitting... */ 875 orig_height = info.max_depth - info.curr_level; 876 orig_lblk = extent.e_lblk; 877 878 /* Is there room in the parent for a new entry? */ 879 if (handle->level && 880 (handle->path[handle->level - 1].entries >= 881 handle->path[handle->level - 1].max_entries)) { 882 883#ifdef DEBUG 884 printf("parent level %d full; splitting it too\n", 885 handle->level - 1); 886#endif 887 /* split the parent */ 888 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent); 889 if (retval) 890 goto done; 891 goal_blk = extent.e_pblk; 892 893 retval = ext2fs_extent_node_split(handle); 894 if (retval) 895 goto done; 896 897 /* get handle back to our original split position */ 898 retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk); 899 if (retval) 900 goto done; 901 } 902 903 /* At this point, parent should have room for this split */ 904 path = handle->path + handle->level; 905 if (!path->curr) 906 return EXT2_ET_NO_CURRENT_NODE; 907 908 /* extent header of the current node we'll split */ 909 eh = (struct ext3_extent_header *)path->buf; 910 911 /* splitting root level means moving them all out */ 912 if (handle->level == 0) { 913 new_root = 1; 914 tocopy = ext2fs_le16_to_cpu(eh->eh_entries); 915 retval = ext2fs_get_mem(((handle->max_depth+2) * 916 sizeof(struct extent_path)), 917 &newpath); 918 if (retval) 919 goto done; 920 memset(newpath, 0, 921 ((handle->max_depth+2) * sizeof(struct extent_path))); 922 } else { 923 tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2; 924 } 925 926#ifdef DEBUG 927 printf("will copy out %d of %d entries at level %d\n", 928 tocopy, ext2fs_le16_to_cpu(eh->eh_entries), 929 handle->level); 930#endif 931 932 if (!tocopy) { 933#ifdef DEBUG 934 printf("Nothing to copy to new block!\n"); 935#endif 936 retval = EXT2_ET_CANT_SPLIT_EXTENT; 937 goto done; 938 } 939 940 /* first we need a new block, or can do nothing. */ 941 block_buf = malloc(handle->fs->blocksize); 942 if (!block_buf) { 943 retval = ENOMEM; 944 goto done; 945 } 946 947 if (!goal_blk) { 948 dgrp_t group = ext2fs_group_of_ino(handle->fs, handle->ino); 949 __u8 log_flex = handle->fs->super->s_log_groups_per_flex; 950 951 if (log_flex) 952 group = group & ~((1 << (log_flex)) - 1); 953 goal_blk = ext2fs_group_first_block2(handle->fs, group); 954 } 955 retval = ext2fs_alloc_block2(handle->fs, goal_blk, block_buf, 956 &new_node_pblk); 957 if (retval) 958 goto done; 959 960#ifdef DEBUG 961 printf("will copy to new node at block %lu\n", 962 (unsigned long) new_node_pblk); 963#endif 964 965 /* Copy data into new block buffer */ 966 /* First the header for the new block... */ 967 neweh = (struct ext3_extent_header *) block_buf; 968 memcpy(neweh, eh, sizeof(struct ext3_extent_header)); 969 neweh->eh_entries = ext2fs_cpu_to_le16(tocopy); 970 neweh->eh_max = ext2fs_cpu_to_le16((handle->fs->blocksize - 971 sizeof(struct ext3_extent_header)) / 972 sizeof(struct ext3_extent)); 973 974 /* then the entries for the new block... */ 975 memcpy(EXT_FIRST_INDEX(neweh), 976 EXT_FIRST_INDEX(eh) + 977 (ext2fs_le16_to_cpu(eh->eh_entries) - tocopy), 978 sizeof(struct ext3_extent_idx) * tocopy); 979 980 new_node_start = ext2fs_le32_to_cpu(EXT_FIRST_INDEX(neweh)->ei_block); 981 982 /* then update the checksum */ 983 retval = ext2fs_extent_block_csum_set(handle->fs, handle->ino, neweh); 984 if (retval) 985 goto done; 986 987 /* ...and write the new node block out to disk. */ 988 retval = io_channel_write_blk64(handle->fs->io, new_node_pblk, 1, 989 block_buf); 990 991 if (retval) 992 goto done; 993 994 /* OK! we've created the new node; now adjust the tree */ 995 996 /* current path now has fewer active entries, we copied some out */ 997 if (handle->level == 0) { 998 memcpy(newpath, path, 999 sizeof(struct extent_path) * (handle->max_depth+1)); 1000 handle->path = newpath; 1001 newpath = path; 1002 path = handle->path; 1003 path->entries = 1; 1004 path->left = path->max_entries - 1; 1005 handle->max_depth++; 1006 eh->eh_depth = ext2fs_cpu_to_le16(handle->max_depth); 1007 } else { 1008 path->entries -= tocopy; 1009 path->left -= tocopy; 1010 } 1011 1012 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 1013 /* this writes out the node, incl. the modified header */ 1014 retval = update_path(handle); 1015 if (retval) 1016 goto done; 1017 1018 /* now go up and insert/replace index for new node we created */ 1019 if (new_root) { 1020 retval = ext2fs_extent_get(handle, EXT2_EXTENT_FIRST_SIB, &extent); 1021 if (retval) 1022 goto done; 1023 1024 extent.e_lblk = new_node_start; 1025 extent.e_pblk = new_node_pblk; 1026 extent.e_len = handle->path[0].end_blk - extent.e_lblk; 1027 retval = ext2fs_extent_replace(handle, 0, &extent); 1028 if (retval) 1029 goto done; 1030 } else { 1031 __u32 new_node_length; 1032 1033 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent); 1034 /* will insert after this one; it's length is shorter now */ 1035 new_node_length = new_node_start - extent.e_lblk; 1036 extent.e_len -= new_node_length; 1037 retval = ext2fs_extent_replace(handle, 0, &extent); 1038 if (retval) 1039 goto done; 1040 1041 /* now set up the new extent and insert it */ 1042 extent.e_lblk = new_node_start; 1043 extent.e_pblk = new_node_pblk; 1044 extent.e_len = new_node_length; 1045 retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER, &extent); 1046 if (retval) 1047 goto done; 1048 } 1049 1050 /* get handle back to our original position */ 1051 retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk); 1052 if (retval) 1053 goto done; 1054 1055 /* new node hooked in, so update inode block count (do this here?) */ 1056 handle->inode->i_blocks += (handle->fs->blocksize * 1057 EXT2FS_CLUSTER_RATIO(handle->fs)) / 512; 1058 retval = ext2fs_write_inode(handle->fs, handle->ino, 1059 handle->inode); 1060 if (retval) 1061 goto done; 1062 1063done: 1064 if (newpath) 1065 ext2fs_free_mem(&newpath); 1066 free(block_buf); 1067 1068 return retval; 1069} 1070 1071errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags, 1072 struct ext2fs_extent *extent) 1073{ 1074 struct extent_path *path; 1075 struct ext3_extent_idx *ix; 1076 struct ext3_extent_header *eh; 1077 errcode_t retval; 1078 1079 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1080 1081 if (!(handle->fs->flags & EXT2_FLAG_RW)) 1082 return EXT2_ET_RO_FILSYS; 1083 1084 if (!handle->path) 1085 return EXT2_ET_NO_CURRENT_NODE; 1086 1087#ifdef DEBUG 1088 printf("extent insert: %u ", handle->ino); 1089 dbg_print_extent(0, extent); 1090#endif 1091 1092 path = handle->path + handle->level; 1093 1094 if (path->entries >= path->max_entries) { 1095 if (flags & EXT2_EXTENT_INSERT_NOSPLIT) { 1096 return EXT2_ET_CANT_INSERT_EXTENT; 1097 } else { 1098#ifdef DEBUG 1099 printf("node full (level %d) - splitting\n", 1100 handle->level); 1101#endif 1102 retval = ext2fs_extent_node_split(handle); 1103 if (retval) 1104 return retval; 1105 path = handle->path + handle->level; 1106 } 1107 } 1108 1109 eh = (struct ext3_extent_header *) path->buf; 1110 if (path->curr) { 1111 ix = path->curr; 1112 if (flags & EXT2_EXTENT_INSERT_AFTER) { 1113 ix++; 1114 path->left--; 1115 } 1116 } else 1117 ix = EXT_FIRST_INDEX(eh); 1118 1119 path->curr = ix; 1120 1121 if (path->left >= 0) 1122 memmove(ix + 1, ix, 1123 (path->left+1) * sizeof(struct ext3_extent_idx)); 1124 path->left++; 1125 path->entries++; 1126 1127 eh = (struct ext3_extent_header *) path->buf; 1128 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 1129 1130 retval = ext2fs_extent_replace(handle, 0, extent); 1131 if (retval) 1132 goto errout; 1133 1134 retval = update_path(handle); 1135 if (retval) 1136 goto errout; 1137 1138 return 0; 1139 1140errout: 1141 ext2fs_extent_delete(handle, 0); 1142 return retval; 1143} 1144 1145/* 1146 * Sets the physical block for a logical file block in the extent tree. 1147 * 1148 * May: map unmapped, unmap mapped, or remap mapped blocks. 1149 * 1150 * Mapping an unmapped block adds a single-block extent. 1151 * 1152 * Unmapping first or last block modifies extent in-place 1153 * - But may need to fix parent's starts too in first-block case 1154 * 1155 * Mapping any unmapped block requires adding a (single-block) extent 1156 * and inserting into proper point in tree. 1157 * 1158 * Modifying (unmapping or remapping) a block in the middle 1159 * of an extent requires splitting the extent. 1160 * - Remapping case requires new single-block extent. 1161 * 1162 * Remapping first or last block adds an extent. 1163 * 1164 * We really need extent adding to be smart about merging. 1165 */ 1166 1167errcode_t ext2fs_extent_set_bmap(ext2_extent_handle_t handle, 1168 blk64_t logical, blk64_t physical, int flags) 1169{ 1170 errcode_t ec, retval = 0; 1171 int mapped = 1; /* logical is mapped? */ 1172 int orig_height; 1173 int extent_uninit = 0; 1174 int prev_uninit = 0; 1175 int next_uninit = 0; 1176 int new_uninit = 0; 1177 int max_len = EXT_INIT_MAX_LEN; 1178 int has_prev, has_next; 1179 blk64_t orig_lblk; 1180 struct extent_path *path; 1181 struct ext2fs_extent extent, next_extent, prev_extent; 1182 struct ext2fs_extent newextent; 1183 struct ext2_extent_info info; 1184 1185 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1186 1187#ifdef DEBUG 1188 printf("set_bmap ino %u log %lld phys %lld flags %d\n", 1189 handle->ino, logical, physical, flags); 1190#endif 1191 1192 if (!(handle->fs->flags & EXT2_FLAG_RW)) 1193 return EXT2_ET_RO_FILSYS; 1194 1195 if (!handle->path) 1196 return EXT2_ET_NO_CURRENT_NODE; 1197 1198 path = handle->path + handle->level; 1199 1200 if (flags & EXT2_EXTENT_SET_BMAP_UNINIT) { 1201 new_uninit = 1; 1202 max_len = EXT_UNINIT_MAX_LEN; 1203 } 1204 1205 /* if (re)mapping, set up new extent to insert */ 1206 if (physical) { 1207 newextent.e_len = 1; 1208 newextent.e_pblk = physical; 1209 newextent.e_lblk = logical; 1210 newextent.e_flags = EXT2_EXTENT_FLAGS_LEAF; 1211 if (new_uninit) 1212 newextent.e_flags |= EXT2_EXTENT_FLAGS_UNINIT; 1213 } 1214 1215 /* special case if the extent tree is completely empty */ 1216 if ((handle->max_depth == 0) && (path->entries == 0)) { 1217 retval = ext2fs_extent_insert(handle, 0, &newextent); 1218 return retval; 1219 } 1220 1221 /* save our original location in the extent tree */ 1222 if ((retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, 1223 &extent))) { 1224 if (retval != EXT2_ET_NO_CURRENT_NODE) 1225 return retval; 1226 memset(&extent, 0, sizeof(extent)); 1227 } 1228 if ((retval = ext2fs_extent_get_info(handle, &info))) 1229 return retval; 1230 orig_height = info.max_depth - info.curr_level; 1231 orig_lblk = extent.e_lblk; 1232 1233 /* go to the logical spot we want to (re/un)map */ 1234 retval = ext2fs_extent_goto(handle, logical); 1235 if (retval) { 1236 if (retval == EXT2_ET_EXTENT_NOT_FOUND) { 1237 retval = 0; 1238 mapped = 0; 1239 if (!physical) { 1240#ifdef DEBUG 1241 printf("block %llu already unmapped\n", 1242 logical); 1243#endif 1244 goto done; 1245 } 1246 } else 1247 goto done; 1248 } 1249 1250 /* 1251 * This may be the extent *before* the requested logical, 1252 * if it's currently unmapped. 1253 * 1254 * Get the previous and next leaf extents, if they are present. 1255 */ 1256 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 1257 if (retval) 1258 goto done; 1259 if (extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 1260 extent_uninit = 1; 1261 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_LEAF, &next_extent); 1262 if (retval) { 1263 has_next = 0; 1264 if (retval != EXT2_ET_EXTENT_NO_NEXT) 1265 goto done; 1266 } else { 1267 dbg_print_extent("set_bmap: next_extent", 1268 &next_extent); 1269 has_next = 1; 1270 if (next_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 1271 next_uninit = 1; 1272 } 1273 retval = ext2fs_extent_goto(handle, logical); 1274 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND) 1275 goto done; 1276 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_LEAF, &prev_extent); 1277 if (retval) { 1278 has_prev = 0; 1279 if (retval != EXT2_ET_EXTENT_NO_PREV) 1280 goto done; 1281 } else { 1282 has_prev = 1; 1283 dbg_print_extent("set_bmap: prev_extent", 1284 &prev_extent); 1285 if (prev_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 1286 prev_uninit = 1; 1287 } 1288 retval = ext2fs_extent_goto(handle, logical); 1289 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND) 1290 goto done; 1291 1292 /* check if already pointing to the requested physical */ 1293 if (mapped && (new_uninit == extent_uninit) && 1294 (extent.e_pblk + (logical - extent.e_lblk) == physical)) { 1295#ifdef DEBUG 1296 printf("physical block (at %llu) unchanged\n", logical); 1297#endif 1298 goto done; 1299 } 1300 1301 if (!mapped) { 1302#ifdef DEBUG 1303 printf("mapping unmapped logical block %llu\n", logical); 1304#endif 1305 if ((logical == extent.e_lblk + extent.e_len) && 1306 (physical == extent.e_pblk + extent.e_len) && 1307 (new_uninit == extent_uninit) && 1308 ((int) extent.e_len < max_len-1)) { 1309 extent.e_len++; 1310 retval = ext2fs_extent_replace(handle, 0, &extent); 1311 } else if ((logical == extent.e_lblk - 1) && 1312 (physical == extent.e_pblk - 1) && 1313 (new_uninit == extent_uninit) && 1314 ((int) extent.e_len < max_len - 1)) { 1315 extent.e_len++; 1316 extent.e_lblk--; 1317 extent.e_pblk--; 1318 retval = ext2fs_extent_replace(handle, 0, &extent); 1319 } else if (has_next && 1320 (logical == next_extent.e_lblk - 1) && 1321 (physical == next_extent.e_pblk - 1) && 1322 (new_uninit == next_uninit) && 1323 ((int) next_extent.e_len < max_len - 1)) { 1324 retval = ext2fs_extent_get(handle, 1325 EXT2_EXTENT_NEXT_LEAF, 1326 &next_extent); 1327 if (retval) 1328 goto done; 1329 next_extent.e_len++; 1330 next_extent.e_lblk--; 1331 next_extent.e_pblk--; 1332 retval = ext2fs_extent_replace(handle, 0, &next_extent); 1333 } else if (logical < extent.e_lblk) 1334 retval = ext2fs_extent_insert(handle, 0, &newextent); 1335 else 1336 retval = ext2fs_extent_insert(handle, 1337 EXT2_EXTENT_INSERT_AFTER, &newextent); 1338 if (retval) 1339 goto done; 1340 retval = ext2fs_extent_fix_parents(handle); 1341 if (retval) 1342 goto done; 1343 } else if ((logical == extent.e_lblk) && (extent.e_len == 1)) { 1344#ifdef DEBUG 1345 printf("(re/un)mapping only block in extent\n"); 1346#endif 1347 if (physical) { 1348 retval = ext2fs_extent_replace(handle, 0, &newextent); 1349 } else { 1350 retval = ext2fs_extent_delete(handle, 0); 1351 if (retval) 1352 goto done; 1353 ec = ext2fs_extent_fix_parents(handle); 1354 if (ec != EXT2_ET_NO_CURRENT_NODE) 1355 retval = ec; 1356 } 1357 1358 if (retval) 1359 goto done; 1360 } else if (logical == extent.e_lblk + extent.e_len - 1) { 1361#ifdef DEBUG 1362 printf("(re/un)mapping last block in extent\n"); 1363#endif 1364 if (physical) { 1365 if (has_next && 1366 (logical == (next_extent.e_lblk - 1)) && 1367 (physical == (next_extent.e_pblk - 1)) && 1368 (new_uninit == next_uninit) && 1369 ((int) next_extent.e_len < max_len - 1)) { 1370 retval = ext2fs_extent_get(handle, 1371 EXT2_EXTENT_NEXT_LEAF, &next_extent); 1372 if (retval) 1373 goto done; 1374 next_extent.e_len++; 1375 next_extent.e_lblk--; 1376 next_extent.e_pblk--; 1377 retval = ext2fs_extent_replace(handle, 0, 1378 &next_extent); 1379 if (retval) 1380 goto done; 1381 } else 1382 retval = ext2fs_extent_insert(handle, 1383 EXT2_EXTENT_INSERT_AFTER, &newextent); 1384 if (retval) 1385 goto done; 1386 /* Now pointing at inserted extent; move back to prev */ 1387 retval = ext2fs_extent_get(handle, 1388 EXT2_EXTENT_PREV_LEAF, 1389 &extent); 1390 if (retval) 1391 goto done; 1392 } 1393 extent.e_len--; 1394 retval = ext2fs_extent_replace(handle, 0, &extent); 1395 if (retval) 1396 goto done; 1397 } else if (logical == extent.e_lblk) { 1398#ifdef DEBUG 1399 printf("(re/un)mapping first block in extent\n"); 1400#endif 1401 if (physical) { 1402 if (has_prev && 1403 (logical == (prev_extent.e_lblk + 1404 prev_extent.e_len)) && 1405 (physical == (prev_extent.e_pblk + 1406 prev_extent.e_len)) && 1407 (new_uninit == prev_uninit) && 1408 ((int) prev_extent.e_len < max_len-1)) { 1409 retval = ext2fs_extent_get(handle, 1410 EXT2_EXTENT_PREV_LEAF, &prev_extent); 1411 if (retval) 1412 goto done; 1413 prev_extent.e_len++; 1414 retval = ext2fs_extent_replace(handle, 0, 1415 &prev_extent); 1416 } else 1417 retval = ext2fs_extent_insert(handle, 1418 0, &newextent); 1419 if (retval) 1420 goto done; 1421 retval = ext2fs_extent_get(handle, 1422 EXT2_EXTENT_NEXT_LEAF, 1423 &extent); 1424 if (retval) 1425 goto done; 1426 } 1427 extent.e_pblk++; 1428 extent.e_lblk++; 1429 extent.e_len--; 1430 retval = ext2fs_extent_replace(handle, 0, &extent); 1431 if (retval) 1432 goto done; 1433 } else { 1434 __u32 orig_length; 1435 1436#ifdef DEBUG 1437 printf("(re/un)mapping in middle of extent\n"); 1438#endif 1439 /* need to split this extent; later */ 1440 1441 orig_length = extent.e_len; 1442 1443 /* shorten pre-split extent */ 1444 extent.e_len = (logical - extent.e_lblk); 1445 retval = ext2fs_extent_replace(handle, 0, &extent); 1446 if (retval) 1447 goto done; 1448 /* insert our new extent, if any */ 1449 if (physical) { 1450 /* insert new extent after current */ 1451 retval = ext2fs_extent_insert(handle, 1452 EXT2_EXTENT_INSERT_AFTER, &newextent); 1453 if (retval) 1454 goto done; 1455 } 1456 /* add post-split extent */ 1457 extent.e_pblk += extent.e_len + 1; 1458 extent.e_lblk += extent.e_len + 1; 1459 extent.e_len = orig_length - extent.e_len - 1; 1460 retval = ext2fs_extent_insert(handle, 1461 EXT2_EXTENT_INSERT_AFTER, &extent); 1462 if (retval) 1463 goto done; 1464 } 1465 1466done: 1467 /* get handle back to its position */ 1468 if (orig_height > handle->max_depth) 1469 orig_height = handle->max_depth; /* In case we shortened the tree */ 1470 ext2fs_extent_goto2(handle, orig_height, orig_lblk); 1471 return retval; 1472} 1473 1474errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags) 1475{ 1476 struct extent_path *path; 1477 char *cp; 1478 struct ext3_extent_header *eh; 1479 errcode_t retval = 0; 1480 1481 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1482 1483 if (!(handle->fs->flags & EXT2_FLAG_RW)) 1484 return EXT2_ET_RO_FILSYS; 1485 1486 if (!handle->path) 1487 return EXT2_ET_NO_CURRENT_NODE; 1488 1489#ifdef DEBUG 1490 { 1491 struct ext2fs_extent extent; 1492 1493 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, 1494 &extent); 1495 if (retval == 0) { 1496 printf("extent delete %u ", handle->ino); 1497 dbg_print_extent(0, &extent); 1498 } 1499 } 1500#endif 1501 1502 path = handle->path + handle->level; 1503 if (!path->curr) 1504 return EXT2_ET_NO_CURRENT_NODE; 1505 1506 cp = path->curr; 1507 1508 if (path->left) { 1509 memmove(cp, cp + sizeof(struct ext3_extent_idx), 1510 path->left * sizeof(struct ext3_extent_idx)); 1511 path->left--; 1512 } else { 1513 struct ext3_extent_idx *ix = path->curr; 1514 ix--; 1515 path->curr = ix; 1516 } 1517 if (--path->entries == 0) 1518 path->curr = 0; 1519 1520 /* if non-root node has no entries left, remove it & parent ptr to it */ 1521 if (path->entries == 0 && handle->level) { 1522 if (!(flags & EXT2_EXTENT_DELETE_KEEP_EMPTY)) { 1523 struct ext2fs_extent extent; 1524 1525 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, 1526 &extent); 1527 if (retval) 1528 return retval; 1529 1530 retval = ext2fs_extent_delete(handle, flags); 1531 handle->inode->i_blocks -= 1532 (handle->fs->blocksize * 1533 EXT2FS_CLUSTER_RATIO(handle->fs)) / 512; 1534 retval = ext2fs_write_inode(handle->fs, handle->ino, 1535 handle->inode); 1536 ext2fs_block_alloc_stats2(handle->fs, 1537 extent.e_pblk, -1); 1538 } 1539 } else { 1540 eh = (struct ext3_extent_header *) path->buf; 1541 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 1542 if ((path->entries == 0) && (handle->level == 0)) 1543 eh->eh_depth = handle->max_depth = 0; 1544 retval = update_path(handle); 1545 } 1546 return retval; 1547} 1548 1549errcode_t ext2fs_extent_get_info(ext2_extent_handle_t handle, 1550 struct ext2_extent_info *info) 1551{ 1552 struct extent_path *path; 1553 1554 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1555 1556 memset(info, 0, sizeof(struct ext2_extent_info)); 1557 1558 path = handle->path + handle->level; 1559 if (path) { 1560 if (path->curr) 1561 info->curr_entry = ((char *) path->curr - path->buf) / 1562 sizeof(struct ext3_extent_idx); 1563 else 1564 info->curr_entry = 0; 1565 info->num_entries = path->entries; 1566 info->max_entries = path->max_entries; 1567 info->bytes_avail = (path->max_entries - path->entries) * 1568 sizeof(struct ext3_extent); 1569 } 1570 1571 info->curr_level = handle->level; 1572 info->max_depth = handle->max_depth; 1573 info->max_lblk = ((__u64) 1 << 32) - 1; 1574 info->max_pblk = ((__u64) 1 << 48) - 1; 1575 info->max_len = (1UL << 15); 1576 info->max_uninit_len = (1UL << 15) - 1; 1577 1578 return 0; 1579} 1580 1581#ifdef DEBUG 1582/* 1583 * Override debugfs's prompt 1584 */ 1585const char *debug_prog_name = "tst_extents"; 1586 1587#endif 1588 1589