ia64/xen-unstable

view extras/mini-os/lib/xmalloc.c @ 18811:390ef36eb596

Remove Xen-private definitions from kexec public header.

Signed-off-by: Keir Fraser <keir.fraser@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Wed Nov 19 13:13:39 2008 +0000 (2008-11-19)
parents 3ab0e76fb8e2
children
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 MINIOS_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 minios_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 /* Return size, increased to alignment with align. */
66 static inline size_t align_up(size_t size, size_t align)
67 {
68 return (size + align - 1) & ~(align - 1);
69 }
71 static void maybe_split(struct xmalloc_hdr *hdr, size_t size, size_t block)
72 {
73 struct xmalloc_hdr *extra;
74 size_t leftover;
75 size = align_up(size, __alignof__(struct xmalloc_hdr));
76 size = align_up(size, __alignof__(struct xmalloc_pad));
77 leftover = block - size;
79 /* If enough is left to make a block, put it on free list. */
80 if ( leftover >= (2 * (sizeof(struct xmalloc_hdr) + sizeof(struct xmalloc_pad))) )
81 {
82 extra = (struct xmalloc_hdr *)((unsigned long)hdr + size);
83 extra->size = leftover;
84 /* spin_lock_irqsave(&freelist_lock, flags); */
85 minios_list_add(&extra->freelist, &freelist);
86 /* spin_unlock_irqrestore(&freelist_lock, flags); */
87 }
88 else
89 {
90 size = block;
91 }
93 hdr->size = size;
94 /* Debugging aid. */
95 hdr->freelist.next = hdr->freelist.prev = NULL;
96 }
98 static struct xmalloc_hdr *xmalloc_new_page(size_t size)
99 {
100 struct xmalloc_hdr *hdr;
101 /* unsigned long flags; */
103 hdr = (struct xmalloc_hdr *)alloc_page();
104 if ( hdr == NULL )
105 return NULL;
107 maybe_split(hdr, size, PAGE_SIZE);
109 return hdr;
110 }
112 /* Big object? Just use the page allocator. */
113 static void *xmalloc_whole_pages(size_t size, size_t align)
114 {
115 struct xmalloc_hdr *hdr;
116 struct xmalloc_pad *pad;
117 unsigned int pageorder;
118 void *ret;
119 /* Room for headers */
120 size_t hdr_size = sizeof(struct xmalloc_hdr) + sizeof(struct xmalloc_pad);
121 /* Align for actual beginning of data */
122 hdr_size = align_up(hdr_size, align);
124 pageorder = get_order(hdr_size + size);
126 hdr = (struct xmalloc_hdr *)alloc_pages(pageorder);
127 if ( hdr == NULL )
128 return NULL;
130 hdr->size = (1UL << (pageorder + PAGE_SHIFT));
131 /* Debugging aid. */
132 hdr->freelist.next = hdr->freelist.prev = NULL;
134 ret = (char*)hdr + hdr_size;
135 pad = (struct xmalloc_pad *) ret - 1;
136 pad->hdr_size = hdr_size;
137 return ret;
138 }
140 void *_xmalloc(size_t size, size_t align)
141 {
142 struct xmalloc_hdr *i, *tmp, *hdr = NULL;
143 uintptr_t data_begin;
144 size_t hdr_size;
145 /* unsigned long flags; */
147 hdr_size = sizeof(struct xmalloc_hdr) + sizeof(struct xmalloc_pad);
148 /* Align on headers requirements. */
149 align = align_up(align, __alignof__(struct xmalloc_hdr));
150 align = align_up(align, __alignof__(struct xmalloc_pad));
152 /* For big allocs, give them whole pages. */
153 if ( size + align_up(hdr_size, align) >= PAGE_SIZE )
154 return xmalloc_whole_pages(size, align);
156 /* Search free list. */
157 /* spin_lock_irqsave(&freelist_lock, flags); */
158 minios_list_for_each_entry_safe( i, tmp, &freelist, freelist )
159 {
160 data_begin = align_up((uintptr_t)i + hdr_size, align);
162 if ( data_begin + size > (uintptr_t)i + i->size )
163 continue;
165 minios_list_del(&i->freelist);
166 /* spin_unlock_irqrestore(&freelist_lock, flags); */
168 uintptr_t size_before = (data_begin - hdr_size) - (uintptr_t)i;
170 if (size_before >= 2 * hdr_size) {
171 /* Worth splitting the beginning */
172 struct xmalloc_hdr *new_i = (void*)(data_begin - hdr_size);
173 new_i->size = i->size - size_before;
174 i->size = size_before;
175 /* spin_lock_irqsave(&freelist_lock, flags); */
176 minios_list_add(&i->freelist, &freelist);
177 /* spin_unlock_irqrestore(&freelist_lock, flags); */
178 i = new_i;
179 }
180 maybe_split(i, (data_begin + size) - (uintptr_t)i, i->size);
181 hdr = i;
182 break;
183 }
185 if (!hdr) {
186 /* spin_unlock_irqrestore(&freelist_lock, flags); */
188 /* Alloc a new page and return from that. */
189 hdr = xmalloc_new_page(align_up(hdr_size, align) + size);
190 data_begin = (uintptr_t)hdr + align_up(hdr_size, align);
191 }
193 struct xmalloc_pad *pad = (struct xmalloc_pad *) data_begin - 1;
194 pad->hdr_size = data_begin - (uintptr_t)hdr;
195 BUG_ON(data_begin % align);
196 return (void*)data_begin;
197 }
199 void xfree(const void *p)
200 {
201 /* unsigned long flags; */
202 struct xmalloc_hdr *i, *tmp, *hdr;
203 struct xmalloc_pad *pad;
205 if ( p == NULL )
206 return;
208 pad = (struct xmalloc_pad *)p - 1;
209 hdr = (struct xmalloc_hdr *)((char *)p - pad->hdr_size);
211 /* Big allocs free directly. */
212 if ( hdr->size >= PAGE_SIZE )
213 {
214 free_pages(hdr, get_order(hdr->size));
215 return;
216 }
218 /* We know hdr will be on same page. */
219 if(((long)p & PAGE_MASK) != ((long)hdr & PAGE_MASK))
220 {
221 printk("Header should be on the same page\n");
222 *(int*)0=0;
223 }
225 /* Not previously freed. */
226 if(hdr->freelist.next || hdr->freelist.prev)
227 {
228 printk("Should not be previously freed\n");
229 *(int*)0=0;
230 }
232 /* Merge with other free block, or put in list. */
233 /* spin_lock_irqsave(&freelist_lock, flags); */
234 minios_list_for_each_entry_safe( i, tmp, &freelist, freelist )
235 {
236 unsigned long _i = (unsigned long)i;
237 unsigned long _hdr = (unsigned long)hdr;
239 /* Do not merge across page boundaries. */
240 if ( ((_i ^ _hdr) & PAGE_MASK) != 0 )
241 continue;
243 /* We follow this block? Swallow it. */
244 if ( (_i + i->size) == _hdr )
245 {
246 minios_list_del(&i->freelist);
247 i->size += hdr->size;
248 hdr = i;
249 }
251 /* We precede this block? Swallow it. */
252 if ( (_hdr + hdr->size) == _i )
253 {
254 minios_list_del(&i->freelist);
255 hdr->size += i->size;
256 }
257 }
259 /* Did we merge an entire page? */
260 if ( hdr->size == PAGE_SIZE )
261 {
262 if((((unsigned long)hdr) & (PAGE_SIZE-1)) != 0)
263 {
264 printk("Bug\n");
265 *(int*)0=0;
266 }
267 free_page(hdr);
268 }
269 else
270 {
271 minios_list_add(&hdr->freelist, &freelist);
272 }
274 /* spin_unlock_irqrestore(&freelist_lock, flags); */
275 }
277 void *_realloc(void *ptr, size_t size)
278 {
279 void *new;
280 struct xmalloc_hdr *hdr;
281 struct xmalloc_pad *pad;
283 if (ptr == NULL)
284 return _xmalloc(size, DEFAULT_ALIGN);
286 pad = (struct xmalloc_pad *)ptr - 1;
287 hdr = (struct xmalloc_hdr *)((char*)ptr - pad->hdr_size);
288 if (hdr->size >= size) {
289 maybe_split(hdr, size, hdr->size);
290 return ptr;
291 }
293 new = _xmalloc(size, DEFAULT_ALIGN);
294 if (new == NULL)
295 return NULL;
297 memcpy(new, ptr, hdr->size);
298 xfree(ptr);
300 return new;
301 }
302 #endif