ia64/xen-unstable

view extras/mini-os/lib/xmalloc.c @ 13878:9d103e5fd471

[XEN] Fix typos in comment describing 32on64 memory layout

Signed-off-by: Ian Campbell <ian.campbell@xensource.com>
author Ian Campbell <ian.campbell@xensource.com>
date Thu Feb 08 12:33:32 2007 +0000 (2007-02-08)
parents e9e327c3e81b
children 8984cc0a1d80
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 * Changes:
9 *
10 * Date: Aug 2005
11 *
12 * Environment: Xen Minimal OS
13 * Description: simple memory allocator
14 *
15 ****************************************************************************
16 * Simple allocator for Mini-os. If larger than a page, simply use the
17 * page-order allocator.
18 *
19 * Copy of the allocator for Xen by Rusty Russell:
20 * Copyright (C) 2005 Rusty Russell IBM Corporation
21 *
22 * This program is free software; you can redistribute it and/or modify
23 * it under the terms of the GNU General Public License as published by
24 * the Free Software Foundation; either version 2 of the License, or
25 * (at your option) any later version.
26 *
27 * This program is distributed in the hope that it will be useful,
28 * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 * GNU General Public License for more details.
31 *
32 * You should have received a copy of the GNU General Public License
33 * along with this program; if not, write to the Free Software
34 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
35 */
37 #include <os.h>
38 #include <mm.h>
39 #include <types.h>
40 #include <lib.h>
41 #include <list.h>
43 static LIST_HEAD(freelist);
44 /* static spinlock_t freelist_lock = SPIN_LOCK_UNLOCKED; */
46 struct xmalloc_hdr
47 {
48 /* Total including this hdr. */
49 size_t size;
50 struct list_head freelist;
51 #if defined(__ia64__)
52 // Needed for ia64 as long as the align parameter in _xmalloc()
53 // is not supported.
54 uint64_t pad;
55 #endif
57 } __cacheline_aligned;
59 static void maybe_split(struct xmalloc_hdr *hdr, size_t size, size_t block)
60 {
61 struct xmalloc_hdr *extra;
62 size_t leftover = block - size;
64 /* If enough is left to make a block, put it on free list. */
65 if ( leftover >= (2 * sizeof(struct xmalloc_hdr)) )
66 {
67 extra = (struct xmalloc_hdr *)((unsigned long)hdr + size);
68 extra->size = leftover;
69 list_add(&extra->freelist, &freelist);
70 }
71 else
72 {
73 size = block;
74 }
76 hdr->size = size;
77 /* Debugging aid. */
78 hdr->freelist.next = hdr->freelist.prev = NULL;
79 }
81 static void *xmalloc_new_page(size_t size)
82 {
83 struct xmalloc_hdr *hdr;
84 /* unsigned long flags; */
86 hdr = (struct xmalloc_hdr *)alloc_page();
87 if ( hdr == NULL )
88 return NULL;
90 /* spin_lock_irqsave(&freelist_lock, flags); */
91 maybe_split(hdr, size, PAGE_SIZE);
92 /* spin_unlock_irqrestore(&freelist_lock, flags); */
94 return hdr+1;
95 }
97 /* Big object? Just use the page allocator. */
98 static void *xmalloc_whole_pages(size_t size)
99 {
100 struct xmalloc_hdr *hdr;
101 unsigned int pageorder = get_order(size);
103 hdr = (struct xmalloc_hdr *)alloc_pages(pageorder);
104 if ( hdr == NULL )
105 return NULL;
107 hdr->size = (1 << (pageorder + PAGE_SHIFT));
108 /* Debugging aid. */
109 hdr->freelist.next = hdr->freelist.prev = NULL;
111 return hdr+1;
112 }
114 /* Return size, increased to alignment with align. */
115 static inline size_t align_up(size_t size, size_t align)
116 {
117 return (size + align - 1) & ~(align - 1);
118 }
120 void *_xmalloc(size_t size, size_t align)
121 {
122 struct xmalloc_hdr *i;
123 /* unsigned long flags; */
125 /* Add room for header, pad to align next header. */
126 size += sizeof(struct xmalloc_hdr);
127 size = align_up(size, __alignof__(struct xmalloc_hdr));
129 /* For big allocs, give them whole pages. */
130 if ( size >= PAGE_SIZE )
131 return xmalloc_whole_pages(size);
133 /* Search free list. */
134 /* spin_lock_irqsave(&freelist_lock, flags); */
135 list_for_each_entry( i, &freelist, freelist )
136 {
137 if ( i->size < size )
138 continue;
139 list_del(&i->freelist);
140 maybe_split(i, size, i->size);
141 /* spin_unlock_irqrestore(&freelist_lock, flags); */
142 return i+1;
143 }
144 /* spin_unlock_irqrestore(&freelist_lock, flags); */
146 /* Alloc a new page and return from that. */
147 return xmalloc_new_page(size);
148 }
150 void xfree(const void *p)
151 {
152 /* unsigned long flags; */
153 struct xmalloc_hdr *i, *tmp, *hdr;
155 if ( p == NULL )
156 return;
158 hdr = (struct xmalloc_hdr *)p - 1;
160 /* We know hdr will be on same page. */
161 if(((long)p & PAGE_MASK) != ((long)hdr & PAGE_MASK))
162 {
163 printk("Header should be on the same page\n");
164 *(int*)0=0;
165 }
167 /* Not previously freed. */
168 if(hdr->freelist.next || hdr->freelist.prev)
169 {
170 printk("Should not be previously freed\n");
171 *(int*)0=0;
172 }
174 /* Big allocs free directly. */
175 if ( hdr->size >= PAGE_SIZE )
176 {
177 free_pages(hdr, get_order(hdr->size));
178 return;
179 }
181 /* Merge with other free block, or put in list. */
182 /* spin_lock_irqsave(&freelist_lock, flags); */
183 list_for_each_entry_safe( i, tmp, &freelist, freelist )
184 {
185 unsigned long _i = (unsigned long)i;
186 unsigned long _hdr = (unsigned long)hdr;
188 /* Do not merge across page boundaries. */
189 if ( ((_i ^ _hdr) & PAGE_MASK) != 0 )
190 continue;
192 /* We follow this block? Swallow it. */
193 if ( (_i + i->size) == _hdr )
194 {
195 list_del(&i->freelist);
196 i->size += hdr->size;
197 hdr = i;
198 }
200 /* We precede this block? Swallow it. */
201 if ( (_hdr + hdr->size) == _i )
202 {
203 list_del(&i->freelist);
204 hdr->size += i->size;
205 }
206 }
208 /* Did we merge an entire page? */
209 if ( hdr->size == PAGE_SIZE )
210 {
211 if((((unsigned long)hdr) & (PAGE_SIZE-1)) != 0)
212 {
213 printk("Bug\n");
214 *(int*)0=0;
215 }
216 free_pages(hdr, 0);
217 }
218 else
219 {
220 list_add(&hdr->freelist, &freelist);
221 }
223 /* spin_unlock_irqrestore(&freelist_lock, flags); */
224 }