Cet article explore la conception et l'implémentation d'un tampon circulaire, en s'inspirant fortement de la structure kfifo du noyau Linux. L'objectif est de créer un mécanisme de stockage de données efficace et performant, particulièrement utile dans les scénarios de communication inter-processus ou de gestion de flux de données.
- Puissances de Deux et Manipulation Binaire
La structure kfifo exige que la taille du tampon soit une puissance de deux. Cela simplifie grandement les calculs d'adressage et les opérations de gestion du tampon.
Vérifier si un nombre est une puissance de deux
Une astuce courante pour vérifier si un entier positif n est une puissance de deux repose sur l'observation suivante : si n est une puissance de deux, sa représentation binaire est un 1 suivi de zéros (par exemple, 8 est 1000). Alors, n - 1 aura des 1 dans toutes les positions inférieures (par exemple, 7 est 0111). Ainsi, n & (n - 1) sera toujours zéro pour une puissance de deux.
/**
* @brief Vérifie si un entier est une puissance de deux.
*
* @param n L'entier à vérifier.
* @return true si n est une puissance de deux, false sinon.
*/
static inline bool estPuissanceDeDeux(uint32_t n) {
return (n != 0 && ((n & (n - 1)) == 0));
}
Arrondir un nombre à la puissance de deux supérieure
Si la taille du tampon fournie n'est pas une puissance de deux, il est nécessaire de l'arrondir à la puissance de deux immédiatement supérieure. Pour ce faire, on peut trouver la position du bit le plus significatif (le premier 1 à partir de la gauche) et décaler un 1 de cette position. Par exemple, pour 5 (0101), le bit le plus significatif est en position 3 (en comptant à partir de 1). Donc, 1 << 3 donne 8 (1000).
/**
* @brief Arrondit un nombre à la puissance de deux supérieure.
*
* @param a Le nombre à arrondir.
* @return La plus petite puissance de deux supérieure ou égale à a.
*/
static inline uint32_t arrondirPuissanceDeDeux(uint32_t a) {
if (a == 0) {
return 0;
}
// Trouve la position du bit le plus significatif.
// On peut utiliser des fonctions intrinsèques pour optimiser cela,
// mais une boucle simple est plus portable.
uint32_t decalage = 0;
// Recherche le bit le plus significatif
uint32_t temp = a;
while (temp >>= 1) {
decalage++;
}
// Si a n'est pas une puissance de 2 exacte, on décale d'une position supplémentaire
// pour obtenir la puissance supérieure.
if (!estPuissanceDeDeux(a)) {
return static_cast<uint32_t>(1 << (decalage + 1));
} else {
return a; // a est déjà une puissance de 2
}
}
</uint32_t>
- Analyse du
kfifodu Noyau Linux
L'implémentation du kfifo dans le noyau Linux se distingue par plusieurs aspects clés :
- Utilisation de barrières mémoire (Memory Barriers) : Permet un accès concurrentiel sans verrou (lock-free) pour un producteur et un consommateur uniques. Pour plusieurs producteurs/consommateurs, un verrouillage est nécessaire.
- Taille du tampon comme puissance de deux : Essentiel pour l'efficacité des opérations d'adressage via des masques binaires (
& (taille - 1)) qui remplacent les opérations de modulo. - Index d'entrée/sortie non signés et débordement naturel : Les index
inetoutsont des entiers non signés. Au lieu d'effectuer des opérations de modulo, on laisse les entiers déborder naturellement. La différencein - out(traitée comme un entier non signé) représente toujours la quantité de données présentes dans le tampon, même en cas de débordement.
Fonctiosn clés du kfifo :
/**
* @brief Ajoute des données dans le kfifo.
*
* @param fifo Le pointeur vers la structure kfifo.
* @param buffer Le buffer source contenant les données à ajouter.
* @param len La longueur des données à ajouter.
* @return La quantité réelle de données ajoutées.
*/
unsigned int __kfifo_put(struct kfifo *fifo, unsigned char *buffer, unsigned int len)
{
unsigned int l;
// Limite la longueur aux données qui peuvent tenir dans l'espace libre.
len = min(len, fifo->size - fifo->in + fifo->out);
/* Barre mémoire : s'assurer que fifo->out est lu avant d'écrire. */
smp_mb();
/* Copie des données depuis l'index 'in' jusqu'à la fin du tampon. */
l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
/* Copie des données restantes au début du tampon si nécessaire. */
memcpy(fifo->buffer, buffer + l, len - l);
/* Barre mémoire : s'assurer que les données sont dans le kfifo avant de mettre à jour 'in'. */
smp_wmb();
// Mise à jour de l'index d'entrée. Le débordement est géré naturellement.
fifo->in += len;
return len;
}
/**
* @brief Récupère des données du kfifo.
*
* @param fifo Le pointeur vers la structure kfifo.
* @param buffer Le buffer destination pour les données récupérées.
* @param len La longueur maximale des données à récupérer.
* @return La quantité réelle de données récupérées.
*/
unsigned int __kfifo_get(struct kfifo *fifo, unsigned char *buffer, unsigned int len)
{
unsigned int l;
// Limite la longueur aux données disponibles dans le tampon.
len = min(len, fifo->in - fifo->out);
/* Barre mémoire : s'assurer que fifo->in est lu avant de commencer la récupération. */
smp_rmb();
/* Récupération des données depuis l'index 'out' jusqu'à la fin du tampon. */
l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
/* Récupération des données restantes depuis le début du tampon si nécessaire. */
memcpy(buffer + l, fifo->buffer, len - l);
/* Barre mémoire : s'assurer que les données ont été retirées avant de mettre à jour 'out'. */
smp_mb();
// Mise à jour de l'index de sortie. Le débordement est géré naturellement.
fifo->out += len;
return len;
}
Le mécanisme de débordement naturel des entiers non signés est la partie la plus ingénieuse. L'utilisation de in & (size - 1) comme masque d'adressage, combinée au débordement, permet de gérer les transferts de données sur deux "segments" du tampon circulaire sans logique complexe de détection de fin de tampon.
- Implémentation d'un Tampon Circulaire Inspiré du
kfifo
Cette section présente une implémentation en C++ qui émule le comportement du kfifo, notamment l'utilisation du débordement naturel des entiers non signés pour la gestion des index. Les barrières mémoire pour l'accès concurrentiel ne sont pas implémentées ici pour simplifier, supposant un usage mono-producteur/mono-consommateur sans besoin de synchronisation explicite via des verrous dans ce contexte.
#include <cstdint>
#include <algorithm> // pour std::min
#include <cstring> // pour memcpy
#include <iostream> // pour les tests
// Fonctions utilitaires pour la puissance de deux (définies précédemment)
static inline bool estPuissanceDeDeux(uint32_t n) {
return (n != 0 && ((n & (n - 1)) == 0));
}
static inline uint32_t arrondirPuissanceDeDeux(uint32_t a) {
if (a == 0) return 0;
uint32_t decalage = 0;
uint32_t temp = a;
while (temp >>= 1) {
decalage++;
}
// Si a n'est pas une puissance de 2 exacte, on décale d'une position supplémentaire
if (!estPuissanceDeDeux(a)) {
return static_cast<uint32_t>(1 << (decalage + 1));
} else {
return a;
}
}
class TamponCirculaire {
private:
uint8_t* tampon_; // Le pointeur vers les données du tampon
uint32_t in_; // L'index d'entrée (produit)
uint32_t out_; // L'index de sortie (consommé)
uint32_t taille_; // La taille du tampon (doit être une puissance de deux)
public:
/**
* @brief Constructeur du TamponCirculaire.
* @param taille La taille désirée du tampon. Sera arrondie à la puissance de deux supérieure si nécessaire.
*/
TamponCirculaire(uint32_t taille) : in_(0), out_(0) {
taille_ = arrondirPuissanceDeDeux(taille);
if (taille_ == 0) {
// Gérer le cas d'une taille nulle ou invalide
taille_ = 1; // Au moins 1 pour éviter des problèmes
}
tampon_ = new uint8_t[taille_];
}
/**
* @brief Destructeur du TamponCirculaire.
*/
~TamponCirculaire() {
delete[] tampon_;
}
/**
* @brief Ajoute des données dans le tampon.
* @param donnees Le pointeur vers les données à ajouter.
* @param longueur La quantité de données à ajouter.
* @return La quantité réelle de données ajoutées.
*/
uint32_t ajouter(const uint8_t* donnees, uint32_t longueur) {
// Calcule l'espace libre disponible, en tenant compte du débordement potentiel.
// L'espace libre est `taille_ - (in_ - out_)`.
uint32_t espaceLibre = taille_ - (in_ - out_);
longueur = std::min(longueur, espaceLibre);
if (longueur == 0) {
return 0;
}
// Calcule la quantité de données qui peuvent être copiées jusqu'à la fin du tampon physique.
// L'adresse physique est calculée par `in_ & (taille_ - 1)`.
uint32_t portion1 = std::min(longueur, taille_ - (in_ & (taille_ - 1)));
// Copie la première partie des données.
memcpy(tampon_ + (in_ & (taille_ - 1)), donnees, portion1);
// Copie la deuxième partie (si elle existe) au début du tampon physique.
memcpy(tampon_, donnees + portion1, longueur - portion1);
// Met à jour l'index d'entrée. Le débordement est naturel pour les entiers non signés.
in_ += longueur;
return longueur;
}
/**
* @brief Récupère des données du tampon.
* @param destination Le pointeur vers le buffer de destination.
* @param longueur La quantité maximale de données à récupérer.
* @return La quantité réelle de données récupérées.
*/
uint32_t recuperer(uint8_t* destination, uint32_t longueur) {
// Calcule la quantité de données disponibles dans le tampon.
// La quantité de données est `in_ - out_`.
uint32_t donneesDisponibles = in_ - out_;
longueur = std::min(longueur, donneesDisponibles);
if (longueur == 0) {
return 0;
}
// Calcule la quantité de données qui peuvent être lues à partir de l'index de sortie
// jusqu'à la fin du tampon physique.
uint32_t portion1 = std::min(longueur, taille_ - (out_ & (taille_ - 1)));
// Copie la première partie des données.
memcpy(destination, tampon_ + (out_ & (taille_ - 1)), portion1);
// Copie la deuxième partie (si elle existe) depuis le début du tampon physique.
memcpy(destination + portion1, tampon_, longueur - portion1);
// Met à jour l'index de sortie. Le débordement est naturel pour les entiers non signés.
out_ += longueur;
return longueur;
}
/**
* @brief Vérifie si le tampon est vide.
* @return true si le tampon est vide, false sinon.
*/
bool estVide() const {
return in_ == out_;
}
/**
* @brief Renvoie l'espace libre restant dans le tampon.
* @return La quantité d'espace libre.
*/
uint32_t espaceRestant() const {
return taille_ - (in_ - out_);
}
/**
* @brief Renvoie la quantité de données présentes dans le tampon.
* @return La quantité de données.
*/
uint32_t longueur() const {
return in_ - out_;
}
/**
* @brief Renvoie la taille totale allouée pour le tampon.
* @return La taille du tampon.
*/
uint32_t tailleTotale() const {
return taille_;
}
};
// Exemple d'utilisation pour tester l'implémentation
int main() {
uint8_t bufferSortie[512] = { 0 };
uint8_t donneesEntree[256];
for (int i = 0; i < 256; i++) {
donneesEntree[i] = static_cast<uint8_t>(i);
}
TamponCirculaire tampon(128); // Taille initiale de 128, qui est une puissance de 2.
std::cout << "Taille du tampon allouee: " << tampon.tailleTotale() << std::endl;
// Ajout de 100 octets
uint32_t ecrit = tampon.ajouter(donneesEntree, 100);
std::cout << "Ajoute " << ecrit << " octets." << std::endl;
std::cout << "Vide: " << tampon.estVide() << std::endl;
std::cout << "Espace Restant: " << tampon.espaceRestant() << std::endl;
std::cout << "Longueur: " << tampon.longueur() << std::endl;
// Récupération de 50 octets
uint32_t lu = tampon.recuperer(bufferSortie, 50);
std::cout << "Recupere " << lu << " octets." << std::endl;
std::cout << "Vide: " << tampon.estVide() << std::endl;
std::cout << "Espace Restant: " << tampon.espaceRestant() << std::endl;
std::cout << "Longueur: " << tampon.longueur() << std::endl;
// Ajout de 30 octets
ecrit = tampon.ajouter(donneesEntree, 30);
std::cout << "Ajoute " << ecrit << " octets." << std::endl;
std::cout << "Vide: " << tampon.estVide() << std::endl;
std::cout << "Espace Restant: " << tampon.espaceRestant() << std::endl;
std::cout << "Longueur: " << tampon.longueur() << std::endl;
// Ajout de données supplémentaires qui vont provoquer un débordement de l'index 'in_'
// On ajoute 92 octets. Capacité restante = 128 - ( (100+30) - 50 ) = 128 - 80 = 48.
// Il y aura donc 48 octets ajoutés dans le premier segment et le reste (92 - 48 = 44) au début.
uint32_t ecrit2 = tampon.ajouter(donneesEntree + 10, 92); // Utilisation de donnesEntree + 10 pour varier les données
std::cout << "Ajoute " << ecrit2 << " octets." << std::endl;
std::cout << "Vide: " << tampon.estVide() << std::endl;
std::cout << "Espace Restant: " << tampon.espaceRestant() << std::endl;
std::cout << "Longueur: " << tampon.longueur() << std::endl;
// Vérification des valeurs brutes des index après débordement
// La taille du tampon est 128. Les index in_ et out_ sont des uint32_t.
// Si in_ a dépassé 2^32, il aura débordé.
// Cependant, les calculs in_ - out_ pour la longueur et espaceRestant()
// utilisent la magie des entiers non signés pour rester corrects.
// Vérifions manuellement avec des uint8_t si la taille était petite pour illustrer le débordement.
// Ici, avec uint32_t et une taille de 128, le débordement de in_ n'est pas visible dans la valeur in_,
// mais le mécanisme in_ & (taille_-1) et les calculs de différence fonctionnent toujours.
// L'exemple original utilisait des uint8_t pour in/out pour illustrer le débordement.
// En C++, les uint32_t débordent à 2^32, donc il faudrait ajouter beaucoup plus de données.
// Pour simuler le comportement, on peut observer `longueur()` et `espaceRestant()`.
uint32_t actuel_longueur = tampon.longueur();
uint32_t actuel_espace = tampon.espaceRestant();
std::cout << "---- Verification apres ajout avec potentiel debordement ----" << std::endl;
std::cout << "Vide: " << tampon.estVide() << std::endl;
std::cout << "Espace Restant: " << actuel_espace << std::endl; // Doit correspondre à la capacité vide
std::cout << "Longueur: " << actuel_longueur << std::endl; // Doit correspondre au total des données insérées moins celles récupérées.
// Vidage complet du tampon
std::cout << "\n---- Vidage du tampon ----" << std::endl;
lu = tampon.recuperer(bufferSortie, 128); // Essayer de récupérer plus que ce qu'il y a
std::cout << "Recupere " << lu << " octets." << std::endl;
std::cout << "Vide: " << tampon.estVide() << std::endl;
std::cout << "Espace Restant: " << tampon.espaceRestant() << std::endl;
std::cout << "Longueur: " << tampon.longueur() << std::endl;
// Remplissage à nouveau et test du débordement de 'in_' (si les index étaient des uint8_t)
// Avec des uint32_t, cela prendrait beaucoup plus de données pour déclencher un débordement.
// L'important est que les calculs in_ - out_ et taille_ - (in_ - out_) fonctionnent correctement.
std::cout << "\n---- Remplissage apres vidage ----" << std::endl;
ecrit = tampon.ajouter(donneesEntree, 100);
std::cout << "Ajoute " << ecrit << " octets." << std::endl;
std::cout << "Vide: " << tampon.estVide() << std::endl;
std::cout << "Espace Restant: " << tampon.espaceRestant() << std::endl; // 128 - 100 = 28
std::cout << "Longueur: " << tampon.longueur() << std::endl; // 100
return 0;
}
</uint8_t></uint32_t>
Le comportement de débordement des entiers non signés est crucial. Lorsque in_ dépasse sa valeur maximale et revient à zéro, la différence in_ - out_ (traitée comme un entier non signé) représente toujours correctement la quantité de données dans le tampon. Par exemple, si taille_ = 256 (pour des index uint8_t), out_ = 100 et in_ = 250, la longueur est 250 - 100 = 150. Si l'on ajoute 10 octets, in_ devient 260, qui déborde à 4 (260 % 256 = 4). La nouvelle différence est 4 - 100. En arithmétique non signée, cela équivaut à (2^8 - 100) + 4 = 156 + 4 = 160. Ce résultat correspond bien à la longueur attendue (150 + 10). L'utilisation de uint32_t pour les index dans l'implémentation C++ signifie qu'il faudrait insérer et lire des quantités de données énormes (de l'ordre de 4 milliards) pour observer ce débordement dans la pratique avec une taille de tampon de 128.
L'efficacité de cette approche réside dans la simplification des calculs d'indexation et la gestion implicite des cycles du tampon grâce au comportement arithmétique des entiers non signés, à condition que la taille du tampon soit une puissance de deux.