Explicar esta implementación de malloc del libro de K & R

Este es un extracto del libro sobre C de Kernighan y Ritchie . Muestra cómo implementar una versión de malloc . Aunque bien comentado, estoy teniendo grandes dificultades para entenderlo. ¿Alguien puede explicarlo?

 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 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 s.ptr); p = p->s.ptr) if (p >= p->s.ptr && (bp > p || bp 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; } 

Ok, lo que tenemos aquí es una porción de código realmente mal escrito. Lo que haré en este post podría describirse mejor como arqueología de software.

Paso 1: arregla el formateo.

La sangría y el formato compacto no hacen ningún bien a nadie. Se deben insertar varios espacios y filas vacías. Los comentarios podrían escribirse de maneras más legibles. Comenzaré por arreglar eso.

Al mismo tiempo, estoy cambiando el estilo de corsé del estilo K & R: tenga en cuenta que el estilo de corsé de K & R es aceptable, esto es simplemente una preferencia personal mía. Otra preferencia personal es escribir el * para punteros al lado del tipo señalado. No discutiré sobre el estilo (subjetivo) aquí.

Además, la definición de tipo de Header es completamente ilegible, necesita una solución drástica.

Y vi algo completamente oscuro: parecen haber declarado un prototipo de función dentro de la función. Header* morecore(unsigned); . Este es un estilo muy viejo y muy pobre, y no estoy seguro si C incluso lo permite. Solo eliminemos esa línea, sea lo que sea que haga esa función, tendrá que definirse en otro lugar.

 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, ahora podríamos leer el código.

Paso 2: elimina malas prácticas ampliamente reconocidas.

Este código está lleno de cosas que hoy en día se consideran malas prácticas. Deben eliminarse, ya que ponen en peligro la seguridad, la legibilidad y el mantenimiento del código. Si desea una referencia a una autoridad que predica las mismas prácticas que yo, consulte el estándar de encoding ampliamente reconocido MISRA-C .

He detectado y eliminado las siguientes malas prácticas:

1) Simplemente escribiendo unsigned en el código podría generar confusión: ¿fue esto un error del progtwigdor o fue la intención de escribir unsigned int ? Deberíamos reemplazar todos los unsigned con unsigned int . Pero a medida que hacemos eso, encontramos que se usa en este contexto para dar el tamaño de varios datos binarios. El tipo correcto para usar en tales asuntos es el tipo estándar C size_t . Esto es esencialmente solo un int sin firmar también, pero se garantiza que es “lo suficientemente grande” para la plataforma en particular. El operador sizeof devuelve un resultado de tipo size_t y si miramos la definición del malloc real del estándar C, es void *malloc(size_t size); . Entonces size_t es el tipo más correcto de usar.

2) Es una mala idea usar el mismo nombre para nuestra propia función malloc que el que reside en stdlib.h. Si necesitamos incluir stdlib.h, las cosas se complicarán. Como regla general, nunca use nombres de identificación de funciones de biblioteca estándar C en su propio código. Cambiaré el nombre a kr_malloc.

3) El código está abusando del hecho de que se garantiza que todas las variables estáticas se inicializan a cero. Esto está bien definido por el estándar C, pero es una regla bastante sutil. Inicialicemos todas las estáticas explícitamente, para mostrar que no hemos olvidado iniciarlas por accidente.

4) La asignación dentro de las condiciones es peligrosa y difícil de leer. Esto debería evitarse si es posible, ya que también puede provocar errores, como el error clásico = vs ==.

5) Las asignaciones múltiples en la misma fila son difíciles de leer, y posiblemente también peligrosas, debido al orden de evaluación.

6) Las declaraciones múltiples en la misma fila son difíciles de leer y peligrosas, ya que podrían provocar errores al mezclar datos y declaraciones de punteros. Siempre declare cada variable en una fila propia.

7) Siempre utiliza llaves después de cada statement. No hacerlo dará lugar a errores de insectos.

8) Nunca escriba el lanzamiento de un tipo de puntero específico a void *. No es necesario en C, y podría ocultar errores que el comstackdor habría detectado de otra manera.

9) Evite usar declaraciones de devolución múltiples dentro de una función. A veces conducen a un código más claro, pero en la mayoría de los casos conducen a espaguetis. A medida que el código permanece, no podemos cambiar eso sin reescribir el bucle, así que lo arreglaré más tarde.

10) Keep for loops simple. Deben contener una instrucción init, una condición de bucle y una iteración, nada más. Esto para bucle, con el operador de coma y todo, es muy oscuro. Una vez más, detectamos la necesidad de reescribir este ciclo en algo sensato. Lo haré a continuación, pero por ahora tenemos:

 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 */ } 

Paso 3: reescribe el bucle oscuro.

Por las razones mencionadas anteriormente. Podemos ver que este ciclo continúa para siempre, termina volviendo de la función, ya sea cuando se realiza la asignación o cuando no queda memoria. Entonces, creemos eso como una condición de bucle, y levantemos el retorno al final de la función donde debería estar. Y vamos a deshacernos de ese feo operador de coma.

Presentaré dos nuevas variables: una variable de resultado para contener el puntero resultante, y otra para realizar un seguimiento de si el ciclo debe continuar o no. Voy a volar las mentes de K & R usando el tipo bool , que es parte del lenguaje C desde 1999.

(Espero no haber alterado el algoritmo con este cambio, creo que no)

 #include  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; } 

Paso 4: comstack esta mierda.

Como esto es de K & R, está lleno de errores tipográficos. sizeof(header) debe ser sizeof(Header) . Faltan secuaces. Usan diferentes nombres freep, prevp versus freeptr, prevptr, pero claramente significan la misma variable. Creo que estos últimos en realidad eran nombres mejores, así que permite usarlos.

 #include  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; } 

¡Y ahora tenemos un código legible y fácil de mantener, sin numerosas prácticas peligrosas, que incluso comstackrá! Entonces ahora podríamos comenzar a reflexionar sobre lo que el código realmente está haciendo.

La estructura “Encabezado” es, como ya habrás adivinado, la statement de un nodo en una lista vinculada. Cada nodo contiene un puntero al siguiente. No entiendo muy bien la función morecore, ni el “wrap-around”, nunca he usado esta función, ni sbrk . Pero supongo que asigna un encabezado como se especifica en esta estructura, y también parte de los datos sin procesar que siguen a ese encabezado. Si es así, eso explica por qué no hay un puntero de datos real: se supone que los datos siguen al encabezado, adyacentes en la memoria. Entonces, para cada nodo, obtenemos el encabezado, y obtenemos un fragmento de datos sin procesar después del encabezado.

La iteración en sí es bastante directa, están pasando por una lista de enlaces únicos, un nodo a la vez.

Al final del ciclo, establecen el puntero al punto uno más allá del final del “fragmento”, luego lo almacenan en una variable estática, de modo que el progtwig recuerde dónde asignó previamente la memoria, la próxima vez que se llame a la función.

Están utilizando un truco para hacer que su cabecera termine en una dirección de memoria alineada: almacenan toda la información de gastos generales en una unión junto con una variable lo suficientemente grande como para corresponderse con los requisitos de alineación de la plataforma. Entonces, si el tamaño de “ptr” más el tamaño de “tamaño” son demasiado pequeños para proporcionar la alineación exacta, la unión garantiza que se asignan al menos sizeof (Align) bytes. Creo que todo este truco está obsoleto hoy, ya que el estándar C exige el relleno automático struct / union.

Estoy estudiando K & R como me imagino que OP fue cuando hizo esta pregunta, y vine aquí porque también encontré que estas implementaciones son confusas. Si bien la respuesta aceptada es muy detallada y útil, traté de tomar una táctica diferente que consistiera en comprender el código tal como estaba escrito originalmente: he revisado el código y agregado comentarios a las secciones del código que me resultaron difíciles. . Esto incluye el código para las otras rutinas en la sección (que son las funciones free y memcore ; los he renombrado kandr_malloc y kandr_free para evitar conflictos con el stdlib). Pensé que dejaría esto aquí como un complemento a la respuesta aceptada, para otros estudiantes que puedan encontrarlo útil.

Reconozco que los comentarios en este código son excesivos. Por favor, sepan que solo estoy haciendo esto como un ejercicio de aprendizaje y no estoy proponiendo que esta sea una buena forma de escribir el código.

Me tomé la libertad de cambiar algunos nombres de variables por otros que me parecían más intuitivos; aparte de eso, el código se deja esencialmente intacto. Parece comstackr y ejecutar bien para los progtwigs de prueba que utilicé, aunque valgrind tenía quejas para algunas aplicaciones.

Además, parte del texto de los comentarios se elimina directamente de K & R o de las páginas de manual; no pretendo acreditar estas secciones.

 #include  // 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 presumbly 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, ie 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 (ie, 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 (ie 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 (ie 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; } 

El básico de malloc ()

En Linux, hay dos formas típicas de solicitar memoria: sbrk y mmap . Estas llamadas al sistema tienen severas limitaciones en asignaciones pequeñas frecuentes. malloc () es una función de biblioteca para abordar este problema. Solicita grandes fragmentos de memoria con sbrk / mmap y devuelve pequeños bloques de memoria dentro de grandes fragmentos. Esto es mucho más eficiente y flexible que llamar directamente a sbrk / mmap.

K & R malloc ()

En la implementación de K & R, un núcleo (más comúnmente llamado arena ) es una gran parte de la memoria. morecore() solicita un núcleo del sistema a través de sbrk() . Cuando llama a malloc () / free () varias veces, algunos bloques en los núcleos se utilizan / asignan mientras que otros son gratuitos. K & R malloc almacena las direcciones de bloques libres en una lista circular de enlace único. En esta lista, cada nodo es un bloque de memoria libre. Los primeros bytes sizeof(Header) mantienen el tamaño del bloque y el puntero al siguiente bloque libre. El rest de bytes en el bloque libre no están inicializados. A diferencia de las listas típicas en los libros de texto, los nodos en la lista gratuita son solo punteros a algunas áreas no utilizadas en núcleos; no asigna realmente cada nodo, excepto los núcleos. Esta lista es la clave para la comprensión del algoritmo.

El siguiente diagtwig muestra un diseño de memoria de ejemplo con dos núcleos / arenas. En el diagtwig, cada carácter toma el sizeof(Header) bytes. @ es un Header , + marcas asignadas a la memoria y - marca la memoria libre dentro de los núcleos. En el ejemplo, hay tres bloques asignados y tres bloques libres. Los tres bloques libres se almacenan en la lista circular. Para los tres bloques asignados, solo sus tamaños se almacenan en el Header .

  This is core 1 This is core 2 @---------@+++++++++@++++++++++++ @----------@+++++++++++++++++@------------ | | | p->ptr->ptr p = p->ptr->ptr->ptr p->ptr 

En su código, freep es un punto de entrada a la lista gratuita. Si sigue repetidamente freep->ptr , regresará a freep , es circular. Una vez que comprenda la lista circular de enlace único, el rest es relativamente fácil. malloc() encuentra un bloque libre y posiblemente lo divida. free() agrega un bloque libre a la lista y puede fusionarlo a bloques libres adyacentes. Ambos intentan mantener la estructura de la lista.

Otros comentarios sobre la implementación

  • Los comentarios del código se mencionaron como “envueltos” en malloc() . Esa línea ocurre cuando ha atravesado toda la lista libre pero no puede encontrar un bloque libre más grande que la longitud solicitada. En este caso, debe agregar un nuevo núcleo con morecore() .

  • base es un bloque de tamaño cero que siempre se incluye en la lista gratuita. Es un truco para evitar una carcasa especial. No es estrictamente necesario.

  • free() puede parecer un poco complejo porque tiene que considerar cuatro casos diferentes para fusionar un bloque recién liberado con otros bloques libres en la lista. Este detalle no es tan importante a menos que desee volver a realizarlo usted mismo.

  • Esta publicación de blog explica K & R malloc en más detalles.

PD: K & R malloc es una de las piezas de código más elegantes desde mi punto de vista. Fue realmente revelador cuando entendí el código por primera vez. Me entristece que algunos progtwigdores modernos, que ni siquiera entienden lo básico de esta implementación, estén llamando la basura de la obra maestra únicamente en función de su estilo de encoding.

También encontré este ejercicio genial e interesante.

En mi opinión, visualizar la estructura puede ayudar mucho con la comprensión de la lógica, o al menos esto funcionó para mí. Debajo está mi código, que imprime tanto como sea posible sobre el flujo del malloc de K & R.

The most significant change I made in the K&R malloc is the change of ‘free’ to make sure some old pointer will not be used again. Other than that I added comments and fixed some small typos.

Experimenting with NALLOC, MAXMEM and the test variables in ‘main’ could be also of help.

On my computer (Ubuntu 16.04.3) this compiled without errors with:

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

krmalloc.c :

 #include  #include  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; }