1
\$\begingroup\$

I am building a small command interpreter to be run on a microcontroller. To queue each command and its accompanying arguments, I am using a queue implemented as a singly linked list. All of the queue operations work, however there seems to be a memory leak. When I look at the available ram at run time the numbers don't seem to add up. The program posted below under "main.c" will just queue up 100 elements of "012345", then dequeue them and report the available sram after each operation by measuring the difference between the top of the stack and the top of the heap. The behavior is a bit unusual... Please take a look at the code below, I'm sure I am just doing something remarkably stupid.

Here are a few details about the system: Microcontroller: ATmega2560-16AU Language: C, Development Environment: Atmel Studio 6 with avr gcc

main.c

#include <avr/io.h>
#include "setup.h"
#include "stdlib.h"
#include "string.h"
#include "StringQueue.h"

 #define TEST_STR "012345"

strqueue_t qCommands, qArgs;

struct gFlags
{
    uint8_t returnCharacterRecieved;
}gFlags;

enum states
{
    idle,
    invoke,
    exec,
    error
};

//testing
uint16_t free_ram();
uint16_t free_ram()
{
    extern uint16_t __heap_start, *__brkval;
    uint16_t v;
    return (uint16_t) &v - (__brkval == 0 ? (uint16_t) &__heap_start : (uint16_t) __brkval);
}

int main(void)
{
    _delay_ms(500);
    uart_init(&UART0);
    stdout = &outputStream;
    printf("-------------------------------------------------\n");
    printf("Command Interpreter Test\n");
    printf("Hardware:\n\tATmega2560p\n");
    printf("-------------------------------------------------\n");
    printf("Initialization complete...\n");
    printf("-------------------------------------------------\n");
    printf("free sram:\t%d\n", free_ram());
    printf("-------------------------------------------------\n");

    printf("creating qCommands queue...");
    queueCreate(&qCommands, 0);
    printf("free sram:\t%d\n", free_ram());
    printf("-------------------------------------------------\n");
    printf("element size:\t%d\n", strlen(TEST_STR));
    printf("-------------------------------------------------\n");

    printf("starting memory allocation test...\n");

    for(volatile uint8_t runs = 0; runs < 1; runs++)
    {
        printf("enqueueing elements...");
        for(volatile uint8_t i = 0; i < 100; i++)
        {
            enqueue(&qCommands, TEST_STR);
            puts(queueFront(&qCommands));
            printf("num elements:\t%d\n", queueSize(&qCommands));
            _delay_ms(50);
            printf("free sram:\t%d\n", free_ram());
        }

        printf("-------------------------------------------------\n");

        _delay_ms(1000);
        printf("dequeueing elements...\n");

        while(!queueIsEmpty(&qCommands))
        {
            puts(queueFront(&qCommands));
            dequeue(&qCommands);
            printf("num elements:\t%d\n", queueSize(&qCommands));
            _delay_ms(50);
            printf("free sram:\t%d\n", free_ram());
        }
    }

    printf("-------------------------------------------------\n");
    sei();
    while(1)
    {

        if(gFlags.returnCharacterRecieved)
        {
            while(uart_data_available(&UART0))
            {
                enqueue(&qArgs, (char *)uart_read_byte(&UART0));
                printf("enq value:\t%s\n", queueFront(&qArgs));
            }
            gFlags.returnCharacterRecieved = 0;
        }
    }
}

ISR(USART0_RX_vect)
{
    if(bit_is_clear(UCSR0A, UPE0))
    {
        UART0.incomingData = UDR0;
        UART0.recieveFlag  = 1;
        uint8_t i = (uint16_t)(UART0.rxHead + 1) % BUFF_SIZE;

        if(i != UART0.rxTail)
        {
            UART0.rxBuffer[UART0.rxHead] = UART0.incomingData;
            UART0.rxHead = i;
        }
    }
    else
    {
        //UDR0;
    }

    // check for return character, if received, flag main process
    if(UART0.incomingData == '\n')
    {
        gFlags.returnCharacterRecieved = 1;
    }
}

StringQueue.h

#ifndef StringQueue_h
#define StringQueue_h

#include "stdlib.h"
#include "stdint.h"
#include "string.h"
#include "stdio.h"

#define MAX_ELEMENTS 32

//!<@struct node_t
typedef struct 
{
    char * data;                //!< string for node data
    struct node_t * nodePtr;    //!< link to next node, may be NULL to indicate rear
}node_t;

//!<@strqueue_t
typedef struct 
{
    node_t *front;  //!< front node_t
    node_t *rear;   //!< rear node_t
    node_t *tempA;  //!< temp node_t for certain operations
    node_t *tempB;  //!<
    uint8_t nodeCount;      //!< current number of node_ts
    uint8_t maxElements;    //!< maximum number of node_ts
}strqueue_t; 

///
extern char * queueFront(strqueue_t * queue);
///
extern uint8_t enqueue(strqueue_t * queue, const char * str);
///
extern char * dequeue(strqueue_t * queue);
///
extern uint8_t queueIsEmpty(const strqueue_t * queue);
///
extern void queueDisplay(strqueue_t * queue);
///
extern void queueCreate(strqueue_t * queue, uint8_t elements);
///
extern uint8_t queueSize(const strqueue_t * queue);
///
extern uint8_t queueIsFull(const strqueue_t * queue);


#endif

StringQueue.c

#include "StringQueue.h"

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param strqueue_t [description]
 * @return [description]
 */
char * queueFront(strqueue_t * queue)
{
    if ((queue->front != NULL) && (queue->rear != NULL))
        return (queue->front->data);
    else
        return 0;
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param strqueue_t [description]
 * @param str [description]
 * 
 * @return [description]
 */
uint8_t enqueue(strqueue_t * queue, const char * str)
{
    // if first element and last element in queue. i.e. no allocations yet
    if(queue->rear == NULL)
    {
        queue->rear             = (node_t *)malloc(strlen(str) + sizeof(node_t) );
        queue->rear->nodePtr    = NULL; // null link
        queue->rear->data       = str;
        queue->front            = queue->rear;
    }
    // if any elements exist so fart
    else
    {
        queue->tempA            = (node_t *)malloc(strlen(str) + sizeof(node_t));
        queue->rear->nodePtr    = (queue->tempA); // link to next rear node
        queue->tempA->data      = str;
        queue->tempA->nodePtr   = NULL; //ensure rear maintains null link

        queue->rear = queue->tempA;     
    }
    return queue->nodeCount++;
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param strqueue_t [description]
 * @return [description]
 */
char * dequeue(strqueue_t * queue)
{
    queue->tempB = queue->front;
    char *tempStr = NULL;

    if(queue->tempB == NULL)
    {
        // list is empty
        return 0;
    }
    else
    {
        if (queue->tempB->nodePtr != NULL)
        {
            queue->tempB = queue->tempB->nodePtr;
            //free(queue->front->data);         // free memory occupied by the head data
            free(queue->front);             // free memory occupied by head node
            queue->front = queue->tempB;    // move head back
        }
        else
        {
            //free(queue->front->data); //  free memory occupied by the head data
            free(queue->front);         //  free memory occupied by the head node
            queue->front    = NULL;     //  reset list to empty
            queue->rear     = NULL;     //  reset list to empty
        }
        queue->nodeCount--;
    }
    return (tempStr == NULL ? 0 : tempStr);
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param queue [description]
 * @return [description]
 */
uint8_t queueIsEmpty(const strqueue_t *queue)
{
    if(queue->front == NULL && queue->rear == NULL && queue->nodeCount == 0)
        return 1;
    else
        return 0;
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param queue [description]
 * @return [description]
 */
void queueDisplay(strqueue_t *queue)
{
    queue->tempB = queue->front;

    // check for empty list
    if((queue->tempB == NULL) && (queue->rear == NULL))
    {
        //printf("Queue empty...\n");
        putchar('-');
        return;
    }

    // while list is not empty, print contents
    while(queue->tempB != queue->rear)
    {
        printf("%s\n", queue->tempB->data);
        queue->tempB = queue->tempB->nodePtr;
    }

    if(queue->tempB == queue->rear)
    {
        printf("%s\n", queue->tempB->data);
    }

}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param queue [description]
 * @param elements [description]
 */
void queueCreate(strqueue_t * queue, uint8_t elements)
{
    queue->front        =   NULL;
    queue->rear         =   NULL; 
    queue->tempA        =   NULL;
    queue->tempB        =   NULL;
    queue->nodeCount    =   0;

    if(elements == 0)
        queue->maxElements  =   MAX_ELEMENTS;
    else
        queue->maxElements  =   elements;
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param queue [description]
 * @return [description]
 */
uint8_t queueSize(const strqueue_t * queue)
{
    return queue->nodeCount;
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param queue [description]
 * @return [description]
 */
uint8_t queueIsFull(const strqueue_t *queue)
{
    if(queue->front != NULL && queue->nodeCount >= MAX_ELEMENTS)
        return 1;
    else
        return 0;
}

OUTPUT from putty

-------------------------------------------------
Command Interpreter Test
Hardware:
        ATmega2560p
-------------------------------------------------
Initialization complete...
-------------------------------------------------
free sram:      7705
-------------------------------------------------
creating qCommands queue...free sram:   7699
-------------------------------------------------
element size:   6
-------------------------------------------------
starting memory allocation test...
enqueueing elements...012345
num elements:   1
free sram:      7689
012345
num elements:   2
free sram:      7677
012345
num elements:   3
free sram:      7665
012345
num elements:   4
free sram:      7653
012345
num elements:   5
free sram:      7641
012345
num elements:   6
free sram:      7629
012345
num elements:   7
free sram:      7617
012345
num elements:   8
free sram:      7605
012345
num elements:   9
free sram:      7593
012345
num elements:   10
free sram:      7581
012345
num elements:   11
free sram:      7569
012345
num elements:   12
free sram:      7557
012345
num elements:   13
free sram:      7545
012345
num elements:   14
free sram:      7533
012345
num elements:   15
free sram:      7521
012345
num elements:   16
free sram:      7509
012345
num elements:   17
free sram:      7497
012345
num elements:   18
free sram:      7485
012345
num elements:   19
free sram:      7473
012345
num elements:   20
free sram:      7461
012345
num elements:   21
free sram:      7449
012345
num elements:   22
free sram:      7437
012345
num elements:   23
free sram:      7425
012345
num elements:   24
free sram:      7413
012345
num elements:   25
free sram:      7401
012345
num elements:   26
free sram:      7389
012345
num elements:   27
free sram:      7377
012345
num elements:   28
free sram:      7365
012345
num elements:   29
free sram:      7353
012345
num elements:   30
free sram:      7341
012345
num elements:   31
free sram:      7329
012345
num elements:   32
free sram:      7317
012345
num elements:   33
free sram:      7305
012345
num elements:   34
free sram:      7293
012345
num elements:   35
free sram:      7281
012345
num elements:   36
free sram:      7269
012345
num elements:   37
free sram:      7257
012345
num elements:   38
free sram:      7245
012345
num elements:   39
free sram:      7233
012345
num elements:   40
free sram:      7221
012345
num elements:   41
free sram:      7209
012345
num elements:   42
free sram:      7197
012345
num elements:   43
free sram:      7185
012345
num elements:   44
free sram:      7173
012345
num elements:   45
free sram:      7161
012345
num elements:   46
free sram:      7149
012345
num elements:   47
free sram:      7137
012345
num elements:   48
free sram:      7125
012345
num elements:   49
free sram:      7113
012345
num elements:   50
free sram:      7101
012345
num elements:   51
free sram:      7089
012345
num elements:   52
free sram:      7077
012345
num elements:   53
free sram:      7065
012345
num elements:   54
free sram:      7053
012345
num elements:   55
free sram:      7041
012345
num elements:   56
free sram:      7029
012345
num elements:   57
free sram:      7017
012345
num elements:   58
free sram:      7005
012345
num elements:   59
free sram:      6993
012345
num elements:   60
free sram:      6981
012345
num elements:   61
free sram:      6969
012345
num elements:   62
free sram:      6957
012345
num elements:   63
free sram:      6945
012345
num elements:   64
free sram:      6933
012345
num elements:   65
free sram:      6921
012345
num elements:   66
free sram:      6909
012345
num elements:   67
free sram:      6897
012345
num elements:   68
free sram:      6885
012345
num elements:   69
free sram:      6873
012345
num elements:   70
free sram:      6861
012345
num elements:   71
free sram:      6849
012345
num elements:   72
free sram:      6837
012345
num elements:   73
free sram:      6825
012345
num elements:   74
free sram:      6813
012345
num elements:   75
free sram:      6801
012345
num elements:   76
free sram:      6789
012345
num elements:   77
free sram:      6777
012345
num elements:   78
free sram:      6765
012345
num elements:   79
free sram:      6753
012345
num elements:   80
free sram:      6741
012345
num elements:   81
free sram:      6729
012345
num elements:   82
free sram:      6717
012345
num elements:   83
free sram:      6705
012345
num elements:   84
free sram:      6693
012345
num elements:   85
free sram:      6681
012345
num elements:   86
free sram:      6669
012345
num elements:   87
free sram:      6657
012345
num elements:   88
free sram:      6645
012345
num elements:   89
free sram:      6633
012345
num elements:   90
free sram:      6621
012345
num elements:   91
free sram:      6609
012345
num elements:   92
free sram:      6597
012345
num elements:   93
free sram:      6585
012345
num elements:   94
free sram:      6573
012345
num elements:   95
free sram:      6561
012345
num elements:   96
free sram:      6549
012345
num elements:   97
free sram:      6537
012345
num elements:   98
free sram:      6525
012345
num elements:   99
free sram:      6513
012345
num elements:   100
free sram:      6501
-------------------------------------------------
dequeueing elements...
012345
num elements:   99
free sram:      6501
012345
num elements:   98
free sram:      6501
012345
num elements:   97
free sram:      6501
012345
num elements:   96
free sram:      6501
012345
num elements:   95
free sram:      6501
012345
num elements:   94
free sram:      6501
012345
num elements:   93
free sram:      6501
012345
num elements:   92
free sram:      6501
012345
num elements:   91
free sram:      6501
012345
num elements:   90
free sram:      6501
012345
num elements:   89
free sram:      6501
012345
num elements:   88
free sram:      6501
012345
num elements:   87
free sram:      6501
012345
num elements:   86
free sram:      6501
012345
num elements:   85
free sram:      6501
012345
num elements:   84
free sram:      6501
012345
num elements:   83
free sram:      6501
012345
num elements:   82
free sram:      6501
012345
num elements:   81
free sram:      6501
012345
num elements:   80
free sram:      6501
012345
num elements:   79
free sram:      6501
012345
num elements:   78
free sram:      6501
012345
num elements:   77
free sram:      6501
012345
num elements:   76
free sram:      6501
012345
num elements:   75
free sram:      6501
012345
num elements:   74
free sram:      6501
012345
num elements:   73
free sram:      6501
012345
num elements:   72
free sram:      6501
012345
num elements:   71
free sram:      6501
012345
num elements:   70
free sram:      6501
012345
num elements:   69
free sram:      6501
012345
num elements:   68
free sram:      6501
012345
num elements:   67
free sram:      6501
012345
num elements:   66
free sram:      6501
012345
num elements:   65
free sram:      6501
012345
num elements:   64
free sram:      6501
012345
num elements:   63
free sram:      6501
012345
num elements:   62
free sram:      6501
012345
num elements:   61
free sram:      6501
012345
num elements:   60
free sram:      6501
012345
num elements:   59
free sram:      6501
012345
num elements:   58
free sram:      6501
012345
num elements:   57
free sram:      6501
012345
num elements:   56
free sram:      6501
012345
num elements:   55
free sram:      6501
012345
num elements:   54
free sram:      6501
012345
num elements:   53
free sram:      6501
012345
num elements:   52
free sram:      6501
012345
num elements:   51
free sram:      6501
012345
num elements:   50
free sram:      6501
012345
num elements:   49
free sram:      6501
012345
num elements:   48
free sram:      6501
012345
num elements:   47
free sram:      6501
012345
num elements:   46
free sram:      6501
012345
num elements:   45
free sram:      6501
012345
num elements:   44
free sram:      6501
012345
num elements:   43
free sram:      6501
012345
num elements:   42
free sram:      6501
012345
num elements:   41
free sram:      6501
012345
num elements:   40
free sram:      6501
012345
num elements:   39
free sram:      6501
012345
num elements:   38
free sram:      6501
012345
num elements:   37
free sram:      6501
012345
num elements:   36
free sram:      6501
012345
num elements:   35
free sram:      6501
012345
num elements:   34
free sram:      6501
012345
num elements:   33
free sram:      6501
012345
num elements:   32
free sram:      6501
012345
num elements:   31
free sram:      6501
012345
num elements:   30
free sram:      6501
012345
num elements:   29
free sram:      6501
012345
num elements:   28
free sram:      6501
012345
num elements:   27
free sram:      6501
012345
num elements:   26
free sram:      6501
012345
num elements:   25
free sram:      6501
012345
num elements:   24
free sram:      6501
012345
num elements:   23
free sram:      6501
012345
num elements:   22
free sram:      6501
012345
num elements:   21
free sram:      6501
012345
num elements:   20
free sram:      6501
012345
num elements:   19
free sram:      6501
012345
num elements:   18
free sram:      6501
012345
num elements:   17
free sram:      6501
012345
num elements:   16
free sram:      6501
012345
num elements:   15
free sram:      6501
012345
num elements:   14
free sram:      6501
012345
num elements:   13
free sram:      6501
012345
num elements:   12
free sram:      6501
012345
num elements:   11
free sram:      6501
012345
num elements:   10
free sram:      6501
012345
num elements:   9
free sram:      6501
012345
num elements:   8
free sram:      6501
012345
num elements:   7
free sram:      6501
012345
num elements:   6
free sram:      6501
012345
num elements:   5
free sram:      6501
012345
num elements:   4
free sram:      6501
012345
num elements:   3
free sram:      6501
012345
num elements:   2
free sram:      6501
012345
num elements:   1
free sram:      6501
012345
num elements:   0
free sram:      7701
-------------------------------------------------
\$\endgroup\$
  • \$\begingroup\$ I'm not so sure that this is a memory leak, but maybe an error in the implementation for calculating the available sram? \$\endgroup\$ – Luke Gary Jun 18 '15 at 21:56
  • \$\begingroup\$ Yeah I agree with Luke - have a look at how you are calculating available sram. I suspect it has something to do with you freeing memory blocks from the front of the queue and this is leaving a hole at the start of the heap that is not accounted for in your calculation. Between allocating elements and freeing them all there is no memory leak, so it doesn't look like malloc/free are the issue. \$\endgroup\$ – Jon Jun 18 '15 at 22:05
1
\$\begingroup\$

I am surprised that there is code that actually decreases __brkval, as free heap is usually collected in a "free blocks" list.

Your two bytes missing at the end might be actually the stack, because the compiler needed some space for a local variable.

Note that your "free RAM" calculation shows you too much free RAM, as interrups and function calls will take additional stack space. Remember that stack grows "downwards" to heap.

\$\endgroup\$
  • \$\begingroup\$ Thank you Turbo J, I will investigate a better free ram calculation! Do you have any recommendations? \$\endgroup\$ – Luke Gary Jun 19 '15 at 17:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.