btrfs-progs: image: move metadump definitions to own header

[platform/upstream/btrfs-progs.git] / image / main.c

diff --git a/image/main.c b/image/main.c
index 378a0d4..4557f96 100644 (file)
--- a/image/main.c
+++ b/image/main.c
@@ -36,54 +36,10 @@
 #include "volumes.h"
 #include "extent_io.h"
 #include "help.h"
-
-#define HEADER_MAGIC           0xbd5c25e27295668bULL
-#define MAX_PENDING_SIZE       (256 * 1024)
-#define BLOCK_SIZE             1024
-#define BLOCK_MASK             (BLOCK_SIZE - 1)
-
-#define COMPRESS_NONE          0
-#define COMPRESS_ZLIB          1
+#include "image/metadump.h"
 
 #define MAX_WORKER_THREADS     (32)
 
-struct meta_cluster_item {
-       __le64 bytenr;
-       __le32 size;
-} __attribute__ ((__packed__));
-
-struct meta_cluster_header {
-       __le64 magic;
-       __le64 bytenr;
-       __le32 nritems;
-       u8 compress;
-} __attribute__ ((__packed__));
-
-/* cluster header + index items + buffers */
-struct meta_cluster {
-       struct meta_cluster_header header;
-       struct meta_cluster_item items[];
-} __attribute__ ((__packed__));
-
-#define ITEMS_PER_CLUSTER ((BLOCK_SIZE - sizeof(struct meta_cluster)) / \
-                          sizeof(struct meta_cluster_item))
-
-struct fs_chunk {
-       u64 logical;
-       u64 physical;
-       /*
-        * physical_dup only store additonal physical for BTRFS_BLOCK_GROUP_DUP
-        * currently restore only support single and DUP
-        * TODO: modify this structure and the function related to this
-        * structure for support RAID*
-        */
-       u64 physical_dup;
-       u64 bytes;
-       struct rb_node l;
-       struct rb_node p;
-       struct list_head list;
-};
-
 struct async_work {
        struct list_head list;
        struct list_head ordered;
@@ -408,17 +364,65 @@ static const u32 crc32c_rev_table[256] = {
        0x588982AFL,0x5D65F45EL,0x53516F4DL,0x56BD19BCL
 };
 
-static int find_collision_brute_force(struct name *val, u32 name_len)
+/*
+ * Calculate a 4-byte suffix to match desired CRC32C
+ *
+ * @current_crc: CRC32C checksum of all bytes before the suffix
+ * @desired_crc: the checksum that we want to get after adding the suffix
+ *
+ * Outputs: @suffix: pointer to where the suffix will be written (4-bytes)
+ */
+static void find_collision_calc_suffix(unsigned long current_crc,
+                                      unsigned long desired_crc,
+                                      char *suffix)
+{
+       int i;
+
+       for(i = 3; i >= 0; i--) {
+               desired_crc = (desired_crc << 8)
+                           ^ crc32c_rev_table[desired_crc >> 24 & 0xFF]
+                           ^ ((current_crc >> i * 8) & 0xFF);
+       }
+       for (i = 0; i < 4; i++)
+               suffix[i] = (desired_crc >> i * 8) & 0xFF;
+}
+
+/*
+ * Check if suffix is valid according to our file name conventions
+ */
+static int find_collision_is_suffix_valid(const char *suffix)
+{
+       int i;
+       char c;
+
+       for (i = 0; i < 4; i++) {
+               c = suffix[i];
+               if (c < ' ' || c > 126 || c == '/')
+                       return 0;
+       }
+       return 1;
+}
+
+static int find_collision_reverse_crc32c(struct name *val, u32 name_len)
 {
        unsigned long checksum;
+       unsigned long current_checksum;
        int found = 0;
        int i;
 
+       /* There are no same length collisions of 4 or less bytes */
+       if (name_len <= 4)
+               return 0;
        checksum = crc32c(~1, val->val, name_len);
+       name_len -= 4;
        memset(val->sub, ' ', name_len);
        i = 0;
        while (1) {
-               if (crc32c(~1, val->sub, name_len) == checksum &&
+               current_checksum = crc32c(~1, val->sub, name_len);
+               find_collision_calc_suffix(current_checksum,
+                                          checksum,
+                                          val->sub + name_len);
+               if (find_collision_is_suffix_valid(val->sub + name_len) &&
                    memcmp(val->sub, val->val, val->len)) {
                        found = 1;
                        break;
@@ -485,7 +489,7 @@ static char *find_collision(struct metadump_struct *md, char *name,
                return NULL;
        }
 
-       found = find_collision_brute_force(val, name_len);
+       found = find_collision_reverse_crc32c(val, name_len);
 
        if (!found) {
                warning(