Step 1:

Step 2:

Step 3:

Step 4:

I was searching for a simple way of experimenting with Turing machines for a small course I will give, but most of the software out there is either too complicated or has restrictions, like a predefined alphabet. So I hacked together a small turing machine:

(defun run-turing-machine
  (statelist current-state-name band bandptr)
   (let* ((bandlen (length band))
	  (cstate (cdr (assoc current-state-name statelist)))
	  (calpha (elt band bandptr))
	  (cdo (cdr (assoc calpha cstate)))
	  (do-write (car cdo))
	  (do-move (cadr cdo))
	  (do-goto (caddr cdo)))
     (setf (elt band bandptr) do-write)
     (incf bandptr (cond ((eql do-move 'R) 1)
                         ((eql do-move 'L) -1)
                         ((eql do-move 'S) 0)))
     (dotimes (i 70)
       (format t "~d" (elt band (+ i bandptr -35))))
     (format t "~%")
     (if (eql do-goto 'HALT) nil
	 (run-turing-machine statelist do-goto band bandptr))))

As it is very short, it is very easy to customize, so maybe it is the right thing for other people who are able to use lisp and want something similar. Which is why I am blogging about it, even though it is nothing special.

The code should be self-explanatory, as an example, the following is a machine which increases a dual number (consisting of 0s and 1s, bounded by 2 in the beginning and 3 in the end), and its output:

(run-turing-machine 
 '(
  (anf (0 2 S HALT) (1 2 S HALT) (2 2 R zu3))
  (zu3 (0 0 R zu3) (1 1 R zu3) (3 3 L letzteziffer))
  (letzteziffer (0 1 L andenanf) (1 0 L letzteziffer) (2 1 L anf))
  (andenanf (0 0 L andenanf) (1 1 L andenanf) (2 2 S HALT))
 )
 'anf
 (make-array '(100) :initial-contents
 '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 1 3 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)) 50)

0000000000000000000000000000000000211111300000000000000000000000000000
0000000000000000000000000000000002111113000000000000000000000000000000
0000000000000000000000000000000021111130000000000000000000000000000000
0000000000000000000000000000000211111300000000000000000000000000000000
0000000000000000000000000000002111113000000000000000000000000000000000
0000000000000000000000000000021111130000000000000000000000000000000000
0000000000000000000000000000002111113000000000000000000000000000000000
0000000000000000000000000000000211110300000000000000000000000000000000
0000000000000000000000000000000021110030000000000000000000000000000000
0000000000000000000000000000000002110003000000000000000000000000000000
0000000000000000000000000000000000210000300000000000000000000000000000
0000000000000000000000000000000000020000030000000000000000000000000000
0000000000000000000000000000000000001000003000000000000000000000000000
0000000000000000000000000000000000021000003000000000000000000000000000

Na also es geht doch: Eine dreizehnjährige die im Internet sexuell belästigt wurde hat dies zur Anzeige gebracht.

Zitat: “So muss es laufen“, sagte ein Sprecher.

Ja, das ist genau das was ich mich so oft frage. Man sagt seinen Kindern auch, dass sie nicht zu Fremden ins Auto steigen sollen, und auch nicht mit Fremden mitgehen sollen. Wieso kann man ihnen nicht auch so einen Umgang mit dem Internet beibringen?

Es ist doch wirklich nicht so schwer: Wenn dich jemand belästigt sag es weiter, sag niemandem deine Adresse, und treffe dich nie mit jemanden den du nur aus dem Internet kennst ohne Begleitung. Einfache Regeln, die das Netz wirklich sicherer machen. Und das ohne Zensurmaßnahmen und Vorratsdatenspeicherung.

Ich frage es mich immer wieder. Die Programmierung scheint immernoch als akademische Disziplin zu gelten. Dabei regen sich die Leute immer wieder auf, dass das Informatik-Studium zu theoretisch dafür ist. Ich meine damit nicht die Elfenbeinturmschwingereien zwischen den theoretischen Informatikern und denen die die Informatik als reine Ingenieurswissenschaft ansehen, ich sehe hier den klaren Unterschied zwischen Fachinformatik die man an einer FH lernt und universitärer Informatik. Nein, ich meine damit das bloße Programmieren als solches.

Wieso ist "Programmierer" kein Handwerk, wie Bäcker, Maurer, Friseur? So normal mit Ausbildung, Meisterbrief, etc.? Man würde damit einen Haufen Nervensägen von der Uni fernhalten, andererseits einem Haufen von Real- und Hauptschülern eine zusätzliche Berufschance geben, die garnicht so schlecht ist.

Was muss man als Programmierer tun? Wohl in erster Linie implementieren was Andere einem sagen. Die Programmierarbeiten erledigen, die sonst keiner machen will. Klar, das ist das Los der Handwerker, man muss auch mal Drecksarbeit machen (ist aber auch im akademischen Bereich nicht anders, sieht nur etwas anders aus). Was muss man dafür können?

Sicherlich ist die Kenntnis von mehreren Programmiersprachen und Software-Systemen notwendig. Das Wissen um effiziente Algorithmen ebenfalls. Ein wenig Theorie ist sicher auch nicht schlecht, allerdings kann man das sehr weit herunterschrauben, denn das meiste Theoretische kann man (Fach)Informatikern überlassen.

Programmieren kann man jedenfalls gut in Eigenregie lernen, und die notwendigen Kenntnisse, um im unternehmerischen Bereich Fuß zu fassen, kann man wohl am Besten in Unternehmen lernen. Es wäre eigentlich ein hervorragender Handwerksberuf. Mir ist aber nicht bekannt, dass es einen solchen gibt.

W00t. Soon there will be eatable tomatoes! Remember that the whole plant looked like this in the begining, and like this halfways. Now it looks like this:

Awesome!

I forgot to throw away the rest of my noodle soup a few days ago. The result was not as gross as I expected. It resulted in an interesting structure:

At least the ext[2-4] filesystems support files with holes. They can be created in several ways, one possibility is the seek-argument of the dd command:

$ dd if=/dev/urandom of=test bs=4096 count=10 seek=10
10+0 records in
10+0 records out
40960 bytes (41 kB) copied, 0.0126733 s, 3.2 MB/s
$ wc -c test
81920 test

So I was interested in whether it is possible to actally find these holes. ZFS and XFS have their own API for that.

For ext*, there is also a possibility to find holes. Basing on the FIBMAP Ioctl (and similar), you need to have the CAP_SYS_RAWIO capability (that is, usually you have to be root). If you only want to watch the holes in the files, you can use for example hdparm (as shown here):

$ sudo hdparm --fibmap test

test:
 filesystem blocksize 4096, begins at LBA 0; assuming 512 byte sectors.
 byte_offset  begin_LBA    end_LBA    sectors
       40960    8928120    8928199         80

Another possibility is to use the filefrag-utility, which is contained in the debian squeeze package e2fsprogs (as shown here):

$ sudo filefrag -v test
Filesystem type is: ef53
File size of test is 81920 (20 blocks, blocksize 4096)
 ext logical physical expected length flags
   0      10  1116015              10 eof
test: 2 extents found

Now if you really want to use your own program, here is a nice example code I found, on which I based my own code:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include <fcntl.h>
#include <sys/ioctl.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <linux/fs.h>


int main (int argc, char* argv[]) {
  int fd, blocknum, blocksize;
  struct stat fileinfo;

  if (argc < 1) {
    fprintf(stderr, "Syntax Errof\n");
    exit(EXIT_FAILURE);
  }

  if ((fd = open(argv[1], O_RDONLY)) < 0) {
    int errnum = errno;
    fprintf(stderr, "Cannot open '%s': %s\n", argv[1], strerror(errnum));
    exit(EXIT_FAILURE);
  }

  if (ioctl(fd, FIGETBSZ, &blocksize) < 0 ) {
    int errnum = errno;
    fprintf(stderr, "Cannot get blocksize: %s\n", strerror(errnum));
    exit(EXIT_FAILURE);
  }

  if (fstat(fd, &fileinfo) < 0) {
    int errnum = errno;
    fprintf(stderr, "Stat failed: %s\n", strerror(errnum));
    exit(EXIT_FAILURE);
  }

  blocknum = (fileinfo.st_size + blocksize - 1) / blocksize;

  printf("Filename: %s\nBlocksize: %d\nBlocknum: %d\n",
         argv[1], blocksize, blocknum);
 
  int i;
  for (i = 0; i < blocknum; i++) {
    int block = i;
    if (ioctl(fd, FIBMAP, &block)) {
      printf("ioctl failed: %s\n", strerror(errno));
    }
    printf("%10d\t", block);
  }
  close(fd);
  printf("\n");
  exit(EXIT_SUCCESS);
}

The output:

$ sudo ./fibmap test
Filename: test
Blocksize: 4096
Blocknum: 20
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
   1116015
   1116016
   1116017
   1116018
   1116019
   1116020
   1116021
   1116022
   1116023
   1116024

And that is indeed a list of ten null-pointers and ten consecutive blocks.

It has been a while, but now I have green tomatoes:

Amazing.

External Content not shown. Further Information. Tröööt! There is a new protocol joining the small group of network protocols which I like. The Network Block Device protocol. It seems like it is exactly as complicated as it needs to be. It just has a major disadvantage: It is not well documented. Surprisingly, the German Wikipedia has a quite nice article about NBD, and this article is not that bad! It even has a protocol documentation - as one wishes when consulting an encyclopedia. (So it will probably be deleted soon.)

Actually, I had a closer look at NBD while I was actually looking for something else, but the implementation of an NBD server took some time. I wanted to create an NBD server which allocates a specified amount of memory and populates it as block device - just as a proof of concept telling me that I have "understood" the protocol and that I am able to implement it.

I began with C and finally succeeded, after finding out that every adress has to be sent in network byte order, and finding some useful header files like <linux/nbd.h>. Still, my C implementation has some bug, and as I did not have any special aim, I re-implemented everything in Common Lisp. The code can be found at GitHub (exercise: find out where its name comes from).

Its only dependency so far is usocket, and as I did not yet create an asd file it has to be loaded manually, which I do via Quicklisp.

CL-USER> (ql:quickload "usocket")

Then I load my file and start a server with a 10 megabyte block device.

CL-USER> (load #P"~/projects/7-chloro-4-nitrobenzofurazan/nbdserver.lisp")
CL-USER> (defvar *pool* (run-rampool 13337 (* 10 1024 1024)))

This will block until an nbd client connected and returned again. So let us connect via the linux nbd client. We create an ext2 filesystem and then mount it and create a file GANS with the content NILPFERD in the shell

# nbd-client localhost 13337 /dev/nbd0
Negotiation: ..size = 10240KB
bs=1024, sz=10240
# mkfs.ext2 /dev/nbd0
[...]
# mount /dev/nbd0 /mnt
# echo "NILPFERD" > /mnt/GANS
# sync
# cat /mnt/GANS
NILPFERD

Then we unmount it again and detatch the device.

# umount /mnt
# nbd-client -d /dev/nbd0
Disconnecting: que, disconnect, sock, done

Now, the REPL is free again, and *pool* contains the data. We have just created an ext2 filesystem on a lisp vector. Now we should find the word "NILPFERD" in *pool*, and indeed

CL-USER> (search (map 'list #'char-code "NILPFERD") *pool*)
2098176

Now let us see what happens if we replace this string (as this returns the whole *pool*, we set *print-length* first):

CL-USER> (setf *print-length* 10)
10
CL-USER> (replace *pool* (map 'list #'char-code "nilpferd") :start1 2098176)
#(0 0 0 0 0 0 0 0 0 0 ...)

Now, let us re-run the nbd-server with the modified *pool*

CL-USER> (run-rampool 13337 (* 10 1024 1024) *pool*)

And attatch and mount it again

# nbd-client localhost 13337 /dev/nbd0
Negotiation: ..size = 10240KB
bs=1024, sz=10240
# mount /dev/nbd0 /mnt

Now, about the file:

# cat /mnt/GANS
nilpferd

Yep, it is indeed lowercase now. Which is ... nice ... somehow. Though useless, of course.

Besides that, I found an implementation of a server in python, though I have not tested it. Same for this Java implementation.

Unfortunately, there seems to be a lack of clients. A port to some other Unices and Windows would be nice. Especially, looking at these implementations of block device drivers, there should be people who can easily implement an NBD Client for Windows.