Date: Sun, 1 Apr 2007 06:22:35 GMT From: Brian Walenz<thebri@gmail.com> To: freebsd-gnats-submit@FreeBSD.org Subject: kern/111085: [patch] qsort fails on large (> 2GB) arrays Message-ID: <200704010622.l316MZZq001719@www.freebsd.org> Resent-Message-ID: <200704010630.l316U5B9003305@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
>Number: 111085
>Category: kern
>Synopsis: [patch] qsort fails on large (> 2GB) arrays
>Confidential: no
>Severity: non-critical
>Priority: low
>Responsible: freebsd-bugs
>State: open
>Quarter:
>Keywords:
>Date-Required:
>Class: sw-bug
>Submitter-Id: current-users
>Arrival-Date: Sun Apr 01 06:30:05 GMT 2007
>Closed-Date:
>Last-Modified:
>Originator: Brian Walenz
>Release: 6.2-RELEASE
>Organization:
>Environment:
FreeBSD xxxx 6.2-RELEASE FreeBSD 6.2-RELEASE #2: Tue Mar 27 20:00:46 EDT 2007 xxxx:/usr/src/sys/amd64/compile/TWOBYFOUR amd64
>Description:
qsort(3) fails if given an array of many small elements, where the total size of the array is >> 2GB. Exact conditions not known; 200 million 16 byte elements (~3GB total size) fails.
>How-To-Repeat:
Compile and run (needs > 3GB core):
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
typedef struct {
uint64_t x;
uint64_t a;
} thing;
int
cmp(const void *a, const void *b) {
thing const *A = (thing const *)a;
thing const *B = (thing const *)b;
if (A->x < B->x) return(-1);
if (A->x > B->x) return(1);
return(0);
}
int
main(int argc, char **argv) {
uint64_t i;
uint64_t Tn;
thing *T;
srand48(4);
Tn = 3; Tn *= 1024; Tn *= 1024; Tn *= 1024;
Tn /= sizeof(thing);
T = (thing *)malloc(sizeof(thing) * Tn);
if (T == NULL)
exit(1);
fprintf(stderr, "building %lu %lu\n", Tn, Tn * sizeof(thing));
for (i=0; i<Tn; i++)
T[i].x = lrand48();
fprintf(stderr, "sorting\n");
qsort(T, Tn, sizeof(thing), cmp);
fprintf(stderr, "sorted\n");
free(T);
exit(0);
}
>Fix:
In /usr/src/lib/libc/stdlib/qsort.c, line 118, change the type of 'd and 'r' from int to long.
>Release-Note:
>Audit-Trail:
>Unformatted:
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200704010622.l316MZZq001719>