lib/libstand/zalloc.c

   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 /*
  34  * LIB/MEMORY/ZALLOC.C  - self contained low-overhead memory pool/allocation
  35  *                        subsystem
  36  *
  37  *      This subsystem implements memory pools and memory allocation
  38  *      routines.
  39  *
  40  *      Pools are managed via a linked list of 'free' areas.  Allocating
  41  *      memory creates holes in the freelist, freeing memory fills them.
  42  *      Since the freelist consists only of free memory areas, it is possible
  43  *      to allocate the entire pool without incuring any structural overhead.
  44  *
  45  *      The system works best when allocating similarly-sized chunks of
  46  *      memory.  Care must be taken to avoid fragmentation when
  47  *      allocating/deallocating dissimilar chunks.
  48  *
  49  *      When a memory pool is first allocated, the entire pool is marked as
  50  *      allocated.  This is done mainly because we do not want to modify any
  51  *      portion of a pool's data area until we are given permission.  The
  52  *      caller must explicitly deallocate portions of the pool to make them
  53  *      available.
  54  *
  55  *      z[n]xalloc() works like z[n]alloc() but the allocation is made from
  56  *      within the specified address range.  If the segment could not be
  57  *      allocated, NULL is returned.  WARNING!  The address range will be
  58  *      aligned to an 8 or 16 byte boundry depending on the cpu so if you
  59  *      give an unaligned address range, unexpected results may occur.
  60  *
  61  *      If a standard allocation fails, the reclaim function will be called
  62  *      to recover some space.  This usually causes other portions of the
  63  *      same pool to be released.  Memory allocations at this low level
  64  *      should not block but you can do that too in your reclaim function
  65  *      if you want.  Reclaim does not function when z[n]xalloc() is used,
  66  *      only for z[n]alloc().
  67  *
  68  *      Allocation and frees of 0 bytes are valid operations.
  69  */
  70
  71 #include "zalloc_defs.h"
  72
  73 /*
  74  * Objects in the pool must be aligned to at least the size of struct MemNode.
  75  * They must also be aligned to MALLOCALIGN, which should normally be larger
  76  * than the struct, so assert that to be so at compile time.
  77  */
  78 typedef char assert_align[(sizeof(struct MemNode) <= MALLOCALIGN) ? 1 : -1];
  79
  80 #define MEMNODE_SIZE_MASK       MALLOCALIGN_MASK
  81
  82 /*
  83  * znalloc() -  allocate memory (without zeroing) from pool.  Call reclaim
  84  *              and retry if appropriate, return NULL if unable to allocate
  85  *              memory.
  86  */
  87
  88 void *
  89 znalloc(MemPool *mp, uintptr_t bytes)
  90 {
  91     /*
  92      * align according to pool object size (can be 0).  This is
  93      * inclusive of the MEMNODE_SIZE_MASK minimum alignment.
  94      *
  95      */
  96     bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK;
  97
  98     if (bytes == 0)
  99         return((void *)-1);
 100
 101     /*
 102      * locate freelist entry big enough to hold the object.  If all objects
 103      * are the same size, this is a constant-time function.
 104      */
 105
 106     if (bytes <= mp->mp_Size - mp->mp_Used) {
 107         MemNode **pmn;
 108         MemNode *mn;
 109
 110         for (pmn = &mp->mp_First; (mn=*pmn) != NULL; pmn = &mn->mr_Next) {
 111             if (bytes > mn->mr_Bytes)
 112                 continue;
 113
 114             /*
 115              *  Cut a chunk of memory out of the beginning of this
 116              *  block and fixup the link appropriately.
 117              */
 118
 119             {
 120                 char *ptr = (char *)mn;
 121
 122                 if (mn->mr_Bytes == bytes) {
 123                     *pmn = mn->mr_Next;
 124                 } else {
 125                     mn = (MemNode *)((char *)mn + bytes);
 126                     mn->mr_Next  = ((MemNode *)ptr)->mr_Next;
 127                     mn->mr_Bytes = ((MemNode *)ptr)->mr_Bytes - bytes;
 128                     *pmn = mn;
 129                 }
 130                 mp->mp_Used += bytes;
 131                 return(ptr);
 132             }
 133         }
 134     }
 135
 136     /*
 137      * Memory pool is full, return NULL.
 138      */
 139
 140     return(NULL);
 141 }
 142
 143 /*
 144  * zfree() - free previously allocated memory
 145  */
 146
 147 void
 148 zfree(MemPool *mp, void *ptr, uintptr_t bytes)
 149 {
 150     /*
 151      * align according to pool object size (can be 0).  This is
 152      * inclusive of the MEMNODE_SIZE_MASK minimum alignment.
 153      */
 154     bytes = (bytes + MEMNODE_SIZE_MASK) & ~MEMNODE_SIZE_MASK;
 155
 156     if (bytes == 0)
 157         return;
 158
 159     /*
 160      * panic if illegal pointer
 161      */
 162
 163     if ((char *)ptr < (char *)mp->mp_Base ||
 164         (char *)ptr + bytes > (char *)mp->mp_End ||
 165         ((uintptr_t)ptr & MEMNODE_SIZE_MASK) != 0)
 166         panic("zfree(%p,%ju): wild pointer", ptr, (uintmax_t)bytes);
 167
 168     /*
 169      * free the segment
 170      */
 171
 172     {
 173         MemNode **pmn;
 174         MemNode *mn;
 175
 176         mp->mp_Used -= bytes;
 177
 178         for (pmn = &mp->mp_First; (mn = *pmn) != NULL; pmn = &mn->mr_Next) {
 179             /*
 180              * If area between last node and current node
 181              *  - check range
 182              *  - check merge with next area
 183              *  - check merge with previous area
 184              */
 185             if ((char *)ptr <= (char *)mn) {
 186                 /*
 187                  * range check
 188                  */
 189                 if ((char *)ptr + bytes > (char *)mn) {
 190                     panic("zfree(%p,%ju): corrupt memlist1", ptr,
 191                         (uintmax_t)bytes);
 192                 }
 193
 194                 /*
 195                  * merge against next area or create independant area
 196                  */
 197
 198                 if ((char *)ptr + bytes == (char *)mn) {
 199                     ((MemNode *)ptr)->mr_Next = mn->mr_Next;
 200                     ((MemNode *)ptr)->mr_Bytes= bytes + mn->mr_Bytes;
 201                 } else {
 202                     ((MemNode *)ptr)->mr_Next = mn;
 203                     ((MemNode *)ptr)->mr_Bytes= bytes;
 204                 }
 205                 *pmn = mn = (MemNode *)ptr;
 206
 207                 /*
 208                  * merge against previous area (if there is a previous
 209                  * area).
 210                  */
 211
 212                 if (pmn != &mp->mp_First) {
 213                     if ((char*)pmn + ((MemNode*)pmn)->mr_Bytes == (char*)ptr) {
 214                         ((MemNode *)pmn)->mr_Next = mn->mr_Next;
 215                         ((MemNode *)pmn)->mr_Bytes += mn->mr_Bytes;
 216                         mn = (MemNode *)pmn;
 217                     }
 218                 }
 219                 return;
 220                 /* NOT REACHED */
 221             }
 222             if ((char *)ptr < (char *)mn + mn->mr_Bytes) {
 223                 panic("zfree(%p,%ju): corrupt memlist2", ptr,
 224                     (uintmax_t)bytes);
 225             }
 226         }
 227         /*
 228          * We are beyond the last MemNode, append new MemNode.  Merge against
 229          * previous area if possible.
 230          */
 231         if (pmn == &mp->mp_First ||
 232             (char *)pmn + ((MemNode *)pmn)->mr_Bytes != (char *)ptr
 233         ) {
 234             ((MemNode *)ptr)->mr_Next = NULL;
 235             ((MemNode *)ptr)->mr_Bytes = bytes;
 236             *pmn = (MemNode *)ptr;
 237             mn = (MemNode *)ptr;
 238         } else {
 239             ((MemNode *)pmn)->mr_Bytes += bytes;
 240             mn = (MemNode *)pmn;
 241         }
 242     }
 243 }
 244
 245 /*
 246  * zextendPool() - extend memory pool to cover additional space.
 247  *
 248  *                 Note: the added memory starts out as allocated, you
 249  *                 must free it to make it available to the memory subsystem.
 250  *
 251  *                 Note: mp_Size may not reflect (mp_End - mp_Base) range
 252  *                 due to other parts of the system doing their own sbrk()
 253  *                 calls.
 254  */
 255
 256 void
 257 zextendPool(MemPool *mp, void *base, uintptr_t bytes)
 258 {
 259     if (mp->mp_Size == 0) {
 260         mp->mp_Base = base;
 261         mp->mp_Used = bytes;
 262         mp->mp_End = (char *)base + bytes;
 263         mp->mp_Size = bytes;
 264     } else {
 265         void *pend = (char *)mp->mp_Base + mp->mp_Size;
 266
 267         if (base < mp->mp_Base) {
 268             mp->mp_Size += (char *)mp->mp_Base - (char *)base;
 269             mp->mp_Used += (char *)mp->mp_Base - (char *)base;
 270             mp->mp_Base = base;
 271         }
 272         base = (char *)base + bytes;
 273         if (base > pend) {
 274             mp->mp_Size += (char *)base - (char *)pend;
 275             mp->mp_Used += (char *)base - (char *)pend;
 276             mp->mp_End = (char *)base;
 277         }
 278     }
 279 }
 280
 281 #ifdef ZALLOCDEBUG
 282
 283 void
 284 zallocstats(MemPool *mp)
 285 {
 286     int abytes = 0;
 287     int hbytes = 0;
 288     int fcount = 0;
 289     MemNode *mn;
 290
 291     printf("%d bytes reserved", (int) mp->mp_Size);
 292
 293     mn = mp->mp_First;
 294
 295     if ((void *)mn != (void *)mp->mp_Base) {
 296         abytes += (char *)mn - (char *)mp->mp_Base;
 297     }
 298
 299     while (mn) {
 300         if ((char *)mn + mn->mr_Bytes != mp->mp_End) {
 301             hbytes += mn->mr_Bytes;
 302             ++fcount;
 303         }
 304         if (mn->mr_Next)
 305             abytes += (char *)mn->mr_Next - ((char *)mn + mn->mr_Bytes);
 306         mn = mn->mr_Next;
 307     }
 308     printf(" %d bytes allocated\n%d fragments (%d bytes fragmented)\n",
 309         abytes,
 310         fcount,
 311         hbytes
 312     );
 313 }
 314
 315 #endif
 316