extent.c revision 49fed79e7c23783832df3bb137d2db4607fa98a7
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 /* Is there room in the parent for a new entry? */ 938 if (handle->level && 939 (handle->path[handle->level - 1].entries >= 940 handle->path[handle->level - 1].max_entries)) { 941 942#ifdef DEBUG 943 printf("parent level %d full; splitting it too\n", 944 handle->level - 1); 945#endif 946 /* split the parent */ 947 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent); 948 if (retval) 949 goto done; 950 goal_blk = extent.e_pblk; 951 952 retval = extent_node_split(handle, expand_allowed); 953 if (retval) 954 goto done; 955 956 /* get handle back to our original split position */ 957 retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk); 958 if (retval) 959 goto done; 960 } 961 962 /* At this point, parent should have room for this split */ 963 path = handle->path + handle->level; 964 if (!path->curr) 965 return EXT2_ET_NO_CURRENT_NODE; 966 967 /* 968 * Normally, we try to split a full node in half. This doesn't turn 969 * out so well if we're tacking extents on the end of the file because 970 * then we're stuck with a tree of half-full extent blocks. This of 971 * course doesn't apply to the root level. 972 */ 973 no_balance = expand_allowed ? splitting_at_eof(handle, path) : 0; 974 975 /* extent header of the current node we'll split */ 976 eh = (struct ext3_extent_header *)path->buf; 977 978 /* splitting root level means moving them all out */ 979 if (handle->level == 0) { 980 new_root = 1; 981 tocopy = ext2fs_le16_to_cpu(eh->eh_entries); 982 retval = ext2fs_get_memzero((handle->max_paths + 1) * 983 sizeof(struct extent_path), 984 &newpath); 985 if (retval) 986 goto done; 987 } else { 988 if (no_balance) 989 tocopy = 1; 990 else 991 tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2; 992 } 993 994#ifdef DEBUG 995 printf("will copy out %d of %d entries at level %d\n", 996 tocopy, ext2fs_le16_to_cpu(eh->eh_entries), 997 handle->level); 998#endif 999 1000 if (!tocopy && !no_balance) { 1001#ifdef DEBUG 1002 printf("Nothing to copy to new block!\n"); 1003#endif 1004 retval = EXT2_ET_CANT_SPLIT_EXTENT; 1005 goto done; 1006 } 1007 1008 /* first we need a new block, or can do nothing. */ 1009 block_buf = malloc(handle->fs->blocksize); 1010 if (!block_buf) { 1011 retval = ENOMEM; 1012 goto done; 1013 } 1014 1015 if (!goal_blk) { 1016 dgrp_t group = ext2fs_group_of_ino(handle->fs, handle->ino); 1017 __u8 log_flex = handle->fs->super->s_log_groups_per_flex; 1018 1019 if (log_flex) 1020 group = group & ~((1 << (log_flex)) - 1); 1021 goal_blk = ext2fs_group_first_block2(handle->fs, group); 1022 } 1023 retval = ext2fs_alloc_block2(handle->fs, goal_blk, block_buf, 1024 &new_node_pblk); 1025 if (retval) 1026 goto done; 1027 1028#ifdef DEBUG 1029 printf("will copy to new node at block %lu\n", 1030 (unsigned long) new_node_pblk); 1031#endif 1032 1033 /* Copy data into new block buffer */ 1034 /* First the header for the new block... */ 1035 neweh = (struct ext3_extent_header *) block_buf; 1036 memcpy(neweh, eh, sizeof(struct ext3_extent_header)); 1037 neweh->eh_entries = ext2fs_cpu_to_le16(tocopy); 1038 neweh->eh_max = ext2fs_cpu_to_le16((handle->fs->blocksize - 1039 sizeof(struct ext3_extent_header)) / 1040 sizeof(struct ext3_extent)); 1041 1042 /* then the entries for the new block... */ 1043 memcpy(EXT_FIRST_INDEX(neweh), 1044 EXT_FIRST_INDEX(eh) + 1045 (ext2fs_le16_to_cpu(eh->eh_entries) - tocopy), 1046 sizeof(struct ext3_extent_idx) * tocopy); 1047 1048 new_node_start = ext2fs_le32_to_cpu(EXT_FIRST_INDEX(neweh)->ei_block); 1049 1050 /* then update the checksum */ 1051 retval = ext2fs_extent_block_csum_set(handle->fs, handle->ino, neweh); 1052 if (retval) 1053 goto done; 1054 1055 /* ...and write the new node block out to disk. */ 1056 retval = io_channel_write_blk64(handle->fs->io, new_node_pblk, 1, 1057 block_buf); 1058 1059 if (retval) 1060 goto done; 1061 1062 /* OK! we've created the new node; now adjust the tree */ 1063 1064 /* current path now has fewer active entries, we copied some out */ 1065 if (handle->level == 0) { 1066 memcpy(newpath, path, 1067 sizeof(struct extent_path) * handle->max_paths); 1068 handle->path = newpath; 1069 newpath = path; 1070 path = handle->path; 1071 path->entries = 1; 1072 path->left = path->max_entries - 1; 1073 handle->max_depth++; 1074 handle->max_paths++; 1075 eh->eh_depth = ext2fs_cpu_to_le16(handle->max_depth); 1076 } else { 1077 path->entries -= tocopy; 1078 path->left -= tocopy; 1079 } 1080 1081 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 1082 /* this writes out the node, incl. the modified header */ 1083 retval = update_path(handle); 1084 if (retval) 1085 goto done; 1086 1087 /* now go up and insert/replace index for new node we created */ 1088 if (new_root) { 1089 retval = ext2fs_extent_get(handle, EXT2_EXTENT_FIRST_SIB, &extent); 1090 if (retval) 1091 goto done; 1092 1093 extent.e_lblk = new_node_start; 1094 extent.e_pblk = new_node_pblk; 1095 extent.e_len = handle->path[0].end_blk - extent.e_lblk; 1096 retval = ext2fs_extent_replace(handle, 0, &extent); 1097 if (retval) 1098 goto done; 1099 } else { 1100 __u32 new_node_length; 1101 1102 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent); 1103 /* will insert after this one; it's length is shorter now */ 1104 new_node_length = new_node_start - extent.e_lblk; 1105 extent.e_len -= new_node_length; 1106 retval = ext2fs_extent_replace(handle, 0, &extent); 1107 if (retval) 1108 goto done; 1109 1110 /* now set up the new extent and insert it */ 1111 extent.e_lblk = new_node_start; 1112 extent.e_pblk = new_node_pblk; 1113 extent.e_len = new_node_length; 1114 retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER, &extent); 1115 if (retval) 1116 goto done; 1117 } 1118 1119 /* get handle back to our original position */ 1120 retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk); 1121 if (retval) 1122 goto done; 1123 1124 /* new node hooked in, so update inode block count (do this here?) */ 1125 ext2fs_iblk_add_blocks(handle->fs, handle->inode, 1); 1126 retval = ext2fs_write_inode(handle->fs, handle->ino, 1127 handle->inode); 1128 if (retval) 1129 goto done; 1130 1131done: 1132 if (newpath) 1133 ext2fs_free_mem(&newpath); 1134 free(block_buf); 1135 1136 return retval; 1137} 1138 1139errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle) 1140{ 1141 return extent_node_split(handle, 0); 1142} 1143 1144errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags, 1145 struct ext2fs_extent *extent) 1146{ 1147 struct extent_path *path; 1148 struct ext3_extent_idx *ix; 1149 struct ext3_extent_header *eh; 1150 errcode_t retval; 1151 1152 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1153 1154 if (!(handle->fs->flags & EXT2_FLAG_RW)) 1155 return EXT2_ET_RO_FILSYS; 1156 1157 if (!handle->path) 1158 return EXT2_ET_NO_CURRENT_NODE; 1159 1160#ifdef DEBUG 1161 printf("extent insert: %u ", handle->ino); 1162 dbg_print_extent(0, extent); 1163#endif 1164 1165 path = handle->path + handle->level; 1166 1167 if (path->entries >= path->max_entries) { 1168 if (flags & EXT2_EXTENT_INSERT_NOSPLIT) { 1169 return EXT2_ET_CANT_INSERT_EXTENT; 1170 } else { 1171#ifdef DEBUG 1172 printf("node full (level %d) - splitting\n", 1173 handle->level); 1174#endif 1175 retval = extent_node_split(handle, 1); 1176 if (retval) 1177 return retval; 1178 path = handle->path + handle->level; 1179 } 1180 } 1181 1182 eh = (struct ext3_extent_header *) path->buf; 1183 if (path->curr) { 1184 ix = path->curr; 1185 if (flags & EXT2_EXTENT_INSERT_AFTER) { 1186 ix++; 1187 path->left--; 1188 } 1189 } else { 1190 ix = EXT_FIRST_INDEX(eh); 1191 path->left = -1; 1192 } 1193 1194 path->curr = ix; 1195 1196 if (path->left >= 0) 1197 memmove(ix + 1, ix, 1198 (path->left+1) * sizeof(struct ext3_extent_idx)); 1199 path->left++; 1200 path->entries++; 1201 1202 eh = (struct ext3_extent_header *) path->buf; 1203 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 1204 1205 retval = ext2fs_extent_replace(handle, 0, extent); 1206 if (retval) 1207 goto errout; 1208 1209 retval = update_path(handle); 1210 if (retval) 1211 goto errout; 1212 1213 return 0; 1214 1215errout: 1216 ext2fs_extent_delete(handle, 0); 1217 return retval; 1218} 1219 1220/* 1221 * Sets the physical block for a logical file block in the extent tree. 1222 * 1223 * May: map unmapped, unmap mapped, or remap mapped blocks. 1224 * 1225 * Mapping an unmapped block adds a single-block extent. 1226 * 1227 * Unmapping first or last block modifies extent in-place 1228 * - But may need to fix parent's starts too in first-block case 1229 * 1230 * Mapping any unmapped block requires adding a (single-block) extent 1231 * and inserting into proper point in tree. 1232 * 1233 * Modifying (unmapping or remapping) a block in the middle 1234 * of an extent requires splitting the extent. 1235 * - Remapping case requires new single-block extent. 1236 * 1237 * Remapping first or last block adds an extent. 1238 * 1239 * We really need extent adding to be smart about merging. 1240 */ 1241 1242errcode_t ext2fs_extent_set_bmap(ext2_extent_handle_t handle, 1243 blk64_t logical, blk64_t physical, int flags) 1244{ 1245 errcode_t ec, retval = 0; 1246 int mapped = 1; /* logical is mapped? */ 1247 int orig_height; 1248 int extent_uninit = 0; 1249 int prev_uninit = 0; 1250 int next_uninit = 0; 1251 int new_uninit = 0; 1252 int max_len = EXT_INIT_MAX_LEN; 1253 int has_prev, has_next; 1254 blk64_t orig_lblk; 1255 struct extent_path *path; 1256 struct ext2fs_extent extent, next_extent, prev_extent; 1257 struct ext2fs_extent newextent; 1258 struct ext2_extent_info info; 1259 1260 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1261 1262#ifdef DEBUG 1263 printf("set_bmap ino %u log %lld phys %lld flags %d\n", 1264 handle->ino, logical, physical, flags); 1265#endif 1266 1267 if (!(handle->fs->flags & EXT2_FLAG_RW)) 1268 return EXT2_ET_RO_FILSYS; 1269 1270 if (!handle->path) 1271 return EXT2_ET_NO_CURRENT_NODE; 1272 1273 path = handle->path + handle->level; 1274 1275 if (flags & EXT2_EXTENT_SET_BMAP_UNINIT) { 1276 new_uninit = 1; 1277 max_len = EXT_UNINIT_MAX_LEN; 1278 } 1279 1280 /* if (re)mapping, set up new extent to insert */ 1281 if (physical) { 1282 newextent.e_len = 1; 1283 newextent.e_pblk = physical; 1284 newextent.e_lblk = logical; 1285 newextent.e_flags = EXT2_EXTENT_FLAGS_LEAF; 1286 if (new_uninit) 1287 newextent.e_flags |= EXT2_EXTENT_FLAGS_UNINIT; 1288 } 1289 1290 /* special case if the extent tree is completely empty */ 1291 if ((handle->max_depth == 0) && (path->entries == 0)) { 1292 retval = ext2fs_extent_insert(handle, 0, &newextent); 1293 return retval; 1294 } 1295 1296 /* save our original location in the extent tree */ 1297 if ((retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, 1298 &extent))) { 1299 if (retval != EXT2_ET_NO_CURRENT_NODE) 1300 return retval; 1301 memset(&extent, 0, sizeof(extent)); 1302 } 1303 if ((retval = ext2fs_extent_get_info(handle, &info))) 1304 return retval; 1305 orig_height = info.max_depth - info.curr_level; 1306 orig_lblk = extent.e_lblk; 1307 1308 /* go to the logical spot we want to (re/un)map */ 1309 retval = ext2fs_extent_goto(handle, logical); 1310 if (retval) { 1311 if (retval == EXT2_ET_EXTENT_NOT_FOUND) { 1312 retval = 0; 1313 mapped = 0; 1314 if (!physical) { 1315#ifdef DEBUG 1316 printf("block %llu already unmapped\n", 1317 logical); 1318#endif 1319 goto done; 1320 } 1321 } else 1322 goto done; 1323 } 1324 1325 /* 1326 * This may be the extent *before* the requested logical, 1327 * if it's currently unmapped. 1328 * 1329 * Get the previous and next leaf extents, if they are present. 1330 */ 1331 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 1332 if (retval) 1333 goto done; 1334 if (extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 1335 extent_uninit = 1; 1336 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_LEAF, &next_extent); 1337 if (retval) { 1338 has_next = 0; 1339 if (retval != EXT2_ET_EXTENT_NO_NEXT) 1340 goto done; 1341 } else { 1342 dbg_print_extent("set_bmap: next_extent", 1343 &next_extent); 1344 has_next = 1; 1345 if (next_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 1346 next_uninit = 1; 1347 } 1348 retval = ext2fs_extent_goto(handle, logical); 1349 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND) 1350 goto done; 1351 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_LEAF, &prev_extent); 1352 if (retval) { 1353 has_prev = 0; 1354 if (retval != EXT2_ET_EXTENT_NO_PREV) 1355 goto done; 1356 } else { 1357 has_prev = 1; 1358 dbg_print_extent("set_bmap: prev_extent", 1359 &prev_extent); 1360 if (prev_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 1361 prev_uninit = 1; 1362 } 1363 retval = ext2fs_extent_goto(handle, logical); 1364 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND) 1365 goto done; 1366 1367 /* check if already pointing to the requested physical */ 1368 if (mapped && (new_uninit == extent_uninit) && 1369 (extent.e_pblk + (logical - extent.e_lblk) == physical)) { 1370#ifdef DEBUG 1371 printf("physical block (at %llu) unchanged\n", logical); 1372#endif 1373 goto done; 1374 } 1375 1376 if (!mapped) { 1377#ifdef DEBUG 1378 printf("mapping unmapped logical block %llu\n", logical); 1379#endif 1380 if ((logical == extent.e_lblk + extent.e_len) && 1381 (physical == extent.e_pblk + extent.e_len) && 1382 (new_uninit == extent_uninit) && 1383 ((int) extent.e_len < max_len-1)) { 1384 extent.e_len++; 1385 retval = ext2fs_extent_replace(handle, 0, &extent); 1386 } else if ((logical == extent.e_lblk - 1) && 1387 (physical == extent.e_pblk - 1) && 1388 (new_uninit == extent_uninit) && 1389 ((int) extent.e_len < max_len - 1)) { 1390 extent.e_len++; 1391 extent.e_lblk--; 1392 extent.e_pblk--; 1393 retval = ext2fs_extent_replace(handle, 0, &extent); 1394 } else if (has_next && 1395 (logical == next_extent.e_lblk - 1) && 1396 (physical == next_extent.e_pblk - 1) && 1397 (new_uninit == next_uninit) && 1398 ((int) next_extent.e_len < max_len - 1)) { 1399 retval = ext2fs_extent_get(handle, 1400 EXT2_EXTENT_NEXT_LEAF, 1401 &next_extent); 1402 if (retval) 1403 goto done; 1404 next_extent.e_len++; 1405 next_extent.e_lblk--; 1406 next_extent.e_pblk--; 1407 retval = ext2fs_extent_replace(handle, 0, &next_extent); 1408 } else if (logical < extent.e_lblk) 1409 retval = ext2fs_extent_insert(handle, 0, &newextent); 1410 else 1411 retval = ext2fs_extent_insert(handle, 1412 EXT2_EXTENT_INSERT_AFTER, &newextent); 1413 if (retval) 1414 goto done; 1415 retval = ext2fs_extent_fix_parents(handle); 1416 if (retval) 1417 goto done; 1418 } else if ((logical == extent.e_lblk) && (extent.e_len == 1)) { 1419#ifdef DEBUG 1420 printf("(re/un)mapping only block in extent\n"); 1421#endif 1422 if (physical) { 1423 retval = ext2fs_extent_replace(handle, 0, &newextent); 1424 } else { 1425 retval = ext2fs_extent_delete(handle, 0); 1426 if (retval) 1427 goto done; 1428 ec = ext2fs_extent_fix_parents(handle); 1429 if (ec != EXT2_ET_NO_CURRENT_NODE) 1430 retval = ec; 1431 } 1432 1433 if (retval) 1434 goto done; 1435 } else if (logical == extent.e_lblk + extent.e_len - 1) { 1436#ifdef DEBUG 1437 printf("(re/un)mapping last block in extent\n"); 1438#endif 1439 if (physical) { 1440 if (has_next && 1441 (logical == (next_extent.e_lblk - 1)) && 1442 (physical == (next_extent.e_pblk - 1)) && 1443 (new_uninit == next_uninit) && 1444 ((int) next_extent.e_len < max_len - 1)) { 1445 retval = ext2fs_extent_get(handle, 1446 EXT2_EXTENT_NEXT_LEAF, &next_extent); 1447 if (retval) 1448 goto done; 1449 next_extent.e_len++; 1450 next_extent.e_lblk--; 1451 next_extent.e_pblk--; 1452 retval = ext2fs_extent_replace(handle, 0, 1453 &next_extent); 1454 if (retval) 1455 goto done; 1456 } else 1457 retval = ext2fs_extent_insert(handle, 1458 EXT2_EXTENT_INSERT_AFTER, &newextent); 1459 if (retval) 1460 goto done; 1461 retval = ext2fs_extent_fix_parents(handle); 1462 if (retval) 1463 goto done; 1464 /* 1465 * Now pointing at inserted extent; move back to prev. 1466 * 1467 * We cannot use EXT2_EXTENT_PREV to go back; note the 1468 * subtlety in the comment for fix_parents(). 1469 */ 1470 retval = ext2fs_extent_goto(handle, logical); 1471 if (retval) 1472 goto done; 1473 retval = ext2fs_extent_get(handle, 1474 EXT2_EXTENT_CURRENT, 1475 &extent); 1476 if (retval) 1477 goto done; 1478 } 1479 extent.e_len--; 1480 retval = ext2fs_extent_replace(handle, 0, &extent); 1481 if (retval) 1482 goto done; 1483 } else if (logical == extent.e_lblk) { 1484#ifdef DEBUG 1485 printf("(re/un)mapping first block in extent\n"); 1486#endif 1487 if (physical) { 1488 if (has_prev && 1489 (logical == (prev_extent.e_lblk + 1490 prev_extent.e_len)) && 1491 (physical == (prev_extent.e_pblk + 1492 prev_extent.e_len)) && 1493 (new_uninit == prev_uninit) && 1494 ((int) prev_extent.e_len < max_len-1)) { 1495 retval = ext2fs_extent_get(handle, 1496 EXT2_EXTENT_PREV_LEAF, &prev_extent); 1497 if (retval) 1498 goto done; 1499 prev_extent.e_len++; 1500 retval = ext2fs_extent_replace(handle, 0, 1501 &prev_extent); 1502 } else 1503 retval = ext2fs_extent_insert(handle, 1504 0, &newextent); 1505 if (retval) 1506 goto done; 1507 retval = ext2fs_extent_fix_parents(handle); 1508 if (retval) 1509 goto done; 1510 retval = ext2fs_extent_get(handle, 1511 EXT2_EXTENT_NEXT_LEAF, 1512 &extent); 1513 if (retval) 1514 goto done; 1515 } 1516 extent.e_pblk++; 1517 extent.e_lblk++; 1518 extent.e_len--; 1519 retval = ext2fs_extent_replace(handle, 0, &extent); 1520 if (retval) 1521 goto done; 1522 retval = ext2fs_extent_fix_parents(handle); 1523 if (retval) 1524 goto done; 1525 } else { 1526 __u32 orig_length; 1527 blk64_t orig_lblk; 1528 struct ext2fs_extent orig_extent; 1529 errcode_t r2; 1530 1531#ifdef DEBUG 1532 printf("(re/un)mapping in middle of extent\n"); 1533#endif 1534 /* need to split this extent; later */ 1535 orig_lblk = extent.e_lblk; 1536 orig_length = extent.e_len; 1537 orig_extent = extent; 1538 1539 /* shorten pre-split extent */ 1540 extent.e_len = (logical - extent.e_lblk); 1541 retval = ext2fs_extent_replace(handle, 0, &extent); 1542 if (retval) 1543 goto done; 1544 /* insert our new extent, if any */ 1545 if (physical) { 1546 /* insert new extent after current */ 1547 retval = ext2fs_extent_insert(handle, 1548 EXT2_EXTENT_INSERT_AFTER, &newextent); 1549 if (retval) { 1550 r2 = ext2fs_extent_goto(handle, orig_lblk); 1551 if (r2 == 0) 1552 (void)ext2fs_extent_replace(handle, 0, 1553 &orig_extent); 1554 goto done; 1555 } 1556 } 1557 /* add post-split extent */ 1558 extent.e_pblk += extent.e_len + 1; 1559 extent.e_lblk += extent.e_len + 1; 1560 extent.e_len = orig_length - extent.e_len - 1; 1561 retval = ext2fs_extent_insert(handle, 1562 EXT2_EXTENT_INSERT_AFTER, &extent); 1563 if (retval) { 1564 if (physical) { 1565 r2 = ext2fs_extent_goto(handle, 1566 newextent.e_lblk); 1567 if (r2 == 0) 1568 (void)ext2fs_extent_delete(handle, 0); 1569 } 1570 r2 = ext2fs_extent_goto(handle, orig_lblk); 1571 if (r2 == 0) 1572 (void)ext2fs_extent_replace(handle, 0, 1573 &orig_extent); 1574 goto done; 1575 } 1576 } 1577 1578done: 1579 /* get handle back to its position */ 1580 if (orig_height > handle->max_depth) 1581 orig_height = handle->max_depth; /* In case we shortened the tree */ 1582 ext2fs_extent_goto2(handle, orig_height, orig_lblk); 1583 return retval; 1584} 1585 1586errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags) 1587{ 1588 struct extent_path *path; 1589 char *cp; 1590 struct ext3_extent_header *eh; 1591 errcode_t retval = 0; 1592 1593 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1594 1595 if (!(handle->fs->flags & EXT2_FLAG_RW)) 1596 return EXT2_ET_RO_FILSYS; 1597 1598 if (!handle->path) 1599 return EXT2_ET_NO_CURRENT_NODE; 1600 1601#ifdef DEBUG 1602 { 1603 struct ext2fs_extent extent; 1604 1605 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, 1606 &extent); 1607 if (retval == 0) { 1608 printf("extent delete %u ", handle->ino); 1609 dbg_print_extent(0, &extent); 1610 } 1611 } 1612#endif 1613 1614 path = handle->path + handle->level; 1615 if (!path->curr) 1616 return EXT2_ET_NO_CURRENT_NODE; 1617 1618 cp = path->curr; 1619 1620 if (path->left) { 1621 memmove(cp, cp + sizeof(struct ext3_extent_idx), 1622 path->left * sizeof(struct ext3_extent_idx)); 1623 path->left--; 1624 } else { 1625 struct ext3_extent_idx *ix = path->curr; 1626 ix--; 1627 path->curr = ix; 1628 } 1629 if (--path->entries == 0) 1630 path->curr = 0; 1631 1632 /* if non-root node has no entries left, remove it & parent ptr to it */ 1633 if (path->entries == 0 && handle->level) { 1634 if (!(flags & EXT2_EXTENT_DELETE_KEEP_EMPTY)) { 1635 struct ext2fs_extent extent; 1636 1637 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, 1638 &extent); 1639 if (retval) 1640 return retval; 1641 1642 retval = ext2fs_extent_delete(handle, flags); 1643 handle->inode->i_blocks -= 1644 (handle->fs->blocksize * 1645 EXT2FS_CLUSTER_RATIO(handle->fs)) / 512; 1646 retval = ext2fs_write_inode(handle->fs, handle->ino, 1647 handle->inode); 1648 ext2fs_block_alloc_stats2(handle->fs, 1649 extent.e_pblk, -1); 1650 } 1651 } else { 1652 eh = (struct ext3_extent_header *) path->buf; 1653 eh->eh_entries = ext2fs_cpu_to_le16(path->entries); 1654 if ((path->entries == 0) && (handle->level == 0)) 1655 eh->eh_depth = handle->max_depth = 0; 1656 retval = update_path(handle); 1657 } 1658 return retval; 1659} 1660 1661errcode_t ext2fs_extent_get_info(ext2_extent_handle_t handle, 1662 struct ext2_extent_info *info) 1663{ 1664 struct extent_path *path; 1665 1666 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); 1667 1668 memset(info, 0, sizeof(struct ext2_extent_info)); 1669 1670 path = handle->path + handle->level; 1671 if (path) { 1672 if (path->curr) 1673 info->curr_entry = ((char *) path->curr - path->buf) / 1674 sizeof(struct ext3_extent_idx); 1675 else 1676 info->curr_entry = 0; 1677 info->num_entries = path->entries; 1678 info->max_entries = path->max_entries; 1679 info->bytes_avail = (path->max_entries - path->entries) * 1680 sizeof(struct ext3_extent); 1681 } 1682 1683 info->curr_level = handle->level; 1684 info->max_depth = handle->max_depth; 1685 info->max_lblk = ((__u64) 1 << 32) - 1; 1686 info->max_pblk = ((__u64) 1 << 48) - 1; 1687 info->max_len = (1UL << 15); 1688 info->max_uninit_len = (1UL << 15) - 1; 1689 1690 return 0; 1691} 1692 1693#ifdef DEBUG 1694/* 1695 * Override debugfs's prompt 1696 */ 1697const char *debug_prog_name = "tst_extents"; 1698 1699#endif 1700 1701