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

Cache object: 090283d0e673d8356e1754d72f331256


[ 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.