lundi 15 novembre 2010

Things learned while writing an erlang driver

  I've spent a couple of days writing an erlang binding for zfec. The binding takes the form of a driver, that is, a shared library written in C that communicates with erlang according to the defined interface.

  The reference doc was ambiguous for some points, which gets summarized here:

Q: How is the Command parameter of open_port() passed to the ErlDriverEntry .start callback ?
A: The Command is a string, and the first word (whitespace-separated) must be the name of the driver. The whole string, including the driver name, is passed to the callback.


Q: If I send a list of binaries to the port, can I expect to get every one of them separately with the outputv callback ? How does the SysIOVec struct work ?
A: NO. Small binaries, and presumably sub binaries spliced from a common one, may get merged in the resulting ErlIOVec. I've written this to iterate over an ErlIOVec. The doc defines:

typedef struct {
  int vsize;
  int size;
  SysIOVec* iov;
  ErlDrvBinary** binv;

and does not define (because it is platform-dependant, but in this case we want Unix):

typedef struct {
    char *iov_base;
    size_t iov_len;
}

size is the total byte size of the whole ErlIOVec. vsize is the number of chunks (which may not match the number of binaries in the original iolist). iov and binv both are arrays of size vsize.

binv references the parent refc binaries (so the same binary can appear twice, and you may not be interested in all its data). Use this to manipulate the refcounter of the binary if you need to keep the data around.

iov is the chunks of data you are actually interested in. The two fields should be self-explanatory :)

Q: Is it OK to define the outputv callback and not output one ?
A: yes, you will receive an IOVec with a single chunk


Q: Why does open_port seemingly randomly fail with "bad argument" ? 
A: It will if you try to open a driver that is not loaded. Now, erl_ddll is smart and remembers who loaded which driver, and will unload a driver when it is not needed anymore. If you are testing from the shell, getting an uncaught exception will terminate the shell process and start a new one, which may cause your driver to get unloaded.

Q: Why is erl_ddll:load/2 asking for a path ? What is a reasonable value to provide ?
A: According to the OTP doc, the standard way is to use code:priv_dir(app_name)

jeudi 4 novembre 2010

Changement a chaud de la configuration d'ejabberd

Depuis le 1er novembre, mon serveur jabber (qui dessert aussi swisslinux.org) dispose du client web Jappix, qui nécessite un point de service BOSH. BOSH est supporté nativement par ejabberd, mais il n'était pas activé dans la configuration .

J'aurais pu redémarrer ejabberd, mais cela aurait provoqué quelques désagréments: déconnexion temporaire de tous les membres utilisant une addresse @swisslinux.org, et déconnexion de la chat-room officielle. Heureusement, il existe un moyen très simple d'ajouter le service à chaud.

Dans la configuration de ejabberd, il existe un tuple appelé "listen", qui liste un certain nombre de "listeners". Chaque listener est responsable d'un port tcp. Par exemple, par défaut, on trouve le listener suivant:

  {5222, ejabberd_c2s, [{access, c2s}, {shaper, cs2_shaper}, starttls, {certfile, "/etc/ssl/jabber.pem"}]}

Cela signifie qu'une instance du module ejabberd_c2s (le listener pour les connexions client) écoute sur le port 5222, avec une liste particulière d'options.

Le listener requis pour BOSH, que j'avais désactivé parce que je n'utilise pas l'interface d'administration web, est le suivant:

  {5280, ejabberd_http, [http_bind]}

Le listener web est un peu particulier, puisqu'il peut écouter sur un seul port et y fournir plusieurs services sur des chemins différents. L'option http_bind active le service BOSH sur l'addresse /http-bind.

Pour ajouter ce listener à chaud, il suffit de se connecter au noeud erlang; sur ma distribution favorite, il suffit d'un simple

  hostname # ejabberdctl debug


Qui nous donne un prompt erlang:

  (ejabberd@hostname)1>

On démarre le listener supplémentaire:

    (ejabberd@hostname)1> ejabberd_listener:start_listener(5280, ejabberd_http, [http_bind]).

Et hop, ça fonctionne... plus qu'a quitter le shell erlang avec un double Ctrl-C !

mercredi 25 août 2010

shatag: un détecteur de doublons

Si vous êtes comme moi, il vous arrive fréquemment de déplacer à la main des fichiers volumineux d'un serveur à un autre. Vous n'utilisez pas encore partout un fs distribué, parce que la bande passante disponible ne le permet pas; vous avez des vieilles copies qui trainent dans les coins, et vous ne savez jamais quoi effacer lorsque vous faites le ménage, incapables de vous rappeler si vous avez déja téléchargé le fichier x ou y sur le serveur domestique.

Voici shatag, un petit script python pour inventorier des fichiers efficacement, et détecter les doublons ou la présence de fichiers identiques sur un stockage distant:

http://bitbucket.org/maugier/shatag/

Le programme calcule une somme de contrôle SHA-256 pour chaque fichier, et la met en cache dans un attribut étendu POSIX. La somme reste ainsi en cache même si le fichier est déplacé ou renommé. Une modification du fichier invalide la somme, qui peut être recalculée de manière transparente.

Un autre script permet ensuite de collecter ces sommes via ssh, et de les accumuler dans une base sqlite. Cette base peut ensuite être utilisée pour examiner le fs local, signaler les fichiers qui existent sur un serveur distant, a double ou pas !

jeudi 10 juin 2010

Monoïdes, Flèches, et Pliables: un cas particulier

Voici un joli exemple de la puissance du polymorphisme en Haskell. Le contexte est similaire au problème dit de "stream fusion": il s'agit d'effectuer en une seule passe plusieurs calculs qui demandent d'itérer sur une structure de données. L'exemple classique consiste à calculer la moyenne d'une liste:

average xs = sum xs / length xs

Cette expression est inefficace, parce que le programme va traverser la liste deux fois: une fois pour calculer le sum, une fois pour le length. Bien sur, on peut éviter le double passage en implémentant la récursion à la main:

average = uncurry (/) . foldAverage (0,0) where
    foldAverage (sum,length) [] = (sum,length)
    foldAverage (sum,length) (x:xs) = foldAverage (sum+x,length+1) xs

Ce qui a le désavantage d'être plutôt moche; exprimons le plutôt avec un fold:

average = uncurry (/) . foldl' (\(s,l) x -> (s+x,l+1)) (0,0)

Mieux, sans être extraordinaire. Observons qu'encore une fois, les deux opérations qui nous intéressent (la longeur et la somme) son associatives et admettent un neutre: nous sommes donc en présence d'un Monoid.

Coup de chance, ces deux notions qui nous intéressent sont déja dans la lib standard sous la forme du wrapper Sum, qui transfome n'importe quel Num en Monoid sous l'addition. Mieux: il existe une instance

(Monoid a, Monoid b) => Monoid (a,b)

Qui fait ce que vous pensez: appliquer deux mappend ou mconcat en parallèle.

Pour calculer notre moyenne, commençons par mapper chaque élément de la liste vers une paire de Monoids additifs, effectuons le concat, et il restera la division finale:

average = (\(s,l) -> getSum s / getSum l) . mconcat . map (\x -> (Sum x, Sum 1))

Encore un peu trop verbeux à mon goût: les lambdas peuvent être éliminés grâce aux combinateurs de flèches:

import Control.Arrow
average = uncurry (/) . (getSum *** getSum)
        . mconcat . map (Sum &&& (Sum.const 1))

Cette fois-ci, nous sommes PointFree, un progrès apréciable. Mais nous pouvons encore améliorer les choses. Par exemple, et si nous généralisions la fonction à d'autres types de données (arbres, arrays, ...)

Nous avons utilisé mconcat, qui n'est autre qu'un fold de mappend. Si nous disposons d'un fold générique pour une structure de données, nous pouvons généraliser. Il existe une classe à ce dessein, la classe Foldable. La définition minimale d'un type Foldable consiste en une seule fonction:

instance Foldable t where
    foldMap :: (Monoid m) => (a  -> m) -> t a -> m

Qui applique une fonction (a->m) au contenu de la structure pour obtenir un Monoid, sur lequel on appelle mappend. Passer par un Monoid garantit que l'opération est associative, ce qui permet dans certains cas d'explorer la structure très efficacement (sujet d'un prochain article).

Evidemment, par défaut les Lists sont Foldable, et nous pouvons donc réécrire average en utilisant Foldable:

average = uncurry (/) . (getSum *** getSum) . foldMap (Sum &&& (Sum.const 1)

Pour la petite histoire: Il existe deux wrappers Bool, les Monoids And et Or, qui utilisent respectivement (&&) et (||) comme opération. Ceci permet d'écrire très simplement une fonction pour controler en une passe si un ensemble de Booléens ne contient que des True, que des False, ou un mix des deux:

alltruefalse = (getAny *** getAll) . foldMap (Any &&& All)

Cette expression est équivalente à  (or &&& and), avec l'avantage de calculer les deux folds en une seule passe....

   ... ou pas. Cette fonction est en réalité complètement stupide pour deux raisons:

  1. La définition du Monoid sur les tuples est trop stricte, et force l'itération de la liste jusqu'a la fin, même en présence de deux folds paresseux et court-circuités. Ce qui nous amène au point suivant,
  2. or et and sont court-circuités par défaut, et au moins un de ces deux terminera son évaluation immédiatement après le 1er élément (Si le premier élément est True, or retourne True, sinon and retourne False). La fusion des folds n'a donc aucun intérêt dans ce cas particulier !

Haskell, c'est concis !

Considérez le problème de la rotation d'une liste: On dispose d'une liste xs de longueur inconnue, on souhaite effectuer une rotation de n positions (déplacer n éléments du début à la fin.) Faisons une tentative d'implémentation en Haskell, tout a fait normale, en utilisant la récursion sur n:

rotate 0 xs = xs 
rotate n (x:xs) = rotate (n-1) (xs ++ [x])

C'est bien connu, le ++[x] est très loin d'être efficace (Les listes sont simplement chainées, et immutables, ce qui implique une réallocation complète de l'argument à gauche, donc ici O(l*n) allocations).

Sacrifions un peu de généralité pour une meilleure implémentation (mais qui n'accepte pas de n supérieur à la taille de la liste):

rotate n xs = (drop n xs) ++ (take n xs)

take est une fonction de la librairie standard qui retourne les n premiers éléments d'une liste, tandis que drop retire ces mêmes n premiers éléments.

Concis ? pas encore assez. Intéressons-nous à une classe souvent sous-estimée, le Monoid, dont voici la définition:

class Monoid m where
    mzero :: m
    mappend :: m -> m -> m
    mconcat :: [m] -> m
    mconcat = foldr mappend mzero

Rien d'extraordinaire ici, la classe Monoid regroupe les types pour lesquels il existe une opération naturelle associative, mappend, et un élément neutre des deux côtés, mzero.  Quant à mconcat, c'est une fonction de convenance dont la définition par défaut est donnée.

Il existe beaucoup d'exemples de Monoids; on peut citer les nombres entiers dans deux contextes différents (addition et multiplication), le type Ordering (pour décrire un ordre hiérarchique), mais plus simplement: les listes !

Dans le cas des listes, on à simplement
instance Monoid [a] where
    mzero = []
    mappend = (++)
    mconcat = concat

Comme les Monoids sont fort utiles, on peut généraliser le sens de (++) et de concat à tous les Monoids (c'est d'ailleurs le cas en Caleskell):

import Prelude hiding ((++), concat)
import Data.Monoid

(++) = mappend
concat = mconcat

Ceci nous permet donc d'utiliser (++) sur n'importe quel Monoid, et pas seulement sur les listes.


Voyez-vous ou tout ceci nous mène ? Probablement pas encore, sauf si vous
connaissez l'existence de l'instance suivante (dans la librairie standard):

instance Monoid a => Monoid (t -> a)
 
dont l'implémentation est laissée comme un exercice au lecteur ;)

Traduction: si les listes [a] forment un Monoid, les fonctions (t -> [a]) en forment également un ! ce qui me permet par exemple de remplacer la définition

f x = g x ++ h x

par une plus concise:

f = g ++ h

A condition que x soit d'un type appartenant à la classe Monoid.

Encore plus fort, notre instance est récursive ! en effet, on à

instance Monoid b => Monoid (t' -> b)

(on a juste renommé les variables de type).

Posons b = (t -> a),  on a alors Monoid a => Monoid b, qui se dérive en

instance Monoid a => Monoid (t' -> (t -> a))

C'est exact, le truc fonctionne également sur les fonctions à plus d'un argument ! Ce qui nous permet de simplifier immédiatement

rotate n xs = (drop n xs) ++ (take n xs)

en

rotate = drop ++ take

Si ça c'est pas de la concision...

lundi 25 janvier 2010

Lîlarfikod, "Patternglazed"

Journal d'Ushat Olonkulal, Maire de Lîlarfikod - le 12e Hématite 214.

  Une dizaine d'années se sont écoulées depuis le premier coup de pioche, porté dans le flanc de la montagne par l'un des septs vaillants nains fondateurs. Jadis hameau perdu au milieu des montagnes, Lîlarfikod est aujourd'hui une métropole florissante. le Duc Kandzudmeng en a fait sa capitale régionale, et une rumeur voudrait que la Reine Inod elle-même y considère l'installation de son palais d'hiver.

  La situation extérieure est au beau fixe; le commerce avec les humains est plus lucratif que jamais, et les kobolds se terrent dans les montagnes après le massacre de leurs troupes pendant le dernier siège. Même ces pleurnichards d'elfes nous sont reconnaissants d'avoir limité l'abattage des arbres. Bah. Comme si le bois présentait un quelconque intérêt face a la pierre. Mais je m'égare.

  Non, décidément, c'est la forteresse elle-même qui nous cause le plus d'inquiétude. Il y a six mois, l'équipe de minage sud-est, creusant à la poursuite d'une veine d'argent natif, détectait un secteur de roche anormalement humide. Quelques mètres de plus, et les vaillants mineurs exposaient une immense rivière souterraine, à la présence jusque la totalement insoupçonnée. Voici donc l'origine des rumeurs de monstres aquatiques hantant les sous-sols de cette région !

  Suivant l'ouverture du tunnel, nous essuyâmes une attaque d'hommes-lézards armés jusqu'au dents. L'attaque couta la vie à deux de nos meilleurs soldats, noyés d'épuisement après avoir combattu a mains nues et étranglé une dizaine d'assaillants. Un brave maçon, au péril de sa vie, parvint à murer le dangereux orifice, scellant le péril hors du périmètre du fort.

  Nos ingénieurs ayant estimé le tracé de la rivière, je démarrai immédiatement la construction de fortifications en différents points stratégique autour du cours d'eau, et y installai une troupe de nos meilleurs
arbalétriers. La rivière rougit bientôt du sang de nos ennemis tombés !

  L'humidité de la rivière souterraine fertilise nos tunnels, et mes nains me signalent que des champignons Chapeaux-de-Tours poussent un peu partout. Ces champignons, en vieillissant, acquièrent la dureté et la texture du bois. Nous allons creuser une immense ferme souterraine et les y cultiver; voila qui dispensera nos bûcherons de s'exposer au soleil, et devrait par la même calmer les humeurs des bouffeurs de baies des bois.

  Cette rivière nous apporte un deuxième avantage, celui de nous débarasser bien plus facilement de nos ordures. J'ai fait creuser une cheminée d'accès, descendant des niveaux principaux jusqu'au gouffre souterrain dans lequel se jette la rivière. Nos concitoyens peuvent maintenant évacuer leurs déchets sans s'aventurer dans les dangereux territoires extérieurs !

  En revanche, toujours rien d'intéressant du côté de l'équipe de minage ouest, chargée d'explorer les veines d'obsidienne à la recherche de magma. En dix ans, nous n'avons pas trouvé une seule veine de houille dans la région, et notre industrie métallurgique dépend entièrement du charbon de bois, ce qui n'est pas pour plaire aux clowns aux oreilles pointues.

  Les lubies du Duc nous causent également des ennuis. Ce fils de yack des montagnes a ordonné que la ville développe une industrie du verre, pour lui fournir de la vaisselle de luxe. Nous n'avons pas les ressources nécessaire pour en produire, et le temps que le message parviennent à nos voisins marchands, qui sait si le vieux fou n'aura pas perdu patience. La dernière fois que nous avons raté un délai (une commande fantaisiste de 12 armoires en electrum), il a condamné a mort l'artisan fautif, notre meilleur forgeron.

  Notre meilleure chance reste de convaincre la Reine de venir s'installer dans notre forteresse, et prions qu'elle puisse modérer les excès d'autorité du Duc. Nous allons donc nous atteler à une tâche titanesque: percer la montagne de part en part, pour permettre aux caravanes de traverser en toute sécurité en évitant le dangereux col, propice aux embuscades gobelines. L'entrée du tunnel est terminée, mais nous devons terminer les fortifications intérieures avant de creuser le tunnel principal; sans quoi nos ennemis auront une voie royale pour contourner toutes nos défenses et nous envahir de l'intérieur.

  Mais voila que la délégation diplomatique Elfe frappe à nos portes, et je me dois d'aller les acueillir. Encore une dure journée dans la vie d'un vieux bureaucrate nain...