GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libc/db/btree/bt_overflow.c Lines: 0 52 0.0 %
Date: 2017-11-13 Branches: 0 22 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: bt_overflow.c,v 1.11 2015/01/16 16:48:51 deraadt Exp $	*/
2
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
#include <stdio.h>
36
#include <stdlib.h>
37
#include <string.h>
38
39
#include <db.h>
40
#include "btree.h"
41
42
#define MINIMUM(a, b)	(((a) < (b)) ? (a) : (b))
43
44
/*
45
 * Big key/data code.
46
 *
47
 * Big key and data entries are stored on linked lists of pages.  The initial
48
 * reference is byte string stored with the key or data and is the page number
49
 * and size.  The actual record is stored in a chain of pages linked by the
50
 * nextpg field of the PAGE header.
51
 *
52
 * The first page of the chain has a special property.  If the record is used
53
 * by an internal page, it cannot be deleted and the P_PRESERVE bit will be set
54
 * in the header.
55
 *
56
 * XXX
57
 * A single DBT is written to each chain, so a lot of space on the last page
58
 * is wasted.  This is a fairly major bug for some data sets.
59
 */
60
61
/*
62
 * __OVFL_GET -- Get an overflow key/data item.
63
 *
64
 * Parameters:
65
 *	t:	tree
66
 *	p:	pointer to { pgno_t, u_int32_t }
67
 *	buf:	storage address
68
 *	bufsz:	storage size
69
 *
70
 * Returns:
71
 *	RET_ERROR, RET_SUCCESS
72
 */
73
int
74
__ovfl_get(BTREE *t, void *p, size_t *ssz, void **buf, size_t *bufsz)
75
{
76
	PAGE *h;
77
	pgno_t pg;
78
	size_t nb, plen;
79
	u_int32_t sz;
80
	void *tp;
81
82
	memmove(&pg, p, sizeof(pgno_t));
83
	memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
84
	*ssz = sz;
85
86
#ifdef DEBUG
87
	if (pg == P_INVALID || sz == 0)
88
		abort();
89
#endif
90
	/* Make the buffer bigger as necessary. */
91
	if (*bufsz < sz) {
92
		tp = realloc(*buf, sz);
93
		if (tp == NULL)
94
			return (RET_ERROR);
95
		*buf = tp;
96
		*bufsz = sz;
97
	}
98
99
	/*
100
	 * Step through the linked list of pages, copying the data on each one
101
	 * into the buffer.  Never copy more than the data's length.
102
	 */
103
	plen = t->bt_psize - BTDATAOFF;
104
	for (p = *buf;; p = (char *)p + nb, pg = h->nextpg) {
105
		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
106
			return (RET_ERROR);
107
108
		nb = MINIMUM(sz, plen);
109
		memmove(p, (char *)h + BTDATAOFF, nb);
110
		mpool_put(t->bt_mp, h, 0);
111
112
		if ((sz -= nb) == 0)
113
			break;
114
	}
115
	return (RET_SUCCESS);
116
}
117
118
/*
119
 * __OVFL_PUT -- Store an overflow key/data item.
120
 *
121
 * Parameters:
122
 *	t:	tree
123
 *	data:	DBT to store
124
 *	pgno:	storage page number
125
 *
126
 * Returns:
127
 *	RET_ERROR, RET_SUCCESS
128
 */
129
int
130
__ovfl_put(BTREE *t, const DBT *dbt, pgno_t *pg)
131
{
132
	PAGE *h, *last;
133
	void *p;
134
	pgno_t npg;
135
	size_t nb, plen;
136
	u_int32_t sz;
137
138
	/*
139
	 * Allocate pages and copy the key/data record into them.  Store the
140
	 * number of the first page in the chain.
141
	 */
142
	plen = t->bt_psize - BTDATAOFF;
143
	for (last = NULL, p = dbt->data, sz = dbt->size;;
144
	    p = (char *)p + plen, last = h) {
145
		if ((h = __bt_new(t, &npg)) == NULL)
146
			return (RET_ERROR);
147
148
		h->pgno = npg;
149
		h->nextpg = h->prevpg = P_INVALID;
150
		h->flags = P_OVERFLOW;
151
		h->lower = h->upper = 0;
152
153
		nb = MINIMUM(sz, plen);
154
		memmove((char *)h + BTDATAOFF, p, nb);
155
156
		if (last) {
157
			last->nextpg = h->pgno;
158
			mpool_put(t->bt_mp, last, MPOOL_DIRTY);
159
		} else
160
			*pg = h->pgno;
161
162
		if ((sz -= nb) == 0) {
163
			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
164
			break;
165
		}
166
	}
167
	return (RET_SUCCESS);
168
}
169
170
/*
171
 * __OVFL_DELETE -- Delete an overflow chain.
172
 *
173
 * Parameters:
174
 *	t:	tree
175
 *	p:	pointer to { pgno_t, u_int32_t }
176
 *
177
 * Returns:
178
 *	RET_ERROR, RET_SUCCESS
179
 */
180
int
181
__ovfl_delete(BTREE *t, void *p)
182
{
183
	PAGE *h;
184
	pgno_t pg;
185
	size_t plen;
186
	u_int32_t sz;
187
188
	memmove(&pg, p, sizeof(pgno_t));
189
	memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
190
191
#ifdef DEBUG
192
	if (pg == P_INVALID || sz == 0)
193
		abort();
194
#endif
195
	if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
196
		return (RET_ERROR);
197
198
	/* Don't delete chains used by internal pages. */
199
	if (h->flags & P_PRESERVE) {
200
		mpool_put(t->bt_mp, h, 0);
201
		return (RET_SUCCESS);
202
	}
203
204
	/* Step through the chain, calling the free routine for each page. */
205
	for (plen = t->bt_psize - BTDATAOFF;; sz -= plen) {
206
		pg = h->nextpg;
207
		__bt_free(t, h);
208
		if (sz <= plen)
209
			break;
210
		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
211
			return (RET_ERROR);
212
	}
213
	return (RET_SUCCESS);
214
}