hardlink fixes
[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 };
17
18 #include <sys/mman.h>
19
20 struct link_group_table *new_link_group_table(u64 capacity)
21 {
22         return (struct link_group_table*)new_lookup_table(capacity);
23 }
24
25 /* Insert a dentry into the hard link group table based on its hard link group
26  * ID.
27  *
28  * If there is already a dentry in the table having the same hard link group ID,
29  * we link the dentries together in a circular list.
30  *
31  * If the hard link group ID is 0, this is a no-op and the dentry is not
32  * inserted.
33  */
34 int link_group_table_insert(struct dentry *dentry, struct link_group_table *table)
35 {
36         size_t pos;
37         struct link_group *group;
38
39         if (dentry->hard_link == 0) {
40                 INIT_LIST_HEAD(&dentry->link_group_list);
41                 return 0;
42         }
43
44         /* Try adding to existing hard link group */
45         pos = dentry->hard_link % table->capacity;
46         group = table->array[pos];
47         while (group) {
48                 if (group->link_group_id == dentry->hard_link) {
49                         list_add(&dentry->link_group_list, group->dentry_list);
50                         return 0;
51                 }
52                 group = group->next;
53         }
54
55         /* Add new hard link group to the table */
56
57         group = MALLOC(sizeof(struct link_group));
58         if (!group)
59                 return WIMLIB_ERR_NOMEM;
60         group->link_group_id   = dentry->hard_link;
61         group->next            = table->array[pos];
62         INIT_LIST_HEAD(&dentry->link_group_list);
63         group->dentry_list = &dentry->link_group_list;
64         table->array[pos]      = group;
65
66         /* XXX Make the table grow when too many entries have been inserted. */
67         table->num_entries++;
68         return 0;
69 }
70
71 /* Frees a link group table. */
72 void free_link_group_table(struct link_group_table *table)
73 {
74         if (!table)
75                 return;
76         if (table->array) {
77                 for (u64 i = 0; i < table->capacity; i++) {
78                         struct link_group *group = table->array[i];
79                         struct link_group *next;
80                         while (group) {
81                                 next = group->next;
82                                 FREE(group);
83                                 group = next;
84                         }
85                 }
86                 FREE(table->array);
87         }
88         FREE(table);
89 }
90
91 /* Assign the link group IDs to dentries in a link group table, and return the
92  * next available link group ID. */
93 u64 assign_link_groups(struct link_group_table *table)
94 {
95         struct link_group *remaining_groups = NULL;
96         u64 id = 1;
97         for (u64 i = 0; i < table->capacity; i++) {
98                 struct link_group *group = table->array[i];
99                 struct link_group *next_group;
100                 struct dentry *dentry;
101                 while (group) {
102                         next_group = group->next;
103                         u64 cur_id;
104                         struct list_head *dentry_list = group->dentry_list;
105                         if (dentry_list->next == dentry_list) {
106                                 /* Hard link group of size 1.  Change the hard
107                                  * link ID to 0 and discard the link_group */
108                                 cur_id = 0;
109                                 FREE(group);
110                         } else {
111                                 /* Hard link group of size > 1.  Assign the
112                                  * dentries in the group the next available hard
113                                  * link IDs and queue the group to be
114                                  * re-inserted into the table. */
115                                 cur_id = id++;
116                                 group->next = remaining_groups;
117                                 remaining_groups = group;
118                         }
119                         struct list_head *cur = dentry_list;
120                         do {
121                                 dentry = container_of(cur,
122                                                       struct dentry,
123                                                       link_group_list);
124                                 dentry->hard_link = cur_id;
125                                 cur = cur->next;
126                         } while (cur != dentry_list);
127                         group = next_group;
128                 }
129         }
130         memset(table->array, 0, table->capacity * sizeof(table->array[0]));
131         table->num_entries = 0;
132         while (remaining_groups) {
133                 struct link_group *group = remaining_groups;
134                 size_t pos = group->link_group_id % table->capacity;
135
136                 table->num_entries++;
137                 group->next = table->array[pos];
138                 table->array[pos] = group;
139                 remaining_groups = remaining_groups->next;
140         }
141         return id;
142 }
143
144 #if 0
145 /* Load a dentry tree into the link group table */
146 int load_link_groups(struct link_group_table *table, struct dentry *root)
147 {
148         int ret = for_dentry_in_tree(dentry, link_group_table_insert, table);
149         if (ret == 0)
150                 assign_link_groups(table);
151         return ret;
152 }
153 #endif