webentwicklung-frage-antwort-db.com.de

Erklären Sie diese Implementierung von Malloc aus dem K & R-Buch

Dies ist ein Auszug aus dem Buch über C von Kernighan und Ritchie . Es zeigt, wie Sie eine Version von malloc implementieren. Obwohl gut kommentiert, habe ich große Schwierigkeiten, es zu verstehen. Kann jemand es bitte erklären?

typedef long Align; /* for alignment to long boundary */
union header { /* block header */
struct {
union header *ptr; /* next block if on free list */
unsigned size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
};
typedef union header Header;

static Header base; /* empty list to get started */
static Header *freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void *malloc(unsigned nbytes)
{
   Header *p, *prevp;
   Header *morecore(unsigned);
   unsigned nunits;
   nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;
   if ((prevp = freep) == NULL) { /* no free list yet */
      base.s.ptr = freeptr = prevptr = &base;
      base.s.size = 0;
   }
   for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
      if (p->s.size >= nunits) { /* big enough */
        if (p->s.size == nunits) /* exactly */
           prevp->s.ptr = p->s.ptr;
        else { /* allocate tail end */
           p->s.size -= nunits;
           p += p->s.size;
           p->s.size = nunits
             }
        freep = prevp;
        return (void *)(p+1);
      }
      if (p == freep) /* wrapped around free list */
         if ((p = morecore(nunits)) == NULL)
             return NULL; /* none left */
      }
}

#define NALLOC 1024 /* minimum #units to request */
/* morecore: ask system for more memory */

static Header *morecore(unsigned nu)
{

  char *cp, *sbrk(int);
  Header *up;

  if (nu < NALLOC)
    nu = NALLOC;

  cp = sbrk(nu * sizeof(Header));

  if (cp == (char *) -1) /* no space at all */
    return NULL;

  up = (Header *) cp;
  up->s.size = nu;
  free((void *)(up+1));

  return freep;
}

/* free: put block ap in free list */
void free(void *ap) {
  Header *bp, *p;
  bp = (Header *)ap - 1; /* point to block header */
  for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
    if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
      break; /* freed block at start or end of arena */
  if (bp + bp->size == p->s.ptr) {
    bp->s.size += p->s.ptr->s.size;
    bp->s.ptr = p->s.ptr->s.ptr;
  } else
      bp->s.ptr = p->s.ptr;

  if (p + p->size == bp) {
    p->s.size += bp->s.size;
    p->s.ptr = bp->s.ptr;
  } else
    p->s.ptr = bp;
  freep = p;
}
27
SexyBeast

Ok, wir haben hier einen Teil wirklich schlecht geschriebenen Codes. Was ich in diesem Beitrag tun werde, lässt sich am besten als Software-Archäologie beschreiben.

Schritt 1: Korrigieren Sie die Formatierung.

Die Einrückung und das kompakte Format nützen niemandem. Verschiedene Leerzeichen und leere Zeilen müssen eingefügt werden. Die Kommentare könnten lesbarer geschrieben werden. Ich werde damit anfangen, das zu reparieren.

Gleichzeitig ändere ich den Orthesenstil von K & R - bitte beachten Sie, dass der K & R-Orthesenstil akzeptabel ist. Dies ist nur eine persönliche Präferenz von mir. Eine andere persönliche Präferenz ist, das * für Zeiger neben den Typ zu schreiben, auf den gezeigt wird. Ich werde hier nicht über (subjektive) Stilfragen streiten.

Auch die Typdefinition von Header ist völlig unlesbar, es bedarf einer drastischen Korrektur.

Und ich habe etwas völlig Dunkles entdeckt: Sie scheinen einen Funktionsprototyp innerhalb der Funktion deklariert zu haben. Header* morecore(unsigned);. Dies ist ein sehr alter und sehr schlechter Stil, und ich bin mir nicht sicher, ob C es überhaupt noch zulässt. Entfernen wir einfach diese Zeile, was auch immer diese Funktion tut, sie muss an einer anderen Stelle definiert werden.

typedef long Align;                      /* for alignment to long boundary */

typedef union header                     /* block header */
{
  struct
  {
    union header *ptr;                   /* next block if on free list */
    unsigned size;                       /* size of this block */
  } s;

  Align x;                               /* force alignment of blocks */

} Header;


static Header base;                      /* empty list to get started */
static Header* freep = NULL;             /* start of free list */


/* malloc: general-purpose storage allocator */
void* malloc (unsigned nbytes)
{
  Header*   p;
  Header*   prevp;
  unsigned  nunits;

  nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;

  if ((prevp = freep) == NULL)           /* no free list yet */
  {
    base.s.ptr = freeptr = prevptr = &base;
    base.s.size = 0;
  }

  for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
  {
    if (p->s.size >= nunits)             /* big enough */
    {
      if (p->s.size == nunits)           /* exactly */
        prevp->s.ptr = p->s.ptr;
      else                               /* allocate tail end */
      {
        p->s.size -= nunits;
        p += p->s.size;
        p->s.size = nunits
      }

      freep = prevp;
      return (void *)(p+1);
    }

    if (p == freep)                      /* wrapped around free list */
      if ((p = morecore(nunits)) == NULL)
        return NULL;                     /* none left */
  }
}

Ok, jetzt können wir den Code möglicherweise tatsächlich lesen.

Schritt 2: weithin anerkannte schlechte Praktiken ausmerzen.

Dieser Code ist mit Dingen gefüllt, die heutzutage als schlechte Praxis angesehen werden. Sie müssen entfernt werden, da sie die Sicherheit, Lesbarkeit und Wartung des Codes gefährden. Wenn Sie einen Verweis auf eine Behörde wünschen, die dieselben Praktiken wie ich predigt, lesen Sie den allgemein anerkannten Kodierungsstandard MISRA-C .

Ich habe die folgenden schlechten Praktiken entdeckt und beseitigt:

1) Nur die Eingabe von unsigned im Code kann zu Verwirrung führen: War dies ein Tippfehler des Programmierers oder die Absicht, unsigned int zu schreiben? Wir sollten alle unsigned durch unsigned int ersetzen. Dabei stellen wir jedoch fest, dass es in diesem Zusammenhang verwendet wird, um die Größe verschiedener Binärdaten anzugeben. Der richtige Typ für solche Angelegenheiten ist der C-Standardtyp size_t. Dies ist im Grunde auch nur ein Int ohne Vorzeichen, aber es ist garantiert "groß genug" für die bestimmte Plattform. Der Operator sizeof gibt ein Ergebnis vom Typ size_t zurück, und wenn wir uns die Definition des realen Mallocs nach dem C-Standard ansehen, ist dies void *malloc(size_t size);. Daher ist size_t der am besten zu verwendende Typ.

2) Es ist eine schlechte Idee, für unsere eigene Malloc-Funktion denselben Namen zu verwenden wie für die in stdlib.h. Sollten wir stdlib.h einbinden müssen, wird es chaotisch. Verwenden Sie als Faustregel niemals Bezeichnernamen von C-Standardbibliotheksfunktionen in Ihrem eigenen Code. Ich werde den Namen in kr_malloc ändern.

3) Der Code missbraucht die Tatsache, dass alle statischen Variablen garantiert auf Null initialisiert werden. Dies ist durch den C-Standard gut definiert, aber eine ziemlich subtile Regel. Initialisieren wir alle Statiken explizit, um zu zeigen, dass wir nicht vergessen haben, sie versehentlich zu initialisieren.

4) Die Zuordnung innerhalb von Bedingungen ist gefährlich und schwer zu lesen. Dies sollte nach Möglichkeit vermieden werden, da es auch zu Fehlern wie dem klassischen = vs == Fehler kommen kann.

5) Mehrfachzuweisungen in derselben Zeile sind aufgrund der Reihenfolge der Auswertung schwer lesbar und möglicherweise auch gefährlich.

6) Mehrere Deklarationen in derselben Zeile sind schwer zu lesen und gefährlich, da es beim Mischen von Daten und Zeigerdeklarationen zu Fehlern kommen kann. Deklarieren Sie jede Variable immer in einer eigenen Zeile.

7) Verwendet nach jeder Anweisung immer geschweifte Klammern. Nichtbeachtung führt zu Fehlern, Bugs, Bugs.

8) Geben Sie niemals cast von einem bestimmten Zeigertyp in void * ein. In C ist dies nicht erforderlich und kann Fehler verbergen, die der Compiler sonst entdeckt hätte.

9) Vermeiden Sie die Verwendung mehrerer return-Anweisungen in einer Funktion. Manchmal führen sie zu klarerem Code, in den meisten Fällen jedoch zu Spaghetti. Gegenwärtig können wir das nicht ändern, ohne die Schleife neu zu schreiben. Ich werde das später beheben.

10) Halten Sie for-Schleifen einfach. Sie sollten eine Init-Anweisung, eine Schleifenbedingung und eine Iteration enthalten, sonst nichts. Diese for-Schleife mit dem Kommaoperator und allem ist sehr dunkel. Auch hier sehen wir die Notwendigkeit, diese Schleife in etwas Vernünftiges umzuschreiben. Ich mache das als nächstes, aber jetzt haben wir:

typedef long Align;                      /* for alignment to long boundary */

typedef union header                     /* block header */
{
  struct
  {
    union header *ptr;                   /* next block if on free list */
    size_t size;                         /* size of this block */
  } s;

  Align x;                               /* force alignment of blocks */

} Header;


static Header base = {0};                /* empty list to get started */
static Header* freep = NULL;             /* start of free list */


/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
  Header*  p;
  Header*  prevp;
  size_t   nunits;

  nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;

  prevp = freep;
  if (prevp == NULL)                     /* no free list yet */
  {
    base.s.ptr  = &base;
    freeptr     = &base;
    prevptr     = &base;
    base.s.size = 0;
  }

  for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
  {
    if (p->s.size >= nunits)             /* big enough */
    {
      if (p->s.size == nunits)           /* exactly */
      {
        prevp->s.ptr = p->s.ptr;
      }
      else                               /* allocate tail end */
      {
        p->s.size -= nunits;
        p += p->s.size;
        p->s.size = nunits
      }

      freep = prevp;
      return p+1;
    }

    if (p == freep)                      /* wrapped around free list */
    {
      p = morecore(nunits);
      if (p == NULL)
      {
        return NULL;                     /* none left */
      }
    }
  } /* for */
}

Schritt 3: Schreiben Sie die obskure Schleife neu.

Aus den zuvor genannten Gründen. Wir können sehen, dass diese Schleife für immer weitergeht. Sie endet, indem sie von der Funktion zurückkehrt, entweder wenn die Zuordnung abgeschlossen ist oder wenn kein Speicher mehr vorhanden ist. Lassen Sie uns das also als Schleifenbedingung erstellen und die Rückkehr an das Ende der Funktion heben, wo sie sein sollte. Und lassen Sie uns diesen hässlichen Kommaoperator loswerden.

Ich werde zwei neue Variablen einführen: eine Ergebnisvariable, um den resultierenden Zeiger zu halten, und eine andere, um zu verfolgen, ob die Schleife fortgesetzt werden soll oder nicht. Ich werde K & R um den Verstand bringen, indem ich den Typ bool verwende, der seit 1999 Teil der Sprache C ist.

(Ich hoffe, ich habe den Algorithmus mit dieser Änderung nicht geändert, ich glaube, ich habe nicht)

#include <stdbool.h>

typedef long Align;                      /* for alignment to long boundary */

typedef union header                     /* block header */
{
  struct
  {
    union header *ptr;                   /* next block if on free list */
    size_t size;                         /* size of this block */
  } s;

  Align x;                               /* force alignment of blocks */

} Header;


static Header base = {0};                /* empty list to get started */
static Header* freep = NULL;             /* start of free list */


/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
  Header*  p;
  Header*  prevp;
  size_t   nunits;
  void*    result;
  bool     is_allocating;

  nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;

  prevp = freep;
  if (prevp == NULL)                     /* no free list yet */
  {
    base.s.ptr  = &base;
    freeptr     = &base;
    prevptr     = &base;
    base.s.size = 0;
  }

  is_allocating = true;
  for (p = prevp->s.ptr; is_allocating; p = p->s.ptr)
  {
    if (p->s.size >= nunits)             /* big enough */
    {
      if (p->s.size == nunits)           /* exactly */
      {
        prevp->s.ptr = p->s.ptr;
      }
      else                               /* allocate tail end */
      {
        p->s.size -= nunits;
        p += p->s.size;
        p->s.size = nunits
      }

      freep = prevp;
      result = p+1;
      is_allocating = false;             /* we are done */
    }

    if (p == freep)                      /* wrapped around free list */
    {
      p = morecore(nunits);
      if (p == NULL)
      {
        result = NULL;                   /* none left */
        is_allocating = false;
      }
    }
    prevp = p;
  } /* for */

  return result;
}

Schritt 4: Machen Sie diesen Mist kompilieren.

Da dies von K & R stammt, ist es mit Tippfehlern gefüllt. sizeof(header) sollte sizeof(Header) sein. Es fehlen Semikolons. Sie verwenden unterschiedliche Namen freep, prevp versus freeptr, prevptr, bedeuten aber eindeutig die gleiche Variable. Ich glaube, die letzteren waren eigentlich bessere Namen, also lasst uns diese verwenden.

#include <stdbool.h>

typedef long Align;                      /* for alignment to long boundary */

typedef union header                     /* block header */
{
  struct
  {
    union header *ptr;                   /* next block if on free list */
    size_t size;                         /* size of this block */
  } s;

  Align x;                               /* force alignment of blocks */

} Header;


static Header base = {0};                /* empty list to get started */
static Header* freeptr = NULL;           /* start of free list */


/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
  Header*  p;
  Header*  prevptr;
  size_t   nunits;
  void*    result;
  bool     is_allocating;

  nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

  prevptr = freeptr;
  if (prevptr == NULL)                   /* no free list yet */
  {
    base.s.ptr  = &base;
    freeptr     = &base;
    prevptr     = &base;
    base.s.size = 0;
  }

  is_allocating = true;
  for (p = prevptr->s.ptr; is_allocating; p = p->s.ptr)
  {
    if (p->s.size >= nunits)             /* big enough */
    {
      if (p->s.size == nunits)           /* exactly */
      {
        prevptr->s.ptr = p->s.ptr;
      }
      else                               /* allocate tail end */
      {
        p->s.size -= nunits;
        p += p->s.size;
        p->s.size = nunits;
      }

      freeptr = prevptr;
      result = p+1;
      is_allocating = false;             /* we are done */
    }

    if (p == freeptr)                    /* wrapped around free list */
    {
      p = morecore(nunits);
      if (p == NULL)
      {
        result = NULL;                   /* none left */
        is_allocating = false;
      }
    }
    prevptr = p;
  } /* for */

  return result;
}

Und jetzt haben wir etwas lesbaren, wartbaren Code ohne zahlreiche gefährliche Methoden, der sogar kompiliert werden kann! Jetzt könnten wir uns tatsächlich Gedanken darüber machen, was der Code tatsächlich tut.

Die Struktur "Header" ist, wie Sie vielleicht erraten haben, die Deklaration eines Knotens in einer verknüpften Liste. Jeder dieser Knoten enthält einen Zeiger auf den nächsten. Ich verstehe weder die Morecore-Funktion noch das "Wrap-Around", ich habe diese Funktion noch sbrk noch nie verwendet. Aber ich gehe davon aus, dass es einen Header wie in dieser Struktur angegeben und auch einen Teil der Rohdaten nach diesem Header zuweist. Wenn dies der Fall ist, wird erklärt, warum es keinen tatsächlichen Datenzeiger gibt: Es wird angenommen, dass die Daten dem Header benachbart im Speicher folgen. Für jeden Knoten erhalten wir den Header und nach dem Header einen Teil der Rohdaten.

Die Iteration selbst ist ziemlich unkompliziert. Sie durchlaufen jeweils einen Knoten einer einzelnen verknüpften Liste.

Am Ende der Schleife setzen sie den Zeiger auf einen Punkt nach dem Ende des "Chunks" und speichern ihn dann in einer statischen Variablen, damit das Programm beim nächsten Aufruf der Funktion merkt, wo es zuvor Speicher zugewiesen hat.

Sie verwenden einen Trick, um ihren Header auf eine ausgerichtete Speicheradresse zu bringen: Sie speichern alle Overhead-Informationen in einer Union zusammen mit einer Variablen, die groß genug ist, um den Ausrichtungsanforderungen der Plattform zu entsprechen. Wenn also die Größe von "ptr" plus die Größe von "size" zu klein sind, um die exakte Ausrichtung zu ermöglichen, garantiert die Vereinigung, dass mindestens die Größe von (Ausrichten) Bytes zugewiesen wird. Ich glaube, dass dieser ganze Trick heute überholt ist, da der C-Standard automatisches Struktur-/Vereinigungs-Auffüllen vorschreibt.

58
Lundin

Ich studiere K & R, weil ich mir vorstellen konnte, dass OP diese Frage stellte, und ich kam hierher, weil ich auch diese Implementierungen als verwirrend empfand. Während die akzeptierte Antwort sehr detailliert und hilfreich ist, habe ich versucht, einen anderen Ansatz zu verwenden, um den Code so zu verstehen, wie er ursprünglich geschrieben wurde. Ich habe den Code durchgearbeitet und den Abschnitten des Codes Kommentare hinzugefügt, die für mich schwierig waren . Dies beinhaltet Code für die anderen Routinen in diesem Abschnitt (dies sind die Funktionen free und memcore - Ich habe sie in kandr_malloc und kandr_free umbenannt, um Konflikte mit der stdlib zu vermeiden). Ich dachte, ich würde dies hier als Ergänzung zu der akzeptierten Antwort lassen, für andere Studenten, die es hilfreich finden könnten.

Ich gebe zu, dass die Kommentare in diesem Code übertrieben sind. Bitte beachten Sie, dass ich dies nur als Lernübung mache und nicht vorschlage, dass dies ein guter Weg ist, um tatsächlich Code zu schreiben.

Ich erlaubte mir, einige Variablennamen in Namen zu ändern, die mir intuitiver erschienen. ansonsten bleibt der Code im Wesentlichen erhalten. Es scheint für die von mir verwendeten Testprogramme zu kompilieren und zu laufen, obwohl Valgrind bei einigen Anwendungen Beschwerden hatte.

Außerdem: Ein Teil des Textes in den Kommentaren wird direkt von K & R oder den Manpages abgehoben. Ich habe nicht vor, diesen Abschnitten irgendwelche Anerkennung zukommen zu lassen.

#include <unistd.h>  // sbrk

#define NALLOC 1024  // Number of block sizes to allocate on call to sbrk
#ifdef NULL
#undef NULL
#endif
#define NULL 0


// long is chosen as an instance of the most restrictive alignment type
typedef long Align;

/* Construct Header data structure.  To ensure that the storage returned by
 * kandr_malloc is aligned properly for the objects that are stored in it, all
 * blocks are multiples of the header size, and the header itself is aligned
 * properly.  This is achieved through the use of a union; this data type is big
 * enough to hold the "widest" member, and the alignment is appropriate for all
 * of the types in the union.  Thus by including a member of type Align, which
 * is an instance of the most restrictive type, we guarantee that the size of
 * Header is aligned to the worst-case boundary.  The Align field is never used;
 * it just forces each header to the desired alignment.
 */
union header {
  struct {
    union header *next;
    unsigned size;
  } s;

  Align x;
};
typedef union header Header;


static Header base;           // Used to get an initial member for free list
static Header *freep = NULL;  // Free list starting point


static Header *morecore(unsigned nblocks);
void kandr_free(void *ptr);




void *kandr_malloc(unsigned nbytes) {

  Header *currp;
  Header *prevp;
  unsigned nunits;

  /* Calculate the number of memory units needed to provide at least nbytes of
   * memory.
   *
   * Suppose that we need n >= 0 bytes and that the memory unit sizes are b > 0
   * bytes.  Then n / b (using integer division) yields one less than the number
   * of units needed to provide n bytes of memory, except in the case that n is
   * a multiple of b; then it provides exactly the number of units needed.  It
   * can be verified that (n - 1) / b provides one less than the number of units
   * needed to provide n bytes of memory for all values of n > 0.  Thus ((n - 1)
   * / b) + 1 provides exactly the number of units needed for n > 0.
   *
   * The extra sizeof(Header) in the numerator is to include the unit of memory
   * needed for the header itself.
   */
  nunits = ((nbytes + sizeof(Header) - 1) / sizeof(Header)) + 1;

  // case: no free list yet exists; we have to initialize.
  if (freep == NULL) {

    // Create degenerate free list; base points to itself and has size 0
    base.s.next = &base;
    base.s.size = 0;

    // Set free list starting point to base address
    freep = &base;
  }

  /* Initialize pointers to two consecutive blocks in the free list, which we
   * call prevp (the previous block) and currp (the current block)
   */
  prevp = freep;
  currp = prevp->s.next;

  /* Step through the free list looking for a block of memory large enough to
   * fit nunits units of memory into.  If the whole list is traversed without
   * finding such a block, then morecore is called to request more memory from
   * the OS.
   */
  for (; ; prevp = currp, currp = currp->s.next) {

    /* case: found a block of memory in free list large enough to fit nunits
     * units of memory into.  Partition block if necessary, remove it from the
     * free list, and return the address of the block (after moving past the
     * header).
     */
    if (currp->s.size >= nunits) {

      /* case: block is exactly the right size; remove the block from the free
       * list by pointing the previous block to the next block.
       */
      if (currp->s.size == nunits) {
    /* Note that this line wouldn't work as intended if we were down to only
     * 1 block.  However, we would never make it here in that scenario
     * because the block at &base has size 0 and thus the conditional will
     * fail (note that nunits is always >= 1).  It is true that if the block
     * at &base had combined with another block, then previous statement
     * wouldn't apply - but presumably since base is a global variable and
     * future blocks are allocated on the heap, we can be sure that they
     * won't border each other.
     */
    prevp->s.next = currp->s.next;
      }
      /* case: block is larger than the amount of memory asked for; allocate
       * tail end of the block to the user.
       */
      else {
    // Changes the memory stored at currp to reflect the reduced block size
    currp->s.size -= nunits;
    // Find location at which to create the block header for the new block
    currp += currp->s.size;
    // Store the block size in the new header
    currp->s.size = nunits;
      }

      /* Set global starting position to the previous pointer.  Next call to
       * malloc will start either at the remaining part of the partitioned block
       * if a partition occurred, or at the block after the selected block if
       * not.
       */
      freep = prevp;

      /* Return the location of the start of the memory, i.e. after adding one
       * so as to move past the header
       */
      return (void *) (currp + 1);

    } // end found a block of memory in free list case

    /* case: we've wrapped around the free list without finding a block large
     * enough to fit nunits units of memory into.  Call morecore to request that
     * at least nunits units of memory are allocated.
     */
    if (currp == freep) {
      /* morecore returns freep; the reason that we have to assign currp to it
       * again (since we just tested that they are equal), is that there is a
       * call to free inside of morecore that can potentially change the value
       * of freep.  Thus we reassign it so that we can be assured that the newly
       * added block is found before (currp == freep) again.
       */
      if ((currp = morecore(nunits)) == NULL) {
    return NULL;
      }
    } // end wrapped around free list case
  } // end step through free list looking for memory loop
}




static Header *morecore(unsigned nunits) {

  void *freemem;    // The address of the newly created memory
  Header *insertp;  // Header ptr for integer arithmatic and constructing header

  /* Obtaining memory from OS is a comparatively expensive operation, so obtain
   * at least NALLOC blocks of memory and partition as needed
   */
  if (nunits < NALLOC) {
    nunits = NALLOC;
  }

  /* Request that the OS increment the program's data space.  sbrk changes the
   * location of the program break, which defines the end of the process's data
   * segment (i.e., the program break is the first location after the end of the
   * uninitialized data segment).  Increasing the program break has the effect
   * of allocating memory to the process.  On success, brk returns the previous
   * break - so if the break was increased, then this value is a pointer to the
   * start of the newly allocated memory.
   */
  freemem = sbrk(nunits * sizeof(Header));
  // case: unable to allocate more memory; sbrk returns (void *) -1 on error
  if (freemem == (void *) -1) {
    return NULL;
  }

  // Construct new block
  insertp = (Header *) freemem;
  insertp->s.size = nunits;

  /* Insert block into the free list so that it is available for malloc.  Note
   * that we add 1 to the address, effectively moving to the first position
   * after the header data, since of course we want the block header to be
   * transparent for the user's interactions with malloc and free.
   */
  kandr_free((void *) (insertp + 1));

  /* Returns the start of the free list; recall that freep has been set to the
   * block immediately preceeding the newly allocated memory (by free).  Thus by
   * returning this value the calling function can immediately find the new
   * memory by following the pointer to the next block.
   */
  return freep;
}




void kandr_free(void *ptr) {

  Header *insertp, *currp;

  // Find address of block header for the data to be inserted
  insertp = ((Header *) ptr) - 1;

  /* Step through the free list looking for the position in the list to place
   * the insertion block.  In the typical circumstances this would be the block
   * immediately to the left of the insertion block; this is checked for by
   * finding a block that is to the left of the insertion block and such that
   * the following block in the list is to the right of the insertion block.
   * However this check doesn't check for one such case, and misses another.  We
   * still have to check for the cases where either the insertion block is
   * either to the left of every other block owned by malloc (the case that is
   * missed), or to the right of every block owned by malloc (the case not
   * checked for).  These last two cases are what is checked for by the
   * condition inside of the body of the loop.
   */
  for (currp = freep; !((currp < insertp) && (insertp < currp->s.next)); currp = currp->s.next) {

    /* currp >= currp->s.ptr implies that the current block is the rightmost
     * block in the free list.  Then if the insertion block is to the right of
     * that block, then it is the new rightmost block; conversely if it is to
     * the left of the block that currp points to (which is the current leftmost
     * block), then the insertion block is the new leftmost block.  Note that
     * this conditional handles the case where we only have 1 block in the free
     * list (this case is the reason that we need >= in the first test rather
     * than just >).
     */
    if ((currp >= currp->s.next) && ((currp < insertp) || (insertp < currp->s.next))) {
      break;
    }
  }

  /* Having found the correct location in the free list to place the insertion
   * block, now we have to (i) link it to the next block, and (ii) link the
   * previous block to it.  These are the tasks of the next two if/else pairs.
   */

  /* case: the end of the insertion block is adjacent to the beginning of
   * another block of data owned by malloc.  Absorb the block on the right into
   * the block on the left (i.e. the previously existing block is absorbed into
   * the insertion block).
   */
  if ((insertp + insertp->s.size) == currp->s.next) {
    insertp->s.size += currp->s.next->s.size;
    insertp->s.next = currp->s.next->s.next;
  }
  /* case: the insertion block is not left-adjacent to the beginning of another
   * block of data owned by malloc.  Set the insertion block member to point to
   * the next block in the list.
   */
  else {
    insertp->s.next = currp->s.next;
  }

  /* case: the end of another block of data owned by malloc is adjacent to the
   * beginning of the insertion block.  Absorb the block on the right into the
   * block on the left (i.e. the insertion block is absorbed into the preceeding
   * block).
   */
  if ((currp + currp->s.size) == insertp) {
    currp->s.size += insertp->s.size;
    currp->s.next = insertp->s.next;
  }
  /* case: the insertion block is not right-adjacent to the end of another block
   * of data owned by malloc.  Set the previous block in the list to point to
   * the insertion block.
   */
  else {
    currp->s.next = insertp;
  }

  /* Set the free pointer list to start the block previous to the insertion
   * block.  This makes sense because calls to malloc start their search for
   * memory at the next block after freep, and the insertion block has as good a
   * chance as any of containing a reasonable amount of memory since we've just
   * added some to it.  It also coincides with calls to morecore from
   * kandr_malloc because the next search in the iteration looks at exactly the
   * right memory block.
   */
  freep = currp;
}
26
dpritch

Die Grundlagen von Malloc ()

In Linux gibt es zwei typische Möglichkeiten, um Speicher abzufragen: sbrk und mmap . Diese Systemaufrufe haben starke Einschränkungen bei häufigen kleinen Zuweisungen. malloc () ist eine Bibliotheksfunktion, um dieses Problem zu beheben. Es fordert große Speicherbereiche mit Sbrk/mmap an und gibt kleine Speicherblöcke in großen Abschnitten zurück. Dies ist wesentlich effizienter und flexibler als das direkte Anrufen von sbrk/mmap.

K & R Malloc ()

In der K & R-Implementierung ist ein Kern (häufiger als arena bezeichnet) ein großer Speicherblock. morecore() fordert einen Kern über sbrk() vom System an. Wenn Sie malloc ()/free () mehrmals aufrufen, werden einige Blöcke in den Kernen verwendet/zugewiesen, während andere frei sind. K & R malloc speichert die Adressen der freien Blöcke in einer circular - Einzelverknüpfungsliste. In dieser Liste ist jeder Knoten ein Block mit freiem Speicher. Die ersten sizeof(Header)-Bytes behalten die Größe des Blocks und den Zeiger auf den nächsten freien Block. Die restlichen Bytes im freien Block werden nicht initialisiert. Im Gegensatz zu typischen Listen in Lehrbüchern sind Knoten in der freien Liste lediglich Verweise auf einige nicht verwendete Bereiche in Kernen. Sie ordnen nicht tatsächlich jeden Knoten außer Kernen zu. Diese Liste ist der Schlüssel zum Verständnis des Algorithmus.

Das folgende Diagramm zeigt ein Beispiel für ein Speicherlayout mit zwei Kernen/Arenen. In dem Diagramm benötigt jedes Zeichen sizeof(Header) Bytes. @ ist eine Header, + kennzeichnet den zugewiesenen Speicher und - den freien Speicherplatz in den Kernen. Im Beispiel gibt es drei zugeordnete Blöcke und drei freie Blöcke. Die drei freien Blöcke werden in der Zirkelliste gespeichert. Für die drei zugewiesenen Blöcke werden nur ihre Größen in Header gespeichert.

            This is core 1                             This is core 2

@[email protected][email protected]++++++++++++        @[email protected][email protected]
|                                        |                            |
p->ptr->ptr                              p = p->ptr->ptr->ptr         p->ptr

In Ihrem Code ist freep ein Einstiegspunkt in die freie Liste. Wenn Sie wiederholt freep->ptr folgen, kehren Sie zu freep zurück - es ist zirkulär. Wenn Sie die kreisförmige, einfach verknüpfte Liste verstanden haben, ist der Rest relativ einfach. malloc() findet einen freien Block und teilt ihn möglicherweise auf. free() fügt der Liste einen freien Block hinzu und fügt ihn möglicherweise zu benachbarten freien Blöcken zusammen. Beide versuchen, die Struktur der Liste zu erhalten.

Weitere Kommentare zur Implementierung

  • Die Code-Kommentare, die in malloc() "umbrochen" erwähnt wurden Diese Zeile tritt auf, wenn Sie die gesamte freie Liste durchlaufen haben, aber keinen freien Block finden können, der die angeforderte Länge überschreitet. In diesem Fall müssen Sie mit morecore() einen neuen Kern hinzufügen.

  • base ist ein nullgroßer Block, der immer in der freien Liste enthalten ist. Es ist ein Trick, um spezielle Gehäuse zu vermeiden. Es ist nicht unbedingt notwendig.

  • free() kann etwas komplex erscheinen, da vier verschiedene Fälle berücksichtigt werden müssen, um einen neu freigegebenen Block mit anderen freien Blöcken in der Liste zusammenzuführen. Dieses Detail ist nicht so wichtig, es sei denn, Sie möchten es selbst neu implementieren.

  • Dieser Blogbeitrag erläutert K & R Malloc in weiteren Einzelheiten.

PS: K & R Malloc ist meiner Meinung nach eines der elegantesten Codestücke. Es war wirklich eine Augenöffnung, als ich den Code zum ersten Mal verstanden hatte. Es macht mich traurig, dass einige moderne Programmierer, die die Grundlagen dieser Implementierung nicht einmal verstehen, den Meisterstück nur aufgrund ihres Codierstils bezeichnen.

7
user172818

Ich fand diese Übung auch großartig und interessant.

Meiner Meinung nach kann das Visualisieren der Struktur sehr hilfreich sein, um die Logik zu verstehen - oder zumindest hat dies für mich funktioniert. Unten ist mein Code, der so viel wie möglich über den Ablauf des K & R Malloc druckt.

Die bedeutendste Änderung, die ich im K & R-Malloc vorgenommen habe, ist die Änderung von 'free', um sicherzustellen, dass alte Zeiger nicht mehr verwendet werden. Ansonsten habe ich Kommentare hinzugefügt und einige kleine Tippfehler behoben.

Das Experimentieren mit NALLOC, MAXMEM und den Testvariablen in 'main' könnte ebenfalls hilfreich sein.

Auf meinem Rechner (Ubuntu 16.04.3) wurde dies fehlerfrei mit kompiliert:

gcc -g -std=c99 -Wall -Wextra -pedantic-errors krmalloc.c

krmalloc.c:

#include <stdio.h>
#include <unistd.h>

typedef long Align;             /* for alignment to long boundary */
union header {                  /* block header */
    struct {
        union header *ptr;      /* next block if on free list */
        size_t size;            /* size of this block */
                                /*      including the Header itself */
                                /*      measured in count of Header chunks */
                                /*      not less than NALLOC Header's */
    } s;
    Align x;                    /* force alignment of blocks */
};
typedef union header Header;

static Header *morecore(size_t);
void *mmalloc(size_t);
void _mfree(void **);
void visualize(const char*);
size_t getfreem(void);
size_t totmem = 0;              /* total memory in chunks */

static Header base;             /* empty list to get started */
static Header *freep = NULL;    /* start of free list */

#define NALLOC 1                /* minimum chunks to request */
#define MAXMEM 2048             /* max memory available (in bytes) */

#define mfree(p) _mfree((void **)&p)

void *sbrk(__intptr_t incr);


int main(void)
{
    char *pc, *pcc, *pccc, *ps;
    long *pd, *pdd;
    int dlen = 100;
    int ddlen = 50;

    visualize("start");


    /* trying to fragment as much as possible to get a more interesting view */

    /* claim a char */
    if ((pc = (char *) mmalloc(sizeof(char))) == NULL)
        return -1;

    /* claim a string */
    if ((ps = (char *) mmalloc(dlen * sizeof(char))) == NULL)
        return -1;

    /* claim some long's */
    if ((pd = (long *) mmalloc(ddlen * sizeof(long))) == NULL)
        return -1;

    /* claim some more long's */
    if ((pdd = (long *) mmalloc(ddlen * 2 * sizeof(long))) == NULL)
        return -1;

    /* claim one more char */
    if ((pcc = (char *) mmalloc(sizeof(char))) == NULL)
        return -1;

    /* claim the last char */
    if ((pccc = (char *) mmalloc(sizeof(char))) == NULL)
        return -1;


    /* free and visualize */
    printf("\n");
    mfree(pccc);
    /*      bugged on purpose to test free(NULL) */
    mfree(pccc);
    visualize("free(the last char)");

    mfree(pdd);
    visualize("free(lot of long's)");

    mfree(ps);
    visualize("free(string)");

    mfree(pd);
    visualize("free(less long's)");

    mfree(pc);
    visualize("free(first char)");

    mfree(pcc);
    visualize("free(second char)");


    /* check memory condition */
    size_t freemem = getfreem();
    printf("\n");
    printf("--- Memory claimed  : %ld chunks (%ld bytes)\n",
                totmem, totmem * sizeof(Header));
    printf("    Free memory now : %ld chunks (%ld bytes)\n",
                freemem, freemem * sizeof(Header));
    if (freemem == totmem)
        printf("    No memory leaks detected.\n");
    else
        printf("    (!) Leaking memory: %ld chunks (%ld bytes).\n",
                    (totmem - freemem), (totmem - freemem) * sizeof(Header));

    printf("// Done.\n\n");
    return 0;
}


/* visualize: print the free list (educational purpose) */
void visualize(const char* msg)
{
    Header *tmp;

    printf("--- Free list after \"%s\":\n", msg);

    if (freep == NULL) {                   /* does not exist */
        printf("\tList does not exist\n\n");
        return;
    }

    if  (freep == freep->s.ptr) {          /* self-pointing list = empty */
        printf("\tList is empty\n\n");
        return;
    }

    printf("  ptr: %10p size: %-3lu -->  ", (void *) freep, freep->s.size);

    tmp = freep;                           /* find the start of the list */
    while (tmp->s.ptr > freep) {           /* traverse the list */
        tmp = tmp->s.ptr;
        printf("ptr: %10p size: %-3lu -->  ", (void *) tmp, tmp->s.size);
    }
    printf("end\n\n");
}


/* calculate the total amount of available free memory */
size_t getfreem(void)
{
    if (freep == NULL)
        return 0;

    Header *tmp;
    tmp = freep;
    size_t res = tmp->s.size;

    while (tmp->s.ptr > tmp) {
        tmp = tmp->s.ptr;
        res += tmp->s.size;
    }

    return res;
}


/* mmalloc: general-purpose storage allocator */
void *mmalloc(size_t nbytes)
{
    Header *p, *prevp;
    size_t nunits;

    /* smallest count of Header-sized memory chunks */
    /*  (+1 additional chunk for the Header itself) needed to hold nbytes */
    nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

    /* too much memory requested? */
    if (((nunits + totmem + getfreem())*sizeof(Header)) > MAXMEM) {
        printf("Memory limit overflow!\n");
        return NULL;
    }

    if ((prevp = freep) == NULL) {          /* no free list yet */
        /* set the list to point to itself */
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }

    /* traverse the circular list */
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {

        if (p->s.size >= nunits) {          /* big enough */
            if (p->s.size == nunits)        /* exactly */
                prevp->s.ptr = p->s.ptr;
            else {                          /* allocate tail end */
                /* adjust the size */
                p->s.size -= nunits;
                /* find the address to return */
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p+1);
        }

        /* back where we started and nothing found - we need to allocate */
        if (p == freep)                     /* wrapped around free list */
            if ((p = morecore(nunits)) == NULL)
                return NULL;                /* none left */
    }
}


/* morecore: ask system for more memory */
/*      nu: count of Header-chunks needed */
static Header *morecore(size_t nu)
{
    char *cp;
    Header *up;

    /* get at least NALLOC Header-chunks from the OS */
    if (nu < NALLOC)
        nu = NALLOC;

    cp = (char *) sbrk(nu * sizeof(Header));

    if (cp == (char *) -1)                  /* no space at all */
        return NULL;

    printf("... (sbrk) claimed %ld chunks.\n", nu);
    totmem += nu;                           /* keep track of allocated memory */

    up = (Header *) cp;
    up->s.size = nu;

    /* add the free space to the circular list */
    void *n = (void *)(up+1);
    mfree(n);

    return freep;
}


/* mfree: put block ap in free list */
void _mfree(void **ap)
{
    if (*ap == NULL)
        return;

    Header *bp, *p;
    bp = (Header *)*ap - 1;                 /* point to block header */

    if (bp->s.size == 0 || bp->s.size > totmem) {
        printf("_mfree: impossible value for size\n");
        return;
    }

    /* the free space is only marked as free, but 'ap' still points to it */
    /* to avoid reusing this address and corrupt our structure set it to '\0' */
    *ap = NULL;

    /* look where to insert the free space */

    /* (bp > p && bp < p->s.ptr)    => between two nodes */
    /* (p > p->s.ptr)               => this is the end of the list */
    /* (p == p->p.str)              => list is one element only */
    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            /* freed block at start or end of arena */
            break;

    if (bp + bp->s.size == p->s.ptr) {      /* join to upper nbr */
    /* the new block fits perfect up to the upper neighbor */

        /* merging up: adjust the size */
        bp->s.size += p->s.ptr->s.size;
        /* merging up: point to the second next */
        bp->s.ptr = p->s.ptr->s.ptr;

    } else
        /* set the upper pointer */
        bp->s.ptr = p->s.ptr;

    if (p + p->s.size == bp) {              /* join to lower nbr */
    /* the new block fits perfect on top of the lower neighbor */

        /* merging below: adjust the size */
        p->s.size += bp->s.size;
        /* merging below: point to the next */
        p->s.ptr = bp->s.ptr;

    } else
        /* set the lower pointer */
        p->s.ptr = bp;

    /* reset the start of the free list */
    freep = p;
}
0
Vladimir