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