xref: /illumos-gate/usr/src/cmd/sendmail/db/db/db_salloc.c (revision 7c478bd9)
1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 1996, 1997, 1998
5  *	Sleepycat Software.  All rights reserved.
6  */
7 
8 #include "config.h"
9 
10 #ifndef lint
11 static const char sccsid[] = "@(#)db_salloc.c	10.14 (Sleepycat) 11/16/98";
12 #endif /* not lint */
13 
14 #ifndef NO_SYSTEM_INCLUDES
15 #include <sys/types.h>
16 
17 #include <errno.h>
18 #include <string.h>
19 #endif
20 
21 #include "db_int.h"
22 #include "shqueue.h"
23 #include "common_ext.h"
24 
25 /*
26  * Implement shared memory region allocation, using simple first-fit algorithm.
27  * The model is that we take a "chunk" of shared memory store and begin carving
28  * it up into areas, similarly to how malloc works.  We do coalescing on free.
29  *
30  * The "len" field in the __data struct contains the length of the free region
31  * (less the size_t bytes that holds the length).  We use the address provided
32  * by the caller to find this length, which allows us to free a chunk without
33  * requiring that the caller pass in the length of the chunk they're freeing.
34  */
35 SH_LIST_HEAD(__head);
36 struct __data {
37 	size_t len;
38 	SH_LIST_ENTRY links;
39 };
40 
41 /*
42  * __db_shalloc_init --
43  *	Initialize the area as one large chunk.
44  *
45  * PUBLIC: void __db_shalloc_init __P((void *, size_t));
46  */
47 void
__db_shalloc_init(area,size)48 __db_shalloc_init(area, size)
49 	void *area;
50 	size_t size;
51 {
52 	struct __data *elp;
53 	struct __head *hp;
54 
55 	hp = area;
56 	SH_LIST_INIT(hp);
57 
58 	elp = (struct __data *)(hp + 1);
59 	elp->len = size - sizeof(struct __head) - sizeof(elp->len);
60 	SH_LIST_INSERT_HEAD(hp, elp, links, __data);
61 }
62 
63 /*
64  * __db_shalloc --
65  *	Allocate some space from the shared region.
66  *
67  * PUBLIC: int __db_shalloc __P((void *, size_t, size_t, void *));
68  */
69 int
__db_shalloc(p,len,align,retp)70 __db_shalloc(p, len, align, retp)
71 	void *p, *retp;
72 	size_t len, align;
73 {
74 	struct __data *elp;
75 	size_t *sp;
76 	void *rp;
77 
78 	/*
79 	 * We never allocate less than the size of a struct __data, align
80 	 * to less than a size_t boundary, or align to something that's not
81 	 * a multiple of a size_t.
82 	 */
83 	if (len < sizeof(struct __data))
84 		len = sizeof(struct __data);
85 	align = align <= sizeof(size_t) ?
86 	    sizeof(size_t) : ALIGN(align, sizeof(size_t));
87 
88 	/* Walk the list, looking for a slot. */
89 	for (elp = SH_LIST_FIRST((struct __head *)p, __data);
90 	    elp != NULL;
91 	    elp = SH_LIST_NEXT(elp, links, __data)) {
92 		/*
93 		 * Calculate the value of the returned pointer if we were to
94 		 * use this chunk.
95 		 *	+ Find the end of the chunk.
96 		 *	+ Subtract the memory the user wants.
97 		 *	+ Find the closest previous correctly-aligned address.
98 		 */
99 		rp = (u_int8_t *)elp + sizeof(size_t) + elp->len;
100 		rp = (u_int8_t *)rp - len;
101 		rp = (u_int8_t *)((ALIGNTYPE)rp & ~(align - 1));
102 
103 		/*
104 		 * Rp may now point before elp->links, in which case the chunk
105 		 * was too small, and we have to try again.
106 		 */
107 		if ((u_int8_t *)rp < (u_int8_t *)&elp->links)
108 			continue;
109 
110 		*(void **)retp = rp;
111 
112 #define	SHALLOC_FRAGMENT	32
113 		/*
114 		 * If there are at least SHALLOC_FRAGMENT additional bytes of
115 		 * memory, divide the chunk into two chunks.
116 		 */
117 		if ((u_int8_t *)rp >=
118 		    (u_int8_t *)&elp->links + SHALLOC_FRAGMENT) {
119 			sp = rp;
120 			*--sp = elp->len -
121 			    ((u_int8_t *)rp - (u_int8_t *)&elp->links);
122 			elp->len -= *sp + sizeof(size_t);
123 			return (0);
124 		}
125 
126 		/*
127 		 * Otherwise, we return the entire chunk, wasting some amount
128 		 * of space to keep the list compact.  However, because the
129 		 * address we're returning to the user may not be the address
130 		 * of the start of the region for alignment reasons, set the
131 		 * size_t length fields back to the "real" length field to a
132 		 * flag value, so that we can find the real length during free.
133 		 */
134 #define	ILLEGAL_SIZE	1
135 		SH_LIST_REMOVE(elp, links, __data);
136 		for (sp = rp; (u_int8_t *)--sp >= (u_int8_t *)&elp->links;)
137 			*sp = ILLEGAL_SIZE;
138 		return (0);
139 	}
140 
141 	/* Nothing found large enough; need to grow the region. */
142 	return (ENOMEM);
143 }
144 
145 /*
146  * __db_shalloc_free --
147  *	Free a shared memory allocation.
148  *
149  * PUBLIC: void __db_shalloc_free __P((void *, void *));
150  */
151 void
__db_shalloc_free(regionp,ptr)152 __db_shalloc_free(regionp, ptr)
153 	void *regionp, *ptr;
154 {
155 	struct __data *elp, *lastp, *newp;
156 	struct __head *hp;
157 	size_t free_size, *sp;
158 	int merged;
159 
160 	/*
161 	 * Step back over flagged length fields to find the beginning of
162 	 * the object and its real size.
163 	 */
164 	for (sp = (size_t *)ptr; sp[-1] == ILLEGAL_SIZE; --sp)
165 		;
166 	ptr = sp;
167 
168 	newp = (struct __data *)((u_int8_t *)ptr - sizeof(size_t));
169 	free_size = newp->len;
170 
171 	/* Trash the returned memory. */
172 #ifdef DIAGNOSTIC
173 	memset(ptr, 0xdb, free_size);
174 #endif
175 
176 	/*
177 	 * Walk the list, looking for where this entry goes.
178 	 *
179 	 * We keep the free list sorted by address so that coalescing is
180 	 * trivial.
181 	 *
182 	 * XXX
183 	 * Probably worth profiling this to see how expensive it is.
184 	 */
185 	hp = (struct __head *)regionp;
186 	for (elp = SH_LIST_FIRST(hp, __data), lastp = NULL;
187 	    elp != NULL && (void *)elp < (void *)ptr;
188 	    lastp = elp, elp = SH_LIST_NEXT(elp, links, __data))
189 		;
190 
191 	/*
192 	 * Elp is either NULL (we reached the end of the list), or the slot
193 	 * after the one that's being returned.  Lastp is either NULL (we're
194 	 * returning the first element of the list) or the element before the
195 	 * one being returned.
196 	 *
197 	 * Check for coalescing with the next element.
198 	 */
199 	merged = 0;
200 	if ((u_int8_t *)ptr + free_size == (u_int8_t *)elp) {
201 		newp->len += elp->len + sizeof(size_t);
202 		SH_LIST_REMOVE(elp, links, __data);
203 		if (lastp != NULL)
204 			SH_LIST_INSERT_AFTER(lastp, newp, links, __data);
205 		else
206 			SH_LIST_INSERT_HEAD(hp, newp, links, __data);
207 		merged = 1;
208 	}
209 
210 	/* Check for coalescing with the previous element. */
211 	if (lastp != NULL && (u_int8_t *)lastp +
212 	    lastp->len + sizeof(size_t) == (u_int8_t *)newp) {
213 		lastp->len += newp->len + sizeof(size_t);
214 
215 		/*
216 		 * If we have already put the new element into the list take
217 		 * it back off again because it's just been merged with the
218 		 * previous element.
219 		 */
220 		if (merged)
221 			SH_LIST_REMOVE(newp, links, __data);
222 		merged = 1;
223 	}
224 
225 	if (!merged)
226 		if (lastp == NULL)
227 			SH_LIST_INSERT_HEAD(hp, newp, links, __data);
228 		else
229 			SH_LIST_INSERT_AFTER(lastp, newp, links, __data);
230 }
231 
232 /*
233  * __db_shalloc_count --
234  *	Return the amount of memory on the free list.
235  *
236  * PUBLIC: size_t __db_shalloc_count __P((void *));
237  */
238 size_t
__db_shalloc_count(addr)239 __db_shalloc_count(addr)
240 	void *addr;
241 {
242 	struct __data *elp;
243 	size_t count;
244 
245 	count = 0;
246 	for (elp = SH_LIST_FIRST((struct __head *)addr, __data);
247 	    elp != NULL;
248 	    elp = SH_LIST_NEXT(elp, links, __data))
249 		count += elp->len;
250 
251 	return (count);
252 }
253 
254 /*
255  * __db_shsizeof --
256  *	Return the size of a shalloc'd piece of memory.
257  *
258  * PUBLIC: size_t __db_shsizeof __P((void *));
259  */
260 size_t
__db_shsizeof(ptr)261 __db_shsizeof(ptr)
262 	void *ptr;
263 {
264 	struct __data *elp;
265 	size_t *sp;
266 
267 	/*
268 	 * Step back over flagged length fields to find the beginning of
269 	 * the object and its real size.
270 	 */
271 	for (sp = (size_t *)ptr; sp[-1] == ILLEGAL_SIZE; --sp)
272 		;
273 
274 	elp = (struct __data *)((u_int8_t *)sp - sizeof(size_t));
275 	return (elp->len);
276 }
277 
278 /*
279  * __db_shalloc_dump --
280  *
281  * PUBLIC: void __db_shalloc_dump __P((void *, FILE *));
282  */
283 void
__db_shalloc_dump(addr,fp)284 __db_shalloc_dump(addr, fp)
285 	void *addr;
286 	FILE *fp;
287 {
288 	struct __data *elp;
289 
290 	/* Make it easy to call from the debugger. */
291 	if (fp == NULL)
292 		fp = stderr;
293 
294 	fprintf(fp, "%s\nMemory free list\n", DB_LINE);
295 
296 	for (elp = SH_LIST_FIRST((struct __head *)addr, __data);
297 	    elp != NULL;
298 	    elp = SH_LIST_NEXT(elp, links, __data))
299 		fprintf(fp, "%#lx: %lu\t", (u_long)elp, (u_long)elp->len);
300 	fprintf(fp, "\n");
301 }
302