1/* temp_serializer.c: serialization functions for caching of FSFS structures 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 <apr_pools.h> 24 25#include "svn_pools.h" 26#include "svn_hash.h" 27 28#include "id.h" 29#include "svn_fs.h" 30 31#include "private/svn_fs_util.h" 32#include "private/svn_temp_serializer.h" 33#include "private/svn_subr_private.h" 34 35#include "temp_serializer.h" 36 37/* Utility to encode a signed NUMBER into a variable-length sequence of 38 * 8-bit chars in KEY_BUFFER and return the last writen position. 39 * 40 * Numbers will be stored in 7 bits / byte and using byte values above 41 * 32 (' ') to make them combinable with other string by simply separating 42 * individual parts with spaces. 43 */ 44static char* 45encode_number(apr_int64_t number, char *key_buffer) 46{ 47 /* encode the sign in the first byte */ 48 if (number < 0) 49 { 50 number = -number; 51 *key_buffer = (char)((number & 63) + ' ' + 65); 52 } 53 else 54 *key_buffer = (char)((number & 63) + ' ' + 1); 55 number /= 64; 56 57 /* write 7 bits / byte until no significant bits are left */ 58 while (number) 59 { 60 *++key_buffer = (char)((number & 127) + ' ' + 1); 61 number /= 128; 62 } 63 64 /* return the last written position */ 65 return key_buffer; 66} 67 68const char* 69svn_fs_fs__combine_number_and_string(apr_int64_t number, 70 const char *string, 71 apr_pool_t *pool) 72{ 73 apr_size_t len = strlen(string); 74 75 /* number part requires max. 10x7 bits + 1 space. 76 * Add another 1 for the terminal 0 */ 77 char *key_buffer = apr_palloc(pool, len + 12); 78 const char *key = key_buffer; 79 80 /* Prepend the number to the string and separate them by space. No other 81 * number can result in the same prefix, no other string in the same 82 * postfix nor can the boundary between them be ambiguous. */ 83 key_buffer = encode_number(number, key_buffer); 84 *++key_buffer = ' '; 85 memcpy(++key_buffer, string, len+1); 86 87 /* return the start of the key */ 88 return key; 89} 90 91/* Utility function to serialize string S in the given serialization CONTEXT. 92 */ 93static void 94serialize_svn_string(svn_temp_serializer__context_t *context, 95 const svn_string_t * const *s) 96{ 97 const svn_string_t *string = *s; 98 99 /* Nothing to do for NULL string references. */ 100 if (string == NULL) 101 return; 102 103 svn_temp_serializer__push(context, 104 (const void * const *)s, 105 sizeof(*string)); 106 107 /* the "string" content may actually be arbitrary binary data. 108 * Thus, we cannot use svn_temp_serializer__add_string. */ 109 svn_temp_serializer__push(context, 110 (const void * const *)&string->data, 111 string->len + 1); 112 113 /* back to the caller's nesting level */ 114 svn_temp_serializer__pop(context); 115 svn_temp_serializer__pop(context); 116} 117 118/* Utility function to deserialize the STRING inside the BUFFER. 119 */ 120static void 121deserialize_svn_string(void *buffer, svn_string_t **string) 122{ 123 svn_temp_deserializer__resolve(buffer, (void **)string); 124 if (*string == NULL) 125 return; 126 127 svn_temp_deserializer__resolve(*string, (void **)&(*string)->data); 128} 129 130/* Utility function to serialize checkum CS within the given serialization 131 * CONTEXT. 132 */ 133static void 134serialize_checksum(svn_temp_serializer__context_t *context, 135 svn_checksum_t * const *cs) 136{ 137 const svn_checksum_t *checksum = *cs; 138 if (checksum == NULL) 139 return; 140 141 svn_temp_serializer__push(context, 142 (const void * const *)cs, 143 sizeof(*checksum)); 144 145 /* The digest is arbitrary binary data. 146 * Thus, we cannot use svn_temp_serializer__add_string. */ 147 svn_temp_serializer__push(context, 148 (const void * const *)&checksum->digest, 149 svn_checksum_size(checksum)); 150 151 /* return to the caller's nesting level */ 152 svn_temp_serializer__pop(context); 153 svn_temp_serializer__pop(context); 154} 155 156/* Utility function to deserialize the checksum CS inside the BUFFER. 157 */ 158static void 159deserialize_checksum(void *buffer, svn_checksum_t **cs) 160{ 161 svn_temp_deserializer__resolve(buffer, (void **)cs); 162 if (*cs == NULL) 163 return; 164 165 svn_temp_deserializer__resolve(*cs, (void **)&(*cs)->digest); 166} 167 168/* Utility function to serialize the REPRESENTATION within the given 169 * serialization CONTEXT. 170 */ 171static void 172serialize_representation(svn_temp_serializer__context_t *context, 173 representation_t * const *representation) 174{ 175 const representation_t * rep = *representation; 176 if (rep == NULL) 177 return; 178 179 /* serialize the representation struct itself */ 180 svn_temp_serializer__push(context, 181 (const void * const *)representation, 182 sizeof(*rep)); 183 184 /* serialize sub-structures */ 185 serialize_checksum(context, &rep->md5_checksum); 186 serialize_checksum(context, &rep->sha1_checksum); 187 188 svn_temp_serializer__add_string(context, &rep->txn_id); 189 svn_temp_serializer__add_string(context, &rep->uniquifier); 190 191 /* return to the caller's nesting level */ 192 svn_temp_serializer__pop(context); 193} 194 195/* Utility function to deserialize the REPRESENTATIONS inside the BUFFER. 196 */ 197static void 198deserialize_representation(void *buffer, 199 representation_t **representation) 200{ 201 representation_t *rep; 202 203 /* fixup the reference to the representation itself */ 204 svn_temp_deserializer__resolve(buffer, (void **)representation); 205 rep = *representation; 206 if (rep == NULL) 207 return; 208 209 /* fixup of sub-structures */ 210 deserialize_checksum(rep, &rep->md5_checksum); 211 deserialize_checksum(rep, &rep->sha1_checksum); 212 213 svn_temp_deserializer__resolve(rep, (void **)&rep->txn_id); 214 svn_temp_deserializer__resolve(rep, (void **)&rep->uniquifier); 215} 216 217/* auxilliary structure representing the content of a directory hash */ 218typedef struct hash_data_t 219{ 220 /* number of entries in the directory */ 221 apr_size_t count; 222 223 /* number of unused dir entry buckets in the index */ 224 apr_size_t over_provision; 225 226 /* internal modifying operations counter 227 * (used to repack data once in a while) */ 228 apr_size_t operations; 229 230 /* size of the serialization buffer actually used. 231 * (we will allocate more than we actually need such that we may 232 * append more data in situ later) */ 233 apr_size_t len; 234 235 /* reference to the entries */ 236 svn_fs_dirent_t **entries; 237 238 /* size of the serialized entries and don't be too wasteful 239 * (needed since the entries are no longer in sequence) */ 240 apr_uint32_t *lengths; 241} hash_data_t; 242 243static int 244compare_dirent_id_names(const void *lhs, const void *rhs) 245{ 246 return strcmp((*(const svn_fs_dirent_t *const *)lhs)->name, 247 (*(const svn_fs_dirent_t *const *)rhs)->name); 248} 249 250/* Utility function to serialize the *ENTRY_P into a the given 251 * serialization CONTEXT. Return the serialized size of the 252 * dir entry in *LENGTH. 253 */ 254static void 255serialize_dir_entry(svn_temp_serializer__context_t *context, 256 svn_fs_dirent_t **entry_p, 257 apr_uint32_t *length) 258{ 259 svn_fs_dirent_t *entry = *entry_p; 260 apr_size_t initial_length = svn_temp_serializer__get_length(context); 261 262 svn_temp_serializer__push(context, 263 (const void * const *)entry_p, 264 sizeof(svn_fs_dirent_t)); 265 266 svn_fs_fs__id_serialize(context, &entry->id); 267 svn_temp_serializer__add_string(context, &entry->name); 268 269 *length = (apr_uint32_t)( svn_temp_serializer__get_length(context) 270 - APR_ALIGN_DEFAULT(initial_length)); 271 272 svn_temp_serializer__pop(context); 273} 274 275/* Utility function to serialize the ENTRIES into a new serialization 276 * context to be returned. Allocation will be made form POOL. 277 */ 278static svn_temp_serializer__context_t * 279serialize_dir(apr_hash_t *entries, apr_pool_t *pool) 280{ 281 hash_data_t hash_data; 282 apr_hash_index_t *hi; 283 apr_size_t i = 0; 284 svn_temp_serializer__context_t *context; 285 286 /* calculate sizes */ 287 apr_size_t count = apr_hash_count(entries); 288 apr_size_t over_provision = 2 + count / 4; 289 apr_size_t entries_len = (count + over_provision) * sizeof(svn_fs_dirent_t*); 290 apr_size_t lengths_len = (count + over_provision) * sizeof(apr_uint32_t); 291 292 /* copy the hash entries to an auxilliary struct of known layout */ 293 hash_data.count = count; 294 hash_data.over_provision = over_provision; 295 hash_data.operations = 0; 296 hash_data.entries = apr_palloc(pool, entries_len); 297 hash_data.lengths = apr_palloc(pool, lengths_len); 298 299 for (hi = apr_hash_first(pool, entries); hi; hi = apr_hash_next(hi), ++i) 300 hash_data.entries[i] = svn__apr_hash_index_val(hi); 301 302 /* sort entry index by ID name */ 303 qsort(hash_data.entries, 304 count, 305 sizeof(*hash_data.entries), 306 compare_dirent_id_names); 307 308 /* Serialize that aux. structure into a new one. Also, provide a good 309 * estimate for the size of the buffer that we will need. */ 310 context = svn_temp_serializer__init(&hash_data, 311 sizeof(hash_data), 312 50 + count * 200 + entries_len, 313 pool); 314 315 /* serialize entries references */ 316 svn_temp_serializer__push(context, 317 (const void * const *)&hash_data.entries, 318 entries_len); 319 320 /* serialize the individual entries and their sub-structures */ 321 for (i = 0; i < count; ++i) 322 serialize_dir_entry(context, 323 &hash_data.entries[i], 324 &hash_data.lengths[i]); 325 326 svn_temp_serializer__pop(context); 327 328 /* serialize entries references */ 329 svn_temp_serializer__push(context, 330 (const void * const *)&hash_data.lengths, 331 lengths_len); 332 333 return context; 334} 335 336/* Utility function to reconstruct a dir entries hash from serialized data 337 * in BUFFER and HASH_DATA. Allocation will be made form POOL. 338 */ 339static apr_hash_t * 340deserialize_dir(void *buffer, hash_data_t *hash_data, apr_pool_t *pool) 341{ 342 apr_hash_t *result = svn_hash__make(pool); 343 apr_size_t i; 344 apr_size_t count; 345 svn_fs_dirent_t *entry; 346 svn_fs_dirent_t **entries; 347 348 /* resolve the reference to the entries array */ 349 svn_temp_deserializer__resolve(buffer, (void **)&hash_data->entries); 350 entries = hash_data->entries; 351 352 /* fixup the references within each entry and add it to the hash */ 353 for (i = 0, count = hash_data->count; i < count; ++i) 354 { 355 svn_temp_deserializer__resolve(entries, (void **)&entries[i]); 356 entry = hash_data->entries[i]; 357 358 /* pointer fixup */ 359 svn_temp_deserializer__resolve(entry, (void **)&entry->name); 360 svn_fs_fs__id_deserialize(entry, (svn_fs_id_t **)&entry->id); 361 362 /* add the entry to the hash */ 363 svn_hash_sets(result, entry->name, entry); 364 } 365 366 /* return the now complete hash */ 367 return result; 368} 369 370void 371svn_fs_fs__noderev_serialize(svn_temp_serializer__context_t *context, 372 node_revision_t * const *noderev_p) 373{ 374 const node_revision_t *noderev = *noderev_p; 375 if (noderev == NULL) 376 return; 377 378 /* serialize the representation struct itself */ 379 svn_temp_serializer__push(context, 380 (const void * const *)noderev_p, 381 sizeof(*noderev)); 382 383 /* serialize sub-structures */ 384 svn_fs_fs__id_serialize(context, &noderev->id); 385 svn_fs_fs__id_serialize(context, &noderev->predecessor_id); 386 serialize_representation(context, &noderev->prop_rep); 387 serialize_representation(context, &noderev->data_rep); 388 389 svn_temp_serializer__add_string(context, &noderev->copyfrom_path); 390 svn_temp_serializer__add_string(context, &noderev->copyroot_path); 391 svn_temp_serializer__add_string(context, &noderev->created_path); 392 393 /* return to the caller's nesting level */ 394 svn_temp_serializer__pop(context); 395} 396 397 398void 399svn_fs_fs__noderev_deserialize(void *buffer, 400 node_revision_t **noderev_p) 401{ 402 node_revision_t *noderev; 403 404 /* fixup the reference to the representation itself, 405 * if this is part of a parent structure. */ 406 if (buffer != *noderev_p) 407 svn_temp_deserializer__resolve(buffer, (void **)noderev_p); 408 409 noderev = *noderev_p; 410 if (noderev == NULL) 411 return; 412 413 /* fixup of sub-structures */ 414 svn_fs_fs__id_deserialize(noderev, (svn_fs_id_t **)&noderev->id); 415 svn_fs_fs__id_deserialize(noderev, (svn_fs_id_t **)&noderev->predecessor_id); 416 deserialize_representation(noderev, &noderev->prop_rep); 417 deserialize_representation(noderev, &noderev->data_rep); 418 419 svn_temp_deserializer__resolve(noderev, (void **)&noderev->copyfrom_path); 420 svn_temp_deserializer__resolve(noderev, (void **)&noderev->copyroot_path); 421 svn_temp_deserializer__resolve(noderev, (void **)&noderev->created_path); 422} 423 424 425/* Utility function to serialize COUNT svn_txdelta_op_t objects 426 * at OPS in the given serialization CONTEXT. 427 */ 428static void 429serialize_txdelta_ops(svn_temp_serializer__context_t *context, 430 const svn_txdelta_op_t * const * ops, 431 apr_size_t count) 432{ 433 if (*ops == NULL) 434 return; 435 436 /* the ops form a contiguous chunk of memory with no further references */ 437 svn_temp_serializer__push(context, 438 (const void * const *)ops, 439 count * sizeof(svn_txdelta_op_t)); 440 svn_temp_serializer__pop(context); 441} 442 443/* Utility function to serialize W in the given serialization CONTEXT. 444 */ 445static void 446serialize_txdeltawindow(svn_temp_serializer__context_t *context, 447 svn_txdelta_window_t * const * w) 448{ 449 svn_txdelta_window_t *window = *w; 450 451 /* serialize the window struct itself */ 452 svn_temp_serializer__push(context, 453 (const void * const *)w, 454 sizeof(svn_txdelta_window_t)); 455 456 /* serialize its sub-structures */ 457 serialize_txdelta_ops(context, &window->ops, window->num_ops); 458 serialize_svn_string(context, &window->new_data); 459 460 svn_temp_serializer__pop(context); 461} 462 463svn_error_t * 464svn_fs_fs__serialize_txdelta_window(void **buffer, 465 apr_size_t *buffer_size, 466 void *item, 467 apr_pool_t *pool) 468{ 469 svn_fs_fs__txdelta_cached_window_t *window_info = item; 470 svn_stringbuf_t *serialized; 471 472 /* initialize the serialization process and allocate a buffer large 473 * enough to do without the need of re-allocations in most cases. */ 474 apr_size_t text_len = window_info->window->new_data 475 ? window_info->window->new_data->len 476 : 0; 477 svn_temp_serializer__context_t *context = 478 svn_temp_serializer__init(window_info, 479 sizeof(*window_info), 480 500 + text_len, 481 pool); 482 483 /* serialize the sub-structure(s) */ 484 serialize_txdeltawindow(context, &window_info->window); 485 486 /* return the serialized result */ 487 serialized = svn_temp_serializer__get(context); 488 489 *buffer = serialized->data; 490 *buffer_size = serialized->len; 491 492 return SVN_NO_ERROR; 493} 494 495svn_error_t * 496svn_fs_fs__deserialize_txdelta_window(void **item, 497 void *buffer, 498 apr_size_t buffer_size, 499 apr_pool_t *pool) 500{ 501 svn_txdelta_window_t *window; 502 503 /* Copy the _full_ buffer as it also contains the sub-structures. */ 504 svn_fs_fs__txdelta_cached_window_t *window_info = 505 (svn_fs_fs__txdelta_cached_window_t *)buffer; 506 507 /* pointer reference fixup */ 508 svn_temp_deserializer__resolve(window_info, 509 (void **)&window_info->window); 510 window = window_info->window; 511 512 svn_temp_deserializer__resolve(window, (void **)&window->ops); 513 514 deserialize_svn_string(window, (svn_string_t**)&window->new_data); 515 516 /* done */ 517 *item = window_info; 518 519 return SVN_NO_ERROR; 520} 521 522svn_error_t * 523svn_fs_fs__serialize_manifest(void **data, 524 apr_size_t *data_len, 525 void *in, 526 apr_pool_t *pool) 527{ 528 apr_array_header_t *manifest = in; 529 530 *data_len = sizeof(apr_off_t) *manifest->nelts; 531 *data = apr_palloc(pool, *data_len); 532 memcpy(*data, manifest->elts, *data_len); 533 534 return SVN_NO_ERROR; 535} 536 537svn_error_t * 538svn_fs_fs__deserialize_manifest(void **out, 539 void *data, 540 apr_size_t data_len, 541 apr_pool_t *pool) 542{ 543 apr_array_header_t *manifest = apr_array_make(pool, 1, sizeof(apr_off_t)); 544 545 manifest->nelts = (int) (data_len / sizeof(apr_off_t)); 546 manifest->nalloc = (int) (data_len / sizeof(apr_off_t)); 547 manifest->elts = (char*)data; 548 549 *out = manifest; 550 551 return SVN_NO_ERROR; 552} 553 554/* Auxilliary structure representing the content of a properties hash. 555 This structure is much easier to (de-)serialize than an apr_hash. 556 */ 557typedef struct properties_data_t 558{ 559 /* number of entries in the hash */ 560 apr_size_t count; 561 562 /* reference to the keys */ 563 const char **keys; 564 565 /* reference to the values */ 566 const svn_string_t **values; 567} properties_data_t; 568 569/* Serialize COUNT C-style strings from *STRINGS into CONTEXT. */ 570static void 571serialize_cstring_array(svn_temp_serializer__context_t *context, 572 const char ***strings, 573 apr_size_t count) 574{ 575 apr_size_t i; 576 const char **entries = *strings; 577 578 /* serialize COUNT entries pointers (the array) */ 579 svn_temp_serializer__push(context, 580 (const void * const *)strings, 581 count * sizeof(const char*)); 582 583 /* serialize array elements */ 584 for (i = 0; i < count; ++i) 585 svn_temp_serializer__add_string(context, &entries[i]); 586 587 svn_temp_serializer__pop(context); 588} 589 590/* Serialize COUNT svn_string_t* items from *STRINGS into CONTEXT. */ 591static void 592serialize_svn_string_array(svn_temp_serializer__context_t *context, 593 const svn_string_t ***strings, 594 apr_size_t count) 595{ 596 apr_size_t i; 597 const svn_string_t **entries = *strings; 598 599 /* serialize COUNT entries pointers (the array) */ 600 svn_temp_serializer__push(context, 601 (const void * const *)strings, 602 count * sizeof(const char*)); 603 604 /* serialize array elements */ 605 for (i = 0; i < count; ++i) 606 serialize_svn_string(context, &entries[i]); 607 608 svn_temp_serializer__pop(context); 609} 610 611svn_error_t * 612svn_fs_fs__serialize_properties(void **data, 613 apr_size_t *data_len, 614 void *in, 615 apr_pool_t *pool) 616{ 617 apr_hash_t *hash = in; 618 properties_data_t properties; 619 svn_temp_serializer__context_t *context; 620 apr_hash_index_t *hi; 621 svn_stringbuf_t *serialized; 622 apr_size_t i; 623 624 /* create our auxilliary data structure */ 625 properties.count = apr_hash_count(hash); 626 properties.keys = apr_palloc(pool, sizeof(const char*) * (properties.count + 1)); 627 properties.values = apr_palloc(pool, sizeof(const char*) * properties.count); 628 629 /* populate it with the hash entries */ 630 for (hi = apr_hash_first(pool, hash), i=0; hi; hi = apr_hash_next(hi), ++i) 631 { 632 properties.keys[i] = svn__apr_hash_index_key(hi); 633 properties.values[i] = svn__apr_hash_index_val(hi); 634 } 635 636 /* serialize it */ 637 context = svn_temp_serializer__init(&properties, 638 sizeof(properties), 639 properties.count * 100, 640 pool); 641 642 properties.keys[i] = ""; 643 serialize_cstring_array(context, &properties.keys, properties.count + 1); 644 serialize_svn_string_array(context, &properties.values, properties.count); 645 646 /* return the serialized result */ 647 serialized = svn_temp_serializer__get(context); 648 649 *data = serialized->data; 650 *data_len = serialized->len; 651 652 return SVN_NO_ERROR; 653} 654 655svn_error_t * 656svn_fs_fs__deserialize_properties(void **out, 657 void *data, 658 apr_size_t data_len, 659 apr_pool_t *pool) 660{ 661 apr_hash_t *hash = svn_hash__make(pool); 662 properties_data_t *properties = (properties_data_t *)data; 663 size_t i; 664 665 /* de-serialize our auxilliary data structure */ 666 svn_temp_deserializer__resolve(properties, (void**)&properties->keys); 667 svn_temp_deserializer__resolve(properties, (void**)&properties->values); 668 669 /* de-serialize each entry and put it into the hash */ 670 for (i = 0; i < properties->count; ++i) 671 { 672 apr_size_t len = properties->keys[i+1] - properties->keys[i] - 1; 673 svn_temp_deserializer__resolve((void*)properties->keys, 674 (void**)&properties->keys[i]); 675 676 deserialize_svn_string((void*)properties->values, 677 (svn_string_t **)&properties->values[i]); 678 679 apr_hash_set(hash, 680 properties->keys[i], len, 681 properties->values[i]); 682 } 683 684 /* done */ 685 *out = hash; 686 687 return SVN_NO_ERROR; 688} 689 690svn_error_t * 691svn_fs_fs__serialize_id(void **data, 692 apr_size_t *data_len, 693 void *in, 694 apr_pool_t *pool) 695{ 696 const svn_fs_id_t *id = in; 697 svn_stringbuf_t *serialized; 698 699 /* create an (empty) serialization context with plenty of buffer space */ 700 svn_temp_serializer__context_t *context = 701 svn_temp_serializer__init(NULL, 0, 250, pool); 702 703 /* serialize the id */ 704 svn_fs_fs__id_serialize(context, &id); 705 706 /* return serialized data */ 707 serialized = svn_temp_serializer__get(context); 708 *data = serialized->data; 709 *data_len = serialized->len; 710 711 return SVN_NO_ERROR; 712} 713 714svn_error_t * 715svn_fs_fs__deserialize_id(void **out, 716 void *data, 717 apr_size_t data_len, 718 apr_pool_t *pool) 719{ 720 /* Copy the _full_ buffer as it also contains the sub-structures. */ 721 svn_fs_id_t *id = (svn_fs_id_t *)data; 722 723 /* fixup of all pointers etc. */ 724 svn_fs_fs__id_deserialize(id, &id); 725 726 /* done */ 727 *out = id; 728 return SVN_NO_ERROR; 729} 730 731/** Caching node_revision_t objects. **/ 732 733svn_error_t * 734svn_fs_fs__serialize_node_revision(void **buffer, 735 apr_size_t *buffer_size, 736 void *item, 737 apr_pool_t *pool) 738{ 739 svn_stringbuf_t *serialized; 740 node_revision_t *noderev = item; 741 742 /* create an (empty) serialization context with plenty of (initial) 743 * buffer space. */ 744 svn_temp_serializer__context_t *context = 745 svn_temp_serializer__init(NULL, 0, 746 1024 - SVN_TEMP_SERIALIZER__OVERHEAD, 747 pool); 748 749 /* serialize the noderev */ 750 svn_fs_fs__noderev_serialize(context, &noderev); 751 752 /* return serialized data */ 753 serialized = svn_temp_serializer__get(context); 754 *buffer = serialized->data; 755 *buffer_size = serialized->len; 756 757 return SVN_NO_ERROR; 758} 759 760svn_error_t * 761svn_fs_fs__deserialize_node_revision(void **item, 762 void *buffer, 763 apr_size_t buffer_size, 764 apr_pool_t *pool) 765{ 766 /* Copy the _full_ buffer as it also contains the sub-structures. */ 767 node_revision_t *noderev = (node_revision_t *)buffer; 768 769 /* fixup of all pointers etc. */ 770 svn_fs_fs__noderev_deserialize(noderev, &noderev); 771 772 /* done */ 773 *item = noderev; 774 return SVN_NO_ERROR; 775} 776 777/* Utility function that returns the directory serialized inside CONTEXT 778 * to DATA and DATA_LEN. */ 779static svn_error_t * 780return_serialized_dir_context(svn_temp_serializer__context_t *context, 781 void **data, 782 apr_size_t *data_len) 783{ 784 svn_stringbuf_t *serialized = svn_temp_serializer__get(context); 785 786 *data = serialized->data; 787 *data_len = serialized->blocksize; 788 ((hash_data_t *)serialized->data)->len = serialized->len; 789 790 return SVN_NO_ERROR; 791} 792 793svn_error_t * 794svn_fs_fs__serialize_dir_entries(void **data, 795 apr_size_t *data_len, 796 void *in, 797 apr_pool_t *pool) 798{ 799 apr_hash_t *dir = in; 800 801 /* serialize the dir content into a new serialization context 802 * and return the serialized data */ 803 return return_serialized_dir_context(serialize_dir(dir, pool), 804 data, 805 data_len); 806} 807 808svn_error_t * 809svn_fs_fs__deserialize_dir_entries(void **out, 810 void *data, 811 apr_size_t data_len, 812 apr_pool_t *pool) 813{ 814 /* Copy the _full_ buffer as it also contains the sub-structures. */ 815 hash_data_t *hash_data = (hash_data_t *)data; 816 817 /* reconstruct the hash from the serialized data */ 818 *out = deserialize_dir(hash_data, hash_data, pool); 819 820 return SVN_NO_ERROR; 821} 822 823svn_error_t * 824svn_fs_fs__get_sharded_offset(void **out, 825 const void *data, 826 apr_size_t data_len, 827 void *baton, 828 apr_pool_t *pool) 829{ 830 const apr_off_t *manifest = data; 831 apr_int64_t shard_pos = *(apr_int64_t *)baton; 832 833 *(apr_off_t *)out = manifest[shard_pos]; 834 835 return SVN_NO_ERROR; 836} 837 838/* Utility function that returns the lowest index of the first entry in 839 * *ENTRIES that points to a dir entry with a name equal or larger than NAME. 840 * If an exact match has been found, *FOUND will be set to TRUE. COUNT is 841 * the number of valid entries in ENTRIES. 842 */ 843static apr_size_t 844find_entry(svn_fs_dirent_t **entries, 845 const char *name, 846 apr_size_t count, 847 svn_boolean_t *found) 848{ 849 /* binary search for the desired entry by name */ 850 apr_size_t lower = 0; 851 apr_size_t upper = count; 852 apr_size_t middle; 853 854 for (middle = upper / 2; lower < upper; middle = (upper + lower) / 2) 855 { 856 const svn_fs_dirent_t *entry = 857 svn_temp_deserializer__ptr(entries, (const void *const *)&entries[middle]); 858 const char* entry_name = 859 svn_temp_deserializer__ptr(entry, (const void *const *)&entry->name); 860 861 int diff = strcmp(entry_name, name); 862 if (diff < 0) 863 lower = middle + 1; 864 else 865 upper = middle; 866 } 867 868 /* check whether we actually found a match */ 869 *found = FALSE; 870 if (lower < count) 871 { 872 const svn_fs_dirent_t *entry = 873 svn_temp_deserializer__ptr(entries, (const void *const *)&entries[lower]); 874 const char* entry_name = 875 svn_temp_deserializer__ptr(entry, (const void *const *)&entry->name); 876 877 if (strcmp(entry_name, name) == 0) 878 *found = TRUE; 879 } 880 881 return lower; 882} 883 884svn_error_t * 885svn_fs_fs__extract_dir_entry(void **out, 886 const void *data, 887 apr_size_t data_len, 888 void *baton, 889 apr_pool_t *pool) 890{ 891 const hash_data_t *hash_data = data; 892 const char* name = baton; 893 svn_boolean_t found; 894 895 /* resolve the reference to the entries array */ 896 const svn_fs_dirent_t * const *entries = 897 svn_temp_deserializer__ptr(data, (const void *const *)&hash_data->entries); 898 899 /* resolve the reference to the lengths array */ 900 const apr_uint32_t *lengths = 901 svn_temp_deserializer__ptr(data, (const void *const *)&hash_data->lengths); 902 903 /* binary search for the desired entry by name */ 904 apr_size_t pos = find_entry((svn_fs_dirent_t **)entries, 905 name, 906 hash_data->count, 907 &found); 908 909 /* de-serialize that entry or return NULL, if no match has been found */ 910 *out = NULL; 911 if (found) 912 { 913 const svn_fs_dirent_t *source = 914 svn_temp_deserializer__ptr(entries, (const void *const *)&entries[pos]); 915 916 /* Entries have been serialized one-by-one, each time including all 917 * nested structures and strings. Therefore, they occupy a single 918 * block of memory whose end-offset is either the beginning of the 919 * next entry or the end of the buffer 920 */ 921 apr_size_t size = lengths[pos]; 922 923 /* copy & deserialize the entry */ 924 svn_fs_dirent_t *new_entry = apr_palloc(pool, size); 925 memcpy(new_entry, source, size); 926 927 svn_temp_deserializer__resolve(new_entry, (void **)&new_entry->name); 928 svn_fs_fs__id_deserialize(new_entry, (svn_fs_id_t **)&new_entry->id); 929 *(svn_fs_dirent_t **)out = new_entry; 930 } 931 932 return SVN_NO_ERROR; 933} 934 935/* Utility function for svn_fs_fs__replace_dir_entry that implements the 936 * modification as a simply deserialize / modify / serialize sequence. 937 */ 938static svn_error_t * 939slowly_replace_dir_entry(void **data, 940 apr_size_t *data_len, 941 void *baton, 942 apr_pool_t *pool) 943{ 944 replace_baton_t *replace_baton = (replace_baton_t *)baton; 945 hash_data_t *hash_data = (hash_data_t *)*data; 946 apr_hash_t *dir; 947 948 SVN_ERR(svn_fs_fs__deserialize_dir_entries((void **)&dir, 949 *data, 950 hash_data->len, 951 pool)); 952 svn_hash_sets(dir, replace_baton->name, replace_baton->new_entry); 953 954 return svn_fs_fs__serialize_dir_entries(data, data_len, dir, pool); 955} 956 957svn_error_t * 958svn_fs_fs__replace_dir_entry(void **data, 959 apr_size_t *data_len, 960 void *baton, 961 apr_pool_t *pool) 962{ 963 replace_baton_t *replace_baton = (replace_baton_t *)baton; 964 hash_data_t *hash_data = (hash_data_t *)*data; 965 svn_boolean_t found; 966 svn_fs_dirent_t **entries; 967 apr_uint32_t *lengths; 968 apr_uint32_t length; 969 apr_size_t pos; 970 971 svn_temp_serializer__context_t *context; 972 973 /* after quite a number of operations, let's re-pack everything. 974 * This is to limit the number of vasted space as we cannot overwrite 975 * existing data but must always append. */ 976 if (hash_data->operations > 2 + hash_data->count / 4) 977 return slowly_replace_dir_entry(data, data_len, baton, pool); 978 979 /* resolve the reference to the entries array */ 980 entries = (svn_fs_dirent_t **) 981 svn_temp_deserializer__ptr((const char *)hash_data, 982 (const void *const *)&hash_data->entries); 983 984 /* resolve the reference to the lengths array */ 985 lengths = (apr_uint32_t *) 986 svn_temp_deserializer__ptr((const char *)hash_data, 987 (const void *const *)&hash_data->lengths); 988 989 /* binary search for the desired entry by name */ 990 pos = find_entry(entries, replace_baton->name, hash_data->count, &found); 991 992 /* handle entry removal (if found at all) */ 993 if (replace_baton->new_entry == NULL) 994 { 995 if (found) 996 { 997 /* remove reference to the entry from the index */ 998 memmove(&entries[pos], 999 &entries[pos + 1], 1000 sizeof(entries[pos]) * (hash_data->count - pos)); 1001 memmove(&lengths[pos], 1002 &lengths[pos + 1], 1003 sizeof(lengths[pos]) * (hash_data->count - pos)); 1004 1005 hash_data->count--; 1006 hash_data->over_provision++; 1007 hash_data->operations++; 1008 } 1009 1010 return SVN_NO_ERROR; 1011 } 1012 1013 /* if not found, prepare to insert the new entry */ 1014 if (!found) 1015 { 1016 /* fallback to slow operation if there is no place left to insert an 1017 * new entry to index. That will automatically give add some spare 1018 * entries ("overprovision"). */ 1019 if (hash_data->over_provision == 0) 1020 return slowly_replace_dir_entry(data, data_len, baton, pool); 1021 1022 /* make entries[index] available for pointing to the new entry */ 1023 memmove(&entries[pos + 1], 1024 &entries[pos], 1025 sizeof(entries[pos]) * (hash_data->count - pos)); 1026 memmove(&lengths[pos + 1], 1027 &lengths[pos], 1028 sizeof(lengths[pos]) * (hash_data->count - pos)); 1029 1030 hash_data->count++; 1031 hash_data->over_provision--; 1032 hash_data->operations++; 1033 } 1034 1035 /* de-serialize the new entry */ 1036 entries[pos] = replace_baton->new_entry; 1037 context = svn_temp_serializer__init_append(hash_data, 1038 entries, 1039 hash_data->len, 1040 *data_len, 1041 pool); 1042 serialize_dir_entry(context, &entries[pos], &length); 1043 1044 /* return the updated serialized data */ 1045 SVN_ERR (return_serialized_dir_context(context, 1046 data, 1047 data_len)); 1048 1049 /* since the previous call may have re-allocated the buffer, the lengths 1050 * pointer may no longer point to the entry in that buffer. Therefore, 1051 * re-map it again and store the length value after that. */ 1052 1053 hash_data = (hash_data_t *)*data; 1054 lengths = (apr_uint32_t *) 1055 svn_temp_deserializer__ptr((const char *)hash_data, 1056 (const void *const *)&hash_data->lengths); 1057 lengths[pos] = length; 1058 1059 return SVN_NO_ERROR; 1060} 1061 1062/* Utility function to serialize change CHANGE_P in the given serialization 1063 * CONTEXT. 1064 */ 1065static void 1066serialize_change(svn_temp_serializer__context_t *context, 1067 change_t * const *change_p) 1068{ 1069 const change_t * change = *change_p; 1070 if (change == NULL) 1071 return; 1072 1073 /* serialize the change struct itself */ 1074 svn_temp_serializer__push(context, 1075 (const void * const *)change_p, 1076 sizeof(*change)); 1077 1078 /* serialize sub-structures */ 1079 svn_fs_fs__id_serialize(context, &change->noderev_id); 1080 1081 svn_temp_serializer__add_string(context, &change->path); 1082 svn_temp_serializer__add_string(context, &change->copyfrom_path); 1083 1084 /* return to the caller's nesting level */ 1085 svn_temp_serializer__pop(context); 1086} 1087 1088/* Utility function to serialize the CHANGE_P within the given 1089 * serialization CONTEXT. 1090 */ 1091static void 1092deserialize_change(void *buffer, change_t **change_p) 1093{ 1094 change_t * change; 1095 1096 /* fix-up of the pointer to the struct in question */ 1097 svn_temp_deserializer__resolve(buffer, (void **)change_p); 1098 1099 change = *change_p; 1100 if (change == NULL) 1101 return; 1102 1103 /* fix-up of sub-structures */ 1104 svn_fs_fs__id_deserialize(change, (svn_fs_id_t **)&change->noderev_id); 1105 1106 svn_temp_deserializer__resolve(change, (void **)&change->path); 1107 svn_temp_deserializer__resolve(change, (void **)&change->copyfrom_path); 1108} 1109 1110/* Auxiliary structure representing the content of a change_t array. 1111 This structure is much easier to (de-)serialize than an APR array. 1112 */ 1113typedef struct changes_data_t 1114{ 1115 /* number of entries in the array */ 1116 int count; 1117 1118 /* reference to the changes */ 1119 change_t **changes; 1120} changes_data_t; 1121 1122svn_error_t * 1123svn_fs_fs__serialize_changes(void **data, 1124 apr_size_t *data_len, 1125 void *in, 1126 apr_pool_t *pool) 1127{ 1128 apr_array_header_t *array = in; 1129 changes_data_t changes; 1130 svn_temp_serializer__context_t *context; 1131 svn_stringbuf_t *serialized; 1132 int i; 1133 1134 /* initialize our auxiliary data structure */ 1135 changes.count = array->nelts; 1136 changes.changes = apr_palloc(pool, sizeof(change_t*) * changes.count); 1137 1138 /* populate it with the array elements */ 1139 for (i = 0; i < changes.count; ++i) 1140 changes.changes[i] = APR_ARRAY_IDX(array, i, change_t*); 1141 1142 /* serialize it and all its elements */ 1143 context = svn_temp_serializer__init(&changes, 1144 sizeof(changes), 1145 changes.count * 100, 1146 pool); 1147 1148 svn_temp_serializer__push(context, 1149 (const void * const *)&changes.changes, 1150 changes.count * sizeof(change_t*)); 1151 1152 for (i = 0; i < changes.count; ++i) 1153 serialize_change(context, &changes.changes[i]); 1154 1155 svn_temp_serializer__pop(context); 1156 1157 /* return the serialized result */ 1158 serialized = svn_temp_serializer__get(context); 1159 1160 *data = serialized->data; 1161 *data_len = serialized->len; 1162 1163 return SVN_NO_ERROR; 1164} 1165 1166svn_error_t * 1167svn_fs_fs__deserialize_changes(void **out, 1168 void *data, 1169 apr_size_t data_len, 1170 apr_pool_t *pool) 1171{ 1172 int i; 1173 changes_data_t *changes = (changes_data_t *)data; 1174 apr_array_header_t *array = apr_array_make(pool, changes->count, 1175 sizeof(change_t *)); 1176 1177 /* de-serialize our auxiliary data structure */ 1178 svn_temp_deserializer__resolve(changes, (void**)&changes->changes); 1179 1180 /* de-serialize each entry and add it to the array */ 1181 for (i = 0; i < changes->count; ++i) 1182 { 1183 deserialize_change((void*)changes->changes, 1184 (change_t **)&changes->changes[i]); 1185 APR_ARRAY_PUSH(array, change_t *) = changes->changes[i]; 1186 } 1187 1188 /* done */ 1189 *out = array; 1190 1191 return SVN_NO_ERROR; 1192} 1193 1194/* Auxiliary structure representing the content of a svn_mergeinfo_t hash. 1195 This structure is much easier to (de-)serialize than an APR array. 1196 */ 1197typedef struct mergeinfo_data_t 1198{ 1199 /* number of paths in the hash */ 1200 unsigned count; 1201 1202 /* COUNT keys (paths) */ 1203 const char **keys; 1204 1205 /* COUNT keys lengths (strlen of path) */ 1206 apr_ssize_t *key_lengths; 1207 1208 /* COUNT entries, each giving the number of ranges for the key */ 1209 int *range_counts; 1210 1211 /* all ranges in a single, concatenated buffer */ 1212 svn_merge_range_t *ranges; 1213} mergeinfo_data_t; 1214 1215svn_error_t * 1216svn_fs_fs__serialize_mergeinfo(void **data, 1217 apr_size_t *data_len, 1218 void *in, 1219 apr_pool_t *pool) 1220{ 1221 svn_mergeinfo_t mergeinfo = in; 1222 mergeinfo_data_t merges; 1223 svn_temp_serializer__context_t *context; 1224 svn_stringbuf_t *serialized; 1225 apr_hash_index_t *hi; 1226 unsigned i; 1227 int k; 1228 apr_size_t range_count; 1229 1230 /* initialize our auxiliary data structure */ 1231 merges.count = apr_hash_count(mergeinfo); 1232 merges.keys = apr_palloc(pool, sizeof(*merges.keys) * merges.count); 1233 merges.key_lengths = apr_palloc(pool, sizeof(*merges.key_lengths) * 1234 merges.count); 1235 merges.range_counts = apr_palloc(pool, sizeof(*merges.range_counts) * 1236 merges.count); 1237 1238 i = 0; 1239 range_count = 0; 1240 for (hi = apr_hash_first(pool, mergeinfo); hi; hi = apr_hash_next(hi), ++i) 1241 { 1242 svn_rangelist_t *ranges; 1243 apr_hash_this(hi, (const void**)&merges.keys[i], 1244 &merges.key_lengths[i], 1245 (void **)&ranges); 1246 merges.range_counts[i] = ranges->nelts; 1247 range_count += ranges->nelts; 1248 } 1249 1250 merges.ranges = apr_palloc(pool, sizeof(*merges.ranges) * range_count); 1251 1252 i = 0; 1253 for (hi = apr_hash_first(pool, mergeinfo); hi; hi = apr_hash_next(hi)) 1254 { 1255 svn_rangelist_t *ranges = svn__apr_hash_index_val(hi); 1256 for (k = 0; k < ranges->nelts; ++k, ++i) 1257 merges.ranges[i] = *APR_ARRAY_IDX(ranges, k, svn_merge_range_t*); 1258 } 1259 1260 /* serialize it and all its elements */ 1261 context = svn_temp_serializer__init(&merges, 1262 sizeof(merges), 1263 range_count * 30, 1264 pool); 1265 1266 /* keys array */ 1267 svn_temp_serializer__push(context, 1268 (const void * const *)&merges.keys, 1269 merges.count * sizeof(*merges.keys)); 1270 1271 for (i = 0; i < merges.count; ++i) 1272 svn_temp_serializer__add_string(context, &merges.keys[i]); 1273 1274 svn_temp_serializer__pop(context); 1275 1276 /* key lengths array */ 1277 svn_temp_serializer__push(context, 1278 (const void * const *)&merges.key_lengths, 1279 merges.count * sizeof(*merges.key_lengths)); 1280 svn_temp_serializer__pop(context); 1281 1282 /* range counts array */ 1283 svn_temp_serializer__push(context, 1284 (const void * const *)&merges.range_counts, 1285 merges.count * sizeof(*merges.range_counts)); 1286 svn_temp_serializer__pop(context); 1287 1288 /* ranges */ 1289 svn_temp_serializer__push(context, 1290 (const void * const *)&merges.ranges, 1291 range_count * sizeof(*merges.ranges)); 1292 svn_temp_serializer__pop(context); 1293 1294 /* return the serialized result */ 1295 serialized = svn_temp_serializer__get(context); 1296 1297 *data = serialized->data; 1298 *data_len = serialized->len; 1299 1300 return SVN_NO_ERROR; 1301} 1302 1303svn_error_t * 1304svn_fs_fs__deserialize_mergeinfo(void **out, 1305 void *data, 1306 apr_size_t data_len, 1307 apr_pool_t *pool) 1308{ 1309 unsigned i; 1310 int k, n; 1311 mergeinfo_data_t *merges = (mergeinfo_data_t *)data; 1312 svn_mergeinfo_t mergeinfo; 1313 1314 /* de-serialize our auxiliary data structure */ 1315 svn_temp_deserializer__resolve(merges, (void**)&merges->keys); 1316 svn_temp_deserializer__resolve(merges, (void**)&merges->key_lengths); 1317 svn_temp_deserializer__resolve(merges, (void**)&merges->range_counts); 1318 svn_temp_deserializer__resolve(merges, (void**)&merges->ranges); 1319 1320 /* de-serialize keys and add entries to the result */ 1321 n = 0; 1322 mergeinfo = svn_hash__make(pool); 1323 for (i = 0; i < merges->count; ++i) 1324 { 1325 svn_rangelist_t *ranges = apr_array_make(pool, 1326 merges->range_counts[i], 1327 sizeof(svn_merge_range_t*)); 1328 for (k = 0; k < merges->range_counts[i]; ++k, ++n) 1329 APR_ARRAY_PUSH(ranges, svn_merge_range_t*) = &merges->ranges[n]; 1330 1331 svn_temp_deserializer__resolve((void*)merges->keys, 1332 (void**)&merges->keys[i]); 1333 apr_hash_set(mergeinfo, merges->keys[i], merges->key_lengths[i], ranges); 1334 } 1335 1336 /* done */ 1337 *out = mergeinfo; 1338 1339 return SVN_NO_ERROR; 1340} 1341 1342