--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hbcore/core/hbmultisegmentallocator_p.cpp Mon Apr 19 14:02:13 2010 +0300
@@ -0,0 +1,282 @@
+/****************************************************************************
+**
+** Copyright (C) 2008-2010 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (developer.feedback@nokia.com)
+**
+** This file is part of the HbCore module of the UI Extensions for Mobile.
+**
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this file.
+** Please review the following information to ensure the GNU Lesser General
+** Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at developer.feedback@nokia.com.
+**
+****************************************************************************/
+
+
+#include "hbsharedmemoryallocators_p.h"
+
+#include <QDebug>
+#include <QSharedMemory>
+
+// this identifier is used to check, if the multisegment allocator is already
+// initialized in given shared chunk
+static const unsigned int INITIALIZED_MULTISEGMENTALLOCATOR_IDENTIFIER = 0x4D554C54; //'MULT'
+
+// chunk sizes
+// every size is aligned to 8
+static const int ChunkSizes[AMOUNT_OF_DIFFERENT_CHUNK_SIZES] = {8, 16, 24, 32, 48, 64, 120, 224};
+
+static const int CHUNKS_IN_ONE_LIST = 512;
+
+/*
+* HbMultiSegmentAlgo implementation
+*
+* Since this function is crucial to the working of HbSharedMemory manager, it's required
+* that it's initialize function is successfully completed. In the OOM condition,
+* the exception is thrown.
+*
+* All chunk sizes should be multiples of 8 (so that the memory is automatically aligned).
+* Based on actual data, following ranges are used:
+*
+* Range of sizes Number of allocations for several applications
+* between 0-8 926
+* between 9-16 7715
+* between 17-24 5814
+* between 25-32 364
+* between 33-48 409
+* between 49-64 587
+* between 65-120 430
+* between 121-224 2322
+*
+*/
+
+/**
+ * HbMultiSegmentAllocator::initialize
+ *
+ * Initializes multisegment allocator.
+ * This allocates memory from main allocator and won't block main allocator's
+ * OOM exception.
+ */
+void HbMultiSegmentAllocator::initialize(QSharedMemory *sharedChunk,
+ const unsigned int offset,
+ HbSharedMemoryAllocator *mainAllocator)
+{
+ chunk = sharedChunk;
+ this->offset = offset;
+ this->mainAllocator = mainAllocator;
+
+ // initialize fast index-getter table
+ int index = 0;
+ for (int i = 0; i < AMOUNT_OF_DIFFERENT_CHUNK_SIZES; i++) {
+ int limit = ChunkSizes[i];
+ do {
+ indexTable[index++] = i;
+ } while (index <= limit);
+ }
+
+ header = (MultiAllocatorHeader*)((unsigned char*)(chunk->data()) + offset);
+ if (header->identifier == INITIALIZED_MULTISEGMENTALLOCATOR_IDENTIFIER) {
+ return; // already initialized
+ }
+
+ // every chunk list have space for 512 chunks
+ ChunkListHeader *listHeader;
+ for (int i = 0; i < AMOUNT_OF_DIFFERENT_CHUNK_SIZES; i++) {
+ header->offsetsToChunkLists[i] = mainAllocator->alloc(sizeof(ChunkListHeader) + (sizeof(int)+ChunkSizes[i])*CHUNKS_IN_ONE_LIST);
+ header->offsetsToFreeChunkLists[i] = header->offsetsToChunkLists[i];
+ listHeader = (ChunkListHeader*)((unsigned char*)(chunk->data()) + header->offsetsToChunkLists[i]);
+ listHeader->chunkListIndex = i;
+ listHeader->freedChunkCursor = -1;
+ listHeader->allocCursor = header->offsetsToChunkLists[i]+sizeof(ChunkListHeader);
+ listHeader->previousListOffset = -1;
+ listHeader->nextListOffset = -1;
+ listHeader->allocatedChunks = 0;
+ }
+
+ header->identifier = INITIALIZED_MULTISEGMENTALLOCATOR_IDENTIFIER;
+}
+
+/*
+* Constructor
+*/
+HbMultiSegmentAllocator::HbMultiSegmentAllocator():
+ chunk(0),
+ offset(0),
+ mainAllocator(0),
+ header(0)
+{
+}
+
+/*
+* Destructor
+*/
+HbMultiSegmentAllocator::~HbMultiSegmentAllocator()
+{
+}
+
+/*
+* alloc function
+* Will throw OOM (from main allocator) in case we run out of memory.
+*/
+int HbMultiSegmentAllocator::alloc(int size)
+{
+ // size should already be between 1...max. chunk size - no need to check
+
+ // first find out correct list of chunks
+ int i = indexTable[size];
+
+ // qDebug() << "HbMultiSegmentAllocator::alloc, with size " << size << " chunkList " << i << " used\n";
+
+ int dataOffset = -1;
+ int *metaData = 0;
+ // this should always point to list with free chunks
+ ChunkListHeader *listHeader = (ChunkListHeader*)((unsigned char*)(chunk->data()) + header->offsetsToFreeChunkLists[i]);
+
+ if (listHeader->freedChunkCursor >= 0) { // freedChunkCursor points to freed chunk
+ dataOffset = listHeader->freedChunkCursor + sizeof(int);
+ metaData = (int*)((unsigned char*)(chunk->data())+listHeader->freedChunkCursor);
+ listHeader->freedChunkCursor = *metaData; // point to next freed chunk
+ } else { // no chunks freed -> allocate in order
+ dataOffset = listHeader->allocCursor + sizeof(int);
+ metaData = (int*)((unsigned char*)(chunk->data())+listHeader->allocCursor);
+ // we will never allocate from full list, so allocCursor is always valid
+ listHeader->allocCursor += ChunkSizes[listHeader->chunkListIndex]+sizeof(int);
+ }
+
+ // for allocated chunks metadata is:
+ // 00xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx,
+ // where xx... = offset to this list's header (max. 1 GB)
+ *metaData = header->offsetsToFreeChunkLists[i] /* & 0x3FFFFFFF */;
+ listHeader->allocatedChunks++;
+ if (listHeader->allocatedChunks == CHUNKS_IN_ONE_LIST) { // list full
+ if (!setFreeList(listHeader->chunkListIndex)) {
+ // there is no list(s) with free chunks, so add new list
+ addList(listHeader->chunkListIndex,
+ mainAllocator->alloc((sizeof(ChunkListHeader)+sizeof(int)+ChunkSizes[listHeader->chunkListIndex])*CHUNKS_IN_ONE_LIST));
+ }
+ }
+
+ return dataOffset;
+}
+
+/*
+* free the offset
+*/
+void HbMultiSegmentAllocator::free(int offset)
+{
+ // metadata has offset to list's header
+ int *metaData = (int*)((unsigned char*)(chunk->data())+offset-sizeof(int));
+ int listHeaderOffset = *metaData;
+ ChunkListHeader *listHeader = (ChunkListHeader*)((unsigned char*)(chunk->data()) + listHeaderOffset);
+ listHeader->allocatedChunks--;
+ if (listHeader->allocatedChunks == 0) {
+ // if there are multiple lists, this list could be released
+ ChunkListHeader *previous = 0;
+ if (listHeader->previousListOffset > -1) {
+ previous = (ChunkListHeader*)((unsigned char*)(chunk->data()) + listHeader->previousListOffset);
+ }
+ ChunkListHeader *next = 0;
+ if (listHeader->nextListOffset > -1) {
+ next = (ChunkListHeader*)((unsigned char*)(chunk->data()) + listHeader->nextListOffset);
+ }
+
+ if (previous || next) {
+ if (previous) {
+ previous->nextListOffset = listHeader->nextListOffset;
+ } else {
+ // with no previous list, we are removing first list
+ // and because if we don't have previous, next will be valid list
+ header->offsetsToChunkLists[listHeader->chunkListIndex] = listHeader->nextListOffset;
+ }
+ if (next) {
+ next->previousListOffset = listHeader->previousListOffset;
+ }
+ if (setFreeList(listHeader->chunkListIndex)) {
+ // there is space in other list(s), so this list can be removed
+ mainAllocator->free(listHeaderOffset);
+ } else {
+ // all the other lists are full, so just add this list back
+ addList(listHeader->chunkListIndex, listHeaderOffset);
+ }
+ } else {
+ // only list can't be freed
+ *metaData = listHeader->freedChunkCursor;
+ listHeader->freedChunkCursor = offset-sizeof(int);
+ }
+ } else {
+ // this list is not yet empty
+ *metaData = listHeader->freedChunkCursor;
+ listHeader->freedChunkCursor = offset-sizeof(int);
+ }
+}
+
+/**
+ * HbMultiSegmentAllocator::allocatedSize
+ *
+ * Used for reallocation.
+ * Returns actual allocated size for given offset.
+ */
+int HbMultiSegmentAllocator::allocatedSize(int offset)
+{
+ int *metaData = (int*)((unsigned char*)(chunk->data())+offset-sizeof(int));
+ ChunkListHeader *listHeader = (ChunkListHeader*)((unsigned char*)(chunk->data()) + *metaData);
+ // not actual size in alloc(), but the size of chunk, where this data is stored
+ return ChunkSizes[listHeader->chunkListIndex];
+}
+
+/*
+* Helper method for adding new list of chunks.
+* Won't fail, because memory for the list is already allocated (offset).
+*/
+void HbMultiSegmentAllocator::addList(int index, int offset)
+{
+ ChunkListHeader *newListHeader = (ChunkListHeader*)((unsigned char*)(chunk->data()) + offset);
+ ChunkListHeader *oldListHeader = (ChunkListHeader*)((unsigned char*)(chunk->data()) + header->offsetsToChunkLists[index]);
+ // when this method is called, there will be at least one list,
+ // so oldListHeader is valid and also all the lists are full
+ newListHeader->allocatedChunks = 0;
+ newListHeader->allocCursor = offset+sizeof(ChunkListHeader);
+ newListHeader->chunkListIndex = index;
+ newListHeader->freedChunkCursor = -1;
+ newListHeader->previousListOffset = -1;
+ newListHeader->nextListOffset = header->offsetsToChunkLists[index];
+ oldListHeader->previousListOffset = offset;
+ header->offsetsToChunkLists[index] = offset;
+ setFreeList(index); // won't fail, because we just added free list
+}
+
+/*
+* Try to set (new) free list to given index. If no such list exists (all are full),
+* return false. Otherwise sets free list and returns true.
+*/
+bool HbMultiSegmentAllocator::setFreeList(int index)
+{
+ ChunkListHeader *listHeader;
+ listHeader = (ChunkListHeader*)((unsigned char*)(chunk->data()) + header->offsetsToChunkLists[index]);
+ bool retVal = false;
+ for (;;) {
+ if (listHeader->allocatedChunks < CHUNKS_IN_ONE_LIST) {
+ int offset = (int)((char*)(listHeader)-(char*)(chunk->data()));
+ header->offsetsToFreeChunkLists[index] = offset;
+ retVal = true;
+ break;
+ }
+ if (listHeader->nextListOffset == -1) {
+ break;
+ }
+ listHeader = (ChunkListHeader*)((unsigned char*)(chunk->data()) + listHeader->nextListOffset);
+ }
+
+ return retVal;
+}