summaryrefslogtreecommitdiff
path: root/libsparse/backed_block.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'libsparse/backed_block.cpp')
-rw-r--r--libsparse/backed_block.cpp629
1 files changed, 302 insertions, 327 deletions
diff --git a/libsparse/backed_block.cpp b/libsparse/backed_block.cpp
index fb26d1a6e..7f5632eea 100644
--- a/libsparse/backed_block.cpp
+++ b/libsparse/backed_block.cpp
@@ -24,382 +24,357 @@
#include "sparse_defs.h"
struct backed_block {
- unsigned int block;
- unsigned int len;
- enum backed_block_type type;
- union {
- struct {
- void *data;
- } data;
- struct {
- char *filename;
- int64_t offset;
- } file;
- struct {
- int fd;
- int64_t offset;
- } fd;
- struct {
- uint32_t val;
- } fill;
- };
- struct backed_block *next;
+ unsigned int block;
+ unsigned int len;
+ enum backed_block_type type;
+ union {
+ struct {
+ void* data;
+ } data;
+ struct {
+ char* filename;
+ int64_t offset;
+ } file;
+ struct {
+ int fd;
+ int64_t offset;
+ } fd;
+ struct {
+ uint32_t val;
+ } fill;
+ };
+ struct backed_block* next;
};
struct backed_block_list {
- struct backed_block *data_blocks;
- struct backed_block *last_used;
- unsigned int block_size;
+ struct backed_block* data_blocks;
+ struct backed_block* last_used;
+ unsigned int block_size;
};
-struct backed_block *backed_block_iter_new(struct backed_block_list *bbl)
-{
- return bbl->data_blocks;
+struct backed_block* backed_block_iter_new(struct backed_block_list* bbl) {
+ return bbl->data_blocks;
}
-struct backed_block *backed_block_iter_next(struct backed_block *bb)
-{
- return bb->next;
+struct backed_block* backed_block_iter_next(struct backed_block* bb) {
+ return bb->next;
}
-unsigned int backed_block_len(struct backed_block *bb)
-{
- return bb->len;
+unsigned int backed_block_len(struct backed_block* bb) {
+ return bb->len;
}
-unsigned int backed_block_block(struct backed_block *bb)
-{
- return bb->block;
+unsigned int backed_block_block(struct backed_block* bb) {
+ return bb->block;
}
-void *backed_block_data(struct backed_block *bb)
-{
- assert(bb->type == BACKED_BLOCK_DATA);
- return bb->data.data;
+void* backed_block_data(struct backed_block* bb) {
+ assert(bb->type == BACKED_BLOCK_DATA);
+ return bb->data.data;
}
-const char *backed_block_filename(struct backed_block *bb)
-{
- assert(bb->type == BACKED_BLOCK_FILE);
- return bb->file.filename;
+const char* backed_block_filename(struct backed_block* bb) {
+ assert(bb->type == BACKED_BLOCK_FILE);
+ return bb->file.filename;
}
-int backed_block_fd(struct backed_block *bb)
-{
- assert(bb->type == BACKED_BLOCK_FD);
- return bb->fd.fd;
+int backed_block_fd(struct backed_block* bb) {
+ assert(bb->type == BACKED_BLOCK_FD);
+ return bb->fd.fd;
}
-int64_t backed_block_file_offset(struct backed_block *bb)
-{
- assert(bb->type == BACKED_BLOCK_FILE || bb->type == BACKED_BLOCK_FD);
- if (bb->type == BACKED_BLOCK_FILE) {
- return bb->file.offset;
- } else { /* bb->type == BACKED_BLOCK_FD */
- return bb->fd.offset;
- }
+int64_t backed_block_file_offset(struct backed_block* bb) {
+ assert(bb->type == BACKED_BLOCK_FILE || bb->type == BACKED_BLOCK_FD);
+ if (bb->type == BACKED_BLOCK_FILE) {
+ return bb->file.offset;
+ } else { /* bb->type == BACKED_BLOCK_FD */
+ return bb->fd.offset;
+ }
}
-uint32_t backed_block_fill_val(struct backed_block *bb)
-{
- assert(bb->type == BACKED_BLOCK_FILL);
- return bb->fill.val;
+uint32_t backed_block_fill_val(struct backed_block* bb) {
+ assert(bb->type == BACKED_BLOCK_FILL);
+ return bb->fill.val;
}
-enum backed_block_type backed_block_type(struct backed_block *bb)
-{
- return bb->type;
+enum backed_block_type backed_block_type(struct backed_block* bb) {
+ return bb->type;
}
-void backed_block_destroy(struct backed_block *bb)
-{
- if (bb->type == BACKED_BLOCK_FILE) {
- free(bb->file.filename);
- }
+void backed_block_destroy(struct backed_block* bb) {
+ if (bb->type == BACKED_BLOCK_FILE) {
+ free(bb->file.filename);
+ }
- free(bb);
+ free(bb);
}
-struct backed_block_list *backed_block_list_new(unsigned int block_size)
-{
- struct backed_block_list *b = reinterpret_cast<backed_block_list*>(
- calloc(sizeof(struct backed_block_list), 1));
- b->block_size = block_size;
- return b;
+struct backed_block_list* backed_block_list_new(unsigned int block_size) {
+ struct backed_block_list* b =
+ reinterpret_cast<backed_block_list*>(calloc(sizeof(struct backed_block_list), 1));
+ b->block_size = block_size;
+ return b;
}
-void backed_block_list_destroy(struct backed_block_list *bbl)
-{
- if (bbl->data_blocks) {
- struct backed_block *bb = bbl->data_blocks;
- while (bb) {
- struct backed_block *next = bb->next;
- backed_block_destroy(bb);
- bb = next;
- }
- }
-
- free(bbl);
+void backed_block_list_destroy(struct backed_block_list* bbl) {
+ if (bbl->data_blocks) {
+ struct backed_block* bb = bbl->data_blocks;
+ while (bb) {
+ struct backed_block* next = bb->next;
+ backed_block_destroy(bb);
+ bb = next;
+ }
+ }
+
+ free(bbl);
}
-void backed_block_list_move(struct backed_block_list *from,
- struct backed_block_list *to, struct backed_block *start,
- struct backed_block *end)
-{
- struct backed_block *bb;
-
- if (start == NULL) {
- start = from->data_blocks;
- }
-
- if (!end) {
- for (end = start; end && end->next; end = end->next)
- ;
- }
-
- if (start == NULL || end == NULL) {
- return;
- }
-
- from->last_used = NULL;
- to->last_used = NULL;
- if (from->data_blocks == start) {
- from->data_blocks = end->next;
- } else {
- for (bb = from->data_blocks; bb; bb = bb->next) {
- if (bb->next == start) {
- bb->next = end->next;
- break;
- }
- }
- }
-
- if (!to->data_blocks) {
- to->data_blocks = start;
- end->next = NULL;
- } else {
- for (bb = to->data_blocks; bb; bb = bb->next) {
- if (!bb->next || bb->next->block > start->block) {
- end->next = bb->next;
- bb->next = start;
- break;
- }
- }
- }
+void backed_block_list_move(struct backed_block_list* from, struct backed_block_list* to,
+ struct backed_block* start, struct backed_block* end) {
+ struct backed_block* bb;
+
+ if (start == NULL) {
+ start = from->data_blocks;
+ }
+
+ if (!end) {
+ for (end = start; end && end->next; end = end->next)
+ ;
+ }
+
+ if (start == NULL || end == NULL) {
+ return;
+ }
+
+ from->last_used = NULL;
+ to->last_used = NULL;
+ if (from->data_blocks == start) {
+ from->data_blocks = end->next;
+ } else {
+ for (bb = from->data_blocks; bb; bb = bb->next) {
+ if (bb->next == start) {
+ bb->next = end->next;
+ break;
+ }
+ }
+ }
+
+ if (!to->data_blocks) {
+ to->data_blocks = start;
+ end->next = NULL;
+ } else {
+ for (bb = to->data_blocks; bb; bb = bb->next) {
+ if (!bb->next || bb->next->block > start->block) {
+ end->next = bb->next;
+ bb->next = start;
+ break;
+ }
+ }
+ }
}
/* may free b */
-static int merge_bb(struct backed_block_list *bbl,
- struct backed_block *a, struct backed_block *b)
-{
- unsigned int block_len;
-
- /* Block doesn't exist (possible if one block is the last block) */
- if (!a || !b) {
- return -EINVAL;
- }
-
- assert(a->block < b->block);
-
- /* Blocks are of different types */
- if (a->type != b->type) {
- return -EINVAL;
- }
-
- /* Blocks are not adjacent */
- block_len = a->len / bbl->block_size; /* rounds down */
- if (a->block + block_len != b->block) {
- return -EINVAL;
- }
-
- switch (a->type) {
- case BACKED_BLOCK_DATA:
- /* Don't support merging data for now */
- return -EINVAL;
- case BACKED_BLOCK_FILL:
- if (a->fill.val != b->fill.val) {
- return -EINVAL;
- }
- break;
- case BACKED_BLOCK_FILE:
- /* Already make sure b->type is BACKED_BLOCK_FILE */
- if (strcmp(a->file.filename, b->file.filename) ||
- a->file.offset + a->len != b->file.offset) {
- return -EINVAL;
- }
- break;
- case BACKED_BLOCK_FD:
- if (a->fd.fd != b->fd.fd ||
- a->fd.offset + a->len != b->fd.offset) {
- return -EINVAL;
- }
- break;
- }
-
- /* Blocks are compatible and adjacent, with a before b. Merge b into a,
- * and free b */
- a->len += b->len;
- a->next = b->next;
-
- backed_block_destroy(b);
-
- return 0;
+static int merge_bb(struct backed_block_list* bbl, struct backed_block* a, struct backed_block* b) {
+ unsigned int block_len;
+
+ /* Block doesn't exist (possible if one block is the last block) */
+ if (!a || !b) {
+ return -EINVAL;
+ }
+
+ assert(a->block < b->block);
+
+ /* Blocks are of different types */
+ if (a->type != b->type) {
+ return -EINVAL;
+ }
+
+ /* Blocks are not adjacent */
+ block_len = a->len / bbl->block_size; /* rounds down */
+ if (a->block + block_len != b->block) {
+ return -EINVAL;
+ }
+
+ switch (a->type) {
+ case BACKED_BLOCK_DATA:
+ /* Don't support merging data for now */
+ return -EINVAL;
+ case BACKED_BLOCK_FILL:
+ if (a->fill.val != b->fill.val) {
+ return -EINVAL;
+ }
+ break;
+ case BACKED_BLOCK_FILE:
+ /* Already make sure b->type is BACKED_BLOCK_FILE */
+ if (strcmp(a->file.filename, b->file.filename) || a->file.offset + a->len != b->file.offset) {
+ return -EINVAL;
+ }
+ break;
+ case BACKED_BLOCK_FD:
+ if (a->fd.fd != b->fd.fd || a->fd.offset + a->len != b->fd.offset) {
+ return -EINVAL;
+ }
+ break;
+ }
+
+ /* Blocks are compatible and adjacent, with a before b. Merge b into a,
+ * and free b */
+ a->len += b->len;
+ a->next = b->next;
+
+ backed_block_destroy(b);
+
+ return 0;
}
-static int queue_bb(struct backed_block_list *bbl, struct backed_block *new_bb)
-{
- struct backed_block *bb;
-
- if (bbl->data_blocks == NULL) {
- bbl->data_blocks = new_bb;
- return 0;
- }
-
- if (bbl->data_blocks->block > new_bb->block) {
- new_bb->next = bbl->data_blocks;
- bbl->data_blocks = new_bb;
- return 0;
- }
-
- /* Optimization: blocks are mostly queued in sequence, so save the
- pointer to the last bb that was added, and start searching from
- there if the next block number is higher */
- if (bbl->last_used && new_bb->block > bbl->last_used->block)
- bb = bbl->last_used;
- else
- bb = bbl->data_blocks;
- bbl->last_used = new_bb;
-
- for (; bb->next && bb->next->block < new_bb->block; bb = bb->next)
- ;
-
- if (bb->next == NULL) {
- bb->next = new_bb;
- } else {
- new_bb->next = bb->next;
- bb->next = new_bb;
- }
-
- merge_bb(bbl, new_bb, new_bb->next);
- if (!merge_bb(bbl, bb, new_bb)) {
- /* new_bb destroyed, point to retained as last_used */
- bbl->last_used = bb;
- }
-
- return 0;
+static int queue_bb(struct backed_block_list* bbl, struct backed_block* new_bb) {
+ struct backed_block* bb;
+
+ if (bbl->data_blocks == NULL) {
+ bbl->data_blocks = new_bb;
+ return 0;
+ }
+
+ if (bbl->data_blocks->block > new_bb->block) {
+ new_bb->next = bbl->data_blocks;
+ bbl->data_blocks = new_bb;
+ return 0;
+ }
+
+ /* Optimization: blocks are mostly queued in sequence, so save the
+ pointer to the last bb that was added, and start searching from
+ there if the next block number is higher */
+ if (bbl->last_used && new_bb->block > bbl->last_used->block)
+ bb = bbl->last_used;
+ else
+ bb = bbl->data_blocks;
+ bbl->last_used = new_bb;
+
+ for (; bb->next && bb->next->block < new_bb->block; bb = bb->next)
+ ;
+
+ if (bb->next == NULL) {
+ bb->next = new_bb;
+ } else {
+ new_bb->next = bb->next;
+ bb->next = new_bb;
+ }
+
+ merge_bb(bbl, new_bb, new_bb->next);
+ if (!merge_bb(bbl, bb, new_bb)) {
+ /* new_bb destroyed, point to retained as last_used */
+ bbl->last_used = bb;
+ }
+
+ return 0;
}
/* Queues a fill block of memory to be written to the specified data blocks */
-int backed_block_add_fill(struct backed_block_list *bbl, unsigned int fill_val,
- unsigned int len, unsigned int block)
-{
- struct backed_block *bb = reinterpret_cast<backed_block*>(calloc(1, sizeof(struct backed_block)));
- if (bb == NULL) {
- return -ENOMEM;
- }
-
- bb->block = block;
- bb->len = len;
- bb->type = BACKED_BLOCK_FILL;
- bb->fill.val = fill_val;
- bb->next = NULL;
-
- return queue_bb(bbl, bb);
+int backed_block_add_fill(struct backed_block_list* bbl, unsigned int fill_val, unsigned int len,
+ unsigned int block) {
+ struct backed_block* bb = reinterpret_cast<backed_block*>(calloc(1, sizeof(struct backed_block)));
+ if (bb == NULL) {
+ return -ENOMEM;
+ }
+
+ bb->block = block;
+ bb->len = len;
+ bb->type = BACKED_BLOCK_FILL;
+ bb->fill.val = fill_val;
+ bb->next = NULL;
+
+ return queue_bb(bbl, bb);
}
/* Queues a block of memory to be written to the specified data blocks */
-int backed_block_add_data(struct backed_block_list *bbl, void *data,
- unsigned int len, unsigned int block)
-{
- struct backed_block *bb = reinterpret_cast<backed_block*>(calloc(1, sizeof(struct backed_block)));
- if (bb == NULL) {
- return -ENOMEM;
- }
-
- bb->block = block;
- bb->len = len;
- bb->type = BACKED_BLOCK_DATA;
- bb->data.data = data;
- bb->next = NULL;
-
- return queue_bb(bbl, bb);
+int backed_block_add_data(struct backed_block_list* bbl, void* data, unsigned int len,
+ unsigned int block) {
+ struct backed_block* bb = reinterpret_cast<backed_block*>(calloc(1, sizeof(struct backed_block)));
+ if (bb == NULL) {
+ return -ENOMEM;
+ }
+
+ bb->block = block;
+ bb->len = len;
+ bb->type = BACKED_BLOCK_DATA;
+ bb->data.data = data;
+ bb->next = NULL;
+
+ return queue_bb(bbl, bb);
}
/* Queues a chunk of a file on disk to be written to the specified data blocks */
-int backed_block_add_file(struct backed_block_list *bbl, const char *filename,
- int64_t offset, unsigned int len, unsigned int block)
-{
- struct backed_block *bb = reinterpret_cast<backed_block*>(calloc(1, sizeof(struct backed_block)));
- if (bb == NULL) {
- return -ENOMEM;
- }
-
- bb->block = block;
- bb->len = len;
- bb->type = BACKED_BLOCK_FILE;
- bb->file.filename = strdup(filename);
- bb->file.offset = offset;
- bb->next = NULL;
-
- return queue_bb(bbl, bb);
+int backed_block_add_file(struct backed_block_list* bbl, const char* filename, int64_t offset,
+ unsigned int len, unsigned int block) {
+ struct backed_block* bb = reinterpret_cast<backed_block*>(calloc(1, sizeof(struct backed_block)));
+ if (bb == NULL) {
+ return -ENOMEM;
+ }
+
+ bb->block = block;
+ bb->len = len;
+ bb->type = BACKED_BLOCK_FILE;
+ bb->file.filename = strdup(filename);
+ bb->file.offset = offset;
+ bb->next = NULL;
+
+ return queue_bb(bbl, bb);
}
/* Queues a chunk of a fd to be written to the specified data blocks */
-int backed_block_add_fd(struct backed_block_list *bbl, int fd, int64_t offset,
- unsigned int len, unsigned int block)
-{
- struct backed_block *bb = reinterpret_cast<backed_block*>(calloc(1, sizeof(struct backed_block)));
- if (bb == NULL) {
- return -ENOMEM;
- }
-
- bb->block = block;
- bb->len = len;
- bb->type = BACKED_BLOCK_FD;
- bb->fd.fd = fd;
- bb->fd.offset = offset;
- bb->next = NULL;
-
- return queue_bb(bbl, bb);
+int backed_block_add_fd(struct backed_block_list* bbl, int fd, int64_t offset, unsigned int len,
+ unsigned int block) {
+ struct backed_block* bb = reinterpret_cast<backed_block*>(calloc(1, sizeof(struct backed_block)));
+ if (bb == NULL) {
+ return -ENOMEM;
+ }
+
+ bb->block = block;
+ bb->len = len;
+ bb->type = BACKED_BLOCK_FD;
+ bb->fd.fd = fd;
+ bb->fd.offset = offset;
+ bb->next = NULL;
+
+ return queue_bb(bbl, bb);
}
-int backed_block_split(struct backed_block_list *bbl, struct backed_block *bb,
- unsigned int max_len)
-{
- struct backed_block *new_bb;
-
- max_len = ALIGN_DOWN(max_len, bbl->block_size);
-
- if (bb->len <= max_len) {
- return 0;
- }
-
- new_bb = reinterpret_cast<backed_block*>(malloc(sizeof(struct backed_block)));
- if (new_bb == NULL) {
- return -ENOMEM;
- }
-
- *new_bb = *bb;
-
- new_bb->len = bb->len - max_len;
- new_bb->block = bb->block + max_len / bbl->block_size;
- new_bb->next = bb->next;
- bb->next = new_bb;
- bb->len = max_len;
-
- switch (bb->type) {
- case BACKED_BLOCK_DATA:
- new_bb->data.data = (char *)bb->data.data + max_len;
- break;
- case BACKED_BLOCK_FILE:
- new_bb->file.offset += max_len;
- break;
- case BACKED_BLOCK_FD:
- new_bb->fd.offset += max_len;
- break;
- case BACKED_BLOCK_FILL:
- break;
- }
-
- return 0;
+int backed_block_split(struct backed_block_list* bbl, struct backed_block* bb,
+ unsigned int max_len) {
+ struct backed_block* new_bb;
+
+ max_len = ALIGN_DOWN(max_len, bbl->block_size);
+
+ if (bb->len <= max_len) {
+ return 0;
+ }
+
+ new_bb = reinterpret_cast<backed_block*>(malloc(sizeof(struct backed_block)));
+ if (new_bb == NULL) {
+ return -ENOMEM;
+ }
+
+ *new_bb = *bb;
+
+ new_bb->len = bb->len - max_len;
+ new_bb->block = bb->block + max_len / bbl->block_size;
+ new_bb->next = bb->next;
+ bb->next = new_bb;
+ bb->len = max_len;
+
+ switch (bb->type) {
+ case BACKED_BLOCK_DATA:
+ new_bb->data.data = (char*)bb->data.data + max_len;
+ break;
+ case BACKED_BLOCK_FILE:
+ new_bb->file.offset += max_len;
+ break;
+ case BACKED_BLOCK_FD:
+ new_bb->fd.offset += max_len;
+ break;
+ case BACKED_BLOCK_FILL:
+ break;
+ }
+
+ return 0;
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-03 19:11:56 +0000