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