sys_lazyk(): syscall of Lazy K interpreter

0001-Add-syscall-of-Lazy-K-interpreter-as-sys_lazyk.patch

From b5fae6767cdee2dff093ab296b86926583f85512 Mon Sep 17 00:00:00 2001
From: Hiromu Yakura <hiromu1996@gmail.com>
Date: Thu, 8 Dec 2011 15:13:38 +0900
Subject: [PATCH] Add syscall of Lazy K interpreter as sys_lazyk

---
 arch/arm/include/asm/unistd.h      |    1 +
 arch/arm/kernel/calls.S            |    1 +
 arch/x86/include/asm/unistd_32.h   |    3 +-
 arch/x86/include/asm/unistd_64.h   |    2 +
 arch/x86/kernel/syscall_table_32.S |    1 +
 include/asm-generic/unistd.h       |    2 +
 include/linux/syscalls.h           |    3 +
 kernel/Makefile                    |    2 +-
 kernel/lazyk.c                     |  522 ++++++++++++++++++++++++++++++++++++
 9 files changed, 535 insertions(+), 2 deletions(-)
 create mode 100644 kernel/lazyk.c

diff --git a/arch/arm/include/asm/unistd.h b/arch/arm/include/asm/unistd.h
index 4a11237..f7b0ac8 100644
--- a/arch/arm/include/asm/unistd.h
+++ b/arch/arm/include/asm/unistd.h
@@ -404,6 +404,7 @@
 #define __NR_setns			(__NR_SYSCALL_BASE+375)
 #define __NR_process_vm_readv		(__NR_SYSCALL_BASE+376)
 #define __NR_process_vm_writev		(__NR_SYSCALL_BASE+377)
+#define __NR_lazyk			(__NR_SYSCALL_BASE+378)
 
 /*
  * The following SWIs are ARM private.
diff --git a/arch/arm/kernel/calls.S b/arch/arm/kernel/calls.S
index 463ff4a..d4dcba3 100644
--- a/arch/arm/kernel/calls.S
+++ b/arch/arm/kernel/calls.S
@@ -387,6 +387,7 @@
 /* 375 */	CALL(sys_setns)
 		CALL(sys_process_vm_readv)
 		CALL(sys_process_vm_writev)
+		CALL(sys_lazyk)
 #ifndef syscalls_counted
 .equ syscalls_padding, ((NR_syscalls + 3) & ~3) - NR_syscalls
 #define syscalls_counted
diff --git a/arch/x86/include/asm/unistd_32.h b/arch/x86/include/asm/unistd_32.h
index 599c77d..cade79d 100644
--- a/arch/x86/include/asm/unistd_32.h
+++ b/arch/x86/include/asm/unistd_32.h
@@ -354,10 +354,11 @@
 #define __NR_setns		346
 #define __NR_process_vm_readv	347
 #define __NR_process_vm_writev	348
+#define __NR_lazyk
 
 #ifdef __KERNEL__
 
-#define NR_syscalls 349
+#define NR_syscalls 350
 
 #define __ARCH_WANT_IPC_PARSE_VERSION
 #define __ARCH_WANT_OLD_READDIR
diff --git a/arch/x86/include/asm/unistd_64.h b/arch/x86/include/asm/unistd_64.h
index 0431f19..c85e262 100644
--- a/arch/x86/include/asm/unistd_64.h
+++ b/arch/x86/include/asm/unistd_64.h
@@ -686,6 +686,8 @@ __SYSCALL(__NR_getcpu, sys_getcpu)
 __SYSCALL(__NR_process_vm_readv, sys_process_vm_readv)
 #define __NR_process_vm_writev			311
 __SYSCALL(__NR_process_vm_writev, sys_process_vm_writev)
+#define __NR_lazyk				312
+__SYSCALL(__NR_lazyk, sys_lazyk(
 
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR
diff --git a/arch/x86/kernel/syscall_table_32.S b/arch/x86/kernel/syscall_table_32.S
index 9a0e312..09e53b4 100644
--- a/arch/x86/kernel/syscall_table_32.S
+++ b/arch/x86/kernel/syscall_table_32.S
@@ -348,3 +348,4 @@ ENTRY(sys_call_table)
 	.long sys_setns
 	.long sys_process_vm_readv
 	.long sys_process_vm_writev
+	.long sys_lazyk
diff --git a/include/asm-generic/unistd.h b/include/asm-generic/unistd.h
index f4c38d8c..a6b9660 100644
--- a/include/asm-generic/unistd.h
+++ b/include/asm-generic/unistd.h
@@ -685,6 +685,8 @@ __SYSCALL(__NR_syncfs, sys_syncfs)
 __SYSCALL(__NR_setns, sys_setns)
 #define __NR_sendmmsg 269
 __SC_COMP(__NR_sendmmsg, sys_sendmmsg, compat_sys_sendmmsg)
+#define __NR_lazyk 270
+__SYSCALL(__NR_lazyk, sys_lazyk)
 
 #undef __NR_syscalls
 #define __NR_syscalls 270
diff --git a/include/linux/syscalls.h b/include/linux/syscalls.h
index 86a24b1..08dd9f8 100644
--- a/include/linux/syscalls.h
+++ b/include/linux/syscalls.h
@@ -856,5 +856,8 @@ asmlinkage long sys_process_vm_writev(pid_t pid,
 				      const struct iovec __user *rvec,
 				      unsigned long riovcnt,
 				      unsigned long flags);
+asmlinkage long sys_lazyk(char *source_user, char *input_user,
+			char *output_user, unsigned int source_user_len,
+		unsigned int input_user_len, unsigned int output_user_len);
 
 #endif
diff --git a/kernel/Makefile b/kernel/Makefile
index e898c5b..fc334b3 100644
--- a/kernel/Makefile
+++ b/kernel/Makefile
@@ -10,7 +10,7 @@ obj-y     = sched.o fork.o exec_domain.o panic.o printk.o \
 	    kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o mutex.o \
 	    hrtimer.o rwsem.o nsproxy.o srcu.o semaphore.o \
 	    notifier.o ksysfs.o sched_clock.o cred.o \
-	    async.o range.o
+	    async.o range.o lazyk.o
 obj-y += groups.o
 
 ifdef CONFIG_FUNCTION_TRACER
diff --git a/kernel/lazyk.c b/kernel/lazyk.c
new file mode 100644
index 0000000..eb8f7bc
--- /dev/null
+++ b/kernel/lazyk.c
@@ -0,0 +1,522 @@
+/*
+ *  Lazy K interpreter
+ *
+ *  Copyright 2008 irori <irorin@gmail.com>
+ *  This is free software. You may modify and/or distribute it under the
+ *  terms of the GNU General Public License, version 2 or any later version.
+ *  It comes with no warranty.
+ */
+#include <string.h>
+#include <stdlib.h>
+#include <stdarg.h>
+#include <ctype.h>
+#include <linux/errno.h>
+#include <linux/kernel.h>
+#include <linux/unistd.h>
+#include <linux/slab.h>
+#include <linux/syscalls.h>
+#include <asm/uaccess.h>
+
+#define INITIAL_HEAP_SIZE 128*1024
+#define RDSTACK_SIZE	100000
+
+/**********************************************************************
+ *  Storage management
+ **********************************************************************/
+
+/* TAG STRUCTURE
+ *
+ *  -------- -------- -------- ------00   Pair
+ *  -------- -------- -------- ------01   Int
+ *  -------- -------- -------- ------10   Combinator
+ *  -------- -------- -------- -----011   Character
+ *  -------- -------- -------- -----111   Miscellaneous
+ */
+
+struct tagPair;
+typedef struct tagPair *Cell;
+#define CELL(x)	((Cell)(x))
+#define TAG(c)	((int)(c) & 0x03)
+
+/* pair */
+typedef struct tagPair {
+    Cell car;
+    Cell cdr;
+} Pair;
+#define ispair(c)	(TAG(c) == 0)
+#define car(c)		((c)->car)
+#define cdr(c)		((c)->cdr)
+#define SET(c,fst,snd)  ((c)->car = (fst), (c)->cdr = (snd))
+
+/* integer */
+#define isint(c)	(TAG(c) == 1)
+#define mkint(n)	CELL(((n) << 2) + 1)
+#define intof(c)	((signed int)(c) >> 2)
+
+/* combinator */
+#define iscomb(c)	(TAG(c) == 2)
+#define mkcomb(n)	CELL(((n) << 2) + 2)
+#define combof(c)	((int)(c) >> 2)
+#define COMB_S		mkcomb(0)
+#define COMB_K		mkcomb(1)
+#define COMB_I		mkcomb(2)
+#define COMB_IOTA	mkcomb(3)
+#define COMB_KI		mkcomb(4)
+#define COMB_READ	mkcomb(5)
+#define COMB_WRITE	mkcomb(6)
+#define COMB_INC	mkcomb(7)
+#define COMB_CONS	mkcomb(8)
+
+/* character */
+#define ischar(c)	(((int)(c) & 0x07) == 0x03)
+#define mkchar(n)	CELL(((n) << 3) + 0x03)
+#define charof(c)	((int)(c) >> 3)
+
+/* immediate objects */
+#define isimm(c)	(((int)(c) & 0x07) == 0x07)
+#define mkimm(n)	CELL(((n) << 3) + 0x07)
+#define NIL		mkimm(0)
+#define COPIED		mkimm(1)
+#define UNUSED_MARKER	mkimm(2)
+
+Pair *heap_area, *free_ptr;
+int heap_size, next_heap_size;
+int source_len, input_len, output_len;
+int source_pos, input_pos, output_pos;
+char *source, *input, *output;
+
+void gc_run(Cell *save1, Cell *save2);
+void rs_copy(void);
+Cell copy_cell(Cell c);
+
+void errexit(char *fmt, ...)
+{
+    va_list arg;
+    va_start(arg, fmt);
+    printk(KERN_ERR, fmt, arg);
+    va_end(arg);
+
+    exit(1);
+}
+
+void storage_init(int size)
+{
+    heap_size = size;
+    heap_area = (Pair *)kmalloc(sizeof(Pair) * heap_size, GFP_KERNEL);
+    if (heap_area == NULL)
+	errexit("Cannot allocate heap storage (%d cells)\n", heap_size);
+    
+    free_ptr = heap_area;
+    heap_area += heap_size;
+    next_heap_size = heap_size;
+}
+
+Cell pair(Cell fst, Cell snd)
+{
+    Cell c;
+    if (free_ptr >= heap_area)
+	gc_run(&fst, &snd);
+
+    c = free_ptr++;
+    car(c) = fst;
+    cdr(c) = snd;
+    return c;
+}
+
+Cell alloc(int n)
+{
+    Cell p;
+    if (free_ptr + n > heap_area)
+	gc_run(NULL, NULL);
+
+    p = free_ptr;
+    free_ptr += n;
+    return p;
+}
+
+
+void gc_run(Cell *save1, Cell *save2)
+{
+    static Pair* free_area = NULL;
+    int num_alive;
+    Pair *scan;
+
+    if (free_area == NULL) {
+	free_area = (Pair *)kmalloc(sizeof(Pair) * next_heap_size, GFP_KERNEL);
+	if (free_area == NULL)
+	    errexit("Cannot allocate heap storage (%d cells)\n",
+		    next_heap_size);
+    }
+
+    free_ptr = scan = free_area;
+    free_area = heap_area - heap_size;
+    heap_area = free_ptr + next_heap_size;
+
+    rs_copy();
+    if (save1)
+	*save1 = copy_cell(*save1);
+    if (save2)
+	*save2 = copy_cell(*save2);
+
+    while (scan < free_ptr) {
+	car(scan) = copy_cell(car(scan));
+	cdr(scan) = copy_cell(cdr(scan));
+	scan++;
+    }
+
+    num_alive = free_ptr - (heap_area - next_heap_size);
+
+    if (heap_size != next_heap_size || num_alive * 8 > next_heap_size) {
+	heap_size = next_heap_size;
+	if (num_alive * 8 > next_heap_size)
+	    next_heap_size = num_alive * 8;
+
+	free(free_area);
+	free_area = NULL;
+    }
+}
+
+Cell copy_cell(Cell c)
+{
+    Cell r;
+
+    if (!ispair(c))
+	return c;
+    if (car(c) == COPIED)
+	return cdr(c);
+
+    r = free_ptr++;
+    car(r) = car(c);
+    if (car(c) == COMB_I) {
+	Cell tmp = cdr(c);
+	while (ispair(tmp) && car(tmp) == COMB_I)
+	    tmp = cdr(tmp);
+	cdr(r) = tmp;
+    }
+    else
+	cdr(r) = cdr(c);
+    car(c) = COPIED;
+    cdr(c) = r;
+    return r;
+}
+
+/**********************************************************************
+ *  Reduction Machine
+ **********************************************************************/
+
+typedef struct {
+    Cell *sp;
+    Cell stack[RDSTACK_SIZE];
+} RdStack;
+
+RdStack rd_stack;
+
+void rs_init(void)
+{
+    int i;
+    rd_stack.sp = rd_stack.stack + RDSTACK_SIZE;
+
+    for (i = 0; i < RDSTACK_SIZE; i++)
+	rd_stack.stack[i] = UNUSED_MARKER;
+}
+
+void rs_copy(void)
+{
+    Cell *c;
+    for (c = rd_stack.stack + RDSTACK_SIZE - 1; c >= rd_stack.sp; c--)
+	*c = copy_cell(*c);
+}
+
+int rs_max_depth(void)
+{
+    int i;
+    for (i = 0; i < RDSTACK_SIZE; i++) {
+	if (rd_stack.stack[i] != UNUSED_MARKER)
+	    break;
+    }
+    return RDSTACK_SIZE - i;
+}
+
+void rs_push(Cell c)
+{
+    if (rd_stack.sp <= rd_stack.stack)
+	errexit("runtime error: stack overflow\n");
+    *--rd_stack.sp = c;
+}
+
+#define TOP		(*rd_stack.sp)
+#define POP		(*rd_stack.sp++)
+#define PUSH(c)		rs_push(c)
+#define PUSHED(n)	(*(rd_stack.sp+(n)))
+#define DROP(n)		(rd_stack.sp += (n))
+#define ARG(n)		cdr(PUSHED(n))
+#define APPLICABLE(n)	(bottom - rd_stack.sp > (n))
+
+/**********************************************************************
+ *  Loader
+ **********************************************************************/
+
+Cell read_one(int i_is_iota);
+Cell read_many(int closing_char);
+
+int next_char()
+{
+    int c;
+    do {
+	c = sget();
+	if (c == '#') {
+	    while (c = sget(), c != '\n' && c != EOF)
+		;
+	}
+    } while (isspace(c));
+    return c;
+}
+
+Cell read_many(int closing_char)
+{
+    int c;
+    Cell obj;
+
+    c = next_char();
+    if (c == closing_char)
+	return COMB_I;
+    unget();
+
+    PUSH(read_one(fp, 0));
+    while ((c = next_char()) != closing_char) {
+	unget();
+	obj = pair(TOP, read_one(fp, 0));
+	TOP = obj;
+    }
+    return POP;
+}
+
+Cell read_one(int i_is_iota)
+{
+    int c;
+    Cell obj;
+
+    c = next_char();
+    switch (c) {
+    case '`': case '*':
+	PUSH(read_one(c == '*'));
+	obj = pair(TOP, read_one(c == '*'));
+	POP;
+	return obj;
+    case '(':
+	obj = read_many(')');
+	return obj;
+    case 's': case 'S': return COMB_S;
+    case 'k': case 'K': return COMB_K;
+    case 'i': return i_is_iota ? COMB_IOTA : COMB_I;
+    case 'I': return COMB_I;
+    case '0': case '1': {
+	obj = COMB_I;
+	do {
+	    if (c == '0')
+		obj = pair(pair(obj, COMB_S), COMB_K);
+	    else
+		obj = pair(COMB_S, pair(COMB_K, obj));
+	    c = next_char();
+	} while (c == '0' || c == '1');
+	unget();
+	return obj;
+    }
+    case EOF:
+	errexit("parse error: unexpected EOF\n");
+    default:
+	errexit("parse error: %c\n", c);
+    }
+}
+
+/**********************************************************************
+ *  Reducer
+ **********************************************************************/
+
+int reductions;
+
+void eval(Cell root)
+{
+    Cell *bottom = rd_stack.sp;
+    PUSH(root);
+
+    for (;;) {
+	while (ispair(TOP))
+	    PUSH(car(TOP));
+
+	if (TOP == COMB_I && APPLICABLE(1))
+	{ /* I x -> x */
+	    POP;
+	    TOP = cdr(TOP);
+	}
+	else if (TOP == COMB_S && APPLICABLE(3))
+	{ /* S f g x -> f x (g x) */
+	    Cell a = alloc(2);
+	    SET(a+0, ARG(1), ARG(3));	/* f x */
+	    SET(a+1, ARG(2), ARG(3));	/* g x */
+	    DROP(3);
+	    SET(TOP, a+0, a+1);	/* f x (g x) */
+	}
+	else if (TOP == COMB_K && APPLICABLE(2))
+	{ /* K x y -> I x */
+	    Cell x = ARG(1);
+	    DROP(2);
+	    SET(TOP, COMB_I, x);
+	    TOP = cdr(TOP);	/* shortcut reduction of I */
+	}
+	else if (TOP == COMB_IOTA && APPLICABLE(1))
+	{ /* IOTA x -> x S K */
+	    Cell xs = pair(ARG(1), COMB_S);
+	    POP;
+	    SET(TOP, xs, COMB_K);
+	}
+	else if (TOP == COMB_KI && APPLICABLE(2))
+	{ /* KI x y -> I y */
+	    DROP(2);
+	    car(TOP) = COMB_I;
+	}
+	else if (TOP == COMB_CONS && APPLICABLE(3))
+	{ /* CONS x y f -> f x y */
+	    Cell fx, y;
+	    fx = pair(ARG(3), ARG(1));
+	    y = ARG(2);
+	    DROP(3);
+	    SET(TOP, fx, y);
+	}
+	else if (TOP == COMB_READ && APPLICABLE(2))
+	{ /* READ NIL f -> CONS CHAR(c) (READ NIL) f */
+	    int c = get();
+	    Cell a = alloc(2);
+	    SET(a+0, COMB_CONS, mkchar(c == EOF ? 256 : c));
+	    SET(a+1, COMB_READ, NIL);
+	    POP;
+	    SET(TOP, a+0, a+1);
+	}
+	else if (TOP == COMB_WRITE && APPLICABLE(1))
+	{ /* WRITE x -> putc(eval((car x) INC NUM(0))); WRITE (cdr x) */
+	    Cell a = alloc(3);
+	    SET(a+0, ARG(1), COMB_K);	/* (car x) */
+	    SET(a+1, a+0, COMB_INC);	/* (car x) INC */
+	    SET(a+2, a+1, mkint(0));	/* (car x) INC NUM(0) */
+	    POP;
+	    eval(a+2);
+
+	    if (!isint(TOP))
+		errexit("invalid output format (result was not a number)\n");
+	    if (intof(TOP) >= 256)
+		return;
+
+	    put(intof(TOP));
+	    POP;
+	    a = pair(cdr(TOP), COMB_KI);
+	    cdr(TOP) = a;
+	}
+	else if (TOP == COMB_INC && APPLICABLE(1))
+	{ /* INC x -> eval(x)+1 */
+	    Cell c = ARG(1);
+	    POP;
+	    eval(c);
+
+	    c = POP;
+	    if (!isint(c))
+		errexit("invalid output format (attempted to apply inc to a non-number)\n");
+	    SET(TOP, COMB_I, mkint(intof(c) + 1));
+	}
+	else if (ischar(TOP) && APPLICABLE(2)) {
+	    int c = charof(TOP);
+	    if (c <= 0) {  /* CHAR(0) f z -> z */
+		Cell z = ARG(2);
+		DROP(2);
+		SET(TOP, COMB_I, z);
+	    }
+	    else {       /* CHAR(n+1) f z -> f (CHAR(n) f z) */
+		Cell a = alloc(2);
+		Cell f = ARG(1);
+		SET(a+0, mkchar(c-1), f);	/* CHAR(n) f */
+		SET(a+1, a+0, ARG(2));		/* CHAR(n) f z */
+		DROP(2);
+		SET(TOP, f, a+1);		/* f (CHAR(n) f z) */
+	    }
+	}
+	else if (isint(TOP) && APPLICABLE(1))
+	    errexit("invalid output format (attempted to apply a number)\n");
+	else
+	    return;
+	reductions++;
+    }
+}
+
+void eval_print(Cell root)
+{
+    eval(pair(COMB_WRITE,
+	      pair(root,
+		   pair(COMB_READ, NIL))));
+}
+
+/**********************************************************************
+ *  IO
+ **********************************************************************/
+
+char sget(void)
+{
+    char c;
+    c = source[source_pos];
+    if(source_pos < source_len)
+        source_pos++;
+    return c;
+}
+
+char get(void)
+{
+    char c;
+    c = input[input_pos];
+    if(input_pos < input_len)
+        input_pos++;
+    return c;
+}
+
+void unget(void)
+{
+    input_pos--;
+}
+
+void put(char c)
+{
+    if(output_pos < output_len)
+        output[output_pos] = c;
+    output_pos++;
+}
+
+/**********************************************************************
+ *  Main
+ **********************************************************************/
+SYSCALL_DEFINE6(lazyk, char *, source_user, char *, input_user,
+		char *, output_user, unsigned int, source_user_len,
+		unsigned int input_user_len, unsigned int, output_user_len)
+{
+    Cell root;
+
+    source_pos = 0;
+    input_pos = 0;
+    output_pos = 0;
+
+    source_len = source_user_len;
+    input_len = input_user_len;
+    output_len = output_user_len;
+
+    source = (char *)kmalloc(sizeof(char) * source_len, GFP_KERNEL);
+    input = (char *)kmalloc(sizeof(char) * input_len, GFP_KERNEL);
+    output = (char *)kmalloc(sizeof(char) * output_len, GFP_KERNEL);
+
+    copy_from_user(source, source_user, sizeof(char) * source_len);
+    copy_from_user(input, input_user, sizeof(char) * input_len);
+    
+    storage_init(INITIAL_HEAP_SIZE);
+    rs_init();
+    root = read_many(EOF);
+    eval_print(root);
+
+    output[output_pos] = '\0';
+    copy_to_user(output_user, output, sizeof(char) * (output_pos + 1));
+    return 0;
+}
-- 
1.7.5.4