[PATCH] Core: merge adjacent free slab pages to ameliorate fragmentation from multi-page blocks (Was Re: Help with shared memory usage)

[Maxim Dounin]

Hello!

On Sun, May 11, 2014 at 10:13:52PM -0700, Yichun Zhang (agentzh) wrote:

> Hello!
> 
> On Mon, Jul 29, 2013 at 10:11 AM, Maxim Dounin wrote:
> > Additionally, doing a full merge of all free blocks on a free
> > operation looks too much.  It might be something we want to do on
> > allocation failure, but not on a normal path in
> > ngx_slab_free_pages().  And/or something lightweight may be done
> > in ngx_slab_free_pages(), e.g., checking if pages following pages
> > we are freeing are free too, and merging them in this case.
> >
> 
> I'd propose an alternative patch taking the second approach, that is,
> merging adjacent free pages (for both the previous and next blocks) in
> ngx_slab_free_pages(). This approach has the following advantages:
> 
> 1. It can effectively distribute the merging computations across all
> the page free operations, which can prevent potential frequent and
> long stalls when actually running out of large enough free blocks
> along the "free" list that is already very long for large zones (which
> usually consists of  tons of one-page blocks upon allocation
> failures).
> 
> 2. it can also make multi-page allocations generally faster because
> we're merging pages immediately when we can and thus it's more likely
> to find large enough free blocks along the (relatively short) free
> list for ngx_slab_alloc_pages().
> 
> The only downside is that I have to introduce an extra field
> "prev_slab" (8-byte for x86_64) in ngx_slab_page_t in my patch, which
> makes the slab page metadata a bit larger.

Below is a patch which does mostly the same without introducing 
any additional per-page fields.  Please take a look if it works 
for you.

# HG changeset patch
# User Maxim Dounin <mdounin at mdounin.ru>
# Date 1401302011 -14400
#      Wed May 28 22:33:31 2014 +0400
# Node ID 7fb45c6042324e6cd92b0fb230c67a9c8c75681c
# Parent  80bd391c90d11de707a05fcd0c9aa2a09c62877f
Core: slab allocator defragmentation.

Large allocations from a slab pool result in free page blocks being fragmented,
eventually leading to a situation when no further allocation larger than a page
size are possible from the pool.  While this isn't a problem for nginx itself,
it is known to be bad for various 3rd party modules.  Fix is to merge adjacent
blocks of free pages in the ngx_slab_free_pages() function.

Prodded by Wandenberg Peixoto and Yichun Zhang.

diff --git a/src/core/ngx_slab.c b/src/core/ngx_slab.c
--- a/src/core/ngx_slab.c
+++ b/src/core/ngx_slab.c
@@ -129,6 +129,8 @@ ngx_slab_init(ngx_slab_pool_t *pool)
         pool->pages->slab = pages;
     }
 
+    pool->last = pool->pages + pages;
+
     pool->log_nomem = 1;
     pool->log_ctx = &pool->zero;
     pool->zero = '\0';
@@ -626,6 +628,8 @@ ngx_slab_alloc_pages(ngx_slab_pool_t *po
         if (page->slab >= pages) {
 
             if (page->slab > pages) {
+                page[page->slab - 1].prev = (uintptr_t) &page[pages];
+
                 page[pages].slab = page->slab - pages;
                 page[pages].next = page->next;
                 page[pages].prev = page->prev;
@@ -672,7 +676,8 @@ static void
 ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
     ngx_uint_t pages)
 {
-    ngx_slab_page_t  *prev;
+    ngx_uint_t        type;
+    ngx_slab_page_t  *prev, *join;
 
     page->slab = pages--;
 
@@ -686,6 +691,53 @@ ngx_slab_free_pages(ngx_slab_pool_t *poo
         page->next->prev = page->prev;
     }
 
+    join = page + page->slab;
+
+    if (join < pool->last) {
+        type = join->prev & NGX_SLAB_PAGE_MASK;
+
+        if (type == NGX_SLAB_PAGE && join->next != NULL) {
+            pages += join->slab;
+            page->slab += join->slab;
+
+            prev = (ngx_slab_page_t *) (join->prev & ~NGX_SLAB_PAGE_MASK);
+            prev->next = join->next;
+            join->next->prev = join->prev;
+
+            join->slab = NGX_SLAB_PAGE_FREE;
+            join->next = NULL;
+            join->prev = NGX_SLAB_PAGE;
+        }
+    }
+
+    if (page > pool->pages) {
+        join = page - 1;
+        type = join->prev & NGX_SLAB_PAGE_MASK;
+
+        if (type == NGX_SLAB_PAGE && join->slab == NGX_SLAB_PAGE_FREE) {
+            join = (ngx_slab_page_t *) (join->prev & ~NGX_SLAB_PAGE_MASK);
+        }
+
+        if (type == NGX_SLAB_PAGE && join->next != NULL) {
+            pages += join->slab;
+            join->slab += page->slab;
+
+            prev = (ngx_slab_page_t *) (join->prev & ~NGX_SLAB_PAGE_MASK);
+            prev->next = join->next;
+            join->next->prev = join->prev;
+
+            page->slab = NGX_SLAB_PAGE_FREE;
+            page->next = NULL;
+            page->prev = NGX_SLAB_PAGE;
+
+            page = join;
+        }
+    }
+
+    if (pages) {
+        page[pages].prev = (uintptr_t) page;
+    }
+
     page->prev = (uintptr_t) &pool->free;
     page->next = pool->free.next;
 
diff --git a/src/core/ngx_slab.h b/src/core/ngx_slab.h
--- a/src/core/ngx_slab.h
+++ b/src/core/ngx_slab.h
@@ -29,6 +29,7 @@ typedef struct {
     size_t            min_shift;
 
     ngx_slab_page_t  *pages;
+    ngx_slab_page_t  *last;
     ngx_slab_page_t   free;
 
     u_char           *start;

-- 
Maxim Dounin
http://nginx.org/