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