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 return (EIO); 1104 1105 /* Move top-level index/leaf into new block. */ 1106 memmove(bp->b_data, curpath->ep_header, sizeof(ip->i_data)); 1107 1108 /* Set size of new block */ 1109 neh = ext4_ext_block_header(bp->b_data); 1110 neh->eh_magic = htole16(EXT4_EXT_MAGIC); 1111 1112 if (ext4_ext_inode_depth(ip)) 1113 neh->eh_max = htole16(ext4_ext_space_block_index(ip)); 1114 else 1115 neh->eh_max = htole16(ext4_ext_space_block(ip)); 1116 1117 ext2_extent_blk_csum_set(ip, bp->b_data); 1118 error = bwrite(bp); 1119 if (error) 1120 goto out; 1121 1122 bp = NULL; 1123 1124 curpath->ep_header->eh_magic = htole16(EXT4_EXT_MAGIC); 1125 curpath->ep_header->eh_max = htole16(ext4_ext_space_root(ip)); 1126 curpath->ep_header->eh_ecount = htole16(1); 1127 curpath->ep_index = EXT_FIRST_INDEX(curpath->ep_header); 1128 curpath->ep_index->ei_blk = EXT_FIRST_EXTENT(path[0].ep_header)->e_blk; 1129 ext4_index_store_pblock(curpath->ep_index, newblk); 1130 1131 neh = ext4_ext_inode_header(ip); 1132 neh->eh_depth = htole16(path->ep_depth + 1); 1133 ext4_ext_dirty(ip, curpath); 1134 out: 1135 brelse(bp); 1136 1137 return (error); 1138 } 1139 1140 static int 1141 ext4_ext_create_new_leaf(struct inode *ip, struct ext4_extent_path *path, 1142 struct ext4_extent *newext) 1143 { 1144 struct ext4_extent_path *curpath; 1145 int depth, i, error; 1146 1147 repeat: 1148 i = depth = ext4_ext_inode_depth(ip); 1149 1150 /* Look for free index entry int the tree */ 1151 curpath = path + depth; 1152 while (i > 0 && !EXT_HAS_FREE_INDEX(curpath)) { 1153 i--; 1154 curpath--; 1155 } 1156 1157 /* 1158 * We use already allocated block for index block, 1159 * so subsequent data blocks should be contiguous. 1160 */ 1161 if (EXT_HAS_FREE_INDEX(curpath)) { 1162 error = ext4_ext_split(ip, path, newext, i); 1163 if (error) 1164 goto out; 1165 1166 /* Refill path. */ 1167 ext4_ext_drop_refs(path); 1168 error = ext4_ext_find_extent(ip, le32toh(newext->e_blk), &path); 1169 if (error) 1170 goto out; 1171 } else { 1172 /* Tree is full, do grow in depth. */ 1173 error = ext4_ext_grow_indepth(ip, path, newext); 1174 if (error) 1175 goto out; 1176 1177 /* Refill path. */ 1178 ext4_ext_drop_refs(path); 1179 error = ext4_ext_find_extent(ip, le32toh(newext->e_blk), &path); 1180 if (error) 1181 goto out; 1182 1183 /* Check and split tree if required. */ 1184 depth = ext4_ext_inode_depth(ip); 1185 if (le16toh(path[depth].ep_header->eh_ecount) == 1186 le16toh(path[depth].ep_header->eh_max)) 1187 goto repeat; 1188 } 1189 1190 out: 1191 return (error); 1192 } 1193 1194 static int 1195 ext4_ext_correct_indexes(struct inode *ip, struct ext4_extent_path *path) 1196 { 1197 struct ext4_extent_header *eh; 1198 struct ext4_extent *ex; 1199 int32_t border; 1200 int depth, k; 1201 1202 depth = ext4_ext_inode_depth(ip); 1203 eh = path[depth].ep_header; 1204 ex = path[depth].ep_ext; 1205 1206 if (ex == NULL || eh == NULL) 1207 return (EIO); 1208 1209 if (!depth) 1210 return (0); 1211 1212 /* We will correct tree if first leaf got modified only. */ 1213 if (ex != EXT_FIRST_EXTENT(eh)) 1214 return (0); 1215 1216 k = depth - 1; 1217 border = le32toh(path[depth].ep_ext->e_blk); 1218 path[k].ep_index->ei_blk = htole32(border); 1219 ext4_ext_dirty(ip, path + k); 1220 while (k--) { 1221 /* Change all left-side indexes. */ 1222 if (path[k+1].ep_index != EXT_FIRST_INDEX(path[k+1].ep_header)) 1223 break; 1224 1225 path[k].ep_index->ei_blk = htole32(border); 1226 ext4_ext_dirty(ip, path + k); 1227 } 1228 1229 return (0); 1230 } 1231 1232 static int 1233 ext4_ext_insert_extent(struct inode *ip, struct ext4_extent_path *path, 1234 struct ext4_extent *newext) 1235 { 1236 struct ext4_extent_header * eh; 1237 struct ext4_extent *ex, *nex, *nearex; 1238 struct ext4_extent_path *npath; 1239 int depth, len, error, next; 1240 1241 depth = ext4_ext_inode_depth(ip); 1242 ex = path[depth].ep_ext; 1243 npath = NULL; 1244 1245 if (htole16(newext->e_len) == 0 || path[depth].ep_header == NULL) 1246 return (EINVAL); 1247 1248 /* Insert block into found extent. */ 1249 if (ex && ext4_can_extents_be_merged(ex, newext)) { 1250 ex->e_len = htole16(le16toh(ex->e_len) + le16toh(newext->e_len)); 1251 eh = path[depth].ep_header; 1252 nearex = ex; 1253 goto merge; 1254 } 1255 1256 repeat: 1257 depth = ext4_ext_inode_depth(ip); 1258 eh = path[depth].ep_header; 1259 if (le16toh(eh->eh_ecount) < le16toh(eh->eh_max)) 1260 goto has_space; 1261 1262 /* Try next leaf */ 1263 nex = EXT_LAST_EXTENT(eh); 1264 next = ext4_ext_next_leaf_block(ip, path); 1265 if (le32toh(newext->e_blk) > le32toh(nex->e_blk) && next != 1266 EXT4_MAX_BLOCKS) { 1267 KASSERT(npath == NULL, 1268 ("ext4_ext_insert_extent: bad path")); 1269 1270 error = ext4_ext_find_extent(ip, next, &npath); 1271 if (error) 1272 goto cleanup; 1273 1274 if (npath->ep_depth != path->ep_depth) { 1275 error = EIO; 1276 goto cleanup; 1277 } 1278 1279 eh = npath[depth].ep_header; 1280 if (le16toh(eh->eh_ecount) < le16toh(eh->eh_max)) { 1281 path = npath; 1282 goto repeat; 1283 } 1284 } 1285 1286 /* 1287 * There is no free space in the found leaf, 1288 * try to add a new leaf to the tree. 1289 */ 1290 error = ext4_ext_create_new_leaf(ip, path, newext); 1291 if (error) 1292 goto cleanup; 1293 1294 depth = ext4_ext_inode_depth(ip); 1295 eh = path[depth].ep_header; 1296 1297 has_space: 1298 nearex = path[depth].ep_ext; 1299 if (!nearex) { 1300 /* Create new extent in the leaf. */ 1301 path[depth].ep_ext = EXT_FIRST_EXTENT(eh); 1302 } else if (le32toh(newext->e_blk) > le32toh(nearex->e_blk)) { 1303 if (nearex != EXT_LAST_EXTENT(eh)) { 1304 len = EXT_MAX_EXTENT(eh) - nearex; 1305 len = (len - 1) * sizeof(struct ext4_extent); 1306 len = len < 0 ? 0 : len; 1307 memmove(nearex + 2, nearex + 1, len); 1308 } 1309 path[depth].ep_ext = nearex + 1; 1310 } else { 1311 len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent); 1312 len = len < 0 ? 0 : len; 1313 memmove(nearex + 1, nearex, len); 1314 path[depth].ep_ext = nearex; 1315 } 1316 1317 eh->eh_ecount = htole16(le16toh(eh->eh_ecount) + 1); 1318 nearex = path[depth].ep_ext; 1319 nearex->e_blk = newext->e_blk; 1320 nearex->e_start_lo = newext->e_start_lo; 1321 nearex->e_start_hi = newext->e_start_hi; 1322 nearex->e_len = newext->e_len; 1323 1324 merge: 1325 /* Try to merge extents to the right. */ 1326 while (nearex < EXT_LAST_EXTENT(eh)) { 1327 if (!ext4_can_extents_be_merged(nearex, nearex + 1)) 1328 break; 1329 1330 /* Merge with next extent. */ 1331 nearex->e_len = htole16(le16toh(nearex->e_len) + 1332 le16toh(nearex[1].e_len)); 1333 if (nearex + 1 < EXT_LAST_EXTENT(eh)) { 1334 len = (EXT_LAST_EXTENT(eh) - nearex - 1) * 1335 sizeof(struct ext4_extent); 1336 memmove(nearex + 1, nearex + 2, len); 1337 } 1338 1339 eh->eh_ecount = htole16(le16toh(eh->eh_ecount) - 1); 1340 KASSERT(le16toh(eh->eh_ecount) != 0, 1341 ("ext4_ext_insert_extent: bad ecount")); 1342 } 1343 1344 /* 1345 * Try to merge extents to the left, 1346 * start from inexes correction. 1347 */ 1348 error = ext4_ext_correct_indexes(ip, path); 1349 if (error) 1350 goto cleanup; 1351 1352 ext4_ext_dirty(ip, path + depth); 1353 1354 cleanup: 1355 if (npath) { 1356 ext4_ext_drop_refs(npath); 1357 free(npath, M_EXT2EXTENTS); 1358 } 1359 1360 ip->i_ext_cache.ec_type = EXT4_EXT_CACHE_NO; 1361 return (error); 1362 } 1363 1364 static e4fs_daddr_t 1365 ext4_new_blocks(struct inode *ip, daddr_t lbn, e4fs_daddr_t pref, 1366 struct ucred *cred, unsigned long *count, int *perror) 1367 { 1368 struct m_ext2fs *fs; 1369 e4fs_daddr_t newblk; 1370 1371 /* 1372 * We will allocate only single block for now. 1373 */ 1374 if (*count > 1) 1375 return (0); 1376 1377 fs = ip->i_e2fs; 1378 EXT2_LOCK(ip->i_ump); 1379 *perror = ext2_alloc(ip, lbn, pref, (int)fs->e2fs_bsize, cred, &newblk); 1380 if (*perror) 1381 return (0); 1382 1383 if (newblk) { 1384 ip->i_flag |= IN_CHANGE | IN_UPDATE; 1385 ext2_update(ip->i_vnode, 1); 1386 } 1387 1388 return (newblk); 1389 } 1390 1391 int 1392 ext4_ext_get_blocks(struct inode *ip, e4fs_daddr_t iblk, 1393 unsigned long max_blocks, struct ucred *cred, struct buf **bpp, 1394 int *pallocated, daddr_t *nb) 1395 { 1396 struct m_ext2fs *fs; 1397 struct buf *bp = NULL; 1398 struct ext4_extent_path *path; 1399 struct ext4_extent newex, *ex; 1400 e4fs_daddr_t bpref, newblk = 0; 1401 unsigned long allocated = 0; 1402 int error = 0, depth; 1403 1404 if(bpp) 1405 *bpp = NULL; 1406 *pallocated = 0; 1407 1408 /* Check cache. */ 1409 path = NULL; 1410 if ((bpref = ext4_ext_in_cache(ip, iblk, &newex))) { 1411 if (bpref == EXT4_EXT_CACHE_IN) { 1412 /* Block is already allocated. */ 1413 newblk = iblk - le32toh(newex.e_blk) + 1414 ext4_ext_extent_pblock(&newex); 1415 allocated = le16toh(newex.e_len) - (iblk - le32toh(newex.e_blk)); 1416 goto out; 1417 } else { 1418 error = EIO; 1419 goto out2; 1420 } 1421 } 1422 1423 error = ext4_ext_find_extent(ip, iblk, &path); 1424 if (error) { 1425 goto out2; 1426 } 1427 1428 depth = ext4_ext_inode_depth(ip); 1429 if (path[depth].ep_ext == NULL && depth != 0) { 1430 error = EIO; 1431 goto out2; 1432 } 1433 1434 if ((ex = path[depth].ep_ext)) { 1435 uint64_t lblk = le32toh(ex->e_blk); 1436 uint16_t e_len = le16toh(ex->e_len); 1437 e4fs_daddr_t e_start = ext4_ext_extent_pblock(ex); 1438 1439 if (e_len > EXT4_MAX_LEN) 1440 goto out2; 1441 1442 /* If we found extent covers block, simply return it. */ 1443 if (iblk >= lblk && iblk < lblk + e_len) { 1444 newblk = iblk - lblk + e_start; 1445 allocated = e_len - (iblk - lblk); 1446 ext4_ext_put_in_cache(ip, lblk, e_len, 1447 e_start, EXT4_EXT_CACHE_IN); 1448 goto out; 1449 } 1450 } 1451 1452 /* Allocate the new block. */ 1453 if (S_ISREG(ip->i_mode) && (!ip->i_next_alloc_block)) { 1454 ip->i_next_alloc_goal = 0; 1455 } 1456 1457 bpref = ext4_ext_blkpref(ip, path, iblk); 1458 allocated = max_blocks; 1459 newblk = ext4_new_blocks(ip, iblk, bpref, cred, &allocated, &error); 1460 if (!newblk) 1461 goto out2; 1462 1463 /* Try to insert new extent into found leaf and return. */ 1464 newex.e_blk = htole32(iblk); 1465 ext4_ext_store_pblock(&newex, newblk); 1466 newex.e_len = htole16(allocated); 1467 error = ext4_ext_insert_extent(ip, path, &newex); 1468 if (error) 1469 goto out2; 1470 1471 newblk = ext4_ext_extent_pblock(&newex); 1472 ext4_ext_put_in_cache(ip, iblk, allocated, newblk, EXT4_EXT_CACHE_IN); 1473 *pallocated = 1; 1474 1475 out: 1476 if (allocated > max_blocks) 1477 allocated = max_blocks; 1478 1479 if (bpp) 1480 { 1481 fs = ip->i_e2fs; 1482 error = bread(ip->i_devvp, fsbtodb(fs, newblk), 1483 fs->e2fs_bsize, cred, &bp); 1484 if (error) { 1485 brelse(bp); 1486 } else { 1487 *bpp = bp; 1488 } 1489 } 1490 1491 out2: 1492 if (path) { 1493 ext4_ext_drop_refs(path); 1494 free(path, M_EXT2EXTENTS); 1495 } 1496 1497 if (nb) 1498 *nb = newblk; 1499 1500 return (error); 1501 } 1502 1503 static inline struct ext4_extent_header * 1504 ext4_ext_header(struct inode *ip) 1505 { 1506 1507 return ((struct ext4_extent_header *)ip->i_db); 1508 } 1509 1510 static int 1511 ext4_remove_blocks(struct inode *ip, struct ext4_extent *ex, 1512 unsigned long from, unsigned long to) 1513 { 1514 unsigned long num, start; 1515 1516 if (from >= le32toh(ex->e_blk) && 1517 to == le32toh(ex->e_blk) + ext4_ext_get_actual_len(ex) - 1) { 1518 /* Tail cleanup. */ 1519 num = le32toh(ex->e_blk) + ext4_ext_get_actual_len(ex) - from; 1520 start = ext4_ext_extent_pblock(ex) + 1521 ext4_ext_get_actual_len(ex) - num; 1522 ext4_ext_blkfree(ip, start, num, 0); 1523 } 1524 1525 return (0); 1526 } 1527 1528 static int 1529 ext4_ext_rm_index(struct inode *ip, struct ext4_extent_path *path) 1530 { 1531 e4fs_daddr_t leaf; 1532 1533 /* Free index block. */ 1534 path--; 1535 leaf = ext4_ext_index_pblock(path->ep_index); 1536 KASSERT(path->ep_header->eh_ecount != 0, 1537 ("ext4_ext_rm_index: bad ecount")); 1538 path->ep_header->eh_ecount = 1539 htole16(le16toh(path->ep_header->eh_ecount) - 1); 1540 ext4_ext_dirty(ip, path); 1541 ext4_ext_blkfree(ip, leaf, 1, 0); 1542 return (0); 1543 } 1544 1545 static int 1546 ext4_ext_rm_leaf(struct inode *ip, struct ext4_extent_path *path, 1547 uint64_t start) 1548 { 1549 struct ext4_extent_header *eh; 1550 struct ext4_extent *ex; 1551 unsigned int a, b, block, num; 1552 unsigned long ex_blk; 1553 unsigned short ex_len; 1554 int depth; 1555 int error, correct_index; 1556 1557 depth = ext4_ext_inode_depth(ip); 1558 if (!path[depth].ep_header) { 1559 if (path[depth].ep_data == NULL) 1560 return (EINVAL); 1561 path[depth].ep_header = 1562 (struct ext4_extent_header* )path[depth].ep_data; 1563 } 1564 1565 eh = path[depth].ep_header; 1566 if (!eh) { 1567 SDT_PROBE2(ext2fs, , trace, extents, 1, 1568 "bad header => extent corrupted"); 1569 return (EIO); 1570 } 1571 1572 ex = EXT_LAST_EXTENT(eh); 1573 ex_blk = le32toh(ex->e_blk); 1574 ex_len = ext4_ext_get_actual_len(ex); 1575 1576 error = 0; 1577 correct_index = 0; 1578 while (ex >= EXT_FIRST_EXTENT(eh) && ex_blk + ex_len > start) { 1579 path[depth].ep_ext = ex; 1580 a = ex_blk > start ? ex_blk : start; 1581 b = (uint64_t)ex_blk + ex_len - 1 < 1582 EXT4_MAX_BLOCKS ? ex_blk + ex_len - 1 : EXT4_MAX_BLOCKS; 1583 1584 if (a != ex_blk && b != ex_blk + ex_len - 1) 1585 return (EINVAL); 1586 else if (a != ex_blk) { 1587 /* Remove tail of the extent. */ 1588 block = ex_blk; 1589 num = a - block; 1590 } else if (b != ex_blk + ex_len - 1) { 1591 /* Remove head of the extent, not implemented. */ 1592 return (EINVAL); 1593 } else { 1594 /* Remove whole extent. */ 1595 block = ex_blk; 1596 num = 0; 1597 } 1598 1599 if (ex == EXT_FIRST_EXTENT(eh)) 1600 correct_index = 1; 1601 1602 error = ext4_remove_blocks(ip, ex, a, b); 1603 if (error) 1604 goto out; 1605 1606 if (num == 0) { 1607 ext4_ext_store_pblock(ex, 0); 1608 eh->eh_ecount = htole16(le16toh(eh->eh_ecount) - 1); 1609 } 1610 1611 ex->e_blk = htole32(block); 1612 ex->e_len = htole16(num); 1613 1614 ext4_ext_dirty(ip, path + depth); 1615 1616 ex--; 1617 ex_blk = htole32(ex->e_blk); 1618 ex_len = ext4_ext_get_actual_len(ex); 1619 }; 1620 1621 if (correct_index && le16toh(eh->eh_ecount)) 1622 error = ext4_ext_correct_indexes(ip, path); 1623 1624 /* 1625 * If this leaf is free, we should 1626 * remove it from index block above. 1627 */ 1628 if (error == 0 && eh->eh_ecount == 0 && 1629 path[depth].ep_data != NULL) 1630 error = ext4_ext_rm_index(ip, path + depth); 1631 1632 out: 1633 return (error); 1634 } 1635 1636 static struct buf * 1637 ext4_read_extent_tree_block(struct inode *ip, e4fs_daddr_t pblk, 1638 int depth, int flags) 1639 { 1640 struct m_ext2fs *fs; 1641 struct ext4_extent_header *eh; 1642 struct buf *bp; 1643 int error; 1644 1645 fs = ip->i_e2fs; 1646 error = bread(ip->i_devvp, fsbtodb(fs, pblk), 1647 fs->e2fs_bsize, NOCRED, &bp); 1648 if (error) { 1649 return (NULL); 1650 } 1651 1652 eh = ext4_ext_block_header(bp->b_data); 1653 if (le16toh(eh->eh_depth) != depth) { 1654 SDT_PROBE2(ext2fs, , trace, extents, 1, 1655 "unexpected eh_depth"); 1656 goto err; 1657 } 1658 1659 error = ext4_ext_check_header(ip, eh, depth); 1660 if (error) 1661 goto err; 1662 1663 return (bp); 1664 1665 err: 1666 brelse(bp); 1667 return (NULL); 1668 1669 } 1670 1671 static int inline 1672 ext4_ext_more_to_rm(struct ext4_extent_path *path) 1673 { 1674 1675 KASSERT(path->ep_index != NULL, 1676 ("ext4_ext_more_to_rm: bad index from path")); 1677 1678 if (path->ep_index < EXT_FIRST_INDEX(path->ep_header)) 1679 return (0); 1680 1681 if (le16toh(path->ep_header->eh_ecount) == path->index_count) 1682 return (0); 1683 1684 return (1); 1685 } 1686 1687 int 1688 ext4_ext_remove_space(struct inode *ip, off_t length, int flags, 1689 struct ucred *cred, struct thread *td) 1690 { 1691 struct buf *bp; 1692 struct ext4_extent_header *ehp; 1693 struct ext4_extent_path *path; 1694 int depth; 1695 int i, error; 1696 1697 ehp = (struct ext4_extent_header *)ip->i_db; 1698 depth = ext4_ext_inode_depth(ip); 1699 1700 error = ext4_ext_check_header(ip, ehp, depth); 1701 if(error) 1702 return (error); 1703 1704 path = malloc(sizeof(struct ext4_extent_path) * (depth + 1), 1705 M_EXT2EXTENTS, M_WAITOK | M_ZERO); 1706 path[0].ep_header = ehp; 1707 path[0].ep_depth = depth; 1708 i = 0; 1709 while (error == 0 && i >= 0) { 1710 if (i == depth) { 1711 /* This is leaf. */ 1712 error = ext4_ext_rm_leaf(ip, path, length); 1713 if (error) 1714 break; 1715 free(path[i].ep_data, M_EXT2EXTENTS); 1716 path[i].ep_data = NULL; 1717 i--; 1718 continue; 1719 } 1720 1721 /* This is index. */ 1722 if (!path[i].ep_header) 1723 path[i].ep_header = 1724 (struct ext4_extent_header *)path[i].ep_data; 1725 1726 if (!path[i].ep_index) { 1727 /* This level hasn't touched yet. */ 1728 path[i].ep_index = EXT_LAST_INDEX(path[i].ep_header); 1729 path[i].index_count = 1730 le16toh(path[i].ep_header->eh_ecount) + 1; 1731 } else { 1732 /* We've already was here, see at next index. */ 1733 path[i].ep_index--; 1734 } 1735 1736 if (ext4_ext_more_to_rm(path + i)) { 1737 memset(path + i + 1, 0, sizeof(*path)); 1738 bp = ext4_read_extent_tree_block(ip, 1739 ext4_ext_index_pblock(path[i].ep_index), 1740 path[0].ep_depth - (i + 1), 0); 1741 if (!bp) { 1742 error = EIO; 1743 break; 1744 } 1745 1746 ext4_ext_fill_path_bdata(&path[i+1], bp, 1747 ext4_ext_index_pblock(path[i].ep_index)); 1748 brelse(bp); 1749 path[i].index_count = 1750 le16toh(path[i].ep_header->eh_ecount); 1751 i++; 1752 } else { 1753 if (path[i].ep_header->eh_ecount == 0 && i > 0) { 1754 /* Index is empty, remove it. */ 1755 error = ext4_ext_rm_index(ip, path + i); 1756 } 1757 free(path[i].ep_data, M_EXT2EXTENTS); 1758 path[i].ep_data = NULL; 1759 i--; 1760 } 1761 } 1762 1763 if (path->ep_header->eh_ecount == 0) { 1764 /* 1765 * Truncate the tree to zero. 1766 */ 1767 ext4_ext_header(ip)->eh_depth = 0; 1768 ext4_ext_header(ip)->eh_max = htole16(ext4_ext_space_root(ip)); 1769 ext4_ext_dirty(ip, path); 1770 } 1771 1772 ext4_ext_drop_refs(path); 1773 free(path, M_EXT2EXTENTS); 1774 1775 ip->i_ext_cache.ec_type = EXT4_EXT_CACHE_NO; 1776 return (error); 1777 } 1778