From: Scott Worley Date: Tue, 10 Oct 2023 07:50:42 +0000 (-0700) Subject: client: Hold presses in queues, one queue per send_count X-Git-Tag: v0.1.0~30 X-Git-Url: http://git.scottworley.com/tattlekey/commitdiff_plain/0527f2292fd8cb1585d63cee916f918cc0a65098?ds=inline client: Hold presses in queues, one queue per send_count This lets us efficiently hold many more presses with pending resends and eliminates the failure mode in which young presses could be dropped because the sleeps_heap was full of old presses. Instead of storing each press in the sleeps_heap, we now only store up to config_resend_count entries in the sleeps_heap. Old presses now only compete with similarly-old presses for retention space. --- diff --git a/client/press.c b/client/press.c index 1c8ce9f..cec1709 100644 --- a/client/press.c +++ b/client/press.c @@ -1,14 +1,20 @@ #include "press.h" #include "blink.h" +#include "config.h" -static uint32_t next_send(press_t *s) { +static uint32_t press_next_send(press_t *s) { return s->timestamp + (1 << s->send_count) - 1; } +static uint32_t press_queue_next_send(queue_t *q) { + press_t press; + return queue_try_peek(q, &press) ? press_next_send(&press) : UINT32_MAX; +} + static bool next_send_less_than(void *user_data, pheap_node_id_t a, pheap_node_id_t b) { - press_t *presses = (press_t *)user_data; - return next_send(&presses[a]) < next_send(&presses[b]); + queue_t **sleeps = (queue_t **)user_data; + return press_queue_next_send(sleeps[a]) < press_queue_next_send(sleeps[b]); } static void *xcalloc(size_t nmemb, size_t size) { @@ -20,38 +26,55 @@ static void *xcalloc(size_t nmemb, size_t size) { press_pile_t *create_press_pile() { press_pile_t *pp = (press_pile_t *)xcalloc(1, sizeof(press_pile_t)); - pp->presses = (press_t *)xcalloc(PICO_PHEAP_MAX_ENTRIES, sizeof(press_t)); + pp->presses = (queue_t *)xcalloc(config_resend_count, sizeof(queue_t)); + pp->sleeps = (queue_t **)xcalloc(config_resend_count, sizeof(queue_t *)); + for (int i = 0; i < config_resend_count; i++) { + uint element_count = 1 << i; + element_count = MAX(element_count, 32); + element_count = MIN(element_count, 512); + queue_init(&pp->presses[i], sizeof(press_t), element_count); + } pp->sleeps_heap = - ph_create(PICO_PHEAP_MAX_ENTRIES, next_send_less_than, pp->presses); + ph_create(config_resend_count, next_send_less_than, pp->sleeps); if (pp->sleeps_heap == NULL) signal_error_by_blinking(); return pp; } void add_press(press_pile_t *pp, press_t *press) { - pheap_node_id_t i = ph_new_node(pp->sleeps_heap); - if (i == 0) { - /* TODO: Don't drop new presses just because sleeps_heap is full of old - * presses. */ - return; + int sc = press->send_count; + if (sc >= config_resend_count) + signal_error_by_blinking(); + bool was_empty = queue_is_empty(&pp->presses[sc]); + /* No error check; blithely continue if the queue was full. */ + queue_try_add(&pp->presses[sc], press); + if (was_empty) { + pheap_node_id_t i = ph_new_node(pp->sleeps_heap); + pp->sleeps[i] = &pp->presses[sc]; + ph_insert_node(pp->sleeps_heap, i); } - pp->presses[i] = *press; - ph_insert_node(pp->sleeps_heap, i); } int32_t next_scheduled_send(press_pile_t *pp) { pheap_node_id_t i = ph_peek_head(pp->sleeps_heap); if (i == 0) return -1; - return next_send(&pp->presses[i]); + return press_queue_next_send(pp->sleeps[i]); } bool get_press_due_for_resend(press_pile_t *pp, uint32_t now, press_t *press) { pheap_node_id_t i = ph_peek_head(pp->sleeps_heap); - if (i == 0 || next_send(&pp->presses[i]) > now) + if (i == 0 || press_queue_next_send(pp->sleeps[i]) > now) return false; - if (ph_remove_head(pp->sleeps_heap, true) != i) + if (!queue_try_remove(pp->sleeps[i], press)) + signal_error_by_blinking(); + bool became_empty = queue_is_empty(pp->sleeps[i]); + if (ph_remove_head(pp->sleeps_heap, became_empty) != i) signal_error_by_blinking(); - *press = pp->presses[i]; + if (became_empty) { + pp->sleeps[i] = NULL; + } else { + ph_insert_node(pp->sleeps_heap, i); + } return true; } diff --git a/client/press.h b/client/press.h index 69789e0..6cd4c5b 100644 --- a/client/press.h +++ b/client/press.h @@ -3,6 +3,7 @@ #include "pico/cyw43_arch.h" #include "pico/util/pheap.h" +#include "pico/util/queue.h" typedef struct { uint32_t timestamp; @@ -11,8 +12,17 @@ typedef struct { } press_t; typedef struct { - press_t *presses; + /* Queues of various sizes that hold presses. There is one queue for each + * send_count. */ + queue_t *presses; + + /* Tracks when each queue will be next ready-to-send. Empty queues are not in + * the heap. */ pheap_t *sleeps_heap; + + /* The companion-array for the heap. */ + queue_t **sleeps; + } press_pile_t; press_pile_t *create_press_pile();