1/*
2 * Copyright 2004-2012, Axel D��rfler, axeld@pinc-software.de.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include <new>
8#include <stdlib.h>
9#include <string.h>
10
11#ifdef FS_SHELL
12#	include "vfs.h"
13#	include "fssh_api_wrapper.h"
14
15using namespace FSShell;
16#else
17#	include <unistd.h>
18
19#	include <KernelExport.h>
20#	include <fs_cache.h>
21
22#	include <condition_variable.h>
23#	include <file_cache.h>
24#	include <generic_syscall.h>
25#	include <util/AutoLock.h>
26#	include <util/DoublyLinkedList.h>
27#	include <vfs.h>
28#	include <vm/vm.h>
29#	include <vm/vm_page.h>
30#	include <vm/VMCache.h>
31
32#	include "kernel_debug_config.h"
33#endif
34
35
36//#define TRACE_FILE_MAP
37#ifdef TRACE_FILE_MAP
38#	define TRACE(x...) dprintf_no_syslog(x)
39#else
40#	define TRACE(x...) ;
41#endif
42
43// TODO: use a sparse array - eventually, the unused BlockMap would be something
44//	to reuse for this. We could also have an upperbound of memory consumption
45//	for the whole map.
46// TODO: it would be nice if we could free a file map in low memory situations.
47
48
49#define CACHED_FILE_EXTENTS	2
50	// must be smaller than MAX_FILE_IO_VECS
51	// TODO: find out how much of these are typically used
52
53struct file_extent {
54	off_t			offset;
55	file_io_vec		disk;
56};
57
58struct file_extent_array {
59	file_extent*	array;
60	size_t			max_count;
61};
62
63class FileMap
64#if DEBUG_FILE_MAP
65	: public DoublyLinkedListLinkImpl<FileMap>
66#endif
67{
68public:
69							FileMap(struct vnode* vnode, off_t size);
70							~FileMap();
71
72			void			Invalidate(off_t offset, off_t size);
73			void			SetSize(off_t size);
74
75			status_t		Translate(off_t offset, size_t size,
76								file_io_vec* vecs, size_t* _count,
77								size_t align);
78
79			file_extent*	ExtentAt(uint32 index);
80
81			size_t			Count() const { return fCount; }
82			struct vnode*	Vnode() const { return fVnode; }
83			off_t			Size() const { return fSize; }
84
85			status_t		SetMode(uint32 mode);
86
87private:
88			file_extent*	_FindExtent(off_t offset, uint32* _index);
89			status_t		_MakeSpace(size_t count);
90			status_t		_Add(file_io_vec* vecs, size_t vecCount,
91								off_t& lastOffset);
92			status_t		_Cache(off_t offset, off_t size);
93			void			_InvalidateAfter(off_t offset);
94			void			_Free();
95
96	union {
97		file_extent	fDirect[CACHED_FILE_EXTENTS];
98		file_extent_array fIndirect;
99	};
100	mutex			fLock;
101	size_t			fCount;
102	struct vnode*	fVnode;
103	off_t			fSize;
104	bool			fCacheAll;
105};
106
107#if DEBUG_FILE_MAP
108typedef DoublyLinkedList<FileMap> FileMapList;
109
110static FileMapList sList;
111static mutex sLock;
112#endif
113
114
115FileMap::FileMap(struct vnode* vnode, off_t size)
116	:
117	fCount(0),
118	fVnode(vnode),
119	fSize(size),
120	fCacheAll(false)
121{
122	mutex_init(&fLock, "file map");
123
124#if DEBUG_FILE_MAP
125	MutexLocker _(sLock);
126	sList.Add(this);
127#endif
128}
129
130
131FileMap::~FileMap()
132{
133	_Free();
134	mutex_destroy(&fLock);
135
136#if DEBUG_FILE_MAP
137	MutexLocker _(sLock);
138	sList.Remove(this);
139#endif
140}
141
142
143file_extent*
144FileMap::ExtentAt(uint32 index)
145{
146	if (index >= fCount)
147		return NULL;
148
149	if (fCount > CACHED_FILE_EXTENTS)
150		return &fIndirect.array[index];
151
152	return &fDirect[index];
153}
154
155
156file_extent*
157FileMap::_FindExtent(off_t offset, uint32 *_index)
158{
159	int32 left = 0;
160	int32 right = fCount - 1;
161
162	while (left <= right) {
163		int32 index = (left + right) / 2;
164		file_extent* extent = ExtentAt(index);
165
166		if (extent->offset > offset) {
167			// search in left part
168			right = index - 1;
169		} else if (extent->offset + extent->disk.length <= offset) {
170			// search in right part
171			left = index + 1;
172		} else {
173			// found extent
174			if (_index)
175				*_index = index;
176
177			return extent;
178		}
179	}
180
181	return NULL;
182}
183
184
185status_t
186FileMap::_MakeSpace(size_t count)
187{
188	if (count <= CACHED_FILE_EXTENTS) {
189		// just use the reserved area in the file_cache_ref structure
190		if (fCount > CACHED_FILE_EXTENTS) {
191			// the new size is smaller than the minimal array size
192			file_extent *array = fIndirect.array;
193			memcpy(fDirect, array, sizeof(file_extent) * count);
194			free(array);
195		}
196	} else {
197		// resize array if needed
198		file_extent* oldArray = NULL;
199		size_t maxCount = CACHED_FILE_EXTENTS;
200		if (fCount > CACHED_FILE_EXTENTS) {
201			oldArray = fIndirect.array;
202			maxCount = fIndirect.max_count;
203		}
204
205		if (count > maxCount) {
206			// allocate new array
207			while (maxCount < count) {
208				if (maxCount < 32768)
209					maxCount <<= 1;
210				else
211					maxCount += 32768;
212			}
213
214			file_extent* newArray = (file_extent *)realloc(oldArray,
215				maxCount * sizeof(file_extent));
216			if (newArray == NULL)
217				return B_NO_MEMORY;
218
219			if (fCount > 0 && fCount <= CACHED_FILE_EXTENTS)
220				memcpy(newArray, fDirect, sizeof(file_extent) * fCount);
221
222			fIndirect.array = newArray;
223			fIndirect.max_count = maxCount;
224		}
225	}
226
227	fCount = count;
228	return B_OK;
229}
230
231
232status_t
233FileMap::_Add(file_io_vec* vecs, size_t vecCount, off_t& lastOffset)
234{
235	TRACE("FileMap@%p::Add(vecCount = %ld)\n", this, vecCount);
236
237	uint32 start = fCount;
238	off_t offset = 0;
239
240	status_t status = _MakeSpace(fCount + vecCount);
241	if (status != B_OK)
242		return status;
243
244	file_extent* lastExtent = NULL;
245	if (start != 0) {
246		lastExtent = ExtentAt(start - 1);
247		offset = lastExtent->offset + lastExtent->disk.length;
248	}
249
250	for (uint32 i = 0; i < vecCount; i++) {
251		if (lastExtent != NULL) {
252			if (lastExtent->disk.offset + lastExtent->disk.length
253					== vecs[i].offset
254				|| (lastExtent->disk.offset == -1 && vecs[i].offset == -1)) {
255
256				lastExtent->disk.length += vecs[i].length;
257				offset += vecs[i].length;
258
259				_MakeSpace(fCount - 1);
260				if (fCount == CACHED_FILE_EXTENTS) {
261					// We moved the indirect array into the direct one, making
262					// lastExtent a stale pointer, re-get it.
263					lastExtent = ExtentAt(start - 1);
264				}
265
266				continue;
267			}
268		}
269
270		file_extent* extent = ExtentAt(start++);
271		extent->offset = offset;
272		extent->disk = vecs[i];
273
274		offset += extent->disk.length;
275		lastExtent = extent;
276	}
277
278#ifdef TRACE_FILE_MAP
279	for (uint32 i = 0; i < fCount; i++) {
280		file_extent* extent = ExtentAt(i);
281		TRACE("[%ld] extent offset %lld, disk offset %lld, length %lld\n",
282			i, extent->offset, extent->disk.offset, extent->disk.length);
283	}
284#endif
285
286	lastOffset = offset;
287	return B_OK;
288}
289
290
291void
292FileMap::_InvalidateAfter(off_t offset)
293{
294	uint32 index;
295	file_extent* extent = _FindExtent(offset, &index);
296	if (extent != NULL) {
297		uint32 resizeTo = index + 1;
298
299		if (extent->offset + extent->disk.length > offset) {
300			extent->disk.length = offset - extent->offset;
301			if (extent->disk.length == 0)
302				resizeTo = index;
303		}
304
305		_MakeSpace(resizeTo);
306	}
307}
308
309
310/*!	Invalidates or removes the specified part of the file map.
311*/
312void
313FileMap::Invalidate(off_t offset, off_t size)
314{
315	MutexLocker _(fLock);
316
317	// TODO: honour size, we currently always remove everything after "offset"
318	if (offset == 0) {
319		_Free();
320		return;
321	}
322
323	_InvalidateAfter(offset);
324}
325
326
327void
328FileMap::SetSize(off_t size)
329{
330	MutexLocker _(fLock);
331
332	if (size < fSize)
333		_InvalidateAfter(size);
334
335	fSize = size;
336}
337
338
339void
340FileMap::_Free()
341{
342	if (fCount > CACHED_FILE_EXTENTS)
343		free(fIndirect.array);
344
345	fCount = 0;
346}
347
348
349status_t
350FileMap::_Cache(off_t offset, off_t size)
351{
352	file_extent* lastExtent = NULL;
353	if (fCount > 0)
354		lastExtent = ExtentAt(fCount - 1);
355
356	off_t mapEnd = 0;
357	if (lastExtent != NULL)
358		mapEnd = lastExtent->offset + lastExtent->disk.length;
359
360	off_t end = offset + size;
361
362	if (fCacheAll && mapEnd < end)
363		return B_ERROR;
364
365	status_t status = B_OK;
366	file_io_vec vecs[8];
367	const size_t kMaxVecs = 8;
368
369	while (status == B_OK && mapEnd < end) {
370		// We don't have the requested extents yet, retrieve them
371		size_t vecCount = kMaxVecs;
372		status = vfs_get_file_map(Vnode(), mapEnd, ~0UL, vecs, &vecCount);
373		if (status == B_OK || status == B_BUFFER_OVERFLOW)
374			status = _Add(vecs, vecCount, mapEnd);
375	}
376
377	return status;
378}
379
380
381status_t
382FileMap::SetMode(uint32 mode)
383{
384	if (mode != FILE_MAP_CACHE_ALL && mode != FILE_MAP_CACHE_ON_DEMAND)
385		return B_BAD_VALUE;
386
387	MutexLocker _(fLock);
388
389	if ((mode == FILE_MAP_CACHE_ALL && fCacheAll)
390		|| (mode == FILE_MAP_CACHE_ON_DEMAND && !fCacheAll))
391		return B_OK;
392
393	if (mode == FILE_MAP_CACHE_ALL) {
394		status_t status = _Cache(0, fSize);
395		if (status != B_OK)
396			return status;
397
398		fCacheAll = true;
399	} else
400		fCacheAll = false;
401
402	return B_OK;
403}
404
405
406status_t
407FileMap::Translate(off_t offset, size_t size, file_io_vec* vecs, size_t* _count,
408	size_t align)
409{
410	if (offset < 0)
411		return B_BAD_VALUE;
412
413	MutexLocker _(fLock);
414
415	size_t maxVecs = *_count;
416	size_t padLastVec = 0;
417
418	if (offset >= Size()) {
419		*_count = 0;
420		return B_OK;
421	}
422	if ((off_t)(offset + size) > fSize) {
423		if (align > 1) {
424			off_t alignedSize = (fSize + align - 1) & ~(off_t)(align - 1);
425			if ((off_t)(offset + size) >= alignedSize)
426				padLastVec = alignedSize - fSize;
427		}
428		size = fSize - offset;
429	}
430
431	// First, we need to make sure that we have already cached all file
432	// extents needed for this request.
433
434	status_t status = _Cache(offset, size);
435	if (status != B_OK)
436		return status;
437
438	// We now have cached the map of this file as far as we need it, now
439	// we need to translate it for the requested access.
440
441	uint32 index;
442	file_extent* fileExtent = _FindExtent(offset, &index);
443
444	offset -= fileExtent->offset;
445	if (fileExtent->disk.offset != -1)
446		vecs[0].offset = fileExtent->disk.offset + offset;
447	else
448		vecs[0].offset = -1;
449	vecs[0].length = fileExtent->disk.length - offset;
450
451	if (vecs[0].length >= (off_t)size) {
452		vecs[0].length = size + padLastVec;
453		*_count = 1;
454		return B_OK;
455	}
456
457	// copy the rest of the vecs
458
459	size -= vecs[0].length;
460	uint32 vecIndex = 1;
461
462	while (true) {
463		fileExtent++;
464
465		vecs[vecIndex++] = fileExtent->disk;
466
467		if ((off_t)size <= fileExtent->disk.length) {
468			vecs[vecIndex - 1].length = size + padLastVec;
469			break;
470		}
471
472		if (vecIndex >= maxVecs) {
473			*_count = vecIndex;
474			return B_BUFFER_OVERFLOW;
475		}
476
477		size -= fileExtent->disk.length;
478	}
479
480	*_count = vecIndex;
481	return B_OK;
482}
483
484
485//	#pragma mark -
486
487
488#if DEBUG_FILE_MAP
489
490static int
491dump_file_map(int argc, char** argv)
492{
493	if (argc < 2) {
494		print_debugger_command_usage(argv[0]);
495		return 0;
496	}
497
498	bool printExtents = false;
499	if (argc > 2 && !strcmp(argv[1], "-p"))
500		printExtents = true;
501
502	FileMap* map = (FileMap*)parse_expression(argv[argc - 1]);
503	if (map == NULL) {
504		kprintf("invalid file map!\n");
505		return 0;
506	}
507
508	kprintf("FileMap %p\n", map);
509	kprintf("  size    %" B_PRIdOFF "\n", map->Size());
510	kprintf("  count   %lu\n", map->Count());
511
512	if (!printExtents)
513		return 0;
514
515	for (uint32 i = 0; i < map->Count(); i++) {
516		file_extent* extent = map->ExtentAt(i);
517
518		kprintf("  [%" B_PRIu32 "] offset %" B_PRIdOFF ", disk offset %"
519			B_PRIdOFF ", length %" B_PRIdOFF "\n", i, extent->offset,
520			extent->disk.offset, extent->disk.length);
521	}
522
523	return 0;
524}
525
526
527static int
528dump_file_map_stats(int argc, char** argv)
529{
530	off_t minSize = 0;
531	off_t maxSize = -1;
532
533	if (argc == 2) {
534		maxSize = parse_expression(argv[1]);
535	} else if (argc > 2) {
536		minSize = parse_expression(argv[1]);
537		maxSize = parse_expression(argv[2]);
538	}
539
540	FileMapList::Iterator iterator = sList.GetIterator();
541	off_t size = 0;
542	off_t mapSize = 0;
543	uint32 extents = 0;
544	uint32 count = 0;
545	uint32 emptyCount = 0;
546
547	while (iterator.HasNext()) {
548		FileMap* map = iterator.Next();
549
550		if (minSize > map->Size() || (maxSize != -1 && maxSize < map->Size()))
551			continue;
552
553		if (map->Count() != 0) {
554			file_extent* extent = map->ExtentAt(map->Count() - 1);
555			if (extent != NULL)
556				mapSize += extent->offset + extent->disk.length;
557
558			extents += map->Count();
559		} else
560			emptyCount++;
561
562		size += map->Size();
563		count++;
564	}
565
566	kprintf("%" B_PRId32 " file maps (%" B_PRIu32 " empty), %" B_PRIdOFF " file"
567		" bytes in total, %" B_PRIdOFF " bytes cached, %" B_PRIu32 " extents\n",
568		count, emptyCount, size, mapSize, extents);
569	kprintf("average %" B_PRIu32 " extents per map for %" B_PRIdOFF " bytes.\n",
570		extents / (count - emptyCount), mapSize / (count - emptyCount));
571
572	return 0;
573}
574
575#endif	// DEBUG_FILE_MAP
576
577
578//	#pragma mark - private kernel API
579
580
581extern "C" status_t
582file_map_init(void)
583{
584#if DEBUG_FILE_MAP
585	add_debugger_command_etc("file_map", &dump_file_map,
586		"Dumps the specified file map.",
587		"[-p] <file-map>\n"
588		"  -p          - causes the file extents to be printed as well.\n"
589		"  <file-map>  - pointer to the file map.\n", 0);
590	add_debugger_command("file_map_stats", &dump_file_map_stats,
591		"Dumps some file map statistics.");
592
593	mutex_init(&sLock, "file map list");
594#endif
595	return B_OK;
596}
597
598
599//	#pragma mark - public FS API
600
601
602extern "C" void*
603file_map_create(dev_t mountID, ino_t vnodeID, off_t size)
604{
605	TRACE("file_map_create(mountID = %ld, vnodeID = %lld, size = %lld)\n",
606		mountID, vnodeID, size);
607
608	// Get the vnode for the object
609	// (note, this does not grab a reference to the node)
610	struct vnode* vnode;
611	if (vfs_lookup_vnode(mountID, vnodeID, &vnode) != B_OK)
612		return NULL;
613
614	return new(std::nothrow) FileMap(vnode, size);
615}
616
617
618extern "C" void
619file_map_delete(void* _map)
620{
621	FileMap* map = (FileMap*)_map;
622	if (map == NULL)
623		return;
624
625	TRACE("file_map_delete(map = %p)\n", map);
626	delete map;
627}
628
629
630extern "C" void
631file_map_set_size(void* _map, off_t size)
632{
633	FileMap* map = (FileMap*)_map;
634	if (map == NULL)
635		return;
636
637	map->SetSize(size);
638}
639
640
641extern "C" void
642file_map_invalidate(void* _map, off_t offset, off_t size)
643{
644	FileMap* map = (FileMap*)_map;
645	if (map == NULL)
646		return;
647
648	map->Invalidate(offset, size);
649}
650
651
652extern "C" status_t
653file_map_set_mode(void* _map, uint32 mode)
654{
655	FileMap* map = (FileMap*)_map;
656	if (map == NULL)
657		return B_BAD_VALUE;
658
659	return map->SetMode(mode);
660}
661
662
663extern "C" status_t
664file_map_translate(void* _map, off_t offset, size_t size, file_io_vec* vecs,
665	size_t* _count, size_t align)
666{
667	TRACE("file_map_translate(map %p, offset %lld, size %ld)\n",
668		_map, offset, size);
669
670	FileMap* map = (FileMap*)_map;
671	if (map == NULL)
672		return B_BAD_VALUE;
673
674	return map->Translate(offset, size, vecs, _count, align);
675}
676
677