Insufficient memory available

[nilmerg]

Hello.

The following nxc code that I have written causes a file error -5 at line 588 when it is about to call "follow_way". My experience with NXC and C or C++ is very limited so I have no idea why this is happening. I noticed already that the array definition at line 580 and lastly its initialisation at line 581 causes the used memory to increase by around 3 KB. I thought the long datatype needs just 4 Byte so the array needs only 2304 bytes? Additionally I pass the array to "follow_way" by reference so why do I get this error? (Even if I disable the movement and collision task so that they do not initialise those two global arrays it is failing.)

It would be great if someone has an idea how to fix it.

(The robot is using the enhanced firmware v132, 02-25-12)

Code: Select all

// The ports the robot is going to use.
#define BOTH_WHEELS OUT_AB
#define RIGHT_WHEEL OUT_A
#define LEFT_WHEEL OUT_B
#define COLOR_SENSOR IN_1
#define LIGHT_SENSOR IN_2
#define US_SENSOR IN_4

const int ROBOT_SPEED = 100; // At which speed should the robot drive?
const int COLLISION_TRESHOLD = 10; // When should a collision be triggered?
const int LIGHT_TRESHOLD = 40; // When should the light sensor be triggered?

const int WHITE_COLOR = 6; // These should be the color values the color
const int BLACK_COLOR = 4; // sensor will detect on your surfaces.
const int RED_COLOR = 5;

const int DESTINATION_TIMEOUT = 2000; // How long must a blockade be present so
                                      // that the robot identifies it as the
                                      // destination? (in milliseconds)

// How many time (in milliseconds) needs the robot to turn
// by 90 degrees when it is driving at full speed?
const int NINETY_DEGREE_TURN_DURATION = 465;

// These are the signals the movement and the controller
// task will use to communicate with each other.
const int SIG_STOP_RIGHT = 0;
const int SIG_STOP_LEFT = 1;
const int SIG_STOP_BOTH = 2;
const int SIG_FORWARD_RIGHT = 3;
const int SIG_FORWARD_LEFT = 4;
const int SIG_FORWARD_BOTH = 5;
const int SIG_REVERSE_RIGHT = 6;
const int SIG_REVERSE_LEFT = 7;
const int SIG_REVERSE_BOTH = 8;
const int SIG_RIGHT_TURN = 9;
const int SIG_LEFT_TURN = 10;

// The following signals are used by the collision task
// to notify the controller about a imminent collision.
const int SIG_BLOCKED_WAY = 11;
const int SIG_CLEAR_WAY = 12;

// The size of these arrays seems a bit high at first but it is necessary as
// we are going to use every index only once. (A poor man's fifo queue...)
int COLLISION_SIGNALS[32];
int MOVE_SIGNALS[64][2]; // [signal, speed]

// To avoid race conditions when accessing the two
// arrays above we need a mutex for each of those.
mutex COLLISION_MUTEX, MOVE_MUTEX;

// These globals are used to notify a task that it should stop.
bool EVT_COLLISION, EVT_MOVEMENT = false;

// This global is used to notify the controller about a finished turn request.
bool EVT_TURN_FINISHED = false;


// Some prototypes...
void send_movement_signal(int index, int signal, int speed=-1);
void way_back(long way_data[][], int next_move_index);
void send_collision_signal(int index, int signal);
int follow_way(long &known_ways[][][], int way);
void turn(int &wheel_states[][], bool left);
bool check_collision_signal(int index);
bool check_movement_signal(int index);
int detect_way(void);


/*
Makes the robot to perform a turn by 90 degrees.

The function handles the direction in which the
robot is currently driving automatically.

Note that you have to set NINETY_DEGREE_TURN_DURATION
to a reasonable value if you want proper results!
*/
void turn(int &wheel_states[][], bool left)
{
    int opposite_speed, speed, opposite_port, port;
    bool forward;
    
    // When determining the wheel which needs to be stopped we assume
    // that both wheels are spinning into the same direction.
    if (left) {
        if (wheel_states[0][0]) {
            forward = true;
            port = LEFT_WHEEL;
            speed = wheel_states[0][1];
            opposite_port = RIGHT_WHEEL;
            opposite_speed = wheel_states[1][1];
        } else {
            forward = false;
            port = RIGHT_WHEEL;
            speed = wheel_states[1][1];
            opposite_port = LEFT_WHEEL;
            opposite_speed = wheel_states[0][1];
        }
    } else {
        if (wheel_states[0][0]) {
            forward = true;
            port = RIGHT_WHEEL;
            speed = wheel_states[1][1];
            opposite_port = LEFT_WHEEL;
            opposite_speed = wheel_states[0][1];
        } else {
            forward = false;
            port = LEFT_WHEEL;
            speed = wheel_states[0][1];
            opposite_port = RIGHT_WHEEL;
            opposite_speed = wheel_states[1][1];
        }
    }
    
    Off(port);
    Wait(NINETY_DEGREE_TURN_DURATION * (100 / opposite_speed));
    Off(opposite_port); // As we are using the synchronsation feature of NXT
                        // we have to reset both wheels before the feature
                        // gets reinitiated.
    
    if (forward) {
        OnFwdReg(BOTH_WHEELS, speed, OUT_REGMODE_SYNC);
    } else {
        OnRevReg(BOTH_WHEELS, speed, OUT_REGMODE_SYNC);
    }
    
    EVT_TURN_FINISHED = true;
}


/*
Inserts a new movement signal into the queue on the given index.

If signal is SIG_LEFT_TURN or SIG_RIGHT_TURN the function blocks
until the requested turn has been completed.
*/
void send_movement_signal(int index, int signal, int speed=-1)
{
    Acquire(MOVE_MUTEX);
    MOVE_SIGNALS[index][0] = signal;
    MOVE_SIGNALS[index][1] = speed;
    Release(MOVE_MUTEX);
    
    if (signal == SIG_LEFT_TURN || signal == SIG_RIGHT_TURN) {
        until (EVT_TURN_FINISHED);
        EVT_TURN_FINISHED = false;
    }
}


/*
Checks if a movement signal exists in the queue on the given index.
*/
bool check_movement_signal(int index)
{
    bool found_signal = false;
    
    Acquire(MOVE_MUTEX);
    if (MOVE_SIGNALS[index][0] != -1) {
        found_signal = true;
    }
    Release(MOVE_MUTEX);
    
    return found_signal;
}


/*
This task is responsible for the entire movement of the robot. It receives
signals sent by the controller and will perform the requested actions.
*/
task movement()
{
    // As this task gets started/stopped randomly we have to clear our queue.
    int value[2] = {-1, -1};
    ArrayInit(MOVE_SIGNALS, value, 64);
    
    int next_index = 0;
    bool keep_running = true;
    int current_states[2][2] = {0, 0, 0, 0}; // [left, right][direction, speed]
    
    while (keep_running)
    {
        if (check_movement_signal(next_index))
        {
            switch (MOVE_SIGNALS[next_index][0])
            {
                case SIG_STOP_RIGHT:
                    Off(RIGHT_WHEEL);
                    current_states[1][1] = 0;
                    break;
                case SIG_STOP_LEFT:
                    Off(LEFT_WHEEL);
                    current_states[0][1] = 0;
                    break;
                case SIG_STOP_BOTH:
                    Off(BOTH_WHEELS);
                    current_states[1][1] = 0;
                    current_states[0][1] = 0;
                    break;
                case SIG_FORWARD_RIGHT:
                    current_states[1][0] = 1;
                    current_states[1][1] = MOVE_SIGNALS[next_index][1];
                    if (current_states[1][1] == current_states[0][1] &&
                            current_states[1][0] == current_states[0][0]) {
                        Off(BOTH_WHEELS);
                        OnFwdReg(BOTH_WHEELS, current_states[1][1],
                                 OUT_REGMODE_SYNC);
                    } else {
                        OnFwd(RIGHT_WHEEL, current_states[1][1]);
                    }
                    break;
                case SIG_FORWARD_LEFT:
                    current_states[0][0] = 1;
                    current_states[0][1] = MOVE_SIGNALS[next_index][1];
                    if (current_states[0][1] == current_states[1][1] &&
                            current_states[0][0] == current_states[1][0]) {
                        Off(BOTH_WHEELS);
                        OnFwdReg(BOTH_WHEELS, current_states[0][1],
                                 OUT_REGMODE_SYNC);
                    } else {
                        OnFwd(LEFT_WHEEL, current_states[0][1]);
                    }
                    break;
                case SIG_FORWARD_BOTH:
                    if (current_states[0][1] > 0 || current_states[1][1] > 0) {
                        Off(BOTH_WHEELS);
                    }
                    OnFwdReg(BOTH_WHEELS, MOVE_SIGNALS[next_index][1],
                             OUT_REGMODE_SYNC);
                    current_states[1][0] = 1;
                    current_states[1][1] = MOVE_SIGNALS[next_index][1];
                    current_states[0][0] = 1;
                    current_states[0][1] = MOVE_SIGNALS[next_index][1];
                    break;
                case SIG_REVERSE_RIGHT:
                    current_states[1][0] = 0;
                    current_states[1][1] = MOVE_SIGNALS[next_index][1];
                    if (current_states[1][1] == current_states[0][1] &&
                            current_states[1][0] == current_states[0][0]) {
                        Off(BOTH_WHEELS);
                        OnRevReg(BOTH_WHEELS, current_states[1][1],
                                 OUT_REGMODE_SYNC);
                    } else {
                        OnRev(RIGHT_WHEEL, current_states[1][1]);
                    }
                    break;
                case SIG_REVERSE_LEFT:
                    current_states[0][0] = 0;
                    current_states[0][1] = MOVE_SIGNALS[next_index][1];
                    if (current_states[0][1] == current_states[1][1] &&
                            current_states[0][0] == current_states[1][0]) {
                        Off(BOTH_WHEELS);
                        OnRevReg(BOTH_WHEELS, current_states[0][1],
                                 OUT_REGMODE_SYNC);
                    } else {
                        OnRev(LEFT_WHEEL, current_states[0][1]);
                    }
                    break;
                case SIG_REVERSE_BOTH:
                    if (current_states[0][1] > 0 || current_states[1][1] > 0) {
                        Off(BOTH_WHEELS);
                    }
                    OnRevReg(BOTH_WHEELS, MOVE_SIGNALS[next_index][1],
                             OUT_REGMODE_SYNC);
                    current_states[1][0] = 0;
                    current_states[1][1] = MOVE_SIGNALS[next_index][1];
                    current_states[0][0] = 0;
                    current_states[0][1] = MOVE_SIGNALS[next_index][1];
                    break;
                case SIG_RIGHT_TURN:
                    turn(current_states, false);
                    break;
                case SIG_LEFT_TURN:
                    turn(current_states, true);
                    break;
            }
            next_index++;
        } else {
            if (EVT_MOVEMENT) {
                EVT_MOVEMENT = false;
                keep_running = false;
            } else {
                Wait(25); // To not to waste cpu cycles the task should sleep
                          // a reasonable small amount of milliseconds.
            }
        }
    }
}


/*
Inserts a new collision signal into the queue on the given index.
*/
void send_collision_signal(int index, int signal)
{
    Acquire(COLLISION_MUTEX);
    COLLISION_SIGNALS[index] = signal;
    Release(COLLISION_MUTEX);
}


/*
Checks if a collision signal exists in the queue on the given index.
*/
bool check_collision_signal(int index)
{
    bool found_signal = false;
    
    Acquire(COLLISION_MUTEX);
    if (COLLISION_SIGNALS[index] != -1) {
        found_signal = true;
    }
    Release(COLLISION_MUTEX);
    
    return found_signal;
}


/*
This task is responsible for the collision detection of the robot. It will send
signals to the controller when there is a blockade on the way and when a
previously detected blockade has gone.
*/
task collision()
{
    ArrayInit(COLLISION_SIGNALS, -1, 32);
    
    // We initialise the ultra sonic sensor at first.
    SetSensorLowspeed(US_SENSOR);
    
    bool contact = false;
    bool keep_running = true;
    int distance, next_index = 0;
    
    while (keep_running)
    {
        if (EVT_COLLISION) {
            EVT_COLLISION = false;
            keep_running = false;
        } else {
            distance = SensorUS(US_SENSOR);
            if (!contact && distance <= COLLISION_TRESHOLD) {
                send_collision_signal(next_index++, SIG_BLOCKED_WAY);
                contact = true;
            } else {
                if (contact && distance > COLLISION_TRESHOLD) {
                    send_collision_signal(next_index++, SIG_CLEAR_WAY);
                    contact = false;
                }
            }
            Wait(25);
        }
    }
    
    // To not to waste energy we deinitialise the ultra sonic sensor.
    SetSensorLowspeed(US_SENSOR, false);
}


/*
Blocks until the color sensor has detected a surface with a valid color.

Note that you have to set BLACK_COLOR, RED_COLOR and WHITE_COLOR so that
their values represent the color values which the color sensor will detect
on your surfaces.
*/
int detect_way(void)
{
    SetSensorColorFull(COLOR_SENSOR);
    
    int color, way = -1;
    
    while (way == -1)
    {
        color = Sensor(COLOR_SENSOR);
        if (color > 1) {
            if (color <= BLACK_COLOR) {
                way = 0;
            } else {
                if (color <= RED_COLOR) {
                    way = 1;
                } else {
                    if (color <= WHITE_COLOR) {
                        way = 2;
                    }
                }
            }
        }
        Wait(50);
    }
    
    SetSensorColorNone(COLOR_SENSOR);
    return way;
}


int follow_way(long &known_ways[][][], int way)
{
    SetSensorLight(LIGHT_SENSOR);
    
    // To control the distinction between temporary blockades and
    // the destination we need to calculate a timeout.
    long time_blocked = 0;
    
    bool center_passed, center_reached = false;
    int collision_index, movement_index = 0;
    long last_signal_initiation;
    
    // The robot is standing still at first so
    // we have to make it to move forward now.
    send_movement_signal(movement_index++, SIG_FORWARD_BOTH, ROBOT_SPEED);
    last_signal_initiation = CurrentTick();
    
    while (true)
    {
        if (check_collision_signal(collision_index)) {
            switch (COLLISION_SIGNALS[collision_index++])
            {
                case SIG_BLOCKED_WAY:
                    send_movement_signal(movement_index++, SIG_STOP_BOTH);
                    time_blocked = CurrentTick();
                case SIG_CLEAR_WAY:
                    send_movement_signal(movement_index++, SIG_FORWARD_BOTH,
                                         ROBOT_SPEED);
                    last_signal_initiation += CurrentTick() - time_blocked;
                    time_blocked = 0;
            }
        } else {
            if (time_blocked > 0) {
                if (CurrentTick() - time_blocked >= DESTINATION_TIMEOUT) {
                    known_ways[way][movement_index][0] = SIG_FORWARD_BOTH;
                    known_ways[way][movement_index][1] = ROBOT_SPEED;
                    known_ways[way][movement_index][2] = 
                        time_blocked - last_signal_initiation;
                    break;
                }
            } else {
                if (Sensor(LIGHT_SENSOR) > LIGHT_TRESHOLD) {
                    if (!center_reached) {
                        if (center_passed) {
                            switch (way)
                            {
                                case 0:
                                    known_ways[way][movement_index][0] =
                                        SIG_RIGHT_TURN;
                                    known_ways[way][movement_index][2] =
                                        CurrentTick() - last_signal_initiation;
                                    send_movement_signal(movement_index++,
                                                         SIG_RIGHT_TURN);
                                    last_signal_initiation = CurrentTick();
                                case 2:
                                    known_ways[way][movement_index][0] =
                                        SIG_LEFT_TURN;
                                    known_ways[way][movement_index][2] =
                                        CurrentTick() - last_signal_initiation;
                                    send_movement_signal(movement_index++,
                                                         SIG_LEFT_TURN);
                                    last_signal_initiation = CurrentTick();
                            }
                        } else {
                            center_reached = true;
                        }
                    }
                } else {
                    if (center_reached) {
                        switch (way)
                        {
                            case 0:
                                known_ways[way][movement_index][0] =
                                    SIG_LEFT_TURN;
                                known_ways[way][movement_index][2] =
                                    CurrentTick() - last_signal_initiation;
                                send_movement_signal(movement_index++,
                                                     SIG_LEFT_TURN);
                                last_signal_initiation = CurrentTick();
                            case 2:
                                known_ways[way][movement_index][0] =
                                    SIG_RIGHT_TURN;
                                known_ways[way][movement_index][2] =
                                    CurrentTick() - last_signal_initiation;
                                send_movement_signal(movement_index++,
                                                     SIG_RIGHT_TURN);
                                last_signal_initiation = CurrentTick();
                        }
                        center_reached = false;
                        center_passed = true;
                    }
                }
            }
        }
        Wait(25);
    }
    
    SetSensorLight(LIGHT_SENSOR, false);
}


/*
This function interprets previously recorded movement signals
and makes the robot to perform those actions reversed.
*/
void way_back(long way_data[][], int next_move_index)
{
    int next_index = 63; // As we want to iterate over the signals reversed
                         // we start with the highest possible index.
    
    do {
        switch (way_data[next_index][0])
        {
            case SIG_STOP_RIGHT:
                send_movement_signal(next_move_index++, SIG_STOP_RIGHT);
                Wait(way_data[next_index][2]);
                break;
            case SIG_STOP_LEFT:
                send_movement_signal(next_move_index++, SIG_STOP_LEFT);
                Wait(way_data[next_index][2]);
                break;
            case SIG_STOP_BOTH:
                send_movement_signal(next_move_index++, SIG_STOP_BOTH);
                Wait(way_data[next_index][2]);
                break;
            case SIG_FORWARD_RIGHT:
                send_movement_signal(next_move_index++, SIG_REVERSE_RIGHT,
                                     way_data[next_index][1]);
                Wait(way_data[next_index][2]);
                break;
            case SIG_FORWARD_LEFT:
                send_movement_signal(next_move_index++, SIG_REVERSE_LEFT,
                                     way_data[next_index][1]);
                Wait(way_data[next_index][2]);
                break;
            case SIG_FORWARD_BOTH:
                send_movement_signal(next_move_index++, SIG_REVERSE_BOTH,
                                     way_data[next_index][1]);
                Wait(way_data[next_index][2]);
                break;
            case SIG_REVERSE_RIGHT:
                send_movement_signal(next_move_index++, SIG_FORWARD_RIGHT,
                                     way_data[next_index][1]);
                Wait(way_data[next_index][2]);
                break;
            case SIG_REVERSE_LEFT:
                send_movement_signal(next_move_index++, SIG_FORWARD_LEFT,
                                     way_data[next_index][1]);
                Wait(way_data[next_index][2]);
                break;
            case SIG_REVERSE_BOTH:
                send_movement_signal(next_move_index++, SIG_FORWARD_BOTH,
                                     way_data[next_index][1]);
                Wait(way_data[next_index][2]);
                break;
            case SIG_RIGHT_TURN:
                send_movement_signal(next_move_index++, SIG_RIGHT_TURN);
                Wait(way_data[next_index][2]);
                break;
            case SIG_LEFT_TURN:
                send_movement_signal(next_move_index++, SIG_LEFT_TURN);
                Wait(way_data[next_index][2]);
                break;
        }
        next_index--;
    } while (next_index >= 0);
    
    // Before the robot is following its way it is standing still and this
    // circumstance will not registered so we have to do it manually.
    send_movement_signal(next_move_index, SIG_STOP_BOTH);
}


/*
This represents the core of the main logic that
is responsible for how the robot will behave.
*/
task controller()
{
    int way_to_follow, move_index;
    long known_ways[3][64][3]; // [signal, speed, duration]
    ArrayInit(known_ways, NULL, 3*64*3);
    
    while (true)
    {
        way_to_follow = detect_way();
        start collision;
        start movement;
        move_index = follow_way(known_ways, way_to_follow);
        EVT_COLLISION = true; // Stops the collision task.
        way_back(known_ways[way_to_follow], move_index);
        EVT_MOVEMENT = true; // Stops the movement task.
    }
}


task main()
{
    Precedes(controller);
}

[tcwan]

Hello.

The following nxc code that I have written causes a file error -5 at line 588 when it is about to call "follow_way". My experience with NXC and C or C++ is very limited so I have no idea why this is happening. I noticed already that the array definition at line 580 and lastly its initialisation at line 581 causes the used memory to increase by around 3 KB. I thought the long datatype needs just 4 Byte so the array needs only 2304 bytes? Additionally I pass the array to "follow_way" by reference so why do I get this error? (Even if I disable the movement and collision task so that they do not initialise those two global arrays it is failing.)

I am not familiar with NXC personally, but my guess is that since the array is declared inside a routine, is is a local variable, making the compiler allocate the memory on the stack. Can you declare it as a global variable (ie., outside of all the routines, similar to the way you declared COLLISION_SIGNALS[])?

Global variables are put on the heap, and not the stack. Heap space is limited mostly by available free RAM, whereas Stack space may be limited by the max size of the stack for the NXT VM. In a general OS design, heap grows upwards in memory space, whereas Stack grows downwards from top of memory, so it is flexible in trading off using RAM for heap vs. stack space. However, that may not be the case for the NXT VM.

[spillerrec]

The NXT do not have a stack, so all variables are on the heap. However references aren't possible either, all memory locations are static. So if a function need to access some data, it has to be at a certain location. So if you have:

Code: Select all

long arr[100];
foo( arr );

then it needs to copy the whole array into the memory location the function expects. So if the array is 2 KB large, then you suddenly need 4 KB. Even worse, some array functions will require a temporary variable to hold the array, causing even more copies. (And these arrays aren't cleared when they are not needed any longer, so expect them to stay in memory.)

The only easy thing you can do to prevent some of the extra copies is to use globals instead of passing arrays into functions.

[HaWe]

hi,
IIRC, NXC (resp. the SFW or the EFW) hasn't got neither a heap nor a stack, but just sort of a chunk.
But it's correct that passing a variable (e.g., an array) to a function makes no local copy but an additional global copy of the source, and even passing a variable "by reference" does the same (and then overwrites the source by the new values).
So intermediately you'll need at least twice the original variable memory.