lwip/core/mem.c

   1 /** @file
   2  *
   3  * Dynamic memory manager
   4  *
   5  */
   6
   7 /*
   8  * Copyright (c) 2001-2004 Swedish Institute of Computer Science.
   9  * All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without modification,
  12  * are permitted provided that the following conditions are met:
  13  *
  14  * 1. Redistributions of source code must retain the above copyright notice,
  15  *    this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright notice,
  17  *    this list of conditions and the following disclaimer in the documentation
  18  *    and/or other materials provided with the distribution.
  19  * 3. The name of the author may not be used to endorse or promote products
  20  *    derived from this software without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
  23  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  24  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
  25  * SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  26  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
  27  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  28  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  29  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  30  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
  31  * OF SUCH DAMAGE.
  32  *
  33  * This file is part of the lwIP TCP/IP stack.
  34  *
  35  * Author: Adam Dunkels <adam@sics.se>
  36  *
  37  */
  38
  39 #include <string.h>
  40
  41 #include "lwip/arch.h"
  42 #include "lwip/opt.h"
  43 #include "lwip/def.h"
  44 #include "lwip/mem.h"
  45
  46 #include "lwip/sys.h"
  47
  48 #include "lwip/stats.h"
  49
  50 struct mem {
  51   mem_size_t next, prev;
  52 #if MEM_ALIGNMENT == 1
  53   u8_t used;
  54 #elif MEM_ALIGNMENT == 2
  55   u16_t used;
  56 #elif MEM_ALIGNMENT == 4
  57   u32_t used;
  58 #elif MEM_ALIGNMENT == 8
  59   u64_t used;
  60 #else
  61 #error "unhandled MEM_ALIGNMENT size"
  62 #endif /* MEM_ALIGNMENT */
  63 };
  64
  65 static struct mem *ram_end;
  66 static u8_t ram[MEM_SIZE + sizeof(struct mem) + MEM_ALIGNMENT];
  67
  68 #define MIN_SIZE 12
  69 #if 0 /* this one does not align correctly for some, resulting in crashes */
  70 #define SIZEOF_STRUCT_MEM (unsigned int)MEM_ALIGN_SIZE(sizeof(struct mem))
  71 #else
  72 #define SIZEOF_STRUCT_MEM (sizeof(struct mem) + \
  73                           (((sizeof(struct mem) % MEM_ALIGNMENT) == 0)? 0 : \
  74                           (4 - (sizeof(struct mem) % MEM_ALIGNMENT))))
  75 #endif
  76
  77 static struct mem *lfree;   /* pointer to the lowest free block */
  78
  79 static sys_sem mem_sem;
  80
  81 static void
  82 plug_holes(struct mem *mem)
  83 {
  84   struct mem *nmem;
  85   struct mem *pmem;
  86
  87   LWIP_ASSERT("plug_holes: mem >= ram", (u8_t *)mem >= ram);
  88   LWIP_ASSERT("plug_holes: mem < ram_end", (u8_t *)mem < (u8_t *)ram_end);
  89   LWIP_ASSERT("plug_holes: mem->used == 0", mem->used == 0);
  90
  91   /* plug hole forward */
  92   LWIP_ASSERT("plug_holes: mem->next <= MEM_SIZE", mem->next <= MEM_SIZE);
  93
  94   nmem = (struct mem *)&ram[mem->next];
  95   if (mem != nmem && nmem->used == 0 && (u8_t *)nmem != (u8_t *)ram_end) {
  96     if (lfree == nmem) {
  97       lfree = mem;
  98     }
  99     mem->next = nmem->next;
 100     ((struct mem *)&ram[nmem->next])->prev = (u8_t *)mem - ram;
 101   }
 102
 103   /* plug hole backward */
 104   pmem = (struct mem *)&ram[mem->prev];
 105   if (pmem != mem && pmem->used == 0) {
 106     if (lfree == mem) {
 107       lfree = pmem;
 108     }
 109     pmem->next = mem->next;
 110     ((struct mem *)&ram[mem->next])->prev = (u8_t *)pmem - ram;
 111   }
 112
 113 }
 114 void
 115 mem_init(void)
 116 {
 117   struct mem *mem;
 118
 119   memset(ram, 0, MEM_SIZE);
 120   mem = (struct mem *)ram;
 121   mem->next = MEM_SIZE;
 122   mem->prev = 0;
 123   mem->used = 0;
 124   ram_end = (struct mem *)&ram[MEM_SIZE];
 125   ram_end->used = 1;
 126   ram_end->next = MEM_SIZE;
 127   ram_end->prev = MEM_SIZE;
 128
 129   LWP_SemInit(&mem_sem,1,1);
 130
 131   lfree = (struct mem *)ram;
 132
 133 #if MEM_STATS
 134   lwip_stats.mem.avail = MEM_SIZE;
 135 #endif /* MEM_STATS */
 136 }
 137 void
 138 mem_free(void *rmem)
 139 {
 140   struct mem *mem;
 141
 142   if (rmem == NULL) {
 143     LWIP_DEBUGF(MEM_DEBUG | DBG_TRACE | 2, ("mem_free(p == NULL) was called.\n"));
 144     return;
 145   }
 146
 147   LWP_SemWait(mem_sem);
 148
 149   LWIP_ASSERT("mem_free: legal memory", (u8_t *)rmem >= (u8_t *)ram &&
 150     (u8_t *)rmem < (u8_t *)ram_end);
 151
 152   if ((u8_t *)rmem < (u8_t *)ram || (u8_t *)rmem >= (u8_t *)ram_end) {
 153     LWIP_DEBUGF(MEM_DEBUG | 3, ("mem_free: illegal memory\n"));
 154 #if MEM_STATS
 155     ++lwip_stats.mem.err;
 156 #endif /* MEM_STATS */
 157     LWP_SemPost(mem_sem);
 158     return;
 159   }
 160   mem = (struct mem *)((u8_t *)rmem - SIZEOF_STRUCT_MEM);
 161
 162   LWIP_ASSERT("mem_free: mem->used", mem->used);
 163
 164   mem->used = 0;
 165
 166   if (mem < lfree) {
 167     lfree = mem;
 168   }
 169
 170 #if MEM_STATS
 171   lwip_stats.mem.used -= mem->next - ((u8_t *)mem - ram);
 172
 173 #endif /* MEM_STATS */
 174   plug_holes(mem);
 175   LWP_SemPost(mem_sem);
 176 }
 177 void *
 178 mem_reallocm(void *rmem, mem_size_t newsize)
 179 {
 180   void *nmem;
 181   nmem = mem_malloc(newsize);
 182   if (nmem == NULL) {
 183     return mem_realloc(rmem, newsize);
 184   }
 185   memcpy(nmem, rmem, newsize);
 186   mem_free(rmem);
 187   return nmem;
 188 }
 189
 190 void *
 191 mem_realloc(void *rmem, mem_size_t newsize)
 192 {
 193   mem_size_t size;
 194   mem_size_t ptr, ptr2;
 195   struct mem *mem, *mem2;
 196
 197   /* Expand the size of the allocated memory region so that we can
 198      adjust for alignment. */
 199   if ((newsize % MEM_ALIGNMENT) != 0) {
 200    newsize += MEM_ALIGNMENT - ((newsize + SIZEOF_STRUCT_MEM) % MEM_ALIGNMENT);
 201   }
 202
 203   if (newsize > MEM_SIZE) {
 204     return NULL;
 205   }
 206
 207   LWP_SemWait(mem_sem);
 208
 209   LWIP_ASSERT("mem_realloc: legal memory", (u8_t *)rmem >= (u8_t *)ram &&
 210    (u8_t *)rmem < (u8_t *)ram_end);
 211
 212   if ((u8_t *)rmem < (u8_t *)ram || (u8_t *)rmem >= (u8_t *)ram_end) {
 213     LWIP_DEBUGF(MEM_DEBUG | 3, ("mem_realloc: illegal memory\n"));
 214     return rmem;
 215   }
 216   mem = (struct mem *)((u8_t *)rmem - SIZEOF_STRUCT_MEM);
 217
 218   ptr = (u8_t *)mem - ram;
 219
 220   size = mem->next - ptr - SIZEOF_STRUCT_MEM;
 221 #if MEM_STATS
 222   lwip_stats.mem.used -= (size - newsize);
 223 #endif /* MEM_STATS */
 224
 225   if (newsize + SIZEOF_STRUCT_MEM + MIN_SIZE < size) {
 226     ptr2 = ptr + SIZEOF_STRUCT_MEM + newsize;
 227     mem2 = (struct mem *)&ram[ptr2];
 228     mem2->used = 0;
 229     mem2->next = mem->next;
 230     mem2->prev = ptr;
 231     mem->next = ptr2;
 232     if (mem2->next != MEM_SIZE) {
 233       ((struct mem *)&ram[mem2->next])->prev = ptr2;
 234     }
 235
 236     plug_holes(mem2);
 237   }
 238   LWP_SemPost(mem_sem);
 239   return rmem;
 240 }
 241 void *
 242 mem_malloc(mem_size_t size)
 243 {
 244   mem_size_t ptr, ptr2;
 245   struct mem *mem, *mem2;
 246
 247   if (size == 0) {
 248     return NULL;
 249   }
 250
 251   /* Expand the size of the allocated memory region so that we can
 252      adjust for alignment. */
 253   if ((size % MEM_ALIGNMENT) != 0) {
 254     size += MEM_ALIGNMENT - ((size + SIZEOF_STRUCT_MEM) % MEM_ALIGNMENT);
 255   }
 256
 257   if (size > MEM_SIZE) {
 258     return NULL;
 259   }
 260
 261   LWP_SemWait(mem_sem);
 262
 263   for (ptr = (u8_t *)lfree - ram; ptr < MEM_SIZE; ptr = ((struct mem *)&ram[ptr])->next) {
 264     mem = (struct mem *)&ram[ptr];
 265     if (!mem->used &&
 266        mem->next - (ptr + SIZEOF_STRUCT_MEM) >= size + SIZEOF_STRUCT_MEM) {
 267       ptr2 = ptr + SIZEOF_STRUCT_MEM + size;
 268       mem2 = (struct mem *)&ram[ptr2];
 269
 270       mem2->prev = ptr;
 271       mem2->next = mem->next;
 272       mem->next = ptr2;
 273       if (mem2->next != MEM_SIZE) {
 274         ((struct mem *)&ram[mem2->next])->prev = ptr2;
 275       }
 276
 277       mem2->used = 0;
 278       mem->used = 1;
 279 #if MEM_STATS
 280       lwip_stats.mem.used += (size + SIZEOF_STRUCT_MEM);
 281       /*      if (lwip_stats.mem.max < lwip_stats.mem.used) {
 282         lwip_stats.mem.max = lwip_stats.mem.used;
 283   } */
 284       if (lwip_stats.mem.max < ptr2) {
 285         lwip_stats.mem.max = ptr2;
 286       }
 287 #endif /* MEM_STATS */
 288
 289       if (mem == lfree) {
 290   /* Find next free block after mem */
 291         while (lfree->used && lfree != ram_end) {
 292     lfree = (struct mem *)&ram[lfree->next];
 293         }
 294         LWIP_ASSERT("mem_malloc: !lfree->used", !lfree->used);
 295       }
 296       LWP_SemPost(mem_sem);
 297       LWIP_ASSERT("mem_malloc: allocated memory not above ram_end.",
 298        (mem_ptr_t)mem + SIZEOF_STRUCT_MEM + size <= (mem_ptr_t)ram_end);
 299       LWIP_ASSERT("mem_malloc: allocated memory properly aligned.",
 300        (unsigned long)((u8_t *)mem + SIZEOF_STRUCT_MEM) % MEM_ALIGNMENT == 0);
 301       return (u8_t *)mem + SIZEOF_STRUCT_MEM;
 302     }
 303   }
 304   LWIP_DEBUGF(MEM_DEBUG | 2, ("mem_malloc: could not allocate %"S16_F" bytes\n", (s16_t)size));
 305 #if MEM_STATS
 306   ++lwip_stats.mem.err;
 307 #endif /* MEM_STATS */
 308   LWP_SemPost(mem_sem);
 309   return NULL;
 310 }