sys/fs/ext2fs/ext2_extents.c

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