dm vdo: implement the open chapter and chapter indexes
authorMatthew Sakai <msakai@redhat.com>
Fri, 17 Nov 2023 00:54:29 +0000 (19:54 -0500)
committerMike Snitzer <snitzer@kernel.org>
Tue, 20 Feb 2024 18:43:14 +0000 (13:43 -0500)
commit6afc7bcaa40d7ec6bf37483b35e68615cfaad524
tree04ca6f0c0fe5390dfcb60c21b153505c35e2f2ab
parenta4eb7e2555171a95135678ea111a60f0d2a154e6
dm vdo: implement the open chapter and chapter indexes

Deduplication records are stored in groups called chapters. New records are
collected in a structure called the open chapter, which is optimized for
adding, removing, and sorting records.

When a chapter fills, it is packed into a read-only structure called a
closed chapter, which is optimized for searching and reading. The closed
chapter includes a delta index, called the chapter index, which maps each
record name to the record page containing the record and allows the index
to read at most one record page when looking up a record.

Co-developed-by: J. corwin Coburn <corwin@hurlbutnet.net>
Signed-off-by: J. corwin Coburn <corwin@hurlbutnet.net>
Co-developed-by: Michael Sclafani <dm-devel@lists.linux.dev>
Signed-off-by: Michael Sclafani <dm-devel@lists.linux.dev>
Co-developed-by: Thomas Jaskiewicz <tom@jaskiewicz.us>
Signed-off-by: Thomas Jaskiewicz <tom@jaskiewicz.us>
Signed-off-by: Matthew Sakai <msakai@redhat.com>
Signed-off-by: Mike Snitzer <snitzer@kernel.org>
drivers/md/dm-vdo/chapter-index.c [new file with mode: 0644]
drivers/md/dm-vdo/chapter-index.h [new file with mode: 0644]
drivers/md/dm-vdo/open-chapter.c [new file with mode: 0644]
drivers/md/dm-vdo/open-chapter.h [new file with mode: 0644]