-/* Block-relocating memory allocator.
- Copyright (C) 1992 Free Software Foundation, Inc.
+/* Block-relocating memory allocator.
+ Copyright (C) 1993, 1995, 2000, 2002, 2003, 2004,
+ 2005 Free Software Foundation, Inc.
This file is part of GNU Emacs.
GNU Emacs is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 1, or (at your option)
+the Free Software Foundation; either version 2, or (at your option)
any later version.
GNU Emacs is distributed in the hope that it will be useful,
You should have received a copy of the GNU General Public License
along with GNU Emacs; see the file COPYING. If not, write to
-the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA. */
/* NOTES:
- Only relocate the blocs neccessary for SIZE in r_alloc_sbrk,
+ Only relocate the blocs necessary for SIZE in r_alloc_sbrk,
rather than all of them. This means allowing for a possible
- hole between the first bloc and the end of malloc storage. */
+ hole between the first bloc and the end of malloc storage. */
-#include "config.h"
+#ifdef emacs
+
+#include <config.h>
#include "lisp.h" /* Needed for VALBITS. */
-#undef NULL
-#include "mem_limits.h"
+#include "blockinput.h"
+
+#ifdef HAVE_UNISTD_H
+#include <unistd.h>
+#endif
+
+typedef POINTER_TYPE *POINTER;
+typedef size_t SIZE;
+
+/* Declared in dispnew.c, this version doesn't screw up if regions
+ overlap. */
+
+extern void safe_bcopy ();
+
+#ifdef DOUG_LEA_MALLOC
+#define M_TOP_PAD -2
+extern int mallopt ();
+#else /* not DOUG_LEA_MALLOC */
+#ifndef SYSTEM_MALLOC
+extern size_t __malloc_extra_blocks;
+#endif /* SYSTEM_MALLOC */
+#endif /* not DOUG_LEA_MALLOC */
+
+#else /* not emacs */
+
+#include <stddef.h>
+
+typedef size_t SIZE;
+typedef void *POINTER;
+
+#include <unistd.h>
+#include <malloc.h>
+
+#define safe_bcopy(x, y, z) memmove (y, x, z)
+#define bzero(x, len) memset (x, 0, len)
+
+#endif /* not emacs */
+
+
#include "getpagesize.h"
#define NIL ((POINTER) 0)
+/* A flag to indicate whether we have initialized ralloc yet. For
+ Emacs's sake, please do not make this local to malloc_init; on some
+ machines, the dumping procedure makes all static variables
+ read-only. On these machines, the word static is #defined to be
+ the empty string, meaning that r_alloc_initialized becomes an
+ automatic variable, and loses its value each time Emacs is started
+ up. */
+
+static int r_alloc_initialized = 0;
+
+static void r_alloc_init ();
+
\f
/* Declarations for working with the malloc, ralloc, and system breaks. */
-/* System call to set the break value. */
-extern POINTER sbrk ();
+/* Function to set the real break value. */
+POINTER (*real_morecore) ();
-/* The break value, as seen by malloc (). */
+/* The break value, as seen by malloc. */
static POINTER virtual_break_value;
-/* The break value, viewed by the relocatable blocs. */
+/* The address of the end of the last data in use by ralloc,
+ including relocatable blocs as well as malloc data. */
static POINTER break_value;
-/* The REAL (i.e., page aligned) break value of the process. */
-static POINTER page_break_value;
+/* This is the size of a page. We round memory requests to this boundary. */
+static int page_size;
+
+/* Whenever we get memory from the system, get this many extra bytes. This
+ must be a multiple of page_size. */
+static int extra_bytes;
/* Macros for rounding. Note that rounding to any value is possible
- by changing the definition of PAGE. */
+ by changing the definition of PAGE. */
#define PAGE (getpagesize ())
-#define ALIGNED(addr) (((unsigned int) (addr) & (PAGE - 1)) == 0)
-#define ROUNDUP(size) (((unsigned int) (size) + PAGE) & ~(PAGE - 1))
-#define ROUND_TO_PAGE(addr) (addr & (~(PAGE - 1)))
+#define ALIGNED(addr) (((unsigned long int) (addr) & (page_size - 1)) == 0)
+#define ROUNDUP(size) (((unsigned long int) (size) + page_size - 1) \
+ & ~(page_size - 1))
+#define ROUND_TO_PAGE(addr) (addr & (~(page_size - 1)))
+
+#define MEM_ALIGN sizeof(double)
+#define MEM_ROUNDUP(addr) (((unsigned long int)(addr) + MEM_ALIGN - 1) \
+ & ~(MEM_ALIGN - 1))
+
+/* The hook `malloc' uses for the function which gets more space
+ from the system. */
+
+#ifndef SYSTEM_MALLOC
+extern POINTER (*__morecore) ();
+#endif
+
+
\f
-/* Managing "almost out of memory" warnings. */
+/***********************************************************************
+ Implementation using sbrk
+ ***********************************************************************/
-/* Level of warnings issued. */
-static int warnlevel;
+/* Data structures of heaps and blocs. */
-/* Function to call to issue a warning;
- 0 means don't issue them. */
-static void (*warnfunction) ();
+/* The relocatable objects, or blocs, and the malloc data
+ both reside within one or more heaps.
+ Each heap contains malloc data, running from `start' to `bloc_start',
+ and relocatable objects, running from `bloc_start' to `free'.
-static void
-check_memory_limits (address)
- POINTER address;
+ Relocatable objects may relocate within the same heap
+ or may move into another heap; the heaps themselves may grow
+ but they never move.
+
+ We try to make just one heap and make it larger as necessary.
+ But sometimes we can't do that, because we can't get contiguous
+ space to add onto the heap. When that happens, we start a new heap. */
+
+typedef struct heap
{
- SIZE data_size = address - data_space_start;
+ struct heap *next;
+ struct heap *prev;
+ /* Start of memory range of this heap. */
+ POINTER start;
+ /* End of memory range of this heap. */
+ POINTER end;
+ /* Start of relocatable data in this heap. */
+ POINTER bloc_start;
+ /* Start of unused space in this heap. */
+ POINTER free;
+ /* First bloc in this heap. */
+ struct bp *first_bloc;
+ /* Last bloc in this heap. */
+ struct bp *last_bloc;
+} *heap_ptr;
+
+#define NIL_HEAP ((heap_ptr) 0)
+#define HEAP_PTR_SIZE (sizeof (struct heap))
+
+/* This is the first heap object.
+ If we need additional heap objects, each one resides at the beginning of
+ the space it covers. */
+static struct heap heap_base;
+
+/* Head and tail of the list of heaps. */
+static heap_ptr first_heap, last_heap;
- switch (warnlevel)
- {
- case 0:
- if (data_size > (lim_data / 4) * 3)
- {
- warnlevel++;
- (*warnfunction) ("Warning: past 75% of memory limit");
- }
- break;
+/* These structures are allocated in the malloc arena.
+ The linked list is kept in order of increasing '.data' members.
+ The data blocks abut each other; if b->next is non-nil, then
+ b->data + b->size == b->next->data.
- case 1:
- if (data_size > (lim_data / 20) * 17)
- {
- warnlevel++;
- (*warnfunction) ("Warning: past 85% of memory limit");
- }
- break;
+ An element with variable==NIL denotes a freed block, which has not yet
+ been collected. They may only appear while r_alloc_freeze > 0, and will be
+ freed when the arena is thawed. Currently, these blocs are not reusable,
+ while the arena is frozen. Very inefficient. */
- case 2:
- if (data_size > (lim_data / 20) * 19)
- {
- warnlevel++;
- (*warnfunction) ("Warning: past 95% of memory limit");
- }
- break;
+typedef struct bp
+{
+ struct bp *next;
+ struct bp *prev;
+ POINTER *variable;
+ POINTER data;
+ SIZE size;
+ POINTER new_data; /* temporarily used for relocation */
+ struct heap *heap; /* Heap this bloc is in. */
+} *bloc_ptr;
- default:
- (*warnfunction) ("Warning: past acceptable memory limits");
- break;
- }
+#define NIL_BLOC ((bloc_ptr) 0)
+#define BLOC_PTR_SIZE (sizeof (struct bp))
+
+/* Head and tail of the list of relocatable blocs. */
+static bloc_ptr first_bloc, last_bloc;
+
+static int use_relocatable_buffers;
+
+/* If >0, no relocation whatsoever takes place. */
+static int r_alloc_freeze_level;
- if (EXCEEDS_ELISP_PTR (address))
- memory_full ();
-}
\f
/* Functions to get and return memory from the system. */
-/* Obtain SIZE bytes of space. If enough space is not presently available
- in our process reserve, (i.e., (page_break_value - break_value)),
- this means getting more page-aligned space from the system. */
+/* Find the heap that ADDRESS falls within. */
-static void
-obtain (size)
- SIZE size;
+static heap_ptr
+find_heap (address)
+ POINTER address;
{
- SIZE already_available = page_break_value - break_value;
+ heap_ptr heap;
- if (already_available < size)
+ for (heap = last_heap; heap; heap = heap->prev)
{
- SIZE get = ROUNDUP (size - already_available);
+ if (heap->start <= address && address <= heap->end)
+ return heap;
+ }
- if (warnfunction)
- check_memory_limits (page_break_value);
+ return NIL_HEAP;
+}
- if (((int) sbrk (get)) < 0)
- abort ();
+/* Find SIZE bytes of space in a heap.
+ Try to get them at ADDRESS (which must fall within some heap's range)
+ if we can get that many within one heap.
- page_break_value += get;
- }
+ If enough space is not presently available in our reserve, this means
+ getting more page-aligned space from the system. If the returned space
+ is not contiguous to the last heap, allocate a new heap, and append it
- break_value += size;
-}
+ obtain does not try to keep track of whether space is in use
+ or not in use. It just returns the address of SIZE bytes that
+ fall within a single heap. If you call obtain twice in a row
+ with the same arguments, you typically get the same value.
+ to the heap list. It's the caller's responsibility to keep
+ track of what space is in use.
-/* Obtain SIZE bytes of space and return a pointer to the new area. */
+ Return the address of the space if all went well, or zero if we couldn't
+ allocate the memory. */
static POINTER
-get_more_space (size)
- SIZE size;
+obtain (address, size)
+ POINTER address;
+ SIZE size;
{
- POINTER ptr = break_value;
- obtain (size);
- return ptr;
-}
+ heap_ptr heap;
+ SIZE already_available;
-/* Note that SIZE bytes of space have been relinquished by the process.
- If SIZE is more than a page, return the space to the system. */
+ /* Find the heap that ADDRESS falls within. */
+ for (heap = last_heap; heap; heap = heap->prev)
+ {
+ if (heap->start <= address && address <= heap->end)
+ break;
+ }
-static void
-relinquish (size)
- SIZE size;
-{
- POINTER new_page_break;
+ if (! heap)
+ abort ();
+
+ /* If we can't fit SIZE bytes in that heap,
+ try successive later heaps. */
+ while (heap && (char *) address + size > (char *) heap->end)
+ {
+ heap = heap->next;
+ if (heap == NIL_HEAP)
+ break;
+ address = heap->bloc_start;
+ }
- break_value -= size;
- new_page_break = (POINTER) ROUNDUP (break_value);
-
- if (new_page_break != page_break_value)
+ /* If we can't fit them within any existing heap,
+ get more space. */
+ if (heap == NIL_HEAP)
{
- if (((int) (sbrk ((char *) new_page_break
- - (char *) page_break_value))) < 0)
- abort ();
+ POINTER new = (*real_morecore)(0);
+ SIZE get;
+
+ already_available = (char *)last_heap->end - (char *)address;
+
+ if (new != last_heap->end)
+ {
+ /* Someone else called sbrk. Make a new heap. */
+
+ heap_ptr new_heap = (heap_ptr) MEM_ROUNDUP (new);
+ POINTER bloc_start = (POINTER) MEM_ROUNDUP ((POINTER)(new_heap + 1));
+
+ if ((*real_morecore) ((char *) bloc_start - (char *) new) != new)
+ return 0;
+
+ new_heap->start = new;
+ new_heap->end = bloc_start;
+ new_heap->bloc_start = bloc_start;
+ new_heap->free = bloc_start;
+ new_heap->next = NIL_HEAP;
+ new_heap->prev = last_heap;
+ new_heap->first_bloc = NIL_BLOC;
+ new_heap->last_bloc = NIL_BLOC;
+ last_heap->next = new_heap;
+ last_heap = new_heap;
+
+ address = bloc_start;
+ already_available = 0;
+ }
+
+ /* Add space to the last heap (which we may have just created).
+ Get some extra, so we can come here less often. */
- page_break_value = new_page_break;
+ get = size + extra_bytes - already_available;
+ get = (char *) ROUNDUP ((char *)last_heap->end + get)
+ - (char *) last_heap->end;
+
+ if ((*real_morecore) (get) != last_heap->end)
+ return 0;
+
+ last_heap->end = (char *) last_heap->end + get;
}
- /* Zero the space from the end of the "official" break to the actual
- break, so that bugs show up faster. */
- bzero (break_value, ((char *) page_break_value - (char *) break_value));
+ return address;
}
-\f
-/* The meat - allocating, freeing, and relocating blocs. */
-/* These structures are allocated in the malloc arena.
- The linked list is kept in order of increasing '.data' members.
- The data blocks abut each other; if b->next is non-nil, then
- b->data + b->size == b->next->data. */
-typedef struct bp
+/* Return unused heap space to the system
+ if there is a lot of unused space now.
+ This can make the last heap smaller;
+ it can also eliminate the last heap entirely. */
+
+static void
+relinquish ()
{
- struct bp *next;
- struct bp *prev;
- POINTER *variable;
- POINTER data;
- SIZE size;
-} *bloc_ptr;
+ register heap_ptr h;
+ int excess = 0;
-#define NIL_BLOC ((bloc_ptr) 0)
-#define BLOC_PTR_SIZE (sizeof (struct bp))
+ /* Add the amount of space beyond break_value
+ in all heaps which have extend beyond break_value at all. */
-/* Head and tail of the list of relocatable blocs. */
-static bloc_ptr first_bloc, last_bloc;
+ for (h = last_heap; h && break_value < h->end; h = h->prev)
+ {
+ excess += (char *) h->end - (char *) ((break_value < h->bloc_start)
+ ? h->bloc_start : break_value);
+ }
-/* Declared in dispnew.c, this version doesn't screw up if regions
- overlap. */
-extern void safe_bcopy ();
+ if (excess > extra_bytes * 2 && (*real_morecore) (0) == last_heap->end)
+ {
+ /* Keep extra_bytes worth of empty space.
+ And don't free anything unless we can free at least extra_bytes. */
+ excess -= extra_bytes;
+
+ if ((char *)last_heap->end - (char *)last_heap->bloc_start <= excess)
+ {
+ /* This heap should have no blocs in it. */
+ if (last_heap->first_bloc != NIL_BLOC
+ || last_heap->last_bloc != NIL_BLOC)
+ abort ();
+
+ /* Return the last heap, with its header, to the system. */
+ excess = (char *)last_heap->end - (char *)last_heap->start;
+ last_heap = last_heap->prev;
+ last_heap->next = NIL_HEAP;
+ }
+ else
+ {
+ excess = (char *) last_heap->end
+ - (char *) ROUNDUP ((char *)last_heap->end - excess);
+ last_heap->end = (char *) last_heap->end - excess;
+ }
+
+ if ((*real_morecore) (- excess) == 0)
+ {
+ /* If the system didn't want that much memory back, adjust
+ the end of the last heap to reflect that. This can occur
+ if break_value is still within the original data segment. */
+ last_heap->end = (char *) last_heap->end + excess;
+ /* Make sure that the result of the adjustment is accurate.
+ It should be, for the else clause above; the other case,
+ which returns the entire last heap to the system, seems
+ unlikely to trigger this mode of failure. */
+ if (last_heap->end != (*real_morecore) (0))
+ abort ();
+ }
+ }
+}
+
+/* Return the total size in use by relocating allocator,
+ above where malloc gets space. */
+
+long
+r_alloc_size_in_use ()
+{
+ return (char *) break_value - (char *) virtual_break_value;
+}
+\f
+/* The meat - allocating, freeing, and relocating blocs. */
/* Find the bloc referenced by the address in PTR. Returns a pointer
- to that block. */
+ to that block. */
static bloc_ptr
find_bloc (ptr)
}
/* Allocate a bloc of SIZE bytes and append it to the chain of blocs.
- Returns a pointer to the new bloc. */
+ Returns a pointer to the new bloc, or zero if we couldn't allocate
+ memory for the new block. */
static bloc_ptr
get_bloc (size)
SIZE size;
{
- register bloc_ptr new_bloc = (bloc_ptr) malloc (BLOC_PTR_SIZE);
+ register bloc_ptr new_bloc;
+ register heap_ptr heap;
+
+ if (! (new_bloc = (bloc_ptr) malloc (BLOC_PTR_SIZE))
+ || ! (new_bloc->data = obtain (break_value, size)))
+ {
+ if (new_bloc)
+ free (new_bloc);
+
+ return 0;
+ }
+
+ break_value = (char *) new_bloc->data + size;
- new_bloc->data = get_more_space (size);
new_bloc->size = size;
new_bloc->next = NIL_BLOC;
new_bloc->variable = (POINTER *) NIL;
+ new_bloc->new_data = 0;
+
+ /* Record in the heap that this space is in use. */
+ heap = find_heap (new_bloc->data);
+ heap->free = break_value;
+
+ /* Maintain the correspondence between heaps and blocs. */
+ new_bloc->heap = heap;
+ heap->last_bloc = new_bloc;
+ if (heap->first_bloc == NIL_BLOC)
+ heap->first_bloc = new_bloc;
+ /* Put this bloc on the doubly-linked list of blocs. */
if (first_bloc)
{
new_bloc->prev = last_bloc;
return new_bloc;
}
+\f
+/* Calculate new locations of blocs in the list beginning with BLOC,
+ relocating it to start at ADDRESS, in heap HEAP. If enough space is
+ not presently available in our reserve, call obtain for
+ more space.
+
+ Store the new location of each bloc in its new_data field.
+ Do not touch the contents of blocs or break_value. */
+
+static int
+relocate_blocs (bloc, heap, address)
+ bloc_ptr bloc;
+ heap_ptr heap;
+ POINTER address;
+{
+ register bloc_ptr b = bloc;
+
+ /* No need to ever call this if arena is frozen, bug somewhere! */
+ if (r_alloc_freeze_level)
+ abort();
+
+ while (b)
+ {
+ /* If bloc B won't fit within HEAP,
+ move to the next heap and try again. */
+ while (heap && (char *) address + b->size > (char *) heap->end)
+ {
+ heap = heap->next;
+ if (heap == NIL_HEAP)
+ break;
+ address = heap->bloc_start;
+ }
+
+ /* If BLOC won't fit in any heap,
+ get enough new space to hold BLOC and all following blocs. */
+ if (heap == NIL_HEAP)
+ {
+ register bloc_ptr tb = b;
+ register SIZE s = 0;
+
+ /* Add up the size of all the following blocs. */
+ while (tb != NIL_BLOC)
+ {
+ if (tb->variable)
+ s += tb->size;
+
+ tb = tb->next;
+ }
-/* Relocate all blocs from BLOC on upward in the list to the zone
- indicated by ADDRESS. Direction of relocation is determined by
- the position of ADDRESS relative to BLOC->data.
+ /* Get that space. */
+ address = obtain (address, s);
+ if (address == 0)
+ return 0;
- Note that ordering of blocs is not affected by this function. */
+ heap = last_heap;
+ }
+
+ /* Record the new address of this bloc
+ and update where the next bloc can start. */
+ b->new_data = address;
+ if (b->variable)
+ address = (char *) address + b->size;
+ b = b->next;
+ }
+
+ return 1;
+}
+
+/* Reorder the bloc BLOC to go before bloc BEFORE in the doubly linked list.
+ This is necessary if we put the memory of space of BLOC
+ before that of BEFORE. */
+
+static void
+reorder_bloc (bloc, before)
+ bloc_ptr bloc, before;
+{
+ bloc_ptr prev, next;
+
+ /* Splice BLOC out from where it is. */
+ prev = bloc->prev;
+ next = bloc->next;
+
+ if (prev)
+ prev->next = next;
+ if (next)
+ next->prev = prev;
+
+ /* Splice it in before BEFORE. */
+ prev = before->prev;
+
+ if (prev)
+ prev->next = bloc;
+ bloc->prev = prev;
+
+ before->prev = bloc;
+ bloc->next = before;
+}
+\f
+/* Update the records of which heaps contain which blocs, starting
+ with heap HEAP and bloc BLOC. */
static void
-relocate_some_blocs (bloc, address)
+update_heap_bloc_correspondence (bloc, heap)
bloc_ptr bloc;
- POINTER address;
+ heap_ptr heap;
{
register bloc_ptr b;
- POINTER data_zone = bloc->data;
- register SIZE data_zone_size = 0;
- register SIZE offset = bloc->data - address;
- POINTER new_data_zone = data_zone - offset;
+ /* Initialize HEAP's status to reflect blocs before BLOC. */
+ if (bloc != NIL_BLOC && bloc->prev != NIL_BLOC && bloc->prev->heap == heap)
+ {
+ /* The previous bloc is in HEAP. */
+ heap->last_bloc = bloc->prev;
+ heap->free = (char *) bloc->prev->data + bloc->prev->size;
+ }
+ else
+ {
+ /* HEAP contains no blocs before BLOC. */
+ heap->first_bloc = NIL_BLOC;
+ heap->last_bloc = NIL_BLOC;
+ heap->free = heap->bloc_start;
+ }
+
+ /* Advance through blocs one by one. */
for (b = bloc; b != NIL_BLOC; b = b->next)
{
- data_zone_size += b->size;
- b->data -= offset;
- *b->variable = b->data;
+ /* Advance through heaps, marking them empty,
+ till we get to the one that B is in. */
+ while (heap)
+ {
+ if (heap->bloc_start <= b->data && b->data <= heap->end)
+ break;
+ heap = heap->next;
+ /* We know HEAP is not null now,
+ because there has to be space for bloc B. */
+ heap->first_bloc = NIL_BLOC;
+ heap->last_bloc = NIL_BLOC;
+ heap->free = heap->bloc_start;
+ }
+
+ /* Update HEAP's status for bloc B. */
+ heap->free = (char *) b->data + b->size;
+ heap->last_bloc = b;
+ if (heap->first_bloc == NIL_BLOC)
+ heap->first_bloc = b;
+
+ /* Record that B is in HEAP. */
+ b->heap = heap;
}
- safe_bcopy (data_zone, new_data_zone, data_zone_size);
+ /* If there are any remaining heaps and no blocs left,
+ mark those heaps as empty. */
+ heap = heap->next;
+ while (heap)
+ {
+ heap->first_bloc = NIL_BLOC;
+ heap->last_bloc = NIL_BLOC;
+ heap->free = heap->bloc_start;
+ heap = heap->next;
+ }
}
+\f
+/* Resize BLOC to SIZE bytes. This relocates the blocs
+ that come after BLOC in memory. */
+
+static int
+resize_bloc (bloc, size)
+ bloc_ptr bloc;
+ SIZE size;
+{
+ register bloc_ptr b;
+ heap_ptr heap;
+ POINTER address;
+ SIZE old_size;
+
+ /* No need to ever call this if arena is frozen, bug somewhere! */
+ if (r_alloc_freeze_level)
+ abort();
+
+ if (bloc == NIL_BLOC || size == bloc->size)
+ return 1;
+
+ for (heap = first_heap; heap != NIL_HEAP; heap = heap->next)
+ {
+ if (heap->bloc_start <= bloc->data && bloc->data <= heap->end)
+ break;
+ }
+
+ if (heap == NIL_HEAP)
+ abort ();
+
+ old_size = bloc->size;
+ bloc->size = size;
+
+ /* Note that bloc could be moved into the previous heap. */
+ address = (bloc->prev ? (char *) bloc->prev->data + bloc->prev->size
+ : (char *) first_heap->bloc_start);
+ while (heap)
+ {
+ if (heap->bloc_start <= address && address <= heap->end)
+ break;
+ heap = heap->prev;
+ }
+
+ if (! relocate_blocs (bloc, heap, address))
+ {
+ bloc->size = old_size;
+ return 0;
+ }
+
+ if (size > old_size)
+ {
+ for (b = last_bloc; b != bloc; b = b->prev)
+ {
+ if (!b->variable)
+ {
+ b->size = 0;
+ b->data = b->new_data;
+ }
+ else
+ {
+ safe_bcopy (b->data, b->new_data, b->size);
+ *b->variable = b->data = b->new_data;
+ }
+ }
+ if (!bloc->variable)
+ {
+ bloc->size = 0;
+ bloc->data = bloc->new_data;
+ }
+ else
+ {
+ safe_bcopy (bloc->data, bloc->new_data, old_size);
+ bzero ((char *) bloc->new_data + old_size, size - old_size);
+ *bloc->variable = bloc->data = bloc->new_data;
+ }
+ }
+ else
+ {
+ for (b = bloc; b != NIL_BLOC; b = b->next)
+ {
+ if (!b->variable)
+ {
+ b->size = 0;
+ b->data = b->new_data;
+ }
+ else
+ {
+ safe_bcopy (b->data, b->new_data, b->size);
+ *b->variable = b->data = b->new_data;
+ }
+ }
+ }
+
+ update_heap_bloc_correspondence (bloc, heap);
-/* Free BLOC from the chain of blocs, relocating any blocs above it
- and returning BLOC->size bytes to the free area. */
+ break_value = (last_bloc ? (char *) last_bloc->data + last_bloc->size
+ : (char *) first_heap->bloc_start);
+ return 1;
+}
+\f
+/* Free BLOC from the chain of blocs, relocating any blocs above it.
+ This may return space to the system. */
static void
free_bloc (bloc)
bloc_ptr bloc;
{
+ heap_ptr heap = bloc->heap;
+
+ if (r_alloc_freeze_level)
+ {
+ bloc->variable = (POINTER *) NIL;
+ return;
+ }
+
+ resize_bloc (bloc, 0);
+
if (bloc == first_bloc && bloc == last_bloc)
{
first_bloc = last_bloc = NIL_BLOC;
{
first_bloc = bloc->next;
first_bloc->prev = NIL_BLOC;
- relocate_some_blocs (bloc->next, bloc->data);
}
else
{
bloc->next->prev = bloc->prev;
bloc->prev->next = bloc->next;
- relocate_some_blocs (bloc->next, bloc->data);
}
- relinquish (bloc->size);
+ /* Update the records of which blocs are in HEAP. */
+ if (heap->first_bloc == bloc)
+ {
+ if (bloc->next != 0 && bloc->next->heap == heap)
+ heap->first_bloc = bloc->next;
+ else
+ heap->first_bloc = heap->last_bloc = NIL_BLOC;
+ }
+ if (heap->last_bloc == bloc)
+ {
+ if (bloc->prev != 0 && bloc->prev->heap == heap)
+ heap->last_bloc = bloc->prev;
+ else
+ heap->first_bloc = heap->last_bloc = NIL_BLOC;
+ }
+
+ relinquish ();
free (bloc);
}
\f
/* Interface routines. */
-static int use_relocatable_buffers;
+/* Obtain SIZE bytes of storage from the free pool, or the system, as
+ necessary. If relocatable blocs are in use, this means relocating
+ them. This function gets plugged into the GNU malloc's __morecore
+ hook.
+
+ We provide hysteresis, never relocating by less than extra_bytes.
-/* Obtain SIZE bytes of storage from the free pool, or the system,
- as neccessary. If relocatable blocs are in use, this means
- relocating them. */
+ If we're out of memory, we should return zero, to imitate the other
+ __morecore hook values - in particular, __default_morecore in the
+ GNU malloc package. */
-POINTER
+POINTER
r_alloc_sbrk (size)
long size;
{
- POINTER ptr;
+ register bloc_ptr b;
+ POINTER address;
+
+ if (! r_alloc_initialized)
+ r_alloc_init ();
if (! use_relocatable_buffers)
- return sbrk (size);
+ return (*real_morecore) (size);
+
+ if (size == 0)
+ return virtual_break_value;
if (size > 0)
{
- obtain (size);
- if (first_bloc)
+ /* Allocate a page-aligned space. GNU malloc would reclaim an
+ extra space if we passed an unaligned one. But we could
+ not always find a space which is contiguous to the previous. */
+ POINTER new_bloc_start;
+ heap_ptr h = first_heap;
+ SIZE get = ROUNDUP (size);
+
+ address = (POINTER) ROUNDUP (virtual_break_value);
+
+ /* Search the list upward for a heap which is large enough. */
+ while ((char *) h->end < (char *) MEM_ROUNDUP ((char *)address + get))
+ {
+ h = h->next;
+ if (h == NIL_HEAP)
+ break;
+ address = (POINTER) ROUNDUP (h->start);
+ }
+
+ /* If not found, obtain more space. */
+ if (h == NIL_HEAP)
{
- relocate_some_blocs (first_bloc, first_bloc->data + size);
+ get += extra_bytes + page_size;
+
+ if (! obtain (address, get))
+ return 0;
- /* Zero out the space we just allocated, to help catch bugs
- quickly. */
- bzero (virtual_break_value, size);
+ if (first_heap == last_heap)
+ address = (POINTER) ROUNDUP (virtual_break_value);
+ else
+ address = (POINTER) ROUNDUP (last_heap->start);
+ h = last_heap;
+ }
+
+ new_bloc_start = (POINTER) MEM_ROUNDUP ((char *)address + get);
+
+ if (first_heap->bloc_start < new_bloc_start)
+ {
+ /* This is no clean solution - no idea how to do it better. */
+ if (r_alloc_freeze_level)
+ return NIL;
+
+ /* There is a bug here: if the above obtain call succeeded, but the
+ relocate_blocs call below does not succeed, we need to free
+ the memory that we got with obtain. */
+
+ /* Move all blocs upward. */
+ if (! relocate_blocs (first_bloc, h, new_bloc_start))
+ return 0;
+
+ /* Note that (POINTER)(h+1) <= new_bloc_start since
+ get >= page_size, so the following does not destroy the heap
+ header. */
+ for (b = last_bloc; b != NIL_BLOC; b = b->prev)
+ {
+ safe_bcopy (b->data, b->new_data, b->size);
+ *b->variable = b->data = b->new_data;
+ }
+
+ h->bloc_start = new_bloc_start;
+
+ update_heap_bloc_correspondence (first_bloc, h);
+ }
+ if (h != first_heap)
+ {
+ /* Give up managing heaps below the one the new
+ virtual_break_value points to. */
+ first_heap->prev = NIL_HEAP;
+ first_heap->next = h->next;
+ first_heap->start = h->start;
+ first_heap->end = h->end;
+ first_heap->free = h->free;
+ first_heap->first_bloc = h->first_bloc;
+ first_heap->last_bloc = h->last_bloc;
+ first_heap->bloc_start = h->bloc_start;
+
+ if (first_heap->next)
+ first_heap->next->prev = first_heap;
+ else
+ last_heap = first_heap;
}
+
+ bzero (address, size);
}
- else if (size < 0)
+ else /* size < 0 */
{
- if (first_bloc)
- relocate_some_blocs (first_bloc, first_bloc->data + size);
- relinquish (- size);
+ SIZE excess = (char *)first_heap->bloc_start
+ - ((char *)virtual_break_value + size);
+
+ address = virtual_break_value;
+
+ if (r_alloc_freeze_level == 0 && excess > 2 * extra_bytes)
+ {
+ excess -= extra_bytes;
+ first_heap->bloc_start
+ = (POINTER) MEM_ROUNDUP ((char *)first_heap->bloc_start - excess);
+
+ relocate_blocs (first_bloc, first_heap, first_heap->bloc_start);
+
+ for (b = first_bloc; b != NIL_BLOC; b = b->next)
+ {
+ safe_bcopy (b->data, b->new_data, b->size);
+ *b->variable = b->data = b->new_data;
+ }
+ }
+
+ if ((char *)virtual_break_value + size < (char *)first_heap->start)
+ {
+ /* We found an additional space below the first heap */
+ first_heap->start = (POINTER) ((char *)virtual_break_value + size);
+ }
}
- ptr = virtual_break_value;
- virtual_break_value += size;
- return ptr;
+ virtual_break_value = (POINTER) ((char *)address + size);
+ break_value = (last_bloc
+ ? (char *) last_bloc->data + last_bloc->size
+ : (char *) first_heap->bloc_start);
+ if (size < 0)
+ relinquish ();
+
+ return address;
}
+
/* Allocate a relocatable bloc of storage of size SIZE. A pointer to
the data is returned in *PTR. PTR is thus the address of some variable
- which will use the data area. */
+ which will use the data area.
+
+ The allocation of 0 bytes is valid.
+ In case r_alloc_freeze is set, a best fit of unused blocs could be done
+ before allocating a new area. Not yet done.
+
+ If we can't allocate the necessary memory, set *PTR to zero, and
+ return zero. */
POINTER
r_alloc (ptr, size)
{
register bloc_ptr new_bloc;
- new_bloc = get_bloc (size);
- new_bloc->variable = ptr;
- *ptr = new_bloc->data;
+ if (! r_alloc_initialized)
+ r_alloc_init ();
+
+ new_bloc = get_bloc (MEM_ROUNDUP (size));
+ if (new_bloc)
+ {
+ new_bloc->variable = ptr;
+ *ptr = new_bloc->data;
+ }
+ else
+ *ptr = 0;
return *ptr;
}
-/* Free a bloc of relocatable storage whose data is pointed to by PTR. */
+/* Free a bloc of relocatable storage whose data is pointed to by PTR.
+ Store 0 in *PTR to show there's no block allocated. */
void
r_alloc_free (ptr)
{
register bloc_ptr dead_bloc;
+ if (! r_alloc_initialized)
+ r_alloc_init ();
+
dead_bloc = find_bloc (ptr);
if (dead_bloc == NIL_BLOC)
abort ();
free_bloc (dead_bloc);
+ *ptr = 0;
+
+#ifdef emacs
+ refill_memory_reserve ();
+#endif
}
/* Given a pointer at address PTR to relocatable data, resize it to SIZE.
- This is done by shifting all blocks above this one up in memory,
- unless SIZE is less than or equal to the current bloc size, in
- which case nothing happens and the current value is returned.
+ Do this by shifting all blocks above this one up in memory, unless
+ SIZE is less than or equal to the current bloc size, in which case
+ do nothing.
+
+ In case r_alloc_freeze is set, a new bloc is allocated, and the
+ memory copied to it. Not very efficient. We could traverse the
+ bloc_list for a best fit of free blocs first.
- The contents of PTR is changed to reflect the new bloc, and this
- value is returned. */
+ Change *PTR to reflect the new bloc, and return this value.
+
+ If more memory cannot be allocated, then leave *PTR unchanged, and
+ return zero. */
POINTER
r_re_alloc (ptr, size)
{
register bloc_ptr bloc;
+ if (! r_alloc_initialized)
+ r_alloc_init ();
+
+ if (!*ptr)
+ return r_alloc (ptr, size);
+ if (!size)
+ {
+ r_alloc_free (ptr);
+ return r_alloc (ptr, 0);
+ }
+
bloc = find_bloc (ptr);
if (bloc == NIL_BLOC)
abort ();
- if (size <= bloc->size)
- /* Wouldn't it be useful to actually resize the bloc here? */
- return *ptr;
+ if (size < bloc->size)
+ {
+ /* Wouldn't it be useful to actually resize the bloc here? */
+ /* I think so too, but not if it's too expensive... */
+ if ((bloc->size - MEM_ROUNDUP (size) >= page_size)
+ && r_alloc_freeze_level == 0)
+ {
+ resize_bloc (bloc, MEM_ROUNDUP (size));
+ /* Never mind if this fails, just do nothing... */
+ /* It *should* be infallible! */
+ }
+ }
+ else if (size > bloc->size)
+ {
+ if (r_alloc_freeze_level)
+ {
+ bloc_ptr new_bloc;
+ new_bloc = get_bloc (MEM_ROUNDUP (size));
+ if (new_bloc)
+ {
+ new_bloc->variable = ptr;
+ *ptr = new_bloc->data;
+ bloc->variable = (POINTER *) NIL;
+ }
+ else
+ return NIL;
+ }
+ else
+ {
+ if (! resize_bloc (bloc, MEM_ROUNDUP (size)))
+ return NIL;
+ }
+ }
+ return *ptr;
+}
- obtain (size - bloc->size);
- relocate_some_blocs (bloc->next, bloc->data + size);
+/* Disable relocations, after making room for at least SIZE bytes
+ of non-relocatable heap if possible. The relocatable blocs are
+ guaranteed to hold still until thawed, even if this means that
+ malloc must return a null pointer. */
- /* Zero out the new space in the bloc, to help catch bugs faster. */
- bzero (bloc->data + bloc->size, size - bloc->size);
+void
+r_alloc_freeze (size)
+ long size;
+{
+ if (! r_alloc_initialized)
+ r_alloc_init ();
+
+ /* If already frozen, we can't make any more room, so don't try. */
+ if (r_alloc_freeze_level > 0)
+ size = 0;
+ /* If we can't get the amount requested, half is better than nothing. */
+ while (size > 0 && r_alloc_sbrk (size) == 0)
+ size /= 2;
+ ++r_alloc_freeze_level;
+ if (size > 0)
+ r_alloc_sbrk (-size);
+}
- /* Indicate that this block has a new size. */
- bloc->size = size;
+void
+r_alloc_thaw ()
+{
- return *ptr;
+ if (! r_alloc_initialized)
+ r_alloc_init ();
+
+ if (--r_alloc_freeze_level < 0)
+ abort ();
+
+ /* This frees all unused blocs. It is not too inefficient, as the resize
+ and bcopy is done only once. Afterwards, all unreferenced blocs are
+ already shrunk to zero size. */
+ if (!r_alloc_freeze_level)
+ {
+ bloc_ptr *b = &first_bloc;
+ while (*b)
+ if (!(*b)->variable)
+ free_bloc (*b);
+ else
+ b = &(*b)->next;
+ }
}
-\f
-/* The hook `malloc' uses for the function which gets more space
- from the system. */
-extern POINTER (*__morecore) ();
-/* A flag to indicate whether we have initialized ralloc yet. For
- Emacs's sake, please do not make this local to malloc_init; on some
- machines, the dumping procedure makes all static variables
- read-only. On these machines, the word static is #defined to be
- the empty string, meaning that malloc_initialized becomes an
- automatic variable, and loses its value each time Emacs is started
- up. */
-static int malloc_initialized = 0;
-/* Intialize various things for memory allocation. */
+#if defined (emacs) && defined (DOUG_LEA_MALLOC)
+
+/* Reinitialize the morecore hook variables after restarting a dumped
+ Emacs. This is needed when using Doug Lea's malloc from GNU libc. */
+void
+r_alloc_reinit ()
+{
+ /* Only do this if the hook has been reset, so that we don't get an
+ infinite loop, in case Emacs was linked statically. */
+ if (__morecore != r_alloc_sbrk)
+ {
+ real_morecore = __morecore;
+ __morecore = r_alloc_sbrk;
+ }
+}
+
+#endif /* emacs && DOUG_LEA_MALLOC */
+
+#ifdef DEBUG
+
+#include <assert.h>
void
-malloc_init (start, warn_func)
- POINTER start;
- void (*warn_func) ();
+r_alloc_check ()
{
- if (start)
- data_space_start = start;
+ int found = 0;
+ heap_ptr h, ph = 0;
+ bloc_ptr b, pb = 0;
- if (malloc_initialized)
+ if (!r_alloc_initialized)
return;
- malloc_initialized = 1;
- __morecore = r_alloc_sbrk;
+ assert (first_heap);
+ assert (last_heap->end <= (POINTER) sbrk (0));
+ assert ((POINTER) first_heap < first_heap->start);
+ assert (first_heap->start <= virtual_break_value);
+ assert (virtual_break_value <= first_heap->end);
- virtual_break_value = break_value = sbrk (0);
- if (break_value == (POINTER)NULL)
- (*warn_func)("Malloc initialization returned 0 from sbrk(0).");
+ for (h = first_heap; h; h = h->next)
+ {
+ assert (h->prev == ph);
+ assert ((POINTER) ROUNDUP (h->end) == h->end);
+#if 0 /* ??? The code in ralloc.c does not really try to ensure
+ the heap start has any sort of alignment.
+ Perhaps it should. */
+ assert ((POINTER) MEM_ROUNDUP (h->start) == h->start);
+#endif
+ assert ((POINTER) MEM_ROUNDUP (h->bloc_start) == h->bloc_start);
+ assert (h->start <= h->bloc_start && h->bloc_start <= h->end);
+
+ if (ph)
+ {
+ assert (ph->end < h->start);
+ assert (h->start <= (POINTER)h && (POINTER)(h+1) <= h->bloc_start);
+ }
- page_break_value = (POINTER) ROUNDUP (break_value);
- bzero (break_value, (page_break_value - break_value));
- use_relocatable_buffers = 1;
+ if (h->bloc_start <= break_value && break_value <= h->end)
+ found = 1;
- lim_data = 0;
- warnlevel = 0;
- warnfunction = warn_func;
+ ph = h;
+ }
+
+ assert (found);
+ assert (last_heap == ph);
+
+ for (b = first_bloc; b; b = b->next)
+ {
+ assert (b->prev == pb);
+ assert ((POINTER) MEM_ROUNDUP (b->data) == b->data);
+ assert ((SIZE) MEM_ROUNDUP (b->size) == b->size);
- get_lim_data ();
+ ph = 0;
+ for (h = first_heap; h; h = h->next)
+ {
+ if (h->bloc_start <= b->data && b->data + b->size <= h->end)
+ break;
+ ph = h;
+ }
+
+ assert (h);
+
+ if (pb && pb->data + pb->size != b->data)
+ {
+ assert (ph && b->data == h->bloc_start);
+ while (ph)
+ {
+ if (ph->bloc_start <= pb->data
+ && pb->data + pb->size <= ph->end)
+ {
+ assert (pb->data + pb->size + b->size > ph->end);
+ break;
+ }
+ else
+ {
+ assert (ph->bloc_start + b->size > ph->end);
+ }
+ ph = ph->prev;
+ }
+ }
+ pb = b;
+ }
+
+ assert (last_bloc == pb);
+
+ if (last_bloc)
+ assert (last_bloc->data + last_bloc->size == break_value);
+ else
+ assert (first_heap->bloc_start == break_value);
}
+
+#endif /* DEBUG */
+
+
+\f
+/***********************************************************************
+ Initialization
+ ***********************************************************************/
+
+/* Initialize various things for memory allocation. */
+
+static void
+r_alloc_init ()
+{
+ if (r_alloc_initialized)
+ return;
+ r_alloc_initialized = 1;
+
+ page_size = PAGE;
+#ifndef SYSTEM_MALLOC
+ real_morecore = __morecore;
+ __morecore = r_alloc_sbrk;
+
+ first_heap = last_heap = &heap_base;
+ first_heap->next = first_heap->prev = NIL_HEAP;
+ first_heap->start = first_heap->bloc_start
+ = virtual_break_value = break_value = (*real_morecore) (0);
+ if (break_value == NIL)
+ abort ();
+
+ extra_bytes = ROUNDUP (50000);
+#endif
+
+#ifdef DOUG_LEA_MALLOC
+ BLOCK_INPUT;
+ mallopt (M_TOP_PAD, 64 * 4096);
+ UNBLOCK_INPUT;
+#else
+#ifndef SYSTEM_MALLOC
+ /* Give GNU malloc's morecore some hysteresis
+ so that we move all the relocatable blocks much less often. */
+ __malloc_extra_blocks = 64;
+#endif
+#endif
+
+#ifndef SYSTEM_MALLOC
+ first_heap->end = (POINTER) ROUNDUP (first_heap->start);
+
+ /* The extra call to real_morecore guarantees that the end of the
+ address space is a multiple of page_size, even if page_size is
+ not really the page size of the system running the binary in
+ which page_size is stored. This allows a binary to be built on a
+ system with one page size and run on a system with a smaller page
+ size. */
+ (*real_morecore) ((char *) first_heap->end - (char *) first_heap->start);
+
+ /* Clear the rest of the last page; this memory is in our address space
+ even though it is after the sbrk value. */
+ /* Doubly true, with the additional call that explicitly adds the
+ rest of that page to the address space. */
+ bzero (first_heap->start,
+ (char *) first_heap->end - (char *) first_heap->start);
+ virtual_break_value = break_value = first_heap->bloc_start = first_heap->end;
+#endif
+
+ use_relocatable_buffers = 1;
+}
+
+/* arch-tag: 6a524a15-faff-44c8-95d4-a5da6f55110f
+ (do not change this comment) */
HCoop / bpt / emacs.git / blobdiff