Fix the build.
[WebKit-https.git] / Source / JavaScriptCore / wtf / MetaAllocator.h
1 /*
2  * Copyright (C) 2011 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  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer. 
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution. 
13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission. 
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #ifndef WTF_MetaAllocator_h
30 #define WTF_MetaAllocator_h
31
32 #include <wtf/Assertions.h>
33 #include <wtf/HashMap.h>
34 #include <wtf/MetaAllocatorHandle.h>
35 #include <wtf/Noncopyable.h>
36 #include <wtf/PageBlock.h>
37 #include <wtf/RedBlackTree.h>
38 #include <wtf/RefCounted.h>
39 #include <wtf/RefPtr.h>
40 #include <wtf/TCSpinLock.h>
41
42 namespace WTF {
43
44 #define ENABLE_META_ALLOCATOR_PROFILE 0
45
46 class MetaAllocatorTracker {
47 public:
48     void notify(MetaAllocatorHandle*);
49     void release(MetaAllocatorHandle*);
50
51     MetaAllocatorHandle* find(void* address)
52     {
53         MetaAllocatorHandle* handle = m_allocations.findGreatestLessThanOrEqual(address);
54         if (handle && address < handle->end())
55             return handle;
56         return 0;
57     }
58
59     RedBlackTree<MetaAllocatorHandle, void*> m_allocations;
60 };
61
62 class MetaAllocator {
63     WTF_MAKE_NONCOPYABLE(MetaAllocator);
64
65 public:
66     WTF_EXPORT_PRIVATE MetaAllocator(size_t allocationGranule);
67     
68     WTF_EXPORT_PRIVATE virtual ~MetaAllocator();
69     
70     WTF_EXPORT_PRIVATE PassRefPtr<MetaAllocatorHandle> allocate(size_t sizeInBytes, void* ownerUID);
71
72     void trackAllocations(MetaAllocatorTracker* tracker)
73     {
74         m_tracker = tracker;
75     }
76     
77     // Non-atomic methods for getting allocator statistics.
78     size_t bytesAllocated() { return m_bytesAllocated; }
79     size_t bytesReserved() { return m_bytesReserved; }
80     size_t bytesCommitted() { return m_bytesCommitted; }
81     
82     // Atomic method for getting allocator statistics.
83     struct Statistics {
84         size_t bytesAllocated;
85         size_t bytesReserved;
86         size_t bytesCommitted;
87     };
88     Statistics currentStatistics();
89
90     // Add more free space to the allocator. Call this directly from
91     // the constructor if you wish to operate the allocator within a
92     // fixed pool.
93     WTF_EXPORT_PRIVATE void addFreshFreeSpace(void* start, size_t sizeInBytes);
94
95     // This is meant only for implementing tests. Never call this in release
96     // builds.
97     WTF_EXPORT_PRIVATE size_t debugFreeSpaceSize();
98     
99 #if ENABLE(META_ALLOCATOR_PROFILE)
100     void dumpProfile();
101 #else
102     void dumpProfile() { }
103 #endif
104
105 protected:
106     
107     // Allocate new virtual space, but don't commit. This may return more
108     // pages than we asked, in which case numPages is changed.
109     virtual void* allocateNewSpace(size_t& numPages) = 0;
110     
111     // Commit a page.
112     virtual void notifyNeedPage(void* page) = 0;
113     
114     // Uncommit a page.
115     virtual void notifyPageIsFree(void* page) = 0;
116     
117     // NOTE: none of the above methods are called during allocator
118     // destruction, in part because a MetaAllocator cannot die so long
119     // as there are Handles that refer to it.
120
121 private:
122     
123     friend class MetaAllocatorHandle;
124     
125     class FreeSpaceNode : public RedBlackTree<FreeSpaceNode, size_t>::Node {
126     public:
127         FreeSpaceNode(void* start, size_t sizeInBytes)
128             : m_start(start)
129             , m_sizeInBytes(sizeInBytes)
130         {
131         }
132
133         size_t key()
134         {
135             return m_sizeInBytes;
136         }
137
138         void* m_start;
139         size_t m_sizeInBytes;
140     };
141     typedef RedBlackTree<FreeSpaceNode, size_t> Tree;
142
143     // Release a MetaAllocatorHandle.
144     void release(MetaAllocatorHandle*);
145     
146     // Remove free space from the allocator. This is effectively
147     // the allocate() function, except that it does not mark the
148     // returned space as being in-use.
149     void* findAndRemoveFreeSpace(size_t sizeInBytes);
150
151     // This is called when memory from an allocation is freed.
152     void addFreeSpaceFromReleasedHandle(void* start, size_t sizeInBytes);
153     
154     // This is the low-level implementation of adding free space; it
155     // is called from both addFreeSpaceFromReleasedHandle and from
156     // addFreshFreeSpace.
157     void addFreeSpace(void* start, size_t sizeInBytes);
158     
159     // Management of used space.
160     
161     void incrementPageOccupancy(void* address, size_t sizeInBytes);
162     void decrementPageOccupancy(void* address, size_t sizeInBytes);
163
164     // Utilities.
165     
166     size_t roundUp(size_t sizeInBytes);
167     
168     FreeSpaceNode* allocFreeSpaceNode();
169     WTF_EXPORT_PRIVATE void freeFreeSpaceNode(FreeSpaceNode*);
170     
171     size_t m_allocationGranule;
172     unsigned m_logAllocationGranule;
173     size_t m_pageSize;
174     unsigned m_logPageSize;
175     
176     Tree m_freeSpaceSizeMap;
177     HashMap<void*, FreeSpaceNode*> m_freeSpaceStartAddressMap;
178     HashMap<void*, FreeSpaceNode*> m_freeSpaceEndAddressMap;
179     HashMap<uintptr_t, size_t> m_pageOccupancyMap;
180     
181     size_t m_bytesAllocated;
182     size_t m_bytesReserved;
183     size_t m_bytesCommitted;
184     
185     SpinLock m_lock;
186
187     MetaAllocatorTracker* m_tracker;
188
189 #ifndef NDEBUG
190     size_t m_mallocBalance;
191 #endif
192
193 #if ENABLE(META_ALLOCATOR_PROFILE)
194     unsigned m_numAllocations;
195     unsigned m_numFrees;
196 #endif
197 };
198
199 } // namespace WTF
200
201 #endif // WTF_MetaAllocator_h
202