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
41size_t *mm_first_free;
42
43#ifndef CONF_TM
44typedef size_t tid_t;
45
47
50const 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*/
70size_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
84void 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
103void 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
116void 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
144void *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
198void 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
243void *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
265void 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
282int 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
#define NULL
null pointer value
Definition: mem.h:35
Internal Interface: memory management.
int mm_free_mem(void)
how many bytes of memory are free?
void mm_init()
initialize memory management
void mm_reaper()
free all blocks allocated by the current process
size_t mm_start
end of kernel code + data
#define MM_BLOCK_FREE(addr)
memory from addr on can be allocated
Definition: mm.h:68
#define MM_SPLIT_THRESH
split off if 8+ data bytes
Definition: mm.h:54
#define MM_BLOCK_RESERVED(addr)
memory from addr on is reserved
Definition: mm.h:79
size_t * mm_first_free
ptr to first free block.
#define MM_HEADER_SIZE
2 words header: pid, size
Definition: mm.h:53
#define MM_FREE
marker: block free
Definition: mm.h:47
Interface: reduced standard C library.
void * calloc(size_t nmemb, size_t size)
allocate and return pointer to initialized memory
void * malloc(size_t size)
allocate and return pointer to uninitialized memory
void free(void *ptr)
return the allocated memory to memory management.
Interface: string functions.
void * memset(void *s, int c, size_t n)
fill memory block with a byte value.
Interface: kernel level critical sections.
#define ENTER_KERNEL_CRITICAL_SECTION()
Definition: critsec.h:41
#define LEAVE_KERNEL_CRITICAL_SECTION()
Definition: critsec.h:42
Internal Interface: task management.
tdata_t * ctid
ptr to current process data
signed int tid_t
task id type
Definition: tm.h:143

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

Generated for brickOS Kernel Developer by doxygen 1.9.4