1 /*
2  * Copyright (C) 2014 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_COMPILER_UTILS_SWAP_SPACE_H_
18 #define ART_COMPILER_UTILS_SWAP_SPACE_H_
19 
20 #include <cstdlib>
21 #include <list>
22 #include <set>
23 #include <stdint.h>
24 #include <stddef.h>
25 
26 #include "base/logging.h"
27 #include "base/macros.h"
28 #include "base/mutex.h"
29 #include "mem_map.h"
30 #include "utils.h"
31 #include "utils/debug_stack.h"
32 
33 namespace art {
34 
35 // Chunk of space.
36 struct SpaceChunk {
37   uint8_t* ptr;
38   size_t size;
39 
StartSpaceChunk40   uintptr_t Start() const {
41     return reinterpret_cast<uintptr_t>(ptr);
42   }
EndSpaceChunk43   uintptr_t End() const {
44     return reinterpret_cast<uintptr_t>(ptr) + size;
45   }
46 };
47 
48 inline bool operator==(const SpaceChunk& lhs, const SpaceChunk& rhs) {
49   return (lhs.size == rhs.size) && (lhs.ptr == rhs.ptr);
50 }
51 
52 class SortChunkByPtr {
53  public:
operator()54   bool operator()(const SpaceChunk& a, const SpaceChunk& b) const {
55     return reinterpret_cast<uintptr_t>(a.ptr) < reinterpret_cast<uintptr_t>(b.ptr);
56   }
57 };
58 
59 // An arena pool that creates arenas backed by an mmaped file.
60 class SwapSpace {
61  public:
62   SwapSpace(int fd, size_t initial_size);
63   ~SwapSpace();
64   void* Alloc(size_t size) LOCKS_EXCLUDED(lock_);
65   void Free(void* ptr, size_t size) LOCKS_EXCLUDED(lock_);
66 
GetSize()67   size_t GetSize() {
68     return size_;
69   }
70 
71  private:
72   SpaceChunk NewFileChunk(size_t min_size);
73 
74   int fd_;
75   size_t size_;
76   std::list<SpaceChunk> maps_;
77 
78   // NOTE: Boost.Bimap would be useful for the two following members.
79 
80   // Map start of a free chunk to its size.
81   typedef std::set<SpaceChunk, SortChunkByPtr> FreeByStartSet;
82   FreeByStartSet free_by_start_ GUARDED_BY(lock_);
83 
84   // Map size to an iterator to free_by_start_'s entry.
85   typedef std::pair<size_t, FreeByStartSet::const_iterator> FreeBySizeEntry;
86   struct FreeBySizeComparator {
operatorFreeBySizeComparator87     bool operator()(const FreeBySizeEntry& lhs, const FreeBySizeEntry& rhs) {
88       if (lhs.first != rhs.first) {
89         return lhs.first < rhs.first;
90       } else {
91         return lhs.second->Start() < rhs.second->Start();
92       }
93     }
94   };
95   typedef std::set<FreeBySizeEntry, FreeBySizeComparator> FreeBySizeSet;
96   FreeBySizeSet free_by_size_ GUARDED_BY(lock_);
97 
98   mutable Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
99   DISALLOW_COPY_AND_ASSIGN(SwapSpace);
100 };
101 
102 template <typename T> class SwapAllocator;
103 
104 template <>
105 class SwapAllocator<void> {
106  public:
107   typedef void value_type;
108   typedef void* pointer;
109   typedef const void* const_pointer;
110 
111   template <typename U>
112   struct rebind {
113     typedef SwapAllocator<U> other;
114   };
115 
SwapAllocator(SwapSpace * swap_space)116   explicit SwapAllocator(SwapSpace* swap_space) : swap_space_(swap_space) {}
117 
118   template <typename U>
SwapAllocator(const SwapAllocator<U> & other)119   SwapAllocator(const SwapAllocator<U>& other) : swap_space_(other.swap_space_) {}
120 
121   SwapAllocator(const SwapAllocator& other) = default;
122   SwapAllocator& operator=(const SwapAllocator& other) = default;
123   ~SwapAllocator() = default;
124 
125  private:
126   SwapSpace* swap_space_;
127 
128   template <typename U>
129   friend class SwapAllocator;
130 };
131 
132 template <typename T>
133 class SwapAllocator {
134  public:
135   typedef T value_type;
136   typedef T* pointer;
137   typedef T& reference;
138   typedef const T* const_pointer;
139   typedef const T& const_reference;
140   typedef size_t size_type;
141   typedef ptrdiff_t difference_type;
142 
143   template <typename U>
144   struct rebind {
145     typedef SwapAllocator<U> other;
146   };
147 
SwapAllocator(SwapSpace * swap_space)148   explicit SwapAllocator(SwapSpace* swap_space) : swap_space_(swap_space) {}
149 
150   template <typename U>
SwapAllocator(const SwapAllocator<U> & other)151   SwapAllocator(const SwapAllocator<U>& other) : swap_space_(other.swap_space_) {}
152 
153   SwapAllocator(const SwapAllocator& other) = default;
154   SwapAllocator& operator=(const SwapAllocator& other) = default;
155   ~SwapAllocator() = default;
156 
max_size()157   size_type max_size() const {
158     return static_cast<size_type>(-1) / sizeof(T);
159   }
160 
address(reference x)161   pointer address(reference x) const { return &x; }
address(const_reference x)162   const_pointer address(const_reference x) const { return &x; }
163 
164   pointer allocate(size_type n, SwapAllocator<void>::pointer hint = nullptr) {
165     DCHECK_LE(n, max_size());
166     if (swap_space_ == nullptr) {
167       return reinterpret_cast<T*>(malloc(n * sizeof(T)));
168     } else {
169       return reinterpret_cast<T*>(swap_space_->Alloc(n * sizeof(T)));
170     }
171   }
deallocate(pointer p,size_type n)172   void deallocate(pointer p, size_type n) {
173     if (swap_space_ == nullptr) {
174       free(p);
175     } else {
176       swap_space_->Free(p, n * sizeof(T));
177     }
178   }
179 
construct(pointer p,const_reference val)180   void construct(pointer p, const_reference val) {
181     new (static_cast<void*>(p)) value_type(val);
182   }
183   template <class U, class... Args>
construct(U * p,Args &&...args)184   void construct(U* p, Args&&... args) {
185     ::new (static_cast<void*>(p)) U(std::forward<Args>(args)...);
186   }
destroy(pointer p)187   void destroy(pointer p) {
188     p->~value_type();
189   }
190 
191   inline bool operator==(SwapAllocator const& other) {
192     return swap_space_ == other.swap_space_;
193   }
194   inline bool operator!=(SwapAllocator const& other) {
195     return !operator==(other);
196   }
197 
198  private:
199   SwapSpace* swap_space_;
200 
201   template <typename U>
202   friend class SwapAllocator;
203 };
204 
205 template <typename T>
206 using SwapVector = std::vector<T, SwapAllocator<T>>;
207 template <typename T, typename Comparator>
208 using SwapSet = std::set<T, Comparator, SwapAllocator<T>>;
209 
210 }  // namespace art
211 
212 #endif  // ART_COMPILER_UTILS_SWAP_SPACE_H_
213