00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 #include <unistd.h>
00029 #include <sys/mman.h>
00030
00031 #include <qintdict.h>
00032 #include <qmap.h>
00033
00034 #include <ktempfile.h>
00035 #include <kdebug.h>
00036
00037 #include "kvmallocator.h"
00038
00039
00040 #define KVM_ALIGN 4095
00041
00042 struct KVMAllocator::Block
00043 {
00044 off_t start;
00045 size_t length;
00046 size_t size;
00047 void *mmap;
00048 };
00049
00050
00051 class KVMAllocatorPrivate
00052 {
00053 public:
00054 KTempFile *tempfile;
00055 off_t max_length;
00056 QMap<off_t, KVMAllocator::Block> used_blocks;
00057 QMap<off_t, KVMAllocator::Block> free_blocks;
00058 };
00059
00063 KVMAllocator::KVMAllocator()
00064 {
00065 d = new KVMAllocatorPrivate;
00066 d->tempfile = 0;
00067 d->max_length = 0;
00068 }
00069
00073 KVMAllocator::~KVMAllocator()
00074 {
00075 delete d->tempfile;
00076 delete d;
00077 }
00078
00083 KVMAllocator::Block *
00084 KVMAllocator::allocate(size_t _size)
00085 {
00086 if (!d->tempfile)
00087 {
00088 d->tempfile = new KTempFile(QString::null, "vmdata");
00089 d->tempfile->unlink();
00090 }
00091
00092 QMap<off_t,KVMAllocator::Block>::iterator it;
00093 it = d->free_blocks.begin();
00094 while (it != d->free_blocks.end())
00095 {
00096 if (it.data().size > _size)
00097 {
00098 Block &free_block = it.data();
00099 Block block;
00100 kdDebug(180)<<"VM alloc: using block from free list "<<(long)free_block.start<<" size ="<<(long)free_block.size<<" request = "<<_size<< endl;
00101 block.start = free_block.start;
00102 block.length = _size;
00103 block.size = (_size + KVM_ALIGN) & ~KVM_ALIGN;
00104 block.mmap = 0;
00105 free_block.size -= block.size;
00106 free_block.start += block.size;
00107 if (!free_block.size)
00108 d->free_blocks.remove(it);
00109 it = d->used_blocks.replace(block.start, block);
00110 return &(it.data());
00111 }
00112 ++it;
00113 }
00114
00115
00116
00117 Block block;
00118 block.start = d->max_length;
00119 block.length = _size;
00120 block.size = (_size + KVM_ALIGN) & ~KVM_ALIGN;
00121 block.mmap = 0;
00122 kdDebug(180)<<"VM alloc: using new block "<<(long)block.start<<" size ="<<(long)block.size<<" request = "<<_size<< endl;
00123 it = d->used_blocks.replace(block.start, block);
00124 d->max_length += block.size;
00125 return &(it.data());
00126 }
00127
00131 void
00132 KVMAllocator::free(Block *block_p)
00133 {
00134 Block block = *block_p;
00135 if (block.mmap)
00136 {
00137 kdDebug(180)<<"VM free: Block "<<(long)block.start<<" is still mmapped!"<<endl;
00138 return;
00139 }
00140 QMap<off_t,KVMAllocator::Block>::iterator it;
00141 it = d->used_blocks.find(block.start);
00142 if (it == d->used_blocks.end())
00143 {
00144 kdDebug(180)<<"VM free: Block "<<(long)block.start<<" is not allocated."<<endl;
00145 return;
00146 }
00147 d->used_blocks.remove(it);
00148 it = d->free_blocks.replace(block.start, block);
00149 QMap<off_t,KVMAllocator::Block>::iterator before = it;
00150 --before;
00151 if (before != d->free_blocks.end())
00152 {
00153 Block &block_before = before.data();
00154 if ((block_before.start + off_t(block_before.size)) == block.start)
00155 {
00156
00157 kdDebug(180) << "VM merging: Block "<< (long)block_before.start<<
00158 " with "<< (long)block.start<< " (before)" << endl;
00159 block.size += block_before.size;
00160 block.start = block_before.start;
00161 it.data() = block;
00162 d->free_blocks.remove(before);
00163 }
00164 }
00165
00166 QMap<off_t,KVMAllocator::Block>::iterator after = it;
00167 ++after;
00168 if (after != d->free_blocks.end())
00169 {
00170 Block &block_after = after.data();
00171 if ((block.start + off_t(block.size)) == block_after.start)
00172 {
00173
00174 kdDebug(180) << "VM merging: Block "<< (long)block.start<<
00175 " with "<< (long)block_after.start<< " (after)" << endl;
00176 block.size += block_after.size;
00177 it.data() = block;
00178 d->free_blocks.remove(after);
00179 }
00180 }
00181 }
00182
00186 void
00187 KVMAllocator::copy(void *dest, Block *src, int _offset, size_t length)
00188 {
00189 (void) copyBlock(dest, src, _offset, length);
00190 }
00191
00192 bool
00193 KVMAllocator::copyBlock(void *dest, Block *src, int _offset, size_t length)
00194 {
00195
00196 lseek(d->tempfile->handle(), src->start+_offset, SEEK_SET);
00197 if (length == 0)
00198 length = src->length - _offset;
00199 int to_go = length;
00200 int done = 0;
00201 char *buf = (char *) dest;
00202 while(to_go > 0)
00203 {
00204 int n = read(d->tempfile->handle(), buf+done, to_go);
00205 if (n <= 0)
00206 {
00207 if (n < 0)
00208 return false;
00209 else
00210 return true;
00211 }
00212 done += n;
00213 to_go -= n;
00214 }
00215
00216 return true;
00217 }
00218
00222 void
00223 KVMAllocator::copy(Block *dest, void *src, int _offset, size_t length)
00224 {
00225 (void) copyBlock(dest, src, _offset, length);
00226 }
00227
00228 bool
00229 KVMAllocator::copyBlock(Block *dest, void *src, int _offset, size_t length)
00230 {
00231
00232 lseek(d->tempfile->handle(), dest->start+_offset, SEEK_SET);
00233 if (length == 0)
00234 length = dest->length - _offset;
00235 int to_go = length;
00236 int done = 0;
00237 char *buf = (char *) src;
00238 while(to_go > 0)
00239 {
00240 int n = write(d->tempfile->handle(), buf+done, to_go);
00241 if (n <= 0) return false;
00242 done += n;
00243 to_go -= n;
00244 }
00245
00246 return true;
00247 }
00248
00252 void *
00253 KVMAllocator::map(Block *block)
00254 {
00255 if (block->mmap)
00256 return block->mmap;
00257
00258 void *result = mmap(0, block->length, PROT_READ| PROT_WRITE,
00259 MAP_SHARED, d->tempfile->handle(), block->start);
00260 block->mmap = result;
00261 return block->mmap;
00262 }
00263
00267 void
00268 KVMAllocator::unmap(Block *block)
00269 {
00270
00271
00272 munmap((char *)block->mmap, block->length);
00273 block->mmap = 0;
00274 }