Return to kmem.c CVS log

Up to [GnuMach] / Gnu-Mach / linux / dev / glue

Annotation of Gnu-Mach/linux/dev/glue/kmem.c, revision 1.1

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.