1 /*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <assert.h>
18 #include <stdlib.h>
19
20 #include <sparse/sparse.h>
21
22 #include "defs.h"
23 #include "sparse_file.h"
24
25 #include "backed_block.h"
26 #include "output_file.h"
27 #include "sparse_defs.h"
28 #include "sparse_format.h"
29
sparse_file_new(unsigned int block_size,int64_t len)30 struct sparse_file* sparse_file_new(unsigned int block_size, int64_t len) {
31 struct sparse_file* s = reinterpret_cast<sparse_file*>(calloc(sizeof(struct sparse_file), 1));
32 if (!s) {
33 return nullptr;
34 }
35
36 s->backed_block_list = backed_block_list_new(block_size);
37 if (!s->backed_block_list) {
38 free(s);
39 return nullptr;
40 }
41
42 s->block_size = block_size;
43 s->len = len;
44
45 return s;
46 }
47
sparse_file_destroy(struct sparse_file * s)48 void sparse_file_destroy(struct sparse_file* s) {
49 backed_block_list_destroy(s->backed_block_list);
50 free(s);
51 }
52
sparse_file_add_data(struct sparse_file * s,void * data,unsigned int len,unsigned int block)53 int sparse_file_add_data(struct sparse_file* s, void* data, unsigned int len, unsigned int block) {
54 return backed_block_add_data(s->backed_block_list, data, len, block);
55 }
56
sparse_file_add_fill(struct sparse_file * s,uint32_t fill_val,unsigned int len,unsigned int block)57 int sparse_file_add_fill(struct sparse_file* s, uint32_t fill_val, unsigned int len,
58 unsigned int block) {
59 return backed_block_add_fill(s->backed_block_list, fill_val, len, block);
60 }
61
sparse_file_add_file(struct sparse_file * s,const char * filename,int64_t file_offset,unsigned int len,unsigned int block)62 int sparse_file_add_file(struct sparse_file* s, const char* filename, int64_t file_offset,
63 unsigned int len, unsigned int block) {
64 return backed_block_add_file(s->backed_block_list, filename, file_offset, len, block);
65 }
66
sparse_file_add_fd(struct sparse_file * s,int fd,int64_t file_offset,unsigned int len,unsigned int block)67 int sparse_file_add_fd(struct sparse_file* s, int fd, int64_t file_offset, unsigned int len,
68 unsigned int block) {
69 return backed_block_add_fd(s->backed_block_list, fd, file_offset, len, block);
70 }
sparse_count_chunks(struct sparse_file * s)71 unsigned int sparse_count_chunks(struct sparse_file* s) {
72 struct backed_block* bb;
73 unsigned int last_block = 0;
74 unsigned int chunks = 0;
75
76 for (bb = backed_block_iter_new(s->backed_block_list); bb; bb = backed_block_iter_next(bb)) {
77 if (backed_block_block(bb) > last_block) {
78 /* If there is a gap between chunks, add a skip chunk */
79 chunks++;
80 }
81 chunks++;
82 last_block = backed_block_block(bb) + DIV_ROUND_UP(backed_block_len(bb), s->block_size);
83 }
84 if (last_block < DIV_ROUND_UP(s->len, s->block_size)) {
85 chunks++;
86 }
87
88 return chunks;
89 }
90
sparse_file_write_block(struct output_file * out,struct backed_block * bb)91 static int sparse_file_write_block(struct output_file* out, struct backed_block* bb) {
92 int ret = -EINVAL;
93
94 switch (backed_block_type(bb)) {
95 case BACKED_BLOCK_DATA:
96 ret = write_data_chunk(out, backed_block_len(bb), backed_block_data(bb));
97 break;
98 case BACKED_BLOCK_FILE:
99 ret = write_file_chunk(out, backed_block_len(bb), backed_block_filename(bb),
100 backed_block_file_offset(bb));
101 break;
102 case BACKED_BLOCK_FD:
103 ret = write_fd_chunk(out, backed_block_len(bb), backed_block_fd(bb),
104 backed_block_file_offset(bb));
105 break;
106 case BACKED_BLOCK_FILL:
107 ret = write_fill_chunk(out, backed_block_len(bb), backed_block_fill_val(bb));
108 break;
109 }
110
111 return ret;
112 }
113
write_all_blocks(struct sparse_file * s,struct output_file * out)114 static int write_all_blocks(struct sparse_file* s, struct output_file* out) {
115 struct backed_block* bb;
116 unsigned int last_block = 0;
117 int64_t pad;
118 int ret = 0;
119
120 for (bb = backed_block_iter_new(s->backed_block_list); bb; bb = backed_block_iter_next(bb)) {
121 if (backed_block_block(bb) > last_block) {
122 unsigned int blocks = backed_block_block(bb) - last_block;
123 write_skip_chunk(out, (int64_t)blocks * s->block_size);
124 }
125 ret = sparse_file_write_block(out, bb);
126 if (ret) return ret;
127 last_block = backed_block_block(bb) + DIV_ROUND_UP(backed_block_len(bb), s->block_size);
128 }
129
130 pad = s->len - (int64_t)last_block * s->block_size;
131 assert(pad >= 0);
132 if (pad > 0) {
133 write_skip_chunk(out, pad);
134 }
135
136 return 0;
137 }
138
sparse_file_write(struct sparse_file * s,int fd,bool gz,bool sparse,bool crc)139 int sparse_file_write(struct sparse_file* s, int fd, bool gz, bool sparse, bool crc) {
140 int ret;
141 int chunks;
142 struct output_file* out;
143
144 chunks = sparse_count_chunks(s);
145 out = output_file_open_fd(fd, s->block_size, s->len, gz, sparse, chunks, crc);
146
147 if (!out) return -ENOMEM;
148
149 ret = write_all_blocks(s, out);
150
151 output_file_close(out);
152
153 return ret;
154 }
155
sparse_file_callback(struct sparse_file * s,bool sparse,bool crc,int (* write)(void * priv,const void * data,size_t len),void * priv)156 int sparse_file_callback(struct sparse_file* s, bool sparse, bool crc,
157 int (*write)(void* priv, const void* data, size_t len), void* priv) {
158 int ret;
159 int chunks;
160 struct output_file* out;
161
162 chunks = sparse_count_chunks(s);
163 out = output_file_open_callback(write, priv, s->block_size, s->len, false, sparse, chunks, crc);
164
165 if (!out) return -ENOMEM;
166
167 ret = write_all_blocks(s, out);
168
169 output_file_close(out);
170
171 return ret;
172 }
173
174 struct chunk_data {
175 void* priv;
176 unsigned int block;
177 unsigned int nr_blocks;
178 int (*write)(void* priv, const void* data, size_t len, unsigned int block, unsigned int nr_blocks);
179 };
180
foreach_chunk_write(void * priv,const void * data,size_t len)181 static int foreach_chunk_write(void* priv, const void* data, size_t len) {
182 struct chunk_data* chk = reinterpret_cast<chunk_data*>(priv);
183
184 return chk->write(chk->priv, data, len, chk->block, chk->nr_blocks);
185 }
186
sparse_file_foreach_chunk(struct sparse_file * s,bool sparse,bool crc,int (* write)(void * priv,const void * data,size_t len,unsigned int block,unsigned int nr_blocks),void * priv)187 int sparse_file_foreach_chunk(struct sparse_file* s, bool sparse, bool crc,
188 int (*write)(void* priv, const void* data, size_t len,
189 unsigned int block, unsigned int nr_blocks),
190 void* priv) {
191 int ret;
192 int chunks;
193 struct chunk_data chk;
194 struct output_file* out;
195 struct backed_block* bb;
196
197 chk.priv = priv;
198 chk.write = write;
199 chk.block = chk.nr_blocks = 0;
200 chunks = sparse_count_chunks(s);
201 out = output_file_open_callback(foreach_chunk_write, &chk, s->block_size, s->len, false, sparse,
202 chunks, crc);
203
204 if (!out) return -ENOMEM;
205
206 for (bb = backed_block_iter_new(s->backed_block_list); bb; bb = backed_block_iter_next(bb)) {
207 chk.block = backed_block_block(bb);
208 chk.nr_blocks = (backed_block_len(bb) - 1) / s->block_size + 1;
209 ret = sparse_file_write_block(out, bb);
210 if (ret) return ret;
211 }
212
213 output_file_close(out);
214
215 return ret;
216 }
217
out_counter_write(void * priv,const void * data __unused,size_t len)218 static int out_counter_write(void* priv, const void* data __unused, size_t len) {
219 int64_t* count = reinterpret_cast<int64_t*>(priv);
220 *count += len;
221 return 0;
222 }
223
sparse_file_len(struct sparse_file * s,bool sparse,bool crc)224 int64_t sparse_file_len(struct sparse_file* s, bool sparse, bool crc) {
225 int ret;
226 int chunks = sparse_count_chunks(s);
227 int64_t count = 0;
228 struct output_file* out;
229
230 out = output_file_open_callback(out_counter_write, &count, s->block_size, s->len, false, sparse,
231 chunks, crc);
232 if (!out) {
233 return -1;
234 }
235
236 ret = write_all_blocks(s, out);
237
238 output_file_close(out);
239
240 if (ret < 0) {
241 return -1;
242 }
243
244 return count;
245 }
246
sparse_file_block_size(struct sparse_file * s)247 unsigned int sparse_file_block_size(struct sparse_file* s) {
248 return s->block_size;
249 }
250
move_chunks_up_to_len(struct sparse_file * from,struct sparse_file * to,unsigned int len)251 static struct backed_block* move_chunks_up_to_len(struct sparse_file* from, struct sparse_file* to,
252 unsigned int len) {
253 int64_t count = 0;
254 struct output_file* out_counter;
255 struct backed_block* last_bb = nullptr;
256 struct backed_block* bb;
257 struct backed_block* start;
258 unsigned int last_block = 0;
259 int64_t file_len = 0;
260 int ret;
261
262 /*
263 * overhead is sparse file header, the potential end skip
264 * chunk and crc chunk.
265 */
266 int overhead = sizeof(sparse_header_t) + 2 * sizeof(chunk_header_t) + sizeof(uint32_t);
267 len -= overhead;
268
269 start = backed_block_iter_new(from->backed_block_list);
270 out_counter = output_file_open_callback(out_counter_write, &count, to->block_size, to->len, false,
271 true, 0, false);
272 if (!out_counter) {
273 return nullptr;
274 }
275
276 for (bb = start; bb; bb = backed_block_iter_next(bb)) {
277 count = 0;
278 if (backed_block_block(bb) > last_block) count += sizeof(chunk_header_t);
279 last_block = backed_block_block(bb) + DIV_ROUND_UP(backed_block_len(bb), to->block_size);
280
281 /* will call out_counter_write to update count */
282 ret = sparse_file_write_block(out_counter, bb);
283 if (ret) {
284 bb = nullptr;
285 goto out;
286 }
287 if (file_len + count > len) {
288 /*
289 * If the remaining available size is more than 1/8th of the
290 * requested size, split the chunk. Results in sparse files that
291 * are at least 7/8ths of the requested size
292 */
293 file_len += sizeof(chunk_header_t);
294 if (!last_bb || (len - file_len > (len / 8))) {
295 backed_block_split(from->backed_block_list, bb, len - file_len);
296 last_bb = bb;
297 }
298 goto move;
299 }
300 file_len += count;
301 last_bb = bb;
302 }
303
304 move:
305 backed_block_list_move(from->backed_block_list, to->backed_block_list, start, last_bb);
306
307 out:
308 output_file_close(out_counter);
309
310 return bb;
311 }
312
sparse_file_resparse(struct sparse_file * in_s,unsigned int max_len,struct sparse_file ** out_s,int out_s_count)313 int sparse_file_resparse(struct sparse_file* in_s, unsigned int max_len, struct sparse_file** out_s,
314 int out_s_count) {
315 struct backed_block* bb;
316 struct sparse_file* s;
317 struct sparse_file* tmp;
318 int c = 0;
319
320 tmp = sparse_file_new(in_s->block_size, in_s->len);
321 if (!tmp) {
322 return -ENOMEM;
323 }
324
325 do {
326 s = sparse_file_new(in_s->block_size, in_s->len);
327
328 bb = move_chunks_up_to_len(in_s, s, max_len);
329
330 if (c < out_s_count) {
331 out_s[c] = s;
332 } else {
333 backed_block_list_move(s->backed_block_list, tmp->backed_block_list, nullptr, nullptr);
334 sparse_file_destroy(s);
335 }
336 c++;
337 } while (bb);
338
339 backed_block_list_move(tmp->backed_block_list, in_s->backed_block_list, nullptr, nullptr);
340
341 sparse_file_destroy(tmp);
342
343 return c;
344 }
345
sparse_file_verbose(struct sparse_file * s)346 void sparse_file_verbose(struct sparse_file* s) {
347 s->verbose = true;
348 }
349