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 GetHeapFeatures() const;
100 : virtual void* Allocate(size_t bytes);
101 : virtual bool Free(void* alloc);
102 : virtual bool IsAllocated(const void* alloc);
103 : virtual size_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(size_t size,
112 : size_t min_left_redzone_size,
113 : size_t min_right_redzone_size,
114 : BlockLayout* layout);
115 : virtual bool FreeBlock(const BlockInfo& block_info);
116 : // @}
117 :
118 : // @name BlockQuarantineInterface functions.
119 : // @{
120 : virtual bool Push(const CompactBlockInfo& info);
121 : virtual bool Pop(CompactBlockInfo* info);
122 : virtual void Empty(std::vector<CompactBlockInfo>* infos);
123 : virtual size_t GetCount();
124 E : virtual size_t GetLockId(const CompactBlockInfo& info) {
125 E : return 0;
126 E : }
127 E : virtual void Lock(size_t id) { }
128 E : virtual void Unlock(size_t id) { }
129 : // @}
130 :
131 : // Get the ratio of the memory used by the quarantine.
132 E : float quarantine_ratio() const { return quarantine_ratio_; }
133 :
134 : // Set the ratio of the memory used by the quarantine.
135 : void set_quarantine_ratio(float quarantine_ratio);
136 :
137 : protected:
138 : // The set of possible states of the slabs.
139 : enum SlabState {
140 : kFreeSlab,
141 : kAllocatedSlab,
142 : kQuarantinedSlab
143 : };
144 :
145 : struct SlabInfo {
146 : // The state of the slab.
147 : SlabState state;
148 : // Information about the allocation.
149 : CompactBlockInfo info;
150 : };
151 :
152 : // Performs an allocation, and returns a pointer to the SlabInfo where the
153 : // allocation was made.
154 : SlabInfo* AllocateImpl(size_t bytes);
155 :
156 : // Checks if the quarantine invariant is satisfied.
157 : // @returns true if the quarantine invariant is satisfied, false otherwise.
158 : bool QuarantineInvariantIsSatisfied();
159 :
160 : // Gives the 0-based index of the slab containing 'address'.
161 : // @param address address.
162 : // @returns The 0-based index of the slab containing 'address', or
163 : // kInvalidSlab index if the address is not valid.
164 : size_t GetSlabIndex(const void* address);
165 :
166 : // Gives the addres of the given slab.
167 : // @param index 0-based index of the slab.
168 : // @returns The address of the slab, or NULL if the index is invalid.
169 : uint8* GetSlabAddress(size_t index);
170 :
171 : // Defines an invalid slab index.
172 : static const size_t kInvalidSlabIndex = SIZE_MAX;
173 :
174 : // Heap memory address.
175 : uint8* heap_address_;
176 :
177 : // The heap size in bytes.
178 : size_t heap_size_;
179 :
180 : // The total number of slabs.
181 : size_t slab_count_;
182 :
183 : // The ratio [0 .. 1] of the memory used by the quarantine. Under lock_.
184 : float quarantine_ratio_;
185 :
186 : typedef CircularQueue<size_t, HeapAllocator<size_t>> SlabIndexQueue;
187 :
188 : // Holds the indices of free slabs. Under lock_.
189 : SlabIndexQueue free_slabs_;
190 :
191 : // Holds the indices of the quarantined slabs. Under lock_.
192 : SlabIndexQueue quarantine_;
193 :
194 : typedef std::vector<SlabInfo,
195 : HeapAllocator<SlabInfo>> SlabInfoVector;
196 :
197 : // Holds the information related to slabs. Under lock_.
198 : SlabInfoVector slab_info_;
199 :
200 : // The interface that will be notified of internal memory use. Has its own
201 : // locking.
202 : MemoryNotifierInterface* memory_notifier_;
203 :
204 : // The global lock for this allocator.
205 : ::common::RecursiveLock lock_;
206 :
207 : private:
208 : DISALLOW_COPY_AND_ASSIGN(ZebraBlockHeap);
209 : };
210 :
211 : } // namespace heaps
212 : } // namespace asan
213 : } // namespace agent
214 :
215 : #endif // SYZYGY_AGENT_ASAN_HEAPS_ZEBRA_BLOCK_HEAP_H_
|