Merge from vendor branch BINUTILS:
[dragonfly.git] / sys / i386 / boot / cdboot / malloc.c
1 /*
2  * Copyright © 1997 Pluto Technologies International, Inc.  Boulder CO
3  * Copyright © 1997 interface business GmbH, Dresden.
4  *      All rights reserved.
5  *
6  * This code was written by Jörg Wunsch, Dresden.
7  * Direct comments to <joerg_wunsch@interface-business.de>.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  * 1. Redistributions of source code must retain the above copyright
13  *    notice, this list of conditions and the following disclaimer.
14  * 2. Redistributions in binary form must reproduce the above copyright
15  *    notice, this list of conditions and the following disclaimer in the
16  *    documentation and/or other materials provided with the distribution.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21  * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT,
22  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
24  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
26  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
27  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28  * POSSIBILITY OF SUCH DAMAGE.
29  *
30  * $FreeBSD: src/sys/i386/boot/cdboot/malloc.c,v 1.2 1999/08/28 00:43:18 peter Exp $
31  * $DragonFly: src/sys/i386/boot/cdboot/Attic/malloc.c,v 1.2 2003/06/17 04:28:34 dillon Exp $
32  */
33
34 /*
35  * Simple memory allocator for the bootstrap loader.  Probably suffers
36  * a lot from fragmentation.
37  */
38
39 #include "boot.h"
40
41 #include <stddef.h>
42
43 /* ``Nobody will ever need more than 640 KB of RAM.'' :-) */
44 #define MAXBRK (640 * 1024 * 1024)
45
46 /* allocation unit */
47 #define NCHUNKS 2048
48
49 struct chunk
50 {
51         struct chunk *next;
52         size_t len;
53 };
54
55 static void *brkval;
56 static struct chunk *freelist;
57
58 void *
59 malloc(size_t len)
60 {
61         struct chunk *p, *q, *oldp;
62         size_t nelems;
63
64         nelems = (len + sizeof(struct chunk) - 1) / sizeof(struct chunk) + 1;
65
66         /*
67          * First, see if we can satisfy the request from the freelist.
68          */
69         for (p = freelist, oldp = 0;
70              p && p != (struct chunk *)brkval;
71              oldp = p, p = p->next) {
72                 if (p->len > nelems) {
73                         /* chunk is larger, shorten, and return the tail */
74                         p->len -= nelems;
75                         q = p + p->len;
76                         q->next = 0;
77                         q->len = nelems;
78                         q++;
79                         return (void *)q;
80                 }
81                 if (p->len == nelems) {
82                         /* exact match, remove from freelist */
83                         if (oldp == 0)
84                                 freelist = p->next;
85                         else
86                                 oldp->next = p->next;
87                         p->next = 0;
88                         p++;
89                         return (void *)p;
90                 }
91         }
92         /*
93          * Nothing found on freelist, try obtaining more space.
94          */
95         if (brkval == 0)
96                 brkval = &end;
97         q = p = (struct chunk *)brkval;
98         if ((int)(p + NCHUNKS) > MAXBRK)
99                 return 0;
100
101         p += NCHUNKS;
102         brkval = p;
103
104         q->next = p;
105         q->len = NCHUNKS;
106
107         if (oldp == 0)
108                 freelist = q;
109         else {
110                 if (oldp + oldp->len == q) {
111                         /* extend last chunk */
112                         oldp->len += NCHUNKS;
113                         oldp->next = p;
114                 } else
115                         oldp->next = q;
116         }
117
118         return malloc(len);
119 }
120
121 void
122 free(void *ptr)
123 {
124         struct chunk *p, *q, *oldp;
125
126         if (ptr == 0)
127                 return;
128
129         q = (struct chunk *)ptr;
130         q--;
131         if (q->next != 0) {
132                 printf("malloc error: botched ptr to free()\n");
133                 return;
134         }
135
136         /*
137          * Walk the freelist, and insert in the correct sequence.
138          */
139         for (p = freelist, oldp = 0;
140              p && p != (struct chunk *)brkval;
141              oldp = p, p = p->next) {
142                 if ((unsigned)p > (unsigned)q) {
143                         if (q + q->len == p) {
144                                 /* aggregate with next chunk */
145                                 q->len += p->len;
146                                 q->next = p->next;
147                                 p = p->next;
148                         }
149                         if (oldp) {
150                                 if (oldp + oldp->len == q) {
151                                 /* aggregate with previous chunk */
152                                         oldp->len += q->len;
153                                         oldp->next = p;
154                                 } else {
155                                 /* insert into chain */
156                                         q->next = p;
157                                         oldp->next = q;
158                                 }
159                                 return;
160                         }
161                         q->next = p;
162                         freelist = q;
163                 }
164         }
165         if (oldp) {
166                 /* we are topmost */
167                 if (oldp + oldp->len == q) {
168                         /* aggregate with previous chunk */
169                         oldp->len += q->len;
170                         oldp->next = p;
171                 } else {
172                         oldp->next = q;
173                         q->next = p;
174                 }
175                 return;
176         }
177         /* we are alone on the freelist */
178         freelist = q;
179 }
180