On Tue, May 25, 2021 at 8:22 PM Tim Newsome <t...@sifive.com> wrote:
> On Mon, May 24, 2021 at 4:31 PM Andreas Fritiofson <
> andreas.fritiof...@gmail.com> wrote:
>
>>
>>
>> On Wed, Feb 17, 2021 at 9:21 PM Tim Newsome <t...@sifive.com> wrote:
>>
>>> On Tue, Feb 16, 2021 at 4:17 PM Steven Stallion via OpenOCD-devel <
>>> openocd-devel@lists.sourceforge.net> wrote:
>>>
>>>> Out of curiosity, why even bother with a more advanced structure when a
>>>> list will suffice? I agree it feels gross to iterate to find a given
>>>> thread, however we're looking at a relatively low number of iterations. Is
>>>> it really worth introducing an additional dependency to avoid a loop?
>>>>
>>>
>>> A list is fine. But I don't want to have to implement that list. linux.c
>>> implements its own list. list.h implements a slightly different list, but
>>> doesn't implement look-up by a key.
>>>
>>
>> struct thread *lookup(int id)
>> {
>> struct thread *t;
>> list_for_each_entry(t, &threads, lh) {
>> if (t->id == id)
>> return t;
>> }
>> return NULL;
>> }
>>
>>
>>> I could build something on top of that list, or write my own from
>>> scratch. That's just a big waste of effort though, given that there already
>>> are fast, well-tested implementations out there.
>>>
>>
>> I myself have spent far more time reading this email thread, checking out
>> gnulib licensing and so on, than what it took to write that lookup
>> function. Just saying... I'm not buying that "waste of effort" argument at
>> all.
>>
>
> Part of my motivation was to get better than O(n) lookup times, but for
> this particular application it doesn't matter much (until somebody has a
> use case where it does, of course). Can you add some basic documentation to
> list.h explaining overall how it's intended to be used? It just took me way
> too long to figure out that you have to put a `struct list_head` to the
> front of the structure you want to put in the list. Just a short bit of
> code that makes a list, adds some entries, iterates, removes some entries,
> and then frees the whole thing would be a great resource. I know that
> exists in the code, but it's usually dispersed among different functions.
>
Here's the full example I wrote yesterday. I've added a lookup by tcb as
well. I noticed that your freertos.c needs to lookup by both and so you
need two independent hash maps which must be in sync with tasks added and
removed from both. I'd say that is actually a really big downside of using
a hash map so I'd avoid that even if we had the map library in OpenOCD
already. The dual lookup in the single list.h list is as you can see
trivial.
To move from a static "threads" list head to one in struct freertos, you
need to do INIT_LIST_HEAD() on it when initializing struct freertos.
As Antonio said, list.h is already as documented as you could wish for, if
you look at the newer copy in the kernel. Also, being from linux, there are
plenty of people who have explained and described how it works already.
#include <list.h>
#include <assert.h>
static LIST_HEAD(threads);
struct thread {
int id;
uint64_t tcb_address;
struct list_head lh;
};
void insert(struct thread *t)
{
list_add_tail(&t->lh, &threads);
}
void remove(struct thread *t)
{
list_del(&t->lh);
}
struct thread *lookup_id(int id)
{
struct thread *t;
list_for_each_entry(t, &threads, lh) {
if (t->id == id)
return t;
}
return NULL;
}
struct thread *lookup_tcb(uint64_t addr)
{
struct thread *t;
list_for_each_entry(t, &threads, lh) {
if (t->tcb_address == addr)
return t;
}
return NULL;
}
int main(void)
{
struct thread t1 = { .id = 1, .tcb_address = 111111111 };
struct thread t2 = { .id = 2, .tcb_address = 222222222 };
struct thread t3 = { .id = 3, .tcb_address = 333333333 };
insert(&t1);
insert(&t2);
assert(lookup_id(1) == &t1);
assert(lookup_tcb(111111111) == &t1);
assert(lookup_id(2) == &t2);
assert(lookup_id(42) == NULL);
remove(&t1);
assert(lookup_id(1) == NULL);
insert(&t3);
remove(&t2);
assert(lookup_id(3) == &t3);
assert(lookup_tcb(333333333) == &t3);
assert(lookup_id(2) == NULL);
remove(&t3);
assert(list_empty(&threads));
}
> I'm inclined to just use the list and ignore performance, because I'm as
> tired of this thread as you probably are. Nobody besides me seems to be
> excited to have a hash map easily usable from OpenOCD.
>
Being better than O(n) means nothing when n is in the tens and performance
is limited by I/O, as it usually is in OpenOCD. Having a hash map in
OpenOCD should not be a goal in itself. In this case a hash map isn't even
a particularly good fit.
/Andreas
