• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision123 (tree)
Time2018-09-10 06:59:09
Authorquiret

Log Message

- optimized the native heap allocator by allowing growing memory regions to shrink or grow the virtual memory space aswell, potentially decreasing the amount of required memory copies.

Change Summary

Incremental Difference

--- common/sdk/OSUtils.memheap.h (revision 122)
+++ common/sdk/OSUtils.memheap.h (revision 123)
@@ -546,6 +546,29 @@
546546 return ( lastFreeBlock->freeRegion.GetSliceStartPoint() - (size_t)this );
547547 }
548548
549+ private:
550+ AINLINE bool grow_validity_region( NativeHeapAllocator *manager, VMemFreeBlock *lastFreeBlock, size_t newReqSize )
551+ {
552+ bool growSuccess = manager->nativeMemProv.SetHandleSize( this->allocHandle, newReqSize );
553+
554+ if ( growSuccess )
555+ {
556+ if ( lastFreeBlock->freeRegion.IsEmpty() == false )
557+ {
558+ this->avlSortedBySize.RemoveByNodeFast( &lastFreeBlock->sortedBySizeNode );
559+ }
560+
561+ // Grow the available free space.
562+ lastFreeBlock->freeRegion.SetSliceEndPoint( this->allocHandle->GetTargetSlice().GetSliceEndPoint() );
563+
564+ // Since we have grown we must have some space now.
565+ this->avlSortedBySize.Insert( &lastFreeBlock->sortedBySizeNode );
566+ }
567+
568+ return growSuccess;
569+ }
570+
571+ public:
549572 // Each memory island can maybe allocate new data.
550573 // If an island cannot allocate anymore, maybe it can later, but we
551574 // (almost) always can create another island!
@@ -632,21 +655,10 @@
632655 // Calculate the required new virtual memory size.
633656 size_t newReqSize = ( finalMemEndOffset - vmemOffset );
634657
635- bool growSuccess = manager->nativeMemProv.SetHandleSize( this->allocHandle, newReqSize );
658+ bool growSuccess = grow_validity_region( manager, lastFreeBlock, newReqSize );
636659
637660 if ( growSuccess )
638661 {
639- if ( lastFreeBlock->freeRegion.IsEmpty() == false )
640- {
641- this->avlSortedBySize.RemoveByNodeFast( &lastFreeBlock->sortedBySizeNode );
642- }
643-
644- // Grow the available free space.
645- lastFreeBlock->freeRegion.SetSliceEndPoint( this->allocHandle->GetTargetSlice().GetSliceEndPoint() );
646-
647- // Since we have grown we must have some space now.
648- this->avlSortedBySize.Insert( &lastFreeBlock->sortedBySizeNode );
649-
650662 // Just return the new spot.
651663 // We will insert to the end node.
652664 allocPtr = (void*)tryNewMemOffset;
@@ -719,11 +731,50 @@
719731 return newAlloc;
720732 }
721733
734+ private:
735+ AINLINE bool is_last_node( VMemAllocation *allocObj )
736+ {
737+ return ( this->sortedByAddrFreeBlocks.root.prev == &allocObj->freeSpaceAfterThis.sortedByAddrNode );
738+ }
739+
740+ AINLINE void truncate_to_minimum_space( NativeHeapAllocator *manager, VMemFreeBlock *lastFreeBlock )
741+ {
742+ // WARNING: we assume that lastFreeBlock IS NOT INSIDE THE AVL TREE.
743+
744+ // Make sure we at least have the minimum size.
745+ size_t pageSize = manager->nativeMemProv.GetPageSize();
746+
747+ size_t minSizeByPage = ( pageSize * MIN_PAGES_FOR_ISLAND );
748+
749+ size_t actualReqSize = minSizeByPage;
750+
751+ // Minimum size by span.
752+ {
753+ size_t vmemOff = (size_t)this;
754+
755+ size_t newReqSize_local = ( lastFreeBlock->freeRegion.GetSliceStartPoint() - (size_t)this );
756+
757+ if ( newReqSize_local > actualReqSize )
758+ {
759+ actualReqSize = newReqSize_local;
760+ }
761+ }
762+
763+ bool gotToShrink = manager->nativeMemProv.SetHandleSize( this->allocHandle, actualReqSize );
764+
765+ assert( gotToShrink == true );
766+
767+ // Update the region of free space for the last block.
768+ lastFreeBlock->freeRegion.SetSliceEndPoint( this->allocHandle->GetTargetSlice().GetSliceEndPoint() );
769+ }
770+
771+ public:
722772 inline void Free( NativeHeapAllocator *manager, VMemAllocation *allocObj )
723773 {
724- bool isLastNode = ( this->sortedByAddrFreeBlocks.root.prev == &allocObj->freeSpaceAfterThis.sortedByAddrNode );
774+ bool isLastNode = is_last_node( allocObj );
725775
726776 // We simply release out the memory that we are asked to free.
777+ VMemFreeBlock *potLastFreeBlock = nullptr;
727778 {
728779 size_t newFreeEndOffset = allocObj->freeSpaceAfterThis.freeRegion.GetSliceEndPoint();
729780
@@ -742,12 +793,11 @@
742793
743794 prevFreeBlock->freeRegion.SetSliceEndPoint( newFreeEndOffset );
744795
745- // Kinda has to have a size now.
746- assert( prevFreeBlock->freeRegion.IsEmpty() == false );
747-
748- this->avlSortedBySize.Insert( &prevFreeBlock->sortedBySizeNode );
796+ // If we deleted the last block, then the previous one becomes the new last.
797+ potLastFreeBlock = prevFreeBlock;
749798 }
750799
800+ // Kill the current last node, with the free block.
751801 if ( allocObj->freeSpaceAfterThis.freeRegion.IsEmpty() == false )
752802 {
753803 this->avlSortedBySize.RemoveByNodeFast( &allocObj->freeSpaceAfterThis.sortedBySizeNode );
@@ -761,32 +811,15 @@
761811 // the required memory region to best-fit.
762812 if ( isLastNode )
763813 {
764- // Make sure we at least have the minimum size.
765- size_t pageSize = manager->nativeMemProv.GetPageSize();
814+ VMemFreeBlock *lastFreeBlock = potLastFreeBlock;
766815
767- size_t minSizeByPage = ( pageSize * MIN_PAGES_FOR_ISLAND );
816+ truncate_to_minimum_space( manager, lastFreeBlock );
817+ }
768818
769- size_t actualReqSize = minSizeByPage;
770-
771- // Minimum size by span.
772- VMemFreeBlock *lastFreeBlock = LIST_GETITEM( VMemFreeBlock, this->sortedByAddrFreeBlocks.root.prev, sortedByAddrNode );
773- {
774- size_t vmemOff = (size_t)this;
775-
776- size_t newReqSize_local = ( lastFreeBlock->freeRegion.GetSliceStartPoint() - (size_t)this );
777-
778- if ( newReqSize_local > actualReqSize )
779- {
780- actualReqSize = newReqSize_local;
781- }
782- }
783-
784- bool gotToShrink = manager->nativeMemProv.SetHandleSize( this->allocHandle, actualReqSize );
785-
786- assert( gotToShrink == true );
787-
788- // Update the region of free space for the last block.
789- lastFreeBlock->freeRegion.SetSliceEndPoint( this->allocHandle->GetTargetSlice().GetSliceEndPoint() );
819+ // Kinda has to have a size now (?).
820+ if ( potLastFreeBlock->freeRegion.IsEmpty() == false )
821+ {
822+ this->avlSortedBySize.Insert( &potLastFreeBlock->sortedBySizeNode );
790823 }
791824 }
792825
@@ -801,6 +834,12 @@
801834 if ( oldDataSize == newSize )
802835 return true;
803836
837+ bool isGrowingAlloc = ( oldDataSize < newSize );
838+
839+ // If we are the last allocation we can either shrink or grow the allocation depending on the
840+ // requested size.
841+ bool isLastNode = is_last_node( memHandle );
842+
804843 // Since we know the free space after the memory handle, we can simply grow or shrink without issue.
805844 // The operation takes logarithmic time though, because we update the AVL tree.
806845
@@ -807,30 +846,55 @@
807846 size_t startOfDataOffset = (size_t)memPtr;
808847
809848 size_t newRequestedStartOfFreeBytes = ( startOfDataOffset + newSize );
810-
849+
811850 // Get the offset to the byte that is last of the available (possible) free space.
812851 size_t endOfFreeSpaceOffset = memHandle->freeSpaceAfterThis.freeRegion.GetSliceEndPoint();
813852
814853 // If this is not a valid offset for the free bytes, we bail.
815854 // We add 1 because it could become empty aswell.
855+ // (I guess this could only be triggered if we grow memory?)
816856 if ( endOfFreeSpaceOffset + 1 < newRequestedStartOfFreeBytes )
817- return false;
857+ {
858+ // If we are the last node we could actually try to grow the island.
859+ if ( !isLastNode )
860+ {
861+ return false;
862+ }
818863
864+ assert( isGrowingAlloc );
865+
866+ size_t requiredMemSize = ( newRequestedStartOfFreeBytes - (size_t)this );
867+
868+ bool couldGrow = grow_validity_region( manager, &memHandle->freeSpaceAfterThis, requiredMemSize );
869+
870+ if ( !couldGrow )
871+ {
872+ // We absolutely fail.
873+ return false;
874+ }
875+
876+ // Second wind! We got more space.
877+ }
878+
819879 // Update the meta-data.
820- VMemIsland *memIsland = memHandle->manager;
821-
822880 if ( memHandle->freeSpaceAfterThis.freeRegion.IsEmpty() == false )
823881 {
824- memIsland->avlSortedBySize.RemoveByNodeFast( &memHandle->freeSpaceAfterThis.sortedBySizeNode );
882+ this->avlSortedBySize.RemoveByNodeFast( &memHandle->freeSpaceAfterThis.sortedBySizeNode );
825883 }
826884
827- memHandle->freeSpaceAfterThis.freeRegion = memBlockSlice_t::fromOffsets( newRequestedStartOfFreeBytes, endOfFreeSpaceOffset );
885+ memHandle->freeSpaceAfterThis.freeRegion.SetSliceStartPoint( newRequestedStartOfFreeBytes );
828886 memHandle->dataSize = newSize;
829887
888+ // If we are actually shrinking the allocation, we should try to truncate the virtual memory to the minimum required.
889+ if ( isLastNode && !isGrowingAlloc )
890+ {
891+ truncate_to_minimum_space( manager, &memHandle->freeSpaceAfterThis );
892+ }
893+
830894 // Insert the new thing again.
831895 if ( memHandle->freeSpaceAfterThis.freeRegion.IsEmpty() == false )
832896 {
833- memIsland->avlSortedBySize.Insert( &memHandle->freeSpaceAfterThis.sortedBySizeNode );
897+ this->avlSortedBySize.Insert( &memHandle->freeSpaceAfterThis.sortedBySizeNode );
834898 }
835899
836900 return true;
--- unittests/src/string.cpp (revision 122)
+++ unittests/src/string.cpp (revision 123)
@@ -123,6 +123,8 @@
123123 {
124124 string.Insert( n * 3, insert_chars, sizeof(insert_chars) - 1 );
125125 }
126+
127+ assert( string.GetLength() == INSERT_COUNT * ( sizeof(insert_chars) - 1 ) );
126128 }
127129 printf( "ok.\n" );
128130
Show on old repository browser