Linux Attitude

Niveau :
Résumé : chmod +x test.c

Après une technique utilisant du perl, voici une nouvelle façon d'utiliser du C aussi simplement qu'un script.

Cette fois nous évitons l'usage de perl, on se passe donc de ses avantages en terme de parsing. Par contre, on utilise un en-tête court et le code fonctionne avec n'importe quel code valide en C. Comme d'habitude, on fait propre et on renvoie le bon code de retour.

#!/bin/sh
tail -n +4 $0 | gcc -Wall -o /tmp/cscript.$$ -x c - && /tmp/cscript.$$ $*
ret=$? ; rm -f /tmp/cscript.$$ ; exit $ret
//
// Code C
//
#include <stdio.h>
int main(int argc, char** argv)
{
        printf( "Appel de %s avec %d arguments\n", argv[0], argc-1 );
        return 0;
}

Et maintenant on teste pour prouver que ça marche :

chmod +x test.c
./test.c 1 2 3 && echo "OK" | | echo "KO"

Niveau :
Résumé : SSE

Aujourd'hui l'avenir (et un peu le passé aussi). Vous souvenez-vous des cray ? Ces machines surpuissantes qui avaient au moins la puissance de calcul d'une TI92. Comment faisaient-ils pour avoir une telle puissance ? Il faisaient des calculs identiques en parallèle et multipliaient ainsi par n le nombre d'opérations. C'est ce qu'on appelle une architecture vectorielle.

Intel dans sa grande bonté a commencé à mettre en place une telle architecture dans ses processeurs. Tout d'abord avec les instructions MMX. Ces instructions utilisent les registres servant au calcul en virgule flottante (quelques transistors de gagnés), lesquels font 64 bits. On peut ainsi exécuter des instructions identiques simultanément sur 4 fois 1 octets ou sur 2 fois 2 octets. Ce qui est bien, mais pas top.

Le SSE est une amélioration du concept. Tout d'abord on utilise de nouveaux registres (ce qui libère les calculs en virgule flottante) et on leur donne une taille de 128bits. Du coup on peut manipuler deux fois plus d'entiers et cela devient intéressant pour les flottants. On peut caser 4 flottants simple précision et 2 flottants double précision dans 128 bits. Le SSE s'arrête aux 4 flottants et le SSE2 ajoute quasiment toutes les autres combinaisons possibles (flottants et entiers).

Version normale

Comme nous sommes joueurs, nous allons jouer à améliorer notre code de calcul de Mandelbrot. Mais cette fois, nous allons le laisser tourner sous linux. Comme ne sommes plus dans notre monde, mais sur un vrai système, nous allons devoir faire quelques modifications. Nous allons continuer à écrire directement en mémoire, donc on garde nos fonctions d'écriture de pixels, mais cette fois dans une mémoire allouée avec malloc. Ajoutons le support de l'écriture d'un des format d'image les plus simples, le BMP, pour stocker notre image dans un fichier et pouvoir admirer le résultat. Pour cela on prend la première documentation venue.

/* Ecriture de l'image dans un fichier bitmap (on écrit l'en-tête kivabien puis les données) */
void writebitmap(char* filename, char*bitmap, int width, int height);

Et voilà, cela nous donne une première version du code quasiment identique à la précédente et donc non optimisée pour le SSE (disponible à la fin de l'article).

Version SSE

Commençons à travailler en découvrant les instructions du sse. Celles-ci sont rendues disponibles en C à travers les en-têtes qui vont bien. Ouf, cela nous évitera de coder directement en assembleur :

/* mm=mmx   xmm=sse  emm=sse2   pmm=sse3 (rien que de très logique ...) */
#include <emmintrin.h>

Il est possible de lire ces en-têtes pour savoir quelles sont les instructions et les types disponibles. C'est un peu long et assez peu instructif lorsqu'on ne connait pas la base du sse, mais ils peuvent servir de référence quand on sait ce qu'on cherche. Ils se trouvent dans /usr/lib/gcc/x86_64-linux-gnu/4.1.2/include/ (à adapter à votre cas). Les types et fonctions du sse sont codifiés.

Les opérations sont construites comme suit _mm_XXXX_YY :

• _mm est un préfixe
• XXXX est le nom de l'instruction en assembleur (à quelques variations près)
• YY est le type des opérandes manipulés :
  • sd : double seul (1 double qui n'occupe pas tout le registre)
  • pd : double packé (2 doubles dans un registre)
  • ss : flottant seul (1 flottant qui n'occupe pas tout le registre)
  • ps : flottant packé (4 flottants dans un registre)
  • ...

Les types de données sont aussi définis selon un certain schéma :

• __m128 : registre de 128 bits
• __m128i : registre de 128 bits destiné au calcul entier
• __m128d : registre de 128 bits destiné au calcul flottant
• __v4sf : vecteur de 4 simple flotants (4 * 32 bits)
• __v2di : vecteur de 2 entiers doubles (2 * 64 bits)
• ...

Notez que d'un point de vue binaire, ils sont tous identiques et font 128bits.

Maintenant nous allons modifier le code pour qu'il calcule les points 4 par 4. On va donc changer nos 2 fonctions de calcul en :

/* conversion de coordonnées 4 points par 4 */
void convert_i2d4(int x, int y, __v4sf *ppx, __v4sf *ppy)
/* une itération du calcul pour 4 points */
__v4sf iteration4(__v4sf cx, __v4sf cy, __v4sf *ppx, __v4sf *ppy)

On utilise un des types précédents : __v4sf. C'est un vecteur de 128 bits contenant 4 flottants simple précision. Mais comme nous n'utilisons plus des types standards du C, nous devrons utiliser des fonctions à la place des opérateurs +, -, / et *, ce qui rend le code un peu plus lourd à lire et à écrire, par exemple :

        /* t = p^2 + C */
        tx = _mm_add_ps( _mm_sub_ps(_mm_mul_ps( *ppx, *ppx),  _mm_mul_ps(*ppy, *ppy)) , cx);
        ty = _mm_add_ps( _mm_mul_ps(two, _mm_mul_ps(*ppx, *ppy)), cy);

On y ajoute quelques constantes globales du fait que les constantes n'existent pas pour les type vectoriels :

__v4sf two = _mm_set_ps(2,2,2,2);

Et enfin, on doit adapter un peu notre algorithme pour qu'il ne s'arrête que lorsque les 4 points ont tous dépassés le seuil. Pour que la bonne couleur soit bien enregistrée séparément pour chaque point, on va faire la comparaison sur les 4 points grâce à _mm_cmple_ps qui renvoit 0 ou -1 sous forme de vecteur d'entier. Il nous suffit d'additionner les résultats pour récupérer la couleur de chaque point telle que nous l'avions définie plus tôt.

    /* calcul */
    radius = iteration4(cx, cy, &px, &py);
    /* on compare au rayon max, la valeur de retour est constituées de 4 entiers valant 0 ou -1 */
    jj = (__m128i)_mm_cmple_ps(radius, eight);
    /* et on additionne tous les -1 */
    ii = _mm_add_epi32(ii, jj);
    /* un int fait 32 bits sur les i386 et les x86-64 ... */
    ptr = (int*)&jj;
    /* il y a un moment où ce n'est plus la peine de calculer */
    if(ptr[0] == 0 && ptr[1] == 0 && ptr[2] == 0 && ptr[3] == 0)
        break;
 

Le code complet est disponible à la fin de l'article.

Résultat

Mais cela vaut-il le coup ? Oui, et nous allons le montrer. Tout d'abord sur un processeur 32 bits. Nous allons comparer plusieurs combinaisons. Avec sse, sans sse, avec différents niveaux d'optimisation, avec notre code spécifique, et sans.

exécution sur un i386 (en secondes)

Optimization	-		-O1		-O2		-O3
Gcc parameter	-	-msse2	-	-msse2	-	-msse2	-	-msse2
normal code	6.20	6.40	3.4	3.5	2.95	2.65	2.60	2.35
SSE code	-	4.75	-	0.91	-	0.55	-	0.50

Les résultats sont assez parlants. Que peut-on en déduire ? Que le sse ne semble pas très performant en l'absence d'optimisation (nosse.c et colonnes sans optimisation ou avec -O1).

Ensuite, que même sans utiliser le sse, gcc est lui-même capable de nous faire gagner beaucoup en performances avec ses optimisations. Mais gardez à l'esprit que cela est surtout valable parce qu'on utilise beaucoup de calculs en virgule flottantes et que nos fonctions prennent de gros arguments.

Enfin, que la modification de notre algorithme pour profiter du sse nous a permis de faire mieux que x4 sur du code déjà optimisé par gcc. En effet, gcc optimise ce qu'il peut, mais il lui est très difficile de changer un algorithme. Il est prévu que de nouvelles versions de gcc sachent vectoriser automatiquement des calculs, mais il faudra tout de même faire attention à la façon dont on code.

exécution sur un x86-64 (en secondes)

Optimization	-		-O1		-O2		-O3
Gcc parameter	-	-msse2	-	-msse2	-	-msse2	-	-msse2
normal code	2.10	2.10	1.05	1.05	0.76	0.76	0.72	0.72
SSE code	2.10	2.10	0.30	0.30	0.30	0.30	0.30	0.30

Et enfin regardons le même code sur un processeur 64 bits. Tout d'abord on remarque que ma machine 64 bits est plus puissante que la précédente :-) Ensuite, on constate qu'il n'y a pas de différence entre l'option sse et sont absence. Et heureusement puisque tous les processeurs 64 bits ont le sse par défaut et le compilateur ne se gène pas pour l'ajouter lui-même. On remarque que comme pour le code 32 bits, il y a un facteur 3 entre l'option -O3 et l'absence d'optimisation pour le code normal.

Par contre, les différents niveaux d'optimisation au delà de -O1 n'influent plus sur la vitesse d'exécution. Je n'ai pas d'explications à cela.

Et enfin on constate que le sse a réduit la différence de puissance entre les 2 machines.

Pour ceux qui se demanderaient si on mesure les bonnes choses, un test écrivant tous les pixels en noir a été fait, et il ne prend pas plus de 0.03s sur ces plate-formes (toujours moins de 10%). Ce qui veut dire que nos comparaisons sont pertinentes (et qu'il n'est pas nécessaire d'optimiser cette partie).

Vous voulez tout savoir sur le SSE ? Arstechnica a publié un très bon article sur le sujet. Sinon, vous avez toujours la liste détaillée des instructions.

PS : Intel trouvant que la vectorisation est une bonne chose et voyant que tout cela marche bien a prévu d'ajouter les instructions AVX dans ses prochains processeurs. En gros, c'est la même chose que le SSE mais sur 256 bits cette fois.

PJ :

• mandel-nosse.c
• mandel-sse.c

Niveau :
Résumé : grub ; noyau ; multiboot ; mandelbrot

Suite à de précédentes bidouilles, on veut faire mieux.

Multiboot

Donc grub peut booter plusieurs formats, l'un d'entre eux est le multiboot, un format de fichier bootable défini par les développeurs de grub espérant qu'il soit adopté par différentes distributions. Il souffre d'un certain nombre de faiblesses et n'est pas encore vraiment un standard. D'autant que grub lui-même ne supporte pas encore complètement la spécification pourtant très courte. Si vous ne voulez pas lire toute la spécification, allez directement au chapitre 4 où on trouve un code d'exemple prêt à compiler pour vous lancer dans le développement.

Vous trouverez un autre exemple chez quelqu'un qui s'est amusé à coder un space invaders bootable directement à partir de la spécification multiboot.

Alors c'est parti, reprenons notre projet précédent. Faites attention, le processeur est dans un état particulier lorsqu'on vous laisse la main (lisez le chapitre 3.2), à vous de vous en accommoder.

Mode graphique

Tout d'abord on voudrait changer le mode graphique, et si possible pour mieux que la première fois. Pour cela, on va utiliser le standard vesa 2.0 qui standardise des modes avec une plus grande définition et qui ajoute de nouvelles fonctions au bios pour manipuler la carte.

Choisissons le mode 0x118 (1024x768x24) avec 16 millions de couleurs. Plus besoin de gérer un palette puisqu'on écrit directement les couleurs RGB à utiliser pour le pixel. On aura tout de même une fonction de palette puisqu'on n'utilise qu'un petit nombre de couleurs placées sur une échelle.

Le problème c'est que vesa n'a pas prévu qu'on puisse appeler les fonctions de la carte en mode protégé sans passer au moins une fois par une interruption en mode réel. Multiboot est bien gentil, il a prévu le cas, malheureusement, grub n'implémente pas les fonctions qu'il devrait pour le faire pour nous. Un patch est disponible pour ceux qui voudrait quand même cette fonctionnalité.

Il nous faudra donc faire nous-même ces interruptions. Pour survivre au mode réel nous devrons être sous le premier Mo de RAM, or grub nous place juste au dessus (en 0x100000). Notre premier bout de code aura donc pour but de nous déplacer en dessous. Pour cela on commence par prendre l'en-tête multiboot (beaucoup plus simple que pour les zImage) et on écrit le code pour se déplacer en 0x1000 (choix arbitraire) :

        /* on se copie ailleurs */
        mov     $KERNEL_SIZE,%ecx /* en octets */
        mov     $KERNEL_ORIG,%esi /* source juste après ce secteur */
        mov     $KERNEL_DEST,%edi /* destination sous les 1Mo */
        rep movsw

        /* et on va dans notre nouveau noyau */
        ljmp    $0x8,$KERNEL_DEST

Bien, maintenant, il faut passer du mode protégé au mode réel et inversement pour pouvoir faire des interruptions. Choisissons comme toujours de ne pas réinventer la roue et repiquons le code de grub qui dispose déjà de ces fonctions en assembleur. Elles s'appellent real_to_prot et prot_to_real. Pour ceux qui voudraient comprendre comment faire, c'est partout sur le net. Comme le mode protégé a besoin de descripteurs de segment, on n'oublie pas de les définir aussi (lire la fin du fichier asm.S) .

Du coup on peut utiliser 2 fonctions vesa bien utiles dans notre code, set_mode pour mettre en place notre mode graphique, et get_modeinfo pour savoir comment l'utiliser. En effet, on voudrait, comme avant pouvoir accéder directement à la mémoire vidéo pour y mettre nos pixels. La fonction get_modeinfo est là pour ça, elle utilise la fonction 0x4F01 du bios. On lui passe une adresse dans laquelle elle va écrire une structure de données nous informant sur le mode choisi. On choisit l'adresse de cette structure au pif puisqu'on n'a pas de gestion de la mémoire et qu'on a toute la ram pour nous. On prend 8000:0000.

La structure renvoyée contient l'adresse du mapping de la mémoire vidéo en 28h, ainsi que ses dimensions. Cela nos permettrait de changer le mode dans notre code facilement (notez les conversions de type pour lire le bon nombre d'octets) :

        /* on récupère les infos sur le mode qui nous intéresse */
        get_modeinfo(0x118);
        /* conversion de l'adresse du format [segment:offset] au format à plat */
        data = (MODEINFO_SEG << 4)+MODEINFO_OFF;
        /* on joue sur les converstions pour la lecture du bon nombre d'octets en ram */
        video = (unsigned char*) *(unsigned int*)(data + 0x28);
        width = (int) *(unsigned short*)(data + 0x12);
        height = (int) *(unsigned short*)(data + 0x14);

Code

On repart du code de l'article précédent. On y apporte quelques modifications techniques liées au changement de mode. Par exemple l'écriture d'un pixel se résume à l'écriture des 3 couleurs au bon endroit en ram :

        int pos = bpp*(x + y*width);
        /* et on ecrit directement en mémoire vidéo */
        video[pos] = r;
        video[pos+1] = g;
        video[pos+2] = b;

Pour ceux qui veulent aller plus loin dans la compréhension du mode protégé, ça aurait pu aussi être l'occasion de mettre en place un segment séparé pour écrire en mémoire vidéo avec la commande lgdt.

On peut imaginer y ajouter des tâches, par exemple une sorte de thread pour gérer le clavier. Mais la ça commence à devenir complexe et il vaudrait mieux lire des OS existants pour bien comprendre tout ça. Par exemple il existe minix qui a été fait dans un but pédagogique.

Compilation

Une autre chose change, c'est la compilation. Puisque le format multiboot est plus simple, nous n'avons plus besoin du script setup.ld. Par contre, puisque notre binaire contient deux morceaux (souvenez vous de la copie sous les 1Mo en début d'article), on devra modifier notre compilation.

Ce qui se résume en 2 partie, une pour le code de copie fait pour tourner en 0x100000 :

LDFLAGS1="-nostdlib -Wl,-N -Wl,-Ttext -Wl,100000 -m32"
gcc $LDFLAGS1 -o boot.exec boot.o
objcopy -O binary boot.exec boot

Et une partie contenant tout le reste du code, qu'on va placer en 0x1000 :

LDFLAGS2="-nostdlib -Wl,-N -Wl,-Ttext -Wl,1000 -m32"
gcc $LDFLAGS2 -o kernel.exec start.o asm.o kernel.o debug.o
objcopy -O binary kernel.exec kernel

Et enfin une dernière copie qui va concaténer les 2 binaires :

# on force la taille pour éviter les problèmes avec le bootloader
dd if=/dev/zero of=mandel2 bs=256 count=32 2>/dev/null 
# la premiere partie
dd if=boot bs=256 count=1 of=mandel2 conv=notrunc 2>/dev/null
# la 2e partie a une position fixée dans le code de la première (boot.S + header.h)
dd if=kernel bs=256 seek=1 of=mandel2 conv=notrunc 2>/dev/null

Run

Encore une fois, il suffit de préciser le fichier à grub pour qu'il le boote :

kernel         (hd0,0)/boot/mandel

Vous trouverez les sources en pièce jointe de cet article, et en complément une image disque contenant les 2 projets avec un grub installé qui fonctionne directement sur qemu.

$ qemu image.dd

Bravo à vous !

PJ :

• asm.S
• boot.S
• compile.sh
• debug.c
• header.h
• kernel.c
• start.S
• mandel.dd

Niveau :
Résumé : C

Le C est plus lisible que le perl, la preuve le code C (test.c) suivant est valide :

%:include <stdio.h>
??=define T 2

int main(void)
??<
        int n<:T:>;

        n??(0??) = 1;
        if(n<:0??) == 1)
        <%
                n??(1:> = ??- n<:0:>;
        %> else
        <%
                n??(1??) = n<:0:> ??! 2;
        %>
        n??(0??) ??'= 3;

        printf( " n0 = %d ??/
                n1 = %d\n", n<:0:>, n<:1:> );

        return 0;
??>

Je le dis et je le prouve :

$ gcc -trigraphs test.c
$ ./a.out
 n0 = 2 		n1 = -2

Hé oui, le C contient quelques spécifications plus ou moins oubliées qui vous permettent ces bizarreries. Il s'agit en fait des trigraphs et des digraphs. Les premiers (3 caractères dont les 2 premiers sont des ?) ont été inventé pour palier un manque dans les tables de caractères pré ASCII (on me souffle qu'en fait c'est post ASCII), dont le petit nom est ISO 646. À l'époque de l'unicode ceci est toujours valable (par une option du compilateur il est vrai).

La deuxième série de caractère spéciaux (basée sur des <, >, % et :) a été introduite en 1999 ! Hé oui, la première écriture était trop peu lisible et devait être simplifiée ...

On peut ainsi créer un bug en C99 sans s'en rendre compte avant longtemps. Exemple :

int a;
a=1;
// Algo a la Kevin ?????????????????/
a++;

Exercice : Pour ceux qui suivent, trouvez la signification de chacun des groupes de caractères. Vous avez le droit à un gcc mais pas au web.

Niveau :
Résumé : cmsg_type = SCM_RIGHTS

Ne vous-êtes vous jamais posé la question de comment fait apache pour lancer des processus à l'avance tout en continuant de recevoir les connexions sur le processus père ? Les cours de programmation sur les sockets ne proposent que deux façons de coder un serveur. Vous écoutez (listen) sur un processus et à chaque nouvelle connexion d'un client (accept) vous obtenez une nouvelle socket. Ensuite, soit vous créez (fork) un nouveau processus qui communiquera uniquement avec ce client sur la socket ainsi créée, soit vous gérez toutes les sockets dans le même processus (merci select).

Bien, je vous propose de continuer à faire gérer les connexions par des processus fils, tout en lançant ceux-ci à l'avance. Pour cela, il suffit de faire en sorte qu'un processus puisse communiquer un file descriptor (ou une socket) à un autre. La solution est relativement simple si on est habitué à la gestion des sockets en C. Elle se trouve dans man 7 PF_UNIX à la section "Ancillary Messages".

Les socket unix permettent de communiquer certaines informations non communicables par le réseau. Dans notre cas, nous allons communiquer des file descriptor. Il nous faut donc une socket unix pour communiquer entre les différents processus. Vous trouverez en attaché le source pour deux programme. Le premier (listener) écoute les connexions sur le port tcp 2000, dès qu'une connexion est ouverte, il communique le fd résultant au second (worker) qui va simplement afficher un petit message. Notez que la communication passe par une socket unix (/tmp/transmit) et que listener doit être lancé en premier.

Voici un aperçu des fonctions intéressantes :

Transmission du file descriptor

void fd_transmit(int unixfd, int fd)
{
 [ ... ]
        /* on transmet le minimum de données (1 octet) 
         * pour que le message soit pris en compte */
        iov.iov_base    = &one_char;
        iov.iov_len     = 1;
        msg.msg_iov     = &iov;
        msg.msg_iovlen  = 1;

        /* on spéficie un header spécial précisant qu'on transmet une socket */
        cmsg->cmsg_level = SOL_SOCKET;
        cmsg->cmsg_len   = CONTROLLEN;
        cmsg->cmsg_type  = SCM_RIGHTS;
        *(int *)CMSG_DATA(cmsg) = fd;

        msg.msg_control = cmsg;
        msg.msg_controllen = CONTROLLEN;

        /* ce type de message doit être envoyé avec sendmsg */
        rval = sendmsg(unixfd, &msg, 0);
[ ... ]
}

Réception du file descriptor

int fd_receive(int unixfd)
{
[ ... ]
        /* on se prépare à recevoir un octet */
        iov.iov_base    = buf;
        iov.iov_len     = sizeof(buf);
        msg.msg_iov     = &iov;
        msg.msg_iovlen  = 1;

        /* on se prépare à recevoir un fd */
        msg.msg_control = cmsg;
        msg.msg_controllen = CONTROLLEN;

        /* c'est par cette fonction qu'on peut recevoir ce genre de message */
        rval = recvmsg(unixfd, &msg, 0);
[ ... ]

        /* le fd est juste derrière le cmsgheader */
        fd = *(int *)CMSG_DATA(cmsg);
        return fd;
}

Résultat

$ gcc -o listener listener.c
$ gcc -o worker worker.c

Puis dans 3 terminaux différents :

# C'est lui qui écoute sur le port 2000
$ ./listener

# C'est lui qui imprimera le message
$ ./worker

# Un client quelconque
$ nc localhost 2000
> Bonjour monde

PS : Si vous avez bien lu le manuel, vous noterez qu'il est aussi possible de vérifier un utilisateur à travers une socket unix en utilisant SCM_CREDENTIALS à la place de SCM_RIGHTS.

PPS : Au fait si vous voulez troller, dites-moi s'il y a trop ou pas assez de commentaires dans mon code ...