git.sur5r.net Git - freertos/blob - Demo/Common/ethernet/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 #if (MEM_LIBC_MALLOC == 0)
  51 /* lwIP replacement for your libc malloc() */
  52
  53 struct mem {
  54   mem_size_t next, prev;
  55 #if MEM_ALIGNMENT == 1
  56   u8_t used;
  57 #elif MEM_ALIGNMENT == 2
  58   u16_t used;
  59 #elif MEM_ALIGNMENT == 4
  60   u32_t used;
  61 #elif MEM_ALIGNMENT == 8
  62   u64_t used;
  63 #else
  64 #error "unhandled MEM_ALIGNMENT size"
  65 #endif /* MEM_ALIGNMENT */
  66 };
  67
  68 static struct mem *ram_end;
  69 #if 1
  70 /* Adam original */
  71 static u8_t ram[MEM_SIZE + sizeof(struct mem) + MEM_ALIGNMENT];
  72 #else
  73 /* Christiaan alignment fix */
  74 static u8_t *ram;
  75 static struct mem ram_heap[1 + ( (MEM_SIZE + sizeof(struct mem) - 1) / sizeof(struct mem))];
  76 #endif
  77
  78 #define MIN_SIZE 12
  79 #if 0 /* this one does not align correctly for some, resulting in crashes */
  80 #define SIZEOF_STRUCT_MEM (unsigned int)MEM_ALIGN_SIZE(sizeof(struct mem))
  81 #else
  82 #define SIZEOF_STRUCT_MEM (sizeof(struct mem) + \
  83                           (((sizeof(struct mem) % MEM_ALIGNMENT) == 0)? 0 : \
  84                           (4 - (sizeof(struct mem) % MEM_ALIGNMENT))))
  85 #endif
  86
  87 static struct mem *lfree;   /* pointer to the lowest free block */
  88
  89 static sys_sem_t mem_sem;
  90
  91 static void
  92 plug_holes(struct mem *mem)
  93 {
  94   struct mem *nmem;
  95   struct mem *pmem;
  96
  97   LWIP_ASSERT("plug_holes: mem >= ram", (u8_t *)mem >= ram);
  98   LWIP_ASSERT("plug_holes: mem < ram_end", (u8_t *)mem < (u8_t *)ram_end);
  99   LWIP_ASSERT("plug_holes: mem->used == 0", mem->used == 0);
 100
 101   /* plug hole forward */
 102   LWIP_ASSERT("plug_holes: mem->next <= MEM_SIZE", mem->next <= MEM_SIZE);
 103
 104   nmem = (struct mem *)&ram[mem->next];
 105   if (mem != nmem && nmem->used == 0 && (u8_t *)nmem != (u8_t *)ram_end) {
 106     if (lfree == nmem) {
 107       lfree = mem;
 108     }
 109     mem->next = nmem->next;
 110     ((struct mem *)&ram[nmem->next])->prev = (u8_t *)mem - ram;
 111   }
 112
 113   /* plug hole backward */
 114   pmem = (struct mem *)&ram[mem->prev];
 115   if (pmem != mem && pmem->used == 0) {
 116     if (lfree == mem) {
 117       lfree = pmem;
 118     }
 119     pmem->next = mem->next;
 120     ((struct mem *)&ram[mem->next])->prev = (u8_t *)pmem - ram;
 121   }
 122 }
 123
 124 void
 125 mem_init(void)
 126 {
 127   struct mem *mem;
 128
 129 #if 1
 130   /* Adam original */
 131 #else
 132   /* Christiaan alignment fix */
 133   ram = (u8_t*)ram_heap;
 134 #endif
 135   memset(ram, 0, MEM_SIZE);
 136   mem = (struct mem *)ram;
 137   mem->next = MEM_SIZE;
 138   mem->prev = 0;
 139   mem->used = 0;
 140   ram_end = (struct mem *)&ram[MEM_SIZE];
 141   ram_end->used = 1;
 142   ram_end->next = MEM_SIZE;
 143   ram_end->prev = MEM_SIZE;
 144
 145   mem_sem = sys_sem_new(1);
 146
 147   lfree = (struct mem *)ram;
 148
 149 #if MEM_STATS
 150   lwip_stats.mem.avail = MEM_SIZE;
 151 #endif /* MEM_STATS */
 152 }
 153
 154 void
 155 mem_free(void *rmem)
 156 {
 157   struct mem *mem;
 158
 159   if (rmem == NULL) {
 160     LWIP_DEBUGF(MEM_DEBUG | DBG_TRACE | 2, ("mem_free(p == NULL) was called.\n"));
 161     return;
 162   }
 163
 164   sys_sem_wait(mem_sem);
 165
 166   LWIP_ASSERT("mem_free: legal memory", (u8_t *)rmem >= (u8_t *)ram &&
 167     (u8_t *)rmem < (u8_t *)ram_end);
 168
 169   if ((u8_t *)rmem < (u8_t *)ram || (u8_t *)rmem >= (u8_t *)ram_end) {
 170     LWIP_DEBUGF(MEM_DEBUG | 3, ("mem_free: illegal memory\n"));
 171 #if MEM_STATS
 172     ++lwip_stats.mem.err;
 173 #endif /* MEM_STATS */
 174     sys_sem_signal(mem_sem);
 175     return;
 176   }
 177   mem = (struct mem *)((u8_t *)rmem - SIZEOF_STRUCT_MEM);
 178
 179   LWIP_ASSERT("mem_free: mem->used", mem->used);
 180
 181   mem->used = 0;
 182
 183   if (mem < lfree) {
 184     lfree = mem;
 185   }
 186
 187 #if MEM_STATS
 188   lwip_stats.mem.used -= mem->next - ((u8_t *)mem - ram);
 189
 190 #endif /* MEM_STATS */
 191   plug_holes(mem);
 192   sys_sem_signal(mem_sem);
 193 }
 194
 195 void *
 196 mem_realloc(void *rmem, mem_size_t newsize)
 197 {
 198   mem_size_t size;
 199   mem_size_t ptr, ptr2;
 200   struct mem *mem, *mem2;
 201
 202   /* Expand the size of the allocated memory region so that we can
 203      adjust for alignment. */
 204   if ((newsize % MEM_ALIGNMENT) != 0) {
 205    newsize += MEM_ALIGNMENT - ((newsize + SIZEOF_STRUCT_MEM) % MEM_ALIGNMENT);
 206   }
 207
 208   if (newsize > MEM_SIZE) {
 209     return NULL;
 210   }
 211
 212   sys_sem_wait(mem_sem);
 213
 214   LWIP_ASSERT("mem_realloc: legal memory", (u8_t *)rmem >= (u8_t *)ram &&
 215    (u8_t *)rmem < (u8_t *)ram_end);
 216
 217   if ((u8_t *)rmem < (u8_t *)ram || (u8_t *)rmem >= (u8_t *)ram_end) {
 218     LWIP_DEBUGF(MEM_DEBUG | 3, ("mem_realloc: illegal memory\n"));
 219     return rmem;
 220   }
 221   mem = (struct mem *)((u8_t *)rmem - SIZEOF_STRUCT_MEM);
 222
 223   ptr = (u8_t *)mem - ram;
 224
 225   size = mem->next - ptr - SIZEOF_STRUCT_MEM;
 226 #if MEM_STATS
 227   lwip_stats.mem.used -= (size - newsize);
 228 #endif /* MEM_STATS */
 229
 230   if (newsize + SIZEOF_STRUCT_MEM + MIN_SIZE < size) {
 231     ptr2 = ptr + SIZEOF_STRUCT_MEM + newsize;
 232     mem2 = (struct mem *)&ram[ptr2];
 233     mem2->used = 0;
 234     mem2->next = mem->next;
 235     mem2->prev = ptr;
 236     mem->next = ptr2;
 237     if (mem2->next != MEM_SIZE) {
 238       ((struct mem *)&ram[mem2->next])->prev = ptr2;
 239     }
 240
 241     plug_holes(mem2);
 242   }
 243   sys_sem_signal(mem_sem);
 244   return rmem;
 245 }
 246
 247 #if 1
 248 /**
 249  * Adam's mem_malloc(), suffers from bug #17922
 250  * Set if to 0 for alternative mem_malloc().
 251  */
 252 void *
 253 mem_malloc(mem_size_t size)
 254 {
 255   mem_size_t ptr, ptr2;
 256   struct mem *mem, *mem2;
 257
 258   if (size == 0) {
 259     return NULL;
 260   }
 261
 262   /* Expand the size of the allocated memory region so that we can
 263      adjust for alignment. */
 264   if ((size % MEM_ALIGNMENT) != 0) {
 265     size += MEM_ALIGNMENT - ((size + SIZEOF_STRUCT_MEM) % MEM_ALIGNMENT);
 266   }
 267
 268   if (size > MEM_SIZE) {
 269     return NULL;
 270   }
 271
 272   sys_sem_wait(mem_sem);
 273
 274   for (ptr = (u8_t *)lfree - ram; ptr < MEM_SIZE; ptr = ((struct mem *)&ram[ptr])->next) {
 275     mem = (struct mem *)&ram[ptr];
 276     if (!mem->used &&
 277        mem->next - (ptr + SIZEOF_STRUCT_MEM) >= size + SIZEOF_STRUCT_MEM) {
 278       ptr2 = ptr + SIZEOF_STRUCT_MEM + size;
 279       mem2 = (struct mem *)&ram[ptr2];
 280
 281       mem2->prev = ptr;
 282       mem2->next = mem->next;
 283       mem->next = ptr2;
 284       if (mem2->next != MEM_SIZE) {
 285         ((struct mem *)&ram[mem2->next])->prev = ptr2;
 286       }
 287
 288       mem2->used = 0;
 289       mem->used = 1;
 290 #if MEM_STATS
 291       lwip_stats.mem.used += (size + SIZEOF_STRUCT_MEM);
 292       /*      if (lwip_stats.mem.max < lwip_stats.mem.used) {
 293         lwip_stats.mem.max = lwip_stats.mem.used;
 294         } */
 295       if (lwip_stats.mem.max < ptr2) {
 296         lwip_stats.mem.max = ptr2;
 297       }
 298 #endif /* MEM_STATS */
 299
 300       if (mem == lfree) {
 301         /* Find next free block after mem */
 302         while (lfree->used && lfree != ram_end) {
 303           lfree = (struct mem *)&ram[lfree->next];
 304         }
 305         LWIP_ASSERT("mem_malloc: !lfree->used", !lfree->used);
 306       }
 307       sys_sem_signal(mem_sem);
 308       LWIP_ASSERT("mem_malloc: allocated memory not above ram_end.",
 309        (mem_ptr_t)mem + SIZEOF_STRUCT_MEM + size <= (mem_ptr_t)ram_end);
 310       LWIP_ASSERT("mem_malloc: allocated memory properly aligned.",
 311        (unsigned long)((u8_t *)mem + SIZEOF_STRUCT_MEM) % MEM_ALIGNMENT == 0);
 312       return (u8_t *)mem + SIZEOF_STRUCT_MEM;
 313     }
 314   }
 315   LWIP_DEBUGF(MEM_DEBUG | 2, ("mem_malloc: could not allocate %"S16_F" bytes\n", (s16_t)size));
 316 #if MEM_STATS
 317   ++lwip_stats.mem.err;
 318 #endif /* MEM_STATS */
 319   sys_sem_signal(mem_sem);
 320   return NULL;
 321 }
 322 #else
 323 /**
 324  * Adam's mem_malloc() plus solution for bug #17922
 325  */
 326 void *
 327 mem_malloc(mem_size_t size)
 328 {
 329   mem_size_t ptr, ptr2;
 330   struct mem *mem, *mem2;
 331
 332   if (size == 0) {
 333     return NULL;
 334   }
 335
 336   /* Expand the size of the allocated memory region so that we can
 337      adjust for alignment. */
 338   if ((size % MEM_ALIGNMENT) != 0) {
 339     size += MEM_ALIGNMENT - ((size + SIZEOF_STRUCT_MEM) % MEM_ALIGNMENT);
 340   }
 341
 342   if (size > MEM_SIZE) {
 343     return NULL;
 344   }
 345
 346   sys_sem_wait(mem_sem);
 347
 348   for (ptr = (u8_t *)lfree - ram; ptr < MEM_SIZE - size; ptr = ((struct mem *)&ram[ptr])->next) {
 349     mem = (struct mem *)&ram[ptr];
 350
 351     if (!mem->used) {
 352
 353       ptr2 = ptr + SIZEOF_STRUCT_MEM + size;
 354
 355       if (mem->next - (ptr + (2*SIZEOF_STRUCT_MEM)) >= size) {
 356         /* split large block, create empty remainder */
 357         mem->next = ptr2;
 358         mem->used = 1;
 359         /* create mem2 struct */
 360         mem2 = (struct mem *)&ram[ptr2];
 361         mem2->used = 0;
 362         mem2->next = mem->next;
 363         mem2->prev = ptr;
 364
 365         if (mem2->next != MEM_SIZE) {
 366           ((struct mem *)&ram[mem2->next])->prev = ptr2;
 367         }
 368       }
 369       else if (mem->next - (ptr + SIZEOF_STRUCT_MEM) > size) {
 370         /* near fit, no split, no mem2 creation,
 371            round up to mem->next */
 372         ptr2 = mem->next;
 373         mem->used = 1;
 374       }
 375       else if (mem->next - (ptr + SIZEOF_STRUCT_MEM) == size) {
 376         /* exact fit, do not split, no mem2 creation */
 377         mem->next = ptr2;
 378         mem->used = 1;
 379       }
 380
 381       if (mem->used) {
 382 #if MEM_STATS
 383         lwip_stats.mem.used += (size + SIZEOF_STRUCT_MEM);
 384         if (lwip_stats.mem.max < ptr2) {
 385           lwip_stats.mem.max = ptr2;
 386         }
 387 #endif /* MEM_STATS */
 388         if (mem == lfree) {
 389           /* Find next free block after mem */
 390           while (lfree->used && lfree != ram_end) {
 391             lfree = (struct mem *)&ram[lfree->next];
 392           }
 393           LWIP_ASSERT("mem_malloc: !lfree->used", !lfree->used);
 394         }
 395         sys_sem_signal(mem_sem);
 396         LWIP_ASSERT("mem_malloc: allocated memory not above ram_end.",
 397          (mem_ptr_t)mem + SIZEOF_STRUCT_MEM + size <= (mem_ptr_t)ram_end);
 398         LWIP_ASSERT("mem_malloc: allocated memory properly aligned.",
 399          (unsigned long)((u8_t *)mem + SIZEOF_STRUCT_MEM) % MEM_ALIGNMENT == 0);
 400         return (u8_t *)mem + SIZEOF_STRUCT_MEM;
 401       }
 402     }
 403   }
 404   LWIP_DEBUGF(MEM_DEBUG | 2, ("mem_malloc: could not allocate %"S16_F" bytes\n", (s16_t)size));
 405 #if MEM_STATS
 406   ++lwip_stats.mem.err;
 407 #endif /* MEM_STATS */
 408   sys_sem_signal(mem_sem);
 409   return NULL;
 410 }
 411 #endif
 412
 413 #endif /* MEM_LIBC_MALLOC == 0 */
 414