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