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
32namespace 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
188