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 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
  31 struct inode_fixup_params {
  32         struct wim_inode_table inode_table;
  33         unsigned long num_dir_hard_links;
  34         unsigned long num_inconsistent_inodes;
  35 };
  36
  37 #define MAX_DIR_HARD_LINK_WARNINGS 8
  38
  39 static bool
  40 inodes_consistent(const struct wim_inode *inode_1,
  41                   const struct wim_inode *inode_2)
  42 {
  43         /* This certainly isn't the only thing we need to check to make sure the
  44          * inodes are consistent.  However, this seems to be the only thing that
  45          * the MS implementation checks when working around its own bug.
  46          *
  47          * (Tested: If two dentries share the same hard link group ID, Windows
  48          * 8.1 DISM will link them if they have the same unnamed stream hash,
  49          * even if the dentries provide different timestamps, attributes,
  50          * alternate data streams, and security IDs!  And the one that gets used
  51          * will change if you merely swap the filenames.  But if you use
  52          * different unnamed stream hashes with everything else the same, it
  53          * doesn't link the dentries.)
  54          *
  55          * For non-buggy WIMs this function will always return true.  */
  56         return hashes_equal(inode_get_hash_of_unnamed_data_stream(inode_1),
  57                             inode_get_hash_of_unnamed_data_stream(inode_2));
  58 }
  59
  60 static int
  61 inode_table_insert(struct wim_dentry *dentry, void *_params)
  62 {
  63         struct inode_fixup_params *params = _params;
  64         struct wim_inode_table *table = &params->inode_table;
  65         struct wim_inode *d_inode = dentry->d_inode;
  66         size_t pos;
  67         struct wim_inode *inode;
  68
  69         if (d_inode->i_ino == 0) {
  70                 hlist_add_head(&d_inode->i_hlist_node, &table->extra_inodes);
  71                 return 0;
  72         }
  73
  74         /* Try adding this dentry to an existing inode.  */
  75         pos = d_inode->i_ino % table->capacity;
  76         hlist_for_each_entry(inode, &table->array[pos], i_hlist_node) {
  77                 if (inode->i_ino != d_inode->i_ino) {
  78                         continue;
  79                 }
  80                 if (unlikely(!inodes_consistent(inode, d_inode))) {
  81                         params->num_inconsistent_inodes++;
  82                         continue;
  83                 }
  84                 if (unlikely((d_inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) ||
  85                              (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY)))
  86                 {
  87                         params->num_dir_hard_links++;
  88                         if (params->num_dir_hard_links <=
  89                             MAX_DIR_HARD_LINK_WARNINGS)
  90                         {
  91                                 WARNING("Unsupported directory hard link "
  92                                         "\"%"TS"\" <=> \"%"TS"\"",
  93                                         dentry_full_path(dentry),
  94                                         inode_any_full_path(inode));
  95                         } else if (params->num_dir_hard_links ==
  96                                    MAX_DIR_HARD_LINK_WARNINGS + 1)
  97                         {
  98                                 WARNING("Suppressing additional warnings about "
  99                                         "directory hard links...");
 100                         }
 101                         continue;
 102                 }
 103                 /* Transfer this dentry to the existing inode.  */
 104                 d_disassociate(dentry);
 105                 d_associate(dentry, inode);
 106                 return 0;
 107         }
 108
 109         /* Keep this dentry's inode.  */
 110         hlist_add_head(&d_inode->i_hlist_node, &table->array[pos]);
 111         return 0;
 112 }
 113
 114 static void
 115 hlist_move_all(struct hlist_head *src, struct hlist_head *dest)
 116 {
 117         struct hlist_node *node;
 118
 119         while ((node = src->first) != NULL) {
 120                 hlist_del(node);
 121                 hlist_add_head(node, dest);
 122         }
 123 }
 124
 125 /* Move the inodes from the 'struct wim_inode_table' to the 'inode_list'.  */
 126 static void
 127 build_inode_list(struct wim_inode_table *inode_table,
 128                  struct hlist_head *inode_list)
 129 {
 130         hlist_move_all(&inode_table->extra_inodes, inode_list);
 131         for (size_t i = 0; i < inode_table->capacity; i++)
 132                 hlist_move_all(&inode_table->array[i], inode_list);
 133 }
 134
 135 /* Re-assign inode numbers to the inodes in the list.  */
 136 static void
 137 reassign_inode_numbers(struct hlist_head *inode_list)
 138 {
 139         struct wim_inode *inode;
 140         u64 cur_ino = 1;
 141
 142         hlist_for_each_entry(inode, inode_list, i_hlist_node)
 143                 inode->i_ino = cur_ino++;
 144 }
 145
 146 /*
 147  * Given a WIM image's tree of dentries such that each dentry initially
 148  * has a unique inode associated with it, determine the actual
 149  * dentry/inode information.  Following this, a single inode may be named
 150  * by more than one dentry (usually called a hard link).
 151  *
 152  * The 'hard_link_group_id' field of the on-disk WIM dentry, which we
 153  * have read into 'i_ino' of each dentry's initial inode, determines
 154  * which dentries share the same inode.  Ideally, dentries share the same
 155  * inode if and only if they have the same value in this field.  However,
 156  * exceptions apply:
 157  *
 158  * - If 'hard_link_group_id' is 0, the corresponding dentry is the sole
 159  *   name for its inode.
 160  * - Due to bugs in the Microsoft implementation, dentries with different
 161  *   'hard_link_group_id' fields may, in fact, need to be interpreted as
 162  *   naming different inodes.  This seems to mostly affect images in
 163  *   install.wim for Windows 7.  I try to work around this in the same way
 164  *   the Microsoft implementation works around this.
 165  *
 166  * Returns 0 or WIMLIB_ERR_NOMEM.  On success, the resulting inodes will be
 167  * appended to the @inode_list, and they will have consistent numbers in their
 168  * i_ino fields.
 169  */
 170 int
 171 dentry_tree_fix_inodes(struct wim_dentry *root, struct hlist_head *inode_list)
 172 {
 173         struct inode_fixup_params params;
 174         int ret;
 175
 176         /* We use a hash table to map inode numbers to inodes.  */
 177
 178         ret = init_inode_table(&params.inode_table, 9001);
 179         if (ret)
 180                 return ret;
 181
 182         params.num_dir_hard_links = 0;
 183         params.num_inconsistent_inodes = 0;
 184
 185         for_dentry_in_tree(root, inode_table_insert, &params);
 186
 187         /* Generate the resulting list of inodes, and if needed reassign
 188          * the inode numbers.  */
 189         build_inode_list(&params.inode_table, inode_list);
 190         destroy_inode_table(&params.inode_table);
 191
 192         if (unlikely(params.num_inconsistent_inodes))
 193                 WARNING("Fixed %lu invalid hard links in WIM image",
 194                         params.num_inconsistent_inodes);
 195
 196         if (unlikely(params.num_dir_hard_links))
 197                 WARNING("Ignoring %lu directory hard links",
 198                         params.num_dir_hard_links);
 199
 200         if (unlikely(params.num_inconsistent_inodes ||
 201                      params.num_dir_hard_links))
 202                 reassign_inode_numbers(inode_list);
 203         return 0;
 204 }