runtime/objc-layout.mm

   1 /*
   2  * Copyright (c) 2004-2008 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 #include <stdlib.h>
  25 #include <assert.h>
  26
  27 #include "objc-private.h"
  28
  29 /**********************************************************************
  30 * Object Layouts.
  31 *
  32 * Layouts are used by the garbage collector to identify references from
  33 * the object to other objects.
  34 *
  35 * Layout information is in the form of a '\0' terminated byte string.
  36 * Each byte contains a word skip count in the high nibble and a
  37 * consecutive references count in the low nibble. Counts that exceed 15 are
  38 * continued in the succeeding byte with a zero in the opposite nibble.
  39 * Objects that should be scanned conservatively will have a NULL layout.
  40 * Objects that have no references have a empty byte string.
  41 *
  42 * Example;
  43 *
  44 *   For a class with pointers at offsets 4,12, 16, 32-128
  45 *   the layout is { 0x11, 0x12, 0x3f, 0x0a, 0x00 } or
  46 *       skip 1 - 1 reference (4)
  47 *       skip 1 - 2 references (12, 16)
  48 *       skip 3 - 15 references (32-88)
  49 *       no skip - 10 references (92-128)
  50 *       end
  51 *
  52 **********************************************************************/
  53
  54
  55 /**********************************************************************
  56 * compress_layout
  57 * Allocates and returns a compressed string matching the given layout bitmap.
  58 **********************************************************************/
  59 static unsigned char *
  60 compress_layout(const uint8_t *bits, size_t bitmap_bits, bool weak)
  61 {
  62     bool all_set = YES;
  63     bool none_set = YES;
  64     unsigned char *result;
  65
  66     // overallocate a lot; reallocate at correct size later
  67     unsigned char * const layout = (unsigned char *)
  68         calloc(bitmap_bits + 1, 1);
  69     unsigned char *l = layout;
  70
  71     size_t i = 0;
  72     while (i < bitmap_bits) {
  73         size_t skip = 0;
  74         size_t scan = 0;
  75
  76         // Count one range each of skip and scan.
  77         while (i < bitmap_bits) {
  78             uint8_t bit = (uint8_t)((bits[i/8] >> (i % 8)) & 1);
  79             if (bit) break;
  80             i++;
  81             skip++;
  82         }
  83         while (i < bitmap_bits) {
  84             uint8_t bit = (uint8_t)((bits[i/8] >> (i % 8)) & 1);
  85             if (!bit) break;
  86             i++;
  87             scan++;
  88             none_set = NO;
  89         }
  90
  91         // Record skip and scan
  92         if (skip) all_set = NO;
  93         if (scan) none_set = NO;
  94         while (skip > 0xf) {
  95             *l++ = 0xf0;
  96             skip -= 0xf;
  97         }
  98         if (skip || scan) {
  99             *l = (uint8_t)(skip << 4);    // NOT incremented - merges with scan
 100             while (scan > 0xf) {
 101                 *l++ |= 0x0f;  // May merge with short skip; must calloc
 102                 scan -= 0xf;
 103             }
 104             *l++ |= scan;      // NOT checked for zero - always increments
 105                                // May merge with short skip; must calloc
 106         }
 107     }
 108
 109     // insert terminating byte
 110     *l++ = '\0';
 111
 112     // return result
 113     if (none_set  &&  weak) {
 114         result = NULL;  // NULL weak layout means none-weak
 115     } else if (all_set  &&  !weak) {
 116         result = NULL;  // NULL ivar layout means all-scanned
 117     } else {
 118         result = (unsigned char *)strdup((char *)layout);
 119     }
 120     free(layout);
 121     return result;
 122 }
 123
 124
 125 static void set_bits(layout_bitmap bits, size_t which, size_t count)
 126 {
 127     // fixme optimize for byte/word at a time
 128     size_t bit;
 129     for (bit = which; bit < which + count  &&  bit < bits.bitCount; bit++) {
 130         bits.bits[bit/8] |= 1 << (bit % 8);
 131     }
 132     if (bit == bits.bitCount  &&  bit < which + count) {
 133         // couldn't fit full type in bitmap
 134         _objc_fatal("layout bitmap too short");
 135     }
 136 }
 137
 138 static void clear_bits(layout_bitmap bits, size_t which, size_t count)
 139 {
 140     // fixme optimize for byte/word at a time
 141     size_t bit;
 142     for (bit = which; bit < which + count  &&  bit < bits.bitCount; bit++) {
 143         bits.bits[bit/8] &= ~(1 << (bit % 8));
 144     }
 145     if (bit == bits.bitCount  &&  bit < which + count) {
 146         // couldn't fit full type in bitmap
 147         _objc_fatal("layout bitmap too short");
 148     }
 149 }
 150
 151 static void move_bits(layout_bitmap bits, size_t src, size_t dst,
 152                       size_t count)
 153 {
 154     // fixme optimize for byte/word at a time
 155
 156     if (dst == src) {
 157         return;
 158     }
 159     else if (dst > src) {
 160         // Copy backwards in case of overlap
 161         size_t pos = count;
 162         while (pos--) {
 163             size_t srcbit = src + pos;
 164             size_t dstbit = dst + pos;
 165             if (bits.bits[srcbit/8] & (1 << (srcbit % 8))) {
 166                 bits.bits[dstbit/8] |= 1 << (dstbit % 8);
 167             } else {
 168                 bits.bits[dstbit/8] &= ~(1 << (dstbit % 8));
 169             }
 170         }
 171     }
 172     else {
 173         // Copy forwards in case of overlap
 174         size_t pos;
 175         for (pos = 0; pos < count; pos++) {
 176             size_t srcbit = src + pos;
 177             size_t dstbit = dst + pos;
 178             if (bits.bits[srcbit/8] & (1 << (srcbit % 8))) {
 179                 bits.bits[dstbit/8] |= 1 << (dstbit % 8);
 180             } else {
 181                 bits.bits[dstbit/8] &= ~(1 << (dstbit % 8));
 182             }
 183         }
 184     }
 185 }
 186
 187 // emacs autoindent hack - it doesn't like the loop in set_bits/clear_bits
 188 #if 0
 189 } }
 190 #endif
 191
 192
 193 static void decompress_layout(const unsigned char *layout_string, layout_bitmap bits)
 194 {
 195     unsigned char c;
 196     size_t bit = 0;
 197     while ((c = *layout_string++)) {
 198         unsigned char skip = (c & 0xf0) >> 4;
 199         unsigned char scan = (c & 0x0f);
 200         bit += skip;
 201         set_bits(bits, bit, scan);
 202         bit += scan;
 203     }
 204 }
 205
 206
 207 /***********************************************************************
 208 * layout_bitmap_create
 209 * Allocate a layout bitmap.
 210 * The new bitmap spans the given instance size bytes.
 211 * The start of the bitmap is filled from the given layout string (which
 212 *   spans an instance size of layoutStringSize); the rest is zero-filled.
 213 * The returned bitmap must be freed with layout_bitmap_free().
 214 **********************************************************************/
 215 layout_bitmap
 216 layout_bitmap_create(const unsigned char *layout_string,
 217                      size_t layoutStringInstanceSize,
 218                      size_t instanceSize, bool weak)
 219 {
 220     layout_bitmap result;
 221     size_t words = instanceSize / sizeof(id);
 222
 223     result.weak = weak;
 224     result.bitCount = words;
 225     result.bitsAllocated = words;
 226     result.bits = (uint8_t *)calloc((words+7)/8, 1);
 227
 228     if (!layout_string) {
 229         if (!weak) {
 230             // NULL ivar layout means all-scanned
 231             // (but only up to layoutStringSize instance size)
 232             set_bits(result, 0, layoutStringInstanceSize/sizeof(id));
 233         } else {
 234             // NULL weak layout means none-weak.
 235         }
 236     } else {
 237         decompress_layout(layout_string, result);
 238     }
 239
 240     return result;
 241 }
 242
 243
 244 /***********************************************************************
 245  * layout_bitmap_create_empty
 246  * Allocate a layout bitmap.
 247  * The new bitmap spans the given instance size bytes.
 248  * The bitmap is empty, to represent an object whose ivars are completely unscanned.
 249  * The returned bitmap must be freed with layout_bitmap_free().
 250  **********************************************************************/
 251 layout_bitmap
 252 layout_bitmap_create_empty(size_t instanceSize, bool weak)
 253 {
 254     layout_bitmap result;
 255     size_t words = instanceSize / sizeof(id);
 256
 257     result.weak = weak;
 258     result.bitCount = words;
 259     result.bitsAllocated = words;
 260     result.bits = (uint8_t *)calloc((words+7)/8, 1);
 261
 262     return result;
 263 }
 264
 265 void
 266 layout_bitmap_free(layout_bitmap bits)
 267 {
 268     if (bits.bits) free(bits.bits);
 269 }
 270
 271 const unsigned char *
 272 layout_string_create(layout_bitmap bits)
 273 {
 274     const unsigned char *result =
 275         compress_layout(bits.bits, bits.bitCount, bits.weak);
 276
 277 #if DEBUG
 278     // paranoia: cycle to bitmap and back to string again, and compare
 279     layout_bitmap check = layout_bitmap_create(result, bits.bitCount*sizeof(id),
 280                                                bits.bitCount*sizeof(id), bits.weak);
 281     unsigned char *result2 =
 282         compress_layout(check.bits, check.bitCount, check.weak);
 283     if (result != result2  &&  0 != strcmp((char*)result, (char *)result2)) {
 284         layout_bitmap_print(bits);
 285         layout_bitmap_print(check);
 286         _objc_fatal("libobjc bug: mishandled layout bitmap");
 287     }
 288     free(result2);
 289     layout_bitmap_free(check);
 290 #endif
 291
 292     return result;
 293 }
 294
 295
 296 void
 297 layout_bitmap_set_ivar(layout_bitmap bits, const char *type, size_t offset)
 298 {
 299     // fixme only handles some types
 300     size_t bit = offset / sizeof(id);
 301
 302     if (!type) return;
 303     if (type[0] == '@'  ||  0 == strcmp(type, "^@")) {
 304         // id
 305         // id *
 306         // Block ("@?")
 307         set_bits(bits, bit, 1);
 308     }
 309     else if (type[0] == '[') {
 310         // id[]
 311         char *t;
 312         unsigned long count = strtoul(type+1, &t, 10);
 313         if (t  &&  t[0] == '@') {
 314             set_bits(bits, bit, count);
 315         }
 316     }
 317     else if (strchr(type, '@')) {
 318         _objc_inform("warning: failing to set GC layout for '%s'\n", type);
 319     }
 320 }
 321
 322
 323
 324 /***********************************************************************
 325 * layout_bitmap_grow
 326 * Expand a layout bitmap to span newCount bits.
 327 * The new bits are undefined.
 328 **********************************************************************/
 329 void
 330 layout_bitmap_grow(layout_bitmap *bits, size_t newCount)
 331 {
 332     if (bits->bitCount >= newCount) return;
 333     bits->bitCount = newCount;
 334     if (bits->bitsAllocated < newCount) {
 335         size_t newAllocated = bits->bitsAllocated * 2;
 336         if (newAllocated < newCount) newAllocated = newCount;
 337         bits->bits = (uint8_t *)
 338             realloc(bits->bits, (newAllocated+7) / 8);
 339         bits->bitsAllocated = newAllocated;
 340     }
 341     ASSERT(bits->bitsAllocated >= bits->bitCount);
 342     ASSERT(bits->bitsAllocated >= newCount);
 343 }
 344
 345
 346 /***********************************************************************
 347 * layout_bitmap_slide
 348 * Slide the end of a layout bitmap farther from the start.
 349 * Slides bits [oldPos, bits.bitCount) to [newPos, bits.bitCount+newPos-oldPos)
 350 * Bits [oldPos, newPos) are zero-filled.
 351 * The bitmap is expanded and bitCount updated if necessary.
 352 * newPos >= oldPos.
 353 **********************************************************************/
 354 void
 355 layout_bitmap_slide(layout_bitmap *bits, size_t oldPos, size_t newPos)
 356 {
 357     size_t shift;
 358     size_t count;
 359
 360     if (oldPos == newPos) return;
 361     if (oldPos > newPos) _objc_fatal("layout bitmap sliding backwards");
 362
 363     shift = newPos - oldPos;
 364     count = bits->bitCount - oldPos;
 365     layout_bitmap_grow(bits, bits->bitCount + shift);
 366     move_bits(*bits, oldPos, newPos, count);  // slide
 367     clear_bits(*bits, oldPos, shift);         // zero-fill
 368 }
 369
 370
 371 /***********************************************************************
 372 * layout_bitmap_slide_anywhere
 373 * Slide the end of a layout bitmap relative to the start.
 374 * Like layout_bitmap_slide, but can slide backwards too.
 375 * The end of the bitmap is truncated.
 376 **********************************************************************/
 377 void
 378 layout_bitmap_slide_anywhere(layout_bitmap *bits, size_t oldPos, size_t newPos)
 379 {
 380     size_t shift;
 381     size_t count;
 382
 383     if (oldPos == newPos) return;
 384
 385     if (oldPos < newPos) {
 386         layout_bitmap_slide(bits, oldPos, newPos);
 387         return;
 388     }
 389
 390     shift = oldPos - newPos;
 391     count = bits->bitCount - oldPos;
 392     move_bits(*bits, oldPos, newPos, count);  // slide
 393     bits->bitCount -= shift;
 394 }
 395
 396
 397 /***********************************************************************
 398 * layout_bitmap_splat
 399 * Pastes the contents of bitmap src to the start of bitmap dst.
 400 * dst bits between the end of src and oldSrcInstanceSize are zeroed.
 401 * dst must be at least as long as src.
 402 * Returns YES if any of dst's bits were changed.
 403 **********************************************************************/
 404 bool
 405 layout_bitmap_splat(layout_bitmap dst, layout_bitmap src,
 406                     size_t oldSrcInstanceSize)
 407 {
 408     bool changed;
 409     size_t oldSrcBitCount;
 410     size_t bit;
 411
 412     if (dst.bitCount < src.bitCount) _objc_fatal("layout bitmap too short");
 413
 414     changed = NO;
 415     oldSrcBitCount = oldSrcInstanceSize / sizeof(id);
 416
 417     // fixme optimize for byte/word at a time
 418     for (bit = 0; bit < oldSrcBitCount; bit++) {
 419         int dstset = dst.bits[bit/8] & (1 << (bit % 8));
 420         int srcset = (bit < src.bitCount)
 421             ? src.bits[bit/8] & (1 << (bit % 8))
 422             : 0;
 423         if (dstset != srcset) {
 424             changed = YES;
 425             if (srcset) {
 426                 dst.bits[bit/8] |= 1 << (bit % 8);
 427             } else {
 428                 dst.bits[bit/8] &= ~(1 << (bit % 8));
 429             }
 430         }
 431     }
 432
 433     return changed;
 434 }
 435
 436
 437 /***********************************************************************
 438 * layout_bitmap_or
 439 * Set dst=dst|src.
 440 * dst must be at least as long as src.
 441 * Returns YES if any of dst's bits were changed.
 442 **********************************************************************/
 443 bool
 444 layout_bitmap_or(layout_bitmap dst, layout_bitmap src, const char *msg)
 445 {
 446     bool changed = NO;
 447     size_t bit;
 448
 449     if (dst.bitCount < src.bitCount) {
 450         _objc_fatal("layout_bitmap_or: layout bitmap too short%s%s",
 451                     msg ? ": " : "", msg ? msg : "");
 452     }
 453
 454     // fixme optimize for byte/word at a time
 455     for (bit = 0; bit < src.bitCount; bit++) {
 456         int dstset = dst.bits[bit/8] & (1 << (bit % 8));
 457         int srcset = src.bits[bit/8] & (1 << (bit % 8));
 458         if (srcset  &&  !dstset) {
 459             changed = YES;
 460             dst.bits[bit/8] |= 1 << (bit % 8);
 461         }
 462     }
 463
 464     return changed;
 465 }
 466
 467
 468 /***********************************************************************
 469 * layout_bitmap_clear
 470 * Set dst=dst&~src.
 471 * dst must be at least as long as src.
 472 * Returns YES if any of dst's bits were changed.
 473 **********************************************************************/
 474 bool
 475 layout_bitmap_clear(layout_bitmap dst, layout_bitmap src, const char *msg)
 476 {
 477     bool changed = NO;
 478     size_t bit;
 479
 480     if (dst.bitCount < src.bitCount) {
 481         _objc_fatal("layout_bitmap_clear: layout bitmap too short%s%s",
 482                     msg ? ": " : "", msg ? msg : "");
 483     }
 484
 485     // fixme optimize for byte/word at a time
 486     for (bit = 0; bit < src.bitCount; bit++) {
 487         int dstset = dst.bits[bit/8] & (1 << (bit % 8));
 488         int srcset = src.bits[bit/8] & (1 << (bit % 8));
 489         if (srcset  &&  dstset) {
 490             changed = YES;
 491             dst.bits[bit/8] &= ~(1 << (bit % 8));
 492         }
 493     }
 494
 495     return changed;
 496 }
 497
 498
 499 void
 500 layout_bitmap_print(layout_bitmap bits)
 501 {
 502     size_t i;
 503     printf("%zu: ", bits.bitCount);
 504     for (i = 0; i < bits.bitCount; i++) {
 505         int set = bits.bits[i/8] & (1 << (i % 8));
 506         printf("%c", set ? '#' : '.');
 507     }
 508     printf("\n");
 509 }
 510
 511 #if 0
 512 // The code below may be useful when interpreting ivar types more precisely.
 513
 514 /**********************************************************************
 515 * mark_offset_for_layout
 516 *
 517 * Marks the appropriate bit in the bits array cooresponding to a the
 518 * offset of a reference.  If we are scanning a nested pointer structure
 519 * then the bits array will be NULL then this function does nothing.
 520 *
 521 **********************************************************************/
 522 static void mark_offset_for_layout(long offset, long bits_size, unsigned char *bits) {
 523     // references are ignored if bits is NULL
 524     if (bits) {
 525         long slot = offset / sizeof(long);
 526
 527         // determine byte index using (offset / 8 bits per byte)
 528         long i_byte = slot >> 3;
 529
 530         // if the byte index is valid
 531         if (i_byte < bits_size) {
 532             // set the (offset / 8 bits per byte)th bit
 533             bits[i_byte] |= 1 << (slot & 7);
 534         } else {
 535             // offset not within instance size
 536             _objc_inform ("layout - offset exceeds instance size");
 537         }
 538     }
 539 }
 540
 541 /**********************************************************************
 542 * skip_ivar_type_name
 543 *
 544 * Skip over the name of a field/class in an ivar type string.  Names
 545 * are in the form of a double-quoted string.  Returns the remaining
 546 * string.
 547 *
 548 **********************************************************************/
 549 static char *skip_ivar_type_name(char *type) {
 550     // current character
 551     char ch;
 552
 553     // if there is an open quote
 554     if (*type == '\"') {
 555         // skip quote
 556         type++;
 557
 558         // while no closing quote
 559         while ((ch = *type) != '\"') {
 560             // if end of string return end of string
 561             if (!ch) return type;
 562
 563             // skip character
 564             type++;
 565         }
 566
 567         // skip closing quote
 568         type++;
 569     }
 570
 571     // return remaining string
 572     return type;
 573 }
 574
 575
 576 /**********************************************************************
 577 * skip_ivar_struct_name
 578 *
 579 * Skip over the name of a struct in an ivar type string.  Names
 580 * may be followed by an equals sign.  Returns the remaining string.
 581 *
 582 **********************************************************************/
 583 static char *skip_ivar_struct_name(char *type) {
 584     // get first character
 585     char ch = *type;
 586
 587     if (ch == _C_UNDEF) {
 588         // skip undefined name
 589         type++;
 590     } else if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || ch == '_') {
 591         // if alphabetic
 592
 593         // scan alphanumerics
 594         do {
 595             // next character
 596             ch = *++type;
 597         } while ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || ch == '_' || (ch >= '0' && ch <= '9'));
 598     } else {
 599         // no struct name present
 600         return type;
 601     }
 602
 603     // skip equals sign
 604     if (*type == '=') type++;
 605
 606     return type;
 607 }
 608
 609
 610 /**********************************************************************
 611 * scan_basic_ivar_type
 612 *
 613 * Determines the size and alignment of a basic ivar type.  If the basic
 614 * type is a possible reference to another garbage collected type the
 615 * is_reference is set to true (false otherwise.)  Returns the remaining
 616 * string.
 617 *
 618 **********************************************************************/
 619 static char *scan_ivar_type_for_layout(char *type, long offset, long bits_size, unsigned char *bits, long *next_offset);
 620 static char *scan_basic_ivar_type(char *type, long *size, long *alignment, bool *is_reference) {
 621     // assume it is a non-reference type
 622     *is_reference = NO;
 623
 624     // get the first character (advancing string)
 625     const char *full_type = type;
 626     char ch = *type++;
 627
 628     // GCC 4 uses for const type*.
 629     if (ch == _C_CONST) ch = *type++;
 630
 631     // act on first character
 632     switch (ch) {
 633         case _C_ID: {
 634             // ID type
 635
 636             // skip over optional class name
 637             type = skip_ivar_type_name(type);
 638
 639             // size and alignment of an id type
 640             *size = sizeof(id);
 641             *alignment = __alignof(id);
 642
 643             // is a reference type
 644             *is_reference = YES;
 645             break;
 646         }
 647         case _C_PTR: {
 648             // C pointer type
 649
 650             // skip underlying type
 651             long ignored_offset;
 652             type = scan_ivar_type_for_layout(type, 0, 0, NULL, &ignored_offset);
 653
 654             // size and alignment of a generic pointer type
 655             *size = sizeof(void *);
 656             *alignment = __alignof(void *);
 657
 658             // is a reference type
 659             *is_reference = YES;
 660             break;
 661         }
 662         case _C_CHARPTR: {
 663             // C string
 664
 665            // size and alignment of a char pointer type
 666             *size = sizeof(char *);
 667             *alignment = __alignof(char *);
 668
 669             // is a reference type
 670             *is_reference = YES;
 671             break;
 672         }
 673         case _C_CLASS:
 674         case _C_SEL: {
 675             // classes and selectors are ignored for now
 676             *size = sizeof(void *);
 677             *alignment = __alignof(void *);
 678             break;
 679         }
 680         case _C_CHR:
 681         case _C_UCHR: {
 682             // char and unsigned char
 683             *size = sizeof(char);
 684             *alignment = __alignof(char);
 685             break;
 686         }
 687         case _C_SHT:
 688         case _C_USHT: {
 689             // short and unsigned short
 690             *size = sizeof(short);
 691             *alignment = __alignof(short);
 692             break;
 693         }
 694         case _C_ATOM:
 695         case _C_INT:
 696         case _C_UINT: {
 697             // int and unsigned int
 698             *size = sizeof(int);
 699             *alignment = __alignof(int);
 700             break;
 701         }
 702         case _C_LNG:
 703         case _C_ULNG: {
 704             // long and unsigned long
 705             *size = sizeof(long);
 706             *alignment = __alignof(long);
 707             break;
 708         }
 709         case _C_LNG_LNG:
 710         case _C_ULNG_LNG: {
 711             // long long and unsigned long long
 712             *size = sizeof(long long);
 713             *alignment = __alignof(long long);
 714             break;
 715         }
 716         case _C_VECTOR: {
 717             // vector
 718             *size = 16;
 719             *alignment = 16;
 720             break;
 721         }
 722         case _C_FLT: {
 723             // float
 724             *size = sizeof(float);
 725             *alignment = __alignof(float);
 726             break;
 727         }
 728         case _C_DBL: {
 729             // double
 730             *size = sizeof(double);
 731             *alignment = __alignof(double);
 732             break;
 733         }
 734         case _C_BFLD: {
 735             // bit field
 736
 737             // get number of bits in bit field (advance type string)
 738             long lng = strtol(type, &type, 10);
 739
 740             // while next type is a bit field
 741             while (*type == _C_BFLD) {
 742                 // skip over _C_BFLD
 743                 type++;
 744
 745                 // get next bit field length
 746                 long next_lng = strtol(type, &type, 10);
 747
 748                 // if spans next word then align to next word
 749                 if ((lng & ~31) != ((lng + next_lng) & ~31)) lng = (lng + 31) & ~31;
 750
 751                 // increment running length
 752                 lng += next_lng;
 753
 754                 // skip over potential field name
 755                 type = skip_ivar_type_name(type);
 756             }
 757
 758             // determine number of bytes bits represent
 759             *size = (lng + 7) / 8;
 760
 761             // byte alignment
 762             *alignment = __alignof(char);
 763             break;
 764         }
 765         case _C_BOOL: {
 766             // double
 767             *size = sizeof(BOOL);
 768             *alignment = __alignof(BOOL);
 769             break;
 770         }
 771         case _C_VOID: {
 772             // skip void types
 773             *size = 0;
 774             *alignment = __alignof(char);
 775             break;
 776         }
 777         case _C_UNDEF: {
 778             *size = 0;
 779             *alignment = __alignof(char);
 780             break;
 781         }
 782         default: {
 783             // unhandled type
 784             _objc_fatal("unrecognized character \'%c\' in ivar type: \"%s\"", ch, full_type);
 785         }
 786     }
 787
 788     return type;
 789 }
 790
 791
 792 /**********************************************************************
 793 * scan_ivar_type_for_layout
 794 *
 795 * Scan an ivar type string looking for references.  The offset indicates
 796 * where the ivar begins.  bits is a byte array of size bits_size used to
 797 * contain the references bit map.  next_offset is the offset beyond the
 798 * ivar.  Returns the remaining string.
 799 *
 800 **********************************************************************/
 801 static char *scan_ivar_type_for_layout(char *type, long offset, long bits_size, unsigned char *bits, long *next_offset) {
 802     long size;                                   // size of a basic type
 803     long alignment;                              // alignment of the basic type
 804     bool is_reference;                      // true if the type indicates a reference to a garbage collected object
 805
 806     // get the first character
 807     char ch = *type;
 808
 809     // GCC 4 uses for const type*.
 810     if (ch == _C_CONST) ch = *++type;
 811
 812     // act on first character
 813     switch (ch) {
 814         case _C_ARY_B: {
 815             // array type
 816
 817             // get the array length
 818             long lng = strtol(type + 1, &type, 10);
 819
 820             // next type will be where to advance the type string once the array is processed
 821             char *next_type = type;
 822
 823             // repeat the next type x lng
 824             if (!lng) {
 825                 next_type = scan_ivar_type_for_layout(type, 0, 0, NULL, &offset);
 826             } else {
 827                 while (lng--) {
 828                     // repeatedly scan the same type
 829                     next_type = scan_ivar_type_for_layout(type, offset, bits_size, bits, &offset);
 830                 }
 831             }
 832
 833             // advance the type now
 834             type = next_type;
 835
 836             // after the end of the array
 837             *next_offset = offset;
 838
 839             // advance over closing bracket
 840             if (*type == _C_ARY_E) type++;
 841             else                   _objc_inform("missing \'%c\' in ivar type.", _C_ARY_E);
 842
 843             break;
 844         }
 845         case _C_UNION_B: {
 846             // union type
 847
 848             // skip over possible union name
 849             type = skip_ivar_struct_name(type + 1);
 850
 851             // need to accumulate the maximum element offset
 852             long max_offset = 0;
 853
 854             // while not closing paren
 855             while ((ch = *type) && ch != _C_UNION_E) {
 856                 // skip over potential field name
 857                 type = skip_ivar_type_name(type);
 858
 859                 // scan type
 860                 long union_offset;
 861                 type = scan_ivar_type_for_layout(type, offset, bits_size, bits, &union_offset);
 862
 863                 // adjust the maximum element offset
 864                 if (max_offset < union_offset) max_offset = union_offset;
 865             }
 866
 867             // after the largest element
 868             *next_offset = max_offset;
 869
 870             // advance over closing paren
 871             if (ch == _C_UNION_E) {
 872               type++;
 873             } else {
 874               _objc_inform("missing \'%c\' in ivar type", _C_UNION_E);
 875             }
 876
 877             break;
 878         }
 879         case _C_STRUCT_B: {
 880             // struct type
 881
 882             // skip over possible struct name
 883             type = skip_ivar_struct_name(type + 1);
 884
 885             // while not closing brace
 886             while ((ch = *type) && ch != _C_STRUCT_E) {
 887                 // skip over potential field name
 888                 type = skip_ivar_type_name(type);
 889
 890                 // scan type
 891                 type = scan_ivar_type_for_layout(type, offset, bits_size, bits, &offset);
 892             }
 893
 894             // after the end of the struct
 895             *next_offset = offset;
 896
 897             // advance over closing brace
 898             if (ch == _C_STRUCT_E) type++;
 899             else                   _objc_inform("missing \'%c\' in ivar type", _C_STRUCT_E);
 900
 901             break;
 902         }
 903         default: {
 904             // basic type
 905
 906             // scan type
 907             type = scan_basic_ivar_type(type, &size, &alignment, &is_reference);
 908
 909             // create alignment mask
 910             alignment--;
 911
 912             // align offset
 913             offset = (offset + alignment) & ~alignment;
 914
 915             // if is a reference then mark in the bit map
 916             if (is_reference) mark_offset_for_layout(offset, bits_size, bits);
 917
 918             // after the basic type
 919             *next_offset = offset + size;
 920             break;
 921         }
 922     }
 923
 924     // return remainder of type string
 925     return type;
 926 }
 927
 928 #endif