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.

Feedback welcome!

Thanks!
-agentzh

# HG changeset patch
# User Yichun Zhang <agentzh@gmail.com>
# Date 1399870567 25200
# Sun May 11 21:56:07 2014 -0700
# Node ID 93614769dd4b6df8844c3c43c6a0b3f83bfa6746
# Parent 48c97d83ab7f0a3f641987fb32ace8af7720aefc
Core: merge adjacent free slab pages to ameliorate fragmentation from
multi-page blocks.

diff -r 48c97d83ab7f -r 93614769dd4b src/core/ngx_slab.c
--- a/src/core/ngx_slab.c Tue Apr 29 22:22:38 2014 +0200
+++ b/src/core/ngx_slab.c Sun May 11 21:56:07 2014 -0700
@@ -111,6 +111,7 @@
ngx_memzero(p, pages * sizeof(ngx_slab_page_t));

pool->pages = (ngx_slab_page_t *) p;
+ pool->npages = pages;

pool->free.prev = 0;
pool->free.next = (ngx_slab_page_t *) p;
@@ -118,6 +119,7 @@
pool->pages->slab = pages;
pool->pages->next = &pool->free;
pool->pages->prev = (uintptr_t) &pool->free;
+ pool->pages->prev_slab = 0;

pool->start = (u_char *)
ngx_align_ptr((uintptr_t) p + pages *
sizeof(ngx_slab_page_t),
@@ -626,9 +628,16 @@
if (page->slab >= pages) {

if (page->slab > pages) {
+ /* adjust the next adjacent block's "prev_slab" field */
+ p = &page[page->slab];
+ if (p < pool->pages + pool->npages) {
+ p->prev_slab = page->slab - pages;
+ }
+
page[pages].slab = page->slab - pages;
page[pages].next = page->next;
page[pages].prev = page->prev;
+ page[pages].prev_slab = pages;

p = (ngx_slab_page_t *) page->prev;
p->next = &page[pages];
@@ -652,6 +661,7 @@
p->slab = NGX_SLAB_PAGE_BUSY;
p->next = NULL;
p->prev = NGX_SLAB_PAGE;
+ p->prev_slab = 0;
p++;
}

@@ -672,7 +682,7 @@
ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
ngx_uint_t pages)
{
- ngx_slab_page_t *prev;
+ ngx_slab_page_t *prev, *p;

page->slab = pages--;

@@ -686,6 +696,53 @@
page->next->prev = page->prev;
}

+ /* merge the next adjacent free block if it is free */
+
+ p = &page[page->slab];
+ if (p < pool->pages + pool->npages
+ && !(p->slab & NGX_SLAB_PAGE_START)
+ && p->next != NULL
+ && (p->prev & NGX_SLAB_PAGE_MASK) == NGX_SLAB_PAGE)
+ {
+ page->slab += p->slab;
+
+ /* remove the next adjacent block from the free list */
+
+ prev = (ngx_slab_page_t *) p->prev;
+ prev->next = p->next;
+ p->next->prev = p->prev;
+
+ /* adjust the "prev_slab" field in the next next adjacent block */
+ if (p + p->slab < pool->pages + pool->npages) {
+ p[p->slab].prev_slab = page->slab;
+ }
+
+ ngx_memzero(p, sizeof(ngx_slab_page_t));
+ }
+
+ if (page->prev_slab) {
+ /* merge the previous adjacent block if it is free */
+
+ p = page - page->prev_slab;
+ if (!(p->slab & NGX_SLAB_PAGE_START)
+ && p->next != NULL
+ && (p->prev & NGX_SLAB_PAGE_MASK) == NGX_SLAB_PAGE)
+ {
+ /* p->slab == page->prev_slab */
+
+ p->slab += page->slab;
+ ngx_memzero(page, sizeof(ngx_slab_page_t));
+
+ /* adjust the "prev_slab" field in the next adjacent block */
+ if (p + p->slab < pool->pages + pool->npages) {
+ p[p->slab].prev_slab = p->slab;
+ }
+
+ /* skip adding "page" to the free list */
+ return;
+ }
+ }
+
page->prev = (uintptr_t) &pool->free;
page->next = pool->free.next;

diff -r 48c97d83ab7f -r 93614769dd4b src/core/ngx_slab.h
--- a/src/core/ngx_slab.h Tue Apr 29 22:22:38 2014 +0200
+++ b/src/core/ngx_slab.h Sun May 11 21:56:07 2014 -0700
@@ -19,6 +19,8 @@
uintptr_t slab;
ngx_slab_page_t *next;
uintptr_t prev;
+ uintptr_t prev_slab;
+ /* number of pages for the previous adjacent block */
};


@@ -31,6 +33,8 @@
ngx_slab_page_t *pages;
ngx_slab_page_t free;

+ ngx_uint_t npages;
+
u_char *start;
u_char *end;
_______________________________________________
nginx-devel mailing list
nginx-devel@nginx.org
http://mailman.nginx.org/mailman/listinfo/nginx-devel