linux-kernel - Re: Major mke2fs slowdown (reproducable, bisected)

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-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <p736406yuxm.fsf@bingen.suse.de>
Date:	Tue, 13 Nov 2007 17:25:09 +0100
From:	Andi Kleen <andi@...stfloor.org>
To:	Alexey Dobriyan <adobriyan@...il.com>
Cc:	mel@....ul.ie, akpm@...l.org, torvalds@...l.org,
	linux-kernel@...r.kernel.org, linux-mm@...r.kernel.org
Subject: Re: Major mke2fs slowdown (reproducable, bisected)

Alexey Dobriyan <adobriyan@...il.com> writes:
>  
> +/* Return the page with the lowest PFN in the list */
> +static struct page *min_page(struct list_head *list)
> +{
> +	unsigned long min_pfn = -1UL;
> +	struct page *min_page = NULL, *page;;
> +
> +	list_for_each_entry(page, list, lru) {
> +		unsigned long pfn = page_to_pfn(page);
> +		if (pfn < min_pfn) {
> +			min_pfn = pfn;
> +			min_page = page;
> +		}
> +	}
> +
> +	return min_page;
> +}
> +
>  /* Remove an element from the buddy allocator from the fallback list */
>  static struct page *__rmqueue_fallback(struct zone *zone, int order,
>  						int start_migratetype)
> @@ -795,8 +812,11 @@ retry:
>  			if (list_empty(&area->free_list[migratetype]))
>  				continue;
>  
> +			/* Bias kernel allocations towards low pfns */
>  			page = list_entry(area->free_list[migratetype].next,
>  					struct page, lru);
> +			if (unlikely(start_migratetype != MIGRATE_MOVABLE))
> +				page = min_page(&area->free_list[migratetype]);

Do I misread this, or does it really turn the O(1) buddy allocation into
a "search whole free list" algorithm?  Even as fallback that looks like
a quite extreme thing to do.

-Andi
-
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/