This is an automated email from the ASF dual-hosted git repository. xiaoxiang781216 pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/nuttx.git
commit b22d69c25b910babd69e6aeb268b03446f65a035 Author: yinshengkai <[email protected]> AuthorDate: Thu Jan 2 22:18:34 2025 +0800 libc: support dynamic expansion of backtrace records The backtrace records lived in a static pool sized by CONFIG_LIBC_BACKTRACE_BUFFSIZE: the memory was reserved even when few records were in use, and backtrace_record() failed once the pool was full. Allocate the records from the heap instead: the pool is created on the first record and doubled, together with the hash table, when the share of used records reaches CONFIG_LIBC_BACKTRACE_LOAD_FACTOR. In the kernel the pool only grows when the heap is ready and the caller is not in an interrupt or the idle loop; until then a record is not taken. CONFIG_LIBC_BACKTRACE_DEPTH (the depth of a record) now enables the feature, CONFIG_LIBC_BACKTRACE_INIT_SIZE sets the initial size, and CONFIG_LIBC_BACKTRACE_BUFFSIZE is removed. backtrace_record() returns the record (or NULL) instead of an index, and backtrace_remove() and backtrace_get() take the record. Signed-off-by: yinshengkai <[email protected]> --- include/execinfo.h | 24 +-- libs/libc/misc/Kconfig | 24 ++- libs/libc/misc/lib_backtrace.c | 385 +++++++++++++++++++++++------------------ 3 files changed, 251 insertions(+), 182 deletions(-) diff --git a/include/execinfo.h b/include/execinfo.h index 7571f507dfa..4f4238f23bf 100644 --- a/include/execinfo.h +++ b/include/execinfo.h @@ -48,6 +48,10 @@ #define backtrace(b, s) sched_backtrace(_SCHED_GETTID(), b, s, 0) #define dump_stack() sched_dumpstack(_SCHED_GETTID()) +#ifndef CONFIG_LIBC_BACKTRACE_DEPTH +# define CONFIG_LIBC_BACKTRACE_DEPTH 0 +#endif + /**************************************************************************** * Public Function Prototypes ****************************************************************************/ @@ -62,17 +66,17 @@ void backtrace_symbols_fd(FAR void *const *buffer, int size, int fd); int backtrace_format(FAR char *buffer, int size, FAR void *backtrace[], int depth); -# if CONFIG_LIBC_BACKTRACE_BUFFSIZE > 0 -int backtrace_record(int skip); -int backtrace_remove(int index); -FAR void **backtrace_get(int index, FAR int *size); +#if CONFIG_LIBC_BACKTRACE_DEPTH > 0 +FAR void *backtrace_record(int skip); +void backtrace_remove(FAR void *entry); +FAR void **backtrace_get(FAR void *entry, FAR int *size); void backtrace_dump(void); -# else -# define backtrace_record(skip) (-ENOSYS) -# define backtrace_remove(index) (-ENOSYS) -# define backtrace_get(index, size) (*(size)=0) -# define backtrace_dump() -# endif +#else +# define backtrace_record(skip) (NULL) +# define backtrace_remove(entry) +# define backtrace_get(entry, size) (*(size)=0) +# define backtrace_dump() +#endif #if defined(__cplusplus) } diff --git a/libs/libc/misc/Kconfig b/libs/libc/misc/Kconfig index 62ddbb21b37..4f5db06f8fc 100644 --- a/libs/libc/misc/Kconfig +++ b/libs/libc/misc/Kconfig @@ -165,19 +165,27 @@ config LIBC_TEMPBUFFER_MALLOC endif # LIBC_TEMPBUFFER -config LIBC_BACKTRACE_BUFFSIZE - int "The size of backtrace record buffer" +config LIBC_BACKTRACE_DEPTH + int "The maximum depth of the backtrace record." depends on SCHED_BACKTRACE default 0 ---help--- - The size of the backtrace buffer. + The maximum depth of the backtrace record. -config LIBC_BACKTRACE_DEPTH - int "The depth of backtrace" - depends on LIBC_BACKTRACE_BUFFSIZE > 0 - default 8 +config LIBC_BACKTRACE_INIT_SIZE + int "The initial size of backtrace record" + depends on LIBC_BACKTRACE_DEPTH > 0 + default 64 + ---help--- + The initial size of the backtrace record. + +config LIBC_BACKTRACE_LOAD_FACTOR + int "The load factor of backtrace record" + depends on LIBC_BACKTRACE_DEPTH > 0 + range 0 100 + default 75 ---help--- - The depth of the backtrace buffer. + The load factor of the backtrace record. config LIBC_MUTEX_BACKTRACE int "The depth of mutex backtrace" diff --git a/libs/libc/misc/lib_backtrace.c b/libs/libc/misc/lib_backtrace.c index 327f19399cd..1dcc444701b 100644 --- a/libs/libc/misc/lib_backtrace.c +++ b/libs/libc/misc/lib_backtrace.c @@ -24,12 +24,14 @@ * Included Files ****************************************************************************/ +#include <arch/irq.h> #include <execinfo.h> #include <stdio.h> #include <stdbool.h> #include <syslog.h> -#include <sys/param.h> +#include <nuttx/init.h> +#include <nuttx/sched.h> #include <nuttx/spinlock.h> #include "libc.h" @@ -38,25 +40,19 @@ * Pre-processor Definitions ****************************************************************************/ -#ifndef CONFIG_LIBC_BACKTRACE_BUFFSIZE -# define CONFIG_LIBC_BACKTRACE_BUFFSIZE 0 +#if defined(CONFIG_BUILD_FLAT) || defined(__KERNEL__) +# define backtrace_lock(bp) spin_lock_irqsave(&(bp)->lock) +# define backtrace_unlock(bp, flags) spin_unlock_irqrestore(&(bp)->lock, flags) +#else +# define backtrace_lock(bp) ((irqstate_t)nxmutex_lock(&(bp)->lock)) +# define backtrace_unlock(bp, flags) (flags, nxmutex_unlock(&(bp)->lock)) #endif -/* Calculate the number of backtrace that can be saved based on - * LIBC_BACKTRACE_BUFFSIZE. Each backtrace entry corresponds to a hash - * table entry. The maximum number of entries that can be recorded is - * BACKTRACE_BUFFSIZE / (backtrace entry size + hash entry size). - */ - -#define BACKTRACE_NUMBER (CONFIG_LIBC_BACKTRACE_BUFFSIZE / \ - (sizeof(struct backtrace_entry_s) + \ - sizeof(int))) - /**************************************************************************** * Private Types ****************************************************************************/ -#if CONFIG_LIBC_BACKTRACE_BUFFSIZE > 0 +#if CONFIG_LIBC_BACKTRACE_DEPTH > 0 struct backtrace_entry_s { union @@ -65,23 +61,23 @@ struct backtrace_entry_s struct sq_entry_s freenode; }; - uint16_t depth; /* Depth of the backtrace */ - uint16_t count; /* Count of the backtrace */ - int next; /* Next index in the hash chain */ + FAR void *next; /* Next index in the hash chain */ + uint16_t depth; /* Depth of the backtrace */ + uint16_t ref; /* Count of the backtrace */ }; struct backtrace_pool_s { - /* Pool to store the backtrace record */ - - struct backtrace_entry_s pool[BACKTRACE_NUMBER]; - - /* Hash table to store the index of the backtrace record */ - - int bucket[BACKTRACE_NUMBER]; + FAR struct backtrace_entry_s **bucket; struct sq_queue_s freelist; +#if defined(CONFIG_BUILD_FLAT) || defined(__KERNEL__) spinlock_t lock; - bool init; +#else + mutex_t lock; +#endif + size_t capacity; + size_t used; + bool expanding; }; /**************************************************************************** @@ -119,114 +115,188 @@ static FAR char **backtrace_malloc(FAR void *const *buffer, int size) return lib_malloc(length); } -#if CONFIG_LIBC_BACKTRACE_BUFFSIZE > 0 +#if CONFIG_LIBC_BACKTRACE_DEPTH > 0 /**************************************************************************** - * Name: backtrace_init - * - * Description: - * Initialize the backtrace record - * + * Name: backtrace_hash ****************************************************************************/ -static void backtrace_init(void) +static uint32_t backtrace_hash(FAR const void *backtrace, int depth) { - FAR struct backtrace_pool_s *bp = &g_backtrace_pool; - size_t i; + FAR const uintptr_t *data = backtrace; + uint32_t hash = 5381; + int i; - sq_init(&bp->freelist); - spin_lock_init(&bp->lock); - memset(bp->bucket, -1, sizeof(bp->bucket)); - for (i = 0; i < nitems(bp->pool); i++) + for (i = 0; i < depth; i++) { - sq_addlast(&bp->pool[i].freenode, &bp->freelist); + hash = ((hash << 5) + hash) + data[i]; } + + return hash; } /**************************************************************************** - * Name: backtrace_hash + * Name: backtrace_rehash ****************************************************************************/ -static int backtrace_hash(FAR struct backtrace_pool_s *bp, - FAR const void *backtrace, int depth) +static void backtrace_rehash(FAR struct backtrace_pool_s *bp, + FAR struct backtrace_entry_s **bucket) { - FAR const uint8_t *data = backtrace; - uint32_t hash = 5381; - int i; + FAR struct backtrace_entry_s *entry; + size_t capacity = bp->capacity; + size_t i; + + /* Rehash the backtrace record, and move the backtrace record to the new + * bucket + */ - for (i = 0; i < depth * sizeof(uintptr_t); i++) + for (i = 0; i < capacity; i++) { - hash = ((hash << 5) + hash) + data[i]; + entry = bp->bucket[i]; + while (entry) + { + uint32_t slot = backtrace_hash(entry->stack, entry->depth); + FAR struct backtrace_entry_s *next = entry->next; + slot = slot % (capacity * 2); + entry->next = bucket[slot]; + bucket[slot] = entry; + entry = next; + } } - - return hash % nitems(bp->bucket); } /**************************************************************************** - * Name: backtrace_exist + * Name: backtrace_expand ****************************************************************************/ -static int backtrace_exist(FAR struct backtrace_pool_s *bp, int slot, - FAR void *backtrace, int depth) +static int backtrace_expand(FAR struct backtrace_pool_s *bp) { - FAR struct backtrace_entry_s *entry; - int index; + FAR struct backtrace_entry_s **oldbucket; + FAR struct backtrace_entry_s **bucket; + FAR struct backtrace_entry_s *pool; + size_t capacity = bp->capacity; + size_t poolsize; + irqstate_t flags; + size_t i; + + /* If the capacity is 0, it means that the backtrace record is not + * initialized, we will initialize it with the default size + */ - if (bp->init == false) + if (capacity == 0) { - bp->init = true; - backtrace_init(); - return -ENOENT; + poolsize = CONFIG_LIBC_BACKTRACE_INIT_SIZE; + capacity = CONFIG_LIBC_BACKTRACE_INIT_SIZE; } + else + { + /* When expanding, double the capacity of the bunket and release + * the old bunket. + */ - index = bp->bucket[slot]; + poolsize = capacity; + capacity = capacity * 2; + } + + bucket = lib_zalloc(sizeof(FAR struct backtrace_entry_s *) * capacity); + pool = lib_zalloc(sizeof(struct backtrace_entry_s) * poolsize); + if (bucket == NULL || pool == NULL) + { + lib_free(bucket); + lib_free(pool); + return -ENOMEM; + } + + /* Rehash the backtrace record, and move the backtrace record to the new + * bucket + */ + + flags = backtrace_lock(bp); + if (bp->capacity) + { + backtrace_rehash(bp, bucket); + } + else + { + sq_init(&bp->freelist); + } + + /* Expand the backtrace entry pool, and add the new backtrace entry + * to the free list + */ - while (index >= 0) + for (i = 0; i < poolsize; i++) + { + sq_addlast(&pool[i].freenode, &bp->freelist); + } + + oldbucket = bp->bucket; + bp->bucket = bucket; + bp->capacity = capacity; + backtrace_unlock(bp, flags); + lib_free(oldbucket); + return 0; +} + +/**************************************************************************** + * Name: backtrace_exist + ****************************************************************************/ + +static FAR struct backtrace_entry_s * +backtrace_find(FAR struct backtrace_pool_s *bp, uint32_t slot, + FAR const void *stack, int depth) +{ + FAR struct backtrace_entry_s *entry = bp->bucket[slot]; + + while (entry != NULL) { - entry = &bp->pool[index]; if (entry->depth == depth && - memcmp(backtrace, entry->stack, depth * sizeof(FAR void *)) == 0) + memcmp(stack, entry->stack, depth * sizeof(FAR void *)) == 0) { - return index; + /* If the backtrace record already exists, just increase the + * reference count + */ + + entry->ref++; + return entry; } - index = entry->next; + entry = entry->next; } - return -ENOENT; + return NULL; } /**************************************************************************** * Name: backtrace_alloc ****************************************************************************/ -static int backtrace_alloc(FAR struct backtrace_pool_s *bp) +static FAR struct backtrace_entry_s * +backtrace_alloc(FAR struct backtrace_pool_s *bp, uint32_t slot, + const FAR void *stack, int depth) { FAR struct backtrace_entry_s *entry; - FAR struct sq_entry_s *sq; /* Get the first entry from the free list */ - sq = sq_remfirst(&bp->freelist); - if (!sq) + entry = (FAR struct backtrace_entry_s *)sq_remfirst(&bp->freelist); + if (entry == NULL) { - return -ENOMEM; + return NULL; } - entry = (FAR struct backtrace_entry_s *)sq; - return entry - bp->pool; -} + /* Copy the backtrace to the entry */ -/**************************************************************************** - * Name: backtrace_free - ****************************************************************************/ + bp->used++; + memcpy(entry->stack, stack, depth * sizeof(FAR void *)); + entry->depth = depth; + entry->ref = 1; -static void backtrace_free(FAR struct backtrace_pool_s *bp, int index) -{ - FAR struct backtrace_entry_s *entry = &bp->pool[index]; + /* Insert backtrace entry to the head of the linked list */ - sq_addlast(&entry->freenode, &bp->freelist); - entry->depth = 0; + entry->next = bp->bucket[slot]; + bp->bucket[slot] = entry; + return entry; } /**************************************************************************** @@ -244,56 +314,58 @@ static void backtrace_free(FAR struct backtrace_pool_s *bp, int index) * a negative value. ****************************************************************************/ -int backtrace_record(int skip) +FAR void *backtrace_record(int skip) { FAR void *buffer[CONFIG_LIBC_BACKTRACE_DEPTH]; FAR struct backtrace_pool_s *bp = &g_backtrace_pool; - FAR struct backtrace_entry_s *entry; + FAR struct backtrace_entry_s *entry = NULL; irqstate_t flags; + uint32_t slot; int depth; - int index; - int slot; depth = sched_backtrace(_SCHED_GETTID(), buffer, CONFIG_LIBC_BACKTRACE_DEPTH, skip); if (depth <= 0) { - return -ENOENT; + return NULL; } - slot = backtrace_hash(bp, buffer, depth); - flags = spin_lock_irqsave(&bp->lock); - index = backtrace_exist(bp, slot, buffer, depth); - if (index >= 0) - { - /* If the backtrace record already exists, just increase the count */ + slot = backtrace_hash(buffer, depth); + flags = backtrace_lock(bp); - entry = &bp->pool[index]; - entry->count++; - spin_unlock_irqrestore(&bp->lock, flags); - return index; - } + /* If the used amount reaches the threshold, we will expand it */ - index = backtrace_alloc(bp); - if (index < 0) + if (bp->used >= bp->capacity * CONFIG_LIBC_BACKTRACE_LOAD_FACTOR / 100 && + !bp->expanding +#if defined(CONFIG_BUILD_FLAT) || defined(__KERNEL__) + && OSINIT_MM_READY() && !up_interrupt_context() && + (!is_idle_task(nxsched_self()) || !OSINIT_IDLELOOP()) +#endif + ) { - spin_unlock_irqrestore(&bp->lock, flags); - return index; + bp->expanding = true; + backtrace_unlock(bp, flags); + backtrace_expand(bp); + flags = backtrace_lock(bp); + bp->expanding = false; } - entry = &bp->pool[index]; - memcpy(entry->stack, buffer, depth * sizeof(FAR void *)); - entry->depth = depth; - entry->count = 1; + /* Backtrace can only be recorded after initialization */ - /* Insert backtrace to the head of the linked list of the - * current hash value - */ + if (bp->capacity) + { + slot = slot % bp->capacity; + entry = backtrace_find(bp, slot, buffer, depth); + if (entry == NULL) + { + /* If the backtrace record does not exist, allocate a new one */ - entry->next = bp->bucket[slot]; - bp->bucket[slot] = index; - spin_unlock_irqrestore(&bp->lock, flags); - return index; + entry = backtrace_alloc(bp, slot, buffer, depth); + } + } + + backtrace_unlock(bp, flags); + return entry; } /**************************************************************************** @@ -309,71 +381,52 @@ int backtrace_record(int skip) * Return 0 if success, otherwise return a negative value. ****************************************************************************/ -int backtrace_remove(int index) +void backtrace_remove(FAR void *index) { FAR struct backtrace_pool_s *bp = &g_backtrace_pool; - FAR struct backtrace_entry_s *entry; + FAR struct backtrace_entry_s *entry = index; irqstate_t flags; - int slot; + uint32_t slot; - if (index < 0 || index >= nitems(bp->pool)) + if (entry == NULL) { - return -EINVAL; + return; } - flags = spin_lock_irqsave(&bp->lock); - entry = &bp->pool[index]; - if (entry->count > 1) + flags = backtrace_lock(bp); + if (entry->ref > 1) { - entry->count--; - spin_unlock_irqrestore(&bp->lock, flags); - return OK; + entry->ref--; + backtrace_unlock(bp, flags); + return; } - slot = backtrace_hash(bp, entry->stack, entry->depth); - - /* Remove the backtrace record from the linked list */ - - if (bp->bucket[slot] == index) + slot = backtrace_hash(entry->stack, entry->depth); + slot = slot % bp->capacity; + if (bp->bucket[slot] == entry) { - /* Remove the head of the singly linked list */ - bp->bucket[slot] = entry->next; } - else if (entry->next >= 0) - { - /* Copy and delete the next node of the singly linked list - * to achieve O(1) deletion - */ - - FAR struct backtrace_entry_s *next = &bp->pool[entry->next]; - - index = entry->next; - memcpy(entry, next, sizeof(struct backtrace_entry_s)); - } else { - /* If it is the last node in the linked list, we need to traverse - * and find the previous node to delete it. - */ + /* Remove the backtrace record from the linked list */ - int prev = bp->bucket[slot]; - - while (prev >= 0) + FAR struct backtrace_entry_s *prev = bp->bucket[slot]; + while (prev) { - if (bp->pool[prev].next == index) + if (prev->next == entry) { - bp->pool[prev].next = -1; + prev->next = entry->next; break; } - prev = bp->pool[prev].next; + prev = prev->next; } } - backtrace_free(bp, index); - spin_unlock_irqrestore(&bp->lock, flags); - return OK; + bp->used--; + sq_addlast(&entry->freenode, &bp->freelist); + backtrace_unlock(bp, flags); } /**************************************************************************** @@ -390,17 +443,15 @@ int backtrace_remove(int index) * Return the backtrace record if success, otherwise return NULL ****************************************************************************/ -FAR void **backtrace_get(int index, FAR int *size) +FAR void **backtrace_get(FAR void *index, FAR int *size) { - FAR struct backtrace_pool_s *bp = &g_backtrace_pool; - FAR struct backtrace_entry_s *entry; + FAR struct backtrace_entry_s *entry = index; - if (size == NULL || index < 0 || index >= nitems(bp->pool)) + if (size == NULL || entry == NULL) { return NULL; } - entry = &bp->pool[index]; *size = entry->depth; return entry->stack; } @@ -410,18 +461,24 @@ void backtrace_dump(void) char buf[BACKTRACE_BUFFER_SIZE(CONFIG_LIBC_BACKTRACE_DEPTH)]; FAR struct backtrace_pool_s *bp = &g_backtrace_pool; FAR struct backtrace_entry_s *entry; - size_t i; + size_t conflict = 0; + uint32_t slot; - syslog(LOG_INFO, "%-6s %-6s %s", "index", "count", "backtrace"); - for (i = 0; i < nitems(bp->pool); i++) + syslog(LOG_INFO, "%-8s %-8s %s", "slot", "refcount", "backtrace"); + for (slot = 0; slot < bp->capacity; slot++) { - entry = &bp->pool[i]; - if (entry->depth) + entry = bp->bucket[slot]; + while (entry) { backtrace_format(buf, sizeof(buf), entry->stack, entry->depth); - syslog(LOG_INFO, "%-6zu %-6u %s\n", i, entry->count, buf); + syslog(LOG_INFO, "%-8zu %-8u %s\n", slot, entry->ref, buf); + conflict += entry->next != NULL; + entry = entry->next; } } + + syslog(LOG_INFO, "capacity: %u, used: %u, conflict: %zu\n", + bp->capacity, bp->used, conflict); } #endif
