[haiku-commits] haiku: hrev46192 - in src/system/boot: loader platform/bios_ia32
- From: ingo_weinhold@xxxxxx
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Tue, 8 Oct 2013 21:04:24 +0200 (CEST)
hrev46192 adds 4 changesets to branch 'master'
old head: e67f9c9bd11e8dc9087fc0f91090609a6b1776e2
new head: ea4f2ac2dcfed69600d74c9d4b1e57cb3445b47d
overview: http://cgit.haiku-os.org/haiku/log/?qt=range&q=ea4f2ac+%5Ee67f9c9
----------------------------------------------------------------------------
908ce69: IteratableSplayTree: Add FindClosest()
33def42: boot loader: bios IA32: Add optional timestamps to debug output
e1b63b4: boot loader: mount_file_systems(): Fix warning
ea4f2ac: boot loader: Optimize heap implementation
* Increase general allocation alignment from 4 to 8 byte. That was even
incorrect.
* Use a splay tree instead of a singly linked list to manage the free
chunks. That increases the size of the per-chunk structure to manage
the free chunks, i.e. the of minimally allocatable memory size (from
align(sizeof(void*)) to align(3 * sizeof(void*))), but make finding
and inserting chunks much faster.
Fixes #10063 respectively improves the situation significantly.
[ Ingo Weinhold <ingo_weinhold@xxxxxx> ]
----------------------------------------------------------------------------
4 files changed, 218 insertions(+), 141 deletions(-)
headers/private/kernel/util/SplayTree.h | 5 +
src/system/boot/loader/heap.cpp | 313 +++++++++++++----------
src/system/boot/loader/vfs.cpp | 1 +
src/system/boot/platform/bios_ia32/debug.cpp | 40 ++-
############################################################################
Commit: 908ce69d6e1517e0e9339304d1173a4184b3f107
URL: http://cgit.haiku-os.org/haiku/commit/?id=908ce69
Author: Ingo Weinhold <ingo_weinhold@xxxxxx>
Date: Tue Oct 8 18:38:45 2013 UTC
IteratableSplayTree: Add FindClosest()
----------------------------------------------------------------------------
diff --git a/headers/private/kernel/util/SplayTree.h
b/headers/private/kernel/util/SplayTree.h
index f9a2b50..551a7a4 100644
--- a/headers/private/kernel/util/SplayTree.h
+++ b/headers/private/kernel/util/SplayTree.h
@@ -563,6 +563,11 @@ public:
return fTree.IsEmpty();
}
+ Node* FindClosest(const Key& key, bool greater, bool orEqual)
+ {
+ return fTree.FindClosest(key, greater, orEqual);
+ }
+
Node* FindMin()
{
return fTree.FindMin();
############################################################################
Commit: 33def4258ee66c2d0a2a28c8374f5562c4e3f00a
URL: http://cgit.haiku-os.org/haiku/commit/?id=33def42
Author: Ingo Weinhold <ingo_weinhold@xxxxxx>
Date: Tue Oct 8 18:48:08 2013 UTC
boot loader: bios IA32: Add optional timestamps to debug output
----------------------------------------------------------------------------
diff --git a/src/system/boot/platform/bios_ia32/debug.cpp
b/src/system/boot/platform/bios_ia32/debug.cpp
index 73d2906..39cfc1f 100644
--- a/src/system/boot/platform/bios_ia32/debug.cpp
+++ b/src/system/boot/platform/bios_ia32/debug.cpp
@@ -19,6 +19,10 @@
#include "serial.h"
+//#define PRINT_TIME_STAMPS
+ // Define to print a TSC timestamp before each line of output.
+
+
static const char* const kDebugSyslogSignature = "Haiku syslog";
static char sBuffer[16384];
@@ -28,22 +32,48 @@ static ring_buffer* sDebugSyslogBuffer = NULL;
static bool sPostCleanup = false;
+#ifdef PRINT_TIME_STAMPS
+extern "C" uint64 rdtsc();
+#endif
+
+
+static void
+syslog_write(const char* buffer, size_t length)
+{
+ if (sPostCleanup && sDebugSyslogBuffer != NULL) {
+ ring_buffer_write(sDebugSyslogBuffer, (const uint8*)buffer,
length);
+ } else if (sBufferPosition + length < sizeof(sBuffer)) {
+ memcpy(sBuffer + sBufferPosition, buffer, length);
+ sBufferPosition += length;
+ }
+}
+
+
static void
dprintf_args(const char *format, va_list args)
{
char buffer[512];
int length = vsnprintf(buffer, sizeof(buffer), format, args);
+ if (length == 0)
+ return;
if (length >= (int)sizeof(buffer))
length = sizeof(buffer) - 1;
- if (sPostCleanup && sDebugSyslogBuffer != NULL) {
- ring_buffer_write(sDebugSyslogBuffer, (const uint8*)buffer,
length);
- } else if (sBufferPosition + length < sizeof(sBuffer)) {
- memcpy(sBuffer + sBufferPosition, buffer, length);
- sBufferPosition += length;
+#ifdef PRINT_TIME_STAMPS
+ static bool sNewLine = true;
+
+ if (sNewLine) {
+ char timeBuffer[32];
+ snprintf(timeBuffer, sizeof(timeBuffer), "[%" B_PRIu64 "] ",
rdtsc());
+ syslog_write(timeBuffer, strlen(timeBuffer));
+ serial_puts(timeBuffer, strlen(timeBuffer));
}
+ sNewLine = buffer[length - 1] == '\n';
+#endif // PRINT_TIME_STAMPS
+
+ syslog_write(buffer, length);
serial_puts(buffer, length);
if (platform_boot_options() & BOOT_OPTION_DEBUG_OUTPUT)
############################################################################
Commit: e1b63b4fb869c7128e7da11d76ab0bb8acc58b94
URL: http://cgit.haiku-os.org/haiku/commit/?id=e1b63b4
Author: Ingo Weinhold <ingo_weinhold@xxxxxx>
Date: Tue Oct 8 18:48:30 2013 UTC
boot loader: mount_file_systems(): Fix warning
----------------------------------------------------------------------------
diff --git a/src/system/boot/loader/vfs.cpp b/src/system/boot/loader/vfs.cpp
index b94e5dd..ae95a85 100644
--- a/src/system/boot/loader/vfs.cpp
+++ b/src/system/boot/loader/vfs.cpp
@@ -611,6 +611,7 @@ mount_file_systems(stage2_args *args)
device = last;
}
*/
+(void)last;
}
last = device;
}
############################################################################
Revision: hrev46192
Commit: ea4f2ac2dcfed69600d74c9d4b1e57cb3445b47d
URL: http://cgit.haiku-os.org/haiku/commit/?id=ea4f2ac
Author: Ingo Weinhold <ingo_weinhold@xxxxxx>
Date: Tue Oct 8 19:03:20 2013 UTC
Ticket: https://dev.haiku-os.org/ticket/10063
boot loader: Optimize heap implementation
* Increase general allocation alignment from 4 to 8 byte. That was even
incorrect.
* Use a splay tree instead of a singly linked list to manage the free
chunks. That increases the size of the per-chunk structure to manage
the free chunks, i.e. the of minimally allocatable memory size (from
align(sizeof(void*)) to align(3 * sizeof(void*))), but make finding
and inserting chunks much faster.
Fixes #10063 respectively improves the situation significantly.
----------------------------------------------------------------------------
diff --git a/src/system/boot/loader/heap.cpp b/src/system/boot/loader/heap.cpp
index eecfd93..9d945fc 100644
--- a/src/system/boot/loader/heap.cpp
+++ b/src/system/boot/loader/heap.cpp
@@ -5,9 +5,6 @@
#include <boot/heap.h>
-#include <boot/platform.h>
-
-#include <algorithm>
#ifdef HEAP_TEST
# include <stdio.h>
@@ -15,6 +12,11 @@
#include <stdlib.h>
#include <string.h>
+#include <algorithm>
+
+#include <boot/platform.h>
+#include <util/SplayTree.h>
+
//#define TRACE_HEAP
#ifdef TRACE_HEAP
@@ -46,72 +48,169 @@
// if defined, the maximum heap usage is determined and printed before
// entering the kernel
-class FreeChunk {
+
+const static size_t kAlignment = 8;
+ // all memory chunks will be a multiple of this
+
+
+class Chunk {
public:
- void SetTo(size_t size,
FreeChunk* next);
+ size_t CompleteSize() const
+ {
+ return fSize;
+ }
+
+protected:
+ union {
+ size_t fSize;
+ char fAlignment[kAlignment];
+ };
+};
- uint32 Size() const;
- uint32 CompleteSize() const {
return fSize; }
- FreeChunk* Next() const { return
fNext; }
- void SetNext(FreeChunk*
next) { fNext = next; }
+class FreeChunk;
+
+
+struct FreeChunkData : SplayTreeLink<FreeChunk> {
+
+ FreeChunk* Next() const
+ {
+ return fNext;
+ }
+
+ FreeChunk** NextLink()
+ {
+ return &fNext;
+ }
+
+protected:
+ FreeChunk* fNext;
+};
+
+
+class FreeChunk : public Chunk, public FreeChunkData {
+public:
+ void SetTo(size_t size);
+
+ size_t Size() const;
- FreeChunk* Split(uint32 splitSize);
+ FreeChunk* Split(size_t splitSize);
bool IsTouching(FreeChunk*
link);
FreeChunk* Join(FreeChunk* link);
- void Remove(FreeChunk*
previous = NULL);
- void Enqueue();
void* AllocatedAddress()
const;
static FreeChunk* SetToAllocated(void* allocated);
- static addr_t NextOffset() { return
sizeof(uint32); }
+};
+
+
+struct FreeChunkKey {
+ FreeChunkKey(size_t size)
+ :
+ fSize(size),
+ fChunk(NULL)
+ {
+ }
+
+ FreeChunkKey(const FreeChunk* chunk)
+ :
+ fSize(chunk->Size()),
+ fChunk(chunk)
+ {
+ }
+
+ int Compare(const FreeChunk* chunk) const
+ {
+ size_t chunkSize = chunk->Size();
+ if (chunkSize != fSize)
+ return fSize < chunkSize ? -1 : 1;
+
+ if (fChunk == chunk)
+ return 0;
+ return fChunk < chunk ? -1 : 1;
+ }
private:
- uint32 fSize;
- FreeChunk* fNext;
+ size_t fSize;
+ const FreeChunk* fChunk;
};
-const static uint32 kAlignment = 4;
- // all memory chunks will be a multiple of this
+struct FreeChunkTreeDefinition {
+ typedef FreeChunkKey KeyType;
+ typedef FreeChunk NodeType;
+
+ static FreeChunkKey GetKey(const FreeChunk* node)
+ {
+ return FreeChunkKey(node);
+ }
+
+ static SplayTreeLink<FreeChunk>* GetLink(FreeChunk* node)
+ {
+ return node;
+ }
+
+ static int Compare(const FreeChunkKey& key, const FreeChunk* node)
+ {
+ return key.Compare(node);
+ }
+
+ static FreeChunk** GetListLink(FreeChunk* node)
+ {
+ return node->NextLink();
+ }
+};
+
+
+typedef IteratableSplayTree<FreeChunkTreeDefinition> FreeChunkTree;
+
static void* sHeapBase;
-static uint32 /*sHeapSize,*/ sMaxHeapSize, sAvailable, sMaxHeapUsage;
-static FreeChunk sFreeAnchor;
+static size_t /*sHeapSize,*/ sMaxHeapSize, sAvailable, sMaxHeapUsage;
+static FreeChunkTree sFreeChunkTree;
+
+static uint64 sTotalMallocCycles = 0;
+static uint64 sTotalFreeCycles = 0;
+
+
+static inline size_t
+align(size_t size)
+{
+ return (size + kAlignment - 1) & ~(kAlignment - 1);
+}
void
-FreeChunk::SetTo(size_t size, FreeChunk* next)
+FreeChunk::SetTo(size_t size)
{
fSize = size;
- fNext = next;
+ fNext = NULL;
}
/*! Returns the amount of bytes that can be allocated
in this chunk.
*/
-uint32
+size_t
FreeChunk::Size() const
{
- return fSize - FreeChunk::NextOffset();
+ return (addr_t)this + fSize - (addr_t)AllocatedAddress();
}
-/*! Splits the upper half at the requested location
- and returns it.
-*/
+/*! Splits the upper half at the requested location and returns it. This
chunk
+ will no longer be a valid FreeChunk object; only its fSize will be
valid.
+ */
FreeChunk*
-FreeChunk::Split(uint32 splitSize)
+FreeChunk::Split(size_t splitSize)
{
- splitSize = (splitSize - 1 + kAlignment) & ~(kAlignment - 1);
+ splitSize = align(splitSize);
- FreeChunk* chunk
- = (FreeChunk*)((uint8*)this + FreeChunk::NextOffset() +
splitSize);
- chunk->fSize = fSize - splitSize - FreeChunk::NextOffset();
- chunk->fNext = fNext;
+ FreeChunk* chunk = (FreeChunk*)((addr_t)AllocatedAddress() + splitSize);
+ size_t newSize = (addr_t)chunk - (addr_t)this;
+ chunk->fSize = fSize - newSize;
+ chunk->fNext = NULL;
- fSize = splitSize + FreeChunk::NextOffset();
+ fSize = newSize;
return chunk;
}
@@ -153,58 +252,17 @@ FreeChunk::Join(FreeChunk* chunk)
}
-void
-FreeChunk::Remove(FreeChunk* previous)
-{
- if (previous == NULL) {
- // find the previous chunk in the list
- FreeChunk* chunk = sFreeAnchor.fNext;
-
- while (chunk != NULL && chunk != this) {
- previous = chunk;
- chunk = chunk->fNext;
- }
-
- if (chunk == NULL)
- panic("try to remove chunk that's not in list");
- }
-
- previous->fNext = fNext;
- fNext = NULL;
-}
-
-
-void
-FreeChunk::Enqueue()
-{
- FreeChunk* chunk = sFreeAnchor.fNext;
- FreeChunk* last = &sFreeAnchor;
- while (chunk && chunk->Size() < fSize) {
- last = chunk;
- chunk = chunk->fNext;
- }
-
- fNext = chunk;
- last->fNext = this;
-
-#ifdef DEBUG_ALLOCATIONS
- memset((uint8*)this + sizeof(FreeChunk), 0xde,
- fSize - sizeof(FreeChunk));
-#endif
-}
-
-
void*
FreeChunk::AllocatedAddress() const
{
- return (void*)&fNext;
+ return (void*)static_cast<const FreeChunkData*>(this);
}
FreeChunk*
FreeChunk::SetToAllocated(void* allocated)
{
- return (FreeChunk*)((uint8*)allocated - FreeChunk::NextOffset());
+ return static_cast<FreeChunk*>((FreeChunkData*)allocated);
}
@@ -237,17 +295,17 @@ heap_init(stage2_args* args)
sHeapBase = base;
sMaxHeapSize = (uint8*)top - (uint8*)base;
- sAvailable = sMaxHeapSize - FreeChunk::NextOffset();
-#ifdef DEBUG_MAX_HEAP_USAGE
- sMaxHeapUsage = sMaxHeapSize - sAvailable;
-#endif
// declare the whole heap as one chunk, and add it
// to the free list
-
FreeChunk* chunk = (FreeChunk*)base;
- chunk->SetTo(sMaxHeapSize, NULL);
- sFreeAnchor.SetTo(0, chunk);
+ chunk->SetTo(sMaxHeapSize);
+ sFreeChunkTree.Insert(chunk);
+
+ sAvailable = chunk->Size();
+#ifdef DEBUG_MAX_HEAP_USAGE
+ sMaxHeapUsage = sMaxHeapSize - sAvailable;
+#endif
return B_OK;
}
@@ -274,11 +332,8 @@ grow_heap(uint32 bytes)
void
dump_chunks(void)
{
- FreeChunk* chunk = sFreeAnchor.Next();
- FreeChunk* last = &sFreeAnchor;
+ FreeChunk* chunk = sFreeChunkTree.FindMin();
while (chunk != NULL) {
- last = chunk;
-
printf("\t%p: chunk size = %ld, end = %p, next = %p\n", chunk,
chunk->Size(), (uint8*)chunk + chunk->CompleteSize(),
chunk->Next());
@@ -290,7 +345,7 @@ dump_chunks(void)
uint32
heap_available(void)
{
- return sAvailable;
+ return (uint32)sAvailable;
}
@@ -301,19 +356,17 @@ malloc(size_t size)
return NULL;
// align the size requirement to a kAlignment bytes boundary
- size = (size - 1 + kAlignment) & ~(size_t)(kAlignment - 1);
+ if (size < sizeof(FreeChunkData))
+ size = sizeof(FreeChunkData);
+ size = align(size);
if (size > sAvailable) {
dprintf("malloc(): Out of memory!\n");
return NULL;
}
- FreeChunk* chunk = sFreeAnchor.Next();
- FreeChunk* last = &sFreeAnchor;
- while (chunk && chunk->Size() < size) {
- last = chunk;
- chunk = chunk->Next();
- }
+ FreeChunk* chunk = sFreeChunkTree.FindClosest(FreeChunkKey(size), true,
+ true);
if (chunk == NULL) {
// could not find a free chunk as large as needed
@@ -321,30 +374,25 @@ malloc(size_t size)
return NULL;
}
- if (chunk->Size() > size + sizeof(FreeChunk) + kAlignment) {
- // if this chunk is bigger than the requested size,
- // we split it to form two chunks (with a minimal
- // size of kAlignment allocatable bytes).
-
- FreeChunk* freeChunk = chunk->Split(size);
- last->SetNext(freeChunk);
+ sFreeChunkTree.Remove(chunk);
+ sAvailable -= chunk->Size();
- // re-enqueue the free chunk at the correct position
- freeChunk->Remove(last);
- freeChunk->Enqueue();
- } else {
- // remove the chunk from the free list
+ void* allocatedAddress = chunk->AllocatedAddress();
- last->SetNext(chunk->Next());
+ // If this chunk is bigger than the requested size and there's enough
space
+ // left over for a new chunk, we split it.
+ if (chunk->Size() >= size + align(sizeof(FreeChunk))) {
+ FreeChunk* freeChunk = chunk->Split(size);
+ sFreeChunkTree.Insert(freeChunk);
+ sAvailable += freeChunk->Size();
}
- sAvailable -= size + sizeof(uint32);
#ifdef DEBUG_MAX_HEAP_USAGE
sMaxHeapUsage = std::max(sMaxHeapUsage, sMaxHeapSize - sAvailable);
#endif
- TRACE("malloc(%lu) -> %p\n", size, chunk->AllocatedAddress());
- return chunk->AllocatedAddress();
+ TRACE("malloc(%lu) -> %p\n", size, allocatedAddress);
+ return allocatedAddress;
}
@@ -398,54 +446,47 @@ free(void* allocated)
FreeChunk* freedChunk = FreeChunk::SetToAllocated(allocated);
#ifdef DEBUG_ALLOCATIONS
- if (freedChunk->CompleteSize() > sMaxHeapSize) {
- panic("freed chunk %p clobbered (%lx)!\n", freedChunk,
+ if (freedChunk->Size() > sMaxHeapSize - sAvailable) {
+ panic("freed chunk %p clobbered (%#zx)!\n", freedChunk,
freedChunk->Size());
}
{
- FreeChunk* chunk = sFreeAnchor.Next();
+ FreeChunk* chunk = sFreeChunkTree.FindMin();
while (chunk) {
- if (chunk->CompleteSize() > sMaxHeapSize || freedChunk
== chunk)
- panic("invalid chunk in free list, or double
free\n");
+ if (chunk->Size() > sAvailable || freedChunk == chunk)
+ panic("invalid chunk in free list (%p (%zu)),
or double free\n",
+ chunk, chunk->Size());
chunk = chunk->Next();
}
}
#endif
- sAvailable += freedChunk->CompleteSize();
-#ifdef DEBUG_MAX_HEAP_USAGE
- sMaxHeapUsage = std::max(sMaxHeapUsage, sMaxHeapSize - sAvailable);
-#endif
-
// try to join the new free chunk with an existing one
// it may be joined with up to two chunks
- FreeChunk* chunk = sFreeAnchor.Next();
- FreeChunk* last = &sFreeAnchor;
+ FreeChunk* chunk = sFreeChunkTree.FindMin();
int32 joinCount = 0;
while (chunk) {
+ FreeChunk* nextChunk = chunk->Next();
+
if (chunk->IsTouching(freedChunk)) {
- // almost "insert" it into the list before joining
- // because the next pointer is inherited by the chunk
- freedChunk->SetNext(chunk->Next());
- freedChunk = chunk->Join(freedChunk);
+ sFreeChunkTree.Remove(chunk);
+ sAvailable -= chunk->Size();
- // remove the joined chunk from the list
- last->SetNext(freedChunk->Next());
- chunk = last;
+ freedChunk = chunk->Join(freedChunk);
if (++joinCount == 2)
break;
}
- last = chunk;
- chunk = chunk->Next();
+ chunk = nextChunk;
}
- // enqueue the link at the right position; the
- // free link queue is ordered by size
-
- freedChunk->Enqueue();
+ sFreeChunkTree.Insert(freedChunk);
+ sAvailable += freedChunk->Size();
+#ifdef DEBUG_MAX_HEAP_USAGE
+ sMaxHeapUsage = std::max(sMaxHeapUsage, sMaxHeapSize - sAvailable);
+#endif
}
Other related posts:
- » [haiku-commits] haiku: hrev46192 - in src/system/boot: loader platform/bios_ia32 - ingo_weinhold
