lib/ext2fs/extent.c

   1 /*
   2  * extent.c --- routines to implement extents support
   3  *
   4  * Copyright (C) 2007 Theodore Ts'o.
   5  *
   6  * %Begin-Header%
   7  * This file may be redistributed under the terms of the GNU Public
   8  * License.
   9  * %End-Header%
  10  */
  11
  12 #include <stdio.h>
  13 #include <string.h>
  14 #if HAVE_UNISTD_H
  15 #include <unistd.h>
  16 #endif
  17 #if HAVE_ERRNO_H
  18 #include <errno.h>
  19 #endif
  20 #if HAVE_SYS_STAT_H
  21 #include <sys/stat.h>
  22 #endif
  23 #if HAVE_SYS_TYPES_H
  24 #include <sys/types.h>
  25 #endif
  26
  27 #include "ext2_fs.h"
  28 #include "ext2fsP.h"
  29 #include "e2image.h"
  30 #include "ss/ss.h"
  31
  32 /*
  33  * Definitions to be dropped in lib/ext2fs/ext2fs.h
  34  */
  35
  36 /*
  37  * Private definitions
  38  */
  39
  40 struct extent_path {
  41         char            *buf;
  42         int             entries;
  43         int             max_entries;
  44         int             left;
  45         int             visit_num;
  46         int             flags;
  47         blk64_t         end_blk;
  48         void            *curr;
  49 };
  50
  51
  52 struct ext2_extent_handle {
  53         errcode_t               magic;
  54         ext2_filsys             fs;
  55         ext2_ino_t              ino;
  56         struct ext2_inode       *inode;
  57         int                     type;
  58         int                     level;
  59         int                     max_depth;
  60         struct extent_path      *path;
  61 };
  62
  63 struct ext2_extent_path {
  64         errcode_t               magic;
  65         int                     leaf_height;
  66         blk64_t                 lblk;
  67 };
  68
  69 /*
  70  *  Useful Debugging stuff
  71  */
  72
  73 #ifdef DEBUG
  74 static void dbg_show_header(struct ext3_extent_header *eh)
  75 {
  76         printf("header: magic=%x entries=%u max=%u depth=%u generation=%u\n",
  77                eh->eh_magic, eh->eh_entries, eh->eh_max, eh->eh_depth,
  78                eh->eh_generation);
  79 }
  80
  81 static void dbg_show_index(struct ext3_extent_idx *ix)
  82 {
  83         printf("index: block=%u leaf=%u leaf_hi=%u unused=%u\n",
  84                ix->ei_block, ix->ei_leaf, ix->ei_leaf_hi, ix->ei_unused);
  85 }
  86
  87 static void dbg_show_extent(struct ext3_extent *ex)
  88 {
  89         printf("extent: block=%u-%u len=%u start=%u start_hi=%u\n",
  90                ex->ee_block, ex->ee_block + ex->ee_len - 1,
  91                ex->ee_len, ex->ee_start, ex->ee_start_hi);
  92 }
  93
  94 static void dbg_print_extent(char *desc, struct ext2fs_extent *extent)
  95 {
  96         if (desc)
  97                 printf("%s: ", desc);
  98         printf("extent: lblk %llu--%llu, len %lu, pblk %llu, flags: ",
  99                extent->e_lblk, extent->e_lblk + extent->e_len - 1,
 100                extent->e_len, extent->e_pblk);
 101         if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF)
 102                 fputs("LEAF ", stdout);
 103         if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT)
 104                 fputs("UNINIT ", stdout);
 105         if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT)
 106                 fputs("2ND_VISIT ", stdout);
 107         if (!extent->e_flags)
 108                 fputs("(none)", stdout);
 109         fputc('\n', stdout);
 110
 111 }
 112
 113 #define dbg_printf(fmt, args...) printf(fmt, ## args)
 114 #else
 115 #define dbg_show_header(eh) do { } while (0)
 116 #define dbg_show_index(ix) do { } while (0)
 117 #define dbg_show_extent(ex) do { } while (0)
 118 #define dbg_print_extent(desc, ex) do { } while (0)
 119 #define dbg_printf(fmt, args...) do { } while (0)
 120 #endif
 121
 122 /*
 123  * Verify the extent header as being sane
 124  */
 125 errcode_t ext2fs_extent_header_verify(void *ptr, int size)
 126 {
 127         int eh_max, entry_size;
 128         struct ext3_extent_header *eh = ptr;
 129
 130         dbg_show_header(eh);
 131         if (ext2fs_le16_to_cpu(eh->eh_magic) != EXT3_EXT_MAGIC)
 132                 return EXT2_ET_EXTENT_HEADER_BAD;
 133         if (ext2fs_le16_to_cpu(eh->eh_entries) > ext2fs_le16_to_cpu(eh->eh_max))
 134                 return EXT2_ET_EXTENT_HEADER_BAD;
 135         if (eh->eh_depth == 0)
 136                 entry_size = sizeof(struct ext3_extent);
 137         else
 138                 entry_size = sizeof(struct ext3_extent_idx);
 139
 140         eh_max = (size - sizeof(*eh)) / entry_size;
 141         /* Allow two extent-sized items at the end of the block, for
 142          * ext4_extent_tail with checksum in the future. */
 143         if ((ext2fs_le16_to_cpu(eh->eh_max) > eh_max) ||
 144             (ext2fs_le16_to_cpu(eh->eh_max) < (eh_max - 2)))
 145                 return EXT2_ET_EXTENT_HEADER_BAD;
 146
 147         return 0;
 148 }
 149
 150
 151 /*
 152  * Begin functions to handle an inode's extent information
 153  */
 154 extern void ext2fs_extent_free(ext2_extent_handle_t handle)
 155 {
 156         int                     i;
 157
 158         if (!handle)
 159                 return;
 160
 161         if (handle->inode)
 162                 ext2fs_free_mem(&handle->inode);
 163         if (handle->path) {
 164                 for (i=1; i < handle->max_depth; i++) {
 165                         if (handle->path[i].buf)
 166                                 ext2fs_free_mem(&handle->path[i].buf);
 167                 }
 168                 ext2fs_free_mem(&handle->path);
 169         }
 170         ext2fs_free_mem(&handle);
 171 }
 172
 173 extern errcode_t ext2fs_extent_open(ext2_filsys fs, ext2_ino_t ino,
 174                                     ext2_extent_handle_t *ret_handle)
 175 {
 176         struct ext2_extent_handle       *handle;
 177         errcode_t                       retval;
 178         int                             isize = EXT2_INODE_SIZE(fs->super);
 179         struct ext3_extent_header       *eh;
 180
 181         EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
 182
 183         if ((ino == 0) || (ino > fs->super->s_inodes_count))
 184                 return EXT2_ET_BAD_INODE_NUM;
 185
 186         retval = ext2fs_get_mem(sizeof(struct ext2_extent_handle), &handle);
 187         if (retval)
 188                 return retval;
 189         memset(handle, 0, sizeof(struct ext2_extent_handle));
 190
 191         retval = ext2fs_get_mem(isize, &handle->inode);
 192         if (retval)
 193                 goto errout;
 194
 195         handle->ino = ino;
 196         handle->fs = fs;
 197
 198         retval = ext2fs_read_inode_full(fs, ino, handle->inode, isize);
 199         if (retval)
 200                 goto errout;
 201
 202         if (!(handle->inode->i_flags & EXT4_EXTENTS_FL))
 203                 return EXT2_ET_INODE_NOT_EXTENT;
 204
 205         eh = (struct ext3_extent_header *) &handle->inode->i_block[0];
 206
 207         retval = ext2fs_extent_header_verify(eh, sizeof(handle->inode->i_block));
 208         if (retval)
 209                 return (retval);
 210
 211         handle->max_depth = ext2fs_le16_to_cpu(eh->eh_depth);
 212         handle->type = ext2fs_le16_to_cpu(eh->eh_magic);
 213
 214         retval = ext2fs_get_mem(((handle->max_depth+1) *
 215                                  sizeof(struct extent_path)),
 216                                 &handle->path);
 217         memset(handle->path, 0,
 218                (handle->max_depth+1) * sizeof(struct extent_path));
 219         handle->path[0].buf = (char *) handle->inode->i_block;
 220
 221         handle->path[0].left = handle->path[0].entries =
 222                 ext2fs_le16_to_cpu(eh->eh_entries);
 223         handle->path[0].max_entries = ext2fs_le16_to_cpu(eh->eh_max);
 224         handle->path[0].curr = 0;
 225         handle->path[0].end_blk =
 226                 ((((__u64) handle->inode->i_size_high << 32) +
 227                   handle->inode->i_size + (fs->blocksize - 1))
 228                  >> EXT2_BLOCK_SIZE_BITS(fs->super));
 229         handle->path[0].visit_num = 1;
 230         handle->level = 0;
 231         handle->magic = EXT2_ET_MAGIC_EXTENT_HANDLE;
 232
 233         *ret_handle = handle;
 234         return 0;
 235
 236 errout:
 237         ext2fs_extent_free(handle);
 238         return retval;
 239 }
 240
 241 /*
 242  * This function is responsible for (optionally) moving through the
 243  * extent tree and then returning the current extent
 244  */
 245 errcode_t ext2fs_extent_get(ext2_extent_handle_t handle,
 246                             int flags, struct ext2fs_extent *extent)
 247 {
 248         struct extent_path      *path, *newpath;
 249         struct ext3_extent_header       *eh;
 250         struct ext3_extent_idx          *ix = 0;
 251         struct ext3_extent              *ex;
 252         errcode_t                       retval;
 253         blk_t                           blk;
 254         blk64_t                         end_blk;
 255         int                             orig_op, op;
 256
 257         EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
 258
 259         if (!handle->path)
 260                 return EXT2_ET_NO_CURRENT_NODE;
 261
 262         orig_op = op = flags & EXT2_EXTENT_MOVE_MASK;
 263
 264 retry:
 265         path = handle->path + handle->level;
 266         if ((orig_op == EXT2_EXTENT_NEXT) ||
 267             (orig_op == EXT2_EXTENT_NEXT_LEAF)) {
 268                 if (handle->level < handle->max_depth) {
 269                         /* interior node */
 270                         if (path->visit_num == 0) {
 271                                 path->visit_num++;
 272                                 op = EXT2_EXTENT_DOWN;
 273                         } else if (path->left > 0)
 274                                 op = EXT2_EXTENT_NEXT_SIB;
 275                         else if (handle->level > 0)
 276                                 op = EXT2_EXTENT_UP;
 277                         else
 278                                 return EXT2_ET_EXTENT_NO_NEXT;
 279                 } else {
 280                         /* leaf node */
 281                         if (path->left > 0)
 282                                 op = EXT2_EXTENT_NEXT_SIB;
 283                         else if (handle->level > 0)
 284                                 op = EXT2_EXTENT_UP;
 285                         else
 286                                 return EXT2_ET_EXTENT_NO_NEXT;
 287                 }
 288                 if (op != EXT2_EXTENT_NEXT_SIB) {
 289                         dbg_printf("<<<< OP = %s\n",
 290                                (op == EXT2_EXTENT_DOWN) ? "down" :
 291                                ((op == EXT2_EXTENT_UP) ? "up" : "unknown"));
 292                 }
 293         }
 294
 295         if ((orig_op == EXT2_EXTENT_PREV) ||
 296             (orig_op == EXT2_EXTENT_PREV_LEAF)) {
 297                 if (handle->level < handle->max_depth) {
 298                         /* interior node */
 299                         if (path->visit_num > 0 ) {
 300                                 /* path->visit_num = 0; */
 301                                 op = EXT2_EXTENT_DOWN_AND_LAST;
 302                         } else if (path->left < path->entries-1)
 303                                 op = EXT2_EXTENT_PREV_SIB;
 304                         else if (handle->level > 0)
 305                                 op = EXT2_EXTENT_UP;
 306                         else
 307                                 return EXT2_ET_EXTENT_NO_PREV;
 308                 } else {
 309                         /* leaf node */
 310                         if (path->left < path->entries-1)
 311                                 op = EXT2_EXTENT_PREV_SIB;
 312                         else if (handle->level > 0)
 313                                 op = EXT2_EXTENT_UP;
 314                         else
 315                                 return EXT2_ET_EXTENT_NO_PREV;
 316                 }
 317                 if (op != EXT2_EXTENT_PREV_SIB) {
 318                         dbg_printf("<<<< OP = %s\n",
 319                                (op == EXT2_EXTENT_DOWN_AND_LAST) ? "down/last" :
 320                                ((op == EXT2_EXTENT_UP) ? "up" : "unknown"));
 321                 }
 322         }
 323
 324         if (orig_op == EXT2_EXTENT_LAST_LEAF) {
 325                 if ((handle->level < handle->max_depth) &&
 326                     (path->left == 0))
 327                         op = EXT2_EXTENT_DOWN;
 328                 else
 329                         op = EXT2_EXTENT_LAST_SIB;
 330                 dbg_printf("<<<< OP = %s\n",
 331                            (op == EXT2_EXTENT_DOWN) ? "down" : "last_sib");
 332         }
 333
 334         switch (op) {
 335         case EXT2_EXTENT_CURRENT:
 336                 ix = path->curr;
 337                 break;
 338         case EXT2_EXTENT_ROOT:
 339                 handle->level = 0;
 340                 path = handle->path + handle->level;
 341         case EXT2_EXTENT_FIRST_SIB:
 342                 path->left = path->entries;
 343                 path->curr = 0;
 344         case EXT2_EXTENT_NEXT_SIB:
 345                 if (path->left <= 0)
 346                         return EXT2_ET_EXTENT_NO_NEXT;
 347                 if (path->curr) {
 348                         ix = path->curr;
 349                         ix++;
 350                 } else {
 351                         eh = (struct ext3_extent_header *) path->buf;
 352                         ix = EXT_FIRST_INDEX(eh);
 353                 }
 354                 path->left--;
 355                 path->curr = ix;
 356                 path->visit_num = 0;
 357                 break;
 358         case EXT2_EXTENT_PREV_SIB:
 359                 if (!path->curr ||
 360                     path->left+1 >= path->entries)
 361                         return EXT2_ET_EXTENT_NO_PREV;
 362                 ix = path->curr;
 363                 ix--;
 364                 path->curr = ix;
 365                 path->left++;
 366                 if (handle->level < handle->max_depth)
 367                         path->visit_num = 1;
 368                 break;
 369         case EXT2_EXTENT_LAST_SIB:
 370                 eh = (struct ext3_extent_header *) path->buf;
 371                 path->curr = EXT_LAST_EXTENT(eh);
 372                 ix = path->curr;
 373                 path->left = 0;
 374                 path->visit_num = 0;
 375                 break;
 376         case EXT2_EXTENT_UP:
 377                 if (handle->level <= 0)
 378                         return EXT2_ET_EXTENT_NO_UP;
 379                 handle->level--;
 380                 path--;
 381                 ix = path->curr;
 382                 if ((orig_op == EXT2_EXTENT_PREV) ||
 383                     (orig_op == EXT2_EXTENT_PREV_LEAF))
 384                         path->visit_num = 0;
 385                 break;
 386         case EXT2_EXTENT_DOWN:
 387         case EXT2_EXTENT_DOWN_AND_LAST:
 388                 if (!path->curr ||(handle->level >= handle->max_depth))
 389                         return EXT2_ET_EXTENT_NO_DOWN;
 390
 391                 ix = path->curr;
 392                 newpath = path + 1;
 393                 if (!newpath->buf) {
 394                         retval = ext2fs_get_mem(handle->fs->blocksize,
 395                                                 &newpath->buf);
 396                         if (retval)
 397                                 return retval;
 398                 }
 399                 blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
 400                         ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
 401                 if ((handle->fs->flags & EXT2_FLAG_IMAGE_FILE) &&
 402                     (handle->fs->io != handle->fs->image_io))
 403                         memset(newpath->buf, 0, handle->fs->blocksize);
 404                 else {
 405                         retval = io_channel_read_blk(handle->fs->io,
 406                                                      blk, 1, newpath->buf);
 407                         if (retval)
 408                                 return retval;
 409                 }
 410                 handle->level++;
 411
 412                 eh = (struct ext3_extent_header *) newpath->buf;
 413
 414                 retval = ext2fs_extent_header_verify(eh, handle->fs->blocksize);
 415                 if (retval)
 416                         return retval;
 417
 418                 newpath->left = newpath->entries =
 419                         ext2fs_le16_to_cpu(eh->eh_entries);
 420                 newpath->max_entries = ext2fs_le16_to_cpu(eh->eh_max);
 421
 422                 if (path->left > 0) {
 423                         ix++;
 424                         newpath->end_blk = ext2fs_le32_to_cpu(ix->ei_block);
 425                 } else
 426                         newpath->end_blk = path->end_blk;
 427
 428                 path = newpath;
 429                 if (op == EXT2_EXTENT_DOWN) {
 430                         ix = EXT_FIRST_INDEX((struct ext3_extent_header *) eh);
 431                         path->curr = ix;
 432                         path->left = path->entries - 1;
 433                         path->visit_num = 0;
 434                 } else {
 435                         ix = EXT_LAST_INDEX((struct ext3_extent_header *) eh);
 436                         path->curr = ix;
 437                         path->left = 0;
 438                         if (handle->level < handle->max_depth)
 439                                 path->visit_num = 1;
 440                 }
 441
 442                 dbg_printf("Down to level %d/%d, end_blk=%llu\n",
 443                            handle->level, handle->max_depth,
 444                            path->end_blk);
 445
 446                 break;
 447         default:
 448                 return EXT2_ET_OP_NOT_SUPPORTED;
 449         }
 450
 451         if (!ix)
 452                 return EXT2_ET_NO_CURRENT_NODE;
 453
 454         extent->e_flags = 0;
 455         dbg_printf("(Left %d)\n", path->left);
 456
 457         if (handle->level == handle->max_depth) {
 458                 ex = (struct ext3_extent *) ix;
 459
 460                 extent->e_pblk = ext2fs_le32_to_cpu(ex->ee_start) +
 461                         ((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32);
 462                 extent->e_lblk = ext2fs_le32_to_cpu(ex->ee_block);
 463                 extent->e_len = ext2fs_le16_to_cpu(ex->ee_len);
 464                 extent->e_flags |= EXT2_EXTENT_FLAGS_LEAF;
 465                 if (extent->e_len > EXT_INIT_MAX_LEN) {
 466                         extent->e_len -= EXT_INIT_MAX_LEN;
 467                         extent->e_flags |= EXT2_EXTENT_FLAGS_UNINIT;
 468                 }
 469         } else {
 470                 extent->e_pblk = ext2fs_le32_to_cpu(ix->ei_leaf) +
 471                         ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
 472                 extent->e_lblk = ext2fs_le32_to_cpu(ix->ei_block);
 473                 if (path->left > 0) {
 474                         ix++;
 475                         end_blk = ext2fs_le32_to_cpu(ix->ei_block);
 476                 } else
 477                         end_blk = path->end_blk;
 478
 479                 extent->e_len = end_blk - extent->e_lblk;
 480         }
 481         if (path->visit_num)
 482                 extent->e_flags |= EXT2_EXTENT_FLAGS_SECOND_VISIT;
 483
 484         if (((orig_op == EXT2_EXTENT_NEXT_LEAF) ||
 485              (orig_op == EXT2_EXTENT_PREV_LEAF)) &&
 486             (handle->level != handle->max_depth))
 487                 goto retry;
 488
 489         if ((orig_op == EXT2_EXTENT_LAST_LEAF) &&
 490             ((handle->level != handle->max_depth) ||
 491              (path->left != 0)))
 492                 goto retry;
 493
 494         return 0;
 495 }
 496
 497 static errcode_t update_path(ext2_extent_handle_t handle)
 498 {
 499         blk64_t                         blk;
 500         errcode_t                       retval;
 501         struct ext3_extent_idx          *ix;
 502
 503         if (handle->level == 0) {
 504                 retval = ext2fs_write_inode_full(handle->fs, handle->ino,
 505                            handle->inode, EXT2_INODE_SIZE(handle->fs->super));
 506         } else {
 507                 ix = handle->path[handle->level - 1].curr;
 508                 blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
 509                         ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
 510
 511                 retval = io_channel_write_blk(handle->fs->io,
 512                                       blk, 1, handle->path[handle->level].buf);
 513         }
 514         return retval;
 515 }
 516
 517 #if 0
 518 errcode_t ext2fs_extent_save_path(ext2_extent_handle_t handle,
 519                                   ext2_extent_path_t *ret_path)
 520 {
 521         ext2_extent_path_t      save_path;
 522         struct ext2fs_extent    extent;
 523         struct ext2_extent_info info;
 524         errcode_t               retval;
 525
 526         retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
 527         if (retval)
 528                 return retval;
 529
 530         retval = ext2fs_extent_get_info(handle, &info);
 531         if (retval)
 532                 return retval;
 533
 534         retval = ext2fs_get_mem(sizeof(struct ext2_extent_path), &save_path);
 535         if (retval)
 536                 return retval;
 537         memset(save_path, 0, sizeof(struct ext2_extent_path));
 538
 539         save_path->magic = EXT2_ET_MAGIC_EXTENT_PATH;
 540         save_path->leaf_height = info.max_depth - info.curr_level - 1;
 541         save_path->lblk = extent.e_lblk;
 542
 543         *ret_path = save_path;
 544         return 0;
 545 }
 546
 547 errcode_t ext2fs_extent_free_path(ext2_extent_path_t path)
 548 {
 549         EXT2_CHECK_MAGIC(path, EXT2_ET_MAGIC_EXTENT_PATH);
 550
 551         ext2fs_free_mem(&path);
 552         return 0;
 553 }
 554 #endif
 555
 556 /*
 557  * Go to the node at leaf_level which contains logical block blk.
 558  *
 559  * leaf_level is height from the leaf node level, i.e.
 560  * leaf_level 0 is at leaf node, leaf_level 1 is 1 above etc.
 561  *
 562  * If "blk" has no mapping (hole) then handle is left at last
 563  * extent before blk.
 564  */
 565 static errcode_t extent_goto(ext2_extent_handle_t handle,
 566                              int leaf_level, blk64_t blk)
 567 {
 568         struct ext2fs_extent    extent;
 569         errcode_t               retval;
 570
 571         retval = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent);
 572         if (retval)
 573                 return retval;
 574
 575         if (leaf_level > handle->max_depth) {
 576                 dbg_printf("leaf level %d greater than tree depth %d\n",
 577                         leaf_level, handle->max_depth);
 578                 return EXT2_ET_OP_NOT_SUPPORTED;
 579         }
 580
 581         dbg_print_extent("root", &extent);
 582         while (1) {
 583                 if (handle->max_depth - handle->level == leaf_level) {
 584                         /* block is in this &extent */
 585                         if ((blk >= extent.e_lblk) &&
 586                             (blk < extent.e_lblk + extent.e_len))
 587                                 return 0;
 588                         if (blk < extent.e_lblk) {
 589                                 retval = ext2fs_extent_get(handle,
 590                                                            EXT2_EXTENT_PREV_SIB,
 591                                                            &extent);
 592                                 return EXT2_ET_EXTENT_NOT_FOUND;
 593                         }
 594                         retval = ext2fs_extent_get(handle,
 595                                                    EXT2_EXTENT_NEXT_SIB,
 596                                                    &extent);
 597                         if (retval == EXT2_ET_EXTENT_NO_NEXT)
 598                                 return EXT2_ET_EXTENT_NOT_FOUND;
 599                         if (retval)
 600                                 return retval;
 601                         continue;
 602                 }
 603
 604                 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_SIB,
 605                                            &extent);
 606                 if (retval == EXT2_ET_EXTENT_NO_NEXT)
 607                         goto go_down;
 608                 if (retval)
 609                         return retval;
 610
 611                 dbg_print_extent("next", &extent);
 612                 if (blk == extent.e_lblk)
 613                         goto go_down;
 614                 if (blk > extent.e_lblk)
 615                         continue;
 616
 617                 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_SIB,
 618                                            &extent);
 619                 if (retval)
 620                         return retval;
 621
 622                 dbg_print_extent("prev", &extent);
 623
 624         go_down:
 625                 retval = ext2fs_extent_get(handle, EXT2_EXTENT_DOWN,
 626                                            &extent);
 627                 if (retval)
 628                         return retval;
 629
 630                 dbg_print_extent("down", &extent);
 631         }
 632 }
 633
 634 errcode_t ext2fs_extent_goto(ext2_extent_handle_t handle,
 635                              blk64_t blk)
 636 {
 637         return extent_goto(handle, 0, blk);
 638 }
 639
 640 errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle,
 641                                 int flags EXT2FS_ATTR((unused)),
 642                                 struct ext2fs_extent *extent)
 643 {
 644         struct extent_path              *path;
 645         struct ext3_extent_idx          *ix;
 646         struct ext3_extent              *ex;
 647
 648         EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
 649
 650         if (!(handle->fs->flags & EXT2_FLAG_RW))
 651                 return EXT2_ET_RO_FILSYS;
 652
 653         if (!handle->path)
 654                 return EXT2_ET_NO_CURRENT_NODE;
 655
 656         path = handle->path + handle->level;
 657         if (!path->curr)
 658                 return EXT2_ET_NO_CURRENT_NODE;
 659
 660         if (handle->level == handle->max_depth) {
 661                 ex = path->curr;
 662
 663                 ex->ee_block = ext2fs_cpu_to_le32(extent->e_lblk);
 664                 ex->ee_start = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF);
 665                 ex->ee_start_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32);
 666                 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len);
 667         } else {
 668                 ix = path->curr;
 669
 670                 ix->ei_leaf = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF);
 671                 ix->ei_leaf_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32);
 672                 ix->ei_block = ext2fs_cpu_to_le32(extent->e_lblk);
 673                 ix->ei_unused = 0;
 674         }
 675         update_path(handle);
 676         return 0;
 677 }
 678
 679 errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
 680                                       struct ext2fs_extent *extent)
 681 {
 682         struct extent_path              *path;
 683         struct ext3_extent_idx          *ix;
 684         struct ext3_extent_header       *eh;
 685         errcode_t                       retval;
 686
 687         EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
 688
 689         if (!(handle->fs->flags & EXT2_FLAG_RW))
 690                 return EXT2_ET_RO_FILSYS;
 691
 692         if (!handle->path)
 693                 return EXT2_ET_NO_CURRENT_NODE;
 694
 695         path = handle->path + handle->level;
 696
 697         if (path->entries >= path->max_entries)
 698                 return EXT2_ET_CANT_INSERT_EXTENT;
 699
 700         eh = (struct ext3_extent_header *) path->buf;
 701         if (path->curr) {
 702                 ix = path->curr;
 703                 if (flags & EXT2_EXTENT_INSERT_AFTER) {
 704                         ix++;
 705                         path->left--;
 706                 }
 707         } else
 708                 ix = EXT_FIRST_INDEX(eh);
 709
 710         path->curr = ix;
 711
 712         if (path->left >= 0)
 713                 memmove(ix + 1, ix,
 714                         (path->left+1) * sizeof(struct ext3_extent_idx));
 715         path->left++;
 716         path->entries++;
 717
 718         eh = (struct ext3_extent_header *) path->buf;
 719         eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
 720
 721         retval = ext2fs_extent_replace(handle, 0, extent);
 722         if (retval)
 723                 goto errout;
 724
 725         retval = update_path(handle);
 726         if (retval)
 727                 goto errout;
 728
 729         return 0;
 730
 731 errout:
 732         ext2fs_extent_delete(handle, 0);
 733         return retval;
 734 }
 735
 736 errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle,
 737                                int flags EXT2FS_ATTR((unused)))
 738 {
 739         struct extent_path              *path;
 740         char                            *cp;
 741         struct ext3_extent_header       *eh;
 742         errcode_t                       retval;
 743
 744         EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
 745
 746         if (!(handle->fs->flags & EXT2_FLAG_RW))
 747                 return EXT2_ET_RO_FILSYS;
 748
 749         if (!handle->path)
 750                 return EXT2_ET_NO_CURRENT_NODE;
 751
 752         path = handle->path + handle->level;
 753         if (!path->curr)
 754                 return EXT2_ET_NO_CURRENT_NODE;
 755
 756         cp = path->curr;
 757
 758         if (path->left) {
 759                 memmove(cp, cp + sizeof(struct ext3_extent_idx),
 760                         path->left * sizeof(struct ext3_extent_idx));
 761                 path->left--;
 762         } else {
 763                 struct ext3_extent_idx  *ix = path->curr;
 764                 ix--;
 765                 path->curr = ix;
 766         }
 767         path->entries--;
 768         if (path->entries == 0)
 769                 path->curr = 0;
 770
 771         eh = (struct ext3_extent_header *) path->buf;
 772         eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
 773
 774         retval = update_path(handle);
 775
 776         return retval;
 777 }
 778
 779 errcode_t ext2fs_extent_get_info(ext2_extent_handle_t handle,
 780                                  struct ext2_extent_info *info)
 781 {
 782         struct extent_path              *path;
 783
 784         EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
 785
 786         memset(info, 0, sizeof(struct ext2_extent_info));
 787
 788         path = handle->path + handle->level;
 789         if (path) {
 790                 if (path->curr)
 791                         info->curr_entry = ((char *) path->curr - path->buf) /
 792                                 sizeof(struct ext3_extent_idx);
 793                 else
 794                         info->curr_entry = 0;
 795                 info->num_entries = path->entries;
 796                 info->max_entries = path->max_entries;
 797                 info->bytes_avail = (path->max_entries - path->entries) *
 798                         sizeof(struct ext3_extent);
 799         }
 800
 801         info->curr_level = handle->level;
 802         info->max_depth = handle->max_depth;
 803         info->max_lblk = ((__u64) 1 << 32) - 1;
 804         info->max_pblk = ((__u64) 1 << 48) - 1;
 805         info->max_len = (1UL << 15);
 806         info->max_uninit_len = (1UL << 15) - 1;
 807
 808         return 0;
 809 }
 810
 811 #ifdef DEBUG
 812
 813 #include "debugfs.h"
 814
 815 /*
 816  * Hook in new commands into debugfs
 817  */
 818 const char *debug_prog_name = "tst_extents";
 819 extern ss_request_table extent_cmds;
 820 ss_request_table *extra_cmds = &extent_cmds;
 821
 822 ext2_ino_t      current_ino = 0;
 823 ext2_extent_handle_t current_handle;
 824
 825 void do_inode(int argc, char *argv[])
 826 {
 827         ext2_ino_t      inode;
 828         int             i;
 829         struct ext3_extent_header *eh;
 830         errcode_t retval;
 831
 832         if (check_fs_open(argv[0]))
 833                 return;
 834
 835         if (argc == 1) {
 836                 if (current_ino)
 837                         printf("Current inode is %d\n", current_ino);
 838                 else
 839                         printf("No current inode\n");
 840                 return;
 841         }
 842
 843         if (common_inode_args_process(argc, argv, &inode, 0)) {
 844                 return;
 845         }
 846
 847         current_ino = 0;
 848
 849         retval = ext2fs_extent_open(current_fs, inode, &current_handle);
 850         if (retval) {
 851                 com_err(argv[1], retval, "while opening extent handle");
 852                 return;
 853         }
 854
 855         current_ino = inode;
 856
 857         printf("Loaded inode %d\n", current_ino);
 858
 859         return;
 860 }
 861
 862 void generic_goto_node(char *cmd_name, int op)
 863 {
 864         struct ext2fs_extent    extent;
 865         errcode_t               retval;
 866
 867         if (check_fs_open(cmd_name))
 868                 return;
 869
 870         if (!current_handle) {
 871                 com_err(cmd_name, 0, "Extent handle not open");
 872                 return;
 873         }
 874
 875         retval = ext2fs_extent_get(current_handle, op, &extent);
 876         if (retval) {
 877                 com_err(cmd_name, retval, 0);
 878                 return;
 879         }
 880         dbg_print_extent(0, &extent);
 881 }
 882
 883 void do_current_node(int argc, char *argv[])
 884 {
 885         generic_goto_node(argv[0], EXT2_EXTENT_CURRENT);
 886 }
 887
 888 void do_root_node(int argc, char *argv[])
 889 {
 890         generic_goto_node(argv[0], EXT2_EXTENT_ROOT);
 891 }
 892
 893 void do_last_leaf(int argc, char *argv[])
 894 {
 895         generic_goto_node(argv[0], EXT2_EXTENT_LAST_LEAF);
 896 }
 897
 898 void do_first_sib(int argc, char *argv[])
 899 {
 900         generic_goto_node(argv[0], EXT2_EXTENT_FIRST_SIB);
 901 }
 902
 903 void do_last_sib(int argc, char *argv[])
 904 {
 905         generic_goto_node(argv[0], EXT2_EXTENT_LAST_SIB);
 906 }
 907
 908 void do_next_sib(int argc, char *argv[])
 909 {
 910         generic_goto_node(argv[0], EXT2_EXTENT_NEXT_SIB);
 911 }
 912
 913 void do_prev_sib(int argc, char *argv[])
 914 {
 915         generic_goto_node(argv[0], EXT2_EXTENT_PREV_SIB);
 916 }
 917
 918 void do_next_leaf(int argc, char *argv[])
 919 {
 920         generic_goto_node(argv[0], EXT2_EXTENT_NEXT_LEAF);
 921 }
 922
 923 void do_prev_leaf(int argc, char *argv[])
 924 {
 925         generic_goto_node(argv[0], EXT2_EXTENT_PREV_LEAF);
 926 }
 927
 928 void do_next(int argc, char *argv[])
 929 {
 930         generic_goto_node(argv[0], EXT2_EXTENT_NEXT);
 931 }
 932
 933 void do_prev(int argc, char *argv[])
 934 {
 935         generic_goto_node(argv[0], EXT2_EXTENT_PREV);
 936 }
 937
 938 void do_up(int argc, char *argv[])
 939 {
 940         generic_goto_node(argv[0], EXT2_EXTENT_UP);
 941 }
 942
 943 void do_down(int argc, char *argv[])
 944 {
 945         generic_goto_node(argv[0], EXT2_EXTENT_DOWN);
 946 }
 947
 948 void do_delete_node(int argc, char *argv[])
 949 {
 950         errcode_t       retval;
 951         int             err;
 952
 953         if (check_fs_read_write(argv[0]))
 954                 return;
 955
 956         retval = ext2fs_extent_delete(current_handle, 0);
 957         if (retval) {
 958                 com_err(argv[0], retval, 0);
 959                 return;
 960         }
 961         do_current_node(argc, argv);
 962 }
 963
 964 void do_replace_node(int argc, char *argv[])
 965 {
 966         errcode_t       retval;
 967         struct ext2fs_extent extent;
 968         int err;
 969
 970         if (check_fs_read_write(argv[0]))
 971                 return;
 972
 973         if (argc != 4) {
 974                 fprintf(stderr, "usage: %s <lblk> <len> <pblk>\n", argv[0]);
 975                 return;
 976         }
 977
 978         extent.e_lblk = parse_ulong(argv[1], argv[0],
 979                                     "logical block", &err);
 980         if (err)
 981                 return;
 982
 983         extent.e_len = parse_ulong(argv[2], argv[0],
 984                                     "logical block", &err);
 985         if (err)
 986                 return;
 987
 988         extent.e_pblk = parse_ulong(argv[3], argv[0],
 989                                     "logical block", &err);
 990         if (err)
 991                 return;
 992
 993         retval = ext2fs_extent_replace(current_handle, 0, &extent);
 994         if (retval) {
 995                 com_err(argv[0], retval, 0);
 996                 return;
 997         }
 998         do_current_node(argc, argv);
 999 }
1000
1001 void do_insert_node(int argc, char *argv[])
1002 {
1003         errcode_t       retval;
1004         struct ext2fs_extent extent;
1005         char *cmd;
1006         int err;
1007         int flags = 0;
1008
1009         if (check_fs_read_write(argv[0]))
1010                 return;
1011
1012         cmd = argv[0];
1013
1014         if (argc > 2 && !strcmp(argv[1], "--after")) {
1015                 argc--;
1016                 argv++;
1017                 flags |= EXT2_EXTENT_INSERT_AFTER;
1018         }
1019
1020         if (argc != 4) {
1021                 fprintf(stderr, "usage: %s <lblk> <len> <pblk>\n", cmd);
1022                 return;
1023         }
1024
1025         extent.e_lblk = parse_ulong(argv[1], cmd,
1026                                     "logical block", &err);
1027         if (err)
1028                 return;
1029
1030         extent.e_len = parse_ulong(argv[2], cmd,
1031                                     "length", &err);
1032         if (err)
1033                 return;
1034
1035         extent.e_pblk = parse_ulong(argv[3], cmd,
1036                                     "pysical block", &err);
1037         if (err)
1038                 return;
1039
1040         retval = ext2fs_extent_insert(current_handle, flags, &extent);
1041         if (retval) {
1042                 com_err(cmd, retval, 0);
1043                 return;
1044         }
1045         do_current_node(argc, argv);
1046 }
1047
1048 void do_print_all(int argc, char **argv)
1049 {
1050         struct ext2fs_extent    extent;
1051         errcode_t               retval;
1052         errcode_t               end_err = EXT2_ET_EXTENT_NO_NEXT;
1053         int                     op = EXT2_EXTENT_NEXT;
1054         int                     first_op = EXT2_EXTENT_ROOT;
1055
1056
1057         if (check_fs_open(argv[0]))
1058                 return;
1059
1060         if (!current_handle) {
1061                 com_err(argv[0], 0, "Extent handle not open");
1062                 return;
1063         }
1064
1065         if (argc > 2) {
1066         print_usage:
1067                 fprintf(stderr,
1068                         "Usage: %s [--leaf-only|--reverse|--reverse-leaf]\n",
1069                         argv[0]);
1070                 return;
1071         }
1072
1073         if (argc == 2) {
1074                 if (!strcmp(argv[1], "--leaf-only"))
1075                         op = EXT2_EXTENT_NEXT_LEAF;
1076                 else if (!strcmp(argv[1], "--reverse")) {
1077                         op = EXT2_EXTENT_PREV;
1078                         first_op = EXT2_EXTENT_LAST_LEAF;
1079                         end_err = EXT2_ET_EXTENT_NO_PREV;
1080                 } else if (!strcmp(argv[1], "--reverse-leaf")) {
1081                         op = EXT2_EXTENT_PREV_LEAF;
1082                         first_op = EXT2_EXTENT_LAST_LEAF;
1083                         end_err = EXT2_ET_EXTENT_NO_PREV;
1084                 } else
1085                           goto print_usage;
1086         }
1087
1088         retval = ext2fs_extent_get(current_handle, first_op, &extent);
1089         if (retval) {
1090                 com_err(argv[0], retval, 0);
1091                 return;
1092         }
1093         dbg_print_extent(0, &extent);
1094
1095         while (1) {
1096                 retval = ext2fs_extent_get(current_handle, op, &extent);
1097                 if (retval == end_err)
1098                         break;
1099
1100                 if (retval) {
1101                         com_err(argv[0], retval, 0);
1102                         return;
1103                 }
1104                 dbg_print_extent(0, &extent);
1105         }
1106 }
1107
1108 void do_info(int argc, char **argv)
1109 {
1110         struct ext2fs_extent    extent;
1111         struct ext2_extent_info info;
1112         errcode_t               retval;
1113
1114         if (check_fs_open(argv[0]))
1115                 return;
1116
1117         if (!current_handle) {
1118                 com_err(argv[0], 0, "Extent handle not open");
1119                 return;
1120         }
1121
1122         retval = ext2fs_extent_get_info(current_handle, &info);
1123         if (retval) {
1124                 com_err(argv[0], retval, 0);
1125                 return;
1126         }
1127
1128         retval = ext2fs_extent_get(current_handle,
1129                                    EXT2_EXTENT_CURRENT, &extent);
1130         if (retval) {
1131                 com_err(argv[0], retval, 0);
1132                 return;
1133         }
1134
1135         dbg_print_extent(0, &extent);
1136
1137         printf("Current handle location: %d/%d (max: %d, bytes %d), level %d/%d\n",
1138                info.curr_entry, info.num_entries, info.max_entries,
1139                info.bytes_avail, info.curr_level, info.max_depth);
1140         printf("\tmax lblk: %llu, max pblk: %llu\n", info.max_lblk,
1141                info.max_pblk);
1142         printf("\tmax_len: %u, max_uninit_len: %u\n", info.max_len,
1143                info.max_uninit_len);
1144 }
1145
1146 void do_goto_block(int argc, char **argv)
1147 {
1148         struct ext2fs_extent    extent;
1149         errcode_t               retval;
1150         int                     op = EXT2_EXTENT_NEXT_LEAF;
1151         blk_t                   blk;
1152         int                     level = 0;
1153
1154         if (check_fs_open(argv[0]))
1155                 return;
1156
1157         if (!current_handle) {
1158                 com_err(argv[0], 0, "Extent handle not open");
1159                 return;
1160         }
1161
1162         if (argc < 2 || argc > 3) {
1163                 fprintf(stderr, "%s block [level]\n", argv[0]);
1164                 return;
1165         }
1166
1167         if (strtoblk(argv[0], argv[1], &blk))
1168                 return;
1169
1170         if (argc == 3)
1171                 if (strtoblk(argv[0], argv[2], &level))
1172                         return;
1173
1174         retval = extent_goto(current_handle, level, (blk64_t) blk);
1175
1176         if (retval) {
1177                 com_err(argv[0], retval, "while trying to go to block %lu, level %d",
1178                         blk, level);
1179                 return;
1180         }
1181
1182         generic_goto_node(argv[0], EXT2_EXTENT_CURRENT);
1183 }
1184 #endif
1185