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