contrib/subversion/subversion/libsvn_fs_x/temp_serializer.c

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