[nginx] Core: slab allocator free pages defragmentation.

[Maxim Dounin]

details:   http://hg.nginx.org/nginx/rev/c46657e391a3
branches:  
changeset: 5718:c46657e391a3
user:      Maxim Dounin <mdounin at mdounin.ru>
date:      Tue Jun 03 17:53:03 2014 +0400
description:
Core: slab allocator free pages 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.

diffstat:

 src/core/ngx_slab.c |  60 ++++++++++++++++++++++++++++++++++++++++++++++++++++-
 src/core/ngx_slab.h |   1 +
 2 files changed, 60 insertions(+), 1 deletions(-)

diffs (102 lines):

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,59 @@ 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) {
+
+            if (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) {
+
+            if (join->slab == NGX_SLAB_PAGE_FREE) {
+                join = (ngx_slab_page_t *) (join->prev & ~NGX_SLAB_PAGE_MASK);
+            }
+
+            if (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;