Newsgroup: it.comp.lang.c
Titolo: Problemone per esperti! (Parte seconda) [x AnalogFile e altri]

Continuo la discussione "Problemone per esperti!" di un paio di settimane
fa... (Indirizzata in maniera particolare ad AnalogFile)
Ho letto tutto quello che mi avevi scritto e ho fatto alcune ricerche su
internet per cercare ulteriori informazioni.
Tenendo presente che il nucleo centrale del programma sara' diviso come
detto in tre parti ecco le mie problemantiche:
 
PRIMO THREAD/PROCESSO: lettura dei pacchetti TCP/IP dal link di rete,
filtraggio delle porte non interessanti e immagazzinamento dei
dati/pacchetti in un buffer FIFO.
Fino a qui tutto ok, sembra una cosa abbastanza semplice da implementare. Ho
solo alcuni dubbi su quello che mi hai consigliato e cioe' realizzare il
buffer su file (o piu' file) e non in memoria. L'idea di fare il buffer su
piu' file pero' puo' portare a dei vantaggi: ad esempio mentre realizzo il
primo file (ipotesi 50MB) posso osservare la distribuzione statistica della
dimensione dei pacchetti per realizzare gli allocatori della grandezza
opportuna. In piu' con un file unico avrei problemi di scrittura e lettura
che al momento mi sembrano un po' complessi (avrei due thread/processi che
accedono in contemporanea in scrittura(il primo) e in lettura e scrittura
(il secondo) sullo stesso file) e quindi, in definitiva, sarei indeciso su:
buffer in memoria o baffer su piu' file. Che ne pensi? Consigli per
realizzare il buffer su piu' file?
Quando il link della rete ha poco traffico il buffer su piu' file non
diventa problematico e sconveniente? Sicuramente il processi seguenti si
bloccano fino a che il file di buffer e' pieno... (Anche qui la dimensione
del file di buffer dovrebbe variare in base alla velocita' del link)
Quando il link e' velocissimo invece riesco a scrivere su disco (operazione
cmq lenta rispetto alla scrittura in memoria) senza perdere pacchetti?
SECONDO THREAD/PROCESSO: lettura del buffer FIFO (da memoria o file),
gestione della memoria tramite allocatori e inserimento dei dati di ogni
connessione in una struttura dati.
Per la lettura dal buffer FIFO da file non ci dovrebbero essere problemi.
Per quello che riguarda gli allocatori ho capito, grazie al codice che mi
hai spedito la volta scorsa, come funzionano: direi che sono molto
interessanti e utili per il mio programma! Ho solo un paio di domande sulla
scelta dei vari parametri:
-) Numero e dimensione degli allocatori: e' possibile, complicando un po' il
tutto, definirli durante la prima creazione del file di buffer da
un'analisi statistica della grandezza dei pacchetti in arrivo. Non penso
sia complicatissimo... Che ne pensi?
-) Numero minimo di blocchi e numero minimo di memoria da allocare volta per
volta (funzione "allocator_grow()"): a parte un transitorio iniziale in cui
ci saranno sicuramente moltissime malloc() credo che arrivati ad un certo
punto (con buffer su file) tutta la memoria sara' gestita internamente dal
programma tramite allocatori. Quali sono i pro e i contro ad usare dei
MIN_NEW_BLOCKS o MIN_NEW_MEMORY grandi o piccoli? Se si usano grandi ci
saranno poche malloc all'inizio ma si rischia di occupare piu' memoria del
necessario mentre se sono piccoli si rischia di avere un transitorio
iniziale molto lungo nel quale si avranno tante malloc() di piccole
dimensioni. Giusto? Consigli?
Ora la parte piu' complessa: l'ADT.
Primo problema: calcolo/uso della chiave. La chiave nel mio caso deve
identificare univocamente una connessione e quindi deve per forza essere
ip_src:port_src:ip_dst:port_dst. Come usare questa lunghissima chiave in un
Hash o in un Albero Bilanciato (come mi hai suggerito)? Purtroppo il numero
di connessioni (e quindi chiavi) possibili e' teoricamente enorme e il
numero massimo di connessioni istantanee e' al momento vicino alle 50000.
Se si usa un hash i problemi principali a mio avviso sono la scelta della
dimensione della tabella di hashing e la funzione di generazione delle
chiavi. Credo nn si possano eliminare le collisioni e quindi tutto il
sistema di gestione si complica molto. Idem per l'albero bilanciato: si
elimina il problema della lunghezza della tabella, rimane il problema della
chiave (e quindi delle collisioni) ma si complica la gestione (per tenere
bilanciato l'albero). Consigli? 
TERZO THREAD/PROCESSO: riconoscimento di file dai dati. Anche qui penso che
problemi non ce ne siano una volta che la struttura che contiene tutti i
dati funzioni correttamente. Dopo aver immagazzinato per una connesione una
certa quantita' di byte (ad esempio 10MB) o dopo un determinato timeout o
dopo un RST della connessione o dopo un FIN della connessione (o dopo
cos'altro?) vengono concatenati i dati fino ad ora arrivati e spediti alle
routine di ricerca.
Che ne pensi?
Grazie mille...
GiAn

GiAn wrote:
 > PRIMO THREAD/PROCESSO: lettura dei pacchetti TCP/IP dal link di rete,
 > filtraggio delle porte non interessanti e immagazzinamento dei
 > dati/pacchetti in un buffer FIFO.
 > Fino a qui tutto ok, sembra una cosa abbastanza semplice da 
implementare. Ho
 > solo alcuni dubbi su quello che mi hai consigliato e cioe' realizzare il
 > buffer su file (o piu' file) e non in memoria. L'idea di fare il 
buffer su
 > piu' file pero' puo' portare a dei vantaggi: ad esempio mentre 
realizzo il
 > primo file (ipotesi 50MB) posso osservare la distribuzione statistica 
della
 > dimensione dei pacchetti per realizzare gli allocatori della grandezza
 > opportuna.
Tieni tale analisi supersemplice.
Io non la renderei dinamica.
O meglio: il numero degli allocatori (e la dimensione del buffer per 
ciascuno di essi) lo metterei in un file di configurazione e lo lascerei 
editabile dall'utente. Durante la sessione non varierei questi parametri.
Dato che mi hai detto che il programma non gira 24/7 ma viene lanciato 
per un tot di tempo io prevederei in output (magari opzionalmente) delle 
statistiche (count delle dimensioni dei pacchetti che hai ricevuto nella 
sessione).
Al massimo poi puoi sviluppare una utility a parte che prende questi 
dati statistici e ti genere aun file di configurazione consigliato.
 > In piu' con un file unico avrei problemi di scrittura e lettura
 > che al momento mi sembrano un po' complessi (avrei due 
thread/processi che
 > accedono in contemporanea in scrittura(il primo) e in lettura e scrittura
 > (il secondo) sullo stesso file) e quindi, in definitiva, sarei 
indeciso su:
 > buffer in memoria o baffer su piu' file. Che ne pensi? Consigli per
 > realizzare il buffer su piu' file?
No. Un thread crea il file e ci scrive sopra. L'altro legge e alla fine 
cancella, ma non ci scrive.
La sincronizzazione la puoi fare in due modi:
1) (sconsigliato) con un counter condiviso (ricordati che deve essere 
protetto!)
2) il secondo thread legge e se trova EOF fa una pausa e riprova
Userei file multipli per semplificare il riutilizzo del disco.
Fissa una dimensione FILE_MAX_LEN. Il thread che legge apre il primo 
file e ci scrive. Quando arriva ESATTAMENTE a FILA_MAX_LEN lo chiude e 
ne apre un'altro. In lettura, una volta che tutti i dati di un file sono 
stati letti, cancelli il file.
Funziona anche fra processi separati. L'unica comunicazione 
interprocesso che ti serve è un segnale che il primo thread ha finito. 
Ma puoi anche scrivere un tappo direttamente nel file e farlo rilevare 
in lettura (hint: se ogni pacchetto è salvato raw preceduto da un int 
contenente la sua dimensione ... pacchetto di size zero).
 > Quando il link della rete ha poco traffico il buffer su piu' file non
 > diventa problematico e sconveniente? Sicuramente il processi seguenti si
 > bloccano fino a che il file di buffer e' pieno... (Anche qui la 
dimensione
 > del file di buffer dovrebbe variare in base alla velocita' del link)
 > Quando il link e' velocissimo invece riesco a scrivere su disco 
(operazione
 > cmq lenta rispetto alla scrittura in memoria) senza perdere pacchetti?
No. La dimensione dei file falla fissa o ti incasini.
Puoi scrivere e leggere contamporaneamnete (vedi sopra).
L'unico problema possibile è che il disco non sia abbaswtanza veloce per 
il traffico e/o non sia abbastanza grosso da tenere i dati se il thread 
di analisi è troppo lento (e resta troppo indietro). Non sapendo quanto 
è veloce il link ne per quanto tempo viene fatto girare il programma ad 
ogni iterazione è difficile valutare la cosa. Dammi info.
Nota: se il disco non ce la fa, ci saranno casi in cui perderai 
pacchetti comunque. Se non altro ... a memoria piena).
 > SECONDO THREAD/PROCESSO: lettura del buffer FIFO (da memoria o file),
 > gestione della memoria tramite allocatori e inserimento dei dati di ogni
 > connessione in una struttura dati.
No. Gli allocatori speciali ti servono nel primo processo che è quello 
time-critical.
Il secondo processo non è time critical e può anche "rimanere indietro". 
Puoi usare gli allocatori (dopotutto il codice ti viene gratis dato che 
lo hai sviluppato nell'altro processo) per ottimizzare la fase in cui 
lavori sui pacchetti. Ma quando concateni i pacchetti avrai bisogno di 
buffer più grossi, e non essendo time critical puopi restare su malloc 
senza problemi.
 > Per la lettura dal buffer FIFO da file non ci dovrebbero essere problemi.
 > Per quello che riguarda gli allocatori ho capito, grazie al codice che mi
 > hai spedito la volta scorsa, come funzionano: direi che sono molto
 > interessanti e utili per il mio programma! Ho solo un paio di domande 
sulla
 > scelta dei vari parametri:
 > -) Numero e dimensione degli allocatori: e' possibile, complicando un 
po' il
 > tutto, definirli durante la prima creazione del file di buffer da
 > un'analisi statistica della grandezza dei pacchetti in arrivo. Non penso
 > sia complicatissimo... Che ne pensi?
Vedi sopra. Non superottimizzare. Setup da file di configurazione. Da 3 
a 6 allocatori, così a occhio. Ma per dirlo con certezza servirebbero 
minimo delle statistiche.
 > -) Numero minimo di blocchi e numero minimo di memoria da allocare 
volta per
 > volta (funzione "allocator_grow()"): a parte un transitorio iniziale 
in cui
 > ci saranno sicuramente moltissime malloc() credo che arrivati ad un certo
 > punto (con buffer su file) tutta la memoria sara' gestita 
internamente dal
 > programma tramite allocatori. Quali sono i pro e i contro ad usare dei
 > MIN_NEW_BLOCKS o MIN_NEW_MEMORY grandi o piccoli? Se si usano grandi ci
 > saranno poche malloc all'inizio ma si rischia di occupare piu' 
memoria del
 > necessario mentre se sono piccoli si rischia di avere un transitorio
 > iniziale molto lungo nel quale si avranno tante malloc() di piccole
 > dimensioni. Giusto? Consigli?
Esatte le tue considerazioni. Nel thread time critical credo che se 
fissi un blocco di ridimensionamento di qualche decina di buffer come 
minimo e di qualche megabyte come minimo (verificando che entrambe i 
minimi siano soddisfatti) dovresti essere a posto. Puoi arricchire gli 
allocatori inmodo che tengano qualche statistica (numero di 
allocazioni/deallocazioni fatte dal programma cliente e numero di buffer 
allocati con malloc). Vedrai che te ne serviranno meno di quanto pensi. 
Il trucco è essere veloci ad allocare/deallocare, non a gestire grandi 
quantità.
Sul numero degli allocatori, non troppi ne troppo pochi. Come detto 
credo che da 3 a 6 sia un buon numero. Le dimensioni dipendono dal tipo 
di traffico che hai in rete. Comincia a scrivere il codice di base del 
primo processo. Piglia i pacchetti e salvali su file multipli come 
descritto. Appena hai qualche dato statistico postalo e ne parliamo.
 > Ora la parte piu' complessa: l'ADT.
 > Primo problema: calcolo/uso della chiave. La chiave nel mio caso deve
 > identificare univocamente una connessione e quindi deve per forza essere
 > ip_src:port_src:ip_dst:port_dst.
Non ho fatto un'analisi completa, ma forse ti potrebbe anche servire un 
timestamp.
 > Come usare questa lunghissima chiave in un
 > Hash o in un Albero Bilanciato (come mi hai suggerito)? Purtroppo il 
numero
 > di connessioni (e quindi chiavi) possibili e' teoricamente enorme e il
 > numero massimo di connessioni istantanee e' al momento vicino alle 50000.
 > Se si usa un hash i problemi principali a mio avviso sono la scelta della
 > dimensione della tabella di hashing e la funzione di generazione delle
 > chiavi. Credo nn si possano eliminare le collisioni e quindi tutto il
 > sistema di gestione si complica molto. Idem per l'albero bilanciato: si
 > elimina il problema della lunghezza della tabella, rimane il problema 
della
 > chiave (e quindi delle collisioni) ma si complica la gestione (per tenere
 > bilanciato l'albero). Consigli?
Non reinventare la ruota: se puoi usa un'implementazione esistente.
Questo problema riguarda il secondo processo, che non è time critical.
C'è un motivo per farlo in C? Se non c'è un motivo, passa ad un'altro 
linguaggio.
Python sarebbe molto produttivo. Ruby è un'ottima alternativa (ed è 
anche facile chiamare le routine in C per il riconoscimento).
Ma se vuoi essere veloce e rimanere in un linguaggio simile ... passa a 
C++. Puoi usarlo anche solo come un "better C".
Non solo ti semplifica anche il discorso degli allocatori, ma ha nella 
libreria std::map che fa esattamente al caso tuo.
Comuqnue se devi fare tutto in C io userei un albero, non una hash. 
Bilanciato con algoritmo Red/Black, per esempio.
Puoi anche valutare i Trie e i Patricia, ma a meno di giustificarli con 
una analisi dei dati delle connessioni, meglio che resti sul classico e 
conosciuto Red/Black binary tree.
 > TERZO THREAD/PROCESSO: riconoscimento di file dai dati. Anche qui 
penso che
 > problemi non ce ne siano una volta che la struttura che contiene tutti i
 > dati funzioni correttamente. Dopo aver immagazzinato per una 
connesione una
 > certa quantita' di byte (ad esempio 10MB) o dopo un determinato timeout o
 > dopo un RST della connessione o dopo un FIN della connessione (o dopo
 > cos'altro?) vengono concatenati i dati fino ad ora arrivati e spediti 
alle
 > routine di ricerca.
Inutile. Fai tutto nel secondo processo.

 Inutile. Fai tutto nel secondo processo.
Ok!
Grazie mille...
GiAn

 Ok! Grazie del consiglio.
La chiave non è importante in se. Quello che ti serve è una è una 
operatore di paragone (vedi il qsort della libreria C, per esempio). 
Quali campi della struttura vengono letti da questa funzione (ovvero la 
chiave) non importa.
Prova ad implementare un albero red/black generico che usa una funzione 
esterna (un puntatore a funzione) per il sorting. Non è banalissimo, ma 
neppure troppo difficile.

 neppure troppo difficile.
Ho dato un'occhiata a quello che mi hai detto ma nn mi e' chiaro l'uso della
mia chiave per cercare un termine di paragone fra due diverse conenssioni.
Cioe'...
Io implemento l'albero con la funzione esterna per il sorting (come avviene
per il qsort del C dove la funzione che esegue la comparazione fra due
elementi e' passata come parametro), e fin qui tutto ok: non facilissimo ma
neanche troppo difficile cosi' ad occhio... Quello che non capisco e':
-) La funzione di sorting nel mio caso e' esterna per "semplicita'" di
aggiornamento (se la devo cambiare non devo mettere mano alla parte del
codice che gestisce l'albero) o per altri motivi?
-) Non capisco come utilizzare la mia chiave che identifica univocamente la
connessione per il sorting dell'albero: come faccio a paragonare due
connessioni? Uso solo le informazioni relative alle porte? Uso solo gli
indirizzi ip? :-(
Grazie ancora...
GiAn

 indirizzi ip? :-(
Per tenere bilanciato l'albero e per poter sapere se una connessione 
esiste o meno in esso tutto quello che ti serve è una relazione d'ordine 
stretto (che, matematicamente parlando è ciò che la tua funzione di 
paragone con valore binario rappresenta).
Quale usare e su quali elementi dell'header costruirla lo lascio 
decidere a te (altrimenti ti faccio io il lavoro e ti spiego come l'ho 
fatto, ma allora poi ti presento fattura).

 fatto, ma allora poi ti presento fattura).
In effetti hai ragione... Mi hai gia' aiutato moltissimo...
Grazie mille!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
GiAn