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 : // An implementation of HeapInterface which ensures that the end of memory
16 : // allocations is aligned to the system page size and followed by an empty
17 : // page.
18 :
19 : #ifndef SYZYGY_AGENT_ASAN_HEAPS_ZEBRA_BLOCK_HEAP_H_
20 : #define SYZYGY_AGENT_ASAN_HEAPS_ZEBRA_BLOCK_HEAP_H_
21 :
22 : #include <windows.h>
23 :
24 : #include <list>
25 : #include <queue>
26 : #include <vector>
27 :
28 : #include "base/logging.h"
29 : #include "syzygy/agent/asan/allocators.h"
30 : #include "syzygy/agent/asan/circular_queue.h"
31 : #include "syzygy/agent/asan/constants.h"
32 : #include "syzygy/agent/asan/heap.h"
33 : #include "syzygy/agent/asan/memory_notifier.h"
34 : #include "syzygy/agent/asan/quarantine.h"
35 : #include "syzygy/common/recursive_lock.h"
36 :
37 : namespace agent {
38 : namespace asan {
39 : namespace heaps {
40 :
41 : // A zebra-stripe heap allocates a (maximum) predefined amount of memory
42 : // and serves allocation requests with size less than or equal to the system
43 : // page size.
44 : // It divides the memory into 'slabs'; each slab consist of an 'even' page
45 : // followed by an 'odd' page (like zebra-stripes).
46 : //
47 : // |-----------slab 1----------|
48 : // +-------------+-------------+-------------+-------------+------------- - -+
49 : // |even 4k page | odd 4k page |even 4k page | odd 4k page | ... |
50 : // +-------------+-------------+-------------+-------------+------------- - -+
51 : // |-----------slab 0----------| |---slab 2---- - -|
52 : //
53 : // All the allocations are done in the even pages, just before the odd pages.
54 : // The odd pages can be protected againt read/write which gives a basic
55 : // mechanism for detecting buffer overflows.
56 : //
57 : // A block allocation starts with the block header and ends with the block
58 : // trailer. The body is completely contained in the even page and pushed to the
59 : // right, but since the body must be kShadowRatio-aligned there could be a
60 : // small gap between the body and the odd page which is covered by the trailer
61 : // padding. Both paddings fill the rest of the pages.
62 : //
63 : // |-header-padding-| |-------trailer-padding------|
64 : // +--------+----------------+------+--+-------------------------+---------+
65 : // | even 4k page | odd 4k page |
66 : // +--------+----------------+------+--+-------------------------+---------+
67 : // |-header-| |-body-| |-trailer-|
68 : //
69 : // Calling Free on a quarantined address is an invalid operation.
70 : class ZebraBlockHeap : public BlockHeapInterface,
71 : public BlockQuarantineInterface {
72 : public:
73 : // The size of a 2-page slab (2 * kPageSize).
74 : static const size_t kSlabSize;
75 :
76 : // The maximum raw allocation size. Anything bigger than this will always
77 : // fail a call to 'Allocate'.
78 : static const size_t kMaximumAllocationSize;
79 :
80 : // The maximum size of a block body that can be allocated. Anything bigger
81 : // than this will always fail a call to 'AllocateBlock'.
82 : static const size_t kMaximumBlockAllocationSize;
83 :
84 : // Constructor.
85 : // @param heap_size The amount of memory reserved by the heap in bytes.
86 : // @param memory_notifier The MemoryNotifierInterface used to report
87 : // allocation information.
88 : // @param internal_heap The heap to use for making internal allocations.
89 : ZebraBlockHeap(size_t heap_size,
90 : MemoryNotifierInterface* memory_notifier,
91 : HeapInterface* internal_heap);
92 :
93 : // Virtual destructor. Frees all the allocated memory.
94 : virtual ~ZebraBlockHeap();
95 :
96 : // @name HeapInterface functions.
97 : // @{
98 : virtual HeapType GetHeapType() const;
99 : virtual uint32_t GetHeapFeatures() const;
100 : virtual void* Allocate(uint32_t bytes);
101 : virtual bool Free(void* alloc);
102 : virtual bool IsAllocated(const void* alloc);
103 : virtual uint32_t GetAllocationSize(const void* alloc);
104 : virtual void Lock();
105 : virtual void Unlock();
106 : virtual bool TryLock();
107 : // @}
108 :
109 : // @name BlockHeapInterface functions.
110 : // @{
111 : virtual void* AllocateBlock(uint32_t size,
112 : uint32_t min_left_redzone_size,
113 : uint32_t min_right_redzone_size,
114 : BlockLayout* layout);
115 : virtual bool FreeBlock(const BlockInfo& block_info);
116 : // @}
117 :
118 : // @name BlockQuarantineInterface functions.
119 : // @note As of now, the zebra heap always gets trimmed synchronously after
120 : // each successful push by calling pop once. Therefore, a successful push will
121 : // always return SYNC_TRIM_REQUIRED and a pop will always return the GREEN
122 : // color.
123 : // @{
124 : virtual PushResult Push(const CompactBlockInfo& info);
125 : virtual PopResult Pop(CompactBlockInfo* info);
126 : virtual void Empty(std::vector<CompactBlockInfo>* infos);
127 : virtual size_t GetCountForTesting();
128 E : virtual size_t GetLockId(const CompactBlockInfo& info) {
129 E : return 0;
130 E : }
131 E : virtual void Lock(size_t id) { }
132 E : virtual void Unlock(size_t id) { }
133 : // @}
134 :
135 : // Get the ratio of the memory used by the quarantine.
136 E : float quarantine_ratio() const { return quarantine_ratio_; }
137 :
138 : // Set the ratio of the memory used by the quarantine.
139 : void set_quarantine_ratio(float quarantine_ratio);
140 :
141 : protected:
142 : // The set of possible states of the slabs.
143 : enum SlabState {
144 : kFreeSlab,
145 : kAllocatedSlab,
146 : kQuarantinedSlab
147 : };
148 :
149 : struct SlabInfo {
150 : // The state of the slab.
151 : SlabState state;
152 : // Information about the allocation.
153 : CompactBlockInfo info;
154 : };
155 :
156 : // Performs an allocation, and returns a pointer to the SlabInfo where the
157 : // allocation was made.
158 : SlabInfo* AllocateImpl(uint32_t bytes);
159 :
160 : // Checks if the quarantine invariant is satisfied.
161 : // @returns true if the quarantine invariant is satisfied, false otherwise.
162 : bool QuarantineInvariantIsSatisfied();
163 :
164 : // Gives the 0-based index of the slab containing 'address'.
165 : // @param address address.
166 : // @returns The 0-based index of the slab containing 'address', or
167 : // kInvalidSlab index if the address is not valid.
168 : size_t GetSlabIndex(const void* address);
169 :
170 : // Gives the addres of the given slab.
171 : // @param index 0-based index of the slab.
172 : // @returns The address of the slab, or NULL if the index is invalid.
173 : uint8_t* GetSlabAddress(size_t index);
174 :
175 : // Defines an invalid slab index.
176 : static const size_t kInvalidSlabIndex = SIZE_MAX;
177 :
178 : // Heap memory address.
179 : uint8_t* heap_address_;
180 :
181 : // The heap size in bytes.
182 : size_t heap_size_;
183 :
184 : // The total number of slabs.
185 : size_t slab_count_;
186 :
187 : // The ratio [0 .. 1] of the memory used by the quarantine. Under lock_.
188 : float quarantine_ratio_;
189 :
190 : typedef CircularQueue<size_t, HeapAllocator<size_t>> SlabIndexQueue;
191 :
192 : // Holds the indices of free slabs. Under lock_.
193 : SlabIndexQueue free_slabs_;
194 :
195 : // Holds the indices of the quarantined slabs. Under lock_.
196 : SlabIndexQueue quarantine_;
197 :
198 : typedef std::vector<SlabInfo,
199 : HeapAllocator<SlabInfo>> SlabInfoVector;
200 :
201 : // Holds the information related to slabs. Under lock_.
202 : SlabInfoVector slab_info_;
203 :
204 : // The interface that will be notified of internal memory use. Has its own
205 : // locking.
206 : MemoryNotifierInterface* memory_notifier_;
207 :
208 : // The global lock for this allocator.
209 : ::common::RecursiveLock lock_;
210 :
211 : private:
212 : DISALLOW_COPY_AND_ASSIGN(ZebraBlockHeap);
213 : };
214 :
215 : } // namespace heaps
216 : } // namespace asan
217 : } // namespace agent
218 :
219 : #endif // SYZYGY_AGENT_ASAN_HEAPS_ZEBRA_BLOCK_HEAP_H_
|