1 /*

     2  * Copyright (C) 2009 Apple Inc. All rights reserved.

     3  *

     4  * Redistribution and use in source and binary forms, with or without

     5  * modification, are permitted provided that the following conditions

     6  * are met:

     7  * 1. Redistributions of source code must retain the above copyright

     8  *    notice, this list of conditions and the following disclaimer.

     9  * 2. Redistributions in binary form must reproduce the above copyright

    10  *    notice, this list of conditions and the following disclaimer in the

    11  *    documentation and/or other materials provided with the distribution.

    12  *

    13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY

    14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

    16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR

    17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

    18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

    19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR

    20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY

    21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

    22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

    23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 

    24  */

    25 

    26 #ifndef MarkStack_h

    27 #define MarkStack_h

    28 

    29 #include "JSValue.h"

    30 #include <wtf/Noncopyable.h>

    31 

    32 namespace JSC {

    33 

    34     class JSGlobalData;

    35     class Register;

    36     

    37     enum MarkSetProperties { MayContainNullValues, NoNullValues };

    38     

    39     class MarkStack : Noncopyable {

    40     public:

    41         MarkStack(void* jsArrayVPtr)

    42             : m_jsArrayVPtr(jsArrayVPtr)

    43 #ifndef NDEBUG

    44             , m_isCheckingForDefaultMarkViolation(false)

    45 #endif

    46         {

    47         }

    48 

    49         ALWAYS_INLINE void append(JSValue);

    50         void append(JSCell*);

    51         

    52         ALWAYS_INLINE void appendValues(Register* values, size_t count, MarkSetProperties properties = NoNullValues)

    53         {

    54             appendValues(reinterpret_cast<JSValue*>(values), count, properties);

    55         }

    56 

    57         ALWAYS_INLINE void appendValues(JSValue* values, size_t count, MarkSetProperties properties = NoNullValues)

    58         {

    59             if (count)

    60                 m_markSets.append(MarkSet(values, values + count, properties));

    61         }

    62 

    63         inline void drain();

    64         void compact();

    65 

    66         ~MarkStack()

    67         {

    68             ASSERT(m_markSets.isEmpty());

    69             ASSERT(m_values.isEmpty());

    70         }

    71 

    72     private:

    73         void markChildren(JSCell*);

    74 

    75         struct MarkSet {

    76             MarkSet(JSValue* values, JSValue* end, MarkSetProperties properties)

    77                 : m_values(values)

    78                 , m_end(end)

    79                 , m_properties(properties)

    80             {

    81                 ASSERT(values);

    82             }

    83             JSValue* m_values;

    84             JSValue* m_end;

    85             MarkSetProperties m_properties;

    86         };

    87 

    88         static void* allocateStack(size_t size);

    89         static void releaseStack(void* addr, size_t size);

    90 

    91         static void initializePagesize();

    92         static size_t pageSize()

    93         {

    94             if (!s_pageSize)

    95                 initializePagesize();

    96             return s_pageSize;

    97         }

    98 

    99         template <typename T> struct MarkStackArray {

   100             MarkStackArray()

   101                 : m_top(0)

   102                 , m_allocated(MarkStack::pageSize())

   103                 , m_capacity(m_allocated / sizeof(T))

   104             {

   105                 m_data = reinterpret_cast<T*>(allocateStack(m_allocated));

   106             }

   107 

   108             ~MarkStackArray()

   109             {

   110                 releaseStack(m_data, m_allocated);

   111             }

   112 

   113             void expand()

   114             {

   115                 size_t oldAllocation = m_allocated;

   116                 m_allocated *= 2;

   117                 m_capacity = m_allocated / sizeof(T);

   118                 void* newData = allocateStack(m_allocated);

   119                 memcpy(newData, m_data, oldAllocation);

   120                 releaseStack(m_data, oldAllocation);

   121                 m_data = reinterpret_cast<T*>(newData);

   122             }

   123 

   124             inline void append(const T& v)

   125             {

   126                 if (m_top == m_capacity)

   127                     expand();

   128                 m_data[m_top++] = v;

   129             }

   130 

   131             inline T removeLast()

   132             {

   133                 ASSERT(m_top);

   134                 return m_data[--m_top];

   135             }

   136             

   137             inline T& last()

   138             {

   139                 ASSERT(m_top);

   140                 return m_data[m_top - 1];

   141             }

   142 

   143             inline bool isEmpty()

   144             {

   145                 return m_top == 0;

   146             }

   147 

   148             inline size_t size() { return m_top; }

   149 

   150             inline void shrinkAllocation(size_t size)

   151             {

   152                 ASSERT(size <= m_allocated);

   153                 ASSERT(0 == (size % MarkStack::pageSize()));

   154                 if (size == m_allocated)

   155                     return;

   156 #if OS(WINDOWS) || OS(SYMBIAN) || PLATFORM(BREWMP)

   157                 // We cannot release a part of a region with VirtualFree.  To get around this,

   158                 // we'll release the entire region and reallocate the size that we want.

   159                 releaseStack(m_data, m_allocated);

   160                 m_data = reinterpret_cast<T*>(allocateStack(size));

   161 #else

   162                 releaseStack(reinterpret_cast<char*>(m_data) + size, m_allocated - size);

   163 #endif

   164                 m_allocated = size;

   165                 m_capacity = m_allocated / sizeof(T);

   166             }

   167 

   168         private:

   169             size_t m_top;

   170             size_t m_allocated;

   171             size_t m_capacity;

   172             T* m_data;

   173         };

   174 

   175         void* m_jsArrayVPtr;

   176         MarkStackArray<MarkSet> m_markSets;

   177         MarkStackArray<JSCell*> m_values;

   178         static size_t s_pageSize;

   179 

   180 #ifndef NDEBUG

   181     public:

   182         bool m_isCheckingForDefaultMarkViolation;

   183 #endif

   184     };

   185 }

   186 

   187 #endif