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

Brian Walenz thebri at
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
>Class:          sw-bug
>Submitter-Id:   current-users
>Arrival-Date:   Sun Apr 01 06:30:05 GMT 2007
>Originator:     Brian Walenz
>Release:        6.2-RELEASE
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
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.

Compile and run (needs > 3GB core):

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

typedef struct {
  uint64_t x;
  uint64_t a;
} thing;

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);

main(int argc, char **argv) {
  uint64_t  i;
  uint64_t  Tn;
  thing    *T;


  Tn  = 3; Tn *= 1024; Tn *= 1024; Tn *= 1024;
  Tn /= sizeof(thing);

  T  = (thing *)malloc(sizeof(thing) * Tn);
  if (T == NULL)

  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");

In /usr/src/lib/libc/stdlib/qsort.c, line 118, change the type of 'd and 'r' from int to long.


More information about the freebsd-bugs mailing list