kern/111085: [patch] qsort fails on large (> 2GB) arrays

Brian Walenz thebri at gmail.com
Sun Apr 1 06:30:06 UTC 2007


>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:


More information about the freebsd-bugs mailing list