Statistics
| Branch: | Revision:

scoutos / prex-0.9.0 / usr / lib / prex / malloc / malloc.c @ 03e9c04a

History | View | Annotate | Download (4.55 KB)

1
/*
2
 * Copyright (c) 2005-2007, 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
#include <sys/types.h>
31
#include <sys/prex.h>
32
#include <sys/param.h>
33
#include <sys/syslog.h>
34
#include <string.h>
35
#include <errno.h>
36
#include <stdlib.h>
37
#include "malloc.h"
38

    
39
#ifdef _REENTRANT
40
static mutex_t malloc_lock = MUTEX_INITIALIZER;
41
#endif
42

    
43
static struct header *more_core(size_t size);
44

    
45
static struct header free_list;                /* start of free list */
46
static struct header *scan_head;        /* start point to scan */
47

    
48
/*
49
 * Simple memory allocator from K&R
50
 */
51
void *
52
malloc(size_t size)
53
{
54
        struct header *p, *prev;
55

    
56
        if (size == 0)                /* sanity check */
57
                return NULL;
58
        size = ROUNDUP(size + sizeof(struct header));
59

    
60
        MALLOC_LOCK();
61

    
62
        if (scan_head == NULL) {
63
                /* Initialize */
64
                free_list.next = &free_list;
65
                free_list.size = 0;
66
                free_list.vm_size = 0;
67
                scan_head = &free_list;
68
        }
69
        prev = scan_head;
70
        for (p = prev->next;; prev = p, p = p->next) {
71
                if (p->size >= size) {        /* big enough */
72
                        if (p->size == size)        /* exactly */
73
                                prev->next = p->next;
74
                        else {                        /* allocate tail end */
75
                                p->size -= size;
76
                                p = (struct header *)((char *)p + p->size);
77
                                p->size = size;
78
                                p->vm_size = 0;
79
                        }
80
#ifdef DEBUG_MALLOC
81
                        p->magic = MALLOC_MAGIC;
82
#endif
83
                        scan_head = prev;
84
                        break;
85
                }
86
                if (p == scan_head) {
87
                        if ((p = more_core(size)) == NULL)
88
                                break;
89
                }
90
        }
91
        MALLOC_UNLOCK();
92

    
93
        if (p == NULL) {
94
#ifdef DEBUG_MALLOC
95
                sys_panic("malloc: out of memory");
96
#endif
97
                return NULL;
98
        }
99
        return (void *)(p + 1);
100
}
101

    
102
/*
103
 * Create new block and insert it to the free list.
104
 */
105
static struct header *more_core(size_t size)
106
{
107
        struct header *p, *prev;
108

    
109
        size = round_page(size);
110
        if (vm_allocate(task_self(), (void *)&p, size, 1))
111
                return NULL;
112
        p->size = size;
113
        p->vm_size = size;
114

    
115
        /* Insert to free list */
116
        for (prev = scan_head; !(p > prev && p < prev->next); prev = prev->next) {
117
                if (prev >= prev->next && (p > prev || p < prev->next))
118
                        break;
119
        }
120
        p->next = prev->next;
121
        prev->next = p;
122
        scan_head = prev;
123
        return prev;
124
}
125

    
126
void
127
free(void *addr)
128
{
129
        struct header *p, *prev;
130

    
131
        if (addr == NULL)
132
                return;
133

    
134
        MALLOC_LOCK();
135
        p = (struct header *)addr - 1;
136
#ifdef DEBUG_MALLOC
137
        if (p->magic != MALLOC_MAGIC)
138
                sys_panic("free: invalid pointer");
139
        p->magic = 0;
140
#endif
141
        for (prev = scan_head; !(p > prev && p < prev->next); prev = prev->next) {
142
                if (prev >= prev->next && (p > prev || p < prev->next))
143
                        break;
144
        }
145
        if ((prev->next->vm_size == 0) &&        /* join to upper block */
146
            ((char *)p + p->size == (char *)prev->next)) {
147
                p->size += prev->next->size;
148
                p->next = prev->next->next;
149
        } else {
150
                p->next = prev->next;
151
        }
152
        if ((p->vm_size == 0) &&        /* join to lower block */
153
            ((char *)prev + prev->size == (char *)p)) {
154
                prev->size += p->size;
155
                prev->next = p->next;
156
        } else {
157
                prev->next = p;
158
        }
159
        /* Deallocate pool */
160
        if (p->size == p->vm_size) {
161
                prev->next = p->next;
162
                vm_free(task_self(), p);
163
        }
164
        scan_head = prev;
165
        MALLOC_UNLOCK();
166
}
167

    
168
#ifdef DEBUG_MALLOC
169
void
170
mstat(void)
171
{
172
        struct header *p;
173

    
174
        printf("mstat: task=%x\n", task_self());
175
        for (p = free_list.next; p != &free_list; p = p->next) {
176
                printf("mstat: addr=%x size=%d next=%x\n", p, p->size, p->next);
177
        }
178
}
179
#endif