--hardlink fix
[wimlib] / src / lookup_table.c
1 /*
2  * lookup_table.c
3  *
4  * Lookup table, implemented as a hash table, that maps dentries to file
5  * resources.
6  */
7
8 /*
9  * Copyright (C) 2012 Eric Biggers
10  *
11  * This file is part of wimlib, a library for working with WIM files.
12  *
13  * wimlib is free software; you can redistribute it and/or modify it under the
14  * terms of the GNU Lesser General Public License as published by the Free
15  * Software Foundation; either version 2.1 of the License, or (at your option)
16  * any later version.
17  *
18  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
19  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
20  * A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
21  * details.
22  *
23  * You should have received a copy of the GNU Lesser General Public License
24  * along with wimlib; if not, see http://www.gnu.org/licenses/.
25  */
26
27 #include "wimlib_internal.h"
28 #include "lookup_table.h"
29 #include "io.h"
30 #include <errno.h>
31
32 struct lookup_table *new_lookup_table(size_t capacity)
33 {
34         struct lookup_table *table;
35         struct lookup_table_entry **array;
36
37         table = MALLOC(sizeof(struct lookup_table));
38         if (!table)
39                 goto err;
40         array = CALLOC(capacity, sizeof(array[0]));
41         if (!array) {
42                 FREE(table);
43                 goto err;
44         }
45         table->num_entries = 0;
46         table->capacity = capacity;
47         table->array = array;
48         return table;
49 err:
50         ERROR("Failed to allocate memory for lookup table with capacity %zu",
51               capacity);
52         return NULL;
53 }
54
55 struct lookup_table_entry *new_lookup_table_entry()
56 {
57         struct lookup_table_entry *lte;
58         
59         lte = CALLOC(1, sizeof(struct lookup_table_entry));
60         if (!lte) {
61                 ERROR("Out of memory (tried to allocate %zu bytes for "
62                       "lookup table entry)",
63                       sizeof(struct lookup_table_entry));
64                 return NULL;
65         }
66
67         lte->part_number  = 1;
68         lte->refcnt       = 1;
69         return lte;
70 }
71
72
73
74 /*
75  * Inserts an entry into the lookup table.
76  *
77  * @lookup_table:       A pointer to the lookup table.
78  * @entry:              A pointer to the entry to insert.
79  */
80 void lookup_table_insert(struct lookup_table *table, 
81                          struct lookup_table_entry *lte)
82 {
83         size_t pos;
84         pos = lte->hash_short % table->capacity;
85         lte->next = table->array[pos];
86         table->array[pos] = lte;
87         /* XXX Make the table grow when too many entries have been inserted. */
88         table->num_entries++;
89 }
90
91
92 /* Unlinks a lookup table entry from the table; does not free it. */
93 void lookup_table_unlink(struct lookup_table *table, 
94                          struct lookup_table_entry *lte)
95 {
96         size_t pos;
97         struct lookup_table_entry *prev, *cur_entry, *next;
98
99         pos = lte->hash_short % table->capacity;
100         prev = NULL;
101         cur_entry = table->array[pos];
102
103         while (cur_entry) {
104                 next = cur_entry->next;
105                 if (cur_entry == lte) {
106                         if (prev)
107                                 prev->next = next;
108                         else
109                                 table->array[pos] = next;
110                         table->num_entries--;
111                         return;
112                 }
113                 prev = cur_entry;
114                 cur_entry = next;
115         }
116 }
117
118
119 /* Decrement the reference count for the dentry having hash value @hash in the
120  * lookup table.  The lookup table entry is unlinked and freed if there are no
121  * references to in remaining.  */
122 struct lookup_table_entry *
123 lookup_table_decrement_refcnt(struct lookup_table* table, const u8 hash[])
124 {
125         size_t pos = *(size_t*)hash % table->capacity;
126         struct lookup_table_entry *prev = NULL;
127         struct lookup_table_entry *entry = table->array[pos];
128         struct lookup_table_entry *next;
129         while (entry) {
130                 next = entry->next;
131                 if (memcmp(hash, entry->hash, WIM_HASH_SIZE) == 0) {
132                         wimlib_assert(entry->refcnt != 0);
133                         if (--entry->refcnt == 0) {
134                                 if (entry->num_opened_fds == 0) {
135                                         free_lookup_table_entry(entry);
136                                         entry = NULL;
137                                 }
138                                 if (prev)
139                                         prev->next = next;
140                                 else
141                                         table->array[pos] = next;
142                                 break;
143                         }
144                 }
145                 prev = entry;
146                 entry = next;
147         }
148         return entry;
149 }
150
151
152 /* 
153  * Calls a function on all the entries in the lookup table.  Stop early and
154  * return nonzero if any call to the function returns nonzero.
155  */
156 int for_lookup_table_entry(struct lookup_table *table, 
157                            int (*visitor)(struct lookup_table_entry *, void *),
158                            void *arg)
159 {
160         struct lookup_table_entry *entry, *next;
161         size_t i;
162         int ret;
163
164         for (i = 0; i < table->capacity; i++) {
165                 entry = table->array[i];
166                 while (entry) {
167                         next = entry->next;
168                         ret = visitor(entry, arg);
169                         if (ret != 0)
170                                 return ret;
171                         entry = next;
172                 }
173         }
174         return 0;
175 }
176
177
178 /*
179  * Reads the lookup table from a WIM file.
180  *
181  * @fp:                 The FILE* for the WIM file.
182  * @offset:             The offset of the lookup table resource.
183  * @size:               The size of the lookup table resource.
184  * @lookup_table_ret:   A pointer to a struct lookup_table structure into which the
185  *                              lookup table will be returned.
186  * @return:             True on success, false on failure.
187  */
188 int read_lookup_table(FILE *fp, u64 offset, u64 size, 
189                       struct lookup_table **table_ret)
190 {
191         size_t num_entries;
192         u8     buf[WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE];
193         int    ret;
194         struct lookup_table *table;
195         const u8 *p;
196         struct lookup_table_entry *cur_entry;
197
198         DEBUG("Reading lookup table: offset %"PRIu64", size %"PRIu64"",
199               offset, size);
200
201         if (fseeko(fp, offset, SEEK_SET) != 0) {
202                 ERROR_WITH_ERRNO("Failed to seek to byte %"PRIu64" to read "
203                                  "lookup table", offset);
204                 return WIMLIB_ERR_READ;
205         }
206
207         num_entries = size / WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE;
208         table = new_lookup_table(num_entries * 2 + 1);
209         if (!table)
210                 return WIMLIB_ERR_NOMEM;
211
212         while (num_entries--) {
213                 if (fread(buf, 1, sizeof(buf), fp) != sizeof(buf)) {
214                         if (feof(fp)) {
215                                 ERROR("Unexpected EOF in WIM lookup table!");
216                         } else {
217                                 ERROR_WITH_ERRNO("Error reading WIM lookup "
218                                                  "table");
219                         }
220                         ret = WIMLIB_ERR_READ;
221                         goto out;
222                 }
223                 cur_entry = new_lookup_table_entry();
224                 if (!cur_entry) {
225                         ret = WIMLIB_ERR_NOMEM;
226                         goto out;
227                 }
228                          
229                 p = get_resource_entry(buf, &cur_entry->resource_entry);
230                 p = get_u16(p, &cur_entry->part_number);
231                 p = get_u32(p, &cur_entry->refcnt);
232                 p = get_bytes(p, WIM_HASH_SIZE, cur_entry->hash);
233                 lookup_table_insert(table, cur_entry);
234         }
235         DEBUG("Done reading lookup table.");
236         *table_ret = table;
237         return 0;
238 out:
239         free_lookup_table(table);
240         return ret;
241 }
242
243
244 /* 
245  * Writes a lookup table entry to the output file.
246  */
247 int write_lookup_table_entry(struct lookup_table_entry *lte, void *__out)
248 {
249         FILE *out;
250         u8 buf[WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE];
251         u8 *p;
252
253         out = __out;
254
255         /* do not write lookup table entries for empty files */
256         if (lte->output_resource_entry.original_size == 0)
257                 return 0;
258
259         /* Don't write entries that have not had file resources or metadata
260          * resources written for them. */
261         if (lte->out_refcnt == 0)
262                 return 0;
263
264         if (lte->output_resource_entry.flags & WIM_RESHDR_FLAG_METADATA)
265                 DEBUG("Writing metadata entry at %lu (orig size = %zu)",
266                       ftello(out), lte->output_resource_entry.original_size);
267
268         p = put_resource_entry(buf, &lte->output_resource_entry);
269         p = put_u16(p, lte->part_number);
270         p = put_u32(p, lte->out_refcnt);
271         p = put_bytes(p, WIM_HASH_SIZE, lte->hash);
272         if (fwrite(buf, 1, sizeof(buf), out) != sizeof(buf)) {
273                 ERROR_WITH_ERRNO("Failed to write lookup table entry");
274                 return WIMLIB_ERR_WRITE;
275         }
276         return 0;
277 }
278
279 static int do_free_lookup_table_entry(struct lookup_table_entry *entry,
280                                       void *ignore)
281 {
282         free_lookup_table_entry(entry);
283         return 0;
284 }
285
286 void free_lookup_table(struct lookup_table *table)
287 {
288         if (!table)
289                 return;
290         if (table->array) {
291                 for_lookup_table_entry(table, do_free_lookup_table_entry, NULL);
292                 FREE(table->array);
293         }
294         FREE(table);
295 }
296
297 int zero_out_refcnts(struct lookup_table_entry *entry, void *ignore)
298 {
299         entry->out_refcnt = 0;
300         return 0;
301 }
302
303 int print_lookup_table_entry(struct lookup_table_entry *entry, void *ignore)
304 {
305         printf("Offset            = %"PRIu64" bytes\n", 
306                entry->resource_entry.offset);
307         printf("Size              = %"PRIu64" bytes\n", 
308                (u64)entry->resource_entry.size);
309         printf("Original size     = %"PRIu64" bytes\n", 
310                entry->resource_entry.original_size);
311         printf("Part Number       = %hu\n", entry->part_number);
312         printf("Reference Count   = %u\n", entry->refcnt);
313         printf("Hash              = ");
314         print_hash(entry->hash);
315         putchar('\n');
316         printf("Flags             = ");
317         u8 flags = entry->resource_entry.flags;
318         if (flags & WIM_RESHDR_FLAG_COMPRESSED)
319                 fputs("WIM_RESHDR_FLAG_COMPRESSED, ", stdout);
320         if (flags & WIM_RESHDR_FLAG_FREE)
321                 fputs("WIM_RESHDR_FLAG_FREE, ", stdout);
322         if (flags & WIM_RESHDR_FLAG_METADATA)
323                 fputs("WIM_RESHDR_FLAG_METADATA, ", stdout);
324         if (flags & WIM_RESHDR_FLAG_SPANNED)
325                 fputs("WIM_RESHDR_FLAG_SPANNED, ", stdout);
326         putchar('\n');
327         if (entry->file_on_disk)
328                 printf("File on Disk      = `%s'\n", entry->file_on_disk);
329         putchar('\n');
330         return 0;
331 }
332
333 /*
334  * Prints the lookup table of a WIM file. 
335  */
336 WIMLIBAPI void wimlib_print_lookup_table(WIMStruct *w)
337 {
338         for_lookup_table_entry(w->lookup_table, 
339                                print_lookup_table_entry, NULL);
340 }
341
342 /* 
343  * Looks up an entry in the lookup table.
344  */
345 struct lookup_table_entry *
346 __lookup_resource(const struct lookup_table *lookup_table, const u8 hash[])
347 {
348         size_t pos;
349         struct lookup_table_entry *lte;
350
351         pos = *(size_t*)hash % lookup_table->capacity;
352         lte = lookup_table->array[pos];
353         while (lte) {
354                 if (memcmp(hash, lte->hash, WIM_HASH_SIZE) == 0)
355                         return lte;
356                 lte = lte->next;
357         }
358         return NULL;
359 }
360
361 int lookup_resource(WIMStruct *w, const char *path,
362                     int lookup_flags,
363                     struct dentry **dentry_ret,
364                     struct lookup_table_entry **lte_ret,
365                     u8 **hash_ret)
366 {
367         struct dentry *dentry = get_dentry(w, path);
368         struct lookup_table_entry *lte;
369         u8 *hash;
370         if (!dentry)
371                 return -ENOENT;
372         if (!(lookup_flags & LOOKUP_FLAG_DIRECTORY_OK)
373               && dentry_is_directory(dentry))
374                 return -EISDIR;
375         if (lookup_flags & LOOKUP_FLAG_ADS_OK) {
376                 const char *stream_name = path_stream_name(path);
377                 if (stream_name) {
378                         size_t stream_name_len = strlen(stream_name);
379                         for (u16 i = 0; i < dentry->num_ads; i++) {
380                                 if (ads_entry_has_name(&dentry->ads_entries[i],
381                                                        stream_name,
382                                                        stream_name_len))
383                                 {
384                                         hash = dentry->ads_entries[i].hash;
385                                         goto do_lookup;
386                                 }
387                         }
388                         return -ENOENT;
389                 }
390         }
391         hash = dentry->hash;
392 do_lookup:
393         lte = __lookup_resource(w->lookup_table, hash);
394         if (dentry_ret)
395                 *dentry_ret = dentry;
396         if (lte_ret)
397                 *lte_ret = lte;
398         if (hash_ret)
399                 *hash_ret = hash;
400         return 0;
401 }