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

[avagin at gmail.com]

On 04/07/2012 12:18 PM, Cyrill Gorcunov wrote:
> 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?
No, because s_vma points on vma after the hole.
>
> 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.

Look at "continue" one more time.
prev_vma_end is returned only if both condition are true

if (prev_vma_end + vma_len > s_vma->vma.start) {
....
if (prev_vma_end + vma_len > t_vma->vma.start) {
...

>
> Or I miss something obvious?
>
> 	Cyrill