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