mem.c

一个操作系统的源代码

/** mem.c                               
 **                                                              
 ** Original Author: Kasper Verdich Lund                         
 ** Date: 10.26.99     
 ** 
 ** Description:
 ** Memory allocation routines     
 **                                       
 ** Revision History: 
 ** First version     
 **
 ** 0.0.1 10.26.99 Kasper Verdich Lund - (no comments)
 ** 0.0.2 02.13.00 Guido de Jong - (no comments)
 **
 ** This program is free software, you can redistribute it and/or
 ** modify it under the terms of the GNU General Public License  
 ** as published by the Free Software Foundation; either version 
 ** 2 of the License, or (at your option) any later version.     
 **                                                              
 ** This program is distributed in the hope that it will be      
 ** useful, but WITHOUT ANY WARRANTY; without even the implied   
 ** warranty or MERCHANTABILITY or FITNESS FOR A PARTICULAR      
 ** PURPOSE.  See the GNU General Public License for more       
 ** details.                                                     
 **                                                              
 ** You should have received a copy of the GNU General Public    
 ** License along with this program; if not, write to the        
 ** Free Software Foundation, Inc., 59 Temple Place, Suite 330,  
 ** Boston, MA 02111-1307 USA                                    
 **                                                              
 *********************************************************Apostle OS**/

#include <mem.h>
#include <halt.h>
#include <paging.h>
#include <process.h>
#include <request.h>
#include <scheduler.h>
#include <string.h>
#include <types.h>

#ifdef DEBUG
#include <debug/conio.h>
#endif

#define pput(n) (pbitmap[(n)>>5]&=~(1<<((n)&0x1F)))
#define pget(n) (pbitmap[(n)>>5]|=(1<<((n)&0x1F))) 
#define pval(n) ((pbitmap[(n)>>5]>>((n)&0x1F))&1)

dword *pbitmap;
dword pavailable;

typedef long Align; /* for alignment to long boundary */

typedef union header
{ /* block header */
  struct
  {
    union header *ptr; /* next block on the free list */
    unsigned size; /* size of this block */
  } s;
  Align x; /* force alignment of blocks */
} Header;

static Header base = {{NULL,0}}; /* empty list to get started */
static Header *freep = NULL; /* start of free list */

void *brk = 0;

void *sbrk(size_t increment)
{
  dword *PD = (dword *)CR3;
  dword *PT;
  void *rbrk = (void *)((dword)brk + 0x10000000);
  int page, tables = 0;
  Process *p;
  Request *r;

  if (((dword)brk + increment) > 0x10000000)
    {
#ifdef DEBUG
      DebugPrintF("Cannot extend kernel vspace!\n");
#endif
      return NULL;
    }
  
  /* NOTICE: The extension of kernel vspace is done
   * in the address space pointed to by the CR3 variable. 
   * In order to be able to use the vspace extension in all
   * address spaces the lower 512 bytes of the page
   * directory pointed to by CR3 must be copied to ALL other
   * page directories. This is yet to be implemented. 
   * A good implementation is one that only copies the changes
   * and then flushes the correct TLB entry in the current
   * address space. */

  for (page=((dword)rbrk>>12); page<=(((dword)rbrk+increment)>>12); page++)
    {
      if ((PD[page>>10] & 1) != 1) 
	{
	  PT = pmalloc();
	  tables++;
	  PD[page>>10] = (dword)PT + PAGE_PRESENT;

          if ((page >> 10) < 128)
            {
#ifdef DEBUG
              DebugPrintF("Extending kernel vspace...\n");
#endif
              if (currentProcess != NULL)
                ((dword*)currentProcess->addressSpace)[page>>10] = 
                                                 (dword)PT + PAGE_PRESENT;

          /* Propagate changes in kernel space through readyQueue */
              if ((p = readyQueue) != NULL)
                {
                  do
                    {
                      p = p->next;
                      ((dword*)p->addressSpace)[page>>10] =
                                                 (dword)PT + PAGE_PRESENT;
                    }
                  while (p != readyQueue);
                }
          
              /* Propagate changes in kernel space through kernelRequests */
              if ((r = kernelRequests) != NULL)
                {
                  do
                    {
                      r = r->next;
                      ((dword*)r->process->addressSpace)[page>>10] =
                                                 (dword)PT + PAGE_PRESENT;  
                    }
                  while (r != kernelRequests);
                }

              /* This is a really ugly way to flush the TLB. :-(
               * The TLB is flushed completely, which is very costly.
               * It's also the only way to do it on a i386, more
               * intelligent flushing strategies are only possible
               * on i486+ processors. */
              flush_tlb();
            }
	}
      else
	PT = (dword *)(PD[page>>10] & 0xFFFFF000);
      if ((PT[page&0x3FF] & 1) != 1)
        PT[page&0x3FF] = (dword)pmalloc() + PAGE_PRESENT;
    }
  brk = (void *)((dword)brk + increment);

  return rbrk;
}

void *calloc(size_t nmemb, size_t size)
{
  void *p = malloc(nmemb * size);
  memset(p,0,nmemb * size);
  return p;
}

static Header *morecore(size_t size)
{
  Header *up;

  if (size < 1024)
    size = 1024; /* minimum units to request */
  up = sbrk(size * sizeof(Header));
  if (up == NULL)
    return NULL;
  up->s.size = size;
  free((void *)(up+1));
  return freep;
}

void *malloc(size_t size)
{
  Header *p, *prevp;
  unsigned nunits;

  nunits = (size+sizeof(Header)-1)/sizeof(Header)+1;
  if ((prevp = freep) == NULL)
    { /* no free list yet */
      base.s.ptr = freep = prevp = &base;
      base.s.size = 0;
    }
  for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
    {
      if (p->s.size >= nunits)
        { /* big enough */
          if (p->s.size == nunits) /* exactly */
            prevp->s.ptr = p->s.ptr;
          else
            {
              p->s.size -= nunits;
              p += p->s.size;
              p->s.size = nunits;
            }
          freep = prevp;
          return (void *)(p+1);
        }
      if (p == freep) /* wrapped around the free list */
        if ((p = morecore(nunits)) == NULL)
          {
#ifdef DEBUG
            DebugPrintF("malloc() failed\n");
#endif	
            return NULL; /* none left */
          }
    }
}

void free(void *ptr)
{
  Header *bp, *p;
  
  bp = (Header *)ptr - 1; /* point to block header */
  for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
    if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
      break; /* freed block at start or end of arena */

  if (bp + bp->s.size == p->s.ptr)
    { /* join to upper nbr */
      bp->s.size += p->s.ptr->s.size;
      bp->s.ptr = p->s.ptr->s.ptr;
    }
  else
      bp->s.ptr = p->s.ptr;
  if (p + p->s.size == bp)
    { /* join to lower nbr */
      p->s.size += bp->s.size;
      p->s.ptr = bp->s.ptr;
    }
  else
      p->s.ptr = bp;
  freep = p;
}

void *pmalloc(void)
{
  int i;
  for (i=0; i<pavailable; i++)
    if (!pval(i)) 
      {
        pget(i);
	return (void *)(i << 12);
      }
#ifdef DEBUG
  DebugPrintF("pmalloc() failed\n");
#endif
  return NULL;
}

void pfree(void *ptr)
{
  pput((dword)ptr >> 12);
}

void *p2malloc(void)
{
  int i;
  for (i=0; i<pavailable; i++)
    if (!(pval(i) || pval(i+1))) 
      {
        pget(i);
	pget(i+1);
	return (void *)(i << 12);
      }
#ifdef DEBUG
  DebugPrintF("p2malloc() failed\n");
#endif
  return NULL;
}

void p2free(void *ptr)
{
  pput((dword)ptr >> 12);
  pput(((dword)ptr >> 12) + 1);
}

void psetup(dword available, dword used)
{
  int i;
  dword pbitmap_size = ((available>>15)+PAGE_SIZE-1)&0xFFFFF000;

  if ((used + pbitmap_size) >= available)
    {
#ifdef DEBUG
      DebugPrintF("Not enough memory to allocate page bitmap\n");
#endif
      halt();
    }
  
  pbitmap = (dword*) used;
  pavailable = available >> 12;
  memset(pbitmap, 0, pbitmap_size);
  used += pbitmap_size;

  for (i=0; i<(used>>12); i++)
    pget(i);
}