libsqfs: Implement exact matching of fragments

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

4 files changed, 187 insertions, 7 deletions

diff --git a/lib/sqfs/block_processor/common.c b/lib/sqfs/block_processor/common.c
index 97cb790..d6c0889 100644
--- a/lib/sqfs/block_processor/common.c
+++ b/lib/sqfs/block_processor/common.c
@@ -176,8 +176,11 @@ static int process_completed_fragment(sqfs_block_processor_t *proc,
 		search.hash = frag->checksum;
 		search.size = frag->size;
 
+		proc->frag_cmp_current = frag;
 		entry = hash_table_search_pre_hashed(proc->frag_ht,
 						     search.hash, &search);
+		proc->frag_cmp_current = NULL;
+
 		if (entry != NULL) {
 			if (frag->inode != NULL) {
 				chunk = entry->data;
@@ -238,8 +241,11 @@ static int process_completed_fragment(sqfs_block_processor_t *proc,
 		chunk->size = frag->size;
 		chunk->hash = frag->checksum;
 
+		proc->frag_cmp_current = frag;
 		entry = hash_table_insert_pre_hashed(proc->frag_ht, chunk->hash,
 						     chunk, chunk);
+		proc->frag_cmp_current = NULL;
+
 		if (entry == NULL) {
 			free(chunk);
 			goto fail_outblk;
@@ -268,12 +274,69 @@ static uint32_t chunk_info_hash(void *user, const void *key)
 	return chunk->hash;
 }
 
-static bool chunk_info_equals(void *user, const void *a, const void *b)
+static bool chunk_info_equals(void *user, const void *k, const void *c)
 {
-	const chunk_info_t *a_ = a, *b_ = b;
-	(void)user;
-	return a_->size == b_->size &&
-	       a_->hash == b_->hash;
+	const chunk_info_t *key = k, *cmp = c;
+	sqfs_block_processor_t *proc = user;
+	sqfs_fragment_t frag;
+	unsigned char *temp;
+	size_t size;
+	int ret;
+
+	if (key->size != cmp->size || key->hash != cmp->hash)
+		return false;
+
+	if (proc->file == NULL || proc->uncmp == NULL)
+		return true;
+
+	ret = proc->compare_frag_in_flight(proc, proc->frag_cmp_current,
+					   cmp->index, cmp->offset);
+	if (ret == 0)
+		return true;
+
+	if (proc->buffered_index != cmp->index ||
+	    proc->buffered_blk_size == 0) {
+		if (sqfs_frag_table_lookup(proc->frag_tbl, cmp->index, &frag))
+			return false;
+
+		proc->buffered_index = 0xFFFFFFFF;
+		size = SQFS_ON_DISK_BLOCK_SIZE(frag.size);
+
+		if (SQFS_IS_BLOCK_COMPRESSED(frag.size)) {
+			temp = proc->frag_buffer + proc->max_block_size;
+
+			ret = proc->file->read_at(proc->file, frag.start_offset,
+						  temp, size);
+			if (ret != 0)
+				return false;
+
+			ret = proc->uncmp->do_block(proc->uncmp, temp, size,
+						    proc->frag_buffer,
+						    proc->max_block_size);
+			if (ret <= 0)
+				return false;
+
+			size = ret;
+		} else {
+			ret = proc->file->read_at(proc->file, frag.start_offset,
+						  proc->frag_buffer, size);
+			if (ret != 0)
+				return false;
+		}
+
+		proc->buffered_index = cmp->index;
+		proc->buffered_blk_size = size;
+	}
+
+	if (cmp->offset >= proc->buffered_blk_size)
+		return false;
+
+	if (cmp->size > (proc->buffered_blk_size - cmp->offset))
+		return false;
+
+	return memcmp(proc->frag_buffer + cmp->offset,
+		      proc->frag_cmp_current->data,
+		      cmp->size) == 0;
 }
 
 static void ht_delete_function(struct hash_entry *entry)
@@ -289,6 +352,7 @@ void block_processor_cleanup(sqfs_block_processor_t *base)
 		release_old_block(base, base->frag_block);
 
 	free(base->blk_current);
+	free(base->frag_buffer);
 
 	while (base->free_list != NULL) {
 		it = base->free_list;
@@ -311,12 +375,22 @@ int block_processor_init(sqfs_block_processor_t *base,
 	base->wr = desc->wr;
 	base->file = desc->file;
 	base->uncmp = desc->uncmp;
+	base->buffered_index = 0xFFFFFFFF;
 	base->stats.size = sizeof(base->stats);
 
+	if (desc->file != NULL && desc->uncmp != NULL && desc->tbl != NULL) {
+		base->frag_buffer = malloc(2 * desc->max_block_size);
+		if (base->frag_buffer == NULL)
+			return SQFS_ERROR_ALLOC;
+	}
+
 	base->frag_ht = hash_table_create(chunk_info_hash, chunk_info_equals);
-	if (base->frag_ht == NULL)
+	if (base->frag_ht == NULL) {
+		free(base->frag_buffer);
 		return SQFS_ERROR_ALLOC;
+	}
 
+	base->frag_ht->user = base;
 	return 0;
 }
 
diff --git a/lib/sqfs/block_processor/internal.h b/lib/sqfs/block_processor/internal.h
index efea3d4..4699dc6 100644
--- a/lib/sqfs/block_processor/internal.h
+++ b/lib/sqfs/block_processor/internal.h
@@ -83,6 +83,10 @@ struct sqfs_block_processor_t {
 
 	sqfs_file_t *file;
 	sqfs_compressor_t *uncmp;
+	sqfs_block_t *frag_cmp_current;
+	sqfs_u8 *frag_buffer;
+	sqfs_u32 buffered_index;
+	sqfs_u32 buffered_blk_size;
 
 	int (*process_completed_block)(sqfs_block_processor_t *proc,
 				       sqfs_block_t *block);
@@ -94,6 +98,10 @@ struct sqfs_block_processor_t {
 	int (*process_block)(sqfs_block_t *block, sqfs_compressor_t *cmp,
 			     sqfs_u8 *scratch, size_t scratch_size);
 
+	int (*compare_frag_in_flight)(sqfs_block_processor_t *proc,
+				      sqfs_block_t *frag, sqfs_u32 index,
+				      sqfs_u32 offset);
+
 	int (*append_to_work_queue)(sqfs_block_processor_t *proc,
 				    sqfs_block_t *block);
 
diff --git a/lib/sqfs/block_processor/serial.c b/lib/sqfs/block_processor/serial.c
index daa11fe..b20d5b0 100644
--- a/lib/sqfs/block_processor/serial.c
+++ b/lib/sqfs/block_processor/serial.c
@@ -61,6 +61,22 @@ static int block_processor_sync(sqfs_block_processor_t *proc)
 	return ((serial_block_processor_t *)proc)->status;
 }
 
+static int compare_frag_in_flight(sqfs_block_processor_t *proc,
+				  sqfs_block_t *frag, sqfs_u32 index,
+				  sqfs_u32 offset)
+{
+	if (proc->frag_block == NULL || index != proc->frag_block->index)
+		return -1;
+
+	if (offset >= proc->frag_block->size)
+		return -1;
+
+	if (frag->size > (proc->frag_block->size - offset))
+		return -1;
+
+	return memcmp(proc->frag_block->data + offset, frag->data, frag->size);
+}
+
 int sqfs_block_processor_create_ex(const sqfs_block_processor_desc_t *desc,
 				   sqfs_block_processor_t **out)
 {
@@ -82,6 +98,7 @@ int sqfs_block_processor_create_ex(const sqfs_block_processor_desc_t *desc,
 
 	proc->base.sync = block_processor_sync;
 	proc->base.append_to_work_queue = append_to_work_queue;
+	proc->base.compare_frag_in_flight = compare_frag_in_flight;
 	((sqfs_object_t *)proc)->destroy = block_processor_destroy;
 
 	*out = (sqfs_block_processor_t *)proc;
diff --git a/lib/sqfs/block_processor/winpthread.c b/lib/sqfs/block_processor/winpthread.c
index c3e3d13..806c749 100644
--- a/lib/sqfs/block_processor/winpthread.c
+++ b/lib/sqfs/block_processor/winpthread.c
@@ -78,6 +78,8 @@ struct compress_worker_t {
 	thread_pool_processor_t *shared;
 	sqfs_compressor_t *cmp;
 	THREAD_HANDLE thread;
+	sqfs_u32 frag_blk_index;
+	sqfs_u32 frag_blk_size;
 	sqfs_u8 scratch[];
 };
 
@@ -178,6 +180,14 @@ static THREAD_TYPE worker_proc(THREAD_ARG arg)
 			store_completed_block(shared, blk, status);
 
 		blk = get_next_work_item(shared);
+
+		if (blk != NULL && (blk->flags & SQFS_BLK_FRAGMENT_BLOCK) &&
+		    shared->base.uncmp != NULL && shared->base.file != NULL) {
+			memcpy(worker->scratch + shared->base.max_block_size,
+			       blk->data, blk->size);
+			worker->frag_blk_index = blk->index;
+			worker->frag_blk_size = blk->size;
+		}
 		UNLOCK(&shared->mtx);
 
 		if (blk == NULL)
@@ -388,6 +398,70 @@ static int append_to_work_queue(sqfs_block_processor_t *proc,
 	return status;
 }
 
+static sqfs_block_t *find_frag_blk_in_queue(sqfs_block_t *q, sqfs_u32 index)
+{
+	while (q != NULL) {
+		if ((q->flags & SQFS_BLK_FRAGMENT_BLOCK) && q->index == index)
+			break;
+		q = q->next;
+	}
+	return q;
+}
+
+static int compare_frag_in_flight(sqfs_block_processor_t *proc,
+				  sqfs_block_t *frag, sqfs_u32 index,
+				  sqfs_u32 offset)
+{
+	thread_pool_processor_t *thproc = (thread_pool_processor_t *)proc;
+	sqfs_block_t *it = NULL;
+	void *blockbuf = NULL;
+	size_t i, size = 0;
+	int ret;
+
+	if (proc->frag_block != NULL && proc->frag_block->index == index)
+		it = proc->frag_block;
+
+	if (it == NULL)
+		it = find_frag_blk_in_queue(thproc->proc_queue, index);
+
+	if (it == NULL)
+		it = find_frag_blk_in_queue(thproc->io_queue, index);
+
+	if (it == NULL)
+		it = find_frag_blk_in_queue(thproc->done, index);
+
+	if (it == NULL) {
+		for (i = 0; i < thproc->num_workers; ++i) {
+			if (thproc->workers[i]->frag_blk_index == index) {
+				size = thproc->workers[i]->frag_blk_size;
+				blockbuf = thproc->workers[i]->scratch +
+					proc->max_block_size;
+				break;
+			}
+		}
+	} else if (it->flags & SQFS_BLK_IS_COMPRESSED) {
+		proc->buffered_index = 0xFFFFFFFF;
+		blockbuf = proc->frag_buffer;
+		ret = proc->uncmp->do_block(proc->uncmp, it->data, it->size,
+					    blockbuf, proc->max_block_size);
+		if (ret <= 0)
+			return -1;
+		proc->buffered_index = it->index;
+		size = ret;
+	} else {
+		blockbuf = it->data;
+		size = it->size;
+	}
+
+	if (blockbuf == NULL || size == 0)
+		return -1;
+
+	if (offset >= size || frag->size > (size - offset))
+		return -1;
+
+	return memcmp((const char *)blockbuf + offset, frag->data, frag->size);
+}
+
 static int block_processor_sync(sqfs_block_processor_t *proc)
 {
 	return append_to_work_queue(proc, NULL);
@@ -398,6 +472,7 @@ int sqfs_block_processor_create_ex(const sqfs_block_processor_desc_t *desc,
 {
 	thread_pool_processor_t *proc;
 	unsigned int i, num_workers;
+	size_t scratch_size;
 	sigset_t oldset;
 	int ret;
 
@@ -419,6 +494,7 @@ int sqfs_block_processor_create_ex(const sqfs_block_processor_desc_t *desc,
 
 	proc->base.sync = block_processor_sync;
 	proc->base.append_to_work_queue = append_to_work_queue;
+	proc->base.compare_frag_in_flight = compare_frag_in_flight;
 	proc->num_workers = num_workers;
 	proc->max_backlog = desc->max_backlog;
 	((sqfs_object_t *)proc)->destroy = block_processor_destroy;
@@ -430,8 +506,12 @@ int sqfs_block_processor_create_ex(const sqfs_block_processor_desc_t *desc,
 	SIGNAL_DISABLE(&oldset);
 
 	for (i = 0; i < num_workers; ++i) {
+		scratch_size = desc->max_block_size;
+		if (desc->uncmp != NULL && desc->file != NULL)
+			scratch_size *= 2;
+
 		proc->workers[i] = alloc_flex(sizeof(compress_worker_t),
-					      1, desc->max_block_size);
+					      1, scratch_size);
 
 		if (proc->workers[i] == NULL) {
 			ret = SQFS_ERROR_ALLOC;
@@ -440,6 +520,7 @@ int sqfs_block_processor_create_ex(const sqfs_block_processor_desc_t *desc,
 
 		proc->workers[i]->shared = proc;
 		proc->workers[i]->cmp = sqfs_copy(desc->cmp);
+		proc->workers[i]->frag_blk_index = 0xFFFFFFFF;
 
 		if (proc->workers[i]->cmp == NULL) {
 			ret = SQFS_ERROR_ALLOC;