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

   1 /*
   2  * inode_table.c - hard link detection
   3  */
   4
   5 /*
   6  * Copyright (C) 2012, 2013, 2014 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/dentry.h"
  27 #include "wimlib/error.h"
  28 #include "wimlib/inode.h"
  29 #include "wimlib/inode_table.h"
  30 #include "wimlib/list.h"
  31 #include "wimlib/util.h"
  32
  33 /* Initialize a hash table for hard link detection.  */
  34 int
  35 init_inode_table(struct wim_inode_table *table, size_t capacity)
  36 {
  37         table->array = CALLOC(capacity, sizeof(table->array[0]));
  38         if (!table->array)
  39                 return WIMLIB_ERR_NOMEM;
  40         table->num_entries = 0;
  41         table->capacity = capacity;
  42         INIT_HLIST_HEAD(&table->extra_inodes);
  43         return 0;
  44 }
  45
  46 /* Free the memory allocated by init_inode_table().  */
  47 void
  48 destroy_inode_table(struct wim_inode_table *table)
  49 {
  50         FREE(table->array);
  51 }
  52
  53 /*
  54  * Allocate a new dentry, with hard link detection.
  55  *
  56  * @table
  57  *      The inode table being used for the current directory scan operation.  It
  58  *      will contain the mapping from (ino, devno) pairs to inodes.
  59  *
  60  * @name
  61  *      The name to give the new dentry.
  62  *
  63  * @ino
  64  *      The inode number of the file, read from the filesystem.
  65  *
  66  * @devno
  67  *      The device number of the file, read from the filesystem.  Proper setting
  68  *      of this parameter prevents cross-device hardlinks from being created.
  69  *      If this is not a problem (perhaps because the current directory scan
  70  *      operation is guaranteed to never traverse a filesystem boundary), then
  71  *      this parameter can just be a fixed value such as 0.
  72  *
  73  * @noshare
  74  *      If %true, the new dentry will not be hard linked to any existing inode,
  75  *      regardless of the values of @ino and @devno.  If %false, normal hard
  76  *      link detection will be done.
  77  *
  78  * @dentry_ret
  79  *      On success, a pointer to the new dentry will be returned in this
  80  *      location.  If i_nlink of the dentry's inode is greater than 1, then this
  81  *      function created a hard link to an existing inode rather than creating a
  82  *      new inode.
  83  *
  84  * On success, returns 0.  On failure, returns WIMLIB_ERR_NOMEM or an error code
  85  * resulting from a failed string conversion.
  86  */
  87 int
  88 inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
  89                        u64 ino, u64 devno, bool noshare,
  90                        struct wim_dentry **dentry_ret)
  91 {
  92         struct wim_dentry *dentry;
  93         struct wim_inode *inode;
  94         struct hlist_head *list;
  95         int ret;
  96
  97         if (noshare) {
  98                 /* No hard link detection  */
  99                 list = &table->extra_inodes;
 100         } else {
 101                 /* Hard link detection  */
 102                 list = &table->array[hash_u64(hash_u64(ino) + hash_u64(devno))
 103                                      % table->capacity];
 104                 hlist_for_each_entry(inode, list, i_hlist_node) {
 105                         if (inode->i_ino != ino || inode->i_devno != devno)
 106                                 continue;
 107                         if (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) {
 108                                 WARNING("Not honoring directory hard link "
 109                                         "of \"%"TS"\"",
 110                                         inode_any_full_path(inode));
 111                                 continue;
 112                         }
 113                         /* Inode found; use it.  */
 114                         return new_dentry_with_existing_inode(name, inode,
 115                                                               dentry_ret);
 116                 }
 117
 118                 /* Inode not found; create it.  */
 119                 table->num_entries++;
 120         }
 121
 122         ret = new_dentry_with_new_inode(name, false, &dentry);
 123         if (ret)
 124                 return ret;
 125         inode = dentry->d_inode;
 126         hlist_add_head(&inode->i_hlist_node, list);
 127         inode->i_ino = ino;
 128         inode->i_devno = devno;
 129         *dentry_ret = dentry;
 130         return 0;
 131 }
 132
 133 /*
 134  * Following the allocation of dentries with hard link detection using
 135  * inode_table_new_dentry(), this function will assign consecutive inode numbers
 136  * to the new set of inodes.  It will also append the list of new inodes to the
 137  * list @head, which must contain any inodes already existing in the WIM image.
 138  */
 139 void
 140 inode_table_prepare_inode_list(struct wim_inode_table *table,
 141                                struct hlist_head *head)
 142 {
 143         struct wim_inode *inode;
 144         struct hlist_node *tmp;
 145         u64 cur_ino = 1;
 146
 147         /* Re-assign inode numbers in the existing list to avoid duplicates. */
 148         hlist_for_each_entry(inode, head, i_hlist_node)
 149                 inode->i_ino = cur_ino++;
 150
 151         /* Assign inode numbers to the new inodes and move them to the image's
 152          * inode list. */
 153         for (size_t i = 0; i < table->capacity; i++) {
 154                 hlist_for_each_entry_safe(inode, tmp, &table->array[i], i_hlist_node) {
 155                         inode->i_ino = cur_ino++;
 156                         hlist_add_head(&inode->i_hlist_node, head);
 157                 }
 158                 INIT_HLIST_HEAD(&table->array[i]);
 159         }
 160         hlist_for_each_entry_safe(inode, tmp, &table->extra_inodes, i_hlist_node) {
 161                 inode->i_ino = cur_ino++;
 162                 hlist_add_head(&inode->i_hlist_node, head);
 163         }
 164         INIT_HLIST_HEAD(&table->extra_inodes);
 165         table->num_entries = 0;
 166 }