diff --git a/libsparse/backed_block.c b/libsparse/backed_block.c
index 2548138..6e8ef44 100644
--- a/libsparse/backed_block.c
+++ b/libsparse/backed_block.c
@@ -33,32 +33,57 @@
 	u16 pad2;
 };
 
-static struct data_block *data_blocks = NULL;
-static struct data_block *last_used = NULL;
+struct backed_block_list {
+	struct data_block *data_blocks;
+	struct data_block *last_used;
+};
 
-static void queue_db(struct data_block *new_db)
+struct backed_block_list *backed_block_list_new(void)
+{
+	struct backed_block_list *b = calloc(sizeof(struct backed_block_list), 1);
+
+	return b;
+}
+
+void backed_block_list_destroy(struct backed_block_list *b)
+{
+	if (b->data_blocks) {
+		struct data_block *db = b->data_blocks;
+		while (db) {
+			struct data_block *next = db->next;
+			free((void*)db->filename);
+
+			free(db);
+			db = next;
+		}
+	}
+
+	free(b);
+}
+
+static void queue_db(struct backed_block_list *b, struct data_block *new_db)
 {
 	struct data_block *db;
 
-	if (data_blocks == NULL) {
-		data_blocks = new_db;
+	if (b->data_blocks == NULL) {
+		b->data_blocks = new_db;
 		return;
 	}
 
-	if (data_blocks->block > new_db->block) {
-		new_db->next = data_blocks;
-		data_blocks = new_db;
+	if (b->data_blocks->block > new_db->block) {
+		new_db->next = b->data_blocks;
+		b->data_blocks = new_db;
 		return;
 	}
 
 	/* Optimization: blocks are mostly queued in sequence, so save the
 	   pointer to the last db that was added, and start searching from
 	   there if the next block number is higher */
-	if (last_used && new_db->block > last_used->block)
-		db = last_used;
+	if (b->last_used && new_db->block > b->last_used->block)
+		db = b->last_used;
 	else
-		db = data_blocks;
-	last_used = new_db;
+		db = b->data_blocks;
+	b->last_used = new_db;
 
 	for (; db->next && db->next->block < new_db->block; db = db->next)
 		;
@@ -72,9 +97,10 @@
 }
 
 /* Queues a fill block of memory to be written to the specified data blocks */
-void queue_fill_block(unsigned int fill_val, unsigned int len, unsigned int block)
+void queue_fill_block(struct backed_block_list *b, unsigned int fill_val,
+		unsigned int len, unsigned int block)
 {
-	struct data_block *db = malloc(sizeof(struct data_block));
+	struct data_block *db = calloc(1, sizeof(struct data_block));
 	if (db == NULL) {
 		error_errno("malloc");
 		return;
@@ -88,11 +114,12 @@
 	db->filename = NULL;
 	db->next = NULL;
 
-	queue_db(db);
+	queue_db(b, db);
 }
 
 /* Queues a block of memory to be written to the specified data blocks */
-void queue_data_block(void *data, unsigned int len, unsigned int block)
+void queue_data_block(struct backed_block_list *b, void *data, unsigned int len,
+		unsigned int block)
 {
 	struct data_block *db = malloc(sizeof(struct data_block));
 	if (db == NULL) {
@@ -107,12 +134,12 @@
 	db->fill = 0;
 	db->next = NULL;
 
-	queue_db(db);
+	queue_db(b, db);
 }
 
 /* Queues a chunk of a file on disk to be written to the specified data blocks */
-void queue_data_file(const char *filename, int64_t offset, unsigned int len,
-		unsigned int block)
+void queue_data_file(struct backed_block_list *b, const char *filename,
+		int64_t offset, unsigned int len, unsigned int block)
 {
 	struct data_block *db = malloc(sizeof(struct data_block));
 	if (db == NULL) {
@@ -128,19 +155,21 @@
 	db->fill = 0;
 	db->next = NULL;
 
-	queue_db(db);
+	queue_db(b, db);
 }
 
 /* Iterates over the queued data blocks, calling data_func for each contiguous
    data block, and file_func for each contiguous file block */
-void for_each_data_block(data_block_callback_t data_func,
+void for_each_data_block(struct backed_block_list *b,
+	data_block_callback_t data_func,
 	data_block_file_callback_t file_func,
-	data_block_fill_callback_t fill_func, void *priv, unsigned int block_size)
+	data_block_fill_callback_t fill_func,
+	void *priv, unsigned int block_size)
 {
 	struct data_block *db;
 	u32 last_block = 0;
 
-	for (db = data_blocks; db; db = db->next) {
+	for (db = b->data_blocks; db; db = db->next) {
 		if (db->block < last_block)
 			error("data blocks out of order: %u < %u", db->block, last_block);
 		last_block = db->block + DIV_ROUND_UP(db->len, block_size) - 1;
@@ -153,27 +182,3 @@
 			data_func(priv, (u64)db->block * block_size, db->data, db->len);
 	}
 }
-
-/* Frees the memory used by the linked list of data blocks */
-void free_data_blocks()
-{
-	if (!data_blocks) return;
-	struct data_block *db = data_blocks;
-	while (db) {
-		struct data_block *next = db->next;
-		free((void*)db->filename);
-
-                // There used to be a free() of db->data here, but it
-		// made the function crash since queue_data_block() is
-		// sometimes passed pointers it can't take ownership of
-		// (like a pointer into the middle of an allocated
-		// block).  It's not clear what the queue_data_block
-		// contract is supposed to be, but we'd rather leak
-		// memory than crash.
-
-		free(db);
-		db = next;
-	}
-	data_blocks = NULL;
-	last_used = NULL;
-}
diff --git a/libsparse/backed_block.h b/libsparse/backed_block.h
index 7b7c90a..d1bfa1e 100644
--- a/libsparse/backed_block.h
+++ b/libsparse/backed_block.h
@@ -17,23 +17,29 @@
 #ifndef _BACKED_BLOCK_H_
 #define _BACKED_BLOCK_H_
 
-#include <sparse/sparse.h>
+struct backed_block_list;
 
-typedef void (*data_block_callback_t)(void *priv, int64_t off, void *data, int len);
-typedef void (*data_block_fill_callback_t)(void *priv, int64_t off, unsigned int fill_val, int len);
+typedef void (*data_block_callback_t)(void *priv, int64_t off, void *data,
+		int len);
+typedef void (*data_block_fill_callback_t)(void *priv, int64_t off,
+		unsigned int fill_val, int len);
 typedef void (*data_block_file_callback_t)(void *priv, int64_t off,
-					   const char *file, int64_t offset,
-					   int len);
+		const char *file, int64_t offset, int len);
 
-void for_each_data_block(data_block_callback_t data_func,
+void for_each_data_block(struct backed_block_list *b,
+	data_block_callback_t data_func,
 	data_block_file_callback_t file_func,
-	data_block_fill_callback_t fill_func, void *priv, unsigned int);
+	data_block_fill_callback_t fill_func,
+	void *priv, unsigned int);
 
-void queue_data_block(void *data, unsigned int len, unsigned int block);
-void queue_fill_block(unsigned int fill_val, unsigned int len, unsigned int block);
-void queue_data_file(const char *filename, int64_t offset, unsigned int len,
+void queue_data_block(struct backed_block_list *b,void *data, unsigned int len,
 		unsigned int block);
+void queue_fill_block(struct backed_block_list *b,unsigned int fill_val,
+		unsigned int len, unsigned int block);
+void queue_data_file(struct backed_block_list *b,const char *filename,
+		int64_t offset, unsigned int len, unsigned int block);
 
-void free_data_blocks();
+struct backed_block_list *backed_block_list_new(void);
+void backed_block_list_destroy(struct backed_block_list *b);
 
 #endif
diff --git a/libsparse/sparse.c b/libsparse/sparse.c
index d6f5561..a6134c9 100644
--- a/libsparse/sparse.c
+++ b/libsparse/sparse.c
@@ -32,7 +32,11 @@
 		return NULL;
 	}
 
-	/* TODO: allocate backed block list */
+	s->backed_block_list = backed_block_list_new();
+	if (!s->backed_block_list) {
+		free(s);
+		return NULL;
+	}
 
 	s->block_size = block_size;
 	s->len = len;
@@ -42,14 +46,14 @@
 
 void sparse_file_destroy(struct sparse_file *s)
 {
-	free_data_blocks();
+	backed_block_list_destroy(s->backed_block_list);
 	free(s);
 }
 
 int sparse_file_add_data(struct sparse_file *s,
 		void *data, unsigned int len, unsigned int block)
 {
-	queue_data_block(data, len, block);
+	queue_data_block(s->backed_block_list, data, len, block);
 
 	return 0;
 }
@@ -57,7 +61,7 @@
 int sparse_file_add_fill(struct sparse_file *s,
 		uint32_t fill_val, unsigned int len, unsigned int block)
 {
-	queue_fill_block(fill_val, len, block);
+	queue_fill_block(s->backed_block_list, fill_val, len, block);
 
 	return 0;
 }
@@ -66,7 +70,7 @@
 		const char *filename, int64_t file_offset, unsigned int len,
 		unsigned int block)
 {
-	queue_data_file(filename, file_offset, len, block);
+	queue_data_file(s->backed_block_list, filename, file_offset, len, block);
 
 	return 0;
 }
@@ -105,11 +109,13 @@
 	count_chunks->chunks++;
 }
 
-static int count_sparse_chunks(unsigned int block_size, int64_t len)
+static int count_sparse_chunks(struct backed_block_list *b,
+		unsigned int block_size, int64_t len)
 {
 	struct count_chunks count_chunks = {0, 0, block_size};
 
-	for_each_data_block(count_data_block, count_file_block, count_fill_block, &count_chunks, block_size);
+	for_each_data_block(b, count_data_block, count_file_block,
+			count_fill_block, &count_chunks, block_size);
 
 	if (count_chunks.cur_ptr != len)
 		count_chunks.chunks++;
@@ -136,14 +142,16 @@
 int sparse_file_write(struct sparse_file *s, int fd, bool gz, bool sparse,
 		bool crc)
 {
-	int chunks = count_sparse_chunks(s->block_size, s->len);
+	int chunks = count_sparse_chunks(s->backed_block_list, s->block_size,
+			s->len);
 	struct output_file *out = open_output_fd(fd, s->block_size, s->len,
 			gz, sparse, chunks, crc);
 
 	if (!out)
 		return -ENOMEM;
 
-	for_each_data_block(ext4_write_data_block, ext4_write_data_file, ext4_write_fill_block, out, s->block_size);
+	for_each_data_block(s->backed_block_list, ext4_write_data_block,
+			ext4_write_data_file, ext4_write_fill_block, out, s->block_size);
 
 	if (s->len)
 		pad_output_file(out, s->len);
diff --git a/libsparse/sparse_file.h b/libsparse/sparse_file.h
index 05a78d9..fae1c16 100644
--- a/libsparse/sparse_file.h
+++ b/libsparse/sparse_file.h
@@ -23,6 +23,7 @@
 	unsigned int block_size;
 	int64_t len;
 
+	struct backed_block_list *backed_block_list;
 	struct output_file *out;
 };