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