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