[prev in list] [next in list] [prev in thread] [next in thread]
List: asterisk-commits
Subject: [asterisk-commits] kpfleming: trunk r185581 - in /trunk:
From: SVN commits to the Asterisk project <asterisk-commits () lists ! digium ! com>
Date: 2009-03-31 21:30:00
Message-ID: E1LolWy-0001ks-HQ () wibble ! digium ! internal
[Download RAW message or body]
Author: kpfleming
Date: Tue Mar 31 16:29:50 2009
New Revision: 185581
URL: http://svn.digium.com/svn-view/asterisk?view=rev&rev=185581
Log:
Optimizations to the stringfields API
This patch provides a number of optimizations to the stringfields API, focused around \
saving (not wasting) memory whenever possible. Thanks to Mark Michelson for inspiring \
this work and coming up with the first two optimizations that are represented here:
Changes:
- Cleanup of some code, fix incorrect doxygen comments
- When a field is emptied or replaced with a new allocation, decrease the amount of \
'active' space in the pool it was held in; if that pool reaches zero active space, \
and is not the current pool, then free it as it is no longer in use
- When allocating a pool, try to allocate a size that will fit in a 'standard' \
malloc() allocation without wasting space
- When allocating space for a field, store the amount of space in the two bytes \
immediately preceding the field; this eliminates the need to call strlen() on the \
field when overwriting it, and more importantly it 'remembers' the amount of space \
the field has available, even if a shorter string has been stored in it since it was \
allocated
- Don't automatically double the size of each successive pool allocated; it's \
wasteful
http://reviewboard.digium.com/r/165/
Modified:
trunk/include/asterisk/stringfields.h
trunk/main/utils.c
Modified: trunk/include/asterisk/stringfields.h
URL: http://svn.digium.com/svn-view/asterisk/trunk/include/asterisk/stringfields.h?view=diff&rev=185581&r1=185580&r2=185581
==============================================================================
--- trunk/include/asterisk/stringfields.h (original)
+++ trunk/include/asterisk/stringfields.h Tue Mar 31 16:29:50 2009
@@ -57,25 +57,23 @@
Fields will default to pointing to an empty string, and will revert to
that when ast_string_field_set() is called with a NULL argument.
- A string field will \b never contain NULL (this feature is not used
- in this code, but comes from external requirements).
+ A string field will \b never contain NULL.
ast_string_field_init(x, 0) will reset fields to the
initial value while keeping the pool allocated.
Reading the fields is much like using 'const char * const' fields in the
- structure: you cannot write to the field or to the memory it points to
- (XXX perhaps the latter is too much of a restriction since values
- are not shared).
+ structure: you cannot write to the field or to the memory it points to.
Writing to the fields must be done using the wrapper macros listed below;
and assignments are always by value (i.e. strings are copied):
* ast_string_field_set() stores a simple value;
- * ast_string_field_build() builds the string using a printf-style;
+ * ast_string_field_build() builds the string using a printf-style format;
* ast_string_field_build_va() is the varargs version of the above (for
- portability reasons it uses two vararg);
+ portability reasons it uses two vararg arguments);
* variants of these function allow passing a pointer to the field
as an argument.
+
\code
ast_string_field_set(x, foo, "infinite loop");
ast_string_field_set(x, foo, NULL); // set to an empty string
@@ -110,6 +108,9 @@
Don't declare instances of this type directly; use the AST_STRING_FIELD()
macro instead.
+
+ In addition to the string itself, the amount of space allocated for the
+ field is stored in the two bytes immediately preceding it.
*/
typedef const char * ast_string_field;
@@ -117,7 +118,7 @@
\internal
\brief A constant empty string used for fields that have no other value
*/
-extern const char __ast_string_field_empty[];
+extern const char *__ast_string_field_empty;
/*!
\internal
@@ -125,18 +126,17 @@
*/
struct ast_string_field_pool {
struct ast_string_field_pool *prev; /*!< pointer to the previous pool, if any */
+ size_t size; /*!< the total size of the pool */
+ size_t used; /*!< the space used in the pool */
+ size_t active; /*!< the amount of space actively in use by fields */
char base[0]; /*!< storage space for the fields */
};
/*!
\internal
\brief Structure used to manage the storage for a set of string fields.
- Because of the way pools are managed, we can only allocate from the topmost
- pool, so the numbers here reflect just that.
*/
struct ast_string_field_mgr {
- size_t size; /*!< the total size of the current pool */
- size_t used; /*!< the space used in the current pool */
ast_string_field last_alloc; /*!< the last field allocated */
};
@@ -154,7 +154,8 @@
the pool has enough space available. If so, the additional space will be
allocated to this field and the field's address will not be changed.
*/
-int __ast_string_field_ptr_grow(struct ast_string_field_mgr *mgr, size_t needed,
+int __ast_string_field_ptr_grow(struct ast_string_field_mgr *mgr,
+ struct ast_string_field_pool **pool_head, size_t needed,
const ast_string_field *ptr);
/*!
@@ -176,7 +177,7 @@
\internal
\brief Set a field to a complex (built) value
\param mgr Pointer to the pool manager structure
- \param fields Pointer to the first entry of the field array
+ \param pool_head Pointer to the current pool
\param ptr Pointer to a field within the structure
\param format printf-style format string
\return nothing
@@ -189,7 +190,7 @@
\internal
\brief Set a field to a complex (built) value
\param mgr Pointer to the pool manager structure
- \param fields Pointer to the first entry of the field array
+ \param pool_head Pointer to the current pool
\param ptr Pointer to a field within the structure
\param format printf-style format string
\param args va_list of the args for the format_string
@@ -242,29 +243,55 @@
/*! \internal \brief internal version of ast_string_field_init */
int __ast_string_field_init(struct ast_string_field_mgr *mgr,
- struct ast_string_field_pool **pool_head, int needed);
+ struct ast_string_field_pool **pool_head, int needed);
+
+/*!
+ \internal
+ \brief Release a field's allocation from a pool
+ \param pool_head Pointer to the current pool
+ \param ptr Field to be released
+ \return nothing
+
+ This function will search the pool list to find the pool that contains
+ the allocation for the specified field, then remove the field's allocation
+ from that pool's 'active' count. If the pool's active count reaches zero,
+ and it is not the current pool, then it will be freed.
+ */
+void __ast_string_field_release_active(struct ast_string_field_pool *pool_head,
+ const ast_string_field ptr);
+
+/* the type of storage used to track how many bytes were allocated for a field */
+
+typedef uint16_t ast_string_field_allocation;
+
+/*!
+ \brief Macro to provide access to the allocation field that lives immediately in \
front of a string field + \param x Pointer to the string field
+*/
+#define AST_STRING_FIELD_ALLOCATION(x) *((ast_string_field_allocation *) (x - \
sizeof(ast_string_field_allocation)))
/*!
\brief Set a field to a simple string value
\param x Pointer to a structure containing fields
\param ptr Pointer to a field within the structure
- \param data String value to be copied into the field
- \return nothing
-*/
-#define ast_string_field_ptr_set(x, ptr, data) do { \
- const char *__d__ = (data); \
- size_t __dlen__ = (__d__) ? strlen(__d__) + 1 : 1; \
- const char **__p__ = (const char **) (ptr); \
- char *__q__; \
- if (__dlen__ == 1) \
- *__p__ = __ast_string_field_empty; \
- else if (!__ast_string_field_ptr_grow(&(x)->__field_mgr, __dlen__, ptr)) { \
- __q__ = (char *) *__p__; \
- memcpy(__q__, __d__, __dlen__); \
- } else if ((*__p__ = __ast_string_field_alloc_space(&(x)->__field_mgr, \
&(x)->__field_mgr_pool, __dlen__))) { \
- __q__ = (char *) *__p__; \
- memcpy(__q__, __d__, __dlen__); \
- } \
+ \param data String value to be copied into the field
+ \return nothing
+*/
+#define ast_string_field_ptr_set(x, ptr, data) do { \
+ const char *__d__ = (data); \
+ size_t __dlen__ = (__d__) ? strlen(__d__) + 1 : 1; \
+ ast_string_field *__p__ = (ast_string_field *) (ptr); \
+ if (__dlen__ == 1) { \
+ __ast_string_field_release_active((x)->__field_mgr_pool, *__p__); \
+ *__p__ = __ast_string_field_empty; \
+ } else if ((__dlen__ <= AST_STRING_FIELD_ALLOCATION(*__p__)) || \
+ (!__ast_string_field_ptr_grow(&(x)->__field_mgr, &(x)->__field_mgr_pool, \
__dlen__, __p__)) || \ + (*__p__ = \
__ast_string_field_alloc_space(&(x)->__field_mgr, &(x)->__field_mgr_pool, __dlen__))) \
{ \ + if (*__p__ != (*ptr)) { \
+ __ast_string_field_release_active((x)->__field_mgr_pool, (*ptr)); \
+ } \
+ memcpy((void *) *__p__, __d__, __dlen__); \
+ } \
} while (0)
/*!
Modified: trunk/main/utils.c
URL: http://svn.digium.com/svn-view/asterisk/trunk/main/utils.c?view=diff&rev=185581&r1=185580&r2=185581
==============================================================================
--- trunk/main/utils.c (original)
+++ trunk/main/utils.c Tue Mar 31 16:29:50 2009
@@ -1469,7 +1469,32 @@
* stringfields support routines.
*/
-const char __ast_string_field_empty[] = ""; /*!< the empty string */
+/* this is a little complex... string fields are stored with their
+ allocated size in the bytes preceding the string; even the
+ constant 'empty' string has to be this way, so the code that
+ checks to see if there is enough room for a new string doesn't
+ have to have any special case checks
+*/
+
+static const struct {
+ ast_string_field_allocation allocation;
+ char string[1];
+} __ast_string_field_empty_buffer;
+
+ast_string_field __ast_string_field_empty = __ast_string_field_empty_buffer.string;
+
+#define ALLOCATOR_OVERHEAD 48
+
+static size_t optimal_alloc_size(size_t size)
+{
+ unsigned int count;
+
+ size += ALLOCATOR_OVERHEAD;
+
+ for (count = 1; size; size >>= 1, count++);
+
+ return (1 << count) - ALLOCATOR_OVERHEAD;
+}
/*! \brief add a new block to the pool.
* We can only allocate from the topmost pool, so the
@@ -1480,14 +1505,15 @@
size_t size)
{
struct ast_string_field_pool *pool;
-
- if (!(pool = ast_calloc(1, sizeof(*pool) + size)))
+ size_t alloc_size = optimal_alloc_size(sizeof(*pool) + size);
+
+ if (!(pool = ast_calloc(1, alloc_size))) {
return -1;
-
+ }
+
pool->prev = *pool_head;
+ pool->size = alloc_size - sizeof(*pool);
*pool_head = pool;
- mgr->size = size;
- mgr->used = 0;
mgr->last_alloc = NULL;
return 0;
@@ -1511,13 +1537,16 @@
struct ast_string_field_pool *cur = *pool_head;
/* clear fields - this is always necessary */
- while ((struct ast_string_field_mgr *) p != mgr)
+ while ((struct ast_string_field_mgr *) p != mgr) {
*p++ = __ast_string_field_empty;
+ }
+
mgr->last_alloc = NULL;
if (size > 0) { /* allocate the initial pool */
*pool_head = NULL;
return add_string_pool(mgr, pool_head, size);
}
+
if (size < 0) { /* reset all pools */
*pool_head = NULL;
} else { /* preserve the first pool */
@@ -1527,7 +1556,7 @@
}
cur = cur->prev;
(*pool_head)->prev = NULL;
- mgr->used = 0;
+ (*pool_head)->used = (*pool_head)->active = 0;
}
while (cur) {
@@ -1544,33 +1573,36 @@
struct ast_string_field_pool **pool_head, size_t needed)
{
char *result = NULL;
- size_t space = mgr->size - mgr->used;
-
- if (__builtin_expect(needed > space, 0)) {
- size_t new_size = mgr->size * 2;
-
- while (new_size < needed)
+ size_t space = (*pool_head)->size - (*pool_head)->used;
+ size_t to_alloc = needed + sizeof(ast_string_field_allocation);
+
+ if (__builtin_expect(to_alloc > space, 0)) {
+ size_t new_size = (*pool_head)->size;
+
+ while (new_size < to_alloc) {
new_size *= 2;
+ }
if (add_string_pool(mgr, pool_head, new_size))
return NULL;
}
- result = (*pool_head)->base + mgr->used;
- mgr->used += needed;
+ result = (*pool_head)->base + (*pool_head)->used;
+ (*pool_head)->used += to_alloc;
+ (*pool_head)->active += needed;
+ result += sizeof(ast_string_field_allocation);
+ AST_STRING_FIELD_ALLOCATION(result) = needed;
mgr->last_alloc = result;
+
return result;
}
-int __ast_string_field_ptr_grow(struct ast_string_field_mgr *mgr, size_t needed,
+int __ast_string_field_ptr_grow(struct ast_string_field_mgr *mgr,
+ struct ast_string_field_pool **pool_head, size_t needed,
const ast_string_field *ptr)
{
- int grow = needed - (strlen(*ptr) + 1);
- size_t space = mgr->size - mgr->used;
-
- if (grow <= 0) {
- return 0;
- }
+ ssize_t grow = needed - AST_STRING_FIELD_ALLOCATION(*ptr);
+ size_t space = (*pool_head)->size - (*pool_head)->used;
if (*ptr != mgr->last_alloc) {
return 1;
@@ -1580,9 +1612,32 @@
return 1;
}
- mgr->used += grow;
+ (*pool_head)->used += grow;
+ (*pool_head)->active += grow;
+ AST_STRING_FIELD_ALLOCATION(*ptr) += grow;
return 0;
+}
+
+void __ast_string_field_release_active(struct ast_string_field_pool *pool_head,
+ const ast_string_field ptr)
+{
+ struct ast_string_field_pool *pool, *prev;
+
+ if (ptr == __ast_string_field_empty) {
+ return;
+ }
+
+ for (pool = pool_head, prev = NULL; pool; prev = pool, pool = pool->prev) {
+ if ((ptr >= pool->base) && (ptr <= (pool->base + pool->size))) {
+ pool->active -= AST_STRING_FIELD_ALLOCATION(ptr);
+ if ((pool->active == 0) && prev) {
+ prev->prev = pool->prev;
+ ast_free(pool);
+ }
+ break;
+ }
+ }
}
void __ast_string_field_ptr_build_va(struct ast_string_field_mgr *mgr,
@@ -1591,19 +1646,23 @@
{
size_t needed;
size_t available;
- size_t space = mgr->size - mgr->used;
+ size_t space = (*pool_head)->size - (*pool_head)->used;
+ ssize_t grow;
char *target;
/* if the field already has space allocated, try to reuse it;
- otherwise, use the empty space at the end of the current
+ otherwise, try to use the empty space at the end of the current
pool
*/
- if ((*ptr)[0] != '\0') {
+ if (*ptr != __ast_string_field_empty) {
target = (char *) *ptr;
- available = strlen(target) + 1;
+ available = AST_STRING_FIELD_ALLOCATION(*ptr);
+ if (*ptr == mgr->last_alloc) {
+ available += space;
+ }
} else {
- target = (*pool_head)->base + mgr->used;
- available = space;
+ target = (*pool_head)->base + (*pool_head)->used + \
sizeof(ast_string_field_allocation); + available = space - \
sizeof(ast_string_field_allocation); }
needed = vsnprintf(target, available, format, ap1) + 1;
@@ -1611,28 +1670,32 @@
va_end(ap1);
if (needed > available) {
- /* if the space needed can be satisfied by using the current
- pool (which could only occur if we tried to use the field's
- allocated space and failed), then use that space; otherwise
- allocate a new pool
+ /* the allocation could not be satisfied using the field's current allocation
+ (if it has one), or the space available in the pool (if it does not). allocate
+ space for it, adding a new string pool if necessary.
*/
- if (needed > space) {
- size_t new_size = mgr->size * 2;
-
- while (new_size < needed)
- new_size *= 2;
-
- if (add_string_pool(mgr, pool_head, new_size))
- return;
- }
-
- target = (*pool_head)->base + mgr->used;
+ if (!(target = (char *) __ast_string_field_alloc_space(mgr, pool_head, needed))) {
+ return;
+ }
vsprintf(target, format, ap2);
- }
-
- if (*ptr != target) {
+ __ast_string_field_release_active(*pool_head, *ptr);
+ *ptr = target;
+ } else if (*ptr != target) {
+ /* the allocation was satisfied using available space in the pool, but not
+ using the space already allocated to the field
+ */
+ __ast_string_field_release_active(*pool_head, *ptr);
mgr->last_alloc = *ptr = target;
- mgr->used += needed;
+ AST_STRING_FIELD_ALLOCATION(target) = needed;
+ (*pool_head)->used += needed + sizeof(ast_string_field_allocation);
+ (*pool_head)->active += needed;
+ } else if ((grow = (needed - AST_STRING_FIELD_ALLOCATION(*ptr))) > 0) {
+ /* the allocation was satisfied by using available space in the pool *and*
+ the field was the last allocated field from the pool, so it grew
+ */
+ (*pool_head)->used += grow;
+ (*pool_head)->active += grow;
+ AST_STRING_FIELD_ALLOCATION(*ptr) += grow;
}
}
_______________________________________________
--Bandwidth and Colocation Provided by http://www.api-digital.com--
asterisk-commits mailing list
To UNSUBSCRIBE or update options visit:
http://lists.digium.com/mailman/listinfo/asterisk-commits
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic