// SPDX-License-Identifier: GPL-2.0
/*
* Bad block management
*
* - Heavily based on MD badblocks code from Neil Brown
*
* Copyright (c) 2015, Intel Corporation.
*/
#include <linux/badblocks.h>
#include <linux/seqlock.h>
#include <linux/device.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/stddef.h>
#include <linux/types.h>
#include <linux/slab.h>
/*
* The purpose of badblocks set/clear is to manage bad blocks ranges which are
* identified by LBA addresses.
*
* When the caller of badblocks_set() wants to set a range of bad blocks, the
* setting range can be acked or unacked. And the setting range may merge,
* overwrite, skip the overlapped already set range, depends on who they are
* overlapped or adjacent, and the acknowledgment type of the ranges. It can be
* more complicated when the setting range covers multiple already set bad block
* ranges, with restrictions of maximum length of each bad range and the bad
* table space limitation.
*
* It is difficult and unnecessary to take care of all the possible situations,
* for setting a large range of bad blocks, we can handle it by dividing the
* large range into smaller ones when encounter overlap, max range length or
* bad table full conditions. Every time only a smaller piece of the bad range
* is handled with a limited number of conditions how it is interacted with
* possible overlapped or adjacent already set bad block ranges. Then the hard
* complicated problem can be much simpler to handle in proper way.
*
* When setting a range of bad blocks to the bad table, the simplified situations
* to be considered are, (The already set bad blocks ranges are naming with
* prefix E, and the setting bad blocks range is naming with prefix S)
*
* 1) A setting range is not overlapped or adjacent to any other already set bad
* block range.
* +--------+
* | S |
* +--------+
* +-------------+ +-------------+
* | E1 | | E2 |
* +-------------+ +-------------+
* For this situation if the bad blocks table is not full, just allocate a
* free slot from the bad blocks table to mark the setting range S. The
* result is,
* +-------------+ +--------+ +-------------+
* | E1 | | S | | E2 |
* +-------------+ +--------+ +-------------+
* 2) A setting range starts exactly at a start LBA of an already set bad blocks
* range.
* 2.1) The setting range size < already set range size
* +--------+
* | S |
* +--------+
* +-------------+
* | E |
* +-------------+
* 2.1.1) If S and E are both acked or unacked range, the setting range S can
* be merged into existing bad range E. The result is,
* +-------------+
* | S |
* +-------------+
* 2.1.2) If S is unacked setting and E is acked, the setting will be denied, and
* the result is,
* +-------------+
* | E |
* +-------------+
* 2.1.3) If S is acked setting and E is unacked, range S can overwrite on E.
* An extra slot from the bad blocks table will be allocated for S, and head
* of E will move to end of the inserted range S. The result is,
* +--------+----+
* | S | E |
* +--------+----+
* 2.2) The setting range size == already set range size
* 2.2.1) If S and E are both acked or unacked range, the setting range S can
* be merged into existing bad range E. The result is,
* +-------------+
* | S |
* +-------------+
* 2.2.2) If S is unacked setting and E is acked, the setting will be denied, and
* the result is,
* +-------------+
* | E |
* +-------
| 