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                 DEBUG("Insert single group `%s'", dentry->full_path_utf8);
  67                 group->link_group_id = 0;
  68                 group->next          = table->singles;
  69                 table->singles       = group;
  70                 INIT_LIST_HEAD(&dentry->link_group_list);
  71                 group->dentry_list = &dentry->link_group_list;
  72                 return 0;
  73         }
  74
  75         /* Try adding to existing hard link group */
  76         pos = dentry->hard_link % table->capacity;
  77         group = table->array[pos];
  78         while (group) {
  79                 if (group->link_group_id == dentry->hard_link) {
  80                         list_add(&dentry->link_group_list, group->dentry_list);
  81                         return 0;
  82                 }
  83                 group = group->next;
  84         }
  85
  86         /* Add new hard link group to the table */
  87
  88         group = MALLOC(sizeof(struct link_group));
  89         if (!group)
  90                 return WIMLIB_ERR_NOMEM;
  91         group->link_group_id   = dentry->hard_link;
  92         group->next            = table->array[pos];
  93         INIT_LIST_HEAD(&dentry->link_group_list);
  94         group->dentry_list = &dentry->link_group_list;
  95         table->array[pos]      = group;
  96
  97         /* XXX Make the table grow when too many entries have been inserted. */
  98         table->num_entries++;
  99         return 0;
 100 }
 101
 102 /* Frees a link group table. */
 103 void free_link_group_table(struct link_group_table *table)
 104 {
 105         if (!table)
 106                 return;
 107         if (table->array) {
 108                 for (u64 i = 0; i < table->capacity; i++) {
 109                         struct link_group *group = table->array[i];
 110                         struct link_group *next;
 111                         while (group) {
 112                                 next = group->next;
 113                                 FREE(group);
 114                                 group = next;
 115                         }
 116                 }
 117                 FREE(table->array);
 118         }
 119         FREE(table);
 120 }
 121
 122 /* Assign the link group IDs to dentries in a link group table, and return the
 123  * next available link group ID. */
 124 u64 assign_link_groups(struct link_group_table *table)
 125 {
 126         DEBUG("Assigning link groups");
 127         u64 id = 1;
 128         for (u64 i = 0; i < table->capacity; i++) {
 129                 struct link_group *group = table->array[i];
 130                 struct link_group *next_group;
 131                 struct dentry *dentry;
 132                 struct list_head *cur;
 133                 while (group) {
 134                         cur = group->dentry_list;
 135                         do {
 136                                 dentry = container_of(cur,
 137                                                       struct dentry,
 138                                                       link_group_list);
 139                                 dentry->hard_link = id;
 140                                 cur = cur->next;
 141                         } while (cur != group->dentry_list);
 142                         id++;
 143                         group = group->next;
 144                 }
 145         }
 146         /* Singles */
 147         struct link_group *single = table->singles;
 148         while (single) {
 149                 struct dentry *dentry;
 150                 struct link_group *next_single;
 151                 size_t pos;
 152
 153                 next_single = single->next;
 154
 155                 dentry = container_of(single->dentry_list, struct dentry,
 156                                       link_group_list);
 157                 dentry->hard_link = id;
 158                 DEBUG("Assign single `%s'", dentry->full_path_utf8);
 159
 160                 pos = id % table->capacity;
 161                 single->next = table->array[pos];
 162                 table->array[pos] = single;
 163
 164                 single = next_single;
 165                 id++;
 166         }
 167         return id;
 168 }
 169
 170 static int link_group_free_duplicate_data(struct link_group *group)
 171 {
 172         struct list_head *head;
 173         struct dentry *master;
 174
 175         head = group->dentry_list;
 176         master = container_of(head, struct dentry, link_group_list);
 177         head = head->next;
 178         master->link_group_master_status = GROUP_MASTER;
 179         while (head != group->dentry_list) {
 180                 int ret = share_dentry_ads(master,
 181                                            container_of(head, struct dentry,
 182                                                         link_group_list));
 183                 if (ret != 0)
 184                         return ret;
 185                 head = head->next;
 186         }
 187         return 0;
 188 }
 189
 190 int link_groups_free_duplicate_data(struct link_group_table *table)
 191 {
 192         for (u64 i = 0; i < table->capacity; i++) {
 193                 struct link_group *group = table->array[i];
 194                 while (group) {
 195                         int ret = link_group_free_duplicate_data(group);
 196                         if (ret != 0)
 197                                 return ret;
 198                         group = group->next;
 199                 }
 200         }
 201         return 0;
 202 }