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