path: root/tests/fs-tests/integrity/integck.c

/*
 * Copyright (C) 2007 Nokia Corporation.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * version 2 as published by the Free Software Foundation.
 *
 * 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, Inc., 51 Franklin St, Fifth Floor, Boston, MA
 * 02110-1301 USA
 *
 * Author: Adrian Hunter
 */

#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <errno.h>
#include <limits.h>
#include <dirent.h>
#include <sys/mman.h>

#include "tests.h"

/* Structures to store data written to the test file system,
   so that we can check whether the file system is correct. */

struct write_info /* Record of random data written into a file */
{
	struct write_info *next;
	off_t offset; /* Where in the file the data was written */
	size_t size; /* Number of bytes written */
	unsigned random_seed; /* Seed for rand() to create random data */
	off_t random_offset; /* Call rand() this number of times first */
	int trunc; /* Records a truncation (raw_writes only) */
};

struct dir_entry_info;

struct file_info /* Each file has one of these */
{
	char *name; /* Original name */
	struct write_info *writes; /* Record accumulated writes to the file */
	struct write_info *raw_writes;
				/* Record in order all writes to the file */
	struct fd_info *fds; /* All open file descriptors for this file */
	struct dir_entry_info *links;
	int link_count;
	off_t length;
	int deleted; /* File has been deleted but is still open */
	int no_space_error; /* File has incurred a ENOSPC error */
	uint64_t check_run_no; /* Run number used when checking */
};

struct dir_info /* Each directory has one of these */
{
	char *name;
	struct dir_info *parent; /* Parent directory or null
					for our top directory */
	unsigned number_of_entries;
	struct dir_entry_info *first;
	struct dir_entry_info *entry; /* Dir entry of this dir */
};

struct dir_entry_info /* Each entry in a directory has one of these */
{
	struct dir_entry_info *next; /* List of entries in directory */
	struct dir_entry_info *prev; /* List of entries in directory */
	struct dir_entry_info *next_link; /* List of hard links for same file */
	struct dir_entry_info *prev_link; /* List of hard links for same file */
	char *name;
	struct dir_info *parent; /* Parent directory */
	char type; /* f => file, d => dir */
	int checked; /* Temporary flag used when checking */
	union entry_
	{
		struct file_info *file;
		struct dir_info *dir;
		void *target;
	} entry;
};

struct fd_info /* We keep a number of files open */
{
	struct fd_info *next;
	struct file_info *file;
	int fd;
};

struct open_file_info /* We keep a list of open files */
{
	struct open_file_info *next;
	struct fd_info *fdi;
};

static struct dir_info *top_dir = NULL; /* Our top directory */

static struct open_file_info *open_files = NULL; /* We keep a list of
							open files */
static size_t open_files_count = 0;

static int grow   = 1; /* Should we try to grow files and directories */
static int shrink = 0; /* Should we try to shrink files and directories */
static int full   = 0; /* Flag that the file system is full */
static uint64_t operation_count = 0; /* Number of operations used to fill
                                        up the file system */
static uint64_t initial_free_space = 0; /* Free space on file system when
					   test starts */
static unsigned log10_initial_free_space = 0; /* log10 of initial_free_space */

static int check_nospc_files = 0; /* Also check data in files that incurred a
				     "no space" error */

static int can_mmap = 0; /* Can write via mmap */

static long mem_page_size; /* Page size for mmap */

static uint64_t check_run_no;

static char *copy_string(const char *s)
{
	char *str;

	if (!s)
		return NULL;
	str = (char *) malloc(strlen(s) + 1);
	CHECK(str != NULL);
	strcpy(str, s);
	return str;
}

static char *cat_strings(const char *a, const char *b)
{
	char *str;
	size_t sz;

	if (a && !b)
		return copy_string(a);
	if (b && !a)
		return copy_string(b);
	if (!a && !b)
		return NULL;
	sz = strlen(a) + strlen(b) + 1;
	str = (char *) malloc(sz);
	CHECK(str != NULL);
	strcpy(str, a);
	strcat(str, b);
	return str;
}

static char *cat_paths(const char *a, const char *b)
{
	char *str;
	size_t sz;
	int as, bs;
	size_t na, nb;

	if (a && !b)
		return copy_string(a);
	if (b && !a)
		return copy_string(b);
	if (!a && !b)
		return NULL;

	as = 0;
	bs = 0;
	na = strlen(a);
	nb = strlen(b);
	if (na && a[na - 1] == '/')
		as = 1;
	if (nb && b[0] == '/')
		bs = 1;
	if ((as && !bs) || (!as && bs))
		return cat_strings(a, b);
	if (as && bs)
		return cat_strings(a, b + 1);

	sz = na + nb + 2;
	str = (char *) malloc(sz);
	CHECK(str != NULL);
	strcpy(str, a);
	strcat(str, "/");
	strcat(str, b);
	return str;
}

static char *dir_path(struct dir_info *parent, const char *name)
{
	char *parent_path;
	char *path;

	if (!parent)
		return cat_paths(tests_file_system_mount_dir, name);
	parent_path = dir_path(parent->parent, parent->name);
	path = cat_paths(parent_path, name);
	free(parent_path);
	return path;
}

static void open_file_add(struct fd_info *fdi)
{
	struct open_file_info *ofi;
	size_t sz;

	sz = sizeof(struct open_file_info);
	ofi = (struct open_file_info *) malloc(sz);
	CHECK(ofi != NULL);
	memset(ofi, 0, sz);
	ofi->next = open_files;
	ofi->fdi = fdi;
	open_files = ofi;
	open_files_count += 1;
}

static void open_file_remove(struct fd_info *fdi)
{
	struct open_file_info *ofi;
	struct open_file_info **prev;

	prev = &open_files;
	for (ofi = open_files; ofi; ofi = ofi->next) {
		if (ofi->fdi == fdi) {
			*prev = ofi->next;
			free(ofi);
			open_files_count -= 1;
			return;
		}
		prev = &ofi->next;
	}
	CHECK(0); /* We are trying to remove something that is not there */
}

static struct fd_info *add_fd(struct file_info *file, int fd)
{
	struct fd_info *fdi;
	size_t sz;

	sz = sizeof(struct fd_info);
	fdi = (struct fd_info *) malloc(sz);
	CHECK(fdi != NULL);
	memset(fdi, 0, sz);
	fdi->next = file->fds;
	fdi->file = file;
	fdi->fd = fd;
	file->fds = fdi;
	open_file_add(fdi);
	return fdi;
}

static void add_dir_entry(struct dir_info *parent, char type, const char *name,
			  void *target)
{
	struct dir_entry_info *entry;
	size_t sz;

	sz = sizeof(struct dir_entry_info);
	entry = (struct dir_entry_info *) malloc(sz);
	CHECK(entry != NULL);
	memset(entry, 0, sz);

	entry->type = type;
	entry->name = copy_string(name);
	entry->parent = parent;

	entry->next = parent->first;
	if (parent->first)
		parent->first->prev = entry;
	parent->first = entry;
	parent->number_of_entries += 1;

	if (entry->type == 'f') {
		struct file_info *file = target;

		entry->entry.file = file;
		entry->next_link = file->links;
		if (file->links)
			file->links->prev_link = entry;
		file->links = entry;
		file->link_count += 1;
	} else if (entry->type == 'd') {
		struct dir_info *dir = target;

		entry->entry.dir = dir;
		dir->entry = entry;
		dir->name = copy_string(name);
		dir->parent = parent;
	}
}

static void remove_dir_entry(struct dir_entry_info *entry)
{
	entry->parent->number_of_entries -= 1;
	if (entry->parent->first == entry)
		entry->parent->first = entry->next;
	if (entry->prev)
		entry->prev->next = entry->next;
	if (entry->next)
		entry->next->prev = entry->prev;

	if (entry->type == 'f') {
		struct file_info *file = entry->entry.file;

		if (entry->prev_link)
			entry->prev_link->next_link = entry->next_link;
		if (entry->next_link)
			entry->next_link->prev_link = entry->prev_link;
		if (file->links == entry)
			file->links = entry->next_link;
		file->link_count -= 1;
		if (file->link_count == 0)
			file->deleted = 1;
	}

	free(entry->name);
	free(entry);
}

static struct dir_info *dir_new(struct dir_info *parent, const char *name)
{
	struct dir_info *dir;
	size_t sz;
	char *path;

	path = dir_path(parent, name);
	if (mkdir(path, 0777) == -1) {
		CHECK(errno == ENOSPC);
		full = 1;
		free(path);
		return NULL;
	}
	free(path);

	sz = sizeof(struct dir_info);
	dir = (struct dir_info *) malloc(sz);
	CHECK(dir != NULL);
	memset(dir, 0, sz);
	dir->name = copy_string(name);
	dir->parent = parent;
	if (parent)
		add_dir_entry(parent, 'd', name, dir);
	return dir;
}

static void file_delete(struct file_info *file);
static void file_unlink(struct dir_entry_info *entry);

static void dir_remove(struct dir_info *dir)
{
	char *path;

	/* Remove directory contents */
	while (dir->first) {
		struct dir_entry_info *entry;

		entry = dir->first;
		if (entry->type == 'd')
			dir_remove(entry->entry.dir);
		else if (entry->type == 'f')
			file_unlink(entry);
		else
			CHECK(0); /* Invalid struct dir_entry_info */
	}
	/* Remove entry from parent directory */
	remove_dir_entry(dir->entry);
	/* Remove directory itself */
	path = dir_path(dir->parent, dir->name);
	CHECK(rmdir(path) != -1);
	free(dir);
}

static struct file_info *file_new(struct dir_info *parent, const char *name)
{
	struct file_info *file = NULL;
	char *path;
	mode_t mode;
	int fd;
	size_t sz;

	CHECK(parent != NULL);

	path = dir_path(parent, name);
	mode = S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP | S_IROTH;
	fd = open(path, O_CREAT | O_EXCL | O_RDWR, mode);
	if (fd == -1) {
		CHECK(errno == ENOSPC);
		free(path);
		full = 1;
		return NULL;
	}
	free(path);

	sz = sizeof(struct file_info);
	file = (struct file_info *) malloc(sz);
	CHECK(file != NULL);
	memset(file, 0, sz);
	file->name = copy_string(name);

	add_dir_entry(parent, 'f', name, file);

	add_fd(file, fd);

	return file;
}

static void link_new(struct dir_info *parent, const char *name,
		     struct file_info *file)
{
	struct dir_entry_info *entry;
	char *path, *target;
	int ret;

	if (!file)
		return;
	entry = file->links;
	if (!entry)
		return;
	path = dir_path(parent, name);
	target = dir_path(entry->parent, entry->name);
	ret = link(target, path);
	if (ret == -1) {
		CHECK(errno == ENOSPC);
		free(target);
		free(path);
		full = 1;
		return;
	}
	free(target);
	free(path);

	add_dir_entry(parent, 'f', name, file);
}

static void file_close(struct fd_info *fdi);

static void file_close_all(struct file_info *file)
{
	struct fd_info *fdi = file->fds;

	while (fdi) {
		struct fd_info *next = fdi->next;

		file_close(fdi);
		fdi = next;
	}
}

static void file_unlink(struct dir_entry_info *entry)
{
	struct file_info *file = entry->entry.file;
	char *path;

	path = dir_path(entry->parent, entry->name);

	/* Remove file entry from parent directory */
	remove_dir_entry(entry);

	/* Unlink the file */
	CHECK(unlink(path) != -1);
	free(path);

	/* Free struct file_info if file is not open and not linked */
	if (!file->fds && !file->links) {
		struct write_info *w, *next;

		free(file->name);
		w = file->writes;
		while (w) {
			next = w->next;
			free(w);
			w = next;
		}
		free(file);
	} else if (!file->links)
		file->deleted = 1;
}

static struct dir_entry_info *pick_entry(struct file_info *file)
{
	struct dir_entry_info *entry;
	size_t r;

	if (!file->link_count)
		return NULL;
	r = tests_random_no(file->link_count);
	entry = file->links;
	while (entry && r--)
		entry = entry->next_link;
	return entry;
}

static void file_unlink_file(struct file_info *file)
{
	struct dir_entry_info *entry;

	entry = pick_entry(file);
	if (!entry)
		return;
	file_unlink(entry);
}

static void file_delete(struct file_info *file)
{
	struct dir_entry_info *entry = file->links;

	file_close_all(file);
	while (entry) {
		struct dir_entry_info *next = entry->next_link;

		file_unlink(entry);
		entry = next;
	}
}

static void file_info_display(struct file_info *file)
{
	struct dir_entry_info *entry;
	struct write_info *w;
	unsigned wcnt;

	fprintf(stderr, "File Info:\n");
	fprintf(stderr, "    Original name: %s\n", file->name);
	fprintf(stderr, "    Link count: %d\n", file->link_count);
	fprintf(stderr, "    Links:\n");
	entry = file->links;
	while (entry) {
		fprintf(stderr, "      Name: %s\n", entry->name);
		fprintf(stderr, "      Directory: %s\n", entry->parent->name);
		entry = entry->next_link;
	}
	fprintf(stderr, "    Length: %u\n", (unsigned) file->length);
	fprintf(stderr, "    File was open: %s\n",
		(file->fds == NULL) ? "false" : "true");
	fprintf(stderr, "    File was deleted: %s\n",
		(file->deleted == 0) ? "false" : "true");
	fprintf(stderr, "    File was out of space: %s\n",
		(file->no_space_error == 0) ? "false" : "true");
	fprintf(stderr, "    File Data:\n");
	wcnt = 0;
	w = file->writes;
	while (w) {
		fprintf(stderr, "        Offset: %u  Size: %u  Seed: %u"
				"  R.Off: %u\n",
				(unsigned) w->offset,
				(unsigned) w->size,
				(unsigned) w->random_seed,
				(unsigned) w->random_offset);
		wcnt += 1;
		w = w->next;
	}
	fprintf(stderr, "    %u writes\n", wcnt);
	fprintf(stderr, "    ============================================\n");
	fprintf(stderr, "    Write Info:\n");
	wcnt = 0;
	w = file->raw_writes;
	while (w) {
		if (w->trunc)
			fprintf(stderr, "        Trunc from %u to %u\n",
					(unsigned) w->offset,
					(unsigned) w->random_offset);
		else
			fprintf(stderr, "        Offset: %u  Size: %u  Seed: %u"
					"  R.Off: %u\n",
					(unsigned) w->offset,
					(unsigned) w->size,
					(unsigned) w->random_seed,
					(unsigned) w->random_offset);
		wcnt += 1;
		w = w->next;
	}
	fprintf(stderr, "    %u writes or truncations\n", wcnt);
	fprintf(stderr, "    ============================================\n");
}

static struct fd_info *file_open(struct file_info *file)
{
	int fd, flags = O_RDWR;
	char *path;

	path = dir_path(file->links->parent, file->links->name);
	if (tests_random_no(100) == 1)
		flags |= O_SYNC;
	fd = open(path, flags);
	CHECK(fd != -1);
	free(path);
	return add_fd(file, fd);
}

#define BUFFER_SIZE 32768

static size_t file_write_data(	struct file_info *file,
				int fd,
				off_t offset,
				size_t size,
				unsigned seed)
{
	size_t remains, actual, block;
	ssize_t written;
	char buf[BUFFER_SIZE];

	srand(seed);
	CHECK(lseek(fd, offset, SEEK_SET) != (off_t) -1);
	remains = size;
	actual = 0;
	written = BUFFER_SIZE;
	while (remains) {
		/* Fill up buffer with random data */
		if (written < BUFFER_SIZE) {
			memmove(buf, buf + written, BUFFER_SIZE - written);
			written = BUFFER_SIZE - written;
		} else
			written = 0;
		for (; written < BUFFER_SIZE; ++written)
			buf[written] = rand();
		/* Write a block of data */
		if (remains > BUFFER_SIZE)
			block = BUFFER_SIZE;
		else
			block = remains;
		written = write(fd, buf, block);
		if (written < 0) {
			CHECK(errno == ENOSPC); /* File system full */
			full = 1;
			file->no_space_error = 1;
			break;
		}
		remains -= written;
		actual += written;
	}
	return actual;
}

static void file_write_info(struct file_info *file,
			off_t offset,
			size_t size,
			unsigned seed)
{
	struct write_info *new_write, *w, **prev, *tmp;
	int inserted;
	size_t sz;
	off_t end, chg;

	/* Create struct write_info */
	sz = sizeof(struct write_info);
	new_write = (struct write_info *) malloc(sz);
	CHECK(new_write != NULL);
	memset(new_write, 0, sz);
	new_write->offset = offset;
	new_write->size = size;
	new_write->random_seed = seed;

	w = (struct write_info *) malloc(sz);
	CHECK(w != NULL);
	memset(w, 0, sz);
	w->next = file->raw_writes;
	w->offset = offset;
	w->size = size;
	w->random_seed = seed;
	file->raw_writes = w;

	/* Insert it into file->writes */
	inserted = 0;
	end = offset + size;
	w = file->writes;
	prev = &file->writes;
	while (w) {
		if (w->offset >= end) {
			/* w comes after new_write, so insert before it */
			new_write->next = w;
			*prev = new_write;
			inserted = 1;
			break;
		}
		/* w does not come after new_write */
		if (w->offset + w->size > offset) {
			/* w overlaps new_write */
			if (w->offset < offset) {
				/* w begins before new_write begins */
				if (w->offset + w->size <= end)
					/* w ends before new_write ends */
					w->size = offset - w->offset;
				else {
					/* w ends after new_write ends */
					/* Split w */
					tmp = (struct write_info *) malloc(sz);
					CHECK(tmp != NULL);
					*tmp = *w;
					chg = end - tmp->offset;
					tmp->offset += chg;
					tmp->random_offset += chg;
					tmp->size -= chg;
					w->size = offset - w->offset;
					/* Insert new struct write_info */
					w->next = new_write;
					new_write->next = tmp;
					inserted = 1;
					break;
				}
			} else {
				/* w begins after new_write begins */
				if (w->offset + w->size <= end) {
					/* w is completely overlapped,
					   so remove it */
					*prev = w->next;
					tmp = w;
					w = w->next;
					free(tmp);
					continue;
				}
				/* w ends after new_write ends */
				chg = end - w->offset;
				w->offset += chg;
				w->random_offset += chg;
				w->size -= chg;
				continue;
			}
		}
		prev = &w->next;
		w = w->next;
	}
	if (!inserted)
		*prev = new_write;
	/* Update file length */
	if (end > file->length)
		file->length = end;
}

/* Randomly select offset and and size to write in a file */
static void get_offset_and_size(struct file_info *file,
				off_t *offset,
				size_t *size)
{
	size_t r, n;

	r = tests_random_no(100);
	if (r == 0 && grow)
		/* 1 time in 100, when growing, write off the end of the file */
		*offset = file->length + tests_random_no(10000000);
	else if (r < 4)
		/* 3 (or 4) times in 100, write at the beginning of file */
		*offset = 0;
	else if (r < 52 || !grow)
		/* 48 times in 100, write into the file */
		*offset = tests_random_no(file->length);
	else
		/* 48 times in 100, write at the end of the  file */
		*offset = file->length;
	/* Distribute the size logarithmically */
	if (tests_random_no(1000) == 0)
		r = tests_random_no(log10_initial_free_space + 2);
	else
		r = tests_random_no(log10_initial_free_space);
	n = 1;
	while (r--)
		n *= 10;
	*size = tests_random_no(n);
	if (!grow && *offset + *size > file->length)
		*size = file->length - *offset;
	if (*size == 0)
		*size = 1;
}

static void file_truncate_info(struct file_info *file, size_t new_length);

static int file_ftruncate(struct file_info *file, int fd, off_t new_length)
{
	if (ftruncate(fd, new_length) == -1) {
		CHECK(errno = ENOSPC);
		file->no_space_error = 1;
		/* Delete errored files */
		if (!check_nospc_files)
			file_delete(file);
		return 0;
	}
	return 1;
}

static void file_mmap_write(struct file_info *file)
{
	size_t write_cnt = 0, r, i, len, size;
	struct write_info *w = file->writes;
	void *addr;
	char *waddr;
	off_t offs, offset;
	unsigned seed;
	uint64_t free_space;
	int fd;
	char *path;

	if (!file->links)
		return;
	free_space = tests_get_free_space();
	if (!free_space)
		return;
	/* Randomly pick a written area of the file */
	if (!w)
		return;
	while (w) {
		write_cnt += 1;
		w = w->next;
	}
	r = tests_random_no(write_cnt);
	w = file->writes;
	for (i = 0; w && w->next && i < r; i++)
		w = w->next;

	offs = (w->offset / mem_page_size) * mem_page_size;
	len = w->size + (w->offset - offs);
	if (len > 1 << 24)
		len = 1 << 24;

	/* Open it */
	path = dir_path(file->links->parent, file->links->name);
	fd = open(path, O_RDWR);
	CHECK(fd != -1);
	free(path);

	/* mmap it */
	addr = mmap(NULL, len, PROT_READ | PROT_WRITE, MAP_SHARED, fd, offs);
	CHECK(close(fd) != -1);
	CHECK(addr != MAP_FAILED);

	/* Randomly select a part of the mmapped area to write */
	size = tests_random_no(w->size);
	if (size > free_space)
		size = free_space;
	if (size == 0)
		size = 1;
	offset = w->offset + tests_random_no(w->size - size);

	/* Write it */
	seed = tests_random_no(10000000);
	srand(seed);
	waddr = addr + (offset - offs);
	for (i = 0; i < size; i++)
		waddr[i] = rand();

	/* Unmap it */
	CHECK(munmap(addr, len) != -1);

	/* Record what was written */
	file_write_info(file, offset, size, seed);
}

static void file_write(struct file_info *file, int fd)
{
	off_t offset;
	size_t size, actual;
	unsigned seed;
	int truncate = 0;

	if (can_mmap && !full && !file->deleted && tests_random_no(100) == 1) {
		file_mmap_write(file);
		return;
	}

	get_offset_and_size(file, &offset, &size);
	seed = tests_random_no(10000000);
	actual = file_write_data(file, fd, offset, size, seed);

	if (offset + actual <= file->length && shrink)
		/* 1 time in 100, when shrinking
		   truncate after the write */
		if (tests_random_no(100) == 0)
			truncate = 1;

	if (actual != 0)
		file_write_info(file, offset, actual, seed);

	/* Delete errored files */
	if (!check_nospc_files && file->no_space_error) {
		file_delete(file);
		return;
	}

	if (truncate) {
		size_t new_length = offset + actual;
		if (file_ftruncate(file, fd, new_length))
			file_truncate_info(file, new_length);
	}
}

static void file_write_file(struct file_info *file)
{
	int fd;
	char *path;

	path = dir_path(file->links->parent, file->links->name);
	fd = open(path, O_WRONLY);
	CHECK(fd != -1);
	file_write(file, fd);
	CHECK(close(fd) != -1);
	free(path);
}

static void file_truncate_info(struct file_info *file, size_t new_length)
{
	struct write_info *w, **prev, *tmp;
	size_t sz;

	/* Remove / truncate file->writes */
	w = file->writes;
	prev = &file->writes;
	while (w) {
		if (w->offset >= new_length) {
			/* w comes after eof, so remove it */
			*prev = w->next;
			tmp = w;
			w = w->next;
			free(tmp);
			continue;
		}
		if (w->offset + w->size > new_length)
			w->size = new_length - w->offset;
		prev = &w->next;
		w = w->next;
	}
	/* Add an entry in raw_writes for the truncation */
	sz = sizeof(struct write_info);
	w = (struct write_info *) malloc(sz);
	CHECK(w != NULL);
	memset(w, 0, sz);
	w->next = file->raw_writes;
	w->offset = file->length;
	w->random_offset = new_length; /* Abuse random_offset */
	w->trunc = 1;
	file->raw_writes = w;
	/* Update file length */
	file->length = new_length;
}

static void file_truncate(struct file_info *file, int fd)
{
	size_t new_length;

	new_length = tests_random_no(file->length);

	if (file_ftruncate(file, fd, new_length))
		file_truncate_info(file, new_length);
}

static void file_truncate_file(struct file_info *file)
{
	int fd;
	char *path;

	path = dir_path(file->links->parent, file->links->name);
	fd = open(path, O_WRONLY);
	CHECK(fd != -1);
	file_truncate(file, fd);
	CHECK(close(fd) != -1);
	free(path);
}

static void file_close(struct fd_info *fdi)
{
	struct file_info *file;
	struct fd_info *fdp;
	struct fd_info **prev;

	/* Close file */
	CHECK(close(fdi->fd) != -1);
	/* Remove struct fd_info */
	open_file_remove(fdi);
	file = fdi->file;
	prev = &file->fds;
	for (fdp = file->fds; fdp; fdp = fdp->next) {
		if (fdp == fdi) {
			*prev = fdi->next;
			free(fdi);
			if (file->deleted && !file->fds) {
				/* Closing deleted file */
				struct write_info *w, *next;

				w = file->writes;
				while (w) {
					next = w->next;
					free(w);
					w = next;
				}
				free(file->name);
				free(file);
			}
			return;
		}
		prev = &fdp->next;
	}
	CHECK(0); /* Didn't find struct fd_info */
}

static void file_rewrite_data(int fd, struct write_info *w, char *buf)
{
	size_t remains, block;
	ssize_t written;
	off_t r;

	srand(w->random_seed);
	for (r = 0; r < w->random_offset; ++r)
		rand();
	CHECK(lseek(fd, w->offset, SEEK_SET) != (off_t) -1);
	remains = w->size;
	written = BUFFER_SIZE;
	while (remains) {
		/* Fill up buffer with random data */
		if (written < BUFFER_SIZE)
			memmove(buf, buf + written, BUFFER_SIZE - written);
		else
			written = 0;
		for (; written < BUFFER_SIZE; ++written)
			buf[written] = rand();
		/* Write a block of data */
		if (remains > BUFFER_SIZE)
			block = BUFFER_SIZE;
		else
			block = remains;
		written = write(fd, buf, block);
		CHECK(written == block);
		remains -= written;
	}
}

static void save_file(int fd, struct file_info *file)
{
	int w_fd;
	struct write_info *w;
	char buf[BUFFER_SIZE];
	char name[256];

	/* Open file to save contents to */
	strcpy(name, "/tmp/");
	strcat(name, file->name);
	strcat(name, ".integ.sav.read");
	fprintf(stderr, "Saving %s\n", name);
	w_fd = open(name, O_CREAT | O_WRONLY, 0777);
	CHECK(w_fd != -1);

	/* Start at the beginning */
	CHECK(lseek(fd, 0, SEEK_SET) != (off_t) -1);

	for (;;) {
		ssize_t r = read(fd, buf, BUFFER_SIZE);
		CHECK(r != -1);
		if (!r)
			break;
		CHECK(write(w_fd, buf, r) == r);
	}
	CHECK(close(w_fd) != -1);

	/* Open file to save contents to */
	strcpy(name, "/tmp/");
	strcat(name, file->name);
	strcat(name, ".integ.sav.written");
	fprintf(stderr, "Saving %s\n", name);
	w_fd = open(name, O_CREAT | O_WRONLY, 0777);
	CHECK(w_fd != -1);

	for (w = file->writes; w; w = w->next)
		file_rewrite_data(w_fd, w, buf);

	CHECK(close(w_fd) != -1);
}

static void file_check_hole(	struct file_info *file,
				int fd, off_t offset,
				size_t size)
{
	size_t remains, block, i;
	char buf[BUFFER_SIZE];

	CHECK(lseek(fd, offset, SEEK_SET) != (off_t) -1);
	remains = size;
	while (remains) {
		if (remains > BUFFER_SIZE)
			block = BUFFER_SIZE;
		else
			block = remains;
		CHECK(read(fd, buf, block) == block);
		for (i = 0; i < block; ++i) {
			if (buf[i] != 0) {
				fprintf(stderr, "file_check_hole failed at %u "
					"checking hole at %u size %u\n",
					(unsigned) (size - remains + i),
					(unsigned) offset,
					(unsigned) size);
				file_info_display(file);
				save_file(fd, file);
			}
			CHECK(buf[i] == 0);
		}
		remains -= block;
	}
}

static void file_check_data(	struct file_info *file,
				int fd,
				struct write_info *w)
{
	size_t remains, block, i;
	off_t r;
	char buf[BUFFER_SIZE];

	srand(w->random_seed);
	for (r = 0; r < w->random_offset; ++r)
		rand();
	CHECK(lseek(fd, w->offset, SEEK_SET) != (off_t) -1);
	remains = w->size;
	while (remains) {
		if (remains > BUFFER_SIZE)
			block = BUFFER_SIZE;
		else
			block = remains;
		CHECK(read(fd, buf, block) == block);
		for (i = 0; i < block; ++i) {
			char c = (char) rand();
			if (buf[i] != c) {
				fprintf(stderr, "file_check_data failed at %u "
					"checking data at %u size %u\n",
					(unsigned) (w->size - remains + i),
					(unsigned) w->offset,
					(unsigned) w->size);
				file_info_display(file);
				save_file(fd, file);
			}
			CHECK(buf[i] == c);
		}
		remains -= block;
	}
}

static void file_check(struct file_info *file, int fd)
{
	int open_and_close = 0, link_count = 0;
	char *path = NULL;
	off_t pos;
	struct write_info *w;
	struct dir_entry_info *entry;
	struct stat st;

	/* Do not check files that have errored */
	if (!check_nospc_files && file->no_space_error)
		return;
	/* Do not check the same file twice */
	if (file->check_run_no == check_run_no)
		return;
	file->check_run_no = check_run_no;
	if (fd == -1)
		open_and_close = 1;
	if (open_and_close) {
		/* Open file */
		path = dir_path(file->links->parent, file->links->name);
		fd = open(path, O_RDONLY);
		CHECK(fd != -1);
	}
	/* Check length */
	pos = lseek(fd, 0, SEEK_END);
	if (pos != file->length) {
		fprintf(stderr, "file_check failed checking length "
			"expected %u actual %u\n",
			(unsigned) file->length,
			(unsigned) pos);
		file_info_display(file);
		save_file(fd, file);
	}
	CHECK(pos == file->length);
	/* Check each write */
	pos = 0;
	for (w = file->writes; w; w = w->next) {
		if (w->offset > pos)
			file_check_hole(file, fd, pos, w->offset - pos);
		file_check_data(file, fd, w);
		pos = w->offset + w->size;
	}
	if (file->length > pos)
		file_check_hole(file, fd, pos, file->length - pos);
	CHECK(fstat(fd, &st) != -1);
	CHECK(file->link_count == st.st_nlink);
	if (open_and_close) {
		CHECK(close(fd) != -1);
		free(path);
	}
	entry = file->links;
	while (entry) {
		link_count += 1;
		entry = entry->next_link;
	}
	CHECK(link_count == file->link_count);
}

static int search_comp(const void *pa, const void *pb)
{
	const struct dirent *a = (const struct dirent *) pa;
	const struct dir_entry_info *b = * (const struct dir_entry_info **) pb;
	return strcmp(a->d_name, b->name);
}

static void dir_entry_check(struct dir_entry_info **entry_array,
			size_t number_of_entries,
			struct dirent *ent)
{
	struct dir_entry_info **found;
	struct dir_entry_info *entry;
	size_t sz;

	sz = sizeof(struct dir_entry_info *);
	found = bsearch(ent, entry_array, number_of_entries, sz, search_comp);
	CHECK(found != NULL);
	entry = *found;
	CHECK(!entry->checked);
	entry->checked = 1;
}

static int sort_comp(const void *pa, const void *pb)
{
	const struct dir_entry_info *a = * (const struct dir_entry_info **) pa;
	const struct dir_entry_info *b = * (const struct dir_entry_info **) pb;
	return strcmp(a->name, b->name);
}

static void dir_check(struct dir_info *dir)
{
	struct dir_entry_info **entry_array, **p;
	size_t sz, n;
	struct dir_entry_info *entry;
	DIR *d;
	struct dirent *ent;
	unsigned checked = 0;
	char *path;
	int link_count = 2; /* Parent and dot */
	struct stat st;

	/* Create an array of entries */
	sz = sizeof(struct dir_entry_info *);
	n = dir->number_of_entries;
	entry_array = (struct dir_entry_info **) malloc(sz * n);
	CHECK(entry_array != NULL);

	entry = dir->first;
	p = entry_array;
	while (entry) {
		*p++ = entry;
		entry->checked = 0;
		entry = entry->next;
	}

	/* Sort it by name */
	qsort(entry_array, n, sz, sort_comp);

	/* Go through directory on file system checking entries match */
	path = dir_path(dir->parent, dir->name);
	d = opendir(path);
	CHECK(d != NULL);
	for (;;) {
		errno = 0;
		ent = readdir(d);
		if (ent) {
			if (strcmp(".",ent->d_name) != 0 &&
					strcmp("..",ent->d_name) != 0) {
				dir_entry_check(entry_array, n, ent);
				checked += 1;
			}
		} else {
			CHECK(errno == 0);
			break;
		}
	}
	CHECK(closedir(d) != -1);
	CHECK(checked == dir->number_of_entries);

	/* Now check each entry */
	entry = dir->first;
	while (entry) {
		if (entry->type == 'd') {
			dir_check(entry->entry.dir);
			link_count += 1; /* <subdir>/.. */
		} else if (entry->type == 'f')
			file_check(entry->entry.file, -1);
		else
			CHECK(0);
		entry = entry->next;
	}

	CHECK(stat(path, &st) != -1);
	CHECK(link_count == st.st_nlink);

	free(entry_array);
	free(path);
}

static void check_deleted_files(void)
{
	struct open_file_info *ofi;

	for (ofi = open_files; ofi; ofi = ofi->next)
		if (ofi->fdi->file->deleted)
			file_check(ofi->fdi->file, ofi->fdi->fd);
}

static void close_open_files(void)
{
	struct open_file_info *ofi;

	for (ofi = open_files; ofi; ofi = open_files)
		file_close(ofi->fdi);
}

static char *make_name(struct dir_info *dir)
{
	static char name[256];
	struct dir_entry_info *entry;
	int found;

	do {
		found = 0;
		if (tests_random_no(5) == 1) {
			int i, n = tests_random_no(255) + 1;

			CHECK(n > 0 && n < 256);
			for (i = 0; i < n; i++)
				name[i] = 'a' + tests_random_no(26);
			name[i] = '\0';
		} else
			sprintf(name, "%u", (unsigned) tests_random_no(1000000));
		for (entry = dir->first; entry; entry = entry->next) {
			if (strcmp(entry->name, name) == 0) {
				found = 1;
				break;
			}
		}
	} while (found);
	return name;
}

static struct file_info *pick_file(void)
{
	struct dir_info *dir = top_dir;

	for (;;) {
		struct dir_entry_info *entry;
		size_t r;

		r = tests_random_no(dir->number_of_entries);
		entry = dir->first;
		while (entry && r) {
			entry = entry->next;
			--r;
		}
		for (;;) {
			if (!entry)
				return NULL;
			if (entry->type == 'f')
				return entry->entry.file;
			if (entry->type == 'd')
				if (entry->entry.dir->number_of_entries != 0)
					break;
			entry = entry->next;
		}
		dir = entry->entry.dir;
	}
}

static struct dir_info *pick_dir(void)
{
	struct dir_info *dir = top_dir;

	if (tests_random_no(40) >= 30)
		return dir;
	for (;;) {
		struct dir_entry_info *entry;
		size_t r;

		r = tests_random_no(dir->number_of_entries);
		entry = dir->first;
		while (entry && r) {
			entry = entry->next;
			--r;
		}
		for (;;) {
			if (!entry)
				break;
			if (entry->type == 'd')
				break;
			entry = entry->next;
		}
		if (!entry) {
			entry = dir->first;
			for (;;) {
				if (!entry)
					break;
				if (entry->type == 'd')
					break;
				entry = entry->next;
			}
		}
		if (!entry)
			return dir;
		dir = entry->entry.dir;
		if (tests_random_no(40) >= 30)
			return dir;
	}
}

static char *pick_rename_name(struct dir_info **parent,
			      struct dir_entry_info **rename_entry, int isdir)
{
	struct dir_info *dir = pick_dir();
	struct dir_entry_info *entry;
	size_t r;

	*parent = dir;
	*rename_entry = NULL;

	if (grow || tests_random_no(20) < 10)
		return copy_string(make_name(dir));

	r = tests_random_no(dir->number_of_entries);
	entry = dir->first;
	while (entry && r) {
		entry = entry->next;
		--r;
	}
	if (!entry)
		entry = dir->first;
	if (!entry ||
	    (entry->type == 'd' && entry->entry.dir->number_of_entries != 0))
		return copy_string(make_name(dir));

	if ((isdir && entry->type != 'd') ||
	    (!isdir && entry->type == 'd'))
		return copy_string(make_name(dir));

	*rename_entry = entry;
	return copy_string(entry->name);
}

static void rename_entry(struct dir_entry_info *entry)
{
	struct dir_entry_info *rename_entry = NULL;
	struct dir_info *parent;
	char *path, *to, *name;
	int ret, isdir, retry;

	if (!entry->parent)
		return;

	for (retry = 0; retry < 3; retry++) {
		path = dir_path(entry->parent, entry->name);
		isdir = entry->type == 'd' ? 1 : 0;
		name = pick_rename_name(&parent, &rename_entry, isdir);
		to = dir_path(parent, name);
		/*
		 * Check we are not trying to move a directory to a subdirectory
		 * of itself.
		 */
		if (isdir) {
			struct dir_info *p;

			for (p = parent; p; p = p->parent)
				if (p == entry->entry.dir)
					break;
			if (p == entry->entry.dir) {
				free(path);
				free(name);
				free(to);
				continue;
			}
		}
		break;
	}

	ret = rename(path, to);
	if (ret == -1) {
		if (errno == ENOSPC)
			full = 1;
		CHECK(errno == ENOSPC || errno == EBUSY);
		free(path);
		free(name);
		free(to);
		return;
	}

	free(path);
	free(to);

	if (rename_entry && rename_entry->type == entry->type &&
	    rename_entry->entry.target == entry->entry.target) {
		free(name);
		return;
	}

	add_dir_entry(parent, entry->type, name, entry->entry.target);
	if (rename_entry)
		remove_dir_entry(rename_entry);
	remove_dir_entry(entry);
	free(name);
}

static void operate_on_dir(struct dir_info *dir);
static void operate_on_file(struct file_info *file);

/* Randomly select something to do with a directory entry */
static void operate_on_entry(struct dir_entry_info *entry)
{
	/* 1 time in 1000 rename */
	if (tests_random_no(1000) == 0) {
		rename_entry(entry);
		return;
	}
	if (entry->type == 'd') {
		/* If shrinking, 1 time in 50, remove a directory */
		if (shrink && tests_random_no(50) == 0) {
			dir_remove(entry->entry.dir);
			return;
		}
		operate_on_dir(entry->entry.dir);
	}
	if (entry->type == 'f') {
		/* If shrinking, 1 time in 10, remove a file */
		if (shrink && tests_random_no(10) == 0) {
			file_delete(entry->entry.file);
			return;
		}
		/* If not growing, 1 time in 10, unlink a file with links > 1 */
		if (!grow && entry->entry.file->link_count > 1 &&
		    tests_random_no(10) == 0) {
			file_unlink_file(entry->entry.file);
			return;
		}
		operate_on_file(entry->entry.file);
	}
}

/* Randomly select something to do with a directory */
static void operate_on_dir(struct dir_info *dir)
{
	size_t r;
	struct dir_entry_info *entry;
	struct file_info *file;

	r = tests_random_no(12);
	if (r == 0 && grow)
		/* When growing, 1 time in 12 create a file */
		file_new(dir, make_name(dir));
	else if (r == 1 && grow)
		/* When growing, 1 time in 12 create a directory */
		dir_new(dir, make_name(dir));
	else if (r == 2 && grow && (file = pick_file()) != NULL)
		/* When growing, 1 time in 12 create a hard link */
		link_new(dir, make_name(dir), file);
	else {
		/* Otherwise randomly select an entry to operate on */
		r = tests_random_no(dir->number_of_entries);
		entry = dir->first;
		while (entry && r) {
			entry = entry->next;
			--r;
		}
		if (entry)
			operate_on_entry(entry);
	}
}

/* Randomly select something to do with a file */
static void operate_on_file(struct file_info *file)
{
	/* Try to keep at least 10 files open */
	if (open_files_count < 10) {
		file_open(file);
		return;
	}
	/* Try to keep about 20 files open */
	if (open_files_count < 20 && tests_random_no(2) == 0) {
		file_open(file);
		return;
	}
	/* Try to keep up to 40 files open */
	if (open_files_count < 40 && tests_random_no(20) == 0) {
		file_open(file);
		return;
	}
	/* Occasionly truncate */
	if (shrink && tests_random_no(100) == 0) {
		file_truncate_file(file);
		return;
	}
	/* Mostly just write */
	file_write_file(file);
	/* Once in a while check it too */
	if (tests_random_no(100) == 1) {
		int fd = -2;

		if (file->links)
			fd = -1;
		else if (file->fds)
			fd = file->fds->fd;
		if (fd != -2) {
			check_run_no += 1;
			file_check(file, fd);
		}
	}
}

/* Randomly select something to do with an open file */
static void operate_on_open_file(struct fd_info *fdi)
{
	size_t r;

	r = tests_random_no(1000);
	if (shrink && r < 5)
		file_truncate(fdi->file, fdi->fd);
	else if (r < 21)
		file_close(fdi);
	else if (shrink && r < 121 && !fdi->file->deleted)
		file_delete(fdi->file);
	else {
		file_write(fdi->file, fdi->fd);
		if (r >= 999) {
			if (tests_random_no(100) >= 50)
				CHECK(fsync(fdi->fd) != -1);
			else
				CHECK(fdatasync(fdi->fd) != -1);
		}
	}
}

/* Select an open file at random */
static void operate_on_an_open_file(void)
{
	size_t r;
	struct open_file_info *ofi;

	/* When shrinking, close all open files 1 time in 128 */
	if (shrink) {
		static int x = 0;

		x += 1;
		x &= 127;
		if (x == 0) {
			close_open_files();
			return;
		}
	}
	/* Close any open files that have errored */
	if (!check_nospc_files) {
		ofi = open_files;
		while (ofi) {
			if (ofi->fdi->file->no_space_error) {
				struct fd_info *fdi;

				fdi = ofi->fdi;
				ofi = ofi->next;
				file_close(fdi);
			} else
				ofi = ofi->next;
		}
	}
	r = tests_random_no(open_files_count);
	for (ofi = open_files; ofi; ofi = ofi->next, --r)
		if (!r) {
			operate_on_open_file(ofi->fdi);
			return;
		}
}

static void do_an_operation(void)
{
	/* Half the time operate on already open files */
	if (tests_random_no(100) < 50)
		operate_on_dir(top_dir);
	else
		operate_on_an_open_file();
}

static void create_test_data(void)
{
	uint64_t i, n;

	grow = 1;
	shrink = 0;
	full = 0;
	operation_count = 0;
	while (!full) {
		do_an_operation();
		++operation_count;
	}
	grow = 0;
	shrink = 1;
	/* Drop to less than 90% full */
	n = operation_count / 40;
	while (n--) {
		uint64_t free;
		uint64_t total;
		for (i = 0; i < 10; ++i)
			do_an_operation();
		free = tests_get_free_space();
		total = tests_get_total_space();
		if ((free * 100) / total >= 10)
			break;
	}
	grow = 0;
	shrink = 0;
	full = 0;
	n = operation_count * 2;
	for (i = 0; i < n; ++i)
		do_an_operation();
}

static void update_test_data(void)
{
	uint64_t i, n;

	grow = 1;
	shrink = 0;
	full = 0;
	while (!full)
		do_an_operation();
	grow = 0;
	shrink = 1;
	/* Drop to less than 50% full */
	n = operation_count / 10;
	while (n--) {
		uint64_t free;
		uint64_t total;
		for (i = 0; i < 10; ++i)
			do_an_operation();
		free = tests_get_free_space();
		total = tests_get_total_space();
		if ((free * 100) / total >= 50)
			break;
	}
	grow = 0;
	shrink = 0;
	full = 0;
	n = operation_count * 2;
	for (i = 0; i < n; ++i)
		do_an_operation();
}

void integck(void)
{
	pid_t pid;
	int64_t rpt;
	uint64_t z;
	char dir_name[256];

	/* Get memory page size for mmap */
	mem_page_size = sysconf(_SC_PAGE_SIZE);
	CHECK(mem_page_size > 0);
	/* Make our top directory */
	pid = getpid();
	printf("pid is %u\n", (unsigned) pid);
	tests_cat_pid(dir_name, "integck_test_dir_", pid);
	if (chdir(dir_name) != -1) {
		/* Remove it if it is already there */
		tests_clear_dir(".");
		CHECK(chdir("..") != -1);
		CHECK(rmdir(dir_name) != -1);
	}
	initial_free_space = tests_get_free_space();
	log10_initial_free_space = 0;
	for (z = initial_free_space; z >= 10; z /= 10)
		++log10_initial_free_space;
	top_dir = dir_new(NULL, dir_name);

	if (!top_dir)
		return;

	srand(pid);

	create_test_data();

	if (!tests_fs_is_rootfs()) {
		close_open_files();
		tests_remount(); /* Requires root access */
	}

	/* Check everything */
	check_run_no += 1;
	dir_check(top_dir);
	check_deleted_files();

	for (rpt = 0; tests_repeat_parameter == 0 ||
				rpt < tests_repeat_parameter; ++rpt) {
		update_test_data();

		if (!tests_fs_is_rootfs()) {
			close_open_files();
			tests_remount(); /* Requires root access */
		}

		/* Check everything */
		check_run_no += 1;
		dir_check(top_dir);
		check_deleted_files();
	}

	/* Tidy up by removing everything */
	close_open_files();
	tests_clear_dir(dir_name);
	CHECK(rmdir(dir_name) != -1);
}

/* Title of this test */

const char *integck_get_title(void)
{
	return "Test file system integrity";
}

/* Description of this test */

const char *integck_get_description(void)
{
	return
		"Create a directory named integck_test_dir_pid " \
		"where pid is the process id. " \
		"Randomly create and delete files and directories. " \
		"Randomly write to and truncate files. " \
		"Un-mount and re-mount test file " \
		"system (if it is not the root file system ). " \
		"Check data. Make more random changes. " \
		"Un-mount and re-mount again. Check again. " \
		"Repeat some number of times. "
		"The repeat count is set by the -n or --repeat option, " \
		"otherwise it defaults to 1. " \
		"A repeat count of zero repeats forever.";
}

int main(int argc, char *argv[])
{
	int run_test;

	/* Set default test repetition */
	tests_repeat_parameter = 1;

	/* Handle common arguments */
	run_test = tests_get_args(argc, argv, integck_get_title(),
			integck_get_description(), "n");
	if (!run_test)
		return 1;
	/* Change directory to the file system and check it is ok for testing */
	tests_check_test_file_system();
	/*
	 * We expect accurate file size from ubifs even after "no space"
	 * errors. And we can mmap.
	 */
	if (strcmp(tests_file_system_type, "ubifs") == 0) {
		check_nospc_files = 1;
		can_mmap = 1;
	}
	/* Do the actual test */
	integck();
	return 0;
}