DS Ram Leakage in TestNScripts

I had thought that fixing 'slope unit-tests' in addition to 'wall unit tests' would mean my fixes to get the scorpeye behaving as intended. That would mean the 'summer code review' would be over and the 'summer game dev' could start. Well, that was hoping too much, because there's actually one more test that, for some reason, doesn't show up in ./testme --list but still exists and is important: TestNScripts. This one loads the real .cmd files of SchoolRush and checks parsing went fine. And it does not only check one of them: it will reload many scripts in the same "engine", the way the game does.

while (ntests < n) {
   TestBench tc;
   for (uint i=0; i < REDO; i++) {
       printf("== R%i/%i redo%i ", ntests, n, i);
       tc.ResetEngineResources();
       ParseScript(tc, scripts[rand()%nscripts], __FUNCTION__);
       tc.CheckEngine();
   }
   ntests++;
   tc.Over();
}

No assertion failure here, instead one of the trickiest things to track: memory exhaustion. So it's time for me to learn how to use my tracking tools again. I even left documentation for my future self back in the past (thanks, past self ^^). Once again, the problem arise also in 'default'... looks like I had been over-optimistic in September 2021 when I merged sprites overlay into default.

Well, at least if gives me hope this time: on the 'newmap branch', the forgotten test terminates with 'Out of DS memory'. I managed to get a log of what is allocated at that time, but it would require filtering what has leaked from last ParseScript, and what belongs to the current, interrupted because there's no more memory, running ParseScript. Hopefully, when the bug occurs on default, it gives me a nice 'halt because of leakage' and not a 'out of DS memory' condition. 

• [done] understand why the new branch gets so high on memory consumption
• [todo] make sure .spr and .cmd files in fakeroot/ are working fine (despite they now need bilou.spr and school.spr)
• [todo] that should be the job of UnitTest.mk

edit: dummy! dummy! dummy! ... the 'DS Ram Usage' statistics in those tests is a lie! when it says 95% used, it doesn't mean you'd use 95% of the NDS 4MiB of RAM to play the script. It means that the dummy-allocator-that-never-recycle-memory used 95% of its storage to process the script. Should parsing become more complex (e.g. because we're loading one more file, or creating more intermediate structures), the memory used by the script will grow while the true RAM usage on the NDS would stay roughly the same.

Eeet ouaip. Je me suis donc morfondu un bon morceau de l'été sur le fait que mon moteur de jeu faisait péter sa consommation de mémoire. En tout cas, ça a sérieusement refroidi mon appétit pour le dévelopement de jeu après les heures de boulot. Trouver le problème, ça demandait de se plonger dans une montagne de données et les outils d'il-y-a-longtemps pour comprendre où était la fuite... Sauf qu'en vrai il n'y avait pas de fuite. Tout ça, c'était juste un ou deux messages d'erreur mal nommés qui me faisaient croire que la lecture des scripts prenait plus de 4MB de mémoire (tout ce que la DS a, en somme), sauf que l'environnement de test pour faire tourner les niveaux de mes jeux DS sur PC n'est pas prévu pour qu'on joue, mais pour qu'on trouve les erreurs. 

Donc contrairement à un système de gestion de mémoire ordinaire, quand on lui "rend" un bloc de mémoire il ne le réutilise jamais. La mémoire qu'il fournit à la demande est toujours de la mémoire qui n'a jamais servi pour une autre tâche dans le niveau, et c'est elle qui finissait par faire défaut. Vous me permettrez de croire que si vous avez envie d'en savoir plus, vous êtes aussi en mesure de lire l'Anglais?

If I want to have an estimate of the memory it would take on the NDS, I'd have to keep track of individual allocs and frees and see whether they reach some maximum at a new alloc. (2023-10-23)

What is that one-time allocator ? well, maybe you've heard of bottom-up allocator, where you just keep track of one position in memory: the top-of-used-area, and everything above the top is unused memory. Of course, as soon as you free things out-of-order compared to how you allocated them, that allocator is no longer enough. You would like at least a list of freed-blocks-that-could-further-reduce-top in case the block at the top is eventually freed. Well, the one-time allocator does not even do that. Any byte of one-time memory can be allocated exactly only once. If freed, it is "painted" as free and will remain like that until the ongoing test terminates. 

That is silly as far as memory management is concerned, but it means if some block has not benn freed when the test terminates, you know what role this memory had when it failed. There can't be any tricky-as-hell case where "yeah, that memory had been used for A and then freed, but then it has been re-allocated for B. So maybe B is wrong or maybe something still had a reference of when it was used for A". Sometimes it truly helps. When I'm not misguided by my past self with lying error messages.

test de pente en cours

Voilà, j'ai mis en route quelques modifications pour appliquer les idées du nouveau système de description du niveau avec comme point de départ un p'tit morceau de code qui crèe un 'niveau de référence' et place un personnage simple dessus qui devra avancer d'un bout à l'autre sans ce faire stopper.

Tout ça se passe dans l'environnement 'unit-testing' plutôt que sur la console elle-même et donc est testé contre les fuites de mémoire. Mais au moment d'essayer de comprendre pourquoi il y a une fuite, je me rends compte que scan-mem.pl (qui traduit les adresses stockées dans un fichier trace%d.log en nom de fichier/fonction/numéro de ligne) ne marche plus.

I had to do some more unit-testing on the new level description system. Good thing with that unit-testing environment (running on my dev PC rather than on the NDS or in an emulator) is that it features some memory leak detection. But unfortunately, as I tried to use my scan-mem.pl script -- the one that converts raw addresses stored in log files into filenames and line numbers -- I couldn't get anything relevant.

The reason for that is that Linux "now" features an address space layout randomization mechanism, that ensure .ELF files are no longer loaded at well-known memory locations, but instead takes advantage of their re*L*ocatable nature to make every instance of the program somewhat different from the others, and therefore make sith-hat hackers' life miserable by denying them simple access to part of the code/data they'd like to use in their exploit. Generally speaking, this is great, but right-here-right-now, this is bad news.

La faute au "nouveau" système de brouillage d'espace mémoire qui ne charge plus les fichiers .elf des programmes Linux à des adresses fixes (définies dans le programme) mais qui va utiliser la faculté des fichiers ELF à se reloger en mémoire pour que chaque exécution du programme utilise des adresses légèrement différentes. L'idée est de faire en sorte qu'un hacker qui parviendrait à provoquer un crash dans votre machine avec des données à lui (au hasard, une police .ttf véreuse ;) ne puisse pas pour autant appeler la fonction popen() ou system() avec des données à lui ... parce qu'il faudrait d'abord qu'il devine où elle se trouve dans ce processus-ci.

Ça ne fait pas mes affaires, mais c'est assez simple à régler: une 'simple' ligne supplémentaire dans le fichier log pour indiquer l'emplacement actuel d'une fonction précise et un appel à nm fichier_elf | grep nom_de_fonction dans le script de décodage, et je peux recalculer le décalage utilisé, le soustraire aux valeurs trouvées dans le fichier log et conquérir le monde (mouah hah hah ...)

Hopefully, this isn't that bad to fix. All I need to do is to extract the 'expected' address of some function within the decoding script, re-compute the offset and substract it to every value found in the logfile and tAke oVeR the wORld (mwah ha haah)... Erhm. The leak. Did I just said 'the world' ?  

Euh. Enfin. On va déjà essayer de conquérir le "leakage: 0%", ce sera pas si mal.

Où était le memory leak, alors?

Le bloc incriminé, c'est une palette d'actions spéciales qui est allouée dans le parseur de scripts. Je n'utilise encore rien de ce genre pour mes petits tests, mais ils sont alloués automatiquement quand on crée le parseur. Normalement, ils devraient ensuite être délégués à GameScript quand le parseur est détruit (et qu'on est prêt à jouer au niveau) .. sauf que dans ce cas-ci c'est le destructeur de GameScript qui détruit le ScriptParser, mais il le fait après avoir regardé aux palettes d'actions ... et donc cette délégation tombe trop tard. Facile à corriger.

Tout vient d'la cache

Quand Eric parlait de faire des mises à jour à la volée de la mémoire au fil de l'animation des sprites, je pensais spontanément à un système semblable à celui de Donkey Kong Country: chaque personnage se voit attribué un emplacement en VRAM et les mises à jours pour ce personnage-là viennent systématiquement à l'emplacement alloué à l'apparition du personnage. Du coup, s'il y a deux "kritters" en même temps à l'écran, il n'y aura aucun partage entre eux: le nombre d'objets à l'écran devient fortement contraint, même s'il y a peu d'images indépendantes, comme dans le cas d'Apple Assault.

In my first attempt to understand Eric Zmiro's animation engine I thought the video memory would be managed somehow similarly to what happens in DKC on SNES: every new object on screen would receive a chunk of video memory large enough for the most complex frame it has to render and it would update its content during the vertical synchronization timeslice (or at some other time slice when the GPU isn't busy looking up those pixels). To some extent, the DKC engine would be an auwfully bad choice to implement a game such as Apple Assault, where there are a large number of similar ennemies on screen and high probability that a single block of VRAM is in use by multiple ennemies at the same time. That was failing to include the key ingredient in Zmiro's engine.

J'avais oublié un élément essentiel des moteurs de jeu à la sauce Zmiro:

Chez moi, tout est en cache : Fichier, sprites, palettes, bloc... tu n'allais tout de même pas dupliquer les blocs autant de fois qu'il y a d'instance ? si ? [...] avec ce systeme (développé sur GBA en 2000), on fait actuellement l'affichage de fonte (du texte!) avec caractères proportionnel sur XBOX one et PS4, codé en utf-8 et disposant de toutes les langues y compris chinoix, japonais et coréen ! Tu vois, c'est souple.

Like for tileset used by a gigantic and varied map, Eric introduced cache management algorithm deep into the animation rendering. Animation data refer to logical blocks and the mapping to VRAM location happens dynamically, reusing blocks when possible, importing new ones only when they are not yet in VRAM somewhere else and dropping unused one only when room is needed, keeping them available for the next animation cycle when you have few sprites on screen.

With this approach, no need for pre-defined locations, no need to do spritesheet optimizations such as "let's keep only one VRAM slot for the stunned dumblador and update it from main RAM to get the desired animation on screen". For every block in the SpriteSet, all we need is an additional short integer indicating whether the block is currently missing in VRAM or stored at some location between 0 and 1023. Everytime an OAM need to be patched to reference one logical sprite block (like "page 4, block 21), you can check the corresponding VRAM slot in the spriteset and copy to a free VRAM slot if none is currently assigned.

Fini donc les emplacements pré-établis. Finies les acrobaties du genre "je vais garder une seule image pour 'dumblador assomé' sur la spritesheet et j'aurai un SprAnim qui change son contenu depuis la banque d'image restée en RAM (je fais pareil avec les vagues d'encre actuellement): pour chaque bloc de données contenues dans le spriteset, il nous faut un nombre supplémentaire, entre -1 (absent) et 1023 qui indique l'endroit en VRAM où on peut trouver cette image-là.

A chaque fois que l'on veut reprogrammer un OAM pour qu'il fasse référence au bloc "page 4, image 21", on regarde l'emplacement VRAM associé, et on en alloue un en réutilisant un emplacement libre si le bloc correspondant n'est pas encore en VRAM. Avec 1024 blocs de 16x16, on peut avoir assez de pixels différents dans les sprites pour couvrir 5 fois l'écran de la DS. Le risque d'un objet invisible par faute de mémoire vidéo est virtuellement nul. Dans mon organisation actuelle, j'ai 128Ko pour les sprites, soit moitié moins, mais ça reste tout à fait viable.

Le côté génial du truc, c'est que tant qu'on alloue sur des blocs qui ne sont pas actuellement présents à l'écran (marqués comme libres), on peut faire la mise à jour de la mémoire vidéo pendant la phase longue où le GPU retrace les pixels à l'écran. Seules les substitutions où on est obligé d'éjecter un bloc utilisé lors de l'image actuellement dessinée devront se faire pendant la phase courte émulant un "retour de balayage".

Now, how would that work with Bilou's spritesheet ? I'm currently using about 1/4th of the video memory for Bilou's heads while only one is shown at every single frame. Streaming Bilou's head into a double-buffer as the animation needs it was one of my top improvements for AnimEDS. With a Zmiro-cache, I no longer need to allocate VRAM slots to GOBs. I no longer need AnimEDS updates. And potentially, I could have the whole set of heads used by the current animation in video memory, having only gradual updates of the VRAM as I switch between actions.

Alors, est-ce que ça marcherait avec Bilou ? Un bon quart de la VRAM est utilisé actuellement pour toutes ses "têtes" et une seule est affichée à la fois. J'avais bien l'intention de faire une sorte de "streaming par double-buffer de la RAM vers la VRAM" dans une révision de AnimEDS. Le Zmiro-cache permet de passer souplement d'un double-buffer à "seules les têtes utilisées dans l'action en cours restent en mémoire vidéo". Je gagne de la place et je peux (enfin) me permettre d'autres petites animations avec des grimaces, etc.

Les mains et pieds partagés par les crayons, les taille-crayons et Bilou ? Ils n'occupent pas beaucoup de place et ont de bonnes chances de rester présents en permanence.

Shared hands and feet (used by Bilou, pendats and dumbladors) only use a small area of the whole spritesheet. It's likely a 'least-recently-used' policy would keep them permanently in video memory. Bonuses, ink drops, dust clouds would likely come and go as needed, giving more room for ennemies frames.

How many ennemies could we host ? Well the critical point is more "how much VRAM slots will be off-screen at every frame?". If you have a free (off-screen) slot for every block you need to bring in for the next frame, then you don't need time-critical copies during the blanking interval. You have 128KB of sprites memory, which means 512 different 16x16 blocks. enough to cover 2.5 times the 256x192 screen of the NDS. The gameplay will become cluttered well before you hit the cache limits. 

Les bonus, gouttes d'encre et autres nuages-de-poussière-encore-à-dessiner ferait probablement des apparitions éphémères, forçant des objets dont l'animation tient plus déjà du "streaming" (p.ex. inkjet) à faire revenir une image de la mémoire centrale vers la VRAM.

Bref, vu le nombre de fois où je me suis "cogné la tête au plafond" de la quantité de VRAM disponible juste sur le projet "School Rush", introduire cette technique de cache pour gérer la mémoire vidéo serait sans doute la bienvenue avant d'envisager un jeu plus ambitieux ... disons de la taille d'un Commander Keen ?

Tests passed, Guru still meditating.

It's a bit disappointing: I set up an environment to stress-test the code, make sure uninitialized memory has garbage content, etc, and everything runs fine. I use the same code in SchoolTest (rush) application on real hardware and it crash before starting to run the title screen. What else could I do but add the "memory inspector" mode of the Guru Meditation screen in the game ?

Pff. Râlant. J'ai fait des cas de tests, j'ai émulé, j'ai fait des corrections, j'ai vérifié mon "build system". Tout semble bon, mais quand je fais tourner le vrai code sur la vraie DS, j'ai toujours un gros crash vers la fin du chargement de l'écran de titre. Il ne me reste donc qu'à reprendre le code d'inspection de mémoire hors de runme et l'ajouter dans le jeu pour repasser en mode "débugging post-mortem"...

Edit: Grâce à l'inspection libre de la mémoire de myGuruHandler(), j'ai pu reconstruire les différents groupes de paramètres des fonctions qui ont appelé un "free()"  là où il n'aurait pas dû, corrigé le système de tests pour qu'il vérifie le "tag magique" inséré par malloc(). Jubilation: le jeu lance maintenant son écran-titre.
Déception: dès le premier contact spécial avec un autre personnage, le moteur de jeu se re-plante.

Je peux améliorer mon C++

Grande différence entre mon "nouveau" boulot (depuis Mars 2014) et mon ancien poste universitaire: ici, il y a des revues de code. Et mes collègues "Hergé et Jigé" ont un sacrément haut niveau en C++ comparé au mien. Alors autant profiter de mes deux semaines de "Super Papa Bros" pour essayer de remanier le code de mon moteur de jeu, le rendre plus fiable, plus lisible, et peut-être plus efficace.

J'avais introduit un mécanisme de gestion de mémoire inspiré du cours "compilateurs" : le "tank", avec un seul bloc de mémoire qui est découpé progressivement en sous-blocs qui auront tous la même durée de vie. L'ennui principal, c'est que ce "tank" n'a aucun moyen de retenir quels objets ont été créés ni d'appeler les destructeurs en fin de cycle. Du coup, tout objet "standard" présent dans les morceaux du tank sont une fuite de mémoire potentielle.


Parmi les "nouveaux trucs" appris cette année qui pourront m'être utiles, il y a la fonction "foreach", les fonctions template (et en particulier leur utilisation pour faire de la programmation assertive), les namespaces anonymes, et les structures-internes-pour-masquer-l'implémentation.


Let me collate a few C++ tricks I practiced this year and hope to use in my hobby tools/game engine to improve them.
If it make sense to have a function applied on all members of a collection, foreach can help:

- for (vector<Tire>::iterator it = wheels.begin(), e = wheels.end(); it != e; it++) {
- checkPressure(*it);
- }
+ for_each(wheels.begin(), wheels.end(), checkPressure);


Template function do exist. Template functions do not need their template argument to be specified when it can be inferred from function arguments. E.g.

template<typename T>
void assert(T a, T b, const std::string msg) {
  if (a != b) throw AssertException(msg);
}

can be invoked as
+ assert(myCar, TimeTravellingDelorean, "timed' out");
-assert<Car>(myCar, TimeTravelling ...);;

Template integers exist too. If you want something to behave completely differently depending on whether you're on a 32-bit or 64-bit system, you might consider the following function that can be invoked as getLibraryPath<sizeof(int)>():

template<int> path getLibraryPath();
template<> inline path getLibraryPath<4>() {
  return "/usr/lib32";
}
template<> path getLibraryPath<8>() {
  return "/usr/lib/x86_64-linux-gnu";
}

Note that only template declaration can fit within the class body. Specializations introduced with template<> must be out of the class block and have additional MyClass:: token.

And as we're talking about templates stack overflow's question on puzzling template error messages can help.

You don't need to declare your functions static to avoid interference with other translation units of the program. Simply put them in an anonymous namespace.

You don't need to explicitly track the "object setup sequence" with an init_level if you can do it with contents of the regular members of the objects,

Car::~Car() {
- switch(init_level) {
- case TIRES_MOUNTED: RecycleTires();
- case ENGINE_INSTALLED: RecycleEngine();
- // FIXME: what do you do for default: ?
- }

+ if (tires!=UNDEF) RecycleTires();
+ if (engine!=UNDEF) RecycleEngine();

PS: UNDEF could just be 0 for pointers to components.

You can have compact structure initialization with (optionally-)named fields but it must be *trivial*, e.g.

• you may not swap the order of components;
• you may not omit a field if there are other field after it
• but you *can* omit items at the tail of the description

If you want a class/struct to look more like a first-class citizen, think about

• copy constructor : Car(const Car &that) : engine(that.engine), tires(that.tires) {}
• comparison operator : bool operator==(const Car &that) { return that.tires==tires && that.engine==engine; }
• ostream-compatibility: this requires a additional std::ostream& operator<<(std::ostream& os, const Car& that) { os << "powered by " << engine << " on " << tires; return os; } function. Note that it is *not* a member of the Car struct/class and that it will need to be declared friend of the Class in case of a class.

Something thrown as throw new std::runtime_error(..) is caught by catch (...) { releaseResources(); throw; }, but not by catch(const exception& e). That latest one only catch stack-allocated exceptions, e.g. throw std::runtime_error(...);. Reading more on this I should.

I should remember that namespace ds = PPPTeam::LibGEDS is the way to say import PPPTeam.LibGEDS as ds. And that ostream & operator << (ostream &out, const Complex &c) is the way to tell how the class 'Complex' should be printed.

Oh, and I shouldn't use std::unique_ptr on stack-allocated object. ever. unique_ptr will eventually call free on the pointer it holds.

 

In case of doubt on performance, remember that Quick-Bench.com does exist.

Usage: 15% ; Leakage: 12%

I guess you all know what a "memory leak" is. Well, you might not have a lot of gameplay updates in the following weeks: I just enabled a sort of report that measures how much of the state created when parsing the title screen of School Rush. 12%. I've got some code-cleanup to go through.

Bon, bin les premiers résultats de l'analyseur mémoire intégré à mon système de test-de-code-DS-sur-x86 sont précis, mais aussi assez effrayant: 12% de la mémoire allouée lors de l'initialisation de l'écran-titre ne sont pas rendus à la fin du niveau. Dans un cas pareil, la mémoire de la DS (4Mo) finit systématiquement par être saturée après un certain temps d'utilisation du jeu, ce qui ce traduira fort probablement par un crash.

Allez, joyeuses fêtes à vous aussi. (Et, euh, non, n'espérez pas trop une version "spéciale Noël" de School Rush avec de la neige sur les bancs et des bonnets à ponpon sur les gommes sauteuses, du coup)

PS: I suspect this could be linked to the migration of most state-machine data structure into the "tank" memory allocator: because the tank doesn't know objects themselves, and that it's quite unlikely that it invokes their destructors when "flushing" the tank. I'll have to make sure that structures that were pushed into the tank are flat enough or that their sub-components are allocated in the tank too.

The missing frame.

Why is my backtrace-recording code not properly recording backtrace ? And the true question is ... is it really not back-tracing correctly ?

• malloc < new() < __gnu_cxx::new_allocator < Vector_base < std::vector ... " is missing __gnu_cxx::new_allocator.
• "malloc < new() < TestBasicScript() < main() is missing TestBasicScript.
• malloc < GameScript ctor < TestBasicScript is complete. good.
• malloc < operator new  < GameScript ctor < TestBasicScript < main is missing the ctor.

Having a look at the disassembled code explains already some of the things. For instance, remembering me that neither the constructor calls operator new, nor the operator new calls the constructor. No. The function constructing an object, TestBasicScript, calls both the "operator new" (_Znwj) and then the constructor.

Next interesting thing, operator new is systematically the function whose caller is missing. That can be explained if operator new itself is not creating some stack frame.

void TestBasicScript() {
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   56                      push   %esi
   4:   53                      push   %ebx
   5:   83 ec 20                sub    $0x20,%esp
/home/pype/DS/tests/BasicScript.cpp:6
  BufferReader *ir = new BufferReader("print \"hello\"\nend\n");
   8:   c7 04 24 0c 00 00 00    movl   $0xc,(%esp)
_ZN12BufferReaderD0Ev():
   f:   e8 fc ff ff ff          call     _Znwj
  14:   89 c3                   mov    %eax,%ebx
  16:   c7 44 24 04 00 00 00    movl   $0x0,0x4(%esp)
  1d:   00 
                        1a: R_386_32    .rodata
_ZN11InputReaderD2Ev():
  1e:   89 1c 24                mov    %ebx,(%esp)
  21:   e8 fc ff ff ff          call   _ZN12BufferReaderC1EPKc
_ZN12BufferReaderC2EPKc():
  26:   89 5d f0                mov    %ebx,-0x10(%ebp) 

Emunit-testing

I am stuck with bugs in the two approaches I planned to use to allow shop-for-bonus in-between levels. Kind of bugs that are difficult to track with regular debugging, and that may even crash the emulator or the debugger itself.

So it's time for me to start doing more professional testing on my code base, dropping rendering and things alike so that I have more control on memor allocation and objects lifecycle. For that I need that access to NDS registers can still be performed although it will be a regular x86 program running under linux. I thought I could use a custom linker map to force the declaration of a regular area where the registers are expected, which you use with -T linker-script-file. But being sure that all of C++ sections will remain in place might be harder than creating a custom layout for an operating system kernel.

Hopefully, the memory map is somewhat compatible with the default locations for a 32-bit linux process. A few mmap calls and I can have valid read/write memory mapped at the place where NDS registers are expected. That should be all I need.

I will need to track what memory area are still alive after the end of a level, to know whether some could still reference dead objects and lead to memory corruption. I'll need too, to know who allocated such block so that I can understand their nature and purpose. I remember of Tim Robinson explaining how he embedded a call trace leading to *alloc. I'll try and do the same. It's not quite completely working at the moment.

reverse emulator bug ?

Je connaissais le bug d'émulation. Vous savez, ce genre de bug qui ne se produit jamais quand vous testez sur émulateur et qui crashe lamentablement le programme dès qu'il tourne sur une vraie plate-forme (généralement parce qu'elle a de la vraie mémoire).

Why? I can explain easily a bug that happens only on bare metal, but not in an emulator, but this time, it's the opposite. I spent 3 evenings trying to figure out why the emulator crashed before I could explore any issue with DDD. However, on the Real Thing, I can play the game without any issue... 

If I find a way to re-build that emulator from its source, it could be interesting to implement a ring of last N jumps/calls so that we can actually track the reason of such crash. But do I still have the source+compiler combination do to so ?

Là, il semblerait que je viens de passer 3 soirées à tenter de comprendre l'inverse: un bug qui ne se produit que sur l'émulateur. Mais qui crashe l'émulateur, pas le programme émulé, sans espoir de placer des breakpoints ni rien de ce genre. J'avais fini par m'imaginer qu'un vrai "guru meditation screen" serait plus instructif que ce rapport de crash généré par desmume. Et euh ... rien. Pas de bug. Je fait les 4 niveaux deux fois, avec des morts ici et là. Sans que ça ne s'arrête. Au moins, le nouveau système de gestion de mémoire (merci, PAdM) m'a sorti d'un mauvais pas.

Automated OAMs management

Over the summer, I crafted plans for managing larger levels, that would use more than 128 hardware sprites (the OAMs in DS parlance) for all the monsters. Some of those plans use the notion of a "Gob Group", that could be used to spawn several objects at once, at level-specific locations by having them statically placed (unlike shoot-able "dyngobs") but wouldn't be active unless their group is enabled.

Browsing through the game engine code for another purpose on my cybook, it struck me that it would be so easy to have lazy allocation of the hardware sprites as we approach on-screen area and early recycling of those OAMs when we're going far enough from that area. It's now coded. Funny enough, it doesn't affect activation and movement of GOBs in any way: only whether they have hardware sprites assigned to them or not.

done: find a way for Bilou to keep its priority (displays over monsters)

1 day left

I have quirks in moving inkjets and the pendat doesn't feel like progressing forward right now (nor left now, afaik). There's a more concerning issue, however: I will have to cut the number of monsters present in the level. With pendat reaching up to 6 or 7 "limbs", and each limb being an individual OAM, and all those OAM (i.e. hardware sprite) being statically assigned to objects, I regularily (e.g. when inkjet throws droplets) hit the "128 OAMs" barrier of the hardware that makes some sprite becoming invisible. Another engine update will be requiredwelcome to fix that. That shall be the road ahead.

J-1, bonjour les pépins. En plus des effets curieux lors des déplacements d'encriers et du pendat qui fait la grève, je me retrouve régulièrement avec le moteur de jeu qui se plaint qu'on dépasse la limite des 128 sprites hardware. Il faut dire qu'à lui seul, un pendat en consomme déjà bien 6 ou 7, et que le moteur les pré-alloue pour l'ensemble du niveau. Du coup, quand les encriers décident de lancer de l'encre je suis trop court.

(edit: heureusement, ce n'était qu'une fausse alerte liée au fait qu'un des morceaux de runME s'auto-alloue la moitié des sprites hardware et n'en laisse que 64 pour les niveaux du jeu ^^" voir les détails dans les commentaires)

edit: fixed with automated OAMs management. It took over 1 year, but hopefully, meanwhile I had realised that I was far from the hardware limit and just experiencing issues in runME because it pre-allocated half the OAMs "for internal purpose"

More slopes

J'ai envie d'avoir plus de souplesse dans les pentes que juste "45° dans quel sens?". Si ça n'apporte pas grand-chose au niveau du gameplay en tant que tel (un ennemi-marcheur en haut d'une pente garde un avantage stratégique même pour d'autres formes de pentes), ça permet de construire des niveaux plus "organiques", ce qui n'est déjà pas si mal.

I deliberately picked a side item that should somewhat be less braintensive to work on as Lil'son is now released. In clear, something that can take place in a FridayAfternoon branch. So let's see how we could introduce more slope angles (and shapes) in my game engine. I assume that most of these "extra slopes" will be designed in larger chunks of 64 pixel wide, like a staircase, a curved hill top or a pair of 22.5° slopes. 

En revanche, j'ai déjà saturé le nombre de "type de blocs" dont je dispose vu ma technique d'encodage. L'idée cette fois serait de combiner le "type" (encodé par élément 8x8) avec la position du tile au sein d'un bloc de 64x16. Si ça reste jouable au niveau du moteur de jeu, ça demande un support spécifique dans l'éditeur de sprite pour "préparer" ces blocs de 64x16 contenant 16 tiles alloués de manière contigüe dans la SpriteRam (alors qu'ils sont normalement alloués par bloc de 4) puis de les disposer conformément à ce qui est prévu pour un des type d'obstacles souhaités.
You may remember that I have 16 major tiles types, which can be freely assigned to any tile. This "chunking" is thus actually required so that we can use the offset of tiles within a chunk as an additional clue of "which sub-type of slope" we're walking on (and eventually convert that into the appropriate height array in the engine's data. No real difficulty is expected from the game engine code, but it requires that we can alter tiles arrangement in the sprite editors so that the "curved hill" uses appropriate tile numbers. Some UML/C++ joy expected ahead. One that really insists on implementing a SMW clone could rather use "gradual" (11.25) slopes rather than those curves.

En comparaison, le moteur de SMW (selon Lunar Magic) offre 3 angles de pente: 'normal' (22.5), 'gradual' (11.) et 'steep' (45). Au niveau du gameplay, les pentes 'steep' étaient les seules à pousser d'office le joueur vers le bas (si ma mémoire est bonne).

Bon, je sais, ce n'est sans doute pas ultra-prioritaire pour faire avancer Bilou, mais mon petit J.l.n est né vendredi dernier, ce qui réduit un peu ma liberté d'action. Un peu de bidouille dans les éditeurs devrait donc être plus aisé que d'aller créer du code pour de nouvelles interactions avec Inkjet.

Repaired, and still not working

Want a funny trivia? altough I got the spriteset "repaired", it's still too large for the game engine, after all. So I still don't see spongebop at all, but just some Bilou feet/hands again >_<

Maybe some blocks should be marked "free" and they aren't, maybe I really need to optimize so that I lower the allocation watermark ... or maybe it's something else.

At first, I thought some visualization of the spriteset content (preferably on SEDS's file window) would *definitely* help to figure out. Something like a 32x32 sprite can providing one-pixel-per-spritepage. But that'd be a bad idea.

I mean, *I* would find it handy, but it shouldn't be the problem of the sprite artist to organise the tileset so that sprites fit in. Doing something like "move this page to 'draft', click 'optimize' and then move the page back to 'sprite'" is a hack, not something I want to read (and definitely not write) in any user manual for my software.

The root of the problem is in the tiles allocation: it prefers allocating what has been recently freed, while it should prefer what has low values and would lead to a compact enough tileset. Think about it.

Debugging Industriel ?

Finalement, j'ai opté pour une approche toute neuve (pour moi) pour ce problème de malloc. C'est toujours via gdb que j'attaque le problème, mais je laisse tomber la sur-couche graphique (ddd) au profit d'un petit script perl. Celui-ci va placer les breakpoints à l'entrée et à la sortie des fonctions "malloc" et "free" (ainsi qu'à des emplacements stratégiques dans les opérateurs new et delete du C++) et enregistrer consciencieusement la pile d'appels, le contenu des registres du processeur ARM9 et le contenu du tableau __malloc_av_ dont j'ai parlé précédemment, et qui représente la "partie visible" de l'état maintenu par malloc.

Ce côté "totalement automatique" permet d'obtenir une trace exhaustive (64Mo) de ce qui s'est passé au niveau gestion de la mémoire pendant l'exécution du programme, que je peux ensuite traiter avec d'autres scripts. Par exemple pour vérifier qu'il y a bien eu un appel a free avant chaque delete operator, et surtout qu'il y a un malloc()=X pour chaque free(X), et l'emplacement dans la trace de la dernière opération sur l'adresse X dans le cas contraire.

Avec un peu d'ajustement, je devrais même être capable de trouver les malloc() pour lesquels il n'y a aucun free .. et donc potentiellement d'identifier les fuites de mémoire dans mon code. Bien sûr, il existe d'autres programmes pour faire ça, et ce de manière plus automatique (valgrind, si ma mémoire est bonne). Il y a aussi des implémentations qui intègrent ce genre de tests (cf. la variable d'environnement MALLOC_CHECK_ sous Linux) ... je profite du côté "hobby" de ce projet pour découvrir et tester des hypothèses, me construire de petits outils et tout ça ...

Et j'ai finalement mis le doigt sur le problème ... une bête initialisation manquante dans la classe GobState. C++ n'aide vraiment pas le programmeur, de ce point de vue-là. Je devrais m'habituer à compiler avec -Weffc++, s'il ne contenait pas une quantité ridicule de warnings qui me sont inutiles.

0_o still 42 zombies

Making funghi-generated applemen EVIL wasn't such a hard task. Now I need to ensure they are properly destroyed when the level is over. It looks like it's something I had postponed when writing ClearDynGobs() ... Resulting in an enigmatic "still 42 zombies" message in the middle of parsing logs.

I don't like zombies. They believe their iWorld still exists but it doesn't. They mess up with the real world instead, poking and peeking here and there. They follow NuLL pointer ... chaos and madness await them at its end.

Avec 3 jours 3/4 de congé commençant ce soir et les bouts de code qui s'assemblent comme des pièces de puzzle, je sentais bien une pre-release d'Apple Assault avant de décoller pour la Suède ... Un petit message "42 zombies restant" fixé sans trop de soucis (en nettoyant convenablement les "dyngobs"), enfin la possibilité d'assommer les ribanbelles de pommes. Let the sun shine, quoi.

Ouais. C'était compté sans malloc et ses effets à retardement. Cette fois, même gedsdemo, la version autonome du moteur de jeu utilisé pour les release, est affecté. Desmume lui même en reste sans voix: impossible d'effectuer du débugging puisque le "serveur GDB" qu'il intègre semble s'être bloqué lui-même. J'ai quelques pistes à tenter, mais ça prendra du temps, du papier et quelques tasses de thé. Je vous tiens informés.

Btw, 42 apples in a level doesn't slow the engine down in any way, and it produce funny "wiggler" or "lemmings" behaviours. And it sure keeps the doctor away ^_^

I see coming more "debugging sessions darker than night itself", though. For some unclear (yet) reason, the current game engine crash in bowels of the memory manager after two runs. I can only guess this means something is freed twice or some similar issue. The codebase has grown since the last (not so succesful) attempts, and today not only runme is affected, but also the game engine demonstrator. It's the most stable memory bug I've seen ever, and I hope I'll at last be able to pinpoint what's going wrong.

oamstack from XeO³

Bion, ajouter des sprites dans tous les sens, c'est sympa. Continuer à avoir des sprites dans le 2eme niveau, c'est mieux. L'ennui, c'est que le GuiEngine, comme son nom l'indique, a été au départ conçu pour gérer des interfaces graphiques (SEDS et LEDS), et pas des jeux, ce qui signifie qu'il n'y a pas la possibilité à ce niveau de libérer des sprites -- ou plus précisément, les OAM, c.à.d. les zones en mémoire vidéo qui décrivent l'emplacement et les propriétés des sprites. Qu'à celà ne tienne: m'inspirant du "stack allocator" pour 6502 du projet XeO³, je rajoute une petite surcouche ...

I was making sure that sprites could be reclaimed and that you keep seeing little stars even if you got hit > 60 times ... Just one problem here : Engine::allocate is the only way to inform the GuiEngine of how much sprites it should sync to the DS video memory ... As the level is reset, that number is reset to 0, but since all the Gobs of the level have just been "pushed" in the oamstack ... well ... Engine::allocate() is never called and thus no sprite show up ... at all. Trivial to fix, but reminds me that you should always think twice when you alter the behaviour of something ... And that was a nice occasion to mention Dailly, Kekule & Russel's work on XeO3 : the Ultimate shoot'm'up for Commodore Plus/4 (which has some armalyte taste, if you ask me) and how this code gets inspiration from the 6502 "stack allocator" for bullets in that game.

Ca n'a pas tout à fait marché, mais presque: le GuiEngine retient le nombre de sprites qu'il a effectivement alloué et ne copiera en VRAM que ceux-là. Or, lorsque le niveau recommence, tous les OAMs précédemment restent dans la "pile de sprites recyclés" alors que le GuiEngine pense qu'il n'y en a aucun en service. Le résultat ? Bin le jeu tourne, mais plus aucun sprite ne s'affiche. C'est plutôt bête comme chou à régler, donc je vais aller règler ça pendant que vous découvrez en détail cet étonnant projet XeO³ mené par Mike Dailly, un (ancien ?) programmeur de chez DMA design dont je suis le blog depuis un moment.

edit: Btw, yes, this implies u8 oamstack[128] because there is at most 128 OAMs per screen and that the game is only on one screen. I can't think of another allocation scheme that would save me more and don't disturb run-time operations. I'd love to extend the mechanism to GameObject structure themselves (which have higher allocation overhead)

edit++: funny, they seem to use the same kind of "script-encoded-into-asm-constants" approach than I used in 2000 for Out'm'UP :).

Tracking Memory Bugs

malloc et free sont des outils formidables, mais quand on s'est un peu embrouillé dans son code, ça devient vite une plaie. Je m'explique: le système d'allocation dynamique ne fonctionne pas "magiquement": il conserve autour des blocs libres et occupés des informations : taille de la zone, prochaine zone libre, etc. Elles sont évidemment importantes lorsqu'une zone libre est allouée ou qu'une zone occupée est libérée, mais elles servent aussi lors d'opérations de "compaction" (pensez au defrag du disque windows, vous n'êtes pas loin). Si on dépasse l'espace alloué pour une zone A, on peut facilement aller écraser les informations de contrôle d'une zone B. Du coup, on perd le lien entre la cause de l'erreur (le code qui gère A) et ses conséquences (erreur lors de la libération ou de l'allocation de B).

Dynamic memory allocation is a key aspect of programming that both open new horizons and puzzle newbie programmers. Unfortunately, it can also become a real nightmare for the seasoned programmer who has overestimated his skills, even just temporarily. malloc and free are not built from magic out of the void*, of course. They are algorithms that use small memory headers to maintain internal information about which block is free, how big is what, etc. This information is used when allocating/freeing blocks, of course, but also in the process of coercing small, contiguous free blocks into a larger one to avoid excessive memory fragmentation.
The problem is, that if code responsible for block A trashes information about block B (e.g. due to a buffer overflow bug), the error remains latent until block B is used again, and by then, you completely lost the knowledge that A is the faulty guy.

Ca fait un moment que je traine un bug de ce genre dans runme, sans trop savoir si c'est mon code qui est en faute ou celui de NTXM, le module player que j'y ai intégré. Bug plus ou moins facile à reproduire d'une révision à l'autre, mais que je sais être lié à une erreur de gestion de mémoire grâce au "crash code address" indiqué sur l'écran "guru meditation". Ces dernières semaines, j'ai pas mal avancé dans la gestion des erreurs et j'ai maintenant une fonction die() qui peut reprendre la main en cas de guru meditation ou d'exception C++ non traitée. Elle peut à présent tenter de retourner au moonshell, mais aussi afficher le contenu de n'importe quelle zone de mémoire de la DS. De quoi étudier la situation de manière un peu plus méthodique.

I know that I've got such a bug in runme (hence the lack of releases and the extensive use of gedsdemo). It's reappearing now and then and then hides again for a few releases. I've already proceed to a few code sanitization steps, but it doesn't look like i've been effective. With my recent findings (__cxa_terminate) and the introduction of a die() loop that replace main() after a guru meditation has been notified, I've given myself a memory inspection tool that let me follow "valid blocks" (starting the list from entries in __malloc_av_, the entry point of free lists) up to a faulty block that precedes the one where malloc/free() triggered an exception due to a wrong size.

Now, the goal is to trace back the owner of this memory block ... to be continued.
Un papier ... un bic ... pas mal de patience et la DS branchée sur chargeur ... C'est parti.

Try Again ...

La bonne nouvelle, c'est que j'ai enfin un mécanisme me permettant de recharger un niveau quand Bilou s'est pris trop de coup. La mauvaise, c'est qu'à recommencer 20 fois le même niveau, je finis par mettre en évidence des fuites de mémoire dans mon code.
Il est temps de reprendre le code de mon prototype de manière un peu plus rigoureuse, de passer en revue mes classes en suivant les bons conseils++ d'Axel. Jusqu'à 300K qui partent en fumée à chaque vie, ça coûte vite cher sur une machine qui n'a que 4MB.

Good news first: I can at last reload a level when Bilou has been hit too much. The downside is, that this highlight a memory leak in my game engine. Most likely some machine state isn't properly reclaimed. It's time to print my code and read it back with a mop in hand ...

• double invocation of GameScript ctor on reload : >280 K goes away
• not taking care of transitions when cleaning the state machine : 5K
• not taking care of cleaning "guns" : neglectible right now
• other (under inspection) lost things : 5K
• not taking care of OAMs allocation over iterations : invisible sprites after ~16 attempts
  

edit: fixing a stupid and obvious bug reduce the leak from 300K per live to 10K per live. Below comes the checkram() function i'm using to count available memory (that simply allocate as much as possible, then releases everything). Just refrain yourself from using std::whatever to store allocated chunks if you don't want to see a bad_alloc exception thrown in the middle of the process.

int checkram() {
int total=0;
iprintf("grabbing ...");
void **chunks=0;
void **chunk=0, **prev=0;

for (int chunksize = 1024*1024; chunksize>32; chunksize=chunksize/2) {
int n=0;
while((chunk=(void**)malloc(chunksize))) {
*chunk=(void*) prev;
chunks=chunk;
n++;
total+=chunksize;
prev=chunk;
}
iprintf("%i,",n);
}

iprintf("releasing ...");
while(chunks) {
void **chunk=chunks;
chunks=(void**) *chunk;
free(chunk);
}
return total;
}

Bien sûr, une telle fonction est une dépense de resources matérielles inutile si l'on connaît suffisamment l'implémentation de malloc dans l'environnement précis où l'on développe. En l'occurence, ludo connaît une méthode bien plus efficace et élégante pour libnds. And ludo's sources come from this gbadev post

Bilou par Wifi ...

Hehe. Je vais me faire enflammer avec un titre pareil. Non, on ne joue pas encore à Bilou par Wifi, mais j'ai transféré les couleurs de mes tests sur Pixelization vers SEDS histoire de pouvoir essayer un p'tit Bilou (mais alors vraiment tout petit, là). Ce qui veut dire que les réorganisations de couleurs dans la palette, c'est fait aussi. Je me ferais bien un petit "publier le sprite courant par Wifi" avec conversion immédiate en .png à la réception sur le PC, tiens ;)

Oh, keep cool. You cannot play Bilou vs Bouli over wifi. Not yet. But i can beam my palettes to SEDS using Wifi and give a try on new looks for Bilou. I made quite a bunch of very funny animations with those colours, and i have to admit that it's working well. Unfortunately, i made *too much* animations, and i should rather have polished my code instead. When i tried to finally save my work and go to sleep, the display looked strange, and when i later tried to re-load the sprites, all i got was a guru meditation.

The most likely explanation is that the code for managing animation is very rusty -- one of the very last remains of the initial code for SEDS that has never been refactored, and it obviously contain bad practice memory management stuff that have last beyond initial expectations. I lost a couple of things in the process, but nothing i couldn't re-do. Hopefully enough, it happened on a testbed spritesheet, and not on my preciousss "greenzone" tileset. It's a good thing to see that my tools for handling .spr files can recover some corrupt data too ;)

Aaargh. sur ma lancée, j'ai essayé de faire un deuxième Bilou un peu plus grand. Puis je l'ai animé pour donner l'impression de "respirer" et j'ai refait des balles de formes diverses (plus applatie et plus ronde) sur la même base. Puis j'ai joué à faire marcher mon p'tit Bilou et donner quelques expressions au plus grand.

Ouais. Bin j'aurais mieux fait de finir le debugging de mon éditeur, pas encore capable de gérer correctement les longues animations qui s'en sont suivies. Au moment de sauver tout ça, il m'a montré des pages de sprites de plus en plus louche ... Pas dupe, j'ai voulu recharger : bardaf : Guru Meditation.

Comme vous pouvez le voir, la plupart des "tiles" seront récupérables (à la main dans Gimp, j'imagine), mais les infos qui disent quel bloc utilise quel tile, là, c'est irrémédiablement foutu >_<

edit: comme je m'y attendais, c'est plus que probablement dans la gestion des animations que se trouve le gros bug. C'est du vieux code d'avant que je ne me mette à la bibliothèque standard du C++ (vecteurs, maps, etc) qui est encore plein de malloc(sizeof(x)*n) et qui manque de if(i>n) return; si vous voyez ce que j'veux dire