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