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