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

   1 /*
   2  * inode_fixup.c
   3  */
   4
   5 /*
   6  * Copyright (C) 2012, 2013, 2014 Eric Biggers
   7  *
   8  * This file is part of wimlib, a library for working with WIM files.
   9  *
  10  * wimlib is free software; you can redistribute it and/or modify it under the
  11  * terms of the GNU General Public License as published by the Free
  12  * Software Foundation; either version 3 of the License, or (at your option)
  13  * any later version.
  14  *
  15  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
  16  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  17  * A PARTICULAR PURPOSE. See the GNU General Public License for more
  18  * details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with wimlib; if not, see http://www.gnu.org/licenses/.
  22  */
  23
  24 #ifdef HAVE_CONFIG_H
  25 #  include "config.h"
  26 #endif
  27
  28 #include "wimlib/dentry.h"
  29 #include "wimlib/error.h"
  30 #include "wimlib/inode.h"
  31 #include "wimlib/inode_table.h"
  32 #include "wimlib/lookup_table.h"
  33
  34 struct inode_fixup_params {
  35         struct wim_inode_table inode_table;
  36         unsigned long num_dir_hard_links;
  37         unsigned long num_inconsistent_inodes;
  38 };
  39
  40 #define MAX_DIR_HARD_LINK_WARNINGS 8
  41
  42 static bool
  43 ads_entries_have_same_name(const struct wim_ads_entry *entry_1,
  44                            const struct wim_ads_entry *entry_2)
  45 {
  46         return entry_1->stream_name_nbytes == entry_2->stream_name_nbytes &&
  47                 !memcmp(entry_1->stream_name, entry_2->stream_name,
  48                         entry_1->stream_name_nbytes);
  49 }
  50
  51 static bool
  52 inodes_consistent(const struct wim_inode *inode_1,
  53                   const struct wim_inode *inode_2)
  54 {
  55         if (inode_1->i_num_ads != inode_2->i_num_ads)
  56                 return false;
  57
  58         for (u32 i = 0; i <= inode_1->i_num_ads; i++) {
  59                 const u8 *hash_1 = inode_stream_hash_unresolved(inode_1, i);
  60                 const u8 *hash_2 = inode_stream_hash_unresolved(inode_2, i);
  61
  62                 if (!hashes_equal(hash_1, hash_2) && !is_zero_hash(hash_1))
  63                         return false;
  64
  65                 if (i && !ads_entries_have_same_name(&inode_1->i_ads_entries[i - 1],
  66                                                      &inode_2->i_ads_entries[i - 1]))
  67                         return false;
  68         }
  69
  70         if (inode_1->i_attributes != inode_2->i_attributes)
  71                 return false;
  72
  73         if (inode_1->i_security_id != inode_2->i_security_id)
  74                 return false;
  75
  76         return true;
  77 }
  78
  79 static int
  80 inode_table_insert(struct wim_dentry *dentry, void *_params)
  81 {
  82         struct inode_fixup_params *params = _params;
  83         struct wim_inode_table *table = &params->inode_table;
  84         struct wim_inode *d_inode = dentry->d_inode;
  85         size_t pos;
  86         struct wim_inode *inode;
  87         struct hlist_node *cur;
  88
  89         if (d_inode->i_ino == 0) {
  90                 list_add_tail(&d_inode->i_list, &table->extra_inodes);
  91                 return 0;
  92         }
  93
  94         /* Try adding this dentry to an existing inode.  */
  95         pos = d_inode->i_ino % table->capacity;
  96         hlist_for_each_entry(inode, cur, &table->array[pos], i_hlist) {
  97                 if (inode->i_ino != d_inode->i_ino) {
  98                         continue;
  99                 }
 100                 if (unlikely(!inodes_consistent(inode, d_inode))) {
 101                         params->num_inconsistent_inodes++;
 102                         continue;
 103                 }
 104                 if (unlikely(d_inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY)) {
 105                         params->num_dir_hard_links++;
 106                         if (params->num_dir_hard_links <=
 107                             MAX_DIR_HARD_LINK_WARNINGS)
 108                         {
 109                                 WARNING("Unsupported directory hard link "
 110                                         "\"%"TS"\" <=> \"%"TS"\"",
 111                                         dentry_full_path(dentry),
 112                                         inode_first_full_path(inode));
 113                         } else if (params->num_dir_hard_links ==
 114                                    MAX_DIR_HARD_LINK_WARNINGS + 1)
 115                         {
 116                                 WARNING("Suppressing additional warnings about "
 117                                         "directory hard links...");
 118                         }
 119                         continue;
 120                 }
 121                 /* Transfer this dentry to the existing inode.  */
 122                 free_inode(d_inode);
 123                 dentry->d_inode = inode;
 124                 inode->i_nlink++;
 125                 inode_add_dentry(dentry, inode);
 126                 return 0;
 127         }
 128
 129         /* Keep this dentry's inode.  */
 130         hlist_add_head(&d_inode->i_hlist, &table->array[pos]);
 131         return 0;
 132 }
 133
 134 /* Move the inodes from the 'struct wim_inode_table' to the 'inode_list'.  */
 135 static void
 136 build_inode_list(struct wim_inode_table *inode_table,
 137                  struct list_head *inode_list)
 138 {
 139         list_splice(&inode_table->extra_inodes, inode_list);
 140         for (size_t i = 0; i < inode_table->capacity; i++) {
 141                 while (!hlist_empty(&inode_table->array[i])) {
 142                         struct wim_inode *inode;
 143
 144                         inode = hlist_entry(inode_table->array[i].first,
 145                                             struct wim_inode, i_hlist);
 146                         hlist_del(&inode->i_hlist);
 147                         list_add(&inode->i_list, inode_list);
 148                 }
 149         }
 150 }
 151
 152 /* Re-assign inode numbers to the inodes in the list.  */
 153 static void
 154 reassign_inode_numbers(struct list_head *inode_list)
 155 {
 156         struct wim_inode *inode;
 157         u64 cur_ino = 1;
 158
 159         list_for_each_entry(inode, inode_list, i_list)
 160                 inode->i_ino = cur_ino++;
 161 }
 162
 163 /*
 164  * Given a WIM image's tree of dentries such that each dentry initially
 165  * has a unique inode associated with it, determine the actual
 166  * dentry/inode information.  Following this, a single inode may be named
 167  * by more than one dentry (usually called a hard link).
 168  *
 169  * The 'hard_link_group_id' field of the on-disk WIM dentry, which we
 170  * have read into 'i_ino' of each dentry's initial inode, determines
 171  * which dentries share the same inode.  Ideally, dentries share the same
 172  * inode if and only if they have the same value in this field.  However,
 173  * exceptions apply:
 174  *
 175  * - If 'hard_link_group_id' is 0, the corresponding dentry is the sole
 176  *   name for its inode.
 177  * - Due to bugs in the Microsoft implementation, dentries with different
 178  *   'hard_link_group_id' fields may, in fact, need to be interpreted as
 179  *   naming different inodes.  This seems to mostly affect images in
 180  *   install.wim for Windows 7.  I still have not been able to determine
 181  *   precisely how Microsoft's implementation generates and handles this
 182  *   invalid case, but we can at least try doing something reasonable by
 183  *   only joining a dentry with a different inode when this would not
 184  *   change the file's meaning (e.g. its contents or attributes).
 185  *
 186  * Returns 0 or WIMLIB_ERR_NOMEM.  On success, the resulting inodes will be
 187  * appended to the @inode_list, and they will have consistent numbers in their
 188  * i_ino fields.
 189  */
 190 int
 191 dentry_tree_fix_inodes(struct wim_dentry *root, struct list_head *inode_list)
 192 {
 193         struct inode_fixup_params params;
 194         int ret;
 195
 196         /* We use a hash table to map inode numbers to inodes.  */
 197
 198         ret = init_inode_table(&params.inode_table, 9001);
 199         if (ret)
 200                 return ret;
 201
 202         params.num_dir_hard_links = 0;
 203         params.num_inconsistent_inodes = 0;
 204
 205         for_dentry_in_tree(root, inode_table_insert, &params);
 206
 207         /* Generate the resulting list of inodes, and if needed reassign
 208          * the inode numbers.  */
 209         build_inode_list(&params.inode_table, inode_list);
 210         destroy_inode_table(&params.inode_table);
 211
 212         if (unlikely(params.num_inconsistent_inodes))
 213                 WARNING("Fixed %lu invalid hard links in WIM image",
 214                         params.num_inconsistent_inodes);
 215
 216         if (unlikely(params.num_dir_hard_links))
 217                 WARNING("Ignoring %lu directory hard links",
 218                         params.num_dir_hard_links);
 219
 220         if (unlikely(params.num_inconsistent_inodes ||
 221                      params.num_dir_hard_links))
 222                 reassign_inode_numbers(inode_list);
 223         return 0;
 224 }