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