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