boehm-gc/allchblk.c

   1 /*
   2  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
   3  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
   4  * Copyright (c) 1998 by Silicon Graphics.  All rights reserved.
   5  *
   6  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   7  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   8  *
   9  * Permission is hereby granted to use or copy this program
  10  * for any purpose,  provided the above notices are retained on all copies.
  11  * Permission to modify the code and to distribute modified code is granted,
  12  * provided the above notices are retained, and a notice that the code was
  13  * modified is included with the above copyright notice.
  14  */
  15 /* Boehm, August 9, 1995 5:08 pm PDT */
  16
  17 #define DEBUG
  18 #undef DEBUG
  19 #include <stdio.h>
  20 #include "gc_priv.h"
  21
  22
  23 /*
  24  * allocate/free routines for heap blocks
  25  * Note that everything called from outside the garbage collector
  26  * should be prepared to abort at any point as the result of a signal.
  27  */
  28
  29 /*
  30  * Free heap blocks are kept on a list sorted by address.
  31  * The hb_hdr.hbh_sz field of a free heap block contains the length
  32  * (in bytes) of the entire block.
  33  * Neighbors are coalesced.
  34  */
  35
  36 # define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE)
  37                 /* largest block we will allocate starting on a black   */
  38                 /* listed block.  Must be >= HBLKSIZE.                  */
  39
  40 struct hblk * GC_hblkfreelist = 0;
  41
  42 struct hblk *GC_savhbp = (struct hblk *)0;  /* heap block preceding next */
  43                                          /* block to be examined by   */
  44                                          /* GC_allochblk.                */
  45
  46 # if !defined(NO_DEBUGGING)
  47 void GC_print_hblkfreelist()
  48 {
  49     struct hblk * h = GC_hblkfreelist;
  50     word total_free = 0;
  51     hdr * hhdr = HDR(h);
  52     word sz;
  53
  54     while (h != 0) {
  55         sz = hhdr -> hb_sz;
  56         GC_printf2("0x%lx size %lu ", (unsigned long)h, (unsigned long)sz);
  57         total_free += sz;
  58         if (GC_is_black_listed(h, HBLKSIZE) != 0) {
  59              GC_printf0("start black listed\n");
  60         } else if (GC_is_black_listed(h, hhdr -> hb_sz) != 0) {
  61              GC_printf0("partially black listed\n");
  62         } else {
  63              GC_printf0("not black listed\n");
  64         }
  65         h = hhdr -> hb_next;
  66         hhdr = HDR(h);
  67     }
  68     GC_printf1("Total of %lu bytes on free list\n", (unsigned long)total_free);
  69 }
  70
  71 # endif /* NO_DEBUGGING */
  72
  73 /* Initialize hdr for a block containing the indicated size and         */
  74 /* kind of objects.                                                     */
  75 /* Return FALSE on failure.                                             */
  76 static GC_bool setup_header(hhdr, sz, kind, flags)
  77 register hdr * hhdr;
  78 word sz;        /* object size in words */
  79 int kind;
  80 unsigned char flags;
  81 {
  82     register word descr;
  83
  84     /* Add description of valid object pointers */
  85       if (!GC_add_map_entry(sz)) return(FALSE);
  86       hhdr -> hb_map = GC_obj_map[sz > MAXOBJSZ? 0 : sz];
  87
  88     /* Set size, kind and mark proc fields */
  89       hhdr -> hb_sz = sz;
  90       hhdr -> hb_obj_kind = kind;
  91       hhdr -> hb_flags = flags;
  92       descr = GC_obj_kinds[kind].ok_descriptor;
  93       if (GC_obj_kinds[kind].ok_relocate_descr) descr += WORDS_TO_BYTES(sz);
  94       hhdr -> hb_descr = descr;
  95
  96     /* Clear mark bits */
  97       GC_clear_hdr_marks(hhdr);
  98
  99     hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
 100     return(TRUE);
 101 }
 102
 103 #ifdef EXACT_FIRST
 104 #   define LAST_TRIP 2
 105 #else
 106 #   define LAST_TRIP 1
 107 #endif
 108
 109 /*
 110  * Allocate (and return pointer to) a heap block
 111  *   for objects of size sz words.
 112  *
 113  * NOTE: We set obj_map field in header correctly.
 114  *       Caller is resposnsible for building an object freelist in block.
 115  *
 116  * We clear the block if it is destined for large objects, and if
 117  * kind requires that newly allocated objects be cleared.
 118  */
 119 struct hblk *
 120 GC_allochblk(sz, kind, flags)
 121 word sz;
 122 int kind;
 123 unsigned char flags;  /* IGNORE_OFF_PAGE or 0 */
 124 {
 125     register struct hblk *thishbp;
 126     register hdr * thishdr;             /* Header corr. to thishbp */
 127     register struct hblk *hbp;
 128     register hdr * hhdr;                /* Header corr. to hbp */
 129     struct hblk *prevhbp;
 130     register hdr * phdr;                /* Header corr. to prevhbp */
 131     signed_word size_needed;    /* number of bytes in requested objects */
 132     signed_word size_avail;     /* bytes available in this block        */
 133     int trip_count = 0;
 134
 135     size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS(sz);
 136
 137     /* search for a big enough block in free list */
 138         hbp = GC_savhbp;
 139         hhdr = HDR(hbp);
 140         for(;;) {
 141
 142             prevhbp = hbp;
 143             phdr = hhdr;
 144             hbp = (prevhbp == 0? GC_hblkfreelist : phdr->hb_next);
 145             hhdr = HDR(hbp);
 146
 147             if( prevhbp == GC_savhbp) {
 148                 if (trip_count == LAST_TRIP) return(0);
 149                 ++trip_count;
 150             }
 151
 152             if( hbp == 0 ) continue;
 153
 154             size_avail = hhdr->hb_sz;
 155 #           ifdef EXACT_FIRST
 156                 if (trip_count <= 1 && size_avail != size_needed) continue;
 157 #           endif
 158             if (size_avail < size_needed) continue;
 159 #           ifdef PRESERVE_LAST
 160                 if (size_avail != size_needed
 161                     && !GC_incremental
 162                     && GC_in_last_heap_sect(hbp) && GC_should_collect()) {
 163                     continue;
 164                 }
 165 #           endif
 166             /* If the next heap block is obviously better, go on.       */
 167             /* This prevents us from disassembling a single large block */
 168             /* to get tiny blocks.                                      */
 169             {
 170               signed_word next_size;
 171
 172               thishbp = hhdr -> hb_next;
 173               if (thishbp == 0) thishbp = GC_hblkfreelist;
 174               thishdr = HDR(thishbp);
 175               next_size = (signed_word)(thishdr -> hb_sz);
 176               if (next_size < size_avail
 177                   && next_size >= size_needed
 178                   && !GC_is_black_listed(thishbp, (word)size_needed)) {
 179                   continue;
 180               }
 181             }
 182             if ( !IS_UNCOLLECTABLE(kind) &&
 183                  (kind != PTRFREE || size_needed > MAX_BLACK_LIST_ALLOC)) {
 184               struct hblk * lasthbp = hbp;
 185               ptr_t search_end = (ptr_t)hbp + size_avail - size_needed;
 186               signed_word orig_avail = size_avail;
 187               signed_word eff_size_needed = ((flags & IGNORE_OFF_PAGE)?
 188                                                 HBLKSIZE
 189                                                 : size_needed);
 190
 191
 192               while ((ptr_t)lasthbp <= search_end
 193                      && (thishbp = GC_is_black_listed(lasthbp,
 194                                                       (word)eff_size_needed))) {
 195                 lasthbp = thishbp;
 196               }
 197               size_avail -= (ptr_t)lasthbp - (ptr_t)hbp;
 198               thishbp = lasthbp;
 199               if (size_avail >= size_needed) {
 200                 if (thishbp != hbp && GC_install_header(thishbp)) {
 201                   /* Split the block at thishbp */
 202                       thishdr = HDR(thishbp);
 203                       /* GC_invalidate_map not needed, since we will    */
 204                       /* allocate this block.                           */
 205                       thishdr -> hb_next = hhdr -> hb_next;
 206                       thishdr -> hb_sz = size_avail;
 207                       hhdr -> hb_sz = (ptr_t)thishbp - (ptr_t)hbp;
 208                       hhdr -> hb_next = thishbp;
 209                   /* Advance to thishbp */
 210                       prevhbp = hbp;
 211                       phdr = hhdr;
 212                       hbp = thishbp;
 213                       hhdr = thishdr;
 214                 }
 215               } else if (size_needed > (signed_word)BL_LIMIT
 216                          && orig_avail - size_needed
 217                             > (signed_word)BL_LIMIT) {
 218                 /* Punt, since anything else risks unreasonable heap growth. */
 219                 WARN("Needed to allocate blacklisted block at 0x%lx\n",
 220                      (word)hbp);
 221                 thishbp = hbp;
 222                 size_avail = orig_avail;
 223               } else if (size_avail == 0
 224                          && size_needed == HBLKSIZE
 225                          && prevhbp != 0) {
 226 #               ifndef FIND_LEAK
 227                   static unsigned count = 0;
 228
 229                   /* The block is completely blacklisted.  We need      */
 230                   /* to drop some such blocks, since otherwise we spend */
 231                   /* all our time traversing them if pointerfree        */
 232                   /* blocks are unpopular.                              */
 233                   /* A dropped block will be reconsidered at next GC.   */
 234                   if ((++count & 3) == 0) {
 235                     /* Allocate and drop the block in small chunks, to  */
 236                     /* maximize the chance that we will recover some    */
 237                     /* later.                                           */
 238                       struct hblk * limit = hbp + (hhdr->hb_sz/HBLKSIZE);
 239                       struct hblk * h;
 240
 241                       GC_words_wasted += hhdr->hb_sz;
 242                       phdr -> hb_next = hhdr -> hb_next;
 243                       for (h = hbp; h < limit; h++) {
 244                         if (h == hbp || GC_install_header(h)) {
 245                           hhdr = HDR(h);
 246                           (void) setup_header(
 247                                   hhdr,
 248                                   BYTES_TO_WORDS(HBLKSIZE - HDR_BYTES),
 249                                   PTRFREE, 0); /* Cant fail */
 250                           if (GC_debugging_started) {
 251                             BZERO(hbp + HDR_BYTES, HBLKSIZE - HDR_BYTES);
 252                           }
 253                         }
 254                       }
 255                     /* Restore hbp to point at free block */
 256                       if (GC_savhbp == hbp) GC_savhbp = prevhbp;
 257                       hbp = prevhbp;
 258                       hhdr = phdr;
 259                       if (hbp == GC_savhbp) --trip_count;
 260                   }
 261 #               endif
 262               }
 263             }
 264             if( size_avail >= size_needed ) {
 265                 /* found a big enough block       */
 266                 /* let thishbp --> the block      */
 267                 /* set prevhbp, hbp to bracket it */
 268                     thishbp = hbp;
 269                     thishdr = hhdr;
 270                     if( size_avail == size_needed ) {
 271                         hbp = hhdr->hb_next;
 272                         hhdr = HDR(hbp);
 273                     } else {
 274                         hbp = (struct hblk *)
 275                             (((word)thishbp) + size_needed);
 276                         if (!GC_install_header(hbp)) {
 277                             hbp = thishbp;
 278                             continue;
 279                         }
 280                         hhdr = HDR(hbp);
 281                         GC_invalidate_map(hhdr);
 282                         hhdr->hb_next = thishdr->hb_next;
 283                         hhdr->hb_sz = size_avail - size_needed;
 284                     }
 285                 /* remove *thishbp from hblk freelist */
 286                     if( prevhbp == 0 ) {
 287                         GC_hblkfreelist = hbp;
 288                     } else {
 289                         phdr->hb_next = hbp;
 290                     }
 291                 /* save current list search position */
 292                     GC_savhbp = hbp;
 293                 break;
 294             }
 295         }
 296
 297     /* Notify virtual dirty bit implementation that we are about to write. */
 298         GC_write_hint(thishbp);
 299
 300     /* Add it to map of valid blocks */
 301         if (!GC_install_counts(thishbp, (word)size_needed)) return(0);
 302         /* This leaks memory under very rare conditions. */
 303
 304     /* Set up header */
 305         if (!setup_header(thishdr, sz, kind, flags)) {
 306             GC_remove_counts(thishbp, (word)size_needed);
 307             return(0); /* ditto */
 308         }
 309
 310     /* Clear block if necessary */
 311         if (GC_debugging_started
 312             || sz > MAXOBJSZ && GC_obj_kinds[kind].ok_init) {
 313             BZERO(thishbp + HDR_BYTES,  size_needed - HDR_BYTES);
 314         }
 315
 316     /* We just successfully allocated a block.  Restart count of        */
 317     /* consecutive failures.                                            */
 318     {
 319         extern unsigned GC_fail_count;
 320
 321         GC_fail_count = 0;
 322     }
 323
 324     return( thishbp );
 325 }
 326
 327 struct hblk * GC_freehblk_ptr = 0;  /* Search position hint for GC_freehblk */
 328
 329 /*
 330  * Free a heap block.
 331  *
 332  * Coalesce the block with its neighbors if possible.
 333  *
 334  * All mark words are assumed to be cleared.
 335  */
 336 void
 337 GC_freehblk(p)
 338 register struct hblk *p;
 339 {
 340 register hdr *phdr;     /* Header corresponding to p */
 341 register struct hblk *hbp, *prevhbp;
 342 register hdr *hhdr, *prevhdr;
 343 register signed_word size;
 344
 345     /* GC_savhbp may become invalid due to coalescing.  Clear it. */
 346         GC_savhbp = (struct hblk *)0;
 347
 348     phdr = HDR(p);
 349     size = phdr->hb_sz;
 350     size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(size);
 351     GC_remove_counts(p, (word)size);
 352     phdr->hb_sz = size;
 353     GC_invalidate_map(phdr);
 354     prevhbp = 0;
 355
 356     /* The following optimization was suggested by David Detlefs.       */
 357     /* Note that the header cannot be NIL, since there cannot be an     */
 358     /* intervening  call to GC_freehblk without resetting               */
 359     /* GC_freehblk_ptr.                                                 */
 360     if (GC_freehblk_ptr != 0 &&
 361         HDR(GC_freehblk_ptr)->hb_map == GC_invalid_map &&
 362         (ptr_t)GC_freehblk_ptr < (ptr_t)p) {
 363       hbp = GC_freehblk_ptr;
 364     } else {
 365       hbp = GC_hblkfreelist;
 366     };
 367     hhdr = HDR(hbp);
 368
 369     while( (hbp != 0) && (hbp < p) ) {
 370         prevhbp = hbp;
 371         prevhdr = hhdr;
 372         hbp = hhdr->hb_next;
 373         hhdr = HDR(hbp);
 374     }
 375     GC_freehblk_ptr = prevhbp;
 376
 377     /* Check for duplicate deallocation in the easy case */
 378       if (hbp != 0 && (ptr_t)p + size > (ptr_t)hbp
 379         || prevhbp != 0 && (ptr_t)prevhbp + prevhdr->hb_sz > (ptr_t)p) {
 380         GC_printf1("Duplicate large block deallocation of 0x%lx\n",
 381                    (unsigned long) p);
 382         GC_printf2("Surrounding free blocks are 0x%lx and 0x%lx\n",
 383                    (unsigned long) prevhbp, (unsigned long) hbp);
 384       }
 385
 386     /* Coalesce with successor, if possible */
 387       if( (((word)p)+size) == ((word)hbp) ) {
 388         phdr->hb_next = hhdr->hb_next;
 389         phdr->hb_sz += hhdr->hb_sz;
 390         GC_remove_header(hbp);
 391       } else {
 392         phdr->hb_next = hbp;
 393       }
 394
 395
 396     if( prevhbp == 0 ) {
 397         GC_hblkfreelist = p;
 398     } else if( (((word)prevhbp) + prevhdr->hb_sz)
 399                == ((word)p) ) {
 400       /* Coalesce with predecessor */
 401         prevhdr->hb_next = phdr->hb_next;
 402         prevhdr->hb_sz += phdr->hb_sz;
 403         GC_remove_header(p);
 404     } else {
 405         prevhdr->hb_next = p;
 406     }
 407 }
 408