sched: core: added initial sched files.

* Added files to start the development of the scheduler.
* Fixed some header bugs with current subsystems which have a potential
  dependency on the scheduler if CONFIG_SCHED is visible.

Signed-off-by: Michel Megens <dev@michelmegens.net>
irq: threads: fixed a nasty build problem

Fixed a nasty build problem between the IRQ, threading and time header,
which cause the CPP to go completely nuts.

Fix:

Moved tm_process_source from the time.h header to the time.c source
file. Causing it to become a public function and no longer a static
inline header function.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: added the rq and sched_class structures

RQ:
rq stands for 'run queue'. It contains all runnable threads for a
given CPU. Each active CPU should have a run queue initialised during
the boot process.

sched_class:
The sched_class data structure describes the scheduling algorithm. How
threads are ordered, removed, and added to run queue's.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: core: added the basics of the sched core

sched-core:
The scheduling core is the base of the scheduler, with the central
scheduling functions `schedule()' and `rq_schedule()'. These two
functions run the CPU time and are responsible for correct context
switches.

The `rq_schedule()' function takes the following actions:
	* It gets the current run queue;
	* Disables preemption;
	* Acquires the run queue lock;
	* It posts all events which have been posted from IRQ context;
	* Updates its clock source and times;
	* Checks if it has to do a context switch;
	* Switches context and enables preemption
	* Checks the NEED_RESCHED flag, and if set, runs again from step 1;

Apart from the `schedule()', the core also contains a bunch of queue
editing functions:

	* rq_add_thread
	* rq_remove_thread
	* raw_rq_add_thread
	* raw_rq_remove_thread
	* class_add_thread
	* class_remove_thread

The class_* functions add a thread to the scheduling class. All threads
have to be registered on a class (no matter if they're sleeping,
running, ready to run or waiting for a signal).

The rq_* functions add a thread to a run queue. All threads which are
ready to run or are running have to be on a run queue. All active CPU's
must have a run queue.

The raw_* functions do the same as the non raw functions, but they don't
try to acquire the run queue spin locks. These functions should only be
used from an already locked context (some parts of the scheduling core,
for example).

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: core: redisgned the kill/event queue.

The event and kill queuing has received a major overhaul, or actually -
queueing threads on run queue's in general has been completely
redisgned.

Run queue's now hold a specific RQ structure for the configured
scheduling algorithm. The round robin scheduler has `struct rr_rq' and
a deadline scheduler would get something similar, like `struct dl_rq'.
These structers hold the entity information of a run queue. The core
doesn't know, and doesn't need to know. They are driven by the
scheduling algorithm which has a uniform API, used by the sched-core,
stored in a `struct sched_class' (struct rq::sched_class).

Threads which are queued in an event mutex will be linked on the
wake_queue queue head using the rq::rq_list variable. The same is true
for threads which have to be queued to be killed, except that they use
kill_queue as a list head.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: core: fixed a potential RQ bug

The RQ pointer in the `struct thread' data structure (struct thread::rq)
was potentially being violated by kill/wake queue editing functions.
Fixed by acquiring the current run queue as their destination run queue.

If that isn't their current RQ it will be removed from their current run
queue and reassigned to the run queue of the executing CPU. This might
introduce some thread bouncing on SMP systems, but the overhead is
minimal.

The 'currently running thread' is never violated and moved to another
run queue, because it already is on the run queue of the executing CPU.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: core: fixed a rq removal bug

rq_remove_thread would run into trouble if it had to remove the
currently running thread. To do so, you need to remove the runnable mask
and set a resched mask and then request a context switch using
`schedule()'.

In the process, another bug involving the adding of threads to wake/kill
queue's got fixed. These threads shouldn't use rq_remove_thread untill
they are completely finished, because if its about the currently running
thread the context will be switched before anything useful is done.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: core: fixes on rq and thread queue's

Fixed a few issue's with thread queue's:

* Fixed up the parameter list of rq_remove_wake_thread and co. These
  functions now take an additional RQ argument (should typically only be
  the RQ of the executing CPU).
* Added thread_remove_from_wake_q, thread_remove_from_kill_q. These
  functions only function if the `struct thread::rq' pointer has been
  set. If that is not the case, these functions return silently.

* Added `raw_rq_remove_thread_noresched'. This function removes the
  given thread from the given run queue without sending any reschedule
  signals in any case. Should be used in functions editing the Q of
  another CPU or when editing queue's without interruption is required.

Added the a basic priority round robin scheduler

* No dynamic priorities yet.
* Queue's are sorted with increasing priority (most important threads
  first).
* All inteface functions assume that the correct locks have been
  acquired (or interrupts have been disabled).

Spinlocks:

* Added raw spinlock calls. These calls wont cause a (possible)
  preemption (not yet implemented).

Signed-off-by: Michel Megens <dev@michelmegens.net>
usr: schedtest: added a scheduling unit test

Unit test to test the functionality of the scheduler.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: core: added ifdefs for event mutexes.

Added ifdefs around event mutex specific code. Temporarily disabled the
these same ifdefs (CONFIG_EVENT_MUTEX) in the mutex header, has the
mutexes are far from ready to use. The standard mutexes should be used
untill they are the event based ones are mainlined.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: core: added irqsave to spinlocks

Spin locks:
Changed most spinlocks from spin_lock and spin_unlock to
spin_lock_irqsave and spin_unlock_irqrestore respectively. Spin locks
which have been changed are about to edit the queue pointers of a run
queue and interrupts might change these aswell (event signals etc..).
Therefore, when editing these queue's interrupts should be excluded.

Thread queue's:
Added thread queue's as a build option to Kconfig. Thread queue's are
required by event mutexes, but otherwise they should be an optional
feature which can be picked if preferred.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: core: added evm signal function

rq_signal_event_queue:
This function signals the queue of a thread if it has been signaled by
an IRQ (i.e. struct thread::ec has been incremented). This function is
called by rq_schedule to handle evm's (Event Mutexes).

raw_rq_add_thread:
Removed this bit of code:

if(tp->on_rq && test_bit(THREAD_RUNNING_FLAG, &tp->flags))
	err = raw_rq_remove_thread_noresched(tp->rq, tp);

It would create a massive bug on SMP systems if you were to try and add
a thread to a run queue while its on the run queue of another CPU.
Moving threads to other run queue's should be done by the IDLE balancer
only.
Changed the return value from `int' to `void'.

raw_queue_remove_thread:
Removed:

if(test_bit(THREAD_RUNNING_FLAG, &tp->flags))
	raw_rq_add_thread(sched_get_cpu_rq(), tp)

It was causing trouble for event queue's. Readding threads which come
off an event queue should be readded manually at all times. Also changed
the return value of raw_queue_remove_thread from `int' to `void'.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: core: fixed an empty run queue bug.

If the run queue was empty (i.e. the IDLE thread is running), it would
try to run a NULL pointer thread. Fixed by setting the next thread to
struct rq::current if sched_class::next_runnable returns NULL.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: avr: implemented the AVR context switch

Implemented the context switching mechanism for the AVR architecture.
The sched::core calls cpu_reschedule, a function prototype implemented
specifically by each architecture. In the case of AVR, this function
disables interrupts, calls avr_switch_context and re-enables interrupts.

avr_switch_context is implemented in arch/avr/kernel/context.S. It
pushes all registers to the stack and saves the stack on the correct
(current) stack structure. Then, the new stack is loaded into the stack
registers and all registers are popped from the stack and the 'ret'
instruction will take the IP back to where it finished before this
thread was scheduled out.

timer: exec: fixed a small bug in the timer execution.

The `struct timer::tc_resume' was never being set correctly, which
prevent the timers to execute with the right time frames. Non-oneshot
timers also had a lock bug. Fixed by temporarily unlocking.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: core: implemented partial preemption.

With preemption enabled, threads now have a time slice which will be
checked every time the `schedule()' function is called. If the time
slice is over, THREAD_NEED_RESCHED_FLAG is set and the slice is reset to
CONFIG_TIME_SLICE (defaults to 5ms).

`sleep()':
Use sleep to sleep a thread for given amount of time (in ms). The thread
is returned to the run queue when that amount of time is over.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: core: added dynamic priorities

Added dynamic priorities to increase the likely hood of fair scheduling.
Everytime a task is succesfully switched, the dynamic priorities of
other tasks get incremented. After a while, the priorities of verry low
priority threads will be really high, to ensure CPU time.

Also fixed some build errors with preemption disabled.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: core: abstracted the main stack pointer.

The main stack pointer is from now on provided by the architecture,
since it might be able to reuse its old main stack after the idle thread
is running. This stack isn't used on AVR after sched_init and can be
reused without issues.

Signed-off-by: Michel Megens <dev@michelmegens.net>
avr: init: fixed a big memory related bug.

When not using `kzalloc' you MUST initialise EVERY data field of a
structure, or it will be undefined. This happend in the thread creation
process and caused a nasty bug in the scheduler.

Fix:
* Implemented memset in the standard string library (TODO: optimize).
* Implemented kzalloc in include/mem.h

`kzalloc' uses memset if the stardard string library is being build, if
not, it uses its own (slow) algorithm to zero out the allocated memory.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: evm: added event mutex handling

EVM's are a mutex policy based on the scheduler. All threads trying to
enter an EVM while it's locked are removed from the run queue and placed
onto a special thread_queue, unique to that mutex. Once the mutex
receives a signal, the next thread ('next' is defined by the system
sched class) is removed from the queue and executed.

Signed-off-by: Michel Megens <dev@michelmegens.net>
sched: evm: added support for event queue mutexes.

Event queue mutexes are mutexes with more overhead on locking and
unlocking. Whats the point, you might wonder. The point of using them
over spinlocks, is that they give up control over the CPU when they
enter a locking state. In other words, it is taking 'aquiring a
deadlock' to a whole new level, which is a good thing. It also frees up
CPU time for other threads, which would otherwise be waiting for a
thread doing nothing but waiting on a lock to get released.

Signed-off-by: Michel Megens <dev@michelmegens.net>