[PATCH v3] lightnvm: pblk

[PATCH v3] lightnvm: pblk

[Javier González]

This patch introduces pblk, a new target for LightNVM implementing a
full host-based FTL. Details on the commit message.

Changes since v2:
* Rebase on top of Matias' for-4.12/core
* Implement L2P scan recovery to recover L2P table in case of power
  failure.
* Re-design disk format to be more flexible in future versions (from
  Matias Bjørling)
* Implement per-instance uuid to allow correct recovery without
  forcing line erases (from Matias Bjørling)
* Re-design GC threading to have several GC readers and a single
  writer that places data on the write buffer. This allows to maximize
  the GC write buffer budget without having unnecessary GC writers
  competing for the write buffer lock.
* Simplify sysfs interface.
* Refactoring and several code improvements (together with Matias
  Bjørling)

Changes since v1:
* Rebase on top of Matias' for-4.12/core
* Move from per-LUN block allocation to a line model. This means that a
  whole lines across all LUNs is allocated at a time. Data is still
  stripped in a round-robin fashion at a page granurality.
* Implement new disk format scheme, where metadata is stored per line
  instead of per LUN. This allows for space optimizations.
* Improvements on GC workqueue management and victim selection.
* Implement sysfs interface to query pblk's operation and statistics.
* Implement a user - GC I/O rate-limiter
* Various bug fixes

Javier González (1):
  lightnvm: physical block device (pblk) target

 Documentation/lightnvm/pblk.txt  |   21 +
 drivers/lightnvm/Kconfig         |   19 +
 drivers/lightnvm/Makefile        |    5 +
 drivers/lightnvm/pblk-cache.c    |  112 +++
 drivers/lightnvm/pblk-core.c     | 1641 ++++++++++++++++++++++++++++++++++++++
 drivers/lightnvm/pblk-gc.c       |  542 +++++++++++++
 drivers/lightnvm/pblk-init.c     |  942 ++++++++++++++++++++++
 drivers/lightnvm/pblk-map.c      |  135 ++++
 drivers/lightnvm/pblk-rb.c       |  859 ++++++++++++++++++++
 drivers/lightnvm/pblk-read.c     |  513 ++++++++++++
 drivers/lightnvm/pblk-recovery.c | 1007 +++++++++++++++++++++++
 drivers/lightnvm/pblk-rl.c       |  182 +++++
 drivers/lightnvm/pblk-sysfs.c    |  500 ++++++++++++
 drivers/lightnvm/pblk-write.c    |  408 ++++++++++
 drivers/lightnvm/pblk.h          | 1127 ++++++++++++++++++++++++++
 include/linux/lightnvm.h         |   57 +-
 pblk-sysfs.c                     |  581 ++++++++++++++
 17 files changed, 8638 insertions(+), 13 deletions(-)
 create mode 100644 Documentation/lightnvm/pblk.txt
 create mode 100644 drivers/lightnvm/pblk-cache.c
 create mode 100644 drivers/lightnvm/pblk-core.c
 create mode 100644 drivers/lightnvm/pblk-gc.c
 create mode 100644 drivers/lightnvm/pblk-init.c
 create mode 100644 drivers/lightnvm/pblk-map.c
 create mode 100644 drivers/lightnvm/pblk-rb.c
 create mode 100644 drivers/lightnvm/pblk-read.c
 create mode 100644 drivers/lightnvm/pblk-recovery.c
 create mode 100644 drivers/lightnvm/pblk-rl.c
 create mode 100644 drivers/lightnvm/pblk-sysfs.c
 create mode 100644 drivers/lightnvm/pblk-write.c
 create mode 100644 drivers/lightnvm/pblk.h
 create mode 100644 pblk-sysfs.c

-- 
2.7.4

Re: [PATCH v3] lightnvm: physical block device (pblk) target

[Bart Van Assche]

On 04/07/17 11:50, Javier Gonz=E1lez wrote:=0A=
>  Documentation/lightnvm/pblk.txt  |   21 +=0A=
>  drivers/lightnvm/Kconfig         |   19 +=0A=
>  drivers/lightnvm/Makefile        |    5 +=0A=
>  drivers/lightnvm/pblk-cache.c    |  112 +++=0A=
>  drivers/lightnvm/pblk-core.c     | 1641 ++++++++++++++++++++++++++++++++=
++++++=0A=
>  drivers/lightnvm/pblk-gc.c       |  542 +++++++++++++=0A=
>  drivers/lightnvm/pblk-init.c     |  942 ++++++++++++++++++++++=0A=
>  drivers/lightnvm/pblk-map.c      |  135 ++++=0A=
>  drivers/lightnvm/pblk-rb.c       |  859 ++++++++++++++++++++=0A=
>  drivers/lightnvm/pblk-read.c     |  513 ++++++++++++=0A=
>  drivers/lightnvm/pblk-recovery.c | 1007 +++++++++++++++++++++++=0A=
>  drivers/lightnvm/pblk-rl.c       |  182 +++++=0A=
>  drivers/lightnvm/pblk-sysfs.c    |  500 ++++++++++++=0A=
>  drivers/lightnvm/pblk-write.c    |  408 ++++++++++=0A=
>  drivers/lightnvm/pblk.h          | 1127 ++++++++++++++++++++++++++=0A=
>  include/linux/lightnvm.h         |   57 +-=0A=
>  pblk-sysfs.c                     |  581 ++++++++++++++=0A=
=0A=
This patch introduces two slightly different versions of pblk-sysfs.c - =0A=
one at the top level and one in drivers/lightnvm. Please remove the file=0A=
at the top level.=0A=
=0A=
> +config NVM_PBLK_L2P_OPT=0A=
> +	bool "PBLK with optimized L2P table for devices up to 8TB"=0A=
> +	depends on NVM_PBLK=0A=
> +	---help---=0A=
> +	Physical device addresses are typical 64-bit integers. Since we store=
=0A=
> +	the logical to physical (L2P) table on the host, this takes 1/500 of=0A=
> +	host memory (e.g., 2GB per 1TB of storage media). On drives under 8TB,=
=0A=
> +	it is possible to reduce this to 1/1000 (e.g., 1GB per 1TB). This=0A=
> +	option allows to do this optimization on the host L2P table.=0A=
=0A=
Why is NVM_PBLK_L2P_OPT a compile-time option instead of a run-time =0A=
option? Since this define does not affect the definition of the ppa_addr =
=0A=
I don't see why this has to be a compile-time option. For e.g. Linux =0A=
distributors the only choice would be to disable NVM_PBLK_L2P_OPT. I =0A=
think it would be unfortunate if no Linux distribution ever would be =0A=
able to benefit from this optimization.=0A=
=0A=
> +#ifdef CONFIG_NVM_DEBUG=0A=
> +	atomic_add(nr_entries, &pblk->inflight_writes);=0A=
> +	atomic_add(nr_entries, &pblk->req_writes);=0A=
> +#endif=0A=
=0A=
Has it been considered to use the "static key" feature such that =0A=
consistency checks can be enabled at run-time instead of having to =0A=
rebuild the kernel to enable CONFIG_NVM_DEBUG?=0A=
=0A=
> +#ifdef CONFIG_NVM_DEBUG=0A=
> +	BUG_ON(nr_rec_entries !=3D valid_entries);=0A=
> +	atomic_add(valid_entries, &pblk->inflight_writes);=0A=
> +	atomic_add(valid_entries, &pblk->recov_gc_writes);=0A=
> +#endif=0A=
=0A=
Are you aware that Linus is strongly opposed against using BUG_ON()?=0A=
=0A=
> +#ifdef CONFIG_NVM_DEBUG=0A=
> +	lockdep_assert_held(&l_mg->free_lock);=0A=
> +#endif=0A=
=0A=
Why is lockdep_assert_held() surrounded with #ifdef CONFIG_NVM_DEBUG / =0A=
#endif? Are you aware that lockdep_assert_held() do not generate any =0A=
code with CONFIG_PROVE_LOCKING=3Dn?=0A=
=0A=
> +static const struct block_device_operations pblk_fops =3D {=0A=
> +	.owner		=3D THIS_MODULE,=0A=
> +};=0A=
=0A=
Is this data structure useful? If so, where is pblk_fops used?=0A=
=0A=
> +static void pblk_l2p_free(struct pblk *pblk)=0A=
> +{=0A=
> +	vfree(pblk->trans_map);=0A=
> +}=0A=
> +=0A=
> +static int pblk_l2p_init(struct pblk *pblk)=0A=
> +{=0A=
> +	sector_t i;=0A=
> +=0A=
> +	pblk->trans_map =3D vmalloc(sizeof(pblk_addr) * pblk->rl.nr_secs);=0A=
> +	if (!pblk->trans_map)=0A=
> +		return -ENOMEM;=0A=
> +=0A=
> +	for (i =3D 0; i < pblk->rl.nr_secs; i++)=0A=
> +		pblk_ppa_set_empty(&pblk->trans_map[i]);=0A=
> +=0A=
> +	return 0;=0A=
> +}=0A=
=0A=
Has it been considered to add support for keeping a subset of the L2P =0A=
translation table in memory instead of keeping it in memory in its entirety=
?=0A=
=0A=
> +	sprintf(cache_name, "pblk_line_m_%s", pblk->disk->disk_name);=0A=
=0A=
Please use snprintf() or kasprintf() instead of printf(). That makes it =0A=
easier for humans to verify that no buffer overflow is triggered.=0A=
=0A=
> +/* physical block device target */=0A=
> +static struct nvm_tgt_type tt_pblk =3D {=0A=
> +	.name		=3D "pblk",=0A=
> +	.version	=3D {1, 0, 0},=0A=
=0A=
Are version numbers useful inside the kernel tree?=0A=
=0A=
> +void pblk_map_rq(struct pblk *pblk, struct nvm_rq *rqd, unsigned int sen=
try,=0A=
> +		 unsigned long *lun_bitmap, unsigned int valid_secs,=0A=
> +		 unsigned int off)=0A=
> +{=0A=
> +	struct pblk_sec_meta *meta_list =3D rqd->meta_list;=0A=
> +	unsigned int map_secs;=0A=
> +	int min =3D pblk->min_write_pgs;=0A=
> +	int i;=0A=
> +=0A=
> +	for (i =3D off; i < rqd->nr_ppas; i +=3D min) {=0A=
> +		map_secs =3D (i + min > valid_secs) ? (valid_secs % min) : min;=0A=
> +		pblk_map_page_data(pblk, sentry + i, &rqd->ppa_list[i],=0A=
> +					lun_bitmap, &meta_list[i], map_secs);=0A=
> +	}=0A=
> +}=0A=
=0A=
Has it been considered to implement the above code such that no modulo =0A=
(%) computation is needed, which is a relatively expensive operation? I =0A=
think for this loop that can be done easily.=0A=
=0A=
> +static DECLARE_RWSEM(pblk_rb_lock);=0A=
> +=0A=
> +void pblk_rb_data_free(struct pblk_rb *rb)=0A=
> +{=0A=
> +	struct pblk_rb_pages *p, *t;=0A=
> +=0A=
> +	down_write(&pblk_rb_lock);=0A=
> +	list_for_each_entry_safe(p, t, &rb->pages, list) {=0A=
> +		free_pages((unsigned long)page_address(p->pages), p->order);=0A=
> +		list_del(&p->list);=0A=
> +		kfree(p);=0A=
> +	}=0A=
> +	up_write(&pblk_rb_lock);=0A=
> +}=0A=
=0A=
Global locks like pblk_rb_lock are a performance bottleneck on =0A=
multi-socket systems. Why is that lock global?=0A=
=0A=
Bart.=0A=

Re: [PATCH v3] lightnvm: physical block device (pblk) target

[Javier González]

[-- Attachment #1: Type: text/plain, Size: 7415 bytes --]

Hi Bart,

Thanks for reviewing the code.

> On 8 Apr 2017, at 22.56, Bart Van Assche <bart.vanassche@sandisk.com> wrote:
> 
> On 04/07/17 11:50, Javier González wrote:
>> Documentation/lightnvm/pblk.txt  |   21 +
>> drivers/lightnvm/Kconfig         |   19 +
>> drivers/lightnvm/Makefile        |    5 +
>> drivers/lightnvm/pblk-cache.c    |  112 +++
>> drivers/lightnvm/pblk-core.c     | 1641 ++++++++++++++++++++++++++++++++++++++
>> drivers/lightnvm/pblk-gc.c       |  542 +++++++++++++
>> drivers/lightnvm/pblk-init.c     |  942 ++++++++++++++++++++++
>> drivers/lightnvm/pblk-map.c      |  135 ++++
>> drivers/lightnvm/pblk-rb.c       |  859 ++++++++++++++++++++
>> drivers/lightnvm/pblk-read.c     |  513 ++++++++++++
>> drivers/lightnvm/pblk-recovery.c | 1007 +++++++++++++++++++++++
>> drivers/lightnvm/pblk-rl.c       |  182 +++++
>> drivers/lightnvm/pblk-sysfs.c    |  500 ++++++++++++
>> drivers/lightnvm/pblk-write.c    |  408 ++++++++++
>> drivers/lightnvm/pblk.h          | 1127 ++++++++++++++++++++++++++
>> include/linux/lightnvm.h         |   57 +-
>> pblk-sysfs.c                     |  581 ++++++++++++++
> 
> This patch introduces two slightly different versions of pblk-sysfs.c -
> one at the top level and one in drivers/lightnvm. Please remove the file
> at the top level.

The top level file is a mistake; I'll remove it.

> 
>> +config NVM_PBLK_L2P_OPT
>> +	bool "PBLK with optimized L2P table for devices up to 8TB"
>> +	depends on NVM_PBLK
>> +	---help---
>> +	Physical device addresses are typical 64-bit integers. Since we store
>> +	the logical to physical (L2P) table on the host, this takes 1/500 of
>> +	host memory (e.g., 2GB per 1TB of storage media). On drives under 8TB,
>> +	it is possible to reduce this to 1/1000 (e.g., 1GB per 1TB). This
>> +	option allows to do this optimization on the host L2P table.
> 
> Why is NVM_PBLK_L2P_OPT a compile-time option instead of a run-time
> option? Since this define does not affect the definition of the ppa_addr
> I don't see why this has to be a compile-time option. For e.g. Linux
> distributors the only choice would be to disable NVM_PBLK_L2P_OPT. I
> think it would be unfortunate if no Linux distribution ever would be
> able to benefit from this optimization.

struct ppa_addr, which is the physical address format is not affected,
but pblk's internal L2P address representation (pblk_addr) is. You can
see that the type either represents struct ppa_addr or ppa_addr_32. How
would you define a type that can either be u64 or u32 with different bit
offsets at run-time? Note that address conversions to this type is in
the fast path and this format allows us to only use bit shifts.

> 
>> +#ifdef CONFIG_NVM_DEBUG
>> +	atomic_add(nr_entries, &pblk->inflight_writes);
>> +	atomic_add(nr_entries, &pblk->req_writes);
>> +#endif
> 
> Has it been considered to use the "static key" feature such that
> consistency checks can be enabled at run-time instead of having to
> rebuild the kernel to enable CONFIG_NVM_DEBUG?

I haven't considered it. I'll look into it. I would like to have this
counters and the corresponding sysfs entry only available on debug mode
since it allows us to have a good picture of the FTL state.

> 
>> +#ifdef CONFIG_NVM_DEBUG
>> +	BUG_ON(nr_rec_entries != valid_entries);
>> +	atomic_add(valid_entries, &pblk->inflight_writes);
>> +	atomic_add(valid_entries, &pblk->recov_gc_writes);
>> +#endif
> 
> Are you aware that Linus is strongly opposed against using BUG_ON()?
> 

Yes, I am aware of the discussions around BUG_ON. The rationale on the
cases we have it is that they represent a pblk internal state error.
This will most probably result on a wild memory access or an
out-of-bound, which will eventually cause the kernel to crash either
way. You can see that most of them are under CONFIG_NVM_DEBUG. Would it
make sense to maintain CONFIG_NVM_DEBUG so that all BUG_ON checks are
contained within them? As far as I can read, this is not possible with
"static key"

>> +#ifdef CONFIG_NVM_DEBUG
>> +	lockdep_assert_held(&l_mg->free_lock);
>> +#endif
> 
> Why is lockdep_assert_held() surrounded with #ifdef CONFIG_NVM_DEBUG /
> #endif? Are you aware that lockdep_assert_held() do not generate any
> code with CONFIG_PROVE_LOCKING=n?

I did not know about CONFIG_PROVE_LOCKING, thanks for pointing it out.

> 
>> +static const struct block_device_operations pblk_fops = {
>> +	.owner		= THIS_MODULE,
>> +};
> 
> Is this data structure useful? If so, where is pblk_fops used?

It is not useful anymore. I'll remove it.

> 
>> +static void pblk_l2p_free(struct pblk *pblk)
>> +{
>> +	vfree(pblk->trans_map);
>> +}
>> +
>> +static int pblk_l2p_init(struct pblk *pblk)
>> +{
>> +	sector_t i;
>> +
>> +	pblk->trans_map = vmalloc(sizeof(pblk_addr) * pblk->rl.nr_secs);
>> +	if (!pblk->trans_map)
>> +		return -ENOMEM;
>> +
>> +	for (i = 0; i < pblk->rl.nr_secs; i++)
>> +		pblk_ppa_set_empty(&pblk->trans_map[i]);
>> +
>> +	return 0;
>> +}
> 
> Has it been considered to add support for keeping a subset of the L2P
> translation table in memory instead of keeping it in memory in its entirety?

Yes. L2P caching is on our roadmap and will be included in the future.

> 
>> +	sprintf(cache_name, "pblk_line_m_%s", pblk->disk->disk_name);
> 
> Please use snprintf() or kasprintf() instead of printf(). That makes it
> easier for humans to verify that no buffer overflow is triggered.
> 

Ok.

>> +/* physical block device target */
>> +static struct nvm_tgt_type tt_pblk = {
>> +	.name		= "pblk",
>> +	.version	= {1, 0, 0},
> 
> Are version numbers useful inside the kernel tree?

It allows us to relate in to the disk format version, but most probably
the version on the actual disk format structures is enough.

> 
>> +void pblk_map_rq(struct pblk *pblk, struct nvm_rq *rqd, unsigned int sentry,
>> +		 unsigned long *lun_bitmap, unsigned int valid_secs,
>> +		 unsigned int off)
>> +{
>> +	struct pblk_sec_meta *meta_list = rqd->meta_list;
>> +	unsigned int map_secs;
>> +	int min = pblk->min_write_pgs;
>> +	int i;
>> +
>> +	for (i = off; i < rqd->nr_ppas; i += min) {
>> +		map_secs = (i + min > valid_secs) ? (valid_secs % min) : min;
>> +		pblk_map_page_data(pblk, sentry + i, &rqd->ppa_list[i],
>> +					lun_bitmap, &meta_list[i], map_secs);
>> +	}
>> +}
> 
> Has it been considered to implement the above code such that no modulo
> (%) computation is needed, which is a relatively expensive operation? I
> think for this loop that can be done easily.

I'll look into it.

> 
>> +static DECLARE_RWSEM(pblk_rb_lock);
>> +
>> +void pblk_rb_data_free(struct pblk_rb *rb)
>> +{
>> +	struct pblk_rb_pages *p, *t;
>> +
>> +	down_write(&pblk_rb_lock);
>> +	list_for_each_entry_safe(p, t, &rb->pages, list) {
>> +		free_pages((unsigned long)page_address(p->pages), p->order);
>> +		list_del(&p->list);
>> +		kfree(p);
>> +	}
>> +	up_write(&pblk_rb_lock);
>> +}
> 
> Global locks like pblk_rb_lock are a performance bottleneck on
> multi-socket systems. Why is that lock global?

This global lock is only used for the write buffer init and exit; it
does not touch the fast path. On tear down it guarantees that we flush
all the data present on the buffer before freeing the buffer itself.

> 
> Bart.

Javier

[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

Re: [PATCH v3] lightnvm: physical block device (pblk) target

[Bart Van Assche]

On Sun, 2017-04-09 at 11:15 +0200, Javier Gonz=E1lez wrote:
> On 8 Apr 2017, at 22.56, Bart Van Assche <bart.vanassche@sandisk.com> wro=
te:
> > On 04/07/17 11:50, Javier Gonz=E1lez wrote:
> struct ppa_addr, which is the physical address format is not affected,
> but pblk's internal L2P address representation (pblk_addr) is. You can
> see that the type either represents struct ppa_addr or ppa_addr_32. How
> would you define a type that can either be u64 or u32 with different bit
> offsets at run-time? Note that address conversions to this type is in
> the fast path and this format allows us to only use bit shifts.

Selecting the appropriate representation at run-time would require to pass
pblk_addr by reference instead of by value to any function that expects a
pblk_addr. It would also require to have two versions of every data structu=
re
that depends on pblk_addr and to use casts to convert to the appropritate
version. However, this approach is probably only worth to be implemented if
it doesn't introduce too much additional complexity.

> > > +#ifdef CONFIG_NVM_DEBUG
> > > +	atomic_add(nr_entries, &pblk->inflight_writes);
> > > +	atomic_add(nr_entries, &pblk->req_writes);
> > > +#endif
> >=20
> > Has it been considered to use the "static key" feature such that
> > consistency checks can be enabled at run-time instead of having to
> > rebuild the kernel to enable CONFIG_NVM_DEBUG?
>=20
> I haven't considered it. I'll look into it. I would like to have this
> counters and the corresponding sysfs entry only available on debug mode
> since it allows us to have a good picture of the FTL state.

If there are sysfs entries that depend on CONFIG_NVM_DEBUG then the static
key mechanism is probably not a good alternative for CONFIG_NVM_DEBUG.

> > Has it been considered to add support for keeping a subset of the L2P
> > translation table in memory instead of keeping it in memory in its enti=
rety?
>=20
> Yes. L2P caching is on our roadmap and will be included in the future.

That's great. This will also help with reducing the time between discovery =
of
a lightnvm device and the time at which I/O can start since the L2P table m=
ust
be available before I/O can start.

Bart.=

Re: [PATCH v3] lightnvm: physical block device (pblk) target

[Matias Bjørling]

On 04/10/2017 05:55 PM, Bart Van Assche wrote:
> On Sun, 2017-04-09 at 11:15 +0200, Javier Gonz�lez wrote:
>> On 8 Apr 2017, at 22.56, Bart Van Assche <bart.vanassche@sandisk.com> wrote:
>>> On 04/07/17 11:50, Javier Gonz�lez wrote:
>> struct ppa_addr, which is the physical address format is not affected,
>> but pblk's internal L2P address representation (pblk_addr) is. You can
>> see that the type either represents struct ppa_addr or ppa_addr_32. How
>> would you define a type that can either be u64 or u32 with different bit
>> offsets at run-time? Note that address conversions to this type is in
>> the fast path and this format allows us to only use bit shifts.
>
> Selecting the appropriate representation at run-time would require to pass
> pblk_addr by reference instead of by value to any function that expects a
> pblk_addr. It would also require to have two versions of every data structure
> that depends on pblk_addr and to use casts to convert to the appropritate
> version. However, this approach is probably only worth to be implemented if
> it doesn't introduce too much additional complexity.
>

Hi Bart, thanks for the feedback!

I've spent the time today to implement it such that 32bit entries are 
used if the device addressing can fit. We do see a slight overhead, 
however not enough to be a deal-breaker. We'll post an updated version 
with the flag removed.

>>>> +#ifdef CONFIG_NVM_DEBUG
>>>> +	atomic_add(nr_entries, &pblk->inflight_writes);
>>>> +	atomic_add(nr_entries, &pblk->req_writes);
>>>> +#endif
>>>
>>> Has it been considered to use the "static key" feature such that
>>> consistency checks can be enabled at run-time instead of having to
>>> rebuild the kernel to enable CONFIG_NVM_DEBUG?
>>
>> I haven't considered it. I'll look into it. I would like to have this
>> counters and the corresponding sysfs entry only available on debug mode
>> since it allows us to have a good picture of the FTL state.
>
> If there are sysfs entries that depend on CONFIG_NVM_DEBUG then the static
> key mechanism is probably not a good alternative for CONFIG_NVM_DEBUG.
>
>>> Has it been considered to add support for keeping a subset of the L2P
>>> translation table in memory instead of keeping it in memory in its entirety?
>>
>> Yes. L2P caching is on our roadmap and will be included in the future.
>
> That's great. This will also help with reducing the time between discovery of
> a lightnvm device and the time at which I/O can start since the L2P table must
> be available before I/O can start.

Definitely. I would love if one could jump in and implement it. We have 
a bunch of features that we want in before implementing a translation cache.
>
> Bart.
>