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