contrib/subversion/subversion/libsvn_subr/temp_serializer.c

   1 /*
   2  * svn_temp_serializer.c: implement the tempoary structure serialization API
   3  *
   4  * ====================================================================
   5  *    Licensed to the Apache Software Foundation (ASF) under one
   6  *    or more contributor license agreements.  See the NOTICE file
   7  *    distributed with this work for additional information
   8  *    regarding copyright ownership.  The ASF licenses this file
   9  *    to you under the Apache License, Version 2.0 (the
  10  *    "License"); you may not use this file except in compliance
  11  *    with the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  *    Unless required by applicable law or agreed to in writing,
  16  *    software distributed under the License is distributed on an
  17  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  18  *    KIND, either express or implied.  See the License for the
  19  *    specific language governing permissions and limitations
  20  *    under the License.
  21  * ====================================================================
  22  */
  23
  24 #include <assert.h>
  25 #include "private/svn_temp_serializer.h"
  26 #include "svn_string.h"
  27
  28 /* This is a very efficient serialization and especially efficient
  29  * deserialization framework. The idea is just to concatenate all sub-
  30  * structures and strings into a single buffer while preserving proper
  31  * member alignment. Pointers will be replaced by the respective data
  32  * offsets in the buffer when that target that it pointed to gets
  33  * serialized, i.e. appended to the data buffer written so far.
  34  *
  35  * Hence, deserialization can be simply done by copying the buffer and
  36  * adjusting the pointers. No fine-grained allocation and copying is
  37  * necessary.
  38  */
  39
  40 /* An element in the structure stack. It contains a pointer to the source
  41  * structure so that the relative offset of sub-structure or string
  42  * references can be determined properly. It also contains the corresponding
  43  * position within the serialized data. Thus, pointers can be serialized
  44  * as offsets within the target buffer.
  45  */
  46 typedef struct source_stack_t
  47 {
  48   /* the source structure passed in to *_init or *_push */
  49   const void *source_struct;
  50
  51   /* offset within the target buffer to where the structure got copied */
  52   apr_size_t target_offset;
  53
  54   /* parent stack entry. Will be NULL for the root entry.
  55    * Items in the svn_temp_serializer__context_t recycler will use this
  56    * to link to the next unused item. */
  57   struct source_stack_t *upper;
  58 } source_stack_t;
  59
  60 /* Serialization context info. It basically consists of the buffer holding
  61  * the serialized result and the stack of source structure information.
  62  */
  63 struct svn_temp_serializer__context_t
  64 {
  65   /* allocations are made from this pool */
  66   apr_pool_t *pool;
  67
  68   /* the buffer holding all serialized data */
  69   svn_stringbuf_t *buffer;
  70
  71   /* the stack of structures being serialized. If NULL, the serialization
  72    * process has been finished. However, it is not necessarily NULL when
  73    * the application end serialization. */
  74   source_stack_t *source;
  75
  76   /* unused stack elements will be put here for later reuse. */
  77   source_stack_t *recycler;
  78 };
  79
  80 /* Make sure the serialized data len is a multiple of the default alignment,
  81  * i.e. structures may be appended without violating member alignment
  82  * guarantees.
  83  */
  84 static void
  85 align_buffer_end(svn_temp_serializer__context_t *context)
  86 {
  87   apr_size_t current_len = context->buffer->len;
  88   apr_size_t aligned_len = APR_ALIGN_DEFAULT(current_len);
  89
  90   if (aligned_len + 1 > context->buffer->blocksize)
  91     svn_stringbuf_ensure(context->buffer, aligned_len);
  92
  93    context->buffer->len = aligned_len;
  94 }
  95
  96 /* Begin the serialization process for the SOURCE_STRUCT and all objects
  97  * referenced from it. STRUCT_SIZE must match the result of sizeof() of
  98  * the actual structure. You may suggest a larger initial buffer size
  99  * in SUGGESTED_BUFFER_SIZE to minimize the number of internal buffer
 100  * re-allocations during the serialization process. All allocations will
 101  * be made from POOL.
 102  */
 103 svn_temp_serializer__context_t *
 104 svn_temp_serializer__init(const void *source_struct,
 105                           apr_size_t struct_size,
 106                           apr_size_t suggested_buffer_size,
 107                           apr_pool_t *pool)
 108 {
 109   /* select a meaningful initial memory buffer capacity */
 110   apr_size_t init_size = suggested_buffer_size < struct_size
 111                        ? struct_size
 112                        : suggested_buffer_size;
 113
 114   /* create the serialization context and initialize it */
 115   svn_temp_serializer__context_t *context = apr_palloc(pool, sizeof(*context));
 116   context->pool = pool;
 117   context->buffer = svn_stringbuf_create_ensure(init_size, pool);
 118   context->recycler = NULL;
 119
 120   /* If a source struct has been given, make it the root struct. */
 121   if (source_struct)
 122     {
 123       context->source = apr_palloc(pool, sizeof(*context->source));
 124       context->source->source_struct = source_struct;
 125       context->source->target_offset = 0;
 126       context->source->upper = NULL;
 127
 128       /* serialize, i.e. append, the content of the first structure */
 129       svn_stringbuf_appendbytes(context->buffer, source_struct, struct_size);
 130     }
 131     else
 132     {
 133       /* The root struct will be set with the first push() op, or not at all
 134        * (in case of a plain string). */
 135       context->source = NULL;
 136     }
 137
 138   /* done */
 139   return context;
 140 }
 141
 142 /* Continue the serialization process of the SOURCE_STRUCT that has already
 143  * been serialized to BUFFER but contains references to new objects yet to
 144  * serialize. The current size of the serialized data is given in
 145  * CURRENTLY_USED. If the allocated data buffer is actually larger, you may
 146  * specifiy that in CURRENTLY_ALLOCATED to prevent unnecessary allocations.
 147  * Otherwise, set it to 0. All allocations will be made from POOl.
 148  */
 149 svn_temp_serializer__context_t *
 150 svn_temp_serializer__init_append(void *buffer,
 151                                  void *source_struct,
 152                                  apr_size_t currently_used,
 153                                  apr_size_t currently_allocated,
 154                                  apr_pool_t *pool)
 155 {
 156   /* determine the current memory buffer capacity */
 157   apr_size_t init_size = currently_allocated < currently_used
 158                        ? currently_used
 159                        : currently_allocated;
 160
 161   /* create the serialization context and initialize it */
 162   svn_temp_serializer__context_t *context = apr_palloc(pool, sizeof(*context));
 163   context->pool = pool;
 164
 165   /* use BUFFER as serialization target */
 166   context->buffer = svn_stringbuf_create_ensure(0, pool);
 167   context->buffer->data = buffer;
 168   context->buffer->len = currently_used;
 169   context->buffer->blocksize = init_size;
 170
 171   /* SOURCE_STRUCT is our serialization root */
 172   context->source = apr_palloc(pool, sizeof(*context->source));
 173   context->source->source_struct = source_struct;
 174   context->source->target_offset = (char *)source_struct - (char *)buffer;
 175   context->source->upper = NULL;
 176
 177   /* initialize the RECYCLER */
 178   context->recycler = NULL;
 179
 180   /* done */
 181   return context;
 182 }
 183
 184 /* Utility function replacing the serialized pointer corresponding to
 185  * *SOURCE_POINTER with the offset that it will be put when being append
 186  * right after this function call.
 187  */
 188 static void
 189 store_current_end_pointer(svn_temp_serializer__context_t *context,
 190                           const void * const * source_pointer)
 191 {
 192   apr_size_t ptr_offset;
 193   apr_size_t *target_ptr;
 194
 195   /* if *source_pointer is the root struct, there will be no parent structure
 196    * to relate it to */
 197   if (context->source == NULL)
 198     return;
 199
 200   /* position of the serialized pointer relative to the begin of the buffer */
 201   ptr_offset = (const char *)source_pointer
 202              - (const char *)context->source->source_struct
 203              + context->source->target_offset;
 204
 205   /* the offset must be within the serialized data. Otherwise, you forgot
 206    * to serialize the respective sub-struct. */
 207   assert(context->buffer->len > ptr_offset);
 208
 209   /* use the serialized pointer as a storage for the offset */
 210   target_ptr = (apr_size_t*)(context->buffer->data + ptr_offset);
 211
 212   /* store the current buffer length because that's where we will append
 213    * the serialized data of the sub-struct or string */
 214   *target_ptr = *source_pointer == NULL
 215               ? 0
 216               : context->buffer->len - context->source->target_offset;
 217 }
 218
 219 /* Begin serialization of a referenced sub-structure within the
 220  * serialization CONTEXT. SOURCE_STRUCT must be a reference to the pointer
 221  * in the original parent structure so that the correspondence in the
 222  * serialized structure can be established. STRUCT_SIZE must match the
 223  * result of sizeof() of the actual structure.
 224  */
 225 void
 226 svn_temp_serializer__push(svn_temp_serializer__context_t *context,
 227                           const void * const * source_struct,
 228                           apr_size_t struct_size)
 229 {
 230   const void *source = *source_struct;
 231   source_stack_t *new;
 232
 233   /* recycle an old entry or create a new one for the structure stack */
 234   if (context->recycler)
 235     {
 236       new = context->recycler;
 237       context->recycler = new->upper;
 238     }
 239   else
 240     new = apr_palloc(context->pool, sizeof(*new));
 241
 242   /* the serialized structure must be properly aligned */
 243   if (source)
 244     align_buffer_end(context);
 245
 246   /* Store the offset at which the struct data that will the appended.
 247    * Write 0 for NULL pointers. */
 248   store_current_end_pointer(context, source_struct);
 249
 250   /* store source and target information */
 251   new->source_struct = source;
 252   new->target_offset = context->buffer->len;
 253
 254   /* put the new entry onto the stack*/
 255   new->upper = context->source;
 256   context->source = new;
 257
 258   /* finally, actually append the new struct
 259    * (so we can now manipulate pointers within it) */
 260   if (*source_struct)
 261     svn_stringbuf_appendbytes(context->buffer, source, struct_size);
 262 }
 263
 264 /* Remove the lastest structure from the stack.
 265  */
 266 void
 267 svn_temp_serializer__pop(svn_temp_serializer__context_t *context)
 268 {
 269   source_stack_t *old = context->source;
 270
 271   /* we may pop the original struct but not further */
 272   assert(context->source);
 273
 274   /* one level up the structure stack */
 275   context->source = context->source->upper;
 276
 277   /* put the old stack element into the recycler for later reuse */
 278   old->upper = context->recycler;
 279   context->recycler = old;
 280 }
 281
 282 /* Serialize a string referenced from the current structure within the
 283  * serialization CONTEXT. S must be a reference to the char* pointer in
 284  * the original structure so that the correspondence in the serialized
 285  * structure can be established.
 286  */
 287 void
 288 svn_temp_serializer__add_string(svn_temp_serializer__context_t *context,
 289                                 const char * const * s)
 290 {
 291   const char *string = *s;
 292
 293   /* Store the offset at which the string data that will the appended.
 294    * Write 0 for NULL pointers. Strings don't need special alignment. */
 295   store_current_end_pointer(context, (const void **)s);
 296
 297   /* append the string data */
 298   if (string)
 299     svn_stringbuf_appendbytes(context->buffer, string, strlen(string) + 1);
 300 }
 301
 302 /* Set the serialized representation of the pointer PTR inside the current
 303  * structure within the serialization CONTEXT to NULL. This is particularly
 304  * useful if the pointer is not NULL in the source structure.
 305  */
 306 void
 307 svn_temp_serializer__set_null(svn_temp_serializer__context_t *context,
 308                               const void * const * ptr)
 309 {
 310   apr_size_t offset;
 311
 312   /* there must be a parent structure */
 313   assert(context->source);
 314
 315   /* position of the serialized pointer relative to the begin of the buffer */
 316   offset = (const char *)ptr
 317          - (const char *)context->source->source_struct
 318          + context->source->target_offset;
 319
 320   /* the offset must be within the serialized data. Otherwise, you forgot
 321    * to serialize the respective sub-struct. */
 322   assert(context->buffer->len > offset);
 323
 324   /* use the serialized pointer as a storage for the offset */
 325   *(apr_size_t*)(context->buffer->data + offset) = 0;
 326 }
 327
 328 /* Return the number of bytes currently used in the serialization buffer
 329  * of the given serialization CONTEXT.*/
 330 apr_size_t
 331 svn_temp_serializer__get_length(svn_temp_serializer__context_t *context)
 332 {
 333   return context->buffer->len;
 334 }
 335
 336 /* Return the data buffer that receives the serialized data from
 337  * the given serialization CONTEXT.
 338  */
 339 svn_stringbuf_t *
 340 svn_temp_serializer__get(svn_temp_serializer__context_t *context)
 341 {
 342   return context->buffer;
 343 }
 344
 345 /* Replace the deserialized pointer value at PTR inside BUFFER with a
 346  * proper pointer value.
 347  */
 348 void
 349 svn_temp_deserializer__resolve(void *buffer, void **ptr)
 350 {
 351   /* All pointers are stored as offsets to the buffer start
 352    * (of the respective serialized sub-struct). */
 353   apr_size_t ptr_offset = *(apr_size_t *)ptr;
 354   if (ptr_offset)
 355     {
 356       /* Reconstruct the original pointer value */
 357       const char *target = (const char *)buffer + ptr_offset;
 358
 359       /* All sub-structs are written _after_ their respective parent.
 360        * Thus, all offsets are > 0. If the following assertion is not met,
 361        * the data is either corrupt or you tried to resolve the pointer
 362        * more than once. */
 363       assert(target > (const char *)buffer);
 364
 365       /* replace the PTR_OFFSET in *ptr with the pointer to TARGET */
 366       (*(const char **)ptr) = target;
 367     }
 368   else
 369     {
 370       /* NULL pointers are stored as 0 which might have a different
 371        * binary representation. */
 372       *ptr = NULL;
 373     }
 374 }
 375
 376 const void *
 377 svn_temp_deserializer__ptr(const void *buffer, const void *const *ptr)
 378 {
 379   return (apr_size_t)*ptr == 0
 380       ? NULL
 381       : (const char*)buffer + (apr_size_t)*ptr;
 382 }