Statistics
| Branch: | Revision:

root / prex-0.9.0 / sys / mem / kmem.c @ 03e9c04a

History | View | Annotate | Download (9.24 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
 * kmem.c - kernel memory allocator
32
 */
33

    
34
/*
35
 * This is a memory allocator optimized for the low foot print
36
 * kernel. It works on top of the underlying page allocator, and
37
 * manages more smaller memory than page size. It will divide one page
38
 * into two or more blocks, and each page is linked as a kernel page.
39
 *
40
 * There are following 3 linked lists to manage used/free blocks.
41
 *  1) All pages allocated for the kernel memory are linked.
42
 *  2) All blocks divided in the same page are linked.
43
 *  3) All free blocks of the same size are linked.
44
 *
45
 * Currently, it can not handle the memory size exceeding one page.
46
 * Instead, a driver can use page_alloc() to allocate larger memory.
47
 *
48
 * The kmem functions are used by not only the kernel core but also by
49
 * the buggy drivers. If such kernel code illegally writes data in
50
 * exceeding the allocated area, the system will crash easily. In
51
 * order to detect the memory over run, each free block has a magic
52
 * ID.
53
 */
54

    
55
#include <kernel.h>
56
#include <page.h>
57
#include <sched.h>
58
#include <vm.h>
59
#include <kmem.h>
60

    
61
/*
62
 * Block header
63
 *
64
 * All free blocks that have same size are linked each other.
65
 * In addition, all free blocks within same page are also linked.
66
 */
67
struct block_hdr {
68
        u_short                 magic;                /* magic number */
69
        u_short                 size;                /* size of this block */
70
        struct list         link;                /* link to the free list */
71
        struct block_hdr *pg_next;        /* next block in same page */
72
};
73

    
74
/*
75
 * Page header
76
 *
77
 * The page header is placed at the top of each page. This
78
 * header is used in order to free the page when there are no
79
 * used block left in the page. If 'nallocs' value becomes zero,
80
 * that page can be removed from kernel page.
81
 */
82
struct page_hdr {
83
        u_short                 magic;                /* magic number */
84
        u_short                 nallocs;        /* number of allocated blocks */
85
        struct block_hdr first_blk;        /* first block in this page */
86
};
87

    
88
#define ALIGN_SIZE        16
89
#define ALIGN_MASK        (ALIGN_SIZE - 1)
90
#define ALLOC_SIZE(n)        (size_t) \
91
                        (((vaddr_t)(n) + ALIGN_MASK) & (vaddr_t)~ALIGN_MASK)
92

    
93
/* number of free block list */
94
#define NR_BLOCK_LIST        (PAGE_SIZE / ALIGN_SIZE)
95

    
96
#define BLOCK_MAGIC        0xdead
97
#define PAGE_MAGIC        0xbeef
98

    
99
#define BLKHDR_SIZE        (sizeof(struct block_hdr))
100
#define PGHDR_SIZE        (sizeof(struct page_hdr))
101
#define MAX_ALLOC_SIZE        (size_t)(PAGE_SIZE - PGHDR_SIZE)
102

    
103
#define MIN_BLOCK_SIZE        (BLKHDR_SIZE + 16)
104
#define MAX_BLOCK_SIZE        (u_short)(PAGE_SIZE - (PGHDR_SIZE - BLKHDR_SIZE))
105

    
106
/* macro to point the page header from specific address. */
107
#define PAGETOP(n)        (struct page_hdr *) \
108
                            ((vaddr_t)(n) & (vaddr_t)~(PAGE_SIZE - 1))
109

    
110
/* macro to get the index of free block list. */
111
#define BLKNDX(b)        ((u_int)((b)->size) >> 4)
112

    
113
/**
114
 * Array of the head block of free block list.
115
 *
116
 * The index of array is decided by the size of each block.
117
 * All block has the size of the multiple of 16.
118
 *
119
 * ie. free_blocks[0] = list for 16 byte block
120
 *     free_blocks[1] = list for 32 byte block
121
 *     free_blocks[2] = list for 48 byte block
122
 *         .
123
 *         .
124
 *     free_blocks[255] = list for 4096 byte block
125
 *
126
 * Generally, only one list is used to search the free block with
127
 * a first fit algorithm. Basically, this allocator also uses a
128
 * first fit method. However it uses multiple lists corresponding
129
 * to each block size. A search is started from the list of the
130
 * requested size. So, it is not necessary to search smaller
131
 * block's list wastefully.
132
 *
133
 * Most of kernel memory allocator is using 2^n as block size.
134
 * But, these implementation will throw away much memory that
135
 * the block size is not fit. This is not suitable for the
136
 * embedded system with low foot print.
137
 */
138
static struct list free_blocks[NR_BLOCK_LIST];
139

    
140
/*
141
 * Find the free block for the specified size.
142
 * Returns pointer to free block, or NULL on failure.
143
 *
144
 * First, it searches from the list of same size. If it does not
145
 * exists, then it will search the list of larger one.
146
 * It will use the block of smallest size that satisfies the
147
 * specified size.
148
 */
149
static struct block_hdr *
150
block_find(size_t size)
151
{
152
        int i;
153
        list_t n;
154

    
155
        for (i = (int)((u_int)size >> 4); i < NR_BLOCK_LIST; i++) {
156
                if (!list_empty(&free_blocks[i]))
157
                        break;
158
        }
159
        if (i >= NR_BLOCK_LIST)
160
                return NULL;
161

    
162
        n = list_first(&free_blocks[i]);
163
        return list_entry(n, struct block_hdr, link);
164
}
165

    
166
/*
167
 * Allocate memory block for kernel
168
 *
169
 * This function does not fill the allocated block by 0 for performance.
170
 * kmem_alloc() returns NULL on failure.
171
 *
172
 * => must not be called from interrupt context.
173
 */
174
void *
175
kmem_alloc(size_t size)
176
{
177
        struct block_hdr *blk, *newblk;
178
        struct page_hdr *pg;
179
        paddr_t pa;
180
        void *p;
181

    
182
        ASSERT(size != 0);
183

    
184
        sched_lock();                /* Lock scheduler */
185

    
186
        /*
187
         * First, the free block of enough size is searched
188
         * from the page already used. If it does not exist,
189
         * new page is allocated for free block.
190
         */
191
        size = ALLOC_SIZE(size + BLKHDR_SIZE);
192
        if (size > MAX_ALLOC_SIZE)
193
                panic("kmem_alloc: too large allocation");
194

    
195
        blk = block_find(size);
196
        if (blk) {
197
                /*
198
                 * Block found.
199
                 */
200
                list_remove(&blk->link); /* Remove from free list */
201
                pg = PAGETOP(blk);         /* Get the page address */
202
        } else {
203
                /*
204
                 * No block found. Allocate new page.
205
                 */
206
                if ((pa = page_alloc(PAGE_SIZE)) == 0) {
207
                        sched_unlock();
208
                        return NULL;
209
                }
210
                pg = ptokv(pa);
211
                pg->nallocs = 0;
212
                pg->magic = PAGE_MAGIC;
213

    
214
                /*
215
                 * Setup first block.
216
                 */
217
                blk = &pg->first_blk;
218
                blk->magic = BLOCK_MAGIC;
219
                blk->size = MAX_BLOCK_SIZE;
220
                blk->pg_next = NULL;
221
        }
222

    
223
        /*
224
         * Sanity check
225
         */
226
        if (pg->magic != PAGE_MAGIC || blk->magic != BLOCK_MAGIC)
227
                panic("kmem_alloc: overrun");
228

    
229
        /*
230
         * If the found block is large enough, split it.
231
         */
232
        if (blk->size - size >= MIN_BLOCK_SIZE) {
233
                /*
234
                 * Make new block.
235
                 */
236
                newblk = (struct block_hdr *)((vaddr_t)blk + size);
237
                newblk->magic = BLOCK_MAGIC;
238
                newblk->size = (u_short)(blk->size - size);
239
                list_insert(&free_blocks[BLKNDX(newblk)], &newblk->link);
240

    
241
                /*
242
                 * Update page list.
243
                 */
244
                newblk->pg_next = blk->pg_next;
245
                blk->pg_next = newblk;
246
                blk->size = (u_short)size;
247
        }
248
        /*
249
         * Increment allocation count of this page.
250
         */
251
        pg->nallocs++;
252
        p = (void *)((vaddr_t)blk + BLKHDR_SIZE);
253

    
254
        sched_unlock();
255
        return p;
256
}
257

    
258
/*
259
 * Free allocated memory block.
260
 *
261
 * Some kernel does not release the free page for the kernel memory
262
 * because it is needed to allocate immediately later. For example,
263
 * it is efficient here if the free page is just linked to the list
264
 * of the biggest size. However, consider the case where a driver
265
 * requires many small memories temporarily. After these pages are
266
 * freed, they can not be reused for an application.
267
 */
268
void
269
kmem_free(void *ptr)
270
{
271
        struct block_hdr *blk;
272
        struct page_hdr *pg;
273

    
274
        ASSERT(ptr != NULL);
275

    
276
        /* Lock scheduler */
277
        sched_lock();
278

    
279
        /* Get the block header */
280
        blk = (struct block_hdr *)((vaddr_t)ptr - BLKHDR_SIZE);
281
        if (blk->magic != BLOCK_MAGIC)
282
                panic("kmem_free: invalid address");
283

    
284
        /*
285
         * Return the block to free list. Since kernel code will
286
         * request fixed size of memory block, we don't merge the
287
         * blocks to use it as cache.
288
         */
289
        list_insert(&free_blocks[BLKNDX(blk)], &blk->link);
290

    
291
        /*
292
         * Decrement allocation count of this page.
293
         */
294
        pg = PAGETOP(blk);
295
        if (--pg->nallocs == 0) {
296
                /*
297
                 * No allocated block in this page.
298
                 * Remove all blocks and deallocate this page.
299
                 */
300
                for (blk = &pg->first_blk; blk != NULL; blk = blk->pg_next) {
301
                        list_remove(&blk->link); /* Remove from free list */
302
                }
303
                pg->magic = 0;
304
                page_free(kvtop(pg), PAGE_SIZE);
305
        }
306
        sched_unlock();
307
}
308

    
309
/*
310
 * Map specified virtual address to the kernel address
311
 * Returns kernel address on success, or NULL if no mapped memory.
312
 */
313
void *
314
kmem_map(void *addr, size_t size)
315
{
316
        paddr_t pa;
317

    
318
        pa = vm_translate((vaddr_t)addr, size);
319
        if (pa == 0)
320
                return NULL;
321
        return ptokv(pa);
322
}
323

    
324
void
325
kmem_init(void)
326
{
327
        int i;
328

    
329
        for (i = 0; i < NR_BLOCK_LIST; i++)
330
                list_init(&free_blocks[i]);
331
}