array: introduce an array collection storing elements very efficiently
authorMartin Willi <martin@revosec.ch>
Thu, 11 Jul 2013 09:44:33 +0000 (11:44 +0200)
committerMartin Willi <martin@revosec.ch>
Wed, 17 Jul 2013 15:20:17 +0000 (17:20 +0200)
Currently we use the very versatile linked-list collection to store elements
with variable count. This is fine, but very inefficient: Due to the many
methods in the linked list, on 64-bit platforms an empty list alone is more
than 200 bytes. As we currently have about 50 lists per IKE_SA/CHILD_SA pair,
this takes up to 10KB just for managing the empty lists. This is about the
half of memory used by an IKE_SA/CHILD_SA pair, and obviously way too much.

The new array type is not an object, but a collection of functions on an
abstract type.

The following lists are per IKE_SA and should be considered for a replacement
with more efficient arrays (this uses load-testers on-demand created dynamic
configurations, other scenarios have different lists):

14 -> ike_sa_create() @ src/libcharon/sa/ike_sa.c:2198
10 -> auth_cfg_create() @ src/libstrongswan/credentials/auth_cfg.c:1088
 6 -> task_manager_v2_create() @ src/libcharon/sa/ikev2/task_manager_v2.c:1505
 6 -> proposal_create() @ src/libcharon/config/proposal.c:592
 5 -> peer_cfg_create() @ src/libcharon/config/peer_cfg.c:657
 4 -> child_sa_create() @ src/libcharon/sa/child_sa.c:1090
 2 -> child_cfg_create() @ src/libcharon/config/child_cfg.c:536
 1 -> ike_cfg_create() @ src/libcharon/config/ike_cfg.c:330
 1 -> put_connected_peers() @ src/libcharon/sa/ike_sa_manager.c:854

src/libstrongswan/Android.mk
src/libstrongswan/Makefile.am
src/libstrongswan/collections/array.c [new file with mode: 0644]
src/libstrongswan/collections/array.h [new file with mode: 0644]

index 75b501f..dc533a3 100644 (file)
@@ -6,6 +6,7 @@ LOCAL_SRC_FILES := \
 library.c \
 asn1/asn1.c asn1/asn1_parser.c asn1/oid.c bio/bio_reader.c bio/bio_writer.c \
 collections/blocking_queue.c collections/enumerator.c collections/hashtable.c \
+collections/array.c \
 collections/linked_list.c crypto/crypters/crypter.c crypto/hashers/hasher.c \
 crypto/proposal/proposal_keywords.c crypto/proposal/proposal_keywords_static.c \
 crypto/prfs/prf.c crypto/prfs/mac_prf.c crypto/pkcs5.c \
@@ -110,4 +111,3 @@ LOCAL_PRELINK_MODULE := false
 LOCAL_SHARED_LIBRARIES += libdl libvstr
 
 include $(BUILD_SHARED_LIBRARY)
-
index 567bdfe..bde5f71 100644 (file)
@@ -4,6 +4,7 @@ libstrongswan_la_SOURCES = \
 library.c \
 asn1/asn1.c asn1/asn1_parser.c asn1/oid.c bio/bio_reader.c bio/bio_writer.c \
 collections/blocking_queue.c collections/enumerator.c collections/hashtable.c \
+collections/array.c \
 collections/linked_list.c crypto/crypters/crypter.c crypto/hashers/hasher.c \
 crypto/proposal/proposal_keywords.c crypto/proposal/proposal_keywords_static.c \
 crypto/prfs/prf.c crypto/prfs/mac_prf.c crypto/pkcs5.c \
@@ -39,7 +40,7 @@ nobase_strongswan_include_HEADERS = \
 library.h \
 asn1/asn1.h asn1/asn1_parser.h asn1/oid.h bio/bio_reader.h bio/bio_writer.h \
 collections/blocking_queue.h collections/enumerator.h collections/hashtable.h \
-collections/linked_list.h \
+collections/linked_list.h collections/array.h \
 crypto/crypters/crypter.h crypto/hashers/hasher.h crypto/mac.h \
 crypto/proposal/proposal_keywords.h crypto/proposal/proposal_keywords_static.h \
 crypto/prfs/prf.h crypto/prfs/mac_prf.h crypto/rngs/rng.h crypto/nonce_gen.h \
diff --git a/src/libstrongswan/collections/array.c b/src/libstrongswan/collections/array.c
new file mode 100644 (file)
index 0000000..d92eaac
--- /dev/null
@@ -0,0 +1,416 @@
+/*
+ * Copyright (C) 2013 Martin Willi
+ * Copyright (C) 2013 revosec AG
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * for more details.
+ */
+
+#include "array.h"
+
+/**
+ * Data is an allocated block, with potentially unused head and tail:
+ *
+ *   "esize" each (or sizeof(void*) if esize = 0)
+ *  /-\ /-\ /-\ /-\ /-\ /-\
+ *
+ * +---------------+-------------------------------+---------------+
+ * | h | e | a | d | e | l | e | m | e | n | t | s | t | a | i | l |
+ * +---------------+-------------------------------+---------------+
+ *
+ * \--------------/ \-----------------------------/ \-------------/
+ *      unused                    used                   unused
+ *      "head"                   "count"                 "tail"
+ *
+ */
+struct array_t {
+       /** number of elements currently in array (not counting head/tail) */
+       u_int32_t count;
+       /** size of each element, 0 for a pointer based array */
+       u_int16_t esize;
+       /** allocated but unused elements at array front */
+       u_int8_t head;
+       /** allocated but unused elements at array end */
+       u_int8_t tail;
+       /** array elements */
+       void *data;
+};
+
+/** maximum number of unused head/tail elements before cleanup */
+#define ARRAY_MAX_UNUSED 32
+
+/**
+ * Get the actual size of a number of elements
+ */
+static size_t get_size(array_t *array, int num)
+{
+       if (array->esize)
+       {
+               return array->esize * num;
+       }
+       return sizeof(void*) * num;
+}
+
+/**
+ * Increase allocated but unused tail room to at least "room"
+ */
+static void make_tail_room(array_t *array, u_int8_t room)
+{
+       if (array->tail < room)
+       {
+               array->data = realloc(array->data,
+                                               get_size(array, array->count + array->head + room));
+               array->tail = room;
+       }
+}
+
+/**
+ * Increase allocated but unused head room to at least "room"
+ */
+static void make_head_room(array_t *array, u_int8_t room)
+{
+       if (array->head < room)
+       {
+               u_int8_t increase = room - array->head;
+
+               array->data = realloc(array->data,
+                                               get_size(array, array->count + array->tail + room));
+               memmove(array->data + get_size(array, increase), array->data,
+                               get_size(array, array->count + array->tail + array->head));
+               array->head = room;
+       }
+}
+
+/**
+ * Make space for an item at index using tail room
+ */
+static void insert_tail(array_t *array, int idx)
+{
+       make_tail_room(array, 1);
+       /* move up all elements after idx by one */
+       memmove(array->data + get_size(array, array->head + idx + 1),
+                       array->data + get_size(array, array->head + idx),
+                       get_size(array, array->count - idx));
+
+       array->tail--;
+       array->count++;
+}
+
+/**
+ * Make space for an item at index using head room
+ */
+static void insert_head(array_t *array, int idx)
+{
+       make_head_room(array, 1);
+       /* move down all elements before idx by one */
+       memmove(array->data + get_size(array, array->head - 1),
+                       array->data + get_size(array, array->head),
+                       get_size(array, idx));
+
+       array->head--;
+       array->count++;
+}
+
+/**
+ * Remove an item, increase tail
+ */
+static void remove_tail(array_t *array, int idx)
+{
+       /* move all items after idx one down */
+       memmove(array->data + get_size(array, idx + array->head),
+                       array->data + get_size(array, idx + array->head + 1),
+                       get_size(array, array->count - idx));
+       array->count--;
+       array->tail++;
+}
+
+/**
+ * Remove an item, increase head
+ */
+static void remove_head(array_t *array, int idx)
+{
+       /* move all items before idx one up */
+       memmove(array->data + get_size(array, array->head + 1),
+                       array->data + get_size(array, array->head), get_size(array, idx));
+       array->count--;
+       array->head++;
+}
+
+array_t *array_create(u_int esize, u_int8_t reserve)
+{
+       array_t *array;
+
+       INIT(array,
+               .esize = esize,
+               .tail = reserve,
+       );
+       if (array->tail)
+       {
+               array->data = malloc(array->tail * array->esize);
+       }
+       return array;
+}
+
+int array_count(array_t *array)
+{
+       if (array)
+       {
+               return array->count;
+       }
+       return 0;
+}
+
+void array_compress(array_t *array)
+{
+       if (array)
+       {
+               u_int32_t tail;
+
+               tail = array->tail;
+               if (array->head)
+               {
+                       memmove(array->data, array->data + get_size(array, array->head),
+                                       get_size(array, array->count + array->tail));
+                       tail += array->head;
+                       array->head = 0;
+               }
+               if (tail)
+               {
+                       array->data = realloc(array->data, get_size(array, array->count));
+                       array->tail = 0;
+               }
+       }
+}
+
+typedef struct {
+       /** public enumerator interface */
+       enumerator_t public;
+       /** enumerated array */
+       array_t *array;
+       /** current index +1, initialized at 0 */
+       int idx;
+} array_enumerator_t;
+
+METHOD(enumerator_t, enumerate, bool,
+       array_enumerator_t *this, void **out)
+{
+       void *pos;
+
+       if (this->idx >= this->array->count)
+       {
+               return FALSE;
+       }
+
+       pos = this->array->data +
+                 get_size(this->array, this->idx + this->array->head);
+       if (this->array->esize)
+       {
+               /* for element based arrays we return a pointer to the element */
+               *out = pos;
+       }
+       else
+       {
+               /* for pointer based arrays we return the pointer directly */
+               *out = *(void**)pos;
+       }
+       this->idx++;
+       return TRUE;
+}
+
+enumerator_t* array_create_enumerator(array_t *array)
+{
+       array_enumerator_t *enumerator;
+
+       if (!array)
+       {
+               return enumerator_create_empty();
+       }
+
+       INIT(enumerator,
+               .public = {
+                       .enumerate = (void*)_enumerate,
+                       .destroy = (void*)free,
+               },
+               .array = array,
+       );
+       return &enumerator->public;
+}
+
+void array_remove_at(array_t *array, enumerator_t *public)
+{
+       array_enumerator_t *enumerator = (array_enumerator_t*)public;
+
+       if (enumerator->idx)
+       {
+               array_remove(array, --enumerator->idx, NULL);
+       }
+}
+
+void array_insert_create(array_t **array, int idx, void *ptr)
+{
+       if (*array == NULL)
+       {
+               *array = array_create(0, 0);
+       }
+       array_insert(*array, idx, ptr);
+}
+
+void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator)
+{
+       void *ptr;
+
+       while (enumerator->enumerate(enumerator, &ptr))
+       {
+               array_insert(array, idx, ptr);
+       }
+       enumerator->destroy(enumerator);
+}
+
+void array_insert(array_t *array, int idx, void *data)
+{
+       if (idx < 0 || idx <= array_count(array))
+       {
+               void *pos;
+
+               if (idx < 0)
+               {
+                       idx = array_count(array);
+               }
+
+               if (array->head && !array->tail)
+               {
+                       insert_head(array, idx);
+               }
+               else if (array->tail && !array->head)
+               {
+                       insert_tail(array, idx);
+               }
+               else if (idx > array_count(array) / 2)
+               {
+                       insert_tail(array, idx);
+               }
+               else
+               {
+                       insert_head(array, idx);
+               }
+
+               pos = array->data + get_size(array, array->head + idx);
+               if (array->esize)
+               {
+                       memcpy(pos, data, get_size(array, 1));
+               }
+               else
+               {
+                       /* pointer based array, copy pointer value */
+                       *(void**)pos = data;
+               }
+       }
+}
+
+bool array_remove(array_t *array, int idx, void *data)
+{
+       if (!array)
+       {
+               return FALSE;
+       }
+       if (idx >= 0 && idx >= array_count(array))
+       {
+               return FALSE;
+       }
+       if (idx < 0)
+       {
+               if (array_count(array) == 0)
+               {
+                       return FALSE;
+               }
+               idx = array_count(array) - 1;
+       }
+       if (data)
+       {
+               memcpy(data, array->data + get_size(array, array->head + idx),
+                          get_size(array, 1));
+       }
+       if (idx > array_count(array) / 2)
+       {
+               remove_tail(array, idx);
+       }
+       else
+       {
+               remove_head(array, idx);
+       }
+       if (array->head + array->tail > ARRAY_MAX_UNUSED)
+       {
+               array_compress(array);
+       }
+       return TRUE;
+}
+
+void array_invoke(array_t *array, array_callback_t cb, void *user)
+{
+       if (array)
+       {
+               void *obj;
+               int i;
+
+               for (i = array->head; i < array->count + array->head; i++)
+               {
+                       obj = array->data + get_size(array, i);
+                       if (!array->esize)
+                       {
+                               /* dereference if we store store pointers */
+                               obj = *(void**)obj;
+                       }
+                       cb(obj, i - array->head, user);
+               }
+       }
+}
+
+void array_invoke_offset(array_t *array, size_t offset)
+{
+       if (array)
+       {
+               void (*method)(void *data);
+               void *obj;
+               int i;
+
+               for (i = array->head; i < array->count + array->head; i++)
+               {
+                       obj = array->data + get_size(array, i);
+                       if (!array->esize)
+                       {
+                               /* dereference if we store store pointers */
+                               obj = *(void**)obj;
+                       }
+                       method = *(void**)(obj + offset);
+                       method(obj);
+               }
+       }
+}
+
+void array_destroy(array_t *array)
+{
+       if (array)
+       {
+               free(array->data);
+               free(array);
+       }
+}
+
+void array_destroy_function(array_t *array, array_callback_t cb, void *user)
+{
+       array_invoke(array, cb, user);
+       array_destroy(array);
+}
+
+void array_destroy_offset(array_t *array, size_t offset)
+{
+       array_invoke_offset(array, offset);
+       array_destroy(array);
+}
diff --git a/src/libstrongswan/collections/array.h b/src/libstrongswan/collections/array.h
new file mode 100644 (file)
index 0000000..3e6180b
--- /dev/null
@@ -0,0 +1,194 @@
+/*
+ * Copyright (C) 2013 Martin Willi
+ * Copyright (C) 2013 revosec AG
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * for more details.
+ */
+
+/**
+ * @defgroup array array
+ * @{ @ingroup collections
+ */
+
+#ifndef ARRAY_H_
+#define ARRAY_H_
+
+#include <collections/enumerator.h>
+
+/**
+ * Variable sized array with fixed size elements.
+ *
+ * An array is a primitive object with associated functions to avoid the
+ * overhead of an object with methods. It is efficient in memory usage, but
+ * less effecient than a linked list in manipulating elements.
+ */
+typedef struct array_t array_t;
+
+typedef enum array_idx_t array_idx_t;
+
+/**
+ * Special array index values for insert/remove.
+ */
+enum array_idx_t {
+       ARRAY_HEAD = 0,
+       ARRAY_TAIL = -1,
+};
+
+/**
+ * Callback function invoked for each array element.
+ *
+ * Data is a pointer to the array element. If this is a pointer based array,
+ * (esize is zero), data is the pointer itself.
+ *
+ * @param data                 pointer to array data, or the pointer itself
+ * @param idx                  array index
+ * @param user                 user data passed with callback
+ */
+typedef void (*array_callback_t)(void *data, int idx, void *user);
+
+/**
+ * Create a array instance.
+ *
+ * Elements get tight packed to each other. If any alignment is required, pass
+ * appropriate padding to each element. The reserved space does not affect
+ * array_count(), but just preallocates buffer space.
+ *
+ * @param esize                        element size for this array, use 0 for a pointer array
+ * @param reserve              number of items to allocate space for
+ * @return                             array instance
+ */
+array_t *array_create(u_int esize, u_int8_t reserve);
+
+/**
+ * Get the number of elements currently in the array.
+ *
+ * @return                             number of elements
+ */
+int array_count(array_t *array);
+
+/**
+ * Compress an array, remove unused head/tail space.
+ *
+ * @param array                        array to compress, or NULL
+ */
+void array_compress(array_t *array);
+
+/**
+ * Create an enumerator over an array.
+ *
+ * The enumerater enumerates directly over the array element (pass a pointer to
+ * element types), unless the array is pointer based. If zero is passed as
+ * element size during construction, the enumerator enumerates over the
+ * deferenced pointer values.
+ *
+ * @param array                        array to create enumerator for, or NULL
+ * @return                             enumerator, over elements or pointers
+ */
+enumerator_t* array_create_enumerator(array_t *array);
+
+/**
+ * Remove an element at enumerator position.
+ *
+ * @param array                        array to remove element in
+ * @param enumerator   enumerator position, from array_create_enumerator()
+ */
+void array_remove_at(array_t *array, enumerator_t *enumerator);
+
+/**
+ * Insert an element to an array.
+ *
+ * If the array is pointer based (esize = 0), the pointer itself is appended.
+ * Otherwise the element gets copied from the pointer.
+ * The idx must be either within array_count() or one above to append the item.
+ * Passing -1 has the same effect as passing array_count(), i.e. appends the
+ * item. It is always valid to pass idx 0 to prepend the item.
+ *
+ * @param array                        array to append element to
+ * @param idx                  index to insert item at
+ * @param data                 pointer to array element to copy
+ */
+void array_insert(array_t *array, int idx, void *data);
+
+/**
+ * Create an pointer based array if it does not exist, insert pointer.
+ *
+ * This is a convenience function for insert a pointer and implicitly
+ * create a pointer based array if array is NULL. Array is set the the newly
+ * created array, if any.
+ *
+ * @param array                        pointer to array reference, potentially NULL
+ * @param idx                  index to insert item at
+ * @param ptr                  pointer to append
+ */
+void array_insert_create(array_t **array, int idx, void *ptr);
+
+/**
+ * Insert all items from an enumerator to an array.
+ *
+ * @param array                        array to add items to
+ * @param idx                  index to insert each item with
+ * @param enumerator   enumerator over void*, gets destroyed
+ */
+void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator);
+
+/**
+ * Remove an element from the array end.
+ *
+ * If data is given, the element is copied to that position.
+ *
+ * @param array                        array to remove element from, or NULL
+ * @param data                 data to copy element to, or NULL
+ * @return                             TRUE if idx existed and item removed
+ */
+bool array_remove(array_t *array, int idx, void *data);
+
+/**
+ * Invoke a callback for all array members.
+ *
+ * @param array                        array to traverse, or NULL
+ * @param cb                   callback function to invoke each element with
+ * @param user                 user data to pass to callback
+ */
+void array_invoke(array_t *array, array_callback_t cb, void *user);
+
+/**
+ * Invoke a method of each element defined with offset.
+ *
+ * @param array                        array to traverse, or NULL
+ * @param offset               offset of element method, use offsetof()
+ */
+void array_invoke_offset(array_t *array, size_t offset);
+
+/**
+ * Destroy an array.
+ *
+ * @param array                        array to destroy, or NULL
+ */
+void array_destroy(array_t *array);
+
+/**
+ * Destroy an array, call a function to clean up all elements.
+ *
+ * @param array                        array to destroy, or NULL
+ * @param cb                   callback function to free element data
+ * @param user                 user data to pass to callback
+ */
+void array_destroy_function(array_t *array, array_callback_t cb, void *user);
+
+/**
+ * Destroy an array, call element method defined with offset.
+ *
+ * @param array                        array to destroy, or NULL
+ * @param offset               offset of element method, use offsetof()
+ */
+void array_destroy_offset(array_t *array, size_t offset);
+
+#endif /** ARRAY_H_ @}*/