e9c92d6a0571fa13ace88029452e8455cbb25231
[wimlib] / src / inode_table.c
1 /*
2  * inode_table.c - hard link detection
3  */
4
5 /*
6  * Copyright (C) 2012, 2013, 2014 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/dentry.h"
27 #include "wimlib/error.h"
28 #include "wimlib/inode.h"
29 #include "wimlib/inode_table.h"
30 #include "wimlib/list.h"
31 #include "wimlib/util.h"
32
33 /* Initialize a hash table for hard link detection.  */
34 int
35 init_inode_table(struct wim_inode_table *table, size_t capacity)
36 {
37         table->array = CALLOC(capacity, sizeof(table->array[0]));
38         if (!table->array)
39                 return WIMLIB_ERR_NOMEM;
40         table->capacity = capacity;
41         INIT_HLIST_HEAD(&table->extra_inodes);
42         return 0;
43 }
44
45 /* Free the memory allocated by init_inode_table().  */
46 void
47 destroy_inode_table(struct wim_inode_table *table)
48 {
49         FREE(table->array);
50 }
51
52 /*
53  * Allocate a new dentry, with hard link detection.
54  *
55  * @table
56  *      The inode table being used for the current directory scan operation.  It
57  *      will contain the mapping from (ino, devno) pairs to inodes.
58  *
59  * @name
60  *      The name to give the new dentry.
61  *
62  * @ino
63  *      The inode number of the file, read from the filesystem.
64  *
65  * @devno
66  *      The device number of the file, read from the filesystem.  Proper setting
67  *      of this parameter prevents cross-device hardlinks from being created.
68  *      If this is not a problem (perhaps because the current directory scan
69  *      operation is guaranteed to never traverse a filesystem boundary), then
70  *      this parameter can just be a fixed value such as 0.
71  *
72  * @noshare
73  *      If %true, the new dentry will not be hard linked to any existing inode,
74  *      regardless of the values of @ino and @devno.  If %false, normal hard
75  *      link detection will be done.
76  *
77  * @dentry_ret
78  *      On success, a pointer to the new dentry will be returned in this
79  *      location.  If i_nlink of the dentry's inode is greater than 1, then this
80  *      function created a hard link to an existing inode rather than creating a
81  *      new inode.
82  *
83  * On success, returns 0.  On failure, returns WIMLIB_ERR_NOMEM or an error code
84  * resulting from a failed string conversion.
85  */
86 int
87 inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
88                        u64 ino, u64 devno, bool noshare,
89                        struct wim_dentry **dentry_ret)
90 {
91         struct wim_dentry *dentry;
92         struct wim_inode *inode;
93         struct hlist_head *list;
94         int ret;
95
96         if (noshare) {
97                 /* No hard link detection  */
98                 list = &table->extra_inodes;
99         } else {
100                 /* Hard link detection  */
101                 list = &table->array[hash_u64(hash_u64(ino) + hash_u64(devno))
102                                      % table->capacity];
103                 hlist_for_each_entry(inode, list, i_hlist_node) {
104                         if (inode->i_ino != ino || inode->i_devno != devno)
105                                 continue;
106                         if (inode->i_attributes & FILE_ATTRIBUTE_DIRECTORY) {
107                                 WARNING("Not honoring directory hard link "
108                                         "of \"%"TS"\"",
109                                         inode_any_full_path(inode));
110                                 continue;
111                         }
112                         /* Inode found; use it.  */
113                         return new_dentry_with_existing_inode(name, inode,
114                                                               dentry_ret);
115                 }
116
117                 /* Inode not found; create it.  */
118         }
119
120         ret = new_dentry_with_new_inode(name, false, &dentry);
121         if (ret)
122                 return ret;
123         inode = dentry->d_inode;
124         hlist_add_head(&inode->i_hlist_node, list);
125         inode->i_ino = ino;
126         inode->i_devno = devno;
127         *dentry_ret = dentry;
128         return 0;
129 }
130
131 /*
132  * Following the allocation of dentries with hard link detection using
133  * inode_table_new_dentry(), this function will assign consecutive inode numbers
134  * to the new set of inodes.  It will also append the list of new inodes to the
135  * list @head, which must contain any inodes already existing in the WIM image.
136  */
137 void
138 inode_table_prepare_inode_list(struct wim_inode_table *table,
139                                struct hlist_head *head)
140 {
141         struct wim_inode *inode;
142         struct hlist_node *tmp;
143         u64 cur_ino = 1;
144
145         /* Re-assign inode numbers in the existing list to avoid duplicates. */
146         hlist_for_each_entry(inode, head, i_hlist_node)
147                 inode->i_ino = cur_ino++;
148
149         /* Assign inode numbers to the new inodes and move them to the image's
150          * inode list. */
151         for (size_t i = 0; i < table->capacity; i++) {
152                 hlist_for_each_entry_safe(inode, tmp, &table->array[i], i_hlist_node) {
153                         inode->i_ino = cur_ino++;
154                         hlist_add_head(&inode->i_hlist_node, head);
155                 }
156                 INIT_HLIST_HEAD(&table->array[i]);
157         }
158         hlist_for_each_entry_safe(inode, tmp, &table->extra_inodes, i_hlist_node) {
159                 inode->i_ino = cur_ino++;
160                 hlist_add_head(&inode->i_hlist_node, head);
161         }
162         INIT_HLIST_HEAD(&table->extra_inodes);
163 }