src/ralloc.c

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