mm.c
Go to the documentation of this file.
1 
6 /*
7  * The contents of this file are subject to the Mozilla Public License
8  * Version 1.0 (the "License"); you may not use this file except in
9  * compliance with the License. You may obtain a copy of the License at
10  * http://www.mozilla.org/MPL/
11  *
12  * Software distributed under the License is distributed on an "AS IS"
13  * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
14  * License for the specific language governing rights and limitations
15  * under the License.
16  *
17  * The Original Code is legOS code, released October 17, 1999.
18  *
19  * The Initial Developer of the Original Code is Markus L. Noga.
20  * Portions created by Markus L. Noga are Copyright (C) 1999
21  * Markus L. Noga. All Rights Reserved.
22  *
23  * Contributor(s): Markus L. Noga <markus@noga.de>
24  */
25 
26 #include <sys/mm.h>
27 
28 #ifdef CONF_MM
29 
30 #include <stdlib.h>
31 #include <sys/tm.h>
32 #include <sys/critsec.h>
33 #include <string.h>
34 
36 //
37 // Variables
38 //
40 
41 size_t *mm_first_free;
42 
43 #ifndef CONF_TM
44 typedef size_t tid_t;
45 
47 
50 const tid_t ctid=0x0001;
51 #endif
52 
54 //
55 // Functions
56 //
58 
59 //
60 // memory block structure:
61 // 0 1 : pid of owner (0=empty)
62 // 2 3 : size of data block >> 1
63 // 4 ... 4+2n: data
64 //
65 
67 /* \param ptr pointer to size field of current block
68  \return size of block
69 */
70 size_t mm_try_join(size_t *ptr) {
71  size_t *next=ptr+*ptr+1;
72  size_t increase=0;
73 
74  while(*next==MM_FREE && next>=&mm_start) {
75  increase+=*(next+1) + MM_HEADER_SIZE;
76  next +=*(next+1) + MM_HEADER_SIZE;
77  }
78  return (*ptr)+=increase;
79 }
80 
82 
84 void mm_defrag() {
85  size_t *ptr = &mm_start;
86 #ifdef CONF_TM
88 #endif
89  while(ptr >= &mm_start) {
90  if(*ptr == MM_FREE)
91  mm_try_join(ptr+1);
92  ptr += *(ptr+1);
93  ptr += MM_HEADER_SIZE;
94  }
95 #ifdef CONF_TM
97 #endif
98 }
99 
101 
103 void mm_update_first_free(size_t *start) {
104  size_t *ptr=start;
105 
106  while((*ptr!=MM_FREE) && (ptr>=&mm_start))
107  ptr+=*(ptr+1)+MM_HEADER_SIZE;
108 
109  mm_first_free=ptr;
110 }
111 
112 
114 
116 void mm_init() {
117  size_t *current,*next;
118 
119  current=&mm_start;
120 
121  // memory layout
122  //
123  MM_BLOCK_FREE (&mm_start); // ram
124 
125  // something at 0xc000 ?
126 
127  MM_BLOCK_RESERVED(0xef30); // lcddata
128  MM_BLOCK_FREE (0xef50); // ram2
129  MM_BLOCK_RESERVED(0xf000); // motor
130  MM_BLOCK_FREE (0xfe00); // ram4
131  MM_BLOCK_RESERVED(0xff00); // stack, onchip
132 
133  // expand last block to encompass all available memory
134  *current=(int)(((-(int) current)-2)>>1);
135 
136  mm_update_first_free(&mm_start);
137 }
138 
139 
141 
144 void *malloc(size_t size) {
145  size_t *ptr,*next;
146 
147  size=(size+1)>>1; // only multiples of 2
148 
149 #ifdef CONF_TM
151 #endif
152  ptr=mm_first_free;
153 
154  while(ptr>=&mm_start) {
155  if(*(ptr++)==MM_FREE) { // free block?
156 #ifdef CONF_TM
157  mm_try_join(ptr); // unite with later blocks
158 #endif
159  if(*ptr>=size) { // big enough?
160  *(ptr-1)=(size_t)ctid; // set owner
161 
162  // split this block?
163  if((*ptr-size)>=MM_SPLIT_THRESH) {
164  next=ptr+size+1;
165  *(next++)=MM_FREE;
166  *(next)=*ptr-size-MM_HEADER_SIZE;
167  mm_try_join(next);
168 
169  *ptr=size;
170  }
171 
172  // was it the first free one?
173  if(ptr==mm_first_free+1)
174  mm_update_first_free(ptr+*ptr+1);
175 
176 #ifdef CONF_TM
178 #endif
179  return (void*) (ptr+1);
180  }
181  }
182 
183  ptr+=(*ptr)+1; // find next block.
184  }
185 
186 #ifdef CONF_TM
188 #endif
189  return NULL;
190 }
191 
192 
194 
198 void free(void *the_ptr) {
199  size_t *ptr=the_ptr;
200 #ifndef CONF_TM
201  size_t *p2,*next;
202 #endif
203 
204  if(ptr==NULL || (((size_t)ptr)&1) )
205  return;
206 
207  ptr-=MM_HEADER_SIZE;
208  *((size_t*) ptr)=MM_FREE; // mark as free
209 
210 #ifdef CONF_TM
211  // for task safe operations, free needs to be
212  // atomic and nonblocking, because it may be
213  // called by the scheduler.
214  //
215  // therefore, just update mm_first_free
216  //
218  mm_first_free=ptr; // update mm_first_free
219 #else
220  // without task management, we have the time to
221  // unite neighboring memory blocks.
222  //
223  p2=&mm_start;
224  while(p2!=ptr) { // we could make free
225  next=p2+*(p2+1)+MM_HEADER_SIZE; // O(1) if we included
226  if(*p2==MM_FREE && next==ptr) // a pointer to the
227  break; // previous block.
228  p2=next; // I don't want to.
229  }
230  mm_try_join(p2+1); // defragment free areas
231 
233  mm_update_first_free(ptr); // update mm_first_free
234 #endif
235 }
236 
237 
239 
243 void *calloc(size_t nmemb, size_t size) {
244  void *ptr;
245  size_t original_size = size;
246 
247  if (nmemb == 0 || size == 0)
248  return 0;
249 
250  size*=nmemb;
251 
252  // if an overflow occurred, size/nmemb will not equal original_size
253  if (size/nmemb != original_size)
254  return 0;
255 
256  if((ptr=malloc(size))!=NULL)
257  memset(ptr,0,size);
258 
259  return ptr;
260 }
261 
263 
265 void mm_reaper() {
266  size_t *ptr;
267 
268  // pass 1: mark as free
269  ptr=&mm_start;
270  while(ptr>=&mm_start) {
271  if(*ptr==(size_t)ctid)
272  *ptr=MM_FREE;
273  ptr+=*(ptr+1)+MM_HEADER_SIZE;
274  }
275 
276  // pass 2: defragment free areas
277  // this may alter free blocks
278  mm_defrag();
279 }
280 
282 int mm_free_mem(void) {
283  int free = 0;
284  size_t *ptr;
285 
286 #ifdef CONF_TM
288 #endif
289 
290  // Iterate through the free list
291  for (ptr = mm_first_free;
292  ptr >= &mm_start;
293  ptr += *(ptr+1) + MM_HEADER_SIZE)
294  free += *(ptr+1);
295 
296 #ifdef CONF_TM
298 #endif
299  return free*2;
300 }
301 
302 #endif
int mm_free_mem(void)
how many bytes of memory are free?
Interface: string functions.
void free(void *ptr)
return the allocated memory to memory management.
Interface: kernel level critical sections.
void * calloc(size_t nmemb, size_t size)
allocate and return pointer to initialized memory
void mm_reaper()
free all blocks allocated by the current process
#define LEAVE_KERNEL_CRITICAL_SECTION()
Definition: critsec.h:42
#define NULL
null pointer value
Definition: mem.h:35
#define ENTER_KERNEL_CRITICAL_SECTION()
Definition: critsec.h:41
#define MM_SPLIT_THRESH
split off if 8+ data bytes
Definition: mm.h:54
signed int tid_t
task id type
Definition: tm.h:143
Internal Interface: task management.
#define MM_FREE
marker: block free
Definition: mm.h:47
#define MM_BLOCK_RESERVED(addr)
memory from addr on is reserved
Definition: mm.h:79
Internal Interface: memory management.
tdata_t * ctid
ptr to current process data
void * malloc(size_t size)
allocate and return pointer to uninitialized memory
size_t mm_start
end of kernel code + data
size_t * mm_first_free
ptr to first free block.
#define MM_BLOCK_FREE(addr)
memory from addr on can be allocated
Definition: mm.h:68
Interface: reduced standard C library.
void mm_init()
initialize memory management
void * memset(void *s, int c, size_t n)
fill memory block with a byte value.
#define MM_HEADER_SIZE
2 words header: pid, size
Definition: mm.h:53

brickOS is released under the Mozilla Public License.
Original code copyright 1998-2005 by the authors.

Generated on Sat Feb 14 2015 23:12:05 for brickOS Kernel Developer by doxygen 1.8.9.1