NetBSD Problem Report #44969
From www@NetBSD.org Sun May 15 04:28:38 2011
Return-Path: <www@NetBSD.org>
Received: from mail.netbsd.org (mail.netbsd.org [204.152.190.11])
by www.NetBSD.org (Postfix) with ESMTP id 7243563C60A
for <gnats-bugs@gnats.NetBSD.org>; Sun, 15 May 2011 04:28:38 +0000 (UTC)
Message-Id: <20110515042837.D491163B8AC@www.NetBSD.org>
Date: Sun, 15 May 2011 04:28:37 +0000 (UTC)
From: bybinary01@gmail.com
Reply-To: bybinary01@gmail.com
To: gnats-bugs@NetBSD.org
Subject: vmem_xalloc() don't search best-fit free segment in spite of VMEM_BESTFIT
X-Send-Pr-Version: www-1.0
>Number: 44969
>Category: kern
>Synopsis: vmem_xalloc() don't search best-fit free segment in spite of VMEM_BESTFIT
>Confidential: no
>Severity: non-critical
>Priority: medium
>Responsible: kern-bug-people
>State: open
>Class: sw-bug
>Submitter-Id: net
>Arrival-Date: Sun May 15 04:30:00 +0000 2011
>Last-Modified: Tue Jul 26 13:10:02 +0000 2011
>Originator: Fumiyuki Yoshida
>Release: 5.1
>Organization:
>Environment:
I find this problem when I read source code for study.So I don't have the netbsd installed machine.
>Description:
Though you call vmem_xalloc() with VM_BESTFIT(allocation strategy) , you find that vmem_xalloc() don't search best-fit free segment.
VMEM_BESTFIT means that using the smallest free segment that can satisfy the allocation.But current implementation use the free segment which is found at first.(not search best-fit free segment)
>How-To-Repeat:
Call vmem_xalloc() with VM_BESTFIT.
>Fix:
The patch for the bug is following.
Index: subr_vmem.c
===================================================================
RCS file: /cvsroot/src/sys/kern/subr_vmem.c,v
retrieving revision 1.58
diff -r1.58 subr_vmem.c
891a892
> bt_t *bestfit = NULL;
946c947,948
< if (bt->bt_size >= size) {
---
> /* very best-fit */
> if (bt->bt_size == size) {
952a955,962
> else if( bestfit == NULL || bestfit->size > bt->size){
> bestfit = bt;
> }
> }
>
> if( bestfit ){
> bt = bestfit;
> goto gotit;
>Audit-Trail:
From: akachochin <bybinary01@gmail.com>
To: gnats-bugs@netbsd.org
Cc:
Subject: Re: kern/44969
Date: Mon, 16 May 2011 23:00:47 +0900
--0016e65b54fe1565ca04a3651501
Content-Type: text/plain; charset=ISO-8859-1
I'm Fumiyuki Yoshida.
>Category: kern
> >Responsible: kern-bug-people
> >Synopsis: vmem_xalloc() don't search best-fit free segment in spite
> of VMEM_BESTFIT
> >Arrival-Date: Sun May 15 04:30:00 +0000 2011
>
Thank you for accepting my problem report.
But I'm sorry for making a mistake about my patch in the report.I'll
correect and re-submit it.
Following is the patch I correct.
--- subr_vmem.c 17 Dec 2010 22:24:11 -0000 1.58
+++ subr_vmem.c 16 May 2011 13:57:06 -0000
@@ -889,6 +889,7 @@
bt_t *bt;
bt_t *btnew;
bt_t *btnew2;
+ bt_t *bestfit = NULL;
const vmem_size_t size = vmem_roundup_size(vm, size0);
vm_flag_t strat = flags & VM_FITMASK;
vmem_addr_t start;
@@ -943,12 +944,22 @@
} else { /* VM_BESTFIT */
for (list = first; list < end; list++) {
LIST_FOREACH(bt, list, bt_freelist) {
- if (bt->bt_size >= size) {
- start = vmem_fit(bt, size, align, phase,
- nocross, minaddr, maxaddr);
- if (start != VMEM_ADDR_NULL) {
- goto gotit;
- }
+ /* very best-fit */
+ if (bt->bt_size == size) {
+ bestfit = bt;
+ break;
+ }
+ else if( bestfit == NULL || (bestfit->size > bt->size) && ((bt->size -
size > 0))){
+ bestfit = bt;
+ }
+ }
+
+ if( bestfit ){
+ bt = bestfit;
+ start = vmem_fit(bt, size, align, phase,
+ nocross, minaddr, maxaddr);
+ if (start != VMEM_ADDR_NULL) {
+ goto gotit;
}
}
}
--0016e65b54fe1565ca04a3651501
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
I'm Fumiyuki Yoshida.<br><br><div class=3D"gmail_quote"><blockquote cla=
ss=3D"gmail_quote" style=3D"margin:0pt 0pt 0pt 0.8ex;border-left:1px solid =
rgb(204, 204, 204);padding-left:1ex">
>Category: =A0 =A0 =A0 kern<br>
>Responsible: =A0 =A0kern-bug-people<br>
>Synopsis: =A0 =A0 =A0 vmem_xalloc() don't search best-fit free segm=
ent in spite of VMEM_BESTFIT<br>
>Arrival-Date: =A0 Sun May 15 04:30:00 +0000 2011<br></blockquote><div><=
br>Thank you for accepting my problem report.<br>
But I'm sorry for making a mistake about my patch in the report.I'l=
l correect and re-submit it.</div><div>Following is the patch I correct.</d=
iv><div><br></div><div><div>--- subr_vmem.c<span class=3D"Apple-tab-span" s=
tyle=3D"white-space:pre"> </span>17 Dec 2010 22:24:11 -0000<span class=3D"A=
pple-tab-span" style=3D"white-space:pre"> </span>1.58</div>
<div>+++ subr_vmem.c<span class=3D"Apple-tab-span" style=3D"white-space:pre=
"> </span>16 May 2011 13:57:06 -0000</div><div>@@ -889,6 +889,7 @@</div><di=
v>=A0<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>bt_t =
*bt;</div>
<div>=A0<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>bt=
_t *btnew;</div><div>=A0<span class=3D"Apple-tab-span" style=3D"white-space=
:pre"> </span>bt_t *btnew2;</div><div>+<span class=3D"Apple-tab-span" style=
=3D"white-space:pre"> </span>bt_t *bestfit =3D NULL;</div>
<div>=A0<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>co=
nst vmem_size_t size =3D vmem_roundup_size(vm, size0);</div><div>=A0<span c=
lass=3D"Apple-tab-span" style=3D"white-space:pre"> </span>vm_flag_t strat =
=3D flags & VM_FITMASK;</div>
<div>=A0<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>vm=
em_addr_t start;</div><div>@@ -943,12 +944,22 @@</div><div>=A0<span class=
=3D"Apple-tab-span" style=3D"white-space:pre"> </span>} else { /* VM_BESTFI=
T */</div>
<div>=A0<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>f=
or (list =3D first; list < end; list++) {</div><div>=A0<span class=3D"Ap=
ple-tab-span" style=3D"white-space:pre"> </span>LIST_FOREACH(bt, list, bt=
_freelist) {</div>
<div>-<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>i=
f (bt->bt_size >=3D size) {</div><div>-<span class=3D"Apple-tab-span"=
style=3D"white-space:pre"> </span>start =3D vmem_fit(bt, size, align, =
phase,</div>
<div>-<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>=
=A0 =A0nocross, minaddr, maxaddr);</div><div>-<span class=3D"Apple-tab-spa=
n" style=3D"white-space:pre"> </span>if (start !=3D VMEM_ADDR_NULL) {</=
div><div>-<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </=
span>goto gotit;</div>
<div>-<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>=
}</div><div>+<span class=3D"Apple-tab-span" style=3D"white-space:pre"> <=
/span>/* very best-fit */</div><div>+<span class=3D"Apple-tab-span" style=
=3D"white-space:pre"> </span>if (bt->bt_size =3D=3D size) {</div>
<div>+<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>=
bestfit =3D bt;</div><div>+<span class=3D"Apple-tab-span" style=3D"white-sp=
ace:pre"> </span>break;</div><div>+<span class=3D"Apple-tab-span" style=
=3D"white-space:pre"> </span>}</div>
<div>+<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>e=
lse if( bestfit =3D=3D NULL || (bestfit->size > bt->size) &&am=
p; ((bt->size - size > 0))){</div><div>+<span class=3D"Apple-tab-span=
" style=3D"white-space:pre"> </span>bestfit =3D bt;</div>
<div>+<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>}=
</div><div>+<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </s=
pan>}</div><div>+</div><div>+<span class=3D"Apple-tab-span" style=3D"white-=
space:pre"> </span>if( bestfit ){</div>
<div>+<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>b=
t =3D bestfit;</div><div>+<span class=3D"Apple-tab-span" style=3D"white-spa=
ce:pre"> </span>start =3D vmem_fit(bt, size, align, phase,</div><div>+<s=
pan class=3D"Apple-tab-span" style=3D"white-space:pre"> </span> =A0 =A0n=
ocross, minaddr, maxaddr);</div>
<div>+<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>i=
f (start !=3D VMEM_ADDR_NULL) {</div><div>+<span class=3D"Apple-tab-span" s=
tyle=3D"white-space:pre"> </span>goto gotit;</div><div>=A0<span class=
=3D"Apple-tab-span" style=3D"white-space:pre"> </span>}</div>
<div>=A0<span class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>=
}</div><div>=A0<span class=3D"Apple-tab-span" style=3D"white-space:pre"> <=
/span>}</div><div><br></div><br>=A0<br></div></div><br>
--0016e65b54fe1565ca04a3651501--
From: yamt@mwd.biglobe.ne.jp (YAMAMOTO Takashi)
To: gnats-bugs@NetBSD.org
Cc: kern-bug-people@netbsd.org, gnats-admin@netbsd.org,
netbsd-bugs@netbsd.org
Subject: Re: kern/44969: vmem_xalloc() don't search best-fit free segment in
spite of VMEM_BESTFIT
Date: Tue, 12 Jul 2011 00:17:02 +0000 (UTC)
hi,
>>Description:
> Though you call vmem_xalloc() with VM_BESTFIT(allocation strategy) , you find that vmem_xalloc() don't search best-fit free segment.
> VMEM_BESTFIT means that using the smallest free segment that can satisfy the allocation.But current implementation use the free segment which is found at first.(not search best-fit free segment)
it's an intended behaviour.
have you seen space efficiency problems due to this?
YAMAMOTO Takashi
From: David Laight <david@l8s.co.uk>
To: gnats-bugs@NetBSD.org
Cc:
Subject: Re: kern/44969: vmem_xalloc() don't search best-fit free segment in spite of VMEM_BESTFIT
Date: Tue, 12 Jul 2011 08:05:01 +0100
On Tue, Jul 12, 2011 at 12:20:05AM +0000, YAMAMOTO Takashi wrote:
> The following reply was made to PR kern/44969; it has been noted by GNATS.
>
> From: yamt@mwd.biglobe.ne.jp (YAMAMOTO Takashi)
> To: gnats-bugs@NetBSD.org
> Cc: kern-bug-people@netbsd.org, gnats-admin@netbsd.org,
> netbsd-bugs@netbsd.org
> Subject: Re: kern/44969: vmem_xalloc() don't search best-fit free segment in
> spite of VMEM_BESTFIT
> Date: Tue, 12 Jul 2011 00:17:02 +0000 (UTC)
>
> hi,
>
> >>Description:
> > Though you call vmem_xalloc() with VM_BESTFIT(allocation strategy),
> > you find that vmem_xalloc() don't search best-fit free segment.
> > VMEM_BESTFIT means that using the smallest free segment that can satisfy
> > the allocation.But current implementation use the free segment which is
> > found at first.(not search best-fit free segment)
>
> it's an intended behaviour.
> have you seen space efficiency problems due to this?
Not here, but I've had serious problems with 'first free' causing
excessive fragmentation in the past.
In that case changing the code to do 'best fit' completely removed
the fragmentation issue.
(That one may have been made worse by being a linked list, but the
amount of dross at the front meant that I actually reduced the
typical number of items scanned!)
David
--
David Laight: david@l8s.co.uk
From: akachochin <bybinary01@gmail.com>
To: gnats-bugs@netbsd.org
Cc:
Subject: Re: kern/44969: vmem_xalloc() don't search best-fit free segment in
spite of VMEM_BESTFIT
Date: Wed, 13 Jul 2011 23:48:21 +0900
--0016364d2b0503389c04a7f48259
Content-Type: text/plain; charset=ISO-8859-1
Hello , I'm Fumiyuki Yoshida.I send this patch.
Thank you for replying my Send-PR.
I think VM_BESTFIT search the smallest free segment that can satisfy the
allocation.
Also "Solaris Internals 2nd edition" says that about VM_BESTFIT.So,I send
the patch.
have you seen space efficiency problems due to this?
>
I don't get the problem due to this.But I found this code while I read the
source code for study.
If I make any mistake , I'm glad to tell me about my mistake.
--0016364d2b0503389c04a7f48259
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Hello , I'm Fumiyuki Yoshida.I send this patch.<br><br>Thank you for re=
plying my Send-PR.<br><br><div class=3D"gmail_quote">I think VM_BESTFIT sea=
rch the smallest free segment that can satisfy the allocation.<br>Also &quo=
t;Solaris Internals 2nd edition" says that about VM_BESTFIT.So,I send =
the patch.<br>
<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-lef=
t:1px #ccc solid;padding-left:1ex">=A0
have you seen space efficiency problems due to this?<br></blockquote><div>I=
don't get the problem due to this.But I found this code while I read t=
he source code for study. <br>If I make any mistake , I'm glad to tell =
me about my mistake.<br>
</div></div>
--0016364d2b0503389c04a7f48259--
From: David Holland <dholland-bugs@netbsd.org>
To: gnats-bugs@NetBSD.org
Cc:
Subject: Re: kern/44969: vmem_xalloc() don't search best-fit free segment in
spite of VMEM_BESTFIT
Date: Tue, 19 Jul 2011 02:47:42 +0000
On Tue, Jul 12, 2011 at 07:10:06AM +0000, David Laight wrote:
>>> Though you call vmem_xalloc() with VM_BESTFIT(allocation strategy),
>>> you find that vmem_xalloc() don't search best-fit free segment.
>>> VMEM_BESTFIT means that using the smallest free segment that can satisfy
>>> the allocation.But current implementation use the free segment which is
>>> found at first.(not search best-fit free segment)
>>
>> it's an intended behaviour.
>> have you seen space efficiency problems due to this?
>
> Not here, but I've had serious problems with 'first free' causing
> excessive fragmentation in the past.
> In that case changing the code to do 'best fit' completely removed
> the fragmentation issue.
In general/on average first-fit, next-fit, and best-fit tend to do
about the same, but for specific workloads one or another may be
markedly better.
ISTM that if the caller asks for best fit, the caller should get best
fit, and callers should ask specifically for a particular method only
when they care and get the default otherwise.
Oh hm.
The allocation strategy is one of:
VM_BESTFIT Prefer space efficiency.
VM_INSTANTFIT Prefer performance.
that's rather bollocks...
--
David A. Holland
dholland@netbsd.org
From: "YAMAMOTO Takashi" <yamt@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc:
Subject: PR/44969 CVS commit: src/sys/kern
Date: Tue, 26 Jul 2011 13:09:11 +0000
Module Name: src
Committed By: yamt
Date: Tue Jul 26 13:09:11 UTC 2011
Modified Files:
src/sys/kern: subr_vmem.c
Log Message:
comments. related to PR/44969
To generate a diff of this commit:
cvs rdiff -u -r1.58 -r1.59 src/sys/kern/subr_vmem.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
(Contact us)
$NetBSD: query-full-pr,v 1.39 2013/11/01 18:47:49 spz Exp $
$NetBSD: gnats_config.sh,v 1.8 2006/05/07 09:23:38 tsutsui Exp $
Copyright © 1994-2007
The NetBSD Foundation, Inc. ALL RIGHTS RESERVED.
Home