kdepdb.c@ 2657

Last change on this file since 2657 was 2450, checked in by bird, 13 years ago
fixes
Property svn:eol-style set to `native`
File size: 30.9 KB

Line
1	/* $Id: incdep.c 2283 2009-02-24 04:54:00Z bird $ */
2	/** @file
3	* kdepdb - Dependency database.
4	*/
5
6	/*
7	* Copyright (c) 2009-2010 knut st. osmundsen <[email protected]>
8	*
9	* This file is part of kBuild.
10	*
11	* kBuild is free software; you can redistribute it and/or modify
12	* it under the terms of the GNU General Public License as published by
13	* the Free Software Foundation; either version 3 of the License, or
14	* (at your option) any later version.
15	*
16	* kBuild is distributed in the hope that it will be useful,
17	* but WITHOUT ANY WARRANTY; without even the implied warranty of
18	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19	* GNU General Public License for more details.
20	*
21	* You should have received a copy of the GNU General Public License
22	* along with kBuild. If not, see <http://www.gnu.org/licenses/>
23	*
24	*/
25
26	/*******************************************************************************
27	* Header Files *
28	*******************************************************************************/
29	#include "make.h"
30	#include "../lib/k/kDefs.h"
31	#include "../lib/k/kTypes.h"
32	#include <assert.h>
33	#include <glob.h>
34
35	#include "dep.h"
36	#include "filedef.h"
37	#include "job.h"
38	#include "commands.h"
39	#include "variable.h"
40	#include "rule.h"
41	#include "debug.h"
42	#include "strcache2.h"
43
44	#ifdef HAVE_FCNTL_H
45	# include <fcntl.h>
46	#else
47	# include <sys/file.h>
48	#endif
49
50	#if K_OS == K_WINDOWS
51	# include <Windows.h>
52	#else
53	# include <unistd.h>
54	# include <sys/mman.h>
55	#endif
56
57
58	/*******************************************************************************
59	* Defined Constants And Macros *
60	*******************************************************************************/
61	/** @def KDEPDB_ASSERT_SIZE
62	* Check the size of an on-disk type.
63	*
64	* @param Type The type which size it being checked.
65	* @param Size The size it should have.
66	*/
67	#ifdef __GNUC__
68	# define KDEPDB_ASSERT_SIZE(Type, Size) \
69	extern int kDepDbAssertSize[1] __attribute__((unused)), \
70	kDepDbAssertSize[sizeof(Type) == (Size)] __attribute__((unused))
71	#else
72	# define KDEPDB_ASSERT_SIZE(Type, Size) \
73	typedef int kDepDbAssertSize[sizeof(Type) == (Size)]
74	#endif
75	KDEPDB_ASSERT_SIZE(KU8, 1);
76	KDEPDB_ASSERT_SIZE(KU16, 2);
77	KDEPDB_ASSERT_SIZE(KU32, 4);
78	KDEPDB_ASSERT_SIZE(KU64, 8);
79
80
81	/*******************************************************************************
82	* Structures and Typedefs *
83	*******************************************************************************/
84	/**
85	* File header.
86	*
87	* @remarks All on-disk formats are in little-endian format.
88	*/
89	typedef struct KDEPDBHDR
90	{
91	/** The file magic. */
92	KU8 szMagic[8];
93	/** The major file format version. */
94	KU8 uVerMajor;
95	/** The minor file format version. */
96	KU8 uVerMinor;
97	/** Reserved \#2. */
98	KU16 uReserved2;
99	/** Reserved \#1. */
100	KU32 uReserved1;
101	/** The internal name of this file. */
102	KU8 szName[16];
103	} KDEPDBHDR;
104	KDEPDB_ASSERT_SIZE(KDEPDBHDR, 32);
105
106	/** The file header magic value. */
107	#define KDEPDBHDR_MAGIC "kDepDb\0"
108	/** The current major file format version number. */
109	#define KDEPDBHDR_VERSION_MAJOR 0
110	/** The current minor file format version number.
111	* Numbers above 240 indicate unsupported development variants. */
112	#define KDEPDBHDR_VERSION_MINOR 240
113
114
115	/**
116	* Hash table file.
117	*
118	* The hash table is recreated in a new file when we have to grow it.
119	*/
120	typedef struct KDEPDBHASH
121	{
122	/** The file header. */
123	KDEPDBHDR Hdr;
124	/** The number of hash table entries. */
125	KU32 cEntries;
126	/** The number of hash table entries with content. */
127	KU32 cUsedEntries;
128	/** The number of collisions on insert. */
129	KU32 cCollisions;
130	/** Reserved member \#5. */
131	KU32 uReserved5;
132	/** Reserved member \#4. */
133	KU32 uReserved4;
134	/** Reserved member \#3. */
135	KU32 uReserved3;
136	/** Reserved member \#2. */
137	KU32 uReserved2;
138	/** Reserved member \#1. */
139	KU32 uReserved1;
140	/** The hash table. */
141	KU32 auEntries[32];
142	} KDEPDBHASH;
143	KDEPDB_ASSERT_SIZE(KDEPDBHASH, 32+32+4*32);
144
145	/** The item value indicating that it is unused. */
146	#define KDEPDBHASH_UNUSED KU32_C(0xffffffff)
147	/** The item indicating that it hash been deleted. */
148	#define KDEPDBHASH_DELETED KU32_C(0xfffffffe)
149	/** The first special item value. */
150	#define KDEPDBHASH_END KU32_C(0xfffffff0)
151
152
153	/**
154	* A string table string entry.
155	*
156	* This should be a multiple of 32 bytes.
157	*/
158	typedef struct KDEPDBSTRING
159	{
160	/** The hash number for the string. */
161	KU32 uHash;
162	/** The string length, excluding the zero terminator. */
163	KU32 cchString;
164	/** The string. */
165	KU8 szString[24];
166	} KDEPDBSTRING;
167	KDEPDB_ASSERT_SIZE(KDEPDBSTRING, 32);
168
169
170	/**
171	* String table file.
172	*
173	* The file is insertion only and will grow forever.
174	*/
175	typedef struct KDEPDBSTRTAB
176	{
177	/** The file header. */
178	KDEPDBHDR Hdr;
179	/** The end of the valid string table indexes. */
180	KU32 iStringEnd;
181	/** Reserved member \#7. */
182	KU32 uReserved7;
183	/** Reserved member \#6. */
184	KU32 uReserved6;
185	/** Reserved member \#5. */
186	KU32 uReserved5;
187	/** Reserved member \#4. */
188	KU32 uReserved4;
189	/** Reserved member \#3. */
190	KU32 uReserved3;
191	/** Reserved member \#2. */
192	KU32 uReserved2;
193	/** Reserved member \#1. */
194	KU32 uReserved1;
195	/** The string table. */
196	KDEPDBSTRING aStrings[1];
197	} KDEPDBSTRTAB;
198	KDEPDB_ASSERT_SIZE(KDEPDBSTRTAB, 32+32+32);
199
200	/** The end of the valid string table indexes (exclusive). */
201	#define KDEPDBG_STRTAB_IDX_END KU32_C(0x80000000)
202	/** The string was not found. */
203	#define KDEPDBG_STRTAB_IDX_NOT_FOUND KU32_C(0xfffffffd)
204	/** Error during string table operation. */
205	#define KDEPDBG_STRTAB_IDX_ERROR KU32_C(0xfffffffe)
206	/** Generic invalid string table index. */
207	#define KDEPDBG_STRTAB_IDX_INVALID KU32_C(0xffffffff)
208
209
210	/**
211	* Directory entry.
212	*/
213	typedef struct KDEPDBDIRENTRY
214	{
215	/** The string table index of the entry name.
216	* Unused entries are set to KDEPDBG_STRTAB_IDX_INVALID. */
217	KU32 iName;
218	/** The actual data stream size.
219	* Unused entries are set to KU32_MAX. */
220	KU32 cbData;
221	/** The number of blocks allocated for this stream.
222	* Unused entries are set to KU32_MAX. */
223	KU32 cBlocks;
224	/** The start block number.
225	* The stream is a contiguous sequence of blocks. This optimizes and
226	* simplifies reading the stream at the expense of operations extending it.
227	*
228	* In unused entries, this serves as the free chain pointer with KU32_MAX as
229	* nil value. */
230	KU32 iStartBlock;
231	} KDEPDBDIRENTRY;
232	KDEPDB_ASSERT_SIZE(KDEPDBDIRENTRY, 16);
233
234	/**
235	* Directory file.
236	*/
237	typedef struct KDEPDBDIR
238	{
239	/** The file header. */
240	KDEPDBHDR Hdr;
241	/** The number of entries. */
242	KU32 cEntries;
243	/** The head of the free chain. (Index into aEntries.) */
244	KU32 iFreeHead;
245	/** Reserved member \#6. */
246	KU32 uReserved6;
247	/** Reserved member \#5. */
248	KU32 uReserved5;
249	/** Reserved member \#4. */
250	KU32 uReserved4;
251	/** Reserved member \#3. */
252	KU32 uReserved3;
253	/** Reserved member \#2. */
254	KU32 uReserved2;
255	/** Reserved member \#1. */
256	KU32 uReserved1;
257	/** Directory entries. */
258	KDEPDBDIRENTRY aEntries[2];
259	} KDEPDBDIR;
260	KDEPDB_ASSERT_SIZE(KDEPDBDIR, 32+32+32);
261
262
263	/**
264	* A block allocation bitmap.
265	*
266	* This can track 2^(12+8) = 2^20 = 1M blocks.
267	*/
268	typedef struct KDEPDBDATABITMAP
269	{
270	/** Bitmap where each bit is a block.
271	* 0 indicates unused blocks and 1 indicates used ones. */
272	KU8 bm[4096];
273	} KDEPDBDATABITMAP;
274	KDEPDB_ASSERT_SIZE(KDEPDBDATABITMAP, 4096);
275
276	/**
277	* Data file.
278	*
279	* The block numbering starts with this structure as block 0.
280	*/
281	typedef struct KDEPDBDATA
282	{
283	/** The file header. */
284	KDEPDBHDR Hdr;
285	/** The size of a block. */
286	KU32 cbBlock;
287	/** Reserved member \#7. */
288	KU32 uReserved7;
289	/** Reserved member \#6. */
290	KU32 uReserved6;
291	/** Reserved member \#5. */
292	KU32 uReserved5;
293	/** Reserved member \#4. */
294	KU32 uReserved4;
295	/** Reserved member \#3. */
296	KU32 uReserved3;
297	/** Reserved member \#2. */
298	KU32 uReserved2;
299	/** Reserved member \#1. */
300	KU32 uReserved1;
301
302	/** Block numbers for the allocation bitmaps. */
303	KU32 aiBitmaps[4096];
304	} KDEPDBDATA;
305
306	/** The end of the valid block indexes (exclusive). */
307	#define KDEPDB_BLOCK_IDX_END KU32_C(0xfffffff0)
308	/** The index of an unallocated bitmap block. */
309	#define KDEPDB_BLOCK_IDX_UNALLOCATED KU32_C(0xffffffff)
310
311
312	/**
313	* Stream storing dependencies.
314	*
315	* The stream name gives the output file name, so all that we need is the list
316	* of files it depends on. These are serialized as a list of string table
317	* indexes.
318	*/
319	typedef struct KDEPDBDEPSTREAM
320	{
321	/** String table indexes for the dependencies. */
322	KU32 aiDeps[1];
323	} KDEPDBDEPSTREAM;
324
325
326	/**
327	* A file handle structure.
328	*/
329	typedef struct KDEPDBFH
330	{
331	#if K_OS == K_OS_WINDOWS
332	/** The file handle. */
333	HANDLE hFile;
334	/** The mapping object handle. */
335	HANDLE hMapObj;
336	#else
337	/** The file handle. */
338	int fd;
339	#endif
340	/** The current file size. */
341	KU32 cb;
342	} KDEPDBFH;
343
344
345	/**
346	* Internal control structure for a string table.
347	*/
348	typedef struct KDEPDBINTSTRTAB
349	{
350	/** The hash file. */
351	KDEPDBHASH *pHash;
352	/** The handle of the hash file. */
353	KDEPDBFH hHash;
354	/** The string table file. */
355	KDEPDBSTRTAB *pStrTab;
356	/** The handle of the string table file. */
357	KDEPDBFH hStrTab;
358	/** The end of the allocated string table indexes (i.e. when to grow the
359	* file). */
360	KU32 iStringAlloced;
361	} KDEPDBINTSTRTAB;
362
363
364	/**
365	* Internal control structure for a data set.
366	*
367	* This governs the directory file, the directory hash file and the data file.
368	*/
369	typedef struct KDEPDBINTDATASET
370	{
371	/** The hash file. */
372	KDEPDBHASH pHash;
373	/** The size of the hash file. */
374	KU32 cbHash;
375	/** The size of the directory file. */
376	KU32 cbDir;
377	/** The mapping of the directory file. */
378	KDEPDBHASH pDir;
379	/** The data file. */
380	KDEPDBDATA pData;
381	/** The size of the data file. */
382	KU32 cbData;
383	/** The handle of the hash file. */
384	KDEPDBFH hHash;
385	/** The handle of the directory file. */
386	KDEPDBFH hDir;
387	/** The handle of the data file. */
388	KDEPDBFH hData;
389	} KDEPDBINTDATASET;
390
391
392	/**
393	* The database instance.
394	*
395	* To simplifiy things the database uses 8 files for storing the different kinds
396	* of data. This greatly reduces the complexity compared to a single file
397	* solution.
398	*/
399	typedef struct KDEPDB
400	{
401	/** The string table. */
402	KDEPDBINTSTRTAB StrTab;
403	/** The variable data set. */
404	KDEPDBINTDATASET DepSet;
405	/** The command data set. */
406	KDEPDBINTDATASET CmdSet;
407	} KDEPDB;
408
409
410	/*******************************************************************************
411	* Internal Functions *
412	*******************************************************************************/
413	static void *kDepDbAlloc(KSIZE cb);
414	static void kDepDbFree(void *pv);
415	static void kDepDbFHInit(KDEPDBFH *pFH);
416	static int kDepDbFHUpdateSize(KDEPDBFH *pFH);
417	static int kDepDbFHOpen(KDEPDBFH pFH, const char pszFilename, KBOOL fCreate, KBOOL *pfNew);
418	static int kDepDbFHClose(KDEPDBFH *pFH);
419	static int kDepDbFHWriteAt(KDEPDBFH pFH, KU32 off, void const pvBuf, KSIZE cbBuf);
420	static int kDepDbFHMap(KDEPDBFH pFH, void *ppvMap);
421	static int kDepDbFHUnmap(KDEPDBFH pFH, void *ppvMap);
422	static int kDepDbFHGrow(KDEPDBFH pFH, KSIZE cbNew, void *ppvMap);
423	static KU32 kDepDbHashString(const char *pszString, size_t cchString);
424
425
426	/** xmalloc wrapper. */
427	static void *kDepDbAlloc(KSIZE cb)
428	{
429	return xmalloc(cb);
430	}
431
432	/** free wrapper. */
433	static void kDepDbFree(void *pv)
434	{
435	if (pv)
436	free(pv);
437	}
438
439
440	/**
441	* Initializes the file handle structure so closing it without first opening it
442	* will work smoothly.
443	*
444	* @param pFH The file handle structure.
445	*/
446	static void kDepDbFHInit(KDEPDBFH *pFH)
447	{
448	#if K_OS == K_OS_WINDOWS
449	pFH->hFile = INVALID_HANDLE_VALUE;
450	pFH->hMapObj = INVALID_HANDLE_VALUE;
451	#else
452	pFH->fd = -1;
453	#endif
454	pFH->cb = 0;
455	}
456
457	/**
458	* Updates the file size.
459	*
460	* @returns 0 on success. Some non-zero native error code on failure.
461	* @param pFH The file handle structure.
462	*/
463	static int kDepDbFHUpdateSize(KDEPDBFH *pFH)
464	{
465	#if K_OS == K_OS_WINDOWS
466	DWORD rc;
467	DWORD dwHigh;
468	DWORD dwLow;
469
470	SetLastError(0);
471	dwLow = GetFileSize(File, &High);
472	rc = GetLastError();
473	if (rc)
474	{
475	pFH->cb = 0;
476	return (int)rc;
477	}
478	if (High)
479	pFH->cb = KU32_MAX;
480	else
481	pFH->cb = dwLow;
482	#else
483	off_t cb;
484
485	cb = lseek(pFH->fd, 0, SEEK_END);
486	if (cb == -1)
487	{
488	pFH->cb = 0;
489	return errno;
490	}
491	pFH->cb = cb;
492	if ((off_t)pFH->cb != cb)
493	pFH->cb = KU32_MAX;
494	#endif
495	return 0;
496	}
497
498	/**
499	* Opens an existing file or creates a new one.
500	*
501	* @returns 0 on success. Some non-zero native error code on failure.
502	*
503	* @param pFH The file handle structure.
504	* @param pszFilename The name of the file.
505	* @param fCreate Whether we should create the file or not.
506	* @param pfCreated Where to return whether we created it or not.
507	*/
508	static int kDepDbFHOpen(KDEPDBFH pFH, const char pszFilename, KBOOL fCreate, KBOOL *pfCreated)
509	{
510	int rc;
511	#if K_OS == K_OS_WINDOWS
512	SECURITY_ATTRIBUTES SecAttr;
513
514	SecAttr.bInheritHandle = FALSE;
515	SecAttr.lpSecurityDescriptor = NULL;
516	SecAttr.nLength = 0;
517	pFH->cb = 0;
518	SetLastError(0);
519	pFH->hFile = CreateFile(pszFilename, GENERIC_READ \| GENERIC_WRITE, FILE_SHARE_READ, &SecAttr,
520	fCreate ? OPEN_ALWAYS : OPEN_EXISTING, 0, NULL);
521	if (pFH->hFile == INVALID_HANDLE_VALUE)
522	return GetLastError();
523	*pfCreated = GetLastError() == 0;
524
525	#else
526	int fFlags = O_RDWR;
527	# ifdef O_BINARY
528	fFlags \|= O_BINARY;
529	# endif
530	pFH->cb = 0;
531	pFH->fd = open(pszFilename, fFlags, 0);
532	if (pFH->fd >= 0)
533	*pfCreated = K_FALSE;
534	else if (!fCreate)
535	return errno;
536	else
537	{
538	pFH->fd = open(pszFilename, fFlags \| O_EXCL \| O_CREAT, 0666);
539	if (pFH->fd < 0)
540	return errno;
541	*pfCreated = K_TRUE;
542	}
543	fcntl(pFH->fd, F_SETFD, FD_CLOEXEC);
544	#endif
545
546	/* update the size */
547	rc = kDepDbFHUpdateSize(pFH);
548	if (rc)
549	kDepDbFHClose(pFH);
550	return rc;
551	}
552
553	/**
554	* Closes an open file.
555	*
556	* @returns 0 on success. Some non-zero native error code on failure.
557	*
558	* @param pFH The file handle structure.
559	*/
560	static int kDepDbFHClose(KDEPDBFH *pFH)
561	{
562	#if K_OS == K_OS_WINDOWS
563	if (pFH->hFile != INVALID_HANDLE_VALUE)
564	{
565	if (!CloseHandle(pFH->hFile))
566	return GetLastError();
567	pFH->hFile = INVALID_HANDLE_VALUE;
568	}
569
570	#else
571	if (pFH->fd >= 0)
572	{
573	if (close(pFH->fd) != 0)
574	return errno;
575	pFH->fd = -1;
576	}
577	#endif
578	pFH->cb = 0;
579	return 0;
580	}
581
582	/**
583	* Writes to a file.
584	*
585	* @returns 0 on success. Some non-zero native error code on failure.
586	*
587	* @param pFH The file handle structure.
588	* @param off The offset into the file to start writing at.
589	* @param pvBuf What to write.
590	* @param cbBuf How much to write.
591	*/
592	static int kDepDbFHWriteAt(KDEPDBFH pFH, KU32 off, void const pvBuf, KSIZE cbBuf)
593	{
594	#if K_OS == K_OS_WINDOWS
595	ULONG cbWritten;
596
597	if (SetFilePointer(pFH->hFile, off, NULL, FILE_CURRENT) == INVALID_SET_FILE_POINTER)
598	return GetLastError();
599
600	if (!WriteFile(pFH->hFile, pvBuf, cbBuf, &cbWritten, NULL))
601	return GetLastError();
602	if (cbWritten != cbBuf)
603	return -1;
604
605	#else
606	ssize_t cbWritten;
607	if (lseek(pFH->fd, off, SEEK_SET) == -1)
608	return errno;
609	errno = 0;
610	cbWritten = write(pFH->fd, pvBuf, cbBuf);
611	if ((size_t)cbWritten != cbBuf)
612	return errno ? errno : EIO;
613	#endif
614	return kDepDbFHUpdateSize(pFH);
615	}
616
617
618	/**
619	* Creates a memory mapping of the file.
620	*
621	* @returns 0 on success. Some non-zero native error code on failure.
622	*
623	* @param pFH The file handle structure.
624	* @param ppvMap Where to return the map address.
625	*/
626	static int kDepDbFHMap(KDEPDBFH pFH, void *ppvMap)
627	{
628	#if K_OS == K_OS_WINDOWS
629	*ppvMap = NULL;
630	return -1;
631	#else
632	*ppvMap = mmap(NULL, pFH->cb, PROT_READ \| PROT_WRITE, MAP_FILE \| MAP_SHARED, pFH->fd, 0);
633	if (ppvMap == (void )-1)
634	{
635	*ppvMap = NULL;
636	return errno;
637	}
638	#endif
639	return 0;
640	}
641
642
643	/**
644	* Flushes and destroys a memory of the file.
645	*
646	* @returns 0 on success. Some non-zero native error code on failure.
647	*
648	* @param pFH The file handle structure.
649	* @param ppvMap The pointer to the mapping pointer. This will be set to
650	* NULL on success.
651	*/
652	static int kDepDbFHUnmap(KDEPDBFH pFH, void *ppvMap)
653	{
654	#if K_OS == K_OS_WINDOWS
655	return -1;
656	#else
657	if (msync(*ppvMap, pFH->cb, MS_SYNC) == -1)
658	return errno;
659	if (munmap(*ppvMap, pFH->cb) == -1)
660	return errno;
661	*ppvMap = NULL;
662	#endif
663	return 0;
664	}
665
666
667	/**
668	* Grows the memory mapping of the file.
669	*
670	* The content of the new space is undefined.
671	*
672	* @returns 0 on success. Some non-zero native error code on failure.
673	*
674	* @param pFH The file handle structure.
675	* @param cbNew The new mapping size.
676	* @param ppvMap The pointer to the mapping pointer. This may change and
677	* may be set to NULL on failure.
678	*/
679	static int kDepDbFHGrow(KDEPDBFH pFH, KSIZE cbNew, void *ppvMap)
680	{
681	#if K_OS == K_OS_WINDOWS
682	return -1;
683	#else
684	if ((KU32)cbNew != cbNew)
685	return ERANGE;
686	if (cbNew <= pFH->cb)
687	return 0;
688
689	if (munmap(*ppvMap, pFH->cb) == -1)
690	return errno;
691	*ppvMap = NULL;
692
693	pFH->cb = cbNew;
694	return kDepDbFHMap(pFH, ppvMap);
695	#endif
696	}
697
698
699	/** Macro for reading an potentially unaligned 16-bit word from a string. */
700	# if K_ARCH == K_ARCH_AMD64 \
701	\|\| K_ARCH == K_ARCH_X86_32 \
702	\|\| K_ARCH == K_ARCH_X86_16
703	# define kDepDbHashString_get_unaligned_16bits(ptr) ( ((const KU16 )(ptr)) )
704	# elif K_ENDIAN == K_ENDIAN_LITTLE
705	# define kDepDbHashString_get_unaligned_16bits(ptr) ( (((const KU8 *)(ptr))[0]) \
706	\| (((const KU8 *)(ptr))[1] << 8) )
707	# else
708	# define kDepDbHashString_get_unaligned_16bits(ptr) ( (((const KU8 *)(ptr))[0] << 8) \
709	\| (((const KU8 *)(ptr))[1]) )
710	# endif
711
712
713	/**
714	* Hash a string.
715	*
716	* @returns Hash value.
717	*
718	* @param pszString The string to hash.
719	* @param cchString How much to hash.
720	*/
721	static KU32 kDepDbHashString(const char *pszString, size_t cchString)
722	{
723	/*
724	* Paul Hsieh hash SuperFast function:
725	* http://www.azillionmonkeys.com/qed/hash.html
726	*/
727	/** @todo A path for well aligned data should be added to speed up execution on
728	* alignment sensitive systems. */
729	unsigned int uRem;
730	KU32 uHash;
731	KU32 uTmp;
732
733	assert(sizeof(KU8) == sizeof(char));
734
735	/* main loop, walking on 2 x KU16 */
736	uHash = cchString;
737	uRem = cchString & 3;
738	cchString >>= 2;
739	while (cchString > 0)
740	{
741	uHash += kDepDbHashString_get_unaligned_16bits(pszString);
742	uTmp = (kDepDbHashString_get_unaligned_16bits(pszString + 2) << 11) ^ uHash;
743	uHash = (uHash << 16) ^ uTmp;
744	pszString += 2 * sizeof(KU16);
745	uHash += uHash >> 11;
746	cchString--;
747	}
748
749	/* the remainder */
750	switch (uRem)
751	{
752	case 3:
753	uHash += kDepDbHashString_get_unaligned_16bits(pszString);
754	uHash ^= uHash << 16;
755	uHash ^= pszString[sizeof(KU16)] << 18;
756	uHash += uHash >> 11;
757	break;
758	case 2:
759	uHash += kDepDbHashString_get_unaligned_16bits(pszString);
760	uHash ^= uHash << 11;
761	uHash += uHash >> 17;
762	break;
763	case 1:
764	uHash += *pszString;
765	uHash ^= uHash << 10;
766	uHash += uHash >> 1;
767	break;
768	}
769
770	/* force "avalanching" of final 127 bits. */
771	uHash ^= uHash << 3;
772	uHash += uHash >> 5;
773	uHash ^= uHash << 4;
774	uHash += uHash >> 17;
775	uHash ^= uHash << 25;
776	uHash += uHash >> 6;
777
778	return uHash;
779	}
780
781
782	/***
783	* Looks up a string in the string table.
784	*
785	* @returns The string table index.
786	* @retval KDEPDBG_STRTAB_IDX_NOT_FOUND is not found.
787	* @retval KDEPDBG_STRTAB_IDX_ERROR on internal inconsistency.
788	*
789	* @param pStrTab The string table.
790	* @param pszString The string.
791	* @param cchStringIn The string length.
792	* @param uHash The hash of the string.
793	*/
794	static KU32 kDepDbStrTabLookupHashed(KDEPDBINTSTRTAB const pStrTab, const char pszString, size_t cchStringIn, KU32 uHash)
795	{
796	KU32 const cchString = (KU32)cchStringIn;
797	KDEPDBHASH const *pHash = pStrTab->pHash;
798	KDEPDBSTRING const *paStrings = &pStrTab->pStrTab->aStrings[0];
799	KU32 const iStringEnd = K_LE2H_U32(pStrTab->pStrTab->iStringEnd);
800	KU32 iHash;
801
802	/* sanity */
803	if (cchString != cchStringIn)
804	return KDEPDBG_STRTAB_IDX_NOT_FOUND;
805
806	/*
807	* Hash lookup of the string.
808	*/
809	iHash = uHash % pHash->cEntries;
810	for (;;)
811	{
812	KU32 iString = K_LE2H_U32(pHash->auEntries[iHash]);
813	if (iString < iStringEnd)
814	{
815	KDEPDBSTRING const *pString = &paStrings[iString];
816	if ( K_LE2H_U32(pString->uHash) == uHash
817	&& K_LE2H_U32(pString->cchString) == cchString
818	&& !memcmp(pString->szString, pszString, cchString))
819	return iString;
820	}
821	else if (iString == KDEPDBHASH_UNUSED)
822	return KDEPDBG_STRTAB_IDX_NOT_FOUND;
823	else if (iString != KDEPDBHASH_DELETED)
824	return KDEPDBG_STRTAB_IDX_ERROR;
825
826	/* advance */
827	iHash = (iHash + 1) % pHash->cEntries;
828	}
829	}
830
831
832	/**
833	* Doubles the hash table size and rehashes it.
834	*
835	* @returns 0 on success, -1 on failure.
836	* @param pStrTab The string table.
837	* @todo Rebuild from string table, we'll be accessing it anyways.
838	*/
839	static int kDepDbStrTabReHash(KDEPDBINTSTRTAB *pStrTab)
840	{
841	KDEPDBSTRING const *paStrings = &pStrTab->pStrTab->aStrings[0];
842	KU32 const iStringEnd = K_LE2H_U32(pStrTab->pStrTab->iStringEnd);
843	KDEPDBHASH *pHash = pStrTab->pHash;
844	KDEPDBHASH HashHdr = *pHash;
845	KU32 *pauNew;
846	KU32 cEntriesNew;
847	KU32 i;
848
849	/*
850	* Calc the size of the new hash table.
851	*/
852	if (pHash->cEntries >= KU32_C(0x80000000))
853	return -1;
854	cEntriesNew = 1024;
855	while (cEntriesNew <= pHash->cEntries)
856	cEntriesNew <<= 1;
857
858	/*
859	* Allocate and initialize an empty hash table in memory.
860	*/
861	pauNew = kDepDbAlloc(cEntriesNew * sizeof(KU32));
862	if (!pauNew)
863	return -1;
864	i = cEntriesNew;
865	while (i-- > 0)
866	pauNew[i] = KDEPDBHASH_UNUSED;
867
868	/*
869	* Popuplate the new table.
870	*/
871	HashHdr.cEntries = K_LE2H_U32(cEntriesNew);
872	HashHdr.cCollisions = 0;
873	HashHdr.cUsedEntries = 0;
874	i = pHash->cEntries;
875	while (i-- > 0)
876	{
877	KU32 iString = K_LE2H_U32(pHash->auEntries[i]);
878	if (iString < iStringEnd)
879	{
880	KU32 iHash = (paStrings[iString].uHash % cEntriesNew);
881	if (pauNew[iHash] != K_H2LE_U32(KDEPDBHASH_UNUSED))
882	{
883	do
884	{
885	iHash = (iHash + 1) % cEntriesNew;
886	HashHdr.cCollisions++;
887	} while (pauNew[iHash] != K_H2LE_U32(KDEPDBHASH_UNUSED));
888	}
889	pauNew[iHash] = iString;
890	HashHdr.cUsedEntries++;
891	}
892	else if ( iString != KDEPDBHASH_UNUSED
893	&& iString != KDEPDBHASH_DELETED)
894	{
895	kDepDbFree(pauNew);
896	return -1;
897	}
898	}
899	HashHdr.cCollisions = K_H2LE_U32(HashHdr.cCollisions);
900	HashHdr.cUsedEntries = K_H2LE_U32(HashHdr.cUsedEntries);
901
902	/*
903	* Unmap the hash, write the new hash table and map it again.
904	*/
905	if (!kDepDbFHUnmap(&pStrTab->hHash, (void **)&pStrTab->pHash))
906	{
907	if ( !kDepDbFHWriteAt(&pStrTab->hHash, 0, &HashHdr, K_OFFSETOF(KDEPDBHASH, auEntries))
908	&& !kDepDbFHWriteAt(&pStrTab->hHash, K_OFFSETOF(KDEPDBHASH, auEntries), pauNew, sizeof(pauNew[0]) * cEntriesNew))
909	{
910	kDepDbFree(pauNew);
911	pauNew = NULL;
912	if (!kDepDbFHMap(&pStrTab->hHash, (void **)&pStrTab->pHash))
913	return 0;
914	}
915	else
916	kDepDbFHWriteAt(&pStrTab->hHash, 0, "\0\0\0\0", 4); /* file is screwed, trash the magic. */
917	}
918
919	kDepDbFree(pauNew);
920	return -1;
921	}
922
923
924	/**
925	* Add a string to the string table.
926	*
927	* If already in the table, the index of the existing entry is returned.
928	*
929	* @returns String index on success,
930	* @retval KDEPDBG_STRTAB_IDX_ERROR on I/O and inconsistency errors.
931	*
932	* @param pStrTab The string table.
933	* @param pszString The string to add.
934	* @param cchStringIn The length of the string.
935	* @param uHash The hash of the string.
936	*/
937	static KU32 kDepDbStrTabAddHashed(KDEPDBINTSTRTAB pStrTab, const char pszString, size_t cchStringIn, KU32 uHash)
938	{
939	KU32 const cchString = (KU32)cchStringIn;
940	KDEPDBHASH *pHash = pStrTab->pHash;
941	KDEPDBSTRING *paStrings = &pStrTab->pStrTab->aStrings[0];
942	KU32 const iStringEnd = K_LE2H_U32(pStrTab->pStrTab->iStringEnd);
943	KU32 iInsertAt = KDEPDBHASH_UNUSED;
944	KU32 cCollisions = 0;
945	KU32 iHash;
946	KU32 iString;
947	KU32 cEntries;
948	KDEPDBSTRING *pNewString;
949
950	/* sanity */
951	if (cchString != cchStringIn)
952	return KDEPDBG_STRTAB_IDX_NOT_FOUND;
953
954	/*
955	* Hash lookup of the string, finding either an existing copy or where to
956	* insert the new string at in the hash table.
957	*/
958	iHash = uHash % pHash->cEntries;
959	for (;;)
960	{
961	iString = K_LE2H_U32(pHash->auEntries[iHash]);
962	if (iString < iStringEnd)
963	{
964	KDEPDBSTRING const *pString = &paStrings[iString];
965	if ( K_LE2H_U32(pString->uHash) == uHash
966	&& K_LE2H_U32(pString->cchString) == cchString
967	&& !memcmp(pString->szString, pszString, cchString))
968	return iString;
969	}
970	else
971	{
972	if (iInsertAt == KDEPDBHASH_UNUSED)
973	iInsertAt = iHash;
974	if (iString == KDEPDBHASH_UNUSED)
975	break;
976	if (iString != KDEPDBHASH_DELETED)
977	return KDEPDBG_STRTAB_IDX_ERROR;
978	}
979
980	/* advance */
981	cCollisions++;
982	iHash = (iHash + 1) % pHash->cEntries;
983	}
984
985	/*
986	* Add string to the string table.
987	* The string table file is grown in 256KB increments and ensuring at least 64KB unused new space.
988	*/
989	cEntries = cchString + 1 <= sizeof(paStrings[0].szString)
990	? 1
991	: (cchString + 1 - sizeof(paStrings[0].szString) + sizeof(KDEPDBSTRING) - 1) / sizeof(KDEPDBSTRING);
992	if (iStringEnd + cEntries > pStrTab->iStringAlloced)
993	{
994	KSIZE cbNewSize = K_ALIGN_Z((iStringEnd + cEntries) * sizeof(KDEPDBSTRING) + 641024, 2561024);
995	KU32 iStringAlloced = (pStrTab->hStrTab.cb - K_OFFSETOF(KDEPDBSTRTAB, aStrings)) / sizeof(KDEPDBSTRING);
996	if ( iStringAlloced <= pStrTab->iStringAlloced
997	\|\| iStringAlloced >= KDEPDBG_STRTAB_IDX_END
998	\|\| iStringAlloced >= KDEPDBHASH_END)
999	return KDEPDBG_STRTAB_IDX_ERROR;
1000	if (kDepDbFHGrow(&pStrTab->hStrTab, cbNewSize, (void **)&pStrTab->pStrTab) != 0)
1001	return KDEPDBG_STRTAB_IDX_ERROR;
1002	pStrTab->iStringAlloced = iStringAlloced;
1003	paStrings = &pStrTab->pStrTab->aStrings[0];
1004	}
1005
1006	pNewString = &paStrings[iStringEnd];
1007	pNewString->uHash = K_H2LE_U32(uHash);
1008	pNewString->cchString = K_H2LE_U32(cchString);
1009	memcpy(&pNewString->szString, pszString, cchString);
1010	pNewString->szString[cchString] = '\0';
1011
1012	pStrTab->pStrTab->iStringEnd = K_H2LE_U32(iStringEnd + cEntries);
1013
1014	/*
1015	* Insert hash table entry, rehash it if necessary.
1016	*/
1017	pHash->auEntries[iInsertAt] = K_H2LE_U32(iStringEnd);
1018	pHash->cUsedEntries = K_H2LE_U32(K_LE2H_U32(pHash->cUsedEntries) + 1);
1019	pHash->cCollisions = K_H2LE_U32(K_LE2H_U32(pHash->cCollisions) + cCollisions);
1020	if ( K_LE2H_U32(pHash->cUsedEntries) > K_LE2H_U32(pHash->cEntries) / 3 * 2
1021	&& kDepDbStrTabReHash(pStrTab) != 0)
1022	return KDEPDBG_STRTAB_IDX_ERROR;
1023
1024	return iStringEnd;
1025	}
1026
1027
1028	/** Wrapper for kDepDbStrTabLookupHashed. */
1029	static KU32 kDepDbStrTabLookupN(KDEPDBINTSTRTAB const pStrTab, const char pszString, size_t cchString)
1030	{
1031	return kDepDbStrTabLookupHashed(pStrTab, pszString, cchString, kDepDbHashString(pszString, cchString));
1032	}
1033
1034
1035	/** Wrapper for kDepDbStrTabAddHashed. */
1036	static KU32 kDepDbStrTabAddN(KDEPDBINTSTRTAB pStrTab, const char pszString, size_t cchString)
1037	{
1038	return kDepDbStrTabAddHashed(pStrTab, pszString, cchString, kDepDbHashString(pszString, cchString));
1039	}
1040
1041
1042	/** Wrapper for kDepDbStrTabLookupHashed. */
1043	static KU32 kDepDbStrTabLookup(KDEPDBINTSTRTAB const pStrTab, const char pszString)
1044	{
1045	return kDepDbStrTabLookupN(pStrTab, pszString, strlen(pszString));
1046	}
1047
1048
1049	/** Wrapper for kDepDbStrTabAddHashed. */
1050	static KU32 kDepDbStrTabAdd(KDEPDBINTSTRTAB pStrTab, const char pszString)
1051	{
1052	return kDepDbStrTabAddN(pStrTab, pszString, strlen(pszString));
1053	}
1054
1055
1056	/**
1057	* Opens the string table files, creating them if necessary.
1058	*/
1059	static int kDepDbStrTabInit(KDEPDBINTSTRTAB pStrTab, const char pszFilenameBase)
1060	{
1061	size_t cchFilenameBase = strlen(pszFilenameBase);
1062	char szPath[4096];
1063	int rc;
1064	KBOOL fNew;
1065
1066	/* Basic member init, so kDepDbStrTabTerm always works. */
1067	pStrTab->pHash = NULL;
1068	kDepDbFHInit(&pStrTab->hHash);
1069	pStrTab->pStrTab = NULL;
1070	kDepDbFHInit(&pStrTab->hStrTab);
1071	pStrTab->iStringAlloced = 0;
1072
1073	/* check the length. */
1074	if (cchFilenameBase + sizeof(".strtab.hash") > sizeof(szPath))
1075	return -1;
1076
1077	/*
1078	* Open the string table first.
1079	*/
1080	memcpy(szPath, pszFilenameBase, cchFilenameBase);
1081	memcpy(&szPath[cchFilenameBase], ".strtab", sizeof(".strtab"));
1082	rc = kDepDbFHOpen(&pStrTab->hStrTab, szPath, K_TRUE, &fNew);
1083
1084
1085	return -1;
1086	}
1087

Note: See TracBrowser for help on using the repository browser.

source: kBuild/trunk/src/kmk/kdepdb.c@ 2657

Download in other formats: