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