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