1// Copyright (c) 2011 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef COURGETTE_MEMORY_ALLOCATOR_H_
6#define COURGETTE_MEMORY_ALLOCATOR_H_
7
8#include <memory>
9
10#include "base/basictypes.h"
11#include "base/files/file_path.h"
12#include "base/logging.h"
13#include "base/platform_file.h"
14
15#ifndef NDEBUG
16
17// A helper class to track down call sites that are not handling error cases.
18template<class T>
19class CheckReturnValue {
20 public:
21  // Not marked explicit on purpose.
22  CheckReturnValue(T value) : value_(value), checked_(false) {  // NOLINT
23  }
24  CheckReturnValue(const CheckReturnValue& other)
25      : value_(other.value_), checked_(other.checked_) {
26    other.checked_ = true;
27  }
28
29  CheckReturnValue& operator=(const CheckReturnValue& other) {
30    if (this != &other) {
31      DCHECK(checked_);
32      value_ = other.value_;
33      checked_ = other.checked_;
34      other.checked_ = true;
35    }
36  }
37
38  ~CheckReturnValue() {
39    DCHECK(checked_);
40  }
41
42  operator const T&() const {
43    checked_ = true;
44    return value_;
45  }
46
47 private:
48  T value_;
49  mutable bool checked_;
50};
51typedef CheckReturnValue<bool> CheckBool;
52#else
53typedef bool CheckBool;
54#endif
55
56namespace courgette {
57
58#if defined(OS_WIN)
59
60// Manages a temporary file.  The file is created in the %TEMP% folder and
61// is deleted when the file handle is closed.
62// NOTE: Since the file will be used as backing for a memory allocation,
63// it will never be so big that size_t cannot represent its size.
64class TempFile {
65 public:
66  TempFile();
67  ~TempFile();
68
69  bool Create();
70  void Close();
71  bool SetSize(size_t size);
72
73  // Returns true iff the temp file is currently open.
74  bool valid() const;
75
76  // Returns the handle of the temporary file or INVALID_HANDLE_VALUE if
77  // a temp file has not been created.
78  base::PlatformFile handle() const;
79
80 protected:
81  base::PlatformFile file_;
82};
83
84// Manages a read/write virtual mapping of a physical file.
85class FileMapping {
86 public:
87  FileMapping();
88  ~FileMapping();
89
90  // Map a file from beginning to |size|.
91  bool Create(HANDLE file, size_t size);
92  void Close();
93
94  // Returns true iff a mapping has been created.
95  bool valid() const;
96
97  // Returns a writable pointer to the beginning of the memory mapped file.
98  // If Create has not been called successfully, return value is NULL.
99  void* view() const;
100
101 protected:
102  bool InitializeView(size_t size);
103
104  HANDLE mapping_;
105  void* view_;
106};
107
108// Manages a temporary file and a memory mapping of the temporary file.
109// The memory that this class manages holds a pointer back to the TempMapping
110// object itself, so that given a memory pointer allocated by this class,
111// you can get a pointer to the TempMapping instance that owns that memory.
112class TempMapping {
113 public:
114  TempMapping();
115  ~TempMapping();
116
117  // Creates a temporary file of size |size| and maps it into the current
118  // process's address space.
119  bool Initialize(size_t size);
120
121  // Returns a writable pointer to the reserved memory.
122  void* memory() const;
123
124  // Returns true if the mapping is valid and memory is available.
125  bool valid() const;
126
127  // Returns a pointer to the TempMapping instance that allocated the |mem|
128  // block of memory.  It's the callers responsibility to make sure that
129  // the memory block was allocated by the TempMapping class.
130  static TempMapping* GetMappingFromPtr(void* mem);
131
132 protected:
133  TempFile file_;
134  FileMapping mapping_;
135};
136
137// A memory allocator class that allocates memory either from the heap or via a
138// temporary file.  The interface is STL inspired but the class does not throw
139// STL exceptions on allocation failure.  Instead it returns NULL.
140// A file allocation will be made if either the requested memory size exceeds
141// |kMaxHeapAllocationSize| or if a heap allocation fails.
142// Allocating the memory as a mapping of a temporary file solves the problem
143// that there might not be enough physical memory and pagefile to support the
144// allocation.  This can happen because these resources are too small, or
145// already committed to other processes.  Provided there is enough disk, the
146// temporary file acts like a pagefile that other processes can't access.
147template<class T>
148class MemoryAllocator {
149 public:
150  typedef T value_type;
151  typedef value_type* pointer;
152  typedef value_type& reference;
153  typedef const value_type* const_pointer;
154  typedef const value_type& const_reference;
155  typedef size_t size_type;
156  typedef ptrdiff_t difference_type;
157
158  // Each allocation is tagged with a single byte so that we know how to
159  // deallocate it.
160  enum AllocationType {
161    HEAP_ALLOCATION,
162    FILE_ALLOCATION,
163  };
164
165  // 5MB is the maximum heap allocation size that we'll attempt.
166  // When applying a patch for Chrome 10.X we found that at this
167  // threshold there were 17 allocations higher than this threshold
168  // (largest at 136MB) 10 allocations just below the threshold and 6362
169  // smaller allocations.
170  static const size_t kMaxHeapAllocationSize = 1024 * 1024 * 5;
171
172  template<class OtherT>
173  struct rebind {
174    // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
175    typedef MemoryAllocator<OtherT> other;
176  };
177
178  MemoryAllocator() _THROW0() {
179  }
180
181  // We can't use an explicit constructor here, as dictated by our style guide.
182  // The implementation of basic_string in Visual Studio 2010 prevents this.
183  MemoryAllocator(const MemoryAllocator<T>& other) _THROW0() {  // NOLINT
184  }
185
186  template<class OtherT>
187  MemoryAllocator(const MemoryAllocator<OtherT>& other) _THROW0() {  // NOLINT
188  }
189
190  ~MemoryAllocator() {
191  }
192
193  void deallocate(pointer ptr, size_type size) {
194    uint8* mem = reinterpret_cast<uint8*>(ptr);
195    mem -= sizeof(T);
196    if (mem[0] == HEAP_ALLOCATION) {
197      delete [] mem;
198    } else {
199      DCHECK_EQ(static_cast<uint8>(FILE_ALLOCATION), mem[0]);
200      TempMapping* mapping = TempMapping::GetMappingFromPtr(mem);
201      delete mapping;
202    }
203  }
204
205  pointer allocate(size_type count) {
206    // We use the first byte of each allocation to mark the allocation type.
207    // However, so that the allocation is properly aligned, we allocate an
208    // extra element and then use the first byte of the first element
209    // to mark the allocation type.
210    count++;
211
212    if (count > max_size())
213      return NULL;
214
215    size_type bytes = count * sizeof(T);
216    uint8* mem = NULL;
217
218    // First see if we can do this allocation on the heap.
219    if (count < kMaxHeapAllocationSize)
220      mem = new(std::nothrow) uint8[bytes];
221    if (mem != NULL) {
222      mem[0] = static_cast<uint8>(HEAP_ALLOCATION);
223    } else {
224      // If either the heap allocation failed or the request exceeds the
225      // max heap allocation threshold, we back the allocation with a temp file.
226      TempMapping* mapping = new(std::nothrow) TempMapping();
227      if (mapping && mapping->Initialize(bytes)) {
228        mem = reinterpret_cast<uint8*>(mapping->memory());
229        mem[0] = static_cast<uint8>(FILE_ALLOCATION);
230      }
231    }
232    return mem ? reinterpret_cast<pointer>(mem + sizeof(T)) : NULL;
233  }
234
235  pointer allocate(size_type count, const void* hint) {
236    return allocate(count);
237  }
238
239  void construct(pointer ptr, const T& value) {
240    ::new(ptr) T(value);
241  }
242
243  void destroy(pointer ptr) {
244    ptr->~T();
245  }
246
247  size_type max_size() const _THROW0() {
248    size_type count = static_cast<size_type>(-1) / sizeof(T);
249    return (0 < count ? count : 1);
250  }
251};
252
253#else  // OS_WIN
254
255// On Mac, Linux, we use a bare bones implementation that only does
256// heap allocations.
257template<class T>
258class MemoryAllocator {
259 public:
260  typedef T value_type;
261  typedef value_type* pointer;
262  typedef value_type& reference;
263  typedef const value_type* const_pointer;
264  typedef const value_type& const_reference;
265  typedef size_t size_type;
266  typedef ptrdiff_t difference_type;
267
268  template<class OtherT>
269  struct rebind {
270    // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
271    typedef MemoryAllocator<OtherT> other;
272  };
273
274  MemoryAllocator() {
275  }
276
277  explicit MemoryAllocator(const MemoryAllocator<T>& other) {
278  }
279
280  template<class OtherT>
281  explicit MemoryAllocator(const MemoryAllocator<OtherT>& other) {
282  }
283
284  ~MemoryAllocator() {
285  }
286
287  void deallocate(pointer ptr, size_type size) {
288    delete [] ptr;
289  }
290
291  pointer allocate(size_type count) {
292    if (count > max_size())
293      return NULL;
294    return reinterpret_cast<pointer>(
295        new(std::nothrow) uint8[count * sizeof(T)]);
296  }
297
298  pointer allocate(size_type count, const void* hint) {
299    return allocate(count);
300  }
301
302  void construct(pointer ptr, const T& value) {
303    ::new(ptr) T(value);
304  }
305
306  void destroy(pointer ptr) {
307    ptr->~T();
308  }
309
310  size_type max_size() const {
311    size_type count = static_cast<size_type>(-1) / sizeof(T);
312    return (0 < count ? count : 1);
313  }
314};
315
316#endif  // OS_WIN
317
318// Manages a growable buffer.  The buffer allocation is done by the
319// MemoryAllocator class.  This class will not throw exceptions so call sites
320// must be prepared to handle memory allocation failures.
321// The interface is STL inspired to avoid having to make too many changes
322// to code that previously was using STL.
323template<typename T, class Allocator = MemoryAllocator<T> >
324class NoThrowBuffer {
325 public:
326  typedef T value_type;
327  static const size_t kAllocationFailure = 0xffffffff;
328  static const size_t kStartSize = sizeof(T) > 0x100 ? 1 : 0x100 / sizeof(T);
329
330  NoThrowBuffer() : buffer_(NULL), size_(0), alloc_size_(0) {
331  }
332
333  ~NoThrowBuffer() {
334    clear();
335  }
336
337  void clear() {
338    if (buffer_) {
339      alloc_.deallocate(buffer_, alloc_size_);
340      buffer_ = NULL;
341      size_ = 0;
342      alloc_size_ = 0;
343    }
344  }
345
346  bool empty() const {
347    return size_ == 0;
348  }
349
350  CheckBool reserve(size_t size) WARN_UNUSED_RESULT {
351    if (failed())
352      return false;
353
354    if (size <= alloc_size_)
355      return true;
356
357    if (size < kStartSize)
358      size = kStartSize;
359
360    T* new_buffer = alloc_.allocate(size);
361    if (!new_buffer) {
362      clear();
363      alloc_size_ = kAllocationFailure;
364    } else {
365      if (buffer_) {
366        memcpy(new_buffer, buffer_, size_ * sizeof(T));
367        alloc_.deallocate(buffer_, alloc_size_);
368      }
369      buffer_ = new_buffer;
370      alloc_size_ = size;
371    }
372
373    return !failed();
374  }
375
376  CheckBool append(const T* data, size_t size) WARN_UNUSED_RESULT {
377    if (failed())
378      return false;
379
380    if (size > alloc_.max_size() - size_)
381      return false;
382
383    if (!size)
384      return true;
385
386    if ((alloc_size_ - size_) < size) {
387      const size_t max_size = alloc_.max_size();
388      size_t new_size = alloc_size_ ? alloc_size_ : kStartSize;
389      while (new_size < size_ + size) {
390        if (new_size < max_size - new_size) {
391          new_size *= 2;
392        } else {
393          new_size = max_size;
394        }
395      }
396      if (!reserve(new_size))
397        return false;
398    }
399
400    memcpy(buffer_ + size_, data, size * sizeof(T));
401    size_ += size;
402
403    return true;
404  }
405
406  CheckBool resize(size_t size, const T& init_value) WARN_UNUSED_RESULT {
407    if (size > size_) {
408      if (!reserve(size))
409        return false;
410      for (size_t i = size_; i < size; ++i)
411        buffer_[i] = init_value;
412    } else if (size < size_) {
413      // TODO(tommi): Should we allocate a new, smaller buffer?
414      // It might be faster for us to simply change the size.
415    }
416
417    size_ = size;
418
419    return true;
420  }
421
422  CheckBool push_back(const T& item) WARN_UNUSED_RESULT {
423    return append(&item, 1);
424  }
425
426  const T& back() const {
427    return buffer_[size_ - 1];
428  }
429
430  T& back() {
431    return buffer_[size_ - 1];
432  }
433
434  const T* begin() const {
435    if (!size_)
436      return NULL;
437    return &buffer_[0];
438  }
439
440  T* begin() {
441    if (!size_)
442      return NULL;
443    return &buffer_[0];
444  }
445
446  const T* end() const {
447    if (!size_)
448      return NULL;
449    return &buffer_[size_ - 1];
450  }
451
452  T* end() {
453    if (!size_)
454      return NULL;
455    return &buffer_[size_ - 1];
456  }
457
458  const T& operator[](size_t index) const {
459    DCHECK(index < size_);
460    return buffer_[index];
461  }
462
463  T& operator[](size_t index) {
464    DCHECK(index < size_);
465    return buffer_[index];
466  }
467
468  size_t size() const {
469    return size_;
470  }
471
472  T* data() const {
473    return buffer_;
474  }
475
476  // Returns true if an allocation failure has ever occurred for this object.
477  bool failed() const {
478    return alloc_size_ == kAllocationFailure;
479  }
480
481 protected:
482  T* buffer_;
483  size_t size_;  // how much of the buffer we're using.
484  size_t alloc_size_;  // how much space we have allocated.
485  Allocator alloc_;
486};
487
488}  // namespace courgette
489
490#endif  // COURGETTE_MEMORY_ALLOCATOR_H_
491