sys/fs/ext2fs/ext2_extents.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2010 Zheng Liu <lz@freebsd.org>
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  26  * SUCH DAMAGE.
  27  *
  28  * $FreeBSD$
  29  */
  30
  31 #include <sys/param.h>
  32 #include <sys/systm.h>
  33 #include <sys/types.h>
  34 #include <sys/kernel.h>
  35 #include <sys/malloc.h>
  36 #include <sys/vnode.h>
  37 #include <sys/bio.h>
  38 #include <sys/buf.h>
  39 #include <sys/conf.h>
  40 #include <sys/stat.h>
  41
  42 #include <fs/ext2fs/ext2_mount.h>
  43 #include <fs/ext2fs/fs.h>
  44 #include <fs/ext2fs/inode.h>
  45 #include <fs/ext2fs/ext2fs.h>
  46 #include <fs/ext2fs/ext2_extents.h>
  47 #include <fs/ext2fs/ext2_extern.h>
  48
  49 static MALLOC_DEFINE(M_EXT2EXTENTS, "ext2_extents", "EXT2 extents");
  50
  51 #ifdef EXT2FS_DEBUG
  52 static void
  53 ext4_ext_print_extent(struct ext4_extent *ep)
  54 {
  55
  56         printf("    ext %p => (blk %u len %u start %ju)\n",
  57             ep, ep->e_blk, ep->e_len,
  58             (uint64_t)ep->e_start_hi << 32 | ep->e_start_lo);
  59 }
  60
  61 static void ext4_ext_print_header(struct inode *ip, struct ext4_extent_header *ehp);
  62
  63 static void
  64 ext4_ext_print_index(struct inode *ip, struct ext4_extent_index *ex, int do_walk)
  65 {
  66         struct m_ext2fs *fs;
  67         struct buf *bp;
  68         int error;
  69
  70         fs = ip->i_e2fs;
  71
  72         printf("    index %p => (blk %u pblk %ju)\n",
  73             ex, ex->ei_blk, (uint64_t)ex->ei_leaf_hi << 32 | ex->ei_leaf_lo);
  74
  75         if(!do_walk)
  76                 return;
  77
  78         if ((error = bread(ip->i_devvp,
  79             fsbtodb(fs, ((uint64_t)ex->ei_leaf_hi << 32 | ex->ei_leaf_lo)),
  80             (int)fs->e2fs_bsize, NOCRED, &bp)) != 0) {
  81                 brelse(bp);
  82                 return;
  83         }
  84
  85         ext4_ext_print_header(ip, (struct ext4_extent_header *)bp->b_data);
  86
  87         brelse(bp);
  88
  89 }
  90
  91 static void
  92 ext4_ext_print_header(struct inode *ip, struct ext4_extent_header *ehp)
  93 {
  94         int i;
  95
  96         printf("header %p => (magic 0x%x entries %d max %d depth %d gen %d)\n",
  97             ehp, ehp->eh_magic, ehp->eh_ecount, ehp->eh_max, ehp->eh_depth,
  98             ehp->eh_gen);
  99
 100         for (i = 0; i < ehp->eh_ecount; i++)
 101                 if (ehp->eh_depth != 0)
 102                         ext4_ext_print_index(ip,
 103                             (struct ext4_extent_index *)(ehp + 1 + i), 1);
 104                 else
 105                         ext4_ext_print_extent((struct ext4_extent *)(ehp + 1 + i));
 106 }
 107
 108 static void
 109 ext4_ext_print_path(struct inode *ip, struct ext4_extent_path *path)
 110 {
 111         int k, l;
 112
 113         l = path->ep_depth;
 114
 115         printf("ip=%ju, Path:\n", ip->i_number);
 116         for (k = 0; k <= l; k++, path++) {
 117                 if (path->ep_index) {
 118                         ext4_ext_print_index(ip, path->ep_index, 0);
 119                 } else if (path->ep_ext) {
 120                         ext4_ext_print_extent(path->ep_ext);
 121                 }
 122         }
 123 }
 124
 125 void
 126 ext4_ext_print_extent_tree_status(struct inode *ip)
 127 {
 128         struct ext4_extent_header *ehp;
 129
 130         ehp = (struct ext4_extent_header *)(char *)ip->i_db;
 131
 132         printf("Extent status:ip=%ju\n", ip->i_number);
 133         if (!(ip->i_flag & IN_E4EXTENTS))
 134                 return;
 135
 136         ext4_ext_print_header(ip, ehp);
 137
 138         return;
 139 }
 140 #endif
 141
 142 static inline struct ext4_extent_header *
 143 ext4_ext_inode_header(struct inode *ip)
 144 {
 145
 146         return ((struct ext4_extent_header *)ip->i_db);
 147 }
 148
 149 static inline struct ext4_extent_header *
 150 ext4_ext_block_header(char *bdata)
 151 {
 152
 153         return ((struct ext4_extent_header *)bdata);
 154 }
 155
 156 static inline unsigned short
 157 ext4_ext_inode_depth(struct inode *ip)
 158 {
 159         struct ext4_extent_header *ehp;
 160
 161         ehp = (struct ext4_extent_header *)ip->i_data;
 162         return (ehp->eh_depth);
 163 }
 164
 165 static inline e4fs_daddr_t
 166 ext4_ext_index_pblock(struct ext4_extent_index *index)
 167 {
 168         e4fs_daddr_t blk;
 169
 170         blk = index->ei_leaf_lo;
 171         blk |= (e4fs_daddr_t)index->ei_leaf_hi << 32;
 172
 173         return (blk);
 174 }
 175
 176 static inline void
 177 ext4_index_store_pblock(struct ext4_extent_index *index, e4fs_daddr_t pb)
 178 {
 179
 180         index->ei_leaf_lo = pb & 0xffffffff;
 181         index->ei_leaf_hi = (pb >> 32) & 0xffff;
 182 }
 183
 184
 185 static inline e4fs_daddr_t
 186 ext4_ext_extent_pblock(struct ext4_extent *extent)
 187 {
 188         e4fs_daddr_t blk;
 189
 190         blk = extent->e_start_lo;
 191         blk |= (e4fs_daddr_t)extent->e_start_hi << 32;
 192
 193         return (blk);
 194 }
 195
 196 static inline void
 197 ext4_ext_store_pblock(struct ext4_extent *ex, e4fs_daddr_t pb)
 198 {
 199
 200         ex->e_start_lo = pb & 0xffffffff;
 201         ex->e_start_hi = (pb >> 32) & 0xffff;
 202 }
 203
 204 int
 205 ext4_ext_in_cache(struct inode *ip, daddr_t lbn, struct ext4_extent *ep)
 206 {
 207         struct ext4_extent_cache *ecp;
 208         int ret = EXT4_EXT_CACHE_NO;
 209
 210         ecp = &ip->i_ext_cache;
 211         if (ecp->ec_type == EXT4_EXT_CACHE_NO)
 212                 return (ret);
 213
 214         if (lbn >= ecp->ec_blk && lbn < ecp->ec_blk + ecp->ec_len) {
 215                 ep->e_blk = ecp->ec_blk;
 216                 ep->e_start_lo = ecp->ec_start & 0xffffffff;
 217                 ep->e_start_hi = ecp->ec_start >> 32 & 0xffff;
 218                 ep->e_len = ecp->ec_len;
 219                 ret = ecp->ec_type;
 220         }
 221         return (ret);
 222 }
 223
 224 static int
 225 ext4_ext_check_header(struct inode *ip, struct ext4_extent_header *eh)
 226 {
 227         struct m_ext2fs *fs;
 228         char *error_msg;
 229
 230         fs = ip->i_e2fs;
 231
 232         if (eh->eh_magic != EXT4_EXT_MAGIC) {
 233                 error_msg = "invalid magic";
 234                 goto corrupted;
 235         }
 236         if (eh->eh_max == 0) {
 237                 error_msg = "invalid eh_max";
 238                 goto corrupted;
 239         }
 240         if (eh->eh_ecount > eh->eh_max) {
 241                 error_msg = "invalid eh_entries";
 242                 goto corrupted;
 243         }
 244
 245         return (0);
 246
 247 corrupted:
 248         ext2_fserr(fs, ip->i_uid, error_msg);
 249         return (EIO);
 250 }
 251
 252 static void
 253 ext4_ext_binsearch_index(struct ext4_extent_path *path, int blk)
 254 {
 255         struct ext4_extent_header *eh;
 256         struct ext4_extent_index *r, *l, *m;
 257
 258         eh = path->ep_header;
 259
 260         KASSERT(eh->eh_ecount <= eh->eh_max && eh->eh_ecount > 0,
 261             ("ext4_ext_binsearch_index: bad args"));
 262
 263         l = EXT_FIRST_INDEX(eh) + 1;
 264         r = EXT_FIRST_INDEX(eh) + eh->eh_ecount - 1;
 265         while (l <= r) {
 266                 m = l + (r - l) / 2;
 267                 if (blk < m->ei_blk)
 268                         r = m - 1;
 269                 else
 270                         l = m + 1;
 271         }
 272
 273         path->ep_index = l - 1;
 274 }
 275
 276 static void
 277 ext4_ext_binsearch_ext(struct ext4_extent_path *path, int blk)
 278 {
 279         struct ext4_extent_header *eh;
 280         struct ext4_extent *r, *l, *m;
 281
 282         eh = path->ep_header;
 283
 284         KASSERT(eh->eh_ecount <= eh->eh_max,
 285             ("ext4_ext_binsearch_ext: bad args"));
 286
 287         if (eh->eh_ecount == 0)
 288                 return;
 289
 290         l = EXT_FIRST_EXTENT(eh) + 1;
 291         r = EXT_FIRST_EXTENT(eh) + eh->eh_ecount - 1;
 292
 293         while (l <= r) {
 294                 m = l + (r - l) / 2;
 295                 if (blk < m->e_blk)
 296                         r = m - 1;
 297                 else
 298                         l = m + 1;
 299         }
 300
 301         path->ep_ext = l - 1;
 302 }
 303
 304 static int
 305 ext4_ext_fill_path_bdata(struct ext4_extent_path *path,
 306     struct buf *bp, uint64_t blk)
 307 {
 308
 309         KASSERT(path->ep_data == NULL,
 310             ("ext4_ext_fill_path_bdata: bad ep_data"));
 311
 312         path->ep_data = malloc(bp->b_bufsize, M_EXT2EXTENTS, M_WAITOK);
 313         if (!path->ep_data)
 314                 return (ENOMEM);
 315
 316         memcpy(path->ep_data, bp->b_data, bp->b_bufsize);
 317         path->ep_blk = blk;
 318
 319         return (0);
 320 }
 321
 322 static void
 323 ext4_ext_fill_path_buf(struct ext4_extent_path *path, struct buf *bp)
 324 {
 325
 326         KASSERT(path->ep_data != NULL,
 327             ("ext4_ext_fill_path_buf: bad ep_data"));
 328
 329         memcpy(bp->b_data, path->ep_data, bp->b_bufsize);
 330 }
 331
 332 static void
 333 ext4_ext_drop_refs(struct ext4_extent_path *path)
 334 {
 335         int depth, i;
 336
 337         if (!path)
 338                 return;
 339
 340         depth = path->ep_depth;
 341         for (i = 0; i <= depth; i++, path++)
 342                 if (path->ep_data) {
 343                         free(path->ep_data, M_EXT2EXTENTS);
 344                         path->ep_data = NULL;
 345                 }
 346 }
 347
 348 void
 349 ext4_ext_path_free(struct ext4_extent_path *path)
 350 {
 351
 352         if (!path)
 353                 return;
 354
 355         ext4_ext_drop_refs(path);
 356         free(path, M_EXT2EXTENTS);
 357 }
 358
 359 int
 360 ext4_ext_find_extent(struct inode *ip, daddr_t block,
 361     struct ext4_extent_path **ppath)
 362 {
 363         struct m_ext2fs *fs;
 364         struct ext4_extent_header *eh;
 365         struct ext4_extent_path *path;
 366         struct buf *bp;
 367         uint64_t blk;
 368         int error, depth, i, ppos, alloc;
 369
 370         fs = ip->i_e2fs;
 371         eh = ext4_ext_inode_header(ip);
 372         depth = ext4_ext_inode_depth(ip);
 373         ppos = 0;
 374         alloc = 0;
 375
 376         error = ext4_ext_check_header(ip, eh);
 377         if (error)
 378                 return (error);
 379
 380         if (ppath == NULL)
 381                 return (EINVAL);
 382
 383         path = *ppath;
 384         if (path == NULL) {
 385                 path = malloc(EXT4_EXT_DEPTH_MAX *
 386                     sizeof(struct ext4_extent_path),
 387                     M_EXT2EXTENTS, M_WAITOK | M_ZERO);
 388                 if (!path)
 389                         return (ENOMEM);
 390
 391                 *ppath = path;
 392                 alloc = 1;
 393         }
 394
 395         path[0].ep_header = eh;
 396         path[0].ep_data = NULL;
 397
 398         /* Walk through the tree. */
 399         i = depth;
 400         while (i) {
 401                 ext4_ext_binsearch_index(&path[ppos], block);
 402                 blk = ext4_ext_index_pblock(path[ppos].ep_index);
 403                 path[ppos].ep_depth = i;
 404                 path[ppos].ep_ext = NULL;
 405
 406                 error = bread(ip->i_devvp, fsbtodb(ip->i_e2fs, blk),
 407                     ip->i_e2fs->e2fs_bsize, NOCRED, &bp);
 408                 if (error) {
 409                         brelse(bp);
 410                         goto error;
 411                 }
 412
 413                 ppos++;
 414                 if (ppos > depth) {
 415                         ext2_fserr(fs, ip->i_uid,
 416                             "ppos > depth => extent corrupted");
 417                         error = EIO;
 418                         brelse(bp);
 419                         goto error;
 420                 }
 421
 422                 ext4_ext_fill_path_bdata(&path[ppos], bp, blk);
 423                 bqrelse(bp);
 424
 425                 eh = ext4_ext_block_header(path[ppos].ep_data);
 426                 if (ext4_ext_check_header(ip, eh) ||
 427                     ext2_extent_blk_csum_verify(ip, path[ppos].ep_data)) {
 428                         error = EIO;
 429                         goto error;
 430                 }
 431
 432                 path[ppos].ep_header = eh;
 433
 434                 i--;
 435         }
 436
 437         error = ext4_ext_check_header(ip, eh);
 438         if (error)
 439                 goto error;
 440
 441         /* Find extent. */
 442         path[ppos].ep_depth = i;
 443         path[ppos].ep_header = eh;
 444         path[ppos].ep_ext = NULL;
 445         path[ppos].ep_index = NULL;
 446         ext4_ext_binsearch_ext(&path[ppos], block);
 447         return (0);
 448
 449 error:
 450         ext4_ext_drop_refs(path);
 451         if (alloc)
 452                 free(path, M_EXT2EXTENTS);
 453
 454         *ppath = NULL;
 455
 456         return (error);
 457 }
 458
 459 static inline int
 460 ext4_ext_space_root(struct inode *ip)
 461 {
 462         int size;
 463
 464         size = sizeof(ip->i_data);
 465         size -= sizeof(struct ext4_extent_header);
 466         size /= sizeof(struct ext4_extent);
 467
 468         return (size);
 469 }
 470
 471 static inline int
 472 ext4_ext_space_block(struct inode *ip)
 473 {
 474         struct m_ext2fs *fs;
 475         int size;
 476
 477         fs = ip->i_e2fs;
 478
 479         size = (fs->e2fs_bsize - sizeof(struct ext4_extent_header)) /
 480             sizeof(struct ext4_extent);
 481
 482         return (size);
 483 }
 484
 485 static inline int
 486 ext4_ext_space_block_index(struct inode *ip)
 487 {
 488         struct m_ext2fs *fs;
 489         int size;
 490
 491         fs = ip->i_e2fs;
 492
 493         size = (fs->e2fs_bsize - sizeof(struct ext4_extent_header)) /
 494             sizeof(struct ext4_extent_index);
 495
 496         return (size);
 497 }
 498
 499 void
 500 ext4_ext_tree_init(struct inode *ip)
 501 {
 502         struct ext4_extent_header *ehp;
 503
 504         ip->i_flag |= IN_E4EXTENTS;
 505
 506         memset(ip->i_data, 0, EXT2_NDADDR + EXT2_NIADDR);
 507         ehp = (struct ext4_extent_header *)ip->i_data;
 508         ehp->eh_magic = EXT4_EXT_MAGIC;
 509         ehp->eh_max = ext4_ext_space_root(ip);
 510         ip->i_ext_cache.ec_type = EXT4_EXT_CACHE_NO;
 511         ip->i_flag |= IN_CHANGE | IN_UPDATE;
 512         ext2_update(ip->i_vnode, 1);
 513 }
 514
 515 static inline void
 516 ext4_ext_put_in_cache(struct inode *ip, uint32_t blk,
 517                         uint32_t len, uint32_t start, int type)
 518 {
 519
 520         KASSERT(len != 0, ("ext4_ext_put_in_cache: bad input"));
 521
 522         ip->i_ext_cache.ec_type = type;
 523         ip->i_ext_cache.ec_blk = blk;
 524         ip->i_ext_cache.ec_len = len;
 525         ip->i_ext_cache.ec_start = start;
 526 }
 527
 528 static e4fs_daddr_t
 529 ext4_ext_blkpref(struct inode *ip, struct ext4_extent_path *path,
 530     e4fs_daddr_t block)
 531 {
 532         struct m_ext2fs *fs;
 533         struct ext4_extent *ex;
 534         e4fs_daddr_t bg_start;
 535         int depth;
 536
 537         fs = ip->i_e2fs;
 538
 539         if (path) {
 540                 depth = path->ep_depth;
 541                 ex = path[depth].ep_ext;
 542                 if (ex) {
 543                         e4fs_daddr_t pblk = ext4_ext_extent_pblock(ex);
 544                         e2fs_daddr_t blk = ex->e_blk;
 545
 546                         if (block > blk)
 547                                 return (pblk + (block - blk));
 548                         else
 549                                 return (pblk - (blk - block));
 550                 }
 551
 552                 /* Try to get block from index itself. */
 553                 if (path[depth].ep_data)
 554                         return (path[depth].ep_blk);
 555         }
 556
 557         /* Use inode's group. */
 558         bg_start = (ip->i_block_group * EXT2_BLOCKS_PER_GROUP(ip->i_e2fs)) +
 559             fs->e2fs->e2fs_first_dblock;
 560
 561         return (bg_start + block);
 562 }
 563
 564 static int inline
 565 ext4_can_extents_be_merged(struct ext4_extent *ex1,
 566     struct ext4_extent *ex2)
 567 {
 568
 569         if (ex1->e_blk + ex1->e_len != ex2->e_blk)
 570                 return (0);
 571
 572         if (ex1->e_len + ex2->e_len > EXT4_MAX_LEN)
 573                 return (0);
 574
 575         if (ext4_ext_extent_pblock(ex1) + ex1->e_len ==
 576             ext4_ext_extent_pblock(ex2))
 577                 return (1);
 578
 579         return (0);
 580 }
 581
 582 static unsigned
 583 ext4_ext_next_leaf_block(struct inode *ip, struct ext4_extent_path *path)
 584 {
 585         int depth = path->ep_depth;
 586
 587         /* Empty tree */
 588         if (depth == 0)
 589                 return (EXT4_MAX_BLOCKS);
 590
 591         /* Go to indexes. */
 592         depth--;
 593
 594         while (depth >= 0) {
 595                 if (path[depth].ep_index !=
 596                     EXT_LAST_INDEX(path[depth].ep_header))
 597                         return (path[depth].ep_index[1].ei_blk);
 598
 599                 depth--;
 600         }
 601
 602         return (EXT4_MAX_BLOCKS);
 603 }
 604
 605 static int
 606 ext4_ext_dirty(struct inode *ip, struct ext4_extent_path *path)
 607 {
 608         struct m_ext2fs *fs;
 609         struct buf *bp;
 610         uint64_t blk;
 611         int error;
 612
 613         fs = ip->i_e2fs;
 614
 615         if (!path)
 616                 return (EINVAL);
 617
 618         if (path->ep_data) {
 619                 blk = path->ep_blk;
 620                 bp = getblk(ip->i_devvp, fsbtodb(fs, blk),
 621                     fs->e2fs_bsize, 0, 0, 0);
 622                 if (!bp)
 623                         return (EIO);
 624                 ext4_ext_fill_path_buf(path, bp);
 625                 ext2_extent_blk_csum_set(ip, bp->b_data);
 626                 error = bwrite(bp);
 627         } else {
 628                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
 629                 error = ext2_update(ip->i_vnode, 1);
 630         }
 631
 632         return (error);
 633 }
 634
 635 static int
 636 ext4_ext_insert_index(struct inode *ip, struct ext4_extent_path *path,
 637     uint32_t lblk, e4fs_daddr_t blk)
 638 {
 639         struct m_ext2fs *fs;
 640         struct ext4_extent_index *idx;
 641         int len;
 642
 643         fs = ip->i_e2fs;
 644
 645         if (lblk == path->ep_index->ei_blk) {
 646                 ext2_fserr(fs, ip->i_uid,
 647                     "lblk == index blk => extent corrupted");
 648                 return (EIO);
 649         }
 650
 651         if (path->ep_header->eh_ecount >= path->ep_header->eh_max) {
 652                 ext2_fserr(fs, ip->i_uid,
 653                     "ecout > maxcount => extent corrupted");
 654                 return (EIO);
 655         }
 656
 657         if (lblk > path->ep_index->ei_blk) {
 658                 /* Insert after. */
 659                 idx = path->ep_index + 1;
 660         } else {
 661                 /* Insert before. */
 662                 idx = path->ep_index;
 663         }
 664
 665         len = EXT_LAST_INDEX(path->ep_header) - idx + 1;
 666         if (len > 0)
 667                 memmove(idx + 1, idx, len * sizeof(struct ext4_extent_index));
 668
 669         if (idx > EXT_MAX_INDEX(path->ep_header)) {
 670                 ext2_fserr(fs, ip->i_uid,
 671                     "index is out of range => extent corrupted");
 672                 return (EIO);
 673         }
 674
 675         idx->ei_blk = lblk;
 676         ext4_index_store_pblock(idx, blk);
 677         path->ep_header->eh_ecount++;
 678
 679         return (ext4_ext_dirty(ip, path));
 680 }
 681
 682 static e4fs_daddr_t
 683 ext4_ext_alloc_meta(struct inode *ip)
 684 {
 685         e4fs_daddr_t blk = ext2_alloc_meta(ip);
 686         if (blk) {
 687                 ip->i_blocks += btodb(ip->i_e2fs->e2fs_bsize);
 688                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
 689                 ext2_update(ip->i_vnode, 1);
 690         }
 691
 692         return (blk);
 693 }
 694
 695 static void
 696 ext4_ext_blkfree(struct inode *ip, uint64_t blk, int count, int flags)
 697 {
 698         struct m_ext2fs *fs;
 699         int i, blocksreleased;
 700
 701         fs = ip->i_e2fs;
 702         blocksreleased = count;
 703
 704         for(i = 0; i < count; i++)
 705                 ext2_blkfree(ip, blk + i, fs->e2fs_bsize);
 706
 707         if (ip->i_blocks >= blocksreleased)
 708                 ip->i_blocks -= (btodb(fs->e2fs_bsize)*blocksreleased);
 709         else
 710                 ip->i_blocks = 0;
 711
 712         ip->i_flag |= IN_CHANGE | IN_UPDATE;
 713         ext2_update(ip->i_vnode, 1);
 714 }
 715
 716 static int
 717 ext4_ext_split(struct inode *ip, struct ext4_extent_path *path,
 718     struct ext4_extent *newext, int at)
 719 {
 720         struct m_ext2fs *fs;
 721         struct  buf *bp;
 722         int depth = ext4_ext_inode_depth(ip);
 723         struct ext4_extent_header *neh;
 724         struct ext4_extent_index *fidx;
 725         struct ext4_extent *ex;
 726         int i = at, k, m, a;
 727         e4fs_daddr_t newblk, oldblk;
 728         uint32_t border;
 729         e4fs_daddr_t *ablks = NULL;
 730         int error = 0;
 731
 732         fs = ip->i_e2fs;
 733         bp = NULL;
 734
 735         /*
 736          * We will split at current extent for now.
 737          */
 738         if (path[depth].ep_ext > EXT_MAX_EXTENT(path[depth].ep_header)) {
 739                 ext2_fserr(fs, ip->i_uid,
 740                     "extent is out of range => extent corrupted");
 741                 return (EIO);
 742         }
 743
 744         if (path[depth].ep_ext != EXT_MAX_EXTENT(path[depth].ep_header))
 745                 border = path[depth].ep_ext[1].e_blk;
 746         else
 747                 border = newext->e_blk;
 748
 749         /* Allocate new blocks. */
 750         ablks = malloc(sizeof(e4fs_daddr_t) * depth,
 751             M_EXT2EXTENTS, M_WAITOK | M_ZERO);
 752         if (!ablks)
 753                 return (ENOMEM);
 754         for (a = 0; a < depth - at; a++) {
 755                 newblk = ext4_ext_alloc_meta(ip);
 756                 if (newblk == 0)
 757                         goto cleanup;
 758                 ablks[a] = newblk;
 759         }
 760
 761         newblk = ablks[--a];
 762         bp = getblk(ip->i_devvp, fsbtodb(fs, newblk), fs->e2fs_bsize, 0, 0, 0);
 763         if (!bp) {
 764                 error = EIO;
 765                 goto cleanup;
 766         }
 767
 768         neh = ext4_ext_block_header(bp->b_data);
 769         neh->eh_ecount = 0;
 770         neh->eh_max = ext4_ext_space_block(ip);
 771         neh->eh_magic = EXT4_EXT_MAGIC;
 772         neh->eh_depth = 0;
 773         ex = EXT_FIRST_EXTENT(neh);
 774
 775         if (path[depth].ep_header->eh_ecount != path[depth].ep_header->eh_max) {
 776                 ext2_fserr(fs, ip->i_uid,
 777                     "extents count out of range => extent corrupted");
 778                 error = EIO;
 779                 goto cleanup;
 780         }
 781
 782         /* Start copy from next extent. */
 783         m = 0;
 784         path[depth].ep_ext++;
 785         while (path[depth].ep_ext <= EXT_MAX_EXTENT(path[depth].ep_header)) {
 786                 path[depth].ep_ext++;
 787                 m++;
 788         }
 789         if (m) {
 790                 memmove(ex, path[depth].ep_ext - m,
 791                     sizeof(struct ext4_extent) * m);
 792                 neh->eh_ecount = neh->eh_ecount + m;
 793         }
 794
 795         ext2_extent_blk_csum_set(ip, bp->b_data);
 796         bwrite(bp);
 797         bp = NULL;
 798
 799         /* Fix old leaf. */
 800         if (m) {
 801                 path[depth].ep_header->eh_ecount =
 802                     path[depth].ep_header->eh_ecount - m;
 803                 ext4_ext_dirty(ip, path + depth);
 804         }
 805
 806         /* Create intermediate indexes. */
 807         k = depth - at - 1;
 808         KASSERT(k >= 0, ("ext4_ext_split: negative k"));
 809
 810         /* Insert new index into current index block. */
 811         i = depth - 1;
 812         while (k--) {
 813                 oldblk = newblk;
 814                 newblk = ablks[--a];
 815                 error = bread(ip->i_devvp, fsbtodb(fs, newblk),
 816                     (int)fs->e2fs_bsize, NOCRED, &bp);
 817                 if (error) {
 818                         brelse(bp);
 819                         goto cleanup;
 820                 }
 821
 822                 neh = (struct ext4_extent_header *)bp->b_data;
 823                 neh->eh_ecount = 1;
 824                 neh->eh_magic = EXT4_EXT_MAGIC;
 825                 neh->eh_max = ext4_ext_space_block_index(ip);
 826                 neh->eh_depth = depth - i;
 827                 fidx = EXT_FIRST_INDEX(neh);
 828                 fidx->ei_blk = border;
 829                 ext4_index_store_pblock(fidx, oldblk);
 830
 831                 m = 0;
 832                 path[i].ep_index++;
 833                 while (path[i].ep_index <= EXT_MAX_INDEX(path[i].ep_header)) {
 834                         path[i].ep_index++;
 835                         m++;
 836                 }
 837                 if (m) {
 838                         memmove(++fidx, path[i].ep_index - m,
 839                             sizeof(struct ext4_extent_index) * m);
 840                         neh->eh_ecount = neh->eh_ecount + m;
 841                 }
 842
 843                 ext2_extent_blk_csum_set(ip, bp->b_data);
 844                 bwrite(bp);
 845                 bp = NULL;
 846
 847                 /* Fix old index. */
 848                 if (m) {
 849                         path[i].ep_header->eh_ecount =
 850                             path[i].ep_header->eh_ecount - m;
 851                         ext4_ext_dirty(ip, path + i);
 852                 }
 853
 854                 i--;
 855         }
 856
 857         error = ext4_ext_insert_index(ip, path + at, border, newblk);
 858
 859 cleanup:
 860         if (bp)
 861                 brelse(bp);
 862
 863         if (error) {
 864                 for (i = 0; i < depth; i++) {
 865                         if (!ablks[i])
 866                                 continue;
 867                         ext4_ext_blkfree(ip, ablks[i], 1, 0);
 868                 }
 869         }
 870
 871         free(ablks, M_EXT2EXTENTS);
 872
 873         return (error);
 874 }
 875
 876 static int
 877 ext4_ext_grow_indepth(struct inode *ip, struct ext4_extent_path *path,
 878     struct ext4_extent *newext)
 879 {
 880         struct m_ext2fs *fs;
 881         struct ext4_extent_path *curpath;
 882         struct ext4_extent_header *neh;
 883         struct buf *bp;
 884         e4fs_daddr_t newblk;
 885         int error = 0;
 886
 887         fs = ip->i_e2fs;
 888         curpath = path;
 889
 890         newblk = ext4_ext_alloc_meta(ip);
 891         if (newblk == 0)
 892                 return (error);
 893
 894         bp = getblk(ip->i_devvp, fsbtodb(fs, newblk), fs->e2fs_bsize, 0, 0, 0);
 895         if (!bp)
 896                 return (EIO);
 897
 898         /* Move top-level index/leaf into new block. */
 899         memmove(bp->b_data, curpath->ep_header, sizeof(ip->i_data));
 900
 901         /* Set size of new block */
 902         neh = ext4_ext_block_header(bp->b_data);
 903         neh->eh_magic = EXT4_EXT_MAGIC;
 904
 905         if (ext4_ext_inode_depth(ip))
 906                 neh->eh_max = ext4_ext_space_block_index(ip);
 907         else
 908                 neh->eh_max = ext4_ext_space_block(ip);
 909
 910         ext2_extent_blk_csum_set(ip, bp->b_data);
 911         error = bwrite(bp);
 912         if (error)
 913                 goto out;
 914
 915         bp = NULL;
 916
 917         curpath->ep_header->eh_magic = EXT4_EXT_MAGIC;
 918         curpath->ep_header->eh_max = ext4_ext_space_root(ip);
 919         curpath->ep_header->eh_ecount = 1;
 920         curpath->ep_index = EXT_FIRST_INDEX(curpath->ep_header);
 921         curpath->ep_index->ei_blk = EXT_FIRST_EXTENT(path[0].ep_header)->e_blk;
 922         ext4_index_store_pblock(curpath->ep_index, newblk);
 923
 924         neh = ext4_ext_inode_header(ip);
 925         neh->eh_depth = path->ep_depth + 1;
 926         ext4_ext_dirty(ip, curpath);
 927 out:
 928         brelse(bp);
 929
 930         return (error);
 931 }
 932
 933 static int
 934 ext4_ext_create_new_leaf(struct inode *ip, struct ext4_extent_path *path,
 935     struct ext4_extent *newext)
 936 {
 937         struct ext4_extent_path *curpath;
 938         int depth, i, error;
 939
 940 repeat:
 941         i = depth = ext4_ext_inode_depth(ip);
 942
 943         /* Look for free index entry int the tree */
 944         curpath = path + depth;
 945         while (i > 0 && !EXT_HAS_FREE_INDEX(curpath)) {
 946                 i--;
 947                 curpath--;
 948         }
 949
 950         /*
 951          * We use already allocated block for index block,
 952          * so subsequent data blocks should be contiguous.
 953          */
 954         if (EXT_HAS_FREE_INDEX(curpath)) {
 955                 error = ext4_ext_split(ip, path, newext, i);
 956                 if (error)
 957                         goto out;
 958
 959                 /* Refill path. */
 960                 ext4_ext_drop_refs(path);
 961                 error = ext4_ext_find_extent(ip, newext->e_blk, &path);
 962                 if (error)
 963                         goto out;
 964         } else {
 965                 /* Tree is full, do grow in depth. */
 966                 error = ext4_ext_grow_indepth(ip, path, newext);
 967                 if (error)
 968                         goto out;
 969
 970                 /* Refill path. */
 971                 ext4_ext_drop_refs(path);
 972                 error = ext4_ext_find_extent(ip, newext->e_blk, &path);
 973                 if (error)
 974                         goto out;
 975
 976                 /* Check and split tree if required. */
 977                 depth = ext4_ext_inode_depth(ip);
 978                 if (path[depth].ep_header->eh_ecount ==
 979                     path[depth].ep_header->eh_max)
 980                         goto repeat;
 981         }
 982
 983 out:
 984         return (error);
 985 }
 986
 987 static int
 988 ext4_ext_correct_indexes(struct inode *ip, struct ext4_extent_path *path)
 989 {
 990         struct ext4_extent_header *eh;
 991         struct ext4_extent *ex;
 992         int32_t border;
 993         int depth, k;
 994
 995         depth = ext4_ext_inode_depth(ip);
 996         eh = path[depth].ep_header;
 997         ex = path[depth].ep_ext;
 998
 999         if (ex == NULL || eh == NULL)
1000                 return (EIO);
1001
1002         if (!depth)
1003                 return (0);
1004
1005         /* We will correct tree if first leaf got modified only. */
1006         if (ex != EXT_FIRST_EXTENT(eh))
1007                 return (0);
1008
1009         k = depth - 1;
1010         border = path[depth].ep_ext->e_blk;
1011         path[k].ep_index->ei_blk = border;
1012         ext4_ext_dirty(ip, path + k);
1013         while (k--) {
1014                 /* Change all left-side indexes. */
1015                 if (path[k+1].ep_index != EXT_FIRST_INDEX(path[k+1].ep_header))
1016                         break;
1017
1018                 path[k].ep_index->ei_blk = border;
1019                 ext4_ext_dirty(ip, path + k);
1020         }
1021
1022         return (0);
1023 }
1024
1025 static int
1026 ext4_ext_insert_extent(struct inode *ip, struct ext4_extent_path *path,
1027     struct ext4_extent *newext)
1028 {
1029         struct ext4_extent_header * eh;
1030         struct ext4_extent *ex, *nex, *nearex;
1031         struct ext4_extent_path *npath;
1032         int depth, len, error, next;
1033
1034         depth = ext4_ext_inode_depth(ip);
1035         ex = path[depth].ep_ext;
1036         npath = NULL;
1037
1038         if (newext->e_len == 0 || path[depth].ep_header == NULL)
1039                 return (EINVAL);
1040
1041         /* Insert block into found extent. */
1042         if (ex && ext4_can_extents_be_merged(ex, newext)) {
1043                 ex->e_len = ex->e_len + newext->e_len;
1044                 eh = path[depth].ep_header;
1045                 nearex = ex;
1046                 goto merge;
1047         }
1048
1049 repeat:
1050         depth = ext4_ext_inode_depth(ip);
1051         eh = path[depth].ep_header;
1052         if (eh->eh_ecount < eh->eh_max)
1053                 goto has_space;
1054
1055         /* Try next leaf */
1056         nex = EXT_LAST_EXTENT(eh);
1057         next = ext4_ext_next_leaf_block(ip, path);
1058         if (newext->e_blk > nex->e_blk && next != EXT4_MAX_BLOCKS) {
1059                 KASSERT(npath == NULL,
1060                     ("ext4_ext_insert_extent: bad path"));
1061
1062                 error = ext4_ext_find_extent(ip, next, &npath);
1063                 if (error)
1064                         goto cleanup;
1065
1066                 if (npath->ep_depth != path->ep_depth) {
1067                         error = EIO;
1068                         goto cleanup;
1069                 }
1070
1071                 eh = npath[depth].ep_header;
1072                 if (eh->eh_ecount < eh->eh_max) {
1073                         path = npath;
1074                         goto repeat;
1075                 }
1076         }
1077
1078         /*
1079          * There is no free space in the found leaf,
1080          * try to add a new leaf to the tree.
1081          */
1082         error = ext4_ext_create_new_leaf(ip, path, newext);
1083         if (error)
1084                 goto cleanup;
1085
1086         depth = ext4_ext_inode_depth(ip);
1087         eh = path[depth].ep_header;
1088
1089 has_space:
1090         nearex = path[depth].ep_ext;
1091         if (!nearex) {
1092                 /* Create new extent in the leaf. */
1093                 path[depth].ep_ext = EXT_FIRST_EXTENT(eh);
1094         } else if (newext->e_blk > nearex->e_blk) {
1095                 if (nearex != EXT_LAST_EXTENT(eh)) {
1096                         len = EXT_MAX_EXTENT(eh) - nearex;
1097                         len = (len - 1) * sizeof(struct ext4_extent);
1098                         len = len < 0 ? 0 : len;
1099                         memmove(nearex + 2, nearex + 1, len);
1100                 }
1101                 path[depth].ep_ext = nearex + 1;
1102         } else {
1103                 len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent);
1104                 len = len < 0 ? 0 : len;
1105                 memmove(nearex + 1, nearex, len);
1106                 path[depth].ep_ext = nearex;
1107         }
1108
1109         eh->eh_ecount = eh->eh_ecount + 1;
1110         nearex = path[depth].ep_ext;
1111         nearex->e_blk = newext->e_blk;
1112         nearex->e_start_lo = newext->e_start_lo;
1113         nearex->e_start_hi = newext->e_start_hi;
1114         nearex->e_len = newext->e_len;
1115
1116 merge:
1117         /* Try to merge extents to the right. */
1118         while (nearex < EXT_LAST_EXTENT(eh)) {
1119                 if (!ext4_can_extents_be_merged(nearex, nearex + 1))
1120                         break;
1121
1122                 /* Merge with next extent. */
1123                 nearex->e_len = nearex->e_len + nearex[1].e_len;
1124                 if (nearex + 1 < EXT_LAST_EXTENT(eh)) {
1125                         len = (EXT_LAST_EXTENT(eh) - nearex - 1) *
1126                             sizeof(struct ext4_extent);
1127                         memmove(nearex + 1, nearex + 2, len);
1128                 }
1129
1130                 eh->eh_ecount = eh->eh_ecount - 1;
1131                 KASSERT(eh->eh_ecount != 0,
1132                     ("ext4_ext_insert_extent: bad ecount"));
1133         }
1134
1135         /*
1136          * Try to merge extents to the left,
1137          * start from inexes correction.
1138          */
1139         error = ext4_ext_correct_indexes(ip, path);
1140         if (error)
1141                 goto cleanup;
1142
1143         ext4_ext_dirty(ip, path + depth);
1144
1145 cleanup:
1146         if (npath) {
1147                 ext4_ext_drop_refs(npath);
1148                 free(npath, M_EXT2EXTENTS);
1149         }
1150
1151         ip->i_ext_cache.ec_type = EXT4_EXT_CACHE_NO;
1152         return (error);
1153 }
1154
1155 static e4fs_daddr_t
1156 ext4_new_blocks(struct inode *ip, daddr_t lbn, e4fs_daddr_t pref,
1157     struct ucred *cred, unsigned long *count, int *perror)
1158 {
1159         struct m_ext2fs *fs;
1160         e4fs_daddr_t newblk;
1161
1162         /*
1163          * We will allocate only single block for now.
1164          */
1165         if (*count > 1)
1166                 return (0);
1167
1168         fs = ip->i_e2fs;
1169         EXT2_LOCK(ip->i_ump);
1170         *perror = ext2_alloc(ip, lbn, pref, (int)fs->e2fs_bsize, cred, &newblk);
1171         if (*perror)
1172                 return (0);
1173
1174         if (newblk) {
1175                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
1176                 ext2_update(ip->i_vnode, 1);
1177         }
1178
1179         return (newblk);
1180 }
1181
1182 int
1183 ext4_ext_get_blocks(struct inode *ip, e4fs_daddr_t iblk,
1184     unsigned long max_blocks, struct ucred *cred, struct buf **bpp,
1185     int *pallocated, daddr_t *nb)
1186 {
1187         struct m_ext2fs *fs;
1188         struct buf *bp = NULL;
1189         struct ext4_extent_path *path;
1190         struct ext4_extent newex, *ex;
1191         e4fs_daddr_t bpref, newblk = 0;
1192         unsigned long allocated = 0;
1193         int error = 0, depth;
1194
1195         if(bpp)
1196                 *bpp = NULL;
1197         *pallocated = 0;
1198
1199         /* Check cache. */
1200         path = NULL;
1201         if ((bpref = ext4_ext_in_cache(ip, iblk, &newex))) {
1202                 if (bpref == EXT4_EXT_CACHE_IN) {
1203                         /* Block is already allocated. */
1204                         newblk = iblk - newex.e_blk +
1205                             ext4_ext_extent_pblock(&newex);
1206                         allocated = newex.e_len - (iblk - newex.e_blk);
1207                         goto out;
1208                 } else {
1209                         error = EIO;
1210                         goto out2;
1211                 }
1212         }
1213
1214         error = ext4_ext_find_extent(ip, iblk, &path);
1215         if (error) {
1216                 goto out2;
1217         }
1218
1219         depth = ext4_ext_inode_depth(ip);
1220         if (path[depth].ep_ext == NULL && depth != 0) {
1221                 error = EIO;
1222                 goto out2;
1223         }
1224
1225         if ((ex = path[depth].ep_ext)) {
1226                 uint64_t lblk = ex->e_blk;
1227                 uint16_t e_len  = ex->e_len;
1228                 e4fs_daddr_t e_start = ext4_ext_extent_pblock(ex);
1229
1230                 if (e_len > EXT4_MAX_LEN)
1231                         goto out2;
1232
1233                 /* If we found extent covers block, simply return it. */
1234                 if (iblk >= lblk && iblk < lblk + e_len) {
1235                         newblk = iblk - lblk + e_start;
1236                         allocated = e_len - (iblk - lblk);
1237                         ext4_ext_put_in_cache(ip, lblk, e_len,
1238                             e_start, EXT4_EXT_CACHE_IN);
1239                         goto out;
1240                 }
1241         }
1242
1243         /* Allocate the new block. */
1244         if (S_ISREG(ip->i_mode) && (!ip->i_next_alloc_block)) {
1245                 ip->i_next_alloc_goal = 0;
1246         }
1247
1248         bpref = ext4_ext_blkpref(ip, path, iblk);
1249         allocated = max_blocks;
1250         newblk = ext4_new_blocks(ip, iblk, bpref, cred, &allocated, &error);
1251         if (!newblk)
1252                 goto out2;
1253
1254         /* Try to insert new extent into found leaf and return. */
1255         newex.e_blk = iblk;
1256         ext4_ext_store_pblock(&newex, newblk);
1257         newex.e_len = allocated;
1258         error = ext4_ext_insert_extent(ip, path, &newex);
1259         if (error)
1260                 goto out2;
1261
1262         newblk = ext4_ext_extent_pblock(&newex);
1263         ext4_ext_put_in_cache(ip, iblk, allocated, newblk, EXT4_EXT_CACHE_IN);
1264         *pallocated = 1;
1265
1266 out:
1267         if (allocated > max_blocks)
1268                 allocated = max_blocks;
1269
1270         if (bpp)
1271         {
1272                 fs = ip->i_e2fs;
1273                 error = bread(ip->i_devvp, fsbtodb(fs, newblk),
1274                     fs->e2fs_bsize, cred, &bp);
1275                 if (error) {
1276                         brelse(bp);
1277                 } else {
1278                         *bpp = bp;
1279                 }
1280         }
1281
1282 out2:
1283         if (path) {
1284                 ext4_ext_drop_refs(path);
1285                 free(path, M_EXT2EXTENTS);
1286         }
1287
1288         if (nb)
1289                 *nb = newblk;
1290
1291         return (error);
1292 }
1293
1294 static inline uint16_t
1295 ext4_ext_get_actual_len(struct ext4_extent *ext)
1296 {
1297
1298         return (ext->e_len <= EXT_INIT_MAX_LEN ?
1299             ext->e_len : (ext->e_len - EXT_INIT_MAX_LEN));
1300 }
1301
1302 static inline struct ext4_extent_header *
1303 ext4_ext_header(struct inode *ip)
1304 {
1305
1306         return ((struct ext4_extent_header *)ip->i_db);
1307 }
1308
1309 static int
1310 ext4_remove_blocks(struct inode *ip, struct ext4_extent *ex,
1311     unsigned long from, unsigned long to)
1312 {
1313         unsigned long num, start;
1314
1315         if (from >= ex->e_blk &&
1316             to == ex->e_blk + ext4_ext_get_actual_len(ex) - 1) {
1317                 /* Tail cleanup. */
1318                 num = ex->e_blk + ext4_ext_get_actual_len(ex) - from;
1319                 start = ext4_ext_extent_pblock(ex) +
1320                     ext4_ext_get_actual_len(ex) - num;
1321                 ext4_ext_blkfree(ip, start, num, 0);
1322         }
1323
1324         return (0);
1325 }
1326
1327 static int
1328 ext4_ext_rm_index(struct inode *ip, struct ext4_extent_path *path)
1329 {
1330         e4fs_daddr_t leaf;
1331
1332         /* Free index block. */
1333         path--;
1334         leaf = ext4_ext_index_pblock(path->ep_index);
1335         KASSERT(path->ep_header->eh_ecount != 0,
1336             ("ext4_ext_rm_index: bad ecount"));
1337         path->ep_header->eh_ecount--;
1338         ext4_ext_dirty(ip, path);
1339         ext4_ext_blkfree(ip, leaf, 1, 0);
1340         return (0);
1341 }
1342
1343 static int
1344 ext4_ext_rm_leaf(struct inode *ip, struct ext4_extent_path *path,
1345     uint64_t start)
1346 {
1347         struct ext4_extent_header *eh;
1348         struct ext4_extent *ex;
1349         unsigned int a, b, block, num;
1350         unsigned long ex_blk;
1351         unsigned short ex_len;
1352         int depth;
1353         int error, correct_index;
1354
1355         depth = ext4_ext_inode_depth(ip);
1356         if (!path[depth].ep_header) {
1357                 if (path[depth].ep_data == NULL)
1358                         return (EINVAL);
1359                 path[depth].ep_header =
1360                     (struct ext4_extent_header* )path[depth].ep_data;
1361         }
1362
1363         eh = path[depth].ep_header;
1364         if (!eh) {
1365                 ext2_fserr(ip->i_e2fs, ip->i_uid,
1366                     "bad header => extent corrupted");
1367                 return (EIO);
1368         }
1369
1370         ex = EXT_LAST_EXTENT(eh);
1371         ex_blk = ex->e_blk;
1372         ex_len = ext4_ext_get_actual_len(ex);
1373
1374         error = 0;
1375         correct_index = 0;
1376         while (ex >= EXT_FIRST_EXTENT(eh) && ex_blk + ex_len > start) {
1377                 path[depth].ep_ext = ex;
1378                 a = ex_blk > start ? ex_blk : start;
1379                 b = (uint64_t)ex_blk + ex_len - 1 <
1380                     EXT4_MAX_BLOCKS ? ex_blk + ex_len - 1 : EXT4_MAX_BLOCKS;
1381
1382                 if (a != ex_blk && b != ex_blk + ex_len - 1)
1383                         return (EINVAL);
1384                 else if (a != ex_blk) {
1385                         /* Remove tail of the extent. */
1386                         block = ex_blk;
1387                         num = a - block;
1388                 } else if (b != ex_blk + ex_len - 1) {
1389                         /* Remove head of the extent, not implemented. */
1390                         return (EINVAL);
1391                 } else {
1392                         /* Remove whole extent. */
1393                         block = ex_blk;
1394                         num = 0;
1395                 }
1396
1397                 if (ex == EXT_FIRST_EXTENT(eh))
1398                         correct_index = 1;
1399
1400                 error = ext4_remove_blocks(ip, ex, a, b);
1401                 if (error)
1402                         goto out;
1403
1404                 if (num == 0) {
1405                         ext4_ext_store_pblock(ex, 0);
1406                         eh->eh_ecount--;
1407                 }
1408
1409                 ex->e_blk = block;
1410                 ex->e_len = num;
1411
1412                 ext4_ext_dirty(ip, path + depth);
1413
1414                 ex--;
1415                 ex_blk = ex->e_blk;
1416                 ex_len = ext4_ext_get_actual_len(ex);
1417         };
1418
1419         if (correct_index && eh->eh_ecount)
1420                 error = ext4_ext_correct_indexes(ip, path);
1421
1422         /*
1423          * If this leaf is free, we should
1424          * remove it from index block above.
1425          */
1426         if (error == 0 && eh->eh_ecount == 0 && path[depth].ep_data != NULL)
1427                 error = ext4_ext_rm_index(ip, path + depth);
1428
1429 out:
1430         return (error);
1431 }
1432
1433 static struct buf *
1434 ext4_read_extent_tree_block(struct inode *ip, e4fs_daddr_t pblk,
1435     int depth, int flags)
1436 {
1437         struct m_ext2fs *fs;
1438         struct ext4_extent_header *eh;
1439         struct buf *bp;
1440         int error;
1441
1442         fs = ip->i_e2fs;
1443         error = bread(ip->i_devvp, fsbtodb(fs, pblk),
1444             fs->e2fs_bsize, NOCRED, &bp);
1445         if (error) {
1446                 brelse(bp);
1447                 return (NULL);
1448         }
1449
1450         eh = ext4_ext_block_header(bp->b_data);
1451         if (eh->eh_depth != depth) {
1452                 ext2_fserr(fs, ip->i_uid, "unexpected eh_depth");
1453                 goto err;
1454         }
1455
1456         error = ext4_ext_check_header(ip, eh);
1457         if (error)
1458                 goto err;
1459
1460         return (bp);
1461
1462 err:
1463         brelse(bp);
1464         return (NULL);
1465
1466 }
1467
1468 static int inline
1469 ext4_ext_more_to_rm(struct ext4_extent_path *path)
1470 {
1471
1472         KASSERT(path->ep_index != NULL,
1473             ("ext4_ext_more_to_rm: bad index from path"));
1474
1475         if (path->ep_index < EXT_FIRST_INDEX(path->ep_header))
1476                 return (0);
1477
1478         if (path->ep_header->eh_ecount == path->index_count)
1479                 return (0);
1480
1481         return (1);
1482 }
1483
1484 int
1485 ext4_ext_remove_space(struct inode *ip, off_t length, int flags,
1486     struct ucred *cred, struct thread *td)
1487 {
1488         struct buf *bp;
1489         struct ext4_extent_header *ehp;
1490         struct ext4_extent_path *path;
1491         int depth;
1492         int i, error;
1493
1494         ehp = (struct ext4_extent_header *)ip->i_db;
1495         depth = ext4_ext_inode_depth(ip);
1496
1497         error = ext4_ext_check_header(ip, ehp);
1498         if(error)
1499                 return (error);
1500
1501         path = malloc(sizeof(struct ext4_extent_path) * (depth + 1),
1502             M_EXT2EXTENTS, M_WAITOK | M_ZERO);
1503         if (!path)
1504                 return (ENOMEM);
1505
1506         path[0].ep_header = ehp;
1507         path[0].ep_depth = depth;
1508         i = 0;
1509         while (error == 0 && i >= 0) {
1510                 if (i == depth) {
1511                         /* This is leaf. */
1512                         error = ext4_ext_rm_leaf(ip, path, length);
1513                         if (error)
1514                                 break;
1515                         free(path[i].ep_data, M_EXT2EXTENTS);
1516                         path[i].ep_data = NULL;
1517                         i--;
1518                         continue;
1519                 }
1520
1521                 /* This is index. */
1522                 if (!path[i].ep_header)
1523                         path[i].ep_header =
1524                             (struct ext4_extent_header *)path[i].ep_data;
1525
1526                 if (!path[i].ep_index) {
1527                         /* This level hasn't touched yet. */
1528                         path[i].ep_index = EXT_LAST_INDEX(path[i].ep_header);
1529                         path[i].index_count = path[i].ep_header->eh_ecount + 1;
1530                 } else {
1531                         /* We've already was here, see at next index. */
1532                         path[i].ep_index--;
1533                 }
1534
1535                 if (ext4_ext_more_to_rm(path + i)) {
1536                         memset(path + i + 1, 0, sizeof(*path));
1537                         bp = ext4_read_extent_tree_block(ip,
1538                             ext4_ext_index_pblock(path[i].ep_index),
1539                             path[0].ep_depth - (i + 1), 0);
1540                         if (!bp) {
1541                                 error = EIO;
1542                                 break;
1543                         }
1544
1545                         ext4_ext_fill_path_bdata(&path[i+1], bp,
1546                             ext4_ext_index_pblock(path[i].ep_index));
1547                         brelse(bp);
1548                         path[i].index_count = path[i].ep_header->eh_ecount;
1549                         i++;
1550                 } else {
1551                         if (path[i].ep_header->eh_ecount == 0 && i > 0) {
1552                                 /* Index is empty, remove it. */
1553                                 error = ext4_ext_rm_index(ip, path + i);
1554                         }
1555                         free(path[i].ep_data, M_EXT2EXTENTS);
1556                         path[i].ep_data = NULL;
1557                         i--;
1558                 }
1559         }
1560
1561         if (path->ep_header->eh_ecount == 0) {
1562                 /*
1563                  * Truncate the tree to zero.
1564                  */
1565                  ext4_ext_header(ip)->eh_depth = 0;
1566                  ext4_ext_header(ip)->eh_max = ext4_ext_space_root(ip);
1567                  ext4_ext_dirty(ip, path);
1568         }
1569
1570         ext4_ext_drop_refs(path);
1571         free(path, M_EXT2EXTENTS);
1572
1573         return (error);
1574 }