![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to linux_kmem.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GnuMach] / Gnu-Mach / i386 / i386at / gpl / linux|
Return to linux_kmem.c CVS log | Up to [GnuMach] / Gnu-Mach / i386 / i386at / gpl / linux |
1.1 root 1: /*
2: * Linux memory allocation.
3: *
4: * Copyright (C) 1996 The University of Utah and the Computer Systems
5: * Laboratory at the University of Utah (CSL)
6: *
7: * This program is free software; you can redistribute it and/or modify
8: * it under the terms of the GNU General Public License as published by
9: * the Free Software Foundation; either version 2, or (at your option)
10: * any later version.
11: *
12: * This program is distributed in the hope that it will be useful,
13: * but WITHOUT ANY WARRANTY; without even the implied warranty of
14: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15: * GNU General Public License for more details.
16: *
17: * You should have received a copy of the GNU General Public License
18: * along with this program; if not, write to the Free Software
19: * Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
20: *
21: * Author: Shantanu Goel, University of Utah CSL
22: *
23: */
24:
25: #include <sys/types.h>
26:
27: #include <mach/mach_types.h>
28: #include <mach/vm_param.h>
29:
30: #include <kern/assert.h>
31: #include <kern/kalloc.h>
32:
33: #include <vm/vm_page.h>
34:
35: #include <i386at/gpl/linux/linux_emul.h>
36:
37: #define MACH_INCLUDE
38: #include <linux/sched.h>
39: #include <linux/malloc.h>
40: #include <linux/delay.h>
41:
42: #include <asm/system.h>
43:
44: /* Amount of memory to reserve for Linux memory allocator.
45: We reserve 64K chunks to stay within DMA limits.
46: Increase MEM_CHUNKS if the kernel is running out of memory. */
47: #define MEM_CHUNK_SIZE (64 * 1024)
48: #define MEM_CHUNKS 3
49:
50: /* Mininum amount that linux_kmalloc will allocate. */
51: #define MIN_ALLOC 12
52:
53: #ifndef NBPW
54: #define NBPW 32
55: #endif
56:
57: /* Memory block header. */
58: struct blkhdr
59: {
60: unsigned short free; /* 1 if block is free */
61: unsigned short size; /* size of block */
62: };
63:
64: /* This structure heads a page allocated by linux_kmalloc. */
65: struct pagehdr
66: {
67: unsigned size; /* size (multiple of PAGE_SIZE) */
68: struct pagehdr *next; /* next header in list */
69: };
70:
71: /* This structure describes a memory chunk. */
72: struct chunkhdr
73: {
74: unsigned long start; /* start address */
75: unsigned long end; /* end address */
76: unsigned long bitmap; /* busy/free bitmap of pages */
77: };
78:
79: /* Chunks from which pages are allocated. */
80: static struct chunkhdr pages_free[MEM_CHUNKS];
81:
82: /* Memory list maintained by linux_kmalloc. */
83: static struct pagehdr *memlist;
84:
85: /* Some statistics. */
86: int num_block_coalesce = 0;
87: int num_page_collect = 0;
88: int linux_mem_avail;
89:
90: /* Initialize the Linux memory allocator. */
91: void
92: linux_kmem_init ()
93: {
94: int i, j;
95: vm_page_t p, pages;
96:
97: for (i = 0; i < MEM_CHUNKS; i++)
98: {
99: /* Allocate memory. */
100: pages_free[i].start = (unsigned long) alloc_contig_mem (MEM_CHUNK_SIZE,
101: 16 * 1024 * 1024,
102: 0xffff, &pages);
103:
104: assert (pages_free[i].start);
105: assert ((pages_free[i].start & 0xffff) == 0);
106:
107: /* Sanity check: ensure pages are contiguous and within DMA limits. */
108: for (p = pages, j = 0; j < MEM_CHUNK_SIZE - PAGE_SIZE; j += PAGE_SIZE)
109: {
110: assert (p->phys_addr < 16 * 1024 * 1024);
111: assert (p->phys_addr + PAGE_SIZE
112: == ((vm_page_t) p->pageq.next)->phys_addr);
113:
114: p = (vm_page_t) p->pageq.next;
115: }
116:
117: pages_free[i].end = pages_free[i].start + MEM_CHUNK_SIZE;
118:
119: /* Initialize free page bitmap. */
120: pages_free[i].bitmap = 0;
121: j = MEM_CHUNK_SIZE >> PAGE_SHIFT;
122: while (--j >= 0)
123: pages_free[i].bitmap |= 1 << j;
124: }
125:
126: linux_mem_avail = (MEM_CHUNKS * MEM_CHUNK_SIZE) >> PAGE_SHIFT;
127: }
128:
129: /* Return the number by which the page size should be
130: shifted such that the resulting value is >= SIZE. */
131: static unsigned long
132: get_page_order (int size)
133: {
134: unsigned long order;
135:
136: for (order = 0; (PAGE_SIZE << order) < size; order++)
137: ;
138: return order;
139: }
140:
141: #ifdef LINUX_DEV_DEBUG
142: static void
143: check_page_list (int line)
144: {
145: unsigned size;
146: struct pagehdr *ph;
147: struct blkhdr *bh;
148:
149: for (ph = memlist; ph; ph = ph->next)
150: {
151: if ((int) ph & PAGE_MASK)
152: panic ("%s:%d: page header not aligned", __FILE__, line);
153:
154: size = 0;
155: bh = (struct blkhdr *) (ph + 1);
156: while (bh < (struct blkhdr *) ((void *) ph + ph->size))
157: {
158: size += bh->size + sizeof (struct blkhdr);
159: bh = (void *) (bh + 1) + bh->size;
160: }
161:
162: if (size + sizeof (struct pagehdr) != ph->size)
163: panic ("%s:%d: memory list destroyed", __FILE__, line);
164: }
165: }
166: #else
167: #define check_page_list(line)
168: #endif
169:
170: /* Merge adjacent free blocks in the memory list. */
171: static void
172: coalesce_blocks ()
173: {
174: struct pagehdr *ph;
175: struct blkhdr *bh, *bhp, *ebh;
176:
177: num_block_coalesce++;
178:
179: for (ph = memlist; ph; ph = ph->next)
180: {
181: bh = (struct blkhdr *) (ph + 1);
182: ebh = (struct blkhdr *) ((void *) ph + ph->size);
183: while (1)
184: {
185: /* Skip busy blocks. */
186: while (bh < ebh && ! bh->free)
187: bh = (struct blkhdr *) ((void *) (bh + 1) + bh->size);
188: if (bh == ebh)
189: break;
190:
191: /* Merge adjacent free blocks. */
192: while (1)
193: {
194: bhp = (struct blkhdr *) ((void *) (bh + 1) + bh->size);
195: if (bhp == ebh)
196: {
197: bh = bhp;
198: break;
199: }
200: if (! bhp->free)
201: {
202: bh = (struct blkhdr *) ((void *) (bhp + 1) + bhp->size);
203: break;
204: }
205: bh->size += bhp->size + sizeof (struct blkhdr);
206: }
207: }
208: }
209: }
210:
211: /* Allocate SIZE bytes of memory.
212: The PRIORITY parameter specifies various flags
213: such as DMA, atomicity, etc. It is not used by Mach. */
214: void *
215: linux_kmalloc (unsigned int size, int priority)
216: {
217: int order, coalesced = 0;
218: unsigned flags;
219: struct pagehdr *ph;
220: struct blkhdr *bh, *new_bh;
221:
222: if (size < MIN_ALLOC)
223: size = MIN_ALLOC;
224: else
225: size = (size + sizeof (int) - 1) & ~(sizeof (int) - 1);
226:
227: assert (size <= (MEM_CHUNK_SIZE
228: - sizeof (struct pagehdr)
229: - sizeof (struct blkhdr)));
230:
231: save_flags (flags);
232: cli ();
233:
234: again:
235: check_page_list (__LINE__);
236:
237: /* Walk the page list and find the first free block with size
238: greater than or equal to the one required. */
239: for (ph = memlist; ph; ph = ph->next)
240: {
241: bh = (struct blkhdr *) (ph + 1);
242: while (bh < (struct blkhdr *) ((void *) ph + ph->size))
243: {
244: if (bh->free && bh->size >= size)
245: {
246: bh->free = 0;
247: if (bh->size - size >= MIN_ALLOC + sizeof (struct blkhdr))
248: {
249: /* Split the current block and create a new free block. */
250: new_bh = (void *) (bh + 1) + size;
251: new_bh->free = 1;
252: new_bh->size = bh->size - size - sizeof (struct blkhdr);
253: bh->size = size;
254: }
255:
256: check_page_list (__LINE__);
257:
258: restore_flags (flags);
259: return bh + 1;
260: }
261: bh = (void *) (bh + 1) + bh->size;
262: }
263: }
264:
265: check_page_list (__LINE__);
266:
267: /* Allocation failed; coalesce free blocks and try again. */
268: if (! coalesced)
269: {
270: coalesce_blocks ();
271: coalesced = 1;
272: goto again;
273: }
274:
275: /* Allocate more pages. */
276: order = get_page_order (size
277: + sizeof (struct pagehdr)
278: + sizeof (struct blkhdr));
279: ph = (struct pagehdr *) __get_free_pages (GFP_KERNEL, order, ~0UL);
280: if (! ph)
281: {
282: restore_flags (flags);
283: return NULL;
284: }
285:
286: ph->size = PAGE_SIZE << order;
287: ph->next = memlist;
288: memlist = ph;
289: bh = (struct blkhdr *) (ph + 1);
290: bh->free = 0;
291: bh->size = ph->size - sizeof (struct pagehdr) - sizeof (struct blkhdr);
292: if (bh->size - size >= MIN_ALLOC + sizeof (struct blkhdr))
293: {
294: new_bh = (void *) (bh + 1) + size;
295: new_bh->free = 1;
296: new_bh->size = bh->size - size - sizeof (struct blkhdr);
297: bh->size = size;
298: }
299:
300: check_page_list (__LINE__);
301:
302: restore_flags (flags);
303: return bh + 1;
304: }
305:
306: /* Free memory P previously allocated by linux_kmalloc. */
307: void
308: linux_kfree (void *p)
309: {
310: unsigned flags;
311: struct blkhdr *bh, *bhp;
312: struct pagehdr *ph;
313:
314: assert (((int) p & (sizeof (int) - 1)) == 0);
315:
316: save_flags (flags);
317: cli ();
318:
319: check_page_list (__LINE__);
320:
321: for (ph = memlist; ph; ph = ph->next)
322: if (p >= (void *) ph && p < (void *) ph + ph->size)
323: break;
324:
325: assert (ph);
326:
327: bh = (struct blkhdr *) p - 1;
328:
329: assert (! bh->free);
330: assert (bh->size >= MIN_ALLOC);
331: assert ((bh->size & (sizeof (int) - 1)) == 0);
332:
333: bh->free = 1;
334:
335: check_page_list (__LINE__);
336:
337: restore_flags (flags);
338: }
339:
340: /* Free any pages that are not in use.
341: Called by __get_free_pages when pages are running low. */
342: static void
343: collect_kmalloc_pages ()
344: {
345: struct blkhdr *bh;
346: struct pagehdr *ph, **prev_ph;
347:
348: check_page_list (__LINE__);
349:
350: coalesce_blocks ();
351:
352: check_page_list (__LINE__);
353:
354: ph = memlist;
355: prev_ph = &memlist;
356: while (ph)
357: {
358: bh = (struct blkhdr *) (ph + 1);
359: if (bh->free && (void *) (bh + 1) + bh->size == (void *) ph + ph->size)
360: {
361: *prev_ph = ph->next;
362: free_pages ((unsigned long) ph, get_page_order (ph->size));
363: ph = *prev_ph;
364: }
365: else
366: {
367: prev_ph = &ph->next;
368: ph = ph->next;
369: }
370: }
371:
372: check_page_list (__LINE__);
373: }
374:
375: /* Allocate ORDER + 1 number of physically contiguous pages.
376: PRIORITY and MAX_ADDR are not used in Mach.
377:
378: XXX: This needs to be dynamic. To do that we need to make
379: the Mach page manipulation routines interrupt safe and they
380: must provide machine dependant hooks. */
381: unsigned long
382: __get_free_pages (int priority, unsigned long order, unsigned long max_addr)
383: {
384: int i, pages_collected = 0;
385: unsigned flags, bits, off, j, len;
386:
387: assert ((PAGE_SIZE << order) <= MEM_CHUNK_SIZE);
388:
389: /* Construct bitmap of contiguous pages. */
390: bits = 0;
391: j = 0;
392: len = 0;
393: while (len < (PAGE_SIZE << order))
394: {
395: bits |= 1 << j++;
396: len += PAGE_SIZE;
397: }
398:
399: again:
400: save_flags (flags);
401: cli ();
402:
403: /* Search each chunk for the required number of contiguous pages. */
404: for (i = 0; i < MEM_CHUNKS; i++)
405: {
406: off = 0;
407: j = bits;
408: while (MEM_CHUNK_SIZE - off >= (PAGE_SIZE << order))
409: {
410: if ((pages_free[i].bitmap & j) == j)
411: {
412: pages_free[i].bitmap &= ~j;
413: linux_mem_avail -= order + 1;
414: restore_flags (flags);
415: return pages_free[i].start + off;
416: }
417: j <<= 1;
418: off += PAGE_SIZE;
419: }
420: }
421:
422: /* Allocation failed; collect kmalloc and buffer pages
423: and try again. */
424: if (! pages_collected)
425: {
426: num_page_collect++;
427: collect_kmalloc_pages ();
428: collect_buffer_pages ();
429: pages_collected = 1;
430: goto again;
431: }
432:
433: printf ("%s:%d: __get_free_pages: ran out of pages\n", __FILE__, __LINE__);
434:
435: restore_flags (flags);
436: return 0;
437: }
438:
439: /* Free ORDER + 1 number of physically
440: contiguous pages starting at address ADDR. */
441: void
442: free_pages (unsigned long addr, unsigned long order)
443: {
444: int i;
445: unsigned flags, bits, len, j;
446:
447: assert ((addr & PAGE_MASK) == 0);
448:
449: for (i = 0; i < MEM_CHUNKS; i++)
450: if (addr >= pages_free[i].start && addr < pages_free[i].end)
451: break;
452:
453: assert (i < MEM_CHUNKS);
454:
455: /* Contruct bitmap of contiguous pages. */
456: len = 0;
457: j = 0;
458: bits = 0;
459: while (len < (PAGE_SIZE << order))
460: {
461: bits |= 1 << j++;
462: len += PAGE_SIZE;
463: }
464: bits <<= (addr - pages_free[i].start) >> PAGE_SHIFT;
465:
466: save_flags (flags);
467: cli ();
468:
469: assert ((pages_free[i].bitmap & bits) == 0);
470:
471: pages_free[i].bitmap |= bits;
472: linux_mem_avail += order + 1;
473: restore_flags (flags);
474: }
475:
476: /* Allocate SIZE bytes of memory. The pages need not be contiguous. */
477: void *
478: vmalloc (unsigned long size)
479: {
480: return (void *) __get_free_pages (GFP_KERNEL, get_page_order (size), ~0UL);
481: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.