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