From owner-freebsd-stable  Thu Apr 19 16:34:49 2001
Delivered-To: freebsd-stable@freebsd.org
Received: from cs.rpi.edu (mumble.cs.rpi.edu [128.213.8.16])
	by hub.freebsd.org (Postfix) with ESMTP
	id 4D28D37B43F; Thu, 19 Apr 2001 16:34:37 -0700 (PDT)
	(envelope-from crossd@srs.cs.rpi.edu)
Received: from srs.cs.rpi.edu (srs.cs.rpi.edu [128.213.12.66])
	by cs.rpi.edu (8.9.3/8.9.3) with ESMTP id TAA67858;
	Thu, 19 Apr 2001 19:34:35 -0400 (EDT)
Message-Id: <200104192334.TAA67858@cs.rpi.edu>
To: wpaul@FreeBSD.ORG (Bill Paul)
Cc: crossd@cs.rpi.edu (David E. Cross), jkh@osd.bsdi.com,
	stable@FreeBSD.ORG, developers@FreeBSD.ORG, crossd@cs.rpi.edu
Subject: Re: FreeBSD 4.3-RC5 now on ftp.freebsd.org 
In-Reply-To: Message from wpaul@FreeBSD.ORG (Bill Paul) 
   of "Thu, 19 Apr 2001 14:00:36 PDT." <20010419210036.5A53A37B424@hub.freebsd.org> 
Date: Thu, 19 Apr 2001 19:34:35 -0400
From: "David E. Cross" <crossd@srs.cs.rpi.edu>
Sender: owner-freebsd-stable@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.ORG

> Uh. Look closer. No no, closer. The key/size members in the cached
> database handle are used by the first/next routines to keep an eye on
> where we are in the database so we can match a database handle with an
> ongoing first/next enumeration request. (That is, where the client
> does a yp_first() and then a series of yp_next()s to dump out all of
> the entries in a map. Things like getpwent() and getgrent() do this,
> and it gets *really* slow if you have to start from the top and linear
> search down for each yp_next() request, which is what you'd have to do
> since the Berkeley DB hash database method doesn't let you position the
> 'cursor' at arbitrary locations. This trick lets us say: "Hey! This is
> the same handle we used for the last yp_next() request, and it's positioned
> at the right place in the database for us to pick up where we left off.
> Let's use this handle again.")
> 
> The key pointer remains valid up until the next request is made, which
> could be a yp_first_record(), yp_next_record() or yp_get_record().
> 
> - yp_first_record(): we set the key pointer to the current key
> - yp_next_record: we set the key pointer to the current key
> - yp_get_record(): we set the key pointer to NULL
> 
> Every time we do a new database access, we update the key pointer.
> It can never point off into the weeds because it never becomes stale.
> 
> I admit, the optimization is grody. Had I used the btree database method,
> this wouldn't have been necessary, but something told me not to do that.
> If you can prove that using the btree method would be faster, you can
> re-write the yp_dblookup.c module to use it.
I did look closer, indeed here is a routine that tickels the exact behaviour 
that I am describing (which does exactly the re-iterate from the top that 
you describe):

#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>
#include <limits.h>
#include <db.h>
#include <fcntl.h>
#include <errno.h>

int db_next_key(DB *dbp, DBT *key, DBT *data)
{
        DBT lkey = {NULL, 0};
        DBT ldata = {NULL, 0};
        if (key->data == NULL) 
                return ((dbp->seq)(dbp, key, data, R_FIRST));
        (dbp->seq)(dbp, &lkey, &ldata, R_FIRST);
        while (key->size != lkey.size ||
                strncmp((char *)key->data, lkey.data, (int)key->size)) {
                        if ((dbp->seq)(dbp, &lkey,&ldata, R_NEXT)) {
                          return 1;
                        }
        }
	if ((dbp->seq)(dbp, key, data, R_NEXT)) {
                return 1;
        }
	return 0;
}

int main(void)
{
        DB *dbp;
        DBT lkey = {NULL, 0};
        DBT ldata = {NULL, 0};
        DBT key = {NULL, 0};
        DBT data = {NULL, 0};
        int rval;

        dbp=dbopen("/var/yp/DOMAIN/passwd.byname", O_RDONLY, 0600, DB_HASH, NULL);
	        while (db_next_key(dbp, &key, &data) == 0)
                printf("%.*s\n", data.size, data.data);
        (dbp->close)(dbp);
        return 0;
} 


Note: you will need a relatively large database for this, ours is about 2000, 
but it looks like you will trip over this with just a 400 byte entry.  Yes, I
know this is inefficient, it is supposed to be, its purpose is to show that
the data base internally re-uses the pointers, the end effect is that this
code produces an infinite loop as the "prev" key gets over-written with a more
distant key then was previously listed.

In my attempts to track down this ypserv problem it has come down to the 
Berkley DB code.  There is simply no other place it could be.  I ave been
over the ypserv code line by line, and placed numerous debugging statements, 
it must be the DB code that is thrashing the stack, specifically how ypserv
is using the Berkley DB code.

--
David Cross                               | email: crossd@cs.rpi.edu 
Lab Director                              | Rm: 308 Lally Hall
Rensselaer Polytechnic Institute,         | Ph: 518.276.2860            
Department of Computer Science            | Fax: 518.276.4033
I speak only for myself.                  | WinNT:Linux::Linux:FreeBSD

To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-stable" in the body of the message