Return to linux_kmem.c CVS log

Up to [GnuMach] / Gnu-Mach / i386 / i386at / gpl / linux

Annotation of Gnu-Mach/i386/i386at/gpl/linux/linux_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: 
        !            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.