From owner-cvs-src@FreeBSD.ORG Sat Jun 11 00:05:16 2005 Return-Path: X-Original-To: cvs-src@FreeBSD.org Delivered-To: cvs-src@FreeBSD.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 8F29B16A41C; Sat, 11 Jun 2005 00:05:16 +0000 (GMT) (envelope-from green@FreeBSD.org) Received: from repoman.freebsd.org (repoman.freebsd.org [216.136.204.115]) by mx1.FreeBSD.org (Postfix) with ESMTP id 6B01B43D53; Sat, 11 Jun 2005 00:05:16 +0000 (GMT) (envelope-from green@FreeBSD.org) Received: from repoman.freebsd.org (localhost [127.0.0.1]) by repoman.freebsd.org (8.13.1/8.13.1) with ESMTP id j5B05Goo008833; Sat, 11 Jun 2005 00:05:16 GMT (envelope-from green@repoman.freebsd.org) Received: (from green@localhost) by repoman.freebsd.org (8.13.1/8.13.1/Submit) id j5B05G1A008832; Sat, 11 Jun 2005 00:05:16 GMT (envelope-from green) Message-Id: <200506110005.j5B05G1A008832@repoman.freebsd.org> From: Brian Feldman Date: Sat, 11 Jun 2005 00:05:16 +0000 (UTC) To: src-committers@FreeBSD.org, cvs-src@FreeBSD.org, cvs-all@FreeBSD.org X-FreeBSD-CVS-Branch: HEAD Cc: Subject: cvs commit: src/sys/vm vm_contig.c X-BeenThere: cvs-src@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: CVS commit messages for the src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 11 Jun 2005 00:05:16 -0000 green 2005-06-11 00:05:16 UTC FreeBSD src repository Modified files: sys/vm vm_contig.c Log: The new contigmalloc(9) has a bad degenerate case where there were many regions checked again and again despite knowing the pages contained were not usable and only satisfied the alignment constraints This case was compounded, especially for large allocations, by the practice of looping from the top of memory so as to keep out of the important low-memory regions. While the old contigmalloc(9) has the same problem, it is not as noticeable due to looping from the low memory to high. This degenerate case is fixed, as well as reversing the sense of the rest of the loops within it, to provide a tremendous speed increase. This makes the best case O(n * VM overhead) much more likely than the worst case O(4 * VM overhead). For comparison, the worst case for old contigmalloc would be O(5 * VM overhead) in addition to its strategy of turning used memory into free being highly pessimal. Also, fix a bug that in practice most likely couldn't have been triggered, int the new contigmalloc(9): it walked backwards from the end of memory without accounting for how many pages it needed. Potentially, nonexistant pages could have been mapped. This hasn't occurred because the kernel generally requests as its first contigmalloc(9) a single page. Reported by: Nicolas Dehaine , wes MFC After: 1 month More testing by: Nicolas Dehaine , wes Revision Changes Path 1.43 +23 -11 src/sys/vm/vm_contig.c