squashfs-tools/squashfs-tools/mksquashfs.c

/*
 * Create a squashfs filesystem.  This is a highly compressed read only
 * filesystem.
 *
 * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011,
 * 2012, 2013, 2014
 * Phillip Lougher <phillip@squashfs.org.uk>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2,
 * or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 * mksquashfs.c
 */

#define FALSE 0
#define TRUE 1
#define MAX_LINE 16384

#include <pwd.h>
#include <grp.h>
#include <time.h>
#include <unistd.h>
#include <stdio.h>
#include <stddef.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <errno.h>
#include <dirent.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>
#include <setjmp.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <pthread.h>
#include <regex.h>
#include <fnmatch.h>
#include <sys/wait.h>
#include <limits.h>
#include <ctype.h>

#ifndef FNM_EXTMATCH /* glibc extension */
    #define FNM_EXTMATCH 0
#endif

#ifndef linux
#define __BYTE_ORDER BYTE_ORDER
#define __BIG_ENDIAN BIG_ENDIAN
#define __LITTLE_ENDIAN LITTLE_ENDIAN
#include <sys/sysctl.h>
#else
#include <endian.h>
#include <sys/sysinfo.h>
#endif

#include "squashfs_fs.h"
#include "squashfs_swap.h"
#include "mksquashfs.h"
#include "sort.h"
#include "pseudo.h"
#include "compressor.h"
#include "xattr.h"
#include "action.h"
#include "error.h"
#include "progressbar.h"
#include "info.h"
#include "caches-queues-lists.h"
#include "read_fs.h"
#include "restore.h"
#include "process_fragments.h"

/* ANDROID CHANGES START*/
#ifdef ANDROID
#include "android.h"
#include "private/android_filesystem_config.h"
#include "private/canned_fs_config.h"
int android_config = FALSE;
char *context_file = NULL;
char *mount_point = NULL;
char *target_out_path = NULL;
fs_config_func_t fs_config_func = NULL;
#endif
/* ANDROID CHANGES END */

int delete = FALSE;
int fd;
struct squashfs_super_block sBlk;

/* filesystem flags for building */
int comp_opts = FALSE;
int no_xattrs = XATTR_DEF;
int noX = FALSE;
int duplicate_checking = TRUE;
int noF = FALSE;
int no_fragments = FALSE;
int always_use_fragments = FALSE;
int noI = FALSE;
int noD = FALSE;
int silent = TRUE;
int exportable = TRUE;
int sparse_files = TRUE;
int old_exclude = TRUE;
int use_regex = FALSE;
int nopad = FALSE;
int exit_on_error = FALSE;

long long global_uid = -1, global_gid = -1;

/* superblock attributes */
int block_size = SQUASHFS_FILE_SIZE, block_log;
unsigned int id_count = 0;
int file_count = 0, sym_count = 0, dev_count = 0, dir_count = 0, fifo_count = 0,
	sock_count = 0;

/* write position within data section */
long long bytes = 0, total_bytes = 0;

/* in memory directory table - possibly compressed */
char *directory_table = NULL;
unsigned int directory_bytes = 0, directory_size = 0, total_directory_bytes = 0;

/* cached directory table */
char *directory_data_cache = NULL;
unsigned int directory_cache_bytes = 0, directory_cache_size = 0;

/* in memory inode table - possibly compressed */
char *inode_table = NULL;
unsigned int inode_bytes = 0, inode_size = 0, total_inode_bytes = 0;

/* cached inode table */
char *data_cache = NULL;
unsigned int cache_bytes = 0, cache_size = 0, inode_count = 0;

/* inode lookup table */
squashfs_inode *inode_lookup_table = NULL;

/* in memory directory data */
#define I_COUNT_SIZE		128
#define DIR_ENTRIES		32
#define INODE_HASH_SIZE		65536
#define INODE_HASH_MASK		(INODE_HASH_SIZE - 1)
#define INODE_HASH(dev, ino)	(ino & INODE_HASH_MASK)

struct cached_dir_index {
	struct squashfs_dir_index	index;
	char				*name;
};

struct directory {
	unsigned int		start_block;
	unsigned int		size;
	unsigned char		*buff;
	unsigned char		*p;
	unsigned int		entry_count;
	unsigned char		*entry_count_p;
	unsigned int		i_count;
	unsigned int		i_size;
	struct cached_dir_index	*index;
	unsigned char		*index_count_p;
	unsigned int		inode_number;
};

struct inode_info *inode_info[INODE_HASH_SIZE];

/* hash tables used to do fast duplicate searches in duplicate check */
struct file_info *dupl[65536];
int dup_files = 0;

/* exclude file handling */
/* list of exclude dirs/files */
struct exclude_info {
	dev_t			st_dev;
	ino_t			st_ino;
};

#define EXCLUDE_SIZE 8192
int exclude = 0;
struct exclude_info *exclude_paths = NULL;
int old_excluded(char *filename, struct stat *buf);

struct path_entry {
	char *name;
	regex_t *preg;
	struct pathname *paths;
};

struct pathname {
	int names;
	struct path_entry *name;
};

struct pathnames {
	int count;
	struct pathname *path[0];
};
#define PATHS_ALLOC_SIZE 10

struct pathnames *paths = NULL;
struct pathname *path = NULL;
struct pathname *stickypath = NULL;
int excluded(char *name, struct pathnames *paths, struct pathnames **new);

int fragments = 0;

#define FRAG_SIZE 32768

struct squashfs_fragment_entry *fragment_table = NULL;
int fragments_outstanding = 0;

int fragments_locked = FALSE;

/* current inode number for directories and non directories */
unsigned int inode_no = 1;
unsigned int root_inode_number = 0;

/* list of source dirs/files */
int source = 0;
char **source_path;

/* list of root directory entries read from original filesystem */
int old_root_entries = 0;
struct old_root_entry_info {
	char			*name;
	struct inode_info	inode;
};
struct old_root_entry_info *old_root_entry;

/* restore orignal filesystem state if appending to existing filesystem is
 * cancelled */
int appending = FALSE;
char *sdata_cache, *sdirectory_data_cache, *sdirectory_compressed;

long long sbytes, stotal_bytes;

unsigned int sinode_bytes, scache_bytes, sdirectory_bytes,
	sdirectory_cache_bytes, sdirectory_compressed_bytes,
	stotal_inode_bytes, stotal_directory_bytes,
	sinode_count = 0, sfile_count, ssym_count, sdev_count,
	sdir_count, sfifo_count, ssock_count, sdup_files;
int sfragments;
int threads;

/* flag whether destination file is a block device */
int block_device = FALSE;

/* flag indicating whether files are sorted using sort list(s) */
int sorted = FALSE;

/* save destination file name for deleting on error */
char *destination_file = NULL;

/* recovery file for abnormal exit on appending */
char *recovery_file = NULL;
int recover = TRUE;

struct id *id_hash_table[ID_ENTRIES];
struct id *id_table[SQUASHFS_IDS], *sid_table[SQUASHFS_IDS];
unsigned int uid_count = 0, guid_count = 0;
unsigned int sid_count = 0, suid_count = 0, sguid_count = 0;

struct cache *reader_buffer, *fragment_buffer, *reserve_cache;
struct cache *bwriter_buffer, *fwriter_buffer;
struct queue *to_reader, *to_deflate, *to_writer, *from_writer,
	*to_frag, *locked_fragment, *to_process_frag;
struct seq_queue *to_main;
pthread_t reader_thread, writer_thread, main_thread;
pthread_t *deflator_thread, *frag_deflator_thread, *frag_thread;
pthread_t *restore_thread = NULL;
pthread_mutex_t	fragment_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t	pos_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t	dup_mutex = PTHREAD_MUTEX_INITIALIZER;

/* user options that control parallelisation */
int processors = -1;
int bwriter_size;

/* compression operations */
struct compressor *comp = NULL;
int compressor_opt_parsed = FALSE;
void *stream = NULL;

/* xattr stats */
unsigned int xattr_bytes = 0, total_xattr_bytes = 0;

/* fragment to file mapping used when appending */
int append_fragments = 0;
struct append_file **file_mapping;

/* root of the in-core directory structure */
struct dir_info *root_dir;

static char *read_from_disk(long long start, unsigned int avail_bytes);
void add_old_root_entry(char *name, squashfs_inode inode, int inode_number,
	int type);
struct file_info *duplicate(long long file_size, long long bytes,
	unsigned int **block_list, long long *start, struct fragment **fragment,
	struct file_buffer *file_buffer, int blocks, unsigned short checksum,
	int checksum_flag);
struct dir_info *dir_scan1(char *, char *, struct pathnames *,
	struct dir_ent *(_readdir)(struct dir_info *), int);
void dir_scan2(struct dir_info *dir, struct pseudo *pseudo);
void dir_scan3(struct dir_info *dir);
void dir_scan4(struct dir_info *dir);
void dir_scan5(struct dir_info *dir);
void dir_scan6(struct dir_info *dir);
void dir_scan7(squashfs_inode *inode, struct dir_info *dir_info);
struct file_info *add_non_dup(long long file_size, long long bytes,
	unsigned int *block_list, long long start, struct fragment *fragment,
	unsigned short checksum, unsigned short fragment_checksum,
	int checksum_flag, int checksum_frag_flag);
long long generic_write_table(int, void *, int, void *, int);
void restorefs();
struct dir_info *scan1_opendir(char *pathname, char *subpath, int depth);
void write_filesystem_tables(struct squashfs_super_block *sBlk, int nopad);
unsigned short get_checksum_mem(char *buff, int bytes);
void check_usable_phys_mem(int total_mem);


void prep_exit()
{
	if(restore_thread) {
		if(pthread_self() == *restore_thread) {
			/*
			 * Recursive failure when trying to restore filesystem!
			 * Nothing to do except to exit, otherwise we'll just
			 * appear to hang.  The user should be able to restore
			 * from the recovery file (which is why it was added, in
			 * case of catastrophic failure in Mksquashfs)
			 */
			exit(1);
		} else {
			/* signal the restore thread to restore */
			pthread_kill(*restore_thread, SIGUSR1);
			pthread_exit(NULL);
		}
	} else if(delete) {
		if(destination_file && !block_device)
			unlink(destination_file);
	} else if(recovery_file)
		unlink(recovery_file);
}


int add_overflow(int a, int b)
{
	return (INT_MAX - a) < b;
}


int shift_overflow(int a, int shift)
{
	return (INT_MAX >> shift) < a;
}

 
int multiply_overflow(int a, int multiplier)
{
	return (INT_MAX / multiplier) < a;
}


int multiply_overflowll(long long a, int multiplier)
{
	return (LLONG_MAX / multiplier) < a;
}


#define MKINODE(A)	((squashfs_inode)(((squashfs_inode) inode_bytes << 16) \
			+ (((char *)A) - data_cache)))


void restorefs()
{
	ERROR("Exiting - restoring original filesystem!\n\n");

	bytes = sbytes;
	memcpy(data_cache, sdata_cache, cache_bytes = scache_bytes);
	memcpy(directory_data_cache, sdirectory_data_cache,
		sdirectory_cache_bytes);
	directory_cache_bytes = sdirectory_cache_bytes;
	inode_bytes = sinode_bytes;
	directory_bytes = sdirectory_bytes;
 	memcpy(directory_table + directory_bytes, sdirectory_compressed,
		sdirectory_compressed_bytes);
 	directory_bytes += sdirectory_compressed_bytes;
	total_bytes = stotal_bytes;
	total_inode_bytes = stotal_inode_bytes;
	total_directory_bytes = stotal_directory_bytes;
	inode_count = sinode_count;
	file_count = sfile_count;
	sym_count = ssym_count;
	dev_count = sdev_count;
	dir_count = sdir_count;
	fifo_count = sfifo_count;
	sock_count = ssock_count;
	dup_files = sdup_files;
	fragments = sfragments;
	id_count = sid_count;
	restore_xattrs();
	write_filesystem_tables(&sBlk, nopad);
	exit(1);
}


void sighandler()
{
	EXIT_MKSQUASHFS();
}


int mangle2(void *strm, char *d, char *s, int size,
	int block_size, int uncompressed, int data_block)
{
	int error, c_byte = 0;

	if(!uncompressed) {
		c_byte = compressor_compress(comp, strm, d, s, size, block_size,
			 &error);
		if(c_byte == -1)
			BAD_ERROR("mangle2:: %s compress failed with error "
				"code %d\n", comp->name, error);
	}

	if(c_byte == 0 || c_byte >= size) {
		memcpy(d, s, size);
		return size | (data_block ? SQUASHFS_COMPRESSED_BIT_BLOCK :
			SQUASHFS_COMPRESSED_BIT);
	}

	return c_byte;
}


int mangle(char *d, char *s, int size, int block_size,
	int uncompressed, int data_block)
{
	return mangle2(stream, d, s, size, block_size, uncompressed,
		data_block);
}


void *get_inode(int req_size)
{
	int data_space;
	unsigned short c_byte;

	while(cache_bytes >= SQUASHFS_METADATA_SIZE) {
		if((inode_size - inode_bytes) <
				((SQUASHFS_METADATA_SIZE << 1)) + 2) {
			void *it = realloc(inode_table, inode_size +
				(SQUASHFS_METADATA_SIZE << 1) + 2);
			if(it == NULL)
				MEM_ERROR();
			inode_table = it;
			inode_size += (SQUASHFS_METADATA_SIZE << 1) + 2;
		}

		c_byte = mangle(inode_table + inode_bytes + BLOCK_OFFSET,
			data_cache, SQUASHFS_METADATA_SIZE,
			SQUASHFS_METADATA_SIZE, noI, 0);
		TRACE("Inode block @ 0x%x, size %d\n", inode_bytes, c_byte);
		SQUASHFS_SWAP_SHORTS(&c_byte, inode_table + inode_bytes, 1);
		inode_bytes += SQUASHFS_COMPRESSED_SIZE(c_byte) + BLOCK_OFFSET;
		total_inode_bytes += SQUASHFS_METADATA_SIZE + BLOCK_OFFSET;
		memmove(data_cache, data_cache + SQUASHFS_METADATA_SIZE,
			cache_bytes - SQUASHFS_METADATA_SIZE);
		cache_bytes -= SQUASHFS_METADATA_SIZE;
	}

	data_space = (cache_size - cache_bytes);
	if(data_space < req_size) {
			int realloc_size = cache_size == 0 ?
				((req_size + SQUASHFS_METADATA_SIZE) &
				~(SQUASHFS_METADATA_SIZE - 1)) : req_size -
				data_space;

			void *dc = realloc(data_cache, cache_size +
				realloc_size);
			if(dc == NULL)
				MEM_ERROR();
			cache_size += realloc_size;
			data_cache = dc;
	}

	cache_bytes += req_size;

	return data_cache + cache_bytes - req_size;
}


int read_bytes(int fd, void *buff, int bytes)
{
	int res, count;

	for(count = 0; count < bytes; count += res) {
		res = read(fd, buff + count, bytes - count);
		if(res < 1) {
			if(res == 0)
				goto bytes_read;
			else if(errno != EINTR) {
				ERROR("Read failed because %s\n",
						strerror(errno));
				return -1;
			} else
				res = 0;
		}
	}

bytes_read:
	return count;
}


int read_fs_bytes(int fd, long long byte, int bytes, void *buff)
{
	off_t off = byte;
	int res = 1;

	TRACE("read_fs_bytes: reading from position 0x%llx, bytes %d\n",
		byte, bytes);

	pthread_cleanup_push((void *) pthread_mutex_unlock, &pos_mutex);
	pthread_mutex_lock(&pos_mutex);
	if(lseek(fd, off, SEEK_SET) == -1) {
		ERROR("read_fs_bytes: Lseek on destination failed because %s, "
			"offset=0x%llx\n", strerror(errno), off);
		res = 0;
	} else if(read_bytes(fd, buff, bytes) < bytes) {
		ERROR("Read on destination failed\n");
		res = 0;
	}

	pthread_cleanup_pop(1);
	return res;
}


int write_bytes(int fd, void *buff, int bytes)
{
	int res, count;

	for(count = 0; count < bytes; count += res) {
		res = write(fd, buff + count, bytes - count);
		if(res == -1) {
			if(errno != EINTR) {
				ERROR("Write failed because %s\n",
						strerror(errno));
				return -1;
			}
			res = 0;
		}
	}

	return 0;
}


void write_destination(int fd, long long byte, int bytes, void *buff)
{
	off_t off = byte;

	pthread_cleanup_push((void *) pthread_mutex_unlock, &pos_mutex);
	pthread_mutex_lock(&pos_mutex);

	if(lseek(fd, off, SEEK_SET) == -1) {
		ERROR("write_destination: Lseek on destination "
			"failed because %s, offset=0x%llx\n", strerror(errno),
			off);
		BAD_ERROR("Probably out of space on output %s\n",
			block_device ? "block device" : "filesystem");
	}

	if(write_bytes(fd, buff, bytes) == -1)
		BAD_ERROR("Failed to write to output %s\n",
			block_device ? "block device" : "filesystem");

	pthread_cleanup_pop(1);
}


long long write_inodes()
{
	unsigned short c_byte;
	int avail_bytes;
	char *datap = data_cache;
	long long start_bytes = bytes;

	while(cache_bytes) {
		if(inode_size - inode_bytes <
				((SQUASHFS_METADATA_SIZE << 1) + 2)) {
			void *it = realloc(inode_table, inode_size +
				((SQUASHFS_METADATA_SIZE << 1) + 2));
			if(it == NULL)
				MEM_ERROR();
			inode_size += (SQUASHFS_METADATA_SIZE << 1) + 2;
			inode_table = it;
		}
		avail_bytes = cache_bytes > SQUASHFS_METADATA_SIZE ?
			SQUASHFS_METADATA_SIZE : cache_bytes;
		c_byte = mangle(inode_table + inode_bytes + BLOCK_OFFSET, datap,
			avail_bytes, SQUASHFS_METADATA_SIZE, noI, 0);
		TRACE("Inode block @ 0x%x, size %d\n", inode_bytes, c_byte);
		SQUASHFS_SWAP_SHORTS(&c_byte, inode_table + inode_bytes, 1); 
		inode_bytes += SQUASHFS_COMPRESSED_SIZE(c_byte) + BLOCK_OFFSET;
		total_inode_bytes += avail_bytes + BLOCK_OFFSET;
		datap += avail_bytes;
		cache_bytes -= avail_bytes;
	}

	write_destination(fd, bytes, inode_bytes,  inode_table);
	bytes += inode_bytes;

	return start_bytes;
}


long long write_directories()
{
	unsigned short c_byte;
	int avail_bytes;
	char *directoryp = directory_data_cache;
	long long start_bytes = bytes;

	while(directory_cache_bytes) {
		if(directory_size - directory_bytes <
				((SQUASHFS_METADATA_SIZE << 1) + 2)) {
			void *dt = realloc(directory_table,
				directory_size + ((SQUASHFS_METADATA_SIZE << 1)
				+ 2));
			if(dt == NULL)
				MEM_ERROR();
			directory_size += (SQUASHFS_METADATA_SIZE << 1) + 2;
			directory_table = dt;
		}
		avail_bytes = directory_cache_bytes > SQUASHFS_METADATA_SIZE ?
			SQUASHFS_METADATA_SIZE : directory_cache_bytes;
		c_byte = mangle(directory_table + directory_bytes +
			BLOCK_OFFSET, directoryp, avail_bytes,
			SQUASHFS_METADATA_SIZE, noI, 0);
		TRACE("Directory block @ 0x%x, size %d\n", directory_bytes,
			c_byte);
		SQUASHFS_SWAP_SHORTS(&c_byte,
			directory_table + directory_bytes, 1);
		directory_bytes += SQUASHFS_COMPRESSED_SIZE(c_byte) +
			BLOCK_OFFSET;
		total_directory_bytes += avail_bytes + BLOCK_OFFSET;
		directoryp += avail_bytes;
		directory_cache_bytes -= avail_bytes;
	}
	write_destination(fd, bytes, directory_bytes, directory_table);
	bytes += directory_bytes;

	return start_bytes;
}


long long write_id_table()
{
	unsigned int id_bytes = SQUASHFS_ID_BYTES(id_count);
	unsigned int p[id_count];
	int i;

	TRACE("write_id_table: ids %d, id_bytes %d\n", id_count, id_bytes);
	for(i = 0; i < id_count; i++) {
		TRACE("write_id_table: id index %d, id %d", i, id_table[i]->id);
		SQUASHFS_SWAP_INTS(&id_table[i]->id, p + i, 1);
	}

	return generic_write_table(id_bytes, p, 0, NULL, noI);
}


struct id *get_id(unsigned int id)
{
	int hash = ID_HASH(id);
	struct id *entry = id_hash_table[hash];

	for(; entry; entry = entry->next)
		if(entry->id == id)
			break;

	return entry;
}


struct id *create_id(unsigned int id)
{
	int hash = ID_HASH(id);
	struct id *entry = malloc(sizeof(struct id));
	if(entry == NULL)
		MEM_ERROR();
	entry->id = id;
	entry->index = id_count ++;
	entry->flags = 0;
	entry->next = id_hash_table[hash];
	id_hash_table[hash] = entry;
	id_table[entry->index] = entry;
	return entry;
}


unsigned int get_uid(unsigned int uid)
{
	struct id *entry = get_id(uid);

	if(entry == NULL) {
		if(id_count == SQUASHFS_IDS)
			BAD_ERROR("Out of uids!\n");
		entry = create_id(uid);
	}

	if((entry->flags & ISA_UID) == 0) {
		entry->flags |= ISA_UID;
		uid_count ++;
	}

	return entry->index;
}


unsigned int get_guid(unsigned int guid)
{
	struct id *entry = get_id(guid);

	if(entry == NULL) {
		if(id_count == SQUASHFS_IDS)
			BAD_ERROR("Out of gids!\n");
		entry = create_id(guid);
	}

	if((entry->flags & ISA_GID) == 0) {
		entry->flags |= ISA_GID;
		guid_count ++;
	}

	return entry->index;
}


#define ALLOC_SIZE 128

char *_pathname(struct dir_ent *dir_ent, char *pathname, int *size)
{
	if(pathname == NULL) {
		pathname = malloc(ALLOC_SIZE);
		if(pathname == NULL)
			MEM_ERROR();
	}

	for(;;) {
		int res = snprintf(pathname, *size, "%s/%s", 
			dir_ent->our_dir->pathname,
			dir_ent->source_name ? : dir_ent->name);

		if(res < 0)
			BAD_ERROR("snprintf failed in pathname\n");
		else if(res >= *size) {
			/*
			 * pathname is too small to contain the result, so
			 * increase it and try again
			 */
			*size = (res + ALLOC_SIZE) & ~(ALLOC_SIZE - 1);
			pathname = realloc(pathname, *size);
			if(pathname == NULL)
				MEM_ERROR();
		} else
			break;
	}

	return pathname;
}


char *pathname(struct dir_ent *dir_ent)
{
	static char *pathname = NULL;
	static int size = ALLOC_SIZE;

	if (dir_ent->nonstandard_pathname)
		return dir_ent->nonstandard_pathname;

	return pathname = _pathname(dir_ent, pathname, &size);
}


char *pathname_reader(struct dir_ent *dir_ent)
{
	static char *pathname = NULL;
	static int size = ALLOC_SIZE;

	if (dir_ent->nonstandard_pathname)
		return dir_ent->nonstandard_pathname;

	return pathname = _pathname(dir_ent, pathname, &size);
}


char *subpathname(struct dir_ent *dir_ent)
{
	static char *subpath = NULL;
	static int size = ALLOC_SIZE;
	int res;

	if(subpath == NULL) {
		subpath = malloc(ALLOC_SIZE);
		if(subpath == NULL)
			MEM_ERROR();
	}

	for(;;) {
		if(dir_ent->our_dir->subpath[0] != '\0')
			res = snprintf(subpath, size, "%s/%s",
				dir_ent->our_dir->subpath, dir_ent->name);
		else
			res = snprintf(subpath, size, "/%s", dir_ent->name);

		if(res < 0)
			BAD_ERROR("snprintf failed in subpathname\n");
		else if(res >= size) {
			/*
			 * subpath is too small to contain the result, so
			 * increase it and try again
			 */
			size = (res + ALLOC_SIZE) & ~(ALLOC_SIZE - 1);
			subpath = realloc(subpath, size);
			if(subpath == NULL)
				MEM_ERROR();
		} else
			break;
	}

	return subpath;
}


static inline unsigned int get_inode_no(struct inode_info *inode)
{
	return inode->inode_number;
}


static inline unsigned int get_parent_no(struct dir_info *dir)
{
	return dir->depth ? get_inode_no(dir->dir_ent->inode) : inode_no;
}

	
int create_inode(squashfs_inode *i_no, struct dir_info *dir_info,
	struct dir_ent *dir_ent, int type, long long byte_size,
	long long start_block, unsigned int offset, unsigned int *block_list,
	struct fragment *fragment, struct directory *dir_in, long long sparse)
{
	struct stat *buf = &dir_ent->inode->buf;
	union squashfs_inode_header inode_header;
	struct squashfs_base_inode_header *base = &inode_header.base;
	void *inode;
	char *filename = pathname(dir_ent);
	int nlink = dir_ent->inode->nlink;
	int xattr = read_xattrs(dir_ent);

	switch(type) {
	case SQUASHFS_FILE_TYPE:
		if(dir_ent->inode->nlink > 1 ||
				byte_size >= (1LL << 32) ||
				start_block >= (1LL << 32) ||
				sparse || IS_XATTR(xattr))
			type = SQUASHFS_LREG_TYPE;
		break;
	case SQUASHFS_DIR_TYPE:
		if(dir_info->dir_is_ldir || IS_XATTR(xattr))
			type = SQUASHFS_LDIR_TYPE;
		break;
	case SQUASHFS_SYMLINK_TYPE:
		if(IS_XATTR(xattr))
			type = SQUASHFS_LSYMLINK_TYPE;
		break;
	case SQUASHFS_BLKDEV_TYPE:
		if(IS_XATTR(xattr))
			type = SQUASHFS_LBLKDEV_TYPE;
		break;
	case SQUASHFS_CHRDEV_TYPE:
		if(IS_XATTR(xattr))
			type = SQUASHFS_LCHRDEV_TYPE;
		break;
	case SQUASHFS_FIFO_TYPE:
		if(IS_XATTR(xattr))
			type = SQUASHFS_LFIFO_TYPE;
		break;
	case SQUASHFS_SOCKET_TYPE:
		if(IS_XATTR(xattr))
			type = SQUASHFS_LSOCKET_TYPE;
		break;
	}
			
	base->mode = SQUASHFS_MODE(buf->st_mode);
	base->uid = get_uid((unsigned int) global_uid == -1 ?
		buf->st_uid : global_uid);
	base->inode_type = type;
	base->guid = get_guid((unsigned int) global_gid == -1 ?
		buf->st_gid : global_gid);
	base->mtime = buf->st_mtime;
	base->inode_number = get_inode_no(dir_ent->inode);

	if(type == SQUASHFS_FILE_TYPE) {
		int i;
		struct squashfs_reg_inode_header *reg = &inode_header.reg;
		size_t off = offsetof(struct squashfs_reg_inode_header, block_list);

		inode = get_inode(sizeof(*reg) + offset * sizeof(unsigned int));
		reg->file_size = byte_size;
		reg->start_block = start_block;
		reg->fragment = fragment->index;
		reg->offset = fragment->offset;
		SQUASHFS_SWAP_REG_INODE_HEADER(reg, inode);
		SQUASHFS_SWAP_INTS(block_list, inode + off, offset);
		TRACE("File inode, file_size %lld, start_block 0x%llx, blocks "
			"%d, fragment %d, offset %d, size %d\n", byte_size,
			start_block, offset, fragment->index, fragment->offset,
			fragment->size);
		for(i = 0; i < offset; i++)
			TRACE("Block %d, size %d\n", i, block_list[i]);
	}
	else if(type == SQUASHFS_LREG_TYPE) {
		int i;
		struct squashfs_lreg_inode_header *reg = &inode_header.lreg;
		size_t off = offsetof(struct squashfs_lreg_inode_header, block_list);

		inode = get_inode(sizeof(*reg) + offset * sizeof(unsigned int));
		reg->nlink = nlink;
		reg->file_size = byte_size;
		reg->start_block = start_block;
		reg->fragment = fragment->index;
		reg->offset = fragment->offset;
		if(sparse && sparse >= byte_size)
			sparse = byte_size - 1;
		reg->sparse = sparse;
		reg->xattr = xattr;
		SQUASHFS_SWAP_LREG_INODE_HEADER(reg, inode);
		SQUASHFS_SWAP_INTS(block_list, inode + off, offset);
		TRACE("Long file inode, file_size %lld, start_block 0x%llx, "
			"blocks %d, fragment %d, offset %d, size %d, nlink %d"
			"\n", byte_size, start_block, offset, fragment->index,
			fragment->offset, fragment->size, nlink);
		for(i = 0; i < offset; i++)
			TRACE("Block %d, size %d\n", i, block_list[i]);
	}
	else if(type == SQUASHFS_LDIR_TYPE) {
		int i;
		unsigned char *p;
		struct squashfs_ldir_inode_header *dir = &inode_header.ldir;
		struct cached_dir_index *index = dir_in->index;
		unsigned int i_count = dir_in->i_count;
		unsigned int i_size = dir_in->i_size;

		if(byte_size >= 1 << 27)
			BAD_ERROR("directory greater than 2^27-1 bytes!\n");

		inode = get_inode(sizeof(*dir) + i_size);
		dir->inode_type = SQUASHFS_LDIR_TYPE;
		dir->nlink = dir_ent->dir->directory_count + 2;
		dir->file_size = byte_size;
		dir->offset = offset;
		dir->start_block = start_block;
		dir->i_count = i_count;
		dir->parent_inode = get_parent_no(dir_ent->our_dir);
		dir->xattr = xattr;

		SQUASHFS_SWAP_LDIR_INODE_HEADER(dir, inode);
		p = inode + offsetof(struct squashfs_ldir_inode_header, index);
		for(i = 0; i < i_count; i++) {
			SQUASHFS_SWAP_DIR_INDEX(&index[i].index, p);
			p += offsetof(struct squashfs_dir_index, name);
			memcpy(p, index[i].name, index[i].index.size + 1);
			p += index[i].index.size + 1;
		}
		TRACE("Long directory inode, file_size %lld, start_block "
			"0x%llx, offset 0x%x, nlink %d\n", byte_size,
			start_block, offset, dir_ent->dir->directory_count + 2);
	}
	else if(type == SQUASHFS_DIR_TYPE) {
		struct squashfs_dir_inode_header *dir = &inode_header.dir;

		inode = get_inode(sizeof(*dir));
		dir->nlink = dir_ent->dir->directory_count + 2;
		dir->file_size = byte_size;
		dir->offset = offset;
		dir->start_block = start_block;
		dir->parent_inode = get_parent_no(dir_ent->our_dir);
		SQUASHFS_SWAP_DIR_INODE_HEADER(dir, inode);
		TRACE("Directory inode, file_size %lld, start_block 0x%llx, "
			"offset 0x%x, nlink %d\n", byte_size, start_block,
			offset, dir_ent->dir->directory_count + 2);
	}
	else if(type == SQUASHFS_CHRDEV_TYPE || type == SQUASHFS_BLKDEV_TYPE) {
		struct squashfs_dev_inode_header *dev = &inode_header.dev;
		unsigned int major = major(buf->st_rdev);
		unsigned int minor = minor(buf->st_rdev);

		if(major > 0xfff) {
			ERROR("Major %d out of range in device node %s, "
				"truncating to %d\n", major, filename,
				major & 0xfff);
			major &= 0xfff;
		}
		if(minor > 0xfffff) {
			ERROR("Minor %d out of range in device node %s, "
				"truncating to %d\n", minor, filename,
				minor & 0xfffff);
			minor &= 0xfffff;
		}
		inode = get_inode(sizeof(*dev));
		dev->nlink = nlink;
		dev->rdev = (major << 8) | (minor & 0xff) |
				((minor & ~0xff) << 12);
		SQUASHFS_SWAP_DEV_INODE_HEADER(dev, inode);
		TRACE("Device inode, rdev 0x%x, nlink %d\n", dev->rdev, nlink);
	}
	else if(type == SQUASHFS_LCHRDEV_TYPE || type == SQUASHFS_LBLKDEV_TYPE) {
		struct squashfs_ldev_inode_header *dev = &inode_header.ldev;
		unsigned int major = major(buf->st_rdev);
		unsigned int minor = minor(buf->st_rdev);

		if(major > 0xfff) {
			ERROR("Major %d out of range in device node %s, "
				"truncating to %d\n", major, filename,
				major & 0xfff);
			major &= 0xfff;
		}
		if(minor > 0xfffff) {
			ERROR("Minor %d out of range in device node %s, "
				"truncating to %d\n", minor, filename,
				minor & 0xfffff);
			minor &= 0xfffff;
		}
		inode = get_inode(sizeof(*dev));
		dev->nlink = nlink;
		dev->rdev = (major << 8) | (minor & 0xff) |
				((minor & ~0xff) << 12);
		dev->xattr = xattr;
		SQUASHFS_SWAP_LDEV_INODE_HEADER(dev, inode);
		TRACE("Device inode, rdev 0x%x, nlink %d\n", dev->rdev, nlink);
	}
	else if(type == SQUASHFS_SYMLINK_TYPE) {
		struct squashfs_symlink_inode_header *symlink = &inode_header.symlink;
		int byte = strlen(dir_ent->inode->symlink);
		size_t off = offsetof(struct squashfs_symlink_inode_header, symlink);

		inode = get_inode(sizeof(*symlink) + byte);
		symlink->nlink = nlink;
		symlink->symlink_size = byte;
		SQUASHFS_SWAP_SYMLINK_INODE_HEADER(symlink, inode);
		strncpy(inode + off, dir_ent->inode->symlink, byte);
		TRACE("Symbolic link inode, symlink_size %d, nlink %d\n", byte,
			nlink);
	}
	else if(type == SQUASHFS_LSYMLINK_TYPE) {
		struct squashfs_symlink_inode_header *symlink = &inode_header.symlink;
		int byte = strlen(dir_ent->inode->symlink);
		size_t off = offsetof(struct squashfs_symlink_inode_header, symlink);

		inode = get_inode(sizeof(*symlink) + byte +
						sizeof(unsigned int));
		symlink->nlink = nlink;
		symlink->symlink_size = byte;
		SQUASHFS_SWAP_SYMLINK_INODE_HEADER(symlink, inode);
		strncpy(inode + off, dir_ent->inode->symlink, byte);
		SQUASHFS_SWAP_INTS(&xattr, inode + off + byte, 1);
		TRACE("Symbolic link inode, symlink_size %d, nlink %d\n", byte,
			nlink);
	}
	else if(type == SQUASHFS_FIFO_TYPE || type == SQUASHFS_SOCKET_TYPE) {
		struct squashfs_ipc_inode_header *ipc = &inode_header.ipc;

		inode = get_inode(sizeof(*ipc));
		ipc->nlink = nlink;
		SQUASHFS_SWAP_IPC_INODE_HEADER(ipc, inode);
		TRACE("ipc inode, type %s, nlink %d\n", type ==
			SQUASHFS_FIFO_TYPE ? "fifo" : "socket", nlink);
	}
	else if(type == SQUASHFS_LFIFO_TYPE || type == SQUASHFS_LSOCKET_TYPE) {
		struct squashfs_lipc_inode_header *ipc = &inode_header.lipc;

		inode = get_inode(sizeof(*ipc));
		ipc->nlink = nlink;
		ipc->xattr = xattr;
		SQUASHFS_SWAP_LIPC_INODE_HEADER(ipc, inode);
		TRACE("ipc inode, type %s, nlink %d\n", type ==
			SQUASHFS_FIFO_TYPE ? "fifo" : "socket", nlink);
	} else
		BAD_ERROR("Unrecognised inode %d in create_inode\n", type);

	*i_no = MKINODE(inode);
	inode_count ++;

	TRACE("Created inode 0x%llx, type %d, uid %d, guid %d\n", *i_no, type,
		base->uid, base->guid);

	return TRUE;
}


void add_dir(squashfs_inode inode, unsigned int inode_number, char *name,
	int type, struct directory *dir)
{
	unsigned char *buff;
	struct squashfs_dir_entry idir;
	unsigned int start_block = inode >> 16;
	unsigned int offset = inode & 0xffff;
	unsigned int size = strlen(name);
	size_t name_off = offsetof(struct squashfs_dir_entry, name);

	if(size > SQUASHFS_NAME_LEN) {
		size = SQUASHFS_NAME_LEN;
		ERROR("Filename is greater than %d characters, truncating! ..."
			"\n", SQUASHFS_NAME_LEN);
	}

	if(dir->p + sizeof(struct squashfs_dir_entry) + size +
			sizeof(struct squashfs_dir_header)
			>= dir->buff + dir->size) {
		buff = realloc(dir->buff, dir->size += SQUASHFS_METADATA_SIZE);
		if(buff == NULL)
			MEM_ERROR();

		dir->p = (dir->p - dir->buff) + buff;
		if(dir->entry_count_p) 
			dir->entry_count_p = (dir->entry_count_p - dir->buff +
			buff);
		dir->index_count_p = dir->index_count_p - dir->buff + buff;
		dir->buff = buff;
	}

	if(dir->entry_count == 256 || start_block != dir->start_block ||
			((dir->entry_count_p != NULL) &&
			((dir->p + sizeof(struct squashfs_dir_entry) + size -
			dir->index_count_p) > SQUASHFS_METADATA_SIZE)) ||
			((long long) inode_number - dir->inode_number) > 32767
			|| ((long long) inode_number - dir->inode_number)
			< -32768) {
		if(dir->entry_count_p) {
			struct squashfs_dir_header dir_header;

			if((dir->p + sizeof(struct squashfs_dir_entry) + size -
					dir->index_count_p) >
					SQUASHFS_METADATA_SIZE) {
				if(dir->i_count % I_COUNT_SIZE == 0) {
					dir->index = realloc(dir->index,
						(dir->i_count + I_COUNT_SIZE) *
						sizeof(struct cached_dir_index));
					if(dir->index == NULL)
						MEM_ERROR();
				}
				dir->index[dir->i_count].index.index =
					dir->p - dir->buff;
				dir->index[dir->i_count].index.size = size - 1;
				dir->index[dir->i_count++].name = name;
				dir->i_size += sizeof(struct squashfs_dir_index)
					+ size;
				dir->index_count_p = dir->p;
			}

			dir_header.count = dir->entry_count - 1;
			dir_header.start_block = dir->start_block;
			dir_header.inode_number = dir->inode_number;
			SQUASHFS_SWAP_DIR_HEADER(&dir_header,
				dir->entry_count_p);

		}


		dir->entry_count_p = dir->p;
		dir->start_block = start_block;
		dir->entry_count = 0;
		dir->inode_number = inode_number;
		dir->p += sizeof(struct squashfs_dir_header);
	}

	idir.offset = offset;
	idir.type = type;
	idir.size = size - 1;
	idir.inode_number = ((long long) inode_number - dir->inode_number);
	SQUASHFS_SWAP_DIR_ENTRY(&idir, dir->p);
	strncpy((char *) dir->p + name_off, name, size);
	dir->p += sizeof(struct squashfs_dir_entry) + size;
	dir->entry_count ++;
}


void write_dir(squashfs_inode *inode, struct dir_info *dir_info,
	struct directory *dir)
{
	unsigned int dir_size = dir->p - dir->buff;
	int data_space = directory_cache_size - directory_cache_bytes;
	unsigned int directory_block, directory_offset, i_count, index;
	unsigned short c_byte;

	if(data_space < dir_size) {
		int realloc_size = directory_cache_size == 0 ?
			((dir_size + SQUASHFS_METADATA_SIZE) &
			~(SQUASHFS_METADATA_SIZE - 1)) : dir_size - data_space;

		void *dc = realloc(directory_data_cache,
			directory_cache_size + realloc_size);
		if(dc == NULL)
			MEM_ERROR();
		directory_cache_size += realloc_size;
		directory_data_cache = dc;
	}

	if(dir_size) {
		struct squashfs_dir_header dir_header;

		dir_header.count = dir->entry_count - 1;
		dir_header.start_block = dir->start_block;
		dir_header.inode_number = dir->inode_number;
		SQUASHFS_SWAP_DIR_HEADER(&dir_header, dir->entry_count_p);
		memcpy(directory_data_cache + directory_cache_bytes, dir->buff,
			dir_size);
	}
	directory_offset = directory_cache_bytes;
	directory_block = directory_bytes;
	directory_cache_bytes += dir_size;
	i_count = 0;
	index = SQUASHFS_METADATA_SIZE - directory_offset;

	while(1) {
		while(i_count < dir->i_count &&
				dir->index[i_count].index.index < index)
			dir->index[i_count++].index.start_block =
				directory_bytes;
		index += SQUASHFS_METADATA_SIZE;

		if(directory_cache_bytes < SQUASHFS_METADATA_SIZE)
			break;

		if((directory_size - directory_bytes) <
					((SQUASHFS_METADATA_SIZE << 1) + 2)) {
			void *dt = realloc(directory_table,
				directory_size + (SQUASHFS_METADATA_SIZE << 1)
				+ 2);
			if(dt == NULL)
				MEM_ERROR();
			directory_size += SQUASHFS_METADATA_SIZE << 1;
			directory_table = dt;
		}

		c_byte = mangle(directory_table + directory_bytes +
				BLOCK_OFFSET, directory_data_cache,
				SQUASHFS_METADATA_SIZE, SQUASHFS_METADATA_SIZE,
				noI, 0);
		TRACE("Directory block @ 0x%x, size %d\n", directory_bytes,
			c_byte);
		SQUASHFS_SWAP_SHORTS(&c_byte,
			directory_table + directory_bytes, 1);
		directory_bytes += SQUASHFS_COMPRESSED_SIZE(c_byte) +
			BLOCK_OFFSET;
		total_directory_bytes += SQUASHFS_METADATA_SIZE + BLOCK_OFFSET;
		memmove(directory_data_cache, directory_data_cache +
			SQUASHFS_METADATA_SIZE, directory_cache_bytes -
			SQUASHFS_METADATA_SIZE);
		directory_cache_bytes -= SQUASHFS_METADATA_SIZE;
	}

	create_inode(inode, dir_info, dir_info->dir_ent, SQUASHFS_DIR_TYPE,
		dir_size + 3, directory_block, directory_offset, NULL, NULL,
		dir, 0);

#ifdef SQUASHFS_TRACE
	{
		unsigned char *dirp;
		int count;

		TRACE("Directory contents of inode 0x%llx\n", *inode);
		dirp = dir->buff;
		while(dirp < dir->p) {
			char buffer[SQUASHFS_NAME_LEN + 1];
			struct squashfs_dir_entry idir, *idirp;
			struct squashfs_dir_header dirh;
			SQUASHFS_SWAP_DIR_HEADER((struct squashfs_dir_header *) dirp,
				&dirh);
			count = dirh.count + 1;
			dirp += sizeof(struct squashfs_dir_header);

			TRACE("\tStart block 0x%x, count %d\n",
				dirh.start_block, count);

			while(count--) {
				idirp = (struct squashfs_dir_entry *) dirp;
				SQUASHFS_SWAP_DIR_ENTRY(idirp, &idir);
				strncpy(buffer, idirp->name, idir.size + 1);
				buffer[idir.size + 1] = '\0';
				TRACE("\t\tname %s, inode offset 0x%x, type "
					"%d\n", buffer, idir.offset, idir.type);
				dirp += sizeof(struct squashfs_dir_entry) + idir.size +
					1;
			}
		}
	}
#endif
	dir_count ++;
}


static struct file_buffer *get_fragment(struct fragment *fragment)
{
	struct squashfs_fragment_entry *disk_fragment;
	struct file_buffer *buffer, *compressed_buffer;
	long long start_block;
	int res, size, index = fragment->index;
	char locked;

	/*
	 * Lookup fragment block in cache.
	 * If the fragment block doesn't exist, then get the compressed version
	 * from the writer cache or off disk, and decompress it.
	 *
	 * This routine has two things which complicate the code:
	 *
	 *	1. Multiple threads can simultaneously lookup/create the
	 *	   same buffer.  This means a buffer needs to be "locked"
	 *	   when it is being filled in, to prevent other threads from
	 *	   using it when it is not ready.  This is because we now do
	 *	   fragment duplicate checking in parallel.
	 *	2. We have two caches which need to be checked for the
	 *	   presence of fragment blocks: the normal fragment cache
	 *	   and a "reserve" cache.  The reserve cache is used to
	 *	   prevent an unnecessary pipeline stall when the fragment cache
	 *	   is full of fragments waiting to be compressed.
	 */

	if(fragment->index == SQUASHFS_INVALID_FRAG)
		return NULL;

	pthread_cleanup_push((void *) pthread_mutex_unlock, &dup_mutex);
	pthread_mutex_lock(&dup_mutex);

again:
	buffer = cache_lookup_nowait(fragment_buffer, index, &locked);
	if(buffer) {
		pthread_mutex_unlock(&dup_mutex);
		if(locked)
			/* got a buffer being filled in.  Wait for it */
			cache_wait_unlock(buffer);
		goto finished;
	}

	/* not in fragment cache, is it in the reserve cache? */
	buffer = cache_lookup_nowait(reserve_cache, index, &locked);
	if(buffer) {
		pthread_mutex_unlock(&dup_mutex);
		if(locked)
			/* got a buffer being filled in.  Wait for it */
			cache_wait_unlock(buffer);
		goto finished;
	}

	/* in neither cache, try to get it from the fragment cache */
	buffer = cache_get_nowait(fragment_buffer, index);
	if(!buffer) {
		/*
		 * no room, get it from the reserve cache, this is
		 * dimensioned so it will always have space (no more than
		 * processors + 1 can have an outstanding reserve buffer)
		 */
		buffer = cache_get_nowait(reserve_cache, index);
		if(!buffer) {
			/* failsafe */
			ERROR("no space in reserve cache\n");
			goto again;
		}
	}

	pthread_mutex_unlock(&dup_mutex);

	compressed_buffer = cache_lookup(fwriter_buffer, index);

	pthread_cleanup_push((void *) pthread_mutex_unlock, &fragment_mutex);
	pthread_mutex_lock(&fragment_mutex);
	disk_fragment = &fragment_table[index];
	size = SQUASHFS_COMPRESSED_SIZE_BLOCK(disk_fragment->size);
	start_block = disk_fragment->start_block;
	pthread_cleanup_pop(1);

	if(SQUASHFS_COMPRESSED_BLOCK(disk_fragment->size)) {
		int error;
		char *data;

		if(compressed_buffer)
			data = compressed_buffer->data;
		else {
			data = read_from_disk(start_block, size);
			if(data == NULL) {
				ERROR("Failed to read fragment from output"
					" filesystem\n");
				BAD_ERROR("Output filesystem corrupted?\n");
			}
		}

		res = compressor_uncompress(comp, buffer->data, data, size,
			block_size, &error);
		if(res == -1)
			BAD_ERROR("%s uncompress failed with error code %d\n",
				comp->name, error);
	} else if(compressed_buffer)
		memcpy(buffer->data, compressed_buffer->data, size);
	else {
		res = read_fs_bytes(fd, start_block, size, buffer->data);
		if(res == 0) {
			ERROR("Failed to read fragment from output "
				"filesystem\n");
			BAD_ERROR("Output filesystem corrupted?\n");
		}
	}

	cache_unlock(buffer);
	cache_block_put(compressed_buffer);

finished:
	pthread_cleanup_pop(0);

	return buffer;
}


unsigned short get_fragment_checksum(struct file_info *file)
{
	struct file_buffer *frag_buffer;
	struct append_file *append;
	int res, index = file->fragment->index;
	unsigned short checksum;

	if(index == SQUASHFS_INVALID_FRAG)
		return 0;

	pthread_cleanup_push((void *) pthread_mutex_unlock, &dup_mutex);
	pthread_mutex_lock(&dup_mutex);
	res = file->have_frag_checksum;
	checksum = file->fragment_checksum;
	pthread_cleanup_pop(1);

	if(res)
		return checksum;

	frag_buffer = get_fragment(file->fragment);

	pthread_cleanup_push((void *) pthread_mutex_unlock, &dup_mutex);

	for(append = file_mapping[index]; append; append = append->next) {
		int offset = append->file->fragment->offset;
		int size = append->file->fragment->size;
		unsigned short cksum =
			get_checksum_mem(frag_buffer->data + offset, size);

		if(file == append->file)
			checksum = cksum;

		pthread_mutex_lock(&dup_mutex);
		append->file->fragment_checksum = cksum;
		append->file->have_frag_checksum = TRUE;
		pthread_mutex_unlock(&dup_mutex);
	}

	cache_block_put(frag_buffer);
	pthread_cleanup_pop(0);

	return checksum;
}


void lock_fragments()
{
	pthread_cleanup_push((void *) pthread_mutex_unlock, &fragment_mutex);
	pthread_mutex_lock(&fragment_mutex);
	fragments_locked = TRUE;
	pthread_cleanup_pop(1);
}


void unlock_fragments()
{
	int frg, size;
	struct file_buffer *write_buffer;

	pthread_cleanup_push((void *) pthread_mutex_unlock, &fragment_mutex);
	pthread_mutex_lock(&fragment_mutex);

	/*
	 * Note queue_empty() is inherently racy with respect to concurrent
	 * queue get and pushes.  We avoid this because we're holding the
	 * fragment_mutex which ensures no other threads can be using the
	 * queue at this time.
	 */
	while(!queue_empty(locked_fragment)) {
		write_buffer = queue_get(locked_fragment);
		frg = write_buffer->block;	
		size = SQUASHFS_COMPRESSED_SIZE_BLOCK(fragment_table[frg].size);
		fragment_table[frg].start_block = bytes;
		write_buffer->block = bytes;
		bytes += size;
		fragments_outstanding --;
		queue_put(to_writer, write_buffer);
		TRACE("fragment_locked writing fragment %d, compressed size %d"
			"\n", frg, size);
	}
	fragments_locked = FALSE;
	pthread_cleanup_pop(1);
}

/* Called with the fragment_mutex locked */
void add_pending_fragment(struct file_buffer *write_buffer, int c_byte,
	int fragment)
{
	fragment_table[fragment].size = c_byte;
	write_buffer->block = fragment;

	queue_put(locked_fragment, write_buffer);
}


void write_fragment(struct file_buffer *fragment)
{
	if(fragment == NULL)
		return;

	pthread_cleanup_push((void *) pthread_mutex_unlock, &fragment_mutex);
	pthread_mutex_lock(&fragment_mutex);
	fragment_table[fragment->block].unused = 0;
	fragments_outstanding ++;
	queue_put(to_frag, fragment);
	pthread_cleanup_pop(1);
}


struct file_buffer *allocate_fragment()
{
	struct file_buffer *fragment = cache_get(fragment_buffer, fragments);

	pthread_cleanup_push((void *) pthread_mutex_unlock, &fragment_mutex);
	pthread_mutex_lock(&fragment_mutex);

	if(fragments % FRAG_SIZE == 0) {
		void *ft = realloc(fragment_table, (fragments +
			FRAG_SIZE) * sizeof(struct squashfs_fragment_entry));
		if(ft == NULL)
			MEM_ERROR();
		fragment_table = ft;
	}

	fragment->size = 0;
	fragment->block = fragments ++;

	pthread_cleanup_pop(1);

	return fragment;
}


static struct fragment empty_fragment = {SQUASHFS_INVALID_FRAG, 0, 0};


void free_fragment(struct fragment *fragment)
{
	if(fragment != &empty_fragment)
		free(fragment);
}


struct fragment *get_and_fill_fragment(struct file_buffer *file_buffer,
	struct dir_ent *dir_ent)
{
	struct fragment *ffrg;
	struct file_buffer **fragment;

	if(file_buffer == NULL || file_buffer->size == 0)
		return &empty_fragment;

	fragment = eval_frag_actions(root_dir, dir_ent);

	if((*fragment) && (*fragment)->size + file_buffer->size > block_size) {
		write_fragment(*fragment);
		*fragment = NULL;
	}

	ffrg = malloc(sizeof(struct fragment));
	if(ffrg == NULL)
		MEM_ERROR();

	if(*fragment == NULL)
		*fragment = allocate_fragment();

	ffrg->index = (*fragment)->block;
	ffrg->offset = (*fragment)->size;
	ffrg->size = file_buffer->size;
	memcpy((*fragment)->data + (*fragment)->size, file_buffer->data,
		file_buffer->size);
	(*fragment)->size += file_buffer->size;

	return ffrg;
}


long long generic_write_table(int length, void *buffer, int length2,
	void *buffer2, int uncompressed)
{
	int meta_blocks = (length + SQUASHFS_METADATA_SIZE - 1) /
		SQUASHFS_METADATA_SIZE;
	long long *list, start_bytes;
	int compressed_size, i, list_size = meta_blocks * sizeof(long long);
	unsigned short c_byte;
	char cbuffer[(SQUASHFS_METADATA_SIZE << 2) + 2];
	
#ifdef SQUASHFS_TRACE
	long long obytes = bytes;
	int olength = length;
#endif

	list = malloc(list_size);
	if(list == NULL)
		MEM_ERROR();

	for(i = 0; i < meta_blocks; i++) {
		int avail_bytes = length > SQUASHFS_METADATA_SIZE ?
			SQUASHFS_METADATA_SIZE : length;
		c_byte = mangle(cbuffer + BLOCK_OFFSET, buffer + i *
			SQUASHFS_METADATA_SIZE , avail_bytes,
			SQUASHFS_METADATA_SIZE, uncompressed, 0);
		SQUASHFS_SWAP_SHORTS(&c_byte, cbuffer, 1);
		list[i] = bytes;
		compressed_size = SQUASHFS_COMPRESSED_SIZE(c_byte) +
			BLOCK_OFFSET;
		TRACE("block %d @ 0x%llx, compressed size %d\n", i, bytes,
			compressed_size);
		write_destination(fd, bytes, compressed_size, cbuffer);
		bytes += compressed_size;
		total_bytes += avail_bytes;
		length -= avail_bytes;
	}

	start_bytes = bytes;
	if(length2) {
		write_destination(fd, bytes, length2, buffer2);
		bytes += length2;
		total_bytes += length2;
	}
		
	SQUASHFS_INSWAP_LONG_LONGS(list, meta_blocks);
	write_destination(fd, bytes, list_size, list);
	bytes += list_size;
	total_bytes += list_size;

	TRACE("generic_write_table: total uncompressed %d compressed %lld\n",
		olength, bytes - obytes);

	free(list);

	return start_bytes;
}


long long write_fragment_table()
{
	unsigned int frag_bytes = SQUASHFS_FRAGMENT_BYTES(fragments);
	int i;

	TRACE("write_fragment_table: fragments %d, frag_bytes %d\n", fragments,
		frag_bytes);
	for(i = 0; i < fragments; i++) {
		TRACE("write_fragment_table: fragment %d, start_block 0x%llx, "
			"size %d\n", i, fragment_table[i].start_block,
			fragment_table[i].size);
		SQUASHFS_INSWAP_FRAGMENT_ENTRY(&fragment_table[i]);
	}

	return generic_write_table(frag_bytes, fragment_table, 0, NULL, noF);
}


char read_from_file_buffer[SQUASHFS_FILE_MAX_SIZE];
static char *read_from_disk(long long start, unsigned int avail_bytes)
{
	int res;

	res = read_fs_bytes(fd, start, avail_bytes, read_from_file_buffer);
	if(res == 0)
		return NULL;

	return read_from_file_buffer;
}


char read_from_file_buffer2[SQUASHFS_FILE_MAX_SIZE];
char *read_from_disk2(long long start, unsigned int avail_bytes)
{
	int res;

	res = read_fs_bytes(fd, start, avail_bytes, read_from_file_buffer2);
	if(res == 0)
		return NULL;

	return read_from_file_buffer2;
}


/*
 * Compute 16 bit BSD checksum over the data
 */
unsigned short get_checksum(char *buff, int bytes, unsigned short chksum)
{
	unsigned char *b = (unsigned char *) buff;

	while(bytes --) {
		chksum = (chksum & 1) ? (chksum >> 1) | 0x8000 : chksum >> 1;
		chksum += *b++;
	}

	return chksum;
}


unsigned short get_checksum_disk(long long start, long long l,
	unsigned int *blocks)
{
	unsigned short chksum = 0;
	unsigned int bytes;
	struct file_buffer *write_buffer;
	int i;

	for(i = 0; l; i++)  {
		bytes = SQUASHFS_COMPRESSED_SIZE_BLOCK(blocks[i]);
		if(bytes == 0) /* sparse block */
			continue;
		write_buffer = cache_lookup(bwriter_buffer, start);
		if(write_buffer) {
			chksum = get_checksum(write_buffer->data, bytes,
				chksum);
			cache_block_put(write_buffer);
		} else {
			void *data = read_from_disk(start, bytes);
			if(data == NULL) {	
				ERROR("Failed to checksum data from output"
					" filesystem\n");
				BAD_ERROR("Output filesystem corrupted?\n");
			}

			chksum = get_checksum(data, bytes, chksum);
		}

		l -= bytes;
		start += bytes;
	}

	return chksum;
}


unsigned short get_checksum_mem(char *buff, int bytes)
{
	return get_checksum(buff, bytes, 0);
}


unsigned short get_checksum_mem_buffer(struct file_buffer *file_buffer)
{
	if(file_buffer == NULL)
		return 0;
	else
		return get_checksum(file_buffer->data, file_buffer->size, 0);
}


#define DUP_HASH(a) (a & 0xffff)
void add_file(long long start, long long file_size, long long file_bytes,
	unsigned int *block_listp, int blocks, unsigned int fragment,
	int offset, int bytes)
{
	struct fragment *frg;
	unsigned int *block_list = block_listp;
	struct file_info *dupl_ptr = dupl[DUP_HASH(file_size)];
	struct append_file *append_file;
	struct file_info *file;

	if(!duplicate_checking || file_size == 0)
		return;

	for(; dupl_ptr; dupl_ptr = dupl_ptr->next) {
		if(file_size != dupl_ptr->file_size)
			continue;
		if(blocks != 0 && start != dupl_ptr->start)
			continue;
		if(fragment != dupl_ptr->fragment->index)
			continue;
		if(fragment != SQUASHFS_INVALID_FRAG && (offset !=
				dupl_ptr->fragment->offset || bytes !=
				dupl_ptr->fragment->size))
			continue;
		return;
	}

	frg = malloc(sizeof(struct fragment));
	if(frg == NULL)
		MEM_ERROR();

	frg->index = fragment;
	frg->offset = offset;
	frg->size = bytes;

	file = add_non_dup(file_size, file_bytes, block_list, start, frg, 0, 0,
		FALSE, FALSE);

	if(fragment == SQUASHFS_INVALID_FRAG)
		return;

	append_file = malloc(sizeof(struct append_file));
	if(append_file == NULL)
		MEM_ERROR();

	append_file->file = file;
	append_file->next = file_mapping[fragment];
	file_mapping[fragment] = append_file;
}


int pre_duplicate(long long file_size)
{
	struct file_info *dupl_ptr = dupl[DUP_HASH(file_size)];

	for(; dupl_ptr; dupl_ptr = dupl_ptr->next)
		if(dupl_ptr->file_size == file_size)
			return TRUE;

	return FALSE;
}


struct file_info *add_non_dup(long long file_size, long long bytes,
	unsigned int *block_list, long long start, struct fragment *fragment,
	unsigned short checksum, unsigned short fragment_checksum,
	int checksum_flag, int checksum_frag_flag)
{
	struct file_info *dupl_ptr = malloc(sizeof(struct file_info));

	if(dupl_ptr == NULL)
		MEM_ERROR();

	dupl_ptr->file_size = file_size;
	dupl_ptr->bytes = bytes;
	dupl_ptr->block_list = block_list;
	dupl_ptr->start = start;
	dupl_ptr->fragment = fragment;
	dupl_ptr->checksum = checksum;
	dupl_ptr->fragment_checksum = fragment_checksum;
	dupl_ptr->have_frag_checksum = checksum_frag_flag;
	dupl_ptr->have_checksum = checksum_flag;

	pthread_cleanup_push((void *) pthread_mutex_unlock, &dup_mutex);
        pthread_mutex_lock(&dup_mutex);
	dupl_ptr->next = dupl[DUP_HASH(file_size)];
	dupl[DUP_HASH(file_size)] = dupl_ptr;
	dup_files ++;
	pthread_cleanup_pop(1);

	return dupl_ptr;
}


struct fragment *frag_duplicate(struct file_buffer *file_buffer, char *dont_put)
{
	struct file_info *dupl_ptr;
	struct file_buffer *buffer;
	struct file_info *dupl_start = file_buffer->dupl_start;
	long long file_size = file_buffer->file_size;
	unsigned short checksum = file_buffer->checksum;
	int res;

	if(file_buffer->duplicate) {
		TRACE("Found duplicate file, fragment %d, size %d, offset %d, "
			"checksum 0x%x\n", dupl_start->fragment->index,
			file_size, dupl_start->fragment->offset, checksum);
		*dont_put = TRUE;
		return dupl_start->fragment;
	} else {
		*dont_put = FALSE;
		dupl_ptr = dupl[DUP_HASH(file_size)];
	}

	for(; dupl_ptr && dupl_ptr != dupl_start; dupl_ptr = dupl_ptr->next) {
		if(file_size == dupl_ptr->file_size && file_size ==
				dupl_ptr->fragment->size) {
			if(get_fragment_checksum(dupl_ptr) == checksum) {
				buffer = get_fragment(dupl_ptr->fragment);
				res = memcmp(file_buffer->data, buffer->data +
					dupl_ptr->fragment->offset, file_size);
				cache_block_put(buffer);
				if(res == 0)
					break;
			}
		}
	}

	if(!dupl_ptr || dupl_ptr == dupl_start)
		return NULL;

	TRACE("Found duplicate file, fragment %d, size %d, offset %d, "
		"checksum 0x%x\n", dupl_ptr->fragment->index, file_size,
		dupl_ptr->fragment->offset, checksum);

	return dupl_ptr->fragment;
}


struct file_info *duplicate(long long file_size, long long bytes,
	unsigned int **block_list, long long *start, struct fragment **fragment,
	struct file_buffer *file_buffer, int blocks, unsigned short checksum,
	int checksum_flag)
{
	struct file_info *dupl_ptr = dupl[DUP_HASH(file_size)];
	int frag_bytes = file_buffer ? file_buffer->size : 0;
	unsigned short fragment_checksum = file_buffer ?
		file_buffer->checksum : 0;

	for(; dupl_ptr; dupl_ptr = dupl_ptr->next)
		if(file_size == dupl_ptr->file_size && bytes == dupl_ptr->bytes
				 && frag_bytes == dupl_ptr->fragment->size) {
			long long target_start, dup_start = dupl_ptr->start;
			int block;

			if(memcmp(*block_list, dupl_ptr->block_list, blocks *
					sizeof(unsigned int)) != 0)
				continue;

			if(checksum_flag == FALSE) {
				checksum = get_checksum_disk(*start, bytes,
					*block_list);
				checksum_flag = TRUE;
			}

			if(!dupl_ptr->have_checksum) {
				dupl_ptr->checksum =
					get_checksum_disk(dupl_ptr->start,
					dupl_ptr->bytes, dupl_ptr->block_list);
				dupl_ptr->have_checksum = TRUE;
			}

			if(checksum != dupl_ptr->checksum ||
					fragment_checksum !=
					get_fragment_checksum(dupl_ptr))
				continue;

			target_start = *start;
			for(block = 0; block < blocks; block ++) {
				int size = SQUASHFS_COMPRESSED_SIZE_BLOCK
					((*block_list)[block]);
				struct file_buffer *target_buffer = NULL;
				struct file_buffer *dup_buffer = NULL;
				char *target_data, *dup_data;
				int res;

				if(size == 0)
					continue;
				target_buffer = cache_lookup(bwriter_buffer,
					target_start);
				if(target_buffer)
					target_data = target_buffer->data;
				else {
					target_data =
						read_from_disk(target_start,
						size);
					if(target_data == NULL) {
						ERROR("Failed to read data from"
							" output filesystem\n");
						BAD_ERROR("Output filesystem"
							" corrupted?\n");
					}
				}

				dup_buffer = cache_lookup(bwriter_buffer,
					dup_start);
				if(dup_buffer)
					dup_data = dup_buffer->data;
				else {
					dup_data = read_from_disk2(dup_start,
						size);
					if(dup_data == NULL) {
						ERROR("Failed to read data from"
							" output filesystem\n");
						BAD_ERROR("Output filesystem"
							" corrupted?\n");
					}
				}

				res = memcmp(target_data, dup_data, size);
				cache_block_put(target_buffer);
				cache_block_put(dup_buffer);
				if(res != 0)
					break;
				target_start += size;
				dup_start += size;
			}
			if(block == blocks) {
				struct file_buffer *frag_buffer =
					get_fragment(dupl_ptr->fragment);

				if(frag_bytes == 0 ||
						memcmp(file_buffer->data,
						frag_buffer->data +
						dupl_ptr->fragment->offset,
						frag_bytes) == 0) {
					TRACE("Found duplicate file, start "
						"0x%llx, size %lld, checksum "
						"0x%x, fragment %d, size %d, "
						"offset %d, checksum 0x%x\n",
						dupl_ptr->start,
						dupl_ptr->bytes,
						dupl_ptr->checksum,
						dupl_ptr->fragment->index,
						frag_bytes,
						dupl_ptr->fragment->offset,
						fragment_checksum);
					*block_list = dupl_ptr->block_list;
					*start = dupl_ptr->start;
					*fragment = dupl_ptr->fragment;
					cache_block_put(frag_buffer);
					return 0;
				}
				cache_block_put(frag_buffer);
			}
		}


	return add_non_dup(file_size, bytes, *block_list, *start, *fragment,
		checksum, fragment_checksum, checksum_flag, TRUE);
}


static inline int is_fragment(struct inode_info *inode)
{
	off_t file_size = inode->buf.st_size;

	/*
	 * If this block is to be compressed differently to the
	 * fragment compression then it cannot be a fragment
	 */
	if(inode->noF != noF)
		return FALSE;

	return !inode->no_fragments && file_size && (file_size < block_size ||
		(inode->always_use_fragments && file_size & (block_size - 1)));
}


void put_file_buffer(struct file_buffer *file_buffer)
{
	/*
	 * Decide where to send the file buffer:
	 * - compressible non-fragment blocks go to the deflate threads,
	 * - fragments go to the process fragment threads,
	 * - all others go directly to the main thread
	 */
	if(file_buffer->error) {
		file_buffer->fragment = 0;
		seq_queue_put(to_main, file_buffer);
	} else if (file_buffer->file_size == 0)
		seq_queue_put(to_main, file_buffer);
 	else if(file_buffer->fragment)
		queue_put(to_process_frag, file_buffer);
	else
		queue_put(to_deflate, file_buffer);
}


static int seq = 0;
void reader_read_process(struct dir_ent *dir_ent)
{
	long long bytes = 0;
	struct inode_info *inode = dir_ent->inode;
	struct file_buffer *prev_buffer = NULL, *file_buffer;
	int status, byte, res, child;
	int file = pseudo_exec_file(get_pseudo_file(inode->pseudo_id), &child);

	if(!file) {
		file_buffer = cache_get_nohash(reader_buffer);
		file_buffer->sequence = seq ++;
		goto read_err;
	}

	while(1) {
		file_buffer = cache_get_nohash(reader_buffer);
		file_buffer->sequence = seq ++;
		file_buffer->noD = inode->noD;

		byte = read_bytes(file, file_buffer->data, block_size);
		if(byte == -1)
			goto read_err2;

		file_buffer->size = byte;
		file_buffer->file_size = -1;
		file_buffer->error = FALSE;
		file_buffer->fragment = FALSE;
		bytes += byte;

		if(byte == 0)
			break;

		/*
		 * Update progress bar size.  This is done
		 * on every block rather than waiting for all blocks to be
		 * read incase write_file_process() is running in parallel
		 * with this.  Otherwise the current progress bar position
		 * may get ahead of the progress bar size.
		 */ 
		progress_bar_size(1);

		if(prev_buffer)
			put_file_buffer(prev_buffer);
		prev_buffer = file_buffer;
	}

	/*
 	 * Update inode file size now that the size of the dynamic pseudo file
	 * is known.  This is needed for the -info option.
	 */
	inode->buf.st_size = bytes;

	res = waitpid(child, &status, 0);
	close(file);

	if(res == -1 || !WIFEXITED(status) || WEXITSTATUS(status) != 0)
		goto read_err;

	if(prev_buffer == NULL)
		prev_buffer = file_buffer;
	else {
		cache_block_put(file_buffer);
		seq --;
	}
	prev_buffer->file_size = bytes;
	prev_buffer->fragment = is_fragment(inode);
	put_file_buffer(prev_buffer);

	return;

read_err2:
	close(file);
read_err:
	if(prev_buffer) {
		cache_block_put(file_buffer);
		seq --;
		file_buffer = prev_buffer;
	}
	file_buffer->error = TRUE;
	put_file_buffer(file_buffer);
}


void reader_read_file(struct dir_ent *dir_ent)
{
	struct stat *buf = &dir_ent->inode->buf, buf2;
	struct file_buffer *file_buffer;
	int blocks, file, res;
	long long bytes, read_size;
	struct inode_info *inode = dir_ent->inode;

	if(inode->read)
		return;

	inode->read = TRUE;
again:
	bytes = 0;
	read_size = buf->st_size;
	blocks = (read_size + block_size - 1) >> block_log;

	file = open(pathname_reader(dir_ent), O_RDONLY);
	if(file == -1) {
		file_buffer = cache_get_nohash(reader_buffer);
		file_buffer->sequence = seq ++;
		goto read_err2;
	}

	do {
		file_buffer = cache_get_nohash(reader_buffer);
		file_buffer->file_size = read_size;
		file_buffer->sequence = seq ++;
		file_buffer->noD = inode->noD;
		file_buffer->error = FALSE;

		/*
		 * Always try to read block_size bytes from the file rather
		 * than expected bytes (which will be less than the block_size
		 * at the file tail) to check that the file hasn't grown
		 * since being stated.  If it is longer (or shorter) than
		 * expected, then restat, and try again.  Note the special
		 * case where the file is an exact multiple of the block_size
		 * is dealt with later.
		 */
		file_buffer->size = read_bytes(file, file_buffer->data,
			block_size);
		if(file_buffer->size == -1)
			goto read_err;

		bytes += file_buffer->size;

		if(blocks > 1) {
			/* non-tail block should be exactly block_size */
			if(file_buffer->size < block_size)
				goto restat;

			file_buffer->fragment = FALSE;
			put_file_buffer(file_buffer);
		}
	} while(-- blocks > 0);

	/* Overall size including tail should match */
	if(read_size != bytes)
		goto restat;

	if(read_size && read_size % block_size == 0) {
		/*
		 * Special case where we've not tried to read past the end of
		 * the file.  We expect to get EOF, i.e. the file isn't larger
		 * than we expect.
		 */
		char buffer;
		int res;

		res = read_bytes(file, &buffer, 1);
		if(res == -1)
			goto read_err;

		if(res != 0)
			goto restat;
	}

	file_buffer->fragment = is_fragment(inode);
	put_file_buffer(file_buffer);

	close(file);

	return;

restat:
	res = fstat(file, &buf2);
	if(res == -1) {
		ERROR("Cannot stat dir/file %s because %s\n",
			pathname_reader(dir_ent), strerror(errno));
		goto read_err;
	}

	if(read_size != buf2.st_size) {
		close(file);
		memcpy(buf, &buf2, sizeof(struct stat));
		file_buffer->error = 2;
		put_file_buffer(file_buffer);
		goto again;
	}
read_err:
	close(file);
read_err2:
	file_buffer->error = TRUE;
	put_file_buffer(file_buffer);
}


void reader_scan(struct dir_info *dir) {
	struct dir_ent *dir_ent = dir->list;

	for(; dir_ent; dir_ent = dir_ent->next) {
		struct stat *buf = &dir_ent->inode->buf;
		if(dir_ent->inode->root_entry)
			continue;

		if(IS_PSEUDO_PROCESS(dir_ent->inode)) {
			reader_read_process(dir_ent);
			continue;
		}

		switch(buf->st_mode & S_IFMT) {
			case S_IFREG:
				reader_read_file(dir_ent);
				break;
			case S_IFDIR:
				reader_scan(dir_ent->dir);
				break;
		}
	}
}


void *reader(void *arg)
{
	if(!sorted)
		reader_scan(queue_get(to_reader));
	else {
		int i;
		struct priority_entry *entry;

		queue_get(to_reader);
		for(i = 65535; i >= 0; i--)
			for(entry = priority_list[i]; entry;
							entry = entry->next)
				reader_read_file(entry->dir);
	}

	pthread_exit(NULL);
}


void *writer(void *arg)
{
	while(1) {
		struct file_buffer *file_buffer = queue_get(to_writer);
		off_t off;

		if(file_buffer == NULL) {
			queue_put(from_writer, NULL);
			continue;
		}

		off = file_buffer->block;

		pthread_cleanup_push((void *) pthread_mutex_unlock, &pos_mutex);
		pthread_mutex_lock(&pos_mutex);

		if(lseek(fd, off, SEEK_SET) == -1) {
			ERROR("writer: Lseek on destination failed because "
				"%s, offset=0x%llx\n", strerror(errno), off);
			BAD_ERROR("Probably out of space on output "
				"%s\n", block_device ? "block device" :
				"filesystem");
		}

		if(write_bytes(fd, file_buffer->data,
				file_buffer->size) == -1)
			BAD_ERROR("Failed to write to output %s\n",
				block_device ? "block device" : "filesystem");

		pthread_cleanup_pop(1);

		cache_block_put(file_buffer);
	}
}


int all_zero(struct file_buffer *file_buffer)
{
	int i;
	long entries = file_buffer->size / sizeof(long);
	long *p = (long *) file_buffer->data;

	for(i = 0; i < entries && p[i] == 0; i++);

	if(i == entries) {
		for(i = file_buffer->size & ~(sizeof(long) - 1);
			i < file_buffer->size && file_buffer->data[i] == 0;
			i++);

		return i == file_buffer->size;
	}

	return 0;
}


void *deflator(void *arg)
{
	struct file_buffer *write_buffer = cache_get_nohash(bwriter_buffer);
	void *stream = NULL;
	int res;

	res = compressor_init(comp, &stream, block_size, 1);
	if(res)
		BAD_ERROR("deflator:: compressor_init failed\n");

	while(1) {
		struct file_buffer *file_buffer = queue_get(to_deflate);

		if(sparse_files && all_zero(file_buffer)) { 
			file_buffer->c_byte = 0;
			seq_queue_put(to_main, file_buffer);
		} else {
			write_buffer->c_byte = mangle2(stream,
				write_buffer->data, file_buffer->data,
				file_buffer->size, block_size,
				file_buffer->noD, 1);
			write_buffer->sequence = file_buffer->sequence;
			write_buffer->file_size = file_buffer->file_size;
			write_buffer->block = file_buffer->block;
			write_buffer->size = SQUASHFS_COMPRESSED_SIZE_BLOCK
				(write_buffer->c_byte);
			write_buffer->fragment = FALSE;
			write_buffer->error = FALSE;
			cache_block_put(file_buffer);
			seq_queue_put(to_main, write_buffer);
			write_buffer = cache_get_nohash(bwriter_buffer);
		}
	}
}


void *frag_deflator(void *arg)
{
	void *stream = NULL;
	int res;

	res = compressor_init(comp, &stream, block_size, 1);
	if(res)
		BAD_ERROR("frag_deflator:: compressor_init failed\n");

	pthread_cleanup_push((void *) pthread_mutex_unlock, &fragment_mutex);

	while(1) {
		int c_byte, compressed_size;
		struct file_buffer *file_buffer = queue_get(to_frag);
		struct file_buffer *write_buffer =
			cache_get(fwriter_buffer, file_buffer->block);

		c_byte = mangle2(stream, write_buffer->data, file_buffer->data,
			file_buffer->size, block_size, noF, 1);
		compressed_size = SQUASHFS_COMPRESSED_SIZE_BLOCK(c_byte);
		write_buffer->size = compressed_size;
		pthread_mutex_lock(&fragment_mutex);
		if(fragments_locked == FALSE) {
			fragment_table[file_buffer->block].size = c_byte;
			fragment_table[file_buffer->block].start_block = bytes;
			write_buffer->block = bytes;
			bytes += compressed_size;
			fragments_outstanding --;
			queue_put(to_writer, write_buffer);
			pthread_mutex_unlock(&fragment_mutex);
			TRACE("Writing fragment %lld, uncompressed size %d, "
				"compressed size %d\n", file_buffer->block,
				file_buffer->size, compressed_size);
		} else {
				add_pending_fragment(write_buffer, c_byte,
					file_buffer->block);
				pthread_mutex_unlock(&fragment_mutex);
		}
		cache_block_put(file_buffer);
	}

	pthread_cleanup_pop(0);
}


struct file_buffer *get_file_buffer()
{
	struct file_buffer *file_buffer = seq_queue_get(to_main);

	return file_buffer;
}


void write_file_empty(squashfs_inode *inode, struct dir_ent *dir_ent,
	struct file_buffer *file_buffer, int *duplicate_file)
{
	file_count ++;
	*duplicate_file = FALSE;
	cache_block_put(file_buffer);
	create_inode(inode, NULL, dir_ent, SQUASHFS_FILE_TYPE, 0, 0, 0,
		 NULL, &empty_fragment, NULL, 0);
}


void write_file_frag(squashfs_inode *inode, struct dir_ent *dir_ent,
	struct file_buffer *file_buffer, int *duplicate_file)
{
	int size = file_buffer->file_size;
	struct fragment *fragment;
	unsigned short checksum = file_buffer->checksum;
	char dont_put;

	fragment = frag_duplicate(file_buffer, &dont_put);
	*duplicate_file = !fragment;
	if(!fragment) {
		fragment = get_and_fill_fragment(file_buffer, dir_ent);
		if(duplicate_checking)
			add_non_dup(size, 0, NULL, 0, fragment, 0, checksum,
				TRUE, TRUE);
	}

	if(dont_put)
		free(file_buffer);
	else
		cache_block_put(file_buffer);

	total_bytes += size;
	file_count ++;

	inc_progress_bar();

	create_inode(inode, NULL, dir_ent, SQUASHFS_FILE_TYPE, size, 0,
			0, NULL, fragment, NULL, 0);

	if(!duplicate_checking)
		free_fragment(fragment);
}


int write_file_process(squashfs_inode *inode, struct dir_ent *dir_ent,
	struct file_buffer *read_buffer, int *duplicate_file)
{
	long long read_size, file_bytes, start;
	struct fragment *fragment;
	unsigned int *block_list = NULL;
	int block = 0, status;
	long long sparse = 0;
	struct file_buffer *fragment_buffer = NULL;

	*duplicate_file = FALSE;

	lock_fragments();

	file_bytes = 0;
	start = bytes;
	while (1) {
		read_size = read_buffer->file_size;
		if(read_buffer->fragment)
			fragment_buffer = read_buffer;
		else {
			block_list = realloc(block_list, (block + 1) *
				sizeof(unsigned int));
			if(block_list == NULL)
				MEM_ERROR();
			block_list[block ++] = read_buffer->c_byte;
			if(read_buffer->c_byte) {
				read_buffer->block = bytes;
				bytes += read_buffer->size;
				cache_hash(read_buffer, read_buffer->block);
				file_bytes += read_buffer->size;
				queue_put(to_writer, read_buffer);
			} else {
				sparse += read_buffer->size;
				cache_block_put(read_buffer);
			}
		}
		inc_progress_bar();

		if(read_size != -1)
			break;

		read_buffer = get_file_buffer();
		if(read_buffer->error)
			goto read_err;
	}

	unlock_fragments();
	fragment = get_and_fill_fragment(fragment_buffer, dir_ent);

	if(duplicate_checking)
		add_non_dup(read_size, file_bytes, block_list, start, fragment,
			0, fragment_buffer ? fragment_buffer->checksum : 0,
			FALSE, TRUE);
	cache_block_put(fragment_buffer);
	file_count ++;
	total_bytes += read_size;

	create_inode(inode, NULL, dir_ent, SQUASHFS_FILE_TYPE, read_size, start,
		 block, block_list, fragment, NULL, sparse);

	if(duplicate_checking == FALSE) {
		free(block_list);
		free_fragment(fragment);
	}

	return 0;

read_err:
	dec_progress_bar(block);
	status = read_buffer->error;
	bytes = start;
	if(!block_device) {
		int res;

		queue_put(to_writer, NULL);
		if(queue_get(from_writer) != 0)
			EXIT_MKSQUASHFS();
		res = ftruncate(fd, bytes);
		if(res != 0)
			BAD_ERROR("Failed to truncate dest file because %s\n",
				strerror(errno));
	}
	unlock_fragments();
	free(block_list);
	cache_block_put(read_buffer);
	return status;
}


int write_file_blocks_dup(squashfs_inode *inode, struct dir_ent *dir_ent,
	struct file_buffer *read_buffer, int *duplicate_file)
{
	int block, thresh;
	long long read_size = read_buffer->file_size;
	long long file_bytes, dup_start, start;
	struct fragment *fragment;
	struct file_info *dupl_ptr;
	int blocks = (read_size + block_size - 1) >> block_log;
	unsigned int *block_list, *block_listp;
	struct file_buffer **buffer_list;
	int status;
	long long sparse = 0;
	struct file_buffer *fragment_buffer = NULL;

	block_list = malloc(blocks * sizeof(unsigned int));
	if(block_list == NULL)
		MEM_ERROR();
	block_listp = block_list;

	buffer_list = malloc(blocks * sizeof(struct file_buffer *));
	if(buffer_list == NULL)
		MEM_ERROR();

	lock_fragments();

	file_bytes = 0;
	start = dup_start = bytes;
	thresh = blocks > bwriter_size ? blocks - bwriter_size : 0;

	for(block = 0; block < blocks;) {
		if(read_buffer->fragment) {
			block_list[block] = 0;
			buffer_list[block] = NULL;
			fragment_buffer = read_buffer;
			blocks = read_size >> block_log;
		} else {
			block_list[block] = read_buffer->c_byte;

			if(read_buffer->c_byte) {
				read_buffer->block = bytes;
				bytes += read_buffer->size;
				file_bytes += read_buffer->size;
				cache_hash(read_buffer, read_buffer->block);
				if(block < thresh) {
					buffer_list[block] = NULL;
					queue_put(to_writer, read_buffer);
				} else
					buffer_list[block] = read_buffer;
			} else {
				buffer_list[block] = NULL;
				sparse += read_buffer->size;
				cache_block_put(read_buffer);
			}
		}
		inc_progress_bar();

		if(++block < blocks) {
			read_buffer = get_file_buffer();
			if(read_buffer->error)
				goto read_err;
		}
	}

	dupl_ptr = duplicate(read_size, file_bytes, &block_listp, &dup_start,
		&fragment, fragment_buffer, blocks, 0, FALSE);

	if(dupl_ptr) {
		*duplicate_file = FALSE;
		for(block = thresh; block < blocks; block ++)
			if(buffer_list[block])
				queue_put(to_writer, buffer_list[block]);
		fragment = get_and_fill_fragment(fragment_buffer, dir_ent);
		dupl_ptr->fragment = fragment;
	} else {
		*duplicate_file = TRUE;
		for(block = thresh; block < blocks; block ++)
			cache_block_put(buffer_list[block]);
		bytes = start;
		if(thresh && !block_device) {
			int res;

			queue_put(to_writer, NULL);
			if(queue_get(from_writer) != 0)
				EXIT_MKSQUASHFS();
			res = ftruncate(fd, bytes);
			if(res != 0)
				BAD_ERROR("Failed to truncate dest file because"
					"  %s\n", strerror(errno));
		}
	}

	unlock_fragments();
	cache_block_put(fragment_buffer);
	free(buffer_list);
	file_count ++;
	total_bytes += read_size;

	/*
	 * sparse count is needed to ensure squashfs correctly reports a
 	 * a smaller block count on stat calls to sparse files.  This is
 	 * to ensure intelligent applications like cp correctly handle the
 	 * file as a sparse file.  If the file in the original filesystem isn't
 	 * stored as a sparse file then still store it sparsely in squashfs, but
 	 * report it as non-sparse on stat calls to preserve semantics
 	 */
	if(sparse && (dir_ent->inode->buf.st_blocks << 9) >= read_size)
		sparse = 0;

	create_inode(inode, NULL, dir_ent, SQUASHFS_FILE_TYPE, read_size,
		dup_start, blocks, block_listp, fragment, NULL, sparse);

	if(*duplicate_file == TRUE)
		free(block_list);

	return 0;

read_err:
	dec_progress_bar(block);
	status = read_buffer->error;
	bytes = start;
	if(thresh && !block_device) {
		int res;

		queue_put(to_writer, NULL);
		if(queue_get(from_writer) != 0)
			EXIT_MKSQUASHFS();
		res = ftruncate(fd, bytes);
		if(res != 0)
			BAD_ERROR("Failed to truncate dest file because %s\n",
				strerror(errno));
	}
	unlock_fragments();
	for(blocks = thresh; blocks < block; blocks ++)
		cache_block_put(buffer_list[blocks]);
	free(buffer_list);
	free(block_list);
	cache_block_put(read_buffer);
	return status;
}


int write_file_blocks(squashfs_inode *inode, struct dir_ent *dir_ent,
	struct file_buffer *read_buffer, int *dup)
{
	long long read_size = read_buffer->file_size;
	long long file_bytes, start;
	struct fragment *fragment;
	unsigned int *block_list;
	int block, status;
	int blocks = (read_size + block_size - 1) >> block_log;
	long long sparse = 0;
	struct file_buffer *fragment_buffer = NULL;

	if(pre_duplicate(read_size))
		return write_file_blocks_dup(inode, dir_ent, read_buffer, dup);

	*dup = FALSE;

	block_list = malloc(blocks * sizeof(unsigned int));
	if(block_list == NULL)
		MEM_ERROR();

	lock_fragments();

	file_bytes = 0;
	start = bytes;
	for(block = 0; block < blocks;) {
		if(read_buffer->fragment) {
			block_list[block] = 0;
			fragment_buffer = read_buffer;
			blocks = read_size >> block_log;
		} else {
			block_list[block] = read_buffer->c_byte;
			if(read_buffer->c_byte) {
				read_buffer->block = bytes;
				bytes += read_buffer->size;
				cache_hash(read_buffer, read_buffer->block);
				file_bytes += read_buffer->size;
				queue_put(to_writer, read_buffer);
			} else {
				sparse += read_buffer->size;
				cache_block_put(read_buffer);
			}
		}
		inc_progress_bar();

		if(++block < blocks) {
			read_buffer = get_file_buffer();
			if(read_buffer->error)
				goto read_err;
		}
	}

	unlock_fragments();
	fragment = get_and_fill_fragment(fragment_buffer, dir_ent);

	if(duplicate_checking)
		add_non_dup(read_size, file_bytes, block_list, start, fragment,
			0, fragment_buffer ? fragment_buffer->checksum : 0,
			FALSE, TRUE);
	cache_block_put(fragment_buffer);
	file_count ++;
	total_bytes += read_size;

	/*
	 * sparse count is needed to ensure squashfs correctly reports a
 	 * a smaller block count on stat calls to sparse files.  This is
 	 * to ensure intelligent applications like cp correctly handle the
 	 * file as a sparse file.  If the file in the original filesystem isn't
 	 * stored as a sparse file then still store it sparsely in squashfs, but
 	 * report it as non-sparse on stat calls to preserve semantics
 	 */
	if(sparse && (dir_ent->inode->buf.st_blocks << 9) >= read_size)
		sparse = 0;

	create_inode(inode, NULL, dir_ent, SQUASHFS_FILE_TYPE, read_size, start,
		 blocks, block_list, fragment, NULL, sparse);

	if(duplicate_checking == FALSE) {
		free(block_list);
		free_fragment(fragment);
	}

	return 0;

read_err:
	dec_progress_bar(block);
	status = read_buffer->error;
	bytes = start;
	if(!block_device) {
		int res;

		queue_put(to_writer, NULL);
		if(queue_get(from_writer) != 0)
			EXIT_MKSQUASHFS();
		res = ftruncate(fd, bytes);
		if(res != 0)
			BAD_ERROR("Failed to truncate dest file because %s\n",
				strerror(errno));
	}
	unlock_fragments();
	free(block_list);
	cache_block_put(read_buffer);
	return status;
}


void write_file(squashfs_inode *inode, struct dir_ent *dir, int *dup)
{
	int status;
	struct file_buffer *read_buffer;

again:
	read_buffer = get_file_buffer();
	status = read_buffer->error;

	if(status)
		cache_block_put(read_buffer);
	else if(read_buffer->file_size == -1)
		status = write_file_process(inode, dir, read_buffer, dup);
	else if(read_buffer->file_size == 0)
		write_file_empty(inode, dir, read_buffer, dup);
	else if(read_buffer->fragment && read_buffer->c_byte)
		write_file_frag(inode, dir, read_buffer, dup);
	else
		status = write_file_blocks(inode, dir, read_buffer, dup);

	if(status == 2) {
		ERROR("File %s changed size while reading filesystem, "
			"attempting to re-read\n", pathname(dir));
		goto again;
	} else if(status == 1) {
		ERROR_START("Failed to read file %s", pathname(dir));
		ERROR_EXIT(", creating empty file\n");
		write_file_empty(inode, dir, NULL, dup);
	}
}


#define BUFF_SIZE 512
char *name;
char *basename_r();

char *getbase(char *pathname)
{
	static char *b_buffer = NULL;
	static int b_size = BUFF_SIZE;
	char *result;

	if(b_buffer == NULL) {
		b_buffer = malloc(b_size);
		if(b_buffer == NULL)
			MEM_ERROR();
	}

	while(1) {
		if(*pathname != '/') {
			result = getcwd(b_buffer, b_size);
			if(result == NULL && errno != ERANGE)
				BAD_ERROR("Getcwd failed in getbase\n");

			/* enough room for pathname + "/" + '\0' terminator? */
			if(result && strlen(pathname) + 2 <=
						b_size - strlen(b_buffer)) {
				strcat(strcat(b_buffer, "/"), pathname);
				break;
			}
		} else if(strlen(pathname) < b_size) {
			strcpy(b_buffer, pathname);
			break;
		}

		/* Buffer not large enough, realloc and try again */
		b_buffer = realloc(b_buffer, b_size += BUFF_SIZE);
		if(b_buffer == NULL)
			MEM_ERROR();
	}

	name = b_buffer;
	if(((result = basename_r()) == NULL) || (strcmp(result, "..") == 0))
		return NULL;
	else
		return result;
}


char *basename_r()
{
	char *s;
	char *p;
	int n = 1;

	for(;;) {
		s = name;
		if(*name == '\0')
			return NULL;
		if(*name != '/') {
			while(*name != '\0' && *name != '/') name++;
			n = name - s;
		}
		while(*name == '/') name++;
		if(strncmp(s, ".", n) == 0)
			continue;
		if((*name == '\0') || (strncmp(s, "..", n) == 0) ||
				((p = basename_r()) == NULL)) {
			s[n] = '\0';
			return s;
		}
		if(strcmp(p, "..") == 0)
			continue;
		return p;
	}
}


struct inode_info *lookup_inode3(struct stat *buf, int pseudo, int id,
	char *symlink, int bytes)
{
	int ino_hash = INODE_HASH(buf->st_dev, buf->st_ino);
	struct inode_info *inode;

	/*
	 * Look-up inode in hash table, if it already exists we have a
	 * hard-link, so increment the nlink count and return it.
	 * Don't do the look-up for directories because we don't hard-link
	 * directories.
	 */
	if ((buf->st_mode & S_IFMT) != S_IFDIR) {
		for(inode = inode_info[ino_hash]; inode; inode = inode->next) {
			if(memcmp(buf, &inode->buf, sizeof(struct stat)) == 0) {
				inode->nlink ++;
				return inode;
			}
		}
	}

	inode = malloc(sizeof(struct inode_info) + bytes);
	if(inode == NULL)
		MEM_ERROR();

	if(bytes)
		memcpy(&inode->symlink, symlink, bytes);
	memcpy(&inode->buf, buf, sizeof(struct stat));
	inode->read = FALSE;
	inode->root_entry = FALSE;
	inode->pseudo_file = pseudo;
	inode->pseudo_id = id;
	inode->inode = SQUASHFS_INVALID_BLK;
	inode->nlink = 1;
	inode->inode_number = 0;

	/*
	 * Copy filesystem wide defaults into inode, these filesystem
	 * wide defaults may be altered on an individual inode basis by
	 * user specified actions
	 *
	*/
	inode->no_fragments = no_fragments;
	inode->always_use_fragments = always_use_fragments;
	inode->noD = noD;
	inode->noF = noF;

	inode->next = inode_info[ino_hash];
	inode_info[ino_hash] = inode;

	return inode;
}


static inline struct inode_info *lookup_inode2(struct stat *buf, int pseudo, int id)
{
	return lookup_inode3(buf, pseudo, id, NULL, 0);
}


static inline struct inode_info *lookup_inode(struct stat *buf)
{
	return lookup_inode2(buf, 0, 0);
}


static inline void alloc_inode_no(struct inode_info *inode, unsigned int use_this)
{
	if (inode->inode_number == 0) {
		inode->inode_number = use_this ? : inode_no ++;