Scheduler is now selectable in make menuconfig in kernel hacking.
authorAnton Eisenbraun <anton@localhost.localdomain>
Mon, 9 Dec 2013 18:51:51 +0000 (19:51 +0100)
committerAnton Eisenbraun <anton@localhost.localdomain>
Mon, 9 Dec 2013 18:51:51 +0000 (19:51 +0100)
New directory structure in sched. Renamed sched.new in modsched and added cfs folder.
Symplified make file which was responsible for intigrating the framework into the build.

49 files changed:
arch/x86/Kconfig.debug
kernel/Makefile
kernel/sched/Makefile
kernel/sched/cfs/Makefile [new file with mode: 0644]
kernel/sched/cfs/auto_group.c [moved from kernel/sched/auto_group.c with 100% similarity]
kernel/sched/cfs/auto_group.h [moved from kernel/sched/auto_group.h with 100% similarity]
kernel/sched/cfs/clock.c [moved from kernel/sched/clock.c with 100% similarity]
kernel/sched/cfs/core.c [moved from kernel/sched/core.c with 100% similarity]
kernel/sched/cfs/cpupri.c [moved from kernel/sched/cpupri.c with 100% similarity]
kernel/sched/cfs/cpupri.h [moved from kernel/sched/cpupri.h with 100% similarity]
kernel/sched/cfs/cputime.c [moved from kernel/sched/cputime.c with 100% similarity]
kernel/sched/cfs/debug.c [moved from kernel/sched/debug.c with 100% similarity]
kernel/sched/cfs/fair.c [moved from kernel/sched/fair.c with 100% similarity]
kernel/sched/cfs/features.h [moved from kernel/sched/features.h with 100% similarity]
kernel/sched/cfs/idle_task.c [moved from kernel/sched/idle_task.c with 100% similarity]
kernel/sched/cfs/rt.c [moved from kernel/sched/rt.c with 100% similarity]
kernel/sched/cfs/sched.h [moved from kernel/sched/sched.h with 100% similarity]
kernel/sched/cfs/stats.c [moved from kernel/sched/stats.c with 100% similarity]
kernel/sched/cfs/stats.h [moved from kernel/sched/stats.h with 100% similarity]
kernel/sched/cfs/stop_task.c [moved from kernel/sched/stop_task.c with 100% similarity]
kernel/sched/modsched/Makefile [moved from kernel/sched.new/Makefile with 97% similarity]
kernel/sched/modsched/clock.c [moved from kernel/sched.new/clock.c with 100% similarity]
kernel/sched/modsched/core.c [moved from kernel/sched.new/core.c with 100% similarity]
kernel/sched/modsched/cputime.c [moved from kernel/sched.new/cputime.c with 100% similarity]
kernel/sched/modsched/framework/Kconfig.debug [new file with mode: 0644]
kernel/sched/modsched/framework/Makefile [new file with mode: 0644]
kernel/sched/modsched/framework/fw.c [new file with mode: 0644]
kernel/sched/modsched/framework/fw_modules.c [new file with mode: 0644]
kernel/sched/modsched/framework/include/fw.h [new file with mode: 0644]
kernel/sched/modsched/framework/include/fw_comm.h [new file with mode: 0644]
kernel/sched/modsched/framework/include/fw_list.h [new file with mode: 0644]
kernel/sched/modsched/framework/include/fw_modules.h [new file with mode: 0644]
kernel/sched/modsched/framework/include/fw_task.h [new file with mode: 0644]
kernel/sched/modsched/framework/include/fw_types.h [new file with mode: 0644]
kernel/sched/modsched/framework/include/os.h [new file with mode: 0644]
kernel/sched/modsched/framework/modules/Makefile [new file with mode: 0644]
kernel/sched/modsched/framework/modules/round_robin.c [new file with mode: 0644]
kernel/sched/modsched/framework/os/Makefile [new file with mode: 0644]
kernel/sched/modsched/framework/os/bertos/os.c [new file with mode: 0644]
kernel/sched/modsched/framework/os/bertos/os.h [new file with mode: 0644]
kernel/sched/modsched/framework/os/bertos/os_p.c [new file with mode: 0644]
kernel/sched/modsched/framework/os/bertos/rules.mk [new file with mode: 0644]
kernel/sched/modsched/framework/os/freebsd/os.c [new file with mode: 0644]
kernel/sched/modsched/framework/os/linux/Makefile [new file with mode: 0644]
kernel/sched/modsched/framework/os/linux/os.c [new file with mode: 0644]
kernel/sched/modsched/framework/sys/Makefile [new file with mode: 0644]
kernel/sched/modsched/framework/sys/fw_comm.c [new file with mode: 0644]
kernel/sched/modsched/framework/sys/fw_list.c [new file with mode: 0644]
kernel/sched/modsched/sched.h [moved from kernel/sched.new/sched.h with 100% similarity]

index b322f12..9e5945b 100644 (file)
@@ -318,4 +318,6 @@ config DEBUG_NMI_SELFTEST
 
          If unsure, say N.
 
+source "kernel/sched/modsched/framework/Kconfig.debug"
+
 endmenu
index 904c367..607e4c5 100644 (file)
@@ -22,11 +22,8 @@ CFLAGS_REMOVE_cgroup-debug.o = -pg
 CFLAGS_REMOVE_irq_work.o = -pg
 endif
 
-ifdef __KERN_ORG__
 obj-y += sched/
-else
-obj-y += sched.new/
-endif
+
 obj-y += power/
 
 obj-$(CONFIG_CHECKPOINT_RESTORE) += kcmp.o
index f06d249..f4a761b 100644 (file)
@@ -1,18 +1,7 @@
-ifdef CONFIG_FUNCTION_TRACER
-CFLAGS_REMOVE_clock.o = -pg
-endif
+KBUILD_CFLAGS += -Ikernel/sched/
 
-ifneq ($(CONFIG_SCHED_OMIT_FRAME_POINTER),y)
-# According to Alan Modra <alan@linuxcare.com.au>, the -fno-omit-frame-pointer is
-# needed for x86 only.  Why this used to be enabled for all architectures is beyond
-# me.  I suspect most platforms don't need this, but until we know that for sure
-# I turn this off for IA-64 only.  Andreas Schwab says it's also needed on m68k
-# to get a correct value for the wait-channel (WCHAN in ps). --davidm
-CFLAGS_core.o := $(PROFILING) -fno-omit-frame-pointer
-endif
-
-obj-y += core.o clock.o cputime.o idle_task.o fair.o rt.o stop_task.o
-obj-$(CONFIG_SMP) += cpupri.o
-obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o
-obj-$(CONFIG_SCHEDSTATS) += stats.o
-obj-$(CONFIG_SCHED_DEBUG) += debug.o
+ifdef __KERN_ORG__
+obj-$(CONFIG_CFS_SCHED) += cfs/
+else
+obj-$(CONFIG_MOD_SCHED) += modsched/
+endif
\ No newline at end of file
diff --git a/kernel/sched/cfs/Makefile b/kernel/sched/cfs/Makefile
new file mode 100644 (file)
index 0000000..f06d249
--- /dev/null
@@ -0,0 +1,18 @@
+ifdef CONFIG_FUNCTION_TRACER
+CFLAGS_REMOVE_clock.o = -pg
+endif
+
+ifneq ($(CONFIG_SCHED_OMIT_FRAME_POINTER),y)
+# According to Alan Modra <alan@linuxcare.com.au>, the -fno-omit-frame-pointer is
+# needed for x86 only.  Why this used to be enabled for all architectures is beyond
+# me.  I suspect most platforms don't need this, but until we know that for sure
+# I turn this off for IA-64 only.  Andreas Schwab says it's also needed on m68k
+# to get a correct value for the wait-channel (WCHAN in ps). --davidm
+CFLAGS_core.o := $(PROFILING) -fno-omit-frame-pointer
+endif
+
+obj-y += core.o clock.o cputime.o idle_task.o fair.o rt.o stop_task.o
+obj-$(CONFIG_SMP) += cpupri.o
+obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o
+obj-$(CONFIG_SCHEDSTATS) += stats.o
+obj-$(CONFIG_SCHED_DEBUG) += debug.o
similarity index 100%
rename from kernel/sched/core.c
rename to kernel/sched/cfs/core.c
similarity index 100%
rename from kernel/sched/fair.c
rename to kernel/sched/cfs/fair.c
similarity index 100%
rename from kernel/sched/rt.c
rename to kernel/sched/cfs/rt.c
similarity index 97%
rename from kernel/sched.new/Makefile
rename to kernel/sched/modsched/Makefile
index 35630f6..a0bedc9 100644 (file)
@@ -17,3 +17,6 @@ obj-y += core.o clock.o cputime.o
 #obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o
 #obj-$(CONFIG_SCHEDSTATS) += stats.o
 #obj-$(CONFIG_SCHED_DEBUG) += debug.o
+
+obj-y += framework/
+
diff --git a/kernel/sched/modsched/framework/Kconfig.debug b/kernel/sched/modsched/framework/Kconfig.debug
new file mode 100644 (file)
index 0000000..ceb824f
--- /dev/null
@@ -0,0 +1,19 @@
+#
+# Modulized scheduler framework
+#
+
+choice 
+       prompt "Scheduler"
+       default MOD_SCHED
+
+config MOD_SCHED
+        boolean "Modulized scheduler framework"
+        help
+          Modulized scheduler framework developted by KBS Institute TU Berlin.
+
+config CFS_SCHED
+        boolean "Completely Fair Scheduler"
+        help
+          Completely Fair Scheduler (CFS) is a process scheduler developt by Ingo Molnár. 
+
+endchoice
diff --git a/kernel/sched/modsched/framework/Makefile b/kernel/sched/modsched/framework/Makefile
new file mode 100644 (file)
index 0000000..b47e879
--- /dev/null
@@ -0,0 +1,8 @@
+KBUILD_CFLAGS += -Ikernel/sched/modsched/framework/include
+
+obj-y += fw.o fw_modules.o
+
+obj-y += os/
+obj-y += modules/
+obj-y += sys/
+
diff --git a/kernel/sched/modsched/framework/fw.c b/kernel/sched/modsched/framework/fw.c
new file mode 100644 (file)
index 0000000..f0b9e77
--- /dev/null
@@ -0,0 +1,88 @@
+/*
+ * fw.c
+ *
+ * Framework functionality is mapped to os functions.
+ *
+ *      Author: Daniel Roehrig, Christian Rene Sechting
+ */
+
+
+#include "include/fw.h"
+#include "include/fw_comm.h"
+#include "include/os.h"
+
+
+
+void *fw_malloc(fw_size_t size)
+{
+       return os_malloc(size);
+}
+
+void fw_free(void* ptr)
+{
+       os_free(ptr);
+}
+
+void fw_create_task(fw_task_t *task)
+{
+       os_create_task(task);
+       fw_notify(ADMIT, task);
+}
+
+void fw_dispatch(fw_task_t *task)
+{
+       os_dispatch(task);
+}
+
+void fw_dispatch_mp(fw_task_t *task, int cpu)
+{
+       os_dispatch_mp(task, cpu);
+}
+
+fw_task_t *fw_current_task(int cpu)
+{
+       return os_current_task(cpu);
+}
+
+int fw_task_info(fw_task_t *task, char *buf, int length)
+{
+       int count = 0;
+
+//     count += snprintf(buf, length, "Name: ");
+//
+//     count += os_task_name(task, buf+count, length-count);
+//
+//     count += snprintf(buf+count, length-count, ", State: ");
+
+
+//     switch(task->state) {
+//     case RUNNING:
+//             count += snprintf(buf+count, length-count, "running");
+//             break;
+//     case BLOCKED:
+//             count += snprintf(buf+count, length-count, "blocked");
+//             break;
+//     case READY:
+//             count += snprintf(buf+count, length-count, "ready");
+//             break;
+//     default:
+//             count += snprintf(buf+count, length-count, "unknown");
+//             break;
+//     }
+
+       return count;
+}
+
+int fw_module_count;
+int fw_register_module(){
+       return (fw_module_count+1) == FW_MAX_MODULES ? -1 : fw_module_count++;
+}
+
+void fw_init()
+{
+       fw_module_count = 0;
+
+       os_init_os();
+       fw_init_comm();
+       fw_modules_init();
+}
diff --git a/kernel/sched/modsched/framework/fw_modules.c b/kernel/sched/modsched/framework/fw_modules.c
new file mode 100644 (file)
index 0000000..679dc93
--- /dev/null
@@ -0,0 +1,14 @@
+/*
+ * fw_modules.c
+ *
+ *
+ */
+#include "include/fw_modules.h"
+
+
+
+void fw_modules_init(void)
+{
+       rr_init();
+//     init_sched_rr_module();
+}
diff --git a/kernel/sched/modsched/framework/include/fw.h b/kernel/sched/modsched/framework/include/fw.h
new file mode 100644 (file)
index 0000000..d6e4cda
--- /dev/null
@@ -0,0 +1,63 @@
+#ifndef FW_H_
+#define FW_H_
+
+#include "fw_types.h"
+#include "fw_task.h"
+#include "os.h"
+
+#define fw_printf os_printf
+
+/**
+ * \brief A printf function.
+ *
+ * @param formatstring The format string to print on screen.
+ */
+//#define fw_printf(fmt, ...)  os_printf(fmt ,## __VA_ARGS__)
+
+/**
+ * \brief Dynamic allocation of memory.
+ *
+ * @param size The amount of memory to allocate.
+ * @return A pointer to the allocated memory.
+ */
+void *fw_malloc(fw_size_t size);
+
+/**
+ * \brief Releases a dynamically allocated chunk of memory.
+ *
+ * @param ptr Memory region to release.
+ */
+void fw_free(void* ptr);
+
+void fw_create_task(fw_task_t *task);
+
+/**
+ * \brief Runs the given task on a (random) processing unit.
+ *
+ * @param task The task that shall run.
+ */
+void fw_dispatch(fw_task_t *task);
+
+/**
+ * \brief Runs the given task on the given processing unit.
+ *
+ * @param task The task that shall run.
+ * @param cpu The CPU that will run the task.
+ */
+void fw_dispatch_mp(fw_task_t *task, int cpu);
+
+/**
+ * \brief Retrieves the currently running thread on the requested CPU.
+ *
+ * @param cpu The CPU of interest.
+ * @return The thread structure of the requested or current CPU respectively.
+ */
+fw_task_t *fw_current_task(int cpu);
+
+int fw_task_info(fw_task_t *task, char *buf, int length);
+
+int fw_register_module(void);
+
+void fw_init(void);
+
+#endif /* FW_H_ */
diff --git a/kernel/sched/modsched/framework/include/fw_comm.h b/kernel/sched/modsched/framework/include/fw_comm.h
new file mode 100644 (file)
index 0000000..fa9ec92
--- /dev/null
@@ -0,0 +1,34 @@
+#ifndef FW_COMM_H_
+#define FW_COMM_H_
+
+/**
+ * Prototypes:
+ *
+ * SCHEDULE:   void (void);
+ * ADMIT:              void (fw_task_t *task);
+ * RELEASE:            void (fw_task_t *task);
+ * EVENT:              void (fw_task_t *task);
+ * EVENT_WAIT: void (fw_task_t *task);
+ * SUSPEND:            void (fw_task_t *task);
+ * ACTIVATE:   void (fw_task_t *task);
+ *
+ */
+typedef enum {
+       FW_FIRST,
+       SCHEDULE,
+       ADMIT,
+       RELEASE,
+       EVENT,
+       EVENT_WAIT,
+       SUSPEND,
+       ACTIVATE,
+       FW_LAST
+} topic_t;
+
+void fw_subscribe(topic_t topic, void *callback);
+
+void fw_notify(topic_t topic, void *data);
+
+void fw_init_comm(void);
+
+#endif /* FW_COMM_H_ */
diff --git a/kernel/sched/modsched/framework/include/fw_list.h b/kernel/sched/modsched/framework/include/fw_list.h
new file mode 100644 (file)
index 0000000..3534f18
--- /dev/null
@@ -0,0 +1,140 @@
+#ifndef _FW_LIST_H
+#define _FW_LIST_H
+
+
+/*
+ * Copied and heavily modified from Linux implementation.
+ *  Created on:23.07.2013
+ *     Authors: Christian René Sechting, Daniel Roehrig
+ *
+ */
+
+#undef offsetof
+#define offsetof(TYPE, MEMBER) ((fw_size_t) &((TYPE *)0)->MEMBER)
+
+/**
+ * fw_container_of - cast a member of a structure out to the containing structure
+ * @ptr:        the pointer to the member.
+ * @type:       the type of the container struct this is embedded in.
+ * @member:     the name of the member within the struct.
+ *
+ */
+#define fw_container_of(ptr, type, member) ({               \
+       const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
+       (type *)( (char *)__mptr - offsetof(type,member) );})
+
+
+typedef struct fw_list_head {
+       struct fw_list_head *next, *prev;
+} fw_list_head_t;
+
+/**
+ * Initializing the list
+ * @name: the head for your list.
+ */
+#define FW_LIST_INIT(name)     name.next = name.prev = &(name)
+
+#define FW_LIST_HEAD_INIT(name) { &(name), &(name) }
+
+#define FW_LIST_HEAD(name) \
+       struct fw_list_head name = FW_LIST_HEAD_INIT(name)
+
+
+/**
+ * fw_list_entry - get the struct for this entry
+ * @ptr:       the &struct list_head pointer.
+ * @type:      the type of the struct this is embedded in.
+ * @member:    the name of the list_struct within the struct.
+ */
+#define fw_list_entry(ptr, type, member) \
+       fw_container_of(ptr, type, member)
+
+/**
+ * list_for_each_entry -       iterate over list of given type
+ * @pos:       the type * to use as a loop cursor.
+ * @head:      the head for your list.
+ * @member:    the name of the list_struct within the struct.
+ */
+#define fw_list_for_each_entry(pos, head, member)                              \
+       for (pos = fw_list_entry((head)->next, typeof(*pos), member);   \
+            &pos->member != (head);    \
+            pos = fw_list_entry(pos->member.next, typeof(*pos), member))
+
+/**
+ * list_empty - tests whether a list is empty
+ * @head: the list to test.
+ */
+int fw_list_empty(const struct fw_list_head *head);
+
+/**
+ * fw_list_length - returns the number of entries in a list.
+ * @head: the &struct fw_list_head pointer.
+ */
+int fw_list_length(const struct fw_list_head *head);
+
+/*
+ * Insert a new entry between two known consecutive entries.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+void __fw_list_add(struct fw_list_head *_new,
+                             struct fw_list_head *prev,
+                             struct fw_list_head *next);
+
+/**
+ * list_add_tail - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it before
+ *
+ * Insert a new entry before the specified head.
+ * This is useful for implementing queues.
+ */
+void fw_list_add_tail(struct fw_list_head *_new, struct fw_list_head *head);
+
+/**
+ * fw_list_add_first - add a new entry at the beginning of the list
+ * @new: new entry to be added
+ * @head: list head to add it after
+ */
+void fw_list_add_first(struct fw_list_head *_new, struct fw_list_head *head);
+
+/**
+ * fw_list_add_at_pos - add a new entry at this position (starting with 0);
+ * @new: new entry to be added
+ * @head: list head to add it after
+ * @pos: position where to insert the element at
+ */
+void fw_list_add_at_pos(struct fw_list_head *_new, struct fw_list_head *head, int pos);
+
+
+/*
+ * Delete a list entry by making the prev/next entries
+ * point to each other.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+void __fw_list_del(struct fw_list_head * prev, struct fw_list_head * next);
+
+void __fw_list_del_entry(struct fw_list_head *entry);
+
+/**
+ * fw_list_del - deletes entry from list.
+ * @entry: the element to delete from the list.
+ * Note: list_empty() on entry does not return true after this, the entry is
+ * in an undefined state.
+ */
+void fw_list_del(struct fw_list_head *entry);
+
+/*
+ * pop functionality to remove the first element of the list an return it
+ */
+struct fw_list_head *__fw_list_pop(struct fw_list_head *head);
+
+/*
+ * use the define here to pop of the list to get the entry and not only the list element
+ */
+#define fw_list_pop(head,type,member) fw_list_entry(__fw_list_pop(head),type,member)
+
+#endif
diff --git a/kernel/sched/modsched/framework/include/fw_modules.h b/kernel/sched/modsched/framework/include/fw_modules.h
new file mode 100644 (file)
index 0000000..e46ea9b
--- /dev/null
@@ -0,0 +1,13 @@
+#ifndef FW_MODULES_H_
+#define FW_MODULES_H_
+
+#define FW_MAX_MODULES 8
+
+
+void fw_modules_init(void);
+
+int init_sched_rr_module(void);
+
+void rr_init(void);
+
+#endif /* FW_MODULES_H_ */
diff --git a/kernel/sched/modsched/framework/include/fw_task.h b/kernel/sched/modsched/framework/include/fw_task.h
new file mode 100644 (file)
index 0000000..9eb6c63
--- /dev/null
@@ -0,0 +1,76 @@
+/**
+ * fw_task.h
+ *
+ * Framework Tasks (implemented in the os spcific folder)
+ *
+ *  Created on: 05.11.2013
+ *      Author: Daniel Roehrig, Christian Rene Sechting
+ */
+#ifndef FW_TASK_H_
+#define FW_TASK_H_
+
+#include "fw_list.h"
+#include "fw_modules.h"
+
+#define task_context_t void
+
+typedef enum {RUNNING, BLOCKED, READY} fw_task_state_t;
+
+typedef struct fw_task{
+       task_context_t *task_context;
+       void *real_task;
+
+       fw_task_state_t state;
+
+       void *module_data[FW_MAX_MODULES];
+
+       fw_list_head_t list;
+} fw_task_t;
+
+typedef struct fw_task_list_entry{
+       fw_list_head_t list;
+       fw_task_t task;
+       void *module_data[FW_MAX_MODULES];
+} fw_task_list_entry_t;
+
+/*
+ *  initialize the task_struct_padding with 0 and
+ *  creates a list for all tasks
+ */
+void init_fw_tasks(void);
+
+/*
+ *  TODO: check if needed
+ *  every scheduler module can demand individual
+ *  fields in the task_struct and this is the
+ *  overall counter of all extra memory that needs
+ *  to be allocated from the framework per task
+ */
+extern unsigned long task_struct_padding;
+
+/*
+ * returns the fw_task equivalent of the given os task
+ */
+struct fw_task *find_fw_task(void *real_task);
+
+/*
+ *  returns the os task equivalent of the given fw_task
+ */
+void *find_real_task(struct fw_task *task);
+
+/*
+ *  creates a fw_task equivalent for the given os task
+ *  or returns the fw_task if already there.
+ */
+struct fw_task *register_task(void *real_task);
+
+int fw_task_is_registered(void *tsk);
+void insert_fw_task(struct fw_task *new_task, void *tsk);
+
+void set_idle_task(struct fw_task *idle);
+struct fw_task *get_idle_task(void);
+
+int fw_get_state(struct fw_task *task);
+int fw_get_pid(struct fw_task *task);
+
+#endif /* FW_TASK_H_ */
diff --git a/kernel/sched/modsched/framework/include/fw_types.h b/kernel/sched/modsched/framework/include/fw_types.h
new file mode 100644 (file)
index 0000000..92e3ad9
--- /dev/null
@@ -0,0 +1,21 @@
+/*
+ * types.h
+ *
+ *  Created on: 23.10.2013
+ *      Author: Anselm Busse
+ */
+
+#ifndef FW_TYPES_H_
+#define FW_TYPES_H_
+
+#ifndef NULL
+#define NULL (void *)0
+#endif
+
+#define fw_spinlock_t int
+#define FW_SPINLOCK_CREATE(name) fw_spinlock_t name = 0
+
+//int for 8 bit long for 64 bit?
+#define fw_size_t long
+
+#endif /* FW_TYPES_H_ */
diff --git a/kernel/sched/modsched/framework/include/os.h b/kernel/sched/modsched/framework/include/os.h
new file mode 100644 (file)
index 0000000..61e556d
--- /dev/null
@@ -0,0 +1,89 @@
+/**
+ * \file os.h
+ * \brief Function prototypes for operating system depend code.
+ * \author Anselm Busse
+ *
+ * This file defines functions that have to be implemented explicitly for every operating system
+ */
+
+#ifndef OS_H_
+#define OS_H_
+
+#include "fw_types.h"
+#include "fw_task.h"
+#include <linux/kernel.h>
+
+
+#define os_printf              printk                  /* Mapping of OS dependent printf */
+
+
+
+/**
+ * \brief Dynamic allocation of memory.
+ *
+ * @param size The amount of memory to allocate.
+ * @return A pointer to the allocated memory.
+ */
+void *os_malloc(fw_size_t size);
+
+/**
+ * \brief Releases a dynamically allocated chunk of memory.
+ *
+ * @param ptr Memory region to release.
+ */
+void os_free(void* ptr);
+
+void os_create_task(fw_task_t *task);
+
+/**
+ * \brief Runs the given task on a (random) processing unit.
+ *
+ * @param task The task that shall run.
+ */
+void os_dispatch(fw_task_t *task);
+
+/**
+ * \brief Runs the given task on the given processing unit.
+ *
+ * @param task The task that shall run.
+ * @param cpu The CPU that will run the task.
+ */
+void os_dispatch_mp(fw_task_t *task, int cpu);
+
+/**
+ * \brief Returns current task on cpu.
+ *
+ * @param cpu The CPU .
+ */
+fw_task_t *os_current_task(int cpu);
+
+/**
+ * \brief Initialization of the operating depended code.
+ *
+ * @return Should return 0 iff initialization successful.
+ */
+int os_init_os(void);
+
+void os_spinlock(fw_spinlock_t *lock);
+
+void os_spinunlock(fw_spinlock_t *lock);
+
+/**
+ * \brief Returns the name of the task.
+ *
+ * @param *task Pointer to the task
+ * @param *buf Buffer the name is written to.
+ * @param size Size of the buffer.
+ * @return Returns the size of buf.
+ */
+int os_task_name(fw_task_t *task, char *buf, fw_size_t size);
+
+const char *os_task_info(fw_task_t *task);
+
+/*
+#if 1
+#include "bertos/os.h"
+#endif
+*/
+
+#endif /* OS_H_ */
diff --git a/kernel/sched/modsched/framework/modules/Makefile b/kernel/sched/modsched/framework/modules/Makefile
new file mode 100644 (file)
index 0000000..0b6fb89
--- /dev/null
@@ -0,0 +1 @@
+obj-y += round_robin.o
diff --git a/kernel/sched/modsched/framework/modules/round_robin.c b/kernel/sched/modsched/framework/modules/round_robin.c
new file mode 100644 (file)
index 0000000..6d52a6d
--- /dev/null
@@ -0,0 +1,188 @@
+
+
+#include "fw.h"
+#include "os.h"
+#include "fw_comm.h"
+#include "fw_modules.h"
+
+
+
+
+void rr_print_ready_list(void);
+void rr_schedule(void);
+void rr_task_admit(fw_task_t *task);
+void rr_task_release(fw_task_t *task);
+void rr_task_wait(fw_task_t *task);
+void rr_task_event(fw_task_t *task);
+void rr_init(void);
+
+int module_uid;
+
+int idle = 0;
+
+FW_LIST_HEAD(rr_processes);
+FW_SPINLOCK_CREATE(rr_lock);
+
+struct rr_proc_list_elem {
+       fw_list_head_t list;
+       fw_task_t *task;
+};
+
+struct rr_proc_list_elem *rr_current_task = NULL;
+
+struct prpc *current_process;
+
+char rr_buf[120];
+
+
+
+void rr_print_ready_list(void)
+{
+       struct rr_proc_list_elem *tmp;
+
+       fw_printf("Task List:\n");
+
+       fw_list_for_each_entry(tmp, &rr_processes, list){
+               fw_task_info(tmp->task, rr_buf, 120);
+               fw_printf("\t%s\n", rr_buf);
+       }
+}
+
+void rr_schedule(void)
+{
+       struct rr_proc_list_elem *next_task;
+
+       fw_printf("invoked schedule\n");
+       rr_print_ready_list();
+       //printf("invoked schedule! curent task state %d\n", fw_current_task(0)->state);
+
+       os_spinlock(&rr_lock);
+
+       if(fw_current_task(0)->state == RUNNING)
+               fw_list_add_tail(&fw_current_task(0)->list, &rr_processes);
+
+       os_spinunlock(&rr_lock);
+
+       if(fw_list_empty(&rr_processes))
+               fw_printf("start waiting\n");
+
+       while(fw_list_empty(&rr_processes)){
+//             IRQ_ENABLE;
+//             CPU_IDLE;
+//             MEMORY_BARRIER;
+//             IRQ_DISABLE;
+
+       }
+
+       fw_printf("finished waiting\n");
+
+       os_spinlock(&rr_lock);
+
+       fw_printf("ready tasks: %d\n", fw_list_length(&rr_processes));
+
+       next_task = fw_list_pop(&rr_processes, struct rr_proc_list_elem, list);
+
+       current_process = next_task->task->real_task;
+
+//     os_spinlock(&rr_lock);
+       os_spinunlock(&rr_lock);
+
+       fw_printf("dispatching %s\n", os_task_info(next_task->task));
+
+       fw_dispatch(next_task->task);
+}
+
+void rr_task_admit(fw_task_t *task)
+{
+       struct rr_proc_list_elem *new_task = fw_malloc((fw_size_t) sizeof(struct rr_proc_list_elem));
+
+
+       fw_printf("RR registered creation of %s (%p)\n", os_task_info(task), task);
+
+       new_task->task = task;
+
+       os_spinlock(&rr_lock);
+
+
+       fw_list_add_tail(&new_task->list, &rr_processes);
+       rr_current_task = new_task;
+
+       os_spinunlock(&rr_lock);
+}
+
+void rr_task_release(fw_task_t *task)
+{
+       struct rr_proc_list_elem *tmp;
+
+       fw_printf("RR registered deletion of %s (%p)\n", os_task_info(task), task);
+
+       os_spinlock(&rr_lock);
+
+       fw_list_for_each_entry(tmp, &rr_processes, list)
+               if(tmp->task == task)
+               {
+                       fw_list_del(&tmp->list);
+                       fw_free(tmp);
+                       break;
+               }
+
+       fw_printf("RR removed %s (%p)\n", os_task_info(task), task);
+
+       os_spinunlock(&rr_lock);
+}
+
+void rr_task_wait(fw_task_t *task)
+{
+       struct rr_proc_list_elem *tmp;
+
+       fw_printf("RR registered suspension of %s (%p)\n", os_task_info(task), task);
+
+       os_spinlock(&rr_lock);
+
+       fw_printf("%d tasks available\n", fw_list_length(&rr_processes));
+
+       task->state = BLOCKED;
+
+//     current_process = NULL;
+//     os_set_current_task(NULL);
+
+       fw_list_for_each_entry(tmp, &rr_processes, list) {
+               //fw_printf("considering %s (%p) for removal\n", os_task_info(tmp->task), tmp->task);
+
+               if(tmp->task == task)
+               {
+                       fw_list_del(&tmp->list);
+                       fw_free(tmp);
+                       break;
+               }
+       }
+
+       fw_printf("%d tasks remaining\n", fw_list_length(&rr_processes));
+
+       os_spinunlock(&rr_lock);
+
+}
+
+void rr_task_event(fw_task_t *task)
+{
+       struct rr_proc_list_elem *new_task = fw_malloc((fw_size_t) sizeof(struct rr_proc_list_elem));
+       new_task->task = task;
+
+       os_spinlock(&rr_lock);
+
+       task->state = READY;
+       fw_list_add_tail(&new_task->list, &rr_processes);
+
+       os_spinunlock(&rr_lock);
+       fw_printf("task submitted\n");
+}
+
+void rr_init(){
+       module_uid = fw_register_module();
+
+       fw_subscribe(ADMIT, &rr_task_admit);
+       fw_subscribe(RELEASE, &rr_task_release);
+       fw_subscribe(EVENT, &rr_task_event);
+       fw_subscribe(EVENT_WAIT, &rr_task_wait);
+       fw_subscribe(SCHEDULE, &rr_schedule);
+}
diff --git a/kernel/sched/modsched/framework/os/Makefile b/kernel/sched/modsched/framework/os/Makefile
new file mode 100644 (file)
index 0000000..c26281a
--- /dev/null
@@ -0,0 +1 @@
+obj-y += linux/
diff --git a/kernel/sched/modsched/framework/os/bertos/os.c b/kernel/sched/modsched/framework/os/bertos/os.c
new file mode 100644 (file)
index 0000000..71e98f1
--- /dev/null
@@ -0,0 +1,98 @@
+#include "../os.h"
+
+#include <stdarg.h>
+
+#include <cfg/debug.h>
+
+#include <cpu/pgm.h>
+#include <cpu/irq.h>
+#include <cpu/types.h>
+#include <cpu/frame.h>
+
+#include <struct/heap.h>
+
+#include <kern/proc.h>
+
+
+HEAP_DEFINE_BUF(os_heap_buf, 1024);
+Heap os_heap;
+
+fw_task_t *current_task = NULL;
+
+void os_set_current_task(fw_task_t *task){
+       current_task = task;
+}
+
+void *os_malloc(fw_size_t size){
+       return heap_malloc(&os_heap, (size_t) size);
+}
+
+void os_free(void* ptr)
+{
+       heap_free(&os_heap, ptr);
+}
+
+void os_create_task(fw_task_t *task)
+{
+       (void) task;
+}
+
+void os_dispatch(fw_task_t *task)
+{
+       cpu_stack_t *dummy;
+
+       fw_task_t *old_task = current_task;
+       current_task = task;
+
+
+       /*
+        * If there is no old process, we save the old stack pointer into a
+        * dummy variable that we ignore.  In fact, this happens only when the
+        * old process has just exited.
+        */
+       //os_printf("switching %x (%x) and %x (%x)\n", ((Process*)(task->real_task))->stack, &((Process*)(task->real_task))->stack, ((Process*)(current_task->real_task))->stack, &((Process*)(current_task->real_task))->stack);
+
+
+       asm_switch_context(&((Process*)(current_task->real_task))->stack, old_task ? &((Process*)(old_task->real_task))->stack : &dummy);
+}
+
+void os_dispatch_mp(fw_task_t *task, int cpu)
+{
+       (void) cpu;
+       os_dispatch(task);
+}
+
+int os_init_os(){
+       kprintf("Initializing for BeRTOS...");
+
+       heap_init(&os_heap, os_heap_buf, sizeof(os_heap_buf));
+
+       kprintf("done!\n");
+       return 0;
+}
+
+inline void os_spinlock(fw_spinlock_t *lock)
+{
+       cpu_flags_t __flags; \
+       IRQ_SAVE_DISABLE(__flags); \
+       while(*lock){
+               IRQ_RESTORE(__flags);
+               CPU_IDLE;
+               MEMORY_BARRIER;
+               IRQ_SAVE_DISABLE(__flags);
+       }
+       *lock = 1;
+       IRQ_RESTORE(__flags);
+}
+
+inline void os_spinunlock(fw_spinlock_t *lock)
+{
+       cpu_flags_t __flags; \
+       IRQ_SAVE_DISABLE(__flags); \
+       *lock = 0;
+       IRQ_RESTORE(__flags);
+}
+
+const char *os_task_info(fw_task_t *task){
+       return task->real_task ? proc_name(task->real_task) : "Invalid Task";
+}
diff --git a/kernel/sched/modsched/framework/os/bertos/os.h b/kernel/sched/modsched/framework/os/bertos/os.h
new file mode 100644 (file)
index 0000000..82842ce
--- /dev/null
@@ -0,0 +1,25 @@
+#ifndef BERTOS_OS_H_
+#define BERTOS_OS_H_
+
+#include <cfg/os.h>
+#include <cfg/compiler.h>
+
+#include "cfg/cfg_debug.h"   /* CONFIG_KDEBUG_* */
+
+#include <kern/irq.h>
+
+#ifdef _DEBUG
+       #include <cpu/attr.h>        /* CPU_HARVARD */
+       #if CPU_HARVARD
+               #include <cpu/pgm.h>
+               //void os_printf_P(const char *PROGMEM fmt, ...) FORMAT(__printf__, 1, 2);
+               #define os_printf(fmt, ...)  kprintf_P(PSTR(fmt) ,## __VA_ARGS__)
+       #else /* !CPU_HARVARD */
+               void os_printf(const char *fmt, ...) FORMAT(__printf__, 1, 2);
+       #endif /* !CPU_HARVARD */
+#endif
+
+
+
+
+#endif /* BERTOS_OS_H_ */
diff --git a/kernel/sched/modsched/framework/os/bertos/os_p.c b/kernel/sched/modsched/framework/os/bertos/os_p.c
new file mode 100644 (file)
index 0000000..86eea27
--- /dev/null
@@ -0,0 +1,17 @@
+#include "../os.h"
+
+#include <stdarg.h>
+
+#include <cfg/debug.h>
+
+#include <cpu/pgm.h>
+
+/*
+void PGM_FUNC(os_printf)(const char * PGM_ATTR fmt, ...)
+{
+       va_list ap;
+
+       va_start(ap, fmt);
+       PGM_FUNC(kvprintf)(fmt, ap);
+       va_end(ap);
+}*/
diff --git a/kernel/sched/modsched/framework/os/bertos/rules.mk b/kernel/sched/modsched/framework/os/bertos/rules.mk
new file mode 100644 (file)
index 0000000..b0199bf
--- /dev/null
@@ -0,0 +1,14 @@
+fw_CPPFLAGS += \
+    -I$(SCHED_PATH)
+    
+fw_USER_CSRC += \
+    $(SCHED_PATH)/fw.c \
+    $(SCHED_PATH)/fw_comm.c \
+    $(SCHED_PATH)/fw_list.c \
+    $(SCHED_PATH)/fw_modules.c \
+    $(SCHED_PATH)/modules/round_robin.c \
+    $(SCHED_PATH)/os/bertos/os.c 
+
+# Files included by the user.
+fw_USER_PCSRC += \
+    $(SCHED_PATH)/os/bertos/os_p.c
diff --git a/kernel/sched/modsched/framework/os/freebsd/os.c b/kernel/sched/modsched/framework/os/freebsd/os.c
new file mode 100644 (file)
index 0000000..890a82e
--- /dev/null
@@ -0,0 +1,118 @@
+/*
+ * os.c
+ *
+ *  Created on: 04.12.2013
+ *      Author: jkrieg
+ */
+
+#include "os.h"
+
+
+/**
+ * CPU dependent context switching routines.
+ *
+ * Saving and restoring the context on the stack is done by a CPU-dependent
+ * support routine which usually needs to be written in assembly.
+ */
+//EXTERN_C void asm_switch_context(cpu_stack_t **new_sp, cpu_stack_t **save_sp);
+
+//HEAP_DEFINE_BUF(os_heap_buf, 1024);
+//Heap os_heap;
+
+fw_task_t *current_task = NULL;
+
+void os_set_current_task(fw_task_t *task){
+       current_task = task;
+       printf("current_task set to %p\n", task);
+}
+
+void *os_malloc(fw_size_t size){
+//     return heap_malloc(&os_heap, (size_t) size);
+}
+
+void os_free(void* ptr)
+{
+//     heap_free(&os_heap, ptr);
+}
+
+void os_create_task(fw_task_t *task)
+{
+       (void) task;
+}
+
+void os_dispatch(fw_task_t *task)
+{
+//     cpu_stack_t *dummy;
+//
+//
+//
+//     fw_task_t *old_task;
+//     old_task = current_task;
+//
+//
+//     os_set_current_task(task);
+//
+//     os_printf("switching from '%s' (%p) to '%s' (%p)\n", os_task_info(old_task), old_task, os_task_info(current_task), current_task);
+//     os_printf("switching stack from %x (%p) &(%p) to %x (%p) &(%p)\n", *((Process*)(old_task->real_task))->stack, ((Process*)(old_task->real_task))->stack, &((Process*)(old_task->real_task))->stack, *((Process*)(current_task->real_task))->stack, ((Process*)(current_task->real_task))->stack, &((Process*)(current_task->real_task))->stack);
+//
+//     /*
+//      * If there is no old process, we save the old stack pointer into a
+//      * dummy variable that we ignore.  In fact, this happens only when the
+//      * old process has just exited.
+//      */
+//     asm_switch_context(&((Process*)(current_task->real_task))->stack, old_task ? &((Process*)(old_task->real_task))->stack : &dummy);
+}
+
+void os_dispatch_mp(fw_task_t *task, int cpu)
+{
+//     (void) cpu;
+//     os_dispatch(task);
+}
+
+fw_task_t *os_current_task(int cpu){
+       (void) cpu;
+
+//     return proc_current()->fw_task;
+       return 0;
+}
+
+int os_init_os(){
+       printf("Initializing for BeRTOS...");
+
+//     heap_init(&os_heap, os_heap_buf, sizeof(os_heap_buf));
+
+       printf("done!\n");
+       return 0;
+}
+
+inline void os_spinlock(fw_spinlock_t *lock)
+{
+//     cpu_flags_t __flags; \
+//     IRQ_SAVE_DISABLE(__flags); \
+//     while(*lock){
+//             IRQ_RESTORE(__flags);
+//             CPU_IDLE;
+//             MEMORY_BARRIER;
+//             IRQ_SAVE_DISABLE(__flags);
+//     }
+//     *lock = 1;
+//     IRQ_RESTORE(__flags);
+}
+
+inline void os_spinunlock(fw_spinlock_t *lock)
+{
+//     cpu_flags_t __flags; \
+//     IRQ_SAVE_DISABLE(__flags); \
+//     *lock = 0;
+//     IRQ_RESTORE(__flags);
+}
+
+int os_task_name(fw_task_t *task, char *buf, fw_size_t size)
+{
+       return strlcpy(buf, os_task_info(task), size);
+}
+
+const char *os_task_info(fw_task_t *task){
+//     return task ? (task->real_task ? proc_name(task->real_task) : "Invalid Task") : "<NULL>";
+       return 0;
+}
diff --git a/kernel/sched/modsched/framework/os/linux/Makefile b/kernel/sched/modsched/framework/os/linux/Makefile
new file mode 100644 (file)
index 0000000..cfb2ab8
--- /dev/null
@@ -0,0 +1 @@
+obj-y += os.o
diff --git a/kernel/sched/modsched/framework/os/linux/os.c b/kernel/sched/modsched/framework/os/linux/os.c
new file mode 100644 (file)
index 0000000..f6f597c
--- /dev/null
@@ -0,0 +1,119 @@
+/*
+ * os.c
+ *
+ *  Created on: 04.12.2013
+ *      Author: jkrieg
+ */
+
+#include "os.h"
+
+
+/**
+ * CPU dependent context switching routines.
+ *
+ * Saving and restoring the context on the stack is done by a CPU-dependent
+ * support routine which usually needs to be written in assembly.
+ */
+//EXTERN_C void asm_switch_context(cpu_stack_t **new_sp, cpu_stack_t **save_sp);
+
+//HEAP_DEFINE_BUF(os_heap_buf, 1024);
+//Heap os_heap;
+
+//fw_task_t *current_task = NULL;
+
+void os_set_current_task(fw_task_t *task){
+//     current_task = task;
+       printk("current_task set to %p\n", task);
+}
+
+void *os_malloc(fw_size_t size){
+//     return heap_malloc(&os_heap, (size_t) size);
+       return 0;
+}
+
+void os_free(void* ptr)
+{
+//     heap_free(&os_heap, ptr);
+}
+
+void os_create_task(fw_task_t *task)
+{
+       (void) task;
+}
+
+void os_dispatch(fw_task_t *task)
+{
+//     cpu_stack_t *dummy;
+//
+//
+//
+//     fw_task_t *old_task;
+//     old_task = current_task;
+//
+//
+//     os_set_current_task(task);
+//
+//     os_printf("switching from '%s' (%p) to '%s' (%p)\n", os_task_info(old_task), old_task, os_task_info(current_task), current_task);
+//     os_printf("switching stack from %x (%p) &(%p) to %x (%p) &(%p)\n", *((Process*)(old_task->real_task))->stack, ((Process*)(old_task->real_task))->stack, &((Process*)(old_task->real_task))->stack, *((Process*)(current_task->real_task))->stack, ((Process*)(current_task->real_task))->stack, &((Process*)(current_task->real_task))->stack);
+//
+//     /*
+//      * If there is no old process, we save the old stack pointer into a
+//      * dummy variable that we ignore.  In fact, this happens only when the
+//      * old process has just exited.
+//      */
+//     asm_switch_context(&((Process*)(current_task->real_task))->stack, old_task ? &((Process*)(old_task->real_task))->stack : &dummy);
+}
+
+void os_dispatch_mp(fw_task_t *task, int cpu)
+{
+//     (void) cpu;
+//     os_dispatch(task);
+}
+
+fw_task_t *os_current_task(int cpu){
+       (void) cpu;
+
+//     return proc_current()->fw_task;
+       return 0;
+}
+
+int os_init_os(){
+       printk("Initializing for BeRTOS...");
+
+//     heap_init(&os_heap, os_heap_buf, sizeof(os_heap_buf));
+
+       printk("done!\n");
+       return 0;
+}
+
+inline void os_spinlock(fw_spinlock_t *lock)
+{
+//     cpu_flags_t __flags;
+//     IRQ_SAVE_DISABLE(__flags);
+//     while(*lock){
+//             IRQ_RESTORE(__flags);
+//             CPU_IDLE;
+//             MEMORY_BARRIER;
+//             IRQ_SAVE_DISABLE(__flags);
+//     }
+//     *lock = 1;
+//     IRQ_RESTORE(__flags);
+}
+
+inline void os_spinunlock(fw_spinlock_t *lock)
+{
+//     cpu_flags_t __flags;
+//     IRQ_SAVE_DISABLE(__flags);
+//     *lock = 0;
+//     IRQ_RESTORE(__flags);
+}
+
+int os_task_name(fw_task_t *task, char *buf, fw_size_t size)
+{
+       return strlcpy(buf, os_task_info(task), size);
+}
+
+const char *os_task_info(fw_task_t *task){
+//     return task ? (task->real_task ? proc_name(task->real_task) : "Invalid Task") : "<NULL>";
+       return 0;
+}
diff --git a/kernel/sched/modsched/framework/sys/Makefile b/kernel/sched/modsched/framework/sys/Makefile
new file mode 100644 (file)
index 0000000..3f6315d
--- /dev/null
@@ -0,0 +1 @@
+obj-y += fw_comm.o fw_list.o
diff --git a/kernel/sched/modsched/framework/sys/fw_comm.c b/kernel/sched/modsched/framework/sys/fw_comm.c
new file mode 100644 (file)
index 0000000..fb6bfb6
--- /dev/null
@@ -0,0 +1,43 @@
+/*
+ * fw_comm.c
+ *
+ * Simplistic Pub-Sub-System
+ *
+ *             Author: Anselm Busse, Daniel Roehrig, Christian Rene Sechting
+ */
+
+#include "fw_comm.h"
+#include "fw_list.h"
+#include "fw.h"
+
+fw_list_head_t topics[FW_LAST-FW_FIRST];
+
+struct fw_topic_element {
+       fw_list_head_t list;
+       void *callback;
+};
+
+
+void fw_subscribe(topic_t topic, void *callback)
+{
+       struct fw_topic_element *subscriber = fw_malloc(sizeof(struct fw_topic_element));
+       subscriber->callback = callback;
+       fw_list_add_tail(&subscriber->list, &topics[topic]);
+}
+
+void fw_notify(topic_t topic, void *data)
+{
+       struct fw_topic_element *iter;
+
+       fw_list_for_each_entry(iter, &topics[topic], list)
+               ((void (*)(void *))iter->callback)(data);
+}
+
+void fw_init_comm()
+{
+       int i;
+
+       for(i=FW_FIRST; i<FW_LAST; i++){
+               FW_LIST_INIT(topics[i]);
+       }
+}
diff --git a/kernel/sched/modsched/framework/sys/fw_list.c b/kernel/sched/modsched/framework/sys/fw_list.c
new file mode 100644 (file)
index 0000000..7d079c0
--- /dev/null
@@ -0,0 +1,99 @@
+#include "fw_list.h"
+#include "fw_types.h"
+
+/*
+ *     ALL LIST FUNCTIONALITIES
+ */
+
+int fw_list_empty(const fw_list_head_t *head)
+{
+       return (head->next == (fw_list_head_t*)head);
+}
+
+int fw_list_length(const fw_list_head_t *head)
+{
+       int length = 0;
+       fw_list_head_t* start;
+
+       if (fw_list_empty(head)) {
+               return 0;
+       }
+       start = head->next;
+
+       while (start != head) {
+               start = start->next;
+               length++;
+       }
+
+       return length;
+}
+
+void __fw_list_add(fw_list_head_t *_new,
+                             fw_list_head_t *prev,
+                             fw_list_head_t *next)
+{
+       next->prev = _new;
+       _new->next = next;
+       _new->prev = prev;
+       prev->next = _new;
+}
+
+void fw_list_add_tail(fw_list_head_t *_new, fw_list_head_t *head)
+{
+       __fw_list_add(_new, head->prev, head);
+}
+
+void fw_list_add_first(fw_list_head_t *_new, fw_list_head_t *head)
+{
+       __fw_list_add(_new, head, head->next);
+}
+
+void fw_list_add_at_pos(fw_list_head_t *_new, fw_list_head_t *head, int pos)
+{
+       if ((pos <= fw_list_length(head)) && (pos >= 0)) {
+               while (pos-- > 0) {
+                       head = head->next;
+               }
+               __fw_list_add(_new, head, head->next);
+       }
+       else{
+               // TODO: was is wenn pos >fw_list_length ist? hinten einfuegen?
+               fw_list_add_tail(_new, head);
+       }
+}
+
+void __fw_list_del(fw_list_head_t * prev, fw_list_head_t * next)
+{
+       next->prev = prev;
+       prev->next = next;
+}
+
+void __fw_list_del_entry(fw_list_head_t *entry)
+{
+       __fw_list_del(entry->prev, entry->next);
+}
+
+#define LIST_POISON1  ((void *) 0x00100100)
+#define LIST_POISON2  ((void *) 0x00200200)
+
+void fw_list_del(fw_list_head_t *entry)
+{
+       if (entry->next!=LIST_POISON1 && entry->prev!=LIST_POISON2)
+       {
+               __fw_list_del(entry->prev, entry->next);
+               entry->next = LIST_POISON1;
+               entry->prev = LIST_POISON2;
+       }
+}
+
+fw_list_head_t *__fw_list_pop(fw_list_head_t *head)
+{
+       fw_list_head_t *ret = head->next;
+       if (fw_list_empty(head)){
+               return NULL;
+       }
+
+       fw_list_del(ret);
+
+       return ret;
+}