kvm.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Claudio Imbrenda <imbrenda@linux.ibm.com>
To: kvm@vger.kernel.org
Cc: frankja@linux.ibm.com, david@redhat.com, thuth@redhat.com,
	pbonzini@redhat.com, cohuck@redhat.com, lvivier@redhat.com,
	nadav.amit@gmail.com, krish.sadhukhan@oracle.com
Subject: [kvm-unit-tests PATCH v2 07/11] lib/alloc_page: Optimization to skip known empty freelists
Date: Fri, 15 Jan 2021 13:37:26 +0100	[thread overview]
Message-ID: <20210115123730.381612-8-imbrenda@linux.ibm.com> (raw)
In-Reply-To: <20210115123730.381612-1-imbrenda@linux.ibm.com>

Keep track of the largest block order available in each area, and do not
search past it when looking for free memory.

This will avoid needlessly scanning the freelists for the largest block
orders, which will be empty in most cases.

Signed-off-by: Claudio Imbrenda <imbrenda@linux.ibm.com>
Reviewed-by: Krish Sadhukhan <krish.sadhukhan@oracle.com>
---
 lib/alloc_page.c | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)

diff --git a/lib/alloc_page.c b/lib/alloc_page.c
index 7d1fa85..37f28ce 100644
--- a/lib/alloc_page.c
+++ b/lib/alloc_page.c
@@ -31,6 +31,8 @@ struct mem_area {
 	pfn_t top;
 	/* Per page metadata, each entry is a combination *_MASK and order */
 	u8 *page_states;
+	/* Highest block order available in this area */
+	u8 max_order;
 	/* One freelist for each possible block size, up to NLISTS */
 	struct linked_list freelists[NLISTS];
 };
@@ -104,6 +106,8 @@ static void split(struct mem_area *a, void *addr)
 		assert(a->page_states[idx + i] == order);
 		a->page_states[idx + i] = order - 1;
 	}
+	if ((order == a->max_order) && (is_list_empty(a->freelists + order)))
+		a->max_order--;
 	order--;
 	/* add the first half block to the appropriate free list */
 	list_add(a->freelists + order, addr);
@@ -127,13 +131,13 @@ static void *page_memalign_order(struct mem_area *a, u8 al, u8 sz)
 	order = sz > al ? sz : al;
 
 	/* search all free lists for some memory */
-	for ( ; order < NLISTS; order++) {
+	for ( ; order <= a->max_order; order++) {
 		p = a->freelists[order].next;
 		if (!is_list_empty(p))
 			break;
 	}
 	/* out of memory */
-	if (order >= NLISTS)
+	if (order > a->max_order)
 		return NULL;
 
 	/*
@@ -201,6 +205,8 @@ static bool coalesce(struct mem_area *a, u8 order, pfn_t pfn, pfn_t pfn2)
 	}
 	/* finally add the newly coalesced block to the appropriate freelist */
 	list_add(a->freelists + order + 1, pfn_to_virt(pfn));
+	if (order + 1 > a->max_order)
+		a->max_order = order + 1;
 	return true;
 }
 
@@ -438,6 +444,7 @@ static void _page_alloc_init_area(u8 n, pfn_t start_pfn, pfn_t top_pfn)
 	a->page_states = pfn_to_virt(start_pfn);
 	a->base = start_pfn + table_size;
 	a->top = top_pfn;
+	a->max_order = 0;
 	npages = top_pfn - a->base;
 	assert((a->base - start_pfn) * PAGE_SIZE >= npages);
 
@@ -472,6 +479,8 @@ static void _page_alloc_init_area(u8 n, pfn_t start_pfn, pfn_t top_pfn)
 		/* initialize the metadata and add to the freelist */
 		memset(a->page_states + (i - a->base), order, BIT(order));
 		list_add(a->freelists + order, pfn_to_virt(i));
+		if (order > a->max_order)
+			a->max_order = order;
 	}
 	/* finally mark the area as present */
 	areas_mask |= BIT(n);
-- 
2.26.2


  parent reply	other threads:[~2021-01-15 12:44 UTC|newest]

Thread overview: 20+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-01-15 12:37 [kvm-unit-tests PATCH v2 00/11] Fix and improve the page allocator Claudio Imbrenda
2021-01-15 12:37 ` [kvm-unit-tests PATCH v2 01/11] lib/x86: fix page.h to include the generic header Claudio Imbrenda
2021-01-19 15:12   ` Janosch Frank
2021-01-15 12:37 ` [kvm-unit-tests PATCH v2 02/11] lib/list.h: add list_add_tail Claudio Imbrenda
2021-01-19 15:18   ` Janosch Frank
2021-01-15 12:37 ` [kvm-unit-tests PATCH v2 03/11] lib/vmalloc: add some asserts and improvements Claudio Imbrenda
2021-01-19 15:26   ` Janosch Frank
2021-01-15 12:37 ` [kvm-unit-tests PATCH v2 04/11] lib/asm: Fix definitions of memory areas Claudio Imbrenda
2021-01-19 15:33   ` Janosch Frank
2021-01-19 17:05     ` Claudio Imbrenda
2021-01-21  1:23   ` David Matlack
2021-01-21  5:32     ` Thomas Huth
2021-01-21  9:28     ` Claudio Imbrenda
2021-01-15 12:37 ` [kvm-unit-tests PATCH v2 05/11] lib/alloc_page: fix and improve the page allocator Claudio Imbrenda
2021-01-15 12:37 ` [kvm-unit-tests PATCH v2 06/11] lib/alloc.h: remove align_min from struct alloc_ops Claudio Imbrenda
2021-01-15 12:37 ` Claudio Imbrenda [this message]
2021-01-15 12:37 ` [kvm-unit-tests PATCH v2 08/11] lib/alloc_page: rework metadata format Claudio Imbrenda
2021-01-15 12:37 ` [kvm-unit-tests PATCH v2 09/11] lib/alloc: replace areas with more generic flags Claudio Imbrenda
2021-01-15 12:37 ` [kvm-unit-tests PATCH v2 10/11] lib/alloc_page: Wire up FLAG_DONTZERO Claudio Imbrenda
2021-01-15 12:37 ` [kvm-unit-tests PATCH v2 11/11] lib/alloc_page: Properly handle requests for fresh blocks Claudio Imbrenda

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20210115123730.381612-8-imbrenda@linux.ibm.com \
    --to=imbrenda@linux.ibm.com \
    --cc=cohuck@redhat.com \
    --cc=david@redhat.com \
    --cc=frankja@linux.ibm.com \
    --cc=krish.sadhukhan@oracle.com \
    --cc=kvm@vger.kernel.org \
    --cc=lvivier@redhat.com \
    --cc=nadav.amit@gmail.com \
    --cc=pbonzini@redhat.com \
    --cc=thuth@redhat.com \
    --subject='Re: [kvm-unit-tests PATCH v2 07/11] lib/alloc_page: Optimization to skip known empty freelists' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).