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

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