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_htree.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, 2012 Zheng Liu <lz@freebsd.org>
    5  * Copyright (c) 2012, Vyacheslav Matyushin
    6  * All rights reserved.
    7  *
    8  * Redistribution and use in source and binary forms, with or without
    9  * modification, are permitted provided that the following conditions
   10  * are met:
   11  * 1. Redistributions of source code must retain the above copyright
   12  *    notice, this list of conditions and the following disclaimer.
   13  * 2. Redistributions in binary form must reproduce the above copyright
   14  *    notice, this list of conditions and the following disclaimer in the
   15  *    documentation and/or other materials provided with the distribution.
   16  *
   17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   27  * SUCH DAMAGE.
   28  *
   29  * $FreeBSD: releng/12.0/sys/fs/ext2fs/ext2_htree.c 337453 2018-08-08 12:07:45Z fsu $
   30  */
   31 
   32 #include <sys/param.h>
   33 #include <sys/endian.h>
   34 #include <sys/systm.h>
   35 #include <sys/namei.h>
   36 #include <sys/bio.h>
   37 #include <sys/buf.h>
   38 #include <sys/endian.h>
   39 #include <sys/mount.h>
   40 #include <sys/vnode.h>
   41 #include <sys/malloc.h>
   42 #include <sys/dirent.h>
   43 #include <sys/sysctl.h>
   44 
   45 #include <ufs/ufs/dir.h>
   46 
   47 #include <fs/ext2fs/fs.h>
   48 #include <fs/ext2fs/inode.h>
   49 #include <fs/ext2fs/ext2_mount.h>
   50 #include <fs/ext2fs/ext2fs.h>
   51 #include <fs/ext2fs/fs.h>
   52 #include <fs/ext2fs/ext2_extern.h>
   53 #include <fs/ext2fs/ext2_dinode.h>
   54 #include <fs/ext2fs/ext2_dir.h>
   55 #include <fs/ext2fs/htree.h>
   56 
   57 static void     ext2_append_entry(char *block, uint32_t blksize,
   58                     struct ext2fs_direct_2 *last_entry,
   59                     struct ext2fs_direct_2 *new_entry, int csum_size);
   60 static int      ext2_htree_append_block(struct vnode *vp, char *data,
   61                     struct componentname *cnp, uint32_t blksize);
   62 static int      ext2_htree_check_next(struct inode *ip, uint32_t hash,
   63                     const char *name, struct ext2fs_htree_lookup_info *info);
   64 static int      ext2_htree_cmp_sort_entry(const void *e1, const void *e2);
   65 static int      ext2_htree_find_leaf(struct inode *ip, const char *name,
   66                     int namelen, uint32_t *hash, uint8_t *hash_version,
   67                     struct ext2fs_htree_lookup_info *info);
   68 static uint32_t ext2_htree_get_block(struct ext2fs_htree_entry *ep);
   69 static uint16_t ext2_htree_get_count(struct ext2fs_htree_entry *ep);
   70 static uint32_t ext2_htree_get_hash(struct ext2fs_htree_entry *ep);
   71 static uint16_t ext2_htree_get_limit(struct ext2fs_htree_entry *ep);
   72 static void     ext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level,
   73                     uint32_t hash, uint32_t blk);
   74 static void     ext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info,
   75                     uint32_t hash, uint32_t blk);
   76 static uint32_t ext2_htree_node_limit(struct inode *ip);
   77 static void     ext2_htree_set_block(struct ext2fs_htree_entry *ep,
   78                     uint32_t blk);
   79 static void     ext2_htree_set_count(struct ext2fs_htree_entry *ep,
   80                     uint16_t cnt);
   81 static void     ext2_htree_set_hash(struct ext2fs_htree_entry *ep,
   82                     uint32_t hash);
   83 static void     ext2_htree_set_limit(struct ext2fs_htree_entry *ep,
   84                     uint16_t limit);
   85 static int      ext2_htree_split_dirblock(struct inode *ip,
   86                     char *block1, char *block2, uint32_t blksize,
   87                     uint32_t *hash_seed, uint8_t hash_version,
   88                     uint32_t *split_hash, struct  ext2fs_direct_2 *entry);
   89 static void     ext2_htree_release(struct ext2fs_htree_lookup_info *info);
   90 static uint32_t ext2_htree_root_limit(struct inode *ip, int len);
   91 static int      ext2_htree_writebuf(struct inode *ip,
   92                     struct ext2fs_htree_lookup_info *info);
   93 
   94 int
   95 ext2_htree_has_idx(struct inode *ip)
   96 {
   97         if (EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) &&
   98             ip->i_flag & IN_E3INDEX)
   99                 return (1);
  100         else
  101                 return (0);
  102 }
  103 
  104 static int
  105 ext2_htree_check_next(struct inode *ip, uint32_t hash, const char *name,
  106     struct ext2fs_htree_lookup_info *info)
  107 {
  108         struct vnode *vp = ITOV(ip);
  109         struct ext2fs_htree_lookup_level *level;
  110         struct buf *bp;
  111         uint32_t next_hash;
  112         int idx = info->h_levels_num - 1;
  113         int levels = 0;
  114 
  115         do {
  116                 level = &info->h_levels[idx];
  117                 level->h_entry++;
  118                 if (level->h_entry < level->h_entries +
  119                     ext2_htree_get_count(level->h_entries))
  120                         break;
  121                 if (idx == 0)
  122                         return (0);
  123                 idx--;
  124                 levels++;
  125         } while (1);
  126 
  127         next_hash = ext2_htree_get_hash(level->h_entry);
  128         if ((hash & 1) == 0) {
  129                 if (hash != (next_hash & ~1))
  130                         return (0);
  131         }
  132 
  133         while (levels > 0) {
  134                 levels--;
  135                 if (ext2_blkatoff(vp, ext2_htree_get_block(level->h_entry) *
  136                     ip->i_e2fs->e2fs_bsize, NULL, &bp) != 0)
  137                         return (0);
  138                 level = &info->h_levels[idx + 1];
  139                 brelse(level->h_bp);
  140                 level->h_bp = bp;
  141                 level->h_entry = level->h_entries =
  142                     ((struct ext2fs_htree_node *)bp->b_data)->h_entries;
  143         }
  144 
  145         return (1);
  146 }
  147 
  148 static uint32_t
  149 ext2_htree_get_block(struct ext2fs_htree_entry *ep)
  150 {
  151         return (ep->h_blk & 0x00FFFFFF);
  152 }
  153 
  154 static void
  155 ext2_htree_set_block(struct ext2fs_htree_entry *ep, uint32_t blk)
  156 {
  157         ep->h_blk = blk;
  158 }
  159 
  160 static uint16_t
  161 ext2_htree_get_count(struct ext2fs_htree_entry *ep)
  162 {
  163         return (((struct ext2fs_htree_count *)(ep))->h_entries_num);
  164 }
  165 
  166 static void
  167 ext2_htree_set_count(struct ext2fs_htree_entry *ep, uint16_t cnt)
  168 {
  169         ((struct ext2fs_htree_count *)(ep))->h_entries_num = cnt;
  170 }
  171 
  172 static uint32_t
  173 ext2_htree_get_hash(struct ext2fs_htree_entry *ep)
  174 {
  175         return (ep->h_hash);
  176 }
  177 
  178 static uint16_t
  179 ext2_htree_get_limit(struct ext2fs_htree_entry *ep)
  180 {
  181         return (((struct ext2fs_htree_count *)(ep))->h_entries_max);
  182 }
  183 
  184 static void
  185 ext2_htree_set_hash(struct ext2fs_htree_entry *ep, uint32_t hash)
  186 {
  187         ep->h_hash = hash;
  188 }
  189 
  190 static void
  191 ext2_htree_set_limit(struct ext2fs_htree_entry *ep, uint16_t limit)
  192 {
  193         ((struct ext2fs_htree_count *)(ep))->h_entries_max = limit;
  194 }
  195 
  196 static void
  197 ext2_htree_release(struct ext2fs_htree_lookup_info *info)
  198 {
  199         u_int i;
  200 
  201         for (i = 0; i < info->h_levels_num; i++) {
  202                 struct buf *bp = info->h_levels[i].h_bp;
  203 
  204                 if (bp != NULL)
  205                         brelse(bp);
  206         }
  207 }
  208 
  209 static uint32_t
  210 ext2_htree_root_limit(struct inode *ip, int len)
  211 {
  212         struct m_ext2fs *fs;
  213         uint32_t space;
  214 
  215         fs = ip->i_e2fs;
  216         space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) -
  217             EXT2_DIR_REC_LEN(2) - len;
  218 
  219         if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
  220                 space -= sizeof(struct ext2fs_htree_tail);
  221 
  222         return (space / sizeof(struct ext2fs_htree_entry));
  223 }
  224 
  225 static uint32_t
  226 ext2_htree_node_limit(struct inode *ip)
  227 {
  228         struct m_ext2fs *fs;
  229         uint32_t space;
  230 
  231         fs = ip->i_e2fs;
  232         space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(0);
  233 
  234         if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
  235                 space -= sizeof(struct ext2fs_htree_tail);
  236 
  237         return (space / sizeof(struct ext2fs_htree_entry));
  238 }
  239 
  240 static int
  241 ext2_htree_find_leaf(struct inode *ip, const char *name, int namelen,
  242     uint32_t *hash, uint8_t *hash_ver,
  243     struct ext2fs_htree_lookup_info *info)
  244 {
  245         struct vnode *vp;
  246         struct ext2fs *fs;
  247         struct m_ext2fs *m_fs;
  248         struct buf *bp = NULL;
  249         struct ext2fs_htree_root *rootp;
  250         struct ext2fs_htree_entry *entp, *start, *end, *middle, *found;
  251         struct ext2fs_htree_lookup_level *level_info;
  252         uint32_t hash_major = 0, hash_minor = 0;
  253         uint32_t levels, cnt;
  254         uint8_t hash_version;
  255 
  256         if (name == NULL || info == NULL)
  257                 return (-1);
  258 
  259         vp = ITOV(ip);
  260         fs = ip->i_e2fs->e2fs;
  261         m_fs = ip->i_e2fs;
  262 
  263         if (ext2_blkatoff(vp, 0, NULL, &bp) != 0)
  264                 return (-1);
  265 
  266         info->h_levels_num = 1;
  267         info->h_levels[0].h_bp = bp;
  268         rootp = (struct ext2fs_htree_root *)bp->b_data;
  269         if (rootp->h_info.h_hash_version != EXT2_HTREE_LEGACY &&
  270             rootp->h_info.h_hash_version != EXT2_HTREE_HALF_MD4 &&
  271             rootp->h_info.h_hash_version != EXT2_HTREE_TEA)
  272                 goto error;
  273 
  274         hash_version = rootp->h_info.h_hash_version;
  275         if (hash_version <= EXT2_HTREE_TEA)
  276                 hash_version += m_fs->e2fs_uhash;
  277         *hash_ver = hash_version;
  278 
  279         ext2_htree_hash(name, namelen, fs->e3fs_hash_seed,
  280             hash_version, &hash_major, &hash_minor);
  281         *hash = hash_major;
  282 
  283         if ((levels = rootp->h_info.h_ind_levels) > 1)
  284                 goto error;
  285 
  286         entp = (struct ext2fs_htree_entry *)(((char *)&rootp->h_info) +
  287             rootp->h_info.h_info_len);
  288 
  289         if (ext2_htree_get_limit(entp) !=
  290             ext2_htree_root_limit(ip, rootp->h_info.h_info_len))
  291                 goto error;
  292 
  293         while (1) {
  294                 cnt = ext2_htree_get_count(entp);
  295                 if (cnt == 0 || cnt > ext2_htree_get_limit(entp))
  296                         goto error;
  297 
  298                 start = entp + 1;
  299                 end = entp + cnt - 1;
  300                 while (start <= end) {
  301                         middle = start + (end - start) / 2;
  302                         if (ext2_htree_get_hash(middle) > hash_major)
  303                                 end = middle - 1;
  304                         else
  305                                 start = middle + 1;
  306                 }
  307                 found = start - 1;
  308 
  309                 level_info = &(info->h_levels[info->h_levels_num - 1]);
  310                 level_info->h_bp = bp;
  311                 level_info->h_entries = entp;
  312                 level_info->h_entry = found;
  313                 if (levels == 0)
  314                         return (0);
  315                 levels--;
  316                 if (ext2_blkatoff(vp,
  317                     ext2_htree_get_block(found) * m_fs->e2fs_bsize,
  318                     NULL, &bp) != 0)
  319                         goto error;
  320                 entp = ((struct ext2fs_htree_node *)bp->b_data)->h_entries;
  321                 info->h_levels_num++;
  322                 info->h_levels[info->h_levels_num - 1].h_bp = bp;
  323         }
  324 
  325 error:
  326         ext2_htree_release(info);
  327         return (-1);
  328 }
  329 
  330 /*
  331  * Try to lookup a directory entry in HTree index
  332  */
  333 int
  334 ext2_htree_lookup(struct inode *ip, const char *name, int namelen,
  335     struct buf **bpp, int *entryoffp, doff_t *offp,
  336     doff_t *prevoffp, doff_t *endusefulp,
  337     struct ext2fs_searchslot *ss)
  338 {
  339         struct vnode *vp;
  340         struct ext2fs_htree_lookup_info info;
  341         struct ext2fs_htree_entry *leaf_node;
  342         struct m_ext2fs *m_fs;
  343         struct buf *bp;
  344         uint32_t blk;
  345         uint32_t dirhash;
  346         uint32_t bsize;
  347         uint8_t hash_version;
  348         int search_next;
  349         int found = 0;
  350 
  351         m_fs = ip->i_e2fs;
  352         bsize = m_fs->e2fs_bsize;
  353         vp = ITOV(ip);
  354 
  355         /* TODO: print error msg because we don't lookup '.' and '..' */
  356 
  357         memset(&info, 0, sizeof(info));
  358         if (ext2_htree_find_leaf(ip, name, namelen, &dirhash,
  359             &hash_version, &info))
  360                 return (-1);
  361 
  362         do {
  363                 leaf_node = info.h_levels[info.h_levels_num - 1].h_entry;
  364                 blk = ext2_htree_get_block(leaf_node);
  365                 if (ext2_blkatoff(vp, blk * bsize, NULL, &bp) != 0) {
  366                         ext2_htree_release(&info);
  367                         return (-1);
  368                 }
  369 
  370                 *offp = blk * bsize;
  371                 *entryoffp = 0;
  372                 *prevoffp = blk * bsize;
  373                 *endusefulp = blk * bsize;
  374 
  375                 if (ss->slotstatus == NONE) {
  376                         ss->slotoffset = -1;
  377                         ss->slotfreespace = 0;
  378                 }
  379 
  380                 if (ext2_search_dirblock(ip, bp->b_data, &found,
  381                     name, namelen, entryoffp, offp, prevoffp,
  382                     endusefulp, ss) != 0) {
  383                         brelse(bp);
  384                         ext2_htree_release(&info);
  385                         return (-1);
  386                 }
  387 
  388                 if (found) {
  389                         *bpp = bp;
  390                         ext2_htree_release(&info);
  391                         return (0);
  392                 }
  393 
  394                 brelse(bp);
  395                 search_next = ext2_htree_check_next(ip, dirhash, name, &info);
  396         } while (search_next);
  397 
  398         ext2_htree_release(&info);
  399         return (ENOENT);
  400 }
  401 
  402 static int
  403 ext2_htree_append_block(struct vnode *vp, char *data,
  404     struct componentname *cnp, uint32_t blksize)
  405 {
  406         struct iovec aiov;
  407         struct uio auio;
  408         struct inode *dp = VTOI(vp);
  409         uint64_t cursize, newsize;
  410         int error;
  411 
  412         cursize = roundup(dp->i_size, blksize);
  413         newsize = cursize + blksize;
  414 
  415         auio.uio_offset = cursize;
  416         auio.uio_resid = blksize;
  417         aiov.iov_len = blksize;
  418         aiov.iov_base = data;
  419         auio.uio_iov = &aiov;
  420         auio.uio_iovcnt = 1;
  421         auio.uio_rw = UIO_WRITE;
  422         auio.uio_segflg = UIO_SYSSPACE;
  423         error = VOP_WRITE(vp, &auio, IO_SYNC, cnp->cn_cred);
  424         if (!error)
  425                 dp->i_size = newsize;
  426 
  427         return (error);
  428 }
  429 
  430 static int
  431 ext2_htree_writebuf(struct inode* ip, struct ext2fs_htree_lookup_info *info)
  432 {
  433         int i, error;
  434 
  435         for (i = 0; i < info->h_levels_num; i++) {
  436                 struct buf *bp = info->h_levels[i].h_bp;
  437                 ext2_dx_csum_set(ip, (struct ext2fs_direct_2 *)bp->b_data);
  438                 error = bwrite(bp);
  439                 if (error)
  440                         return (error);
  441         }
  442 
  443         return (0);
  444 }
  445 
  446 static void
  447 ext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level,
  448     uint32_t hash, uint32_t blk)
  449 {
  450         struct ext2fs_htree_entry *target;
  451         int entries_num;
  452 
  453         target = level->h_entry + 1;
  454         entries_num = ext2_htree_get_count(level->h_entries);
  455 
  456         memmove(target + 1, target, (char *)(level->h_entries + entries_num) -
  457             (char *)target);
  458         ext2_htree_set_block(target, blk);
  459         ext2_htree_set_hash(target, hash);
  460         ext2_htree_set_count(level->h_entries, entries_num + 1);
  461 }
  462 
  463 /*
  464  * Insert an index entry to the index node.
  465  */
  466 static void
  467 ext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info,
  468     uint32_t hash, uint32_t blk)
  469 {
  470         struct ext2fs_htree_lookup_level *level;
  471 
  472         level = &info->h_levels[info->h_levels_num - 1];
  473         ext2_htree_insert_entry_to_level(level, hash, blk);
  474 }
  475 
  476 /*
  477  * Compare two entry sort descriptors by name hash value.
  478  * This is used together with qsort.
  479  */
  480 static int
  481 ext2_htree_cmp_sort_entry(const void *e1, const void *e2)
  482 {
  483         const struct ext2fs_htree_sort_entry *entry1, *entry2;
  484 
  485         entry1 = (const struct ext2fs_htree_sort_entry *)e1;
  486         entry2 = (const struct ext2fs_htree_sort_entry *)e2;
  487 
  488         if (entry1->h_hash < entry2->h_hash)
  489                 return (-1);
  490         if (entry1->h_hash > entry2->h_hash)
  491                 return (1);
  492         return (0);
  493 }
  494 
  495 /*
  496  * Append an entry to the end of the directory block.
  497  */
  498 static void
  499 ext2_append_entry(char *block, uint32_t blksize,
  500     struct ext2fs_direct_2 *last_entry,
  501     struct ext2fs_direct_2 *new_entry, int csum_size)
  502 {
  503         uint16_t entry_len;
  504 
  505         entry_len = EXT2_DIR_REC_LEN(last_entry->e2d_namlen);
  506         last_entry->e2d_reclen = entry_len;
  507         last_entry = (struct ext2fs_direct_2 *)((char *)last_entry + entry_len);
  508         new_entry->e2d_reclen = block + blksize - (char *)last_entry - csum_size;
  509         memcpy(last_entry, new_entry, EXT2_DIR_REC_LEN(new_entry->e2d_namlen));
  510 }
  511 
  512 /*
  513  * Move half of entries from the old directory block to the new one.
  514  */
  515 static int
  516 ext2_htree_split_dirblock(struct inode *ip, char *block1, char *block2,
  517     uint32_t blksize, uint32_t *hash_seed, uint8_t hash_version,
  518     uint32_t *split_hash, struct ext2fs_direct_2 *entry)
  519 {
  520         struct m_ext2fs *fs;
  521         int entry_cnt = 0;
  522         int size = 0, csum_size = 0;
  523         int i, k;
  524         uint32_t offset;
  525         uint16_t entry_len = 0;
  526         uint32_t entry_hash;
  527         struct ext2fs_direct_2 *ep, *last;
  528         char *dest;
  529         struct ext2fs_htree_sort_entry *sort_info;
  530 
  531         fs = ip->i_e2fs;
  532         ep = (struct ext2fs_direct_2 *)block1;
  533         dest = block2;
  534         sort_info = (struct ext2fs_htree_sort_entry *)
  535             ((char *)block2 + blksize);
  536 
  537         if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
  538                 csum_size = sizeof(struct ext2fs_direct_tail);
  539 
  540         /*
  541          * Calculate name hash value for the entry which is to be added.
  542          */
  543         ext2_htree_hash(entry->e2d_name, entry->e2d_namlen, hash_seed,
  544             hash_version, &entry_hash, NULL);
  545 
  546         /*
  547          * Fill in directory entry sort descriptors.
  548          */
  549         while ((char *)ep < block1 + blksize - csum_size) {
  550                 if (ep->e2d_ino && ep->e2d_namlen) {
  551                         entry_cnt++;
  552                         sort_info--;
  553                         sort_info->h_size = ep->e2d_reclen;
  554                         sort_info->h_offset = (char *)ep - block1;
  555                         ext2_htree_hash(ep->e2d_name, ep->e2d_namlen,
  556                             hash_seed, hash_version,
  557                             &sort_info->h_hash, NULL);
  558                 }
  559                 ep = (struct ext2fs_direct_2 *)
  560                     ((char *)ep + ep->e2d_reclen);
  561         }
  562 
  563         /*
  564          * Sort directory entry descriptors by name hash value.
  565          */
  566         qsort(sort_info, entry_cnt, sizeof(struct ext2fs_htree_sort_entry),
  567             ext2_htree_cmp_sort_entry);
  568 
  569         /*
  570          * Count the number of entries to move to directory block 2.
  571          */
  572         for (i = entry_cnt - 1; i >= 0; i--) {
  573                 if (sort_info[i].h_size + size > blksize / 2)
  574                         break;
  575                 size += sort_info[i].h_size;
  576         }
  577 
  578         *split_hash = sort_info[i + 1].h_hash;
  579 
  580         /*
  581          * Set collision bit.
  582          */
  583         if (*split_hash == sort_info[i].h_hash)
  584                 *split_hash += 1;
  585 
  586         /*
  587          * Move half of directory entries from block 1 to block 2.
  588          */
  589         for (k = i + 1; k < entry_cnt; k++) {
  590                 ep = (struct ext2fs_direct_2 *)((char *)block1 +
  591                     sort_info[k].h_offset);
  592                 entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen);
  593                 memcpy(dest, ep, entry_len);
  594                 ((struct ext2fs_direct_2 *)dest)->e2d_reclen = entry_len;
  595                 /* Mark directory entry as unused. */
  596                 ep->e2d_ino = 0;
  597                 dest += entry_len;
  598         }
  599         dest -= entry_len;
  600 
  601         /* Shrink directory entries in block 1. */
  602         last = (struct ext2fs_direct_2 *)block1;
  603         entry_len = 0;
  604         for (offset = 0; offset < blksize - csum_size; ) {
  605                 ep = (struct ext2fs_direct_2 *)(block1 + offset);
  606                 offset += ep->e2d_reclen;
  607                 if (ep->e2d_ino) {
  608                         last = (struct ext2fs_direct_2 *)
  609                             ((char *)last + entry_len);
  610                         entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen);
  611                         memcpy((void *)last, (void *)ep, entry_len);
  612                         last->e2d_reclen = entry_len;
  613                 }
  614         }
  615 
  616         if (entry_hash >= *split_hash) {
  617                 /* Add entry to block 2. */
  618                 ext2_append_entry(block2, blksize,
  619                     (struct ext2fs_direct_2 *)dest, entry, csum_size);
  620 
  621                 /* Adjust length field of last entry of block 1. */
  622                 last->e2d_reclen = block1 + blksize - (char *)last - csum_size;
  623         } else {
  624                 /* Add entry to block 1. */
  625                 ext2_append_entry(block1, blksize, last, entry, csum_size);
  626 
  627                 /* Adjust length field of last entry of block 2. */
  628                 ((struct ext2fs_direct_2 *)dest)->e2d_reclen =
  629                     block2 + blksize - dest - csum_size;
  630         }
  631 
  632         if (csum_size) {
  633                 ext2_init_dirent_tail(EXT2_DIRENT_TAIL(block1, blksize));
  634                 ext2_init_dirent_tail(EXT2_DIRENT_TAIL(block2, blksize));
  635         }
  636 
  637         return (0);
  638 }
  639 
  640 /*
  641  * Create an HTree index for a directory
  642  */
  643 int
  644 ext2_htree_create_index(struct vnode *vp, struct componentname *cnp,
  645     struct ext2fs_direct_2 *new_entry)
  646 {
  647         struct buf *bp = NULL;
  648         struct inode *dp;
  649         struct ext2fs *fs;
  650         struct m_ext2fs *m_fs;
  651         struct ext2fs_direct_2 *ep, *dotdot;
  652         struct ext2fs_htree_root *root;
  653         struct ext2fs_htree_lookup_info info;
  654         uint32_t blksize, dirlen, split_hash;
  655         uint8_t hash_version;
  656         char *buf1 = NULL;
  657         char *buf2 = NULL;
  658         int error = 0;
  659 
  660         dp = VTOI(vp);
  661         fs = dp->i_e2fs->e2fs;
  662         m_fs = dp->i_e2fs;
  663         blksize = m_fs->e2fs_bsize;
  664 
  665         buf1 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
  666         buf2 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
  667 
  668         if ((error = ext2_blkatoff(vp, 0, NULL, &bp)) != 0)
  669                 goto out;
  670 
  671         root = (struct ext2fs_htree_root *)bp->b_data;
  672         dotdot = (struct ext2fs_direct_2 *)((char *)&(root->h_dotdot));
  673         ep = (struct ext2fs_direct_2 *)((char *)dotdot + dotdot->e2d_reclen);
  674         dirlen = (char *)root + blksize - (char *)ep;
  675         memcpy(buf1, ep, dirlen);
  676         ep = (struct ext2fs_direct_2 *)buf1;
  677         while ((char *)ep < buf1 + dirlen)
  678                 ep = (struct ext2fs_direct_2 *)
  679                     ((char *)ep + ep->e2d_reclen);
  680         ep->e2d_reclen = buf1 + blksize - (char *)ep;
  681 
  682         dp->i_flag |= IN_E3INDEX;
  683 
  684         /*
  685          * Initialize index root.
  686          */
  687         dotdot->e2d_reclen = blksize - EXT2_DIR_REC_LEN(1);
  688         memset(&root->h_info, 0, sizeof(root->h_info));
  689         root->h_info.h_hash_version = fs->e3fs_def_hash_version;
  690         root->h_info.h_info_len = sizeof(root->h_info);
  691         ext2_htree_set_block(root->h_entries, 1);
  692         ext2_htree_set_count(root->h_entries, 1);
  693         ext2_htree_set_limit(root->h_entries,
  694             ext2_htree_root_limit(dp, sizeof(root->h_info)));
  695 
  696         memset(&info, 0, sizeof(info));
  697         info.h_levels_num = 1;
  698         info.h_levels[0].h_entries = root->h_entries;
  699         info.h_levels[0].h_entry = root->h_entries;
  700 
  701         hash_version = root->h_info.h_hash_version;
  702         if (hash_version <= EXT2_HTREE_TEA)
  703                 hash_version += m_fs->e2fs_uhash;
  704         ext2_htree_split_dirblock(dp, buf1, buf2, blksize, fs->e3fs_hash_seed,
  705             hash_version, &split_hash, new_entry);
  706         ext2_htree_insert_entry(&info, split_hash, 2);
  707 
  708         /*
  709          * Write directory block 0.
  710          */
  711         ext2_dx_csum_set(dp, (struct ext2fs_direct_2 *)bp->b_data);
  712         if (DOINGASYNC(vp)) {
  713                 bdwrite(bp);
  714                 error = 0;
  715         } else {
  716                 error = bwrite(bp);
  717         }
  718         dp->i_flag |= IN_CHANGE | IN_UPDATE;
  719         if (error)
  720                 goto out;
  721 
  722         /*
  723          * Write directory block 1.
  724          */
  725         ext2_dirent_csum_set(dp, (struct ext2fs_direct_2 *)buf1);
  726         error = ext2_htree_append_block(vp, buf1, cnp, blksize);
  727         if (error)
  728                 goto out1;
  729 
  730         /*
  731          * Write directory block 2.
  732          */
  733         ext2_dirent_csum_set(dp, (struct ext2fs_direct_2 *)buf2);
  734         error = ext2_htree_append_block(vp, buf2, cnp, blksize);
  735 
  736         free(buf1, M_TEMP);
  737         free(buf2, M_TEMP);
  738         return (error);
  739 out:
  740         if (bp != NULL)
  741                 brelse(bp);
  742 out1:
  743         free(buf1, M_TEMP);
  744         free(buf2, M_TEMP);
  745         return (error);
  746 }
  747 
  748 /*
  749  * Add an entry to the directory using htree index.
  750  */
  751 int
  752 ext2_htree_add_entry(struct vnode *dvp, struct ext2fs_direct_2 *entry,
  753     struct componentname *cnp)
  754 {
  755         struct ext2fs_htree_entry *entries, *leaf_node;
  756         struct ext2fs_htree_lookup_info info;
  757         struct buf *bp = NULL;
  758         struct ext2fs *fs;
  759         struct m_ext2fs *m_fs;
  760         struct inode *ip;
  761         uint16_t ent_num;
  762         uint32_t dirhash, split_hash;
  763         uint32_t blksize, blknum;
  764         uint64_t cursize, dirsize;
  765         uint8_t hash_version;
  766         char *newdirblock = NULL;
  767         char *newidxblock = NULL;
  768         struct ext2fs_htree_node *dst_node;
  769         struct ext2fs_htree_entry *dst_entries;
  770         struct ext2fs_htree_entry *root_entires;
  771         struct buf *dst_bp = NULL;
  772         int error, write_bp = 0, write_dst_bp = 0, write_info = 0;
  773 
  774         ip = VTOI(dvp);
  775         m_fs = ip->i_e2fs;
  776         fs = m_fs->e2fs;
  777         blksize = m_fs->e2fs_bsize;
  778 
  779         if (ip->i_count != 0)
  780                 return ext2_add_entry(dvp, entry);
  781 
  782         /* Target directory block is full, split it */
  783         memset(&info, 0, sizeof(info));
  784         error = ext2_htree_find_leaf(ip, entry->e2d_name, entry->e2d_namlen,
  785             &dirhash, &hash_version, &info);
  786         if (error)
  787                 return (error);
  788 
  789         entries = info.h_levels[info.h_levels_num - 1].h_entries;
  790         ent_num = ext2_htree_get_count(entries);
  791         if (ent_num == ext2_htree_get_limit(entries)) {
  792                 /* Split the index node. */
  793                 root_entires = info.h_levels[0].h_entries;
  794                 newidxblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
  795                 dst_node = (struct ext2fs_htree_node *)newidxblock;
  796                 memset(&dst_node->h_fake_dirent, 0,
  797                     sizeof(dst_node->h_fake_dirent));
  798                 dst_node->h_fake_dirent.e2d_reclen = blksize;
  799 
  800                 cursize = roundup(ip->i_size, blksize);
  801                 dirsize = cursize + blksize;
  802                 blknum = dirsize / blksize - 1;
  803                 ext2_dx_csum_set(ip, (struct ext2fs_direct_2 *)newidxblock);
  804                 error = ext2_htree_append_block(dvp, newidxblock,
  805                     cnp, blksize);
  806                 if (error)
  807                         goto finish;
  808                 error = ext2_blkatoff(dvp, cursize, NULL, &dst_bp);
  809                 if (error)
  810                         goto finish;
  811                 dst_node = (struct ext2fs_htree_node *)dst_bp->b_data;
  812                 dst_entries = dst_node->h_entries;
  813 
  814                 if (info.h_levels_num == 2) {
  815                         uint16_t src_ent_num, dst_ent_num;
  816 
  817                         if (ext2_htree_get_count(root_entires) ==
  818                             ext2_htree_get_limit(root_entires)) {
  819                                 /* Directory index is full */
  820                                 error = EIO;
  821                                 goto finish;
  822                         }
  823 
  824                         src_ent_num = ent_num / 2;
  825                         dst_ent_num = ent_num - src_ent_num;
  826                         split_hash = ext2_htree_get_hash(entries + src_ent_num);
  827 
  828                         /* Move half of index entries to the new index node */
  829                         memcpy(dst_entries, entries + src_ent_num,
  830                             dst_ent_num * sizeof(struct ext2fs_htree_entry));
  831                         ext2_htree_set_count(entries, src_ent_num);
  832                         ext2_htree_set_count(dst_entries, dst_ent_num);
  833                         ext2_htree_set_limit(dst_entries,
  834                             ext2_htree_node_limit(ip));
  835 
  836                         if (info.h_levels[1].h_entry >= entries + src_ent_num) {
  837                                 struct buf *tmp = info.h_levels[1].h_bp;
  838 
  839                                 info.h_levels[1].h_bp = dst_bp;
  840                                 dst_bp = tmp;
  841 
  842                                 info.h_levels[1].h_entry =
  843                                     info.h_levels[1].h_entry -
  844                                     (entries + src_ent_num) +
  845                                     dst_entries;
  846                                 info.h_levels[1].h_entries = dst_entries;
  847                         }
  848                         ext2_htree_insert_entry_to_level(&info.h_levels[0],
  849                             split_hash, blknum);
  850 
  851                         /* Write new index node to disk */
  852                         ext2_dx_csum_set(ip,
  853                             (struct ext2fs_direct_2 *)dst_bp->b_data);
  854                         error = bwrite(dst_bp);
  855                         ip->i_flag |= IN_CHANGE | IN_UPDATE;
  856                         if (error)
  857                                 goto finish;
  858                         write_dst_bp = 1;
  859                 } else {
  860                         /* Create second level for htree index */
  861                         struct ext2fs_htree_root *idx_root;
  862 
  863                         memcpy(dst_entries, entries,
  864                             ent_num * sizeof(struct ext2fs_htree_entry));
  865                         ext2_htree_set_limit(dst_entries,
  866                             ext2_htree_node_limit(ip));
  867 
  868                         idx_root = (struct ext2fs_htree_root *)
  869                             info.h_levels[0].h_bp->b_data;
  870                         idx_root->h_info.h_ind_levels = 1;
  871 
  872                         ext2_htree_set_count(entries, 1);
  873                         ext2_htree_set_block(entries, blknum);
  874 
  875                         info.h_levels_num = 2;
  876                         info.h_levels[1].h_entries = dst_entries;
  877                         info.h_levels[1].h_entry = info.h_levels[0].h_entry -
  878                             info.h_levels[0].h_entries + dst_entries;
  879                         info.h_levels[1].h_bp = dst_bp;
  880                         dst_bp = NULL;
  881                 }
  882         }
  883 
  884         leaf_node = info.h_levels[info.h_levels_num - 1].h_entry;
  885         blknum = ext2_htree_get_block(leaf_node);
  886         error = ext2_blkatoff(dvp, blknum * blksize, NULL, &bp);
  887         if (error)
  888                 goto finish;
  889 
  890         /* Split target directory block */
  891         newdirblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
  892         ext2_htree_split_dirblock(ip, (char *)bp->b_data, newdirblock, blksize,
  893             fs->e3fs_hash_seed, hash_version, &split_hash, entry);
  894         cursize = roundup(ip->i_size, blksize);
  895         dirsize = cursize + blksize;
  896         blknum = dirsize / blksize - 1;
  897 
  898         /* Add index entry for the new directory block */
  899         ext2_htree_insert_entry(&info, split_hash, blknum);
  900 
  901         /* Write the new directory block to the end of the directory */
  902         ext2_dirent_csum_set(ip, (struct ext2fs_direct_2 *)newdirblock);
  903         error = ext2_htree_append_block(dvp, newdirblock, cnp, blksize);
  904         if (error)
  905                 goto finish;
  906 
  907         /* Write the target directory block */
  908         ext2_dirent_csum_set(ip, (struct ext2fs_direct_2 *)bp->b_data);
  909         error = bwrite(bp);
  910         ip->i_flag |= IN_CHANGE | IN_UPDATE;
  911         if (error)
  912                 goto finish;
  913         write_bp = 1;
  914 
  915         /* Write the index block */
  916         error = ext2_htree_writebuf(ip, &info);
  917         if (!error)
  918                 write_info = 1;
  919 
  920 finish:
  921         if (dst_bp != NULL && !write_dst_bp)
  922                 brelse(dst_bp);
  923         if (bp != NULL && !write_bp)
  924                 brelse(bp);
  925         if (newdirblock != NULL)
  926                 free(newdirblock, M_TEMP);
  927         if (newidxblock != NULL)
  928                 free(newidxblock, M_TEMP);
  929         if (!write_info)
  930                 ext2_htree_release(&info);
  931         return (error);
  932 }

Cache object: aae3da85ad72576e3cb99dff65726dff


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