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