1 /* 2 * This module derived from code donated to the FreeBSD Project by 3 * Matthew Dillon <dillon@backplane.com> 4 * 5 * Copyright (c) 1998 The FreeBSD Project 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 30 #include <sys/cdefs.h> 31 __FBSDID("$FreeBSD$"); 32 33 #include <sys/param.h> 34 35 /* 36 * LIB/MEMORY/ZALLOC.C - self contained low-overhead memory pool/allocation 37 * subsystem 38 * 39 * This subsystem implements memory pools and memory allocation 40 * routines. 41 * 42 * Pools are managed via a linked list of 'free' areas. Allocating 43 * memory creates holes in the freelist, freeing memory fills them. 44 * Since the freelist consists only of free memory areas, it is possible 45 * to allocate the entire pool without incuring any structural overhead. 46 * 47 * The system works best when allocating similarly-sized chunks of 48 * memory. Care must be taken to avoid fragmentation when 49 * allocating/deallocating dissimilar chunks. 50 * 51 * When a memory pool is first allocated, the entire pool is marked as 52 * allocated. This is done mainly because we do not want to modify any 53 * portion of a pool's data area until we are given permission. The 54 * caller must explicitly deallocate portions of the pool to make them 55 * available. 56 * 57 * z[n]xalloc() works like z[n]alloc() but the allocation is made from 58 * within the specified address range. If the segment could not be 59 * allocated, NULL is returned. WARNING! The address range will be 60 * aligned to an 8 or 16 byte boundry depending on the cpu so if you 61 * give an unaligned address range, unexpected results may occur. 62 * 63 * If a standard allocation fails, the reclaim function will be called 64 * to recover some space. This usually causes other portions of the 65 * same pool to be released. Memory allocations at this low level 66 * should not block but you can do that too in your reclaim function 67 * if you want. Reclaim does not function when z[n]xalloc() is used, 68 * only for z[n]alloc(). 69 * 70 * Allocation and frees of 0 bytes are valid operations. 71 */ 72 73 #include "zalloc_defs.h" 74 75 /* 76 * Objects in the pool must be aligned to at least the size of struct MemNode. 77 * They must also be aligned to MALLOCALIGN, which should normally be larger 78 * than the struct, so assert that to be so at compile time. 79 */ 80 typedef char assert_align[(sizeof(struct MemNode) <= MALLOCALIGN) ? 1 : -1]; 81 82 #define MEMNODE_SIZE_MASK MALLOCALIGN_MASK 83 84 /* 85 * znalloc() - allocate memory (without zeroing) from pool. Call reclaim 86 * and retry if appropriate, return NULL if unable to allocate 87 * memory. 88 */ 89 90 void * 91 znalloc(MemPool *mp, uintptr_t bytes, size_t align) 92 { 93 MemNode **pmn; 94 MemNode *mn; 95 96 /* 97 * align according to pool object size (can be 0). This is 98 * inclusive of the MEMNODE_SIZE_MASK minimum alignment. 99 * 100 */ 101 bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK; 102 103 if (bytes == 0) 104 return ((void *)-1); 105 106 /* 107 * locate freelist entry big enough to hold the object. If all objects 108 * are the same size, this is a constant-time function. 109 */ 110 111 if (bytes > mp->mp_Size - mp->mp_Used) 112 return (NULL); 113 114 for (pmn = &mp->mp_First; (mn = *pmn) != NULL; pmn = &mn->mr_Next) { 115 char *ptr = (char *)mn; 116 uintptr_t dptr; 117 char *aligned; 118 size_t extra; 119 120 dptr = (uintptr_t)(ptr + MALLOCALIGN); /* pointer to data */ 121 aligned = (char *)(roundup2(dptr, align) - MALLOCALIGN); 122 extra = aligned - ptr; 123 124 if (bytes + extra > mn->mr_Bytes) 125 continue; 126 127 /* 128 * Cut extra from head and create new memory node from 129 * remainder. 130 */ 131 132 if (extra != 0) { 133 MemNode *new; 134 135 new = (MemNode *)aligned; 136 new->mr_Next = mn->mr_Next; 137 new->mr_Bytes = mn->mr_Bytes - extra; 138 139 /* And update current memory node */ 140 mn->mr_Bytes = extra; 141 mn->mr_Next = new; 142 /* In next iteration, we will get our aligned address */ 143 continue; 144 } 145 146 /* 147 * Cut a chunk of memory out of the beginning of this 148 * block and fixup the link appropriately. 149 */ 150 151 if (mn->mr_Bytes == bytes) { 152 *pmn = mn->mr_Next; 153 } else { 154 mn = (MemNode *)((char *)mn + bytes); 155 mn->mr_Next = ((MemNode *)ptr)->mr_Next; 156 mn->mr_Bytes = ((MemNode *)ptr)->mr_Bytes - bytes; 157 *pmn = mn; 158 } 159 mp->mp_Used += bytes; 160 return(ptr); 161 } 162 163 /* 164 * Memory pool is full, return NULL. 165 */ 166 167 return (NULL); 168 } 169 170 /* 171 * zfree() - free previously allocated memory 172 */ 173 174 void 175 zfree(MemPool *mp, void *ptr, uintptr_t bytes) 176 { 177 MemNode **pmn; 178 MemNode *mn; 179 180 /* 181 * align according to pool object size (can be 0). This is 182 * inclusive of the MEMNODE_SIZE_MASK minimum alignment. 183 */ 184 bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK; 185 186 if (bytes == 0) 187 return; 188 189 /* 190 * panic if illegal pointer 191 */ 192 193 if ((char *)ptr < (char *)mp->mp_Base || 194 (char *)ptr + bytes > (char *)mp->mp_End || 195 ((uintptr_t)ptr & MEMNODE_SIZE_MASK) != 0) 196 panic("zfree(%p,%ju): wild pointer", ptr, (uintmax_t)bytes); 197 198 /* 199 * free the segment 200 */ 201 mp->mp_Used -= bytes; 202 203 for (pmn = &mp->mp_First; (mn = *pmn) != NULL; pmn = &mn->mr_Next) { 204 /* 205 * If area between last node and current node 206 * - check range 207 * - check merge with next area 208 * - check merge with previous area 209 */ 210 if ((char *)ptr <= (char *)mn) { 211 /* 212 * range check 213 */ 214 if ((char *)ptr + bytes > (char *)mn) { 215 panic("zfree(%p,%ju): corrupt memlist1", ptr, 216 (uintmax_t)bytes); 217 } 218 219 /* 220 * merge against next area or create independent area 221 */ 222 223 if ((char *)ptr + bytes == (char *)mn) { 224 ((MemNode *)ptr)->mr_Next = mn->mr_Next; 225 ((MemNode *)ptr)->mr_Bytes = 226 bytes + mn->mr_Bytes; 227 } else { 228 ((MemNode *)ptr)->mr_Next = mn; 229 ((MemNode *)ptr)->mr_Bytes = bytes; 230 } 231 *pmn = mn = (MemNode *)ptr; 232 233 /* 234 * merge against previous area (if there is a previous 235 * area). 236 */ 237 238 if (pmn != &mp->mp_First) { 239 if ((char *)pmn + ((MemNode*)pmn)->mr_Bytes == 240 (char *)ptr) { 241 ((MemNode *)pmn)->mr_Next = mn->mr_Next; 242 ((MemNode *)pmn)->mr_Bytes += 243 mn->mr_Bytes; 244 mn = (MemNode *)pmn; 245 } 246 } 247 return; 248 } 249 if ((char *)ptr < (char *)mn + mn->mr_Bytes) { 250 panic("zfree(%p,%ju): corrupt memlist2", ptr, 251 (uintmax_t)bytes); 252 } 253 } 254 /* 255 * We are beyond the last MemNode, append new MemNode. Merge against 256 * previous area if possible. 257 */ 258 if (pmn == &mp->mp_First || 259 (char *)pmn + ((MemNode *)pmn)->mr_Bytes != (char *)ptr) { 260 ((MemNode *)ptr)->mr_Next = NULL; 261 ((MemNode *)ptr)->mr_Bytes = bytes; 262 *pmn = (MemNode *)ptr; 263 mn = (MemNode *)ptr; 264 } else { 265 ((MemNode *)pmn)->mr_Bytes += bytes; 266 mn = (MemNode *)pmn; 267 } 268 } 269 270 /* 271 * zextendPool() - extend memory pool to cover additional space. 272 * 273 * Note: the added memory starts out as allocated, you 274 * must free it to make it available to the memory subsystem. 275 * 276 * Note: mp_Size may not reflect (mp_End - mp_Base) range 277 * due to other parts of the system doing their own sbrk() 278 * calls. 279 */ 280 281 void 282 zextendPool(MemPool *mp, void *base, uintptr_t bytes) 283 { 284 if (mp->mp_Size == 0) { 285 mp->mp_Base = base; 286 mp->mp_Used = bytes; 287 mp->mp_End = (char *)base + bytes; 288 mp->mp_Size = bytes; 289 } else { 290 void *pend = (char *)mp->mp_Base + mp->mp_Size; 291 292 if (base < mp->mp_Base) { 293 mp->mp_Size += (char *)mp->mp_Base - (char *)base; 294 mp->mp_Used += (char *)mp->mp_Base - (char *)base; 295 mp->mp_Base = base; 296 } 297 base = (char *)base + bytes; 298 if (base > pend) { 299 mp->mp_Size += (char *)base - (char *)pend; 300 mp->mp_Used += (char *)base - (char *)pend; 301 mp->mp_End = (char *)base; 302 } 303 } 304 } 305 306 #ifdef ZALLOCDEBUG 307 308 void 309 zallocstats(MemPool *mp) 310 { 311 int abytes = 0; 312 int hbytes = 0; 313 int fcount = 0; 314 MemNode *mn; 315 316 printf("%d bytes reserved", (int)mp->mp_Size); 317 318 mn = mp->mp_First; 319 320 if ((void *)mn != (void *)mp->mp_Base) { 321 abytes += (char *)mn - (char *)mp->mp_Base; 322 } 323 324 while (mn != NULL) { 325 if ((char *)mn + mn->mr_Bytes != mp->mp_End) { 326 hbytes += mn->mr_Bytes; 327 ++fcount; 328 } 329 if (mn->mr_Next != NULL) { 330 abytes += (char *)mn->mr_Next - 331 ((char *)mn + mn->mr_Bytes); 332 } 333 mn = mn->mr_Next; 334 } 335 printf(" %d bytes allocated\n%d fragments (%d bytes fragmented)\n", 336 abytes, fcount, hbytes); 337 } 338 339 #endif 340