db2/btree/bt_open.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996, 1997
   5  *      Sleepycat Software.  All rights reserved.
   6  */
   7 /*
   8  * Copyright (c) 1990, 1993, 1994, 1995, 1996
   9  *      Keith Bostic.  All rights reserved.
  10  */
  11 /*
  12  * Copyright (c) 1990, 1993, 1994, 1995
  13  *      The Regents of the University of California.  All rights reserved.
  14  *
  15  * This code is derived from software contributed to Berkeley by
  16  * Mike Olson.
  17  *
  18  * Redistribution and use in source and binary forms, with or without
  19  * modification, are permitted provided that the following conditions
  20  * are met:
  21  * 1. Redistributions of source code must retain the above copyright
  22  *    notice, this list of conditions and the following disclaimer.
  23  * 2. Redistributions in binary form must reproduce the above copyright
  24  *    notice, this list of conditions and the following disclaimer in the
  25  *    documentation and/or other materials provided with the distribution.
  26  * 3. All advertising materials mentioning features or use of this software
  27  *    must display the following acknowledgement:
  28  *      This product includes software developed by the University of
  29  *      California, Berkeley and its contributors.
  30  * 4. Neither the name of the University nor the names of its contributors
  31  *    may be used to endorse or promote products derived from this software
  32  *    without specific prior written permission.
  33  *
  34  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  35  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  36  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  37  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  38  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  39  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  40  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  41  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  42  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  43  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  44  * SUCH DAMAGE.
  45  */
  46
  47 #include "config.h"
  48
  49 #ifndef lint
  50 static const char sccsid[] = "@(#)bt_open.c     10.21 (Sleepycat) 10/25/97";
  51 #endif /* not lint */
  52
  53 /*
  54  * Implementation of btree access method for 4.4BSD.
  55  *
  56  * The design here was originally based on that of the btree access method
  57  * used in the Postgres database system at UC Berkeley.  This implementation
  58  * is wholly independent of the Postgres code.
  59  */
  60
  61 #ifndef NO_SYSTEM_INCLUDES
  62 #include <sys/types.h>
  63 #include <sys/stat.h>
  64
  65 #include <errno.h>
  66 #include <fcntl.h>
  67 #include <limits.h>
  68 #include <stdio.h>
  69 #include <stdlib.h>
  70 #include <string.h>
  71 #include <unistd.h>
  72 #endif
  73
  74 #include "db_int.h"
  75 #include "db_page.h"
  76 #include "btree.h"
  77 #include "common_ext.h"
  78
  79 static int __bam_keyalloc __P((BTREE *));
  80 static int __bam_setmeta __P((DB *, BTREE *));
  81
  82 /*
  83  * __bam_open --
  84  *      Open a btree.
  85  *
  86  * PUBLIC: int __bam_open __P((DB *, DBTYPE, DB_INFO *));
  87  */
  88 int
  89 __bam_open(dbp, type, dbinfo)
  90         DB *dbp;
  91         DBTYPE type;
  92         DB_INFO *dbinfo;
  93 {
  94         BTREE *t;
  95         int ret;
  96
  97         /* Allocate the btree internal structure. */
  98         if ((t = (BTREE *)__db_calloc(1, sizeof(BTREE))) == NULL)
  99                 return (ENOMEM);
 100
 101         t->bt_sp = t->bt_csp = t->bt_stack;
 102         t->bt_esp = t->bt_stack + sizeof(t->bt_stack) / sizeof(t->bt_stack[0]);
 103
 104         if ((type == DB_RECNO || F_ISSET(dbp, DB_BT_RECNUM)) &&
 105             (ret = __bam_keyalloc(t)) != 0)
 106                 goto err;
 107
 108         /*
 109          * Intention is to make sure all of the user's selections are okay
 110          * here and then use them without checking.
 111          */
 112         if (dbinfo != NULL) {
 113                 /* Minimum number of keys per page. */
 114                 if (dbinfo->bt_minkey == 0)
 115                         t->bt_minkey = DEFMINKEYPAGE;
 116                 else {
 117                         if (dbinfo->bt_minkey < 2)
 118                                 goto einval;
 119                         t->bt_minkey = dbinfo->bt_minkey;
 120                 }
 121
 122                 /* Maximum number of keys per page. */
 123                 if (dbinfo->bt_maxkey == 0)
 124                         t->bt_maxkey = 0;
 125                 else {
 126                         if (dbinfo->bt_maxkey < 1)
 127                                 goto einval;
 128                         t->bt_maxkey = dbinfo->bt_maxkey;
 129                 }
 130
 131                 /*
 132                  * If no comparison, use default comparison.  If no comparison
 133                  * and no prefix, use default prefix.  (We can't default the
 134                  * prefix if the user supplies a comparison routine; shortening
 135                  * the keys may break their comparison algorithm.)
 136                  */
 137                 t->bt_compare = dbinfo->bt_compare == NULL ?
 138                     __bam_defcmp : dbinfo->bt_compare;
 139                 t->bt_prefix = dbinfo->bt_prefix == NULL ?
 140                     (dbinfo->bt_compare == NULL ?
 141                     __bam_defpfx : NULL) : dbinfo->bt_prefix;
 142         } else {
 143                 t->bt_minkey = DEFMINKEYPAGE;
 144                 t->bt_compare = __bam_defcmp;
 145                 t->bt_prefix = __bam_defpfx;
 146         }
 147
 148         /* Initialize the remaining fields of the DB. */
 149         dbp->type = type;
 150         dbp->internal = t;
 151         dbp->cursor = __bam_cursor;
 152         dbp->del = __bam_delete;
 153         dbp->get = __bam_get;
 154         dbp->put = __bam_put;
 155         dbp->stat = __bam_stat;
 156         dbp->sync = __bam_sync;
 157
 158         /*
 159          * The btree data structure requires that at least two key/data pairs
 160          * can fit on a page, but other than that there's no fixed requirement.
 161          * Translate the minimum number of items into the bytes a key/data pair
 162          * can use before being placed on an overflow page.  We calculate for
 163          * the worst possible alignment by assuming every item requires the
 164          * maximum alignment for padding.
 165          *
 166          * Recno uses the btree bt_ovflsize value -- it's close enough.
 167          */
 168         t->bt_ovflsize = (dbp->pgsize - P_OVERHEAD) / (t->bt_minkey * P_INDX)
 169             - (BKEYDATA_PSIZE(0) + ALIGN(1, 4));
 170
 171         /* Create a root page if new tree. */
 172         if ((ret = __bam_setmeta(dbp, t)) != 0)
 173                 goto err;
 174
 175         return (0);
 176
 177 einval: ret = EINVAL;
 178
 179 err:    if (t != NULL) {
 180                 /* If we allocated room for key/data return, discard it. */
 181                 if (t->bt_rkey.data != NULL)
 182                         __db_free(t->bt_rkey.data);
 183
 184                 FREE(t, sizeof(BTREE));
 185         }
 186         return (ret);
 187 }
 188
 189 /*
 190  * __bam_bdup --
 191  *      Create a BTREE handle for a threaded DB handle.
 192  *
 193  * PUBLIC: int __bam_bdup __P((DB *, DB *));
 194  */
 195 int
 196 __bam_bdup(orig, new)
 197         DB *orig, *new;
 198 {
 199         BTREE *t, *ot;
 200         int ret;
 201
 202         ot = orig->internal;
 203
 204         if ((t = (BTREE *)__db_calloc(1, sizeof(*t))) == NULL)
 205                 return (ENOMEM);
 206
 207         /*
 208          * !!!
 209          * Ignore the cursor queue, only the first DB has attached cursors.
 210          */
 211
 212         t->bt_sp = t->bt_csp = t->bt_stack;
 213         t->bt_esp = t->bt_stack + sizeof(t->bt_stack) / sizeof(t->bt_stack[0]);
 214
 215         if ((orig->type == DB_RECNO || F_ISSET(orig, DB_BT_RECNUM)) &&
 216             (ret = __bam_keyalloc(t)) != 0) {
 217                 FREE(t, sizeof(*t));
 218                 return (ret);
 219         }
 220
 221         t->bt_maxkey = ot->bt_maxkey;
 222         t->bt_minkey = ot->bt_minkey;
 223         t->bt_compare = ot->bt_compare;
 224         t->bt_prefix = ot->bt_prefix;
 225         t->bt_ovflsize = ot->bt_ovflsize;
 226
 227         /*
 228          * !!!
 229          * The entire RECNO structure is shared.  If it breaks, the application
 230          * was misusing it to start with.
 231          */
 232         t->bt_recno = ot->bt_recno;
 233
 234         new->internal = t;
 235
 236         return (0);
 237 }
 238
 239 /*
 240  * __bam_keyalloc --
 241  *      Allocate return memory for recno keys.
 242  */
 243 static int
 244 __bam_keyalloc(t)
 245         BTREE *t;
 246 {
 247         /*
 248          * Recno keys are always the same size, and we don't want to have
 249          * to check for space on each return.  Allocate it now.
 250          */
 251         if ((t->bt_rkey.data = (void *)__db_malloc(sizeof(db_recno_t))) == NULL)
 252                 return (ENOMEM);
 253         t->bt_rkey.ulen = sizeof(db_recno_t);
 254         return (0);
 255 }
 256
 257 /*
 258  * __bam_setmeta --
 259  *      Check (and optionally create) a tree.
 260  */
 261 static int
 262 __bam_setmeta(dbp, t)
 263         DB *dbp;
 264         BTREE *t;
 265 {
 266         BTMETA *meta;
 267         PAGE *root;
 268         DB_LOCK mlock, rlock;
 269         db_pgno_t pgno;
 270         int ret;
 271
 272         /* Get, and optionally create the metadata page. */
 273         pgno = PGNO_METADATA;
 274         if ((ret =
 275             __bam_lget(dbp, 0, PGNO_METADATA, DB_LOCK_WRITE, &mlock)) != 0)
 276                 return (ret);
 277         if ((ret =
 278             __bam_pget(dbp, (PAGE **)&meta, &pgno, DB_MPOOL_CREATE)) != 0) {
 279                 (void)__BT_LPUT(dbp, mlock);
 280                 return (ret);
 281         }
 282
 283         /*
 284          * If the magic number is correct, we're not creating the tree.
 285          * Correct any fields that may not be right.  Note, all of the
 286          * local flags were set by db_open(3).
 287          */
 288         if (meta->magic != 0) {
 289                 t->bt_maxkey = meta->maxkey;
 290                 t->bt_minkey = meta->minkey;
 291
 292                 (void)memp_fput(dbp->mpf, (PAGE *)meta, 0);
 293                 (void)__BT_LPUT(dbp, mlock);
 294                 return (0);
 295         }
 296
 297         /* Initialize the tree structure metadata information. */
 298         ZERO_LSN(meta->lsn);
 299         meta->pgno = PGNO_METADATA;
 300         meta->magic = DB_BTREEMAGIC;
 301         meta->version = DB_BTREEVERSION;
 302         meta->pagesize = dbp->pgsize;
 303         meta->maxkey = t->bt_maxkey;
 304         meta->minkey = t->bt_minkey;
 305         meta->free = PGNO_INVALID;
 306         meta->flags = 0;
 307         if (dbp->type == DB_RECNO)
 308                 F_SET(meta, BTM_RECNO);
 309         if (F_ISSET(dbp, DB_AM_DUP))
 310                 F_SET(meta, BTM_DUP);
 311         if (F_ISSET(dbp, DB_RE_FIXEDLEN))
 312                 F_SET(meta, BTM_FIXEDLEN);
 313         if (F_ISSET(dbp, DB_BT_RECNUM))
 314                 F_SET(meta, BTM_RECNUM);
 315         if (F_ISSET(dbp, DB_RE_RENUMBER))
 316                 F_SET(meta, BTM_RENUMBER);
 317         meta->re_len = 0;
 318         meta->re_pad = 0;
 319         memcpy(meta->uid, dbp->lock.fileid, DB_FILE_ID_LEN);
 320
 321         /* Create and initialize a root page. */
 322         pgno = PGNO_ROOT;
 323         if ((ret = __bam_lget(dbp, 0, PGNO_ROOT, DB_LOCK_WRITE, &rlock)) != 0)
 324                 return (ret);
 325         if ((ret = __bam_pget(dbp, &root, &pgno, DB_MPOOL_CREATE)) != 0) {
 326                 (void)__BT_LPUT(dbp, rlock);
 327                 return (ret);
 328         }
 329         P_INIT(root, dbp->pgsize, PGNO_ROOT, PGNO_INVALID,
 330             PGNO_INVALID, 1, dbp->type == DB_RECNO ? P_LRECNO : P_LBTREE);
 331         ZERO_LSN(root->lsn);
 332
 333         /* Release the metadata and root pages. */
 334         if ((ret = memp_fput(dbp->mpf, (PAGE *)meta, DB_MPOOL_DIRTY)) != 0)
 335                 return (ret);
 336         if ((ret = memp_fput(dbp->mpf, root, DB_MPOOL_DIRTY)) != 0)
 337                 return (ret);
 338
 339         /*
 340          * Flush the metadata and root pages to disk -- since the user can't
 341          * transaction protect open, the pages have to exist during recovery.
 342          *
 343          * XXX
 344          * It's not useful to return not-yet-flushed here -- convert it to
 345          * an error.
 346          */
 347         if ((ret = memp_fsync(dbp->mpf)) == DB_INCOMPLETE)
 348                 ret = EINVAL;
 349
 350         /* Release the locks. */
 351         (void)__BT_LPUT(dbp, mlock);
 352         (void)__BT_LPUT(dbp, rlock);
 353
 354         return (ret);
 355 }