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