qa6B2YXq

1/*! \file kernel.c
2 *  \brief
3 *  This is the main source code for the kernel. Here all important variables
4 *  will be initialized.
5 */
6
7#include "kernel.h"
8#include "threadqueue.h"
9#include "mm.h"
10#include "sync.h"
11
12/* Note: Look in kernel.h for documentation of global variables and
13 functions. */
14
15/* Variables */
16volatile unsigned int screen_lock = 0;
17
18union thread thread_table[MAX_NUMBER_OF_THREADS];
19
20volatile unsigned int thread_table_lock = 0;
21
22struct process process_table[MAX_NUMBER_OF_PROCESSES];
23
24volatile unsigned int process_table_lock = 0;
25
26struct thread_queue ready_queue;
27
28volatile unsigned int ready_queue_lock = 0;
29/*!< Spin lock used to ensure mutual exclusion to the ready queue. */
30
31struct CPU_private CPU_private_table[MAX_NUMBER_OF_CPUS];
32
33
34// ### changed
35struct QH{
36	unsigned int load;
37	struct thread_queue running_queue;
38	struct thread_queue next_queue;
39};
40
41struct QH que_handle[MAX_NUMBER_OF_CPUS];
42
43volatile unsigned int que_handle_lock = 0;
44
45
46
47int number_of_available_CPUs = 0;
48
49volatile int number_of_initialized_CPUs = 0;
50
51struct IO_APIC IO_APIC;
52
53volatile unsigned int CPU_private_table_lock = 0;
54
55unsigned int pic_interrupt_map[16];
56
57static struct executable executable_table[MAX_NUMBER_OF_PROCESSES];
58/*!< Array holding descriptions of all executable programs. */
59
60static int executable_table_size = 0;
61/*!< The number of executable programs in the executable_table */
62
63/* Initialize the timer queue to be empty. */
64int timer_queue_head = -1;
65
66volatile unsigned int timer_queue_lock = 0;
67
68/* Initialize the system time to be 0. */
69volatile long system_time = 0;
70
71const unsigned char BSP_APIC_id;
72
73void* AP_boot_stack;
74
75unsigned int GS_base;
76
77unsigned int TSS_selector;
78
79/*! Size of the keyboard scan code buffer. */
80#define KEYBOARD_BUFFER_SIZE 16
81
82/*! Buffer which holds the keyboard scan codes coming from the keyboard
83 interrupt handler. */
84static unsigned char keyboard_scancode_buffer[KEYBOARD_BUFFER_SIZE];
85
86/*! Low water mark for the scan code buffer. */
87static int keyboard_scancode_low_marker = 0;
88
89/*! High water mark for the scan code buffer. */
90static int keyboard_scancode_high_marker = 0;
91
92/*! List of threads blocked waiting for scan codes. */
93struct thread_queue keyboard_blocked_threads;
94
95volatile int keyboard_scancode_buffer_lock = 0;
96/*!< Spin lock used to ensure mutual exclusion to the keyboard scan code
97 buffer. */
98
99/*! Points to the first byte after the area where the kernel stacks are
100 located.  */
101extern char kernel_stack_base[1];
102
103/* Function definitions */
104
105/*! Helper struct that is used to return values from prepare_process. */
106struct prepare_process_return_value {
107	unsigned long first_instruction_address
108	/*!< The address of the first instruction in the prepared process image. */;
109	unsigned long page_table_address
110	/*!< The address of the page table tree set up for the process. */;
111};
112
113/*! Copies an ELF image to memory and prepares a process. prepare_process
114 does some checks to avoid that corrupt images gets copied to memory.
115 However, the checks are not as thorough as the check in initialize.
116 \return A prepare_process_return_value struct holding the first address
117 of the process image and an address to the page table for
118 the process. */
119static struct prepare_process_return_value prepare_process(const struct Elf64_Ehdr* elf_image
120/*!< Points to the ELF image to copy. */, const unsigned int process
121/*!< The index of the process that is to be created. */, unsigned long memory_footprint_size
122/*!< Holds the maximum amount of memory, in bytes,
123 the image is allowed to use. */) {
124	/* Get the address of the program header table. */
125	int program_header_index;
126	struct Elf64_Phdr* program_header = ((struct Elf64_Phdr*) (((char*) (elf_image)) + elf_image->e_phoff));
127	unsigned long used_memory = 0;
128
129	/* Allocate memory for the page table and for the process' memory. All of
130	 this is allocated in a single memory block. The memory block is set up so
131	 that it cannot be de-allocated via kfree. */
132	long address_to_memory_block = kalloc(memory_footprint_size + 19 * 4 * 1024, process, ALLOCATE_FLAG_KERNEL);
133
134	struct prepare_process_return_value ret_val = { 0, 0 };
135
136	/* First check that we have enough memory. */
137	if (0 >= address_to_memory_block) {
138		/* No, we don't. */
139		return ret_val;
140	}
141
142	ret_val.page_table_address = address_to_memory_block;
143
144	{
145		/* Create a page table for the process. */
146		unsigned long* dst = (unsigned long*) address_to_memory_block;
147		unsigned long* src = (unsigned long*) (kernel_page_table_root + 3 * 4 * 1024);
148		register int i;
149
150		/* Clear the first frames. */
151		for (i = 0; i < 3 * 4 * 1024 / 8; i++) {
152			*dst++ = 0;
153		}
154
155		/* Build the pml4 table. */
156		dst = (unsigned long*) (address_to_memory_block);
157		*dst = (address_to_memory_block + 4096) | 7;
158
159		/* Build the pdp table. */
160		dst = (unsigned long*) (address_to_memory_block + 4096);
161		*dst = (address_to_memory_block + 2 * 4096) | 7;
162		/* Copy the APIC mapping. */
163		*(dst + 3) = *((unsigned long*) (kernel_page_table_root + 4096 + 24));
164
165		/* Build the pd table. */
166		dst = (unsigned long*) (address_to_memory_block + 2 * 4096);
167		for (i = 0; i < 16; i++) {
168			*dst++ = (address_to_memory_block + (3 + i) * 4096) | 7;
169		}
170
171		/* Copy the rest of the kernel page table. */
172		dst = (unsigned long*) (address_to_memory_block + 3 * 4 * 1024);
173		for (i = 0; i < (16 * 1024 * 4 / 8); i++) {
174			*dst++ = *src++;
175		}
176	}
177
178	/* Update the start of the block to be after the page table. */
179
180	address_to_memory_block += 19 * 4 * 1024;
181
182	/* Scan through the program header table and copy all PT_LOAD segments to
183	 memory. Perform checks at the same time.*/
184
185	for (program_header_index = 0; program_header_index < elf_image->e_phnum; program_header_index++) {
186		if (PT_LOAD == program_header[program_header_index].p_type) {
187			/* Calculate destination adress. */
188			unsigned long* dst = (unsigned long *) (address_to_memory_block + used_memory);
189
190			/* Check for odd things. */
191			if (
192			/* Check if the segment is contiguous */
193			(used_memory != program_header[program_header_index].p_vaddr) ||
194			/* Check if the segmen fits in memory. */
195			(used_memory + program_header[program_header_index].p_memsz > memory_footprint_size) ||
196			/* Check if the segment has an odd size. We require the segment
197			 size to be an even multiple of 8. */
198			(0 != (program_header[program_header_index].p_memsz & 7))
199					|| (0 != (program_header[program_header_index].p_filesz & 7))) {
200				/* Something went wrong. Panic. */
201				while (1) {
202					kprints("Kernel panic: Trying to create a process out of a corrupt executable image!");
203				}
204			}
205
206			/* First copy p_filesz from the image to memory. */
207			{
208				/* Calculate the source address. */
209				unsigned long* src = (unsigned long *) (((char*) elf_image)
210						+ program_header[program_header_index].p_offset);
211				unsigned long count = program_header[program_header_index].p_filesz / 8;
212
213				for (; count > 0; count--) {
214					*dst++ = *src++;
215				}
216			}
217
218			/* Then write p_memsz-p_filesz bytes of zeros. This to pad the segment. */
219			{
220				unsigned long count = (program_header[program_header_index].p_memsz
221						- program_header[program_header_index].p_filesz) / 8;
222
223				for (; count > 0; count--) {
224					*dst++ = 0;
225				}
226			}
227
228			/* Set the permission bits on the loaded segment. */
229			update_memory_protection(ret_val.page_table_address,
230					program_header[program_header_index].p_vaddr + address_to_memory_block,
231					program_header[program_header_index].p_memsz, program_header[program_header_index].p_flags & 7);
232
233			/* Finally update the amount of used memory. */
234			used_memory += program_header[program_header_index].p_memsz;
235		}
236	}
237
238	/* Find out the address to the first instruction to be executed. */
239	ret_val.first_instruction_address = address_to_memory_block + elf_image->e_entry;
240
241	return ret_val;
242}
243
244/*! This is the last thing that is run when a process terminates. */
245static void cleanup_process(const int process /*!< The index, into process_table, of the
246 terminating process. */) {
247	register unsigned int i;
248
249	/* Obtain exclusive access to the page_frame_table. */
250	grab_lock_rw(&page_frame_table_lock);
251
252	for (i = 0; i < memory_pages; i++) {
253		if (page_frame_table[i].owner == process) {
254			page_frame_table[i].owner = -1;
255			page_frame_table[i].free_is_allowed = 1;
256		}
257	}
258
259	release_lock(&page_frame_table_lock);
260}
261
262void send_IPI(register unsigned char const destination_processor_index, register unsigned int const vector) {
263	/* Get address to local APIC. */
264	register unsigned int const processor_index = get_processor_index();
265	register volatile unsigned int* const APIC_base_address = (unsigned int*) ((CPU_private_table[processor_index].apic_phys_address) & 0xffffffffULL);
266	/* Set destination. */
267	*(APIC_base_address + 0x310 / 4) = CPU_private_table[destination_processor_index].local_apic_id << (56 - 32);
268	/* And send interrupts. */
269	*(APIC_base_address + 0x300 / 4) = vector & 0xff;
270}
271
272/*! Initialize the local APIC for the current CPU. */
273void initialize_APIC(void) {
274	/* Get address to local APIC and the number of LVTs. */
275	register unsigned int const processor_index = get_processor_index();
276	register volatile unsigned int* const APIC_base_address =
277			(unsigned int*) ((CPU_private_table[processor_index].apic_phys_address) & 0xffffffffULL);
278	register unsigned int max_lvt_entries = (*(APIC_base_address + 0x30 / sizeof(unsigned int)) >> 16) & 0xff;
279
280	while (5 != max_lvt_entries) {
281		kprints("PANIC: APIC configuration not supported.\n");
282	}
283
284	/* Make sure the APIC is enabled. */
285	*(APIC_base_address + 0xf0 / sizeof(unsigned int)) |= 0x100;
286
287	/* Set task priority. */
288	*(APIC_base_address + 0x80 / sizeof(unsigned int)) = 0;
289
290	/* Mask all local sources. */
291	*(APIC_base_address + 0x320 / sizeof(unsigned int)) |= 0x10000;
292	*(APIC_base_address + 0x330 / sizeof(unsigned int)) |= 0x10000;
293	*(APIC_base_address + 0x340 / sizeof(unsigned int)) |= 0x10000;
294	*(APIC_base_address + 0x350 / sizeof(unsigned int)) |= 0x10000;
295	*(APIC_base_address + 0x360 / sizeof(unsigned int)) |= 0x10000;
296	*(APIC_base_address + 0x370 / sizeof(unsigned int)) |= 0x10000;
297
298	number_of_initialized_CPUs++;
299}
300
301static unsigned int read_io_apic_register(register unsigned int const register_number) {
302	volatile unsigned int * const io_apic_address = (unsigned int*) IO_APIC.ioapic_phys_address;
303
304	*io_apic_address = register_number;
305
306	return (*(io_apic_address + 16 / sizeof(unsigned int)));
307}
308
309static void write_io_apic_register(register unsigned int const register_number, register unsigned int const value) {
310	volatile unsigned int * const io_apic_address = (unsigned int*) IO_APIC.ioapic_phys_address;
311
312	*io_apic_address = register_number;
313
314	*(io_apic_address + 16 / sizeof(unsigned int)) = value;
315}
316
317void initialize(void) {
318	register int i;
319
320	/* Loop over all threads in the thread table and reset the owner. */
321	for (i = 0; i < MAX_NUMBER_OF_THREADS; i++) {
322		/* -1 is an illegal process_table index. We use that to show that the thread is dormant. */
323		thread_table[i].data.owner = -1;
324	}
325
326	/* Loop over all processes in the thread table and mark them as not executing. */
327	for (i = 0; i < MAX_NUMBER_OF_PROCESSES; i++) {
328		process_table[i].threads = 0; /* No executing process has less than 1
329		 thread. */
330	}
331
332	/* Initialize the CPU_private_table. */
333	for (i = 0; i < MAX_NUMBER_OF_CPUS; i++) {
334		CPU_private_table[i].stack = (unsigned long long) &kernel_stack_base[-i * 2 * 4096];
335		CPU_private_table[i].page_table_root = kernel_page_table_root;
336		CPU_private_table[i].thread_index = -1;
337		CPU_private_table[i].CPU_index = i;
338		CPU_private_table[i].ticks_left_of_time_slice = 1;
339// ### changed
340		/* Initialize CPU queues */
341		que_handle[i].load = 0;
342		thread_queue_init(&que_handle[i].running_queue);
343		thread_queue_init(&que_handle[i].next_queue);
344	}
345
346	// TODO: Delete global ready que
347	/* Initialize the ready queue. */
348	thread_queue_init(&ready_queue);
349
350	/* Initialize the list of blocked threads waiting for the keyboard. */
351	thread_queue_init(&keyboard_blocked_threads);
352
353	/* Calculate the number of pages. */
354	memory_pages = memory_size / (4 * 1024);
355
356	/* Check if the number of pages is larger than the size of the page frame
357	 table. */
358	if (MAX_NUMBER_OF_FRAMES < memory_pages) {
359		memory_pages = MAX_NUMBER_OF_FRAMES;
360	}
361
362	{
363		/* Calculate the number of frames occupied by the kernel and executable images. */
364		const register int k = first_available_memory_byte / (4 * 1024);
365
366		/* Mark the pages that are used by the kernel or executable images as taken
367		 by the kernel (-2 in the owner field). */
368		for (i = 0; i < k; i++) {
369			page_frame_table[i].owner = -2;
370			page_frame_table[i].free_is_allowed = 0;
371		}
372
373		/* Loop over all the rest page frames and mark them as free (-1 in owner
374		 field). */
375		for (i = k; i < memory_pages; i++) {
376			page_frame_table[i].owner = -1;
377			page_frame_table[i].free_is_allowed = 1;
378		}
379
380		/* Mark any unusable pages as taken by the kernel. */
381		for (i = memory_pages; i < MAX_NUMBER_OF_FRAMES; i++) {
382			page_frame_table[i].owner = -2;
383			page_frame_table[i].free_is_allowed = 0;
384		}
385	}
386
387	/* Go through the linked list of executable images and verify that they
388	 are correct. At the same time build the executable_table. */
389	{
390		register int image_index;
391
392		for (image_index = 0; 0 != ELF_images[image_index]; image_index++) {
393			/* Check that the image is an ELF image and that it is of the
394			 right type. */
395			if (
396			/* EI_MAG0 - EI_MAG3 have to be 0x7f 'E' 'L' 'F'. */
397			(ELF_images[image_index]->e_ident[EI_MAG0] != 0x7f) || (ELF_images[image_index]->e_ident[EI_MAG1] != 'E')
398					|| (ELF_images[image_index]->e_ident[EI_MAG2] != 'L')
399					|| (ELF_images[image_index]->e_ident[EI_MAG3] != 'F') ||
400			/* Check that the image is a 64-bit image. */
401			(ELF_images[image_index]->e_ident[EI_CLASS] != 2) ||
402			/* Check that the image is a little endian image. */
403			(ELF_images[image_index]->e_ident[EI_DATA] != 1) ||
404			/* And that the version of the image format is correct. */
405			(ELF_images[image_index]->e_ident[EI_VERSION] != 1) ||
406			/* NB: We do not check the ABI or ABI version. We really should
407			 but currently those fields are not set properly by the build
408			 tools. They are both set to zero which means: System V ABI,
409			 third edition. However, the ABI used is clearly not System V :-) */
410
411			/* Check that the image is executable. */
412			(ELF_images[image_index]->e_type != 2) ||
413			/* Check that the image is executable on AMD64. */
414			(ELF_images[image_index]->e_machine != 0x3e) ||
415			/* Check that the object format is corrent. */
416			(ELF_images[image_index]->e_version != 1) ||
417			/* Check that the processor dependent flags are all reset. */
418			(ELF_images[image_index]->e_flags != 0) ||
419			/* Check that the length of t   he header is what we expect. */
420			(ELF_images[image_index]->e_ehsize != sizeof(struct Elf64_Ehdr)) ||
421			/* Check that the size of the program header table entry is what
422			 we expect. */
423			(ELF_images[image_index]->e_phentsize != sizeof(struct Elf64_Phdr)) ||
424			/* Check that the number of entries is reasonable. */
425			(ELF_images[image_index]->e_phnum < 0) || (ELF_images[image_index]->e_phnum > 8) ||
426			/* Check that the entry point is within the image. */
427			(ELF_images[image_index]->e_entry < 0))
428
429			{
430				/* There is something wrong with the image. */
431				while (1) {
432					kprints("Kernel panic! Corrupt executable image.\n");
433				}
434				continue;
435			}
436
437			/* Now check the program header table. */
438			{
439				int program_header_index;
440				struct Elf64_Phdr* program_header = ((struct Elf64_Phdr*) (((char*) (ELF_images[image_index]))
441						+ ELF_images[image_index]->e_phoff));
442				unsigned long memory_footprint_size = 0;
443
444				for (program_header_index = 0; program_header_index < ELF_images[image_index]->e_phnum;
445						program_header_index++) {
446					/* First sanity check the entry. */
447					if (
448					/* Check that the segment is a type we can handle. */
449					(program_header[program_header_index].p_type < 0)
450							|| (!((program_header[program_header_index].p_type == PT_NULL)
451									|| (program_header[program_header_index].p_type == PT_LOAD)
452									|| (program_header[program_header_index].p_type == PT_PHDR)))
453							||
454							/* Look more carefully into loadable segments. */
455							((program_header[program_header_index].p_type == PT_LOAD)
456									&&
457									/* Check if any flags that we can not handle is set. */
458									(((program_header[program_header_index].p_flags & ~7) != 0) ||
459									/* Check if sizes and offsets look sane. */
460									(program_header[program_header_index].p_offset < 0)
461											|| (program_header[program_header_index].p_vaddr < 0)
462											|| (program_header[program_header_index].p_filesz < 0)
463											|| (program_header[program_header_index].p_memsz < 0) ||
464									/* Check if the segment has an odd size. We require the
465									 segement size to be an even multiple of 8. */
466									(0 != (program_header[program_header_index].p_memsz & 7))
467											|| (0 != (program_header[program_header_index].p_filesz & 7))))) {
468						while (1) {
469							kprints("Kernel panic! Corrupt segment.\n");
470						}
471					}
472
473					/* Check that all PT_LOAD segments are contiguous starting from
474					 address 0. Also, calculate the memory footprint of the image. */
475					if (program_header[program_header_index].p_type == PT_LOAD) {
476						if (program_header[program_header_index].p_vaddr != memory_footprint_size) {
477							while (1) {
478								kprints("Kernel panic! Executable image has illegal memory layout.\n");
479							}
480						}
481
482						memory_footprint_size += program_header[program_header_index].p_memsz;
483					}
484				}
485
486				executable_table[executable_table_size].memory_footprint_size = memory_footprint_size;
487			}
488
489			executable_table[executable_table_size].elf_image = ELF_images[image_index];
490			executable_table_size += 1;
491
492			kprints("Found an executable image.\n");
493
494			if (executable_table_size >= MAX_NUMBER_OF_PROCESSES) {
495				while (1) {
496					kprints("Kernel panic! Too many executable images found.\n");
497				}
498			}
499		}
500	}
501
502	/* Check that actually some executable files are found. Also check that the
503	 thread structure is of the right size. The assembly code will break if it
504	 is not. */
505
506	if ((0 >= executable_table_size) || (1024 != sizeof(union thread))) {
507		while (1) {
508			kprints("Kernel panic! Can not boot.\n");
509		}
510	}
511
512	/* Copy the application processor bootstrap code into place. */
513	{
514		register char* dst = (char*) 0x10000;
515		register const char* src = start_application_processor;
516
517		for (; src < start_application_processor_end;) {
518			*dst++ = *src++;
519		}
520	}
521
522	initialize_memory_protection();
523	initialize_thread_synchronization();
524
525	/* All sub-systems are now initialized. Kernel areas can now get the right
526	 memory protection. */
527
528	{
529		/* Use the kernel's ELF header. */
530		struct Elf32_Phdr* program_header = ((struct Elf32_Phdr*) (((char*) (0x00100000))
531				+ ((struct Elf32_Ehdr*) 0x00100000)->e_phoff));
532
533		/* Traverse the program header. */
534		short number_of_program_header_entries = ((struct Elf32_Ehdr*) 0x00100000)->e_phnum;
535		int i;
536		for (i = 0; i < number_of_program_header_entries; i++) {
537			if (PT_LOAD == program_header[i].p_type) {
538				/* Set protection on each segment. */
539
540				update_memory_protection(kernel_page_table_root, program_header[i].p_vaddr, program_header[i].p_memsz,
541						(program_header[i].p_flags & 7) | PF_KERNEL);
542			}
543		}
544
545		/* Set the protection for the bootstrap code. */
546		update_memory_protection(kernel_page_table_root, 0x10000, 4096, PF_X | PF_R | PF_KERNEL);
547
548		/* Reload the kernel page table. */
549		__asm volatile("movq %0,%%cr3" : :
550				"r" (kernel_page_table_root));
551	}
552
553	/* Now we set up the 8259A interrupt controller to not send interrupts. */
554	outb(0x20, 0x11);
555	outb(0xA0, 0x11);
556
557	outb(0x21, 0x20);
558	outb(0xA1, 0x28);
559
560	outb(0x21, 1 << 2);
561	outb(0xA1, 2);
562
563	outb(0x21, 1);
564	outb(0xA1, 1);
565
566	outb(0x21, 0xff);
567	outb(0xA1, 0xff);
568
569	/* Set up the timer hardware to generate interrupts 200 times a second. */
570	outb(0x43, 0x36);
571	outb(0x40, 78);
572	outb(0x40, 23);
573
574	/* Initialize IO APIC disabling all interrupts. */
575	{
576		register int i;
577		for (i = 0; i < 24; i++) {
578			register unsigned int const io_apic_low_bits = read_io_apic_register(0x10 + 2 * i);
579			write_io_apic_register(0x10 + 2 * i, io_apic_low_bits | 0x10000);
580		}
581	}
582
583	/* Route NMIs and 8259 interrupts through the APIC. */
584	outb(0x22, 0x70);
585	outb(0x23, 1);
586
587	/* Bootstrap all processors. */
588	{
589		register int processor_index;
590		register volatile unsigned int* const APIC_base_address =
591				(unsigned int*) ((CPU_private_table[0].apic_phys_address) & 0xffffffffULL);
592
593		/* The ACPI spec says the first entry has to be the bootstrap processor. */
594		while (BSP_APIC_id != CPU_private_table[0].local_apic_id) {
595			kprints("Kernel panic! ACPI information not correct.\n");
596		}
597
598		initialize_APIC();
599		number_of_initialized_CPUs = 1;
600
601		kprints("BSP initialized.\n");
602
603		for (processor_index = 1; processor_index < number_of_available_CPUs; processor_index++) {
604			/* Set up information to be sent to the application processor boot strap. */
605
606			TSS_selector = 40 + processor_index * 16;
607			GS_base = (unsigned int) (((unsigned long) (&CPU_private_table[processor_index])) & 0xffffffff);
608			AP_boot_stack = &kernel_stack_base[-processor_index * 2 * 4096];
609
610			kprints("Attempting to start AP \0");
611
612			/* Application processor. Send IPI to wake it up. */
613
614			/*! \todo The SIPI procedure is not bullet proof. It works with bochs but
615			 to be fully working on all CPU types and revisions there should be a
616			 timeout and a second try if the first does not work. */
617
618			kprinthex(CPU_private_table[processor_index].local_apic_id);
619			kprints(".\n\0");
620
621			/* Send INIT command. */
622			*(APIC_base_address + 0x310 / 4) = CPU_private_table[processor_index].local_apic_id << (56 - 32);
623			*(APIC_base_address + 0x300 / 4) = 0x510;
624
625			/* Pause for a moment, using busy loop and CPU0's APIC timer. */
626			{
627				/* Set divider to 2. */
628				*(APIC_base_address + 0x3e0 / 4) = 0x00;
629
630				/* Set initial count */
631				*(APIC_base_address + 0x380 / 4) = 1000000;
632
633				while (*(APIC_base_address + 0x390 / 4) > 0)
634					;
635			}
636
637			/* Send SIPI. */
638			*(APIC_base_address + 0x300 / 4) = 0x610;
639
640			/* Spin until the application processor is woken up. */
641			while ((processor_index + 1) != number_of_initialized_CPUs)
642				;
643
644			kprints("AP initialized.\n\0");
645		}
646	}
647
648	/* Start running the first program in the executable table. */
649
650	/* Use the ELF program header table and copy the right portions of the
651	 image to memory. This is done by prepare_process. */
652
653	{
654		struct prepare_process_return_value prepare_process_ret_val = prepare_process(executable_table[0].elf_image, 0,
655				executable_table[0].memory_footprint_size);
656
657		if (0 == prepare_process_ret_val.first_instruction_address) {
658			while (1) {
659				kprints("Kernel panic! Can not start process 0!\n");
660			}
661		}
662
663		/* Start executable program 0 as process 0. At this point, there are no
664		 processes so we can just grab entry 0 and use it. */
665		process_table[0].parent = -1; /* We put -1 to indicate that there is no
666		 parent process. */
667		process_table[0].threads = 1;
668
669		/* Set the page table address. */
670		process_table[0].page_table_root = prepare_process_ret_val.page_table_address;
671		CPU_private_table[0].page_table_root = prepare_process_ret_val.page_table_address;
672
673		/* We need a thread. We just take the first one as no threads are running or
674		 have been allocated at this point. */
675		thread_table[0].data.owner = 0; /* 0 is the index of the first process. */
676
677		/* We reset all flags and enable interrupts */
678		thread_table[0].data.registers.integer_registers.rflags = 0x200;
679
680		/* And set the start address. */
681		thread_table[0].data.registers.integer_registers.rip = prepare_process_ret_val.first_instruction_address;
682
683		/* Finally we set the current thread. */
684		CPU_private_table[0].thread_index = 0;
685
686		/* Set the CPU load */
687		que_handle[0].load = 1;
688		kprints("CPU: "); kprinthex(get_processor_index());
689		kprints(" Created thread:    "); kprinthex(get_current_thread());
690		kprints(" with load: "); kprinthex(que_handle[get_processor_index()].load); kprints("\n");
691	}
692
693	/* Set up the keyboard controller. */
694
695	/* Empty the keyboard buffer. */
696	{
697		register unsigned char status_byte;
698		do {
699			status_byte = inb(0x64);
700			if ((status_byte & 3) == 1) {
701				inb(0x60);
702			}
703		} while ((status_byte & 0x3) != 0x0);
704	}
705
706	/* Change the command byte to enable interrupts. */
707	outb(0x64, 0x20);
708	{
709		register unsigned char keyboard_controller_command_byte;
710
711		{
712			register unsigned char status_byte;
713			do {
714				status_byte = inb(0x64);
715			} while ((status_byte & 3) != 1);
716		}
717
718		keyboard_controller_command_byte = inb(0x60);
719
720		/* Enable keyboard interrupts. */
721		keyboard_controller_command_byte |= 1;
722
723		kprints("Keyboard controller command byte:");
724		kprinthex(keyboard_controller_command_byte);
725		kprints("\n");
726
727		outb(0x64, 0x60);
728		outb(0x60, keyboard_controller_command_byte);
729
730		/* Wait until command is done. */
731		{
732			register unsigned char status_byte;
733			do {
734				status_byte = inb(0x64);
735			} while ((status_byte & 0x2) != 0x0);
736		}
737	}
738
739	clear_screen();
740	kprints("\n\n\nThe kernel has booted!\n\n\n");
741	/* Enable timer and keyboard interrupts. */
742
743	{
744		register int timer_gsi = pic_interrupt_map[0];
745		/* Send timer interrupts to all cpus. */
746		write_io_apic_register(0x11 + timer_gsi * 2, 0xff000000);
747		write_io_apic_register(0x10 + timer_gsi * 2, 0x00000020);
748	}
749
750	{
751		register int keyboard_gsi = pic_interrupt_map[1];
752		/* Send keyboard interrupts to the BSP. */
753		write_io_apic_register(0x11 + keyboard_gsi * 2, CPU_private_table[0].local_apic_id << 24);
754		write_io_apic_register(0x10 + keyboard_gsi * 2, 0x00000021);
755	}
756	/* Now go back to the assembly language code and let the process run. */
757}
758
759/*! Allocate one thread. The allocated thread is not initialized.
760 Rip and rflags need to be set for the thread to start properly.
761
762 Callers of this function must ensure that the thread_table is locked
763 for reading for the duration of the call.
764
765 \return An index into thread_table or -1 if no thread could be allocated.
766 */
767static inline int allocate_thread(void) {
768
769	register int i;
770	/* loop over all threads and find a free thread. */
771	for (i = 0; i < MAX_NUMBER_OF_THREADS; i++) {
772		/* An owner index of -1 means that the thread is available. */
773		if (-1 == thread_table[i].data.owner) {
774			return i;
775		}
776	}
777	/* We return -1 to indicate that there are no available threads. */
778	return -1;
779}
780
781/* Insert thread on the current CPU while
782 * distributing work load among the available CPUs */
783static inline void insert_thread(unsigned const int thread){
784
785	int cpu = get_processor_index();
786
787	/* Enqueue the thread on the current CPU */
788	thread_queue_enqueue(&que_handle[cpu].next_queue, thread);
789
790	/* Increment the CPU's load */
791	que_handle[cpu].load++;
792	kprints("CPU: "); kprinthex(cpu);
793	kprints(" Created thread:    "); kprinthex(thread);
794	kprints(" with load: "); kprinthex(que_handle[cpu].load); kprints("\n");
795
796	/* If "high" load */
797	if (que_handle[cpu].load > 1) {
798		/* Test if idle CPU */
799		int idle_CPU;
800		for (idle_CPU = 0; idle_CPU < number_of_available_CPUs; ++idle_CPU) {
801			/* Find a CPU with lesser load (i.e. no load here) */
802			if (que_handle[idle_CPU].load == 0) {
803				/* Poke one idle CPU */
804				//send_IPI(idle_CPU, 241);
805				kprints("Poke Poke CPU: "); kprinthex(idle_CPU); kprints(" its your turn to work!\n");
806				break;
807			}
808		}
809	}
810}
811
812
813extern void system_call_handler(void) {
814	register int schedule = 0;
815	/*!< System calls may set this variable to 1. The variable is used as
816	 input to the scheduler to indicate that scheduling is not necessary. */
817
818	/* Reset the interrupt flag indicating that the context of the caller was
819	 saved by the system call routine. */
820	thread_table[get_current_thread()].data.registers.from_interrupt = 0;
821
822	switch (SYSCALL_ARGUMENTS.rax) {
823	case SYSCALL_PAUSE: {
824		register int tmp_thread_index;
825		unsigned long timer_ticks = SYSCALL_ARGUMENTS.rdi;
826
827		/* Set the return value before doing anything else. We will switch to a new
828		 thread very soon! */
829		SYSCALL_ARGUMENTS.rax = ALL_OK;
830
831		if (0 == timer_ticks) {
832			/* We should not wait if the rdi register is 0. */
833			break;
834		}
835
836		/* Get the current thread. */
837		tmp_thread_index = get_current_thread();
838
839		/* Force a re-schedule. */
840		schedule = 1;
841
842		/* And insert the thread into the timer queue. */
843
844		/* The timer queue is a linked list of threads. The head (first entry)
845		 (thread) in the list has a list_data field that holds the number of
846		 ticks to wait before the thread is made ready. The next entries (threads)
847		 has a list_data field that holds the number of ticks to wait after the
848		 previous thread is made ready. This is called to use a delta-time and
849		 makes the code to test if threads should be made ready very quick. It
850		 also, unfortunately, makes the code that insert code into the queue
851		 rather complex. */
852
853		int cpu = get_processor_index();
854		que_handle[cpu].load--;
855
856		kprints("CPU: "); kprinthex(cpu);
857		kprints(" paused thread:     "); kprinthex(get_current_thread());
858		kprints(" with load: "); kprinthex(que_handle[cpu].load); kprints("\n");
859
860		/* Grab the locks we need. */
861		grab_lock_rw(&timer_queue_lock);
862//		grab_lock_rw(&thread_table_lock);
863
864		/* If the queue is empty put the thread as only entry. */
865		if (-1 == timer_queue_head) {
866			thread_table[tmp_thread_index].data.next = -1;
867			thread_table[tmp_thread_index].data.list_data = timer_ticks;
868			timer_queue_head = tmp_thread_index;
869		} else {
870			/* Check if the thread should be made ready before the head of the
871			 previous timer queue. */
872			register int curr_timer_queue_entry = timer_queue_head;
873
874			if (thread_table[curr_timer_queue_entry].data.list_data > timer_ticks) {
875				/* If so set it up as the head in the new timer queue. */
876
877				thread_table[curr_timer_queue_entry].data.list_data -= timer_ticks;
878				thread_table[tmp_thread_index].data.next = curr_timer_queue_entry;
879				thread_table[tmp_thread_index].data.list_data = timer_ticks;
880				timer_queue_head = tmp_thread_index;
881			} else {
882				register int prev_timer_queue_entry = curr_timer_queue_entry;
883
884				/* Search until the end of the queue or until we found the right spot. */
885				while ((-1 != thread_table[curr_timer_queue_entry].data.next)
886						&& (timer_ticks >= thread_table[curr_timer_queue_entry].data.list_data)) {
887					timer_ticks -= thread_table[curr_timer_queue_entry].data.list_data;
888					prev_timer_queue_entry = curr_timer_queue_entry;
889					curr_timer_queue_entry = thread_table[curr_timer_queue_entry].data.next;
890				}
891
892				if (timer_ticks >= thread_table[curr_timer_queue_entry].data.list_data) {
893					/* Insert the thread into the queue after the existing entry. */
894					thread_table[tmp_thread_index].data.next = thread_table[curr_timer_queue_entry].data.next;
895					thread_table[curr_timer_queue_entry].data.next = tmp_thread_index;
896					thread_table[tmp_thread_index].data.list_data = timer_ticks
897							- thread_table[curr_timer_queue_entry].data.list_data;
898				} else {
899					/* Insert the thread into the queue before the existing entry. */
900					thread_table[tmp_thread_index].data.next = curr_timer_queue_entry;
901					thread_table[prev_timer_queue_entry].data.next = tmp_thread_index;
902					thread_table[tmp_thread_index].data.list_data = timer_ticks;
903					thread_table[curr_timer_queue_entry].data.list_data -= timer_ticks;
904				}
905			}
906		}
907
908		/* We are done accessing the timer queue so we can release the lock. */
909//		release_lock(&thread_table_lock);
910		release_lock(&timer_queue_lock);
911		break;
912	}
913
914	case SYSCALL_TIME: {
915		/* Returns the current system time to the program. */
916
917		/* Grabs the lock with read permissions so that the time will not change
918		 when reading it. */
919		// TODO: question lock
920		grab_lock_r(&timer_queue_lock);
921		SYSCALL_ARGUMENTS.rax = system_time;
922		release_lock(&timer_queue_lock);
923		break;
924	}
925
926	case SYSCALL_FREE: {
927		SYSCALL_ARGUMENTS.rax = kfree(SYSCALL_ARGUMENTS.rdi);
928		break;
929	}
930
931	case SYSCALL_ALLOCATE: {
932		/* Check the flags. */
933		if (0 != SYSCALL_ARGUMENTS.rsi & ~(ALLOCATE_FLAG_READONLY | ALLOCATE_FLAG_EX)) {
934			/* Return if the flags were not properly set. */
935			SYSCALL_ARGUMENTS.rax = ERROR;
936			break;
937		}
938
939		SYSCALL_ARGUMENTS.rax = kalloc(	SYSCALL_ARGUMENTS.rdi, thread_table[get_current_thread()].data.owner,
940										SYSCALL_ARGUMENTS.rsi & (ALLOCATE_FLAG_READONLY | ALLOCATE_FLAG_EX));
941		break;
942	}
943
944	case SYSCALL_GETSCANCODE: {
945		/* Grab spin lock. */
946		grab_lock_rw(&keyboard_scancode_buffer_lock);
947
948		/* Check if there is data in the scan code buffer. */
949		if (keyboard_scancode_high_marker != keyboard_scancode_low_marker) {
950			/* There is data in the buffer. Get it! */
951			SYSCALL_ARGUMENTS.rax = keyboard_scancode_buffer[(keyboard_scancode_low_marker++) & (KEYBOARD_BUFFER_SIZE - 1)];
952		} else {
953			/* No data in the buffer. We will block waiting for data. */
954			register int current_thread_index;
955
956			/* Set the default return value to be an error. */SYSCALL_ARGUMENTS.rax = ERROR;
957			current_thread_index = get_current_thread();
958			/* Tell the scheduler that it must run. */
959			schedule = 1;
960			thread_queue_enqueue(&keyboard_blocked_threads, current_thread_index);
961		}
962
963		/* Release spin lock. */
964		release_lock(&keyboard_scancode_buffer_lock);
965		break;
966	}
967
968	case SYSCALL_PRINTAT: {
969
970		/* Test for positive address range */
971		if (SYSCALL_ARGUMENTS.rdx < 0) {
972			SYSCALL_ARGUMENTS.rax = ERROR;
973			break;
974		}
975
976		/* Grab screen lock. */
977		grab_lock_rw(&screen_lock);
978
979		/* Test position */
980		if (setCourser(SYSCALL_ARGUMENTS.rdi, SYSCALL_ARGUMENTS.rsi) == ERROR) {
981			/* Release screen lock. */
982			release_lock(&screen_lock);
983			SYSCALL_ARGUMENTS.rax = ERROR;
984			break;
985		}
986
987		/* Print the string */
988		kprints(SYSCALL_ARGUMENTS.rdx);
989
990		/* Release screen lock. */
991		release_lock(&screen_lock);
992
993		SYSCALL_ARGUMENTS.rax = ALL_OK;
994		break;
995	}
996
997	case SYSCALL_GETPID: {
998		grab_lock_r(&thread_table_lock);
999		SYSCALL_ARGUMENTS.rax = thread_table[get_current_thread()].data.owner;
1000		release_lock(&thread_table_lock);
1001		break;
1002	}
1003
1004//#include "syscall.c"
1005
1006	case SYSCALL_PRINTS: {
1007		/* Grab screen lock. */
1008		grab_lock_rw(&screen_lock);
1009		kprints((char*) (SYSCALL_ARGUMENTS.rdi));
1010		/* Release screen lock. */
1011		release_lock(&screen_lock);
1012		SYSCALL_ARGUMENTS.rax = ALL_OK;
1013		break;
1014	}
1015
1016	case SYSCALL_PRINTHEX: {
1017		kprinthex(SYSCALL_ARGUMENTS.rdi);
1018		SYSCALL_ARGUMENTS.rax = ALL_OK;
1019		break;
1020	}
1021
1022	case SYSCALL_DEBUGGER: {
1023		/* Enable the bochs iodevice and force a return to the debugger. */
1024		outw(0x8a00, 0x8a00);
1025		outw(0x8a00, 0x8ae0);
1026
1027		SYSCALL_ARGUMENTS.rax = ALL_OK;
1028		break;
1029	}
1030
1031	case SYSCALL_VERSION: {
1032		SYSCALL_ARGUMENTS.rax = KERNEL_VERSION;
1033		break;
1034	}
1035
1036	case SYSCALL_CREATEPROCESS: {
1037
1038		grab_lock_rw(&process_table_lock);
1039
1040		/* Find free process entry */
1041		int i, success = 0;
1042		for (i = 0; i < MAX_NUMBER_OF_PROCESSES; ++i) {
1043			if (process_table[i].threads == 0) {
1044				success = 1;
1045				break;
1046			}
1047		}
1048		/* If no available processes return a error */
1049		if (!success) {
1050			release_lock(&process_table_lock);
1051			SYSCALL_ARGUMENTS.rax = ERROR;
1052			break;
1053		}
1054
1055		/* Prepare to load */
1056		struct prepare_process_return_value prepare_process_ret_val = prepare_process(
1057				executable_table[SYSCALL_ARGUMENTS.rdi].elf_image, i,
1058				executable_table[SYSCALL_ARGUMENTS.rdi].memory_footprint_size);
1059		/* Test if the exe is loaded */
1060		if (0 == prepare_process_ret_val.first_instruction_address) {
1061			release_lock(&process_table_lock);
1062			SYSCALL_ARGUMENTS.rax = ERROR;
1063			break;
1064		}
1065
1066		grab_lock_rw(&thread_table_lock);
1067
1068		/* Set parent to the current threads process */
1069		process_table[i].parent = thread_table[get_current_thread()].data.owner;
1070		process_table[i].threads++;
1071
1072		/* Find a position in thread_table */
1073		int new_thread = allocate_thread();
1074
1075		/* If no threads is available */
1076		if (new_thread == -1) {
1077			process_table[i].threads--;
1078
1079			release_lock(&thread_table_lock);
1080			release_lock(&process_table_lock);
1081
1082			SYSCALL_ARGUMENTS.rax = ERROR;
1083			break;
1084		}
1085
1086		release_lock(&process_table_lock);
1087
1088		/* Set owner process */
1089		thread_table[new_thread].data.owner = i;
1090		/* Reset all flags */
1091		thread_table[new_thread].data.registers.integer_registers.rflags = 0x200;
1092		/* Load exe start address */
1093		thread_table[new_thread].data.registers.integer_registers.rip =
1094				prepare_process_ret_val.first_instruction_address;
1095
1096		release_lock(&thread_table_lock);
1097
1098
1099		/* Insert the new thread on current CPU */
1100		insert_thread(new_thread);
1101
1102
1103// TODO: DIE
1104		grab_lock_rw(&ready_queue_lock);
1105		/* Enqueue the new thread */
1106		thread_queue_enqueue(&ready_queue, new_thread);
1107
1108		/* Release all locks */
1109		release_lock(&ready_queue_lock);
1110
1111
1112		SYSCALL_ARGUMENTS.rax = ALL_OK;
1113		break;
1114	}
1115
1116	case SYSCALL_CREATETHREAD: {
1117
1118		/* Halt on illegal instruction pointer */
1119		if (SYSCALL_ARGUMENTS.rdi < 0) {
1120			SYSCALL_ARGUMENTS.rax = ERROR;
1121			break;
1122		}
1123
1124		/* Halt on low memory allocation */
1125		if (SYSCALL_ARGUMENTS.rsi <= 0) {
1126			SYSCALL_ARGUMENTS.rax = ERROR;
1127			break;
1128		}
1129
1130		 grab_lock_rw(&thread_table_lock);
1131
1132		/* Allocate a new thread */
1133		int new_thread = allocate_thread();
1134
1135		/* Halt on thread shortage */
1136		if (new_thread == -1) {
1137			 release_lock(&thread_table_lock);
1138			SYSCALL_ARGUMENTS.rax = ERROR;
1139			break;
1140		}
1141
1142		/* Setup instruction pointer */
1143		thread_table[new_thread].data.registers.integer_registers.rip = SYSCALL_ARGUMENTS.rdi;
1144		/* Setup stack pointer */
1145		thread_table[new_thread].data.registers.integer_registers.rsp = SYSCALL_ARGUMENTS.rsi;
1146		/* Enable interrupts */
1147		thread_table[new_thread].data.registers.integer_registers.rflags = 0x200;
1148
1149		int owner_process = thread_table[get_current_thread()].data.owner;
1150		/* Ensure the thread is bound to a process */
1151		if (owner_process == -1) {
1152			SYSCALL_ARGUMENTS.rax = ERROR;
1153			break;
1154		}
1155		/* Set owner process to current thread owner */
1156		thread_table[new_thread].data.owner = owner_process;
1157
1158		 release_lock(&thread_table_lock);
1159
1160		 grab_lock_rw(&process_table_lock);
1161
1162		/* Increment the number of threads */
1163		process_table[owner_process].threads++;
1164
1165		release_lock(&process_table_lock);
1166
1167
1168		/* Insert the new thread on current CPU */
1169		insert_thread(new_thread);
1170
1171
1172// TODO: DIE
1173		 grab_lock_rw(&ready_queue_lock);
1174		/* Enqueue the new thread */
1175		thread_queue_enqueue(&ready_queue, new_thread);
1176		 release_lock(&ready_queue_lock);
1177
1178		SYSCALL_ARGUMENTS.rax = ALL_OK;
1179		break;
1180	}
1181
1182	case SYSCALL_TERMINATE: {
1183
1184		 grab_lock_rw(&thread_table_lock);
1185
1186		/* Find and terminate current thread */
1187		int owner_process = thread_table[get_current_thread()].data.owner;
1188
1189		/* Ensure process exists */
1190		if (owner_process == -1) {
1191			release_lock(&thread_table_lock);
1192			SYSCALL_ARGUMENTS.rax = ERROR;
1193			break;
1194		}
1195
1196		/* Terminate thread */
1197		thread_table[get_current_thread()].data.owner = -1;
1198		release_lock(&thread_table_lock);
1199
1200
1201		grab_lock_rw(&process_table_lock);
1202		/* Terminate process if last threads */
1203		if (--process_table[owner_process].threads == 0) {
1204			/* Cleanup the process */
1205			cleanup_process(owner_process);
1206		}
1207		release_lock(&process_table_lock);
1208
1209// ### change
1210		/* Adjust load */
1211		int cpu = get_processor_index();
1212		que_handle[cpu].load--;
1213
1214		kprints("CPU: "); kprinthex(cpu);
1215		kprints(" Terminated thread: "); kprinthex(get_current_thread());
1216		kprints(" with load: "); kprinthex(que_handle[cpu].load); kprints("\n");
1217
1218		/* Time to reschedule */
1219		schedule = 1;
1220
1221		SYSCALL_ARGUMENTS.rax = ALL_OK;
1222		break;
1223	}
1224
1225	case SYSCALL_CREATESEMAPHORE: {
1226
1227		/* Deny negative semaphores*/
1228		int val = SYSCALL_ARGUMENTS.rdi;
1229		if (val < 0) {
1230			SYSCALL_ARGUMENTS.rax = ERROR;
1231			break;
1232		}
1233
1234		int pos, succes = 0;
1235		/* Find a free semaphore */
1236		grab_lock_rw(&semaphore_table_lock);
1237		for (pos = 0; pos < MAX_NUMBER_OF_SEMAPHORES; ++pos) {
1238			if (semaphore_table[pos].process == -1) {
1239				succes = 1;
1240				break;
1241			}
1242		}
1243
1244		/* No available semaphore */
1245		if (!succes) {
1246			release_lock(&semaphore_table_lock);
1247			SYSCALL_ARGUMENTS.rax = ERROR;
1248			break;
1249		}
1250
1251		grab_lock_r(&thread_table_lock);
1252
1253		/* Associate semaphore with calling process */
1254		semaphore_table[pos].process = thread_table[get_current_thread()].data.owner;
1255
1256		release_lock(&thread_table_lock);
1257
1258		/* Assign semaphore count */
1259		semaphore_table[pos].value = val;
1260
1261		release_lock(&semaphore_table_lock);
1262
1263		/* Return semaphore index */
1264		SYSCALL_ARGUMENTS.rax = pos;
1265		break;
1266	}
1267
1268	case SYSCALL_SEMAPHOREUP: {
1269
1270		int pos = SYSCALL_ARGUMENTS.rdi;
1271
1272		grab_lock_rw(&semaphore_table_lock);
1273		grab_lock_r(&thread_table_lock);
1274
1275		/* Test semaphore owner process */
1276		if (semaphore_table[pos].process != thread_table[get_current_thread()].data.owner) {
1277			release_lock(&thread_table_lock);
1278			SYSCALL_ARGUMENTS.rax = ERROR;
1279			break;
1280		}
1281		release_lock(&thread_table_lock);
1282
1283		/* If no waiting threads increment semaphore */
1284		if (thread_queue_is_empty(&semaphore_table[pos].block_queue)) {
1285			semaphore_table[pos].value++;
1286		} else {
1287			/* Enqueue first blocked thread */
1288			int thread = thread_queue_dequeue(&semaphore_table[pos].block_queue);
1289
1290// TODO: DIE
1291			grab_lock_rw(&ready_queue_lock);
1292			thread_queue_enqueue(&ready_queue, thread);
1293			release_lock(&ready_queue_lock);
1294
1295			/* Insert the thread on current CPU */
1296			//insert_thread(thread);
1297		}
1298
1299		release_lock(&semaphore_table_lock);
1300		SYSCALL_ARGUMENTS.rax = ALL_OK;
1301		break;
1302	}
1303
1304	case SYSCALL_SEMAPHOREDOWN: {
1305
1306		kprints("Semaphore down called\n");
1307
1308		int pos = SYSCALL_ARGUMENTS.rdi;
1309
1310		grab_lock_rw(&semaphore_table_lock);
1311		grab_lock_r(&thread_table_lock);
1312
1313		/* Test semaphore owner process */
1314		if (semaphore_table[pos].process != thread_table[get_current_thread()].data.owner) {
1315			release_lock(&thread_table_lock);
1316			SYSCALL_ARGUMENTS.rax = ERROR;
1317			break;
1318		}
1319		release_lock(&thread_table_lock);
1320
1321
1322		/* Test if semaphore is positive */
1323		if (semaphore_table[pos].value > 0) {
1324			semaphore_table[pos].value--;
1325		}
1326		else {
1327			/* Block thread and reschedule */
1328			thread_queue_enqueue(&semaphore_table[pos].block_queue, get_current_thread());
1329
1330			/* Adjust load */
1331//			int cpu = get_processor_index();
1332//			grab_lock_rw(&que_handle_lock[cpu]);
1333//			que_handle[cpu].load--;
1334//			kprints("Semaphore down load: "); kprinthex(que_handle[cpu].load); kprints("\n");
1335//			release_lock(&que_handle_lock[cpu]);
1336//			schedule = 1;
1337		}
1338		release_lock(&semaphore_table_lock);
1339		SYSCALL_ARGUMENTS.rax = ALL_OK;
1340		break;
1341	}
1342
1343	default: {
1344		/* No system call defined. */
1345		SYSCALL_ARGUMENTS.rax = ERROR_ILLEGAL_SYSCALL;
1346		break;
1347	}
1348	}
1349//#include "scheduler.c"
1350
1351	if (schedule == 1) {
1352
1353		int this_cpu = get_processor_index();
1354
1355		/* If the CPU's running queue is empty switch to next queue */
1356		if (thread_queue_is_empty(&que_handle[this_cpu].running_queue)) {
1357			/* If the next queue is empty go idle */
1358			if (thread_queue_is_empty(&que_handle[this_cpu].next_queue)) {
1359				CPU_private_table[this_cpu].thread_index = -1;
1360			}
1361			else /* Swap the running and next queue*/
1362			{
1363				struct thread_queue tmp;
1364				tmp = que_handle[this_cpu].next_queue;
1365				que_handle[this_cpu].next_queue = que_handle[this_cpu].running_queue;
1366				que_handle[this_cpu].running_queue = tmp;
1367
1368				/* Get the next running thread */
1369				int next_runnting_thread = thread_queue_dequeue(&que_handle[this_cpu].running_queue);
1370
1371				CPU_private_table[this_cpu].thread_index = next_runnting_thread;
1372				CPU_private_table[this_cpu].ticks_left_of_time_slice = 200;
1373			}
1374		}else{
1375
1376			/* Get the next ready thread */
1377			int next_runnting_thread = thread_queue_dequeue(&que_handle[this_cpu].running_queue);
1378
1379			CPU_private_table[this_cpu].thread_index = next_runnting_thread;
1380			CPU_private_table[this_cpu].ticks_left_of_time_slice = 200;
1381		}
1382	}
1383
1384//	if (schedule == 1) {
1385//		grab_lock_rw(&ready_queue_lock);
1386//		grab_lock_rw(&CPU_private_table_lock);
1387//		/* If no ready threads sleep else set the new thread as running */
1388//		if (thread_queue_is_empty(&ready_queue)) {
1389//			CPU_private_table[get_processor_index()].thread_index = -1;
1390//		} else {
1391//			CPU_private_table[get_processor_index()].thread_index = thread_queue_dequeue(&ready_queue);
1392//			CPU_private_table[get_processor_index()].ticks_left_of_time_slice = 200;
1393//		}
1394//		release_lock(&CPU_private_table_lock);
1395//		release_lock(&ready_queue_lock);
1396//	}
1397}
1398
1399extern void timer_interrupt_handler(void) {
1400	/* Only the BSP should maintain the timer queue and system time. */
1401	if (0 == get_processor_index()) {
1402		/* Grab the locks so that we can access the data structures freely. */
1403		grab_lock_rw(&timer_queue_lock);
1404
1405		/* Increment system time. */
1406		system_time++;
1407
1408		/* Check if there are any thread that we should make ready.
1409		 First check if there are any threads at all in the timer
1410		 queue. */
1411		if (-1 != timer_queue_head) {
1412			/* Then decrement the list_data in the head. */
1413			thread_table[timer_queue_head].data.list_data -= 1;
1414
1415			/* Then remove all elements including with a list_data equal to zero
1416			 and insert them into the ready queue. These are the threads that
1417			 should be woken up. */
1418			/* We remove all entries less than or equal to 0. Equality should be
1419			 enough but checking with less than or equal may hide the symptoms
1420			 of some bugs and make the system more stable. */
1421			while ((-1 != timer_queue_head) && (thread_table[timer_queue_head].data.list_data <= 0)) {
1422				register int tmp_thread_index = timer_queue_head;
1423				/* Remove the head element.*/
1424				timer_queue_head = thread_table[tmp_thread_index].data.next;
1425
1426				/* Let the woken thread run if the CPU is not running any thread. */
1427				if (-1 == get_current_thread()) {
1428					CPU_private_table[get_processor_index()].thread_index = tmp_thread_index;
1429				} else {
1430					/* Or insert it into the ready queue. */
1431					grab_lock_rw(&ready_queue_lock);
1432					thread_queue_enqueue(&ready_queue, tmp_thread_index);
1433					release_lock(&ready_queue_lock);
1434
1435					/* Insert the thread on current CPU */
1436					insert_thread(tmp_thread_index);
1437				}
1438			}
1439		}
1440		/* Done updating the structures. */
1441		release_lock(&timer_queue_lock);
1442	}
1443//#include "pscheduler.c"
1444	/* If time slice is over preempt the thread */
1445//	grab_lock_rw(&CPU_private_table_lock);
1446//	if (--CPU_private_table[get_processor_index()].ticks_left_of_time_slice <= 0) {
1447//		thread_queue_enqueue(&ready_queue, CPU_private_table[get_processor_index()].thread_index);
1448//		CPU_private_table[get_processor_index()].thread_index = thread_queue_dequeue(&ready_queue);
1449//		CPU_private_table[get_processor_index()].ticks_left_of_time_slice = 200;
1450//	}
1451//	release_lock(&CPU_private_table_lock);
1452
1453
1454	if (--CPU_private_table[get_processor_index()].ticks_left_of_time_slice <= 0) {
1455
1456		int this_cpu = get_processor_index();
1457
1458		/* Enqueue the old thread */
1459		thread_queue_enqueue(&que_handle[this_cpu].next_queue, get_current_thread());
1460
1461		/* If the CPU's running queue is empty switch to next queue */
1462		if (thread_queue_is_empty(&que_handle[this_cpu].running_queue)) {
1463
1464				/* Swap the running and next queue*/
1465				struct thread_queue tmp;
1466				tmp = que_handle[this_cpu].next_queue;
1467				que_handle[this_cpu].next_queue = que_handle[this_cpu].running_queue;
1468				que_handle[this_cpu].running_queue = tmp;
1469		}
1470		/* Get the next ready thread */
1471		int next_runnting_thread = thread_queue_dequeue(&que_handle[this_cpu].running_queue);
1472		CPU_private_table[this_cpu].thread_index = next_runnting_thread;
1473		CPU_private_table[this_cpu].ticks_left_of_time_slice = 200;
1474	}
1475}
1476
1477/*! Keyboard interrupt handler. */
1478static inline void keyboard_interrupt_handler(void) {
1479	register unsigned char status_byte = inb(0x64);
1480
1481	if ((status_byte & 1) == 1) {
1482		register unsigned char data = inb(0x60);
1483
1484		/* Grab the buffer lock. */
1485		grab_lock_rw(&keyboard_scancode_buffer_lock);
1486
1487		/* Is a thread waiting for data? */
1488		if (thread_queue_is_empty(&keyboard_blocked_threads)) {
1489			/* Store scan code in the buffer if there is space in the buffer. */
1490			register int buffer_size = keyboard_scancode_high_marker - keyboard_scancode_low_marker;
1491			if (buffer_size < KEYBOARD_BUFFER_SIZE) {
1492				keyboard_scancode_buffer[(keyboard_scancode_high_marker++) & (KEYBOARD_BUFFER_SIZE - 1)] = data;
1493			}
1494		} else {
1495			/* Let the first blocked thread get the scan code. */
1496			register int blocked_thread_index = thread_queue_dequeue(&keyboard_blocked_threads);
1497			thread_table[blocked_thread_index].data.registers.integer_registers.rax = data;
1498
1499			/* Let the woken thread run if the CPU is not running any thread. */
1500			if (-1 == get_current_thread()) {
1501				CPU_private_table[get_processor_index()].thread_index = blocked_thread_index;
1502			} else {
1503				/* Or insert it into the ready queue. */
1504				grab_lock_rw(&ready_queue_lock);
1505				thread_queue_enqueue(&ready_queue, blocked_thread_index);
1506				release_lock(&ready_queue_lock);
1507			}
1508		}
1509
1510		/* Release buffer lock. */
1511		release_lock(&keyboard_scancode_buffer_lock);
1512	}
1513}
1514
1515extern void interrupt_dispatcher(const unsigned long interrupt_number) {
1516	/* Select a handler based on interrupt source. */
1517	switch (interrupt_number) {
1518
1519	case 6: {
1520//		kprints("CPU: "); kprinthex(get_processor_index());
1521//		kprints(" thread: "); kprinthex(get_current_thread());
1522//		kprints(" with load: "); kprinthex(que_handle[get_processor_index()].load); kprints("\n");
1523		break;
1524	}
1525
1526	case 32: {
1527		timer_interrupt_handler();
1528		break;
1529	}
1530
1531	case 33: {
1532		keyboard_interrupt_handler();
1533		break;
1534	}
1535
1536	case 255:
1537	case 39: {
1538		/* Spurious interrupt occurred. This could happen if we spend too long
1539		 time with interrupts disabled. */
1540		break;
1541	}
1542
1543	case 240: {
1544		/* Dummy IPI handler. */
1545		break;
1546	}
1547
1548	default: {
1549		kprints("Unknown interrupt. Vector: ");
1550		kprinthex(interrupt_number);
1551		kprints("\n");
1552		while (1) {
1553			outw(0x8a00, 0x8a00);
1554			outw(0x8a00, 0x8ae0);
1555		}
1556		break;
1557	}
1558	}
1559
1560	/* Acknowledge interrupt so that new interrupts can be sent to the CPU. */
1561	if (interrupt_number >= 32) {
1562		/* Do an EOI procedure on the local APIC. */
1563
1564		/* Get address to local APIC. */
1565		register unsigned int const processor_index = get_processor_index();
1566		register volatile unsigned int* const APIC_base_address = (unsigned int*) ((CPU_private_table[processor_index].apic_phys_address) & 0xffffffffULL);
1567
1568		/* Acknowledge the interrupt. */
1569		*(APIC_base_address + 0xb0 / sizeof(unsigned int)) = 0;
1570	}
1571}