Net2/usr/src/lib/libc/db/btree/storage.c
/*-
* Copyright (c) 1990 The Regents of the University of California.
* All rights reserved.
*
* This code is derived from software contributed to Berkeley by
* Mike Olson.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the University of
* California, Berkeley and its contributors.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid[] = "@(#)storage.c 5.2 (Berkeley) 2/22/91";
#endif /* LIBC_SCCS and not lint */
#include <sys/param.h>
#include <db.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "btree.h"
/*
* BT_GETPAGE -- Make pgno the current page of the btree.
*
* This routine is just a wrapper that decides whether to call the
* memory or disk-based routine to do the work.
*
* Parameters:
* t -- btree in which to get page
* pgno -- page number to get
*
* Returns:
* RET_SUCCESS or RET_ERROR.
*/
int
_bt_getpage(t, pgno)
BTREE_P t;
pgno_t pgno;
{
#ifdef DEBUG
if (pgno == P_NONE)
_punt();
#endif /* DEBUG */
/* see if we can get away without doing any work */
if (t->bt_curpage != (BTHEADER *) NULL) {
if (t->bt_curpage->h_pgno == pgno)
return (RET_SUCCESS);
}
if (t->bt_fname == (char *) NULL)
return (_bt_getmpage(t, pgno));
else
return (_bt_getdpage(t, pgno));
}
/*
* _BT_GETMPAGE -- Make pgno the current page of the btree.
*
* This routine gets pages for in-memory btrees.
*
* Parameters:
* t -- btree in which to get page
* pgno -- page number to get
*
* Returns:
* RET_SUCCESS or RET_ERROR.
*/
int
_bt_getmpage(t, pgno)
register BTREE_P t;
pgno_t pgno;
{
int htindex;
BTHEADER *h;
HTBUCKET *b;
if (t->bt_curpage == (BTHEADER *) NULL) {
if (pgno != P_ROOT) {
errno = EBADF;
return (RET_ERROR);
}
t->bt_npages++;
h = (BTHEADER *) malloc((unsigned) t->bt_psize);
if (h == (BTHEADER *) NULL)
return (RET_ERROR);
h->h_pgno = P_ROOT;
h->h_flags = F_LEAF;
h->h_lower = (index_t)
(((char *) &(h->h_linp[0])) - ((char *) h));
h->h_upper = t->bt_psize;
h->h_prevpg = h->h_nextpg = P_NONE;
t->bt_curpage = h;
/* get the root page into the hash table */
if (_bt_write(t, h, RELEASE) == RET_ERROR)
return (RET_ERROR);
}
htindex = HASHKEY(pgno);
for (b = t->bt_s.bt_ht[htindex];
b != (HTBUCKET *) NULL;
b = b->ht_next) {
if (b->ht_pgno == pgno) {
t->bt_curpage = b->ht_page;
return (RET_SUCCESS);
}
}
return (RET_ERROR);
}
/*
* _BT_GETDPAGE -- Make pgno the current page of the btree.
*
* This routine gets pages for disk btrees.
*
* Because disk btree pages must be readable across machine architectures,
* the btree code writes integers out in network format. This routine
* converts them back to host format before returning the page.
*
* Parameters:
* t -- btree in which to get page
* pgno -- page number to get
*
* Returns:
* RET_SUCCESS, RET_ERROR.
*/
int
_bt_getdpage(t, pgno)
register BTREE_P t;
pgno_t pgno;
{
BTHEADER *h;
char *cache;
long pos;
int n, nbytes;
/* if we have an lru cache, let the cache code do the work */
if (ISCACHE(t)) {
cache = t->bt_s.bt_d.d_cache;
/* release the old page */
if (t->bt_curpage != (BTHEADER *) NULL) {
pgno_t opgno = t->bt_curpage->h_pgno;
t->bt_curpage->h_flags &= ~F_DIRTY;
if (lruwrite(cache, (int) opgno) < 0)
return (RET_ERROR);
if (lrurelease(cache, (int) opgno) < 0)
return (RET_ERROR);
}
if (pgno > t->bt_npages) {
if ((h = (BTHEADER *) lrugetnew(cache, (int)pgno, &nbytes))
== (BTHEADER *) NULL)
return (RET_ERROR);
t->bt_npages = pgno;
} else {
if ((h = (BTHEADER *) lruget(cache, (int)pgno, &nbytes))
== (BTHEADER *) NULL)
return (RET_ERROR);
}
/* init this page, if necessary */
if (nbytes == 0) {
h->h_pgno = pgno;
h->h_flags = F_LEAF;
h->h_lower = (index_t)
(((char *) &(h->h_linp[0])) - ((char *) h));
h->h_upper = t->bt_psize;
h->h_prevpg = h->h_nextpg = P_NONE;
}
t->bt_curpage = h;
return (RET_SUCCESS);
}
/* sync the current page, if necessary */
if (t->bt_curpage != (BTHEADER *) NULL) {
if (t->bt_curpage->h_flags & F_DIRTY)
if (_bt_write(t, t->bt_curpage, RELEASE) == RET_ERROR)
return (RET_ERROR);
} else {
if (t->bt_npages == 0)
t->bt_npages = 1;
/* if no current page, get space for one */
if ((t->bt_curpage = (BTHEADER *) malloc((unsigned) t->bt_psize))
== (BTHEADER *) NULL) {
return (RET_ERROR);
}
}
n = t->bt_psize;
pos = (long) (pgno * n);
/* seek to correct location in file */
if (lseek(t->bt_s.bt_d.d_fd, pos, L_SET) != pos) {
return (RET_ERROR);
}
/* read the page */
if ((nbytes = read(t->bt_s.bt_d.d_fd, t->bt_curpage, n)) < n) {
/*
* If we didn't get a full page, we must have gotten no
* data at all -- in which case we're trying to read a
* root page that doesn't exist yet. This is the only
* case in which this is okay. If this happens, construct
* an empty root page by hand.
*/
if (nbytes != 0 || pgno != P_ROOT) {
errno = EBADF;
return (RET_ERROR);
}
h = (BTHEADER *) t->bt_curpage;
h->h_pgno = pgno;
h->h_flags = F_LEAF;
h->h_lower = (index_t)
(((char *) &(h->h_linp[0])) - ((char *) h));
h->h_upper = t->bt_psize;
h->h_prevpg = h->h_nextpg = P_NONE;
} else
(void) _bt_pgin(t->bt_curpage, (char *) t->bt_lorder);
return (RET_SUCCESS);
}
/*
* _BT_PGOUT, _BT_PGIN -- Convert host-specific number layout to/from
* the host-independent format stored on disk.
*
* Parameters:
* h -- page to convert
* _lorder -- byte order for pages (stored as a char * in the
* cache, and passed around as a magic cookie).
*
* Returns:
* RET_SUCCESS (lru code requires a return value).
*
* Side Effects:
* Layout of tree metadata on the page is changed in place.
*
* Warnings:
* Everywhere else in the code, the types pgno_t and index_t
* are opaque. These two routines know what they really
* are.
*/
int
_bt_pgout(h, _lorder)
BTHEADER *h;
char *_lorder;
{
int i;
int top;
int lorder;
DATUM *d;
IDATUM *id;
size_t chain;
lorder = (int) _lorder;
if (lorder == BYTE_ORDER)
return (RET_SUCCESS);
if (h->h_flags & F_LEAF) {
if (h->h_flags & F_CONT) {
if (h->h_prevpg == P_NONE) {
size_t longsz;
(void) bcopy((char *) &(h->h_linp[0]),
(char *) &longsz,
sizeof(longsz));
BLSWAP(longsz);
(void) bcopy((char *) &longsz,
(char *) &(h->h_linp[0]),
sizeof(longsz));
}
} else {
top = NEXTINDEX(h);
for (i = 0; i < top; i++) {
d = (DATUM *) GETDATUM(h, i);
if (d->d_flags & D_BIGKEY) {
(void) bcopy((char *) &(d->d_bytes[0]),
(char *) &chain,
sizeof(chain));
BLSWAP(chain);
(void) bcopy((char *) &chain,
(char *) &(d->d_bytes[0]),
sizeof(chain));
}
if (d->d_flags & D_BIGDATA) {
(void) bcopy((char *) &(d->d_bytes[d->d_ksize]),
(char *) &chain,
sizeof(chain));
BLSWAP(chain);
(void) bcopy((char *) &chain,
(char *) &(d->d_bytes[d->d_ksize]),
sizeof(chain));
}
BLSWAP(d->d_dsize);
BLSWAP(d->d_ksize);
BLSWAP(d->d_flags);
BLSWAP(h->h_linp[i]);
}
}
} else {
top = NEXTINDEX(h);
for (i = 0; i < top; i++) {
id = (IDATUM *) GETDATUM(h, i);
BLSWAP(id->i_size);
BLSWAP(id->i_pgno);
BLSWAP(id->i_flags);
if (id->i_flags & D_BIGKEY) {
(void) bcopy((char *) &(id->i_bytes[0]),
(char *) &chain,
sizeof(chain));
BLSWAP(chain);
(void) bcopy((char *) &chain,
(char *) &(id->i_bytes[0]),
sizeof(chain));
}
BLSWAP(h->h_linp[i]);
}
}
BLSWAP(h->h_flags);
BLSWAP(h->h_pgno);
BLSWAP(h->h_prevpg);
BLSWAP(h->h_nextpg);
BLSWAP(h->h_lower);
BLSWAP(h->h_upper);
return (RET_SUCCESS);
}
int
_bt_pgin(h, _lorder)
BTHEADER *h;
char *_lorder;
{
int i;
int top;
int lorder;
DATUM *d;
IDATUM *id;
size_t chain;
/*
* If btree pages are to be stored in the host byte order, don't
* bother swapping.
*/
lorder = (int) _lorder;
if (lorder == BYTE_ORDER)
return (RET_SUCCESS);
BLSWAP(h->h_upper);
BLSWAP(h->h_lower);
BLSWAP(h->h_nextpg);
BLSWAP(h->h_prevpg);
BLSWAP(h->h_pgno);
BLSWAP(h->h_flags);
if (h->h_flags & F_LEAF) {
if (h->h_flags & F_CONT) {
if (h->h_prevpg == P_NONE) {
size_t longsz;
(void) bcopy((char *) &(h->h_linp[0]),
(char *) &longsz,
sizeof(longsz));
BLSWAP(longsz);
(void) bcopy((char *) &longsz,
(char *) &(h->h_linp[0]),
sizeof(longsz));
}
} else {
top = NEXTINDEX(h);
for (i = 0; i < top; i++) {
BLSWAP(h->h_linp[i]);
d = (DATUM *) GETDATUM(h, i);
BLSWAP(d->d_dsize);
BLSWAP(d->d_ksize);
BLSWAP(d->d_flags);
if (d->d_flags & D_BIGKEY) {
(void) bcopy((char *) &(d->d_bytes[0]),
(char *) &chain,
sizeof(chain));
BLSWAP(chain);
(void) bcopy((char *) &chain,
(char *) &(d->d_bytes[0]),
sizeof(chain));
}
if (d->d_flags & D_BIGDATA) {
(void) bcopy((char *) &(d->d_bytes[d->d_ksize]),
(char *) &chain,
sizeof(chain));
BLSWAP(chain);
(void) bcopy((char *) &chain,
(char *) &(d->d_bytes[d->d_ksize]),
sizeof(chain));
}
}
}
} else {
top = NEXTINDEX(h);
for (i = 0; i < top; i++) {
BLSWAP(h->h_linp[i]);
id = (IDATUM *) GETDATUM(h, i);
BLSWAP(id->i_size);
BLSWAP(id->i_pgno);
BLSWAP(id->i_flags);
if (id->i_flags & D_BIGKEY) {
(void) bcopy((char *) &(id->i_bytes[0]),
(char *) &chain,
sizeof(chain));
BLSWAP(chain);
(void) bcopy((char *) &chain,
(char *) &(id->i_bytes[0]),
sizeof(chain));
}
}
}
return (RET_SUCCESS);
}
/*
* _BT_ALLOCPG -- allocate a new page in the btree.
*
* This is called when we split a page, to get space to do the split.
* For disk btrees, these pages are released when the split is done.
* For memory btrees, they are not.
*
* Parameters:
* t -- tree in which to do split
*
* Returns:
* Pointer to the newly-allocated page
*/
BTHEADER *
_bt_allocpg(t)
BTREE_P t;
{
BTHEADER *h = t->bt_curpage;
BTHEADER *nh;
int nbytes;
/* if we have a cache, let the cache code do the work */
if (ISDISK(t) && ISCACHE(t)) {
nh = (BTHEADER *) lrugetnew(t->bt_s.bt_d.d_cache,
(int) (t->bt_npages + 1),
&nbytes);
} else {
nh = (BTHEADER *) malloc((unsigned) t->bt_psize);
}
if (nh != (BTHEADER *) NULL) {
nh->h_pgno = nh->h_prevpg = nh->h_nextpg = P_NONE;
nh->h_flags = h->h_flags;
nh->h_lower = (index_t)
(((char *) &(nh->h_linp[0])) - ((char *) nh));
nh->h_upper = t->bt_psize;
}
return (nh);
}
/*
* _BT_WRITE -- Write a specific page to a btree file.
*
* Parameters:
* t -- btree to get the page
* h -- page to write
* relflag -- (int) this page may/may not be released
*
* Returns:
* RET_SUCCESS, RET_ERROR.
*
* Side Effects:
* Writes a metadata page if none has been written yet.
*/
int
_bt_write(t, h, relflag)
BTREE_P t;
BTHEADER *h;
int relflag;
{
long pos;
int htindex;
HTBUCKET *b;
char *cache;
pgno_t pgno;
h->h_flags &= ~F_DIRTY;
if (ISDISK(t)) {
/* if we haven't done so yet, write the metadata */
if (!(t->bt_flags & BTF_METAOK)) {
if (_bt_wrtmeta(t) == RET_ERROR)
return (RET_ERROR);
}
pgno = h->h_pgno;
/* if we have a cache, let the cache code do the work */
if ((cache = t->bt_s.bt_d.d_cache) != (char *) NULL) {
if (lruwrite(cache, (int) pgno) < 0)
return (RET_ERROR);
if (relflag && lrurelease(cache, (int) pgno) < 0)
return (RET_ERROR);
} else {
(void) _bt_pgout(h, (char *) t->bt_lorder);
/* now write the current page */
pos = (long) (pgno * t->bt_psize);
if (lseek(t->bt_s.bt_d.d_fd, pos, L_SET) != pos)
return (RET_ERROR);
if (write(t->bt_s.bt_d.d_fd, (char *) h, (int) t->bt_psize)
< t->bt_psize)
return (RET_ERROR);
if (!relflag)
(void) _bt_pgin(h, (char *) t->bt_lorder);
}
} else {
/* in-memory btree */
htindex = HASHKEY(h->h_pgno);
/* see if we need to overwrite existing entry */
for (b = t->bt_s.bt_ht[htindex];
b != (HTBUCKET *) NULL;
b = b->ht_next) {
if (b->ht_pgno == h->h_pgno) {
b->ht_page = h;
return (RET_SUCCESS);
}
}
/* new entry, write it */
b = (HTBUCKET *) malloc((unsigned) sizeof (HTBUCKET));
if (b == (HTBUCKET *) NULL)
return (RET_ERROR);
b->ht_pgno = h->h_pgno;
b->ht_page = h;
b->ht_next = t->bt_s.bt_ht[htindex];
t->bt_s.bt_ht[htindex] = b;
}
return (RET_SUCCESS);
}
/*
* _BT_RELEASE -- Release a locked-down cache page
*
* During page splits, we want to force pages out to the cache
* before we actually release them, in some cases. This routine
* releases such a page when it is no longer needed.
*
* Parameters:
* t -- btree in which to release page
* h -- page to release
*
* Returns:
* RET_SUCCESS, RET_ERROR.
*
* Side Effects:
* None.
*/
int
_bt_release(t, h)
BTREE_P t;
BTHEADER *h;
{
if (ISDISK(t) && ISCACHE(t)) {
if (lrurelease(t->bt_s.bt_d.d_cache, (int) (h->h_pgno)) < 0)
return (RET_ERROR);
}
return (RET_SUCCESS);
}
/*
* _BT_WRTMETA -- Write metadata to the btree.
*
* Parameters:
* t -- tree to which to write
*
* Returns:
* RET_SUCCESS, RET_ERROR.
*/
int
_bt_wrtmeta(t)
BTREE_P t;
{
BTMETA m;
if (lseek(t->bt_s.bt_d.d_fd, 0l, L_SET) != 0l)
return (RET_ERROR);
/* lorder has to be in host-independent format */
m.m_lorder = (u_long) htonl((long) t->bt_lorder);
m.m_magic = BTREEMAGIC;
m.m_version = BTREEVERSION;
m.m_psize = t->bt_psize;
m.m_free = t->bt_free;
m.m_flags = t->bt_flags & BTF_NODUPS;
if (t->bt_lorder != BYTE_ORDER) {
BLSWAP(m.m_magic);
BLSWAP(m.m_version);
BLSWAP(m.m_psize);
BLSWAP(m.m_free);
BLSWAP(m.m_flags);
}
if (write(t->bt_s.bt_d.d_fd, (char *) &m, sizeof(m))
!= sizeof(m)) {
return (RET_ERROR);
}
t->bt_flags |= BTF_METAOK;
return (RET_SUCCESS);
}