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