Livelock avoidance for data integrity writes
Subsystems (4)
Jan Kara
maintainerv5 cover Livelock avoidance for data integrity writes
Hi,
this is an update of my patches to implement livelock avoidance for data
integrity writes using page tagging. There are some minor changes against the previous versions:
* fixed some whitespace problems spotted checkpatch
* added WARN_ON_ONCE to catch a problem if radix_tree_range_tag_if_tagged tags more pages than we asked
* fixed radix_tree_range_tag_if_tagged to tag at most as many pages as we asked (it could tag one page more).
The patch now passed also XFSQA for XFS (well, several tests failed - like
192, 195, 228 ... - but they don't seem to be related - they are atime test, ctime test, file alignment test, ...). Also the radix tree code passed through 10000 iterations of the following test I've implemented in Andrew's rtth:
void copy_tag_check(void)
{
RADIX_TREE(tree, GFP_KERNEL);
unsigned long idx[ITEMS];
unsigned long start, end, count = 0, tagged, cur, tmp;
int i;// printf("generating radix tree indices...\n");
start = rand();
end = rand();
if (start > end && (rand() % 10)) {
cur = start;
start = end;
end = cur;
}
/* Specifically create items around the start and the end of the range
* with high probability to check for off by one errors */
cur = rand();
if (cur & 1) {
item_insert(&tree, start);
if (cur & 2) {
if (start <= end)
count++;
item_tag_set(&tree, start, 0);
}
}
if (cur & 4) {
item_insert(&tree, start-1);
if (cur & 8)
item_tag_set(&tree, start-1, 0);
}
if (cur & 16) {
item_insert(&tree, end);
if (cur & 32) {
if (start <= end)
count++;
item_tag_set(&tree, end, 0);
}
}
if (cur & 64) {
item_insert(&tree, end+1);
if (cur & 128)
item_tag_set(&tree, end+1, 0);
}
for (i = 0; i < ITEMS; i++) {
do {
idx[i] = rand();
} while (item_lookup(&tree, idx[i]));
item_insert(&tree, idx[i]);
if (rand() & 1) {
item_tag_set(&tree, idx[i], 0);
if (idx[i] >= start && idx[i] <= end)
count++;
}
/* if (i % 1000 == 0)
putchar('.'); */
}// printf("\ncopying tags...\n");
cur = start;
tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, ITEMS, 0, 1);// printf("checking copied tags\n");
assert(tagged == count);
check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
/* Copy tags in several rounds */
// printf("\ncopying tags...\n");
cur = start;
do {
tmp = rand() % (count/10+2);
tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, tmp, 0
} while (tmp == tagged);// printf("%lu %lu %lu\n", tagged, tmp, count);
// printf("checking copied tags\n");
check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
assert(tagged < tmp);
// printf("\n");
item_kill_tree(&tree);
}Honza
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Jan Kara
maintainerPATCH v5 1/2 radix-tree: Implement function radix_tree_range_tag_if_tagged
Implement function for setting one tag if another tag is set for each item in given range.
--- include/linux/radix-tree.h | 4 ++ lib/radix-tree.c | 94 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 98 insertions(+), 0 deletions(-)
include/linux/radix-tree.h +4 -0
@@ -192,6 +192,10 @@ unsigned int radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, unsigned long first_index, unsigned int max_items, unsigned int tag); +unsigned long radix_tree_range_tag_if_tagged (struct radix_tree_root *root, +unsigned long *first_indexp,unsigned long last_index, +unsigned long nr_to_tag, +unsigned int fromtag,unsigned int totag);int radix_tree_tagged (struct radix_tree_root *root,unsigned int tag);static inline void radix_tree_preload_end (void )
lib/radix-tree.c +94 -0
100 lines not on this page · raw message
Signature · 7 lines
1.6.4.2 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Jan Kara
maintainerPATCH v5 2/2 mm: Implement writeback livelock avoidance using page tagging
In reply to Jan KaraWe try to avoid livelocks of writeback when some steadily creates dirty pages in a mapping we are writing out. For memory-cleaning writeback, using nr_to_write works reasonably well but we cannot really use it for data integrity writeback. This patch tries to solve the problem.
The idea is simple: Tag all pages that should be written back with a special tag (TOWRITE) in the radix tree. This can be done rather quickly and thus livelocks should not happen in practice. Then we start doing the hard work of locking pages and sending them to disk only for those pages that have TOWRITE tag set.
Note: Adding new radix tree tag grows radix tree node from 288 to 296 bytes for 32-bit archs and from 552 to 560 bytes for 64-bit archs. However, the number of slab/slub items per page remains the same (13 and 7 respectively).
--- include/linux/fs.h | 1 + include/linux/radix-tree.h | 2 +- mm/page-writeback.c | 70 +++++++++++++++++++++++++++++++++---------- 3 files changed, 55 insertions(+), 18 deletions(-)
include/linux/fs.h +1 -0
@@ -685,6 +685,7 @@ struct block_device {*/ #define PAGECACHE_TAG_DIRTY 0#define PAGECACHE_TAG_WRITEBACK 1 +#define PAGECACHE_TAG_TOWRITE 2int mapping_tagged (struct address_space *mapping,int tag);
include/linux/radix-tree.h +1 -1
@@ -55,7 +55,7 @@ static inline int radix_tree_is_indirect_ptr(void *ptr)/*** radix-tree API starts here ***/ -#define RADIX_TREE_MAX_TAGS 2 +#define RADIX_TREE_MAX_TAGS 3/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */ struct radix_tree_root {
mm/page-writeback.c +53 -17
106 lines not on this page · raw message
Signature · 7 lines
1.6.4.2 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Jan Kara
maintainerPATCH v5 2/2 mm: Implement writeback livelock avoidance using page tagging
In reply to Jan KaraWe try to avoid livelocks of writeback when some steadily creates dirty pages in a mapping we are writing out. For memory-cleaning writeback, using nr_to_write works reasonably well but we cannot really use it for data integrity writeback. This patch tries to solve the problem.
The idea is simple: Tag all pages that should be written back with a special tag (TOWRITE) in the radix tree. This can be done rather quickly and thus livelocks should not happen in practice. Then we start doing the hard work of locking pages and sending them to disk only for those pages that have TOWRITE tag set.
Note: Adding new radix tree tag grows radix tree node from 288 to 296 bytes for 32-bit archs and from 552 to 560 bytes for 64-bit archs. However, the number of slab/slub items per page remains the same (13 and 7 respectively).
--- include/linux/fs.h | 1 + include/linux/radix-tree.h | 2 +- mm/page-writeback.c | 70 +++++++++++++++++++++++++++++++++---------- 3 files changed, 55 insertions(+), 18 deletions(-)
include/linux/fs.h +1 -0
@@ -685,6 +685,7 @@ struct block_device {*/ #define PAGECACHE_TAG_DIRTY 0#define PAGECACHE_TAG_WRITEBACK 1 +#define PAGECACHE_TAG_TOWRITE 2int mapping_tagged (struct address_space *mapping,int tag);
include/linux/radix-tree.h +1 -1
@@ -55,7 +55,7 @@ static inline int radix_tree_is_indirect_ptr(void *ptr)/*** radix-tree API starts here ***/ -#define RADIX_TREE_MAX_TAGS 2 +#define RADIX_TREE_MAX_TAGS 3/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */ struct radix_tree_root {
mm/page-writeback.c +53 -17
106 lines not on this page · raw message
Signature · 1 line
1.6.4.2