#include "portable.h"
#include "xbt/xbt_os_thread.h"
#include "xbt/mmalloc.h"
+#include "xbt/ex.h"
#include <semaphore.h>
#ifdef HAVE_LIMITS_H
const char *xbt_thread_self_name(void);
-/* Data structure giving per-block information. */
-typedef union {
+/* Data structure giving per-block information.
+ *
+ * There is one such structure in the mdp->heapinfo array,
+ * that is addressed by block number.
+ *
+ * There is several types of blocks in memory:
+ * - full busy blocks: used when we are asked to malloc a block which size is > BLOCKSIZE/2
+ * In this situation, the full block is given to the malloc.
+ *
+ * - fragmented busy blocks: when asked for smaller amount of memory.
+ * Fragment sizes are only power of 2. When looking for such a free fragment,
+ * we get one from mdp->fraghead (that contains a linked list of blocks fragmented at that
+ * size and containing a free fragment), or we get a fresh block that we fragment.
+ *
+ * - free blocks are grouped by clusters, that are chained together.
+ * When looking for free blocks, we traverse the mdp->heapinfo looking
+ * for a cluster of free blocks that would be large enough.
+ *
+ * The size of the cluster is only to be trusted in the first block of the cluster.
+ * If the cluster results of the fusion of several clusters, the previously first
+ * block of their cluster will have partial data. The only information kept consistent over
+ * all blocks of the clusters is their type (== -1).
+ *
+ * Note that there is no way to determine if the block is free or busy by exploring
+ * this structure only. It wasn't intended to be crawled for comparison and we should fix it (TODO).
+ *
+ * TODO: understand whether the information are written in each blocks of a cluster (be it
+ * free or busy) or only in the first block of the cluster. And in the latter case, how can
+ * I retrieve the first block of my cluster.
+ *
+ * TODO:
+ * - add an indication of the requested size in each fragment, similarly to busy_block.busy_size
+ * - make room to store the backtrace of where the blocks and fragment were malloced, too.
+ */
+typedef struct {
+ int type; /* 0: busy large block
+ >0: busy fragmented (fragments of size 2^type bytes)
+ <0: free block */
+ union {
/* Heap information for a busy block. */
- struct {
- /* Zero for a large block, or positive giving the
- logarithm to the base two of the fragment size. */
- int type;
- union {
- struct {
- size_t nfree; /* Free fragments in a fragmented block. */
- size_t first; /* First free fragment of the block. */
- } frag;
- struct {
- size_t size; /* Size (in blocks) of a large cluster. */
- size_t busy_size;
- } block;
- } info;
- } busy;
- /* Heap information for a free block (that may be the first of
- a free cluster). */
- struct {
- size_t size; /* Size (in blocks) of a free cluster. */
- size_t next; /* Index of next free cluster. */
- size_t prev; /* Index of previous free cluster. */
- } free;
+ struct {
+ size_t nfree; /* Free fragments in a fragmented block. */
+ size_t first; /* First free fragment of the block. */
+ } busy_frag;
+ struct {
+ size_t size; /* Size (in blocks) of a large cluster. */
+ size_t busy_size; /* Actually used space, in bytes */
+ } busy_block;
+ /* Heap information for a free block (that may be the first of a free cluster). */
+ struct {
+ size_t size; /* Size (in blocks) of a free cluster. */
+ size_t next; /* Index of next free cluster. */
+ size_t prev; /* Index of previous free cluster. */
+ } free_block;
+ };
} malloc_info;
/* Doubly linked lists of free fragments. */
size_t heaplimit;
/* Block information table.
- Allocated with malign/__mmalloc_free (not mmalloc/mfree). */
+ Allocated with malign/mfree (not mmalloc/mfree). */
/* Table indexed by block number giving per-block information. */
-
malloc_info *heapinfo;
- /* Free list headers for each fragment size. */
- /* Free lists for each fragment size. */
-
+ /* List of all blocks containing free fragments of this size. The array indice is the log2 of requested size */
struct list fraghead[BLOCKLOG];
- /* List of blocks allocated by memalign. */
-
- struct alignlist *aligned_blocks;
-
/* The base address of the memory region for this malloc heap. This
is the location where the bookkeeping data for mmap and for malloc
begins. */
#define MMALLOC_ANONYMOUS (1 << 1) /* Use anonymous mapping */
#define MMALLOC_INITIALIZED (1 << 2) /* Initialized mmalloc */
-/* Internal version of `mfree' used in `morecore'. */
-
-extern void __mmalloc_free(struct mdesc *mdp, void *ptr);
-
/* A default malloc descriptor for the single sbrk() managed region. */
extern struct mdesc *__mmalloc_default_mdp;
