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