/* 19Jun24: NEGATIV-BEISPIEL (I) einer Stack Implementierung.
 *
 * In diesem Ansatz vergeben wir Teile eines Speicherbereichs
 * (`memory'), indem wir Intern ein "Stack" (nicht zu verwechseln mit
 * dem Stack in einem Prozess) verwaltet.  Das heißt wir können die
 * Fähigkeit Speicherbereiche in beliebiger Reihenfolge zu reservieren
 * und freizugeben nicht gewährleisten.  (Damit hat es Ähnlichkeiten
 * zu Konstrukten wie dem "Return-Stack" aus Stack-Orientierten
 * Sprachen wie FORTH.)
 *
 * Vorteile hierbei sind, dass man in 𝒪(1) sowohl Speicher anfordern,
 * wie auch freigeben, und dass kaum administrative Datenstrukturen
 * notwendig sind.
 *
 * Nachteile sind, eben dass
 *
 *   char *p1 = malloc(10);
 *   char *p2 = malloc(20);
 *   free(p1);
 *
 * auch p2 in-validieren wird.  */

/* Indem man `_GNU_SOURCE' definiert, oder bei Aufrufen von cc mit
 * "-D_GNU_SOURCE" angibt, werden zusätzliche Funktionen sichtbar
 * gemacht, welche man nur mit der GNU Libc benutzen kann (also nicht
 * Portabel).  In der Halde braucht man das für mmap(2), wir verwenden
 * das hier für strfry(3), siehe unten.
 *
 * Siehe https://www.gnu.org/s/libc/manual/html_node/Feature-Test-Macros.html. */
#define _GNU_SOURCE
#include "halde.h"

#include <errno.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/mman.h>

#define SIZE (1024*1024*1024)

/* Eine Halde abstrahiert die Speicherverwaltung, und trennt die
 * Aufgabe Speicher zu finden von Anwendungen welche es benutzen.
 * Welchen Speicher eine Halde verwaltet, ist erstmal offen.  In
 * diesem Fall benutzen wir Speicher den wir statisch innerhalb des
 * Moduls anlegen.  In eigentlichen "halde.c" soll man den Speicher
 * vom Betriebsystem anfordern, mittels mmap(2). */
static char memory[SIZE];

/* Der Stack-Ansatz in dieser Implementierung merkt sich immer nur
 * eine Position in `memory', wo der nächste Speicherbereich vergeben
 * werden kann.  Anfangs zeigt es also auf den Anfang vom Speicher,
 * und wenn was vergeben wird schieben wir es nach vorne.  Bei der
 * Freigabe vom Speicher, brauchen wir es dann nur zurückzusetzen an
 * die Freigegebene stelle! */
static char *tos = memory;

void *malloc(size_t size) {
     /* Weil wir nur einen festen Speicherbereich verwalten, können
      * wir leicht prüfen ob wir genug Speicher vergeben können.  Wenn
      * nicht, setzen wir `errno' und deuten über den Rückgabewert
      * einen Fehler an. */
     if (tos + size > memory + sizeof memory) {
          errno = ENOMEM;
          return NULL;
     }

     /* Wenn alles passt, merken wir den Top-Of-Stack, weil der gleich
      * vergeben wird, verschieben den TOS über den vergebenen
      * Speicherbereich hinaus.  Damit wird der nächste `malloc'
      * Aufruf nach dem jetzt vergebenen Intervall weiteren Speicher
      * vergeben. */
     char *next = tos;
     tos += size;

     /* Eine Idee für eine Verbesserung: Auf dem Stack den alten TOS
      * zu speichern, und dann  */

     return next;
}

void free(void *ptr) {
     if (ptr == NULL) return;   /* es ist erlaubt NULL an free(3) zu geben! */

     /* Bei der Freigabe wollen wir erstmal sicher gehen, dass der
      * Zeiger auch von uns selbst vergeben wurde.  Das prüfen wir,
      * indem wir sicherstellen, ob der Zeiger innerhalb von `memory'
      * liegt, aber unterhalb des TOS: */
     if (!(memory <= (char*)ptr && (char*)ptr < tos)) {
          /* Ist das nicht der Fall, dann brechen wir unser Programm
           * ab.  Wir benutzen hierzu nicht exit(3), sondern abort(3)
           * womit wir andeuten, uns in einem "ungültigem" Zustand
           * (bezüglich der Schnittstelle) zu befinden.
           *
           * IdR. bricht das das Programm normal ab, aber in einem
           * Debugger würden wir an dieser stelle Stehenbleiben und
           * könnten dann den Zustand des Programm analysieren.  Wenn
           * wir Coredumps aktiviert haben, würde es auch ein
           * eingefrorenes Speicherbild im Dateisystem ablegen. */
          /* abort(); */
     }

     /* Hier nutzen wir aus, dass man sich nicht an POSIX halten muss
      * in dieser Aufgabe.  In Glibc ist strfry(3) eine Funktion,
      * welche die Reihenfolge der Zeichen in einem String zufällig
      * umsortiert.  Hier nutzen wir also die Freiheit von free(3)
      * aus, dass der Speicherinhalt von `ptr' nicht definiert ist,
      * nachdem free(3) diesen freigegeben hat.   */
     *tos = '\0';
     strfry(ptr);

     /* Die Freigabe den Speichers besteht am Ende nur daraus, dass
      * man den Speicher zurückgeschrieben hat. */
     tos = ptr;
}

/**********************************************************************/
/* ACHTUNG: Diese Datei enthält keine Implementierung von calloc(3)   */
/* und realloc(3).  Diese Funktionen sind jedoch für die Aufgabe 5 zu */
/* implementieren.  Programme welche man gegen dieses Modul bindet    */
/* könnten sich möglicherweise Falsch verhalten, wenn es unsere               */
/* `malloc' und realloc(3) kombinierend!                              */
/**********************************************************************/