3
\$\begingroup\$

I'm trying to learn C and memory management, therefore as an exercise I've written a memory allocator. I've taken the best fit algorithm and added multithreading with locks. I'm a beginner with multithreading in C and therefore I would like your suggestions.

It is the same project as in my previous question and the code is openly available in a github repo.

I'm trying to achieve something similar as in this question.

Bottom up, the data structure is in the file openmalloc.h

#ifndef _openmalloc_h_
#define _openmalloc_h_

#include <string.h>
#include <pthread.h>
/*
 * The strategy (allocation algorithm) to use. Choose from:
 * 1) First fit
 * 2) Best fit
 * 3) Worst fit
 * 4) Quick fit
 * 5) Multithreaded fit
 */
#ifndef STRATEGY
#define STRATEGY 5
#endif

/*
 * The number of lists to use in the Quick fit algorithm implementation.
 */
#ifndef NRQUICKLISTS
#define NRQUICKLISTS 4
#endif

/*
 * The minimum #units to request when asking system for more memory.
 */
#define NALLOC 1024

typedef long Align; /* for alignment to long boundary */

union header {
    /* block header */
    struct {
        union header *ptr;/* next block if on free list */
        unsigned size;
        /* size of this block */
        pthread_mutex_t lock;
    } s;
    Align x;
    /* force alignment of blocks */
};
typedef union header Header;

void *malloc(size_t size);
void free(void *ptr);
void *realloc(void *ptr, size_t size);
static Header *morecore(unsigned nu);

#endif /* _malloc_h */

The multithreaded malloc is in the file mthreadfit.c

/* multithreaded fit openmalloc
 *
 * This module contains the function that implements the multithreaded malloc
 * strategy, malloc_mthread().
 *
 */

#include <limits.h>

/* malloc_mthread
 *
 * malloc_mthread returns the start address of the newly allocated memory.
 * It implements the multithreaded best fit algorithm, which tries to find the smallest free
 * block that is large enough.
 *
 */
/* number of bytes of memory to allocate */
void *malloc_mthread(size_t nbytes) {
    Header *p, *prevp;
    unsigned nunits, min_size = INT_MAX;
    Header *minp = NULL, *minprevp = NULL;

    nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
    if ((prevp = freep) == NULL) { /* no free list yet */
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    pthread_mutex_init(&base.s.lock, NULL);
    pthread_mutex_lock(&base.s.lock);
    /*
     * Iterate over the free list and find the smallest block that is large
     * enough to hold nbytes of data.
     */

    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) { /* big enough */
            if (p->s.size == nunits) { /* exactly */
                prevp->s.ptr = p->s.ptr;
                freep = prevp;
                pthread_mutex_unlock(&base.s.lock);
                return (void *) (p + 1);
            }
            else {
                if (minp == NULL || p->s.size < min_size) {
                    minp = p;
                    minprevp = prevp;
                    min_size = minp->s.size;
                }
            }
        }
        if (p == freep) { /* wrapped around free list */
            if (minp != NULL) {
                /* allocate tail end */
                minp->s.size -= nunits;
                minp += minp->s.size;
                minp->s.size = nunits;
                freep = minprevp;
                pthread_mutex_unlock(&base.s.lock);
                return (void *) (minp + 1);
            }
            if ((p = morecore(nunits)) == NULL) {
                pthread_mutex_unlock(&base.s.lock);
                return NULL; /* none left */
            }
        }
    }
}

The actual malloc is just wrapper code depending on which algorithm that is used, located in the file openmalloc.c.

#include "brk.h"
#include "openmalloc.h"
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/*
 * An empty list to get started.
 */
static Header base;

/*
 * Start of the free list, in non-Quick fit strategies.
 */
static Header *freep = NULL;

/* Include the different malloc implementation source files here. */
#include "firstfit.c"
#include "bestfit.c"
#include "worstfit.c"
#include "quickfit.c"
#include "mthreadfit.c"

/* malloc
 *
 * malloc returns the start address of dynamically allocated memory.
 * This is simply a wrapper function that calls the different algorithm
 * implementations depending on the value of STRATEGY.
 *
 */
/* number of bytes of memory to allocate */
void *malloc(size_t nbytes) {
    if (nbytes == 0) {
        return NULL;
    }

#if   STRATEGY == 1
    return malloc_first(nbytes);
#elif STRATEGY == 2
    return malloc_best(nbytes);
#elif STRATEGY == 3
    return malloc_worst(nbytes);
#elif STRATEGY == 4
    return malloc_quick(nbytes);
#elif STRATEGY == 5
    return malloc_mthread(nbytes);
#else
    exit(1);
#endif
}


/* morecore
 *
 * morecore asks system for more memory and returns pointer to it.
 *
 */
/* the amount of memory to ask for (in Header-sized units) */
static Header *morecore(unsigned nu) {
    char *cp;
    Header *up;
    if (nu < NALLOC)
        nu = NALLOC;
    cp = sbrk(nu * sizeof(Header));
    if (cp == (char *) -1) /* no space at all */
        return NULL;
    up = (Header *) cp;
    up->s.size = nu;
    free((void *) (up + 1));
    return freep;
}


/* free
 *
 * Put block ap in free list.
 */
/* pointer to data part of allocated memory block */
void free(void *ap) {
#if STRATEGY == 4
    int list_index;
    Header* old_first_free;
#endif

    if (ap == NULL) {
        return;
    }

    Header *bp, *p;
    bp = (Header *) ap - 1;

    if (bp->s.size <= 0) {
        return;
    }


    /*
     * For the Quick fit strategy, if allocated memory block has been stored in
     * a quick list, simply put the whole block back and return.
     */

#if STRATEGY == 4
    list_index = qindex(sizeof(Header) * (bp->s.size - 1));
    if (list_index < NRQUICKLISTS) {
        old_first_free = quick_fit_lists[list_index];
        quick_fit_lists[list_index] = bp;
        bp->s.ptr = old_first_free;
        return;
    }
#endif


    /*
     * Merge free memory blocks if the one being freed is adjacent to another
     * free one,
     */

    /* point to block header */
    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break; /* freed block at start or end of arena */


    if (bp + bp->s.size == p->s.ptr) {
        /* join to upper nbr */
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr = p->s.ptr->s.ptr;
    } else
        bp->s.ptr = p->s.ptr;

    if (p + p->s.size == bp) {
        /* join to lower nbr */
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    } else
        p->s.ptr = bp;

    freep = p;
}

/* realloc
 *
 * realloc changes size of the given memory block and returns pointer to new
 */
/* pointer to memory block to resize */
/* the new size, in bytes */
void *realloc(void *ptr, size_t size) {
    Header *bp, *p;

    /*
     * Take care of some simple, basic cases like when the given pointer is
     * NULL or the size is non-positive.
     */

    if (ptr == NULL) {
        return malloc(size);
    } else if (size <= 0) {
        free(ptr);
        return NULL;
    }

    bp = (Header *) ptr - 1;
    unsigned int numbytes = sizeof(Header) * (bp->s.size - 1);

    if (size == numbytes) {
        return ptr; /* stop and return here if no resize is necessary */
    }


    /*
     * Simply allocate as much memory as the new size and copy the old data
     * into the new place. Then free the previously allocated memory.
     */

    p = malloc(size);
    if (p == NULL) {
        return NULL;
    }

    if (size < numbytes) {
        numbytes = size;
    }

    memcpy(p, ptr, numbytes);
    free(ptr);

    return p;
}

To test my malloc with the STRATEGY=5 the file with tests RUN_TESTS is used.

#!/bin/sh
echo "-- Testing your implementation of malloc --"
echo ""
echo "- If you have any problem in passing a test read the corresponding"
echo "- source file to understand what the test is checking"
echo ""
echo -n "********************* TEST MERGE ... "
read answ
./tstmerge
echo -n "********************* TEST ALGORITHMS ... "
read answ
./tstalgorithms
echo -n "********************* TEST EXTREME USAGE ... "
read ans
./tstextreme
echo -n "********************* TEST MALLOC ... "
read ans
./tstmalloc
echo -n "********************* TEST MEMORY ... "
read ans
./tstmemory
echo -n "********************* TEST REALLOC ... "
read ans
./tstrealloc
echo -n "********************* TEST CRASH  SIMPLE ... "
read ans
./tstcrash_simple
echo -n "********************* TEST CRASH COMPLEX ...  "
read ans
./tstcrash_complex

A typical test (tstmerge.c) looks like the following code.

#include <stdio.h>
#include <stdlib.h>
#include "brk.h"
#include <unistd.h>

#define SIZE 16384

int main(int argc, char * argv[])
{

  void *p1, *p2,  *oldBrk, *newBrk1, *newBrk2;
  unsigned long largeSize = SIZE;

  oldBrk = (void *)sbrk(0);

  p1 = (void *)malloc(1);

  newBrk1 = (void *) sbrk(0);

  largeSize = ((unsigned long)(newBrk1-oldBrk) > SIZE ? (unsigned long)(newBrk1-oldBrk) : SIZE);

  free(p1);

  printf("-- Testing merging of deallocated large blocks ( >= %u bytes)\n", (unsigned)largeSize);

  p1 = (void *)malloc(largeSize);
  p2 = (void *)malloc(largeSize);

  if(p1 == NULL || p2 == NULL) printf("* ERROR: unable to allocate memory of size %u bytes\n", (unsigned) largeSize);

  newBrk1 = (void *)sbrk(0);

  free(p1);
  free(p2);

  p1 = (void *)malloc(largeSize * 2);

  if(p1 == NULL) printf("* ERROR: unable to allocate memory of size %u bytes\n", (unsigned)largeSize);

  newBrk2 = (void *)sbrk(0);

  if(((double)(newBrk2 - oldBrk))/((double)(newBrk1 - oldBrk)) > 1)
    printf("* ERROR: not good enough usage of memory (probably incorrect merging of deallocated memory blocks)\nYour implementation used %u bytes more than expected\n", ((unsigned)(newBrk2-newBrk1)));
  else
    printf("Test passed OK\n");
  exit(0);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.