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