GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libc/db/hash/hash_bigkey.c Lines: 0 277 0.0 %
Date: 2017-11-13 Branches: 0 140 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: hash_bigkey.c,v 1.19 2015/12/28 22:08:18 mmcc 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
 * Margo Seltzer.
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
/*
36
 * PACKAGE: hash
37
 * DESCRIPTION:
38
 *	Big key/data handling for the hashing package.
39
 *
40
 * ROUTINES:
41
 * External
42
 *	__big_keydata
43
 *	__big_split
44
 *	__big_insert
45
 *	__big_return
46
 *	__big_delete
47
 *	__find_last_page
48
 * Internal
49
 *	collect_key
50
 *	collect_data
51
 */
52
53
#include <errno.h>
54
#include <stdio.h>
55
#include <stdlib.h>
56
#include <string.h>
57
58
#ifdef DEBUG
59
#include <assert.h>
60
#endif
61
62
#include <db.h>
63
#include "hash.h"
64
#include "page.h"
65
#include "extern.h"
66
67
#define MINIMUM(a, b)	(((a) < (b)) ? (a) : (b))
68
69
static int collect_key(HTAB *, BUFHEAD *, int, DBT *, int);
70
static int collect_data(HTAB *, BUFHEAD *, int, int);
71
72
/*
73
 * Big_insert
74
 *
75
 * You need to do an insert and the key/data pair is too big
76
 *
77
 * Returns:
78
 * 0 ==> OK
79
 *-1 ==> ERROR
80
 */
81
int
82
__big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val)
83
{
84
	u_int16_t *p;
85
	int key_size, n, val_size;
86
	u_int16_t space, move_bytes, off;
87
	char *cp, *key_data, *val_data;
88
89
	cp = bufp->page;		/* Character pointer of p. */
90
	p = (u_int16_t *)cp;
91
92
	key_data = (char *)key->data;
93
	key_size = key->size;
94
	val_data = (char *)val->data;
95
	val_size = val->size;
96
97
	/* First move the Key */
98
	for (space = FREESPACE(p) - BIGOVERHEAD; key_size;
99
	    space = FREESPACE(p) - BIGOVERHEAD) {
100
		move_bytes = MINIMUM(space, key_size);
101
		off = OFFSET(p) - move_bytes;
102
		memmove(cp + off, key_data, move_bytes);
103
		key_size -= move_bytes;
104
		key_data += move_bytes;
105
		n = p[0];
106
		p[++n] = off;
107
		p[0] = ++n;
108
		FREESPACE(p) = off - PAGE_META(n);
109
		OFFSET(p) = off;
110
		p[n] = PARTIAL_KEY;
111
		bufp = __add_ovflpage(hashp, bufp);
112
		if (!bufp)
113
			return (-1);
114
		n = p[0];
115
		if (!key_size) {
116
			space = FREESPACE(p);
117
			if (space) {
118
				move_bytes = MINIMUM(space, val_size);
119
				/*
120
				 * If the data would fit exactly in the
121
				 * remaining space, we must overflow it to the
122
				 * next page; otherwise the invariant that the
123
				 * data must end on a page with FREESPACE
124
				 * non-zero would fail.
125
				 */
126
				if (space == val_size && val_size == val->size)
127
					goto toolarge;
128
				off = OFFSET(p) - move_bytes;
129
				memmove(cp + off, val_data, move_bytes);
130
				val_data += move_bytes;
131
				val_size -= move_bytes;
132
				p[n] = off;
133
				p[n - 2] = FULL_KEY_DATA;
134
				FREESPACE(p) = FREESPACE(p) - move_bytes;
135
				OFFSET(p) = off;
136
			} else {
137
			toolarge:
138
				p[n - 2] = FULL_KEY;
139
			}
140
		}
141
		p = (u_int16_t *)bufp->page;
142
		cp = bufp->page;
143
		bufp->flags |= BUF_MOD;
144
	}
145
146
	/* Now move the data */
147
	for (space = FREESPACE(p) - BIGOVERHEAD; val_size;
148
	    space = FREESPACE(p) - BIGOVERHEAD) {
149
		move_bytes = MINIMUM(space, val_size);
150
		/*
151
		 * Here's the hack to make sure that if the data ends on the
152
		 * same page as the key ends, FREESPACE is at least one.
153
		 */
154
		if (space == val_size && val_size == val->size)
155
			move_bytes--;
156
		off = OFFSET(p) - move_bytes;
157
		memmove(cp + off, val_data, move_bytes);
158
		val_size -= move_bytes;
159
		val_data += move_bytes;
160
		n = p[0];
161
		p[++n] = off;
162
		p[0] = ++n;
163
		FREESPACE(p) = off - PAGE_META(n);
164
		OFFSET(p) = off;
165
		if (val_size) {
166
			p[n] = FULL_KEY;
167
			bufp = __add_ovflpage(hashp, bufp);
168
			if (!bufp)
169
				return (-1);
170
			cp = bufp->page;
171
			p = (u_int16_t *)cp;
172
		} else
173
			p[n] = FULL_KEY_DATA;
174
		bufp->flags |= BUF_MOD;
175
	}
176
	return (0);
177
}
178
179
/*
180
 * Called when bufp's page  contains a partial key (index should be 1)
181
 *
182
 * All pages in the big key/data pair except bufp are freed.  We cannot
183
 * free bufp because the page pointing to it is lost and we can't get rid
184
 * of its pointer.
185
 *
186
 * Returns:
187
 * 0 => OK
188
 *-1 => ERROR
189
 */
190
int
191
__big_delete(HTAB *hashp, BUFHEAD *bufp)
192
{
193
	BUFHEAD *last_bfp, *rbufp;
194
	u_int16_t *bp, pageno;
195
	int key_done, n;
196
197
	rbufp = bufp;
198
	last_bfp = NULL;
199
	bp = (u_int16_t *)bufp->page;
200
	pageno = 0;
201
	key_done = 0;
202
203
	while (!key_done || (bp[2] != FULL_KEY_DATA)) {
204
		if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
205
			key_done = 1;
206
207
		/*
208
		 * If there is freespace left on a FULL_KEY_DATA page, then
209
		 * the data is short and fits entirely on this page, and this
210
		 * is the last page.
211
		 */
212
		if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
213
			break;
214
		pageno = bp[bp[0] - 1];
215
		rbufp->flags |= BUF_MOD;
216
		rbufp = __get_buf(hashp, pageno, rbufp, 0);
217
		if (last_bfp)
218
			__free_ovflpage(hashp, last_bfp);
219
		last_bfp = rbufp;
220
		if (!rbufp)
221
			return (-1);		/* Error. */
222
		bp = (u_int16_t *)rbufp->page;
223
	}
224
225
	/*
226
	 * If we get here then rbufp points to the last page of the big
227
	 * key/data pair.  Bufp points to the first one -- it should now be
228
	 * empty pointing to the next page after this pair.  Can't free it
229
	 * because we don't have the page pointing to it.
230
	 */
231
232
	/* This is information from the last page of the pair. */
233
	n = bp[0];
234
	pageno = bp[n - 1];
235
236
	/* Now, bp is the first page of the pair. */
237
	bp = (u_int16_t *)bufp->page;
238
	if (n > 2) {
239
		/* There is an overflow page. */
240
		bp[1] = pageno;
241
		bp[2] = OVFLPAGE;
242
		bufp->ovfl = rbufp->ovfl;
243
	} else
244
		/* This is the last page. */
245
		bufp->ovfl = NULL;
246
	n -= 2;
247
	bp[0] = n;
248
	FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
249
	OFFSET(bp) = hashp->BSIZE;
250
251
	bufp->flags |= BUF_MOD;
252
	if (rbufp)
253
		__free_ovflpage(hashp, rbufp);
254
	if (last_bfp && last_bfp != rbufp)
255
		__free_ovflpage(hashp, last_bfp);
256
257
	hashp->NKEYS--;
258
	return (0);
259
}
260
/*
261
 * Returns:
262
 *  0 = key not found
263
 * -1 = get next overflow page
264
 * -2 means key not found and this is big key/data
265
 * -3 error
266
 */
267
int
268
__find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size)
269
{
270
	u_int16_t *bp;
271
	char *p;
272
	int ksize;
273
	u_int16_t bytes;
274
	char *kkey;
275
276
	bp = (u_int16_t *)bufp->page;
277
	p = bufp->page;
278
	ksize = size;
279
	kkey = key;
280
281
	for (bytes = hashp->BSIZE - bp[ndx];
282
	    bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
283
	    bytes = hashp->BSIZE - bp[ndx]) {
284
		if (memcmp(p + bp[ndx], kkey, bytes))
285
			return (-2);
286
		kkey += bytes;
287
		ksize -= bytes;
288
		bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);
289
		if (!bufp)
290
			return (-3);
291
		p = bufp->page;
292
		bp = (u_int16_t *)p;
293
		ndx = 1;
294
	}
295
296
	if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {
297
#ifdef HASH_STATISTICS
298
		++hash_collisions;
299
#endif
300
		return (-2);
301
	} else
302
		return (ndx);
303
}
304
305
/*
306
 * Given the buffer pointer of the first overflow page of a big pair,
307
 * find the end of the big pair
308
 *
309
 * This will set bpp to the buffer header of the last page of the big pair.
310
 * It will return the pageno of the overflow page following the last page
311
 * of the pair; 0 if there isn't any (i.e. big pair is the last key in the
312
 * bucket)
313
 */
314
u_int16_t
315
__find_last_page(HTAB *hashp, BUFHEAD **bpp)
316
{
317
	BUFHEAD *bufp;
318
	u_int16_t *bp, pageno;
319
	int n;
320
321
	bufp = *bpp;
322
	bp = (u_int16_t *)bufp->page;
323
	for (;;) {
324
		n = bp[0];
325
326
		/*
327
		 * This is the last page if: the tag is FULL_KEY_DATA and
328
		 * either only 2 entries OVFLPAGE marker is explicit there
329
		 * is freespace on the page.
330
		 */
331
		if (bp[2] == FULL_KEY_DATA &&
332
		    ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
333
			break;
334
335
		pageno = bp[n - 1];
336
		bufp = __get_buf(hashp, pageno, bufp, 0);
337
		if (!bufp)
338
			return (0);	/* Need to indicate an error! */
339
		bp = (u_int16_t *)bufp->page;
340
	}
341
342
	*bpp = bufp;
343
	if (bp[0] > 2)
344
		return (bp[3]);
345
	else
346
		return (0);
347
}
348
349
/*
350
 * Return the data for the key/data pair that begins on this page at this
351
 * index (index should always be 1).
352
 */
353
int
354
__big_return(HTAB *hashp, BUFHEAD *bufp, int ndx, DBT *val, int set_current)
355
{
356
	BUFHEAD *save_p;
357
	u_int16_t *bp, len, off, save_addr;
358
	char *tp;
359
360
	bp = (u_int16_t *)bufp->page;
361
	while (bp[ndx + 1] == PARTIAL_KEY) {
362
		bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
363
		if (!bufp)
364
			return (-1);
365
		bp = (u_int16_t *)bufp->page;
366
		ndx = 1;
367
	}
368
369
	if (bp[ndx + 1] == FULL_KEY) {
370
		bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
371
		if (!bufp)
372
			return (-1);
373
		bp = (u_int16_t *)bufp->page;
374
		save_p = bufp;
375
		save_addr = save_p->addr;
376
		off = bp[1];
377
		len = 0;
378
	} else
379
		if (!FREESPACE(bp)) {
380
			/*
381
			 * This is a hack.  We can't distinguish between
382
			 * FULL_KEY_DATA that contains complete data or
383
			 * incomplete data, so we require that if the data
384
			 * is complete, there is at least 1 byte of free
385
			 * space left.
386
			 */
387
			off = bp[bp[0]];
388
			len = bp[1] - off;
389
			save_p = bufp;
390
			save_addr = bufp->addr;
391
			bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
392
			if (!bufp)
393
				return (-1);
394
			bp = (u_int16_t *)bufp->page;
395
		} else {
396
			/* The data is all on one page. */
397
			tp = (char *)bp;
398
			off = bp[bp[0]];
399
			val->data = (u_char *)tp + off;
400
			val->size = bp[1] - off;
401
			if (set_current) {
402
				if (bp[0] == 2) {	/* No more buckets in
403
							 * chain */
404
					hashp->cpage = NULL;
405
					hashp->cbucket++;
406
					hashp->cndx = 1;
407
				} else {
408
					hashp->cpage = __get_buf(hashp,
409
					    bp[bp[0] - 1], bufp, 0);
410
					if (!hashp->cpage)
411
						return (-1);
412
					hashp->cndx = 1;
413
					if (!((u_int16_t *)
414
					    hashp->cpage->page)[0]) {
415
						hashp->cbucket++;
416
						hashp->cpage = NULL;
417
					}
418
				}
419
			}
420
			return (0);
421
		}
422
423
	val->size = (size_t)collect_data(hashp, bufp, (int)len, set_current);
424
	if (val->size == (size_t)-1)
425
		return (-1);
426
	if (save_p->addr != save_addr) {
427
		/* We are pretty short on buffers. */
428
		errno = EINVAL;			/* OUT OF BUFFERS */
429
		return (-1);
430
	}
431
	memmove(hashp->tmp_buf, (save_p->page) + off, len);
432
	val->data = (u_char *)hashp->tmp_buf;
433
	return (0);
434
}
435
/*
436
 * Count how big the total datasize is by recursing through the pages.  Then
437
 * allocate a buffer and copy the data as you recurse up.
438
 */
439
static int
440
collect_data(HTAB *hashp, BUFHEAD *bufp, int len, int set)
441
{
442
	u_int16_t *bp;
443
	char *p;
444
	BUFHEAD *xbp;
445
	u_int16_t save_addr;
446
	int mylen, totlen;
447
448
	p = bufp->page;
449
	bp = (u_int16_t *)p;
450
	mylen = hashp->BSIZE - bp[1];
451
	save_addr = bufp->addr;
452
453
	if (bp[2] == FULL_KEY_DATA) {		/* End of Data */
454
		totlen = len + mylen;
455
		free(hashp->tmp_buf);
456
		if ((hashp->tmp_buf = (char *)malloc(totlen)) == NULL)
457
			return (-1);
458
		if (set) {
459
			hashp->cndx = 1;
460
			if (bp[0] == 2) {	/* No more buckets in chain */
461
				hashp->cpage = NULL;
462
				hashp->cbucket++;
463
			} else {
464
				hashp->cpage =
465
				    __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
466
				if (!hashp->cpage)
467
					return (-1);
468
				else if (!((u_int16_t *)hashp->cpage->page)[0]) {
469
					hashp->cbucket++;
470
					hashp->cpage = NULL;
471
				}
472
			}
473
		}
474
	} else {
475
		xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
476
		if (!xbp || ((totlen =
477
		    collect_data(hashp, xbp, len + mylen, set)) < 1))
478
			return (-1);
479
	}
480
	if (bufp->addr != save_addr) {
481
		errno = EINVAL;			/* Out of buffers. */
482
		return (-1);
483
	}
484
	memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen);
485
	return (totlen);
486
}
487
488
/*
489
 * Fill in the key and data for this big pair.
490
 */
491
int
492
__big_keydata(HTAB *hashp, BUFHEAD *bufp, DBT *key, DBT *val, int set)
493
{
494
	key->size = (size_t)collect_key(hashp, bufp, 0, val, set);
495
	if (key->size == (size_t)-1)
496
		return (-1);
497
	key->data = (u_char *)hashp->tmp_key;
498
	return (0);
499
}
500
501
/*
502
 * Count how big the total key size is by recursing through the pages.  Then
503
 * collect the data, allocate a buffer and copy the key as you recurse up.
504
 */
505
static int
506
collect_key(HTAB *hashp, BUFHEAD *bufp, int len, DBT *val, int set)
507
{
508
	BUFHEAD *xbp;
509
	char *p;
510
	int mylen, totlen;
511
	u_int16_t *bp, save_addr;
512
513
	p = bufp->page;
514
	bp = (u_int16_t *)p;
515
	mylen = hashp->BSIZE - bp[1];
516
517
	save_addr = bufp->addr;
518
	totlen = len + mylen;
519
	if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) {    /* End of Key. */
520
		free(hashp->tmp_key);
521
		if ((hashp->tmp_key = (char *)malloc(totlen)) == NULL)
522
			return (-1);
523
		if (__big_return(hashp, bufp, 1, val, set))
524
			return (-1);
525
	} else {
526
		xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
527
		if (!xbp || ((totlen =
528
		    collect_key(hashp, xbp, totlen, val, set)) < 1))
529
			return (-1);
530
	}
531
	if (bufp->addr != save_addr) {
532
		errno = EINVAL;		/* MIS -- OUT OF BUFFERS */
533
		return (-1);
534
	}
535
	memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen);
536
	return (totlen);
537
}
538
539
/*
540
 * Returns:
541
 *  0 => OK
542
 * -1 => error
543
 */
544
int
545
__big_split(HTAB *hashp,
546
    BUFHEAD *op,	/* Pointer to where to put keys that go in old bucket */
547
    BUFHEAD *np,	/* Pointer to new bucket page */
548
    BUFHEAD *big_keyp,	/* Pointer to first page containing the big key/data */
549
    int addr,		/* Address of big_keyp */
550
    u_int32_t obucket,	/* Old Bucket */
551
    SPLIT_RETURN *ret)
552
{
553
	BUFHEAD *bp, *tmpp;
554
	DBT key, val;
555
	u_int32_t change;
556
	u_int16_t free_space, n, off, *tp;
557
558
	bp = big_keyp;
559
560
	/* Now figure out where the big key/data goes */
561
	if (__big_keydata(hashp, big_keyp, &key, &val, 0))
562
		return (-1);
563
	change = (__call_hash(hashp, key.data, key.size) != obucket);
564
565
	if ((ret->next_addr = __find_last_page(hashp, &big_keyp))) {
566
		if (!(ret->nextp =
567
		    __get_buf(hashp, ret->next_addr, big_keyp, 0)))
568
			return (-1);
569
	} else
570
		ret->nextp = NULL;
571
572
	/* Now make one of np/op point to the big key/data pair */
573
#ifdef DEBUG
574
	assert(np->ovfl == NULL);
575
#endif
576
	if (change)
577
		tmpp = np;
578
	else
579
		tmpp = op;
580
581
	tmpp->flags |= BUF_MOD;
582
#ifdef DEBUG1
583
	(void)fprintf(stderr,
584
	    "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
585
	    (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
586
#endif
587
	tmpp->ovfl = bp;	/* one of op/np point to big_keyp */
588
	tp = (u_int16_t *)tmpp->page;
589
#ifdef DEBUG
590
	assert(FREESPACE(tp) >= OVFLSIZE);
591
#endif
592
	n = tp[0];
593
	off = OFFSET(tp);
594
	free_space = FREESPACE(tp);
595
	tp[++n] = (u_int16_t)addr;
596
	tp[++n] = OVFLPAGE;
597
	tp[0] = n;
598
	OFFSET(tp) = off;
599
	FREESPACE(tp) = free_space - OVFLSIZE;
600
601
	/*
602
	 * Finally, set the new and old return values. BIG_KEYP contains a
603
	 * pointer to the last page of the big key_data pair. Make sure that
604
	 * big_keyp has no following page (2 elements) or create an empty
605
	 * following page.
606
	 */
607
608
	ret->newp = np;
609
	ret->oldp = op;
610
611
	tp = (u_int16_t *)big_keyp->page;
612
	big_keyp->flags |= BUF_MOD;
613
	if (tp[0] > 2) {
614
		/*
615
		 * There may be either one or two offsets on this page.  If
616
		 * there is one, then the overflow page is linked on normally
617
		 * and tp[4] is OVFLPAGE.  If there are two, tp[4] contains
618
		 * the second offset and needs to get stuffed in after the
619
		 * next overflow page is added.
620
		 */
621
		n = tp[4];
622
		free_space = FREESPACE(tp);
623
		off = OFFSET(tp);
624
		tp[0] -= 2;
625
		FREESPACE(tp) = free_space + OVFLSIZE;
626
		OFFSET(tp) = off;
627
		tmpp = __add_ovflpage(hashp, big_keyp);
628
		if (!tmpp)
629
			return (-1);
630
		tp[4] = n;
631
	} else
632
		tmpp = big_keyp;
633
634
	if (change)
635
		ret->newp = tmpp;
636
	else
637
		ret->oldp = tmpp;
638
	return (0);
639
}