Newsgroup: it.comp.lang.c
Titolo: Problemone per esperti!

Sto realizzando un programma che dovrebbe gestire un flusso di dati in input
molto grande. L'input viene generato da piu' di 8000 "utenti" in
contemporanea. Non si sa a priori la lunghezze dei dati spediti dai
singoli "utenti" e, ovviamente, i dati arrivano mischiati (c'e' un
identificativo univoco che identifica l'utente).
In pratica dovrei leggere i dati, salvarli in memoria, aggiornarli
all'arrivo di nuovi dati, elaborarli e dopo alcuni secondi (timeout)
eliminarli se non servono piu'.
Un esempio dell'ordine dei dati potrebbe essere:
A spedisce 10Kb
B spedisce 1MB
A spedisce altri 45Kb
C spedisce 4MB
B spedisce altri 500Kb e non spedisce piu' nulla
A spedisce altri 2MB
D spedisce 1bit e non spedisce piu' nulla
...
Al momento (gli utenti erano meno di 10) c'e' una lista di puntatori a
struttura che contiene un campo intero "alloc", che indica la dimensione
della memoria allocata, e un puntatore che punta alla zona di memoria che
contiene/conterra' i dati.
Durante l'inizializzazione viene allocato nella struttura uno spazio di
memoria pari a 16KByte e quando ci si accorge che la memoria allocata non
e' sufficiente il campo alloc viene raddoppiato fino a quando la dimensione
dello spazio in memoria e' maggiore dei dati da allocare. A questo punto
tramite una realloc() viene reallocata la memoria (aumentandone la
dimensione come da campo alloc) e vengono aggiunti i nuovi dati.
Questo metodo fa molto uso di memoria e usa pochissime realloc(): visto che
alcuni utenti possono spedire anche solo un 1 bit allocarne 16KB come
default e' eccessivo e raddoppiare di volta in volta il campo alloc puo'
dimostrarsi disastroso (magari per memorizzare 11MB di dati vengono
allocati 20MB di memoria)! Da alcuni test ho trovato che circa l'80% della
memoria (110MB su 140MB!!!) e' sprecata (memoria allocata - memoria usata).
Partendo invece da un campo alloc iniziale di 1 bit e modificandolo in base
alla lunghezza effettiva dei dati in arrivo (se un utente invia altri 14bit
da aggiungere ai precedenti 500 rialloco lo spazio per 514 bit) lo spazio
di memoria sprecata scenda praticamente a zero ma l'uso delle realloc()
aumenta di un'ordine di grandezza (da circa 1000 ogni 2 minuti a 20000 ogni
2 minuti circa) minando le prestazioni del programma.
Ora, qualcuno ha qualche idea per usare il minor numero di realloc()
possibili e in modo da sprecare pochissima memoria? Non si cerca
l'ottimizzazione massima ma qualche idea buona per migliorare la situazione
attuale...
Grazie a tutti...
GiAn

 molto grande.
MEGACUT
Invece di alloc e realloc, non fai prima a fare solo delle alloc e 
creare una lista linkata per ogni utente (ogni elemento della lista 
contiene una "spedizione").
Non è chiaro come ricevi di fatto i dati (ovvero come fai a sapere 
quanto sono lunghi etc.) ne che elaborazioni ci fai sopra. Quindi è 
difficile dire quale sia la soluzione migliore.

 difficile dire quale sia la soluzione migliore.
In pratica gli utenti sono delle coppie indirizzo_ip:porta e i dati vengono
ottenuti tramite le librerie pcap. Le elaborazioni sono atte al
riconoscimento (per sicurezza di una grossa rete informatica) del tipo di
file trasmesso: immagini, zip, eseguibili,...
Grazie...
GiAn

 tutti gli elementi della lista.
Usa una libreria esterna, come Glib, che gestisca le stringhe automaticamente:
http://developer.gnome.org/doc/API/2.0/glib/glib-Strings.html
Ciao,
Danilo

 tutti gli elementi della lista.
Se questo tipo di accesso lo devi fare ad *ogni* ricezione di di un 
blocchetto di dati, è un conto. Ma se lo fai solo al termine di tutti i 
blocchetti che compongono una data trasmissione o anche solo se lo fai 
ogni tanto ma non a ogni blocco, allora il tempo che "perdi a unire gli 
elementi" è molto ma molto minore di quello che perdi a riallocare la 
memoria ogni volta.
Fidati. O meglio: NON fidarti ne di me NE DI TE. Prova ad implementare 
la cosa come ti suggerisco e poi MISURA se e quanto è più o meno veloce 
di come lo fai ora.
E se le prestazioni non sono sufficienti o usi un profiler per capire 
esattamente dove non lo sono, o descrivi meglio cosa succede nella tua 
applicazione per avere suggerimenti.

Danilo Piazzalunga wrote:

Belle ste funzioni! Sembrano proprio fatte su misura per quello che devo
fare!!! :-)
Unico dubbio... E dal punto di vista prestazionale? Visto che la quantita'
di dati da trattare e' rilevante non vorrei che questo metodo mi facesse
calare le prestazioni dell'intero programma. Anche perche' bisogna tener
presente che i dati arrivano impacchettati nei protocolli TCP/IP e quindi
ci possono essere delle ritrasmissioni, i dati non arrivano in ordine, ...
Grazie mille per la dritta!
GiAn

 applicazione per avere suggerimenti.
Qualche info sui profiler su Linux? Grazie mille!!!
Al momento la struttura che descrive i dati contiene i campi che
identificano univocamente la connessione (IP:porta sorgente-destinazione),
un puntatore a stringa e un pontatore a lista (piu' altre due o tre
variabile per gestire il tutto). In pratica il puntatore a stringa punta
alla zona di memoria che contiene i dati in arrivo: puo' capitare che i
dati non arrivino in ordine e che qualche pacchetto venga perso e quindi i
dati non sono contigui (ci sono dei "buchi"). Al momento la stringa č di
lunghezza fissa (vengono allocati 16KB), se questa dimensione non e'
sufficiente la stringa viene reallocata. I dati vengono inseriti nella
stringa in memoria in base all'offset e in base alla loro lunghezza
(parametri del protocollo TCP). Per tener conto dei buchi nei dati viene
utilizzata una lista dove ogni blocco contiene informazioni relative ai
dati contigui: l'offset (rispetto all'inizio della stringa di dati) e la
lunghezza dei dati contigui, un flag che indica se sono gia' stati
scansionati dalle routine di identificazione dei file e se e' gia' stato
trovato un file all'interno di questo blocco di dati.
L'idea sarebbe quella di modificare la struttura per migliorare le
prestazioni del programma e diminuire l'uso di memoria.
Qualche idea?
Grazie...
GiAn

 Qualche idea?
Fare il meno possibile e farlo il più tardi possibile per tutto ciò che 
riguarda dati in evoluzione, fare tutto il necessario appena possibile 
per i dati che non evolveranno.
Come tradurre ciò nel tuo caso ... dipende da cosa stai cercando di fare 
ESATTAMENTE.

 calare le prestazioni dell'intero programma.
Costruisci una funzione di test che usa buffer allocati e riallocati con
malloc() e realloc() e un'altra che usa GString per fare lo stesso compito,
poi chiamale un milione di volte e misura il tempo trascorso (vedi il thread
"cronometrare il codice" oppure includi <time.h> e usa clock(). Qualcosa del
genere dovrebbe andare bene:
clock_t start, end;
int i;
start = clock();
for (i = 0; i < 1000000; i++)
{
	funzione();
}
end = clock();
printf("Secondi trascorsi: %ld\n", (end - start) / CLOCKS_PER_SEC

 ESATTAMENTE.
Spero che adesso il problema sia piu' chiaro...
Sto cercando di modificare questa struttura in modo da non perdere troppi
pacchetti (rendere tutto molto veloce) e in modo da usare poca memoria (al
momento l'80% della memoria e' sprecata!!!)
Grazie mille...
GiAn

 al momento a 8MB) i dati vengono cancellati.
Mi mancano ancora molte info, ma per come la vedo io scriverei 
allocatori specifici per buffer di varie dimensioni (sintonizzati sugli 
MTU che vedi passare, prevedendo sempre la possibilità dell'MTU massimo 
dettato dal link hardware e aggiungendo altre dimensioni se vi è un'alta 
frequenza di size significativamente più basse).
Leggerei i pacchetti e li salverei tutti senza concatenarli ma facendo 
al volo un minimo di parsing dei parametri del protocollo. Usando gli 
allocatori suddetti e non il lentissimo malloc.
Userei le informazioni della window e/o del contatore del byte per 
capire a che punto è arrivata la trasmissione. Soprattutto considererei 
che i dati che TU hai ricevuto sono ricevuti (se li ricevi un'altra 
volta puoi buttare via la seconda copia) indipendentemente dall'ACK del 
destinatario. Inoltre l'ACK del destinatario (occhio alle estensioni 
moderne del TCP in cui questo non è del tutto vero) indica che i dati 
precedenti ad un certo punto o li hai ricevuti o NON li riceverai mai più.
A questo punto definisci un valore (diciamo 4 MB) e NON analizzi i dati 
ricevuti fino a che non hai ricevuto 4MB di dati.
Quando hai ricevuto 4 MB di dati, li concateni, chiami le routine di 
analisi e se non danno risultato butti via quei 4MB (eccetto un tot alla 
fine. Diciamo che se il le routine cercano headers che sono di al 
massimo 1Kb, non butti via l'ultimo Kb che tieni come "primo pacchetto" 
per la prossima analisi).
Quando la connnessione viene chiusa (incluso il caso di timeout) 
analizzerei i dati che restano prima di scartarla del tutto.
Se all'analisi risulta un positivo per un dato header, hai il problema 
di capire non solo quale routine chiamare per estrarre i dati relativi a 
quel file, ma anche quando chiamarla. Se non hai informazioni farei come 
sopra: ogni 4Mb concateno e chiamo la routine. Se mi dice che ha 
estratto 2Mb di dati, butto via i primi due mega e gli altri li 
considero il prossimo primo pacchetto da analizzare. Se mi dice che 
tutti e 4Mb sono dati del file e che ce ne possono essere ancora, li 
mantengo e passo ad una attesa doppia. Al prossimo giro gli mando 8Mb, 
poi 16 etc.
Nota che per non perdere nessun dato una buona idea è di non fare le 
analisi in tempo reale ma di salvare tutto il traffico su disco e 
analizzarlo nei momenti di calma. Se sei su ethernet e il traffico è 
diretto verso internet è quasi certo che ce la fai. Se stai su ethernet 
e il traffico è interno, ti serve lavorare in stripe per stare al passo, 
ma avrai più periodi di "notturna" che di "diurna". Se sei un internet 
provider di grosso livello allora il discorso potrebbe essere diverso ma 
è comunque fattibile.

 Qualche info sui profiler su Linux? Grazie mille!!!
man gprof

 è comunque fattibile.
Quello che mi e' stato chiesto invece e' proprio un'analisi in tempo
reale.:-(
Cmq quello e' il problema minore, volendo con tcpdump si creano dei file di
traffico e poi questi possono essere passati in un secondo tempo al
programma.
Grazie mille...
Se vuoi avere altre informazioni sul problema fammi sapere! :-)
GiAn

 programma.
Gia`.
Ciao,
Cesare

 Cesare
Grazie mille dei consigli!
GiAn

 La seconda che hai detto! E' un lavoro di tesi! :-)
Va be', sono un po' fuso... Cmq ci siamo capiti! :-P
GiAn

GiAn wrote:
 > Tornando al nostro programma non dico che quello che fa adesso e' 
corretto,
 > anzi, ci sono moltissime cose da migliorare: e' quello che sto 
cercando di
 > fare, ma non e' semplice!
No certo. Ma proprio per questo ti conviene semplificare tutto quello 
che puoi e prevedere anche future espansioni.
 > Quando l'ho preso in mano (oltre ad una miriade di BUG) c'era un solo 
thread
 > dove il pacchetto veniva sniffato, venivano acquisite tutte le 
informazioni
 > importanti (indirizzi IP, porte, vari flag del TCP,...), i dati
 > appartenenti ad una data connessione venivano inseriti in una struttura
 > dati (_connection), veniva aggiornata la lista che contiene informazioni
 > sui blocchi di dati contigui (datablock) della connessione modificata,
 > veniva eseguita una routine di ricerca dei contenuti al termine della 
quale
 > veniva sniffato il nuovo pacchetto.
E questo meccanismo rischia, se il link è veloce, di perdere dati anche 
se le connessioni sono poche. Se sei su una Gb ethernet e ci sono 10 o 
20 connessioni in corso tutte fra macchine interne (e quindi tutte 
potenzialmente a bassa latency e alto transfer rate) ti trovi con il 
canale saturo o quasi e con un alto rischio di perdere pacchetti.
 > Ora ho diviso il tutto in 2 thread (ma in futuro saranno 3): il primo 
che si
 > occupa di sniffare i pacchetti e di inserirli in un buffer FIFO e il
 > secondo che legge i dati dal buffer e fa tutto il resto. (Il terzo thread
 > dovrebbe in futuro occuparsi della ricerca dei file conosciuti nella
 > struttura dati).
Bravo. E se il buffer fifo è su file ancora meglio: nei momenti di 
saturazione il secondo thread può anche rimanere indietro senza che tu 
perda pacchetti e/o saturi la memoria. Inoltre puoi fare due processi 
invece che due thread. Infine puoi analizzare i dati sia in tempo reale 
che in tempo differito (o meglio: il tempo reale diventa un differito di 
pochi millisecondi se il secondo thread ce la fa, e il lag aumenta 
automaticamente se non ce la fa).
Infine il primo processo diventa abbastanza semplice da sviluppare e 
testare. E il secondo diventa molto più semplice da sviluppare e 
debuggare dato che puoi usare dati reali, l'esecuzione può essere 
ripetuta con gli stessi dati, non sei più vincolato in maniera streatta 
al realtime (quindi puoi privilegiare la leggibilità e il design 
rispetto all'ottimizzazione) etc. etc.
 > Le varie strutture _connection (che identificano le connessioni sniffate)
 > sono tenute assieme da una zona di memoria di dimensione fissa
 > (numero_puntatori_max*sizeof(connection)) che contiene i puntatori alle
 > strutture (anche questo si vorrebbe modificare). Quando non ci sono piu'
 > puntatori liberi viene riallocato tutto raddoppiando la dimensione dello
 > spazio di memoria. :-O
Premessa: io comincerei con il passare a C++. Ti semplificherebbe molte 
cose (anche se le parti "ereditate", come le routine di analisi restano 
in C).
Per prima cosa non ha senso usare una zona di memoria fissa. Ha il 
vantaggio di non usare la malloc che è lenta, ma se si riempie e la 
raddoppi come detto hai dei momenti in cui ti rallenta parecchio. Dato 
che probabilmente l'accesso principale che ci fai è la ricerca di una 
connessione (chiave gli ip e le porte) e il secondo tipo di accesso in 
ordine di importanza è l'inserimento/cancellazione di un elemento, io 
userei una hash o un albero bilanciato come implementazione dell'ADT 
conosciuto come 'map' o come 'dictionary'. Se fai come suggerisco 
(processo distinto, dati da file, sviluppo in C++) usa std::map e hai 
già tutto pronto!
Se hai problemi di prestazioni con malloc/free puoi ottimizzare creando 
un allocatore specializzato tarato sulla dimensione del nodo della 
struttura. Ma se ti organizzi in modo che il thread che gestisce i 
calcoli sia svincolato e possa "rimanere indietro", il problema non c'è.
 > La routine di ricerca in pratica, tramite un ciclo for sulla zona di 
memoria
 > che contiene i puntatori alle strutture _connection, scandisce tutte le
 > strutture e passa i blocchi di dati contigui che non sono stati ancora
 > scanditi a delle routine di ricerca specifiche per ogni file che si 
intende
 > trovare (gif, jpeg, png, mp3, zip, ... Tramite delle opzioni che si 
passano
 > al programma all'avvio e' possibile scegliere quali file cercare). Queste
 > routine specifiche per prima cosa cercano in questi blocchi qualcosa che
 > assomiglia ad un header del file cercato. Se lo trovano allora 
controllano
 > se la struttura del file viene rispettata fino all'eof. Se tutto combacia
 > all'ora restituiscono l'offset del primo bit dell'header e la 
lunghezza del
 > file. Il file verra' estratto e salvato subito dopo. Il tutto 
ripetuto per
 > ogni file da cercare!
Cominciamo a separare le fasi.
Leggere i dati e metterli da qualche parte è compito del primo thread. 
Per ora accantoniamo questa parte del problema.
Il secondo thread a sua volta "legge i dati" (nel senso di estrarli 
dalla FIFO) e poi li elabora. Si tratta di connessioni e i pacchetti 
possono arrivare in ordine sparso, possono non arrivare, possono 
sovrapporsi e/o arrivere più volte etc.
Dobbiamo poter gestire una connessione che dura ore e trasferisce molti 
mega o giga di dati. Ma dobbiamo anche gestire 50000 connessioni 
contemporaneamente. E alcune saranno corte altre saranno lunghe. Sono 
due aspetti distinti ma le implicazioni sono che non ha senso attendere 
la fine di una connessione per analizzarla (scartiamo i dati al più 
presto possibile). Però non ha molto senso neppure analizzare gli stessi 
dati più volte: più lunga è la sequenza di dati che analizziamo ogni 
volta, meno dati dobbiamo analizzare.
Supponendo che le routine di analisi cerchino header aventi lunghezza 
massima MAXHLEN diciamo che fatta l'analisi di un blocco consecutivo di 
byte possiamo scartarli tutti tranne gli ultimi MAXHLEN-1 che dobbiamo 
ricordare e considerare come prima parte per l'analisi successiva. 
Tranne nel caso in cui l'analisi ci dia un positivo. In questo caso 
dobbiamo per forza ricordare tutti i dati a partire dal punto in cui 
inizia il file che vogliamo estrarre e fino alla fine dello stesso.
A questo punto molto dipende da come sono fatte le routine di estrazione 
del file. Se possono gestire il file "a pezzetti" bene. Altrimenti 
dovremo poter concatenare tutti i dati necessari ad arrivare fino alla 
fine del file per poi estrarlo (e possono essere tanti!).
Appena individuata la fine del file, si passa quello che resta della 
trasmissione alle routine di analisi per cercare di individuare altri file.
 > In pratica l'addetto alla sicurezza della rete dovrebbe far funzionare
 > questo programma ogni tanto per un determinato tempo e controllare se e
 > dove vengono scambiati file non leciti.
Ancor più inutile cercare di forzare una analisi in realtime. Basta un 
realtime "finto".
 > Al momento controlla solamente i dati "in chiaro" dove con questa parola
 > intendo file non criptati, non ricodificati, non compressi, ... In 
pratica
 > al momento i vari protocolli da te indicati non vengono presi in
 > considerazione. Tutto quello che e' un dato di una connessione TCP viene
 > concatenato con il seguente e la stringa ottenuta viene controllata senza
 > alcuna altra elaborazione. In futuro pero' si vorrebbe migliorarlo
 > ulteriormente e identificare anche dati trasmessi ad esempio tramite i
 > protocolli P2P (che sono quasi sempre compressi): eDonkeye e Kad.
Peggio: spesso sono UDP!
E non dimenticare che per come lo fai adesso mi sa che non pigli neppure 
i file trasferiti via mail o via HTTP (o almeno non tutti quelli 
trasferiti via HTTP).
 >> Mi mancano ancora molte info, ma per come la vedo io scriverei
 >> allocatori specifici per buffer di varie dimensioni (sintonizzati sugli
 >> MTU che vedi passare, prevedendo sempre la possibilità dell'MTU massimo
 >> dettato dal link hardware e aggiungendo altre dimensioni se vi è un'alta
 >> frequenza di size significativamente più basse).
 >
 > Avevo gia' in mente di chiamare in ballo l'MTU... La tua idea mi sembra
 > ottima!!!!
 >
 >> Leggerei i pacchetti e li salverei tutti senza concatenarli ma facendo
 >> al volo un minimo di parsing dei parametri del protocollo. Usando gli
 >> allocatori suddetti e non il lentissimo malloc.
 >
 > Qui mi sono perso:
 > 1) Parsing dei parametri del protocollo: intendi il protocollo TCP ed IP
 > vero?
Certo.
 > 2) Come faccio a creare gli allocatori senza malloc? Mi potresti per 
favore
 > spiegare meglio?
Ci arriviamo.
 > 3) Se ho capito bene questi allocatori in pratica formerebbero una lista
 > dove ogni allocatore contiene i dati contenuti in un pacchetto, giusto?
 > Alla fine pero', prima di passare il tutto alla routine di ricerca, devo
 > riunire tutti i dati in un'unica stringa, giusto?
Quasi.
 > 4) Come faccio a gestire l'ordine dei pacchetti? Non arrivano in 
ordine e ci
 > possono essere ritrasmissioni... Quindi, per usare questi allocatori,
 > dovrei implementare qcosa che gestisca il TCP per ogni connessione
 > (ACK,...). Giusto?
Ni.
Provo a spiegare.
Il problema va distinto in due fasi (che poi sono i due thread).
Parliamo del primo thread: riceve i pacchetti e li inserisce in una 
FIFO. Se lo fai come ti suggerisco la FIFO è un file e non dovresti 
avere grossi problemi. Ma supponiamo che tu resti in un sistema a due 
thread e lavori sempre e solo in memoria.
Una cosa che ti troverai a fare è allocare un blocco di memoria per ogni 
pacchetto che il primo thread inserisce nella FIFO. Poi lo deallocherai 
quando il pacchetto è stato analizzato e scartato (o concatenato). Al 
momento fai di peggio: RIALLOCHI la memoria per tutti i dati ricevuti in 
quella connessione per metterci dentro i dati del nuovo pacchetto (ok: 
magari quando riallochi ti tieni un margine e non riallochi proprio ad 
ogni pacchetto, ma in questo modo sprechi memoria). Inoltre così facendo 
tu non sai che dimensione hanno i blocchi di memoria che allochi e 
quindi devi usare malloc/realloc/free. Quelle funzioni sono ottimizzate 
per allocazioni generiche. Ma nel caso dei pacchetti tu hai delle info 
che malloc non può avere. Sia in termini di dimensioni che in termini di 
sequenza probabile di allocazione/deallocazione.
L'allocatore specifico, in C++, è banale da scrivere (grazie ai 
template). In C leggermente meno banale, ma sempre possibile. E' 
probabile che te ne serva più di uno, in base alle dimensioni del blocco 
di memoria. Nota che nel caso dei pacchetti della rete hai un limite 
massimo (l' MTU della connessione, che per ethernet classica è di 1500). 
Dato che devi poter gestire il caso di pacchetto di dimensione massima 
ti serve almeno questo allocatore.
Supponi di definire una struttura di questo tipo:
struct packet_data {
   // dimensione del pacchetto grezzo con tutti gli header
   unsigned packet_len;
   // dati relativi al payload TCP
   // lunghezza del payload, posizione nel pacchetto,
   // offset del primo byte dall'inizio della
   // trasmissione ed eventuali altri.
   unsigned data_len;
   unsigned idata; // oppure char* pdata
   unsigned long offset;
   ...
   // altri dati
   ....
   // il pacchetto
   char raw_data[MAX_PACKET_LEN];
};
Quando ricevi il pacchetto puoi anche solo limitarti ad inserirlo in 
raw_data e settare packet_len. Gli altri campi li aggiornerà il secondo 
thread quando analizza il pacchetto stesso. Nella struttura puoi anche 
aggiungere i dati che ti servono per gestire la FIFO e/o qualunque altro 
dato.
Ora hai due problemi:
1) se statisticamente l'MTU delle connessioni è molto più basso di 
quello massimo, stai sprecando molta memoria (immaginati che i pacchetti 
siano quasi tutti intorno ai 600 byte e che MAX_PACKET_LEN sia di 1500 o 
più).
2) farai molte malloc/free di struct packet_data che hanno sempre la 
stessa dimensione, e soprattutto le farai in una situazione critica in 
termini di prestazioni.
Quindi puoi pensare di risolvere creando un allocatore speciale per 
packet_data. O meglio: più allocatori speciali per packet_data 
instanziati con MAX_PACKET_LEN diversi. Inoltre puoi accomunare parte 
dei dati in testa alla struttura per rendere gli algoritmi più generici. 
Supponiamo che la FIFO la implementi come lista doppiamente linkata. Che 
decidi di creare allocatori ottimizzati per valori di MAX_PACKET_LEN di 
1500, 1280, 576 che sono valori comuni (ma è meglio se ti basi su 
statistiche del tuo traffico). Che vuoi "generalizzare" al massimo i 
tuoi algoritmi e che lavori in C (in C++ puoi ottenere alcuni vantaggi, 
ma questo non è il NG giusto).
Potresti fare qualche cosa del genere (nota: scrivo nell'editor. Codice 
non testato):
// **** implementazione di una LIFO con lista linkata
typedef struct sl_list_node_header_t {
   struct sl_list_node_header_t *next;
   // char data[];
} sl_list_node_header;
// riutilizziamo l'header del nodo anche
// come struttura della lista. Il membro
// next sarà usato come un first.
typedef sl_list_node_header lifo_node_header;
typedef sl_list_node_header lifo;
// usata (opzionalmente) per inizializzare un nodo
// appena allocato
lifo_node_header* lifo_node_init( lifo_node_header* n )
{
   assert( n != NULL );
   n->next = NULL;
   return n;
}
// inizializza una LIFO vuota
lifo* lifo_init( lifo *l )
{
   return (lifo*) lifo_node_init( (lifo_node_header*) l );
}
// test
bool lifo_empty( lifo *l )
{
   assert( l != NULL );
   return l->next == NULL;
}
// inserisce un elemento nella LIFO
void lifo_push( lifo *l, lifo_node_header* n )
{
   assert( l != NULL );
   if ( n != NULL ) {
     n->next = l->next;
     l->next = n;
   }
}
// accesso e delink (senza deallocazione) all'elemento
// in testa alla LIFO
lifo_node_header* lifo_peek( lifo *l )
{
   assert( l != NULL );
   return l->next;
}
lifo_node_header* lifo_pop( lifo *l )
{
   // nota: la chiamata alla lifo_peek valida l
   lifo_node_header* head = lifo_peek( l );
   if ( head != NULL ) {
     l->next = head->next;
     lifo_node_init(head);
   }
   return head;
}
// funzioni con deallocazione del nodo
bool lifo_pop_off( lifo *l, void (*pfree)(void*) )
{
   if ( ! lifo_empty(l) ) {
     assert( pfree != NULL );
     pfree( lifo_pop(l) );
   }
   return ! lifo_empty(l);
}
lifo* lifo_clear( lifo *l, void (*pfree)(void*) )
{
   while ( lifo_pop_off( l, pfree ) )
     ;
   return l;
}
// **** implementazione di una FIFO con lista doppiamente linkata
// nota: importante che la parte iniziale della struttura
// resti "allineata" a quella usata per la lista singolarmente
// linkata.
typedef struct dl_list_node_header_t {
   struct dl_list_node_header_t *next;
   struct dl_list_node_header_t *prev;
   // char data[];
} dl_list_node_header;
// omissis. Implementazione simile a quella per la LIFO.
// *** implementazione di un allocatore specializzato per
//
// ciascuna istanza di un allocatore è specializzata per
// queste condizioni:
// -) i blocchi tramite essa allocati hanni tutti la stessa
//    dimensione (non inferiore a sizeof( lifo_node_header ) )
// -) i blocchi devono poter essere logicamente allocati
//    e deallocati velocemente
// -) non esiste un pattern regolare di alloc/free (ovvero
//    non è detto che quando si dealloca un blocco questo
//    sia l'ultimo allocato. Se così fosse il pattern sarebbe
//    LIFO ed è possibile scrivere un allocatore ancora +
//    veloce)
// -) la memoria usata dai blocchi logicamente deallocati non
//    può essere riutilizzata se non per un successivo blocco
//    della stessa dimensione allocato dallo stesso allocatore
//    (ovvero la deallocazione è logica ma non reale e la
//    memoria non viene rilasciata se non al termine del
//    programma)
// -) un blocco appena allocato non è inizializzato a zero e
//    contiene dati casuali
typedef struct allocator_t {
   unsigned block_size;
   lifo free_blocks;
} allocator;
// arrotonda per eccesso un valore in modo che sia
// assicurato l'allineamento per l'host in uso
unsigned allocator_alignement( unsigned v )
{
   // per ora presuppongo 8 byte
   return (v+7) & ~7;
}
// inizializza un allocatore
allocator* allocator_init( allocator* a, unsigned size )
{
   assert( a != NULL );
   a->block_size = size >= sizeof(lifo) ? size : sizeof(lifo);
   a->block_size = allocator_alignement( a->block_size );
   lifo_init( & a->lifo );
   return a;
}
// prepara nuovi blocchi (nota: routine interna, puoi anche
// dichiararla statica)
allocator* allocator_grow( allocator* a )
{
   // facciamo che allochiamo almeno 2MB e almeno 8 blocchi
   // le define le metto qui ma ovviamente vanno a inizio file
   #define MIN_NEW_BLOCKS 8
   #define MIN_NEW_MEMORY 2000000
   unsigned new_blocks_count = 0;
   char* new_mem = NULL;
   // inutile assert: è una routine interna
   // assert( a != NULL );
   if ( MIN_NEW_BLOCKS*a->block_size >= MIN_NEW_MEMORY )
     new_blocks_count = MIN_NEW_BLOCKS
   else
     new_blocks_count = 1+(MIN_NEW_MEMORY/a->block_size);
   new_mem = malloc( new_blocks_count * a->block_size );
   assert( new_mem != NULL );
   for ( ;
         new_blocks_count != 0;
         --new_blocks_count,  new_mem += a->block_size )
      lifo_push( &a->lifo, (lifo_node_header*)new_mem );
   return a;
}
// alloca un blocco
void* allocator_alloc_block( allocator* a )
{
   lifo_node_header *head = NULL;
   assert( a != NULL );
   head = lifo_pop( &a->lifo )
   if ( head == NULL )
     head = lifo_pop( & allocator_grow( a )->lifo );
   return (void*) head;
}
// dealloca un blocco (deve essere stato allocato da
// questo allocatore, ma non facciamo verifiche per
// motivi di efficienza)
void allocator_free_block( allocator* a, void*p )
{
   assert( a != NULL );
   if ( p != NULL )
     lifo_push( &a->lifo, (lifo_node_header*)p );
}
// implementiamo un minimo di intelligenza per gestire
// allocatori multipli specializzati per una struttura
// atta per gestire i pacchetti.
// per esempio gestiamo 1500, 1280, 576 come dimensioni
// dei pacchetti co la struttura packet_data
typedef struct {
   // questo ci serve per gestire la FIFO dei pacchetti
   fifo_node_header fifo_data;
   // i dati del pacchetto
   unsigned packet_len;
   ....
   char raw_data[];
} packet_data;
#define NUM_ALLOC_SIZES 3
const unsigned alloc_sizes[NUM_ALLOC_SIZES] = {
   1500+sizeof(packet_data),
   1280+sizeof(packet_data),
   576+sizeof(packet_data)
};
allocator allocators[NUM_ALLOC_SIZES];
// nota: il valore tornato è base 1, non base 0
// 0 significa che il valore è troppo grosso
unsigned index_for_packet_size( unsigned s )
{
   unsigned i;
   for ( i=NUM_ALLOC_SIZES;
         i>0 && alloc_sizes[i-1] < s + sizeof(packet_data);
         --i )
     ;
   return i;
}
// inizializza
void init_allocators()
{
   int i;
   for ( i=0; i<NUM_ALLOC_SIZES; ++i )
     allocator_init( allocators+i, alloc_sizes[i] );
}
// alloca un blocco per un pacchetto di data dimensione
// l'unico campo inizializzato nel blocco ritornato
// è packet_len. E' importante che questo valore NON
// cambi e sia ancora lo stesso al momento della
// deallocazione
packet_data* allocators_alloc( unsigned pk_len )
{
   unsigned i = index_for_packet_size( pk_len );
   packet_data *p = NULL;
   if ( i != 0 )
     p = allocator_alloc_block( allocators + i - 1 );
   else
     p = malloc( pk_len + sizeof(packet_data) );
   assert( p != NULL );
   p->packet_len = pk_len;
   return p;
}
// dealloca il blocco contenente un pacchetto
// nota: il prototipo è valido anche per
// deallocare direttamente con una chiamata
// alle funzioni di deallocazione di una lista
void allocators_free( void* p )
{
   unsigned i = 0;
   if ( p != NULL ) {
     i = index_for_packet_size( ((packet_data*)p)-> packet_len );
     if ( i != 0 )
       allocator_free_block( allocators + i - 1, p );
     else
       free( p );
}
Il codice implementa una lista linkata (e quindi una LIFO) minimali, 
prepara lo stage per l'implementazione dei una lista doppiamente linkata 
(e quindi una FIFO) e implementa un generico allocatore ottimizzato. 
Infine implementa minimalmente una logica per utilizzare in maniera 
abbastanza trasparente un insieme di tre allocatori (sintonizzati su 
dimensioni diverse).
I tempi di allocazione e dellocazione sono rapidissimi (ma perdi in 
generalità) ma per quello che stai facendo tu vedrai che risparmi 
parecchi cicli (e perdi meno pacchetti).
 >> Userei le informazioni della window e/o del contatore del byte per
 >> capire a che punto è arrivata la trasmissione.
 >
 > Questa me la devo studiare bene, al momento non viene utilizzata la 
window
 > del protocollo.
 >
 >> Soprattutto considererei
 >> che i dati che TU hai ricevuto sono ricevuti (se li ricevi un'altra
 >> volta puoi buttare via la seconda copia) indipendentemente dall'ACK del
 >> destinatario. Inoltre l'ACK del destinatario (occhio alle estensioni
 >> moderne del TCP in cui questo non è del tutto vero) indica che i dati
 >> precedenti ad un certo punto o li hai ricevuti o NON li riceverai 
mai più.
 >
 > Qui le cose si complicano ulteriormente... Non vengono tenuti in
 > considerazione gli ACK delle varie connessioni me tutto quello che viene
 > ritrasmesso viene risalvato sopra i dati gia' presenti e ricevuti in
 > precedenza. Questo politica penso sia stata scelta per evitare di
 > complicare il programma che a questo punto dovrebbe controllare in 
maniera
 > approfondita tutte le connessioni.
La questione la vedo in questi termini: se ricevi due volte gli stessi 
dati puoi benissimo copiare quelli nuovi sopra a quelli vecchi (tanto 
sono uguali), la perdita di tempo è minima. Oppure puoi scartare quelli 
nuovi.
Ma ricorda che dopo aver ricevuto tot byte tu vuoi concatenare e fare 
una scansione, dopodiché potresti scartare una parte dei dati.
Ora la questione è: cosa succede se ricevi nuovamente i dati che hai 
scartato? Ovviamente ha solo senso scartarli, non "riportare indietro" 
il "puntatore" che internamente usi per tracciare a che punto della 
connessione sei arrivato TU.
L'altra punto da analizzare è quello di "buchi" e dei multipli. Se 
capita che perdi pacchetti potresti non ricevere parte dei dati. 
Naturalmente non avendo tu un capo della connessione non puoi certo 
chiedere una ritrasmissione. Inoltre se NON concateni i blocchi fino a 
che non hai ricevuto almeno tot byte, come fai a sapere quanti ne hai 
ricevuti tenendo conto del fatto che alcuni li hai ricevuti più volte?
La window del TCP probabilmente non ti serve. Ma seguire i vari ACK/NAK 
invece può essere utile (e veloce). Di fatto puoi scoprire a che punto è 
arrivato il ricevente. E quindi scopri quanti byte non riceverai 
certamente più (o ci sono o non ci sono). Questo ti risolve entrambe i 
problemi in un colpo. Se ti basi su questo puoi decidere di procedere ad 
una concatenazione quando vedi che il ricevente è arrivato a X e tu 
avevi analizzato fino a Y. Se X-Y è almeno tot byte ha senso che 
concateni e scandisci. E se i byte non ci sono ... non ci sono e basta. 
Puoi persino scartare i MAXHLEN byte che precedono immediatamente il 
buco nonché tutto il buco (che tanto non hai) e risincronizzare la 
prossima scansione subito dopo il buco stesso.
 >
 >> A questo punto definisci un valore (diciamo 4 MB) e NON analizzi i dati
 >> ricevuti fino a che non hai ricevuto 4MB di dati.
 >> Quando hai ricevuto 4 MB di dati, li concateni, chiami le routine di
 >> analisi e se non danno risultato butti via quei 4MB (eccetto un tot alla
 >> fine.
 >
 > Qui non sono d'accordo. Se le connessioni simultanee raggiungono punte
 > vicino alle 50000, facendo l'ipotesi che anche solo l'1% (500) raggiunga
 > quei fatidici 4MB si avrebbe un'occupazione di memoria teorica pari a
 > 2GB!!! (In pratica si intaserebbe meta' della memoria disponibile!!!)
Se lavori totalmente in memoria, da qualche parte devi fermarti!
Se hai 50000 connessioni che stanno tutte trasferendo immagini pedoporno 
da 50MB l'una che fai?
Nota che si tratta di bilanciare: se cerchi di seguire tutte le 
connessioni continuando a concatenare i blocchi rischi di perdere dei 
dati. Se invece ritardi la concatenazione allora sei pià efficiente e 
non perdi dati, ma ti servono più risorse se lavori del tutto in memoria.
Se invece lavori con la FIFO su disco (magari spezzata in più file, ma 
questo è un'altro discorso) la cosa si semplifica.
Puoi sempre decidere che se l'utilizzo di risorse aumenta troppo, 
analizzi tot secondi per volta (diciamo 5) facendo passaggi multipli e 
considerando solo tot connessioni per volta (diciamo 300) per passaggio.
La FIFO su disco (se la connessione non è spaventosamente veloce) 
dovrebbe permetterti di non perdere mai nessun pacchetto (o almeno non 
per colpa di mancanza di risorse da parte tua) e nello stesso tempo di 
analizzare al massimo tutti i dati in maniera efficiente.
In cambio significa che il processo di analisi non è propriamente in 
realtime. Se il traffico aumenta ... i risultati arriveranno in ritardo. 
Se poi il traffico diminuisce i risultati torneranno (dopo un pochino di 
tempo) ad essere praticamente in realtime.
 >> Nota che per non perdere nessun dato una buona idea è di non fare le
 >> analisi in tempo reale ma di salvare tutto il traffico su disco e
 >> analizzarlo nei momenti di calma. Se sei su ethernet e il traffico è
 >> diretto verso internet è quasi certo che ce la fai. Se stai su ethernet
 >> e il traffico è interno, ti serve lavorare in stripe per stare al passo,
 >> ma avrai più periodi di "notturna" che di "diurna". Se sei un internet
 >> provider di grosso livello allora il discorso potrebbe essere diverso ma
 >> è comunque fattibile.
 >
 > Quello che mi e' stato chiesto invece e' proprio un'analisi in tempo
 > reale.:-(
Che scelgano: se vogliono il vero tempo reale gli serve una macchina 
super (magari un cluster di macchine). Oppure possono decidere che è in 
realtime ma analizza solo una parte delle connessioni (se superano un 
tot di connessioni le ignori). Oppure le gestisce tutte, ma perde i dati 
in maniera random con il rischio di non gestirne di fatto neanche una.
In altrnativa l'analisi è in realtime fittizio. Se girano pochi dati è 
praticamente in realtime, altrimenti i risultati arrivano in ritardo. Di 
quanto dipende: qualche secondo o qualche minuto a seconda di quanto è 
il traffico e quanto è potente la macchina.
Puoi anche usare un serverino molto ma molto più piccolo di quello che 
hai. L'unico vero tuning importante è fra la velocità del link e la 
velocità dei dischi. Ed eventualmente la loro capacità se il link è 
saturo 24/7 (il che è molto ma molto improbabile).
 > Cmq quello e' il problema minore, volendo con tcpdump si creano dei 
file di
 > traffico e poi questi possono essere passati in un secondo tempo al
 > programma.
Infatti. Una possibilità è proprio questa.
Anche se il grosso di tcpdump e/o ethereal è nell'analisi degli stream, 
cosa che comunque fai in modo proprietario.
Il semplice "capture" dei dati e salvataggio su disco non è poi così 
difficile da implementare.

[SUPER_MEGA_CUT]
Mi sono stampato tutto quello che mi hai mandato e credo mi ci vorra' un po'
di orette per masticare ed acquisire tutte le idee, il codice e i consigli
che mi hai scritto.
Magari fra un paio di giorni ti faccio sapere cosa ho deciso di fare. Ok?
Spero di leggere ancora tue e-mail... :-)
Per il momento ti ringrazio enormemente...
Ciao ciao...
GiAn


Beh se e` un lavoro di tesi potrebbe essere che il tuo prof sia gia` 
contento se gli implementi il buffer pool e il terzo thread (quello a 
bassa priorita` che ricerca i file per interderci).
Posso darti anche questi consigli:
1) Se hai tempo puoi andare a leggerti un po` di codice di squid, 
dovrebbe essere GPL. Ovviamente senza copiarlo. Potrebbe darti una idea 
di come i programmatori di squid hanno gestito le connessioni.
2) Ricorda che in una applicazione multithread e` facilissimo introdurre 
bachi perche` si aprono tutta una serie di problematiche.
La piu` comuni sono: la gestione dell'accesso a risorse condivise 
(variabili globali, file, ecc.) da parte di piu` thread, se i tuoi 
thread sono preentive devi scrivere funzioni rientranti perche` un 
thread potrebbe essere interrotto in ogni momento.
Tutte queste problematiche sono ben note, puoi trovare una buona guida qui:
http://concentric.net/~tics/tutorials.html
3) Potresti dare un'occhiata anche a qualcosa di moderno riguardo alla 
programmazione di rete.
Per esempio ci sono lavori che implementano il cosiddetto "modello 
asincrono".
Per esempio esiste ACE (C++).
http://www.cs.wustl.edu/~schmidt/ACE.html
Oppure Twisted (Python):
http://twistedmatrix.com/trac/
Attenzione pero` perche` introdurre uno di questi framework potrebbe 
essere oneroso e farti perdere troppo tempo.
Pero` io una occhiata alla parte dei "facade wrapper" di ACE gliela 
darei (leggi la ACE overview).
Voi tesisti moderni avete la fortuna di avere internet. Usatela!
:-)
Ciao,
Cesare

 valutare l'adozione di squid o ethereal.
Più che altro non è acqua fresca se deve garantire di non perdere dati o 
che i dati li perde con una policy ben precisa.
In pratica credo che il giosto compromesso per lui sia acquisire su file 
e analizzare in due tempi diversi (con due processi/thread distinti) e 
usare il disco come supporto intermedio.
Che poi è quello che fa anche ethereal.
Può usare ethereal per l'acquisizione? Si e no. Non so come, di fatto, 
ethereal salvi i dati su disco (credo salvi i dati raw con un suo 
headerino per ogni pacchetto). Ma questa parte non dovrebbe essere 
troppo difficile da fare o da rifare.
Un problema che potrebbe avere è quello della prestazione del disco. 
Bisogna verificare la velocità del link e se ha o meno a disposizione 
uno o più dischi dedicati. La lettura da parte del secondo thread può o 
meno interferire. Un kernel tuning potrebbe aiutare (in genere si 
privilegiano le letture sulle scritture perché danno un maggior senso di 
"reattività" agli utenti, ma in questo caso ha senso fare il contrario).
Definire una dimensione di file e cambiare file una volta che la si è 
raggiunta può semplificare la gestione dei "dati scartati".
Insomma ci so


 :-)
Ottimo consiglio.
E in un certo senso è quello che sta facendo :-)