Aller au contenu | Aller au menu | Aller à la recherche

/var/log/iksaif

mercredi, mars 18 2009

Coccinelle: Patchs sémantiques

Je viens de découvrir coccinelle, et c'est vraiment un outil sympa.

Imaginez que vous voulez remplacer tout les expr ? 1 : 0 par des !!expr. Et bah avec coccinelle rien de plus simple :

test.cocci

@@ expression cond; @@
 
- cond ? 1 : 0
+ !!cond
 
@@ expression cond; @@
 
- (!!cond)
+ !!cond

test.c

int main(void)
{
  int val;
 
  val = val ? 1 : 0;
  printf("%d", val);
  printf("%d", val ? 1 : 0);
  printf("%d", (val ? 1 : 0));
}

$ spatch -sp_file test.cocci test.c

--- test.c      2009-03-18 11:06:17.000000000 +0100
+++ /tmp/cocci-output-14620-bafaae-test.c       2009-03-18 11:21:17.000000000 +0100
@@ -2,8 +2,8 @@ int main(void)
 {
   int val;
 
-  val = val ? 1 : 0;
+  val = !!val;
   printf("%d", val);
-  printf("%d", val ? 1 : 0);
-  printf("%d", (val ? 1 : 0));
+  printf("%d", !!val);
+  printf("%d", !!val);
 }

Donc vachement pratique pour changer des trucs quand un search&replace ne suffit pas ! Plus d'informations:

dimanche, février 1 2009

UFFS Website

UFFS Website is now open at http://uffs.org/. You'll find news, documentation, etc ...

NandFS git tree will also probably be opened this week at git.iksaif.net. I'll post some mails on linux mailing-lists.

samedi, décembre 27 2008

Sphinx: Faire un moteur de recherche en PHP/(MySQL|PostgreSQL)

Cet article s'adresse à ceux qui auraient une (grosse) base de donnée, et qui aimeraient disposer d'un moteur de recherche rapide et performant. Une première solution est d'utiliser les index full text et de chercher directement dans la base en faisant des requêtes SQL. Cette solutions présente des avantages certains, mais aussi les désavantages suivants:

  • La taille de l'index peut rapidement devenir très importante
  • L'index peut ralentir les insertions (les insertions lockent la table sous MySQL !)
  • Les fonctions mises à dispositions par MySQL (ou PostgreSQL) en matìere de recherche full-text sont assez limitées.
  • Il faut refaire soit même le moteur de recherche qui va créer les requètes SQL

Sphinx

Sphinx

A Propos

Sphinx est un moteur de recherche full-text, distribué sous GPL v2. (Une licence commerciale est disponible)

En gros, c'est un moteur de recherche à part entière, crée pour fournir des fonctions de recherches rapides et pertinentes pour d'autres applications. Sphinx a été fait en particulier pour s'intégrer facilement avec des base de données SQL et des languages de scripts (typiquement, le couple PHP/MySQL). Pour l'instant les sources de données peuvent être des bases de donnée MySQL ou PostgreSQL, mais aussi des flux XML.

Sphinx signifie SQL Phrase Inde_x__

Programmes

  • indexer: un utilitiaire pour créer les index
  • search: a simple utilitaire (de test) pour rechercher en ligne de commandes
  • searchd: un service pour faire des recherches en utilisant sphinxapi
  • sphinxapi: un ensemple d'acpi pour les languages les plus utilisés PHP, Python, Java, Perl et Ruby.

Avantages

  • Indexation assez rapide (sur mes machines, à peu près 2000 docs/sec)
  • Support de plusieurs langues, y compris CJK
  • Il est facile de mettre le moteur de recherche sur une (voir plusieurs) machine différente et ainsi mieux répartir la charge
  • API PHP, Python, Java, Perl, et Ruby

Articles

Les articles en italique ne sont pas encore publiés

  • Configuration de base
  • Indexation
    • Indexation basique
    • Utilisation des range queries
    • Diminuer la charge du processus d'indexation: utilisation d'un index "delta"
    • Gestion de plusieurs langues
  • Tests avec l'utilitaire search
  • Utilisation de l'API PHP
  • Utilisation de l'API Python

lundi, novembre 24 2008

Fetchmail, Procmail, Bogofilter et imapd

Voila un billet qui sera sûrement utile à certains, vu que ça l'a été à William.

Comme moi, vous avez sûrement au moins une dizaine de compte mail, et vous voudriez bien.

Cet article vous permettra de centraliser tout vos mails, et d'y accéder via imap, ou via un webmail de votre choix.

Tout ce qu'il vous faudra, c'est un serveur, idéalement sous Gentoo.

L'idée c'est que fetchmail va télécharger les mails, puis les passer à procmail qui s'occupera de les ranger au bon endroit suivant des règle que vous lui préciserez. Et pour y accéder, un serveur imap ira lire tout ça.

Logiciels à installer

emerge ou apt-get sont vos amis:

  • fetchmail
  • procmail
  • bogofilter
  • courier-imap
  • roundcube ou squirrelmail

Récupérer les mails: Fetchmail

Il suffit de configurer correctement fetchmail avec le fichier .fetchmailrc

poll mail.iksaif.net
    protocol pop3
    username "bidule@iksaif.net"
    password "xxxx"
    nokeep
    mda "/usr/bin/procmail -d %T"

Pour un compte gmail, je vous invite à aller voir cette page http://download.gna.org/hpr/fetchmail/FAQ/gmail-pop-howto.html.

Ranger les mails: Procmail

Voila de quoi remplir votre fichier ~/.procmailrc (avec de nombreux exemples ;) ). Attention à bien régler le paramètre MAILDIR !

# caractère verbeux de procmail ; mettre 'yes' permet d'avoir des messages
# supplémentaires
VERBOSE=yes
 
# mettre /bin/sh surtout si vous utilisez tcsh !
SHELL=/bin/sh
 
# chemin d'accès aux excutables ; en mettre le minimum, pour n'accèder qu'aux
# programmes indiqus dans le fichier de configuration
PATH=/bin:/usr/bin:/usr/local/bin
 
# rpertoire o seront stocks les mails ; s'assurer que votre MUA sait y
# accder aussi
MAILDIR=/home/iksaif/.maildir
 
# si procmail n'arrive pas  dlivrer le courrier, cette bote sera utilise
# en dernier ressort : il vaut mieux dfinir cette variable !
#ORGMAIL=$MAILDIR/.emergency-inbox
 
# bote de rception par dfaut
#DEFAULT=/home/iksaif/.maildir
 
# fichier de log de procmail ; si vous dfinissez cette variable,
# procmail gardera une trace de son excution dans le fichier
# indiqu.  consulter priodiquement !
 
:0
* ^X-Mailing-List:.*linux-ide@vger.kernel.org
:0
* acpi4asus
.Mailing-List.Linux.acpi4asus/
 
:0
* eee
.Mailing-List.Linux.eeepc/
 
:0
* ^(To|Cc|Cci).*(zordania.com)
.Boulot.Zordania/
 
:0
* ^(To|Cc|Cci).*(pouet@epitech.net)
.Epitech/
 
:0
* ^(To|Cc|Cci).*(pouet@iksaif.net)
.Mobile/
 
# Tout ce qui n'a pas t tri jusqu'ici va dans la mailbox principale "inbox"
:0
.Bordel/

Maintenant que fetchmail et procmail sont configuré, il est possible de récupérer ses mails avec la commande "fetchmail". Mais on a toujours rien pour les lire !

Filtrer les mails: Bogofilter

Un antispam, c'est toujours pratique, on va donc utiliser bogofilter. Pourquoi bogofilter ? Parce qu'il marche bien et qu'il est simple. Voila les règles à ajouter dans ~/.procmailrc (après DEFAULT=....). Cette configuration nécessite quatres dossiers :

  • Junk - Vrais spam
  • Junk/Unsure - Spams probables
  • Junk/New - Ici on copie les messages qui sont des spams et qui n'ont pas été détectés
  • Junk/False - Ici on copie les spam qui en fait n'en étaient pas
# Utilisation de bogofilter, à commenter si bogofilter n'est pas installé
:0fw
| bogofilter -u -e -p
:0e
{ EXITCODE=75 HOST }
# Si c'est un spam il va dans le dossier Junk
:0:
* ^X-Bogosity: (Spam|Yes)
.Junk/
 
# Si on est pas sur, il va dans le dossier Junk.Unsure
:0:
* ^X-Bogosity: Unsure
.Junk.Unsure/
# Fin bogofilter

Maintenant, on va rajouter de quoi apprendre à bogofilter à reconnaître les spams. Voila un petit script shell qui fera l'affaire.

#!/bin/bash
MAILDIR=/home/iksaif/.maildir
 
if [ -z `echo $MAILDIR/.Junk.New/*/* |grep '/\*/\*'` ] ; then
    for spam in $MAILDIR/.Junk.New/*/*; do
        bogofilter -Ns -I "${spam}" -p -O "${MAILDIR}/.Junk/cur/`basename ${spam}`"
        rm $spam
    done
fi
 
if [ -z `echo $MAILDIR/.Junk.False/*/* |grep '/\*/\*'` ] ; then
    for mail in $MAILDIR/.Junk.False/*/*; do
        bogofilter -Sn -I "${mail}" -p -O "${MAILDIR}/.Bordel/cur/`basename ${mail}`"
        rm "${mail}"
    done
fi

Automatiser tout ça avec des crons

Hop, pour lancer le tout toutes les 5 minutes.

$ crontab -e
*/5 * * * * fetchmail &> ~/fethmail.log
*/5 * * * * sh ~/bogofilter.sh &> /dev/null

Accéder aux mails: courrier-imapd

Bon maintenant que tout est bon, on aimerait bien accéder à nos mails ! Il suffit d'installer le serveur imap courrier. Pour dans le fichier /etc/courier-imap/imapd vérifier que ces valeurs sont les bonnes :

# Hardwire a value for ${MAILDIR}
MAILDIR=.maildir
MAILDIRPATH=.maildir

Maintenant on le lance, et hop, on peut lire ses mails avec son client préféré.

Un webmail: roundcube

Une autre solution peut être d'installer un webmail. roundcube est simple à installer et assez joli. Normalement l'installation ne devrais pas vous poser de problème, et au pire, y'a les fichiers INSTALL et README ;).

mercredi, octobre 15 2008

simple malloc 0.1

Tout le monde (enfin .... presque) connaît la fonction malloc dans la bibliothèque standard. Mais beaucoup se demandent comment recoder cette fonction, comment allouer de la mémoire sans malloc ?

Note: Cet article est un peu dépassé, les dernière versions se trouvent sur http://git.iksaif.net

Allocation de mémoire

brk - man

 brk()  positionne  la fin du segment de données (le premier mot mémoire
 hors de la zone accessible) à l’adresse spécifiée par end_data_segment.
 Cette  valeur doit être raisonnable, le système doit avoir suffisamment
 de mémoire, et le processus ne doit pas dépasser sa taille maximale  de
 segment de données (voir setrlimit(2)).

 sbrk() incrémente l’espace de données du programme de increment octets.
 sbrk() n’est pas un appel  système,  juste  une  fonction  de  la  bib‐
 liothèque  C.  Appeler  sbrk()  avec  un incrément nul permet d’obtenir
 l’emplacement de la limite actuelle.
 Si elle réussit, la fonction brk() renvoie zéro. En cas d’erreur,  elle
 renvoie  -1  et  remplit errno avec la valeur d’erreur (voir la section
 NOTES SUR LINUX ci‐dessous).

 sbrk() retourne un pointeur  sur  le  début  de  la  nouvelle  zone  de
 données.  En  cas  d’échec  -1  est  renvoyé, et errno contient le code
 d’erreur ENOMEM.

mmap - man

Voir la manpage, mais de toute façon mon implémentation actuelle utilise brk/sbrk. Le mieux serait d'utiliser mmap, et ça sera fait dans une prochaine version.

Implémentation

Simple

Un implémentation simple consiste à faire une liste chaînée de tout les bouts de mémoires alloués lors d'un malloc. une utilise une structure de ce type:

struct s_chunk
{
   struct s_chunk *prev;
   size_t size;
   bool used;
};

Lors de chaque appel à malloc(size), on appelle sbrk(sizeof(s_chunk) + size). On utilise les sizeof(s_chunk) premier bit pour la structure utilisée dans la liste chaînée. Le reste est le bout de mémoire qu'on peut donner à l'application. Lors d'un free, il suffit de marquer used à false. Il est ainsi possible de parcourir la liste à la recherche d'un bout de bonne taille avant d'allouer encore plus de mémoires.

En gros, ça nous donne:

static t_chunk *list = NULL;
void *malloc(size_t size)
{
   s_chunk *chunk = sbrk(sizeof(*chunk) + size);
 
   chunk->size = size;
   chunk->prev = NULL;
   chunk->used = true;
   if (list)
     list->prev = chunk;
   list = chunk; 
   return chunk + 1; 
 }
void free(void *p)
{
   t_chunk *chunk = p;
   chunk -= 1;
   chunk->used = false;
}

Bon, cette approche est plutôt simple mais pose plusieurs problème. Tout d'abord la mémoire n'est pas alignée, mais pour ça il suffirais que t_chunk soit une structure dont la taille est une puissance de sizeof(long). Mais surtout, on à beaucoup de fragmentation, et la recherche de bout de bonne taille est très lente. Enfin la mémoire n'est jamais retournée au système.

Afin d'améliorer un peu les performances, il est possible d'utiliser juste une liste pour les bouts non utilisés, ce qui réduira la taille de la liste. Mais la complexité sera encore en O(n).

Mon choix

Avec encore plus de listes

J'utilise deux constantes

# define MALLOC_SHIFT_LOW       1
# define MALLOC_SHIFT_HIGH      10

La solution que j'ai adoptée comporte une liste de tout les bouts (nécessaires pour split/fusion, voir après) et 2^10+1 liste de morceaux libres. La taille des bouts est compté en sizeof(t_chunk) et non en bytes.

  • Tout les bouts dont la taille est plus petite que 2^MALLOC_SHIFT_LOW sont rangés ensembles.
  • Tout les bouts dont la taille est plus grande que 2^MALLOC_SHIFT_HIGH sont rangés ensembles.
  • Les autres bouts sont rangés avec leurs copains de puissance de 2 similaire (ou la puissance est entre MALLOC_SHIFT_LOW et MALLOC_SHIFT_HIGH).

split/fusion

Si on ne trouve pas de morceau alloué de la bonne taille, on en choisis un tros grand, et on le coupe en deux. La deuxième partie restera ainsi dans la liste des bouts libres. Lorsqu'on libère un morceau, si c'est possible, on le fusionne avec les bouts adjacents libres. C'est là que la liste de tout les bouts est nécessaire car elle garde les bouts dans l'orde dans le quel ils ont été alloués. Il est ainsi possible de retrouver très facilement les bouts adjacent.

Utilisation

Pour utiliser ce malloc dans vous programmes sans les recompiler (ça à très peut d'interêt, mais bon) vous pouvez utiliser le script mallocize.sh présent dans l'archive. En gros ça revient à rajouter le chemin de la lib dans la variable d'environement LD_PRELOAD.

Il est aussi possible de bidouiller le tout pour compiler vos programmes avec.

Télécharger

malloc-0.1.tar.gz

Liens