direct-io.hg

view extras/mini-os/mm.c @ 15481:538c3d8aa4b1

Revert 15471:7ac7f147241405af83e7a9d748cf7b01279734fc

Block-device specifiers in ioemu can contain colons, so skipping
always past the first colon is not a good idea. Better solutions are
in the pipeline to solve the blktap issues.

Signed-off-by: Keir Fraser <keir@xensource.com>
author kfraser@localhost.localdomain
date Fri Jul 06 15:01:20 2007 +0100 (2007-07-06)
parents bdebca505d8e
children
line source
1 /*
2 ****************************************************************************
3 * (C) 2003 - Rolf Neugebauer - Intel Research Cambridge
4 * (C) 2005 - Grzegorz Milos - Intel Research Cambridge
5 ****************************************************************************
6 *
7 * File: mm.c
8 * Author: Rolf Neugebauer (neugebar@dcs.gla.ac.uk)
9 * Changes: Grzegorz Milos
10 *
11 * Date: Aug 2003, chages Aug 2005
12 *
13 * Environment: Xen Minimal OS
14 * Description: memory management related functions
15 * contains buddy page allocator from Xen.
16 *
17 ****************************************************************************
18 * Permission is hereby granted, free of charge, to any person obtaining a copy
19 * of this software and associated documentation files (the "Software"), to
20 * deal in the Software without restriction, including without limitation the
21 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
22 * sell copies of the Software, and to permit persons to whom the Software is
23 * furnished to do so, subject to the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be included in
26 * all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
29 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
30 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
31 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
32 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
33 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
34 * DEALINGS IN THE SOFTWARE.
35 */
37 #include <os.h>
38 #include <hypervisor.h>
39 #include <mm.h>
40 #include <types.h>
41 #include <lib.h>
42 #include <xmalloc.h>
44 #ifdef MM_DEBUG
45 #define DEBUG(_f, _a...) \
46 printk("MINI_OS(file=mm.c, line=%d) " _f "\n", __LINE__, ## _a)
47 #else
48 #define DEBUG(_f, _a...) ((void)0)
49 #endif
51 /*********************
52 * ALLOCATION BITMAP
53 * One bit per page of memory. Bit set => page is allocated.
54 */
56 static unsigned long *alloc_bitmap;
57 #define PAGES_PER_MAPWORD (sizeof(unsigned long) * 8)
59 #define allocated_in_map(_pn) \
60 (alloc_bitmap[(_pn)/PAGES_PER_MAPWORD] & (1<<((_pn)&(PAGES_PER_MAPWORD-1))))
62 /*
63 * Hint regarding bitwise arithmetic in map_{alloc,free}:
64 * -(1<<n) sets all bits >= n.
65 * (1<<n)-1 sets all bits < n.
66 * Variable names in map_{alloc,free}:
67 * *_idx == Index into `alloc_bitmap' array.
68 * *_off == Bit offset within an element of the `alloc_bitmap' array.
69 */
71 static void map_alloc(unsigned long first_page, unsigned long nr_pages)
72 {
73 unsigned long start_off, end_off, curr_idx, end_idx;
75 curr_idx = first_page / PAGES_PER_MAPWORD;
76 start_off = first_page & (PAGES_PER_MAPWORD-1);
77 end_idx = (first_page + nr_pages) / PAGES_PER_MAPWORD;
78 end_off = (first_page + nr_pages) & (PAGES_PER_MAPWORD-1);
80 if ( curr_idx == end_idx )
81 {
82 alloc_bitmap[curr_idx] |= ((1<<end_off)-1) & -(1<<start_off);
83 }
84 else
85 {
86 alloc_bitmap[curr_idx] |= -(1<<start_off);
87 while ( ++curr_idx < end_idx ) alloc_bitmap[curr_idx] = ~0L;
88 alloc_bitmap[curr_idx] |= (1<<end_off)-1;
89 }
90 }
93 static void map_free(unsigned long first_page, unsigned long nr_pages)
94 {
95 unsigned long start_off, end_off, curr_idx, end_idx;
97 curr_idx = first_page / PAGES_PER_MAPWORD;
98 start_off = first_page & (PAGES_PER_MAPWORD-1);
99 end_idx = (first_page + nr_pages) / PAGES_PER_MAPWORD;
100 end_off = (first_page + nr_pages) & (PAGES_PER_MAPWORD-1);
102 if ( curr_idx == end_idx )
103 {
104 alloc_bitmap[curr_idx] &= -(1<<end_off) | ((1<<start_off)-1);
105 }
106 else
107 {
108 alloc_bitmap[curr_idx] &= (1<<start_off)-1;
109 while ( ++curr_idx != end_idx ) alloc_bitmap[curr_idx] = 0;
110 alloc_bitmap[curr_idx] &= -(1<<end_off);
111 }
112 }
116 /*************************
117 * BINARY BUDDY ALLOCATOR
118 */
120 typedef struct chunk_head_st chunk_head_t;
121 typedef struct chunk_tail_st chunk_tail_t;
123 struct chunk_head_st {
124 chunk_head_t *next;
125 chunk_head_t **pprev;
126 int level;
127 };
129 struct chunk_tail_st {
130 int level;
131 };
133 /* Linked lists of free chunks of different powers-of-two in size. */
134 #define FREELIST_SIZE ((sizeof(void*)<<3)-PAGE_SHIFT)
135 static chunk_head_t *free_head[FREELIST_SIZE];
136 static chunk_head_t free_tail[FREELIST_SIZE];
137 #define FREELIST_EMPTY(_l) ((_l)->next == NULL)
139 #define round_pgdown(_p) ((_p)&PAGE_MASK)
140 #define round_pgup(_p) (((_p)+(PAGE_SIZE-1))&PAGE_MASK)
142 #ifdef MM_DEBUG
143 /*
144 * Prints allocation[0/1] for @nr_pages, starting at @start
145 * address (virtual).
146 */
147 USED static void print_allocation(void *start, int nr_pages)
148 {
149 unsigned long pfn_start = virt_to_pfn(start);
150 int count;
151 for(count = 0; count < nr_pages; count++)
152 if(allocated_in_map(pfn_start + count)) printk("1");
153 else printk("0");
155 printk("\n");
156 }
158 /*
159 * Prints chunks (making them with letters) for @nr_pages starting
160 * at @start (virtual).
161 */
162 USED static void print_chunks(void *start, int nr_pages)
163 {
164 char chunks[1001], current='A';
165 int order, count;
166 chunk_head_t *head;
167 unsigned long pfn_start = virt_to_pfn(start);
169 memset(chunks, (int)'_', 1000);
170 if(nr_pages > 1000)
171 {
172 DEBUG("Can only pring 1000 pages. Increase buffer size.");
173 }
175 for(order=0; order < FREELIST_SIZE; order++)
176 {
177 head = free_head[order];
178 while(!FREELIST_EMPTY(head))
179 {
180 for(count = 0; count < 1<< head->level; count++)
181 {
182 if(count + virt_to_pfn(head) - pfn_start < 1000)
183 chunks[count + virt_to_pfn(head) - pfn_start] = current;
184 }
185 head = head->next;
186 current++;
187 }
188 }
189 chunks[nr_pages] = '\0';
190 printk("%s\n", chunks);
191 }
192 #endif
195 /*
196 * Initialise allocator, placing addresses [@min,@max] in free pool.
197 * @min and @max are PHYSICAL addresses.
198 */
199 static void init_page_allocator(unsigned long min, unsigned long max)
200 {
201 int i;
202 unsigned long range, bitmap_size;
203 chunk_head_t *ch;
204 chunk_tail_t *ct;
205 for ( i = 0; i < FREELIST_SIZE; i++ )
206 {
207 free_head[i] = &free_tail[i];
208 free_tail[i].pprev = &free_head[i];
209 free_tail[i].next = NULL;
210 }
212 min = round_pgup (min);
213 max = round_pgdown(max);
215 /* Allocate space for the allocation bitmap. */
216 bitmap_size = (max+1) >> (PAGE_SHIFT+3);
217 bitmap_size = round_pgup(bitmap_size);
218 alloc_bitmap = (unsigned long *)to_virt(min);
219 min += bitmap_size;
220 range = max - min;
222 /* All allocated by default. */
223 memset(alloc_bitmap, ~0, bitmap_size);
224 /* Free up the memory we've been given to play with. */
225 map_free(PHYS_PFN(min), range>>PAGE_SHIFT);
227 /* The buddy lists are addressed in high memory. */
228 min = (unsigned long) to_virt(min);
229 max = (unsigned long) to_virt(max);
231 while ( range != 0 )
232 {
233 /*
234 * Next chunk is limited by alignment of min, but also
235 * must not be bigger than remaining range.
236 */
237 for ( i = PAGE_SHIFT; (1<<(i+1)) <= range; i++ )
238 if ( min & (1<<i) ) break;
241 ch = (chunk_head_t *)min;
242 min += (1<<i);
243 range -= (1<<i);
244 ct = (chunk_tail_t *)min-1;
245 i -= PAGE_SHIFT;
246 ch->level = i;
247 ch->next = free_head[i];
248 ch->pprev = &free_head[i];
249 ch->next->pprev = &ch->next;
250 free_head[i] = ch;
251 ct->level = i;
252 }
253 }
256 /* Allocate 2^@order contiguous pages. Returns a VIRTUAL address. */
257 unsigned long alloc_pages(int order)
258 {
259 int i;
260 chunk_head_t *alloc_ch, *spare_ch;
261 chunk_tail_t *spare_ct;
264 /* Find smallest order which can satisfy the request. */
265 for ( i = order; i < FREELIST_SIZE; i++ ) {
266 if ( !FREELIST_EMPTY(free_head[i]) )
267 break;
268 }
270 if ( i == FREELIST_SIZE ) goto no_memory;
272 /* Unlink a chunk. */
273 alloc_ch = free_head[i];
274 free_head[i] = alloc_ch->next;
275 alloc_ch->next->pprev = alloc_ch->pprev;
277 /* We may have to break the chunk a number of times. */
278 while ( i != order )
279 {
280 /* Split into two equal parts. */
281 i--;
282 spare_ch = (chunk_head_t *)((char *)alloc_ch + (1<<(i+PAGE_SHIFT)));
283 spare_ct = (chunk_tail_t *)((char *)spare_ch + (1<<(i+PAGE_SHIFT)))-1;
285 /* Create new header for spare chunk. */
286 spare_ch->level = i;
287 spare_ch->next = free_head[i];
288 spare_ch->pprev = &free_head[i];
289 spare_ct->level = i;
291 /* Link in the spare chunk. */
292 spare_ch->next->pprev = &spare_ch->next;
293 free_head[i] = spare_ch;
294 }
296 map_alloc(PHYS_PFN(to_phys(alloc_ch)), 1<<order);
298 return((unsigned long)alloc_ch);
300 no_memory:
302 printk("Cannot handle page request order %d!\n", order);
304 return 0;
305 }
307 void free_pages(void *pointer, int order)
308 {
309 chunk_head_t *freed_ch, *to_merge_ch;
310 chunk_tail_t *freed_ct;
311 unsigned long mask;
313 /* First free the chunk */
314 map_free(virt_to_pfn(pointer), 1 << order);
316 /* Create free chunk */
317 freed_ch = (chunk_head_t *)pointer;
318 freed_ct = (chunk_tail_t *)((char *)pointer + (1<<(order + PAGE_SHIFT)))-1;
320 /* Now, possibly we can conseal chunks together */
321 while(order < FREELIST_SIZE)
322 {
323 mask = 1 << (order + PAGE_SHIFT);
324 if((unsigned long)freed_ch & mask)
325 {
326 to_merge_ch = (chunk_head_t *)((char *)freed_ch - mask);
327 if(allocated_in_map(virt_to_pfn(to_merge_ch)) ||
328 to_merge_ch->level != order)
329 break;
331 /* Merge with predecessor */
332 freed_ch = to_merge_ch;
333 }
334 else
335 {
336 to_merge_ch = (chunk_head_t *)((char *)freed_ch + mask);
337 if(allocated_in_map(virt_to_pfn(to_merge_ch)) ||
338 to_merge_ch->level != order)
339 break;
341 /* Merge with successor */
342 freed_ct = (chunk_tail_t *)((char *)to_merge_ch + mask) - 1;
343 }
345 /* We are commited to merging, unlink the chunk */
346 *(to_merge_ch->pprev) = to_merge_ch->next;
347 to_merge_ch->next->pprev = to_merge_ch->pprev;
349 order++;
350 }
352 /* Link the new chunk */
353 freed_ch->level = order;
354 freed_ch->next = free_head[order];
355 freed_ch->pprev = &free_head[order];
356 freed_ct->level = order;
358 freed_ch->next->pprev = &freed_ch->next;
359 free_head[order] = freed_ch;
361 }
365 void init_mm(void)
366 {
368 unsigned long start_pfn, max_pfn;
370 printk("MM: Init\n");
372 arch_init_mm(&start_pfn, &max_pfn);
373 /*
374 * now we can initialise the page allocator
375 */
376 printk("MM: Initialise page allocator for %lx(%lx)-%lx(%lx)\n",
377 (u_long)to_virt(PFN_PHYS(start_pfn)), PFN_PHYS(start_pfn),
378 (u_long)to_virt(PFN_PHYS(max_pfn)), PFN_PHYS(max_pfn));
379 init_page_allocator(PFN_PHYS(start_pfn), PFN_PHYS(max_pfn));
380 printk("MM: done\n");
382 arch_init_p2m(max_pfn);
384 arch_init_demand_mapping_area(max_pfn);
385 }
387 void sanity_check(void)
388 {
389 int x;
390 chunk_head_t *head;
392 for (x = 0; x < FREELIST_SIZE; x++) {
393 for (head = free_head[x]; !FREELIST_EMPTY(head); head = head->next) {
394 ASSERT(!allocated_in_map(virt_to_pfn(head)));
395 if (head->next)
396 ASSERT(head->next->pprev == &head->next);
397 }
398 if (free_head[x]) {
399 ASSERT(free_head[x]->pprev == &free_head[x]);
400 }
401 }
402 }