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