VirtualBox

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

Last change on this file since 3633 was 3140, checked in by bird, 7 years ago

kmk: Merged in changes from GNU make 4.2.1 (2e55f5e4abdc0e38c1d64be703b446695e70b3b6 / https://git.savannah.gnu.org/git/make.git).

  • 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 "makeint.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
75KDEPDB_ASSERT_SIZE(KU8, 1);
76KDEPDB_ASSERT_SIZE(KU16, 2);
77KDEPDB_ASSERT_SIZE(KU32, 4);
78KDEPDB_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 */
89typedef 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;
104KDEPDB_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 */
120typedef 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;
143KDEPDB_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 */
158typedef 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;
167KDEPDB_ASSERT_SIZE(KDEPDBSTRING, 32);
168
169
170/**
171 * String table file.
172 *
173 * The file is insertion only and will grow forever.
174 */
175typedef 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;
198KDEPDB_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 */
213typedef 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;
232KDEPDB_ASSERT_SIZE(KDEPDBDIRENTRY, 16);
233
234/**
235 * Directory file.
236 */
237typedef 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;
260KDEPDB_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 */
268typedef 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;
274KDEPDB_ASSERT_SIZE(KDEPDBDATABITMAP, 4096);
275
276/**
277 * Data file.
278 *
279 * The block numbering starts with this structure as block 0.
280 */
281typedef 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 */
319typedef 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 */
329typedef 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 */
348typedef 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 */
369typedef 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 */
399typedef 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*******************************************************************************/
413static void *kDepDbAlloc(KSIZE cb);
414static void kDepDbFree(void *pv);
415static void kDepDbFHInit(KDEPDBFH *pFH);
416static int kDepDbFHUpdateSize(KDEPDBFH *pFH);
417static int kDepDbFHOpen(KDEPDBFH *pFH, const char *pszFilename, KBOOL fCreate, KBOOL *pfNew);
418static int kDepDbFHClose(KDEPDBFH *pFH);
419static int kDepDbFHWriteAt(KDEPDBFH *pFH, KU32 off, void const *pvBuf, KSIZE cbBuf);
420static int kDepDbFHMap(KDEPDBFH *pFH, void **ppvMap);
421static int kDepDbFHUnmap(KDEPDBFH *pFH, void **ppvMap);
422static int kDepDbFHGrow(KDEPDBFH *pFH, KSIZE cbNew, void **ppvMap);
423static KU32 kDepDbHashString(const char *pszString, size_t cchString);
424
425
426/** xmalloc wrapper. */
427static void *kDepDbAlloc(KSIZE cb)
428{
429 return xmalloc(cb);
430}
431
432/** free wrapper. */
433static 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 */
446static 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 */
463static 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 */
508static 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 */
560static 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 */
592static 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 */
626static 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 */
652static 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 */
679static 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 */
721static 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 */
794static 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 */
839static 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 */
937static 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) + 64*1024, 256*1024);
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. */
1029static 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. */
1036static 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. */
1043static KU32 kDepDbStrTabLookup(KDEPDBINTSTRTAB const *pStrTab, const char *pszString)
1044{
1045 return kDepDbStrTabLookupN(pStrTab, pszString, strlen(pszString));
1046}
1047
1048
1049/** Wrapper for kDepDbStrTabAddHashed. */
1050static 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 */
1059static 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.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette