Dati di buffer per blocchi separati da delimitatori

Question

C'è una domanda che mi chiedevo da anni e speravo che qualcuno potesse darmi una risposta per riposare la mia mente.

Supponiamo che io abbia un flusso di input (come un file / socket / pipe) e che voglia analizzare i dati in arrivo. Supponiamo che ogni blocco di dati in entrata sia diviso da una nuova riga, come i protocolli Internet più comuni. Questa applicazione potrebbe anche analizzare html, xml o qualsiasi altra struttura di dati intelligente. Il punto è che i dati sono divisi in blocchi logici da un delimitatore anziché da una lunghezza fissa. Come posso bufferizzare i dati in attesa che appaia il delimitatore?

La risposta sembra abbastanza semplice: basta avere un array byte / char abbastanza grande da adattarsi all'intera cosa.

Ma cosa succede se il delimitatore arriva dopo che il buffer è pieno? Questa è in realtà una domanda su come adattare un blocco dinamico di dati in un blocco di dimensioni fisse. Posso solo pensare ad alcune alternative:

1. Aumenta la dimensione del buffer quando necessario. Ciò può richiedere una riallocazione della memoria pesante e può portare all'esaurimento delle risorse da flussi appositamente predisposti (o forse persino alla negazione del servizio nel caso di socket in cui vogliamo proteggerci dagli attacchi di esaurimento e rilasciare connessioni che tentano di esaurire le risorse ... e un attaccante inizia a inviare pacchetti falsi, sovradimensionati per attivare la protezione.

2. Inizia a sovrascrivere i vecchi dati usando un buffer circolare. Forse non è un metodo ideale poiché il blocco logico diventerebbe incompleto.

3. Scarica nuovi dati quando il buffer è pieno. Tuttavia, in questo modo il delimitatore non verrà mai trovato, quindi questa scelta non è ovviamente una buona opzione.

4. Rendi il buffer di dimensioni fisse dannatamente grande e supponi che tutti i blocchi di dati logici in entrata siano entro i suoi limiti ... e se si riempie mai, basta interpretare l'intero buffer come un blocco logico ...

In entrambi i casi ritengo che dobbiamo supporre che i blocchi logici non supereranno mai una certa dimensione ...

Qualche idea su questo argomento? Ovviamente deve esserci un modo poiché le lingue di livello superiore offrono una sorta di meccanismi di buffering con i loro metodi di flusso readLine () .

Esiste un "modo migliore"? per risolvere questo o c'è sempre un compromesso? Apprezzo davvero tutti i pensieri e le idee su questo argomento poiché questa domanda mi ha perseguitato ogni volta che ho avuto bisogno di scrivere un parser di qualche tipo.

Answer 1

Esistono normalmente due tecniche per questo

1) Cosa penso che readline usi - se i riempimenti del buffer restituiscono i dati senza il delimitatore alla fine

2) Quando il buffer si riempie, ricordalo riempito, continua a leggere fino a quando non ottieni il delimitatore e segnala un errore (o tronca il record alla dimensione del buffer)

Answer 2

Le opzioni (2) e (3) non sono disponibili poiché in entrambi i casi si stanno perdendo dati. L'opzione (4) di un enorme buffer di dimensioni fisse non risolverebbe il problema in quanto non è possibile sapere quale dimensione è abbastanza grande? È tutta la memoria fisica + lo spazio di scambio + lo spazio libero disponibile in tutti i dischi ovunque nell'universo conosciuto?

Il ridimensionamento del buffer sembra la soluzione migliore. Pronuncia rialloc a dimensioni doppie e continua a scrivere. Esiste sempre la possibilità di un flusso appositamente costruito come un DoS che tenta di arrestare il sistema. Il mio primo pensiero è stato di impostare una dimensione arbitrariamente grande come max_size per il buffer. Tuttavia, se potessimo farlo, potremmo semplicemente impostarlo come dimensione del buffer di grandi dimensioni. Quindi, ridimensionare il buffer mi sembra l'opzione migliore.

Answer 3

1. Se il protocollo o non si definisce un limite superiore per la lunghezza di ciascun blocco, non vedo come sia possibile prevenire casi limite di esaurimento della memoria.

2. Supponendo che ci sia un limite superiore usando un blocco di dimensioni fisse sembra un buon approccio per limiti di dimensioni ragionevoli.

3. Se i limiti sono abbastanza alti da rendere inefficiente un singolo buffer fisso, suggerirei di utilizzare una struttura di dati implementata internamente come elenco collegato di buffer di dimensioni fisse.

Answer 4

Perché devi aspettare per iniziare l'elaborazione?

Generalmente l'alternativa 4 è il suono. Tuttavia, non richiede un "presupposto", piuttosto una definizione. Devi semplicemente dichiarare che i blocchi sono più piccoli di 8 KB e hai finito. Non è difficile da fare.

Inoltre, esiste un'alternativa 5: avviare l'elaborazione di buffer parziali. Funziona a meno che tu non abbia progettato un protocollo veramente patologico che invia dati critici alla fine del blocco.

HTML, XML, JSON / YAML, ecc., possono essere analizzati in modo incrementale. Non richiedi un delimitatore per eseguire un'elaborazione utile.