sys/fs/ext2fs/ext2_extents.c

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