/* pbcache.c -- Copyright 1989, 1993, 1994, 1996 Liam R. E. Quin.
* All Rights Reserved.
* This code is NOT in the public domain.
* See the file COPYRIGHT for full details.
*/
#ifndef LINT
static char *RcsId = "@(#) $Id: pbcache.c,v 1.33 1996/08/14 16:55:27 lee Exp lee $";
#endif
/* Block cache for lq-text */
#include "globals.h" /* defines and declarations for database filenames */
#include "error.h"
#include <stdio.h> /* stderr, also for fileinfo.h */
#include <sys/types.h> /* for fileinfo.h, which uses time_t */
#ifdef HAVE_FCNTL_H
# ifdef HAVE_SYSV_FCNTL_H
# include <sys/stat.h>
# endif
# include <fcntl.h>
#endif
#ifdef HAVE_UNISTD_H
# include <unistd.h>
#endif
#ifdef HAVE_STDLIB_H
# include <stdlib.h>
#endif
#include "fileinfo.h" /* for wordinfo.h */
#include "wordinfo.h" /* for t_WID */
#include "pblock.h"
#include "blkheader.h"
#include "block0.h"
#include "emalloc.h"
#include "liblqtext.h"
#include "lqutil.h"
#include "lqtrace.h"
/** Unix system calls that need to be declared: **/
/** C library functions that need to be declared: **/
/** lqtext library functions that need to be declared: **/
/** Functions within this file that need to be declared: **/
PRIVATE void OpenDataBase(
#ifdef HAVE_PROTO
t_LQTEXT_Database *db
#endif
);
PRIVATE void OpenFreeFile(
#ifdef HAVE_PROTO
t_LQTEXT_Database *db
#endif
);
PRIVATE void WriteFreeBlock(
#ifdef HAVE_PROTO
t_LQTEXT_Database *db
#endif
);
#ifdef HAVE_MPOOL
LIBRARY unsigned long ReclaimFreeBlocks(
#ifdef HAVE_PROTO
t_LQTEXT_Database *db,
unsigned long AmountNeeded
#endif
);
PRIVATE void AddMemoryReclaimers(
#ifdef HAVE_PROTO
t_LQTEXT_Database *db
#endif
);
#endif
#define SetBitInByte(Which) (01 << (Which))
/** **/
static int DataFile = -1;
static char BlockCacheIsDirty = 0;
static char FreeBitBlockIsDirty = 0;
#define BLOCKS_PER_CACHE_SEGMENT 128
#define CACHELEN (BLOCKSIZE * BLOCKS_PER_CACHE_SEGMENT)
/* with 64 byte blocks this gives 8 KBytes.
* That's a good size to read/write on a BSD or SunOS file system,
* as that's the underlying block size. On System V, a smaller value
* might be better, but it won't hurt too much. For NFS, 4K is
* probably best, although with NFS 3 it won't make much difference,
* assuming the write-through cache is working OK!
* You can't have MAX_CONTIGUOUS_BLOCKS bigger than 255, however big
* you make BLOCKS_PER_CACHE_SEGMENT, because there's only one byte
* available to store it.
*/
#if (BLOCKS_PER_CACHE_SEGMENT<256)
# define MAX_CONTIGUOUS_BLOCKS (BLOCKS_PER_CACHE_SEGMENT - 1)
#else
# define MAX_CONTIGUOUS_BLOCKS 255
#endif
static unsigned long BlockCacheTimer = 0;
typedef struct s_CacheEntry {
unsigned long CacheStart;
long CacheLen;
int TimeLastUsed;
unsigned char ReadAheadBuffer[CACHELEN];
short IsDirty;
} t_CacheEntry;
/* CACHEDBLOCKS *must* be at least 2, or mayhem will result. */
#define CACHEDBLOCKS 200
static t_CacheEntry **BlockCache = 0;
static t_CacheEntry *CurrentBlock = 0;
static unsigned long FreeBlockStart = 3L;
/* i.e. not a multiple of 2, and hence not a valid value */
#define FREEBITLEN 1024
#define CACHEDFREEBLOCKS 200
#define BYTESPERFREEBIT (BLOCKSIZE*8)
static unsigned char *FreeBitBlock = (unsigned char *) 0;
static unsigned int LowestFreeBlock = 0L;
PRIVATE INLINE int
FindUnsetBitInByte(Value)
unsigned int Value;
{
register int WhichBit = 0;
while (Value & 01) {
Value >>= 1;
WhichBit++;
}
return WhichBit;
}
PRIVATE void
printcache(db)
t_LQTEXT_Database *db;
{
register int i;
fprintf(stderr, "**** cache at %ld is [", BlockCacheTimer);
for (i = 0; i < CACHEDBLOCKS; i++) {
if (BlockCache[i]) {
fprintf(stderr, " %ld-%ld@%d",
BlockCache[i]->CacheStart,
BlockCache[i]->CacheStart + BlockCache[i]->CacheLen,
BlockCache[i]->TimeLastUsed
);
}
}
fprintf(stderr, "]\n");
}
PRIVATE void
LQTpMoveCacheDatesBack(db)
t_LQTEXT_Database *db;
{
if (BlockCacheTimer < 1) {
t_CacheEntry **cpp;
unsigned long Smallest = CurrentBlock->TimeLastUsed;
/* we went round the clock.
* So we'll go round and reduce all the others
*/
/* First, work out what to subtract */
for (cpp = BlockCache; cpp - BlockCache < CACHEDBLOCKS; cpp++) {
if (*cpp) {
register t_CacheEntry *cp2 = *cpp;
if (!Smallest || cp2->TimeLastUsed < Smallest) {
Smallest = cp2->TimeLastUsed;
}
}
}
/* now do the subtraction */
if (Smallest < CACHEDBLOCKS) {
Error(E_FATAL|E_INTERNAL|E_BUG,
"%s: %d; There's a block stuck in the cache [%ul]",
__FILE__, __LINE__, Smallest
);
}
--Smallest;
for (cpp = BlockCache; cpp - BlockCache < CACHEDBLOCKS; cpp++) {
if (*cpp) {
register t_CacheEntry *cp2 = *cpp;
cp2->TimeLastUsed -= Smallest;
if (cp2->TimeLastUsed > BlockCacheTimer) {
BlockCacheTimer = cp2->TimeLastUsed;
}
}
}
/* This won't overflow, because smallest was >= CACHEDBLOCKS,
* which must be at least 2.
*/
++BlockCacheTimer;
}
}
/* <Function>
* <Name>LQT_BlockIsCached
* <Class>Database/Files, Database/Physical
* <Purpose>
* <P>Determine whether the block at a given offset in the data file is
* in the block buffer cache or not.
* Since LQT_ReadBlock returns a pointer into the cache, it is a
* fatal error (E_BUG) if LQT_WriteBlock is called for a block that
* is not cached.</P>
* <P>The cache is always large enough to hold at least the last two
* blocks returned by LQT_ReadBlock.
* This is just enough to ensure that the NextOffset field in a
* block's header can be filled in after allocating the next block
* in a chain.</P>
* <Returns>
* Non-zero if the block is cached, and zero otherwise.
* <Errors>
* Fatal error if the main data file can't be opened or created.
* <Notes>
* As a side-effect, the CurrentBlock variable in pbcache.c is set to
* point to the cached block; this is used internally by the library
* routines in that file.
* <SeeAlso>
* LQT_ReadBlock
* LQT_WriteBlock
* </Function>
*/
API int
LQT_BlockIsCached(db, Block)
t_LQTEXT_Database *db;
unsigned long Block;
{
/* see if the requested block is cached, and, if so, make
* CurrentBlock point to it.
*/
register t_CacheEntry **cpp;
if (DataFile < 0) {
/* clearly it isn't cached if we haven't read or written
* anything yet...
*/
return 0;
}
for (cpp = BlockCache; cpp - BlockCache < CACHEDBLOCKS; cpp++) {
if (*cpp) {
register t_CacheEntry *cp = *cpp;
if (cp->CacheStart <= Block &&
cp->CacheStart + cp->CacheLen >= Block + BLOCKSIZE
) {
/* Note: use CacheLen, not CACHELEN, in case the cache entry
* isn't valid, in which case CacheLen is zero.
*
* Once we've found a block, we move it to the start,
* and move the previous first block to place 2,
* so that we find them quickly next time. This is
* because WriteBlock typically refers to the previous
* block and then the current one.
*/
if (cpp - BlockCache > 3) {
/* we remember the current entry in "cp" */
/* cp = *cpp (already done) */
/* move BlockCache[2] to the current entry */
*cpp = BlockCache[2];
/* move BlockCache[1] to BlockCache[2] */
BlockCache[2] = BlockCache[1];
/* move BlockCache[0] to BlockCache[1] */
BlockCache[1] = BlockCache[0];
/* put the current entry (saved in cp) to the front */
CurrentBlock = BlockCache[0] = cp;
} else {
CurrentBlock = cp;
}
if (++BlockCacheTimer < 1) {
LQTpMoveCacheDatesBack(db);
}
CurrentBlock->TimeLastUsed = BlockCacheTimer;
return 1;
}
}
}
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_BLOCKCACHE)) {
fprintf(stderr, "** IsCached Miss for %ld\n", Block);
printcache(db);
}
#endif
return 0;
}
/* Returns the approximate amount of memory freed */
PRIVATE unsigned long
ReclaimCleanBlocks(db, SpaceNeeded)
t_LQTEXT_Database *db;
unsigned long SpaceNeeded;
{
t_CacheEntry **Oldestp = 0;
t_CacheEntry **cpp;
int BlocksInCache = 0;
int FlushThisMany = 0;
unsigned long AmountSaved = 0;
if (DataFile <= 0) {
if (BlockCacheIsDirty) {
Error(E_BUG|E_MEMORY,
"ReclaimCleanBlocks: DataFile closed, cache is dirty, help!"
);
BlockCacheIsDirty = 0;
}
return 0;
}
/* Count blocks to flush and identify the oldest clean block */
for (cpp = BlockCache; cpp - BlockCache < CACHEDBLOCKS; cpp++) {
if (*cpp) {
register t_CacheEntry *cp = *cpp;
/* We are only interested in blocks that are not dirty.
* Furthermore, we cannot flush the youngest two blocks,
* because they may be in use, even though they are not
* locked. Well, there's no locking code right now anyway.
*/
if (!cp->IsDirty) {
if (!Oldestp || cp->TimeLastUsed < (*Oldestp)->TimeLastUsed) {
Oldestp = cpp;
}
++BlocksInCache;
}
}
}
if (BlocksInCache <= 2 || !Oldestp) {
/* We can't save anything safely */
return 0L;
}
for (FlushThisMany = BlocksInCache - 2; FlushThisMany; FlushThisMany--) {
/* get rid of the oldest entry that we found last time round */
efree((unsigned char *) *Oldestp);
*Oldestp = (t_CacheEntry *) 0;
AmountSaved += sizeof(t_CacheEntry);
if (AmountSaved >= SpaceNeeded) {
return AmountSaved;
}
/* find the next oldest */
Oldestp = 0;
for (cpp = BlockCache; cpp - BlockCache < CACHEDBLOCKS; cpp++) {
if (!(*cpp)->IsDirty) {
if (!Oldestp||(*cpp)->TimeLastUsed < (*Oldestp)->TimeLastUsed) {
Oldestp = cpp;
}
}
}
}
return AmountSaved;
}
PRIVATE void
FlushOneBlock(db, theEntry)
t_LQTEXT_Database *db;
t_CacheEntry *theEntry;
{
int i;
if (DataFile <= 0) {
if (BlockCacheIsDirty) {
Error(E_BUG,
"FlushOneBlock: dirty cache %ld len %ld, fd %d=%s",
theEntry->CacheStart,
theEntry->CacheLen,
DataFile,
db->DataBase
);
BlockCacheIsDirty = 0;
}
return;
}
if (!theEntry->IsDirty) {
return;
}
(void) LQU_Elseek(E_FATAL,
db->DataBase,
"main data file",
DataFile,
(long) theEntry->CacheStart,
SEEK_SET /* = 0 */
);
i = write(
DataFile,
(char *) theEntry->ReadAheadBuffer,
theEntry->CacheLen
);
if (i != theEntry->CacheLen) {
Error(E_FATAL|E_SYS,
"FlushOneBlock: write(%d=%s, 0x%s, %d) failed, returned %d",
DataFile, db->DataBase,
theEntry->ReadAheadBuffer, theEntry->CacheLen,
i
);
}
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_READBLOCK)) {
LQT_Trace(LQTRACE_BLOCKCACHE,
"WRITE entry %d: %ld %d bytes",
i, theEntry->CacheStart, theEntry->CacheLen
);
}
#endif
theEntry->IsDirty = 0;
/* Don't change CacheLen, so that we will still find the block
* if we want it
*/
}
PRIVATE int
CompareCacheStartPoints(e1p, e2p)
t_CacheEntry **e1p, **e2p;
{
/* This is an unstable sort if sizeof(int) < sizeof(long),
* but neighbouring blocks will generally sort together,
* which is all that matters here.
*/
if (!*e1p) {
return 100000;
}
if (!*e2p) {
return -100000;
}
return (int) (*e1p)->CacheStart - (*e2p)->CacheStart;
}
PRIVATE void
SortCache()
{
qsort(
(char *) BlockCache,
CACHEDBLOCKS,
sizeof(t_CacheEntry *),
CompareCacheStartPoints
);
}
/* <Function>
* <Name>LQT_FlushBlockCache
* <Class>Database/Files, Database/Physical
* <Purpose>
* <P>Writes any pending dirty blocks to the disk.
* Copies of the blocks are retained in memory, however, until
* LQT_CloseDatabase is called, and will be found by LQT_BlockIsCached
* and hence by LQT_ReadBlock if an attempt is made to read
* them again.</P>
* <P>When a database is opened, LQT_OpenDatabase adds LQT_FlushBlockCache
* as an action to be performed automatically whenever the database
* is flushed or closed. It should not be necessary to call this code
* directly from outside the library, and it is made available primarily
* to aid in debugging.</P>
* <Errors>
* Fatal error (E_BUG) if the cache is dirty in read-only mode.
* <SeeAlso>
* LQT_AddActionOnClose
* LQT_OpenDatabase
* LQT_SyncDatabase
* LQT_CloseDatabase
* </Function>
*/
LIBRARY int
LQT_FlushBlockCache(db)
t_LQTEXT_Database *db;
{
t_CacheEntry *Oldest = 0;
t_CacheEntry **cpp;
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_READBLOCK)) {
LQT_Trace(LQTRACE_BLOCKCACHE, "cache flush:");
}
#endif
if (DataFile < 0) {
if (BlockCacheIsDirty) {
Error(E_WARN|E_INTERNAL,
"\"data\" isn't open but cache is dirty %ld len %ld, fd %d=%s",
CurrentBlock->CacheStart,
CurrentBlock->CacheLen,
DataFile,
db->DataBase
);
BlockCacheIsDirty = 0;
}
return 0;
}
/* If we sort the cache by block number first, the writes
* would be in ascending order, minimising disk seeks.
*/
SortCache();
for (cpp = BlockCache; cpp - BlockCache < CACHEDBLOCKS; cpp++) {
if (*cpp) {
register t_CacheEntry *cp = *cpp;
if (!Oldest || cp->TimeLastUsed < Oldest->TimeLastUsed) {
Oldest = cp;
}
if (cp->CacheLen && cp->IsDirty) {
FlushOneBlock(db, cp);
}
}
}
BlockCacheIsDirty = 0;
CurrentBlock = Oldest;
if (FreeBitBlockIsDirty) {
WriteFreeBlock(db);
}
#ifdef ASCIITRACE
/* check the result! */
if (LQT_TraceFlagsSet(LQTRACE_READAFTERWRITE|LQTRACE_WIDCACHE)) {
(void) LQT_GetMaxWID(db);
}
if (LQT_TraceFlagsSet(LQTRACE_READBLOCK)) {
LQT_Trace(LQTRACE_BLOCKCACHE, "cache flushed");
}
#endif
return 0;
}
/* <Function>
* <Name>LQT_FlushOneBlockFromCache
* <Class>Database/Files, Database/Physical
* <Purpose>
* <P>If there any data blocks that are waiting to be written out
* to disk, LQT_FlushOneBlockFromCache will write one of them out.</P>
* <P>This function is internal to lq-text and users of the Physical
* layer of the database.</P>
* <Errors>
* Fatal error (E_BUG) if the cache is dirty in read-only mode.
* <SeeAlso>
* LQT_FlushBlockCache
* </Function>
*/
LIBRARY int
LQT_FlushOneBlockFromCache(db)
t_LQTEXT_Database *db;
{
t_CacheEntry *Oldest = 0;
t_CacheEntry **cpp;
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_READBLOCK)) {
LQT_Trace(LQTRACE_BLOCKCACHE, "(flush one block from cache)");
}
#endif
if (DataFile < 0) {
if (BlockCacheIsDirty) {
Error(E_BUG|E_WARN,
"\"data\" is not open but cache is dirty %ld len %ld, fd %d=%s",
CurrentBlock->CacheStart,
CurrentBlock->CacheLen,
DataFile,
db->DataBase
);
BlockCacheIsDirty = 0;
}
return 0;
}
/* check that the cache is in fact full:
* if so, find the oldest block and free it;
* if not, allocate a new block that we can use.
*/
for (cpp = BlockCache; cpp - BlockCache < CACHEDBLOCKS; cpp++) {
if (*cpp) {
register t_CacheEntry *cp = *cpp;
if (!Oldest || cp->TimeLastUsed < Oldest->TimeLastUsed) {
Oldest = *cpp;
}
} else {
/* a virgin block --
* this only happens the first few times!
* (it's wearing white socks...)
*/
/* allocate a nw cache entry */
*cpp = (t_CacheEntry *) emalloc("CacheEntry", sizeof(t_CacheEntry));
/*INITACHE*/
(*cpp)->CacheStart = 0;
(*cpp)->CacheLen = 0;
(*cpp)->TimeLastUsed = 0;
(*cpp)->IsDirty = 0;
Oldest = *cpp;
break;
}
}
CurrentBlock = Oldest;
if (CurrentBlock->CacheLen && CurrentBlock->IsDirty) {
FlushOneBlock(db, CurrentBlock);
}
return 0;
}
#ifdef WIDINBLOCK
static int WIDDebugFile = -1;
static t_WID *WIDDebugArray;
#define WID_DEBUG_LENGTH 1500000
static unsigned long WIDLargestOffset;
PRIVATE void
LQTpEndWIDDebugging(db)
t_LQTEXT_Database *db;
{
if (WIDDebugFile > 0) {
int i;
(void) LQU_Elseek(E_FATAL,
"widfile.dbg",
"WID debug file",
WIDDebugFile,
0L,
SEEK_SET /* = 0 */
);
i = write(
WIDDebugFile,
WIDDebugArray,
(WIDLargestOffset / BLOCKSIZE) * sizeof(t_WID)
);
if (i != sizeof(t_WID) * WID_DEBUG_LENGTH) {
Error(E_WARN|E_SYS,
"write: widfile.dbg: wrote %d bytes, not %d",
i,
sizeof(t_WID) * WID_DEBUG_LENGTH
);
}
(void) close(WIDDebugFile);
WIDDebugFile = 0;
}
}
PRIVATE void
LQTpStartWIDDebugging(db)
t_LQTEXT_Database *db;
{
int Flags, Modes;
char *theFile = LQU_joinstr3(db->DatabaseDir, "/", "widfile.dbg");
LQT_GetFileModes(db, &Flags, &Modes);
WIDDebugFile = LQU_Eopen(E_FATAL, theFile, "WID debug file", Flags, Modes);
{
int i;
WIDDebugArray = (t_WID *) emalloc(
"WID debug array",
sizeof(t_WID) * WID_DEBUG_LENGTH
);
i = read(WIDDebugFile, WIDDebugArray, sizeof(t_WID)*WID_DEBUG_LENGTH);
if (i < 0) {
Error(E_FATAL|E_SYS, "can't read %ld bytes from wid debug file %s",
sizeof(t_WID) * WID_DEBUG_LENGTH,
theFile
);
}
WIDLargestOffset = (i / sizeof(t_WID)) * BLOCKSIZE;
LQT_AddActionOnClose(
db,
"Save WID debugging data",
LQTpEndWIDDebugging,
LQT_ON_CLOSE|LQT_ON_SYNC
);
}
}
LIBRARY t_WID
LQTpGetWIDofBlock(db, Offset)
t_LQTEXT_Database *db;
unsigned long Offset;
{
if (WIDDebugFile < 0) {
LQTpStartWIDDebugging(db);
}
if (Offset > WIDLargestOffset) {
return (t_WID) 0;
} else {
return WIDDebugArray[Offset / BLOCKSIZE];
}
}
LIBRARY void
LQTpSetWIDofBlock(db, Offset, WID)
t_LQTEXT_Database *db;
unsigned long Offset;
t_WID WID;
{
if (WIDDebugFile < 0) {
LQTpStartWIDDebugging(db);
}
if (Offset >= WID_DEBUG_LENGTH * BLOCKSIZE) {
return;
}
if (Offset > WIDLargestOffset) {
WIDLargestOffset = Offset;
}
WIDDebugArray[Offset / BLOCKSIZE] = WID;
}
#endif /* WIDINBLOCK */
/* <Function>
* <Name>LQT_WriteBlock
* <Class>Database/Files, Database/Physical
* <Purpose><P>
* Writes the given block to the database. Actually the block is
* saved in the cache, and if it was originally obtained with
* LQT_ReadBlock it's already in the cache, so LQT_WriteBlock simply
* marks it as dirty, needing to be saved. If you change data in a
* block without calling LQT_WriteBlock, the changes usually won't be
* written to disk (unless an adjacent block in the cache is written).
* </P>
* <P>The block must have a valid header; if the block's length field is
* larger than the Length argument, the extra blocks are marked as free.
* The header is described in <h>blkheader.h</h>.
* </P>
* <Errors>
* Format or consistency errors are generally fatal.
* Attempting to write a block not in the cache will produce a warning.
* <SeeAlso>
* LQT_FindFreeBlock
* LQT_ReadBlock
* LQT_WriteBlock
* </Function>
*/
API void
#ifdef ASCIITRACE
LQTp_WriteBlock(db, theFile, theLine, Block, Data, Length, theWID)
t_LQTEXT_Database *db;
char *theFile;
int theLine;
#else
LQT_WriteBlock(db, Block, Data, Length, theWID)
t_LQTEXT_Database *db;
#endif
unsigned long Block;
unsigned char *Data;
int Length;
t_WID theWID;
{
t_BlockHeader *H;
int MaxLength;
unsigned OffsetInBlock;
if (DataFile < 0) {
OpenDataBase(db);
}
if (!Data) {
Error(E_BUG,
#ifdef ASCIITRACE
"%s: %d: %s: %d: LQT_WriteBlock %ld, 0x0: second argument (Data) is invalid",
theFile, theLine,
__FILE__, __LINE__,
#else
"LQT_WriteBlock %ld, 0x0: second argument (Data) is invalid",
#endif
Block
);
}
H = (t_BlockHeader *) Data;
MaxLength = H->NumberOfBlocks;
#ifdef WIDINBLOCK
# ifndef ASCIITRACE
how did this happen? check Makefile includes either both
-DWIDINBLOCK and -DASCIITRACE
or neither
# endif
if (H->WID != theWID) {
Error(E_INTERNAL|E_WARN,
"%s: %d: %s: %d: LQT_WriteBlock 0x%x: WID %ld != BH->WID %ld (next %ld)",
theFile, theLine,
__FILE__, __LINE__,
Block,
theWID,
H->WID,
H->NextOffset
);
}
#endif /* WIDINBLOCK */
if (!MaxLength) {
Error(E_INTERNAL|((MaxLength > 0) ? E_WARN : (E_BUG|E_FATAL)),
#ifdef ASCIITRACE
"%s: %d: %s: %d: LQT_WriteBlock 0%o: WID=%ld: Length=%d, BH->l=0",
theFile, theLine,
#else
"%s: %d: LQT_WriteBlock 0%o: WID=%ld: Length=%d, BH->l 0",
#endif
__FILE__, __LINE__,
theWID, Length
);
Length = H->NumberOfBlocks;
}
if (!Length) {
Error(E_INTERNAL|((MaxLength > 0) ? E_WARN : (E_BUG|E_FATAL)),
#ifdef ASCIITRACE
"%s: %d: %s: %d: LQT_WriteBlock 0%o: WID %ld: Length 0, BH->l %d",
theFile, theLine,
#else
"%s: %d: LQT_WriteBlock 0%o: WID %ld: Length 0, BH->l %d",
#endif
__FILE__, __LINE__,
theWID, MaxLength
);
Length = H->NumberOfBlocks;
}
{
unsigned long unwantedOffset = Block + (MaxLength * BLOCKSIZE);
while (MaxLength > Length) {
--MaxLength;
/* e.g. if MaxLength is 2 and Length is 1, we must free
* block number "Block + 1"
*/
unwantedOffset -= BLOCKSIZE;
LQT_SetBlockStatus(db, unwantedOffset, SET_BLOCK_AS_FREE);
}
}
H->NumberOfBlocks = Length;
if (theWID != (t_WID) 0 && H->NextOffset == 0L) {
LQT_SetLastBlockInChain(
db,
theWID,
&Block,
&Data[(Length * BLOCKSIZE) - 1],
Data
);
}
if (!LQT_BlockIsCached(db, Block)) {
/* With an in-place cache this is a distaster, it means that
* the block got swapped out while it was in use!
*/
Error(E_WARN|E_INTERNAL,
#ifdef ASCIITRACE
"%s: %d: %s: %d: LQT_WriteBlock %ld not in cache!",
theFile, theLine,
#else
"%s: %d: LQT_WriteBlock %ld not in cache!",
#endif
__FILE__, __LINE__,
Block
);
printcache(db);
(void) LQT_ReadBlock(db, Block, theWID);
/* so that the cache gets full;
* this isn't so bad as we're likely to want the other blocks
* in the cache... and I/O is in 8K chunks anyway. We ought to
* check that this block isn't 8K long, though...
*/
}
OffsetInBlock = Block - CurrentBlock->CacheStart;
if (Length > 1) {
if (OffsetInBlock + Length*BLOCKSIZE > CACHELEN) {
#ifdef ASCIITRACE
Error(E_BUG,
"%s: %d: %s: %d: LQT_WriteBlock: offset %ld, length %ld overran cache at %ld by %d bytes",
__FILE__, __LINE__,
theFile, theLine,
Block,
Length,
CurrentBlock->CacheStart,
(OffsetInBlock + Length*BLOCKSIZE) - CACHELEN
);
#else
Error(E_BUG,
"LQT_WriteBlock: offset %ld, length %ld overran cache at %ld by %d bytes",
Block,
Length,
CurrentBlock->CacheStart,
(OffsetInBlock + Length*BLOCKSIZE) - CACHELEN
);
#endif
}
}
if (Data != &CurrentBlock->ReadAheadBuffer[OffsetInBlock]) {
Error(E_INTERNAL|E_WARN,
#ifdef ASCIITRACE
"%s: %d: %s: %d: LQT_WriteBlock %ld: WID %ld: data at 0x%x not returned by LQT_ReadBlock 0x%x",
theFile, theLine,
__FILE__, __LINE__,
#else
"LQT_WriteBlock %ld: WID %ld: data at 0x%x not returned by LQT_ReadBlock 0x%x",
#endif
Block, theWID, Data,
&CurrentBlock->ReadAheadBuffer[OffsetInBlock]
);
bcopy(
Data,
(char *) &CurrentBlock->ReadAheadBuffer[OffsetInBlock],
BLOCKSIZE * Length
);
}
if (++BlockCacheTimer < 1) {
LQTpMoveCacheDatesBack(db);
}
CurrentBlock->TimeLastUsed = BlockCacheTimer;
CurrentBlock->IsDirty = 1;
BlockCacheIsDirty = 1;
#ifdef WIDINBLOCK
LQTpSetWIDofBlock(Block, theWID);
#endif
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_WRITEBLOCK)) {
LQT_Trace(LQTRACE_WRITEBLOCK,
"WROTE %ld len %d Next %ld",
Block,
Length,
H->NextOffset
);
}
#endif
return;
}
PRIVATE void
OpenDataBase(thedb)
t_LQTEXT_Database *thedb;
{
int Flags, Modes;
LQT_GetFileModes(thedb, &Flags, &Modes);
DataFile = LQU_Eopen(E_FATAL, thedb->DataBase, "match data", Flags, Modes);
if (!BlockCache) {
BlockCache = (t_CacheEntry **) ecalloc(
"block buffer cache",
sizeof(t_CacheEntry *),
CACHEDBLOCKS
);
}
/* LQT_WriteVersionToDatabase and LQT_CheckDatabaseVersion() MUST do a
* LQT_ReadBlock(0) immediately,
* so that the cache gets initialised properly.
*/
LQT_CheckDatabaseVersion(thedb);
(void) LQT_GetMaxWID(thedb);
#ifdef HAVE_MPOOL
AddMemoryReclaimers(thedb);
#endif
}
static int FreeFile = -1;
/* Pages in the cache are FREEBITLEN bytes long, and each represent
* FREEBITLEN * 8 blocks (one per bit in each of FREEBITLEN 8-bit bytes).
*/
#define PAGENO_TO_BLOCK(pageNumber) ((pageNumber) * BYTESPERFREEBIT * FREEBITLEN)
/* The reverse transformation is harder, as we have to round down to
* get the start of the block.
*/
#define BLOCK_TO_PAGENO(blockNumber) \
((unsigned long) (blockNumber / (FREEBITLEN * BYTESPERFREEBIT)))
#ifdef bsddb
# define HAVE_MPOOL probably_ok
#endif
#ifdef HAVE_MPOOL
/* In this case we have the mpool(3) routines, and can use them to
* get a considerable performance improvement with the free block code.
* Except, this code is broken for some reason.
*/
# include <db.h>
# include <mpool.h>
static MPOOL *FreePool = 0;
PRIVATE void
OpenFreePool(FileName)
char *FileName;
{
if (FreePool) {
Error(E_FATAL|E_INTERNAL|E_BUG,
"%s: -- OpenFreePool: already open", FileName
);
}
FreePool = mpool_open((DBT *) NULL,
FreeFile,
(pgno_t) FREEBITLEN,
(pgno_t) CACHEDBLOCKS
);
if (!FreePool) {
Error(E_FATAL|E_SYS, "couldn't open free bit cache \"%s\"", FileName);
}
}
PRIVATE void
SyncFreePool(db)
t_LQTEXT_Database *db;
{
if (!FreePool) return;
if (mpool_sync(FreePool) < 0) {
Error(E_SYS|E_WARN, "Problem sync'ing freelist pool");
}
FreeBitBlockIsDirty = 0;
}
PRIVATE void
CloseFreePool(db)
t_LQTEXT_Database *db;
{
if (!FreePool) {
Error(E_WARN|E_INTERNAL|E_BUG,
"%s: %d: FreePool NULL in CloseFreePool",
__FILE__, __LINE__
);
}
SyncFreePool(db);
if (mpool_close(FreePool) < 0) {
Error(E_SYS|E_WARN, "Problem closing freelist pool");
}
FreePool = (MPOOL *) 0;
close(FreeFile);
FreeFile = -1;
FreeBitBlockIsDirty = 0;
}
LIBRARY unsigned long
ReclaimFreeBlocks(db, AmountNeeded)
t_LQTEXT_Database *db;
unsigned long AmountNeeded;
{
if (!FreePool) {
return 0;
}
SyncFreePool(db);
CloseFreePool(db);
return AmountNeeded; /* guess */
}
PRIVATE void
AddMemoryReclaimers(db)
t_LQTEXT_Database *db;
{
/* If we run low on space, we can shrink the cache */
LQU_AddMemoryReclaimFunction(thedb, ReclaimCleanBlocks);
/* If that doesn't work, we can shrink the free block cache */
LQU_AddMemoryReclaimFunction(thedb, ReclaimFreeBlocks);
}
static unsigned char *currentPoolPage = 0;
PRIVATE void ReadFreeBitBlock(
#ifdef HAVE_PROTO
t_LQTEXT_Database *db,
unsigned long BlockNumber
#endif
);
PRIVATE void
WriteFreeBlock(db)
t_LQTEXT_Database *db;
{
if (!FreePool) {
Error(E_FATAL|E_BUG|E_INTERNAL,
"%s: %d: WriteFreeBlock/FreePool Null for %lu",
__FILE__, __LINE__, FreeBlockStart
);
}
if (!currentPoolPage) {
return;
}
if (mpool_put(
FreePool,
currentPoolPage,
FreeBitBlockIsDirty ? MPOOL_DIRTY : 0
) < 0
) {
Error(E_WARN|E_SYS, "WriteFreeBlock(%lu): mpool_put: ",
FreeBlockStart
);
}
FreeBitBlockIsDirty = 0;
}
PRIVATE void
ReadFreeBitBlock(db, BlockNumber)
t_LQTEXT_Database *db;
unsigned long BlockNumber;
{
unsigned long PageNumber;
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_FREEBLOCKS)) {
LQT_Trace(LQTRACE_FREEBLOCKS,
"<ReadFreeBitBlock where=%ld>",
BlockNumber
);
}
#endif
if (FreeFile < 0) {
OpenFreeFile(db);
}
/* Read the free bitmap for the block containing the bit that tells us
* whether the given Block Number is free or used...
*/
if (!FreePool) {
Error(E_FATAL|E_BUG|E_INTERNAL,
"%s: %d: FetchFreeBitPage/FreePool Null for %lu",
__FILE__, __LINE__, BlockNumber
);
}
if (FreeBitBlockIsDirty) {
WriteFreeBlock(db);
}
PageNumber = BLOCK_TO_PAGENO(BlockNumber);
currentPoolPage = mpool_get(FreePool, PageNumber, (u_int) 0);
if (!currentPoolPage) {
pgno_t returnedPageNumber;
/* allocate a new page */
do {
currentPoolPage = mpool_new(
FreePool,
&returnedPageNumber
);
if (!currentPoolPage) {
Error(E_FATAL|E_SYS,
"mpool_new returned NULL for %lu",
PageNumber
);
}
bzero(currentPoolPage, FREEBITLEN);
} while (returnedPageNumber != PageNumber);
}
FreeBitBlock = (unsigned char *) currentPoolPage;
FreeBitBlockIsDirty = 0;
/* The free block now contains the single bit representing the
* given block number, but it might not start with that bit:
*/
FreeBlockStart = PAGENO_TO_BLOCK(PageNumber);
}
#else
PRIVATE void
WriteFreeBlock(db)
t_LQTEXT_Database *db;
{
int i;
unsigned long OffsetInFile;
if (FreeFile < 0 || !FreeBitBlockIsDirty) {
return;
}
OffsetInFile = FreeBlockStart / (BLOCKSIZE * 8);
(void) LQU_Elseek(E_FATAL,
db->FreeFileName,
"free block bitmap",
FreeFile,
(long) OffsetInFile,
SEEK_SET /* = 0 */
);
i = write(FreeFile, FreeBitBlock, FREEBITLEN);
if (i != FREEBITLEN) {
Error(E_FATAL|E_SYS,
"WriteFreeBlock: write(%d=\"%s\", 0x%x, %d) returned %d",
FreeFile, db->FreeFileName, FreeBitBlock, FREEBITLEN, i);
}
FreeBitBlockIsDirty = 0;
}
PRIVATE void
ReadFreeBitBlock(db, Where)
t_LQTEXT_Database *db;
long Where;
{
long AmountRead;
unsigned long OffsetInFile;
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_FREEBLOCKS)) {
LQT_Trace(LQTRACE_FREEBLOCKS,
"<ReadFreeBitBlock where=%ld>",
Where
);
}
#endif
if (FreeFile < 0) {
OpenFreeFile(db);
}
OffsetInFile = Where / BYTESPERFREEBIT;
/* Round FREEBITLEN down to the start of the block */
OffsetInFile /= FREEBITLEN;
OffsetInFile *= FREEBITLEN;
if (OffsetInFile * BYTESPERFREEBIT == FreeBlockStart) {
return;
}
if (FreeBitBlockIsDirty) {
WriteFreeBlock(db);
}
(void) LQU_Elseek(E_FATAL,
db->FreeFileName,
"block free/used bitmap",
FreeFile,
(long) OffsetInFile,
SEEK_SET /* = 0 */
);
AmountRead = read(FreeFile, FreeBitBlock, FREEBITLEN);
if (AmountRead < 0) {
Error(E_FATAL|E_SYS,
"ReadFreeBlock: read(%d=\"%s\", ...) returned %d, not %d",
FreeFile, db->FreeFileName, AmountRead, FREEBITLEN
);
}
FreeBlockStart = OffsetInFile * BYTESPERFREEBIT;
/* If we have gone past the end of the file, set the rest of the
* block to zeros.
*/
if (AmountRead < FREEBITLEN) {
(void) bzero(&FreeBitBlock[AmountRead], FREEBITLEN - AmountRead);
}
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_FREEBLOCKS)) {
LQT_Trace(LQTRACE_FREEBLOCKS,
"</ReadFreeBitBlock FreeBlockStart %ld>",
FreeBlockStart
);
}
#endif
}
#endif /* HAVE_MPOOL */
/* For efficiency, we keep a bitmap in memory: each bit refers to
* a single block in the freeblocks bitmap. Each bit in that freeblock in
* turn refers to a data block.
* Hence, for a maximum 4Gbyte data file, we need
* 4G / (DATABLOCKSIZE * 8) --> max size of freeblocks
* freeblocks.maxsize / (FREEBITLEN * 8) --> number of bytes we need.
* When DATABLOCKSIZE is 64 and FREEBITLEN is also 64, we need
* 16384 bytes for the free block bitmap.
* In practice, FREEBITLEN is usually 1024 or 8192 bytes, and that means
* we only need 1KByte.
*
* On a 64-bit computer, you could configure lq-text to make much larger
* databases, and then you might need more than would fit in memory.
* Hence, we use 2K and assume it doesn't all fit into memory.
*/
#ifdef BROKEN
unsigned long FreeBitBlockBitmapStart;
PRIVATE int FreeBitBlockBitmapFile = -1;
#define FREE_BIT_BIT_LENGTH 2048
PRIVATE unsigned char *FreeBitBlockBitmapData;
PRIVATE char FreeBitBitBlockIsDirty = 0;
PRIVATE void
WriteFreeBitBlockToDisk(db)
t_LQTEXT_Database *db;
{
int nbytes;
if (!FreeBitBitBlockIsDirty) {
return;
}
(void) LQU_Elseek(E_FATAL,
"freelist.bit",
"bit map of free block bitmap",
FreeBitBlockBitmapFile,
FreeBitBlockBitmapStart,
SEEK_SET /* = 0 */
);
nbytes = write(
FreeBitBlockBitmapFile, FreeBitBlockBitmapData, FREE_BIT_BIT_LENGTH
);
if (nbytes == -1) {
Error(E_FATAL|E_SYS, "%s: couldn't save bitbit data", "freelist.bit");
} else if (nbytes != FREE_BIT_BIT_LENGTH) {
Error(E_FATAL|E_SYS, "%s: wrote %d bytes of freelist.bit, not %d",
nbytes, FREE_BIT_BIT_LENGTH
);
}
FreeBitBitBlockIsDirty = 0;
}
PRIVATE void
LoadFreeBitmapBitmap(db)
t_LQTEXT_Database *db;
{
int Flags, Modes;
char *tmp;
tmp = emalloc("free bit bit name", strlen(db->FreeFileName) + 4);
(void) sprintf(tmp, "%s.bit", db->FreeFileName);
LQT_GetFileModes(db, &Flags, &Modes);
FreeBitBlockBitmapFile = LQU_Eopen(E_FATAL,
tmp, "free block bitmap bitmap [sic]", Flags, Modes
);
FreeBitBlockBitmapData = (unsigned char *)
emalloc("free bitbit data", FREE_BIT_BIT_LENGTH);
FreeBitBlockBitmapStart = 3L; /* so we read the real one */
LoadFreeBitBitBlock(db, 0L);
efree(tmp);
}
PRIVATE void
LoadFreeBitBitBlock(db, BlockInBitBitmap)
t_LQTEXT_Database *db;
unsigned long BlockInBitBitmap;
{
int nbytes;
if (!FreeBitBlockBitmapData) {
LoadFreeBitmapBitmap(db);
}
if (FreeBitBitBlockIsDirty) {
WriteFreeBitBlockToDisk(db);
}
if (BlockInBitBitmap == FreeBitBlockBitmapStart) {
return; /* it's already there */
}
(void) LQU_Elseek(E_FATAL,
"freelist.bit",
"bit map of free block bitmap",
FreeBitBlockBitmapFile,
BlockInBitBitmap,
SEEK_SET /* = 0 */
);
FreeBitBlockBitmapStart = BlockInBitBitmap;
nbytes = read(
FreeBitBlockBitmapFile, FreeBitBlockBitmapData, FREE_BIT_BIT_LENGTH
);
if (nbytes == -1) {
Error(E_FATAL|E_SYS, "%s: couldn't read bitbit data", "freelist.bit");
}
if (nbytes == 0) {
(void) bzero(FreeBitBlockBitmapData, FREE_BIT_BIT_LENGTH);
} else if (nbytes != FREE_BIT_BIT_LENGTH) {
Error(E_FATAL|E_INTERNAL, "%s: read %d bytes, expected %d",
"freelist.bit", nbytes
);
}
FreeBitBitBlockIsDirty = 0;
}
PRIVATE void
SetFreeBitBitStatusForFreeBlock(db, FreeBlock, Status)
t_LQTEXT_Database *db;
unsigned long FreeBlock;
int Status;
{
unsigned long ByteInBitBitmap;
unsigned long BlockInBitBitmap;
register unsigned char *p;
ByteInBitBitmap = FreeBlock / (8 * FREEBITLEN);
BlockInBitBitmap = ByteInBitBitmap / FREE_BIT_BIT_LENGTH;
if (ByteInBitBitmap < FreeBitBlockBitmapStart) {
LoadFreeBitBitBlock(db, BlockInBitBitmap);
}
p = &FreeBitBlockBitmapData[ByteInBitBitmap - FreeBitBlockBitmapStart];
if (*p == 0xFF && (Status == SET_BLOCK_AS_USED)) {
/* no change */
return;
} else if (*p == 0 && (Status == SET_BLOCK_AS_FREE)) {
return;
} else {
/* Find if our bit is set to zero */
unsigned int ui;
unsigned char OldValue = (*p);
/* We have:
* The byte offset of the free block we're interested in,
* measured from the start of the Free Bitmap.
* The byte offset of the byte containing the single bit in
* the free bitmap bitmap corresponding to that block.
* We need:
* The actual bit address within the byte.
*/
ui = (FreeBlock / FREEBITLEN);
if (Status == SET_BLOCK_AS_FREE) {
*p &= (unsigned char)~(unsigned char) SetBitInByte(ui & 07);
} else {
*p |= (unsigned char) SetBitInByte(ui & 07);
}
if (*p != OldValue) {
FreeBitBitBlockIsDirty = 1;
}
}
}
PRIVATE void
ABlockMightBeFreeInFreeBlock(db, FreeBlock)
t_LQTEXT_Database *db;
unsigned long FreeBlock;
{
unsigned long ByteInBitBitmap;
unsigned long BlockInBitBitmap;
register unsigned char *p;
ByteInBitBitmap = FreeBlock / (8 * FREEBITLEN);
BlockInBitBitmap = ByteInBitBitmap / FREE_BIT_BIT_LENGTH;
if (ByteInBitBitmap < FreeBitBlockBitmapStart) {
LoadFreeBitBitBlock(db, BlockInBitBitmap);
}
p = &FreeBitBlockBitmapData[ByteInBitBitmap - FreeBitBlockBitmapStart];
if (*p == 0xFF) {
/* the whole block of blocks is full, so no point looking further */
return;
} else {
/* Find if our bit is set to zero */
unsigned int ui;
/* We have:
* The byte offset of the free block we're interested in,
* measured from the start of the Free Bitmap.
* The byte offset of the byte containing the single bit in
* the free bitmap bitmap corresponding to that block.
* We need:
* The actual bit address within the byte.
*/
ui = (FreeBlock / FREEBITLEN);
if ((*p) & SetBitInByte(ui & 07)) {
return; /* nope */
}
}
return;
}
PRIVATE unsigned long
FindLowestCandidateForFreeBlock(db, NoLowerThan)
t_LQTEXT_Database *db;
unsigned long NoLowerThan;
{
unsigned long BlockInFreeList;
unsigned long BlockInFreeBitBitList;
/* NoLowerThan is a byte offset in the main data file.
* Our job is to find an approximate place where there's a free block
* in the data file no lower than NoLowerThan.
* We do this by returning an address that's at the start of a
* block in the free block bitmap, where that free block bitmap block
* contains at least one free block. The caller than has to find the
* free block by scanning the bitmap.
*/
/* First, round NoLowerThan down to a multiple of the free
* bit block size to find the starting block number in the
* free block bitmap:
*/
BlockInFreeList = NoLowerThan / (BYTESPERFREEBIT * FREEBITLEN);
NoLowerThan = BlockInFreeList * (BYTESPERFREEBIT * FREEBITLEN);
/* next, find the FreeBitBit block containing the bit representing
* the freelist block which contains a bit representing NoLowerThan
*/
BlockInFreeBitBitList = BlockInFreeList /
(FREEBITLEN * 8 * FREE_BIT_BIT_LENGTH);
/* Actually, we work with byte offsets and not block numbers: */
BlockInFreeBitBitList *= FREE_BIT_BIT_LENGTH;
/* now, find the first zero bit in that FreeBitBit block, or in a higher
* block
*/
for (;;) {
register unsigned char *p;
/* load the block (TODO: check if it's already loaded!)
* note that eventually this loop will end up allocating a new
* block, because we'll call LoadFreeBitBitBlock with a 2nd
* argument that's larger than the current free list. This block
* will be initialised by LoadFreeBitBitBlock to contain all zeros,
* and hene we'll eventually find a free block.
*/
LoadFreeBitBitBlock(db, BlockInFreeBitBitList);
for (p = FreeBitBlockBitmapData;
p - FreeBitBlockBitmapData < FREE_BIT_BIT_LENGTH;
p++
) {
if (*p != 0xFF) {
/* found a zero --> return the block number */
/* the byte in the free block bitmap bitmap file: */
LowestFreeBlock =
(p - FreeBitBlockBitmapData) + FreeBitBlockBitmapStart;
/* convert to the exact bit offset: */
LowestFreeBlock *= 8;
LowestFreeBlock += FindUnsetBitInByte( (unsigned int) *p);
/* each bit in this file represents an entire free block */
LowestFreeBlock *= FREEBITLEN;
/* now we have a byte address in the free block bitmap file */
LowestFreeBlock *= BYTESPERFREEBIT;
return LowestFreeBlock;
}
}
/* nope, that block was all used! */
BlockInFreeBitBitList += FREE_BIT_BIT_LENGTH;
}
}
#endif /*BROKEN*/
PRIVATE void
OpenFreeFile(db)
t_LQTEXT_Database *db;
{
int Flags, Modes;
LQT_GetFileModes(db, &Flags, &Modes);
FreeFile = LQU_Eopen(E_FATAL,
db->FreeFileName, "free block bitmap", Flags, Modes
);
#ifdef HAVE_MPOOL
OpenFreePool(db->FreeFileName);
FreeBitBlock = 0;
#else /* !HAVE_MPOOL */
if (FreeBitBlock) {
efree((char *) FreeBitBlock);
}
FreeBitBlock = (unsigned char *) emalloc("Free Bit Block", FREEBITLEN);
#endif /* HAVE_MPOOL */
LQT_AddActionOnClose(
db,
"Write out cached freelist blocks",
#ifdef HAVE_MPOOL
(int (*)()) CloseFreePool,
#else
(int (*)()) WriteFreeBlock,
#endif
LQT_ON_CLOSE|LQT_ON_SYNC
);
ReadFreeBitBlock(db, 0L);
if (LQT_BlockIsFree(db, 0L)) {
/* A new database */
unsigned long Reserved = 0L;
do {
LQT_SetBlockStatus(db, Reserved, SET_BLOCK_AS_USED);
Reserved += BLOCKSIZE;
} while (Reserved + BLOCKSIZE <= BLOCK_ZERO_RESERVEDBYTES);
LowestFreeBlock = Reserved;
} else {
/* an existing database; guess the lowest free block
* Actually if this was stored in block0 we might get a
* really big win, but I would need to improve the
* way I keep track of its value to get maximum benefit.
*/
LowestFreeBlock = BLOCK_ZERO_RESERVEDBYTES;
}
}
#define ReadNextFreeBitBlock(db) \
ReadFreeBitBlock(db, FreeBlockStart + (BYTESPERFREEBIT * FREEBITLEN + 1))
/* <Function>
* <Name>LQT_FindFreeBlock
* <Class>Database/Physical
* <Purpose>
* Allocates a block from the free list, and marks it as in use.
* The block is at least BLOCKSIZE bytes long, and may be longer,
* as contiguous free blocks are combined to make a single longer
* block as long as will fit in a single cache entry.
* If the BytesWanted argument is non-zero, the block will not
* be more than BLOCKSIZE bytes longer than than BytesWanted bytes.
* Since LQT_FindFreeBlock does not actually read the data from the
* disk (or cache), it is up to the caller to ensure that LQT_ReadBlock
* is called, and that the resulting block's header is filled in with
* NumberOfBlocks equal to the value that LQT_FindFreeBlock stored in
* *BlockLengthp.
* <Returns>
* the byte offset in the data file of the block allocated, and also
* the number of blocks allocated (in BlockLengthp).
* <SeeAlso>
* LQT_BlockIsCached
* LQT_BlockIsFree
* LQT_SetBlockStatus
* </Function>
*/
API unsigned long
LQT_FindFreeBlock(db, WID, BlockLengthp, BytesWanted)
t_LQTEXT_Database *db;
t_WID WID;
unsigned int *BlockLengthp;
unsigned long BytesWanted;
{
register unsigned char *p;
int GotOne = 0;
unsigned long Here = 0;
if (FreeFile < 0) {
OpenFreeFile(db); /* OpenFreeFile() calls ReadFreeBitBlock(0L) */
}
if (LowestFreeBlock && LQT_BlockIsFree(db, LowestFreeBlock)) {
Here = LowestFreeBlock;
GotOne = 1;
}
/* search the free bit bitmap to find a possible freelist block to search
* for a free block. The idea is to avoid looking at every block in
* the freelist, as that's too slow.
*/
if (!GotOne) {
do {
#ifdef BROKEN
LowestFreeBlock =
FindLowestCandidateForFreeBlock(db, LowestFreeBlock);
#endif
ReadFreeBitBlock(db, LowestFreeBlock);
/* start at the right place: */
#ifdef BROKEN
p = &FreeBitBlock[
(LowestFreeBlock - FreeBlockStart) / BYTESPERFREEBIT
];
#else
p = FreeBitBlock;
#endif
for (; p - FreeBitBlock < FREEBITLEN; p++) {
if (*p != (unsigned char) 0xff) {
GotOne++;
break;
}
}
if (GotOne) break;
#ifdef BROKEN
/* it's all full, as we didn't find anything */
SetFreeBitBitStatusForFreeBlock(
db, LowestFreeBlock, SET_BLOCK_AS_USED
);
#else
LowestFreeBlock += BYTESPERFREEBIT * FREEBITLEN;
#endif
} while (!GotOne);
/* Now we've found a byte `containing' a free block... ( a zero bit)
* so we have to identify the block.
*/
Here = FreeBlockStart + (p - FreeBitBlock) * BYTESPERFREEBIT +
(FindUnsetBitInByte((unsigned int)*p) * BLOCKSIZE);
}
if (!GotOne || !Here) {
Error(E_FATAL|E_INTERNAL|E_BUG,
"%s: %d: GotOne %d here %lu; failed to find free block",
__FILE__, __LINE__, GotOne, Here
);
}
LQT_SetBlockStatus(db, Here, SET_BLOCK_AS_USED);
/* Now make the block as long as we can: */
*BlockLengthp = 1;
if (BytesWanted == 0 || BytesWanted > BLOCKSIZE) {
LQT_ExtendBlock(db, Here, BlockLengthp, BytesWanted);
}
*BlockLengthp *= BLOCKSIZE;
/* we have found the lowest free block and used it... */
LowestFreeBlock = Here + (*BlockLengthp);
return Here;
}
/* <Function>
* <Name>LQT_ExtendBlock
* <Class>Database/Physical
* <Purpose>
* <P>LQT_ExtendBlock marks as many blocks as possible following the
* given byte Offset as being used, and increments the unsigned int
* pointed to by BlockCountp by the number of blocks added.
* The number of blocks added is such that a single contiguous stretch
* of data starting at the given Offset, and continuing for the
* number of blocks in *BlockCountp, does not cross an LQT_ReadBlock
* cache boundary.</P>
* <P>If the BytesWanted argument is non-zero, the total number of
* blocks in BlockCountp when LQT_ExtendBlock returns will not be
* more than one block greater than BytesWanted bytes.</P>
* <Notes>
* *BlockCountp must be greater than zero on entry to LQT_ExtendBlock.
* <Returns>
* The total number of blocks in *BlockCountp
* <SeeAlso>
* LQT_FindFreeBlock
* LQT_SetBlockStatus
* </Function>
*/
API void
LQT_ExtendBlock(db, Offset, BlockCountp, BytesWanted)
t_LQTEXT_Database *db;
unsigned long Offset;
unsigned int *BlockCountp;
unsigned long BytesWanted;
{
unsigned long Candidate;
int MaxLength;
Candidate = Offset + (*BlockCountp * BLOCKSIZE);
/** Work out the maximum possible length, based on the
** fact that blocks can't span bigblock boundaries:
*/
/* We only have one byte in which to store the length...
* see blockhdr.h
* Note: Offset and CACHELEN are multiples of BLOCKSIZE.
*/
{
unsigned long LastUsedBlock = (Candidate - BLOCKSIZE) & (CACHELEN - 1);
MaxLength = (CACHELEN - LastUsedBlock) / BLOCKSIZE;
if (BytesWanted != 0) {
int MaxWanted = (BytesWanted / BLOCKSIZE) + 1;
if (MaxLength > MaxWanted) {
MaxLength = MaxWanted;
}
}
}
/* we only have one byte available...
* the limit here is arbitrary.
*/
if (MaxLength > MAX_CONTIGUOUS_BLOCKS) {
MaxLength = MAX_CONTIGUOUS_BLOCKS;
}
while (*BlockCountp < MaxLength && LQT_BlockIsFree(db, Candidate)) {
LQT_SetBlockStatus(db, Candidate, SET_BLOCK_AS_USED);
++*BlockCountp;
Candidate += BLOCKSIZE;
}
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_PUTPLACES|LQTRACE_FREEBLOCKS)) {
LQT_Trace(LQTRACE_PUTPLACES|LQTRACE_FREEBLOCKS,
"Extend %ld --> %d\n", Offset, *BlockCountp
);
}
#endif
}
/* <Function>
* <Name>LQT_BlockIsFree
* <Class>Database/Physical
* <Purpose>
* <P>Determine the status of the block at a given byte offset from the
* start of the data overflow file (data).
* An external file, freelist, is kept in the database directory; this
* file uses a single bit to represent the status of each block, either
* in use or free. If the freelist file is removed, subsequent
* attempts to write to the database will fail. Read-only
* access will still work unless LQTRACE_READAFTERWRITE is set,
* whereupon LQT_ReadBlock checks the status of each
* block before returning it;
* it is an error to attempt to read an unallocated block,
* although this not normally checked, for performance reasons.</P>
* <Returns>
* Non-zero if the block is available, zero if it is free
* <Notes>
* <P>The first few blocks are reserved for storing information about
* the database; they are marked as used automatically whenever a
* database is created.</P>
* <P>The freelist file can be rebuilt by the lqmkfreelist program.</P>
* <P>The test program `free' contains examples of using the Block
* Status functions LQT_BlockIsFree and LQT_SetBlockStatus.
* It can also be used to edit the contents of the freelist file.</P>
* <Errors>
* Fatal error if the freelist file could not be opened
* <SeeAlso>
* LQT_SetBlockStatus
* LQT_FindFreeBlock
* LQT_ReadBlock
* </Function>
*/
API int
LQT_BlockIsFree(db, Offset)
t_LQTEXT_Database *db;
unsigned long Offset;
{
if (FreeFile < 0) {
OpenFreeFile(db);
}
/* First make sure that the necessary bitmap block is loaded: */
if (
Offset < FreeBlockStart ||
Offset >= (FreeBlockStart + (BYTESPERFREEBIT * FREEBITLEN))
) {
ReadFreeBitBlock(db, Offset);
}
{
/* Declare p and ui now, so that they weren't around for the
* ReadFreeBitBlock() call above. This may save a register dump on
* some systems. LQT_BlockIsFree is called a *lot*.
*/
register unsigned char *p;
register unsigned int ui;
ui = (Offset - FreeBlockStart) / BLOCKSIZE; /* the bit address */
p = &FreeBitBlock[ui >> 3]; /* i.e. ui/8, i.e. the right byte */
if ((*p) & SetBitInByte(ui & 07)) {
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_FREEBLOCKS)) {
LQT_Trace(LQTRACE_FREEBLOCKS, "<?%ldu>", Offset);
}
#endif
return 0; /* bit is set --> block is in use */
} else {
/* We could update LowestFreeBlock here, but the chances are
* that we're about to allocate the block, and then we'd end
* up with LowestFreeBlock being used immediately, and lost
* the advantage.
* So we only set it if it isn't already set.
*/
if (!LowestFreeBlock) {
LowestFreeBlock = Offset;
}
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_FREEBLOCKS)) {
LQT_Trace(LQTRACE_FREEBLOCKS, "<?%ldf>", Offset);
}
#endif
return 1; /* bit not set --> block is free */
}
}
}
/* <Function>
* <Name>LQT_SetBlockStatus
* <Class>Database/Physical
* <Purpose>
* <P>Set the status of the block at a given byte offset in the
* data file.</P>
* <P>Status must be either SET_BLOCK_AS_USED or SET_BLOCK_AS_FREE.
* In the former (USED) case, the block is marked as being in use,
* and can be brought into the cache with LQT_ReadBlock.
* In the latter case (FREE), the block is marked as being available
* for reuse. Since LQT_SetBlockStatus does not access the actual
* data, it does not have access to the block's length. It is
* therefore the caller's responsibility to call LQT_SetBlockstatus
* for each contiguous block when a block header's NumberOfBlock
* field is greater than one.</P>
* <Notes>
* This routine was called 2,785,338 times when indexing Shakespeare's
* complete works. To try and speed things up, LQT_SetBlockstatus
* performs as few checks as possible.
* <SeeAlso>
* LQT_BlockIsFree
* </Function>
*/
API void
LQT_SetBlockStatus(db, Offset, Status)
t_LQTEXT_Database *db;
unsigned long Offset;
int Status;
{
if (FreeFile < 0) {
OpenFreeFile(db);
}
/* First make sure that the necessary bitmap block is loaded: */
if (Offset >= (FreeBlockStart + (BYTESPERFREEBIT * FREEBITLEN)) ||
(Offset < FreeBlockStart)) {
ReadFreeBitBlock(db, Offset);
}
{
/* Declare p and ui now, so that they weren't around for
* ReadFreeBitBlock(). This may save a register dump on
* some systems.
*/
register unsigned char *p;
register unsigned int ui;
ui = (Offset - FreeBlockStart) / BLOCKSIZE; /* the bit address */
p = &FreeBitBlock[ui >> 3]; /* i.e. ui/8, i.e. the right byte */
if (Status == SET_BLOCK_AS_FREE) {
/* ui & 07 is ui % 8 is the bit within the byte: */
*p &= (unsigned char)~(unsigned char) SetBitInByte(ui & 07);
if (!LowestFreeBlock || Offset < LowestFreeBlock) {
LowestFreeBlock = Offset;
}
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_FREEBLOCKS)) {
LQT_Trace(LQTRACE_FREEBLOCKS, "<!%ldf>", Offset);
}
#endif
} else {
#ifdef PARANOID
if (Status != SET_BLOCK_AS_USED) {
Error(E_BUG, "LQT_SetBlockStatus(%ld, %d)", Offset, Status);
}
#endif
/* no point in setting LowestFreeBlock, as we don't know
* what to set it to. But there is no free block below it.
*/
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_FREEBLOCKS)) {
LQT_Trace(LQTRACE_FREEBLOCKS, "<!%ldu>", Offset);
}
#endif
*p |= (unsigned char) SetBitInByte(ui & 07);
}
FreeBitBlockIsDirty = 1;
}
}
/* <Function>
* <Name>LQT_ReadBlock
* <Class>Database/Files, Database/Physical
* <Purpose>
* Reads the block at the given byte offset, and returns a pointer to
* the data. The data is stored in a cache, so it is important not
* to try and write beyond the end of the block or group of blocks as
* determined by LQT_ExtendBlock or LQT_FindFreeBlock.
* The block must be written out with LQT_WriteBlock if it has changed.
* In addition, the block is not locked in memory, but LQT_ReadBlock
* ensures that it is safe to read at least one other block before
* writing this one out with LQT_WriteBlock.
* <Returns>
* A pointer to the data
* <Notes>
* Attempts to read beyond the end of the data file will extend
* the database automatically.
* The data will be initialised to zero, except for the block headers,
* whose NumberOfBlocks field will all be set to one.
* <Errors>
* Fatal error (E_BUG) if the database can't be opened or created.
* <SeeAlso>
* LQT_ExtendBlock
* LQT_FindFreeBlock
* LQT_WriteBlock
* </Function>
*/
API unsigned char *
LQT_ReadBlock(db, Offset, WID)
t_LQTEXT_Database *db;
unsigned long Offset;
t_WID WID;
{
t_BlockHeader *BH;
if (DataFile < 0) {
OpenDataBase(db);
}
#ifdef WIDINBLOCK
{
t_WID otherWID = LQTpGetWIDofBlock(db, Offset);
if (WID && otherWID && otherWID != WID) {
Error(E_WARN|E_BUG,
"Reading block %ld, WID %ld, was last written for WID %ld",
Offset, WID, otherWID
);
}
}
#endif
if (LQT_BlockIsCached(db, Offset)) {
if (++BlockCacheTimer < 1) {
LQTpMoveCacheDatesBack(db);
}
CurrentBlock->TimeLastUsed = BlockCacheTimer;
#ifdef ASCIITRACE
/* Block 0 is used to store other data: */
if (WID && Offset > 0L) {
if (LQT_TraceFlagsSet(LQTRACE_READBLOCK)
#ifdef WIDINBLOCK
|| 1
#endif
) {
BH = (t_BlockHeader *) &(CurrentBlock->ReadAheadBuffer[
Offset - CurrentBlock->CacheStart
]);
LQT_Trace(LQTRACE_READBLOCK,
"READ %ld len %d Next %ld",
Offset,
BH->NumberOfBlocks,
BH->NextOffset
);
#ifdef WIDINBLOCK
if (BH->WID != WID) {
Error(E_WARN|E_INTERNAL,
"%s: %d: LQT_ReadBlock(%ld, WID %ld) Block WID is %ld (next %ld)",
__FILE__, __LINE__,
Offset, WID,
BH->WID,
BH->NextOffset
);
BH->WID = WID;
}
#endif /* WIDINBLOCK */
}
}
#endif /*ASCIITRACE */
return
&(CurrentBlock->ReadAheadBuffer[Offset - CurrentBlock->CacheStart]);
}
/* So it's not cached...
* Which means we have to read a new cache.
* So let's make some room:
*/
LQT_FlushOneBlockFromCache(db);
/* cache only on CACHELEN boundaries (typically 8K) as this helps the
* file system, especially over NFS.
*/
CurrentBlock->CacheStart = Offset / CACHELEN;
CurrentBlock->CacheStart *= CACHELEN;
(void) LQU_Elseek(E_FATAL,
db->DataBase,
"Main data file",
DataFile,
CurrentBlock->CacheStart,
SEEK_SET /* = 0 */
);
/* Now we are in the right place */
CurrentBlock->CacheLen = read(
DataFile,
(char *) CurrentBlock->ReadAheadBuffer,
CACHELEN
);
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_READBLOCK)) {
LQT_Trace(LQTRACE_READBLOCK,
"READ %ld len %d -> %d Cached",
Offset,
CACHELEN,
CurrentBlock->CacheLen
);
}
#endif
if (CurrentBlock->CacheLen < 0) {
Error(E_FATAL|E_SYS,
"LQT_ReadBlock: read(%d=\"%s\"...) returned %d, not %d",
DataFile, db->DataBase, CurrentBlock->CacheLen, CACHELEN
);
}
BH = (t_BlockHeader *)
&(CurrentBlock->ReadAheadBuffer[Offset-CurrentBlock->CacheStart]);
#ifdef WIDINBLOCK
if (WID) {
if (BH->WID != WID) {
Error(E_WARN|E_INTERNAL,
"%s: %d: LQT_ReadBlock(%ld, WID %ld) WID in block is %ld",
__FILE__, __LINE__,
Offset, WID,
BH->WID
);
BH->WID = WID;
}
}
#endif
if (CurrentBlock->CacheLen < CACHELEN) {
/* If CacheLen was less than CACHELN this can only mean that we
* have tried to read beyond the end of the file. In this case,
* we might as well consider that we have the extra bytes cached
* as well. The disadvantage is that the file will always grow to
* a multiple of CACHELEN, but the advantage is fewer reads when
* the file is growing.
*/
/* First, zero out the block if it's near the start.
* This is so that we can check for things stored in block zero.
*/
bzero(
(char *) &CurrentBlock->ReadAheadBuffer[CurrentBlock->CacheLen],
CACHELEN - CurrentBlock->CacheLen
);
{
register long Block = CurrentBlock->CacheLen / BLOCKSIZE;
for (Block *= BLOCKSIZE; Block < CACHELEN; Block += BLOCKSIZE) {
BH = (t_BlockHeader *) &(CurrentBlock->ReadAheadBuffer[Block]);
if (BH->NumberOfBlocks == 0) {
BH->NumberOfBlocks = 1;
}
}
}
BH = (t_BlockHeader *)
&(CurrentBlock->ReadAheadBuffer[Offset-CurrentBlock->CacheStart]);
if (BH->NumberOfBlocks == 0) {
BH->NumberOfBlocks = 1;
}
CurrentBlock->CacheLen = CACHELEN;
}
if (++BlockCacheTimer < 1) {
LQTpMoveCacheDatesBack(db);
}
CurrentBlock->TimeLastUsed = BlockCacheTimer;
#ifdef ASCIITRACE
if (LQT_TraceFlagsSet(LQTRACE_READBLOCK)) {
printcache(db);
}
#endif
return &(CurrentBlock->ReadAheadBuffer[Offset - CurrentBlock->CacheStart]);
}
/* <Function>
* <Name>LQT_DeleteWordPlaces
* <Class>Database/Update, Database/Words
* <Purpose>
* <P>Deletes the word places from disk for a given WID, marking the
* corresponding data blocks as unused.<P>
* <P>The given FirstBlock argument is the first block in the chain of
* the linked list of blocks for the given WID. If the data is
* contained entirely in the WID index block, LQT_DeleteWordPlaces
* should not be called, and this is a fatal error.</P>
* <P>LQT_DeleteWordPlaces does not remove the WID <--> Word mapping
* from the wordlist Key Value Database, and does not zero out the
* information in the widindex block.</P>
* <Errors>
* Fatal (E_BUG) error if FirstBlock or WID are zero.
* <SeeAlso>
* LQT_Deletepblock
* </Function>
*/
API void
LQT_DeleteWordPlaces(db, FirstBlock, WID)
t_LQTEXT_Database *db;
unsigned long FirstBlock;
t_WID WID;
{
t_BlockHeader *H;
unsigned long Block = FirstBlock;
if (!FirstBlock || !WID) {
Error(E_BUG, "LQT_DeleteWordPlaces(%ld, %ld) invalid", FirstBlock, WID);
}
if (DataFile < 0) {
OpenDataBase(db);
}
while (Block != 0L) {
int NumberOfBlocks;
H = (t_BlockHeader *) LQT_ReadBlock(db, Block, WID);
NumberOfBlocks = H->NumberOfBlocks;
#ifdef WIDINBLOCK
H->WID = 0;
/* help debugging: */
(void) sprintf(&H->Data[0], "Deleted -- was %ld\n", WID);
/* only need to write the block if debugging... */
LQT_WriteBlock(
db,
Block,
(unsigned char *) H
H->NumberOfBlocks,
(t_WID) 0
);
#endif
while (NumberOfBlocks > 0) {
--NumberOfBlocks;
LQT_SetBlockStatus(db, Block + (NumberOfBlocks * BLOCKSIZE),
SET_BLOCK_AS_FREE);
}
Block = H->NextOffset;
}
return;
}
/* <Function>
* <Name>LQT_Deletepblock
* <Class>Database/Words, Database/Update
* <Purpose>
* <P>Deletes the word places for a given pblock, using
* LQT_DeleteWordPlaces.</P>
* <P>Like LQT_DeleteWordPlaces, LQT_Deletepblock does not remove
* the WID <--> Word mapping
* from the wordlist Key Value Database, and does not zero out the
* information in the widindex block.</P>
* <P>In other words, the word is not removed from the database
* vocabulary, and subsequent calls to LQT_WordToWID will return
* the same WID value as before the call to LQT_Deletepblock.<P>
* <SeeAlso>
* LQT_Getpblock
* LQT_DestroyWordInfo
* </Function>
*/
API void
LQT_Deletepblock(db, pblock)
t_LQTEXT_Database *db;
t_pblock *pblock;
{
if (!pblock) {
Error(E_BUG, "Attempt to delete null pblock (address 0x%x)", pblock);
} else if (!pblock->ChainStart || !pblock->WID) {
Error(E_BUG,
"Attempt to delete pblock 0x%x with WID %d, ChainStart %ld",
pblock,
pblock->WID,
pblock->ChainStart
);
}
LQT_DeleteWordPlaces(db, pblock->ChainStart, pblock->WID);
return;
}