wimlib.net Git - wimlib/blob - src/inode_table.c

   1 /*
   2  * inode_table.c - hard link detection
   3  */
   4
   5 /*
   6  * Copyright (C) 2012-2016 Eric Biggers
   7  *
   8  * This file is free software; you can redistribute it and/or modify it under
   9  * the terms of the GNU Lesser General Public License as published by the Free
  10  * Software Foundation; either version 3 of the License, or (at your option) any
  11  * later version.
  12  *
  13  * This file is distributed in the hope that it will be useful, but WITHOUT
  14  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  15  * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public License
  19  * along with this file; if not, see http://www.gnu.org/licenses/.
  20  */
  21
  22 #ifdef HAVE_CONFIG_H
  23 #  include "config.h"
  24 #endif
  25
  26 #include "wimlib/bitops.h"
  27 #include "wimlib/dentry.h"
  28 #include "wimlib/error.h"
  29 #include "wimlib/inode.h"
  30 #include "wimlib/inode_table.h"
  31 #include "wimlib/list.h"
  32 #include "wimlib/util.h"
  33
  34 /* Initialize a hash table for hard link detection.  */
  35 int
  36 init_inode_table(struct wim_inode_table *table, size_t capacity)
  37 {
  38         capacity = roundup_pow_of_2(capacity);
  39         table->array = CALLOC(capacity, sizeof(table->array[0]));
  40         if (!table->array)
  41                 return WIMLIB_ERR_NOMEM;
  42         table->filled = 0;
  43         table->capacity = capacity;
  44         INIT_HLIST_HEAD(&table->extra_inodes);
  45         return 0;
  46 }
  47
  48 /* Free the memory allocated by init_inode_table().  */
  49 void
  50 destroy_inode_table(struct wim_inode_table *table)
  51 {
  52         FREE(table->array);
  53 }
  54
  55 /* Double the capacity of the inode hash table.  */
  56 void
  57 enlarge_inode_table(struct wim_inode_table *table)
  58 {
  59         const size_t old_capacity = table->capacity;
  60         const size_t new_capacity = old_capacity * 2;
  61         struct hlist_head *old_array = table->array;
  62         struct hlist_head *new_array;
  63         struct wim_inode *inode;
  64         struct hlist_node *tmp;
  65
  66         new_array = CALLOC(new_capacity, sizeof(struct hlist_head));
  67         if (!new_array)
  68                 return;
  69         table->array = new_array;
  70         table->capacity = new_capacity;
  71         for (size_t i = 0; i < old_capacity; i++) {
  72                 hlist_for_each_entry_safe(inode, tmp, &old_array[i], i_hlist_node) {
  73                         hlist_add_head(&inode->i_hlist_node,
  74                                        &new_array[hash_inode(table, inode->i_ino,
  75                                                              inode->i_devno)]);
  76                 }
  77         }
  78         FREE(old_array);
  79 }
  80
  81 /*
  82  * Allocate a new dentry, with hard link detection.
  83  *
  84  * @table
  85  *      The inode table being used for the current directory scan operation.  It
  86  *      will contain the mapping from (ino, devno) pairs to inodes.
  87  *
  88  * @name
  89  *      The name to give the new dentry.
  90  *
  91  * @ino
  92  *      The inode number of the file, read from the filesystem.
  93  *
  94  * @devno
  95  *      The device number of the file, read from the filesystem.  Proper setting
  96  *      of this parameter prevents cross-device hardlinks from being created.
  97  *      If this is not a problem (perhaps because the current directory scan
  98  *      operation is guaranteed to never traverse a filesystem boundary), then
  99  *      this parameter can just be a fixed value such as 0.
 100  *
 101  * @noshare
 102  *      If %true, the new dentry will not be hard linked to any existing inode,
 103  *      regardless of the values of @ino and @devno.  If %false, normal hard
 104  *      link detection will be done.
 105  *
 106  * @dentry_ret
 107  *      On success, a pointer to the new dentry will be returned in this
 108  *      location.  If i_nlink of the dentry's inode is greater than 1, then this
 109  *      function created a hard link to an existing inode rather than creating a
 110  *      new inode.
 111  *
 112  * On success, returns 0.  On failure, returns WIMLIB_ERR_NOMEM or an error code
 113  * resulting from a failed string conversion.
 114  */
 115 int
 116 inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
 117                        u64 ino, u64 devno, bool noshare,
 118                        struct wim_dentry **dentry_ret)
 119 {
 120         struct wim_dentry *dentry;
 121         struct wim_inode *inode;
 122         struct hlist_head *list;
 123         int ret;
 124
 125         if (noshare) {
 126                 /* No hard link detection  */
 127                 list = &table->extra_inodes;
 128         } else {
 129                 /* Hard link detection  */
 130                 list = &table->array[hash_inode(table, ino, devno)];
 131                 hlist_for_each_entry(inode, list, i_hlist_node) {
 132                         if (inode->i_ino != ino || inode->i_devno != devno)
 133                                 continue;
 134                         if (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) {
 135                                 WARNING("Not honoring directory hard link "
 136                                         "of \"%"TS"\"",
 137                                         inode_any_full_path(inode));
 138                                 continue;
 139                         }
 140                         /* Inode found; use it.  */
 141                         return new_dentry_with_existing_inode(name, inode,
 142                                                               dentry_ret);
 143                 }
 144
 145                 /* Inode not found; create it.  */
 146         }
 147
 148         ret = new_dentry_with_new_inode(name, false, &dentry);
 149         if (ret)
 150                 return ret;
 151         inode = dentry->d_inode;
 152         inode->i_ino = ino;
 153         inode->i_devno = devno;
 154         hlist_add_head(&inode->i_hlist_node, list);
 155         if (list != &table->extra_inodes)
 156                 if (++table->filled > table->capacity)
 157                         enlarge_inode_table(table);
 158         *dentry_ret = dentry;
 159         return 0;
 160 }
 161
 162 /*
 163  * Following the allocation of dentries with hard link detection using
 164  * inode_table_new_dentry(), this function will assign consecutive inode numbers
 165  * to the new set of inodes.  It will also append the list of new inodes to the
 166  * list @head, which must contain any inodes already existing in the WIM image.
 167  */
 168 void
 169 inode_table_prepare_inode_list(struct wim_inode_table *table,
 170                                struct hlist_head *head)
 171 {
 172         struct wim_inode *inode;
 173         struct hlist_node *tmp;
 174         u64 cur_ino = 1;
 175
 176         /* Re-assign inode numbers in the existing list to avoid duplicates. */
 177         hlist_for_each_entry(inode, head, i_hlist_node)
 178                 inode->i_ino = cur_ino++;
 179
 180         /* Assign inode numbers to the new inodes and move them to the image's
 181          * inode list. */
 182         for (size_t i = 0; i < table->capacity; i++) {
 183                 hlist_for_each_entry_safe(inode, tmp, &table->array[i], i_hlist_node) {
 184                         inode->i_ino = cur_ino++;
 185                         hlist_add_head(&inode->i_hlist_node, head);
 186                 }
 187         }
 188         hlist_for_each_entry_safe(inode, tmp, &table->extra_inodes, i_hlist_node) {
 189                 inode->i_ino = cur_ino++;
 190                 hlist_add_head(&inode->i_hlist_node, head);
 191         }
 192 }