annotate cos/kernel/malloc.c @ 299:674789d9ff37

Added a doc
author Windel Bouwman
date Sun, 01 Dec 2013 18:37:23 +0100
parents 24ce177e01e8
children
rev   line source
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
1 #include "kernel.h"
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
2
28
47b7df514243 Moved Makefiles
windel
parents: 26
diff changeset
3 // ================= Placement malloc:
29
7e3bdcb391dc Added get_page function to mm
windel
parents: 28
diff changeset
4 // Assume here that nothing gets ever kfree'd. This makes it simple!
7e3bdcb391dc Added get_page function to mm
windel
parents: 28
diff changeset
5
7e3bdcb391dc Added get_page function to mm
windel
parents: 28
diff changeset
6 uint64_t placement_address = (uint64_t)&kernel_end;
28
47b7df514243 Moved Makefiles
windel
parents: 26
diff changeset
7
47b7df514243 Moved Makefiles
windel
parents: 26
diff changeset
8 // ================= Other malloc
47b7df514243 Moved Makefiles
windel
parents: 26
diff changeset
9 // TODO: move this to user space?
47b7df514243 Moved Makefiles
windel
parents: 26
diff changeset
10
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
11 #define HEAP_MAGIC 0xc0ffee
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
12 #define HEAP_INUSE 1
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
13 #define HEAP_FREE 0
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
14
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
15 /*
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
16 malloc and free divide the chunks of memory present at the heap
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
17 of the kernel into smaller parts.
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
18 The heap is located at: 0x
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
19 */
28
47b7df514243 Moved Makefiles
windel
parents: 26
diff changeset
20
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
21 static heap_t* kernel_heap = 0;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
22
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
23 void expand_heap(heap_t *heap, uint64_t newsize);
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
24
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
25 /* Allocates 'size' bytes and returns the pointer if succesfull.
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
26 Before the kernel is initialized, placement malloc is used.
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
27 Kernelpanic in case of failure..
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
28 */
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
29 static void* kmalloc_int(uint64_t size, uint64_t aligned)
26
dcce92b1efbc Added mm.c
windel
parents: 25
diff changeset
30 {
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
31 // Check if there exists a kernel heap. If not, use placement malloc for now.
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
32 if (kernel_heap == 0)
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
33 {
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
34 // Before that the heap is initialized, use placement malloc
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
35 if (aligned == 1)
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
36 {
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
37 // Align placement address
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
38 if ( (placement_address | 0xFFF) != 0 )
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
39 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
40 placement_address &= ~(0xFFF);
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
41 placement_address += 0x1000;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
42 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
43 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
44 uint64_t tmp = placement_address;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
45 placement_address += size;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
46 return (void*)tmp;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
47 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
48 else
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
49 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
50 // We have a kernel heap, search the heap for a block of suitable size.
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
51
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
52 // Start at the beginning of our heap and search a free block:
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
53 heap_header_t *current = kernel_heap->first_block;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
54 while (current->magic == HEAP_MAGIC)
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
55 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
56 if ((current->state == HEAP_FREE) && (current->size >= size))
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
57 {
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
58 // We found a hole with suitable size. Determine if split is of any use.
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
59
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
60 // Insert a heap header if required:
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
61 if (current->size > size + sizeof(heap_t) + 1)
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
62 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
63 // Calculate location of the inserted header:
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
64 heap_header_t *newheader = (heap_header_t*) (((uint64_t)current)+size+sizeof(heap_header_t));
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
65
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
66 // Set the new header fields:
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
67 newheader->size = current->size - size - sizeof(heap_header_t);
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
68 newheader->state = HEAP_FREE;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
69 newheader->magic = HEAP_MAGIC;
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
70
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
71 // Set the size of this block
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
72 current->size = size;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
73 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
74 else
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
75 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
76 // We allocate this whole block
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
77 // Mark block as used:
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
78 current->state = HEAP_INUSE;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
79 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
80 // Calculate the size of the block:
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
81 char *address = ((char*)current)+sizeof(heap_header_t);
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
82 return address;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
83
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
84 }
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
85 // Goto next heap block:
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
86 current = (heap_header_t*)(((uint64_t) current) + current->size + sizeof(heap_header_t));
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
87 }
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
88
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
89 // We did not find a block large enough. Expand the heap and try again.
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
90 expand_heap(kernel_heap, 0x10000000);
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
91 return kmalloc_int(size, aligned);
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
92 }
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
93 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
94
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
95 // Convenient wrappers:
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
96 void* kmalloc(uint64_t size)
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
97 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
98 return kmalloc_int(size, 0);
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
99 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
100
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
101 void* kmalloc_a(uint64_t size)
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
102 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
103 return kmalloc_int(size, 1);
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
104 }
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
105
26
dcce92b1efbc Added mm.c
windel
parents: 25
diff changeset
106 void kfree(void* ptr)
dcce92b1efbc Added mm.c
windel
parents: 25
diff changeset
107 {
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
108 printf("Free address %x\n", ptr);
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
109 if (kernel_heap == 0)
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
110 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
111 return;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
112 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
113 else
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
114 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
115 // TODO
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
116 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
117 // TODO: free blocks:
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
118 }
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
119
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
120 heap_t* create_heap(uint64_t location, uint64_t size)
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
121 {
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
122 // Make sure that the new heap location is mapped into the address space:
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
123 uint64_t i = 0;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
124 while (i < size)
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
125 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
126 alloc_frame( get_page(location + i, kernel_map));
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
127 i += 0x1000;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
128 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
129
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
130 // create new heap structure:
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
131 heap_t* h = (heap_t*)kmalloc(sizeof(heap_t));
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
132
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
133 // Create one big hole:
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
134 h->first_block = (heap_header_t*)location; // Place header at beginning of heap
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
135 h->first_block->magic = HEAP_MAGIC;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
136 h->first_block->state = HEAP_FREE;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
137 h->first_block->size = size - sizeof(heap_header_t);
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
138 return h;
24
d8627924d40d Split up in more files and reboot command
windel
parents:
diff changeset
139 }
25
d3c4bf3720a3 Beginning of multitasking
windel
parents: 24
diff changeset
140
40
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
141 // Make the total heap bigger:
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
142 void expand_heap(heap_t *heap, uint64_t newsize)
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
143 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
144 uint64_t oldsize = heap->end_address - heap->start_address;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
145 if (newsize < oldsize)
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
146 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
147 panic("Cannot expand heap to a smaller size\n");
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
148 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
149
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
150 uint64_t i = oldsize;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
151 while (i < newsize)
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
152 {
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
153 alloc_frame( get_page(heap->start_address + i, kernel_map));
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
154 i += 0x1000;
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
155 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
156 }
24ce177e01e8 Added more malloc stuff. Added mem usage
windel
parents: 29
diff changeset
157