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