From nobody Tue Apr 26 08:14:14 2022 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id E102B19937F7; Tue, 26 Apr 2022 08:14:14 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4KnZRB606Hz3kV1; Tue, 26 Apr 2022 08:14:14 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1650960854; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=l0zm4kC0PftCRBcDx3qHfnT31VpMdfGLR7jyNgqBGTU=; b=XCSZ+GRqN6jSUSeJt3sjp0S0zAlV8VrozwYpjyvTI37IL1O7mlT5JRu2HF+OsIff0DQWju JtK/qZeQLL5b5cTbCYJ57jNYnUcfFKR8RTIYQmYYEDNW/e6jAKGsaiU42kQqi7X24Nl1pM QhvwDAqfoxv1U91aCZj9WUBSp2+mH+DQCZhY3unJq5ywi/OS88qbzyfik2B50ixIvt0Eu1 AxH/gDS1eVl5Q2cHzD5FQHU/ox34B1nCjoNWX76myLk6C6ZGTgMtnu+HHwuNckM3060aOT MeKRfiD4Uh6AvmQmoMEyaP57e9WYJWtTcVM2Qxfv8eS/Ori09fJw1A8CQZ4Ciw== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id A2DF93892; Tue, 26 Apr 2022 08:14:14 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 23Q8EEjd081757; Tue, 26 Apr 2022 08:14:14 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 23Q8EEkn081756; Tue, 26 Apr 2022 08:14:14 GMT (envelope-from git) Date: Tue, 26 Apr 2022 08:14:14 GMT Message-Id: <202204260814.23Q8EEkn081756@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Doug Moore Subject: git: fa8a6585c752 - main - vm_phys: avoid waste in multipage allocation List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: dougm X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: fa8a6585c7522b7de6d29802967bd5eba2f2dcf1 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1650960854; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=l0zm4kC0PftCRBcDx3qHfnT31VpMdfGLR7jyNgqBGTU=; b=DuklwVQ0cMAwE1+b9s1KTMPhHyF1kpBaPkqUr8zebhbzirU42Jzy88Ck60hCwI1+mG3P5W FQy4JUiFQ6ziV4fy2rqOJ+EAZfZau1ubAOgS9YMo7t4FnIXfSorr8RfbHBQPDGuvv93aEg NJy47xn1fUTk1N7hTlVDWn3VooWIR4sCWpdlXiC4EDqbMYtZK9rXlE6Pz/yJPDYijCIkDG f4B6s0WS3JR6Y3XkO/1nMcLs6HYkeFNUyaInewF7FkB4RtMNSWpc/HGcRCOjBZ50Ej3kKT k8eVubMwcEN2xh5yhP5d4O7VWdG7PxNjYcZWOhIt4wGs2tfKE79nNJ2vGCv5Og== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1650960854; a=rsa-sha256; cv=none; b=eOsI06MwUFD/38AlOm3nANc6HOyIhaOpTNSEj2H+CalEd7Qp+wwAwbRIu+ZnHvgvgoiuDd kiogFwzA9OS/4YmUdZ3hFXVB52sPqMpOmP3vpw4F6W3+fYdRcE5xDiX0ZJa9CkGjewG9e+ EWeIzz/BFNEz2rCN7BCzDDcOOjNviK7l8oHEOL2uJlPtlIvjawp4Bu93QvCFSAuFQu4OkF OMYadKIuWpwiBFmT2PuNIb3SHXsmpAuuYOHxfhu/qeGLKU9uRq8OYr8uf+A2J3kID7ev1u tki9aRSYB4sWkr+vYCKr7t/8k08Oy9iu+YAf8BHPHAya4KGVaZyqbN6nUZy+Bg== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=fa8a6585c7522b7de6d29802967bd5eba2f2dcf1 commit fa8a6585c7522b7de6d29802967bd5eba2f2dcf1 Author: Doug Moore AuthorDate: 2022-04-26 07:56:23 +0000 Commit: Doug Moore CommitDate: 2022-04-26 07:56:23 +0000 vm_phys: avoid waste in multipage allocation In vm_phys_alloc_contig, for an allocation bigger than the size of any buddy queue free block, avoid examining any maximum-size free block more than twice, by only starting to consider a sequence of adjacent max-blocks starting at a max-block that does not follow another max-block. If that first max-block follows adjacent blocks of smaller size, and if together they provide enough memory to reduce by one the number of max-blocks required for this allocation, use them as part of this allocation. Reviewed by: markj Tested by: pho Discussed with: alc Differential Revision: https://reviews.freebsd.org/D34815 --- sys/vm/vm_phys.c | 221 ++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 146 insertions(+), 75 deletions(-) diff --git a/sys/vm/vm_phys.c b/sys/vm/vm_phys.c index a7ff4f14691e..45c624fdd451 100644 --- a/sys/vm/vm_phys.c +++ b/sys/vm/vm_phys.c @@ -1354,20 +1354,125 @@ vm_phys_unfree_page(vm_page_t m) } /* - * Allocate a run of contiguous physical pages from the specified free list + * Find a run of contiguous physical pages from the specified page list. + */ +static vm_page_t +vm_phys_find_freelist_contig(struct vm_freelist *fl, int oind, u_long npages, + vm_paddr_t low, vm_paddr_t high, u_long alignment, vm_paddr_t boundary) +{ + struct vm_phys_seg *seg; + vm_paddr_t frag, lbound, pa, page_size, pa_end, pa_pre, size; + vm_page_t m, m_listed, m_ret; + int order; + + KASSERT(npages > 0, ("npages is 0")); + KASSERT(powerof2(alignment), ("alignment is not a power of 2")); + KASSERT(powerof2(boundary), ("boundary is not a power of 2")); + /* Search for a run satisfying the specified conditions. */ + page_size = PAGE_SIZE; + size = npages << PAGE_SHIFT; + frag = (npages & ~(~0UL << oind)) << PAGE_SHIFT; + TAILQ_FOREACH(m_listed, &fl[oind].pl, listq) { + /* + * Determine if the address range starting at pa is + * too low. + */ + pa = VM_PAGE_TO_PHYS(m_listed); + if (pa < low) + continue; + + /* + * If this is not the first free oind-block in this range, bail + * out. We have seen the first free block already, or will see + * it before failing to find an appropriate range. + */ + seg = &vm_phys_segs[m_listed->segind]; + lbound = low > seg->start ? low : seg->start; + pa_pre = pa - (page_size << oind); + m = &seg->first_page[atop(pa_pre - seg->start)]; + if (pa != 0 && pa_pre >= lbound && m->order == oind) + continue; + + if (!vm_addr_align_ok(pa, alignment)) + /* Advance to satisfy alignment condition. */ + pa = roundup2(pa, alignment); + else if (frag != 0 && lbound + frag <= pa) { + /* + * Back up to the first aligned free block in this + * range, without moving below lbound. + */ + pa_end = pa; + for (order = oind - 1; order >= 0; order--) { + pa_pre = pa_end - (page_size << order); + if (!vm_addr_align_ok(pa_pre, alignment)) + break; + m = &seg->first_page[atop(pa_pre - seg->start)]; + if (pa_pre >= lbound && m->order == order) + pa_end = pa_pre; + } + /* + * If the extra small blocks are enough to complete the + * fragment, use them. Otherwise, look to allocate the + * fragment at the other end. + */ + if (pa_end + frag <= pa) + pa = pa_end; + } + + /* Advance as necessary to satisfy boundary conditions. */ + if (!vm_addr_bound_ok(pa, size, boundary)) + pa = roundup2(pa + 1, boundary); + pa_end = pa + size; + + /* + * Determine if the address range is valid (without overflow in + * pa_end calculation), and fits within the segment. + */ + if (pa_end < pa || seg->end < pa_end) + continue; + + m_ret = &seg->first_page[atop(pa - seg->start)]; + + /* + * Determine whether there are enough free oind-blocks here to + * satisfy the allocation request. + */ + pa = VM_PAGE_TO_PHYS(m_listed); + do { + pa += page_size << oind; + if (pa >= pa_end) + return (m_ret); + m = &seg->first_page[atop(pa - seg->start)]; + } while (oind == m->order); + + /* + * Determine if an additional series of free blocks of + * diminishing size can help to satisfy the allocation request. + */ + while (m->order < oind && + pa + 2 * (page_size << m->order) > pa_end) { + pa += page_size << m->order; + if (pa >= pa_end) + return (m_ret); + m = &seg->first_page[atop(pa - seg->start)]; + } + } + return (NULL); +} + +/* + * Find a run of contiguous physical pages from the specified free list * table. */ static vm_page_t -vm_phys_alloc_queues_contig( +vm_phys_find_queues_contig( struct vm_freelist (*queues)[VM_NFREEPOOL][VM_NFREEORDER_MAX], u_long npages, vm_paddr_t low, vm_paddr_t high, u_long alignment, vm_paddr_t boundary) { - struct vm_phys_seg *seg; struct vm_freelist *fl; + vm_page_t m_ret; vm_paddr_t pa, pa_end, size; - vm_page_t m, m_ret; - u_long npages_end; int oind, order, pind; KASSERT(npages > 0, ("npages is 0")); @@ -1375,10 +1480,9 @@ vm_phys_alloc_queues_contig( KASSERT(powerof2(boundary), ("boundary is not a power of 2")); /* Compute the queue that is the best fit for npages. */ order = flsl(npages - 1); - /* Search for a run satisfying the specified conditions. */ + /* Search for a large enough free block. */ size = npages << PAGE_SHIFT; - for (oind = min(order, VM_NFREEORDER - 1); oind < VM_NFREEORDER; - oind++) { + for (oind = order; oind < VM_NFREEORDER; oind++) { for (pind = 0; pind < VM_NFREEPOOL; pind++) { fl = (*queues)[pind]; TAILQ_FOREACH(m_ret, &fl[oind].pl, listq) { @@ -1390,74 +1494,24 @@ vm_phys_alloc_queues_contig( */ pa = VM_PAGE_TO_PHYS(m_ret); pa_end = pa + size; - if (pa < low || pa_end > high || - !vm_addr_ok(pa, size, alignment, boundary)) - continue; - - /* - * Is the size of this allocation request - * no more than the largest block size? - */ - if (order < VM_NFREEORDER) - goto done; - - /* - * Determine if the address range is valid - * (without overflow in pa_end calculation) - * and fits within the segment. - */ - seg = &vm_phys_segs[m_ret->segind]; - if (pa_end < pa || seg->end < pa_end) - continue; - - /* - * Determine if a series of free oind-blocks - * starting here can satisfy the allocation - * request. - */ - do { - pa += 1 << - (PAGE_SHIFT + VM_NFREEORDER - 1); - if (pa >= pa_end) - goto done; - } while (VM_NFREEORDER - 1 == seg->first_page[ - atop(pa - seg->start)].order); - - /* - * Determine if an additional series of free - * blocks of diminishing size can help to - * satisfy the allocation request. - */ - for (;;) { - m = &seg->first_page[ - atop(pa - seg->start)]; - if (m->order == VM_NFREEORDER || - pa + (2 << (PAGE_SHIFT + m->order)) - <= pa_end) - break; - pa += 1 << (PAGE_SHIFT + m->order); - if (pa >= pa_end) - goto done; - } + if (low <= pa && pa_end <= high && + vm_addr_ok(pa, size, alignment, boundary)) + return (m_ret); } } } - return (NULL); -done: - for (m = m_ret; m < &m_ret[npages]; m = &m[1 << oind]) { - fl = (*queues)[m->pool]; - oind = m->order; - vm_freelist_rem(fl, m, oind); - if (m->pool != VM_FREEPOOL_DEFAULT) - vm_phys_set_pool(VM_FREEPOOL_DEFAULT, m, oind); - } - /* Return excess pages to the free lists. */ - npages_end = roundup2(npages, 1 << oind); - if (npages < npages_end) { - fl = (*queues)[VM_FREEPOOL_DEFAULT]; - vm_phys_enq_range(&m_ret[npages], npages_end - npages, fl, 0); + if (order < VM_NFREEORDER) + return (NULL); + /* Search for a long-enough sequence of small blocks. */ + oind = VM_NFREEORDER - 1; + for (pind = 0; pind < VM_NFREEPOOL; pind++) { + fl = (*queues)[pind]; + m_ret = vm_phys_find_freelist_contig(fl, oind, npages, + low, high, alignment, boundary); + if (m_ret != NULL) + return (m_ret); } - return (m_ret); + return (NULL); } /* @@ -1475,10 +1529,11 @@ vm_phys_alloc_contig(int domain, u_long npages, vm_paddr_t low, vm_paddr_t high, u_long alignment, vm_paddr_t boundary) { vm_paddr_t pa_end, pa_start; - vm_page_t m_run; + struct vm_freelist *fl; + vm_page_t m, m_run; struct vm_phys_seg *seg; struct vm_freelist (*queues)[VM_NFREEPOOL][VM_NFREEORDER_MAX]; - int segind; + int oind, segind; KASSERT(npages > 0, ("npages is 0")); KASSERT(powerof2(alignment), ("alignment is not a power of 2")); @@ -1513,11 +1568,27 @@ vm_phys_alloc_contig(int domain, u_long npages, vm_paddr_t low, vm_paddr_t high, if (seg->free_queues == queues) continue; queues = seg->free_queues; - m_run = vm_phys_alloc_queues_contig(queues, npages, + m_run = vm_phys_find_queues_contig(queues, npages, low, high, alignment, boundary); if (m_run != NULL) break; } + if (m_run == NULL) + return (NULL); + + /* Allocate pages from the page-range found. */ + for (m = m_run; m < &m_run[npages]; m = &m[1 << oind]) { + fl = (*queues)[m->pool]; + oind = m->order; + vm_freelist_rem(fl, m, oind); + if (m->pool != VM_FREEPOOL_DEFAULT) + vm_phys_set_pool(VM_FREEPOOL_DEFAULT, m, oind); + } + /* Return excess pages to the free lists. */ + if (&m_run[npages] < m) { + fl = (*queues)[VM_FREEPOOL_DEFAULT]; + vm_phys_enq_range(&m_run[npages], m - &m_run[npages], fl, 0); + } return (m_run); }