| /* nodes-table.c : working with the `nodes' table |
| * |
| * ==================================================================== |
| * Copyright (c) 2000-2002 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/. |
| * ==================================================================== |
| */ |
| |
| #include <string.h> |
| |
| #include "svn_fs.h" |
| |
| #include "db.h" |
| #include "fs.h" |
| #include "err.h" |
| #include "dbt.h" |
| #include "skel.h" |
| #include "trail.h" |
| #include "validate.h" |
| #include "nodes-table.h" |
| #include "id.h" |
| |
| |
| |
| /* Opening/creating the `nodes' table. */ |
| |
| |
| /* Compare two node ID's, according to the rules in `structure'. */ |
| static int |
| compare_ids (svn_fs_id_t *a, svn_fs_id_t *b) |
| { |
| int i = 0; |
| |
| while (a[i] == b[i]) |
| { |
| if (a[i] == -1) |
| return 0; |
| i++; |
| } |
| |
| /* Different nodes, or different branches, are ordered by their |
| node / branch numbers. */ |
| if ((i & 1) == 0) |
| return a[i] - b[i]; |
| |
| /* This function is only prepared to handle node revision ID's. */ |
| if (a[i] == -1 || b[i] == -1) |
| abort (); |
| |
| /* Different revisions of the same node are ordered by revision number. */ |
| if (a[i + 1] == -1 && b[i + 1] == -1) |
| return a[i] - b[i]; |
| |
| /* A branch off of any revision of a node comes after all revisions |
| of that node. */ |
| if (a[i + 1] == -1) |
| return -1; |
| if (b[i + 1] == -1) |
| return 1; |
| |
| /* Branches are ordered by increasing revision number. */ |
| return a[i] - b[i]; |
| } |
| |
| |
| /* Parse a node revision ID from D. The ID returned is allocated |
| using `malloc', not in an APR pool. Return zero if D does not |
| contain a well-formed node revision ID. */ |
| static svn_fs_id_t * |
| parse_node_revision_dbt (const DBT *d) |
| { |
| svn_fs_id_t *id = svn_fs_parse_id (d->data, d->size, 0); |
| |
| if (! id) |
| return 0; |
| |
| /* It must be a node revision ID, not a node ID. */ |
| if (svn_fs__id_length (id) & 1) |
| { |
| free (id); |
| return 0; |
| } |
| |
| return id; |
| } |
| |
| |
| /* The key comparison function for the `nodes' table. |
| |
| Strictly speaking, this function only needs to handle strings that |
| we actually use as keys in the table. However, if we happen to |
| insert garbage keys, and this comparison function doesn't do |
| something consistent with them (i.e., something transitive and |
| reflexive), we can actually corrupt the btree structure. Which |
| seems unfriendly. |
| |
| So this function tries to act as a proper comparison for any two |
| arbitrary byte strings. Two well-formed node revisions ID's compare |
| according to the rules described in the `structure' file; any |
| malformed key comes before any well-formed key; and two malformed |
| keys come in byte-by-byte order. |
| |
| NOTE WELL: this function and its helpers use `malloc' to get space |
| for the parsed node revision ID's. In general, we try to use pools |
| for everything in Subversion, but in this case it's not practical. |
| Berkeley DB doesn't provide any way to pass a baton through to the |
| btree comparison function. Even if it did, since Berkeley DB needs |
| to invoke the comparison function at pretty arbitrary times, you'd |
| have to pass the baton to almost every Berkeley DB operation. You |
| could stuff a pool pointer in a global variable, but then you'd |
| have to make sure the pool was up to date before every Berkeley DB |
| operation; you'd surely forget, leading to crashes... Using malloc |
| is more maintainable. Since the comparison function isn't allowed |
| to signal an error anyway, the need for pools isn't quite as urgent |
| as in other code, but we still need to take care. */ |
| static int |
| compare_nodes_keys (DB *dummy, const DBT *ak, const DBT *bk) |
| { |
| svn_fs_id_t *a = parse_node_revision_dbt (ak); |
| svn_fs_id_t *b = parse_node_revision_dbt (bk); |
| int result; |
| |
| /* Two well-formed keys are compared by the rules in `structure'. */ |
| if (a && b) |
| result = compare_ids (a, b); |
| |
| /* Malformed keys come before well-formed keys. */ |
| else if (a) |
| result = 1; |
| else if (b) |
| result = -1; |
| |
| /* Two malformed keys are compared byte-by-byte. */ |
| else |
| result = svn_fs__compare_dbt (ak, bk); |
| |
| if (a) free (a); |
| if (b) free (b); |
| |
| return result; |
| } |
| |
| |
| int |
| svn_fs__open_nodes_table (DB **nodes_p, |
| DB_ENV *env, |
| int create) |
| { |
| DB *nodes; |
| |
| DB_ERR (db_create (&nodes, env, 0)); |
| DB_ERR (nodes->set_bt_compare (nodes, compare_nodes_keys)); |
| DB_ERR (nodes->open (nodes, "nodes", 0, DB_BTREE, |
| create ? (DB_CREATE | DB_EXCL) : 0, |
| 0666)); |
| |
| *nodes_p = nodes; |
| return 0; |
| } |
| |
| |
| |
| /* Validating NODE-REVISION skels. */ |
| |
| |
| static int |
| is_valid_option (skel_t *skel) |
| { |
| int len = svn_fs__list_length (skel); |
| |
| if (len == 3 |
| && svn_fs__matches_atom (skel->children, "copy") |
| && skel->children->next->is_atom |
| && skel->children->next->next->is_atom) |
| { |
| return 1; |
| } |
| |
| return 0; |
| } |
| |
| |
| static int |
| is_valid_header (skel_t *skel, skel_t **kind_p) |
| { |
| int len = svn_fs__list_length (skel); |
| |
| if (len >= 2) |
| { |
| if (skel->children->is_atom && skel->children->next->is_atom) |
| { |
| skel_t *option; |
| |
| for (option = skel->children->next->next; |
| option; |
| option = option->next) |
| if (! is_valid_option (option)) |
| return 0; |
| |
| *kind_p = skel->children; |
| return 1; |
| } |
| } |
| |
| return 0; |
| } |
| |
| |
| static int |
| is_mutable_header (skel_t *skel) |
| { |
| return ((skel->children->next->len == 0) ? 1 : 0); |
| } |
| |
| |
| static int |
| is_valid_node_revision (skel_t *skel) |
| { |
| int len = svn_fs__list_length (skel); |
| |
| if (len >= 1) |
| { |
| skel_t *header = skel->children; |
| skel_t *kind; |
| |
| if (is_valid_header (header, &kind)) |
| { |
| if (svn_fs__matches_atom (kind, "dir") |
| && len == 3 |
| && header->next->is_atom |
| && header->next->next->is_atom) |
| return 1; |
| |
| if (svn_fs__matches_atom (kind, "file") |
| && len >= 3 |
| && header->next->is_atom |
| && header->next->next->is_atom) |
| { |
| if ((len == 3) && (! header->next->next->next)) |
| return 1; |
| |
| /* edit-data-key can only exist on mutable file nodes. */ |
| if ((len == 4) |
| && is_mutable_header (header) |
| && header->next->next->next->is_atom) |
| return 1; |
| } |
| } |
| } |
| |
| return 0; |
| } |
| |
| |
| |
| /* Choosing node revision ID's. */ |
| |
| |
| svn_error_t * |
| svn_fs__new_node_id (svn_fs_id_t **id_p, |
| svn_fs_t *fs, |
| trail_t *trail) |
| { |
| int db_err; |
| DBC *cursor = 0; |
| DBT key, value; |
| svn_fs_id_t *id; |
| |
| /* Create a database cursor. */ |
| SVN_ERR (DB_WRAP (fs, "choosing new node ID (creating cursor)", |
| fs->nodes->cursor (fs->nodes, trail->db_txn, &cursor, 0))); |
| |
| /* Find the last entry in the `nodes' table, and increment its node |
| number. */ |
| db_err = cursor->c_get (cursor, |
| svn_fs__result_dbt (&key), |
| svn_fs__nodata_dbt (&value), |
| DB_LAST); |
| svn_fs__track_dbt (&key, trail->pool); |
| if (db_err) |
| { |
| /* Free the cursor. Ignore any error value --- the error above |
| is more interesting. */ |
| cursor->c_close (cursor); |
| |
| if (db_err == DB_NOTFOUND) |
| /* The root directory should always be present, at least. */ |
| return |
| svn_error_createf |
| (SVN_ERR_FS_CORRUPT, 0, 0, fs->pool, |
| "root directory missing from `nodes' table, in filesystem `%s'", |
| fs->path); |
| |
| return DB_WRAP (fs, "choosing new node ID (finding last entry)", db_err); |
| } |
| |
| /* Try to parse the key as a node revision ID. */ |
| id = svn_fs_parse_id (key.data, key.size, trail->pool); |
| if (! id |
| || svn_fs__id_length (id) < 2) |
| { |
| cursor->c_close (cursor); |
| return svn_fs__err_corrupt_nodes_key (fs); |
| } |
| |
| /* We've got the value; close the cursor. */ |
| SVN_ERR (DB_WRAP (fs, "choosing new node ID (closing cursor)", |
| cursor->c_close (cursor))); |
| |
| /* Given the ID of the last node revision, what's the ID of the |
| first revision of an entirely new node? */ |
| id[0]++; |
| id[1] = 1; |
| id[2] = -1; |
| |
| *id_p = id; |
| return SVN_NO_ERROR; |
| } |
| |
| |
| /* Find the last entry before KEY in the btree table DB. |
| |
| KEY must be initialized as for any normal Berkeley DB operation. |
| The settings of KEY->flags and KEY's other members control how the |
| value is returned. |
| |
| If DB_TXN is non-zero, perform the operation as part of that |
| Berkeley DB transaction. */ |
| static int |
| last_key_before (DB *db, |
| DB_TXN *db_txn, |
| DBT *key) |
| { |
| int db_err; |
| DBC *cursor; |
| DBT temp_key, value; |
| |
| /* Create a cursor into the table. */ |
| DB_ERR (db->cursor (db, db_txn, &cursor, 0)); |
| |
| /* Position CURSOR to the first table entry at or after KEY. |
| Don't bother retrieving the key or value we find there. */ |
| svn_fs__nodata_dbt (&temp_key); |
| temp_key.data = key->data; |
| temp_key.size = key->size; |
| svn_fs__nodata_dbt (&value); |
| db_err = cursor->c_get (cursor, &temp_key, &value, DB_SET_RANGE); |
| if (db_err && db_err != DB_NOTFOUND) |
| { |
| cursor->c_close (cursor); |
| return db_err; |
| } |
| |
| /* If db_err == 0, we found the first table entry at or after KEY; |
| the record we want comes immediately before that. |
| |
| If db_err == DB_NOTFOUND, then we couldn't find any entry at or |
| after KEY, so the record we want must be the last record in the |
| table. */ |
| db_err = cursor->c_get (cursor, key, svn_fs__nodata_dbt (&value), |
| db_err == DB_NOTFOUND ? DB_LAST : DB_PREV); |
| if (db_err) |
| { |
| cursor->c_close (cursor); |
| return db_err; |
| } |
| |
| /* We're finished with the cursor now. */ |
| DB_ERR (cursor->c_close (cursor)); |
| |
| return 0; |
| } |
| |
| |
| svn_error_t * |
| svn_fs__new_successor_id (svn_fs_id_t **successor_p, |
| svn_fs_t *fs, |
| const svn_fs_id_t *id, |
| trail_t *trail) |
| { |
| int id_len = svn_fs__id_length (id); |
| svn_fs_id_t *new_id; |
| apr_pool_t *pool = trail->pool; |
| DB_TXN *db_txn = trail->db_txn; |
| DBT key, value; |
| int db_err; |
| |
| /* Make sure ID is really a node revision ID. */ |
| if (id_len & 1) |
| return svn_fs__err_corrupt_id (fs, id); |
| |
| /* Set NEW_ID to the next node revision after ID. Allocate some |
| extra room, in case we need to construct a branch ID below. */ |
| new_id = (svn_fs_id_t *) apr_palloc (pool, |
| (id_len + 3) * sizeof (*new_id)); |
| memcpy (new_id, id, (id_len + 1) * sizeof (*id)); /* copy the -1 */ |
| new_id[id_len - 1]++; /* increment the revision number */ |
| |
| /* Check to see if there already exists a node whose ID is NEW_ID. */ |
| db_err = fs->nodes->get (fs->nodes, db_txn, |
| svn_fs__id_to_dbt (&key, new_id, pool), |
| svn_fs__nodata_dbt (&value), |
| 0); |
| if (db_err == DB_NOTFOUND) |
| { |
| /* NEW_ID isn't currently in use, so return that. */ |
| *successor_p = new_id; |
| return SVN_NO_ERROR; |
| } |
| else |
| SVN_ERR (DB_WRAP (fs, "checking for next node revision", db_err)); |
| |
| /* Okay, the next revision of ID already exists, so we'll need to make |
| a new branch. What's the next available branch number? |
| |
| The sort order for the nodes table says that all revisions of a |
| node come together, followed by all branches from any revision of |
| that node; the branches are sorted by the revision they branch |
| from, and then by branch number. |
| |
| So, if our node revision ID is N.V, then all its branches will |
| come immediately before the first branch from N.(V+1). So we |
| find the last node in the table before node ID N.(V+1).1.1; that |
| node is (perhaps a branch from) the last branch from N.V. |
| |
| NEW_ID is currently N.(V+1); stick on the ".1.1". */ |
| new_id[id_len + 0] = 1; |
| new_id[id_len + 1] = 1; |
| new_id[id_len + 2] = -1; |
| SVN_ERR (DB_WRAP (fs, "checking for next node branch", |
| last_key_before (fs->nodes, db_txn, |
| svn_fs__id_to_dbt (&key, new_id, pool)))); |
| |
| { |
| svn_fs_id_t *last_branch_id = svn_fs_parse_id (key.data, key.size, pool); |
| int last_branch_len; |
| |
| if (! last_branch_id) |
| return svn_fs__err_corrupt_nodes_key (fs); |
| |
| last_branch_len = svn_fs__id_length (last_branch_id); |
| |
| /* Only node revision ID's may appear as keys in the `nodes' table. */ |
| if (last_branch_len & 1) |
| return svn_fs__err_corrupt_nodes_key (fs); |
| |
| /* If the last key before NEW_ID is just another revision of node |
| N (specifically, the last revision), then there are no branches |
| yet. */ |
| if (last_branch_len == id_len) |
| { |
| /* The first branch from N.V is N.V.1.1. */ |
| memcpy (new_id, id, id_len * sizeof (*id)); |
| new_id[id_len + 0] = 1; |
| new_id[id_len + 1] = 1; |
| new_id[id_len + 2] = -1; |
| |
| *successor_p = new_id; |
| return SVN_NO_ERROR; |
| } |
| |
| /* If the last key before NEW_ID is a branch off of ID, then |
| choose the next branch number. */ |
| else if (last_branch_len > id_len) |
| { |
| /* The last key has the form N.V.B... so the first revision |
| on our new branch is N.V.(B+1).1. */ |
| memcpy (new_id, last_branch_id, (id_len + 1) * sizeof (*id)); |
| new_id[id_len + 0]++; |
| new_id[id_len + 1] = 1; |
| new_id[id_len + 2] = -1; |
| |
| *successor_p = new_id; |
| return SVN_NO_ERROR; |
| } |
| |
| /* Otherwise, something strange is going on. */ |
| else |
| return svn_fs__err_corrupt_nodes_key (fs); |
| } |
| } |
| |
| |
| |
| /* Removing node revisions. */ |
| svn_error_t * |
| svn_fs__delete_nodes_entry (svn_fs_t *fs, |
| const svn_fs_id_t *id, |
| trail_t *trail) |
| { |
| DBT key; |
| |
| SVN_ERR (DB_WRAP (fs, "deleting entry from `nodes' table", |
| fs->nodes->del (fs->nodes, |
| trail->db_txn, |
| svn_fs__id_to_dbt (&key, id, trail->pool), |
| 0))); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| |
| |
| |
| /* Storing and retrieving NODE-REVISION skels. */ |
| |
| |
| svn_error_t * |
| svn_fs__get_node_revision (skel_t **skel_p, |
| svn_fs_t *fs, |
| const svn_fs_id_t *id, |
| trail_t *trail) |
| { |
| skel_t *skel; |
| int db_err; |
| DBT key, value; |
| |
| db_err = fs->nodes->get (fs->nodes, trail->db_txn, |
| svn_fs__id_to_dbt (&key, id, trail->pool), |
| svn_fs__result_dbt (&value), |
| 0); |
| svn_fs__track_dbt (&value, trail->pool); |
| |
| /* If there's no such node, return an appropriately specific error. */ |
| if (db_err == DB_NOTFOUND) |
| return svn_fs__err_dangling_id (fs, id); |
| |
| /* Handle any other error conditions. */ |
| SVN_ERR (DB_WRAP (fs, "reading node revision", db_err)); |
| |
| /* Parse and check the NODE-REVISION skel. */ |
| skel = svn_fs__parse_skel (value.data, value.size, trail->pool); |
| if (! skel |
| || ! is_valid_node_revision (skel)) |
| return svn_fs__err_corrupt_node_revision (fs, id); |
| |
| *skel_p = skel; |
| return SVN_NO_ERROR; |
| } |
| |
| |
| svn_error_t * |
| svn_fs__put_node_revision (svn_fs_t *fs, |
| const svn_fs_id_t *id, |
| skel_t *skel, |
| trail_t *trail) |
| { |
| DB_TXN *db_txn = trail->db_txn; |
| apr_pool_t *pool = trail->pool; |
| DBT key, value; |
| |
| if (! is_valid_node_revision (skel)) |
| return svn_fs__err_corrupt_node_revision (fs, id); |
| |
| SVN_ERR (DB_WRAP (fs, "storing node revision", |
| fs->nodes->put (fs->nodes, db_txn, |
| svn_fs__id_to_dbt (&key, id, pool), |
| svn_fs__skel_to_dbt (&value, skel, pool), |
| 0))); |
| |
| return 0; |
| } |
| |
| |
| |
| /* |
| * local variables: |
| * eval: (load-file "../../tools/dev/svn-dev.el") |
| * end: |
| */ |
