1 /* tree.c : tree-like filesystem, built on DAG filesystem
2 *
3 * ====================================================================
4 * Licensed to the Apache Software Foundation (ASF) under one
5 * or more contributor license agreements. See the NOTICE file
6 * distributed with this work for additional information
7 * regarding copyright ownership. The ASF licenses this file
8 * to you under the Apache License, Version 2.0 (the
9 * "License"); you may not use this file except in compliance
10 * with the License. You may obtain a copy of the License at
11 *
12 * http://www.apache.org/licenses/LICENSE-2.0
13 *
14 * Unless required by applicable law or agreed to in writing,
15 * software distributed under the License is distributed on an
16 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17 * KIND, either express or implied. See the License for the
18 * specific language governing permissions and limitations
19 * under the License.
20 * ====================================================================
21 */
22
23
24 /* The job of this layer is to take a filesystem with lots of node
25 sharing going on --- the real DAG filesystem as it appears in the
26 database --- and make it look and act like an ordinary tree
27 filesystem, with no sharing.
28
29 We do just-in-time cloning: you can walk from some unfinished
30 transaction's root down into directories and files shared with
31 committed revisions; as soon as you try to change something, the
32 appropriate nodes get cloned (and parent directory entries updated)
33 invisibly, behind your back. Any other references you have to
34 nodes that have been cloned by other changes, even made by other
35 processes, are automatically updated to point to the right clones. */
36
37
38 #include <stdlib.h>
39 #include <string.h>
40 #include <assert.h>
41 #include <apr_pools.h>
42 #include <apr_hash.h>
43
44 #include "svn_hash.h"
45 #include "svn_private_config.h"
46 #include "svn_pools.h"
47 #include "svn_error.h"
48 #include "svn_path.h"
49 #include "svn_mergeinfo.h"
50 #include "svn_fs.h"
51 #include "svn_props.h"
52 #include "svn_sorts.h"
53
54 #include "fs.h"
55 #include "cached_data.h"
56 #include "dag.h"
57 #include "lock.h"
58 #include "tree.h"
59 #include "fs_fs.h"
60 #include "id.h"
61 #include "pack.h"
62 #include "temp_serializer.h"
63 #include "transaction.h"
64 #include "util.h"
65
66 #include "private/svn_mergeinfo_private.h"
67 #include "private/svn_subr_private.h"
68 #include "private/svn_fs_util.h"
69 #include "private/svn_fspath.h"
70 #include "../libsvn_fs/fs-loader.h"
71
72
73
74 /* The root structures.
75
76 Why do they contain different data? Well, transactions are mutable
77 enough that it isn't safe to cache the DAG node for the root
78 directory or the hash of copyfrom data: somebody else might modify
79 them concurrently on disk! (Why is the DAG node cache safer than
80 the root DAG node? When cloning transaction DAG nodes in and out
81 of the cache, all of the possibly-mutable data from the
82 node_revision_t inside the dag_node_t is dropped.) Additionally,
83 revisions are immutable enough that their DAG node cache can be
84 kept in the FS object and shared among multiple revision root
85 objects.
86 */
87 typedef dag_node_t fs_rev_root_data_t;
88
89 typedef struct fs_txn_root_data_t
90 {
91 /* TXN_ID value from the main struct but as a struct instead of a string */
92 svn_fs_fs__id_part_t txn_id;
93
94 /* Cache of txn DAG nodes (without their nested noderevs, because
95 * it's mutable). Same keys/values as ffd->rev_node_cache. */
96 svn_cache__t *txn_node_cache;
97 } fs_txn_root_data_t;
98
99 /* Declared here to resolve the circular dependencies. */
100 static svn_error_t * get_dag(dag_node_t **dag_node_p,
101 svn_fs_root_t *root,
102 const char *path,
103 apr_pool_t *pool);
104
105 static svn_fs_root_t *make_revision_root(svn_fs_t *fs, svn_revnum_t rev,
106 dag_node_t *root_dir,
107 apr_pool_t *pool);
108
109 static svn_error_t *make_txn_root(svn_fs_root_t **root_p,
110 svn_fs_t *fs,
111 const svn_fs_fs__id_part_t *txn,
112 svn_revnum_t base_rev,
113 apr_uint32_t flags,
114 apr_pool_t *pool);
115
116 static svn_error_t *fs_closest_copy(svn_fs_root_t **root_p,
117 const char **path_p,
118 svn_fs_root_t *root,
119 const char *path,
120 apr_pool_t *pool);
121
122
123 /*** Node Caching ***/
124
125 /* 1st level cache */
126
127 /* An entry in the first-level cache. REVISION and PATH form the key that
128 will ultimately be matched.
129 */
130 typedef struct cache_entry_t
131 {
132 /* hash value derived from PATH, REVISION.
133 Used to short-circuit failed lookups. */
134 apr_uint32_t hash_value;
135
136 /* revision to which the NODE belongs */
137 svn_revnum_t revision;
138
139 /* path of the NODE */
140 char *path;
141
142 /* cached value of strlen(PATH). */
143 apr_size_t path_len;
144
145 /* the node allocated in the cache's pool. NULL for empty entries. */
146 dag_node_t *node;
147 } cache_entry_t;
148
149 /* Number of entries in the cache. Keep this low to keep pressure on the
150 CPU caches low as well. A binary value is most efficient. If we walk
151 a directory tree, we want enough entries to store nodes for all files
152 without overwriting the nodes for the parent folder. That way, there
153 will be no unnecessary misses (except for a few random ones caused by
154 hash collision).
155
156 The actual number of instances may be higher but entries that got
157 overwritten are no longer visible.
158 */
159 enum { BUCKET_COUNT = 256 };
160
161 /* The actual cache structure. All nodes will be allocated in POOL.
162 When the number of INSERTIONS (i.e. objects created form that pool)
163 exceeds a certain threshold, the pool will be cleared and the cache
164 with it.
165 */
166 struct fs_fs_dag_cache_t
167 {
168 /* fixed number of (possibly empty) cache entries */
169 cache_entry_t buckets[BUCKET_COUNT];
170
171 /* pool used for all node allocation */
172 apr_pool_t *pool;
173
174 /* number of entries created from POOL since the last cleanup */
175 apr_size_t insertions;
176
177 /* Property lookups etc. have a very high locality (75% re-hit).
178 Thus, remember the last hit location for optimistic lookup. */
179 apr_size_t last_hit;
180
181 /* Position of the last bucket hit that actually had a DAG node in it.
182 LAST_HIT may refer to a bucket that matches path@rev but has not
183 its NODE element set, yet.
184 This value is a mere hint for optimistic lookup and any value is
185 valid (as long as it is < BUCKET_COUNT). */
186 apr_size_t last_non_empty;
187 };
188
189 fs_fs_dag_cache_t*
svn_fs_fs__create_dag_cache(apr_pool_t * pool)190 svn_fs_fs__create_dag_cache(apr_pool_t *pool)
191 {
192 fs_fs_dag_cache_t *result = apr_pcalloc(pool, sizeof(*result));
193 result->pool = svn_pool_create(pool);
194
195 return result;
196 }
197
198 /* Clears the CACHE at regular intervals (destroying all cached nodes)
199 */
200 static void
auto_clear_dag_cache(fs_fs_dag_cache_t * cache)201 auto_clear_dag_cache(fs_fs_dag_cache_t* cache)
202 {
203 if (cache->insertions > BUCKET_COUNT)
204 {
205 svn_pool_clear(cache->pool);
206
207 memset(cache->buckets, 0, sizeof(cache->buckets));
208 cache->insertions = 0;
209 }
210 }
211
212 /* Returns a 32 bit hash value for the given REVISION and PATH of exactly
213 * PATH_LEN chars.
214 */
215 static apr_uint32_t
hash_func(svn_revnum_t revision,const char * path,apr_size_t path_len)216 hash_func(svn_revnum_t revision,
217 const char *path,
218 apr_size_t path_len)
219 {
220 apr_size_t i;
221 apr_uint32_t hash_value = (apr_uint32_t)revision;
222
223 #if SVN_UNALIGNED_ACCESS_IS_OK
224 /* "randomizing" / distributing factor used in our hash function */
225 const apr_uint32_t factor = 0xd1f3da69;
226 #endif
227
228 /* Calculate the hash value
229 (HASH_VALUE has been initialized to REVISION).
230
231 Note that the actual hash function is arbitrary as long as its result
232 in HASH_VALUE only depends on REVISION and *PATH. However, we try to
233 make as much of *PATH influence the result as possible to get an "even"
234 spread across the hash buckets (maximizes our cache retention rate and
235 thus the hit rates).
236
237 When chunked access is possible (independent of the PATH pointer's
238 value!), we read 4 bytes at once and multiply the hash value with a
239 FACTOR that mirror / pattern / shift all 4 input bytes to various bits
240 of the result. The final result will be taken from the MSBs.
241
242 When chunked access is not possible (not supported by CPU or odd bytes
243 at the end of *PATH), we use the simple traditional "* 33" hash
244 function that works very well with texts / paths and that e.g. APR uses.
245
246 Please note that the bytewise and the chunked calculation are *NOT*
247 interchangeable as they will yield different results for the same input.
248 For any given machine and *PATH, we must use a fixed combination of the
249 two functions.
250 */
251 i = 0;
252 #if SVN_UNALIGNED_ACCESS_IS_OK
253 /* We relax the dependency chain between iterations by processing
254 two chunks from the input per hash_value self-multiplication.
255 The HASH_VALUE update latency is now 1 MUL latency + 1 ADD latency
256 per 2 chunks instead of 1 chunk.
257 */
258 for (; i + 8 <= path_len; i += 8)
259 hash_value = hash_value * factor * factor
260 + ( *(const apr_uint32_t*)(path + i) * factor
261 + *(const apr_uint32_t*)(path + i + 4));
262 #endif
263
264 for (; i < path_len; ++i)
265 /* Help GCC to minimize the HASH_VALUE update latency by splitting the
266 MUL 33 of the naive implementation: h = h * 33 + path[i]. This
267 shortens the dependency chain from 1 shift + 2 ADDs to 1 shift + 1 ADD.
268 */
269 hash_value = hash_value * 32 + (hash_value + (unsigned char)path[i]);
270
271 return hash_value;
272 }
273
274 /* For the given REVISION and PATH, return the respective node found in
275 * CACHE. If there is none, return NULL.
276 */
277 static dag_node_t *
cache_lookup(fs_fs_dag_cache_t * cache,svn_revnum_t revision,const char * path)278 cache_lookup( fs_fs_dag_cache_t *cache
279 , svn_revnum_t revision
280 , const char *path)
281 {
282 apr_size_t bucket_index;
283 apr_size_t path_len = strlen(path);
284 apr_uint32_t hash_value;
285
286 /* optimistic lookup: hit the same bucket again? */
287 cache_entry_t *result = &cache->buckets[cache->last_hit];
288 if ( (result->revision == revision)
289 && (result->path_len == path_len)
290 && !memcmp(result->path, path, path_len))
291 {
292 /* Remember the position of the last node we found in this cache. */
293 if (result->node)
294 cache->last_non_empty = cache->last_hit;
295
296 return result->node;
297 }
298
299 /* need to do a full lookup. */
300 hash_value = hash_func(revision, path, path_len);
301
302 bucket_index = hash_value + (hash_value >> 16);
303 bucket_index = (bucket_index + (bucket_index >> 8)) % BUCKET_COUNT;
304
305 /* access the corresponding bucket and remember its location */
306 result = &cache->buckets[bucket_index];
307 cache->last_hit = bucket_index;
308
309 /* if it is *NOT* a match, clear the bucket, expect the caller to fill
310 in the node and count it as an insertion */
311 if ( (result->hash_value != hash_value)
312 || (result->revision != revision)
313 || (result->path_len != path_len)
314 || memcmp(result->path, path, path_len))
315 {
316 return NULL;
317 }
318 else if (result->node)
319 {
320 /* This bucket is valid & has a suitable DAG node in it.
321 Remember its location. */
322 cache->last_non_empty = bucket_index;
323 }
324
325 return result->node;
326 }
327
328 /* Store a copy of NODE in CACHE, taking REVISION and PATH as key.
329 * This function will clean the cache at regular intervals.
330 */
331 static void
cache_insert(fs_fs_dag_cache_t * cache,svn_revnum_t revision,const char * path,dag_node_t * node)332 cache_insert(fs_fs_dag_cache_t *cache,
333 svn_revnum_t revision,
334 const char *path,
335 dag_node_t *node)
336 {
337 apr_size_t bucket_index;
338 apr_size_t path_len = strlen(path);
339 apr_uint32_t hash_value;
340 cache_entry_t *entry;
341
342 auto_clear_dag_cache(cache);
343
344 /* calculate the bucket index to use */
345 hash_value = hash_func(revision, path, path_len);
346
347 bucket_index = hash_value + (hash_value >> 16);
348 bucket_index = (bucket_index + (bucket_index >> 8)) % BUCKET_COUNT;
349
350 /* access the corresponding bucket and remember its location */
351 entry = &cache->buckets[bucket_index];
352 cache->last_hit = bucket_index;
353
354 /* if it is *NOT* a match, clear the bucket, expect the caller to fill
355 in the node and count it as an insertion */
356 entry->hash_value = hash_value;
357 entry->revision = revision;
358 if (entry->path_len < path_len)
359 entry->path = apr_palloc(cache->pool, path_len + 1);
360 entry->path_len = path_len;
361 memcpy(entry->path, path, path_len + 1);
362
363 entry->node = svn_fs_fs__dag_dup(node, cache->pool);
364 cache->insertions++;
365 }
366
367 /* Optimistic lookup using the last seen non-empty location in CACHE.
368 Return the node of that entry, if it is still in use and matches PATH.
369 Return NULL otherwise. Since the caller usually already knows the path
370 length, provide it in PATH_LEN. */
371 static dag_node_t *
cache_lookup_last_path(fs_fs_dag_cache_t * cache,const char * path,apr_size_t path_len)372 cache_lookup_last_path(fs_fs_dag_cache_t *cache,
373 const char *path,
374 apr_size_t path_len)
375 {
376 cache_entry_t *result = &cache->buckets[cache->last_non_empty];
377 assert(strlen(path) == path_len);
378
379 if ( result->node
380 && (result->path_len == path_len)
381 && !memcmp(result->path, path, path_len))
382 {
383 return result->node;
384 }
385
386 return NULL;
387 }
388
389 /* 2nd level cache */
390
391 /* Find and return the DAG node cache for ROOT and the key that
392 should be used for PATH.
393
394 Pool will only be used for allocating a new keys if necessary */
395 static void
locate_cache(svn_cache__t ** cache,const char ** key,svn_fs_root_t * root,const char * path,apr_pool_t * pool)396 locate_cache(svn_cache__t **cache,
397 const char **key,
398 svn_fs_root_t *root,
399 const char *path,
400 apr_pool_t *pool)
401 {
402 if (root->is_txn_root)
403 {
404 fs_txn_root_data_t *frd = root->fsap_data;
405
406 if (cache)
407 *cache = frd->txn_node_cache;
408 if (key && path)
409 *key = path;
410 }
411 else
412 {
413 fs_fs_data_t *ffd = root->fs->fsap_data;
414
415 if (cache)
416 *cache = ffd->rev_node_cache;
417 if (key && path)
418 *key = svn_fs_fs__combine_number_and_string(root->rev, path, pool);
419 }
420 }
421
422 /* In *NODE_P, return the DAG node for PATH from ROOT's node cache, or NULL
423 if the node isn't cached. *NODE_P is allocated in POOL. */
424 static svn_error_t *
dag_node_cache_get(dag_node_t ** node_p,svn_fs_root_t * root,const char * path,apr_pool_t * pool)425 dag_node_cache_get(dag_node_t **node_p,
426 svn_fs_root_t *root,
427 const char *path,
428 apr_pool_t *pool)
429 {
430 svn_boolean_t found;
431 dag_node_t *node = NULL;
432 svn_cache__t *cache;
433 const char *key;
434
435 SVN_ERR_ASSERT(*path == '/');
436
437 if (!root->is_txn_root)
438 {
439 /* immutable DAG node. use the global caches for it */
440
441 fs_fs_data_t *ffd = root->fs->fsap_data;
442
443 node = cache_lookup(ffd->dag_node_cache, root->rev, path);
444 if (node == NULL)
445 {
446 locate_cache(&cache, &key, root, path, pool);
447 SVN_ERR(svn_cache__get((void **)&node, &found, cache, key, pool));
448 if (found && node)
449 {
450 /* Patch up the FS, since this might have come from an old FS
451 * object. */
452 svn_fs_fs__dag_set_fs(node, root->fs);
453
454 /* Retain the DAG node in L1 cache. */
455 cache_insert(ffd->dag_node_cache, root->rev, path, node);
456 }
457 }
458 else
459 {
460 /* Copy the node from L1 cache into the passed-in POOL. */
461 node = svn_fs_fs__dag_dup(node, pool);
462 }
463 }
464 else
465 {
466 /* DAG is mutable / may become invalid. Use the TXN-local cache */
467
468 locate_cache(&cache, &key, root, path, pool);
469
470 SVN_ERR(svn_cache__get((void **) &node, &found, cache, key, pool));
471 if (found && node)
472 {
473 /* Patch up the FS, since this might have come from an old FS
474 * object. */
475 svn_fs_fs__dag_set_fs(node, root->fs);
476 }
477 }
478
479 *node_p = node;
480
481 return SVN_NO_ERROR;
482 }
483
484
485 /* Add the NODE for PATH to ROOT's node cache. */
486 static svn_error_t *
dag_node_cache_set(svn_fs_root_t * root,const char * path,dag_node_t * node,apr_pool_t * pool)487 dag_node_cache_set(svn_fs_root_t *root,
488 const char *path,
489 dag_node_t *node,
490 apr_pool_t *pool)
491 {
492 svn_cache__t *cache;
493 const char *key;
494
495 SVN_ERR_ASSERT(*path == '/');
496
497 locate_cache(&cache, &key, root, path, pool);
498 return svn_cache__set(cache, key, node, pool);
499 }
500
501
502 /* Baton for find_descendants_in_cache. */
503 struct fdic_baton {
504 const char *path;
505 apr_array_header_t *list;
506 apr_pool_t *pool;
507 };
508
509 /* If the given item is a descendant of BATON->PATH, push
510 * it onto BATON->LIST (copying into BATON->POOL). Implements
511 * the svn_iter_apr_hash_cb_t prototype. */
512 static svn_error_t *
find_descendants_in_cache(void * baton,const void * key,apr_ssize_t klen,void * val,apr_pool_t * pool)513 find_descendants_in_cache(void *baton,
514 const void *key,
515 apr_ssize_t klen,
516 void *val,
517 apr_pool_t *pool)
518 {
519 struct fdic_baton *b = baton;
520 const char *item_path = key;
521
522 if (svn_fspath__skip_ancestor(b->path, item_path))
523 APR_ARRAY_PUSH(b->list, const char *) = apr_pstrdup(b->pool, item_path);
524
525 return SVN_NO_ERROR;
526 }
527
528 /* Invalidate cache entries for PATH and any of its children. This
529 should *only* be called on a transaction root! */
530 static svn_error_t *
dag_node_cache_invalidate(svn_fs_root_t * root,const char * path,apr_pool_t * pool)531 dag_node_cache_invalidate(svn_fs_root_t *root,
532 const char *path,
533 apr_pool_t *pool)
534 {
535 struct fdic_baton b;
536 svn_cache__t *cache;
537 apr_pool_t *iterpool;
538 int i;
539
540 b.path = path;
541 b.pool = svn_pool_create(pool);
542 b.list = apr_array_make(b.pool, 1, sizeof(const char *));
543
544 SVN_ERR_ASSERT(root->is_txn_root);
545 locate_cache(&cache, NULL, root, NULL, b.pool);
546
547
548 SVN_ERR(svn_cache__iter(NULL, cache, find_descendants_in_cache,
549 &b, b.pool));
550
551 iterpool = svn_pool_create(b.pool);
552
553 for (i = 0; i < b.list->nelts; i++)
554 {
555 const char *descendant = APR_ARRAY_IDX(b.list, i, const char *);
556 svn_pool_clear(iterpool);
557 SVN_ERR(svn_cache__set(cache, descendant, NULL, iterpool));
558 }
559
560 svn_pool_destroy(iterpool);
561 svn_pool_destroy(b.pool);
562 return SVN_NO_ERROR;
563 }
564
565
566
567 /* Creating transaction and revision root nodes. */
568
569 svn_error_t *
svn_fs_fs__txn_root(svn_fs_root_t ** root_p,svn_fs_txn_t * txn,apr_pool_t * pool)570 svn_fs_fs__txn_root(svn_fs_root_t **root_p,
571 svn_fs_txn_t *txn,
572 apr_pool_t *pool)
573 {
574 apr_uint32_t flags = 0;
575 apr_hash_t *txnprops;
576
577 /* Look for the temporary txn props representing 'flags'. */
578 SVN_ERR(svn_fs_fs__txn_proplist(&txnprops, txn, pool));
579 if (txnprops)
580 {
581 if (svn_hash_gets(txnprops, SVN_FS__PROP_TXN_CHECK_OOD))
582 flags |= SVN_FS_TXN_CHECK_OOD;
583
584 if (svn_hash_gets(txnprops, SVN_FS__PROP_TXN_CHECK_LOCKS))
585 flags |= SVN_FS_TXN_CHECK_LOCKS;
586 }
587
588 return make_txn_root(root_p, txn->fs, svn_fs_fs__txn_get_id(txn),
589 txn->base_rev, flags, pool);
590 }
591
592
593 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)594 svn_fs_fs__revision_root(svn_fs_root_t **root_p,
595 svn_fs_t *fs,
596 svn_revnum_t rev,
597 apr_pool_t *pool)
598 {
599 dag_node_t *root_dir;
600
601 SVN_ERR(svn_fs__check_fs(fs, TRUE));
602
603 SVN_ERR(svn_fs_fs__dag_revision_root(&root_dir, fs, rev, pool));
604
605 *root_p = make_revision_root(fs, rev, root_dir, pool);
606
607 return SVN_NO_ERROR;
608 }
609
610
611
612 /* Getting dag nodes for roots. */
613
614 /* Return the transaction ID to a given transaction ROOT. */
615 static const svn_fs_fs__id_part_t *
root_txn_id(svn_fs_root_t * root)616 root_txn_id(svn_fs_root_t *root)
617 {
618 fs_txn_root_data_t *frd = root->fsap_data;
619 assert(root->is_txn_root);
620
621 return &frd->txn_id;
622 }
623
624 /* Set *NODE_P to a freshly opened dag node referring to the root
625 directory of ROOT, allocating from POOL. */
626 static svn_error_t *
root_node(dag_node_t ** node_p,svn_fs_root_t * root,apr_pool_t * pool)627 root_node(dag_node_t **node_p,
628 svn_fs_root_t *root,
629 apr_pool_t *pool)
630 {
631 if (root->is_txn_root)
632 {
633 /* It's a transaction root. Open a fresh copy. */
634 return svn_fs_fs__dag_txn_root(node_p, root->fs, root_txn_id(root),
635 pool);
636 }
637 else
638 {
639 /* It's a revision root, so we already have its root directory
640 opened. */
641 dag_node_t *root_dir = root->fsap_data;
642 *node_p = svn_fs_fs__dag_dup(root_dir, pool);
643 return SVN_NO_ERROR;
644 }
645 }
646
647
648 /* Set *NODE_P to a mutable root directory for ROOT, cloning if
649 necessary, allocating in POOL. ROOT must be a transaction root.
650 Use ERROR_PATH in error messages. */
651 static svn_error_t *
mutable_root_node(dag_node_t ** node_p,svn_fs_root_t * root,const char * error_path,apr_pool_t * pool)652 mutable_root_node(dag_node_t **node_p,
653 svn_fs_root_t *root,
654 const char *error_path,
655 apr_pool_t *pool)
656 {
657 if (root->is_txn_root)
658 {
659 /* It's a transaction root. Open a fresh copy. */
660 return svn_fs_fs__dag_clone_root(node_p, root->fs, root_txn_id(root),
661 pool);
662 }
663 else
664 /* If it's not a transaction root, we can't change its contents. */
665 return SVN_FS__ERR_NOT_MUTABLE(root->fs, root->rev, error_path);
666 }
667
668
669
670 /* Traversing directory paths. */
671
672 typedef enum copy_id_inherit_t
673 {
674 copy_id_inherit_unknown = 0,
675 copy_id_inherit_self,
676 copy_id_inherit_parent,
677 copy_id_inherit_new
678
679 } copy_id_inherit_t;
680
681 /* A linked list representing the path from a node up to a root
682 directory. We use this for cloning, and for operations that need
683 to deal with both a node and its parent directory. For example, a
684 `delete' operation needs to know that the node actually exists, but
685 also needs to change the parent directory. */
686 typedef struct parent_path_t
687 {
688
689 /* A node along the path. This could be the final node, one of its
690 parents, or the root. Every parent path ends with an element for
691 the root directory. */
692 dag_node_t *node;
693
694 /* The name NODE has in its parent directory. This is zero for the
695 root directory, which (obviously) has no name in its parent. */
696 char *entry;
697
698 /* The parent of NODE, or zero if NODE is the root directory. */
699 struct parent_path_t *parent;
700
701 /* The copy ID inheritance style. */
702 copy_id_inherit_t copy_inherit;
703
704 /* If copy ID inheritance style is copy_id_inherit_new, this is the
705 path which should be implicitly copied; otherwise, this is NULL. */
706 const char *copy_src_path;
707
708 } parent_path_t;
709
710 /* Return a text string describing the absolute path of parent_path
711 PARENT_PATH. It will be allocated in POOL. */
712 static const char *
parent_path_path(parent_path_t * parent_path,apr_pool_t * pool)713 parent_path_path(parent_path_t *parent_path,
714 apr_pool_t *pool)
715 {
716 const char *path_so_far = "/";
717 if (parent_path->parent)
718 path_so_far = parent_path_path(parent_path->parent, pool);
719 return parent_path->entry
720 ? svn_fspath__join(path_so_far, parent_path->entry, pool)
721 : path_so_far;
722 }
723
724
725 /* Return the FS path for the parent path chain object CHILD relative
726 to its ANCESTOR in the same chain, allocated in POOL. */
727 static const char *
parent_path_relpath(parent_path_t * child,parent_path_t * ancestor,apr_pool_t * pool)728 parent_path_relpath(parent_path_t *child,
729 parent_path_t *ancestor,
730 apr_pool_t *pool)
731 {
732 const char *path_so_far = "";
733 parent_path_t *this_node = child;
734 while (this_node != ancestor)
735 {
736 assert(this_node != NULL);
737 path_so_far = svn_relpath_join(this_node->entry, path_so_far, pool);
738 this_node = this_node->parent;
739 }
740 return path_so_far;
741 }
742
743
744
745 /* Choose a copy ID inheritance method *INHERIT_P to be used in the
746 event that immutable node CHILD in FS needs to be made mutable. If
747 the inheritance method is copy_id_inherit_new, also return a
748 *COPY_SRC_PATH on which to base the new copy ID (else return NULL
749 for that path). CHILD must have a parent (it cannot be the root
750 node). Allocations are taken from POOL. */
751 static svn_error_t *
get_copy_inheritance(copy_id_inherit_t * inherit_p,const char ** copy_src_path,svn_fs_t * fs,parent_path_t * child,apr_pool_t * pool)752 get_copy_inheritance(copy_id_inherit_t *inherit_p,
753 const char **copy_src_path,
754 svn_fs_t *fs,
755 parent_path_t *child,
756 apr_pool_t *pool)
757 {
758 const svn_fs_id_t *child_id, *parent_id, *copyroot_id;
759 const svn_fs_fs__id_part_t *child_copy_id, *parent_copy_id;
760 const char *id_path = NULL;
761 svn_fs_root_t *copyroot_root;
762 dag_node_t *copyroot_node;
763 svn_revnum_t copyroot_rev;
764 const char *copyroot_path;
765
766 SVN_ERR_ASSERT(child && child->parent);
767
768 /* Initialize some convenience variables. */
769 child_id = svn_fs_fs__dag_get_id(child->node);
770 parent_id = svn_fs_fs__dag_get_id(child->parent->node);
771 child_copy_id = svn_fs_fs__id_copy_id(child_id);
772 parent_copy_id = svn_fs_fs__id_copy_id(parent_id);
773
774 /* If this child is already mutable, we have nothing to do. */
775 if (svn_fs_fs__id_is_txn(child_id))
776 {
777 *inherit_p = copy_id_inherit_self;
778 *copy_src_path = NULL;
779 return SVN_NO_ERROR;
780 }
781
782 /* From this point on, we'll assume that the child will just take
783 its copy ID from its parent. */
784 *inherit_p = copy_id_inherit_parent;
785 *copy_src_path = NULL;
786
787 /* Special case: if the child's copy ID is '0', use the parent's
788 copy ID. */
789 if (svn_fs_fs__id_part_is_root(child_copy_id))
790 return SVN_NO_ERROR;
791
792 /* Compare the copy IDs of the child and its parent. If they are
793 the same, then the child is already on the same branch as the
794 parent, and should use the same mutability copy ID that the
795 parent will use. */
796 if (svn_fs_fs__id_part_eq(child_copy_id, parent_copy_id))
797 return SVN_NO_ERROR;
798
799 /* If the child is on the same branch that the parent is on, the
800 child should just use the same copy ID that the parent would use.
801 Else, the child needs to generate a new copy ID to use should it
802 need to be made mutable. We will claim that child is on the same
803 branch as its parent if the child itself is not a branch point,
804 or if it is a branch point that we are accessing via its original
805 copy destination path. */
806 SVN_ERR(svn_fs_fs__dag_get_copyroot(©root_rev, ©root_path,
807 child->node));
808 SVN_ERR(svn_fs_fs__revision_root(©root_root, fs, copyroot_rev, pool));
809 SVN_ERR(get_dag(©root_node, copyroot_root, copyroot_path, pool));
810 copyroot_id = svn_fs_fs__dag_get_id(copyroot_node);
811
812 if (svn_fs_fs__id_compare(copyroot_id, child_id) == svn_fs_node_unrelated)
813 return SVN_NO_ERROR;
814
815 /* Determine if we are looking at the child via its original path or
816 as a subtree item of a copied tree. */
817 id_path = svn_fs_fs__dag_get_created_path(child->node);
818 if (strcmp(id_path, parent_path_path(child, pool)) == 0)
819 {
820 *inherit_p = copy_id_inherit_self;
821 return SVN_NO_ERROR;
822 }
823
824 /* We are pretty sure that the child node is an unedited nested
825 branched node. When it needs to be made mutable, it should claim
826 a new copy ID. */
827 *inherit_p = copy_id_inherit_new;
828 *copy_src_path = id_path;
829 return SVN_NO_ERROR;
830 }
831
832 /* Allocate a new parent_path_t node from POOL, referring to NODE,
833 ENTRY, PARENT, and COPY_ID. */
834 static parent_path_t *
make_parent_path(dag_node_t * node,char * entry,parent_path_t * parent,apr_pool_t * pool)835 make_parent_path(dag_node_t *node,
836 char *entry,
837 parent_path_t *parent,
838 apr_pool_t *pool)
839 {
840 parent_path_t *parent_path = apr_pcalloc(pool, sizeof(*parent_path));
841 parent_path->node = node;
842 parent_path->entry = entry;
843 parent_path->parent = parent;
844 parent_path->copy_inherit = copy_id_inherit_unknown;
845 parent_path->copy_src_path = NULL;
846 return parent_path;
847 }
848
849
850 /* Flags for open_path. */
851 typedef enum open_path_flags_t {
852
853 /* The last component of the PATH need not exist. (All parent
854 directories must exist, as usual.) If the last component doesn't
855 exist, simply leave the `node' member of the bottom parent_path
856 component zero. */
857 open_path_last_optional = 1,
858
859 /* When this flag is set, don't bother to lookup the DAG node in
860 our caches because we already tried this. Ignoring this flag
861 has no functional impact. */
862 open_path_uncached = 2,
863
864 /* The caller does not care about the parent node chain but only
865 the final DAG node. */
866 open_path_node_only = 4,
867
868 /* The caller wants a NULL path object instead of an error if the
869 path cannot be found. */
870 open_path_allow_null = 8
871 } open_path_flags_t;
872
873 /* Try a short-cut for the open_path() function using the last node accessed.
874 * If that ROOT is that nodes's "created rev" and PATH of PATH_LEN chars is
875 * its "created path", return the node in *NODE_P. Set it to NULL otherwise.
876 *
877 * This function is used to support ra_serf-style access patterns where we
878 * are first asked for path@rev and then for path@c_rev of the same node.
879 * The shortcut works by ignoring the "rev" part of the cache key and then
880 * checking whether we got lucky. Lookup and verification are both quick
881 * plus there are many early outs for common types of mismatch.
882 */
883 static svn_error_t *
try_match_last_node(dag_node_t ** node_p,svn_fs_root_t * root,const char * path,apr_size_t path_len,apr_pool_t * scratch_pool)884 try_match_last_node(dag_node_t **node_p,
885 svn_fs_root_t *root,
886 const char *path,
887 apr_size_t path_len,
888 apr_pool_t *scratch_pool)
889 {
890 fs_fs_data_t *ffd = root->fs->fsap_data;
891
892 /* Optimistic lookup: if the last node returned from the cache applied to
893 the same PATH, return it in NODE. */
894 dag_node_t *node
895 = cache_lookup_last_path(ffd->dag_node_cache, path, path_len);
896
897 /* Did we get a bucket with a committed node? */
898 if (node && !svn_fs_fs__dag_check_mutable(node))
899 {
900 /* Get the path&rev pair at which this node was created.
901 This is repository location for which this node is _known_ to be
902 the right lookup result irrespective of how we found it. */
903 const char *created_path
904 = svn_fs_fs__dag_get_created_path(node);
905 svn_revnum_t revision;
906 SVN_ERR(svn_fs_fs__dag_get_revision(&revision, node, scratch_pool));
907
908 /* Is it an exact match? */
909 if (revision == root->rev && strcmp(created_path, path) == 0)
910 {
911 /* Cache it under its full path@rev access path. */
912 SVN_ERR(dag_node_cache_set(root, path, node, scratch_pool));
913
914 *node_p = node;
915 return SVN_NO_ERROR;
916 }
917 }
918
919 *node_p = NULL;
920 return SVN_NO_ERROR;
921 }
922
923 /* Helper for open_path() that constructs and returns an appropriate
924 SVN_ERR_FS_NOT_DIRECTORY error. */
925 static svn_error_t *
err_not_directory(svn_fs_root_t * root,const char * path,apr_pool_t * scratch_pool)926 err_not_directory(svn_fs_root_t *root,
927 const char *path,
928 apr_pool_t *scratch_pool)
929 {
930 const char *msg;
931
932 msg = root->is_txn_root
933 ? apr_psprintf(scratch_pool,
934 _("Failure opening '%s' in transaction '%s'"),
935 path, root->txn)
936 : apr_psprintf(scratch_pool,
937 _("Failure opening '%s' in revision %ld"),
938 path, root->rev);
939
940 return svn_error_quick_wrap(SVN_FS__ERR_NOT_DIRECTORY(root->fs, path), msg);
941 }
942
943 /* Open the node identified by PATH in ROOT, allocating in POOL. Set
944 *PARENT_PATH_P to a path from the node up to ROOT. The resulting
945 **PARENT_PATH_P value is guaranteed to contain at least one
946 *element, for the root directory. PATH must be in canonical form.
947
948 If resulting *PARENT_PATH_P will eventually be made mutable and
949 modified, or if copy ID inheritance information is otherwise needed,
950 IS_TXN_PATH must be set. If IS_TXN_PATH is FALSE, no copy ID
951 inheritance information will be calculated for the *PARENT_PATH_P chain.
952
953 If FLAGS & open_path_last_optional is zero, return the error
954 SVN_ERR_FS_NOT_FOUND if the node PATH refers to does not exist. If
955 non-zero, require all the parent directories to exist as normal,
956 but if the final path component doesn't exist, simply return a path
957 whose bottom `node' member is zero. This option is useful for
958 callers that create new nodes --- we find the parent directory for
959 them, and tell them whether the entry exists already.
960
961 The remaining bits in FLAGS are hints that allow this function
962 to take shortcuts based on knowledge that the caller provides,
963 such as the caller is not actually being interested in PARENT_PATH_P,
964 but only in (*PARENT_PATH_P)->NODE.
965
966 NOTE: Public interfaces which only *read* from the filesystem
967 should not call this function directly, but should instead use
968 get_dag().
969 */
970 static svn_error_t *
open_path(parent_path_t ** parent_path_p,svn_fs_root_t * root,const char * path,int flags,svn_boolean_t is_txn_path,apr_pool_t * pool)971 open_path(parent_path_t **parent_path_p,
972 svn_fs_root_t *root,
973 const char *path,
974 int flags,
975 svn_boolean_t is_txn_path,
976 apr_pool_t *pool)
977 {
978 svn_fs_t *fs = root->fs;
979 dag_node_t *here = NULL; /* The directory we're currently looking at. */
980 parent_path_t *parent_path; /* The path from HERE up to the root. */
981 const char *rest = NULL; /* The portion of PATH we haven't traversed yet. */
982 apr_pool_t *iterpool = svn_pool_create(pool);
983
984 /* path to the currently processed entry without trailing '/'.
985 We will reuse this across iterations by simply putting a NUL terminator
986 at the respective position and replacing that with a '/' in the next
987 iteration. This is correct as we assert() PATH to be canonical. */
988 svn_stringbuf_t *path_so_far = svn_stringbuf_create(path, pool);
989 apr_size_t path_len = path_so_far->len;
990
991 /* Callers often traverse the DAG in some path-based order or along the
992 history segments. That allows us to try a few guesses about where to
993 find the next item. This is only useful if the caller didn't request
994 the full parent chain. */
995 assert(svn_fs__is_canonical_abspath(path));
996 path_so_far->len = 0; /* "" */
997 if (flags & open_path_node_only)
998 {
999 const char *directory;
1000
1001 /* First attempt: Assume that we access the DAG for the same path as
1002 in the last lookup but for a different revision that happens to be
1003 the last revision that touched the respective node. This is a
1004 common pattern when e.g. checking out over ra_serf. Note that this
1005 will only work for committed data as the revision info for nodes in
1006 txns is bogus.
1007
1008 This shortcut is quick and will exit this function upon success.
1009 So, try it first. */
1010 if (!root->is_txn_root)
1011 {
1012 dag_node_t *node;
1013 SVN_ERR(try_match_last_node(&node, root, path, path_len, iterpool));
1014
1015 /* Did the shortcut work? */
1016 if (node)
1017 {
1018 /* Construct and return the result. */
1019 svn_pool_destroy(iterpool);
1020
1021 parent_path = make_parent_path(node, 0, 0, pool);
1022 parent_path->copy_inherit = copy_id_inherit_self;
1023 *parent_path_p = parent_path;
1024
1025 return SVN_NO_ERROR;
1026 }
1027 }
1028
1029 /* Second attempt: Try starting the lookup immediately at the parent
1030 node. We will often have recently accessed either a sibling or
1031 said parent DIRECTORY itself for the same revision. */
1032 directory = svn_dirent_dirname(path, pool);
1033 if (directory[1] != 0) /* root nodes are covered anyway */
1034 {
1035 SVN_ERR(dag_node_cache_get(&here, root, directory, pool));
1036
1037 /* Did the shortcut work? */
1038 if (here && svn_fs_fs__dag_node_kind(here) == svn_node_dir)
1039 {
1040 apr_size_t dirname_len = strlen(directory);
1041 path_so_far->len = dirname_len;
1042 rest = path + dirname_len + 1;
1043 }
1044 else if (here)
1045 {
1046 /* The parent node is not a directory. We are looking for some
1047 sub-path, so that sub-path will not exist. That will be o.k.
1048 if we are just here to check for the path's existence, but
1049 should result in an error otherwise. */
1050 if (flags & open_path_allow_null)
1051 {
1052 *parent_path_p = NULL;
1053 return SVN_NO_ERROR;
1054 }
1055 else
1056 return svn_error_trace(err_not_directory(root, directory, pool));
1057 }
1058 }
1059 }
1060
1061 /* did the shortcut work? */
1062 if (!here)
1063 {
1064 /* Make a parent_path item for the root node, using its own current
1065 copy id. */
1066 SVN_ERR(root_node(&here, root, pool));
1067 rest = path + 1; /* skip the leading '/', it saves in iteration */
1068 }
1069
1070 path_so_far->data[path_so_far->len] = '\0';
1071 parent_path = make_parent_path(here, 0, 0, pool);
1072 parent_path->copy_inherit = copy_id_inherit_self;
1073
1074 /* Whenever we are at the top of this loop:
1075 - HERE is our current directory,
1076 - ID is the node revision ID of HERE,
1077 - REST is the path we're going to find in HERE, and
1078 - PARENT_PATH includes HERE and all its parents. */
1079 for (;;)
1080 {
1081 const char *next;
1082 char *entry;
1083 dag_node_t *child;
1084
1085 svn_pool_clear(iterpool);
1086
1087 /* Parse out the next entry from the path. */
1088 entry = svn_fs__next_entry_name(&next, rest, pool);
1089
1090 /* Update the path traversed thus far. */
1091 path_so_far->data[path_so_far->len] = '/';
1092 path_so_far->len += strlen(entry) + 1;
1093 path_so_far->data[path_so_far->len] = '\0';
1094
1095 if (*entry == '\0')
1096 {
1097 /* Given the behavior of svn_fs__next_entry_name(), this
1098 happens when the path either starts or ends with a slash.
1099 In either case, we stay put: the current directory stays
1100 the same, and we add nothing to the parent path. */
1101 child = here;
1102 }
1103 else
1104 {
1105 copy_id_inherit_t inherit;
1106 const char *copy_path = NULL;
1107 dag_node_t *cached_node = NULL;
1108
1109 /* If we found a directory entry, follow it. First, we
1110 check our node cache, and, failing that, we hit the DAG
1111 layer. Don't bother to contact the cache for the last
1112 element if we already know the lookup to fail for the
1113 complete path. */
1114 if (next || !(flags & open_path_uncached))
1115 SVN_ERR(dag_node_cache_get(&cached_node, root, path_so_far->data,
1116 pool));
1117 if (cached_node)
1118 child = cached_node;
1119 else
1120 SVN_ERR(svn_fs_fs__dag_open(&child, here, entry, pool, iterpool));
1121
1122 /* "file not found" requires special handling. */
1123 if (child == NULL)
1124 {
1125 /* If this was the last path component, and the caller
1126 said it was optional, then don't return an error;
1127 just put a NULL node pointer in the path. */
1128
1129 if ((flags & open_path_last_optional)
1130 && (! next || *next == '\0'))
1131 {
1132 parent_path = make_parent_path(NULL, entry, parent_path,
1133 pool);
1134 break;
1135 }
1136 else if (flags & open_path_allow_null)
1137 {
1138 parent_path = NULL;
1139 break;
1140 }
1141 else
1142 {
1143 /* Build a better error message than svn_fs_fs__dag_open
1144 can provide, giving the root and full path name. */
1145 return SVN_FS__NOT_FOUND(root, path);
1146 }
1147 }
1148
1149 if (flags & open_path_node_only)
1150 {
1151 /* Shortcut: the caller only wants the final DAG node. */
1152 parent_path->node = child;
1153 }
1154 else
1155 {
1156 /* Now, make a parent_path item for CHILD. */
1157 parent_path = make_parent_path(child, entry, parent_path, pool);
1158 if (is_txn_path)
1159 {
1160 SVN_ERR(get_copy_inheritance(&inherit, ©_path, fs,
1161 parent_path, iterpool));
1162 parent_path->copy_inherit = inherit;
1163 parent_path->copy_src_path = apr_pstrdup(pool, copy_path);
1164 }
1165 }
1166
1167 /* Cache the node we found (if it wasn't already cached). */
1168 if (! cached_node)
1169 SVN_ERR(dag_node_cache_set(root, path_so_far->data, child,
1170 iterpool));
1171 }
1172
1173 /* Are we finished traversing the path? */
1174 if (! next)
1175 break;
1176
1177 /* The path isn't finished yet; we'd better be in a directory. */
1178 if (svn_fs_fs__dag_node_kind(child) != svn_node_dir)
1179 {
1180 /* Since this is not a directory and we are looking for some
1181 sub-path, that sub-path will not exist. That will be o.k.,
1182 if we are just here to check for the path's existence. */
1183 if (flags & open_path_allow_null)
1184 {
1185 parent_path = NULL;
1186 break;
1187 }
1188
1189 /* It's really a problem ... */
1190 return svn_error_trace(
1191 err_not_directory(root, path_so_far->data, iterpool));
1192 }
1193
1194 rest = next;
1195 here = child;
1196 }
1197
1198 svn_pool_destroy(iterpool);
1199 *parent_path_p = parent_path;
1200 return SVN_NO_ERROR;
1201 }
1202
1203
1204 /* Make the node referred to by PARENT_PATH mutable, if it isn't
1205 already, allocating from POOL. ROOT must be the root from which
1206 PARENT_PATH descends. Clone any parent directories as needed.
1207 Adjust the dag nodes in PARENT_PATH to refer to the clones. Use
1208 ERROR_PATH in error messages. */
1209 static svn_error_t *
make_path_mutable(svn_fs_root_t * root,parent_path_t * parent_path,const char * error_path,apr_pool_t * pool)1210 make_path_mutable(svn_fs_root_t *root,
1211 parent_path_t *parent_path,
1212 const char *error_path,
1213 apr_pool_t *pool)
1214 {
1215 dag_node_t *clone;
1216 const svn_fs_fs__id_part_t *txn_id = root_txn_id(root);
1217
1218 /* Is the node mutable already? */
1219 if (svn_fs_fs__dag_check_mutable(parent_path->node))
1220 return SVN_NO_ERROR;
1221
1222 /* Are we trying to clone the root, or somebody's child node? */
1223 if (parent_path->parent)
1224 {
1225 const svn_fs_id_t *parent_id, *child_id, *copyroot_id;
1226 svn_fs_fs__id_part_t copy_id = { SVN_INVALID_REVNUM, 0 };
1227 svn_fs_fs__id_part_t *copy_id_ptr = ©_id;
1228 copy_id_inherit_t inherit = parent_path->copy_inherit;
1229 const char *clone_path, *copyroot_path;
1230 svn_revnum_t copyroot_rev;
1231 svn_boolean_t is_parent_copyroot = FALSE;
1232 svn_fs_root_t *copyroot_root;
1233 dag_node_t *copyroot_node;
1234
1235 /* We're trying to clone somebody's child. Make sure our parent
1236 is mutable. */
1237 SVN_ERR(make_path_mutable(root, parent_path->parent,
1238 error_path, pool));
1239
1240 switch (inherit)
1241 {
1242 case copy_id_inherit_parent:
1243 parent_id = svn_fs_fs__dag_get_id(parent_path->parent->node);
1244 copy_id = *svn_fs_fs__id_copy_id(parent_id);
1245 break;
1246
1247 case copy_id_inherit_new:
1248 SVN_ERR(svn_fs_fs__reserve_copy_id(©_id, root->fs, txn_id,
1249 pool));
1250 break;
1251
1252 case copy_id_inherit_self:
1253 copy_id_ptr = NULL;
1254 break;
1255
1256 case copy_id_inherit_unknown:
1257 default:
1258 SVN_ERR_MALFUNCTION(); /* uh-oh -- somebody didn't calculate copy-ID
1259 inheritance data. */
1260 }
1261
1262 /* Determine what copyroot our new child node should use. */
1263 SVN_ERR(svn_fs_fs__dag_get_copyroot(©root_rev, ©root_path,
1264 parent_path->node));
1265 SVN_ERR(svn_fs_fs__revision_root(©root_root, root->fs,
1266 copyroot_rev, pool));
1267 SVN_ERR(get_dag(©root_node, copyroot_root, copyroot_path, pool));
1268
1269 child_id = svn_fs_fs__dag_get_id(parent_path->node);
1270 copyroot_id = svn_fs_fs__dag_get_id(copyroot_node);
1271 if (!svn_fs_fs__id_part_eq(svn_fs_fs__id_node_id(child_id),
1272 svn_fs_fs__id_node_id(copyroot_id)))
1273 is_parent_copyroot = TRUE;
1274
1275 /* Now make this node mutable. */
1276 clone_path = parent_path_path(parent_path->parent, pool);
1277 SVN_ERR(svn_fs_fs__dag_clone_child(&clone,
1278 parent_path->parent->node,
1279 clone_path,
1280 parent_path->entry,
1281 copy_id_ptr, txn_id,
1282 is_parent_copyroot,
1283 pool));
1284
1285 /* Update the path cache. */
1286 SVN_ERR(dag_node_cache_set(root, parent_path_path(parent_path, pool),
1287 clone, pool));
1288 }
1289 else
1290 {
1291 /* We're trying to clone the root directory. */
1292 SVN_ERR(mutable_root_node(&clone, root, error_path, pool));
1293 }
1294
1295 /* Update the PARENT_PATH link to refer to the clone. */
1296 parent_path->node = clone;
1297
1298 return SVN_NO_ERROR;
1299 }
1300
1301
1302 /* Open the node identified by PATH in ROOT. Set DAG_NODE_P to the
1303 node we find, allocated in POOL. Return the error
1304 SVN_ERR_FS_NOT_FOUND if this node doesn't exist. */
1305 static svn_error_t *
get_dag(dag_node_t ** dag_node_p,svn_fs_root_t * root,const char * path,apr_pool_t * pool)1306 get_dag(dag_node_t **dag_node_p,
1307 svn_fs_root_t *root,
1308 const char *path,
1309 apr_pool_t *pool)
1310 {
1311 parent_path_t *parent_path;
1312 dag_node_t *node = NULL;
1313
1314 /* First we look for the DAG in our cache
1315 (if the path may be canonical). */
1316 if (*path == '/')
1317 SVN_ERR(dag_node_cache_get(&node, root, path, pool));
1318
1319 if (! node)
1320 {
1321 /* Canonicalize the input PATH. As it turns out, >95% of all paths
1322 * seen here during e.g. svnadmin verify are non-canonical, i.e.
1323 * miss the leading '/'. Check for those quickly.
1324 *
1325 * For normalized paths, it is much faster to check the path than
1326 * to attempt a second cache lookup (which would fail). */
1327 if (*path != '/' || !svn_fs__is_canonical_abspath(path))
1328 {
1329 path = svn_fs__canonicalize_abspath(path, pool);
1330 SVN_ERR(dag_node_cache_get(&node, root, path, pool));
1331 }
1332
1333 if (! node)
1334 {
1335 /* Call open_path with no flags, as we want this to return an
1336 * error if the node for which we are searching doesn't exist. */
1337 SVN_ERR(open_path(&parent_path, root, path,
1338 open_path_uncached | open_path_node_only,
1339 FALSE, pool));
1340 node = parent_path->node;
1341
1342 /* No need to cache our find -- open_path() will do that for us. */
1343 }
1344 }
1345
1346 *dag_node_p = node;
1347 return SVN_NO_ERROR;
1348 }
1349
1350
1351
1352 /* Populating the `changes' table. */
1353
1354 /* Add a change to the changes table in FS, keyed on transaction id
1355 TXN_ID, and indicated that a change of kind CHANGE_KIND occurred on
1356 PATH (whose node revision id is--or was, in the case of a
1357 deletion--NODEREV_ID), and optionally that TEXT_MODs, PROP_MODs or
1358 MERGEINFO_MODs occurred. If the change resulted from a copy,
1359 COPYFROM_REV and COPYFROM_PATH specify under which revision and path
1360 the node was copied from. If this was not part of a copy, COPYFROM_REV
1361 should be SVN_INVALID_REVNUM. Do all this as part of POOL. */
1362 static svn_error_t *
add_change(svn_fs_t * fs,const svn_fs_fs__id_part_t * txn_id,const char * path,const svn_fs_id_t * noderev_id,svn_fs_path_change_kind_t change_kind,svn_boolean_t text_mod,svn_boolean_t prop_mod,svn_boolean_t mergeinfo_mod,svn_node_kind_t node_kind,svn_revnum_t copyfrom_rev,const char * copyfrom_path,apr_pool_t * pool)1363 add_change(svn_fs_t *fs,
1364 const svn_fs_fs__id_part_t *txn_id,
1365 const char *path,
1366 const svn_fs_id_t *noderev_id,
1367 svn_fs_path_change_kind_t change_kind,
1368 svn_boolean_t text_mod,
1369 svn_boolean_t prop_mod,
1370 svn_boolean_t mergeinfo_mod,
1371 svn_node_kind_t node_kind,
1372 svn_revnum_t copyfrom_rev,
1373 const char *copyfrom_path,
1374 apr_pool_t *pool)
1375 {
1376 return svn_fs_fs__add_change(fs, txn_id,
1377 svn_fs__canonicalize_abspath(path, pool),
1378 noderev_id, change_kind,
1379 text_mod, prop_mod, mergeinfo_mod,
1380 node_kind, copyfrom_rev, copyfrom_path,
1381 pool);
1382 }
1383
1384
1385
1386 /* Generic node operations. */
1387
1388 /* Get the id of a node referenced by path PATH in ROOT. Return the
1389 id in *ID_P allocated in POOL. */
1390 svn_error_t *
svn_fs_fs__node_id(const svn_fs_id_t ** id_p,svn_fs_root_t * root,const char * path,apr_pool_t * pool)1391 svn_fs_fs__node_id(const svn_fs_id_t **id_p,
1392 svn_fs_root_t *root,
1393 const char *path,
1394 apr_pool_t *pool)
1395 {
1396 if ((! root->is_txn_root)
1397 && (path[0] == '\0' || ((path[0] == '/') && (path[1] == '\0'))))
1398 {
1399 /* Optimize the case where we don't need any db access at all.
1400 The root directory ("" or "/") node is stored in the
1401 svn_fs_root_t object, and never changes when it's a revision
1402 root, so we can just reach in and grab it directly. */
1403 dag_node_t *root_dir = root->fsap_data;
1404 *id_p = svn_fs_fs__id_copy(svn_fs_fs__dag_get_id(root_dir), pool);
1405 }
1406 else
1407 {
1408 dag_node_t *node;
1409
1410 SVN_ERR(get_dag(&node, root, path, pool));
1411 *id_p = svn_fs_fs__id_copy(svn_fs_fs__dag_get_id(node), pool);
1412 }
1413 return SVN_NO_ERROR;
1414 }
1415
1416 static svn_error_t *
fs_node_relation(svn_fs_node_relation_t * relation,svn_fs_root_t * root_a,const char * path_a,svn_fs_root_t * root_b,const char * path_b,apr_pool_t * pool)1417 fs_node_relation(svn_fs_node_relation_t *relation,
1418 svn_fs_root_t *root_a, const char *path_a,
1419 svn_fs_root_t *root_b, const char *path_b,
1420 apr_pool_t *pool)
1421 {
1422 dag_node_t *node;
1423 const svn_fs_id_t *id_a, *id_b;
1424 svn_fs_fs__id_part_t node_id_a, node_id_b;
1425
1426 /* Root paths are a common special case. */
1427 svn_boolean_t a_is_root_dir
1428 = (path_a[0] == '\0') || ((path_a[0] == '/') && (path_a[1] == '\0'));
1429 svn_boolean_t b_is_root_dir
1430 = (path_b[0] == '\0') || ((path_b[0] == '/') && (path_b[1] == '\0'));
1431
1432 /* Another useful thing to know: Both are txns but not the same txn. */
1433 svn_boolean_t different_txn
1434 = root_a->is_txn_root && root_b->is_txn_root
1435 && strcmp(root_a->txn, root_b->txn);
1436
1437 /* Path from different repository are always unrelated. */
1438 if (root_a->fs != root_b->fs)
1439 {
1440 *relation = svn_fs_node_unrelated;
1441 return SVN_NO_ERROR;
1442 }
1443
1444 /* Are both (!) root paths? Then, they are related and we only test how
1445 * direct the relation is. */
1446 if (a_is_root_dir && b_is_root_dir)
1447 {
1448 /* For txn roots, root->REV is the base revision of that TXN. */
1449 *relation = ( (root_a->rev == root_b->rev)
1450 && (root_a->is_txn_root == root_b->is_txn_root)
1451 && !different_txn)
1452 ? svn_fs_node_unchanged
1453 : svn_fs_node_common_ancestor;
1454 return SVN_NO_ERROR;
1455 }
1456
1457 /* We checked for all separations between ID spaces (repos, txn).
1458 * Now, we can simply test for the ID values themselves. */
1459 SVN_ERR(get_dag(&node, root_a, path_a, pool));
1460 id_a = svn_fs_fs__dag_get_id(node);
1461 node_id_a = *svn_fs_fs__id_node_id(id_a);
1462
1463 SVN_ERR(get_dag(&node, root_b, path_b, pool));
1464 id_b = svn_fs_fs__dag_get_id(node);
1465 node_id_b = *svn_fs_fs__id_node_id(id_b);
1466
1467 /* Noderevs from different nodes are unrelated. */
1468 if (!svn_fs_fs__id_part_eq(&node_id_a, &node_id_b))
1469 {
1470 *relation = svn_fs_node_unrelated;
1471 return SVN_NO_ERROR;
1472 }
1473
1474 /* Noderevs have the same node-ID now. So, they *seem* to be related.
1475 *
1476 * Special case: Different txns may create the same (txn-local) node ID.
1477 * These are not related to each other, nor to any other node ID so far. */
1478 if (different_txn && node_id_a.revision == SVN_INVALID_REVNUM)
1479 {
1480 *relation = svn_fs_node_unrelated;
1481 return SVN_NO_ERROR;
1482 }
1483
1484 /* The noderevs are actually related. Are they the same? */
1485 if (svn_fs_fs__id_eq(id_a, id_b))
1486 *relation = svn_fs_node_unchanged;
1487 else
1488 *relation = svn_fs_node_common_ancestor;
1489
1490 return SVN_NO_ERROR;
1491 }
1492
1493 svn_error_t *
svn_fs_fs__node_created_rev(svn_revnum_t * revision,svn_fs_root_t * root,const char * path,apr_pool_t * pool)1494 svn_fs_fs__node_created_rev(svn_revnum_t *revision,
1495 svn_fs_root_t *root,
1496 const char *path,
1497 apr_pool_t *pool)
1498 {
1499 dag_node_t *node;
1500
1501 SVN_ERR(get_dag(&node, root, path, pool));
1502 return svn_fs_fs__dag_get_revision(revision, node, pool);
1503 }
1504
1505
1506 /* Set *CREATED_PATH to the path at which PATH under ROOT was created.
1507 Return a string allocated in POOL. */
1508 static svn_error_t *
fs_node_created_path(const char ** created_path,svn_fs_root_t * root,const char * path,apr_pool_t * pool)1509 fs_node_created_path(const char **created_path,
1510 svn_fs_root_t *root,
1511 const char *path,
1512 apr_pool_t *pool)
1513 {
1514 dag_node_t *node;
1515
1516 SVN_ERR(get_dag(&node, root, path, pool));
1517 *created_path = svn_fs_fs__dag_get_created_path(node);
1518
1519 return SVN_NO_ERROR;
1520 }
1521
1522 /* Set *KIND_P to the type of node present at PATH under ROOT. If
1523 PATH does not exist under ROOT, set *KIND_P to svn_node_none. Use
1524 POOL for temporary allocation. */
1525 svn_error_t *
svn_fs_fs__check_path(svn_node_kind_t * kind_p,svn_fs_root_t * root,const char * path,apr_pool_t * pool)1526 svn_fs_fs__check_path(svn_node_kind_t *kind_p,
1527 svn_fs_root_t *root,
1528 const char *path,
1529 apr_pool_t *pool)
1530 {
1531 dag_node_t *node;
1532 svn_error_t *err;
1533
1534 err = get_dag(&node, root, path, pool);
1535 if (err &&
1536 ((err->apr_err == SVN_ERR_FS_NOT_FOUND)
1537 || (err->apr_err == SVN_ERR_FS_NOT_DIRECTORY)))
1538 {
1539 svn_error_clear(err);
1540 *kind_p = svn_node_none;
1541 return SVN_NO_ERROR;
1542 }
1543 else if (err)
1544 return svn_error_trace(err);
1545
1546 *kind_p = svn_fs_fs__dag_node_kind(node);
1547 return SVN_NO_ERROR;
1548 }
1549
1550 /* Set *VALUE_P to the value of the property named PROPNAME of PATH in
1551 ROOT. If the node has no property by that name, set *VALUE_P to
1552 zero. Allocate the result in POOL. */
1553 static svn_error_t *
fs_node_prop(svn_string_t ** value_p,svn_fs_root_t * root,const char * path,const char * propname,apr_pool_t * pool)1554 fs_node_prop(svn_string_t **value_p,
1555 svn_fs_root_t *root,
1556 const char *path,
1557 const char *propname,
1558 apr_pool_t *pool)
1559 {
1560 dag_node_t *node;
1561 apr_hash_t *proplist;
1562
1563 SVN_ERR(get_dag(&node, root, path, pool));
1564 SVN_ERR(svn_fs_fs__dag_get_proplist(&proplist, node, pool));
1565 *value_p = NULL;
1566 if (proplist)
1567 *value_p = svn_hash_gets(proplist, propname);
1568
1569 return SVN_NO_ERROR;
1570 }
1571
1572
1573 /* Set *TABLE_P to the entire property list of PATH under ROOT, as an
1574 APR hash table allocated in POOL. The resulting property table
1575 maps property names to pointers to svn_string_t objects containing
1576 the property value. */
1577 static svn_error_t *
fs_node_proplist(apr_hash_t ** table_p,svn_fs_root_t * root,const char * path,apr_pool_t * pool)1578 fs_node_proplist(apr_hash_t **table_p,
1579 svn_fs_root_t *root,
1580 const char *path,
1581 apr_pool_t *pool)
1582 {
1583 apr_hash_t *table;
1584 dag_node_t *node;
1585
1586 SVN_ERR(get_dag(&node, root, path, pool));
1587 SVN_ERR(svn_fs_fs__dag_get_proplist(&table, node, pool));
1588 *table_p = table ? table : apr_hash_make(pool);
1589
1590 return SVN_NO_ERROR;
1591 }
1592
1593 static svn_error_t *
fs_node_has_props(svn_boolean_t * has_props,svn_fs_root_t * root,const char * path,apr_pool_t * scratch_pool)1594 fs_node_has_props(svn_boolean_t *has_props,
1595 svn_fs_root_t *root,
1596 const char *path,
1597 apr_pool_t *scratch_pool)
1598 {
1599 dag_node_t *node;
1600
1601 SVN_ERR(get_dag(&node, root, path, scratch_pool));
1602
1603 return svn_error_trace(svn_fs_fs__dag_has_props(has_props, node,
1604 scratch_pool));
1605 }
1606
1607 static svn_error_t *
increment_mergeinfo_up_tree(parent_path_t * pp,apr_int64_t increment,apr_pool_t * pool)1608 increment_mergeinfo_up_tree(parent_path_t *pp,
1609 apr_int64_t increment,
1610 apr_pool_t *pool)
1611 {
1612 for (; pp; pp = pp->parent)
1613 SVN_ERR(svn_fs_fs__dag_increment_mergeinfo_count(pp->node,
1614 increment,
1615 pool));
1616
1617 return SVN_NO_ERROR;
1618 }
1619
1620 /* Change, add, or delete a node's property value. The affected node
1621 is PATH under ROOT, the property value to modify is NAME, and VALUE
1622 points to either a string value to set the new contents to, or NULL
1623 if the property should be deleted. Perform temporary allocations
1624 in POOL. */
1625 static svn_error_t *
fs_change_node_prop(svn_fs_root_t * root,const char * path,const char * name,const svn_string_t * value,apr_pool_t * pool)1626 fs_change_node_prop(svn_fs_root_t *root,
1627 const char *path,
1628 const char *name,
1629 const svn_string_t *value,
1630 apr_pool_t *pool)
1631 {
1632 parent_path_t *parent_path;
1633 apr_hash_t *proplist;
1634 const svn_fs_fs__id_part_t *txn_id;
1635 svn_boolean_t mergeinfo_mod = FALSE;
1636
1637 if (! root->is_txn_root)
1638 return SVN_FS__NOT_TXN(root);
1639 txn_id = root_txn_id(root);
1640
1641 path = svn_fs__canonicalize_abspath(path, pool);
1642 SVN_ERR(open_path(&parent_path, root, path, 0, TRUE, pool));
1643
1644 /* Check (non-recursively) to see if path is locked; if so, check
1645 that we can use it. */
1646 if (root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
1647 SVN_ERR(svn_fs_fs__allow_locked_operation(path, root->fs, FALSE, FALSE,
1648 pool));
1649
1650 SVN_ERR(make_path_mutable(root, parent_path, path, pool));
1651 SVN_ERR(svn_fs_fs__dag_get_proplist(&proplist, parent_path->node, pool));
1652
1653 /* If there's no proplist, but we're just deleting a property, exit now. */
1654 if ((! proplist) && (! value))
1655 return SVN_NO_ERROR;
1656
1657 /* Now, if there's no proplist, we know we need to make one. */
1658 if (! proplist)
1659 proplist = apr_hash_make(pool);
1660
1661 if (svn_fs_fs__fs_supports_mergeinfo(root->fs)
1662 && strcmp (name, SVN_PROP_MERGEINFO) == 0)
1663 {
1664 apr_int64_t increment = 0;
1665 svn_boolean_t had_mergeinfo;
1666 SVN_ERR(svn_fs_fs__dag_has_mergeinfo(&had_mergeinfo, parent_path->node));
1667
1668 if (value && !had_mergeinfo)
1669 increment = 1;
1670 else if (!value && had_mergeinfo)
1671 increment = -1;
1672
1673 if (increment != 0)
1674 {
1675 SVN_ERR(increment_mergeinfo_up_tree(parent_path, increment, pool));
1676 SVN_ERR(svn_fs_fs__dag_set_has_mergeinfo(parent_path->node,
1677 (value != NULL), pool));
1678 }
1679
1680 mergeinfo_mod = TRUE;
1681 }
1682
1683 /* Set the property. */
1684 svn_hash_sets(proplist, name, value);
1685
1686 /* Overwrite the node's proplist. */
1687 SVN_ERR(svn_fs_fs__dag_set_proplist(parent_path->node, proplist,
1688 pool));
1689
1690 /* Make a record of this modification in the changes table. */
1691 return add_change(root->fs, txn_id, path,
1692 svn_fs_fs__dag_get_id(parent_path->node),
1693 svn_fs_path_change_modify, FALSE, TRUE, mergeinfo_mod,
1694 svn_fs_fs__dag_node_kind(parent_path->node),
1695 SVN_INVALID_REVNUM, NULL, pool);
1696 }
1697
1698
1699 /* Determine if the properties of two path/root combinations are
1700 different. Set *CHANGED_P to TRUE if the properties at PATH1 under
1701 ROOT1 differ from those at PATH2 under ROOT2, or FALSE otherwise.
1702 Both roots must be in the same filesystem. */
1703 static svn_error_t *
fs_props_changed(svn_boolean_t * changed_p,svn_fs_root_t * root1,const char * path1,svn_fs_root_t * root2,const char * path2,svn_boolean_t strict,apr_pool_t * pool)1704 fs_props_changed(svn_boolean_t *changed_p,
1705 svn_fs_root_t *root1,
1706 const char *path1,
1707 svn_fs_root_t *root2,
1708 const char *path2,
1709 svn_boolean_t strict,
1710 apr_pool_t *pool)
1711 {
1712 dag_node_t *node1, *node2;
1713
1714 /* Check that roots are in the same fs. */
1715 if (root1->fs != root2->fs)
1716 return svn_error_create
1717 (SVN_ERR_FS_GENERAL, NULL,
1718 _("Cannot compare property value between two different filesystems"));
1719
1720 SVN_ERR(get_dag(&node1, root1, path1, pool));
1721 SVN_ERR(get_dag(&node2, root2, path2, pool));
1722 return svn_fs_fs__dag_things_different(changed_p, NULL,
1723 node1, node2, strict, pool);
1724 }
1725
1726
1727
1728 /* Merges and commits. */
1729
1730 /* Set *NODE to the root node of ROOT. */
1731 static svn_error_t *
get_root(dag_node_t ** node,svn_fs_root_t * root,apr_pool_t * pool)1732 get_root(dag_node_t **node, svn_fs_root_t *root, apr_pool_t *pool)
1733 {
1734 return get_dag(node, root, "/", pool);
1735 }
1736
1737
1738 /* Set the contents of CONFLICT_PATH to PATH, and return an
1739 SVN_ERR_FS_CONFLICT error that indicates that there was a conflict
1740 at PATH. Perform all allocations in POOL (except the allocation of
1741 CONFLICT_PATH, which should be handled outside this function). */
1742 static svn_error_t *
conflict_err(svn_stringbuf_t * conflict_path,const char * path)1743 conflict_err(svn_stringbuf_t *conflict_path,
1744 const char *path)
1745 {
1746 svn_stringbuf_set(conflict_path, path);
1747 return svn_error_createf(SVN_ERR_FS_CONFLICT, NULL,
1748 _("Conflict at '%s'"), path);
1749 }
1750
1751 /* Compare the directory representations at nodes LHS and RHS and set
1752 * *CHANGED to TRUE, if at least one entry has been added or removed them.
1753 * Use POOL for temporary allocations.
1754 */
1755 static svn_error_t *
compare_dir_structure(svn_boolean_t * changed,dag_node_t * lhs,dag_node_t * rhs,apr_pool_t * pool)1756 compare_dir_structure(svn_boolean_t *changed,
1757 dag_node_t *lhs,
1758 dag_node_t *rhs,
1759 apr_pool_t *pool)
1760 {
1761 apr_array_header_t *lhs_entries;
1762 apr_array_header_t *rhs_entries;
1763 int i;
1764
1765 SVN_ERR(svn_fs_fs__dag_dir_entries(&lhs_entries, lhs, pool));
1766 SVN_ERR(svn_fs_fs__dag_dir_entries(&rhs_entries, rhs, pool));
1767
1768 /* different number of entries -> some addition / removal */
1769 if (lhs_entries->nelts != rhs_entries->nelts)
1770 {
1771 *changed = TRUE;
1772 return SVN_NO_ERROR;
1773 }
1774
1775 /* Since directories are sorted by name, we can simply compare their
1776 entries one-by-one without binary lookup etc. */
1777 for (i = 0; i < lhs_entries->nelts; ++i)
1778 {
1779 svn_fs_dirent_t *lhs_entry
1780 = APR_ARRAY_IDX(lhs_entries, i, svn_fs_dirent_t *);
1781 svn_fs_dirent_t *rhs_entry
1782 = APR_ARRAY_IDX(rhs_entries, i, svn_fs_dirent_t *);
1783
1784 if (strcmp(lhs_entry->name, rhs_entry->name)
1785 || !svn_fs_fs__id_part_eq(svn_fs_fs__id_node_id(lhs_entry->id),
1786 svn_fs_fs__id_node_id(rhs_entry->id))
1787 || !svn_fs_fs__id_part_eq(svn_fs_fs__id_copy_id(lhs_entry->id),
1788 svn_fs_fs__id_copy_id(rhs_entry->id)))
1789 {
1790 *changed = TRUE;
1791 return SVN_NO_ERROR;
1792 }
1793 }
1794
1795 *changed = FALSE;
1796 return SVN_NO_ERROR;
1797 }
1798
1799 /* Merge changes between ANCESTOR and SOURCE into TARGET. ANCESTOR
1800 * and TARGET must be distinct node revisions. TARGET_PATH should
1801 * correspond to TARGET's full path in its filesystem, and is used for
1802 * reporting conflict location.
1803 *
1804 * SOURCE, TARGET, and ANCESTOR are generally directories; this
1805 * function recursively merges the directories' contents. If any are
1806 * files, this function simply returns an error whenever SOURCE,
1807 * TARGET, and ANCESTOR are all distinct node revisions.
1808 *
1809 * If there are differences between ANCESTOR and SOURCE that conflict
1810 * with changes between ANCESTOR and TARGET, this function returns an
1811 * SVN_ERR_FS_CONFLICT error, and updates CONFLICT_P to the name of the
1812 * conflicting node in TARGET, with TARGET_PATH prepended as a path.
1813 *
1814 * If there are no conflicting differences, CONFLICT_P is updated to
1815 * the empty string.
1816 *
1817 * CONFLICT_P must point to a valid svn_stringbuf_t.
1818 *
1819 * Do any necessary temporary allocation in POOL.
1820 */
1821 static svn_error_t *
merge(svn_stringbuf_t * conflict_p,const char * target_path,dag_node_t * target,dag_node_t * source,dag_node_t * ancestor,const svn_fs_fs__id_part_t * txn_id,apr_int64_t * mergeinfo_increment_out,apr_pool_t * pool)1822 merge(svn_stringbuf_t *conflict_p,
1823 const char *target_path,
1824 dag_node_t *target,
1825 dag_node_t *source,
1826 dag_node_t *ancestor,
1827 const svn_fs_fs__id_part_t *txn_id,
1828 apr_int64_t *mergeinfo_increment_out,
1829 apr_pool_t *pool)
1830 {
1831 const svn_fs_id_t *source_id, *target_id, *ancestor_id;
1832 apr_array_header_t *s_entries, *t_entries, *a_entries;
1833 int i, s_idx = -1, t_idx = -1;
1834 svn_fs_t *fs;
1835 apr_pool_t *iterpool;
1836 apr_int64_t mergeinfo_increment = 0;
1837 svn_boolean_t fs_supports_mergeinfo;
1838
1839 /* Make sure everyone comes from the same filesystem. */
1840 fs = svn_fs_fs__dag_get_fs(ancestor);
1841 if ((fs != svn_fs_fs__dag_get_fs(source))
1842 || (fs != svn_fs_fs__dag_get_fs(target)))
1843 {
1844 return svn_error_create
1845 (SVN_ERR_FS_CORRUPT, NULL,
1846 _("Bad merge; ancestor, source, and target not all in same fs"));
1847 }
1848
1849 /* We have the same fs, now check it. */
1850 SVN_ERR(svn_fs__check_fs(fs, TRUE));
1851
1852 source_id = svn_fs_fs__dag_get_id(source);
1853 target_id = svn_fs_fs__dag_get_id(target);
1854 ancestor_id = svn_fs_fs__dag_get_id(ancestor);
1855
1856 /* It's improper to call this function with ancestor == target. */
1857 if (svn_fs_fs__id_eq(ancestor_id, target_id))
1858 {
1859 svn_string_t *id_str = svn_fs_fs__id_unparse(target_id, pool);
1860 return svn_error_createf
1861 (SVN_ERR_FS_GENERAL, NULL,
1862 _("Bad merge; target '%s' has id '%s', same as ancestor"),
1863 target_path, id_str->data);
1864 }
1865
1866 svn_stringbuf_setempty(conflict_p);
1867
1868 /* Base cases:
1869 * Either no change made in source, or same change as made in target.
1870 * Both mean nothing to merge here.
1871 */
1872 if (svn_fs_fs__id_eq(ancestor_id, source_id)
1873 || (svn_fs_fs__id_eq(source_id, target_id)))
1874 return SVN_NO_ERROR;
1875
1876 /* Else proceed, knowing all three are distinct node revisions.
1877 *
1878 * How to merge from this point:
1879 *
1880 * if (not all 3 are directories)
1881 * {
1882 * early exit with conflict;
1883 * }
1884 *
1885 * // Property changes may only be made to up-to-date
1886 * // directories, because once the client commits the prop
1887 * // change, it bumps the directory's revision, and therefore
1888 * // must be able to depend on there being no other changes to
1889 * // that directory in the repository.
1890 * if (target's property list differs from ancestor's)
1891 * conflict;
1892 *
1893 * For each entry NAME in the directory ANCESTOR:
1894 *
1895 * Let ANCESTOR-ENTRY, SOURCE-ENTRY, and TARGET-ENTRY be the IDs of
1896 * the name within ANCESTOR, SOURCE, and TARGET respectively.
1897 * (Possibly null if NAME does not exist in SOURCE or TARGET.)
1898 *
1899 * If ANCESTOR-ENTRY == SOURCE-ENTRY, then:
1900 * No changes were made to this entry while the transaction was in
1901 * progress, so do nothing to the target.
1902 *
1903 * Else if ANCESTOR-ENTRY == TARGET-ENTRY, then:
1904 * A change was made to this entry while the transaction was in
1905 * process, but the transaction did not touch this entry. Replace
1906 * TARGET-ENTRY with SOURCE-ENTRY.
1907 *
1908 * Else:
1909 * Changes were made to this entry both within the transaction and
1910 * to the repository while the transaction was in progress. They
1911 * must be merged or declared to be in conflict.
1912 *
1913 * If SOURCE-ENTRY and TARGET-ENTRY are both null, that's a
1914 * double delete; flag a conflict.
1915 *
1916 * If any of the three entries is of type file, declare a conflict.
1917 *
1918 * If either SOURCE-ENTRY or TARGET-ENTRY is not a direct
1919 * modification of ANCESTOR-ENTRY (determine by comparing the
1920 * node-id fields), declare a conflict. A replacement is
1921 * incompatible with a modification or other replacement--even
1922 * an identical replacement.
1923 *
1924 * Direct modifications were made to the directory ANCESTOR-ENTRY
1925 * in both SOURCE and TARGET. Recursively merge these
1926 * modifications.
1927 *
1928 * For each leftover entry NAME in the directory SOURCE:
1929 *
1930 * If NAME exists in TARGET, declare a conflict. Even if SOURCE and
1931 * TARGET are adding exactly the same thing, two additions are not
1932 * auto-mergeable with each other.
1933 *
1934 * Add NAME to TARGET with the entry from SOURCE.
1935 *
1936 * Now that we are done merging the changes from SOURCE into the
1937 * directory TARGET, update TARGET's predecessor to be SOURCE.
1938 */
1939
1940 if ((svn_fs_fs__dag_node_kind(source) != svn_node_dir)
1941 || (svn_fs_fs__dag_node_kind(target) != svn_node_dir)
1942 || (svn_fs_fs__dag_node_kind(ancestor) != svn_node_dir))
1943 {
1944 return conflict_err(conflict_p, target_path);
1945 }
1946
1947
1948 /* Possible early merge failure: if target and ancestor have
1949 different property lists, then the merge should fail.
1950 Propchanges can *only* be committed on an up-to-date directory.
1951 ### TODO: see issue #418 about the inelegance of this.
1952
1953 Another possible, similar, early merge failure: if source and
1954 ancestor have different property lists (meaning someone else
1955 changed directory properties while our commit transaction was
1956 happening), the merge should fail. See issue #2751.
1957 */
1958 {
1959 node_revision_t *tgt_nr, *anc_nr, *src_nr;
1960 svn_boolean_t same;
1961 apr_pool_t *scratch_pool;
1962
1963 /* Get node revisions for our id's. */
1964 scratch_pool = svn_pool_create(pool);
1965 SVN_ERR(svn_fs_fs__get_node_revision(&tgt_nr, fs, target_id, pool,
1966 scratch_pool));
1967 svn_pool_clear(scratch_pool);
1968 SVN_ERR(svn_fs_fs__get_node_revision(&anc_nr, fs, ancestor_id, pool,
1969 scratch_pool));
1970 svn_pool_clear(scratch_pool);
1971 SVN_ERR(svn_fs_fs__get_node_revision(&src_nr, fs, source_id, pool,
1972 scratch_pool));
1973 svn_pool_destroy(scratch_pool);
1974
1975 /* Now compare the prop-keys of the skels. Note that just because
1976 the keys are different -doesn't- mean the proplists have
1977 different contents. */
1978 SVN_ERR(svn_fs_fs__prop_rep_equal(&same, fs, src_nr, anc_nr, pool));
1979 if (! same)
1980 return conflict_err(conflict_p, target_path);
1981
1982 /* The directory entries got changed in the repository but the directory
1983 properties did not. */
1984 SVN_ERR(svn_fs_fs__prop_rep_equal(&same, fs, tgt_nr, anc_nr, pool));
1985 if (! same)
1986 {
1987 /* There is an incoming prop change for this directory.
1988 We will accept it only if the directory changes were mere updates
1989 to its entries, i.e. there were no additions or removals.
1990 Those could cause update problems to the working copy. */
1991 svn_boolean_t changed;
1992 SVN_ERR(compare_dir_structure(&changed, source, ancestor, pool));
1993
1994 if (changed)
1995 return conflict_err(conflict_p, target_path);
1996 }
1997 }
1998
1999 /* ### todo: it would be more efficient to simply check for a NULL
2000 entries hash where necessary below than to allocate an empty hash
2001 here, but another day, another day... */
2002 SVN_ERR(svn_fs_fs__dag_dir_entries(&s_entries, source, pool));
2003 SVN_ERR(svn_fs_fs__dag_dir_entries(&t_entries, target, pool));
2004 SVN_ERR(svn_fs_fs__dag_dir_entries(&a_entries, ancestor, pool));
2005
2006 fs_supports_mergeinfo = svn_fs_fs__fs_supports_mergeinfo(fs);
2007
2008 /* for each entry E in a_entries... */
2009 iterpool = svn_pool_create(pool);
2010 for (i = 0; i < a_entries->nelts; ++i)
2011 {
2012 svn_fs_dirent_t *s_entry, *t_entry, *a_entry;
2013 svn_pool_clear(iterpool);
2014
2015 a_entry = APR_ARRAY_IDX(a_entries, i, svn_fs_dirent_t *);
2016 s_entry = svn_fs_fs__find_dir_entry(s_entries, a_entry->name, &s_idx);
2017 t_entry = svn_fs_fs__find_dir_entry(t_entries, a_entry->name, &t_idx);
2018
2019 /* No changes were made to this entry while the transaction was
2020 in progress, so do nothing to the target. */
2021 if (s_entry && svn_fs_fs__id_eq(a_entry->id, s_entry->id))
2022 continue;
2023
2024 /* A change was made to this entry while the transaction was in
2025 process, but the transaction did not touch this entry. */
2026 else if (t_entry && svn_fs_fs__id_eq(a_entry->id, t_entry->id))
2027 {
2028 dag_node_t *t_ent_node;
2029 SVN_ERR(svn_fs_fs__dag_get_node(&t_ent_node, fs,
2030 t_entry->id, iterpool));
2031 if (fs_supports_mergeinfo)
2032 {
2033 apr_int64_t mergeinfo_start;
2034 SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_start,
2035 t_ent_node));
2036 mergeinfo_increment -= mergeinfo_start;
2037 }
2038
2039 if (s_entry)
2040 {
2041 dag_node_t *s_ent_node;
2042 SVN_ERR(svn_fs_fs__dag_get_node(&s_ent_node, fs,
2043 s_entry->id, iterpool));
2044
2045 if (fs_supports_mergeinfo)
2046 {
2047 apr_int64_t mergeinfo_end;
2048 SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_end,
2049 s_ent_node));
2050 mergeinfo_increment += mergeinfo_end;
2051 }
2052
2053 SVN_ERR(svn_fs_fs__dag_set_entry(target, a_entry->name,
2054 s_entry->id,
2055 s_entry->kind,
2056 txn_id,
2057 pool));
2058 }
2059 else
2060 {
2061 SVN_ERR(svn_fs_fs__dag_delete(target, a_entry->name, txn_id,
2062 iterpool));
2063 }
2064 }
2065
2066 /* Changes were made to this entry both within the transaction
2067 and to the repository while the transaction was in progress.
2068 They must be merged or declared to be in conflict. */
2069 else
2070 {
2071 dag_node_t *s_ent_node, *t_ent_node, *a_ent_node;
2072 const char *new_tpath;
2073 apr_int64_t sub_mergeinfo_increment;
2074
2075 /* If SOURCE-ENTRY and TARGET-ENTRY are both null, that's a
2076 double delete; if one of them is null, that's a delete versus
2077 a modification. In any of these cases, flag a conflict. */
2078 if (s_entry == NULL || t_entry == NULL)
2079 return conflict_err(conflict_p,
2080 svn_fspath__join(target_path,
2081 a_entry->name,
2082 iterpool));
2083
2084 /* If any of the three entries is of type file, flag a conflict. */
2085 if (s_entry->kind == svn_node_file
2086 || t_entry->kind == svn_node_file
2087 || a_entry->kind == svn_node_file)
2088 return conflict_err(conflict_p,
2089 svn_fspath__join(target_path,
2090 a_entry->name,
2091 iterpool));
2092
2093 /* If either SOURCE-ENTRY or TARGET-ENTRY is not a direct
2094 modification of ANCESTOR-ENTRY, declare a conflict. */
2095 if (!svn_fs_fs__id_part_eq(svn_fs_fs__id_node_id(s_entry->id),
2096 svn_fs_fs__id_node_id(a_entry->id))
2097 || !svn_fs_fs__id_part_eq(svn_fs_fs__id_copy_id(s_entry->id),
2098 svn_fs_fs__id_copy_id(a_entry->id))
2099 || !svn_fs_fs__id_part_eq(svn_fs_fs__id_node_id(t_entry->id),
2100 svn_fs_fs__id_node_id(a_entry->id))
2101 || !svn_fs_fs__id_part_eq(svn_fs_fs__id_copy_id(t_entry->id),
2102 svn_fs_fs__id_copy_id(a_entry->id)))
2103 return conflict_err(conflict_p,
2104 svn_fspath__join(target_path,
2105 a_entry->name,
2106 iterpool));
2107
2108 /* Direct modifications were made to the directory
2109 ANCESTOR-ENTRY in both SOURCE and TARGET. Recursively
2110 merge these modifications. */
2111 SVN_ERR(svn_fs_fs__dag_get_node(&s_ent_node, fs,
2112 s_entry->id, iterpool));
2113 SVN_ERR(svn_fs_fs__dag_get_node(&t_ent_node, fs,
2114 t_entry->id, iterpool));
2115 SVN_ERR(svn_fs_fs__dag_get_node(&a_ent_node, fs,
2116 a_entry->id, iterpool));
2117 new_tpath = svn_fspath__join(target_path, t_entry->name, iterpool);
2118 SVN_ERR(merge(conflict_p, new_tpath,
2119 t_ent_node, s_ent_node, a_ent_node,
2120 txn_id,
2121 &sub_mergeinfo_increment,
2122 iterpool));
2123 if (fs_supports_mergeinfo)
2124 mergeinfo_increment += sub_mergeinfo_increment;
2125 }
2126 }
2127
2128 /* For each entry E in source but not in ancestor */
2129 for (i = 0; i < s_entries->nelts; ++i)
2130 {
2131 svn_fs_dirent_t *a_entry, *s_entry, *t_entry;
2132 dag_node_t *s_ent_node;
2133
2134 svn_pool_clear(iterpool);
2135
2136 s_entry = APR_ARRAY_IDX(s_entries, i, svn_fs_dirent_t *);
2137 a_entry = svn_fs_fs__find_dir_entry(a_entries, s_entry->name, &s_idx);
2138 t_entry = svn_fs_fs__find_dir_entry(t_entries, s_entry->name, &t_idx);
2139
2140 /* Process only entries in source that are NOT in ancestor. */
2141 if (a_entry)
2142 continue;
2143
2144 /* If NAME exists in TARGET, declare a conflict. */
2145 if (t_entry)
2146 return conflict_err(conflict_p,
2147 svn_fspath__join(target_path,
2148 t_entry->name,
2149 iterpool));
2150
2151 SVN_ERR(svn_fs_fs__dag_get_node(&s_ent_node, fs,
2152 s_entry->id, iterpool));
2153 if (fs_supports_mergeinfo)
2154 {
2155 apr_int64_t mergeinfo_s;
2156 SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_s,
2157 s_ent_node));
2158 mergeinfo_increment += mergeinfo_s;
2159 }
2160
2161 SVN_ERR(svn_fs_fs__dag_set_entry
2162 (target, s_entry->name, s_entry->id, s_entry->kind,
2163 txn_id, iterpool));
2164 }
2165 svn_pool_destroy(iterpool);
2166
2167 SVN_ERR(svn_fs_fs__dag_update_ancestry(target, source, pool));
2168
2169 if (fs_supports_mergeinfo)
2170 SVN_ERR(svn_fs_fs__dag_increment_mergeinfo_count(target,
2171 mergeinfo_increment,
2172 pool));
2173
2174 if (mergeinfo_increment_out)
2175 *mergeinfo_increment_out = mergeinfo_increment;
2176
2177 return SVN_NO_ERROR;
2178 }
2179
2180 /* Merge changes between an ancestor and SOURCE_NODE into
2181 TXN. The ancestor is either ANCESTOR_NODE, or if
2182 that is null, TXN's base node.
2183
2184 If the merge is successful, TXN's base will become
2185 SOURCE_NODE, and its root node will have a new ID, a
2186 successor of SOURCE_NODE.
2187
2188 If a conflict results, update *CONFLICT to the path in the txn that
2189 conflicted; see the CONFLICT_P parameter of merge() for details. */
2190 static svn_error_t *
merge_changes(dag_node_t * ancestor_node,dag_node_t * source_node,svn_fs_txn_t * txn,svn_stringbuf_t * conflict,apr_pool_t * pool)2191 merge_changes(dag_node_t *ancestor_node,
2192 dag_node_t *source_node,
2193 svn_fs_txn_t *txn,
2194 svn_stringbuf_t *conflict,
2195 apr_pool_t *pool)
2196 {
2197 dag_node_t *txn_root_node;
2198 svn_fs_t *fs = txn->fs;
2199 const svn_fs_fs__id_part_t *txn_id = svn_fs_fs__txn_get_id(txn);
2200
2201 SVN_ERR(svn_fs_fs__dag_txn_root(&txn_root_node, fs, txn_id, pool));
2202
2203 if (ancestor_node == NULL)
2204 {
2205 SVN_ERR(svn_fs_fs__dag_txn_base_root(&ancestor_node, fs,
2206 txn_id, pool));
2207 }
2208
2209 if (svn_fs_fs__id_eq(svn_fs_fs__dag_get_id(ancestor_node),
2210 svn_fs_fs__dag_get_id(txn_root_node)))
2211 {
2212 /* If no changes have been made in TXN since its current base,
2213 then it can't conflict with any changes since that base.
2214 The caller isn't supposed to call us in that case. */
2215 SVN_ERR_MALFUNCTION();
2216 }
2217 else
2218 SVN_ERR(merge(conflict, "/", txn_root_node,
2219 source_node, ancestor_node, txn_id, NULL, pool));
2220
2221 return SVN_NO_ERROR;
2222 }
2223
2224
2225 svn_error_t *
svn_fs_fs__commit_txn(const char ** conflict_p,svn_revnum_t * new_rev,svn_fs_txn_t * txn,apr_pool_t * pool)2226 svn_fs_fs__commit_txn(const char **conflict_p,
2227 svn_revnum_t *new_rev,
2228 svn_fs_txn_t *txn,
2229 apr_pool_t *pool)
2230 {
2231 /* How do commits work in Subversion?
2232 *
2233 * When you're ready to commit, here's what you have:
2234 *
2235 * 1. A transaction, with a mutable tree hanging off it.
2236 * 2. A base revision, against which TXN_TREE was made.
2237 * 3. A latest revision, which may be newer than the base rev.
2238 *
2239 * The problem is that if latest != base, then one can't simply
2240 * attach the txn root as the root of the new revision, because that
2241 * would lose all the changes between base and latest. It is also
2242 * not acceptable to insist that base == latest; in a busy
2243 * repository, commits happen too fast to insist that everyone keep
2244 * their entire tree up-to-date at all times. Non-overlapping
2245 * changes should not interfere with each other.
2246 *
2247 * The solution is to merge the changes between base and latest into
2248 * the txn tree [see the function merge()]. The txn tree is the
2249 * only one of the three trees that is mutable, so it has to be the
2250 * one to adjust.
2251 *
2252 * You might have to adjust it more than once, if a new latest
2253 * revision gets committed while you were merging in the previous
2254 * one. For example:
2255 *
2256 * 1. Jane starts txn T, based at revision 6.
2257 * 2. Someone commits (or already committed) revision 7.
2258 * 3. Jane's starts merging the changes between 6 and 7 into T.
2259 * 4. Meanwhile, someone commits revision 8.
2260 * 5. Jane finishes the 6-->7 merge. T could now be committed
2261 * against a latest revision of 7, if only that were still the
2262 * latest. Unfortunately, 8 is now the latest, so...
2263 * 6. Jane starts merging the changes between 7 and 8 into T.
2264 * 7. Meanwhile, no one commits any new revisions. Whew.
2265 * 8. Jane commits T, creating revision 9, whose tree is exactly
2266 * T's tree, except immutable now.
2267 *
2268 * Lather, rinse, repeat.
2269 */
2270
2271 svn_error_t *err = SVN_NO_ERROR;
2272 svn_stringbuf_t *conflict = svn_stringbuf_create_empty(pool);
2273 svn_fs_t *fs = txn->fs;
2274 fs_fs_data_t *ffd = fs->fsap_data;
2275
2276 /* Limit memory usage when the repository has a high commit rate and
2277 needs to run the following while loop multiple times. The memory
2278 growth without an iteration pool is very noticeable when the
2279 transaction modifies a node that has 20,000 sibling nodes. */
2280 apr_pool_t *iterpool = svn_pool_create(pool);
2281
2282 /* Initialize output params. */
2283 *new_rev = SVN_INVALID_REVNUM;
2284 if (conflict_p)
2285 *conflict_p = NULL;
2286
2287 while (1729)
2288 {
2289 svn_revnum_t youngish_rev;
2290 svn_fs_root_t *youngish_root;
2291 dag_node_t *youngish_root_node;
2292
2293 svn_pool_clear(iterpool);
2294
2295 /* Get the *current* youngest revision. We call it "youngish"
2296 because new revisions might get committed after we've
2297 obtained it. */
2298
2299 SVN_ERR(svn_fs_fs__youngest_rev(&youngish_rev, fs, iterpool));
2300 SVN_ERR(svn_fs_fs__revision_root(&youngish_root, fs, youngish_rev,
2301 iterpool));
2302
2303 /* Get the dag node for the youngest revision. Later we'll use
2304 it as the SOURCE argument to a merge, and if the merge
2305 succeeds, this youngest root node will become the new base
2306 root for the svn txn that was the target of the merge (but
2307 note that the youngest rev may have changed by then -- that's
2308 why we're careful to get this root in its own bdb txn
2309 here). */
2310 SVN_ERR(get_root(&youngish_root_node, youngish_root, iterpool));
2311
2312 /* Try to merge. If the merge succeeds, the base root node of
2313 TARGET's txn will become the same as youngish_root_node, so
2314 any future merges will only be between that node and whatever
2315 the root node of the youngest rev is by then. */
2316 err = merge_changes(NULL, youngish_root_node, txn, conflict, iterpool);
2317 if (err)
2318 {
2319 if ((err->apr_err == SVN_ERR_FS_CONFLICT) && conflict_p)
2320 *conflict_p = conflict->data;
2321 goto cleanup;
2322 }
2323 txn->base_rev = youngish_rev;
2324
2325 /* Try to commit. */
2326 err = svn_fs_fs__commit(new_rev, fs, txn, iterpool);
2327 if (err && (err->apr_err == SVN_ERR_FS_TXN_OUT_OF_DATE))
2328 {
2329 /* Did someone else finish committing a new revision while we
2330 were in mid-merge or mid-commit? If so, we'll need to
2331 loop again to merge the new changes in, then try to
2332 commit again. Or if that's not what happened, then just
2333 return the error. */
2334 svn_revnum_t youngest_rev;
2335 SVN_ERR(svn_fs_fs__youngest_rev(&youngest_rev, fs, iterpool));
2336 if (youngest_rev == youngish_rev)
2337 goto cleanup;
2338 else
2339 svn_error_clear(err);
2340 }
2341 else if (err)
2342 {
2343 goto cleanup;
2344 }
2345 else
2346 {
2347 err = SVN_NO_ERROR;
2348 goto cleanup;
2349 }
2350 }
2351
2352 cleanup:
2353
2354 svn_fs_fs__reset_txn_caches(fs);
2355
2356 svn_pool_destroy(iterpool);
2357
2358 SVN_ERR(err);
2359
2360 if (ffd->pack_after_commit)
2361 {
2362 SVN_ERR(svn_fs_fs__pack(fs, 0, NULL, NULL, NULL, NULL, pool));
2363 }
2364
2365 return SVN_NO_ERROR;
2366 }
2367
2368
2369 /* Merge changes between two nodes into a third node. Given nodes
2370 SOURCE_PATH under SOURCE_ROOT, TARGET_PATH under TARGET_ROOT and
2371 ANCESTOR_PATH under ANCESTOR_ROOT, modify target to contain all the
2372 changes between the ancestor and source. If there are conflicts,
2373 return SVN_ERR_FS_CONFLICT and set *CONFLICT_P to a textual
2374 description of the offending changes. Perform any temporary
2375 allocations in POOL. */
2376 static svn_error_t *
fs_merge(const char ** conflict_p,svn_fs_root_t * source_root,const char * source_path,svn_fs_root_t * target_root,const char * target_path,svn_fs_root_t * ancestor_root,const char * ancestor_path,apr_pool_t * pool)2377 fs_merge(const char **conflict_p,
2378 svn_fs_root_t *source_root,
2379 const char *source_path,
2380 svn_fs_root_t *target_root,
2381 const char *target_path,
2382 svn_fs_root_t *ancestor_root,
2383 const char *ancestor_path,
2384 apr_pool_t *pool)
2385 {
2386 dag_node_t *source, *ancestor;
2387 svn_fs_txn_t *txn;
2388 svn_error_t *err;
2389 svn_stringbuf_t *conflict = svn_stringbuf_create_empty(pool);
2390
2391 if (! target_root->is_txn_root)
2392 return SVN_FS__NOT_TXN(target_root);
2393
2394 /* Paranoia. */
2395 if ((source_root->fs != ancestor_root->fs)
2396 || (target_root->fs != ancestor_root->fs))
2397 {
2398 return svn_error_create
2399 (SVN_ERR_FS_CORRUPT, NULL,
2400 _("Bad merge; ancestor, source, and target not all in same fs"));
2401 }
2402
2403 /* ### kff todo: is there any compelling reason to get the nodes in
2404 one db transaction? Right now we don't; txn_body_get_root() gets
2405 one node at a time. This will probably need to change:
2406
2407 Jim Blandy <jimb@zwingli.cygnus.com> writes:
2408 > svn_fs_merge needs to be a single transaction, to protect it against
2409 > people deleting parents of nodes it's working on, etc.
2410 */
2411
2412 /* Get the ancestor node. */
2413 SVN_ERR(get_root(&ancestor, ancestor_root, pool));
2414
2415 /* Get the source node. */
2416 SVN_ERR(get_root(&source, source_root, pool));
2417
2418 /* Open a txn for the txn root into which we're merging. */
2419 SVN_ERR(svn_fs_fs__open_txn(&txn, ancestor_root->fs, target_root->txn,
2420 pool));
2421
2422 /* Merge changes between ANCESTOR and SOURCE into TXN. */
2423 err = merge_changes(ancestor, source, txn, conflict, pool);
2424 if (err)
2425 {
2426 if ((err->apr_err == SVN_ERR_FS_CONFLICT) && conflict_p)
2427 *conflict_p = conflict->data;
2428 return svn_error_trace(err);
2429 }
2430
2431 return SVN_NO_ERROR;
2432 }
2433
2434 svn_error_t *
svn_fs_fs__deltify(svn_fs_t * fs,svn_revnum_t revision,apr_pool_t * pool)2435 svn_fs_fs__deltify(svn_fs_t *fs,
2436 svn_revnum_t revision,
2437 apr_pool_t *pool)
2438 {
2439 /* Deltify is a no-op for fs_fs. */
2440
2441 return SVN_NO_ERROR;
2442 }
2443
2444
2445
2446 /* Directories. */
2447
2448 /* Set *TABLE_P to a newly allocated APR hash table containing the
2449 entries of the directory at PATH in ROOT. The keys of the table
2450 are entry names, as byte strings, excluding the final null
2451 character; the table's values are pointers to svn_fs_dirent_t
2452 structures. Allocate the table and its contents in POOL. */
2453 static svn_error_t *
fs_dir_entries(apr_hash_t ** table_p,svn_fs_root_t * root,const char * path,apr_pool_t * pool)2454 fs_dir_entries(apr_hash_t **table_p,
2455 svn_fs_root_t *root,
2456 const char *path,
2457 apr_pool_t *pool)
2458 {
2459 dag_node_t *node;
2460 apr_hash_t *hash = svn_hash__make(pool);
2461 apr_array_header_t *table;
2462 int i;
2463
2464 /* Get the entries for this path in the caller's pool. */
2465 SVN_ERR(get_dag(&node, root, path, pool));
2466 SVN_ERR(svn_fs_fs__dag_dir_entries(&table, node, pool));
2467
2468 /* Convert directory array to hash. */
2469 for (i = 0; i < table->nelts; ++i)
2470 {
2471 svn_fs_dirent_t *entry = APR_ARRAY_IDX(table, i, svn_fs_dirent_t *);
2472 svn_hash_sets(hash, entry->name, entry);
2473 }
2474
2475 *table_p = hash;
2476 return SVN_NO_ERROR;
2477 }
2478
2479 static svn_error_t *
fs_dir_optimal_order(apr_array_header_t ** ordered_p,svn_fs_root_t * root,apr_hash_t * entries,apr_pool_t * result_pool,apr_pool_t * scratch_pool)2480 fs_dir_optimal_order(apr_array_header_t **ordered_p,
2481 svn_fs_root_t *root,
2482 apr_hash_t *entries,
2483 apr_pool_t *result_pool,
2484 apr_pool_t *scratch_pool)
2485 {
2486 *ordered_p = svn_fs_fs__order_dir_entries(root->fs, entries, result_pool,
2487 scratch_pool);
2488
2489 return SVN_NO_ERROR;
2490 }
2491
2492 /* Raise an error if PATH contains a newline because FSFS cannot handle
2493 * such paths. See issue #4340. */
2494 static svn_error_t *
check_newline(const char * path,apr_pool_t * pool)2495 check_newline(const char *path, apr_pool_t *pool)
2496 {
2497 char *c = strchr(path, '\n');
2498
2499 if (c)
2500 return svn_error_createf(SVN_ERR_FS_PATH_SYNTAX, NULL,
2501 _("Invalid control character '0x%02x' in path '%s'"),
2502 (unsigned char)*c, svn_path_illegal_path_escape(path, pool));
2503
2504 return SVN_NO_ERROR;
2505 }
2506
2507 /* Create a new directory named PATH in ROOT. The new directory has
2508 no entries, and no properties. ROOT must be the root of a
2509 transaction, not a revision. Do any necessary temporary allocation
2510 in POOL. */
2511 static svn_error_t *
fs_make_dir(svn_fs_root_t * root,const char * path,apr_pool_t * pool)2512 fs_make_dir(svn_fs_root_t *root,
2513 const char *path,
2514 apr_pool_t *pool)
2515 {
2516 parent_path_t *parent_path;
2517 dag_node_t *sub_dir;
2518 const svn_fs_fs__id_part_t *txn_id = root_txn_id(root);
2519
2520 SVN_ERR(check_newline(path, pool));
2521
2522 path = svn_fs__canonicalize_abspath(path, pool);
2523 SVN_ERR(open_path(&parent_path, root, path, open_path_last_optional,
2524 TRUE, pool));
2525
2526 /* Check (recursively) to see if some lock is 'reserving' a path at
2527 that location, or even some child-path; if so, check that we can
2528 use it. */
2529 if (root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
2530 SVN_ERR(svn_fs_fs__allow_locked_operation(path, root->fs, TRUE, FALSE,
2531 pool));
2532
2533 /* If there's already a sub-directory by that name, complain. This
2534 also catches the case of trying to make a subdirectory named `/'. */
2535 if (parent_path->node)
2536 return SVN_FS__ALREADY_EXISTS(root, path);
2537
2538 /* Create the subdirectory. */
2539 SVN_ERR(make_path_mutable(root, parent_path->parent, path, pool));
2540 SVN_ERR(svn_fs_fs__dag_make_dir(&sub_dir,
2541 parent_path->parent->node,
2542 parent_path_path(parent_path->parent,
2543 pool),
2544 parent_path->entry,
2545 txn_id,
2546 pool));
2547
2548 /* Add this directory to the path cache. */
2549 SVN_ERR(dag_node_cache_set(root, parent_path_path(parent_path, pool),
2550 sub_dir, pool));
2551
2552 /* Make a record of this modification in the changes table. */
2553 return add_change(root->fs, txn_id, path, svn_fs_fs__dag_get_id(sub_dir),
2554 svn_fs_path_change_add, FALSE, FALSE, FALSE,
2555 svn_node_dir, SVN_INVALID_REVNUM, NULL, pool);
2556 }
2557
2558
2559 /* Delete the node at PATH under ROOT. ROOT must be a transaction
2560 root. Perform temporary allocations in POOL. */
2561 static svn_error_t *
fs_delete_node(svn_fs_root_t * root,const char * path,apr_pool_t * pool)2562 fs_delete_node(svn_fs_root_t *root,
2563 const char *path,
2564 apr_pool_t *pool)
2565 {
2566 parent_path_t *parent_path;
2567 const svn_fs_fs__id_part_t *txn_id;
2568 apr_int64_t mergeinfo_count = 0;
2569 svn_node_kind_t kind;
2570
2571 if (! root->is_txn_root)
2572 return SVN_FS__NOT_TXN(root);
2573
2574 txn_id = root_txn_id(root);
2575 path = svn_fs__canonicalize_abspath(path, pool);
2576 SVN_ERR(open_path(&parent_path, root, path, 0, TRUE, pool));
2577 kind = svn_fs_fs__dag_node_kind(parent_path->node);
2578
2579 /* We can't remove the root of the filesystem. */
2580 if (! parent_path->parent)
2581 return svn_error_create(SVN_ERR_FS_ROOT_DIR, NULL,
2582 _("The root directory cannot be deleted"));
2583
2584 /* Check to see if path (or any child thereof) is locked; if so,
2585 check that we can use the existing lock(s). */
2586 if (root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
2587 SVN_ERR(svn_fs_fs__allow_locked_operation(path, root->fs, TRUE, FALSE,
2588 pool));
2589
2590 /* Make the parent directory mutable, and do the deletion. */
2591 SVN_ERR(make_path_mutable(root, parent_path->parent, path, pool));
2592 if (svn_fs_fs__fs_supports_mergeinfo(root->fs))
2593 SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_count,
2594 parent_path->node));
2595 SVN_ERR(svn_fs_fs__dag_delete(parent_path->parent->node,
2596 parent_path->entry,
2597 txn_id, pool));
2598
2599 /* Remove this node and any children from the path cache. */
2600 SVN_ERR(dag_node_cache_invalidate(root, parent_path_path(parent_path, pool),
2601 pool));
2602
2603 /* Update mergeinfo counts for parents */
2604 if (mergeinfo_count > 0)
2605 SVN_ERR(increment_mergeinfo_up_tree(parent_path->parent,
2606 -mergeinfo_count,
2607 pool));
2608
2609 /* Make a record of this modification in the changes table. */
2610 return add_change(root->fs, txn_id, path,
2611 svn_fs_fs__dag_get_id(parent_path->node),
2612 svn_fs_path_change_delete, FALSE, FALSE, FALSE, kind,
2613 SVN_INVALID_REVNUM, NULL, pool);
2614 }
2615
2616
2617 /* Set *SAME_P to TRUE if FS1 and FS2 have the same UUID, else set to FALSE.
2618 Use POOL for temporary allocation only.
2619 Note: this code is duplicated between libsvn_fs_fs and libsvn_fs_base. */
2620 static svn_error_t *
fs_same_p(svn_boolean_t * same_p,svn_fs_t * fs1,svn_fs_t * fs2,apr_pool_t * pool)2621 fs_same_p(svn_boolean_t *same_p,
2622 svn_fs_t *fs1,
2623 svn_fs_t *fs2,
2624 apr_pool_t *pool)
2625 {
2626 *same_p = ! strcmp(fs1->uuid, fs2->uuid);
2627 return SVN_NO_ERROR;
2628 }
2629
2630 /* Copy the node at FROM_PATH under FROM_ROOT to TO_PATH under
2631 TO_ROOT. If PRESERVE_HISTORY is set, then the copy is recorded in
2632 the copies table. Perform temporary allocations in POOL. */
2633 static svn_error_t *
copy_helper(svn_fs_root_t * from_root,const char * from_path,svn_fs_root_t * to_root,const char * to_path,svn_boolean_t preserve_history,apr_pool_t * pool)2634 copy_helper(svn_fs_root_t *from_root,
2635 const char *from_path,
2636 svn_fs_root_t *to_root,
2637 const char *to_path,
2638 svn_boolean_t preserve_history,
2639 apr_pool_t *pool)
2640 {
2641 dag_node_t *from_node;
2642 parent_path_t *to_parent_path;
2643 const svn_fs_fs__id_part_t *txn_id = root_txn_id(to_root);
2644 svn_boolean_t same_p;
2645
2646 /* Use an error check, not an assert, because even the caller cannot
2647 guarantee that a filesystem's UUID has not changed "on the fly". */
2648 SVN_ERR(fs_same_p(&same_p, from_root->fs, to_root->fs, pool));
2649 if (! same_p)
2650 return svn_error_createf
2651 (SVN_ERR_UNSUPPORTED_FEATURE, NULL,
2652 _("Cannot copy between two different filesystems ('%s' and '%s')"),
2653 from_root->fs->path, to_root->fs->path);
2654
2655 /* more things that we can't do ATM */
2656 if (from_root->is_txn_root)
2657 return svn_error_create
2658 (SVN_ERR_UNSUPPORTED_FEATURE, NULL,
2659 _("Copy from mutable tree not currently supported"));
2660
2661 if (! to_root->is_txn_root)
2662 return svn_error_create
2663 (SVN_ERR_UNSUPPORTED_FEATURE, NULL,
2664 _("Copy immutable tree not supported"));
2665
2666 /* Get the NODE for FROM_PATH in FROM_ROOT.*/
2667 SVN_ERR(get_dag(&from_node, from_root, from_path, pool));
2668
2669 /* Build up the parent path from TO_PATH in TO_ROOT. If the last
2670 component does not exist, it's not that big a deal. We'll just
2671 make one there. */
2672 SVN_ERR(open_path(&to_parent_path, to_root, to_path,
2673 open_path_last_optional, TRUE, pool));
2674
2675 /* Check to see if path (or any child thereof) is locked; if so,
2676 check that we can use the existing lock(s). */
2677 if (to_root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
2678 SVN_ERR(svn_fs_fs__allow_locked_operation(to_path, to_root->fs,
2679 TRUE, FALSE, pool));
2680
2681 /* If the destination node already exists as the same node as the
2682 source (in other words, this operation would result in nothing
2683 happening at all), just do nothing an return successfully,
2684 proud that you saved yourself from a tiresome task. */
2685 if (to_parent_path->node &&
2686 svn_fs_fs__id_eq(svn_fs_fs__dag_get_id(from_node),
2687 svn_fs_fs__dag_get_id(to_parent_path->node)))
2688 return SVN_NO_ERROR;
2689
2690 if (! from_root->is_txn_root)
2691 {
2692 svn_fs_path_change_kind_t kind;
2693 dag_node_t *new_node;
2694 const char *from_canonpath;
2695 apr_int64_t mergeinfo_start;
2696 apr_int64_t mergeinfo_end;
2697
2698 /* If TO_PATH already existed prior to the copy, note that this
2699 operation is a replacement, not an addition. */
2700 if (to_parent_path->node)
2701 {
2702 kind = svn_fs_path_change_replace;
2703 if (svn_fs_fs__fs_supports_mergeinfo(to_root->fs))
2704 SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_start,
2705 to_parent_path->node));
2706 }
2707 else
2708 {
2709 kind = svn_fs_path_change_add;
2710 mergeinfo_start = 0;
2711 }
2712
2713 if (svn_fs_fs__fs_supports_mergeinfo(to_root->fs))
2714 SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_end,
2715 from_node));
2716
2717 /* Make sure the target node's parents are mutable. */
2718 SVN_ERR(make_path_mutable(to_root, to_parent_path->parent,
2719 to_path, pool));
2720
2721 /* Canonicalize the copyfrom path. */
2722 from_canonpath = svn_fs__canonicalize_abspath(from_path, pool);
2723
2724 SVN_ERR(svn_fs_fs__dag_copy(to_parent_path->parent->node,
2725 to_parent_path->entry,
2726 from_node,
2727 preserve_history,
2728 from_root->rev,
2729 from_canonpath,
2730 txn_id, pool));
2731
2732 if (kind != svn_fs_path_change_add)
2733 SVN_ERR(dag_node_cache_invalidate(to_root,
2734 parent_path_path(to_parent_path,
2735 pool), pool));
2736
2737 if (svn_fs_fs__fs_supports_mergeinfo(to_root->fs)
2738 && mergeinfo_start != mergeinfo_end)
2739 SVN_ERR(increment_mergeinfo_up_tree(to_parent_path->parent,
2740 mergeinfo_end - mergeinfo_start,
2741 pool));
2742
2743 /* Make a record of this modification in the changes table. */
2744 SVN_ERR(get_dag(&new_node, to_root, to_path, pool));
2745 SVN_ERR(add_change(to_root->fs, txn_id, to_path,
2746 svn_fs_fs__dag_get_id(new_node), kind, FALSE,
2747 FALSE, FALSE, svn_fs_fs__dag_node_kind(from_node),
2748 from_root->rev, from_canonpath, pool));
2749 }
2750 else
2751 {
2752 /* See IZ Issue #436 */
2753 /* Copying from transaction roots not currently available.
2754
2755 ### cmpilato todo someday: make this not so. :-) Note that
2756 when copying from mutable trees, you have to make sure that
2757 you aren't creating a cyclic graph filesystem, and a simple
2758 referencing operation won't cut it. Currently, we should not
2759 be able to reach this clause, and the interface reports that
2760 this only works from immutable trees anyway, but JimB has
2761 stated that this requirement need not be necessary in the
2762 future. */
2763
2764 SVN_ERR_MALFUNCTION();
2765 }
2766
2767 return SVN_NO_ERROR;
2768 }
2769
2770
2771 /* Create a copy of FROM_PATH in FROM_ROOT named TO_PATH in TO_ROOT.
2772 If FROM_PATH is a directory, copy it recursively. Temporary
2773 allocations are from POOL.*/
2774 static svn_error_t *
fs_copy(svn_fs_root_t * from_root,const char * from_path,svn_fs_root_t * to_root,const char * to_path,apr_pool_t * pool)2775 fs_copy(svn_fs_root_t *from_root,
2776 const char *from_path,
2777 svn_fs_root_t *to_root,
2778 const char *to_path,
2779 apr_pool_t *pool)
2780 {
2781 SVN_ERR(check_newline(to_path, pool));
2782
2783 return svn_error_trace(copy_helper(from_root,
2784 svn_fs__canonicalize_abspath(from_path,
2785 pool),
2786 to_root,
2787 svn_fs__canonicalize_abspath(to_path,
2788 pool),
2789 TRUE, pool));
2790 }
2791
2792
2793 /* Create a copy of FROM_PATH in FROM_ROOT named TO_PATH in TO_ROOT.
2794 If FROM_PATH is a directory, copy it recursively. No history is
2795 preserved. Temporary allocations are from POOL. */
2796 static svn_error_t *
fs_revision_link(svn_fs_root_t * from_root,svn_fs_root_t * to_root,const char * path,apr_pool_t * pool)2797 fs_revision_link(svn_fs_root_t *from_root,
2798 svn_fs_root_t *to_root,
2799 const char *path,
2800 apr_pool_t *pool)
2801 {
2802 if (! to_root->is_txn_root)
2803 return SVN_FS__NOT_TXN(to_root);
2804
2805 path = svn_fs__canonicalize_abspath(path, pool);
2806 return svn_error_trace(copy_helper(from_root, path, to_root, path,
2807 FALSE, pool));
2808 }
2809
2810
2811 /* Discover the copy ancestry of PATH under ROOT. Return a relevant
2812 ancestor/revision combination in *PATH_P and *REV_P. Temporary
2813 allocations are in POOL. */
2814 static svn_error_t *
fs_copied_from(svn_revnum_t * rev_p,const char ** path_p,svn_fs_root_t * root,const char * path,apr_pool_t * pool)2815 fs_copied_from(svn_revnum_t *rev_p,
2816 const char **path_p,
2817 svn_fs_root_t *root,
2818 const char *path,
2819 apr_pool_t *pool)
2820 {
2821 dag_node_t *node;
2822
2823 /* There is no cached entry, look it up the old-fashioned
2824 way. */
2825 SVN_ERR(get_dag(&node, root, path, pool));
2826 SVN_ERR(svn_fs_fs__dag_get_copyfrom_rev(rev_p, node));
2827 SVN_ERR(svn_fs_fs__dag_get_copyfrom_path(path_p, node));
2828
2829 return SVN_NO_ERROR;
2830 }
2831
2832
2833
2834 /* Files. */
2835
2836 /* Create the empty file PATH under ROOT. Temporary allocations are
2837 in POOL. */
2838 static svn_error_t *
fs_make_file(svn_fs_root_t * root,const char * path,apr_pool_t * pool)2839 fs_make_file(svn_fs_root_t *root,
2840 const char *path,
2841 apr_pool_t *pool)
2842 {
2843 parent_path_t *parent_path;
2844 dag_node_t *child;
2845 const svn_fs_fs__id_part_t *txn_id = root_txn_id(root);
2846
2847 SVN_ERR(check_newline(path, pool));
2848
2849 path = svn_fs__canonicalize_abspath(path, pool);
2850 SVN_ERR(open_path(&parent_path, root, path, open_path_last_optional,
2851 TRUE, pool));
2852
2853 /* If there's already a file by that name, complain.
2854 This also catches the case of trying to make a file named `/'. */
2855 if (parent_path->node)
2856 return SVN_FS__ALREADY_EXISTS(root, path);
2857
2858 /* Check (non-recursively) to see if path is locked; if so, check
2859 that we can use it. */
2860 if (root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
2861 SVN_ERR(svn_fs_fs__allow_locked_operation(path, root->fs, FALSE, FALSE,
2862 pool));
2863
2864 /* Create the file. */
2865 SVN_ERR(make_path_mutable(root, parent_path->parent, path, pool));
2866 SVN_ERR(svn_fs_fs__dag_make_file(&child,
2867 parent_path->parent->node,
2868 parent_path_path(parent_path->parent,
2869 pool),
2870 parent_path->entry,
2871 txn_id,
2872 pool));
2873
2874 /* Add this file to the path cache. */
2875 SVN_ERR(dag_node_cache_set(root, parent_path_path(parent_path, pool), child,
2876 pool));
2877
2878 /* Make a record of this modification in the changes table. */
2879 return add_change(root->fs, txn_id, path, svn_fs_fs__dag_get_id(child),
2880 svn_fs_path_change_add, TRUE, FALSE, FALSE,
2881 svn_node_file, SVN_INVALID_REVNUM, NULL, pool);
2882 }
2883
2884
2885 /* Set *LENGTH_P to the size of the file PATH under ROOT. Temporary
2886 allocations are in POOL. */
2887 static svn_error_t *
fs_file_length(svn_filesize_t * length_p,svn_fs_root_t * root,const char * path,apr_pool_t * pool)2888 fs_file_length(svn_filesize_t *length_p,
2889 svn_fs_root_t *root,
2890 const char *path,
2891 apr_pool_t *pool)
2892 {
2893 dag_node_t *file;
2894
2895 /* First create a dag_node_t from the root/path pair. */
2896 SVN_ERR(get_dag(&file, root, path, pool));
2897
2898 /* Now fetch its length */
2899 return svn_fs_fs__dag_file_length(length_p, file, pool);
2900 }
2901
2902
2903 /* Set *CHECKSUM to the checksum of type KIND for PATH under ROOT, or
2904 NULL if that information isn't available. Temporary allocations
2905 are from POOL. */
2906 static svn_error_t *
fs_file_checksum(svn_checksum_t ** checksum,svn_checksum_kind_t kind,svn_fs_root_t * root,const char * path,apr_pool_t * pool)2907 fs_file_checksum(svn_checksum_t **checksum,
2908 svn_checksum_kind_t kind,
2909 svn_fs_root_t *root,
2910 const char *path,
2911 apr_pool_t *pool)
2912 {
2913 dag_node_t *file;
2914
2915 SVN_ERR(get_dag(&file, root, path, pool));
2916 return svn_fs_fs__dag_file_checksum(checksum, file, kind, pool);
2917 }
2918
2919
2920 /* --- Machinery for svn_fs_file_contents() --- */
2921
2922 /* Set *CONTENTS to a readable stream that will return the contents of
2923 PATH under ROOT. The stream is allocated in POOL. */
2924 static svn_error_t *
fs_file_contents(svn_stream_t ** contents,svn_fs_root_t * root,const char * path,apr_pool_t * pool)2925 fs_file_contents(svn_stream_t **contents,
2926 svn_fs_root_t *root,
2927 const char *path,
2928 apr_pool_t *pool)
2929 {
2930 dag_node_t *node;
2931 svn_stream_t *file_stream;
2932
2933 /* First create a dag_node_t from the root/path pair. */
2934 SVN_ERR(get_dag(&node, root, path, pool));
2935
2936 /* Then create a readable stream from the dag_node_t. */
2937 SVN_ERR(svn_fs_fs__dag_get_contents(&file_stream, node, pool));
2938
2939 *contents = file_stream;
2940 return SVN_NO_ERROR;
2941 }
2942
2943 /* --- End machinery for svn_fs_file_contents() --- */
2944
2945
2946 /* --- Machinery for svn_fs_try_process_file_contents() --- */
2947
2948 static svn_error_t *
fs_try_process_file_contents(svn_boolean_t * success,svn_fs_root_t * root,const char * path,svn_fs_process_contents_func_t processor,void * baton,apr_pool_t * pool)2949 fs_try_process_file_contents(svn_boolean_t *success,
2950 svn_fs_root_t *root,
2951 const char *path,
2952 svn_fs_process_contents_func_t processor,
2953 void* baton,
2954 apr_pool_t *pool)
2955 {
2956 dag_node_t *node;
2957 SVN_ERR(get_dag(&node, root, path, pool));
2958
2959 return svn_fs_fs__dag_try_process_file_contents(success, node,
2960 processor, baton, pool);
2961 }
2962
2963 /* --- End machinery for svn_fs_try_process_file_contents() --- */
2964
2965
2966 /* --- Machinery for svn_fs_apply_textdelta() --- */
2967
2968
2969 /* Local baton type for all the helper functions below. */
2970 typedef struct txdelta_baton_t
2971 {
2972 /* This is the custom-built window consumer given to us by the delta
2973 library; it uniquely knows how to read data from our designated
2974 "source" stream, interpret the window, and write data to our
2975 designated "target" stream (in this case, our repos file.) */
2976 svn_txdelta_window_handler_t interpreter;
2977 void *interpreter_baton;
2978
2979 /* The original file info */
2980 svn_fs_root_t *root;
2981 const char *path;
2982
2983 /* Derived from the file info */
2984 dag_node_t *node;
2985
2986 svn_stream_t *source_stream;
2987 svn_stream_t *target_stream;
2988
2989 /* MD5 digest for the base text against which a delta is to be
2990 applied, and for the resultant fulltext, respectively. Either or
2991 both may be null, in which case ignored. */
2992 svn_checksum_t *base_checksum;
2993 svn_checksum_t *result_checksum;
2994
2995 /* Pool used by db txns */
2996 apr_pool_t *pool;
2997
2998 } txdelta_baton_t;
2999
3000
3001 /* The main window handler returned by svn_fs_apply_textdelta. */
3002 static svn_error_t *
window_consumer(svn_txdelta_window_t * window,void * baton)3003 window_consumer(svn_txdelta_window_t *window, void *baton)
3004 {
3005 txdelta_baton_t *tb = (txdelta_baton_t *) baton;
3006
3007 /* Send the window right through to the custom window interpreter.
3008 In theory, the interpreter will then write more data to
3009 cb->target_string. */
3010 SVN_ERR(tb->interpreter(window, tb->interpreter_baton));
3011
3012 /* Is the window NULL? If so, we're done. The stream has already been
3013 closed by the interpreter. */
3014 if (! window)
3015 SVN_ERR(svn_fs_fs__dag_finalize_edits(tb->node, tb->result_checksum,
3016 tb->pool));
3017
3018 return SVN_NO_ERROR;
3019 }
3020
3021 /* Helper function for fs_apply_textdelta. BATON is of type
3022 txdelta_baton_t. */
3023 static svn_error_t *
apply_textdelta(void * baton,apr_pool_t * pool)3024 apply_textdelta(void *baton, apr_pool_t *pool)
3025 {
3026 txdelta_baton_t *tb = (txdelta_baton_t *) baton;
3027 parent_path_t *parent_path;
3028 const svn_fs_fs__id_part_t *txn_id = root_txn_id(tb->root);
3029
3030 /* Call open_path with no flags, as we want this to return an error
3031 if the node for which we are searching doesn't exist. */
3032 SVN_ERR(open_path(&parent_path, tb->root, tb->path, 0, TRUE, pool));
3033
3034 /* Check (non-recursively) to see if path is locked; if so, check
3035 that we can use it. */
3036 if (tb->root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
3037 SVN_ERR(svn_fs_fs__allow_locked_operation(tb->path, tb->root->fs,
3038 FALSE, FALSE, pool));
3039
3040 /* Now, make sure this path is mutable. */
3041 SVN_ERR(make_path_mutable(tb->root, parent_path, tb->path, pool));
3042 tb->node = parent_path->node;
3043
3044 if (tb->base_checksum)
3045 {
3046 svn_checksum_t *checksum;
3047
3048 /* Until we finalize the node, its data_key points to the old
3049 contents, in other words, the base text. */
3050 SVN_ERR(svn_fs_fs__dag_file_checksum(&checksum, tb->node,
3051 tb->base_checksum->kind, pool));
3052 if (!svn_checksum_match(tb->base_checksum, checksum))
3053 return svn_checksum_mismatch_err(tb->base_checksum, checksum, pool,
3054 _("Base checksum mismatch on '%s'"),
3055 tb->path);
3056 }
3057
3058 /* Make a readable "source" stream out of the current contents of
3059 ROOT/PATH; obviously, this must done in the context of a db_txn.
3060 The stream is returned in tb->source_stream. */
3061 SVN_ERR(svn_fs_fs__dag_get_contents(&(tb->source_stream),
3062 tb->node, tb->pool));
3063
3064 /* Make a writable "target" stream */
3065 SVN_ERR(svn_fs_fs__dag_get_edit_stream(&(tb->target_stream), tb->node,
3066 tb->pool));
3067
3068 /* Now, create a custom window handler that uses our two streams. */
3069 svn_txdelta_apply(tb->source_stream,
3070 tb->target_stream,
3071 NULL,
3072 tb->path,
3073 tb->pool,
3074 &(tb->interpreter),
3075 &(tb->interpreter_baton));
3076
3077 /* Make a record of this modification in the changes table. */
3078 return add_change(tb->root->fs, txn_id, tb->path,
3079 svn_fs_fs__dag_get_id(tb->node),
3080 svn_fs_path_change_modify, TRUE, FALSE, FALSE,
3081 svn_node_file, SVN_INVALID_REVNUM, NULL, pool);
3082 }
3083
3084
3085 /* Set *CONTENTS_P and *CONTENTS_BATON_P to a window handler and baton
3086 that will accept text delta windows to modify the contents of PATH
3087 under ROOT. Allocations are in POOL. */
3088 static svn_error_t *
fs_apply_textdelta(svn_txdelta_window_handler_t * contents_p,void ** contents_baton_p,svn_fs_root_t * root,const char * path,svn_checksum_t * base_checksum,svn_checksum_t * result_checksum,apr_pool_t * pool)3089 fs_apply_textdelta(svn_txdelta_window_handler_t *contents_p,
3090 void **contents_baton_p,
3091 svn_fs_root_t *root,
3092 const char *path,
3093 svn_checksum_t *base_checksum,
3094 svn_checksum_t *result_checksum,
3095 apr_pool_t *pool)
3096 {
3097 txdelta_baton_t *tb = apr_pcalloc(pool, sizeof(*tb));
3098
3099 tb->root = root;
3100 tb->path = svn_fs__canonicalize_abspath(path, pool);
3101 tb->pool = pool;
3102 tb->base_checksum = svn_checksum_dup(base_checksum, pool);
3103 tb->result_checksum = svn_checksum_dup(result_checksum, pool);
3104
3105 SVN_ERR(apply_textdelta(tb, pool));
3106
3107 *contents_p = window_consumer;
3108 *contents_baton_p = tb;
3109 return SVN_NO_ERROR;
3110 }
3111
3112 /* --- End machinery for svn_fs_apply_textdelta() --- */
3113
3114 /* --- Machinery for svn_fs_apply_text() --- */
3115
3116 /* Baton for svn_fs_apply_text(). */
3117 struct text_baton_t
3118 {
3119 /* The original file info */
3120 svn_fs_root_t *root;
3121 const char *path;
3122
3123 /* Derived from the file info */
3124 dag_node_t *node;
3125
3126 /* The returned stream that will accept the file's new contents. */
3127 svn_stream_t *stream;
3128
3129 /* The actual fs stream that the returned stream will write to. */
3130 svn_stream_t *file_stream;
3131
3132 /* MD5 digest for the final fulltext written to the file. May
3133 be null, in which case ignored. */
3134 svn_checksum_t *result_checksum;
3135
3136 /* Pool used by db txns */
3137 apr_pool_t *pool;
3138 };
3139
3140
3141 /* A wrapper around svn_fs_fs__dag_finalize_edits, but for
3142 * fulltext data, not text deltas. Closes BATON->file_stream.
3143 *
3144 * Note: If you're confused about how this function relates to another
3145 * of similar name, think of it this way:
3146 *
3147 * svn_fs_apply_textdelta() ==> ... ==> txn_body_txdelta_finalize_edits()
3148 * svn_fs_apply_text() ==> ... ==> txn_body_fulltext_finalize_edits()
3149 */
3150
3151 /* Write function for the publically returned stream. */
3152 static svn_error_t *
text_stream_writer(void * baton,const char * data,apr_size_t * len)3153 text_stream_writer(void *baton,
3154 const char *data,
3155 apr_size_t *len)
3156 {
3157 struct text_baton_t *tb = baton;
3158
3159 /* Psst, here's some data. Pass it on to the -real- file stream. */
3160 return svn_stream_write(tb->file_stream, data, len);
3161 }
3162
3163 /* Close function for the publically returned stream. */
3164 static svn_error_t *
text_stream_closer(void * baton)3165 text_stream_closer(void *baton)
3166 {
3167 struct text_baton_t *tb = baton;
3168
3169 /* Close the internal-use stream. ### This used to be inside of
3170 txn_body_fulltext_finalize_edits(), but that invoked a nested
3171 Berkeley DB transaction -- scandalous! */
3172 SVN_ERR(svn_stream_close(tb->file_stream));
3173
3174 /* Need to tell fs that we're done sending text */
3175 return svn_fs_fs__dag_finalize_edits(tb->node, tb->result_checksum,
3176 tb->pool);
3177 }
3178
3179
3180 /* Helper function for fs_apply_text. BATON is of type
3181 text_baton_t. */
3182 static svn_error_t *
apply_text(void * baton,apr_pool_t * pool)3183 apply_text(void *baton, apr_pool_t *pool)
3184 {
3185 struct text_baton_t *tb = baton;
3186 parent_path_t *parent_path;
3187 const svn_fs_fs__id_part_t *txn_id = root_txn_id(tb->root);
3188
3189 /* Call open_path with no flags, as we want this to return an error
3190 if the node for which we are searching doesn't exist. */
3191 SVN_ERR(open_path(&parent_path, tb->root, tb->path, 0, TRUE, pool));
3192
3193 /* Check (non-recursively) to see if path is locked; if so, check
3194 that we can use it. */
3195 if (tb->root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
3196 SVN_ERR(svn_fs_fs__allow_locked_operation(tb->path, tb->root->fs,
3197 FALSE, FALSE, pool));
3198
3199 /* Now, make sure this path is mutable. */
3200 SVN_ERR(make_path_mutable(tb->root, parent_path, tb->path, pool));
3201 tb->node = parent_path->node;
3202
3203 /* Make a writable stream for replacing the file's text. */
3204 SVN_ERR(svn_fs_fs__dag_get_edit_stream(&(tb->file_stream), tb->node,
3205 tb->pool));
3206
3207 /* Create a 'returnable' stream which writes to the file_stream. */
3208 tb->stream = svn_stream_create(tb, tb->pool);
3209 svn_stream_set_write(tb->stream, text_stream_writer);
3210 svn_stream_set_close(tb->stream, text_stream_closer);
3211
3212 /* Make a record of this modification in the changes table. */
3213 return add_change(tb->root->fs, txn_id, tb->path,
3214 svn_fs_fs__dag_get_id(tb->node),
3215 svn_fs_path_change_modify, TRUE, FALSE, FALSE,
3216 svn_node_file, SVN_INVALID_REVNUM, NULL, pool);
3217 }
3218
3219
3220 /* Return a writable stream that will set the contents of PATH under
3221 ROOT. RESULT_CHECKSUM is the MD5 checksum of the final result.
3222 Temporary allocations are in POOL. */
3223 static svn_error_t *
fs_apply_text(svn_stream_t ** contents_p,svn_fs_root_t * root,const char * path,svn_checksum_t * result_checksum,apr_pool_t * pool)3224 fs_apply_text(svn_stream_t **contents_p,
3225 svn_fs_root_t *root,
3226 const char *path,
3227 svn_checksum_t *result_checksum,
3228 apr_pool_t *pool)
3229 {
3230 struct text_baton_t *tb = apr_pcalloc(pool, sizeof(*tb));
3231
3232 tb->root = root;
3233 tb->path = svn_fs__canonicalize_abspath(path, pool);
3234 tb->pool = pool;
3235 tb->result_checksum = svn_checksum_dup(result_checksum, pool);
3236
3237 SVN_ERR(apply_text(tb, pool));
3238
3239 *contents_p = tb->stream;
3240 return SVN_NO_ERROR;
3241 }
3242
3243 /* --- End machinery for svn_fs_apply_text() --- */
3244
3245
3246 /* Check if the contents of PATH1 under ROOT1 are different from the
3247 contents of PATH2 under ROOT2. If they are different set
3248 *CHANGED_P to TRUE, otherwise set it to FALSE. */
3249 static svn_error_t *
fs_contents_changed(svn_boolean_t * changed_p,svn_fs_root_t * root1,const char * path1,svn_fs_root_t * root2,const char * path2,svn_boolean_t strict,apr_pool_t * pool)3250 fs_contents_changed(svn_boolean_t *changed_p,
3251 svn_fs_root_t *root1,
3252 const char *path1,
3253 svn_fs_root_t *root2,
3254 const char *path2,
3255 svn_boolean_t strict,
3256 apr_pool_t *pool)
3257 {
3258 dag_node_t *node1, *node2;
3259
3260 /* Check that roots are in the same fs. */
3261 if (root1->fs != root2->fs)
3262 return svn_error_create
3263 (SVN_ERR_FS_GENERAL, NULL,
3264 _("Cannot compare file contents between two different filesystems"));
3265
3266 SVN_ERR(get_dag(&node1, root1, path1, pool));
3267 /* Make sure that path is file. */
3268 if (svn_fs_fs__dag_node_kind(node1) != svn_node_file)
3269 return svn_error_createf
3270 (SVN_ERR_FS_NOT_FILE, NULL, _("'%s' is not a file"), path1);
3271
3272 SVN_ERR(get_dag(&node2, root2, path2, pool));
3273 /* Make sure that path is file. */
3274 if (svn_fs_fs__dag_node_kind(node2) != svn_node_file)
3275 return svn_error_createf
3276 (SVN_ERR_FS_NOT_FILE, NULL, _("'%s' is not a file"), path2);
3277
3278 return svn_fs_fs__dag_things_different(NULL, changed_p,
3279 node1, node2, strict, pool);
3280 }
3281
3282
3283
3284 /* Public interface to computing file text deltas. */
3285
3286 static svn_error_t *
fs_get_file_delta_stream(svn_txdelta_stream_t ** stream_p,svn_fs_root_t * source_root,const char * source_path,svn_fs_root_t * target_root,const char * target_path,apr_pool_t * pool)3287 fs_get_file_delta_stream(svn_txdelta_stream_t **stream_p,
3288 svn_fs_root_t *source_root,
3289 const char *source_path,
3290 svn_fs_root_t *target_root,
3291 const char *target_path,
3292 apr_pool_t *pool)
3293 {
3294 dag_node_t *source_node, *target_node;
3295
3296 if (source_root && source_path)
3297 SVN_ERR(get_dag(&source_node, source_root, source_path, pool));
3298 else
3299 source_node = NULL;
3300 SVN_ERR(get_dag(&target_node, target_root, target_path, pool));
3301
3302 /* Create a delta stream that turns the source into the target. */
3303 return svn_fs_fs__dag_get_file_delta_stream(stream_p, source_node,
3304 target_node, pool);
3305 }
3306
3307
3308
3309 /* Finding Changes */
3310
3311 /* Set *CHANGED_PATHS_P to a newly allocated hash containing
3312 descriptions of the paths changed under ROOT. The hash is keyed
3313 with const char * paths and has svn_fs_path_change2_t * values. Use
3314 POOL for all allocations. */
3315 static svn_error_t *
fs_paths_changed(apr_hash_t ** changed_paths_p,svn_fs_root_t * root,apr_pool_t * pool)3316 fs_paths_changed(apr_hash_t **changed_paths_p,
3317 svn_fs_root_t *root,
3318 apr_pool_t *pool)
3319 {
3320 if (root->is_txn_root)
3321 return svn_fs_fs__txn_changes_fetch(changed_paths_p, root->fs,
3322 root_txn_id(root), pool);
3323 else
3324 return svn_fs_fs__paths_changed(changed_paths_p, root->fs, root->rev,
3325 pool);
3326 }
3327
3328
3329 /* Copy the contents of ENTRY at PATH with LEN to OUTPUT. */
3330 static void
convert_path_change(svn_fs_path_change3_t * output,const char * path,size_t path_len,svn_fs_path_change2_t * entry)3331 convert_path_change(svn_fs_path_change3_t *output,
3332 const char *path,
3333 size_t path_len,
3334 svn_fs_path_change2_t *entry)
3335 {
3336 output->path.data = path;
3337 output->path.len = path_len;
3338 output->change_kind = entry->change_kind;
3339 output->node_kind = entry->node_kind;
3340 output->text_mod = entry->text_mod;
3341 output->prop_mod = entry->prop_mod;
3342 output->mergeinfo_mod = entry->mergeinfo_mod;
3343 output->copyfrom_known = entry->copyfrom_known;
3344 output->copyfrom_rev = entry->copyfrom_rev;
3345 output->copyfrom_path = entry->copyfrom_path;
3346 }
3347
3348 /* FSAP data structure for in-txn changes list iterators. */
3349 typedef struct fs_txn_changes_iterator_data_t
3350 {
3351 /* Current iterator position. */
3352 apr_hash_index_t *hi;
3353
3354 /* For efficiency such that we don't need to dynamically allocate
3355 yet another copy of that data. */
3356 svn_fs_path_change3_t change;
3357 } fs_txn_changes_iterator_data_t;
3358
3359 /* Implement changes_iterator_vtable_t.get for in-txn change lists. */
3360 static svn_error_t *
fs_txn_changes_iterator_get(svn_fs_path_change3_t ** change,svn_fs_path_change_iterator_t * iterator)3361 fs_txn_changes_iterator_get(svn_fs_path_change3_t **change,
3362 svn_fs_path_change_iterator_t *iterator)
3363 {
3364 fs_txn_changes_iterator_data_t *data = iterator->fsap_data;
3365
3366 if (data->hi)
3367 {
3368 const void *key;
3369 apr_ssize_t length;
3370 void *value;
3371 apr_hash_this(data->hi, &key, &length, &value);
3372
3373 convert_path_change(&data->change, key, length, value);
3374
3375 *change = &data->change;
3376 data->hi = apr_hash_next(data->hi);
3377 }
3378 else
3379 {
3380 *change = NULL;
3381 }
3382
3383 return SVN_NO_ERROR;
3384 }
3385
3386 static changes_iterator_vtable_t txn_changes_iterator_vtable =
3387 {
3388 fs_txn_changes_iterator_get
3389 };
3390
3391 /* FSAP data structure for in-revision changes list iterators. */
3392 typedef struct fs_revision_changes_iterator_data_t
3393 {
3394 /* Context that tells the lower layers from where to fetch the next
3395 block of changes. */
3396 svn_fs_fs__changes_context_t *context;
3397
3398 /* Changes to send. */
3399 apr_array_header_t *changes;
3400
3401 /* Current indexes within CHANGES. */
3402 int idx;
3403
3404 /* For efficiency such that we don't need to dynamically allocate
3405 yet another copy of that data. */
3406 svn_fs_path_change3_t change;
3407
3408 /* A cleanable scratch pool in case we need one.
3409 No further sub-pool creation necessary. */
3410 apr_pool_t *scratch_pool;
3411 } fs_revision_changes_iterator_data_t;
3412
3413 /* Implement changes_iterator_vtable_t.get for in-revision change lists. */
3414 static svn_error_t *
fs_revision_changes_iterator_get(svn_fs_path_change3_t ** change,svn_fs_path_change_iterator_t * iterator)3415 fs_revision_changes_iterator_get(svn_fs_path_change3_t **change,
3416 svn_fs_path_change_iterator_t *iterator)
3417 {
3418 fs_revision_changes_iterator_data_t *data = iterator->fsap_data;
3419
3420 /* If we exhausted our block of changes and did not reach the end of the
3421 list, yet, fetch the next block. Note that that block may be empty. */
3422 if ((data->idx >= data->changes->nelts) && !data->context->eol)
3423 {
3424 apr_pool_t *changes_pool = data->changes->pool;
3425
3426 /* Drop old changes block, read new block. */
3427 svn_pool_clear(changes_pool);
3428 SVN_ERR(svn_fs_fs__get_changes(&data->changes, data->context,
3429 changes_pool, data->scratch_pool));
3430 data->idx = 0;
3431
3432 /* Immediately release any temporary data. */
3433 svn_pool_clear(data->scratch_pool);
3434 }
3435
3436 if (data->idx < data->changes->nelts)
3437 {
3438 change_t *entry = APR_ARRAY_IDX(data->changes, data->idx, change_t *);
3439 convert_path_change(&data->change, entry->path.data, entry->path.len,
3440 &entry->info);
3441
3442 *change = &data->change;
3443 ++data->idx;
3444 }
3445 else
3446 {
3447 *change = NULL;
3448 }
3449
3450 return SVN_NO_ERROR;
3451 }
3452
3453 static changes_iterator_vtable_t rev_changes_iterator_vtable =
3454 {
3455 fs_revision_changes_iterator_get
3456 };
3457
3458 static svn_error_t *
fs_report_changes(svn_fs_path_change_iterator_t ** iterator,svn_fs_root_t * root,apr_pool_t * result_pool,apr_pool_t * scratch_pool)3459 fs_report_changes(svn_fs_path_change_iterator_t **iterator,
3460 svn_fs_root_t *root,
3461 apr_pool_t *result_pool,
3462 apr_pool_t *scratch_pool)
3463 {
3464 svn_fs_path_change_iterator_t *result = apr_pcalloc(result_pool,
3465 sizeof(*result));
3466 if (root->is_txn_root)
3467 {
3468 fs_txn_changes_iterator_data_t *data = apr_pcalloc(result_pool,
3469 sizeof(*data));
3470 apr_hash_t *changed_paths;
3471 SVN_ERR(svn_fs_fs__txn_changes_fetch(&changed_paths, root->fs,
3472 root_txn_id(root), result_pool));
3473
3474 data->hi = apr_hash_first(result_pool, changed_paths);
3475 result->fsap_data = data;
3476 result->vtable = &txn_changes_iterator_vtable;
3477 }
3478 else
3479 {
3480 /* The block of changes that we retrieve need to live in a separately
3481 cleanable pool. */
3482 apr_pool_t *changes_pool = svn_pool_create(result_pool);
3483
3484 /* Our iteration context info. */
3485 fs_revision_changes_iterator_data_t *data = apr_pcalloc(result_pool,
3486 sizeof(*data));
3487
3488 /* This pool must remain valid as long as ITERATOR lives but will
3489 be used only for temporary allocations and will be cleaned up
3490 frequently. So, this must be a sub-pool of RESULT_POOL. */
3491 data->scratch_pool = svn_pool_create(result_pool);
3492
3493 /* Fetch the first block of data. */
3494 SVN_ERR(svn_fs_fs__create_changes_context(&data->context,
3495 root->fs, root->rev,
3496 result_pool));
3497 SVN_ERR(svn_fs_fs__get_changes(&data->changes, data->context,
3498 changes_pool, scratch_pool));
3499
3500 /* Return the fully initialized object. */
3501 result->fsap_data = data;
3502 result->vtable = &rev_changes_iterator_vtable;
3503 }
3504
3505 *iterator = result;
3506
3507 return SVN_NO_ERROR;
3508 }
3509
3510
3511 /* Our coolio opaque history object. */
3512 typedef struct fs_history_data_t
3513 {
3514 /* filesystem object */
3515 svn_fs_t *fs;
3516
3517 /* path and revision of historical location */
3518 const char *path;
3519 svn_revnum_t revision;
3520
3521 /* internal-use hints about where to resume the history search. */
3522 const char *path_hint;
3523 svn_revnum_t rev_hint;
3524
3525 /* FALSE until the first call to svn_fs_history_prev(). */
3526 svn_boolean_t is_interesting;
3527
3528 /* If not SVN_INVALID_REVISION, we know that the next copy operation
3529 is at this revision. */
3530 svn_revnum_t next_copy;
3531
3532 /* If not NULL, this is the noderev ID of PATH@REVISION. */
3533 const svn_fs_id_t *current_id;
3534
3535 } fs_history_data_t;
3536
3537 static svn_fs_history_t *
3538 assemble_history(svn_fs_t *fs,
3539 const char *path,
3540 svn_revnum_t revision,
3541 svn_boolean_t is_interesting,
3542 const char *path_hint,
3543 svn_revnum_t rev_hint,
3544 svn_revnum_t next_copy,
3545 const svn_fs_id_t *current_id,
3546 apr_pool_t *pool);
3547
3548
3549 /* Set *HISTORY_P to an opaque node history object which represents
3550 PATH under ROOT. ROOT must be a revision root. Use POOL for all
3551 allocations. */
3552 static svn_error_t *
fs_node_history(svn_fs_history_t ** history_p,svn_fs_root_t * root,const char * path,apr_pool_t * result_pool,apr_pool_t * scratch_pool)3553 fs_node_history(svn_fs_history_t **history_p,
3554 svn_fs_root_t *root,
3555 const char *path,
3556 apr_pool_t *result_pool,
3557 apr_pool_t *scratch_pool)
3558 {
3559 svn_node_kind_t kind;
3560
3561 /* We require a revision root. */
3562 if (root->is_txn_root)
3563 return svn_error_create(SVN_ERR_FS_NOT_REVISION_ROOT, NULL, NULL);
3564
3565 /* And we require that the path exist in the root. */
3566 SVN_ERR(svn_fs_fs__check_path(&kind, root, path, scratch_pool));
3567 if (kind == svn_node_none)
3568 return SVN_FS__NOT_FOUND(root, path);
3569
3570 /* Okay, all seems well. Build our history object and return it. */
3571 *history_p = assemble_history(root->fs, path, root->rev, FALSE, NULL,
3572 SVN_INVALID_REVNUM, SVN_INVALID_REVNUM,
3573 NULL, result_pool);
3574 return SVN_NO_ERROR;
3575 }
3576
3577 /* Find the youngest copyroot for path PARENT_PATH or its parents in
3578 filesystem FS, and store the copyroot in *REV_P and *PATH_P.
3579 Perform all allocations in POOL. */
3580 static svn_error_t *
find_youngest_copyroot(svn_revnum_t * rev_p,const char ** path_p,svn_fs_t * fs,parent_path_t * parent_path,apr_pool_t * pool)3581 find_youngest_copyroot(svn_revnum_t *rev_p,
3582 const char **path_p,
3583 svn_fs_t *fs,
3584 parent_path_t *parent_path,
3585 apr_pool_t *pool)
3586 {
3587 svn_revnum_t rev_mine;
3588 svn_revnum_t rev_parent = SVN_INVALID_REVNUM;
3589 const char *path_mine;
3590 const char *path_parent = NULL;
3591
3592 /* First find our parent's youngest copyroot. */
3593 if (parent_path->parent)
3594 SVN_ERR(find_youngest_copyroot(&rev_parent, &path_parent, fs,
3595 parent_path->parent, pool));
3596
3597 /* Find our copyroot. */
3598 SVN_ERR(svn_fs_fs__dag_get_copyroot(&rev_mine, &path_mine,
3599 parent_path->node));
3600
3601 /* If a parent and child were copied to in the same revision, prefer
3602 the child copy target, since it is the copy relevant to the
3603 history of the child. */
3604 if (rev_mine >= rev_parent)
3605 {
3606 *rev_p = rev_mine;
3607 *path_p = path_mine;
3608 }
3609 else
3610 {
3611 *rev_p = rev_parent;
3612 *path_p = path_parent;
3613 }
3614
3615 return SVN_NO_ERROR;
3616 }
3617
3618
fs_closest_copy(svn_fs_root_t ** root_p,const char ** path_p,svn_fs_root_t * root,const char * path,apr_pool_t * pool)3619 static svn_error_t *fs_closest_copy(svn_fs_root_t **root_p,
3620 const char **path_p,
3621 svn_fs_root_t *root,
3622 const char *path,
3623 apr_pool_t *pool)
3624 {
3625 svn_fs_t *fs = root->fs;
3626 parent_path_t *parent_path, *copy_dst_parent_path;
3627 svn_revnum_t copy_dst_rev, created_rev;
3628 const char *copy_dst_path;
3629 svn_fs_root_t *copy_dst_root;
3630 dag_node_t *copy_dst_node;
3631
3632 /* Initialize return values. */
3633 *root_p = NULL;
3634 *path_p = NULL;
3635
3636 path = svn_fs__canonicalize_abspath(path, pool);
3637 SVN_ERR(open_path(&parent_path, root, path, 0, FALSE, pool));
3638
3639 /* Find the youngest copyroot in the path of this node-rev, which
3640 will indicate the target of the innermost copy affecting the
3641 node-rev. */
3642 SVN_ERR(find_youngest_copyroot(©_dst_rev, ©_dst_path,
3643 fs, parent_path, pool));
3644 if (copy_dst_rev == 0) /* There are no copies affecting this node-rev. */
3645 return SVN_NO_ERROR;
3646
3647 /* It is possible that this node was created from scratch at some
3648 revision between COPY_DST_REV and REV. Make sure that PATH
3649 exists as of COPY_DST_REV and is related to this node-rev. */
3650 SVN_ERR(svn_fs_fs__revision_root(©_dst_root, fs, copy_dst_rev, pool));
3651 SVN_ERR(open_path(©_dst_parent_path, copy_dst_root, path,
3652 open_path_node_only | open_path_allow_null, FALSE, pool));
3653 if (copy_dst_parent_path == NULL)
3654 return SVN_NO_ERROR;
3655
3656 copy_dst_node = copy_dst_parent_path->node;
3657 if (! svn_fs_fs__id_check_related(svn_fs_fs__dag_get_id(copy_dst_node),
3658 svn_fs_fs__dag_get_id(parent_path->node)))
3659 return SVN_NO_ERROR;
3660
3661 /* One final check must be done here. If you copy a directory and
3662 create a new entity somewhere beneath that directory in the same
3663 txn, then we can't claim that the copy affected the new entity.
3664 For example, if you do:
3665
3666 copy dir1 dir2
3667 create dir2/new-thing
3668 commit
3669
3670 then dir2/new-thing was not affected by the copy of dir1 to dir2.
3671 We detect this situation by asking if PATH@COPY_DST_REV's
3672 created-rev is COPY_DST_REV, and that node-revision has no
3673 predecessors, then there is no relevant closest copy.
3674 */
3675 SVN_ERR(svn_fs_fs__dag_get_revision(&created_rev, copy_dst_node, pool));
3676 if (created_rev == copy_dst_rev)
3677 {
3678 const svn_fs_id_t *pred;
3679 SVN_ERR(svn_fs_fs__dag_get_predecessor_id(&pred, copy_dst_node));
3680 if (! pred)
3681 return SVN_NO_ERROR;
3682 }
3683
3684 /* The copy destination checks out. Return it. */
3685 *root_p = copy_dst_root;
3686 *path_p = copy_dst_path;
3687 return SVN_NO_ERROR;
3688 }
3689
3690
3691 /* Set *PREV_PATH and *PREV_REV to the path and revision which
3692 represent the location at which PATH in FS was located immediately
3693 prior to REVISION iff there was a copy operation (to PATH or one of
3694 its parent directories) between that previous location and
3695 PATH@REVISION.
3696
3697 If there was no such copy operation in that portion of PATH's
3698 history, set *PREV_PATH to NULL and *PREV_REV to SVN_INVALID_REVNUM. */
3699 static svn_error_t *
prev_location(const char ** prev_path,svn_revnum_t * prev_rev,svn_fs_t * fs,svn_fs_root_t * root,const char * path,apr_pool_t * pool)3700 prev_location(const char **prev_path,
3701 svn_revnum_t *prev_rev,
3702 svn_fs_t *fs,
3703 svn_fs_root_t *root,
3704 const char *path,
3705 apr_pool_t *pool)
3706 {
3707 const char *copy_path, *copy_src_path, *remainder_path;
3708 svn_fs_root_t *copy_root;
3709 svn_revnum_t copy_src_rev;
3710
3711 /* Ask about the most recent copy which affected PATH@REVISION. If
3712 there was no such copy, we're done. */
3713 SVN_ERR(fs_closest_copy(©_root, ©_path, root, path, pool));
3714 if (! copy_root)
3715 {
3716 *prev_rev = SVN_INVALID_REVNUM;
3717 *prev_path = NULL;
3718 return SVN_NO_ERROR;
3719 }
3720
3721 /* Ultimately, it's not the path of the closest copy's source that
3722 we care about -- it's our own path's location in the copy source
3723 revision. So we'll tack the relative path that expresses the
3724 difference between the copy destination and our path in the copy
3725 revision onto the copy source path to determine this information.
3726
3727 In other words, if our path is "/branches/my-branch/foo/bar", and
3728 we know that the closest relevant copy was a copy of "/trunk" to
3729 "/branches/my-branch", then that relative path under the copy
3730 destination is "/foo/bar". Tacking that onto the copy source
3731 path tells us that our path was located at "/trunk/foo/bar"
3732 before the copy.
3733 */
3734 SVN_ERR(fs_copied_from(©_src_rev, ©_src_path,
3735 copy_root, copy_path, pool));
3736 remainder_path = svn_fspath__skip_ancestor(copy_path, path);
3737 *prev_path = svn_fspath__join(copy_src_path, remainder_path, pool);
3738 *prev_rev = copy_src_rev;
3739 return SVN_NO_ERROR;
3740 }
3741
3742
3743 static svn_error_t *
fs_node_origin_rev(svn_revnum_t * revision,svn_fs_root_t * root,const char * path,apr_pool_t * pool)3744 fs_node_origin_rev(svn_revnum_t *revision,
3745 svn_fs_root_t *root,
3746 const char *path,
3747 apr_pool_t *pool)
3748 {
3749 svn_fs_t *fs = root->fs;
3750 const svn_fs_id_t *given_noderev_id, *cached_origin_id;
3751 const svn_fs_fs__id_part_t *node_id;
3752
3753 path = svn_fs__canonicalize_abspath(path, pool);
3754
3755 /* Check the cache first. */
3756 SVN_ERR(svn_fs_fs__node_id(&given_noderev_id, root, path, pool));
3757 node_id = svn_fs_fs__id_node_id(given_noderev_id);
3758
3759 /* Is it a brand new uncommitted node or a new-style node ID?
3760 * (committed old-style nodes will have a 0 revision value;
3761 * rev 0, number 0 is rev 0 root node). Note that != 0 includes
3762 * SVN_INVALID_REVNUM for uncommitted nodes. */
3763 if (node_id->revision != 0 || node_id->number == 0)
3764 {
3765 *revision = node_id->revision;
3766 return SVN_NO_ERROR;
3767 }
3768
3769 /* OK, it's an old-style ID? Maybe it's cached. */
3770 SVN_ERR(svn_fs_fs__get_node_origin(&cached_origin_id,
3771 fs,
3772 node_id,
3773 pool));
3774 if (cached_origin_id != NULL)
3775 {
3776 *revision = svn_fs_fs__id_rev(cached_origin_id);
3777 return SVN_NO_ERROR;
3778 }
3779
3780 {
3781 /* Ah well, the answer isn't in the ID itself or in the cache.
3782 Let's actually calculate it, then. */
3783 svn_fs_root_t *curroot = root;
3784 apr_pool_t *subpool = svn_pool_create(pool);
3785 apr_pool_t *predidpool = svn_pool_create(pool);
3786 svn_stringbuf_t *lastpath = svn_stringbuf_create(path, pool);
3787 svn_revnum_t lastrev = SVN_INVALID_REVNUM;
3788 dag_node_t *node;
3789 const svn_fs_id_t *pred_id;
3790
3791 /* Walk the closest-copy chain back to the first copy in our history.
3792
3793 NOTE: We merely *assume* that this is faster than walking the
3794 predecessor chain, because we *assume* that copies of parent
3795 directories happen less often than modifications to a given item. */
3796 while (1)
3797 {
3798 svn_revnum_t currev;
3799 const char *curpath = lastpath->data;
3800
3801 svn_pool_clear(subpool);
3802
3803 /* Get a root pointing to LASTREV. (The first time around,
3804 LASTREV is invalid, but that's cool because CURROOT is
3805 already initialized.) */
3806 if (SVN_IS_VALID_REVNUM(lastrev))
3807 SVN_ERR(svn_fs_fs__revision_root(&curroot, fs, lastrev, subpool));
3808
3809 /* Find the previous location using the closest-copy shortcut. */
3810 SVN_ERR(prev_location(&curpath, &currev, fs, curroot, curpath,
3811 subpool));
3812 if (! curpath)
3813 break;
3814
3815 /* Update our LASTPATH and LASTREV variables (which survive
3816 SUBPOOL). */
3817 svn_stringbuf_set(lastpath, curpath);
3818 lastrev = currev;
3819 }
3820
3821 /* Walk the predecessor links back to origin. */
3822 SVN_ERR(svn_fs_fs__node_id(&pred_id, curroot, lastpath->data, predidpool));
3823 do
3824 {
3825 svn_pool_clear(subpool);
3826 SVN_ERR(svn_fs_fs__dag_get_node(&node, fs, pred_id, subpool));
3827
3828 /* Why not just fetch the predecessor ID in PREDIDPOOL?
3829 Because svn_fs_fs__dag_get_predecessor_id() doesn't
3830 necessarily honor the passed-in pool, and might return a
3831 value cached in the node (which is allocated in
3832 SUBPOOL... maybe). */
3833 svn_pool_clear(predidpool);
3834 SVN_ERR(svn_fs_fs__dag_get_predecessor_id(&pred_id, node));
3835 pred_id = pred_id ? svn_fs_fs__id_copy(pred_id, predidpool) : NULL;
3836 }
3837 while (pred_id);
3838
3839 /* When we get here, NODE should be the first node-revision in our
3840 chain. */
3841 SVN_ERR(svn_fs_fs__dag_get_revision(revision, node, pool));
3842
3843 /* Wow, I don't want to have to do all that again. Let's cache
3844 the result. */
3845 if (node_id->revision != SVN_INVALID_REVNUM)
3846 SVN_ERR(svn_fs_fs__set_node_origin(fs, node_id,
3847 svn_fs_fs__dag_get_id(node), pool));
3848
3849 svn_pool_destroy(subpool);
3850 svn_pool_destroy(predidpool);
3851 return SVN_NO_ERROR;
3852 }
3853 }
3854
3855
3856 static svn_error_t *
history_prev(svn_fs_history_t ** prev_history,svn_fs_history_t * history,svn_boolean_t cross_copies,apr_pool_t * result_pool,apr_pool_t * scratch_pool)3857 history_prev(svn_fs_history_t **prev_history,
3858 svn_fs_history_t *history,
3859 svn_boolean_t cross_copies,
3860 apr_pool_t *result_pool,
3861 apr_pool_t *scratch_pool)
3862 {
3863 fs_history_data_t *fhd = history->fsap_data;
3864 const char *commit_path, *src_path, *path = fhd->path;
3865 svn_revnum_t commit_rev, src_rev, dst_rev;
3866 svn_revnum_t revision = fhd->revision;
3867 svn_fs_t *fs = fhd->fs;
3868 parent_path_t *parent_path;
3869 dag_node_t *node;
3870 svn_fs_root_t *root;
3871 svn_boolean_t reported = fhd->is_interesting;
3872 svn_revnum_t copyroot_rev;
3873 const char *copyroot_path;
3874 const svn_fs_id_t *pred_id = NULL;
3875
3876 /* Initialize our return value. */
3877 *prev_history = NULL;
3878
3879 /* When following history, there tend to be long sections of linear
3880 history where there are no copies at PATH or its parents. Within
3881 these sections, we only need to follow the node history. */
3882 if ( SVN_IS_VALID_REVNUM(fhd->next_copy)
3883 && revision > fhd->next_copy
3884 && fhd->current_id)
3885 {
3886 /* We know the last reported node (CURRENT_ID) and the NEXT_COPY
3887 revision is somewhat further in the past. */
3888 node_revision_t *noderev;
3889 assert(reported);
3890
3891 /* Get the previous node change. If there is none, then we already
3892 reported the initial addition and this history traversal is done. */
3893 SVN_ERR(svn_fs_fs__get_node_revision(&noderev, fs, fhd->current_id,
3894 scratch_pool, scratch_pool));
3895 if (! noderev->predecessor_id)
3896 return SVN_NO_ERROR;
3897
3898 /* If the previous node change is younger than the next copy, it is
3899 part of the linear history section. */
3900 commit_rev = svn_fs_fs__id_rev(noderev->predecessor_id);
3901 if (commit_rev > fhd->next_copy)
3902 {
3903 /* Within the linear history, simply report all node changes and
3904 continue with the respective predecessor. */
3905 *prev_history = assemble_history(fs, noderev->created_path,
3906 commit_rev, TRUE, NULL,
3907 SVN_INVALID_REVNUM,
3908 fhd->next_copy,
3909 noderev->predecessor_id,
3910 result_pool);
3911
3912 return SVN_NO_ERROR;
3913 }
3914
3915 /* We hit a copy. Fall back to the standard code path. */
3916 }
3917
3918 /* If our last history report left us hints about where to pickup
3919 the chase, then our last report was on the destination of a
3920 copy. If we are crossing copies, start from those locations,
3921 otherwise, we're all done here. */
3922 if (fhd->path_hint && SVN_IS_VALID_REVNUM(fhd->rev_hint))
3923 {
3924 reported = FALSE;
3925 if (! cross_copies)
3926 return SVN_NO_ERROR;
3927 path = fhd->path_hint;
3928 revision = fhd->rev_hint;
3929 }
3930
3931 /* Construct a ROOT for the current revision. */
3932 SVN_ERR(svn_fs_fs__revision_root(&root, fs, revision, scratch_pool));
3933
3934 /* Open PATH/REVISION, and get its node and a bunch of other
3935 goodies. */
3936 SVN_ERR(open_path(&parent_path, root, path, 0, FALSE, scratch_pool));
3937 node = parent_path->node;
3938 commit_path = svn_fs_fs__dag_get_created_path(node);
3939 SVN_ERR(svn_fs_fs__dag_get_revision(&commit_rev, node, scratch_pool));
3940
3941 /* The Subversion filesystem is written in such a way that a given
3942 line of history may have at most one interesting history point
3943 per filesystem revision. Either that node was edited (and
3944 possibly copied), or it was copied but not edited. And a copy
3945 source cannot be from the same revision as its destination. So,
3946 if our history revision matches its node's commit revision, we
3947 know that ... */
3948 if (revision == commit_rev)
3949 {
3950 if (! reported)
3951 {
3952 /* ... we either have not yet reported on this revision (and
3953 need now to do so) ... */
3954 *prev_history = assemble_history(fs, commit_path,
3955 commit_rev, TRUE, NULL,
3956 SVN_INVALID_REVNUM,
3957 SVN_INVALID_REVNUM, NULL,
3958 result_pool);
3959 return SVN_NO_ERROR;
3960 }
3961 else
3962 {
3963 /* ... or we *have* reported on this revision, and must now
3964 progress toward this node's predecessor (unless there is
3965 no predecessor, in which case we're all done!). */
3966 SVN_ERR(svn_fs_fs__dag_get_predecessor_id(&pred_id, node));
3967 if (! pred_id)
3968 return SVN_NO_ERROR;
3969
3970 /* Replace NODE and friends with the information from its
3971 predecessor. */
3972 SVN_ERR(svn_fs_fs__dag_get_node(&node, fs, pred_id, scratch_pool));
3973 commit_path = svn_fs_fs__dag_get_created_path(node);
3974 SVN_ERR(svn_fs_fs__dag_get_revision(&commit_rev, node, scratch_pool));
3975 }
3976 }
3977
3978 /* Find the youngest copyroot in the path of this node, including
3979 itself. */
3980 SVN_ERR(find_youngest_copyroot(©root_rev, ©root_path, fs,
3981 parent_path, scratch_pool));
3982
3983 /* Initialize some state variables. */
3984 src_path = NULL;
3985 src_rev = SVN_INVALID_REVNUM;
3986 dst_rev = SVN_INVALID_REVNUM;
3987
3988 if (copyroot_rev > commit_rev)
3989 {
3990 const char *remainder_path;
3991 const char *copy_dst, *copy_src;
3992 svn_fs_root_t *copyroot_root;
3993
3994 SVN_ERR(svn_fs_fs__revision_root(©root_root, fs, copyroot_rev,
3995 scratch_pool));
3996 SVN_ERR(get_dag(&node, copyroot_root, copyroot_path, scratch_pool));
3997 copy_dst = svn_fs_fs__dag_get_created_path(node);
3998
3999 /* If our current path was the very destination of the copy,
4000 then our new current path will be the copy source. If our
4001 current path was instead the *child* of the destination of
4002 the copy, then figure out its previous location by taking its
4003 path relative to the copy destination and appending that to
4004 the copy source. Finally, if our current path doesn't meet
4005 one of these other criteria ... ### for now just fallback to
4006 the old copy hunt algorithm. */
4007 remainder_path = svn_fspath__skip_ancestor(copy_dst, path);
4008
4009 if (remainder_path)
4010 {
4011 /* If we get here, then our current path is the destination
4012 of, or the child of the destination of, a copy. Fill
4013 in the return values and get outta here. */
4014 SVN_ERR(svn_fs_fs__dag_get_copyfrom_rev(&src_rev, node));
4015 SVN_ERR(svn_fs_fs__dag_get_copyfrom_path(©_src, node));
4016
4017 dst_rev = copyroot_rev;
4018 src_path = svn_fspath__join(copy_src, remainder_path, scratch_pool);
4019 }
4020 }
4021
4022 /* If we calculated a copy source path and revision, we'll make a
4023 'copy-style' history object. */
4024 if (src_path && SVN_IS_VALID_REVNUM(src_rev))
4025 {
4026 svn_boolean_t retry = FALSE;
4027
4028 /* It's possible for us to find a copy location that is the same
4029 as the history point we've just reported. If that happens,
4030 we simply need to take another trip through this history
4031 search. */
4032 if ((dst_rev == revision) && reported)
4033 retry = TRUE;
4034
4035 *prev_history = assemble_history(fs, path, dst_rev, ! retry,
4036 src_path, src_rev,
4037 SVN_INVALID_REVNUM, NULL,
4038 result_pool);
4039 }
4040 else
4041 {
4042 /* We know the next copy revision. If we are not at the copy rev
4043 itself, we will also know the predecessor node ID and the next
4044 invocation will use the optimized "linear history" code path. */
4045 *prev_history = assemble_history(fs, commit_path, commit_rev, TRUE,
4046 NULL, SVN_INVALID_REVNUM,
4047 copyroot_rev, pred_id, result_pool);
4048 }
4049
4050 return SVN_NO_ERROR;
4051 }
4052
4053
4054 /* Implement svn_fs_history_prev, set *PREV_HISTORY_P to a new
4055 svn_fs_history_t object that represents the predecessory of
4056 HISTORY. If CROSS_COPIES is true, *PREV_HISTORY_P may be related
4057 only through a copy operation. Perform all allocations in POOL. */
4058 static svn_error_t *
fs_history_prev(svn_fs_history_t ** prev_history_p,svn_fs_history_t * history,svn_boolean_t cross_copies,apr_pool_t * result_pool,apr_pool_t * scratch_pool)4059 fs_history_prev(svn_fs_history_t **prev_history_p,
4060 svn_fs_history_t *history,
4061 svn_boolean_t cross_copies,
4062 apr_pool_t *result_pool,
4063 apr_pool_t *scratch_pool)
4064 {
4065 svn_fs_history_t *prev_history = NULL;
4066 fs_history_data_t *fhd = history->fsap_data;
4067 svn_fs_t *fs = fhd->fs;
4068
4069 /* Special case: the root directory changes in every single
4070 revision, no exceptions. And, the root can't be the target (or
4071 child of a target -- duh) of a copy. So, if that's our path,
4072 then we need only decrement our revision by 1, and there you go. */
4073 if (strcmp(fhd->path, "/") == 0)
4074 {
4075 if (! fhd->is_interesting)
4076 prev_history = assemble_history(fs, "/", fhd->revision,
4077 1, NULL, SVN_INVALID_REVNUM,
4078 SVN_INVALID_REVNUM, NULL,
4079 result_pool);
4080 else if (fhd->revision > 0)
4081 prev_history = assemble_history(fs, "/", fhd->revision - 1,
4082 1, NULL, SVN_INVALID_REVNUM,
4083 SVN_INVALID_REVNUM, NULL,
4084 result_pool);
4085 }
4086 else
4087 {
4088 apr_pool_t *iterpool = svn_pool_create(scratch_pool);
4089 prev_history = history;
4090
4091 while (1)
4092 {
4093 svn_pool_clear(iterpool);
4094 SVN_ERR(history_prev(&prev_history, prev_history, cross_copies,
4095 result_pool, iterpool));
4096
4097 if (! prev_history)
4098 break;
4099 fhd = prev_history->fsap_data;
4100 if (fhd->is_interesting)
4101 break;
4102 }
4103
4104 svn_pool_destroy(iterpool);
4105 }
4106
4107 *prev_history_p = prev_history;
4108 return SVN_NO_ERROR;
4109 }
4110
4111
4112 /* Set *PATH and *REVISION to the path and revision for the HISTORY
4113 object. Use POOL for all allocations. */
4114 static svn_error_t *
fs_history_location(const char ** path,svn_revnum_t * revision,svn_fs_history_t * history,apr_pool_t * pool)4115 fs_history_location(const char **path,
4116 svn_revnum_t *revision,
4117 svn_fs_history_t *history,
4118 apr_pool_t *pool)
4119 {
4120 fs_history_data_t *fhd = history->fsap_data;
4121
4122 *path = apr_pstrdup(pool, fhd->path);
4123 *revision = fhd->revision;
4124 return SVN_NO_ERROR;
4125 }
4126
4127 static history_vtable_t history_vtable = {
4128 fs_history_prev,
4129 fs_history_location
4130 };
4131
4132 /* Return a new history object (marked as "interesting") for PATH and
4133 REVISION, allocated in POOL, and with its members set to the values
4134 of the parameters provided. Note that PATH and PATH_HINT get
4135 normalized and duplicated in POOL. */
4136 static svn_fs_history_t *
assemble_history(svn_fs_t * fs,const char * path,svn_revnum_t revision,svn_boolean_t is_interesting,const char * path_hint,svn_revnum_t rev_hint,svn_revnum_t next_copy,const svn_fs_id_t * current_id,apr_pool_t * pool)4137 assemble_history(svn_fs_t *fs,
4138 const char *path,
4139 svn_revnum_t revision,
4140 svn_boolean_t is_interesting,
4141 const char *path_hint,
4142 svn_revnum_t rev_hint,
4143 svn_revnum_t next_copy,
4144 const svn_fs_id_t *current_id,
4145 apr_pool_t *pool)
4146 {
4147 svn_fs_history_t *history = apr_pcalloc(pool, sizeof(*history));
4148 fs_history_data_t *fhd = apr_pcalloc(pool, sizeof(*fhd));
4149 fhd->path = svn_fs__canonicalize_abspath(path, pool);
4150 fhd->revision = revision;
4151 fhd->is_interesting = is_interesting;
4152 fhd->path_hint = path_hint ? svn_fs__canonicalize_abspath(path_hint, pool)
4153 : NULL;
4154 fhd->rev_hint = rev_hint;
4155 fhd->next_copy = next_copy;
4156 fhd->current_id = current_id ? svn_fs_fs__id_copy(current_id, pool) : NULL;
4157 fhd->fs = fs;
4158
4159 history->vtable = &history_vtable;
4160 history->fsap_data = fhd;
4161 return history;
4162 }
4163
4164
4165 /* mergeinfo queries */
4166
4167
4168 /* DIR_DAG is a directory DAG node which has mergeinfo in its
4169 descendants. This function iterates over its children. For each
4170 child with immediate mergeinfo, call RECEIVER with it and BATON.
4171 For each child with descendants with mergeinfo, it recurses. Note
4172 that it does *not* call the action on the path for DIR_DAG itself.
4173
4174 SCRATCH_POOL is used for temporary allocations, including the mergeinfo
4175 hashes passed to actions.
4176 */
4177 static svn_error_t *
crawl_directory_dag_for_mergeinfo(svn_fs_root_t * root,const char * this_path,dag_node_t * dir_dag,svn_fs_mergeinfo_receiver_t receiver,void * baton,apr_pool_t * scratch_pool)4178 crawl_directory_dag_for_mergeinfo(svn_fs_root_t *root,
4179 const char *this_path,
4180 dag_node_t *dir_dag,
4181 svn_fs_mergeinfo_receiver_t receiver,
4182 void *baton,
4183 apr_pool_t *scratch_pool)
4184 {
4185 apr_array_header_t *entries;
4186 int i;
4187 apr_pool_t *iterpool = svn_pool_create(scratch_pool);
4188
4189 SVN_ERR(svn_fs_fs__dag_dir_entries(&entries, dir_dag, scratch_pool));
4190 for (i = 0; i < entries->nelts; ++i)
4191 {
4192 svn_fs_dirent_t *dirent = APR_ARRAY_IDX(entries, i, svn_fs_dirent_t *);
4193 const char *kid_path;
4194 dag_node_t *kid_dag;
4195 svn_boolean_t has_mergeinfo, go_down;
4196
4197 svn_pool_clear(iterpool);
4198
4199 kid_path = svn_fspath__join(this_path, dirent->name, iterpool);
4200 SVN_ERR(get_dag(&kid_dag, root, kid_path, iterpool));
4201
4202 SVN_ERR(svn_fs_fs__dag_has_mergeinfo(&has_mergeinfo, kid_dag));
4203 SVN_ERR(svn_fs_fs__dag_has_descendants_with_mergeinfo(&go_down, kid_dag));
4204
4205 if (has_mergeinfo)
4206 {
4207 /* Save this particular node's mergeinfo. */
4208 apr_hash_t *proplist;
4209 svn_mergeinfo_t kid_mergeinfo;
4210 svn_string_t *mergeinfo_string;
4211 svn_error_t *err;
4212
4213 SVN_ERR(svn_fs_fs__dag_get_proplist(&proplist, kid_dag, iterpool));
4214 mergeinfo_string = svn_hash_gets(proplist, SVN_PROP_MERGEINFO);
4215 if (!mergeinfo_string)
4216 {
4217 svn_string_t *idstr = svn_fs_fs__id_unparse(dirent->id, iterpool);
4218 return svn_error_createf
4219 (SVN_ERR_FS_CORRUPT, NULL,
4220 _("Node-revision #'%s' claims to have mergeinfo but doesn't"),
4221 idstr->data);
4222 }
4223
4224 /* Issue #3896: If a node has syntactically invalid mergeinfo, then
4225 treat it as if no mergeinfo is present rather than raising a parse
4226 error. */
4227 err = svn_mergeinfo_parse(&kid_mergeinfo,
4228 mergeinfo_string->data,
4229 iterpool);
4230 if (err)
4231 {
4232 if (err->apr_err == SVN_ERR_MERGEINFO_PARSE_ERROR)
4233 svn_error_clear(err);
4234 else
4235 return svn_error_trace(err);
4236 }
4237 else
4238 {
4239 SVN_ERR(receiver(kid_path, kid_mergeinfo, baton, iterpool));
4240 }
4241 }
4242
4243 if (go_down)
4244 SVN_ERR(crawl_directory_dag_for_mergeinfo(root,
4245 kid_path,
4246 kid_dag,
4247 receiver,
4248 baton,
4249 iterpool));
4250 }
4251
4252 svn_pool_destroy(iterpool);
4253 return SVN_NO_ERROR;
4254 }
4255
4256 /* Return the cache key as a combination of REV_ROOT->REV, the inheritance
4257 flags INHERIT and ADJUST_INHERITED_MERGEINFO, and the PATH. The result
4258 will be allocated in POOL..
4259 */
4260 static const char *
mergeinfo_cache_key(const char * path,svn_fs_root_t * rev_root,svn_mergeinfo_inheritance_t inherit,svn_boolean_t adjust_inherited_mergeinfo,apr_pool_t * pool)4261 mergeinfo_cache_key(const char *path,
4262 svn_fs_root_t *rev_root,
4263 svn_mergeinfo_inheritance_t inherit,
4264 svn_boolean_t adjust_inherited_mergeinfo,
4265 apr_pool_t *pool)
4266 {
4267 apr_int64_t number = rev_root->rev;
4268 number = number * 4
4269 + (inherit == svn_mergeinfo_nearest_ancestor ? 2 : 0)
4270 + (adjust_inherited_mergeinfo ? 1 : 0);
4271
4272 return svn_fs_fs__combine_number_and_string(number, path, pool);
4273 }
4274
4275 /* Calculates the mergeinfo for PATH under REV_ROOT using inheritance
4276 type INHERIT. Returns it in *MERGEINFO, or NULL if there is none.
4277 The result is allocated in RESULT_POOL; SCRATCH_POOL is
4278 used for temporary allocations.
4279 */
4280 static svn_error_t *
get_mergeinfo_for_path_internal(svn_mergeinfo_t * mergeinfo,svn_fs_root_t * rev_root,const char * path,svn_mergeinfo_inheritance_t inherit,svn_boolean_t adjust_inherited_mergeinfo,apr_pool_t * result_pool,apr_pool_t * scratch_pool)4281 get_mergeinfo_for_path_internal(svn_mergeinfo_t *mergeinfo,
4282 svn_fs_root_t *rev_root,
4283 const char *path,
4284 svn_mergeinfo_inheritance_t inherit,
4285 svn_boolean_t adjust_inherited_mergeinfo,
4286 apr_pool_t *result_pool,
4287 apr_pool_t *scratch_pool)
4288 {
4289 parent_path_t *parent_path, *nearest_ancestor;
4290 apr_hash_t *proplist;
4291 svn_string_t *mergeinfo_string;
4292
4293 path = svn_fs__canonicalize_abspath(path, scratch_pool);
4294
4295 SVN_ERR(open_path(&parent_path, rev_root, path, 0, FALSE, scratch_pool));
4296
4297 if (inherit == svn_mergeinfo_nearest_ancestor && ! parent_path->parent)
4298 return SVN_NO_ERROR;
4299
4300 if (inherit == svn_mergeinfo_nearest_ancestor)
4301 nearest_ancestor = parent_path->parent;
4302 else
4303 nearest_ancestor = parent_path;
4304
4305 while (TRUE)
4306 {
4307 svn_boolean_t has_mergeinfo;
4308
4309 SVN_ERR(svn_fs_fs__dag_has_mergeinfo(&has_mergeinfo,
4310 nearest_ancestor->node));
4311 if (has_mergeinfo)
4312 break;
4313
4314 /* No need to loop if we're looking for explicit mergeinfo. */
4315 if (inherit == svn_mergeinfo_explicit)
4316 {
4317 return SVN_NO_ERROR;
4318 }
4319
4320 nearest_ancestor = nearest_ancestor->parent;
4321
4322 /* Run out? There's no mergeinfo. */
4323 if (!nearest_ancestor)
4324 {
4325 return SVN_NO_ERROR;
4326 }
4327 }
4328
4329 SVN_ERR(svn_fs_fs__dag_get_proplist(&proplist, nearest_ancestor->node,
4330 scratch_pool));
4331 mergeinfo_string = svn_hash_gets(proplist, SVN_PROP_MERGEINFO);
4332 if (!mergeinfo_string)
4333 return svn_error_createf
4334 (SVN_ERR_FS_CORRUPT, NULL,
4335 _("Node-revision '%s@%ld' claims to have mergeinfo but doesn't"),
4336 parent_path_path(nearest_ancestor, scratch_pool), rev_root->rev);
4337
4338 /* Parse the mergeinfo; store the result in *MERGEINFO. */
4339 {
4340 /* Issue #3896: If a node has syntactically invalid mergeinfo, then
4341 treat it as if no mergeinfo is present rather than raising a parse
4342 error. */
4343 svn_error_t *err = svn_mergeinfo_parse(mergeinfo,
4344 mergeinfo_string->data,
4345 result_pool);
4346 if (err)
4347 {
4348 if (err->apr_err == SVN_ERR_MERGEINFO_PARSE_ERROR)
4349 {
4350 svn_error_clear(err);
4351 err = NULL;
4352 *mergeinfo = NULL;
4353 }
4354 return svn_error_trace(err);
4355 }
4356 }
4357
4358 /* If our nearest ancestor is the very path we inquired about, we
4359 can return the mergeinfo results directly. Otherwise, we're
4360 inheriting the mergeinfo, so we need to a) remove non-inheritable
4361 ranges and b) telescope the merged-from paths. */
4362 if (adjust_inherited_mergeinfo && (nearest_ancestor != parent_path))
4363 {
4364 svn_mergeinfo_t tmp_mergeinfo;
4365
4366 SVN_ERR(svn_mergeinfo_inheritable2(&tmp_mergeinfo, *mergeinfo,
4367 NULL, SVN_INVALID_REVNUM,
4368 SVN_INVALID_REVNUM, TRUE,
4369 scratch_pool, scratch_pool));
4370 SVN_ERR(svn_fs__append_to_merged_froms(mergeinfo, tmp_mergeinfo,
4371 parent_path_relpath(
4372 parent_path, nearest_ancestor,
4373 scratch_pool),
4374 result_pool));
4375 }
4376
4377 return SVN_NO_ERROR;
4378 }
4379
4380 /* Caching wrapper around get_mergeinfo_for_path_internal().
4381 */
4382 static svn_error_t *
get_mergeinfo_for_path(svn_mergeinfo_t * mergeinfo,svn_fs_root_t * rev_root,const char * path,svn_mergeinfo_inheritance_t inherit,svn_boolean_t adjust_inherited_mergeinfo,apr_pool_t * result_pool,apr_pool_t * scratch_pool)4383 get_mergeinfo_for_path(svn_mergeinfo_t *mergeinfo,
4384 svn_fs_root_t *rev_root,
4385 const char *path,
4386 svn_mergeinfo_inheritance_t inherit,
4387 svn_boolean_t adjust_inherited_mergeinfo,
4388 apr_pool_t *result_pool,
4389 apr_pool_t *scratch_pool)
4390 {
4391 fs_fs_data_t *ffd = rev_root->fs->fsap_data;
4392 const char *cache_key;
4393 svn_boolean_t found = FALSE;
4394 svn_stringbuf_t *mergeinfo_exists;
4395
4396 *mergeinfo = NULL;
4397
4398 cache_key = mergeinfo_cache_key(path, rev_root, inherit,
4399 adjust_inherited_mergeinfo, scratch_pool);
4400 if (ffd->mergeinfo_existence_cache)
4401 {
4402 SVN_ERR(svn_cache__get((void **)&mergeinfo_exists, &found,
4403 ffd->mergeinfo_existence_cache,
4404 cache_key, result_pool));
4405 if (found && mergeinfo_exists->data[0] == '1')
4406 SVN_ERR(svn_cache__get((void **)mergeinfo, &found,
4407 ffd->mergeinfo_cache,
4408 cache_key, result_pool));
4409 }
4410
4411 if (! found)
4412 {
4413 SVN_ERR(get_mergeinfo_for_path_internal(mergeinfo, rev_root, path,
4414 inherit,
4415 adjust_inherited_mergeinfo,
4416 result_pool, scratch_pool));
4417 if (ffd->mergeinfo_existence_cache)
4418 {
4419 mergeinfo_exists = svn_stringbuf_create(*mergeinfo ? "1" : "0",
4420 scratch_pool);
4421 SVN_ERR(svn_cache__set(ffd->mergeinfo_existence_cache,
4422 cache_key, mergeinfo_exists, scratch_pool));
4423 if (*mergeinfo)
4424 SVN_ERR(svn_cache__set(ffd->mergeinfo_cache,
4425 cache_key, *mergeinfo, scratch_pool));
4426 }
4427 }
4428
4429 return SVN_NO_ERROR;
4430 }
4431
4432 /* Invoke RECEIVER with BATON for each mergeinfo found on descendants of
4433 PATH (but not PATH itself). Use SCRATCH_POOL for temporary values. */
4434 static svn_error_t *
add_descendant_mergeinfo(svn_fs_root_t * root,const char * path,svn_fs_mergeinfo_receiver_t receiver,void * baton,apr_pool_t * scratch_pool)4435 add_descendant_mergeinfo(svn_fs_root_t *root,
4436 const char *path,
4437 svn_fs_mergeinfo_receiver_t receiver,
4438 void *baton,
4439 apr_pool_t *scratch_pool)
4440 {
4441 dag_node_t *this_dag;
4442 svn_boolean_t go_down;
4443
4444 SVN_ERR(get_dag(&this_dag, root, path, scratch_pool));
4445 SVN_ERR(svn_fs_fs__dag_has_descendants_with_mergeinfo(&go_down,
4446 this_dag));
4447 if (go_down)
4448 SVN_ERR(crawl_directory_dag_for_mergeinfo(root,
4449 path,
4450 this_dag,
4451 receiver,
4452 baton,
4453 scratch_pool));
4454 return SVN_NO_ERROR;
4455 }
4456
4457
4458 /* Find all the mergeinfo for a set of PATHS under ROOT and report it
4459 through RECEIVER with BATON. INHERITED, INCLUDE_DESCENDANTS and
4460 ADJUST_INHERITED_MERGEINFO are the same as in the FS API.
4461
4462 Allocate temporary values are allocated in SCRATCH_POOL. */
4463 static svn_error_t *
get_mergeinfos_for_paths(svn_fs_root_t * root,const apr_array_header_t * paths,svn_mergeinfo_inheritance_t inherit,svn_boolean_t include_descendants,svn_boolean_t adjust_inherited_mergeinfo,svn_fs_mergeinfo_receiver_t receiver,void * baton,apr_pool_t * scratch_pool)4464 get_mergeinfos_for_paths(svn_fs_root_t *root,
4465 const apr_array_header_t *paths,
4466 svn_mergeinfo_inheritance_t inherit,
4467 svn_boolean_t include_descendants,
4468 svn_boolean_t adjust_inherited_mergeinfo,
4469 svn_fs_mergeinfo_receiver_t receiver,
4470 void *baton,
4471 apr_pool_t *scratch_pool)
4472 {
4473 apr_pool_t *iterpool = svn_pool_create(scratch_pool);
4474 int i;
4475
4476 for (i = 0; i < paths->nelts; i++)
4477 {
4478 svn_error_t *err;
4479 svn_mergeinfo_t path_mergeinfo;
4480 const char *path = APR_ARRAY_IDX(paths, i, const char *);
4481
4482 svn_pool_clear(iterpool);
4483
4484 err = get_mergeinfo_for_path(&path_mergeinfo, root, path,
4485 inherit, adjust_inherited_mergeinfo,
4486 iterpool, iterpool);
4487 if (err)
4488 {
4489 if (err->apr_err == SVN_ERR_MERGEINFO_PARSE_ERROR)
4490 {
4491 svn_error_clear(err);
4492 err = NULL;
4493 path_mergeinfo = NULL;
4494 }
4495 else
4496 {
4497 return svn_error_trace(err);
4498 }
4499 }
4500
4501 if (path_mergeinfo)
4502 SVN_ERR(receiver(path, path_mergeinfo, baton, iterpool));
4503 if (include_descendants)
4504 SVN_ERR(add_descendant_mergeinfo(root, path, receiver, baton,
4505 iterpool));
4506 }
4507 svn_pool_destroy(iterpool);
4508
4509 return SVN_NO_ERROR;
4510 }
4511
4512
4513 /* Implements svn_fs_get_mergeinfo. */
4514 static svn_error_t *
fs_get_mergeinfo(svn_fs_root_t * root,const apr_array_header_t * paths,svn_mergeinfo_inheritance_t inherit,svn_boolean_t include_descendants,svn_boolean_t adjust_inherited_mergeinfo,svn_fs_mergeinfo_receiver_t receiver,void * baton,apr_pool_t * scratch_pool)4515 fs_get_mergeinfo(svn_fs_root_t *root,
4516 const apr_array_header_t *paths,
4517 svn_mergeinfo_inheritance_t inherit,
4518 svn_boolean_t include_descendants,
4519 svn_boolean_t adjust_inherited_mergeinfo,
4520 svn_fs_mergeinfo_receiver_t receiver,
4521 void *baton,
4522 apr_pool_t *scratch_pool)
4523 {
4524 fs_fs_data_t *ffd = root->fs->fsap_data;
4525
4526 /* We require a revision root. */
4527 if (root->is_txn_root)
4528 return svn_error_create(SVN_ERR_FS_NOT_REVISION_ROOT, NULL, NULL);
4529
4530 /* We have to actually be able to find the mergeinfo metadata! */
4531 if (! svn_fs_fs__fs_supports_mergeinfo(root->fs))
4532 return svn_error_createf
4533 (SVN_ERR_UNSUPPORTED_FEATURE, NULL,
4534 _("Querying mergeinfo requires version %d of the FSFS filesystem "
4535 "schema; filesystem '%s' uses only version %d"),
4536 SVN_FS_FS__MIN_MERGEINFO_FORMAT, root->fs->path, ffd->format);
4537
4538 /* Retrieve a path -> mergeinfo hash mapping. */
4539 return get_mergeinfos_for_paths(root, paths, inherit,
4540 include_descendants,
4541 adjust_inherited_mergeinfo,
4542 receiver, baton,
4543 scratch_pool);
4544 }
4545
4546
4547 /* The vtable associated with root objects. */
4548 static root_vtable_t root_vtable = {
4549 fs_paths_changed,
4550 fs_report_changes,
4551 svn_fs_fs__check_path,
4552 fs_node_history,
4553 svn_fs_fs__node_id,
4554 fs_node_relation,
4555 svn_fs_fs__node_created_rev,
4556 fs_node_origin_rev,
4557 fs_node_created_path,
4558 fs_delete_node,
4559 fs_copy,
4560 fs_revision_link,
4561 fs_copied_from,
4562 fs_closest_copy,
4563 fs_node_prop,
4564 fs_node_proplist,
4565 fs_node_has_props,
4566 fs_change_node_prop,
4567 fs_props_changed,
4568 fs_dir_entries,
4569 fs_dir_optimal_order,
4570 fs_make_dir,
4571 fs_file_length,
4572 fs_file_checksum,
4573 fs_file_contents,
4574 fs_try_process_file_contents,
4575 fs_make_file,
4576 fs_apply_textdelta,
4577 fs_apply_text,
4578 fs_contents_changed,
4579 fs_get_file_delta_stream,
4580 fs_merge,
4581 fs_get_mergeinfo,
4582 };
4583
4584 /* Construct a new root object in FS, allocated from POOL. */
4585 static svn_fs_root_t *
make_root(svn_fs_t * fs,apr_pool_t * pool)4586 make_root(svn_fs_t *fs,
4587 apr_pool_t *pool)
4588 {
4589 svn_fs_root_t *root = apr_pcalloc(pool, sizeof(*root));
4590
4591 root->fs = fs;
4592 root->pool = pool;
4593 root->vtable = &root_vtable;
4594
4595 return root;
4596 }
4597
4598
4599 /* Construct a root object referring to the root of REVISION in FS,
4600 whose root directory is ROOT_DIR. Create the new root in POOL. */
4601 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)4602 make_revision_root(svn_fs_t *fs,
4603 svn_revnum_t rev,
4604 dag_node_t *root_dir,
4605 apr_pool_t *pool)
4606 {
4607 svn_fs_root_t *root = make_root(fs, pool);
4608
4609 root->is_txn_root = FALSE;
4610 root->rev = rev;
4611 root->fsap_data = root_dir;
4612
4613 return root;
4614 }
4615
4616
4617 /* Construct a root object referring to the root of the transaction
4618 named TXN and based on revision BASE_REV in FS, with FLAGS to
4619 describe transaction's behavior. Create the new root in POOL. */
4620 static svn_error_t *
make_txn_root(svn_fs_root_t ** root_p,svn_fs_t * fs,const svn_fs_fs__id_part_t * txn,svn_revnum_t base_rev,apr_uint32_t flags,apr_pool_t * pool)4621 make_txn_root(svn_fs_root_t **root_p,
4622 svn_fs_t *fs,
4623 const svn_fs_fs__id_part_t *txn,
4624 svn_revnum_t base_rev,
4625 apr_uint32_t flags,
4626 apr_pool_t *pool)
4627 {
4628 svn_fs_root_t *root = make_root(fs, pool);
4629 fs_txn_root_data_t *frd = apr_pcalloc(root->pool, sizeof(*frd));
4630 frd->txn_id = *txn;
4631
4632 root->is_txn_root = TRUE;
4633 root->txn = svn_fs_fs__id_txn_unparse(txn, root->pool);
4634 root->txn_flags = flags;
4635 root->rev = base_rev;
4636
4637 /* Because this cache actually tries to invalidate elements, keep
4638 the number of elements per page down.
4639
4640 Note that since dag_node_cache_invalidate uses svn_cache__iter,
4641 this *cannot* be a memcache-based cache. */
4642 SVN_ERR(svn_cache__create_inprocess(&(frd->txn_node_cache),
4643 svn_fs_fs__dag_serialize,
4644 svn_fs_fs__dag_deserialize,
4645 APR_HASH_KEY_STRING,
4646 32, 20, FALSE,
4647 apr_pstrcat(pool, root->txn, ":TXN",
4648 SVN_VA_NULL),
4649 root->pool));
4650
4651 /* Initialize transaction-local caches in FS.
4652
4653 Note that we cannot put those caches in frd because that content
4654 fs root object is not available where we would need it. */
4655 SVN_ERR(svn_fs_fs__initialize_txn_caches(fs, root->txn, root->pool));
4656
4657 root->fsap_data = frd;
4658
4659 *root_p = root;
4660 return SVN_NO_ERROR;
4661 }
4662
4663
4664
4665 /* Verify. */
4666 static const char *
stringify_node(dag_node_t * node,apr_pool_t * pool)4667 stringify_node(dag_node_t *node,
4668 apr_pool_t *pool)
4669 {
4670 /* ### TODO: print some PATH@REV to it, too. */
4671 return svn_fs_fs__id_unparse(svn_fs_fs__dag_get_id(node), pool)->data;
4672 }
4673
4674 /* Check metadata sanity on NODE, and on its children. Manually verify
4675 information for DAG nodes in revision REV, and trust the metadata
4676 accuracy for nodes belonging to older revisions. To detect cycles,
4677 provide all parent dag_node_t * in PARENT_NODES. */
4678 static svn_error_t *
verify_node(dag_node_t * node,svn_revnum_t rev,apr_array_header_t * parent_nodes,apr_pool_t * pool)4679 verify_node(dag_node_t *node,
4680 svn_revnum_t rev,
4681 apr_array_header_t *parent_nodes,
4682 apr_pool_t *pool)
4683 {
4684 svn_boolean_t has_mergeinfo;
4685 apr_int64_t mergeinfo_count;
4686 const svn_fs_id_t *pred_id;
4687 svn_fs_t *fs = svn_fs_fs__dag_get_fs(node);
4688 int pred_count;
4689 svn_node_kind_t kind;
4690 apr_pool_t *iterpool = svn_pool_create(pool);
4691 int i;
4692
4693 /* Detect (non-)DAG cycles. */
4694 for (i = 0; i < parent_nodes->nelts; ++i)
4695 {
4696 dag_node_t *parent = APR_ARRAY_IDX(parent_nodes, i, dag_node_t *);
4697 if (svn_fs_fs__id_eq(svn_fs_fs__dag_get_id(parent),
4698 svn_fs_fs__dag_get_id(node)))
4699 return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4700 "Node is its own direct or indirect parent '%s'",
4701 stringify_node(node, iterpool));
4702 }
4703
4704 /* Fetch some data. */
4705 SVN_ERR(svn_fs_fs__dag_has_mergeinfo(&has_mergeinfo, node));
4706 SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_count, node));
4707 SVN_ERR(svn_fs_fs__dag_get_predecessor_id(&pred_id, node));
4708 SVN_ERR(svn_fs_fs__dag_get_predecessor_count(&pred_count, node));
4709 kind = svn_fs_fs__dag_node_kind(node);
4710
4711 /* Sanity check. */
4712 if (mergeinfo_count < 0)
4713 return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4714 "Negative mergeinfo-count %" APR_INT64_T_FMT
4715 " on node '%s'",
4716 mergeinfo_count, stringify_node(node, iterpool));
4717
4718 /* Issue #4129. (This check will explicitly catch non-root instances too.) */
4719 if (pred_id)
4720 {
4721 dag_node_t *pred;
4722 int pred_pred_count;
4723 SVN_ERR(svn_fs_fs__dag_get_node(&pred, fs, pred_id, iterpool));
4724 SVN_ERR(svn_fs_fs__dag_get_predecessor_count(&pred_pred_count, pred));
4725 if (pred_pred_count+1 != pred_count)
4726 return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4727 "Predecessor count mismatch: "
4728 "%s has %d, but %s has %d",
4729 stringify_node(node, iterpool), pred_count,
4730 stringify_node(pred, iterpool),
4731 pred_pred_count);
4732 }
4733
4734 /* Kind-dependent verifications. */
4735 if (kind == svn_node_none)
4736 {
4737 return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4738 "Node '%s' has kind 'none'",
4739 stringify_node(node, iterpool));
4740 }
4741 if (kind == svn_node_file)
4742 {
4743 if (has_mergeinfo != mergeinfo_count) /* comparing int to bool */
4744 return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4745 "File node '%s' has inconsistent mergeinfo: "
4746 "has_mergeinfo=%d, "
4747 "mergeinfo_count=%" APR_INT64_T_FMT,
4748 stringify_node(node, iterpool),
4749 has_mergeinfo, mergeinfo_count);
4750 }
4751 if (kind == svn_node_dir)
4752 {
4753 apr_array_header_t *entries;
4754 apr_int64_t children_mergeinfo = 0;
4755 APR_ARRAY_PUSH(parent_nodes, dag_node_t*) = node;
4756
4757 SVN_ERR(svn_fs_fs__dag_dir_entries(&entries, node, pool));
4758
4759 /* Compute CHILDREN_MERGEINFO. */
4760 for (i = 0; i < entries->nelts; ++i)
4761 {
4762 svn_fs_dirent_t *dirent
4763 = APR_ARRAY_IDX(entries, i, svn_fs_dirent_t *);
4764 dag_node_t *child;
4765 apr_int64_t child_mergeinfo;
4766
4767 svn_pool_clear(iterpool);
4768
4769 /* Compute CHILD_REV. */
4770 if (svn_fs_fs__id_rev(dirent->id) == rev)
4771 {
4772 SVN_ERR(svn_fs_fs__dag_get_node(&child, fs, dirent->id,
4773 iterpool));
4774 SVN_ERR(verify_node(child, rev, parent_nodes, iterpool));
4775 SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&child_mergeinfo,
4776 child));
4777 }
4778 else
4779 {
4780 /* access mergeinfo counter with minimal overhead */
4781 node_revision_t *noderev;
4782 SVN_ERR(svn_fs_fs__get_node_revision(&noderev, fs, dirent->id,
4783 iterpool, iterpool));
4784 child_mergeinfo = noderev->mergeinfo_count;
4785 }
4786
4787 children_mergeinfo += child_mergeinfo;
4788 }
4789
4790 /* Side-effect of issue #4129. */
4791 if (children_mergeinfo+has_mergeinfo != mergeinfo_count)
4792 return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4793 "Mergeinfo-count discrepancy on '%s': "
4794 "expected %" APR_INT64_T_FMT "+%d, "
4795 "counted %" APR_INT64_T_FMT,
4796 stringify_node(node, iterpool),
4797 mergeinfo_count, has_mergeinfo,
4798 children_mergeinfo);
4799
4800 /* If we don't make it here, there was an error / corruption.
4801 * In that case, nobody will need PARENT_NODES anymore. */
4802 apr_array_pop(parent_nodes);
4803 }
4804
4805 svn_pool_destroy(iterpool);
4806 return SVN_NO_ERROR;
4807 }
4808
4809 svn_error_t *
svn_fs_fs__verify_root(svn_fs_root_t * root,apr_pool_t * pool)4810 svn_fs_fs__verify_root(svn_fs_root_t *root,
4811 apr_pool_t *pool)
4812 {
4813 svn_fs_t *fs = root->fs;
4814 dag_node_t *root_dir;
4815 apr_array_header_t *parent_nodes;
4816
4817 /* Issue #4129: bogus pred-counts and minfo-cnt's on the root node-rev
4818 (and elsewhere). This code makes more thorough checks than the
4819 commit-time checks in validate_root_noderev(). */
4820
4821 /* Callers should disable caches by setting SVN_FS_CONFIG_FSFS_CACHE_NS;
4822 see r1462436.
4823
4824 When this code is called in the library, we want to ensure we
4825 use the on-disk data --- rather than some data that was read
4826 in the possibly-distance past and cached since. */
4827
4828 if (root->is_txn_root)
4829 {
4830 fs_txn_root_data_t *frd = root->fsap_data;
4831 SVN_ERR(svn_fs_fs__dag_txn_root(&root_dir, fs, &frd->txn_id, pool));
4832 }
4833 else
4834 {
4835 root_dir = root->fsap_data;
4836 }
4837
4838 /* Recursively verify ROOT_DIR. */
4839 parent_nodes = apr_array_make(pool, 16, sizeof(dag_node_t *));
4840 SVN_ERR(verify_node(root_dir, root->rev, parent_nodes, pool));
4841
4842 /* Verify explicitly the predecessor of the root. */
4843 {
4844 const svn_fs_id_t *pred_id;
4845
4846 /* Only r0 should have no predecessor. */
4847 SVN_ERR(svn_fs_fs__dag_get_predecessor_id(&pred_id, root_dir));
4848 if (! root->is_txn_root && !!pred_id != !!root->rev)
4849 return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4850 "r%ld's root node's predecessor is "
4851 "unexpectedly '%s'",
4852 root->rev,
4853 (pred_id
4854 ? svn_fs_fs__id_unparse(pred_id, pool)->data
4855 : "(null)"));
4856 if (root->is_txn_root && !pred_id)
4857 return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4858 "Transaction '%s''s root node's predecessor is "
4859 "unexpectedly NULL",
4860 root->txn);
4861
4862 /* Check the predecessor's revision. */
4863 if (pred_id)
4864 {
4865 svn_revnum_t pred_rev = svn_fs_fs__id_rev(pred_id);
4866 if (! root->is_txn_root && pred_rev+1 != root->rev)
4867 /* Issue #4129. */
4868 return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4869 "r%ld's root node's predecessor is r%ld"
4870 " but should be r%ld",
4871 root->rev, pred_rev, root->rev - 1);
4872 if (root->is_txn_root && pred_rev != root->rev)
4873 return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4874 "Transaction '%s''s root node's predecessor"
4875 " is r%ld"
4876 " but should be r%ld",
4877 root->txn, pred_rev, root->rev);
4878 }
4879 }
4880
4881 return SVN_NO_ERROR;
4882 }
4883