PROJET AUTOBLOG


®om's blog

Site original : ®om's blog

⇐ retour index

Mise à jour

Mise à jour de la base de données, veuillez patienter...

Gnirehtet réécrit en Rust

jeudi 21 septembre 2017 à 17:00

Il y a quelques mois, j’ai présenté Gnirehtet, un outil de reverse tethering pour Android que j’ai écrit en Java.

Depuis, je l’ai réécrit en Rust.

Et il est également open source ! Téléchargez-le, branchez un téléphone ou une tablette Android, et exécutez :

./gnirehtet run

(adb doit être installé)

Pourquoi Rust?

À Genymobile, nous voulions que Gnirehtet ne nécessite pas d’environnement d’exécution Java (JRE), donc le besoin principal était de compiler l’application vers un binaire exécutable natif.

Par conséquent, j’ai d’abord pensé la réécrire en C ou C++. Mais à ce moment-là (début mai), apprendre Rust m’intéressait, après avoir vaguement entendu parler de ses fonctionnalités:

Cependant, je n’avais jamais écrit une ligne de Rust ni entendu parler de son système de possession, d’emprunt ou de durées de vie.

Mais je suis convaincu que le meilleur moyen d’apprendre un langage de programmation est de travailler à plein temps sur un projet dans ce langage.

J’étais motivé, donc après avoir vérifié que ça pouvait convenir (en gros, j’ai écrit un exemple utilisant la bibliothèque d’I/O asynchrone mio, et je l’ai exécuté à la fois sur Linux et Windows), j’ai décidé de réécrire Gnirehtet en Rust.

Apprendre Rust

Pendant la réécriture, j’ai dévoré successivement le Rust book, Rust by example et le Rustonomicon. J’ai beaucoup appris, et j’aime énormément ce langage. Beaucoup de ses fonctionnalités me manquent maintenant quand je travaille sur un projet C++ :

À propos de l’apprentissage, Paul Graham a écrit:

Reading and experience train your model of the world. And even if you forget the experience or what you read, its effect on your model of the world persists. Your mind is like a compiled program you’ve lost the source of. It works, but you don’t know why.

Pour les non-anglophones, ma propre traduction :

La lecture et l’expérience entraînent votre modèle du monde. Et même si vous oubliez l’expérience ou ce que vous avez lu, son effet sur votre modèle du monde persiste. Votre esprit est comme un programme compilé dont vous auriez perdu le code source. Ça fonctionne, mais vous ne savez pas pourquoi.

Certains des concepts de Rust (comme les durées de vie ou la sémantique de mouvement par défaut) m’ont fourni un jeu de données significativement différent, qui a sans aucun doute affecté mon modèle du monde (de la programmation).

Je ne vais pas présenter toutes ces fonctionnaliés (cliquez sur les liens de la documentation si ça vous intéresse). À la place, je vais essayer d’expliquer où et pourquoi Rust a resisté au design que je voulais implémenter, et comment repenser les problèmes dans le périmètre des contraintes de Rust.

La partie suivant nécessite une certaine connaissance de Rust. Vous pourriez vouloir la passer pour aller directement aux stats.

Difficultés

Je trouvais la conception de l’application Java plutôt réussie, donc je voulais reproduire l’architecture globale dans la version Rust (avec d’éventuelles adaptations pour la rustifier).

Mais j’ai lutté sur les détails, en particulier pour satisfaire le borrow checker. Les règles sont simples:

First, any borrow must last for a scope no greater than that of the owner. Second, you may have one or the other of these two kinds of borrows, but not both at the same time:

  • one or more references (&T) to a resource,
  • exactly one mutable reference (&mut T).

En français :

Premièrement, aucun emprunt ne doit avoir une portée plus grande que celle de son propriétaire. Deuxièmement, vous pouvez avoir l’un ou l’autre de ces types d’emprunts, mais pas les deux à la fois:

  • une ou plusieurs références (&T) vers une ressource,
  • exactement une référence mutable (&mut T).

Cependant, il m’a fallu un peu de temps pour réaliser comment elles entrent en conflit avec certains principes ou modèles de conception.

Voici donc mes retours. J’ai sélectionné 4 sujets qui sont suffisamment généraux pour être indépendants de ce projet particulier :

Encapsulation

Les règles d’emprunt contraignent l’encapsulation. C’est la première conséquence que j’ai réalisée.

Voici un exemple canonique :

pub struct Data {
    header: [u8; 4],
    payload: [u8; 20],
}

impl Data {
    pub fn new() -> Self {
        Self {
            header: [0; 4],
            payload: [0; 20],
        }
    }

    pub fn header(&mut self) -> &mut [u8] {
        &mut self.header
    }

    pub fn payload(&mut self) -> &mut [u8] {
        &mut self.payload
    }
}

fn main() {
    let mut data = Data::new();
    let header = data.header();
    let payload = data.payload();
}

Nous créons juste une nouvelle instance de Data, puis associons à des variables locales des références mutables vers les tableaux header et payload, en passant par des accesseurs.

Cependant, cela ne compile pas :

$ rustc sample.rs
error[E0499]: cannot borrow `data` as mutable more than once at a time
  --> sample.rs:21:19
   |
25 |     let header = data.header();
   |                  ---- first mutable borrow occurs here
26 |     let payload = data.payload();
   |                   ^^^^ second mutable borrow occurs here
27 | }
   | - first borrow ends here

Le compilateur ne peut pas faire l’hypothèse que header() et payload() retournent des références vers des données disjointes dans la structure Data. Par conséquent, chacun emprunte la structure data entièrement. Vu que les règles d’emprunt interdisent d’obtenir deux références mutables vers la même ressource, il rejette le second appel.

Parfois, nous faisons face à des limitations temporaires parce que le compilateur n’est pas (encore) assez malin. Ce n’est pas le cas ici : l’implémentation de header() pourrait très bien retourner une référence vers payload, ou écrire dans le tableau payload, enfreignant ainsi les règles d’emprunt. Et la validité d’un appel d’une méthode ne peut pas dépendre de l’implementation de la méthode.

Pour corriger le problème, le compilateur doit être capable de savoir que les variables locales header et payload référencent des données disjointes, par exemple en accédant aux champs directement :

    let header = &mut data.header;
    let payload = &mut data.payload;

ou en exposant une méthode fournissant les deux références simultanément :

struct Data {
    fn header_and_payload(&mut self) -> (&mut [u8], &mut [u8]) {
        (&mut self.header, &mut self.payload)
    }
}

fn main() {
    let mut data = Data::new();
    let (header, payload) = data.header_and_payload();
}

De même, dans l’implémentation d’une structure, les règles d’emprunt empêchent de factoriser du code dans une méthode privée facilement. Prenons cet exemple (artificiel) :

pub struct Data {
    buf: [u8; 20],
    prefix_length: usize,
    sum: u32,
    port: u16,
}

impl Data {
    pub fn update_sum(&mut self) {
        let content = &self.buf[self.prefix_length..];
        self.sum = content.iter().cloned().map(u32::from).sum();
    }

    pub fn update_port(&mut self) {
        let content = &self.buf[self.prefix_length..];
        self.port = (content[2] as u16) << 8 | content[3] as u16;
    }
}

Ici, le champ buf est un tableau stockant un préfixe et un contenu de manière contiguë.

Nous voulons factoriser la manière dont nous récupérons la slice content, pour que les méthodes update_*() n’aient pas à se préoccuper des détails. Essayons :

 impl Data {
     pub fn update_sum(&mut self) {
-        let content = &self.buf[self.prefix_length..];
+        let content = self.content();
         self.sum = content.iter().cloned().map(u32::from).sum();
     }

     pub fn update_port(&mut self) {
-        let content = &self.buf[self.prefix_length..];
+        let content = self.content();
         self.port = (content[2] as u16) << 8 | content[3] as u16;
     }
+
+    fn content(&mut self) -> &[u8] {
+        &self.buf[self.prefix_length..]
+    }
 }

Malheureusement, cela ne compile pas :

error[E0506]: cannot assign to `self.sum` because it is borrowed
  --> facto2.rs:11:9
   |
10 |         let content = self.content();
   |                       ---- borrow of `self.sum` occurs here
11 |         self.sum = content.iter().cloned().map(u32::from).sum();
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `self.sum` occurs here

error[E0506]: cannot assign to `self.port` because it is borrowed
  --> facto2.rs:16:9
   |
15 |         let content = self.content();
   |                       ---- borrow of `self.port` occurs here
16 |         self.port = (content[2] as u16) << 8 & content[3] as u16;
   |

Comme dans l’exemple précédent, récupérer une référence à travers une méthode emprunte la structure complète (ici, self).

Pour contourner le problème, nous pouvons expliquer au compilateur que les champs sont disjoints :

impl Data {
    pub fn update_sum(&mut self) {
        let content = Self::content(&self.buf, self.prefix_length);
        self.sum = content.iter().cloned().map(u32::from).sum();
    }

    pub fn update_port(&mut self) {
        let content = Self::content(&self.buf, self.prefix_length);
        self.port = (content[2] as u16) << 8 | content[3] as u16;
    }

    fn content(buf: &[u8], prefix_length: usize) -> &[u8] {
        &buf[prefix_length..]
    }
}

Ça compile, mais cela va totalement à l’encontre de la factorisation : l’appelant doit fournir les champs nécessaires.

Comme alternative, nous pouvons utiliser une macro pour inliner le code :

macro_rules! content {
    ($self:ident) => {
        &$self.buf[$self.prefix_length..]
    }
}

impl Data {
    pub fn update_sum(&mut self) {
        let content = content!(self);
        self.sum = content.iter().cloned().map(u32::from).sum();
    }

    pub fn update_port(&mut self) {
        let content = content!(self);
        self.port = (content[2] as u16) << 8 | content[3] as u16;
    }
}

Mais c’est loin d’être idéal.

Je pense que nous devons juste l’accepter : l’encapsulation entre parfois en conflit avec les règles d’emprunt. Après tout, ce n’est pas si surprenant : imposer les règles d’emprunt nécessite de suivre chaque accès concret aux ressources, alors que l’encapsulation vise à les abstraire.

Observateur

Le design pattern observateur est utile pour enregistrer des événements sur un objet.

Dans certains cas, ce pattern pose des difficultés d’implémentation en Rust.

Pour faire simple, considérons que les événements sont des valeurs u32. Voici une implémentation possible :

pub trait EventListener {
    fn on_event(&self, event: u32);
}

pub struct Notifier {
    listeners: Vec<Box<EventListener>>,
}

impl Notifier {
    pub fn new() -> Self {
        Self { listeners: Vec::new() }
    }

    pub fn register<T: EventListener + 'static>(&mut self, listener: T) {
        self.listeners.push(Box::new(listener));
    }

    pub fn notify(&self, event: u32) {
        for listener in &self.listeners {
            listener.on_event(event);
        }
    }
}

Par commodité, implémentons notre trait EventListener pour les closures :

impl<F: Fn(u32)> EventListener for F {
    fn on_event(&self, event: u32) {
        self(event);
    }
}

Ainsi, son utilisation est simple :

    let mut notifier = Notifier::new();
    notifier.register(|event| println!("received [{}]", event));
    println!("notifying...");
    notifier.notify(42);

Cela affiche :

notifying...
received [42]

Jusqu’ici, tout va bien.

Cependant, les choses se compliquent si nous voulons modifier un état sur la réception d’un événement. Par exemple, implémentons une structure pour stocker tous les événements reçus :

pub struct Storage {
    events: Vec<u32>,
}

impl Storage {
    pub fn new() -> Self {
        Self { events: Vec::new() }
    }

    pub fn store(&mut self, value: u32) {
        self.events.push(value);
    }

    pub fn events(&self) -> &Vec<u32> {
        &self.events
    }
}

Pour pouvoir remplir ce Storage sur chaque événement reçu, nous devons d’une manière ou d’une autre le passer avec l’event listener, qui sera stocké dans le Notifier. Par conséquent, nous avons besoin qu’une instance de Storage soit partagée entre le code appelant et le Notifier.

Avoir deux références mutables vers le même objet enfreint évidemment les règles d’emprunt, donc nous avons besoin d’un pointeur à compteur de références.

Cependant, un tel pointeur est en lecture seul, donc nous avons également besoin d’un RefCell pour la mutabilité intérieure.

Ainsi, nous allons utiliser une instance de Rc<RefCell<Storage>>. Cela peut sembler trop verbeux, mais utiliser Rc<RefCell<T>> (ou Arc<Mutex<T>> pour la thread-safety) est très courant en Rust. Et il y a pire.

Voici ce que donne le code client :

    use std::cell::RefCell;
    use std::rc::Rc;

    let mut notifier = Notifier::new();

    // first Rc to the Storage
    let rc = Rc::new(RefCell::new(Storage::new()));

    // second Rc to the Storage
    let rc2 = rc.clone();

    // register the listener saving all the received events to the Storage
    notifier.register(move |event| rc2.borrow_mut().store(event));

    notifier.notify(3);
    notifier.notify(141);
    notifier.notify(59);
    assert_eq!(&vec![3, 141, 59], rc.borrow().events());

De cette manière, le Storage est correctement modifié à partir de l’event listener.

Tout n’est pas résolu pour autant. Dans cet exemple, c’était facile, nous avions accès à l’instance Rc<RefCell<Storage>>. Comment faire si nous avons seulement accès au Storage, par exemple si nous voulons que le Storage s’enregistre lui-même à partir de l’une de ses méthodes, sans que l’appelant n’ait à fournir l’instance Rc<RefCell<Storage>> ?

impl Storage {
    pub fn register_to(&self, notifier: &mut Notifier) {
        notifier.register(move |event| {
            /* how to retrieve a &mut Storage from here? */
        });
    }
}

Nous devons trouver un moyen de récupérer le Rc<RefCell<Storage>> à partir du Storage.

Pour cela, l’idée consiste à rendre Storage conscient de son pointeur à compteur de références. Bien sûr, cela n’a du sens que si Storage est construit dans un Rc<RefCell<Storage>>.

C’est exactement ce que enable_shared_from_this fournit en C++, donc nous pouvons nous inspirer de son fonctionnement : juste stocker un Weak<RefCell<…>>, downgradé à partir du Rc<RefCell<…>>, dans la structure elle-même. De cette manière, nous pouvons l’utiliser pour récupérer une référence &mut Storage à partir de l’event listener :

use std::rc::{Rc, Weak};
use std::cell::RefCell;

pub struct Storage {
    self_weak: Weak<RefCell<Storage>>,
    events: Vec<u32>,
}

impl Storage {
    pub fn new() -> Rc<RefCell<Self>> {
        let rc = Rc::new(RefCell::new(Self {
            self_weak: Weak::new(), // initialize empty
            events: Vec::new(),
        }));
        // set self_weak once we get the Rc instance
        rc.borrow_mut().self_weak = Rc::downgrade(&rc);
        rc
    }

    pub fn register_to(&self, notifier: &mut Notifier) {
        let rc = self.self_weak.upgrade().unwrap();
        notifier.register(move |event| rc.borrow_mut().store(event))
    }
}

Voici comment l’utiliser :

    let mut notifier = Notifier::new();
    let rc = Storage::new();
    rc.borrow().register_to(&mut notifier);
    notifier.notify(3);
    notifier.notify(141);
    notifier.notify(59);
    assert_eq!(&vec![3, 141, 59], rc.borrow().events());

Il est donc possible d’implémenter le design pattern observateur en Rust, mais c’est un peu plus difficile qu’en Java ;-)

Lorsque c’est possible, il est probablement préférable de l’éviter.

Partage de données mutables

Mutable references cannot be aliased.

En français :

Les références mutables ne peuvent pas être aliasées.

Comment partager des données mutables, alors ?

Nous avons vu que nous pouvions utiliser Rc<RefCell<…>> (ou Arc<Mutex<…>>), qui impose les règles d’emprunt à l’exécution. Cependant, ce n’est pas toujours désirable :

Au lieu de cela, nous pourrions utiliser des pointeurs bruts manuellement dans du code non-sûr, mais alors ce serait non-sûr.

Et il y a une autre solution, qui consiste à exposer des vues temporaires d’emprunt d’un objet. Laissez-moi expliquer.

Dans Gnirehtet, un paquet contient une référence vers les données brutes (stockées dans un buffer quelque part) ainsi que les valeur des champs des en-têtes IP et TCP/UDP (parsées à partir du tableau d’octets brut). Nous aurions pu utiliser une structure à plat pour tout stocker :

pub struct Packet<'a> {
    raw: &'a mut [u8],
    ipv4_source: u32,
    ipv4_destination: u32,
    ipv4_protocol: u8,
    // + other ipv4 fields
    transport_source: u16,
    transport_destination: u16,
    // + other transport fields
}

Le Packet aurait fourni des setters pour tous les champs d’en-têtes (modifiant à la fois les champs du paquet et le tableau d’octets). Par exemple :

impl<'a> Packet<'a> {
    pub fn set_transport_source(&mut self, transport_source: u16) {
        self.transport_source = transport_source;
        let transport = &mut self.raw[20..];
        BigEndian::write_u16(&mut transport[0..2], port);
    }
}

Mais cette conception ne serait pas terrible (surtout que les champs d’en-têtes TCP et UDP sont différents).

À la place, nous voudrions extraire les en-têtes d’IP et de transport vers des structures séparées, gérant leur propre partie du tableau d’octets :

// violates the borrowing rules

pub struct Packet<'a> {
    raw: &'a mut [u8], // the whole packet (including headers)
    ipv4_header: Ipv4Header<'a>,
    transport_header: TransportHeader<'a>,
}

pub struct Ipv4Header<'a> {
    raw: &'a mut [u8], // slice related to ipv4 headers
    source: u32,
    destination: u32,
    protocol: u8,
    // + other ipv4 fields
}

pub struct TransportHeader<'a> {
    raw: &'a mut [u8], // slice related to transport headers
    source: u16,
    destination: u16,
    // + other transport fields
}

Vous avez immédiatement repéré le problème : il y a plusieurs références vers la même ressource, le tableau d’octets raw, en même temps.

Remarquez que diviser le tableau n’est pas une possibilité ici, vu que les slices de raw se chevauchent : nous avons besoin d’écrire le paquet complet en une seule fois vers la couche réseau, donc le tableau raw dans Packet doit inclure les headers.

Nous avons besoin d’une solution compatible avec les règles d’emprunt.

Voici celle à laquelle je suis parvenu :

Et voici une simplification de l’implémentation réelle :

pub struct Packet<'a> {
    raw: &'a mut [u8],
    ipv4_header: Ipv4HeaderData,
    transport_header: TransportHeaderData,
}

pub struct Ipv4HeaderData {
    source: u32,
    destination: u32,
    protocol: u8,
    // + other ipv4 fields
}

pub struct TransportHeaderData {
    source: u16,
    destination: u16,
    // + other transport fields
}

pub struct Ipv4Header<'a> {
    raw: &'a mut [u8],
    data: &'a mut Ipv4HeaderData,
}

pub struct TransportHeader<'a> {
    raw: &'a mut [u8],
    data: &'a mut TransportHeaderData,
}

impl<'a> Packet<'a> {
    pub fn ipv4_header(&mut self) -> Ipv4Header {
        Ipv4Header {
            raw: &mut self.raw[..20],
            data: &mut self.ipv4_header,
        }
    }

    pub fn transport_header(&mut self) -> TransportHeader {
        TransportHeader {
            raw: &mut self.raw[20..40],
            data: &mut self.transport_header,
        }
    }
}

Les setters sont implémentés sur les vues, où ils détiennent une référence mutable vers le tableau brut :

impl<'a> TransportHeader<'a> {
    pub fn set_source(&mut self, source: u16) {
        self.data.source = source;
        BigEndian::write_u16(&mut raw[0..2], source);
    }

    pub fn set_destination(&mut self, destination: u16) {
        self.data.destination = destination;
        BigEndian::write_u16(&mut raw[2..4], destination);
    }
}

De cette manière, les règles d’emprunt sont respectées, et l’API est élégante :

    let mut packet = ;
    // "transport_header" borrows "packet" during its scope
    let mut transport_header = packet.transport_header();
    transport_header.set_source(1234);
    transport_header.set_destination(1234);

Limitations du compilateur

Rust est un langage jeune, et le compilateur a quelques problèmes ennuyeux.

Le pire, d’après moi, est lié aux durées de vie non-lexicales, qui provoque des erreurs inattendues :

struct Container {
    vec: Vec<i32>,
}

impl Container {
    fn find(&mut self, v: i32) -> Option<&mut i32> {
        None // we don't care the implementation
    }

    fn get(&mut self, v: i32) -> &mut i32 {
        if let Some(x) = self.find(v) {
            return x;
        }
        self.vec.push(v);
        self.vec.last_mut().unwrap()
    }
}
error[E0499]: cannot borrow `self.vec` as mutable more than once at a time
  --> sample.rs:14:9
   |
11 |         if let Some(x) = self.find(v) {
   |                          ---- first mutable borrow occurs here
...
14 |         self.vec.push(v);
   |         ^^^^^^^^ second mutable borrow occurs here
15 |         self.vec.last_mut().unwrap()
16 |     }
   |     - first borrow ends here

Heureusement, cela devrait être corrigé prochainement.

La fonctionnalité d’Impl Trait, permettant aux fonctions de retourner des types abstraits non-boxés, devrait aussi améliorer l’expérience (il y a aussi une proposition étendue).

Le compilateur produit généralement des messages d’erreur très utiles. Mais quand ce n’est pas le cas, ils peuvent être très déroutants.

Sûreté et pièges

Le premier chapitre du Rustonomicon dit :

Safe Rust is For Reals Totally Safe.

[…]

Safe Rust is the true Rust programming language. If all you do is write Safe Rust, you will never have to worry about type-safety or memory-safety. You will never endure a null or dangling pointer, or any of that Undefined Behavior nonsense.

En français :

La partie Sûre de Rust est Réellement Totallement Sûre.

[…]

Le Rust Sûr est le vrai langage de programmation Rust. Si vous n’écrivez que du Rust Sûr, vous n’aurez jamais à vous inquiétez de la sûreté des types ou de la mémoire. Vous n’aurez jamais à supporter un pointeur null ou dangling, ou l’un de ces comportements indéfinis insensés.

C’est le but. Et c’est presque vrai.

Leakpocalypse

Dans le passé, il a été possible d’écrire du code Rust sûr accédant à de la mémoire libérée.

Cette “leakpocalypse” a conduit à la clarification des guaranties de sûreté : ne pas exécuter un destructeur est maintenant considéré sûr. En d’autres termes, la sûreté mémoire ne peut plus reposer sur RAII (en fait, elle n’a jamais pu, mais cela n’a été remarqué que tardivement).

En conséquence, std::mem::forget est maintenant sûr, et JoinGuard a été déprécié et supprimé de la bibliothèque standard (il a été déplacé vers un crate séparé).

Les autres outils s’appuyant sur RAII (comme Vec::drain()) doivent prendre des précautions particulières pour garantir que la mémoire ne sera pas corrompue.

Ouf, la sûreté mémoire est (maintenant) sauvée.

Infinité indéfinie

En C et C++, les boucles infinies sans effets de bords sont un cas d’undefined behavior. À cause de cela, il est possible d’écrire des programmes qui, de façon inattendue, réfutent le dernier théorème de Fermat.

En pratique, le compilateur Rust s’appuie sur LLVM, qui (actuellement) applique ses optimisations en faisant l’hypothèse que les boucles infinies sans effets de bords ont un comportement indéfini. En conséquence, de tels undefined behaviors se produisent également en Rust.

Voici un exemple minimal pour l’observer :

fn infinite() {
    loop {}
}

fn main() {
    infinite();
}

Quand on l’exécute sans optimisations, il se comporte comme “attendu” :

$ rustc ub.rs && ./ub
^C                    (infinite loop, interrupt it)

Mais activer les optimisations fait paniquer le programme :

$ rustc -O ub.rs && ./ub
thread 'main' panicked at 'assertion failed: c.borrow().is_none()', /checkout/src/libstd/sys_common/thread_info.rs:51
note: Run with `RUST_BACKTRACE=1` for a backtrace.

Nous pouvons aussi produire des résultats inattendus sans plantage :

fn infinite(mut value: u32) {
    // infinite loop unless value initially equals 0
    while value != 0 {
        if value != 1 {
            value -= 1;
        }
    }
}

fn main() {
    infinite(42);
    println!("end");
}
$ rustc ub.rs && ./ub
^C                    (infinite loop, interrupt it)

Mais avec optimisations :

$ rustc -O ub.rs && ./ub
end

C’est un cas particulier, qui sera probablement corrigé dans le futur. En pratique, les garanties de sûreté de Rust sont très fortes (au prix d’être contraignantes).

Erreur de segmentation

Cette section a été ajoutée après la publication.

Il y a d’autres sources d’undefined behaviors (voir les issues taggées I-unsound).

Par exemple, caster une valeur flottante ne pouvant pas être représentée dans le type cible est un undefined behavior, qui peut être propagé pour provoquer une erreur de segmentation :

#[inline(never)]
pub fn f(ary: &[u8; 5]) -> &[u8] {
    let idx = 1e100f64 as usize;
    &ary[idx..]
}

fn main() {
    println!("{}", f(&[1; 5])[0xdeadbeef]);
}
rustc -O ub.rs && ./ub
Erreur de segmentation

Stats

C’est tout pour mes retours sur le langage lui-même.

En supplément, comparons les versions Java et Rust du serveur relais.

Nombre de lignes

$ cloc relay-{java,rust}/src
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Rust                            29            687            655           4506
Java                            37            726            701           2931
-------------------------------------------------------------------------------

(tests included)

Le projet Rust est significativement plus gros, pour plusieurs raisons :

La version Java contient plus de fichiers car les tests unitaires sont séparés, alors qu’en Rust ils se trouvent dans le même fichier que les classes qu’ils testent.

Juste pour information, voici les résultats pour le client Android :

$ cloc app/src
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Java                            15            198            321            875
XML                              6              7              2             76
-------------------------------------------------------------------------------
SUM:                            21            205            323            951
-------------------------------------------------------------------------------

Taille des binaires

--------------------------------------------
Java     gnirehtet.jar                   61K
--------------------------------------------
Rust     gnirehtet                      3.0M
         after "strip -g gnirehtet"     747K
         after "strip gnirehtet"        588K
--------------------------------------------

Le binaire Java lui-même est bien plus petit. La comparaison n’est pas juste cependant, vu qu’il nécessite l’environnement d’exécution Java :

$ du -sh /usr/lib/jvm/java-1.8.0-openjdk-amd64/
156M	/usr/lib/jvm/java-1.8.0-openjdk-amd64/

Utilisation mémoire

Avec une seule connection TCP ouvert, voici la consommation mémoire pour le serveur relais en Java :

$ sudo pmap -x $RELAY_JAVA_PID
                  Kbytes     RSS   Dirty
total kB         4364052   86148   69316

(résultat filtré)

Et pour le serveur relais en Rust :

$ sudo pmap -x $RELAY_RUST_PID
                  Kbytes     RSS   Dirty
total kB           19272    2736     640

Regardez la valeur RSS, qui indique la mémoire réellement utilisée.

Comment on pouvait s’y attendre, la version Java consomme plus de mémoire (86Mo) que la version Rust (moins de 3Mo). De plus, sa valeur est instable à cause de l’allocation de petits objets et leur garbage collection, qui génère aussi davantage de dirty pages. La valeur pour Rust, quant à elle, est très stable : une fois la connection créée, il n’y a plus d’allocations mémoire du tout.

Utilisation CPU

Pour comparer l’utilisation CPU, voici mon scénario : un fichier de 500Mo est hébergé par Apache sur mon ordinateur, je démarre le serveur relais avec perf stat, puis je télécharge le fichier à partir de Firefox sur Android. Dès que le fichier est téléchargé, je stoppe le serveur relais (Ctrl+C).

Voici les résultats pour la version Java :

$ perf stat -B java -jar gnirehtet.jar relay
 Performance counter stats for 'java -jar gnirehtet.jar relay':

      11805,458302      task-clock:u (msec)       #    0,088 CPUs utilized
                 0      context-switches:u        #    0,000 K/sec
                 0      cpu-migrations:u          #    0,000 K/sec
            28 618      page-faults:u             #    0,002 M/sec
    17 908 360 446      cycles:u                  #    1,517 GHz
    13 944 172 792      stalled-cycles-frontend:u #   77,86% frontend cycles idle
    18 437 279 663      instructions:u            #    1,03  insn per cycle
                                                  #    0,76  stalled cycles per insn
     3 088 215 431      branches:u                #  261,592 M/sec
        70 647 760      branch-misses:u           #    2,29% of all branches

     133,975117164 seconds time elapsed

Et pour la version Rust :

$ perf stat -B ./gnirehtet relay
 Performance counter stats for 'target/release/gnirehtet relay':

       2707,479968      task-clock:u (msec)       #    0,020 CPUs utilized
                 0      context-switches:u        #    0,000 K/sec
                 0      cpu-migrations:u          #    0,000 K/sec
             1 001      page-faults:u             #    0,370 K/sec
     1 011 527 340      cycles:u                  #    0,374 GHz
     2 033 810 378      stalled-cycles-frontend:u #  201,06% frontend cycles idle
       981 103 003      instructions:u            #    0,97  insn per cycle
                                                  #    2,07  stalled cycles per insn
        98 929 222      branches:u                #   36,539 M/sec
         3 220 527      branch-misses:u           #    3,26% of all branches

     133,766035253 seconds time elapsed

Je ne suis pas un expert pour analyser les résultats, mais de ce que je comprends de la valeur task-clock:u, la version Rust consomme 4× moins de temps CPU.

Conclusion

Réécrire Gnirehtet en Rust a été une formidable expérience, où j’ai appris un super langage et de nouveaux concepts de programmation. Et maintenant, nous avons une application native avec de meilleures performances.

Bon reverse tethering !

Discussions sur reddit et Hacker News.

Gnirehtet rewritten in Rust

jeudi 21 septembre 2017 à 17:00

Several months ago, I introduced Gnirehtet, a reverse tethering tool for Android I wrote in Java.

Since then, I rewrote it in Rust.

And it’s also open source! Download it, plug an Android device, and execute:

./gnirehtet run

(adb must be installed)

Why Rust?

At Genymobile, we wanted Gnirehtet not to require the Java Runtime Environment, so the main requirement was to compile the application to a native executable binary.

Therefore, I first considered rewriting it in C or C++. But at that time (early May), I was interested in learning Rust, after vaguely hearing what it provided, namely:

However, I had never written a line of Rust code nor heard about Rust ownership, borrowing or lifetimes.

But I am convinced that the best way to learn a programming language is to work full-time on a real project in that language.

I was motivated, so after checking that it could fit our requirements (basically, I wrote a sample using the async I/O library mio, and executed it on both Linux and Windows), I decided to rewrite Gnirehtet in Rust.

Learning Rust

During the rewriting, I devoured successively the Rust book, Rust by example and the Rustonomicon. I learned a lot, and Rust is an awesome language. I now miss many of its features when I work on a C++ project, including:

About learning, Paul Graham wrote:

Reading and experience train your model of the world. And even if you forget the experience or what you read, its effect on your model of the world persists. Your mind is like a compiled program you’ve lost the source of. It works, but you don’t know why.

Some of Rust concepts (like lifetimes or move semantics by default) provided a significantly different new training set which definitely affected my model of the world (of programming).

I am not going to present all these features (just click on the links to the documentation if you are interested). Instead, I will try to explain where and why Rust resisted to the design I wanted to implement, and how to rethink the problems within Rust constraints.

The following part requires some basic knowledge of Rust. You may want to skip directly to the stats.

Difficulties

The design of the Java application was pretty effective, so I wanted to reproduce the global architecture in the Rust version (with adaptations to make it more Rust idiomatic if necessary).

But I struggled on the details, especially to make the borrow checker happy. The rules are simple:

First, any borrow must last for a scope no greater than that of the owner. Second, you may have one or the other of these two kinds of borrows, but not both at the same time:

  • one or more references (&T) to a resource,
  • exactly one mutable reference (&mut T).

However, it took me some time to realize how they conflict with some patterns or principles.

Here are my feedbacks. I selected 4 subjects which are general enough to be independent of this particular project:

Encapsulation

The borrowing rules constrain encapsulation. This was the first consequence I realized.

Here is a canonical sample:

pub struct Data {
    header: [u8; 4],
    payload: [u8; 20],
}

impl Data {
    pub fn new() -> Self {
        Self {
            header: [0; 4],
            payload: [0; 20],
        }
    }

    pub fn header(&mut self) -> &mut [u8] {
        &mut self.header
    }

    pub fn payload(&mut self) -> &mut [u8] {
        &mut self.payload
    }
}

fn main() {
    let mut data = Data::new();
    let header = data.header();
    let payload = data.payload();
}

We just create a new instance of Data, then bind mutable references to the header and payload arrays to local variables, through accessors.

However, this does not compile:

$ rustc sample.rs
error[E0499]: cannot borrow `data` as mutable more than once at a time
  --> sample.rs:21:19
   |
25 |     let header = data.header();
   |                  ---- first mutable borrow occurs here
26 |     let payload = data.payload();
   |                   ^^^^ second mutable borrow occurs here
27 | }
   | - first borrow ends here

The compiler may not assume that header() and payload() return references to disjoint data in the Data struct. Therefore, each one borrows the whole data structure. Since the borrowing rules forbid to get two mutables references to the same resource, it rejects the second call.

Sometimes, we face temporary limitations because the compiler is not smart enough (yet). This is not the case here: the implementation of header() might actually return a reference to payload, or write to the payload array, violating the borrowing rules. And the validity of a method call may not depend on the method implementation.

To fix the problem, the compiler must be able to know that the local variables header and payload reference disjoint data, for example by accessing the fields directly:

    let header = &mut data.header;
    let payload = &mut data.payload;

or by exposing a method providing both references simultaneously:

struct Data {
    fn header_and_payload(&mut self) -> (&mut [u8], &mut [u8]) {
        (&mut self.header, &mut self.payload)
    }
}

fn main() {
    let mut data = Data::new();
    let (header, payload) = data.header_and_payload();
}

Similarly, inside a struct implementation, the borrowing rules also prevent factoring code into a private method easily. Consider this (artificial) example:

pub struct Data {
    buf: [u8; 20],
    prefix_length: usize,
    sum: u32,
    port: u16,
}

impl Data {
    pub fn update_sum(&mut self) {
        let content = &self.buf[self.prefix_length..];
        self.sum = content.iter().cloned().map(u32::from).sum();
    }

    pub fn update_port(&mut self) {
        let content = &self.buf[self.prefix_length..];
        self.port = (content[2] as u16) << 8 | content[3] as u16;
    }
}

Here, the buf field is an array storing some prefix and content contiguously.

We want to factorize the way we retrieve the content slice, so that the update_*() methods are not bothered with the details. Let’s try:

 impl Data {
     pub fn update_sum(&mut self) {
-        let content = &self.buf[self.prefix_length..];
+        let content = self.content();
         self.sum = content.iter().cloned().map(u32::from).sum();
     }

     pub fn update_port(&mut self) {
-        let content = &self.buf[self.prefix_length..];
+        let content = self.content();
         self.port = (content[2] as u16) << 8 | content[3] as u16;
     }
+
+    fn content(&mut self) -> &[u8] {
+        &self.buf[self.prefix_length..]
+    }
 }

Unfortunately, this does not compile:

error[E0506]: cannot assign to `self.sum` because it is borrowed
  --> facto2.rs:11:9
   |
10 |         let content = self.content();
   |                       ---- borrow of `self.sum` occurs here
11 |         self.sum = content.iter().cloned().map(u32::from).sum();
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `self.sum` occurs here

error[E0506]: cannot assign to `self.port` because it is borrowed
  --> facto2.rs:16:9
   |
15 |         let content = self.content();
   |                       ---- borrow of `self.port` occurs here
16 |         self.port = (content[2] as u16) << 8 & content[3] as u16;
   |

As in the previous exemple, retrieving the reference through a method borrows the whole struct (here, self).

To workaround the problem, we can explain to the compiler that the fields are disjoint:

impl Data {
    pub fn update_sum(&mut self) {
        let content = Self::content(&self.buf, self.prefix_length);
        self.sum = content.iter().cloned().map(u32::from).sum();
    }

    pub fn update_port(&mut self) {
        let content = Self::content(&self.buf, self.prefix_length);
        self.port = (content[2] as u16) << 8 | content[3] as u16;
    }

    fn content(buf: &[u8], prefix_length: usize) -> &[u8] {
        &buf[prefix_length..]
    }
}

This compiles, but totally defeats the purpose of factorization: the caller has to provide the necessary fields.

As an alternative, we can use a macro to inline the code:

macro_rules! content {
    ($self:ident) => {
        &$self.buf[$self.prefix_length..]
    }
}

impl Data {
    pub fn update_sum(&mut self) {
        let content = content!(self);
        self.sum = content.iter().cloned().map(u32::from).sum();
    }

    pub fn update_port(&mut self) {
        let content = content!(self);
        self.port = (content[2] as u16) << 8 | content[3] as u16;
    }
}

But this seems far from ideal.

I think we must just live with it: encapsulation sometimes conflicts with the borrowing rules. After all, this is not so surprising: enforcing the borrowing rules requires to follow every concrete access to resources, while encapsulation aims to abstract them away.

Observer

The observer pattern is useful for registering event listeners on an object.

In some cases, this pattern may not be straightforward to implement in Rust.

For simplicity, let’s consider that the events are u32 values. Here is a possible implementation:

pub trait EventListener {
    fn on_event(&self, event: u32);
}

pub struct Notifier {
    listeners: Vec<Box<EventListener>>,
}

impl Notifier {
    pub fn new() -> Self {
        Self { listeners: Vec::new() }
    }

    pub fn register<T: EventListener + 'static>(&mut self, listener: T) {
        self.listeners.push(Box::new(listener));
    }

    pub fn notify(&self, event: u32) {
        for listener in &self.listeners {
            listener.on_event(event);
        }
    }
}

For convenience, make closures implement our EventListener trait:

impl<F: Fn(u32)> EventListener for F {
    fn on_event(&self, event: u32) {
        self(event);
    }
}

Thus, its usage is simple:

    let mut notifier = Notifier::new();
    notifier.register(|event| println!("received [{}]", event));
    println!("notifying...");
    notifier.notify(42);

This prints:

notifying...
received [42]

So far, so good.

However, things get a bit more complicated if we want to mutate a state when an event is received. For example, let’s implement a struct storing all the events we received:

pub struct Storage {
    events: Vec<u32>,
}

impl Storage {
    pub fn new() -> Self {
        Self { events: Vec::new() }
    }

    pub fn store(&mut self, value: u32) {
        self.events.push(value);
    }

    pub fn events(&self) -> &Vec<u32> {
        &self.events
    }
}

To be able to fill this Storage on each event received, we somehow have to pass it along with the event listener, which will be stored in the Notifier. Therefore, we need a single instance of Storage to be shared between the caller code and the Notifier.

Holding two mutable references to the same object obviously violates the borrowing rules, so we need a reference-counting pointer.

However, such a pointer is read-only, so we also need a RefCell for interior mutability.

Thus, we will use an instance of Rc<RefCell<Storage>>. It may seem too verbose, but using Rc<RefCell<T>> (or Arc<Mutex<T>> for thread-safety) is very common in Rust. And there is worse.

Here is the resulting client code:

    use std::cell::RefCell;
    use std::rc::Rc;

    let mut notifier = Notifier::new();

    // first Rc to the Storage
    let rc = Rc::new(RefCell::new(Storage::new()));

    // second Rc to the Storage
    let rc2 = rc.clone();

    // register the listener saving all the received events to the Storage
    notifier.register(move |event| rc2.borrow_mut().store(event));

    notifier.notify(3);
    notifier.notify(141);
    notifier.notify(59);
    assert_eq!(&vec![3, 141, 59], rc.borrow().events());

That way, the Storage is correctly mutated from the event listener.

All is not solved, though. In this example, we had access to the Rc<RefCell<Storage>> instance. What if we only have access to the Storage, e.g. if we want Storage to register itself from one of its methods, without requiring the caller to provide the Rc<RefCell<Storage>> instance?

impl Storage {
    pub fn register_to(&self, notifier: &mut Notifier) {
        notifier.register(move |event| {
            /* how to retrieve a &mut Storage from here? */
        });
    }
}

We need to retrieve the Rc<RefCell<Storage>> from the Storage in some way.

To do so, the idea consists in making the Storage aware of its reference-counting pointer. Of course, this only makes sense if Storage is constructed inside a Rc<RefCell<Storage>>.

This is exactly what enable_shared_from_this provides in C++, so we can draw inspiration from how it works: just store a Weak<RefCell<…>>, downgraded from the Rc<RefCell<…>>, into the structure itself. That way, we can use it to get a &mut Storage reference back in the event listener:

use std::rc::{Rc, Weak};
use std::cell::RefCell;

pub struct Storage {
    self_weak: Weak<RefCell<Storage>>,
    events: Vec<u32>,
}

impl Storage {
    pub fn new() -> Rc<RefCell<Self>> {
        let rc = Rc::new(RefCell::new(Self {
            self_weak: Weak::new(), // initialize empty
            events: Vec::new(),
        }));
        // set self_weak once we get the Rc instance
        rc.borrow_mut().self_weak = Rc::downgrade(&rc);
        rc
    }

    pub fn register_to(&self, notifier: &mut Notifier) {
        let rc = self.self_weak.upgrade().unwrap();
        notifier.register(move |event| rc.borrow_mut().store(event))
    }
}

Here is how to use it:

    let mut notifier = Notifier::new();
    let rc = Storage::new();
    rc.borrow().register_to(&mut notifier);
    notifier.notify(3);
    notifier.notify(141);
    notifier.notify(59);
    assert_eq!(&vec![3, 141, 59], rc.borrow().events());

So it is possible to implement the observer pattern in Rust, but this is a bit more challenging than in Java ;-)

When possible, it might be preferable to avoid it.

Mutable data sharing

Mutable references cannot be aliased.

How to share mutable data, then?

We saw that we can use Rc<RefCell<…>> (or Arc<Mutex<…>>), that enforces the borrowing rules at runtime. However, this is not always desirable:

Alternatively, we could use raw pointers manually inside unsafe code, but then this would be unsafe.

And there is another way, which consists in exposing temporary borrowing views of an object. Let me explain.

In Gnirehtet, a packet contains a reference to the raw data (stored in some buffer elsewhere) along with the IP and TCP/UDP header fields values (parsed from the raw data). We could have used a flat structure to store everything:

pub struct Packet<'a> {
    raw: &'a mut [u8],
    ipv4_source: u32,
    ipv4_destination: u32,
    ipv4_protocol: u8,
    // + other ipv4 fields
    transport_source: u16,
    transport_destination: u16,
    // + other transport fields
}

The Packet would provide setters for all the header fields (updating both the packet fields and the raw data). For example:

impl<'a> Packet<'a> {
    pub fn set_transport_source(&mut self, transport_source: u16) {
        self.transport_source = transport_source;
        let transport = &mut self.raw[20..];
        BigEndian::write_u16(&mut transport[0..2], port);
    }
}

But this would be poor design (especially since TCP and UDP header fields are different).

Instead, we would like to extract IP and transport headers to separate structs, managing their own part of the raw data:

// violates the borrowing rules

pub struct Packet<'a> {
    raw: &'a mut [u8], // the whole packet (including headers)
    ipv4_header: Ipv4Header<'a>,
    transport_header: TransportHeader<'a>,
}

pub struct Ipv4Header<'a> {
    raw: &'a mut [u8], // slice related to ipv4 headers
    source: u32,
    destination: u32,
    protocol: u8,
    // + other ipv4 fields
}

pub struct TransportHeader<'a> {
    raw: &'a mut [u8], // slice related to transport headers
    source: u16,
    destination: u16,
    // + other transport fields
}

You immediately spotted the problem: there are several references to the same resource, the raw byte array, at the same time.

Note that splitting the array is not a possibility here, since the raw slices overlap: we need to write the whole packet at once to the network, so the raw array in Packet must include the headers.

We need a solution compatible with the borrowing rules.

Here is the one I came up with:

And here is a simplification of the actual implementation:

pub struct Packet<'a> {
    raw: &'a mut [u8],
    ipv4_header: Ipv4HeaderData,
    transport_header: TransportHeaderData,
}

pub struct Ipv4HeaderData {
    source: u32,
    destination: u32,
    protocol: u8,
    // + other ipv4 fields
}

pub struct TransportHeaderData {
    source: u16,
    destination: u16,
    // + other transport fields
}

pub struct Ipv4Header<'a> {
    raw: &'a mut [u8],
    data: &'a mut Ipv4HeaderData,
}

pub struct TransportHeader<'a> {
    raw: &'a mut [u8],
    data: &'a mut TransportHeaderData,
}

impl<'a> Packet<'a> {
    pub fn ipv4_header(&mut self) -> Ipv4Header {
        Ipv4Header {
            raw: &mut self.raw[..20],
            data: &mut self.ipv4_header,
        }
    }

    pub fn transport_header(&mut self) -> TransportHeader {
        TransportHeader {
            raw: &mut self.raw[20..40],
            data: &mut self.transport_header,
        }
    }
}

The setters are implemented on the views, where they hold a mutable reference to the raw array:

impl<'a> TransportHeader<'a> {
    pub fn set_source(&mut self, source: u16) {
        self.data.source = source;
        BigEndian::write_u16(&mut raw[0..2], source);
    }

    pub fn set_destination(&mut self, destination: u16) {
        self.data.destination = destination;
        BigEndian::write_u16(&mut raw[2..4], destination);
    }
}

That way, the borrowing rules are respected, and the API is elegant:

    let mut packet = ;
    // "transport_header" borrows "packet" during its scope
    let mut transport_header = packet.transport_header();
    transport_header.set_source(1234);
    transport_header.set_destination(1234);

Compiler limitations

Rust is a young language, and the compiler has some annoying pitfalls.

The worst, in my opinion, is related to non-lexical lifetimes, which leads to unexpected errors:

struct Container {
    vec: Vec<i32>,
}

impl Container {
    fn find(&mut self, v: i32) -> Option<&mut i32> {
        None // we don't care the implementation
    }

    fn get(&mut self, v: i32) -> &mut i32 {
        if let Some(x) = self.find(v) {
            return x;
        }
        self.vec.push(v);
        self.vec.last_mut().unwrap()
    }
}
error[E0499]: cannot borrow `self.vec` as mutable more than once at a time
  --> sample.rs:14:9
   |
11 |         if let Some(x) = self.find(v) {
   |                          ---- first mutable borrow occurs here
...
14 |         self.vec.push(v);
   |         ^^^^^^^^ second mutable borrow occurs here
15 |         self.vec.last_mut().unwrap()
16 |     }
   |     - first borrow ends here

Hopefully, it should be fixed soon.

The Impl Trait feature, allowing to return unboxed abstract types from functions, should also improve the experience (there is also an expanded proposal).

The compiler generally produces very helpful error messages. But when it does not, they can be very confusing.

Safety pitfalls

The first chapter of the Rustonomicon says:

Safe Rust is For Reals Totally Safe.

[…]

Safe Rust is the true Rust programming language. If all you do is write Safe Rust, you will never have to worry about type-safety or memory-safety. You will never endure a null or dangling pointer, or any of that Undefined Behavior nonsense.

That’s the goal. And that’s almost true.

Leakpocalypse

In the past, it was possible to write safe-Rust code accessing freed memory.

This “leakpocalypse” led to a clarification of the safety guarantees: not running a destructor is now considered safe. In other words, memory-safety may not rely on RAII anymore (in fact, it never could, but it has been noticed only belatedly).

As a consequence, std::mem::forget is now safe, and JoinGuard has been deprecated and removed from the standard library (it has been moved to a separate crate).

Other tools relying on RAII (like Vec::drain()) must take special care to prevent memory corruption.

Whew, memory-safety is (now) safe.

Undefined infinity

In C and C++, infinite loops without side-effects are undefined behavior. This makes it possible to write programs that unexpectedly disprove Fermat’s Last Theorem.

In practice, the Rust compiler relies on LLVM, which (currently) applies its optimizations assuming that infinite loops without side-effects are undefined behavior. As a consequence, such undefined behaviors also occur in Rust.

Here is a minimal sample to trigger it:

fn infinite() {
    loop {}
}

fn main() {
    infinite();
}

Running without optimizations, it behaves as “expected”:

$ rustc ub.rs && ./ub
^C                    (infinite loop, interrupt it)

Enabling optimizations makes the program panic:

$ rustc -O ub.rs && ./ub
thread 'main' panicked at 'assertion failed: c.borrow().is_none()', /checkout/src/libstd/sys_common/thread_info.rs:51
note: Run with `RUST_BACKTRACE=1` for a backtrace.

Alternatively, we can produce unexpected results without crashing:

fn infinite(mut value: u32) {
    // infinite loop unless value initially equals 0
    while value != 0 {
        if value != 1 {
            value -= 1;
        }
    }
}

fn main() {
    infinite(42);
    println!("end");
}
$ rustc ub.rs && ./ub
^C                    (infinite loop, interrupt it)

But with optimizations:

$ rustc -O ub.rs && ./ub
end

This is a corner case, that will probably be solved in the future. In practice, Rust safety guarantees are pretty strong (at a cost of being constraining).

Segfault

This section has been added after the publication.

There are other sources of undefined behaviors (look at the issues tagged I-unsound).

For instance, casting a float value that cannot fit into the target type is undefined behavior, which can be propagated to trigger a segfault:

#[inline(never)]
pub fn f(ary: &[u8; 5]) -> &[u8] {
    let idx = 1e100f64 as usize;
    &ary[idx..]
}

fn main() {
    println!("{}", f(&[1; 5])[0xdeadbeef]);
}
rustc -O ub.rs && ./ub
Segmentation fault

Stats

That’s all for my feedbacks about the language itself.

As an appendix, let’s compare the current Java and Rust versions of the relay server.

Number of lines

$ cloc relay-{java,rust}/src
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Rust                            29            687            655           4506
Java                            37            726            701           2931
-------------------------------------------------------------------------------

(tests included)

The Rust project is significantly bigger, for several reasons:

The Java version has more files because the unit tests are separate, while in Rust they are in the same file as the classes they test.

Just for information, here are the results for the Android client:

$ cloc app/src
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Java                            15            198            321            875
XML                              6              7              2             76
-------------------------------------------------------------------------------
SUM:                            21            205            323            951
-------------------------------------------------------------------------------

Binary size

--------------------------------------------
Java     gnirehtet.jar                   61K
--------------------------------------------
Rust     gnirehtet                      3.0M
         after "strip -g gnirehtet"     747K
         after "strip gnirehtet"        588K
--------------------------------------------

The Java binary itself is far smaller. The comparison is not fair though, since it requires the Java Runtime Environment:

$ du -sh /usr/lib/jvm/java-1.8.0-openjdk-amd64/
156M	/usr/lib/jvm/java-1.8.0-openjdk-amd64/

Memory usage

With a single TCP connection opened, here is the memory consumption for the Java relay server:

$ sudo pmap -x $RELAY_JAVA_PID
                  Kbytes     RSS   Dirty
total kB         4364052   86148   69316

(output filtered)

And for the Rust relay server:

$ sudo pmap -x $RELAY_RUST_PID
                  Kbytes     RSS   Dirty
total kB           19272    2736     640

Look at the RSS value, which indicates the actual memory used.

As expected, the Java version consumes more memory (86Mb) than the Rust one (less than 3Mb). Moreover, its value is unstable due to the allocation of tiny objects and their garbage collection, which also generates more dirty pages. On the contrary, the Rust value is very stable: once the connection is created, there are no memory allocations at all.

CPU usage

To compare CPU usage, here is my scenario: a 500Mb file is hosted by Apache on my laptop, I start the relay server through perf stat, then I download the file from Firefox on Android. As soon as the file is downloaded, I stop the relay server (Ctrl+C).

Here are the results for the Java version:

$ perf stat -B java -jar gnirehtet.jar relay
 Performance counter stats for 'java -jar gnirehtet.jar relay':

      11805,458302      task-clock:u (msec)       #    0,088 CPUs utilized
                 0      context-switches:u        #    0,000 K/sec
                 0      cpu-migrations:u          #    0,000 K/sec
            28 618      page-faults:u             #    0,002 M/sec
    17 908 360 446      cycles:u                  #    1,517 GHz
    13 944 172 792      stalled-cycles-frontend:u #   77,86% frontend cycles idle
    18 437 279 663      instructions:u            #    1,03  insn per cycle
                                                  #    0,76  stalled cycles per insn
     3 088 215 431      branches:u                #  261,592 M/sec
        70 647 760      branch-misses:u           #    2,29% of all branches

     133,975117164 seconds time elapsed

And for the Rust version:

$ perf stat -B ./gnirehtet relay
 Performance counter stats for 'target/release/gnirehtet relay':

       2707,479968      task-clock:u (msec)       #    0,020 CPUs utilized
                 0      context-switches:u        #    0,000 K/sec
                 0      cpu-migrations:u          #    0,000 K/sec
             1 001      page-faults:u             #    0,370 K/sec
     1 011 527 340      cycles:u                  #    0,374 GHz
     2 033 810 378      stalled-cycles-frontend:u #  201,06% frontend cycles idle
       981 103 003      instructions:u            #    0,97  insn per cycle
                                                  #    2,07  stalled cycles per insn
        98 929 222      branches:u                #   36,539 M/sec
         3 220 527      branch-misses:u           #    3,26% of all branches

     133,766035253 seconds time elapsed

I am not an expert in analyzing the results, but as far as I understand from the task-clock:u value, the Rust version consumes 4× less CPU-time.

Conclusion

Rewriting Gnirehtet in Rust was an amazing experience, where I learnt a great language and new programming concepts. And now, we get a native application showing better performances.

Happy reverse tethering!

Discuss on reddit and Hacker News.

Fusionner deux dépôts git

mercredi 12 juillet 2017 à 20:30

Ce billet explique comment fusionner un dépôt git (avec son historique) dans un sous-répertoire d’un autre dépôt git.

Cas d’usage

Mon projet principal se trouve dans un dépôt main. J’ai démarré dans un autre dépôt un projet other, que je souhaite finalement intégrer dans un sous-répertoire sub/ du projet principal, en conservant son historique. Après cette fusion, je ne garderai que le dépôt principal.

Fusion

Les deux projets se trouvent dans le répertoire courant :

$ ls
main  other

Dans le dépôt main, copier la branche master de other dans une nouvelle branche tmp :

cd main
git fetch ../other master:tmp

Le dépôt main contient alors les historiques disjoints des deux projets.

Nous allons maintenant réécrire l’historique complet de la branche tmp pour déplacer tout le contenu dans un sous-répertoire sub/, grâce une commande donnée en exemple de man git filter-branch :

git checkout tmp
git filter-branch --index-filter \
    'git ls-files -s | sed "s-\t\"*-&sub/-" |
        GIT_INDEX_FILE=$GIT_INDEX_FILE.new \
            git update-index --index-info &&
     mv "$GIT_INDEX_FILE.new" "$GIT_INDEX_FILE"'

À ce stade, nous avons toujours deux historiques indépendants, mais le contenu lié à la branche tmp se trouve dans le sous-répertoire sub/.

A---B---C---D master

  X---Y---Z tmp

La dernière étape consiste à relier les deux historiques, soit grâce à un rebase, soit grâce à un merge.

Un rebase réécrit l’historique du sous-projet sur la branche master :

git rebase master

# A---B---C---D---X'--Y'--Z' master

Un merge relie juste les deux historiques grâce à un commit de merge :

git merge tmp --allow-unrelated-histories

# A---B---C---D---M  master
#                /
#       X---Y---Z tmp

Concrètement

J’ai débuté la réécriture du serveur relais de gnirehtet en Rust dans un dépôt séparé. Maintenant qu’il commence à fonctionner, je l’ai fusionné dans un sous-répertoire du dépôt principal tout en conservant l’historique :

git fetch ../rustrelay master:tmp
git checkout tmp
git filter-branch --index-filter \
    'git ls-files -s | sed "s-\t\"*-&rustrelay/-" |
        GIT_INDEX_FILE=$GIT_INDEX_FILE.new \
            git update-index --index-info &&
     mv "$GIT_INDEX_FILE.new" "$GIT_INDEX_FILE"'
git rebase master

Fusionner deux dépôts git

mercredi 12 juillet 2017 à 20:30

Ce billet explique comment fusionner un dépôt git (avec son historique) dans un sous-répertoire d’un autre dépôt git.

Cas d’usage

Mon projet principal se trouve dans un dépôt main. J’ai démarré dans un autre dépôt un projet other, que je souhaite finalement intégrer dans un sous-répertoire sub/ du projet principal, en conservant son historique. Après cette fusion, je ne garderai que le dépôt principal.

Fusion

Les deux projets se trouvent dans le répertoire courant :

$ ls
main  other

Dans le dépôt main, copier la branche master de other dans une nouvelle branche tmp :

cd main
git fetch ../other master:tmp

Le dépôt main contient alors les historiques disjoints des deux projets.

Nous allons maintenant réécrire l’historique complet de la branche tmp pour déplacer tout le contenu dans un sous-répertoire sub/, grâce une commande donnée en exemple de man git filter-branch :

git checkout tmp
git filter-branch --index-filter \
    'git ls-files -s | sed "s-\t\"*-&sub/-" |
        GIT_INDEX_FILE=$GIT_INDEX_FILE.new \
            git update-index --index-info &&
     mv "$GIT_INDEX_FILE.new" "$GIT_INDEX_FILE"'

À ce stade, nous avons toujours deux historiques indépendants, mais le contenu lié à la branche tmp se trouve dans le sous-répertoire sub/.

A---B---C---D master

  X---Y---Z tmp

La dernière étape consiste à relier les deux historiques, soit grâce à un rebase, soit grâce à un merge.

Un rebase réécrit l’historique du sous-projet sur la branche master :

git rebase master

# A---B---C---D---X'--Y'--Z' master

Un merge relie juste les deux historiques grâce à un commit de merge :

git merge tmp --allow-unrelated-histories

# A---B---C---D---M  master
#                /
#       X---Y---Z tmp

Concrètement

J’ai débuté la réécriture du serveur relais de gnirehtet en Rust dans un dépôt séparé. Maintenant qu’il commence à fonctionner, je l’ai fusionné dans un sous-répertoire du dépôt principal tout en conservant l’historique :

git fetch ../rustrelay master:tmp
git checkout tmp
git filter-branch --index-filter \
    'git ls-files -s | sed "s-\t\"*-&rustrelay/-" |
        GIT_INDEX_FILE=$GIT_INDEX_FILE.new \
            git update-index --index-info &&
     mv "$GIT_INDEX_FILE.new" "$GIT_INDEX_FILE"'
git rebase master

Gnirehtet

jeudi 30 mars 2017 à 11:50

Durant ces dernières semaines chez Genymobile, j’ai développé un outil de reverse tethering pour Android, permettant aux téléphones (et aux tablettes) d’utiliser la connexion internet de l’ordinateur sur lequel ils sont branchés, sans accès root (ni sur le téléphone, ni sur le PC). Il fonctionne sur GNU/Linux, Windows et Mac OS.

Nous avons décidé de le publier en open source, sous le nom de gnirehtet.

Oui, c’est un nom bizarre, jusqu’à ce qu’on réalise qu’il s’agit du résultat de la commande bash :

rev <<< tethering

Utilisation

Il suffit de télécharger la dernière release, de l’extraire, et d’exécuter la commande suivante sur le PC :

./gnirehtet rt

Une fois activé, un logo en forme de clé apparaît dans la barre de statut du téléphone :

key

Lisez le fichier README pour plus de détails.

Fonctionnement

Le projet est composé de deux parties :

Depuis, je l’ai réécrit en Rust.

Le client s’enregistre en tant que VPN, de manière à intercepter tout le trafic réseau du téléphone, sous la forme de byte[] de paquets IPv4 bruts, qu’il transmet alors vers le serveur relais sur une connexion TCP (établie par-dessus adb).

Le serveur relais analyse les en-têtes des paquets, ouvre des connexions à partir du PC vers les adresses de destinations demandées, et relaie le contenu dans les deux sens en suivant les protocoles UDP et TCP. Il crée et renvoie des paquets de réponse vers le client Android, qui les écrit sur l’interface VPN.

D’une certaine manière, le serveur relais se comporte comme un NAT, en cela qu’il ouvre des connexions pour le compte d’autres machines qui n’ont pas accès au réseau. Cependant, il diffère des NAT standards dans la manière dont il communique avec les clients, en utilisant un protocole spécifique (très simple) sur une connexion TCP.

archi

Pour plus de détails, lisez la page développeurs.

Conception

Une fois que l’application est capable d’intercepter l’intégralité du traffic réseau du téléphone, différentes approches sont possibles. Voici celles que j’ai considérées.

TL;DR: J’ai d’abord étudié l’utilisation d’un “TUN device” sur le PC, mais ça ne répondait pas à nos besoins. J’ai ensuite voulu utiliser SOCKS pour bénéficier des serveurs existants, mais des contraintes nous empêchaient de relayer le trafic UDP. Alors j’ai implémenté gnirehtet.

TUN device

Lors de mes recherches pour savoir comment implémenter le reverse tethering, j’ai d’abord trouvé des projets créant un TUN device sur l’ordinateur (vpn-reverse-tether and SimpleRT).

Cette conception fonctionne très bien, et a plusieurs avantages :

Cependant :

Il se peut néanmoins que ces applications répondent davantage à vos besoins.

SOCKS

Afin d’éviter d’avoir à développer un serveur relais spécifique, ma première idée était d’écrire un client qui parlait le protocole SOCKS (suivant le RFC 1928). Ainsi, il serait possible d’utiliser n’importe quel serveur SOCKS existant, par exemple celui fourni par ssh -D.

Vous l’avez probablement déjà utilisé pour éviter le filtrage des pare-feux en entreprise. Pour cela, démarrez le tunnel :

ssh mon_serveur -ND1080

Puis configurez votre navigateur pour utiliser le proxy SOCKS localhost:1080. N’oubliez pas d’activer la résolution DNS distante pour résoudre les noms de domaine à partir de mon_serveur (dans Firefox, activez network.proxy.socks_remote_dns dans about:config).

Malheureusement, l’implémentation d’OpenSSH ne supporte pas UDP, même si le protocole SOCKS5 lui-même le supporte. Et nous avons besoin d’UDP, au moins pour les requêtes DNS (ainsi que pour NTP).

Si vous avez lu attentivement les deux paragraphes précédents, vous devriez vous demander :

Comment Firefox peut-il résoudre les noms de domaine à distance alors que le proxy SOCKS d’OpenSSH ne supporte même pas UDP ?

La réponse se trouve dans la section 4 du RFC : l’adresse de destination demandée peut être une IPv4, une IPv6 ou un nom de domaine. Par contre, pour utiliser cette fonctionnalité, le client (par exemple Firefox) doit savoir qu’il passe par un proxy (puisqu’il doit explicitement passer le nom de domaine au lieu de le résoudre localement), alors que notre reverse tethering doit être transparent.

Mais tout n’est pas perdu. Certes, OpenSSH ne supporte pas UDP, mais ce n’est qu’une implémentation spécifique, nous pourrions en utiliser une autre. Malheureusement, SOCKS5 relaie UDP sur UDP, et les téléphones et l’ordinateur communiquent sur adb (grâce à adb reverse), qui ne supporte pas non plus la redirection de ports UDP.

Peut-être que nous pourrions au moins relayer les requêtes DNS en les forçant à utiliser TCP, comme le fait tsocks :

tsocks will normally not be able to send DNS queries through a SOCKS server since SOCKS V4 works on TCP and DNS normally uses UDP. Version 1.5 and up do however provide a method to force DNS lookups to use TCP, which then makes them proxyable.

Mais finalement, SOCKS n’est plus une solution aussi attirante pour implémenter le reverse tethering.

Gnirehtet

Par conséquent, j’ai développé à la fois le client et le serveur relais manuellement.

Ce billet de blog et différents projets open source (SimpleRT, vpn-reverse-tether, LocalVPN et ToyVpn) m’ont beaucoup aidé à comprendre comment implémenter cette solution de reverse tethering.

Conclusion

Gnirehtet permet aux téléphones et tablettes Android d’utiliser facilement la connection internet d’un ordinateur par USB, sans accès root. C’est très utile quand vous ne pouvez pas accéder au réseau par un point d’accès WiFi.

J’espère qu’il pourra être utile à certains d’entre vous.

Discussions sur reddit et Hacker News.