\documentclass[aspectratio=43,obeyspaces,spaces,hyphens,dvipsnames]{beamer}
\usepackage[utf8x]{inputenc}
\usepackage{lmodern}% http://ctan.org/pkg/lm
\usepackage{minted}
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{pgfplots}
\usepackage{tikz}
\usepackage[normalem]{ulem}
\usepackage{textcomp}
\usepackage{media9}

\mode<presentation>
\usetheme{Bootlin}

\def\signed #1{{\leavevmode\unskip\nobreak\hfil\penalty50\hskip2em
  \hbox{}\nobreak\hfil(#1)
  \parfillskip=0pt \finalhyphendemerits=0 \endgraf}}

\newsavebox\mybox
\newenvironment{aquote}[1]
  {\savebox\mybox{#1}\begin{quotation}}
  {\signed{\usebox\mybox}\end{quotation}}

\title{ECC engines}
\conference{Embedded Linux Conference Europe, October 2020}
\authors{Miquèl Raynal}
\email{\tiny miquel@bootlin.com}
\institute{Bootlin}
\slidesurl{https://bootlin.com/pub/conferences/2020/elce/raynal-ecc-engines}

\begin{document}

\addtocontents{toc}{\protect\setcounter{tocdepth}{-1}}
\section{ECC engines}
\addtocontents{toc}{\protect\setcounter{tocdepth}{2}}

\begin{frame}{Miquèl Raynal}
  \begin{itemize}
  \item Embedded Linux engineer at Bootlin
    \begin{itemize}
    \item Embedded Linux {\bf expertise}
    \item {\bf Development}, consulting and training
    \item Strong open-source focus
    \item \url{https://bootlin.com}
    \end{itemize}
  \item Contributions
    \begin{itemize}
    \item {\bf Maintainer of the NAND subsystem}
    \item {\bf Co-maintainer of the MTD subsystem}
    \item {\bf Kernel support for various ARM SoCs}
    \end{itemize}
  \item Living in {\bf Toulouse}, south west of France
  \end{itemize}
\end{frame}

\section{A bit of context}

\begin{frame}{Error Correcting Codes}
  \begin{itemize}
  \item You want to share an information
  \item The communication medium is subject to disturbances
  \item What do you do?
  \item In a crowd you would either...
    \begin{itemize}
    \item Speak louder?
      \begin{itemize}
      \item Uses more power in the case of telecommunications
      \item Would need to decrease storage media density
      \end{itemize}
    \item Repeat yourself?
      \begin{itemize}
      \item Adds redundancy
      \item Introduces more latency
      \end{itemize}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Redundancy}
  \begin{itemize}
  \item Provide the original data to an algorithm
  \item Retrieve the (transformed) data, including check/redundancy information
    \begin{itemize}
    \item We usually prefer to transfer readable data, so the orginal
      data prepends within the code
    \item Longer than the data you actually want to transmit
    \end{itemize}
  \item The point of this code being, the receiver must be able to
    \begin{itemize}
    \item Detect one or more errors
    \item Eventually correct one or more errors
    \end{itemize}
  \item Not only reserved to communications
  \item Already widely used with storage media as well!
  \end{itemize}
\end{frame}

\begin{frame}{ECCs in communications}
  \begin{itemize}
  \item Case of radio audio communications
    \begin{itemize}
    \item NATO phonetic alphabet
      \begin{itemize}
      \item \code{Lima}
      \item \code{India}
      \item \code{November}
      \item \code{Uniform}
      \item \code{X-ray}
      \end{itemize}
    \end{itemize}
  \item Probably the most widely known ECC
  \item All words are very different to the ears
  \item Mathematiciens call that the distance
  \end{itemize}
\end{frame}

\begin{frame}{Binary informations}
  \begin{itemize}
  \item Let's take the number \code{0xA}, \code{b1010}
  \item A single disturbance could produce \code{b0010}
  \item How do you know that \code{0x2} is not the right number?
  \item Any change leads to a (in appearance) valid number
  \end{itemize}
\end{frame}

\begin{frame}{Simplest algorithms}
  \begin{itemize}
    \onslide<1-> \item Repeatiting may be a solution
    \begin{itemize}
    \item Send twice the same bit
      \begin{itemize}
      \item \code{b1010} becomes \code{b11001100}
      \item Detection of a single bit error
      \item No correction
      \end{itemize}
      \onslide<2-> \item Send three times the same bit
      \begin{itemize}
      \item \code{b1010} becomes \code{b111000111000}
      \item Detection of a single bit error
      \item Automatic correction by majority vote
      \item Very costly!
      \end{itemize}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{ECCs are everywhere}
  \begin{itemize}
  \item Parity bits in UART communications
    \begin{itemize}
    \item A byte may be composed of
      \begin{itemize}
      \item 7 bits of data
      \item 1 parity bit
      \end{itemize}
    \item The parity bit is selected to match either an even or an odd parity
      \begin{itemize}
      \item Example: \code{0x4A} (\code{b1001010}) has 3 binary \code{1}
      \item If we look for an even parity, we will then append a \code{1}
      \item If the message has an odd parity it is assumed to be corrupted
      \end{itemize}
    \end{itemize}
  \item 1-bit error detection is achieved with a 15\% overhead
  \item Much less than the 100\% overhead of the ``repeating'' algorithm!
  \end{itemize}
\end{frame}

\begin{frame}{ECC for storage}
  \begin{columns}
    \column{0.5\textwidth}
    \begin{itemize}
    \item RAM chips embed simple hardware ECC algorithms
      \begin{itemize}
      \item Old technologies used parity bits
      \item Then 1-bit correction algorithms
      \item Silicon vendors tend to move towards more complex on-the-fly
        corrections
      \end{itemize}
    \end{itemize}
    \center\includegraphics[height=0.2\textwidth]{ram.jpg}
    \null\vfill
        {\fontsize{5}{6}\selectfont Elixir 512MB DDR RAM
          M2U51264DS8HC3G-5T for desktop computers \label{ram}}
    \column{0.5\textwidth}
    \begin{itemize}
    \item Compact Disks
      \begin{itemize}
      \item Are intrinsically less prone to bit errors
      \item Errors come from external scratches or dust
      \item Unlike RAMs, errors happen in batch
      \item Philips norm covers the loss of up to 4096 consecutive bits
        (this is a 1 millimeter thick scratch!)
      \end{itemize}
    \end{itemize}
    \center\includegraphics[height=0.2\textwidth]{cd.jpg}
    \null\vfill
        {\fontsize{5}{6}\selectfont Flat view of a CD-R \label{cd}}
  \end{columns}
\end{frame}

\section{NAND and bitflips, a love story}

\begin{frame}{NAND technology 101}
    \centering
    \large
    \onslide<1->It's cheap\\
    \vspace{0.5cm}
    \LARGE
    \onslide<2->It's intrinsically unstable\\
    \vspace{0.5cm}
    \Huge
    \onslide<3->ECC is mandatory\\
\end{frame}

\begin{frame}{NAND technology 102}
  \begin{itemize}
  \item NAND devices are made of a huge amount of tiny NAND cells
  \item A cell is like a bucket with a small hole
  \item An empty bucket is seen as a binary \code{1}
  \item A filled bucket is seen as a binary \code{0}
  \item Multiple reasons can cause a NAND cell to not return the right data:
    \begin{itemize}
    \item Time
      \begin{itemize}
      \item[$\rightarrow$] remember, there is a hole in the bucket!
      \end{itemize}
      \item Intensive use (too many erase cycles) damages the cell
      \begin{itemize}
      \item[$\rightarrow$] the hole gets bigger!
      \end{itemize}
      \item Read disturbances
      \begin{itemize}
      \item[$\rightarrow$] looking into a bucket shakes the other one
      \end{itemize}
      \item Level sensing
      \begin{itemize}
      \item[$\rightarrow$] when do we consider the bucket full/empty?
      \end{itemize}
    \end{itemize}
  \item A more scientific explanation of the NAND technology internals
    available here:
    {\em
    \href{https://www.youtube.com/watch?v=3PROYAbwCmY}{conference} /
    \href{https://elinux.org/images/3/3d/Raynal-understand-and-drive-your-nand.pdf}{slides}}
  \end{itemize}
\end{frame}

\begin{frame}{NAND technology 103}
  \begin{itemize}
  \item Particularly true with newer chips
    \begin{itemize}
    \item[$\rightarrow$] NAND cells are smaller
    \item[$\rightarrow$] Density rises
    \item[$\rightarrow$] The probability of bit error as well (due to
      the inherent disturbances)
    \end{itemize}
  \item We need reliable corrections that suit the chip requirements
    \vfill
  \item Stronger corrections involve:
    \begin{itemize}
    \item More processing power
    \item Additional delays
    \item A bigger overhead
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{ECC engine mission: write path}
  \begin{itemize}
  \item The host controller provides to the ECC engine a chunk of data
  \item The ECC engine processes the chunk and produces ECC bytes
    \begin{itemize}
    \item Usually the processed data is kept identical
    \item The ECC bytes are stored in the out-of-band area
    \end{itemize}
  \end{itemize}
  \begin{center}
    \center\includegraphics[width=0.8\textwidth]{ecc-write-path.pdf}
  \end{center}
  \begin{itemize}
  \item Repeat this operation for all the data chunks contained in the page
  \item Write the entire page to the storage medium
  \end{itemize}
\end{frame}

\begin{frame}{ECC engine mission: read path}
  \begin{itemize}
  \item Raw data and ECC bytes (possibly corrupted) are retrieved
  \end{itemize}
  \begin{center}
    \center\includegraphics[width=0.8\textwidth]{ecc-read-path.pdf}
  \end{center}
  \begin{itemize}
  \item The ECC engine processes all the available data, chunk after chunk, to:
    \begin{itemize}
    \item Detects bit errors
    \item Eventually corrects them
    \end{itemize}
  \item Return the original data to the caller and report a status
  \end{itemize}
\end{frame}

\begin{frame}{Hamming algorithm}
  \begin{columns}
    \column{0.8\textwidth}
    \begin{itemize}
    \item Very popular with older/stronger Single Level Cell (SLC) chips
    \item Efficiently corrects up to 1 bit error per chunk
    \item Detects up to 2 bit errors per chunk
    \item Invented in 1950 to cover defects from punched card readers!
    \item Most of the existing raw NAND controllers embed an hardware
      Hamming ECC engine
    \item Linux provides a software Hamming ECC engine
    \end{itemize}
    \column{0.2\textwidth}
    \begin{center}
      \center\includegraphics[width=\textwidth]{hamming.jpg}
      \null\vfill
      {\fontsize{5}{6}\selectfont Historic portrait of Richard
        W. Hamming \label{hamming}}
    \end{center}
  \end{columns}
\end{frame}

\begin{frame}{BCH algorithm}
  \begin{itemize}
  \item Invented independently in 1959 by Alexis Hocquenghem and 1960 by
    Raj Bose and D. K. Ray-Chaudhuri
  \item Very powerful and flexible: fits almost any kind of (NAND)
    requirement
    \begin{itemize}
    \item Adapts to almost any strength over any chunk size
    \item Carries the data unaltered
    \item Very good ratio overhead$/$correction capabilities
    \item Only limited by the available out-of-band area
    \end{itemize}
  \item Read path almost 10 times more complex than the write path
    \begin{itemize}
    \item[$\Rightarrow$] Better if offloaded to hardware
    \end{itemize}
  \item But still, BCH decoding is considered as rather inexpensive
    compared to its correcting capabilities
  \item Leverages polynomial algebra over binary data
  \item Reverse engineering session of a hardware BCH ECC engine:\\
    \url{https://bootlin.com/blog/supporting-a-misbehaving-nand-ecc-engine/}
  \item Linux also provides a customizable software BCH ECC engine
  \end{itemize}
\end{frame}

\begin{frame}{Reed-Solomon algorithm}
  \begin{itemize}
  \item Introduced in 1960 by Irving S. Reed and Gustave Solomon
  \item Considers symbols instead of bits
    \begin{itemize}
    \item Many bit-errors in a single symbol appear as a single failure
    \item Makes RS codes well suited to fight against burst errors
    \end{itemize}
  \item Treats ``lack of data'' and ``bit failures'' differently
    \begin{itemize}
    \item Given $t$ the number of check symbols, it can correct:
      \begin{itemize}
        \item up to $t$ missing symbols (provided that the algorithm know their
          position) {\bf or}
        \item up to $t / 2$ unlocated errors otherwise
      \end{itemize}
    \end{itemize}
  \item A bit less common than BCH codes in the NAND world
  \item Base of the CIRC ECC algorithm used for CD's (Cross Interleaved
    Reed-Solomon Code)
  \end{itemize}
\end{frame}

\section{ECC engines support}

\begin{frame}{The ECC engine in the raw NAND world}
  \begin{itemize}
  \item How people usually see their hardware:
  \end{itemize}
  \begin{center}
    \center\includegraphics[width=0.8\textwidth]{rawnand-wrong.pdf}
  \end{center}
\end{frame}

\begin{frame}{Raw NAND real situation}
  \begin{itemize}
  \item The real situation:
  \end{itemize}
  \begin{center}
    \center\includegraphics[width=0.8\textwidth]{rawnand-true.pdf}
  \end{center}
\end{frame}

\begin{frame}{Current situation for parallel NANDs}
  \begin{itemize}
  \item Historically, raw NAND device, NAND bus, NAND controller and ECC
    engine were treated by Linux as a single entity
  \item Recently, we separated the NAND device and the NAND controller
    representations
  \item The raw NAND controller and its embedded hardware ECC engine are
    still mixed in practice
  \item We recently pushed in favor of the distinction between:
    \begin{itemize}
    \item \ksym{struct nand_chip *chip}
    \item \ksym{struct nand_controller *controller}
    \item \ksym{stuct nand_ecc_ctrl *ecc}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Current situation for serial NANDs}
  \begin{itemize}
  \item Only ``on-die'' ECC engines:
  \end{itemize}
  \begin{center}
    \center\includegraphics[width=0.8\textwidth]{spi-on-die.pdf}
  \end{center}
\end{frame}

\begin{frame}{Current situation for serial NANDs}
  \begin{itemize}
  \item Support added much more recently (v4.19)
  \item At this time, only on-die ECC engines were supported
  \item Software engines not available (yet)!
  \item We see new devices coming out without embedded engines
    \begin{itemize}
    \item Cheaper to manufacture?
    \item More powerful (for larger corrections) to offload to dedicated
      hardware
    \item Even more when mutualizing between several chips
    \end{itemize}
  \item SPI-NAND subsystem not ready for that
  \end{itemize}
\end{frame}

\begin{frame}{External/pipelined ECC engine}
    \begin{center}
      \center\includegraphics[height=0.8\textheight]{spi-all-possible-engines.pdf}
    \end{center}
\end{frame}

\begin{frame}[fragile]{What describes ECC engines?}
  \begin{columns}
    \column{0.5\textwidth}
    \begin{itemize}
    \item What should discriminate two engines?
    \item Common properties may be used to pick the most appropriate one,
      like:
      \begin{itemize}
      \item The type of engine
      \item The possible strengths
      \item The supported chunk sizes (also called step size, or ECC size)
        on which the correction applies
      \end{itemize}
    \end{itemize}
    \column{0.5\textwidth}
    \begin{block}{}
      \begin{minted}[fontsize=\tiny]{c}
/**
 * struct nand_ecc_props - NAND ECC properties
 * @engine_type: ECC engine type
 * @placement: OOB placement (if relevant)
 * @algo: ECC algorithm (if relevant)
 * @strength: ECC strength
 * @step_size: Number of bytes per step
 * @flags: Misc properties
 */
struct nand_ecc_props {
	enum nand_ecc_engine_type engine_type;
	enum nand_ecc_placement placement;
	enum nand_ecc_algo algo;
	unsigned int strength;
	unsigned int step_size;
	unsigned int flags;
};
      \end{minted}
    \end{block}
  \end{columns}
\end{frame}

\begin{frame}[fragile]{How is the engine's configuration chosen?}
  \begin{itemize}
  \item The core must tune the engine's configuration to best fit the
    engine's capabilities, the NAND part requirements, the subsystem
    defaults, the user desires,...
    \begin{block}{}
      \begin{minted}[fontsize=\tiny]{c}
/**
 * struct nand_ecc - Information relative to the ECC
 * @defaults: Default values, depend on the underlying subsystem
 * @requirements: ECC requirements from the NAND chip perspective
 * @user_conf: User desires in terms of ECC parameters
 * @ctx: ECC context for the ECC engine, derived from the device @requirements
 *       the @user_conf and the @defaults
 * @ondie_engine: On-die ECC engine reference, if any
 * @engine: ECC engine actually bound
 */
struct nand_ecc {
	struct nand_ecc_props defaults;
	struct nand_ecc_props requirements;
	struct nand_ecc_props user_conf;
	struct nand_ecc_context ctx;
	struct nand_ecc_engine *ondie_engine;
	struct nand_ecc_engine *engine;
};
      \end{minted}
    \end{block}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]{Engine and configuration selection}
  \begin{itemize}
  \item For each NAND device, the core must find the engine to be used
    and tune it appropriately
    \begin{block}{}
      \begin{minted}[fontsize=\tiny]{c}
nanddev_ecc_engine_init(struct nand_device *nand)
{
	/* Look for the ECC engine to use */
	nanddev_get_ecc_engine(nand);

	/*
	 * Configure the engine:
	 * balance user input and chip requirements
	 */
	nanddev_find_ecc_configuration(nand)
	{
		nand_ecc_init_ctx(nand);

		if (!nand_ecc_is_strong_enough(nand))
			pr_warn("weak ECC...\n");
	}
}
      \end{minted}
    \end{block}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]{SPI-NAND Bindings}
  \begin{columns}
    \column{0.5\textwidth}

    \begin{block}{On die ECC engine}
      \begin{minted}[fontsize=\tiny]{c}
&spi_host {
	flash@0 {
		compatible = "spi-nand";
		reg = <0>;
		nand-ecc-engine = <&flash>;
	};
};
      \end{minted}
    \end{block}

    \begin{block}{External ECC engine}
      \begin{minted}[fontsize=\tiny]{c}
&spi_host {
	flash@0 {
		compatible = "spi-nand";
		reg = <0>;
		nand-ecc-engine = <&ecc_engine>;
	};
};

ecc_engine: ecc@xxxxxxxx {
	compatible = "mxic,nand-ecc-engine";
	reg = <xxxxxxxx yyyyyyyy>;
};
      \end{minted}
    \end{block}

    \column{0.5\textwidth}

    \begin{block}{Software ECC engine}
      \begin{minted}[fontsize=\tiny]{c}
&spi_host {
	flash@0 {
		compatible = "spi-nand";
		reg = <0>;
                       nand-use-soft-ecc-engine;
                       nand-ecc-algo = "bch";
	};
};
      \end{minted}
    \end{block}

    \begin{block}{On host ECC engine}
      \begin{minted}[fontsize=\tiny]{c}
&spi_host {
	nand-ecc-engine = <&ecc_engine>;
	flash@0 {
		compatible = "spi-nand";
		reg = <0>;
		nand-ecc-engine = <&spi_host>;
	};
};

ecc_engine: ecc@xxxxxxxx {
	compatible = "mxic,nand-ecc-engine";
	reg = <xxxxxxxx yyyyyyyy>;
};
      \end{minted}
    \end{block}
  \end{columns}
\end{frame}

\begin{frame}[fragile]{Hooks to provide}
  \begin{itemize}
    \item \code{->init/cleanup_ctx()} one time configuration/allocations
    \item \code{->prepare_io_req()} gets called for any page I/O
      requesting ECC correction, enables the engine, save information
      on the request, etc
    \item \code{->finish_io_req()} gets called for any page I/O
      requesting ECC correction, ends the transfer, disables the engine,
      reports read errors if relevant, etc
      \begin{block}{}
        \begin{minted}[fontsize=\tiny]{c}
/**
 * struct nand_ecc_engine_ops - ECC engine operations
 * @init_ctx: given a desired user configuration for the pointed NAND device, requests
 *            the ECC engine driver to setup a configuration with values it supports.
 * @cleanup_ctx: clean the context initialized by @init_ctx.
 * @prepare_io_req: is called before reading/writing a page to prepare the I/O request
 *                  to be performed with ECC correction.
 * @finish_io_req: is called after reading/writing a page to terminate the I/O request
 *                 and ensure proper ECC correction.
 */
struct nand_ecc_engine_ops {
	int (*init_ctx)(struct nand_device *nand);
	void (*cleanup_ctx)(struct nand_device *nand);
	int (*prepare_io_req)(struct nand_device *nand, struct nand_page_io_req *req);
	int (*finish_io_req)(struct nand_device *nand, struct nand_page_io_req *req);
};
        \end{minted}
      \end{block}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]{The final NAND ECC engine structure}
  \begin{itemize}
    \item This structure will be registered at probe time and saved into
      a system-wide list of available ECC engines
    \begin{block}{}
      \begin{minted}[fontsize=\tiny]{c}
/**
 * struct nand_ecc_engine - ECC engine abstraction for NAND
 *                          devices
 * @dev: Host device
 * @node: Private field for registration time
 * @ops: ECC engine operations
 * @priv: Private data
 */
struct nand_ecc_engine {
	struct device *dev;
	struct list_head node;
	struct nand_ecc_engine_ops *ops;
	void *priv;
};
      \end{minted}
    \end{block}
  \end{itemize}
\end{frame}

\begin{frame}{What's next?}
  \begin{itemize}
  \item Bootloaders don't have support for these external engines yet
  \item The raw NAND core carries so much history that is very difficult
    to make it fit the ECC abstraction without breaking numerous drivers
  \item New ECC engine drivers to come?
  \item NOR flashes carrying embedded Hamming ECC engines due to
    automotive safety constraints (ASIL-B/ASIL-D).
    \begin{itemize}
    \item[$\rightarrow$] Will it soon be offloaded? \Tiny{(please don't)}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \centering
  \Huge
  Questions? Suggestions? Comments?\\
  \vspace{0.5cm}
  \huge
  Miquèl Raynal\\
  \large
  \vspace{0.5cm}
  \hspace{2.6cm}\code{miquel@bootlin.com}
  \vspace{0.5cm}
  \newline Slides under CC-BY-SA 3.0\\
  \scriptsize
  \url{https://bootlin.com/pub/conferences/2020/elce/raynal-ecc-engines}
\end{frame}

\begin{frame}{References}
  \begin{itemize}
  \item RAM picture slide \ref{ram}:\\
    Unkown author. Possibly Cyberdex (given the
    authors right revendication). ``Personnal work'' supposed (given
    the revendication). Public domain,\\
    {\tiny\url{https://commons.wikimedia.org/w/index.php?curid=647267}}
  \item CD-R picture slide \ref{cd}:\\
    Author: Ubern00b, Personnal work, CC BY-SA 3.0,\\
    {\tiny\url{https://commons.wikimedia.org/w/index.php?curid=226419}}
  \item R. Hamming picture slide \ref{hamming}:\\
    Source (WP: NFCC 4), Fair use,\\
    {\tiny\url{https://en.wikipedia.org/w/index.php?curid=40177109}}
  \end{itemize}
\end{frame}

\end{document}
