#include "portable.h"
#include "xbt/xbt_os_thread.h"
#include "xbt/mmalloc.h"
+#include "xbt/ex.h"
#include <semaphore.h>
#ifdef HAVE_LIMITS_H
# endif
#endif
-#ifndef MIN
-# define MIN(A, B) ((A) < (B) ? (A) : (B))
-#endif
-
#define MMALLOC_MAGIC "mmalloc" /* Mapped file magic number */
#define MMALLOC_MAGIC_SIZE 8 /* Size of magic number buf */
#define MMALLOC_VERSION 1 /* Current mmalloc version */
-#define MMALLOC_KEYS 16 /* Keys for application use */
/* The allocator divides the heap into blocks of fixed size; large
requests receive one or more whole blocks, and small requests
const char *xbt_thread_self_name(void);
-/* Data structure giving per-block information. */
-typedef 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;
- /* Size (in blocks) of a large cluster. */
- size_t size;
- } 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;
+/* 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 {
+ 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;
-/* List of blocks allocated with `mmemalign' (or `mvalloc'). */
-
-struct alignlist {
- struct alignlist *next;
- void *aligned; /* The address that mmemaligned returned. */
- void *exact; /* The address that malloc returned. */
-};
-
/* Doubly linked lists of free fragments. */
-
struct list {
- struct list *next;
- struct list *prev;
-};
-
-/* Statistics available to the user.
- FIXME: By design, the internals of the malloc package are no longer
- exported to the user via an include file, so access to this data needs
- to be via some other mechanism, such as mmstat_<something> where the
- return value is the <something> the user is interested in. */
-
-struct mstats {
- size_t bytes_total; /* Total size of the heap. */
- size_t chunks_used; /* Chunks allocated by the user. */
- size_t bytes_used; /* Byte total of user-allocated chunks. */
- size_t chunks_free; /* Chunks in the free list. */
- size_t bytes_free; /* Byte total of chunks in the free list. */
+ struct list *next;
+ struct list *prev;
};
/* Internal structure that defines the format of the malloc-descriptor.
struct mdesc {
- /* Semaphore locking the access to the heap */
- sem_t sem;
-
- /* Number of processes that attached the heap */
- unsigned int refcount;
-
- /* Chained lists of mdescs */
- struct mdesc *next_mdesc;
-
- /* The "magic number" for an mmalloc file. */
- char magic[MMALLOC_MAGIC_SIZE];
-
- /* The size in bytes of this structure, used as a sanity check when reusing
- a previously created mapped file. */
- unsigned int headersize;
-
- /* The version number of the mmalloc package that created this file. */
- unsigned char version;
-
- /* Some flag bits to keep track of various internal things. */
- unsigned int flags;
-
- /* If a system call made by the mmalloc package fails, the errno is
- preserved for future examination. */
- int saved_errno;
-
- /* Pointer to the function that is used to get more core, or return core
- to the system, for requests using this malloc descriptor. For memory
- mapped regions, this is the mmap() based routine. There may also be
- a single malloc descriptor that points to an sbrk() based routine
- for systems without mmap() or for applications that call the mmalloc()
- package with a NULL malloc descriptor.
-
- FIXME: For mapped regions shared by more than one process, this
- needs to be maintained on a per-process basis. */
- void *(*morecore) (struct mdesc * mdp, int size);
+ /* Semaphore locking the access to the heap */
+ sem_t sem;
- /* Pointer to the function that causes an abort when the memory checking
- features are activated. By default this is set to abort(), but can
- be set to another function by the application using mmalloc().
+ /* Number of processes that attached the heap */
+ unsigned int refcount;
- FIXME: For mapped regions shared by more than one process, this
- needs to be maintained on a per-process basis. */
- void (*abortfunc) (void);
+ /* Chained lists of mdescs */
+ struct mdesc *next_mdesc;
- /* Debugging hook for free.
+ /* The "magic number" for an mmalloc file. */
+ char magic[MMALLOC_MAGIC_SIZE];
- FIXME: For mapped regions shared by more than one process, this
- needs to be maintained on a per-process basis. */
- void (*mfree_hook) (void *mdp, void *ptr);
-
- /* Debugging hook for `malloc'.
-
- FIXME: For mapped regions shared by more than one process, this
- needs to be maintained on a per-process basis. */
- void *(*mmalloc_hook) (void *mdp, size_t size);
-
- /* Debugging hook for realloc.
-
- FIXME: For mapped regions shared by more than one process, this
- needs to be maintained on a per-process basis. */
- void *(*mrealloc_hook) (void *mdp, void *ptr, size_t size);
-
- /* Number of info entries. */
- size_t heapsize;
-
- /* Pointer to first block of the heap (base of the first block). */
- void *heapbase;
-
- /* Current search index for the heap table. */
- /* Search index in the info table. */
- size_t heapindex;
-
- /* Limit of valid info table indices. */
- size_t heaplimit;
+ /* The size in bytes of this structure, used as a sanity check when reusing
+ a previously created mapped file. */
+ unsigned int headersize;
- /* Block information table.
- Allocated with malign/__mmalloc_free (not mmalloc/mfree). */
- /* Table indexed by block number giving per-block information. */
+ /* The version number of the mmalloc package that created this file. */
+ unsigned char version;
- malloc_info *heapinfo;
+ /* Some flag bits to keep track of various internal things. */
+ unsigned int flags;
- /* Instrumentation. */
+ /* Number of info entries. */
+ size_t heapsize;
- struct mstats heapstats;
+ /* Pointer to first block of the heap (base of the first block). */
+ void *heapbase;
- /* Free list headers for each fragment size. */
- /* Free lists for each fragment size. */
+ /* Current search index for the heap table. */
+ /* Search index in the info table. */
+ size_t heapindex;
- struct list fraghead[BLOCKLOG];
+ /* Limit of valid info table indices. */
+ size_t heaplimit;
- /* List of blocks allocated by memalign. */
+ /* Block information table.
+ Allocated with malign/mfree (not mmalloc/mfree). */
+ /* Table indexed by block number giving per-block information. */
+ malloc_info *heapinfo;
- struct alignlist *aligned_blocks;
+ /* List of all blocks containing free fragments of this size. The array indice is the log2 of requested size */
+ struct list fraghead[BLOCKLOG];
- /* The base address of the memory region for this malloc heap. This
+ /* 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. */
- void *base;
+ void *base;
- /* The current location in the memory region for this malloc heap which
+ /* The current location in the memory region for this malloc heap which
represents the end of memory in use. */
- void *breakval;
+ void *breakval;
- /* The end of the current memory region for this malloc heap. This is
+ /* The end of the current memory region for this malloc heap. This is
the first location past the end of mapped memory. */
- void *top;
+ void *top;
- /* Open file descriptor for the file to which this malloc heap is mapped.
+ /* Open file descriptor for the file to which this malloc heap is mapped.
This will always be a valid file descriptor, since /dev/zero is used
by default if no open file is supplied by the client. Also note that
it may change each time the region is mapped and unmapped. */
- int fd;
-
- /* An array of keys to data within the mapped region, for use by the
- application. */
-
- void *keys[MMALLOC_KEYS];
+ int fd;
};
-int mmalloc_compare_heap(void *h1, void *h2);
+int mmalloc_compare_mdesc(struct mdesc *mdp1, struct mdesc *mdp2, void *std_heap_addr);
-int mmalloc_compare_mdesc(struct mdesc *mdp1, struct mdesc *mdp2);
+void mmalloc_display_info(void *h);
/* Bits to look at in the malloc descriptor flags word */
#define MMALLOC_DEVZERO (1 << 0) /* Have mapped to /dev/zero */
#define MMALLOC_ANONYMOUS (1 << 1) /* Use anonymous mapping */
#define MMALLOC_INITIALIZED (1 << 2) /* Initialized mmalloc */
-#define MMALLOC_MMCHECK_USED (1 << 3) /* mmcheckf() called already */
-
-/* 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;
-/* Initialize the first use of the default malloc descriptor, which uses
- an sbrk() region. */
-
-extern struct mdesc *__mmalloc_create_default_mdp(void);
-
-/* Grow or shrink a contiguous mapped region using mmap().
- Works much like sbrk(), only faster */
+/* Remap a mmalloc region that was previously mapped. */
-extern void *__mmalloc_mmap_morecore(struct mdesc *mdp, int size);
+extern void *__mmalloc_remap_core(xbt_mheap_t mdp);
+/* Get core for the memory region specified by MDP, using SIZE as the
+ amount to either add to or subtract from the existing region. Works
+ like sbrk(), but using mmap(). */
+extern void *mmorecore(struct mdesc *mdp, int size);
-/* Remap a mmalloc region that was previously mapped. */
+/* Thread-safety (if the sem is already created) FIXME: KILLIT*/
+#define LOCK(mdp) \
+ sem_wait(&mdp->sem)
-extern void *__mmalloc_remap_core(struct mdesc *mdp);
-
-/* Macro to convert from a user supplied malloc descriptor to pointer to the
- internal malloc descriptor. If the user supplied descriptor is NULL, then
- use the default internal version, initializing it if necessary. Otherwise
- just cast the user supplied version (which is void *) to the proper type
- (struct mdesc *). */
-
-#define MD_TO_MDP(md) \
- ((md) == NULL \
- ? __mmalloc_default_mdp \
- : (struct mdesc *) (md))
-
-/* Thread-safety (if the sem is already created)*/
-#define LOCK(md) \
- do {\
- struct mdesc *lock_local_mdp = MD_TO_MDP(md); \
- sem_wait(&lock_local_mdp->sem); \
- } while (0)
-
-#define UNLOCK(md) \
- do { \
- struct mdesc *unlock_local_mdp = MD_TO_MDP(md); \
- sem_post(&unlock_local_mdp->sem); \
- } while (0)
+#define UNLOCK(mdp) \
+ sem_post(&mdp->sem)
#endif /* __MMPRIVATE_H */