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 necessary 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 long int) (addr) & (page_size - 1)) == 0)
 113 #define ROUNDUP(size) (((unsigned long int) (size) + page_size - 1) \
 114                        & ~(page_size - 1))
 115 #define ROUND_TO_PAGE(addr) (addr & (~(page_size - 1)))
 116 \f
 117 /* Functions to get and return memory from the system.  */
 118
 119 /* Obtain SIZE bytes of space.  If enough space is not presently available
 120    in our process reserve, (i.e., (page_break_value - break_value)),
 121    this means getting more page-aligned space from the system.
 122
 123    Return non-zero if all went well, or zero if we couldn't allocate
 124    the memory.  */
 125 static int
 126 obtain (size)
 127      SIZE size;
 128 {
 129   SIZE already_available = page_break_value - break_value;
 130
 131   if (already_available < size)
 132     {
 133       SIZE get = ROUNDUP (size - already_available);
 134       /* Get some extra, so we can come here less often.  */
 135       get += extra_bytes;
 136
 137       if ((*real_morecore) (get) == 0)
 138         return 0;
 139
 140       page_break_value += get;
 141     }
 142
 143   break_value += size;
 144
 145   return 1;
 146 }
 147
 148 /* Obtain SIZE bytes of space and return a pointer to the new area.
 149    If we could not allocate the space, return zero.  */
 150
 151 static POINTER
 152 get_more_space (size)
 153      SIZE size;
 154 {
 155   POINTER ptr = break_value;
 156   if (obtain (size))
 157     return ptr;
 158   else
 159     return 0;
 160 }
 161
 162 /* Note that SIZE bytes of space have been relinquished by the process.
 163    If SIZE is more than a page, return the space to the system. */
 164
 165 static void
 166 relinquish (size)
 167      SIZE size;
 168 {
 169   POINTER new_page_break;
 170   int excess;
 171
 172   break_value -= size;
 173   new_page_break = (POINTER) ROUNDUP (break_value);
 174   excess = (char *) page_break_value - (char *) new_page_break;
 175
 176   if (excess > extra_bytes * 2)
 177     {
 178       /* Keep extra_bytes worth of empty space.
 179          And don't free anything unless we can free at least extra_bytes.  */
 180       if ((*real_morecore) (extra_bytes - excess) == 0)
 181         abort ();
 182
 183       page_break_value += extra_bytes - excess;
 184     }
 185
 186   /* Zero the space from the end of the "official" break to the actual
 187      break, so that bugs show up faster.  */
 188   bzero (break_value, ((char *) page_break_value - (char *) break_value));
 189 }
 190 \f
 191 /* The meat - allocating, freeing, and relocating blocs.  */
 192
 193 /* These structures are allocated in the malloc arena.
 194    The linked list is kept in order of increasing '.data' members.
 195    The data blocks abut each other; if b->next is non-nil, then
 196    b->data + b->size == b->next->data.  */
 197 typedef struct bp
 198 {
 199   struct bp *next;
 200   struct bp *prev;
 201   POINTER *variable;
 202   POINTER data;
 203   SIZE size;
 204 } *bloc_ptr;
 205
 206 #define NIL_BLOC ((bloc_ptr) 0)
 207 #define BLOC_PTR_SIZE (sizeof (struct bp))
 208
 209 /* Head and tail of the list of relocatable blocs. */
 210 static bloc_ptr first_bloc, last_bloc;
 211
 212 /* Find the bloc referenced by the address in PTR.  Returns a pointer
 213    to that block. */
 214
 215 static bloc_ptr
 216 find_bloc (ptr)
 217      POINTER *ptr;
 218 {
 219   register bloc_ptr p = first_bloc;
 220
 221   while (p != NIL_BLOC)
 222     {
 223       if (p->variable == ptr && p->data == *ptr)
 224         return p;
 225
 226       p = p->next;
 227     }
 228
 229   return p;
 230 }
 231
 232 /* Allocate a bloc of SIZE bytes and append it to the chain of blocs.
 233    Returns a pointer to the new bloc, or zero if we couldn't allocate
 234    memory for the new block.  */
 235
 236 static bloc_ptr
 237 get_bloc (size)
 238      SIZE size;
 239 {
 240   register bloc_ptr new_bloc;
 241
 242   if (! (new_bloc = (bloc_ptr) malloc (BLOC_PTR_SIZE))
 243       || ! (new_bloc->data = get_more_space (size)))
 244     {
 245       if (new_bloc)
 246         free (new_bloc);
 247
 248       return 0;
 249     }
 250
 251   new_bloc->size = size;
 252   new_bloc->next = NIL_BLOC;
 253   new_bloc->variable = (POINTER *) NIL;
 254
 255   if (first_bloc)
 256     {
 257       new_bloc->prev = last_bloc;
 258       last_bloc->next = new_bloc;
 259       last_bloc = new_bloc;
 260     }
 261   else
 262     {
 263       first_bloc = last_bloc = new_bloc;
 264       new_bloc->prev = NIL_BLOC;
 265     }
 266
 267   return new_bloc;
 268 }
 269
 270 /* Relocate all blocs from BLOC on upward in the list to the zone
 271    indicated by ADDRESS.  Direction of relocation is determined by
 272    the position of ADDRESS relative to BLOC->data.
 273
 274    If BLOC is NIL_BLOC, nothing is done.
 275
 276    Note that ordering of blocs is not affected by this function. */
 277
 278 static void
 279 relocate_some_blocs (bloc, address)
 280      bloc_ptr bloc;
 281      POINTER address;
 282 {
 283   if (bloc != NIL_BLOC)
 284     {
 285       register SIZE offset = address - bloc->data;
 286       register SIZE data_size = 0;
 287       register bloc_ptr b;
 288
 289       for (b = bloc; b != NIL_BLOC; b = b->next)
 290         {
 291           data_size += b->size;
 292           b->data += offset;
 293           *b->variable = b->data;
 294         }
 295
 296       safe_bcopy (address - offset, address, data_size);
 297     }
 298 }
 299
 300
 301 /* Free BLOC from the chain of blocs, relocating any blocs above it
 302    and returning BLOC->size bytes to the free area. */
 303
 304 static void
 305 free_bloc (bloc)
 306      bloc_ptr bloc;
 307 {
 308   if (bloc == first_bloc && bloc == last_bloc)
 309     {
 310       first_bloc = last_bloc = NIL_BLOC;
 311     }
 312   else if (bloc == last_bloc)
 313     {
 314       last_bloc = bloc->prev;
 315       last_bloc->next = NIL_BLOC;
 316     }
 317   else if (bloc == first_bloc)
 318     {
 319       first_bloc = bloc->next;
 320       first_bloc->prev = NIL_BLOC;
 321     }
 322   else
 323     {
 324       bloc->next->prev = bloc->prev;
 325       bloc->prev->next = bloc->next;
 326     }
 327
 328   relocate_some_blocs (bloc->next, bloc->data);
 329   relinquish (bloc->size);
 330   free (bloc);
 331 }
 332 \f
 333 /* Interface routines.  */
 334
 335 static int use_relocatable_buffers;
 336
 337 /* Obtain SIZE bytes of storage from the free pool, or the system, as
 338    necessary.  If relocatable blocs are in use, this means relocating
 339    them.  This function gets plugged into the GNU malloc's __morecore
 340    hook.
 341
 342    We provide hysteresis, never relocating by less than extra_bytes.
 343
 344    If we're out of memory, we should return zero, to imitate the other
 345    __morecore hook values - in particular, __default_morecore in the
 346    GNU malloc package.  */
 347
 348 POINTER
 349 r_alloc_sbrk (size)
 350      long size;
 351 {
 352   /* This is the first address not currently available for the heap.  */
 353   POINTER top;
 354   /* Amount of empty space below that.  */
 355   /* It is not correct to use SIZE here, because that is usually unsigned.
 356      ptrdiff_t would be okay, but is not always available.
 357      `long' will work in all cases, in practice.  */
 358   long already_available;
 359   POINTER ptr;
 360
 361   if (! use_relocatable_buffers)
 362     return (*real_morecore) (size);
 363
 364   top = first_bloc ? first_bloc->data : page_break_value;
 365   already_available = (char *) top - (char *) virtual_break_value;
 366
 367   /* Do we not have enough gap already?  */
 368   if (size > 0 && already_available < size)
 369     {
 370       /* Get what we need, plus some extra so we can come here less often.  */
 371       SIZE get = size - already_available + extra_bytes;
 372
 373       if (! obtain (get))
 374         return 0;
 375
 376       if (first_bloc)
 377         relocate_some_blocs (first_bloc, first_bloc->data + get);
 378
 379       /* Zero out the space we just allocated, to help catch bugs
 380          quickly.  */
 381       bzero (virtual_break_value, get);
 382     }
 383   /* Can we keep extra_bytes of gap while freeing at least extra_bytes?  */
 384   else if (size < 0 && already_available - size > 2 * extra_bytes)
 385     {
 386       /* Ok, do so.  This is how many to free.  */
 387       SIZE give_back = already_available - size - extra_bytes;
 388
 389       if (first_bloc)
 390         relocate_some_blocs (first_bloc, first_bloc->data - give_back);
 391       relinquish (give_back);
 392     }
 393
 394   ptr = virtual_break_value;
 395   virtual_break_value += size;
 396
 397   return ptr;
 398 }
 399
 400 /* Allocate a relocatable bloc of storage of size SIZE.  A pointer to
 401    the data is returned in *PTR.  PTR is thus the address of some variable
 402    which will use the data area.
 403
 404    If we can't allocate the necessary memory, set *PTR to zero, and
 405    return zero.  */
 406
 407 POINTER
 408 r_alloc (ptr, size)
 409      POINTER *ptr;
 410      SIZE size;
 411 {
 412   register bloc_ptr new_bloc;
 413
 414   if (! r_alloc_initialized)
 415     r_alloc_init ();
 416
 417   new_bloc = get_bloc (size);
 418   if (new_bloc)
 419     {
 420       new_bloc->variable = ptr;
 421       *ptr = new_bloc->data;
 422     }
 423   else
 424     *ptr = 0;
 425
 426   return *ptr;
 427 }
 428
 429 /* Free a bloc of relocatable storage whose data is pointed to by PTR.
 430    Store 0 in *PTR to show there's no block allocated.  */
 431
 432 void
 433 r_alloc_free (ptr)
 434      register POINTER *ptr;
 435 {
 436   register bloc_ptr dead_bloc;
 437
 438   dead_bloc = find_bloc (ptr);
 439   if (dead_bloc == NIL_BLOC)
 440     abort ();
 441
 442   free_bloc (dead_bloc);
 443   *ptr = 0;
 444 }
 445
 446 /* Given a pointer at address PTR to relocatable data, resize it to SIZE.
 447    Do this by shifting all blocks above this one up in memory, unless
 448    SIZE is less than or equal to the current bloc size, in which case
 449    do nothing.
 450
 451    Change *PTR to reflect the new bloc, and return this value.
 452
 453    If more memory cannot be allocated, then leave *PTR unchanged, and
 454    return zero.  */
 455
 456 POINTER
 457 r_re_alloc (ptr, size)
 458      POINTER *ptr;
 459      SIZE size;
 460 {
 461   register bloc_ptr bloc;
 462
 463   bloc = find_bloc (ptr);
 464   if (bloc == NIL_BLOC)
 465     abort ();
 466
 467   if (size <= bloc->size)
 468     /* Wouldn't it be useful to actually resize the bloc here?  */
 469     return *ptr;
 470
 471   if (! obtain (size - bloc->size))
 472     return 0;
 473
 474   relocate_some_blocs (bloc->next, bloc->data + size);
 475
 476   /* Zero out the new space in the bloc, to help catch bugs faster.  */
 477   bzero (bloc->data + bloc->size, size - bloc->size);
 478
 479   /* Indicate that this block has a new size.  */
 480   bloc->size = size;
 481
 482   return *ptr;
 483 }
 484 \f
 485 /* The hook `malloc' uses for the function which gets more space
 486    from the system.  */
 487 extern POINTER (*__morecore) ();
 488
 489 /* Initialize various things for memory allocation. */
 490
 491 static void
 492 r_alloc_init ()
 493 {
 494   if (r_alloc_initialized)
 495     return;
 496
 497   r_alloc_initialized = 1;
 498   real_morecore = __morecore;
 499   __morecore = r_alloc_sbrk;
 500
 501   virtual_break_value = break_value = (*real_morecore) (0);
 502   if (break_value == NIL)
 503     abort ();
 504
 505   page_size = PAGE;
 506   extra_bytes = ROUNDUP (50000);
 507
 508   page_break_value = (POINTER) ROUNDUP (break_value);
 509   /* Clear the rest of the last page; this memory is in our address space
 510      even though it is after the sbrk value.  */
 511   bzero (break_value, (page_break_value - break_value));
 512   use_relocatable_buffers = 1;
 513 }