[gnome-builder] backoff: add exponential backoff helper

[Christian Hergert <chergert src gnome org>]

commit 320236bc311e430d33816d83ad789eaafe54be07
Author: Christian Hergert <chergert redhat com>
Date:   Sun Oct 7 18:28:01 2018 -0700

    backoff: add exponential backoff helper

 src/libide/ide.h              |   1 +
 src/libide/util/ide-backoff.c | 101 +++++++++++++++++++++++++++++++++++++
 src/libide/util/ide-backoff.h |  47 ++++++++++++++++++
 src/libide/util/meson.build   |   2 +
 src/tests/meson.build         |   7 +++
 src/tests/test-backoff.c      | 113 ++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 271 insertions(+)
---
diff --git a/src/libide/ide.h b/src/libide/ide.h
index 3eedc3356..497f423b1 100644
--- a/src/libide/ide.h
+++ b/src/libide/ide.h
@@ -196,6 +196,7 @@ G_BEGIN_DECLS
 #include "transfers/ide-transfer.h"
 #include "transfers/ide-transfer-button.h"
 #include "transfers/ide-transfer-manager.h"
+#include "util/ide-backoff.h"
 #include "util/ide-cell-renderer-fancy.h"
 #include "util/ide-fancy-tree-view.h"
 #include "util/ide-flatpak.h"
diff --git a/src/libide/util/ide-backoff.c b/src/libide/util/ide-backoff.c
new file mode 100644
index 000000000..3cde978e5
--- /dev/null
+++ b/src/libide/util/ide-backoff.c
@@ -0,0 +1,101 @@
+/* ide-backoff.c
+ *
+ * Copyright 2018 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include "config.h"
+
+#define G_LOG_DOMAIN "ide-backoff"
+
+#include "util/ide-backoff.h"
+
+void
+ide_backoff_init (IdeBackoff *self,
+                  guint       min_delay,
+                  guint       max_delay)
+{
+  g_return_if_fail (self != NULL);
+
+  if (max_delay < 2)
+    max_delay = G_MAXUINT;
+
+  self->min_delay = MAX (1, min_delay);
+  self->max_delay = MAX (min_delay, max_delay);
+  self->cur_delay = self->min_delay;
+  self->n_failures = 0;
+
+  g_return_if_fail (self->min_delay > 0);
+  g_return_if_fail (self->cur_delay > 0);
+  g_return_if_fail (self->max_delay >= self->min_delay);
+}
+
+void
+ide_backoff_failed (IdeBackoff *self,
+                    guint      *next_delay)
+{
+  g_return_if_fail (self != NULL);
+  g_return_if_fail (self->min_delay > 0);
+  g_return_if_fail (self->cur_delay > 0);
+  g_return_if_fail (self->max_delay >= self->min_delay);
+
+  self->n_failures++;
+
+  /* Special case overflow for correctness */
+  if (self->cur_delay > (self->max_delay / 2))
+    self->cur_delay = self->max_delay;
+  else
+    self->cur_delay *= 2;
+
+  if (next_delay != NULL)
+    {
+      guint adjustment;
+
+      /*
+       * Generate small random adjustment to the delay time so that we avoid
+       * coordinating components from racing together to failures.
+       *
+       * We don't set this on cur_delay, because we want things to be more
+       * testable and to not drift based on the adjustment.
+       */
+      adjustment = g_random_int_range (0, MIN (self->min_delay,
+                                               MIN (G_MAXINT, self->max_delay) / 4));
+
+      *next_delay = self->cur_delay;
+
+      if (*next_delay == self->max_delay)
+        *next_delay -= adjustment;
+      else
+        *next_delay += adjustment;
+    }
+}
+
+void
+ide_backoff_succeeded (IdeBackoff *self)
+{
+  g_return_if_fail (self != NULL);
+  g_return_if_fail (self->min_delay > 0);
+  g_return_if_fail (self->cur_delay > 0);
+  g_return_if_fail (self->max_delay >= self->min_delay);
+
+  self->n_failures = 0;
+  self->cur_delay = self->min_delay;
+
+  g_return_if_fail (self->min_delay > 0);
+  g_return_if_fail (self->cur_delay > 0);
+  g_return_if_fail (self->max_delay >= self->min_delay);
+}
diff --git a/src/libide/util/ide-backoff.h b/src/libide/util/ide-backoff.h
new file mode 100644
index 000000000..36e1dcbe4
--- /dev/null
+++ b/src/libide/util/ide-backoff.h
@@ -0,0 +1,47 @@
+/* ide-backoff.h
+ *
+ * Copyright 2018 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#pragma once
+
+#include <glib.h>
+
+#include "ide-version-macros.h"
+
+G_BEGIN_DECLS
+
+typedef struct
+{
+  guint min_delay;
+  guint max_delay;
+  guint cur_delay;
+  guint n_failures;
+} IdeBackoff;
+
+IDE_AVAILABLE_IN_3_32
+void ide_backoff_init      (IdeBackoff *self,
+                            guint       min_delay,
+                            guint       max_delay);
+IDE_AVAILABLE_IN_3_32
+void ide_backoff_failed    (IdeBackoff *self,
+                            guint      *next_delay);
+IDE_AVAILABLE_IN_3_32
+void ide_backoff_succeeded (IdeBackoff *self);
+
+G_END_DECLS
diff --git a/src/libide/util/meson.build b/src/libide/util/meson.build
index da66c5218..5cda3ac9b 100644
--- a/src/libide/util/meson.build
+++ b/src/libide/util/meson.build
@@ -1,4 +1,5 @@
 util_headers = [
+  'ide-backoff.h',
   'ide-cell-renderer-fancy.h',
   'ide-fancy-tree-view.h',
   'ide-flatpak.h',
@@ -17,6 +18,7 @@ util_headers = [
 ]
 
 util_sources = [
+  'ide-backoff.c',
   'ide-cell-renderer-fancy.c',
   'ide-fancy-tree-view.c',
   'ide-flatpak.c',
diff --git a/src/tests/meson.build b/src/tests/meson.build
index 42c0e6d28..4a482d5f4 100644
--- a/src/tests/meson.build
+++ b/src/tests/meson.build
@@ -190,6 +190,13 @@ test_iter = executable('test-iter', 'test-iter.c',
 test('test-iter', test_iter, env: ide_test_env)
 
 
+test_backoff = executable('test-backoff', 'test-backoff.c',
+  c_args: ide_test_cflags,
+  dependencies: [ ide_test_deps ],
+)
+test('test-backoff', test_backoff, env: ide_test_env)
+
+
 test_hdr_format = executable('test-hdr-format', [
   'test-hdr-format.c',
   '../plugins/c-pack/c-parse-helper.c',
diff --git a/src/tests/test-backoff.c b/src/tests/test-backoff.c
new file mode 100644
index 000000000..e93a1c26c
--- /dev/null
+++ b/src/tests/test-backoff.c
@@ -0,0 +1,113 @@
+/* test-backoff.c
+ *
+ * Copyright 2018 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include <ide.h>
+#include <math.h>
+
+static void
+test_backoff_basic (void)
+{
+  IdeBackoff backoff;
+  guint next;
+  guint expected = 100;
+
+  ide_backoff_init (&backoff, 100, G_MAXUINT);
+
+  g_assert_cmpint (backoff.min_delay, ==, 100);
+  g_assert_cmpint (backoff.max_delay, ==, G_MAXUINT);
+  g_assert_cmpint (backoff.cur_delay, ==, 100);
+  g_assert_cmpint (backoff.n_failures, ==, 0);
+
+  for (guint i = 0; i < 25; i++)
+    {
+      ide_backoff_failed (&backoff, &next);
+
+      g_assert_cmpint (next, >=, expected);
+
+      expected *= 2;
+
+      g_assert_cmpint (backoff.min_delay, ==, 100);
+      g_assert_cmpint (backoff.max_delay, ==, G_MAXUINT);
+      g_assert_cmpint (backoff.cur_delay, ==, expected);
+      g_assert_cmpint (backoff.n_failures, ==, i + 1);
+    }
+
+  ide_backoff_failed (&backoff, &next);
+
+  g_assert_cmpint (backoff.min_delay, ==, 100);
+  g_assert_cmpint (backoff.max_delay, ==, G_MAXUINT);
+  g_assert_cmpint (backoff.cur_delay, ==, G_MAXUINT);
+  g_assert_cmpint (backoff.n_failures, ==, 26);
+
+  ide_backoff_succeeded (&backoff);
+
+  g_assert_cmpint (backoff.min_delay, ==, 100);
+  g_assert_cmpint (backoff.max_delay, ==, G_MAXUINT);
+  g_assert_cmpint (backoff.cur_delay, ==, 100);
+  g_assert_cmpint (backoff.n_failures, ==, 0);
+}
+
+static void
+test_backoff_max (void)
+{
+  IdeBackoff backoff;
+  guint next;
+
+  ide_backoff_init (&backoff, 100, 300);
+
+  g_assert_cmpint (backoff.min_delay, ==, 100);
+  g_assert_cmpint (backoff.max_delay, ==, 300);
+  g_assert_cmpint (backoff.cur_delay, ==, 100);
+  g_assert_cmpint (backoff.n_failures, ==, 0);
+
+  ide_backoff_failed (&backoff, &next);
+  g_assert_cmpint (backoff.min_delay, ==, 100);
+  g_assert_cmpint (backoff.max_delay, ==, 300);
+  g_assert_cmpint (backoff.cur_delay, ==, 200);
+  g_assert_cmpint (backoff.n_failures, ==, 1);
+  g_assert_cmpint (next, >=, 100);
+  g_assert_cmpint (next, <, 300);
+
+  ide_backoff_failed (&backoff, &next);
+  g_assert_cmpint (backoff.min_delay, ==, 100);
+  g_assert_cmpint (backoff.max_delay, ==, 300);
+  g_assert_cmpint (backoff.cur_delay, ==, 300);
+  g_assert_cmpint (backoff.n_failures, ==, 2);
+  g_assert_cmpint (next, >=, 200);
+  g_assert_cmpint (next, <=, 300);
+
+  ide_backoff_failed (&backoff, &next);
+  g_assert_cmpint (backoff.min_delay, ==, 100);
+  g_assert_cmpint (backoff.max_delay, ==, 300);
+  g_assert_cmpint (backoff.cur_delay, ==, 300);
+  g_assert_cmpint (backoff.n_failures, ==, 3);
+  g_assert_cmpint (next, >=, 200);
+  g_assert_cmpint (next, <=, 300);
+}
+
+gint
+main (gint argc,
+      gchar *argv[])
+{
+  g_test_init (&argc, &argv, NULL);
+  g_test_add_func ("/Ide/Backoff/basic", test_backoff_basic);
+  g_test_add_func ("/Ide/Backoff/max", test_backoff_max);
+  g_test_run ();
+}