2 * Copyright (C) 2010 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
23 #include "backed_block.h"
24 #include "sparse_defs.h"
29 enum backed_block_type type
;
46 struct backed_block
*next
;
49 struct backed_block_list
{
50 struct backed_block
*data_blocks
;
51 struct backed_block
*last_used
;
52 unsigned int block_size
;
55 struct backed_block
*backed_block_iter_new(struct backed_block_list
*bbl
)
57 return bbl
->data_blocks
;
60 struct backed_block
*backed_block_iter_next(struct backed_block
*bb
)
65 unsigned int backed_block_len(struct backed_block
*bb
)
70 unsigned int backed_block_block(struct backed_block
*bb
)
75 void *backed_block_data(struct backed_block
*bb
)
77 assert(bb
->type
== BACKED_BLOCK_DATA
);
81 const char *backed_block_filename(struct backed_block
*bb
)
83 assert(bb
->type
== BACKED_BLOCK_FILE
);
84 return bb
->file
.filename
;
87 int backed_block_fd(struct backed_block
*bb
)
89 assert(bb
->type
== BACKED_BLOCK_FD
);
93 int64_t backed_block_file_offset(struct backed_block
*bb
)
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 */
103 uint32_t backed_block_fill_val(struct backed_block
*bb
)
105 assert(bb
->type
== BACKED_BLOCK_FILL
);
109 enum backed_block_type
backed_block_type(struct backed_block
*bb
)
114 void backed_block_destroy(struct backed_block
*bb
)
116 if (bb
->type
== BACKED_BLOCK_FILE
) {
117 free(bb
->file
.filename
);
123 struct backed_block_list
*backed_block_list_new(unsigned int block_size
)
125 struct backed_block_list
*b
= calloc(sizeof(struct backed_block_list
), 1);
126 b
->block_size
= block_size
;
130 void backed_block_list_destroy(struct backed_block_list
*bbl
)
132 if (bbl
->data_blocks
) {
133 struct backed_block
*bb
= bbl
->data_blocks
;
135 struct backed_block
*next
= bb
->next
;
136 backed_block_destroy(bb
);
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
)
148 struct backed_block
*bb
;
151 start
= from
->data_blocks
;
155 for (end
= start
; end
&& end
->next
; end
= end
->next
)
159 if (start
== NULL
|| end
== NULL
) {
163 from
->last_used
= NULL
;
164 to
->last_used
= NULL
;
165 if (from
->data_blocks
== start
) {
166 from
->data_blocks
= end
->next
;
168 for (bb
= from
->data_blocks
; bb
; bb
= bb
->next
) {
169 if (bb
->next
== start
) {
170 bb
->next
= end
->next
;
176 if (!to
->data_blocks
) {
177 to
->data_blocks
= start
;
180 for (bb
= to
->data_blocks
; bb
; bb
= bb
->next
) {
181 if (!bb
->next
|| bb
->next
->block
> start
->block
) {
182 end
->next
= bb
->next
;
191 static int merge_bb(struct backed_block_list
*bbl
,
192 struct backed_block
*a
, struct backed_block
*b
)
194 unsigned int block_len
;
196 /* Block doesn't exist (possible if one block is the last block) */
201 assert(a
->block
< b
->block
);
203 /* Blocks are of different types */
204 if (a
->type
!= b
->type
) {
208 /* Blocks are not adjacent */
209 block_len
= a
->len
/ bbl
->block_size
; /* rounds down */
210 if (a
->block
+ block_len
!= b
->block
) {
215 case BACKED_BLOCK_DATA
:
216 /* Don't support merging data for now */
218 case BACKED_BLOCK_FILL
:
219 if (a
->fill
.val
!= b
->fill
.val
) {
223 case BACKED_BLOCK_FILE
:
224 if (a
->file
.filename
!= b
->file
.filename
||
225 a
->file
.offset
+ a
->len
!= b
->file
.offset
) {
229 case BACKED_BLOCK_FD
:
230 if (a
->fd
.fd
!= b
->fd
.fd
||
231 a
->fd
.offset
+ a
->len
!= b
->fd
.offset
) {
237 /* Blocks are compatible and adjacent, with a before b. Merge b into a,
242 backed_block_destroy(b
);
247 static int queue_bb(struct backed_block_list
*bbl
, struct backed_block
*new_bb
)
249 struct backed_block
*bb
;
251 if (bbl
->data_blocks
== NULL
) {
252 bbl
->data_blocks
= new_bb
;
256 if (bbl
->data_blocks
->block
> new_bb
->block
) {
257 new_bb
->next
= bbl
->data_blocks
;
258 bbl
->data_blocks
= new_bb
;
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
)
268 bb
= bbl
->data_blocks
;
269 bbl
->last_used
= new_bb
;
271 for (; bb
->next
&& bb
->next
->block
< new_bb
->block
; bb
= bb
->next
)
274 if (bb
->next
== NULL
) {
277 new_bb
->next
= bb
->next
;
281 merge_bb(bbl
, new_bb
, new_bb
->next
);
282 merge_bb(bbl
, bb
, new_bb
);
287 /* Queues a fill block of memory to be written to the specified data blocks */
288 int backed_block_add_fill(struct backed_block_list
*bbl
, unsigned int fill_val
,
289 unsigned int len
, unsigned int block
)
291 struct backed_block
*bb
= calloc(1, sizeof(struct backed_block
));
298 bb
->type
= BACKED_BLOCK_FILL
;
299 bb
->fill
.val
= fill_val
;
302 return queue_bb(bbl
, bb
);
305 /* Queues a block of memory to be written to the specified data blocks */
306 int backed_block_add_data(struct backed_block_list
*bbl
, void *data
,
307 unsigned int len
, unsigned int block
)
309 struct backed_block
*bb
= calloc(1, sizeof(struct backed_block
));
316 bb
->type
= BACKED_BLOCK_DATA
;
317 bb
->data
.data
= data
;
320 return queue_bb(bbl
, bb
);
323 /* Queues a chunk of a file on disk to be written to the specified data blocks */
324 int backed_block_add_file(struct backed_block_list
*bbl
, const char *filename
,
325 int64_t offset
, unsigned int len
, unsigned int block
)
327 struct backed_block
*bb
= calloc(1, sizeof(struct backed_block
));
334 bb
->type
= BACKED_BLOCK_FILE
;
335 bb
->file
.filename
= strdup(filename
);
336 bb
->file
.offset
= offset
;
339 return queue_bb(bbl
, bb
);
342 /* Queues a chunk of a fd to be written to the specified data blocks */
343 int backed_block_add_fd(struct backed_block_list
*bbl
, int fd
, int64_t offset
,
344 unsigned int len
, unsigned int block
)
346 struct backed_block
*bb
= calloc(1, sizeof(struct backed_block
));
353 bb
->type
= BACKED_BLOCK_FD
;
355 bb
->fd
.offset
= offset
;
358 return queue_bb(bbl
, bb
);
361 int backed_block_split(struct backed_block_list
*bbl
, struct backed_block
*bb
,
362 unsigned int max_len
)
364 struct backed_block
*new_bb
;
366 max_len
= ALIGN_DOWN(max_len
, bbl
->block_size
);
368 if (bb
->len
<= max_len
) {
372 new_bb
= malloc(sizeof(struct backed_block
));
373 if (new_bb
== NULL
) {
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
;
386 case BACKED_BLOCK_DATA
:
387 new_bb
->data
.data
= (char *)bb
->data
.data
+ max_len
;
389 case BACKED_BLOCK_FILE
:
390 new_bb
->file
.offset
+= max_len
;
392 case BACKED_BLOCK_FD
:
393 new_bb
->fd
.offset
+= max_len
;
395 case BACKED_BLOCK_FILL
: