dm vdo: add basic hash map data structures
authorMatthew Sakai <msakai@redhat.com>
Fri, 17 Nov 2023 00:49:57 +0000 (19:49 -0500)
committerMike Snitzer <snitzer@kernel.org>
Tue, 20 Feb 2024 18:43:13 +0000 (13:43 -0500)
commitcc46b9554b3f6d2f09b1111386b2706e5b4f56c8
treec6247c73746bc7e2f374cdfcf2fa67c54fe1423c
parentd9e894d9b2ec9f3117f4d16400a3981c48bb0639
dm vdo: add basic hash map data structures

This patch adds two hash maps, one keyed by integers, the other by
pointers, and also a priority heap. The integer map is used for locking of
logical and physical addresses. The pointer map is used for managing
concurrent writes of the same data, ensuring that those writes are
deduplicated. The priority heap is used to minimize the search time for
free blocks.

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>
Signed-off-by: Matthew Sakai <msakai@redhat.com>
Signed-off-by: Mike Snitzer <snitzer@kernel.org>
drivers/md/dm-vdo/int-map.c [new file with mode: 0644]
drivers/md/dm-vdo/int-map.h [new file with mode: 0644]
drivers/md/dm-vdo/pointer-map.c [new file with mode: 0644]
drivers/md/dm-vdo/pointer-map.h [new file with mode: 0644]
drivers/md/dm-vdo/priority-table.c [new file with mode: 0644]
drivers/md/dm-vdo/priority-table.h [new file with mode: 0644]