Move allocator base code into core/, alloc_mmap to alloc/

8 files changed, 739 insertions, 9 deletions

diff --git a/src/core/allocate.h b/src/core/allocate.h
new file mode 100644
index 000000000..efbb77291
--- /dev/null
+++ b/src/core/allocate.h
@@ -0,0 +1,35 @@
+/*************************************************
+* Allocator Header File                          *
+* (C) 1999-2007 Jack Lloyd                       *
+*************************************************/
+
+#ifndef BOTAN_ALLOCATOR_H__
+#define BOTAN_ALLOCATOR_H__
+
+#include <botan/types.h>
+#include <string>
+
+namespace Botan {
+
+/*************************************************
+* Allocator Interface                            *
+*************************************************/
+class BOTAN_DLL Allocator
+   {
+   public:
+      static Allocator* get(bool);
+
+      virtual void* allocate(u32bit) = 0;
+      virtual void deallocate(void*, u32bit) = 0;
+
+      virtual std::string type() const = 0;
+
+      virtual void init() {}
+      virtual void destroy() {}
+
+      virtual ~Allocator() {}
+   };
+
+}
+
+#endif
diff --git a/src/core/defalloc.cpp b/src/core/defalloc.cpp
new file mode 100644
index 000000000..5fb8e1447
--- /dev/null
+++ b/src/core/defalloc.cpp
@@ -0,0 +1,98 @@
+/*************************************************
+* Basic Allocators Source File                   *
+* (C) 1999-2007 Jack Lloyd                       *
+*************************************************/
+
+#include <botan/defalloc.h>
+#include <botan/libstate.h>
+#include <botan/util.h>
+#include <cstdlib>
+#include <cstring>
+
+namespace Botan {
+
+namespace {
+
+/*************************************************
+* Perform Memory Allocation                      *
+*************************************************/
+void* do_malloc(u32bit n, bool do_lock)
+   {
+   void* ptr = std::malloc(n);
+
+   if(!ptr)
+      return 0;
+
+   if(do_lock)
+      lock_mem(ptr, n);
+
+   std::memset(ptr, 0, n);
+   return ptr;
+   }
+
+/*************************************************
+* Perform Memory Deallocation                    *
+*************************************************/
+void do_free(void* ptr, u32bit n, bool do_lock)
+   {
+   if(!ptr)
+      return;
+
+   std::memset(ptr, 0, n);
+   if(do_lock)
+      unlock_mem(ptr, n);
+
+   std::free(ptr);
+   }
+
+}
+
+/*************************************************
+* Malloc_Allocator's Allocation                  *
+*************************************************/
+void* Malloc_Allocator::allocate(u32bit n)
+   {
+   return do_malloc(n, false);
+   }
+
+/*************************************************
+* Malloc_Allocator's Deallocation                *
+*************************************************/
+void Malloc_Allocator::deallocate(void* ptr, u32bit n)
+   {
+   do_free(ptr, n, false);
+   }
+
+/*************************************************
+* Locking_Allocator's Allocation                 *
+*************************************************/
+void* Locking_Allocator::alloc_block(u32bit n)
+   {
+   return do_malloc(n, true);
+   }
+
+/*************************************************
+* Locking_Allocator's Deallocation               *
+*************************************************/
+void Locking_Allocator::dealloc_block(void* ptr, u32bit n)
+   {
+   do_free(ptr, n, true);
+   }
+
+/*************************************************
+* Get an allocator                               *
+*************************************************/
+Allocator* Allocator::get(bool locking)
+   {
+   std::string type = "";
+   if(!locking)
+      type = "malloc";
+
+   Allocator* alloc = global_state().get_allocator(type);
+   if(alloc)
+      return alloc;
+
+   throw Exception("Couldn't find an allocator to use in get_allocator");
+   }
+
+}
diff --git a/src/core/defalloc.h b/src/core/defalloc.h
new file mode 100644
index 000000000..dc01ee47f
--- /dev/null
+++ b/src/core/defalloc.h
@@ -0,0 +1,41 @@
+/*************************************************
+* Basic Allocators Header File                   *
+* (C) 1999-2007 Jack Lloyd                       *
+*************************************************/
+
+#ifndef BOTAN_BASIC_ALLOC_H__
+#define BOTAN_BASIC_ALLOC_H__
+
+#include <botan/mem_pool.h>
+
+namespace Botan {
+
+/*************************************************
+* Malloc Allocator                              *
+*************************************************/
+class BOTAN_DLL Malloc_Allocator : public Allocator
+   {
+   public:
+      void* allocate(u32bit);
+      void deallocate(void*, u32bit);
+
+      std::string type() const { return "malloc"; }
+   };
+
+/*************************************************
+* Locking Allocator                              *
+*************************************************/
+class BOTAN_DLL Locking_Allocator : public Pooling_Allocator
+   {
+   public:
+      Locking_Allocator(Mutex* m) : Pooling_Allocator(m) {}
+
+      std::string type() const { return "locking"; }
+   private:
+      void* alloc_block(u32bit);
+      void dealloc_block(void*, u32bit);
+   };
+
+}
+
+#endif
diff --git a/src/core/info.txt b/src/core/info.txt
index fabf676f3..9331d56dd 100644
--- a/src/core/info.txt
+++ b/src/core/info.txt
@@ -9,27 +9,29 @@ aes
 sha1
 sha2
 hmac
-allocators
 filters
 libstate
 timer_base
 </requires>
 
 <add>
+allocate.h
 base.cpp
 base.h
 botan.h
 data_src.cpp
 data_src.h
 def_powm.cpp
+defalloc.cpp
+defalloc.h
 eng_def.h
 enums.h
 exceptn.cpp
 exceptn.h
 kdf.cpp
 kdf.h
-modules.cpp
-modules.h
+mem_pool.cpp
+mem_pool.h
 mutex.h
 pk_pad.cpp
 pk_pad.h
@@ -37,6 +39,7 @@ rng.cpp
 rng.h
 s2k.cpp
 s2k.h
+secmem.h
 symkey.cpp
 symkey.h
 </add>
diff --git a/src/core/libstate/info.txt b/src/core/libstate/info.txt
index f0040a688..89bb3a462 100644
--- a/src/core/libstate/info.txt
+++ b/src/core/libstate/info.txt
@@ -14,21 +14,23 @@ def_alg.cpp
 def_mode.cpp
 eng_base.cpp
 engine.cpp
+engine.h
 get_enc.cpp
 get_pbe.cpp
+get_pbe.h
 init.h
 init_def.cpp
 init_opt.cpp
 libstate.cpp
-look_pk.cpp
-lookup.cpp
-oids.cpp
-policy.cpp
-engine.h
-get_pbe.h
 libstate.h
 look_add.h
+look_pk.cpp
 look_pk.h
+lookup.cpp
 lookup.h
+modules.cpp
+modules.h
+oids.cpp
 oids.h
+policy.cpp
 </add>
diff --git a/src/core/mem_pool.cpp b/src/core/mem_pool.cpp
new file mode 100644
index 000000000..c99d627ad
--- /dev/null
+++ b/src/core/mem_pool.cpp
@@ -0,0 +1,260 @@
+/*************************************************
+* Pooling Allocator Source File                  *
+* (C) 1999-2008 Jack Lloyd                       *
+*     2005 Matthew Gregan                        *
+*     2005-2006 Matt Johnston                    *
+*************************************************/
+
+#include <botan/mem_pool.h>
+#include <botan/util.h>
+#include <botan/mem_ops.h>
+#include <algorithm>
+#include <exception>
+
+namespace Botan {
+
+namespace {
+
+/*************************************************
+* Memory Allocation Exception                    *
+*************************************************/
+struct Memory_Exhaustion : public std::bad_alloc
+   {
+   const char* what() const throw()
+      { return "Ran out of memory, allocation failed"; }
+   };
+
+}
+
+/*************************************************
+* Memory_Block Constructor                       *
+*************************************************/
+Pooling_Allocator::Memory_Block::Memory_Block(void* buf)
+   {
+   buffer = static_cast<byte*>(buf);
+   bitmap = 0;
+   buffer_end = buffer + (BLOCK_SIZE * BITMAP_SIZE);
+   }
+
+/*************************************************
+* See if ptr is contained by this block          *
+*************************************************/
+bool Pooling_Allocator::Memory_Block::contains(void* ptr,
+                                               u32bit length) const throw()
+   {
+   return ((buffer <= ptr) &&
+           (buffer_end >= static_cast<byte*>(ptr) + length * BLOCK_SIZE));
+   }
+
+/*************************************************
+* Allocate some memory, if possible              *
+*************************************************/
+byte* Pooling_Allocator::Memory_Block::alloc(u32bit n) throw()
+   {
+   if(n == 0 || n > BITMAP_SIZE)
+      return 0;
+
+   if(n == BITMAP_SIZE)
+      {
+      if(bitmap)
+         return 0;
+      else
+         {
+         bitmap = ~bitmap;
+         return buffer;
+         }
+      }
+
+   bitmap_type mask = (static_cast<bitmap_type>(1) << n) - 1;
+   u32bit offset = 0;
+
+   while(bitmap & mask)
+      {
+      mask <<= 1;
+      ++offset;
+
+      if((bitmap & mask) == 0)
+         break;
+      if(mask >> 63)
+         break;
+      }
+
+   if(bitmap & mask)
+      return 0;
+
+   bitmap |= mask;
+   return buffer + offset * BLOCK_SIZE;
+   }
+
+/*************************************************
+* Mark this memory as free, if we own it         *
+*************************************************/
+void Pooling_Allocator::Memory_Block::free(void* ptr, u32bit blocks) throw()
+   {
+   clear_mem(static_cast<byte*>(ptr), blocks * BLOCK_SIZE);
+
+   const u32bit offset = (static_cast<byte*>(ptr) - buffer) / BLOCK_SIZE;
+
+   if(offset == 0 && blocks == BITMAP_SIZE)
+      bitmap = ~bitmap;
+   else
+      {
+      for(u32bit j = 0; j != blocks; ++j)
+         bitmap &= ~(static_cast<bitmap_type>(1) << (j+offset));
+      }
+   }
+
+/*************************************************
+* Pooling_Allocator Constructor                  *
+*************************************************/
+Pooling_Allocator::Pooling_Allocator(Mutex* m) : mutex(m)
+   {
+   last_used = blocks.begin();
+   }
+
+/*************************************************
+* Pooling_Allocator Destructor                   *
+*************************************************/
+Pooling_Allocator::~Pooling_Allocator()
+   {
+   delete mutex;
+   if(blocks.size())
+      throw Invalid_State("Pooling_Allocator: Never released memory");
+   }
+
+/*************************************************
+* Free all remaining memory                      *
+*************************************************/
+void Pooling_Allocator::destroy()
+   {
+   Mutex_Holder lock(mutex);
+
+   blocks.clear();
+
+   for(u32bit j = 0; j != allocated.size(); ++j)
+      dealloc_block(allocated[j].first, allocated[j].second);
+   allocated.clear();
+   }
+
+/*************************************************
+* Allocation                                     *
+*************************************************/
+void* Pooling_Allocator::allocate(u32bit n)
+   {
+   const u32bit BITMAP_SIZE = Memory_Block::bitmap_size();
+   const u32bit BLOCK_SIZE = Memory_Block::block_size();
+
+   Mutex_Holder lock(mutex);
+
+   if(n <= BITMAP_SIZE * BLOCK_SIZE)
+      {
+      const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE;
+
+      byte* mem = allocate_blocks(block_no);
+      if(mem)
+         return mem;
+
+      get_more_core(PREF_SIZE);
+
+      mem = allocate_blocks(block_no);
+      if(mem)
+         return mem;
+
+      throw Memory_Exhaustion();
+      }
+
+   void* new_buf = alloc_block(n);
+   if(new_buf)
+      return new_buf;
+
+   throw Memory_Exhaustion();
+   }
+
+/*************************************************
+* Deallocation                                   *
+*************************************************/
+void Pooling_Allocator::deallocate(void* ptr, u32bit n)
+   {
+   const u32bit BITMAP_SIZE = Memory_Block::bitmap_size();
+   const u32bit BLOCK_SIZE = Memory_Block::block_size();
+
+   if(ptr == 0 && n == 0)
+      return;
+
+   Mutex_Holder lock(mutex);
+
+   if(n > BITMAP_SIZE * BLOCK_SIZE)
+      dealloc_block(ptr, n);
+   else
+      {
+      const u32bit block_no = round_up(n, BLOCK_SIZE) / BLOCK_SIZE;
+
+      std::vector<Memory_Block>::iterator i =
+         std::lower_bound(blocks.begin(), blocks.end(), Memory_Block(ptr));
+
+      if(i == blocks.end() || !i->contains(ptr, block_no))
+         throw Invalid_State("Pointer released to the wrong allocator");
+
+      i->free(ptr, block_no);
+      }
+   }
+
+/*************************************************
+* Try to get some memory from an existing block  *
+*************************************************/
+byte* Pooling_Allocator::allocate_blocks(u32bit n)
+   {
+   if(blocks.empty())
+      return 0;
+
+   std::vector<Memory_Block>::iterator i = last_used;
+
+   do
+      {
+      byte* mem = i->alloc(n);
+      if(mem)
+         {
+         last_used = i;
+         return mem;
+         }
+
+      ++i;
+      if(i == blocks.end())
+         i = blocks.begin();
+      }
+   while(i != last_used);
+
+   return 0;
+   }
+
+/*************************************************
+* Allocate more memory for the pool              *
+*************************************************/
+void Pooling_Allocator::get_more_core(u32bit in_bytes)
+   {
+   const u32bit BITMAP_SIZE = Memory_Block::bitmap_size();
+   const u32bit BLOCK_SIZE = Memory_Block::block_size();
+
+   const u32bit TOTAL_BLOCK_SIZE = BLOCK_SIZE * BITMAP_SIZE;
+
+   const u32bit in_blocks = round_up(in_bytes, BLOCK_SIZE) / TOTAL_BLOCK_SIZE;
+   const u32bit to_allocate = in_blocks * TOTAL_BLOCK_SIZE;
+
+   void* ptr = alloc_block(to_allocate);
+   if(ptr == 0)
+      throw Memory_Exhaustion();
+
+   allocated.push_back(std::make_pair(ptr, to_allocate));
+
+   for(u32bit j = 0; j != in_blocks; ++j)
+      {
+      byte* byte_ptr = static_cast<byte*>(ptr);
+      blocks.push_back(Memory_Block(byte_ptr + j * TOTAL_BLOCK_SIZE));
+      }
+
+   std::sort(blocks.begin(), blocks.end());
+   last_used = std::lower_bound(blocks.begin(), blocks.end(),
+                                Memory_Block(ptr));
+   }
+
+}
diff --git a/src/core/mem_pool.h b/src/core/mem_pool.h
new file mode 100644
index 000000000..b74e08a8d
--- /dev/null
+++ b/src/core/mem_pool.h
@@ -0,0 +1,74 @@
+/*************************************************
+* Pooling Allocator Header File                  *
+* (C) 1999-2007 Jack Lloyd                       *
+*************************************************/
+
+#ifndef BOTAN_POOLING_ALLOCATOR_H__
+#define BOTAN_POOLING_ALLOCATOR_H__
+
+#include <botan/allocate.h>
+#include <botan/exceptn.h>
+#include <botan/mutex.h>
+#include <utility>
+#include <vector>
+
+namespace Botan {
+
+/*************************************************
+* Pooling Allocator                              *
+*************************************************/
+class BOTAN_DLL Pooling_Allocator : public Allocator
+   {
+   public:
+      void* allocate(u32bit);
+      void deallocate(void*, u32bit);
+
+      void destroy();
+
+      Pooling_Allocator(Mutex*);
+      ~Pooling_Allocator();
+   private:
+      void get_more_core(u32bit);
+      byte* allocate_blocks(u32bit);
+
+      virtual void* alloc_block(u32bit) = 0;
+      virtual void dealloc_block(void*, u32bit) = 0;
+
+      class BOTAN_DLL Memory_Block
+         {
+         public:
+            Memory_Block(void*);
+
+            static u32bit bitmap_size() { return BITMAP_SIZE; }
+            static u32bit block_size() { return BLOCK_SIZE; }
+
+            bool contains(void*, u32bit) const throw();
+            byte* alloc(u32bit) throw();
+            void free(void*, u32bit) throw();
+
+            bool operator<(const Memory_Block& other) const
+               {
+               if(buffer < other.buffer && other.buffer < buffer_end)
+                  return false;
+               return (buffer < other.buffer);
+               }
+         private:
+            typedef u64bit bitmap_type;
+            static const u32bit BITMAP_SIZE = 8 * sizeof(bitmap_type);
+            static const u32bit BLOCK_SIZE = 64;
+
+            bitmap_type bitmap;
+            byte* buffer, *buffer_end;
+         };
+
+      static const u32bit PREF_SIZE = BOTAN_MEM_POOL_CHUNK_SIZE;
+
+      std::vector<Memory_Block> blocks;
+      std::vector<Memory_Block>::iterator last_used;
+      std::vector<std::pair<void*, u32bit> > allocated;
+      Mutex* mutex;
+   };
+
+}
+
+#endif
diff --git a/src/core/secmem.h b/src/core/secmem.h
new file mode 100644
index 000000000..37adf7f42
--- /dev/null
+++ b/src/core/secmem.h
@@ -0,0 +1,217 @@
+/*************************************************
+* Secure Memory Buffers Header File              *
+* (C) 1999-2007 Jack Lloyd                       *
+*************************************************/
+
+#ifndef BOTAN_SECURE_MEMORY_BUFFERS_H__
+#define BOTAN_SECURE_MEMORY_BUFFERS_H__
+
+#include <botan/allocate.h>
+#include <botan/mem_ops.h>
+
+namespace Botan {
+
+/*************************************************
+* Variable Length Memory Buffer                  *
+*************************************************/
+template<typename T>
+class MemoryRegion
+   {
+   public:
+      u32bit size() const { return used; }
+      u32bit is_empty() const { return (used == 0); }
+      u32bit has_items() const { return (used != 0); }
+
+      operator T* () { return buf; }
+      operator const T* () const { return buf; }
+
+      T* begin() { return buf; }
+      const T* begin() const { return buf; }
+
+      T* end() { return (buf + size()); }
+      const T* end() const { return (buf + size()); }
+
+      bool operator==(const MemoryRegion<T>& other) const
+         {
+         return (size() == other.size() &&
+                 same_mem(buf, other.buf, size()));
+         }
+
+      bool operator<(const MemoryRegion<T>&) const;
+
+      bool operator!=(const MemoryRegion<T>& in) const
+         { return (!(*this == in)); }
+      MemoryRegion<T>& operator=(const MemoryRegion<T>& in)
+         { if(this != &in) set(in); return (*this); }
+
+      void copy(const T in[], u32bit n)
+         { copy(0, in, n); }
+      void copy(u32bit off, const T in[], u32bit n)
+         { copy_mem(buf + off, in, (n > size() - off) ? (size() - off) : n); }
+
+      void set(const T in[], u32bit n)    { create(n); copy(in, n); }
+      void set(const MemoryRegion<T>& in) { set(in.begin(), in.size()); }
+
+      void append(const T data[], u32bit n)
+         { grow_to(size()+n); copy(size() - n, data, n); }
+      void append(T x) { append(&x, 1); }
+      void append(const MemoryRegion<T>& x) { append(x.begin(), x.size()); }
+
+      void clear() { clear_mem(buf, allocated); }
+      void destroy() { create(0); }
+
+      void create(u32bit);
+      void grow_to(u32bit);
+      void swap(MemoryRegion<T>&);
+
+      ~MemoryRegion() { deallocate(buf, allocated); }
+   protected:
+      MemoryRegion() { buf = 0; alloc = 0; used = allocated = 0; }
+      MemoryRegion(const MemoryRegion<T>& other)
+         {
+         buf = 0;
+         used = allocated = 0;
+         alloc = other.alloc;
+         set(other.buf, other.used);
+         }
+
+      void init(bool locking, u32bit length = 0)
+         { alloc = Allocator::get(locking); create(length); }
+   private:
+      T* allocate(u32bit n)
+         {
+         return static_cast<T*>(alloc->allocate(sizeof(T)*n));
+         }
+
+      void deallocate(T* p, u32bit n)
+         { alloc->deallocate(p, sizeof(T)*n); }
+
+      T* buf;
+      u32bit used;
+      u32bit allocated;
+      Allocator* alloc;
+   };
+
+/*************************************************
+* Create a new buffer                            *
+*************************************************/
+template<typename T>
+void MemoryRegion<T>::create(u32bit n)
+   {
+   if(n <= allocated) { clear(); used = n; return; }
+   deallocate(buf, allocated);
+   buf = allocate(n);
+   allocated = used = n;
+   }
+
+/*************************************************
+* Increase the size of the buffer                *
+*************************************************/
+template<typename T>
+void MemoryRegion<T>::grow_to(u32bit n)
+   {
+   if(n > used && n <= allocated)
+      {
+      clear_mem(buf + used, n - used);
+      used = n;
+      return;
+      }
+   else if(n > allocated)
+      {
+      T* new_buf = allocate(n);
+      copy_mem(new_buf, buf, used);
+      deallocate(buf, allocated);
+      buf = new_buf;
+      allocated = used = n;
+      }
+   }
+
+/*************************************************
+* Compare this buffer with another one           *
+*************************************************/
+template<typename T>
+bool MemoryRegion<T>::operator<(const MemoryRegion<T>& in) const
+   {
+   if(size() < in.size()) return true;
+   if(size() > in.size()) return false;
+
+   for(u32bit j = 0; j != size(); j++)
+      {
+      if(buf[j] < in[j]) return true;
+      if(buf[j] > in[j]) return false;
+      }
+
+   return false;
+   }
+
+/*************************************************
+* Swap this buffer with another one              *
+*************************************************/
+template<typename T>
+void MemoryRegion<T>::swap(MemoryRegion<T>& x)
+   {
+   std::swap(buf, x.buf);
+   std::swap(used, x.used);
+   std::swap(allocated, x.allocated);
+   std::swap(alloc, x.alloc);
+   }
+
+/*************************************************
+* Unlocked Variable Length Buffer                *
+*************************************************/
+template<typename T>
+class MemoryVector : public MemoryRegion<T>
+   {
+   public:
+      MemoryVector<T>& operator=(const MemoryRegion<T>& in)
+         { if(this != &in) set(in); return (*this); }
+
+      MemoryVector(u32bit n = 0) { MemoryRegion<T>::init(false, n); }
+      MemoryVector(const T in[], u32bit n)
+         { MemoryRegion<T>::init(false); set(in, n); }
+      MemoryVector(const MemoryRegion<T>& in)
+         { MemoryRegion<T>::init(false); set(in); }
+      MemoryVector(const MemoryRegion<T>& in1, const MemoryRegion<T>& in2)
+         { MemoryRegion<T>::init(false); set(in1); append(in2); }
+   };
+
+/*************************************************
+* Locked Variable Length Buffer                  *
+*************************************************/
+template<typename T>
+class SecureVector : public MemoryRegion<T>
+   {
+   public:
+      SecureVector<T>& operator=(const MemoryRegion<T>& in)
+         { if(this != &in) set(in); return (*this); }
+
+      SecureVector(u32bit n = 0) { MemoryRegion<T>::init(true, n); }
+      SecureVector(const T in[], u32bit n)
+         { MemoryRegion<T>::init(true); set(in, n); }
+      SecureVector(const MemoryRegion<T>& in)
+         { MemoryRegion<T>::init(true); set(in); }
+      SecureVector(const MemoryRegion<T>& in1, const MemoryRegion<T>& in2)
+         { MemoryRegion<T>::init(true); set(in1); append(in2); }
+   };
+
+/*************************************************
+* Locked Fixed Length Buffer                     *
+*************************************************/
+template<typename T, u32bit L>
+class SecureBuffer : public MemoryRegion<T>
+   {
+   public:
+      SecureBuffer<T,L>& operator=(const SecureBuffer<T,L>& in)
+         { if(this != &in) set(in); return (*this); }
+
+      SecureBuffer() { MemoryRegion<T>::init(true, L); }
+      SecureBuffer(const T in[], u32bit n)
+         { MemoryRegion<T>::init(true, L); copy(in, n); }
+   private:
+      SecureBuffer<T, L>& operator=(const MemoryRegion<T>& in)
+         { if(this != &in) set(in); return (*this); }
+   };
+
+}
+
+#endif