directory.c

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

/* Directory object.

   Maintains a mapping from names to keys.  Key operations are LINK,
   LOOKUP, UNLINK.  Uses the BSD-style namespace manipulation routines
   to manage the mapping. A key difference between this code and the
   BSD code is that it does not concern itself with the underlying
   object size.  Instead, we rely on consistent checkpointing for our
   recoverability.

   NOTE that parts of this code are subject to the BSD copyright,
   which is appended at the bottom of the file.

   FIX: An open issue with this design is whether it shouldn't use
   UNICODE internally.  This can be done transparently preserving the
   existing interface by adding new order codes, but I'm sorely
   tempted to do it now.

   I assume that the instruction to be executed is in rcv_code
   and the data in rcv_data.
   The key or the error code is returned in snd_key1 */

#include <eros/target.h>
#include <domain/Runtime.h>
#include <eros/Invoke.h>
#include <eros/Key.h>
#include <eros/NodeKey.h>
#include <eros/ProcessKey.h>
#include <eros/KeyBitsKey.h>
#include <eros/StdKeyType.h>
#include <domain/SpaceBankKey.h>
#include <domain/SuperNodeKey.h>
#include <domain/ConstructorKey.h>
#include <domain/DirectoryKey.h>
#include <domain/domdbg.h>
#include <domain/Runtime.h>

#include "libc.h"
#include "constituents.h"

#define KR_SNODE       KR_APP(0)
#define KR_OSTREAM     KR_APP(1)
#define KR_SCRATCH     KR_APP(2)
#define KR_ARG0        KR_ARG(0)

#define dbg_init    0x1
#define dbg_op      0x2
#define dbg_link    0x4
#define dbg_unlink  0x8
#define dbg_lookup  0x10
#define dbg_find    0x20
#define dbg_freemap 0x40

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

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




/* Theoretically, directories can be more than 1Gb in length, however,
 * in practice this seems unlikely, and we don't currently support
 * it. */

#define	doff_t		Word
#define	MAXDIRSIZE	0x4000000 /* 1 GB */

/* A directory consists of some number of directory entry structures,
 * which are of variable length.  Each directory entry has a struct
 * direct at the front of it, containing its entry number, the length
 * of the entry, and the length of the name contained in the entry.
 * These are followed by the name padded to a 4 byte boundary with
 * null bytes.  All names are guaranteed null terminated.  The maximum
 * length of a name in a directory is MAXNAMLEN.
 *
 * The macro DIRSIZ(fmt, dp) gives the amount of space required to
 * represent a directory entry.  Free space in a directory is
 * represented by entries which have dp->d_reclen > DIRSIZ(fmt, dp).
 *
 * Entries are not permitted to span page boundaries; the last entry
 * in a block will incorporate the free space at the end of the page
 * in it's dp->d_reclen field.
 *
 * When entries are deleted from a directory, the space is returned by
 * simply marking the dp->dt_inuse field false.  When entries are
 * added to a directory, a page with sufficient space is first
 * located.  If one exists, it's free space is first coalesced and
 * then the new entry is added at the end.  If none exists, a new page
 * is tacked on to the end of the directory to hold the insertion.
 * The (empty) space AFTER the last entry is named by state->dir_top.
 *
 * The idea is not to mutate more than one page at a time.  If
 * coalescence were allowed to span page boundaries, the write time
 * would be substantially larger. */

#define	MAXNAMLEN	255

struct	direct {
  uint32_t d_entno;	/* directory ndx */
  uint16_t d_reclen;	/* length of this record */
  uint8_t  d_inuse;	/* entry has content or not */
  uint8_t  d_namlen;	/* true length of string in d_name */
  char	   d_name[MAXNAMLEN + 1];/* name with length <= MAXNAMLEN */
};

/* The DIRSIZ macro gives the minimum record length which will hold
 * the directory entry.  This requires the amount of space in struct
 * direct without the d_name field, plus enough space for the name
 * with a terminating null byte (dp->d_namlen+1), rounded up to a 4
 * byte boundary. */

#define DIRSIZ(dp) ((sizeof(struct direct) - (MAXNAMLEN+1)) + (((dp)->d_namlen+1 + 3) &~ 3))

#define NEXTDIR(dp) ((struct direct *) ((uint8_t *)dp + dp->d_reclen))

#define PAGESTART(dp) ((struct direct *) ((uint32_t)dp & (~(EROS_PAGE_MASK))))


#define true 1
#define false 0


const struct dir_template {
  uint32_t	   dot_entno;
  uint16_t d_reclen;
  uint8_t	   dot_inuse;
  uint8_t	   dot_namlen;
  char	   dot_name[4];	/* must be multiple of 4 */

  uint32_t	   dotdot_entno;
  uint16_t dotdot_reclen;
  uint8_t	   dotdot_inuse;
  uint8_t	   dotdot_namlen;
  char	   dotdot_name[4]; /* ditto */
} template = {
  0,				/* slot 0 */
  12,				/* reclen for "." entry */
  true,				/* entry in use */
  1,				/* name length */
  { '.', 0, 0, 0 },		/* null-padded "." */
  1,				/* slot 1 */
  EROS_PAGE_SIZE - 12, 		/* reclen for ".." entry */
  true,				/* entry in use */
  2,				/* name length */
  { '.', '.', 0, 0 }		/* null-padded ".." */
};

const struct new_page_template {
  uint32_t	   dot_entno;
  uint16_t d_reclen;
  uint8_t	   dot_inuse;
  uint8_t	   dot_namlen;
  char	   dot_name[4];	/* must be multiple of 4 */
} blank_page = {
  0,				/* N/A */
  EROS_PAGE_SIZE,		/* to end of page */
  false,			/* entry in use */
  0,				/* name length */
  { 0, 0, 0, 0 }		/* placeholder, not used! */
};

#define N_FREEMAP_PAGE 0x1

typedef struct {
  uint32_t ndirent;			/* number of entries in directory */
  struct direct *dir_top;
  uint32_t freeMap[(EROS_PAGE_SIZE * N_FREEMAP_PAGE)/sizeof(uint32_t)];
  char name[MAXNAMLEN+1];	/* incoming name on requests + NULL */
} state_t;

typedef uint32_t bool;

const uint32_t __rt_stack_pages = 0x1 + N_FREEMAP_PAGE;

/* First dirent is at the address of the VCS */
#define VCS_LOCATION 0x40000000u

struct direct * const first_entry = (struct direct *) VCS_LOCATION;

uint32_t
alloc_dirent(state_t *state)
{
  uint32_t w;
  uint32_t max_w = EROS_PAGE_SIZE * N_FREEMAP_PAGE / sizeof(uint32_t);
  
  DEBUG(freemap) kprintf(KR_OSTREAM, "state->freeMap is 0x%08x\n", state->freeMap);

  for (w = 0; w < max_w; w++) {
    if (state->freeMap[w] != UINT32_MAX) {
      /* at least one bit is free. */
      uint32_t bit;

      DEBUG(freemap) kprintf(KR_OSTREAM, "Word %d is 0x%08x\n", w, state->freeMap[w]);
      for (bit = 0; bit < UINT32_BITS; bit++) {
	uint32_t which_bit = bit ? (1 << bit) : 1;
	if ((state->freeMap[w] & which_bit) == 0) {
	  DEBUG(freemap) kdprintf(KR_OSTREAM, "Setting bit %d of word %d\n",
		   bit, w);
	  state->freeMap[w] |= which_bit;

	  return bit + w * UINT32_BITS;
	}
      }
    }
  }

  return 0;
}

void
free_dirent(state_t *state, uint32_t ndx)
{
  uint32_t w = ndx / UINT32_BITS;
  uint32_t bit = ndx % UINT32_BITS;
  uint32_t which_bit = bit ? (1 << bit) : 1;
  
  state->freeMap[w] &= ~which_bit;
}

struct direct *
find(char *name, state_t * state)
{
  struct direct *dp = first_entry;
  size_t len = strlen(name);

  DEBUG(find) kdprintf(KR_OSTREAM, "find(\"%s\" [%d]): top=0x%08x\n",
		       name, len, state->dir_top);
	     
  while (dp != state->dir_top) {
    DEBUG(find) kdprintf(KR_OSTREAM, "find(\"%s\"): dp=0x%08x len %d ent %d (\"%s\")\n",
	     name, dp, dp->d_namlen, dp->d_entno,
	     dp->d_inuse ? dp->d_name : "<not in use>");

    if (dp->d_inuse &&
	dp->d_namlen == len &&
	strcmp(dp->d_name, name) == 0)
      return dp;
    
    dp = NEXTDIR(dp);
  }
  
  return 0;
}

uint32_t
lookup (char *name, uint32_t kr, state_t *state)
{
  uint32_t result;
  
  struct direct *dp = find(name, state);

  if (!dp)
    return RC_Directory_NotFound;
  
  DEBUG(lookup) kdprintf(KR_OSTREAM, "lookup(\"%s\"): call to snode w/ entry %d\n",
	   name, dp->d_entno);

  if ((result = supernode_copy(KR_SNODE, dp->d_entno, kr)) != RC_OK) {
    kdprintf(KR_OSTREAM, "Result from supernode_copy: 0x%08x\n", result);
    return result;
  }

  return RC_OK;

}

uint32_t
unlink(char *name, uint32_t kr, state_t * state)
{
  struct direct *dp = find(name, state);

  if (dp) {
    supernode_swap(KR_SNODE, dp->d_entno, KR_VOID, KR_SCRATCH);
    dp->d_inuse = false;
    free_dirent(state, dp->d_entno);

    /* file_unreference(KR_SCRATCH); */
    return RC_OK;
  }
  else
    return RC_Directory_NotFound;
}

/* The passed dirent contains sufficient space. */
bool
insert_dirent(struct direct *dp, char *name, uint32_t kr, state_t *state)
{
  uint32_t entno;
  uint32_t len = strlen(name);

  uint32_t padlen = len;
  padlen += 4;			/* round up to NEXT 4 byte multiple */
  padlen &= ~3u;
  padlen += 8;			/* overhead per dirent */
  
#ifdef NDEBUG
  if (dp->d_inuse) {
    DEBUG(link) kdprintf(KR_OSTREAM, "insert_dirent(): dp 0x%08x in use already!\n",
	     dp);
  }
#endif
  
  entno = alloc_dirent(state);
#if 0
  if (entno == 0)
    return false;
#endif

  
  DEBUG(link) kdprintf(KR_OSTREAM, "insrt_de(0x%08x, \"%s\", %d) entno %d\n",
	   dp, name, kr, entno);
  
  dp->d_entno = entno;
  /* no change to dp->d_reclen */
  dp->d_inuse = true;
  dp->d_namlen = len;
  bcopy(name, dp->d_name, len);

  while (padlen > len)		/* zero-pad the name */
    dp->d_name[len++] = 0;

  supernode_swap(KR_SNODE, entno, kr, KR_VOID);

  return true;
}

/* This routine is only called by link(), and only when it is already
   known that there exists sufficient space in the page to make use