Hard link fix
[wimlib] / src / hardlink.c
1 #include "wimlib_internal.h"
2 #include "dentry.h"
3 #include "list.h"
4 #include "lookup_table.h"
5
6 struct link_group {
7         u64 link_group_id;
8         struct link_group *next;
9         struct list_head *dentry_list;
10 };
11
12 struct link_group_table {
13         struct link_group **array;
14         u64 num_entries;
15         u64 capacity;
16         struct link_group *singles;
17 };
18
19 #include <sys/mman.h>
20
21 struct link_group_table *new_link_group_table(u64 capacity)
22 {
23         struct link_group_table *table;
24         struct link_group **array;
25
26         table = MALLOC(sizeof(struct link_group_table));
27         if (!table)
28                 goto err;
29         array = CALLOC(capacity, sizeof(array[0]));
30         if (!array) {
31                 FREE(table);
32                 goto err;
33         }
34         table->num_entries = 0;
35         table->capacity = capacity;
36         table->array = array;
37         table->singles = NULL;
38         return table;
39 err:
40         ERROR("Failed to allocate memory for link group table with capacity %zu",
41               capacity);
42         return NULL;
43 }
44
45 /* Insert a dentry into the hard link group table based on its hard link group
46  * ID.
47  *
48  * If there is already a dentry in the table having the same hard link group ID,
49  * we link the dentries together in a circular list.
50  *
51  * If the hard link group ID is 0, this is a no-op and the dentry is not
52  * inserted.
53  */
54 int link_group_table_insert(struct dentry *dentry, struct link_group_table *table)
55 {
56         size_t pos;
57         struct link_group *group;
58
59         if (dentry->hard_link == 0) {
60                 /* Single group--- Add to the singles list (we can't put it in
61                  * the table itself because all the singles have a link group ID
62                  * of 0) */
63                 group = MALLOC(sizeof(struct link_group));
64                 if (!group)
65                         return WIMLIB_ERR_NOMEM;
66                 group->link_group_id = 0;
67                 group->next          = table->singles;
68                 table->singles       = group;
69                 INIT_LIST_HEAD(&dentry->link_group_list);
70                 group->dentry_list = &dentry->link_group_list;
71                 return 0;
72         }
73
74         /* Try adding to existing hard link group */
75         pos = dentry->hard_link % table->capacity;
76         group = table->array[pos];
77         while (group) {
78                 if (group->link_group_id == dentry->hard_link) {
79                         list_add(&dentry->link_group_list, group->dentry_list);
80                         return 0;
81                 }
82                 group = group->next;
83         }
84
85         /* Add new hard link group to the table */
86
87         group = MALLOC(sizeof(struct link_group));
88         if (!group)
89                 return WIMLIB_ERR_NOMEM;
90         group->link_group_id   = dentry->hard_link;
91         group->next            = table->array[pos];
92         INIT_LIST_HEAD(&dentry->link_group_list);
93         group->dentry_list = &dentry->link_group_list;
94         table->array[pos]      = group;
95
96         /* XXX Make the table grow when too many entries have been inserted. */
97         table->num_entries++;
98         return 0;
99 }
100
101 /* Frees a link group table. */
102 void free_link_group_table(struct link_group_table *table)
103 {
104         if (!table)
105                 return;
106         if (table->array) {
107                 for (u64 i = 0; i < table->capacity; i++) {
108                         struct link_group *group = table->array[i];
109                         struct link_group *next;
110                         while (group) {
111                                 next = group->next;
112                                 FREE(group);
113                                 group = next;
114                         }
115                 }
116                 FREE(table->array);
117         }
118         FREE(table);
119 }
120
121 /* Assign the link group IDs to dentries in a link group table, and return the
122  * next available link group ID. */
123 u64 assign_link_groups(struct link_group_table *table)
124 {
125         DEBUG("Assigning link groups");
126         u64 id = 1;
127         for (u64 i = 0; i < table->capacity; i++) {
128                 struct link_group *group = table->array[i];
129                 struct link_group *next_group;
130                 struct dentry *dentry;
131                 struct list_head *cur;
132                 while (group) {
133                         cur = group->dentry_list;
134                         do {
135                                 dentry = container_of(cur,
136                                                       struct dentry,
137                                                       link_group_list);
138                                 dentry->hard_link = id;
139                                 cur = cur->next;
140                         } while (cur != group->dentry_list);
141                         id++;
142                         group = group->next;
143                 }
144         }
145         /* Singles */
146         struct link_group *single = table->singles;
147         while (single) {
148                 struct dentry *dentry;
149                 struct link_group *next_single;
150                 size_t pos;
151
152                 next_single = single->next;
153
154                 dentry = container_of(single->dentry_list, struct dentry,
155                                       link_group_list);
156                 dentry->hard_link = id;
157
158                 pos = id % table->capacity;
159                 single->next = table->array[pos];
160                 table->array[pos] = single;
161
162                 single = next_single;
163                 id++;
164         }
165         table->singles = NULL;
166         return id;
167 }
168
169 static int link_group_free_duplicate_data(struct link_group *group,
170                                           struct link_group **bad_links)
171 {
172         struct list_head *head;
173         struct list_head *next;
174         struct dentry *master;
175
176         head = group->dentry_list;
177         master = container_of(head, struct dentry, link_group_list);
178         head = head->next;
179         master->link_group_master_status = GROUP_MASTER;
180         while (head != group->dentry_list) {
181                 next = head->next;
182                 struct dentry *slave;
183                 int ret;
184
185                 slave = container_of(head, struct dentry, link_group_list);
186                 ret = share_dentry_ads(master, slave);
187
188                 /* I would it to be an error if two dentries are the same hard
189                  * link group but have irreconcilable differences such as
190                  * different file permissions, but unfortunately some of M$'s
191                  * WIMs contain many instances of this error.  This problem is
192                  * worked around here by splitting each offending dentry off
193                  * into its own hard link group. */
194                 if (ret != 0) {
195                         struct link_group *single;
196                         single = MALLOC(sizeof(struct link_group));
197                         if (!single)
198                                 return WIMLIB_ERR_NOMEM;
199                         single->link_group_id = 0;
200                         single->next          = *bad_links;
201                         *bad_links            = single;
202                         INIT_LIST_HEAD(&slave->link_group_list);
203                         single->dentry_list = &slave->link_group_list;
204                         slave->link_group_master_status = GROUP_INDEPENDENT;
205                 }
206                 head = next;
207         }
208         return 0;
209 }
210
211 int link_groups_free_duplicate_data(struct link_group_table *table)
212 {
213         for (u64 i = 0; i < table->capacity; i++) {
214                 struct link_group *group = table->array[i];
215                 while (group) {
216                         int ret;
217                         ret = link_group_free_duplicate_data(group,
218                                                              &table->singles);
219                         if (ret != 0)
220                                 return ret;
221                         group = group->next;
222                 }
223         }
224         return 0;
225 }