singrdk/base/Imported/Bartok/runtime/shared/GCs/BumpAllocator.cs

//
// Copyright (c) Microsoft Corporation.  All rights reserved.
//

/*******************************************************************/
/*                           WARNING                               */
/* This file should be identical in the Bartok and Singularity     */
/* depots. Master copy resides in Bartok Depot. Changes should be  */
/* made to Bartok Depot and propagated to Singularity Depot.       */
/*******************************************************************/


// Conceptually, even if nothing is recorded in the offset table
// during object allocation, the offset table itself should be
// able to identify objects correctly in the execution. So as
// a stress mode to test the correctness of the offset table,
// here we can turn on the following macro to disable recording
// object allocation in the offset table.

//#define DONT_RECORD_OBJALLOC_IN_OFFSETTABLE

#define ENSURE_ALLOCATION_ALLOWED

namespace System.GCs {

    using System.Runtime.CompilerServices;
    using System.Threading;

    using Microsoft.Bartok.Options;
    using Microsoft.Bartok.Runtime;
#if SINGULARITY
    using Microsoft.Singularity;
#endif

    // Common struct for allocation pool.
    [NoCCtor]
    internal struct BumpAllocator /* : Allocator */
    {

        [RequiredByBartok]
        private UIntPtr           allocPtr; // Next allocation.
        [RequiredByBartok]
        private UIntPtr           zeroedLimit; // Limit of zeroed pool.
        private UIntPtr           reserveLimit; // Limit of reserved pool.
        private UIntPtr           allocNew; // Most recent page allocation.
        private readonly PageType pageType;

        [MixinOverride]
        private static bool CLEAR_POOL_PAGES() {
            VTable.DebugBreak();
            return false;
        }

        [MixinConditional("BumpAllocator")]
        [MixinConditional("AllThreadMixins")]
        [Mixin(typeof(Thread))]
        // Should be private, but mixin implementation will warn if visibility
        // does not match that of Thread.
        public sealed class BumpAllocatorThread : Object {
            // Thread-specific bump allocator
            [RequiredByBartok]
            internal BumpAllocator bumpAllocator;
        }

        [Inline]
        private static BumpAllocatorThread MixinThread(Thread t)
        {
            return (BumpAllocatorThread) (Object) t;
        }

        internal BumpAllocator(PageType pageType) {
            this.zeroedLimit = UIntPtr.Zero;
            this.reserveLimit = UIntPtr.Zero;
            this.allocPtr = UIntPtr.Zero;
            this.allocNew = UIntPtr.Zero;
            this.pageType = pageType;
        }

        internal void SetReservedRange(UIntPtr startAddr, UIntPtr length) {
            this.allocPtr = startAddr;
            this.reserveLimit = startAddr + length;
        }

        internal void SetZeroedRange(UIntPtr startAddr, UIntPtr length) {
            this.allocPtr = startAddr;
            this.zeroedLimit = startAddr + length;
            this.reserveLimit = startAddr + length;
        }

        internal void SetZeroedLimit(UIntPtr zeroedLimit) {
            this.zeroedLimit = zeroedLimit;
        }

        internal UIntPtr AllocPtr {
            get { return this.allocPtr; }
        }

        internal UIntPtr ZeroedLimit {
            get { return this.zeroedLimit; }
        }

        internal UIntPtr ReserveLimit {
            get { return this.reserveLimit; }
        }

        internal UIntPtr AllocNew {
            get { return this.allocNew; }
        }

        internal void Dump()
        {
#if SINGULARITY
            Tracing.Log(Tracing.Debug, "[gen={0} {1:x8}..{2:x8}..{3:x8}]",
                        (UIntPtr)unchecked((uint)this.pageType),
                        this.allocPtr, this.zeroedLimit, this.reserveLimit);
#else
            VTable.DebugPrint(" [gen={0} {1:x8}..{2:x8}..{3:x8}]\n",
                              __arglist(this.pageType, this.allocPtr,
                                        this.zeroedLimit, this.reserveLimit));
#endif
        }

        internal static void NewThreadNotification(Thread newThread,
                                                   PageType pageType)
        {
            MixinThread(newThread).bumpAllocator = new BumpAllocator(pageType);
        }

        [ManualRefCounts]
        public static UIntPtr Allocate(Thread thread,
                                       UIntPtr bytes, uint alignment)
        {
            BumpAllocatorThread mixinThread = MixinThread(thread);
            return mixinThread.bumpAllocator.Allocate(bytes, alignment,
                                                      thread);
        }

        [RequiredByBartok]
        [Inline]
        public static unsafe Object CompilerAllocateGenerational
        (VTable vtable, Thread currentThread, UIntPtr bytes, uint alignment)
        {
            VTable.Assert((alignment == 4)
                          || ((alignment == 8) && (UIntPtr.Size == 8))
                          || ((alignment == 8) && (PreHeader.Size == 4)),
                          "Unsupported object layout");
            VTable.Assert(UIntPtr.Size == PreHeader.Size,
                          "Unsupported preheader size");
            VTable.Assert
                (Util.IsAligned((uint) PreHeader.Size + (uint)PostHeader.Size,
                                alignment),
                 "Unsupported header sizes");

            UIntPtr preHeaderAddr =
                MixinThread(currentThread).bumpAllocator.allocPtr;

            // allocPtr is only needed when alignment needs to be checked.  It
            // stores the beginning of the region to be allocation including
            // a possible alignment token.
            UIntPtr allocPtr = UIntPtr.Zero;
            if((alignment == 8) && (UIntPtr.Size == 4)) {
                allocPtr = preHeaderAddr;
                preHeaderAddr = Util.Pad(preHeaderAddr, (UIntPtr) alignment);
            }

            UIntPtr bound = preHeaderAddr + bytes;
            UIntPtr limitPtr =
                MixinThread(currentThread).bumpAllocator.zeroedLimit;
            if (bound <= limitPtr) {
                if((alignment == 8) && (UIntPtr.Size == 4)) {
                    // Store alignment token at allocPtr.  This will be where an
                    // alignment token should go if 'preHeaderAddr' was
                    // bumped...
                    Allocator.WriteAlignment(allocPtr);
                    // ... or the alignment token is where the object header
                    // should be.  This code zeroes the object header regardless
                    // and avoids a branch in this fast path.
                    *(UIntPtr *)preHeaderAddr = UIntPtr.Zero;
                }
                MixinThread(currentThread).bumpAllocator.allocPtr = bound;

                UIntPtr objAddr = preHeaderAddr + PreHeader.Size;
                Object obj = Magic.fromAddress(objAddr);
                obj.vtable = vtable;
                return obj;
            }

            return GC.AllocateObjectNoInline(vtable, currentThread);
        }

        [Inline]
        internal static UIntPtr AllocateFast(Thread thread,
                                             UIntPtr bytes, uint alignment)
        {
            BumpAllocatorThread mixinThread = MixinThread(thread);
            return mixinThread.bumpAllocator.AllocateFast(bytes, alignment);
        }

        [ManualRefCounts]
        public static UIntPtr AllocateSlow(Thread currentThread,
                                           UIntPtr bytes, uint alignment)
        {
            BumpAllocatorThread mixinThread = MixinThread(currentThread);
            return mixinThread.bumpAllocator.AllocateSlow(bytes, alignment,
                                                          currentThread);
        }

        [ManualRefCounts]
        public UIntPtr Allocate(UIntPtr bytes, uint alignment) {
            UIntPtr resultAddr = this.AllocateFast(bytes, alignment);
            if (resultAddr == UIntPtr.Zero) {
                Thread currentThread = Thread.CurrentThread;
                resultAddr = this.AllocateSlow(bytes, alignment,
                                               currentThread);
                VTable.Assert(resultAddr != UIntPtr.Zero);
            }
            return resultAddr;
        }

        [ManualRefCounts]
        public UIntPtr Allocate(UIntPtr bytes, uint alignment, Thread thread)
        {
            UIntPtr resultAddr = this.AllocateFast(bytes, alignment);
            if (resultAddr == UIntPtr.Zero) {
                resultAddr = this.AllocateSlow(bytes, alignment, thread);
                VTable.Assert(resultAddr != UIntPtr.Zero);
            }
            return resultAddr;
        }

        [ManualRefCounts]
        internal UIntPtr AllocateFast(UIntPtr bytes, uint alignment)
        {
#if SINGULARITY_KERNEL
#if ENSURE_ALLOCATION_ALLOWED
            // BumpAllocator.EnsureAllocationAllowed();
#endif
#endif
            UIntPtr allocPtr =
                Allocator.AlignedAllocationPtr(this.allocPtr, this.zeroedLimit,
                                               alignment);
            if (allocPtr + bytes > this.zeroedLimit) {
                this.allocPtr = allocPtr;
                return UIntPtr.Zero;
            }
            this.allocPtr = allocPtr + bytes;
            return allocPtr + PreHeader.Size;
        }

        internal UIntPtr AllocateSlow(UIntPtr bytes, uint alignment,
                                      Thread currentThread)
        {
            UIntPtr newObjectAddr = this.ExtendZero(bytes, alignment);
            if (newObjectAddr == UIntPtr.Zero) {
                newObjectAddr =
                    this.ExtendAlloc(bytes, alignment, currentThread);
                if (newObjectAddr == UIntPtr.Zero) {
                    newObjectAddr =
                        this.FreshAlloc(bytes, alignment, currentThread);
                }
            }
            return newObjectAddr;
        }

        [Inline]
        private UIntPtr ExtendZero(UIntPtr bytes, uint alignment)
        {
            return UIntPtr.Zero;
        }

        private UIntPtr ExtendAlloc(UIntPtr bytes, uint alignment,
                                    Thread currentThread)
        {
            if (this.reserveLimit == UIntPtr.Zero) {
                return UIntPtr.Zero;
            }
#if SINGULARITY_KERNEL
            Kernel.Waypoint(700);
#endif
            UIntPtr neededBytes =
                bytes +  // Bytes required for object +
                alignment - UIntPtr.Size - // worst case alignment overhead +
                (this.reserveLimit - this.allocPtr); // bytes already available
            UIntPtr paddedNeed = PageTable.PagePad(neededBytes);
            UIntPtr pageCount = PageTable.PageCount(paddedNeed);
            UIntPtr startPage = PageTable.Page(this.reserveLimit);
            bool fCleanPages = CLEAR_POOL_PAGES();
            bool gotPages =
                PageManager.TryReserveUnusedPages(currentThread, startPage,
                                                  pageCount, this.pageType,
                                                  ref fCleanPages);
            if (!gotPages) {
                // We can't indiscriminately ask for more memory if we have
                // unused pages already available.
                return UIntPtr.Zero;
            }
            if (this.reserveLimit == UIntPtr.Zero) {
                // A collection occurred, so there is no region to extend
                PageManager.ReleaseUnusedPages(startPage, pageCount,
                                               fCleanPages);
                return UIntPtr.Zero;
            }
            BaseCollector.IncrementNewBytesSinceGC(paddedNeed);
            this.allocNew = this.reserveLimit;
            // Pad alignment space if necessary.  NB: a prior call to
            // AllocateFast may have started generating alignment tokens,
            // but we may need to finish the job here if the residual space
            // was insufficient for a multi-word alignment.
            UIntPtr oldReserveLimit = this.reserveLimit;
            this.reserveLimit += paddedNeed;
            this.allocPtr =
                Allocator.AlignedAllocationPtr(this.allocPtr,
                                               this.reserveLimit,
                                               alignment);
            if (this.zeroedLimit < this.allocPtr) {
                this.zeroedLimit = this.allocPtr;
            }
            UIntPtr objectAddr = this.allocPtr + PreHeader.Size;
            this.allocPtr += bytes;
            if (fCleanPages) {
                if (this.zeroedLimit < oldReserveLimit) {
                    Util.MemClear(this.zeroedLimit,
                                  oldReserveLimit - this.zeroedLimit);
                }
                this.zeroedLimit = this.reserveLimit;
            } else {
                Util.MemClear(this.zeroedLimit,
                              this.allocPtr - this.zeroedLimit);
                this.zeroedLimit = this.allocPtr;
            }
            VTable.Assert(this.allocPtr <= this.zeroedLimit);
            VTable.Assert(PageTable.PageAligned(this.reserveLimit));
            if (objectAddr >= oldReserveLimit) {
                // Object is first on new page
                InteriorPtrTable.SetFirst(objectAddr);
            } else if (objectAddr + bytes < this.reserveLimit) {
                // The object does not end on new limit

                // N.B. The next object may not be allocated at exactly
                // (objectAddr + bytes) due to alignment considerations.  It
                // also might not ever be allocated.  These cases are handled
                // by InteriorPtrTable.First skipping over alignment tokens
                // and callers of First watching out for unused space tokens.

                InteriorPtrTable.SetFirst(objectAddr + bytes);
            }
            // We know an object is located as the last one in a page
            // when it extends through the page to the next.
            // Otherwise, it is totally before or below the page, and
            // we are not sure whether it is the last object or not.
            // So record only such an object for the last card in that
            // page. Many objects may have been omitted due to
            // this coarse-grain recording. But we should be able
            // to incrementally update the offset table and find them.
            // I believe this is a better choice than simply recording
            // any object to the offset table, because most objects
            // may just die and need not to record.

#if !SINGULARITY || SEMISPACE_COLLECTOR || ADAPTIVE_COPYING_COLLECTOR || SLIDING_COLLECTOR
            if (GC.remsetType == RemSetType.Cards) {
                if (objectAddr < oldReserveLimit &&
                    allocPtr + bytes > oldReserveLimit) {
#if DONT_RECORD_OBJALLOC_IN_OFFSETTABLE
#else
                    OffsetTable.SetLast(objectAddr);
#endif
                }
            }
#endif

#if SINGULARITY_KERNEL
            Kernel.Waypoint(701);
#endif
            return objectAddr;
        }

        private UIntPtr FreshAlloc(UIntPtr bytes, uint alignment,
                                   Thread currentThread)
        {
#if SINGULARITY_KERNEL
            Kernel.Waypoint(702);
#endif
            this.Truncate();
            UIntPtr paddedBytes =
                PageTable.PagePad(bytes + alignment - UIntPtr.Size);
            BaseCollector.IncrementNewBytesSinceGC(paddedBytes);
            UIntPtr pages = PageTable.PageCount(paddedBytes);
            bool fCleanPages = CLEAR_POOL_PAGES();
            // We may eventually want to ask for specific pages
            // between asking if any pages are reusable and asking the
            // OS for any possible page.
            UIntPtr startPage =
                PageManager.EnsurePages(currentThread, pages, this.pageType,
                                        ref fCleanPages);
            UIntPtr startAddr = PageTable.PageAddr(startPage);
            UIntPtr limitAddr = PageTable.PageAddr(startPage + pages);
            startAddr = Allocator.AlignedAllocationPtr(startAddr, limitAddr,
                                                       alignment);
            this.allocNew = startAddr;
            this.allocPtr = startAddr + bytes;
            if (fCleanPages) {
                this.zeroedLimit = limitAddr;
            } else {
                Util.MemClear(startAddr, bytes);
                this.zeroedLimit = this.allocPtr;
            }
            this.reserveLimit = limitAddr;
            UIntPtr resultAddr = startAddr + PreHeader.Size;
            InteriorPtrTable.SetFirst(resultAddr);

#if !SINGULARITY || SEMISPACE_COLLECTOR || ADAPTIVE_COPYING_COLLECTOR || SLIDING_COLLECTOR
            if (GC.remsetType == RemSetType.Cards) {
                UIntPtr nextPageAddr = startAddr + PageTable.PageSize;
                VTable.Assert(resultAddr < nextPageAddr);
                if (this.allocPtr > nextPageAddr) {
#if DONT_RECORD_OBJALLOC_IN_OFFSETTABLE
#else
                    OffsetTable.SetLast(resultAddr);
#endif
                }
            }
#endif

#if SINGULARITY_KERNEL
            Kernel.Waypoint(703);
#endif
            return resultAddr;
        }

        internal static void Preempt(Thread t)
        {
            MixinThread(t).bumpAllocator.Preempt();
        }

        private void Preempt()
        {
            this.zeroedLimit = UIntPtr.Zero;
        }

        internal static void Truncate(Thread t)
        {
            MixinThread(t).bumpAllocator.Truncate();
        }

        internal void Truncate()
        {
            UIntPtr allocPtr = this.allocPtr;
            if (!PageTable.PageAligned(allocPtr)) {
                WriteUnusedMarker(allocPtr);
            }
            // NB: allocPtr must never be zero unless zeroedLimit is also zero.
            // NB: zeroedLimit can be zero if GC is necessary.
            this.zeroedLimit = UIntPtr.Zero;
            this.reserveLimit = UIntPtr.Zero;
            this.allocPtr = UIntPtr.Zero;
            this.allocNew = UIntPtr.Zero;
        }

        private static UIntPtr UNUSED_SPACE_TOKEN {
            [Inline]
            [NoHeapAllocation]
            get { return ~((UIntPtr)7u); }
        }

        [Inline]
        [NoHeapAllocation]
        internal static unsafe void WriteUnusedMarker(UIntPtr addr)
        {
            *(UIntPtr*)addr = BumpAllocator.UNUSED_SPACE_TOKEN;
        }

        [Inline]
        [NoHeapAllocation]
        internal static unsafe bool IsUnusedMarkerAddr(UIntPtr addr)
        {
            return (*(UIntPtr*)addr == UNUSED_SPACE_TOKEN);
        }

        [Inline]
        [NoHeapAllocation]
        internal static unsafe bool IsUnusedSpace(UIntPtr obj)
        {
            return *(UIntPtr*)(obj - PreHeader.Size) == UNUSED_SPACE_TOKEN;
        }

        internal static unsafe UIntPtr SkipNonObjectData(UIntPtr objectAddr,
                                                         UIntPtr limit)
        {
            // Skip any UNUSED_SPACE_TOKEN and ALIGNMENT_TOKEN areas
            while (true) {
                if (objectAddr >= limit) {
                    break;
                }
                if (Allocator.IsAlignment(objectAddr)) {
                    objectAddr += UIntPtr.Size;
                } else if (IsUnusedSpace(objectAddr)) {
                    UIntPtr wordAfterUnused =
                        objectAddr - PreHeader.Size + UIntPtr.Size;
                    UIntPtr pageLimit = PageTable.PagePad(wordAfterUnused);
                    CheckMemoryClear(wordAfterUnused, pageLimit);
                    objectAddr = pageLimit + PreHeader.Size;
                } else if (Allocator.IsZeroVTable(objectAddr)) {
                    // The rest of the page must not be used
                    UIntPtr pageLimit = PageTable.PagePad(objectAddr);
                    CheckMemoryClear(objectAddr, pageLimit);
                    objectAddr = pageLimit + PreHeader.Size;
                } else {
                    break;
                }
            }
            return objectAddr;
        }

        [Inline]
        internal static unsafe bool IsRestOfPageZero(UIntPtr lowAddr) {
            UIntPtr* initial = (UIntPtr*)lowAddr;
            UIntPtr* pageLimit = (UIntPtr*)PageTable.PagePad(lowAddr);
            for (UIntPtr* addr = initial; addr < pageLimit; addr++) {
                 if (*addr != UIntPtr.Zero) {
                     return false;
                 }
            }
            return true;
        }

        [System.Diagnostics.Conditional("DEBUG")]
        private static void CheckMemoryClear(UIntPtr begin,
                                             UIntPtr limit) {
            VTable.DebugBreak();
        }

#if SINGULARITY_KERNEL
#if ENSURE_ALLOCATION_ALLOWED
        internal static void EnsureAllocationAllowed()
        {
            // Verify that we're not in an interrupt or non-preemptible region where allocations are prohibited
            Microsoft.Singularity.Processor currentProcessor = Microsoft.Singularity.Processor.CurrentProcessor;
            if (currentProcessor != null) // The Processor object itself may still need to be allocated
            {
                if (currentProcessor.InInterruptContext)
                {
                    Tracing.Log(Tracing.Fatal, "Attempt to allocate memory from interrupt context!");
                    VTable.DebugPrint("Attempt to allocate memory from interrupt context!\n");
                    VTable.DebugBreak();
                }
#if false // Currently too many allocations with preemption disabled to debug right now
                if (currentProcessor.PreemptionDisabled)
                {
                    VTable.DebugPrint("Attempt to allocate memory with preemption disabled!\n");
                    VTable.DebugBreak();
                }
#endif
            }
            VTable.Deny(Thread.CurrentThread != null &&
                        Transitions.fInitializedRuntime &&
                        Transitions.UnderGCControl(Thread.GetCurrentThreadIndex()));
        }
#endif
#endif

    }

    [MixinConditional("BumpAllocatorPageClear")]
    [Mixin(typeof(BumpAllocator))]
    internal struct BumpAllocatorPageClear /* : BumpAllocator */
    {

        [MixinOverride]
        private static bool CLEAR_POOL_PAGES() {
            return true;
        }

        [System.Diagnostics.Conditional("DEBUG")]
        [MixinOverride]
        private static unsafe void CheckMemoryClear(UIntPtr begin,
                                                    UIntPtr limit)
        {
            UIntPtr *beg = (UIntPtr *)begin;
            UIntPtr *lim = (UIntPtr *)limit;

            for (; beg < lim; beg++) {
                VTable.Assert(*beg == UIntPtr.Zero, "Memory isn't zero.");
            }
        }

    }

    [MixinConditional("BumpAllocatorObjectClear")]
    [Mixin(typeof(BumpAllocator))]
    internal struct BumpAllocatorObjectClear /* : BumpAllocator */
    {

        private UIntPtr           allocPtr; // Next allocation.
        private UIntPtr           zeroedLimit; // Limit of zeroed pool.
        private UIntPtr           reserveLimit; // Limit of reserved pool.

        [MixinOverride]
        private static bool CLEAR_POOL_PAGES() {
            return false;
        }

        [MixinOverride]
        [ManualRefCounts]
        [Inline]
        internal UIntPtr AllocateFast(UIntPtr bytes, uint alignment)
        {
#if SINGULARITY_KERNEL
#if ENSURE_ALLOCATION_ALLOWED
            BumpAllocator.EnsureAllocationAllowed();
#endif
#endif
            UIntPtr allocPtr =
                Allocator.AlignedAllocationPtr(this.allocPtr,
                                               this.reserveLimit,
                                               alignment);
            UIntPtr objectLimitPtr = allocPtr + bytes;
            if (objectLimitPtr > this.reserveLimit) {
                this.allocPtr = allocPtr;
                return UIntPtr.Zero;
            }
            if (objectLimitPtr > this.zeroedLimit) {
                Util.MemClear(allocPtr, bytes);
                this.zeroedLimit = objectLimitPtr;
            }
            this.allocPtr = objectLimitPtr;
            return allocPtr + PreHeader.Size;
        }

        [System.Diagnostics.Conditional("DEBUG")]
        [MixinOverride]
        private static unsafe void CheckMemoryClear(UIntPtr begin,
                                                    UIntPtr limit)
        {
            // Since we are only clearing memory on demand, the memory area
            // is allowed to contain random garbage values.
        }

    }

    [MixinConditional("BumpAllocatorCacheClear")]
    [Mixin(typeof(BumpAllocator))]
    internal struct BumpAllocatorCacheClear /* : BumpAllocator */
    {

        private UIntPtr           allocPtr; // Next allocation.
        private UIntPtr           zeroedLimit; // Limit of zeroed pool.
        private UIntPtr           reserveLimit; // Limit of reserved pool.

        [MixinOverride]
        private static bool CLEAR_POOL_PAGES() {
            return false;
        }

        private static UIntPtr CACHE_SIZE {
            get { return (UIntPtr) 128; }
        }

        [MixinOverride]
        internal UIntPtr ExtendZero(UIntPtr bytes, uint alignment)
        {
            while (this.allocPtr + bytes <= this.reserveLimit) {
                UIntPtr newZeroedLimit =
                    Util.Pad(this.allocPtr + bytes, CACHE_SIZE);
                Util.MemClear(this.zeroedLimit,
                              newZeroedLimit - this.zeroedLimit);
                this.zeroedLimit = newZeroedLimit;
                UIntPtr allocPtr =
                    Allocator.AlignedAllocationPtr(this.allocPtr,
                                                   newZeroedLimit,
                                                   alignment);
                if (allocPtr + bytes <= newZeroedLimit) {
                    this.allocPtr = allocPtr + bytes;
                    return allocPtr + PreHeader.Size;
                } else {
                    this.allocPtr = allocPtr;
                }
            }
            return UIntPtr.Zero;
        }

        [System.Diagnostics.Conditional("DEBUG")]
        [MixinOverride]
        private static unsafe void CheckMemoryClear(UIntPtr begin,
                                                    UIntPtr limit)
        {
            // Since we are only clearing memory on demand, the memory area
            // is allowed to contain random garbage values.
        }

    }

}