pooled_allocator.cc

简单的动态内存管理程序源代码

// file: pooled_allocator.cc
// author: Marc Bumble
// May 12, 2000
// Memory allocator for shared memory access
// Copyright (C) 2000 by Marc D. Bumble

//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License
//  as published by the Free Software Foundation; either version 2
//  of the License, or (at your option) any later version.

//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.

//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

#include <pooled_allocator.h>

namespace pooled_allocator {

  char none[] = "my_x_key";
  unsigned char shmaddr = 0x00000000;
  
  ////////////////////////////////////////////////////////////////////
  //////                    Class Chunk
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        Unit of  pooled memory composed  of multiple elements.
  //////        The  Pool class  defined below  retrieve a  portion of
  //////        UNIX  shared  memory  using  the shared  class.   That
  //////        retrived memory is formated using the class chunk into
  //////        element sized portions.
  //////        
  //////        
  //////        
  ////////////////////////////////////////////////////////////////////


  // constructor
  // constructor
  // elem_size         - element   size    in    bytes.
  // total_chunk_size  - The  chunk is  instantiated in  a  piece of
  //                     memory which is total_chunk_size in bytes.

  // Need to  do some calculatons  of memory sizes to  instantiate the
  // chunk.  The goal is to  determine how many elements can be stored
  // in the chunk, and then setup the space to hold the maximum number
  // of elements:
  //
  //      total_chunk_size = header + bit_vec + elements (1)
  //
  // where total_chunk_size is defined  above, the header is the Chunk
  // overhead or  sizeof(Chunk).  The bit_vec is the  data buffer used
  // by the bit  vector.  The rest of the bit  vector overhead is part
  // of the header or normal chunk overhead.  Finally, elements is the
  // space occupied by the elements stored in the Chunk.
  //
  // Known quantities:
  //
  // total_chunk_size - this is a given parameter, the amount of space
  //                    allocated to hold the chunk.
  //
  // header - sizeof(Chunk), the chunk class overhead.
  //
  // Use equation 1 above to solve for the number of elements:
  //
  //   total_chunk_size = header + (nelem/8 + 1) + (nelem*esize)
  //
  // Where:
  //
  //   nelem - number of elements
  //   esize - size of elements
  //
  // Solve for nelem:
  //
  //   nelem = (8*(chunk - header - 1))/(1 + 8*esize)       (2)
  // 
  
  Chunk::Chunk(const int& elem_size,
	       const int& total_chunk_size,
 	       const int project_id,
	       const int segment_page_number)
    // elem_size - element size in bytes.
    // pg_size   - page size in bytes.

    : element_size(elem_size),
      // see derivation of num_of_elements above equation 2
      num_of_elements((8*(total_chunk_size - sizeof(Chunk) - 1))/(1 + 8*element_size)),
      memory_size(num_of_elements*element_size),
      bit_vec_size((num_of_elements/8) + 1),
      proj_id(project_id),
      segment_page_num(segment_page_number),
      num_of_segment_pages(total_chunk_size/page_size),
      // bit vector monitors num_of_elements elements
      // bit vector is stored after this class, which is
      //    at the address (this + sizeof(Chunk))
      bit_vec(num_of_elements,
	      reinterpret_cast<unsigned char*>(this)+
	      sizeof(Chunk)) {
    // first_elem_num is initially unknown    
    first_elem_num=-1;
    // set the start of the data segment
    mem = reinterpret_cast<unsigned char*>(this) +
      sizeof(Chunk) + bit_vec_size;
    prev=0;
    next=0;
  };  // Chunk::Chunk()  constructor

  // copy constructor
  Chunk::Chunk(const Chunk& t)
    : element_size(t.element_size),
      num_of_elements(t.num_of_elements),
      memory_size(t.memory_size),
      bit_vec_size(t.bit_vec_size),
      proj_id(t.proj_id),
      segment_page_num(t.segment_page_num),
      num_of_segment_pages(t.num_of_segment_pages),
      bit_vec(t.bit_vec) {

    first_elem_num=t.first_elem_num;

    mem=reinterpret_cast<unsigned char*>(this)+sizeof(Chunk)+bit_vec_size;
    for (int i=0; i<memory_size; i++) {
      mem[i] = t.mem[i];
    }
    prev=t.prev;
    next=t.next;
  }; // copy constructor
  
  // assignment operator
  Chunk& Chunk::operator=(const Chunk& t) {
    if (this != &t) {		// avoid self assignment: t=t
      
      first_elem_num=t.first_elem_num; 
      mem=reinterpret_cast<unsigned char*>(this) +
	sizeof(Chunk) +
	bit_vec_size;
      for (int i=0; i<memory_size; i++) {
	mem[i] = t.mem[i];
      }
      bit_vec=t.bit_vec;
      prev=t.prev;
      next=t.next;
    }  // if (this != &t)
    return *this;
  }; // assignment operator

  bool Chunk::operator==(const Chunk& t) {
    // Define logical equality for a chunk
    bool return_val = false;
    if ((element_size==t.element_size) &&
	(num_of_elements==t.num_of_elements) &&
	(memory_size==t.memory_size) && 
	(bit_vec_size==t.bit_vec_size) &&
	(!strcmp(pathname,t.pathname)) &&
 	(proj_id==t.proj_id) &&
	(segment_page_num==t.segment_page_num) &&
	(num_of_segment_pages==t.num_of_segment_pages) &&
	(first_elem_num==t.first_elem_num) &&
	(bit_vec==t.bit_vec))
      return_val=true;
    else
      return_val=false;
    return return_val;
  };


  ////////////////////////////////////////////////////////////////////
  //////                 Chunk::find()
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        num_of_elements - memory for num_of_elements
  //////        
  //////        find free memory  space for num_of_elements.  
  //////        
  //////        Returns  the   global  start_element  number   of  the
  //////        requested space.
  //////        
  ////////////////////////////////////////////////////////////////////



  int Chunk::find(int num_of_elements) {
    // find num_of_elements contiguous free blocks Query this chunk to
    // see  if num_of_elements  memory  is avail.   If  so return  its
    // start_block number, otherwise return -1;

    // first find starting point.  This function may return a -1 which
    // will be sent to the higher level indicating that the next chunk
    // should  be searched  (there is  no more  suitable space  in the
    // current chunk).
    int start_elem = bit_vec.find_free_items(num_of_elements);
    // Convert the start_block  addr which is the block  addr local to
    // this block, into a global  block number by adding in the global
    // address of the first_elem_num of this chunk
    if (start_elem!=-1)
      start_elem += first_elem_num;
    return start_elem;
  };  // Chunk::find()