lib/ext2fs/extent.c

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