wimlib.net Git - wimlib/blob - src/hardlink.c

   1 /*
   2  * hardlink.c
   3  *
   4  * Code to deal with hard links in WIMs.  Essentially, the WIM dentries are put
   5  * into a hash table indexed by the hard link group ID field, then for each hard
   6  * link group, a linked list is made to connect the dentries.
   7  */
   8
   9 /*
  10  * Copyright (C) 2012 Eric Biggers
  11  *
  12  * This file is part of wimlib, a library for working with WIM files.
  13  *
  14  * wimlib is free software; you can redistribute it and/or modify it under the
  15  * terms of the GNU Lesser General Public License as published by the Free
  16  * Software Foundation; either version 2.1 of the License, or (at your option)
  17  * any later version.
  18  *
  19  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
  20  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  21  * A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
  22  * details.
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * along with wimlib; if not, see http://www.gnu.org/licenses/.
  26  */
  27
  28 #include "wimlib_internal.h"
  29 #include "dentry.h"
  30 #include "list.h"
  31 #include "lookup_table.h"
  32
  33 /* Hard link group; it's identified by its hard link group ID and consists of a
  34  * circularly linked list of dentries. */
  35 struct link_group {
  36         u64 link_group_id;
  37         struct link_group *next;
  38         struct list_head *dentry_list;
  39 };
  40
  41 /* Hash table to find hard link groups, identified by their hard link group ID.
  42  * */
  43 struct link_group_table {
  44         struct link_group **array;
  45         u64 num_entries;
  46         u64 capacity;
  47         struct link_group *singles;
  48 };
  49
  50 /* Returns pointer to a new link group table having the specified capacity */
  51 struct link_group_table *new_link_group_table(u64 capacity)
  52 {
  53         struct link_group_table *table;
  54         struct link_group **array;
  55
  56         table = MALLOC(sizeof(struct link_group_table));
  57         if (!table)
  58                 goto err;
  59         array = CALLOC(capacity, sizeof(array[0]));
  60         if (!array) {
  61                 FREE(table);
  62                 goto err;
  63         }
  64         table->num_entries = 0;
  65         table->capacity = capacity;
  66         table->array = array;
  67         table->singles = NULL;
  68         return table;
  69 err:
  70         ERROR("Failed to allocate memory for link group table with capacity %zu",
  71               capacity);
  72         return NULL;
  73 }
  74
  75 /*
  76  * Insert a dentry into the hard link group table based on its hard link group
  77  * ID.
  78  *
  79  * If there is already a dentry in the table having the same hard link group ID,
  80  * we link the dentries together in a circular list.
  81  *
  82  * If the hard link group ID is 0, this indicates a dentry that's in a hard link
  83  * group by itself (has a link count of 1).  We can't insert it into the hash
  84  * table itself because we don't know what hard link group IDs are available to
  85  * give it (this could be kept track of but would be more difficult).  Instead
  86  * we keep a linked list of the single dentries, and assign them hard link group
  87  * IDs later.
  88  */
  89 int link_group_table_insert(struct dentry *dentry, void *__table)
  90 {
  91         struct link_group_table *table = __table;
  92         size_t pos;
  93         struct link_group *group;
  94
  95         if (dentry->hard_link == 0) {
  96                 /* Single group--- Add to the singles list (we can't put it in
  97                  * the table itself because all the singles have a link group ID
  98                  * of 0) */
  99                 group = MALLOC(sizeof(struct link_group));
 100                 if (!group)
 101                         return WIMLIB_ERR_NOMEM;
 102                 group->link_group_id = 0;
 103                 group->next          = table->singles;
 104                 table->singles       = group;
 105                 INIT_LIST_HEAD(&dentry->link_group_list);
 106                 group->dentry_list = &dentry->link_group_list;
 107         } else {
 108                 /* Hard link group that may should multiple dentries (the code
 109                  * will work even if the group actually contains only 1 dentry
 110                  * though) */
 111
 112                 /* Try adding to existing hard link group */
 113                 pos = dentry->hard_link % table->capacity;
 114                 group = table->array[pos];
 115                 while (group) {
 116                         if (group->link_group_id == dentry->hard_link) {
 117                                 list_add(&dentry->link_group_list,
 118                                          group->dentry_list);
 119                                 return 0;
 120                         }
 121                         group = group->next;
 122                 }
 123
 124                 /* Add new hard link group to the table */
 125
 126                 group = MALLOC(sizeof(struct link_group));
 127                 if (!group)
 128                         return WIMLIB_ERR_NOMEM;
 129                 group->link_group_id   = dentry->hard_link;
 130                 group->next            = table->array[pos];
 131                 INIT_LIST_HEAD(&dentry->link_group_list);
 132                 group->dentry_list = &dentry->link_group_list;
 133                 table->array[pos]      = group;
 134
 135                 /* XXX Make the table grow when too many entries have been
 136                  * inserted. */
 137                 table->num_entries++;
 138         }
 139         return 0;
 140 }
 141
 142 /* Frees a link group table. */
 143 void free_link_group_table(struct link_group_table *table)
 144 {
 145         struct link_group *single, *next;
 146
 147         if (!table)
 148                 return;
 149         if (table->array) {
 150                 for (u64 i = 0; i < table->capacity; i++) {
 151                         struct link_group *group = table->array[i];
 152                         struct link_group *next;
 153                         while (group) {
 154                                 next = group->next;
 155                                 FREE(group);
 156                                 group = next;
 157                         }
 158                 }
 159                 FREE(table->array);
 160         }
 161         single = table->singles;
 162         while (single) {
 163                 next = single->next;
 164                 FREE(single);
 165                 single = next;
 166         }
 167
 168         FREE(table);
 169 }
 170
 171 /* Assign the link group IDs to dentries in a link group table, and return the
 172  * next available link group ID. */
 173 u64 assign_link_groups(struct link_group_table *table)
 174 {
 175         DEBUG("Assigning link groups");
 176
 177         /* Assign consecutive link group IDs to each link group in the hash
 178          * table */
 179         u64 id = 1;
 180         for (u64 i = 0; i < table->capacity; i++) {
 181                 struct link_group *group = table->array[i];
 182                 struct link_group *next_group;
 183                 struct dentry *dentry;
 184                 struct list_head *cur;
 185                 while (group) {
 186                         cur = group->dentry_list;
 187                         do {
 188                                 dentry = container_of(cur,
 189                                                       struct dentry,
 190                                                       link_group_list);
 191                                 dentry->hard_link = id;
 192                                 cur = cur->next;
 193                         } while (cur != group->dentry_list);
 194                         id++;
 195                         group = group->next;
 196                 }
 197         }
 198         /* Assign link group IDs to the link groups that previously had link
 199          * group IDs of 0, and insert them into the hash table */
 200         struct link_group *single = table->singles;
 201         while (single) {
 202                 struct dentry *dentry;
 203                 struct link_group *next_single;
 204                 size_t pos;
 205
 206                 next_single = single->next;
 207
 208                 dentry = container_of(single->dentry_list, struct dentry,
 209                                       link_group_list);
 210                 dentry->hard_link = id;
 211
 212                 pos = id % table->capacity;
 213                 single->next = table->array[pos];
 214                 table->array[pos] = single;
 215
 216                 single = next_single;
 217                 id++;
 218         }
 219         table->singles = NULL;
 220         return id;
 221 }
 222
 223 static bool dentries_have_same_ads(const struct dentry *d1,
 224                                    const struct dentry *d2)
 225 {
 226         /* Verify stream names and hashes are the same */
 227         for (u16 i = 0; i < d1->num_ads; i++) {
 228                 if (strcmp(d1->ads_entries[i].stream_name_utf8,
 229                            d2->ads_entries[i].stream_name_utf8) != 0)
 230                         return false;
 231                 if (!hashes_equal(d1->ads_entries[i].hash,
 232                                   d2->ads_entries[i].hash))
 233                         return false;
 234         }
 235         return true;
 236 }
 237
 238 /* Share the alternate stream entries between hard-linked dentries. */
 239 static int share_dentry_ads(struct dentry *owner, struct dentry *user)
 240 {
 241         const char *mismatch_type;
 242         wimlib_assert(owner->num_ads == 0 ||
 243                       owner->ads_entries != user->ads_entries);
 244         if (owner->attributes != user->attributes) {
 245                 mismatch_type = "attributes";
 246                 goto mismatch;
 247         }
 248         if (owner->attributes & FILE_ATTRIBUTE_DIRECTORY) {
 249                 WARNING("`%s' is hard-linked to `%s', which is a directory ",
 250                         user->full_path_utf8, owner->full_path_utf8);
 251                 return WIMLIB_ERR_INVALID_DENTRY;
 252         }
 253         if (owner->security_id != user->security_id) {
 254                 mismatch_type = "security ID";
 255                 goto mismatch;
 256         }
 257         if (!hashes_equal(owner->hash, user->hash)) {
 258                 mismatch_type = "main file resource";
 259                 goto mismatch;
 260         }
 261         if (!dentries_have_same_ads(owner, user)) {
 262                 mismatch_type = "Alternate Stream Entries";
 263                 goto mismatch;
 264         }
 265         dentry_free_ads_entries(user);
 266         user->ads_entries = owner->ads_entries;
 267         user->ads_entries_status = ADS_ENTRIES_USER;
 268         return 0;
 269 mismatch:
 270         WARNING("Dentries `%s' and `%s' in the same hard-link group but "
 271                 "do not share the same %s",
 272                 owner->full_path_utf8, user->full_path_utf8,
 273                 mismatch_type);
 274         return WIMLIB_ERR_INVALID_DENTRY;
 275 }
 276
 277 static int link_group_free_duplicate_data(struct link_group *group,
 278                                           struct link_group **bad_links)
 279 {
 280         struct dentry *owner, *user, *tmp;
 281
 282         owner = container_of(group->dentry_list, struct dentry,
 283                               link_group_list);
 284         owner->ads_entries_status = ADS_ENTRIES_OWNER;
 285
 286         list_for_each_entry_safe(user, tmp, group->dentry_list,
 287                                  link_group_list)
 288         {
 289                 /* I would like it to be an error if two dentries are in the
 290                  * same hard link group but have irreconcilable differences such
 291                  * as different file permissions, but unfortunately some of M$'s
 292                  * WIMs contain many instances of this error.  This problem is
 293                  * worked around here by splitting each offending dentry off
 294                  * into its own hard link group. */
 295                 if (share_dentry_ads(owner, user) != 0) {
 296                         struct link_group *single;
 297                         single = MALLOC(sizeof(struct link_group));
 298                         if (!single)
 299                                 return WIMLIB_ERR_NOMEM;
 300                         list_del(&user->link_group_list);
 301                         INIT_LIST_HEAD(&user->link_group_list);
 302                         single->link_group_id = 0;
 303                         single->next          = *bad_links;
 304                         single->dentry_list   = &user->link_group_list;
 305                         *bad_links            = single;
 306                         user->ads_entries_status = ADS_ENTRIES_OWNER;
 307                 }
 308         }
 309         return 0;
 310 }
 311
 312 /*
 313  * Goes through each link group and shares the ads_entries (Alternate Data
 314  * Stream entries) field of each dentry between members of a hard link group.
 315  *
 316  * In the process, the dentries in each link group are checked for consistency.
 317  * If they contain data features that indicate they cannot really be in the same
 318  * hard link group, this should be an error, but in reality this case needs to
 319  * be handled, so we split the dentries into different hard link groups.
 320  *
 321  * One of the dentries in the group is arbitrarily assigned the role of "owner"
 322  * (ADS_ENTRIES_OWNER), while the others are "users" (ADS_ENTRIES_USER).
 323  */
 324 int link_groups_free_duplicate_data(struct link_group_table *table)
 325 {
 326         for (u64 i = 0; i < table->capacity; i++) {
 327                 struct link_group *group = table->array[i];
 328                 while (group) {
 329                         int ret;
 330                         ret = link_group_free_duplicate_data(group,
 331                                                              &table->singles);
 332                         if (ret != 0)
 333                                 return ret;
 334                         group = group->next;
 335                 }
 336         }
 337         return 0;
 338 }