The Tor Browser / file revision

 // Copyright (c) 2009, Google Inc.

 // All rights reserved.

 //

 // Redistribution and use in source and binary forms, with or without

 // modification, are permitted provided that the following conditions are

 // met:

 //

 //     * Redistributions of source code must retain the above copyright

 // notice, this list of conditions and the following disclaimer.

 //     * Redistributions in binary form must reproduce the above

 // copyright notice, this list of conditions and the following disclaimer

 // in the documentation and/or other materials provided with the

 // distribution.

 //     * Neither the name of Google Inc. nor the names of its

 // contributors may be used to endorse or promote products derived from

 // this software without specific prior written permission.

 //

 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 #ifndef GOOGLE_BREAKPAD_COMMON_MEMORY_H_

 #define GOOGLE_BREAKPAD_COMMON_MEMORY_H_

 #include <stdint.h>

 #include <stdlib.h>

 #include <unistd.h>

 #include <sys/mman.h>

 #ifdef __APPLE__

 #define sys_mmap mmap

 #define sys_mmap2 mmap

 #define sys_munmap munmap

 #define MAP_ANONYMOUS MAP_ANON

 #else

 #include "third_party/lss/linux_syscall_support.h"

 #endif

 namespace google_breakpad {

 // This is very simple allocator which fetches pages from the kernel directly.

 // Thus, it can be used even when the heap may be corrupted.

 //

 // There is no free operation. The pages are only freed when the object is

 // destroyed.

 class PageAllocator {

  public:

   PageAllocator()

       : page_size_(getpagesize()),

         last_(NULL),

         current_page_(NULL),

         page_offset_(0) {

   }

   ~PageAllocator() {

     FreeAll();

   }

   void *Alloc(unsigned bytes) {

     if (!bytes)

       return NULL;

     if (current_page_ && page_size_ - page_offset_ >= bytes) {

       uint8_t *const ret = current_page_ + page_offset_;

       page_offset_ += bytes;

       if (page_offset_ == page_size_) {

         page_offset_ = 0;

         current_page_ = NULL;

       }

       return ret;

     }

     const unsigned pages =

         (bytes + sizeof(PageHeader) + page_size_ - 1) / page_size_;

     uint8_t *const ret = GetNPages(pages);

     if (!ret)

       return NULL;

     page_offset_ = (page_size_ - (page_size_ * pages - (bytes + sizeof(PageHeader)))) % page_size_;

     current_page_ = page_offset_ ? ret + page_size_ * (pages - 1) : NULL;

     return ret + sizeof(PageHeader);

   }

  private:

   uint8_t *GetNPages(unsigned num_pages) {

 #ifdef __x86_64

     void *a = sys_mmap(NULL, page_size_ * num_pages, PROT_READ | PROT_WRITE,

                        MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

 #else

     void *a = sys_mmap2(NULL, page_size_ * num_pages, PROT_READ | PROT_WRITE,

                         MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

 #endif

     if (a == MAP_FAILED)

       return NULL;

     struct PageHeader *header = reinterpret_cast<PageHeader*>(a);

     header->next = last_;

     header->num_pages = num_pages;

     last_ = header;

     return reinterpret_cast<uint8_t*>(a);

   }

   void FreeAll() {

     PageHeader *next;

     for (PageHeader *cur = last_; cur; cur = next) {

       next = cur->next;

       sys_munmap(cur, cur->num_pages * page_size_);

     }

   }

   struct PageHeader {

     PageHeader *next;  // pointer to the start of the next set of pages.

     unsigned num_pages;  // the number of pages in this set.

   };

   const unsigned page_size_;

   PageHeader *last_;

   uint8_t *current_page_;

   unsigned page_offset_;

 };

 // A wasteful vector is like a normal std::vector, except that it's very much

 // simplier and it allocates memory from a PageAllocator. It's wasteful

 // because, when resizing, it always allocates a whole new array since the

 // PageAllocator doesn't support realloc.

 template<class T>

 class wasteful_vector {

  public:

   wasteful_vector(PageAllocator *allocator, unsigned size_hint = 16)

       : allocator_(allocator),

         a_((T*) allocator->Alloc(sizeof(T) * size_hint)),

         allocated_(size_hint),

         used_(0) {

   }

   T& back() {

     return a_[used_ - 1];

   }

   const T& back() const {

     return a_[used_ - 1];

   }

   bool empty() const {

     return used_ == 0;

   }

   void push_back(const T& new_element) {

     if (used_ == allocated_)

       Realloc(allocated_ * 2);

     a_[used_++] = new_element;

   }

   size_t size() const {

     return used_;

   }

   void resize(unsigned sz, T c = T()) {

     // No need to test "sz >= 0", as "sz" is unsigned.

     if (sz <= used_) {

       used_ = sz;

     } else {

       unsigned a = allocated_;

       if (sz > a) {

         while (sz > a) {

           a *= 2;

         }

         Realloc(a);

       }

       while (sz > used_) {

         a_[used_++] = c;

       }

     }

   }

   T& operator[](size_t index) {

     return a_[index];

   }

   const T& operator[](size_t index) const {

     return a_[index];

   }

  private:

   void Realloc(unsigned new_size) {

     T *new_array =

         reinterpret_cast<T*>(allocator_->Alloc(sizeof(T) * new_size));

     memcpy(new_array, a_, used_ * sizeof(T));

     a_ = new_array;

     allocated_ = new_size;

   }

   PageAllocator *const allocator_;

   T *a_;  // pointer to an array of |allocated_| elements.

   unsigned allocated_;  // size of |a_|, in elements.

   unsigned used_;  // number of used slots in |a_|.

 };

 }  // namespace google_breakpad

 inline void* operator new(size_t nbytes,

                           google_breakpad::PageAllocator& allocator) {

    return allocator.Alloc(nbytes);

 }

 #endif  // GOOGLE_BREAKPAD_COMMON_MEMORY_H_