Memory pools refactoring.

1 files changed, 890 insertions, 0 deletions

diff --git a/src/nxt_mp.c b/src/nxt_mp.c
new file mode 100644
index 00000000..aa6776b5
--- /dev/null
+++ b/src/nxt_mp.c
@@ -0,0 +1,890 @@
+
+/*
+ * Copyright (C) Igor Sysoev
+ * Copyright (C) NGINX, Inc.
+ */
+
+#include <nxt_main.h>
+
+
+/*
+ * A memory pool allocates memory in clusters of specified size and aligned
+ * to page_alignment.  A cluster is divided on pages of specified size.  Page
+ * size must be a power of 2.  A page can be used entirely or can be divided
+ * on chunks of equal size.  Chunk size must be a power of 2.  Non-freeable
+ * memory is also allocated from pages.  A cluster can contains a mix of pages
+ * with different chunk sizes and non-freeable pages.  Cluster size must be
+ * a multiple of page size and may be not a power of 2.  Allocations greater
+ * than page are allocated outside clusters.  Start addresses and sizes of
+ * the clusters and large allocations are stored in rbtree blocks to find
+ * them on free operations.  The rbtree nodes are sorted by start addresses.
+ * The rbtree is also used to destroy memory pool.
+ */
+
+
+typedef struct {
+    /*
+     * Used to link
+     *  *) pages with free chunks in pool chunk pages lists,
+     *  *) pages with free space for non-freeable allocations,
+     *  *) free pages in clusters.
+     */
+    nxt_queue_link_t     link;
+
+    union {
+        /* Chunk bitmap.  There can be no more than 32 chunks in a page. */
+        uint32_t         map;
+
+        /* Size of taken non-freeable space. */
+        uint32_t         taken;
+    } u;
+
+    /*
+     * Size of chunks or page shifted by pool->chunk_size_shift.  Zero means
+     * that page is free, 0xFF means page with non-freeable allocations.
+     */
+    uint8_t              size;
+
+    /* Number of free chunks of a chunked page. */
+    uint8_t              chunks;
+
+    /*
+     * Number of allocation fails due to free space insufficiency
+     * in non-freeable page.
+     */
+    uint8_t              fails;
+
+    /*
+     * Page number in page cluster.
+     * There can be no more than 256 pages in a cluster.
+     */
+    uint8_t              number;
+} nxt_mp_page_t;
+
+
+/*
+ * Some malloc implementations (e.g. jemalloc) allocates large enough
+ * blocks (e.g. greater than 4K) with 4K alignment.  So if a block
+ * descriptor will be allocated together with the block it will take
+ * excessive 4K memory.  So it is better to allocate the block descriptor
+ * apart.
+ */
+
+typedef enum {
+    /* Block of cluster.  The block is allocated apart of the cluster. */
+    NXT_MP_CLUSTER_BLOCK = 0,
+    /*
+     * Block of large allocation.
+     * The block is allocated apart of the allocation.
+     */
+    NXT_MP_DISCRETE_BLOCK,
+    /*
+     * Block of large allocation.
+     * The block is allocated just after of the allocation.
+     */
+    NXT_MP_EMBEDDED_BLOCK,
+} nxt_mp_block_type_t;
+
+
+typedef struct {
+    NXT_RBTREE_NODE      (node);
+    nxt_mp_block_type_t  type:8;
+
+    /* Block size must be less than 4G. */
+    uint32_t             size;
+
+    u_char               *start;
+    nxt_mp_page_t        pages[];
+} nxt_mp_block_t;
+
+
+struct nxt_mp_s {
+    /* rbtree of nxt_mp_block_t. */
+    nxt_rbtree_t         blocks;
+
+    uint8_t              chunk_size_shift;
+    uint8_t              page_size_shift;
+    uint32_t             page_size;
+    uint32_t             page_alignment;
+    uint32_t             cluster_size;
+    uint32_t             retain;
+
+    /* Lists of nxt_mp_page_t. */
+    nxt_queue_t          free_pages;
+    nxt_queue_t          nget_pages;
+    nxt_queue_t          get_pages;
+    nxt_queue_t          chunk_pages[0];
+};
+
+
+#define nxt_mp_chunk_get_free(map)                                            \
+    (__builtin_ffs(map) - 1)
+
+
+#define nxt_mp_chunk_is_free(map, chunk)                                      \
+    ((map & (1 << chunk)) != 0)
+
+
+#define nxt_mp_chunk_set_busy(map, chunk)                                     \
+    map &= ~(1 << chunk)
+
+
+#define nxt_mp_chunk_set_free(map, chunk)                                     \
+    map |= (1 << chunk)
+
+
+#define nxt_mp_free_junk(p, size)                                             \
+    memset((p), 0x5A, size)
+
+
+#if !(NXT_DEBUG_MEMORY)
+static void *nxt_mp_get_small(nxt_mp_t *mp, nxt_queue_t *pages, size_t size);
+static void *nxt_mp_alloc_small(nxt_mp_t *mp, size_t size);
+static nxt_mp_page_t *nxt_mp_alloc_page(nxt_mp_t *mp);
+static nxt_mp_block_t *nxt_mp_alloc_cluster(nxt_mp_t *mp);
+#endif
+static void *nxt_mp_alloc_large(nxt_mp_t *mp, size_t alignment, size_t size);
+static intptr_t nxt_mp_rbtree_compare(nxt_rbtree_node_t *node1,
+    nxt_rbtree_node_t *node2);
+static nxt_mp_block_t *nxt_mp_find_block(nxt_rbtree_t *tree, u_char *p);
+static const char *nxt_mp_chunk_free(nxt_mp_t *mp, nxt_mp_block_t *cluster,
+    u_char *p);
+
+
+nxt_mp_t *
+nxt_mp_create(size_t cluster_size, size_t page_alignment, size_t page_size,
+    size_t min_chunk_size)
+{
+    nxt_mp_t     *mp;
+    nxt_uint_t   pages, chunk_size;
+    nxt_queue_t  *chunk_pages;
+
+    pages = 0;
+    chunk_size = page_size;
+
+    do {
+        pages++;
+        chunk_size /= 2;
+    } while (chunk_size > min_chunk_size);
+
+    mp = nxt_zalloc(sizeof(nxt_mp_t) + pages * sizeof(nxt_queue_t));
+
+    if (nxt_fast_path(mp != NULL)) {
+        mp->retain = 1;
+        mp->page_size = page_size;
+        mp->page_alignment = nxt_max(page_alignment, NXT_MAX_ALIGNMENT);
+        mp->cluster_size = cluster_size;
+
+        chunk_pages = mp->chunk_pages;
+
+        do {
+            nxt_queue_init(chunk_pages);
+            chunk_pages++;
+            chunk_size *= 2;
+        } while (chunk_size < page_size);
+
+        mp->chunk_size_shift = nxt_lg2(min_chunk_size);
+        mp->page_size_shift = nxt_lg2(page_size);
+
+        nxt_rbtree_init(&mp->blocks, nxt_mp_rbtree_compare);
+
+        nxt_queue_init(&mp->free_pages);
+    }
+
+    return mp;
+}
+
+
+void
+nxt_mp_destroy(nxt_mp_t *mp)
+{
+    void               *p;
+    nxt_mp_block_t     *block;
+    nxt_rbtree_node_t  *node, *next;
+
+    nxt_debug_alloc("mp destroy");
+
+    next = nxt_rbtree_root(&mp->blocks);
+
+    while (next != nxt_rbtree_sentinel(&mp->blocks)) {
+
+        node = nxt_rbtree_destroy_next(&mp->blocks, &next);
+        block = (nxt_mp_block_t *) node;
+
+        p = block->start;
+
+        if (block->type != NXT_MP_EMBEDDED_BLOCK) {
+            nxt_free(block);
+        }
+
+        nxt_free(p);
+    }
+
+    nxt_free(mp);
+}
+
+
+nxt_bool_t
+nxt_mp_test_sizes(size_t cluster_size, size_t page_alignment, size_t page_size,
+    size_t min_chunk_size)
+{
+    nxt_bool_t  valid;
+
+    /* Alignment and sizes must be a power of 2. */
+
+    valid = nxt_expect(1, (nxt_is_power_of_two(page_alignment)
+                           && nxt_is_power_of_two(page_size)
+                           && nxt_is_power_of_two(min_chunk_size)));
+    if (!valid) {
+        return 0;
+    }
+
+    page_alignment = nxt_max(page_alignment, NXT_MAX_ALIGNMENT);
+
+    valid = nxt_expect(1, (page_size >= 64
+                           && page_size >= page_alignment
+                           && page_size >= min_chunk_size
+                           && min_chunk_size * 32 >= page_size
+                           && cluster_size >= page_size
+                           && cluster_size / page_size <= 256
+                           && cluster_size % page_size == 0));
+    if (!valid) {
+        return 0;
+    }
+
+    return 1;
+}
+
+
+nxt_bool_t
+nxt_mp_is_empty(nxt_mp_t *mp)
+{
+    return (nxt_rbtree_is_empty(&mp->blocks)
+            && nxt_queue_is_empty(&mp->free_pages));
+}
+
+
+void *
+nxt_mp_alloc(nxt_mp_t *mp, size_t size)
+{
+    nxt_debug_alloc("mp alloc: %uz", size);
+
+#if !(NXT_DEBUG_MEMORY)
+
+    if (size <= mp->page_size) {
+        return nxt_mp_alloc_small(mp, size);
+    }
+
+#endif
+
+    return nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size);
+}
+
+
+void *
+nxt_mp_zalloc(nxt_mp_t *mp, size_t size)
+{
+    void  *p;
+
+    p = nxt_mp_alloc(mp, size);
+
+    if (nxt_fast_path(p != NULL)) {
+        memset(p, 0, size);
+    }
+
+    return p;
+}
+
+
+void *
+nxt_mp_align(nxt_mp_t *mp, size_t alignment, size_t size)
+{
+    nxt_debug_alloc("mp align: @%uz:%uz", alignment, size);
+
+    /* Alignment must be a power of 2. */
+
+    if (nxt_fast_path(nxt_is_power_of_two(alignment))) {
+
+#if !(NXT_DEBUG_MEMORY)
+
+        if (size <= mp->page_size && alignment <= mp->page_alignment) {
+            size = nxt_max(size, alignment);
+
+            if (size <= mp->page_size) {
+                return nxt_mp_alloc_small(mp, size);
+            }
+        }
+
+#endif
+
+        return nxt_mp_alloc_large(mp, alignment, size);
+    }
+
+    return NULL;
+}
+
+
+void *
+nxt_mp_zalign(nxt_mp_t *mp, size_t alignment, size_t size)
+{
+    void  *p;
+
+    p = nxt_mp_align(mp, alignment, size);
+
+    if (nxt_fast_path(p != NULL)) {
+        memset(p, 0, size);
+    }
+
+    return p;
+}
+
+
+#if !(NXT_DEBUG_MEMORY)
+
+nxt_inline u_char *
+nxt_mp_page_addr(nxt_mp_t *mp, nxt_mp_page_t *page)
+{
+    size_t          page_offset;
+    nxt_mp_block_t  *block;
+
+    page_offset = page->number * sizeof(nxt_mp_page_t)
+                  + offsetof(nxt_mp_block_t, pages);
+
+    block = (nxt_mp_block_t *) ((u_char *) page - page_offset);
+
+    return block->start + (page->number << mp->page_size_shift);
+}
+
+
+nxt_inline nxt_uint_t
+nxt_mp_chunk_pages_index(nxt_mp_t *mp, size_t size)
+{
+    nxt_int_t  n, index;
+
+    index = 0;
+
+    if (size > 1) {
+        n = nxt_lg2(size - 1) + 1 - mp->chunk_size_shift;
+
+        if (n > 0) {
+            index = n;
+        }
+    }
+
+    return index;
+}
+
+
+static void *
+nxt_mp_alloc_small(nxt_mp_t *mp, size_t size)
+{
+    u_char            *p;
+    nxt_uint_t        n, index;
+    nxt_queue_t       *chunk_pages;
+    nxt_mp_page_t     *page;
+    nxt_queue_link_t  *link;
+
+    p = NULL;
+
+    if (size <= mp->page_size / 2) {
+
+        index = nxt_mp_chunk_pages_index(mp, size);
+        chunk_pages = &mp->chunk_pages[index];
+
+        if (nxt_fast_path(!nxt_queue_is_empty(chunk_pages))) {
+
+            link = nxt_queue_first(chunk_pages);
+            page = nxt_queue_link_data(link, nxt_mp_page_t, link);
+
+            p = nxt_mp_page_addr(mp, page);
+
+            n = nxt_mp_chunk_get_free(page->u.map);
+            nxt_mp_chunk_set_busy(page->u.map, n);
+
+            p += ((n << index) << mp->chunk_size_shift);
+
+            page->chunks--;
+
+            if (page->chunks == 0) {
+                /*
+                 * Remove full page from the pool chunk pages list
+                 * of pages with free chunks.
+                 */
+                nxt_queue_remove(&page->link);
+            }
+
+        } else {
+            page = nxt_mp_alloc_page(mp);
+
+            if (nxt_fast_path(page != NULL)) {
+                page->size = (1 << index);
+
+                n = mp->page_size_shift - (index + mp->chunk_size_shift);
+                page->chunks = (1 << n) - 1;
+
+                nxt_queue_insert_head(chunk_pages, &page->link);
+
+                /* Mark the first chunk as busy. */
+                page->u.map = 0xFFFFFFFE;
+
+                p = nxt_mp_page_addr(mp, page);
+            }
+        }
+
+    } else {
+        page = nxt_mp_alloc_page(mp);
+
+        if (nxt_fast_path(page != NULL)) {
+            page->size = mp->page_size >> mp->chunk_size_shift;
+
+            p = nxt_mp_page_addr(mp, page);
+        }
+    }
+
+    nxt_debug_alloc("mp chunk:%uz alloc: %p",
+                    page->size << mp->chunk_size_shift, p);
+
+    return p;
+}
+
+
+static nxt_mp_page_t *
+nxt_mp_alloc_page(nxt_mp_t *mp)
+{
+    nxt_mp_page_t     *page;
+    nxt_mp_block_t    *cluster;
+    nxt_queue_link_t  *link;
+
+    if (nxt_queue_is_empty(&mp->free_pages)) {
+        cluster = nxt_mp_alloc_cluster(mp);
+        if (nxt_slow_path(cluster == NULL)) {
+            return NULL;
+        }
+    }
+
+    link = nxt_queue_first(&mp->free_pages);
+    nxt_queue_remove(link);
+
+    page = nxt_queue_link_data(link, nxt_mp_page_t, link);
+
+    return page;
+}
+
+
+static nxt_mp_block_t *
+nxt_mp_alloc_cluster(nxt_mp_t *mp)
+{
+    nxt_uint_t      n;
+    nxt_mp_block_t  *cluster;
+
+    n = mp->cluster_size >> mp->page_size_shift;
+
+    cluster = nxt_zalloc(sizeof(nxt_mp_block_t) + n * sizeof(nxt_mp_page_t));
+
+    if (nxt_slow_path(cluster == NULL)) {
+        return NULL;
+    }
+
+    /* NXT_MP_CLUSTER_BLOCK type is zero. */
+
+    cluster->size = mp->cluster_size;
+
+    cluster->start = nxt_memalign(mp->page_alignment, mp->cluster_size);
+    if (nxt_slow_path(cluster->start == NULL)) {
+        nxt_free(cluster);
+        return NULL;
+    }
+
+    n--;
+    cluster->pages[n].number = n;
+    nxt_queue_insert_head(&mp->free_pages, &cluster->pages[n].link);
+
+    while (n != 0) {
+        n--;
+        cluster->pages[n].number = n;
+        nxt_queue_insert_before(&cluster->pages[n + 1].link,
+                                &cluster->pages[n].link);
+    }
+
+    nxt_rbtree_insert(&mp->blocks, &cluster->node);
+
+    return cluster;
+}
+
+#endif
+
+
+static void *
+nxt_mp_alloc_large(nxt_mp_t *mp, size_t alignment, size_t size)
+{
+    u_char          *p;
+    size_t          aligned_size;
+    uint8_t         type;
+    nxt_mp_block_t  *block;
+
+    /* Allocation must be less than 4G. */
+    if (nxt_slow_path(size >= 0xFFFFFFFF)) {
+        return NULL;
+    }
+
+    if (nxt_is_power_of_two(size)) {
+        block = nxt_malloc(sizeof(nxt_mp_block_t));
+        if (nxt_slow_path(block == NULL)) {
+            return NULL;
+        }
+
+        p = nxt_memalign(alignment, size);
+        if (nxt_slow_path(p == NULL)) {
+            nxt_free(block);
+            return NULL;
+        }
+
+        type = NXT_MP_DISCRETE_BLOCK;
+
+    } else {
+        aligned_size = nxt_align_size(size, sizeof(uintptr_t));
+
+        p = nxt_memalign(alignment, aligned_size + sizeof(nxt_mp_block_t));
+        if (nxt_slow_path(p == NULL)) {
+            return NULL;
+        }
+
+        block = (nxt_mp_block_t *) (p + aligned_size);
+        type = NXT_MP_EMBEDDED_BLOCK;
+    }
+
+    block->type = type;
+    block->size = size;
+    block->start = p;
+
+    nxt_rbtree_insert(&mp->blocks, &block->node);
+
+    return p;
+}
+
+
+static intptr_t
+nxt_mp_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2)
+{
+    nxt_mp_block_t  *block1, *block2;
+
+    block1 = (nxt_mp_block_t *) node1;
+    block2 = (nxt_mp_block_t *) node2;
+
+    return (uintptr_t) block1->start - (uintptr_t) block2->start;
+}
+
+
+void
+nxt_mp_free(nxt_mp_t *mp, void *p)
+{
+    const char      *err;
+    nxt_thread_t    *thread;
+    nxt_mp_block_t  *block;
+
+    nxt_debug_alloc("mp free %p", p);
+
+    block = nxt_mp_find_block(&mp->blocks, p);
+
+    if (nxt_fast_path(block != NULL)) {
+
+        if (block->type == NXT_MP_CLUSTER_BLOCK) {
+            err = nxt_mp_chunk_free(mp, block, p);
+
+            if (nxt_fast_path(err == NULL)) {
+                return;
+            }
+
+        } else if (nxt_fast_path(p == block->start)) {
+            nxt_rbtree_delete(&mp->blocks, &block->node);
+
+            if (block->type == NXT_MP_DISCRETE_BLOCK) {
+                nxt_free(block);
+            }
+
+            nxt_free(p);
+
+            return;
+
+        } else {
+            err = "freed pointer points to middle of block: %p";
+        }
+
+    } else {
+        err = "freed pointer is out of pool: %p";
+    }
+
+    thread = nxt_thread();
+
+    nxt_log(thread->task, NXT_LOG_CRIT, err, p);
+}
+
+
+static nxt_mp_block_t *
+nxt_mp_find_block(nxt_rbtree_t *tree, u_char *p)
+{
+    nxt_mp_block_t     *block;
+    nxt_rbtree_node_t  *node, *sentinel;
+
+    node = nxt_rbtree_root(tree);
+    sentinel = nxt_rbtree_sentinel(tree);
+
+    while (node != sentinel) {
+
+        block = (nxt_mp_block_t *) node;
+
+        if (p < block->start) {
+            node = node->left;
+
+        } else if (p >= block->start + block->size) {
+            node = node->right;
+
+        } else {
+            return block;
+        }
+    }
+
+    return NULL;
+}
+
+
+static const char *
+nxt_mp_chunk_free(nxt_mp_t *mp, nxt_mp_block_t *cluster, u_char *p)
+{
+    u_char         *start;
+    uintptr_t      offset;
+    nxt_uint_t     n, size, chunk;
+    nxt_queue_t    *chunk_pages;
+    nxt_mp_page_t  *page;
+
+    n = (p - cluster->start) >> mp->page_size_shift;
+    start = cluster->start + (n << mp->page_size_shift);
+
+    page = &cluster->pages[n];
+
+    if (nxt_slow_path(page->size == 0)) {
+        return "freed pointer points to already free page: %p";
+    }
+
+    if (nxt_slow_path(page->size == 0xFF)) {
+        return "freed pointer points to non-freeble page: %p";
+    }
+
+    size = page->size << mp->chunk_size_shift;
+
+    if (size != mp->page_size) {
+
+        offset = (uintptr_t) (p - start) & (mp->page_size - 1);
+        chunk = offset / size;
+
+        if (nxt_slow_path(offset != chunk * size)) {
+            return "freed pointer points to wrong chunk: %p";
+        }
+
+        if (nxt_slow_path(nxt_mp_chunk_is_free(page->u.map, chunk))) {
+            return "freed pointer points to already free chunk: %p";
+        }
+
+        nxt_mp_chunk_set_free(page->u.map, chunk);
+
+        if (page->u.map != 0xFFFFFFFF) {
+            page->chunks++;
+
+            if (page->chunks == 1) {
+                /*
+                 * Add the page to the head of pool chunk pages list
+                 * of pages with free chunks.
+                 */
+                n = nxt_mp_chunk_pages_index(mp, size);
+                chunk_pages = &mp->chunk_pages[n];
+
+                nxt_queue_insert_head(chunk_pages, &page->link);
+            }
+
+            nxt_mp_free_junk(p, size);
+
+            return NULL;
+
+        } else {
+            /*
+             * All chunks are free, remove the page from pool
+             * chunk pages list of pages with free chunks.
+             */
+            nxt_queue_remove(&page->link);
+        }
+
+    } else if (nxt_slow_path(p != start)) {
+        return "invalid pointer to chunk: %p";
+    }
+
+    /* Add the free page to the pool's free pages tree. */
+
+    page->size = 0;
+    nxt_queue_insert_head(&mp->free_pages, &page->link);
+
+    nxt_mp_free_junk(p, size);
+
+    /* Test if all pages in the cluster are free. */
+
+    n = mp->cluster_size >> mp->page_size_shift;
+    page = cluster->pages;
+
+    do {
+         if (page->size != 0) {
+             return NULL;
+         }
+
+         page++;
+         n--;
+    } while (n != 0);
+
+    /* Free cluster. */
+
+    n = mp->cluster_size >> mp->page_size_shift;
+    page = cluster->pages;
+
+    do {
+         nxt_queue_remove(&page->link);
+         page++;
+         n--;
+    } while (n != 0);
+
+    nxt_rbtree_delete(&mp->blocks, &cluster->node);
+
+    p = cluster->start;
+
+    nxt_free(cluster);
+    nxt_free(p);
+
+    return NULL;
+}
+
+
+void *
+nxt_mp_retain(nxt_mp_t *mp, size_t size)
+{
+    void  *p;
+
+    p = nxt_mp_alloc(mp, size);
+
+    if (nxt_fast_path(p != NULL)) {
+        mp->retain++;
+        nxt_debug_alloc("mp retain: %uD", mp->retain);
+    }
+
+    return p;
+}
+
+
+void
+nxt_mp_release(nxt_mp_t *mp, void *p)
+{
+    nxt_mp_free(mp, p);
+
+    mp->retain--;
+
+    nxt_debug_alloc("mp release: %uD", mp->retain);
+
+    if (mp->retain == 0) {
+        nxt_mp_destroy(mp);
+    }
+}
+
+
+void *
+nxt_mp_nget(nxt_mp_t *mp, size_t size)
+{
+    nxt_debug_alloc("mp nget: %uz", size);
+
+#if !(NXT_DEBUG_MEMORY)
+
+    if (size <= mp->page_size) {
+        return nxt_mp_get_small(mp, &mp->nget_pages, size);
+    }
+
+#endif
+
+    return nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size);
+}
+
+
+void *
+nxt_mp_get(nxt_mp_t *mp, size_t size)
+{
+    nxt_debug_alloc("mp get: %uz", size);
+
+#if !(NXT_DEBUG_MEMORY)
+
+    if (size <= mp->page_size) {
+        size = nxt_max(size, NXT_MAX_ALIGNMENT);
+        return nxt_mp_get_small(mp, &mp->get_pages, size);
+    }
+
+#endif
+
+    return nxt_mp_alloc_large(mp, NXT_MAX_ALIGNMENT, size);
+}
+
+
+void *
+nxt_mp_zget(nxt_mp_t *mp, size_t size)
+{
+    void  *p;
+
+    p = nxt_mp_get(mp, size);
+
+    if (nxt_fast_path(p != NULL)) {
+        memset(p, 0, size);
+    }
+
+    return p;
+}
+
+
+static void *
+nxt_mp_get_small(nxt_mp_t *mp, nxt_queue_t *pages, size_t size)
+{
+    u_char            *p;
+    uint32_t          available;
+    nxt_mp_page_t     *page;
+    nxt_queue_link_t  *link, *next;
+
+    for (link = nxt_queue_first(pages);
+         link != nxt_queue_tail(pages);
+         link = next)
+    {
+        next = nxt_queue_next(link);
+        page = nxt_queue_link_data(link, nxt_mp_page_t, link);
+
+        available = mp->page_size - page->u.taken;
+
+        if (size <= available) {
+            goto found;
+        }
+
+        if (available == 0 || page->fails++ > 100) {
+            nxt_queue_remove(link);
+        }
+    }
+
+    page = nxt_mp_alloc_page(mp);
+
+    if (nxt_slow_path(page == NULL)) {
+        return page;
+    }
+
+    nxt_queue_insert_head(pages, &page->link);
+
+    page->size = 0xFF;
+
+found:
+
+    p = nxt_mp_page_addr(mp, page);
+
+    p += page->u.taken;
+    page->u.taken += size;
+
+    nxt_debug_alloc("mp get: %p", p);
+
+    return p;
+}