Subversion Repositories shark

Rev

Rev 3 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 pj 1
/*
2
 * Project: S.Ha.R.K.
3
 *
4
 * Coordinators:
5
 *   Giorgio Buttazzo    <giorgio@sssup.it>
6
 *   Paolo Gai           <pj@gandalf.sssup.it>
7
 *
8
 * Authors     :
9
 *   Paolo Gai           <pj@gandalf.sssup.it>
10
 *   (see the web pages for full authors list)
11
 *
12
 * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)
13
 *
14
 * http://www.sssup.it
15
 * http://retis.sssup.it
16
 * http://shark.sssup.it
17
 */
18
 
19
/**
20
 ------------
21
 CVS :        $Id: alloc_ge.c,v 1.1.1.1 2002-03-29 14:12:52 pj Exp $
22
 
23
 File:        $File$
24
 Revision:    $Revision: 1.1.1.1 $
25
 Last update: $Date: 2002-03-29 14:12:52 $
26
 ------------
27
 
28
this code is from:
29
List-based Memory Management, from OsKit.
30
 
31
**/
32
 
33
/*
34
 * Copyright (C) 2000 Paolo Gai
35
 *
36
 * This program is free software; you can redistribute it and/or modify
37
 * it under the terms of the GNU General Public License as published by
38
 * the Free Software Foundation; either version 2 of the License, or
39
 * (at your option) any later version.
40
 *
41
 * This program is distributed in the hope that it will be useful,
42
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
43
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
44
 * GNU General Public License for more details.
45
 *
46
 * You should have received a copy of the GNU General Public License
47
 * along with this program; if not, write to the Free Software
48
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
49
 *
50
 */
51
 
52
/*
53
 * Copyright (c) 1995-1996, 1998-1999 University of Utah and the Flux Group.
54
 * All rights reserved.
55
 *
56
 * This file is part of the Flux OSKit.  The OSKit is free software, also known
57
 * as "open source;" you can redistribute it and/or modify it under the terms
58
 * of the GNU General Public License (GPL), version 2, as published by the Free
59
 * Software Foundation (FSF).  To explore alternate licensing terms, contact
60
 * the University of Utah at csl-dist@cs.utah.edu or +1-801-585-3271.
61
 *
62
 * The OSKit is distributed in the hope that it will be useful, but WITHOUT ANY
63
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
64
 * FOR A PARTICULAR PURPOSE.  See the GPL for more details.  You should have
65
 * received a copy of the GPL along with the OSKit; see the file COPYING.  If
66
 * not, write to the FSF, 59 Temple Place #330, Boston, MA 02111-1307, USA.
67
 */
68
 
69
#include <kernel/lmm.h>
70
#define assert(test) assertk(test)
71
 
72
void *lmm_alloc_gen(lmm_t *lmm, size_t size, lmm_flags_t flags,
73
                    int align_bits, DWORD align_ofs,
74
                    DWORD in_min, size_t in_size)
75
{
76
        DWORD in_max = in_min + in_size;
77
        struct lmm_region *reg;
78
 
79
#if 0
80
        kern_printf("lmm_alloc_gen %08x\n", size);
81
        lmm_dump(lmm);
82
#endif
83
 
84
        assert(lmm != 0);
85
        assert(size > 0);
86
 
87
        for (reg = lmm->regions; reg; reg = reg->next)
88
        {
89
                struct lmm_node **nodep, *node;
90
 
91
                CHECKREGPTR(reg);
92
 
93
                /* First trivially reject the entire region if possible.  */
94
                if ((flags & ~reg->flags)
95
                    || (reg->min >= in_max)
96
                    || (reg->max <= in_min))
97
                        continue;
98
 
99
                for (nodep = &reg->nodes;
100
                     (node = *nodep) != 0;
101
                     nodep = &node->next)
102
                {
103
                        DWORD addr;
104
                        struct lmm_node *anode;
105
                        int i;
106
 
107
                        assert(((DWORD)node & ALIGN_MASK) == 0);
108
                        assert(((DWORD)node->size & ALIGN_MASK) == 0);
109
                        assert((node->next == 0) || (node->next > node));
110
                        assert((DWORD)node < reg->max);
111
 
112
                        /* Now make a first-cut trivial elimination check
113
                           to skip chunks that are _definitely_ too small.  */
114
                        if (node->size < size)
115
                                continue;
116
 
117
                        /* Now compute the address at which
118
                           the allocated chunk would have to start.  */
119
                        addr = (DWORD)node;
120
                        if (addr < in_min)
121
                                addr = in_min;
122
                        for (i = 0; i < align_bits; i++)
123
                        {
124
                                DWORD bit = (DWORD)1 << i;
125
                                if ((addr ^ align_ofs) & bit)
126
                                        addr += bit;
127
                        }
128
 
129
                        /* See if the block at the adjusted address
130
                           is still entirely within the node.  */
131
                        if ((addr - (DWORD)node + size) > node->size)
132
                                continue;
133
 
134
                        /* If the block extends past the range constraint,
135
                           then all of the rest of the nodes in this region
136
                           will extend past it too, so stop here. */
137
                        if (addr + size > in_max)
138
                                break;
139
 
140
                        /* OK, we can allocate the block from this node.  */
141
 
142
                        /* If the allocation leaves at least ALIGN_SIZE
143
                           space before it, then split the node.  */
144
                        anode = (struct lmm_node*)(addr & ~ALIGN_MASK);
145
                        assert(anode >= node);
146
                        if (anode > node)
147
                        {
148
                                size_t split_size = (DWORD)anode
149
                                                  - (DWORD)node;
150
                                assert((split_size & ALIGN_MASK) == 0);
151
                                anode->next = node->next;
152
                                anode->size = node->size - split_size;
153
                                node->size = split_size;
154
                                nodep = &node->next;
155
                        }
156
 
157
                        /* Now use the first part of the anode
158
                           to satisfy the allocation,
159
                           splitting off the tail end if necessary.  */
160
                        size = ((addr & ALIGN_MASK) + size + ALIGN_MASK)
161
                                & ~ALIGN_MASK;
162
                        if (anode->size > size)
163
                        {
164
                                struct lmm_node *newnode;
165
 
166
                                /* Split the node and return its head.  */
167
                                newnode = (struct lmm_node*)
168
                                                ((void*)anode + size);
169
                                newnode->next = anode->next;
170
                                newnode->size = anode->size - size;
171
                                *nodep = newnode;
172
                        }
173
                        else
174
                        {
175
                                /* Remove and return the entire node.  */
176
                                *nodep = anode->next;
177
                        }
178
 
179
                        /* Adjust the region's free memory counter.  */
180
                        assert(reg->free >= size);
181
                        reg->free -= size;
182
 
183
#if 0
184
                        kern_printf("lmm_alloc_gen returning %08x\n", addr);
185
                        lmm_dump(lmm);
186
#endif
187
 
188
                        return (void*)addr;
189
                }
190
        }
191
 
192
#if 0
193
        kern_printf("lmm_alloc_gen failed\n");
194
#endif
195
 
196
        return 0;
197
}
198