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.
36 : struct PageAllocatorStatistics;
37 : template<bool kKeepStats> struct PageAllocatorStatisticsHelper;
38 :
39 : // An untyped PageAllocator. Thread safety is provided by this object.
40 : // @tparam kObjectSize The size of objects returned by the allocator,
41 : // in bytes. Objects will be tightly packed so any alignment constraints
42 : // should be reflected in this size.
43 : // @tparam kMaxObjectCount The maximum number of consecutive objects that
44 : // will be requested at once by the allocator. The allocator will
45 : // ensure that this is possible, and will maintain separate free lists
46 : // for each possible length from 1 to kMaxObjectCount.
47 : // @tparam kPageSize The amount of memory to be allocated at a time as
48 : // the pool grows.
49 : // @tparam kKeepStats If true, then statistics will be collected.
50 : template<size_t kObjectSize,
51 : size_t kMaxObjectCount,
52 : size_t kPageSize,
53 : bool kKeepStats>
54 : class PageAllocator {
55 : public:
56 : // Constructor.
57 : PageAllocator();
58 :
59 : // Destructor.
60 : ~PageAllocator();
61 :
62 : // Allocates @p count objects of the configured size.
63 : // @param count The number of objects to allocate. Must be > 0.
64 : // @returns A pointer to the allocated objects, or NULL on failure.
65 : void* Allocate(size_t count);
66 :
67 : // Allocates at least @p count objects of the configured size, indicating
68 : // how many were actually returned via @p received. This helps to keep
69 : // fragmentation lower by keeping larger allocations intact.
70 : // @param count The number of objects to allocate. Must be > 0.
71 : // @param received Will be set to the number of object actually
72 : // allocated. This must be the value that is passed to the corresponding
73 : // call to free.
74 : // @returns A pointer to the allocated objects, or NULL on failure.
75 : void* Allocate(size_t count, size_t* received);
76 :
77 : // Frees the given objects.
78 : // @param object The object to be returned.
79 : // @param count The number of objects to return. This must match the
80 : // number of objects originally allocated.
81 : void Free(void* object, size_t count);
82 :
83 : // Determines if an allocation was handed out by this allocator.
84 : // @param object The object to be checked.
85 : // @param count The number of objects in the allocation.
86 : // @returns true if the given object was handed out by this allocator.
87 : // @note Handles locking, so no locks must already be held.
88 : bool Allocated(const void* object, size_t count);
89 :
90 : // Determines if an allocation has been returned to this allocator.
91 : // @param object The object to be checked.
92 : // @param count The number of objects in the allocation. If this is zero then
93 : // all freed size classes will be checked, otherwise only the exact
94 : // specified size class will be checked.
95 : // @returns true if the given object is the first object in a range that was
96 : // freed by the allocator.
97 : // @note Handles locking, so no locks must already be held.
98 : bool Freed(const void* object, size_t count);
99 :
100 : // Returns current statistics. If kKeepStats is false this is a noop and
101 : // does not set any meaningful data.
102 : // @param stats The statistics data to be populated.
103 : void GetStatistics(PageAllocatorStatistics* stats);
104 :
105 : protected:
106 : // Pops the top item from the given free list.
107 : // @param count The size class.
108 : // @returns a pointer to the popped item, NULL if there was none.
109 : // @note Handles locking, so no free_lock_ should be already held.
110 : uint8* FreePop(size_t count);
111 :
112 : // Pushes the given object to the specified free list. Directives as to
113 : // statistics keeping are provided directly here to minimize the number of
114 : // times the statistics lock needs to be taken.
115 : // @param object The objects to free.
116 : // @param count The number of objects to free.
117 : // @param decr_alloc_groups If true then decrements allocated_groups.
118 : // @param decr_alloc_objects If true then decrements allocated_object.
119 : // @note Handles locking, so no free_lock_ should be already held.
120 : void FreePush(void* object, size_t count,
121 : bool decr_alloc_groups, bool decr_alloc_objects);
122 :
123 : // Reserves a new page of objects, modifying current_page_ and
124 : // current_object_. Any remaining unallocated objects are stuffed into the
125 : // appropriate freed list. There may be no more than kMaxObjectCount of them.
126 : // @returns true if the allocation was successful, false otherwise.
127 : // @note Assumes the lock_ has already been acquired.
128 : bool AllocatePageLocked();
129 :
130 : // The size of a page in bytes, and the number of objects that fits in it.
131 : // Initialized in the constructor and never touched again. These are
132 : // actually compile time constants, but are hard to express that way.
133 : size_t page_size_;
134 : size_t objects_per_page_;
135 :
136 : // The currently active page of objects. Under lock_.
137 : uint8* current_page_;
138 :
139 : // A pointer into the currently active page of objects. Under lock_.
140 : uint8* current_object_;
141 :
142 : // A pointer into the currently active page of objects that represents beyond
143 : // the end of allocatable objects. This also points to the last pointer sized
144 : // run of bytes in the page, which is used for storing the linked list
145 : // pointer. Under lock_.
146 : uint8* end_object_;
147 :
148 : // A singly linked list of freed objects, one per possible size category.
149 : // These are under the corresponding free_lock_.
150 : uint8* free_[kMaxObjectCount];
151 :
152 : // Locks for the freed lists. This keeps contention down while freeing.
153 : base::Lock free_lock_[kMaxObjectCount];
154 :
155 : // The global lock for the allocator.
156 : base::Lock lock_;
157 :
158 : // For keeping statistics. If kKeepStats == 0 this is an empty struct with
159 : // noop routines.
160 : PageAllocatorStatisticsHelper<kKeepStats> stats_;
161 :
162 : private:
163 : DISALLOW_COPY_AND_ASSIGN(PageAllocator);
164 : };
165 :
166 : // A templated PageAllocator with convenience functions for allocating and
167 : // freeing typed objects.
168 : // @tparam ObjectType The type of object that is returned by the allocator.
169 : // @tparam kMaxObjectCount The maximum number of consecutive objects that
170 : // will be requested at once by the allocator. The allocator will
171 : // ensure that this is possible, and will maintain separate free lists
172 : // for each possible length from 1 to kMaxObjectCount.
173 : // @tparam kPageSize The amount of memory to be allocated at a time as
174 : // the pool grows.
175 : // @tparam kKeepStats If true, then statistics will be collected.
176 : template<typename ObjectType,
177 : size_t kMaxObjectCount,
178 : size_t kPageSize,
179 : bool kKeepStats>
180 : class TypedPageAllocator
181 : : public PageAllocator<sizeof(ObjectType),
182 : kMaxObjectCount,
183 : kPageSize,
184 : kKeepStats> {
185 : public:
186 : // The parent type for this class.
187 : typedef PageAllocator<sizeof(ObjectType), kMaxObjectCount, kPageSize,
188 : kKeepStats> Super;
189 :
190 : // Constructor.
191 E : TypedPageAllocator() { }
192 :
193 : // Destructor.
194 E : ~TypedPageAllocator() { }
195 :
196 : // Allocates objects.
197 : // @param count The number of objects to allocate. Must be > 0.
198 : // @returns A pointer to the allocated object, or NULL on failure.
199 : ObjectType* Allocate(size_t count);
200 :
201 : // Allocates at least the requested number of objects, possibly returning
202 : // more. This allocator is preferred as it results in less fragmentation.
203 : // @param count The number of objects to allocate. Must be > 0.
204 : // @param received Will be set to the number of object actually
205 : // allocated. This must be the value that is passed to the corresponding
206 : // call to free.
207 : // @returns A pointer to the allocated objects, or NULL on failure.
208 : ObjectType* Allocate(size_t count, size_t* received);
209 :
210 : // Frees the given object.
211 : // @param object The object to be returned.
212 : // @param count The number of objects to return. This must match the
213 : // number of objects originally allocated.
214 : void Free(ObjectType* object, size_t count);
215 :
216 : private:
217 : DISALLOW_COPY_AND_ASSIGN(TypedPageAllocator);
218 : };
219 :
220 : // A structure used for collecting statistics aggregated by a page allocator.
221 : struct PageAllocatorStatistics {
222 : // The number of pages allocated.
223 : size_t page_count;
224 : // The number of groups of objects handed out.
225 : size_t allocated_groups;
226 : // The total number of objects handed out.
227 : size_t allocated_objects;
228 : // The number of groups of objects living in free lists.
229 : size_t freed_groups;
230 : // The total number of objects living in free lists.
231 : size_t freed_objects;
232 : };
233 :
234 : } // namespace asan
235 : } // namespace agent
236 :
237 : #include "syzygy/agent/asan/page_allocator_impl.h"
238 :
239 : #endif // SYZYGY_AGENT_ASAN_PAGE_ALLOCATOR_H_
|