1 /*
2  * Copyright (C) 2010 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 <errno.h>
19 #include <stdint.h>
20 #include <stdlib.h>
21 #include <string.h>
22 
23 #include "backed_block.h"
24 #include "sparse_defs.h"
25 
26 struct backed_block {
27 	unsigned int block;
28 	unsigned int len;
29 	enum backed_block_type type;
30 	union {
31 		struct {
32 			void *data;
33 		} data;
34 		struct {
35 			char *filename;
36 			int64_t offset;
37 		} file;
38 		struct {
39 			int fd;
40 			int64_t offset;
41 		} fd;
42 		struct {
43 			uint32_t val;
44 		} fill;
45 	};
46 	struct backed_block *next;
47 };
48 
49 struct backed_block_list {
50 	struct backed_block *data_blocks;
51 	struct backed_block *last_used;
52 	unsigned int block_size;
53 };
54 
backed_block_iter_new(struct backed_block_list * bbl)55 struct backed_block *backed_block_iter_new(struct backed_block_list *bbl)
56 {
57 	return bbl->data_blocks;
58 }
59 
backed_block_iter_next(struct backed_block * bb)60 struct backed_block *backed_block_iter_next(struct backed_block *bb)
61 {
62 	return bb->next;
63 }
64 
backed_block_len(struct backed_block * bb)65 unsigned int backed_block_len(struct backed_block *bb)
66 {
67 	return bb->len;
68 }
69 
backed_block_block(struct backed_block * bb)70 unsigned int backed_block_block(struct backed_block *bb)
71 {
72 	return bb->block;
73 }
74 
backed_block_data(struct backed_block * bb)75 void *backed_block_data(struct backed_block *bb)
76 {
77 	assert(bb->type == BACKED_BLOCK_DATA);
78 	return bb->data.data;
79 }
80 
backed_block_filename(struct backed_block * bb)81 const char *backed_block_filename(struct backed_block *bb)
82 {
83 	assert(bb->type == BACKED_BLOCK_FILE);
84 	return bb->file.filename;
85 }
86 
backed_block_fd(struct backed_block * bb)87 int backed_block_fd(struct backed_block *bb)
88 {
89 	assert(bb->type == BACKED_BLOCK_FD);
90 	return bb->fd.fd;
91 }
92 
backed_block_file_offset(struct backed_block * bb)93 int64_t backed_block_file_offset(struct backed_block *bb)
94 {
95 	assert(bb->type == BACKED_BLOCK_FILE || bb->type == BACKED_BLOCK_FD);
96 	if (bb->type == BACKED_BLOCK_FILE) {
97 		return bb->file.offset;
98 	} else { /* bb->type == BACKED_BLOCK_FD */
99 		return bb->fd.offset;
100 	}
101 }
102 
backed_block_fill_val(struct backed_block * bb)103 uint32_t backed_block_fill_val(struct backed_block *bb)
104 {
105 	assert(bb->type == BACKED_BLOCK_FILL);
106 	return bb->fill.val;
107 }
108 
backed_block_type(struct backed_block * bb)109 enum backed_block_type backed_block_type(struct backed_block *bb)
110 {
111 	return bb->type;
112 }
113 
backed_block_destroy(struct backed_block * bb)114 void backed_block_destroy(struct backed_block *bb)
115 {
116 	if (bb->type == BACKED_BLOCK_FILE) {
117 		free(bb->file.filename);
118 	}
119 
120 	free(bb);
121 }
122 
backed_block_list_new(unsigned int block_size)123 struct backed_block_list *backed_block_list_new(unsigned int block_size)
124 {
125 	struct backed_block_list *b = calloc(sizeof(struct backed_block_list), 1);
126 	b->block_size = block_size;
127 	return b;
128 }
129 
backed_block_list_destroy(struct backed_block_list * bbl)130 void backed_block_list_destroy(struct backed_block_list *bbl)
131 {
132 	if (bbl->data_blocks) {
133 		struct backed_block *bb = bbl->data_blocks;
134 		while (bb) {
135 			struct backed_block *next = bb->next;
136 			backed_block_destroy(bb);
137 			bb = next;
138 		}
139 	}
140 
141 	free(bbl);
142 }
143 
backed_block_list_move(struct backed_block_list * from,struct backed_block_list * to,struct backed_block * start,struct backed_block * end)144 void backed_block_list_move(struct backed_block_list *from,
145 		struct backed_block_list *to, struct backed_block *start,
146 		struct backed_block *end)
147 {
148 	struct backed_block *bb;
149 
150 	if (start == NULL) {
151 		start = from->data_blocks;
152 	}
153 
154 	if (!end) {
155 		for (end = start; end && end->next; end = end->next)
156 			;
157 	}
158 
159 	if (start == NULL || end == NULL) {
160 		return;
161 	}
162 
163 	from->last_used = NULL;
164 	to->last_used = NULL;
165 	if (from->data_blocks == start) {
166 		from->data_blocks = end->next;
167 	} else {
168 		for (bb = from->data_blocks; bb; bb = bb->next) {
169 			if (bb->next == start) {
170 				bb->next = end->next;
171 				break;
172 			}
173 		}
174 	}
175 
176 	if (!to->data_blocks) {
177 		to->data_blocks = start;
178 		end->next = NULL;
179 	} else {
180 		for (bb = to->data_blocks; bb; bb = bb->next) {
181 			if (!bb->next || bb->next->block > start->block) {
182 				end->next = bb->next;
183 				bb->next = start;
184 				break;
185 			}
186 		}
187 	}
188 }
189 
190 /* may free b */
merge_bb(struct backed_block_list * bbl,struct backed_block * a,struct backed_block * b)191 static int merge_bb(struct backed_block_list *bbl,
192 		struct backed_block *a, struct backed_block *b)
193 {
194 	unsigned int block_len;
195 
196 	/* Block doesn't exist (possible if one block is the last block) */
197 	if (!a || !b) {
198 		return -EINVAL;
199 	}
200 
201 	assert(a->block < b->block);
202 
203 	/* Blocks are of different types */
204 	if (a->type != b->type) {
205 		return -EINVAL;
206 	}
207 
208 	/* Blocks are not adjacent */
209 	block_len = a->len / bbl->block_size; /* rounds down */
210 	if (a->block + block_len != b->block) {
211 		return -EINVAL;
212 	}
213 
214 	switch (a->type) {
215 	case BACKED_BLOCK_DATA:
216 		/* Don't support merging data for now */
217 		return -EINVAL;
218 	case BACKED_BLOCK_FILL:
219 		if (a->fill.val != b->fill.val) {
220 			return -EINVAL;
221 		}
222 		break;
223 	case BACKED_BLOCK_FILE:
224 		if (a->file.filename != b->file.filename ||
225 				a->file.offset + a->len != b->file.offset) {
226 			return -EINVAL;
227 		}
228 		break;
229 	case BACKED_BLOCK_FD:
230 		if (a->fd.fd != b->fd.fd ||
231 				a->fd.offset + a->len != b->fd.offset) {
232 			return -EINVAL;
233 		}
234 		break;
235 	}
236 
237 	/* Blocks are compatible and adjacent, with a before b.  Merge b into a,
238 	 * and free b */
239 	a->len += b->len;
240 	a->next = b->next;
241 
242 	backed_block_destroy(b);
243 
244 	return 0;
245 }
246 
queue_bb(struct backed_block_list * bbl,struct backed_block * new_bb)247 static int queue_bb(struct backed_block_list *bbl, struct backed_block *new_bb)
248 {
249 	struct backed_block *bb;
250 
251 	if (bbl->data_blocks == NULL) {
252 		bbl->data_blocks = new_bb;
253 		return 0;
254 	}
255 
256 	if (bbl->data_blocks->block > new_bb->block) {
257 		new_bb->next = bbl->data_blocks;
258 		bbl->data_blocks = new_bb;
259 		return 0;
260 	}
261 
262 	/* Optimization: blocks are mostly queued in sequence, so save the
263 	   pointer to the last bb that was added, and start searching from
264 	   there if the next block number is higher */
265 	if (bbl->last_used && new_bb->block > bbl->last_used->block)
266 		bb = bbl->last_used;
267 	else
268 		bb = bbl->data_blocks;
269 	bbl->last_used = new_bb;
270 
271 	for (; bb->next && bb->next->block < new_bb->block; bb = bb->next)
272 		;
273 
274 	if (bb->next == NULL) {
275 		bb->next = new_bb;
276 	} else {
277 		new_bb->next = bb->next;
278 		bb->next = new_bb;
279 	}
280 
281 	merge_bb(bbl, new_bb, new_bb->next);
282 	merge_bb(bbl, bb, new_bb);
283 
284 	return 0;
285 }
286 
287 /* Queues a fill block of memory to be written to the specified data blocks */
backed_block_add_fill(struct backed_block_list * bbl,unsigned int fill_val,unsigned int len,unsigned int block)288 int backed_block_add_fill(struct backed_block_list *bbl, unsigned int fill_val,
289 		unsigned int len, unsigned int block)
290 {
291 	struct backed_block *bb = calloc(1, sizeof(struct backed_block));
292 	if (bb == NULL) {
293 		return -ENOMEM;
294 	}
295 
296 	bb->block = block;
297 	bb->len = len;
298 	bb->type = BACKED_BLOCK_FILL;
299 	bb->fill.val = fill_val;
300 	bb->next = NULL;
301 
302 	return queue_bb(bbl, bb);
303 }
304 
305 /* Queues a block of memory to be written to the specified data blocks */
backed_block_add_data(struct backed_block_list * bbl,void * data,unsigned int len,unsigned int block)306 int backed_block_add_data(struct backed_block_list *bbl, void *data,
307 		unsigned int len, unsigned int block)
308 {
309 	struct backed_block *bb = calloc(1, sizeof(struct backed_block));
310 	if (bb == NULL) {
311 		return -ENOMEM;
312 	}
313 
314 	bb->block = block;
315 	bb->len = len;
316 	bb->type = BACKED_BLOCK_DATA;
317 	bb->data.data = data;
318 	bb->next = NULL;
319 
320 	return queue_bb(bbl, bb);
321 }
322 
323 /* Queues a chunk of a file on disk to be written to the specified data blocks */
backed_block_add_file(struct backed_block_list * bbl,const char * filename,int64_t offset,unsigned int len,unsigned int block)324 int backed_block_add_file(struct backed_block_list *bbl, const char *filename,
325 		int64_t offset, unsigned int len, unsigned int block)
326 {
327 	struct backed_block *bb = calloc(1, sizeof(struct backed_block));
328 	if (bb == NULL) {
329 		return -ENOMEM;
330 	}
331 
332 	bb->block = block;
333 	bb->len = len;
334 	bb->type = BACKED_BLOCK_FILE;
335 	bb->file.filename = strdup(filename);
336 	bb->file.offset = offset;
337 	bb->next = NULL;
338 
339 	return queue_bb(bbl, bb);
340 }
341 
342 /* Queues a chunk of a fd to be written to the specified data blocks */
backed_block_add_fd(struct backed_block_list * bbl,int fd,int64_t offset,unsigned int len,unsigned int block)343 int backed_block_add_fd(struct backed_block_list *bbl, int fd, int64_t offset,
344 		unsigned int len, unsigned int block)
345 {
346 	struct backed_block *bb = calloc(1, sizeof(struct backed_block));
347 	if (bb == NULL) {
348 		return -ENOMEM;
349 	}
350 
351 	bb->block = block;
352 	bb->len = len;
353 	bb->type = BACKED_BLOCK_FD;
354 	bb->fd.fd = fd;
355 	bb->fd.offset = offset;
356 	bb->next = NULL;
357 
358 	return queue_bb(bbl, bb);
359 }
360 
backed_block_split(struct backed_block_list * bbl,struct backed_block * bb,unsigned int max_len)361 int backed_block_split(struct backed_block_list *bbl, struct backed_block *bb,
362 		unsigned int max_len)
363 {
364 	struct backed_block *new_bb;
365 
366 	max_len = ALIGN_DOWN(max_len, bbl->block_size);
367 
368 	if (bb->len <= max_len) {
369 		return 0;
370 	}
371 
372 	new_bb = malloc(sizeof(struct backed_block));
373 	if (new_bb == NULL) {
374 		return -ENOMEM;
375 	}
376 
377 	*new_bb = *bb;
378 
379 	new_bb->len = bb->len - max_len;
380 	new_bb->block = bb->block + max_len / bbl->block_size;
381 	new_bb->next = bb->next;
382 	bb->next = new_bb;
383 	bb->len = max_len;
384 
385 	switch (bb->type) {
386 	case BACKED_BLOCK_DATA:
387 		new_bb->data.data = (char *)bb->data.data + max_len;
388 		break;
389 	case BACKED_BLOCK_FILE:
390 		new_bb->file.offset += max_len;
391 		break;
392 	case BACKED_BLOCK_FD:
393 		new_bb->fd.offset += max_len;
394 		break;
395 	case BACKED_BLOCK_FILL:
396 		break;
397 	}
398 
399 	return 0;
400 }
401