Re: [PATCH 5/9] lib: radix-tree: check accounting of existing slot replacement users

[Jan Kara]

On Thu 17-11-16 14:30:21, Johannes Weiner wrote:
> The bug in khugepaged fixed earlier in this series shows that radix
> tree slot replacement is fragile; and it will become more so when not
> only NULL<->!NULL transitions need to be caught but transitions from
> and to exceptional entries as well. We need checks.
> 
> Re-implement radix_tree_replace_slot() on top of the sanity-checked
> __radix_tree_replace(). This requires existing callers to also pass
> the radix tree root, but it'll warn us when somebody replaces slots
> with contents that need proper accounting (transitions between NULL
> entries, real entries, exceptional entries) and where a replacement
> through the slot pointer would corrupt the radix tree node counts.
> 
> Suggested-by: Jan Kara 
> Signed-off-by: Johannes Weiner 

Looks good. You can add:

Reviewed-by: Jan Kara 

One nit below:

> @@ -785,6 +776,50 @@ void __radix_tree_replace(struct radix_tree_root *root,
>  }
>  
>  /**
> + * __radix_tree_replace  - replace item in a slot
> + * @root:radix tree root
> + * @node:pointer to tree node
> + * @slot:pointer to slot in @node
> + * @item:new item to store in the slot.
> + *
> + * For use with __radix_tree_lookup().  Caller must hold tree write locked
> + * across slot lookup and replacement.
> + */

I'd comment here that even this function cannot be used for NULL <->
non-NULL replacements. For that are radix_tree_delete() and
radix_tree_insert().

Honza
-- 
Jan Kara 
SUSE Labs, CR

Re: [PATCH 5/9] lib: radix-tree: check accounting of existing slot replacement users

[Jan Kara]

On Thu 17-11-16 14:30:21, Johannes Weiner wrote:
> The bug in khugepaged fixed earlier in this series shows that radix
> tree slot replacement is fragile; and it will become more so when not
> only NULL<->!NULL transitions need to be caught but transitions from
> and to exceptional entries as well. We need checks.
> 
> Re-implement radix_tree_replace_slot() on top of the sanity-checked
> __radix_tree_replace(). This requires existing callers to also pass
> the radix tree root, but it'll warn us when somebody replaces slots
> with contents that need proper accounting (transitions between NULL
> entries, real entries, exceptional entries) and where a replacement
> through the slot pointer would corrupt the radix tree node counts.
> 
> Suggested-by: Jan Kara 
> Signed-off-by: Johannes Weiner 

Looks good. You can add:

Reviewed-by: Jan Kara 

One nit below:

> @@ -785,6 +776,50 @@ void __radix_tree_replace(struct radix_tree_root *root,
>  }
>  
>  /**
> + * __radix_tree_replace  - replace item in a slot
> + * @root:radix tree root
> + * @node:pointer to tree node
> + * @slot:pointer to slot in @node
> + * @item:new item to store in the slot.
> + *
> + * For use with __radix_tree_lookup().  Caller must hold tree write locked
> + * across slot lookup and replacement.
> + */

I'd comment here that even this function cannot be used for NULL <->
non-NULL replacements. For that are radix_tree_delete() and
radix_tree_insert().

Honza
-- 
Jan Kara 
SUSE Labs, CR