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-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

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

Cache object: 49f18fa598ce08fdfd9cfc14badc6f0f


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