1/*-------------------------------------------------------------------------
2 * Vulkan CTS Framework
3 * --------------------
4 *
5 * Copyright (c) 2015 Google Inc.
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 *      http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 *
19 *//*!
20 * \file
21 * \brief Program binary registry.
22 *//*--------------------------------------------------------------------*/
23
24#include "vkBinaryRegistry.hpp"
25#include "tcuResource.hpp"
26#include "tcuFormatUtil.hpp"
27#include "deFilePath.hpp"
28#include "deStringUtil.hpp"
29#include "deDirectoryIterator.hpp"
30#include "deString.h"
31#include "deInt32.h"
32#include "deFile.h"
33
34#include <sstream>
35#include <fstream>
36#include <stdexcept>
37#include <limits>
38
39namespace vk
40{
41namespace BinaryRegistryDetail
42{
43
44using std::string;
45using std::vector;
46
47namespace
48{
49
50string getProgramFileName (deUint32 index)
51{
52	return de::toString(tcu::toHex(index)) + ".spv";
53}
54
55string getProgramPath (const std::string& dirName, deUint32 index)
56{
57	return de::FilePath::join(dirName, getProgramFileName(index)).getPath();
58}
59
60bool isHexChr (char c)
61{
62	return de::inRange(c, '0', '9') || de::inRange(c, 'a', 'f') || de::inRange(c, 'A', 'F');
63}
64
65bool isProgramFileName (const std::string& name)
66{
67	// 0x + 00000000 + .spv
68	if (name.length() != (2 + 8 + 4))
69		return false;
70
71	if (name[0] != '0' ||
72		name[1] != 'x' ||
73		name[10] != '.' ||
74		name[11] != 's' ||
75		name[12] != 'p' ||
76		name[13] != 'v')
77		return false;
78
79	for (size_t ndx = 2; ndx < 10; ++ndx)
80	{
81		if (!isHexChr(name[ndx]))
82			return false;
83	}
84
85	return true;
86}
87
88deUint32 getProgramIndexFromName (const std::string& name)
89{
90	DE_ASSERT(isProgramFileName(name));
91
92	deUint32			index	= ~0u;
93	std::stringstream	str;
94
95	str << std::hex << name.substr(2,10);
96	str >> index;
97
98	DE_ASSERT(getProgramFileName(index) == name);
99
100	return index;
101}
102
103string getIndexPath (const std::string& dirName)
104{
105	return de::FilePath::join(dirName, "index.bin").getPath();
106}
107
108void writeBinary (const ProgramBinary& binary, const std::string& dstPath)
109{
110	const de::FilePath	filePath(dstPath);
111
112	if (!de::FilePath(filePath.getDirName()).exists())
113		de::createDirectoryAndParents(filePath.getDirName().c_str());
114
115	{
116		std::ofstream	out		(dstPath.c_str(), std::ios_base::binary);
117
118		if (!out.is_open() || !out.good())
119			throw tcu::Exception("Failed to open " + dstPath);
120
121		out.write((const char*)binary.getBinary(), binary.getSize());
122		out.close();
123	}
124}
125
126void writeBinary (const std::string& dstDir, deUint32 index, const ProgramBinary& binary)
127{
128	writeBinary(binary, getProgramPath(dstDir, index));
129}
130
131ProgramBinary* readBinary (const std::string& srcPath)
132{
133	std::ifstream	in		(srcPath.c_str(), std::ios::binary | std::ios::ate);
134	const size_t	size	= (size_t)in.tellg();
135
136	if (!in.is_open() || !in.good())
137		throw tcu::Exception("Failed to open " + srcPath);
138
139	if (size == 0)
140		throw tcu::Exception("Malformed binary, size = 0");
141
142	in.seekg(0, std::ios::beg);
143
144	{
145		std::vector<deUint8>	bytes	(size);
146
147		in.read((char*)&bytes[0], size);
148		DE_ASSERT(bytes[0] != 0);
149
150		return new ProgramBinary(vk::PROGRAM_FORMAT_SPIRV, bytes.size(), &bytes[0]);
151	}
152}
153
154deUint32 binaryHash (const ProgramBinary* binary)
155{
156	return deMemoryHash(binary->getBinary(), binary->getSize());
157}
158
159deBool binaryEqual (const ProgramBinary* a, const ProgramBinary* b)
160{
161	if (a->getSize() == b->getSize())
162		return deMemoryEqual(a->getBinary(), b->getBinary(), a->getSize());
163	else
164		return DE_FALSE;
165}
166
167std::vector<deUint32> getSearchPath (const ProgramIdentifier& id)
168{
169	const std::string	combinedStr		= id.testCasePath + '#' + id.programName;
170	const size_t		strLen			= combinedStr.size();
171	const size_t		numWords		= strLen/4 + 1;		// Must always end up with at least one 0 byte
172	vector<deUint32>	words			(numWords, 0u);
173
174	deMemcpy(&words[0], combinedStr.c_str(), strLen);
175
176	return words;
177}
178
179const deUint32* findBinaryIndex (BinaryIndexAccess* index, const ProgramIdentifier& id)
180{
181	const vector<deUint32>	words	= getSearchPath(id);
182	size_t					nodeNdx	= 0;
183	size_t					wordNdx	= 0;
184
185	for (;;)
186	{
187		const BinaryIndexNode&	curNode	= (*index)[nodeNdx];
188
189		if (curNode.word == words[wordNdx])
190		{
191			if (wordNdx+1 < words.size())
192			{
193				TCU_CHECK_INTERNAL((size_t)curNode.index < index->size());
194
195				nodeNdx  = curNode.index;
196				wordNdx	+= 1;
197			}
198			else if (wordNdx+1 == words.size())
199				return &curNode.index;
200			else
201				return DE_NULL;
202		}
203		else if (curNode.word != 0)
204		{
205			nodeNdx += 1;
206
207			// Index should always be null-terminated
208			TCU_CHECK_INTERNAL(nodeNdx < index->size());
209		}
210		else
211			return DE_NULL;
212	}
213
214	return DE_NULL;
215}
216
217//! Sparse index node used for final binary index construction
218struct SparseIndexNode
219{
220	deUint32						word;
221	deUint32						index;
222	std::vector<SparseIndexNode*>	children;
223
224	SparseIndexNode (deUint32 word_, deUint32 index_)
225		: word	(word_)
226		, index	(index_)
227	{}
228
229	SparseIndexNode (void)
230		: word	(0)
231		, index	(0)
232	{}
233
234	~SparseIndexNode (void)
235	{
236		for (size_t ndx = 0; ndx < children.size(); ndx++)
237			delete children[ndx];
238	}
239};
240
241#if defined(DE_DEBUG)
242bool isNullByteTerminated (deUint32 word)
243{
244	deUint8 bytes[4];
245	deMemcpy(bytes, &word, sizeof(word));
246	return bytes[3] == 0;
247}
248#endif
249
250void addToSparseIndex (SparseIndexNode* group, const deUint32* words, size_t numWords, deUint32 index)
251{
252	const deUint32		curWord	= words[0];
253	SparseIndexNode*	child	= DE_NULL;
254
255	for (size_t childNdx = 0; childNdx < group->children.size(); childNdx++)
256	{
257		if (group->children[childNdx]->word == curWord)
258		{
259			child = group->children[childNdx];
260			break;
261		}
262	}
263
264	DE_ASSERT(numWords > 1 || !child);
265
266	if (!child)
267	{
268		group->children.reserve(group->children.size()+1);
269		group->children.push_back(new SparseIndexNode(curWord, numWords == 1 ? index : 0));
270
271		child = group->children.back();
272	}
273
274	if (numWords > 1)
275		addToSparseIndex(child, words+1, numWords-1, index);
276	else
277		DE_ASSERT(isNullByteTerminated(curWord));
278}
279
280// Prepares sparse index for finalization. Ensures that child with word = 0 is moved
281// to the end, or one is added if there is no such child already.
282void normalizeSparseIndex (SparseIndexNode* group)
283{
284	int		zeroChildPos	= -1;
285
286	for (size_t childNdx = 0; childNdx < group->children.size(); childNdx++)
287	{
288		normalizeSparseIndex(group->children[childNdx]);
289
290		if (group->children[childNdx]->word == 0)
291		{
292			DE_ASSERT(zeroChildPos < 0);
293			zeroChildPos = (int)childNdx;
294		}
295	}
296
297	if (zeroChildPos >= 0)
298	{
299		// Move child with word = 0 to last
300		while (zeroChildPos != (int)group->children.size()-1)
301		{
302			std::swap(group->children[zeroChildPos], group->children[zeroChildPos+1]);
303			zeroChildPos += 1;
304		}
305	}
306	else if (!group->children.empty())
307	{
308		group->children.reserve(group->children.size()+1);
309		group->children.push_back(new SparseIndexNode(0, 0));
310	}
311}
312
313deUint32 getIndexSize (const SparseIndexNode* group)
314{
315	size_t	numNodes	= group->children.size();
316
317	for (size_t childNdx = 0; childNdx < group->children.size(); childNdx++)
318		numNodes += getIndexSize(group->children[childNdx]);
319
320	DE_ASSERT(numNodes <= std::numeric_limits<deUint32>::max());
321
322	return (deUint32)numNodes;
323}
324
325deUint32 addAndCountNodes (BinaryIndexNode* index, deUint32 baseOffset, const SparseIndexNode* group)
326{
327	const deUint32	numLocalNodes	= (deUint32)group->children.size();
328	deUint32		curOffset		= numLocalNodes;
329
330	// Must be normalized prior to construction of final index
331	DE_ASSERT(group->children.empty() || group->children.back()->word == 0);
332
333	for (size_t childNdx = 0; childNdx < numLocalNodes; childNdx++)
334	{
335		const SparseIndexNode*	child		= group->children[childNdx];
336		const deUint32			subtreeSize	= addAndCountNodes(index+curOffset, baseOffset+curOffset, child);
337
338		index[childNdx].word = child->word;
339
340		if (subtreeSize == 0)
341			index[childNdx].index = child->index;
342		else
343		{
344			DE_ASSERT(child->index == 0);
345			index[childNdx].index = baseOffset+curOffset;
346		}
347
348		curOffset += subtreeSize;
349	}
350
351	return curOffset;
352}
353
354void buildFinalIndex (std::vector<BinaryIndexNode>* dst, const SparseIndexNode* root)
355{
356	const deUint32	indexSize	= getIndexSize(root);
357
358	if (indexSize > 0)
359	{
360		dst->resize(indexSize);
361		addAndCountNodes(&(*dst)[0], 0, root);
362	}
363	else
364	{
365		// Generate empty index
366		dst->resize(1);
367		(*dst)[0].word	= 0u;
368		(*dst)[0].index	= 0u;
369	}
370}
371
372void buildBinaryIndex (std::vector<BinaryIndexNode>* dst, size_t numEntries, const ProgramIdentifierIndex* entries)
373{
374	de::UniquePtr<SparseIndexNode>	sparseIndex	(new SparseIndexNode());
375
376	for (size_t ndx = 0; ndx < numEntries; ndx++)
377	{
378		const std::vector<deUint32>	searchPath	= getSearchPath(entries[ndx].id);
379		addToSparseIndex(sparseIndex.get(), &searchPath[0], searchPath.size(), entries[ndx].index);
380	}
381
382	normalizeSparseIndex(sparseIndex.get());
383	buildFinalIndex(dst, sparseIndex.get());
384}
385
386} // anonymous
387
388// BinaryIndexHash
389
390DE_IMPLEMENT_POOL_HASH(BinaryIndexHashImpl, const ProgramBinary*, deUint32, binaryHash, binaryEqual);
391
392BinaryIndexHash::BinaryIndexHash (void)
393	: m_hash(BinaryIndexHashImpl_create(m_memPool.getRawPool()))
394{
395	if (!m_hash)
396		throw std::bad_alloc();
397}
398
399BinaryIndexHash::~BinaryIndexHash (void)
400{
401}
402
403deUint32* BinaryIndexHash::find (const ProgramBinary* binary) const
404{
405	return BinaryIndexHashImpl_find(m_hash, binary);
406}
407
408void BinaryIndexHash::insert (const ProgramBinary* binary, deUint32 index)
409{
410	if (!BinaryIndexHashImpl_insert(m_hash, binary, index))
411		throw std::bad_alloc();
412}
413
414// BinaryRegistryWriter
415
416BinaryRegistryWriter::BinaryRegistryWriter (const std::string& dstPath)
417	: m_dstPath(dstPath)
418{
419	if (de::FilePath(dstPath).exists())
420		initFromPath(dstPath);
421}
422
423BinaryRegistryWriter::~BinaryRegistryWriter (void)
424{
425	for (BinaryVector::const_iterator binaryIter = m_binaries.begin();
426		 binaryIter != m_binaries.end();
427		 ++binaryIter)
428		delete binaryIter->binary;
429}
430
431void BinaryRegistryWriter::initFromPath (const std::string& srcPath)
432{
433	DE_ASSERT(m_binaries.empty());
434
435	for (de::DirectoryIterator iter(srcPath); iter.hasItem(); iter.next())
436	{
437		const de::FilePath	path		= iter.getItem();
438		const std::string	baseName	= path.getBaseName();
439
440		if (isProgramFileName(baseName))
441		{
442			const deUint32						index	= getProgramIndexFromName(baseName);
443			const de::UniquePtr<ProgramBinary>	binary	(readBinary(path.getPath()));
444
445			addBinary(index, *binary);
446			// \note referenceCount is left to 0 and will only be incremented
447			//		 if binary is reused (added via addProgram()).
448		}
449	}
450}
451
452void BinaryRegistryWriter::addProgram (const ProgramIdentifier& id, const ProgramBinary& binary)
453{
454	const deUint32* const	indexPtr	= findBinary(binary);
455	deUint32				index		= indexPtr ? *indexPtr : ~0u;
456
457	if (!indexPtr)
458	{
459		index = getNextSlot();
460		addBinary(index, binary);
461	}
462
463	m_binaries[index].referenceCount += 1;
464	m_binaryIndices.push_back(ProgramIdentifierIndex(id, index));
465}
466
467deUint32* BinaryRegistryWriter::findBinary (const ProgramBinary& binary) const
468{
469	return m_binaryHash.find(&binary);
470}
471
472deUint32 BinaryRegistryWriter::getNextSlot (void) const
473{
474	const deUint32	index	= (deUint32)m_binaries.size();
475
476	if ((size_t)index != m_binaries.size())
477		throw std::bad_alloc(); // Overflow
478
479	return index;
480}
481
482void BinaryRegistryWriter::addBinary (deUint32 index, const ProgramBinary& binary)
483{
484	DE_ASSERT(binary.getFormat() == vk::PROGRAM_FORMAT_SPIRV);
485	DE_ASSERT(findBinary(binary) == DE_NULL);
486
487	ProgramBinary* const	binaryClone		= new ProgramBinary(binary);
488
489	try
490	{
491		if (m_binaries.size() < (size_t)index+1)
492			m_binaries.resize(index+1);
493
494		DE_ASSERT(!m_binaries[index].binary);
495		DE_ASSERT(m_binaries[index].referenceCount == 0);
496
497		m_binaries[index].binary = binaryClone;
498		// \note referenceCount is not incremented here
499	}
500	catch (...)
501	{
502		delete binaryClone;
503		throw;
504	}
505
506	m_binaryHash.insert(binaryClone, index);
507}
508
509void BinaryRegistryWriter::write (void) const
510{
511	writeToPath(m_dstPath);
512}
513
514void BinaryRegistryWriter::writeToPath (const std::string& dstPath) const
515{
516	if (!de::FilePath(dstPath).exists())
517		de::createDirectoryAndParents(dstPath.c_str());
518
519	DE_ASSERT(m_binaries.size() <= 0xffffffffu);
520	for (size_t binaryNdx = 0; binaryNdx < m_binaries.size(); ++binaryNdx)
521	{
522		const BinarySlot&	slot	= m_binaries[binaryNdx];
523
524		if (slot.referenceCount > 0)
525		{
526			DE_ASSERT(slot.binary);
527			writeBinary(dstPath, (deUint32)binaryNdx, *slot.binary);
528		}
529		else
530		{
531			// Delete stale binary if such exists
532			const std::string	progPath	= getProgramPath(dstPath, (deUint32)binaryNdx);
533
534			if (de::FilePath(progPath).exists())
535				deDeleteFile(progPath.c_str());
536		}
537
538	}
539
540	// Write index
541	{
542		const de::FilePath				indexPath	= getIndexPath(dstPath);
543		std::vector<BinaryIndexNode>	index;
544
545		buildBinaryIndex(&index, m_binaryIndices.size(), !m_binaryIndices.empty() ? &m_binaryIndices[0] : DE_NULL);
546
547		// Even in empty index there is always terminating node for the root group
548		DE_ASSERT(!index.empty());
549
550		if (!de::FilePath(indexPath.getDirName()).exists())
551			de::createDirectoryAndParents(indexPath.getDirName().c_str());
552
553		{
554			std::ofstream indexOut(indexPath.getPath(), std::ios_base::binary);
555
556			if (!indexOut.is_open() || !indexOut.good())
557				throw tcu::InternalError(string("Failed to open program binary index file ") + indexPath.getPath());
558
559			indexOut.write((const char*)&index[0], index.size()*sizeof(BinaryIndexNode));
560		}
561	}
562}
563
564// BinaryRegistryReader
565
566BinaryRegistryReader::BinaryRegistryReader (const tcu::Archive& archive, const std::string& srcPath)
567	: m_archive	(archive)
568	, m_srcPath	(srcPath)
569{
570}
571
572BinaryRegistryReader::~BinaryRegistryReader (void)
573{
574}
575
576ProgramBinary* BinaryRegistryReader::loadProgram (const ProgramIdentifier& id) const
577{
578	if (!m_binaryIndex)
579	{
580		try
581		{
582			m_binaryIndex = BinaryIndexPtr(new BinaryIndexAccess(de::MovePtr<tcu::Resource>(m_archive.getResource(getIndexPath(m_srcPath).c_str()))));
583		}
584		catch (const tcu::ResourceError& e)
585		{
586			throw ProgramNotFoundException(id, string("Failed to open binary index (") + e.what() + ")");
587		}
588	}
589
590	{
591		const deUint32*	indexPos	= findBinaryIndex(m_binaryIndex.get(), id);
592
593		if (indexPos)
594		{
595			const string	fullPath	= getProgramPath(m_srcPath, *indexPos);
596
597			try
598			{
599				de::UniquePtr<tcu::Resource>	progRes		(m_archive.getResource(fullPath.c_str()));
600				const int						progSize	= progRes->getSize();
601				vector<deUint8>					bytes		(progSize);
602
603				TCU_CHECK_INTERNAL(!bytes.empty());
604
605				progRes->read(&bytes[0], progSize);
606
607				return new ProgramBinary(vk::PROGRAM_FORMAT_SPIRV, bytes.size(), &bytes[0]);
608			}
609			catch (const tcu::ResourceError& e)
610			{
611				throw ProgramNotFoundException(id, e.what());
612			}
613		}
614		else
615			throw ProgramNotFoundException(id, "Program not found in index");
616	}
617}
618
619} // BinaryRegistryDetail
620} // vk
621