1 // SPDX-License-Identifier: GPL-2.0+ OR Apache-2.0
2 /*
3 * Copyright (C) 2022 Alibaba Cloud
4 */
5 #include <stdlib.h>
6 #include "erofs/dedupe.h"
7 #include "erofs/print.h"
8 #include "rolling_hash.h"
9 #include "xxhash.h"
10 #include "sha256.h"
11
erofs_memcmp2(const u8 * s1,const u8 * s2,unsigned long sz)12 unsigned long erofs_memcmp2(const u8 *s1, const u8 *s2,
13 unsigned long sz)
14 {
15 const unsigned long *a1, *a2;
16 unsigned long n = sz;
17
18 if (sz < sizeof(long))
19 goto out_bytes;
20
21 if (((long)s1 & (sizeof(long) - 1)) ==
22 ((long)s2 & (sizeof(long) - 1))) {
23 while ((long)s1 & (sizeof(long) - 1)) {
24 if (*s1 != *s2)
25 break;
26 ++s1;
27 ++s2;
28 --sz;
29 }
30
31 a1 = (const unsigned long *)s1;
32 a2 = (const unsigned long *)s2;
33 while (sz >= sizeof(long)) {
34 if (*a1 != *a2)
35 break;
36 ++a1;
37 ++a2;
38 sz -= sizeof(long);
39 }
40 } else {
41 a1 = (const unsigned long *)s1;
42 a2 = (const unsigned long *)s2;
43 do {
44 if (get_unaligned(a1) != get_unaligned(a2))
45 break;
46 ++a1;
47 ++a2;
48 sz -= sizeof(long);
49 } while (sz >= sizeof(long));
50 }
51 s1 = (const u8 *)a1;
52 s2 = (const u8 *)a2;
53 out_bytes:
54 while (sz) {
55 if (*s1 != *s2)
56 break;
57 ++s1;
58 ++s2;
59 --sz;
60 }
61 return n - sz;
62 }
63
64 static unsigned int window_size, rollinghash_rm;
65 static struct list_head dedupe_tree[65536];
66 struct z_erofs_dedupe_item *dedupe_subtree;
67
68 struct z_erofs_dedupe_item {
69 struct list_head list;
70 struct z_erofs_dedupe_item *chain;
71 long long hash;
72 u8 prefix_sha256[32];
73 u64 prefix_xxh64;
74
75 erofs_blk_t compressed_blkaddr;
76 unsigned int compressed_blks;
77
78 int original_length;
79 bool partial, raw;
80 u8 extra_data[];
81 };
82
z_erofs_dedupe_match(struct z_erofs_dedupe_ctx * ctx)83 int z_erofs_dedupe_match(struct z_erofs_dedupe_ctx *ctx)
84 {
85 struct z_erofs_dedupe_item e_find;
86 u8 *cur;
87 bool initial = true;
88
89 if (!window_size)
90 return -ENOENT;
91
92 if (ctx->cur > ctx->end - window_size)
93 cur = ctx->end - window_size;
94 else
95 cur = ctx->cur;
96
97 /* move backward byte-by-byte */
98 for (; cur >= ctx->start; --cur) {
99 struct list_head *p;
100 struct z_erofs_dedupe_item *e;
101
102 unsigned int extra = 0;
103 u64 xxh64_csum = 0;
104 u8 sha256[32];
105
106 if (initial) {
107 /* initial try */
108 e_find.hash = erofs_rolling_hash_init(cur, window_size, true);
109 initial = false;
110 } else {
111 e_find.hash = erofs_rolling_hash_advance(e_find.hash,
112 rollinghash_rm, cur[window_size], cur[0]);
113 }
114
115 p = &dedupe_tree[e_find.hash & (ARRAY_SIZE(dedupe_tree) - 1)];
116 list_for_each_entry(e, p, list) {
117 if (e->hash != e_find.hash)
118 continue;
119 if (!extra) {
120 xxh64_csum = xxh64(cur, window_size, 0);
121 extra = 1;
122 }
123 if (e->prefix_xxh64 == xxh64_csum)
124 break;
125 }
126
127 if (&e->list == p)
128 continue;
129
130 erofs_sha256(cur, window_size, sha256);
131 if (memcmp(sha256, e->prefix_sha256, sizeof(sha256)))
132 continue;
133
134 extra = min_t(unsigned int, ctx->end - cur - window_size,
135 e->original_length - window_size);
136 extra = erofs_memcmp2(cur + window_size, e->extra_data, extra);
137 if (window_size + extra <= ctx->cur - cur)
138 continue;
139 ctx->cur = cur;
140 ctx->e.length = window_size + extra;
141 ctx->e.partial = e->partial ||
142 (window_size + extra < e->original_length);
143 ctx->e.raw = e->raw;
144 ctx->e.inlined = false;
145 ctx->e.blkaddr = e->compressed_blkaddr;
146 ctx->e.compressedblks = e->compressed_blks;
147 return 0;
148 }
149 return -ENOENT;
150 }
151
z_erofs_dedupe_insert(struct z_erofs_inmem_extent * e,void * original_data)152 int z_erofs_dedupe_insert(struct z_erofs_inmem_extent *e,
153 void *original_data)
154 {
155 struct list_head *p;
156 struct z_erofs_dedupe_item *di, *k;
157
158 if (!window_size || e->length < window_size)
159 return 0;
160
161 di = malloc(sizeof(*di) + e->length - window_size);
162 if (!di)
163 return -ENOMEM;
164
165 di->original_length = e->length;
166 erofs_sha256(original_data, window_size, di->prefix_sha256);
167
168 di->prefix_xxh64 = xxh64(original_data, window_size, 0);
169 di->hash = erofs_rolling_hash_init(original_data,
170 window_size, true);
171 memcpy(di->extra_data, original_data + window_size,
172 e->length - window_size);
173 di->compressed_blkaddr = e->blkaddr;
174 di->compressed_blks = e->compressedblks;
175 di->partial = e->partial;
176 di->raw = e->raw;
177
178 /* skip the same xxh64 hash */
179 p = &dedupe_tree[di->hash & (ARRAY_SIZE(dedupe_tree) - 1)];
180 list_for_each_entry(k, p, list) {
181 if (k->prefix_xxh64 == di->prefix_xxh64) {
182 free(di);
183 return 0;
184 }
185 }
186 di->chain = dedupe_subtree;
187 dedupe_subtree = di;
188 list_add_tail(&di->list, p);
189 return 0;
190 }
191
z_erofs_dedupe_commit(bool drop)192 void z_erofs_dedupe_commit(bool drop)
193 {
194 if (!dedupe_subtree)
195 return;
196 if (drop) {
197 struct z_erofs_dedupe_item *di, *n;
198
199 for (di = dedupe_subtree; di; di = n) {
200 n = di->chain;
201 list_del(&di->list);
202 free(di);
203 }
204 }
205 dedupe_subtree = NULL;
206 }
207
z_erofs_dedupe_init(unsigned int wsiz)208 int z_erofs_dedupe_init(unsigned int wsiz)
209 {
210 struct list_head *p;
211
212 for (p = dedupe_tree;
213 p < dedupe_tree + ARRAY_SIZE(dedupe_tree); ++p)
214 init_list_head(p);
215
216 window_size = wsiz;
217 rollinghash_rm = erofs_rollinghash_calc_rm(window_size);
218 return 0;
219 }
220
z_erofs_dedupe_exit(void)221 void z_erofs_dedupe_exit(void)
222 {
223 struct z_erofs_dedupe_item *di, *n;
224 struct list_head *p;
225
226 if (!window_size)
227 return;
228
229 z_erofs_dedupe_commit(true);
230
231 for (p = dedupe_tree;
232 p < dedupe_tree + ARRAY_SIZE(dedupe_tree); ++p) {
233 list_for_each_entry_safe(di, n, p, list) {
234 list_del(&di->list);
235 free(di);
236 }
237 }
238 dedupe_subtree = NULL;
239 }
240