Root/kernel/memory.ccp

1#pypp 0
2// Iris: micro-kernel for a capability-based operating system.
3// memory.ccp: Page allocation system.
4// Copyright 2009 Bas Wijnen <wijnen@debian.org>
5//
6// This program is free software: you can redistribute it and/or modify
7// it under the terms of the GNU General Public License as published by
8// the Free Software Foundation, either version 3 of the License, or
9// (at your option) any later version.
10//
11// This program is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15//
16// You should have received a copy of the GNU General Public License
17// along with this program. If not, see <http://www.gnu.org/licenses/>.
18
19#include "kernel.hh"
20//#define DEBUG_ALLOC
21
22extern unsigned _end
23
24static void clear_page (unsigned page, unsigned num = 1):
25    #ifdef DEBUG_ALLOC
26    kdebug ("clearing page ")
27    kdebug_num (page)
28    kdebug ("+")
29    kdebug_num (num << PAGE_BITS)
30    kdebug ('\n')
31    #endif
32    page = (page & ~0xc0000000) | 0xa0000000
33    for unsigned p = 0; p < num; ++p:
34        arch_uncache_page (page - 0x20000000 + (p << PAGE_BITS))
35        for unsigned i = 0; i < (1 << (PAGE_BITS - 2)); ++i:
36            // Clear page.
37            ((unsigned *)page)[(p << PAGE_BITS - 2) + i] = 0
38    if *(unsigned *)page != 0 || ((unsigned *)page)[(num << (PAGE_BITS - 2)) - 1] != 0:
39        kdebug_num ((num << (PAGE_BITS - 2)) - 1)
40        kdebug ("/")
41        kdebug_num (((unsigned *)page)[(num << (PAGE_BITS - 2)) - 1])
42        kdebug (",")
43        kdebug_num (*(unsigned *)page)
44        kdebug ("\n")
45        dpanic (0, "clear_page didn't work")
46
47#if 0
48
49static unsigned free_begin
50static unsigned free_end
51
52unsigned init_memory (unsigned mem):
53    free_begin = ((unsigned)&_end + ~PAGE_MASK) & PAGE_MASK
54    free_end = (0x80000000 + mem) & PAGE_MASK
55    return (free_end - free_begin) >> PAGE_BITS
56
57unsigned phys_alloc (unsigned num):
58    if free_begin + num * PAGE_SIZE > free_end:
59        kdebug ("memory allocation failed\n")
60        return 0
61    unsigned ret = free_begin
62    free_begin += num * PAGE_SIZE
63    clear_page (ret, num)
64    return ret
65
66void phys_free (unsigned page, unsigned num):
67    // Not supported.
68
69#ifndef NDEBUG
70/*void check_impl (kObject *o, unsigned num, char const *msg):
71// for ; o; o = (kObject *)o->next:
72// if (unsigned)o >= (unsigned)free_begin && (unsigned)o < (unsigned)free_end:
73*/ // panic (num, msg)
74bool check_free (kObject *o, unsigned size):
75    return true
76void print_free ():
77#endif
78#else
79
80struct kFreePages:
81    kFreePages *prev, *next
82    unsigned num
83
84static kFreePages *first_free
85
86unsigned init_memory (unsigned mem):
87    first_free = (kFreePages *)(((unsigned)&_end + ~PAGE_MASK) & PAGE_MASK)
88    first_free->prev = NULL
89    first_free->next = NULL
90    first_free->num = ((mem & PAGE_MASK) - ((unsigned)first_free & ~0xc0000000)) >> PAGE_BITS
91    #ifdef DEBUG_ALLOC
92    kdebug ("initial memory: ")
93    kdebug_num ((unsigned)first_free & ~0xc0000000)
94    kdebug ("+")
95    kdebug_num (first_free->num)
96    kdebug ("\n")
97    #endif
98    return first_free->num
99
100#ifdef DEBUG_ALLOC
101static bool is_free (unsigned page):
102    for kFreePages *p = first_free; p; p = p->next:
103        if page >= (unsigned)p && page < (unsigned)p + (p->num << PAGE_BITS):
104            return true
105    return false
106#endif
107
108unsigned phys_alloc (unsigned num):
109    kFreePages *choice = NULL
110    for kFreePages *p = first_free; p; p = p->next:
111        if p->num < num:
112            continue
113        if choice && choice->num < p->num:
114            continue
115        if p->num == num:
116            if p->prev:
117                p->prev->next = p->next
118            else:
119                first_free = p->next
120            if p->next:
121                p->next->prev = p->prev
122            clear_page ((unsigned)p, num)
123            #ifdef DEBUG_ALLOC
124            kdebug ("allocating ")
125            kdebug_num ((unsigned)p & ~0xc0000000)
126            kdebug ("+")
127            kdebug_num (num << PAGE_BITS)
128            kdebug ("\n")
129            if is_free ((unsigned)p):
130                panic ((unsigned)p, "page still free after allocation")
131            #endif
132            return (unsigned)p
133        choice = p
134    if !choice:
135        // TODO: reorganizing may work to allow allocation.
136        dpanic (0x03948859, "range memory allocation failed")
137        return 0
138    choice->num -= num
139    unsigned ret = (unsigned)choice + (choice->num << PAGE_BITS)
140    clear_page (ret, num)
141    #ifdef DEBUG_ALLOC
142    kdebug ("allocating ")
143    kdebug_num (ret & ~0xc0000000)
144    kdebug ("+")
145    kdebug_num (num << PAGE_BITS)
146    kdebug ("\n")
147    if is_free (ret):
148        panic (ret, "page still free after allocation")
149    #endif
150    return ret
151
152void phys_free (unsigned page, unsigned num):
153    #ifdef DEBUG_ALLOC
154    kdebug ("free ")
155    kdebug_num (page & ~0xc0000000)
156    kdebug ("+")
157    kdebug_num (num << PAGE_BITS)
158    kdebug ("\n")
159    if is_free (page):
160        panic (page, "page already free")
161    #endif
162    unsigned size = num << PAGE_BITS
163    if !first_free || (unsigned)first_free > page:
164        // This is the first free block.
165        kFreePages *n = (kFreePages *)page
166        n->prev = NULL
167        if (unsigned)first_free == page + size:
168            // It fits exactly before the previous first free block.
169            n->next = first_free->next
170            n->num = num + first_free->num
171        else:
172            // It is a new block.
173            n->next = first_free
174            n->num = num
175        first_free = n
176        if n->next:
177            n->next->prev = n
178        return
179    kFreePages *p
180    for p = first_free; p->next && (unsigned)p->next < page; p = p->next:
181        // Do nothing.
182        if p == p->next:
183            dpanic (0, "page is its own next")
184    // The new block should be inserted directly after p.
185    if (unsigned)p->next == page + size:
186        // It can be merged with the block after it: do that.
187        kFreePages *n = (kFreePages *)page
188        n->prev = p
189        n->next = p->next->next
190        if n->next:
191            n->next->prev = n
192        n->num = num + p->next->num
193        p->next = n
194        if (unsigned)p + (p->num << PAGE_BITS) == (unsigned)n:
195            // It can also be merged with the page before it: do that as well.
196            p->num += n->num
197            p->next = n->next
198            if p->next:
199                p->next->prev = p
200        return
201    // The new block cannot be merged with the block after it.
202    if (unsigned)p + (p->num << PAGE_BITS) == page:
203        // But it can be merged with the one before it: do that.
204        p->num += num
205        return
206    // The new block cannot be merged at all.
207    kFreePages *n = (kFreePages *)page
208    n->next = p->next
209    n->prev = p
210    if n->next:
211        n->next->prev = n
212    p->next = n
213    n->num = num
214
215#ifndef NDEBUG
216bool check_free (kObject *o, unsigned size):
217    for kFreePages *p = first_free; p; p = p->next:
218        if (unsigned)o + size > (unsigned)p && (unsigned)o < (unsigned)p + p->num * PAGE_SIZE:
219            return false
220    return true
221
222void print_free ():
223    kdebug ("Free pages: ")
224    for kFreePages *p = first_free; p; p = p->next:
225        kdebug_num ((unsigned)p)
226        kdebug (":")
227        kdebug_num (p->num, 4)
228        kdebug ("->")
229    kdebug ("NULL\n")
230#endif
231#endif
232
233#ifndef NDEBUG
234void check_memory (kMemory *mem, unsigned num, char const *msg):
235    check_impl (mem->pages, num, msg)
236    check_impl (mem->threads, num, msg)
237    check_impl (mem->receivers, num, msg)
238    for kReceiver *r = mem->receivers; r; r = (kReceiver *)r->next:
239        check_impl (r->messages, num, msg)
240    check_impl (mem->capses, num, msg)
241    check_impl (mem->memories, num, msg)
242    for kMemory *m = mem->memories; m; m = (kMemory *)m->next:
243        check_memory (m, num, msg)
244
245void check (unsigned num, char const *msg):
246    check_memory (&top_memory, num, msg)
247    top_memory.check (num)
248#endif
249
250unsigned raw_zalloc ():
251    return phys_alloc (1)
252
253void raw_pfree (unsigned page):
254    return phys_free (page, 1)
255
256unsigned kMemory::zalloc ():
257    if !use ():
258        dpanic (0x34638920, "limit reached: allocation not allowed")
259        kdebug ("limit reached: allocation not allowed\n")
260        return NULL
261    return raw_zalloc ()
262
263void kMemory::pfree (unsigned page):
264    unuse ()
265    return raw_pfree (page)
266
267unsigned kMemory::palloc ():
268    return zalloc ()
269
270void kMemory::zfree (unsigned page):
271    pfree (page)
272

Archive Download this file

Branches:
master



interactive