src/mm/boehm-gc/typd_mlc.c

   1 /*
   2  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
   3  * opyright (c) 1999-2000 by Hewlett-Packard Company.  All rights reserved.
   4  *
   5  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   6  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   7  *
   8  * Permission is hereby granted to use or copy this program
   9  * for any purpose,  provided the above notices are retained on all copies.
  10  * Permission to modify the code and to distribute modified code is granted,
  11  * provided the above notices are retained, and a notice that the code was
  12  * modified is included with the above copyright notice.
  13  *
  14  */
  15
  16
  17 /*
  18  * Some simple primitives for allocation with explicit type information.
  19  * Simple objects are allocated such that they contain a GC_descr at the
  20  * end (in the last allocated word).  This descriptor may be a procedure
  21  * which then examines an extended descriptor passed as its environment.
  22  *
  23  * Arrays are treated as simple objects if they have sufficiently simple
  24  * structure.  Otherwise they are allocated from an array kind that supplies
  25  * a special mark procedure.  These arrays contain a pointer to a
  26  * complex_descriptor as their last word.
  27  * This is done because the environment field is too small, and the collector
  28  * must trace the complex_descriptor.
  29  *
  30  * Note that descriptors inside objects may appear cleared, if we encounter a
  31  * false refrence to an object on a free list.  In the GC_descr case, this
  32  * is OK, since a 0 descriptor corresponds to examining no fields.
  33  * In the complex_descriptor case, we explicitly check for that case.
  34  *
  35  * MAJOR PARTS OF THIS CODE HAVE NOT BEEN TESTED AT ALL and are not testable,
  36  * since they are not accessible through the current interface.
  37  */
  38
  39 #include "config.h"
  40
  41 #include "private/gc_pmark.h"
  42 #include "gc_typed.h"
  43
  44 # define TYPD_EXTRA_BYTES (sizeof(word) - EXTRA_BYTES)
  45
  46 GC_bool GC_explicit_typing_initialized = FALSE;
  47
  48 int GC_explicit_kind;   /* Object kind for objects with indirect        */
  49                         /* (possibly extended) descriptors.             */
  50
  51 int GC_array_kind;      /* Object kind for objects with complex         */
  52                         /* descriptors and GC_array_mark_proc.          */
  53
  54 /* Extended descriptors.  GC_typed_mark_proc understands these. */
  55 /* These are used for simple objects that are larger than what  */
  56 /* can be described by a BITMAP_BITS sized bitmap.              */
  57 typedef struct {
  58         word ed_bitmap; /* lsb corresponds to first word.       */
  59         GC_bool ed_continued;   /* next entry is continuation.  */
  60 } ext_descr;
  61
  62 /* Array descriptors.  GC_array_mark_proc understands these.    */
  63 /* We may eventually need to add provisions for headers and     */
  64 /* trailers.  Hence we provide for tree structured descriptors, */
  65 /* though we don't really use them currently.                   */
  66 typedef union ComplexDescriptor {
  67     struct LeafDescriptor {     /* Describes simple array       */
  68         word ld_tag;
  69 #       define LEAF_TAG 1
  70         size_t ld_size;         /* bytes per element    */
  71                                 /* multiple of ALIGNMENT        */
  72         size_t ld_nelements;    /* Number of elements.  */
  73         GC_descr ld_descriptor; /* A simple length, bitmap,     */
  74                                 /* or procedure descriptor.     */
  75     } ld;
  76     struct ComplexArrayDescriptor {
  77         word ad_tag;
  78 #       define ARRAY_TAG 2
  79         size_t ad_nelements;
  80         union ComplexDescriptor * ad_element_descr;
  81     } ad;
  82     struct SequenceDescriptor {
  83         word sd_tag;
  84 #       define SEQUENCE_TAG 3
  85         union ComplexDescriptor * sd_first;
  86         union ComplexDescriptor * sd_second;
  87     } sd;
  88 } complex_descriptor;
  89 #define TAG ld.ld_tag
  90
  91 ext_descr * GC_ext_descriptors; /* Points to array of extended  */
  92                                 /* descriptors.                 */
  93
  94 size_t GC_ed_size = 0;  /* Current size of above arrays.        */
  95 # define ED_INITIAL_SIZE 100;
  96
  97 size_t GC_avail_descr = 0;      /* Next available slot.         */
  98
  99 int GC_typed_mark_proc_index;   /* Indices of my mark           */
 100 int GC_array_mark_proc_index;   /* procedures.                  */
 101
 102 static void GC_push_typed_structures_proc (void)
 103 {
 104   GC_push_all((ptr_t)&GC_ext_descriptors, (ptr_t)&GC_ext_descriptors + sizeof(word));
 105 }
 106
 107 /* Add a multiword bitmap to GC_ext_descriptors arrays.  Return */
 108 /* starting index.                                              */
 109 /* Returns -1 on failure.                                       */
 110 /* Caller does not hold allocation lock.                        */
 111 signed_word GC_add_ext_descriptor(GC_bitmap bm, word nbits)
 112 {
 113     size_t nwords = divWORDSZ(nbits + WORDSZ-1);
 114     signed_word result;
 115     size_t i;
 116     word last_part;
 117     size_t extra_bits;
 118     DCL_LOCK_STATE;
 119
 120     LOCK();
 121     while (GC_avail_descr + nwords >= GC_ed_size) {
 122         ext_descr * new;
 123         size_t new_size;
 124         word ed_size = GC_ed_size;
 125
 126         if (ed_size == 0) {
 127             GC_push_typed_structures = GC_push_typed_structures_proc;
 128             UNLOCK();
 129             new_size = ED_INITIAL_SIZE;
 130         } else {
 131             UNLOCK();
 132             new_size = 2 * ed_size;
 133             if (new_size > MAX_ENV) return(-1);
 134         }
 135         new = (ext_descr *) GC_malloc_atomic(new_size * sizeof(ext_descr));
 136         if (new == 0) return(-1);
 137         LOCK();
 138         if (ed_size == GC_ed_size) {
 139             if (GC_avail_descr != 0) {
 140                 BCOPY(GC_ext_descriptors, new,
 141                       GC_avail_descr * sizeof(ext_descr));
 142             }
 143             GC_ed_size = new_size;
 144             GC_ext_descriptors = new;
 145         }  /* else another thread already resized it in the meantime */
 146     }
 147     result = GC_avail_descr;
 148     for (i = 0; i < nwords-1; i++) {
 149         GC_ext_descriptors[result + i].ed_bitmap = bm[i];
 150         GC_ext_descriptors[result + i].ed_continued = TRUE;
 151     }
 152     last_part = bm[i];
 153     /* Clear irrelevant bits. */
 154     extra_bits = nwords * WORDSZ - nbits;
 155     last_part <<= extra_bits;
 156     last_part >>= extra_bits;
 157     GC_ext_descriptors[result + i].ed_bitmap = last_part;
 158     GC_ext_descriptors[result + i].ed_continued = FALSE;
 159     GC_avail_descr += nwords;
 160     UNLOCK();
 161     return(result);
 162 }
 163
 164 /* Table of bitmap descriptors for n word long all pointer objects.     */
 165 GC_descr GC_bm_table[WORDSZ/2];
 166
 167 /* Return a descriptor for the concatenation of 2 nwords long objects,  */
 168 /* each of which is described by descriptor.                            */
 169 /* The result is known to be short enough to fit into a bitmap          */
 170 /* descriptor.                                                          */
 171 /* Descriptor is a GC_DS_LENGTH or GC_DS_BITMAP descriptor.             */
 172 GC_descr GC_double_descr(GC_descr descriptor, word nwords)
 173 {
 174     if ((descriptor & GC_DS_TAGS) == GC_DS_LENGTH) {
 175         descriptor = GC_bm_table[BYTES_TO_WORDS((word)descriptor)];
 176     };
 177     descriptor |= (descriptor & ~GC_DS_TAGS) >> nwords;
 178     return(descriptor);
 179 }
 180
 181 complex_descriptor * GC_make_sequence_descriptor();
 182
 183 /* Build a descriptor for an array with nelements elements,     */
 184 /* each of which can be described by a simple descriptor.       */
 185 /* We try to optimize some common cases.                        */
 186 /* If the result is COMPLEX, then a complex_descr* is returned  */
 187 /* in *complex_d.                                                       */
 188 /* If the result is LEAF, then we built a LeafDescriptor in     */
 189 /* the structure pointed to by leaf.                            */
 190 /* The tag in the leaf structure is not set.                    */
 191 /* If the result is SIMPLE, then a GC_descr                     */
 192 /* is returned in *simple_d.                                    */
 193 /* If the result is NO_MEM, then                                */
 194 /* we failed to allocate the descriptor.                        */
 195 /* The implementation knows that GC_DS_LENGTH is 0.             */
 196 /* *leaf, *complex_d, and *simple_d may be used as temporaries  */
 197 /* during the construction.                                     */
 198 # define COMPLEX 2
 199 # define LEAF 1
 200 # define SIMPLE 0
 201 # define NO_MEM (-1)
 202 int GC_make_array_descriptor(size_t nelements, size_t size, GC_descr descriptor,
 203                              GC_descr *simple_d,
 204                              complex_descriptor **complex_d,
 205                              struct LeafDescriptor * leaf)
 206 {
 207 #   define OPT_THRESHOLD 50
 208         /* For larger arrays, we try to combine descriptors of adjacent */
 209         /* descriptors to speed up marking, and to reduce the amount    */
 210         /* of space needed on the mark stack.                           */
 211     if ((descriptor & GC_DS_TAGS) == GC_DS_LENGTH) {
 212       if (descriptor == (GC_descr)size) {
 213         *simple_d = nelements * descriptor;
 214         return(SIMPLE);
 215       } else if ((word)descriptor == 0) {
 216         *simple_d = (GC_descr)0;
 217         return(SIMPLE);
 218       }
 219     }
 220     if (nelements <= OPT_THRESHOLD) {
 221       if (nelements <= 1) {
 222         if (nelements == 1) {
 223             *simple_d = descriptor;
 224             return(SIMPLE);
 225         } else {
 226             *simple_d = (GC_descr)0;
 227             return(SIMPLE);
 228         }
 229       }
 230     } else if (size <= BITMAP_BITS/2
 231                && (descriptor & GC_DS_TAGS) != GC_DS_PROC
 232                && (size & (sizeof(word)-1)) == 0) {
 233       int result =
 234           GC_make_array_descriptor(nelements/2, 2*size,
 235                                    GC_double_descr(descriptor,
 236                                                    BYTES_TO_WORDS(size)),
 237                                    simple_d, complex_d, leaf);
 238       if ((nelements & 1) == 0) {
 239           return(result);
 240       } else {
 241           struct LeafDescriptor * one_element =
 242               (struct LeafDescriptor *)
 243                 GC_malloc_atomic(sizeof(struct LeafDescriptor));
 244
 245           if (result == NO_MEM || one_element == 0) return(NO_MEM);
 246           one_element -> ld_tag = LEAF_TAG;
 247           one_element -> ld_size = size;
 248           one_element -> ld_nelements = 1;
 249           one_element -> ld_descriptor = descriptor;
 250           switch(result) {
 251             case SIMPLE:
 252             {
 253               struct LeafDescriptor * beginning =
 254                 (struct LeafDescriptor *)
 255                   GC_malloc_atomic(sizeof(struct LeafDescriptor));
 256               if (beginning == 0) return(NO_MEM);
 257               beginning -> ld_tag = LEAF_TAG;
 258               beginning -> ld_size = size;
 259               beginning -> ld_nelements = 1;
 260               beginning -> ld_descriptor = *simple_d;
 261               *complex_d = GC_make_sequence_descriptor(
 262                                 (complex_descriptor *)beginning,
 263                                 (complex_descriptor *)one_element);
 264               break;
 265             }
 266             case LEAF:
 267             {
 268               struct LeafDescriptor * beginning =
 269                 (struct LeafDescriptor *)
 270                   GC_malloc_atomic(sizeof(struct LeafDescriptor));
 271               if (beginning == 0) return(NO_MEM);
 272               beginning -> ld_tag = LEAF_TAG;
 273               beginning -> ld_size = leaf -> ld_size;
 274               beginning -> ld_nelements = leaf -> ld_nelements;
 275               beginning -> ld_descriptor = leaf -> ld_descriptor;
 276               *complex_d = GC_make_sequence_descriptor(
 277                                 (complex_descriptor *)beginning,
 278                                 (complex_descriptor *)one_element);
 279               break;
 280             }
 281             case COMPLEX:
 282               *complex_d = GC_make_sequence_descriptor(
 283                                 *complex_d,
 284                                 (complex_descriptor *)one_element);
 285               break;
 286           }
 287           return(COMPLEX);
 288       }
 289     }
 290     {
 291         leaf -> ld_size = size;
 292         leaf -> ld_nelements = nelements;
 293         leaf -> ld_descriptor = descriptor;
 294         return(LEAF);
 295     }
 296 }
 297
 298 complex_descriptor * GC_make_sequence_descriptor(complex_descriptor *first,
 299                                                  complex_descriptor *second)
 300 {
 301     struct SequenceDescriptor * result =
 302         (struct SequenceDescriptor *)
 303                 GC_malloc(sizeof(struct SequenceDescriptor));
 304     /* Can't result in overly conservative marking, since tags are      */
 305     /* very small integers. Probably faster than maintaining type       */
 306     /* info.                                                            */
 307     if (result != 0) {
 308         result -> sd_tag = SEQUENCE_TAG;
 309         result -> sd_first = first;
 310         result -> sd_second = second;
 311     }
 312     return((complex_descriptor *)result);
 313 }
 314
 315 #ifdef UNDEFINED
 316 complex_descriptor * GC_make_complex_array_descriptor(word nelements,
 317                                                       complex_descriptor *descr)
 318 {
 319     struct ComplexArrayDescriptor * result =
 320         (struct ComplexArrayDescriptor *)
 321                 GC_malloc(sizeof(struct ComplexArrayDescriptor));
 322
 323     if (result != 0) {
 324         result -> ad_tag = ARRAY_TAG;
 325         result -> ad_nelements = nelements;
 326         result -> ad_element_descr = descr;
 327     }
 328     return((complex_descriptor *)result);
 329 }
 330 #endif
 331
 332 ptr_t * GC_eobjfreelist;
 333
 334 ptr_t * GC_arobjfreelist;
 335
 336 mse * GC_typed_mark_proc(word * addr, mse * mark_stack_ptr,
 337                          mse * mark_stack_limit, word env);
 338
 339 mse * GC_array_mark_proc(word * addr, mse * mark_stack_ptr,
 340                          mse * mark_stack_limit, word env);
 341
 342 /* Caller does not hold allocation lock. */
 343 void GC_init_explicit_typing(void)
 344 {
 345     register int i;
 346     DCL_LOCK_STATE;
 347
 348
 349     /* Ignore gcc "no effect" warning.  */
 350     GC_STATIC_ASSERT(sizeof(struct LeafDescriptor) % sizeof(word) == 0);
 351     LOCK();
 352     if (GC_explicit_typing_initialized) {
 353       UNLOCK();
 354       return;
 355     }
 356     GC_explicit_typing_initialized = TRUE;
 357     /* Set up object kind with simple indirect descriptor. */
 358       GC_eobjfreelist = (ptr_t *)GC_new_free_list_inner();
 359       GC_explicit_kind = GC_new_kind_inner(
 360                             (void **)GC_eobjfreelist,
 361                             (((word)WORDS_TO_BYTES(-1)) | GC_DS_PER_OBJECT),
 362                             TRUE, TRUE);
 363                 /* Descriptors are in the last word of the object. */
 364       GC_typed_mark_proc_index = GC_new_proc_inner(GC_typed_mark_proc);
 365     /* Set up object kind with array descriptor. */
 366       GC_arobjfreelist = (ptr_t *)GC_new_free_list_inner();
 367       GC_array_mark_proc_index = GC_new_proc_inner(GC_array_mark_proc);
 368       GC_array_kind = GC_new_kind_inner(
 369                             (void **)GC_arobjfreelist,
 370                             GC_MAKE_PROC(GC_array_mark_proc_index, 0),
 371                             FALSE, TRUE);
 372       for (i = 0; i < WORDSZ/2; i++) {
 373           GC_descr d = (((word)(-1)) >> (WORDSZ - i)) << (WORDSZ - i);
 374           d |= GC_DS_BITMAP;
 375           GC_bm_table[i] = d;
 376       }
 377     UNLOCK();
 378 }
 379
 380 mse * GC_typed_mark_proc(word * addr, mse * mark_stack_ptr,
 381                          mse * mark_stack_limit, word env)
 382 {
 383     word bm = GC_ext_descriptors[env].ed_bitmap;
 384     word * current_p = addr;
 385     word current;
 386     ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
 387     ptr_t least_ha = GC_least_plausible_heap_addr;
 388     DECLARE_HDR_CACHE;
 389
 390     INIT_HDR_CACHE;
 391     for (; bm != 0; bm >>= 1, current_p++) {
 392         if (bm & 1) {
 393             current = *current_p;
 394             FIXUP_POINTER(current);
 395             if ((ptr_t)current >= least_ha && (ptr_t)current <= greatest_ha) {
 396                 PUSH_CONTENTS((ptr_t)current, mark_stack_ptr,
 397                               mark_stack_limit, current_p, exit1);
 398             }
 399         }
 400     }
 401     if (GC_ext_descriptors[env].ed_continued) {
 402         /* Push an entry with the rest of the descriptor back onto the  */
 403         /* stack.  Thus we never do too much work at once.  Note that   */
 404         /* we also can't overflow the mark stack unless we actually     */
 405         /* mark something.                                              */
 406         mark_stack_ptr++;
 407         if (mark_stack_ptr >= mark_stack_limit) {
 408             mark_stack_ptr = GC_signal_mark_stack_overflow(mark_stack_ptr);
 409         }
 410         mark_stack_ptr -> mse_start = (ptr_t)(addr + WORDSZ);
 411         mark_stack_ptr -> mse_descr =
 412                 GC_MAKE_PROC(GC_typed_mark_proc_index, env+1);
 413     }
 414     return(mark_stack_ptr);
 415 }
 416
 417 /* Return the size of the object described by d.  It would be faster to */
 418 /* store this directly, or to compute it as part of                     */
 419 /* GC_push_complex_descriptor, but hopefully it doesn't matter.         */
 420 word GC_descr_obj_size(complex_descriptor *d)
 421 {
 422     switch(d -> TAG) {
 423       case LEAF_TAG:
 424         return(d -> ld.ld_nelements * d -> ld.ld_size);
 425       case ARRAY_TAG:
 426         return(d -> ad.ad_nelements
 427                * GC_descr_obj_size(d -> ad.ad_element_descr));
 428       case SEQUENCE_TAG:
 429         return(GC_descr_obj_size(d -> sd.sd_first)
 430                + GC_descr_obj_size(d -> sd.sd_second));
 431       default:
 432         ABORT("Bad complex descriptor");
 433         /*NOTREACHED*/ return 0; /*NOTREACHED*/
 434     }
 435 }
 436
 437 /* Push descriptors for the object at addr with complex descriptor d    */
 438 /* onto the mark stack.  Return 0 if the mark stack overflowed.         */
 439 mse * GC_push_complex_descriptor(word *addr, complex_descriptor *d,
 440                                  mse *msp, mse *msl)
 441 {
 442     register ptr_t current = (ptr_t) addr;
 443     register word nelements;
 444     register word sz;
 445     register word i;
 446
 447     switch(d -> TAG) {
 448       case LEAF_TAG:
 449         {
 450           register GC_descr descr = d -> ld.ld_descriptor;
 451
 452           nelements = d -> ld.ld_nelements;
 453           if (msl - msp <= (ptrdiff_t)nelements) return(0);
 454           sz = d -> ld.ld_size;
 455           for (i = 0; i < nelements; i++) {
 456               msp++;
 457               msp -> mse_start = current;
 458               msp -> mse_descr = descr;
 459               current += sz;
 460           }
 461           return(msp);
 462         }
 463       case ARRAY_TAG:
 464         {
 465           register complex_descriptor *descr = d -> ad.ad_element_descr;
 466
 467           nelements = d -> ad.ad_nelements;
 468           sz = GC_descr_obj_size(descr);
 469           for (i = 0; i < nelements; i++) {
 470               msp = GC_push_complex_descriptor((word *)current, descr,
 471                                                 msp, msl);
 472               if (msp == 0) return(0);
 473               current += sz;
 474           }
 475           return(msp);
 476         }
 477       case SEQUENCE_TAG:
 478         {
 479           sz = GC_descr_obj_size(d -> sd.sd_first);
 480           msp = GC_push_complex_descriptor((word *)current, d -> sd.sd_first,
 481                                            msp, msl);
 482           if (msp == 0) return(0);
 483           current += sz;
 484           msp = GC_push_complex_descriptor((word *)current, d -> sd.sd_second,
 485                                            msp, msl);
 486           return(msp);
 487         }
 488       default:
 489         ABORT("Bad complex descriptor");
 490         /*NOTREACHED*/ return 0; /*NOTREACHED*/
 491    }
 492 }
 493
 494 /*ARGSUSED*/
 495 mse * GC_array_mark_proc(word * addr, mse * mark_stack_ptr,
 496                          mse * mark_stack_limit, word env)
 497 {
 498     hdr * hhdr = HDR(addr);
 499     size_t sz = hhdr -> hb_sz;
 500     size_t nwords = BYTES_TO_WORDS(sz);
 501     complex_descriptor * descr = (complex_descriptor *)(addr[nwords-1]);
 502     mse * orig_mark_stack_ptr = mark_stack_ptr;
 503     mse * new_mark_stack_ptr;
 504
 505     if (descr == 0) {
 506         /* Found a reference to a free list entry.  Ignore it. */
 507         return(orig_mark_stack_ptr);
 508     }
 509     /* In use counts were already updated when array descriptor was     */
 510     /* pushed.  Here we only replace it by subobject descriptors, so    */
 511     /* no update is necessary.                                          */
 512     new_mark_stack_ptr = GC_push_complex_descriptor(addr, descr,
 513                                                     mark_stack_ptr,
 514                                                     mark_stack_limit-1);
 515     if (new_mark_stack_ptr == 0) {
 516         /* Doesn't fit.  Conservatively push the whole array as a unit  */
 517         /* and request a mark stack expansion.                          */
 518         /* This cannot cause a mark stack overflow, since it replaces   */
 519         /* the original array entry.                                    */
 520         GC_mark_stack_too_small = TRUE;
 521         new_mark_stack_ptr = orig_mark_stack_ptr + 1;
 522         new_mark_stack_ptr -> mse_start = (ptr_t)addr;
 523         new_mark_stack_ptr -> mse_descr = sz | GC_DS_LENGTH;
 524     } else {
 525         /* Push descriptor itself */
 526         new_mark_stack_ptr++;
 527         new_mark_stack_ptr -> mse_start = (ptr_t)(addr + nwords - 1);
 528         new_mark_stack_ptr -> mse_descr = sizeof(word) | GC_DS_LENGTH;
 529     }
 530     return new_mark_stack_ptr;
 531 }
 532
 533 GC_descr GC_make_descriptor(GC_bitmap bm, size_t len)
 534 {
 535     signed_word last_set_bit = len - 1;
 536     GC_descr result;
 537     signed_word i;
 538 #   define HIGH_BIT (((word)1) << (WORDSZ - 1))
 539
 540     if (!GC_explicit_typing_initialized) GC_init_explicit_typing();
 541     while (last_set_bit >= 0 && !GC_get_bit(bm, last_set_bit)) last_set_bit --;
 542     if (last_set_bit < 0) return(0 /* no pointers */);
 543 #   if ALIGNMENT == CPP_WORDSZ/8
 544     {
 545       register GC_bool all_bits_set = TRUE;
 546       for (i = 0; i < last_set_bit; i++) {
 547         if (!GC_get_bit(bm, i)) {
 548             all_bits_set = FALSE;
 549             break;
 550         }
 551       }
 552       if (all_bits_set) {
 553         /* An initial section contains all pointers.  Use length descriptor. */
 554         return (WORDS_TO_BYTES(last_set_bit+1) | GC_DS_LENGTH);
 555       }
 556     }
 557 #   endif
 558     if (last_set_bit < BITMAP_BITS) {
 559         /* Hopefully the common case.                   */
 560         /* Build bitmap descriptor (with bits reversed) */
 561         result = HIGH_BIT;
 562         for (i = last_set_bit - 1; i >= 0; i--) {
 563             result >>= 1;
 564             if (GC_get_bit(bm, i)) result |= HIGH_BIT;
 565         }
 566         result |= GC_DS_BITMAP;
 567         return(result);
 568     } else {
 569         signed_word index;
 570
 571         index = GC_add_ext_descriptor(bm, (word)last_set_bit+1);
 572         if (index == -1) return(WORDS_TO_BYTES(last_set_bit+1) | GC_DS_LENGTH);
 573                                 /* Out of memory: use conservative      */
 574                                 /* approximation.                       */
 575         result = GC_MAKE_PROC(GC_typed_mark_proc_index, (word)index);
 576         return result;
 577     }
 578 }
 579
 580 ptr_t GC_clear_stack();
 581
 582 #define GENERAL_MALLOC(lb,k) \
 583     (void *)GC_clear_stack(GC_generic_malloc((word)lb, k))
 584
 585 #define GENERAL_MALLOC_IOP(lb,k) \
 586     (void *)GC_clear_stack(GC_generic_malloc_ignore_off_page(lb, k))
 587
 588 void * GC_malloc_explicitly_typed(size_t lb, GC_descr d)
 589 {
 590     ptr_t op;
 591     ptr_t * opp;
 592     size_t lg;
 593     DCL_LOCK_STATE;
 594
 595     lb += TYPD_EXTRA_BYTES;
 596     if(SMALL_OBJ(lb)) {
 597         lg = GC_size_map[lb];
 598         opp = &(GC_eobjfreelist[lg]);
 599         LOCK();
 600         if( (op = *opp) == 0 ) {
 601             UNLOCK();
 602             op = (ptr_t)GENERAL_MALLOC((word)lb, GC_explicit_kind);
 603             if (0 == op) return 0;
 604             lg = GC_size_map[lb];       /* May have been uninitialized. */
 605         } else {
 606             *opp = obj_link(op);
 607             obj_link(op) = 0;
 608             GC_bytes_allocd += GRANULES_TO_BYTES(lg);
 609             UNLOCK();
 610         }
 611    } else {
 612        op = (ptr_t)GENERAL_MALLOC((word)lb, GC_explicit_kind);
 613        if (op != NULL)
 614             lg = BYTES_TO_GRANULES(GC_size(op));
 615    }
 616    if (op != NULL)
 617        ((word *)op)[GRANULES_TO_WORDS(lg) - 1] = d;
 618    return((void *) op);
 619 }
 620
 621 void * GC_malloc_explicitly_typed_ignore_off_page(size_t lb, GC_descr d)
 622 {
 623 ptr_t op;
 624 ptr_t * opp;
 625 size_t lg;
 626 DCL_LOCK_STATE;
 627
 628     lb += TYPD_EXTRA_BYTES;
 629     if( SMALL_OBJ(lb) ) {
 630         lg = GC_size_map[lb];
 631         opp = &(GC_eobjfreelist[lg]);
 632         LOCK();
 633         if( (op = *opp) == 0 ) {
 634             UNLOCK();
 635             op = (ptr_t)GENERAL_MALLOC_IOP(lb, GC_explicit_kind);
 636             lg = GC_size_map[lb];       /* May have been uninitialized. */
 637         } else {
 638             *opp = obj_link(op);
 639             obj_link(op) = 0;
 640             GC_bytes_allocd += GRANULES_TO_BYTES(lg);
 641             UNLOCK();
 642         }
 643    } else {
 644        op = (ptr_t)GENERAL_MALLOC_IOP(lb, GC_explicit_kind);
 645        if (op != NULL)
 646          lg = BYTES_TO_WORDS(GC_size(op));
 647    }
 648    if (op != NULL)
 649        ((word *)op)[GRANULES_TO_WORDS(lg) - 1] = d;
 650    return((void *) op);
 651 }
 652
 653 void * GC_calloc_explicitly_typed(size_t n, size_t lb, GC_descr d)
 654 {
 655 ptr_t op;
 656 ptr_t * opp;
 657 size_t lg;
 658 GC_descr simple_descr;
 659 complex_descriptor *complex_descr;
 660 register int descr_type;
 661 struct LeafDescriptor leaf;
 662 DCL_LOCK_STATE;
 663
 664     descr_type = GC_make_array_descriptor((word)n, (word)lb, d,
 665                                           &simple_descr, &complex_descr, &leaf);
 666     switch(descr_type) {
 667         case NO_MEM: return(0);
 668         case SIMPLE: return(GC_malloc_explicitly_typed(n*lb, simple_descr));
 669         case LEAF:
 670             lb *= n;
 671             lb += sizeof(struct LeafDescriptor) + TYPD_EXTRA_BYTES;
 672             break;
 673         case COMPLEX:
 674             lb *= n;
 675             lb += TYPD_EXTRA_BYTES;
 676             break;
 677     }
 678     if( SMALL_OBJ(lb) ) {
 679         lg = GC_size_map[lb];
 680         opp = &(GC_arobjfreelist[lg]);
 681         LOCK();
 682         if( (op = *opp) == 0 ) {
 683             UNLOCK();
 684             op = (ptr_t)GENERAL_MALLOC((word)lb, GC_array_kind);
 685             if (0 == op) return(0);
 686             lg = GC_size_map[lb];       /* May have been uninitialized. */
 687         } else {
 688             *opp = obj_link(op);
 689             obj_link(op) = 0;
 690             GC_bytes_allocd += GRANULES_TO_BYTES(lg);
 691             UNLOCK();
 692         }
 693    } else {
 694        op = (ptr_t)GENERAL_MALLOC((word)lb, GC_array_kind);
 695        if (0 == op) return(0);
 696        lg = BYTES_TO_GRANULES(GC_size(op));
 697    }
 698    if (descr_type == LEAF) {
 699        /* Set up the descriptor inside the object itself. */
 700        volatile struct LeafDescriptor * lp =
 701            (struct LeafDescriptor *)
 702                ((word *)op
 703                 + GRANULES_TO_WORDS(lg)
 704                 - (BYTES_TO_WORDS(sizeof(struct LeafDescriptor)) + 1));
 705
 706        lp -> ld_tag = LEAF_TAG;
 707        lp -> ld_size = leaf.ld_size;
 708        lp -> ld_nelements = leaf.ld_nelements;
 709        lp -> ld_descriptor = leaf.ld_descriptor;
 710        ((volatile word *)op)[GRANULES_TO_WORDS(lg) - 1] = (word)lp;
 711    } else {
 712        extern unsigned GC_finalization_failures;
 713        unsigned ff = GC_finalization_failures;
 714        size_t lw = GRANULES_TO_WORDS(lg);
 715
 716        ((word *)op)[lw - 1] = (word)complex_descr;
 717        /* Make sure the descriptor is cleared once there is any danger  */
 718        /* it may have been collected.                                   */
 719        (void)
 720          GC_general_register_disappearing_link((void * *)
 721                                                   ((word *)op+lw-1),
 722                                                   (void *) op);
 723        if (ff != GC_finalization_failures) {
 724            /* Couldn't register it due to lack of memory.  Punt.        */
 725            /* This will probably fail too, but gives the recovery code  */
 726            /* a chance.                                                 */
 727            return(GC_malloc(n*lb));
 728        }
 729    }
 730    return((void *) op);
 731 }