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/debug_stack.h"
27 #include "base/logging.h"
28 #include "base/macros.h"
29 #include "base/mutex.h"
30 #include "mem_map.h"
31 
32 namespace art {
33 
34 // Chunk of space.
35 struct SpaceChunk {
36   uint8_t* ptr;
37   size_t size;
38 
StartSpaceChunk39   uintptr_t Start() const {
40     return reinterpret_cast<uintptr_t>(ptr);
41   }
EndSpaceChunk42   uintptr_t End() const {
43     return reinterpret_cast<uintptr_t>(ptr) + size;
44   }
45 };
46 
47 inline bool operator==(const SpaceChunk& lhs, const SpaceChunk& rhs) {
48   return (lhs.size == rhs.size) && (lhs.ptr == rhs.ptr);
49 }
50 
51 class SortChunkByPtr {
52  public:
operator()53   bool operator()(const SpaceChunk& a, const SpaceChunk& b) const {
54     return reinterpret_cast<uintptr_t>(a.ptr) < reinterpret_cast<uintptr_t>(b.ptr);
55   }
56 };
57 
58 // An arena pool that creates arenas backed by an mmaped file.
59 class SwapSpace {
60  public:
61   SwapSpace(int fd, size_t initial_size);
62   ~SwapSpace();
63   void* Alloc(size_t size) LOCKS_EXCLUDED(lock_);
64   void Free(void* ptr, size_t size) LOCKS_EXCLUDED(lock_);
65 
GetSize()66   size_t GetSize() {
67     return size_;
68   }
69 
70  private:
71   SpaceChunk NewFileChunk(size_t min_size);
72 
73   int fd_;
74   size_t size_;
75   std::list<SpaceChunk> maps_;
76 
77   // NOTE: Boost.Bimap would be useful for the two following members.
78 
79   // Map start of a free chunk to its size.
80   typedef std::set<SpaceChunk, SortChunkByPtr> FreeByStartSet;
81   FreeByStartSet free_by_start_ GUARDED_BY(lock_);
82 
83   // Map size to an iterator to free_by_start_'s entry.
84   typedef std::pair<size_t, FreeByStartSet::const_iterator> FreeBySizeEntry;
85   struct FreeBySizeComparator {
operatorFreeBySizeComparator86     bool operator()(const FreeBySizeEntry& lhs, const FreeBySizeEntry& rhs) {
87       if (lhs.first != rhs.first) {
88         return lhs.first < rhs.first;
89       } else {
90         return lhs.second->Start() < rhs.second->Start();
91       }
92     }
93   };
94   typedef std::set<FreeBySizeEntry, FreeBySizeComparator> FreeBySizeSet;
95   FreeBySizeSet free_by_size_ GUARDED_BY(lock_);
96 
97   mutable Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
98   DISALLOW_COPY_AND_ASSIGN(SwapSpace);
99 };
100 
101 template <typename T> class SwapAllocator;
102 
103 template <>
104 class SwapAllocator<void> {
105  public:
106   typedef void value_type;
107   typedef void* pointer;
108   typedef const void* const_pointer;
109 
110   template <typename U>
111   struct rebind {
112     typedef SwapAllocator<U> other;
113   };
114 
SwapAllocator(SwapSpace * swap_space)115   explicit SwapAllocator(SwapSpace* swap_space) : swap_space_(swap_space) {}
116 
117   template <typename U>
SwapAllocator(const SwapAllocator<U> & other)118   SwapAllocator(const SwapAllocator<U>& other) : swap_space_(other.swap_space_) {}
119 
120   SwapAllocator(const SwapAllocator& other) = default;
121   SwapAllocator& operator=(const SwapAllocator& other) = default;
122   ~SwapAllocator() = default;
123 
124  private:
125   SwapSpace* swap_space_;
126 
127   template <typename U>
128   friend class SwapAllocator;
129 };
130 
131 template <typename T>
132 class SwapAllocator {
133  public:
134   typedef T value_type;
135   typedef T* pointer;
136   typedef T& reference;
137   typedef const T* const_pointer;
138   typedef const T& const_reference;
139   typedef size_t size_type;
140   typedef ptrdiff_t difference_type;
141 
142   template <typename U>
143   struct rebind {
144     typedef SwapAllocator<U> other;
145   };
146 
SwapAllocator(SwapSpace * swap_space)147   explicit SwapAllocator(SwapSpace* swap_space) : swap_space_(swap_space) {}
148 
149   template <typename U>
SwapAllocator(const SwapAllocator<U> & other)150   SwapAllocator(const SwapAllocator<U>& other) : swap_space_(other.swap_space_) {}
151 
152   SwapAllocator(const SwapAllocator& other) = default;
153   SwapAllocator& operator=(const SwapAllocator& other) = default;
154   ~SwapAllocator() = default;
155 
max_size()156   size_type max_size() const {
157     return static_cast<size_type>(-1) / sizeof(T);
158   }
159 
address(reference x)160   pointer address(reference x) const { return &x; }
address(const_reference x)161   const_pointer address(const_reference x) const { return &x; }
162 
163   pointer allocate(size_type n, SwapAllocator<void>::pointer hint ATTRIBUTE_UNUSED = nullptr) {
164     DCHECK_LE(n, max_size());
165     if (swap_space_ == nullptr) {
166       return reinterpret_cast<T*>(malloc(n * sizeof(T)));
167     } else {
168       return reinterpret_cast<T*>(swap_space_->Alloc(n * sizeof(T)));
169     }
170   }
deallocate(pointer p,size_type n)171   void deallocate(pointer p, size_type n) {
172     if (swap_space_ == nullptr) {
173       free(p);
174     } else {
175       swap_space_->Free(p, n * sizeof(T));
176     }
177   }
178 
construct(pointer p,const_reference val)179   void construct(pointer p, const_reference val) {
180     new (static_cast<void*>(p)) value_type(val);
181   }
182   template <class U, class... Args>
construct(U * p,Args &&...args)183   void construct(U* p, Args&&... args) {
184     ::new (static_cast<void*>(p)) U(std::forward<Args>(args)...);
185   }
destroy(pointer p)186   void destroy(pointer p) {
187     p->~value_type();
188   }
189 
190   inline bool operator==(SwapAllocator const& other) {
191     return swap_space_ == other.swap_space_;
192   }
193   inline bool operator!=(SwapAllocator const& other) {
194     return !operator==(other);
195   }
196 
197  private:
198   SwapSpace* swap_space_;
199 
200   template <typename U>
201   friend class SwapAllocator;
202 };
203 
204 template <typename T>
205 using SwapVector = std::vector<T, SwapAllocator<T>>;
206 template <typename T, typename Comparator>
207 using SwapSet = std::set<T, Comparator, SwapAllocator<T>>;
208 
209 }  // namespace art
210 
211 #endif  // ART_COMPILER_UTILS_SWAP_SPACE_H_
212