Statistics
| Branch: | Revision:

scoutos / prex-0.9.0 / sys / mem / page.c @ 03e9c04a

History | View | Annotate | Download (7.22 KB)

1
/*-
2
 * Copyright (c) 2005-2009, Kohsuke Ohtani
3
 * All rights reserved.
4
 *
5
 * Redistribution and use in source and binary forms, with or without
6
 * modification, are permitted provided that the following conditions
7
 * are met:
8
 * 1. Redistributions of source code must retain the above copyright
9
 *    notice, this list of conditions and the following disclaimer.
10
 * 2. Redistributions in binary form must reproduce the above copyright
11
 *    notice, this list of conditions and the following disclaimer in the
12
 *    documentation and/or other materials provided with the distribution.
13
 * 3. Neither the name of the author nor the names of any co-contributors
14
 *    may be used to endorse or promote products derived from this software
15
 *    without specific prior written permission.
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27
 * SUCH DAMAGE.
28
 */
29

    
30
/*
31
 * page.c - physical page allocator
32
 */
33

    
34
/*
35
 * Simple list-based page allocator:
36
 *
37
 * When the remaining page is exhausted, what should we do ?
38
 * If the system can stop with panic() here, the error check of
39
 * many portions in kernel is not necessary, and kernel code can
40
 * become more simple. But, in general, even if a page is
41
 * exhausted, a kernel can not be stopped but it should return an
42
 * error and continue processing.  If the memory becomes short
43
 * during boot time, kernel and drivers can use panic() in that
44
 * case.
45
 */
46

    
47
#include <kernel.h>
48
#include <page.h>
49
#include <sched.h>
50
#include <hal.h>
51

    
52
/*
53
 * The page structure is put on the head of the first page of
54
 * each free block.
55
 */
56
struct page {
57
        struct page        *next;
58
        struct page        *prev;
59
        vsize_t                size;                /* number of bytes of this block */
60
};
61

    
62
static struct page        page_head;        /* first free block */
63
static psize_t                total_size;        /* size of memory in the system */
64
static psize_t                used_size;        /* current used size */
65
static psize_t                bootdisk_size;        /* size of the boot disk */
66

    
67
/*
68
 * page_alloc - allocate continuous pages of the specified size.
69
 *
70
 * This routine returns the physical address of a new free page
71
 * block, or returns NULL on failure. The requested size is
72
 * automatically round up to the page boundary.  The allocated
73
 * memory is _not_ filled with 0.
74
 */
75
paddr_t
76
page_alloc(psize_t psize)
77
{
78
        struct page *blk, *tmp;
79
        vsize_t size;
80

    
81
        ASSERT(psize != 0);
82

    
83
        sched_lock();
84

    
85
        /*
86
         * Find the free block that has enough size.
87
         */
88
        size = round_page(psize);
89
        blk = &page_head;
90
        do {
91
                blk = blk->next;
92
                if (blk == &page_head) {
93
                        sched_unlock();
94
                        DPRINTF(("page_alloc: out of memory\n"));
95
                        return 0;        /* Not found. */
96
                }
97
        } while (blk->size < size);
98

    
99
        /*
100
         * If found block size is exactly same with requested,
101
         * just remove it from a free list. Otherwise, the
102
         * found block is divided into two and first half is
103
         * used for allocation.
104
         */
105
        if (blk->size == size) {
106
                blk->prev->next = blk->next;
107
                blk->next->prev = blk->prev;
108
        } else {
109
                tmp = (struct page *)((vaddr_t)blk + size);
110
                tmp->size = blk->size - size;
111
                tmp->prev = blk->prev;
112
                tmp->next = blk->next;
113
                blk->prev->next = tmp;
114
                blk->next->prev = tmp;
115
        }
116
        used_size += (psize_t)size;
117
        sched_unlock();
118
        return kvtop(blk);
119
}
120

    
121
/*
122
 * Free page block.
123
 *
124
 * This allocator does not maintain the size of allocated page
125
 * block. The caller must provide the size information of the
126
 * block.
127
 */
128
void
129
page_free(paddr_t paddr, psize_t psize)
130
{
131
        struct page *blk, *prev;
132
        vsize_t size;
133

    
134
        ASSERT(psize != 0);
135

    
136
        sched_lock();
137

    
138
        size = round_page(psize);
139
        blk = ptokv(paddr);
140

    
141
        /*
142
         * Find the target position in list.
143
         */
144
        for (prev = &page_head; prev->next < blk; prev = prev->next) {
145
                if (prev->next == &page_head)
146
                        break;
147
        }
148

    
149
        /*
150
         * Insert new block into list.
151
         */
152
        blk->size = size;
153
        blk->prev = prev;
154
        blk->next = prev->next;
155
        prev->next->prev = blk;
156
        prev->next = blk;
157

    
158
        /*
159
         * If the adjoining block is free, it combines and
160
         * is made on block.
161
         */
162
        if (blk->next != &page_head &&
163
            ((vaddr_t)blk + blk->size) == (vaddr_t)blk->next) {
164
                blk->size += blk->next->size;
165
                blk->next = blk->next->next;
166
                blk->next->prev = blk;
167
        }
168
        if (blk->prev != &page_head &&
169
            (vaddr_t)blk->prev + blk->prev->size == (vaddr_t)blk) {
170
                blk->prev->size += blk->size;
171
                blk->prev->next = blk->next;
172
                blk->next->prev = blk->prev;
173
        }
174
        used_size -= (psize_t)size;
175
        sched_unlock();
176
}
177

    
178
/*
179
 * The function to reserve pages in specific address.
180
 */
181
int
182
page_reserve(paddr_t paddr, psize_t psize)
183
{
184
        struct page *blk, *tmp;
185
        vaddr_t start, end;
186
        vsize_t size;
187

    
188
        if (psize == 0)
189
                return 0;
190

    
191
        start = trunc_page((vaddr_t)ptokv(paddr));
192
        end = round_page((vaddr_t)ptokv(paddr + psize));
193
        size = end - start;
194

    
195
        /*
196
         * Find the block which includes specified block.
197
         */
198
        blk = page_head.next;
199
        for (;;) {
200
                if (blk == &page_head)
201
                        return ENOMEM;
202

    
203
                if ((vaddr_t)blk <= start
204
                    && end <= (vaddr_t)blk + blk->size)
205
                        break;
206
                blk = blk->next;
207
        }
208
        if ((vaddr_t)blk == start && blk->size == size) {
209
                /*
210
                 * Unlink the block from free list.
211
                 */
212
                blk->prev->next = blk->next;
213
                blk->next->prev = blk->prev;
214
        } else {
215
                /*
216
                 * Split this block.
217
                 */
218
                if ((vaddr_t)blk + blk->size != end) {
219
                        tmp = (struct page *)end;
220
                        tmp->size = (vaddr_t)blk + blk->size - end;
221
                        tmp->next = blk->next;
222
                        tmp->prev = blk;
223

    
224
                        blk->size -= tmp->size;
225
                        blk->next->prev = tmp;
226
                        blk->next = tmp;
227
                }
228
                if ((vaddr_t)blk == start) {
229
                        blk->prev->next = blk->next;
230
                        blk->next->prev = blk->prev;
231
                } else
232
                        blk->size = start - (vaddr_t)blk;
233
        }
234
        used_size += (psize_t)size;
235
        return 0;
236
}
237

    
238
void
239
page_info(struct meminfo *info)
240
{
241

    
242
        info->total = total_size;
243
        info->free = total_size - used_size;
244
        info->bootdisk = bootdisk_size;
245

    
246
#ifndef CONFIG_ROMBOOT
247
        /*
248
         * The boot disk is placed at RAM.
249
         */
250
        info->free -= bootdisk_size;
251
#endif
252
}
253

    
254
/*
255
 * Initialize page allocator.
256
 * page_init() must be called prior to other memory manager's
257
 * initializations.
258
 */
259
void
260
page_init(void)
261
{
262
        struct physmem *ram;
263
        struct bootinfo *bi;
264
        int i;
265

    
266
        machine_bootinfo(&bi);
267

    
268
        total_size = 0;
269
        bootdisk_size = 0;
270
        page_head.next = page_head.prev = &page_head;
271

    
272
        /*
273
         * First, create a free list from the boot information.
274
         */
275
        for (i = 0; i < bi->nr_rams; i++) {
276
                ram = &bi->ram[i];
277
                if (ram->type == MT_USABLE) {
278
                        page_free(ram->base, ram->size);
279
                        total_size += ram->size;
280
                }
281
        }
282
        /*
283
         * Then, reserve un-usable memory.
284
         */
285
        for (i = 0; i < bi->nr_rams; i++) {
286
                ram = &bi->ram[i];
287
                switch (ram->type) {
288
                case MT_BOOTDISK:
289
                        bootdisk_size += ram->size;
290
                        /* FALLTHROUGH */
291
                case MT_MEMHOLE:
292
                        total_size -= ram->size;
293
                        /* FALLTHROUGH */
294
                case MT_RESERVED:
295
                        if (page_reserve(ram->base, ram->size))
296
                                panic("page_init");
297
                        break;
298
                }
299
        }
300
        used_size = 0;
301
        DPRINTF(("Memory size=%ld\n", total_size));
302
}