ia64/xen-unstable

view extras/mini-os/mm.c @ 810:3f44ecdcb631

bitkeeper revision 1.499 (3f867c85oOyUdtcboCzrLgktKtvdgA)

ac_timer.h, ac_timer.c:
Xen ac timers now use a heap to find earliest timeout.
author kaf24@scramble.cl.cam.ac.uk
date Fri Oct 10 09:31:49 2003 +0000 (2003-10-10)
parents 209fcea923d4
children 71f9c171157e
line source
1 /* -*- Mode:C; c-basic-offset:4; tab-width:4 -*-
2 ****************************************************************************
3 * (C) 2003 - Rolf Neugebauer - Intel Research Cambridge
4 ****************************************************************************
5 *
6 * File: mm.c
7 * Author: Rolf Neugebauer (neugebar@dcs.gla.ac.uk)
8 * Changes:
9 *
10 * Date: Aug 2003
11 *
12 * Environment: Xen Minimal OS
13 * Description: memory management related functions
14 * contains buddy page allocator from Xen.
15 *
16 ****************************************************************************
17 * $Id: c-insert.c,v 1.7 2002/11/08 16:04:34 rn Exp $
18 ****************************************************************************
19 * This program is free software; you can redistribute it and/or modify
20 * it under the terms of the GNU General Public License as published by
21 * the Free Software Foundation; either version 2 of the License, or
22 * (at your option) any later version.
23 *
24 * This program is distributed in the hope that it will be useful,
25 * but WITHOUT ANY WARRANTY; without even the implied warranty of
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27 * GNU General Public License for more details.
28 *
29 * You should have received a copy of the GNU General Public License
30 * along with this program; if not, write to the Free Software
31 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
32 */
34 #include <os.h>
35 #include <hypervisor.h>
36 #include <mm.h>
37 #include <types.h>
38 #include <lib.h>
40 unsigned long *phys_to_machine_mapping;
41 extern char *stack;
42 extern char _text, _etext, _edata, _end;
44 static void init_page_allocator(unsigned long min, unsigned long max);
46 void init_mm(void)
47 {
49 unsigned long start_pfn, max_pfn, max_free_pfn;
51 unsigned long *pgd = (unsigned long *)start_info.pt_base;
53 printk("MM: Init\n");
55 printk(" _text: %p\n", &_text);
56 printk(" _etext: %p\n", &_etext);
57 printk(" _edata: %p\n", &_edata);
58 printk(" stack start: %p\n", &stack);
59 printk(" _end: %p\n", &_end);
61 /* set up minimal memory infos */
62 start_pfn = PFN_UP(__pa(&_end));
63 max_pfn = start_info.nr_pages;
65 printk(" start_pfn: %lx\n", start_pfn);
66 printk(" max_pfn: %lx\n", max_pfn);
68 /*
69 * we know where free tables start (start_pfn) and how many we
70 * have (max_pfn).
71 *
72 * Currently the hypervisor stores page tables it providesin the
73 * high region of the this memory range.
74 *
75 * next we work out how far down this goes (max_free_pfn)
76 *
77 * XXX this assumes the hypervisor provided page tables to be in
78 * the upper region of our initial memory. I don't know if this
79 * is always true.
80 */
82 max_free_pfn = PFN_DOWN(__pa(pgd));
83 {
84 unsigned long *pgd = (unsigned long *)start_info.pt_base;
85 unsigned long pte;
86 int i;
87 printk(" pgd(pa(pgd)): %lx(%lx)", (u_long)pgd, __pa(pgd));
89 for ( i = 0; i < (HYPERVISOR_VIRT_START>>22); i++ )
90 {
91 unsigned long pgde = *pgd++;
92 if ( !(pgde & 1) ) continue;
93 pte = machine_to_phys(pgde & PAGE_MASK);
94 printk(" PT(%x): %lx(%lx)", i, (u_long)__va(pte), pte);
95 if (PFN_DOWN(pte) <= max_free_pfn)
96 max_free_pfn = PFN_DOWN(pte);
97 }
98 }
99 max_free_pfn--;
100 printk(" max_free_pfn: %lx\n", max_free_pfn);
102 /*
103 * now we can initialise the page allocator
104 */
105 printk("MM: Initialise page allocator for %lx(%lx)-%lx(%lx)\n",
106 (u_long)__va(PFN_PHYS(start_pfn)), PFN_PHYS(start_pfn),
107 (u_long)__va(PFN_PHYS(max_free_pfn)), PFN_PHYS(max_free_pfn));
108 init_page_allocator(PFN_PHYS(start_pfn), PFN_PHYS(max_free_pfn));
111 /* Now initialise the physical->machine mapping table. */
114 printk("MM: done\n");
117 }
119 /*********************
120 * ALLOCATION BITMAP
121 * One bit per page of memory. Bit set => page is allocated.
122 */
124 static unsigned long *alloc_bitmap;
125 #define PAGES_PER_MAPWORD (sizeof(unsigned long) * 8)
127 #define allocated_in_map(_pn) \
128 (alloc_bitmap[(_pn)/PAGES_PER_MAPWORD] & (1<<((_pn)&(PAGES_PER_MAPWORD-1))))
131 /*
132 * Hint regarding bitwise arithmetic in map_{alloc,free}:
133 * -(1<<n) sets all bits >= n.
134 * (1<<n)-1 sets all bits < n.
135 * Variable names in map_{alloc,free}:
136 * *_idx == Index into `alloc_bitmap' array.
137 * *_off == Bit offset within an element of the `alloc_bitmap' array.
138 */
140 static void map_alloc(unsigned long first_page, unsigned long nr_pages)
141 {
142 unsigned long start_off, end_off, curr_idx, end_idx;
144 curr_idx = first_page / PAGES_PER_MAPWORD;
145 start_off = first_page & (PAGES_PER_MAPWORD-1);
146 end_idx = (first_page + nr_pages) / PAGES_PER_MAPWORD;
147 end_off = (first_page + nr_pages) & (PAGES_PER_MAPWORD-1);
149 if ( curr_idx == end_idx )
150 {
151 alloc_bitmap[curr_idx] |= ((1<<end_off)-1) & -(1<<start_off);
152 }
153 else
154 {
155 alloc_bitmap[curr_idx] |= -(1<<start_off);
156 while ( ++curr_idx < end_idx ) alloc_bitmap[curr_idx] = ~0L;
157 alloc_bitmap[curr_idx] |= (1<<end_off)-1;
158 }
159 }
162 static void map_free(unsigned long first_page, unsigned long nr_pages)
163 {
164 unsigned long start_off, end_off, curr_idx, end_idx;
166 curr_idx = first_page / PAGES_PER_MAPWORD;
167 start_off = first_page & (PAGES_PER_MAPWORD-1);
168 end_idx = (first_page + nr_pages) / PAGES_PER_MAPWORD;
169 end_off = (first_page + nr_pages) & (PAGES_PER_MAPWORD-1);
171 if ( curr_idx == end_idx )
172 {
173 alloc_bitmap[curr_idx] &= -(1<<end_off) | ((1<<start_off)-1);
174 }
175 else
176 {
177 alloc_bitmap[curr_idx] &= (1<<start_off)-1;
178 while ( ++curr_idx != end_idx ) alloc_bitmap[curr_idx] = 0;
179 alloc_bitmap[curr_idx] &= -(1<<end_off);
180 }
181 }
185 /*************************
186 * BINARY BUDDY ALLOCATOR
187 */
189 typedef struct chunk_head_st chunk_head_t;
190 typedef struct chunk_tail_st chunk_tail_t;
192 struct chunk_head_st {
193 chunk_head_t *next;
194 chunk_head_t **pprev;
195 int level;
196 };
198 struct chunk_tail_st {
199 int level;
200 };
202 /* Linked lists of free chunks of different powers-of-two in size. */
203 #define FREELIST_SIZE ((sizeof(void*)<<3)-PAGE_SHIFT)
204 static chunk_head_t *free_head[FREELIST_SIZE];
205 static chunk_head_t free_tail[FREELIST_SIZE];
206 #define FREELIST_EMPTY(_l) ((_l)->next == NULL)
208 #define round_pgdown(_p) ((_p)&PAGE_MASK)
209 #define round_pgup(_p) (((_p)+(PAGE_SIZE-1))&PAGE_MASK)
212 /*
213 * Initialise allocator, placing addresses [@min,@max] in free pool.
214 * @min and @max are PHYSICAL addresses.
215 */
216 static void init_page_allocator(unsigned long min, unsigned long max)
217 {
218 int i;
219 unsigned long range, bitmap_size;
220 chunk_head_t *ch;
221 chunk_tail_t *ct;
223 for ( i = 0; i < FREELIST_SIZE; i++ )
224 {
225 free_head[i] = &free_tail[i];
226 free_tail[i].pprev = &free_head[i];
227 free_tail[i].next = NULL;
228 }
230 min = round_pgup (min);
231 max = round_pgdown(max);
233 /* Allocate space for the allocation bitmap. */
234 bitmap_size = (max+1) >> (PAGE_SHIFT+3);
235 bitmap_size = round_pgup(bitmap_size);
236 alloc_bitmap = (unsigned long *)__va(min);
237 min += bitmap_size;
238 range = max - min;
240 /* All allocated by default. */
241 memset(alloc_bitmap, ~0, bitmap_size);
242 /* Free up the memory we've been given to play with. */
243 map_free(min>>PAGE_SHIFT, range>>PAGE_SHIFT);
245 /* The buddy lists are addressed in high memory. */
246 min += PAGE_OFFSET;
247 max += PAGE_OFFSET;
249 while ( range != 0 )
250 {
251 /*
252 * Next chunk is limited by alignment of min, but also
253 * must not be bigger than remaining range.
254 */
255 for ( i = PAGE_SHIFT; (1<<(i+1)) <= range; i++ )
256 if ( min & (1<<i) ) break;
259 ch = (chunk_head_t *)min;
260 min += (1<<i);
261 range -= (1<<i);
262 ct = (chunk_tail_t *)min-1;
263 i -= PAGE_SHIFT;
264 ch->level = i;
265 ch->next = free_head[i];
266 ch->pprev = &free_head[i];
267 ch->next->pprev = &ch->next;
268 free_head[i] = ch;
269 ct->level = i;
270 }
271 }
274 /* Release a PHYSICAL address range to the allocator. */
275 void release_bytes_to_allocator(unsigned long min, unsigned long max)
276 {
277 min = round_pgup (min) + PAGE_OFFSET;
278 max = round_pgdown(max) + PAGE_OFFSET;
280 while ( min < max )
281 {
282 __free_pages(min, 0);
283 min += PAGE_SIZE;
284 }
285 }
288 /* Allocate 2^@order contiguous pages. Returns a VIRTUAL address. */
289 unsigned long __get_free_pages(int order)
290 {
291 int i;
292 chunk_head_t *alloc_ch, *spare_ch;
293 chunk_tail_t *spare_ct;
296 /* Find smallest order which can satisfy the request. */
297 for ( i = order; i < FREELIST_SIZE; i++ ) {
298 if ( !FREELIST_EMPTY(free_head[i]) )
299 break;
300 }
302 if ( i == FREELIST_SIZE ) goto no_memory;
304 /* Unlink a chunk. */
305 alloc_ch = free_head[i];
306 free_head[i] = alloc_ch->next;
307 alloc_ch->next->pprev = alloc_ch->pprev;
309 /* We may have to break the chunk a number of times. */
310 while ( i != order )
311 {
312 /* Split into two equal parts. */
313 i--;
314 spare_ch = (chunk_head_t *)((char *)alloc_ch + (1<<(i+PAGE_SHIFT)));
315 spare_ct = (chunk_tail_t *)((char *)spare_ch + (1<<(i+PAGE_SHIFT)))-1;
317 /* Create new header for spare chunk. */
318 spare_ch->level = i;
319 spare_ch->next = free_head[i];
320 spare_ch->pprev = &free_head[i];
321 spare_ct->level = i;
323 /* Link in the spare chunk. */
324 spare_ch->next->pprev = &spare_ch->next;
325 free_head[i] = spare_ch;
326 }
328 map_alloc(__pa(alloc_ch)>>PAGE_SHIFT, 1<<order);
330 return((unsigned long)alloc_ch);
332 no_memory:
334 printk("Cannot handle page request order %d!\n", order);
336 return 0;
337 }
340 /* Free 2^@order pages at VIRTUAL address @p. */
341 void __free_pages(unsigned long p, int order)
342 {
343 unsigned long size = 1 << (order + PAGE_SHIFT);
344 chunk_head_t *ch;
345 chunk_tail_t *ct;
346 unsigned long pagenr = __pa(p) >> PAGE_SHIFT;
348 map_free(pagenr, 1<<order);
350 /* Merge chunks as far as possible. */
351 for ( ; ; )
352 {
353 if ( (p & size) )
354 {
355 /* Merge with predecessor block? */
356 if ( allocated_in_map(pagenr-1) ) break;
357 ct = (chunk_tail_t *)p - 1;
358 if ( ct->level != order ) break;
359 ch = (chunk_head_t *)(p - size);
360 p -= size;
361 }
362 else
363 {
364 /* Merge with successor block? */
365 if ( allocated_in_map(pagenr+(1<<order)) ) break;
366 ch = (chunk_head_t *)(p + size);
367 if ( ch->level != order ) break;
368 }
370 /* Okay, unlink the neighbour. */
371 *ch->pprev = ch->next;
372 ch->next->pprev = ch->pprev;
374 order++;
375 size <<= 1;
376 }
378 /* Okay, add the final chunk to the appropriate free list. */
379 ch = (chunk_head_t *)p;
380 ct = (chunk_tail_t *)(p+size)-1;
381 ct->level = order;
382 ch->level = order;
383 ch->pprev = &free_head[order];
384 ch->next = free_head[order];
385 ch->next->pprev = &ch->next;
386 free_head[order] = ch;
387 }