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 struct link_group {
   7         u64 link_group_id;
   8         struct link_group *next;
   9         struct list_head *dentry_list;
  10 };
  11
  12 struct link_group_table {
  13         struct link_group **array;
  14         u64 num_entries;
  15         u64 capacity;
  16         struct link_group *singles;
  17 };
  18
  19 #include <sys/mman.h>
  20
  21 struct link_group_table *new_link_group_table(u64 capacity)
  22 {
  23         struct link_group_table *table;
  24         struct link_group **array;
  25
  26         table = MALLOC(sizeof(struct link_group_table));
  27         if (!table)
  28                 goto err;
  29         array = CALLOC(capacity, sizeof(array[0]));
  30         if (!array) {
  31                 FREE(table);
  32                 goto err;
  33         }
  34         table->num_entries = 0;
  35         table->capacity = capacity;
  36         table->array = array;
  37         table->singles = NULL;
  38         return table;
  39 err:
  40         ERROR("Failed to allocate memory for link group table with capacity %zu",
  41               capacity);
  42         return NULL;
  43 }
  44
  45 /* Insert a dentry into the hard link group table based on its hard link group
  46  * ID.
  47  *
  48  * If there is already a dentry in the table having the same hard link group ID,
  49  * we link the dentries together in a circular list.
  50  *
  51  * If the hard link group ID is 0, this is a no-op and the dentry is not
  52  * inserted.
  53  */
  54 int link_group_table_insert(struct dentry *dentry, struct link_group_table *table)
  55 {
  56         size_t pos;
  57         struct link_group *group;
  58
  59         if (dentry->hard_link == 0) {
  60                 /* Single group--- Add to the singles list (we can't put it in
  61                  * the table itself because all the singles have a link group ID
  62                  * of 0) */
  63                 group = MALLOC(sizeof(struct link_group));
  64                 if (!group)
  65                         return WIMLIB_ERR_NOMEM;
  66                 group->link_group_id = 0;
  67                 group->next          = table->singles;
  68                 table->singles       = group;
  69                 INIT_LIST_HEAD(&dentry->link_group_list);
  70                 group->dentry_list = &dentry->link_group_list;
  71                 return 0;
  72         }
  73
  74         /* Try adding to existing hard link group */
  75         pos = dentry->hard_link % table->capacity;
  76         group = table->array[pos];
  77         while (group) {
  78                 if (group->link_group_id == dentry->hard_link) {
  79                         list_add(&dentry->link_group_list, group->dentry_list);
  80                         return 0;
  81                 }
  82                 group = group->next;
  83         }
  84
  85         /* Add new hard link group to the table */
  86
  87         group = MALLOC(sizeof(struct link_group));
  88         if (!group)
  89                 return WIMLIB_ERR_NOMEM;
  90         group->link_group_id   = dentry->hard_link;
  91         group->next            = table->array[pos];
  92         INIT_LIST_HEAD(&dentry->link_group_list);
  93         group->dentry_list = &dentry->link_group_list;
  94         table->array[pos]      = group;
  95
  96         /* XXX Make the table grow when too many entries have been inserted. */
  97         table->num_entries++;
  98         return 0;
  99 }
 100
 101 /* Frees a link group table. */
 102 void free_link_group_table(struct link_group_table *table)
 103 {
 104         if (!table)
 105                 return;
 106         if (table->array) {
 107                 for (u64 i = 0; i < table->capacity; i++) {
 108                         struct link_group *group = table->array[i];
 109                         struct link_group *next;
 110                         while (group) {
 111                                 next = group->next;
 112                                 FREE(group);
 113                                 group = next;
 114                         }
 115                 }
 116                 FREE(table->array);
 117         }
 118         FREE(table);
 119 }
 120
 121 /* Assign the link group IDs to dentries in a link group table, and return the
 122  * next available link group ID. */
 123 u64 assign_link_groups(struct link_group_table *table)
 124 {
 125         DEBUG("Assigning link groups");
 126         u64 id = 1;
 127         for (u64 i = 0; i < table->capacity; i++) {
 128                 struct link_group *group = table->array[i];
 129                 struct link_group *next_group;
 130                 struct dentry *dentry;
 131                 struct list_head *cur;
 132                 while (group) {
 133                         cur = group->dentry_list;
 134                         do {
 135                                 dentry = container_of(cur,
 136                                                       struct dentry,
 137                                                       link_group_list);
 138                                 dentry->hard_link = id;
 139                                 cur = cur->next;
 140                         } while (cur != group->dentry_list);
 141                         id++;
 142                         group = group->next;
 143                 }
 144         }
 145         /* Singles */
 146         struct link_group *single = table->singles;
 147         while (single) {
 148                 struct dentry *dentry;
 149                 struct link_group *next_single;
 150                 size_t pos;
 151
 152                 next_single = single->next;
 153
 154                 dentry = container_of(single->dentry_list, struct dentry,
 155                                       link_group_list);
 156                 dentry->hard_link = id;
 157
 158                 pos = id % table->capacity;
 159                 single->next = table->array[pos];
 160                 table->array[pos] = single;
 161
 162                 single = next_single;
 163                 id++;
 164         }
 165         table->singles = NULL;
 166         return id;
 167 }
 168
 169 static int link_group_free_duplicate_data(struct link_group *group,
 170                                           struct link_group **bad_links)
 171 {
 172         struct list_head *head;
 173         struct list_head *next;
 174         struct dentry *master;
 175
 176         head = group->dentry_list;
 177         master = container_of(head, struct dentry, link_group_list);
 178         head = head->next;
 179         master->link_group_master_status = GROUP_MASTER;
 180         while (head != group->dentry_list) {
 181                 next = head->next;
 182                 struct dentry *slave;
 183                 int ret;
 184
 185                 slave = container_of(head, struct dentry, link_group_list);
 186                 ret = share_dentry_ads(master, slave);
 187
 188                 /* I would it to be an error if two dentries are the same hard
 189                  * link group but have irreconcilable differences such as
 190                  * different file permissions, but unfortunately some of M$'s
 191                  * WIMs contain many instances of this error.  This problem is
 192                  * worked around here by splitting each offending dentry off
 193                  * into its own hard link group. */
 194                 if (ret != 0) {
 195                         struct link_group *single;
 196                         single = MALLOC(sizeof(struct link_group));
 197                         if (!single)
 198                                 return WIMLIB_ERR_NOMEM;
 199                         single->link_group_id = 0;
 200                         single->next          = *bad_links;
 201                         *bad_links            = single;
 202                         INIT_LIST_HEAD(&slave->link_group_list);
 203                         single->dentry_list = &slave->link_group_list;
 204                         slave->link_group_master_status = GROUP_INDEPENDENT;
 205                 }
 206                 head = next;
 207         }
 208         return 0;
 209 }
 210
 211 int link_groups_free_duplicate_data(struct link_group_table *table)
 212 {
 213         for (u64 i = 0; i < table->capacity; i++) {
 214                 struct link_group *group = table->array[i];
 215                 while (group) {
 216                         int ret;
 217                         ret = link_group_free_duplicate_data(group,
 218                                                              &table->singles);
 219                         if (ret != 0)
 220                                 return ret;
 221                         group = group->next;
 222                 }
 223         }
 224         return 0;
 225 }