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