lib/ext2fs/extent.c

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