// 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,