manalloc.cpp

含有多种公开密钥算法、多种块加密、多种数据流加密、多种HASH函数、多种CheckSum校验、多种MAC校验等几十种加密算法的程序

/*************************************************
* Managed Allocator Source File                  *
* (C) 1999-2002 The Botan Project                *
*************************************************/

#include <botan/manalloc.h>
#include <botan/util.h>
#include <algorithm>

namespace Botan {

namespace {

bool Buffer_Cmp(const ManagedAllocator::Buffer& a,
                const ManagedAllocator::Buffer& b)
   { return ((byte*)a.data < (byte*)b.data); }

bool empty_buffer(const ManagedAllocator::Buffer& block)
   { return (block.length == 0); }

}

/*************************************************
* ManagedAllocator Constructor                   *
*************************************************/
ManagedAllocator::ManagedAllocator(bool s, u32bit p) :
   SecureAllocator(s), pref_size((p >= 64 && power_of_2(p)) ? p : 1024)
   {
   lock = get_mutex();
   }

/*************************************************
* ManagedAllocator Destructor                    *
*************************************************/
ManagedAllocator::~ManagedAllocator()
   {
   delete lock;
   }

/*************************************************
* Round up n to multiple of ALIGN_TO             *
*************************************************/
u32bit ManagedAllocator::round_up(u32bit n) const
   {
   if(n % ALIGN_TO)
      n += ALIGN_TO - (n % ALIGN_TO);
   return n;
   }

/*************************************************
* Return true if these buffers overlap           *
*************************************************/
bool ManagedAllocator::overlap(Buffer a, Buffer b) const
   {
   if((byte*)a.data + a.length == (byte*)b.data)
      return true;
   return false;
   }

/*************************************************
* Find the buffer containing this memory         *
*************************************************/
u32bit ManagedAllocator::find_buffer(void* addr) const
   {
   for(u32bit j = 0; j != buffer_list.size(); j++)
      {
      byte* buf_addr = (byte*)buffer_list[j].data;
      if(buf_addr <= addr && addr < buf_addr + buffer_list[j].length)
         return j;
      }
   throw Internal_Error("ManagedAllocator::find_buffer: no buffer found");
   }

/*************************************************
* Remove empty buffers from list                 *
*************************************************/
void ManagedAllocator::remove_empty_buffers(std::vector<Buffer>& list) const
   {
   std::vector<Buffer>::iterator empty;

   empty = std::find_if(list.begin(), list.end(), empty_buffer);
   while(empty != list.end())
      {
      list.erase(empty);
      empty = std::find_if(list.begin(), list.end(), empty_buffer);
      }
   }

/*************************************************
* Find if two free blocks from the same buffer   *
*************************************************/
bool ManagedAllocator::same_buffer(Buffer& a, Buffer& b) const
   {
   return (find_buffer(a.data) == find_buffer(b.data));
   }

/*************************************************
* Allocation                                     *
*************************************************/
void* ManagedAllocator::allocate(u32bit n) const
   {
   if(n == 0) return 0;
   n = round_up(n);

   void* memory = find_free_block(n);
   if(memory)
      return memory;

   lock->lock();
   Buffer block;
   block.length = ((pref_size > n) ? pref_size : n);
   block.data = alloc_block(block.length);
   if(!block.data)
      throw Memory_Exhaustion();
   free_list.push_back(block);
   buffer_list.push_back(block);

   lock->unlock();

   memory = find_free_block(n);
   if(memory)
      return memory;

   throw Memory_Exhaustion();
   }

/*************************************************
* Deallocation                                   *
*************************************************/
void ManagedAllocator::deallocate(void* ptr, u32bit n) const
   {
   static u32bit defrag_counter = 0;
   const u32bit RUNS_TO_DEFRAGS = 2;

   if(ptr == 0 || n == 0) return;

   n = round_up(n);

   std::memset(ptr, 0, n);

   lock->lock();

   Buffer newblock;
   newblock.length = n;
   newblock.data = ptr;
   free_list.push_back(newblock);
   if(free_list.size() >= 2)
      std::inplace_merge(free_list.begin(), free_list.end() - 1,
                         free_list.end(), Buffer_Cmp);

   if(defrag_counter == 0)
      defrag_free_list();
   defrag_counter = (defrag_counter + 1) % RUNS_TO_DEFRAGS;

   for(u32bit j = 0; j != free_list.size(); j++)
      {
      bool erase = false;
      if(free_list[j].data == 0) continue;

      for(u32bit k = 0; k != buffer_list.size(); k++)
         if(free_list[j].data == buffer_list[k].data &&
            free_list[j].length == buffer_list[k].length)
            erase = true;

      if(erase)
         {
         u32bit buf = find_buffer(free_list[j].data);

         dealloc_block(buffer_list[buf].data, buffer_list[buf].length);

         buffer_list[buf].data = 0;
         buffer_list[buf].length = 0;
         free_list[j].data = 0;
         free_list[j].length = 0;
         }
      }

   remove_empty_buffers(free_list);
   remove_empty_buffers(buffer_list);

   lock->unlock();
   }

/*************************************************
* Defragment the free list                       *
*************************************************/
void ManagedAllocator::defrag_free_list() const
   {
   if(free_list.size() < 2) return;

   for(u32bit j = 0; j != free_list.size(); j++)
      {
      if(free_list[j].length == 0)
         continue;

      if(j > 0 && overlap(free_list[j-1], free_list[j]) &&
                  same_buffer(free_list[j-1], free_list[j]))
         {
         free_list[j].data = free_list[j-1].data;
         free_list[j].length += free_list[j-1].length;
         free_list[j-1].length = 0;
         }

      if(j < free_list.size() - 1 && overlap(free_list[j], free_list[j+1]) &&
                                     same_buffer(free_list[j], free_list[j+1]))
         {
         free_list[j+1].data = free_list[j].data;
         free_list[j+1].length += free_list[j].length;
         free_list[j].length = 0;
         }
      }
   remove_empty_buffers(free_list);
   }

/*************************************************
* Find a block on the free list                  *
*************************************************/
void* ManagedAllocator::find_free_block(u32bit n) const
   {
   void* retval = 0;
   lock->lock();

   for(u32bit j = 0; j != free_list.size(); j++)
      if(free_list[j].length >= n)
         {
         allocated[free_list[j].data] =
            &buffer_list[find_buffer(free_list[j].data)];
         retval = free_list[j].data;

         if(free_list[j].length == n)
            free_list.erase(free_list.begin() + j);
         else if(free_list[j].length > n)
            {
            free_list[j].length -= n;
            free_list[j].data = ((byte*)free_list[j].data) + n;
            }
         break;
         }

   lock->unlock();
   return retval;
   }

}