\documentclass[obeyspaces,spaces,hyphens,dvipsnames]{beamer}
\usepackage[utf8]{inputenc}
\usepackage{minted}
\usepackage{hyperref}

\mode<presentation>
\usetheme{Bootlin}

\newcommand{\codehack}[1]{{\usebeamercolor[fg]{code} {\tt #1}}}

\title{MLC/TLC NAND support: (new?) challenges for the MTD/NAND subsystem}
\authors{Boris Brezillon}
\institute{Bootlin}

\setcounter{tocdepth}{2}

\begin{document}

\begin{frame}
  \begin{center}
    \huge
    MLC/TLC NAND support: (new?) challenges for the MTD/NAND subsystem
  \end{center}
\end{frame}

\begin{frame}{Boris Brezillon}
  \begin{itemize}
  \item Embedded Linux engineer and trainer at Bootlin
    \begin{itemize}
    \item Embedded Linux and Android {\bf development}: kernel and driver
      development, system integration, boot time and power
      consumption optimization, consulting, etc.
    \item Embedded Linux, Linux driver development, Android system and
      Yocto/OpenEmbedded {\bf training courses}, with materials freely
      available under a Creative Commons license.
    \item \url{http://bootlin.com}
    \end{itemize}
  \item Contributions
    \begin{itemize}
    \item {\bf Kernel support for the AT91 SoCs} ARM SoCs from Atmel
    \item {\bf Kernel support for the sunXi SoCs} ARM SoCs from Allwinner
    \end{itemize}
  \item Living in {\bf Toulouse}, south west of France
  \end{itemize}
\end{frame}

\AtBeginSection
{
}

\AtBeginSubsection
{
}

\begin{frame}{Agenda}
\tableofcontents
\end{frame}

\section{Context description}
\subsection{What is this talk about?}

\begin{frame}{Context: What is this talk about?}
  \begin{itemize}
  \item Explaining the constraints induced by MLC chips and comparing
	them to SLC chips
  \item Detailing the current Linux flash handling stack and pointing
        missing stuff to properly handle MLC chips
  \item Going through main MLC constraints and describing existing
        solutions or proposing new solutions to address them
  \item Be careful: most of this talk is describing hypothetical changes
  \end{itemize}
\end{frame}

\subsection{NAND flash technology}

\begin{frame}{Context: Short description of the NAND technology}
  \begin{itemize}
  \item Encode bits with Voltage levels
  \item Start with all bits set to 1
  \item Programming implies changing some bits from 1 to 0
  \item Restoring bits to 1 is done via the ERASE operation
  \item Programming and erasing is not done on a per bit or per byte
        basis
  \item Organization
    \begin{itemize}
    \item Page: minimum unit for PROGRAM operation
    \item Block: minimum unit for ERASE operation
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Context: NAND flash organization}
  \begin{center}
    \includegraphics[scale=0.5]{nand-organization.jpg}
  \end{center}
\end{frame}

\begin{frame}{Context: What are MLC NAND chips?}
  \begin{itemize}
  \item Standard NAND chips are SLC (Single-Level Cells) chips
  \item MLC stands for Multi-Level Cells
    \begin{itemize}
    \item Multi is kind of misleading here, we're talking about
          4 level cells: b00, b01, b10, b11
    \item One cell contains 2 bits
    \end{itemize}
  \item Higher data density than SLC chips, but also less reliable
  \item Requires more precautions when accessing the chip (true for both
        read and write accesses)
  \end{itemize}
\end{frame}

\begin{frame}{Context: MLC vs SLC Cell}
  \begin{center}
    \includegraphics[scale=0.3]{slc-mlc-cell.pdf}
  \end{center}
\end{frame}

\subsection{Flash memory handling in Linux}

\begin{frame}{Context: flash related layers in the Linux kernel}
  \begin{center}
    \includegraphics[scale=0.2]{linux-flash-stack.pdf}
  \end{center}
\end{frame}

\begin{frame}{Context: MTD}
  \begin{itemize}
    \item Provide an abstraction layer to expose all kind of memory
          devices (RAM, ROM, NOR, NAND, DATAFLASH, ...)
    \item Does not care about how memory device is accessed: that's
          the responsibility of each MTD driver
    \item Expose methods to access the memory device (read/write/erase)
    \item Expose memory layout information
    \begin{itemize}
      \item \code{erasesize}: minimum erase size unit
      \item \code{writesize}: minimum write size unit
      \item \code{oobsize}: extra size to store metadata or ECC data
      \item \code{size}: device size
      \item \code{flags}: information about device type and capabilities
    \end{itemize}
    \item MTD drivers should fill layout information and access methods
          in \code{mtd_info} and then register the device
  \end{itemize}
\end{frame}

\begin{frame}{Context: NAND framework}
  \begin{itemize}
    \item Provide an abstraction layer for raw NAND devices
    \item Take care of registering NAND chips to the MTD layer
    \item Expose an interface for NAND controllers to register their
          NAND chips: \code{struct nand_chip}
    \item Implement the glue between NAND and MTD logics
    \item Provide interfaces for other NAND related stuff:
    \begin{itemize}
      \item ECC controller: \code{struct nand_ecc_ctrl}
      \item Bad Block handling: \code{struct nand_bbt_descr}
      \item etc
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Context: UBI}
  \begin{itemize}
  \item Stands for Unsorted Block Images
  \item Deals with wear leveling
    \begin{itemize}
    \item Distributes erase block wear over the whole flash
    \item Takes care of moving data from unreliable blocks to reliable ones
    \item Takes care of marking bad blocks (after torturing them)
    \end{itemize}
  \item Provides a volume abstraction layer (similar to LVM for block
        devices)
    \begin{itemize}
    \item Volumes are not composed of physically contiguous blocks
    \item You can't attach specific erase blocks to volumes
    \item Can be dynamically created, removed, resized or renamed
    \end{itemize}
  \item Makes use of the MTD abstraction to access memory devices
  \end{itemize}
\end{frame}

\begin{frame}{Context: UBI}
  \begin{center}
    \includegraphics[scale=0.3]{ubi.pdf}
  \end{center}
\end{frame}

\begin{frame}{context: ubi metadata}
  \begin{center}
    \includegraphics[scale=0.3]{ubi-leb.pdf}
  \end{center}
\end{frame}

\begin{frame}{Context: UBIFS}
  \begin{itemize}
  \item Stands for UBI File System
  \item Relies on the UBI layer for the wear leveling part
  \item Journaling file system created to address JFFS2 scalability
        problems
  \item I won't detail the UBIFS architecture here:
    \begin{itemize}
    \item It would take too long
    \item I'm not qualified enough to describe it
    \end{itemize}
  \end{itemize}
\end{frame}

\section{MLC Constraints}

\begin{frame}{MLC Constraints}
  \begin{itemize}
  \item Paired pages require care when programming a page
  \item Voltage thresholds delimiting each level might change with wear
  \item More prone to bit-flips
  \item Sensitive to repeated data patterns
  \end{itemize}
\end{frame}

\subsection{Paired pages}

\begin{frame}{MLC Constraints: paired pages}
  \begin{itemize}
  \item MLCs embed 2 bits in each cell
  \item Why are NAND vendors so mean to us poor software developers?
    \begin{itemize}
    \item One bit assigned to one page and the other one to another page
    \item TLC cells embed 3 bits: same problem except pages are paired by 3
    \item Changing the cell level is a risky operation, which, if
          interrupted, can lead to undefined voltage level in this cell
    \item Since the same cell is shared by several pages, programming
          one page might corrupt the page(s) it is paired with
    \item Each NAND vendor has its own scheme for page pairing, this
          forces us to provide a vendor specific (if not chip specific)
	  function to find out which pages are paired
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{MLC Constraints: paired pages}
  \begin{center}
    \includegraphics[scale=0.2]{paired-pages.pdf}
  \end{center}
\end{frame}

\subsection{Unpredictable voltage level}

\begin{frame}{MLC Constraints: adapting voltage thresholds}
  \begin{itemize}
  \item The voltage level stored when programming a cell might change with
        wear
  \item Becomes problematic when the level crosses the voltage threshold
        used by the internal logic to determine values stored in cells
  \item Can be fixed by ECCs if the number of impacted cells stays low
  \item Requires a solution when the number of impacted cells is too
        important
  \item Solution: move voltage thresholds to deal with this situation
  \end{itemize}
\end{frame}

\begin{frame}{MLC Constraints: adapting voltage threshold}
  \begin{center}
    \includegraphics[scale=0.2]{adapt-vt.pdf}
  \end{center}
\end{frame}

\subsection{Data retention problems}

\begin{frame}{MLC Constraints: data retention}
  \begin{itemize}
  \item NAND cells are not indefinitely maintaining their state
  \item The external environment (like temperature) can reduce data
        retention
  \item The first source of data retention problems is read/write
        disturbance
  \end{itemize}
\end{frame}

\begin{frame}{MLC Constraints: read and program disturbance}
  \begin{itemize}
  \item This problem is seen on all NAND chips (including SLC) but
        happens more frequently on MLC/TLC NANDs
  \item Read disturbance:
    \begin{itemize}
    \item Is caused by a read command
    \item Might impact the page currently being read or other pages in the
          same block
    \end{itemize}
  \item Program disturbance:
    \begin{itemize}
    \item Is caused by a program command
    \item Might impact other pages in the same block
    \end{itemize}
  \item The most problematic disturbance is the one appearing on other pages
        than the one being accessed
  \item Requires scanning all pages (or at least those rarely read) in
        the background to detect those where the number of bit-flips
	exceeds the bit-flips threshold
  \end{itemize}
\end{frame}

\begin{frame}{MLC Constraints: read and program disturbance}
  \begin{center}
    \includegraphics[scale=0.7]{read-write-disturb.png}
  \end{center}
\end{frame}

\begin{frame}{MLC Constraints: avoiding repeated data patterns}
  \begin{itemize}
  \item Some MLC chips are sensitive to repeated data patterns
  \item Scramble data to avoid writing such patterns
  \item Require a descrambling phase when reading data from the NAND
  \end{itemize}
\end{frame}

\subsection{Power-cut related problems}

\begin{frame}[fragile]{MLC Constraints: unstable bits}
  \begin{itemize}
  \item Not an MLC problem per se (also happens on SLC chips)
  \item Interrupted PROGRAM/ERASE operations might lead to unstable bits
    \begin{itemize}
    \item Cells can store the correct value for some time
    \item Suddenly return erroneous values
    \end{itemize}
  \item Fully described here:
        \url{http://www.linux-mtd.infradead.org/doc/ubifs.html#L_unstable_bits}
  \end{itemize}
\end{frame}

\section{Proposed Solutions}
\subsection{Paired pages}

\begin{frame}{Paired pages handling: First proposal}
  \begin{itemize}
  \item Only write on one of the paired pages
  \item Pros:
    \begin{itemize}
    \item Simple to implement
    \item Can be handle at the NAND layer only
    \item Some chips provide an SLC mode (even simpler to implement)
    \end{itemize}
  \item Cons:
    \begin{itemize}
    \item You loose half the NAND capacity (even more in case of TLC chips)
    \end{itemize}
  \item Implementation details:
    \begin{itemize}
    \item Declare the chip as having half (or one-third in case of TLC) the
          effective size
    \item Use the SLC mode if it exists
    \item Or only write on the pages that are assigned the first bit of
          each cell
    \item In any case hide the logic to the upper layers
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Paired pages handling: Second proposal}
  \begin{itemize}
  \item Differentiate 'safe' and 'unsafe' LEBs
  \item Safe LEBs: only use one bit of each cell
    \begin{itemize}
    \item UBI deals with paired pages and exposes a linear view to users
    \item Users have to take the size of safe LEBs into account
    \item Put safe LEBs in a pool the first time they are unmapped
    \item Use pages from the 2nd group when mapped again
    \item Erase them the second time they are unmapped
    \end{itemize}
  \item Unsafe LEBs expose all LEB capacity
    \begin{itemize}
    \item Users have to deal with paired pages by themselves
    \item Or accept to loose some data
    \item Or atomically program/update LEBs
    \end{itemize}
  \end{itemize}
\end{frame}
	
\begin{frame}{Paired pages handling: Second proposal}
  \begin{itemize}
  \item Pros:
    \begin{itemize}
    \item Reduce wear (safe LEBs are reused twice before being erased)
    \item Provides fine grained control over which operations are sensible
          and which one are not
    \end{itemize}
  \item Cons:
    \begin{itemize}
    \item Still can't use the whole flash capacity
    \item More complicated to implement than 1st proposal
    \item Impacts all layers up to UBIFS
    \end{itemize}
  \item Usage:
    \begin{itemize}
    \item Safe LEBs: file system journal where each entry should be
          consistent
    \item Unsafe LEBs: atomic LEB update where a CRC is used to
          ensure whole LEB consistency
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Paired pages handling: Second proposal}
  \begin{itemize}
  \item Implementation details:
    \begin{itemize}
    \item NAND and MTD layers are exposing paired pages information
    \item UBI should never use pages paired with the EC and VID headers
    \item UBI provides a way to declare safe and unsafe LEBs
      \begin{itemize}
      \item Safe LEBs: only using half (or one-third) of the block capacity
            so that all writes are safe
      \item Safe LEB marker in \code{ubi_vid_hdr}
      \end{itemize}
    \item UBIFS makes use of the unsafe/safe LEB capabilities depending on
          each operation and the associated required reliability (log update,
          garbage collection, etc)
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]{Paired pages handling: Third proposal}
  \begin{itemize}
  \item Yet to be proposed ;-)
  \item Give more control to UBIFS?
  \item Solution proposed here:
	\url{http://www.linux-mtd.infradead.org/doc/ubifs.html#L_ubifs_mlc}
    \begin{itemize}
    \item Let UBIFS decide when a LEB should be safe (pages paired to the
          already programmed ones should not be touched)
  \item Should be done when committing changes (FS sync)?
    \end{itemize}
  \item My knowledge of the UBIFS infrastructure is quite limited
  \item Should be discussed with the UBIFS Maintainer: Artem Bityutskiy
  \item UBI should hide pages paired with VID and EC headers
  \item Pros:
    \begin{itemize}
    \item Better use of the overall NAND capacity?
    \end{itemize}
  \item Cons:
    \begin{itemize}
    \item Far more complicated to implement: UBIFS has to directly deal
          with paired pages
    \item Only UBIFS will benefit from the paired pages handling (but
          are there other dynamic volume users anyway?)
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]{Paired pages handling: Third proposal}
  \begin{center}
    \includegraphics[scale=0.3]{ubi-leb-mlc.pdf}
  \end{center}
\end{frame}

\begin{frame}[fragile]{Paired pages handling: Third proposal}
  \begin{center}
    \includegraphics[scale=0.2]{ubi-ubifs-leb-mlc.pdf}
  \end{center}
\end{frame}

\subsection{Unpredictable voltage level}

\begin{frame}{Handling unpredictable voltage threshold}
  \begin{itemize}
  \item NAND vendors provide a way to tweak the cell level threshold
        (read-retry), but ...
    \begin{itemize}
    \item There is no standard way to do that
    \item Each vendor implements it differently
    \item This might differ even with NAND chips from the same
          manufacturer
    \item While mandatory, this feature is not (or poorly) documented
    \end{itemize}
  \item Detecting the appropriate threshold is not that simple and this
        value is only valid for a given block
  \item It depends on block wear, but there is no paper describing how
        we should choose it (depends on the number of erase/program
        cycles, but how?)
  \item Iterating over modes implies a performance penalty, since the
        page has to be read several times
  \end{itemize}
\end{frame}

\begin{frame}{Handling unpredictable voltage threshold}
  \begin{itemize}
  \item Micron's implementation is already supported in mainline
  \item But, existing core code ...
    \begin{itemize}
    \item stops searching for the best read-retry mode as soon as a
          page is successfully read (even if the number of bit-flips
	  exceed the \code{bitflips_threshold} value)
    \item does not save the last valid read-retry mode: performance
          penalty at each read
    \end{itemize}
  \item What's missing?
    \begin{itemize}
    \item A way for vendor specific code to be registered (assign the
          \code{setup_read_retry} callback)
    \item Some fixes to the existing implementation to find the best
          read-retry mode
    \item Optional: store best read-retry mode in memory
    \item Optional: guess best read-retry mode from the erase counter
    \end{itemize}
  \end{itemize}
\end{frame}

\subsection{Data retention problems}

\begin{frame}{Preventing uncorrectable bit-flips: First Proposal}
  \begin{itemize}
  \item Regularly read all pages to detect pages/blocks where the bit-flips
        threshold is raised
  \item Problem: a page read might generate read disturbance and corrupt
        other pages in the same block
  \item Better read a full block
  \item Solution proposed (and developed) by Richard Weinberger
    \begin{itemize}
    \item At UBI level
    \item Creation of a new user-space interface (sysfs) to trigger a full
          volume scan
    \item Scan done in background (in the UBI thread, or an independent
          one)
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Preventing uncorrectable bit-flips: First Proposal}
  \begin{itemize}
  \item Pros:
    \begin{itemize}
    \item Rather simple implementation
    \item Pretty easy to use
    \item Let user-space decide when the scan is necessary
    \end{itemize}
  \item Cons:
    \begin{itemize}
    \item Force user-space to store information on the last scan and logic
          about when to scan next time
    \item Launching a full scan might be ineffective in some cases (some
          blocks are read quite often and do not need to be scanned)
    \item Performance penalty when reading/programming while a scan is in
          progress (the operation might have to wait for the page read to
	  finish)
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Preventing uncorrectable bit-flips: Second Proposal}
  \begin{itemize}
  \item The UBI layer can store useful information/statistics about
    \begin{itemize}
    \item read and write accesses
    \item number of corrected bit-flips
    \end{itemize}
  \item UBI can use these statistics to decide when to read
        each page/block
  \item Pros:
    \begin{itemize}
    \item All the complexity is hidden from user-space
    \item More efficient in term of useful page/block reads
    \end{itemize}
  \item Cons:
    \begin{itemize}
    \item Far more complicated to implement
    \item Increases memory footprint
    \item Still requires one full scan at boot (to restore the database)
    \item Performance penalty when reading/programming while a bit-flip
          detection is in progress
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]{Avoiding repeated data patterns: data scramblers}
  \begin{itemize}
  \item Should be handled in the NAND layer
  \item Better use a hardware scrambler, but a software implementation is
        possible
  \item Same approach as for ECC handling
  \end{itemize}
\end{frame}

\begin{frame}[fragile]{Avoiding repeated data patterns: data scramblers}
  \begin{center}
    \includegraphics[scale=0.15]{scrambler.pdf}
  \end{center}
\end{frame}

\begin{frame}{Data scrambler: implementation details}
  \begin{itemize}
  \item Data scrambling can be hidden in the NAND controller driver
        implementation, but
    \begin{itemize}
    \item You'll have to use your own read/write implementations
    \item If we ever decide to add a mode to disable the scrambler when
          accessing the NAND, you'll have to implement more functions
    \item Factorizing common operations in default helper functions is
          always a good thing
    \item Trying to match a common model always makes you think twice
          before coding dirty hacks ;-)
    \end{itemize}
  \item The proposed interface is trying to be as much generic as
        possible, but was designed with 2 implementations in mind
    \begin{itemize}
    \item The sunxi NAND controller one
    \item A software based implementation using the LFSR algorithm
    \end{itemize}
  \item Please let me know if your scrambler does not fit in the model
        proposed here
  \end{itemize}
\end{frame}

\begin{frame}[fragile]{Data scrambler: implementation details}
  \tiny
  \begin{block}{}
  \begin{minted}{c}
enum nand_scrambler_action {
  NAND_SCRAMBLER_DISABLE,
  NAND_SCRAMBLER_READ,
  NAND_SCRAMBLER_WRITE,
};

struct nand_scrambler_ops {
  int (*config)(struct mtd_info *mtd, int page, int column,
                enum nand_scrambler_action action);
  void (*write_buf)(struct mtd_info *mtd, const uint8_t *buf, int len);
  void (*read_buf)(struct mtd_info *mtd, uint8_t *buf, int len);
};

struct nand_scrambler_layout {
  int nranges;
  struct nand_rndfree ranges[0];
};

struct nand_scrambler_ctrl {
  struct nand_scrambler_layout *layout;
  struct nand_scrambler_ops *ops;
};

[...]

struct nand_chip {
[...]
  struct nand_scrambler_ctrl *scrambler;
[...]
};

  \end{minted}
 \end{block}
 \normalsize
\end{frame}

\begin{frame}{Data scrambler: implementation details}
  \begin{itemize}
  \item Scrambler layout (\code{struct nand_scrambler_layout})
    \begin{itemize}
    \item Describes area that should not be scrambled
    \item Particularly useful for Bad Block Markers
    \item Not mandatory but highly recommended if feasible
    \end{itemize}
  \item Scrambler operations (\code{struct nand_scrambler_ops})
    \begin{itemize}
    \item \code{config}
      \begin{itemize}
      \item configure the scrambler block for a \code{READ} or
	    \code{WRITE} operation, or disable it
      \item \code{page} and \code{column} arguments are necessary to setup
             the appropriate key or seed value in the scrambler block
      \end{itemize}
    \item \code{read_buf} and \code{write_buf}
      \begin{itemize}
      \item wrapper functions responsible for enabling the scrambler block
            before calling NAND controller \code{read_buf} or
            \code{write_buf} and disabling it after the operation is done
      \item Not mandatory if you do not rely on default helpers
      \end{itemize}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Data scrambler: implementation details}
  \begin{itemize}
  \item Proposed an implementation a year ago:
        \url{https://lkml.org/lkml/2014/4/30/721}
  \item Proof of concept available here:
        \url{https://github.com/bbrezillon/linux-sunxi/tree/sunxi-nand-next}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]{Unstable bits handling}
  \begin{itemize}
  \item Part of a solution described here:
        \url{http://www.linux-mtd.infradead.org/doc/ubifs.html#L_unstable_bits}
  \item That's a topic I haven't thought about yet
  \item Any proposal is welcome
  \end{itemize}
\end{frame}

\section{Conclusion}

\begin{frame}{We need NAND chip vendors help}
  \begin{itemize}
  \item Most solutions proposed in this talk are based on experiments
        and instead of facts or statistics
  \item NAND chip vendors could help us by
    \begin{itemize}
    \item Documenting undocumented or (poorly documented) parts
      \begin{itemize}
      \item How to change voltage thresholds
      \item Impacts of repeated data patterns
      \item Impacts of power-cut failures on data reliability (unstable
            bits issue)
      \end{itemize}
    \item Providing statistics on
      \begin{itemize}
      \item Cells wear evolution
      \item Impacts of wear on voltage level
      \item Impacts of read/write disturbance (to determine how often
            a block should be scanned)
      \end{itemize}
    \item Proposing new approaches to deal with MLC constraints
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{What's next?}
  \begin{itemize}
  \item Most of the solutions proposed here are either untested ones or just
        proofs of concept
    \begin{itemize}
    \item Need to discuss them with MTD, UBI and UBIFS maintainers
    \item Provide MLC chips constraints emulation in order to test UBI/UBIFS
          MLC related stuff with checkfs
    \item Provide implementations and iterate till they are accepted
    \end{itemize}
  \item Doing that on my spare time: don't expect to see things coming
        quickly
  \item Any kind of help is welcome: new ideas, implementations, tests,
        reviews, ...
  \end{itemize}
\end{frame}

\begin{frame}
  \begin{center}
  \Huge
  Questions?\\
  \vspace{1.5cm}
  \huge
  Boris Brezillon\\
  \large
  \vspace{0.5cm}
  \code{boris.brezillon@bootlin.com}
  \vspace{0.5cm}
  \newline Slides under CC-BY-SA 3.0\\
  \scriptsize
  \url{http://bootlin.com/pub/conferences/2015/elc/brezillon-mlc-nand/}
  \end{center}
\end{frame}

\end{document}
