contrib/subversion/subversion/libsvn_fs_fs/temp_serializer.c

   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  */
  44 static char*
  45 encode_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
  68 const char*
  69 svn_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  */
  93 static void
  94 serialize_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  */
 120 static void
 121 deserialize_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  */
 133 static void
 134 serialize_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  */
 158 static void
 159 deserialize_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  */
 171 static void
 172 serialize_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  */
 197 static void
 198 deserialize_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 */
 218 typedef 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
 243 static int
 244 compare_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  */
 254 static void
 255 serialize_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  */
 278 static svn_temp_serializer__context_t *
 279 serialize_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  */
 339 static apr_hash_t *
 340 deserialize_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
 370 void
 371 svn_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
 398 void
 399 svn_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  */
 428 static void
 429 serialize_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  */
 445 static void
 446 serialize_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
 463 svn_error_t *
 464 svn_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
 495 svn_error_t *
 496 svn_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
 522 svn_error_t *
 523 svn_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
 537 svn_error_t *
 538 svn_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  */
 557 typedef 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. */
 570 static void
 571 serialize_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. */
 591 static void
 592 serialize_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
 611 svn_error_t *
 612 svn_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
 655 svn_error_t *
 656 svn_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
 690 svn_error_t *
 691 svn_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
 714 svn_error_t *
 715 svn_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
 733 svn_error_t *
 734 svn_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
 760 svn_error_t *
 761 svn_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. */
 779 static svn_error_t *
 780 return_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
 793 svn_error_t *
 794 svn_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
 808 svn_error_t *
 809 svn_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
 823 svn_error_t *
 824 svn_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  */
 843 static apr_size_t
 844 find_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
 884 svn_error_t *
 885 svn_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  */
 938 static svn_error_t *
 939 slowly_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
 957 svn_error_t *
 958 svn_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  */
1065 static void
1066 serialize_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  */
1091 static void
1092 deserialize_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  */
1113 typedef 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
1122 svn_error_t *
1123 svn_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
1166 svn_error_t *
1167 svn_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  */
1197 typedef 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
1215 svn_error_t *
1216 svn_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
1303 svn_error_t *
1304 svn_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