kdecore Library API Documentation

kvmallocator.cpp

00001 /*
00002     This file is part of the KDE libraries
00003 
00004     Copyright (C) 1999 Waldo Bastian (bastian@kde.org)
00005 
00006     This library is free software; you can redistribute it and/or
00007     modify it under the terms of the GNU Library General Public
00008     License as published by the Free Software Foundation; either
00009     version 2 of the License, or (at your option) any later version.
00010 
00011     This library is distributed in the hope that it will be useful,
00012     but WITHOUT ANY WARRANTY; without even the implied warranty of
00013     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014     Library General Public License for more details.
00015 
00016     You should have received a copy of the GNU Library General Public License
00017     along with this library; see the file COPYING.LIB.  If not, write to
00018     the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00019     Boston, MA 02111-1307, USA.
00020 */
00021 //----------------------------------------------------------------------------
00022 //
00023 // Virtual Memory Allocator
00024 
00025 // TODO: Add large file support.
00026 // TODO: Error reporting. (e.g. disk-full)
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; // Requested length
00046    size_t size; // Actual 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("/tmp/", "vmdata");
00089       d->tempfile->unlink();
00090    }
00091    // Search in free list
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(13020)<<"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    // Create new block
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(13020)<<"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(13020)<<"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(13020)<<"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 + block_before.size) == block.start)
00155       {
00156          // Merge blocks.
00157          kdDebug(13020) << "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 + block.size) == block_after.start)
00172       {
00173          // Merge blocks.
00174          kdDebug(13020) << "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    //kdDebug(13020)<<"VM read: seek "<<(long)src->start<<" +"<<_offset<<":"<<length<<endl;
00190    lseek(d->tempfile->handle(), src->start+_offset, SEEK_SET);
00191    if (length == 0)
00192       length = src->length - _offset;
00193    int to_go = length;
00194    int done = 0;
00195    char *buf = (char *) dest;
00196    while(done < to_go)
00197    {
00198       int n = read(d->tempfile->handle(), buf+done, to_go);
00199       if (n <= 0) return; // End of data or error
00200       done += n;
00201       to_go -= n;
00202    }
00203    // Done.
00204 }
00205 
00209 void
00210 KVMAllocator::copy(Block *dest, void *src, int _offset, size_t length)
00211 {
00212    //kdDebug(13020)<<"VM write: seek "<<(long)dest->start<<" +"<<_offset<< ":" << length << endl;
00213    lseek(d->tempfile->handle(), dest->start+_offset, SEEK_SET);
00214    if (length == 0)
00215       length = dest->length - _offset;
00216    int to_go = length;
00217    int done = 0;
00218    char *buf = (char *) src;
00219    while(done < to_go)
00220    {
00221       int n = write(d->tempfile->handle(), buf+done, to_go);
00222       if (n <= 0) return; // End of data or error
00223       done += n;
00224       to_go -= n;
00225    }
00226    // Done.
00227 }
00228 
00232 void *
00233 KVMAllocator::map(Block *block)
00234 {
00235    if (block->mmap)
00236       return block->mmap;
00237 
00238    void *result = mmap(0, block->length, PROT_READ| PROT_WRITE,
00239                        MAP_SHARED, d->tempfile->handle(), block->start);
00240    block->mmap = result;
00241    return block->mmap;
00242 }
00243 
00247 void
00248 KVMAllocator::unmap(Block *block)
00249 {
00250    // The following cast is necassery for Solaris.
00251    // (touch it and die). --Waba
00252    munmap((char *)block->mmap, block->length);
00253    block->mmap = 0;
00254 }
KDE Logo
This file is part of the documentation for kdelibs Version 3.1.4.
Documentation copyright © 1996-2002 the KDE developers.
Generated on Sun Feb 27 22:14:48 2005 by doxygen 1.3.4 written by Dimitri van Heesch, © 1997-2001