X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Fntfs-3g_capture.c;h=6bdb46484d7150d6c39f2940b95f920a6f9a0c8d;hb=c07877105822d01725b36b011c93609559164b06;hp=c26ca605382d86c970d5ce9cb4f226795b84e862;hpb=1fc939b7bd0b37900d974b1cd5b11df128df71f5;p=wimlib diff --git a/src/ntfs-3g_capture.c b/src/ntfs-3g_capture.c index c26ca605..6bdb4648 100644 --- a/src/ntfs-3g_capture.c +++ b/src/ntfs-3g_capture.c @@ -6,7 +6,7 @@ */ /* - * Copyright (C) 2012, 2013 Eric Biggers + * Copyright (C) 2012, 2013, 2014 Eric Biggers * * This file is part of wimlib, a library for working with WIM files. * @@ -155,14 +155,13 @@ out: } -/* Load the streams from a file or reparse point in the NTFS volume into the WIM - * lookup table */ +/* Load the streams from a file or reparse point in the NTFS volume */ static int capture_ntfs_streams(struct wim_inode *inode, ntfs_inode *ni, char *path, size_t path_len, - struct wim_lookup_table *lookup_table, + struct list_head *unhashed_streams, ntfs_volume *vol, ATTR_TYPES type) { @@ -183,7 +182,7 @@ capture_ntfs_streams(struct wim_inode *inode, /* Capture each data stream or reparse data stream. */ while (!ntfs_attr_lookup(type, NULL, 0, - WIMLIB_CASE_SENSITIVE, 0, NULL, 0, actx)) + CASE_SENSITIVE, 0, NULL, 0, actx)) { u64 data_size = ntfs_get_attribute_value_length(actx->attr); u64 name_length = actx->attr->name_length; @@ -246,12 +245,19 @@ capture_ntfs_streams(struct wim_inode *inode, * dentry's inode. */ if (inode->i_lte) { if (lte) { - ERROR("Found two un-named data streams for \"%s\" " - "(sizes = %"PRIu64", %"PRIu64")", - path, inode->i_lte->size, - lte->size); - ret = WIMLIB_ERR_NTFS_3G; - goto out_free_lte; + if (!(inode->i_attributes & + FILE_ATTRIBUTE_REPARSE_POINT)) + { + WARNING("Found two un-named " + "data streams for \"%s\" " + "(sizes = %"PRIu64", " + "%"PRIu64")", + path, + inode->i_lte->size, + lte->size); + } + free_lookup_table_entry(lte); + continue; } } else { stream_id = 0; @@ -274,8 +280,8 @@ capture_ntfs_streams(struct wim_inode *inode, new_ads_entry->lte = lte; } if (lte) { - lookup_table_insert_unhashed(lookup_table, lte, - inode, stream_id); + add_unhashed_stream(lte, inode, + stream_id, unhashed_streams); } } if (errno == ENOENT) { @@ -302,27 +308,35 @@ out_put_actx: return ret; } -/* Red-black tree that maps NTFS inode numbers to DOS names */ +/* Binary tree that maps NTFS inode numbers to DOS names */ struct dos_name_map { - struct rb_root rb_root; + struct avl_tree_node *root; }; struct dos_name_node { - struct rb_node rb_node; + struct avl_tree_node index_node; char dos_name[24]; int name_nbytes; le64 ntfs_ino; }; +#define DOS_NAME_NODE(avl_node) \ + avl_tree_entry(avl_node, struct dos_name_node, index_node) + +static int +_avl_cmp_by_ntfs_ino(const struct avl_tree_node *n1, + const struct avl_tree_node *n2) +{ + return cmp_u64(DOS_NAME_NODE(n1)->ntfs_ino, + DOS_NAME_NODE(n2)->ntfs_ino); +} + /* Inserts a new DOS name into the map */ static int insert_dos_name(struct dos_name_map *map, const ntfschar *dos_name, size_t name_nbytes, le64 ntfs_ino) { struct dos_name_node *new_node; - struct rb_node **p; - struct rb_root *root; - struct rb_node *rb_parent; DEBUG("DOS name_len = %zu", name_nbytes); new_node = MALLOC(sizeof(struct dos_name_node)); @@ -334,35 +348,23 @@ insert_dos_name(struct dos_name_map *map, const ntfschar *dos_name, wimlib_assert(name_nbytes <= sizeof(new_node->dos_name)); /* Initialize the DOS name, DOS name length, and NTFS inode number of - * the red-black tree node */ + * the search tree node */ memcpy(new_node->dos_name, dos_name, name_nbytes); new_node->name_nbytes = name_nbytes; new_node->ntfs_ino = ntfs_ino; - /* Insert the red-black tree node */ - root = &map->rb_root; - p = &root->rb_node; - rb_parent = NULL; - while (*p) { - struct dos_name_node *this; - - this = container_of(*p, struct dos_name_node, rb_node); - rb_parent = *p; - if (new_node->ntfs_ino < this->ntfs_ino) - p = &((*p)->rb_left); - else if (new_node->ntfs_ino > this->ntfs_ino) - p = &((*p)->rb_right); - else { - /* This should be impossible since a NTFS inode cannot - * have multiple DOS names, and we only should get each - * DOS name entry once from the ntfs_readdir() calls. */ - ERROR("NTFS inode %"PRIu64" has multiple DOS names", - le64_to_cpu(ntfs_ino)); - return -1; - } + /* Insert the search tree node */ + if (avl_tree_insert(&map->root, &new_node->index_node, + _avl_cmp_by_ntfs_ino)) + { + /* This should be impossible since a NTFS inode cannot + * have multiple DOS names, and we only should get each + * DOS name entry once from the ntfs_readdir() calls. */ + ERROR("NTFS inode %"PRIu64" has multiple DOS names", + le64_to_cpu(ntfs_ino)); + FREE(new_node); + return -1; } - rb_link_node(&new_node->rb_node, rb_parent, p); - rb_insert_color(&new_node->rb_node, root); DEBUG("Inserted DOS name for inode %"PRIu64, le64_to_cpu(ntfs_ino)); return 0; } @@ -372,24 +374,21 @@ insert_dos_name(struct dos_name_map *map, const ntfschar *dos_name, static struct dos_name_node * lookup_dos_name(const struct dos_name_map *map, u64 ntfs_ino) { - struct rb_node *node = map->rb_root.rb_node; - while (node) { - struct dos_name_node *this; - this = container_of(node, struct dos_name_node, rb_node); - if (ntfs_ino < this->ntfs_ino) - node = node->rb_left; - else if (ntfs_ino > this->ntfs_ino) - node = node->rb_right; - else - return this; - } - return NULL; + struct dos_name_node dummy; + struct avl_tree_node *res; + + dummy.ntfs_ino = cpu_to_le64(ntfs_ino); + + res = avl_tree_lookup_node(map->root, &dummy.index_node, + _avl_cmp_by_ntfs_ino); + if (!res) + return NULL; + return DOS_NAME_NODE(res); } static int -set_dentry_dos_name(struct wim_dentry *dentry, void *arg) +set_dentry_dos_name(struct wim_dentry *dentry, const struct dos_name_map *map) { - const struct dos_name_map *map = arg; const struct dos_name_node *node; if (dentry->is_win32_name) { @@ -414,18 +413,18 @@ set_dentry_dos_name(struct wim_dentry *dentry, void *arg) } static void -free_dos_name_tree(struct rb_node *node) { +free_dos_name_tree(struct avl_tree_node *node) { if (node) { - free_dos_name_tree(node->rb_left); - free_dos_name_tree(node->rb_right); - FREE(container_of(node, struct dos_name_node, rb_node)); + free_dos_name_tree(node->left); + free_dos_name_tree(node->right); + FREE(DOS_NAME_NODE(node)); } } static void destroy_dos_name_map(struct dos_name_map *map) { - free_dos_name_tree(map->rb_root.rb_node); + free_dos_name_tree(map->root); } struct readdir_ctx { @@ -536,7 +535,6 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_ret, int ret; struct wim_dentry *root = NULL; struct wim_inode *inode = NULL; - ATTR_TYPES stream_type; if (exclude_path(path, path_len, params->config, false)) { /* Exclude a file or directory tree based on the capture @@ -592,20 +590,30 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_ret, inode->i_attributes = le32_to_cpu(attributes); inode->i_resolved = 1; - if (attributes & FILE_ATTR_REPARSE_POINT) - stream_type = AT_REPARSE_POINT; - else - stream_type = AT_DATA; + /* Capture streams. */ + + if (attributes & FILE_ATTR_REPARSE_POINT) { + /* Capture reparse data stream. */ + ret = capture_ntfs_streams(inode, ni, path, path_len, + params->unhashed_streams, + vol, AT_REPARSE_POINT); + if (ret) + goto out; + } - /* Capture the file's streams; more specifically, this is supposed to: + /* Capture data streams. * - * - Regular files: capture unnamed data stream and any named data - * streams - * - Directories: capture any named data streams - * - Reparse points: capture reparse data only - */ + * Directories should not have an unnamed data stream, but they may have + * named data streams. + * + * Reparse points may have an unnamed data stream (which will be ignored + * in favor of the reparse data stream), and they also may have named + * data streams. + * + * Regular files can have an unnamed data stream as well as named data + * streams. */ ret = capture_ntfs_streams(inode, ni, path, path_len, - params->lookup_table, vol, stream_type); + params->unhashed_streams, vol, AT_DATA); if (ret) goto out; @@ -613,7 +621,7 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_ret, /* Recurse to directory children */ s64 pos = 0; - struct dos_name_map dos_name_map = { .rb_root = {.rb_node = NULL} }; + struct dos_name_map dos_name_map = { .root = NULL }; struct readdir_ctx ctx = { .parent = root, .path = path, @@ -627,8 +635,14 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_ret, ERROR_WITH_ERRNO("Error reading directory \"%s\"", path); ret = WIMLIB_ERR_NTFS_3G; } else { - ret = for_dentry_child(root, set_dentry_dos_name, - &dos_name_map); + struct wim_dentry *child; + + ret = 0; + for_dentry_child(child, root) { + ret = set_dentry_dos_name(child, &dos_name_map); + if (ret) + break; + } } destroy_dos_name_map(&dos_name_map); if (ret)