ia64/xen-unstable

view extras/mini-os/mm.c @ 16513:b1da8762f853

blktap: remove unused headers.

Attached patch removes unused linux specific headers
and makes bswap.h ready for BSD support.

This is first step for BSD support in blktap. More to come.
No functional change.

Signed-off-by: Christoph Egger <Christoph.Egger@amd.com>
author Keir Fraser <keir.fraser@citrix.com>
date Tue Dec 04 10:48:28 2007 +0000 (2007-12-04)
parents bdebca505d8e
children a905c582a406
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 }