/*
 * Copyright 2004-2012, Axel Dörfler, axeld@pinc-software.de.
 * Distributed under the terms of the MIT License.
 */


#include <new>
#include <stdlib.h>
#include <string.h>

#ifdef FS_SHELL
#	include "vfs.h"
#	include "fssh_api_wrapper.h"

using namespace FSShell;
#else
#	include <unistd.h>

#	include <KernelExport.h>
#	include <fs_cache.h>

#	include <condition_variable.h>
#	include <file_cache.h>
#	include <generic_syscall.h>
#	include <util/AutoLock.h>
#	include <util/DoublyLinkedList.h>
#	include <vfs.h>
#	include <vm/vm.h>
#	include <vm/vm_page.h>
#	include <vm/VMCache.h>

#	include "kernel_debug_config.h"
#endif


//#define TRACE_FILE_MAP
#ifdef TRACE_FILE_MAP
#	define TRACE(x...) dprintf_no_syslog(x)
#else
#	define TRACE(x...) ;
#endif

// TODO: use a sparse array - eventually, the unused BlockMap would be something
//	to reuse for this. We could also have an upperbound of memory consumption
//	for the whole map.
// TODO: it would be nice if we could free a file map in low memory situations.


#define CACHED_FILE_EXTENTS	2
	// must be smaller than MAX_FILE_IO_VECS
	// TODO: find out how much of these are typically used

struct file_extent {
	off_t			offset;
	file_io_vec		disk;
};

struct file_extent_array {
	file_extent*	array;
	size_t			max_count;
};

class FileMap
#if DEBUG_FILE_MAP
	: public DoublyLinkedListLinkImpl<FileMap>
#endif
{
public:
							FileMap(struct vnode* vnode, off_t size);
							~FileMap();

			void			Invalidate(off_t offset, off_t size);
			void			SetSize(off_t size);

			status_t		Translate(off_t offset, size_t size,
								file_io_vec* vecs, size_t* _count,
								size_t align);

			file_extent*	ExtentAt(uint32 index);

			size_t			Count() const { return fCount; }
			struct vnode*	Vnode() const { return fVnode; }
			off_t			Size() const { return fSize; }

			status_t		SetMode(uint32 mode);

private:
			file_extent*	_FindExtent(off_t offset, uint32* _index);
			status_t		_MakeSpace(size_t count);
			status_t		_Add(file_io_vec* vecs, size_t vecCount,
								off_t& lastOffset);
			status_t		_Cache(off_t offset, off_t size);
			void			_InvalidateAfter(off_t offset);
			void			_Free();

	union {
		file_extent	fDirect[CACHED_FILE_EXTENTS];
		file_extent_array fIndirect;
	};
	mutex			fLock;
	size_t			fCount;
	struct vnode*	fVnode;
	off_t			fSize;
	bool			fCacheAll;
};

#if DEBUG_FILE_MAP
typedef DoublyLinkedList<FileMap> FileMapList;

static FileMapList sList;
static mutex sLock;
#endif


FileMap::FileMap(struct vnode* vnode, off_t size)
	:
	fCount(0),
	fVnode(vnode),
	fSize(size),
	fCacheAll(false)
{
	mutex_init(&fLock, "file map");

#if DEBUG_FILE_MAP
	MutexLocker _(sLock);
	sList.Add(this);
#endif
}


FileMap::~FileMap()
{
	_Free();
	mutex_destroy(&fLock);

#if DEBUG_FILE_MAP
	MutexLocker _(sLock);
	sList.Remove(this);
#endif
}


file_extent*
FileMap::ExtentAt(uint32 index)
{
	if (index >= fCount)
		return NULL;

	if (fCount > CACHED_FILE_EXTENTS)
		return &fIndirect.array[index];

	return &fDirect[index];
}


file_extent*
FileMap::_FindExtent(off_t offset, uint32 *_index)
{
	int32 left = 0;
	int32 right = fCount - 1;

	while (left <= right) {
		int32 index = (left + right) / 2;
		file_extent* extent = ExtentAt(index);

		if (extent->offset > offset) {
			// search in left part
			right = index - 1;
		} else if (extent->offset + extent->disk.length <= offset) {
			// search in right part
			left = index + 1;
		} else {
			// found extent
			if (_index)
				*_index = index;

			return extent;
		}
	}

	return NULL;
}


status_t
FileMap::_MakeSpace(size_t count)
{
	if (count <= CACHED_FILE_EXTENTS) {
		// just use the reserved area in the file_cache_ref structure
		if (fCount > CACHED_FILE_EXTENTS) {
			// the new size is smaller than the minimal array size
			file_extent *array = fIndirect.array;
			memcpy(fDirect, array, sizeof(file_extent) * count);
			free(array);
		}
	} else {
		// resize array if needed
		file_extent* oldArray = NULL;
		size_t maxCount = CACHED_FILE_EXTENTS;
		if (fCount > CACHED_FILE_EXTENTS) {
			oldArray = fIndirect.array;
			maxCount = fIndirect.max_count;
		}

		if (count > maxCount) {
			// allocate new array
			while (maxCount < count) {
				if (maxCount < 32768)
					maxCount <<= 1;
				else
					maxCount += 32768;
			}

			file_extent* newArray = (file_extent *)realloc(oldArray,
				maxCount * sizeof(file_extent));
			if (newArray == NULL)
				return B_NO_MEMORY;

			if (fCount > 0 && fCount <= CACHED_FILE_EXTENTS)
				memcpy(newArray, fDirect, sizeof(file_extent) * fCount);

			fIndirect.array = newArray;
			fIndirect.max_count = maxCount;
		}
	}

	fCount = count;
	return B_OK;
}


status_t
FileMap::_Add(file_io_vec* vecs, size_t vecCount, off_t& lastOffset)
{
	TRACE("FileMap@%p::Add(vecCount = %ld)\n", this, vecCount);

	uint32 start = fCount;
	off_t offset = 0;

	status_t status = _MakeSpace(fCount + vecCount);
	if (status != B_OK)
		return status;

	file_extent* lastExtent = NULL;
	if (start != 0) {
		lastExtent = ExtentAt(start - 1);
		offset = lastExtent->offset + lastExtent->disk.length;
	}

	for (uint32 i = 0; i < vecCount; i++) {
		if (lastExtent != NULL) {
			if (lastExtent->disk.offset + lastExtent->disk.length
					== vecs[i].offset
				|| (lastExtent->disk.offset == -1 && vecs[i].offset == -1)) {

				lastExtent->disk.length += vecs[i].length;
				offset += vecs[i].length;

				_MakeSpace(fCount - 1);
				if (fCount == CACHED_FILE_EXTENTS) {
					// We moved the indirect array into the direct one, making
					// lastExtent a stale pointer, re-get it.
					lastExtent = ExtentAt(start - 1);
				}

				continue;
			}
		}

		file_extent* extent = ExtentAt(start++);
		extent->offset = offset;
		extent->disk = vecs[i];

		offset += extent->disk.length;
		lastExtent = extent;
	}

#ifdef TRACE_FILE_MAP
	for (uint32 i = 0; i < fCount; i++) {
		file_extent* extent = ExtentAt(i);
		TRACE("[%ld] extent offset %lld, disk offset %lld, length %lld\n",
			i, extent->offset, extent->disk.offset, extent->disk.length);
	}
#endif

	lastOffset = offset;
	return B_OK;
}


void
FileMap::_InvalidateAfter(off_t offset)
{
	uint32 index;
	file_extent* extent = _FindExtent(offset, &index);
	if (extent != NULL) {
		uint32 resizeTo = index + 1;

		if (extent->offset + extent->disk.length > offset) {
			extent->disk.length = offset - extent->offset;
			if (extent->disk.length == 0)
				resizeTo = index;
		}

		_MakeSpace(resizeTo);
	}
}


/*!	Invalidates or removes the specified part of the file map.
*/
void
FileMap::Invalidate(off_t offset, off_t size)
{
	MutexLocker _(fLock);

	// TODO: honour size, we currently always remove everything after "offset"
	if (offset == 0) {
		_Free();
		return;
	}

	_InvalidateAfter(offset);
}


void
FileMap::SetSize(off_t size)
{
	MutexLocker _(fLock);

	if (size < fSize)
		_InvalidateAfter(size);

	fSize = size;
}


void
FileMap::_Free()
{
	if (fCount > CACHED_FILE_EXTENTS)
		free(fIndirect.array);

	fCount = 0;
}


status_t
FileMap::_Cache(off_t offset, off_t size)
{
	file_extent* lastExtent = NULL;
	if (fCount > 0)
		lastExtent = ExtentAt(fCount - 1);

	off_t mapEnd = 0;
	if (lastExtent != NULL)
		mapEnd = lastExtent->offset + lastExtent->disk.length;

	off_t end = offset + size;

	if (fCacheAll && mapEnd < end)
		return B_ERROR;

	status_t status = B_OK;
	file_io_vec vecs[8];
	const size_t kMaxVecs = 8;

	while (status == B_OK && mapEnd < end) {
		// We don't have the requested extents yet, retrieve them
		size_t vecCount = kMaxVecs;
		status = vfs_get_file_map(Vnode(), mapEnd, ~0UL, vecs, &vecCount);
		if (status == B_OK || status == B_BUFFER_OVERFLOW)
			status = _Add(vecs, vecCount, mapEnd);
	}

	return status;
}


status_t
FileMap::SetMode(uint32 mode)
{
	if (mode != FILE_MAP_CACHE_ALL && mode != FILE_MAP_CACHE_ON_DEMAND)
		return B_BAD_VALUE;

	MutexLocker _(fLock);

	if ((mode == FILE_MAP_CACHE_ALL && fCacheAll)
		|| (mode == FILE_MAP_CACHE_ON_DEMAND && !fCacheAll))
		return B_OK;

	if (mode == FILE_MAP_CACHE_ALL) {
		status_t status = _Cache(0, fSize);
		if (status != B_OK)
			return status;

		fCacheAll = true;
	} else
		fCacheAll = false;

	return B_OK;
}


status_t
FileMap::Translate(off_t offset, size_t size, file_io_vec* vecs, size_t* _count,
	size_t align)
{
	if (offset < 0)
		return B_BAD_VALUE;

	MutexLocker _(fLock);

	size_t maxVecs = *_count;
	size_t padLastVec = 0;

	if (offset >= Size()) {
		*_count = 0;
		return B_OK;
	}
	if ((off_t)(offset + size) > fSize) {
		if (align > 1) {
			off_t alignedSize = (fSize + align - 1) & ~(off_t)(align - 1);
			if ((off_t)(offset + size) >= alignedSize)
				padLastVec = alignedSize - fSize;
		}
		size = fSize - offset;
	}

	// First, we need to make sure that we have already cached all file
	// extents needed for this request.

	status_t status = _Cache(offset, size);
	if (status != B_OK)
		return status;

	// We now have cached the map of this file as far as we need it, now
	// we need to translate it for the requested access.

	uint32 index;
	file_extent* fileExtent = _FindExtent(offset, &index);

	offset -= fileExtent->offset;
	if (fileExtent->disk.offset != -1)
		vecs[0].offset = fileExtent->disk.offset + offset;
	else
		vecs[0].offset = -1;
	vecs[0].length = fileExtent->disk.length - offset;

	if (vecs[0].length >= (off_t)size) {
		vecs[0].length = size + padLastVec;
		*_count = 1;
		return B_OK;
	}

	// copy the rest of the vecs

	size -= vecs[0].length;
	uint32 vecIndex = 1;

	while (true) {
		fileExtent++;

		vecs[vecIndex++] = fileExtent->disk;

		if ((off_t)size <= fileExtent->disk.length) {
			vecs[vecIndex - 1].length = size + padLastVec;
			break;
		}

		if (vecIndex >= maxVecs) {
			*_count = vecIndex;
			return B_BUFFER_OVERFLOW;
		}

		size -= fileExtent->disk.length;
	}

	*_count = vecIndex;
	return B_OK;
}


//	#pragma mark -


#if DEBUG_FILE_MAP

static int
dump_file_map(int argc, char** argv)
{
	if (argc < 2) {
		print_debugger_command_usage(argv[0]);
		return 0;
	}

	bool printExtents = false;
	if (argc > 2 && !strcmp(argv[1], "-p"))
		printExtents = true;

	FileMap* map = (FileMap*)parse_expression(argv[argc - 1]);
	if (map == NULL) {
		kprintf("invalid file map!\n");
		return 0;
	}

	kprintf("FileMap %p\n", map);
	kprintf("  size    %" B_PRIdOFF "\n", map->Size());
	kprintf("  count   %lu\n", map->Count());

	if (!printExtents)
		return 0;

	for (uint32 i = 0; i < map->Count(); i++) {
		file_extent* extent = map->ExtentAt(i);

		kprintf("  [%" B_PRIu32 "] offset %" B_PRIdOFF ", disk offset %"
			B_PRIdOFF ", length %" B_PRIdOFF "\n", i, extent->offset,
			extent->disk.offset, extent->disk.length);
	}

	return 0;
}


static int
dump_file_map_stats(int argc, char** argv)
{
	off_t minSize = 0;
	off_t maxSize = -1;

	if (argc == 2) {
		maxSize = parse_expression(argv[1]);
	} else if (argc > 2) {
		minSize = parse_expression(argv[1]);
		maxSize = parse_expression(argv[2]);
	}

	FileMapList::Iterator iterator = sList.GetIterator();
	off_t size = 0;
	off_t mapSize = 0;
	uint32 extents = 0;
	uint32 count = 0;
	uint32 emptyCount = 0;

	while (iterator.HasNext()) {
		FileMap* map = iterator.Next();

		if (minSize > map->Size() || (maxSize != -1 && maxSize < map->Size()))
			continue;

		if (map->Count() != 0) {
			file_extent* extent = map->ExtentAt(map->Count() - 1);
			if (extent != NULL)
				mapSize += extent->offset + extent->disk.length;

			extents += map->Count();
		} else
			emptyCount++;

		size += map->Size();
		count++;
	}

	kprintf("%" B_PRId32 " file maps (%" B_PRIu32 " empty), %" B_PRIdOFF " file"
		" bytes in total, %" B_PRIdOFF " bytes cached, %" B_PRIu32 " extents\n",
		count, emptyCount, size, mapSize, extents);
	kprintf("average %" B_PRIu32 " extents per map for %" B_PRIdOFF " bytes.\n",
		extents / (count - emptyCount), mapSize / (count - emptyCount));

	return 0;
}

#endif	// DEBUG_FILE_MAP


//	#pragma mark - private kernel API


extern "C" status_t
file_map_init(void)
{
#if DEBUG_FILE_MAP
	add_debugger_command_etc("file_map", &dump_file_map,
		"Dumps the specified file map.",
		"[-p] <file-map>\n"
		"  -p          - causes the file extents to be printed as well.\n"
		"  <file-map>  - pointer to the file map.\n", 0);
	add_debugger_command("file_map_stats", &dump_file_map_stats,
		"Dumps some file map statistics.");

	mutex_init(&sLock, "file map list");
#endif
	return B_OK;
}


//	#pragma mark - public FS API


extern "C" void*
file_map_create(dev_t mountID, ino_t vnodeID, off_t size)
{
	TRACE("file_map_create(mountID = %ld, vnodeID = %lld, size = %lld)\n",
		mountID, vnodeID, size);

	// Get the vnode for the object
	// (note, this does not grab a reference to the node)
	struct vnode* vnode;
	if (vfs_lookup_vnode(mountID, vnodeID, &vnode) != B_OK)
		return NULL;

	return new(std::nothrow) FileMap(vnode, size);
}


extern "C" void
file_map_delete(void* _map)
{
	FileMap* map = (FileMap*)_map;
	if (map == NULL)
		return;

	TRACE("file_map_delete(map = %p)\n", map);
	delete map;
}


extern "C" void
file_map_set_size(void* _map, off_t size)
{
	FileMap* map = (FileMap*)_map;
	if (map == NULL)
		return;

	map->SetSize(size);
}


extern "C" void
file_map_invalidate(void* _map, off_t offset, off_t size)
{
	FileMap* map = (FileMap*)_map;
	if (map == NULL)
		return;

	map->Invalidate(offset, size);
}


extern "C" status_t
file_map_set_mode(void* _map, uint32 mode)
{
	FileMap* map = (FileMap*)_map;
	if (map == NULL)
		return B_BAD_VALUE;

	return map->SetMode(mode);
}


extern "C" status_t
file_map_translate(void* _map, off_t offset, size_t size, file_io_vec* vecs,
	size_t* _count, size_t align)
{
	TRACE("file_map_translate(map %p, offset %lld, size %ld)\n",
		_map, offset, size);

	FileMap* map = (FileMap*)_map;
	if (map == NULL)
		return B_BAD_VALUE;

	return map->Translate(offset, size, vecs, _count, align);
}