ia64/xen-unstable

view extras/mini-os/lib/xmalloc.c @ 16827:5f3c236d1711

minios: Add align support to _xmalloc().

Signed-off-by: Samuel Thibault <samuel.thibault@eu.citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Tue Jan 22 09:45:54 2008 +0000 (2008-01-22)
parents 8984cc0a1d80
children 945820bfedb6
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 static LIST_HEAD(freelist);
47 /* static spinlock_t freelist_lock = SPIN_LOCK_UNLOCKED; */
49 struct xmalloc_hdr
50 {
51 /* Total including this hdr, unused padding and second hdr. */
52 size_t size;
53 struct list_head freelist;
54 } __cacheline_aligned;
56 /* Unused padding data between the two hdrs. */
58 struct xmalloc_pad
59 {
60 /* Size including both hdrs. */
61 size_t hdr_size;
62 };
64 static void maybe_split(struct xmalloc_hdr *hdr, size_t size, size_t block)
65 {
66 struct xmalloc_hdr *extra;
67 size_t leftover = block - size;
69 /* If enough is left to make a block, put it on free list. */
70 if ( leftover >= (2 * (sizeof(struct xmalloc_hdr) + sizeof(struct xmalloc_pad))) )
71 {
72 extra = (struct xmalloc_hdr *)((unsigned long)hdr + size);
73 extra->size = leftover;
74 /* spin_lock_irqsave(&freelist_lock, flags); */
75 list_add(&extra->freelist, &freelist);
76 /* spin_unlock_irqrestore(&freelist_lock, flags); */
77 }
78 else
79 {
80 size = block;
81 }
83 hdr->size = size;
84 /* Debugging aid. */
85 hdr->freelist.next = hdr->freelist.prev = NULL;
86 }
88 static struct xmalloc_hdr *xmalloc_new_page(size_t size)
89 {
90 struct xmalloc_hdr *hdr;
91 /* unsigned long flags; */
93 hdr = (struct xmalloc_hdr *)alloc_page();
94 if ( hdr == NULL )
95 return NULL;
97 maybe_split(hdr, size, PAGE_SIZE);
99 return hdr;
100 }
102 /* Return size, increased to alignment with align. */
103 static inline size_t align_up(size_t size, size_t align)
104 {
105 return (size + align - 1) & ~(align - 1);
106 }
108 /* Big object? Just use the page allocator. */
109 static void *xmalloc_whole_pages(size_t size, size_t align)
110 {
111 struct xmalloc_hdr *hdr;
112 struct xmalloc_pad *pad;
113 unsigned int pageorder;
114 void *ret;
115 /* Room for headers */
116 size_t hdr_size = sizeof(struct xmalloc_hdr) + sizeof(struct xmalloc_pad);
117 /* Align for actual beginning of data */
118 hdr_size = align_up(hdr_size, align);
120 pageorder = get_order(hdr_size + size);
122 hdr = (struct xmalloc_hdr *)alloc_pages(pageorder);
123 if ( hdr == NULL )
124 return NULL;
126 hdr->size = (1 << (pageorder + PAGE_SHIFT));
127 /* Debugging aid. */
128 hdr->freelist.next = hdr->freelist.prev = NULL;
130 ret = (char*)hdr + hdr_size;
131 pad = (struct xmalloc_pad *) ret - 1;
132 pad->hdr_size = hdr_size;
133 return ret;
134 }
136 void *_xmalloc(size_t size, size_t align)
137 {
138 struct xmalloc_hdr *i, *hdr = NULL;
139 uintptr_t data_begin;
140 size_t hdr_size;
141 /* unsigned long flags; */
143 hdr_size = sizeof(struct xmalloc_hdr) + sizeof(struct xmalloc_pad);
144 /* Align on headers requirements. */
145 align = align_up(align, __alignof__(struct xmalloc_hdr));
146 align = align_up(align, __alignof__(struct xmalloc_pad));
148 /* For big allocs, give them whole pages. */
149 if ( size + align_up(hdr_size, align) >= PAGE_SIZE )
150 return xmalloc_whole_pages(size, align);
152 /* Search free list. */
153 /* spin_lock_irqsave(&freelist_lock, flags); */
154 list_for_each_entry( i, &freelist, freelist )
155 {
156 data_begin = align_up((uintptr_t)i + hdr_size, align);
158 if ( data_begin + size > (uintptr_t)i + i->size )
159 continue;
161 list_del(&i->freelist);
162 /* spin_unlock_irqrestore(&freelist_lock, flags); */
164 uintptr_t size_before = (data_begin - hdr_size) - (uintptr_t)i;
166 if (size_before >= 2 * hdr_size) {
167 /* Worth splitting the beginning */
168 struct xmalloc_hdr *new_i = (void*)(data_begin - hdr_size);
169 new_i->size = i->size - size_before;
170 i->size = size_before;
171 /* spin_lock_irqsave(&freelist_lock, flags); */
172 list_add(&i->freelist, &freelist);
173 /* spin_unlock_irqrestore(&freelist_lock, flags); */
174 i = new_i;
175 }
176 maybe_split(i, (data_begin + size) - (uintptr_t)i, i->size);
177 hdr = i;
178 break;
179 }
181 if (!hdr) {
182 /* spin_unlock_irqrestore(&freelist_lock, flags); */
184 /* Alloc a new page and return from that. */
185 hdr = xmalloc_new_page(align_up(hdr_size, align) + size);
186 data_begin = (uintptr_t)hdr + align_up(hdr_size, align);
187 }
189 struct xmalloc_pad *pad = (struct xmalloc_pad *) data_begin - 1;
190 pad->hdr_size = data_begin - (uintptr_t)hdr;
191 BUG_ON(data_begin % align);
192 return (void*)data_begin;
193 }
195 void xfree(const void *p)
196 {
197 /* unsigned long flags; */
198 struct xmalloc_hdr *i, *tmp, *hdr;
199 struct xmalloc_pad *pad;
201 if ( p == NULL )
202 return;
204 pad = (struct xmalloc_pad *)p - 1;
205 hdr = (struct xmalloc_hdr *)((char *)p - pad->hdr_size);
207 /* We know hdr will be on same page. */
208 if(((long)p & PAGE_MASK) != ((long)hdr & PAGE_MASK))
209 {
210 printk("Header should be on the same page\n");
211 *(int*)0=0;
212 }
214 /* Not previously freed. */
215 if(hdr->freelist.next || hdr->freelist.prev)
216 {
217 printk("Should not be previously freed\n");
218 *(int*)0=0;
219 }
221 /* Big allocs free directly. */
222 if ( hdr->size >= PAGE_SIZE )
223 {
224 free_pages(hdr, get_order(hdr->size));
225 return;
226 }
228 /* Merge with other free block, or put in list. */
229 /* spin_lock_irqsave(&freelist_lock, flags); */
230 list_for_each_entry_safe( i, tmp, &freelist, freelist )
231 {
232 unsigned long _i = (unsigned long)i;
233 unsigned long _hdr = (unsigned long)hdr;
235 /* Do not merge across page boundaries. */
236 if ( ((_i ^ _hdr) & PAGE_MASK) != 0 )
237 continue;
239 /* We follow this block? Swallow it. */
240 if ( (_i + i->size) == _hdr )
241 {
242 list_del(&i->freelist);
243 i->size += hdr->size;
244 hdr = i;
245 }
247 /* We precede this block? Swallow it. */
248 if ( (_hdr + hdr->size) == _i )
249 {
250 list_del(&i->freelist);
251 hdr->size += i->size;
252 }
253 }
255 /* Did we merge an entire page? */
256 if ( hdr->size == PAGE_SIZE )
257 {
258 if((((unsigned long)hdr) & (PAGE_SIZE-1)) != 0)
259 {
260 printk("Bug\n");
261 *(int*)0=0;
262 }
263 free_pages(hdr, 0);
264 }
265 else
266 {
267 list_add(&hdr->freelist, &freelist);
268 }
270 /* spin_unlock_irqrestore(&freelist_lock, flags); */
271 }
273 void *_realloc(void *ptr, size_t size)
274 {
275 void *new;
276 struct xmalloc_hdr *hdr;
277 struct xmalloc_pad *pad;
279 if (ptr == NULL)
280 return _xmalloc(size, DEFAULT_ALIGN);
282 pad = (struct xmalloc_pad *)ptr - 1;
283 hdr = (struct xmalloc_hdr *)((char*)ptr - pad->hdr_size);
284 if (hdr->size >= size) {
285 maybe_split(hdr, size, hdr->size);
286 return ptr;
287 }
289 new = _xmalloc(size, DEFAULT_ALIGN);
290 if (new == NULL)
291 return NULL;
293 memcpy(new, ptr, hdr->size);
294 xfree(ptr);
296 return new;
297 }