percu-allocator: Implement robust pool validation

When set, the RSEQ_POOL_ROBUST flag will add a bitmap to the pool which
is used to track double-free and allocation leaks in the pool.

Signed-off-by: Olivier Dion <odion@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Change-Id: I531782ee57d33c9704b9cca44af1a9464f60cb90

diff --git a/include/rseq/percpu-alloc.h b/include/rseq/percpu-alloc.h
index 5308d61fb7700a926dadab5bb3d49459f16b3ee1..6a1cd51f3e536f68141263ec9f82c7352063a512 100644 (file)
--- a/include/rseq/percpu-alloc.h
+++ b/include/rseq/percpu-alloc.h
@@ -43,6 +43,21 @@ extern "C" {
 struct rseq_mmap_attr;
 struct rseq_percpu_pool;
 
+/*
+ * Create a robust pool.  This enables the following runtime checks:
+ *
+ *   - Check for double free of pointers.
+ *
+ *   - Check that all items were freed when destroying the pool, i.e. no memory
+ *     leak.
+ *
+ *  There is a marginal runtime overhead on malloc/free operations.
+ *
+ *  The memory overhead is (pool->percpu_len / pool->item_len) / CHAR_BIT
+ *  bytes, over the lifetime of the pool.
+ */
+#define RSEQ_POOL_ROBUST    (1 << 0)
+
 /*
  * rseq_percpu_pool_create: Create a per-cpu memory pool.
  *
@@ -56,8 +71,8 @@ struct rseq_percpu_pool;
  * after rseq_percpu_pool_create() returns. The caller keeps ownership
  * of @mmap_attr.
  *
- * Argument @flags is currently expected to be 0. This is for future
- * extensions.
+ * Argument @flags is a bitwise-or'd selector of:
+ *   - RSEQ_POOL_ROBUST
  *
  * Returns a pointer to the created percpu pool. Return NULL on error,
  * with errno set accordingly:

diff --git a/src/rseq-percpu-alloc.c b/src/rseq-percpu-alloc.c
index 289ed8440212efcc3e0f348759c59a90366cf19d..3d756e324795c996f0be2b92d2d0202563cb1113 100644 (file)
--- a/src/rseq-percpu-alloc.c
+++ b/src/rseq-percpu-alloc.c
@@ -66,6 +66,10 @@
  */
 #define FIRST_POOL             1
 
+#define RSEQ_POOL_FLAGS                (RSEQ_POOL_ROBUST)
+
+#define BIT_PER_ULONG          (8 * sizeof(unsigned long))
+
 struct free_list_node;
 
 struct free_list_node {
@@ -102,6 +106,9 @@ struct rseq_percpu_pool {
        pthread_mutex_t lock;
 
        struct rseq_mmap_attr mmap_attr;
+
+       /* Tracks allocation where free slots are set to 0. */
+       unsigned long *free_bitmap;
 };
 
 //TODO: the array of pools should grow dynamically on create.
@@ -198,6 +205,39 @@ int default_munmap_func(void *priv __attribute__((unused)), void *ptr, size_t le
        return munmap(ptr, len);
 }
 
+static
+unsigned long *create_free_bitmap(size_t item_len)
+{
+       size_t count;
+
+       count = (item_len + BIT_PER_ULONG - 1) / BIT_PER_ULONG;
+
+       /*
+        * No need to check for NULL, since all paths using the free_bitmap will
+        * be NO OP in that case.
+        */
+       return calloc(count, sizeof(unsigned long));
+}
+
+static
+void destroy_free_bitmap(unsigned long *bitmap, size_t item_len)
+{
+       size_t count;
+
+       if (!bitmap) {
+               return;
+       }
+
+       count = (item_len + BIT_PER_ULONG - 1) / BIT_PER_ULONG;
+
+       /* Assert that all items in the pool were freed. */
+       for (size_t k = 0; k < count; ++k) {
+               assert(0 == bitmap[k]);
+       }
+
+       free(bitmap);
+}
+
 struct rseq_percpu_pool *rseq_percpu_pool_create(size_t item_len,
                size_t percpu_len, int max_nr_cpus,
                const struct rseq_mmap_attr *mmap_attr,
@@ -211,7 +251,7 @@ struct rseq_percpu_pool *rseq_percpu_pool_create(size_t item_len,
        unsigned int i;
        int order;
 
-       if (flags) {
+       if (flags & ~RSEQ_POOL_FLAGS) {
                errno = EINVAL;
                return NULL;
        }
@@ -273,6 +313,10 @@ found_empty:
        pool->mmap_attr.mmap_func = mmap_func;
        pool->mmap_attr.munmap_func = munmap_func;
        pool->mmap_attr.mmap_priv = mmap_priv;
+
+       if (RSEQ_POOL_ROBUST & flags) {
+               pool->free_bitmap = create_free_bitmap(percpu_len >> order);
+       }
 end:
        pthread_mutex_unlock(&pool_lock);
        return pool;
@@ -293,12 +337,33 @@ int rseq_percpu_pool_destroy(struct rseq_percpu_pool *pool)
        if (ret)
                goto end;
        pthread_mutex_destroy(&pool->lock);
+       destroy_free_bitmap(pool->free_bitmap,
+                           pool->percpu_len >> pool->item_order);
        memset(pool, 0, sizeof(*pool));
 end:
        pthread_mutex_unlock(&pool_lock);
        return 0;
 }
 
+static
+void mask_free_slot(unsigned long *bitmap, size_t item_index)
+{
+       unsigned long mask;
+       size_t k;
+
+       if (!bitmap) {
+               return;
+       }
+
+       k    = item_index / BIT_PER_ULONG;
+       mask = 1ULL << (item_index % BIT_PER_ULONG);
+
+       /* Assert that the item is free. */
+       assert(0 == (bitmap[k] & mask));
+
+       bitmap[k] |= mask;
+}
+
 static
 void __rseq_percpu *__rseq_percpu_malloc(struct rseq_percpu_pool *pool, bool zeroed)
 {
@@ -324,6 +389,7 @@ void __rseq_percpu *__rseq_percpu_malloc(struct rseq_percpu_pool *pool, bool zer
        item_offset = pool->next_unused;
        addr = (void *) (((uintptr_t) pool->index << POOL_INDEX_SHIFT) | item_offset);
        pool->next_unused += pool->item_len;
+       mask_free_slot(pool->free_bitmap, item_offset >> pool->item_order);
 end:
        pthread_mutex_unlock(&pool->lock);
        if (zeroed && addr)
@@ -341,6 +407,25 @@ void __rseq_percpu *rseq_percpu_zmalloc(struct rseq_percpu_pool *pool)
        return __rseq_percpu_malloc(pool, true);
 }
 
+static
+void unmask_free_slot(unsigned long *bitmap, size_t item_index)
+{
+       unsigned long mask;
+       size_t k;
+
+       if (!bitmap) {
+               return;
+       }
+
+       k    = item_index / BIT_PER_ULONG;
+       mask = 1 << (item_index % BIT_PER_ULONG);
+
+       /* Assert that the item is not free. */
+       assert(mask == (bitmap[k] & mask));
+
+       bitmap[k] &= ~mask;
+}
+
 void rseq_percpu_free(void __rseq_percpu *_ptr)
 {
        uintptr_t ptr = (uintptr_t) _ptr;
@@ -350,6 +435,7 @@ void rseq_percpu_free(void __rseq_percpu *_ptr)
        struct free_list_node *head, *item;
 
        pthread_mutex_lock(&pool->lock);
+       unmask_free_slot(pool->free_bitmap, item_offset >> pool->item_order);
        /* Add ptr to head of free list */
        head = pool->free_list_head;
        /* Free-list is in CPU 0 range. */