On Fri, Apr 29, 2011 at 12:42 PM, Solar Designer <solar@openwall.com> wrote:

> JIghtuse -
>
> On Wed, Apr 27, 2011 at 10:24:15AM +0700, JIghtuse wrote:
> > So, I am still working on testing malloc() of musl. My coding breaks by
> > some increase of studing in university, but I have to say I want to
> > participate. Is it real to join Summer of Security?
>
> Sure.  Thanks for the status update.
>
> > After finished musl tests
>
> Luka is the primary person to work on these, but you're welcome to stay
> involved as well - e.g., you may help test Luka's tests against more
> libc's, report problems in here (both those of the tests and of the
> libc's), and improve the tests.
>
> > I want to try blists development also.
>
> Sounds good.  This is off-topic for the musl list, though, so please
> e-mail me off-list for it when you're ready.
>
> Thanks,
>
> Alexander
>
> P.S. Somehow you started a new thread instead of posting to the existing
> thread with the same Subject.  You should have used "reply" on a message
> in the proper thread.
>

So, my program creates array of structures of memory blocks and works with
it.
Source code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#define M 100000000
#define REPEATS 10

struct block {
    unsigned int* ptr;
    unsigned int size;
} blocks[M / 100];

int by_size(const void *, const void *);
int by_address(const void *, const void *);

int main(int argc, char *argv[])
{
    unsigned int i = 0, j, counter;
    unsigned int seed;
    unsigned int amount = 0;
    unsigned int size;

    if (argc > 1) {
        seed = atoi(argv[1]);
    } else {
        printf("Type seed: ");
        scanf("%u", &seed);
    }

    bzero(blocks, sizeof(blocks[0]) * (M / 100));

    for (counter = 0; counter < REPEATS; counter++) {
        while (amount < M) {
            size = rand() % (M / 100);
            if (size > 100000) {
                size |= 0xff0;
            }

            blocks[i].size = size;
            blocks[i].ptr = malloc(sizeof(int) * size);
            if (blocks[i].ptr == NULL) {
                printf("\nmalloc() error!\n");
                exit(EXIT_FAILURE);
            }
            amount += blocks[i].size;
            i++;
        }

        if (counter != REPEATS - 1) {
            qsort(blocks, i, sizeof(struct block), by_size);
            for (j = i / 4; j < i; j++) {
                amount -= blocks[j].size;
                free(blocks[j].ptr);
            }
            bzero((void *)(blocks + i / 4), sizeof(blocks[0]) * ((i / 4) * 3
+ 3));
            i /= 4;
        } else {
            qsort(blocks, i, sizeof(struct block), by_address);
        }
    }

    printf("%5s %12s %8s\n", "No.", "Address", "Size");
    for (j = 0; j < i - 1; j++) {
        printf("%5u %12u %8u\n", j, (unsigned int)blocks[j].ptr,
blocks[j].size);
        if (blocks[j].ptr + blocks[j].size >= blocks[j + 1].ptr) {
            printf("\nOverlaped!\n");
            exit(EXIT_SUCCESS);
        }
    }
    printf("%5u %12u %8u\n", j, (unsigned int)blocks[j].ptr,
blocks[j].size);
    exit (EXIT_SUCCESS);
}

int by_size(const void * a, const void * b)
{
  struct block *ia = (struct block *)a;
  struct block *ib = (struct block *)b;
  return (int)(ia->size - ib->size);
}

int by_address(const void * a, const void * b)
{
    struct block *ia = (struct block *)a;
    struct block *ib = (struct block *)b;
    return (void *)ia->ptr > (void *)ib->ptr;
}




Sample output:
  No.      Address     Size
    0    167530504     5211
    1    167551352    21530
    2    167637480    18456
    3    167711312    28624
<...>
  266   3071238152    36159
  267   3071651848    33333
  268   3073114120   204799
  269   3073937416   794617


I tried to plot this data with gnuplot, but it'll require parting data at
two or more parts because of big address range.