1 /* index.c indexing support for FSX support
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
12 * http://www.apache.org/licenses/LICENSE-2.0
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
20 * ====================================================================
26 #include "svn_pools.h"
27 #include "svn_sorts.h"
33 #include "private/svn_dep_compat.h"
34 #include "private/svn_sorts_private.h"
35 #include "private/svn_subr_private.h"
36 #include "private/svn_temp_serializer.h"
38 #include "svn_private_config.h"
39 #include "temp_serializer.h"
42 #include "../libsvn_fs/fs-loader.h"
44 /* maximum length of a uint64 in an 7/8b encoding */
45 #define ENCODED_INT_LENGTH 10
47 /* APR is missing an APR_OFF_T_MAX. So, define one. We will use it to
48 * limit file offsets stored in the indexes.
50 * We assume that everything shorter than 64 bits, it is at least 32 bits.
51 * We also assume that the type is always signed meaning we only have an
52 * effective positive range of 63 or 31 bits, respectively.
55 const apr_uint64_t off_t_max = (sizeof(apr_off_t) == sizeof(apr_int64_t))
59 /* We store P2L proto-index entries as 6 values, 64 bits each on disk.
60 * See also svn_fs_fs__p2l_proto_index_add_entry().
62 #define P2L_PROTO_INDEX_ENTRY_SIZE (6 * sizeof(apr_uint64_t))
64 /* We put this string in front of the L2P index header. */
65 #define L2P_STREAM_PREFIX "L2P-INDEX\n"
67 /* We put this string in front of the P2L index header. */
68 #define P2L_STREAM_PREFIX "P2L-INDEX\n"
70 /* Size of the buffer that will fit the index header prefixes. */
71 #define STREAM_PREFIX_LEN MAX(sizeof(L2P_STREAM_PREFIX), \
72 sizeof(P2L_STREAM_PREFIX))
74 /* Page tables in the log-to-phys index file exclusively contain entries
75 * of this type to describe position and size of a given page.
77 typedef struct l2p_page_table_entry_t
79 /* global offset on the page within the index file */
82 /* number of mapping entries in that page */
83 apr_uint32_t entry_count;
85 /* size of the page on disk (in the index file) */
87 } l2p_page_table_entry_t;
89 /* Master run-time data structure of an log-to-phys index. It contains
90 * the page tables of every revision covered by that index - but not the
93 typedef struct l2p_header_t
95 /* first revision covered by this index */
96 svn_revnum_t first_revision;
98 /* number of revisions covered */
99 apr_size_t revision_count;
101 /* (max) number of entries per page */
102 apr_uint32_t page_size;
104 /* indexes into PAGE_TABLE that mark the first page of the respective
105 * revision. PAGE_TABLE_INDEX[REVISION_COUNT] points to the end of
108 apr_size_t * page_table_index;
110 /* Page table covering all pages in the index */
111 l2p_page_table_entry_t * page_table;
114 /* Run-time data structure containing a single log-to-phys index page.
116 typedef struct l2p_page_t
118 /* number of entries in the OFFSETS array */
119 apr_uint32_t entry_count;
121 /* global file offsets (item index is the array index) within the
122 * packed or non-packed rev file. Offset will be -1 for unused /
123 * invalid item index values. */
126 /* In case that the item is stored inside a container, this is the
127 * identifying index of the item within that container. 0 for the
128 * container itself or for items that aren't containers. */
129 apr_uint32_t *sub_items;
132 /* All of the log-to-phys proto index file consist of entries of this type.
134 typedef struct l2p_proto_entry_t
136 /* phys offset + 1 of the data container. 0 for "new revision" entries. */
139 /* corresponding item index. 0 for "new revision" entries. */
140 apr_uint64_t item_index;
142 /* index within the container starting @ offset. 0 for "new revision"
143 * entries and for items with no outer container. */
144 apr_uint32_t sub_item;
147 /* Master run-time data structure of an phys-to-log index. It contains
148 * an array with one offset value for each rev file cluster.
150 typedef struct p2l_header_t
152 /* first revision covered by the index (and rev file) */
153 svn_revnum_t first_revision;
155 /* number of bytes in the rev files covered by each p2l page */
156 apr_uint64_t page_size;
158 /* number of pages / clusters in that rev file */
159 apr_size_t page_count;
161 /* number of bytes in the rev file */
162 apr_uint64_t file_size;
164 /* offsets of the pages / cluster descriptions within the index file */
169 * packed stream array
172 /* How many numbers we will pre-fetch and buffer in a packed number stream.
174 enum { MAX_NUMBER_PREFETCH = 64 };
176 /* Prefetched number entry in a packed number stream.
178 typedef struct value_position_pair_t
180 /* prefetched number */
183 /* number of bytes read, *including* this number, since the buffer start */
184 apr_size_t total_len;
185 } value_position_pair_t;
187 /* State of a prefetching packed number stream. It will read compressed
188 * index data efficiently and present it as a series of non-packed uint64.
190 struct svn_fs_x__packed_number_stream_t
192 /* underlying data file containing the packed values */
195 /* Offset within FILE at which the stream data starts
196 * (i.e. which offset will reported as offset 0 by packed_stream_offset). */
197 apr_off_t stream_start;
199 /* First offset within FILE after the stream data.
200 * Attempts to read beyond this will cause an "Unexpected End Of Stream"
202 apr_off_t stream_end;
204 /* number of used entries in BUFFER (starting at index 0) */
207 /* index of the next number to read from the BUFFER (0 .. USED).
208 * If CURRENT == USED, we need to read more data upon get() */
211 /* offset in FILE from which the first entry in BUFFER has been read */
212 apr_off_t start_offset;
214 /* offset in FILE from which the next number has to be read */
215 apr_off_t next_offset;
217 /* read the file in chunks of this size */
218 apr_size_t block_size;
220 /* pool to be used for file ops etc. */
223 /* buffer for prefetched values */
224 value_position_pair_t buffer[MAX_NUMBER_PREFETCH];
227 /* Return an svn_error_t * object for error ERR on STREAM with the given
228 * MESSAGE string. The latter must have a placeholder for the index file
229 * name ("%s") and the current read offset (e.g. "0x%lx").
232 stream_error_create(svn_fs_x__packed_number_stream_t *stream,
236 const char *file_name;
238 SVN_ERR(svn_io_file_name_get(&file_name, stream->file,
240 SVN_ERR(svn_fs_x__get_file_offset(&offset, stream->file, stream->pool));
242 return svn_error_createf(err, NULL, message, file_name,
243 apr_psprintf(stream->pool,
244 "%" APR_UINT64_T_HEX_FMT,
245 (apr_uint64_t)offset));
248 /* Read up to MAX_NUMBER_PREFETCH numbers from the STREAM->NEXT_OFFSET in
249 * STREAM->FILE and buffer them.
251 * We don't want GCC and others to inline this (infrequently called)
252 * function into packed_stream_get() because it prevents the latter from
253 * being inlined itself.
257 packed_stream_read(svn_fs_x__packed_number_stream_t *stream)
259 unsigned char buffer[MAX_NUMBER_PREFETCH];
262 value_position_pair_t *target;
263 apr_off_t block_start = 0;
264 apr_off_t block_left = 0;
267 /* all buffered data will have been read starting here */
268 stream->start_offset = stream->next_offset;
270 /* packed numbers are usually not aligned to MAX_NUMBER_PREFETCH blocks,
271 * i.e. the last number has been incomplete (and not buffered in stream)
272 * and need to be re-read. Therefore, always correct the file pointer.
274 SVN_ERR(svn_io_file_aligned_seek(stream->file, stream->block_size,
275 &block_start, stream->next_offset,
278 /* prefetch at least one number but, if feasible, don't cross block
279 * boundaries. This shall prevent jumping back and forth between two
280 * blocks because the extra data was not actually request _now_.
282 read = sizeof(buffer);
283 block_left = stream->block_size - (stream->next_offset - block_start);
284 if (block_left >= 10 && block_left < read)
285 read = (apr_size_t)block_left;
287 /* Don't read beyond the end of the file section that belongs to this
289 read = (apr_size_t)MIN(read, stream->stream_end - stream->next_offset);
291 err = apr_file_read(stream->file, buffer, &read);
292 if (err && !APR_STATUS_IS_EOF(err))
293 return stream_error_create(stream, err,
294 _("Can't read index file '%s' at offset 0x%"));
296 /* if the last number is incomplete, trim it from the buffer */
297 while (read > 0 && buffer[read-1] >= 0x80)
300 /* we call read() only if get() requires more data. So, there must be
301 * at least *one* further number. */
302 if SVN__PREDICT_FALSE(read == 0)
303 return stream_error_create(stream, err,
304 _("Unexpected end of index file %s at offset 0x%"));
306 /* parse file buffer and expand into stream buffer */
307 target = stream->buffer;
308 for (i = 0; i < read;)
310 if (buffer[i] < 0x80)
312 /* numbers < 128 are relatively frequent and particularly easy
313 * to decode. Give them special treatment. */
314 target->value = buffer[i];
316 target->total_len = i;
321 apr_uint64_t value = 0;
322 apr_uint64_t shift = 0;
323 while (buffer[i] >= 0x80)
325 value += ((apr_uint64_t)buffer[i] & 0x7f) << shift;
330 target->value = value + ((apr_uint64_t)buffer[i] << shift);
332 target->total_len = i;
335 /* let's catch corrupted data early. It would surely cause
336 * havoc further down the line. */
337 if SVN__PREDICT_FALSE(shift > 8 * sizeof(value))
338 return svn_error_createf(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
339 _("Corrupt index: number too large"));
343 /* update stream state */
344 stream->used = target - stream->buffer;
345 stream->next_offset = stream->start_offset + i;
351 /* Create and open a packed number stream reading from offsets START to
352 * END in FILE and return it in *STREAM. Access the file in chunks of
353 * BLOCK_SIZE bytes. Expect the stream to be prefixed by STREAM_PREFIX.
354 * Allocate *STREAM in RESULT_POOL and use SCRATCH_POOL for temporaries.
357 packed_stream_open(svn_fs_x__packed_number_stream_t **stream,
361 const char *stream_prefix,
362 apr_size_t block_size,
363 apr_pool_t *result_pool,
364 apr_pool_t *scratch_pool)
366 char buffer[STREAM_PREFIX_LEN + 1] = { 0 };
367 apr_size_t len = strlen(stream_prefix);
368 svn_fs_x__packed_number_stream_t *result;
370 /* If this is violated, we forgot to adjust STREAM_PREFIX_LEN after
371 * changing the index header prefixes. */
372 SVN_ERR_ASSERT(len < sizeof(buffer));
374 /* Read the header prefix and compare it with the expected prefix */
375 SVN_ERR(svn_io_file_aligned_seek(file, block_size, NULL, start,
377 SVN_ERR(svn_io_file_read_full2(file, buffer, len, NULL, NULL,
380 if (strncmp(buffer, stream_prefix, len))
381 return svn_error_createf(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
382 _("Index stream header prefix mismatch.\n"
384 " found: %s"), stream_prefix, buffer);
386 /* Construct the actual stream object. */
387 result = apr_palloc(result_pool, sizeof(*result));
389 result->pool = result_pool;
391 result->stream_start = start + len;
392 result->stream_end = end;
396 result->start_offset = result->stream_start;
397 result->next_offset = result->stream_start;
398 result->block_size = block_size;
406 * The forced inline is required for performance reasons: This is a very
407 * hot code path (called for every item we read) but e.g. GCC would rather
408 * chose to inline packed_stream_read() here, preventing packed_stream_get
409 * from being inlined itself.
413 packed_stream_get(apr_uint64_t *value,
414 svn_fs_x__packed_number_stream_t *stream)
416 if (stream->current == stream->used)
417 SVN_ERR(packed_stream_read(stream));
419 *value = stream->buffer[stream->current].value;
425 /* Navigate STREAM to packed stream offset OFFSET. There will be no checks
426 * whether the given OFFSET is valid.
429 packed_stream_seek(svn_fs_x__packed_number_stream_t *stream,
432 apr_off_t file_offset = offset + stream->stream_start;
434 if ( stream->used == 0
435 || offset < stream->start_offset
436 || offset >= stream->next_offset)
438 /* outside buffered data. Next get() will read() from OFFSET. */
439 stream->start_offset = file_offset;
440 stream->next_offset = file_offset;
446 /* Find the suitable location in the stream buffer.
447 * Since our buffer is small, it is efficient enough to simply scan
448 * it for the desired position. */
450 for (i = 0; i < stream->used; ++i)
451 if (stream->buffer[i].total_len > file_offset - stream->start_offset)
458 /* Return the packed stream offset of at which the next number in the stream
462 packed_stream_offset(svn_fs_x__packed_number_stream_t *stream)
464 apr_off_t file_offset
465 = stream->current == 0
466 ? stream->start_offset
467 : stream->buffer[stream->current-1].total_len + stream->start_offset;
469 return file_offset - stream->stream_start;
472 /* Write VALUE to the PROTO_INDEX file, using SCRATCH_POOL for temporary
475 * The point of this function is to ensure an architecture-independent
476 * proto-index file format. All data is written as unsigned 64 bits ints
477 * in little endian byte order. 64 bits is the largest portable integer
478 * we have and unsigned values have well-defined conversions in C.
481 write_uint64_to_proto_index(apr_file_t *proto_index,
483 apr_pool_t *scratch_pool)
485 apr_byte_t buffer[sizeof(value)];
489 /* Split VALUE into 8 bytes using LE ordering. */
490 for (i = 0; i < sizeof(buffer); ++i)
492 /* Unsigned conversions are well-defined ... */
493 buffer[i] = (apr_byte_t)value;
497 /* Write it all to disk. */
498 SVN_ERR(svn_io_file_write_full(proto_index, buffer, sizeof(buffer),
499 &written, scratch_pool));
500 SVN_ERR_ASSERT(written == sizeof(buffer));
505 /* Read one unsigned 64 bit value from PROTO_INDEX file and return it in
506 * *VALUE_P. If EOF is NULL, error out when trying to read beyond EOF.
507 * Use SCRATCH_POOL for temporary allocations.
509 * This function is the inverse to write_uint64_to_proto_index (see there),
510 * reading the external LE byte order and convert it into host byte order.
513 read_uint64_from_proto_index(apr_file_t *proto_index,
514 apr_uint64_t *value_p,
516 apr_pool_t *scratch_pool)
518 apr_byte_t buffer[sizeof(*value_p)];
521 /* Read the full 8 bytes or our 64 bit value, unless we hit EOF.
522 * Assert that we never read partial values. */
523 SVN_ERR(svn_io_file_read_full2(proto_index, buffer, sizeof(buffer),
524 &read, eof, scratch_pool));
525 SVN_ERR_ASSERT((eof && *eof) || read == sizeof(buffer));
527 /* If we did not hit EOF, reconstruct the uint64 value and return it. */
533 /* This could only overflow if CHAR_BIT had a value that is not
534 * a divisor of 64. */
536 for (i = sizeof(buffer) - 1; i >= 0; --i)
537 value = (value << CHAR_BIT) + buffer[i];
545 /* Convenience function similar to read_uint64_from_proto_index, but returns
546 * an uint32 value in VALUE_P. Return an error if the value does not fit.
549 read_uint32_from_proto_index(apr_file_t *proto_index,
550 apr_uint32_t *value_p,
552 apr_pool_t *scratch_pool)
555 SVN_ERR(read_uint64_from_proto_index(proto_index, &value, eof,
559 if (value > APR_UINT32_MAX)
560 return svn_error_createf(SVN_ERR_FS_INDEX_OVERFLOW, NULL,
561 _("UINT32 0x%s too large, max = 0x%s"),
562 apr_psprintf(scratch_pool,
563 "%" APR_UINT64_T_HEX_FMT,
565 apr_psprintf(scratch_pool,
566 "%" APR_UINT64_T_HEX_FMT,
567 (apr_uint64_t)APR_UINT32_MAX));
569 /* This conversion is not lossy because the value can be represented
570 * in the target type. */
571 *value_p = (apr_uint32_t)value;
577 /* Convenience function similar to read_uint64_from_proto_index, but returns
578 * an off_t value in VALUE_P. Return an error if the value does not fit.
581 read_off_t_from_proto_index(apr_file_t *proto_index,
584 apr_pool_t *scratch_pool)
587 SVN_ERR(read_uint64_from_proto_index(proto_index, &value, eof,
591 if (value > off_t_max)
592 return svn_error_createf(SVN_ERR_FS_INDEX_OVERFLOW, NULL,
593 _("File offset 0x%s too large, max = 0x%s"),
594 apr_psprintf(scratch_pool,
595 "%" APR_UINT64_T_HEX_FMT,
597 apr_psprintf(scratch_pool,
598 "%" APR_UINT64_T_HEX_FMT,
601 /* Shortening conversion from unsigned to signed int is well-defined
602 * and not lossy in C because the value can be represented in the
604 *value_p = (apr_off_t)value;
614 svn_fs_x__l2p_proto_index_open(apr_file_t **proto_index,
615 const char *file_name,
616 apr_pool_t *result_pool)
618 SVN_ERR(svn_io_file_open(proto_index, file_name, APR_READ | APR_WRITE
619 | APR_CREATE | APR_APPEND | APR_BUFFERED,
620 APR_OS_DEFAULT, result_pool));
625 /* Append ENTRY to log-to-phys PROTO_INDEX file.
626 * Use SCRATCH_POOL for temporary allocations.
629 write_l2p_entry_to_proto_index(apr_file_t *proto_index,
630 l2p_proto_entry_t entry,
631 apr_pool_t *scratch_pool)
633 SVN_ERR(write_uint64_to_proto_index(proto_index, entry.offset,
635 SVN_ERR(write_uint64_to_proto_index(proto_index, entry.item_index,
637 SVN_ERR(write_uint64_to_proto_index(proto_index, entry.sub_item,
643 /* Read *ENTRY from log-to-phys PROTO_INDEX file and indicate end-of-file
644 * in *EOF, or error out in that case if EOF is NULL. *ENTRY is in an
645 * undefined state if an end-of-file occurred.
646 * Use SCRATCH_POOL for temporary allocations.
649 read_l2p_entry_from_proto_index(apr_file_t *proto_index,
650 l2p_proto_entry_t *entry,
652 apr_pool_t *scratch_pool)
654 SVN_ERR(read_uint64_from_proto_index(proto_index, &entry->offset, eof,
656 SVN_ERR(read_uint64_from_proto_index(proto_index, &entry->item_index, eof,
658 SVN_ERR(read_uint32_from_proto_index(proto_index, &entry->sub_item, eof,
665 svn_fs_x__l2p_proto_index_add_revision(apr_file_t *proto_index,
666 apr_pool_t *scratch_pool)
668 l2p_proto_entry_t entry = { 0 };
669 return svn_error_trace(write_l2p_entry_to_proto_index(proto_index, entry,
674 svn_fs_x__l2p_proto_index_add_entry(apr_file_t *proto_index,
676 apr_uint32_t sub_item,
677 apr_uint64_t item_index,
678 apr_pool_t *scratch_pool)
680 l2p_proto_entry_t entry = { 0 };
682 /* make sure the conversion to uint64 works */
683 SVN_ERR_ASSERT(offset >= -1);
685 /* we support offset '-1' as a "not used" indication */
686 entry.offset = (apr_uint64_t)offset + 1;
688 /* make sure we can use item_index as an array index when building the
689 * final index file */
690 SVN_ERR_ASSERT(item_index < UINT_MAX / 2);
691 entry.item_index = item_index;
693 /* no limits on the container sub-item index */
694 entry.sub_item = sub_item;
696 return svn_error_trace(write_l2p_entry_to_proto_index(proto_index, entry,
700 /* Encode VALUE as 7/8b into P and return the number of bytes written.
701 * This will be used when _writing_ packed data. packed_stream_* is for
702 * read operations only.
705 encode_uint(unsigned char *p, apr_uint64_t value)
707 unsigned char *start = p;
708 while (value >= 0x80)
710 *p = (unsigned char)((value % 0x80) + 0x80);
715 *p = (unsigned char)(value % 0x80);
716 return (p - start) + 1;
719 /* Encode VALUE as 7/8b into P and return the number of bytes written.
720 * This maps signed ints onto unsigned ones.
723 encode_int(unsigned char *p, apr_int64_t value)
725 return encode_uint(p, (apr_uint64_t)(value < 0 ? -1 - 2*value : 2*value));
728 /* Append VALUE to STREAM in 7/8b encoding.
731 stream_write_encoded(svn_stream_t *stream,
734 unsigned char encoded[ENCODED_INT_LENGTH];
736 apr_size_t len = encode_uint(encoded, value);
737 return svn_error_trace(svn_stream_write(stream, (char *)encoded, &len));
740 /* Run-length-encode the uint64 numbers in ARRAY starting at index START
741 * up to but not including END. All numbers must be > 0.
742 * Return the number of remaining entries in ARRAY after START.
745 rle_array(apr_array_header_t *array, int start, int end)
749 for (i = start; i < end; ++i)
751 apr_uint64_t value = APR_ARRAY_IDX(array, i, apr_uint64_t);
757 for (counter = 1; i + counter < end; ++counter)
758 if (APR_ARRAY_IDX(array, i + counter, apr_uint64_t) != 1)
763 APR_ARRAY_IDX(array, target, apr_uint64_t) = 0;
764 APR_ARRAY_IDX(array, target + 1, apr_uint64_t) = counter;
771 APR_ARRAY_IDX(array, target, apr_uint64_t) = value;
778 /* Utility data structure describing an log-2-phys page entry.
779 * This is only used as a transient representation during index creation.
781 typedef struct l2p_page_entry_t
784 apr_uint32_t sub_item;
787 /* qsort-compatible compare function taking two l2p_page_entry_t and
788 * ordering them by offset.
791 compare_l2p_entries_by_offset(const l2p_page_entry_t *lhs,
792 const l2p_page_entry_t *rhs)
794 return lhs->offset > rhs->offset ? 1
795 : lhs->offset == rhs->offset ? 0 : -1;
798 /* Write the log-2-phys index page description for the l2p_page_entry_t
799 * array ENTRIES, starting with element START up to but not including END.
800 * Write the resulting representation into BUFFER. Use SCRATCH_POOL for
801 * temporary allocations.
804 encode_l2p_page(apr_array_header_t *entries,
807 svn_spillbuf_t *buffer,
808 apr_pool_t *scratch_pool)
810 unsigned char encoded[ENCODED_INT_LENGTH];
811 apr_hash_t *containers = apr_hash_make(scratch_pool);
812 int count = end - start;
813 int container_count = 0;
814 apr_uint64_t last_offset = 0;
817 apr_size_t data_size = count * sizeof(l2p_page_entry_t);
818 svn_stringbuf_t *container_offsets
819 = svn_stringbuf_create_ensure(count * 2, scratch_pool);
821 /* SORTED: relevant items from ENTRIES, sorted by offset */
822 l2p_page_entry_t *sorted
823 = apr_pmemdup(scratch_pool,
824 entries->elts + start * sizeof(l2p_page_entry_t),
826 qsort(sorted, end - start, sizeof(l2p_page_entry_t),
827 (int (*)(const void *, const void *))compare_l2p_entries_by_offset);
829 /* identify container offsets and create container list */
830 for (i = 0; i < count; ++i)
832 /* skip "unused" entries */
833 if (sorted[i].offset == 0)
836 /* offset already covered? */
837 if (i > 0 && sorted[i].offset == sorted[i-1].offset)
840 /* is this a container item
841 * (appears more than once or accesses to sub-items other than 0)? */
842 if ( (i != count-1 && sorted[i].offset == sorted[i+1].offset)
843 || (sorted[i].sub_item != 0))
845 svn_stringbuf_appendbytes(container_offsets, (const char *)encoded,
846 encode_uint(encoded, sorted[i].offset
848 last_offset = sorted[i].offset;
849 apr_hash_set(containers,
851 sizeof(sorted[i].offset),
852 (void *)(apr_uintptr_t)++container_count);
856 /* write container list to BUFFER */
857 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded,
858 encode_uint(encoded, container_count),
860 SVN_ERR(svn_spillbuf__write(buffer, (const char *)container_offsets->data,
861 container_offsets->len, scratch_pool));
864 for (i = start; i < end; ++i)
866 l2p_page_entry_t *entry = &APR_ARRAY_IDX(entries, i, l2p_page_entry_t);
867 if (entry->offset == 0)
869 SVN_ERR(svn_spillbuf__write(buffer, "\0", 1, scratch_pool));
873 void *void_idx = apr_hash_get(containers, &entry->offset,
874 sizeof(entry->offset));
875 if (void_idx == NULL)
877 apr_uint64_t value = entry->offset + container_count;
878 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded,
879 encode_uint(encoded, value),
884 apr_uintptr_t idx = (apr_uintptr_t)void_idx;
885 apr_uint64_t value = entry->sub_item;
886 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded,
887 encode_uint(encoded, idx),
889 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded,
890 encode_uint(encoded, value),
900 svn_fs_x__l2p_index_append(svn_checksum_t **checksum,
902 apr_file_t *index_file,
903 const char *proto_file_name,
904 svn_revnum_t revision,
905 apr_pool_t * result_pool,
906 apr_pool_t *scratch_pool)
908 svn_fs_x__data_t *ffd = fs->fsap_data;
909 apr_file_t *proto_index = NULL;
910 svn_stream_t *stream;
914 svn_boolean_t eof = FALSE;
916 int last_page_count = 0; /* total page count at the start of
917 the current revision */
919 /* temporary data structures that collect the data which will be moved
920 to the target file in a second step */
921 apr_pool_t *local_pool = svn_pool_create(scratch_pool);
922 apr_pool_t *iterpool = svn_pool_create(local_pool);
923 apr_array_header_t *page_counts
924 = apr_array_make(local_pool, 16, sizeof(apr_uint64_t));
925 apr_array_header_t *page_sizes
926 = apr_array_make(local_pool, 16, sizeof(apr_uint64_t));
927 apr_array_header_t *entry_counts
928 = apr_array_make(local_pool, 16, sizeof(apr_uint64_t));
930 /* collect the item offsets and sub-item value for the current revision */
931 apr_array_header_t *entries
932 = apr_array_make(local_pool, 256, sizeof(l2p_page_entry_t));
934 /* 64k blocks, spill after 16MB */
935 svn_spillbuf_t *buffer
936 = svn_spillbuf__create(0x10000, 0x1000000, local_pool);
938 /* Paranoia check that makes later casting to int32 safe.
939 * The current implementation is limited to 2G entries per page. */
940 if (ffd->l2p_page_size > APR_INT32_MAX)
941 return svn_error_createf(SVN_ERR_FS_INDEX_OVERFLOW , NULL,
942 _("L2P index page size %s"
943 " exceeds current limit of 2G entries"),
944 apr_psprintf(local_pool, "%" APR_UINT64_T_FMT,
945 ffd->l2p_page_size));
947 /* start at the beginning of the source file */
948 SVN_ERR(svn_io_file_open(&proto_index, proto_file_name,
949 APR_READ | APR_CREATE | APR_BUFFERED,
950 APR_OS_DEFAULT, local_pool));
952 /* process all entries until we fail due to EOF */
953 for (entry = 0; !eof; ++entry)
955 l2p_proto_entry_t proto_entry;
957 /* (attempt to) read the next entry from the source */
958 SVN_ERR(read_l2p_entry_from_proto_index(proto_index, &proto_entry,
961 /* handle new revision */
962 if ((entry > 0 && proto_entry.offset == 0) || eof)
964 /* dump entries, grouped into pages */
967 for (i = 0; i < entries->nelts; i += entry_count)
969 /* 1 page with up to L2P_PAGE_SIZE entries.
970 * fsfs.conf settings validation guarantees this to fit into
971 * our address space. */
972 apr_size_t last_buffer_size
973 = (apr_size_t)svn_spillbuf__get_size(buffer);
975 svn_pool_clear(iterpool);
977 entry_count = ffd->l2p_page_size < entries->nelts - i
978 ? (int)ffd->l2p_page_size
979 : entries->nelts - i;
980 SVN_ERR(encode_l2p_page(entries, i, i + entry_count,
983 APR_ARRAY_PUSH(entry_counts, apr_uint64_t) = entry_count;
984 APR_ARRAY_PUSH(page_sizes, apr_uint64_t)
985 = svn_spillbuf__get_size(buffer) - last_buffer_size;
988 apr_array_clear(entries);
990 /* store the number of pages in this revision */
991 APR_ARRAY_PUSH(page_counts, apr_uint64_t)
992 = page_sizes->nelts - last_page_count;
994 last_page_count = page_sizes->nelts;
1000 /* store the mapping in our array */
1001 l2p_page_entry_t page_entry = { 0 };
1003 if (proto_entry.item_index > APR_INT32_MAX)
1004 return svn_error_createf(SVN_ERR_FS_INDEX_OVERFLOW , NULL,
1005 _("Item index %s too large "
1006 "in l2p proto index for revision %ld"),
1007 apr_psprintf(local_pool,
1008 "%" APR_UINT64_T_FMT,
1009 proto_entry.item_index),
1010 revision + page_counts->nelts);
1012 idx = (int)proto_entry.item_index;
1013 while (idx >= entries->nelts)
1014 APR_ARRAY_PUSH(entries, l2p_page_entry_t) = page_entry;
1016 page_entry.offset = proto_entry.offset;
1017 page_entry.sub_item = proto_entry.sub_item;
1018 APR_ARRAY_IDX(entries, idx, l2p_page_entry_t) = page_entry;
1022 /* we are now done with the source file */
1023 SVN_ERR(svn_io_file_close(proto_index, local_pool));
1025 /* Paranoia check that makes later casting to int32 safe.
1026 * The current implementation is limited to 2G pages per index. */
1027 if (page_counts->nelts > APR_INT32_MAX)
1028 return svn_error_createf(SVN_ERR_FS_INDEX_OVERFLOW , NULL,
1029 _("L2P index page count %d"
1030 " exceeds current limit of 2G pages"),
1031 page_counts->nelts);
1033 /* open target stream. */
1034 stream = svn_stream_checksummed2(svn_stream_from_aprfile2(index_file, TRUE,
1036 NULL, checksum, svn_checksum_md5, FALSE,
1040 /* write header info */
1041 SVN_ERR(svn_stream_puts(stream, L2P_STREAM_PREFIX));
1042 SVN_ERR(stream_write_encoded(stream, revision));
1043 SVN_ERR(stream_write_encoded(stream, page_counts->nelts));
1044 SVN_ERR(stream_write_encoded(stream, ffd->l2p_page_size));
1045 SVN_ERR(stream_write_encoded(stream, page_sizes->nelts));
1047 /* write the revision table */
1048 end = rle_array(page_counts, 0, page_counts->nelts);
1049 for (i = 0; i < end; ++i)
1051 apr_uint64_t value = APR_ARRAY_IDX(page_counts, i, apr_uint64_t);
1052 SVN_ERR(stream_write_encoded(stream, value));
1055 /* write the page table */
1056 for (i = 0; i < page_sizes->nelts; ++i)
1058 apr_uint64_t value = APR_ARRAY_IDX(page_sizes, i, apr_uint64_t);
1059 SVN_ERR(stream_write_encoded(stream, value));
1060 value = APR_ARRAY_IDX(entry_counts, i, apr_uint64_t);
1061 SVN_ERR(stream_write_encoded(stream, value));
1064 /* append page contents and implicitly close STREAM */
1065 SVN_ERR(svn_stream_copy3(svn_stream__from_spillbuf(buffer, local_pool),
1066 stream, NULL, NULL, local_pool));
1068 svn_pool_destroy(local_pool);
1070 return SVN_NO_ERROR;
1073 /* Return the base revision used to identify the p2l or lp2 index covering
1077 base_revision(svn_fs_t *fs, svn_revnum_t revision)
1079 svn_fs_x__data_t *ffd = fs->fsap_data;
1080 return svn_fs_x__is_packed_rev(fs, revision)
1081 ? revision - (revision % ffd->max_files_per_dir)
1085 /* Data structure that describes which l2p page info shall be extracted
1086 * from the cache and contains the fields that receive the result.
1088 typedef struct l2p_page_info_baton_t
1090 /* input data: we want the page covering (REVISION,ITEM_INDEX) */
1091 svn_revnum_t revision;
1092 apr_uint64_t item_index;
1095 /* page location and size of the page within the l2p index file */
1096 l2p_page_table_entry_t entry;
1098 /* page number within the pages for REVISION (not l2p index global!) */
1099 apr_uint32_t page_no;
1101 /* offset of ITEM_INDEX within that page */
1102 apr_uint32_t page_offset;
1104 /* revision identifying the l2p index file, also the first rev in that */
1105 svn_revnum_t first_revision;
1106 } l2p_page_info_baton_t;
1109 /* Utility function that copies the info requested by BATON->REVISION and
1110 * BATON->ITEM_INDEX and from HEADER and PAGE_TABLE into the output fields
1111 * of *BATON. Use SCRATCH_POOL for temporary allocations.
1113 static svn_error_t *
1114 l2p_header_copy(l2p_page_info_baton_t *baton,
1115 const l2p_header_t *header,
1116 const l2p_page_table_entry_t *page_table,
1117 const apr_size_t *page_table_index,
1118 apr_pool_t *scratch_pool)
1120 /* revision offset within the index file */
1121 apr_size_t rel_revision = baton->revision - header->first_revision;
1122 if (rel_revision >= header->revision_count)
1123 return svn_error_createf(SVN_ERR_FS_INDEX_REVISION , NULL,
1124 _("Revision %ld not covered by item index"),
1127 /* select the relevant page */
1128 if (baton->item_index < header->page_size)
1130 /* most revs fit well into a single page */
1131 baton->page_offset = (apr_uint32_t)baton->item_index;
1133 baton->entry = page_table[page_table_index[rel_revision]];
1137 const l2p_page_table_entry_t *first_entry;
1138 const l2p_page_table_entry_t *last_entry;
1139 apr_uint64_t max_item_index;
1141 /* range of pages for this rev */
1142 first_entry = page_table + page_table_index[rel_revision];
1143 last_entry = page_table + page_table_index[rel_revision + 1];
1145 /* do we hit a valid index page? */
1146 max_item_index = (apr_uint64_t)header->page_size
1147 * (last_entry - first_entry);
1148 if (baton->item_index >= max_item_index)
1149 return svn_error_createf(SVN_ERR_FS_INDEX_OVERFLOW , NULL,
1150 _("Item index %s exceeds l2p limit "
1151 "of %s for revision %ld"),
1152 apr_psprintf(scratch_pool,
1153 "%" APR_UINT64_T_FMT,
1155 apr_psprintf(scratch_pool,
1156 "%" APR_UINT64_T_FMT,
1160 /* all pages are of the same size and full, except for the last one */
1161 baton->page_offset = (apr_uint32_t)(baton->item_index % header->page_size);
1162 baton->page_no = (apr_uint32_t)(baton->item_index / header->page_size);
1163 baton->entry = first_entry[baton->page_no];
1166 baton->first_revision = header->first_revision;
1168 return SVN_NO_ERROR;
1171 /* Implement svn_cache__partial_getter_func_t: copy the data requested in
1172 * l2p_page_info_baton_t *BATON from l2p_header_t *DATA into the output
1175 static svn_error_t *
1176 l2p_header_access_func(void **out,
1178 apr_size_t data_len,
1180 apr_pool_t *result_pool)
1182 /* resolve all pointer values of in-cache data */
1183 const l2p_header_t *header = data;
1184 const l2p_page_table_entry_t *page_table
1185 = svn_temp_deserializer__ptr(header,
1186 (const void *const *)&header->page_table);
1187 const apr_size_t *page_table_index
1188 = svn_temp_deserializer__ptr(header,
1189 (const void *const *)&header->page_table_index);
1192 return l2p_header_copy(baton, header, page_table, page_table_index,
1196 /* Read COUNT run-length-encoded (see rle_array) uint64 from STREAM and
1197 * return them in VALUES.
1199 static svn_error_t *
1200 expand_rle(apr_array_header_t *values,
1201 svn_fs_x__packed_number_stream_t *stream,
1204 apr_array_clear(values);
1209 SVN_ERR(packed_stream_get(&value, stream));
1213 APR_ARRAY_PUSH(values, apr_uint64_t) = value;
1219 apr_uint64_t repetitions;
1220 SVN_ERR(packed_stream_get(&repetitions, stream));
1221 if (++repetitions > count)
1222 repetitions = count;
1224 for (i = 0; i < repetitions; ++i)
1225 APR_ARRAY_PUSH(values, apr_uint64_t) = 1;
1227 count -= repetitions;
1231 return SVN_NO_ERROR;
1234 /* If REV_FILE->L2P_STREAM is NULL, create a new stream for the log-to-phys
1235 * index for REVISION in FS and return it in REV_FILE.
1237 static svn_error_t *
1238 auto_open_l2p_index(svn_fs_x__revision_file_t *rev_file,
1240 svn_revnum_t revision)
1242 if (rev_file->l2p_stream == NULL)
1244 svn_fs_x__data_t *ffd = fs->fsap_data;
1246 SVN_ERR(svn_fs_x__auto_read_footer(rev_file));
1247 SVN_ERR(packed_stream_open(&rev_file->l2p_stream,
1249 rev_file->l2p_offset,
1250 rev_file->p2l_offset,
1252 (apr_size_t)ffd->block_size,
1257 return SVN_NO_ERROR;
1260 /* Read the header data structure of the log-to-phys index for REVISION
1261 * in FS and return it in *HEADER, allocated in RESULT_POOL. Use REV_FILE
1262 * to access on-disk data. Use SCRATCH_POOL for temporary allocations.
1264 static svn_error_t *
1265 get_l2p_header_body(l2p_header_t **header,
1266 svn_fs_x__revision_file_t *rev_file,
1268 svn_revnum_t revision,
1269 apr_pool_t *result_pool,
1270 apr_pool_t *scratch_pool)
1272 svn_fs_x__data_t *ffd = fs->fsap_data;
1275 apr_size_t page, page_count;
1277 l2p_header_t *result = apr_pcalloc(result_pool, sizeof(*result));
1278 apr_size_t page_table_index;
1279 svn_revnum_t next_rev;
1280 apr_array_header_t *expanded_values
1281 = apr_array_make(scratch_pool, 16, sizeof(apr_uint64_t));
1283 svn_fs_x__pair_cache_key_t key;
1284 key.revision = rev_file->start_revision;
1285 key.second = rev_file->is_packed;
1287 SVN_ERR(auto_open_l2p_index(rev_file, fs, revision));
1288 packed_stream_seek(rev_file->l2p_stream, 0);
1290 /* Read the table sizes. Check the data for plausibility and
1291 * consistency with other bits. */
1292 SVN_ERR(packed_stream_get(&value, rev_file->l2p_stream));
1293 result->first_revision = (svn_revnum_t)value;
1294 if (result->first_revision != rev_file->start_revision)
1295 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
1296 _("Index rev / pack file revision numbers do not match"));
1298 SVN_ERR(packed_stream_get(&value, rev_file->l2p_stream));
1299 result->revision_count = (int)value;
1300 if ( result->revision_count != 1
1301 && result->revision_count != (apr_uint64_t)ffd->max_files_per_dir)
1302 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
1303 _("Invalid number of revisions in L2P index"));
1305 SVN_ERR(packed_stream_get(&value, rev_file->l2p_stream));
1306 result->page_size = (apr_uint32_t)value;
1307 if (!result->page_size || (result->page_size & (result->page_size - 1)))
1308 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
1309 _("L2P index page size is not a power of two"));
1311 SVN_ERR(packed_stream_get(&value, rev_file->l2p_stream));
1312 page_count = (apr_size_t)value;
1313 if (page_count < result->revision_count)
1314 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
1315 _("Fewer L2P index pages than revisions"));
1316 if (page_count > (rev_file->p2l_offset - rev_file->l2p_offset) / 2)
1317 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
1318 _("L2P index page count implausibly large"));
1320 next_rev = result->first_revision + (svn_revnum_t)result->revision_count;
1321 if (result->first_revision > revision || next_rev <= revision)
1322 return svn_error_createf(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
1323 _("Corrupt L2P index for r%ld only covers r%ld:%ld"),
1324 revision, result->first_revision, next_rev);
1326 /* allocate the page tables */
1328 = apr_pcalloc(result_pool, page_count * sizeof(*result->page_table));
1329 result->page_table_index
1330 = apr_pcalloc(result_pool, (result->revision_count + 1)
1331 * sizeof(*result->page_table_index));
1333 /* read per-revision page table sizes (i.e. number of pages per rev) */
1334 page_table_index = 0;
1335 result->page_table_index[0] = page_table_index;
1336 SVN_ERR(expand_rle(expanded_values, rev_file->l2p_stream,
1337 result->revision_count));
1338 for (i = 0; i < result->revision_count; ++i)
1340 value = (apr_size_t)APR_ARRAY_IDX(expanded_values, i, apr_uint64_t);
1342 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
1343 _("Revision with no L2P index pages"));
1345 page_table_index += (apr_size_t)value;
1346 if (page_table_index > page_count)
1347 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
1348 _("L2P page table exceeded"));
1350 result->page_table_index[i+1] = page_table_index;
1353 if (page_table_index != page_count)
1354 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
1355 _("Revisions do not cover the full L2P index page table"));
1357 /* read actual page tables */
1358 for (page = 0; page < page_count; ++page)
1360 SVN_ERR(packed_stream_get(&value, rev_file->l2p_stream));
1362 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
1363 _("Empty L2P index page"));
1365 result->page_table[page].size = (apr_uint32_t)value;
1366 SVN_ERR(packed_stream_get(&value, rev_file->l2p_stream));
1367 if (value > result->page_size)
1368 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
1369 _("Page exceeds L2P index page size"));
1371 result->page_table[page].entry_count = (apr_uint32_t)value;
1374 /* correct the page description offsets */
1375 offset = packed_stream_offset(rev_file->l2p_stream);
1376 for (page = 0; page < page_count; ++page)
1378 result->page_table[page].offset = offset;
1379 offset += result->page_table[page].size;
1382 /* return and cache the header */
1384 SVN_ERR(svn_cache__set(ffd->l2p_header_cache, &key, result, scratch_pool));
1386 return SVN_NO_ERROR;
1389 /* Get the page info requested in *BATON from FS and set the output fields
1391 * To maximize efficiency, use or return the data stream in *STREAM.
1392 * Use SCRATCH_POOL for temporary allocations.
1394 static svn_error_t *
1395 get_l2p_page_info(l2p_page_info_baton_t *baton,
1396 svn_fs_x__revision_file_t *rev_file,
1398 apr_pool_t *scratch_pool)
1400 svn_fs_x__data_t *ffd = fs->fsap_data;
1401 l2p_header_t *result;
1402 svn_boolean_t is_cached = FALSE;
1405 /* try to find the info in the cache */
1406 svn_fs_x__pair_cache_key_t key;
1407 key.revision = base_revision(fs, baton->revision);
1408 key.second = svn_fs_x__is_packed_rev(fs, baton->revision);
1409 SVN_ERR(svn_cache__get_partial((void**)&dummy, &is_cached,
1410 ffd->l2p_header_cache, &key,
1411 l2p_header_access_func, baton,
1414 return SVN_NO_ERROR;
1416 /* read from disk, cache and copy the result */
1417 SVN_ERR(get_l2p_header_body(&result, rev_file, fs, baton->revision,
1418 scratch_pool, scratch_pool));
1419 SVN_ERR(l2p_header_copy(baton, result, result->page_table,
1420 result->page_table_index, scratch_pool));
1422 return SVN_NO_ERROR;
1425 /* Read the log-to-phys header info of the index covering REVISION from FS
1426 * and return it in *HEADER. REV_FILE provides the pack / rev status.
1427 * Allocate *HEADER in RESULT_POOL, use SCRATCH_POOL for temporary
1430 static svn_error_t *
1431 get_l2p_header(l2p_header_t **header,
1432 svn_fs_x__revision_file_t *rev_file,
1434 svn_revnum_t revision,
1435 apr_pool_t *result_pool,
1436 apr_pool_t *scratch_pool)
1438 svn_fs_x__data_t *ffd = fs->fsap_data;
1439 svn_boolean_t is_cached = FALSE;
1441 /* first, try cache lookop */
1442 svn_fs_x__pair_cache_key_t key;
1443 key.revision = rev_file->start_revision;
1444 key.second = rev_file->is_packed;
1445 SVN_ERR(svn_cache__get((void**)header, &is_cached, ffd->l2p_header_cache,
1446 &key, result_pool));
1448 return SVN_NO_ERROR;
1450 /* read from disk and cache the result */
1451 SVN_ERR(get_l2p_header_body(header, rev_file, fs, revision, result_pool,
1454 return SVN_NO_ERROR;
1457 /* From the log-to-phys index file starting at START_REVISION in FS, read
1458 * the mapping page identified by TABLE_ENTRY and return it in *PAGE.
1459 * Use REV_FILE to access on-disk files.
1460 * Use RESULT_POOL for allocations.
1462 static svn_error_t *
1463 get_l2p_page(l2p_page_t **page,
1464 svn_fs_x__revision_file_t *rev_file,
1466 svn_revnum_t start_revision,
1467 l2p_page_table_entry_t *table_entry,
1468 apr_pool_t *result_pool)
1470 apr_uint64_t value, last_value = 0;
1472 l2p_page_t *result = apr_pcalloc(result_pool, sizeof(*result));
1473 apr_uint64_t container_count;
1474 apr_off_t *container_offsets;
1476 /* open index file and select page */
1477 SVN_ERR(auto_open_l2p_index(rev_file, fs, start_revision));
1478 packed_stream_seek(rev_file->l2p_stream, table_entry->offset);
1480 /* initialize the page content */
1481 result->entry_count = table_entry->entry_count;
1482 result->offsets = apr_pcalloc(result_pool, result->entry_count
1483 * sizeof(*result->offsets));
1484 result->sub_items = apr_pcalloc(result_pool, result->entry_count
1485 * sizeof(*result->sub_items));
1487 /* container offsets array */
1489 SVN_ERR(packed_stream_get(&container_count, rev_file->l2p_stream));
1490 container_offsets = apr_pcalloc(result_pool,
1491 container_count * sizeof(*result));
1492 for (i = 0; i < container_count; ++i)
1494 SVN_ERR(packed_stream_get(&value, rev_file->l2p_stream));
1495 last_value += value;
1496 container_offsets[i] = (apr_off_t)last_value - 1;
1497 /* '-1' is represented as '0' in the index file */
1500 /* read all page entries (offsets in rev file and container sub-items) */
1501 for (i = 0; i < result->entry_count; ++i)
1503 SVN_ERR(packed_stream_get(&value, rev_file->l2p_stream));
1506 result->offsets[i] = -1;
1507 result->sub_items[i] = 0;
1509 else if (value <= container_count)
1511 result->offsets[i] = container_offsets[value - 1];
1512 SVN_ERR(packed_stream_get(&value, rev_file->l2p_stream));
1513 result->sub_items[i] = (apr_uint32_t)value;
1517 result->offsets[i] = (apr_off_t)(value - 1 - container_count);
1518 result->sub_items[i] = 0;
1522 /* After reading all page entries, the read cursor must have moved by
1523 * TABLE_ENTRY->SIZE bytes. */
1524 if ( packed_stream_offset(rev_file->l2p_stream)
1525 != table_entry->offset + table_entry->size)
1526 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
1527 _("L2P actual page size does not match page table value."));
1531 return SVN_NO_ERROR;
1534 /* Request data structure for l2p_page_access_func.
1536 typedef struct l2p_page_baton_t
1539 /* revision. Used for error messages only */
1540 svn_revnum_t revision;
1542 /* item index to look up. Used for error messages only */
1543 apr_uint64_t item_index;
1545 /* offset within the cached page */
1546 apr_uint32_t page_offset;
1549 /* absolute item or container offset in rev / pack file */
1552 /* 0 -> container / item itself; sub-item in container otherwise */
1553 apr_uint32_t sub_item;
1557 /* Return the rev / pack file offset of the item at BATON->PAGE_OFFSET in
1558 * OFFSETS of PAGE and write it to *OFFSET.
1559 * Allocate temporaries in SCRATCH_POOL.
1561 static svn_error_t *
1562 l2p_page_get_offset(l2p_page_baton_t *baton,
1563 const l2p_page_t *page,
1564 const apr_off_t *offsets,
1565 const apr_uint32_t *sub_items,
1566 apr_pool_t *scratch_pool)
1568 /* overflow check */
1569 if (page->entry_count <= baton->page_offset)
1570 return svn_error_createf(SVN_ERR_FS_INDEX_OVERFLOW , NULL,
1571 _("Item index %s too large in"
1573 apr_psprintf(scratch_pool, "%" APR_UINT64_T_FMT,
1577 /* return the result */
1578 baton->offset = offsets[baton->page_offset];
1579 baton->sub_item = sub_items[baton->page_offset];
1581 return SVN_NO_ERROR;
1584 /* Implement svn_cache__partial_getter_func_t: copy the data requested in
1585 * l2p_page_baton_t *BATON from l2p_page_t *DATA into apr_off_t *OUT.
1587 static svn_error_t *
1588 l2p_page_access_func(void **out,
1590 apr_size_t data_len,
1592 apr_pool_t *result_pool)
1594 /* resolve all in-cache pointers */
1595 const l2p_page_t *page = data;
1596 const apr_off_t *offsets
1597 = svn_temp_deserializer__ptr(page, (const void *const *)&page->offsets);
1598 const apr_uint32_t *sub_items
1599 = svn_temp_deserializer__ptr(page, (const void *const *)&page->sub_items);
1601 /* return the requested data */
1602 return l2p_page_get_offset(baton, page, offsets, sub_items, result_pool);
1605 /* Data request structure used by l2p_page_table_access_func.
1607 typedef struct l2p_page_table_baton_t
1609 /* revision for which to read the page table */
1610 svn_revnum_t revision;
1612 /* page table entries (of type l2p_page_table_entry_t).
1613 * Must be created by caller and will be filled by callee. */
1614 apr_array_header_t *pages;
1615 } l2p_page_table_baton_t;
1617 /* Implement svn_cache__partial_getter_func_t: copy the data requested in
1618 * l2p_page_baton_t *BATON from l2p_page_t *DATA into BATON->PAGES and *OUT.
1620 static svn_error_t *
1621 l2p_page_table_access_func(void **out,
1623 apr_size_t data_len,
1625 apr_pool_t *result_pool)
1627 /* resolve in-cache pointers */
1628 l2p_page_table_baton_t *table_baton = baton;
1629 const l2p_header_t *header = (const l2p_header_t *)data;
1630 const l2p_page_table_entry_t *page_table
1631 = svn_temp_deserializer__ptr(header,
1632 (const void *const *)&header->page_table);
1633 const apr_size_t *page_table_index
1634 = svn_temp_deserializer__ptr(header,
1635 (const void *const *)&header->page_table_index);
1637 /* copy the revision's page table into BATON */
1638 apr_size_t rel_revision = table_baton->revision - header->first_revision;
1639 if (rel_revision < header->revision_count)
1641 const l2p_page_table_entry_t *entry
1642 = page_table + page_table_index[rel_revision];
1643 const l2p_page_table_entry_t *last_entry
1644 = page_table + page_table_index[rel_revision + 1];
1646 for (; entry < last_entry; ++entry)
1647 APR_ARRAY_PUSH(table_baton->pages, l2p_page_table_entry_t)
1651 /* set output as a courtesy to the caller */
1652 *out = table_baton->pages;
1654 return SVN_NO_ERROR;
1657 /* Read the l2p index page table for REVISION in FS from cache and return
1658 * it in PAGES. The later must be provided by the caller (and can be
1659 * re-used); existing entries will be removed before writing the result.
1660 * If the data cannot be found in the cache, the result will be empty
1661 * (it never can be empty for a valid REVISION if the data is cached).
1662 * Use the info from REV_FILE to determine pack / rev file properties.
1663 * Use SCRATCH_POOL for temporary allocations.
1665 static svn_error_t *
1666 get_l2p_page_table(apr_array_header_t *pages,
1668 svn_revnum_t revision,
1669 apr_pool_t *scratch_pool)
1671 svn_fs_x__data_t *ffd = fs->fsap_data;
1672 svn_boolean_t is_cached = FALSE;
1673 l2p_page_table_baton_t baton;
1675 svn_fs_x__pair_cache_key_t key;
1676 key.revision = base_revision(fs, revision);
1677 key.second = svn_fs_x__is_packed_rev(fs, revision);
1679 apr_array_clear(pages);
1680 baton.revision = revision;
1681 baton.pages = pages;
1682 SVN_ERR(svn_cache__get_partial((void**)&pages, &is_cached,
1683 ffd->l2p_header_cache, &key,
1684 l2p_page_table_access_func, &baton,
1687 return SVN_NO_ERROR;
1690 /* Utility function. Read the l2p index pages for REVISION in FS from
1691 * STREAM and put them into the cache. Skip page number EXLCUDED_PAGE_NO
1692 * (use -1 for 'skip none') and pages outside the MIN_OFFSET, MAX_OFFSET
1693 * range in the l2p index file. The index is being identified by
1694 * FIRST_REVISION. PAGES is a scratch container provided by the caller.
1695 * SCRATCH_POOL is used for temporary allocations.
1697 * This function may be a no-op if the header cache lookup fails / misses.
1699 static svn_error_t *
1700 prefetch_l2p_pages(svn_boolean_t *end,
1702 svn_fs_x__revision_file_t *rev_file,
1703 svn_revnum_t first_revision,
1704 svn_revnum_t revision,
1705 apr_array_header_t *pages,
1706 int exlcuded_page_no,
1707 apr_off_t min_offset,
1708 apr_off_t max_offset,
1709 apr_pool_t *scratch_pool)
1711 svn_fs_x__data_t *ffd = fs->fsap_data;
1713 apr_pool_t *iterpool;
1714 svn_fs_x__page_cache_key_t key = { 0 };
1716 /* Parameter check. */
1720 if (max_offset <= 0)
1724 return SVN_NO_ERROR;
1727 /* get the page table for REVISION from cache */
1729 SVN_ERR(get_l2p_page_table(pages, fs, revision, scratch_pool));
1730 if (pages->nelts == 0)
1732 /* not found -> we can't continue without hitting the disk again */
1734 return SVN_NO_ERROR;
1737 /* prefetch pages individually until all are done or we found one in
1739 iterpool = svn_pool_create(scratch_pool);
1740 assert(revision <= APR_UINT32_MAX);
1741 key.revision = (apr_uint32_t)revision;
1742 key.is_packed = svn_fs_x__is_packed_rev(fs, revision);
1744 for (i = 0; i < pages->nelts && !*end; ++i)
1746 svn_boolean_t is_cached;
1748 l2p_page_table_entry_t *entry
1749 = &APR_ARRAY_IDX(pages, i, l2p_page_table_entry_t);
1750 svn_pool_clear(iterpool);
1752 if (i == exlcuded_page_no)
1755 /* skip pages outside the specified index file range */
1756 if ( entry->offset < (apr_uint64_t)min_offset
1757 || entry->offset + entry->size > (apr_uint64_t)max_offset)
1763 /* page already in cache? */
1765 SVN_ERR(svn_cache__has_key(&is_cached, ffd->l2p_page_cache,
1769 /* no in cache -> read from stream (data already buffered in APR)
1770 * and cache the result */
1771 l2p_page_t *page = NULL;
1772 SVN_ERR(get_l2p_page(&page, rev_file, fs, first_revision,
1775 SVN_ERR(svn_cache__set(ffd->l2p_page_cache, &key, page,
1780 svn_pool_destroy(iterpool);
1782 return SVN_NO_ERROR;
1785 /* Using the log-to-phys indexes in FS, find the absolute offset in the
1786 * rev file for (REVISION, ITEM_INDEX) and return it in *OFFSET.
1787 * Use SCRATCH_POOL for temporary allocations.
1789 static svn_error_t *
1790 l2p_index_lookup(apr_off_t *offset,
1791 apr_uint32_t *sub_item,
1793 svn_fs_x__revision_file_t *rev_file,
1794 svn_revnum_t revision,
1795 apr_uint64_t item_index,
1796 apr_pool_t *scratch_pool)
1798 svn_fs_x__data_t *ffd = fs->fsap_data;
1799 l2p_page_info_baton_t info_baton;
1800 l2p_page_baton_t page_baton;
1801 l2p_page_t *page = NULL;
1802 svn_fs_x__page_cache_key_t key = { 0 };
1803 svn_boolean_t is_cached = FALSE;
1806 /* read index master data structure and extract the info required to
1807 * access the l2p index page for (REVISION,ITEM_INDEX)*/
1808 info_baton.revision = revision;
1809 info_baton.item_index = item_index;
1810 SVN_ERR(get_l2p_page_info(&info_baton, rev_file, fs, scratch_pool));
1812 /* try to find the page in the cache and get the OFFSET from it */
1813 page_baton.revision = revision;
1814 page_baton.item_index = item_index;
1815 page_baton.page_offset = info_baton.page_offset;
1817 assert(revision <= APR_UINT32_MAX);
1818 key.revision = (apr_uint32_t)revision;
1819 key.is_packed = svn_fs_x__is_packed_rev(fs, revision);
1820 key.page = info_baton.page_no;
1822 SVN_ERR(svn_cache__get_partial(&dummy, &is_cached,
1823 ffd->l2p_page_cache, &key,
1824 l2p_page_access_func, &page_baton,
1829 /* we need to read the info from disk (might already be in the
1830 * APR file buffer, though) */
1831 apr_array_header_t *pages;
1832 svn_revnum_t prefetch_revision;
1833 svn_revnum_t last_revision
1834 = info_baton.first_revision
1835 + svn_fs_x__pack_size(fs, info_baton.first_revision);
1836 apr_pool_t *iterpool = svn_pool_create(scratch_pool);
1838 apr_off_t max_offset
1839 = APR_ALIGN(info_baton.entry.offset + info_baton.entry.size,
1841 apr_off_t min_offset = max_offset - ffd->block_size;
1843 /* read the relevant page */
1844 SVN_ERR(get_l2p_page(&page, rev_file, fs, info_baton.first_revision,
1845 &info_baton.entry, scratch_pool));
1847 /* cache the page and extract the result we need */
1848 SVN_ERR(svn_cache__set(ffd->l2p_page_cache, &key, page, scratch_pool));
1849 SVN_ERR(l2p_page_get_offset(&page_baton, page, page->offsets,
1850 page->sub_items, scratch_pool));
1852 /* prefetch pages from following and preceding revisions */
1853 pages = apr_array_make(scratch_pool, 16,
1854 sizeof(l2p_page_table_entry_t));
1856 for (prefetch_revision = revision;
1857 prefetch_revision < last_revision && !end;
1858 ++prefetch_revision)
1860 int excluded_page_no = prefetch_revision == revision
1861 ? info_baton.page_no
1863 svn_pool_clear(iterpool);
1865 SVN_ERR(prefetch_l2p_pages(&end, fs, rev_file,
1866 info_baton.first_revision,
1867 prefetch_revision, pages,
1868 excluded_page_no, min_offset,
1869 max_offset, iterpool));
1873 for (prefetch_revision = revision-1;
1874 prefetch_revision >= info_baton.first_revision && !end;
1875 --prefetch_revision)
1877 svn_pool_clear(iterpool);
1879 SVN_ERR(prefetch_l2p_pages(&end, fs, rev_file,
1880 info_baton.first_revision,
1881 prefetch_revision, pages, -1,
1882 min_offset, max_offset, iterpool));
1885 svn_pool_destroy(iterpool);
1888 *offset = page_baton.offset;
1889 *sub_item = page_baton.sub_item;
1891 return SVN_NO_ERROR;
1894 /* Using the log-to-phys proto index in transaction TXN_ID in FS, find the
1895 * absolute offset in the proto rev file for the given ITEM_INDEX and return
1896 * it in *OFFSET. Use SCRATCH_POOL for temporary allocations.
1898 static svn_error_t *
1899 l2p_proto_index_lookup(apr_off_t *offset,
1900 apr_uint32_t *sub_item,
1902 svn_fs_x__txn_id_t txn_id,
1903 apr_uint64_t item_index,
1904 apr_pool_t *scratch_pool)
1906 svn_boolean_t eof = FALSE;
1907 apr_file_t *file = NULL;
1908 SVN_ERR(svn_io_file_open(&file,
1909 svn_fs_x__path_l2p_proto_index(fs, txn_id,
1911 APR_READ | APR_BUFFERED, APR_OS_DEFAULT,
1914 /* process all entries until we fail due to EOF */
1918 l2p_proto_entry_t entry;
1920 /* (attempt to) read the next entry from the source */
1921 SVN_ERR(read_l2p_entry_from_proto_index(file, &entry, &eof,
1924 /* handle new revision */
1925 if (!eof && entry.item_index == item_index)
1927 *offset = (apr_off_t)entry.offset - 1;
1928 *sub_item = entry.sub_item;
1933 SVN_ERR(svn_io_file_close(file, scratch_pool));
1935 return SVN_NO_ERROR;
1939 svn_fs_x__l2p_get_max_ids(apr_array_header_t **max_ids,
1941 svn_revnum_t start_rev,
1943 apr_pool_t *result_pool,
1944 apr_pool_t *scratch_pool)
1946 l2p_header_t *header = NULL;
1947 svn_revnum_t revision;
1948 svn_revnum_t last_rev = (svn_revnum_t)(start_rev + count);
1949 svn_fs_x__revision_file_t *rev_file;
1950 apr_pool_t *header_pool = svn_pool_create(scratch_pool);
1952 /* read index master data structure for the index covering START_REV */
1953 SVN_ERR(svn_fs_x__open_pack_or_rev_file(&rev_file, fs, start_rev,
1954 header_pool, header_pool));
1955 SVN_ERR(get_l2p_header(&header, rev_file, fs, start_rev, header_pool,
1957 SVN_ERR(svn_fs_x__close_revision_file(rev_file));
1959 /* Determine the length of the item index list for each rev.
1960 * Read new index headers as required. */
1961 *max_ids = apr_array_make(result_pool, (int)count, sizeof(apr_uint64_t));
1962 for (revision = start_rev; revision < last_rev; ++revision)
1964 apr_uint64_t full_page_count;
1965 apr_uint64_t item_count;
1966 apr_size_t first_page_index, last_page_index;
1968 if (revision >= header->first_revision + header->revision_count)
1970 /* need to read the next index. Clear up memory used for the
1971 * previous one. Note that intermittent pack runs do not change
1972 * the number of items in a revision, i.e. there is no consistency
1974 svn_pool_clear(header_pool);
1975 SVN_ERR(svn_fs_x__open_pack_or_rev_file(&rev_file, fs, revision,
1976 header_pool, header_pool));
1977 SVN_ERR(get_l2p_header(&header, rev_file, fs, revision,
1978 header_pool, header_pool));
1979 SVN_ERR(svn_fs_x__close_revision_file(rev_file));
1982 /* in a revision with N index pages, the first N-1 index pages are
1983 * "full", i.e. contain HEADER->PAGE_SIZE entries */
1985 = header->page_table_index[revision - header->first_revision];
1987 = header->page_table_index[revision - header->first_revision + 1];
1988 full_page_count = last_page_index - first_page_index - 1;
1989 item_count = full_page_count * header->page_size
1990 + header->page_table[last_page_index - 1].entry_count;
1992 APR_ARRAY_PUSH(*max_ids, apr_uint64_t) = item_count;
1995 svn_pool_destroy(header_pool);
1996 return SVN_NO_ERROR;
2002 svn_fs_x__p2l_entry_t *
2003 svn_fs_x__p2l_entry_dup(const svn_fs_x__p2l_entry_t *entry,
2004 apr_pool_t *result_pool)
2006 svn_fs_x__p2l_entry_t *new_entry = apr_pmemdup(result_pool, entry,
2007 sizeof(*new_entry));
2008 if (new_entry->item_count)
2009 new_entry->items = apr_pmemdup(result_pool,
2011 entry->item_count * sizeof(*entry->items));
2020 svn_fs_x__p2l_proto_index_open(apr_file_t **proto_index,
2021 const char *file_name,
2022 apr_pool_t *result_pool)
2024 SVN_ERR(svn_io_file_open(proto_index, file_name, APR_READ | APR_WRITE
2025 | APR_CREATE | APR_APPEND | APR_BUFFERED,
2026 APR_OS_DEFAULT, result_pool));
2028 return SVN_NO_ERROR;
2033 svn_fs_x__p2l_proto_index_add_entry(apr_file_t *proto_index,
2034 const svn_fs_x__p2l_entry_t *entry,
2035 apr_pool_t *scratch_pool)
2037 apr_uint64_t revision;
2040 /* Make sure all signed elements of ENTRY have non-negative values.
2042 * For file offsets and sizes, this is a given as we use them to describe
2043 * absolute positions and sizes. For revisions, SVN_INVALID_REVNUM is
2044 * valid, hence we have to shift it by 1.
2046 SVN_ERR_ASSERT(entry->offset >= 0);
2047 SVN_ERR_ASSERT(entry->size >= 0);
2049 /* Now, all values will nicely convert to uint64. */
2050 /* Make sure to keep P2L_PROTO_INDEX_ENTRY_SIZE consistent with this: */
2052 SVN_ERR(write_uint64_to_proto_index(proto_index, entry->offset,
2054 SVN_ERR(write_uint64_to_proto_index(proto_index, entry->size,
2056 SVN_ERR(write_uint64_to_proto_index(proto_index, entry->type,
2058 SVN_ERR(write_uint64_to_proto_index(proto_index, entry->fnv1_checksum,
2060 SVN_ERR(write_uint64_to_proto_index(proto_index, entry->item_count,
2063 /* Add sub-items. */
2064 for (i = 0; i < entry->item_count; ++i)
2066 const svn_fs_x__id_t *sub_item = &entry->items[i];
2068 /* Make sure all signed elements of ENTRY have non-negative values.
2070 * For file offsets and sizes, this is a given as we use them to
2071 * describe absolute positions and sizes. For revisions,
2072 * SVN_INVALID_REVNUM is valid, hence we have to shift it by 1.
2074 SVN_ERR_ASSERT( sub_item->change_set >= 0
2075 || sub_item->change_set == SVN_INVALID_REVNUM);
2077 /* Write sub- record. */
2078 revision = sub_item->change_set == SVN_INVALID_REVNUM
2080 : ((apr_uint64_t)sub_item->change_set + 1);
2082 SVN_ERR(write_uint64_to_proto_index(proto_index, revision,
2084 SVN_ERR(write_uint64_to_proto_index(proto_index, sub_item->number,
2088 /* Add trailer: rev / pack file offset of the next item */
2089 SVN_ERR(write_uint64_to_proto_index(proto_index,
2090 entry->offset + entry->size,
2093 return SVN_NO_ERROR;
2096 /* Read *ENTRY from log-to-phys PROTO_INDEX file and indicate end-of-file
2097 * in *EOF, or error out in that case if EOF is NULL. *ENTRY is in an
2098 * undefined state if an end-of-file occurred.
2099 * Use SCRATCH_POOL for temporary allocations.
2101 static svn_error_t *
2102 read_p2l_entry_from_proto_index(apr_file_t *proto_index,
2103 svn_fs_x__p2l_entry_t *entry,
2105 apr_pool_t *scratch_pool)
2107 SVN_ERR(read_off_t_from_proto_index(proto_index, &entry->offset,
2108 eof, scratch_pool));
2109 SVN_ERR(read_off_t_from_proto_index(proto_index, &entry->size,
2110 eof, scratch_pool));
2111 SVN_ERR(read_uint32_from_proto_index(proto_index, &entry->type,
2112 eof, scratch_pool));
2113 SVN_ERR(read_uint32_from_proto_index(proto_index, &entry->fnv1_checksum,
2114 eof, scratch_pool));
2115 SVN_ERR(read_uint32_from_proto_index(proto_index, &entry->item_count,
2116 eof, scratch_pool));
2118 return SVN_NO_ERROR;
2121 static svn_error_t *
2122 read_p2l_sub_items_from_proto_index(apr_file_t *proto_index,
2123 svn_fs_x__p2l_entry_t *entry,
2125 apr_pool_t *scratch_pool)
2128 for (i = 0; i < entry->item_count; ++i)
2130 apr_uint64_t revision;
2131 svn_fs_x__id_t *sub_item = &entry->items[i];
2133 SVN_ERR(read_uint64_from_proto_index(proto_index, &revision,
2134 eof, scratch_pool));
2135 SVN_ERR(read_uint64_from_proto_index(proto_index, &sub_item->number,
2136 eof, scratch_pool));
2138 /* Do the inverse REVSION number conversion (see
2139 * svn_fs_x__p2l_proto_index_add_entry), if we actually read a
2144 /* Be careful with the arithmetics here (overflows and wrap-around):
2146 if (revision > 0 && revision - 1 > LONG_MAX)
2147 return svn_error_createf(SVN_ERR_FS_INDEX_OVERFLOW, NULL,
2148 _("Revision 0x%s too large, max = 0x%s"),
2149 apr_psprintf(scratch_pool,
2150 "%" APR_UINT64_T_FMT,
2152 apr_psprintf(scratch_pool,
2153 "%" APR_UINT64_T_FMT,
2154 (apr_uint64_t)LONG_MAX));
2156 /* Shortening conversion from unsigned to signed int is well-
2157 * defined and not lossy in C because the value can be represented
2158 * in the target type. Also, cast to 'long' instead of
2159 * 'svn_revnum_t' here to provoke a compiler warning if those
2160 * types should differ and we would need to change the overflow
2163 sub_item->change_set = revision == 0
2164 ? SVN_INVALID_REVNUM
2165 : (long)(revision - 1);
2170 return SVN_NO_ERROR;
2174 svn_fs_x__p2l_proto_index_next_offset(apr_off_t *next_offset,
2175 apr_file_t *proto_index,
2176 apr_pool_t *scratch_pool)
2178 apr_off_t offset = 0;
2180 /* Empty index file? */
2181 SVN_ERR(svn_io_file_seek(proto_index, APR_END, &offset, scratch_pool));
2188 /* The last 64 bits contain the value we are looking for. */
2189 offset -= sizeof(apr_uint64_t);
2190 SVN_ERR(svn_io_file_seek(proto_index, APR_SET, &offset, scratch_pool));
2191 SVN_ERR(read_off_t_from_proto_index(proto_index, next_offset, NULL,
2195 return SVN_NO_ERROR;
2199 svn_fs_x__p2l_index_append(svn_checksum_t **checksum,
2201 apr_file_t *index_file,
2202 const char *proto_file_name,
2203 svn_revnum_t revision,
2204 apr_pool_t *result_pool,
2205 apr_pool_t *scratch_pool)
2207 svn_fs_x__data_t *ffd = fs->fsap_data;
2208 apr_uint64_t page_size = ffd->p2l_page_size;
2209 apr_file_t *proto_index = NULL;
2210 svn_stream_t *stream;
2212 apr_uint32_t sub_item;
2213 svn_boolean_t eof = FALSE;
2214 unsigned char encoded[ENCODED_INT_LENGTH];
2216 apr_uint64_t last_entry_end = 0;
2217 apr_uint64_t last_page_end = 0;
2218 apr_size_t last_buffer_size = 0; /* byte offset in the spill buffer at
2219 the begin of the current revision */
2220 apr_uint64_t file_size = 0;
2222 /* temporary data structures that collect the data which will be moved
2223 to the target file in a second step */
2224 apr_pool_t *local_pool = svn_pool_create(scratch_pool);
2225 apr_array_header_t *table_sizes
2226 = apr_array_make(local_pool, 16, sizeof(apr_uint64_t));
2228 /* 64k blocks, spill after 16MB */
2229 svn_spillbuf_t *buffer
2230 = svn_spillbuf__create(0x10000, 0x1000000, local_pool);
2232 /* for loop temps ... */
2233 apr_pool_t *iterpool = svn_pool_create(scratch_pool);
2235 /* start at the beginning of the source file */
2236 SVN_ERR(svn_io_file_open(&proto_index, proto_file_name,
2237 APR_READ | APR_CREATE | APR_BUFFERED,
2238 APR_OS_DEFAULT, local_pool));
2240 /* process all entries until we fail due to EOF */
2243 svn_fs_x__p2l_entry_t entry;
2244 apr_uint64_t entry_end;
2245 svn_boolean_t new_page = svn_spillbuf__get_size(buffer) == 0;
2246 svn_revnum_t last_revision = revision;
2247 apr_uint64_t last_number = 0;
2249 svn_pool_clear(iterpool);
2251 /* (attempt to) read the next entry from the source */
2252 SVN_ERR(read_p2l_entry_from_proto_index(proto_index, &entry,
2255 if (entry.item_count && !eof)
2257 entry.items = apr_palloc(iterpool,
2258 entry.item_count * sizeof(*entry.items));
2259 SVN_ERR(read_p2l_sub_items_from_proto_index(proto_index, &entry,
2263 /* Read entry trailer. However, we won't need its content. */
2266 apr_uint64_t trailer;
2267 SVN_ERR(read_uint64_from_proto_index(proto_index, &trailer, &eof,
2271 /* "unused" (and usually non-existent) section to cover the offsets
2272 at the end the of the last page. */
2275 file_size = last_entry_end;
2277 entry.offset = last_entry_end;
2278 entry.size = APR_ALIGN(entry.offset, page_size) - entry.offset;
2279 entry.type = SVN_FS_X__ITEM_TYPE_UNUSED;
2280 entry.fnv1_checksum = 0;
2281 entry.item_count = 0;
2285 for (sub_item = 0; sub_item < entry.item_count; ++sub_item)
2286 if (entry.items[sub_item].change_set == SVN_FS_X__INVALID_CHANGE_SET)
2287 entry.items[sub_item].change_set
2288 = svn_fs_x__change_set_by_rev(revision);
2290 /* end pages if entry is extending beyond their boundaries */
2291 entry_end = entry.offset + entry.size;
2292 while (entry_end - last_page_end > page_size)
2294 apr_uint64_t buffer_size = svn_spillbuf__get_size(buffer);
2295 APR_ARRAY_PUSH(table_sizes, apr_uint64_t)
2296 = buffer_size - last_buffer_size;
2298 last_buffer_size = buffer_size;
2299 last_page_end += page_size;
2303 /* this entry starts a new table -> store its offset
2304 (all following entries in the same table will store sizes only) */
2307 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded,
2308 encode_uint(encoded, entry.offset),
2310 last_revision = revision;
2313 /* write simple item / container entry */
2314 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded,
2315 encode_uint(encoded, entry.size),
2317 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded,
2318 encode_uint(encoded, entry.type + entry.item_count * 16),
2320 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded,
2321 encode_uint(encoded, entry.fnv1_checksum),
2324 /* container contents (only one for non-container items) */
2325 for (sub_item = 0; sub_item < entry.item_count; ++sub_item)
2327 svn_revnum_t item_rev
2328 = svn_fs_x__get_revnum(entry.items[sub_item].change_set);
2329 apr_int64_t diff = item_rev - last_revision;
2330 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded,
2331 encode_int(encoded, diff),
2333 last_revision = item_rev;
2336 for (sub_item = 0; sub_item < entry.item_count; ++sub_item)
2338 apr_int64_t diff = entry.items[sub_item].number - last_number;
2339 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded,
2340 encode_int(encoded, diff),
2342 last_number = entry.items[sub_item].number;
2345 last_entry_end = entry_end;
2348 /* close the source file */
2349 SVN_ERR(svn_io_file_close(proto_index, local_pool));
2351 /* store length of last table */
2352 APR_ARRAY_PUSH(table_sizes, apr_uint64_t)
2353 = svn_spillbuf__get_size(buffer) - last_buffer_size;
2355 /* Open target stream. */
2356 stream = svn_stream_checksummed2(svn_stream_from_aprfile2(index_file, TRUE,
2358 NULL, checksum, svn_checksum_md5, FALSE,
2361 /* write the start revision, file size and page size */
2362 SVN_ERR(svn_stream_puts(stream, P2L_STREAM_PREFIX));
2363 SVN_ERR(stream_write_encoded(stream, revision));
2364 SVN_ERR(stream_write_encoded(stream, file_size));
2365 SVN_ERR(stream_write_encoded(stream, page_size));
2367 /* write the page table (actually, the sizes of each page description) */
2368 SVN_ERR(stream_write_encoded(stream, table_sizes->nelts));
2369 for (i = 0; i < table_sizes->nelts; ++i)
2371 apr_uint64_t value = APR_ARRAY_IDX(table_sizes, i, apr_uint64_t);
2372 SVN_ERR(stream_write_encoded(stream, value));
2375 /* append page contents and implicitly close STREAM */
2376 SVN_ERR(svn_stream_copy3(svn_stream__from_spillbuf(buffer, local_pool),
2377 stream, NULL, NULL, local_pool));
2379 svn_pool_destroy(iterpool);
2380 svn_pool_destroy(local_pool);
2382 return SVN_NO_ERROR;
2385 /* If REV_FILE->P2L_STREAM is NULL, create a new stream for the phys-to-log
2386 * index for REVISION in FS using the rev / pack file provided by REV_FILE.
2388 static svn_error_t *
2389 auto_open_p2l_index(svn_fs_x__revision_file_t *rev_file,
2391 svn_revnum_t revision)
2393 if (rev_file->p2l_stream == NULL)
2395 svn_fs_x__data_t *ffd = fs->fsap_data;
2397 SVN_ERR(svn_fs_x__auto_read_footer(rev_file));
2398 SVN_ERR(packed_stream_open(&rev_file->p2l_stream,
2400 rev_file->p2l_offset,
2401 rev_file->footer_offset,
2403 (apr_size_t)ffd->block_size,
2408 return SVN_NO_ERROR;
2411 /* Data structure that describes which p2l page info shall be extracted
2412 * from the cache and contains the fields that receive the result.
2414 typedef struct p2l_page_info_baton_t
2416 /* input variables */
2417 /* revision identifying the index file */
2418 svn_revnum_t revision;
2420 /* offset within the page in rev / pack file */
2423 /* output variables */
2424 /* page containing OFFSET */
2427 /* first revision in this p2l index */
2428 svn_revnum_t first_revision;
2430 /* offset within the p2l index file describing this page */
2431 apr_off_t start_offset;
2433 /* offset within the p2l index file describing the following page */
2434 apr_off_t next_offset;
2436 /* PAGE_NO * PAGE_SIZE (if <= OFFSET) */
2437 apr_off_t page_start;
2439 /* total number of pages indexed */
2440 apr_size_t page_count;
2442 /* size of each page in pack / rev file */
2443 apr_uint64_t page_size;
2444 } p2l_page_info_baton_t;
2446 /* From HEADER and the list of all OFFSETS, fill BATON with the page info
2447 * requested by BATON->OFFSET.
2450 p2l_page_info_copy(p2l_page_info_baton_t *baton,
2451 const p2l_header_t *header,
2452 const apr_off_t *offsets)
2454 /* if the requested offset is out of bounds, return info for
2455 * a zero-sized empty page right behind the last page.
2457 if (baton->offset / header->page_size < header->page_count)
2459 /* This cast is safe because the value is < header->page_count. */
2460 baton->page_no = (apr_size_t)(baton->offset / header->page_size);
2461 baton->start_offset = offsets[baton->page_no];
2462 baton->next_offset = offsets[baton->page_no + 1];
2463 baton->page_size = header->page_size;
2467 /* Beyond the last page. */
2468 baton->page_no = header->page_count;
2469 baton->start_offset = offsets[baton->page_no];
2470 baton->next_offset = offsets[baton->page_no];
2471 baton->page_size = 0;
2474 baton->first_revision = header->first_revision;
2475 baton->page_start = (apr_off_t)(header->page_size * baton->page_no);
2476 baton->page_count = header->page_count;
2479 /* Implement svn_cache__partial_getter_func_t: extract the p2l page info
2480 * requested by BATON and return it in BATON.
2482 static svn_error_t *
2483 p2l_page_info_func(void **out,
2485 apr_size_t data_len,
2487 apr_pool_t *result_pool)
2489 /* all the pointers to cached data we need */
2490 const p2l_header_t *header = data;
2491 const apr_off_t *offsets
2492 = svn_temp_deserializer__ptr(header,
2493 (const void *const *)&header->offsets);
2495 /* copy data from cache to BATON */
2496 p2l_page_info_copy(baton, header, offsets);
2497 return SVN_NO_ERROR;
2500 /* Read the header data structure of the phys-to-log index for REVISION in
2501 * FS and return it in *HEADER, allocated in RESULT_POOL. Use REV_FILE to
2502 * access on-disk data. Use SCRATCH_POOL for temporary allocations.
2504 static svn_error_t *
2505 get_p2l_header(p2l_header_t **header,
2506 svn_fs_x__revision_file_t *rev_file,
2508 svn_revnum_t revision,
2509 apr_pool_t *result_pool,
2510 apr_pool_t *scratch_pool)
2512 svn_fs_x__data_t *ffd = fs->fsap_data;
2516 p2l_header_t *result;
2517 svn_boolean_t is_cached = FALSE;
2519 /* look for the header data in our cache */
2520 svn_fs_x__pair_cache_key_t key;
2521 key.revision = rev_file->start_revision;
2522 key.second = rev_file->is_packed;
2524 SVN_ERR(svn_cache__get((void**)header, &is_cached, ffd->p2l_header_cache,
2525 &key, result_pool));
2527 return SVN_NO_ERROR;
2529 /* not found -> must read it from disk.
2530 * Open index file or position read pointer to the begin of the file */
2531 SVN_ERR(auto_open_p2l_index(rev_file, fs, key.revision));
2532 packed_stream_seek(rev_file->p2l_stream, 0);
2534 /* allocate result data structure */
2535 result = apr_pcalloc(result_pool, sizeof(*result));
2537 /* Read table sizes, check them for plausibility and allocate page array. */
2538 SVN_ERR(packed_stream_get(&value, rev_file->p2l_stream));
2539 result->first_revision = (svn_revnum_t)value;
2540 if (result->first_revision != rev_file->start_revision)
2541 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
2542 _("Index rev / pack file revision numbers do not match"));
2544 SVN_ERR(packed_stream_get(&value, rev_file->p2l_stream));
2545 result->file_size = value;
2546 if (result->file_size != (apr_uint64_t)rev_file->l2p_offset)
2547 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
2548 _("Index offset and rev / pack file size do not match"));
2550 SVN_ERR(packed_stream_get(&value, rev_file->p2l_stream));
2551 result->page_size = value;
2552 if (!result->page_size || (result->page_size & (result->page_size - 1)))
2553 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
2554 _("P2L index page size is not a power of two"));
2556 SVN_ERR(packed_stream_get(&value, rev_file->p2l_stream));
2557 result->page_count = (apr_size_t)value;
2558 if (result->page_count != (result->file_size - 1) / result->page_size + 1)
2559 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
2560 _("P2L page count does not match rev / pack file size"));
2563 = apr_pcalloc(result_pool, (result->page_count + 1) * sizeof(*result->offsets));
2565 /* read page sizes and derive page description offsets from them */
2566 result->offsets[0] = 0;
2567 for (i = 0; i < result->page_count; ++i)
2569 SVN_ERR(packed_stream_get(&value, rev_file->p2l_stream));
2570 result->offsets[i+1] = result->offsets[i] + (apr_off_t)value;
2573 /* correct the offset values */
2574 offset = packed_stream_offset(rev_file->p2l_stream);
2575 for (i = 0; i <= result->page_count; ++i)
2576 result->offsets[i] += offset;
2578 /* cache the header data */
2579 SVN_ERR(svn_cache__set(ffd->p2l_header_cache, &key, result, scratch_pool));
2581 /* return the result */
2584 return SVN_NO_ERROR;
2587 /* Read the header data structure of the phys-to-log index for revision
2588 * BATON->REVISION in FS. Return in *BATON all info relevant to read the
2589 * index page for the rev / pack file offset BATON->OFFSET. Use REV_FILE
2590 * to access on-disk data. Use SCRATCH_POOL for temporary allocations.
2592 static svn_error_t *
2593 get_p2l_page_info(p2l_page_info_baton_t *baton,
2594 svn_fs_x__revision_file_t *rev_file,
2596 apr_pool_t *scratch_pool)
2598 svn_fs_x__data_t *ffd = fs->fsap_data;
2599 p2l_header_t *header;
2600 svn_boolean_t is_cached = FALSE;
2603 /* look for the header data in our cache */
2604 svn_fs_x__pair_cache_key_t key;
2605 key.revision = base_revision(fs, baton->revision);
2606 key.second = svn_fs_x__is_packed_rev(fs, baton->revision);
2608 SVN_ERR(svn_cache__get_partial(&dummy, &is_cached, ffd->p2l_header_cache,
2609 &key, p2l_page_info_func, baton,
2612 return SVN_NO_ERROR;
2614 SVN_ERR(get_p2l_header(&header, rev_file, fs, baton->revision,
2615 scratch_pool, scratch_pool));
2617 /* copy the requested info into *BATON */
2618 p2l_page_info_copy(baton, header, header->offsets);
2620 return SVN_NO_ERROR;
2623 /* Read a mapping entry from the phys-to-log index STREAM and append it to
2624 * RESULT. *ITEM_INDEX contains the phys offset for the entry and will
2625 * be moved forward by the size of entry.
2627 static svn_error_t *
2628 read_entry(svn_fs_x__packed_number_stream_t *stream,
2629 apr_off_t *item_offset,
2630 svn_revnum_t revision,
2631 apr_array_header_t *result)
2634 apr_uint64_t number = 0;
2635 apr_uint32_t sub_item;
2637 svn_fs_x__p2l_entry_t entry;
2639 entry.offset = *item_offset;
2640 SVN_ERR(packed_stream_get(&value, stream));
2641 entry.size = (apr_off_t)value;
2642 SVN_ERR(packed_stream_get(&value, stream));
2643 entry.type = (int)value % 16;
2644 entry.item_count = (apr_uint32_t)(value / 16);
2646 /* Verify item type. */
2647 if (entry.type > SVN_FS_X__ITEM_TYPE_REPS_CONT)
2648 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
2649 _("Invalid item type in P2L index"));
2651 SVN_ERR(packed_stream_get(&value, stream));
2652 entry.fnv1_checksum = (apr_uint32_t)value;
2654 /* Truncating the checksum to 32 bits may have hidden random data in the
2655 * unused extra bits of the on-disk representation (7/8 bit representation
2656 * uses 5 bytes on disk for the 32 bit value, leaving 3 bits unused). */
2657 if (value > APR_UINT32_MAX)
2658 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
2659 _("Invalid FNV1 checksum in P2L index"));
2661 /* Some of the index data for empty rev / pack file sections will not be
2662 * used during normal operation. Thus, we have strict rules for the
2663 * contents of those unused fields. */
2664 if (entry.type == SVN_FS_X__ITEM_TYPE_UNUSED)
2665 if ( entry.fnv1_checksum != 0
2666 || entry.item_count != 0)
2667 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
2668 _("Unused regions must be empty and have checksum 0"));
2670 if (entry.item_count == 0)
2677 = apr_pcalloc(result->pool, entry.item_count * sizeof(*entry.items));
2679 if ( entry.item_count > 1
2680 && entry.type < SVN_FS_X__ITEM_TYPE_CHANGES_CONT)
2681 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
2682 _("Only containers may have more than one sub-item"));
2684 for (sub_item = 0; sub_item < entry.item_count; ++sub_item)
2686 SVN_ERR(packed_stream_get(&value, stream));
2687 revision += (svn_revnum_t)(value % 2 ? -1 - value / 2 : value / 2);
2688 entry.items[sub_item].change_set
2689 = svn_fs_x__change_set_by_rev(revision);
2692 for (sub_item = 0; sub_item < entry.item_count; ++sub_item)
2694 SVN_ERR(packed_stream_get(&value, stream));
2695 number += value % 2 ? -1 - value / 2 : value / 2;
2696 entry.items[sub_item].number = number;
2698 if ( ( entry.type == SVN_FS_X__ITEM_TYPE_CHANGES
2699 || entry.type == SVN_FS_X__ITEM_TYPE_CHANGES_CONT)
2700 && number != SVN_FS_X__ITEM_INDEX_CHANGES)
2701 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
2702 _("Changed path list must have item number 1"));
2706 APR_ARRAY_PUSH(result, svn_fs_x__p2l_entry_t) = entry;
2707 *item_offset += entry.size;
2709 return SVN_NO_ERROR;
2712 /* Read the phys-to-log mappings for the cluster beginning at rev file
2713 * offset PAGE_START from the index for START_REVISION in FS. The data
2714 * can be found in the index page beginning at START_OFFSET with the next
2715 * page beginning at NEXT_OFFSET. PAGE_SIZE is the L2P index page size.
2716 * Return the relevant index entries in *ENTRIES. Use REV_FILE to access
2717 * on-disk data. Allocate *ENTRIES in RESULT_POOL.
2719 static svn_error_t *
2720 get_p2l_page(apr_array_header_t **entries,
2721 svn_fs_x__revision_file_t *rev_file,
2723 svn_revnum_t start_revision,
2724 apr_off_t start_offset,
2725 apr_off_t next_offset,
2726 apr_off_t page_start,
2727 apr_uint64_t page_size,
2728 apr_pool_t *result_pool)
2731 apr_array_header_t *result
2732 = apr_array_make(result_pool, 16, sizeof(svn_fs_x__p2l_entry_t));
2733 apr_off_t item_offset;
2736 /* open index and navigate to page start */
2737 SVN_ERR(auto_open_p2l_index(rev_file, fs, start_revision));
2738 packed_stream_seek(rev_file->p2l_stream, start_offset);
2740 /* read rev file offset of the first page entry (all page entries will
2741 * only store their sizes). */
2742 SVN_ERR(packed_stream_get(&value, rev_file->p2l_stream));
2743 item_offset = (apr_off_t)value;
2745 /* Special case: empty pages. */
2746 if (start_offset == next_offset)
2748 /* Empty page. This only happens if the first entry of the next page
2749 * also covers this page (and possibly more) completely. */
2750 SVN_ERR(read_entry(rev_file->p2l_stream, &item_offset, start_revision,
2755 /* Read non-empty page. */
2758 SVN_ERR(read_entry(rev_file->p2l_stream, &item_offset,
2759 start_revision, result));
2760 offset = packed_stream_offset(rev_file->p2l_stream);
2762 while (offset < next_offset);
2764 /* We should now be exactly at the next offset, i.e. the numbers in
2765 * the stream cannot overlap into the next page description. */
2766 if (offset != next_offset)
2767 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL,
2768 _("P2L page description overlaps with next page description"));
2770 /* if we haven't covered the cluster end yet, we must read the first
2771 * entry of the next page */
2772 if (item_offset < page_start + page_size)
2774 SVN_ERR(packed_stream_get(&value, rev_file->p2l_stream));
2775 item_offset = (apr_off_t)value;
2776 SVN_ERR(read_entry(rev_file->p2l_stream, &item_offset,
2777 start_revision, result));
2783 return SVN_NO_ERROR;
2786 /* If it cannot be found in FS's caches, read the p2l index page selected
2787 * by BATON->OFFSET from *STREAM. If the latter is yet to be constructed,
2788 * do so in STREAM_POOL. Don't read the page if it precedes MIN_OFFSET.
2789 * Set *END to TRUE if the caller should stop refeching.
2791 * *BATON will be updated with the selected page's info and SCRATCH_POOL
2792 * will be used for temporary allocations. If the data is alread in the
2793 * cache, descrease *LEAKING_BUCKET and increase it otherwise. With that
2794 * pattern we will still read all pages from the block even if some of
2795 * them survived in the cached.
2797 static svn_error_t *
2798 prefetch_p2l_page(svn_boolean_t *end,
2799 int *leaking_bucket,
2801 svn_fs_x__revision_file_t *rev_file,
2802 p2l_page_info_baton_t *baton,
2803 apr_off_t min_offset,
2804 apr_pool_t *scratch_pool)
2806 svn_fs_x__data_t *ffd = fs->fsap_data;
2807 svn_boolean_t already_cached;
2808 apr_array_header_t *page;
2809 svn_fs_x__page_cache_key_t key = { 0 };
2811 /* fetch the page info */
2813 baton->revision = baton->first_revision;
2814 SVN_ERR(get_p2l_page_info(baton, rev_file, fs, scratch_pool));
2815 if (baton->start_offset < min_offset)
2817 /* page outside limits -> stop prefetching */
2819 return SVN_NO_ERROR;
2822 /* do we have that page in our caches already? */
2823 assert(baton->first_revision <= APR_UINT32_MAX);
2824 key.revision = (apr_uint32_t)baton->first_revision;
2825 key.is_packed = svn_fs_x__is_packed_rev(fs, baton->first_revision);
2826 key.page = baton->page_no;
2827 SVN_ERR(svn_cache__has_key(&already_cached, ffd->p2l_page_cache,
2828 &key, scratch_pool));
2830 /* yes, already cached */
2833 /* stop prefetching if most pages are already cached. */
2834 if (!--*leaking_bucket)
2837 return SVN_NO_ERROR;
2842 /* read from disk */
2843 SVN_ERR(get_p2l_page(&page, rev_file, fs,
2844 baton->first_revision,
2845 baton->start_offset,
2851 /* and put it into our cache */
2852 SVN_ERR(svn_cache__set(ffd->p2l_page_cache, &key, page, scratch_pool));
2854 return SVN_NO_ERROR;
2857 /* Lookup & construct the baton and key information that we will need for
2858 * a P2L page cache lookup. We want the page covering OFFSET in the rev /
2859 * pack file containing REVSION in FS. Return the results in *PAGE_INFO_P
2860 * and *KEY_P. Read data through REV_FILE. Use SCRATCH_POOL for temporary
2863 static svn_error_t *
2864 get_p2l_keys(p2l_page_info_baton_t *page_info_p,
2865 svn_fs_x__page_cache_key_t *key_p,
2866 svn_fs_x__revision_file_t *rev_file,
2868 svn_revnum_t revision,
2870 apr_pool_t *scratch_pool)
2872 p2l_page_info_baton_t page_info;
2874 /* request info for the index pages that describes the pack / rev file
2875 * contents at pack / rev file position OFFSET. */
2876 page_info.offset = offset;
2877 page_info.revision = revision;
2878 SVN_ERR(get_p2l_page_info(&page_info, rev_file, fs, scratch_pool));
2880 /* if the offset refers to a non-existent page, bail out */
2881 if (page_info.page_count <= page_info.page_no)
2882 return svn_error_createf(SVN_ERR_FS_INDEX_OVERFLOW , NULL,
2883 _("Offset %s too large in revision %ld"),
2884 apr_off_t_toa(scratch_pool, offset), revision);
2886 /* return results */
2888 *page_info_p = page_info;
2890 /* construct cache key */
2893 svn_fs_x__page_cache_key_t key = { 0 };
2894 assert(page_info.first_revision <= APR_UINT32_MAX);
2895 key.revision = (apr_uint32_t)page_info.first_revision;
2896 key.is_packed = svn_fs_x__is_packed_rev(fs, revision);
2897 key.page = page_info.page_no;
2902 return SVN_NO_ERROR;
2905 /* qsort-compatible compare function that compares the OFFSET of the
2906 * svn_fs_x__p2l_entry_t in *LHS with the apr_off_t in *RHS. */
2908 compare_start_p2l_entry(const void *lhs,
2911 const svn_fs_x__p2l_entry_t *entry = lhs;
2912 apr_off_t start = *(const apr_off_t*)rhs;
2913 apr_off_t diff = entry->offset - start;
2915 /* restrict result to int */
2916 return diff < 0 ? -1 : (diff == 0 ? 0 : 1);
2919 /* From the PAGE_ENTRIES array of svn_fs_x__p2l_entry_t, ordered
2920 * by their OFFSET member, copy all elements overlapping the range
2921 * [BLOCK_START, BLOCK_END) to ENTRIES. If RESOLVE_PTR is set, the ITEMS
2922 * sub-array in each entry needs to be de-serialized. */
2924 append_p2l_entries(apr_array_header_t *entries,
2925 apr_array_header_t *page_entries,
2926 apr_off_t block_start,
2927 apr_off_t block_end,
2928 svn_boolean_t resolve_ptr)
2930 const svn_fs_x__p2l_entry_t *entry;
2931 int idx = svn_sort__bsearch_lower_bound(page_entries, &block_start,
2932 compare_start_p2l_entry);
2934 /* start at the first entry that overlaps with BLOCK_START */
2937 entry = &APR_ARRAY_IDX(page_entries, idx - 1, svn_fs_x__p2l_entry_t);
2938 if (entry->offset + entry->size > block_start)
2942 /* copy all entries covering the requested range */
2943 for ( ; idx < page_entries->nelts; ++idx)
2945 svn_fs_x__p2l_entry_t *copy;
2946 entry = &APR_ARRAY_IDX(page_entries, idx, svn_fs_x__p2l_entry_t);
2947 if (entry->offset >= block_end)
2950 /* Copy the entry record. */
2951 copy = apr_array_push(entries);
2954 /* Copy the items of that entries. */
2955 if (entry->item_count)
2957 const svn_fs_x__id_t *items
2959 ? svn_temp_deserializer__ptr(page_entries->elts,
2960 (const void * const *)&entry->items)
2963 copy->items = apr_pmemdup(entries->pool, items,
2964 entry->item_count * sizeof(*items));
2969 /* Auxilliary struct passed to p2l_entries_func selecting the relevant
2971 typedef struct p2l_entries_baton_t
2975 } p2l_entries_baton_t;
2977 /* Implement svn_cache__partial_getter_func_t: extract p2l entries from
2978 * the page in DATA which overlap the p2l_entries_baton_t in BATON.
2979 * The target array is already provided in *OUT.
2981 static svn_error_t *
2982 p2l_entries_func(void **out,
2984 apr_size_t data_len,
2986 apr_pool_t *result_pool)
2988 apr_array_header_t *entries = *(apr_array_header_t **)out;
2989 const apr_array_header_t *raw_page = data;
2990 p2l_entries_baton_t *block = baton;
2992 /* Make PAGE a readable APR array. */
2993 apr_array_header_t page = *raw_page;
2994 page.elts = (void *)svn_temp_deserializer__ptr(raw_page,
2995 (const void * const *)&raw_page->elts);
2997 /* append relevant information to result */
2998 append_p2l_entries(entries, &page, block->start, block->end, TRUE);
3000 return SVN_NO_ERROR;
3004 /* Body of svn_fs_x__p2l_index_lookup. However, do a single index page
3005 * lookup and append the result to the ENTRIES array provided by the caller.
3006 * Use successive calls to cover larger ranges.
3008 static svn_error_t *
3009 p2l_index_lookup(apr_array_header_t *entries,
3010 svn_fs_x__revision_file_t *rev_file,
3012 svn_revnum_t revision,
3013 apr_off_t block_start,
3014 apr_off_t block_end,
3015 apr_pool_t *scratch_pool)
3017 svn_fs_x__data_t *ffd = fs->fsap_data;
3018 svn_fs_x__page_cache_key_t key;
3019 svn_boolean_t is_cached = FALSE;
3020 p2l_page_info_baton_t page_info;
3021 apr_array_header_t *local_result = entries;
3023 /* baton selecting the relevant entries from the one page we access */
3024 p2l_entries_baton_t block;
3025 block.start = block_start;
3026 block.end = block_end;
3028 /* if we requested an empty range, the result would be empty */
3029 SVN_ERR_ASSERT(block_start < block_end);
3031 /* look for the fist page of the range in our cache */
3032 SVN_ERR(get_p2l_keys(&page_info, &key, rev_file, fs, revision, block_start,
3034 SVN_ERR(svn_cache__get_partial((void**)&local_result, &is_cached,
3035 ffd->p2l_page_cache, &key, p2l_entries_func,
3036 &block, scratch_pool));
3041 apr_pool_t *iterpool = svn_pool_create(scratch_pool);
3042 apr_off_t original_page_start = page_info.page_start;
3043 int leaking_bucket = 4;
3044 p2l_page_info_baton_t prefetch_info = page_info;
3045 apr_array_header_t *page_entries;
3047 apr_off_t max_offset
3048 = APR_ALIGN(page_info.next_offset, ffd->block_size);
3049 apr_off_t min_offset
3050 = APR_ALIGN(page_info.start_offset, ffd->block_size) - ffd->block_size;
3052 /* Since we read index data in larger chunks, we probably got more
3053 * page data than we requested. Parse & cache that until either we
3054 * encounter pages already cached or reach the end of the buffer.
3057 /* pre-fetch preceding pages */
3059 prefetch_info.offset = original_page_start;
3060 while (prefetch_info.offset >= prefetch_info.page_size && !end)
3062 prefetch_info.offset -= prefetch_info.page_size;
3063 SVN_ERR(prefetch_p2l_page(&end, &leaking_bucket, fs, rev_file,
3064 &prefetch_info, min_offset, iterpool));
3065 svn_pool_clear(iterpool);
3068 /* fetch page from disk and put it into the cache */
3069 SVN_ERR(get_p2l_page(&page_entries, rev_file, fs,
3070 page_info.first_revision,
3071 page_info.start_offset,
3072 page_info.next_offset,
3073 page_info.page_start,
3074 page_info.page_size, iterpool));
3076 /* The last cache entry must not end beyond the range covered by
3077 * this index. The same applies for any subset of entries. */
3078 if (page_entries->nelts)
3080 const svn_fs_x__p2l_entry_t *entry
3081 = &APR_ARRAY_IDX(page_entries, page_entries->nelts - 1,
3082 svn_fs_x__p2l_entry_t);
3083 if ( entry->offset + entry->size
3084 > page_info.page_size * page_info.page_count)
3085 return svn_error_createf(SVN_ERR_FS_INDEX_OVERFLOW , NULL,
3086 _("Last P2L index entry extends beyond "
3087 "the last page in revision %ld."),
3091 SVN_ERR(svn_cache__set(ffd->p2l_page_cache, &key, page_entries,
3094 /* append relevant information to result */
3095 append_p2l_entries(entries, page_entries, block_start, block_end, FALSE);
3097 /* pre-fetch following pages */
3100 prefetch_info = page_info;
3101 prefetch_info.offset = original_page_start;
3102 while ( prefetch_info.next_offset < max_offset
3103 && prefetch_info.page_no + 1 < prefetch_info.page_count
3106 prefetch_info.offset += prefetch_info.page_size;
3107 SVN_ERR(prefetch_p2l_page(&end, &leaking_bucket, fs, rev_file,
3108 &prefetch_info, min_offset, iterpool));
3109 svn_pool_clear(iterpool);
3112 svn_pool_destroy(iterpool);
3115 /* We access a valid page (otherwise, we had seen an error in the
3116 * get_p2l_keys request). Hence, at least one entry must be found. */
3117 SVN_ERR_ASSERT(entries->nelts > 0);
3119 /* Add an "unused" entry if it extends beyond the end of the data file.
3120 * Since the index page size might be smaller than the current data
3121 * read block size, the trailing "unused" entry in this index may not
3122 * fully cover the end of the last block. */
3123 if (page_info.page_no + 1 >= page_info.page_count)
3125 svn_fs_x__p2l_entry_t *entry
3126 = &APR_ARRAY_IDX(entries, entries->nelts-1, svn_fs_x__p2l_entry_t);
3128 apr_off_t entry_end = entry->offset + entry->size;
3129 if (entry_end < block_end)
3131 if (entry->type == SVN_FS_X__ITEM_TYPE_UNUSED)
3133 /* extend the terminal filler */
3134 entry->size = block_end - entry->offset;
3138 /* No terminal filler. Add one. */
3139 entry = apr_array_push(entries);
3140 entry->offset = entry_end;
3141 entry->size = block_end - entry_end;
3142 entry->type = SVN_FS_X__ITEM_TYPE_UNUSED;
3143 entry->fnv1_checksum = 0;
3144 entry->item_count = 0;
3145 entry->items = NULL;
3150 return SVN_NO_ERROR;
3154 svn_fs_x__p2l_index_lookup(apr_array_header_t **entries,
3156 svn_fs_x__revision_file_t *rev_file,
3157 svn_revnum_t revision,
3158 apr_off_t block_start,
3159 apr_off_t block_size,
3160 apr_pool_t *result_pool,
3161 apr_pool_t *scratch_pool)
3163 apr_off_t block_end = block_start + block_size;
3165 /* the receiving container */
3167 apr_array_header_t *result = apr_array_make(result_pool, 16,
3168 sizeof(svn_fs_x__p2l_entry_t));
3170 /* Fetch entries page-by-page. Since the p2l index is supposed to cover
3171 * every single byte in the rev / pack file - even unused sections -
3172 * every iteration must result in some progress. */
3173 while (block_start < block_end)
3175 svn_fs_x__p2l_entry_t *entry;
3176 SVN_ERR(p2l_index_lookup(result, rev_file, fs, revision, block_start,
3177 block_end, scratch_pool));
3178 SVN_ERR_ASSERT(result->nelts > 0);
3180 /* continue directly behind last item */
3181 entry = &APR_ARRAY_IDX(result, result->nelts-1, svn_fs_x__p2l_entry_t);
3182 block_start = entry->offset + entry->size;
3184 /* Some paranoia check. Successive iterations should never return
3185 * duplicates but if it did, we might get into trouble later on. */
3186 if (last_count > 0 && last_count < result->nelts)
3188 entry = &APR_ARRAY_IDX(result, last_count - 1,
3189 svn_fs_x__p2l_entry_t);
3190 SVN_ERR_ASSERT(APR_ARRAY_IDX(result, last_count,
3191 svn_fs_x__p2l_entry_t).offset
3192 >= entry->offset + entry->size);
3195 last_count = result->nelts;
3199 return SVN_NO_ERROR;
3202 /* compare_fn_t comparing a svn_fs_x__p2l_entry_t at LHS with an offset
3206 compare_p2l_entry_offsets(const void *lhs, const void *rhs)
3208 const svn_fs_x__p2l_entry_t *entry = (const svn_fs_x__p2l_entry_t *)lhs;
3209 apr_off_t offset = *(const apr_off_t *)rhs;
3211 return entry->offset < offset ? -1 : (entry->offset == offset ? 0 : 1);
3214 /* Cached data extraction utility. DATA is a P2L index page, e.g. an APR
3215 * array of svn_fs_fs__p2l_entry_t elements. Return the entry for the item,
3216 * allocated in RESULT_POOL, starting at OFFSET or NULL if that's not an
3217 * the start offset of any item. Use SCRATCH_POOL for temporary allocations.
3219 static svn_fs_x__p2l_entry_t *
3220 get_p2l_entry_from_cached_page(const void *data,
3222 apr_pool_t *result_pool,
3223 apr_pool_t *scratch_pool)
3225 /* resolve all pointer values of in-cache data */
3226 const apr_array_header_t *page = data;
3227 apr_array_header_t *entries = apr_pmemdup(scratch_pool, page,
3229 svn_fs_x__p2l_entry_t *entry;
3231 entries->elts = (char *)svn_temp_deserializer__ptr(page,
3232 (const void *const *)&page->elts);
3234 /* search of the offset we want */
3235 entry = svn_sort__array_lookup(entries, &offset, NULL,
3236 (int (*)(const void *, const void *))compare_p2l_entry_offsets);
3238 /* return it, if it is a perfect match */
3241 svn_fs_x__p2l_entry_t *result
3242 = apr_pmemdup(result_pool, entry, sizeof(*result));
3244 = (svn_fs_x__id_t *)svn_temp_deserializer__ptr(entries->elts,
3245 (const void *const *)&entry->items);
3252 /* Implements svn_cache__partial_getter_func_t for P2L index pages, copying
3253 * the entry for the apr_off_t at BATON into *OUT. *OUT will be NULL if
3254 * there is no matching entry in the index page at DATA.
3256 static svn_error_t *
3257 p2l_entry_lookup_func(void **out,
3259 apr_size_t data_len,
3261 apr_pool_t *result_pool)
3263 svn_fs_x__p2l_entry_t *entry
3264 = get_p2l_entry_from_cached_page(data, *(apr_off_t *)baton, result_pool,
3267 *out = entry && entry->offset == *(apr_off_t *)baton
3268 ? svn_fs_x__p2l_entry_dup(entry, result_pool)
3271 return SVN_NO_ERROR;
3274 static svn_error_t *
3275 p2l_entry_lookup(svn_fs_x__p2l_entry_t **entry_p,
3276 svn_fs_x__revision_file_t *rev_file,
3278 svn_revnum_t revision,
3280 apr_pool_t *result_pool,
3281 apr_pool_t *scratch_pool)
3283 svn_fs_x__data_t *ffd = fs->fsap_data;
3284 svn_fs_x__page_cache_key_t key = { 0 };
3285 svn_boolean_t is_cached = FALSE;
3286 p2l_page_info_baton_t page_info;
3288 /* look for this info in our cache */
3289 SVN_ERR(get_p2l_keys(&page_info, &key, rev_file, fs, revision, offset,
3291 SVN_ERR(svn_cache__get_partial((void**)entry_p, &is_cached,
3292 ffd->p2l_page_cache, &key,
3293 p2l_entry_lookup_func, &offset,
3297 /* do a standard index lookup. This is will automatically prefetch
3298 * data to speed up future lookups. */
3299 apr_array_header_t *entries = apr_array_make(result_pool, 1,
3301 SVN_ERR(p2l_index_lookup(entries, rev_file, fs, revision, offset,
3302 offset + 1, scratch_pool));
3304 /* Find the entry that we want. */
3305 *entry_p = svn_sort__array_lookup(entries, &offset, NULL,
3306 (int (*)(const void *, const void *))compare_p2l_entry_offsets);
3309 return SVN_NO_ERROR;
3313 svn_fs_x__p2l_entry_lookup(svn_fs_x__p2l_entry_t **entry_p,
3315 svn_fs_x__revision_file_t *rev_file,
3316 svn_revnum_t revision,
3318 apr_pool_t *result_pool,
3319 apr_pool_t *scratch_pool)
3321 /* look for this info in our cache */
3322 SVN_ERR(p2l_entry_lookup(entry_p, rev_file, fs, revision, offset,
3323 result_pool, scratch_pool));
3325 return SVN_NO_ERROR;
3328 /* Baton structure for p2l_item_lookup_func. It describes which sub_item
3329 * info shall be returned.
3331 typedef struct p2l_item_lookup_baton_t
3333 /* file offset to find the P2L index entry for */
3336 /* return the sub-item at this position within that entry */
3337 apr_uint32_t sub_item;
3338 } p2l_item_lookup_baton_t;
3340 /* Implements svn_cache__partial_getter_func_t for P2L index pages, copying
3341 * the svn_fs_x__id_t for the item described 2l_item_lookup_baton_t
3342 * *BATON. *OUT will be NULL if there is no matching index entry or the
3343 * sub-item is out of range.
3345 static svn_error_t *
3346 p2l_item_lookup_func(void **out,
3348 apr_size_t data_len,
3350 apr_pool_t *result_pool)
3352 p2l_item_lookup_baton_t *lookup_baton = baton;
3353 svn_fs_x__p2l_entry_t *entry
3354 = get_p2l_entry_from_cached_page(data, lookup_baton->offset, result_pool,
3358 && entry->offset == lookup_baton->offset
3359 && entry->item_count > lookup_baton->sub_item
3360 ? apr_pmemdup(result_pool,
3361 entry->items + lookup_baton->sub_item,
3362 sizeof(*entry->items))
3365 return SVN_NO_ERROR;
3369 svn_fs_x__p2l_item_lookup(svn_fs_x__id_t **item,
3371 svn_fs_x__revision_file_t *rev_file,
3372 svn_revnum_t revision,
3374 apr_uint32_t sub_item,
3375 apr_pool_t *result_pool,
3376 apr_pool_t *scratch_pool)
3378 svn_fs_x__data_t *ffd = fs->fsap_data;
3379 svn_fs_x__page_cache_key_t key = { 0 };
3380 svn_boolean_t is_cached = FALSE;
3381 p2l_page_info_baton_t page_info;
3382 p2l_item_lookup_baton_t baton;
3386 /* look for this info in our cache */
3387 SVN_ERR(get_p2l_keys(&page_info, &key, rev_file, fs, revision, offset,
3389 baton.offset = offset;
3390 baton.sub_item = sub_item;
3391 SVN_ERR(svn_cache__get_partial((void**)item, &is_cached,
3392 ffd->p2l_page_cache, &key,
3393 p2l_item_lookup_func, &baton, result_pool));
3396 /* do a standard index lookup. This is will automatically prefetch
3397 * data to speed up future lookups. */
3398 svn_fs_x__p2l_entry_t *entry;
3399 SVN_ERR(p2l_entry_lookup(&entry, rev_file, fs, revision, offset,
3400 result_pool, scratch_pool));
3403 if (entry && entry->item_count > sub_item)
3404 *item = apr_pmemdup(result_pool, entry->items + sub_item,
3408 return SVN_NO_ERROR;
3411 /* Implements svn_cache__partial_getter_func_t for P2L headers, setting *OUT
3412 * to the largest the first offset not covered by this P2L index.
3414 static svn_error_t *
3415 p2l_get_max_offset_func(void **out,
3417 apr_size_t data_len,
3419 apr_pool_t *result_pool)
3421 const p2l_header_t *header = data;
3422 apr_off_t max_offset = header->file_size;
3423 *out = apr_pmemdup(result_pool, &max_offset, sizeof(max_offset));
3425 return SVN_NO_ERROR;
3429 svn_fs_x__p2l_get_max_offset(apr_off_t *offset,
3431 svn_fs_x__revision_file_t *rev_file,
3432 svn_revnum_t revision,
3433 apr_pool_t *scratch_pool)
3435 svn_fs_x__data_t *ffd = fs->fsap_data;
3436 p2l_header_t *header;
3437 svn_boolean_t is_cached = FALSE;
3438 apr_off_t *offset_p;
3440 /* look for the header data in our cache */
3441 svn_fs_x__pair_cache_key_t key;
3442 key.revision = base_revision(fs, revision);
3443 key.second = svn_fs_x__is_packed_rev(fs, revision);
3445 SVN_ERR(svn_cache__get_partial((void **)&offset_p, &is_cached,
3446 ffd->p2l_header_cache, &key,
3447 p2l_get_max_offset_func, NULL,
3451 *offset = *offset_p;
3452 return SVN_NO_ERROR;
3455 SVN_ERR(get_p2l_header(&header, rev_file, fs, revision, scratch_pool,
3457 *offset = header->file_size;
3459 return SVN_NO_ERROR;
3463 svn_fs_x__item_offset(apr_off_t *absolute_position,
3464 apr_uint32_t *sub_item,
3466 svn_fs_x__revision_file_t *rev_file,
3467 const svn_fs_x__id_t *item_id,
3468 apr_pool_t *scratch_pool)
3470 if (svn_fs_x__is_txn(item_id->change_set))
3471 SVN_ERR(l2p_proto_index_lookup(absolute_position, sub_item, fs,
3472 svn_fs_x__get_txn_id(item_id->change_set),
3473 item_id->number, scratch_pool));
3475 SVN_ERR(l2p_index_lookup(absolute_position, sub_item, fs, rev_file,
3476 svn_fs_x__get_revnum(item_id->change_set),
3477 item_id->number, scratch_pool));
3479 return SVN_NO_ERROR;
3482 /* Calculate the FNV1 checksum over the offset range in REV_FILE, covered by
3483 * ENTRY. Store the result in ENTRY->FNV1_CHECKSUM. Use SCRATCH_POOL for
3484 * temporary allocations. */
3485 static svn_error_t *
3486 calc_fnv1(svn_fs_x__p2l_entry_t *entry,
3487 svn_fs_x__revision_file_t *rev_file,
3488 apr_pool_t *scratch_pool)
3490 unsigned char buffer[4096];
3491 svn_checksum_t *checksum;
3492 svn_checksum_ctx_t *context
3493 = svn_checksum_ctx_create(svn_checksum_fnv1a_32x4, scratch_pool);
3494 apr_off_t size = entry->size;
3496 /* Special rules apply to unused sections / items. The data must be a
3497 * sequence of NUL bytes (not checked here) and the checksum is fixed to 0.
3499 if (entry->type == SVN_FS_X__ITEM_TYPE_UNUSED)
3501 entry->fnv1_checksum = 0;
3502 return SVN_NO_ERROR;
3505 /* Read the block and feed it to the checksum calculator. */
3506 SVN_ERR(svn_io_file_seek(rev_file->file, APR_SET, &entry->offset,
3510 apr_size_t to_read = size > sizeof(buffer)
3513 SVN_ERR(svn_io_file_read_full2(rev_file->file, buffer, to_read, NULL,
3514 NULL, scratch_pool));
3515 SVN_ERR(svn_checksum_update(context, buffer, to_read));
3519 /* Store final checksum in ENTRY. */
3520 SVN_ERR(svn_checksum_final(&checksum, context, scratch_pool));
3521 entry->fnv1_checksum = ntohl(*(const apr_uint32_t *)checksum->digest);
3523 return SVN_NO_ERROR;
3527 * Index (re-)creation utilities.
3531 svn_fs_x__p2l_index_from_p2l_entries(const char **protoname,
3533 svn_fs_x__revision_file_t *rev_file,
3534 apr_array_header_t *entries,
3535 apr_pool_t *result_pool,
3536 apr_pool_t *scratch_pool)
3538 apr_file_t *proto_index;
3540 /* Use a subpool for immediate temp file cleanup at the end of this
3542 apr_pool_t *iterpool = svn_pool_create(scratch_pool);
3545 /* Create a proto-index file. */
3546 SVN_ERR(svn_io_open_unique_file3(NULL, protoname, NULL,
3547 svn_io_file_del_on_pool_cleanup,
3548 result_pool, scratch_pool));
3549 SVN_ERR(svn_fs_x__p2l_proto_index_open(&proto_index, *protoname,
3552 /* Write ENTRIES to proto-index file and calculate checksums as we go. */
3553 for (i = 0; i < entries->nelts; ++i)
3555 svn_fs_x__p2l_entry_t *entry
3556 = APR_ARRAY_IDX(entries, i, svn_fs_x__p2l_entry_t *);
3557 svn_pool_clear(iterpool);
3559 SVN_ERR(calc_fnv1(entry, rev_file, iterpool));
3560 SVN_ERR(svn_fs_x__p2l_proto_index_add_entry(proto_index, entry,
3564 /* Convert proto-index into final index and move it into position.
3565 * Note that REV_FILE contains the start revision of the shard file if it
3566 * has been packed while REVISION may be somewhere in the middle. For
3567 * non-packed shards, they will have identical values. */
3568 SVN_ERR(svn_io_file_close(proto_index, iterpool));
3570 /* Temp file cleanup. */
3571 svn_pool_destroy(iterpool);
3573 return SVN_NO_ERROR;
3576 /* Decorator for svn_fs_x__p2l_entry_t that associates it with a sorted
3577 * variant of its ITEMS array.
3579 typedef struct sub_item_ordered_t
3581 /* ENTRY that got wrapped */
3582 svn_fs_x__p2l_entry_t *entry;
3584 /* Array of pointers into ENTRY->ITEMS, sorted by their revision member
3585 * _descending_ order. May be NULL if ENTRY->ITEM_COUNT < 2. */
3586 svn_fs_x__id_t **order;
3587 } sub_item_ordered_t;
3589 /* implements compare_fn_t. Place LHS before RHS, if the latter is younger.
3590 * Used to sort sub_item_ordered_t::order
3593 compare_sub_items(const svn_fs_x__id_t * const * lhs,
3594 const svn_fs_x__id_t * const * rhs)
3596 return (*lhs)->change_set < (*rhs)->change_set
3598 : ((*lhs)->change_set > (*rhs)->change_set ? -1 : 0);
3601 /* implements compare_fn_t. Place LHS before RHS, if the latter belongs to
3605 compare_p2l_info_rev(const sub_item_ordered_t * lhs,
3606 const sub_item_ordered_t * rhs)
3608 svn_fs_x__id_t *lhs_part;
3609 svn_fs_x__id_t *rhs_part;
3612 if (lhs->entry->item_count == 0)
3613 return rhs->entry->item_count == 0 ? 0 : -1;
3614 if (rhs->entry->item_count == 0)
3617 lhs_part = lhs->order ? lhs->order[lhs->entry->item_count - 1]
3618 : &lhs->entry->items[0];
3619 rhs_part = rhs->order ? rhs->order[rhs->entry->item_count - 1]
3620 : &rhs->entry->items[0];
3622 if (lhs_part->change_set == rhs_part->change_set)
3625 return lhs_part->change_set < rhs_part->change_set ? -1 : 1;
3629 svn_fs_x__l2p_index_from_p2l_entries(const char **protoname,
3631 apr_array_header_t *entries,
3632 apr_pool_t *result_pool,
3633 apr_pool_t *scratch_pool)
3635 apr_file_t *proto_index;
3637 /* Use a subpool for immediate temp file cleanup at the end of this
3639 apr_pool_t *iterpool = svn_pool_create(scratch_pool);
3640 svn_revnum_t prev_rev = SVN_INVALID_REVNUM;
3643 svn_priority_queue__t *queue;
3644 apr_size_t count = 0;
3645 apr_array_header_t *sub_item_orders;
3647 /* Create the temporary proto-rev file. */
3648 SVN_ERR(svn_io_open_unique_file3(NULL, protoname, NULL,
3649 svn_io_file_del_on_pool_cleanup,
3650 result_pool, scratch_pool));
3651 SVN_ERR(svn_fs_x__l2p_proto_index_open(&proto_index, *protoname,
3655 /* wrap P2L entries such that we have access to the sub-items in revision
3656 order. The ENTRY_COUNT member will point to the next item to read+1. */
3657 sub_item_orders = apr_array_make(scratch_pool, entries->nelts,
3658 sizeof(sub_item_ordered_t));
3659 sub_item_orders->nelts = entries->nelts;
3661 for (i = 0; i < entries->nelts; ++i)
3663 svn_fs_x__p2l_entry_t *entry
3664 = APR_ARRAY_IDX(entries, i, svn_fs_x__p2l_entry_t *);
3665 sub_item_ordered_t *ordered
3666 = &APR_ARRAY_IDX(sub_item_orders, i, sub_item_ordered_t);
3668 /* skip unused regions (e.g. padding) */
3669 if (entry->item_count == 0)
3671 --sub_item_orders->nelts;
3676 ordered->entry = entry;
3677 count += entry->item_count;
3679 if (entry->item_count > 1)
3682 = apr_palloc(scratch_pool,
3683 sizeof(*ordered->order) * entry->item_count);
3684 for (k = 0; k < entry->item_count; ++k)
3685 ordered->order[k] = &entry->items[k];
3687 qsort(ordered->order, entry->item_count, sizeof(*ordered->order),
3688 (int (*)(const void *, const void *))compare_sub_items);
3692 /* we need to write the index in ascending revision order */
3693 queue = svn_priority_queue__create
3695 (int (*)(const void *, const void *))compare_p2l_info_rev);
3697 /* write index entries */
3698 for (i = 0; i < count; ++i)
3700 svn_fs_x__id_t *sub_item;
3701 sub_item_ordered_t *ordered = svn_priority_queue__peek(queue);
3703 if (ordered->entry->item_count > 0)
3705 /* if there is only one item, we skip the overhead of having an
3706 extra array for the item order */
3707 sub_item = ordered->order
3708 ? ordered->order[ordered->entry->item_count - 1]
3709 : &ordered->entry->items[0];
3711 /* next revision? */
3712 if (prev_rev != svn_fs_x__get_revnum(sub_item->change_set))
3714 prev_rev = svn_fs_x__get_revnum(sub_item->change_set);
3715 SVN_ERR(svn_fs_x__l2p_proto_index_add_revision
3716 (proto_index, iterpool));
3720 SVN_ERR(svn_fs_x__l2p_proto_index_add_entry
3721 (proto_index, ordered->entry->offset,
3722 (apr_uint32_t)(sub_item - ordered->entry->items),
3723 sub_item->number, iterpool));
3725 /* make ITEM_COUNT point the next sub-item to use+1 */
3726 --ordered->entry->item_count;
3729 /* process remaining sub-items (if any) of that container later */
3730 if (ordered->entry->item_count)
3731 svn_priority_queue__update(queue);
3733 svn_priority_queue__pop(queue);
3735 /* keep memory usage in check */
3737 svn_pool_clear(iterpool);
3740 /* Convert proto-index into final index and move it into position. */
3741 SVN_ERR(svn_io_file_close(proto_index, iterpool));
3743 /* Temp file cleanup. */
3744 svn_pool_destroy(iterpool);
3746 return SVN_NO_ERROR;
3751 * Standard (de-)serialization functions
3755 svn_fs_x__serialize_l2p_header(void **data,
3756 apr_size_t *data_len,
3760 l2p_header_t *header = in;
3761 svn_temp_serializer__context_t *context;
3762 svn_stringbuf_t *serialized;
3763 apr_size_t page_count = header->page_table_index[header->revision_count];
3764 apr_size_t page_table_size = page_count * sizeof(*header->page_table);
3765 apr_size_t index_size
3766 = (header->revision_count + 1) * sizeof(*header->page_table_index);
3767 apr_size_t data_size = sizeof(*header) + index_size + page_table_size;
3769 /* serialize header and all its elements */
3770 context = svn_temp_serializer__init(header,
3775 /* page table index array */
3776 svn_temp_serializer__add_leaf(context,
3777 (const void * const *)&header->page_table_index,
3780 /* page table array */
3781 svn_temp_serializer__add_leaf(context,
3782 (const void * const *)&header->page_table,
3785 /* return the serialized result */
3786 serialized = svn_temp_serializer__get(context);
3788 *data = serialized->data;
3789 *data_len = serialized->len;
3791 return SVN_NO_ERROR;
3795 svn_fs_x__deserialize_l2p_header(void **out,
3797 apr_size_t data_len,
3800 l2p_header_t *header = (l2p_header_t *)data;
3802 /* resolve the pointers in the struct */
3803 svn_temp_deserializer__resolve(header, (void**)&header->page_table_index);
3804 svn_temp_deserializer__resolve(header, (void**)&header->page_table);
3809 return SVN_NO_ERROR;
3813 svn_fs_x__serialize_l2p_page(void **data,
3814 apr_size_t *data_len,
3818 l2p_page_t *page = in;
3819 svn_temp_serializer__context_t *context;
3820 svn_stringbuf_t *serialized;
3821 apr_size_t of_table_size = page->entry_count * sizeof(*page->offsets);
3822 apr_size_t si_table_size = page->entry_count * sizeof(*page->sub_items);
3824 /* serialize struct and all its elements */
3825 context = svn_temp_serializer__init(page,
3827 of_table_size + si_table_size
3828 + sizeof(*page) + 32,
3831 /* offsets and sub_items arrays */
3832 svn_temp_serializer__add_leaf(context,
3833 (const void * const *)&page->offsets,
3835 svn_temp_serializer__add_leaf(context,
3836 (const void * const *)&page->sub_items,
3839 /* return the serialized result */
3840 serialized = svn_temp_serializer__get(context);
3842 *data = serialized->data;
3843 *data_len = serialized->len;
3845 return SVN_NO_ERROR;
3849 svn_fs_x__deserialize_l2p_page(void **out,
3851 apr_size_t data_len,
3854 l2p_page_t *page = data;
3856 /* resolve the pointers in the struct */
3857 svn_temp_deserializer__resolve(page, (void**)&page->offsets);
3858 svn_temp_deserializer__resolve(page, (void**)&page->sub_items);
3863 return SVN_NO_ERROR;
3867 svn_fs_x__serialize_p2l_header(void **data,
3868 apr_size_t *data_len,
3872 p2l_header_t *header = in;
3873 svn_temp_serializer__context_t *context;
3874 svn_stringbuf_t *serialized;
3875 apr_size_t table_size = (header->page_count + 1) * sizeof(*header->offsets);
3877 /* serialize header and all its elements */
3878 context = svn_temp_serializer__init(header,
3880 table_size + sizeof(*header) + 32,
3884 svn_temp_serializer__add_leaf(context,
3885 (const void * const *)&header->offsets,
3888 /* return the serialized result */
3889 serialized = svn_temp_serializer__get(context);
3891 *data = serialized->data;
3892 *data_len = serialized->len;
3894 return SVN_NO_ERROR;
3898 svn_fs_x__deserialize_p2l_header(void **out,
3900 apr_size_t data_len,
3903 p2l_header_t *header = data;
3905 /* resolve the only pointer in the struct */
3906 svn_temp_deserializer__resolve(header, (void**)&header->offsets);
3911 return SVN_NO_ERROR;
3915 svn_fs_x__serialize_p2l_page(void **data,
3916 apr_size_t *data_len,
3920 apr_array_header_t *page = in;
3921 svn_temp_serializer__context_t *context;
3922 svn_stringbuf_t *serialized;
3923 apr_size_t table_size = page->elt_size * page->nelts;
3924 svn_fs_x__p2l_entry_t *entries = (svn_fs_x__p2l_entry_t *)page->elts;
3927 /* serialize array header and all its elements */
3928 context = svn_temp_serializer__init(page,
3930 table_size + sizeof(*page) + 32,
3933 /* items in the array */
3934 svn_temp_serializer__push(context,
3935 (const void * const *)&page->elts,
3938 for (i = 0; i < page->nelts; ++i)
3939 svn_temp_serializer__add_leaf(context,
3940 (const void * const *)&entries[i].items,
3941 entries[i].item_count
3942 * sizeof(*entries[i].items));
3944 svn_temp_serializer__pop(context);
3946 /* return the serialized result */
3947 serialized = svn_temp_serializer__get(context);
3949 *data = serialized->data;
3950 *data_len = serialized->len;
3952 return SVN_NO_ERROR;
3956 svn_fs_x__deserialize_p2l_page(void **out,
3958 apr_size_t data_len,
3961 apr_array_header_t *page = (apr_array_header_t *)data;
3962 svn_fs_x__p2l_entry_t *entries;
3965 /* resolve the only pointer in the struct */
3966 svn_temp_deserializer__resolve(page, (void**)&page->elts);
3968 /* resolve sub-struct pointers*/
3969 entries = (svn_fs_x__p2l_entry_t *)page->elts;
3970 for (i = 0; i < page->nelts; ++i)
3971 svn_temp_deserializer__resolve(entries, (void**)&entries[i].items);
3973 /* patch up members */
3975 page->nalloc = page->nelts;
3980 return SVN_NO_ERROR;