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_LIST_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 static struct wim_inode *
  54 inode_table_get_inode(struct wim_inode_table *table, u64 ino, u64 devno)
  55 {
  56         size_t pos;
  57         struct wim_inode *inode;
  58         struct hlist_node *cur;
  59
  60         /* Search for an existing inode having the same inode number and device
  61          * number.  */
  62         pos = hash_u64(hash_u64(ino) + hash_u64(devno)) % table->capacity;
  63         hlist_for_each_entry(inode, cur, &table->array[pos], i_hlist) {
  64                 if (inode->i_ino == ino && inode->i_devno == devno) {
  65                         /* Found; use the existing inode.  */
  66                         inode->i_nlink++;
  67                         return inode;
  68                 }
  69         }
  70
  71         /* Create a new inode and insert it into the table.  */
  72         inode = new_timeless_inode();
  73         if (inode) {
  74                 inode->i_ino = ino;
  75                 inode->i_devno = devno;
  76                 hlist_add_head(&inode->i_hlist, &table->array[pos]);
  77                 table->num_entries++;
  78         }
  79         return inode;
  80 }
  81
  82 /*
  83  * Allocate a new dentry, with hard link detection.
  84  *
  85  * @table
  86  *      The inode table being used for the current directory scan operation.  It
  87  *      will contain the mapping from (ino, devno) pairs to inodes.
  88  *
  89  * @name
  90  *      The name to give the new dentry.
  91  *
  92  * @ino
  93  *      The inode number of the file, read from the filesystem.
  94  *
  95  * @devno
  96  *      The device number of the file, read from the filesystem.  Proper setting
  97  *      of this parameter prevents cross-device hardlinks from being created.
  98  *      If this is not a problem (perhaps because the current directory scan
  99  *      operation is guaranteed to never traverse a filesystem boundary), then
 100  *      this parameter can just be a fixed value such as 0.
 101  *
 102  * @noshare
 103  *      If %true, the new dentry will not be hard linked to any existing inode,
 104  *      regardless of the values of @ino and @devno.  If %false, normal hard
 105  *      link detection will be done.
 106  *
 107  * @dentry_ret
 108  *      On success, a pointer to the new dentry will be returned in this
 109  *      location.  If i_nlink of the dentry's inode is greater than 1, then this
 110  *      function created a hard link to an existing inode rather than creating a
 111  *      new inode.
 112  *
 113  * On success, returns 0.  On failure, returns WIMLIB_ERR_NOMEM or an error code
 114  * resulting from a failed string conversion.
 115  */
 116 int
 117 inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
 118                        u64 ino, u64 devno, bool noshare,
 119                        struct wim_dentry **dentry_ret)
 120 {
 121         struct wim_dentry *dentry;
 122         struct wim_inode *inode;
 123         int ret;
 124
 125         if (noshare) {
 126                 /* File that cannot be hardlinked--- Return a new inode with its
 127                  * inode and device numbers left at 0. */
 128                 ret = new_dentry_with_timeless_inode(name, &dentry);
 129                 if (ret)
 130                         return ret;
 131                 list_add_tail(&dentry->d_inode->i_list, &table->extra_inodes);
 132         } else {
 133                 /* File that can be hardlinked--- search the table for an
 134                  * existing inode matching the inode number and device;
 135                  * otherwise create a new inode. */
 136                 ret = new_dentry(name, &dentry);
 137                 if (ret)
 138                         return ret;
 139                 inode = inode_table_get_inode(table, ino, devno);
 140                 if (!inode) {
 141                         free_dentry(dentry);
 142                         return WIMLIB_ERR_NOMEM;
 143                 }
 144                 /* If using an existing inode, we need to gain a reference to
 145                  * each of its streams. */
 146                 if (inode->i_nlink > 1)
 147                         inode_ref_streams(inode);
 148                 dentry->d_inode = inode;
 149                 inode_add_dentry(dentry, inode);
 150         }
 151         *dentry_ret = dentry;
 152         return 0;
 153 }
 154
 155 /*
 156  * Following the allocation of dentries with hard link detection using
 157  * inode_table_new_dentry(), this function will assign consecutive inode numbers
 158  * to the new set of inodes.  It will also append the list of new inodes to the
 159  * list @head, which must contain any inodes already existing in the WIM image.
 160  */
 161 void
 162 inode_table_prepare_inode_list(struct wim_inode_table *table,
 163                                struct list_head *head)
 164 {
 165         struct wim_inode *inode, *tmp_inode;
 166         struct hlist_node *cur, *tmp;
 167         u64 cur_ino = 1;
 168
 169         /* Re-assign inode numbers in the existing list to avoid duplicates. */
 170         list_for_each_entry(inode, head, i_list)
 171                 inode->i_ino = cur_ino++;
 172
 173         /* Assign inode numbers to the new inodes and move them to the image's
 174          * inode list. */
 175         for (size_t i = 0; i < table->capacity; i++) {
 176                 hlist_for_each_entry_safe(inode, cur, tmp, &table->array[i], i_hlist)
 177                 {
 178                         inode->i_ino = cur_ino++;
 179                         inode->i_devno = 0;
 180                         list_add_tail(&inode->i_list, head);
 181                 }
 182                 INIT_HLIST_HEAD(&table->array[i]);
 183         }
 184         list_for_each_entry_safe(inode, tmp_inode, &table->extra_inodes, i_list)
 185         {
 186                 inode->i_ino = cur_ino++;
 187                 inode->i_devno = 0;
 188                 list_add_tail(&inode->i_list, head);
 189         }
 190         INIT_LIST_HEAD(&table->extra_inodes);
 191         table->num_entries = 0;
 192 }