The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/fs/ext2fs/ext2_extents.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

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

Cache object: 1cfc6f8f640a72a52a5fef29496b01d2


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.