1 : // Copyright 2014 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 : //
15 : // Defines PageAllocator. This is a simple allocator that grabs pages of
16 : // memory of a fixed specified size and hands out fixed size regions from head
17 : // to tail within that page. Regions of pages that have been freed are kept
18 : // track of in a simple linked list, and returned regions are aggressively
19 : // reused before a new page is allocated.
20 : //
21 : // Since memory is not actively recovered at runtime this allocator will always
22 : // use as much memory as the 'high waterline'. Thus, it is not suitable for
23 : // managing bursty objects. Rather, it should be used for pools that tend to
24 : // grow monotonically to a stable maximum size.
25 :
26 : #ifndef SYZYGY_AGENT_ASAN_PAGE_ALLOCATOR_H_
27 : #define SYZYGY_AGENT_ASAN_PAGE_ALLOCATOR_H_
28 :
29 : #include "base/basictypes.h"
30 : #include "base/synchronization/lock.h"
31 :
32 : namespace agent {
33 : namespace asan {
34 :
35 : // Forward declarations. These are all defined in the corresponding _impl.h.
36 : struct PageAllocatorStatistics;
37 : namespace detail {
38 : template<bool kKeepStats> struct PageAllocatorStatisticsHelper;
39 : template<size_t kObjectSize, size_t kPageSize> struct PageAllocatorPage;
40 : } // namespace detail
41 :
42 :
43 : // NOTE: If you want these to be optimally packed, please use #pragma pack(1)!
44 : // Otherwise, the default compiler alignment will kick in, and the
45 : // objects will be rounded up in size to be 4-byte aligned.
46 :
47 :
48 : // An untyped PageAllocator. Thread safety is provided by this object.
49 : // @tparam kObjectSize The size of objects returned by the allocator,
50 : // in bytes. Objects will be tightly packed so any alignment constraints
51 : // should be reflected in this size. Must be at least as big as a pointer.
52 : // @tparam kMaxObjectCount The maximum number of consecutive objects that
53 : // will be requested at once by the allocator. The allocator will
54 : // ensure that this is possible, and will maintain separate free lists
55 : // for each possible length from 1 to kMaxObjectCount.
56 : // @tparam kPageSize The amount of memory to be allocated at a time as
57 : // the pool grows. This will be rounded up to a multiple of the OS page
58 : // size that is a divisor of the allocation granularity, or a multiple of
59 : // the allocation granularity. This ensures efficient memory use and
60 : // minimal fragmentation.
61 : // @tparam kKeepStats If true, then statistics will be collected.
62 : template<size_t kObjectSize,
63 : size_t kMaxObjectCount,
64 : size_t kPageSize,
65 : bool kKeepStats>
66 : class PageAllocator {
67 : public:
68 : typedef detail::PageAllocatorPage<kObjectSize, kPageSize> Page;
69 : typedef typename Page::Object Object;
70 :
71 : // Constructor.
72 : PageAllocator();
73 :
74 : // Destructor.
75 : ~PageAllocator();
76 :
77 : // Allocates @p count objects of the configured size.
78 : // @param count The number of objects to allocate. Must be > 0.
79 : // @returns A pointer to the allocated objects, or NULL on failure.
80 : void* Allocate(size_t count);
81 :
82 : // Allocates at least @p count objects of the configured size, indicating
83 : // how many were actually returned via @p received. This helps to keep
84 : // fragmentation lower by keeping larger allocations intact.
85 : // @param count The number of objects to allocate. Must be > 0.
86 : // @param received Will be set to the number of object actually
87 : // allocated. This must be the value that is passed to the corresponding
88 : // call to free.
89 : // @returns A pointer to the allocated objects, or NULL on failure.
90 : void* Allocate(size_t count, size_t* received);
91 :
92 : // Frees the given objects.
93 : // @param object The object to be returned.
94 : // @param count The number of objects to return. This must match the
95 : // number of objects originally allocated.
96 : void Free(void* object, size_t count);
97 :
98 : // Returns current statistics. If kKeepStats is false this is a noop and
99 : // does not set any meaningful data.
100 : // @param stats The statistics data to be populated.
101 : void GetStatistics(PageAllocatorStatistics* stats);
102 :
103 : // Determines if an allocation is currently handed out by this allocator.
104 : // @param object The object to be checked.
105 : // @param count The number of objects in the allocation.
106 : // @returns true if the given object was handed out by this allocator.
107 : // @note Handles locking, so no locks must already be held.
108 E : bool Allocated(const void* object, size_t count) {
109 E : return AllocationStatus(object, count) == 1;
110 E : }
111 :
112 : // Determines if an allocation is currently freed by this allocator.
113 : // @param object The object to be checked.
114 : // @param count The number of objects in the allocation. If this is zero then
115 : // all freed size classes will be checked, otherwise only the exact
116 : // specified size class will be checked.
117 : // @returns true if the given object is the first object in a range that was
118 : // freed by the allocator.
119 : // @note Handles locking, so no locks must already be held.
120 E : bool Freed(const void* object, size_t count) {
121 E : return AllocationStatus(object, count) == 0;
122 E : }
123 :
124 : protected:
125 : // Tri-state allocation status function, determining if the given object
126 : // is currently allocated by this allocator (1), currently freed (0), or
127 : // isn't under management by it (-1).
128 : // @returns 1 if the object was allocated, 0 if it has since been freed, or
129 : // -1 if the object is not under management by this allocator.
130 : // @note This is a very costly O(memory under management) function!
131 : int AllocationStatus(const void* object, size_t count);
132 :
133 : // Determines if an allocation was handed out by this allocator. The object
134 : // may since have been freed.
135 : // @param object The object to be checked.
136 : // @param count The number of objects in the allocation.
137 : // @returns true if the given object was handed out by this allocator.
138 : // @note Handles locking, so no locks must already be held.
139 : bool WasOnceAllocated(const void* object, size_t count);
140 :
141 : // Determines if an allocation is currently in the freed list of this
142 : // allocator.
143 : // @param object The object to be checked.
144 : // @param count The number of objects in the allocation. If this is zero then
145 : // all freed size classes will be checked, otherwise only the exact
146 : // specified size class will be checked.
147 : // @returns true if the given object is the first object in a range that was
148 : // freed by the allocator.
149 : // @note Handles locking, so no locks must already be held.
150 : bool IsInFreeList(const void* object, size_t count);
151 :
152 : // Pops the top item from the given free list.
153 : // @param count The size class.
154 : // @returns a pointer to the popped item, NULL if there was none.
155 : // @note Handles locking, so no free_lock_ should be already held.
156 : Object* FreePop(size_t count);
157 :
158 : // Pushes the given object to the specified free list. Directives as to
159 : // statistics keeping are provided directly here to minimize the number of
160 : // times the statistics lock needs to be taken.
161 : // @param object The objects to free.
162 : // @param count The number of objects to free.
163 : // @param decr_alloc_groups If true then decrements allocated_groups.
164 : // @param decr_alloc_objects If true then decrements allocated_object.
165 : // @note Handles locking, so no free_lock_ should be already held.
166 : void FreePush(Object* object, size_t count,
167 : bool decr_alloc_groups, bool decr_alloc_objects);
168 :
169 : // Reserves a new page of objects, modifying current_page_ and
170 : // current_object_. Any remaining unallocated objects are stuffed into the
171 : // appropriate freed list. There may be no more than kMaxObjectCount of them.
172 : // @returns true if the allocation was successful, false otherwise.
173 : // @note Assumes the lock_ has already been acquired.
174 : bool AllocatePageLocked();
175 :
176 : // The number of pages that have been allocated. Under lock_.
177 : size_t page_count_;
178 :
179 : // The current slab of reserved memory we are working from Under lock_.
180 : Page* slab_;
181 : Page* slab_cursor_;
182 :
183 : // The currently active page. Under lock_.
184 : Page* page_;
185 :
186 : // The next object to be allocated in the current page. Under lock_.
187 : Object* object_;
188 :
189 : // A singly linked list of freed objects, one per possible size category.
190 : // These are under the corresponding free_lock_.
191 : Object* free_[kMaxObjectCount];
192 :
193 : // Locks for the freed lists. This keeps contention down while freeing.
194 : base::Lock free_lock_[kMaxObjectCount];
195 :
196 : // The global lock for the allocator.
197 : base::Lock lock_;
198 :
199 : // For keeping statistics. If kKeepStats == 0 this is an empty struct with
200 : // noop routines.
201 : detail::PageAllocatorStatisticsHelper<kKeepStats> stats_;
202 :
203 : private:
204 : DISALLOW_COPY_AND_ASSIGN(PageAllocator);
205 : };
206 :
207 : // A templated PageAllocator with convenience functions for allocating and
208 : // freeing typed objects.
209 : // @tparam ObjectType The type of object that is returned by the allocator.
210 : // @tparam kMaxObjectCount The maximum number of consecutive objects that
211 : // will be requested at once by the allocator. The allocator will
212 : // ensure that this is possible, and will maintain separate free lists
213 : // for each possible length from 1 to kMaxObjectCount.
214 : // @tparam kPageSize The amount of memory to be allocated at a time as
215 : // the pool grows.
216 : // @tparam kKeepStats If true, then statistics will be collected.
217 : template<typename ObjectType,
218 : size_t kMaxObjectCount,
219 : size_t kPageSize,
220 : bool kKeepStats>
221 : class TypedPageAllocator
222 : : public PageAllocator<sizeof(ObjectType),
223 : kMaxObjectCount,
224 : kPageSize,
225 : kKeepStats> {
226 : public:
227 : // The parent type for this class.
228 : typedef PageAllocator<sizeof(ObjectType), kMaxObjectCount, kPageSize,
229 : kKeepStats> Super;
230 :
231 : // Constructor.
232 E : TypedPageAllocator() { }
233 :
234 : // Destructor.
235 E : ~TypedPageAllocator() { }
236 :
237 : // Allocates objects.
238 : // @param count The number of objects to allocate. Must be > 0.
239 : // @returns A pointer to the allocated object, or NULL on failure.
240 : ObjectType* Allocate(size_t count);
241 :
242 : // Allocates at least the requested number of objects, possibly returning
243 : // more. This allocator is preferred as it results in less fragmentation.
244 : // @param count The number of objects to allocate. Must be > 0.
245 : // @param received Will be set to the number of object actually
246 : // allocated. This must be the value that is passed to the corresponding
247 : // call to free.
248 : // @returns A pointer to the allocated objects, or NULL on failure.
249 : ObjectType* Allocate(size_t count, size_t* received);
250 :
251 : // Frees the given object.
252 : // @param object The object to be returned.
253 : // @param count The number of objects to return. This must match the
254 : // number of objects originally allocated.
255 : void Free(ObjectType* object, size_t count);
256 :
257 : private:
258 : DISALLOW_COPY_AND_ASSIGN(TypedPageAllocator);
259 : };
260 :
261 : // A structure used for collecting statistics aggregated by a page allocator.
262 : struct PageAllocatorStatistics {
263 : // The number of pages allocated.
264 : size_t page_count;
265 : // The number of groups of objects handed out.
266 : size_t allocated_groups;
267 : // The total number of objects handed out.
268 : size_t allocated_objects;
269 : // The number of groups of objects living in free lists.
270 : size_t freed_groups;
271 : // The total number of objects living in free lists.
272 : size_t freed_objects;
273 : };
274 :
275 : } // namespace asan
276 : } // namespace agent
277 :
278 : #include "syzygy/agent/asan/page_allocator_impl.h"
279 :
280 : #endif // SYZYGY_AGENT_ASAN_PAGE_ALLOCATOR_H_
|