Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
aligned_allocator.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * thrill/mem/aligned_allocator.hpp
3  *
4  * Copied and modified from STXXL https://github.com/stxxl/stxxl, which is
5  * distributed under the Boost Software License, Version 1.0.
6  *
7  * Part of Project Thrill - http://project-thrill.org
8  *
9  * Copyright (C) 2002 Roman Dementiev <[email protected]>
10  * Copyright (C) 2009 Andreas Beckmann <[email protected]>
11  * Copyright (C) 2016 Timo Bingmann <[email protected]>
12  *
13  * All rights reserved. Published under the BSD-2 license in the LICENSE file.
14  ******************************************************************************/
15 
16 #pragma once
17 #ifndef THRILL_MEM_ALIGNED_ALLOCATOR_HEADER
18 #define THRILL_MEM_ALIGNED_ALLOCATOR_HEADER
19 
20 #include <thrill/common/logger.hpp>
22 
23 #include <cassert>
24 #include <cstdlib>
25 #include <memory>
26 
27 #define THRILL_DEFAULT_ALIGN 4096
28 
29 namespace thrill {
30 namespace mem {
31 
32 template <typename MustBeInt>
34  static bool may_use_realloc_;
35 };
36 
37 template <typename MustBeInt>
39 
40 template <typename Type = char,
41  typename BaseAllocator = std::allocator<char>,
42  size_t Alignment = THRILL_DEFAULT_ALIGN>
44 {
45  static constexpr bool debug = false;
46 
47  static_assert(sizeof(typename BaseAllocator::value_type) == 1,
48  "BaseAllocator must be a char/byte allocator");
49 
50 public:
51  using value_type = Type;
52  using pointer = Type *;
53  using const_pointer = const Type *;
54  using reference = Type &;
55  using const_reference = const Type &;
56  using size_type = std::size_t;
57  using difference_type = std::ptrdiff_t;
58 
59  //! C++11 type flag
60  using is_always_equal = std::false_type;
61 
62  //! Return allocator for different type.
63  template <typename U>
65 
66  //! Construct with base allocator
67  explicit AlignedAllocator(const BaseAllocator& base = BaseAllocator())
68  : base_(base) { }
69 
70  //! copy-constructor
71  AlignedAllocator(const AlignedAllocator&) noexcept = default;
72 
73  //! copy-constructor from a rebound allocator
74  template <typename OtherType>
75  AlignedAllocator(const AlignedAllocator<OtherType>& other) noexcept
76  : base_(other.base()) { }
77 
78  //! copy-assignment operator
79  AlignedAllocator& operator = (const AlignedAllocator&) noexcept = default;
80 
81  //! Attempts to allocate a block of storage with a size large enough to
82  //! contain n elements of member type value_type, and returns a pointer to
83  //! the first element.
84  pointer allocate(size_type n, const void* /* hint */ = nullptr) {
85  if (n > this->max_size())
86  throw std::bad_alloc();
87 
88  return static_cast<pointer>(allocate_bytes(n * sizeof(Type)));
89  }
90 
91  //! Releases a block of storage previously allocated with member allocate
92  //! and not yet released.
93  void deallocate(pointer p, size_type n) noexcept {
94  deallocate_bytes(p, n * sizeof(Type));
95  }
96 
97  //! Compare to another allocator of same type
98  template <typename Other>
99  bool operator == (const AlignedAllocator<Other>& other) const noexcept {
100  return (base_ == other.base_);
101  }
102 
103  //! Compare to another allocator of same type
104  template <typename Other>
105  bool operator != (const AlignedAllocator<Other>& other) const noexcept {
106  return (base_ != other.base_);
107  }
108 
109  /**************************************************************************/
110 
111  void * allocate_bytes(size_t size, size_t meta_info_size = 0);
112  void deallocate_bytes(void* ptr, size_t size, size_t meta_info_size = 0) noexcept;
113 
114  const BaseAllocator& base() const { return base_; }
115 
116 private:
117  //! base allocator
118  BaseAllocator base_;
119 };
120 
121 // meta_info_size > 0 is needed for array allocations that have overhead
122 //
123 // meta_info
124 // aligned begin of data unallocated behind data
125 // v v v
126 // ----===============#MMMM========================------
127 // ^ ^^ ^
128 // buffer result result+m_i_size+size
129 // pointer to buffer
130 // (---) unallocated, (===) allocated memory
131 
132 template <typename Type, typename BaseAllocator, size_t Alignment>
134  size_t size, size_t meta_info_size) {
135 
136  LOG << "aligned_alloc<" << Alignment << ">(), size = " << size
137  << ", meta info size = " << meta_info_size;
138 
139  // malloc()/realloc() variant that frees the unused amount of memory
140  // after the data area of size 'size'. realloc() from valgrind does not
141  // preserve the old memory area when shrinking, so out-of-bounds
142  // accesses can't be detected easily.
143  // Overhead: about Alignment bytes.
144  size_t alloc_size = Alignment + sizeof(char*) + meta_info_size + size;
145  char* buffer = reinterpret_cast<char*>(base_.allocate(alloc_size));
146 
147  if (buffer == nullptr)
148  return nullptr;
149 
150  char* reserve_buffer = buffer + sizeof(char*) + meta_info_size;
151  char* result = reserve_buffer + Alignment -
152  (((size_t)reserve_buffer) % (Alignment)) - meta_info_size;
153 
154  LOG << "aligned_alloc<" << Alignment << ">() address " << static_cast<void*>(result)
155  << " lost " << (result - buffer) << " bytes";
156 
157  // -tb: check that there is space for one char* before the "result" pointer
158  // delivered to the user. this char* is set below to the beginning of the
159  // allocated area.
160  assert(long(result - buffer) >= long(sizeof(char*)));
161 
162 #if 0
163  // free unused memory behind the data area
164  // so access behind the requested size can be recognized
165  size_t realloc_size = (result - buffer) + meta_info_size + size;
166  if (realloc_size < alloc_size && AlignedAllocatorSettings<int>::may_use_realloc_) {
167  char* realloced = static_cast<char*>(std::realloc(buffer, realloc_size));
168  if (buffer != realloced) {
169  // hmm, realloc does move the memory block around while shrinking,
170  // might run under valgrind, so disable realloc and retry
171  LOG1 << "mem::aligned_alloc: disabling realloc()";
172  std::free(realloced);
174  return allocate(size, meta_info_size);
175  }
176  assert(result + size <= buffer + realloc_size);
177  }
178 #endif
179 
180  *((reinterpret_cast<char**>(result)) - 1) = buffer;
181  LOG << "aligned_alloc<" << Alignment << ">(), allocated at "
182  << static_cast<void*>(buffer) << " returning " << static_cast<void*>(result);
183  LOG << "aligned_alloc<" << Alignment << ">(size = " << size
184  << ", meta info size = " << meta_info_size
185  << ") => buffer = " << static_cast<void*>(buffer)
186  << ", ptr = " << static_cast<void*>(result);
187 
188  return result;
189 }
190 
191 template <typename Type, typename BaseAllocator, size_t Alignment>
193  void* ptr, size_t size, size_t meta_info_size) noexcept {
194  if (!ptr)
195  return;
196  char* buffer = *((reinterpret_cast<char**>(ptr)) - 1);
197  size_t alloc_size = Alignment + sizeof(char*) + meta_info_size + size;
198  LOG0 << "aligned_dealloc<" << Alignment << ">(), ptr = " << ptr
199  << ", buffer = " << static_cast<void*>(buffer);
200  base_.deallocate(buffer, alloc_size);
201 }
202 
203 /******************************************************************************/
204 // default aligned allocation methods
205 
206 static inline
207 void * aligned_alloc(size_t size, size_t meta_info_size = 0) {
208  return AlignedAllocator<>().allocate_bytes(size, meta_info_size);
209 }
210 
211 static inline
212 void aligned_dealloc(void* ptr, size_t size, size_t meta_info_size = 0) {
213  return AlignedAllocator<>().deallocate_bytes(ptr, size, meta_info_size);
214 }
215 
216 } // namespace mem
217 } // namespace thrill
218 
219 #endif // !THRILL_MEM_ALIGNED_ALLOCATOR_HEADER
220 
221 /******************************************************************************/
void deallocate_bytes(void *ptr, size_t size, size_t meta_info_size=0) noexcept
AlignedAllocator & operator=(const AlignedAllocator &) noexcept=default
copy-assignment operator
#define LOG1
Definition: logger.hpp:28
static void * aligned_alloc(size_t size, size_t meta_info_size=0)
const BaseAllocator & base() const
#define LOG0
Override default output: never or always output log.
Definition: logger.hpp:27
Type
VFS object type.
Definition: file_io.hpp:52
void * allocate_bytes(size_t size, size_t meta_info_size=0)
#define THRILL_DEFAULT_ALIGN
AlignedAllocator(const BaseAllocator &base=BaseAllocator())
Construct with base allocator.
size_type max_size() const noexcept
Maximum size possible to allocate.
bool operator!=(const AlignedAllocator< Other > &other) const noexcept
Compare to another allocator of same type.
static void aligned_dealloc(void *ptr, size_t size, size_t meta_info_size=0)
BaseAllocator base_
base allocator
pointer allocate(size_type n, const void *=nullptr)
void free(void *ptr) NOEXCEPT
exported free symbol that overrides loading from libc
#define LOG
Default logging method: output if the local debug variable is true.
Definition: logger.hpp:24
bool operator==(const AlignedAllocator< Other > &other) const noexcept
Compare to another allocator of same type.
void * realloc(void *ptr, size_t size) NOEXCEPT
exported realloc() symbol that overrides loading from libc
void deallocate(pointer p, size_type n) noexcept
Return allocator for different type.