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