4640c9cf12524471f7efb92b977e5c8ecaf73358
[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                 DEBUG("Insert single group `%s'", dentry->full_path_utf8);
67                 group->link_group_id = 0;
68                 group->next          = table->singles;
69                 table->singles       = group;
70                 INIT_LIST_HEAD(&dentry->link_group_list);
71                 group->dentry_list = &dentry->link_group_list;
72                 return 0;
73         }
74
75         /* Try adding to existing hard link group */
76         pos = dentry->hard_link % table->capacity;
77         group = table->array[pos];
78         while (group) {
79                 if (group->link_group_id == dentry->hard_link) {
80                         list_add(&dentry->link_group_list, group->dentry_list);
81                         return 0;
82                 }
83                 group = group->next;
84         }
85
86         /* Add new hard link group to the table */
87
88         group = MALLOC(sizeof(struct link_group));
89         if (!group)
90                 return WIMLIB_ERR_NOMEM;
91         group->link_group_id   = dentry->hard_link;
92         group->next            = table->array[pos];
93         INIT_LIST_HEAD(&dentry->link_group_list);
94         group->dentry_list = &dentry->link_group_list;
95         table->array[pos]      = group;
96
97         /* XXX Make the table grow when too many entries have been inserted. */
98         table->num_entries++;
99         return 0;
100 }
101
102 /* Frees a link group table. */
103 void free_link_group_table(struct link_group_table *table)
104 {
105         if (!table)
106                 return;
107         if (table->array) {
108                 for (u64 i = 0; i < table->capacity; i++) {
109                         struct link_group *group = table->array[i];
110                         struct link_group *next;
111                         while (group) {
112                                 next = group->next;
113                                 FREE(group);
114                                 group = next;
115                         }
116                 }
117                 FREE(table->array);
118         }
119         FREE(table);
120 }
121
122 /* Assign the link group IDs to dentries in a link group table, and return the
123  * next available link group ID. */
124 u64 assign_link_groups(struct link_group_table *table)
125 {
126         DEBUG("Assigning link groups");
127         u64 id = 1;
128         for (u64 i = 0; i < table->capacity; i++) {
129                 struct link_group *group = table->array[i];
130                 struct link_group *next_group;
131                 struct dentry *dentry;
132                 struct list_head *cur;
133                 while (group) {
134                         cur = group->dentry_list;
135                         do {
136                                 dentry = container_of(cur,
137                                                       struct dentry,
138                                                       link_group_list);
139                                 dentry->hard_link = id;
140                                 cur = cur->next;
141                         } while (cur != group->dentry_list);
142                         id++;
143                         group = group->next;
144                 }
145         }
146         /* Singles */
147         struct link_group *single = table->singles;
148         while (single) {
149                 struct dentry *dentry;
150                 struct link_group *next_single;
151                 size_t pos;
152
153                 next_single = single->next;
154
155                 dentry = container_of(single->dentry_list, struct dentry,
156                                       link_group_list);
157                 dentry->hard_link = id;
158                 DEBUG("Assign single `%s'", dentry->full_path_utf8);
159
160                 pos = id % table->capacity;
161                 single->next = table->array[pos];
162                 table->array[pos] = single;
163
164                 single = next_single;
165                 id++;
166         }
167         return id;
168 }
169
170 static int link_group_free_duplicate_data(struct link_group *group)
171 {
172         struct list_head *head;
173         struct dentry *master;
174
175         head = group->dentry_list;
176         master = container_of(head, struct dentry, link_group_list);
177         head = head->next;
178         master->link_group_master_status = GROUP_MASTER;
179         while (head != group->dentry_list) {
180                 int ret = share_dentry_ads(master,
181                                            container_of(head, struct dentry,
182                                                         link_group_list));
183                 if (ret != 0)
184                         return ret;
185                 head = head->next;
186         }
187         return 0;
188 }
189
190 int link_groups_free_duplicate_data(struct link_group_table *table)
191 {
192         for (u64 i = 0; i < table->capacity; i++) {
193                 struct link_group *group = table->array[i];
194                 while (group) {
195                         int ret = link_group_free_duplicate_data(group);
196                         if (ret != 0)
197                                 return ret;
198                         group = group->next;
199                 }
200         }
201         return 0;
202 }