ck_coredir.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.
 */

/* #define PARANOID */
#define LOUD_PARANOID

#include <disk/ErosTypes.h>
#include <disk/DiskFrame.hxx>

#include <kerninc/kernel.hxx>
#include <kerninc/MsgLog.hxx>
#include <kerninc/Check.hxx>
#include <kerninc/CkDir.hxx>
#include <kerninc/ObjectCache.hxx>
#ifdef PARANOID
#include <kerninc/Checkpoint.hxx>
#endif
#include <kerninc/IRQ.hxx>

/* Following should be an OR of some of the above */
#define dbg_alloc   1u
#define dbg_grow    2u

#define dbg_flags   ( dbg_grow | 0u )

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

CoreDirent       CoreDirent::nil_sentinal;
CoreDirent      *CoreDirent::freeList = 0;
uint32_t	 CoreDirent::nFree = 0;
uint32_t	 CoreDirent::nAlloc = 0;
uint32_t	 CoreDirent::nTotal = 0;

/* Note that this is mostly the initialization requirement for the
 * CkNil node.
 */
CoreDirent::CoreDirent()
{
  left = CkNIL;
  right = CkNIL;
  parent = CkNIL;
  color = black;
}

static uint32_t MaxCoreDirentFrames;

void
CoreDirent::InitFreeList(uint32_t ckLogSz)
{
  uint32_t nCoreDirent = ckLogSz * 4;

  const uint32_t dpp = EROS_PAGE_SIZE / sizeof(CoreDirent);
  
  /* This is the ideal number: */
  uint32_t nCoreDirentFrames = (nCoreDirent + (dpp-1)) / dpp;

  /* But we don't want to take up too much of main memory: */
  MaxCoreDirentFrames = ObjectCache::TotalPages() / 64;
  if (MaxCoreDirentFrames == 0)
    MaxCoreDirentFrames = 1;

  if (nCoreDirentFrames > MaxCoreDirentFrames)
    nCoreDirentFrames = MaxCoreDirentFrames;

  for (uint32_t frm = 0; frm < nCoreDirentFrames; frm++) {
    ObjectHeader *pObj = ObjectCache::GrabPageFrame();
    assert (pObj);
  
    CoreDirent* cld = (CoreDirent *) ObjectCache::ObHdrToPage(pObj);

    IRQ::DISABLE();
    for (uint32_t i = 0; i < (EROS_PAGE_SIZE / sizeof(CoreDirent)); i++) {
      cld[i].right = freeList;
      freeList = &cld[i];
      nFree++;
      nTotal++;
    }
    IRQ::ENABLE();
  }
}

#if 0
bool
CoreDirent::GrowFreeList()
{
  static uint32_t nPage = 0;

  if (nPage >= MaxCoreDirentFrames) {
    DEBUG(grow)
      MsgLog::dprintf(false, "Cannot grow free list -- maxpages reached\n");
    MsgLog::printf("&");
    return false;
  }
  
  ObjectHeader *pObj = ObjectCache::GrabPageFrame();
  nPage++;
  assert (pObj);
  
  CoreDirent* cld = (CoreDirent *) ObjectCache::ObHdrToPage(pObj);

  for (uint32_t i = 0; i < (EROS_PAGE_SIZE / sizeof(CoreDirent)); i++) {
    cld[i].right = freeList;
    freeList = &cld[i];
    nFree++;
    nTotal++;
  }

  DEBUG(alloc)
    MsgLog::dprintf(false, "GrowFreeList(): freeList 0x%08x, nFree %d\n",
		    freeList, nFree);

  assert(freeList);
  
  return true;
}
#else
bool
CoreDirent::GrowFreeList()
{
  DEBUG(grow)
    MsgLog::dprintf(false,
		    "NOT CoreDirent growing free list -- %d allocated\n",
		    nAlloc);
  return false;
}
#endif

void *
CoreDirent::operator new(size_t)
{
#ifdef PARANOID
  assert(CheckConsistency("top of CoreDirent::new"));
#endif

  DEBUG(alloc)
    MsgLog::dprintf(false, "CoreDirent new(): freeList on entry 0x%08x, nFree %d\n",
		    freeList, nFree);

  if (freeList == 0) {
    assertex((void*)nFree, nFree == 0);
    GrowFreeList();
  }

  if (freeList == 0) {
    assertex((void*)nFree, nFree == 0);
    DEBUG(grow)
      MsgLog::dprintf(false, "Could not grow core dirent free list\n");
    return 0;
  }
  
  CoreDirent *nxt = freeList;
  freeList = freeList->right;
  nFree--;
  nAlloc++;
  
  DEBUG(alloc)
    MsgLog::dprintf(false, "CoreDirent new(): freeList on exit 0x%08x, nFree %d\n",
		    freeList, nFree);

#ifdef PARANOID
  assert(CheckConsistency("bottom of CoreDirent::new"));
#endif
  
  return nxt;
}

void
CoreDirent::operator delete(void * v)
{
  DEBUG(alloc)
    MsgLog::dprintf(false, "CoreDirent delete(): freeList on entry 0x%08x, nFree %d\n",
		   freeList, nFree);

#ifdef PARANOID
  {
    CoreDirent *cde = freeList;
    uint32_t count = 0;
    while (cde) {
      count++;
      if (cde == (CoreDirent*) v)
	MsgLog::fatal("Deleting free core dirent!\n");
      cde = cde->right;
    }
    
    for (int i = 0; i < Checkpoint::nGeneration; i++)
      assert ( Tree_FindReference(Checkpoint::coreGeneration[i].oidTree,
				  (CoreDirent *)v) == 0);
  }
#endif
  
  ((CoreDirent *) v)->right = freeList;
  freeList = (CoreDirent *) v;
  nFree++;
  nAlloc--;

  DEBUG(alloc)
    MsgLog::dprintf(false, "CoreDirent delete(): freeList on exit 0x%08x, nFree %d\n",
		   freeList, nFree);
}

bool
CoreDirent::Require(uint32_t w)
{
  
  assert (w <= (EROS_PAGE_SIZE / sizeof(CoreDirent)));
  
  if (w >= nFree)
    GrowFreeList();

  if (w >= nFree)
    return false;

  return true;
}


CoreDirent *
CoreDirent::Minimum()
{
  CoreDirent *x = this;

  if (x == CkNIL)
    return CkNIL;
  
  while (x->left != CkNIL)
    x = x->left;

  return x;
}

CoreDirent *
CoreDirent::Maximum()
{
  CoreDirent *x = this;

  if (x == CkNIL)
    return CkNIL;
  
  while (x->right != CkNIL)
    x = x->right;

  return x;
}

CoreDirent *
CoreDirent::Successor()
{
  CoreDirent *x = this;

  if (x == CkNIL) {
    MsgLog::fatal("Successor(NIL)!!!\n");
    return CkNIL;
  }
  
  if (x->right != CkNIL)
    return x->right->Minimum();

  CoreDirent *y = x->parent;

  while (y != CkNIL && x == y->right) {
    x = y;
    y = y->parent;
  }

  return y;
}

CoreDirent *
CoreDirent::Predecessor()
{
  CoreDirent *x = this;

  if (x == CkNIL) {
    MsgLog::fatal("Predecessor(NIL)!!!\n");
    return CkNIL;
  }
  
  if (x->left != CkNIL)
    return x->left->Maximum();

  CoreDirent *y = x->parent;

  while (y != CkNIL && x == y->left) {
    x = y;
    y = y->parent;
  }

  return y;
}


#ifdef OPTION_DDB
void
CoreDirent::DumpTree(int indent)
{
  extern void db_printf(const char *fmt, ...);

  if (this != CkNIL)
    left->DumpTree(indent + 4);

  if (this != CkNIL)
    for (int i = 0; i < indent; i++)
      db_printf(" ");

  if (this != CkNIL) {
    const char *cty = "??";
    switch(type) {
    case FRM_TYPE_ZDPAGE:
      cty = "zd";
      break;
    case FRM_TYPE_DPAGE:
      cty = "dp";
      break;
    case FRM_TYPE_NODE:
      cty = "nd";
      break;
    case FRM_TYPE_ZNODE:
      cty = "zn";
      break;
    }

    if (lid == UNDEF_LID)
      db_printf("%c %s 0x%08x%08x  => (UNDEFINED)\n",
		red ? 'R' : 'B',
		cty,
		(uint32_t) (oid >> 32),
		(uint32_t) (oid));
    else
      db_printf("%c %s 0x%08x%08x  => %d\n",
		red ? 'R' : 'B',
		cty,
		(uint32_t) (oid >> 32),
		(uint32_t) (oid),
		lid);
  }

#if 0
  else
    db_printf("CKNIL\n");
#endif

  if (this != CkNIL)
    right->DumpTree(indent + 4);
}

void
CoreDirent::ddb_dump()
{
  extern void db_printf(const char *fmt, ...);

  if (this != CkNIL) {
    const char *cty = "??";
    switch(type) {
    case FRM_TYPE_ZDPAGE:
      cty = "zd";
      break;
    case FRM_TYPE_DPAGE:
      cty = "dp";
      break;
    case FRM_TYPE_NODE:
      cty = "nd";
      break;
    case FRM_TYPE_ZNODE:
      cty = "zn";
      break;
    }

    db_printf("%s 0x%X ac=%u lid=0x%x\n", cty, oid, count, lid);
  }
}
#endif /* OPTION_DDB */


#ifndef NDEBUG
bool
CoreDirent::CheckConsistency(const char *msg)
{
  static const char *lastMsg = "(unknown)";

  /* I have seen this routine get interrupted in the middle of the
   * loop when called from the consistency checker thread.  The
   * consequence is that the count and the nFree values do not match
   * up, which causes a fatal halt.
   */
  IRQ::DISABLE();

  uint32_t curFree = nFree;
  
  CoreDirent *cde = freeList;
  uint32_t count = 0;
  while (cde) {
    count++;
    cde = cde->right;
  }

  IRQ::ENABLE();

  /* Use curFree, which is the on-stack copy... */
  if (count != curFree)
    MsgLog::fatal("Counted %d on free list, nFree %d\n",
		  count, nFree);

  if (count != nFree) {
    MsgLog::dprintf(true, "count != nFree. Last msg: %s\n", lastMsg);
    return false;
  }

  lastMsg = msg;
  return true;
}
#endif

#ifdef OPTION_DDB
void
CoreDirent::ddb_showalloc()
{
  extern void db_printf(const char *fmt, ...);

  CoreDirent *cde = freeList;
  uint32_t count = 0;
  while (cde) {
    count++;
    cde = cde->right;
  }
  db_printf("CKD: nTotal: %d nAlloc: %d nFree: %d count: %d\n",
	    CoreDirent::nTotal, CoreDirent::nAlloc, CoreDirent::nFree,
	    count);
}
#endif