Groups > linux.kernel > #1702740 > unrolled thread

[RFC 00/16] NOVA: a new file system for persistent memory

Started by	Steven Swanson <swanson@eng.ucsd.edu>
First post	2017-08-03 09:50 +0200
Last post	2017-08-06 05:30 +0200
Articles	8 — 4 participants

Back to article view | Back to linux.kernel

  [RFC 00/16] NOVA: a new file system for persistent memory Steven Swanson <swanson@eng.ucsd.edu> - 2017-08-03 09:50 +0200
    [RFC 16/16] NOVA: Build infrastructure Steven Swanson <swanson@eng.ucsd.edu> - 2017-08-03 10:00 +0200
    [RFC 14/16] NOVA: Read-only pmem devices Steven Swanson <swanson@eng.ucsd.edu> - 2017-08-03 10:00 +0200
    [RFC 03/16] NOVA: PMEM allocation system Steven Swanson <swanson@eng.ucsd.edu> - 2017-08-03 10:00 +0200
    [RFC 06/16] NOVA: Lite-weight journaling for complex ops Steven Swanson <swanson@eng.ucsd.edu> - 2017-08-03 10:00 +0200
    Re: [RFC 01/16] NOVA: Documentation Randy Dunlap <rdunlap@infradead.org> - 2017-08-04 00:40 +0200
    Re: [RFC 01/16] NOVA: Documentation Bart Van Assche <Bart.VanAssche@wdc.com> - 2017-08-04 17:20 +0200
      Re: [RFC 01/16] NOVA: Documentation Steven Swanson <steven.swanson@gmail.com> - 2017-08-06 05:30 +0200

#1702740 — [RFC 00/16] NOVA: a new file system for persistent memory

From	Steven Swanson <swanson@eng.ucsd.edu>
Date	2017-08-03 09:50 +0200
Subject	[RFC 00/16] NOVA: a new file system for persistent memory
Message-ID	<uaj3k-5gj-7@gated-at.bofh.it>

This is an RFC patch series that impements NOVA (NOn-Volatile memory
Accelerated file system), a new file system built for PMEM.

NOVA's goal is to provide a high-performance, full-featured, production-ready
file system tailored for byte-addressable non-volatile memories (e.g., NVDIMMs
and Intel's soon-to-be-released 3DXpoint DIMMs).  It combines design elements
from many other file systems to provide a combination of high-performance,
strong consistency guarantees, and comprehensive data protection.  NOVA supports
DAX-style mmap, and making DAX perform well is a first-order priority in NOVA's
design.

NOVA was developed at the Non-Volatile Systems Laboratory in the Computer
Science and Engineering Department at the University of California, San Diego.
Its primary authors are Andiry Xu <jix024@eng.ucsd.edu>, Lu Zhang
<luzh@eng.ucsd.edu>, and Steven Swanson <swanson@eng.ucsd.edu>.

NOVA is stable enough to run complex applications, but there is substantial
work left to do.  This RFC is intended to gather feedback to guide its
development toward eventual inclusion upstream.

The patches are relative Linux 4.12.

Overview
========

NOVA is primarily a log-structured file system, but rather than maintain a
single global log for the entire file system, it maintains separate logs for
each file (inode).  NOVA breaks the logs into 4KB pages, they need not be
contiguous in memory.  The logs only contain metadata.

File data pages reside outside the log, and log entries for write operations
point to data pages they modify.  File modification uses copy-on-write (COW) to
provide atomic file updates.

For file operations that involve multiple inodes, NOVA use small, fixed-sized
redo logs to atomically append log entries to the logs of the inodes involved.

This structure keeps logs small and makes garbage collection very fast.  It also
enables enormous parallelism during recovery from an unclean unmount, since
threads can scan logs in parallel.

NOVA replicates and checksums all metadata structures and protects file data
with RAID-4-style parity.  It supports checkpoints to facilitate backups.

Documentation/filesystems/NOVA.txt contains some lower-level implementation and
usage information.  A more thorough discussion of NOVA's goals and design is
avaialable in two papers:

NOVA: A Log-structured File system for Hybrid Volatile/Non-volatile Main Memories
http://cseweb.ucsd.edu/~swanson/papers/FAST2016NOVA.pdf
Jian Xu and Steven Swanson
Published in FAST 2016

Hardening the NOVA File System
http://cseweb.ucsd.edu/~swanson/papers/TechReport2017HardenedNOVA.pdf UCSD-CSE
Techreport CS2017-1018
Jian Xu, Lu Zhang, Amirsaman Memaripour, Akshatha
Gangadharaiah, Amit Borase, Tamires Brito Da Silva, Andy Rudoff, Steven
Swanson

-steve


---

Steven Swanson (16):
      NOVA: Documentation
      NOVA: Superblock and fs layout
      NOVA: PMEM allocation system
      NOVA: Inode operations and structures
      NOVA: Log data structures and operations
      NOVA: Lite-weight journaling for complex ops
      NOVA: File and directory operations
      NOVA: Garbage collection
      NOVA: DAX code
      NOVA: File data protection
      NOVA: Snapshot support
      NOVA: Recovery code
      NOVA: Sysfs and ioctl
      NOVA: Read-only pmem devices
      NOVA: Performance measurement
      NOVA: Build infrastructure


 Documentation/filesystems/00-INDEX |    2 
 Documentation/filesystems/nova.txt |  771 +++++++++++++++++
 MAINTAINERS                        |    8 
 README.md                          |  173 ++++
 arch/x86/include/asm/io.h          |    1 
 arch/x86/mm/fault.c                |   11 
 arch/x86/mm/ioremap.c              |   25 -
 drivers/nvdimm/pmem.c              |   14 
 fs/Kconfig                         |    2 
 fs/Makefile                        |    1 
 fs/nova/Kconfig                    |   15 
 fs/nova/Makefile                   |    9 
 fs/nova/balloc.c                   |  827 +++++++++++++++++++
 fs/nova/balloc.h                   |  118 +++
 fs/nova/bbuild.c                   | 1602 ++++++++++++++++++++++++++++++++++++
 fs/nova/checksum.c                 |  912 ++++++++++++++++++++
 fs/nova/dax.c                      | 1346 ++++++++++++++++++++++++++++++
 fs/nova/dir.c                      |  760 +++++++++++++++++
 fs/nova/file.c                     |  943 +++++++++++++++++++++
 fs/nova/gc.c                       |  739 +++++++++++++++++
 fs/nova/inode.c                    | 1467 +++++++++++++++++++++++++++++++++
 fs/nova/inode.h                    |  389 +++++++++
 fs/nova/ioctl.c                    |  185 ++++
 fs/nova/journal.c                  |  474 +++++++++++
 fs/nova/journal.h                  |   61 +
 fs/nova/log.c                      | 1411 ++++++++++++++++++++++++++++++++
 fs/nova/log.h                      |  333 +++++++
 fs/nova/mprotect.c                 |  604 ++++++++++++++
 fs/nova/mprotect.h                 |  190 ++++
 fs/nova/namei.c                    |  919 +++++++++++++++++++++
 fs/nova/nova.h                     | 1137 ++++++++++++++++++++++++++
 fs/nova/nova_def.h                 |  154 +++
 fs/nova/parity.c                   |  411 +++++++++
 fs/nova/perf.c                     |  594 +++++++++++++
 fs/nova/perf.h                     |   96 ++
 fs/nova/rebuild.c                  |  847 +++++++++++++++++++
 fs/nova/snapshot.c                 | 1407 ++++++++++++++++++++++++++++++++
 fs/nova/snapshot.h                 |   98 ++
 fs/nova/stats.c                    |  685 +++++++++++++++
 fs/nova/stats.h                    |  218 +++++
 fs/nova/super.c                    | 1222 +++++++++++++++++++++++++++
 fs/nova/super.h                    |  216 +++++
 fs/nova/symlink.c                  |  153 +++
 fs/nova/sysfs.c                    |  543 ++++++++++++
 include/linux/io.h                 |    2 
 include/linux/mm.h                 |    2 
 include/linux/mm_types.h           |    3 
 kernel/memremap.c                  |   24 +
 mm/memory.c                        |    2 
 mm/mmap.c                          |    1 
 mm/mprotect.c                      |   13 
 51 files changed, 22129 insertions(+), 11 deletions(-)
 create mode 100644 Documentation/filesystems/nova.txt
 create mode 100644 README.md
 create mode 100644 fs/nova/Kconfig
 create mode 100644 fs/nova/Makefile
 create mode 100644 fs/nova/balloc.c
 create mode 100644 fs/nova/balloc.h
 create mode 100644 fs/nova/bbuild.c
 create mode 100644 fs/nova/checksum.c
 create mode 100644 fs/nova/dax.c
 create mode 100644 fs/nova/dir.c
 create mode 100644 fs/nova/file.c
 create mode 100644 fs/nova/gc.c
 create mode 100644 fs/nova/inode.c
 create mode 100644 fs/nova/inode.h
 create mode 100644 fs/nova/ioctl.c
 create mode 100644 fs/nova/journal.c
 create mode 100644 fs/nova/journal.h
 create mode 100644 fs/nova/log.c
 create mode 100644 fs/nova/log.h
 create mode 100644 fs/nova/mprotect.c
 create mode 100644 fs/nova/mprotect.h
 create mode 100644 fs/nova/namei.c
 create mode 100644 fs/nova/nova.h
 create mode 100644 fs/nova/nova_def.h
 create mode 100644 fs/nova/parity.c
 create mode 100644 fs/nova/perf.c
 create mode 100644 fs/nova/perf.h
 create mode 100644 fs/nova/rebuild.c
 create mode 100644 fs/nova/snapshot.c
 create mode 100644 fs/nova/snapshot.h
 create mode 100644 fs/nova/stats.c
 create mode 100644 fs/nova/stats.h
 create mode 100644 fs/nova/super.c
 create mode 100644 fs/nova/super.h
 create mode 100644 fs/nova/symlink.c
 create mode 100644 fs/nova/sysfs.c

--
Signature

[toc] | [next] | [standalone]

#1702742 — [RFC 16/16] NOVA: Build infrastructure

From	Steven Swanson <swanson@eng.ucsd.edu>
Date	2017-08-03 10:00 +0200
Subject	[RFC 16/16] NOVA: Build infrastructure
Message-ID	<uajcZ-5jY-1@gated-at.bofh.it>
In reply to	#1702740

Signed-off-by: Steven Swanson <swanson@cs.ucsd.edu>
---
 fs/Kconfig       |    2 ++
 fs/Makefile      |    1 +
 fs/nova/Kconfig  |   15 +++++++++++++++
 fs/nova/Makefile |    9 +++++++++
 4 files changed, 27 insertions(+)
 create mode 100644 fs/nova/Kconfig
 create mode 100644 fs/nova/Makefile

diff --git a/fs/Kconfig b/fs/Kconfig
index b0e42b6a96b9..571714353a5f 100644
--- a/fs/Kconfig
+++ b/fs/Kconfig
@@ -58,6 +58,8 @@ config FS_DAX_PMD
 	depends on ZONE_DEVICE
 	depends on TRANSPARENT_HUGEPAGE
 
+source "fs/nova/Kconfig"
+
 endif # BLOCK
 
 # Posix ACL utility routines
diff --git a/fs/Makefile b/fs/Makefile
index 7bbaca9c67b1..53f6465e0f4c 100644
--- a/fs/Makefile
+++ b/fs/Makefile
@@ -113,6 +113,7 @@ obj-$(CONFIG_OMFS_FS)		+= omfs/
 obj-$(CONFIG_JFS_FS)		+= jfs/
 obj-$(CONFIG_XFS_FS)		+= xfs/
 obj-$(CONFIG_9P_FS)		+= 9p/
+obj-$(CONFIG_NOVA_FS)		+= nova/
 obj-$(CONFIG_AFS_FS)		+= afs/
 obj-$(CONFIG_NILFS2_FS)		+= nilfs2/
 obj-$(CONFIG_BEFS_FS)		+= befs/
diff --git a/fs/nova/Kconfig b/fs/nova/Kconfig
new file mode 100644
index 000000000000..c1c692edef92
--- /dev/null
+++ b/fs/nova/Kconfig
@@ -0,0 +1,15 @@
+config NOVA_FS
+	tristate "NOVA: log-structured file system for non-volatile memories"
+	depends on FS_DAX
+	select CRC32
+	select LIBCRC32C
+	help
+	  If your system has a block of fast (comparable in access speed to
+	  system memory) and non-volatile byte-addressable memory and you wish
+	  to mount a light-weight filesystem with strong consistency support
+	  over it, say Y here.
+
+	  To compile this as a module, choose M here: the module will be
+	  called nova.
+
+	  If unsure, say N.
diff --git a/fs/nova/Makefile b/fs/nova/Makefile
new file mode 100644
index 000000000000..c45e418652ca
--- /dev/null
+++ b/fs/nova/Makefile
@@ -0,0 +1,9 @@
+#
+# Makefile for the linux NOVA filesystem routines.
+#
+
+obj-$(CONFIG_NOVA_FS) += nova.o
+
+nova-y := balloc.o bbuild.o checksum.o dax.o dir.o file.o gc.o inode.o ioctl.o \
+	journal.o log.o mprotect.o namei.o parity.o rebuild.o snapshot.o stats.o \
+	super.o symlink.o sysfs.o perf.o

[toc] | [prev] | [next] | [standalone]

#1702744 — [RFC 14/16] NOVA: Read-only pmem devices

From	Steven Swanson <swanson@eng.ucsd.edu>
Date	2017-08-03 10:00 +0200
Subject	[RFC 14/16] NOVA: Read-only pmem devices
Message-ID	<uajcZ-5jY-9@gated-at.bofh.it>
In reply to	#1702740

Add (and implement) a module command line option to nd_pmem to support read-only pmem devices.

Signed-off-by: Steven Swanson <swanson@cs.ucsd.edu>
---
 arch/x86/include/asm/io.h |    1 +
 arch/x86/mm/ioremap.c     |   25 ++++++++++++++++++-------
 drivers/nvdimm/pmem.c     |   14 ++++++++++++--
 include/linux/io.h        |    2 ++
 kernel/memremap.c         |   24 ++++++++++++++++++++++++
 mm/memory.c               |    2 +-
 mm/mmap.c                 |    1 +
 7 files changed, 59 insertions(+), 10 deletions(-)

diff --git a/arch/x86/include/asm/io.h b/arch/x86/include/asm/io.h
index 7afb0e2f07f4..7aae48f2e4f1 100644
--- a/arch/x86/include/asm/io.h
+++ b/arch/x86/include/asm/io.h
@@ -173,6 +173,7 @@ extern void __iomem *ioremap_uc(resource_size_t offset, unsigned long size);
 #define ioremap_uc ioremap_uc
 
 extern void __iomem *ioremap_cache(resource_size_t offset, unsigned long size);
+extern void __iomem *ioremap_cache_ro(resource_size_t phys_addr, unsigned long size);
 extern void __iomem *ioremap_prot(resource_size_t offset, unsigned long size, unsigned long prot_val);
 
 /**
diff --git a/arch/x86/mm/ioremap.c b/arch/x86/mm/ioremap.c
index bbc558b88a88..bcd473801817 100644
--- a/arch/x86/mm/ioremap.c
+++ b/arch/x86/mm/ioremap.c
@@ -81,7 +81,8 @@ static int __ioremap_check_ram(unsigned long start_pfn, unsigned long nr_pages,
  * caller shouldn't need to know that small detail.
  */
 static void __iomem *__ioremap_caller(resource_size_t phys_addr,
-		unsigned long size, enum page_cache_mode pcm, void *caller)
+		unsigned long size, enum page_cache_mode pcm, void *caller,
+		int readonly)
 {
 	unsigned long offset, vaddr;
 	resource_size_t pfn, last_pfn, last_addr;
@@ -172,6 +173,9 @@ static void __iomem *__ioremap_caller(resource_size_t phys_addr,
 		break;
 	}
 
+	if (readonly)
+		prot = __pgprot((unsigned long)prot.pgprot & ~_PAGE_RW);
+
 	/*
 	 * Ok, go for it..
 	 */
@@ -239,7 +243,7 @@ void __iomem *ioremap_nocache(resource_size_t phys_addr, unsigned long size)
 	enum page_cache_mode pcm = _PAGE_CACHE_MODE_UC_MINUS;
 
 	return __ioremap_caller(phys_addr, size, pcm,
-				__builtin_return_address(0));
+				__builtin_return_address(0), 0);
 }
 EXPORT_SYMBOL(ioremap_nocache);
 
@@ -272,7 +276,7 @@ void __iomem *ioremap_uc(resource_size_t phys_addr, unsigned long size)
 	enum page_cache_mode pcm = _PAGE_CACHE_MODE_UC;
 
 	return __ioremap_caller(phys_addr, size, pcm,
-				__builtin_return_address(0));
+				__builtin_return_address(0), 0);
 }
 EXPORT_SYMBOL_GPL(ioremap_uc);
 
@@ -289,7 +293,7 @@ EXPORT_SYMBOL_GPL(ioremap_uc);
 void __iomem *ioremap_wc(resource_size_t phys_addr, unsigned long size)
 {
 	return __ioremap_caller(phys_addr, size, _PAGE_CACHE_MODE_WC,
-					__builtin_return_address(0));
+					__builtin_return_address(0), 0);
 }
 EXPORT_SYMBOL(ioremap_wc);
 
@@ -306,23 +310,30 @@ EXPORT_SYMBOL(ioremap_wc);
 void __iomem *ioremap_wt(resource_size_t phys_addr, unsigned long size)
 {
 	return __ioremap_caller(phys_addr, size, _PAGE_CACHE_MODE_WT,
-					__builtin_return_address(0));
+					__builtin_return_address(0), 0);
 }
 EXPORT_SYMBOL(ioremap_wt);
 
 void __iomem *ioremap_cache(resource_size_t phys_addr, unsigned long size)
 {
 	return __ioremap_caller(phys_addr, size, _PAGE_CACHE_MODE_WB,
-				__builtin_return_address(0));
+				__builtin_return_address(0), 0);
 }
 EXPORT_SYMBOL(ioremap_cache);
 
+void __iomem *ioremap_cache_ro(resource_size_t phys_addr, unsigned long size)
+{
+	return __ioremap_caller(phys_addr, size, _PAGE_CACHE_MODE_WB,
+				__builtin_return_address(0), 1);
+}
+EXPORT_SYMBOL(ioremap_cache_ro);
+
 void __iomem *ioremap_prot(resource_size_t phys_addr, unsigned long size,
 				unsigned long prot_val)
 {
 	return __ioremap_caller(phys_addr, size,
 				pgprot2cachemode(__pgprot(prot_val)),
-				__builtin_return_address(0));
+				__builtin_return_address(0), 0);
 }
 EXPORT_SYMBOL(ioremap_prot);
 
diff --git a/drivers/nvdimm/pmem.c b/drivers/nvdimm/pmem.c
index c544d466ea51..a6b29c731c53 100644
--- a/drivers/nvdimm/pmem.c
+++ b/drivers/nvdimm/pmem.c
@@ -35,6 +35,11 @@
 #include "pfn.h"
 #include "nd.h"
 
+int readonly;
+
+module_param(readonly, int, S_IRUGO);
+MODULE_PARM_DESC(readonly, "Mount readonly");
+
 static struct device *to_dev(struct pmem_device *pmem)
 {
 	/*
@@ -324,9 +329,14 @@ static int pmem_attach_disk(struct device *dev,
 		addr = devm_memremap_pages(dev, &nsio->res,
 				&q->q_usage_counter, NULL);
 		pmem->pfn_flags |= PFN_MAP;
-	} else
-		addr = devm_memremap(dev, pmem->phys_addr,
+	} else {
+		if (readonly == 0)
+			addr = devm_memremap(dev, pmem->phys_addr,
 				pmem->size, ARCH_MEMREMAP_PMEM);
+		else
+			addr = devm_memremap_ro(dev, pmem->phys_addr,
+				pmem->size, ARCH_MEMREMAP_PMEM);
+	}
 
 	/*
 	 * At release time the queue must be frozen before
diff --git a/include/linux/io.h b/include/linux/io.h
index 2195d9ea4aaa..00641aef9ab3 100644
--- a/include/linux/io.h
+++ b/include/linux/io.h
@@ -86,6 +86,8 @@ void devm_ioremap_release(struct device *dev, void *res);
 
 void *devm_memremap(struct device *dev, resource_size_t offset,
 		size_t size, unsigned long flags);
+void *devm_memremap_ro(struct device *dev, resource_size_t offset,
+		size_t size, unsigned long flags);
 void devm_memunmap(struct device *dev, void *addr);
 
 void *__devm_memremap_pages(struct device *dev, struct resource *res);
diff --git a/kernel/memremap.c b/kernel/memremap.c
index 23a6483c3666..68371a9a40e5 100644
--- a/kernel/memremap.c
+++ b/kernel/memremap.c
@@ -162,6 +162,30 @@ void *devm_memremap(struct device *dev, resource_size_t offset,
 }
 EXPORT_SYMBOL(devm_memremap);
 
+void *devm_memremap_ro(struct device *dev, resource_size_t offset,
+		size_t size, unsigned long flags)
+{
+	void **ptr, *addr;
+
+	printk("%s\n", __func__);
+	ptr = devres_alloc_node(devm_memremap_release, sizeof(*ptr), GFP_KERNEL,
+			dev_to_node(dev));
+	if (!ptr)
+		return ERR_PTR(-ENOMEM);
+
+	addr = ioremap_cache_ro(offset, size);
+	if (addr) {
+		*ptr = addr;
+		devres_add(dev, ptr);
+	} else {
+		devres_free(ptr);
+		return ERR_PTR(-ENXIO);
+	}
+
+	return addr;
+}
+EXPORT_SYMBOL(devm_memremap_ro);
+
 void devm_memunmap(struct device *dev, void *addr)
 {
 	WARN_ON(devres_release(dev, devm_memremap_release,
diff --git a/mm/memory.c b/mm/memory.c
index bb11c474857e..625623a90f08 100644
--- a/mm/memory.c
+++ b/mm/memory.c
@@ -1793,7 +1793,7 @@ static int remap_pte_range(struct mm_struct *mm, pmd_t *pmd,
 		return -ENOMEM;
 	arch_enter_lazy_mmu_mode();
 	do {
-		BUG_ON(!pte_none(*pte));
+//		BUG_ON(!pte_none(*pte));
 		set_pte_at(mm, addr, pte, pte_mkspecial(pfn_pte(pfn, prot)));
 		pfn++;
 	} while (pte++, addr += PAGE_SIZE, addr != end);
diff --git a/mm/mmap.c b/mm/mmap.c
index a5e3dcd75e79..5423e3340e59 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -126,6 +126,7 @@ void vma_set_page_prot(struct vm_area_struct *vma)
 	/* remove_protection_ptes reads vma->vm_page_prot without mmap_sem */
 	WRITE_ONCE(vma->vm_page_prot, vm_page_prot);
 }
+EXPORT_SYMBOL(vma_set_page_prot);
 
 /*
  * Requires inode->i_mapping->i_mmap_rwsem

[toc] | [prev] | [next] | [standalone]

#1702745 — [RFC 03/16] NOVA: PMEM allocation system

From	Steven Swanson <swanson@eng.ucsd.edu>
Date	2017-08-03 10:00 +0200
Subject	[RFC 03/16] NOVA: PMEM allocation system
Message-ID	<uajcZ-5jY-3@gated-at.bofh.it>
In reply to	#1702740

Nova uses per-CPU allocators to manage free PMEM blocks.  On initialization,
NOVA divides the range of blocks in the PMEM device among the CPUs, and those
blocks are managed solely by that CPU.  We call these ranges of allocation regions.

Some of the blocks in an allocation region have fixed roles.  Here's the
layout:

+-------------------------------+
| data checksum blocks          |
+-------------------------------+
| data parity blocks            |
+-------------------------------+
|                               |
| Allocatable blocks            |
|                               |
+-------------------------------+
| replica data parity blocks    |
+-------------------------------+
| replica data checksum blocks  |
+-------------------------------+

The first and last allocation regions, also contain the super block, inode
tables, etc. and their replicas, respectively.

Each allocator maintains a red-black tree of unallocated ranges (struct
nova_range_node).

Allocation Functions
--------------------

Nova allocate PMEM blocks using two mechanisms:

1.  Static allocation as defined in super.h

2.  Allocation for log and data pages via nova_new_log_blocks() and
nova_new_data_blocks().

Both of these functions allow the caller to control whether the allocator
preferes higher addresses for allocation or lower addresses.  We use this to
encourage meta data structures and their replicas to be far from one another.

PMEM Address Translation
------------------------

In Nova's persistent data structures, memory locations are given as offsets
from the beginning of the PMEM region.  nova_get_block() translates offsets to
PMEM addresses.  nova_get_addr_off() performs the reverse translation.

Cautious allocation
-------------------

The allocator allows the caller to provide some control over where the blocks
come from.  Nova uses this to allocate replicas of metadata far from one
another.

Signed-off-by: Steven Swanson <swanson@cs.ucsd.edu>
---
 fs/nova/balloc.c |  827 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/nova/balloc.h |  118 ++++++++
 2 files changed, 945 insertions(+)
 create mode 100644 fs/nova/balloc.c
 create mode 100644 fs/nova/balloc.h

diff --git a/fs/nova/balloc.c b/fs/nova/balloc.c
new file mode 100644
index 000000000000..434507b017bd
--- /dev/null
+++ b/fs/nova/balloc.c
@@ -0,0 +1,827 @@
+/*
+ * NOVA persistent memory management
+ *
+ * Copyright 2015-2016 Regents of the University of California,
+ * UCSD Non-Volatile Systems Lab, Andiry Xu <jix024@cs.ucsd.edu>
+ * Copyright 2012-2013 Intel Corporation
+ * Copyright 2009-2011 Marco Stornelli <marco.stornelli@gmail.com>
+ * Copyright 2003 Sony Corporation
+ * Copyright 2003 Matsushita Electric Industrial Co., Ltd.
+ * 2003-2004 (c) MontaVista Software, Inc. , Steve Longerbeam
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include <linux/fs.h>
+#include <linux/bitops.h>
+#include "nova.h"
+#include "inode.h"
+
+int nova_alloc_block_free_lists(struct super_block *sb)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+	struct free_list *free_list;
+	int i;
+
+	sbi->free_lists = kcalloc(sbi->cpus, sizeof(struct free_list),
+				  GFP_KERNEL);
+
+	if (!sbi->free_lists)
+		return -ENOMEM;
+
+	for (i = 0; i < sbi->cpus; i++) {
+		free_list = nova_get_free_list(sb, i);
+		free_list->block_free_tree = RB_ROOT;
+		spin_lock_init(&free_list->s_lock);
+		free_list->index = i;
+	}
+
+	return 0;
+}
+
+void nova_delete_free_lists(struct super_block *sb)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+
+	/* Each tree is freed in save_blocknode_mappings */
+	kfree(sbi->free_lists);
+	sbi->free_lists = NULL;
+}
+
+static int nova_data_csum_init_free_list(struct super_block *sb,
+	struct free_list *free_list)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+	unsigned long data_csum_blocks;
+
+	/* Allocate pages to hold data checksums.  We store one checksum for
+	 * each stripe for each page.  We replicate the checksums at the
+	 * beginning and end of per-cpu region that holds the data they cover.
+	 */
+	data_csum_blocks = ((sbi->initsize >> NOVA_STRIPE_SHIFT)
+				* NOVA_DATA_CSUM_LEN) >> PAGE_SHIFT;
+	free_list->csum_start = free_list->block_start;
+	free_list->block_start += data_csum_blocks / sbi->cpus;
+	if (data_csum_blocks % sbi->cpus)
+		free_list->block_start++;
+
+	free_list->num_csum_blocks =
+		free_list->block_start - free_list->csum_start;
+
+	free_list->replica_csum_start = free_list->block_end + 1 -
+						free_list->num_csum_blocks;
+	free_list->block_end -= free_list->num_csum_blocks;
+
+	return 0;
+}
+
+
+static int nova_data_parity_init_free_list(struct super_block *sb,
+	struct free_list *free_list)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+	unsigned long blocksize, total_blocks, parity_blocks;
+
+	/* Allocate blocks to store data block parity stripes.
+	 * Always reserve in case user turns it off at init mount but later
+	 * turns it on.
+	 */
+	blocksize = sb->s_blocksize;
+	total_blocks = sbi->initsize / blocksize;
+	parity_blocks = total_blocks / (blocksize / NOVA_STRIPE_SIZE + 1);
+	if (total_blocks % (blocksize / NOVA_STRIPE_SIZE + 1))
+		parity_blocks++;
+
+	free_list->parity_start = free_list->block_start;
+	free_list->block_start += parity_blocks / sbi->cpus;
+	if (parity_blocks % sbi->cpus)
+		free_list->block_start++;
+
+	free_list->num_parity_blocks =
+		free_list->block_start - free_list->parity_start;
+
+	free_list->replica_parity_start = free_list->block_end + 1 -
+		free_list->num_parity_blocks;
+
+	return 0;
+}
+
+
+// Initialize a free list.  Each CPU gets an equal share of the block space to
+// manage.
+static void nova_init_free_list(struct super_block *sb,
+	struct free_list *free_list, int index)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+	unsigned long per_list_blocks;
+
+	per_list_blocks = sbi->num_blocks / sbi->cpus;
+
+	free_list->block_start = per_list_blocks * index;
+	free_list->block_end = free_list->block_start +
+					per_list_blocks - 1;
+	if (index == 0)
+		free_list->block_start += sbi->head_reserved_blocks;
+	if (index == sbi->cpus - 1)
+		free_list->block_end -= sbi->tail_reserved_blocks;
+
+	nova_data_csum_init_free_list(sb, free_list);
+	nova_data_parity_init_free_list(sb, free_list);
+}
+
+inline struct nova_range_node *nova_alloc_blocknode(struct super_block *sb)
+{
+	return nova_alloc_range_node(sb);
+}
+
+inline void nova_free_blocknode(struct super_block *sb,
+	struct nova_range_node *node)
+{
+	nova_free_range_node(node);
+}
+
+
+void nova_init_blockmap(struct super_block *sb, int recovery)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+	struct rb_root *tree;
+	struct nova_range_node *blknode;
+	struct free_list *free_list;
+	int i;
+	int ret;
+
+	/* Divide the block range among per-CPU free lists */
+	sbi->per_list_blocks = sbi->num_blocks / sbi->cpus;
+	for (i = 0; i < sbi->cpus; i++) {
+		free_list = nova_get_free_list(sb, i);
+		tree = &(free_list->block_free_tree);
+		nova_init_free_list(sb, free_list, i);
+
+		/* For recovery, update these fields later */
+		if (recovery == 0) {
+			free_list->num_free_blocks = free_list->block_end -
+						free_list->block_start + 1;
+
+			blknode = nova_alloc_blocknode(sb);
+			if (blknode == NULL)
+				BUG();
+			blknode->range_low = free_list->block_start;
+			blknode->range_high = free_list->block_end;
+			nova_update_range_node_checksum(blknode);
+			ret = nova_insert_blocktree(sbi, tree, blknode);
+			if (ret) {
+				nova_err(sb, "%s failed\n", __func__);
+				nova_free_blocknode(sb, blknode);
+				return;
+			}
+			free_list->first_node = blknode;
+			free_list->last_node = blknode;
+			free_list->num_blocknode = 1;
+		}
+
+		nova_dbgv("%s: free list %d: block start %lu, end %lu, %lu free blocks\n",
+			  __func__, i,
+			  free_list->block_start,
+			  free_list->block_end,
+			  free_list->num_free_blocks);
+	}
+}
+
+static inline int nova_rbtree_compare_rangenode(struct nova_range_node *curr,
+	unsigned long range_low)
+{
+	if (range_low < curr->range_low)
+		return -1;
+	if (range_low > curr->range_high)
+		return 1;
+
+	return 0;
+}
+
+int nova_find_range_node(struct nova_sb_info *sbi,
+	struct rb_root *tree, unsigned long range_low,
+	struct nova_range_node **ret_node)
+{
+	struct nova_range_node *curr = NULL;
+	struct rb_node *temp;
+	int compVal;
+	int ret = 0;
+
+	temp = tree->rb_node;
+
+	while (temp) {
+		curr = container_of(temp, struct nova_range_node, node);
+		compVal = nova_rbtree_compare_rangenode(curr, range_low);
+
+		if (compVal == -1) {
+			temp = temp->rb_left;
+		} else if (compVal == 1) {
+			temp = temp->rb_right;
+		} else {
+			ret = 1;
+			break;
+		}
+	}
+
+	if (curr && !nova_range_node_checksum_ok(curr)) {
+		nova_dbg("%s: curr failed\n", __func__);
+		return 0;
+	}
+
+	*ret_node = curr;
+	return ret;
+}
+
+
+int nova_insert_range_node(struct rb_root *tree,
+	struct nova_range_node *new_node)
+{
+	struct nova_range_node *curr;
+	struct rb_node **temp, *parent;
+	int compVal;
+
+	temp = &(tree->rb_node);
+	parent = NULL;
+
+	while (*temp) {
+		curr = container_of(*temp, struct nova_range_node, node);
+		compVal = nova_rbtree_compare_rangenode(curr,
+					new_node->range_low);
+		parent = *temp;
+
+		if (compVal == -1) {
+			temp = &((*temp)->rb_left);
+		} else if (compVal == 1) {
+			temp = &((*temp)->rb_right);
+		} else {
+			nova_dbg("%s: entry %lu - %lu already exists: %lu - %lu\n",
+				 __func__, new_node->range_low,
+				new_node->range_high, curr->range_low,
+				curr->range_high);
+			return -EINVAL;
+		}
+	}
+
+	rb_link_node(&new_node->node, parent, temp);
+	rb_insert_color(&new_node->node, tree);
+
+	return 0;
+}
+
+inline int nova_insert_blocktree(struct nova_sb_info *sbi,
+	struct rb_root *tree, struct nova_range_node *new_node)
+{
+	int ret;
+
+	ret = nova_insert_range_node(tree, new_node);
+	if (ret)
+		nova_dbg("ERROR: %s failed %d\n", __func__, ret);
+
+	return ret;
+}
+
+
+/* Used for both block free tree and inode inuse tree */
+int nova_find_free_slot(struct nova_sb_info *sbi,
+	struct rb_root *tree, unsigned long range_low,
+	unsigned long range_high, struct nova_range_node **prev,
+	struct nova_range_node **next)
+{
+	struct nova_range_node *ret_node = NULL;
+	struct rb_node *tmp;
+	int check_prev = 0, check_next = 0;
+	int ret;
+
+	ret = nova_find_range_node(sbi, tree, range_low, &ret_node);
+	if (ret) {
+		nova_dbg("%s ERROR: %lu - %lu already in free list\n",
+			__func__, range_low, range_high);
+		return -EINVAL;
+	}
+
+	if (!ret_node) {
+		*prev = *next = NULL;
+	} else if (ret_node->range_high < range_low) {
+		*prev = ret_node;
+		tmp = rb_next(&ret_node->node);
+		if (tmp) {
+			*next = container_of(tmp, struct nova_range_node, node);
+			check_next = 1;
+		} else {
+			*next = NULL;
+		}
+	} else if (ret_node->range_low > range_high) {
+		*next = ret_node;
+		tmp = rb_prev(&ret_node->node);
+		if (tmp) {
+			*prev = container_of(tmp, struct nova_range_node, node);
+			check_prev = 1;
+		} else {
+			*prev = NULL;
+		}
+	} else {
+		nova_dbg("%s ERROR: %lu - %lu overlaps with existing node %lu - %lu\n",
+			 __func__, range_low, range_high, ret_node->range_low,
+			ret_node->range_high);
+		return -EINVAL;
+	}
+
+	if (check_prev && !nova_range_node_checksum_ok(*prev)) {
+		nova_dbg("%s: prev failed\n", __func__);
+		return -EIO;
+	}
+
+	if (check_next && !nova_range_node_checksum_ok(*next)) {
+		nova_dbg("%s: next failed\n", __func__);
+		return -EIO;
+	}
+
+	return 0;
+}
+
+static int nova_free_blocks(struct super_block *sb, unsigned long blocknr,
+	int num, unsigned short btype, int log_page)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+	struct rb_root *tree;
+	unsigned long block_low;
+	unsigned long block_high;
+	unsigned long num_blocks = 0;
+	struct nova_range_node *prev = NULL;
+	struct nova_range_node *next = NULL;
+	struct nova_range_node *curr_node;
+	struct free_list *free_list;
+	int cpuid;
+	int new_node_used = 0;
+	int ret;
+	timing_t free_time;
+
+	if (num <= 0) {
+		nova_dbg("%s ERROR: free %d\n", __func__, num);
+		return -EINVAL;
+	}
+
+	NOVA_START_TIMING(free_blocks_t, free_time);
+	cpuid = blocknr / sbi->per_list_blocks;
+
+	/* Pre-allocate blocknode */
+	curr_node = nova_alloc_blocknode(sb);
+	if (curr_node == NULL) {
+		/* returning without freeing the block*/
+		NOVA_END_TIMING(free_blocks_t, free_time);
+		return -ENOMEM;
+	}
+
+	free_list = nova_get_free_list(sb, cpuid);
+	spin_lock(&free_list->s_lock);
+
+	tree = &(free_list->block_free_tree);
+
+	num_blocks = nova_get_numblocks(btype) * num;
+	block_low = blocknr;
+	block_high = blocknr + num_blocks - 1;
+
+	nova_dbgv("Free: %lu - %lu\n", block_low, block_high);
+
+	if (blocknr < free_list->block_start ||
+			blocknr + num > free_list->block_end + 1) {
+		nova_err(sb, "free blocks %lu to %lu, free list %d, start %lu, end %lu\n",
+				blocknr, blocknr + num - 1,
+				free_list->index,
+				free_list->block_start,
+				free_list->block_end);
+		ret = -EIO;
+		goto out;
+	}
+
+	ret = nova_find_free_slot(sbi, tree, block_low,
+					block_high, &prev, &next);
+
+	if (ret) {
+		nova_dbg("%s: find free slot fail: %d\n", __func__, ret);
+		goto out;
+	}
+
+	if (prev && next && (block_low == prev->range_high + 1) &&
+			(block_high + 1 == next->range_low)) {
+		/* fits the hole */
+		rb_erase(&next->node, tree);
+		free_list->num_blocknode--;
+		prev->range_high = next->range_high;
+		nova_update_range_node_checksum(prev);
+		if (free_list->last_node == next)
+			free_list->last_node = prev;
+		nova_free_blocknode(sb, next);
+		goto block_found;
+	}
+	if (prev && (block_low == prev->range_high + 1)) {
+		/* Aligns left */
+		prev->range_high += num_blocks;
+		nova_update_range_node_checksum(prev);
+		goto block_found;
+	}
+	if (next && (block_high + 1 == next->range_low)) {
+		/* Aligns right */
+		next->range_low -= num_blocks;
+		nova_update_range_node_checksum(next);
+		goto block_found;
+	}
+
+	/* Aligns somewhere in the middle */
+	curr_node->range_low = block_low;
+	curr_node->range_high = block_high;
+	nova_update_range_node_checksum(curr_node);
+	new_node_used = 1;
+	ret = nova_insert_blocktree(sbi, tree, curr_node);
+	if (ret) {
+		new_node_used = 0;
+		goto out;
+	}
+	if (!prev)
+		free_list->first_node = curr_node;
+	if (!next)
+		free_list->last_node = curr_node;
+
+	free_list->num_blocknode++;
+
+block_found:
+	free_list->num_free_blocks += num_blocks;
+
+	if (log_page) {
+		free_list->free_log_count++;
+		free_list->freed_log_pages += num_blocks;
+	} else {
+		free_list->free_data_count++;
+		free_list->freed_data_pages += num_blocks;
+	}
+
+out:
+	spin_unlock(&free_list->s_lock);
+	if (new_node_used == 0)
+		nova_free_blocknode(sb, curr_node);
+
+	NOVA_END_TIMING(free_blocks_t, free_time);
+	return ret;
+}
+
+int nova_free_data_blocks(struct super_block *sb,
+	struct nova_inode_info_header *sih, unsigned long blocknr, int num)
+{
+	int ret;
+	timing_t free_time;
+
+	nova_dbgv("Inode %lu: free %d data block from %lu to %lu\n",
+			sih->ino, num, blocknr, blocknr + num - 1);
+	if (blocknr == 0) {
+		nova_dbg("%s: ERROR: %lu, %d\n", __func__, blocknr, num);
+		return -EINVAL;
+	}
+	NOVA_START_TIMING(free_data_t, free_time);
+	ret = nova_free_blocks(sb, blocknr, num, sih->i_blk_type, 0);
+	if (ret) {
+		nova_err(sb, "Inode %lu: free %d data block from %lu to %lu failed!\n",
+			 sih->ino, num, blocknr, blocknr + num - 1);
+		nova_print_nova_log(sb, sih);
+	}
+	NOVA_END_TIMING(free_data_t, free_time);
+
+	return ret;
+}
+
+int nova_free_log_blocks(struct super_block *sb,
+	struct nova_inode_info_header *sih, unsigned long blocknr, int num)
+{
+	int ret;
+	timing_t free_time;
+
+	nova_dbgv("Inode %lu: free %d log block from %lu to %lu\n",
+			sih->ino, num, blocknr, blocknr + num - 1);
+	if (blocknr == 0) {
+		nova_dbg("%s: ERROR: %lu, %d\n", __func__, blocknr, num);
+		return -EINVAL;
+	}
+	NOVA_START_TIMING(free_log_t, free_time);
+	ret = nova_free_blocks(sb, blocknr, num, sih->i_blk_type, 1);
+	if (ret) {
+		nova_err(sb, "Inode %lu: free %d log block from %lu to %lu failed!\n",
+			 sih->ino, num, blocknr, blocknr + num - 1);
+		nova_print_nova_log(sb, sih);
+	}
+	NOVA_END_TIMING(free_log_t, free_time);
+
+	return ret;
+}
+
+static int not_enough_blocks(struct free_list *free_list,
+	unsigned long num_blocks, enum alloc_type atype)
+{
+	struct nova_range_node *first = free_list->first_node;
+	struct nova_range_node *last = free_list->last_node;
+
+	if (free_list->num_free_blocks < num_blocks || !first || !last) {
+		nova_dbgv("%s: num_free_blocks=%ld; num_blocks=%ld; first=0x%p; last=0x%p",
+			  __func__, free_list->num_free_blocks, num_blocks,
+			  first, last);
+		return 1;
+	}
+
+	if (atype == LOG &&
+	    last->range_high - first->range_low < DEAD_ZONE_BLOCKS) {
+		nova_dbgv("%s: allocation would cause deadzone violation. high=0x%lx, low=0x%lx, DEADZONE=%d",
+			  __func__, last->range_high, first->range_low,
+			  DEAD_ZONE_BLOCKS);
+		return 1;
+	}
+
+	return 0;
+}
+
+/* Return how many blocks allocated */
+static long nova_alloc_blocks_in_free_list(struct super_block *sb,
+	struct free_list *free_list, unsigned short btype,
+	enum alloc_type atype, unsigned long num_blocks,
+	unsigned long *new_blocknr, enum nova_alloc_direction from_tail)
+{
+	struct rb_root *tree;
+	struct nova_range_node *curr, *next = NULL, *prev = NULL;
+	struct rb_node *temp, *next_node, *prev_node;
+	unsigned long curr_blocks;
+	bool found = 0;
+	unsigned long step = 0;
+
+	if (!free_list->first_node || free_list->num_free_blocks == 0) {
+		nova_dbgv("%s: Can't alloc. free_list->first_node=0x%p free_list->num_free_blocks = %lu",
+			  __func__, free_list->first_node,
+			  free_list->num_free_blocks);
+		return -ENOSPC;
+	}
+
+	if (atype == LOG && not_enough_blocks(free_list, num_blocks, atype)) {
+		nova_dbgv("%s: Can't alloc.  not_enough_blocks() == true",
+			  __func__);
+		return -ENOSPC;
+	}
+
+	tree = &(free_list->block_free_tree);
+	if (from_tail == ALLOC_FROM_HEAD)
+		temp = &(free_list->first_node->node);
+	else
+		temp = &(free_list->last_node->node);
+
+	while (temp) {
+		step++;
+		curr = container_of(temp, struct nova_range_node, node);
+
+		if (!nova_range_node_checksum_ok(curr)) {
+			nova_err(sb, "%s curr failed\n", __func__);
+			goto next;
+		}
+
+		curr_blocks = curr->range_high - curr->range_low + 1;
+
+		if (num_blocks >= curr_blocks) {
+			/* Superpage allocation must succeed */
+			if (btype > 0 && num_blocks > curr_blocks)
+				goto next;
+
+			/* Otherwise, allocate the whole blocknode */
+			if (curr == free_list->first_node) {
+				next_node = rb_next(temp);
+				if (next_node)
+					next = container_of(next_node,
+						struct nova_range_node, node);
+				free_list->first_node = next;
+			}
+
+			if (curr == free_list->last_node) {
+				prev_node = rb_prev(temp);
+				if (prev_node)
+					prev = container_of(prev_node,
+						struct nova_range_node, node);
+				free_list->last_node = prev;
+			}
+
+			rb_erase(&curr->node, tree);
+			free_list->num_blocknode--;
+			num_blocks = curr_blocks;
+			*new_blocknr = curr->range_low;
+			nova_free_blocknode(sb, curr);
+			found = 1;
+			break;
+		}
+
+		/* Allocate partial blocknode */
+		if (from_tail == ALLOC_FROM_HEAD) {
+			*new_blocknr = curr->range_low;
+			curr->range_low += num_blocks;
+		} else {
+			*new_blocknr = curr->range_high + 1 - num_blocks;
+			curr->range_high -= num_blocks;
+		}
+
+		nova_update_range_node_checksum(curr);
+		found = 1;
+		break;
+next:
+		if (from_tail == ALLOC_FROM_HEAD)
+			temp = rb_next(temp);
+		else
+			temp = rb_prev(temp);
+	}
+
+	if (free_list->num_free_blocks < num_blocks) {
+		nova_dbg("%s: free list %d has %lu free blocks, but allocated %lu blocks?\n",
+				__func__, free_list->index,
+				free_list->num_free_blocks, num_blocks);
+		return -ENOSPC;
+	}
+
+	if (found == 1)
+		free_list->num_free_blocks -= num_blocks;
+	else {
+		nova_dbgv("%s: Can't alloc.  found = %d", __func__, found);
+		return -ENOSPC;
+	}
+
+	NOVA_STATS_ADD(alloc_steps, step);
+
+	return num_blocks;
+}
+
+/* Find out the free list with most free blocks */
+static int nova_get_candidate_free_list(struct super_block *sb)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+	struct free_list *free_list;
+	int cpuid = 0;
+	int num_free_blocks = 0;
+	int i;
+
+	for (i = 0; i < sbi->cpus; i++) {
+		free_list = nova_get_free_list(sb, i);
+		if (free_list->num_free_blocks > num_free_blocks) {
+			cpuid = i;
+			num_free_blocks = free_list->num_free_blocks;
+		}
+	}
+
+	return cpuid;
+}
+
+static int nova_new_blocks(struct super_block *sb, unsigned long *blocknr,
+	unsigned int num, unsigned short btype, int zero,
+	enum alloc_type atype, int cpuid, enum nova_alloc_direction from_tail)
+{
+	struct free_list *free_list;
+	void *bp;
+	unsigned long num_blocks = 0;
+	unsigned long new_blocknr = 0;
+	long ret_blocks = 0;
+	int retried = 0;
+	timing_t alloc_time;
+
+	num_blocks = num * nova_get_numblocks(btype);
+	if (num_blocks == 0) {
+		nova_dbg_verbose("%s: num_blocks == 0", __func__);
+		return -EINVAL;
+	}
+
+	NOVA_START_TIMING(new_blocks_t, alloc_time);
+	if (cpuid == ANY_CPU)
+		cpuid = smp_processor_id();
+
+retry:
+	free_list = nova_get_free_list(sb, cpuid);
+	spin_lock(&free_list->s_lock);
+
+	if (not_enough_blocks(free_list, num_blocks, atype)) {
+		nova_dbgv("%s: cpu %d, free_blocks %lu, required %lu, blocknode %lu\n",
+			  __func__, cpuid, free_list->num_free_blocks,
+			  num_blocks, free_list->num_blocknode);
+
+		if (retried >= 2)
+			/* Allocate anyway */
+			goto alloc;
+
+		spin_unlock(&free_list->s_lock);
+		cpuid = nova_get_candidate_free_list(sb);
+		retried++;
+		goto retry;
+	}
+alloc:
+	ret_blocks = nova_alloc_blocks_in_free_list(sb, free_list, btype, atype,
+					num_blocks, &new_blocknr, from_tail);
+
+	if (ret_blocks > 0) {
+		if (atype == LOG) {
+			free_list->alloc_log_count++;
+			free_list->alloc_log_pages += ret_blocks;
+		} else if (atype == DATA) {
+			free_list->alloc_data_count++;
+			free_list->alloc_data_pages += ret_blocks;
+		}
+	}
+
+	spin_unlock(&free_list->s_lock);
+	NOVA_END_TIMING(new_blocks_t, alloc_time);
+
+	if (ret_blocks <= 0 || new_blocknr == 0) {
+		nova_dbg_verbose("%s: not able to allocate %d blocks.  ret_blocks=%ld; new_blocknr=%lu",
+				 __func__, num, ret_blocks, new_blocknr);
+		return -ENOSPC;
+	}
+
+	if (zero) {
+		bp = nova_get_block(sb, nova_get_block_off(sb,
+						new_blocknr, btype));
+		nova_memunlock_range(sb, bp, PAGE_SIZE * ret_blocks);
+		memset_nt(bp, 0, PAGE_SIZE * ret_blocks);
+		nova_memlock_range(sb, bp, PAGE_SIZE * ret_blocks);
+	}
+	*blocknr = new_blocknr;
+
+	nova_dbg_verbose("Alloc %lu NVMM blocks 0x%lx\n", ret_blocks, *blocknr);
+	return ret_blocks / nova_get_numblocks(btype);
+}
+
+// Allocate data blocks.  The offset for the allocated block comes back in
+// blocknr.  Return the number of blocks allocated.
+inline int nova_new_data_blocks(struct super_block *sb,
+	struct nova_inode_info_header *sih, unsigned long *blocknr,
+	unsigned long start_blk, unsigned int num,
+	enum nova_alloc_init zero, int cpu,
+	enum nova_alloc_direction from_tail)
+{
+	int allocated;
+	timing_t alloc_time;
+
+	NOVA_START_TIMING(new_data_blocks_t, alloc_time);
+	allocated = nova_new_blocks(sb, blocknr, num,
+			    sih->i_blk_type, zero, DATA, cpu, from_tail);
+	NOVA_END_TIMING(new_data_blocks_t, alloc_time);
+	if (allocated < 0) {
+		nova_dbgv("FAILED: Inode %lu, start blk %lu, alloc %d data blocks from %lu to %lu\n",
+			  sih->ino, start_blk, allocated, *blocknr,
+			  *blocknr + allocated - 1);
+	} else {
+		nova_dbgv("Inode %lu, start blk %lu, alloc %d data blocks from %lu to %lu\n",
+			  sih->ino, start_blk, allocated, *blocknr,
+			  *blocknr + allocated - 1);
+	}
+	return allocated;
+}
+
+
+// Allocate log blocks.	 The offset for the allocated block comes back in
+// blocknr.  Return the number of blocks allocated.
+inline int nova_new_log_blocks(struct super_block *sb,
+			struct nova_inode_info_header *sih,
+			unsigned long *blocknr, unsigned int num,
+			enum nova_alloc_init zero, int cpu,
+			enum nova_alloc_direction from_tail)
+{
+	int allocated;
+	timing_t alloc_time;
+
+	NOVA_START_TIMING(new_log_blocks_t, alloc_time);
+	allocated = nova_new_blocks(sb, blocknr, num,
+			    sih->i_blk_type, zero, LOG, cpu, from_tail);
+	NOVA_END_TIMING(new_log_blocks_t, alloc_time);
+	if (allocated < 0) {
+		nova_dbgv("%s: ino %lu, failed to alloc %d log blocks",
+			  __func__, sih->ino, num);
+	} else {
+		nova_dbgv("%s: ino %lu, alloc %d of %d log blocks %lu to %lu\n",
+			  __func__, sih->ino, allocated, num, *blocknr,
+			  *blocknr + allocated - 1);
+	}
+	return allocated;
+}
+
+unsigned long nova_count_free_blocks(struct super_block *sb)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+	struct free_list *free_list;
+	unsigned long num_free_blocks = 0;
+	int i;
+
+	for (i = 0; i < sbi->cpus; i++) {
+		free_list = nova_get_free_list(sb, i);
+		num_free_blocks += free_list->num_free_blocks;
+	}
+
+	return num_free_blocks;
+}
+
+
diff --git a/fs/nova/balloc.h b/fs/nova/balloc.h
new file mode 100644
index 000000000000..ce7166a5bf37
--- /dev/null
+++ b/fs/nova/balloc.h
@@ -0,0 +1,118 @@
+#ifndef __BALLOC_H
+#define __BALLOC_H
+
+#include "inode.h"
+
+/* DRAM structure to hold a list of free PMEM blocks */
+struct free_list {
+	spinlock_t s_lock;
+	struct rb_root	block_free_tree;
+	struct nova_range_node *first_node; // lowest address free range
+	struct nova_range_node *last_node; // highest address free range
+
+	int		index; // Which CPU do I belong to?
+
+	/* Where are the data checksum blocks */
+	unsigned long	csum_start;
+	unsigned long	replica_csum_start;
+	unsigned long	num_csum_blocks;
+
+	/* Where are the data parity blocks */
+	unsigned long	parity_start;
+	unsigned long	replica_parity_start;
+	unsigned long	num_parity_blocks;
+
+	/* Start and end of allocatable range, inclusive. Excludes csum and
+	 * parity blocks.
+	 */
+	unsigned long	block_start;
+	unsigned long	block_end;
+
+	unsigned long	num_free_blocks;
+
+	/* How many nodes in the rb tree? */
+	unsigned long	num_blocknode;
+
+	u32		csum;		/* Protect integrity */
+
+	/* Statistics */
+	unsigned long	alloc_log_count;
+	unsigned long	alloc_data_count;
+	unsigned long	free_log_count;
+	unsigned long	free_data_count;
+	unsigned long	alloc_log_pages;
+	unsigned long	alloc_data_pages;
+	unsigned long	freed_log_pages;
+	unsigned long	freed_data_pages;
+
+	u64		padding[8];	/* Cache line break */
+};
+
+static inline
+struct free_list *nova_get_free_list(struct super_block *sb, int cpu)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+
+	return &sbi->free_lists[cpu];
+}
+
+enum nova_alloc_direction {ALLOC_FROM_HEAD = 0,
+			   ALLOC_FROM_TAIL = 1};
+
+enum nova_alloc_init {ALLOC_NO_INIT = 0,
+		      ALLOC_INIT_ZERO = 1};
+
+enum alloc_type {
+	LOG = 1,
+	DATA,
+};
+
+
+
+
+int nova_alloc_block_free_lists(struct super_block *sb);
+void nova_delete_free_lists(struct super_block *sb);
+inline struct nova_range_node *nova_alloc_blocknode(struct super_block *sb);
+inline struct nova_range_node *nova_alloc_inode_node(struct super_block *sb);
+inline struct vma_item *nova_alloc_vma_item(struct super_block *sb);
+inline void nova_free_range_node(struct nova_range_node *node);
+inline void nova_free_snapshot_info(struct snapshot_info *info);
+inline void nova_free_blocknode(struct super_block *sb,
+	struct nova_range_node *bnode);
+inline void nova_free_inode_node(struct super_block *sb,
+	struct nova_range_node *bnode);
+inline void nova_free_vma_item(struct super_block *sb,
+	struct vma_item *item);
+extern void nova_init_blockmap(struct super_block *sb, int recovery);
+extern int nova_free_data_blocks(struct super_block *sb,
+	struct nova_inode_info_header *sih, unsigned long blocknr, int num);
+extern int nova_free_log_blocks(struct super_block *sb,
+	struct nova_inode_info_header *sih, unsigned long blocknr, int num);
+extern inline int nova_new_data_blocks(struct super_block *sb,
+	struct nova_inode_info_header *sih, unsigned long *blocknr,
+	unsigned long start_blk, unsigned int num,
+	enum nova_alloc_init zero, int cpu,
+	enum nova_alloc_direction from_tail);
+extern int nova_new_log_blocks(struct super_block *sb,
+	struct nova_inode_info_header *sih,
+	unsigned long *blocknr, unsigned int num,
+	enum nova_alloc_init zero, int cpu,
+	enum nova_alloc_direction from_tail);
+extern unsigned long nova_count_free_blocks(struct super_block *sb);
+inline int nova_search_inodetree(struct nova_sb_info *sbi,
+	unsigned long ino, struct nova_range_node **ret_node);
+inline int nova_insert_blocktree(struct nova_sb_info *sbi,
+	struct rb_root *tree, struct nova_range_node *new_node);
+inline int nova_insert_inodetree(struct nova_sb_info *sbi,
+	struct nova_range_node *new_node, int cpu);
+int nova_find_free_slot(struct nova_sb_info *sbi,
+	struct rb_root *tree, unsigned long range_low,
+	unsigned long range_high, struct nova_range_node **prev,
+	struct nova_range_node **next);
+
+extern int nova_insert_range_node(struct rb_root *tree,
+				  struct nova_range_node *new_node);
+extern int nova_find_range_node(struct nova_sb_info *sbi,
+				struct rb_root *tree, unsigned long range_low,
+				struct nova_range_node **ret_node);
+#endif

[toc] | [prev] | [next] | [standalone]

#1702746 — [RFC 06/16] NOVA: Lite-weight journaling for complex ops

From	Steven Swanson <swanson@eng.ucsd.edu>
Date	2017-08-03 10:00 +0200
Subject	[RFC 06/16] NOVA: Lite-weight journaling for complex ops
Message-ID	<uajd0-5jY-15@gated-at.bofh.it>
In reply to	#1702740

Nova uses a lightweight journaling mechanisms to provide atomicity for
operations that modify more than one on inode.  The journals providing logging
for two operations:

1.  Single word updates (JOURNAL_ENTRY)
2.  Copying inodes (JOURNAL_INODE)

The journals are undo logs: Nova creates the journal entries for an operation,
and if the operation does not complete due to a system failure, the recovery
process rolls back the changes using the journal entries.

To commit, Nova drops the log.

Nova maintains one journal per CPU.  The head and tail pointers for each
journal live in a reserved page near the beginning of the file system.

During recovery, Nova scans the journals and undoes the operations described by
each entry.

Signed-off-by: Steven Swanson <swanson@cs.ucsd.edu>
---
 fs/nova/journal.c |  474 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/nova/journal.h |   61 +++++++
 2 files changed, 535 insertions(+)
 create mode 100644 fs/nova/journal.c
 create mode 100644 fs/nova/journal.h

diff --git a/fs/nova/journal.c b/fs/nova/journal.c
new file mode 100644
index 000000000000..b05c7212929f
--- /dev/null
+++ b/fs/nova/journal.c
@@ -0,0 +1,474 @@
+/*
+ * NOVA journaling facility.
+ *
+ * This file contains journaling code to guarantee the atomicity of directory
+ * operations that span multiple inodes (unlink, rename, etc).
+ *
+ * Copyright 2015-2016 Regents of the University of California,
+ * UCSD Non-Volatile Systems Lab, Andiry Xu <jix024@cs.ucsd.edu>
+ * Copyright 2012-2013 Intel Corporation
+ * Copyright 2009-2011 Marco Stornelli <marco.stornelli@gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include <linux/module.h>
+#include <linux/string.h>
+#include <linux/init.h>
+#include <linux/vfs.h>
+#include <linux/uaccess.h>
+#include <linux/mm.h>
+#include <linux/mutex.h>
+#include <linux/sched.h>
+#include "nova.h"
+#include "journal.h"
+
+/**************************** Lite journal ******************************/
+
+static inline void
+nova_print_lite_transaction(struct nova_lite_journal_entry *entry)
+{
+	nova_dbg("Entry %p: Type %llu, data1 0x%llx, data2 0x%llx\n, checksum %u\n",
+			entry, entry->type,
+			entry->data1, entry->data2, entry->csum);
+}
+
+static inline int nova_update_journal_entry_csum(struct super_block *sb,
+	struct nova_lite_journal_entry *entry)
+{
+	u32 crc = 0;
+
+	crc = nova_crc32c(~0, (__u8 *)entry,
+			(sizeof(struct nova_lite_journal_entry)
+			 - sizeof(__le32)));
+
+	entry->csum = cpu_to_le32(crc);
+	nova_flush_buffer(entry, sizeof(struct nova_lite_journal_entry), 0);
+	return 0;
+}
+
+static inline int nova_check_entry_integrity(struct super_block *sb,
+	struct nova_lite_journal_entry *entry)
+{
+	u32 crc = 0;
+
+	crc = nova_crc32c(~0, (__u8 *)entry,
+			(sizeof(struct nova_lite_journal_entry)
+			 - sizeof(__le32)));
+
+	if (entry->csum == cpu_to_le32(crc))
+		return 0;
+	else
+		return 1;
+}
+
+// Get the next journal entry.  Journal entries are stored in a circular
+// buffer.  They live a 1-page circular buffer.
+//
+// TODO: Add check to ensure that the journal doesn't grow too large.
+static inline u64 next_lite_journal(u64 curr_p)
+{
+	size_t size = sizeof(struct nova_lite_journal_entry);
+
+	if ((curr_p & (PAGE_SIZE - 1)) + size >= PAGE_SIZE)
+		return (curr_p & PAGE_MASK);
+
+	return curr_p + size;
+}
+
+// Walk the journal for one CPU, and verify the checksum on each entry.
+static int nova_check_journal_entries(struct super_block *sb,
+	struct journal_ptr_pair *pair)
+{
+	struct nova_lite_journal_entry *entry;
+	u64 temp;
+	int ret;
+
+	temp = pair->journal_head;
+	while (temp != pair->journal_tail) {
+		entry = (struct nova_lite_journal_entry *)nova_get_block(sb,
+									temp);
+		ret = nova_check_entry_integrity(sb, entry);
+		if (ret) {
+			nova_dbg("Entry %p checksum failure\n", entry);
+			nova_print_lite_transaction(entry);
+			return ret;
+		}
+		temp = next_lite_journal(temp);
+	}
+
+	return 0;
+}
+
+/**************************** Journal Recovery ******************************/
+
+static void nova_undo_journal_inode(struct super_block *sb,
+	struct nova_lite_journal_entry *entry)
+{
+	struct nova_inode *pi, *alter_pi;
+	u64 pi_addr, alter_pi_addr;
+
+	if (metadata_csum == 0)
+		return;
+
+	pi_addr = le64_to_cpu(entry->data1);
+	alter_pi_addr = le64_to_cpu(entry->data2);
+
+	pi = (struct nova_inode *)nova_get_block(sb, pi_addr);
+	alter_pi = (struct nova_inode *)nova_get_block(sb, alter_pi_addr);
+
+	memcpy_to_pmem_nocache(pi, alter_pi, sizeof(struct nova_inode));
+}
+
+static void nova_undo_journal_entry(struct super_block *sb,
+	struct nova_lite_journal_entry *entry)
+{
+	u64 addr, value;
+
+	addr = le64_to_cpu(entry->data1);
+	value = le64_to_cpu(entry->data2);
+
+	*(u64 *)nova_get_block(sb, addr) = (u64)value;
+	nova_flush_buffer((void *)nova_get_block(sb, addr), CACHELINE_SIZE, 0);
+}
+
+static void nova_undo_lite_journal_entry(struct super_block *sb,
+	struct nova_lite_journal_entry *entry)
+{
+	u64 type;
+
+	type = le64_to_cpu(entry->type);
+
+	switch (type) {
+	case JOURNAL_INODE:
+		nova_undo_journal_inode(sb, entry);
+		break;
+	case JOURNAL_ENTRY:
+		nova_undo_journal_entry(sb, entry);
+		break;
+	default:
+		nova_dbg("%s: unknown data type %llu\n", __func__, type);
+		break;
+	}
+}
+
+/* Roll back all journal enries */
+static int nova_recover_lite_journal(struct super_block *sb,
+	struct journal_ptr_pair *pair)
+{
+	struct nova_lite_journal_entry *entry;
+	u64 temp;
+
+	nova_memunlock_journal(sb);
+	temp = pair->journal_head;
+	while (temp != pair->journal_tail) {
+		entry = (struct nova_lite_journal_entry *)nova_get_block(sb,
+									temp);
+		nova_undo_lite_journal_entry(sb, entry);
+		temp = next_lite_journal(temp);
+	}
+
+	pair->journal_tail = pair->journal_head;
+	nova_memlock_journal(sb);
+	nova_flush_buffer(&pair->journal_head, CACHELINE_SIZE, 1);
+
+	return 0;
+}
+
+/**************************** Create/commit ******************************/
+
+static u64 nova_append_replica_inode_journal(struct super_block *sb,
+	u64 curr_p, struct inode *inode)
+{
+	struct nova_lite_journal_entry *entry;
+	struct nova_inode_info *si = NOVA_I(inode);
+	struct nova_inode_info_header *sih = &si->header;
+
+	entry = (struct nova_lite_journal_entry *)nova_get_block(sb,
+							curr_p);
+	entry->type = cpu_to_le64(JOURNAL_INODE);
+	entry->padding = 0;
+	entry->data1 = cpu_to_le64(sih->pi_addr);
+	entry->data2 = cpu_to_le64(sih->alter_pi_addr);
+	nova_update_journal_entry_csum(sb, entry);
+
+	curr_p = next_lite_journal(curr_p);
+	return curr_p;
+}
+
+/* Create and append an undo entry for a small update to PMEM. */
+static u64 nova_append_entry_journal(struct super_block *sb,
+	u64 curr_p, void *field)
+{
+	struct nova_lite_journal_entry *entry;
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+	u64 *aligned_field;
+	u64 addr;
+
+	entry = (struct nova_lite_journal_entry *)nova_get_block(sb,
+							curr_p);
+	entry->type = cpu_to_le64(JOURNAL_ENTRY);
+	entry->padding = 0;
+	/* Align to 8 bytes */
+	aligned_field = (u64 *)((unsigned long)field & ~7UL);
+	/* Store the offset from the start of Nova instead of the pointer */
+	addr = (u64)nova_get_addr_off(sbi, aligned_field);
+	entry->data1 = cpu_to_le64(addr);
+	entry->data2 = cpu_to_le64(*aligned_field);
+	nova_update_journal_entry_csum(sb, entry);
+
+	curr_p = next_lite_journal(curr_p);
+	return curr_p;
+}
+
+static u64 nova_journal_inode_tail(struct super_block *sb,
+	u64 curr_p, struct nova_inode *pi)
+{
+	curr_p = nova_append_entry_journal(sb, curr_p, &pi->log_tail);
+	if (metadata_csum)
+		curr_p = nova_append_entry_journal(sb, curr_p,
+						&pi->alter_log_tail);
+	return curr_p;
+}
+
+/* Create and append undo log entries for creating a new file or directory. */
+static u64 nova_append_inode_journal(struct super_block *sb,
+	u64 curr_p, struct inode *inode, int new_inode,
+	int invalidate, int is_dir)
+{
+	struct nova_inode *pi = nova_get_inode(sb, inode);
+
+	if (metadata_csum)
+		return nova_append_replica_inode_journal(sb, curr_p, inode);
+
+	if (!pi) {
+		nova_err(sb, "%s: get inode failed\n", __func__);
+		return curr_p;
+	}
+
+	if (is_dir)
+		return nova_journal_inode_tail(sb, curr_p, pi);
+
+	if (new_inode) {
+		curr_p = nova_append_entry_journal(sb, curr_p,
+						&pi->valid);
+	} else {
+		curr_p = nova_journal_inode_tail(sb, curr_p, pi);
+		if (invalidate) {
+			curr_p = nova_append_entry_journal(sb, curr_p,
+						&pi->valid);
+			curr_p = nova_append_entry_journal(sb, curr_p,
+						&pi->delete_epoch_id);
+		}
+	}
+
+	return curr_p;
+}
+
+static u64 nova_append_dentry_journal(struct super_block *sb,
+	u64 curr_p, struct nova_dentry *dentry)
+{
+	curr_p = nova_append_entry_journal(sb, curr_p, &dentry->ino);
+	curr_p = nova_append_entry_journal(sb, curr_p, &dentry->csum);
+	return curr_p;
+}
+
+/* Journaled transactions for inode creation */
+u64 nova_create_inode_transaction(struct super_block *sb,
+	struct inode *inode, struct inode *dir, int cpu,
+	int new_inode, int invalidate)
+{
+	struct journal_ptr_pair *pair;
+	u64 temp;
+
+	pair = nova_get_journal_pointers(sb, cpu);
+	if (pair->journal_head == 0 ||
+			pair->journal_head != pair->journal_tail)
+		BUG();
+
+	temp = pair->journal_head;
+
+	temp = nova_append_inode_journal(sb, temp, inode,
+					new_inode, invalidate, 0);
+
+	temp = nova_append_inode_journal(sb, temp, dir,
+					new_inode, invalidate, 1);
+
+	pair->journal_tail = temp;
+	nova_flush_buffer(&pair->journal_head, CACHELINE_SIZE, 1);
+
+	nova_dbgv("%s: head 0x%llx, tail 0x%llx\n",
+			__func__, pair->journal_head, pair->journal_tail);
+	return temp;
+}
+
+/* Journaled transactions for rename operations */
+u64 nova_create_rename_transaction(struct super_block *sb,
+	struct inode *old_inode, struct inode *old_dir, struct inode *new_inode,
+	struct inode *new_dir, struct nova_dentry *father_entry,
+	int invalidate_new_inode, int cpu)
+{
+	struct journal_ptr_pair *pair;
+	u64 temp;
+
+	pair = nova_get_journal_pointers(sb, cpu);
+	if (pair->journal_head == 0 ||
+			pair->journal_head != pair->journal_tail)
+		BUG();
+
+	temp = pair->journal_head;
+
+	/* Journal tails for old inode */
+	temp = nova_append_inode_journal(sb, temp, old_inode, 0, 0, 0);
+
+	/* Journal tails for old dir */
+	temp = nova_append_inode_journal(sb, temp, old_dir, 0, 0, 1);
+
+	if (new_inode) {
+		/* New inode may be unlinked */
+		temp = nova_append_inode_journal(sb, temp, new_inode, 0,
+					invalidate_new_inode, 0);
+	}
+
+	if (new_dir)
+		temp = nova_append_inode_journal(sb, temp, new_dir, 0, 0, 1);
+
+	if (father_entry)
+		temp = nova_append_dentry_journal(sb, temp, father_entry);
+
+	pair->journal_tail = temp;
+	nova_flush_buffer(&pair->journal_head, CACHELINE_SIZE, 1);
+
+	nova_dbgv("%s: head 0x%llx, tail 0x%llx\n",
+			__func__, pair->journal_head, pair->journal_tail);
+	return temp;
+}
+
+/* For log entry inplace update */
+u64 nova_create_logentry_transaction(struct super_block *sb,
+	void *entry, enum nova_entry_type type, int cpu)
+{
+	struct journal_ptr_pair *pair;
+	size_t size = 0;
+	int i, count;
+	u64 temp;
+
+	pair = nova_get_journal_pointers(sb, cpu);
+	if (pair->journal_head == 0 ||
+			pair->journal_head != pair->journal_tail)
+		BUG();
+
+	size = nova_get_log_entry_size(sb, type);
+
+	temp = pair->journal_head;
+
+	count = size / 8;
+	for (i = 0; i < count; i++) {
+		temp = nova_append_entry_journal(sb, temp,
+						(char *)entry + i * 8);
+	}
+
+	pair->journal_tail = temp;
+	nova_flush_buffer(&pair->journal_head, CACHELINE_SIZE, 1);
+
+	nova_dbgv("%s: head 0x%llx, tail 0x%llx\n",
+			__func__, pair->journal_head, pair->journal_tail);
+	return temp;
+}
+
+/* Commit the transactions by dropping the journal entries */
+void nova_commit_lite_transaction(struct super_block *sb, u64 tail, int cpu)
+{
+	struct journal_ptr_pair *pair;
+
+	pair = nova_get_journal_pointers(sb, cpu);
+	if (pair->journal_tail != tail)
+		BUG();
+
+	pair->journal_head = tail;
+	nova_flush_buffer(&pair->journal_head, CACHELINE_SIZE, 1);
+}
+
+/**************************** Initialization ******************************/
+
+// Initialized DRAM journal state, validate, and recover
+int nova_lite_journal_soft_init(struct super_block *sb)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+	struct journal_ptr_pair *pair;
+	int i;
+	int ret = 0;
+
+	sbi->journal_locks = kcalloc(sbi->cpus, sizeof(spinlock_t),
+				     GFP_KERNEL);
+	if (!sbi->journal_locks)
+		return -ENOMEM;
+
+	for (i = 0; i < sbi->cpus; i++)
+		spin_lock_init(&sbi->journal_locks[i]);
+
+	for (i = 0; i < sbi->cpus; i++) {
+		pair = nova_get_journal_pointers(sb, i);
+		if (pair->journal_head == pair->journal_tail)
+			continue;
+
+		/* Ensure all entries are genuine */
+		ret = nova_check_journal_entries(sb, pair);
+		if (ret) {
+			nova_err(sb, "Journal %d checksum failure\n", i);
+			ret = -EINVAL;
+			break;
+		}
+
+		ret = nova_recover_lite_journal(sb, pair);
+	}
+
+	return ret;
+}
+
+/* Initialized persistent journal state */
+int nova_lite_journal_hard_init(struct super_block *sb)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+	struct nova_inode_info_header sih;
+	struct journal_ptr_pair *pair;
+	unsigned long blocknr = 0;
+	int allocated;
+	int i;
+	u64 block;
+
+	sih.ino = NOVA_LITEJOURNAL_INO;
+	sih.i_blk_type = NOVA_BLOCK_TYPE_4K;
+
+	for (i = 0; i < sbi->cpus; i++) {
+		pair = nova_get_journal_pointers(sb, i);
+
+		allocated = nova_new_log_blocks(sb, &sih, &blocknr, 1,
+			ALLOC_INIT_ZERO, ANY_CPU, ALLOC_FROM_HEAD);
+		nova_dbg_verbose("%s: allocate log @ 0x%lx\n", __func__,
+							blocknr);
+		if (allocated != 1 || blocknr == 0)
+			return -ENOSPC;
+
+		block = nova_get_block_off(sb, blocknr, NOVA_BLOCK_TYPE_4K);
+		nova_memunlock_range(sb, pair, CACHELINE_SIZE);
+		pair->journal_head = pair->journal_tail = block;
+		nova_flush_buffer(pair, CACHELINE_SIZE, 0);
+		nova_memlock_range(sb, pair, CACHELINE_SIZE);
+	}
+
+	PERSISTENT_BARRIER();
+	return nova_lite_journal_soft_init(sb);
+}
+
diff --git a/fs/nova/journal.h b/fs/nova/journal.h
new file mode 100644
index 000000000000..621138bb6eac
--- /dev/null
+++ b/fs/nova/journal.h
@@ -0,0 +1,61 @@
+#ifndef __JOURNAL_H
+#define __JOURNAL_H
+
+#include <linux/types.h>
+#include <linux/fs.h>
+#include "nova.h"
+#include "super.h"
+
+
+/* ======================= Lite journal ========================= */
+
+#define NOVA_MAX_JOURNAL_LENGTH 128
+
+#define	JOURNAL_INODE	1
+#define	JOURNAL_ENTRY	2
+
+/* Lightweight journal entry */
+struct nova_lite_journal_entry {
+	__le64 type;       // JOURNAL_INODE or JOURNAL_ENTRY
+	__le64 data1;
+	__le64 data2;
+	__le32 padding;
+	__le32 csum;
+} __attribute((__packed__));
+
+/* Head and tail pointers into a circular queue of journal entries.  There's
+ * one of these per CPU.
+ */
+struct journal_ptr_pair {
+	__le64 journal_head;
+	__le64 journal_tail;
+};
+
+static inline
+struct journal_ptr_pair *nova_get_journal_pointers(struct super_block *sb,
+	int cpu)
+{
+	struct nova_sb_info *sbi = NOVA_SB(sb);
+
+	if (cpu >= sbi->cpus)
+		BUG();
+
+	return (struct journal_ptr_pair *)((char *)nova_get_block(sb,
+		NOVA_DEF_BLOCK_SIZE_4K * JOURNAL_START) + cpu * CACHELINE_SIZE);
+}
+
+
+u64 nova_create_inode_transaction(struct super_block *sb,
+	struct inode *inode, struct inode *dir, int cpu,
+	int new_inode, int invalidate);
+u64 nova_create_rename_transaction(struct super_block *sb,
+	struct inode *old_inode, struct inode *old_dir, struct inode *new_inode,
+	struct inode *new_dir, struct nova_dentry *father_entry,
+	int invalidate_new_inode, int cpu);
+u64 nova_create_logentry_transaction(struct super_block *sb,
+	void *entry, enum nova_entry_type type, int cpu);
+void nova_commit_lite_transaction(struct super_block *sb, u64 tail, int cpu);
+int nova_lite_journal_soft_init(struct super_block *sb);
+int nova_lite_journal_hard_init(struct super_block *sb);
+
+#endif

[toc] | [prev] | [next] | [standalone]

#1703489 — Re: [RFC 01/16] NOVA: Documentation

From	Randy Dunlap <rdunlap@infradead.org>
Date	2017-08-04 00:40 +0200
Subject	Re: [RFC 01/16] NOVA: Documentation
Message-ID	<uawWC-6uI-37@gated-at.bofh.it>
In reply to	#1702740

On 08/03/2017 12:48 AM, Steven Swanson wrote:
> A brief overview is in README.md.
> 

See below.

> Implementation and usage details are in Documentation/filesystems/nova.txt.
> 

Reviewed in a separate email.

> These two papers provide a detailed, high-level description of NOVA's design goals and approach:
> 
>    NOVA: A Log-structured File system for Hybrid Volatile/Non-volatile Main Memories (http://cseweb.ucsd.edu/~swanson/papers/FAST2016NOVA.pdf)
> 
>    Hardening the NOVA File System (http://cseweb.ucsd.edu/~swanson/papers/TechReport2017HardenedNOVA.pdf)
> 
> Signed-off-by: Steven Swanson <swanson@cs.ucsd.edu>
> ---
>  Documentation/filesystems/00-INDEX |    2 
>  Documentation/filesystems/nova.txt |  771 ++++++++++++++++++++++++++++++++++++
>  MAINTAINERS                        |    8 
>  README.md                          |  173 ++++++++
>  4 files changed, 954 insertions(+)
>  create mode 100644 Documentation/filesystems/nova.txt
>  create mode 100644 README.md
> 

This file should not be in the top-level directory.
It would be OK in Documentation/filesystems, probably with a different
filename.

> diff --git a/README.md b/README.md
> new file mode 100644
> index 000000000000..4f778e99a79e
> --- /dev/null
> +++ b/README.md
> @@ -0,0 +1,173 @@
> +# NOVA: NOn-Volatile memory Accelerated log-structured file system
> +
> +NOVA's goal is to provide a high-performance, full-featured, production-ready
> +file system tailored for byte-addressable non-volatile memories (e.g., NVDIMMs
> +and Intel's soon-to-be-released 3DXpoint DIMMs).  It combines design elements
> +from many other file systems to provide a combination of high-performance,

                                                            high performance,

> +strong consistency guarantees, and comprehensive data protection.  NOVA support

                                                                           supports

> +DAX-style mmap and making DAX performs well is a first-order priority in NOVA's

                                 perform

> +design.  NOVA was developed by the [Non-Volatile Systems Laboratory][NVSL] in
> +the [Computer Science and Engineering Department][CSE] at the [University of
> +California, San Diego][UCSD].
> +
> +
> +NOVA is primarily a log-structured file system, but rather than maintain a
> +single global log for the entire file system, it maintains separate logs for
> +each file (inode).  NOVA breaks the logs into 4KB pages, they need not be

                                                     pages;

> +contiguous in memory.  The logs only contain metadata.
> +
> +File data pages reside outside the log, and log entries for write operations
> +point to data pages they modify.  File modification uses copy-on-write (COW) to
> +provide atomic file updates.
> +
> +For file operations that involve multiple inodes, NOVA use small, fixed-sized

                                                          uses

> +redo logs to atomically append log entries to the logs of the inodes involned.

                                                                        involved.

> +
> +This structure keeps logs small and make garbage collection very fast.  It also

                                       makes

> +enables enormous parallelism during recovery from an unclean unmount, since
> +threads can scan logs in parallel.
> +
> +NOVA replicates and checksums all metadata structures and protects file data
> +with RAID-4-style parity.  It supports checkpoints to facilitate backups.
> +
> +A more thorough discussion of NOVA's design is avaialable in these two papers:
> +
> +**NOVA: A Log-structured File system for Hybrid Volatile/Non-volatile Main Memories** 
> +[PDF](http://cseweb.ucsd.edu/~swanson/papers/FAST2016NOVA.pdf)<br>
> +*Jian Xu and Steven Swanson*<br>
> +Published in [FAST 2016][FAST2016]
> +
> +**Hardening the NOVA File System**
> +[PDF](http://cseweb.ucsd.edu/~swanson/papers/TechReport2017HardenedNOVA.pdf) <br>
> +UCSD-CSE Techreport CS2017-1018
> +*Jian Xu, Lu Zhang, Amirsaman Memaripour, Akshatha Gangadharaiah, Amit Borase, Tamires Brito Da Silva, Andy Rudoff, Steven Swanson*<br>
> +
> +Read on for further details about NOVA's overall design and its current status 
> +
> +### Compatibilty with Other File Systems
> +
> +NOVA aims to be compatible with other Linux file systems.  To help verify that it achieves this we run several test suites against NOVA each night.

Compatible in what ways?

> +
> +* The latest version of XFSTests. ([Current failures](https://github.com/NVSL/linux-nova/issues?q=is%3Aopen+is%3Aissue+label%3AXFSTests))
> +* The (Linux testing project)(https://linux-test-project.github.io/) file system tests.
> +* The (fstest POSIX test suite)[POSIXtest].
> +
> +Currently, nearly all of these tests pass for the `master` branch, and we have
> +run complex programs on NOVA.  There are, of course, many bugs left to fix.
> +
> +NOVA uses the standard PMEM kernel interfaces for accessing and managing
> +persistent memory.
> +
> +### Atomicity
> +
> +By default, NOVA makes all metadata and file data operations atomic.
> +
> +Strong atomicity guarantees make it easier to build reliable applications on
> +NOVA, and NOVA can provide these guarantees with sacrificing much performance

                                               without

> +because NVDIMMs support very fast random access.
> +
> +NOVA also supports "unsafe data" and "unsafe metadata" modes that
> +improve performance in some cases and allows for non-atomic updates of file

                                         allow

> +data and metadata, respectively.
> +
> +### Data Protection
> +
> +NOVA aims to protect data against both misdirected writes in the kernel (which
> +can easily "scribble" over the contents of an NVDIMM) as well as media errors.
> +
> +NOVA protects all of its metadata data structures with a combination of
> +replication and checksums.  It protects file data using RAID-5 style parity.

Above here it says RAID-4-style parity...???

> +
> +NOVA can detects data corruption by verifying checksums on each access and by

            detect

> +catching and handling machine check exceptions (MCEs) that arise when the
> +system's memory controller detects at uncorrectable media error.
> +
> +We use a fault injection tool that allows testing of these recovery mechanisms.
> +
> +To facilitate backups, NOVA can take snapshots of the current filesystem state
> +that can be mounted read-only while the current file system is mounted
> +read-write.
> +
> +The tech report list above describes the design of NOVA's data protection system in detail.
> +
> +### DAX Support
> +
> +Supporting DAX efficiently is a core feature of NOVA and one of the challenges
> +in designing NOVA is reconciling DAX support which aims to avoid file system
> +intervention when file data changes, and other features that require such
> +intervention.
> +
> +NOVA's philosophy with respect to DAX is that when a program uses DAX mmap to
> +to modify a file, the program must take full responsibility for that data and
> +NOVA must ensure that the memory will behave as expected.  At other times, the
> +file system provides protection.  This approach has several implications:
> +
> +1. Implementing `msync()` in user space works fine.
> +
> +2. While a file is mmap'd, it is not protected by NOVA's RAID-style parity
> +mechanism, because protecting it would be too expensive.  When the file is
> +unmapped and/or during file system recovery, protection is restored.
> +
> +3. The snapshot mechanism must be careful about the order in which in adds

                                                                      it

> +pages to the file's snapshot image.
> +
> +### Performance
> +
> +The research paper and technical report referenced above compare NOVA's
> +performance to other file systems.  In almost all cases, NOVA outperforms other
> +DAX-enabled file systems.  A notable exception is sub-page updates which incur
> +COW overheads for the entire page.
> +
> +The technical report also illustrates the trade-offs between our protection
> +mechanisms and performance.
> +
> +## Gaps, Missing Features, and Development Status
> +
> +Although NOVA is a fully-functional file system, there is still much work left
> +to be done.  In particular, (at least) the following items are currently missing:
> +
> +1.  There is no mkfs or fsk utility (`mount` takes `-o init` to create a NOVA file system)

                           fsck

> +2.  NOVA doesn't scrub data to prevent corruption from accumulating in infrequently accessed data.
> +3.  NOVA doesn't read bad block information on mount and attempt recovery of the effected data.
> +4.  NOVA only works on x86-64 kernels.
> +5.  NOVA does not currently support extended attributes or ACL.
> +6.  NOVA does not currently prevent writes to mounted snapshots.
> +7.  Using `write()` to modify pages that are mmap'd is not supported.
> +8.  NOVA deoesn't provide quota support.
> +9.  Moving NOVA file systems between machines with different numbers of CPUs does not work.
> +10. Remounting a NOVA file system with different mount options may fail.
> +
> +None of these are fundamental limitations of NOVA's design.  Additional bugs
> +and issues are here [here][https://github.com/NVSL/linux-nova/issues].
> +
> +NOVA is complete and robust enough to run a range of complex applications, but
> +it is not yet ready for production use.  Our current focus is on adding a few
> +missing features list above and finding/fixing bugs.

                    from the list above

> +
> +## Building and Using NOVA
> +
> +This repo contains a version of the Linux with NOVA included.  You should be

what repo?                      of Linux

> +able to build and install it just as you would the mainline Linux source.
> +
> +### Building NOVA
> +
> +To build NOVA, build the kernel with PMEM (`CONFIG_BLK_DEV_PMEM`), DAX (`CONFIG_FS_DAX`) and NOVA (`CONFIG_NOVA_FS`) support.  Install as usual.
> +
> +## Hacking and Contributing
> +
> +The NOVA source code is almost completely contains in the `fs/nova` directory.

                                             contained

> +The execptions are some small changes in the kernel's memory management system

       exceptions

> +to support checkpointing.
> +
> +`Documentation/filesystems/nova.txt` describes the internals of Nova in more detail.
> +
> +If you find bugs, please [report them](https://github.com/NVSL/linux-nova/issues).
> +
> +If you have other questions or suggestions you can contact the NOVA developers at [cse-nova-hackers@eng.ucsd.edu](mailto:cse-nova-hackers@eng.ucsd.edu).
> +
> +
> +[NVSL]: http://nvsl.ucsd.edu/ "http://nvsl.ucsd.edu"
> +[POSIXtest]: http://www.tuxera.com/community/posix-test-suite/ 
> +[FAST2016]: https://www.usenix.org/conference/fast16/technical-sessions
> +[CSE]: http://cs.ucsd.edu
> +[UCSD]: http://www.ucsd.edu
> \ No newline at end of file
> 


-- 
~Randy

[toc] | [prev] | [next] | [standalone]

#1704072 — Re: [RFC 01/16] NOVA: Documentation

From	Bart Van Assche <Bart.VanAssche@wdc.com>
Date	2017-08-04 17:20 +0200
Subject	Re: [RFC 01/16] NOVA: Documentation
Message-ID	<uaMym-f4-15@gated-at.bofh.it>
In reply to	#1702740

On Thu, 2017-08-03 at 00:48 -0700, Steven Swanson wrote:
> +### DAX Support
> +
> +Supporting DAX efficiently is a core feature of NOVA and one of the challenges
> +in designing NOVA is reconciling DAX support which aims to avoid file system
> +intervention when file data changes, and other features that require such
> +intervention.
> +
> +NOVA's philosophy with respect to DAX is that when a program uses DAX mmap to
> +to modify a file, the program must take full responsibility for that data and
> +NOVA must ensure that the memory will behave as expected.  At other times, the
> +file system provides protection.  This approach has several implications:
> +
> +1. Implementing `msync()` in user space works fine.
> +
> +2. While a file is mmap'd, it is not protected by NOVA's RAID-style parity
> +mechanism, because protecting it would be too expensive.  When the file is
> +unmapped and/or during file system recovery, protection is restored.
> +
> +3. The snapshot mechanism must be careful about the order in which in adds
> +pages to the file's snapshot image.

Hello Steven,

Thank you for having shared this very interesting work. After having read the
NOVA paper and patch 01/16 I have a question for you. Does the above mean that
COW is disabled for writable mmap-ed files? If so, what is the reason behind
this? Is there a fundamental issue that does not allow to implement COW for
writable mmap-ed files? Or have you perhaps tried to implement this and was the
performance not sufficient? Please note that I'm neither a filesystem nor a
persistent memory expert.

Thanks,

Bart.

[toc] | [prev] | [next] | [standalone]

#1704738 — Re: [RFC 01/16] NOVA: Documentation

From	Steven Swanson <steven.swanson@gmail.com>
Date	2017-08-06 05:30 +0200
Subject	Re: [RFC 01/16] NOVA: Documentation
Message-ID	<ubkql-5mb-7@gated-at.bofh.it>
In reply to	#1704072

There is nothing impossible COW for mapped files, but it is not a good match for the expected usage model for DAX.  

The idea is that programs can mmap files and the build interesting data structures in them, just like they do in DRAM.  This means lots of small updatEs, and that would be very slow if each of them required a COW.

The reason we use COW for normal accesses is to provide atomicity.  Programs will probably want doe form of atomicity for their mmaped data structures, but part of the DAX bargain is that programmer are responsible for this rather than the FS.

-steve

--
Composed on (and maybe dictated to) my phone.

> On Aug 4, 2017, at 08:09, Bart Van Assche <Bart.VanAssche@wdc.com> wrote:
> 
>> On Thu, 2017-08-03 at 00:48 -0700, Steven Swanson wrote:
>> +### DAX Support
>> +
>> +Supporting DAX efficiently is a core feature of NOVA and one of the challenges
>> +in designing NOVA is reconciling DAX support which aims to avoid file system
>> +intervention when file data changes, and other features that require such
>> +intervention.
>> +
>> +NOVA's philosophy with respect to DAX is that when a program uses DAX mmap to
>> +to modify a file, the program must take full responsibility for that data and
>> +NOVA must ensure that the memory will behave as expected.  At other times, the
>> +file system provides protection.  This approach has several implications:
>> +
>> +1. Implementing `msync()` in user space works fine.
>> +
>> +2. While a file is mmap'd, it is not protected by NOVA's RAID-style parity
>> +mechanism, because protecting it would be too expensive.  When the file is
>> +unmapped and/or during file system recovery, protection is restored.
>> +
>> +3. The snapshot mechanism must be careful about the order in which in adds
>> +pages to the file's snapshot image.
> 
> Hello Steven,
> 
> Thank you for having shared this very interesting work. After having read the
> NOVA paper and patch 01/16 I have a question for you. Does the above mean that
> COW is disabled for writable mmap-ed files? If so, what is the reason behind
> this? Is there a fundamental issue that does not allow to implement COW for
> writable mmap-ed files? Or have you perhaps tried to implement this and was the
> performance not sufficient? Please note that I'm neither a filesystem nor a
> persistent memory expert.
> 
> Thanks,
> 
> Bart.

[toc] | [prev] | [standalone]

csiph-web

[RFC 00/16] NOVA: a new file system for persistent memory

Contents

#1702740 — [RFC 00/16] NOVA: a new file system for persistent memory

#1702742 — [RFC 16/16] NOVA: Build infrastructure

#1702744 — [RFC 14/16] NOVA: Read-only pmem devices

#1702745 — [RFC 03/16] NOVA: PMEM allocation system

#1702746 — [RFC 06/16] NOVA: Lite-weight journaling for complex ops

#1703489 — Re: [RFC 01/16] NOVA: Documentation

#1704072 — Re: [RFC 01/16] NOVA: Documentation

#1704738 — Re: [RFC 01/16] NOVA: Documentation