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