00001 00006 /* 00007 * The contents of this file are subject to the Mozilla Public License 00008 * Version 1.0 (the "License"); you may not use this file except in 00009 * compliance with the License. You may obtain a copy of the License at 00010 * http://www.mozilla.org/MPL/ 00011 * 00012 * Software distributed under the License is distributed on an "AS IS" 00013 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the 00014 * License for the specific language governing rights and limitations 00015 * under the License. 00016 * 00017 * The Original Code is legOS code, released October 17, 1999. 00018 * 00019 * The Initial Developer of the Original Code is Markus L. Noga. 00020 * Portions created by Markus L. Noga are Copyright (C) 1999 00021 * Markus L. Noga. All Rights Reserved. 00022 * 00023 * Contributor(s): Markus L. Noga <markus@noga.de> 00024 */ 00025 00026 #include <sys/mm.h> 00027 00028 #ifdef CONF_MM 00029 00030 #include <stdlib.h> 00031 #include <sys/tm.h> 00032 #include <sys/critsec.h> 00033 #include <string.h> 00034 00036 // 00037 // Variables 00038 // 00040 00041 size_t *mm_first_free; 00042 00043 #ifndef CONF_TM 00044 typedef size_t tid_t; 00045 00047 00050 const tid_t ctid=0x0001; 00051 #endif 00052 00054 // 00055 // Functions 00056 // 00058 00059 // 00060 // memory block structure: 00061 // 0 1 : pid of owner (0=empty) 00062 // 2 3 : size of data block >> 1 00063 // 4 ... 4+2n: data 00064 // 00065 00067 /* \param ptr pointer to size field of current block 00068 \return size of block 00069 */ 00070 size_t mm_try_join(size_t *ptr) { 00071 size_t *next=ptr+*ptr+1; 00072 size_t increase=0; 00073 00074 while(*next==MM_FREE && next>=&mm_start) { 00075 increase+=*(next+1) + MM_HEADER_SIZE; 00076 next +=*(next+1) + MM_HEADER_SIZE; 00077 } 00078 return (*ptr)+=increase; 00079 } 00080 00082 00084 void mm_defrag() { 00085 size_t *ptr = &mm_start; 00086 #ifdef CONF_TM 00087 ENTER_KERNEL_CRITICAL_SECTION(); 00088 #endif 00089 while(ptr >= &mm_start) { 00090 if(*ptr == MM_FREE) 00091 mm_try_join(ptr+1); 00092 ptr += *(ptr+1); 00093 ptr += MM_HEADER_SIZE; 00094 } 00095 #ifdef CONF_TM 00096 LEAVE_KERNEL_CRITICAL_SECTION(); 00097 #endif 00098 } 00099 00101 00103 void mm_update_first_free(size_t *start) { 00104 size_t *ptr=start; 00105 00106 while((*ptr!=MM_FREE) && (ptr>=&mm_start)) 00107 ptr+=*(ptr+1)+MM_HEADER_SIZE; 00108 00109 mm_first_free=ptr; 00110 } 00111 00112 00114 00116 void mm_init() { 00117 size_t *current,*next; 00118 00119 current=&mm_start; 00120 00121 // memory layout 00122 // 00123 MM_BLOCK_FREE (&mm_start); // ram 00124 00125 // something at 0xc000 ? 00126 00127 MM_BLOCK_RESERVED(0xef30); // lcddata 00128 MM_BLOCK_FREE (0xef50); // ram2 00129 MM_BLOCK_RESERVED(0xf000); // motor 00130 MM_BLOCK_FREE (0xf010); // ram3 00131 MM_BLOCK_RESERVED(0xfb80); // bad Memory and vectors 00132 MM_BLOCK_FREE (0xfe00); // ram4 00133 MM_BLOCK_RESERVED(0xff00); // stack, onchip 00134 00135 // expand last block to encompass all available memory 00136 *current=(int)(((-(int) current)-2)>>1); 00137 00138 mm_update_first_free(&mm_start); 00139 } 00140 00141 00143 00146 void *malloc(size_t size) { 00147 size_t *ptr,*next; 00148 00149 size=(size+1)>>1; // only multiples of 2 00150 00151 #ifdef CONF_TM 00152 ENTER_KERNEL_CRITICAL_SECTION(); 00153 #endif 00154 ptr=mm_first_free; 00155 00156 while(ptr>=&mm_start) { 00157 if(*(ptr++)==MM_FREE) { // free block? 00158 #ifdef CONF_TM 00159 mm_try_join(ptr); // unite with later blocks 00160 #endif 00161 if(*ptr>=size) { // big enough? 00162 *(ptr-1)=(size_t)ctid; // set owner 00163 00164 // split this block? 00165 if((*ptr-size)>=MM_SPLIT_THRESH) { 00166 next=ptr+size+1; 00167 *(next++)=MM_FREE; 00168 *(next)=*ptr-size-MM_HEADER_SIZE; 00169 mm_try_join(next); 00170 00171 *ptr=size; 00172 } 00173 00174 // was it the first free one? 00175 if(ptr==mm_first_free+1) 00176 mm_update_first_free(ptr+*ptr+1); 00177 00178 #ifdef CONF_TM 00179 LEAVE_KERNEL_CRITICAL_SECTION(); 00180 #endif 00181 return (void*) (ptr+1); 00182 } 00183 } 00184 00185 ptr+=(*ptr)+1; // find next block. 00186 } 00187 00188 #ifdef CONF_TM 00189 LEAVE_KERNEL_CRITICAL_SECTION(); 00190 #endif 00191 return NULL; 00192 } 00193 00194 00196 00200 void free(void *the_ptr) { 00201 size_t *ptr=the_ptr; 00202 #ifndef CONF_TM 00203 size_t *p2,*next; 00204 #endif 00205 00206 if(ptr==NULL || (((size_t)ptr)&1) ) 00207 return; 00208 00209 ptr-=MM_HEADER_SIZE; 00210 *((size_t*) ptr)=MM_FREE; // mark as free 00211 00212 #ifdef CONF_TM 00213 // for task safe operations, free needs to be 00214 // atomic and nonblocking, because it may be 00215 // called by the scheduler. 00216 // 00217 // therefore, just update mm_first_free 00218 // 00219 if(ptr<mm_first_free || mm_first_free<&mm_start) 00220 mm_first_free=ptr; // update mm_first_free 00221 #else 00222 // without task management, we have the time to 00223 // unite neighboring memory blocks. 00224 // 00225 p2=&mm_start; 00226 while(p2!=ptr) { // we could make free 00227 next=p2+*(p2+1)+MM_HEADER_SIZE; // O(1) if we included 00228 if(*p2==MM_FREE && next==ptr) // a pointer to the 00229 break; // previous block. 00230 p2=next; // I don't want to. 00231 } 00232 mm_try_join(p2+1); // defragment free areas 00233 00234 if(ptr<mm_first_free || mm_first_free<&mm_start) 00235 mm_update_first_free(ptr); // update mm_first_free 00236 #endif 00237 } 00238 00239 00241 00245 void *calloc(size_t nmemb, size_t size) { 00246 void *ptr; 00247 size_t original_size = size; 00248 00249 if (nmemb == 0 || size == 0) 00250 return 0; 00251 00252 size*=nmemb; 00253 00254 // if an overflow occurred, size/nmemb will not equal original_size 00255 if (size/nmemb != original_size) 00256 return 0; 00257 00258 if((ptr=malloc(size))!=NULL) 00259 memset(ptr,0,size); 00260 00261 return ptr; 00262 } 00263 00265 00267 void mm_reaper() { 00268 size_t *ptr; 00269 00270 // pass 1: mark as free 00271 ptr=&mm_start; 00272 while(ptr>=&mm_start) { 00273 if(*ptr==(size_t)ctid) 00274 *ptr=MM_FREE; 00275 ptr+=*(ptr+1)+MM_HEADER_SIZE; 00276 } 00277 00278 // pass 2: defragment free areas 00279 // this may alter free blocks 00280 mm_defrag(); 00281 } 00282 00284 int mm_free_mem(void) { 00285 int free = 0; 00286 size_t *ptr; 00287 00288 #ifdef CONF_TM 00289 ENTER_KERNEL_CRITICAL_SECTION(); 00290 #endif 00291 00292 // Iterate through the free list 00293 for (ptr = mm_first_free; 00294 ptr >= &mm_start; 00295 ptr += *(ptr+1) + MM_HEADER_SIZE) 00296 free += *(ptr+1); 00297 00298 #ifdef CONF_TM 00299 LEAVE_KERNEL_CRITICAL_SECTION(); 00300 #endif 00301 return free*2; 00302 } 00303 00304 #endif
brickOS is released under the
Mozilla Public License.
Original code copyright 1998-2002 by the authors. |