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 /*
 239  * Share the alternate stream entries between hard-linked dentries.
 240  *
 241  * Notes:
 242  * - If you use 'imagex.exe' (version 6.1.7600.16385) to create a WIM containing
 243  *   hard-linked files, only one dentry in the hard link set will refer to data
 244  *   streams, including all alternate data streams.  The rest of the dentries in
 245  *   the hard link set will be marked as having 0 alternate data streams and
 246  *   will not refer to any main file stream (the SHA1 message digest will be all
 247  *   0's).
 248  *
 249  * - However, if you look at the WIM's that Microsoft actually distributes (e.g.
 250  *   Windows 7/8 boot.wim, install.wim), it's not the same as above.  The
 251  *   dentries in hard link sets will have stream information duplicated.  I
 252  *   can't say anything about the alternate data streams because these WIMs do
 253  *   not contain alternate data streams.
 254  *
 255  * - Windows 7 'install.wim' contains hard link sets containing dentries with
 256  *   inconsistent streams and other inconsistent information such as security
 257  *   ID.  The only way I can think to handle these is to treat the hard link
 258  *   grouping as erroneous and split up the hard link group.
 259  */
 260 static int share_dentry_ads(struct dentry *owner, struct dentry *user)
 261 {
 262         const char *mismatch_type;
 263         bool data_streams_shared = true;
 264         wimlib_assert(owner->num_ads == 0 ||
 265                       owner->ads_entries != user->ads_entries);
 266         if (owner->attributes != user->attributes) {
 267                 mismatch_type = "attributes";
 268                 goto mismatch;
 269         }
 270         if (owner->attributes & FILE_ATTRIBUTE_DIRECTORY) {
 271                 WARNING("`%s' is hard-linked to `%s', which is a directory ",
 272                         user->full_path_utf8, owner->full_path_utf8);
 273                 return WIMLIB_ERR_INVALID_DENTRY;
 274         }
 275         if (owner->security_id != user->security_id) {
 276                 mismatch_type = "security ID";
 277                 goto mismatch;
 278         }
 279         if (!hashes_equal(owner->hash, user->hash)) {
 280                 if (is_zero_hash(user->hash)) {
 281                         data_streams_shared = false;
 282                         copy_hash(user->hash, owner->hash);
 283                 } else {
 284                         mismatch_type = "main file resource";
 285                         goto mismatch;
 286                 }
 287         }
 288         if (data_streams_shared) {
 289                 if (!dentries_have_same_ads(owner, user)) {
 290                         mismatch_type = "Alternate Stream Entries";
 291                         goto mismatch;
 292                 }
 293         }
 294         dentry_free_ads_entries(user);
 295         user->ads_entries = owner->ads_entries;
 296         user->ads_entries_status = ADS_ENTRIES_USER;
 297         return 0;
 298 mismatch:
 299         WARNING("Dentries `%s' and `%s' are supposedly in the same hard-link "
 300                 "group but do not share the same %s",
 301                 owner->full_path_utf8, user->full_path_utf8,
 302                 mismatch_type);
 303         return WIMLIB_ERR_INVALID_DENTRY;
 304 }
 305
 306 static int link_group_free_duplicate_data(struct link_group *group,
 307                                           struct link_group **bad_links)
 308 {
 309         struct dentry *owner, *user, *tmp;
 310
 311         /* Find a dentry with non-zero hash to use as a possible link group
 312          * owner (see comments above the share_dentry_ads() function */
 313         owner = container_of(group->dentry_list, struct dentry,
 314                               link_group_list);
 315         do {
 316                 /* imagex.exe may move the un-named data stream from the dentry
 317                  * itself to the first alternate data stream, if there are
 318                  * other alternate data streams */
 319                 if (!is_zero_hash(owner->hash) ||
 320                     (owner->num_ads && !is_zero_hash(owner->ads_entries[0].hash)))
 321                         goto found_owner;
 322                 owner = container_of(owner->link_group_list.next,
 323                                      struct dentry,
 324                                      link_group_list);
 325         } while (&owner->link_group_list != group->dentry_list);
 326
 327         ERROR("Could not find owner of data streams in hard link group");
 328         return WIMLIB_ERR_INVALID_DENTRY;
 329 found_owner:
 330         owner->ads_entries_status = ADS_ENTRIES_OWNER;
 331         list_for_each_entry_safe(user, tmp, &owner->link_group_list,
 332                                  link_group_list)
 333         {
 334                 /* I would like it to be an error if two dentries are in the
 335                  * same hard link group but have irreconcilable differences such
 336                  * as different file permissions, but unfortunately some of M$'s
 337                  * WIMs contain many instances of this error.  This problem is
 338                  * worked around here by splitting each offending dentry off
 339                  * into its own hard link group. */
 340                 if (share_dentry_ads(owner, user) != 0) {
 341                         struct link_group *single;
 342                         single = MALLOC(sizeof(struct link_group));
 343                         if (!single)
 344                                 return WIMLIB_ERR_NOMEM;
 345                         list_del(&user->link_group_list);
 346                         INIT_LIST_HEAD(&user->link_group_list);
 347                         single->link_group_id = 0;
 348                         single->next          = *bad_links;
 349                         single->dentry_list   = &user->link_group_list;
 350                         *bad_links            = single;
 351                         user->ads_entries_status = ADS_ENTRIES_OWNER;
 352                 }
 353         }
 354         return 0;
 355 }
 356
 357 /*
 358  * Goes through each link group and shares the ads_entries (Alternate Data
 359  * Stream entries) field of each dentry between members of a hard link group.
 360  *
 361  * In the process, the dentries in each link group are checked for consistency.
 362  * If they contain data features that indicate they cannot really be in the same
 363  * hard link group, this should be an error, but in reality this case needs to
 364  * be handled, so we split the dentries into different hard link groups.
 365  *
 366  * One of the dentries in the group is arbitrarily assigned the role of "owner"
 367  * (ADS_ENTRIES_OWNER), while the others are "users" (ADS_ENTRIES_USER).
 368  */
 369 int link_groups_free_duplicate_data(struct link_group_table *table)
 370 {
 371         for (u64 i = 0; i < table->capacity; i++) {
 372                 struct link_group *group = table->array[i];
 373                 while (group) {
 374                         int ret;
 375                         ret = link_group_free_duplicate_data(group,
 376                                                              &table->singles);
 377                         if (ret != 0)
 378                                 return ret;
 379                         group = group->next;
 380                 }
 381         }
 382         return 0;
 383 }