moby: os.rename throws exception when renaming directories on lower overlayfs layers

Output of docker version:

Client:
 Version:      1.12.0
 API version:  1.24
 Go version:   go1.6.3
 Git commit:   8eab29e
 Built:        Thu Jul 28 22:11:10 2016
 OS/Arch:      linux/amd64

Server:
 Version:      1.12.0
 API version:  1.24
 Go version:   go1.6.3
 Git commit:   8eab29e
 Built:        Thu Jul 28 22:11:10 2016
 OS/Arch:      linux/amd64

Output of docker info:

Containers: 2
 Running: 0
 Paused: 0
 Stopped: 2
Images: 29
Server Version: 1.12.0
Storage Driver: overlay2
 Backing Filesystem: extfs
Logging Driver: json-file
Cgroup Driver: cgroupfs
Plugins:
 Volume: local
 Network: host bridge null overlay
Swarm: inactive
Runtimes: runc
Default Runtime: runc
Security Options: seccomp
Kernel Version: 4.4.7-1.ng
Operating System: Ubuntu 16.04 LTS
OSType: linux
Architecture: x86_64
CPUs: 8
Total Memory: 15.67 GiB
Name: rovner-qtesting-7
ID: M7UX:OR2K:WJQI:KGPM:XFIJ:UF72:AQ6J:OYUZ:UIBO:6RJZ:LVGN:TT4I
Docker Root Dir: /var/lib/docker
Debug Mode (client): false
Debug Mode (server): false
Registry: https://index.docker.io/v1/
WARNING: No swap limit support
WARNING: No kernel memory limit support
Insecure Registries:
 127.0.0.0/8

Additional environment details (AWS, VirtualBox, physical, etc.):

root@my-host:/# uname -a
Linux my-host 4.4.7-1.ng #1 SMP Fri Apr 15 17:59:44 MSK 2016 x86_64 x86_64 x86_64 GNU/Linux

Steps to reproduce the issue:

• Build image with Dockerfile

FROM ubuntu:14.04
RUN mkdir /foo && touch /foo/bar

Sending build context to Docker daemon 2.048 kB
Step 1 : FROM ubuntu:14.04
 ---> 0ccb13bf1954
Step 2 : RUN mkdir /foo && touch /foo/bar
 ---> Running in dc97258d4d23
 ---> c6216cc93147
Removing intermediate container dc97258d4d23
Successfully built c6216cc93147

• Rename foo to foo2 with python os.rename

root@c18071cd5033:/# python3
Python 3.4.3 (default, Oct 14 2015, 20:28:29)
[GCC 4.8.4] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import os
>>> os.rename('/foo', '/foo2')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OSError: [Errno 18] Invalid cross-device link: '/foo' -> '/foo2'

Describe the results you received: Rename failed with error OSError: [Errno 18] Invalid cross-device link: '/foo' -> '/foo2'

Describe the results you expected: Rename finished successfully