malloc.c

上一个上传的有问题,这个是好的。visopsys包括系统内核和GUI的全部SOURCE code ,还包括一些基本的docs文档。里面src子目录对应所有SOURCE code.对于想研究操作系统的朋

// 
//  Visopsys
//  Copyright (C) 1998-2007 J. Andrew McLaughlin
//  
//  This library is free software; you can redistribute it and/or modify it
//  under the terms of the GNU Lesser General Public License as published by
//  the Free Software Foundation; either version 2.1 of the License, or (at
//  your option) any later version.
//
//  This library is distributed in the hope that it will be useful, but
//  WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser
//  General Public License for more details.
//
//  You should have received a copy of the GNU Lesser General Public License
//  along with this library; if not, write to the Free Software Foundation,
//  Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//
//  malloc.c
//
	
// These routines comprise Visopsys heap memory management system.  It relies
// upon the kernelMemory code, and does similar things, but instead of whole
// memory pages, it allocates arbitrary-sized chunks.

#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <sys/memory.h>
#include <sys/api.h>

static mallocBlock *blockList = NULL;
static mallocBlock *unusedBlockList = NULL;
static volatile unsigned totalBlocks = 0;
static volatile unsigned usedBlocks = 0;
static volatile unsigned totalMemory = 0;
static volatile unsigned usedMemory = 0;
static lock blocksLock;

unsigned mallocHeapMultiple = USER_MEMORY_HEAP_MULTIPLE;
mallocKernelOps mallocKernOps;

#define blockEnd(block) (block->start + block->size - 1)

#if defined(DEBUG)
#define debug(message, arg...) do {                                    \
  if (visopsys_in_kernel)                                              \
    {                                                                  \
      if (mallocKernOps.debug)                                         \
	mallocKernOps.debug(__FILE__, __FUNCTION__, __LINE__,          \
			    debug_memory, message, ##arg);             \
    }                                                                  \
  else                                                                 \
    {                                                                  \
      printf("DEBUG: %s:%s(%d): ", __FILE__, __FUNCTION__, __LINE__);  \
      printf(message, ##arg);                                          \
      printf("\n");                                                    \
    }                                                                  \
} while (0)
#else
#define debug(message, arg...) do { } while (0)
#endif // defined(DEBUG)

#define error(message, arg...) do {                                      \
  if (visopsys_in_kernel)                                                \
    mallocKernOps.error(__FILE__, __FUNCTION__, __LINE__, kernel_error,  \
			message, ##arg);                                 \
  else                                                                   \
    {                                                                    \
      printf("Error: %s:%s(%d): ", __FILE__, __FUNCTION__, __LINE__);    \
      printf(message, ##arg);                                            \
      printf("\n");                                                      \
    }                                                                    \
} while (0)


static inline int procid(void)
{
  if (visopsys_in_kernel)
    return (mallocKernOps.multitaskerGetCurrentProcessId());
  else
    return (multitaskerGetCurrentProcessId());
}


static inline void *memory_get(unsigned size, const char *desc)
{
  debug("%s %u", __FUNCTION__, size);
  if (visopsys_in_kernel)
    return (mallocKernOps.memoryGet(size, desc));
  else
    return (memoryGet(size, desc));
}


static inline int memory_release(void *start)
{
  debug("%s %p", __FUNCTION__, start);
  if (visopsys_in_kernel)
    return (mallocKernOps.memoryRelease(start));
  else
    return (memoryRelease(start));
}


static inline int lock_get(lock *lk)
{
  if (visopsys_in_kernel)
    return (mallocKernOps.lockGet(lk));
  else
    return (lockGet(lk));
}


static inline void lock_release(lock *lk)
{
  if (visopsys_in_kernel)
    mallocKernOps.lockRelease(lk);
  else
    lockRelease(lk);
}


static inline void insertBlock(mallocBlock *insBlock, mallocBlock *nextBlock)
{
  // Stick the first block in front of the second block

  debug("Insert block %u->%u before %u->%u", insBlock->start,
	blockEnd(insBlock), nextBlock->start, blockEnd(nextBlock));

  insBlock->prev = nextBlock->prev;
  insBlock->next = nextBlock;

  if (nextBlock->prev)
    nextBlock->prev->next = insBlock;
  nextBlock->prev = insBlock;

  if (nextBlock == blockList)
    blockList = insBlock;
}


static inline void appendBlock(mallocBlock *appBlock, mallocBlock *prevBlock)
{
  // Stick the first block behind the second block

  debug("Append block %u->%u after %u->%u", appBlock->start,
	blockEnd(appBlock), prevBlock->start, blockEnd(prevBlock));

  appBlock->prev = prevBlock;
  appBlock->next = prevBlock->next;

  if (prevBlock->next)
    prevBlock->next->prev = appBlock;
  prevBlock->next = appBlock;
}


static int sortInsertBlock(mallocBlock *block)
{
  // Find the correct (sorted) place for in the block list for this block.

  int status = 0;
  mallocBlock *nextBlock = NULL;

  if (blockList)
    {
      nextBlock = blockList;

      while (nextBlock)
	{
	  if (nextBlock->start > block->start)
	    {
	      insertBlock(block, nextBlock);
	      break;
	    }

	  if (!nextBlock->next)
	    {
	      appendBlock(block, nextBlock);
	      break;
	    }

	  nextBlock = nextBlock->next;
	}
    }
  else
    {
      block->prev = NULL;
      block->next = NULL;
      blockList = block;
    }

  return (status = 0);
}


static int allocUnusedBlocks(void)
{
  // This grows the unused block list by 1 memory page.

  int status = 0;
  int numBlocks = 0;
  int count;

  debug("Allocating new unused blocks");

  if (visopsys_in_kernel)
    unusedBlockList = memory_get(MEMORY_BLOCK_SIZE, "kernel heap metadata");
  else
    unusedBlockList = memory_get(MEMORY_BLOCK_SIZE, "user heap metadata");
  if (unusedBlockList == NULL)
    {
      error("Unable to allocate heap management memory");
      return (status = ERR_MEMORY);
    }

  // How many blocks is that?
  numBlocks = (MEMORY_BLOCK_SIZE / sizeof(mallocBlock));

  // Initialize the pointers in our list of blocks
  for (count = 0; count < numBlocks; count ++)
    {
      if (count > 0)
	unusedBlockList[count].prev = &unusedBlockList[count - 1];
      if (count < (numBlocks - 1))
	unusedBlockList[count].next = &unusedBlockList[count + 1];
    }

  totalBlocks += numBlocks;

  return (status = 0);
}


static mallocBlock *getBlock(void)
{
  // Get a block from the unused block list.

  mallocBlock *block = NULL;

  // Do we have any more unused blocks?
  if (!unusedBlockList)
    {
      if (allocUnusedBlocks() < 0)
	return (block = NULL);
    }

  block = unusedBlockList;
  unusedBlockList = block->next;
  
  // Clear it
  bzero(block, sizeof(mallocBlock));

  usedBlocks += 1;

  return (block);
}


static void putBlock(mallocBlock *block)
{
  // This function gets called when a block is no longer needed.  We
  // zero out its fields and move it to the end of the used blocks.

  // Remove the block from the list.
  if (block->prev)
    block->prev->next = block->next;
  if (block->next)
    block->next->prev = block->prev;

  if (block == blockList)
    blockList = block->next;

  // Clear it
  bzero(block, sizeof(mallocBlock));

  // Put it at the head of the unused block list
  block->next = unusedBlockList;
  unusedBlockList = block;

  usedBlocks -= 1;

  return;
}


static int addBlock(int used, unsigned start, unsigned size,
		    unsigned heapAlloc)
{
  // Creates a used or free block in our block list.

  int status = 0;
  mallocBlock *block = NULL;

  block = getBlock();
  if (block == NULL)
    return (status = ERR_NOFREE);

  block->used = used;
  block->start = start;
  block->size = size;
  block->heapAlloc = heapAlloc;

  status = sortInsertBlock(block);
  if (status < 0)
    return (status);

  return (status = 0);
}


static int growHeap(unsigned minSize)
{
  // This grows the pool of heap memory by at least minSize bytes.

  void *newHeap = NULL;

  // Don't allocate less than the default heap multiple
  if (minSize < mallocHeapMultiple)
    minSize = mallocHeapMultiple;

  // Allocation should be a multiple of MEMORY_BLOCK_SIZE
  if (minSize % MEMORY_BLOCK_SIZE)
    minSize += (MEMORY_BLOCK_SIZE - (minSize % MEMORY_BLOCK_SIZE));

  debug("%s %u", __FUNCTION__, minSize);
  if (minSize > mallocHeapMultiple)
    debug("Size is greater than %u", mallocHeapMultiple);

  // Get the heap memory
  if (visopsys_in_kernel)
    newHeap = memory_get(minSize, "kernel heap");
  else
    newHeap = memory_get(minSize, "user heap");
  if (newHeap == NULL)
    {
      error("Unable to allocate heap memory");
      return (ERR_MEMORY);
    }

  totalMemory += minSize;

  // Add it as a single free block
  return (addBlock(0 /* unused */, (unsigned) newHeap, minSize,
		   (unsigned) newHeap));
}


static mallocBlock *findFree(unsigned size)
{
  mallocBlock *block = blockList;