NetBSD Problem Report #58115

From www@netbsd.org  Thu Apr  4 22:55:25 2024
Return-Path: <www@netbsd.org>
Received: from mail.netbsd.org (mail.netbsd.org [199.233.217.200])
	(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits))
	(Client CN "mail.NetBSD.org", Issuer "mail.NetBSD.org CA" (not verified))
	by mollari.NetBSD.org (Postfix) with ESMTPS id 76E261A9239
	for <gnats-bugs@gnats.NetBSD.org>; Thu,  4 Apr 2024 22:55:25 +0000 (UTC)
Message-Id: <20240404225524.56ECD1A923B@mollari.NetBSD.org>
Date: Thu,  4 Apr 2024 22:55:24 +0000 (UTC)
From: jbglaw@lug-owl.de
Reply-To: jbglaw@lug-owl.de
To: gnats-bugs@NetBSD.org
Subject: [RB] usr.bin/config: stabilize ioconf.c output
X-Send-Pr-Version: www-1.0

>Number:         58115
>Category:       bin
>Synopsis:       [RB] usr.bin/config: stabilize ioconf.c output
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    bin-bug-people
>State:          needs-pullups
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Thu Apr 04 23:00:00 +0000 2024
>Closed-Date:    
>Last-Modified:  Fri Apr 05 00:55:06 +0000 2024
>Originator:     Jan-Benedict Glaw
>Release:        current
>Organization:
>Environment:
NetBSD amd64 + Linux amd64
>Description:
I'm currently working on advancing reproducibility (so that build artifacts when built on a Linux-based host system are the same compared to a NetBSD-hosted build). One difference affecting kernel and modules arise from qsort() usage. While both NetBSD's and GNU's qsort() functions work as expected, it would be nice to get a matching ioconf.c in both cases. (glibc's qsort() keeps the initial order of objects with equal comparison results, while NetBSD's version does not.)

As an example, let's look at sys/modules/spdmem/spdmem.ioconf:

```
spdmem* at iic? addr 0x50
spdmem* at iic? addr 0x51
spdmem* at iic? addr 0x52
spdmem* at iic? addr 0x53
spdmem* at iic? addr 0x54
spdmem* at iic? addr 0x55
spdmem* at iic? addr 0x56
spdmem* at iic? addr 0x57
```

On a NetBSD host, this is generated:
```
[...]
/* locators */
static int loc[8] = {
        0x57, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x50,
};
[...]
static struct cfdata cfdata_ioconf_spdmem[] = {
    /* driver           attachment    unit state      loc   flags  pspec */
/*  0: spdmem* at iic? addr 0x50 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  7,      0, &pspec0 },
/*  1: spdmem* at iic? addr 0x51 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  1,      0, &pspec0 },
/*  2: spdmem* at iic? addr 0x52 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  2,      0, &pspec0 },
/*  3: spdmem* at iic? addr 0x53 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  3,      0, &pspec0 },
/*  4: spdmem* at iic? addr 0x54 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  4,      0, &pspec0 },
/*  5: spdmem* at iic? addr 0x55 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  5,      0, &pspec0 },
/*  6: spdmem* at iic? addr 0x56 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  6,      0, &pspec0 },
/*  7: spdmem* at iic? addr 0x57 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  0,      0, &pspec0 },
    { NULL,             NULL,            0,    0,    NULL,      0, NULL }
};
[...]
```

...while on a Linux host, we see:

```
[...]
/* locators */
static int loc[8] = {
        0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
};
[...]
static struct cfdata cfdata_ioconf_spdmem[] = {
    /* driver           attachment    unit state      loc   flags  pspec */
/*  0: spdmem* at iic? addr 0x50 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  0,      0, &pspec0 },
/*  1: spdmem* at iic? addr 0x51 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  1,      0, &pspec0 },
/*  2: spdmem* at iic? addr 0x52 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  2,      0, &pspec0 },
/*  3: spdmem* at iic? addr 0x53 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  3,      0, &pspec0 },
/*  4: spdmem* at iic? addr 0x54 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  4,      0, &pspec0 },
/*  5: spdmem* at iic? addr 0x55 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  5,      0, &pspec0 },
/*  6: spdmem* at iic? addr 0x56 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  6,      0, &pspec0 },
/*  7: spdmem* at iic? addr 0x57 */
    { "spdmem",         "spdmem_iic",    0, STAR, loc+  7,      0, &pspec0 },
    { NULL,             NULL,            0,    0,    NULL,      0, NULL }
};
[...]
```

The resulting module has a different `loc` array as well as different pointers to it within the `cfdata_ioconf_spdmem` array.
>How-To-Repeat:
Just build a kernel and check generated ioconf.c files.
>Fix:
Extend sorting by eg. also tracking the overall input line number and use that as a sorting key IFF the sorting used right now would result in a "both are the same" result.

>Release-Note:

>Audit-Trail:

State-Changed-From-To: open->analyzed
State-Changed-By: riastradh@NetBSD.org
State-Changed-When: Thu, 04 Apr 2024 23:23:03 +0000
State-Changed-Why:
qsort is unstable, mergesort is stable but nonstandard
=> switch to mergesort, add to tools/compat


From: Taylor R Campbell <riastradh@NetBSD.org>
To: Jan-Benedict Glaw <jbglaw@lug-owl.de>
Cc: gnats-bugs@NetBSD.org, netbsd-bugs@NetBSD.org
Subject: Re: bin/58115: [RB] usr.bin/config: stabilize ioconf.c output
Date: Thu, 4 Apr 2024 23:22:21 +0000

 We should just use mergesort(3) in config(1).  However, that requires
 adding it to tools/compat, which is a bit of rigmarole judging by the
 heapsort(3) we already have there, so it's not trivial.

 Maybe we could do it more easily by just replacing heapsort by
 mergesort in the tools build anyway.  None of this is a bottleneck,
 and the memory savings of heapsort is just as insignificant as the
 (potential) performance benefit of qsort.

From: "Taylor R Campbell" <riastradh@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/58115 CVS commit: src/usr.bin/config
Date: Fri, 5 Apr 2024 00:43:42 +0000

 Module Name:	src
 Committed By:	riastradh
 Date:		Fri Apr  5 00:43:42 UTC 2024

 Modified Files:
 	src/usr.bin/config: defs.h files.c mkioconf.c mkmakefile.c pack.c

 Log Message:
 config(1): Make sort order deterministic.

 Ensure we break ties in every case.  This way, even though we use the
 unstable qsort(3) library routine, the output is reproducible, no
 matter what algorithm is behind qsort(3).

 It would be nice if we could just use a stable sort function here,
 but mergesort(3) is nonstandard, so we'd have to add it to
 tools/compat, which is a big pain.

 Instead, put a tie-breaking rule in every comparison function we use
 with qsort, and abort() in the event of ties -- that way, we noisily
 refuse to rely on unstable sort order.

 While here, dispense with any question of integer overflow, and
 sprinkle comments.

 PR bin/58115


 To generate a diff of this commit:
 cvs rdiff -u -r1.108 -r1.109 src/usr.bin/config/defs.h
 cvs rdiff -u -r1.37 -r1.38 src/usr.bin/config/files.c
 cvs rdiff -u -r1.35 -r1.36 src/usr.bin/config/mkioconf.c
 cvs rdiff -u -r1.72 -r1.73 src/usr.bin/config/mkmakefile.c
 cvs rdiff -u -r1.10 -r1.11 src/usr.bin/config/pack.c

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

State-Changed-From-To: analyzed->needs-pullups
State-Changed-By: riastradh@NetBSD.org
State-Changed-When: Fri, 05 Apr 2024 00:55:06 +0000
State-Changed-Why:
fixed in HEAD, needs pullups to 10, 9, 8


>Unformatted:

Home	PR Database Search