backed_block.c revision 411619e921904b896eddae81c086c1f687c8304d 
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 <stdlib.h>
18#include <string.h>
19
20#include "backed_block.h"
21#include "sparse_defs.h"
22
23struct data_block {
24	u32 block;
25	u32 len;
26	void *data;
27	const char *filename;
28	int64_t offset;
29	struct data_block *next;
30	u32 fill_val;
31	u8 fill;
32	u8 pad1;
33	u16 pad2;
34};
35
36struct backed_block_list {
37	struct data_block *data_blocks;
38	struct data_block *last_used;
39};
40
41struct backed_block_list *backed_block_list_new(void)
42{
43	struct backed_block_list *b = calloc(sizeof(struct backed_block_list), 1);
44
45	return b;
46}
47
48void backed_block_list_destroy(struct backed_block_list *b)
49{
50	if (b->data_blocks) {
51		struct data_block *db = b->data_blocks;
52		while (db) {
53			struct data_block *next = db->next;
54			free((void*)db->filename);
55
56			free(db);
57			db = next;
58		}
59	}
60
61	free(b);
62}
63
64static void queue_db(struct backed_block_list *b, struct data_block *new_db)
65{
66	struct data_block *db;
67
68	if (b->data_blocks == NULL) {
69		b->data_blocks = new_db;
70		return;
71	}
72
73	if (b->data_blocks->block > new_db->block) {
74		new_db->next = b->data_blocks;
75		b->data_blocks = new_db;
76		return;
77	}
78
79	/* Optimization: blocks are mostly queued in sequence, so save the
80	   pointer to the last db that was added, and start searching from
81	   there if the next block number is higher */
82	if (b->last_used && new_db->block > b->last_used->block)
83		db = b->last_used;
84	else
85		db = b->data_blocks;
86	b->last_used = new_db;
87
88	for (; db->next && db->next->block < new_db->block; db = db->next)
89		;
90
91	if (db->next == NULL) {
92		db->next = new_db;
93	} else {
94		new_db->next = db->next;
95		db->next = new_db;
96	}
97}
98
99/* Queues a fill block of memory to be written to the specified data blocks */
100void queue_fill_block(struct backed_block_list *b, unsigned int fill_val,
101		unsigned int len, unsigned int block)
102{
103	struct data_block *db = calloc(1, sizeof(struct data_block));
104	if (db == NULL) {
105		error_errno("malloc");
106		return;
107	}
108
109	db->block = block;
110	db->len = len;
111	db->fill = 1;
112	db->fill_val = fill_val;
113	db->data = NULL;
114	db->filename = NULL;
115	db->next = NULL;
116
117	queue_db(b, db);
118}
119
120/* Queues a block of memory to be written to the specified data blocks */
121void queue_data_block(struct backed_block_list *b, void *data, unsigned int len,
122		unsigned int block)
123{
124	struct data_block *db = malloc(sizeof(struct data_block));
125	if (db == NULL) {
126		error_errno("malloc");
127		return;
128	}
129
130	db->block = block;
131	db->len = len;
132	db->data = data;
133	db->filename = NULL;
134	db->fill = 0;
135	db->next = NULL;
136
137	queue_db(b, db);
138}
139
140/* Queues a chunk of a file on disk to be written to the specified data blocks */
141void queue_data_file(struct backed_block_list *b, const char *filename,
142		int64_t offset, unsigned int len, unsigned int block)
143{
144	struct data_block *db = malloc(sizeof(struct data_block));
145	if (db == NULL) {
146		error_errno("malloc");
147		return;
148	}
149
150	db->block = block;
151	db->len = len;
152	db->filename = strdup(filename);
153	db->offset = offset;
154	db->data = NULL;
155	db->fill = 0;
156	db->next = NULL;
157
158	queue_db(b, db);
159}
160
161/* Iterates over the queued data blocks, calling data_func for each contiguous
162   data block, and file_func for each contiguous file block */
163void for_each_data_block(struct backed_block_list *b,
164	data_block_callback_t data_func,
165	data_block_file_callback_t file_func,
166	data_block_fill_callback_t fill_func,
167	void *priv, unsigned int block_size)
168{
169	struct data_block *db;
170	u32 last_block = 0;
171
172	for (db = b->data_blocks; db; db = db->next) {
173		if (db->block < last_block)
174			error("data blocks out of order: %u < %u", db->block, last_block);
175		last_block = db->block + DIV_ROUND_UP(db->len, block_size) - 1;
176
177		if (db->filename)
178			file_func(priv, (u64)db->block * block_size, db->filename, db->offset, db->len);
179		else if (db->fill)
180			fill_func(priv, (u64)db->block * block_size, db->fill_val, db->len);
181		else
182			data_func(priv, (u64)db->block * block_size, db->data, db->len);
183	}
184}
185