inode updates (IN PROGRESS)
[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 General Public License as published by the Free
15  * Software Foundation; either version 3 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 General Public License for more
21  * details.
22  *
23  * You should have received a copy of the GNU 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 #ifdef WITH_FUSE
33 #include <unistd.h>
34 #endif
35
36 struct lookup_table *new_lookup_table(size_t capacity)
37 {
38         struct lookup_table *table;
39         struct hlist_head *array;
40
41         table = MALLOC(sizeof(struct lookup_table));
42         if (!table)
43                 goto err;
44         array = CALLOC(capacity, sizeof(array[0]));
45         if (!array) {
46                 FREE(table);
47                 goto err;
48         }
49         table->num_entries = 0;
50         table->capacity = capacity;
51         table->array = array;
52         return table;
53 err:
54         ERROR("Failed to allocate memory for lookup table with capacity %zu",
55               capacity);
56         return NULL;
57 }
58
59 struct lookup_table_entry *new_lookup_table_entry()
60 {
61         struct lookup_table_entry *lte;
62         
63         lte = CALLOC(1, sizeof(struct lookup_table_entry));
64         if (!lte) {
65                 ERROR("Out of memory (tried to allocate %zu bytes for "
66                       "lookup table entry)",
67                       sizeof(struct lookup_table_entry));
68                 return NULL;
69         }
70
71         lte->part_number  = 1;
72         lte->refcnt       = 1;
73         return lte;
74 }
75
76 void free_lookup_table_entry(struct lookup_table_entry *lte)
77 {
78         if (lte) {
79 #ifdef WITH_FUSE
80                 if (lte->staging_list.next)
81                         list_del(&lte->staging_list);
82 #endif
83                 switch (lte->resource_location) {
84                 case RESOURCE_IN_STAGING_FILE:
85                 case RESOURCE_IN_ATTACHED_BUFFER:
86                 case RESOURCE_IN_FILE_ON_DISK:
87                         wimlib_assert(((void*)&lte->file_on_disk ==
88                                       (void*)&lte->staging_file_name)
89                                       && ((void*)&lte->file_on_disk ==
90                                       (void*)&lte->attached_buffer));
91                         FREE(lte->file_on_disk);
92                         break;
93 #ifdef WITH_NTFS_3G
94                 case RESOURCE_IN_NTFS_VOLUME:
95                         if (lte->ntfs_loc) {
96                                 FREE(lte->ntfs_loc->path_utf8);
97                                 FREE(lte->ntfs_loc->stream_name_utf16);
98                                 FREE(lte->ntfs_loc);
99                         }
100                         break;
101 #endif
102                 default:
103                         break;
104                 }
105                 FREE(lte->extracted_file);
106                 FREE(lte);
107         }
108 }
109
110 static int do_free_lookup_table_entry(struct lookup_table_entry *entry,
111                                       void *ignore)
112 {
113         free_lookup_table_entry(entry);
114         return 0;
115 }
116
117
118 void free_lookup_table(struct lookup_table *table)
119 {
120         DEBUG2("Freeing lookup table");
121         if (table) {
122                 if (table->array) {
123                         for_lookup_table_entry(table,
124                                                do_free_lookup_table_entry,
125                                                NULL);
126                         FREE(table->array);
127                 }
128                 FREE(table);
129         }
130 }
131
132 /*
133  * Inserts an entry into the lookup table.
134  *
135  * @table:      A pointer to the lookup table.
136  * @entry:      A pointer to the entry to insert.
137  */
138 void lookup_table_insert(struct lookup_table *table, 
139                          struct lookup_table_entry *lte)
140 {
141         size_t i = lte->hash_short % table->capacity;
142         hlist_add_head(&lte->hash_list, &table->array[i]);
143
144         /* XXX Make the table grow when too many entries have been inserted. */
145         table->num_entries++;
146 }
147
148 static void finalize_lte(struct lookup_table_entry *lte)
149 {
150         #ifdef WITH_FUSE
151         if (lte->resource_location == RESOURCE_IN_STAGING_FILE)
152                 unlink(lte->staging_file_name);
153         #endif
154         free_lookup_table_entry(lte);
155 }
156
157 /* Decrements the reference count for the lookup table entry @lte.  If its
158  * reference count reaches 0, it is unlinked from the lookup table.  If,
159  * furthermore, the entry has no opened file descriptors associated with it, the
160  * entry is freed.  */
161 struct lookup_table_entry *
162 lte_decrement_refcnt(struct lookup_table_entry *lte, struct lookup_table *table)
163 {
164         if (lte) {
165                 wimlib_assert(lte->refcnt);
166                 if (--lte->refcnt == 0) {
167                         lookup_table_unlink(table, lte);
168                 #ifdef WITH_FUSE
169                         if (lte->num_opened_fds == 0)
170                 #endif
171                         {
172                                 finalize_lte(lte);
173                                 lte = NULL;
174                         }
175                 }
176         }
177         return lte;
178 }
179
180 #ifdef WITH_FUSE
181 struct lookup_table_entry *
182 lte_decrement_num_opened_fds(struct lookup_table_entry *lte,
183                              struct lookup_table *table)
184 {
185         if (lte) {
186                 wimlib_assert(lte->num_opened_fds);
187                 if (--lte->num_opened_fds == 0 && lte->refcnt == 0) {
188                         lookup_table_unlink(table, lte);
189                         finalize_lte(lte);
190                         lte = NULL;
191                 }
192         }
193         return lte;
194 }
195 #endif
196
197 /* 
198  * Calls a function on all the entries in the lookup table.  Stop early and
199  * return nonzero if any call to the function returns nonzero.
200  */
201 int for_lookup_table_entry(struct lookup_table *table, 
202                            int (*visitor)(struct lookup_table_entry *, void *),
203                            void *arg)
204 {
205         struct lookup_table_entry *lte;
206         struct hlist_node *pos, *tmp;
207         int ret;
208
209         for (size_t i = 0; i < table->capacity; i++) {
210                 hlist_for_each_entry_safe(lte, pos, tmp, &table->array[i],
211                                           hash_list)
212                 {
213                         ret = visitor(lte, arg);
214                         if (ret != 0)
215                                 return ret;
216                 }
217         }
218         return 0;
219 }
220
221
222 /*
223  * Reads the lookup table from a WIM file.
224  */
225 int read_lookup_table(WIMStruct *w)
226 {
227         u64    num_entries;
228         u8     buf[WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE];
229         int    ret;
230         struct lookup_table *table;
231         struct lookup_table_entry *cur_entry = NULL, *duplicate_entry;
232
233         DEBUG("Reading lookup table: offset %"PRIu64", size %"PRIu64"",
234               w->hdr.lookup_table_res_entry.offset,
235               w->hdr.lookup_table_res_entry.original_size);
236
237         if (fseeko(w->fp, w->hdr.lookup_table_res_entry.offset, SEEK_SET) != 0) {
238                 ERROR_WITH_ERRNO("Failed to seek to byte %"PRIu64" to read "
239                                  "lookup table",
240                                  w->hdr.lookup_table_res_entry.offset);
241                 return WIMLIB_ERR_READ;
242         }
243
244         num_entries = w->hdr.lookup_table_res_entry.original_size /
245                       WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE;
246         table = new_lookup_table(num_entries * 2 + 1);
247         if (!table)
248                 return WIMLIB_ERR_NOMEM;
249
250         while (num_entries--) {
251                 const u8 *p;
252
253                 if (fread(buf, 1, sizeof(buf), w->fp) != sizeof(buf)) {
254                         if (feof(w->fp)) {
255                                 ERROR("Unexpected EOF in WIM lookup table!");
256                         } else {
257                                 ERROR_WITH_ERRNO("Error reading WIM lookup "
258                                                  "table");
259                         }
260                         ret = WIMLIB_ERR_READ;
261                         goto out;
262                 }
263                 cur_entry = new_lookup_table_entry();
264                 if (!cur_entry) {
265                         ret = WIMLIB_ERR_NOMEM;
266                         goto out;
267                 }
268                 cur_entry->wim = w;
269                 cur_entry->resource_location = RESOURCE_IN_WIM;
270                          
271                 p = get_resource_entry(buf, &cur_entry->resource_entry);
272                 p = get_u16(p, &cur_entry->part_number);
273                 p = get_u32(p, &cur_entry->refcnt);
274                 p = get_bytes(p, SHA1_HASH_SIZE, cur_entry->hash);
275
276                 if (cur_entry->part_number != w->hdr.part_number) {
277                         ERROR("A lookup table entry in part %hu of the WIM "
278                               "points to part %hu",
279                               w->hdr.part_number, cur_entry->part_number);
280                         ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
281                         goto out_free_cur_entry;
282                         
283                 }
284
285                 if (is_zero_hash(cur_entry->hash)) {
286                         ERROR("The WIM lookup table contains an entry with a "
287                               "SHA1 message digest of all 0's");
288                         ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
289                         goto out_free_cur_entry;
290                 }
291
292                 duplicate_entry = __lookup_resource(table, cur_entry->hash);
293                 if (duplicate_entry) {
294                         ERROR("The WIM lookup table contains two entries with the "
295                               "same SHA1 message digest!");
296                         ERROR("The first entry is:");
297                         print_lookup_table_entry(duplicate_entry);
298                         ERROR("The second entry is:");
299                         print_lookup_table_entry(cur_entry);
300                         ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
301                         goto out_free_cur_entry;
302                 }
303
304                 if (!(cur_entry->resource_entry.flags & WIM_RESHDR_FLAG_COMPRESSED)
305                     && (cur_entry->resource_entry.size !=
306                       cur_entry->resource_entry.original_size))
307                 {
308                         ERROR("Found uncompressed resource with original size "
309                               "not the same as compressed size");
310                         ERROR("The lookup table entry for the resource is as follows:");
311                         print_lookup_table_entry(cur_entry);
312                         ret = WIMLIB_ERR_INVALID_LOOKUP_TABLE_ENTRY;
313                         goto out_free_cur_entry;
314                 }
315                 lookup_table_insert(table, cur_entry);
316
317         }
318         DEBUG("Done reading lookup table.");
319         w->lookup_table = table;
320         return 0;
321 out_free_cur_entry:
322         FREE(cur_entry);
323 out:
324         free_lookup_table(table);
325         return ret;
326 }
327
328
329 /* 
330  * Writes a lookup table entry to the output file.
331  */
332 int write_lookup_table_entry(struct lookup_table_entry *lte, void *__out)
333 {
334         FILE *out;
335         u8 buf[WIM_LOOKUP_TABLE_ENTRY_DISK_SIZE];
336         u8 *p;
337
338         out = __out;
339
340         /* Don't write entries that have not had file resources or metadata
341          * resources written for them. */
342         if (lte->out_refcnt == 0)
343                 return 0;
344
345         if (lte->output_resource_entry.flags & WIM_RESHDR_FLAG_METADATA)
346                 DEBUG("Writing metadata entry at %lu (orig size = %zu)",
347                       ftello(out), lte->output_resource_entry.original_size);
348
349         p = put_resource_entry(buf, &lte->output_resource_entry);
350         p = put_u16(p, lte->part_number);
351         p = put_u32(p, lte->out_refcnt);
352         p = put_bytes(p, SHA1_HASH_SIZE, lte->hash);
353         if (fwrite(buf, 1, sizeof(buf), out) != sizeof(buf)) {
354                 ERROR_WITH_ERRNO("Failed to write lookup table entry");
355                 return WIMLIB_ERR_WRITE;
356         }
357         return 0;
358 }
359
360
361
362 int zero_out_refcnts(struct lookup_table_entry *entry, void *ignore)
363 {
364         entry->out_refcnt = 0;
365         return 0;
366 }
367
368 void print_lookup_table_entry(const struct lookup_table_entry *lte)
369 {
370         if (!lte) {
371                 putchar('\n');
372                 return;
373         }
374         printf("Offset            = %"PRIu64" bytes\n", 
375                lte->resource_entry.offset);
376         printf("Size              = %"PRIu64" bytes\n", 
377                (u64)lte->resource_entry.size);
378         printf("Original size     = %"PRIu64" bytes\n", 
379                lte->resource_entry.original_size);
380         printf("Part Number       = %hu\n", lte->part_number);
381         printf("Reference Count   = %u\n", lte->refcnt);
382         printf("Hash              = 0x");
383         print_hash(lte->hash);
384         putchar('\n');
385         printf("Flags             = ");
386         u8 flags = lte->resource_entry.flags;
387         if (flags & WIM_RESHDR_FLAG_COMPRESSED)
388                 fputs("WIM_RESHDR_FLAG_COMPRESSED, ", stdout);
389         if (flags & WIM_RESHDR_FLAG_FREE)
390                 fputs("WIM_RESHDR_FLAG_FREE, ", stdout);
391         if (flags & WIM_RESHDR_FLAG_METADATA)
392                 fputs("WIM_RESHDR_FLAG_METADATA, ", stdout);
393         if (flags & WIM_RESHDR_FLAG_SPANNED)
394                 fputs("WIM_RESHDR_FLAG_SPANNED, ", stdout);
395         putchar('\n');
396         switch (lte->resource_location) {
397         case RESOURCE_IN_WIM:
398                 if (lte->wim->filename) {
399                         printf("WIM file          = `%s'\n",
400                                lte->wim->filename);
401                 }
402                 break;
403         case RESOURCE_IN_FILE_ON_DISK:
404                 printf("File on Disk      = `%s'\n", lte->file_on_disk);
405                 break;
406         case RESOURCE_IN_STAGING_FILE:
407                 printf("Staging File      = `%s'\n", lte->staging_file_name);
408                 break;
409         default:
410                 break;
411         }
412         putchar('\n');
413 }
414
415 static int do_print_lookup_table_entry(struct lookup_table_entry *lte,
416                                        void *ignore)
417 {
418         print_lookup_table_entry(lte);
419         return 0;
420 }
421
422 /*
423  * Prints the lookup table of a WIM file. 
424  */
425 WIMLIBAPI void wimlib_print_lookup_table(WIMStruct *w)
426 {
427         for_lookup_table_entry(w->lookup_table, 
428                                do_print_lookup_table_entry,
429                                NULL);
430 }
431
432 /* 
433  * Looks up an entry in the lookup table.
434  */
435 struct lookup_table_entry *
436 __lookup_resource(const struct lookup_table *table, const u8 hash[])
437 {
438         size_t i;
439         struct lookup_table_entry *lte;
440         struct hlist_node *pos;
441
442         i = *(size_t*)hash % table->capacity;
443         hlist_for_each_entry(lte, pos, &table->array[i], hash_list)
444                 if (hashes_equal(hash, lte->hash))
445                         return lte;
446         return NULL;
447 }
448
449 /* 
450  * Finds the dentry, lookup table entry, and stream index for a WIM file stream,
451  * given a path name.
452  *
453  * This is only for pre-resolved inodes.
454  */
455 int lookup_resource(WIMStruct *w, const char *path,
456                     int lookup_flags,
457                     struct dentry **dentry_ret,
458                     struct lookup_table_entry **lte_ret,
459                     u16 *stream_idx_ret)
460 {
461         struct dentry *dentry;
462         struct lookup_table_entry *lte;
463         u16 stream_idx;
464         const char *stream_name = NULL;
465         struct inode *inode;
466         char *p = NULL;
467
468         if (lookup_flags & LOOKUP_FLAG_ADS_OK) {
469                 stream_name = path_stream_name(path);
470                 if (stream_name) {
471                         p = (char*)stream_name - 1;
472                         *p = '\0';
473                 }
474         }
475
476         dentry = get_dentry(w, path);
477         if (p)
478                 *p = ':';
479         if (!dentry)
480                 return -ENOENT;
481
482         inode = dentry->inode;
483
484         wimlib_assert(inode->resolved);
485
486         if (!(lookup_flags & LOOKUP_FLAG_DIRECTORY_OK)
487               && inode_is_directory(inode))
488                 return -EISDIR;
489
490         if (stream_name) {
491                 struct ads_entry *ads_entry;
492                 u16 ads_idx;
493                 ads_entry = inode_get_ads_entry(inode, stream_name,
494                                                 &ads_idx);
495                 if (ads_entry) {
496                         stream_idx = ads_idx + 1;
497                         lte = ads_entry->lte;
498                         goto out;
499                 } else {
500                         return -ENOENT;
501                 }
502         } else {
503                 lte = inode->lte;
504                 stream_idx = 0;
505         }
506 out:
507         if (dentry_ret)
508                 *dentry_ret = dentry;
509         if (lte_ret)
510                 *lte_ret = lte;
511         if (stream_idx_ret)
512                 *stream_idx_ret = stream_idx;
513         return 0;
514 }
515
516 static int inode_resolve_ltes(struct inode *inode, struct lookup_table *table)
517 {
518         struct lookup_table_entry *lte;
519
520         /* Resolve the default file stream */
521         lte = __lookup_resource(table, inode->hash);
522         inode->lte = lte;
523         inode->resolved = true;
524
525         /* Resolve the alternate data streams */
526         for (u16 i = 0; i < inode->num_ads; i++) {
527                 struct ads_entry *cur_entry = inode->ads_entries[i];
528
529                 lte = __lookup_resource(table, cur_entry->hash);
530                 cur_entry->lte = lte;
531         }
532         return 0;
533 }
534
535 /* Resolve a dentry's lookup table entries 
536  *
537  * This replaces the SHA1 hash fields (which are used to lookup an entry in the
538  * lookup table) with pointers directly to the lookup table entries.  A circular
539  * linked list of streams sharing the same lookup table entry is created.
540  *
541  * This function always succeeds; unresolved lookup table entries are given a
542  * NULL pointer.
543  */
544 int dentry_resolve_ltes(struct dentry *dentry, void *table)
545 {
546         if (dentry->inode->resolved)
547                 return 0;
548         else
549                 return inode_resolve_ltes(dentry->inode, table);
550 }
551
552
553
554
555 /* Return the lookup table entry for the unnamed data stream of a inode, or
556  * NULL if there is none.
557  *
558  * You'd think this would be easier than it actually is, since the unnamed data
559  * stream should be the one referenced from the inode itself.  Alas, if there
560  * are named data streams, Microsoft's "imagex.exe" program will put the unnamed
561  * data stream in one of the alternate data streams instead of inside the
562  * inode.  So we need to check the alternate data streams too.
563  *
564  * Also, note that a inode may appear to have than one unnamed stream, but if
565  * the SHA1 message digest is all 0's then the corresponding stream does not
566  * really "count" (this is the case for the inode's own file stream when the
567  * file stream that should be there is actually in one of the alternate stream
568  * entries.).  This is despite the fact that we may need to extract such a
569  * missing entry as an empty file or empty named data stream.
570  */
571 struct lookup_table_entry *
572 inode_unnamed_lte(const struct inode *inode,
573                    const struct lookup_table *table)
574 {
575         if (inode->resolved)
576                 return inode_unnamed_lte_resolved(inode);
577         else
578                 return inode_unnamed_lte_unresolved(inode, table);
579 }
580