From 0527f2292fd8cb1585d63cee916f918cc0a65098 Mon Sep 17 00:00:00 2001
From: Scott Worley <scottworley@scottworley.com>
Date: Tue, 10 Oct 2023 00:50:42 -0700
Subject: [PATCH] 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.
---
 client/press.c | 55 +++++++++++++++++++++++++++++++++++---------------
 client/press.h | 12 ++++++++++-
 2 files changed, 50 insertions(+), 17 deletions(-)

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();
-- 
2.44.1