Licence CC 0

T.P. : un allocateur statique de mémoire

Dernière mise à jour :

Dans ce dernier chapitre, nous allons mettre en œuvre une partie des notions présentées dans cette partie afin de réaliser un allocateur statique de mémoire.

Objectif

Votre objectif sera de parvenir à réaliser un petit allocateur statique de mémoire en mettant en œuvre deux fonctions : static_malloc() et static_free() comparables aux fonctions malloc() et free() de la bibliothèque standard. Toutefois, afin d’éviter d’entrer dans les méandres de l’allocation dynamique de mémoire, ces fonctions fourniront de la mémoire préalablement allouée statiquement.

Première étape : allouer de la mémoire

Pour commencer, vous allez devoir construire une fonction static_malloc() dont le prototype sera le suivant.

1
void *static_malloc(size_t taille);

À la lumière de la fonction malloc(), celle-ci reçoit une taille en multiplet et retourne un pointeur vers un bloc de mémoire d’au moins la taille demandée ou un pointeur nul s’il n’y a plus de mémoire disponible.

Mémoire statique

Afin de réaliser ses allocations, la fonction static_malloc() ira piocher dans un bloc de mémoire statique. Celui-ci consistera simplement en un tableau de char de classe de stockage statique d’une taille prédéterminée. Pour cet exercice, nous partirons avec un bloc de un mébimultiplets, soit 1.048.576 multiplets (1024 × 1024).

1
static char mem[1048576UL];

Alignement

Toutefois, retourner un bloc de char de la taille demandée ne suffit pas. En effet, si nous allouons par exemple treize multiplets, disons pour une chaîne de caractères, puis quatre multiplets pour un int, nous allons retourner une adresse qui ne respecte potentiellement pas l’alignement requis par le type int. Étant donné que la fonction static_malloc() ne connaît pas les contraintes d’alignements que doit respecter l’objet qui sera stocké dans le bloc qu’elle fourni, elle doit retourner un bloc respectant les contraintes les plus strictes. Dit autrement, la taille de chaque bloc devra être un multiple de l’alignement le plus rigoureux.

Cet alignement peut être connu à l’aide d’une union comprenant les types les plus contraignants et de la macrofonction offsetof(), comme précisé dans le chapitre sur les unions.

1
2
3
4
5
6
union align
{
    long e;
    long double f;
    void *p;
};

Mais… ce n’est pas tout ! Le tableau alloué statiquement doit lui aussi être aligné suivant l’alignement le plus sévère. En effet, si celui-ci commence à une adresse non multiple de cet alignement, notre stratégie précédente tombe à l’eau. Pour ce faire, il nous suffit d’inclure le tableau dans une union avec comme autre membre l’union décrite ci-dessus.

1
2
3
4
5
6
7
union reserve
{
    union align align
    char mem[1048576UL]
};

static union reserve reserve;

Avec ceci, vous devriez pouvoir réaliser la fonction static_malloc() sans encombre.
Hop hop ! Au travail ! :)

Correction

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <assert.h>
#include <stddef.h>
#include <stdio.h>

#define MEM_SIZE (1024UL * 1024UL)
#define ALIGNEMENT(type) (offsetof(struct { char c; type t; }, t))

union align
{
    long e;
    long double f;
    void *p;
};

union reserve
{
    union align align;
    char mem[MEM_SIZE];
};

static union reserve reserve;

static size_t calcule_multiple_align(size_t);
static void *static_malloc(size_t);


static size_t calcule_multiple_align(size_t a)
{
    /*
     * Calcule le plus petit multiple de l'alignement maximal égal ou supérieur à `a`.
     */

    static size_t align_max = ALIGNEMENT(union align);
    size_t multiple = a / align_max;

    return ((a % align_max == 0) ? multiple : multiple + 1) * align_max;
}


static void *static_malloc(size_t taille)
{
    /*
     * Alloue un bloc de mémoire au moins de taille `taille`.
     */

    static size_t alloue = 0UL;
    void *ret;

    assert(taille > 0);
    taille = calcule_multiple_align(taille);

    if (MEM_SIZE - alloue < taille)
    {
        fprintf(stderr, "Il n'y a plus assez de mémoire disponible.\n");
        return NULL;
    }

    ret = &reserve.mem[alloue];
    alloue += taille;
    return ret;
}

La fonction calcule_multiple_align() détermine le plus petit multiple de l’alignement maximal égal ou supérieur à a. Celle-ci nous permet d’« arrondir » la taille demandée de sorte que les blocs alloués soit toujours correctement alignés.

La macrofonction ALIGNEMENT() calcule l’alignement d’un type donné en recourant à la macrofonction offsetof() comme expliqué précédemment.

La fonction static_malloc() utilise une variable statique : alloue qui représente la quantité de mémoire déjà allouée. Dans le cas où la taille demandée (arrondie au multiple de l’alignement qui lui est égal ou supérieur) n’est pas disponible, un pointeur nul est retourné. Sinon, la variable alloue est mise à jour et un pointeur vers la position courante du tableau reserve.mem est retourné.

Notez que nous avons utilisé une assertion afin d’éviter qu’une taille nulle ne soit fournie.

Deuxième étape : libérer de la mémoire

Pouvoir allouer de la mémoire, c’est bien, mais pouvoir en libérer, ce serait mieux. Parce que pour le moment, dès que l’on arrive à la fin du tableau, que la mémoire précédemment allouée soit encore utilisée ou non, c’est grillé. :-°

Toutefois, pour mettre en place un système de libération de la mémoire, il va nous falloir changer un peu de tactique.

Ajout d’un en-tête

Tout d’abord, si nous voulons libérer des blocs puis les réutiliser, il nous faut conserver d’une manière ou d’une autre leur taille. En effet, sans cette information, il nous sera impossible de les réaffecter.

Pour ce faire, il nous est possible d’ajouter un en-tête lors de l’allocation d’un bloc, autrement dit un objet (par exemple un entier de type size_t) qui précédera le bloc alloué et contiendra la taille du bloc.

1
2
3
+---------+-----------------+
| En-tête |   Bloc alloué   |
+---------+-----------------+

Ainsi, lors de l’allocation, il nous suffit de transmettre à l’utilisateur le bloc alloué sans son en-tête à l’aide d’une expression du type (char *)ptr + sizeof (size_t) et, à l’inverse, lorsque l’utilisateur souhaite libérer un bloc, de le récupérer à l’aide d’une expression comme (char *)ptr - sizeof (size_t). Notez que cette technique nous coûte un peu plus de mémoire puisqu’il est nécessaire d’allouer le bloc et l’en-tête.

Les listes chaînées

Mais, ce n’est pas tout. Pour pouvoir retrouver un bloc libéré, il nous faut également un moyen pour les conserver et en parcourir la liste. Afin d’atteindre cet objectif, nous allons employer une structure de donnée appelée une liste chaînée. Celle-ci consiste simplement en une structure comprenant des données ainsi qu’un pointeur vers une structure du même type.

1
2
3
4
struct list
{
    struct list *suivante;
};

Ainsi, il est possible de créer des chaines de structure, chaque maillon de la chaîne référencant le suivant. L’idée pour notre allocateur va être de conserver une liste des blocs libérés, liste qu’il parcourera en vue de rechercher un bloc de taille suffisante avant d’allouer de la mémoire provenant de la réserve. De cette manière, il nous sera possible de réutiliser de la mémoire précédemment allouée avant d’aller puiser dans la réserve.

Nous aurons donc a priori besoin d’une liste comprenant une référence vers le bloc libéré et une référence vers le bloc suivant (il ne nous est pas nécessaire d’employer un membre pour la taille du bloc puisque l’en-tête la contient).

1
2
3
4
5
struct bloc
{
    void *p;
    struct bloc *suivant;
};

Le serpent qui se mange la queue

Cependant, avec une telle technique, nous risquons d’entrer dans un cercle vicieux. En effet, imaginons qu’un utilisateur libère un bloc de 64 multiplets. Pour l’ajouter à la liste des blocs libérés, nous avons besoin d’espace pour stocker une structure bloc, nous allons donc allouer un peu de mémoire. De plus, si par la suite ce bloc est réutilisé, la structure bloc ne nous est plus utile, sauf que si nous la libérons, nous allons devoir allouer une autre structure bloc pour référencé… une structure bloc (à moins que la structure ne s’autoréférence). Voilà qui n’est pas très optimal.

À la place, il nous est possible de recourir à une autre stratégie : inclure la structure bloc dans l’en-tête ou, plus précisémment, son champ suivant, la référence vers le bloc n’étant plus nécessaire dans ce cas. Autrement dit, notre en-tête sera le suivant.

1
2
3
4
5
struct bloc
{
    size_t taille;
    struct bloc *suivant;
};

Lors de la libération du bloc, il nous suffit d’employer le champ suivant de l’en-tête pour ajouter le bloc à la liste des blocs libres.

1
2
3
4
5
6
7
8
       En-tête                                          En-tête
<------------------->                            <------------------->
+---------+---------+-----------------+          +---------+---------+-----------------+
| Taille  | Suivant |   Bloc alloué   |          | Taille  | Suivant |   Bloc alloué   |
+---------+---------+-----------------+          +---------+---------+-----------------+
               +                                 ^
               |                                 |
               +---------------------------------+

Étant donné que l’en-tête précède le bloc alloué, il est impératif que sa taille soit « arrondie » de sorte que les données qui seront stockées dans le bloc respectent l’alignement le plus strict.

Avec ceci, vous devriez pouvoir réaliser une fonction static_free() et modifier la fonction static_malloc() en conséquence. ;)

Correction

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <assert.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

#define MEM_SIZE (1024UL * 1024UL)
#define ALIGNEMENT(type) (offsetof(struct { char c; type t; }, t))
#define TAILLE_EN_TETE (offsetof(struct { struct bloc b; union align u; }, u))

union align
{
    long e;
    long double f;
    void *p;
};

union reserve
{
    union align align;
    char mem[MEM_SIZE];
};

struct bloc
{
    size_t taille;
    struct bloc *suivant;
};


static union reserve reserve;
static struct bloc *libre;

static void bloc_init(struct bloc *, size_t);
static size_t calcule_multiple_align(size_t);
static struct bloc *recherche_bloc_libre(size_t);
static void static_free(void *);
static void *static_malloc(size_t);


static void bloc_init(struct bloc *b, size_t taille)
{
    /*
     * Initialise les membres d'une structure `bloc`.
     */

    b->taille = taille;
    b->suivant = NULL;
}


static size_t calcule_multiple_align(size_t a)
{
    /*
     * Calcule le plus petit multiple de l'alignement maximal égal ou supérieur à `a`.
     */

    static size_t align_max = ALIGNEMENT(union align);
    size_t multiple = a / align_max;

    return ((a % align_max == 0) ? multiple : multiple + 1) * align_max;
}


static struct bloc *recherche_bloc_libre(size_t taille)
{
    /*
     * Recherche un bloc libre ou une suite de bloc libres dont la taille
     * est au moins égale à `taille`.
     */

    struct bloc *bloc = libre;
    struct bloc *precedent = NULL;
    struct bloc *ret = NULL;

    while (bloc != NULL)
    {
        if (bloc->taille >= taille)
        {
            if (precedent != NULL)
                precedent->suivant = bloc->suivant;
            else
                libre = bloc->suivant;

            ret = bloc;
            break;
        }

        precedent = bloc;
        bloc = bloc->suivant;
    }

    return ret;
}


static void *static_malloc(size_t taille)
{
    /*
     * Alloue un bloc de mémoire au moins de taille `taille`.
     */

    static size_t alloue = 0UL;
    void *ret;

    assert(taille > 0);
    taille = calcule_multiple_align(taille);
    ret = recherche_bloc_libre(taille);

    if (ret == NULL)
    {
        if (MEM_SIZE - alloue < TAILLE_EN_TETE + taille)
        {
            fprintf(stderr, "Il n'y a plus assez de mémoire disponible.\n");
            return NULL;
        }

        ret = &reserve.mem[alloue];
        alloue += TAILLE_EN_TETE + taille;
        bloc_init(ret, taille);
    }

    return (char *)ret + TAILLE_EN_TETE;
}


static void static_free(void *ptr)
{
    /*
     * Ajoute le bloc fourni à la liste des blocs libres.
     */

    struct bloc *bloc = libre;
    struct bloc *nouveau;

    if (ptr == NULL)
         return;

    nouveau = (struct bloc *)((char *)ptr - TAILLE_EN_TETE);

    while (bloc != NULL && bloc->suivant != NULL)
        bloc = bloc->suivant;

    if (bloc == NULL)
        libre = nouveau;
    else
        bloc->suivant = nouveau;
}

Désormais, la fonction static_malloc() fait d’abord appel à la fonction recherche_bloc_libre() avant d’allouer de la mémoire de la réserve. Comme son nom l’indique, cette fonction parcours la liste des blocs libres à la recherche d’un bloc d’une taille égale ou supérieure à celle demandée. Cette liste est matérialisée par la variable globale libre qui est un pointeur sur une structure de type bloc. Cette variable correspond au premier maillon de la liste et est employée pour initialiser le parcours.

Si aucun bloc libre n’est trouvé, alors la fonction static_malloc() pioche dans la réserve un bloc de la taille demandée augmentée de la taille de l’en-tête. Ces deux tailles sont « arrondies » au multiple égal ou directement supérieur de l’alignement le plus contraignant. Étant donné que la taille de l’en-tête est fixe, nous avons représenté sa taille « arrondie » à l’aide de la macroconstante TAILLE_EN_TETE et de la macrofonction offsetof(). Une fois le tout alloué, l’en-tête est « retiré » en ajoutant la taille de l’en-tête au pointeur référencant la mémoire allouée et le bloc demandé est retourné.

La fonction static_free() se rend à la fin de la liste et y ajoute le bloc qui lui est fourni en argument. Pour ce faire, elle « récupère » l’en-tête en soustrayant la taille de l’en-tête au pointeur fourni en argument. Notez également que cette fonction n’effectue aucune opération dans le cas où un pointeur nul lui est fourni (tout comme la fonction free() standard), ce qui peut être intéressant pour simplifier la gestion d’erreur dans certains cas.

Troisième étape : fragmentation et défragmentation

Bien, notre allocateur recycle à présent les blocs qu’il a précédemment alloués, c’est une bonne chose. Toutefois, un problème subsiste : la fragmentation de la mémoire allouée, autrement dit sa division en une multitude de petits blocs.

S’il s’agit d’un effet partiellement voulu (nous allouons par petits blocs pour préserver la réserve), il peut avoir des conséquences fâcheuses non désirées. En effet, imaginez que nous ayons alloué toute la mémoire sous forme de blocs de 16, 32 et 64 multiplets, si même tous ces blocs sont libres, notre allocateur retournera un pointeur nul dans le cas d’une demande de par exemple 80 multiplets… Voilà qui est plutôt gênant.

Une solution consiste à défragmenter la liste des blocs libres, c’est-à-dire fusionner plusieurs blocs pour en reconstruire d’autre avec une taille plus importante. Dans notre cas, nous allons mettre en œuvre ce système lors de la recherche d’un bloc libre : désormais, nous allons regarder si un bloc est d’une taille suffisante ou si plusieurs blocs, une fois fusionnés, seront de taille suffisante.

Fusion de blocs

Toutefois, une fusion de blocs n’est possible que si ceux-ci sont adjacents, c’est-à-dire s’ils se suivent en mémoire. Plus précisémment, l’adresse suivant le premier bloc à fusionner doit être celle de début du second (autrement dit (char *)ptr_bloc1 + taille_bloc1 == (char *)ptr_bloc2).

Néanmoins, il ne nous est pas possible de vérifier cela facilement si notre liste de blocs libres n’est pas un minimum triée. En effet, sans tri, il nous serait nécessaire de parcourir toute la liste à la recherche d’éventuels blocs adjacents au premier, puis, de faire de même pour le deuxième et ainsi de suite, ce qui n’est pas particulièrement efficace.

À la place, il nous est possible de trier notre liste par adresses croissantes (ou décroissantes, le résultat sera le même) de sorte que si un bloc n’est pas adjacent au suivant, la recherche peut être immédiatement arrêtée pour ce bloc ainsi que tous ceux qui lui étaient adjacents. Ce tri peut être réalisé simplement lors de l’insertion d’un nouveau bloc libre en placant celui-ci correctement dans la liste à l’aide de comparaisons : s’il a une adresse inférieure à celle d’un élément de la liste, il est placé avant cet élément, sinon, le parcours continue.

En effet, deux pointeurs peuvent tout à fait être comparés du moment que ceux-ci référencent un même objet ou un même aggrégat (c’est notre cas ici puisqu’ils référenceront tous des éléments du tableau mem de l’union reserve) et qu’ils sont du même type (une conversion explicite vers le type pointeur sur char sera donc nécessaire comme explicité auparavant).

N’oubliez pas que si deux ou plusieurs blocs sont fusionnés, il n’y a plus besoin que d’un seul en-tête, les autres peuvent donc être comptés comme de la mémoire utilisable.

Correction

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <assert.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

#define MEM_SIZE (1024UL * 1024UL)
#define ALIGNEMENT(type) (offsetof(struct { char c; type t; }, t))
#define TAILLE_EN_TETE (offsetof(struct { struct bloc b; union align u; }, u))

union align
{
    long e;
    long double f;
    void *p;
};

union reserve
{
    union align align;
    char mem[MEM_SIZE];
};

struct bloc
{
    size_t taille;
    struct bloc *suivant;
};

struct suite
{
    struct bloc *precedent;
    struct bloc *premier;
    struct bloc *dernier;
    size_t taille;
};


static union reserve reserve;
static struct bloc *libre;

static void bloc_init(struct bloc *, size_t);
static size_t calcule_multiple_align(size_t);
static struct bloc *recherche_bloc_libre(size_t);
static void static_free(void *);
static void *static_malloc(size_t);


static void bloc_init(struct bloc *b, size_t taille)
{
    /*
     * Initialise les membres d'une structure `bloc`.
     */

    b->taille = taille;
    b->suivant = NULL;
}


static size_t calcule_multiple_align(size_t a)
{
    /*
     * Calcule le plus petit multiple de l'alignement maximal égal ou supérieur à `a`.
     */

    static size_t align_max = ALIGNEMENT(union align);
    size_t multiple = a / align_max;

    return ((a % align_max == 0) ? multiple : multiple + 1) * align_max;
}


static struct bloc *recherche_bloc_libre(size_t taille)
{
    /*
     * Recherche un bloc libre ou une suite de bloc libres dont la taille
     * est au moins égale à `taille`.
     */

    struct suite suite = { 0 };
    struct bloc *bloc = libre;
    struct bloc *precedent = NULL;
    struct bloc *ret = NULL;

    while (bloc != NULL)
    {
        if (bloc->taille >= taille)
        {
            if (precedent != NULL)
                precedent->suivant = bloc->suivant;
            else
                libre = bloc->suivant;

            ret = bloc;
            break;
        }
        else if (suite.dernier != NULL && (char *)suite.dernier + TAILLE_EN_TETE \
        + suite.dernier->taille == (char *)bloc)
        {
            suite.dernier = bloc;
            suite.taille += TAILLE_EN_TETE + bloc->taille;
        }
        else
        {
            suite.precedent = precedent;
            suite.premier = bloc;
            suite.dernier = bloc;
            suite.taille = bloc->taille;
        }

        if (suite.taille >= taille)
        {
            if (suite.precedent != NULL)
                suite.precedent->suivant = suite.dernier->suivant;
            else
                libre = suite.dernier->suivant;

            suite.premier->taille = suite.taille;
            ret = suite.premier;
            break;
        }

        precedent = bloc;
        bloc = bloc->suivant;
    }

    return ret;
}


static void *static_malloc(size_t taille)
{
    /*
     * Alloue un bloc de mémoire au moins de taille `taille`.
     */

    static size_t alloue = 0UL;
    void *ret;

    assert(taille > 0);
    taille = calcule_multiple_align(taille);
    ret = recherche_bloc_libre(taille);

    if (ret == NULL)
    {
        if (MEM_SIZE - alloue < TAILLE_EN_TETE + taille)
        {
            fprintf(stderr, "Il n'y a plus assez de mémoire disponible.\n");
            return NULL;
        }

        ret = &reserve.mem[alloue];
        alloue += TAILLE_EN_TETE + taille;
        bloc_init(ret, taille);
    }

    return (char *)ret + TAILLE_EN_TETE;
}


static void static_free(void *ptr)
{
    /*
     * Ajoute le bloc fourni à la liste des blocs libres.
     */

    struct bloc *bloc = libre;
    struct bloc *precedent = NULL;
    struct bloc *nouveau;

    if (ptr == NULL)
         return;

    nouveau = (struct bloc *)((char *)ptr - TAILLE_EN_TETE);

    while (bloc != NULL)
    {
        if (bloc < nouveau)
        {
            if (precedent != NULL)
                precedent->suivant = nouveau;
            else
                libre = nouveau;
                

            nouveau->suivant = bloc;
            break;
        }

        precedent = bloc;
        bloc = bloc->suivant;
    }

    if (bloc == NULL)
        libre = nouveau;
}

La fonction static_free() a été aménagée afin que les adresses des différents blocs soient triées par ordre croissant. Si le nouveau bloc libéré a une adresse inférieur à un autre bloc, il est placé avant lui, sinon il est placé à la fin de la liste.

Quant à la fonction recherche_bloc_libre(), elle emploie désormais une structure suite qui comprend un pointeur vers le bloc précédent le début de la suite (champ precedent), un pointeur vers le premier bloc de la suite (champ premier), un pointeur vers le dernier bloc de la suite (champ dernier) et la taille totale de la suite (champ taille).

Dans le cas où cette structure n’a pas encore été modifiée ou que le dernier bloc de la suite n’est pas adjacent à celui qui le suit, le premier et le dernier blocs de la suite deviennent le bloc courant, la taille est réinitialisée à la taille du bloc courant et le bloc précédent la suite est… celui qui précède le bloc courant (ou un pointeur nul s’il n’y en a pas).

Si la suite atteint une taille suffisante, alors les blocs la composant sont fusionnés et le nouveau bloc ainsi construit est retourné.


Ce chapitre clôt cette troisième partie ainsi que ce cours. N’hésitez pas à revoir l’un ou l’autre passage qui vous ont sembler difficiles ou flous avant de prendre le large vers de nouveaux horizons. ;)