libtf: implement timeouts

internally put sleepers to d-ary heap based priority queue. the
heap value is compared with overflow.

3 files changed, 112 insertions, 9 deletions

diff --git a/include/libtf/defines.h b/include/libtf/defines.h
index 7e35ff7..b1d2aa9 100644
--- a/include/libtf/defines.h
+++ b/include/libtf/defines.h
@@ -54,7 +54,7 @@
 #define attribute_never_inline		__attribute__((noinline))
 #define attribute_weak_function		__attribute__((weak))
 
-#define TF_BUG_ON(cond) if (cond) { \
+#define TF_BUG_ON(cond) if (unlikely(cond)) { \
 	fprintf(stderr, "BUG: failure at %s:%d/%s(): %s!\n",	\
 		__FILE__, __LINE__, __func__, #cond);		\
 	abort();						\
@@ -64,4 +64,18 @@
 
 #define TF_EMPTY_ARRAY 0
 
+#ifndef TF_STACK_SIZE
+#define TF_STACK_SIZE		4096
+#endif
+
+/* Monotonic time */
+typedef uint32_t tf_mtime_t;
+typedef int32_t tf_mtime_diff_t;
+
+static inline
+tf_mtime_diff_t tf_mtime_diff(tf_mtime_t a, tf_mtime_t b)
+{
+	return (tf_mtime_diff_t)(a - b);
+}
+
 #endif
diff --git a/include/libtf/fiber.h b/include/libtf/fiber.h
index 48d4924..09d5ef1 100644
--- a/include/libtf/fiber.h
+++ b/include/libtf/fiber.h
@@ -17,26 +17,44 @@
 #include <libtf/defines.h>
 #include <libtf/atomic.h>
 #include <libtf/list.h>
+#include <libtf/heap.h>
 
-#ifndef TF_STACK_SIZE
-#define TF_STACK_SIZE		4096
-#endif
+/* Scheduler */
+struct tf_scheduler {
+	struct tf_list_head	run_q;
+	struct tf_list_head	sleep_q;
+	struct tf_heap_head	heap;
+
+	struct tf_fiber *	active_fiber;
+	int			num_fibers;
 
-struct tf_fiber {
-	unsigned int		ref_count;
-	struct tf_list_node	queue_node;
-	char			data[TF_EMPTY_ARRAY];
+	tf_mtime_t		scheduler_time;
 };
 
-typedef void (*tf_fiber_proc)(void *fiber);
+static inline
+struct tf_scheduler *tf_get_scheduler(void)
+{
+	extern struct tf_scheduler *__tf_scheduler;
+	return __tf_scheduler;
+}
 
+static inline
+tf_mtime_t tf_mtime(void)
+{
+	return tf_get_scheduler()->scheduler_time;
+}
+
+/* Fiber creation */
+typedef void (*tf_fiber_proc)(void *fiber);
 int tf_main(tf_fiber_proc fiber_main);
 
 void *tf_fiber_create(tf_fiber_proc fiber_main, int private_size);
 void *tf_fiber_get(void *data);
 void tf_fiber_put(void *data);
 
+/* Scheduling and fiber management */
 int tf_schedule(int err);
+int tf_msleep(int milliseconds);
 void tf_kill(void *fiber);
 
 static inline int tf_yield(void)
diff --git a/include/libtf/heap.h b/include/libtf/heap.h
new file mode 100644
index 0000000..24f4767
--- /dev/null
+++ b/include/libtf/heap.h
@@ -0,0 +1,71 @@
+/* heap.h - libtf heap
+ *
+ * Copyright (C) 2009 Timo Teräs <timo.teras@iki.fi>
+ * All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 or later as
+ * published by the Free Software Foundation.
+ *
+ * See http://www.gnu.org/ for details.
+ */
+
+#ifndef TF_HEAP_H
+#define TF_HEAP_H
+
+#include <libtf/defines.h>
+
+#define TF_HEAP_D		4
+#define TF_HEAP_ITEM0		(TF_HEAP_D - 1)
+
+typedef tf_mtime_t tf_heap_priority;
+
+struct tf_heap_child {
+	struct tf_heap_node *	ptr;
+	tf_heap_priority	val;
+};
+
+struct tf_heap_node {
+	uint32_t		index;
+};
+
+struct tf_heap_head {
+	uint32_t		num_items;
+	uint32_t		allocated;
+	struct tf_heap_child *	item;
+};
+
+int __tf_heap_grow(struct tf_heap_head *head);
+void tf_heap_insert(struct tf_heap_node *node, struct tf_heap_head *head,
+		    tf_heap_priority val);
+void tf_heap_delete(struct tf_heap_node *node, struct tf_heap_head *head);
+void tf_heap_change(struct tf_heap_node *node, struct tf_heap_head *head,
+		    tf_heap_priority val);
+
+static inline
+tf_heap_priority tf_heap_get_value(struct tf_heap_head *head)
+{
+	return head->item[TF_HEAP_ITEM0].val;
+}
+
+static inline
+struct tf_heap_node *tf_heap_get_node(struct tf_heap_head *head)
+{
+	return head->item[TF_HEAP_ITEM0].ptr;
+}
+
+static inline
+int tf_heap_empty(struct tf_heap_head *head)
+{
+	return head->num_items == 0;
+}
+
+static inline
+int tf_heap_prealloc(struct tf_heap_head *head, uint32_t size)
+{
+	if (unlikely(head->num_items + TF_HEAP_ITEM0 >= head->allocated))
+		return __tf_heap_grow(head);
+	return 0;
+}
+
+#endif