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 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 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 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 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 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 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