![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to kmem.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GnuMach] / Gnu-Mach / linux / dev / glue|
Return to kmem.c CVS log | Up to [GnuMach] / Gnu-Mach / linux / dev / glue |
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>
1.1.1.2 ! root 32: #include <kern/printf.h>
1.1 root 33:
34: #include <vm/vm_page.h>
35: #include <vm/vm_kern.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:
1.1.1.2 ! root 44: #include <linux/dev/glue/glue.h>
1.1 root 45:
46: /* Amount of memory to reserve for Linux memory allocator.
47: We reserve 64K chunks to stay within DMA limits.
48: Increase MEM_CHUNKS if the kernel is running out of memory. */
49: #define MEM_CHUNK_SIZE (64 * 1024)
1.1.1.2 ! root 50: #define MEM_CHUNKS 32
! 51: #define MEM_DMA_LIMIT (16 * 1024 * 1024)
1.1 root 52:
53: /* Mininum amount that linux_kmalloc will allocate. */
54: #define MIN_ALLOC 12
55:
56: #ifndef NBPW
57: #define NBPW 32
58: #endif
59:
60: /* Memory block header. */
61: struct blkhdr
62: {
63: unsigned short free; /* 1 if block is free */
64: unsigned short size; /* size of block */
65: };
66:
67: /* This structure heads a page allocated by linux_kmalloc. */
68: struct pagehdr
69: {
70: unsigned size; /* size (multiple of PAGE_SIZE) */
71: struct pagehdr *next; /* next header in list */
72: };
73:
74: /* This structure describes a memory chunk. */
75: struct chunkhdr
76: {
77: unsigned long start; /* start address */
78: unsigned long end; /* end address */
79: unsigned long bitmap; /* busy/free bitmap of pages */
80: };
81:
82: /* Chunks from which pages are allocated. */
83: static struct chunkhdr pages_free[MEM_CHUNKS];
84:
85: /* Memory list maintained by linux_kmalloc. */
86: static struct pagehdr *memlist;
87:
88: /* Some statistics. */
89: int num_block_coalesce = 0;
90: int num_page_collect = 0;
91: int linux_mem_avail;
92:
93: /* Initialize the Linux memory allocator. */
94: void
95: linux_kmem_init ()
96: {
97: int i, j;
98: vm_page_t p, pages;
99:
100: for (i = 0; i < MEM_CHUNKS; i++)
101: {
102: /* Allocate memory. */
103: pages_free[i].start = (unsigned long) alloc_contig_mem (MEM_CHUNK_SIZE,
1.1.1.2 ! root 104: MEM_DMA_LIMIT,
1.1 root 105: 0xffff, &pages);
106:
107: assert (pages_free[i].start);
108: assert ((pages_free[i].start & 0xffff) == 0);
109:
110: /* Sanity check: ensure pages are contiguous and within DMA limits. */
111: for (p = pages, j = 0; j < MEM_CHUNK_SIZE - PAGE_SIZE; j += PAGE_SIZE)
112: {
1.1.1.2 ! root 113: assert (p->phys_addr < MEM_DMA_LIMIT);
1.1 root 114: assert (p->phys_addr + PAGE_SIZE
115: == ((vm_page_t) p->pageq.next)->phys_addr);
116:
117: p = (vm_page_t) p->pageq.next;
118: }
119:
120: pages_free[i].end = pages_free[i].start + MEM_CHUNK_SIZE;
121:
122: /* Initialize free page bitmap. */
123: pages_free[i].bitmap = 0;
124: j = MEM_CHUNK_SIZE >> PAGE_SHIFT;
125: while (--j >= 0)
126: pages_free[i].bitmap |= 1 << j;
127: }
128:
129: linux_mem_avail = (MEM_CHUNKS * MEM_CHUNK_SIZE) >> PAGE_SHIFT;
130: }
131:
132: /* Return the number by which the page size should be
133: shifted such that the resulting value is >= SIZE. */
134: static unsigned long
135: get_page_order (int size)
136: {
137: unsigned long order;
138:
139: for (order = 0; (PAGE_SIZE << order) < size; order++)
140: ;
141: return order;
142: }
143:
144: #ifdef LINUX_DEV_DEBUG
145: static void
146: check_page_list (int line)
147: {
148: unsigned size;
149: struct pagehdr *ph;
150: struct blkhdr *bh;
151:
152: for (ph = memlist; ph; ph = ph->next)
153: {
154: if ((int) ph & PAGE_MASK)
155: panic ("%s:%d: page header not aligned", __FILE__, line);
156:
157: size = 0;
158: bh = (struct blkhdr *) (ph + 1);
159: while (bh < (struct blkhdr *) ((void *) ph + ph->size))
160: {
161: size += bh->size + sizeof (struct blkhdr);
162: bh = (void *) (bh + 1) + bh->size;
163: }
164:
165: if (size + sizeof (struct pagehdr) != ph->size)
166: panic ("%s:%d: memory list destroyed", __FILE__, line);
167: }
168: }
169: #else
170: #define check_page_list(line)
171: #endif
172:
173: /* Merge adjacent free blocks in the memory list. */
174: static void
175: coalesce_blocks ()
176: {
177: struct pagehdr *ph;
178: struct blkhdr *bh, *bhp, *ebh;
179:
180: num_block_coalesce++;
181:
182: for (ph = memlist; ph; ph = ph->next)
183: {
184: bh = (struct blkhdr *) (ph + 1);
185: ebh = (struct blkhdr *) ((void *) ph + ph->size);
186: while (1)
187: {
188: /* Skip busy blocks. */
189: while (bh < ebh && !bh->free)
190: bh = (struct blkhdr *) ((void *) (bh + 1) + bh->size);
191: if (bh == ebh)
192: break;
193:
194: /* Merge adjacent free blocks. */
195: while (1)
196: {
197: bhp = (struct blkhdr *) ((void *) (bh + 1) + bh->size);
198: if (bhp == ebh)
199: {
200: bh = bhp;
201: break;
202: }
203: if (!bhp->free)
204: {
205: bh = (struct blkhdr *) ((void *) (bhp + 1) + bhp->size);
206: break;
207: }
208: bh->size += bhp->size + sizeof (struct blkhdr);
209: }
210: }
211: }
212: }
213:
214: /* Allocate SIZE bytes of memory.
215: The PRIORITY parameter specifies various flags
216: such as DMA, atomicity, etc. It is not used by Mach. */
217: void *
218: linux_kmalloc (unsigned int size, int priority)
219: {
220: int order, coalesced = 0;
1.1.1.2 ! root 221: unsigned long flags;
1.1 root 222: struct pagehdr *ph;
223: struct blkhdr *bh, *new_bh;
224:
225: if (size < MIN_ALLOC)
226: size = MIN_ALLOC;
227: else
228: size = (size + sizeof (int) - 1) & ~(sizeof (int) - 1);
229:
230: assert (size <= (MEM_CHUNK_SIZE
231: - sizeof (struct pagehdr)
232: - sizeof (struct blkhdr)));
233:
234: save_flags (flags);
235: cli ();
236:
237: again:
238: check_page_list (__LINE__);
239:
240: /* Walk the page list and find the first free block with size
241: greater than or equal to the one required. */
242: for (ph = memlist; ph; ph = ph->next)
243: {
244: bh = (struct blkhdr *) (ph + 1);
245: while (bh < (struct blkhdr *) ((void *) ph + ph->size))
246: {
247: if (bh->free && bh->size >= size)
248: {
249: bh->free = 0;
250: if (bh->size - size >= MIN_ALLOC + sizeof (struct blkhdr))
251: {
252: /* Split the current block and create a new free block. */
253: new_bh = (void *) (bh + 1) + size;
254: new_bh->free = 1;
255: new_bh->size = bh->size - size - sizeof (struct blkhdr);
256: bh->size = size;
257: }
258:
259: check_page_list (__LINE__);
260:
261: restore_flags (flags);
262: return bh + 1;
263: }
264: bh = (void *) (bh + 1) + bh->size;
265: }
266: }
267:
268: check_page_list (__LINE__);
269:
270: /* Allocation failed; coalesce free blocks and try again. */
271: if (!coalesced)
272: {
273: coalesce_blocks ();
274: coalesced = 1;
275: goto again;
276: }
277:
278: /* Allocate more pages. */
279: order = get_page_order (size
280: + sizeof (struct pagehdr)
281: + sizeof (struct blkhdr));
282: ph = (struct pagehdr *) __get_free_pages (GFP_KERNEL, order, ~0UL);
283: if (!ph)
284: {
285: restore_flags (flags);
286: return NULL;
287: }
288:
289: ph->size = PAGE_SIZE << order;
290: ph->next = memlist;
291: memlist = ph;
292: bh = (struct blkhdr *) (ph + 1);
293: bh->free = 0;
294: bh->size = ph->size - sizeof (struct pagehdr) - sizeof (struct blkhdr);
295: if (bh->size - size >= MIN_ALLOC + sizeof (struct blkhdr))
296: {
297: new_bh = (void *) (bh + 1) + size;
298: new_bh->free = 1;
299: new_bh->size = bh->size - size - sizeof (struct blkhdr);
300: bh->size = size;
301: }
302:
303: check_page_list (__LINE__);
304:
305: restore_flags (flags);
306: return bh + 1;
307: }
308:
309: /* Free memory P previously allocated by linux_kmalloc. */
310: void
311: linux_kfree (void *p)
312: {
1.1.1.2 ! root 313: unsigned long flags;
1.1 root 314: struct blkhdr *bh;
315: struct pagehdr *ph;
316:
317: assert (((int) p & (sizeof (int) - 1)) == 0);
318:
319: save_flags (flags);
320: cli ();
321:
322: check_page_list (__LINE__);
323:
324: for (ph = memlist; ph; ph = ph->next)
325: if (p >= (void *) ph && p < (void *) ph + ph->size)
326: break;
327:
328: assert (ph);
329:
330: bh = (struct blkhdr *) p - 1;
331:
332: assert (!bh->free);
333: assert (bh->size >= MIN_ALLOC);
334: assert ((bh->size & (sizeof (int) - 1)) == 0);
335:
336: bh->free = 1;
337:
338: check_page_list (__LINE__);
339:
340: restore_flags (flags);
341: }
342:
343: /* Free any pages that are not in use.
344: Called by __get_free_pages when pages are running low. */
345: static void
346: collect_kmalloc_pages ()
347: {
348: struct blkhdr *bh;
349: struct pagehdr *ph, **prev_ph;
350:
351: check_page_list (__LINE__);
352:
353: coalesce_blocks ();
354:
355: check_page_list (__LINE__);
356:
357: ph = memlist;
358: prev_ph = &memlist;
359: while (ph)
360: {
361: bh = (struct blkhdr *) (ph + 1);
362: if (bh->free && (void *) (bh + 1) + bh->size == (void *) ph + ph->size)
363: {
364: *prev_ph = ph->next;
365: free_pages ((unsigned long) ph, get_page_order (ph->size));
366: ph = *prev_ph;
367: }
368: else
369: {
370: prev_ph = &ph->next;
371: ph = ph->next;
372: }
373: }
374:
375: check_page_list (__LINE__);
376: }
377:
378: /* Allocate ORDER + 1 number of physically contiguous pages.
379: PRIORITY and DMA are not used in Mach.
380:
381: XXX: This needs to be dynamic. To do that we need to make
382: the Mach page manipulation routines interrupt safe and they
383: must provide machine dependant hooks. */
384: unsigned long
385: __get_free_pages (int priority, unsigned long order, int dma)
386: {
387: int i, pages_collected = 0;
1.1.1.2 ! root 388: unsigned bits, off, j, len;
! 389: unsigned long flags;
1.1 root 390:
391: assert ((PAGE_SIZE << order) <= MEM_CHUNK_SIZE);
392:
393: /* Construct bitmap of contiguous pages. */
394: bits = 0;
395: j = 0;
396: len = 0;
397: while (len < (PAGE_SIZE << order))
398: {
399: bits |= 1 << j++;
400: len += PAGE_SIZE;
401: }
402:
403: save_flags (flags);
404: cli ();
405: again:
406:
407: /* Search each chunk for the required number of contiguous pages. */
408: for (i = 0; i < MEM_CHUNKS; i++)
409: {
410: off = 0;
411: j = bits;
412: while (MEM_CHUNK_SIZE - off >= (PAGE_SIZE << order))
413: {
414: if ((pages_free[i].bitmap & j) == j)
415: {
416: pages_free[i].bitmap &= ~j;
417: linux_mem_avail -= order + 1;
418: restore_flags (flags);
419: return pages_free[i].start + off;
420: }
421: j <<= 1;
422: off += PAGE_SIZE;
423: }
424: }
425:
426: /* Allocation failed; collect kmalloc and buffer pages
427: and try again. */
428: if (!pages_collected)
429: {
430: num_page_collect++;
431: collect_kmalloc_pages ();
432: pages_collected = 1;
433: goto again;
434: }
435:
436: printf ("%s:%d: __get_free_pages: ran out of pages\n", __FILE__, __LINE__);
437:
438: restore_flags (flags);
439: return 0;
440: }
441:
442: /* Free ORDER + 1 number of physically
443: contiguous pages starting at address ADDR. */
444: void
445: free_pages (unsigned long addr, unsigned long order)
446: {
447: int i;
1.1.1.2 ! root 448: unsigned bits, len, j;
! 449: unsigned long flags;
1.1 root 450:
451: assert ((addr & PAGE_MASK) == 0);
452:
453: for (i = 0; i < MEM_CHUNKS; i++)
454: if (addr >= pages_free[i].start && addr < pages_free[i].end)
455: break;
456:
457: assert (i < MEM_CHUNKS);
458:
459: /* Contruct bitmap of contiguous pages. */
460: len = 0;
461: j = 0;
462: bits = 0;
463: while (len < (PAGE_SIZE << order))
464: {
465: bits |= 1 << j++;
466: len += PAGE_SIZE;
467: }
468: bits <<= (addr - pages_free[i].start) >> PAGE_SHIFT;
469:
470: save_flags (flags);
471: cli ();
472:
473: assert ((pages_free[i].bitmap & bits) == 0);
474:
475: pages_free[i].bitmap |= bits;
476: linux_mem_avail += order + 1;
477: restore_flags (flags);
478: }
479:
480:
481: /* vmalloc management routines. */
482: struct vmalloc_struct
483: {
484: struct vmalloc_struct *prev;
485: struct vmalloc_struct *next;
486: vm_offset_t start;
487: vm_size_t size;
488: };
489:
490: static struct vmalloc_struct
491: vmalloc_list = { &vmalloc_list, &vmalloc_list, 0, 0 };
492:
493: static inline void
494: vmalloc_list_insert (vm_offset_t start, vm_size_t size)
495: {
496: struct vmalloc_struct *p;
497:
498: p = (struct vmalloc_struct *) kalloc (sizeof (struct vmalloc_struct));
499: if (p == NULL)
500: panic ("kernel memory is exhausted");
501:
502: p->prev = vmalloc_list.prev;
503: p->next = &vmalloc_list;
504: vmalloc_list.prev->next = p;
505: vmalloc_list.prev = p;
506:
507: p->start = start;
508: p->size = size;
509: }
510:
511: static struct vmalloc_struct *
512: vmalloc_list_lookup (vm_offset_t start)
513: {
514: struct vmalloc_struct *p;
515:
516: for (p = vmalloc_list.next; p != &vmalloc_list; p = p->next)
517: {
518: if (p->start == start)
519: return p;
520: }
521:
522: return NULL;
523: }
524:
525: static inline void
526: vmalloc_list_remove (struct vmalloc_struct *p)
527: {
528: p->next->prev = p->prev;
529: p->prev->next = p->next;
530:
1.1.1.2 ! root 531: kfree ((vm_offset_t) p, sizeof (struct vmalloc_struct));
1.1 root 532: }
533:
534: /* Allocate SIZE bytes of memory. The pages need not be contiguous. */
535: void *
536: vmalloc (unsigned long size)
537: {
538: kern_return_t ret;
539: vm_offset_t addr;
540:
541: ret = kmem_alloc_wired (kernel_map, &addr, round_page (size));
542: if (ret != KERN_SUCCESS)
543: return NULL;
544:
545: vmalloc_list_insert (addr, round_page (size));
546: return (void *) addr;
547: }
548:
549: /* Free vmalloc'ed and vremap'ed virtual address space. */
550: void
551: vfree (void *addr)
552: {
553: struct vmalloc_struct *p;
554:
555: p = vmalloc_list_lookup ((vm_offset_t) addr);
1.1.1.2 ! root 556: if (!p)
1.1 root 557: panic ("vmalloc_list_lookup failure");
558:
1.1.1.2 ! root 559: kmem_free (kernel_map, (vm_offset_t) addr, p->size);
1.1 root 560: vmalloc_list_remove (p);
561: }
562:
1.1.1.2 ! root 563: unsigned long
! 564: vmtophys (void *addr)
! 565: {
! 566: return kvtophys((vm_offset_t) addr);
! 567: }
! 568:
1.1 root 569: /* XXX: Quick hacking. */
570: /* Remap physical address into virtual address. */
571: void *
572: vremap (unsigned long offset, unsigned long size)
573: {
574: extern vm_offset_t pmap_map_bd (register vm_offset_t virt,
575: register vm_offset_t start,
576: register vm_offset_t end,
577: vm_prot_t prot);
578: vm_offset_t addr;
579: kern_return_t ret;
580:
581: ret = kmem_alloc_wired (kernel_map, &addr, round_page (size));
582: if (ret != KERN_SUCCESS)
583: return NULL;
584:
585: (void) pmap_map_bd (addr, offset, offset + round_page (size),
586: VM_PROT_READ | VM_PROT_WRITE);
587:
588: vmalloc_list_insert (addr, round_page (size));
589: return (void *) addr;
590: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.