inode_table: make the inode table resizable
[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
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 = hash_inode(table, d_inode->i_ino, 0);
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         if (++table->filled > table->capacity)
112                 enlarge_inode_table(table);
113         return 0;
114 }
115
116 static void
117 hlist_move_all(struct hlist_head *src, struct hlist_head *dest)
118 {
119         struct hlist_node *node;
120
121         while ((node = src->first) != NULL) {
122                 hlist_del(node);
123                 hlist_add_head(node, dest);
124         }
125 }
126
127 /* Move the inodes from the 'struct wim_inode_table' to the 'inode_list'.  */
128 static void
129 build_inode_list(struct wim_inode_table *inode_table,
130                  struct hlist_head *inode_list)
131 {
132         hlist_move_all(&inode_table->extra_inodes, inode_list);
133         for (size_t i = 0; i < inode_table->capacity; i++)
134                 hlist_move_all(&inode_table->array[i], inode_list);
135 }
136
137 /* Re-assign inode numbers to the inodes in the list.  */
138 static void
139 reassign_inode_numbers(struct hlist_head *inode_list)
140 {
141         struct wim_inode *inode;
142         u64 cur_ino = 1;
143
144         hlist_for_each_entry(inode, inode_list, i_hlist_node)
145                 inode->i_ino = cur_ino++;
146 }
147
148 /*
149  * Given a WIM image's tree of dentries such that each dentry initially
150  * has a unique inode associated with it, determine the actual
151  * dentry/inode information.  Following this, a single inode may be named
152  * by more than one dentry (usually called a hard link).
153  *
154  * The 'hard_link_group_id' field of the on-disk WIM dentry, which we
155  * have read into 'i_ino' of each dentry's initial inode, determines
156  * which dentries share the same inode.  Ideally, dentries share the same
157  * inode if and only if they have the same value in this field.  However,
158  * exceptions apply:
159  *
160  * - If 'hard_link_group_id' is 0, the corresponding dentry is the sole
161  *   name for its inode.
162  * - Due to bugs in the Microsoft implementation, dentries with different
163  *   'hard_link_group_id' fields may, in fact, need to be interpreted as
164  *   naming different inodes.  This seems to mostly affect images in
165  *   install.wim for Windows 7.  I try to work around this in the same way
166  *   the Microsoft implementation works around this.
167  *
168  * Returns 0 or WIMLIB_ERR_NOMEM.  On success, the resulting inodes will be
169  * appended to the @inode_list, and they will have consistent numbers in their
170  * i_ino fields.
171  */
172 int
173 dentry_tree_fix_inodes(struct wim_dentry *root, struct hlist_head *inode_list)
174 {
175         struct inode_fixup_params params;
176         int ret;
177
178         /* We use a hash table to map inode numbers to inodes.  */
179
180         ret = init_inode_table(&params.inode_table, 64);
181         if (ret)
182                 return ret;
183
184         params.num_dir_hard_links = 0;
185         params.num_inconsistent_inodes = 0;
186
187         for_dentry_in_tree(root, inode_table_insert, &params);
188
189         /* Generate the resulting list of inodes, and if needed reassign
190          * the inode numbers.  */
191         build_inode_list(&params.inode_table, inode_list);
192         destroy_inode_table(&params.inode_table);
193
194         if (unlikely(params.num_inconsistent_inodes))
195                 WARNING("Fixed %lu invalid hard links in WIM image",
196                         params.num_inconsistent_inodes);
197
198         if (unlikely(params.num_dir_hard_links))
199                 WARNING("Ignoring %lu directory hard links",
200                         params.num_dir_hard_links);
201
202         if (unlikely(params.num_inconsistent_inodes ||
203                      params.num_dir_hard_links))
204                 reassign_inode_numbers(inode_list);
205         return 0;
206 }