X-Git-Url: https://code.delx.au/gnu-emacs/blobdiff_plain/8c7f1e3596d1e4a52598392fbd78458f70bcb2c3..7147863a1cadafc27dcab1d3f28ccab2224a6316:/src/ralloc.c diff --git a/src/ralloc.c b/src/ralloc.c index d06472f8ea..83a26dd35d 100644 --- a/src/ralloc.c +++ b/src/ralloc.c @@ -1,11 +1,12 @@ -/* Block-relocating memory allocator. - Copyright (C) 1992 Free Software Foundation, Inc. +/* Block-relocating memory allocator. + Copyright (C) 1993, 1995, 2000, 2002, 2003, 2004, + 2005, 2006 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, @@ -15,186 +16,385 @@ GNU General Public License for more details. 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 #include "lisp.h" /* Needed for VALBITS. */ -#undef NULL -#include "mem_limits.h" +#include "blockinput.h" + +#ifdef HAVE_UNISTD_H +#include +#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 + +typedef size_t SIZE; +typedef void *POINTER; + +#include +#include + +#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 (); + /* 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 + + -/* 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 (); -} /* 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; } - -/* 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; + long 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; +} + +/* 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) @@ -214,19 +414,43 @@ 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; @@ -241,41 +465,284 @@ get_bloc (size) return new_bloc; } + +/* 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; +} + +/* 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; + } } + +/* 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; + } -/* Free BLOC from the chain of blocs, relocating any blocs above it - and returning BLOC->size bytes to the free area. */ + 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); + + break_value = (last_bloc ? (char *) last_bloc->data + last_bloc->size + : (char *) first_heap->bloc_start); + return 1; +} + +/* 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; @@ -289,63 +756,197 @@ free_bloc (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); } /* 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) @@ -354,14 +955,23 @@ 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) @@ -369,86 +979,317 @@ 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 obtaining a new block and freeing the - old, unless SIZE is less than or equal to the current bloc size, - in which case nothing happens and the current value is returned. +/* Given a pointer at address PTR to relocatable data, resize it to SIZE. + 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) POINTER *ptr; SIZE size; { - register bloc_ptr old_bloc, new_bloc; + 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); + } - old_bloc = find_bloc (ptr); - if (old_bloc == NIL_BLOC) + bloc = find_bloc (ptr); + if (bloc == NIL_BLOC) abort (); - if (size <= old_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; +} - new_bloc = get_bloc (size); - new_bloc->variable = ptr; - safe_bcopy (old_bloc->data, new_bloc->data, old_bloc->size); - *ptr = new_bloc->data; +/* 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. */ - free_bloc (old_bloc); +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); +} - return *ptr; +void +r_alloc_thaw () +{ + + 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; + } } - -/* 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 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 */ + + + +/*********************************************************************** + 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) */