e a tutti i miei nonni.
Un ringraziamento speciale ai coinquilini di via Bologna e a Sara che mi hanno sempre supportato e sopportato in questi anni di Università.
Introduzione 10
1 Implementazione della routing table nella RELENG 4 13
1.1 Strutture interne . . . 13
1.2 Introduzione alle funzioni di accesso alla routing table . . . 17
1.3 Le funzioni della famiglia rtalloc . . . . 19
1.3.1 La funzione rtalloc1 . . . . 19
1.3.2 Analisi riga per riga del codice di rtalloc1 . . . . 21
1.3.3 La funzione rtalloc_ign . . . . 22
1.3.4 La funzione rtalloc . . . . 23
1.4 La macro RTFREE e la funzione rtfree . . . . 24
1.5 La macro IFAFREE e la funzione ifafree . . . . 26
1.6 Le funzioni rtrequest e rtrequest1 . . . 26
1.7 La funzione rtredirect . . . . 31
1.8 La funzione rt_setgate . . . . 32
1.9 La funzione rtinit . . . . 34
2 Implementazione della TCP Host Cache 36 2.1 Introduzione . . . 36
2.2 La struttura interna della TCP Host Cache . . . . 37
2.2.1 Bucket Row . . . 37
2.2.2 TCP Host Cache . . . . 40
2.3 Le funzioni di gestione della TCP Host Cache . . . . 41
2.3.1 La funzione tcp_hc_init . . . 42
2.3.2 La funzione tcp_hc_lookup . . . . 42
2.3.3 La funzione tcp_hc_insert . . . . 43 2
2.3.4 La funzione tcp_hc_get . . . . 44 2.3.5 La funzione tcp_hc_getmtu . . . . 44 2.3.6 La funzione tcp_hc_gettao . . . . 44 2.3.7 La funzione tcp_hc_updatemtu . . . . 45 2.3.8 La funzione tcp_hc_update . . . . 45 2.3.9 La funzione tcp_hc_updatetao . . . . 46 2.3.10 La funzione tcp_hc_list . . . . 46 2.3.11 La funzione tcp_hc_get . . . . 47
3 Reimplementazione del protocollo ARP 48 3.1 Introduzione . . . 48 3.2 Implementazione originale . . . 49 3.2.1 Struttura interna . . . 49 3.2.2 Variabili globali . . . 51 3.2.3 La funzione arp_init . . . . 52 3.2.4 La funzione arpintr . . . . 52 3.2.5 La funzione in_arpinput . . . . 53 3.2.6 La funzione arptimer . . . . 55 3.2.7 La funzione arptfree . . . . 56 3.2.8 La funzione arplookup . . . . 56 3.2.9 La funzione arpresolve . . . . 57 3.2.10 La funzione arp_ifinit . . . 59 3.2.11 La funzione arprequest . . . . 60 3.2.12 La funzione arp_rtrequest . . . . 60
3.3 La nuova versione del protocollo ARP . . . 62
3.3.1 Linee guida per la reimplementazione . . . 62
3.3.2 La lista di tabelle di mapping . . . 65
3.3.3 Struttura di una entry dell’ARP cache . . . 67
3.3.4 La funzione find_ifa . . . . 68
3.3.5 La funzione llentry_free . . . . 68
3.3.6 La funzione arp_init . . . . 69
3.3.7 La funzione in_arpinput . . . . 69
3.3.9 La funzione arptfree . . . . 70 3.3.10 La funzione arplookup . . . . 70 3.3.11 La funzione arpresolve . . . . 71 3.3.12 La funzione arp_ifinit . . . 73 3.3.13 La funzione arprequest . . . . 73 3.3.14 La funzione arp_rtrequest . . . . 74
4 Reimplementazione del Neighbor Discovery in IPv6 75 4.1 Introduzione . . . 75 4.2 L’implementazione originale . . . 77 4.2.1 Strutture Interne . . . 77 4.2.2 La funzione nd6_rtrequest . . . . 78 4.2.3 La funzione nd6_timer . . . . 82 4.2.4 La funzione nd6_free . . . . 84 4.2.5 La funzione nd6_purge . . . . 85 4.2.6 La funzione nd6_is_addr_neighbor . . . . 86 4.2.7 La funzione nd6_lookup . . . . 86 4.2.8 La funzione nd6_cache_lladdr . . . . 87 4.2.9 La funzione nd6_need_cache . . . 90 4.2.10 La funzione nd6_output . . . . 90 4.2.11 La funzione nd6_storelladdr . . . . 93 4.3 La nuova implementazione . . . 93 4.3.1 La struttura interna . . . 93 4.3.2 La funzione nd6_rtrequest . . . . 95 4.3.3 La funzione nd6_lookup . . . . 96 4.3.4 La funzione nd6_free . . . . 97 4.3.5 La funzione nd6_storelladdr . . . . 98 4.3.6 La funzione nd6_timer . . . . 98 4.3.7 La funzione nd6_purge . . . . 99 4.3.8 La funzione nd6_cache_lladdr . . . . 99 4.3.9 La funzione nd6_output . . . 100 Conclusioni 101
1.1 Struttura rtentry. . . . 15 1.2 Struttura rt_metrics. . . . 17 1.3 Struttura route. . . . 17 1.4 Dichiarazione di rtalloc1. . . . 19 1.5 Dichiarazione di rtalloc_ign. . . . 22 1.6 Dichiarazione di rtalloc. . . . 24 1.7 Dichiarazione di rtfree. . . . 24 1.8 Dichiarazione di ifafree. . . . 26 1.9 Dichiarazione di rtrequest. . . . 27 1.10 Dichiarazione di rtrequest1. . . . 27 1.11 Dichiarazione di rtredirect. . . . 31 1.12 Dichiarazione di rt_setgate. . . . 33 1.13 Dichiarazione di rtinit. . . . 34 2.1 Struttura rt_metrics_lite. . . . 36
2.2 Strutture dati che compongono la TCP Host Cache . . . . 38
2.3 Struttura hc_metrics. . . . 39
2.4 Struttura hc_head. . . . 40
2.5 Struttura tcp_hostcache. . . . 40
2.6 Dichiarazione di tcp_hc_init. . . . 42
2.7 Costanti di inizializzazione dei membri della struttura tcp_hostcache. 42 2.8 Dichiarazione di tcp_hc_lookup. . . . 43 2.9 Dichiarazione di tcp_hc_insert. . . . 43 2.10 Dichiarazione di tcp_hc_get. . . . 44 2.11 Dichiarazione di tcp_hc_getmtu. . . . 44 2.12 Struttura tcp_hc_gettao. . . . 44 6
2.13 Dichiarazione di tcp_hc_updatemtu. . . . 45
2.14 Dichiarazione di tcp_hc_update. . . . 45
2.15 Dichiarazione di tcp_hc_updatetao. . . . 46
2.16 Dichiarazione di sysctl_tcp_hc_list. . . . 46
2.17 Dichiarazione di tcp_hc_purge. . . . 47
3.1 Testa della ARP cache. . . 49
3.2 Struttura llinfo_arp. . . . 50 3.3 Dichiarazione di arp_init. . . . 52 3.4 Dichiarazione di arpintr. . . . 52 3.5 Dichiarazione di in_arpinput. . . . 53 3.6 Dichiarazione di arptimer. . . . 55 3.7 Dichiarazione di arptfree. . . . 56 3.8 Dichiarazione di arplookup. . . . 56 3.9 Dichiarazione di arpresolve. . . . 57 3.10 Dichiarazione di arp_ifinit. . . . 59 3.11 Dichiarazione di arprequest. . . . 60 3.12 Dichiarazione di arp_request. . . . 60
3.13 Inserzione del nuovo membro lltables nella struttura ifnet. . . . 65
3.14 Struttura lltable. . . . 65 3.15 Dichiarazione di lltable_new. . . . 66 3.16 Dichiarazione di lltable_free. . . . 66 3.17 Dichiarazione di llentry. . . . 67 3.18 Dichiarazione di find_ifa. . . . 68 3.19 Dichiarazione di llentry_free. . . . 68
3.20 Dichiarazione della nuova arplookup. . . . 70
3.21 Dichiarazione della nuova arpresolve. . . . 71
4.1 Struttura llinfo_nd6. . . . 77 4.2 Dichiarazione di nd6_rtrequest. . . . 80 4.3 Dichiarazione di nd6_timer. . . . 83 4.4 Dichiarazione di nd6_free. . . . 85 4.5 Dichiarazione di nd6_purge. . . . 85 4.6 Dichiarazione di nd6_is_addr_neighbor. . . . 86
4.7 Dichiarazione di nd6_lookup. . . . 87 4.8 Dichiarazione di nd6_cache_lladdr. . . . 87 4.9 Dichiarazione di nd6_need_cache. . . . 90 4.10 Dichiarazione di nd6_output. . . . 91 4.11 Dichiarazione di nd6_storelladdr. . . . 93 4.12 Dichiarazione di llinfo_nd6. . . . 94
4.13 Dichiarazione di in6_ifextra e della macro ND6_LIST_HEAD. . . . . 95
4.14 Dichiarazione di nd6_lookup. . . . 96
4.15 Dichiarazione di nd6_free. . . . 97
1.1 Valori per rt_flag . . . . 16 4.1 Valori per ln_flag . . . . 79 4.2 Valori dei flags newentry, olladdr, lladdr e llchange . . . . 89
Lo scopo della tesi è analizzare e riorganizzare le strutture che, nell’implemen-tazione attuale dei sistemi FreeBSD, rappresentano la tabella di routing. In particolare, il lavoro svolto prende come base di partenza la revisione RELENG 4.9 di FreeBSD e si pone come obiettivo quello di snellire e rendere più efficiente la struttura di cia-scuna entrata nella tabella di routing. Tale necessità nasce dal fatto che, attualmente, viene utilizzata una tabella di routing estremamente ingigantita a causa della memoriz-zazione di informazioni non strettamente legate al packet routing. Diversi protocolli, infatti, la sfruttano per immagazzinare dati utilizzati per scopi differenti dal semplice mapping destinatario - next hop. In particolare due sono le tipologie di informazione immagazzinate nella routing table che non vengono utilizzate per il routing:
• metriche relative a connessioni TCP con sistemi remoti;
• informazioni necessarie al mapping tra indirizzi di livello 2 e indirizzi di
livel-lo 3.
Nel primo caso, “una entrata mantiene le informazioni sui parametri TCP misu-rati durante sessioni TCP precedenti. Ciò è utile per avere valori iniziali di parten-za migliori per le successive connessioni verso lo stesso host remoto. A seconda dei parametri della network (ritardo, larghezza di banda, massima MTU, congestion window) tra il sistema locale e quello remoto, questo meccanismo può condurre ad un significativo incremento della velocità per le nuove connessioni successive alla prima”1.
Al secondo insieme, invece, appartengono tutta una serie di informazioni utilizzate dai protocolli che forniscono il mapping L2 - L3 come ad esempio ARP, per IPv4, e l’estensione ND6 di IPv6.
1trad. netinet/tcp_hostcache.c
Una tale implementazione comporta, quindi, svariati problemi. Dal punto di vista del codice, la concezione esposta sopra, produce una più difficile manutenzione. Ciò è dovuto a due problemi principali:
condivisione - essendoci svariati protocolli che condividono la stessa routing table, risulta particolarmente difficile metterli d’accordo tutti. Un meccanismo che intende cancellare una entrata considerata non più utilizzabile, non può farlo finchè, quella entrata, serve a qualcuno. Diventa necessario, quindi, una mutua esclusione che permetta di controllare gli accessi alla struttura e impedisca con-flitti. L’utilizzo di semafori, però, aumenta non poco la complessità del codice, proprio perchè si deve tenere di conto di tutti i meccanismi che dovranno agire sulla routing table.
consistenza - ciascun protocollo che utilizza la routing table, ha un insieme di infor-mazioni su cui può agire. Ovviamente, però, non accede a tutte le inforinfor-mazioni contenute in una singola entrata. Ciò porta al problema della consistenza dei dati. Se un protocollo di routing modifica una entrata, tale modifica dovrà essere ag-ganciata anche dagli altri meccanismi che condividono la stessa entrata, affinchè possano effettuare i cambiamenti necessari per mantenere tutte le informazioni di una entrata, consistenti tra di loro. Ciò da origine ad una serie di chiamate incrociate tra i vari protocolli che, ovviamente, rendono molto difficoltosa la lettura del codice.
Per quanto riguarda l’efficienza, anche questa risulta peggiorata. Una struttura così vasta, comporta l’allocazione e la deallocazione di ampie aree di memoria. Questo problema è sentito maggiormente nei casi in cui la tabella di routing contiene molte entrate in più delle quattro o cinque che si possono trovare in un sistema multihomed ma rimane presente in ogni caso.
Infine una tale implementazione, risulta concettualmente sbagliata. Come detto precedentemente, alla tabella di routing vengono relegate funzioni che per sua defi-nizione non avrebbe. In effetti, la struttura attuale, è il risultato della fusione di varie tabelle che concettualmente dovrebbero restare separate. Tale fusione è di tipo verti-cale poichè interessa la routing table (packet routing di livello 3), ARP table per IPv4 e neighbor cache di ND6 per IPv6 (mapping tra i livelli 2 e 3) e infine metriche del TCP (livello 4).
Il capitolo 1 sarà totalmente dedicato all’analisi della implementazione originale della routing table. Nella prima parte, verranno prese in considerazione le strutture utilizzate nel kernel, per rappresentare ciascuna entrata della tabella di routing, mentre, nella seconda parte, saranno analizzate le funzioni di accesso a tale struttura e gli effetti che hanno su di essa.
È dunque chiaro che le modifiche da apportare ad una tale implementazione deb-bano essere tese a rendere più netto il confine tra le diverse strutture gestite dai vari protocolli. Informazioni concettualmente separate devono prendere posto entro strut-ture quanto più staccate tra loro. In questo senso il lavoro svolto si divide in due parti:
• rimuovere dalla routing table le informazioni proprie del TCP • spostare quelle relative al mapping L2 - L3
Il primo punto verrà portato avanti nel capitolo 2 utilizzando una struttura alternativa dedicata alle metriche del TCP chiamata TCP Host Cache. Gran parte del capitolo sarà dedicata all’analisi di tale cache, sviluppata da Andre Opperman per la versione CURRENT di FreeBSD. Questa struttura è stata portata nella STABLE, ovviamente con alcune modifiche ed accorgimenti che verranno descritti sempre nel capitolo 2.
Il secondo punto, occuperà i successivi due capitoli poichè le modifiche effettuate alla routing table avranno implicazioni tanto per ARP (capitolo 3) quanto per ND6 di IPv6 (capitolo 4). A differenza della TCP host cache, sia la nuova ARP cache che la nuova Neighbor cache, sono state completamente sviluppate nel corso di questa tesi e risultano essere del tutto originali rispetto alle strutture precedenti. Verranno dunque presentati anche questi due meccanismi di mapping sia nel loro funzionamento originale che in quello successivo alla reimplementazione, soffermandosi in particolare sul lavoro di pulizia dedicato alla routing table stessa.
Implementazione della routing table
nella RELENG 4
1.1
Strutture interne
Nella revisione RELENG 4.9 di FreeBSD, il kernel fornisce un meccanismo co-mune, che permette a tutti i protocolli di inserire, cercare e rimuovere entrate da una tabella di routing centrale. Questo meccanismo si basa su una struttura interna ad al-bero binario di tipo Patricia tree per organizzare indirizzi relativi sia ad hosts che a networks. Ad ogni famiglia di indirizzi corrisponde un albero. Ogni nodo dell’albero ha associati un indirizzo (che rappresenta la chiave di ricerca) e una maschera. Nodi relativi ad hosts, avranno questa maschera costituita da tutti 1, mentre per quelli relativi a networks, la maschera coinciderà con la netmask della rete stessa.
L’indirizzo che deve essere cercato viene considerato come una sequenza di bit: in questo modo è possibile utilizzare lo stesso set di funzioni per mantenere l’albero con-tenente indirizzi IPv4, quello concon-tenente indirizzi IPv6, ecc. . . Un lookup all’interno di un albero ha successo solo se viene trovato un nodo, la cui chiave coincide con l’in-dirizzo cercato logicamente ANDato con la maschera del nodo stesso. Ovviamente si possono avere più match, dovuti a nodi che hanno lo stesso net-number della chiave di ricerca. La soluzione sta nel cosidetto longest-match, cioè tra due nodi si sceglie quello con la netmask più lunga.
Questa struttura ad albero viene ad essere completamente opaca alle funzioni che gestiscono la routing table e ai protocolli che le utilizzano. Esiste, infatti, un set di
funzioni (il cui nome è del tipo rnh_XXX o rn_XXX) che sono richiamate per ag-giungere, eliminare, fare ricerche sui nodi dell’albero, semplicemente riferendosi alla coppia indirizzo - maschera della chiave di ricerca. Tali funzioni non verranno ana-lizzate in profondità poichè il codice che si intende trattare non dipende dalla loro implementazione.
La struttura fondamentale che invece, sta alla base della routing table nel codice FreeBSD è rtentry. Tale struttura è dichiarata nel file header net/route.h e corrisponde ad una entrata nella routing table stessa. Le principali informazioni che in essa si possono ritrovare sono:
• indirizzo di destinazione
• indirizzo del gateway o il MAC address del destinatario • flags che indichino il tipo di entrata
• interfaccia da utilizzare per inoltrare il pacchetto verso la giusta direzione • metriche relative a connessioni passate verso l’host destinazione
La Figura 1.1 mostra la dichiarazione della struct rtentry i cui membri vengono descritti di seguito:
rt_nodes - sono i nodi dell’albero patricia tree utilizzato come struttura interna per la routing table. Questi membri includono nella loro struttura l’indirizzo di desti-nazione e la netmask usate quando la rotta é stata creata. Le macro rt_key(rt) e rt_mask(rt) possono essere utilizzate per accedere a queste informazioni: dato un puntatore a struct rtentry, ritornano rispettivamente la chiave (cioé l’indirizzo di destinazione) e la netmask associata.
rt_gateway - punta all’indirizzo del next hop. Si evidenziano due casi:
1. l’host destinatario é direttamente raggiungibile. In questo caso rt_gateway é l’indirizzo hardware dell’host stesso
2. la chiave non é direttamente raggiungibile, ma bisogna passare per un gateway; nel qual caso rt_gateway rappresenta l’indirizzo del gateway
net/route.h struct rtentry {
struct radix_node rt_nodes[2]; /* tree glue, and other values */ #define rt_key(r) ((struct sockaddr *)((r)->rt_nodes->rn_key))
#define rt_mask(r) ((struct sockaddr *)((r)->rt_nodes->rn_mask)) struct sockaddr *rt_gateway; /* value */
long rt_refcnt; /* # held references */
u_long rt_flags; /* up/down, host/net */
struct ifnet *rt_ifp; /* the answer: interface to use */ struct ifaddr *rt_ifa; /* the answer: interface to use */ struct sockaddr *rt_genmask; /* for generation of cloned routes */ caddr_t rt_llinfo; /* pointer to link level info cache */ struct rt_metrics rt_rmx; /* metrics used by rx’ing protocols */ struct rtentry *rt_gwroute; /* implied entry for gatewayed routes */ int (*rt_output) __P((struct ifnet *, struct mbuf *,
struct sockaddr *, struct rtentry *)); /* output routine for this (rt,if) */
struct rtentry *rt_parent; /* cloning parent of this route */
void *rt_filler2; /* more filler */
};
net/route.h
Figura 1.1: Struttura rtentry.
rt_refcnt - é il reference count: conta il numero di riferimenti a questa struttura. Ogni processo che ne ottiene il riferimento incrementa il valore di questo membro in modo da notificare che l’entrata non é inutilizzata. Serve in fase di deallo-cazione: non si può deallocare una entrata che é utilizzata da qualcuno. Ciò significa che il codice che ottiene l’indirizzo a una route, non se ne può lib-erare semplicemente deallocando la struttura, ma deve prima controllare se il reference count é a 0. Questa operazione, detta di rilascio, viene eseguita richia-mando la funzione rtfree oppure la macro RTFREE (vedi paragrafo 1.4 più avanti).
rt_flags - indica la tipologia dell’entrata (vedi lo schema 1.1) rt_ifp - punta all’interfaccia da utilizzare per inoltrare il pacchetto
rt_ifa - viene utilizzato per ottenere il source address nell’header del pacchetto rt_genmask - se è non NULL, punta ad una struttura sockaddr che rappresenta la
net-mask delle rotte che da essa verranno clonate (vedi paragrafo 1.6 sulla funzione rtrequest1).
rt_llinfo - permette ai protocolli di livello 2 di memorizzare in una entrata della routing table il riferimento alle loro prorpie specifiche strutture (vedi capitoli 3 e 4 per ARP, ND6 più’ avanti)
Constante Descrizione
RTF_UP route usable
RTF_GATEWAY destination is a gateway RTF_HOST host entry (net otherwise) RTF_REJECT host or net unreachable
RTF_DYNAMIC created dynamically (by redirect) RTF_MODIFIED modified dynamically (by redirect)
RTF_DONE message confirmed
RTF_CLONING generate new routes on use RTF_XRESOLVE external daemon resolves name RTF_LLINFO generated by link layer (e.g. ARP) RTF_STATIC manually added
RTF_BLACKHOLE just discard pkts (during updates) RTF_PROTO2 protocol specific routing flag RTF_PROTO1 protocol specific routing flag RTF_PRCLONING protocol requires cloning RTF_WASCLONED route generated through cloning RTF_PROTO3 protocol specific routing flag RTF_PINNED future use
RTF_LOCAL route represents a local address RTF_BROADCAST route represents a bcast address RTF_MULTICAST route represents a mcast address
Tabella 1.1: Valori per rt_flag
rt_rmx - metriche associate alla routing entry, per lo più utilizzate da TCP (vedi figura 1.2)
rt_gwroute - punta alla entrata relativa al gateway rt_output - non utilizzato
rt_parent - se l’entrata é stata clonata, punta alla rtentry del padre rt_filler2 - non utilizzato
Un’altra struttura molto utilizzata nel codice relativo alle tabelle di routing è route mostrata nella figura 1.3. Questa è costituita da un indirizzo di destinazione (ro_dst) e da un riferimento ad una rtentry (ro_rt). Da notare che ro_dst è una istanza della struct sockaddr, non il puntatore. Questo significa che la funzione può essere usata solo con indirizzi che sono più corti della struttura sockaddr di default stessa.
net/route.h struct rt_metrics {
u_long rmx_locks; /* Kernel must leave these values alone */ u_long rmx_mtu; /* MTU for this path */
u_long rmx_hopcount; /* max hops expected */
u_long rmx_expire; /* lifetime for route, e.g. redirect */ u_long rmx_recvpipe; /* inbound delay-bandwidth product */ u_long rmx_sendpipe; /* outbound delay-bandwidth product */ u_long rmx_ssthresh; /* outbound gateway buffer limit */ u_long rmx_rtt; /* estimated round trip time */ u_long rmx_rttvar; /* estimated rtt variance */
u_long rmx_pksent; /* packets sent using this route */ u_long rmx_filler[4]; /* will be used for T/TCP later */ };
net/route.h
Figura 1.2: Struttura rt_metrics.
net/route.h struct route {
struct sockaddr ro_dst; struct rtentry *ro_rt; };
net/route.h
Figura 1.3: Struttura route.
1.2
Introduzione alle funzioni di accesso alla routing
table
Una entrata può essere aggiunta, cancellata e ricercata nella routing table. I motivi per cui una entrata si trova nella routing table sono svariati. I principali sono:
• attivazione di una interfaccia
• aggiunta manuale tramite messaggi di routing • clonazione di una rtentry già presente
• redirezione
Tutte le volte che una interfaccia viene abilitata, il sistema crea automaticamente una entrata per ciascuna delle networks a cui quell’interfaccia appartiene. Ciò avviene in fase di inizializzazione del sistema oppure a causa del comando “ifconfig up” (ad es-empio “ifconfig ed0 up”), che abilita un’interfaccia precedentemente down. In questi casi viene richiamata la funzione rtinit (vedi paragrafo 1.9) che si preoccupa di in-vocare rtrequest1 con comando RTM_ADD (vedi paragrafo 1.6), per creare la nuova entrata e di informare i processi in ascolto su socket route, della nuova rotta.
La cosa opposta avviene se un’interfaccia viene disabilitata, per esempio a causa del comando “ifconfig ed0 down”. In questo caso, infatti, viene eseguita una ulteriore chiamata alla rtinit la quale, questa volta, elimina tutte le entrate della routing table, relative a quell’interfaccia.
Un’altro motivo di inserimento di una entrata nella routing table è rappresentato dai messaggi di routing inviati dai processi al kernel. E’ questo il caso, per esempio, del comando “route add . . . ” con il quale si aggiunge manualmente una nuova rotta. Messaggi di routing, comunque, possono essere inviati al kernel anche da altri processi come routed o gated che sono dei demoni di routing. In entrambi i casi, quando il kernel riceve un messaggio di questo tipo, è la funzione route_output che si occupa di richiamare direttamente la rtrequest(RTM_ADD, . . . ). Ovviamente anche in questo caso può succedere l’inverso e cioè che arrivino al kernel messaggi per eliminare una entrata.
Il terzo punto deriva dal fatto che spesso si cerca una rotta che ancora non è presente nella routing table ma che è possibile ottenere dalle rotte già contenute in essa. Un esempio di questa situazione è il seguente: supponiamo di avere nella routing table un’entrata che specifica la rotta per la network 10.10.0.0/16, e che si intenda fare un ping verso l’host 10.10.0.1 a cui però, non corrisponde nessuna rotta. E’ chiaro che l’interfaccia su cui il sistema dovrà inviare il ping sarà quella specificata dall’entrata per 10.10.0.0/16. Il meccanismo di routing fornito dal kernel, riconosce che l’indiriz-zo 10.10.0.1 appartiene alla network 10.10.0.0/16 e dunque crea automaticamente una nuova entrata per questo indirizzo, ricopiandone i valori da quella relativa alla network. Questa operazione è detta clonazione e permette al kernel, in seguito alla ricerca del-la rotta verso un host, di ottenere rotte che non ha, da quelle già presenti. Questo meccanismo è implementato nella funzione rtalloc1 (vedi paragrafo 1.3) che serve ad eseguire ricerche nella routing table. E’ proprio nel codice di questa funzione che il sistema fa il test per capire se sia il caso di eseguire la clonazione e quindi richiamare rtrequest per effettuare la clonazione vera e propria. Questa volta però la rtrequest non viene richiamata con il comando RTM_ADD ma con uno specifico comando per la clonazione: RTM_RESOLVE.
Infine abbiamo la redirezione. Quando un ICMP redirect è ricevuto dal sistema, viene richiamata rtredirect (vedi paragrafo 1.7 a pagina 31). Questa funzione ricerca la rtentry relativa alla rotta da redirigere per modificarla. Nel caso in cui non riesca a
trovarla, oppure la rtentry trovata abbia una netmask non valida, richiama la rtrequest per crearne una nuova in cui inserire le informazioni appena arrivate nel sistema.
1.3
Le funzioni della famiglia rtalloc
rtalloc, rtalloc_ign e rtalloc1 sono le funzioni normalmente chiamate per effettuare la ricerca di una entrata nella routing table.
1.3.1
La funzione rtalloc1
Il cuore del processo di interrogazione della routing table è la funzione rtalloc1 la cui dichiarazione è riportata in figura 1.4.
net/route.c struct rtentry *
rtalloc1(dst, report, ignflags) register struct sockaddr *dst; int report;
u_long ignflags;
net/route.c
Figura 1.4: Dichiarazione di rtalloc1.
I parametri passati alla funzione sono:
dst - è un puntatore alla struttura sockaddr contenente l’indirizzo dell’host per il quale si sta cercando una rotta. Il membro sa_family serve a selezionare la tabella di routing su cui effettuare la ricerca.
report - è un intero ma viene usato come booleano: se diverso da zero, serve al chiamante per richiedere un messaggio di routing di risposta.
ignflags - unsigned che specifica quali tra i flags della entry trovata, debbano essere ignorati
rtalloc1 prende l’indirizzo puntato da dst e ne cerca la rtentry corrispondente nella routing table. Quando viene trovata una entry con il flag RTF_CLONING o RTF_PRCLONING settati e l’azione di questi flags non è mascherata, rtalloc1 ge-nera automaticamente una nuova entrata utilizzando le informazioni contenute nella vecchia entry per chiamare rtrequest (vedi paragrafo 1.6).
Ovviamente sono valide le seguenti asserzioni:
• una rtentry clonata non può essere clonabile (vengono resettati i flags
RTF_CLONING e RTF_PRCLONING)
• la destinazione della nuova entry non sarà certamente statica, cioè creata
manu-almente usando il programma route(9) (viene resettato il flag RTF_STATIC)
• posso ottenere una route verso un host da una entry relativa a una network, in
questo caso setta il flag RTF_HOST
Per queste ragioni, vengono cambiati destinatario e alcuni flags. Inoltre il reference count viene incrementato di 1 (se la entry è ottenuta per clonazione, l’incremento diventa 0 → 1).
Infine, se report è diverso da 0 rtalloc1 genera dei messaggi che invia, utilizzando l’interfaccia socket route(4), ai processi in ascolto. I messaggi sono:
RTM_MISS se la ricerca non ha avuto successo. Ciò può essere dovuto a tre cause principali:
- non è stato trovato il nodo cercato
- il nodo trovato è di tipo ROOT, ossia e’ la radice del Patricia Tree. Se la ricerca ottiene un nodo ROOT, significa che non si è verificato nessun match
- la clonazione non ha avuto successo (in questo caso viene anche inviato l’errore generato dalla rtrequest)
RTM_RESOLVE se la nuova route ottenuta dalla clonazione richiede di essere risolta esternamente (cioè ha il flag RTF_XRESOLVE attivo)
RTM_ADD in caso di clonazione avvenuta con successo. Serve a informare i proces-si in ascolto che è stata aggiunta la nuova rtentry alla routing table. Contestual-mente viene inviato anche il riferimento a una sruttura rt_addrinfo contenente le informazioni relative alla nuova rtentry.
rtalloc1 ritorna, in caso di successo, un puntatore alla rtentry trovata, altrimenti ritorna NULL. Questo significa che lavorare sul risultato tornato da rtalloc1 significa agire direttamente su una entry della routing table!
1.3.2
Analisi riga per riga del codice di rtalloc1
135-136 La ricerca ha esito positivo se valgono le seguenti condizioni:
1. esiste una tabella di routing per la famiglia di protocolli indicata da dst->sa_family
2. rnh->rnh_machaddr ritorna un puntatore non nullo
3. la struttura radix_node ritornata da rnh_matchaddr 1non ha settato il flag RNF_ROOT
141 Se le tre condizioni sono verificate, il puntatore alla struttura radix_node è me-morizzato in rt e newrt. NOTA - Nella definizione di struct rtentry la struttura radix_node relativa alla foglia è all’inizio, quindi il puntatore alla radix_node tornato da rnh_matchaddr è in realtà anche un puntatore alla rtentry che la contiene!
142 Si memorizzano nella variabile locale nflags tutti i flags settati relativi a rt, tranne quelli che sono indicati nel parametro ignflags, che devono cioè essere ignorati. 143-150 se report è diverso da zero, e almeno uno dei due flags RTF_CLONING o RTF_PRCLONING, è settato (significa che quando si usa deve essere clona-to), allora viene effettuata una chiamata alla funzione rtrequest con il comando RTM_RESOLVE, passando netmask, gateway e flags a 0 in modo da creare una nuova struttura rtentry, clone di quella trovata ma con destinazione diversa (è usata da ARP e per indirizzi Multicast). Nella variabile locale newrt viene messo l’indirizzo del puntatore alla rtentry creata.
151-159 se rtrequest ritorna un errore, newrt è ripristinato alla vecchia rtentry ritorna-ta dalla rnh_matchaddr e il relativo campo contenente il numero di riferimenti associati viene incrementato. Infine viene eseguito un salto alla lable miss: dove è generato un messaggio RTM_MISS
160-167 Se invece rtrequest ha ritornato una struct rtentry il cui flag RTF_XRESOLVE è settato, salta alla label miss: per inviare un messaggio di tipo RTM_RESOLVE
1rnh->rnh_machaddr è un puntatore a funzione dichiarato nella struct radix_node_head in
168-178 Se non ci sono salti a miss: riempie la struttura rt_addrinfo con gli indirizzi del destinatario, della netmask, del gateway e, se la entry ritornata da rtrequest punta a una interfaccia (rt->rt_ifp != NULL), inserisce anche tale interfaccia2 e l’indirizzo associato a tale interfaccia relativo a quella entry (rt->rt_ifa->ifa_addr). Quindi invia un messaggio di tipo RTM_ADD per in-formare i processi in ascolto, della nuova route aggiunta
179-180 Se la ricerca della rnh_matchaddr ha successo ma nè il flag RTF_CLONING nè il flag RTF_PRCLONING sono settati, la rtentry ritornata dalla rtalloc1 è la stessa rtentry trovata con rnh_matchaddr quindi viene soltanto incrementato il contatore dei riferimenti associati alla struttura (rt->rt_refcnt)
181-198 Se la ricerca non ha avuto successo oppure il nodo trovato ha il flag RNF_ROOT settato,allora incrementa la statistica rts_unreach e se il secondo parametro passato a rtalloc1 è non zero, genera un messaggio RTM_MISS. La funzione ritorna un puntatore a NULL.
1.3.3
La funzione rtalloc_ign
Questa interfaccia esegue le stesse operazioni di rtalloc ma permette al chiamante di specificare una maschera di flags che dovranno essere ignorati durante il processo di ricerca. A differenza di rtalloc1, nessun messaggio di notifica ai processi in ascolto verrà bloccato. Può essere utile quando si voglia fare una ricerca disabilitando l’azione dei flag RTF_CLONING o RTF_PRCLONING.
net/route.c void
rtalloc_ign(ro, ignore) register struct route *ro; u_long ignore;
net/route.c
Figura 1.5: Dichiarazione di rtalloc_ign.
Segue una analisi più dettagliata del codice di rtalloc_ign la cui dichiarazione è visualizzata in figura 1.5.
2alla riga di codice 175, TAILQ_FIRST(&rt->rt_ifp->if_addrhead)->ifa_addr produce il primo
degli indirizzi associati alla interfaccia rt_ifp. La macro è definita in sys/queue.h, mentre la struct
94-100 I parametri passati sono il riferimento a una route ro e un intero ignore che rappresenta i flag della entry contenuta nella route, che rtalloc1 dovrà ignorare durante la sua esecuzione
102 Se ro punta già ad una rtentry della routing table (ro->ro_rt!=NULL), verrà ana-lizzata quella struttura (rt)
103-104 Se rt ha già il riferimento ad una interfaccia (rt->rt_ifp!=NULL), e quella interfaccia è UP, la funzione ritorna senza eseguire nessun lookup (verrà usata quella route)
106-110 Altrimenti si richiama la macro RTFREE per decrementare il numero di riferimenti a rt e si annulla il puntatore ro->ro_rt3.
111 La precondizione relativa all’esecuzione di questa riga di codice è: ro->ro_rt=NULL. Viene quindi richiamata rtalloc1 passando:
1. l’indirizzo di destinazione, 2. l’intero 1
3. il parametro ignore
Ritorna quanto ritornato dalla rtalloc1
Sia la rtalloc che la rtalloc_ign non ritornano un valore. Il risultato della loro ricerca è sempre un puntatore alla entry cercata ma questa volta viene inserito nella struttura route ro passata dal chiamante.
1.3.4
La funzione rtalloc
rtalloc non fa altro che chiamare rtalloc_ign passando come secondo parametro 0 (significa che la funzione rtalloc1 dovrà considerare tutti i flags della struttura rtentry che verrà trovata).
Quando viene richiamata rtalloc (per la dichiarazione della stessa vedere la figura 1.6), il chiamante deve assicurarsi che i bit non utilizzati della struttura siano settati
3queste operazioni vengono effettuate al livello di priorità network protocol processing mediante la
net/route.c void
rtalloc(ro)
register struct route *ro;
net/route.c
Figura 1.6: Dichiarazione di rtalloc.
a 0. La route passata per riferimento, può contenere una entry valida; rtalloc ritorna senza eseguire la ricerca richesta se valgono tutte le seguenti condizioni:
+ ro->ro_rt è non NULL
+ il flag RTF_UP della entry è settato + esiste una interfaccia associata alla rtentry
Questa interfaccia di query non permette di specificare la maschera dei flags (per default nessun flag verrà ignorato) nè di richiedere/bloccare i messaggi di notifica per i processi in ascolto (per default nessun messaggio verrà bloccato).
1.4
La macro RTFREE e la funzione rtfree
Entrambe vengono utilizzate per eseguire l’operazione di rilascio di una entrata del-la routing table. Ridel-lasciare una rtentry non significa necessariamente deallocardel-la. Può accadere, infatti, che l’entrata sia utilizzata anche da un’altra parte nel codice, o ma-gari da un altro processo. La deallocazione porterebbe dunque a un panic del sistema che in tal modo cercherebbe di referenziare un’area di memoria che invece non è allo-cata. Una tale situazione è verificabile semplicemente andando a testare il valore del reference count relativo alla rtentry.
La macro RTFREE chiama la funzione rtfree solo se il numero dei riferimenti as-sociati alla rtentry rt è minore o uguale a 1, altrimenti decrementa il contatore dei riferimenti di uno.
net/route.c void
rtfree(rt)
register struct rtentry *rt;
net/route.c
Figura 1.7: Dichiarazione di rtfree.
rtfree decrementa il reference count della rtentry passata per riferimento dal chia-mante e la dealloca se non ci sono più riferimenti ad essa. Il problema con questo
membro della struttura rtentry è il seguente: ciascuna entrata, quando nasce, ha un reference count a 0, poichè sia rtinit che route_output lo decrementano dopo averla creata. Quando si arriva a cancellare una entrata, rtfree prima decrementa il reference count e poi ne verifica il valore ottenuto. Un valore inferiore a 0 è considerato errore e la rtentry non viene deallocata. Per questo motivo, rtrequest, prima di chiamare rtfree, provvede a incrementare il reference count di uno se questo produrrebbe un valore negativo per effetto del decremento. In tal modo la rtentry viene deallocata normalmente
207-225 Il parametro passato è il puntatore alla rtentry che deve rilasciare. Questa operazione viene effettuata se rt è non NULL e se esiste la tabella di routing per la famiglia di protocollo indicata dal campo sa_family, relativa alla foglia contenuta in rt
226-228 Se il reference count è uguale a zero ed è stata definita la funzione rnh_close4, prima di eseguire ulteriori operazioni, richiama tale funzione.
235 Se il reference count è inferiore o uguale a 0 e la route non è più utilizzabile (RTF_UP non settato) si può rilasciare la rtentry
236-237 Se il nodo radix_node è ancora parte dell’albero (RNF_ALIVE settato), op-pure è un nodo root (RNF_ROOT settato), viene generato un errore di panic. Altrimenti continua l’esecuzione del codice successivo
242 rttrash viene decrementato
245-248 Controlla che il reference count non sia minore di 0, nel qual caso la funzione genera un messaggio di errore e ritorna senza deallocare la struttura
255-256 L’indirizzo di interfaccia ifaddr da usare viene rilasciato richiamando la macro IFAFREE che decrementa il reference count relativo a ifaddr stessa se questo è maggiore di 0, altrimenti richiama la ifafree per deallocare la struttura (vedi paragrafo 1.5)
4rnh->rnh_close è un puntatore a funzione dichiarato nella struct radix_node_head in net/radix.h,
257-259 Se rt->rt_parent è non NULL, significa che punta alla rtentry dalla quale è stata clonata l’entrata che voglio liberare. Durante l’operazione di liberazione quel puntatore sarà cancellato quindi richiama la macro RTFREE sul padre 266-271 Dealloca la chiave della rtentry5e la rtentry stessa richiamando Free.
1.5
La macro IFAFREE e la funzione ifafree
La macro IFAFREE, definita nel file header net/if_var.h, chiama la funzione ifafree solo se il numero dei riferimenti associati alla ifaddr ifa è minore o uguale a 0, altri-menti decrementa il contatore dei riferialtri-menti.
net/route.c void
ifafree(ifa)
register struct ifaddr *ifa;
net/route.c
Figura 1.8: Dichiarazione di ifafree.
279-280 Se ifa è NULL viene generato un panic
281-284 Se il reference count è uguale a 0 dealloco la struttura ifaddr puntata da ifa altrimenti decremento il reference count.
1.6
Le funzioni rtrequest e rtrequest1
La funzione rtrequest non è altro che una interfaccia per la rtrequest1. E’ stata mantenuta per compatibilità con il resto del codice, permettendo di accedere agli stessi servizi che offre rtrequest1 ma con un diverso modo di passare i parametri.
In figura 1.9 viene presentata la dichiarazione di rtrequest. Segue la descrizione dettagliata del codice della funzione.
471-475 req è il comando da eseguire e può assumere i valori: RTM_DELETE, RTM_RESOLVE, RTM_ADD;
5deallocando la chiave, dealloca automaticamente anche l’indirizzo del gateway perchè allocati in
net/route.c int
rtrequest(req, dst, gateway, netmask, flags, ret_nrt) int req, flags;
struct sockaddr *dst, *gateway, *netmask; struct rtentry **ret_nrt;
net/route.c
Figura 1.9: Dichiarazione di rtrequest.
dst specifica la socket address che deve essere aggiunta o cancellata dalla routing table;
ret_nrt puntatore a rtentry che serve per ritornare l’indirizzo della entry cercata (viene messo a NULL in caso di insuccesso nella ricerca).
477-483 viene allocata una struttura rt_addrinfo in cui sono copiati i parametri passati alla funzione: flags, dst, gateway, netmask
484 chiamata alla funzione rtrequest1.
rtrequest1, la cui dichiarazione è presentata in figura 1.10, rappresenta il cuore del meccanismo che serve a modificare la routing table. L’intero req che rappresenta il tipo di modifica da eseguire e può assumere i valori RTM_ADD, RTM_RESOLVE e RTM_DELETE rispettivamente per aggiungere, clonare e cancellare una entrata della routing table. Viene richiamata da rtinit (vedi paragrafo 1.9) in fase di inizializzazione del sistema per attivare le interfacce, oppure per disattivarle in seguito al comando manuale, per esempio, ifconfig ed0 down. Richiamata da rtalloc1, svolge un ruolo centrale anche nella fase di clonazione di una rtentry. Grazie a rtrequest1, infatti, è possibile creare una nuova entrata derivandola da un’altra già esistente nella tabella di routing. E’ anche utilizzata dalla rtredirect (vedi paragrafo 1.7) nel caso in cui non trovi la rtentry da modificare e la debba quindi creare.
net/route.c int
rtrequest1(req, info, ret_nrt) int req;
struct rt_addrinfo *info; struct rtentry **ret_nrt;
net/route.c
Figura 1.10: Dichiarazione di rtrequest1.
558-561 Se il destinatario è un host, pone rti_info[NETMASK] a 0 e resetta i flag RTF_CLONING e RTF_PRCLONING. Le entry relative a host, infatti, non
de-vono essere clonate. Seguono i comandi che la funzione esegue su richiesta del chiamante.
RTM_DELETE
568-572 Richiama la funzione rnh_deladdr per estrarre la entry dall’albero. Se an-che uno solo dei flag RNF_ACTIVE o RNF_ROOT è settato, ritorna un errore. L’indirizzo del nodo estratto è anche quello della rtentry estratta
578-582 Se la entry estratta ha settato almeno uno tra i flag RTF_CLONING, RTF_PRCLONING, significa che probabilmente nel suo sottoalbero ci sono delle entries clonate da essa e quindi le cancella. Questa operazione viene eseguita richiamando la funzione rnh_walktree_from che scorre il sottoalbero passatole ed applica a tutte le foglie una funzione decisa dal chiamante. Questa iterazione continua finchè la funzione applicata ritorna 0 o non finiscono le foglie. Nel caso specifico in rtrequest viene scelta la funzione rt_fixdelete che date due rtentry rn e vp, cancella la prima se questa è stata clonata da vp
589-593 Se la entry estratta è relativa ad una route indiretta (cioè è espresso un gateway), rilascia il gateway relativo, con la macro RTFREE e annulla il con-tenuto del membro rt_gwroute della entry estratta
602 Ora che la route è stata eliminata dall’albero non è più utilizzabile quindi azzera il flag RTF_UP
607-608 Se la entry aveva una struct sockaddr associata ed è definita la funzione ifa->ifa_rtrequest6, la chiama. Questo serve al codice del protocollo ARP per rimuovere la arp entry associata alla rtentry che viene tolta dalla routing table. 614 Viene incrementato il contatore delle entry che esistono e che non appartengono
più all’albero della routing table (la variabile globale rttrash)
621-626 Se il chiamante vuole la entry estratta, il suo indirizzo viene copiato nel pun-tatore *ret_nrt. Altrimenti se il reference count fosse minore o uguale a 0, lo incrementa e rilascia la entry chiamando la funzione rtfree7.
6L’associazione ifa_rtrequest = arp_rtrequest viene effettuata nella arp_ifinit (vedi paragrafo
3.2.10) durante l’inizializzazione. Per approfondimenti si veda il capitolo 3 sul protocollo ARP
RTM_RESOLVE
ret_nrt punta alla entry da clonare. Essa viene clonata e l’indirizzo del clone assegnato a ret_nrt stesso.
630-638 Inizializza la variabile locale ifa con rt_ifa, la struttura info con i mem-bri rt_flags, rt_gateway e rt_genmask della entry puntata da rt = *ret_nrt, re-settando i flag RTF_CLONING, RTF_PRCLONING e RTF_STATIC e re-settando RTF_WASCLONED. Queste modifiche servono a rendere non clonabile la copia clonata dalla entry passata alla funzione, notificando che essa è già stata clona-ta. Inoltre se rt->rt_genmask punta a NULL viene settato RTF_HOST perchè la entry clone avrà destinatario un host
639 salta a 650
RTM_ADD
aggiunge una nuova entrata nella routing table e ne ritorna l’indirizzo in ret_nrt 642-643 Se il destinatario è raggiungibile tramite gateway ma nessun gateway è stato
specificato genera l’errore
645-647 Utilizza la funzione rt_getifa per ottenere l’indirizzo di interfaccia qualora non sia già contenuto in info. rt_getifa si serve dell’indirizzo del destinatario presente in info per cercare la struttura ifaddr corrispondente ad un indirizzo di interfaccia che appartenga alla stessa network. Se per qualche motivo tale ricerca non ha successo ritorna l’errore ENETUNREACH che genera la chiamata a senderr nella rtrequest1.
649 Quando si arriva alla label makeroute: la variabile locale ifa deve essere inizia-lizzata con l’indirizzo della giusta struttura ifaddr relativa al destinatario, e nella struttura info devono essere inizializzati i membri: rti_info[DST], rti_info[GATEWAY], rti_info[NETMASK] e rti_flags; rti_ifa è inizializzato solo per RTM_ADD
650-654 Alloca lo spazio necessario a contenere una struttura rtentry che, se non ci sono problemi di allocazione viene azzerata. I flags di questa struttura sono
a zero. Normalmente queste righe lo settano a 1, dopodichè rtfree lo decrementa a 0 e cancella la route (vedi paragrafo 1.4 su rtfree).
copiati da quelli passati dal chiamante e contenuti nella struttura info. In più viene settato il flag RTF_UP
659-662 Usando la funzione rt_setgate alloca lo spazio necessario per contenere in-dirizzi di dst e gateway, inizializza i membri rt_key e rt_gateway della copia e anche rt_gwroute se il destinatario non è direttamente raggiungibile (vedi paragrafo 1.8). Se rt_setgate ritorna un errore l’entrata viene rilasciata
667-675 Copia l’indirizzo del destinatario (contenuto in info->rti_info[DST]) nel-la struct sockaddr puntata da rt_key eventualmenta ANData con nel-la maschera (puntata da info->rti_info[NETMASK]), se specificata
682-685 Incrementa il reference count della ifaddr relativa alla entry (sia per RESOLVE che per ADD, è in atto la creazione di una entry nuova il cui campo rt_ifa punta a quella struttura!) inizializza i membri rt_ifa e rt_ifp della entry clone
687 rnh_addaddr viene chiamata per inserire quei due nodi nell’albero. Questo porterà alla inizializzazione dei membri dei due nodi, e alla modifica dell’albero. Alla rnh_addaddr vengono passati indirizzo del destintario, netmask, albero a cui aggiungere i due nodi e i due nodi.
689-721 Se rnh_addaddr non ha successo significa che il nodo che si vuole inserire esiste già nell’albero. In questo caso si richiama rtalloc1 per ottenere il riferi-mento all’entrata corrispondente, la si dealloca invocando prima rtrequest1(RTM_DELETE,. . . ) e poi RTFREE, e quindi si prova ad inserire nuovamente il nodo che volevamo aggiungere.
718-727 Se ancora i due nodi non sono stati inseriti, rilascia la entry relativa all’even-tuale gateway, rilascia la ifaddr corrispondente alla nuova entrata, dealloca la entry appena creata e ritorna l’errore EEXIST
729 Inizializza il membro rt_parent a NULL
736-743 Se il comando è RESOLVE copia le metriche resettando il packet counter e se nella entry originale era settato almeno uno tra i flags RTF_CLONING e RTF_PRCLONING, aggiorna il membro rt_parent con l’indirizzo della entry originale e ne incrementa il reference count (la entry originale adesso ha un nuovo puntatore che la punta)
749-750 Se esiste una funzione associata a ifa->ifa_rtrequest, viene chiamata. Questo punto è utile ai protocolli di livello 2 per aggiornare le loro strutture in funzione delle modifiche eseguite sulla routing table. Nel caso del protocollo ARP questa funzione corrisponde alla arp_rtrequest (vedi capitolo 3 sul protocollo ARP) 757-763 Esegue la stessa procedura presente in rt_setgate per il fissaggio delle altre
entrate. Ciò è utile per mantenere la consistenza tra le rtenrty della routing table 769-772 Se ret_nrt è non NULL significa che il chiamante vuole l’indirizzo della entry appena creata. Questo è quello che viene fatto e in più viene incrementato il reference count della nuova entry.
779 Se ha successo ritorna 0, altrimenti ritorna l’errore che si è verificato.
1.7
La funzione rtredirect
Quando viene ricevuto un ICMP redirect, icmp_input richiama rtredirect per ag-giornare immediatamente la routing table e generare un messaggio di routing verso i processi in ascolto sul socket route. Durante la sua esecuzione, se il lookup dell’entrata voluta non ha successo, richiama rtrequest per crearne una nuova.
net/route.c void
rtredirect(dst, gateway, netmask, flags, src, rtp) struct sockaddr *dst, *gateway, *netmask, *src; int flags;
struct rtentry **rtp;
net/route.c
Figura 1.11: Dichiarazione di rtredirect.
309-312 Se nel sistema non esiste un’interfaccia a cui è associato un indirizzo apparte-nente alla stessa network del gateway, significa che il gateway non è direttamente raggiungibile e genera un errore (ENETUNREACH)
313 Ricerca la entry relativa al destinatario da redirigere (ne mette l’indirizzo in rt) 321-323 Se la ricerca ha avuto successo, ma l’indirizzo del vecchio gateway di rt non
coincide con quello dell’host che ha inviato l’ICMP redirect oppure l’interfaccia per il nuovo gateway è diversa da quella del vecchio, genera un errore (EINVAL)
324-325 Se l’indirizzo del nuovo gateway coincide con uno degli indirizzi associati a una interfaccia del sistema, genera un errore (EHOSTUNREACH) poichè altri-menti redirigerebbe i pacchetti in uscita verso se stesso
334-335 Se invece la entry cercata non è stata trovata oppure è stata trovata ma ha una netmask non valida (di lunghezza inferiore a 2), crea una nuova entry saltando alla label create:(346)
340-375 Se l’entrata da modificare rappresenta una route indiretta, prosegui, altrimen-ti genera un errore (EHOSTUNREACH)
341 Se la entry prima rappresentava una route verso una network e ora deve diventare una route verso un host, ne crea una nuova, altrimenti la modifica
CREA
346-360 Se la entry esiste la rilascia chiamando rtfree, altrimenti imposta i flags set-tando RTF_GATEWAY e RTF_DYNAMIC, crea la struttura rt_addrinfo e chiama rtrequest1 per crare la nuova entry. Inserisce in stat il riferimento a rtstat.rts_dynamic
MODIFICA
361-373 Setta il flag RTF_MODIFIED e chiama rt_setgate per modificare il gateway. Inserisce in stat il riferimento a rtstat.rts_newgateway
376-382 Nel caso in cui la entry esiste, se non ci sono errori e il chiamante vuole tale entry in dietro ne assegna l’indirizzo e rtp, altrimenti la rilascia chiamando rtfree 384-387 Aggiorna le statistiche: in caso di errore incrementa rtstat.rts_badredirect, altrimenti incrementa stat (vedi CREA e MODIFICA per le statisctiche riferite da stat)
388-393 Invia un messaggio RTM_REDIRECT ai processi in ascolto
1.8
La funzione rt_setgate
Alloca un’area di memoria della dimensione giusta per contenere gli indirizzi del destinatario e del gateway (la fa puntare da rt_key e rt_gateway) e vi copia solo
l’in-dirizzo del gateway, lasciando intatto il contenuto della sockaddr puntata da rt_key (eventualmente se ha dovuto allocare nuova memoria, copia il contenuto della vecchia sockaddr puntata da rt_key nella nuova). Se il destinatario non è direttamente raggiun-gibile richiama la rtalloc1 per inizializzare il membro rt_gwroute con l’indirizzo della rtentry relativa al gateway. E’ importante notare che gli indirizzi del destinatario e del gateway vengano memorizzati in aree di memoria contigue. In tal modo è possibile deallocarle entrambe in un’unica chiamata alla syscall free.
net/route.c int
rt_setgate(rt0, dst, gate) struct rtentry *rt0;
struct sockaddr *dst, *gate;
net/route.c
Figura 1.12: Dichiarazione di rt_setgate.
914 La macro ROUNDUP arrotonda il valore a al multiplo di sizeof(long) superiore 931-943 Se la entry passata (rt0) rappresenta una route indiretta verso un host ma
non contiene informazioni di tipo link layer e l’indirizzo di destinazione dst coincide con quello del gateway gate, allora se esiste già una chiave, cancella rt0 dall’albero e ritorna l’errore EADDRNOTAVAIL (address not available) 951-963 Se non è stato ancora allocato spazio per contenere l’indirizzo del gateway o
ne è stato allocato poco, lascia un puntatore alla vecchia chiave di rt=rt0, alloca lo spazio necessario a contenere chiave e gateway e ne assegna l’indirizzo a rt_key (membro rn_key del nodo). Altrimenti lo spazio necessario c’è già e ne copia l’indirizzo nel puntatore new
968-977 Copia la struct sockaddr di gateway nella giusta posizione nell’area punta-ta da new e dealloca l’eventuale area che non serve più. In quest’ultimo ca-so ricopia anche l’indirizzo del destinatario dalla vecchia area di memoria alla nuova
983-986 Se l’entry contiene un rt_gwroute non NULL, sicuramente quella route non è più consistente con il valore di gateway appena inserito nella entry e quindi la rilascia chiamando RTFREE
997-1004 Se la route è indiretta, ricerca nell’albero la entry relativa al gateway chia-mando rtalloc1. Se la entry trovata corrisponde alla entry rt, la rilascia chiaman-do RTFREE, setta a NULL il membro rt_gwroute e ritorna l’errore EDQUOT 1011-1017 Se la route è verso una network e c’è la netmask chiama la
rnh_walktree_from, per sistemare le foglie che sono in relazione alla entry cam-biata. Questa volta la funzione passata alla rnh_walktree_from è rt_fixchange che sistema le cose dopo un inserimento o un cambiamento. “In questo ca-so c’è un problema in più rispetto a rt_fixdelete (vedi paragrafo rtrequest1 nel paragrafo 1.6) perchè deve essere considerata anche la possibilità di un inseri-mento nel mezzo, cioè tra padre e figlio. Per questa ragione un semplice test sul padre non è sufficiente; ciascuna rtentry deve essere confrontata con la coppia netmask, chiave della nuova entrata inserita”8.
1.9
La funzione rtinit
rtinit crea una entrata nelle routing table per una interfaccia. Costruisce una struttura rtentry usando i parametri ifa e flags passati dal chiamante. Il parametro cmd può contenere il valore RTM_ADD (richiesta di aggiungere una nuova entrata) o il valore RTM_DELETE (richiesta di cancellare l’entrata).
net/route.c int
rtinit(ifa, cmd, flags)
register struct ifaddr *ifa; int cmd, flags;
net/route.c
Figura 1.13: Dichiarazione di rtinit.
1062-1068 Se la route è verso un host inserisce in dst l’indirizzo dell’host (altro end del collegamento point-to-point) e setta la netmask a 0. Altrimenti, inserisce in dst e netmask, indirizzo e netmask della network
1074 Se il comando passato alla funzione non è DELETE salta a 1116
1080-1087 Se la route è verso una network, alloca un mbuf di tipo socket name, ci copia l’indirizzo della network AND-ato con la netmask e lo fa puntare da dst.
Questa operazione viene eseguita dalla rt_maskedcopy che prende un indirizzo e una netmask e ritorna il risultato dell’AND logico tra le due
1092-1100 Se almeno una delle seguenti condizioni è valida, se è stato allocato un mbuf lo dealloca e in ogni caso ritorna un errore (EHOSTUNREACH se dst è un host, ENETUNREACH se è network):
• non esiste una tabella di routing per quella famiglia di protocolli;
• non esiste il nodo relativo a dst con maschera netmask nell’albero della
tabella di routing;
• il nodo cercato è un nodo ROOT ;
• il membro rt_ifa della entry trovata non coincide con ifa (puntatore passato
alla funzione)
• la chiave della entry trovata è diversa da dst
1116-1122 La precondizione di ciò che verrà eseguito è che dst punta all’indirizzo del destinatario (host/network) su cui la funzione dovrà agire. Dopo aver azzerato la struttura rt_addrinfo info, ne riempie i campi rti_ifa, rti_flags, rti_info[RTAX_DST], rti_info[RTAX_GATEWAY], rti_info[RTAX_NETMASK] e chiama la funzione rtrequest1 per eseguire il comando cmd (ADD / DELETE) 1123-1127 Se rtrequest1 ha successo e in nrt c’è l’indirizzo della entry (aggiunta o
estratta), notifica l’avvenuta modifica ai processi in ascolto
1128-1137 Se cmd specifica il comando DELETE rilascia la entry se il reference count è minore o uguale a 0, chiamando rtfree
1137-1143 Altrimenti se cmd specifica il comando ADD, decrementa il reference count della entry aggiunta (questo perchè il riferimento a tale entry contenuto in nrt verrà cancellato uscendo dalla funzione)
1145-1147 Se nel corso della funzione è stato allocato un mbuf, lo dealloca e esce dalla funzione (la funzione ha successo se ritorna 0)
Implementazione della TCP Host
Cache
2.1
Introduzione
“La tcp host cache sposta le metriche specifiche del protocollo TCP dalla routing table in una struttura dedicata, indicizzata dall’indirizzo IP dell’host remoto”1. Es-sa mantiene tutte le informazioni che prima erano contenute nel campo rt_rmx che, nella nuova implementazione, diventa molto più snello. In particolare rt_rmx diven-ta una struttura di tipo rt_metrics_lite in cui rimangono soldiven-tanto pochi membri della vecchia struttura rt_metrics. Questi valori sono utilizzati da protocolli affidabili per determinare il comportamento di ritrasmissione e sono inclusi nella struttura di routing. La dichiarazione di rt_metrics_lite è contenuta nel file header net/route.h ed è visu-alizzata in figura 2.1.
net/route.h struct rt_metrics_lite {
u_long rmx_mtu; /* MTU for this path */
u_long rmx_expire; /* lifetime for route, e.g. redirect */ u_long rmx_pksent; /* packets sent using this route */ };
net/route.h
Figura 2.1: Struttura rt_metrics_lite.
“Con questa nuova tcp host cache tutte le informazioni relative alle metriche speci-fiche del protocollo TCP che prima erano nella routing table sono state spostate. La
1trad. netinet/tcp_hostcache.c
struttura INPCB non mantiene più un puntatore all’entrata di routing e anche il mec-canismo di protocol cloning è stato rimosso. Con questi cambiamenti la routing table ritorna ad essere più snella e viene a contenere soltanto informazioni relative al packet forwarding”.2
2.2
La struttura interna della TCP Host Cache
Come si puo’ vedere in figura 2.2, la tcp host cache è costituita da bucket rows che dividono le entrate della cache in insiemi distinti su cui operare in concorrenza. Nella sua implementazione originale “la tcp host cache è progettata per accessi concorrenti in ambienti SMP. Tutte le bucket rows hanno un loro proprio semaforo e quindi possono essere condotte,nello stesso tempo, ricerche e modifiche multiple purchè in bucket rows differenti.”3 Nel porting questa caratteristica non è stata mantenuta perchè nella RELENG 4.9 non esiste il meccanismo dei semafori usato da Andre.
2.2.1
Bucket Row
Ogni bucket row è implementata come una lista a doppio senso di elementi di tipo hc_metrics. Tale struttura, che rappresenta una singola entrata della tcp host cache, è dichiarata in netinet/tcp_hostcache.c, come esposto in figura 2.3.
I primi quattro membri sono utilizzati soltanto dalle funzioni di accesso per scorrere ed eseguire lookup sulla lista. In particolare:
rmx_q - specifica l’entrata nella lista e contiene i puntatori necessari a scorrerla rmx_head - punta alla testa della lista
ip4 e ip6 - rappresentano l’indirizzo a cui è associata la entry; vengono usati in maniera esclusiva poichè non è possibile associare a due indirizzi diversi la stessa entrata I parametri che seguono rappresentano le vere e proprie informazioni e statistiche necessarie a velocizzare la riconnessione ad un host precedentemente connesso: rmx_mtu - MTU per il percorso verso l’host specificato
2trad. netinet/tcp_hostcache.c 3trad. netinet/tcp_hostcache.c
netinet/tcp_hostcache.c struct hc_metrics {
/* housekeeping */
TAILQ_ENTRY(hc_metrics) rmx_q;
struct hc_head *rmx_head; /* head of bucket tail queue */ struct in_addr ip4; /* IP address */
struct in6_addr ip6; /* IP6 address */ /* endpoint specific values for tcp */
u_long rmx_mtu; /* MTU for this path */
u_long rmx_ssthresh; /* outbound gateway buffer limit */ u_long rmx_rtt; /* estimated round trip time */ u_long rmx_rttvar; /* estimated rtt variance */ u_long rmx_bandwidth; /* estimated bandwidth */ u_long rmx_cwnd; /* congestion window */
u_long rmx_sendpipe; /* outbound delay-bandwidth product */ u_long rmx_recvpipe; /* inbound delay-bandwidth product */ struct rmxp_tao rmx_tao; /* TAO cache for T/TCP */
/* tcp hostcache internal data */
int rmx_expire; /* lifetime for object */ u_long rmx_hits; /* number of hits */ u_long rmx_updates; /* number of updates */ };
netinet/tcp_hostcache.c
Figura 2.3: Struttura hc_metrics.
rmx_ssthresh - outbound gateway buffer limit rmx_rtt - round trip time stimato
rmx_rttvar - stima della variazione del RTT
rmx_bandwidth - stima della larghezza di banda necessaria rmx_cwnd - dimensione della congestion window
rmx_sendpipe - outbound delay-bandwidth product rmx_recvpipe - inbound delay-bandwidth product rmxp_tao rmx_tao - TAO cache per T/TCP
Anche i tre parametri finali vengono utilizzati soltanto dalle funzioni di accesso alla tcp host cache:
rmx_expire - tempo di vita dell’entrata
rmx_hits - numero di volte che l’entrata è stata ottenuta; viene incrementata dalle funzioni tcp_hc_get, tcp_hc_getmtu, tcp_hc_gettao
rmx_updates - numero di volte che l’entrata è stata aggiornata
La testa di una bucket row non coincide con la testa della lista ed ha una struttura totalmente differente da hc_metrics, come si vede in figura 2.4.
netinet/tcp_hostcache.c TAILQ_HEAD(hc_qhead, hc_metrics);
struct hc_head {
struct hc_qhead hch_bucket; u_int hch_length;
struct mtx hch_mtx; };
netinet/tcp_hostcache.c
Figura 2.4: Struttura hc_head.
I membri di una struttura hc_head sono: hch_bucket - rappresenta la testa della lista hch_length - lunghezza della bucket row
hch_mtx - semaforo per l’accesso in mutua esclusione alla bucket row
2.2.2
TCP Host Cache
La tcp host cache è rappresentata dalla struttura tcp_hostcache definita come segue: netinet/tcp_hostcache.c struct tcp_hostcache {
struct hc_head *hashbase; /* uma_zone_t zone; */ u_int hashsize; u_int hashmask; u_int bucket_limit; u_int cache_count; u_int cache_limit; int expire; int purgeall; };
static struct tcp_hostcache tcp_hostcache;
netinet/tcp_hostcache.c
Figura 2.5: Struttura tcp_hostcache.
hashbase - è un array di hc_head e dunque ad ogni suo elemento corrisponde una bucket row; viene allocato dinamicamente in fase di inizializzazione
zone - corrisponde all’area di memoria in cui verranno memorizzate le entrate della tcp host cache; è utilizzato dal meccanismo UMA (Uniform Memory Allocator).
Anche questa caratteristica non è stata mantenuta nel porting e quindi il membro non compare più. Al posto dell’UMA le allocazioni e le deallocazioni necessarie sono state eseguite con semplici malloc e free del kernel.
hashsize - definisce la dimensione dell’array puntato dal membro hashbase
hashmask - rappresenta un limite superiore agli indici hash generati dalle funzioni di hash proprie di IPv4 e IPv6 (deve essere una potenza di due)
bucket_limit - numero massimo di elementi in una bucket row
cache_count - numero totale di elementi contenuti nella tcp host cache cache_limit - capcità della host cache
expire - tempo di vita a disposizione per ciascuna entry
purgeall - se settato indica alla tcp_hc_purge di eliminare tutte le entrate esistenti al momento della sua invocazione
2.3
Le funzioni di gestione della TCP Host Cache
“Se la richiesta di una nuova inserzione non può essere soddisfatta, semplicemente ritorna una struttura vuota. Nessuno e niente punterà mai direttamente ad una entra-ta della TCP Host Cache. Tutentra-ta la comunicazione avviene in modo object oriented e soltanto le funzioni della TCP Host Cache manipoleranno le entrate. Altrimenti non saremmo in grado di ottenere un buon comportamento in situazioni di accesso concor-rente. Poichè la TCP Host Cache non fa altro che mantenere informazioni, non ci sono conseguenze fatali se non può essere soddisfatta una particolare richiesta oppure se viene scartata/sovrascritta un’entrata esistente per aver raggiunto il limite di memoria relativa ad una bucket row.”4
Le funzioni introdotte con la TCP Host Cache sono di due tipi: di accesso e in-terne. Le prime sono richiamate dal codice del kernel per eseguire operazioni di ricer-ca, estrazione di informazioni ed aggiornamento dati. Da notare che non esiste una funzione specifica per l’inserimento di nuove entrate nella TCP Host Cache. Questo
perchè una nuova entrata viene creata in seguito all’aggiornamento di dati relativi ad una connessione specifica per la quale ancora non esiste l’entrata corrispondente. Le funzioni interne, invece, sono quelle su cui si appoggiano le funzioni di accesso e non dovrebbero essere richiamate da nessun altra parte nel kernel.
2.3.1
La funzione tcp_hc_init
netinet/tcp_hostcache.c void
tcp_hc_init(void)
netinet/tcp_hostcache.c
Figura 2.6: Dichiarazione di tcp_hc_init.
Inizializza la tcp_hostcache e il timer con cui mandare in esecuzione la funzione di pulizia della cache tcp_hc_purge. In particolare vengono:
1. utilizzate le costanti di figura 2.7 per inizializzare i membri hashsize, bucket_limit, expire:
2. allocato l’array puntato dal membro hashbase;
3. inizializzata la testa di tutte le bucket row (in particolare, nella versione origi-nale, il mutex);
4. allocata l’area di memoria relativa al membro zone che servirà a contenere gli elementi delle varie bucket row (nel porting questo passo non esiste)
5. inizializzato il timer per l’invocazione della funzione tcp_hc_purge che serve a pulire la cache da entrate scadute
netinet/tcp_hostcache.c #define TCP_HOSTCACHE_HASHSIZE 512
#define TCP_HOSTCACHE_BUCKETLIMIT 30
#define TCP_HOSTCACHE_EXPIRE 60*60 /* one hour */
netinet/tcp_hostcache.c
Figura 2.7: Costanti di inizializzazione dei membri della struttura tcp_hostcache.
2.3.2
La funzione tcp_hc_lookup
“Funzione interna: cerca e ritorna una entrata nella host cache; in caso di insuccesso ritorna NULL. Nella versione originale, una volta ritornata una entry, il chiamante
