tree.c

subversion-1.4.3-1.tar.gz 配置svn的源码

/* tree.c : tree-like filesystem, built on DAG filesystem
 *
 * ====================================================================
 * Copyright (c) 2000-2006 CollabNet.  All rights reserved.
 *
 * This software is licensed as described in the file COPYING, which
 * you should have received as part of this distribution.  The terms
 * are also available at http://subversion.tigris.org/license-1.html.
 * If newer versions of this license are posted there, you may use a
 * newer version instead, at your option.
 *
 * This software consists of voluntary contributions made by many
 * individuals.  For exact contribution history, see the revision
 * history and logs, available at http://subversion.tigris.org/.
 * ====================================================================
 */


/* The job of this layer is to take a filesystem with lots of node
   sharing going on --- the real DAG filesystem as it appears in the
   database --- and make it look and act like an ordinary tree
   filesystem, with no sharing.

   We do just-in-time cloning: you can walk from some unfinished
   transaction's root down into directories and files shared with
   committed revisions; as soon as you try to change something, the
   appropriate nodes get cloned (and parent directory entries updated)
   invisibly, behind your back.  Any other references you have to
   nodes that have been cloned by other changes, even made by other
   processes, are automatically updated to point to the right clones.  */


#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "svn_private_config.h"
#include "svn_pools.h"
#include "svn_error.h"
#include "svn_path.h"
#include "svn_md5.h"
#include "svn_fs.h"
#include "fs.h"
#include "err.h"
#include "key-gen.h"
#include "dag.h"
#include "lock.h"
#include "tree.h"
#include "revs-txns.h"
#include "fs_fs.h"
#include "id.h"

#include "../libsvn_fs/fs-loader.h"


/* ### I believe this constant will become internal to reps-strings.c.
   ### see the comment in window_consumer() for more information. */

/* ### the comment also seems to need tweaking: the log file stuff
   ### is no longer an issue... */
/* Data written to the filesystem through the svn_fs_apply_textdelta()
   interface is cached in memory until the end of the data stream, or
   until a size trigger is hit.  Define that trigger here (in bytes).
   Setting the value to 0 will result in no filesystem buffering at
   all.  The value only really matters when dealing with file contents
   bigger than the value itself.  Above that point, large values here
   allow the filesystem to buffer more data in memory before flushing
   to the database, which increases memory usage but greatly decreases
   the amount of disk access (and log-file generation) in database.
   Smaller values will limit your overall memory consumption, but can
   drastically hurt throughput by necessitating more write operations
   to the database (which also generates more log-files).  */
#define SVN_FS_WRITE_BUFFER_SIZE          512000

/* The maximum number of cache items to maintain in the node cache. */
#define SVN_FS_NODE_CACHE_MAX_KEYS        32



/* The root structure.  */

/* Structure for svn_fs_root_t's node_cache hash values.  Cache items
   are arranged in a circular LRU list with a dummy entry, and also
   indexed with a hash table. */
typedef struct dag_node_cache_t
{
  const char *path;               /* Path of cached node */
  dag_node_t *node;               /* Cached node */
  struct dag_node_cache_t *prev;  /* Next node in LRU list */
  struct dag_node_cache_t *next;  /* Previous node in LRU list */
  apr_pool_t *pool;               /* Pool in which node is allocated */
} dag_node_cache_t;


typedef enum root_kind_t {
  unspecified_root = 0,
  revision_root,
  transaction_root
} root_kind_t;


typedef struct
{
  /* For revision roots, this is a dag node for the revision's root
     directory.  For transaction roots, we open the root directory
     afresh every time, since the root may have been cloned, or
     the transaction may have disappeared altogether.  */
  dag_node_t *root_dir;

  /* Dummy entry for circular LRU cache, and associated hash table. */
  dag_node_cache_t node_list;
  apr_hash_t *node_cache;

  /* Cache structure for mapping const char * PATH to const char
     *COPYFROM_STRING, so that paths_changed can remember all the
     copyfrom information in the changes file.
     COPYFROM_STRING has the format "REV PATH", or is the empty string if
     the path was added without history. */
  apr_hash_t *copyfrom_cache;
  
} fs_root_data_t;

/* Declared here to resolve the circular dependencies. */
static svn_error_t * get_dag(dag_node_t **dag_node_p, svn_fs_root_t *root,
                             const char *path, apr_pool_t *pool);

static svn_fs_root_t *make_revision_root(svn_fs_t *fs, svn_revnum_t rev,
                                         dag_node_t *root_dir,
                                         apr_pool_t *pool);

static svn_fs_root_t *make_txn_root(svn_fs_t *fs, const char *txn,
                                    apr_uint32_t flags, apr_pool_t *pool);


/*** Node Caching in the Roots. ***/

/* Return NODE for PATH from ROOT's node cache, or NULL if the node
   isn't cached. */
static dag_node_t *
dag_node_cache_get(svn_fs_root_t *root,
                   const char *path,
                   apr_pool_t *pool)
{
  fs_root_data_t *frd = root->fsap_data;
  dag_node_cache_t *item;

  /* Assert valid input. */
  assert(*path == '/');

  /* Look in the cache for our desired item. */
  item = apr_hash_get(frd->node_cache, path, APR_HASH_KEY_STRING);
  if (item && item->node)
    {
      /* Move this cache item to the front of the LRU list. */
      item->prev->next = item->next;
      item->next->prev = item->prev;
      item->prev = &frd->node_list;
      item->next = frd->node_list.next;
      item->prev->next = item;
      item->next->prev = item;

      /* Return the cached node. */
      return svn_fs_fs__dag_dup(item->node, pool);
    }

  return NULL;
}


/* Add the NODE for PATH to ROOT's node cache. */
static void
dag_node_cache_set(svn_fs_root_t *root,
                   const char *path,
                   dag_node_t *node)
{
  fs_root_data_t *frd = root->fsap_data;
  dag_node_cache_t *item;
  apr_pool_t *pool;

  /* What?  No POOL passed to this function?

     To ensure that our cache values live as long as the svn_fs_root_t
     in which they are ultimately stored, and to allow us to free()
     them individually without harming the rest, they are each
     allocated from a subpool of ROOT's pool.  We'll keep one subpool
     around for each cache slot -- as we start expiring stuff
     to make room for more entries, we'll re-use the expired thing's
     pool. */

  /* Assert valid input and state. */
  assert(*path == '/');

  /* If we have an existing entry for this path, reuse it. */
  item = apr_hash_get(frd->node_cache, path, APR_HASH_KEY_STRING);

  /* Otherwise, if the cache is full, reuse the tail of the LRU list. */
  if (!item && apr_hash_count(frd->node_cache) == SVN_FS_NODE_CACHE_MAX_KEYS)
    item = frd->node_list.prev;

  if (item)
    {
      /* Remove the existing item from the cache and reuse its pool. */
      item->prev->next = item->next;
      item->next->prev = item->prev;
      apr_hash_set(frd->node_cache, item->path, APR_HASH_KEY_STRING, NULL);
      pool = item->pool;
      svn_pool_clear(pool);
    }
  else
    {
      /* Allocate a new pool. */
      pool = svn_pool_create(root->pool);
    }

  /* Create and fill in the cache item. */
  item = apr_palloc(pool, sizeof(*item));
  item->path = apr_pstrdup(pool, path);
  item->node = svn_fs_fs__dag_dup(node, pool);
  item->pool = pool;

  /* Link it into the head of the LRU list and hash table. */
  item->prev = &frd->node_list;
  item->next = frd->node_list.next;
  item->prev->next = item;
  item->next->prev = item;
  apr_hash_set(frd->node_cache, item->path, APR_HASH_KEY_STRING, item);
}


/* Invalidate cache entries for PATH and any of its children. */
static void
dag_node_cache_invalidate(svn_fs_root_t *root,
                          const char *path)
{
  fs_root_data_t *frd = root->fsap_data;
  apr_size_t len = strlen(path);
  const char *key;
  dag_node_cache_t *item;

  for (item = frd->node_list.next; item != &frd->node_list; item = item->next)
    {
      key = item->path;
      if (strncmp(key, path, len) == 0 && (key[len] == '/' || !key[len]))
        item->node = NULL;
    }
}



/* Creating transaction and revision root nodes.  */

svn_error_t *
svn_fs_fs__txn_root(svn_fs_root_t **root_p,
                    svn_fs_txn_t *txn,
                    apr_pool_t *pool)
{
  svn_fs_root_t *root;
  apr_uint32_t flags = 0;
  apr_hash_t *txnprops;

  /* Look for the temporary txn props representing 'flags'. */
  SVN_ERR(svn_fs_fs__txn_proplist(&txnprops, txn, pool));
  if (txnprops)
    {
      if (apr_hash_get(txnprops, SVN_FS_PROP_TXN_CHECK_OOD,
                       APR_HASH_KEY_STRING))
        flags |= SVN_FS_TXN_CHECK_OOD;
      
      if (apr_hash_get(txnprops, SVN_FS_PROP_TXN_CHECK_LOCKS,
                       APR_HASH_KEY_STRING))
        flags |= SVN_FS_TXN_CHECK_LOCKS;
    }
  
  root = make_txn_root(txn->fs, txn->id, flags, pool);

  *root_p = root;
  
  return SVN_NO_ERROR;
}


svn_error_t *
svn_fs_fs__revision_root(svn_fs_root_t **root_p,
                         svn_fs_t *fs,
                         svn_revnum_t rev,
                         apr_pool_t *pool)
{
  dag_node_t *root_dir;

  SVN_ERR(svn_fs_fs__check_fs(fs));

  SVN_ERR(svn_fs_fs__dag_revision_root(&root_dir, fs, rev, pool));

  *root_p = make_revision_root(fs, rev, root_dir, pool);
  
  return SVN_NO_ERROR;
}



/* Constructing nice error messages for roots.  */

/* Return the error SVN_ERR_FS_NOT_FOUND, with a detailed error text,
   for PATH in ROOT. */
static svn_error_t *
not_found(svn_fs_root_t *root, const char *path)
{
  if (root->is_txn_root)
    return
      svn_error_createf
      (SVN_ERR_FS_NOT_FOUND, 0,
       _("File not found: transaction '%s', path '%s'"),
       root->txn, path);
  else
    return
      svn_error_createf
      (SVN_ERR_FS_NOT_FOUND, 0,
       _("File not found: revision %ld, path '%s'"),
       root->rev, path);
}


/* Return a detailed `file already exists' message for PATH in ROOT.  */
static svn_error_t *
already_exists(svn_fs_root_t *root, const char *path)
{
  svn_fs_t *fs = root->fs;

  if (root->is_txn_root)
    return
      svn_error_createf
      (SVN_ERR_FS_ALREADY_EXISTS, 0,
       _("File already exists: filesystem '%s', transaction '%s', path '%s'"),
       fs->path, root->txn, path);
  else
    return
      svn_error_createf
      (SVN_ERR_FS_ALREADY_EXISTS, 0,
       _("File already exists: filesystem '%s', revision %ld, path '%s'"),
       fs->path, root->rev, path);
}


static svn_error_t *
not_txn(svn_fs_root_t *root)
{
  return svn_error_create
    (SVN_ERR_FS_NOT_TXN_ROOT, NULL,
     _("Root object must be a transaction root"));
}



/* Getting dag nodes for roots.  */


/* Set *NODE_P to a freshly opened dag node referring to the root
   directory of ROOT, allocating from POOL.  */
static svn_error_t *
root_node(dag_node_t **node_p,
          svn_fs_root_t *root,
          apr_pool_t *pool)
{
  fs_root_data_t *frd = root->fsap_data;
  
  if (! root->is_txn_root)
    {
      /* It's a revision root, so we already have its root directory
         opened.  */
      *node_p = svn_fs_fs__dag_dup(frd->root_dir, pool);
      return SVN_NO_ERROR;
    }
  else
    {
      /* It's a transaction root.  Open a fresh copy.  */
      return svn_fs_fs__dag_txn_root(node_p, root->fs, root->txn, pool);
    }
}