File contents
#include <string.h>
#include "Memspace.h"
extern "C" char* strerror(int);
#ifdef IDEBUG
#define DB_PRINT(a,b) {if(a){b;}}
#else
#define DB_PRINT(a,b) /**/
#endif
const int MINSEG = 1; // minimum size of mem segment (avoid fragmentation)
class Memseg : public Link { // chunk of memory within a contiguous area
private:
friend class Memspace;
long m_offset;
long m_size;
enum { m_chunk = 16 };
static Memseg* m_free;
void* operator new(size_t);
void operator delete(void*,size_t);
public:
Memseg( long o, long sz ) : m_offset(o), m_size(sz) {}
void display(); // virtual
};
Memseg* Memseg::m_free;
void*
Memseg::operator new(size_t sz)
{
register Memseg* p;
if ( (p=m_free) == 0 ) {
register Memseg* q = (Memseg*) new char[m_chunk*sz];
for (p=m_free=&q[m_chunk-1]; q<p; p--)
p->next = p-1;
(p+1)->next = 0;
}
else {
m_free = (Memseg*)p->next;
}
return p;
}
void
Memseg::operator delete(void* vp, size_t)
{
Memseg* p = (Memseg*)vp;
p->next = m_free;
m_free = p;
vp = 0;
}
Memspace::Memspace( long sz, char* n, unsigned long flags )
{
// initial space contains 1 free seg covering the whole area
M_name = n;
M_size = sz;
M_seg >>= new Memseg( 0, sz );
M_flags = flags;
}
Memspace::~Memspace() {}
#ifdef IDEBUG
void
Memspace::set_debug( int i )
{
M_debug = i;
DB_PRINT(M_debug>=1,fprintf(dbfile,
"\ndebugging Memspace '%s', size 0x%.8lx\n",M_name,M_size));
}
#endif
long
Memspace::allocseg( long sz )
{
// use first-fit
DB_PRINT( M_debug>=1,
fprintf(dbfile,"\n'%s'->allocseg( 0x%.8lx )\n",M_name,sz);
if( M_debug>=2 ) print();
);
Memseg *m = (Memseg*)M_seg.head(), *l=0;
for ( ; m; l=m, m=(Memseg*)m->next ) {
if ( m->m_size >= sz ) {
long rr;
if ( (m->m_size-sz) >= MINSEG ) {
m->m_offset += sz;
m->m_size -= sz;
rr = m->m_offset - sz;
} else {
// delete this chunk
M_seg.delnext(l);
rr = m->m_offset;
delete m;
}
DB_PRINT( M_debug>=2,
fprintf(dbfile, " -- returning offset 0x%.8lx\n",rr);
print();
);
return rr;
}
}
if ( (M_flags & M_dynamic) && grow(sz) ) {
static int r = 0;
if ( r++ > 0 ) { // sanity check
fprintf(stderr, "OOPS! -- %d recursions of Memspace::allocseg()\n",r-1);
print();
DB_PRINT(M_debug>=1, fprintf(dbfile,"OOPS! -- more than one recursion of Memspace::allocseg()\n");print(););
exit(1);
} else {
--r;
return allocseg(sz);
}
} else {
fprintf(stderr,"can't allocate 0x%.8lx units in Memspace '%s', sz 0x%.8lx\n",sz,M_name,M_size);
DB_PRINT(M_debug>=1,fprintf(dbfile,"can't allocate 0x%.8lx units in Memspace '%s', sz 0x%.8lx\n",sz,M_name,M_size););
}
return -1;
}
#if 0
long
Memspace::placeseg( long off, long sz )
{
// use first-fit
DB_PRINT( M_debug>=1,
fprintf(dbfile,"\n'%s'->placeseg( 0x%.8lx, 0x%.8lx )\n",M_name,off,sz);
if( M_debug>=2 ) print();
);
Memseg *m = (Memseg*)M_seg.head(), *l=0;
for ( ; m; l=m, m=(Memseg*)m->next ) {
if ( m->m_offset + m->m_size < off ) continue;
if ( m->m_offset > off ) break;
if ( (m->m_offset + m->m_size - off) < sz ) break;
long d1 = off - m->m_offset;
long d2 = m->m_offset + m->m_size - (off + sz);
if ( d1 == 0 ) {
if ( d2 == 0 ) { M_seg.delnext(l); delete m; }
else { m->m_offset = off + sz; m->m_size = d2; }
} else if ( d2 == 0 ) {
if ( d1 == 0 ) { M_seg.delnext(l); delete m; }
else m->m_size = d1;
} else { // fragment
Memseg *n = new Memseg(off+sz,d2);
m->m_size = d1;
M_seg.addnext(m,n);
}
return off;
}
fprintf(stderr,"can't place 0x%.8lx units at offset 0x%.8lx in Memspace '%s', sz 0x%.8lx\n",sz,off,M_name,M_size);
DB_PRINT(M_debug>=1,fprintf(dbfile,"can't place 0x%.8lx units at offset 0x%.8lx in Memspace '%s', sz 0x%.8lx\n",sz,off,M_name,M_size););
return -1;
}
#endif
void
Memspace::freeseg( long o, long sz )
{
DB_PRINT( M_debug>=1,
fprintf(dbfile,"\n'%s'->freeseg( 0x%.8lx, 0x%.8lx )\n",M_name,o,sz);
if( M_debug>=2 ) { print(); newline(); }
);
// deallocate and merge adjacent free space
if ( o < 0 || (o+sz) >= M_size ) {
fprintf(stderr,"bad args to freeseg( 0x%.8lx, 0x%.8lx ) for Memspace '%s'",o,sz,M_name);
DB_PRINT(M_debug>=1,fprintf(dbfile,"bad args to freeseg( 0x%.8lx, 0x%.8lx ) for Memspace '%s'",o,sz,M_name););
return;
}
if ( sz == 0 ) return;
Memseg *m = (Memseg*)M_seg.head(), *l=0;
for ( ; m; l=m, m=(Memseg*)m->next )
if ( o < m->m_offset ) break;
// m is first free mem seg with offset > o
if ( m ) {
// sanity check
if ( (o+sz) > m->m_offset ) {
fprintf(stderr,"deallocating unallocated memory in memspace '%s' (o==0x%.8lx,sz==0x%.8lx)",M_name,o,sz);
DB_PRINT(M_debug>=1,fprintf(dbfile,"deallocating unallocated memory in memspace '%s' (o==0x%.8lx,sz==0x%.8lx)",M_name,o,sz););
return;
}
// merge if adjacent
if ( (o+sz) == m->m_offset ) {
sz += m->m_size;
M_seg.delnext(l); // m
delete m;
m = 0;
}
}
// try to merge with previous seg
if ( l ) {
// sanity check
if ( (l->m_offset+l->m_size) > o ) {
fprintf(stderr,"deallocating unallocated memory in memspace '%s' (o==0x%.8lx,sz==0x%.8lx)",M_name,o,sz);
DB_PRINT(M_debug>=1,fprintf(dbfile,"deallocating unallocated memory in memspace '%s' (o==0x%.8lx,sz==0x%.8lx)",M_name,o,sz););
return;
}
// merge if adjacent
if ( (l->m_offset+l->m_size) == o ) {
l->m_size += sz;
DB_PRINT( M_debug>=2,
fprintf(dbfile,"merged segment "); l->display();
newline(); print(); newline();
);
return;
}
}
// add new free mem seg
m = new Memseg(o,sz);
M_seg.addnext(l,m);
DB_PRINT( M_debug>=2, fprintf(dbfile,"adding ");
m->display(); newline(); print(); newline());
}
int
Memspace::grow( long sz )
{
Memseg* m = (Memseg*)M_seg.tail();
DB_PRINT( M_debug>=1,
fprintf(dbfile,"\n'%s'->grow( 0x%.8lx )\n",M_name,sz);
if( M_debug>=2 ) { print(); fprintf(dbfile,"\ntail== "); m->display(); }
);
if ( sz < MINSEG ) sz = MINSEG;
if ( (m->m_offset + m->m_size) == M_size )
m->m_size += sz; // increase size of last free segment
else
M_seg >>= new Memseg(M_size,sz); // add new free segment at end
M_size += sz;
DB_PRINT( M_debug>=1,
fprintf(dbfile,"\nafter '%s'->grow( 0x%.8lx )\n",M_name,sz);
if( M_debug>=2 ) print();
);
return 1;
}
#if 0
long
Memspace::nextfree( long o, long& sz )
{
if ( o < 0 || o >= M_size ) {
fprintf(stderr, "bad args to nextfree( 0x%.8lx, ... ) for Memspace '%s'",o,M_name);
DB_PRINT(M_debug>=1,fprintf(dbfile, "bad args to nextfree( 0x%.8lx, ... ) for Memspace '%s'",o,M_name););
sz = 0;
return o;
}
Memseg *m = (Memseg*)M_seg.head();
for ( ; m; m = (Memseg*)m->next )
if ( o < m->m_offset + m->m_size ) break;
if ( m == 0 ) {
sz = 0;
return M_size;
}
if ( o > m->m_offset ) {
fprintf(stderr,"'%s'->nextfree( 0x%.8lx ): offset in middle of free segment <0x%.8lx 0x%.8lx>",o,m->m_offset,m->m_size);
DB_PRINT(M_debug>=1,fprintf(stderr,"'%s'->nextfree( 0x%.8lx ): offset in middle of free segment <0x%.8lx 0x%.8lx>",o,m->m_offset,m->m_size););
sz = 0;
return o;
}
sz = m->m_size;
return m->m_offset;
}
void
Memspace::save( FILE* ofd )
{
long x = M_seg.length();
DB_PRINT(M_debug>=1,
fprintf(dbfile,"saving Memseg '%s', nsegs==%d\n",
M_name, x));
MUSTFWRITE( &x, sizeof(long), ofd );
Memseg *m = (Memseg*)M_seg.head();
for ( ; m; m = (Memseg*)m->next ) {
DB_PRINT(M_debug>=1,
fprintf(dbfile," o==0x%.8lx s==0x%.8lx\n",
m->m_offset, m->m_size));
MUSTFWRITE( &m->m_offset, sizeof(long), ofd );
MUSTFWRITE( &m->m_size, sizeof(long), ofd );
}
}
void
Memspace::restore( long* buf )
{
register long i = 0;
long x = buf[i++]; // nsegs
Memseg *h = (Memseg*)M_seg.head();
M_seg.delnext(0); // remove initial segment; list should now be empty
delete h;
DB_PRINT(M_debug>=1,
fprintf(dbfile,"restoring Memseg '%s', nsegs==%d\n", M_name, x));
for ( ; x>0; --x ) {
long o = buf[i++];
long s = buf[i++];
DB_PRINT(M_debug>=1,
fprintf(dbfile," o==0x%.8lx s==0x%.8lx\n",o,s));
M_seg >>= new Memseg( o, s );
}
}
#endif
void
Memseg::display()
{
fprintf(dbfile,"MEMSEG: offset==0x%.8lx, size==0x%.8lx",m_offset,m_size);
}
void
Memspace::print()
{
fprintf(dbfile,"Memspace '%s': size==0x%.8lx free list: ",M_name,M_size);
M_seg.display();
}