git.sur5r.net Git - freertos/blob - Demo/Common/ethernet/lwIP/core/mem.c

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