Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

kernel/mm.c

Go to the documentation of this file.
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.

Generated on Tue Dec 10 00:09:13 2002 for brickOS Kernel Developer by doxygen 1.2.15