lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date:	Sat, 14 Jul 2007 00:54:35 -0500
From:	Matt Mackall <mpm@...enic.com>
To:	linux-kernel <linux-kernel@...r.kernel.org>
Cc:	Nick Piggin <nickpiggin@...oo.com.au>, akpm@...ux-foundation.org,
	Pekka Enberg <penberg@...helsinki.fi>,
	Christoph Lameter <clameter@....com>
Subject: [PATCH] slob: reduce list scanning

The version of SLOB in -mm always scans its free list from the
beginning, which results in small allocations and free segments
clustering at the beginning of the list over time. This causes the
average search to scan over a large stretch at the beginning on each
allocation.

By starting each page search where the last one left off, we evenly
distribute the allocations and greatly shorten the average search.

Without this patch, kernel compiles on a 1.5G machine take a large
amount of system time for list scanning. With this patch, compiles are
within a few seconds of performance of a SLAB kernel with no notable
change in system time.

Signed-off-by: Matt Mackall <mpm@...enic.com>

Index: mm/mm/slob.c
===================================================================
--- mm.orig/mm/slob.c	2007-07-13 17:51:25.000000000 -0500
+++ mm/mm/slob.c	2007-07-13 18:42:59.000000000 -0500
@@ -293,6 +293,7 @@ static void *slob_page_alloc(struct slob
 static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
 {
 	struct slob_page *sp;
+	struct list_head *prev;
 	slob_t *b = NULL;
 	unsigned long flags;
 
@@ -307,12 +308,22 @@ static void *slob_alloc(size_t size, gfp
 		if (node != -1 && page_to_nid(&sp->page) != node)
 			continue;
 #endif
+		/* Enough room on this page? */
+		if (sp->units < SLOB_UNITS(size))
+			continue;
 
-		if (sp->units >= SLOB_UNITS(size)) {
-			b = slob_page_alloc(sp, size, align);
-			if (b)
-				break;
-		}
+		/* Attempt to alloc */
+		prev = sp->list.prev;
+		b = slob_page_alloc(sp, size, align);
+		if (!b)
+			continue;
+
+		/* Improve fragment distribution and reduce our average
+		 * search time by starting our next search here. (see
+		 * Knuth vol 1, sec 2.5, pg 449) */
+		if (free_slob_pages.next != prev->next)
+			list_move_tail(&free_slob_pages, prev->next);
+		break;
 	}
 	spin_unlock_irqrestore(&slob_lock, flags);
 


-- 
Mathematics is the supreme nostalgia of our time.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists