# kdecore Library API Documentation

Overview | Class Hierarchy | Classes | Classes (annotated) | Members | Namespaces | Source Files

# 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(QString::null, "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(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    // 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(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          // Merge blocks.
    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          // Merge blocks.
    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    //kdDebug(180)<<"VM read: seek "<<(long)src->start<<" +"<<_offset<<":"<<length<<endl;
    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; // Error
    00209          else
    00210             return true; // End of data
    00211       }
    00212       done += n;
    00213       to_go -= n;
    00214    }
    00215    // Done.
    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    //kdDebug(180)<<"VM write: seek "<<(long)dest->start<<" +"<<_offset<< ":" << length << endl;
    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; // Error
    00242       done += n;
    00243       to_go -= n;
    00244    }
    00245    // Done.
    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    // The following cast is necassery for Solaris.
    00271    // (touch it and die). --Waba
    00272    munmap((char *)block->mmap, block->length);
    00273    block->mmap = 0;
    00274 }

This file is part of the documentation for kdecore Library Version 3.4.1.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Sat Jun 11 20:18:12 2005 by doxygen 1.4.1 written by Dimitri van Heesch, © 1997-2003