aboutsummaryrefslogtreecommitdiff
path: root/db2/common/db_salloc.c
blob: c02d7e18e92b666e7b8239c0c710dbdadd2f27ae (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
/*-
 * See the file LICENSE for redistribution information.
 *
 * Copyright (c) 1996, 1997, 1998
 *	Sleepycat Software.  All rights reserved.
 */

#include "config.h"

#ifndef lint
static const char sccsid[] = "@(#)db_salloc.c	10.13 (Sleepycat) 5/10/98";
#endif /* not lint */

#ifndef NO_SYSTEM_INCLUDES
#include <sys/types.h>

#include <errno.h>
#include <string.h>
#endif

#include "db_int.h"
#include "shqueue.h"
#include "common_ext.h"

/*
 * Implement shared memory region allocation, using simple first-fit algorithm.
 * The model is that we take a "chunk" of shared memory store and begin carving
 * it up into areas, similarly to how malloc works.  We do coalescing on free.
 *
 * The "len" field in the __data struct contains the length of the free region
 * (less the size_t bytes that holds the length).  We use the address provided
 * by the caller to find this length, which allows us to free a chunk without
 * requiring that the caller pass in the length of the chunk they're freeing.
 */
SH_LIST_HEAD(__head);
struct __data {
	size_t len;
	SH_LIST_ENTRY links;
};

/*
 * __db_shalloc_init --
 *	Initialize the area as one large chunk.
 *
 * PUBLIC: void __db_shalloc_init __P((void *, size_t));
 */
void
__db_shalloc_init(area, size)
	void *area;
	size_t size;
{
	struct __data *elp;
	struct __head *hp;

	hp = area;
	SH_LIST_INIT(hp);

	elp = (struct __data *)(hp + 1);
	elp->len = size - sizeof(struct __head) - sizeof(elp->len);
	SH_LIST_INSERT_HEAD(hp, elp, links, __data);
}

/*
 * __db_shalloc --
 *	Allocate some space from the shared region.
 *
 * PUBLIC: int __db_shalloc __P((void *, size_t, size_t, void *));
 */
int
__db_shalloc(p, len, align, retp)
	void *p, *retp;
	size_t len, align;
{
	struct __data *elp;
	size_t *sp;
	void *rp;

	/*
	 * We never allocate less than the size of a struct __data, align
	 * to less than a size_t boundary, or align to something that's not
	 * a multiple of a size_t.
	 */
	if (len < sizeof(struct __data))
		len = sizeof(struct __data);
	align = align <= sizeof(size_t) ?
	    sizeof(size_t) : ALIGN(align, sizeof(size_t));

	/* Walk the list, looking for a slot. */
	for (elp = SH_LIST_FIRST((struct __head *)p, __data);
	    elp != NULL;
	    elp = SH_LIST_NEXT(elp, links, __data)) {
		/*
		 * Calculate the value of the returned pointer if we were to
		 * use this chunk.
		 *	+ Find the end of the chunk.
		 *	+ Subtract the memory the user wants.
		 *	+ Find the closest previous correctly-aligned address.
		 */
		rp = (u_int8_t *)elp + sizeof(size_t) + elp->len;
		rp = (u_int8_t *)rp - len;
		rp = (u_int8_t *)((ALIGNTYPE)rp & ~(align - 1));

		/*
		 * Rp may now point before elp->links, in which case the chunk
		 * was too small, and we have to try again.
		 */
		if ((u_int8_t *)rp < (u_int8_t *)&elp->links)
			continue;

		*(void **)retp = rp;

#define	SHALLOC_FRAGMENT	32
		/*
		 * If there are at least SHALLOC_FRAGMENT additional bytes of
		 * memory, divide the chunk into two chunks.
		 */
		if ((u_int8_t *)rp >=
		    (u_int8_t *)&elp->links + SHALLOC_FRAGMENT) {
			sp = rp;
			*--sp = elp->len -
			    ((u_int8_t *)rp - (u_int8_t *)&elp->links);
			elp->len -= *sp + sizeof(size_t);
			return (0);
		}

		/*
		 * Otherwise, we return the entire chunk, wasting some amount
		 * of space to keep the list compact.  However, because the
		 * address we're returning to the user may not be the address
		 * of the start of the region for alignment reasons, set the
		 * size_t length fields back to the "real" length field to a
		 * flag value, so that we can find the real length during free.
		 */
#define	ILLEGAL_SIZE	1
		SH_LIST_REMOVE(elp, links, __data);
		for (sp = rp; (u_int8_t *)--sp >= (u_int8_t *)&elp->links;)
			*sp = ILLEGAL_SIZE;
		return (0);
	}

	/* Nothing found large enough; need to grow the region. */
	return (ENOMEM);
}

/*
 * __db_shalloc_free --
 *	Free a shared memory allocation.
 *
 * PUBLIC: void __db_shalloc_free __P((void *, void *));
 */
void
__db_shalloc_free(regionp, ptr)
	void *regionp, *ptr;
{
	struct __data *elp, *lastp, *newp;
	struct __head *hp;
	size_t free_size, *sp;
	int merged;

	/*
	 * Step back over flagged length fields to find the beginning of
	 * the object and its real size.
	 */
	for (sp = (size_t *)ptr; sp[-1] == ILLEGAL_SIZE; --sp)
		;
	ptr = sp;

	newp = (struct __data *)((u_int8_t *)ptr - sizeof(size_t));
	free_size = newp->len;

	/* Trash the returned memory. */
#ifdef DIAGNOSTIC
	memset(ptr, 0xff, free_size);
#endif

	/*
	 * Walk the list, looking for where this entry goes.
	 *
	 * We keep the free list sorted by address so that coalescing is
	 * trivial.
	 *
	 * XXX
	 * Probably worth profiling this to see how expensive it is.
	 */
	hp = (struct __head *)regionp;
	for (elp = SH_LIST_FIRST(hp, __data), lastp = NULL;
	    elp != NULL && (void *)elp < (void *)ptr;
	    lastp = elp, elp = SH_LIST_NEXT(elp, links, __data))
		;

	/*
	 * Elp is either NULL (we reached the end of the list), or the slot
	 * after the one that's being returned.  Lastp is either NULL (we're
	 * returning the first element of the list) or the element before the
	 * one being returned.
	 *
	 * Check for coalescing with the next element.
	 */
	merged = 0;
	if ((u_int8_t *)ptr + free_size == (u_int8_t *)elp) {
		newp->len += elp->len + sizeof(size_t);
		SH_LIST_REMOVE(elp, links, __data);
		if (lastp != NULL)
			SH_LIST_INSERT_AFTER(lastp, newp, links, __data);
		else
			SH_LIST_INSERT_HEAD(hp, newp, links, __data);
		merged = 1;
	}

	/* Check for coalescing with the previous element. */
	if (lastp != NULL && (u_int8_t *)lastp +
	    lastp->len + sizeof(size_t) == (u_int8_t *)newp) {
		lastp->len += newp->len + sizeof(size_t);

		/*
		 * If we have already put the new element into the list take
		 * it back off again because it's just been merged with the
		 * previous element.
		 */
		if (merged)
			SH_LIST_REMOVE(newp, links, __data);
		merged = 1;
	}

	if (!merged) {
		if (lastp == NULL)
			SH_LIST_INSERT_HEAD(hp, newp, links, __data);
		else
			SH_LIST_INSERT_AFTER(lastp, newp, links, __data);
	}
}

/*
 * __db_shalloc_count --
 *	Return the amount of memory on the free list.
 *
 * PUBLIC: size_t __db_shalloc_count __P((void *));
 */
size_t
__db_shalloc_count(addr)
	void *addr;
{
	struct __data *elp;
	size_t count;

	count = 0;
	for (elp = SH_LIST_FIRST((struct __head *)addr, __data);
	    elp != NULL;
	    elp = SH_LIST_NEXT(elp, links, __data))
		count += elp->len;

	return (count);
}

/*
 * __db_shsizeof --
 *	Return the size of a shalloc'd piece of memory.
 *
 * PUBLIC: size_t __db_shsizeof __P((void *));
 */
size_t
__db_shsizeof(ptr)
	void *ptr;
{
	struct __data *elp;
	size_t *sp;

	/*
	 * Step back over flagged length fields to find the beginning of
	 * the object and its real size.
	 */
	for (sp = (size_t *)ptr; sp[-1] == ILLEGAL_SIZE; --sp)
		;

	elp = (struct __data *)((u_int8_t *)sp - sizeof(size_t));
	return (elp->len);
}

/*
 * __db_shalloc_dump --
 *
 * PUBLIC: void __db_shalloc_dump __P((void *, FILE *));
 */
void
__db_shalloc_dump(addr, fp)
	void *addr;
	FILE *fp;
{
	struct __data *elp;

	/* Make it easy to call from the debugger. */
	if (fp == NULL)
		fp = stderr;

	fprintf(fp, "%s\nMemory free list\n", DB_LINE);

	for (elp = SH_LIST_FIRST((struct __head *)addr, __data);
	    elp != NULL;
	    elp = SH_LIST_NEXT(elp, links, __data))
		fprintf(fp, "%#lx: %lu\t", (u_long)elp, (u_long)elp->len);
	fprintf(fp, "\n");
}