1*aae80e6bSchristos /* $NetBSD: bt_open.c,v 1.29 2016/09/24 21:31:25 christos Exp $ */
2a954b078Scgd
39f0aa214Scgd /*-
4a6d14e36Scgd * Copyright (c) 1990, 1993, 1994
59f0aa214Scgd * The Regents of the University of California. All rights reserved.
69f0aa214Scgd *
79f0aa214Scgd * This code is derived from software contributed to Berkeley by
89f0aa214Scgd * Mike Olson.
99f0aa214Scgd *
109f0aa214Scgd * Redistribution and use in source and binary forms, with or without
119f0aa214Scgd * modification, are permitted provided that the following conditions
129f0aa214Scgd * are met:
139f0aa214Scgd * 1. Redistributions of source code must retain the above copyright
149f0aa214Scgd * notice, this list of conditions and the following disclaimer.
159f0aa214Scgd * 2. Redistributions in binary form must reproduce the above copyright
169f0aa214Scgd * notice, this list of conditions and the following disclaimer in the
179f0aa214Scgd * documentation and/or other materials provided with the distribution.
18eb7c1594Sagc * 3. Neither the name of the University nor the names of its contributors
199f0aa214Scgd * may be used to endorse or promote products derived from this software
209f0aa214Scgd * without specific prior written permission.
219f0aa214Scgd *
229f0aa214Scgd * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
239f0aa214Scgd * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
249f0aa214Scgd * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
259f0aa214Scgd * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
269f0aa214Scgd * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
279f0aa214Scgd * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
289f0aa214Scgd * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
299f0aa214Scgd * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
309f0aa214Scgd * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
319f0aa214Scgd * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
329f0aa214Scgd * SUCH DAMAGE.
339f0aa214Scgd */
349f0aa214Scgd
35d3595ddfSjoerg #if HAVE_NBTOOL_CONFIG_H
36d3595ddfSjoerg #include "nbtool_config.h"
37d3595ddfSjoerg #endif
38d3595ddfSjoerg
3900ae392dSchristos #include <sys/cdefs.h>
40*aae80e6bSchristos __RCSID("$NetBSD: bt_open.c,v 1.29 2016/09/24 21:31:25 christos Exp $");
419f0aa214Scgd
429f0aa214Scgd /*
439f0aa214Scgd * Implementation of btree access method for 4.4BSD.
449f0aa214Scgd *
459f0aa214Scgd * The design here was originally based on that of the btree access method
469f0aa214Scgd * used in the Postgres database system at UC Berkeley. This implementation
479f0aa214Scgd * is wholly independent of the Postgres code.
489f0aa214Scgd */
499f0aa214Scgd
5043fa6fe3Sjtc #include "namespace.h"
519f0aa214Scgd #include <sys/stat.h>
529f0aa214Scgd
53cb9daf8fSchristos #include <assert.h>
549f0aa214Scgd #include <errno.h>
559f0aa214Scgd #include <fcntl.h>
569f0aa214Scgd #include <limits.h>
579f0aa214Scgd #include <signal.h>
589f0aa214Scgd #include <stdio.h>
599f0aa214Scgd #include <stdlib.h>
609f0aa214Scgd #include <string.h>
619f0aa214Scgd #include <unistd.h>
625f062167Sfair #include <paths.h>
639f0aa214Scgd
649f0aa214Scgd #include <db.h>
659f0aa214Scgd #include "btree.h"
669f0aa214Scgd
6724420c01Scgd #ifdef DEBUG
6824420c01Scgd #undef MINPSIZE
6924420c01Scgd #define MINPSIZE 128
7024420c01Scgd #endif
7124420c01Scgd
72cb9daf8fSchristos static int byteorder(void);
73cb9daf8fSchristos static int nroot(BTREE *);
749f0aa214Scgd
759f0aa214Scgd /*
769f0aa214Scgd * __BT_OPEN -- Open a btree.
779f0aa214Scgd *
789f0aa214Scgd * Creates and fills a DB struct, and calls the routine that actually
799f0aa214Scgd * opens the btree.
809f0aa214Scgd *
819f0aa214Scgd * Parameters:
829f0aa214Scgd * fname: filename (NULL for in-memory trees)
839f0aa214Scgd * flags: open flag bits
849f0aa214Scgd * mode: open permission bits
859f0aa214Scgd * b: BTREEINFO pointer
869f0aa214Scgd *
879f0aa214Scgd * Returns:
889f0aa214Scgd * NULL on failure, pointer to DB on success.
899f0aa214Scgd *
909f0aa214Scgd */
919f0aa214Scgd DB *
__bt_open(const char * fname,int flags,mode_t mode,const BTREEINFO * openinfo,int dflags)92cb9daf8fSchristos __bt_open(const char *fname, int flags, mode_t mode, const BTREEINFO *openinfo,
93cb9daf8fSchristos int dflags)
949f0aa214Scgd {
95a6d14e36Scgd struct stat sb;
969f0aa214Scgd BTMETA m;
979f0aa214Scgd BTREE *t;
989f0aa214Scgd BTREEINFO b;
999f0aa214Scgd DB *dbp;
1009f0aa214Scgd pgno_t ncache;
101a6d14e36Scgd ssize_t nr;
102cb9daf8fSchristos size_t temp;
103a6d14e36Scgd int machine_lorder;
1049f0aa214Scgd
1059f0aa214Scgd t = NULL;
1069f0aa214Scgd
1079f0aa214Scgd /*
1089f0aa214Scgd * Intention is to make sure all of the user's selections are okay
1099f0aa214Scgd * here and then use them without checking. Can't be complete, since
1109f0aa214Scgd * we don't know the right page size, lorder or flags until the backing
1119f0aa214Scgd * file is opened. Also, the file's page size can cause the cachesize
1129f0aa214Scgd * to change.
1139f0aa214Scgd */
1149f0aa214Scgd machine_lorder = byteorder();
1159f0aa214Scgd if (openinfo) {
1169f0aa214Scgd b = *openinfo;
1179f0aa214Scgd
1189f0aa214Scgd /* Flags: R_DUP. */
1199f0aa214Scgd if (b.flags & ~(R_DUP))
1209f0aa214Scgd goto einval;
1219f0aa214Scgd
1229f0aa214Scgd /*
1239f0aa214Scgd * Page size must be indx_t aligned and >= MINPSIZE. Default
1249f0aa214Scgd * page size is set farther on, based on the underlying file
1259f0aa214Scgd * transfer size.
1269f0aa214Scgd */
1279f0aa214Scgd if (b.psize &&
1289f0aa214Scgd (b.psize < MINPSIZE || b.psize > MAX_PAGE_OFFSET + 1 ||
12900ae392dSchristos b.psize & (sizeof(indx_t) - 1)))
1309f0aa214Scgd goto einval;
1319f0aa214Scgd
1329f0aa214Scgd /* Minimum number of keys per page; absolute minimum is 2. */
1339f0aa214Scgd if (b.minkeypage) {
1349f0aa214Scgd if (b.minkeypage < 2)
1359f0aa214Scgd goto einval;
1369f0aa214Scgd } else
1379f0aa214Scgd b.minkeypage = DEFMINKEYPAGE;
1389f0aa214Scgd
1399f0aa214Scgd /* If no comparison, use default comparison and prefix. */
1409f0aa214Scgd if (b.compare == NULL) {
1419f0aa214Scgd b.compare = __bt_defcmp;
1429f0aa214Scgd if (b.prefix == NULL)
1439f0aa214Scgd b.prefix = __bt_defpfx;
1449f0aa214Scgd }
1459f0aa214Scgd
1469f0aa214Scgd if (b.lorder == 0)
1479f0aa214Scgd b.lorder = machine_lorder;
1489f0aa214Scgd } else {
1499f0aa214Scgd b.compare = __bt_defcmp;
1509f0aa214Scgd b.cachesize = 0;
1519f0aa214Scgd b.flags = 0;
1529f0aa214Scgd b.lorder = machine_lorder;
1539f0aa214Scgd b.minkeypage = DEFMINKEYPAGE;
1549f0aa214Scgd b.prefix = __bt_defpfx;
1559f0aa214Scgd b.psize = 0;
1569f0aa214Scgd }
1579f0aa214Scgd
1589f0aa214Scgd /* Check for the ubiquitous PDP-11. */
1599f0aa214Scgd if (b.lorder != BIG_ENDIAN && b.lorder != LITTLE_ENDIAN)
1609f0aa214Scgd goto einval;
1619f0aa214Scgd
1629f0aa214Scgd /* Allocate and initialize DB and BTREE structures. */
163b605a13bSchristos if ((t = malloc(sizeof(*t))) == NULL)
1649f0aa214Scgd goto err;
16565aeeefbScgd memset(t, 0, sizeof(BTREE));
16665aeeefbScgd t->bt_fd = -1; /* Don't close unopened fd on error. */
1679f0aa214Scgd t->bt_lorder = b.lorder;
1689f0aa214Scgd t->bt_order = NOT;
1699f0aa214Scgd t->bt_cmp = b.compare;
1709f0aa214Scgd t->bt_pfx = b.prefix;
17165aeeefbScgd t->bt_rfd = -1;
17265aeeefbScgd
173b605a13bSchristos if ((t->bt_dbp = dbp = malloc(sizeof(*dbp))) == NULL)
17465aeeefbScgd goto err;
17524420c01Scgd memset(t->bt_dbp, 0, sizeof(DB));
1769f0aa214Scgd if (t->bt_lorder != machine_lorder)
17724420c01Scgd F_SET(t, B_NEEDSWAP);
1789f0aa214Scgd
1799f0aa214Scgd dbp->type = DB_BTREE;
1809f0aa214Scgd dbp->internal = t;
1819f0aa214Scgd dbp->close = __bt_close;
1829f0aa214Scgd dbp->del = __bt_delete;
1839f0aa214Scgd dbp->fd = __bt_fd;
1849f0aa214Scgd dbp->get = __bt_get;
1859f0aa214Scgd dbp->put = __bt_put;
1869f0aa214Scgd dbp->seq = __bt_seq;
1879f0aa214Scgd dbp->sync = __bt_sync;
1889f0aa214Scgd
1899f0aa214Scgd /*
1909f0aa214Scgd * If no file name was supplied, this is an in-memory btree and we
1919f0aa214Scgd * open a backing temporary file. Otherwise, it's a disk-based tree.
1929f0aa214Scgd */
1939f0aa214Scgd if (fname) {
1949f0aa214Scgd switch (flags & O_ACCMODE) {
1959f0aa214Scgd case O_RDONLY:
19624420c01Scgd F_SET(t, B_RDONLY);
1979f0aa214Scgd break;
1989f0aa214Scgd case O_RDWR:
1999f0aa214Scgd break;
2009f0aa214Scgd case O_WRONLY:
2019f0aa214Scgd default:
2029f0aa214Scgd goto einval;
2039f0aa214Scgd }
204b605a13bSchristos if ((t->bt_fd = __dbopen(fname, flags, mode, &sb)) == -1)
205b7e6351cSmycroft goto err;
2069f0aa214Scgd } else {
2079f0aa214Scgd if ((flags & O_ACCMODE) != O_RDWR)
2089f0aa214Scgd goto einval;
209b605a13bSchristos if ((t->bt_fd = __dbtemp("bt.", &sb)) == -1)
2109f0aa214Scgd goto err;
21124420c01Scgd F_SET(t, B_INMEM);
2129f0aa214Scgd }
2139f0aa214Scgd
2149f0aa214Scgd
2159f0aa214Scgd if (sb.st_size) {
216a6d14e36Scgd if ((nr = read(t->bt_fd, &m, sizeof(BTMETA))) < 0)
2179f0aa214Scgd goto err;
2189f0aa214Scgd if (nr != sizeof(BTMETA))
2199f0aa214Scgd goto eftype;
2209f0aa214Scgd
2219f0aa214Scgd /*
2229f0aa214Scgd * Read in the meta-data. This can change the notion of what
2239f0aa214Scgd * the lorder, page size and flags are, and, when the page size
2249f0aa214Scgd * changes, the cachesize value can change too. If the user
2259f0aa214Scgd * specified the wrong byte order for an existing database, we
2269f0aa214Scgd * don't bother to return an error, we just clear the NEEDSWAP
2279f0aa214Scgd * bit.
2289f0aa214Scgd */
22924420c01Scgd if (m.magic == BTREEMAGIC)
23024420c01Scgd F_CLR(t, B_NEEDSWAP);
2319f0aa214Scgd else {
23224420c01Scgd F_SET(t, B_NEEDSWAP);
23324420c01Scgd M_32_SWAP(m.magic);
23424420c01Scgd M_32_SWAP(m.version);
23524420c01Scgd M_32_SWAP(m.psize);
23624420c01Scgd M_32_SWAP(m.free);
23724420c01Scgd M_32_SWAP(m.nrecs);
23824420c01Scgd M_32_SWAP(m.flags);
2399f0aa214Scgd }
24024420c01Scgd if (m.magic != BTREEMAGIC || m.version != BTREEVERSION)
2419f0aa214Scgd goto eftype;
24224420c01Scgd if (m.psize < MINPSIZE || m.psize > MAX_PAGE_OFFSET + 1 ||
24300ae392dSchristos m.psize & (sizeof(indx_t) - 1))
2449f0aa214Scgd goto eftype;
24524420c01Scgd if (m.flags & ~SAVEMETA)
2469f0aa214Scgd goto eftype;
24724420c01Scgd b.psize = m.psize;
24824420c01Scgd F_SET(t, m.flags);
24924420c01Scgd t->bt_free = m.free;
25024420c01Scgd t->bt_nrecs = m.nrecs;
2519f0aa214Scgd } else {
2529f0aa214Scgd /*
2539f0aa214Scgd * Set the page size to the best value for I/O to this file.
2549f0aa214Scgd * Don't overflow the page offset type.
2559f0aa214Scgd */
2569f0aa214Scgd if (b.psize == 0) {
2579f0aa214Scgd b.psize = sb.st_blksize;
2589f0aa214Scgd if (b.psize < MINPSIZE)
2599f0aa214Scgd b.psize = MINPSIZE;
2609f0aa214Scgd if (b.psize > MAX_PAGE_OFFSET + 1)
2619f0aa214Scgd b.psize = MAX_PAGE_OFFSET + 1;
2629f0aa214Scgd }
2639f0aa214Scgd
2649f0aa214Scgd /* Set flag if duplicates permitted. */
2659f0aa214Scgd if (!(b.flags & R_DUP))
26624420c01Scgd F_SET(t, B_NODUPS);
2679f0aa214Scgd
2689f0aa214Scgd t->bt_free = P_INVALID;
2699f0aa214Scgd t->bt_nrecs = 0;
27024420c01Scgd F_SET(t, B_METADIRTY);
2719f0aa214Scgd }
2729f0aa214Scgd
2739f0aa214Scgd t->bt_psize = b.psize;
2749f0aa214Scgd
2759f0aa214Scgd /* Set the cache size; must be a multiple of the page size. */
27600ae392dSchristos if (b.cachesize && b.cachesize & (b.psize - 1))
27700ae392dSchristos b.cachesize += (~b.cachesize & (b.psize - 1)) + 1;
2789f0aa214Scgd if (b.cachesize < b.psize * MINCACHE)
2799f0aa214Scgd b.cachesize = b.psize * MINCACHE;
2809f0aa214Scgd
2819f0aa214Scgd /* Calculate number of pages to cache. */
2829f0aa214Scgd ncache = (b.cachesize + t->bt_psize - 1) / t->bt_psize;
2839f0aa214Scgd
2849f0aa214Scgd /*
2859f0aa214Scgd * The btree data structure requires that at least two keys can fit on
2869f0aa214Scgd * a page, but other than that there's no fixed requirement. The user
2879f0aa214Scgd * specified a minimum number per page, and we translated that into the
2889f0aa214Scgd * number of bytes a key/data pair can use before being placed on an
2899f0aa214Scgd * overflow page. This calculation includes the page header, the size
2909f0aa214Scgd * of the index referencing the leaf item and the size of the leaf item
2919f0aa214Scgd * structure. Also, don't let the user specify a minkeypage such that
2929f0aa214Scgd * a key/data pair won't fit even if both key and data are on overflow
2939f0aa214Scgd * pages.
2949f0aa214Scgd */
295cb9daf8fSchristos temp = (t->bt_psize - BTDATAOFF) / b.minkeypage -
2969f0aa214Scgd (sizeof(indx_t) + NBLEAFDBT(0, 0));
297cb9daf8fSchristos _DBFIT(temp, indx_t);
298cb9daf8fSchristos t->bt_ovflsize = (indx_t)temp;
299c5e820caSchristos if (t->bt_ovflsize < NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t)) {
300c5e820caSchristos size_t l = NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t);
301c5e820caSchristos _DBFIT(l, indx_t);
302c5e820caSchristos t->bt_ovflsize = (indx_t)l;
303c5e820caSchristos }
3049f0aa214Scgd
3059f0aa214Scgd /* Initialize the buffer pool. */
3069f0aa214Scgd if ((t->bt_mp =
3079f0aa214Scgd mpool_open(NULL, t->bt_fd, t->bt_psize, ncache)) == NULL)
3089f0aa214Scgd goto err;
30924420c01Scgd if (!F_ISSET(t, B_INMEM))
3109f0aa214Scgd mpool_filter(t->bt_mp, __bt_pgin, __bt_pgout, t);
3119f0aa214Scgd
3129f0aa214Scgd /* Create a root page if new tree. */
3139f0aa214Scgd if (nroot(t) == RET_ERROR)
3149f0aa214Scgd goto err;
3159f0aa214Scgd
31645e27c80Scgd /* Global flags. */
31745e27c80Scgd if (dflags & DB_LOCK)
31824420c01Scgd F_SET(t, B_DB_LOCK);
31945e27c80Scgd if (dflags & DB_SHMEM)
32024420c01Scgd F_SET(t, B_DB_SHMEM);
32145e27c80Scgd if (dflags & DB_TXN)
32224420c01Scgd F_SET(t, B_DB_TXN);
32345e27c80Scgd
3249f0aa214Scgd return (dbp);
3259f0aa214Scgd
3269f0aa214Scgd einval: errno = EINVAL;
3279f0aa214Scgd goto err;
3289f0aa214Scgd
3299f0aa214Scgd eftype: errno = EFTYPE;
3309f0aa214Scgd goto err;
3319f0aa214Scgd
3329f0aa214Scgd err: if (t) {
3339f0aa214Scgd if (t->bt_dbp)
3349f0aa214Scgd free(t->bt_dbp);
3359f0aa214Scgd if (t->bt_fd != -1)
3369f0aa214Scgd (void)close(t->bt_fd);
3379f0aa214Scgd free(t);
3389f0aa214Scgd }
3399f0aa214Scgd return (NULL);
3409f0aa214Scgd }
3419f0aa214Scgd
3429f0aa214Scgd /*
3439f0aa214Scgd * NROOT -- Create the root of a new tree.
3449f0aa214Scgd *
3459f0aa214Scgd * Parameters:
3469f0aa214Scgd * t: tree
3479f0aa214Scgd *
3489f0aa214Scgd * Returns:
3499f0aa214Scgd * RET_ERROR, RET_SUCCESS
3509f0aa214Scgd */
3519f0aa214Scgd static int
nroot(BTREE * t)352cb9daf8fSchristos nroot(BTREE *t)
3539f0aa214Scgd {
3549f0aa214Scgd PAGE *meta, *root;
3559f0aa214Scgd pgno_t npg;
3569f0aa214Scgd
357*aae80e6bSchristos if ((root = mpool_get(t->bt_mp, 1, 0)) != NULL) {
35886147b1cSchristos if (root->lower == 0 &&
35986147b1cSchristos root->pgno == 0 &&
36086147b1cSchristos root->linp[0] == 0) {
36186147b1cSchristos mpool_delete(t->bt_mp, root);
36286147b1cSchristos errno = EINVAL;
36386147b1cSchristos } else {
36486147b1cSchristos mpool_put(t->bt_mp, root, 0);
36586147b1cSchristos return RET_SUCCESS;
36686147b1cSchristos }
3679f0aa214Scgd }
368a6d14e36Scgd if (errno != EINVAL) /* It's OK to not exist. */
3699f0aa214Scgd return (RET_ERROR);
370a6d14e36Scgd errno = 0;
3719f0aa214Scgd
37286147b1cSchristos if ((meta = mpool_newf(t->bt_mp, &npg, MPOOL_PAGE_NEXT)) == NULL)
3739f0aa214Scgd return (RET_ERROR);
3749f0aa214Scgd
37586147b1cSchristos if ((root = mpool_newf(t->bt_mp, &npg, MPOOL_PAGE_NEXT)) == NULL)
3769f0aa214Scgd return (RET_ERROR);
3779f0aa214Scgd
3789f0aa214Scgd if (npg != P_ROOT)
3799f0aa214Scgd return (RET_ERROR);
3809f0aa214Scgd root->pgno = npg;
3819f0aa214Scgd root->prevpg = root->nextpg = P_INVALID;
3829f0aa214Scgd root->lower = BTDATAOFF;
3839f0aa214Scgd root->upper = t->bt_psize;
3849f0aa214Scgd root->flags = P_BLEAF;
3859f0aa214Scgd memset(meta, 0, t->bt_psize);
3869f0aa214Scgd mpool_put(t->bt_mp, meta, MPOOL_DIRTY);
3879f0aa214Scgd mpool_put(t->bt_mp, root, MPOOL_DIRTY);
3889f0aa214Scgd return (RET_SUCCESS);
3899f0aa214Scgd }
3909f0aa214Scgd
3919f0aa214Scgd static int
byteorder(void)392cb9daf8fSchristos byteorder(void)
3939f0aa214Scgd {
39440b37a3bSjoerg uint32_t x;
39540b37a3bSjoerg uint8_t *p;
3969f0aa214Scgd
3979f0aa214Scgd x = 0x01020304;
39840b37a3bSjoerg p = (uint8_t *)(void *)&x;
3999f0aa214Scgd switch (*p) {
4009f0aa214Scgd case 1:
4019f0aa214Scgd return (BIG_ENDIAN);
4029f0aa214Scgd case 4:
4039f0aa214Scgd return (LITTLE_ENDIAN);
4049f0aa214Scgd default:
4059f0aa214Scgd return (0);
4069f0aa214Scgd }
4079f0aa214Scgd }
4089f0aa214Scgd
4099f0aa214Scgd int
__bt_fd(const DB * dbp)410cb9daf8fSchristos __bt_fd(const DB *dbp)
4119f0aa214Scgd {
4129f0aa214Scgd BTREE *t;
4139f0aa214Scgd
4149f0aa214Scgd t = dbp->internal;
4159f0aa214Scgd
41645e27c80Scgd /* Toss any page pinned across calls. */
41745e27c80Scgd if (t->bt_pinned != NULL) {
41845e27c80Scgd mpool_put(t->bt_mp, t->bt_pinned, 0);
41945e27c80Scgd t->bt_pinned = NULL;
42045e27c80Scgd }
42145e27c80Scgd
42245e27c80Scgd /* In-memory database can't have a file descriptor. */
42324420c01Scgd if (F_ISSET(t, B_INMEM)) {
4249f0aa214Scgd errno = ENOENT;
4259f0aa214Scgd return (-1);
4269f0aa214Scgd }
4279f0aa214Scgd return (t->bt_fd);
4289f0aa214Scgd }
429