Status update

Not much news to the moment. Except I joined Lisp startup (NovaSparks) and moved to Boston, MA in the middle of November.

Why zero-copy is missing in CL-ZMQ

ZeroMQ can utilize zero-copy technique, which may save a lot of cpu ticks when using large messages. Unfortunately, it's not possible to get this feature to work with supported Common Lisp implementations due to a couple of reasons:

• ZeroMQ uses threads for asynchronous I/O operations on messages. When it finishes all the work with message's data, it calls back Lisp to let it know that data can be safely ripped out.

Unfortunately, not all Lisps can distinguish and handle callback from non-lisp thread. For example, Clozure CL feels good here, but SBCL crashes and LispWorks just hangs.

• Garbage collector may move lisp objects, which are currently used in I/O threads. This leads to image corruption or segmentation fault.

Widely used with-pinned-object technique is not working here, because ZeroMQ operates asynchronously and pinned body can't protect data from GC when it needs to. It's possible to turn off garbage collecting completely or design system in such way, that it won't do gc'ing when it shouldn't. But that's a hard way.

Other possibility is to allocate objects in static area, where garbage collector doesn't move live objects. Some Lisps support this feature, for example AllegroCL, LispWorks and GCL.

If both features (callback from non-lisp thread, objects in static area) are supported by certain Lisp implementation, it's possible then to use zero-copy in CL-ZMQ. Unfortunately, all four Lisps that I use for development and testing (SBCL, Clozure, CLISP and LispWorks) miss this combination.

CL-ZMQ and LispWorks 6

Since yesterday I'm happy user of commercial version of LW.

LW complains about unshadowed symbol `identity'. Yeah, that's strange it wasn't yet catched by 3 other lisps I tested with (sbcl, clisp, ccl). Other minor problem was with `trivial-garbage' library: it uses `hcl:mark-and-sweep', but this function exists only on 32-bit LWs. 64-bit uses `system:marking-gc'. Also `system::hash-table-weak-kind' has a bit different name: `system::hash-table-%weak-kind'.

Otherwise everything works good. LW is officially supported by CL-ZMQ now :)

Hugepages patch

Got something working:

http://paste.lisp.org/display/96287

How to run:

# echo 200 > /sys/kernel/mm/hugepages/hugepages-2048kB/nr_hugepages
# mkdir /dev/huge
# mount -t hugetlbfs none /dev/huge -o size=800M,mode=777
$ sbcl --hugetlbfs-path /dev/huge --huge-pages-nr 200

Here 800 megabytes of memory is prepared for use as huge pages. SBCL has two new command line switches now. If there's something wrong with hugetlbfs, SBCL will fallback to "usual" memory.

To extend feature for other OSes, where POSIX API for hugepages is available, you need to add only few bits:

diff --git a/src/runtime/linux-os.c b/src/runtime/linux-os.c
index 9b2e3cf..386fc25 100644
--- a/src/runtime/linux-os.c
+++ b/src/runtime/linux-os.c
@@ -56,6 +56,8 @@
 #include "cheneygc-internal.h"
 #endif
 
+#include "hugepages.h"
+
 #ifdef LISP_FEATURE_X86
 /* Prototype for personality(2). Done inline here since the header file
  * for this isn't available on old versions of glibc. */
@@ -313,7 +315,10 @@ os_validate(os_vm_address_t addr, os_vm_size_t len)
         addr=under_2gb_free_pointer;
     }
 #endif
-    actual = mmap(addr, len, OS_VM_PROT_ALL, flags, -1, 0);
+    actual = huge_page_validate(addr, len);
+    if (!actual)
+        actual = mmap(addr, len, OS_VM_PROT_ALL, flags, -1, 0);
+
     if (actual == MAP_FAILED) {
         perror("mmap");
         return 0;               /* caller should check this */
@@ -337,6 +342,7 @@ os_validate(os_vm_address_t addr, os_vm_size_t len)
 void
 os_invalidate(os_vm_address_t addr, os_vm_size_t len)
 {
+    huge_page_invalidate(addr, len);
     if (munmap(addr,len) == -1) {
         perror("munmap");
     }

In other words, only new header and small modification of os_validate and os_invalidate are required.

UPD: Garbage collector works much slower with the patch and needs further investigation.

SBCL and huge pages

Yesterday was a lucky day: I compiled SBCL with sb!vm:*backend-page-bytes* = 2097152. There were several problems preventing doing this, but, hopefully, all of them are solved. At least, I'm able to run new core and do everything, what comes in mind, for example, load ZeroMQ2 bindings.

Next step is to teach memory allocator to mmap() pages from hugetlbfs. That will give SBCL real 2mb pages, not 2mb regions composed of 4kb chunks.

Stay tuned!

Hugepages save the kittens

Imagine, we need to read and eval code from some untrusted source. This code may change lisp environment in uncertain way as expected behaviour, but it may also contain error, which stops execution in the middle. This is not what we want: environment should be changed completely or rolled back to previous state.

Naive approach to solve the problem is to fork() lisp image, execute untrusted code in the child (child will be the full clone of parent), return zero in the case of succes and non-zero value otherwise. Parent may check if it's safe to executes code in its environment this way . This is only few lines of code:

(defun rep (expr)
  (eval (read-from-string expr)))

(defun safe-eval (expr)
  (let ((pid (sb-posix:fork)))
    (cond
      ((plusp pid)
       (multiple-value-bind (pid status)
         (sb-posix:waitpid pid 0)
        (declare (ignore pid))
        (when (zerop status)
         (rep expr))))
      ((zerop pid)
       (handler-case
         (rep expr)
        (error ()
          (sb-ext:quit :unix-status 1)))
       (sb-ext:quit :unix-status 0))
      (t
       (error "fork failed~%")))))

It doesn't even matter if child's image completely crashes due to uber-invalid code or compiler's bugs, parent will survive and understand that the code is bad. Next question is: how expensive fork() operation is?

Linux kernel (I'm Linux-only guy) is enough smart not to copy all the process data one-to-one: it uses copy-on-write (COW) technique to separate memory pages of new process from respective pages of old process only at the moment of page changes. So, basically, kernel duplicates task structures for the new process, and that's all.

Unfortunately, modern lisps (like SBCL) creates huge image up to tens megabytes, and it may grow up to gigabytes. In-kernel VMA chains, which describes how much memory the process has and how this memory is organized in address space of process, may grow significantly. The cost of fork operation grows respectively (not to mention, overall system slowdowns as well). One of accessible and acceptable solution is to use huge pages in those programs, which manipulate with a large memory portions.

Normal page size is equal to 4 kilobytes on most of systems. However, modern hardware allows to set page size for part of memory to larger size. For example, x86-64 supports huge pages of size 2 megabytes.

I wrote a small test, which allocates portions of memory with normal and huge page size, and does fork(). Let see the results:

Gosh!... Fork of a process with normal-sized pages is soooo slow! And huge pages definitely rocks!

I wish SBCL built-in memory manager to work with hugepages...

New Gmail's COMPRESS=DEFLATE feature

Two days ago I noticed that Google implemented RFC4978 for their mail service. In short, Gmail is able now to compress all traffic with deflate method. Wanderlust shall support this feature!

Unfortunately, my attempts to find ready-to-use deflate/inflate code in Emacs Lisp have been failed. Even it is impossible to access zlib functions from Emacs Lisp (Emacs links with -lz) without hacking Emacs first. So I decided to write a wrapper, which will stay in between of Emacs and gnutls-cli, which I use for TLS. Gnutls-cli is fully text-oriented client, so it has problem with handling binary data from standard input. I did a small patch to fix it:

--- src/cli.c.orig      2009-06-02 20:59:32.000000000 +0200
+++ src/cli.c   2010-01-24 17:48:05.636222100 +0100
@@ -749,7 +749,8 @@ after_handshake:
 
       if (FD_ISSET (fileno (stdin), &rset))
        {
-         if (fgets (buffer, MAX_BUF, stdin) == NULL)
+         int bytes;
+         if ((bytes = read (fileno(stdin), buffer, MAX_BUF)) < 0)
            {
              if (hd.secure == 0)
                {
@@ -778,11 +779,13 @@ after_handshake:
          if (crlf != 0)
            {
              char *b = strchr (buffer, '\n');
-             if (b != NULL)
+             if (b != NULL) {
                strcpy (b, "\r\n");
+               bytes++;
+             }
            }
 
-         ret = socket_send (&hd, buffer, strlen (buffer));
+         ret = socket_send (&hd, buffer, bytes);
 
          if (ret > 0)
            {

The wrapper is mostly functional now, but I need to beatify it first before releasing to public.

As for results... Deflate is known for its ability to recognize similar patterns and replace them with only one pattern definition and references for the rest. I tried to do uid search uid 1:* undeleted in my Inbox folder. At first, Gmail sent me 12401 byte of deflated text. For the same query, sent for 2nd time, it returned only 581 byte, which consisted mostly of the references to already received patterns. Usual uncompressed text is of 25993 bytes. That's pretty amazing!