inode_table: make the inode table resizable
[wimlib] / src / inode_table.c
1 /*
2  * inode_table.c - hard link detection
3  */
4
5 /*
6  * Copyright (C) 2012-2016 Eric Biggers
7  *
8  * This file is free software; you can redistribute it and/or modify it under
9  * the terms of the GNU Lesser General Public License as published by the Free
10  * Software Foundation; either version 3 of the License, or (at your option) any
11  * later version.
12  *
13  * This file is distributed in the hope that it will be useful, but WITHOUT
14  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15  * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
16  * details.
17  *
18  * You should have received a copy of the GNU Lesser General Public License
19  * along with this file; if not, see http://www.gnu.org/licenses/.
20  */
21
22 #ifdef HAVE_CONFIG_H
23 #  include "config.h"
24 #endif
25
26 #include "wimlib/bitops.h"
27 #include "wimlib/dentry.h"
28 #include "wimlib/error.h"
29 #include "wimlib/inode.h"
30 #include "wimlib/inode_table.h"
31 #include "wimlib/list.h"
32 #include "wimlib/util.h"
33
34 /* Initialize a hash table for hard link detection.  */
35 int
36 init_inode_table(struct wim_inode_table *table, size_t capacity)
37 {
38         capacity = roundup_pow_of_2(capacity);
39         table->array = CALLOC(capacity, sizeof(table->array[0]));
40         if (!table->array)
41                 return WIMLIB_ERR_NOMEM;
42         table->filled = 0;
43         table->capacity = capacity;
44         INIT_HLIST_HEAD(&table->extra_inodes);
45         return 0;
46 }
47
48 /* Free the memory allocated by init_inode_table().  */
49 void
50 destroy_inode_table(struct wim_inode_table *table)
51 {
52         FREE(table->array);
53 }
54
55 /* Double the capacity of the inode hash table.  */
56 void
57 enlarge_inode_table(struct wim_inode_table *table)
58 {
59         const size_t old_capacity = table->capacity;
60         const size_t new_capacity = old_capacity * 2;
61         struct hlist_head *old_array = table->array;
62         struct hlist_head *new_array;
63         struct wim_inode *inode;
64         struct hlist_node *tmp;
65
66         new_array = CALLOC(new_capacity, sizeof(struct hlist_head));
67         if (!new_array)
68                 return;
69         table->array = new_array;
70         table->capacity = new_capacity;
71         for (size_t i = 0; i < old_capacity; i++) {
72                 hlist_for_each_entry_safe(inode, tmp, &old_array[i], i_hlist_node) {
73                         hlist_add_head(&inode->i_hlist_node,
74                                        &new_array[hash_inode(table, inode->i_ino,
75                                                              inode->i_devno)]);
76                 }
77         }
78         FREE(old_array);
79 }
80
81 /*
82  * Allocate a new dentry, with hard link detection.
83  *
84  * @table
85  *      The inode table being used for the current directory scan operation.  It
86  *      will contain the mapping from (ino, devno) pairs to inodes.
87  *
88  * @name
89  *      The name to give the new dentry.
90  *
91  * @ino
92  *      The inode number of the file, read from the filesystem.
93  *
94  * @devno
95  *      The device number of the file, read from the filesystem.  Proper setting
96  *      of this parameter prevents cross-device hardlinks from being created.
97  *      If this is not a problem (perhaps because the current directory scan
98  *      operation is guaranteed to never traverse a filesystem boundary), then
99  *      this parameter can just be a fixed value such as 0.
100  *
101  * @noshare
102  *      If %true, the new dentry will not be hard linked to any existing inode,
103  *      regardless of the values of @ino and @devno.  If %false, normal hard
104  *      link detection will be done.
105  *
106  * @dentry_ret
107  *      On success, a pointer to the new dentry will be returned in this
108  *      location.  If i_nlink of the dentry's inode is greater than 1, then this
109  *      function created a hard link to an existing inode rather than creating a
110  *      new inode.
111  *
112  * On success, returns 0.  On failure, returns WIMLIB_ERR_NOMEM or an error code
113  * resulting from a failed string conversion.
114  */
115 int
116 inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
117                        u64 ino, u64 devno, bool noshare,
118                        struct wim_dentry **dentry_ret)
119 {
120         struct wim_dentry *dentry;
121         struct wim_inode *inode;
122         struct hlist_head *list;
123         int ret;
124
125         if (noshare) {
126                 /* No hard link detection  */
127                 list = &table->extra_inodes;
128         } else {
129                 /* Hard link detection  */
130                 list = &table->array[hash_inode(table, ino, devno)];
131                 hlist_for_each_entry(inode, list, i_hlist_node) {
132                         if (inode->i_ino != ino || inode->i_devno != devno)
133                                 continue;
134                         if (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) {
135                                 WARNING("Not honoring directory hard link "
136                                         "of \"%"TS"\"",
137                                         inode_any_full_path(inode));
138                                 continue;
139                         }
140                         /* Inode found; use it.  */
141                         return new_dentry_with_existing_inode(name, inode,
142                                                               dentry_ret);
143                 }
144
145                 /* Inode not found; create it.  */
146         }
147
148         ret = new_dentry_with_new_inode(name, false, &dentry);
149         if (ret)
150                 return ret;
151         inode = dentry->d_inode;
152         inode->i_ino = ino;
153         inode->i_devno = devno;
154         hlist_add_head(&inode->i_hlist_node, list);
155         if (list != &table->extra_inodes)
156                 if (++table->filled > table->capacity)
157                         enlarge_inode_table(table);
158         *dentry_ret = dentry;
159         return 0;
160 }
161
162 /*
163  * Following the allocation of dentries with hard link detection using
164  * inode_table_new_dentry(), this function will assign consecutive inode numbers
165  * to the new set of inodes.  It will also append the list of new inodes to the
166  * list @head, which must contain any inodes already existing in the WIM image.
167  */
168 void
169 inode_table_prepare_inode_list(struct wim_inode_table *table,
170                                struct hlist_head *head)
171 {
172         struct wim_inode *inode;
173         struct hlist_node *tmp;
174         u64 cur_ino = 1;
175
176         /* Re-assign inode numbers in the existing list to avoid duplicates. */
177         hlist_for_each_entry(inode, head, i_hlist_node)
178                 inode->i_ino = cur_ino++;
179
180         /* Assign inode numbers to the new inodes and move them to the image's
181          * inode list. */
182         for (size_t i = 0; i < table->capacity; i++) {
183                 hlist_for_each_entry_safe(inode, tmp, &table->array[i], i_hlist_node) {
184                         inode->i_ino = cur_ino++;
185                         hlist_add_head(&inode->i_hlist_node, head);
186                 }
187                 INIT_HLIST_HEAD(&table->array[i]);
188         }
189         hlist_for_each_entry_safe(inode, tmp, &table->extra_inodes, i_hlist_node) {
190                 inode->i_ino = cur_ino++;
191                 hlist_add_head(&inode->i_hlist_node, head);
192         }
193         INIT_HLIST_HEAD(&table->extra_inodes);
194 }