- Ensure that the mmallocation code will never return NULL (but die
verbosely), and simplify the using code accordingly.
- Stop using THROWF in there, because these functions probably need
malloc to work, and that what broke when we want to issue a message.
Use printf/abort instead.
- Introduce a SMALLEST_POSSIBLE_MALLOC. It already existed (and were
defined to sizeof(struct list) to ensure that free fragments can be
enlisted, but I need this to declare the block metadata
- Add a frag_size information within the bloc info structure. It may
not perfectly be kept uptodate yet (in particular, by realloc)
/* Prototypes for local functions */
/* Prototypes for local functions */
-static int initialize(xbt_mheap_t mdp);
+static void initialize(xbt_mheap_t mdp);
static void *register_morecore(xbt_mheap_t mdp, size_t size);
static void *align(xbt_mheap_t mdp, size_t size);
static void *register_morecore(xbt_mheap_t mdp, size_t size);
static void *align(xbt_mheap_t mdp, size_t size);
-/* Allocation aligned on block boundary */
+/* Allocation aligned on block boundary.
+ *
+ * It never returns NULL, but dies verbosely on error.
+ */
static void *align(struct mdesc *mdp, size_t size)
{
void *result;
static void *align(struct mdesc *mdp, size_t size)
{
void *result;
/* Finish the initialization of the mheap. If we want to inline it
* properly, we need to make the align function publicly visible, too */
/* Finish the initialization of the mheap. If we want to inline it
* properly, we need to make the align function publicly visible, too */
-static int initialize(xbt_mheap_t mdp)
+static void initialize(xbt_mheap_t mdp)
{
mdp->heapsize = HEAP / BLOCKSIZE;
mdp->heapinfo = (malloc_info *)
align(mdp, mdp->heapsize * sizeof(malloc_info));
{
mdp->heapsize = HEAP / BLOCKSIZE;
mdp->heapinfo = (malloc_info *)
align(mdp, mdp->heapsize * sizeof(malloc_info));
- if (mdp->heapinfo == NULL) {
- return (0);
- }
memset((void *) mdp->heapinfo, 0, mdp->heapsize * sizeof(malloc_info));
mdp->heapinfo[0].type=-1;
mdp->heapinfo[0].free_block.size = 0;
memset((void *) mdp->heapinfo, 0, mdp->heapsize * sizeof(malloc_info));
mdp->heapinfo[0].type=-1;
mdp->heapinfo[0].free_block.size = 0;
mdp->heapindex = 0;
mdp->heapbase = (void *) mdp->heapinfo;
mdp->flags |= MMALLOC_INITIALIZED;
mdp->heapindex = 0;
mdp->heapbase = (void *) mdp->heapinfo;
mdp->flags |= MMALLOC_INITIALIZED;
}
/* Get neatly aligned memory from the low level layers, and register it
}
/* Get neatly aligned memory from the low level layers, and register it
malloc_info *newinfo, *oldinfo;
size_t newsize;
malloc_info *newinfo, *oldinfo;
size_t newsize;
- result = align(mdp, size);
- if (result == NULL) {
- return (NULL);
- }
+ result = align(mdp, size); // Never returns NULL
/* Check if we need to grow the info table (in a multiplicative manner) */
if ((size_t) BLOCK((char *) result + size) > mdp->heapsize) {
/* Check if we need to grow the info table (in a multiplicative manner) */
if ((size_t) BLOCK((char *) result + size) > mdp->heapsize) {
register size_t log;
int it;
register size_t log;
int it;
- /* Work even if the user was stupid enough to ask a 0-byte block, ie return a valid block that can be realloced or freed
- * glibc malloc does not use this trick but return a constant pointer, but my hack is quicker to implement ;)
+ size_t requested_size = size; // The amount of memory requested by user, for real
+
+ /* Work even if the user was stupid enough to ask a ridicullously small block (even 0-length),
+ * ie return a valid block that can be realloced and freed.
+ * glibc malloc does not use this trick but return a constant pointer, but we need to enlist the free fragments later on.
- if (size == 0)
- size = 1;
+ if (size < SMALLEST_POSSIBLE_MALLOC)
+ size = SMALLEST_POSSIBLE_MALLOC;
// printf("(%s) Mallocing %d bytes on %p (default: %p)...",xbt_thread_self_name(),size,mdp,__mmalloc_default_mdp);fflush(stdout);
// printf("(%s) Mallocing %d bytes on %p (default: %p)...",xbt_thread_self_name(),size,mdp,__mmalloc_default_mdp);fflush(stdout);
- if (!(mdp->flags & MMALLOC_INITIALIZED)) {
- if (!initialize(mdp)) {
- return (NULL);
- }
- }
-
- if (size < sizeof(struct list)) {
- size = sizeof(struct list);
- }
+ if (!(mdp->flags & MMALLOC_INITIALIZED))
+ initialize(mdp);
/* Determine the allocation policy based on the request size. */
if (size <= BLOCKSIZE / 2) {
/* Determine the allocation policy based on the request size. */
if (size <= BLOCKSIZE / 2) {
/* There are free fragments of this size.
Pop a fragment out of the fragment list and return it.
Update the block's nfree and first counters. */
/* There are free fragments of this size.
Pop a fragment out of the fragment list and return it.
Update the block's nfree and first counters. */
+ block = BLOCK(result);
+
+ frag_nb = RESIDUAL(result, BLOCKSIZE) >> log;
+ mdp->heapinfo[block].busy_frag.frag_size[frag_nb] = requested_size;
+ //FIXME setup backtrace
+
next->prev->next = next->next;
if (next->next != NULL) {
next->next->prev = next->prev;
}
next->prev->next = next->next;
if (next->next != NULL) {
next->next->prev = next->prev;
}
if (--mdp->heapinfo[block].busy_frag.nfree != 0) {
mdp->heapinfo[block].busy_frag.first =
RESIDUAL(next->next, BLOCKSIZE) >> log;
if (--mdp->heapinfo[block].busy_frag.nfree != 0) {
mdp->heapinfo[block].busy_frag.first =
RESIDUAL(next->next, BLOCKSIZE) >> log;
/* No free fragments of the desired size, so get a new block
and break it into fragments, returning the first. */
//printf("(%s) No free fragment...",xbt_thread_self_name());
/* No free fragments of the desired size, so get a new block
and break it into fragments, returning the first. */
//printf("(%s) No free fragment...",xbt_thread_self_name());
- result = mmalloc(mdp, BLOCKSIZE);
- //printf("(%s) Fragment: %p...",xbt_thread_self_name(),result);
- if (result == NULL) {
- return (NULL);
- }
- /* Link all fragments but the first into the free list. */
+ result = mmalloc(mdp, BLOCKSIZE); // does not return NULL
+
+ /* Link all fragments but the first into the free list, and mark their requested size to 0. */
+ block = BLOCK(result);
for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i) {
for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i) {
+ mdp->heapinfo[block].busy_frag.frag_size[i] = 0;
next = (struct list *) ((char *) result + (i << log));
next->next = mdp->fraghead[log].next;
next->prev = &mdp->fraghead[log];
next = (struct list *) ((char *) result + (i << log));
next->next = mdp->fraghead[log].next;
next->prev = &mdp->fraghead[log];
next->next->prev = next;
}
}
next->next->prev = next;
}
}
+ mdp->heapinfo[block].busy_frag.frag_size[0] = requested_size;
+ // FIXME: setup backtrace
/* Initialize the nfree and first counters for this block. */
/* Initialize the nfree and first counters for this block. */
mdp->heapinfo[block].type = log;
mdp->heapinfo[block].busy_frag.nfree = i - 1;
mdp->heapinfo[block].busy_frag.first = i - 1;
mdp->heapinfo[block].type = log;
mdp->heapinfo[block].busy_frag.nfree = i - 1;
mdp->heapinfo[block].busy_frag.first = i - 1;
blocks = BLOCKIFY(size);
start = block = MALLOC_SEARCH_START;
while (mdp->heapinfo[block].free_block.size < blocks) {
blocks = BLOCKIFY(size);
start = block = MALLOC_SEARCH_START;
while (mdp->heapinfo[block].free_block.size < blocks) {
- if (mdp->heapinfo[block].type >=0) {
+ if (mdp->heapinfo[block].type >=0) { // Don't trust xbt_die and friends in malloc-level library, you fool!
fprintf(stderr,"Internal error: found a free block not marked as such (block=%lu type=%lu). Please report this bug.\n",(unsigned long)block,(unsigned long)mdp->heapinfo[block].type);
abort();
}
fprintf(stderr,"Internal error: found a free block not marked as such (block=%lu type=%lu). Please report this bug.\n",(unsigned long)block,(unsigned long)mdp->heapinfo[block].type);
abort();
}
continue;
}
result = register_morecore(mdp, blocks * BLOCKSIZE);
continue;
}
result = register_morecore(mdp, blocks * BLOCKSIZE);
- if (result == NULL) {
- return (NULL);
- }
block = BLOCK(result);
for (it=0;it<blocks;it++)
mdp->heapinfo[block+it].type = 0;
mdp->heapinfo[block].busy_block.size = blocks;
block = BLOCK(result);
for (it=0;it<blocks;it++)
mdp->heapinfo[block+it].type = 0;
mdp->heapinfo[block].busy_block.size = blocks;
- mdp->heapinfo[block].busy_block.busy_size = size;
- return (result);
+ mdp->heapinfo[block].busy_block.busy_size = requested_size;
+ // FIXME: setup backtrace
+
+ return result;
+ /* Need large block(s), but found some in the existing heap */
}
/* At this point we have found a suitable free list entry.
}
/* At this point we have found a suitable free list entry.
for (it=0;it<blocks;it++)
mdp->heapinfo[block+it].type = 0;
mdp->heapinfo[block].busy_block.size = blocks;
for (it=0;it<blocks;it++)
mdp->heapinfo[block+it].type = 0;
mdp->heapinfo[block].busy_block.size = blocks;
- mdp->heapinfo[block].busy_block.busy_size = size;
+ mdp->heapinfo[block].busy_block.busy_size = requested_size;
}
//printf("(%s) Done mallocing. Result is %p\n",xbt_thread_self_name(),result);fflush(stdout);
return (result);
}
//printf("(%s) Done mallocing. Result is %p\n",xbt_thread_self_name(),result);fflush(stdout);
return (result);
/* 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
/* 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(). */
+ like sbrk(), but using mmap().
+
+ It never returns NULL. Instead, it dies verbosely on errors. */
void *mmorecore(struct mdesc *mdp, int size)
{
ssize_t test = 0;
void *mmorecore(struct mdesc *mdp, int size)
{
ssize_t test = 0;
+ void *result; // please keep it uninitialized to track issues
off_t foffset; /* File offset at which new mapping will start */
size_t mapbytes; /* Number of bytes to map */
void *moveto; /* Address where we wish to move "break value" to */
off_t foffset; /* File offset at which new mapping will start */
size_t mapbytes; /* Number of bytes to map */
void *moveto; /* Address where we wish to move "break value" to */
} else if (size < 0) {
/* We are deallocating memory. If the amount requested would cause
us to try to deallocate back past the base of the mmap'd region
} else if (size < 0) {
/* We are deallocating memory. If the amount requested would cause
us to try to deallocate back past the base of the mmap'd region
- then do nothing, and return NULL. Otherwise, deallocate the
- memory and return the old break value. */
+ then die verbosely. Otherwise, deallocate the memory and return
+ the old break value. */
if (((char *) mdp->breakval) + size >= (char *) mdp->base) {
result = (void *) mdp->breakval;
mdp->breakval = (char *) mdp->breakval + size;
if (((char *) mdp->breakval) + size >= (char *) mdp->base) {
result = (void *) mdp->breakval;
mdp->breakval = (char *) mdp->breakval + size;
munmap(moveto,
(size_t) (((char *) mdp->top) - ((char *) moveto)) - 1);
mdp->top = moveto;
munmap(moveto,
(size_t) (((char *) mdp->top) - ((char *) moveto)) - 1);
mdp->top = moveto;
+ } else {
+ fprintf(stderr,"Internal error: mmap was asked to deallocate more memory than it previously allocated. Bailling out now!\n");
+ abort();
}
} else {
/* We are allocating memory. Make sure we have an open file
descriptor if not working with anonymous memory. */
if (!(mdp->flags & MMALLOC_ANONYMOUS) && mdp->fd < 0) {
}
} else {
/* We are allocating memory. Make sure we have an open file
descriptor if not working with anonymous memory. */
if (!(mdp->flags & MMALLOC_ANONYMOUS) && mdp->fd < 0) {
- THROWF(system_error,0,"mmap file descriptor <0 (%d), without MMALLOC_ANONYMOUS being in the flags",mdp->fd);
- result = NULL;
+ fprintf(stderr,"Internal error: mmap file descriptor <0 (%d), without MMALLOC_ANONYMOUS being in the flags.\n",mdp->fd);
+ abort();
} else if ((char *) mdp->breakval + size > (char *) mdp->top) {
/* The request would move us past the end of the currently
mapped memory, so map in enough more memory to satisfy
} else if ((char *) mdp->breakval + size > (char *) mdp->top) {
/* The request would move us past the end of the currently
mapped memory, so map in enough more memory to satisfy
/* FIXME: Test results of lseek() */
lseek(mdp->fd, foffset + mapbytes - 1, SEEK_SET);
test = write(mdp->fd, &buf, 1);
/* FIXME: Test results of lseek() */
lseek(mdp->fd, foffset + mapbytes - 1, SEEK_SET);
test = write(mdp->fd, &buf, 1);
- if (test == -1)
- THROWF(system_error, 0, "write to mmap'ed fd failed! error: %s", strerror(errno));
+ if (test == -1) {
+ fprintf(stderr,"Internal error: write to mmap'ed fd failed! error: %s", strerror(errno));
+ abort();
+ }
}
/* Let's call mmap. Note that it is possible that mdp->top
}
/* Let's call mmap. Note that it is possible that mdp->top
MAP_PRIVATE_OR_SHARED(mdp) | MAP_IS_ANONYMOUS(mdp) |
MAP_FIXED, MAP_ANON_OR_FD(mdp), foffset);
MAP_PRIVATE_OR_SHARED(mdp) | MAP_IS_ANONYMOUS(mdp) |
MAP_FIXED, MAP_ANON_OR_FD(mdp), foffset);
- if (mapto == (void *) -1/* That's MAP_FAILED */)
- THROWF(system_error,0,"mmap returned MAP_FAILED! error: %s",strerror(errno));
+ if (mapto == (void *) -1/* That's MAP_FAILED */) {
+ fprintf(stderr,"Internal error: mmap returned MAP_FAILED! error: %s",strerror(errno));
+ abort();
+ }
if (mdp->top == 0)
mdp->base = mdp->breakval = mapto;
if (mdp->top == 0)
mdp->base = mdp->breakval = mapto;
requests receive one or more whole blocks, and small requests
receive a fragment of a block. Fragment sizes are powers of two,
and all fragments of a block are the same size. When all the
requests receive one or more whole blocks, and small requests
receive a fragment of a block. Fragment sizes are powers of two,
and all fragments of a block are the same size. When all the
- fragments in a block have been freed, the block itself is freed. */
+ fragments in a block have been freed, the block itself is freed.
+
+ FIXME: we are not targeting 16bits machines anymore; update values */
#define INT_BIT (CHAR_BIT * sizeof(int))
#define BLOCKLOG (INT_BIT > 16 ? 12 : 9)
#define BLOCKSIZE ((unsigned int) 1 << BLOCKLOG)
#define BLOCKIFY(SIZE) (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE)
#define INT_BIT (CHAR_BIT * sizeof(int))
#define BLOCKLOG (INT_BIT > 16 ? 12 : 9)
#define BLOCKSIZE ((unsigned int) 1 << BLOCKLOG)
#define BLOCKIFY(SIZE) (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE)
+/* We keep fragment-specific meta-data for introspection purposes, and these
+ * information are kept in fixed lenght arrays. Here is the computation of
+ * that size.
+ *
+ * Never make SMALLEST_POSSIBLE_MALLOC smaller than sizeof(list) because we
+ * need to enlist the free fragments.
+ */
+
+#define SMALLEST_POSSIBLE_MALLOC (sizeof(struct list))
+#define MAX_FRAGMENT_PER_BLOCK (BLOCKSIZE / SMALLEST_POSSIBLE_MALLOC)
+
/* The difference between two pointers is a signed int. On machines where
the data addresses have the high bit set, we need to ensure that the
difference becomes an unsigned int when we are using the address as an
/* The difference between two pointers is a signed int. On machines where
the data addresses have the high bit set, we need to ensure that the
difference becomes an unsigned int when we are using the address as an
#define HEAP (INT_BIT > 16 ? 4194304 : 65536)
/* Number of contiguous free blocks allowed to build up at the end of
#define HEAP (INT_BIT > 16 ? 4194304 : 65536)
/* Number of contiguous free blocks allowed to build up at the end of
- memory before they will be returned to the system. */
-
+ memory before they will be returned to the system.
+ FIXME: this is not used anymore: we never return memory to the system. */
#define FINAL_FREE_BLOCKS 8
/* Where to start searching the free list when looking for new memory.
#define FINAL_FREE_BLOCKS 8
/* Where to start searching the free list when looking for new memory.
const char *xbt_thread_self_name(void);
const char *xbt_thread_self_name(void);
+/* Doubly linked lists of free fragments. */
+struct list {
+ struct list *next;
+ struct list *prev;
+};
+
/* Data structure giving per-block information.
*
* There is one such structure in the mdp->heapinfo array,
/* Data structure giving per-block information.
*
* There is one such structure in the mdp->heapinfo array,
struct {
size_t nfree; /* Free fragments in a fragmented block. */
size_t first; /* First free fragment of the block. */
struct {
size_t nfree; /* Free fragments in a fragmented block. */
size_t first; /* First free fragment of the block. */
+ unsigned short frag_size[MAX_FRAGMENT_PER_BLOCK];
} busy_frag;
struct {
size_t size; /* Size (in blocks) of a large cluster. */
} busy_frag;
struct {
size_t size; /* Size (in blocks) of a large cluster. */
-/* Doubly linked lists of free fragments. */
-struct list {
- struct list *next;
- struct list *prev;
-};
-
/* Internal structure that defines the format of the malloc-descriptor.
This gets written to the base address of the region that mmalloc is
managing, and thus also becomes the file header for the mapped file,
/* Internal structure that defines the format of the malloc-descriptor.
This gets written to the base address of the region that mmalloc is
managing, and thus also becomes the file header for the mapped file,
switch (type) {
case 0:
/* Maybe reallocate a large block to a small fragment. */
switch (type) {
case 0:
/* Maybe reallocate a large block to a small fragment. */
- if (size <= BLOCKSIZE / 2) {
- //printf("(%s) alloc large block...",xbt_thread_self_name());
+
+ if (size <= BLOCKSIZE / 2) { // Full block -> Fragment; no need to optimize for time
+
result = mmalloc(mdp, size);
result = mmalloc(mdp, size);
+ if (result != NULL) { // useless (mmalloc never returns NULL), but harmless
memcpy(result, ptr, size);
mfree(mdp, ptr);
return (result);
memcpy(result, ptr, size);
mfree(mdp, ptr);
return (result);
