bt_open.c revision 1.16 1 1.16 thorpej /* $NetBSD: bt_open.c,v 1.16 2002/11/11 01:17:20 thorpej Exp $ */
2 1.7 cgd
3 1.1 cgd /*-
4 1.6 cgd * Copyright (c) 1990, 1993, 1994
5 1.1 cgd * The Regents of the University of California. All rights reserved.
6 1.1 cgd *
7 1.1 cgd * This code is derived from software contributed to Berkeley by
8 1.1 cgd * Mike Olson.
9 1.1 cgd *
10 1.1 cgd * Redistribution and use in source and binary forms, with or without
11 1.1 cgd * modification, are permitted provided that the following conditions
12 1.1 cgd * are met:
13 1.1 cgd * 1. Redistributions of source code must retain the above copyright
14 1.1 cgd * notice, this list of conditions and the following disclaimer.
15 1.1 cgd * 2. Redistributions in binary form must reproduce the above copyright
16 1.1 cgd * notice, this list of conditions and the following disclaimer in the
17 1.1 cgd * documentation and/or other materials provided with the distribution.
18 1.1 cgd * 3. All advertising materials mentioning features or use of this software
19 1.1 cgd * must display the following acknowledgement:
20 1.1 cgd * This product includes software developed by the University of
21 1.1 cgd * California, Berkeley and its contributors.
22 1.1 cgd * 4. Neither the name of the University nor the names of its contributors
23 1.1 cgd * may be used to endorse or promote products derived from this software
24 1.1 cgd * without specific prior written permission.
25 1.1 cgd *
26 1.1 cgd * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 1.1 cgd * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 1.1 cgd * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 1.1 cgd * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 1.1 cgd * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 1.1 cgd * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 1.1 cgd * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 1.1 cgd * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 1.1 cgd * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 1.1 cgd * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 1.1 cgd * SUCH DAMAGE.
37 1.1 cgd */
38 1.1 cgd
39 1.9 christos #include <sys/cdefs.h>
40 1.1 cgd #if defined(LIBC_SCCS) && !defined(lint)
41 1.7 cgd #if 0
42 1.8 cgd static char sccsid[] = "@(#)bt_open.c 8.10 (Berkeley) 8/17/94";
43 1.7 cgd #else
44 1.16 thorpej __RCSID("$NetBSD: bt_open.c,v 1.16 2002/11/11 01:17:20 thorpej Exp $");
45 1.7 cgd #endif
46 1.1 cgd #endif /* LIBC_SCCS and not lint */
47 1.1 cgd
48 1.1 cgd /*
49 1.1 cgd * Implementation of btree access method for 4.4BSD.
50 1.1 cgd *
51 1.1 cgd * The design here was originally based on that of the btree access method
52 1.1 cgd * used in the Postgres database system at UC Berkeley. This implementation
53 1.1 cgd * is wholly independent of the Postgres code.
54 1.1 cgd */
55 1.1 cgd
56 1.10 jtc #include "namespace.h"
57 1.1 cgd #include <sys/stat.h>
58 1.1 cgd
59 1.1 cgd #include <errno.h>
60 1.1 cgd #include <fcntl.h>
61 1.1 cgd #include <limits.h>
62 1.1 cgd #include <signal.h>
63 1.1 cgd #include <stdio.h>
64 1.1 cgd #include <stdlib.h>
65 1.1 cgd #include <string.h>
66 1.1 cgd #include <unistd.h>
67 1.11 fair #include <paths.h>
68 1.1 cgd
69 1.1 cgd #include <db.h>
70 1.1 cgd #include "btree.h"
71 1.1 cgd
72 1.8 cgd #ifdef DEBUG
73 1.8 cgd #undef MINPSIZE
74 1.8 cgd #define MINPSIZE 128
75 1.8 cgd #endif
76 1.8 cgd
77 1.1 cgd static int byteorder __P((void));
78 1.1 cgd static int nroot __P((BTREE *));
79 1.1 cgd static int tmp __P((void));
80 1.1 cgd
81 1.1 cgd /*
82 1.1 cgd * __BT_OPEN -- Open a btree.
83 1.1 cgd *
84 1.1 cgd * Creates and fills a DB struct, and calls the routine that actually
85 1.1 cgd * opens the btree.
86 1.1 cgd *
87 1.1 cgd * Parameters:
88 1.1 cgd * fname: filename (NULL for in-memory trees)
89 1.1 cgd * flags: open flag bits
90 1.1 cgd * mode: open permission bits
91 1.1 cgd * b: BTREEINFO pointer
92 1.1 cgd *
93 1.1 cgd * Returns:
94 1.1 cgd * NULL on failure, pointer to DB on success.
95 1.1 cgd *
96 1.1 cgd */
97 1.1 cgd DB *
98 1.4 cgd __bt_open(fname, flags, mode, openinfo, dflags)
99 1.1 cgd const char *fname;
100 1.12 kleink int flags;
101 1.12 kleink mode_t mode;
102 1.1 cgd const BTREEINFO *openinfo;
103 1.12 kleink int dflags;
104 1.1 cgd {
105 1.6 cgd struct stat sb;
106 1.1 cgd BTMETA m;
107 1.1 cgd BTREE *t;
108 1.1 cgd BTREEINFO b;
109 1.1 cgd DB *dbp;
110 1.1 cgd pgno_t ncache;
111 1.6 cgd ssize_t nr;
112 1.6 cgd int machine_lorder;
113 1.1 cgd
114 1.1 cgd t = NULL;
115 1.1 cgd
116 1.1 cgd /*
117 1.1 cgd * Intention is to make sure all of the user's selections are okay
118 1.1 cgd * here and then use them without checking. Can't be complete, since
119 1.1 cgd * we don't know the right page size, lorder or flags until the backing
120 1.1 cgd * file is opened. Also, the file's page size can cause the cachesize
121 1.1 cgd * to change.
122 1.1 cgd */
123 1.1 cgd machine_lorder = byteorder();
124 1.1 cgd if (openinfo) {
125 1.1 cgd b = *openinfo;
126 1.1 cgd
127 1.1 cgd /* Flags: R_DUP. */
128 1.1 cgd if (b.flags & ~(R_DUP))
129 1.1 cgd goto einval;
130 1.1 cgd
131 1.1 cgd /*
132 1.1 cgd * Page size must be indx_t aligned and >= MINPSIZE. Default
133 1.1 cgd * page size is set farther on, based on the underlying file
134 1.1 cgd * transfer size.
135 1.1 cgd */
136 1.1 cgd if (b.psize &&
137 1.1 cgd (b.psize < MINPSIZE || b.psize > MAX_PAGE_OFFSET + 1 ||
138 1.9 christos b.psize & (sizeof(indx_t) - 1)))
139 1.1 cgd goto einval;
140 1.1 cgd
141 1.1 cgd /* Minimum number of keys per page; absolute minimum is 2. */
142 1.1 cgd if (b.minkeypage) {
143 1.1 cgd if (b.minkeypage < 2)
144 1.1 cgd goto einval;
145 1.1 cgd } else
146 1.1 cgd b.minkeypage = DEFMINKEYPAGE;
147 1.1 cgd
148 1.1 cgd /* If no comparison, use default comparison and prefix. */
149 1.1 cgd if (b.compare == NULL) {
150 1.1 cgd b.compare = __bt_defcmp;
151 1.1 cgd if (b.prefix == NULL)
152 1.1 cgd b.prefix = __bt_defpfx;
153 1.1 cgd }
154 1.1 cgd
155 1.1 cgd if (b.lorder == 0)
156 1.1 cgd b.lorder = machine_lorder;
157 1.1 cgd } else {
158 1.1 cgd b.compare = __bt_defcmp;
159 1.1 cgd b.cachesize = 0;
160 1.1 cgd b.flags = 0;
161 1.1 cgd b.lorder = machine_lorder;
162 1.1 cgd b.minkeypage = DEFMINKEYPAGE;
163 1.1 cgd b.prefix = __bt_defpfx;
164 1.1 cgd b.psize = 0;
165 1.1 cgd }
166 1.1 cgd
167 1.1 cgd /* Check for the ubiquitous PDP-11. */
168 1.1 cgd if (b.lorder != BIG_ENDIAN && b.lorder != LITTLE_ENDIAN)
169 1.1 cgd goto einval;
170 1.1 cgd
171 1.1 cgd /* Allocate and initialize DB and BTREE structures. */
172 1.6 cgd if ((t = (BTREE *)malloc(sizeof(BTREE))) == NULL)
173 1.1 cgd goto err;
174 1.5 cgd memset(t, 0, sizeof(BTREE));
175 1.1 cgd t->bt_fd = -1; /* Don't close unopened fd on error. */
176 1.1 cgd t->bt_lorder = b.lorder;
177 1.1 cgd t->bt_order = NOT;
178 1.1 cgd t->bt_cmp = b.compare;
179 1.1 cgd t->bt_pfx = b.prefix;
180 1.5 cgd t->bt_rfd = -1;
181 1.5 cgd
182 1.6 cgd if ((t->bt_dbp = dbp = (DB *)malloc(sizeof(DB))) == NULL)
183 1.5 cgd goto err;
184 1.8 cgd memset(t->bt_dbp, 0, sizeof(DB));
185 1.1 cgd if (t->bt_lorder != machine_lorder)
186 1.8 cgd F_SET(t, B_NEEDSWAP);
187 1.1 cgd
188 1.1 cgd dbp->type = DB_BTREE;
189 1.1 cgd dbp->internal = t;
190 1.1 cgd dbp->close = __bt_close;
191 1.1 cgd dbp->del = __bt_delete;
192 1.1 cgd dbp->fd = __bt_fd;
193 1.1 cgd dbp->get = __bt_get;
194 1.1 cgd dbp->put = __bt_put;
195 1.1 cgd dbp->seq = __bt_seq;
196 1.1 cgd dbp->sync = __bt_sync;
197 1.1 cgd
198 1.1 cgd /*
199 1.1 cgd * If no file name was supplied, this is an in-memory btree and we
200 1.1 cgd * open a backing temporary file. Otherwise, it's a disk-based tree.
201 1.1 cgd */
202 1.1 cgd if (fname) {
203 1.8 cgd switch (flags & O_ACCMODE) {
204 1.1 cgd case O_RDONLY:
205 1.8 cgd F_SET(t, B_RDONLY);
206 1.1 cgd break;
207 1.1 cgd case O_RDWR:
208 1.1 cgd break;
209 1.1 cgd case O_WRONLY:
210 1.1 cgd default:
211 1.1 cgd goto einval;
212 1.1 cgd }
213 1.1 cgd
214 1.4 cgd if ((t->bt_fd = open(fname, flags, mode)) < 0)
215 1.1 cgd goto err;
216 1.1 cgd
217 1.1 cgd } else {
218 1.1 cgd if ((flags & O_ACCMODE) != O_RDWR)
219 1.1 cgd goto einval;
220 1.1 cgd if ((t->bt_fd = tmp()) == -1)
221 1.1 cgd goto err;
222 1.8 cgd F_SET(t, B_INMEM);
223 1.1 cgd }
224 1.1 cgd
225 1.1 cgd if (fcntl(t->bt_fd, F_SETFD, 1) == -1)
226 1.1 cgd goto err;
227 1.1 cgd
228 1.1 cgd if (fstat(t->bt_fd, &sb))
229 1.1 cgd goto err;
230 1.1 cgd if (sb.st_size) {
231 1.6 cgd if ((nr = read(t->bt_fd, &m, sizeof(BTMETA))) < 0)
232 1.1 cgd goto err;
233 1.1 cgd if (nr != sizeof(BTMETA))
234 1.1 cgd goto eftype;
235 1.1 cgd
236 1.1 cgd /*
237 1.1 cgd * Read in the meta-data. This can change the notion of what
238 1.1 cgd * the lorder, page size and flags are, and, when the page size
239 1.1 cgd * changes, the cachesize value can change too. If the user
240 1.1 cgd * specified the wrong byte order for an existing database, we
241 1.1 cgd * don't bother to return an error, we just clear the NEEDSWAP
242 1.1 cgd * bit.
243 1.1 cgd */
244 1.8 cgd if (m.magic == BTREEMAGIC)
245 1.8 cgd F_CLR(t, B_NEEDSWAP);
246 1.1 cgd else {
247 1.8 cgd F_SET(t, B_NEEDSWAP);
248 1.8 cgd M_32_SWAP(m.magic);
249 1.8 cgd M_32_SWAP(m.version);
250 1.8 cgd M_32_SWAP(m.psize);
251 1.8 cgd M_32_SWAP(m.free);
252 1.8 cgd M_32_SWAP(m.nrecs);
253 1.8 cgd M_32_SWAP(m.flags);
254 1.1 cgd }
255 1.8 cgd if (m.magic != BTREEMAGIC || m.version != BTREEVERSION)
256 1.1 cgd goto eftype;
257 1.8 cgd if (m.psize < MINPSIZE || m.psize > MAX_PAGE_OFFSET + 1 ||
258 1.9 christos m.psize & (sizeof(indx_t) - 1))
259 1.1 cgd goto eftype;
260 1.8 cgd if (m.flags & ~SAVEMETA)
261 1.1 cgd goto eftype;
262 1.8 cgd b.psize = m.psize;
263 1.8 cgd F_SET(t, m.flags);
264 1.8 cgd t->bt_free = m.free;
265 1.8 cgd t->bt_nrecs = m.nrecs;
266 1.1 cgd } else {
267 1.1 cgd /*
268 1.1 cgd * Set the page size to the best value for I/O to this file.
269 1.1 cgd * Don't overflow the page offset type.
270 1.1 cgd */
271 1.1 cgd if (b.psize == 0) {
272 1.1 cgd b.psize = sb.st_blksize;
273 1.1 cgd if (b.psize < MINPSIZE)
274 1.1 cgd b.psize = MINPSIZE;
275 1.1 cgd if (b.psize > MAX_PAGE_OFFSET + 1)
276 1.1 cgd b.psize = MAX_PAGE_OFFSET + 1;
277 1.1 cgd }
278 1.1 cgd
279 1.1 cgd /* Set flag if duplicates permitted. */
280 1.1 cgd if (!(b.flags & R_DUP))
281 1.8 cgd F_SET(t, B_NODUPS);
282 1.1 cgd
283 1.1 cgd t->bt_free = P_INVALID;
284 1.1 cgd t->bt_nrecs = 0;
285 1.8 cgd F_SET(t, B_METADIRTY);
286 1.1 cgd }
287 1.1 cgd
288 1.1 cgd t->bt_psize = b.psize;
289 1.1 cgd
290 1.1 cgd /* Set the cache size; must be a multiple of the page size. */
291 1.9 christos if (b.cachesize && b.cachesize & (b.psize - 1))
292 1.9 christos b.cachesize += (~b.cachesize & (b.psize - 1)) + 1;
293 1.1 cgd if (b.cachesize < b.psize * MINCACHE)
294 1.1 cgd b.cachesize = b.psize * MINCACHE;
295 1.1 cgd
296 1.1 cgd /* Calculate number of pages to cache. */
297 1.1 cgd ncache = (b.cachesize + t->bt_psize - 1) / t->bt_psize;
298 1.1 cgd
299 1.1 cgd /*
300 1.1 cgd * The btree data structure requires that at least two keys can fit on
301 1.1 cgd * a page, but other than that there's no fixed requirement. The user
302 1.1 cgd * specified a minimum number per page, and we translated that into the
303 1.1 cgd * number of bytes a key/data pair can use before being placed on an
304 1.1 cgd * overflow page. This calculation includes the page header, the size
305 1.1 cgd * of the index referencing the leaf item and the size of the leaf item
306 1.1 cgd * structure. Also, don't let the user specify a minkeypage such that
307 1.1 cgd * a key/data pair won't fit even if both key and data are on overflow
308 1.1 cgd * pages.
309 1.1 cgd */
310 1.1 cgd t->bt_ovflsize = (t->bt_psize - BTDATAOFF) / b.minkeypage -
311 1.1 cgd (sizeof(indx_t) + NBLEAFDBT(0, 0));
312 1.1 cgd if (t->bt_ovflsize < NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t))
313 1.1 cgd t->bt_ovflsize =
314 1.1 cgd NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t);
315 1.1 cgd
316 1.1 cgd /* Initialize the buffer pool. */
317 1.1 cgd if ((t->bt_mp =
318 1.1 cgd mpool_open(NULL, t->bt_fd, t->bt_psize, ncache)) == NULL)
319 1.1 cgd goto err;
320 1.8 cgd if (!F_ISSET(t, B_INMEM))
321 1.1 cgd mpool_filter(t->bt_mp, __bt_pgin, __bt_pgout, t);
322 1.1 cgd
323 1.1 cgd /* Create a root page if new tree. */
324 1.1 cgd if (nroot(t) == RET_ERROR)
325 1.1 cgd goto err;
326 1.1 cgd
327 1.4 cgd /* Global flags. */
328 1.4 cgd if (dflags & DB_LOCK)
329 1.8 cgd F_SET(t, B_DB_LOCK);
330 1.4 cgd if (dflags & DB_SHMEM)
331 1.8 cgd F_SET(t, B_DB_SHMEM);
332 1.4 cgd if (dflags & DB_TXN)
333 1.8 cgd F_SET(t, B_DB_TXN);
334 1.4 cgd
335 1.1 cgd return (dbp);
336 1.1 cgd
337 1.1 cgd einval: errno = EINVAL;
338 1.1 cgd goto err;
339 1.1 cgd
340 1.1 cgd eftype: errno = EFTYPE;
341 1.1 cgd goto err;
342 1.1 cgd
343 1.1 cgd err: if (t) {
344 1.1 cgd if (t->bt_dbp)
345 1.1 cgd free(t->bt_dbp);
346 1.1 cgd if (t->bt_fd != -1)
347 1.1 cgd (void)close(t->bt_fd);
348 1.1 cgd free(t);
349 1.1 cgd }
350 1.1 cgd return (NULL);
351 1.1 cgd }
352 1.1 cgd
353 1.1 cgd /*
354 1.1 cgd * NROOT -- Create the root of a new tree.
355 1.1 cgd *
356 1.1 cgd * Parameters:
357 1.1 cgd * t: tree
358 1.1 cgd *
359 1.1 cgd * Returns:
360 1.1 cgd * RET_ERROR, RET_SUCCESS
361 1.1 cgd */
362 1.1 cgd static int
363 1.1 cgd nroot(t)
364 1.1 cgd BTREE *t;
365 1.1 cgd {
366 1.1 cgd PAGE *meta, *root;
367 1.1 cgd pgno_t npg;
368 1.1 cgd
369 1.1 cgd if ((meta = mpool_get(t->bt_mp, 0, 0)) != NULL) {
370 1.1 cgd mpool_put(t->bt_mp, meta, 0);
371 1.1 cgd return (RET_SUCCESS);
372 1.1 cgd }
373 1.6 cgd if (errno != EINVAL) /* It's OK to not exist. */
374 1.1 cgd return (RET_ERROR);
375 1.6 cgd errno = 0;
376 1.1 cgd
377 1.1 cgd if ((meta = mpool_new(t->bt_mp, &npg)) == NULL)
378 1.1 cgd return (RET_ERROR);
379 1.1 cgd
380 1.1 cgd if ((root = mpool_new(t->bt_mp, &npg)) == NULL)
381 1.1 cgd return (RET_ERROR);
382 1.1 cgd
383 1.1 cgd if (npg != P_ROOT)
384 1.1 cgd return (RET_ERROR);
385 1.1 cgd root->pgno = npg;
386 1.1 cgd root->prevpg = root->nextpg = P_INVALID;
387 1.1 cgd root->lower = BTDATAOFF;
388 1.1 cgd root->upper = t->bt_psize;
389 1.1 cgd root->flags = P_BLEAF;
390 1.1 cgd memset(meta, 0, t->bt_psize);
391 1.1 cgd mpool_put(t->bt_mp, meta, MPOOL_DIRTY);
392 1.1 cgd mpool_put(t->bt_mp, root, MPOOL_DIRTY);
393 1.1 cgd return (RET_SUCCESS);
394 1.1 cgd }
395 1.1 cgd
396 1.1 cgd static int
397 1.1 cgd tmp()
398 1.1 cgd {
399 1.1 cgd sigset_t set, oset;
400 1.16 thorpej size_t len;
401 1.16 thorpej int fd;
402 1.1 cgd char *envtmp;
403 1.14 thorpej char path[PATH_MAX];
404 1.1 cgd
405 1.15 groo if (issetugid())
406 1.15 groo envtmp = NULL;
407 1.15 groo else
408 1.15 groo envtmp = getenv("TMPDIR");
409 1.15 groo
410 1.15 groo len = snprintf(path,
411 1.11 fair sizeof(path), "%s/bt.XXXXXX", envtmp ? envtmp : _PATH_TMP);
412 1.15 groo if (len >= sizeof(path))
413 1.15 groo return -1;
414 1.15 groo
415 1.1 cgd (void)sigfillset(&set);
416 1.1 cgd (void)sigprocmask(SIG_BLOCK, &set, &oset);
417 1.1 cgd if ((fd = mkstemp(path)) != -1)
418 1.1 cgd (void)unlink(path);
419 1.1 cgd (void)sigprocmask(SIG_SETMASK, &oset, NULL);
420 1.1 cgd return(fd);
421 1.1 cgd }
422 1.1 cgd
423 1.1 cgd static int
424 1.1 cgd byteorder()
425 1.1 cgd {
426 1.6 cgd u_int32_t x;
427 1.1 cgd u_char *p;
428 1.1 cgd
429 1.1 cgd x = 0x01020304;
430 1.13 christos p = (u_char *)(void *)&x;
431 1.1 cgd switch (*p) {
432 1.1 cgd case 1:
433 1.1 cgd return (BIG_ENDIAN);
434 1.1 cgd case 4:
435 1.1 cgd return (LITTLE_ENDIAN);
436 1.1 cgd default:
437 1.1 cgd return (0);
438 1.1 cgd }
439 1.1 cgd }
440 1.1 cgd
441 1.1 cgd int
442 1.1 cgd __bt_fd(dbp)
443 1.1 cgd const DB *dbp;
444 1.1 cgd {
445 1.1 cgd BTREE *t;
446 1.1 cgd
447 1.1 cgd t = dbp->internal;
448 1.1 cgd
449 1.4 cgd /* Toss any page pinned across calls. */
450 1.4 cgd if (t->bt_pinned != NULL) {
451 1.4 cgd mpool_put(t->bt_mp, t->bt_pinned, 0);
452 1.4 cgd t->bt_pinned = NULL;
453 1.4 cgd }
454 1.4 cgd
455 1.4 cgd /* In-memory database can't have a file descriptor. */
456 1.8 cgd if (F_ISSET(t, B_INMEM)) {
457 1.1 cgd errno = ENOENT;
458 1.1 cgd return (-1);
459 1.1 cgd }
460 1.1 cgd return (t->bt_fd);
461 1.1 cgd }
462