Re: [PATCH 4/5] cyclic: switch to using hlist instead of list

On 28.10.22 13:50, Rasmus Villemoes wrote:

A hlist is headed by just a single pointer, so can only be traversed forwards, and insertions can only happen at the head (or before/after an existing list member). But each list node still consists of two pointers, so arbitrary elements can still be removed in O(1).

This is precisely what we need for the cyclic_list - we never need to traverse it backwards, and the order the callbacks appear in the list should really not matter.

One advantage, and the main reason for doing this switch, is that an empty list is represented by a NULL head pointer, so unlike a list_head, it does not need separate C code to initialize - a memset(,0,) of the containing structure is sufficient.

This is mostly mechanical:

• The iterators are updated with an h prefix, and the type of the temporary variable changed to struct hlist_node*.

• Adding/removing is now just hlist_add_head (and not tail) and hlist_del().

• struct members and function return values updated.

Signed-off-by: Rasmus Villemoes rasmus.villemoes@prevas.dk

cmd/cyclic.c | 5 +++-- common/cyclic.c | 18 ++++++++++-------- include/cyclic.h | 6 +++--- 3 files changed, 16 insertions(+), 13 deletions(-)

diff --git a/cmd/cyclic.c b/cmd/cyclic.c index c1bc556aad..97324d8240 100644 --- a/cmd/cyclic.c +++ b/cmd/cyclic.c @@ -61,10 +61,11 @@ static int do_cyclic_demo(struct cmd_tbl *cmdtp, int flag, int argc, static int do_cyclic_list(struct cmd_tbl *cmdtp, int flag, int argc, char *const argv[]) {

• struct cyclic_info *cyclic, *tmp;

• struct cyclic_info *cyclic;
• struct hlist_node *tmp; u64 cnt, freq;

• list_for_each_entry_safe(cyclic, tmp, cyclic_get_list(), list) {

• hlist_for_each_entry_safe(cyclic, tmp, cyclic_get_list(), list) { cnt = cyclic->run_cnt * 1000000ULL * 100ULL; freq = lldiv(cnt, timer_get_us() - cyclic->start_time_us); printf("function: %s, cpu-time: %lld us, frequency: %lld.%02d times/s\n",

diff --git a/common/cyclic.c b/common/cyclic.c index d6f11b002e..32d9bf0d02 100644 --- a/common/cyclic.c +++ b/common/cyclic.c @@ -20,7 +20,7 @@ DECLARE_GLOBAL_DATA_PTR;

void hw_watchdog_reset(void);

-struct list_head *cyclic_get_list(void) +struct hlist_head *cyclic_get_list(void) { return &gd->cyclic->cyclic_list; } @@ -47,14 +47,14 @@ struct cyclic_info *cyclic_register(cyclic_func_t func, uint64_t delay_us, cyclic->name = strdup(name); cyclic->delay_us = delay_us; cyclic->start_time_us = timer_get_us();

• list_add_tail(&cyclic->list, &gd->cyclic->cyclic_list);

• hlist_add_head(&cyclic->list, &gd->cyclic->cyclic_list);

  return cyclic; }

  int cyclic_unregister(struct cyclic_info *cyclic) {

• list_del(&cyclic->list);

• hlist_del(&cyclic->list); free(cyclic);

  return 0;

@@ -62,7 +62,8 @@ int cyclic_unregister(struct cyclic_info *cyclic)

void cyclic_run(void) {

• struct cyclic_info *cyclic, *tmp;

• struct cyclic_info *cyclic;

• struct hlist_node *tmp; uint64_t now, cpu_time;

  /* Prevent recursion */

@@ -70,7 +71,7 @@ void cyclic_run(void) return;

gd->flags |= GD_FLG_CYCLIC_RUNNING;

• list_for_each_entry_safe(cyclic, tmp, &gd->cyclic->cyclic_list, list) {

• hlist_for_each_entry_safe(cyclic, tmp, &gd->cyclic->cyclic_list, list) { /*
  • Check if this cyclic function needs to get called, e.g.
  • do not call the cyclic func too often

@@ -118,9 +119,10 @@ void schedule(void)

int cyclic_uninit(void) {

• struct cyclic_info *cyclic, *tmp;

• struct cyclic_info *cyclic;
• struct hlist_node *tmp;

• list_for_each_entry_safe(cyclic, tmp, &gd->cyclic->cyclic_list, list)

• hlist_for_each_entry_safe(cyclic, tmp, &gd->cyclic->cyclic_list, list) cyclic_unregister(cyclic);

  return 0;

@@ -135,7 +137,7 @@ int cyclic_init(void) return -ENOMEM;

memset(gd->cyclic, '\0', size);

• INIT_LIST_HEAD(&gd->cyclic->cyclic_list);

• INIT_HLIST_HEAD(&gd->cyclic->cyclic_list);

  return 0; }

diff --git a/include/cyclic.h b/include/cyclic.h index 263b74d89b..4a11f9b105 100644 --- a/include/cyclic.h +++ b/include/cyclic.h @@ -20,7 +20,7 @@

• @cyclic_list: Cylic list node

*/ struct cyclic_drv {

• struct list_head cyclic_list;

• struct hlist_head cyclic_list; };

  /**

@@ -46,7 +46,7 @@ struct cyclic_info { uint64_t cpu_time_us; uint64_t run_cnt; uint64_t next_call;

• struct list_head list;

• struct hlist_node list; bool already_warned; };

@@ -95,7 +95,7 @@ int cyclic_uninit(void);

• @return: pointer to cyclic_list

*/ -struct list_head *cyclic_get_list(void); +struct hlist_head *cyclic_get_list(void);

/**

• cyclic_run() - Interate over all registered cyclic functions

Reviewed-by: Stefan Roese sr@denx.de Tested-by: Stefan Roese sr@denx.de

Thanks, Stefan