deallocazione memoria da testa di una lista collegata

Buongiorno a tutti,
nei miei programmi in cui uso liste collegate mi sono accorto che non mi dealloca la memoria quando elimino un elemento dalla testa della lista, se lo elimino dalla coda invece tutto funziona.

La routine incriminata è questa

void delMsgHead(Messages **head) //elimina il primo della lista
{
  Messages *temp;

  if (*head != NULL)
  {
    temp = *head;
    *head = (*head)->next;
    delete(temp);     //<-----------NON LIBERA LA MEMORIA
  }
}

di seguito posto anche il programma che verifica quanto ho detto, ho commentato direttamente il programma… per chi ha voglia di leggerlo o provarlo.

//definizione di classe per generare una lista collegata
class  Messages
{
  public:
    char stringa[200];
    int n;
    Messages *next;
};


Messages *msgHead;  //testa della lista
Messages *msgNode;  //nodo lista
uint8_t nmsg;       //contatore msg in memoria

/**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**/

void delMsgHead(Messages **head) //elimina il primo della lista
{
  Messages *temp;

  if (*head != NULL)
  {
    temp = *head;
    *head = (*head)->next;
    delete(temp);     //<-----------NON LIBERA LA MEMORIA
  }
}

/**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**/


void delLastMsg(Messages **head) //elimina l'ultimo elemento della lista
{
  //se lista vuota esce
  if (*head == NULL)
    return;

  //se lista ha un solo elemento
  if ((*head)->next == NULL)
  {
    delete(*head);
    *head = NULL;
    return;
  }

  //se lista ha due o più elementi
  Messages *temp;
  temp = *head;

  while (temp ->next->next != NULL)
    temp = temp ->next;

  delete(temp->next);
  temp->next = NULL;
}

Messages* infila(Messages ** head)  //restituisce un nuovo elemento della lista attaccato alla fine
{
  if (freeRam() > 500)
  {
    Messages *temp ;

    if (*head == NULL)  //se lista vuota
    {
      temp = new Messages;
      temp->next = NULL;
      *head = temp;
      return temp;
    }
    else
    {
      temp = *head;
      while (temp ->next != NULL) //cerca la fine
        temp = temp ->next;

      temp ->next = new Messages;
      temp = temp ->next;
      temp ->next = NULL;
      return temp;
    }
  }
  else
    return NULL;  //se memoria insufficiente restituisce null
}



int freeRam ()  //restituisce la ram disponibile
{
  extern int __heap_start, *__brkval;
  int v;
  return (int) &v - (__brkval == 0 ? (int) &__heap_start : (int) __brkval);
}


void setup()
{
  //init
  Serial.begin(9600);

  msgHead = NULL;
  msgNode = NULL;
  nmsg = 0;

  //ciclo di 10 volte per testare le routines
  for (int i = 0; i < 10; i++)
  {
    //genero un nuovo nodo
    msgNode = infila(&msgHead);
 

    if (msgNode == NULL)  //se non c'è più memoria ti avverto
      Serial.print("\nMEMORY OVERFLOW\n");

    else  //generato nuovo elemento in lista
    {
      nmsg++;

      //assegno un id all'elemeto
      msgNode->n = i;                

      Serial.print("\ngenerato messaggio n.: "); Serial.print(msgNode->n);
      Serial.print(" messaggi in memoria: "); Serial.print(nmsg);
      Serial.print("\nfree ram : "); Serial.println(freeRam());

      if (freeRam() < 500)  //se sta per finire la ram cancello un messaggio
      {
        Serial.print("\nMEMORY LEAK\n");
        Serial.print("\nfree ram prima di cancellare msg: "); Serial.println(freeRam());

        /**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**/

        //se levo un messaggio dalla testa non dealloca la memoria
        delMsgHead(&msgHead);

        //se levo un messaggio dalla coda invece funziona
        //delLastMsg(&msgHead);

        /**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**//**/

        //aggiorno contatore
        nmsg--;
        Serial.print("\ncancellato messaggio. Ora i msg in memoria sono: "); Serial.println(nmsg);
        Serial.print("\nfree ram dopo cancellato msg: "); Serial.println(freeRam());
/*
        Serial.print("\nguardo cosa c'è in memoria: ");

        msgNode = msgHead;
        while (msgNode != NULL)
        {
          Serial.print("\nmessaggio id: "); Serial.print(msgNode->n);
          msgNode = msgNode->next;
        }
*/
      }
    }
  }
}

void loop()
{

}

il layout del programma è questo

generato messaggio n.: 0 messaggi in memoria: 1
free ram : 1373

generato messaggio n.: 1 messaggi in memoria: 2
free ram : 1167

generato messaggio n.: 2 messaggi in memoria: 3
free ram : 961

generato messaggio n.: 3 messaggi in memoria: 4
free ram : 755

generato messaggio n.: 4 messaggi in memoria: 5
free ram : 549

generato messaggio n.: 5 messaggi in memoria: 6
free ram : 343

MEMORY LEAK

free ram prima di cancellare msg: 343

cancellato messaggio. Ora i msg in memoria sono: 5

free ram dopo cancellato msg: 343



MEMORY OVERFLOW

MEMORY OVERFLOW

MEMORY OVERFLOW

MEMORY OVERFLOW

si vede che anche cancellando i msg la memoria rimane a 343, poi nei successivi cicli non alloca più nulla.

Ringrazio tutti quanti dedicheranno il loro tempo… io non riesco proprio ad uscirne.

Hai mai notato che deprechiamo fortemente l’uso dell’allocazione dinamica della memoria su Arduino (e sulle piattaforme ridotte ai minimi termini in generale)? Il motivo è proprio questo, la frammentazione della memoria: un allocatore dovrebbe essere troppo furbo per tenere traccia di un blocco libero grosso X qua, uno grosso Y là, ecc ecc, per cui di fatto la memoria liberata non viene mai riutilizzata. Andrebbe deframmentata ogni tanto, ma è un’operazione troppo pesante per un microcontrollore (hai mai notato quei momenti in cui i programmi Java si freezano per qualche secondo? Ecco, ora sai perché…)

NB: Ho mentito: in realtà i tuoi conti sono sbagliati a causa del modo in cui funziona freeRam(), ma sono sicuro che l’allocatore di Arduino non è più di tanto furbo, per cui quanto detto sopra è comunque valido.

>Thec: ... mi accodo a quanto già detto da SukkoPera ... NON sei su un PC dove c'è un sistema operativo ed un "garbage collector", sei su una piccola MCU con solo 2KBytes di SRAM, dove devi fare tutto tu e dove usare l'allocazione e riallocazione dinamica della memoria, porta quasi sempre ... a grossi problemi e sicuri mal di testa !!! :smiling_imp:

Guglielmo

Grazie per le risposte prima di tutto.
Dunque, per riassumere, il problema non è nella funzione “delMsgHead” (ecco il mal di testa da dove veniva…) ma nel fatto che quando dealloco la memoria dalla testa della lista, rimane un buco nella porzione di memoria dedicata alla memoria dinamica (HEAP) che il buon MCU non considera più come libera. Togliendo invece un elemento dalla fine della lista questo buco non c’è e la cosa funziona… (sempre di non creare due liste distinte delle quali, dal punto di vista di occupazione dell’heap, una si mette si mette in coda all’altra… e qui scoppia tutto di nuovo).
Il freeRam() dà risultati non corretti perchè, mi pare di capire, indica la memoria libera fra lo heap e lo stack, non considerando i buchi lasciati. Ma se questi buchi non verranno più utilizzati, non è come se fosse memoria allocata o persa? quindi si può dire che il freeRam() dà un risultato “non corretto ma funzionale alla realtà delle cose”?

Questo è quanto ho capito. E accidenti potevo capirlo prima di sbatterci il muso! vabbè… ora il mio problema è un altro. Uso l’allocazione dinamica della memoria (che nei forum ho effettivamente trovato sconsigliato ma se usato senza un controllo della memoria… sto divagando,)… dunque… uso l’allocazione dinamica della memoria proprio perchè la memoria è poca, allocandola quando mi serve per poi liberarla quando serve ad altre routines che a loro volta si allocheranno e deallocheranno le loro porzioni di memoria. L’unica soluzione che vedo è proprio la deframmentazione, anche se occupa risorse credo di riuscire a far trovare ad arduino il tempo per occuparsi anche di quello… Ho cercato in rete ma non riesco a trovare nulla di già pronto e tantomeno di appena accennato… qualcuno ha qualche idea o neanche una discussione accademica risulta una buona idea?

Hai capito perfettamente.

Solo una cosa ti sfugge: quando hai 2K di RAM a disposizione, l'allocazione dinamica è fuori discussione, senza se e senza ma. Decidi un numero massimo di messaggi che supporti e alloca staticamente un array di quella dimensione.

Che poi, se ci pensi, l'allocazione dinamica ha senso su una macchina dove girano più processi, perché la richiesta di memoria di ogni processo può variare nel tempo. Ma in un ambiente come Arduino, dove c'è un processo unico, che senso ha allocare la memoria solo quando serve? Quando non serve, chi altro la usa?

ciao Sukko, non ti arrabbiare se insisto ancora un pò… ma… anche se mi pare che a questo punto lo heap sia più stoico che utile…

se stabilisco un punto di memoria (dove comincia l’haep per esempio) al quale fare riferimento, ogni volta che alloco una lista o quant’altro, la uso per quel che mi serve e poi la libero tutta prima di allocare altre cose, allora quei buchi non dovrebbero affatto formarsi, ma mi pare troppo banale la cosa… c’è qualcos’altro di sconosciuto che si potrebbe mettere in mezzo? in programmi complessi certo la cosa è rischiosa… cosa è che non so???

di seguito un esempio che aiuta a capire come potrebbe servire la stessa memoria per diverse “chiamate”, in cui per ipotesi ho 1 k libero. Il primo esempio usa due variabili che già di per sè stesse superano la memoria disponibile e non riuscirei a realizzare quello che voglio se non allocando e poi deallocando all’interno delle routine (è un esempio banale che trova facili soluzioni alternative, ma è per far capire cosa intendo…):

//codice che richiede troppa memoria rispetto alla disponibile

byte byteVar[700];
int intVar[400];

void uno()
{
  leggoDaShield1(&byteVar[0]);  //leggo dati da una perifierica e riempio l'array

  coputo(&byteVar[0]);  //computo i dati e ottengo risultati

  printa(byteVar); //stampo o archivio e poi li getto via che non servono più
}

void due()
{
  leggoDaShield2(&intVar[0]);  //leggo dati da una perifierica e riempio l'array

  coputo(&intVar[0]);  //computo i dati e ottengo risultati

  printa(intVar); //stampo o archivio e poi li getto via che non servono più
}

void loop
{
  if(condizione)
    uno();
  else
    due();
}

con l’allocazione dinamica lo scriverei così:

byte *byteVar;
int *intVar;

void uno()
{
  byteVar=new byte[700];

  leggoDaShield1(&byteVar[0]);  //leggo dati da una perifierica e riempio l'array

  coputo(&byteVar[0]);  //computo i dati e ottengo risultati

  printa(byteVar); //stampo o archivio e poi li getto via che non servono più

  delete(byteVar);
}

void due()
{
  intVar=new int[400];

  leggoDaShield2(&intVar[0]);  //leggo dati da una perifierica e riempio l'array

  coputo(&intVar[0]);  //computo i dati e ottengo risultati

  printa(intVar); //stampo o archivio e poi li getto via che non servono più

  delete (intVar);
}

void loop
{
  if(condizione)
    uno();
  else
    due();
}

Thec:
… con l’allocazione dinamica lo scriverei così …

…e perché scomodare l’allocazione dinamica “manuale” (con l’uso di new e delete) quando le “variabili locali” (e NON globali come il primo caso che è sempre meglio evitare) sono già di loro allocate dinamicamente dal compilatore ? ? ? :o :o :o

Guglielmo

Francamente non ti so rispondere, bisognerebbe studiare come lavora l'allocatore nel dettaglio, e non l'ho mai fatto. Non aspettarti niente di troppo elaborato però, come già accennato. È assolutamente possibile che lavori semplicemente continuando ad allocare aree successive, senza MAI tornare indietro. Finché c'è spazio bene, quando finisce... Buon divertimento! :smiley:

Secondo me non puoi ignorare il fatto che sei su una piattaforma ridotta all'osso, devi invece adattare il codice tenendo ben presente le risorse che hai a disposizione, a volte facendo cose anche non proprio "pulite" al fine di rispamiare o riciclare aree di memoria, ad esempio.

... in questo modo le variabili vengono allocate e deallocate dinamicamente dal compilatore all'entrata e uscita dalle funzioni (sono variabili LOCALI ed esistono sino a quando esiste la funzione) ... senza stare a fare cose strane gestendo manualmente la memoria ...

void uno()
{
  byte byteVar[700];

  leggoDaShield1(&byteVar[0]);  //leggo dati da una perifierica e riempio l'array

  coputo(&byteVar[0]);  //computo i dati e ottengo risultati

  printa(byteVar); //stampo o archivio e poi li getto via che non servono più
}

void due()
{
  int intVar[400];

  leggoDaShield2(&intVar[0]);  //leggo dati da una perifierica e riempio l'array

  coputo(&intVar[0]);  //computo i dati e ottengo risultati

  printa(intVar); //stampo o archivio e poi li getto via che non servono più
}

void loop
{
  if(condizione)
    uno();
  else
    due();
}

Guglielmo

gpb01:
…e perché scomodare l’allocazione dinamica “manuale” (con l’uso di new e delete) quando le “variabili locali” (e NON globali come il primo caso che è sempre meglio evitare) sono già di loro allocate dinamicamente dal compilatore ? ? ? :o :o :o

Guglielmo

…perchè altrimenti non mi funzionava l’esempio :confused: :confused:

praticamente allocando “manualmente” dovrei agire in modo tale da usare lo heap come il compilatore usa lo stack, cioè come una pila FIFO e come agirebbe l’esempio se usassi le variabili locali (se l’ho capita giusta). Nei prossimi giorni farò le mie prove e laddove non è proprio necessario non userò più l’allocazione dinamica (sigh!) anche se mi piace parecchio usarla.

grazie e buon appetito!!

Thec:
cioè come una pila FIFO

Correggo... LIFO
L'ultimo che entra esce per primo

Thec:
praticamente allocando "manualmente" dovrei agire in modo tale da usare lo heap come il compilatore usa lo stack ...

... dai retta, te lo ripeto, NON sei su un PC, NON hai un sistema operativo ... dove il compilatore fa già le cose (e le fa molto bene), lasciale fare a lui ... di sicuro vanno meglio :smiley:

Guglielmo