00001 /*- 00002 * See the file LICENSE for redistribution information. 00003 * 00004 * Copyright (c) 1996, 1997, 1998, 1999, 2000 00005 * Sleepycat Software. All rights reserved. 00006 */ 00007 00008 #include "config.h" 00009 00010 #ifndef lint 00011 static const char revid[] = "$Id: db__salloc_8c-source.html,v 1.1 2008年06月08日 10:18:16 sebdiaz Exp $"; 00012 #endif /* not lint */ 00013 00014 #ifndef NO_SYSTEM_INCLUDES 00015 #include <sys/types.h> 00016 00017 #include <errno.h> 00018 #include <stdlib.h> 00019 #include <string.h> 00020 #endif 00021 00022 #include "db_int.h" 00023 00024 /* 00025 * Implement shared memory region allocation, using simple first-fit algorithm. 00026 * The model is that we take a "chunk" of shared memory store and begin carving 00027 * it up into areas, similarly to how malloc works. We do coalescing on free. 00028 * 00029 * The "len" field in the __data struct contains the length of the free region 00030 * (less the size_t bytes that holds the length). We use the address provided 00031 * by the caller to find this length, which allows us to free a chunk without 00032 * requiring that the caller pass in the length of the chunk they're freeing. 00033 */ 00034 SH_LIST_HEAD(__head); 00035 struct __data { 00036 size_t len; 00037 SH_LIST_ENTRY links; 00038 }; 00039 00040 /* 00041 * CDB___db_shalloc_init -- 00042 * Initialize the area as one large chunk. 00043 * 00044 * PUBLIC: void CDB___db_shalloc_init __P((void *, size_t)); 00045 */ 00046 void 00047 CDB___db_shalloc_init(area, size) 00048 void *area; 00049 size_t size; 00050 { 00051 struct __data *elp; 00052 struct __head *hp; 00053 00054 hp = area; 00055 SH_LIST_INIT(hp); 00056 00057 elp = (struct __data *)(hp + 1); 00058 elp->len = size - sizeof(struct __head) - sizeof(elp->len); 00059 SH_LIST_INSERT_HEAD(hp, elp, links, __data); 00060 } 00061 00062 /* 00063 * CDB___db_shalloc -- 00064 * Allocate some space from the shared region. 00065 * 00066 * PUBLIC: int CDB___db_shalloc __P((void *, size_t, size_t, void *)); 00067 */ 00068 int 00069 CDB___db_shalloc(p, len, align, retp) 00070 void *p, *retp; 00071 size_t len, align; 00072 { 00073 struct __data *elp; 00074 size_t *sp; 00075 void *rp; 00076 00077 /* Never allocate less than the size of a struct __data. */ 00078 if (len < sizeof(struct __data)) 00079 len = sizeof(struct __data); 00080 00081 #ifdef DIAGNOSTIC 00082 /* Add room for a guard byte. */ 00083 ++len; 00084 #endif 00085 00086 /* Never align to less than a db_align_t boundary. */ 00087 if (align <= sizeof(db_align_t)) 00088 align = sizeof(db_align_t); 00089 00090 /* Walk the list, looking for a slot. */ 00091 for (elp = SH_LIST_FIRST((struct __head *)p, __data); 00092 elp != NULL; 00093 elp = SH_LIST_NEXT(elp, links, __data)) { 00094 /* 00095 * Calculate the value of the returned pointer if we were to 00096 * use this chunk. 00097 * + Find the end of the chunk. 00098 * + Subtract the memory the user wants. 00099 * + Find the closest previous correctly-aligned address. 00100 */ 00101 rp = (u_int8_t *)elp + sizeof(size_t) + elp->len; 00102 rp = (u_int8_t *)rp - len; 00103 rp = (u_int8_t *)((db_alignp_t)rp & ~(align - 1)); 00104 00105 /* 00106 * Rp may now point before elp->links, in which case the chunk 00107 * was too small, and we have to try again. 00108 */ 00109 if ((u_int8_t *)rp < (u_int8_t *)&elp->links) 00110 continue; 00111 00112 *(void **)retp = rp; 00113 #ifdef DIAGNOSTIC 00114 /* 00115 * At this point, whether or not we still need to split up a 00116 * chunk, retp is the address of the region we are returning, 00117 * and (u_int8_t *)elp + sizeof(size_t) + elp->len gives us 00118 * the address of the first byte after the end of the chunk. 00119 * Make the byte immediately before that the guard byte. 00120 */ 00121 *((u_int8_t *)elp + sizeof(size_t) + elp->len - 1) = GUARD_BYTE; 00122 #endif 00123 00124 #define SHALLOC_FRAGMENT 32 00125 /* 00126 * If there are at least SHALLOC_FRAGMENT additional bytes of 00127 * memory, divide the chunk into two chunks. 00128 */ 00129 if ((u_int8_t *)rp >= 00130 (u_int8_t *)&elp->links + SHALLOC_FRAGMENT) { 00131 sp = rp; 00132 *--sp = elp->len - 00133 ((u_int8_t *)rp - (u_int8_t *)&elp->links); 00134 elp->len -= *sp + sizeof(size_t); 00135 return (0); 00136 } 00137 00138 /* 00139 * Otherwise, we return the entire chunk, wasting some amount 00140 * of space to keep the list compact. However, because the 00141 * address we're returning to the user may not be the address 00142 * of the start of the region for alignment reasons, set the 00143 * size_t length fields back to the "real" length field to a 00144 * flag value, so that we can find the real length during free. 00145 */ 00146 #define ILLEGAL_SIZE 1 00147 SH_LIST_REMOVE(elp, links, __data); 00148 for (sp = rp; (u_int8_t *)--sp >= (u_int8_t *)&elp->links;) 00149 *sp = ILLEGAL_SIZE; 00150 return (0); 00151 } 00152 00153 return (ENOMEM); 00154 } 00155 00156 /* 00157 * CDB___db_shalloc_free -- 00158 * Free a shared memory allocation. 00159 * 00160 * PUBLIC: void CDB___db_shalloc_free __P((void *, void *)); 00161 */ 00162 void 00163 CDB___db_shalloc_free(regionp, ptr) 00164 void *regionp, *ptr; 00165 { 00166 struct __data *elp, *lastp, *newp; 00167 struct __head *hp; 00168 size_t free_size, *sp; 00169 int merged; 00170 00171 /* 00172 * Step back over flagged length fields to find the beginning of 00173 * the object and its real size. 00174 */ 00175 for (sp = (size_t *)ptr; sp[-1] == ILLEGAL_SIZE; --sp) 00176 ; 00177 ptr = sp; 00178 00179 newp = (struct __data *)((u_int8_t *)ptr - sizeof(size_t)); 00180 free_size = newp->len; 00181 00182 #ifdef DIAGNOSTIC 00183 /* 00184 * The "real size" includes the guard byte; it's just the last 00185 * byte in the chunk, and the caller never knew it existed. 00186 * 00187 * Check it to make sure it hasn't been stomped. 00188 */ 00189 if (*((u_int8_t *)ptr + free_size - 1) != GUARD_BYTE) { 00190 /* 00191 * Eventually, once we push a DB_ENV handle down to these 00192 * routines, we should use the standard output channels. 00193 */ 00194 fprintf(stderr, 00195 "Guard byte incorrect during shared memory free.\n"); 00196 abort(); 00197 /* NOTREACHED */ 00198 } 00199 00200 /* Trash the returned memory (including guard byte). */ 00201 memset(ptr, CLEAR_BYTE, free_size); 00202 #endif 00203 00204 /* 00205 * Walk the list, looking for where this entry goes. 00206 * 00207 * We keep the free list sorted by address so that coalescing is 00208 * trivial. 00209 * 00210 * XXX 00211 * Probably worth profiling this to see how expensive it is. 00212 */ 00213 hp = (struct __head *)regionp; 00214 for (elp = SH_LIST_FIRST(hp, __data), lastp = NULL; 00215 elp != NULL && (void *)elp < (void *)ptr; 00216 lastp = elp, elp = SH_LIST_NEXT(elp, links, __data)) 00217 ; 00218 00219 /* 00220 * Elp is either NULL (we reached the end of the list), or the slot 00221 * after the one that's being returned. Lastp is either NULL (we're 00222 * returning the first element of the list) or the element before the 00223 * one being returned. 00224 * 00225 * Check for coalescing with the next element. 00226 */ 00227 merged = 0; 00228 if ((u_int8_t *)ptr + free_size == (u_int8_t *)elp) { 00229 newp->len += elp->len + sizeof(size_t); 00230 SH_LIST_REMOVE(elp, links, __data); 00231 if (lastp != NULL) 00232 SH_LIST_INSERT_AFTER(lastp, newp, links, __data); 00233 else 00234 SH_LIST_INSERT_HEAD(hp, newp, links, __data); 00235 merged = 1; 00236 } 00237 00238 /* Check for coalescing with the previous element. */ 00239 if (lastp != NULL && (u_int8_t *)lastp + 00240 lastp->len + sizeof(size_t) == (u_int8_t *)newp) { 00241 lastp->len += newp->len + sizeof(size_t); 00242 00243 /* 00244 * If we have already put the new element into the list take 00245 * it back off again because it's just been merged with the 00246 * previous element. 00247 */ 00248 if (merged) 00249 SH_LIST_REMOVE(newp, links, __data); 00250 merged = 1; 00251 } 00252 00253 if (!merged) { 00254 if (lastp == NULL) 00255 SH_LIST_INSERT_HEAD(hp, newp, links, __data); 00256 else 00257 SH_LIST_INSERT_AFTER(lastp, newp, links, __data); 00258 } 00259 } 00260 00261 /* 00262 * CDB___db_shalloc_count -- 00263 * Return the amount of memory on the free list. 00264 * 00265 * PUBLIC: size_t CDB___db_shalloc_count __P((void *)); 00266 */ 00267 size_t 00268 CDB___db_shalloc_count(addr) 00269 void *addr; 00270 { 00271 struct __data *elp; 00272 size_t count; 00273 00274 count = 0; 00275 for (elp = SH_LIST_FIRST((struct __head *)addr, __data); 00276 elp != NULL; 00277 elp = SH_LIST_NEXT(elp, links, __data)) 00278 count += elp->len; 00279 00280 return (count); 00281 } 00282 00283 /* 00284 * CDB___db_shsizeof -- 00285 * Return the size of a shalloc'd piece of memory. 00286 * 00287 * !!! 00288 * Note that this is from an internal standpoint -- it includes not only 00289 * the size of the memory being used, but also the extra alignment bytes 00290 * in front and, #ifdef DIAGNOSTIC, the guard byte at the end. 00291 * 00292 * PUBLIC: size_t CDB___db_shsizeof __P((void *)); 00293 */ 00294 size_t 00295 CDB___db_shsizeof(ptr) 00296 void *ptr; 00297 { 00298 struct __data *elp; 00299 size_t *sp; 00300 00301 /* 00302 * Step back over flagged length fields to find the beginning of 00303 * the object and its real size. 00304 */ 00305 for (sp = (size_t *)ptr; sp[-1] == ILLEGAL_SIZE; --sp) 00306 ; 00307 00308 elp = (struct __data *)((u_int8_t *)sp - sizeof(size_t)); 00309 return (elp->len); 00310 } 00311 00312 /* 00313 * CDB___db_shalloc_dump -- 00314 * 00315 * PUBLIC: void CDB___db_shalloc_dump __P((void *, FILE *)); 00316 */ 00317 void 00318 CDB___db_shalloc_dump(addr, fp) 00319 void *addr; 00320 FILE *fp; 00321 { 00322 struct __data *elp; 00323 00324 /* Make it easy to call from the debugger. */ 00325 if (fp == NULL) 00326 fp = stderr; 00327 00328 fprintf(fp, "%s\nMemory free list\n", DB_LINE); 00329 00330 for (elp = SH_LIST_FIRST((struct __head *)addr, __data); 00331 elp != NULL; 00332 elp = SH_LIST_NEXT(elp, links, __data)) 00333 fprintf(fp, "%#lx: %lu\t", (u_long)elp, (u_long)elp->len); 00334 fprintf(fp, "\n"); 00335 }