diff options
Diffstat (limited to 'rts/IPE.c')
| -rw-r--r-- | rts/IPE.c | 197 |
1 files changed, 157 insertions, 40 deletions
@@ -1,6 +1,6 @@ /* ----------------------------------------------------------------------------- * - * (c) The GHC Team, 1998-2000 + * (c) The GHC Team, 1998-2021 * * Support for mapping info table pointers to source locations * @@ -10,72 +10,189 @@ #include "rts/PosixSource.h" #include "Rts.h" -#include "RtsUtils.h" -#include "Profiling.h" #include "Arena.h" +#include "Capability.h" +#include "Hash.h" #include "IPE.h" #include "Printer.h" -#include "Capability.h" +#include "Profiling.h" +#include "RtsUtils.h" #include <fs_rts.h> #include <string.h> - #if defined(TRACING) #include "Trace.h" #endif -InfoProvEnt *IPE_LIST = NULL; +/* +Note [The Info Table Provenance Entry (IPE) Map] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +IPEs are stored in a hash map from info table address (pointer) to IPE. This +ensures cheap lookup and traversal. + +Unfortunately, inserting into the hash map is relatively expensive. To keep +startup times low, there's a temporary data structure that is optimized for +collecting IPE lists on registration. + +It's a singly linked list of IPE list buffers. Each buffer contains space for +126 IPE lists. This number is a bit arbitrary, but leaves a few bytes so that +the whole structure might fit into 1024 bytes. + +On registering a new IPE list, there are three cases: -void dumpIPEToEventLog(void) -{ +- It's the first entry at all: Allocate a new IpeBufferListNode and make it the + buffer's first entry. +- The current IpeBufferListNode has space in it's buffer: Add it to the buffer. +- The current IpeBufferListNode's buffer is full: Allocate a new one and link it +to the previous one, making this one the new current. + +Building the hash map is done lazily, i.e. on first lookup or traversal. For +this all IPE lists of all IpeBufferListNode are traversed to insert all IPEs. + +After the content of a IpeBufferListNode has been inserted, it's freed. +*/ + +static HashTable *ipeMap = NULL; + +static IpeBufferListNode *ipeBufferList = NULL; + +static Mutex ipeMapLock; + +void initIpeMapLock(void) { initMutex(&ipeMapLock); } + +void closeIpeMapLock(void) { closeMutex(&ipeMapLock); } + +void dumpIPEToEventLog(void) { #if defined(TRACING) - InfoProvEnt *ip, *next; - for (ip = IPE_LIST; ip != NULL; ip = next) { - next = ip->link; - traceIPE(ip->info, ip->prov.table_name, ip->prov.closure_desc, ip->prov.ty_desc - , ip->prov.label, ip->prov.module, ip->prov.srcloc); + ACQUIRE_LOCK(&ipeMapLock); + + IpeBufferListNode *cursor = ipeBufferList; + while (cursor != NULL) { + for (int i = 0; i < cursor->count; i++) { + for (InfoProvEnt **ipeList = cursor->buffer[i]; *ipeList != NULL; + ipeList++) { + InfoProvEnt *ipe = *ipeList; + + traceIPE(ipe->info, ipe->prov.table_name, + ipe->prov.closure_desc, ipe->prov.ty_desc, + ipe->prov.label, ipe->prov.module, ipe->prov.srcloc); + } + } + + cursor = cursor->next; + } + + if (ipeMap != NULL) { + mapHashTable(ipeMap, NULL, &traceIPEFromHashTable); } + + RELEASE_LOCK(&ipeMapLock); #endif return; } +#if defined(TRACING) +void traceIPEFromHashTable(void *data STG_UNUSED, StgWord key STG_UNUSED, + const void *value) { + InfoProvEnt *ipe = (InfoProvEnt *)value; -/* ----------------------------------------------------------------------------- - Registering IPEs + traceIPE(ipe->info, ipe->prov.table_name, ipe->prov.closure_desc, + ipe->prov.ty_desc, ipe->prov.label, ipe->prov.module, + ipe->prov.srcloc); +} +#endif - Registering a IPE consists of linking it onto the list of registered IPEs +/* Registering IPEs - IPEs are registered at startup by a C constructor function - generated by the compiler (ProfInit.hs) in the _stub.c file for each module. - -------------------------------------------------------------------------- */ +Adds the ent_list to the temporary buffer structure described in +Note [The Info Table Provenance Entry (IPE) Map]. -static void -registerInfoProvEnt(InfoProvEnt *ipe) -{ - ASSERT(ipe->link == NULL); - ipe->link = IPE_LIST; - IPE_LIST = ipe; -} +Statically initialized IPE lists are registered at startup by a C constructor +function generated by the compiler (CodeOutput.hs) in a *.c file for each +module. + +A performance test for IPE registration and lookup can be found here: +https://gitlab.haskell.org/ghc/ghc/-/merge_requests/5724#note_370806 +*/ +void registerInfoProvList(InfoProvEnt **ent_list) { + // The list must be dereferenceable. + ASSERT(ent_list[0] == NULL || ent_list[0] != NULL); -void registerInfoProvList(InfoProvEnt **ent_list) -{ - for (InfoProvEnt **i = ent_list; *i != NULL; i++) { - registerInfoProvEnt(*i); + // Ignore empty lists + if (ent_list[0] == NULL) { + return; + } + + ACQUIRE_LOCK(&ipeMapLock); + + if (ipeBufferList == NULL) { + ASSERT(ipeBufferList == NULL); + + ipeBufferList = stgMallocBytes(sizeof(IpeBufferListNode), + "registerInfoProvList-firstNode"); + ipeBufferList->buffer[0] = ent_list; + ipeBufferList->count = 1; + ipeBufferList->next = NULL; + } else { + if (ipeBufferList->count < IPE_LIST_NODE_BUFFER_SIZE) { + ipeBufferList->buffer[ipeBufferList->count] = ent_list; + ipeBufferList->count = ipeBufferList->count + 1; + + ASSERT(ipeBufferList->next == NULL || + ipeBufferList->next->count == IPE_LIST_NODE_BUFFER_SIZE); + } else { + IpeBufferListNode *newNode = stgMallocBytes( + sizeof(IpeBufferListNode), "registerInfoProvList-nextNode"); + newNode->buffer[0] = ent_list; + newNode->count = 1; + newNode->next = ipeBufferList; + ipeBufferList = newNode; + + ASSERT(ipeBufferList->next->count == IPE_LIST_NODE_BUFFER_SIZE); + } } + + RELEASE_LOCK(&ipeMapLock); +} + +InfoProvEnt *lookupIPE(StgInfoTable *info) { + updateIpeMap(); + return lookupHashTable(ipeMap, (StgWord)info); } +void updateIpeMap() { + // Check if there's any work at all. If not so, we can circumvent locking, + // which decreases performance. + if (ipeMap != NULL && ipeBufferList == NULL) { + return; + } + + ACQUIRE_LOCK(&ipeMapLock); -// MP: TODO: This should not be a linear search, need to improve -// the IPE_LIST structure -InfoProvEnt * lookupIPE(StgInfoTable *info) -{ - InfoProvEnt *ip, *next; - for (ip = IPE_LIST; ip != NULL; ip = next) { - if (ip->info == info) { - return ip; + if (ipeMap == NULL) { + ipeMap = allocHashTable(); + } + + while (ipeBufferList != NULL) { + ASSERT(ipeBufferList->next == NULL || + ipeBufferList->next->count == IPE_LIST_NODE_BUFFER_SIZE); + ASSERT(ipeBufferList->count > 0 && + ipeBufferList->count <= IPE_LIST_NODE_BUFFER_SIZE); + + IpeBufferListNode *currentNode = ipeBufferList; + + for (int i = 0; i < currentNode->count; i++) { + for (InfoProvEnt **ipeList = currentNode->buffer[i]; + *ipeList != NULL; ipeList++) { + insertHashTable(ipeMap, (StgWord)(*ipeList)->info, *ipeList); + } } - next = ip->link; + + ipeBufferList = currentNode->next; + stgFree(currentNode); } - return NULL; + + RELEASE_LOCK(&ipeMapLock); } |