ia64/xen-unstable

view extras/mini-os/lib/xmalloc.c @ 16838:945820bfedb6

minios: POSIX fixes
Fixes some functions which are POSIX. Also make them ifndef HAVE_LIBC.

Signed-off-by: Samuel Thibault <samuel.thibault@eu.citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Tue Jan 22 14:20:22 2008 +0000 (2008-01-22)
parents 5f3c236d1711
children b9b6caf06f8c
line source
1 /*
2 ****************************************************************************
3 * (C) 2005 - Grzegorz Milos - Intel Research Cambridge
4 ****************************************************************************
5 *
6 * File: xmaloc.c
7 * Author: Grzegorz Milos (gm281@cam.ac.uk)
8 * Samuel Thibault (samuel.thibault@eu.citrix.com)
9 * Changes:
10 *
11 * Date: Aug 2005
12 * Jan 2008
13 *
14 * Environment: Xen Minimal OS
15 * Description: simple memory allocator
16 *
17 ****************************************************************************
18 * Simple allocator for Mini-os. If larger than a page, simply use the
19 * page-order allocator.
20 *
21 * Copy of the allocator for Xen by Rusty Russell:
22 * Copyright (C) 2005 Rusty Russell IBM Corporation
23 *
24 * This program is free software; you can redistribute it and/or modify
25 * it under the terms of the GNU General Public License as published by
26 * the Free Software Foundation; either version 2 of the License, or
27 * (at your option) any later version.
28 *
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
33 *
34 * You should have received a copy of the GNU General Public License
35 * along with this program; if not, write to the Free Software
36 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
37 */
39 #include <os.h>
40 #include <mm.h>
41 #include <types.h>
42 #include <lib.h>
43 #include <list.h>
44 #include <xmalloc.h>
46 #ifndef HAVE_LIBC
47 static LIST_HEAD(freelist);
48 /* static spinlock_t freelist_lock = SPIN_LOCK_UNLOCKED; */
50 struct xmalloc_hdr
51 {
52 /* Total including this hdr, unused padding and second hdr. */
53 size_t size;
54 struct list_head freelist;
55 } __cacheline_aligned;
57 /* Unused padding data between the two hdrs. */
59 struct xmalloc_pad
60 {
61 /* Size including both hdrs. */
62 size_t hdr_size;
63 };
65 static void maybe_split(struct xmalloc_hdr *hdr, size_t size, size_t block)
66 {
67 struct xmalloc_hdr *extra;
68 size_t leftover = block - size;
70 /* If enough is left to make a block, put it on free list. */
71 if ( leftover >= (2 * (sizeof(struct xmalloc_hdr) + sizeof(struct xmalloc_pad))) )
72 {
73 extra = (struct xmalloc_hdr *)((unsigned long)hdr + size);
74 extra->size = leftover;
75 /* spin_lock_irqsave(&freelist_lock, flags); */
76 list_add(&extra->freelist, &freelist);
77 /* spin_unlock_irqrestore(&freelist_lock, flags); */
78 }
79 else
80 {
81 size = block;
82 }
84 hdr->size = size;
85 /* Debugging aid. */
86 hdr->freelist.next = hdr->freelist.prev = NULL;
87 }
89 static struct xmalloc_hdr *xmalloc_new_page(size_t size)
90 {
91 struct xmalloc_hdr *hdr;
92 /* unsigned long flags; */
94 hdr = (struct xmalloc_hdr *)alloc_page();
95 if ( hdr == NULL )
96 return NULL;
98 maybe_split(hdr, size, PAGE_SIZE);
100 return hdr;
101 }
103 /* Return size, increased to alignment with align. */
104 static inline size_t align_up(size_t size, size_t align)
105 {
106 return (size + align - 1) & ~(align - 1);
107 }
109 /* Big object? Just use the page allocator. */
110 static void *xmalloc_whole_pages(size_t size, size_t align)
111 {
112 struct xmalloc_hdr *hdr;
113 struct xmalloc_pad *pad;
114 unsigned int pageorder;
115 void *ret;
116 /* Room for headers */
117 size_t hdr_size = sizeof(struct xmalloc_hdr) + sizeof(struct xmalloc_pad);
118 /* Align for actual beginning of data */
119 hdr_size = align_up(hdr_size, align);
121 pageorder = get_order(hdr_size + size);
123 hdr = (struct xmalloc_hdr *)alloc_pages(pageorder);
124 if ( hdr == NULL )
125 return NULL;
127 hdr->size = (1 << (pageorder + PAGE_SHIFT));
128 /* Debugging aid. */
129 hdr->freelist.next = hdr->freelist.prev = NULL;
131 ret = (char*)hdr + hdr_size;
132 pad = (struct xmalloc_pad *) ret - 1;
133 pad->hdr_size = hdr_size;
134 return ret;
135 }
137 void *_xmalloc(size_t size, size_t align)
138 {
139 struct xmalloc_hdr *i, *hdr = NULL;
140 uintptr_t data_begin;
141 size_t hdr_size;
142 /* unsigned long flags; */
144 hdr_size = sizeof(struct xmalloc_hdr) + sizeof(struct xmalloc_pad);
145 /* Align on headers requirements. */
146 align = align_up(align, __alignof__(struct xmalloc_hdr));
147 align = align_up(align, __alignof__(struct xmalloc_pad));
149 /* For big allocs, give them whole pages. */
150 if ( size + align_up(hdr_size, align) >= PAGE_SIZE )
151 return xmalloc_whole_pages(size, align);
153 /* Search free list. */
154 /* spin_lock_irqsave(&freelist_lock, flags); */
155 list_for_each_entry( i, &freelist, freelist )
156 {
157 data_begin = align_up((uintptr_t)i + hdr_size, align);
159 if ( data_begin + size > (uintptr_t)i + i->size )
160 continue;
162 list_del(&i->freelist);
163 /* spin_unlock_irqrestore(&freelist_lock, flags); */
165 uintptr_t size_before = (data_begin - hdr_size) - (uintptr_t)i;
167 if (size_before >= 2 * hdr_size) {
168 /* Worth splitting the beginning */
169 struct xmalloc_hdr *new_i = (void*)(data_begin - hdr_size);
170 new_i->size = i->size - size_before;
171 i->size = size_before;
172 /* spin_lock_irqsave(&freelist_lock, flags); */
173 list_add(&i->freelist, &freelist);
174 /* spin_unlock_irqrestore(&freelist_lock, flags); */
175 i = new_i;
176 }
177 maybe_split(i, (data_begin + size) - (uintptr_t)i, i->size);
178 hdr = i;
179 break;
180 }
182 if (!hdr) {
183 /* spin_unlock_irqrestore(&freelist_lock, flags); */
185 /* Alloc a new page and return from that. */
186 hdr = xmalloc_new_page(align_up(hdr_size, align) + size);
187 data_begin = (uintptr_t)hdr + align_up(hdr_size, align);
188 }
190 struct xmalloc_pad *pad = (struct xmalloc_pad *) data_begin - 1;
191 pad->hdr_size = data_begin - (uintptr_t)hdr;
192 BUG_ON(data_begin % align);
193 return (void*)data_begin;
194 }
196 void xfree(const void *p)
197 {
198 /* unsigned long flags; */
199 struct xmalloc_hdr *i, *tmp, *hdr;
200 struct xmalloc_pad *pad;
202 if ( p == NULL )
203 return;
205 pad = (struct xmalloc_pad *)p - 1;
206 hdr = (struct xmalloc_hdr *)((char *)p - pad->hdr_size);
208 /* We know hdr will be on same page. */
209 if(((long)p & PAGE_MASK) != ((long)hdr & PAGE_MASK))
210 {
211 printk("Header should be on the same page\n");
212 *(int*)0=0;
213 }
215 /* Not previously freed. */
216 if(hdr->freelist.next || hdr->freelist.prev)
217 {
218 printk("Should not be previously freed\n");
219 *(int*)0=0;
220 }
222 /* Big allocs free directly. */
223 if ( hdr->size >= PAGE_SIZE )
224 {
225 free_pages(hdr, get_order(hdr->size));
226 return;
227 }
229 /* Merge with other free block, or put in list. */
230 /* spin_lock_irqsave(&freelist_lock, flags); */
231 list_for_each_entry_safe( i, tmp, &freelist, freelist )
232 {
233 unsigned long _i = (unsigned long)i;
234 unsigned long _hdr = (unsigned long)hdr;
236 /* Do not merge across page boundaries. */
237 if ( ((_i ^ _hdr) & PAGE_MASK) != 0 )
238 continue;
240 /* We follow this block? Swallow it. */
241 if ( (_i + i->size) == _hdr )
242 {
243 list_del(&i->freelist);
244 i->size += hdr->size;
245 hdr = i;
246 }
248 /* We precede this block? Swallow it. */
249 if ( (_hdr + hdr->size) == _i )
250 {
251 list_del(&i->freelist);
252 hdr->size += i->size;
253 }
254 }
256 /* Did we merge an entire page? */
257 if ( hdr->size == PAGE_SIZE )
258 {
259 if((((unsigned long)hdr) & (PAGE_SIZE-1)) != 0)
260 {
261 printk("Bug\n");
262 *(int*)0=0;
263 }
264 free_pages(hdr, 0);
265 }
266 else
267 {
268 list_add(&hdr->freelist, &freelist);
269 }
271 /* spin_unlock_irqrestore(&freelist_lock, flags); */
272 }
274 void *_realloc(void *ptr, size_t size)
275 {
276 void *new;
277 struct xmalloc_hdr *hdr;
278 struct xmalloc_pad *pad;
280 if (ptr == NULL)
281 return _xmalloc(size, DEFAULT_ALIGN);
283 pad = (struct xmalloc_pad *)ptr - 1;
284 hdr = (struct xmalloc_hdr *)((char*)ptr - pad->hdr_size);
285 if (hdr->size >= size) {
286 maybe_split(hdr, size, hdr->size);
287 return ptr;
288 }
290 new = _xmalloc(size, DEFAULT_ALIGN);
291 if (new == NULL)
292 return NULL;
294 memcpy(new, ptr, hdr->size);
295 xfree(ptr);
297 return new;
298 }
299 #endif