430. Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example Input: 1—2—3—4—5—6–NULL | 7—8—9—10–NULL | 11–12–NULL

Output: 1-2-3-7-8-11-12-9-10-4-5-6-NULL

A typical recursive function can do the work.

Definition for a Node.
"""
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""
class Solution:

    def addnode(self,  current):

        while True:

            if current.next is None and current.child is None:
                return current

            if current.child != None:
                current.child.prev = current
                comesback =  current.next
                current.next = current.child
                end = self.addnode(current.child)
                current.child = None
                end.next = comesback
                if comesback is not None:
                    comesback.prev = end

            current = current.next


    def flatten(self, head: 'Node') -> 'Node':
        if head is None:
            return head
        self.newhead  = head
        self.currentnode = head
        self.addnode(self.currentnode)


        return self.newhead

300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Here is the DP version

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

300. Longest Increasing Subsequence
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:

        if len(nums)==0:
            return 0

        Len = [0]*len(nums)


        for j in range(0,len(nums)):
            maxvalue = [0]
            for i in range(0, j):
                if nums[i]< nums[j]:
                    maxvalue.append(Len[i])


            output = max(maxvalue) +1
            Len[j] = output

        return max(Len)

binary search version. However, here I just implement the linear search version. change range(1,len(nums)) to the binary search to achieve n(logn) time complexity.

        class Solution:
            def lengthOfLIS(self, nums: List[int]) -> int:

                if len(nums) == 0:
                    return 0

                lastpos = [0]
                lastpos.append(nums[0])
                length = 1
                for i in range(1, len(nums)):
                    currentval = nums[i]
                    if currentval <= lastpos[-1]:

                        for i in range(0, len(lastpos)):
                            if currentval <= lastpos[i]:
                                break

                        lastpos[i] = currentval
                    else:
                        lastpos.append(currentval)


                print(lastpos)

                return len(lastpos)-1

19. Remove Nth Node From End of List

problem discription:

Given a linked list, remove the n-th node from the end of list and return its head.

Solution:

Firstly, have two pointers $p_1$, $p_2$. let p1,p2 = head, head. Let p2 goes nth before p1, then, move p1,p2 simutanlously. When p2 reaches the end. p1 points to the nth node from the end of the list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        p1,p2 = head,head
        for i in range(0, n):
            if p2 == None:
                break
            p2 = p2.next

        if p2 == None:
            head = head.next
            return head
        while True:

            p2 = p2.next
            if p2 == None:
                break
            p1 = p1.next


        p1.next = p1.next.next

        return head

400. Nth Digit

problem discription:

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Solution:

If n is smaller than 10, just return. then, we seperate the digits to 2 bits(10), 3 bits(1000) blocks. We find which blocks the result nuber in and then calcualte the offset in that block.

class Solution:
    def findNthDigit(self,n):
        if n < 10:
            return n

        accum = 9

        for i in range(1, n):
            all = (10 ** (i+1)-(10**i)) * (i+1)
            if accum + all > n:
                break
            accum += all
        gap = n- accum
        offset = gap%(i+1)
        which = (gap - offset)//(i+1)

        if offset == 0:
            number = 10 ** (i) + which-1
            val = str(number)[-1]
        else:
            number = 10**(i) + which-1
            found = number+1
            val = str(found)[offset-1]

        return int(val)

878. Nth Magical Number

problem discription:

A positive integer is magical if it is divisible by either A or B. Return the N-th magical number. Since the answer may be very large, return it modulo $10^9 + 7$.

Solution:

It A is a factor of B. return N*A elsewise, find the LCM of A,B. and the the LCM also indicate the number of elements in the period list(in program it is base list). For instance, with 5 and 8

base = [5,8,10,15,16,20,25,28,30,35,36,40] and the element in base is LCM/A +LCM/B-1

we calculate the repetions of the list for the given N and the offset in that repetion and return.

class Solution:

    def dowork(self,N,A,B):
        if B % A == 0:
            return N * A

        lcm = A*B//math.gcd(A,B)
        elementlen = lcm//A + lcm//B-1

        i=1
        j=1
        counter = 0
        base = []
        while True:
            if counter == elementlen:
                break
            av = i*A
            bv = j*B
            if av < bv:
                base.append(av)
                i+=1
                counter +=1
            else:
                base.append(bv)
                j+=1
                counter +=1


        block = N//elementlen
        offset = N%elementlen

        if offset == 0:
            return lcm*block

        else:
            val = lcm*block
            val += base[offset-1]

        return val



    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        modval = 1000000000+7
        if A > B:
            A,B = B,A

        ret = self.dowork(N,A,B)
        return ret%modval

1. Introduction

zk-Snark now is now be discussed by many people, however, few people understand what is the zk-Snark and how does it works. Just before the Christmas, I was lucky to have time to understand the whole picture of zk-Snark. If you find any mistake, I appreciate that you could tell me and also teach me:)

In this post, I would like to explain what is zk-snark, what problems does zk-snark try to solve. How to build a zk-snark system from the scratch.

The reading materials that related with this post is at:

[1] Exploring Elliptic Curve Pairings: https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627

[2] Quadratic Arithmetic Programs: from Zero to Hero: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

[3] zk-snark explained_basic_principles: https://blog.coinfabrik.com/wp-content/uploads/2017/03/zkSNARK-explained_basic_principles.pdf

[4] Pinocchio: Nearly Practical Verifiable Computation: https://eprint.iacr.org/2013/279.pdf

[5] Quadratic Span Programs and Succinct NIZKs without PCPs https://eprint.iacr.org/2012/215.pdf

[6] Zerocash: Decentralized Anonymous Payments from Bitcoinhttp://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf

[7] zk-snark in a nutshell: https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/

[8] Bilinear mapping: https://www.encyclopediaofmath.org/index.php/Bilinear_mapping

Before you start, It is better to have the background knowledge about the elliptic curve pairing, homomorphic encryption, basic matrix operations, Bilinear mapping, zero knowledge proof.

if you have already familiar with the knowledge mentioned above, believe me, it is easy for you to understand the zk-snark:)

2. What is zk-snark Roughly speaking, zk-snark is one of Verifiable Computation protocol. It enables the verifier to prove that he/she knows the value and the polynomial without leaking any information about the value or the polynomial. This is of critical importance of privacy protection of the blockchain systems. One of the example is described as the follows:

• A customer purchases the item from the retailer.
• He/she pays the retailer through blockchain.
• To make his payment valid, he should proof that 1. he has enough balance to finish this payment. 2. he has paid the retailer enough money.
• However, none of the customer or the retail can leak any information about the price of this product, or how does this transaction be calculated.

Additionally, we would like to have the following features:

• This proof to be succinct to be easy to send to the network.
• It is easy for the verifier to verify.
• It should be non-interactive, which means that there should be no interaction between the prover and the verifier.

So, the zk-snark has the following features 7

• Succinct: The sizes of the messages are tiny in comparison to the length of the actual computation.

• Non-interactive: There is no or only little interaction. For zk-snark, there is usually a setup phase and after that a single message from the prover to the verifier. Furthermore, SNARKs often have the so-called “public verifier” property meaning that anyone can verify without interacting anew, which is important for blockchains.

• ARguments: The verifier is only protected against computationally limited provers. Provers with enough computational power can create proofs/arguments about wrong statements (Note that with enough computational power, any public-key encryption can be broken). This is also called “computational soundness”, as opposed to “perfect soundness”.

• of Knowledge: It is not possible for the prover to construct a proof/argument without knowing a certain so-called witness (for example the address she wants to spend from, the preimage of a hash function or the path to a certain Merkle-tree node).

3. How to build a zk-snark system

To explain the zk-snark as clear as I could, I will discuss it in two parts, for the first part, I will explain how to construct a QAP from the given polynomial. For the second part, I will explain how to use the arguments from QAP to construct the zk-snark.

3.1 Constructing the QAP

Before we touch any cryptographic stuff, I believe I should explain how to convert the polynomial to a QAP(t Quadratic Arithmetic Programs). I borrow the example in [2] to show how to do that.

Let’s say we have a polynomial $a^3+a+5=b$, and we want to show the verifier that we know there is a point (3,35) that satisfies this polynomial. What we do here is :

• 1. Algebraic Circuit
• 1. R1CS
• 1. QAP
• 1. Linear PCPs
• 1. Linear Interactive proofs
• 1. zk-Snark

So, firstly, we covert this polynomial into a Circuit.

<div align=center>

</div> let’s define the variables as follows:

• ‘one’: The dummy value, it used to multiplied by the constant value.
• ‘x’: The input value.
• ‘out’: final output.
• ‘sym_1’: intermediate value.
• ‘smy_2’: intermediate value.
• ‘y’: intermediate value.

Let’s define g_l as the value enter the gate from left hand side, g_r as the value enter the gate from right hand side, and c as the output from the given gate. So for passing the first gate, the g_l, g_r and c are:

1. Introduction

For most cases, we can use the test environment that already exits. But for some test cases that need the special test environment, we have to create it by ourselves. This artical mainly focuses on how to create the job in community CI system.

We will go through the Openstack-infra/project-config the Zuul and the devstack-gate to see how these project works in CI system.

2. Openstack Infra/Project-config

When we need to add a new test job to the community CI system, we need to modify this Projects. Now, lets go throught these names and configure files.

The CI system works like this, when we create/update a patch to the gerrit, gerrit will pushes out a notification to the event stream. This event stream has a number of subscribers, and one of them is called Zuul. Zuul is designed to manage the graphs of interdependent branch merge proposals in the upstream system. It will monitors in-progress jobs for a set of related patches. More than that, Zuul is responsible for constructing the pipelines of jobs that would be executed on various events. There are plenty of pipelines(gate,check,release-post …..) and you can find pipelines here. Zuul will read the pipeline configuration here and run the jobs in each pipeline.

##1.Pipeline

Let’s take a look at one of the important pipe the gate for exmaple.

  - name: gate
description: Changes that have been approved by core developers are enqueued in order in this pipeline, and if they pass tests in Jenkins, will be merged.
success-message: Build succeeded (gate pipeline).
failure-message: Build failed (gate pipeline).  For information on how to proceed, see http://docs.openstack.org/infra/manual/developers.html#automated-testing
manager: DependentPipelineManager
source: gerrit
precedence: high
require:
	 open: True
  current-patchset: True
  approval:
    - verified: [1, 2]
      username: jenkins
    - workflow: 1
trigger:
  gerrit:
    - event: comment-added
      approval:
        - workflow: 1
    - event: comment-added
      approval:
        - verified: 1
      username: jenkins
start:
  gerrit:
    verified: 0
success:
  gerrit:
    verified: 2
    submit: true
failure:
  gerrit:
    verified: -2
window-floor: 20
window-increase-factor: 2

From the section above, we can clearly see that this pipeline(name:gate) is triggered by the event of comment-added and sometime, we use comment: (?i)^(Patch Set [0-9]+:)?( [\w\\+-]*)*(\n\n)?\s*(recheck|reverify) to trigger the pipeline with special comments. Once the appropriate pipeline is matched, Zuul executes that particular pipeline for the project that had a patch proposed.

##2. jenkins’ jobs

Now, we need to add jobs into the pipelines. Each job should belong to a special projects, so the logic is Openstack projects has some pipelines and each pipeline contains some jobs.

Here I paste part of the neutron configuration in layout.yaml. If you need to add a new test job for neutron, just add the name of the test under the special pipleline under which you want it to run. Please notice the template here, it helps people to put the common jobs together thus you do not need to write the same jobs for different Openstack projects.

  - name: openstack/neutron
template:
  - name: merge-check
  - name: python-jobs
  - name: python34-jobs
  - name: python35-jobs
  - name: openstack-server-publish-jobs
  - name: openstack-server-release-jobs
  - name: periodic-liberty
  - name: periodic-mitaka
  - name: periodic-newton
  - name: periodic-jobs-with-oslo-master
  - name: periodic-jobs-with-neutron-lib-master
  - name: check-requirements
  - name: integrated-gate
  - name: translation-jobs
  - name: translation-jobs-mitaka
  - name: translation-jobs-newton
  - name: experimental-tripleo-jobs
  - name: release-notes-jobs
check:
  - neutron-coverage-ubuntu-xenial
  - gate-neutron-dsvm-api-ubuntu-trusty
  - gate-neutron-dsvm-functional-ubuntu-trusty
  - gate-neutron-dsvm-fullstack-ubuntu-trusty
  - gate-rally-dsvm-neutron-neutron
  - gate-tempest-dsvm-neutron-dvr-ubuntu-trusty
  - gate-tempest-dsvm-neutron-dvr-ubuntu-xenial
  - gate-tempest-dsvm-neutron-identity-v3-only-full-ubuntu-xenial-nv
  - gate-tempest-dsvm-neutron-linuxbridge-ubuntu-trusty
  - gate-tempest-dsvm-neutron-linuxbridge-ubuntu-xenial
  - gate-neutron-lbaasv2-dsvm-minimal
  - gate-grenade-dsvm-neutron-multinode
  - gate-grenade-dsvm-neutron-dvr-multinode
  - gate-tempest-dsvm-neutron-multinode-full-ubuntu-trusty
  - gate-tempest-dsvm-neutron-dvr-multinode-full-ubuntu-trusty
  - gate-tempest-dsvm-neutron-multinode-full-ubuntu-xenial
  - gate-tempest-dsvm-neutron-dvr-multinode-full-ubuntu-xenial
  - gate-tempest-dsvm-ironic-ipa-wholedisk-agent_ssh-tinyipa-nv
gate:
  - neutron-coverage-ubuntu-xenial
  - gate-neutron-dsvm-api-ubuntu-trusty
  - gate-tempest-dsvm-neutron-dvr-ubuntu-trusty
  - gate-tempest-dsvm-neutron-dvr-ubuntu-xenial
  - gate-tempest-dsvm-neutron-linuxbridge-ubuntu-trusty
  - gate-tempest-dsvm-neutron-linuxbridge-ubuntu-xenial
  - gate-grenade-dsvm-neutron-multinode
  - gate-grenade-dsvm-neutron-dvr-multinode
post:
  - neutron-coverage-ubuntu-trusty
  - neutron-coverage-ubuntu-xenial
experimental:
  - gate-neutron-dsvm-functional-py34-ubuntu-trusty
  - gate-neutron-dsvm-functional-ubuntu-xenial
  - gate-neutron-dsvm-functional-py35-ubuntu-xenial
  - gate-neutron-dsvm-fullstack-ubuntu-xenial
  - gate-tempest-dsvm-neutron-scenario
  - gate-tempest-dsvm-neutron-scenario-linuxbridge
  - gate-grenade-dsvm-neutron-forward
  - gate-neutron-vpnaas-dsvm-functional
  - gate-neutron-vpnaas-dsvm-functional-sswan
  - gate-tempest-dsvm-neutron-ipv6only
  - gate-tempest-dsvm-neutron-serviceipv6
  - gate-tempest-dsvm-neutron-ovs-native
  - gate-tempest-dsvm-neutron-dvr-ovs-native
  - gate-neutron-dsvm-api-ubuntu-xenial
  - gate-neutron-dsvm-api-pecan-ubuntu-trusty
  - gate-neutron-dsvm-api-pecan-ubuntu-xenial
  - gate-tempest-dsvm-neutron-pecan
  - gate-tempest-dsvm-neutron-src-neutron-lib
  - gate-grenade-dsvm-neutron-linuxbridge-multinode-nv
  - gate-tempest-dsvm-neutron-pg-full-ubuntu-trusty
  - gate-tempest-dsvm-neutron-pg-full-ubuntu-xenial

##3. Jenkins Job Builder As more and more jobs added to the jenkins, it would be virtually impossible to manage the configuration of so many jobs using human-based processes. To solve this dilemma, the Jenkins Job Builder (JJB) python tool was created. JJB consumes YAML files that describe both individual Jenkins jobs as well as templates for parameterized Jenkins jobs, and writes the config.xml files for all Jenkins jobs that are produced from those templates. Important: Note that Zuul does not construct Jenkins jobs. JJB does that. Zuul simply configures which Jenkins jobs should run for a project and a pipeline.

There is a master projects.yaml file in the same directory that lists the “top-level” definitions of jobs for all projects, and it is in this file that many of the variables that are used in job template instantiation are defined (including the {name} variable, which corresponds to the name of the project.

When JJB build the jobs, it reads the projects.yaml. let’s skip the first jobs like python-jobs or coverage-jobs. If we take a look at the job like grenade-dsvm-neutron-multinode we can see that this job request the node configuration of ubuntu-trusty-2-node from node pool. It is quite simple to understand the configurations here.

 - project:
    name: neutron
    tarball-site: tarballs.openstack.org
    doc-publisher-site: docs.openstack.org

jobs:
  - coverage-jobs
  - python-jobs
  - cross-python-jobs
  - 'gate-{name}-python35{suffix}':
      suffix: ''
  - python-liberty-bitrot-jobs
  - python-mitaka-bitrot-jobs
  - python-newton-bitrot-jobs
  - openstack-publish-jobs
  - openstack-releasenotes-jobs
  - openstack-server-release-jobs
  - translation-jobs
  - translation-jobs-mitaka
  - translation-jobs-newton
  - gate-rally-dsvm-neutron-{name}
  - '{pipeline}-grenade-dsvm-neutron-multinode{job-suffix}':
      pipeline: gate
      node: ubuntu-trusty-2-node
      job-suffix: ''
      branch-override: default
  - '{pipeline}-grenade-dsvm-neutron-dvr-multinode{job-suffix}':
      pipeline: gate
      node: ubuntu-trusty-2-node
      job-suffix: ''
      branch-override: default
      
      **********skip************

Now, we take the python-jobs as an example to show how the jobs are grouped together. It is obvious that this job contains 6 different jobs, as these jobs are general jobs for all the projects so they are grouped together. The {name} prefix will be replace by the project name that starts this job.

-job-group:
name: python-jobs
node:
  - ubuntu-trusty
  - ubuntu-xenial
jobs:
  - 'gate-{name}-pep8-{node}'
  - 'gate-{name}-python27-{node}'
  - 'gate-{name}-python34'
  - 'gate-{name}-docs-{node}'
  - 'gate-{name}-requirements'
  - '{name}-branch-tarball'
  # pylint isn't standard
  # pypy isn't standard
  # gate-{name}-tox-{envlist} also isn't standard, but is reserved for
  # projects that want to run specific jobs via tox

Let’s take a look at gate-{name}-pep8-{node}

The most import section is builders, it instructs how the JJB runs the tests.

- job-template:
name: 'gate-{name}-pep8-{node}'

builders:
  - print-template-name:
      template-name: "{template-name}"
  - zuul-git-prep-upper-constraints
  - install-distro-packages
  - revoke-sudo
  - pep8:
      env: pep8

publishers:
  - test-results
  - console-log

node: '{node}'

Let’s read the print-template-name, it is in macros.yaml. It is quite simple, it just print the name of the template, the varialbe {template-name} is passed by the maping “template-name: “{template-name}””

- builder:
name: print-template-name
builders:
  - shell: 'echo JJB template: {template-name}'

##3. Devtack Gate The real world is not always so simple. We often want to run the test environment in a real Openstack Environment. This work is done by devstack-gate.

To show how it works, I pasted the paragrah from devstack-gate document here.

When a proposed change is approved by the core reviewers, Jenkins triggers the devstack gate test itself. This job runs on one of the previously configured nodes and invokes the devstack-vm-gate-wrap.sh script which checks out code from all of the involved repositories, and merges the proposed change. That script then calls devstack-vm-gate.sh which installs a devstack configuration file, and invokes devstack. Once devstack is finished, it runs exercise.sh and Tempest, which perform integration testing. After everything is done, devstack-gate copies and formats all of the logs for archival. A jenkins jobs then copies these logs to the log archive.

There are two importnat concepts.

• Nodepool— Provides virtual machine instances to Jenkins masters for running complex, isolation-sensitive Jenkins jobs. We just need to pick up the suitable node we need to run the tests from the nodepool. The configration of different node can be found here. The node will be configured to be ready to run the suitalbe tests. It is controleed by the scripts like prepare_node_devstack.sh(it will call prepare_node.sh firstly.).

• Devstack-Gate— Scripts that create an OpenStack environment with Devstack, run tests against that environment, and archive logs and results

The devstack-gate project is here, you can run it locally if you have a openstack environment. When we have got the suitalbe node ready, we need to set up the devstack by running devstack-vm-gate-wrap.sh. Let’s take a look at devstack-gate.yaml from project-config. At the end of this file, it runs the scripts safe-devstack-vm-gate-wrap.sh

- job-template:
name: '{pipeline}-grenade-dsvm-neutron-dvr-multinode{job-suffix}'
node: '{node}'

wrappers:
  - build-timeout:
      timeout: 125
  - timestamps

builders:
  - link-logs
  - net-info
  - devstack-checkout
  - shell: |
      #!/bin/bash -xe
      export PYTHONUNBUFFERED=true
      export DEVSTACK_GATE_NEUTRON=1
      export DEVSTACK_GATE_CONFIGDRIVE=0
      export DEVSTACK_GATE_GRENADE=pullup
      # Test DVR upgrade on multinode
      export PROJECTS="openstack-dev/grenade $PROJECTS"
      export DEVSTACK_GATE_NEUTRON_DVR=1
      export BRANCH_OVERRIDE={branch-override}
      if [ "$BRANCH_OVERRIDE" != "default" ] ; then
          export OVERRIDE_ZUUL_BRANCH=$BRANCH_OVERRIDE
      fi
      export DEVSTACK_GATE_TOPOLOGY="multinode"

      cp devstack-gate/devstack-vm-gate-wrap.sh ./safe-devstack-vm-gate-wrap.sh
      ./safe-devstack-vm-gate-wrap.sh

    publishers:
   		   	- devstack-logs
   	   		- console-log

##4. destack-vm-gate.sh

The devstack-vm-gate will configure the node and finally run the devstack project.

1. OVERLAYFS

OVERLAY file system is really a awesome technnology to log to organise different files based on different layers. With the idea of OVERLAY, users can create/update the files on the uppest layer while the lower layers can only be read! Live disk and Openwrt system usually build their filesystem on OVERLAYFS, thus store the uses’ modification in upper layout and the READ-ONLY disk data is mounted as the lower layer, in this way, system can easily revert users’ modification.

Docker also employs OVERLAYFS to implement its’ filesystem in docker container. Docker LAYOUTFS

1. LAYOUTFS Test

1.2. TEST with the system folders

In tmp, we create lower upper workdir and overlay. we create a file called 123.txt in folder lower.

cd /tmp
mkdir lower upper workdir overlay
sudo mount -t overlay -o \
lowerdir=/tmp/lower,\
upperdir=/tmp/upper,\
workdir=/tmp/workdir \
none /tmp/overlay

with ls /tmp/overlay, we can see that 123.txt is in overlay folder.

1. touch 234.txt in /tmp/overlay, this file is created in folder upper.

2. rm /tmp/overlay/123.txt, 123.txt still in lower, but it create a file like:

   c——— 1 ubuntu ubuntu 0, 0 Jun 6 21:45 123.txt

1.2. TEST with the filesystem

mkdir lower upper overlay
# Lets create a fake block device to hold our "lower" filesystem
dd if=/dev/zero of=lower-fs.img bs=4096 count=10240
dd if=/dev/zero of=upper-fs.img bs=4096 count=10240

# Give this block device an ext4 filesystem.
mkfs -t ext4 lower-fs.img
mkfs -t ext4 upper-fs.img

# Mount the filesystem we just created and give it a file
sudo mount lower-fs.img /tmp/lower
sudo chown $USER:$USER /tmp/lower
echo "hello world" >> /tmp/lower/lower-file.txt

# Remount the lower filesystem as read only just for giggles
sudo mount -o remount,ro lower-fs.img /tmp/lower

# Mount the upper filesystem
sudo mount upper-fs.img /tmp/upper
sudo chown $USER:$USER /tmp/upper

# Create the workdir in the upper filesystem and the 
# directory in the upper filesystem that will act as the upper
# directory (they both have to be in the same filesystem)
mkdir /tmp/upper/upper
mkdir /tmp/upper/workdir

# Create our overlayfs mount
sudo mount -t overlay -o \
lowerdir=/tmp/lower,\
upperdir=/tmp/upper/upper,\
workdir=/tmp/upper/workdir \
none /tmp/overlay

Quite like the first test, when I create a new file called 234, it has the following file structure.

.
|-- lost+found [error opening dir]
|-- upper
|   `-- 324
`-- workdir
	`-- work [error opening dir]

1.3. NESTING support in OVERLAYFS

The nesting overlayFS can be mounted as following:

sudo mount -t overlay -o \
lowerdir=/tmp/lower:/tmp/lowest,\
upperdir=/tmp/upper,\
workdir=/tmp/workdir \
none /tmp/overlay