[PATCH] Introduce fast object pool for image objects (mallocectomy).

[Jonathan Morton]

NB: This falls back to plain malloc() calls on platforms not explicitly supported.
This patch only explicitly supports recent ARM platforms.
Support for PowerPC and x86-family machines would be beneficial.
---
 pixman/pixman-image.c   |   16 +++-
 pixman/pixman-ptrpool.h |  278 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 292 insertions(+), 2 deletions(-)
 create mode 100644 pixman/pixman-ptrpool.h

diff --git a/pixman/pixman-image.c b/pixman/pixman-image.c
index e95cff2..9ce0451 100644
--- a/pixman/pixman-image.c
+++ b/pixman/pixman-image.c
@@ -30,6 +30,7 @@
 #include <assert.h>
 
 #include "pixman-private.h"
+#include "pixman-ptrpool.h"
 
 #define Alpha(x) ((x) >> 24)
 
@@ -88,10 +89,21 @@ _pixman_image_get_scanline_64_generic (pixman_image_t * pict, int x, int y, int
     free(mask8);
 }
 
+static pixman_ptrpool_t* imagePool = NULL;
+
 pixman_image_t *
 _pixman_image_allocate (void)
 {
-    pixman_image_t *image = malloc (sizeof (pixman_image_t));
+    pixman_image_t *image = NULL;
+
+	if(!imagePool) {
+		imagePool = malloc(sizeof(*imagePool));
+		if(!imagePool)
+			return NULL;
+		pixman_ptrpool_init(imagePool, sizeof(*image));
+	}
+
+	image = pixman_ptrpool_fetch(imagePool);
 
     if (image)
     {
@@ -225,7 +237,7 @@ pixman_image_unref (pixman_image_t *image)
 	if (image->type == BITS && image->bits.free_me)
 	    free (image->bits.free_me);
 
-	free (image);
+	pixman_ptrpool_release(imagePool, image);
 
 	return TRUE;
     }
diff --git a/pixman/pixman-ptrpool.h b/pixman/pixman-ptrpool.h
new file mode 100644
index 0000000..a18d722
--- /dev/null
+++ b/pixman/pixman-ptrpool.h
@@ -0,0 +1,278 @@
+/*
+ * Copyright © 2009 Movial Creative Technologies Oy
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of SuSE not be used in advertising or
+ * publicity pertaining to distribution of the software without specific,
+ * written prior permission.  SuSE makes no representations about the
+ * suitability of this software for any purpose.  It is provided "as is"
+ * without express or implied warranty.
+ *
+ * SuSE DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL SuSE
+ * BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Author: Jonathan Morton <jonathan.morton at movial.com>
+ */
+
+#ifndef PIXMAN_PTRPOOL_H
+#define PIXMAN_PTRPOOL_H 1
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <stdio.h>
+
+/*
+ * Fast, thread-safe object-pool implementation.
+ * Strategy: fast atomic operations are provided for specific CPUs.
+ * Platforms not directly supported just call malloc().
+ *
+ * Supported platform list:  (add as required)
+ * - ARMv6 (GCC & armcc)
+ */
+
+// void* pixman_atomic_fetch_reset(void** place)
+//
+// If *place is non-zero, atomically resets it to zero while returning original value.
+// If *place is zero, returns zero while leaving *place at zero.
+// If contention invalidates the result, return zero.
+// Does not spin or iterate.
+//
+// Possible implementation #1 (x86):
+// tmp = *place; if(cmpxchg(place, tmp, NULL) == success) return tmp;
+// Possible implementation #2 (RISC):
+// tmp = ldrex(place); if(!tmp) return NULL; if(strex(place, NULL) == failure) return NULL; return tmp;
+
+#if USE_ARM_SIMD
+#if USE_GCC_INLINE_ASM
+
+#define PIXMAN_POOL_IMPLEMENTED 1
+
+static inline void* pixman_atomic_fetch_reset(void** place)
+{
+	void* out = NULL;
+	uint32_t tmp1 = 0, tmp2 = 0;
+
+	asm volatile (
+	"	ldrex   %[out], [%[place]]          \n"
+	"	cmp     %[out], #0                  \n"
+	"	strexne %[tmp1], %[tmp2], [%[place]]\n"
+	"	cmp     %[tmp1], #0                 \n"
+	"	movne   %[out], #0                  \n"
+	: [out] "+&r" (out), [tmp1] "+&r" (tmp1)
+	: [place] "r" (place), [tmp2] "r" (tmp2)
+	: "cc"
+	);
+
+	return out;
+}
+
+#elif defined(__ARMCC_VERSION)
+
+#define PIXMAN_POOL_IMPLEMENTED 1
+
+static inline void* pixman_atomic_fetch_reset(void** place)
+{
+	void* out = (void*) __ldrex(place);
+
+	if(out)
+		if(__strex(0, place))
+			return NULL;
+
+	return out;
+}
+
+#endif  // ! USE_GCC_INLINE_ASM
+#endif  // USE_ARM_SIMD
+
+// bool pixman_atomic_store_in_empty(void** place, void* item)
+//
+// If *place is zero, atomically fill it with item and return true.
+// Otherwise return false, leaving *place untouched.
+// If contention interferes, return false and leave *place untouched.
+// Does not spin or iterate.
+//
+// Possible implementation #1 (x86):
+// return cmpxchg(place, NULL, item) == success;
+// Possible implementation #2 (RISC):
+// if(ldrex(place)) return false; return strex(place, item) == success;
+
+#if USE_ARM_SIMD
+#if USE_GCC_INLINE_ASM
+
+static inline int pixman_atomic_store_in_empty(void** place, void* item)
+{
+	int tmp = 0;
+
+	asm volatile (
+	"	ldrex   %[tmp], [%[place]]          \n"
+	"	cmp     %[tmp], #0                  \n"
+	"	movne   %[tmp], #1                  \n"
+	"	strexeq %[tmp], %[item], [%[place]] \n"
+	"	rsb     %[tmp], %[tmp], #1          \n"
+	: [tmp] "=&r" (tmp)
+	: [item] "r" (item), [place] "r" (place)
+	: "cc"
+	);
+
+	return tmp;
+}
+
+#elif defined(__ARMCC_VERSION)
+
+static inline int pixman_atomic_store_in_empty(void** place, void* item)
+{
+	if(__ldrex(place))
+		return 0;
+
+	return !__strex((uint32_t) item, place);
+}
+
+#endif  // ! USE_GCC_INLINE_ASM
+#endif  // USE_ARM_SIMD
+
+
+#ifndef PIXMAN_POOL_IMPLEMENTED
+#define PIXMAN_NO_POOL 1
+#endif
+
+#if PIXMAN_NO_POOL
+
+/*
+ * Don't get stuck on the roof.
+ * These generic versions should be no slower than just calling malloc() directly.
+ */
+
+typedef struct { size_t size; } pixman_ptrpool_t;
+
+static inline void pixman_ptrpool_init(pixman_ptrpool_t* pool, size_t size)
+{
+	pool->size = size;
+}
+
+static inline void pixman_ptrpool_destroy(pixman_ptrpool_t* pool)
+{
+	pool=pool;
+}
+
+static inline void* pixman_ptrpool_fetch(pixman_ptrpool_t* pool)
+{
+	return malloc(pool->size);
+}
+
+static inline void pixman_ptrpool_release(pixman_ptrpool_t* pool, void* ptr)
+{
+	pool=pool;
+	free(ptr);
+}
+
+#else
+
+/*
+ * The "porcelain" part of the fast implementation.
+ * This should be used for all optimised implementations.
+ */
+
+#define PIXMAN_POOL_SIZE (4)
+
+typedef struct
+{
+	void *pool[PIXMAN_POOL_SIZE];
+	size_t size;
+	int top;
+} pixman_ptrpool_t;
+
+/*
+ * The init() and destroy() methods need not be thread-safe.
+ */
+
+static inline void pixman_ptrpool_init(pixman_ptrpool_t* pool, size_t size)
+{
+	memset(pool, 0, sizeof(*pool));
+	pool->size = size;
+}
+
+static inline void pixman_ptrpool_destroy(pixman_ptrpool_t* pool)
+{
+	int i;
+
+	for(i=0; i < PIXMAN_POOL_SIZE; i++)
+		if(pool->pool[i])
+			free(pool->pool[i]);
+
+	memset(pool, 0, sizeof(*pool));
+}
+
+/*
+ * The fetch() and release() methods use the atomic "plumbing" operations
+ * defined above to become thread-safe.
+ */
+
+static inline void* pixman_ptrpool_fetch(pixman_ptrpool_t* pool)
+{
+	int i = pool->top-1;
+	void* p;
+
+	if(i < 0) i = 0;
+
+	// fast path first
+	// ideally the pool is used as a bottom-up stack
+	p = pixman_atomic_fetch_reset(&(pool->pool[i]));
+	if(p) {
+		pool->top = i;
+		return p;
+	}
+
+	// either the pool is empty, or contention has broken the fastpath
+	// search the whole pool instead
+	for(i = PIXMAN_POOL_SIZE-1; i >= 0; i--) {
+		p = pixman_atomic_fetch_reset(&(pool->pool[i]));
+		if(p) {
+			pool->top = i;
+			return p;
+		}
+	}
+
+	// the pool is empty
+	pool->top = 0;
+	p = malloc(pool->size);
+	return p;
+}
+
+static inline void pixman_ptrpool_release(pixman_ptrpool_t* pool, void* ptr)
+{
+	// NB: the 'top' pointer is non-critical and can therefore be accessed with less care
+	int i = pool->top;
+
+	// fast path first
+	// ideally the pool is used as a bottom-up stack
+	if(pixman_atomic_store_in_empty(&(pool->pool[i]), ptr)) {
+		pool->top = i+1;
+		return;
+	}
+
+	// either the pool is full, or contention has broken the fastpath
+	// search for a free space
+	for(i=0; i < PIXMAN_POOL_SIZE; i++) {
+		if(pixman_atomic_store_in_empty(&(pool->pool[i]), ptr)) {
+			pool->top = i+1;
+			return;
+		}
+	}
+
+	// the pool is full
+	pool->top = PIXMAN_POOL_SIZE;
+	free(ptr);
+}
+
+#endif  // !PIXMAN_NO_POOL
+
+#endif  // !PIXMAN_PTRPOOL_H
-- 
1.5.6.3


--=-by6jJzXI0j1mDgcsBTPS--