backed_block.c revision be8ddcb35a459481c0bcf5bfe645c1fefe963f5c 
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
144/* may free b */
145static int merge_bb(struct backed_block_list *bbl,
146		struct backed_block *a, struct backed_block *b)
147{
148	unsigned int block_len;
149
150	/* Block doesn't exist (possible if one block is the last block) */
151	if (!a || !b) {
152		return -EINVAL;
153	}
154
155	assert(a->block < b->block);
156
157	/* Blocks are of different types */
158	if (a->type != b->type) {
159		return -EINVAL;
160	}
161
162	/* Blocks are not adjacent */
163	block_len = a->len / bbl->block_size; /* rounds down */
164	if (a->block + block_len != b->block) {
165		return -EINVAL;
166	}
167
168	switch (a->type) {
169	case BACKED_BLOCK_DATA:
170		/* Don't support merging data for now */
171		return -EINVAL;
172	case BACKED_BLOCK_FILL:
173		if (a->fill.val != b->fill.val) {
174			return -EINVAL;
175		}
176		break;
177	case BACKED_BLOCK_FILE:
178		if (a->file.filename != b->file.filename ||
179				a->file.offset + a->len != b->file.offset) {
180			return -EINVAL;
181		}
182		break;
183	case BACKED_BLOCK_FD:
184		if (a->fd.fd != b->fd.fd ||
185				a->fd.offset + a->len != b->fd.offset) {
186			return -EINVAL;
187		}
188		break;
189	}
190
191	/* Blocks are compatible and adjacent, with a before b.  Merge b into a,
192	 * and free b */
193	a->len += b->len;
194	a->next = b->next;
195
196	backed_block_destroy(b);
197
198	return 0;
199}
200
201static int queue_bb(struct backed_block_list *bbl, struct backed_block *new_bb)
202{
203	struct backed_block *bb;
204
205	if (bbl->data_blocks == NULL) {
206		bbl->data_blocks = new_bb;
207		return 0;
208	}
209
210	if (bbl->data_blocks->block > new_bb->block) {
211		new_bb->next = bbl->data_blocks;
212		bbl->data_blocks = new_bb;
213		return 0;
214	}
215
216	/* Optimization: blocks are mostly queued in sequence, so save the
217	   pointer to the last bb that was added, and start searching from
218	   there if the next block number is higher */
219	if (bbl->last_used && new_bb->block > bbl->last_used->block)
220		bb = bbl->last_used;
221	else
222		bb = bbl->data_blocks;
223	bbl->last_used = new_bb;
224
225	for (; bb->next && bb->next->block < new_bb->block; bb = bb->next)
226		;
227
228	if (bb->next == NULL) {
229		bb->next = new_bb;
230	} else {
231		new_bb->next = bb->next;
232		bb->next = new_bb;
233	}
234
235	merge_bb(bbl, new_bb, new_bb->next);
236	merge_bb(bbl, bb, new_bb);
237
238	return 0;
239}
240
241/* Queues a fill block of memory to be written to the specified data blocks */
242int backed_block_add_fill(struct backed_block_list *bbl, unsigned int fill_val,
243		unsigned int len, unsigned int block)
244{
245	struct backed_block *bb = calloc(1, sizeof(struct backed_block));
246	if (bb == NULL) {
247		return -ENOMEM;
248	}
249
250	bb->block = block;
251	bb->len = len;
252	bb->type = BACKED_BLOCK_FILL;
253	bb->fill.val = fill_val;
254	bb->next = NULL;
255
256	return queue_bb(bbl, bb);
257}
258
259/* Queues a block of memory to be written to the specified data blocks */
260int backed_block_add_data(struct backed_block_list *bbl, void *data,
261		unsigned int len, unsigned int block)
262{
263	struct backed_block *bb = calloc(1, sizeof(struct backed_block));
264	if (bb == NULL) {
265		return -ENOMEM;
266	}
267
268	bb->block = block;
269	bb->len = len;
270	bb->type = BACKED_BLOCK_DATA;
271	bb->data.data = data;
272	bb->next = NULL;
273
274	return queue_bb(bbl, bb);
275}
276
277/* Queues a chunk of a file on disk to be written to the specified data blocks */
278int backed_block_add_file(struct backed_block_list *bbl, const char *filename,
279		int64_t offset, unsigned int len, unsigned int block)
280{
281	struct backed_block *bb = calloc(1, sizeof(struct backed_block));
282	if (bb == NULL) {
283		return -ENOMEM;
284	}
285
286	bb->block = block;
287	bb->len = len;
288	bb->type = BACKED_BLOCK_FILE;
289	bb->file.filename = strdup(filename);
290	bb->file.offset = offset;
291	bb->next = NULL;
292
293	return queue_bb(bbl, bb);
294}
295
296/* Queues a chunk of a fd to be written to the specified data blocks */
297int backed_block_add_fd(struct backed_block_list *bbl, int fd, int64_t offset,
298		unsigned int len, unsigned int block)
299{
300	struct backed_block *bb = calloc(1, sizeof(struct backed_block));
301	if (bb == NULL) {
302		return -ENOMEM;
303	}
304
305	bb->block = block;
306	bb->len = len;
307	bb->type = BACKED_BLOCK_FD;
308	bb->fd.fd = fd;
309	bb->fd.offset = offset;
310	bb->next = NULL;
311
312	return queue_bb(bbl, bb);
313}
314