1/*
2 * Copyright 2010-2014, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include "CachedDataReader.h"
8
9#include <algorithm>
10
11#include <DataIO.h>
12
13#include <util/AutoLock.h>
14#include <vm/VMCache.h>
15#include <vm/vm_page.h>
16
17#include "DebugSupport.h"
18
19
20using BPackageKit::BHPKG::BBufferDataReader;
21
22
23static inline bool
24page_physical_number_less(const vm_page* a, const vm_page* b)
25{
26	return a->physical_page_number < b->physical_page_number;
27}
28
29
30// #pragma mark - PagesDataOutput
31
32
33struct CachedDataReader::PagesDataOutput : public BDataIO {
34	PagesDataOutput(vm_page** pages, size_t pageCount)
35		:
36		fPages(pages),
37		fPageCount(pageCount),
38		fInPageOffset(0)
39	{
40	}
41
42	virtual ssize_t Write(const void* buffer, size_t size)
43	{
44		size_t bytesRemaining = size;
45		while (bytesRemaining > 0) {
46			if (fPageCount == 0)
47				return B_BAD_VALUE;
48
49			size_t toCopy = std::min(bytesRemaining,
50				B_PAGE_SIZE - fInPageOffset);
51			status_t error = vm_memcpy_to_physical(
52				fPages[0]->physical_page_number * B_PAGE_SIZE + fInPageOffset,
53				buffer, toCopy, false);
54			if (error != B_OK)
55				return error;
56
57			fInPageOffset += toCopy;
58			if (fInPageOffset == B_PAGE_SIZE) {
59				fInPageOffset = 0;
60				fPages++;
61				fPageCount--;
62			}
63
64			buffer = (const char*)buffer + toCopy;
65			bytesRemaining -= toCopy;
66		}
67
68		return size;
69	}
70
71private:
72	vm_page**	fPages;
73	size_t		fPageCount;
74	size_t		fInPageOffset;
75};
76
77
78// #pragma mark - CachedDataReader
79
80
81CachedDataReader::CachedDataReader()
82	:
83	fReader(NULL),
84	fCache(NULL),
85	fCacheLineLockers()
86{
87	mutex_init(&fLock, "packagefs cached reader");
88}
89
90
91CachedDataReader::~CachedDataReader()
92{
93	if (fCache != NULL) {
94		fCache->Lock();
95		fCache->ReleaseRefAndUnlock();
96	}
97
98	mutex_destroy(&fLock);
99}
100
101
102status_t
103CachedDataReader::Init(BAbstractBufferedDataReader* reader, off_t size)
104{
105	fReader = reader;
106
107	status_t error = fCacheLineLockers.Init();
108	if (error != B_OK)
109		RETURN_ERROR(error);
110
111	error = VMCacheFactory::CreateNullCache(VM_PRIORITY_SYSTEM,
112		fCache);
113	if (error != B_OK)
114		RETURN_ERROR(error);
115
116	AutoLocker<VMCache> locker(fCache);
117
118	error = fCache->Resize(size, VM_PRIORITY_SYSTEM);
119	if (error != B_OK)
120		RETURN_ERROR(error);
121
122	return B_OK;
123}
124
125
126status_t
127CachedDataReader::ReadDataToOutput(off_t offset, size_t size,
128	BDataIO* output)
129{
130	if (offset > fCache->virtual_end
131		|| (off_t)size > fCache->virtual_end - offset) {
132		return B_BAD_VALUE;
133	}
134
135	if (size == 0)
136		return B_OK;
137
138	while (size > 0) {
139		// the start of the current cache line
140		off_t lineOffset = (offset / kCacheLineSize) * kCacheLineSize;
141
142		// intersection of request and cache line
143		off_t cacheLineEnd = std::min(lineOffset + (off_t)kCacheLineSize,
144			fCache->virtual_end);
145		size_t requestLineLength
146			= std::min(cacheLineEnd - offset, (off_t)size);
147
148		// transfer the data of the cache line
149		status_t error = _ReadCacheLine(lineOffset, cacheLineEnd - lineOffset,
150			offset, requestLineLength, output);
151		if (error != B_OK)
152			return error;
153
154		offset = cacheLineEnd;
155		size -= requestLineLength;
156	}
157
158	return B_OK;
159}
160
161
162status_t
163CachedDataReader::_ReadCacheLine(off_t lineOffset, size_t lineSize,
164	off_t requestOffset, size_t requestLength, BDataIO* output)
165{
166	PRINT("CachedDataReader::_ReadCacheLine(%" B_PRIdOFF ", %zu, %" B_PRIdOFF
167		", %zu, %p\n", lineOffset, lineSize, requestOffset, requestLength,
168		output);
169
170	CacheLineLocker cacheLineLocker(this, lineOffset);
171
172	// check whether there are pages of the cache line and the mark them used
173	page_num_t firstPageOffset = lineOffset / B_PAGE_SIZE;
174	page_num_t linePageCount = (lineSize + B_PAGE_SIZE - 1) / B_PAGE_SIZE;
175	vm_page* pages[kPagesPerCacheLine] = {};
176
177	AutoLocker<VMCache> cacheLocker(fCache);
178
179	page_num_t firstMissing = 0;
180	page_num_t lastMissing = 0;
181	page_num_t missingPages = 0;
182	page_num_t pageOffset = firstPageOffset;
183
184	VMCachePagesTree::Iterator it = fCache->pages.GetIterator(pageOffset, true,
185		true);
186	while (pageOffset < firstPageOffset + linePageCount) {
187		vm_page* page = it.Next();
188		page_num_t currentPageOffset;
189		if (page == NULL
190			|| page->cache_offset >= firstPageOffset + linePageCount) {
191			page = NULL;
192			currentPageOffset = firstPageOffset + linePageCount;
193		} else
194			currentPageOffset = page->cache_offset;
195
196		if (pageOffset < currentPageOffset) {
197			// pages are missing
198			if (missingPages == 0)
199				firstMissing = pageOffset;
200			lastMissing = currentPageOffset - 1;
201			missingPages += currentPageOffset - pageOffset;
202
203			for (; pageOffset < currentPageOffset; pageOffset++)
204				pages[pageOffset - firstPageOffset] = NULL;
205		}
206
207		if (page != NULL) {
208			pages[pageOffset++ - firstPageOffset] = page;
209			DEBUG_PAGE_ACCESS_START(page);
210			vm_page_set_state(page, PAGE_STATE_UNUSED);
211			DEBUG_PAGE_ACCESS_END(page);
212		}
213	}
214
215	cacheLocker.Unlock();
216
217	if (missingPages > 0) {
218// TODO: If the missing pages range doesn't intersect with the request, just
219// satisfy the request and don't read anything at all.
220		// There are pages of the cache line missing. We have to allocate fresh
221		// ones.
222
223		// reserve
224		vm_page_reservation reservation;
225		if (!vm_page_try_reserve_pages(&reservation, missingPages,
226				VM_PRIORITY_SYSTEM)) {
227			_DiscardPages(pages, firstMissing - firstPageOffset, missingPages);
228
229			// fall back to uncached transfer
230			return fReader->ReadDataToOutput(requestOffset, requestLength,
231				output);
232		}
233
234		// Allocate the missing pages and remove the already existing pages in
235		// the range from the cache. We're going to read/write the whole range
236		// anyway.
237		for (pageOffset = firstMissing; pageOffset <= lastMissing;
238				pageOffset++) {
239			page_num_t index = pageOffset - firstPageOffset;
240			if (pages[index] == NULL) {
241				pages[index] = vm_page_allocate_page(&reservation,
242					PAGE_STATE_UNUSED);
243				DEBUG_PAGE_ACCESS_END(pages[index]);
244			} else {
245				cacheLocker.Lock();
246				fCache->RemovePage(pages[index]);
247				cacheLocker.Unlock();
248			}
249		}
250
251		missingPages = lastMissing - firstMissing + 1;
252
253		// add the pages to the cache
254		cacheLocker.Lock();
255
256		for (pageOffset = firstMissing; pageOffset <= lastMissing;
257				pageOffset++) {
258			page_num_t index = pageOffset - firstPageOffset;
259			fCache->InsertPage(pages[index], (off_t)pageOffset * B_PAGE_SIZE);
260		}
261
262		cacheLocker.Unlock();
263
264		// read in the missing pages
265		status_t error = _ReadIntoPages(pages, firstMissing - firstPageOffset,
266			missingPages);
267		if (error != B_OK) {
268			ERROR("CachedDataReader::_ReadCacheLine(): Failed to read into "
269				"cache (offset: %" B_PRIdOFF ", length: %" B_PRIuSIZE "), "
270				"trying uncached read (offset: %" B_PRIdOFF ", length: %"
271				B_PRIuSIZE ")\n", (off_t)firstMissing * B_PAGE_SIZE,
272				(size_t)missingPages * B_PAGE_SIZE, requestOffset,
273				requestLength);
274
275			_DiscardPages(pages, firstMissing - firstPageOffset, missingPages);
276
277			// Try again using an uncached transfer
278			return fReader->ReadDataToOutput(requestOffset, requestLength,
279				output);
280		}
281	}
282
283	// write data to output
284	status_t error = _WritePages(pages, requestOffset - lineOffset,
285		requestLength, output);
286	_CachePages(pages, 0, linePageCount);
287	return error;
288}
289
290
291/*!	Frees all pages in given range of the \a pages array.
292	\c NULL entries in the range are OK. All non \c NULL entries must refer
293	to pages with \c PAGE_STATE_UNUSED. The pages may belong to \c fCache or
294	may not have a cache.
295	\c fCache must not be locked.
296*/
297void
298CachedDataReader::_DiscardPages(vm_page** pages, size_t firstPage,
299	size_t pageCount)
300{
301	PRINT("%p->CachedDataReader::_DiscardPages(%" B_PRIuSIZE ", %" B_PRIuSIZE
302		")\n", this, firstPage, pageCount);
303
304	AutoLocker<VMCache> cacheLocker(fCache);
305
306	for (size_t i = firstPage; i < firstPage + pageCount; i++) {
307		vm_page* page = pages[i];
308		if (page == NULL)
309			continue;
310
311		DEBUG_PAGE_ACCESS_START(page);
312
313		ASSERT_PRINT(page->State() == PAGE_STATE_UNUSED,
314			"page: %p @! page -m %p", page, page);
315
316		if (page->Cache() != NULL)
317			fCache->RemovePage(page);
318
319		vm_page_free(NULL, page);
320	}
321}
322
323
324/*!	Marks all pages in the given range of the \a pages array cached.
325	There must not be any \c NULL entries in the given array range. All pages
326	must belong to \c cache and have state \c PAGE_STATE_UNUSED.
327	\c fCache must not be locked.
328*/
329void
330CachedDataReader::_CachePages(vm_page** pages, size_t firstPage,
331	size_t pageCount)
332{
333	PRINT("%p->CachedDataReader::_CachePages(%" B_PRIuSIZE ", %" B_PRIuSIZE
334		")\n", this, firstPage, pageCount);
335
336	AutoLocker<VMCache> cacheLocker(fCache);
337
338	for (size_t i = firstPage; i < firstPage + pageCount; i++) {
339		vm_page* page = pages[i];
340		ASSERT(page != NULL);
341		ASSERT_PRINT(page->State() == PAGE_STATE_UNUSED
342				&& page->Cache() == fCache,
343			"page: %p @! page -m %p", page, page);
344
345		DEBUG_PAGE_ACCESS_START(page);
346		vm_page_set_state(page, PAGE_STATE_CACHED);
347		DEBUG_PAGE_ACCESS_END(page);
348	}
349}
350
351
352/*!	Writes the contents of pages in \c pages to \a output.
353	\param pages The pages array.
354	\param pagesRelativeOffset The offset relative to \a pages[0] where to
355		start writing from.
356	\param requestLength The number of bytes to write.
357	\param output The output to which the data shall be written.
358	\return \c B_OK, if writing went fine, another error code otherwise.
359*/
360status_t
361CachedDataReader::_WritePages(vm_page** pages, size_t pagesRelativeOffset,
362	size_t requestLength, BDataIO* output)
363{
364	PRINT("%p->CachedDataReader::_WritePages(%" B_PRIuSIZE ", %" B_PRIuSIZE
365		", %p)\n", this, pagesRelativeOffset, requestLength, output);
366
367	size_t firstPage = pagesRelativeOffset / B_PAGE_SIZE;
368	size_t endPage = (pagesRelativeOffset + requestLength + B_PAGE_SIZE - 1)
369		/ B_PAGE_SIZE;
370
371	// fallback to copying individual pages
372	size_t inPageOffset = pagesRelativeOffset % B_PAGE_SIZE;
373	for (size_t i = firstPage; i < endPage; i++) {
374		// map the page
375		void* handle;
376		addr_t address;
377		status_t error = vm_get_physical_page(
378			pages[i]->physical_page_number * B_PAGE_SIZE, &address,
379			&handle);
380		if (error != B_OK)
381			return error;
382
383		// write the page's data
384		size_t toCopy = std::min(B_PAGE_SIZE - inPageOffset, requestLength);
385		error = output->WriteExactly((uint8*)(address + inPageOffset), toCopy);
386
387		// unmap the page
388		vm_put_physical_page(address, handle);
389
390		if (error != B_OK)
391			return error;
392
393		inPageOffset = 0;
394		requestLength -= toCopy;
395	}
396
397	return B_OK;
398}
399
400
401status_t
402CachedDataReader::_ReadIntoPages(vm_page** pages, size_t firstPage,
403	size_t pageCount)
404{
405	PagesDataOutput output(pages + firstPage, pageCount);
406
407	off_t firstPageOffset = (off_t)pages[firstPage]->cache_offset
408		* B_PAGE_SIZE;
409	generic_size_t requestLength = std::min(
410			firstPageOffset + (off_t)pageCount * B_PAGE_SIZE,
411			fCache->virtual_end)
412		- firstPageOffset;
413
414	return fReader->ReadDataToOutput(firstPageOffset, requestLength, &output);
415}
416
417
418void
419CachedDataReader::_LockCacheLine(CacheLineLocker* lineLocker)
420{
421	MutexLocker locker(fLock);
422
423	CacheLineLocker* otherLineLocker
424		= fCacheLineLockers.Lookup(lineLocker->Offset());
425	if (otherLineLocker == NULL) {
426		fCacheLineLockers.Insert(lineLocker);
427		return;
428	}
429
430	// queue and wait
431	otherLineLocker->Queue().Add(lineLocker);
432	lineLocker->Wait(fLock);
433}
434
435
436void
437CachedDataReader::_UnlockCacheLine(CacheLineLocker* lineLocker)
438{
439	MutexLocker locker(fLock);
440
441	fCacheLineLockers.Remove(lineLocker);
442
443	if (CacheLineLocker* nextLineLocker = lineLocker->Queue().RemoveHead()) {
444		nextLineLocker->Queue().MoveFrom(&lineLocker->Queue());
445		fCacheLineLockers.Insert(nextLineLocker);
446		nextLineLocker->WakeUp();
447	}
448}
449