Problems and fixes for dbz.c

Tue May 31 09:03:09 AEST 1988

I took this code off alt.sources and found a couple of problems.  I have
sent the changes to the author but have not received any response.
               (Thank you Jon Zeeff for 99% of the work!!)

I feel the problems are severe enough to post what I have at this time.
If you are already running a early version of this code.  You will have to
rebuild your history.pag file after you add this.  Run "expire -R".

  The biggest problem that I found was the fetch of the stored data never
  gave you the correct offset in the history file!  This allowed duplicate
  articles to be received and the system would not honor sendme messages.

  Fetches that clash at the end of the hash table would not wrap around.

  Stores to a full hash table would corrupt an entry before failing.

  The code required all of the news programs to be setuid to the owner of
  the history.pag file or it had to be writable by all.  It now only
  opens the file read/write if a store is attempted.

I have cleaned up the code (my opinion :->) and fixed the above problems.
I also added DEBUG code for both news and rn styles.

For news (I'm running 2.11 p14) there is a skeleton localize.sh script
for SysV systems that makes the changes to add dbz.

For rn the changes are to run ./Configure.  Answer "n"o to run makedepend.
Edit "Makefile" and change the line:

obj4 = respond.o rn.o search.o sw.o term.o util.o

to:

obj4 = respond.o rn.o search.o sw.o term.o util.o dbz.o

Also edit bits.c and change this:

#ifdef DBM
#	include <dbm.h>
#endif DBM

to:

#define DBM
#ifdef DBM
#	include "dbz.h"
#endif DBM

Then do a "makedepend" and "make".

Good Luck

David Butler
gdb at ninja.UUCP
============================ Cut here and feed to /bin/sh ====================
: Run this shell script with "sh" not "csh"
# contents:
# news/localize.sv
# news/dbz.c
# rn/dbz.h
# rn/dbz.c
PATH=/bin:/usr/bin:
export PATH
all=FALSE
if [ $1x = -ax ]; then
	all=TRUE
fi
echo 'Extracting news/localize.sv'
sed 's/^X//' <<'//go.sysin dd *' >news/localize.sv
rm -f Makefile
cp Makefile.dst Makefile
chmod u+w Makefile
ed - Makefile  <<'EOF'
g/^#USG /s///
g/^#V7 /d
g/^#VMS /d
g/^#BSD4_[123] /d
g/#NOTVMS/s/#NOTVMS.*//
g/^#NNTP /d
g/^UUXFLAGS/s/-z/-gR/
g/^CFLAGS/s/-DUSG/-DUSG -DDBM/
g/^IOBJECTS/s/=/= dbz.o/
g/^ISRCS/s/=/= dbz.c/
g/^ROBJECTS/s/=/= dbz.o/
g/^RSRCS/s/=/= dbz.c/
g/^VOBJECTS/s/=/= dbz.o/
g/^VSRCS/s/=/= dbz.c/
g/^EXPOBJS/s/=/= dbz.o/
g/^ESRCS/s/=/= dbz.c/
w
q
EOF

echo "\n\c" >>Makefile
echo "dbz.o: dbz.c" >>Makefile
echo "\t$(CC) $(CFLAGS) -c dbz.c" >>Makefile

rm -f defs.h
cp defs.dist defs.h
chmod u+w defs.h
ed - defs.h <<'EOF'
X/#define TMAIL/s;ucb/Mail;bin/mailx;
X/#define UNAME/s;^/\* ;;
X/#define DOXREFS/s;^/\* ;;
w
q
EOF
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
	chmod 640 news/localize.sv
	echo -n '	'; ls -ld news/localize.sv
fi
echo 'Extracting news/dbz.c'
sed 's/^X//' <<'//go.sysin dd *' >news/dbz.c
X/*
dbz.c  V1.3

Copyright 1988 Jon Zeeff (umix!b-tech!zeeff)
You can use this code in any manner, as long as you leave my name on it
and don't hold me responsible for any problems with it.

For news:
Hacked by gdb at ninja.UUCP (David Butler); Sun May 29 11:19:06 CDT 1988

These routines replace dbm as used by the usenet news software
(it's not a full dbm replacement by any means).  It's fast and
simple.

BSD sites will notice some savings in disk space.  Sys V sites without
dbm will notice much faster operation.

Note: .pag files created by version 1.0 need to be recreated before
      using this version.

This code relies on the fact that news stores a pointer to the history
file as the dbm data.  It doesn't store another copy of the key like
dbm does so it saves disk space.  All you can do is fetch() and
store() data.

Just make news with the dbm option and link with dbz.o.
*/

X/*
   Set this to the something several times larger than the maximum # of
   lines in a history file.  It should be a prime number.
*/
#define INDEX_SIZE 99991L

X/*#include <sys/types.h>*/
X/*#include <sys/stat.h>*/
#include <fcntl.h>
#include <string.h>
#include <memory.h>
#include <ctype.h>

long lseek();

typedef struct {
	char *dptr;
	int dsize;
} datum;

static char Buffer[1024];	/* used for fetch returns */
static int Data_fd;
static char Index_file[512];	/* index file name */
static int Index_fd = -1;
static int Index_for_write = 0;	/* changed when the file is open for write */

dbminit(name)
char *name;
{
	void crcinit();

	if (Index_fd >= 0) {
#ifdef DEBUG
		printf("dbminit: Index_file already open\n");
#endif
		return(-1);    /* init already called once */
	}

	Data_fd = open(name, O_RDONLY);
	if (Data_fd < 0) {
#ifdef DEBUG
		printf("dbminit: Data_file open failed\n");
#endif
		return(-1);
	}

	strcpy(Index_file, name);
	strcat(Index_file, ".pag");
	Index_fd = open(Index_file, O_RDONLY);
	if (Index_fd < 0) {
#ifdef DEBUG
		printf("dbminit: Index_file open failed\n");
#endif
		return(-1);
	}

	crcinit();	/* initialize the crc table */
#ifdef DEBUG
	printf("dbminit: succeeded\n");
#endif
	return(0);
}

dbmclose()
{
	if (Index_fd >= 0) {
		close(Index_fd);
		Index_fd = -1;
		close(Data_fd);
	}
#ifdef DEBUG
	printf("dbmclose: succeeded\n");
#endif
	return(0);
}

X/* get an entry from the database */
datum
fetch(key)
datum key;
{
	long index_ptr;
	long index_size = INDEX_SIZE;
	long data_ptr;
	datum output;
	long hash();
	long get_ptr();
	void lcase();

#ifdef DEBUG
	printf("fetch: (%s)\n", key.dptr);
#endif
	for (index_ptr = hash(key.dptr, key.dsize);
	    index_size-- && (data_ptr = get_ptr(index_ptr)) > 0L;
	    index_ptr = ++index_ptr % INDEX_SIZE) {

		lseek(Data_fd, data_ptr, 0);
		read(Data_fd, Buffer, (unsigned)key.dsize);

		/* key should be lcase version of article id and no tab */

		(void)lcase(Buffer, key.dsize);
		if (Buffer[key.dsize - 1] == '\t') {
			Buffer[key.dsize - 1] = '\0';
		}
#ifdef DEBUG
		printf("fetch: Buffer (%s)\n", Buffer);
#endif
		if (memcmp(key.dptr, Buffer, (int)key.dsize) == 0) {
			/* we found it */
			memcpy(Buffer, (char *)&data_ptr, sizeof(long));
			output.dptr = Buffer;
			output.dsize = sizeof(long);
#ifdef DEBUG
			printf("fetch: successful\n");
#endif
			return(output);
		}
	}

	/* we didn't find it */

	output.dptr = (char *)0;
	output.dsize = 0L;
#ifdef DEBUG
	printf("fetch: failed\n");
#endif
	return(output);
}

X/* add an entry to the database */
store(key, data)
datum key;
datum data;
{
#ifdef DEBUG
	printf("store: (%s, %ld)\n", key.dptr, *((long *)data.dptr));
#endif
	return(put_ptr(hash(key.dptr, key.dsize), *((long *)data.dptr)));
}

X/* get a data file pointer from the specified location in the index file */
static long
get_ptr(index_ptr)
long index_ptr;
{
	long data_ptr;

#ifdef DEBUG
	printf("get_ptr: (%ld)\n", index_ptr);
#endif
	/* seek to where it should be */
	lseek(Index_fd, (long)(index_ptr * sizeof(long)) ,0);

	/* read it */
	if (read(Index_fd, (char *)&data_ptr, sizeof(long)) != sizeof(long) ||
	    data_ptr == 0L) {
#ifdef DEBUG
		printf("get_ptr: failed\n");
#endif
		return(-1L);
	}
#ifdef DEBUG
	printf("get_ptr: succeeded\n");
#endif
	return(--data_ptr);
}

X/* put a data file pointer into the specified location in the index file */
X/* move down further if slots are full */
static
put_ptr(index_ptr, data_ptr)
long index_ptr;
long data_ptr;
{
	long get_ptr();
	long index_size = INDEX_SIZE;
	int fd;

	/* open file for write */
	if (Index_for_write == 0) {
		if ((fd = open(Index_file, O_RDWR)) < 0) {
#ifdef DEBUG
			printf("put_ptr: can't open Index_file for write\n");
#endif
			return(-1);
		}
		close(Index_fd);
		Index_fd = fd;
		++Index_for_write;
	}

	/* find an empty slot */
	while (index_size-- && get_ptr(index_ptr) > 0L) {
		index_ptr = ++index_ptr % INDEX_SIZE;
	}

	if (index_size == 0L) {
#ifdef DEBUG
		printf("put_ptr: hash table overflow - failed\n");
#endif
		return(-1);
	}

	/* seek to spot */
	lseek(Index_fd, (long)(index_ptr * sizeof(long)), 0);

	++data_ptr;

	/* write in data */
	if (write(Index_fd, (char *)&data_ptr, sizeof(long)) != sizeof(long)) {
#ifdef DEBUG
		printf("put_ptr: write failed\n");
#endif
		return(-1);
	}

#ifdef DEBUG
	printf("put_ptr: succeeded\n");
#endif
	return(0);
}

static void
lcase(s, n)
register char *s;
register int n;
{
	for (; n > 0L; --n, ++s)
		if (isupper(*s))
			*s = _tolower(*s);
}

X/* This is a simplified version of the pathalias hashing function.
 * Thanks to Steve Belovin and Peter Honeyman
 *
 * hash a string into a long int.  31 bit crc (from andrew appel).
 * the crc table is computed at run time by crcinit() -- we could
 * precompute, but it takes 1 clock tick on a 750.
 *
 * This fast table calculation works only if POLY is a prime polynomial
 * in the field of integers modulo 2.  Since the coefficients of a
 * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
 * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
 * 31 down to 25 are zero.  Happily, we have candidates, from
 * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
 *	x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
 *	x^31 + x^3 + x^0
 *
 * We reverse the bits to get:
 *	111101010000000000000000000000001 but drop the last 1
 *         f   5   0   0   0   0   0   0
 *	010010000000000000000000000000001 ditto, for 31-bit crc
 *	   4   8   0   0   0   0   0   0
 */

X/*#define POLY32 0xf5000000	/* 32-bit polynomial */
X/*#define POLY31 0x48000000	/* 31-bit polynomial */
X/*#define POLY POLY31		/* use 31-bit to avoid sign problems */

#define POLY 0x48000000		/* 31-bit polynomial */

static long CrcTable[128];

static void
crcinit()
{	register int i, j;
	register long sum;

	for (i = 0; i < 128; ++i) {
		sum = 0;
		for (j = 7 - 1; j >= 0; --j)
			if (i & (1 << j))
				sum ^= POLY >> j;
		CrcTable[i] = sum;
	}
#ifdef DEBUG
	printf("crcinit: done\n");
#endif
}

static long
hash(name, size)
register char *name;
register int size;
{
	register long sum = 0;

	while (size--) {
		sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
	}
#ifdef DEBUG
	printf("hash: returns (%ld)\n", (long)(sum % INDEX_SIZE));
#endif
	return((long)(sum % INDEX_SIZE));
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
	chmod 640 news/dbz.c
	echo -n '	'; ls -ld news/dbz.c
fi
echo 'Extracting rn/dbz.h'
sed 's/^X//' <<'//go.sysin dd *' >rn/dbz.h
typedef struct {
   char *dptr;
   int dsize;
} datum;
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
	chmod 640 rn/dbz.h
	echo -n '	'; ls -ld rn/dbz.h
fi
echo 'Extracting rn/dbz.c'
sed 's/^X//' <<'//go.sysin dd *' >rn/dbz.c
X/*
dbz.c  V1.3