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