Can you provide: 

df -h /tmp

and

df -i

That's what I've already given. And there *is* enough space.

'df -h /tmp' is to confirm that your /tmp is in fact on that partition that you think it is. Perhaps it's a tmpfs? Perhaps it's on another partition? That command will tell us. 

'df -i' is to list free inode counts on your devices. If you are out of inodes you can't create new files, no matter how much free space is available on the disk. This will tell us that. 

Rest assured I didn't ask for the exact info you already provided, or I would just use that. ;)

$ df -h /tmp/
Filesystem                  Size  Used Avail Use% Mounted on
/dev/mapper/vg_bigbox-root  1,2T  1,1T  152G  88% /
$ $ df -i | awk '{print $5}' | sort -u
1%
4%
IUse%
$

Curious. 

Anything in 'dmesg' thats filesystem related? 
What filesystem type is your / and the fs that you are restoring from? ext4?

(In reply to comment #5)
> Anything in 'dmesg' thats filesystem related? 
nope. Neither local nor remote.

> What filesystem type is your / and the fs that you are restoring from? ext4?
from ext3
to xfs

but as I've said, I've got the same problem on a different machine trying to restore locally, i.e. from ext3 to ext3.

Hm. But from what I can read from the verbose output, the problem originates on the remote system instead of on the local system what I initially thought.

Fri Feb 17 21:55:21 2012  Server received (0): 'Processing changed file cgi-bin/mathtex/mathtex.log'
Fri Feb 17 21:55:21 2012  Server sending (0): None
Fri Feb 17 21:55:21 2012  Client received (0): None
Fri Feb 17 21:55:21 2012  Processing changed file cgi-bin/mathtex/mathtex.log
Fri Feb 17 21:55:21 2012  Client sending (0): ConnectionRequest: log.Log.log_to_file with 1 arguments
Fri Feb 17 21:55:21 2012  Client sending (0): "Regular copying ('cgi-bin', 'mathtex', 'mathtex.log') to /tmp/fb18-restore-test/cgi-bin/mathtex/rdiff-backup.tmp.1750"
Fri Feb 17 21:55:21 2012  Server received (0): ConnectionRequest: log.Log.log_to_file with 1 arguments
Fri Feb 17 21:55:21 2012  Server received (0): "Regular copying ('cgi-bin', 'mathtex', 'mathtex.log') to /tmp/fb18-restore-test/cgi-bin/mathtex/rdiff-backup.tmp.1750"
Fri Feb 17 21:55:21 2012  Server sending (0): None
Fri Feb 17 21:55:21 2012  Client received (0): None
Fri Feb 17 21:55:21 2012  Regular copying ('cgi-bin', 'mathtex', 'mathtex.log') to /tmp/fb18-restore-test/cgi-bin/mathtex/rdiff-backup.tmp.1750
Fri Feb 17 21:55:21 2012  Client sending (0): ConnectionRequest: log.Log.log_to_file with 1 arguments
Fri Feb 17 21:55:21 2012  Client sending (0): 'Writing file object to /tmp/fb18-restore-test/cgi-bin/mathtex/rdiff-backup.tmp.1750'
Fri Feb 17 21:55:21 2012  Server received (0): ConnectionRequest: log.Log.log_to_file with 1 arguments
Fri Feb 17 21:55:21 2012  Server received (0): 'Writing file object to /tmp/fb18-restore-test/cgi-bin/mathtex/rdiff-backup.tmp.1750'
Fri Feb 17 21:55:21 2012  Server sending (0): None
Fri Feb 17 21:55:21 2012  Client received (0): None
Fri Feb 17 21:55:21 2012  Writing file object to /tmp/fb18-restore-test/cgi-bin/mathtex/rdiff-backup.tmp.1750
Fri Feb 17 21:55:21 2012  Client sending (0): ConnectionRequest: VirtualFile.readfromid with 2 arguments
Fri Feb 17 21:55:21 2012  Client sending (0): 1
Fri Feb 17 21:55:21 2012  Client sending (0): None
Fri Feb 17 21:55:21 2012  Server received (0): ConnectionRequest: VirtualFile.readfromid with 2 arguments
Fri Feb 17 21:55:21 2012  Server received (0): 1
Fri Feb 17 21:55:21 2012  Server received (0): None
Fri Feb 17 21:55:21 2012  Applying patch fb18.sql.2012-02-16T23:29:45+01:00.diff.gz
Fri Feb 17 21:55:31 2012  Exception '[Errno 28] No space left on device' raised of class '<type 'exceptions.IOError'>':
  File "/usr/lib/pymodules/python2.5/rdiff_backup/robust.py", line 32, in check_common_error
    try: return function(*args)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/restore.py", line 468, in get_fp
    Rdiff.write_patched_fp(current_fp, delta_fp, new_fp)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/Rdiff.py", line 73, in write_patched_fp
    rpath.copyfileobj(librsync.PatchedFile(basis_fp, delta_fp), out_fp)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/rpath.py", line 64, in copyfileobj
    outputfp.write(inbuf)

Fri Feb 17 21:55:31 2012  Sending back exception [Errno 28] No space left on device of type <type 'exceptions.IOError'>: 
  File "/usr/lib/pymodules/python2.5/rdiff_backup/connection.py", line 335, in answer_request
    result = apply(eval(request.function_string), argument_list)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/connection.py", line 485, in readfromid
    if length is None: return cls.vfiles[id].read()
  File "/usr/lib/pymodules/python2.5/rdiff_backup/iterfile.py", line 302, in read
    if not self.addtobuffer(): break
  File "/usr/lib/pymodules/python2.5/rdiff_backup/iterfile.py", line 325, in addtobuffer
    try: currentobj = self.iter.next()
  File "/usr/lib/pymodules/python2.5/rdiff_backup/restore.py", line 247, in get_diffs_from_collated
    diff = cls.get_diff(mir_rorp, target_rorp)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/restore.py", line 260, in get_diff
    file_fp = cls.rf_cache.get_fp(expanded_index, mir_rorp)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/restore.py", line 354, in get_fp
    return rf.get_restore_fp()
  File "/usr/lib/pymodules/python2.5/rdiff_backup/restore.py", line 488, in get_restore_fp
    return robust.check_common_error(error_handler, get_fp)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/robust.py", line 32, in check_common_error
    try: return function(*args)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/restore.py", line 468, in get_fp
    Rdiff.write_patched_fp(current_fp, delta_fp, new_fp)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/Rdiff.py", line 73, in write_patched_fp
    rpath.copyfileobj(librsync.PatchedFile(basis_fp, delta_fp), out_fp)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/rpath.py", line 64, in copyfileobj
    outputfp.write(inbuf)

Fri Feb 17 21:55:31 2012  Server sending (0): [Errno 28] No space left on device
Fri Feb 17 21:55:31 2012  Client received (0): [Errno 28] No space left on device
Fri Feb 17 21:55:32 2012  Exception '[Errno 28] No space left on device' raised of class '<type 'exceptions.IOError'>':
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/Main.py", line 304, in error_check_Main
    try: Main(arglist)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/Main.py", line 324, in Main
    take_action(rps)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/Main.py", line 290, in take_action
    elif action == "restore-as-of": Restore(rps[0], rps[1], 1)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/Main.py", line 573, in Restore
    inc_rpath, dest_rp, time)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/restore.py", line 37, in Restore
    TargetS.patch(target, diff_iter)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/restore.py", line 293, in patch
    ITR(diff.index, diff)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/rorpiter.py", line 281, in __call__
    last_branch.fast_process(*args)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/restore.py", line 609, in fast_process
    self.patch_to_temp(rp, diff_rorp, tf)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/restore.py", line 632, in patch_to_temp
    copy_report = rpath.copy(diff_rorp, new)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/rpath.py", line 105, in copy
    if rpin.isreg(): return copy_reg_file(rpin, rpout, compress)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/rpath.py", line 133, in copy_reg_file
    return rpout.write_from_fileobj(rpin.open("rb"), compress = compress)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/rpath.py", line 1195, in write_from_fileobj
    copyfileobj(fp, outfp)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/rpath.py", line 62, in copyfileobj
    inbuf = inputfp.read(blocksize)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/rpath.py", line 1415, in read
    def read(self, length = -1): return self.file.read(length)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/iterfile.py", line 118, in read
    if not self.addtobuffer(): break
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/iterfile.py", line 133, in addtobuffer
    type, data = self.iwf._get()
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/iterfile.py", line 414, in _get
    if not self.buf: self.buf += self.file.read()
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/connection.py", line 518, in read
    return self.connection.VirtualFile.readfromid(self.id, length)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/connection.py", line 450, in __call__
    return apply(self.connection.reval, (self.name,) + args)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/connection.py", line 370, in reval
    if isinstance(result, Exception): raise result

Traceback (most recent call last):
  File "/usr/bin/rdiff-backup", line 30, in <module>
    rdiff_backup.Main.error_check_Main(sys.argv[1:])
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/Main.py", line 304, in error_check_Main
    try: Main(arglist)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/Main.py", line 324, in Main
    take_action(rps)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/Main.py", line 290, in take_action
    elif action == "restore-as-of": Restore(rps[0], rps[1], 1)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/Main.py", line 573, in Restore
    inc_rpath, dest_rp, time)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/restore.py", line 37, in Restore
    TargetS.patch(target, diff_iter)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/restore.py", line 293, in patch
    ITR(diff.index, diff)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/rorpiter.py", line 281, in __call__
    last_branch.fast_process(*args)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/restore.py", line 609, in fast_process
    self.patch_to_temp(rp, diff_rorp, tf)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/restore.py", line 632, in patch_to_temp
    copy_report = rpath.copy(diff_rorp, new)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/rpath.py", line 105, in copy
    if rpin.isreg(): return copy_reg_file(rpin, rpout, compress)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/rpath.py", line 133, in copy_reg_file
    return rpout.write_from_fileobj(rpin.open("rb"), compress = compress)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/rpath.py", line 1195, in write_from_fileobj
    copyfileobj(fp, outfp)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/rpath.py", line 62, in copyfileobj
    inbuf = inputfp.read(blocksize)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/rpath.py", line 1415, in read
    def read(self, length = -1): return self.file.read(length)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/iterfile.py", line 118, in read
    if not self.addtobuffer(): break
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/iterfile.py", line 133, in addtobuffer
    type, data = self.iwf._get()
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/iterfile.py", line 414, in _get
    if not self.buf: self.buf += self.file.read()
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/connection.py", line 518, in read
    return self.connection.VirtualFile.readfromid(self.id, length)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/connection.py", line 450, in __call__
    return apply(self.connection.reval, (self.name,) + args)
  File "/usr/lib64/python2.7/site-packages/rdiff_backup/connection.py", line 370, in reval
    if isinstance(result, Exception): raise result
IOError: [Errno 28] No space left on device

 Fri Feb 17 21:55:32 2012  Exception 'Truncated header string (problem probably originated remotely)' raised of class '<class 'rdiff_backup.connection.ConnectionReadError'>':
  File "/usr/lib/pymodules/python2.5/rdiff_backup/Main.py", line 304, in error_check_Main
    try: Main(arglist)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/Main.py", line 324, in Main
    take_action(rps)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/Main.py", line 278, in take_action
    connection.PipeConnection(sys.stdin, sys.stdout).Server()
  File "/usr/lib/pymodules/python2.5/rdiff_backup/connection.py", line 355, in Server
    self.get_response(-1)
  File "/usr/lib/pymodules/python2.5/rdiff_backup/connection.py", line 315, in get_response
    try: req_num, object = self._get()
  File "/usr/lib/pymodules/python2.5/rdiff_backup/connection.py", line 233, in _get
    raise ConnectionReadError("Truncated header string (problem "

Fri Feb 17 21:55:32 2012  Fatal Error: Lost connection to the remote system

Seems to be trying to unpack and apply fb18.sql.2012-02-16T23:29:45+01:00.diff.gz
Can you look at that file on the sending side? Does it unpack to a size larger than the source/backup volume you have?

okay, my bad. There is a disk space issue on the server side. /tmp/ is too small to handle the data.

Sorry for the noise. But I initially thought that the no disk space left exception was raised on the local side which confused me quite a lot. Plus, I didn't think that /tmp/ would be used at all.

Anyway, feel free to close and remind me to buy you a beer for having burnt your time.

Ah ha. Yeah, I've never run into this, but then I don't think I have had a source volume run out of space like that... 

No problem at all, I am glad we got it tracked down.