From: Eric Biggers Date: Sun, 19 Aug 2012 01:58:51 +0000 (-0500) Subject: hardlinks (IN PROGRESS) X-Git-Tag: v1.0.0~141 X-Git-Url: https://wimlib.net/git/?p=wimlib;a=commitdiff_plain;h=da2c501c4ca54063126290c2103f607e926c9989 hardlinks (IN PROGRESS) --- diff --git a/src/dentry.c b/src/dentry.c index e5af01ba..e47f8380 100644 --- a/src/dentry.c +++ b/src/dentry.c @@ -80,6 +80,11 @@ void stbuf_to_dentry(const struct stat *stbuf, struct dentry *dentry) } else { dentry->attributes = FILE_ATTRIBUTE_NORMAL; } + if (sizeof(ino_t) >= 8) + dentry->hard_link = (u64)stbuf->st_ino; + else + dentry->hard_link = (u64)stbuf->st_ino | + ((u64)stbuf->st_dev << (sizeof(ino_t) * 8)); } /* Transfers file attributes from a struct dentry to a `stat' buffer. */ diff --git a/src/dentry.h b/src/dentry.h index c1d16776..26832a50 100644 --- a/src/dentry.h +++ b/src/dentry.h @@ -3,8 +3,10 @@ #include "util.h" #include "config.h" +#include "list.h" #include + struct stat; struct lookup_table; typedef struct WIMStruct WIMStruct; @@ -186,10 +188,8 @@ struct dentry { * WIMStructs */ int refcnt; - /* Next dentry in the hard link set */ - //struct dentry *next_dentry_in_link_set; - /* Next hard link that has a lookup table entry */ - //struct dentry *next_link_set; + /* List of dentries in the hard link set */ + struct list_head link_group_list; }; /* Return hash of the "unnamed" (default) data stream. */ diff --git a/src/hardlink.c b/src/hardlink.c new file mode 100644 index 00000000..929837e5 --- /dev/null +++ b/src/hardlink.c @@ -0,0 +1,146 @@ +#include "wimlib_internal.h" +#include "dentry.h" +#include "list.h" +#include "lookup_table.h" + +struct link_group { + u64 link_group_id; + struct link_group *next; + struct list_head *link_group_head; +}; + +struct link_group_table { + struct link_group **array; + u64 num_entries; + u64 capacity; +}; + + +struct link_group_table *new_link_group_table(u64 capacity) +{ + return (struct link_group_table*)new_lookup_table(capacity); +} + +/* Insert a dentry into the hard link group table based on its hard link group + * ID. + * + * If there is already a dentry in the table having the same hard link group ID, + * we link the dentries together in a circular list. + * + * If the hard link group ID is 0, this is a no-op and the dentry is not + * inserted. + */ +int link_group_table_insert(struct dentry *dentry, struct link_group_table *table) +{ + size_t pos; + struct link_group *group; + + if (dentry->hard_link == 0) + return 0; + + /* Try adding to existing hard link group */ + pos = dentry->hard_link % table->capacity; + group = table->array[pos]; + while (group) { + if (group->link_group_id == dentry->hard_link) { + list_add(&dentry->link_group_list, group->link_group_head); + return 0; + } + group = group->next; + } + + /* Add new hard link group to the table */ + + group = MALLOC(sizeof(struct link_group)); + if (!group) + return WIMLIB_ERR_NOMEM; + INIT_LIST_HEAD(&dentry->link_group_list); + group->link_group_id = dentry->hard_link; + group->next = table->array[pos]; + group->link_group_head = &dentry->link_group_list; + table->array[pos] = group; + + /* XXX Make the table grow when too many entries have been inserted. */ + table->num_entries++; + return 0; +} + +/* Frees a link group table. */ +void free_link_group_table(struct link_group_table *table) +{ + if (!table) + return; + if (table->array) { + for (u64 i = 0; i < table->capacity; i++) { + struct link_group *group = table->array[i]; + struct link_group *next; + while (group) { + next = group->next; + FREE(group); + group = next; + } + } + FREE(table->array); + } + FREE(table); +} + +/* Assign the link group IDs to dentries in a link group table, and return the + * next available link group ID. */ +u64 assign_link_groups(struct link_group_table *table) +{ + struct link_group *remaining_groups = NULL; + u64 id = 1; + for (u64 i = 0; i < table->capacity; i++) { + struct link_group *group = table->array[i]; + struct link_group *next_group; + struct dentry *dentry; + while (group) { + next_group = group->next; + if (list_empty(group->link_group_head)) { + /* Hard link group of size 1. Change the hard + * link ID to 0 and discard the link_group */ + dentry = container_of(group->link_group_head, + struct dentry, + link_group_list); + dentry->hard_link = 0; + FREE(group); + } else { + /* Hard link group of size > 1. Assign the + * dentries in the group the next available hard + * link IDs and queue the group to be + * re-inserted into the table. */ + list_for_each_entry(dentry, group->link_group_head, + link_group_list) + dentry->hard_link = id; + group->next = remaining_groups; + remaining_groups = group; + id++; + } + group = next_group; + } + } + memset(table->array, 0, table->capacity * sizeof(table->array[0])); + table->num_entries = 0; + while (remaining_groups) { + struct link_group *group = remaining_groups; + size_t pos = group->link_group_id % table->capacity; + + table->num_entries++; + group->next = table->array[pos]; + table->array[pos] = group; + remaining_groups = remaining_groups->next; + } + return id; +} + +#if 0 +/* Load a dentry tree into the link group table */ +int load_link_groups(struct link_group_table *table, struct dentry *root) +{ + int ret = for_dentry_in_tree(dentry, link_group_table_insert, table); + if (ret == 0) + assign_link_groups(table); + return ret; +} +#endif diff --git a/src/lookup_table.c b/src/lookup_table.c index c0369a9f..2177cb1b 100644 --- a/src/lookup_table.c +++ b/src/lookup_table.c @@ -129,7 +129,7 @@ bool lookup_table_decrement_refcnt(struct lookup_table* table, const u8 hash[]) if (memcmp(hash, entry->hash, WIM_HASH_SIZE) == 0) { wimlib_assert(entry->refcnt != 0); if (--entry->refcnt == 0) { - if (entry->staging_num_times_opened == 0) + if (entry->num_opened_fds == 0) free_lookup_table_entry(entry); if (prev) prev->next = next; @@ -361,7 +361,7 @@ int lookup_resource(WIMStruct *w, const char *path, { struct dentry *dentry = get_dentry(w, path); struct lookup_table_entry *lte; - const u8 *hash; + u8 *hash; if (!dentry) return -ENOENT; if (!(lookup_flags & LOOKUP_FLAG_DIRECTORY_OK) diff --git a/src/lookup_table.h b/src/lookup_table.h index faf62a02..f257aa3f 100644 --- a/src/lookup_table.h +++ b/src/lookup_table.h @@ -21,6 +21,8 @@ struct lookup_table { u64 capacity; }; +struct wimlib_fd; + /* An entry in the lookup table in the WIM file. */ struct lookup_table_entry { @@ -80,23 +82,9 @@ struct lookup_table_entry { /* Compression type used in other WIM. */ int other_wim_ctype; }; - - struct { /* Used for read-write mounts. */ - - - /* Offset of the stream file_on_disk_fd. */ - off_t staging_offset; - - - /* If file_on_disk_fd, if it is not -1, is the file - * descriptor, opened for reading, for file_on_disk. */ - int staging_fd; - - /* Number of times the file has been opened. - * file_on_disk_fd can be closed when num_times_opened - * is decremented to 0. */ - int staging_num_times_opened; - }; + struct wimlib_fd *fds; + u16 num_allocated_fds; + u16 num_opened_fds; }; /* When a WIM file is written, out_refcnt starts at 0 and is incremented diff --git a/src/modify.c b/src/modify.c index 29b16081..fab9ee05 100644 --- a/src/modify.c +++ b/src/modify.c @@ -47,6 +47,7 @@ static void destroy_image_metadata(struct image_metadata *imd, { free_dentry_tree(imd->root_dentry, lt, true); free_security_data(imd->security_data); + free_link_group_table(imd->lgt); /* Get rid of the lookup table entry for this image's metadata resource * */ @@ -252,11 +253,13 @@ static int add_lookup_table_entry_to_dest_wim(struct dentry *dentry, void *arg) if (dentry_is_directory(dentry)) return 0; - src_table_entry = wim_lookup_resource(src_wim, dentry); + /* XXX ADS */ + src_table_entry = __lookup_resource(src_wim->lookup_table, dentry->hash); if (!src_table_entry) return 0; - dest_table_entry = wim_lookup_resource(dest_wim, dentry); + /* XXX ADS */ + dest_table_entry = __lookup_resource(dest_wim->lookup_table, dentry->hash); if (dest_table_entry) { dest_table_entry->refcnt++; } else { @@ -568,6 +571,12 @@ WIMLIBAPI int wimlib_add_image(WIMStruct *w, const char *dir, if (ret != 0) goto out_free_dentry_tree; + ret = for_dentry_in_tree(root_dentry, link_group_table_insert, + &w->image_metadata[w->hdr.image_count - 1].lgt); + if (ret != 0) + goto out_destroy_imd; + assign_link_groups(w->image_metadata[w->hdr.image_count - 1].lgt); + if (flags & WIMLIB_ADD_IMAGE_FLAG_BOOT) wimlib_set_boot_idx(w, w->hdr.image_count); diff --git a/src/mount.c b/src/mount.c index f4f30d11..364d84dc 100644 --- a/src/mount.c +++ b/src/mount.c @@ -45,6 +45,12 @@ #include #include +struct wimlib_fd { + int staging_fd; + u64 hard_link_group; + struct lookup_table_entry *lte; +}; + /* The WIMStruct for the mounted WIM. */ static WIMStruct *w; @@ -74,6 +80,55 @@ static inline int get_lookup_flags() return 0; } +static inline int flags_writable(int open_flags) +{ + return open_flags & (O_RDWR | O_WRONLY); +} + +static int alloc_fd(struct lookup_table_entry *lte, struct wimlib_fd **fd_ret) +{ + struct wimlib_fd *fds, *fd; + if (lte->num_opened_fds == lte->num_allocated_fds) { + if (lte->num_allocated_fds > 0xffff - 8) + return -ENFILE; + + fds = CALLOC(lte->num_allocated_fds + 8, sizeof(struct wimlib_fd)); + if (!fds) + return -ENOMEM; + memcpy(fds, lte->fds, + lte->num_allocated_fds * sizeof(struct wimlib_fd)); + FREE(lte->fds); + lte->fds = fds; + } + fd = lte->fds; + while (1) { + if (!fd->lte) { + fd->hard_link_group = 0; + fd->staging_fd = -1; + fd->lte = lte; + *fd_ret = fd; + return 0; + } + fd++; + } +} + +static int close_fd(struct wimlib_fd *fd) +{ + struct lookup_table_entry *lte = fd->lte; + wimlib_assert(lte); + wimlib_assert(lte->num_opened_fds); + + u16 idx = fd - lte->fds; + if (lte->staging_file_name && fd->staging_fd != -1) + if (close(fd->staging_fd) != 0) + return -errno; + if (--lte->num_opened_fds == 0 && lte->refcnt == 0) + free_lookup_table_entry(lte); + fd->lte = NULL; + return 0; +} + /* * Creates a randomly named staging directory and returns its name into the * static variable staging_dir_name. @@ -308,13 +363,15 @@ static int wimfs_access(const char *path, int mask) /* Closes the staging file descriptor associated with the lookup table entry, if * it is opened. */ -static int close_staging_file(struct lookup_table_entry *lte, void *ignore) +static int close_lte_fds(struct lookup_table_entry *lte, void *ignore) { - if (lte->staging_file_name && lte->staging_num_times_opened) { - if (close(lte->staging_fd) != 0) { - ERROR_WITH_ERRNO("Failed close file `%s'", - lte->staging_file_name); - return WIMLIB_ERR_WRITE; + for (u16 i = 0; i < lte->num_opened_fds; i++) { + if (lte->fds[i].lte && lte->fds[i].staging_fd != -1) { + if (close(lte->fds[i].staging_fd) != 0) { + ERROR_WITH_ERRNO("Failed close file `%s'", + lte->staging_file_name); + return WIMLIB_ERR_WRITE; + } } } return 0; @@ -373,7 +430,7 @@ static int rebuild_wim(WIMStruct *w, bool check_integrity) DEBUG("Closing all staging file descriptors."); /* Close all the staging file descriptors. */ - ret = for_lookup_table_entry(w->lookup_table, close_staging_file, NULL); + ret = for_lookup_table_entry(w->lookup_table, close_lte_fds, NULL); if (ret != 0) { ERROR("Failed to close all staging files"); return ret; @@ -558,7 +615,7 @@ static int create_staging_file(char **name_ret, int open_flags) DEBUG("Creating staging file `%s'", name); - fd = open(name, mode | O_CREAT | O_TRUNC, 0600); + fd = open(name, open_flags | O_CREAT | O_TRUNC, 0600); if (fd == -1) { errno_save = errno; FREE(name); @@ -615,6 +672,7 @@ static int wimfs_open(const char *path, struct fuse_file_info *fi) struct lookup_table_entry *lte; u8 *dentry_hash; int ret; + struct wimlib_fd *fd; ret = lookup_resource(w, path, get_lookup_flags(), &dentry, <e, &dentry_hash); @@ -622,30 +680,37 @@ static int wimfs_open(const char *path, struct fuse_file_info *fi) return ret; if (lte) { - /* If this file is in the staging directory and the file is not - * currently open, open it. */ + /* Common case--- there's a lookup table entry for a file. + * Allocate a new file descriptor for it. */ + + ret = alloc_fd(lte, &fd); + if (ret != 0) + return ret; + + /* The file resource may be in the staging directory (read-write + * mounts only) or in the WIM. If it's in the staging + * directory, we need to open a native file descriptor for the + * corresponding file. Otherwise, we can read the file resource + * directly from the WIM file if we are opening it read-only, + * but we need to extract the resource to the staging directory + * if we are opening it writable. */ if (lte->staging_file_name) { - if (lte->staging_num_times_opened == 0) { - lte->staging_fd = open(lte->staging_file_name, O_RDWR); - if (lte->staging_fd == -1) - return -errno; - lte->staging_offset = 0; + fd->staging_fd = open(lte->staging_file_name, fi->flags); + if (fd->staging_fd == -1) { + close_fd(fd); + return -errno; } - } else { - /* File in the WIM. We must extract it to the staging directory - * before it can be written to. */ - ret = extract_resource_to_staging_dir(dentry_hash, lte, + } else if (flags_writable(fi->flags)) { + + ret = extract_resource_to_staging_dir(lte, lte->resource_entry.original_size); - if (ret != 0) - return ret; } } else { /* Empty file with no lookup-table entry. This is fine if it's - * a read-only filesystem. Otherwise we need to move the file - * to the staging directory with a new lookup table entry, even - * if we aren't opening it for writing at the moment, so that we - * will have a lookup table entry for the file in case it's - * changed. */ + * a read-only filesystem. Otherwise we need to create a lookup + * table entry so that we can keep track of the file descriptors + * (this is important in case someone opens the file for + * writing) */ if (!(mount_flags & WIMLIB_MOUNT_FLAG_READWRITE)) { fi->fd = 0; return 0; @@ -667,8 +732,7 @@ static int wimfs_open(const char *path, struct fuse_file_info *fi) lte->staging_fd = fd; lookup_table_insert(w->lookup_table, lte); } - lte->staging_num_times_opened++; - fi->fd = (uint64_t)lte; + fi->fd = (uint64_t)fd; return 0; } @@ -689,36 +753,25 @@ static int wimfs_opendir(const char *path, struct fuse_file_info *fi) * Read data from a file in the WIM or in the staging directory. */ static int wimfs_read(const char *path, char *buf, size_t size, - off_t offset, struct fuse_file_info *fi) + off_t offset, struct fuse_file_info *fi) { - struct lookup_table_entry *lte; - - lte = (struct lookup_table_entry*)fi->fh; - if (!lte) - return 0; + struct wimlib_fd *fd = (struct wimlib_fd*)fi->fh; - if (lte->staging_file_name) { + wimlib_assert(fd->lte); + wimlib_assert(fd->lte->staging_dir_name); - /* Read from staging */ - int fd; - off_t cur_offset; - ssize_t ret; + if (fd->lte->staging_file_name) { + /* Read from staging file */ - if (lte->staging_num_times_opened == 0) - return -EBADF; + wimlib_assert(fd->staging_fd != -1); - fd = lte->staging_fd; - cur_offset = lte->staging_offset; - if (cur_offset != offset) - if (lseek(fd, offset, SEEK_SET) == -1) - return -errno; - lte->staging_offset = offset; + ssize_t ret; - ret = read(fd, buf, size); + if (lseek(fd->staging_fd, offset, SEEK_SET) == -1) + return -errno; + ret = read(fd->staging_fd, buf, size); if (ret == -1) return -errno; - lte->staging_offset = offset + ret; - return ret; } else { @@ -786,22 +839,12 @@ static int wimfs_readlink(const char *path, char *buf, size_t buf_len) /* Close a file. */ static int wimfs_release(const char *path, struct fuse_file_info *fi) { - struct lookup_table_entry *lte; int ret; - - lte = (struct lookup_table_entry*)fi->fh; + struct wimlib_fd *fd = (struct wimlib_fd*)fi->fh; - if (!lte || lte->staging_num_times_opened == 0) - return -EBADF; - - if (--lte->staging_num_times_opened == 0 && lte->staging_file_name) { - ret = close(lte->staging_fd); - if (lte->refcnt == 0) - free_lookup_table_entry(lte); - if (ret != 0) - return -errno; - } - return 0; + wimlib_assert(fd->lte); + wimlib_assert(fd->num_opened_fds); + return close_fd(fd); } /* Renames a file or directory. See rename (3) */ @@ -864,26 +907,26 @@ static int wimfs_rmdir(const char *path) return 0; } -/* Extracts the resource corresponding to @dentry and its lookup table entry - * @lte to a file in the staging directory. The lookup table entry for @dentry - * is updated to point to the new file. If @lte has multiple dentries - * referencing it, a new lookup table entry is created and the hash of @dentry - * is changed to point to the new lookup table entry. - * +/* + * Extract a WIM resource to the staging directory. * Only @size bytes are extracted, to support truncating the file. * - * Returns the negative error code on failure. + * We need to: + * - Create a staging file for the WIM resource + * - Extract the resource to it + * - Create a new lte for the file resource + * - Transfer fds from the old lte to the new lte, but + * only if they share the same hard link group as this + * dentry */ -static int extract_resource_to_staging_dir(u8 *dentry_hash, - struct lookup_table_entry *lte, +static int extract_resource_to_staging_dir(struct lookup_table_entry *lte, u64 size) { - int fd; - bool ret; char *staging_file_name; + int ret; + int fd; struct lookup_table_entry *new_lte; - - /* File in WIM. Copy it to the staging directory. */ + fd = create_staging_file(&staging_file_name); if (fd == -1) return -errno; @@ -899,7 +942,13 @@ static int extract_resource_to_staging_dir(u8 *dentry_hash, return ret; } - if (lte->refcnt != 1) { + /* XXX + * Need to figure out how to avoid creating orphan lookup table entries. + * XXX + */ + if (lte->refcnt == 1) { + new_lte = lte; + } else { /* Need to make a new lookup table entry if we are * changing only one copy of a hardlinked entry */ lte->refcnt--; @@ -1034,13 +1083,12 @@ static int wimfs_utimens(const char *path, const struct timespec tv[2]) static int wimfs_write(const char *path, const char *buf, size_t size, off_t offset, struct fuse_file_info *fi) { - /* Grab our lookup table entry from the FUSE file info structure. */ - struct lookup_table_entry *lte; - lte = (struct lookup_table_entry*)fi->fh; + struct wimlib_fd *fd = (struct wimlib_fd*)fi->fh; int ret; - if (!lte || !lte->staging_file_name) - return -EBADF; + wimlib_assert(fd->lte); + wimlib_assert(fd->lte->staging_dir_name); + wimlib_assert(fd->staging_fd != -1); /* Seek to correct position in file if needed. */ if (lte->staging_offset != offset) { diff --git a/src/resource.c b/src/resource.c index 03754e08..a1268fbf 100644 --- a/src/resource.c +++ b/src/resource.c @@ -925,6 +925,7 @@ int read_metadata_resource(FILE *fp, int wim_ctype, struct image_metadata *imd) const struct resource_entry *res_entry; struct dentry *dentry; struct wim_security_data *sd; + struct link_group_table *lgt; res_entry = &imd->metadata_lte->resource_entry; @@ -1000,13 +1001,23 @@ int read_metadata_resource(FILE *fp, int wim_ctype, struct image_metadata *imd) if (ret != 0) goto out_free_dentry_tree; + lgt = new_link_group_table(9001); + if (!lgt) + goto out_free_dentry_tree; + ret = for_dentry_in_tree(dentry, link_group_table_insert, lgt); + if (ret != 0) + goto out_free_lgt; + + imd->lgt = lgt; imd->security_data = sd; - imd->root_dentry = dentry; + imd->root_dentry = dentry; goto out_free_buf; -out_free_security_data: - free_security_data(sd); +out_free_lgt: + free_link_group_table(sgt); out_free_dentry_tree: free_dentry_tree(dentry, NULL, false); +out_free_security_data: + free_security_data(sd); out_free_buf: FREE(buf); return ret; diff --git a/src/wimlib_internal.h b/src/wimlib_internal.h index b59b0549..ec1f2807 100644 --- a/src/wimlib_internal.h +++ b/src/wimlib_internal.h @@ -208,6 +208,9 @@ struct wim_security_data { u32 refcnt; } WIMSecurityData; +struct link_group_table; + + /* Metadata resource for an image. */ struct image_metadata { /* Pointer to the root dentry for the image. */ @@ -220,6 +223,9 @@ struct image_metadata { * resource. */ struct lookup_table_entry *metadata_lte; + /* Hard link group table */ + struct link_group_table *lgt; + /* True if the filesystem of the image has been modified. If this is * the case, the memory for the filesystem is not freed when switching * to a different WIM image. */ @@ -320,6 +326,14 @@ static inline void print_hash(const u8 hash[]) print_byte_field(hash, WIM_HASH_SIZE); } +/* hardlink.c */ + +struct link_group_table *new_link_group_table(u64 capacity); +int link_group_table_insert(struct dentry *dentry, + struct link_group_table *table); +void free_link_group_table(struct link_group_table *table); +u64 assign_link_groups(struct link_group_table *table); + /* header.c */ extern int read_header(FILE *fp, struct wim_header *hdr, int split_ok);