Align security data correctly
[wimlib] / src / hardlink.c
1 /*
2  * hardlink.c
3  *
4  * Code to deal with hard links in WIMs.  Essentially, the WIM dentries are put
5  * into a hash table indexed by the hard link group ID field, then for each hard
6  * link group, a linked list is made to connect the dentries.
7  */
8
9 /*
10  * Copyright (C) 2012 Eric Biggers
11  *
12  * This file is part of wimlib, a library for working with WIM files.
13  *
14  * wimlib is free software; you can redistribute it and/or modify it under the
15  * terms of the GNU Lesser General Public License as published by the Free
16  * Software Foundation; either version 2.1 of the License, or (at your option)
17  * any later version.
18  *
19  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
20  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
21  * A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
22  * details.
23  *
24  * You should have received a copy of the GNU Lesser General Public License
25  * along with wimlib; if not, see http://www.gnu.org/licenses/.
26  */
27
28 #include "wimlib_internal.h"
29 #include "dentry.h"
30 #include "list.h"
31 #include "lookup_table.h"
32
33 /* Hard link group; it's identified by its hard link group ID and consists of a
34  * circularly linked list of dentries. */
35 struct link_group {
36         u64 link_group_id;
37         struct link_group *next;
38         struct list_head *dentry_list;
39 };
40
41 /* Hash table to find hard link groups, identified by their hard link group ID.
42  * */
43 struct link_group_table {
44         struct link_group **array;
45         u64 num_entries;
46         u64 capacity;
47         struct link_group *singles;
48 };
49
50 /* Returns pointer to a new link group table having the specified capacity */
51 struct link_group_table *new_link_group_table(u64 capacity)
52 {
53         struct link_group_table *table;
54         struct link_group **array;
55
56         table = MALLOC(sizeof(struct link_group_table));
57         if (!table)
58                 goto err;
59         array = CALLOC(capacity, sizeof(array[0]));
60         if (!array) {
61                 FREE(table);
62                 goto err;
63         }
64         table->num_entries = 0;
65         table->capacity = capacity;
66         table->array = array;
67         table->singles = NULL;
68         return table;
69 err:
70         ERROR("Failed to allocate memory for link group table with capacity %zu",
71               capacity);
72         return NULL;
73 }
74
75 /* 
76  * Insert a dentry into the hard link group table based on its hard link group
77  * ID.
78  *
79  * If there is already a dentry in the table having the same hard link group ID,
80  * we link the dentries together in a circular list.
81  *
82  * If the hard link group ID is 0, this indicates a dentry that's in a hard link
83  * group by itself (has a link count of 1).  We can't insert it into the hash
84  * table itself because we don't know what hard link group IDs are available to
85  * give it (this could be kept track of but would be more difficult).  Instead
86  * we keep a linked list of the single dentries, and assign them hard link group
87  * IDs later.
88  */
89 int link_group_table_insert(struct dentry *dentry, void *__table)
90 {
91         struct link_group_table *table = __table;
92         size_t pos;
93         struct link_group *group;
94
95         if (dentry->hard_link == 0) {
96                 /* Single group--- Add to the singles list (we can't put it in
97                  * the table itself because all the singles have a link group ID
98                  * of 0) */
99                 group = MALLOC(sizeof(struct link_group));
100                 if (!group)
101                         return WIMLIB_ERR_NOMEM;
102                 group->link_group_id = 0;
103                 group->next          = table->singles;
104                 table->singles       = group;
105                 INIT_LIST_HEAD(&dentry->link_group_list);
106                 group->dentry_list = &dentry->link_group_list;
107         } else {
108                 /* Hard link group that may should multiple dentries (the code
109                  * will work even if the group actually contains only 1 dentry
110                  * though) */
111
112                 /* Try adding to existing hard link group */
113                 pos = dentry->hard_link % table->capacity;
114                 group = table->array[pos];
115                 while (group) {
116                         if (group->link_group_id == dentry->hard_link) {
117                                 list_add(&dentry->link_group_list,
118                                          group->dentry_list);
119                                 return 0;
120                         }
121                         group = group->next;
122                 }
123
124                 /* Add new hard link group to the table */
125
126                 group = MALLOC(sizeof(struct link_group));
127                 if (!group)
128                         return WIMLIB_ERR_NOMEM;
129                 group->link_group_id   = dentry->hard_link;
130                 group->next            = table->array[pos];
131                 INIT_LIST_HEAD(&dentry->link_group_list);
132                 group->dentry_list = &dentry->link_group_list;
133                 table->array[pos]      = group;
134
135                 /* XXX Make the table grow when too many entries have been
136                  * inserted. */
137                 table->num_entries++;
138         }
139         return 0;
140 }
141
142 /* Frees a link group table. */
143 void free_link_group_table(struct link_group_table *table)
144 {
145         struct link_group *single, *next;
146
147         if (!table)
148                 return;
149         if (table->array) {
150                 for (u64 i = 0; i < table->capacity; i++) {
151                         struct link_group *group = table->array[i];
152                         struct link_group *next;
153                         while (group) {
154                                 next = group->next;
155                                 FREE(group);
156                                 group = next;
157                         }
158                 }
159                 FREE(table->array);
160         }
161         single = table->singles;
162         while (single) {
163                 next = single->next;
164                 FREE(single);
165                 single = next;
166         }
167
168         FREE(table);
169 }
170
171 /* Assign the link group IDs to dentries in a link group table, and return the
172  * next available link group ID. */
173 u64 assign_link_groups(struct link_group_table *table)
174 {
175         DEBUG("Assigning link groups");
176
177         /* Assign consecutive link group IDs to each link group in the hash
178          * table */
179         u64 id = 1;
180         for (u64 i = 0; i < table->capacity; i++) {
181                 struct link_group *group = table->array[i];
182                 struct link_group *next_group;
183                 struct dentry *dentry;
184                 struct list_head *cur;
185                 while (group) {
186                         cur = group->dentry_list;
187                         do {
188                                 dentry = container_of(cur,
189                                                       struct dentry,
190                                                       link_group_list);
191                                 dentry->hard_link = id;
192                                 cur = cur->next;
193                         } while (cur != group->dentry_list);
194                         id++;
195                         group = group->next;
196                 }
197         }
198         /* Assign link group IDs to the link groups that previously had link
199          * group IDs of 0, and insert them into the hash table */
200         struct link_group *single = table->singles;
201         while (single) {
202                 struct dentry *dentry;
203                 struct link_group *next_single;
204                 size_t pos;
205
206                 next_single = single->next;
207
208                 dentry = container_of(single->dentry_list, struct dentry,
209                                       link_group_list);
210                 dentry->hard_link = id;
211
212                 pos = id % table->capacity;
213                 single->next = table->array[pos];
214                 table->array[pos] = single;
215
216                 single = next_single;
217                 id++;
218         }
219         table->singles = NULL;
220         return id;
221 }
222
223 static bool dentries_have_same_ads(const struct dentry *d1,
224                                    const struct dentry *d2)
225 {
226         /* Verify stream names and hashes are the same */
227         for (u16 i = 0; i < d1->num_ads; i++) {
228                 if (strcmp(d1->ads_entries[i].stream_name_utf8,
229                            d2->ads_entries[i].stream_name_utf8) != 0)
230                         return false;
231                 if (!hashes_equal(d1->ads_entries[i].hash,
232                                   d2->ads_entries[i].hash))
233                         return false;
234         }
235         return true;
236 }
237
238 /* 
239  * Share the alternate stream entries between hard-linked dentries.
240  *
241  * Notes:
242  * - If you use 'imagex.exe' (version 6.1.7600.16385) to create a WIM containing
243  *   hard-linked files, only one dentry in the hard link set will refer to data
244  *   streams, including all alternate data streams.  The rest of the dentries in
245  *   the hard link set will be marked as having 0 alternate data streams and
246  *   will not refer to any main file stream (the SHA1 message digest will be all
247  *   0's).
248  *
249  * - However, if you look at the WIM's that Microsoft actually distributes (e.g.
250  *   Windows 7/8 boot.wim, install.wim), it's not the same as above.  The
251  *   dentries in hard link sets will have stream information duplicated.  I
252  *   can't say anything about the alternate data streams because these WIMs do
253  *   not contain alternate data streams.
254  *
255  * - Windows 7 'install.wim' contains hard link sets containing dentries with
256  *   inconsistent streams and other inconsistent information such as security
257  *   ID.  The only way I can think to handle these is to treat the hard link
258  *   grouping as erroneous and split up the hard link group.
259  */
260 static int share_dentry_ads(struct dentry *owner, struct dentry *user)
261 {
262         const char *mismatch_type;
263         bool data_streams_shared = true;
264         wimlib_assert(owner->num_ads == 0 ||
265                       owner->ads_entries != user->ads_entries);
266         if (owner->attributes != user->attributes) {
267                 mismatch_type = "attributes";
268                 goto mismatch;
269         }
270         if (owner->attributes & FILE_ATTRIBUTE_DIRECTORY) {
271                 WARNING("`%s' is hard-linked to `%s', which is a directory ",
272                         user->full_path_utf8, owner->full_path_utf8);
273                 return WIMLIB_ERR_INVALID_DENTRY;
274         }
275         if (owner->security_id != user->security_id) {
276                 mismatch_type = "security ID";
277                 goto mismatch;
278         }
279         if (!hashes_equal(owner->hash, user->hash)) {
280                 if (is_zero_hash(user->hash)) {
281                         data_streams_shared = false;
282                         copy_hash(user->hash, owner->hash);
283                 } else {
284                         mismatch_type = "main file resource";
285                         goto mismatch;
286                 }
287         }
288         if (data_streams_shared) {
289                 if (!dentries_have_same_ads(owner, user)) {
290                         mismatch_type = "Alternate Stream Entries";
291                         goto mismatch;
292                 }
293         }
294         dentry_free_ads_entries(user);
295         user->ads_entries = owner->ads_entries;
296         user->ads_entries_status = ADS_ENTRIES_USER;
297         return 0;
298 mismatch:
299         WARNING("Dentries `%s' and `%s' are supposedly in the same hard-link "
300                 "group but do not share the same %s",
301                 owner->full_path_utf8, user->full_path_utf8,
302                 mismatch_type);
303         return WIMLIB_ERR_INVALID_DENTRY;
304 }
305
306 static int link_group_free_duplicate_data(struct link_group *group,
307                                           struct link_group **bad_links)
308 {
309         struct dentry *owner, *user, *tmp;
310
311         /* Find a dentry with non-zero hash to use as a possible link group
312          * owner (see comments above the share_dentry_ads() function */
313         owner = container_of(group->dentry_list, struct dentry,
314                               link_group_list);
315         do {
316                 /* imagex.exe may move the un-named data stream from the dentry
317                  * itself to the first alternate data stream, if there are
318                  * other alternate data streams */
319                 if (!is_zero_hash(owner->hash) ||
320                     (owner->num_ads && !is_zero_hash(owner->ads_entries[0].hash)))
321                         goto found_owner;
322                 owner = container_of(owner->link_group_list.next,
323                                      struct dentry,
324                                      link_group_list);
325         } while (&owner->link_group_list != group->dentry_list);
326
327         ERROR("Could not find owner of data streams in hard link group");
328         return WIMLIB_ERR_INVALID_DENTRY;
329 found_owner:
330         owner->ads_entries_status = ADS_ENTRIES_OWNER;
331         list_for_each_entry_safe(user, tmp, &owner->link_group_list,
332                                  link_group_list)
333         {
334                 /* I would like it to be an error if two dentries are in the
335                  * same hard link group but have irreconcilable differences such
336                  * as different file permissions, but unfortunately some of M$'s
337                  * WIMs contain many instances of this error.  This problem is
338                  * worked around here by splitting each offending dentry off
339                  * into its own hard link group. */
340                 if (share_dentry_ads(owner, user) != 0) {
341                         struct link_group *single;
342                         single = MALLOC(sizeof(struct link_group));
343                         if (!single)
344                                 return WIMLIB_ERR_NOMEM;
345                         list_del(&user->link_group_list);
346                         INIT_LIST_HEAD(&user->link_group_list);
347                         single->link_group_id = 0;
348                         single->next          = *bad_links;
349                         single->dentry_list   = &user->link_group_list;
350                         *bad_links            = single;
351                         user->ads_entries_status = ADS_ENTRIES_OWNER;
352                 }
353         }
354         return 0;
355 }
356
357 /*
358  * Goes through each link group and shares the ads_entries (Alternate Data
359  * Stream entries) field of each dentry between members of a hard link group.
360  *
361  * In the process, the dentries in each link group are checked for consistency.
362  * If they contain data features that indicate they cannot really be in the same
363  * hard link group, this should be an error, but in reality this case needs to
364  * be handled, so we split the dentries into different hard link groups.
365  *
366  * One of the dentries in the group is arbitrarily assigned the role of "owner"
367  * (ADS_ENTRIES_OWNER), while the others are "users" (ADS_ENTRIES_USER).
368  */
369 int link_groups_free_duplicate_data(struct link_group_table *table)
370 {
371         for (u64 i = 0; i < table->capacity; i++) {
372                 struct link_group *group = table->array[i];
373                 while (group) {
374                         int ret;
375                         ret = link_group_free_duplicate_data(group,
376                                                              &table->singles);
377                         if (ret != 0)
378                                 return ret;
379                         group = group->next;
380                 }
381         }
382         return 0;
383 }