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