Newsgroup: it.comp.lang.c
Titolo: Interrupt e accesso condiviso ad una lista

Supponiamo di avere una lista circolare dinamica dove ogni elemento
punta al precedente e al successivo.
La funzione list_add(), come è ovvio,  aggiunge un elemento nella
lista
in una data posizione, quindi andando a modificare i puntatori del
nuovo
elemento e degli elementi precedente e successivo.
Il problema è che una funzione di interrupt (in particolare un
interrupt di
un timer) può andare a cancellare un elemento di questa lista, andando
quindi a modificare i puntatori degli elementi precedente e successivo
rispetto a quello da eliminare.
Penso che la funzione list_add() potrebbe non funzionare correttamente
se l'interrupt dovesse capitare proprio mentre la list_add() va a
modificare
i puntatori, lavorando proprio sull'elemento che l'interrupt va a
cancellare.
Una cosa del genere come si risolve? Immagino che disabilitando gli
interrupt (o almeno l'interrupt del timer che va a modificare la
lista) è una
soluzione, ma non mi sembra una soluzione elegante... C'è qualche
altra soluzione?


un flag?
nella struttura insieme ai puntatori ti tieni un flag che segna lo
stato attuale dell'elemento.
Cosa fare per ogni funzione in un determinato stato dell'elemento
dipende dall'applicazione..
Ciao!

 dipende dall'applicazione..
Non penso possa funzionare. L'unica soluzione mi sembra essere
proprio disabilitare gli interrupt.
Infatti nell'ISR devo rimuovere un elemento della lista e l'ISR può
scattare in qualsiasi momento. Nella routine list_add() devo per
forza andare a disabilitare gli interrupt.
Se utilizzassi un flag per bloccare la struttura (tipo uno spinlock)
nell'ISR non riuscirei a cancellare l'elemento e non saprei più cosa
fare. La cancellazione è una cosa che _deve_ avvenire nell'ISR.


Boh, vedi te.
Da come la vedo io, disabilitare l'interrupt o bloccare l'elemento
equivale comunque a non cancellare nulla. :)
Certo, se il tuo hardware ha un sistema di accodamento degli interrupt
(in maniera che appena riattivi gli int. quelli pendenti vengono
spediti) è un'altro discorso.
E poi cmq te l'ho detto, dipende dall'applicazione. L'ISR potrebbe per
esempio marcare l'elemento come cancellato, senza cancellarlo
effettivamente. In questo modo non stacchi nulla e la procedura di
inserimento è banale. Se sai dove inserire una procedura di cleanup
della lista anche questa è una soluzione possibile.
Ciao!

 spediti) è un'altro discorso.
Ti faccio un esempio molto semplice. Sto cercando, anche se con mille
difficoltà, ad implementare una gestione dei timer "alla linux",
naturalmente
**molto** in piccolo. In pratica esiste una variabile (jiffies) che
viene incrementata
ad ogni interrupt del timer (che scatta, diciamo, ogni millisecondo)
ed una
lista contenente i timer attivi con i valori dei jiffies in
corrispondenza dei
quali il timer si esaurisce (per esempio, se jiffies=300 e voglio
attivare un
timer dopo 1 secondo, inserirò nella lista dei timer attivi un timer
con un
jiffies pari a 1300).
Nell'ISR, oltre ad incrementare la variabile jiffies, vado a scorrere
la lista
(che suppongo ordinata, nel senso che in testa ho il timer che scade
prima)
e vado a processare i timer esauriti, eliminandoli dalla lista.
Ho quindi due procedure che accedono in scrittura alla lista. L'ISR
che
elimina i timer eventualmente "spirati" e processati e la funione
timer_add()
che aggiunge un timer alla lista quando richiesto dall'applicazione.
Se riesco ad interpretare bene il kernel di linux, mi sembra che viene
utilizzato
uno spinlock associato alla lista dei timer attivi. La funzione
timer_add(),
in realtà la sua chiamante, va prima a bloccare questo spinlock che,
tra le
altre cose, dovrebbe disabilitare globalmente gli interrupt. Alla
fine
dell'inserimento nella lista del nuovo timer, lo spinlock viene
sbloccato,
quindi gli interrupt vengono riattivati.
Tutto ciò dovrebbe trovarsi in linux/timer.c.
Prima di iniziare ad entrare nei meandri del kernel di linux, pensavo
che un
meccanismo che andasse in continuazione a disabilitare/abilitare gli
interrupt
per evitare conflitti di accesso ad una stessa struttura fosse un
meccanismo
sbagliato o almeno inefficiente. Ora che leggo che questa tecnica è
ampiamente utilizzata in un sistema operativo così diffuso,efficiente
e stabile,
sto cambiando idea...

 sto cambiando idea...
Non e' una buona idea invece. Se per caso avessi un
(o peggio, molti) processo che ciclicamente blocca gli
Irq, anche un sistema non strettamente real-time andrebbe
rapidamente ad escort...
La protezione di eclusivita' ottenuta con la disabilitazione
degli irq va bene per sistemi piccoli e micro-sistemi, tipo
il uCOS etc.. In un sistema con molti processi, tale
tecnica puo' causare un deadlock totale e quindi
dovrebbe essere applicata con moolta cautela e limitata
a casi che non possono essere risolti altrimenti.
Nel caso di Linux, e' vero che la tecnica viene applicata
ma credo sia un rimasuglio nel kernel degli anni '90.
E comunqe, nel caso dello spin_lock in questione, viene
disabilitato la preemption dello scheduler, non gli interrupt
in toto (potrei sbagliare, ma credo sia cosi')
Nel caso dei timer poi non e' una buona idea in generale
disattivare l' interrupt che CONTA i tick e aggiorna
i conteggi.... molto meglio impiegare tecniche diverse
B.
B.

 i conteggi.... molto meglio impiegare tecniche diverse
A parte che non riesco a trovare tecniche diverse (se hai qualche
suggerimento...) quando disabilito gli interrupt per accedere in
scrittura ad una struttura condivisa con gli IRQ, in realtà non sto
fermando il conteggio dei tick. Se l'interrupt del timer scatta ogni
10ms è necessario che la disabilitazione degli interrupt avvenga per
non più di 10ms per evitare di saltare dei conteggi.

 non pi� di 10ms per evitare di saltare dei conteggi.
Introduci pero' una situazione potenzialmente pericolosa.
se il tuo programma va in crash prima di riabilitare
gli IRQ, tutto il sistema muore, non solo il tuo processo..
Ovviamenete se stai lavorando cin ambiente multiprocesso :-)
Bye
B.

 > non più di 10ms per evitare di saltare dei conteggi.



Sul Linux x86 l'int viene gestito dai LAPIC. Su un x86 multicore non
hai problema a staccare sia gli int di un core, sia un int locale, sia
l'intero sistema di gestione globale, che tanto c'è una coda nello
APIC globale.
E' tutto un altro mondo.

<snip>
Ma quanti timer dovrai mai gestire? Metti un array e via. :-|

 minore).
Potresti usare un flag di lock, che puoi settare in modo
atomico:
  // Applicativo
  if(get_lock(my_sem))
  {
     // Inserisci/deleta/ elementi nella lista
     // ........
     get_unlock(my_sem)
  }
  else
      return(BUSY);
L' interrupt, che sicuramente gira con priorita',
controlla solo se esiste il lock: se si conteggia
il numero di tick 'persi' che poi sottrae al prossimo
giro quando aggiorna i contatori dei timer per mantenere
la corretta temporizzazione... se tutto ok si suppone che
possa perdere al massimo solo un giro...
// Interrupt
if(!test_lock(my_sem))
{
    // Gestisci timers usando tick_lost corrente...
    tick_lost=0;
}
else
{
     // Accesso dell' applicatiovo
     // Non posso accedere alla lista adesso...
     tick_lost++;
     // Eventual gestione di timeout su tick_lost
}
No so se risolve il problema....
Bye
B.

 Ma quanti timer dovrai mai gestire? Metti un array e via. :-|
Tu hai ragione, certe volte mi fisso solo per questioni
filosofiche... :)
Però il discorso mi sembra interessante comunque.


Su un OS per x86 multiprocessore (il target primario di linux) il
problema non esiste.
Su un single core senza accodamento hardware delle interruzioni devi
mettere un flag, non si scappa.
La faccio troppo semplice io?
Ciao!

 puo' terminare le proprie operazioni avendo in uso la cpu.
Praticamente mi stai dicendo che l'interrupt viene interrotto, in modo
complicato sì, ma interrotto durante la modifica alla lista.

In effetti penso che risolva il problema, anche se il codice inizia
ad
essere complicato da leggere e manutenere.
Mi sembra che la morale della favola sia che non esiste una soluzione
semplice per creare un driver del timer dinamico e scalabile.
Si passa da una soluzione molto semplice, poco scalabile e poco
performante
di array statico da scorrere ad ogni IRQ (alla ricerca di un timer
esaurito)
ad una soluzione più complicata che coinvolge dei lock.
Alla fine mi tengo stretto il metodo statico...

 Alla fine mi tengo stretto il metodo statico...
Yes :-)
b.

 esaurito)
<snip>
Assolutamente no. L'array è la soluzione più semplice, più scalabile
(in termini di architetture) e più performante.
E' la lista ad essere la soluzione più astrusa, perché usi un
"concetto da user-space" in kernel mode. Io andrei per l'array, tanto
quanti timer ti servono? 100? a 8byte a timer non arrivi nemmeno ad
1K. Direi che se hai bisogno di tutti questi timer 1K di memoria te lo
puoi permettere - o no?
Ciao!

 puoi permettere - o no?
Non è un problema di memoria, piuttosto di performance e di "eleganza"
nell'utilizzo dei timer a livello di user-space.

 modo complicato sì, ma interrotto durante la modifica alla lista.
Purtroppo non conosco il kernel di Linux in dettagli sufficienti ma 
posso suggerirti l'implementazione applicata nel kernel di un sistema 
operativo che ho sviluppato per applicazioni telefoniche.
L'interrupt del timer (5 o 10 0 20 o 50 millisecondi a seconda 
dell'applicazione) aveva come sola funzione di fare il preempting del 
processo running, incrementare il conteggio dei "ticks" e far 
ripartire lo scheduler.
Lo scheduler era strutturato per priorità sulla prima delle quali vi 
era il processo per la gestione della lista dei timer (lista ordinata 
per il tempo di scadenza).  I processo estraeva i timer in scadenza 
nel "tick" corrente e metteva in coda (con la dovuta priorità) i 
processi che li avevano attivati (in attesa) dopo di ciò lo scheduler 
passava a gestire le code dei processi, dal più al meno prioritario.
Quando un processo running richiedeva un timer lo faceva attraverso 
una system call gestita dal kernel stesso che per i pochi micro 
secondi (non proprio pochi sull'80188 a 12 MHz :-) necessari alla 
gestione della lista disabilitava gli interrupt.
Se pensi di realizzare una simile funzionalità in area user ricorda 
che (almeno per i processori x86 su cui ho lavorato) solo il kernel 
può gestire gli interrupt.  Se invece stai lavorando per un SO spero 
che il mio suggerimento possa esserti di chiarimento.
Ciao
Giovanni
-- 
   A computer is like an air conditioner,
   it stops working when you open Windows.
   < 
http://giovanni.homelinux.net/
 >

Non vorrei prendere una grossa cantonata, ma questo per me funziona,
non cicla tutto l'array e non stacca gli interrupt.
La coerenza è data dallo stesso valore del count.
La funzione di add funziona indipendentemente da quando viene
interrotta.
struct timer_s {
    int count;
    pid_t process;
};
struct timer_s timers[NTIMERS];
int last_timer, t_retry;
void init_timers()
{
    memset(timers, 0, sizeof(timers));
    last_timer = 0;
}
void timer_ISR()
{
    int i;
    /* ... */
    t_retry = 0;
    if (timers[last_timer].count!=0)
        ++last_timer;
    for(i=0; i<last_timer; ++i) {
        if (timers[i].count==0)
            break;
        if ((--timers[i].count)==0) {
            memcpy(timers[i], timers[last_timer], sizeof(timers[0]));
            timers[last_timer--].count = 0;
            /* inform the process */
        }
    }
    /* ... */
}
int timer_add(int count, pid_t process)
{
    if (t_retry!=0)
        return -1;
    timers[last_timer].process = process;
    timers[last_timer].count = count;
    timers[last_timer].process = process;
    t_retry = 1;
    return 0;
}

 che il mio suggerimento possa esserti di chiarimento.
Sì, questa soluzione è comparsa sin dall'inizio del thread. Diciamo
che poi la discussione si è spostata su una questione filosofica:
"E' cosa buona e giusta disabilitare gli interrupt?"

 }
Mi sfugge l'utilizzo della t_retry. Sicuramente ti serve perchè hai
bisogno
che l'IRQ aggiorni last_timer. Ma perchè non puoi farlo direttamente
nella
timer_add alla fine? Non penso ci sia conflitto essendo l'incremento e
il decremento una operazione atomica.

 scadenza del nuovo timer.
invece di una lista puoi usare un btree, che e' piu' veloce in lettura
(log(n) invece di n)
Ciao Jack

 il decremento una operazione atomica.
Il problema è se chiami 2 volte la timer_add prima che scatti l'ISR.
In quel caso il giochetto non funziona e dovresti tornare una EAGAIN
in userspace.

 "E' cosa buona e giusta disabilitare gli interrupt?"
Se non trovi una implementazione a prova di bomba è *necessario*.
E IMO non ci sono implementazioni che possano farne a meno.


 in userspace.
Infatti io proponevo di aggiornare direttamente nella timer_add() il
contatore
last_timer:
void timer_add(int count, pid_t process)
{
    timers[last_timer].process = process;
    timers[last_timer].count = count;
    last_timer++;
}
Se la "last_timer++;" è atomica, non dovrebbero esserci problemi, no?

 Se la "last_timer++;" è atomica, non dovrebbero esserci problemi, no?
ecco, come l'hai scritta non può funzionare.
L'int potrebbe arrivare tra i due assegnamenti o prima
dell'incremento, in ciascuno dei due casi non andrebbe.
Come l'avevo scritta io l'int può arrivare in qualsiasi momento, al
massimo lasciando sporco il "buco" (come lo chiami te) passato (per
questo il doppio assegnamento di process prima e dopo il count che fa
da lock).
Ciao!

 da lock).
Hai ragione...

te la butto li': implementazione con liste e 'semafori'
a flag (In Linux: test_and_set_bit, atomic_xxx etc).
l' ISR non fa chiamate di sistema: il rilasco dei timer
scaduti viene fatto a livello user...
Puoi implementare la lista anche con elementi statici
senza usare calloc e free...
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
typedef struct timer{
   void*  pNext;       // Next element
   void*  pBack;       // Previou element
   long	 counter;     // Tempo in tick del timer
   long	 current;     // Contatore temporaneo (facilita il debug)
}TIMER_T;
typedef struct LIST{
   void*    pTimer;  // Pointer alla lista di timer attivi
   void*    pExpired;   // Pointer alla lista di timer scaduti
   unsigned flags;
   long	   tickPace;
   long	   ticks;
}LIST_T;
#define LIST_TMR_BUSY 	(0x0001)
#define LIST_EXP_BUSY 	(0x0002)
int timer_add(LIST_T* pList, int tmo)
{
  TIMER_T* pNew;
  int	  result;
  result=0;
  if(NULL == (pNew=calloc(1, sizeof(TIMER_T))))
  {
      return(ERR_MEMORY);
  }	
  pNew->counter=tmo;
  // Aggiunge nuovo elemento nelle lista
  // nell' ordine opportuno...
  if(LIST_BUSY == (atomic_set_value(&pList->flags,LIST_TMR_BUSY)
                       &LIST_TMR_BUSY) )
  {
     free(pNew);
     return(ERROR_BUSY);
  }
  /******************************************************/
  list_add_ordered_timer(pList,pNew);
  atomic_clr(&pList->flags, LIST_TMR_BUSY);
  /******************************************************/
  return(0);
}
int timer_flush_expired(LIST_T* pList)
{
   TIMER_T*	pExp;
   if(LIST_EXP_BUSY == (atomic_set(&pList->flags, LIST_EXP_BUSY)
                          &LIST_EXP_BUSY))
     return(ERROR_BUSY);
   /******************************************************/
   pExt=pList->pExpired;
   pList->pExpired=NULL;               // FLUSH queue
   atomic_clr(&pList->flags, LIST_EXP_BUSY); // Rilascia lock
   /******************************************************/
   //Cancella tutti i timer spirati...
   while(NULL!=pExp)
   {
      TIMER_T* pNext;
       pNext=pExp->pNext;
       free(pExp);
       pExp=pNext;
    }
    return(0);
}
void timer_handle_isr(LIST_T* pList)
{
   TIMER_T* Timer;
    pList->ticks++;	// Counter free-running
    if(pList->flags & LIST_TMR_BUSY)
    {
       /* List update , non fare nulla...
        * Incrementa il numero di ticks da sottrarre
        */
        pList->tickPace++;
        if(pList->tickPace < MAX_ALLOWED_TICK)
            return;
        // Eventuale gestione anomalia: un processo
        // tiene bloccata la lista da troppo tempo...
	return;
    }
    pTimer=pList->pTimer;
    while(NULL!=pTimer){
        if(pTimer->current < pTimer->counter)
           pTimer->current += pList->tickPace;
        else{
	    // TIMER SCADUTO: Rimuoverlo dalla lista
	    // dei timer attivi, parcheggio nella lista
             // timer spirati...
	   if(0 == (pList->flags & LIST_EXP_BUSY))
		list_remove_timer(pList,pTimer);
            else
            {
	      // verra' rimosso al prossimo giro....
               // Eventuale gestione anomalia se lista
               // bloccata da troppo tempo...
            }
	}
         pTimer=pTimer->pNext;
    }
    pList->tickBusy=1;  // Incremento normale ...
}
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

 Hai ragione...
Fossi in te una prova gliela darei, a me sembra la soluzione migliore
tra liste, flag e "staccaggio" degli interrupt.
Ciao!


Non mi sembra un gran che... I timer non scadono il tick giusto e ci
sono troppi casi di anomalia. :-|

 sono troppi casi di anomalia. :-|
Solo se l' interrupu entra nel momento in cui si aggiunge un
timer. I casi di anomalia sono 2.
In compenso non si disabilitano gli interrupt
b.


Beh, questo anche nell'implementazione mia, solo che funziona anche
quando l'int arriva mentre si aggiunge il timer.
Oltretutto non vedo chi e quando possa richiamare la funzione di clean-
up dei timer scaduti.
A parte queste due cose è ovviamente meglio della mia (molto meno
smanettona e molto più scalabile).
Ciao!

 Ciao!
Mah! nel caso specifico si cerca di trovare una via
per evitare la disabilitazione degli irq ab-stracazzium,
comunque tutte le implementazioni sono valide,piu' o meno,
dall' array statico alle liste. Cosa sia meglio dipende
dai requisiti di progetto, che qui non sono stati
specificati, quindi e' una discussione piu' sui generis ;-)
bye
B.