Begin multitasking refactor to support ring-3 TSS
diff --git a/src/kernel/Jmk b/src/kernel/Jmk
index 09ebdfd..bf51a3f 100644
--- a/src/kernel/Jmk
+++ b/src/kernel/Jmk
@@ -39,6 +39,7 @@
io.o \
vga.o \
gdt_flush.o \
+ tss_flush.o \
idt.o \
log.o \
irq.o \
diff --git a/src/kernel/bf.c b/src/kernel/bf.c
new file mode 100644
index 0000000..04c97d9
--- /dev/null
+++ b/src/kernel/bf.c
@@ -0,0 +1 @@
+#include <bf.h>
diff --git a/src/kernel/descriptor_tables.c b/src/kernel/descriptor_tables.c
index 211dcb2..339162e 100644
--- a/src/kernel/descriptor_tables.c
+++ b/src/kernel/descriptor_tables.c
@@ -7,6 +7,7 @@
extern void gdt_flush(uint gdt);
extern void idt_flush(uint idt);
+extern void tss_flush();
static void gdt_set_gate(uint i, uint base, uint limit, uchar access,
uchar gran);
@@ -29,26 +30,7 @@
extern void (*interrupt_handlers[256])(struct registers);
-void init_gdt()
-{
- vga_write("Initializing GDT...\n");
- gdt_pointer.limit = sizeof(struct gdt_entry) * 5 - 1;
- gdt_pointer.base = (uint)&gdt_entries;
-
- gdt_set_gate(0, 0, 0, 0, 0); // Null segment
- gdt_set_gate(1, 0, ~0, 0x9a, 0xcf); // Code segment
- gdt_set_gate(2, 0, ~0, 0x92, 0xcf); // Data segment
- gdt_set_gate(3, 0, ~0, 0xfa, 0xcf); // User mode code segment
- gdt_set_gate(4, 0, ~0, 0xf2, 0xcf); // User mode data segment
-
- for (volatile uint i = 0; i < 0x1000; i++)
- {
- } // waste some time, for some reason this helps
-
- gdt_flush((uint)&gdt_pointer);
-
- vga_write("GDT Initialized\n");
-}
+struct tss_entry tss_entry;
static void gdt_set_gate(uint i, uint base, uint limit, uchar access,
uchar gran)
@@ -65,6 +47,44 @@
e->access = access;
}
+static void init_tss(uint num, uint ss, uint esp)
+{
+ gdt_set_gate(num, (uint)&tss_entry, (uint)&tss_entry+1, 0xe9, 0x00);
+
+ memset(&tss_entry, 0, sizeof(tss_entry));
+
+ tss_entry.ss0 = ss;
+ tss_entry.esp0 = esp;
+ tss_entry.cs = 0x0b;
+ // | 0b11 to make these readable from user-mode. i.e. user mode
+ // can switch to kernel mode using this tss
+ tss_entry.ss = tss_entry.ds = tss_entry.es = tss_entry.fs = tss_entry.gs = 0x13;
+}
+
+void init_gdt()
+{
+ vga_write("Initializing GDT...\n");
+ gdt_pointer.limit = sizeof(struct gdt_entry) * 5 - 1;
+ gdt_pointer.base = (uint)&gdt_entries;
+
+ gdt_set_gate(0, 0, 0, 0, 0); // Null segment, 0x00
+ gdt_set_gate(1, 0, ~0, 0x9a, 0xcf); // Code segment, 0x08
+ gdt_set_gate(2, 0, ~0, 0x92, 0xcf); // Data segment, 0x10
+ gdt_set_gate(3, 0, ~0, 0xfa, 0xcf); // User mode code segment, 0x18
+ gdt_set_gate(4, 0, ~0, 0xf2, 0xcf); // User mode data segment, 0x20
+ //init_tss(5, 0x10, 0x0); // 0x10 = kernel data segment, 0x28
+
+ for (volatile uint i = 0; i < 0x1000; i++)
+ {
+ } // waste some time, for some reason this helps
+
+ gdt_flush((uint)&gdt_pointer);
+ // For now let's not do this
+ // tss_flush();
+
+ vga_write("GDT Initialized\n");
+}
+
void init_idt()
{
idt_pointer.limit = sizeof(struct idt_entry) * 256 - 1;
@@ -114,3 +134,8 @@
init_gdt();
init_idt();
}
+
+void set_kernel_interrupt_stack(void *stack)
+{
+ tss_entry.esp0 = (uint)stack;
+}
diff --git a/src/kernel/descriptor_tables.h b/src/kernel/descriptor_tables.h
index 0c9f5f1..6022f8d 100644
--- a/src/kernel/descriptor_tables.h
+++ b/src/kernel/descriptor_tables.h
@@ -71,6 +71,50 @@
uint base;
} __attribute__((packed));
+// We don't use hardware task switching, but we need a TSS entry
+// anyway.
+struct __attribute__((packed)) tss_entry
+{
+ // Previous TSS. Unused.
+ uint prev_tss;
+ // Kernel stack pointer.
+ uint esp0;
+ // Kernel stack segment.
+ uint ss0;
+ // Unused
+ uint esp1;
+ uint ss1;
+ uint esp2;
+ uint ss2;
+ uint cr3;
+ uint eip;
+ uint eflags;
+ uint eax;
+ uint ecx;
+ uint edx;
+ uint ebx;
+ uint esp;
+ uint ebp;
+ uint esi;
+ uint edi;
+ // The value to load into ES when we change to kernel mode.
+ uint es;
+ // The value to load into CS when we change to kernel mode.
+ uint cs;
+ // The value to load into SS when we change to kernel mode.
+ uint ss;
+ // The value to load into DS when we change to kernel mode.
+ uint ds;
+ // The value to load into FS when we change to kernel mode.
+ uint fs;
+ // The value to load into GS when we change to kernel mode.
+ uint gs;
+ // Unused...
+ uint ldt;
+ ushort trap;
+ ushort iomap_base;
+};
+
extern void isr0();
extern void isr1();
extern void isr2();
@@ -129,3 +173,8 @@
void init_descriptor_tables();
void init_idt();
void init_gdt();
+
+/// Set the stack to be used for Kernel-mode interrupt routines
+void set_kernel_interrupt_stack(void *stack);
+
+extern struct tss_entry tss_entry;
diff --git a/src/kernel/dri/bf_sso/Jmk b/src/kernel/dri/bf_sso/Jmk
new file mode 100644
index 0000000..45f5bc7
--- /dev/null
+++ b/src/kernel/dri/bf_sso/Jmk
@@ -0,0 +1,17 @@
+init(bf_sso, bf_sso.a)
+
+preset(freestanding)
+preset(optimize)
+preset(debug)
+preset(32)
+preset(warn)
+
+archetype(c)
+
+CFLAGS += -I$(ROOT)/include/kernel
+
+OBJECTS = bf_sso.o
+
+type(static_lib)
+
+finish
diff --git a/src/kernel/dri/bf_sso/bf_sso.c b/src/kernel/dri/bf_sso/bf_sso.c
new file mode 100644
index 0000000..2be8b7d
--- /dev/null
+++ b/src/kernel/dri/bf_sso/bf_sso.c
@@ -0,0 +1,2 @@
+#include <dri/bf_sso/bf_sso.h>
+
diff --git a/src/kernel/idt.s b/src/kernel/idt.s
index 7cd26e6..1b70054 100644
--- a/src/kernel/idt.s
+++ b/src/kernel/idt.s
@@ -61,7 +61,7 @@
[extern isr_handler]
isr_common:
- pusha ; Save all registers
+ pushad ; Save all registers
mov ax, ds ; Save data segment
push eax
@@ -80,7 +80,7 @@
mov fs, ax
mov gs, ax
- popa
+ popad
add esp, 8 ; Passed arguments
sti
iret ; Return from interrupt
diff --git a/src/kernel/irq.s b/src/kernel/irq.s
index e340a61..dc16f89 100644
--- a/src/kernel/irq.s
+++ b/src/kernel/irq.s
@@ -28,7 +28,7 @@
[extern irq_handler]
irq_common:
- pusha
+ pushad
mov ax, ds ; Save data segment
push eax
@@ -46,7 +46,7 @@
mov fs, bx
mov gs, bx
- popa
+ popad
add esp, 8
sti
iret
diff --git a/src/kernel/paging.c b/src/kernel/paging.c
index 50ee738..f1fd125 100644
--- a/src/kernel/paging.c
+++ b/src/kernel/paging.c
@@ -12,6 +12,7 @@
static uint first_page_table[1024] __attribute__((aligned(4096)));
uint kernel_page_directory[1024] __attribute__((aligned(4096)));
+
/* frame utils */
#define BITS 32
@@ -94,16 +95,41 @@
uint *get_or_create_table(uint *dir, uint table, bool user, bool rw)
{
- if (dir[table] >> 12)
+ // If used AND NOT 4mb page (see figure 4-4, page 115 of Intel
+ // manual volume 3)
+ if (dir[table] & 1 && dir[table] ^ 1 << 7)
{
- return (uint *)(size_t)PHYS_TO_VIRT((dir[table] ^ 0xfff));
+ return (uint *)(size_t)PHYS_TO_VIRT((dir[table] & ~0xfff));
}
- uint *page_table = kmalloc_a(sizeof(uint[1024]));
+ uint *page_table = malloc(sizeof(uint[1024]));
dir[table] = VIRT_TO_PHYS(page_table) | 1 | rw << 1 | user << 2;
return page_table;
}
+void unmap_all_frames(uint page_table_p)
+{
+ uint *table = (uint *)PHYS_TO_VIRT(page_table_p);
+
+ for (int i = 0; i < 1024; i++)
+ {
+ if (table[i] & 1)
+ {
+ clear_frame(table[i] >> 12);
+ }
+ }
+}
+
+void destroy_page_table_if_exists(uint *dir, uint table)
+{
+ // If used AND NOT 4mb page
+ if (dir[table] & 1 && dir[table] ^ 1 << 7)
+ {
+ unmap_all_frames(dir[table] >> 12);
+ free((void *)PHYS_TO_VIRT(dir[table] >> 12));
+ }
+}
+
void unmap_page(uint *dir, void *virt)
{
uint page = ((size_t)virt / 0x1000) % 1024;
@@ -171,6 +197,26 @@
/* paging stuff */
+uint *new_page_directory_v()
+{
+ // Only call this AFTER allocator + paging are initialized!
+ uint *dir = malloc(1024 * 4);
+ map_4mb(kernel_page_directory, (size_t)KERNEL_VIRTUAL_BASE, 0, false,
+ false);
+
+ return dir;
+}
+
+void free_page_directory_v(uint *dir_v)
+{
+ for (int i = 0; i < 1024; i++)
+ {
+ destroy_page_table_if_exists(dir_v, i);
+ }
+
+ free(dir_v);
+}
+
void init_paging()
{
memset(kernel_page_directory, 0, 1024 * 4);
@@ -178,6 +224,7 @@
false);
load_page_directory((uint)kernel_page_directory - 0xC0000000);
+
add_interrupt_handler(14, page_fault);
}
diff --git a/src/kernel/paging.h b/src/kernel/paging.h
index 20ecce9..e264356 100644
--- a/src/kernel/paging.h
+++ b/src/kernel/paging.h
@@ -4,7 +4,7 @@
#include "registers.h"
#define VIRT_TO_PHYS(virt) ((uint)(virt) - 0xC0000000)
-#define PHYS_TO_VIRT(phys) ((void *)((phys) + 0xC0000000))
+#define PHYS_TO_VIRT(phys) ((void *)((uint)(phys) + 0xC0000000))
#define KERNEL_VIRTUAL_BASE 0xC0000000
#define KERNEL_PAGE_NUMBER (KERNEL_VIRTUAL_BASE >> 22)
@@ -20,3 +20,4 @@
void alloc_page(uint *dir, uint *page);
void alloc_kernel_page(uint *page);
void page_fault(struct registers *regs);
+uint *new_page_directory_v();
diff --git a/src/kernel/syscall.c b/src/kernel/syscall.c
index 1f31296..26a0002 100644
--- a/src/kernel/syscall.c
+++ b/src/kernel/syscall.c
@@ -11,7 +11,7 @@
{
case SYS_GIVEUP:
// easy, just switch tasks
- switch_task();
+ switch_task(*regs);
break;
default:
diff --git a/src/kernel/task.c b/src/kernel/task.c
index 116e4a2..d538e01 100644
--- a/src/kernel/task.c
+++ b/src/kernel/task.c
@@ -11,7 +11,7 @@
bool tasks_initialized = false;
-void _init_tasks(uint kernel_esp, uint kernel_ebp, uint kernel_eip);
+void _init_tasks(struct registers *regs);
void init_tasks()
{
@@ -22,10 +22,10 @@
void _sys_init_tasks_h(struct registers *regs)
{
- _init_tasks(regs->esp, regs->ebp, regs->eip);
+ _init_tasks(regs);
}
-void _init_tasks(uint kernel_esp, uint kernel_ebp, uint kernel_eip)
+void _init_tasks(struct registers *regs)
{
processes[0] = (struct process){
.exists = true,
@@ -33,12 +33,13 @@
.ring = 0,
.uid = 0,
.page_directory_p = VIRT_TO_PHYS(kernel_page_directory),
- // Obviously this isn't the actual stack position, but we want it to
- // grow down from 4 gb so we will pretend that the first task has its
- // stack at exactly 4gb and work from there. Because the new stack will
- // be mapped to any random frame, it doesn't actually matter where we
- // put it, we just want somewhere that won't collide with any user space
- // stuff or our heap.
+ // Obviously this isn't the actual stack position, but we want
+ // it to grow down from 4 gb so we will pretend that the first
+ // task has its stack at exactly 4gb and work from
+ // there. Because the new stack will be mapped to any random
+ // frame, it doesn't actually matter where we put it, we just
+ // want somewhere that won't collide with any user space stuff
+ // or our heap.
.last_stack_pos = 0xFFFFF000,
};
strcpy(processes[0].name, "kernel");
@@ -47,11 +48,10 @@
first_task->next = NULL;
first_task->prev = NULL;
+ memset(&first_task->task, 0, sizeof(struct task));
first_task->task = (struct task){
.proc = &processes[0],
- .esp = kernel_esp,
- .ebp = kernel_ebp,
- .eip = kernel_eip,
+ .state = *regs,
.id = next_task_id++,
.waiting = false,
};
@@ -101,11 +101,15 @@
struct ll_task_i *ll_task = malloc(sizeof(struct ll_task_i));
memset(ll_task, 0, sizeof(struct ll_task_i));
struct task *task = &ll_task->task;
+ // New task is basically the same as the old one but with just a
+ // few changes
+ *task = current_task->task;
- task->proc = proc;
+ // Namely a new TID
task->id = next_task_id++;
- task->ebp = task->esp = new_stack_base_v;
- task->eip = (uint)function;
+ // And stack, frame, and instruction pointers
+ task->state.ebp = task->state.esp = new_stack_base_v;
+ task->state.eip = (uint)function;
task->waiting = false;
last_task->next = ll_task;
@@ -132,8 +136,9 @@
if (current_task->next != NULL)
{
- // If this is NULL, task will be first_task, which can't be the current task
- // because we know there are more than one task, and this is the last one.
+ // If this is NULL, task will be first_task, which can't be
+ // the current task because we know there are more than one
+ // task, and this is the last one.
current_task->next->prev = current_task->prev;
task = current_task->next;
}
@@ -152,27 +157,29 @@
asm("sti");
}
-extern void _switch_to_task(uint page_directory, uint eip, uint ebp, uint esp);
+extern void _switch_to_task(uint page_directory, struct registers ctx);
+#if 0
+{
+ asm("mov %0, %%ecx" :: "g"(page_directory));
+ asm("mov %ecx, %cr3");
+ // "ctx" will be at the top of the stack.
+ asm("iret");
+}
+#endif
void switch_to_task(struct task *task)
{
- _switch_to_task(task->proc->page_directory_p, task->eip, task->ebp,
- task->esp);
+ _switch_to_task(task->proc->page_directory_p, task->state);
__builtin_unreachable();
}
-// WARNING: do not call this manually, it will clobber everything
-// except esp, ebp, and eip (obviously). Use switch_task in task_api.s
-// instead.
-void _do_switch_task(uint eip, uint ebp, uint esp)
+void _do_switch_task(struct registers regs)
{
// sti is called in switch_to_task
asm("cli");
// save context for this task
- current_task->task.ebp = ebp;
- current_task->task.esp = esp;
- current_task->task.eip = eip;
+ current_task->task.state = regs;
struct ll_task_i *original = current_task;
@@ -213,3 +220,9 @@
asm("sti");
}
+
+void switch_task(struct registers ctx)
+{
+ if (tasks_initialized)
+ _do_switch_task(ctx);
+}
diff --git a/src/kernel/task_api.s b/src/kernel/task_api.s
index c862c21..5c7eaa9 100644
--- a/src/kernel/task_api.s
+++ b/src/kernel/task_api.s
@@ -1,30 +1,37 @@
- [bits 32]
- [extern _do_switch_task]
- [global switch_task]
-switch_task:
- pusha ; Save everything
- push esp ; Arguments for _do_switch_task(eip, ebp, esp)
- push ebp
- push .after
- call _do_switch_task
-.after:
- ;; add esp, 12 ; Clear the arguments
- popa ; Reset everything
- xor eax, eax ; Return 0
- ret
-
- [global _switch_to_task]
- ;; _switch_to_task(uint page_directory, uint eip, uint ebp, uint esp)
-_switch_to_task: ; (page_directory, eip, ebp, esp)
+ ;; This is very much the same as _switch_to_task, but we used iret
+ ;; and switch to ring3.
+ [global _switch_to_user_task]
+ ;; _switch_to_user_task(uint page_directory, uint eip, uint ebp, uint esp)
+_switch_to_user_task: ; (page_directory, eip, ebp, esp)
add esp, 4 ; We don't care about the return address
pop ecx ; Page directory
pop eax ; eip
pop ebp
pop ebx ; esp
-
- mov esp, ebx ; Reset old stack
+ mov dx, 0x23 ; User mode data segment
+ mov ds, dx
+ mov es, dx
+ mov fs, dx
+ mov gs, dx
+
mov cr3, ecx ; Set page directory
+
+ push 0x23
+ push ebx ; esp
+
sti
jmp eax ; Jump back to code
+
+ [global _switch_to_task]
+_switch_to_task: ; (uint page_directory, struct
+ ; registers regs)
+ add esp, 4 ; We don't care about return address
+ pop eax
+ mov cr3, eax ; Change page directories
+ pop eax
+ mov ds, ax ; First is ds
+ popad ; Then the rest of the registers
+ add esp, 8 ; Then IRQ # and error #
+ iret ; And finally the saved state
diff --git a/src/kernel/timer.c b/src/kernel/timer.c
index be177f9..0e52d0e 100644
--- a/src/kernel/timer.c
+++ b/src/kernel/timer.c
@@ -12,7 +12,7 @@
if (tasks_initialized)
{
// Preemptive multitasking!
- switch_task();
+ switch_task(*regs);
}
}
diff --git a/src/kernel/tss_flush.s b/src/kernel/tss_flush.s
new file mode 100644
index 0000000..0da4bfc
--- /dev/null
+++ b/src/kernel/tss_flush.s
@@ -0,0 +1,7 @@
+ [bits 32]
+ [global tss_flush]
+tss_flush:
+ mov ax, 0x2b ; 0x28 = offset of TSS, | 0b11 to make
+ ; it user-readable
+ ltr ax ; Load task register
+ ret
diff --git a/src/lisp/.gdbinit b/src/lisp/.gdbinit
new file mode 100644
index 0000000..dd38820
--- /dev/null
+++ b/src/lisp/.gdbinit
@@ -0,0 +1,2 @@
+unset env
+set env LISP_LIBRARY_PATH=/home/ch/dev/bluejay/lib/lisp
diff --git a/src/lisp/compiler.dasc b/src/lisp/compiler.dasc
index 5cd6897..bfe74e1 100644
--- a/src/lisp/compiler.dasc
+++ b/src/lisp/compiler.dasc
@@ -431,6 +431,7 @@
if (!ok_)
{
free(env);
+ NEARFL(filename, 1);
THROWSAFE(ENOTFOUND);
}
diff --git a/src/lisp/error.h b/src/lisp/error.h
index 7577cdf..6778081 100644
--- a/src/lisp/error.h
+++ b/src/lisp/error.h
@@ -44,6 +44,7 @@
__error.loc.line = cons_line(val), \
__error.loc.file = cons_file(val)
#define NEARIS(is) (is)->getpos((is), &__error.loc.line, &__error.loc.file)
+#define NEARFL(f, l) __error.loc.line=l, __error.loc.file=f
#define _TRY(expr, m, c) \
{ \
struct error __sub = (expr); \
diff --git a/src/lisp/lib/std.c b/src/lisp/lib/std.c
index 935df1f..224c086 100644
--- a/src/lisp/lib/std.c
+++ b/src/lisp/lib/std.c
@@ -71,6 +71,15 @@
env->first = new;
}
+void add_c_varargs(struct environment *env, char *name, void *func, int nargs)
+{
+ struct args *args = new_args();
+ args->num_required = nargs;
+ args->variadic = true;
+
+ add_function(env, name, func, args, NS_FUNCTION);
+}
+
void add_c_function(struct environment *env, char *name, void *func, int nargs)
{
struct args *args = new_args();
@@ -125,7 +134,64 @@
return nil;
}
- return (a >> 3) == (b >> 3) ? t : nil;
+ return (a >> 2) == (b >> 2) ? t : nil;
+}
+
+value_t l_num_gt(value_t a, value_t b)
+{
+ if (!integerp(a) || !integerp(b))
+ return nil;
+
+ return (a >> 2) > (b >> 2) ? t : nil;
+}
+
+value_t l_num_lt(value_t a, value_t b)
+{
+ if (!integerp(a) || !integerp(b))
+ return nil;
+
+ return (a >> 2) < (b >> 2) ? t : nil;
+}
+
+value_t l_append(value_t l)
+{
+ if (nilp(l))
+ return l;
+
+ value_t first = nil;
+ value_t *last = NULL;
+
+ for (value_t item = l; !nilp(item); item = cdr(item))
+ {
+ value_t a = car(item);
+
+ if (!listp(a))
+ {
+ value_t new = cons(a, nil);
+ *last = new;
+ last = cdrref(new);
+ continue;
+ }
+
+ for (value_t i = a; !nilp(i); i = cdr(i))
+ {
+ value_t b = car(i);
+
+ if (!last)
+ {
+ first = cons(b, nil);
+ last = cdrref(first);
+ }
+ else
+ {
+ value_t new = cons(b, nil);
+ *last = new;
+ last = cdrref(new);
+ }
+ }
+ }
+
+ return first;
}
#define LISP_PREDICATE(name) value_t l_##name(value_t v) { return name(v) ? t : nil; }
@@ -147,6 +213,8 @@
add_c_function(env, "*", l_times, 2);
add_c_function(env, "/", l_divide, 2);
add_c_function(env, "=", l_num_eq, 2);
+ add_c_function(env, "<", l_num_lt, 2);
+ add_c_function(env, ">", l_num_gt, 2);
add_c_function(env, "car", car, 1);
add_c_function(env, "cdr", cdr, 1);
@@ -155,6 +223,7 @@
add_c_function(env, "print", l_printval, 1);
add_c_function(env, "read-stdin", l_read_stdin, 0);
add_c_function(env, "apply", l_apply, 2);
+ add_c_varargs(env, "append", l_append, 0);
add_c_function(env, "nilp", l_nilp, 1);
add_c_function(env, "listp", l_listp, 1);
@@ -168,6 +237,7 @@
if (!load_library(env, "std"))
{
+ fprintf(stderr, "Not found std\n");
THROW(ENOTFOUND, "Could not load library `std`, make sure your $LISP_LIBRARY_PATH is correct.");
}
@@ -188,7 +258,7 @@
if (file_exists(path))
{
- fprintf(stderr, "path: %s\n", path);
+ // fprintf(stderr, "loading path: %s\n", path);
return load(env, path);
}
@@ -196,7 +266,7 @@
if (file_exists(path))
{
- fprintf(stderr, "path: %s\n", path);
+ // fprintf(stderr, "loading path: %s\n", path);
return load(env, path);
}
}
diff --git a/src/lisp/quicksort.lisp b/src/lisp/quicksort.lisp
new file mode 100644
index 0000000..b622ec9
--- /dev/null
+++ b/src/lisp/quicksort.lisp
@@ -0,0 +1,23 @@
+;;; Quicksort
+
+(defun quicksort (l)
+ (if (not l)
+ l
+ (let1 (rest (cdr l))
+ (append
+ (quicksort (remove-if-not
+ (lambda (x)
+ (< x (car l)))
+ rest))
+
+ (list (car l))
+
+ (quicksort (remove-if-not
+ (lambda (x)
+ (> x (car l)))
+ rest))))))
+
+(defun main ()
+ (print
+ (quicksort
+ (list 12 3 4 1 6 8 10 5 14))))