f6de4e6047ab7ec8ce4555fad223ab9b936dffe2
[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->num_entries = 0;
41         table->capacity = capacity;
42         INIT_LIST_HEAD(&table->extra_inodes);
43         return 0;
44 }
45
46 /* Free the memory allocated by init_inode_table().  */
47 void
48 destroy_inode_table(struct wim_inode_table *table)
49 {
50         FREE(table->array);
51 }
52
53 /*
54  * Allocate a new dentry, with hard link detection.
55  *
56  * @table
57  *      The inode table being used for the current directory scan operation.  It
58  *      will contain the mapping from (ino, devno) pairs to inodes.
59  *
60  * @name
61  *      The name to give the new dentry.
62  *
63  * @ino
64  *      The inode number of the file, read from the filesystem.
65  *
66  * @devno
67  *      The device number of the file, read from the filesystem.  Proper setting
68  *      of this parameter prevents cross-device hardlinks from being created.
69  *      If this is not a problem (perhaps because the current directory scan
70  *      operation is guaranteed to never traverse a filesystem boundary), then
71  *      this parameter can just be a fixed value such as 0.
72  *
73  * @noshare
74  *      If %true, the new dentry will not be hard linked to any existing inode,
75  *      regardless of the values of @ino and @devno.  If %false, normal hard
76  *      link detection will be done.
77  *
78  * @dentry_ret
79  *      On success, a pointer to the new dentry will be returned in this
80  *      location.  If i_nlink of the dentry's inode is greater than 1, then this
81  *      function created a hard link to an existing inode rather than creating a
82  *      new inode.
83  *
84  * On success, returns 0.  On failure, returns WIMLIB_ERR_NOMEM or an error code
85  * resulting from a failed string conversion.
86  */
87 int
88 inode_table_new_dentry(struct wim_inode_table *table, const tchar *name,
89                        u64 ino, u64 devno, bool noshare,
90                        struct wim_dentry **dentry_ret)
91 {
92         struct wim_dentry *dentry;
93         struct wim_inode *inode;
94         int ret;
95
96         if (noshare) {
97                 /* File that cannot be hardlinked--- Return a new inode with its
98                  * inode and device numbers left at 0. */
99                 ret = new_dentry_with_timeless_inode(name, &dentry);
100                 if (ret)
101                         return ret;
102                 list_add_tail(&dentry->d_inode->i_list, &table->extra_inodes);
103         } else {
104                 size_t pos;
105                 struct hlist_node *cur;
106
107                 /* File that can be hardlinked--- search the table for an
108                  * existing inode matching the inode number and device;
109                  * otherwise create a new inode. */
110                 ret = new_dentry(name, &dentry);
111                 if (ret)
112                         return ret;
113
114                 /* Search for an existing inode having the same inode number and
115                  * device number.  */
116                 pos = hash_u64(hash_u64(ino) + hash_u64(devno)) % table->capacity;
117                 hlist_for_each_entry(inode, cur, &table->array[pos], i_hlist) {
118                         if (inode->i_ino == ino && inode->i_devno == devno) {
119                                 /* Found; use the existing inode.  */
120                                 inode_ref_blobs(inode);
121                                 goto have_inode;
122                         }
123                 }
124
125                 /* Create a new inode and insert it into the table.  */
126                 inode = new_timeless_inode();
127                 if (!inode) {
128                         free_dentry(dentry);
129                         return WIMLIB_ERR_NOMEM;
130                 }
131                 inode->i_ino = ino;
132                 inode->i_devno = devno;
133                 hlist_add_head(&inode->i_hlist, &table->array[pos]);
134                 table->num_entries++;
135         have_inode:
136                 d_associate(dentry, inode);
137         }
138         *dentry_ret = dentry;
139         return 0;
140 }
141
142 /*
143  * Following the allocation of dentries with hard link detection using
144  * inode_table_new_dentry(), this function will assign consecutive inode numbers
145  * to the new set of inodes.  It will also append the list of new inodes to the
146  * list @head, which must contain any inodes already existing in the WIM image.
147  */
148 void
149 inode_table_prepare_inode_list(struct wim_inode_table *table,
150                                struct list_head *head)
151 {
152         struct wim_inode *inode, *tmp_inode;
153         struct hlist_node *cur, *tmp;
154         u64 cur_ino = 1;
155
156         /* Re-assign inode numbers in the existing list to avoid duplicates. */
157         list_for_each_entry(inode, head, i_list)
158                 inode->i_ino = cur_ino++;
159
160         /* Assign inode numbers to the new inodes and move them to the image's
161          * inode list. */
162         for (size_t i = 0; i < table->capacity; i++) {
163                 hlist_for_each_entry_safe(inode, cur, tmp, &table->array[i], i_hlist)
164                 {
165                         inode->i_ino = cur_ino++;
166                         inode->i_devno = 0;
167                         list_add_tail(&inode->i_list, head);
168                 }
169                 INIT_HLIST_HEAD(&table->array[i]);
170         }
171         list_for_each_entry_safe(inode, tmp_inode, &table->extra_inodes, i_list)
172         {
173                 inode->i_ino = cur_ino++;
174                 inode->i_devno = 0;
175                 list_add_tail(&inode->i_list, head);
176         }
177         INIT_LIST_HEAD(&table->extra_inodes);
178         table->num_entries = 0;
179 }