lib/ext2fs/extent.c

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