1/* index.c indexing support for FSX support 2 * 3 * ==================================================================== 4 * Licensed to the Apache Software Foundation (ASF) under one 5 * or more contributor license agreements. See the NOTICE file 6 * distributed with this work for additional information 7 * regarding copyright ownership. The ASF licenses this file 8 * to you under the Apache License, Version 2.0 (the 9 * "License"); you may not use this file except in compliance 10 * with the License. You may obtain a copy of the License at 11 * 12 * http://www.apache.org/licenses/LICENSE-2.0 13 * 14 * Unless required by applicable law or agreed to in writing, 15 * software distributed under the License is distributed on an 16 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 17 * KIND, either express or implied. See the License for the 18 * specific language governing permissions and limitations 19 * under the License. 20 * ==================================================================== 21 */ 22 23#include <assert.h> 24 25#include "svn_io.h" 26#include "svn_pools.h" 27#include "svn_sorts.h" 28 29#include "index.h" 30#include "util.h" 31#include "pack.h" 32 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" 37 38#include "svn_private_config.h" 39#include "temp_serializer.h" 40#include "fs_x.h" 41 42#include "../libsvn_fs/fs-loader.h" 43 44/* maximum length of a uint64 in an 7/8b encoding */ 45#define ENCODED_INT_LENGTH 10 46 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. 49 * 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. 53 */ 54static 55const apr_uint64_t off_t_max = (sizeof(apr_off_t) == sizeof(apr_int64_t)) 56 ? APR_INT64_MAX 57 : APR_INT32_MAX; 58 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(). 61 */ 62#define P2L_PROTO_INDEX_ENTRY_SIZE (6 * sizeof(apr_uint64_t)) 63 64/* We put this string in front of the L2P index header. */ 65#define L2P_STREAM_PREFIX "L2P-INDEX\n" 66 67/* We put this string in front of the P2L index header. */ 68#define P2L_STREAM_PREFIX "P2L-INDEX\n" 69 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)) 73 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. 76 */ 77typedef struct l2p_page_table_entry_t 78{ 79 /* global offset on the page within the index file */ 80 apr_uint64_t offset; 81 82 /* number of mapping entries in that page */ 83 apr_uint32_t entry_count; 84 85 /* size of the page on disk (in the index file) */ 86 apr_uint32_t size; 87} l2p_page_table_entry_t; 88 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 91 * pages themselves. 92 */ 93typedef struct l2p_header_t 94{ 95 /* first revision covered by this index */ 96 svn_revnum_t first_revision; 97 98 /* number of revisions covered */ 99 apr_size_t revision_count; 100 101 /* (max) number of entries per page */ 102 apr_uint32_t page_size; 103 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 106 * PAGE_TABLE. 107 */ 108 apr_size_t * page_table_index; 109 110 /* Page table covering all pages in the index */ 111 l2p_page_table_entry_t * page_table; 112} l2p_header_t; 113 114/* Run-time data structure containing a single log-to-phys index page. 115 */ 116typedef struct l2p_page_t 117{ 118 /* number of entries in the OFFSETS array */ 119 apr_uint32_t entry_count; 120 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. */ 124 apr_off_t *offsets; 125 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; 130} l2p_page_t; 131 132/* All of the log-to-phys proto index file consist of entries of this type. 133 */ 134typedef struct l2p_proto_entry_t 135{ 136 /* phys offset + 1 of the data container. 0 for "new revision" entries. */ 137 apr_uint64_t offset; 138 139 /* corresponding item index. 0 for "new revision" entries. */ 140 apr_uint64_t item_index; 141 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; 145} l2p_proto_entry_t; 146 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. 149 */ 150typedef struct p2l_header_t 151{ 152 /* first revision covered by the index (and rev file) */ 153 svn_revnum_t first_revision; 154 155 /* number of bytes in the rev files covered by each p2l page */ 156 apr_uint64_t page_size; 157 158 /* number of pages / clusters in that rev file */ 159 apr_size_t page_count; 160 161 /* number of bytes in the rev file */ 162 apr_uint64_t file_size; 163 164 /* offsets of the pages / cluster descriptions within the index file */ 165 apr_off_t *offsets; 166} p2l_header_t; 167 168/* 169 * packed stream array 170 */ 171 172/* How many numbers we will pre-fetch and buffer in a packed number stream. 173 */ 174enum { MAX_NUMBER_PREFETCH = 64 }; 175 176/* Prefetched number entry in a packed number stream. 177 */ 178typedef struct value_position_pair_t 179{ 180 /* prefetched number */ 181 apr_uint64_t value; 182 183 /* number of bytes read, *including* this number, since the buffer start */ 184 apr_size_t total_len; 185} value_position_pair_t; 186 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. 189 */ 190struct svn_fs_x__packed_number_stream_t 191{ 192 /* underlying data file containing the packed values */ 193 apr_file_t *file; 194 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; 198 199 /* First offset within FILE after the stream data. 200 * Attempts to read beyond this will cause an "Unexpected End Of Stream" 201 * error. */ 202 apr_off_t stream_end; 203 204 /* number of used entries in BUFFER (starting at index 0) */ 205 apr_size_t used; 206 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() */ 209 apr_size_t current; 210 211 /* offset in FILE from which the first entry in BUFFER has been read */ 212 apr_off_t start_offset; 213 214 /* offset in FILE from which the next number has to be read */ 215 apr_off_t next_offset; 216 217 /* read the file in chunks of this size */ 218 apr_size_t block_size; 219 220 /* pool to be used for file ops etc. */ 221 apr_pool_t *pool; 222 223 /* buffer for prefetched values */ 224 value_position_pair_t buffer[MAX_NUMBER_PREFETCH]; 225}; 226 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"). 230 */ 231static svn_error_t * 232stream_error_create(svn_fs_x__packed_number_stream_t *stream, 233 apr_status_t err, 234 const char *message) 235{ 236 const char *file_name; 237 apr_off_t offset; 238 SVN_ERR(svn_io_file_name_get(&file_name, stream->file, 239 stream->pool)); 240 SVN_ERR(svn_fs_x__get_file_offset(&offset, stream->file, stream->pool)); 241 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)); 246} 247 248/* Read up to MAX_NUMBER_PREFETCH numbers from the STREAM->NEXT_OFFSET in 249 * STREAM->FILE and buffer them. 250 * 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. 254 */ 255SVN__PREVENT_INLINE 256static svn_error_t * 257packed_stream_read(svn_fs_x__packed_number_stream_t *stream) 258{ 259 unsigned char buffer[MAX_NUMBER_PREFETCH]; 260 apr_size_t read = 0; 261 apr_size_t i; 262 value_position_pair_t *target; 263 apr_off_t block_start = 0; 264 apr_off_t block_left = 0; 265 apr_status_t err; 266 267 /* all buffered data will have been read starting here */ 268 stream->start_offset = stream->next_offset; 269 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. 273 */ 274 SVN_ERR(svn_io_file_aligned_seek(stream->file, stream->block_size, 275 &block_start, stream->next_offset, 276 stream->pool)); 277 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_. 281 */ 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; 286 287 /* Don't read beyond the end of the file section that belongs to this 288 * index / stream. */ 289 read = (apr_size_t)MIN(read, stream->stream_end - stream->next_offset); 290 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%")); 295 296 /* if the last number is incomplete, trim it from the buffer */ 297 while (read > 0 && buffer[read-1] >= 0x80) 298 --read; 299 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%")); 305 306 /* parse file buffer and expand into stream buffer */ 307 target = stream->buffer; 308 for (i = 0; i < read;) 309 { 310 if (buffer[i] < 0x80) 311 { 312 /* numbers < 128 are relatively frequent and particularly easy 313 * to decode. Give them special treatment. */ 314 target->value = buffer[i]; 315 ++i; 316 target->total_len = i; 317 ++target; 318 } 319 else 320 { 321 apr_uint64_t value = 0; 322 apr_uint64_t shift = 0; 323 while (buffer[i] >= 0x80) 324 { 325 value += ((apr_uint64_t)buffer[i] & 0x7f) << shift; 326 shift += 7; 327 ++i; 328 } 329 330 target->value = value + ((apr_uint64_t)buffer[i] << shift); 331 ++i; 332 target->total_len = i; 333 ++target; 334 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")); 340 } 341 } 342 343 /* update stream state */ 344 stream->used = target - stream->buffer; 345 stream->next_offset = stream->start_offset + i; 346 stream->current = 0; 347 348 return SVN_NO_ERROR; 349} 350 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. 355 */ 356static svn_error_t * 357packed_stream_open(svn_fs_x__packed_number_stream_t **stream, 358 apr_file_t *file, 359 apr_off_t start, 360 apr_off_t end, 361 const char *stream_prefix, 362 apr_size_t block_size, 363 apr_pool_t *result_pool, 364 apr_pool_t *scratch_pool) 365{ 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; 369 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)); 373 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, 376 scratch_pool)); 377 SVN_ERR(svn_io_file_read_full2(file, buffer, len, NULL, NULL, 378 scratch_pool)); 379 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" 383 " expected: %s" 384 " found: %s"), stream_prefix, buffer); 385 386 /* Construct the actual stream object. */ 387 result = apr_palloc(result_pool, sizeof(*result)); 388 389 result->pool = result_pool; 390 result->file = file; 391 result->stream_start = start + len; 392 result->stream_end = end; 393 394 result->used = 0; 395 result->current = 0; 396 result->start_offset = result->stream_start; 397 result->next_offset = result->stream_start; 398 result->block_size = block_size; 399 400 *stream = result; 401 402 return SVN_NO_ERROR; 403} 404 405/* 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. 410 */ 411SVN__FORCE_INLINE 412static svn_error_t* 413packed_stream_get(apr_uint64_t *value, 414 svn_fs_x__packed_number_stream_t *stream) 415{ 416 if (stream->current == stream->used) 417 SVN_ERR(packed_stream_read(stream)); 418 419 *value = stream->buffer[stream->current].value; 420 ++stream->current; 421 422 return SVN_NO_ERROR; 423} 424 425/* Navigate STREAM to packed stream offset OFFSET. There will be no checks 426 * whether the given OFFSET is valid. 427 */ 428static void 429packed_stream_seek(svn_fs_x__packed_number_stream_t *stream, 430 apr_off_t offset) 431{ 432 apr_off_t file_offset = offset + stream->stream_start; 433 434 if ( stream->used == 0 435 || offset < stream->start_offset 436 || offset >= stream->next_offset) 437 { 438 /* outside buffered data. Next get() will read() from OFFSET. */ 439 stream->start_offset = file_offset; 440 stream->next_offset = file_offset; 441 stream->current = 0; 442 stream->used = 0; 443 } 444 else 445 { 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. */ 449 apr_size_t i; 450 for (i = 0; i < stream->used; ++i) 451 if (stream->buffer[i].total_len > file_offset - stream->start_offset) 452 break; 453 454 stream->current = i; 455 } 456} 457 458/* Return the packed stream offset of at which the next number in the stream 459 * can be found. 460 */ 461static apr_off_t 462packed_stream_offset(svn_fs_x__packed_number_stream_t *stream) 463{ 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; 468 469 return file_offset - stream->stream_start; 470} 471 472/* Write VALUE to the PROTO_INDEX file, using SCRATCH_POOL for temporary 473 * allocations. 474 * 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. 479 */ 480static svn_error_t * 481write_uint64_to_proto_index(apr_file_t *proto_index, 482 apr_uint64_t value, 483 apr_pool_t *scratch_pool) 484{ 485 apr_byte_t buffer[sizeof(value)]; 486 int i; 487 apr_size_t written; 488 489 /* Split VALUE into 8 bytes using LE ordering. */ 490 for (i = 0; i < sizeof(buffer); ++i) 491 { 492 /* Unsigned conversions are well-defined ... */ 493 buffer[i] = (apr_byte_t)value; 494 value >>= CHAR_BIT; 495 } 496 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)); 501 502 return SVN_NO_ERROR; 503} 504 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. 508 * 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. 511 */ 512static svn_error_t * 513read_uint64_from_proto_index(apr_file_t *proto_index, 514 apr_uint64_t *value_p, 515 svn_boolean_t *eof, 516 apr_pool_t *scratch_pool) 517{ 518 apr_byte_t buffer[sizeof(*value_p)]; 519 apr_size_t read; 520 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)); 526 527 /* If we did not hit EOF, reconstruct the uint64 value and return it. */ 528 if (!eof || !*eof) 529 { 530 int i; 531 apr_uint64_t value; 532 533 /* This could only overflow if CHAR_BIT had a value that is not 534 * a divisor of 64. */ 535 value = 0; 536 for (i = sizeof(buffer) - 1; i >= 0; --i) 537 value = (value << CHAR_BIT) + buffer[i]; 538 539 *value_p = value; 540 } 541 542 return SVN_NO_ERROR; 543} 544 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. 547 */ 548static svn_error_t * 549read_uint32_from_proto_index(apr_file_t *proto_index, 550 apr_uint32_t *value_p, 551 svn_boolean_t *eof, 552 apr_pool_t *scratch_pool) 553{ 554 apr_uint64_t value; 555 SVN_ERR(read_uint64_from_proto_index(proto_index, &value, eof, 556 scratch_pool)); 557 if (!eof || !*eof) 558 { 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, 564 value), 565 apr_psprintf(scratch_pool, 566 "%" APR_UINT64_T_HEX_FMT, 567 (apr_uint64_t)APR_UINT32_MAX)); 568 569 /* This conversion is not lossy because the value can be represented 570 * in the target type. */ 571 *value_p = (apr_uint32_t)value; 572 } 573 574 return SVN_NO_ERROR; 575} 576 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. 579 */ 580static svn_error_t * 581read_off_t_from_proto_index(apr_file_t *proto_index, 582 apr_off_t *value_p, 583 svn_boolean_t *eof, 584 apr_pool_t *scratch_pool) 585{ 586 apr_uint64_t value; 587 SVN_ERR(read_uint64_from_proto_index(proto_index, &value, eof, 588 scratch_pool)); 589 if (!eof || !*eof) 590 { 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, 596 value), 597 apr_psprintf(scratch_pool, 598 "%" APR_UINT64_T_HEX_FMT, 599 off_t_max)); 600 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 603 * target type. */ 604 *value_p = (apr_off_t)value; 605 } 606 607 return SVN_NO_ERROR; 608} 609 610/* 611 * log-to-phys index 612 */ 613svn_error_t * 614svn_fs_x__l2p_proto_index_open(apr_file_t **proto_index, 615 const char *file_name, 616 apr_pool_t *result_pool) 617{ 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)); 621 622 return SVN_NO_ERROR; 623} 624 625/* Append ENTRY to log-to-phys PROTO_INDEX file. 626 * Use SCRATCH_POOL for temporary allocations. 627 */ 628static svn_error_t * 629write_l2p_entry_to_proto_index(apr_file_t *proto_index, 630 l2p_proto_entry_t entry, 631 apr_pool_t *scratch_pool) 632{ 633 SVN_ERR(write_uint64_to_proto_index(proto_index, entry.offset, 634 scratch_pool)); 635 SVN_ERR(write_uint64_to_proto_index(proto_index, entry.item_index, 636 scratch_pool)); 637 SVN_ERR(write_uint64_to_proto_index(proto_index, entry.sub_item, 638 scratch_pool)); 639 640 return SVN_NO_ERROR; 641} 642 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. 647 */ 648static svn_error_t * 649read_l2p_entry_from_proto_index(apr_file_t *proto_index, 650 l2p_proto_entry_t *entry, 651 svn_boolean_t *eof, 652 apr_pool_t *scratch_pool) 653{ 654 SVN_ERR(read_uint64_from_proto_index(proto_index, &entry->offset, eof, 655 scratch_pool)); 656 SVN_ERR(read_uint64_from_proto_index(proto_index, &entry->item_index, eof, 657 scratch_pool)); 658 SVN_ERR(read_uint32_from_proto_index(proto_index, &entry->sub_item, eof, 659 scratch_pool)); 660 661 return SVN_NO_ERROR; 662} 663 664svn_error_t * 665svn_fs_x__l2p_proto_index_add_revision(apr_file_t *proto_index, 666 apr_pool_t *scratch_pool) 667{ 668 l2p_proto_entry_t entry = { 0 }; 669 return svn_error_trace(write_l2p_entry_to_proto_index(proto_index, entry, 670 scratch_pool)); 671} 672 673svn_error_t * 674svn_fs_x__l2p_proto_index_add_entry(apr_file_t *proto_index, 675 apr_off_t offset, 676 apr_uint32_t sub_item, 677 apr_uint64_t item_index, 678 apr_pool_t *scratch_pool) 679{ 680 l2p_proto_entry_t entry = { 0 }; 681 682 /* make sure the conversion to uint64 works */ 683 SVN_ERR_ASSERT(offset >= -1); 684 685 /* we support offset '-1' as a "not used" indication */ 686 entry.offset = (apr_uint64_t)offset + 1; 687 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; 692 693 /* no limits on the container sub-item index */ 694 entry.sub_item = sub_item; 695 696 return svn_error_trace(write_l2p_entry_to_proto_index(proto_index, entry, 697 scratch_pool)); 698} 699 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. 703 */ 704static apr_size_t 705encode_uint(unsigned char *p, apr_uint64_t value) 706{ 707 unsigned char *start = p; 708 while (value >= 0x80) 709 { 710 *p = (unsigned char)((value % 0x80) + 0x80); 711 value /= 0x80; 712 ++p; 713 } 714 715 *p = (unsigned char)(value % 0x80); 716 return (p - start) + 1; 717} 718 719/* Encode VALUE as 7/8b into P and return the number of bytes written. 720 * This maps signed ints onto unsigned ones. 721 */ 722static apr_size_t 723encode_int(unsigned char *p, apr_int64_t value) 724{ 725 return encode_uint(p, (apr_uint64_t)(value < 0 ? -1 - 2*value : 2*value)); 726} 727 728/* Append VALUE to STREAM in 7/8b encoding. 729 */ 730static svn_error_t * 731stream_write_encoded(svn_stream_t *stream, 732 apr_uint64_t value) 733{ 734 unsigned char encoded[ENCODED_INT_LENGTH]; 735 736 apr_size_t len = encode_uint(encoded, value); 737 return svn_error_trace(svn_stream_write(stream, (char *)encoded, &len)); 738} 739 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. 743 */ 744static int 745rle_array(apr_array_header_t *array, int start, int end) 746{ 747 int i; 748 int target = start; 749 for (i = start; i < end; ++i) 750 { 751 apr_uint64_t value = APR_ARRAY_IDX(array, i, apr_uint64_t); 752 assert(value > 0); 753 754 if (value == 1) 755 { 756 int counter; 757 for (counter = 1; i + counter < end; ++counter) 758 if (APR_ARRAY_IDX(array, i + counter, apr_uint64_t) != 1) 759 break; 760 761 if (--counter) 762 { 763 APR_ARRAY_IDX(array, target, apr_uint64_t) = 0; 764 APR_ARRAY_IDX(array, target + 1, apr_uint64_t) = counter; 765 target += 2; 766 i += counter; 767 continue; 768 } 769 } 770 771 APR_ARRAY_IDX(array, target, apr_uint64_t) = value; 772 ++target; 773 } 774 775 return target; 776} 777 778/* Utility data structure describing an log-2-phys page entry. 779 * This is only used as a transient representation during index creation. 780 */ 781typedef struct l2p_page_entry_t 782{ 783 apr_uint64_t offset; 784 apr_uint32_t sub_item; 785} l2p_page_entry_t; 786 787/* qsort-compatible compare function taking two l2p_page_entry_t and 788 * ordering them by offset. 789 */ 790static int 791compare_l2p_entries_by_offset(const l2p_page_entry_t *lhs, 792 const l2p_page_entry_t *rhs) 793{ 794 return lhs->offset > rhs->offset ? 1 795 : lhs->offset == rhs->offset ? 0 : -1; 796} 797 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. 802 */ 803static svn_error_t * 804encode_l2p_page(apr_array_header_t *entries, 805 int start, 806 int end, 807 svn_spillbuf_t *buffer, 808 apr_pool_t *scratch_pool) 809{ 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; 815 int i; 816 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); 820 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), 825 data_size); 826 qsort(sorted, end - start, sizeof(l2p_page_entry_t), 827 (int (*)(const void *, const void *))compare_l2p_entries_by_offset); 828 829 /* identify container offsets and create container list */ 830 for (i = 0; i < count; ++i) 831 { 832 /* skip "unused" entries */ 833 if (sorted[i].offset == 0) 834 continue; 835 836 /* offset already covered? */ 837 if (i > 0 && sorted[i].offset == sorted[i-1].offset) 838 continue; 839 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)) 844 { 845 svn_stringbuf_appendbytes(container_offsets, (const char *)encoded, 846 encode_uint(encoded, sorted[i].offset 847 - last_offset)); 848 last_offset = sorted[i].offset; 849 apr_hash_set(containers, 850 &sorted[i].offset, 851 sizeof(sorted[i].offset), 852 (void *)(apr_uintptr_t)++container_count); 853 } 854 } 855 856 /* write container list to BUFFER */ 857 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded, 858 encode_uint(encoded, container_count), 859 scratch_pool)); 860 SVN_ERR(svn_spillbuf__write(buffer, (const char *)container_offsets->data, 861 container_offsets->len, scratch_pool)); 862 863 /* encode items */ 864 for (i = start; i < end; ++i) 865 { 866 l2p_page_entry_t *entry = &APR_ARRAY_IDX(entries, i, l2p_page_entry_t); 867 if (entry->offset == 0) 868 { 869 SVN_ERR(svn_spillbuf__write(buffer, "\0", 1, scratch_pool)); 870 } 871 else 872 { 873 void *void_idx = apr_hash_get(containers, &entry->offset, 874 sizeof(entry->offset)); 875 if (void_idx == NULL) 876 { 877 apr_uint64_t value = entry->offset + container_count; 878 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded, 879 encode_uint(encoded, value), 880 scratch_pool)); 881 } 882 else 883 { 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), 888 scratch_pool)); 889 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded, 890 encode_uint(encoded, value), 891 scratch_pool)); 892 } 893 } 894 } 895 896 return SVN_NO_ERROR; 897} 898 899svn_error_t * 900svn_fs_x__l2p_index_append(svn_checksum_t **checksum, 901 svn_fs_t *fs, 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) 907{ 908 svn_fs_x__data_t *ffd = fs->fsap_data; 909 apr_file_t *proto_index = NULL; 910 svn_stream_t *stream; 911 int i; 912 int end; 913 apr_uint64_t entry; 914 svn_boolean_t eof = FALSE; 915 916 int last_page_count = 0; /* total page count at the start of 917 the current revision */ 918 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)); 929 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)); 933 934 /* 64k blocks, spill after 16MB */ 935 svn_spillbuf_t *buffer 936 = svn_spillbuf__create(0x10000, 0x1000000, local_pool); 937 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)); 946 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)); 951 952 /* process all entries until we fail due to EOF */ 953 for (entry = 0; !eof; ++entry) 954 { 955 l2p_proto_entry_t proto_entry; 956 957 /* (attempt to) read the next entry from the source */ 958 SVN_ERR(read_l2p_entry_from_proto_index(proto_index, &proto_entry, 959 &eof, local_pool)); 960 961 /* handle new revision */ 962 if ((entry > 0 && proto_entry.offset == 0) || eof) 963 { 964 /* dump entries, grouped into pages */ 965 966 int entry_count = 0; 967 for (i = 0; i < entries->nelts; i += entry_count) 968 { 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); 974 975 svn_pool_clear(iterpool); 976 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, 981 buffer, iterpool)); 982 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; 986 } 987 988 apr_array_clear(entries); 989 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; 993 994 last_page_count = page_sizes->nelts; 995 } 996 else 997 { 998 int idx; 999 1000 /* store the mapping in our array */ 1001 l2p_page_entry_t page_entry = { 0 }; 1002 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); 1011 1012 idx = (int)proto_entry.item_index; 1013 while (idx >= entries->nelts) 1014 APR_ARRAY_PUSH(entries, l2p_page_entry_t) = page_entry; 1015 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; 1019 } 1020 } 1021 1022 /* we are now done with the source file */ 1023 SVN_ERR(svn_io_file_close(proto_index, local_pool)); 1024 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); 1032 1033 /* open target stream. */ 1034 stream = svn_stream_checksummed2(svn_stream_from_aprfile2(index_file, TRUE, 1035 local_pool), 1036 NULL, checksum, svn_checksum_md5, FALSE, 1037 result_pool); 1038 1039 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)); 1046 1047 /* write the revision table */ 1048 end = rle_array(page_counts, 0, page_counts->nelts); 1049 for (i = 0; i < end; ++i) 1050 { 1051 apr_uint64_t value = APR_ARRAY_IDX(page_counts, i, apr_uint64_t); 1052 SVN_ERR(stream_write_encoded(stream, value)); 1053 } 1054 1055 /* write the page table */ 1056 for (i = 0; i < page_sizes->nelts; ++i) 1057 { 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)); 1062 } 1063 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)); 1067 1068 svn_pool_destroy(local_pool); 1069 1070 return SVN_NO_ERROR; 1071} 1072 1073/* Return the base revision used to identify the p2l or lp2 index covering 1074 * REVISION in FS. 1075 */ 1076static svn_revnum_t 1077base_revision(svn_fs_t *fs, svn_revnum_t revision) 1078{ 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) 1082 : revision; 1083} 1084 1085/* Data structure that describes which l2p page info shall be extracted 1086 * from the cache and contains the fields that receive the result. 1087 */ 1088typedef struct l2p_page_info_baton_t 1089{ 1090 /* input data: we want the page covering (REVISION,ITEM_INDEX) */ 1091 svn_revnum_t revision; 1092 apr_uint64_t item_index; 1093 1094 /* out data */ 1095 /* page location and size of the page within the l2p index file */ 1096 l2p_page_table_entry_t entry; 1097 1098 /* page number within the pages for REVISION (not l2p index global!) */ 1099 apr_uint32_t page_no; 1100 1101 /* offset of ITEM_INDEX within that page */ 1102 apr_uint32_t page_offset; 1103 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; 1107 1108 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. 1112 */ 1113static svn_error_t * 1114l2p_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) 1119{ 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"), 1125 baton->revision); 1126 1127 /* select the relevant page */ 1128 if (baton->item_index < header->page_size) 1129 { 1130 /* most revs fit well into a single page */ 1131 baton->page_offset = (apr_uint32_t)baton->item_index; 1132 baton->page_no = 0; 1133 baton->entry = page_table[page_table_index[rel_revision]]; 1134 } 1135 else 1136 { 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; 1140 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]; 1144 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, 1154 baton->item_index), 1155 apr_psprintf(scratch_pool, 1156 "%" APR_UINT64_T_FMT, 1157 max_item_index), 1158 baton->revision); 1159 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]; 1164 } 1165 1166 baton->first_revision = header->first_revision; 1167 1168 return SVN_NO_ERROR; 1169} 1170 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 1173 * fields in *BATON. 1174 */ 1175static svn_error_t * 1176l2p_header_access_func(void **out, 1177 const void *data, 1178 apr_size_t data_len, 1179 void *baton, 1180 apr_pool_t *result_pool) 1181{ 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); 1190 1191 /* copy the info */ 1192 return l2p_header_copy(baton, header, page_table, page_table_index, 1193 result_pool); 1194} 1195 1196/* Read COUNT run-length-encoded (see rle_array) uint64 from STREAM and 1197 * return them in VALUES. 1198 */ 1199static svn_error_t * 1200expand_rle(apr_array_header_t *values, 1201 svn_fs_x__packed_number_stream_t *stream, 1202 apr_size_t count) 1203{ 1204 apr_array_clear(values); 1205 1206 while (count) 1207 { 1208 apr_uint64_t value; 1209 SVN_ERR(packed_stream_get(&value, stream)); 1210 1211 if (value) 1212 { 1213 APR_ARRAY_PUSH(values, apr_uint64_t) = value; 1214 --count; 1215 } 1216 else 1217 { 1218 apr_uint64_t i; 1219 apr_uint64_t repetitions; 1220 SVN_ERR(packed_stream_get(&repetitions, stream)); 1221 if (++repetitions > count) 1222 repetitions = count; 1223 1224 for (i = 0; i < repetitions; ++i) 1225 APR_ARRAY_PUSH(values, apr_uint64_t) = 1; 1226 1227 count -= repetitions; 1228 } 1229 } 1230 1231 return SVN_NO_ERROR; 1232} 1233 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. 1236 */ 1237static svn_error_t * 1238auto_open_l2p_index(svn_fs_x__revision_file_t *rev_file, 1239 svn_fs_t *fs, 1240 svn_revnum_t revision) 1241{ 1242 if (rev_file->l2p_stream == NULL) 1243 { 1244 svn_fs_x__data_t *ffd = fs->fsap_data; 1245 1246 SVN_ERR(svn_fs_x__auto_read_footer(rev_file)); 1247 SVN_ERR(packed_stream_open(&rev_file->l2p_stream, 1248 rev_file->file, 1249 rev_file->l2p_offset, 1250 rev_file->p2l_offset, 1251 L2P_STREAM_PREFIX, 1252 (apr_size_t)ffd->block_size, 1253 rev_file->pool, 1254 rev_file->pool)); 1255 } 1256 1257 return SVN_NO_ERROR; 1258} 1259 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. 1263 */ 1264static svn_error_t * 1265get_l2p_header_body(l2p_header_t **header, 1266 svn_fs_x__revision_file_t *rev_file, 1267 svn_fs_t *fs, 1268 svn_revnum_t revision, 1269 apr_pool_t *result_pool, 1270 apr_pool_t *scratch_pool) 1271{ 1272 svn_fs_x__data_t *ffd = fs->fsap_data; 1273 apr_uint64_t value; 1274 apr_size_t i; 1275 apr_size_t page, page_count; 1276 apr_off_t offset; 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)); 1282 1283 svn_fs_x__pair_cache_key_t key; 1284 key.revision = rev_file->start_revision; 1285 key.second = rev_file->is_packed; 1286 1287 SVN_ERR(auto_open_l2p_index(rev_file, fs, revision)); 1288 packed_stream_seek(rev_file->l2p_stream, 0); 1289 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")); 1297 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")); 1304 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")); 1310 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")); 1319 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); 1325 1326 /* allocate the page tables */ 1327 result->page_table 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)); 1332 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) 1339 { 1340 value = (apr_size_t)APR_ARRAY_IDX(expanded_values, i, apr_uint64_t); 1341 if (value == 0) 1342 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL, 1343 _("Revision with no L2P index pages")); 1344 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")); 1349 1350 result->page_table_index[i+1] = page_table_index; 1351 } 1352 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")); 1356 1357 /* read actual page tables */ 1358 for (page = 0; page < page_count; ++page) 1359 { 1360 SVN_ERR(packed_stream_get(&value, rev_file->l2p_stream)); 1361 if (value == 0) 1362 return svn_error_create(SVN_ERR_FS_INDEX_CORRUPTION, NULL, 1363 _("Empty L2P index page")); 1364 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")); 1370 1371 result->page_table[page].entry_count = (apr_uint32_t)value; 1372 } 1373 1374 /* correct the page description offsets */ 1375 offset = packed_stream_offset(rev_file->l2p_stream); 1376 for (page = 0; page < page_count; ++page) 1377 { 1378 result->page_table[page].offset = offset; 1379 offset += result->page_table[page].size; 1380 } 1381 1382 /* return and cache the header */ 1383 *header = result; 1384 SVN_ERR(svn_cache__set(ffd->l2p_header_cache, &key, result, scratch_pool)); 1385 1386 return SVN_NO_ERROR; 1387} 1388 1389/* Get the page info requested in *BATON from FS and set the output fields 1390 * in *BATON. 1391 * To maximize efficiency, use or return the data stream in *STREAM. 1392 * Use SCRATCH_POOL for temporary allocations. 1393 */ 1394static svn_error_t * 1395get_l2p_page_info(l2p_page_info_baton_t *baton, 1396 svn_fs_x__revision_file_t *rev_file, 1397 svn_fs_t *fs, 1398 apr_pool_t *scratch_pool) 1399{ 1400 svn_fs_x__data_t *ffd = fs->fsap_data; 1401 l2p_header_t *result; 1402 svn_boolean_t is_cached = FALSE; 1403 void *dummy = NULL; 1404 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, 1412 scratch_pool)); 1413 if (is_cached) 1414 return SVN_NO_ERROR; 1415 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)); 1421 1422 return SVN_NO_ERROR; 1423} 1424 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 1428 * allocations. 1429 */ 1430static svn_error_t * 1431get_l2p_header(l2p_header_t **header, 1432 svn_fs_x__revision_file_t *rev_file, 1433 svn_fs_t *fs, 1434 svn_revnum_t revision, 1435 apr_pool_t *result_pool, 1436 apr_pool_t *scratch_pool) 1437{ 1438 svn_fs_x__data_t *ffd = fs->fsap_data; 1439 svn_boolean_t is_cached = FALSE; 1440 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)); 1447 if (is_cached) 1448 return SVN_NO_ERROR; 1449 1450 /* read from disk and cache the result */ 1451 SVN_ERR(get_l2p_header_body(header, rev_file, fs, revision, result_pool, 1452 scratch_pool)); 1453 1454 return SVN_NO_ERROR; 1455} 1456 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. 1461 */ 1462static svn_error_t * 1463get_l2p_page(l2p_page_t **page, 1464 svn_fs_x__revision_file_t *rev_file, 1465 svn_fs_t *fs, 1466 svn_revnum_t start_revision, 1467 l2p_page_table_entry_t *table_entry, 1468 apr_pool_t *result_pool) 1469{ 1470 apr_uint64_t value, last_value = 0; 1471 apr_uint32_t i; 1472 l2p_page_t *result = apr_pcalloc(result_pool, sizeof(*result)); 1473 apr_uint64_t container_count; 1474 apr_off_t *container_offsets; 1475 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); 1479 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)); 1486 1487 /* container offsets array */ 1488 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) 1493 { 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 */ 1498 } 1499 1500 /* read all page entries (offsets in rev file and container sub-items) */ 1501 for (i = 0; i < result->entry_count; ++i) 1502 { 1503 SVN_ERR(packed_stream_get(&value, rev_file->l2p_stream)); 1504 if (value == 0) 1505 { 1506 result->offsets[i] = -1; 1507 result->sub_items[i] = 0; 1508 } 1509 else if (value <= container_count) 1510 { 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; 1514 } 1515 else 1516 { 1517 result->offsets[i] = (apr_off_t)(value - 1 - container_count); 1518 result->sub_items[i] = 0; 1519 } 1520 } 1521 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.")); 1528 1529 *page = result; 1530 1531 return SVN_NO_ERROR; 1532} 1533 1534/* Request data structure for l2p_page_access_func. 1535 */ 1536typedef struct l2p_page_baton_t 1537{ 1538 /* in data */ 1539 /* revision. Used for error messages only */ 1540 svn_revnum_t revision; 1541 1542 /* item index to look up. Used for error messages only */ 1543 apr_uint64_t item_index; 1544 1545 /* offset within the cached page */ 1546 apr_uint32_t page_offset; 1547 1548 /* out data */ 1549 /* absolute item or container offset in rev / pack file */ 1550 apr_off_t offset; 1551 1552 /* 0 -> container / item itself; sub-item in container otherwise */ 1553 apr_uint32_t sub_item; 1554 1555} l2p_page_baton_t; 1556 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. 1560 */ 1561static svn_error_t * 1562l2p_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) 1567{ 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" 1572 " revision %ld"), 1573 apr_psprintf(scratch_pool, "%" APR_UINT64_T_FMT, 1574 baton->item_index), 1575 baton->revision); 1576 1577 /* return the result */ 1578 baton->offset = offsets[baton->page_offset]; 1579 baton->sub_item = sub_items[baton->page_offset]; 1580 1581 return SVN_NO_ERROR; 1582} 1583 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. 1586 */ 1587static svn_error_t * 1588l2p_page_access_func(void **out, 1589 const void *data, 1590 apr_size_t data_len, 1591 void *baton, 1592 apr_pool_t *result_pool) 1593{ 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); 1600 1601 /* return the requested data */ 1602 return l2p_page_get_offset(baton, page, offsets, sub_items, result_pool); 1603} 1604 1605/* Data request structure used by l2p_page_table_access_func. 1606 */ 1607typedef struct l2p_page_table_baton_t 1608{ 1609 /* revision for which to read the page table */ 1610 svn_revnum_t revision; 1611 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; 1616 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. 1619 */ 1620static svn_error_t * 1621l2p_page_table_access_func(void **out, 1622 const void *data, 1623 apr_size_t data_len, 1624 void *baton, 1625 apr_pool_t *result_pool) 1626{ 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); 1636 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) 1640 { 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]; 1645 1646 for (; entry < last_entry; ++entry) 1647 APR_ARRAY_PUSH(table_baton->pages, l2p_page_table_entry_t) 1648 = *entry; 1649 } 1650 1651 /* set output as a courtesy to the caller */ 1652 *out = table_baton->pages; 1653 1654 return SVN_NO_ERROR; 1655} 1656 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. 1664 */ 1665static svn_error_t * 1666get_l2p_page_table(apr_array_header_t *pages, 1667 svn_fs_t *fs, 1668 svn_revnum_t revision, 1669 apr_pool_t *scratch_pool) 1670{ 1671 svn_fs_x__data_t *ffd = fs->fsap_data; 1672 svn_boolean_t is_cached = FALSE; 1673 l2p_page_table_baton_t baton; 1674 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); 1678 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, 1685 scratch_pool)); 1686 1687 return SVN_NO_ERROR; 1688} 1689 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. 1696 * 1697 * This function may be a no-op if the header cache lookup fails / misses. 1698 */ 1699static svn_error_t * 1700prefetch_l2p_pages(svn_boolean_t *end, 1701 svn_fs_t *fs, 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) 1710{ 1711 svn_fs_x__data_t *ffd = fs->fsap_data; 1712 int i; 1713 apr_pool_t *iterpool; 1714 svn_fs_x__page_cache_key_t key = { 0 }; 1715 1716 /* Parameter check. */ 1717 if (min_offset < 0) 1718 min_offset = 0; 1719 1720 if (max_offset <= 0) 1721 { 1722 /* Nothing to do */ 1723 *end = TRUE; 1724 return SVN_NO_ERROR; 1725 } 1726 1727 /* get the page table for REVISION from cache */ 1728 *end = FALSE; 1729 SVN_ERR(get_l2p_page_table(pages, fs, revision, scratch_pool)); 1730 if (pages->nelts == 0) 1731 { 1732 /* not found -> we can't continue without hitting the disk again */ 1733 *end = TRUE; 1734 return SVN_NO_ERROR; 1735 } 1736 1737 /* prefetch pages individually until all are done or we found one in 1738 * the cache */ 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); 1743 1744 for (i = 0; i < pages->nelts && !*end; ++i) 1745 { 1746 svn_boolean_t is_cached; 1747 1748 l2p_page_table_entry_t *entry 1749 = &APR_ARRAY_IDX(pages, i, l2p_page_table_entry_t); 1750 svn_pool_clear(iterpool); 1751 1752 if (i == exlcuded_page_no) 1753 continue; 1754 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) 1758 { 1759 *end = TRUE; 1760 continue; 1761 } 1762 1763 /* page already in cache? */ 1764 key.page = i; 1765 SVN_ERR(svn_cache__has_key(&is_cached, ffd->l2p_page_cache, 1766 &key, iterpool)); 1767 if (!is_cached) 1768 { 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, 1773 entry, iterpool)); 1774 1775 SVN_ERR(svn_cache__set(ffd->l2p_page_cache, &key, page, 1776 iterpool)); 1777 } 1778 } 1779 1780 svn_pool_destroy(iterpool); 1781 1782 return SVN_NO_ERROR; 1783} 1784 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. 1788 */ 1789static svn_error_t * 1790l2p_index_lookup(apr_off_t *offset, 1791 apr_uint32_t *sub_item, 1792 svn_fs_t *fs, 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) 1797{ 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; 1804 void *dummy = NULL; 1805 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)); 1811 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; 1816 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; 1821 1822 SVN_ERR(svn_cache__get_partial(&dummy, &is_cached, 1823 ffd->l2p_page_cache, &key, 1824 l2p_page_access_func, &page_baton, 1825 scratch_pool)); 1826 1827 if (!is_cached) 1828 { 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); 1837 svn_boolean_t end; 1838 apr_off_t max_offset 1839 = APR_ALIGN(info_baton.entry.offset + info_baton.entry.size, 1840 ffd->block_size); 1841 apr_off_t min_offset = max_offset - ffd->block_size; 1842 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)); 1846 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)); 1851 1852 /* prefetch pages from following and preceding revisions */ 1853 pages = apr_array_make(scratch_pool, 16, 1854 sizeof(l2p_page_table_entry_t)); 1855 end = FALSE; 1856 for (prefetch_revision = revision; 1857 prefetch_revision < last_revision && !end; 1858 ++prefetch_revision) 1859 { 1860 int excluded_page_no = prefetch_revision == revision 1861 ? info_baton.page_no 1862 : -1; 1863 svn_pool_clear(iterpool); 1864 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)); 1870 } 1871 1872 end = FALSE; 1873 for (prefetch_revision = revision-1; 1874 prefetch_revision >= info_baton.first_revision && !end; 1875 --prefetch_revision) 1876 { 1877 svn_pool_clear(iterpool); 1878 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)); 1883 } 1884 1885 svn_pool_destroy(iterpool); 1886 } 1887 1888 *offset = page_baton.offset; 1889 *sub_item = page_baton.sub_item; 1890 1891 return SVN_NO_ERROR; 1892} 1893 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. 1897 */ 1898static svn_error_t * 1899l2p_proto_index_lookup(apr_off_t *offset, 1900 apr_uint32_t *sub_item, 1901 svn_fs_t *fs, 1902 svn_fs_x__txn_id_t txn_id, 1903 apr_uint64_t item_index, 1904 apr_pool_t *scratch_pool) 1905{ 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, 1910 scratch_pool), 1911 APR_READ | APR_BUFFERED, APR_OS_DEFAULT, 1912 scratch_pool)); 1913 1914 /* process all entries until we fail due to EOF */ 1915 *offset = -1; 1916 while (!eof) 1917 { 1918 l2p_proto_entry_t entry; 1919 1920 /* (attempt to) read the next entry from the source */ 1921 SVN_ERR(read_l2p_entry_from_proto_index(file, &entry, &eof, 1922 scratch_pool)); 1923 1924 /* handle new revision */ 1925 if (!eof && entry.item_index == item_index) 1926 { 1927 *offset = (apr_off_t)entry.offset - 1; 1928 *sub_item = entry.sub_item; 1929 break; 1930 } 1931 } 1932 1933 SVN_ERR(svn_io_file_close(file, scratch_pool)); 1934 1935 return SVN_NO_ERROR; 1936} 1937 1938svn_error_t * 1939svn_fs_x__l2p_get_max_ids(apr_array_header_t **max_ids, 1940 svn_fs_t *fs, 1941 svn_revnum_t start_rev, 1942 apr_size_t count, 1943 apr_pool_t *result_pool, 1944 apr_pool_t *scratch_pool) 1945{ 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); 1951 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, 1956 header_pool)); 1957 SVN_ERR(svn_fs_x__close_revision_file(rev_file)); 1958 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) 1963 { 1964 apr_uint64_t full_page_count; 1965 apr_uint64_t item_count; 1966 apr_size_t first_page_index, last_page_index; 1967 1968 if (revision >= header->first_revision + header->revision_count) 1969 { 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 1973 * issue here. */ 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)); 1980 } 1981 1982 /* in a revision with N index pages, the first N-1 index pages are 1983 * "full", i.e. contain HEADER->PAGE_SIZE entries */ 1984 first_page_index 1985 = header->page_table_index[revision - header->first_revision]; 1986 last_page_index 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; 1991 1992 APR_ARRAY_PUSH(*max_ids, apr_uint64_t) = item_count; 1993 } 1994 1995 svn_pool_destroy(header_pool); 1996 return SVN_NO_ERROR; 1997} 1998 1999/* 2000 * phys-to-log index 2001 */ 2002svn_fs_x__p2l_entry_t * 2003svn_fs_x__p2l_entry_dup(const svn_fs_x__p2l_entry_t *entry, 2004 apr_pool_t *result_pool) 2005{ 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, 2010 entry->items, 2011 entry->item_count * sizeof(*entry->items)); 2012 2013 return new_entry; 2014} 2015 2016/* 2017 * phys-to-log index 2018 */ 2019svn_error_t * 2020svn_fs_x__p2l_proto_index_open(apr_file_t **proto_index, 2021 const char *file_name, 2022 apr_pool_t *result_pool) 2023{ 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)); 2027 2028 return SVN_NO_ERROR; 2029} 2030 2031 2032svn_error_t * 2033svn_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) 2036{ 2037 apr_uint64_t revision; 2038 apr_int32_t i; 2039 2040 /* Make sure all signed elements of ENTRY have non-negative values. 2041 * 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. 2045 */ 2046 SVN_ERR_ASSERT(entry->offset >= 0); 2047 SVN_ERR_ASSERT(entry->size >= 0); 2048 2049 /* Now, all values will nicely convert to uint64. */ 2050 /* Make sure to keep P2L_PROTO_INDEX_ENTRY_SIZE consistent with this: */ 2051 2052 SVN_ERR(write_uint64_to_proto_index(proto_index, entry->offset, 2053 scratch_pool)); 2054 SVN_ERR(write_uint64_to_proto_index(proto_index, entry->size, 2055 scratch_pool)); 2056 SVN_ERR(write_uint64_to_proto_index(proto_index, entry->type, 2057 scratch_pool)); 2058 SVN_ERR(write_uint64_to_proto_index(proto_index, entry->fnv1_checksum, 2059 scratch_pool)); 2060 SVN_ERR(write_uint64_to_proto_index(proto_index, entry->item_count, 2061 scratch_pool)); 2062 2063 /* Add sub-items. */ 2064 for (i = 0; i < entry->item_count; ++i) 2065 { 2066 const svn_fs_x__id_t *sub_item = &entry->items[i]; 2067 2068 /* Make sure all signed elements of ENTRY have non-negative values. 2069 * 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. 2073 */ 2074 SVN_ERR_ASSERT( sub_item->change_set >= 0 2075 || sub_item->change_set == SVN_INVALID_REVNUM); 2076 2077 /* Write sub- record. */ 2078 revision = sub_item->change_set == SVN_INVALID_REVNUM 2079 ? 0 2080 : ((apr_uint64_t)sub_item->change_set + 1); 2081 2082 SVN_ERR(write_uint64_to_proto_index(proto_index, revision, 2083 scratch_pool)); 2084 SVN_ERR(write_uint64_to_proto_index(proto_index, sub_item->number, 2085 scratch_pool)); 2086 } 2087 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, 2091 scratch_pool)); 2092 2093 return SVN_NO_ERROR; 2094} 2095 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. 2100 */ 2101static svn_error_t * 2102read_p2l_entry_from_proto_index(apr_file_t *proto_index, 2103 svn_fs_x__p2l_entry_t *entry, 2104 svn_boolean_t *eof, 2105 apr_pool_t *scratch_pool) 2106{ 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)); 2117 2118 return SVN_NO_ERROR; 2119} 2120 2121static svn_error_t * 2122read_p2l_sub_items_from_proto_index(apr_file_t *proto_index, 2123 svn_fs_x__p2l_entry_t *entry, 2124 svn_boolean_t *eof, 2125 apr_pool_t *scratch_pool) 2126{ 2127 apr_int32_t i; 2128 for (i = 0; i < entry->item_count; ++i) 2129 { 2130 apr_uint64_t revision; 2131 svn_fs_x__id_t *sub_item = &entry->items[i]; 2132 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)); 2137 2138 /* Do the inverse REVSION number conversion (see 2139 * svn_fs_x__p2l_proto_index_add_entry), if we actually read a 2140 * complete record. 2141 */ 2142 if (!eof || !*eof) 2143 { 2144 /* Be careful with the arithmetics here (overflows and wrap-around): 2145 */ 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, 2151 revision), 2152 apr_psprintf(scratch_pool, 2153 "%" APR_UINT64_T_FMT, 2154 (apr_uint64_t)LONG_MAX)); 2155 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 2161 * checking logic. 2162 */ 2163 sub_item->change_set = revision == 0 2164 ? SVN_INVALID_REVNUM 2165 : (long)(revision - 1); 2166 } 2167 2168 } 2169 2170 return SVN_NO_ERROR; 2171} 2172 2173svn_error_t * 2174svn_fs_x__p2l_proto_index_next_offset(apr_off_t *next_offset, 2175 apr_file_t *proto_index, 2176 apr_pool_t *scratch_pool) 2177{ 2178 apr_off_t offset = 0; 2179 2180 /* Empty index file? */ 2181 SVN_ERR(svn_io_file_seek(proto_index, APR_END, &offset, scratch_pool)); 2182 if (offset == 0) 2183 { 2184 *next_offset = 0; 2185 } 2186 else 2187 { 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, 2192 scratch_pool)); 2193 } 2194 2195 return SVN_NO_ERROR; 2196} 2197 2198svn_error_t * 2199svn_fs_x__p2l_index_append(svn_checksum_t **checksum, 2200 svn_fs_t *fs, 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) 2206{ 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; 2211 int i; 2212 apr_uint32_t sub_item; 2213 svn_boolean_t eof = FALSE; 2214 unsigned char encoded[ENCODED_INT_LENGTH]; 2215 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; 2221 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)); 2227 2228 /* 64k blocks, spill after 16MB */ 2229 svn_spillbuf_t *buffer 2230 = svn_spillbuf__create(0x10000, 0x1000000, local_pool); 2231 2232 /* for loop temps ... */ 2233 apr_pool_t *iterpool = svn_pool_create(scratch_pool); 2234 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)); 2239 2240 /* process all entries until we fail due to EOF */ 2241 while (!eof) 2242 { 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; 2248 2249 svn_pool_clear(iterpool); 2250 2251 /* (attempt to) read the next entry from the source */ 2252 SVN_ERR(read_p2l_entry_from_proto_index(proto_index, &entry, 2253 &eof, iterpool)); 2254 2255 if (entry.item_count && !eof) 2256 { 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, 2260 &eof, iterpool)); 2261 } 2262 2263 /* Read entry trailer. However, we won't need its content. */ 2264 if (!eof) 2265 { 2266 apr_uint64_t trailer; 2267 SVN_ERR(read_uint64_from_proto_index(proto_index, &trailer, &eof, 2268 scratch_pool)); 2269 } 2270 2271 /* "unused" (and usually non-existent) section to cover the offsets 2272 at the end the of the last page. */ 2273 if (eof) 2274 { 2275 file_size = last_entry_end; 2276 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; 2282 entry.items = NULL; 2283 } 2284 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); 2289 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) 2293 { 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; 2297 2298 last_buffer_size = buffer_size; 2299 last_page_end += page_size; 2300 new_page = TRUE; 2301 } 2302 2303 /* this entry starts a new table -> store its offset 2304 (all following entries in the same table will store sizes only) */ 2305 if (new_page) 2306 { 2307 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded, 2308 encode_uint(encoded, entry.offset), 2309 iterpool)); 2310 last_revision = revision; 2311 } 2312 2313 /* write simple item / container entry */ 2314 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded, 2315 encode_uint(encoded, entry.size), 2316 iterpool)); 2317 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded, 2318 encode_uint(encoded, entry.type + entry.item_count * 16), 2319 iterpool)); 2320 SVN_ERR(svn_spillbuf__write(buffer, (const char *)encoded, 2321 encode_uint(encoded, entry.fnv1_checksum), 2322 iterpool)); 2323 2324 /* container contents (only one for non-container items) */ 2325 for (sub_item = 0; sub_item < entry.item_count; ++sub_item) 2326 { 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), 2332 iterpool)); 2333 last_revision = item_rev; 2334 } 2335 2336 for (sub_item = 0; sub_item < entry.item_count; ++sub_item) 2337 { 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), 2341 iterpool)); 2342 last_number = entry.items[sub_item].number; 2343 } 2344 2345 last_entry_end = entry_end; 2346 } 2347 2348 /* close the source file */ 2349 SVN_ERR(svn_io_file_close(proto_index, local_pool)); 2350 2351 /* store length of last table */ 2352 APR_ARRAY_PUSH(table_sizes, apr_uint64_t) 2353 = svn_spillbuf__get_size(buffer) - last_buffer_size; 2354 2355 /* Open target stream. */ 2356 stream = svn_stream_checksummed2(svn_stream_from_aprfile2(index_file, TRUE, 2357 local_pool), 2358 NULL, checksum, svn_checksum_md5, FALSE, 2359 result_pool); 2360 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)); 2366 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) 2370 { 2371 apr_uint64_t value = APR_ARRAY_IDX(table_sizes, i, apr_uint64_t); 2372 SVN_ERR(stream_write_encoded(stream, value)); 2373 } 2374 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)); 2378 2379 svn_pool_destroy(iterpool); 2380 svn_pool_destroy(local_pool); 2381 2382 return SVN_NO_ERROR; 2383} 2384 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. 2387 */ 2388static svn_error_t * 2389auto_open_p2l_index(svn_fs_x__revision_file_t *rev_file, 2390 svn_fs_t *fs, 2391 svn_revnum_t revision) 2392{ 2393 if (rev_file->p2l_stream == NULL) 2394 { 2395 svn_fs_x__data_t *ffd = fs->fsap_data; 2396 2397 SVN_ERR(svn_fs_x__auto_read_footer(rev_file)); 2398 SVN_ERR(packed_stream_open(&rev_file->p2l_stream, 2399 rev_file->file, 2400 rev_file->p2l_offset, 2401 rev_file->footer_offset, 2402 P2L_STREAM_PREFIX, 2403 (apr_size_t)ffd->block_size, 2404 rev_file->pool, 2405 rev_file->pool)); 2406 } 2407 2408 return SVN_NO_ERROR; 2409} 2410 2411/* Data structure that describes which p2l page info shall be extracted 2412 * from the cache and contains the fields that receive the result. 2413 */ 2414typedef struct p2l_page_info_baton_t 2415{ 2416 /* input variables */ 2417 /* revision identifying the index file */ 2418 svn_revnum_t revision; 2419 2420 /* offset within the page in rev / pack file */ 2421 apr_off_t offset; 2422 2423 /* output variables */ 2424 /* page containing OFFSET */ 2425 apr_size_t page_no; 2426 2427 /* first revision in this p2l index */ 2428 svn_revnum_t first_revision; 2429 2430 /* offset within the p2l index file describing this page */ 2431 apr_off_t start_offset; 2432 2433 /* offset within the p2l index file describing the following page */ 2434 apr_off_t next_offset; 2435 2436 /* PAGE_NO * PAGE_SIZE (if <= OFFSET) */ 2437 apr_off_t page_start; 2438 2439 /* total number of pages indexed */ 2440 apr_size_t page_count; 2441 2442 /* size of each page in pack / rev file */ 2443 apr_uint64_t page_size; 2444} p2l_page_info_baton_t; 2445 2446/* From HEADER and the list of all OFFSETS, fill BATON with the page info 2447 * requested by BATON->OFFSET. 2448 */ 2449static void 2450p2l_page_info_copy(p2l_page_info_baton_t *baton, 2451 const p2l_header_t *header, 2452 const apr_off_t *offsets) 2453{ 2454 /* if the requested offset is out of bounds, return info for 2455 * a zero-sized empty page right behind the last page. 2456 */ 2457 if (baton->offset / header->page_size < header->page_count) 2458 { 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; 2464 } 2465 else 2466 { 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; 2472 } 2473 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; 2477} 2478 2479/* Implement svn_cache__partial_getter_func_t: extract the p2l page info 2480 * requested by BATON and return it in BATON. 2481 */ 2482static svn_error_t * 2483p2l_page_info_func(void **out, 2484 const void *data, 2485 apr_size_t data_len, 2486 void *baton, 2487 apr_pool_t *result_pool) 2488{ 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); 2494 2495 /* copy data from cache to BATON */ 2496 p2l_page_info_copy(baton, header, offsets); 2497 return SVN_NO_ERROR; 2498} 2499 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. 2503 */ 2504static svn_error_t * 2505get_p2l_header(p2l_header_t **header, 2506 svn_fs_x__revision_file_t *rev_file, 2507 svn_fs_t *fs, 2508 svn_revnum_t revision, 2509 apr_pool_t *result_pool, 2510 apr_pool_t *scratch_pool) 2511{ 2512 svn_fs_x__data_t *ffd = fs->fsap_data; 2513 apr_uint64_t value; 2514 apr_size_t i; 2515 apr_off_t offset; 2516 p2l_header_t *result; 2517 svn_boolean_t is_cached = FALSE; 2518 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; 2523 2524 SVN_ERR(svn_cache__get((void**)header, &is_cached, ffd->p2l_header_cache, 2525 &key, result_pool)); 2526 if (is_cached) 2527 return SVN_NO_ERROR; 2528 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); 2533 2534 /* allocate result data structure */ 2535 result = apr_pcalloc(result_pool, sizeof(*result)); 2536 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")); 2543 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")); 2549 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")); 2555 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")); 2561 2562 result->offsets 2563 = apr_pcalloc(result_pool, (result->page_count + 1) * sizeof(*result->offsets)); 2564 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) 2568 { 2569 SVN_ERR(packed_stream_get(&value, rev_file->p2l_stream)); 2570 result->offsets[i+1] = result->offsets[i] + (apr_off_t)value; 2571 } 2572 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; 2577 2578 /* cache the header data */ 2579 SVN_ERR(svn_cache__set(ffd->p2l_header_cache, &key, result, scratch_pool)); 2580 2581 /* return the result */ 2582 *header = result; 2583 2584 return SVN_NO_ERROR; 2585} 2586 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. 2591 */ 2592static svn_error_t * 2593get_p2l_page_info(p2l_page_info_baton_t *baton, 2594 svn_fs_x__revision_file_t *rev_file, 2595 svn_fs_t *fs, 2596 apr_pool_t *scratch_pool) 2597{ 2598 svn_fs_x__data_t *ffd = fs->fsap_data; 2599 p2l_header_t *header; 2600 svn_boolean_t is_cached = FALSE; 2601 void *dummy = NULL; 2602 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); 2607 2608 SVN_ERR(svn_cache__get_partial(&dummy, &is_cached, ffd->p2l_header_cache, 2609 &key, p2l_page_info_func, baton, 2610 scratch_pool)); 2611 if (is_cached) 2612 return SVN_NO_ERROR; 2613 2614 SVN_ERR(get_p2l_header(&header, rev_file, fs, baton->revision, 2615 scratch_pool, scratch_pool)); 2616 2617 /* copy the requested info into *BATON */ 2618 p2l_page_info_copy(baton, header, header->offsets); 2619 2620 return SVN_NO_ERROR; 2621} 2622 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. 2626 */ 2627static svn_error_t * 2628read_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) 2632{ 2633 apr_uint64_t value; 2634 apr_uint64_t number = 0; 2635 apr_uint32_t sub_item; 2636 2637 svn_fs_x__p2l_entry_t entry; 2638 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); 2645 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")); 2650 2651 SVN_ERR(packed_stream_get(&value, stream)); 2652 entry.fnv1_checksum = (apr_uint32_t)value; 2653 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")); 2660 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")); 2669 2670 if (entry.item_count == 0) 2671 { 2672 entry.items = NULL; 2673 } 2674 else 2675 { 2676 entry.items 2677 = apr_pcalloc(result->pool, entry.item_count * sizeof(*entry.items)); 2678 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")); 2683 2684 for (sub_item = 0; sub_item < entry.item_count; ++sub_item) 2685 { 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); 2690 } 2691 2692 for (sub_item = 0; sub_item < entry.item_count; ++sub_item) 2693 { 2694 SVN_ERR(packed_stream_get(&value, stream)); 2695 number += value % 2 ? -1 - value / 2 : value / 2; 2696 entry.items[sub_item].number = number; 2697 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")); 2703 } 2704 } 2705 2706 APR_ARRAY_PUSH(result, svn_fs_x__p2l_entry_t) = entry; 2707 *item_offset += entry.size; 2708 2709 return SVN_NO_ERROR; 2710} 2711 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. 2718 */ 2719static svn_error_t * 2720get_p2l_page(apr_array_header_t **entries, 2721 svn_fs_x__revision_file_t *rev_file, 2722 svn_fs_t *fs, 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) 2729{ 2730 apr_uint64_t value; 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; 2734 apr_off_t offset; 2735 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); 2739 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; 2744 2745 /* Special case: empty pages. */ 2746 if (start_offset == next_offset) 2747 { 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, 2751 result)); 2752 } 2753 else 2754 { 2755 /* Read non-empty page. */ 2756 do 2757 { 2758 SVN_ERR(read_entry(rev_file->p2l_stream, &item_offset, 2759 start_revision, result)); 2760 offset = packed_stream_offset(rev_file->p2l_stream); 2761 } 2762 while (offset < next_offset); 2763 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")); 2769 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) 2773 { 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)); 2778 } 2779 } 2780 2781 *entries = result; 2782 2783 return SVN_NO_ERROR; 2784} 2785 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. 2790 * 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. 2796 */ 2797static svn_error_t * 2798prefetch_p2l_page(svn_boolean_t *end, 2799 int *leaking_bucket, 2800 svn_fs_t *fs, 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) 2805{ 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 }; 2810 2811 /* fetch the page info */ 2812 *end = FALSE; 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) 2816 { 2817 /* page outside limits -> stop prefetching */ 2818 *end = TRUE; 2819 return SVN_NO_ERROR; 2820 } 2821 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)); 2829 2830 /* yes, already cached */ 2831 if (already_cached) 2832 { 2833 /* stop prefetching if most pages are already cached. */ 2834 if (!--*leaking_bucket) 2835 *end = TRUE; 2836 2837 return SVN_NO_ERROR; 2838 } 2839 2840 ++*leaking_bucket; 2841 2842 /* read from disk */ 2843 SVN_ERR(get_p2l_page(&page, rev_file, fs, 2844 baton->first_revision, 2845 baton->start_offset, 2846 baton->next_offset, 2847 baton->page_start, 2848 baton->page_size, 2849 scratch_pool)); 2850 2851 /* and put it into our cache */ 2852 SVN_ERR(svn_cache__set(ffd->p2l_page_cache, &key, page, scratch_pool)); 2853 2854 return SVN_NO_ERROR; 2855} 2856 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 2861 * allocations. 2862 */ 2863static svn_error_t * 2864get_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, 2867 svn_fs_t *fs, 2868 svn_revnum_t revision, 2869 apr_off_t offset, 2870 apr_pool_t *scratch_pool) 2871{ 2872 p2l_page_info_baton_t page_info; 2873 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)); 2879 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); 2885 2886 /* return results */ 2887 if (page_info_p) 2888 *page_info_p = page_info; 2889 2890 /* construct cache key */ 2891 if (key_p) 2892 { 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; 2898 2899 *key_p = key; 2900 } 2901 2902 return SVN_NO_ERROR; 2903} 2904 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. */ 2907static int 2908compare_start_p2l_entry(const void *lhs, 2909 const void *rhs) 2910{ 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; 2914 2915 /* restrict result to int */ 2916 return diff < 0 ? -1 : (diff == 0 ? 0 : 1); 2917} 2918 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. */ 2923static void 2924append_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) 2929{ 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); 2933 2934 /* start at the first entry that overlaps with BLOCK_START */ 2935 if (idx > 0) 2936 { 2937 entry = &APR_ARRAY_IDX(page_entries, idx - 1, svn_fs_x__p2l_entry_t); 2938 if (entry->offset + entry->size > block_start) 2939 --idx; 2940 } 2941 2942 /* copy all entries covering the requested range */ 2943 for ( ; idx < page_entries->nelts; ++idx) 2944 { 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) 2948 break; 2949 2950 /* Copy the entry record. */ 2951 copy = apr_array_push(entries); 2952 *copy = *entry; 2953 2954 /* Copy the items of that entries. */ 2955 if (entry->item_count) 2956 { 2957 const svn_fs_x__id_t *items 2958 = resolve_ptr 2959 ? svn_temp_deserializer__ptr(page_entries->elts, 2960 (const void * const *)&entry->items) 2961 : entry->items; 2962 2963 copy->items = apr_pmemdup(entries->pool, items, 2964 entry->item_count * sizeof(*items)); 2965 } 2966 } 2967} 2968 2969/* Auxilliary struct passed to p2l_entries_func selecting the relevant 2970 * data range. */ 2971typedef struct p2l_entries_baton_t 2972{ 2973 apr_off_t start; 2974 apr_off_t end; 2975} p2l_entries_baton_t; 2976 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. 2980 */ 2981static svn_error_t * 2982p2l_entries_func(void **out, 2983 const void *data, 2984 apr_size_t data_len, 2985 void *baton, 2986 apr_pool_t *result_pool) 2987{ 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; 2991 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); 2996 2997 /* append relevant information to result */ 2998 append_p2l_entries(entries, &page, block->start, block->end, TRUE); 2999 3000 return SVN_NO_ERROR; 3001} 3002 3003 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. 3007 */ 3008static svn_error_t * 3009p2l_index_lookup(apr_array_header_t *entries, 3010 svn_fs_x__revision_file_t *rev_file, 3011 svn_fs_t *fs, 3012 svn_revnum_t revision, 3013 apr_off_t block_start, 3014 apr_off_t block_end, 3015 apr_pool_t *scratch_pool) 3016{ 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; 3022 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; 3027 3028 /* if we requested an empty range, the result would be empty */ 3029 SVN_ERR_ASSERT(block_start < block_end); 3030 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, 3033 scratch_pool)); 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)); 3037 3038 if (!is_cached) 3039 { 3040 svn_boolean_t end; 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; 3046 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; 3051 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. 3055 */ 3056 3057 /* pre-fetch preceding pages */ 3058 end = FALSE; 3059 prefetch_info.offset = original_page_start; 3060 while (prefetch_info.offset >= prefetch_info.page_size && !end) 3061 { 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); 3066 } 3067 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)); 3075 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) 3079 { 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."), 3088 revision); 3089 } 3090 3091 SVN_ERR(svn_cache__set(ffd->p2l_page_cache, &key, page_entries, 3092 iterpool)); 3093 3094 /* append relevant information to result */ 3095 append_p2l_entries(entries, page_entries, block_start, block_end, FALSE); 3096 3097 /* pre-fetch following pages */ 3098 end = FALSE; 3099 leaking_bucket = 4; 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 3104 && !end) 3105 { 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); 3110 } 3111 3112 svn_pool_destroy(iterpool); 3113 } 3114 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); 3118 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) 3124 { 3125 svn_fs_x__p2l_entry_t *entry 3126 = &APR_ARRAY_IDX(entries, entries->nelts-1, svn_fs_x__p2l_entry_t); 3127 3128 apr_off_t entry_end = entry->offset + entry->size; 3129 if (entry_end < block_end) 3130 { 3131 if (entry->type == SVN_FS_X__ITEM_TYPE_UNUSED) 3132 { 3133 /* extend the terminal filler */ 3134 entry->size = block_end - entry->offset; 3135 } 3136 else 3137 { 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; 3146 } 3147 } 3148 } 3149 3150 return SVN_NO_ERROR; 3151} 3152 3153svn_error_t * 3154svn_fs_x__p2l_index_lookup(apr_array_header_t **entries, 3155 svn_fs_t *fs, 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) 3162{ 3163 apr_off_t block_end = block_start + block_size; 3164 3165 /* the receiving container */ 3166 int last_count = 0; 3167 apr_array_header_t *result = apr_array_make(result_pool, 16, 3168 sizeof(svn_fs_x__p2l_entry_t)); 3169 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) 3174 { 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); 3179 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; 3183 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) 3187 { 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); 3193 } 3194 3195 last_count = result->nelts; 3196 } 3197 3198 *entries = result; 3199 return SVN_NO_ERROR; 3200} 3201 3202/* compare_fn_t comparing a svn_fs_x__p2l_entry_t at LHS with an offset 3203 * RHS. 3204 */ 3205static int 3206compare_p2l_entry_offsets(const void *lhs, const void *rhs) 3207{ 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; 3210 3211 return entry->offset < offset ? -1 : (entry->offset == offset ? 0 : 1); 3212} 3213 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. 3218 */ 3219static svn_fs_x__p2l_entry_t * 3220get_p2l_entry_from_cached_page(const void *data, 3221 apr_off_t offset, 3222 apr_pool_t *result_pool, 3223 apr_pool_t *scratch_pool) 3224{ 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, 3228 sizeof(*page)); 3229 svn_fs_x__p2l_entry_t *entry; 3230 3231 entries->elts = (char *)svn_temp_deserializer__ptr(page, 3232 (const void *const *)&page->elts); 3233 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); 3237 3238 /* return it, if it is a perfect match */ 3239 if (entry) 3240 { 3241 svn_fs_x__p2l_entry_t *result 3242 = apr_pmemdup(result_pool, entry, sizeof(*result)); 3243 result->items 3244 = (svn_fs_x__id_t *)svn_temp_deserializer__ptr(entries->elts, 3245 (const void *const *)&entry->items); 3246 return result; 3247 } 3248 3249 return NULL; 3250} 3251 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. 3255 */ 3256static svn_error_t * 3257p2l_entry_lookup_func(void **out, 3258 const void *data, 3259 apr_size_t data_len, 3260 void *baton, 3261 apr_pool_t *result_pool) 3262{ 3263 svn_fs_x__p2l_entry_t *entry 3264 = get_p2l_entry_from_cached_page(data, *(apr_off_t *)baton, result_pool, 3265 result_pool); 3266 3267 *out = entry && entry->offset == *(apr_off_t *)baton 3268 ? svn_fs_x__p2l_entry_dup(entry, result_pool) 3269 : NULL; 3270 3271 return SVN_NO_ERROR; 3272} 3273 3274static svn_error_t * 3275p2l_entry_lookup(svn_fs_x__p2l_entry_t **entry_p, 3276 svn_fs_x__revision_file_t *rev_file, 3277 svn_fs_t *fs, 3278 svn_revnum_t revision, 3279 apr_off_t offset, 3280 apr_pool_t *result_pool, 3281 apr_pool_t *scratch_pool) 3282{ 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; 3287 3288 /* look for this info in our cache */ 3289 SVN_ERR(get_p2l_keys(&page_info, &key, rev_file, fs, revision, offset, 3290 scratch_pool)); 3291 SVN_ERR(svn_cache__get_partial((void**)entry_p, &is_cached, 3292 ffd->p2l_page_cache, &key, 3293 p2l_entry_lookup_func, &offset, 3294 result_pool)); 3295 if (!is_cached) 3296 { 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, 3300 sizeof(**entry_p)); 3301 SVN_ERR(p2l_index_lookup(entries, rev_file, fs, revision, offset, 3302 offset + 1, scratch_pool)); 3303 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); 3307 } 3308 3309 return SVN_NO_ERROR; 3310} 3311 3312svn_error_t * 3313svn_fs_x__p2l_entry_lookup(svn_fs_x__p2l_entry_t **entry_p, 3314 svn_fs_t *fs, 3315 svn_fs_x__revision_file_t *rev_file, 3316 svn_revnum_t revision, 3317 apr_off_t offset, 3318 apr_pool_t *result_pool, 3319 apr_pool_t *scratch_pool) 3320{ 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)); 3324 3325 return SVN_NO_ERROR; 3326} 3327 3328/* Baton structure for p2l_item_lookup_func. It describes which sub_item 3329 * info shall be returned. 3330 */ 3331typedef struct p2l_item_lookup_baton_t 3332{ 3333 /* file offset to find the P2L index entry for */ 3334 apr_off_t offset; 3335 3336 /* return the sub-item at this position within that entry */ 3337 apr_uint32_t sub_item; 3338} p2l_item_lookup_baton_t; 3339 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. 3344 */ 3345static svn_error_t * 3346p2l_item_lookup_func(void **out, 3347 const void *data, 3348 apr_size_t data_len, 3349 void *baton, 3350 apr_pool_t *result_pool) 3351{ 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, 3355 result_pool); 3356 3357 *out = entry 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)) 3363 : NULL; 3364 3365 return SVN_NO_ERROR; 3366} 3367 3368svn_error_t * 3369svn_fs_x__p2l_item_lookup(svn_fs_x__id_t **item, 3370 svn_fs_t *fs, 3371 svn_fs_x__revision_file_t *rev_file, 3372 svn_revnum_t revision, 3373 apr_off_t offset, 3374 apr_uint32_t sub_item, 3375 apr_pool_t *result_pool, 3376 apr_pool_t *scratch_pool) 3377{ 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; 3383 3384 *item = NULL; 3385 3386 /* look for this info in our cache */ 3387 SVN_ERR(get_p2l_keys(&page_info, &key, rev_file, fs, revision, offset, 3388 scratch_pool)); 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)); 3394 if (!is_cached) 3395 { 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)); 3401 3402 /* return result */ 3403 if (entry && entry->item_count > sub_item) 3404 *item = apr_pmemdup(result_pool, entry->items + sub_item, 3405 sizeof(**item)); 3406 } 3407 3408 return SVN_NO_ERROR; 3409} 3410 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. 3413 */ 3414static svn_error_t * 3415p2l_get_max_offset_func(void **out, 3416 const void *data, 3417 apr_size_t data_len, 3418 void *baton, 3419 apr_pool_t *result_pool) 3420{ 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)); 3424 3425 return SVN_NO_ERROR; 3426} 3427 3428svn_error_t * 3429svn_fs_x__p2l_get_max_offset(apr_off_t *offset, 3430 svn_fs_t *fs, 3431 svn_fs_x__revision_file_t *rev_file, 3432 svn_revnum_t revision, 3433 apr_pool_t *scratch_pool) 3434{ 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; 3439 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); 3444 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, 3448 scratch_pool)); 3449 if (is_cached) 3450 { 3451 *offset = *offset_p; 3452 return SVN_NO_ERROR; 3453 } 3454 3455 SVN_ERR(get_p2l_header(&header, rev_file, fs, revision, scratch_pool, 3456 scratch_pool)); 3457 *offset = header->file_size; 3458 3459 return SVN_NO_ERROR; 3460} 3461 3462svn_error_t * 3463svn_fs_x__item_offset(apr_off_t *absolute_position, 3464 apr_uint32_t *sub_item, 3465 svn_fs_t *fs, 3466 svn_fs_x__revision_file_t *rev_file, 3467 const svn_fs_x__id_t *item_id, 3468 apr_pool_t *scratch_pool) 3469{ 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)); 3474 else 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)); 3478 3479 return SVN_NO_ERROR; 3480} 3481 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. */ 3485static svn_error_t * 3486calc_fnv1(svn_fs_x__p2l_entry_t *entry, 3487 svn_fs_x__revision_file_t *rev_file, 3488 apr_pool_t *scratch_pool) 3489{ 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; 3495 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. 3498 */ 3499 if (entry->type == SVN_FS_X__ITEM_TYPE_UNUSED) 3500 { 3501 entry->fnv1_checksum = 0; 3502 return SVN_NO_ERROR; 3503 } 3504 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, 3507 scratch_pool)); 3508 while (size > 0) 3509 { 3510 apr_size_t to_read = size > sizeof(buffer) 3511 ? sizeof(buffer) 3512 : (apr_size_t)size; 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)); 3516 size -= to_read; 3517 } 3518 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); 3522 3523 return SVN_NO_ERROR; 3524} 3525 3526/* 3527 * Index (re-)creation utilities. 3528 */ 3529 3530svn_error_t * 3531svn_fs_x__p2l_index_from_p2l_entries(const char **protoname, 3532 svn_fs_t *fs, 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) 3537{ 3538 apr_file_t *proto_index; 3539 3540 /* Use a subpool for immediate temp file cleanup at the end of this 3541 * function. */ 3542 apr_pool_t *iterpool = svn_pool_create(scratch_pool); 3543 int i; 3544 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, 3550 scratch_pool)); 3551 3552 /* Write ENTRIES to proto-index file and calculate checksums as we go. */ 3553 for (i = 0; i < entries->nelts; ++i) 3554 { 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); 3558 3559 SVN_ERR(calc_fnv1(entry, rev_file, iterpool)); 3560 SVN_ERR(svn_fs_x__p2l_proto_index_add_entry(proto_index, entry, 3561 iterpool)); 3562 } 3563 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)); 3569 3570 /* Temp file cleanup. */ 3571 svn_pool_destroy(iterpool); 3572 3573 return SVN_NO_ERROR; 3574} 3575 3576/* Decorator for svn_fs_x__p2l_entry_t that associates it with a sorted 3577 * variant of its ITEMS array. 3578 */ 3579typedef struct sub_item_ordered_t 3580{ 3581 /* ENTRY that got wrapped */ 3582 svn_fs_x__p2l_entry_t *entry; 3583 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; 3588 3589/* implements compare_fn_t. Place LHS before RHS, if the latter is younger. 3590 * Used to sort sub_item_ordered_t::order 3591 */ 3592static int 3593compare_sub_items(const svn_fs_x__id_t * const * lhs, 3594 const svn_fs_x__id_t * const * rhs) 3595{ 3596 return (*lhs)->change_set < (*rhs)->change_set 3597 ? 1 3598 : ((*lhs)->change_set > (*rhs)->change_set ? -1 : 0); 3599} 3600 3601/* implements compare_fn_t. Place LHS before RHS, if the latter belongs to 3602 * a newer revision. 3603 */ 3604static int 3605compare_p2l_info_rev(const sub_item_ordered_t * lhs, 3606 const sub_item_ordered_t * rhs) 3607{ 3608 svn_fs_x__id_t *lhs_part; 3609 svn_fs_x__id_t *rhs_part; 3610 3611 assert(lhs != rhs); 3612 if (lhs->entry->item_count == 0) 3613 return rhs->entry->item_count == 0 ? 0 : -1; 3614 if (rhs->entry->item_count == 0) 3615 return 1; 3616 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]; 3621 3622 if (lhs_part->change_set == rhs_part->change_set) 3623 return 0; 3624 3625 return lhs_part->change_set < rhs_part->change_set ? -1 : 1; 3626} 3627 3628svn_error_t * 3629svn_fs_x__l2p_index_from_p2l_entries(const char **protoname, 3630 svn_fs_t *fs, 3631 apr_array_header_t *entries, 3632 apr_pool_t *result_pool, 3633 apr_pool_t *scratch_pool) 3634{ 3635 apr_file_t *proto_index; 3636 3637 /* Use a subpool for immediate temp file cleanup at the end of this 3638 * function. */ 3639 apr_pool_t *iterpool = svn_pool_create(scratch_pool); 3640 svn_revnum_t prev_rev = SVN_INVALID_REVNUM; 3641 int i; 3642 apr_uint32_t k; 3643 svn_priority_queue__t *queue; 3644 apr_size_t count = 0; 3645 apr_array_header_t *sub_item_orders; 3646 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, 3652 scratch_pool)); 3653 3654 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; 3660 3661 for (i = 0; i < entries->nelts; ++i) 3662 { 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); 3667 3668 /* skip unused regions (e.g. padding) */ 3669 if (entry->item_count == 0) 3670 { 3671 --sub_item_orders->nelts; 3672 continue; 3673 } 3674 3675 assert(entry); 3676 ordered->entry = entry; 3677 count += entry->item_count; 3678 3679 if (entry->item_count > 1) 3680 { 3681 ordered->order 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]; 3686 3687 qsort(ordered->order, entry->item_count, sizeof(*ordered->order), 3688 (int (*)(const void *, const void *))compare_sub_items); 3689 } 3690 } 3691 3692 /* we need to write the index in ascending revision order */ 3693 queue = svn_priority_queue__create 3694 (sub_item_orders, 3695 (int (*)(const void *, const void *))compare_p2l_info_rev); 3696 3697 /* write index entries */ 3698 for (i = 0; i < count; ++i) 3699 { 3700 svn_fs_x__id_t *sub_item; 3701 sub_item_ordered_t *ordered = svn_priority_queue__peek(queue); 3702 3703 if (ordered->entry->item_count > 0) 3704 { 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]; 3710 3711 /* next revision? */ 3712 if (prev_rev != svn_fs_x__get_revnum(sub_item->change_set)) 3713 { 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)); 3717 } 3718 3719 /* add entry */ 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)); 3724 3725 /* make ITEM_COUNT point the next sub-item to use+1 */ 3726 --ordered->entry->item_count; 3727 } 3728 3729 /* process remaining sub-items (if any) of that container later */ 3730 if (ordered->entry->item_count) 3731 svn_priority_queue__update(queue); 3732 else 3733 svn_priority_queue__pop(queue); 3734 3735 /* keep memory usage in check */ 3736 if (i % 256 == 0) 3737 svn_pool_clear(iterpool); 3738 } 3739 3740 /* Convert proto-index into final index and move it into position. */ 3741 SVN_ERR(svn_io_file_close(proto_index, iterpool)); 3742 3743 /* Temp file cleanup. */ 3744 svn_pool_destroy(iterpool); 3745 3746 return SVN_NO_ERROR; 3747} 3748 3749 3750/* 3751 * Standard (de-)serialization functions 3752 */ 3753 3754svn_error_t * 3755svn_fs_x__serialize_l2p_header(void **data, 3756 apr_size_t *data_len, 3757 void *in, 3758 apr_pool_t *pool) 3759{ 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; 3768 3769 /* serialize header and all its elements */ 3770 context = svn_temp_serializer__init(header, 3771 sizeof(*header), 3772 data_size + 32, 3773 pool); 3774 3775 /* page table index array */ 3776 svn_temp_serializer__add_leaf(context, 3777 (const void * const *)&header->page_table_index, 3778 index_size); 3779 3780 /* page table array */ 3781 svn_temp_serializer__add_leaf(context, 3782 (const void * const *)&header->page_table, 3783 page_table_size); 3784 3785 /* return the serialized result */ 3786 serialized = svn_temp_serializer__get(context); 3787 3788 *data = serialized->data; 3789 *data_len = serialized->len; 3790 3791 return SVN_NO_ERROR; 3792} 3793 3794svn_error_t * 3795svn_fs_x__deserialize_l2p_header(void **out, 3796 void *data, 3797 apr_size_t data_len, 3798 apr_pool_t *pool) 3799{ 3800 l2p_header_t *header = (l2p_header_t *)data; 3801 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); 3805 3806 /* done */ 3807 *out = header; 3808 3809 return SVN_NO_ERROR; 3810} 3811 3812svn_error_t * 3813svn_fs_x__serialize_l2p_page(void **data, 3814 apr_size_t *data_len, 3815 void *in, 3816 apr_pool_t *pool) 3817{ 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); 3823 3824 /* serialize struct and all its elements */ 3825 context = svn_temp_serializer__init(page, 3826 sizeof(*page), 3827 of_table_size + si_table_size 3828 + sizeof(*page) + 32, 3829 pool); 3830 3831 /* offsets and sub_items arrays */ 3832 svn_temp_serializer__add_leaf(context, 3833 (const void * const *)&page->offsets, 3834 of_table_size); 3835 svn_temp_serializer__add_leaf(context, 3836 (const void * const *)&page->sub_items, 3837 si_table_size); 3838 3839 /* return the serialized result */ 3840 serialized = svn_temp_serializer__get(context); 3841 3842 *data = serialized->data; 3843 *data_len = serialized->len; 3844 3845 return SVN_NO_ERROR; 3846} 3847 3848svn_error_t * 3849svn_fs_x__deserialize_l2p_page(void **out, 3850 void *data, 3851 apr_size_t data_len, 3852 apr_pool_t *pool) 3853{ 3854 l2p_page_t *page = data; 3855 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); 3859 3860 /* done */ 3861 *out = page; 3862 3863 return SVN_NO_ERROR; 3864} 3865 3866svn_error_t * 3867svn_fs_x__serialize_p2l_header(void **data, 3868 apr_size_t *data_len, 3869 void *in, 3870 apr_pool_t *pool) 3871{ 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); 3876 3877 /* serialize header and all its elements */ 3878 context = svn_temp_serializer__init(header, 3879 sizeof(*header), 3880 table_size + sizeof(*header) + 32, 3881 pool); 3882 3883 /* offsets array */ 3884 svn_temp_serializer__add_leaf(context, 3885 (const void * const *)&header->offsets, 3886 table_size); 3887 3888 /* return the serialized result */ 3889 serialized = svn_temp_serializer__get(context); 3890 3891 *data = serialized->data; 3892 *data_len = serialized->len; 3893 3894 return SVN_NO_ERROR; 3895} 3896 3897svn_error_t * 3898svn_fs_x__deserialize_p2l_header(void **out, 3899 void *data, 3900 apr_size_t data_len, 3901 apr_pool_t *pool) 3902{ 3903 p2l_header_t *header = data; 3904 3905 /* resolve the only pointer in the struct */ 3906 svn_temp_deserializer__resolve(header, (void**)&header->offsets); 3907 3908 /* done */ 3909 *out = header; 3910 3911 return SVN_NO_ERROR; 3912} 3913 3914svn_error_t * 3915svn_fs_x__serialize_p2l_page(void **data, 3916 apr_size_t *data_len, 3917 void *in, 3918 apr_pool_t *pool) 3919{ 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; 3925 int i; 3926 3927 /* serialize array header and all its elements */ 3928 context = svn_temp_serializer__init(page, 3929 sizeof(*page), 3930 table_size + sizeof(*page) + 32, 3931 pool); 3932 3933 /* items in the array */ 3934 svn_temp_serializer__push(context, 3935 (const void * const *)&page->elts, 3936 table_size); 3937 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)); 3943 3944 svn_temp_serializer__pop(context); 3945 3946 /* return the serialized result */ 3947 serialized = svn_temp_serializer__get(context); 3948 3949 *data = serialized->data; 3950 *data_len = serialized->len; 3951 3952 return SVN_NO_ERROR; 3953} 3954 3955svn_error_t * 3956svn_fs_x__deserialize_p2l_page(void **out, 3957 void *data, 3958 apr_size_t data_len, 3959 apr_pool_t *pool) 3960{ 3961 apr_array_header_t *page = (apr_array_header_t *)data; 3962 svn_fs_x__p2l_entry_t *entries; 3963 int i; 3964 3965 /* resolve the only pointer in the struct */ 3966 svn_temp_deserializer__resolve(page, (void**)&page->elts); 3967 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); 3972 3973 /* patch up members */ 3974 page->pool = pool; 3975 page->nalloc = page->nelts; 3976 3977 /* done */ 3978 *out = page; 3979 3980 return SVN_NO_ERROR; 3981} 3982