www.pudn.com > allocator.rar > 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&amt; elem_size,
const int&amt; 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&amt; 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&amt; Chunk::operator=(const Chunk&amt; t) {
if (this != &amt;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 != &amt;t)
return *this;
}; // assignment operator

bool Chunk::operator==(const Chunk&amt; t) {
// Define logical equality for a chunk
bool return_val = false;
if ((element_size==t.element_size) &amt;&amt;
(num_of_elements==t.num_of_elements) &amt;&amt;
(memory_size==t.memory_size) &amt;&amt;
(bit_vec_size==t.bit_vec_size) &amt;&amt;
(!strcmp(pathname,t.pathname)) &amt;&amt;
(proj_id==t.proj_id) &amt;&amt;
(segment_page_num==t.segment_page_num) &amt;&amt;
(num_of_segment_pages==t.num_of_segment_pages) &amt;&amt;
(first_elem_num==t.first_elem_num) &amt;&amt;
(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()

////////////////////////////////////////////////////////////////////
////// Chunk::mark()
////////////////////////////////////////////////////////////////////
//////
////// global_start_element - first element of found block
////// num_of_elements - memory for num_of_elements
//////
////// mark as used in the bit vector
//////
////////////////////////////////////////////////////////////////////

void Chunk::mark(int global_start_element,int num_of_elems) {
// mark num_of_elems starting at start_element
// as assigned. This function is used to link
// newly freed memory with a previous free block.
if ((first_elem_num <= global_start_element)&amt;&amt;
(global_start_element < (first_elem_num+num_of_elements)) ) {
int local_start_element=global_start_element-first_elem_num;
bit_vec.mark_items(local_start_element,num_of_elems);
} else {
std::clog << __FILE__ << ':' << __LINE__ << ':' << " mark(): ";
std::clog << "requested start_element outside of chunk.\n";
std::clog << "first_elem_num: " << first_elem_num << std::endl;
}
return;
}; // Chunk::mark()

////////////////////////////////////////////////////////////////////
////// Chunk::clear()
////////////////////////////////////////////////////////////////////
//////
////// start_element - first element of found block
////// num_of_elems - memory for num_of_elements
//////
////// clear set blocks as unused in the bit vector
//////
////////////////////////////////////////////////////////////////////

void Chunk::clear(int global_start_element,int num_of_elems) {
// clear num_of_elems starting at start_element
// as available.
if ((first_elem_num<=global_start_element)&amt;&amt;
(global_start_element<(first_elem_num+num_of_elements))) {
int local_start_element=global_start_element-first_elem_num;
bit_vec.clear_items(local_start_element,num_of_elems);
} else {
std::clog << __FILE__ << ':' << __LINE__ << ':' << " clear(): ";
std::clog << "requested start_element outside of chunk.\n";
std::clog << " first_elem_num: " << first_elem_num <<
" num_of_elements: " << num_of_elements << std::endl;
}
return;
}; // Chunk::clear()

////////////////////////////////////////////////////////////////////
////// Chunk::element_num_to_pointer(int global_start_element)
////////////////////////////////////////////////////////////////////
//////
////// global_start_element - compute the memory address of
////// this global element number.
//////
////// find and return the memory address, p, for this global
////// element number. Used to free blocks which are in use.
//////
////////////////////////////////////////////////////////////////////


unsigned char*
Chunk::element_num_to_pointer(int global_start_element) {
// Calculate and return the global block(element) number of the
// block residing at p.
int local_start_element = global_start_element - first_elem_num;
unsigned char* p = 0;
if ((0 <= local_start_element) &amt;&amt;
(local_start_element < num_of_elements)) {
p = mem+(local_start_element*element_size);
} else {
std::clog << __FILE__ << ':' << __LINE__ << ':' << " element_num_to_pointer(): ";
std::clog << "requested block outside of chunk.\n";
}
return p;
}; // Chunk::element_num_to_pointer()

////////////////////////////////////////////////////////////////////
////// Chunk::get_page_offset()
////////////////////////////////////////////////////////////////////
//////
////// Calculate the offset from the beginning of the Chunk
////// to the specified page number.
//////
////////////////////////////////////////////////////////////////////


const int Chunk::get_element_offset(int global_start_element) {
int element_num = global_start_element - first_elem_num;
if (element_num < 0) {
std::clog << "Error: " << __FILE__ << ':' << __LINE__ ;
std::clog << ": element number out of range: "
<< element_num << std::endl;
throw (Alloc_Exception::alloc_exception(0));
}
return (sizeof(Chunk) + // chunk header
bit_vec_size + // bit_vec space
element_num*element_size); // count to element
}; // const int Chunk::get_page_offset(int page_num)

////////////////////////////////////////////////////////////////////
////// Chunk::find_element_num()
////////////////////////////////////////////////////////////////////
//////
////// p - pointer to allocated memory.
//////
////// Returns element number corresponding to p if p is from
////// this chunk, or -1 if p is not from the chunk. The
////// element number returned is the local element number,
////// not the global element number.
//////
////////////////////////////////////////////////////////////////////

int Chunk::pointer_to_element_num(const unsigned char* p) {
int element_num = -1;
// set chunk memory lower bound
const unsigned char* lower_bound = mem;
// set chunk memory upper bound
const unsigned char* upper_bound = lower_bound +
element_size*num_of_elements;
if ((lower_bound<=p)&amt;&amt;(p<upper_bound)) {
// if the pointer is in the memory range of this chunk
element_num =
(static_cast<int>(p-lower_bound))/element_size;
} // if ((lower_bound<=p)&amt;&amt;(p<upper_bound))
return element_num;
};

////////////////////////////////////////////////////////////////////
////// Chunk::allocate()
////////////////////////////////////////////////////////////////////
//////
////// global_start_element - first element of found block
////// num_of_elements - memory for num_of_elements
//////
////// allocate adjusts pointers in the memory chunk and
////// returns a pointer to the start of the allocated
////// memory.
//////
////////////////////////////////////////////////////////////////////

mem_space::memory_index_t
Chunk::allocate(int global_start_element,
int num_of_elems) {
// allocate num_of_elems starting with element start_element
// assumes that:
// 1. global_start_element has already been located by find()
// as a free block,
// 2. That the memory at global_start_element has been marked
// as allocated by mark() and is now ready to be returned

// mark the elements as in use.
mark(global_start_element,num_of_elems);
unsigned char* p = element_num_to_pointer(global_start_element);
// The segment_page_num can be used to determine global offset
// from beginning of a memory segment to the start of a shared
// memory segment page. Chunks are allocated so that they reside
// a the beginnings of these pages. The global offset =
// chunk_offset + element_offset within the chunk. These values
// are used to compute the offset from segment start to beginning
// of this chunk, to a specific element if desired.
// int segment_page_num = get_segment_page_num();
// compute offset from beginning of this chunk to element number.
int element_offset = get_element_offset(global_start_element);
// return p;

return mem_space::memory_index_t(p,
pathname,
proj_id,
segment_page_num,
element_offset,
global_start_element);
}; // Chunk::allocate()

////////////////////////////////////////////////////////////////////
////// Chunk::free()
////////////////////////////////////////////////////////////////////
//////
////// num_of_elems - memory for num_of_elems
//////
////// free adjusts pointers in the memory chunk
//////
//////
////////////////////////////////////////////////////////////////////

// release chunk elements
void Chunk::free(int global_start_element, int num_of_elems) {
clear(global_start_element,num_of_elems);
return;

}; // Chunk::free()



} // namespace pooled_allocator