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