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 * $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 } 1782