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