ck_allocmap.cxx

C++ 编写的EROS RTOS

/*
 * Copyright (C) 1998, 1999, Jonathan S. Shapiro.
 *
 * This file is part of the EROS Operating System.
 *
 * 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,
 * 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 of
 * 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/* The old version of this logic kept a bit for each checkpoint log
 * page frame.  This version instead keeps a count of the number of
 * allocated objects per frame.  A log page frame is free IFF the
 * associated count is zero.  This permits us to eagerly deallocate
 * objects as they become stale.
 * 
 * While this design takes up more space than the previous design, the
 * previous design carried gobs of overhead in the lochash map for
 * every allocated location (which hopefully is most of them), so we
 * still have a net space savings.
 * 
 * In the interests of debugging, the current implementation uses a
 * byte per log page.  A 40 Mbyte log will therefore require 10 Kbytes
 * of in-core storage, which seems reasonable for now.  This can be
 * cut in half by reducing the size of the per-frame field to 4 bits,
 * which is possible because node frames hold at most 15 nodes.  I
 * haven't done it, because it seems a microoptimization and memory
 * prices are coming down.
 * 
 * Log locations that do not exist have the value BYTE_MAX.
 */

#include <kerninc/kernel.hxx>
#include <kerninc/MsgLog.hxx>
#include <kerninc/Checkpoint.hxx>
#include <kerninc/ObjectCache.hxx>

#ifndef NDEBUG
#include <disk/DiskNode.hxx>
#endif

#define dbg_alloc	0x1	/* allocations */
#define dbg_init	0x2	/* initialization */

/* Following should be an OR of some of the above */
#define dbg_flags   ( 0u )

#define DBCOND(x) (dbg_##x & dbg_flags)
#define DEBUG(x) if DBCOND(x)

/* #define ALLOCMAP_DEBUG */

AllocMap::AllocMap()
{
  for (uint32_t i = 0; i < CKPT_MAXSUBMAP; i++)
    submap[i] = 0;
}

uint32_t
AllocMap::NumAlloc(logframe_t ll)
{
  /* This *ought* to turn into a shift, since pg sz * 8 should be a
   * power of two:
   */

  uint32_t whichSubMap = ll / (EROS_PAGE_SIZE);

  /* Should turn into a mask */
  uint32_t whichByte = ll % (EROS_PAGE_SIZE);

  if (submap[whichSubMap] == 0 || submap[whichSubMap][whichByte] == BYTE_MAX)
    MsgLog::fatal("Checking allocation count on nonexistent log frame\n");

  assert ( submap[whichSubMap][whichByte] != BYTE_MAX );
  assert ( submap[whichSubMap][whichByte] <= DISK_NODES_PER_PAGE );

  return submap[whichSubMap][whichByte];
}

bool
AllocMap::IsFree(logframe_t ll)
{
  if (NumAlloc(ll) == 0)
    return true;
  return false;
}

void
AllocMap::MarkFree(logframe_t ll)
{
  /* This *ought* to turn into a shift, since pg sz * 8 should be a
   * power of two:
   */

  uint32_t whichSubMap = ll / (EROS_PAGE_SIZE);

  if (submap[whichSubMap] == 0) {
    ObjectHeader *pObj = ObjectCache::GrabPageFrame();
    submap[whichSubMap] = (uint8_t *) ObjectCache::ObHdrToPage(pObj);
    for (uint32_t i = 0; i < EROS_PAGE_SIZE; i++)
      submap[whichSubMap][i] = BYTE_MAX;
    DEBUG(init)
      MsgLog::printf("MarkFree: alloc submap %d\n", whichSubMap);
  }

  /* Should turn into a mask */
  uint32_t whichByte = ll % (EROS_PAGE_SIZE);

  submap[whichSubMap][whichByte] = 0;
}

void
AllocMap::Allocate(logframe_t ll)
{
  /* This *ought* to turn into a shift, since pg sz * 8 should be a
   * power of two:
   */

  uint32_t whichSubMap = ll / (EROS_PAGE_SIZE);

  /* Should turn into a mask */
  uint32_t whichByte = ll % (EROS_PAGE_SIZE);

  if (submap[whichSubMap] == 0 || submap[whichSubMap][whichByte] == BYTE_MAX)
    MsgLog::fatal("Allocating nonexistent log frame\n");

  assert ( submap[whichSubMap][whichByte] != BYTE_MAX );
  assert ( submap[whichSubMap][whichByte] <= DISK_NODES_PER_PAGE );

  if (submap[whichSubMap][whichByte] == 0)
    nAllocated++;
  
  submap[whichSubMap][whichByte] ++;

  DEBUG(alloc)
    MsgLog::printf("alloc log frame 0x%x count now %d\n", ll,
		   submap[whichSubMap][whichByte]);
}

void
AllocMap::Deallocate(logframe_t ll)
{
  /* This *ought* to turn into a shift, since pg sz * 8 should be a
   * power of two:
   */

  uint32_t whichSubMap = ll / (EROS_PAGE_SIZE);

  /* Should turn into a mask */
  uint32_t whichByte = ll % (EROS_PAGE_SIZE);

  if (submap[whichSubMap] == 0 || submap[whichSubMap][whichByte] == BYTE_MAX)
    MsgLog::fatal("Allocating nonexistent log frame\n");

  assert ( submap[whichSubMap][whichByte] != BYTE_MAX );
  assert ( submap[whichSubMap][whichByte] != 0 );
  /* Extra 1 for the held-over extra allocation  */
  assert ( submap[whichSubMap][whichByte] <= (DISK_NODES_PER_PAGE+1) );

  submap[whichSubMap][whichByte] --;

  if (submap[whichSubMap][whichByte] == 0)
    nAllocated--;

  DEBUG(alloc)
    MsgLog::printf("dealloc log frame 0x%x count now %d\n", ll,
		   submap[whichSubMap][whichByte]);
}