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

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