src/ralloc.c

   1 /* Block-relocating memory allocator.
   2    Copyright (C) 1993 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Emacs.
   5
   6 GNU Emacs is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 1, or (at your option)
   9 any later version.
  10
  11 GNU Emacs is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Emacs; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19
  20 /* NOTES:
  21
  22    Only relocate the blocs neccessary for SIZE in r_alloc_sbrk,
  23    rather than all of them.  This means allowing for a possible
  24    hole between the first bloc and the end of malloc storage. */
  25
  26 #ifdef emacs
  27
  28 #include "config.h"
  29 #include "lisp.h"               /* Needed for VALBITS.  */
  30
  31 #undef NULL
  32
  33 /* The important properties of this type are that 1) it's a pointer, and
  34    2) arithmetic on it should work as if the size of the object pointed
  35    to has a size of 1.  */
  36 #if 0 /* Arithmetic on void* is a GCC extension.  */
  37 #ifdef __STDC__
  38 typedef void *POINTER;
  39 #else
  40
  41 #ifdef  HAVE_CONFIG_H
  42 #include "config.h"
  43 #endif
  44
  45 typedef char *POINTER;
  46
  47 #endif
  48 #endif /* 0 */
  49
  50 /* Unconditionally use char * for this.  */
  51 typedef char *POINTER;
  52
  53 typedef unsigned long SIZE;
  54
  55 /* Declared in dispnew.c, this version doesn't screw up if regions
  56    overlap.  */
  57 extern void safe_bcopy ();
  58
  59 #include "getpagesize.h"
  60
  61 #else   /* Not emacs.  */
  62
  63 #include <stddef.h>
  64
  65 typedef size_t SIZE;
  66 typedef void *POINTER;
  67
  68 #include <unistd.h>
  69 #include <malloc.h>
  70 #include <string.h>
  71
  72 #define safe_bcopy(x, y, z) memmove (y, x, z)
  73
  74 #endif  /* emacs.  */
  75
  76 #define NIL ((POINTER) 0)
  77
  78 /* A flag to indicate whether we have initialized ralloc yet.  For
  79    Emacs's sake, please do not make this local to malloc_init; on some
  80    machines, the dumping procedure makes all static variables
  81    read-only.  On these machines, the word static is #defined to be
  82    the empty string, meaning that r_alloc_initialized becomes an
  83    automatic variable, and loses its value each time Emacs is started up.  */
  84 static int r_alloc_initialized = 0;
  85
  86 static void r_alloc_init ();
  87 \f
  88 /* Declarations for working with the malloc, ralloc, and system breaks.  */
  89
  90 /* Function to set the real break value. */
  91 static POINTER (*real_morecore) ();
  92
  93 /* The break value, as seen by malloc (). */
  94 static POINTER virtual_break_value;
  95
  96 /* The break value, viewed by the relocatable blocs. */
  97 static POINTER break_value;
  98
  99 /* The REAL (i.e., page aligned) break value of the process. */
 100 static POINTER page_break_value;
 101
 102 /* This is the size of a page.  We round memory requests to this boundary.  */
 103 static int page_size;
 104
 105 /* Whenever we get memory from the system, get this many extra bytes.  This
 106    must be a multiple of page_size.  */
 107 static int extra_bytes;
 108
 109 /* Macros for rounding.  Note that rounding to any value is possible
 110    by changing the definition of PAGE. */
 111 #define PAGE (getpagesize ())
 112 #define ALIGNED(addr) (((unsigned int) (addr) & (page_size - 1)) == 0)
 113 #define ROUNDUP(size) (((unsigned int) (size) + page_size - 1) & ~(page_size - 1))
 114 #define ROUND_TO_PAGE(addr) (addr & (~(page_size - 1)))
 115 \f
 116 /* Functions to get and return memory from the system.  */
 117
 118 /* Obtain SIZE bytes of space.  If enough space is not presently available
 119    in our process reserve, (i.e., (page_break_value - break_value)),
 120    this means getting more page-aligned space from the system.
 121
 122    Return non-zero if all went well, or zero if we couldn't allocate
 123    the memory.  */
 124 static int
 125 obtain (size)
 126      SIZE size;
 127 {
 128   SIZE already_available = page_break_value - break_value;
 129
 130   if (already_available < size)
 131     {
 132       SIZE get = ROUNDUP (size - already_available);
 133       /* Get some extra, so we can come here less often.  */
 134       get += extra_bytes;
 135
 136       if ((*real_morecore) (get) == 0)
 137         return 0;
 138
 139       page_break_value += get;
 140     }
 141
 142   break_value += size;
 143
 144   return 1;
 145 }
 146
 147 /* Obtain SIZE bytes of space and return a pointer to the new area.
 148    If we could not allocate the space, return zero.  */
 149
 150 static POINTER
 151 get_more_space (size)
 152      SIZE size;
 153 {
 154   POINTER ptr = break_value;
 155   if (obtain (size))
 156     return ptr;
 157   else
 158     return 0;
 159 }
 160
 161 /* Note that SIZE bytes of space have been relinquished by the process.
 162    If SIZE is more than a page, return the space to the system. */
 163
 164 static void
 165 relinquish (size)
 166      SIZE size;
 167 {
 168   POINTER new_page_break;
 169   int excess;
 170
 171   break_value -= size;
 172   new_page_break = (POINTER) ROUNDUP (break_value);
 173   excess = (char *) page_break_value - (char *) new_page_break;
 174
 175   if (excess > extra_bytes * 2)
 176     {
 177       /* Keep extra_bytes worth of empty space.
 178          And don't free anything unless we can free at least extra_bytes.  */
 179       if ((*real_morecore) (extra_bytes - excess) == 0)
 180         abort ();
 181
 182       page_break_value += extra_bytes - excess;
 183     }
 184
 185   /* Zero the space from the end of the "official" break to the actual
 186      break, so that bugs show up faster.  */
 187   bzero (break_value, ((char *) page_break_value - (char *) break_value));
 188 }
 189 \f
 190 /* The meat - allocating, freeing, and relocating blocs.  */
 191
 192 /* These structures are allocated in the malloc arena.
 193    The linked list is kept in order of increasing '.data' members.
 194    The data blocks abut each other; if b->next is non-nil, then
 195    b->data + b->size == b->next->data.  */
 196 typedef struct bp
 197 {
 198   struct bp *next;
 199   struct bp *prev;
 200   POINTER *variable;
 201   POINTER data;
 202   SIZE size;
 203 } *bloc_ptr;
 204
 205 #define NIL_BLOC ((bloc_ptr) 0)
 206 #define BLOC_PTR_SIZE (sizeof (struct bp))
 207
 208 /* Head and tail of the list of relocatable blocs. */
 209 static bloc_ptr first_bloc, last_bloc;
 210
 211 /* Find the bloc referenced by the address in PTR.  Returns a pointer
 212    to that block. */
 213
 214 static bloc_ptr
 215 find_bloc (ptr)
 216      POINTER *ptr;
 217 {
 218   register bloc_ptr p = first_bloc;
 219
 220   while (p != NIL_BLOC)
 221     {
 222       if (p->variable == ptr && p->data == *ptr)
 223         return p;
 224
 225       p = p->next;
 226     }
 227
 228   return p;
 229 }
 230
 231 /* Allocate a bloc of SIZE bytes and append it to the chain of blocs.
 232    Returns a pointer to the new bloc, or zero if we couldn't allocate
 233    memory for the new block.  */
 234
 235 static bloc_ptr
 236 get_bloc (size)
 237      SIZE size;
 238 {
 239   register bloc_ptr new_bloc;
 240
 241   if (! (new_bloc = (bloc_ptr) malloc (BLOC_PTR_SIZE))
 242       || ! (new_bloc->data = get_more_space (size)))
 243     {
 244       if (new_bloc)
 245         free (new_bloc);
 246
 247       return 0;
 248     }
 249
 250   new_bloc->size = size;
 251   new_bloc->next = NIL_BLOC;
 252   new_bloc->variable = (POINTER *) NIL;
 253
 254   if (first_bloc)
 255     {
 256       new_bloc->prev = last_bloc;
 257       last_bloc->next = new_bloc;
 258       last_bloc = new_bloc;
 259     }
 260   else
 261     {
 262       first_bloc = last_bloc = new_bloc;
 263       new_bloc->prev = NIL_BLOC;
 264     }
 265
 266   return new_bloc;
 267 }
 268
 269 /* Relocate all blocs from BLOC on upward in the list to the zone
 270    indicated by ADDRESS.  Direction of relocation is determined by
 271    the position of ADDRESS relative to BLOC->data.
 272
 273    If BLOC is NIL_BLOC, nothing is done.
 274
 275    Note that ordering of blocs is not affected by this function. */
 276
 277 static void
 278 relocate_some_blocs (bloc, address)
 279      bloc_ptr bloc;
 280      POINTER address;
 281 {
 282   if (bloc != NIL_BLOC)
 283     {
 284       register SIZE offset = address - bloc->data;
 285       register SIZE data_size = 0;
 286       register bloc_ptr b;
 287
 288       for (b = bloc; b != NIL_BLOC; b = b->next)
 289         {
 290           data_size += b->size;
 291           b->data += offset;
 292           *b->variable = b->data;
 293         }
 294
 295       safe_bcopy (address - offset, address, data_size);
 296     }
 297 }
 298
 299
 300 /* Free BLOC from the chain of blocs, relocating any blocs above it
 301    and returning BLOC->size bytes to the free area. */
 302
 303 static void
 304 free_bloc (bloc)
 305      bloc_ptr bloc;
 306 {
 307   if (bloc == first_bloc && bloc == last_bloc)
 308     {
 309       first_bloc = last_bloc = NIL_BLOC;
 310     }
 311   else if (bloc == last_bloc)
 312     {
 313       last_bloc = bloc->prev;
 314       last_bloc->next = NIL_BLOC;
 315     }
 316   else if (bloc == first_bloc)
 317     {
 318       first_bloc = bloc->next;
 319       first_bloc->prev = NIL_BLOC;
 320     }
 321   else
 322     {
 323       bloc->next->prev = bloc->prev;
 324       bloc->prev->next = bloc->next;
 325     }
 326
 327   relocate_some_blocs (bloc->next, bloc->data);
 328   relinquish (bloc->size);
 329   free (bloc);
 330 }
 331 \f
 332 /* Interface routines.  */
 333
 334 static int use_relocatable_buffers;
 335
 336 /* Obtain SIZE bytes of storage from the free pool, or the system, as
 337    necessary.  If relocatable blocs are in use, this means relocating
 338    them.  This function gets plugged into the GNU malloc's __morecore
 339    hook.
 340
 341    We provide hysteresis, never relocating by less than extra_bytes.
 342
 343    If we're out of memory, we should return zero, to imitate the other
 344    __morecore hook values - in particular, __default_morecore in the
 345    GNU malloc package.  */
 346
 347 POINTER
 348 r_alloc_sbrk (size)
 349      long size;
 350 {
 351   /* This is the first address not currently available for the heap.  */
 352   POINTER top;
 353   /* Amount of empty space below that.  */
 354   /* It is not correct to use SIZE here, because that is usually unsigned.
 355      ptrdiff_t would be okay, but is not always available.
 356      `long' will work in all cases, in practice.  */
 357   long already_available;
 358   POINTER ptr;
 359
 360   if (! use_relocatable_buffers)
 361     return (*real_morecore) (size);
 362
 363   top = first_bloc ? first_bloc->data : page_break_value;
 364   already_available = (char *) top - (char *) virtual_break_value;
 365
 366   /* Do we not have enough gap already?  */
 367   if (size > 0 && already_available < size)
 368     {
 369       /* Get what we need, plus some extra so we can come here less often.  */
 370       SIZE get = size - already_available + extra_bytes;
 371
 372       if (! obtain (get))
 373         return 0;
 374
 375       if (first_bloc)
 376         relocate_some_blocs (first_bloc, first_bloc->data + get);
 377
 378       /* Zero out the space we just allocated, to help catch bugs
 379          quickly.  */
 380       bzero (virtual_break_value, get);
 381     }
 382   /* Can we keep extra_bytes of gap while freeing at least extra_bytes?  */
 383   else if (size < 0 && already_available - size > 2 * extra_bytes)
 384     {
 385       /* Ok, do so.  This is how many to free.  */
 386       SIZE give_back = already_available - size - extra_bytes;
 387
 388       if (first_bloc)
 389         relocate_some_blocs (first_bloc, first_bloc->data - give_back);
 390       relinquish (give_back);
 391     }
 392
 393   ptr = virtual_break_value;
 394   virtual_break_value += size;
 395
 396   return ptr;
 397 }
 398
 399 /* Allocate a relocatable bloc of storage of size SIZE.  A pointer to
 400    the data is returned in *PTR.  PTR is thus the address of some variable
 401    which will use the data area.
 402
 403    If we can't allocate the necessary memory, set *PTR to zero, and
 404    return zero.  */
 405
 406 POINTER
 407 r_alloc (ptr, size)
 408      POINTER *ptr;
 409      SIZE size;
 410 {
 411   register bloc_ptr new_bloc;
 412
 413   if (! r_alloc_initialized)
 414     r_alloc_init ();
 415
 416   new_bloc = get_bloc (size);
 417   if (new_bloc)
 418     {
 419       new_bloc->variable = ptr;
 420       *ptr = new_bloc->data;
 421     }
 422   else
 423     *ptr = 0;
 424
 425   return *ptr;
 426 }
 427
 428 /* Free a bloc of relocatable storage whose data is pointed to by PTR.
 429    Store 0 in *PTR to show there's no block allocated.  */
 430
 431 void
 432 r_alloc_free (ptr)
 433      register POINTER *ptr;
 434 {
 435   register bloc_ptr dead_bloc;
 436
 437   dead_bloc = find_bloc (ptr);
 438   if (dead_bloc == NIL_BLOC)
 439     abort ();
 440
 441   free_bloc (dead_bloc);
 442   *ptr = 0;
 443 }
 444
 445 /* Given a pointer at address PTR to relocatable data, resize it to SIZE.
 446    Do this by shifting all blocks above this one up in memory, unless
 447    SIZE is less than or equal to the current bloc size, in which case
 448    do nothing.
 449
 450    Change *PTR to reflect the new bloc, and return this value.
 451
 452    If more memory cannot be allocated, then leave *PTR unchanged, and
 453    return zero.  */
 454
 455 POINTER
 456 r_re_alloc (ptr, size)
 457      POINTER *ptr;
 458      SIZE size;
 459 {
 460   register bloc_ptr bloc;
 461
 462   bloc = find_bloc (ptr);
 463   if (bloc == NIL_BLOC)
 464     abort ();
 465
 466   if (size <= bloc->size)
 467     /* Wouldn't it be useful to actually resize the bloc here?  */
 468     return *ptr;
 469
 470   if (! obtain (size - bloc->size))
 471     return 0;
 472
 473   relocate_some_blocs (bloc->next, bloc->data + size);
 474
 475   /* Zero out the new space in the bloc, to help catch bugs faster.  */
 476   bzero (bloc->data + bloc->size, size - bloc->size);
 477
 478   /* Indicate that this block has a new size.  */
 479   bloc->size = size;
 480
 481   return *ptr;
 482 }
 483 \f
 484 /* The hook `malloc' uses for the function which gets more space
 485    from the system.  */
 486 extern POINTER (*__morecore) ();
 487
 488 /* Intialize various things for memory allocation. */
 489
 490 static void
 491 r_alloc_init ()
 492 {
 493   if (r_alloc_initialized)
 494     return;
 495
 496   r_alloc_initialized = 1;
 497   real_morecore = __morecore;
 498   __morecore = r_alloc_sbrk;
 499
 500   virtual_break_value = break_value = (*real_morecore) (0);
 501   if (break_value == NIL)
 502     abort ();
 503
 504   page_size = PAGE;
 505   extra_bytes = ROUNDUP (50000);
 506
 507   page_break_value = (POINTER) ROUNDUP (break_value);
 508   /* Clear the rest of the last page; this memory is in our address space
 509      even though it is after the sbrk value.  */
 510   bzero (break_value, (page_break_value - break_value));
 511   use_relocatable_buffers = 1;
 512 }