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