pooled_allocator.h

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

// file: pooled_allocator.h
// 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 <iostream>
#include <set>
#include <map>

#include <allocator_bit_vector.h>
#include <shared_memory.h>

#ifndef POOLED_ALLOCATOR_H
#define POOLED_ALLOCATOR_H
  
namespace pooled_allocator {

  // page_size  and  num_of_pages   are  constants  here.   The  mem
  // variable is  static, so its parameters must  be declared before
  // the class objects are instantiated.
  enum {
    page_size=8192,	      // Each segment is divided into pages of
                              // this size
    num_of_pages=1000,        // There are num_of_pages per segment
    initial_num_of_elems=16   // Num of elems allocated in 1st chunk
  };

  ////////////////////////////////////////////////////////////////////
  //////                           Class Chunk
  ////////////////////////////////////////////////////////////////////
  //////        
  //////        Unit of  pooled memory composed  of multiple elements.
  //////        The Chunk objects are  allocated in Process memory.  A
  //////        process  requests  pages  of  memory from  the  shared
  //////        memory  segment  header.   There  is just  one  shared
  //////        memory segment header  per shared memory segment.  The
  //////        header is  located starting at  the first byte  of the
  //////        shared memory segment.  Chunks  are allocated on a per
  //////        process basis.  Once a  pool of memory is requested by
  //////        the process, that process  is assigned the memory as a
  //////        chunk.  Chunks are composed  of elements which are all
  //////        of the same size.
  //////        
  //////        A chunk manages  its memory on a per  chunk basis.  If
  //////        one  chunks runs  out of  memory, than  the  Pool must
  //////        request a  new chunk, and request  the required memory
  //////        from the  new chunk.  Each chunk only  knows about its
  //////        own elements.   They do  not know about  other chunks,
  //////        except for links  to create lists of chunks  so that a
  //////        set of chunks can be traversed.
  //////        
  //////        
  ////////////////////////////////////////////////////////////////////
  
  class Chunk  {
    const int element_size;	// size of objects held in container
    const int num_of_elements;	// num_of_elements in chunk
    // const int page_size;	// page size of shared seg memory
    const int memory_size;	// total element storage size in bytes
    const int bit_vec_size;	// bit vector size

    ///////////////////////////////////////////////////////////////////////////
    //////        Chunk identification
    ///////////////////////////////////////////////////////////////////////////
    const int proj_id;	        // specific segment within series
    const int segment_page_num;	// segment page number, used to compute offset
                                // from the start of the segment to the chunk.
    const int num_of_segment_pages;	// This chunk is composed of this many
				// shared memory  segment pages.  When
				// the  next chunk is  allocated, this
				// value is used to determine the size
				// of the next requested chunk.
    char pathname[mem_space::name_length];  // identifies which segment series
    int first_elem_num;		// first element number of this chunk
    ///////////////////////////////////////////////////////////////////////////

    // page free/allocated list
    allocator_bit_vector::allocator_bit_vector_t bit_vec;
    // data storage segment
    unsigned char* mem;
    // chunk to the beginning of the specific page_num
    const int get_element_offset(int page_num);
    // convert element number to pointer address
    unsigned char* element_num_to_pointer(int start_block);
    // Linked List implementation
    Chunk* prev;  // points to prev chunk
    Chunk* next;  // points to next chunk
  public:
    // 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.
    // proj_id           - The shared memory segement id or page
    // segment_page_num  - The Chunk is on allocated starting at this
    //                     page number within the shared memory segment
    //                     identified by proj_id.
    Chunk(const int& elem_size,
	  const int& total_chunk_size,
	  const int proj_id,
	  const int segment_page_num);	// The  chunk  is instantiated
					// in a  piece of memory which
					// is    total_chunk_size   in
					// bytes.
    // destructor
    virtual ~Chunk() {};
    // copy constructor
    Chunk(const Chunk& t);
    // assignment operator
    Chunk& operator=(const Chunk& t);
    bool operator==(const Chunk& t);
    // The  segment page  number is  the data  page number  within the
    // segment  specified by  the pathname  and proj_id.   The segment
    // page number  can be used  to compute the chunk_offset  which is
    // the distance from the beginning of the shared memory segment to
    // the beginning of this chunk  in bytes.  The chunk begins at the
    // page boundary.
    const int get_segment_page_num() {return segment_page_num;}
    const int get_num_of_segment_pages() {return num_of_segment_pages;}
    // get_page_offset returns the byte offset from the beginning of the
    // Each chunk consists of a sequence of elements first_elem_num is
    // the first global element number within this chunk.
    void set_first_elem_num(int val) {first_elem_num=val;}
    const int get_first_elem_num() {return first_elem_num;}
    const int get_element_size() {return element_size;}
    // bit_vec size is only for  the bit vector data, does not include
    // header which is part of the Chunk class overhead.
//     const int get_bit_vec_size() {return bit_vec_size;}
    // num_of_elements is number of elements in this chunk
    const int get_num_of_elements() {return num_of_elements;}
    // pathname is the alloc_key used to retrieve the segment in which
    // this chunk is embedded.   Pathname specifies a series of shared
    // memory segments.
    void set_pathname(char* path_name) {strcpy(pathname,path_name);}
    void get_pathname(char* path_name) {strcpy(path_name,pathname);}
    // The proj_id specifies which specific shared memory segment from
    // within this series of shared memory segments.
    const int get_proj_id() {return proj_id;}
    // find num_of_elements contiguous free blocks
    // returns local starting block number or -1
    int find(int num_of_elements);
    // mark num_of_elements starting at start_element
    // as assigned.  This function is used to link
    // newly freed memory with a previous free block.
    void mark(int start_element,int num_of_elements);
    // clear num_of_elements starting at start_element
    // as available.
    void clear(int start_element,int num_of_elements);
    // Compute the element number associated with the pointer
    int pointer_to_element_num(const unsigned char* p);
    // allocate num_of_elements starting with
    // element start_element
    mem_space::memory_index_t
    allocate(int start_element,
	     int num_of_elements);
    // release chunk elements
    void free(int global_first_element, int num_of_elements);
    // Functions for walking through the chunk list
    Chunk* get_next(void) {return next;}
    Chunk* get_prev(void) {return prev;}
    void set_next(Chunk* val) {next=val;}
    void set_prev(Chunk* val) {prev=val;}
  };  // class Chunk


  
  
  
  /////////////////////////////////////////////////////////////////////////////
  //////                           Class Pool
  /////////////////////////////////////////////////////////////////////////////
  //////        
  //////        Class Pool maintains segments of memory which are stored as a
  //////        as a list of chunks.
  //////        
  /////////////////////////////////////////////////////////////////////////////
  
  template<class T,
	   mem_space::allocator_key_t alloc_key,
           mem_space::allocator_addr_t alloc_addr=0> 
  class Pool {
  private:
    const int element_size;
    // source of memory for the Pool
    // static mem_space::shared<alloc_key,alloc_addr> mem;
    mem_space::shared<alloc_key,alloc_addr> mem;
    
    // chunks list is static so that all objects in the
    // process share the same chunks
    static Chunk* chunks; // list of allocated chunks
    // Chunk* chunks; // list of allocated chunks
    void grow();
    int compute_chunk_pages();	// how  big should the  next allocated
				// chunk be?
    // locate shared memory to allocate the next chunk.
    std::pair<mem_space::shared_memory_header_t*,int>
    find_shared_memory(int requested_pages);
    // local reference count
//     int ref_count;
  public:
    // constructor
    //    Pool(unsigned int sz,
//     Pool(const int& esize);
    Pool();
    // destructor
    virtual ~Pool();
    // copy constructor
    Pool(const Pool<T,alloc_key,alloc_addr>& t);
    // assignment operator
    Pool& operator=(const Pool<T,alloc_key,alloc_addr>& t);
    // equality operator
    bool operator==(const Pool<T,alloc_key,alloc_addr>& t) const;
    Chunk* get_last_chunk();	// retrieve the last chunk in list
    // find chunk associated with global_element_num
    Chunk* find_chunk(int global_element_num);
    // find_chunk finds the chunk and element number for pointer *p
    std::pair<Chunk*,int> find_chunk(const unsigned char* p);
    std::pair<Chunk*,int> find(int num_of_elements);
    void mark(int start_element,int num_of_elements);
    void clear(int start_element,int num_of_elements);
    void free_chunk(Chunk* victim); // recycle chunk
    // retrieve a specified shared memory page
    mem_space::shared_memory_header_t*
//     find_shared_segment() {
    find_shared_segment(int proj_id) {
      mem_space::memory_index_t smh_idx =
	mem.allocate(proj_id);
      return
	static_cast<mem_space::shared_memory_header_t*>(smh_idx.get_memory_ptr());
    };
    mem_space::memory_index_t
    alloc(const int num_of_elements);
    void free(unsigned char* p, int num_of_elements);
    // retrieve a pointer to the object
//     unsigned char* retrieve_object_ptr(mem_space::memory_index_t obj_idx);
    // get the allocator main index map
    mem_space::map_index_t get_map_index(void);
    // set the allocator main index map
    void set_map_index(mem_space::map_index_t obj_idx);
    void shutdown(void) {
      // Close and release shared memory and semaphores
      mem_space::shared_memory_header_t* smh =
	find_shared_segment(1);
      const int shared_memory_addr = smh->get_shared_memory_addr();
      const int shared_memory_size = smh->get_shared_memory_size();
//       smh->shutdown();
      smh->~shared_memory_header_t();
      mem.free(shared_memory_addr,shared_memory_size);
    } // shutdown(void)
    void lock(int segment_num, int segment_page_num) {
      // lock access to the shared memory container
      mem_space::shared_memory_header_t* smh =
	find_shared_segment(segment_num);
      smh->lock(segment_page_num);
    }
    void unlock(int segment_num, int segment_page_num) {
      // unlock access to the shared memory container
      mem_space::shared_memory_header_t* smh =
	find_shared_segment(segment_num);
      smh->unlock(segment_page_num);
    }
    Chunk* get_chunks_list(void) {
      return chunks;
    }
    void set_chunks_list(Chunk* val) {
      // first eliminate any existing chunks on the list
      if ((chunks) && (chunks != val)) {
	int chunkcount = 1;
	Chunk* thischunk=chunks;
	Chunk* prevchunk=0;
	// get to the end of the list
	while (thischunk->get_next()) {
	  chunkcount++;
	  prevchunk = thischunk;
	  thischunk = thischunk->get_next();
	}
	if (chunkcount > 1) {
	  // Flag a warning.   There should only be one  chunk at this
	  // point.  This  function is  written to reassign  the first
	  // chunk on  the list when it  is empty, ie  when no objects
	  // are actually stored there.  If  more than one chunk is on
	  // the list,  there is a  high probability that  objects are
	  // already stored in the list.
	  std::cerr << __FILE__ << ':' << __LINE__  << "Attempting to reset a loaded Chunk list."
		    << std::endl;
	}  // if (chunkcount > 1)
	while (thischunk) {
	  // run through the chunk list and release the current existing chunks
	  free_chunk(thischunk);
	  chunkcount--;
	  thischunk = prevchunk;
	  if (prevchunk)
	    prevchunk = prevchunk->get_prev();
	}  // while ((thischunk != chunks) && (thischunk != 0))
	chunks = val;
      }
      // Then reset the chunk list to point to the list from the other
      // process
      return;
    }
    void unlink(void) {
      // use  the map  in the  shared memory  class to  remove all
      // related shared memory segments
      mem.unlink();		// call shared class to unlink shared memory
      return;
    }
  };  // class Pool

//   // static elements of class Pool
//   template<mem_space::allocator_t alloc_type,
// 	   mem_space::allocator_key_t alloc_key,
//            mem_space::allocator_addr_t alloc_addr=0> 
//   mem_space::shared<alloc_key,alloc_addr> Pool<alloc_type,
// 			 alloc_key,alloc_addr>::mem(pooled_allocator::num_of_pages,
// 					 pooled_allocator::page_size);
  
  // static elements of class Pool
  template<class T,
 	   mem_space::allocator_key_t alloc_key,