Restituire una lista di valori in C

[clros]

• 

Ciao,
mi chiedevo quale fosse il modo migliore per far restituire una lista di valori ad una funzione in C.
In C++ alla stessa funzione facevo restituire una std::list<>&, i cui nodi erano costruiti in modo tale da essere automaticamente distrutti all'uscita dello scope (con auto_ptr/unique_ptr).
Per fare la stessa cosa in C  come mi consigliate di procedere?
Farei cmq restituire alla funzione il puntatore al primo elemento della lista (oppure NULL nel caso di una lista senza elementi), e i singoli nodi della lista li costruirei all'interno della mia funzione con dei malloc/calloc. Il problema è questo...chi si dovrà occupare poi di liberare la memoria allocata dalla mia funzione per la lista? Vorrei evitare che sia l'utente della mia funzione a farlo. C'è soluzione?

[clros]

• 

Si può avere il prototipo della tua funzione?
Il numero di questi valori è fisso o variabile? Lo decide l'utente o la funzione?

Il prototipo è qulacosa del genere :

Codice: [Seleziona]

std::list<std::string>& myFunction(...) //non credo siano importanti i parametri passati...
e questo è come dovrebbe venire (devo "portarlo" in C)

Codice: [Seleziona]

myNode
{
 char *value;
 myNode* next;
};

myNode* myFunction(...);

Il numero di valori è variabile e lo decide la funzione (ecco perchè uso una lista)!

[clros]

• 

Se hai delle postcondition sul valore massimo degli elementi potresti usare lo stack (che sarebbe una soluzione abbastanza prestante)

Ehmmm...cioè?

[TheKaneB]

• 

Un metodo "pulito" consiste nel costruire una libreria generica per le liste e predisporre delle funzioni tipo:

List* list_create();
void list_dispose(List* list);
List* list_add(List * list, void *element);
ecc...

In tal caso l'utente crea una lista con:

List* result = list_create();

Poi la passi alla tua funzione con:

myFunction(result, .... );

e alla fine la deallochi con

list_dispose(result);

La tua funzione sarà così definita:
void myFunction(List * output, .... )
{
   if (output == NULL)
      errore();

   struct Elemento * datoCorrente;
   list_add(output, (void *)datoCorrente);
}

Ci sono alcuni svantaggi e un po' di overhead nell'usare questa soluzione, però ti consente di ragionare in OOP anche se usi il C.

[clros]

• 

@dsar:
Uhmm..si ads è più chiaro, facevo qualcosa di questo genere in assembly anni fa.
Però non credo sia praticabile in questo caso:il client non sa in anticipo quanti sono i valori ritornati e potrebbero essere moltissimi (65535 nel mio caso...)

[clros]

• 

@TheKaneB
Si, è quello che facevo nei tempi andati in C (il C++ mi sta viziando!), solo che la creazione della lista la facevo direttamente all'interno della mia funzione e poi fornivo un'altra funzione che serviva solo per liberare la memoria.
Certo, come hai scritto tu è più "logico", è l'utente deve anche crearsi la lista prima oltre a distruggerla...

[TheKaneB]

• 

Ci sono varie scuole di pensiero a riguardo.

Io sono della scuola che allocazione e deallocazione devono andare di pari passo.
Chi alloca qualcosa deve anche deallocarla.

Ciò serve per mitigare i possibili memory leaks dovuti all'uso improprio di una libreria. Infatti l'utente non può sapere, leggendo la signature di una funzione, se viene allocata della memoria al suo interno e quanta ne venga allocata.

Quindi se prevedi di allocare memoria, predisponi una coppia di funzioni create/dispose, il cui nome è già sufficiente per informare l'utente su come usarle.

Nel tuo caso specifico, devi anche decidere se e come cancellare il contenuto delle celle della lista, oltre alla lista stessa.
Quindi se fai delle funzioni come:

List* myLib_listCreate();
void myLib_function(List *output, .... );
void myLib_listDispose(List *list);

dovrai decidere se listDispose cancellerà automaticamente anche il contenuto dei nodi della lista, oppure se lasciarli allocati. Se la lista serve solamente come storage temporaneo, allora meglio deallocarli insieme alla lista stessa. Viceversa, i nodi della lista potrebbero prendere parte di altre strutture definite dall'utente.
Entrambi i casi devono essere chiaramente documentati.
Io preferisco deallocare tutto e subito, nel qual caso bisogna informare l'utente che il contenuto della lista muore con la lista stessa, pertanto dovrà copiarsi i dati da qualche altra parte se ne ha bisogno.
Anche questo aggiunge dell'overhead, ma è un tipo di programmazione che ti aiuta ad avere meno bug, specialmente memory leaks, che sono facilissimi da creare in C.

[clros]

• 

Tuttavia ti consiglio sempre di specificare un valore massimo di elementi della lista nella documentazione, tieni conto che se voglio contare gli elementi devo sapere che tipo di variabile index usare.

Giusta osservazione! A questo per esempio non avevo pensato!

[clros]

• 

Ci sono varie scuole di pensiero a riguardo.

Io sono della scuola che allocazione e deallocazione devono andare di pari passo.
Chi alloca qualcosa deve anche deallocarla.

Ecco, era quello che cercavo, un parere motivato...

[...]

dovrai decidere se listDispose cancellerà automaticamente anche il contenuto dei nodi della lista, oppure se lasciarli allocati. Se la lista serve solamente come storage temporaneo, allora meglio deallocarli insieme alla lista stessa. Viceversa, i nodi della lista potrebbero prendere parte di altre strutture definite dall'utente.
Entrambi i casi devono essere chiaramente documentati.

anche questo è un ottimo consiglio!

[clros]

• 

Io sono per i Garbage Collector

Che non siano come quello di Java!

E poi l'utente client se ne può sbattere della deallocazione (e clros sarebbe molto contento!)

Piu' che essere contento io  :lol: , volevo liberare il client dalla scocciatura di deallocare esplicitamente la memoria!


Ora che ci penso...le funzioni per l'allocazione e la deallocazione della memoria potrei implementarle direttamente nell'header, non c'è alcun bisogno che le "nasconda" direttamente nella libreria (.dll o .so), giusto?

[TheKaneB]

• 

Io sono per i Garbage Collector

Purtroppo la deallocazione manuale rompe l'encapsulation, ma lasciando stare l'encapsulation un memory model GC based è molto più sicuro nel gestire gli accessi alla memoria.

E poi l'utente client se ne può sbattere della deallocazione (e clros sarebbe molto contento!)

L'ideale per me sarebbe un sistema dotato di GC, ma che consenta anche di deallocare manualmente un oggetto.
Infatti ho avuto problemi di memory leaks su Android (Java) proprio perchè alcuni oggetti della GUI, effettuando delle operazioni non documentate, aumentano il reference count degli oggetti Bitmap impedendone la deallocazione.

In particolare avevo creato un sistema di caching delle immagini a 2 livelli: una cache in Ram tramite una Hash Table di weak reference a Bitmap, ed un secondo livello costituito da una cache disco (le immagini originali vengono scaricate da un server).

Nell'applicazione, la stessa Bitmap poteva comparire in più schermate diverse, quindi evitavo l'overhead della decompressione jpg (o png), mettendo in ram le bitmap già decompresse e poi associandole ai widget di quella particolare schermata.

Il caso tipico era rappresentato da una schermata contenente una lista di news, costituita da Titolo + Immagine, e molte schermate di dettaglio, costituite da Titolo + immagine + testo.

Il problema sorge nel momento in cui questa Bitmap entra a far parte della gerarchia di Widget di una View. Infatti quando aggiungi un elemento alla GUI, viene modificato il grafo della scena e ci sono vari elementi che si portano dietro i riferimenti ai vari oggetti. Il problema è che questa cosa non è documentata adeguatamente e capita spessissimo che molte Bitmap rimanessero allocate a causa di un qualche meccanismo di Android che manteneva delle reference valide in oggetti non più utilizzati.

Per risolvere il problema ho dovuto crearmi una funzione che esplora il grafo completo della View e cancella manualmente tutti i riferimenti alle Bitmap usate, e per farlo ho dovuto leggermi il sorgente di alcune parti di Android, perchè questo comportamento non è per nulla documentato.

Se avessi avuto la possibilità di deallocare le Bitmap a mano, avrei risolto il problema dei memory leaks con più facilità.

[clros]

• 

Java attualmente implementa uno dei migliori algoritmi non-realtime per il garbage collector (il Generational garbage collector).
Il runtime di Java si inchioda per altri motivi

Oggi i GC nei linguaggi compilati nemmeno li senti, per esempio in Go il GC viene runnato in una coroutine che è un thread a parte.

Non entro in merito alla bontà dell'algoritmo, però a volte ho sentito la necessità di un maggiore controllo sul garbage collector di Java (volevo poterlo invocare esattamente nel momento in cui dicevo io ed essere sicuro che in quello stesso momento sarebbe entrato in funzione a pulire). Ma forse la stessa cosa si poteva ottenere in altro modo. Bho, non saprei...
EDIT: Magari sono io che sono troppo legato al modo di pensare del C "Alloca e Dealloca" per cui continuo a pensare in questi termini anche su altri linguaggi. Pensa che all'uni, quando ho imparato Java e la programmazione ad oggetti, subito dopo la creazione di un oggetto ero naturalmente portato a confrontare il reference con null per vedere se la creazione era andata a buon fine!

[TheKaneB]

• 

Il problema è che questa cosa non è documentata adeguatamente e capita spessissimo che molte Bitmap rimanessero allocate a causa di un qualche meccanismo di Android che manteneva delle reference valide in oggetti non più utilizzati.

Se c'è un reference counting non è un "memory leaks"

Ho usato dei termini impropri, sorry.
Non possiamo parlare di memory leaks nel senso classico del termine, perchè esistono oggetti che possiedono ancora un'istanza di tali Bitmap.

Cerco di essere più specifico:

Bitmap, oggetto Java che fa riferimento ad una Bitmap allocata fuori dalla VM (Android la chiama Native Bitmap), possiede una reference ad ImageView che è un widget della GUI. A sua volta ImageView possiede una reference alla Bitmap (qui si forma una dipendenza ciclica) ad un oggetto Context che è la classe base di Activity, che a sua volta rappresenta l'entità grafica di una "schermata" di una app di Android.
A sua volta l'Activity contiene il cosiddetto ContentView, che è di tipo View (il tipo base di ImageView) e rappresenta un grafo orientato di Views (tra cui compare anche la suddetta ImageView). Quindi si forma un'altra dipendenza ciclica (View che si riferisce al Context, che poi è la stessa Activity, che a sua volta possiede un grafo di Views).

Il mio problema stava nel fatto che avevo una hashmap di oggetti Bitmap.

Quando creo una schermata, prendo il contenitore che dovrà mostrare l'immagine con un codice tipo:
BitmapDrawable image = memoryCache.getImage(url);
ImageView container = (ImageView) this.findViewById(R.id.newsImage); //this è di tipo Activity, R.id.newsImage è un intero generato da un tool dell'Android SDK, partendo da una descrizione XML della GUI
container.setDrawable(image);

Il codice è volutamente semplificato, giusto per mostrare la situazione.
Ora, accade che quando la schermata (Activity) viene distrutta, Android chiama il metodo onDestroy().

Qui sorgono 2 problemi:
- onDestroy non è chiamata in modo deterministico (Android potrebbe lasciare l'Activity in memoria e riutilizzarla in seguito, a sua discrezione, in tal caso richiama solo il metodo onPause() )
- la memoryCache non è specifica dell'Activity, ma è un singleton usato da tutte le Activities (proprio per far si che la stessa immagine non sia decodificata più volte da più activities)

Questo comporta che: le Bitmap contengano riferimenti ad Activity morte, impedendone il rilascio. Le Activity morte a loro volta contengono riferimenti a Bitmap non più presenti in cache, impedendone il rilascio. A causa delle dipendenze cicliche, una bitmap fuori cache ed una Activity morta possono impedire la distruzione reciproca. Questo finchè Android non decide di chiamare onDestroy e riciclare quell'Activity.

Il problema è che le Bitmap usano memoria al di fuori della VM, che non viene conteggiata dal GC e quindi si verificano frequenti Out Of Memory lato Native Heap, causati da una cattiva gestione della memoria lato VM.

Il mio fix consiste nell'attraversare tutto il grafo delle Views, all'interno del metodo onPause, e settare a null il Drawable di ogni ImageView.
In questo modo, anche se Android decide di tenere in memoria l'Activity senza distruggerla, ho lasciato campo libero al GC di liberare la memoria occupata dalle ImageViews / Bitmap / Native Bitmap, avendo spezzato la catena di riferimenti ciclici.
Quando l'activity riparte, tramite onStart, verifico se le Bitmap sono ancora in ram cache, e in caso contrario le ripesco dal disk cache.

Ciliegina sulla torta: Android usa la sua macchina virtuale Dalvik VM, che non è nemmeno lontanamente paragonabile alla Sun JVM, sia come efficienza sia come gestione della memoria.

Per risolvere il problema ho dovuto crearmi una funzione che esplora il grafo completo della View e cancella manualmente tutti i riferimenti alle Bitmap usate, e per farlo ho dovuto leggermi il sorgente di alcune parti di Android, perchè questo comportamento non è per nulla documentato.

Infatti prima per rompere l'encapsulation intendevo proprio questo (oltre al fatto che lo deve fare il compilatore) non è molto safe quello che hai fatto.

Uhm, come hai stabilito che nonostante ci fosse il reference counting quell'oggetto fosse inutilizzato?

Come già spiegato l'ho capito studiandomi i sorgenti delle View di Android che sono scarsamente documentati. Addirittura non esiste nemmeno una procedura ufficiale per far vedere i source di Android da Eclipse, per il debugging. Ti devi arrangiare come puoi seguendo qualche consiglio letto dai newsgroup e da alcuni spunti che ho trovato sul sito StackOverflow.com.
PS: se cerchi "Android Bitmap OutOfMemoryError" su google trovi tonnellate di problemi uguali a quello che ti ho descritto. E' segnato anche come bug sul bugtracking di Android da anni, e non hanno mai mosso un dito per risolvere questo problema.

[TheKaneB]

• 

nelle ultime versioni il GC è fatto meglio e il bug non si manifesta più.
il meccanismo delle native bitmap invece rimane invariato.

scommetto comunque che, se aumento la risoluzione delle bitmap, riesco ugualmente a replicare il bug anche su Android 4.0

Quello che mi da fastidio è che io devo sporcare il mio codidce, con questi fix brutali, per colpa della loro incapacità di progettare adeguatamente il framework di sviluppo. Con Java/Swing questo genere di problemi non mi si è mai presentato infatti.

[TheKaneB]

• 

Uhm dovrei studiarmi meglio le API Android, però tutto l'ambaradan non l'ho ben chiaro
Leggo che le API native si usano in casi eccezionali perché non gestite dalla VM, però questo solo tramite l'interfaccia JNI (Java Native Interface?), oppure il C.
L'oggetto bitmap dovrebbe essere gestito dalla VM e quindi dal GC.

Io credo che fosse un buggone pauroso della vecchia VM

Non ho usato API native, ma quelle standard, che a loro volta usano delle API native come dettaglio implementativo. Leggiti qualcosa sull'oggetto BitmapDrawable per capire cosa intendo.
Se non trovi molto in giro, di ufficiale intendo, è proprio per la scarsità di documentazione di cui mi lamentavo sopra :-)
Il bug è stato segnalato da anni, ma la risposta ufficiale di Google è che non si tratta di un bug, ma del modo corretto di funzionare, e se ottieni OuOfMemoryError a causa delle bitmap vuol dire che devi usare meno bitmap (dicono loro).
Poi il cliente vuole sapere da me come mai Android crasha mentre  su iPhone funziona con centinaia di immagini... e io mi devo inventare l'impossibile per far funzionare il tutto in modo efficiente.