[CRIU] Re: [PATCH cr] restore: optimize restorer_get_vma_hint

[Cyrill Gorcunov]

On Sat, Apr 07, 2012 at 11:09:29AM +0400, Andrey Vagin wrote:
> It's an O(n) algorithm.
> 
> Now we iterate both lists simultaneously to find a hole.
> 
> Signed-off-by: Andrey Vagin <avagin at openvz.org>
> ---
>  cr-restore.c |   49 ++++++++++++++++++++++++++++++++-----------------
>  1 files changed, 32 insertions(+), 17 deletions(-)
> 
> diff --git a/cr-restore.c b/cr-restore.c
> index 2162fc1..8405336 100644
> --- a/cr-restore.c
> +++ b/cr-restore.c
> @@ -870,39 +870,54 @@ static int restore_all_tasks(pid_t pid, struct cr_options *opts)
>  	return restore_root_task(pid, opts);
>  }
>  
> +#define TASK_SIZE_MAX   ((1UL << 47) - PAGE_SIZE)
>  static long restorer_get_vma_hint(pid_t pid, struct list_head *tgt_vma_list,
>  		struct list_head *self_vma_list, long vma_len)
>  {
> -	struct vma_area *t_vma;
> +	struct vma_area *t_vma, *s_vma;
>  	long prev_vma_end = 0;
> +	struct vma_area end_vma;
> +
> +	end_vma.vma.start = end_vma.vma.end = TASK_SIZE_MAX;
> +	prev_vma_end = PAGE_SIZE;
>  
>  	/*
>  	 * Here we need some heuristics -- the VMA which restorer will
>  	 * belong to should not be unmapped, so we need to gueess out
>  	 * where to put it in.
> -	 *
> -	 * Yes, I know it's an O(n^2) algorithm, but usually there are
> -	 * not that many VMAs presented so instead of consuming memory
> -	 * better to stick with it.
>  	 */
>  
> -	list_for_each_entry(t_vma, tgt_vma_list, list) {
> -		if (prev_vma_end && ((t_vma->vma.start - prev_vma_end) > vma_len)) {
> -			struct vma_area *s_vma;
> -			unsigned long prev_vma_end2 = 0;
> +	s_vma = list_first_entry(self_vma_list, struct vma_area, list);
> +	t_vma = list_first_entry(tgt_vma_list, struct vma_area, list);
>  
> -			list_for_each_entry(s_vma, self_vma_list, list) {
> -				if (prev_vma_end2 + vma_len > t_vma->vma.start)
> -					break;
> -				if (prev_vma_end2 && (prev_vma_end2 >= prev_vma_end) &&
> -				    ((s_vma->vma.start - prev_vma_end2) > vma_len))
> -					return prev_vma_end2;
> +	while (1) {
> +		if (prev_vma_end + vma_len > s_vma->vma.start) {
> +			if (s_vma->list.next == self_vma_list) {
> +				s_vma = &end_vma;

If s_vma is the last one on self_vma_list you could break immediately, no?

And the snippet I somehow miss is -- how the situation handled when

              hole
            a      b
source |----|      |-----|
target   |----|      |-----|
              c      d

the hole fits the requested size but the hole is shifted
in target, so that you've

	prev_vma_end = a

and then you find that a - d > vma_len and return a
as start address for new mapping while finally it
might intersect with address c.

Or I miss something obvious?

	Cyrill