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