Lovlevel Speicher Funktionen anstelle von realloc

[Bitte ein Bit]

Benötigst du wirklich eine Speicherverwaltung oder ist dein Problem eher dass du eine unbekannte Anzahl von Datensätzen in ein Array einlesen willst und nicht dauernd ein realloc machen willst sobald wieder ein Element eingelesen wird ? Wenn ja, gibt es nur zwei Alternativen. Entweder ein Array in der "richtigen" Größe anlegen, so dass alle möglichen Daten eingelesen werden können, oder man benutzt verkettete Listen.

Falls du aber wirklich eine Speicherverwaltung benötigst, würde ich dir den Umstieg auf C++ mit der STL empfehlen. Dort ist nämlich schon alles fein säuberlich drin.

[fortschritts-freak]

Bitte ein Bit schrieb:

Falls du aber wirklich eine Speicherverwaltung benötigst, würde ich dir den Umstieg auf C++ mit der STL empfehlen. Dort ist nämlich schon alles fein säuberlich drin.

*schluck* wie kannst du nur eine fast 30 jahre alte krücke empfehlen? es gibt doch viel ausgereiftere programmierumgebungen, mit einer vollautomatischen speicherveraltung, wenn man schon aus diesem grund was anderes benutzen will.

[Osbios]

Ich versuche es mal so zu erläutern:

Ich habe früher ein bisschen im Lowlevel Bereich Programmiert. Also mit Assembler auf unterster ebene. Ich habe auch ein eigenes "Betriebssystem" mit Tastaturtreiber, Maustreiber ein bisschen Grafik, etc...
Jedenfalls weiß ich daher wie der x86 den Speicher verwaltet, bzw. wie ein Betriebssystem diesen grundlegend verwalten MUSS da die Hardware so aufgebaut ist. (Virtuelle Adressen, 4KiB/4MiB Speicherseiten, etc...)

Daher habe ich gedacht müsste dieses "Virtuelle Adressen reservieren" und "Einzelne Page anfordern und in virtuellen Adressraum mappen lassen" die grundlegende API für ein Programm sein. Dieses wird nur meist durch einfachere Standard Libs verschönert wie die glibc und schaut dann nur noch wie "Speicher anfordern und Adresse geben lassen" aus.

Ich werde in meinem Programm jetzt nur realloc benutzen da ich es etwas umgebaut habe.

Interessieren würde es mich aber immer noch ob es da einen größeren Standard gibt, oder ob ich jeweils auf die OS-Spezifischen Schnittstellen zugreifen muss?

[library-freak]

Osbios schrieb:

Interessieren würde es mich aber immer noch ob es da einen größeren Standard gibt, oder ob ich jeweils auf die OS-Spezifischen Schnittstellen zugreifen muss?

ich glaube nicht. aber vielleicht gibt es portable libraries für verschiedene systeme, über die man die lowlevel speicherverwaltung erreichen kann.

[BorisDieKlinge]

@fortschritts-freak: was denn? Java^^ mit dem geilen garbage collector

[java-freak]

BorisDieKlinge schrieb:

@fortschritts-freak: was denn? Java^^ mit dem geilen garbage collector

nicht unbedingt, es gibt ja noch andere alternativen. aber das hat mit der anfänglichen frage sowieso nichts mehr zu tun.

[pointercrash**]

Osbios schrieb:

Ich habe früher ein bisschen im Lowlevel Bereich Programmiert. Also mit Assembler auf unterster ebene. Ich habe auch ein eigenes "Betriebssystem" mit Tastaturtreiber, etc...)

Komme auch aus der Lowlevel- Ecke ...

Osbios schrieb:

Daher habe ich gedacht müsste dieses "Virtuelle Adressen reservieren" und "Einzelne Page anfordern und in virtuellen Adressraum mappen lassen" die grundlegende API für ein Programm sein. Dieses wird nur meist durch einfachere Standard Libs verschönert wie die glibc und schaut dann nur noch wie "Speicher anfordern und Adresse geben lassen" aus.

Ich glaube, da wirfst Du was durcheinander. Wenn Du ein OS hast, sollte es Dich gar nicht erst da ran lassen, d.h., das OS besorgt den Speicher für Dein malloc(), virtuell oder physikalisch, wie auch immer.
Bei der Systemprogrammierung forderst Du Speicher direkt von der "nackigen" Architektur an, ohne OS- Support, da hast Du selbst die Verantwortung, daß das hinhaut. Du mußt halt Deinem Compiler das Target klarmachen. Für Dich sollte es aber immer bei malloc() bleiben.

Osbios schrieb:

Interessieren würde es mich aber immer noch ob es da einen größeren Standard gibt, oder ob ich jeweils auf die OS-Spezifischen Schnittstellen zugreifen muss?

Auf Die ursprüngliche Frage eingehend glaube ich, daß das Stichwort Smartheap heißt, nach dem Du suchst.

Unter C hat malloc()/realloc() den unschönen Nachteil, daß der Speicher fragmentiert und es keine Garbage Collection gibt. Tatsächlich gibt es Smartheaps für C, aber nicht als Standard. Denen erzählst Du zu Anfang, wieviel Speicher sie sich schnappen sollen und aus dem Pool kriegst Du per Ersatz- mallocs/reallocs Deinen Speicher und Du kannst den Speicher "aufräumen" lassen, wenn Du's für nötig hältst.
Leider sind die meisten Implementationen Architektur- oder Compilergebunden und haben eklatante Einschränkungen, was z.B. Reentranz anbelangt - richtig Überzeugendes habe ich zumindest für embedded noch nichts gefunden.

[heap-freak]

pointercrash() schrieb:

Leider sind die meisten Implementationen Architektur- oder Compilergebunden und haben eklatante Einschränkungen, was z.B. Reentranz anbelangt - richtig Überzeugendes habe ich zumindest für embedded noch nichts gefunden.

das stimmt, aber meistens kommt man für 'embedded' allermeistens ohne heap aus. ich kann wohl sagen, dass ich schon viel in dem bereich gefrickelt habe, aber ich musste bisher nur einmal eine heap-implementation verwenden. das war für ein gerät, in dem eine scriptsprache eingebaut ist, damit benutzer sich eigene programme basteln können, die das gerät steuern. die scriptsprache besteht aus einem bytecode-compiler und 'ner virtual machine. da man sowas nicht selbst neu erfindet, hab' ich mir (nach langem suchen) was gegeignetes aus dem netz gezogen und das machte leider extensiven gebrauch von malloc/realloc/free weil die programme sich z.b. arrays und ähnliche objekte anlegen können. als heap hab' ich 'ne schlanke implementation für S12-CPUs genommen, die so umgebaut, dass sie auf nem ARM7 läuft und jede anomalie (heapcrash etc.) bemerkt und das user-programm abbricht. bisher ist es noch keinem gelungen, das device mit einem script zu killen.

[pointercrash**]

heap-freak schrieb:

das stimmt, aber meistens kommt man für 'embedded' allermeistens ohne heap aus.

Bei 'ner Heizungssteuerung ist klar, das Ding kommt mit 100 Byte RAM aus. Aber sobald ich 'ne Edit- Methode für Eingabefelder krickel', mag ich schon, daß das Ding halbwegs skalierbar wiederverwertbar wird. Wie ohne Zugriff auf den Heap?

heap-freak schrieb:

das war für ein gerät, in dem eine scriptsprache eingebaut ist, damit benutzer sich eigene programme basteln können, ...

Hab' einige Zeite mit FORTH gearbeitet - von Null anzufangen ist nichts einfacher, mich hat die Abkündigungswelle durch ROHS zu C getrieben. Für Scripting habe ich daher was FORTH- mäßiges gebastelt. Stacküberwachung und Function- Threading ist nicht so schlimm.

heap-freak schrieb:

da man sowas nicht selbst neu erfindet, hab' ich mir (nach langem suchen)

Was hast Du gefunden? Würde mich interessieren, echt ...

heap-freak schrieb:

als heap hab' ich 'ne schlanke implementation für S12-CPUs genommen, die so umgebaut, dass sie auf nem ARM7 läuft ...

Ich hab zu meinen bevorzugten CPUs zwar zumeist die Sourcen für malloc() und sonstige Verdächtige, aber da geht das Macro- Stacking bis nahe an die Auflösungsgrenze des Compilers, ich habe kapituliert und hingenommen, daß da irgendwo ein Pointer oder NULL rausfliegt.
Wenn Du Code hast, den man verstehen kann, wär' ein Link drauf sehr nett

[scripting-freak]

pointercrash() schrieb:

Was hast Du gefunden? Würde mich interessieren, echt ...

das hier: http://www.ibiblio.org/pub/micro/pc-stuff/freedos/files/devel/basic/basec/
braucht aber 'ne menge umbauarbeiten. es arbeitet im original mit 'double'-variablen und hat 2 bis 3 fiese bugs (u.a. vergessenes free()) drin. der vorteil ist, dass es aus compiler und bytecode-interpreter besteht (schnellere ausführung als ein textinterpreter) und alles wichtige hat, was ein basic-interpreter braucht. den heap poste ich nacher mal...

[heap-freak]

heap.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "heap.h"

//#define DEBUG_HEAP

/*---------------------------------------------------------------------------------
  MEMORY MANAGEMENT:
  ---------------------------------------------------------------------------------*/

#define ERR_HEAP_ALLOC  1     /* free-list destroyed; found while allocating */
#define ERR_HEAP_FREE   2     /* freeing already freed or destroyed block   */
#define ERR_HEAP_RANGE  3     /* freeing block outside of pool               */
#define ERR_HEAP_REALL  4     /* free list crashed; found while reallocating */

#define FREE  0x7067
#define USED  0x5047

/*****************************************************/

// Creates a heap
// h: A HEAP structure used to describe this heap
// mem: Points to memory for that heap
// size: Number of bytes of *mem
// failfunc: Callback function which is called on allocation failures
// crashfunc: Callback function which is called on heap crash 
void HEAP_Create (HEAP *h, unsigned char *mem, size_t size, void(*failfunc)(size_t), void(*crashfunc)(HEAP*, void *, int))
{
  h->_heap_ = mem;
  h->free_ptr = NULL;
  h->heap_end = NULL;
  h->size = size;
  h->failfunction = failfunc;
  h->crashfunction = crashfunc;
  memset (mem, 0, size);
}

/*****************************************************/

// Get memory block (at least nbytes of memory)
void *HEAP_malloc (HEAP *h, size_t nbytes)
{
  size_t    nunits;
  struct _HEAP_header *p, *pl;

  if (nbytes == 0)
  {
#ifdef DEBUG_HEAP
    printf ("HEAP_malloc: NULL!!!!");
#endif
    return NULL;
  }

  // make 4-aligned
  while (nbytes & 3)
    nbytes++;

  nunits = ((nbytes + sizeof (struct _HEAP_header) - 1) / sizeof (struct _HEAP_header)) + 1;

  if (h->heap_end == NULL)
  {

    /* setup heap */
    h->free_ptr = (struct _HEAP_header *) &(h->_heap_[0]);
    h->free_ptr->size = h->size / sizeof (struct _HEAP_header);
    h->free_ptr->next = NULL;
    h->free_ptr->inuse = FREE;
    h->heap_end = h->free_ptr + h->free_ptr->size - 1;
  }
  if (h->free_ptr == NULL)
  {
    h->failfunction (nbytes);
    return NULL;     /* free list is empty; no more memory */
  }
  else
  {
    pl = NULL;
    p = h->free_ptr;
    while (p != NULL)
    {
      if (p->size >= nunits)
      {
        if (p->size > nunits)
        {
          /* block is bigger, so break it */
          p[nunits].next = p->next;             /* link to next free block */
          p[nunits].size = p->size - nunits;    /* size of new free block  */
          p[nunits].inuse = FREE;
          p->size = nunits;       /* new size of block       */
          p->next = p + nunits;   /* ptr to next free block  */
        }
        if (pl == NULL)
        {
          /* we use the first block */
          h->free_ptr = p->next;
        }
        else
        {
          pl->next = p->next;
        }
        if (p->inuse != FREE)
        {
          h->crashfunction (h, p, ERR_HEAP_ALLOC);
        }
        p->next = NULL;
        p->inuse = USED;
#ifdef DEBUG_HEAP
        printf ("HEAP_malloc: %p %u bytes\n", p+1, nbytes);
#endif
        return ++p;
      }
      pl = p;
      p = p->next;    /* next block */
    }
  }

  h->failfunction (nbytes);
  return NULL;       /* All free blocks are to small */
}   /* end malloc */

/*****************************************************/

// Frees previously allocated memory block
void HEAP_free (HEAP *h, void *ap)
{
  struct _HEAP_header *p, *pNext, *pPrev, *pEnd, *pPrevEnd;

#ifdef DEBUG_HEAP
  printf ("HEAP_free: %p\n", ap);
#endif

  if (ap == NULL)
  {
    return;
  }
  p = (struct _HEAP_header *) ap;
  --p;
  if ((p < (struct _HEAP_header *) & h->_heap_[0]) || (p > h->heap_end))
  {
    h->crashfunction (h, p, ERR_HEAP_RANGE);
    return ;
  }
  if (p->inuse != USED)
  {
    h->crashfunction (h, p, ERR_HEAP_FREE);
  }

  p->inuse = FREE;
  p->next = NULL;

  if (h->free_ptr == NULL)
  {
    /* freelist is empty */
    h->free_ptr = p;
    return ;
  }

  pNext = h->free_ptr;
  pPrev = NULL;
  while (pNext != NULL && pNext < p)
  {
    pPrev = pNext;
    pNext = pNext->next;
  }   /* end while */

  pEnd = p + p->size;
  if (pNext == pEnd)     /* && pNext != NULL : pNext cannot be NULL because it is equal to pEnd */
  {
    /* concatenate p and pNext */
    p->size += pNext->size;
    p->next = pNext->next;
  }
  else if (pNext == p)
  {
    h->crashfunction (h, p, ERR_HEAP_FREE);      /* block to be released was already in free list */
  }
  else if (pEnd > pNext && pNext != NULL)
  {
    h->crashfunction (h, p, ERR_HEAP_FREE);      /* block to be released was completely contained in element in free list */
  }
  else
  {
    p->next = pNext;
  }
  if (pPrev == NULL)
  {
    /* p must be the first free block in the list */
    h->free_ptr = p;
    return ;
  }
  pPrevEnd = pPrev + pPrev->size;
  if (p == pPrevEnd)
  {
    /* concatenate pPrev and p */
    pPrev->size += p->size;
    pPrev->next = p->next;
    return ;
  }
  if (pPrevEnd > p)
  {
    h->crashfunction (h, p, ERR_HEAP_FREE);      /* start of block to be released was contained in element in free list */
    return;
  }
  pPrev->next = p;
}     /* end free */

/*****************************************************/

// Same as malloc but clears all bytes
// Total size is n * size
void *HEAP_calloc (HEAP *h, size_t n, size_t size)
{
  void  *save;

  size = n * size;
  save = HEAP_malloc (h, size);
  if (save != NULL)
  {
    (void)memset (save, 0, size);
  }

  return save;
}     /* end calloc */

/*****************************************************/

// Grows/shrinks prevously allocated block
// If ptr is NULL a new block will be allocated (behaves like malloc).
void *HEAP_realloc (HEAP *h, void *ptr, size_t size)
{
  size_t    nunits;
  struct _HEAP_header *p, *p1, *p2;
  void      *rv;

  if (ptr == NULL)
  {
    return HEAP_malloc (h, size);
  }

  if (size == 0)
  {
    HEAP_free (h, ptr);
    return NULL;
  }
  else
  {
    /* calculate size of new block in allocation units */
    nunits = ((size + sizeof (struct _HEAP_header) - 1) / sizeof (struct _HEAP_header)) + 1;

    p = (struct _HEAP_header *) ptr;
    --p;      /* get pointer to internal struct */

    if ((p < (struct _HEAP_header *) & h->_heap_[0]) || (p > h->heap_end))
    {
      h->crashfunction (h, p, ERR_HEAP_RANGE);
      return NULL;
    }

    if (p->size == nunits)
    {
      return ptr;      /* if new blocksizze == old; do nothing */
    }

    if (p->size > nunits)
    {     /* if new block will be smaller, so break it */
      p[nunits].size = p->size - nunits;      /* create new block */
      p[nunits].next = NULL;
      p[nunits].inuse = USED;           /* mark it used */

      p->size = nunits;                 /* resize old block */

      HEAP_free (h, p + nunits + 1);           /* free the new unused block */

      return ptr;
    }

    if ((p + p->size) < h->heap_end)
    {
      /* this is not the last block in pool */
      p1 = p + p->size;                 /* p1 = pointer to next block */
      if (p1->inuse == FREE)
      {
        /* the fallowing block is free !! */
        size = p1->size + p->size;      /* calculate size of cat-blocks */

        if (size > nunits)
        {
          /* the superblock will be to big, so break it */
          p2 = p + nunits;              /* p2 = pointer to new unused block */

          p2->next = p1->next;          /* break block and link them */
          p2->size = size - nunits;     /* together in the free list */
          p1->size -= p2->size;
          p2->inuse = FREE;
          p1->next = p2;

          size = nunits;
        }

        if (size == nunits)
        {
          /* unlink the next block from the free list and concatenate */
          if (h->free_ptr == p1)
          {
            /* it's the first pointer in free list */
            h->free_ptr = p1->next;        /* unlink the block */

            p->size += p1->size;        /* adjust size */
            return ++p;
          }

          p2 = h->free_ptr;
          while (p2->next != NULL)
          {
            /* search the block */
            if (p2->next == p1)
            {
              /* we found it */
              p2->next = p1->next;      /* unlink the block */

              p->size += p1->size;      /* adjust size */
              return ++p;
            }

            p2 = p2->next;
          }

          h->crashfunction (h, p1, ERR_HEAP_REALL);
        }
      }
    }

    /* There was no way to adjust the block size in place.
           The only chance left is to allocate a new block.
          */
    rv = HEAP_malloc (h, size);
    if (rv != NULL)
    {
      (void)memcpy (rv, ptr, size);
      HEAP_free (h, ptr);
    }
  }

  return rv;
}     /* end realloc */

// returns free meory
size_t HEAP_avail (HEAP *h)
{
    if (h->free_ptr == 0)
        return 0;
    return (h->heap_end - h->free_ptr) * sizeof(struct _HEAP_header);
}

//////////////////////////////////////////////////////

heap.h

#ifndef __HEAP__
#define __HEAP__

// HEAP structures
struct _HEAP_header
{
  unsigned int inuse;
  struct _HEAP_header *next;
  size_t size;
};

// HEAP object
typedef struct _heap
{
    struct _HEAP_header *heap_end;
    struct _HEAP_header *free_ptr;    
    unsigned char *_heap_;
    size_t size;
    void (*failfunction)(size_t size);
    void (*crashfunction)(struct _heap*, void *, int);
} HEAP;

// User callable functions 
void HEAP_Create (HEAP *h, unsigned char *mem, size_t size, void(*failfunc)(size_t), void(*crashfunc)(HEAP*, void *, int));
void *HEAP_malloc (HEAP *h, size_t nbytes);
void HEAP_free (HEAP *h, void *ap);
void *HEAP_calloc (HEAP *h, size_t n, size_t size);
void *HEAP_realloc (HEAP *h, void *ptr, size_t size);
size_t HEAP_avail (HEAP *h);

#endif // __HEAP__

dürfte alles selbsterklärend sein, ansonsten bitte fragen.

[pointercrash**]

heap-freak schrieb:

dürfte alles selbsterklärend sein, ansonsten bitte fragen.

Na, das schaut verständlich aus - hast also keine Belästigungen zu befürchten.
Also ein BASIC- Tokenizer steckt hinter Deiner Script- Maschine, wenn Du mal mehr Funktionalität brauchst, schau' Dir mal http://sourceforge.net/projects/pfe/ an. Ich hab' noch keine echte Einsatzmöglichkeit dafür gefunden, aber das Teil geht für 'nen Compreteransatz wirklich flott zur Sache .
EDIT: Wie unhöflich von mir ... Danke!!!