[Heap Trace Standalone] perf bug causes double traversal (IDFGH-11713)

[chipweinberger]

General issue report

relevant issue: #11173

[v5.1] [Heap Trace Standalone] hash map uses doubly linked list, but single linked would be better (IDFGH-9846)

In response to that issue^^, we added this code:

static HEAP_IRAM_ATTR heap_trace_record_t* map_find_and_remove(void *p)
{
    size_t idx = hash_idx(p);
    heap_trace_record_t *r_cur = NULL;
    SLIST_FOREACH(r_cur, &hash_map[idx], slist_hashmap) {
        if (r_cur->address == p) {
            total_hashmap_hits++;
            SLIST_REMOVE(&hash_map[idx], r_cur, heap_trace_record_t, slist_hashmap);
            return r_cur;
        }
    }
    total_hashmap_miss++;
    return NULL;
}

however, it uses SLIST_REMOVE which causes another traversal. We should have used SLIST_REMOVE_AFTER

something like this:

static HEAP_IRAM_ATTR heap_trace_record_t* map_find_and_remove(void *p)
{
    size_t idx = hash_idx(p);
    heap_trace_record_t *r_cur = NULL;
    heap_trace_record_t *r_prev = NULL;
    SLIST_FOREACH(r_cur, &hash_map[idx], slist_hashmap) {
        if (r_cur->address == p) {
            total_hashmap_hits++;
            if (r_prev) {
               SLIST_REMOVE_AFTER(r_prev, slist_hashmap);
            } else {
                SLIST_REMOVE_HEAD(r_cur, slist_hashmap);
            }
            return r_cur;
        }
        r_prev = r_cur;
    }
    total_hashmap_miss++;
    return NULL;
}

[chipweinberger]

@SoucheSouche

@igrr , not sure if Guillaume is still working.

[SoucheSouche]

@chipweinberger, I will have a look at it during the week.

[chipweinberger]

thanks!

[SoucheSouche]

@chipweinberger, I will update map_find_and_remove as suggested. I forgot that SLIST_REMOVE does go through the list to remove element unlike TAILQ_REMOVE used in the former implementation. Thanks for noticing :)