UbixOS V2 2.0

kmalloc.c
Go to the documentation of this file.
1 /*-
2 * Copyright (c) 2002-2018 The UbixOS Project.
3 * All rights reserved.
4 *
5 * This was developed by Christopher W. Olsen for the UbixOS Project.
6 *
7 * Redistribution and use in source and binary forms, with or without modification, are permitted
8 * provided that the following conditions are met:
9 *
10 * 1) Redistributions of source code must retain the above copyright notice, this list of
11 * conditions, the following disclaimer and the list of authors.
12 * 2) Redistributions in binary form must reproduce the above copyright notice, this list of
13 * conditions, the following disclaimer and the list of authors in the documentation and/or
14 * other materials provided with the distribution.
15 * 3) Neither the name of the UbixOS Project nor the names of its contributors may be used to
16 * endorse or promote products derived from this software without specific prior written
17 * permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED
20 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
21 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
22 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
26 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include <lib/kmalloc.h>
30 #include <lib/kprintf.h>
31 #include <ubixos/kpanic.h>
32 #include <ubixos/sched.h>
33 #include <ubixos/spinlock.h>
34 #include <vmm/vmm.h>
35 #include <string.h>
36 #include <assert.h>
37 #include <sys/types.h>
38
39 /*
40 Set up three descriptor tables:
41
42 kernDesc - The inuse descriptor table
43 freeKernDesc - The free descriptor table (descriptors with memory backing just not in use)
44 emptyKernDesc - The empty descriptor table (descriptors with out a memory backing)
45
46 */
47 static struct memDescriptor *usedKernDesc = 0x0;
48 static struct memDescriptor *freeKernDesc = 0x0;
49 static struct memDescriptor *emptyKernDesc = 0x0;
50
51 /*
52 Set up our spinlocks so we do not corrupt linked lists if we have re-entrancy
53 */
54 static struct spinLock mallocSpinLock = SPIN_LOCK_INITIALIZER;
55 static struct spinLock emptyDescSpinLock = SPIN_LOCK_INITIALIZER;
56
57 /************************************************************************
58
59 Function: void *getEmptyDesc()
60 Description: Find An Empty Descriptor
61
62 Notes:
63
64 02/17/03 - Is This Efficient?
65
66 ************************************************************************/
67 static void *getEmptyDesc() {
68 int i = 0x0;
69 struct memDescriptor *tmpDesc = 0x0;
70
71 spinLock(&emptyDescSpinLock);
72
73 tmpDesc = emptyKernDesc;
74
75 if (tmpDesc != 0x0) {
76 emptyKernDesc = tmpDesc->next;
77 if (emptyKernDesc != 0x0)
78 emptyKernDesc->prev = 0x0;
79
80 tmpDesc->next = 0x0;
81 tmpDesc->prev = 0x0;
82 spinUnlock(&emptyDescSpinLock);
83 return (tmpDesc);
84 }
85 if ((emptyKernDesc = (struct memDescriptor *) vmm_getFreeMallocPage(4)) == 0x0)
86 kpanic("Error: vmmGetFreeKernelPage returned NULL\n");
87
88 /* zero out the memory so we know there is no garbage */
89 memset(emptyKernDesc, 0x0, 0x4000);
90
91 emptyKernDesc[0].next = &emptyKernDesc[1];
92
93 for (i = 0x1; i < ((0x4000 / sizeof(struct memDescriptor))); i++) {
94 if (i + 1 < (0x4000 / sizeof(struct memDescriptor)))
95 emptyKernDesc[i].next = &emptyKernDesc[i + 1];
96 else
97 emptyKernDesc[i].next = 0x0;
98 emptyKernDesc[i].prev = &emptyKernDesc[i - 1];
99 }
100
101 tmpDesc = &emptyKernDesc[0];
102
103 emptyKernDesc = tmpDesc->next;
104 emptyKernDesc->prev = 0x0;
105 tmpDesc->next = 0x0;
106 tmpDesc->prev = 0x0;
107 spinUnlock(&emptyDescSpinLock);
108 return (tmpDesc);
109 }
110
111 /************************************************************************
112
113 Function: void insertFreeDesc(struct memDescriptor *freeDesc)
114 Description: This Function Inserts A Free Descriptor On The List Which Is
115 Kept In Size Order
116
117 Notes:
118
119 02/17/03 - This Was Inspired By TCA's Great Wisdom -
120 "[20:20:59] <TCA> You should just insert it in order"
121
122 ************************************************************************/
123 static int insertFreeDesc(struct memDescriptor *freeDesc) {
124 struct memDescriptor *tmpDesc = 0x0;
125 assert(freeDesc);
126
127 if (freeDesc->limit <= 0x0)
128 kpanic("Inserting Descriptor with no limit\n");
129
130 if (freeKernDesc != 0x0) {
131
132 #if 0
133 freeDesc->next = freeKernDesc;
134 freeDesc->prev = 0x0;
135 freeKernDesc->prev = freeDesc;
136 freeKernDesc = freeDesc;
137 #endif
138
139 for (tmpDesc = freeKernDesc; tmpDesc != 0x0; tmpDesc = tmpDesc->next) {
140 if (freeDesc->limit <= tmpDesc->limit) {
141
142 freeDesc->prev = tmpDesc->prev;
143 if (tmpDesc->prev != 0x0)
144 tmpDesc->prev->next = freeDesc;
145
146 tmpDesc->prev = freeDesc;
147 freeDesc->next = tmpDesc;
148
149 if (tmpDesc == freeKernDesc)
150 freeKernDesc = freeDesc;
151 return (0x0);
152 }
153 if (tmpDesc->next == 0x0) {
154 tmpDesc->next = freeDesc;
155 freeDesc->prev = tmpDesc;
156 freeDesc->next = 0x0;
157 return (0x0);
158 }
159 }
160 kpanic("didnt Insert\n");
161 return (0x0);
162 }
163 else {
164 freeDesc->prev = 0x0;
165 freeDesc->next = 0x0;
166 freeKernDesc = freeDesc;
167 return (0x0);
168 }
169
170 return (0x1);
171 }
172
173 /************************************************************************
174
175 Function: void mergeMemBlocks()
176 Description: This Function Will Merge Free Blocks And Free Pages
177
178 Notes:
179
180 03/05/03 - We Have A Problem It Seems The First Block Is Limit 0x0
181
182 ************************************************************************/
183 #ifdef _IGNORE
184 static void mergeMemBlocks() {
185 struct memDescriptor *tmpDesc1 = 0x0;
186 struct memDescriptor *tmpDesc2 = 0x0;
187 uInt32 baseAddr = 0x0;
188
189 return;
190
191 //Loop The Free Descriptors See If We Can Merge Them
192 mergeStart: for (tmpDesc1 = freeKernDesc; tmpDesc1 != 0x0; tmpDesc1 = tmpDesc1->next) {
193 /*
194 Compare The Base Addr With The Other Descriptors If You Find The One
195 That You Are Looking For Lets Merge Them
196 */
197 if (tmpDesc1->limit != 0x0) {
198 baseAddr = (uInt32) tmpDesc1->baseAddr + (uInt32) tmpDesc1->limit;
199 for (tmpDesc2 = freeKernDesc; tmpDesc2; tmpDesc2 = tmpDesc2->next) {
200 if ((uInt32) tmpDesc2->baseAddr == baseAddr) {
201 tmpDesc1->limit += tmpDesc2->limit;
202 tmpDesc2->baseAddr = 0x0;
203 tmpDesc2->limit = 0x0;
204 if (tmpDesc2->prev) {
205 tmpDesc2->prev->next = tmpDesc2->next;
206 }
207 if (tmpDesc2->next) {
208 tmpDesc2->next->prev = tmpDesc2->prev;
209 }
210 tmpDesc2->prev = 0x0;
211 tmpDesc2->next = emptyKernDesc;
212 emptyKernDesc->prev = tmpDesc2;
213 emptyKernDesc = tmpDesc2;
214 if (tmpDesc1->prev) {
215 tmpDesc1->prev->next = tmpDesc1->next;
216 }
217 if (tmpDesc1->next) {
218 tmpDesc1->next->prev = tmpDesc1->prev;
219 }
220 tmpDesc1->prev = 0x0;
221 tmpDesc1->next = 0x0;
222 kprintf("mergememBlocks: [%i]\n", tmpDesc1->limit);
223 insertFreeDesc(tmpDesc1);
224 //tmpDesc1 = freeKernDesc;
225 goto mergeStart;
226 break;
227 }
228 }
229 }
230 }
231 return;
232 }
233 #endif
234
235 /************************************************************************
236
237 Function: void *kmalloc(uInt32 len)
238 Description: Allocate Kernel Memory
239
240 Notes:
241
242 02/17/03 - Do I Still Need To Pass In The Pid?
243
244 ************************************************************************/
245 void *kmalloc(uInt32 len) {
246 struct memDescriptor *tmpDesc1 = 0x0;
247 struct memDescriptor *tmpDesc2 = 0x0;
248 char *buf = 0x0;
249 int i = 0x0;
250 uInt16 pages = 0x0;
251
252 spinLock(&mallocSpinLock);
253
254 len = MALLOC_ALIGN(len);
255
256 if (len == 0x0) {
257 spinUnlock(&mallocSpinLock);
258 kprintf("kmalloc: len = 0!\n");
259 return (0x0);
260 }
261 for (tmpDesc1 = freeKernDesc; tmpDesc1 != 0x0; tmpDesc1 = tmpDesc1->next) {
262 assert(tmpDesc1);
263 if (tmpDesc1->limit >= len) {
264 if (tmpDesc1->prev != 0x0)
265 tmpDesc1->prev->next = tmpDesc1->next;
266 if (tmpDesc1->next != 0x0)
267 tmpDesc1->next->prev = tmpDesc1->prev;
268
269 if (tmpDesc1 == freeKernDesc)
270 freeKernDesc = tmpDesc1->next;
271
272 tmpDesc1->prev = 0x0;
273 tmpDesc1->next = usedKernDesc;
274 if (usedKernDesc != 0x0)
275 usedKernDesc->prev = tmpDesc1;
276 usedKernDesc = tmpDesc1;
277 if (tmpDesc1->limit > len) {
278 tmpDesc2 = getEmptyDesc();
279 assert(tmpDesc2);
280 tmpDesc2->limit = tmpDesc1->limit - len;
281 tmpDesc1->limit = len;
282 tmpDesc2->baseAddr = tmpDesc1->baseAddr + len;
283 tmpDesc2->next = 0x0;
284 tmpDesc2->prev = 0x0;
285 insertFreeDesc(tmpDesc2);
286 }
287 buf = (char *) tmpDesc1->baseAddr;
288 for (i = 0; i < tmpDesc1->limit; i++) {
289 buf[i] = (char) 0x0;
290 }
291 spinUnlock(&mallocSpinLock);
292 //kprintf("m1[%i:%i:0x%X]",tmpDesc1->limit,len,tmpDesc1->baseAddr);
293 assert(tmpDesc1->baseAddr);
294 return (tmpDesc1->baseAddr);
295 }
296 }
297 tmpDesc1 = getEmptyDesc();
298 //kprintf("no empty desc\n");
299 if (tmpDesc1 != 0x0) {
300 pages = ((len + 4095) / 4096);
301 tmpDesc1->baseAddr = (struct memDescriptor *) vmm_getFreeMallocPage(pages);
302 tmpDesc1->limit = len;
303 tmpDesc1->next = usedKernDesc;
304 tmpDesc1->prev = 0x0;
305 if (usedKernDesc != 0x0)
306 usedKernDesc->prev = tmpDesc1;
307 usedKernDesc = tmpDesc1;
308
309 if (((pages * 4096) - len) > 0x0) {
310 tmpDesc2 = getEmptyDesc();
311 assert(tmpDesc2);
312 tmpDesc2->baseAddr = tmpDesc1->baseAddr + tmpDesc1->limit;
313 tmpDesc2->limit = ((pages * 4096) - len);
314 tmpDesc2->prev = 0x0;
315 tmpDesc2->next = 0x0;
316 if (tmpDesc2->limit <= 0x0)
317 kprintf("kmalloc-2 tmpDesc2: [%i]\n", tmpDesc2->limit);
318 insertFreeDesc(tmpDesc2);
319 }
320
321 buf = (char *) tmpDesc1->baseAddr;
322 for (i = 0; i < tmpDesc1->limit; i++) {
323 buf[i] = (char) 0x0;
324 }
325 spinUnlock(&mallocSpinLock);
326 //kprintf("baseAddr2[0x%X:0x%X]",tmpDesc1,tmpDesc1->baseAddr);
327 //kprintf("m2[%i:%i:0x%X]",tmpDesc1->limit,len,tmpDesc1->baseAddr);
328 assert(tmpDesc1->baseAddr);
329 return (tmpDesc1->baseAddr);
330 }
331 //Return Null If Unable To Malloc
332 spinUnlock(&mallocSpinLock);
333 //kprintf("baseAddr3[0x0]");
334 return (0x0);
335 }
336
337 /************************************************************************
338
339 Function: void kfree(void *baseAddr)
340 Description: This Will Find The Descriptor And Free It
341
342 Notes:
343
344 02/17/03 - I need To Make It Join Descriptors
345
346 ************************************************************************/
347 void kfree(void *baseAddr) {
348 struct memDescriptor *tmpDesc = 0x0;
349
350 if (baseAddr == 0x0)
351 return;
352 assert(baseAddr);
353
354 assert(usedKernDesc);
355 spinLock(&mallocSpinLock);
356
357 for (tmpDesc = usedKernDesc; tmpDesc != 0x0; tmpDesc = tmpDesc->next) {
358
359 if (tmpDesc->baseAddr == baseAddr) {
360 memset(tmpDesc->baseAddr, 0xBE, tmpDesc->limit);
361
362 if (usedKernDesc == tmpDesc)
363 usedKernDesc = tmpDesc->next;
364
365 if (tmpDesc->prev != 0x0)
366 tmpDesc->prev->next = tmpDesc->next;
367
368 if (tmpDesc->next != 0x0)
369 tmpDesc->next->prev = tmpDesc->prev;
370
371 tmpDesc->next = 0x0;
372 tmpDesc->prev = 0x0;
373
374 if (tmpDesc->limit <= 0x0)
375 kprintf("kfree tmpDesc1: [%i]\n", tmpDesc->limit);
376 //kprintf("{0x%X}",tmpDesc->baseAddr);
377 insertFreeDesc(tmpDesc);
378
379 // mergeMemBlocks();
380 spinUnlock(&mallocSpinLock);
381 return;
382 }
383 }
384 spinUnlock(&mallocSpinLock);
385 kprintf("Kernel: Error Freeing Descriptor! [0x%X]\n", (uInt32) baseAddr);
386 return;
387 }
388
389 /***
390 $Log: kmalloc.c,v $
391 Revision 1.3 2006/12/05 14:10:21 reddawg
392 Workign Distro
393
394 Revision 1.2 2006/10/06 15:48:01 reddawg
395 Starting to make ubixos work with UFS2
396
397 Revision 1.1.1.1 2006/06/01 12:46:16 reddawg
398 ubix2
399
400 Revision 1.4 2006/06/01 12:42:09 reddawg
401 Getting back to the basics
402
403 Revision 1.3 2006/06/01 03:58:33 reddawg
404 wondering about this stuff here
405
406 Revision 1.2 2005/10/12 00:13:37 reddawg
407 Removed
408
409 Revision 1.1.1.1 2005/09/26 17:24:11 reddawg
410 no message
411
412 Revision 1.35 2005/08/04 18:32:59 fsdfs
413
414 added error reporting
415
416 Revision 1.34 2005/08/04 18:23:41 reddawg
417 BUG: Assert has issues that must be looked into
418
419 Revision 1.33 2005/08/04 17:11:11 fsdfs
420
421 ----------------------------------------
422
423 -------------------
424
425 Revision 1.32 2004/09/28 21:50:04 reddawg
426 kmalloc: now when we kfree memory is filled with 0xBE so it is easy to debug if we continue to use free'd memory
427
428 Revision 1.31 2004/09/19 16:17:25 reddawg
429 fixed memory leak we now lose no memory....
430
431 Revision 1.30 2004/09/14 21:51:24 reddawg
432 Debug info
433
434 Revision 1.29 2004/09/11 23:39:31 reddawg
435 ok time for bed
436
437 Revision 1.28 2004/09/11 23:21:26 reddawg
438 run now do you get fegfaults with BB?
439
440 Revision 1.27 2004/09/11 22:49:28 reddawg
441 pat look at lines 276-285 does the math seem right?
442
443 Revision 1.26 2004/09/11 22:33:13 reddawg
444 minor changes
445
446 Revision 1.25 2004/09/11 12:11:11 reddawg
447 Cleaning up the VFS more changes to follow...
448
449 Revision 1.24 2004/09/08 23:19:58 reddawg
450 hmm
451
452 Revision 1.23 2004/09/06 15:13:25 reddawg
453 Last commit before FreeBSD 6.0
454
455 Revision 1.22 2004/08/26 22:51:18 reddawg
456 TCA touched me :( i think he likes men....
457
458
459 sched.h: kTask_t added parentPid
460 endtask.c: fixed term back to parentPid
461 exec.c: cleaned warnings
462 fork.c: fixed term to childPid
463 sched.c: clean up for dead tasks
464 systemtask.c: clean up dead tasks
465 kmalloc.c: cleaned up warnings
466 udp.c: cleaned up warnings
467 bot.c: cleaned up warnings
468 shell.c: cleaned up warnings
469 tcpdump.c: took a dump
470 hd.c: cleaned up warnings
471 ubixfs.c: stopped prning debug info
472
473 Revision 1.21 2004/07/28 15:05:43 reddawg
474 Major:
475 Pages now have strict security enforcement.
476 Many null dereferences have been resolved.
477 When apps loaded permissions set for pages rw and ro
478
479 Revision 1.20 2004/07/28 00:17:05 reddawg
480 Major:
481 Disconnected page 0x0 from the system... Unfortunately this broke many things
482 all of which have been fixed. This was good because nothing deferences NULL
483 any more.
484
485 Things affected:
486 malloc,kmalloc,getfreepage,getfreevirtualpage,pagefault,fork,exec,ld,ld.so,exec,file
487
488 Revision 1.19 2004/07/26 19:15:49 reddawg
489 test code, fixes and the like
490
491 Revision 1.18 2004/07/26 16:52:45 reddawg
492 here we go
493
494 Revision 1.17 2004/07/24 23:04:44 reddawg
495 Changes... mark let me know if you fault at pid 185 when you type stress
496
497 Revision 1.16 2004/07/21 10:02:09 reddawg
498 devfs: renamed functions
499 device system: renamed functions
500 fdc: fixed a few potential bugs and cleaned up some unused variables
501 strol: fixed definition
502 endtask: made it print out freepage debug info
503 kmalloc: fixed a huge memory leak we had some unhandled descriptor insertion so some descriptors were lost
504 ld: fixed a pointer conversion
505 file: cleaned up a few unused variables
506 sched: broke task deletion
507 kprintf: fixed ogPrintf definition
508
509 Revision 1.15 2004/07/20 23:20:50 reddawg
510 kmalloc: forgot to remove an assert
511
512 Revision 1.14 2004/07/20 23:18:11 reddawg
513 Made malloc a little more robust but we have a serious memory leak somewhere
514
515 Revision 1.13 2004/07/20 22:29:55 reddawg
516 assert: remade assert
517
518 Revision 1.12 2004/07/20 18:58:24 reddawg
519 Few fixes
520
521 Revision 1.11 2004/07/18 05:24:15 reddawg
522 Fixens
523
524 Revision 1.10 2004/07/17 18:00:47 reddawg
525 kmalloc: added assert()
526
527 Revision 1.9 2004/07/17 15:54:52 reddawg
528 kmalloc: added assert()
529 bioscall: fixed some potential problem by not making 16bit code
530 paging: added assert()
531
532 Revision 1.8 2004/06/17 14:50:32 reddawg
533 kmalloc: converted some variables to static
534
535 Revision 1.7 2004/06/17 02:54:54 flameshadow
536 chg: fixed cast
537
538 Revision 1.6 2004/05/26 11:56:51 reddawg
539 kmalloc: fixed memrgeMemBlocks hopefully it will prevent future segfault issues
540 by not having any more overlapping blocks
541
542 Revision 1.5 2004/05/25 14:01:14 reddawg
543 Implimented Better Spinlocking No More Issues With KMALLOC which actually
544 was causing bizzare problems
545
546 END
547 ***/
548
spinlock.h
uInt32
unsigned long int uInt32
Definition: objgfx30.h:49
string.h
memDescriptor::baseAddr
void * baseAddr
Definition: kmalloc.h:45
uInt16
unsigned short int uInt16
Definition: objgfx30.h:48
memDescriptor::prev
struct memDescriptor * prev
Definition: kmalloc.h:43
assert
#define assert(e)
Definition: assert.h:64
assert.h
spinUnlock
void spinUnlock(spinLock_t *lock)
Definition: spinlock.c:36
vmm.h
SPIN_LOCK_INITIALIZER
#define SPIN_LOCK_INITIALIZER
Definition: spinlock.h:36
sched.h
kpanic
void kpanic(const char *fmt,...)
print panic message and halt system
Definition: kpanic.c:41
types.h
kmalloc
void * kmalloc(uInt32 len)
Definition: kmalloc.c:241
spinLock
void spinLock(spinLock_t *lock)
Definition: spinlock.c:55
MALLOC_ALIGN
#define MALLOC_ALIGN(size)
Definition: kmalloc.h:40
kpanic.h
kfree
void kfree(void *baseAddr)
Definition: kmalloc.c:342
memDescriptor::next
struct memDescriptor * next
Definition: kmalloc.h:44
kprintf.h
buf
Definition: buf.h:35
memDescriptor::limit
uInt32 limit
Definition: kmalloc.h:46
vmm_getFreeMallocPage
void * vmm_getFreeMallocPage(uint16_t count)
spinLock
Definition: spinlock.h:41
memset
void * memset(void *dst, int c, size_t length)
kprintf
int kprintf(const char *,...)
Definition: kprintf.c:259
kmalloc.h
memDescriptor
Definition: kmalloc.h:42