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 \f
  56 /* Managing "almost out of memory" warnings.  */
  57
  58 /* Level of warnings issued. */
  59 static int warnlevel;
  60
  61 /* Function to call to issue a warning;
  62    0 means don't issue them.  */
  63 static void (*warn_function) ();
  64
  65 static void
  66 check_memory_limits (address)
  67      POINTER address;
  68 {
  69   SIZE data_size = address - data_space_start;
  70
  71   switch (warnlevel)
  72     {
  73     case 0:
  74       if (data_size > (lim_data / 4) * 3)
  75         {
  76           warnlevel++;
  77           (*warn_function) ("Warning: past 75% of memory limit");
  78         }
  79       break;
  80
  81     case 1:
  82       if (data_size > (lim_data / 20) * 17)
  83         {
  84           warnlevel++;
  85           (*warn_function) ("Warning: past 85% of memory limit");
  86         }
  87       break;
  88
  89     case 2:
  90       if (data_size > (lim_data / 20) * 19)
  91         {
  92           warnlevel++;
  93           (*warn_function) ("Warning: past 95% of memory limit");
  94         }
  95       break;
  96
  97     default:
  98       (*warn_function) ("Warning: past acceptable memory limits");
  99       break;
 100     }
 101
 102     if (EXCEEDS_ELISP_PTR (address))
 103       memory_full ();
 104 }
 105 \f
 106 /* Functions to get and return memory from the system.  */
 107
 108 /* Obtain SIZE bytes of space.  If enough space is not presently available
 109    in our process reserve, (i.e., (page_break_value - break_value)),
 110    this means getting more page-aligned space from the system.
 111
 112    Return non-zero if all went well, or zero if we couldn't allocate
 113    the memory.  */
 114 static int
 115 obtain (size)
 116      SIZE size;
 117 {
 118   SIZE already_available = page_break_value - break_value;
 119
 120   if (already_available < size)
 121     {
 122       SIZE get = ROUNDUP (size - already_available);
 123
 124       if (warn_function)
 125         check_memory_limits (page_break_value);
 126
 127       if (((int) sbrk (get)) < 0)
 128         return 0;
 129
 130       page_break_value += get;
 131     }
 132
 133   break_value += size;
 134
 135   return 1;
 136 }
 137
 138 /* Obtain SIZE bytes of space and return a pointer to the new area.
 139    If we could not allocate the space, return zero.  */
 140
 141 static POINTER
 142 get_more_space (size)
 143      SIZE size;
 144 {
 145   POINTER ptr = break_value;
 146   if (obtain (size))
 147     return ptr;
 148   else
 149     return 0;
 150 }
 151
 152 /* Note that SIZE bytes of space have been relinquished by the process.
 153    If SIZE is more than a page, return the space to the system. */
 154
 155 static void
 156 relinquish (size)
 157      SIZE size;
 158 {
 159   POINTER new_page_break;
 160
 161   break_value -= size;
 162   new_page_break = (POINTER) ROUNDUP (break_value);
 163
 164   if (new_page_break != page_break_value)
 165     {
 166       if (((int) (sbrk ((char *) new_page_break
 167                         - (char *) page_break_value))) < 0)
 168         abort ();
 169
 170       page_break_value = new_page_break;
 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 /* Declared in dispnew.c, this version doesn't screw up if regions
 200    overlap.  */
 201 extern void safe_bcopy ();
 202
 203 /* Find the bloc referenced by the address in PTR.  Returns a pointer
 204    to that block. */
 205
 206 static bloc_ptr
 207 find_bloc (ptr)
 208      POINTER *ptr;
 209 {
 210   register bloc_ptr p = first_bloc;
 211
 212   while (p != NIL_BLOC)
 213     {
 214       if (p->variable == ptr && p->data == *ptr)
 215         return p;
 216
 217       p = p->next;
 218     }
 219
 220   return p;
 221 }
 222
 223 /* Allocate a bloc of SIZE bytes and append it to the chain of blocs.
 224    Returns a pointer to the new bloc, or zero if we couldn't allocate
 225    memory for the new block.  */
 226
 227 static bloc_ptr
 228 get_bloc (size)
 229      SIZE size;
 230 {
 231   register bloc_ptr new_bloc;
 232
 233   if (! (new_bloc = (bloc_ptr) malloc (BLOC_PTR_SIZE))
 234       || ! (new_bloc->data = get_more_space (size)))
 235     {
 236       if (new_bloc)
 237         free (new_bloc);
 238
 239       return 0;
 240     }
 241
 242   new_bloc->size = size;
 243   new_bloc->next = NIL_BLOC;
 244   new_bloc->variable = (POINTER *) NIL;
 245
 246   if (first_bloc)
 247     {
 248       new_bloc->prev = last_bloc;
 249       last_bloc->next = new_bloc;
 250       last_bloc = new_bloc;
 251     }
 252   else
 253     {
 254       first_bloc = last_bloc = new_bloc;
 255       new_bloc->prev = NIL_BLOC;
 256     }
 257
 258   return new_bloc;
 259 }
 260
 261 /* Relocate all blocs from BLOC on upward in the list to the zone
 262    indicated by ADDRESS.  Direction of relocation is determined by
 263    the position of ADDRESS relative to BLOC->data.
 264
 265    Note that ordering of blocs is not affected by this function. */
 266
 267 static void
 268 relocate_some_blocs (bloc, address)
 269      bloc_ptr bloc;
 270      POINTER address;
 271 {
 272   register bloc_ptr b;
 273   POINTER data_zone = bloc->data;
 274   register SIZE data_zone_size = 0;
 275   register SIZE offset = bloc->data - address;
 276   POINTER new_data_zone = data_zone - offset;
 277
 278   for (b = bloc; b != NIL_BLOC; b = b->next)
 279     {
 280       data_zone_size += b->size;
 281       b->data -= offset;
 282       *b->variable = b->data;
 283     }
 284
 285   safe_bcopy (data_zone, new_data_zone, data_zone_size);
 286 }
 287
 288 /* Free BLOC from the chain of blocs, relocating any blocs above it
 289    and returning BLOC->size bytes to the free area. */
 290
 291 static void
 292 free_bloc (bloc)
 293      bloc_ptr bloc;
 294 {
 295   if (bloc == first_bloc && bloc == last_bloc)
 296     {
 297       first_bloc = last_bloc = NIL_BLOC;
 298     }
 299   else if (bloc == last_bloc)
 300     {
 301       last_bloc = bloc->prev;
 302       last_bloc->next = NIL_BLOC;
 303     }
 304   else if (bloc == first_bloc)
 305     {
 306       first_bloc = bloc->next;
 307       first_bloc->prev = NIL_BLOC;
 308       relocate_some_blocs (bloc->next, bloc->data);
 309     }
 310   else
 311     {
 312       bloc->next->prev = bloc->prev;
 313       bloc->prev->next = bloc->next;
 314       relocate_some_blocs (bloc->next, bloc->data);
 315     }
 316
 317   relinquish (bloc->size);
 318   free (bloc);
 319 }
 320 \f
 321 /* Interface routines.  */
 322
 323 static int use_relocatable_buffers;
 324
 325 /* Obtain SIZE bytes of storage from the free pool, or the system, as
 326    neccessary.  If relocatable blocs are in use, this means relocating
 327    them.  This function gets plugged into the GNU malloc's __morecore
 328    hook.
 329
 330    If we're out of memory, we should return zero, to imitate the other
 331    __morecore hook values - in particular, __default_morecore in the
 332    GNU malloc package.  */
 333
 334 POINTER
 335 r_alloc_sbrk (size)
 336      long size;
 337 {
 338   POINTER ptr;
 339
 340   if (! use_relocatable_buffers)
 341     return sbrk (size);
 342
 343   if (size > 0)
 344     {
 345       if (! obtain (size))
 346         return 0;
 347
 348       if (first_bloc)
 349         {
 350           relocate_some_blocs (first_bloc, first_bloc->data + size);
 351
 352           /* Zero out the space we just allocated, to help catch bugs
 353              quickly.  */
 354           bzero (virtual_break_value, size);
 355         }
 356     }
 357   else if (size < 0)
 358     {
 359       if (first_bloc)
 360         relocate_some_blocs (first_bloc, first_bloc->data + size);
 361       relinquish (- size);
 362     }
 363
 364   ptr = virtual_break_value;
 365   virtual_break_value += size;
 366   return ptr;
 367 }
 368
 369 /* Allocate a relocatable bloc of storage of size SIZE.  A pointer to
 370    the data is returned in *PTR.  PTR is thus the address of some variable
 371    which will use the data area.
 372
 373    If we can't allocate the necessary memory, set *PTR to zero, and
 374    return zero.  */
 375
 376 POINTER
 377 r_alloc (ptr, size)
 378      POINTER *ptr;
 379      SIZE size;
 380 {
 381   register bloc_ptr new_bloc;
 382
 383   new_bloc = get_bloc (size);
 384   if (new_bloc)
 385     {
 386       new_bloc->variable = ptr;
 387       *ptr = new_bloc->data;
 388     }
 389   else
 390     *ptr = 0;
 391
 392   return *ptr;
 393 }
 394
 395 /* Free a bloc of relocatable storage whose data is pointed to by PTR. */
 396
 397 void
 398 r_alloc_free (ptr)
 399      register POINTER *ptr;
 400 {
 401   register bloc_ptr dead_bloc;
 402
 403   dead_bloc = find_bloc (ptr);
 404   if (dead_bloc == NIL_BLOC)
 405     abort ();
 406
 407   free_bloc (dead_bloc);
 408 }
 409
 410 /* Given a pointer at address PTR to relocatable data, resize it to SIZE.
 411    Do this by shifting all blocks above this one up in memory, unless
 412    SIZE is less than or equal to the current bloc size, in which case
 413    do nothing.
 414
 415    Change *PTR to reflect the new bloc, and return this value.
 416
 417    If more memory cannot be allocated, then leave *PTR unchanged, and
 418    return zero.  */
 419
 420 POINTER
 421 r_re_alloc (ptr, size)
 422      POINTER *ptr;
 423      SIZE size;
 424 {
 425   register bloc_ptr bloc;
 426
 427   bloc = find_bloc (ptr);
 428   if (bloc == NIL_BLOC)
 429     abort ();
 430
 431   if (size <= bloc->size)
 432     /* Wouldn't it be useful to actually resize the bloc here?  */
 433     return *ptr;
 434
 435   if (! obtain (size - bloc->size))
 436     return 0;
 437
 438   relocate_some_blocs (bloc->next, bloc->data + size);
 439
 440   /* Zero out the new space in the bloc, to help catch bugs faster.  */
 441   bzero (bloc->data + bloc->size, size - bloc->size);
 442
 443   /* Indicate that this block has a new size.  */
 444   bloc->size = size;
 445
 446   return *ptr;
 447 }
 448 \f
 449 /* The hook `malloc' uses for the function which gets more space
 450    from the system.  */
 451 extern POINTER (*__morecore) ();
 452
 453 /* A flag to indicate whether we have initialized ralloc yet.  For
 454    Emacs's sake, please do not make this local to malloc_init; on some
 455    machines, the dumping procedure makes all static variables
 456    read-only.  On these machines, the word static is #defined to be
 457    the empty string, meaning that malloc_initialized becomes an
 458    automatic variable, and loses its value each time Emacs is started
 459    up.  */
 460 static int malloc_initialized = 0;
 461
 462 /* Intialize various things for memory allocation. */
 463
 464 void
 465 malloc_init (start, warn_func)
 466      POINTER start;
 467      void (*warn_func) ();
 468 {
 469   if (start)
 470     data_space_start = start;
 471
 472   if (malloc_initialized)
 473     return;
 474
 475   malloc_initialized = 1;
 476   __morecore = r_alloc_sbrk;
 477
 478   virtual_break_value = break_value = sbrk (0);
 479   if (break_value == (POINTER)NULL)
 480     (*warn_func)("Malloc initialization returned 0 from sbrk(0).");
 481
 482   page_break_value = (POINTER) ROUNDUP (break_value);
 483   bzero (break_value, (page_break_value - break_value));
 484   use_relocatable_buffers = 1;
 485
 486   lim_data = 0;
 487   warnlevel = 0;
 488   warn_function = warn_func;
 489
 490   get_lim_data ();
 491 }