src/compiler/dmd/lifetime.d

   1 /**
   2  * This module contains all functions related to an object's lifetime:
   3  * allocation, resizing, deallocation, and finalization.
   4  *
   5  * Copyright: Copyright (C) 2004-2007 Digital Mars, www.digitalmars.com.
   6  *            All rights reserved.
   7  * License:
   8  *  This software is provided 'as-is', without any express or implied
   9  *  warranty. In no event will the authors be held liable for any damages
  10  *  arising from the use of this software.
  11  *
  12  *  Permission is granted to anyone to use this software for any purpose,
  13  *  including commercial applications, and to alter it and redistribute it
  14  *  freely, in both source and binary form, subject to the following
  15  *  restrictions:
  16  *
  17  *  o  The origin of this software must not be misrepresented; you must not
  18  *     claim that you wrote the original software. If you use this software
  19  *     in a product, an acknowledgment in the product documentation would be
  20  *     appreciated but is not required.
  21  *  o  Altered source versions must be plainly marked as such, and must not
  22  *     be misrepresented as being the original software.
  23  *  o  This notice may not be removed or altered from any source
  24  *     distribution.
  25  * Authors:   Walter Bright, Sean Kelly
  26  */
  27 module rt.lifetime;
  28
  29
  30 private
  31 {
  32     import stdc.stdlib;
  33     import stdc.string;
  34     import stdc.stdarg;
  35     debug(PRINTF) import stdc.stdio;
  36 }
  37
  38
  39 private
  40 {
  41     enum BlkAttr : uint
  42     {
  43         FINALIZE = 0b0000_0001,
  44         NO_SCAN  = 0b0000_0010,
  45         NO_MOVE  = 0b0000_0100,
  46         ALL_BITS = 0b1111_1111
  47     }
  48
  49     struct BlkInfo
  50     {
  51         void*  base;
  52         size_t size;
  53         uint   attr;
  54     }
  55
  56     extern (C) uint gc_getAttr( void* p );
  57     extern (C) uint gc_setAttr( void* p, uint a );
  58     extern (C) uint gc_clrAttr( void* p, uint a );
  59
  60     extern (C) void*  gc_malloc( size_t sz, uint ba = 0 );
  61     extern (C) void*  gc_calloc( size_t sz, uint ba = 0 );
  62     extern (C) size_t gc_extend( void* p, size_t mx, size_t sz );
  63     extern (C) void   gc_free( void* p );
  64
  65     extern (C) void*   gc_addrOf( void* p );
  66     extern (C) size_t  gc_sizeOf( void* p );
  67     extern (C) BlkInfo gc_query( void* p );
  68
  69     extern (C) void onFinalizeError( ClassInfo c, Exception e );
  70     extern (C) void onOutOfMemoryError();
  71
  72     extern (C) void _d_monitordelete(Object h, bool det = true);
  73
  74     enum
  75     {
  76         PAGESIZE = 4096
  77     }
  78
  79     alias bool function(Object) CollectHandler;
  80     CollectHandler collectHandler = null;
  81 }
  82
  83
  84 /**
  85  *
  86  */
  87 extern (C) Object _d_newclass(ClassInfo ci)
  88 {
  89     void* p;
  90
  91     debug(PRINTF) printf("_d_newclass(ci = %p, %s)\n", ci, cast(char *)ci.name);
  92     if (ci.flags & 1) // if COM object
  93     {   /* COM objects are not garbage collected, they are reference counted
  94          * using AddRef() and Release().  They get free'd by C's free()
  95          * function called by Release() when Release()'s reference count goes
  96          * to zero.
  97      */
  98         p = malloc(ci.init.length);
  99         if (!p)
 100             onOutOfMemoryError();
 101     }
 102     else
 103     {
 104         p = gc_malloc(ci.init.length,
 105                       BlkAttr.FINALIZE | (ci.flags & 2 ? BlkAttr.NO_SCAN : 0));
 106         debug(PRINTF) printf(" p = %p\n", p);
 107     }
 108
 109     debug(PRINTF)
 110     {
 111         printf("p = %p\n", p);
 112         printf("ci = %p, ci.init = %p, len = %d\n", ci, ci.init, ci.init.length);
 113         printf("vptr = %p\n", *cast(void**) ci.init);
 114         printf("vtbl[0] = %p\n", (*cast(void***) ci.init)[0]);
 115         printf("vtbl[1] = %p\n", (*cast(void***) ci.init)[1]);
 116         printf("init[0] = %x\n", (cast(uint*) ci.init)[0]);
 117         printf("init[1] = %x\n", (cast(uint*) ci.init)[1]);
 118         printf("init[2] = %x\n", (cast(uint*) ci.init)[2]);
 119         printf("init[3] = %x\n", (cast(uint*) ci.init)[3]);
 120         printf("init[4] = %x\n", (cast(uint*) ci.init)[4]);
 121     }
 122
 123     // initialize it
 124     (cast(byte*) p)[0 .. ci.init.length] = ci.init[];
 125
 126     debug(PRINTF) printf("initialization done\n");
 127     return cast(Object) p;
 128 }
 129
 130
 131 /**
 132  *
 133  */
 134 extern (C) void _d_delinterface(void** p)
 135 {
 136     if (*p)
 137     {
 138         Interface* pi = **cast(Interface ***)*p;
 139         Object     o  = cast(Object)(*p - pi.offset);
 140
 141         _d_delclass(&o);
 142         *p = null;
 143     }
 144 }
 145
 146
 147 // used for deletion
 148 private extern (D) alias void (*fp_t)(Object);
 149
 150
 151 /**
 152  *
 153  */
 154 extern (C) void _d_delclass(Object* p)
 155 {
 156     if (*p)
 157     {
 158         debug(PRINTF) printf("_d_delclass(%p)\n", *p);
 159
 160         ClassInfo **pc = cast(ClassInfo **)*p;
 161         if (*pc)
 162         {
 163             ClassInfo c = **pc;
 164
 165             rt_finalize(cast(void*) *p);
 166
 167             if (c.deallocator)
 168             {
 169                 fp_t fp = cast(fp_t)c.deallocator;
 170                 (*fp)(*p); // call deallocator
 171                 *p = null;
 172                 return;
 173             }
 174         }
 175         else
 176         {
 177             rt_finalize(cast(void*) *p);
 178         }
 179         gc_free(cast(void*) *p);
 180         *p = null;
 181     }
 182 }
 183
 184
 185 /**
 186  * Allocate a new array of length elements.
 187  * ti is the type of the resulting array, or pointer to element.
 188  * (For when the array is initialized to 0)
 189  */
 190 extern (C) ulong _d_newarrayT(TypeInfo ti, size_t length)
 191 {
 192     void* p;
 193     ulong result;
 194     auto size = ti.next.tsize();                // array element size
 195
 196     debug(PRINTF) printf("_d_newarrayT(length = x%x, size = %d)\n", length, size);
 197     if (length == 0 || size == 0)
 198         result = 0;
 199     else
 200     {
 201         version (D_InlineAsm_X86)
 202         {
 203             asm
 204             {
 205                 mov     EAX,size        ;
 206                 mul     EAX,length      ;
 207                 mov     size,EAX        ;
 208                 jc      Loverflow       ;
 209             }
 210         }
 211         else
 212             size *= length;
 213         p = gc_malloc(size + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
 214         debug(PRINTF) printf(" p = %p\n", p);
 215         memset(p, 0, size);
 216         result = cast(ulong)length + (cast(ulong)cast(uint)p << 32);
 217     }
 218     return result;
 219
 220 Loverflow:
 221     onOutOfMemoryError();
 222 }
 223
 224 /**
 225  * For when the array has a non-zero initializer.
 226  */
 227 extern (C) ulong _d_newarrayiT(TypeInfo ti, size_t length)
 228 {
 229     ulong result;
 230     auto size = ti.next.tsize();                // array element size
 231
 232     debug(PRINTF) printf("_d_newarrayiT(length = %d, size = %d)\n", length, size);
 233
 234     if (length == 0 || size == 0)
 235         result = 0;
 236     else
 237     {
 238         auto initializer = ti.next.init();
 239         auto isize = initializer.length;
 240         auto q = initializer.ptr;
 241         version (D_InlineAsm_X86)
 242         {
 243             asm
 244             {
 245                 mov     EAX,size        ;
 246                 mul     EAX,length      ;
 247                 mov     size,EAX        ;
 248                 jc      Loverflow       ;
 249             }
 250         }
 251         else
 252             size *= length;
 253         auto p = gc_malloc(size + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
 254         debug(PRINTF) printf(" p = %p\n", p);
 255         if (isize == 1)
 256             memset(p, *cast(ubyte*)q, size);
 257         else if (isize == int.sizeof)
 258         {
 259             int init = *cast(int*)q;
 260             size /= int.sizeof;
 261             for (size_t u = 0; u < size; u++)
 262             {
 263                 (cast(int*)p)[u] = init;
 264             }
 265         }
 266         else
 267         {
 268             for (size_t u = 0; u < size; u += isize)
 269             {
 270                 memcpy(p + u, q, isize);
 271             }
 272         }
 273         va_end(q);
 274         result = cast(ulong)length + (cast(ulong)cast(uint)p << 32);
 275     }
 276     return result;
 277
 278 Loverflow:
 279     onOutOfMemoryError();
 280 }
 281
 282 /**
 283  *
 284  */
 285 extern (C) ulong _d_newarraymT(TypeInfo ti, int ndims, ...)
 286 {
 287     ulong result;
 288
 289     debug(PRINTF) printf("_d_newarraymT(ndims = %d)\n", ndims);
 290     if (ndims == 0)
 291         result = 0;
 292     else
 293     {   va_list q;
 294         va_start!(int)(q, ndims);
 295
 296         void[] foo(TypeInfo ti, size_t* pdim, int ndims)
 297         {
 298             size_t dim = *pdim;
 299             void[] p;
 300
 301             debug(PRINTF) printf("foo(ti = %p, ti.next = %p, dim = %d, ndims = %d\n", ti, ti.next, dim, ndims);
 302             if (ndims == 1)
 303             {
 304                 auto r = _d_newarrayT(ti, dim);
 305                 p = *cast(void[]*)(&r);
 306             }
 307             else
 308             {
 309                 p = gc_malloc(dim * (void[]).sizeof + 1)[0 .. dim];
 310                 for (int i = 0; i < dim; i++)
 311                 {
 312                     (cast(void[]*)p.ptr)[i] = foo(ti.next, pdim + 1, ndims - 1);
 313                 }
 314             }
 315             return p;
 316         }
 317
 318         size_t* pdim = cast(size_t *)q;
 319         result = cast(ulong)foo(ti, pdim, ndims);
 320         debug(PRINTF) printf("result = %llx\n", result);
 321
 322         version (none)
 323         {
 324             for (int i = 0; i < ndims; i++)
 325             {
 326                 printf("index %d: %d\n", i, va_arg!(int)(q));
 327             }
 328         }
 329         va_end(q);
 330     }
 331     return result;
 332 }
 333
 334
 335 /**
 336  *
 337  */
 338 extern (C) ulong _d_newarraymiT(TypeInfo ti, int ndims, ...)
 339 {
 340     ulong result;
 341
 342     debug(PRINTF) printf("_d_newarraymiT(ndims = %d)\n", ndims);
 343     if (ndims == 0)
 344         result = 0;
 345     else
 346     {
 347         va_list q;
 348         va_start!(int)(q, ndims);
 349
 350         void[] foo(TypeInfo ti, size_t* pdim, int ndims)
 351         {
 352             size_t dim = *pdim;
 353             void[] p;
 354
 355             if (ndims == 1)
 356             {
 357                 auto r = _d_newarrayiT(ti, dim);
 358                 p = *cast(void[]*)(&r);
 359             }
 360             else
 361             {
 362                 p = gc_malloc(dim * (void[]).sizeof + 1)[0 .. dim];
 363                 for (int i = 0; i < dim; i++)
 364                 {
 365                     (cast(void[]*)p.ptr)[i] = foo(ti.next, pdim + 1, ndims - 1);
 366                 }
 367             }
 368             return p;
 369         }
 370
 371         size_t* pdim = cast(size_t *)q;
 372         result = cast(ulong)foo(ti, pdim, ndims);
 373         debug(PRINTF) printf("result = %llx\n", result);
 374
 375         version (none)
 376         {
 377             for (int i = 0; i < ndims; i++)
 378             {
 379                 printf("index %d: %d\n", i, va_arg!(int)(q));
 380                 printf("init = %d\n", va_arg!(int)(q));
 381             }
 382         }
 383         va_end(q);
 384     }
 385     return result;
 386 }
 387
 388
 389 /**
 390  *
 391  */
 392 struct Array
 393 {
 394     size_t length;
 395     byte*  data;
 396 }
 397
 398
 399 /**
 400  *
 401  */
 402 void* _d_allocmemory(size_t nbytes)
 403 {
 404     return gc_malloc(nbytes);
 405 }
 406
 407
 408 /**
 409  *
 410  */
 411 extern (C) void _d_delarray(Array *p)
 412 {
 413     if (p)
 414     {
 415         assert(!p.length || p.data);
 416
 417         if (p.data)
 418             gc_free(p.data);
 419         p.data = null;
 420         p.length = 0;
 421     }
 422 }
 423
 424
 425 /**
 426  *
 427  */
 428 extern (C) void _d_delmemory(void* *p)
 429 {
 430     if (*p)
 431     {
 432         gc_free(*p);
 433         *p = null;
 434     }
 435 }
 436
 437
 438 /**
 439  *
 440  */
 441 extern (C) void _d_callinterfacefinalizer(void *p)
 442 {
 443     if (p)
 444     {
 445         Interface *pi = **cast(Interface ***)p;
 446         Object o = cast(Object)(p - pi.offset);
 447         rt_finalize(cast(void*)o);
 448     }
 449 }
 450
 451
 452 /**
 453  *
 454  */
 455 extern (C) void _d_callfinalizer(void* p)
 456 {
 457     rt_finalize( p );
 458 }
 459
 460
 461 /**
 462  *
 463  */
 464 extern (C) void  rt_setCollectHandler(CollectHandler h)
 465 {
 466     collectHandler = h;
 467 }
 468
 469
 470 /**
 471  *
 472  */
 473 extern (C) void rt_finalize(void* p, bool det = true)
 474 {
 475     debug(PRINTF) printf("rt_finalize(p = %p)\n", p);
 476
 477     if (p) // not necessary if called from gc
 478     {
 479         ClassInfo** pc = cast(ClassInfo**)p;
 480
 481         if (*pc)
 482         {
 483             ClassInfo c = **pc;
 484
 485             try
 486             {
 487                 if (det || collectHandler is null || collectHandler(cast(Object)p))
 488                 {
 489                     do
 490                     {
 491                         if (c.destructor)
 492                         {
 493                             fp_t fp = cast(fp_t)c.destructor;
 494                             (*fp)(cast(Object)p); // call destructor
 495                         }
 496                         c = c.base;
 497                     } while (c);
 498                 }
 499                 if ((cast(void**)p)[1]) // if monitor is not null
 500                     _d_monitordelete(cast(Object)p, det);
 501             }
 502             catch (Exception e)
 503             {
 504                 onFinalizeError(**pc, e);
 505             }
 506             finally
 507             {
 508                 *pc = null; // zero vptr
 509             }
 510         }
 511     }
 512 }
 513
 514
 515 /**
 516  * Resize dynamic arrays with 0 initializers.
 517  */
 518 extern (C) byte[] _d_arraysetlengthT(TypeInfo ti, size_t newlength, Array *p)
 519 in
 520 {
 521     assert(ti);
 522     assert(!p.length || p.data);
 523 }
 524 body
 525 {
 526     byte* newdata;
 527     size_t sizeelem = ti.next.tsize();
 528
 529     debug(PRINTF)
 530     {
 531         printf("_d_arraysetlengthT(p = %p, sizeelem = %d, newlength = %d)\n", p, sizeelem, newlength);
 532         if (p)
 533             printf("\tp.data = %p, p.length = %d\n", p.data, p.length);
 534     }
 535
 536     if (newlength)
 537     {
 538         version (D_InlineAsm_X86)
 539         {
 540             size_t newsize = void;
 541
 542             asm
 543             {
 544                 mov EAX, newlength;
 545                 mul EAX, sizeelem;
 546                 mov newsize, EAX;
 547                 jc  Loverflow;
 548             }
 549         }
 550         else
 551         {
 552             size_t newsize = sizeelem * newlength;
 553
 554             if (newsize / newlength != sizeelem)
 555                 goto Loverflow;
 556         }
 557
 558         debug(PRINTF) printf("newsize = %x, newlength = %x\n", newsize, newlength);
 559
 560         if (p.data)
 561         {
 562             newdata = p.data;
 563             if (newlength > p.length)
 564             {
 565                 size_t size = p.length * sizeelem;
 566                 auto   info = gc_query(p.data);
 567
 568                 if (info.size <= newsize || info.base != p.data)
 569                 {
 570                     if (info.size >= PAGESIZE && info.base == p.data)
 571                     {   // Try to extend in-place
 572                         auto u = gc_extend(p.data, (newsize + 1) - info.size, (newsize + 1) - info.size);
 573                         if (u)
 574                         {
 575                             goto L1;
 576                         }
 577                     }
 578                     newdata = cast(byte *)gc_malloc(newsize + 1, info.attr);
 579                     newdata[0 .. size] = p.data[0 .. size];
 580                 }
 581              L1:
 582                 newdata[size .. newsize] = 0;
 583             }
 584         }
 585         else
 586         {
 587             newdata = cast(byte *)gc_calloc(newsize + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
 588         }
 589     }
 590     else
 591     {
 592         newdata = p.data;
 593     }
 594
 595     p.data = newdata;
 596     p.length = newlength;
 597     return newdata[0 .. newlength];
 598
 599 Loverflow:
 600     onOutOfMemoryError();
 601 }
 602
 603
 604 /**
 605  * Resize arrays for non-zero initializers.
 606  *      p               pointer to array lvalue to be updated
 607  *      newlength       new .length property of array
 608  *      sizeelem        size of each element of array
 609  *      initsize        size of initializer
 610  *      ...             initializer
 611  */
 612 extern (C) byte[] _d_arraysetlengthiT(TypeInfo ti, size_t newlength, Array *p)
 613 in
 614 {
 615     assert(!p.length || p.data);
 616 }
 617 body
 618 {
 619     byte* newdata;
 620     size_t sizeelem = ti.next.tsize();
 621     void[] initializer = ti.next.init();
 622     size_t initsize = initializer.length;
 623
 624     assert(sizeelem);
 625     assert(initsize);
 626     assert(initsize <= sizeelem);
 627     assert((sizeelem / initsize) * initsize == sizeelem);
 628
 629     debug(PRINTF)
 630     {
 631         printf("_d_arraysetlengthiT(p = %p, sizeelem = %d, newlength = %d, initsize = %d)\n", p, sizeelem, newlength, initsize);
 632         if (p)
 633             printf("\tp.data = %p, p.length = %d\n", p.data, p.length);
 634     }
 635
 636     if (newlength)
 637     {
 638         version (D_InlineAsm_X86)
 639         {
 640             size_t newsize = void;
 641
 642             asm
 643             {
 644                 mov     EAX,newlength   ;
 645                 mul     EAX,sizeelem    ;
 646                 mov     newsize,EAX     ;
 647                 jc      Loverflow       ;
 648             }
 649         }
 650         else
 651         {
 652             size_t newsize = sizeelem * newlength;
 653
 654             if (newsize / newlength != sizeelem)
 655                 goto Loverflow;
 656         }
 657         debug(PRINTF) printf("newsize = %x, newlength = %x\n", newsize, newlength);
 658
 659         size_t size = p.length * sizeelem;
 660
 661         if (p.data)
 662         {
 663             newdata = p.data;
 664             if (newlength > p.length)
 665             {
 666                 auto info = gc_query(p.data);
 667
 668                 if (info.size <= newsize || info.base != p.data)
 669                 {
 670                     if (info.size >= PAGESIZE && info.base == p.data)
 671                     {   // Try to extend in-place
 672                         auto u = gc_extend(p.data, (newsize + 1) - info.size, (newsize + 1) - info.size);
 673                         if (u)
 674                         {
 675                             goto L1;
 676                         }
 677                     }
 678                     newdata = cast(byte *)gc_malloc(newsize + 1, info.attr);
 679                     newdata[0 .. size] = p.data[0 .. size];
 680                 L1: ;
 681                 }
 682             }
 683         }
 684         else
 685         {
 686             newdata = cast(byte *)gc_malloc(newsize + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
 687         }
 688
 689         auto q = initializer.ptr; // pointer to initializer
 690
 691         if (newsize > size)
 692         {
 693             if (initsize == 1)
 694             {
 695                 debug(PRINTF) printf("newdata = %p, size = %d, newsize = %d, *q = %d\n", newdata, size, newsize, *cast(byte*)q);
 696                 newdata[size .. newsize] = *(cast(byte*)q);
 697             }
 698             else
 699             {
 700                 for (size_t u = size; u < newsize; u += initsize)
 701                 {
 702                     memcpy(newdata + u, q, initsize);
 703                 }
 704             }
 705         }
 706     }
 707     else
 708     {
 709         newdata = p.data;
 710     }
 711
 712     p.data = newdata;
 713     p.length = newlength;
 714     return newdata[0 .. newlength];
 715
 716 Loverflow:
 717     onOutOfMemoryError();
 718 }
 719
 720
 721 /**
 722  * Append y[] to array x[].
 723  * size is size of each array element.
 724  */
 725 extern (C) long _d_arrayappendT(TypeInfo ti, Array *px, byte[] y)
 726 {
 727     auto sizeelem = ti.next.tsize();            // array element size
 728     auto info = gc_query(px.data);
 729     auto length = px.length;
 730     auto newlength = length + y.length;
 731     auto newsize = newlength * sizeelem;
 732
 733     if (info.size < newsize || info.base != px.data)
 734     {   byte* newdata;
 735
 736         if (info.size >= PAGESIZE && info.base == px.data)
 737         {   // Try to extend in-place
 738             auto u = gc_extend(px.data, (newsize + 1) - info.size, (newsize + 1) - info.size);
 739             if (u)
 740             {
 741                 goto L1;
 742             }
 743         }
 744         newdata = cast(byte *)gc_malloc(newCapacity(newlength, sizeelem) + 1, info.attr);
 745         memcpy(newdata, px.data, length * sizeelem);
 746         px.data = newdata;
 747     }
 748   L1:
 749     px.length = newlength;
 750     memcpy(px.data + length * sizeelem, y.ptr, y.length * sizeelem);
 751     return *cast(long*)px;
 752 }
 753
 754
 755 /**
 756  *
 757  */
 758 size_t newCapacity(size_t newlength, size_t size)
 759 {
 760     version(none)
 761     {
 762         size_t newcap = newlength * size;
 763     }
 764     else
 765     {
 766         /*
 767          * Better version by Dave Fladebo:
 768          * This uses an inverse logorithmic algorithm to pre-allocate a bit more
 769          * space for larger arrays.
 770          * - Arrays smaller than PAGESIZE bytes are left as-is, so for the most
 771          * common cases, memory allocation is 1 to 1. The small overhead added
 772          * doesn't affect small array perf. (it's virtually the same as
 773          * current).
 774          * - Larger arrays have some space pre-allocated.
 775          * - As the arrays grow, the relative pre-allocated space shrinks.
 776          * - The logorithmic algorithm allocates relatively more space for
 777          * mid-size arrays, making it very fast for medium arrays (for
 778          * mid-to-large arrays, this turns out to be quite a bit faster than the
 779          * equivalent realloc() code in C, on Linux at least. Small arrays are
 780          * just as fast as GCC).
 781          * - Perhaps most importantly, overall memory usage and stress on the GC
 782          * is decreased significantly for demanding environments.
 783          */
 784         size_t newcap = newlength * size;
 785         size_t newext = 0;
 786
 787         if (newcap > PAGESIZE)
 788         {
 789             //double mult2 = 1.0 + (size / log10(pow(newcap * 2.0,2.0)));
 790
 791             // redo above line using only integer math
 792
 793             static int log2plus1(size_t c)
 794             {   int i;
 795
 796                 if (c == 0)
 797                     i = -1;
 798                 else
 799                     for (i = 1; c >>= 1; i++)
 800                     {
 801                     }
 802                 return i;
 803             }
 804
 805             /* The following setting for mult sets how much bigger
 806              * the new size will be over what is actually needed.
 807              * 100 means the same size, more means proportionally more.
 808              * More means faster but more memory consumption.
 809              */
 810             //long mult = 100 + (1000L * size) / (6 * log2plus1(newcap));
 811             long mult = 100 + (1000L * size) / log2plus1(newcap);
 812
 813             // testing shows 1.02 for large arrays is about the point of diminishing return
 814             if (mult < 102)
 815                 mult = 102;
 816             newext = cast(size_t)((newcap * mult) / 100);
 817             newext -= newext % size;
 818             debug(PRINTF) printf("mult: %2.2f, alloc: %2.2f\n",mult/100.0,newext / cast(double)size);
 819         }
 820         newcap = newext > newcap ? newext : newcap;
 821         debug(PRINTF) printf("newcap = %d, newlength = %d, size = %d\n", newcap, newlength, size);
 822     }
 823     return newcap;
 824 }
 825
 826
 827 /**
 828  *
 829  */
 830 extern (C) byte[] _d_arrayappendcT(TypeInfo ti, inout byte[] x, ...)
 831 {
 832     auto sizeelem = ti.next.tsize();            // array element size
 833     auto info = gc_query(x.ptr);
 834     auto length = x.length;
 835     auto newlength = length + 1;
 836     auto newsize = newlength * sizeelem;
 837
 838     assert(info.size == 0 || length * sizeelem <= info.size);
 839
 840     debug(PRINTF) printf("_d_arrayappendcT(sizeelem = %d, ptr = %p, length = %d, cap = %d)\n", sizeelem, x.ptr, x.length, info.size);
 841
 842     if (info.size <= newsize || info.base != x.ptr)
 843     {   byte* newdata;
 844
 845         if (info.size >= PAGESIZE && info.base == x.ptr)
 846         {   // Try to extend in-place
 847             auto u = gc_extend(x.ptr, (newsize + 1) - info.size, (newsize + 1) - info.size);
 848             if (u)
 849             {
 850                 goto L1;
 851             }
 852         }
 853         debug(PRINTF) printf("_d_arrayappendcT(length = %d, newlength = %d, cap = %d)\n", length, newlength, info.size);
 854         auto newcap = newCapacity(newlength, sizeelem);
 855         assert(newcap >= newlength * sizeelem);
 856         newdata = cast(byte *)gc_malloc(newcap + 1, info.attr);
 857         memcpy(newdata, x.ptr, length * sizeelem);
 858         (cast(void**)(&x))[1] = newdata;
 859     }
 860   L1:
 861     byte *argp = cast(byte *)(&ti + 2);
 862
 863     *cast(size_t *)&x = newlength;
 864     x.ptr[length * sizeelem .. newsize] = argp[0 .. sizeelem];
 865     assert((cast(size_t)x.ptr & 15) == 0);
 866     assert(gc_sizeOf(x.ptr) > x.length * sizeelem);
 867     return x;
 868 }
 869
 870
 871 /**
 872  *
 873  */
 874 extern (C) byte[] _d_arraycatT(TypeInfo ti, byte[] x, byte[] y)
 875 out (result)
 876 {
 877     auto sizeelem = ti.next.tsize();            // array element size
 878     debug(PRINTF) printf("_d_arraycatT(%d,%p ~ %d,%p sizeelem = %d => %d,%p)\n", x.length, x.ptr, y.length, y.ptr, sizeelem, result.length, result.ptr);
 879     assert(result.length == x.length + y.length);
 880     for (size_t i = 0; i < x.length * sizeelem; i++)
 881         assert((cast(byte*)result)[i] == (cast(byte*)x)[i]);
 882     for (size_t i = 0; i < y.length * sizeelem; i++)
 883         assert((cast(byte*)result)[x.length * sizeelem + i] == (cast(byte*)y)[i]);
 884
 885     size_t cap = gc_sizeOf(result.ptr);
 886     assert(!cap || cap > result.length * sizeelem);
 887 }
 888 body
 889 {
 890     version (none)
 891     {
 892         /* Cannot use this optimization because:
 893          *  char[] a, b;
 894          *  char c = 'a';
 895          *  b = a ~ c;
 896          *  c = 'b';
 897          * will change the contents of b.
 898          */
 899         if (!y.length)
 900             return x;
 901         if (!x.length)
 902             return y;
 903     }
 904
 905     debug(PRINTF) printf("_d_arraycatT(%d,%p ~ %d,%p)\n", x.length, x.ptr, y.length, y.ptr);
 906     auto sizeelem = ti.next.tsize();            // array element size
 907     debug(PRINTF) printf("_d_arraycatT(%d,%p ~ %d,%p sizeelem = %d)\n", x.length, x.ptr, y.length, y.ptr, sizeelem);
 908     size_t xlen = x.length * sizeelem;
 909     size_t ylen = y.length * sizeelem;
 910     size_t len  = xlen + ylen;
 911
 912     if (!len)
 913         return null;
 914
 915     byte* p = cast(byte*)gc_malloc(len + 1, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
 916     memcpy(p, x.ptr, xlen);
 917     memcpy(p + xlen, y.ptr, ylen);
 918     p[len] = 0;
 919     return p[0 .. x.length + y.length];
 920 }
 921
 922
 923 /**
 924  *
 925  */
 926 extern (C) byte[] _d_arraycatnT(TypeInfo ti, uint n, ...)
 927 {   void* a;
 928     size_t length;
 929     byte[]* p;
 930     uint i;
 931     byte[] b;
 932     auto size = ti.next.tsize(); // array element size
 933
 934     p = cast(byte[]*)(&n + 1);
 935
 936     for (i = 0; i < n; i++)
 937     {
 938         b = *p++;
 939         length += b.length;
 940     }
 941     if (!length)
 942         return null;
 943
 944     a = gc_malloc(length * size, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
 945     p = cast(byte[]*)(&n + 1);
 946
 947     uint j = 0;
 948     for (i = 0; i < n; i++)
 949     {
 950         b = *p++;
 951         if (b.length)
 952         {
 953             memcpy(a + j, b.ptr, b.length * size);
 954             j += b.length * size;
 955         }
 956     }
 957
 958     byte[] result;
 959     *cast(int *)&result = length;       // jam length
 960     (cast(void **)&result)[1] = a;      // jam ptr
 961     return result;
 962 }
 963
 964
 965 /**
 966  *
 967  */
 968 extern (C) void* _d_arrayliteralT(TypeInfo ti, size_t length, ...)
 969 {
 970     auto sizeelem = ti.next.tsize();            // array element size
 971     void* result;
 972
 973     debug(PRINTF) printf("_d_arrayliteralT(sizeelem = %d, length = %d)\n", sizeelem, length);
 974     if (length == 0 || sizeelem == 0)
 975         result = null;
 976     else
 977     {
 978         result = gc_malloc(length * sizeelem, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
 979
 980         va_list q;
 981         va_start!(size_t)(q, length);
 982
 983         size_t stacksize = (sizeelem + int.sizeof - 1) & ~(int.sizeof - 1);
 984
 985         if (stacksize == sizeelem)
 986         {
 987             memcpy(result, q, length * sizeelem);
 988         }
 989         else
 990         {
 991             for (size_t i = 0; i < length; i++)
 992             {
 993                 memcpy(result + i * sizeelem, q, sizeelem);
 994                 q += stacksize;
 995             }
 996         }
 997
 998         va_end(q);
 999     }
1000     return result;
1001 }
1002
1003
1004 /**
1005  * Support for array.dup property.
1006  */
1007 struct Array2
1008 {
1009     size_t length;
1010     void*  ptr;
1011 }
1012
1013
1014 /**
1015  *
1016  */
1017 extern (C) long _adDupT(TypeInfo ti, Array2 a)
1018 out (result)
1019 {
1020     auto sizeelem = ti.next.tsize();            // array element size
1021     assert(memcmp((*cast(Array2*)&result).ptr, a.ptr, a.length * sizeelem) == 0);
1022 }
1023 body
1024 {
1025     Array2 r;
1026
1027     if (a.length)
1028     {
1029         auto sizeelem = ti.next.tsize();                // array element size
1030         auto size = a.length * sizeelem;
1031         r.ptr = gc_malloc(size, !(ti.next.flags() & 1) ? BlkAttr.NO_SCAN : 0);
1032         r.length = a.length;
1033         memcpy(r.ptr, a.ptr, size);
1034     }
1035     return *cast(long*)(&r);
1036 }
1037
1038
1039 unittest
1040 {
1041     int[] a;
1042     int[] b;
1043     int i;
1044
1045     a = new int[3];
1046     a[0] = 1; a[1] = 2; a[2] = 3;
1047     b = a.dup;
1048     assert(b.length == 3);
1049     for (i = 0; i < 3; i++)
1050         assert(b[i] == i + 1);
1051 }