00001 /*------------------------------------------------------------------------ 00002 * This file is used to manage heaps 00003 * 00004 * Created April 2, 2008 by Jim Patchell 00005 * 00006 * Now, this is derived from malloc and free that comes with WinAVR and 00007 * following is the copyright notice that was in THAT code. It is mostly 00008 * unmodified. 00009 * ----------------------------------------------- 00010 Copyright (c) 2002, 2004 Joerg Wunsch 00011 All rights reserved. 00012 00013 Redistribution and use in source and binary forms, with or without 00014 modification, are permitted provided that the following conditions are met: 00015 00016 * Redistributions of source code must retain the above copyright 00017 notice, this list of conditions and the following disclaimer. 00018 00019 * Redistributions in binary form must reproduce the above copyright 00020 notice, this list of conditions and the following disclaimer in 00021 the documentation and/or other materials provided with the 00022 distribution. 00023 00024 * Neither the name of the copyright holders nor the names of 00025 contributors may be used to endorse or promote products derived 00026 from this software without specific prior written permission. 00027 00028 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 00029 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00030 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00031 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 00032 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 00033 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 00034 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 00035 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 00036 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 00037 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 00038 POSSIBILITY OF SUCH DAMAGE. 00039 * ----------------------------------------------------------------------- 00040 * Code first modified on April 2, 2008 00041 ---------------------------------------------------------------------------*/ 00042 00043 #include <stdlib.h> 00044 #include "HeapManager.h" 00045 #include <avr/io.h> 00046 00053 00068 void *HeapAlloc(HEAP_BLOCK *pHB,size_t len) 00069 { 00070 struct __freelist *fp1, *fp2; 00071 char *cp; 00072 size_t s, avail; 00073 00074 /* 00075 * Our minimum chunk size is the size of a pointer (plus the 00076 * size of the "sz" field, but we don't need to account for 00077 * this), otherwise we could not possibly fit a freelist entry 00078 * into the chunk later. 00079 */ 00080 PendSemaphore(pHB->Blocker,0); 00081 if (len < sizeof(struct __freelist) - sizeof(size_t)) 00082 len = sizeof(struct __freelist) - sizeof(size_t); 00083 00084 /* 00085 * First, walk the free list and try finding a chunk that 00086 * would match exactly. If we found one, we are done. While 00087 * walking, note down the size of the largest chunk we found 00088 * that would still fit the request -- we need it for step 2. 00089 * 00090 */ 00091 for (s = 0, fp1 = pHB->__flp, fp2 = 0; 00092 fp1; 00093 fp2 = fp1, fp1 = fp1->nx) { 00094 if (fp1->sz == len) { 00095 /* 00096 * Found it. Disconnect the chunk from the 00097 * freelist, and return it. 00098 */ 00099 if (fp2) 00100 fp2->nx = fp1->nx; 00101 else 00102 pHB->__flp = fp1->nx; 00103 PostSemaphore(pHB->Blocker,0); 00104 return &(fp1->nx); 00105 } 00106 if (fp1->sz > len) { 00107 if (s == 0 || fp1->sz < s) 00108 s = fp1->sz; 00109 } 00110 } 00111 /* 00112 * Step 2: If we found a chunk on the freelist that would fit 00113 * (but was too large), look it up again and use it, since it 00114 * is our closest match now. Since the freelist entry needs 00115 * to be split into two entries then, watch out that the 00116 * difference between the requested size and the size of the 00117 * chunk found is large enough for another freelist entry; if 00118 * not, just enlarge the request size to what we have found, 00119 * and use the entire chunk. 00120 */ 00121 if (s) { 00122 if (s - len < sizeof(struct __freelist)) 00123 len = s; 00124 for (fp1 = pHB->__flp, fp2 = 0; 00125 fp1; 00126 fp2 = fp1, fp1 = fp1->nx) { 00127 if (fp1->sz == s) { 00128 if (len == s) { 00129 /* 00130 * Use entire chunk; same as 00131 * above. 00132 */ 00133 if (fp2) 00134 fp2->nx = fp1->nx; 00135 else 00136 pHB->__flp = fp1->nx; 00137 PostSemaphore(pHB->Blocker,0); 00138 return &(fp1->nx); 00139 } 00140 /* 00141 * Split them up. Note that we leave 00142 * the first part as the new (smaller) 00143 * freelist entry, and return the 00144 * upper portion to the caller. This 00145 * saves us the work to fix up the 00146 * freelist chain; we just need to 00147 * fixup the size of the current 00148 * entry, and note down the size of 00149 * the new chunk before returning it 00150 * to the caller. 00151 */ 00152 cp = (char *)fp1; 00153 s -= len; 00154 cp += s; 00155 fp2 = (struct __freelist *)cp; 00156 fp2->sz = len; 00157 fp1->sz = s - sizeof(size_t); 00158 PostSemaphore(pHB->Blocker,0); 00159 return &(fp2->nx); 00160 } 00161 } 00162 } 00163 /* 00164 * Step 3: If the request could not be satisfied from a 00165 * freelist entry, just prepare a new chunk. This means we 00166 * need to obtain more memory first. The largest address just 00167 * not allocated so far is remembered in the brkval variable. 00168 * Under Unix, the "break value" was the end of the data 00169 * segment as dynamically requested from the operating system. 00170 * Since we don't have an operating system, just make sure 00171 * that we don't collide with the stack. 00172 */ 00173 if (pHB->BrkVal == 0) 00174 pHB->BrkVal = pHB->Start; 00175 cp = pHB->End; 00176 if (cp == 0) 00177 cp = STACK_POINTER() - pHB->Margin; 00178 avail = cp - pHB->BrkVal; 00179 /* 00180 * Both tests below are needed to catch the case len >= 0xfffe. 00181 */ 00182 if (avail >= len && avail >= len + sizeof(size_t)) { 00183 fp1 = (struct __freelist *)pHB->BrkVal; 00184 pHB->BrkVal += len + sizeof(size_t); 00185 fp1->sz = len; 00186 PostSemaphore(pHB->Blocker,0); 00187 return &(fp1->nx); 00188 } 00189 /* 00190 * Step 4: There's no help, just fail. :-/ 00191 */ 00192 PostSemaphore(pHB->Blocker,0); 00193 return 0; 00194 } 00195 00209 void HeapFree(HEAP_BLOCK *pHB,void *p) 00210 { 00211 struct __freelist *fp1, *fp2, *fpnew; 00212 char *cp1, *cp2, *cpnew; 00213 00214 /* ISO C says free(NULL) must be a no-op */ 00215 if (p == 0) 00216 return; 00217 00218 PendSemaphore(pHB->Blocker,0); 00219 cpnew = p; 00220 cpnew -= sizeof(size_t); 00221 fpnew = (struct __freelist *)cpnew; 00222 fpnew->nx = 0; 00223 00224 /* 00225 * Trivial case first: if there's no freelist yet, our entry 00226 * will be the only one on it. 00227 */ 00228 if (pHB->__flp == 0) { 00229 pHB->__flp = fpnew; 00230 PostSemaphore(pHB->Blocker,0); 00231 return; 00232 } 00233 00234 /* 00235 * Now, find the position where our new entry belongs onto the 00236 * freelist. Try to aggregate the chunk with adjacent chunks 00237 * if possible. 00238 */ 00239 for (fp1 = pHB->__flp, fp2 = 0; 00240 fp1; 00241 fp2 = fp1, fp1 = fp1->nx) { 00242 if (fp1 < fpnew) 00243 continue; 00244 cp1 = (char *)fp1; 00245 fpnew->nx = fp1; 00246 if ((char *)&(fpnew->nx) + fpnew->sz == cp1) { 00247 /* upper chunk adjacent, assimilate it */ 00248 fpnew->sz += fp1->sz + sizeof(size_t); 00249 fpnew->nx = fp1->nx; 00250 } 00251 if (fp2 == 0) { 00252 /* new head of freelist */ 00253 pHB->__flp = fpnew; 00254 PostSemaphore(pHB->Blocker,0); 00255 return; 00256 } 00257 break; 00258 } 00259 /* 00260 * Note that we get here either if we hit the "break" above, 00261 * or if we fell off the end of the loop. The latter means 00262 * we've got a new topmost chunk. Either way, try aggregating 00263 * with the lower chunk if possible. 00264 */ 00265 fp2->nx = fpnew; 00266 cp2 = (char *)&(fp2->nx); 00267 if (cp2 + fp2->sz == cpnew) { 00268 /* lower junk adjacent, merge */ 00269 fp2->sz += fpnew->sz + sizeof(size_t); 00270 fp2->nx = fpnew->nx; 00271 } 00272 PostSemaphore(pHB->Blocker,0); 00273 } 00274 00275 //----------------------------------------------------------------------- 00276 // The following code was added by Jim Patchell on April 2, 2008 00277 //----------------------------------------------------------------------- 00278 00298 HEAP_BLOCK * HeapInit(char *start, char *end) 00299 { 00300 //-------------------------------------------------------------------- 00301 // Initialize semaphore used to block access to malloc and free 00302 // parameters: 00303 // start.........start of heap 00304 // end...........end of heap 00305 // 00306 // We use memory in the defined heap to allocate memory for the 00307 // object that is used to manage the memory 00308 // 00309 // return value: 00310 // pointer to heap object 00311 //-------------------------------------------------------------------- 00312 HEAP_BLOCK *pHB = (HEAP_BLOCK *)start; 00313 start += sizeof (HEAP_BLOCK); //allocate heap control block 00314 pHB->Blocker = (ECB *)start; 00315 start += sizeof (ECB); //allocate event control block 00316 pHB->Start = start; 00317 pHB->End = end; 00318 pHB->BrkVal = start; 00319 pHB->Margin = 32; //default value for stack margin...not needed..really 00320 pHB->__flp = 0; //free list is empty 00321 CreateSemaphore(pHB->Blocker,1,SEMAPHORE_MODE_BLOCKING,"Malloc"); 00322 return pHB; 00323 } 00324