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 };
  17
  18 #include <sys/mman.h>
  19
  20 struct link_group_table *new_link_group_table(u64 capacity)
  21 {
  22         return (struct link_group_table*)new_lookup_table(capacity);
  23 }
  24
  25 /* Insert a dentry into the hard link group table based on its hard link group
  26  * ID.
  27  *
  28  * If there is already a dentry in the table having the same hard link group ID,
  29  * we link the dentries together in a circular list.
  30  *
  31  * If the hard link group ID is 0, this is a no-op and the dentry is not
  32  * inserted.
  33  */
  34 int link_group_table_insert(struct dentry *dentry, struct link_group_table *table)
  35 {
  36         size_t pos;
  37         struct link_group *group;
  38
  39         if (dentry->hard_link == 0) {
  40                 INIT_LIST_HEAD(&dentry->link_group_list);
  41                 return 0;
  42         }
  43
  44         /* Try adding to existing hard link group */
  45         pos = dentry->hard_link % table->capacity;
  46         group = table->array[pos];
  47         while (group) {
  48                 if (group->link_group_id == dentry->hard_link) {
  49                         list_add(&dentry->link_group_list, group->dentry_list);
  50                         return 0;
  51                 }
  52                 group = group->next;
  53         }
  54
  55         /* Add new hard link group to the table */
  56
  57         group = MALLOC(sizeof(struct link_group));
  58         if (!group)
  59                 return WIMLIB_ERR_NOMEM;
  60         group->link_group_id   = dentry->hard_link;
  61         group->next            = table->array[pos];
  62         INIT_LIST_HEAD(&dentry->link_group_list);
  63         group->dentry_list = &dentry->link_group_list;
  64         table->array[pos]      = group;
  65
  66         /* XXX Make the table grow when too many entries have been inserted. */
  67         table->num_entries++;
  68         return 0;
  69 }
  70
  71 /* Frees a link group table. */
  72 void free_link_group_table(struct link_group_table *table)
  73 {
  74         if (!table)
  75                 return;
  76         if (table->array) {
  77                 for (u64 i = 0; i < table->capacity; i++) {
  78                         struct link_group *group = table->array[i];
  79                         struct link_group *next;
  80                         while (group) {
  81                                 next = group->next;
  82                                 FREE(group);
  83                                 group = next;
  84                         }
  85                 }
  86                 FREE(table->array);
  87         }
  88         FREE(table);
  89 }
  90
  91 /* Assign the link group IDs to dentries in a link group table, and return the
  92  * next available link group ID. */
  93 u64 assign_link_groups(struct link_group_table *table)
  94 {
  95         struct link_group *remaining_groups = NULL;
  96         u64 id = 1;
  97         for (u64 i = 0; i < table->capacity; i++) {
  98                 struct link_group *group = table->array[i];
  99                 struct link_group *next_group;
 100                 struct dentry *dentry;
 101                 while (group) {
 102                         next_group = group->next;
 103                         u64 cur_id;
 104                         struct list_head *dentry_list = group->dentry_list;
 105                         if (dentry_list->next == dentry_list) {
 106                                 /* Hard link group of size 1.  Change the hard
 107                                  * link ID to 0 and discard the link_group */
 108                                 cur_id = 0;
 109                                 FREE(group);
 110                         } else {
 111                                 /* Hard link group of size > 1.  Assign the
 112                                  * dentries in the group the next available hard
 113                                  * link IDs and queue the group to be
 114                                  * re-inserted into the table. */
 115                                 cur_id = id++;
 116                                 group->next = remaining_groups;
 117                                 remaining_groups = group;
 118                         }
 119                         struct list_head *cur = dentry_list;
 120                         do {
 121                                 dentry = container_of(cur,
 122                                                       struct dentry,
 123                                                       link_group_list);
 124                                 dentry->hard_link = cur_id;
 125                                 cur = cur->next;
 126                         } while (cur != dentry_list);
 127                         group = next_group;
 128                 }
 129         }
 130         memset(table->array, 0, table->capacity * sizeof(table->array[0]));
 131         table->num_entries = 0;
 132         while (remaining_groups) {
 133                 struct link_group *group = remaining_groups;
 134                 size_t pos = group->link_group_id % table->capacity;
 135
 136                 table->num_entries++;
 137                 group->next = table->array[pos];
 138                 table->array[pos] = group;
 139                 remaining_groups = remaining_groups->next;
 140         }
 141         return id;
 142 }
 143
 144 static int link_group_free_duplicate_data(struct link_group *group)
 145 {
 146         struct list_head *head;
 147         struct dentry *master;
 148
 149         head = group->dentry_list;
 150         master = container_of(head, struct dentry, link_group_list);
 151         head = head->next;
 152         master->link_group_master_status = GROUP_MASTER;
 153         while (head != group->dentry_list) {
 154                 int ret = share_dentry_ads(master,
 155                                            container_of(head, struct dentry,
 156                                                         link_group_list));
 157                 if (ret != 0)
 158                         return ret;
 159                 head = head->next;
 160         }
 161         return 0;
 162 }
 163
 164 int link_groups_free_duplicate_data(struct link_group_table *table)
 165 {
 166         for (u64 i = 0; i < table->capacity; i++) {
 167                 struct link_group *group = table->array[i];
 168                 while (group) {
 169                         int ret = link_group_free_duplicate_data(group);
 170                         if (ret != 0)
 171                                 return ret;
 172                         group = group->next;
 173                 }
 174         }
 175         return 0;
 176 }