You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by st...@apache.org on 2010/07/31 22:28:50 UTC
svn commit: r981090 - in /subversion/branches/performance/subversion:
include/private/svn_serializer.h libsvn_subr/svn_serializer.c
Author: stefan2
Date: Sat Jul 31 20:28:49 2010
New Revision: 981090
URL: http://svn.apache.org/viewvc?rev=981090&view=rev
Log:
Introduce a simple serialization framework that simplifies and
speeds up serialization of most data structures used by FSFS,
for instance.
* subversion/include/private/svn_serializer.h
(PCPCSTR, PCPCVOID, PPVOID): introduce useful typedefs
(svn_serializer__context_t): introduce new data type
(svn_serializer__init, svn_serializer__push, svn_serializer__pop,
svn_serializer__add_string, svn_serializer__get): declare new
serialization functions
(svn_deserializer__resolve): declare new deserialization function
Added:
subversion/branches/performance/subversion/include/private/svn_serializer.h (with props)
subversion/branches/performance/subversion/libsvn_subr/svn_serializer.c (with props)
Added: subversion/branches/performance/subversion/include/private/svn_serializer.h
URL: http://svn.apache.org/viewvc/subversion/branches/performance/subversion/include/private/svn_serializer.h?rev=981090&view=auto
==============================================================================
--- subversion/branches/performance/subversion/include/private/svn_serializer.h (added)
+++ subversion/branches/performance/subversion/include/private/svn_serializer.h Sat Jul 31 20:28:49 2010
@@ -0,0 +1,124 @@
+/**
+ * @copyright
+ * ====================================================================
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ * ====================================================================
+ * @endcopyright
+ *
+ * @file svn_serializer.h
+ * @brief Structure serialization helper API
+ */
+
+#include <apr.h>
+#include "svn_types.h"
+
+/* forward declaration */
+struct svn_stringbuf_t;
+
+/* We often use references to pointers. Although converting a pointer to
+ * a pointer can safely be cast to references to constant pointers to
+ * constant data, C compilers tend to reject them. Provide a couple of
+ * typedefs to simplify explicit casts.
+ */
+typedef const char * const * PCPCSTR;
+typedef const void * const * PCPCVOID;
+typedef void * * PPVOID;
+
+/**
+ * Opaque structure controlling the serialization process and holding the
+ * intermediate as well as final results.
+ */
+typedef struct svn_serializer__context_t svn_serializer__context_t;
+
+/**
+ * Begin the serialization process for the @a source_struct and all objects
+ * referenced from it. @a struct_size must match the result of @c sizeof()
+ * of the actual structure. Due to the generic nature of the init function
+ * we can't determine the structure size as part of the function.
+ *
+ * You may suggest a larger initial buffer size in @a suggested_buffer_size
+ * to minimize the number of internal buffer re-allocations during the
+ * serialization process. All allocations will be made from @a pool.
+ *
+ * Pointers within the structure will be replaced by their serialized
+ * representation when the respective strings or sub-structures get
+ * serialized. This scheme allows only for tree-like, i.e. non-circular
+ * data structures.
+ *
+ * @return the serization context.
+ */
+svn_serializer__context_t *
+svn_serializer__init(const void *source_struct,
+ apr_size_t struct_size,
+ apr_size_t suggested_buffer_size,
+ apr_pool_t *pool);
+
+/**
+ * Begin serialization of a referenced sub-structure within the
+ * serialization @a context. @a source_struct must be a reference to the
+ * pointer in the original parent structure so that the correspondence in
+ * the serialized structure can be established. @a struct_size must match
+ * the result of @c sizeof() of the actual structure.
+ *
+ * Sub-structures and strings will be added in a FIFO fashion. If you need
+ * add further sub-structures on the same level, you need to call @ref
+ * svn_serializer__pop to realign the serialization context.
+ */
+void
+svn_serializer__push(svn_serializer__context_t *context,
+ PCPCVOID source_struct,
+ apr_size_t struct_size);
+
+/**
+ * End the serialization of the current sub-structure. The serialization
+ * @c context will be focussed back on the parent structure. You may then
+ * add further sub-structures starting from that level.
+ *
+ * It is not necessary to call this function just for symmetry at the end
+ * of the serialization process.
+ */
+void
+svn_serializer__pop(svn_serializer__context_t *context);
+
+/**
+ * Serialize a string referenced from the current structure within the
+ * serialization @a context. @a s must be a reference to the @c char*
+ * pointer in the original structure so that the correspondence in the
+ * serialized structure can be established.
+ */
+void
+svn_serializer__add_string(svn_serializer__context_t *context, PCPCSTR s);
+
+/**
+ * @return a reference to the data buffer containing the data serialialized
+ * so far in the given serialization @a context.
+ */
+struct svn_stringbuf_t *
+svn_serializer__get(svn_serializer__context_t *context);
+
+/**
+ * Deserialization is straightforward: just copy the serialized buffer to
+ * a natively aligned memory location (APR pools will take care of that
+ * automatically) and resolve all pointers to sub-structures.
+ *
+ * To do the latter, call this function for each of these pointers, giving
+ * the start address of the copyied buffer in @a buffer and a reference to
+ * the pointer to resolve in @a ptr.
+ */
+void
+svn_deserializer__resolve(void *buffer, PPVOID ptr);
Propchange: subversion/branches/performance/subversion/include/private/svn_serializer.h
------------------------------------------------------------------------------
svn:eol-style = native
Added: subversion/branches/performance/subversion/libsvn_subr/svn_serializer.c
URL: http://svn.apache.org/viewvc/subversion/branches/performance/subversion/libsvn_subr/svn_serializer.c?rev=981090&view=auto
==============================================================================
--- subversion/branches/performance/subversion/libsvn_subr/svn_serializer.c (added)
+++ subversion/branches/performance/subversion/libsvn_subr/svn_serializer.c Sat Jul 31 20:28:49 2010
@@ -0,0 +1,242 @@
+/*
+ * svn_serializer.c: serialization helper functions
+ *
+ * ====================================================================
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ * ====================================================================
+ */
+
+#include <assert.h>
+#include "private/svn_serializer.h"
+#include "svn_string.h"
+
+/* This is a very efficient serialization and especially efficient
+ * deserialization framework. The idea is just to concatenate all sub-
+ * structures and strings into a single buffer while preserving proper
+ * member alignment. Pointers will be replaced by the respective data
+ * offsets in the buffer when that target that it pointed to gets
+ * serialized, i.e. appended to the data buffer written so far.
+ *
+ * Hence, deserialization can be simply done by copying the buffer and
+ * adjusting the pointers. No fine-grained allocation and copying is
+ * necessary.
+ */
+
+/* An element in the structure stack. It contains a pointer to the source
+ * structure so that the relative offset of sub-structure or string
+ * references can be determined properly. It also contains the corresponding
+ * position within the serialized data. Thus, pointers can be serialized
+ * as offsets within the target buffer.
+ */
+typedef struct source_stack_t
+{
+ /* the source structure passed in to *_init or *_push */
+ const void *source_struct;
+
+ /* offset within the target buffer to where the structure got copied */
+ apr_size_t target_offset;
+
+ /* parent stack entry. Will be NULL for the root entry. */
+ struct source_stack_t *upper;
+} source_stack_t;
+
+/* Serialization context info. It basically consists of the buffer holding
+ * the serialized result and the stack of source structure information.
+ */
+struct svn_serializer__context_t
+{
+ /* allocations are made from this pool */
+ apr_pool_t *pool;
+
+ /* the buffer holding all serialized data */
+ svn_stringbuf_t *buffer;
+
+ /* the stack of structures being serialized. If NULL, the serialization
+ * process has been finished. However, it is not necessarily NULL when
+ * the application end serialization. */
+ source_stack_t *source;
+};
+
+/* Mmake sure the serialized data len is a multiple of the default alignment,
+ * i.e. structures may be appended without violating member alignment
+ * guarantees.
+ */
+static void
+align_buffer_end(svn_serializer__context_t *context)
+{
+ apr_size_t current_len = context->buffer->len;
+ apr_size_t aligned_len = APR_ALIGN_DEFAULT(current_len);
+ if (aligned_len != current_len)
+ {
+ svn_stringbuf_ensure(context->buffer, aligned_len+1);
+ context->buffer->len = aligned_len;
+ }
+}
+
+/* Begin the serialization process for the SOURCE_STRUCT and all objects
+ * referenced from it. STRUCT_SIZE must match the result of sizeof() of
+ * the actual structure. You may suggest a larger initial buffer size
+ * in SUGGESTED_BUFFER_SIZE to minimize the number of internal buffer
+ * re-allocations during the serialization process. All allocations will
+ * be made from POOL.
+ */
+svn_serializer__context_t *
+svn_serializer__init(const void *source_struct,
+ apr_size_t struct_size,
+ apr_size_t suggested_buffer_size,
+ apr_pool_t *pool)
+{
+ /* select a meaningful initial memory buffer capacity */
+ apr_size_t init_size = suggested_buffer_size < struct_size
+ ? struct_size
+ : suggested_buffer_size;
+
+ /* create the serialization context and initialize it, including the
+ * structure stack */
+ svn_serializer__context_t *context = apr_palloc(pool, sizeof(*context));
+ context->pool = pool;
+ context->buffer = svn_stringbuf_create_ensure(init_size, pool);
+ context->source = apr_palloc(pool, sizeof(*context->source));
+ context->source->source_struct = source_struct;
+ context->source->target_offset = 0;
+ context->source->upper = NULL;
+
+ /* serialize, i.e. append, the content of the first structure */
+ svn_stringbuf_appendbytes(context->buffer, source_struct, struct_size);
+
+ /* done */
+ return context;
+}
+
+/* Utility function replacing the serialized pointer corresponding to
+ * *SOURCE_POINTER with the offset that it will be put when being append
+ * right after this function call.
+ */
+static void
+store_current_end_pointer(svn_serializer__context_t *context,
+ PCPCVOID source_pointer)
+{
+ /* relative position of the serialized pointer to the begin of the buffer */
+ apr_size_t offset = (const char *)source_pointer
+ - (const char *)context->source->source_struct
+ + context->source->target_offset;
+
+ /* use the serialized pointer as a storage for the offset */
+ apr_size_t *target_string_ptr = (apr_size_t*)(context->buffer->data + offset);
+
+ /* the offset must be within the serialized data. Otherwise, you forgot
+ * to serialize the respective sub-struct. */
+ assert(context->buffer->len > offset);
+
+ /* store the current buffer length because that's where we will append
+ * the serialized data of the sub-struct or string */
+ *target_string_ptr = *source_pointer == NULL ? 0 : context->buffer->len;
+}
+
+/* Begin serialization of a referenced sub-structure within the
+ * serialization CONTEXT. SOURCE_STRUCT must be a reference to the pointer
+ * in the original parent structure so that the correspondence in the
+ * serialized structure can be established. STRUCT_SIZE must match the
+ * result of sizeof() of the actual structure.
+ */
+void
+svn_serializer__push(svn_serializer__context_t *context,
+ PCPCVOID source_struct,
+ apr_size_t struct_size)
+{
+ /* create a new entry for the structure stack */
+ source_stack_t *new = apr_palloc(context->pool, sizeof(*new));
+
+ /* the serialized structure must be properly aligned */
+ if (*source_struct)
+ align_buffer_end(context);
+
+ /* Store the offset at which the struct data that will the appended.
+ * Write 0 for NULL pointers. */
+ store_current_end_pointer(context, source_struct);
+
+ /* store source and target information */
+ new->source_struct = *source_struct;
+ new->target_offset = context->buffer->len;
+
+ /* put the new entry onto the stack*/
+ new->upper = context->source;
+ context->source = new;
+
+ /* finally, actually append the new struct
+ * (so we can now manipulate pointers within it) */
+ if (*source_struct)
+ svn_stringbuf_appendbytes(context->buffer, *source_struct, struct_size);
+}
+
+/* Remove the lastest structure from the stack.
+ */
+void
+svn_serializer__pop(svn_serializer__context_t *context)
+{
+ /* we may pop the original struct but not further */
+ assert(context->source);
+
+ /* one level up the structure stack */
+ context->source = context->source->upper;
+}
+
+/* Serialize a string referenced from the current structure within the
+ * serialization CONTEXT. S must be a reference to the char* pointer in
+ * the original structure so that the correspondence in the serialized
+ * structure can be established.
+ */
+void
+svn_serializer__add_string(svn_serializer__context_t *context, PCPCSTR s)
+{
+ /* Store the offset at which the string data that will the appended.
+ * Write 0 for NULL pointers. Strings don't need special alignment. */
+ store_current_end_pointer(context, (const void **)s);
+
+ /* append the string data */
+ if (*s)
+ svn_stringbuf_appendbytes(context->buffer, *s, strlen(*s) + 1);
+}
+
+/* Return the the data buffer that receives the serialialized data from
+ * the given serialization CONTEXT.
+ */
+svn_stringbuf_t *
+svn_serializer__get(svn_serializer__context_t *context)
+{
+ return context->buffer;
+}
+
+/* Replace the deserialized pointer value at PTR inside BUFFER with a
+ * proper pointer value.
+ */
+void
+svn_deserializer__resolve(void *buffer, PPVOID ptr)
+{
+ if ((apr_size_t)*ptr)
+ {
+ /* replace the offset in *ptr with the pointer to buffer[*ptr] */
+ (*(const char **)ptr) = (const char*)buffer + (apr_size_t)*ptr;
+ }
+ else
+ {
+ /* NULL pointers are stored as 0 which might have a different
+ * binary representation. */
+ *ptr = NULL;
+ }
+}
Propchange: subversion/branches/performance/subversion/libsvn_subr/svn_serializer.c
------------------------------------------------------------------------------
svn:eol-style = native
Re: svn commit: r981090 - in /subversion/branches/performance/subversion:
include/private/svn_serializer.h libsvn_subr/svn_serializer.c
Posted by Stefan Fuhrmann <st...@alice-dsl.de>.
Greg Stein wrote:
> And style nit: we *never* use upper-case typedef names (and generally
> avoid hungarian notation concepts).
>
The problem here is that gcc is very picky when it comes to
implicitly converting double pointers to const void * const *:
it tends to issue warnings. So, it takes some extra explicit
casts to silence them.
For the time being, I'm removing the typedefs and will use
verbatim casts where necessary.
-- Stefan^2.
Re: svn commit: r981090 - in /subversion/branches/performance/subversion:
include/private/svn_serializer.h libsvn_subr/svn_serializer.c
Posted by Greg Stein <gs...@gmail.com>.
On Sat, Jul 31, 2010 at 18:22, Blair Zajac <bl...@orcaware.com> wrote:
>
> On Jul 31, 2010, at 1:28 PM, stefan2@apache.org wrote:
>
>> Author: stefan2
>> Date: Sat Jul 31 20:28:49 2010
>> New Revision: 981090
>>
>> URL: http://svn.apache.org/viewvc?rev=981090&view=rev
>> Log:
>> Introduce a simple serialization framework that simplifies and
>> speeds up serialization of most data structures used by FSFS,
>> for instance.
>
> Instead of rolling another serialization in svn, what about using protobuf for C?
>
> http://code.google.com/p/protobuf-c/
>
> I has an Apache 2 license, so will be compatible with us.
>
> Another one to consider is using Thrift, which writes C code:
>
> http://wiki.apache.org/thrift/
>
> On advantage to these serialization tools is that they are extensible, so we can always add additional fields to the serialized structs and not break binary compatibility.
Not to mention our skel implementation.
But the big thing here is that this serializer creates non-portable
files. IIRC, FSFS was designed to have portable files. (where
"portable" means across architectures, byte alignments, etc)
And style nit: we *never* use upper-case typedef names (and generally
avoid hungarian notation concepts).
Cheers,
-g
Re: svn commit: r981090 - in /subversion/branches/performance/subversion:
include/private/svn_serializer.h libsvn_subr/svn_serializer.c
Posted by Stefan Fuhrmann <st...@alice-dsl.de>.
Blair Zajac wrote:
> On Jul 31, 2010, at 1:28 PM, stefan2@apache.org wrote:
>
>
>> Author: stefan2
>> Date: Sat Jul 31 20:28:49 2010
>> New Revision: 981090
>>
>> URL: http://svn.apache.org/viewvc?rev=981090&view=rev
>> Log:
>> Introduce a simple serialization framework that simplifies and
>> speeds up serialization of most data structures used by FSFS,
>> for instance.
>>
>
> Instead of rolling another serialization in svn, what about using protobuf for C?
>
> http://code.google.com/p/protobuf-c/
>
> I has an Apache 2 license, so will be compatible with us.
>
> Another one to consider is using Thrift, which writes C code:
>
> http://wiki.apache.org/thrift/
>
> On advantage to these serialization tools is that they are extensible, so we can always add additional fields to the serialized structs and not break binary compatibility.
>
I'm happy to replace my code with any other that uses 50 LOC or less.
Do you know one ;) ?
But seriously, I probably shouldn't have mentioned FSFS in the commit
message because it obviously misled people. r981189 should make my
intentions clearer. The whole purpose of this API is to allow for efficient
implementations of svn_cache__dup_func_t, svn_cache__deserialize_func_t
and svn_cache__serialize_func_t.
-- Stefan^2.
Re: svn commit: r981090 - in /subversion/branches/performance/subversion: include/private/svn_serializer.h libsvn_subr/svn_serializer.c
Posted by Blair Zajac <bl...@orcaware.com>.
On Jul 31, 2010, at 1:28 PM, stefan2@apache.org wrote:
> Author: stefan2
> Date: Sat Jul 31 20:28:49 2010
> New Revision: 981090
>
> URL: http://svn.apache.org/viewvc?rev=981090&view=rev
> Log:
> Introduce a simple serialization framework that simplifies and
> speeds up serialization of most data structures used by FSFS,
> for instance.
Instead of rolling another serialization in svn, what about using protobuf for C?
http://code.google.com/p/protobuf-c/
I has an Apache 2 license, so will be compatible with us.
Another one to consider is using Thrift, which writes C code:
http://wiki.apache.org/thrift/
On advantage to these serialization tools is that they are extensible, so we can always add additional fields to the serialized structs and not break binary compatibility.
Regards,
Blair