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
26struct 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
49struct backed_block_list {
50	struct backed_block *data_blocks;
51	struct backed_block *last_used;
52	unsigned int block_size;
53};
54
55struct backed_block *backed_block_iter_new(struct backed_block_list *bbl)
56{
57	return bbl->data_blocks;
58}
59
60struct backed_block *backed_block_iter_next(struct backed_block *bb)
61{
62	return bb->next;
63}
64
65unsigned int backed_block_len(struct backed_block *bb)
66{
67	return bb->len;
68}
69
70unsigned int backed_block_block(struct backed_block *bb)
71{
72	return bb->block;
73}
74
75void *backed_block_data(struct backed_block *bb)
76{
77	assert(bb->type == BACKED_BLOCK_DATA);
78	return bb->data.data;
79}
80
81const char *backed_block_filename(struct backed_block *bb)
82{
83	assert(bb->type == BACKED_BLOCK_FILE);
84	return bb->file.filename;
85}
86
87int backed_block_fd(struct backed_block *bb)
88{
89	assert(bb->type == BACKED_BLOCK_FD);
90	return bb->fd.fd;
91}
92
93int64_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
103uint32_t backed_block_fill_val(struct backed_block *bb)
104{
105	assert(bb->type == BACKED_BLOCK_FILL);
106	return bb->fill.val;
107}
108
109enum backed_block_type backed_block_type(struct backed_block *bb)
110{
111	return bb->type;
112}
113
114void 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
123struct 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
130void 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
144void 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 */
191static 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
247static 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 */
288int 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 */
306int 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 */
324int 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 */
343int 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
361int 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