tree.c

linux subdivision ying gai ke yi le ba

/* tree.c : tree-like filesystem, built on DAG filesystem
 *
 * ====================================================================
 * Copyright (c) 2000-2004 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 "svn_hash.h"
#include "svn_sorts.h"
#include "fs.h"
#include "err.h"
#include "trail.h"
#include "node-rev.h"
#include "key-gen.h"
#include "dag.h"
#include "tree.h"
#include "revs-txns.h"
#include "id.h"
#include "bdb/txn-table.h"
#include "bdb/rev-table.h"
#include "bdb/nodes-table.h"
#include "bdb/changes-table.h"
#include "bdb/copies-table.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. */
struct dag_node_cache_t
{
  dag_node_t *node; /* NODE to be cached. */
  int idx;          /* Index into the keys array for this cache item's key. */
  apr_pool_t *pool; /* Pool in which NODE is allocated. */
};


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;

  /* Cache structures, for mapping const char * PATH to const
     struct dag_node_cache_t * structures.

     ### Currently this is only used for revision roots.  To be safe
     for transaction roots, you must have the guarantee that there is
     never more than a single transaction root per Subversion
     transaction ever open at a given time -- having two roots open to
     the same Subversion transaction would be a request for pain.
     Also, you have to ensure that if a 'make_path_mutable()' fails for
     any reason, you don't leave cached nodes for the portion of that
     function that succeeded.  In other words, this cache must never,
     ever, lie. */
  apr_hash_t *node_cache;
  const char *node_cache_keys[SVN_FS_NODE_CACHE_MAX_KEYS];
  int node_cache_idx;
} base_root_data_t;


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_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)
{
  base_root_data_t *brd = root->fsap_data;
  struct dag_node_cache_t *cache_item;

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

  /* Only allow revision roots. */
  if (root->is_txn_root)
    return NULL;

  /* Look in the cache for our desired item. */
  cache_item = apr_hash_get (brd->node_cache, path, APR_HASH_KEY_STRING);
  if (cache_item)
    return svn_fs_base__dag_dup (cache_item->node, pool);

  return NULL;
}


/* Add the NODE for PATH to ROOT's node cache.  Callers should *NOT*
   call this unless they are adding a currently un-cached item to the
   cache, or are replacing the NODE for PATH with a new (different)
   one. */
static void
dag_node_cache_set (svn_fs_root_t *root,
                    const char *path,
                    dag_node_t *node)
{
  base_root_data_t *brd = root->fsap_data;
  const char *cache_path;
  apr_pool_t *cache_pool;
  struct dag_node_cache_t *cache_item;
  int num_keys = apr_hash_count (brd->node_cache);

  /* 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 == '/');
  assert ((brd->node_cache_idx <= num_keys)
          && (num_keys <= SVN_FS_NODE_CACHE_MAX_KEYS));

  /* Only allow revision roots. */
  if (root->is_txn_root)
    return;

  /* Special case: the caller wants us to replace an existing cached
     node with a new one.  If the callers aren't mindless, this should
     only happen when a node is made mutable under a transaction
     root, and that only happens once under that root.  So, we'll be a
     little bit sloppy here, and count on callers doing the right
     thing. */
  cache_item = apr_hash_get (brd->node_cache, path, APR_HASH_KEY_STRING);
  if (cache_item)
    {
      /* ### This section is somehow broken.  I don't know how, but it
         ### is.  And I don't want to spend any more time on it.  So,
         ### callers, use only revision root and don't try to update
         ### an already-cached thing.  -- cmpilato */
      abort();

#if 0
      int cache_index = cache_item->idx;
      cache_path = brd->node_cache_keys[cache_index];
      cache_pool = cache_item->pool;
      cache_item->node = svn_fs_base__dag_dup (node, cache_pool);

      /* Now, move the cache key reference to the end of the keys in
         the keys array (unless it's already at the end).  ### Yes,
         it's a memmove(), but we're not talking about pages of memory
         here. */
      if (cache_index != (num_keys - 1))
        {
          int move_num = SVN_FS_NODE_CACHE_MAX_KEYS - cache_index - 1;
          memmove (brd->node_cache_keys + cache_index,
                   brd->node_cache_keys + cache_index + 1,
                   move_num * sizeof (const char *));
          cache_index = num_keys - 1;
          brd->node_cache_keys[cache_index] = cache_path;
        }

      /* Advance the cache pointers. */
      cache_item->idx = cache_index;
      brd->node_cache_idx = (cache_index + 1) % SVN_FS_NODE_CACHE_MAX_KEYS;
      return;
#endif
    }

  /* We're adding a new cache item.  First, see if we have room for it
     (otherwise, make some room). */
  if (apr_hash_count (brd->node_cache) == SVN_FS_NODE_CACHE_MAX_KEYS)
    {
      /* No room.  Expire the oldest thing. */
      cache_path = brd->node_cache_keys[brd->node_cache_idx];
      cache_item = apr_hash_get (brd->node_cache, cache_path,
                                 APR_HASH_KEY_STRING);
      apr_hash_set (brd->node_cache, cache_path, APR_HASH_KEY_STRING, NULL);
      cache_pool = cache_item->pool;
      svn_pool_clear (cache_pool);
    }
  else
    {
      cache_pool = svn_pool_create (root->pool);
    }

  /* Make the cache item, allocated in its own pool. */
  cache_item = apr_palloc (cache_pool, sizeof (*cache_item));
  cache_item->node = svn_fs_base__dag_dup (node, cache_pool);
  cache_item->idx = brd->node_cache_idx;
  cache_item->pool = cache_pool;

  /* Now add it to the cache. */
  cache_path = apr_pstrdup (cache_pool, path);
  apr_hash_set (brd->node_cache, cache_path, APR_HASH_KEY_STRING, cache_item);
  brd->node_cache_keys[brd->node_cache_idx] = cache_path;

  /* Advance the cache pointer. */
  brd->node_cache_idx = (brd->node_cache_idx + 1) % SVN_FS_NODE_CACHE_MAX_KEYS;
}




/* Creating transaction and revision root nodes.  */

struct txn_root_args
{
  svn_fs_root_t **root_p;
  svn_fs_txn_t *txn;
};


static svn_error_t *
txn_body_txn_root (void *baton,
                   trail_t *trail)
{
  struct txn_root_args *args = baton;
  svn_fs_root_t **root_p = args->root_p;
  svn_fs_txn_t *txn = args->txn;
  svn_fs_t *fs = txn->fs;
  const char *svn_txn_id = txn->id;
  const svn_fs_id_t *root_id, *base_root_id;
  svn_fs_root_t *root;

  /* Verify that the transaction actually exists.  */
  SVN_ERR (svn_fs_base__get_txn_ids (&root_id, &base_root_id, fs,
                                     svn_txn_id, trail));

  root = make_txn_root (fs, svn_txn_id, trail->pool);

  *root_p = root;
  return SVN_NO_ERROR;
}


svn_error_t *
svn_fs_base__txn_root (svn_fs_root_t **root_p,
                       svn_fs_txn_t *txn,
                       apr_pool_t *pool)
{
  svn_fs_root_t *root;
  struct txn_root_args args;

  args.root_p = &root;
  args.txn = txn;
  SVN_ERR (svn_fs_base__retry_txn (txn->fs, txn_body_txn_root, &args, pool));

  *root_p = root;
  return SVN_NO_ERROR;
}


struct revision_root_args
{
  svn_fs_root_t **root_p;
  svn_revnum_t rev;
};


static svn_error_t *
txn_body_revision_root (void *baton,
                        trail_t *trail)
{
  struct revision_root_args *args = baton;
  dag_node_t *root_dir;
  svn_fs_root_t *root;

  SVN_ERR (svn_fs_base__dag_revision_root (&root_dir, trail->fs, args->rev,
                                           trail));
  root = make_revision_root (trail->fs, args->rev, root_dir, trail->pool);

  *args->root_p = root;
  return SVN_NO_ERROR;
}


svn_error_t *
svn_fs_base__revision_root (svn_fs_root_t **root_p,
                            svn_fs_t *fs,
                            svn_revnum_t rev,
                            apr_pool_t *pool)
{
  struct revision_root_args args;
  svn_fs_root_t *root;

  SVN_ERR (svn_fs_base__check_fs (fs));

  args.root_p = &root;
  args.rev = rev;
  SVN_ERR (svn_fs_base__retry_txn (fs, txn_body_revision_root, &args, pool));

  *root_p = root;
  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'"),