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