Xen devel - Aug 2006 - [PATCH] wrong accounting in direct_remap_pfn_range

Looking into the code in linux-2.6-xen-sparse/arch/i386/mm/ioremap-xen.c

I found some logic that did not make sense.  We have a loop than updates 
the page tables in __direct_remap_pfn_range, and in the beginning of 
that loop, there is a test that if we finished the page
(v-u == PAGE_SIZE/sizeof(mmu_update_t)) we call the hypervisor to do our 
update.  This is all fine and dandy but, but the code right after the 
loop seems to be wrong.

There is a check if (v != u) then do some more work.  I''m assuming that
this code is there in case we didn''t reach the if statement at the top 
of the loop.  But what is wrong is that this check is invalid.  Although 
the loop if statement sets v = u, the following if statement ignores the 
fact that v++ is done at the bottom of the loop.  So if we really want 
to do this extra work if we didn''t finish the loop, then the test
really
needs to be.

if ((v - u) != 1) { .... }


Unless I''m missing something here, I''ve attached a patch.

-- Steve

Signed-off-by: Steven Rostedt <srostedt@redhat.com>



_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

Steven Rostedt wrote:
> Looking into the code in linux-2.6-xen-sparse/arch/i386/mm/ioremap-xen.c
> 
> I found some logic that did not make sense.  We have a loop than updates 
> the page tables in __direct_remap_pfn_range, and in the beginning of 
> that loop, there is a test that if we finished the page
> (v-u == PAGE_SIZE/sizeof(mmu_update_t)) we call the hypervisor to do our 
> update.  This is all fine and dandy but, but the code right after the 
> loop seems to be wrong.
> 
> There is a check if (v != u) then do some more work.  I''m assuming
that
> this code is there in case we didn''t reach the if statement at the
top
> of the loop.  But what is wrong is that this check is invalid.  Although 
> the loop if statement sets v = u, the following if statement ignores the 
> fact that v++ is done at the bottom of the loop.  So if we really want 
> to do this extra work if we didn''t finish the loop, then the test
really
> needs to be.
> 
> if ((v - u) != 1) { .... }
> 
> 
> Unless I''m missing something here, I''ve attached a patch.
>
I did miss something.  The fact that the loop may only go once.  This 
means that v - u will equal 1 and we miss that allocation.  So to handle 
  this, I''m submitting this patch that just keeps track of whether or 
not we need to do the final fixup.

-- Steve

Signed-off-by: Steven Rostedt <srostedt@redhat.com>




_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

I think you''re confused. The only time we execute the test-and-fixup
code is
if we exit the for loop in the normal way. All exceptional exits from the
loop are done by ''goto out'', which skips the test-and-fixup
code. So we can
only reach the test-and-fixup code after executing a whole number of
iterations of the for loop, so I don''t think that there is a problem.

 -- Keir

On 29/8/06 7:22 pm, "Steven Rostedt" <srostedt@redhat.com>
wrote:
>> There is a check if (v != u) then do some more work.  I''m
assuming that
>> this code is there in case we didn''t reach the if statement at
the top
>> of the loop.  But what is wrong is that this check is invalid. 
Although
>> the loop if statement sets v = u, the following if statement ignores
the
>> fact that v++ is done at the bottom of the loop.  So if we really want
>> to do this extra work if we didn''t finish the loop, then the
test really
>> needs to be.
>> 
>> if ((v - u) != 1) { .... }
>> 
>> 
>> Unless I''m missing something here, I''ve attached a
patch.
>> 
> 
> I did miss something.  The fact that the loop may only go once.  This
> means that v - u will equal 1 and we miss that allocation.  So to handle
>   this, I''m submitting this patch that just keeps track of whether
or
> not we need to do the final fixup.


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

Keir Fraser wrote:
> I think you''re confused. 
I usually am :)  But not on this one :P
> The only time we execute the test-and-fixup code is
Actually, "fixup" was the wrong name of the variable, so it was 
confusing. Perhaps I should have called it "finish", as in finish 
processing.
> if we exit the for loop in the normal way. All exceptional exits from the
> loop are done by ''goto out'', which skips the
test-and-fixup code. So we can
> only reach the test-and-fixup code after executing a whole number of
> iterations of the for loop, so I don''t think that there is a
problem.
I wasn''t talking about exceptions.  Just fixing up what wasn''t
finished.
But the "fixup" name made it confusing.

The problem is here: let me cut and paste the code to show you.

	for (i = 0; i < size; i += PAGE_SIZE) {

** we are looping here to cover each value in v->val that walks up
"u"

		if ((v - u) == (PAGE_SIZE / sizeof(mmu_update_t))) {

** we enter this condition when we have filled up "u".

			/* Fill in the PTE pointers. */
			rc = apply_to_page_range(mm, start_address,
					 address - start_address,
					 direct_remap_area_pte_fn, &w);
			if (rc)
				goto out;
			w = u;
			rc = -EFAULT;
			if (HYPERVISOR_mmu_update(u, v - u, NULL, domid) < 0)
				goto out;

** here we assign v to u and if this was our last address. That is
** we break out of the loop, you think there''s nothing more to be done.
** Right??

			v = u;
			start_address = address;

** But we continue the loop.

** Note: This could also be solved by putting in:

* if (i == size)
*    break;


		}

		/*
		 * Fill in the machine address: PTE ptr is done later by
		 * __direct_remap_area_pages().
		 */

** we set v->val to the next mfn, even if we are done (because we filled
** up u already).
** But that''s ok, since we are done, we don''t need to do
anything with
** "u" anymore, right?

		v->val = pte_val_ma(pfn_pte_ma(mfn, prot));

		mfn++;
		address += PAGE_SIZE;

** oooh, we increment v here, so v != u, although we finished and are
**  done, and we now have a bad value in u.

		v++;
	}

** Uh Oh, v != u so we go into this if statement.

	if (v != u) {
		/* get the ptep''s filled in */

** Now we "apply_to_page_range" with a bad value in "u".

		rc = apply_to_page_range(mm, start_address,
					 address - start_address,
					 direct_remap_area_pte_fn, &w);
		if (rc)
			goto out;
		rc = -EFAULT;
		if (unlikely(HYPERVISOR_mmu_update(u, v - u, NULL, domid) < 0))
			goto out;
	}




So "fixup" was a bad choice for a variable name.  Should I resend the 
patch with the variable "done" or "finished"?  Or do you
prefer the "if
(i == size) break;" better?

This bug probably was never hit, since the chances of sending in just 
enough pages to map that fills up "u" but no more is very very slim. 
But it _can_ happen, and I''d hate to be the one who is assigned that 
bugzilla!  This bug was found by me just going over the code and seeing 
how things tick.  I didn''t actually run into the bug.

But if you tell me that this isn''t a bug, then you might as well remove
that if statement and just do that apply_to_page_range every time, or 
tell me what I''m really missing.

So, I''m not confused here, but sorry for confusing you :)


-- Steve


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

Steven Rostedt wrote:
> Keir Fraser wrote:
>> I think you''re confused. 
> 
> I usually am :)  But not on this one :P
> 
grr, I take it back, I am the one that''s confused :P


OK, this all happens because this whole blob of code is crazy because it 
is missing a "if (size == 0)" check!

The "if (v != u)" is only not true when this function is called with 
size == 0, and we don''t need to do anything.  Why not just have that 
check in the beginning and remove the "if (v != u)"?

It would have saved me a lot of wasted time here.  Or is this code meant 
to confuse me?

Sorry,


-- Steve

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

On 31/8/06 1:37 am, "Steven Rostedt" <srostedt@redhat.com>
wrote:
> grr, I take it back, I am the one that''s confused :P
> 
> OK, this all happens because this whole blob of code is crazy because it
> is missing a "if (size == 0)" check!
It''s not really missing. We could have a size==0 check *or* we can have
the
v!=u check. We don''t need both and I think the latter is more obviously
correct, as the test is closer to the code that it ''protects''.
Also it''s a
fairly idiomatic way of generating and flushing batches of work.

 -- Keir
> The "if (v != u)" is only not true when this function is called
with
> size == 0, and we don''t need to do anything.  Why not just have
that
> check in the beginning and remove the "if (v != u)"?
>
> It would have saved me a lot of wasted time here.  Or is this code meant
> to confuse me?


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

Keir Fraser wrote:
> On 31/8/06 1:37 am, "Steven Rostedt" <srostedt@redhat.com>
wrote:
> 
>> grr, I take it back, I am the one that''s confused :P
>>
>> OK, this all happens because this whole blob of code is crazy because
it
>> is missing a "if (size == 0)" check!
> 
> It''s not really missing. We could have a size==0 check *or* we can
have the
> v!=u check. We don''t need both and I think the latter is more
obviously
> correct, as the test is closer to the code that it
''protects''. Also it''s a
> fairly idiomatic way of generating and flushing batches of work.
> 
Well it wasn''t obvious to me :P

If a size == 0 is passed in (for whatever reason!), couldn''t we skip
the
  flush_cache_all, flush_tlb_all and the allocation and freeing of a 
page and just return?

If you want this in mainline Linux, you''ll probably have others mention
that too.

-- Steve


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

Keir Fraser wrote:
> On 31/8/06 1:37 am, "Steven Rostedt" <srostedt@redhat.com>
wrote:
> 
>> grr, I take it back, I am the one that''s confused :P
>>
>> OK, this all happens because this whole blob of code is crazy because
it
>> is missing a "if (size == 0)" check!
> 
> It''s not really missing. We could have a size==0 check *or* we can
have the
> v!=u check. We don''t need both and I think the latter is more
obviously
> correct, as the test is closer to the code that it
''protects''. Also it''s a
> fairly idiomatic way of generating and flushing batches of work.
>
So what is really wrong with this code?  Or is the flushes need even on 
size == 0?

-- Steve

Signed-off-by: Steven Rostedt <srostedt@redhat.com>




_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

On 31/8/06 2:03 am, "Steven Rostedt" <srostedt@redhat.com>
wrote:
>> It''s not really missing. We could have a size==0 check *or* we
can have the
>> v!=u check. We don''t need both and I think the latter is more
obviously
>> correct, as the test is closer to the code that it
''protects''. Also it''s a
>> fairly idiomatic way of generating and flushing batches of work.
>> 
> 
> So what is really wrong with this code?  Or is the flushes need even on
> size == 0?
This patch is fine. But it''s no more correct than the current version
of the
code because there is no bug. I don''t think your version is
particularly
clearer.

 -- Keir



_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

Keir Fraser wrote:
> 
> 
> On 31/8/06 2:03 am, "Steven Rostedt" <srostedt@redhat.com>
wrote:
> 
>>> It''s not really missing. We could have a size==0 check
*or* we can have the
>>> v!=u check. We don''t need both and I think the latter is
more obviously
>>> correct, as the test is closer to the code that it
''protects''. Also it''s a
>>> fairly idiomatic way of generating and flushing batches of work.
>>>
>> So what is really wrong with this code?  Or is the flushes need even on
>> size == 0?
> 
> This patch is fine. But it''s no more correct than the current
version of the
> code because there is no bug. I don''t think your version is
particularly
> clearer.
> 
You''re right that the original version was not a bug, which I
admittedly
thought it was.

As for clarity, I''ll argue that my version is clearer. Just because it 
shows exactly that nothing needs to be done when size is zero, instead 
having a check for (v != u) that is only true when we have a zero size.

Usually, when I have a condition of that sort that comes after a loop 
incrementing v and lets v return back to u, I have that condition need 
to be done if a) the loop wasn''t entered (as in this case), or b) the 
condition in the loop wasn''t done at the end (which isn''t the
case here).

Hence, the reason that I thought it was a bug.  Nowhere is there a 
comment that says /* don''t do anything if size was 0 */.

Now enough about clarity.  By the off chance that size would be zero 
(which I still don''t know when that would be), we waste time with 
flushing caches and the TLB, not to mention wasted time getting a memory 
page and freeing it.

But this is all moot anyway, since there is no bug being fixed.  But as 
for submitting to mainline, I''ve submitted enough patches to know that 
Andrew Morton actually cares about readability and optimizations (even 
on the not so often path if it doesn''t hurt anything else).  And I have
a tough time seeing Andrew (or others) think that

   v = u;
   for (i=0; i < size; ...) {
      if (v - u/ ...) {
         ...
         v = u;
         ...
      }
      ...
      v++;
      ...
   }
   if (v != u) { ... }

is more readable and clearer than

   if (!size) return 0;

   for (...) {
     ...
   }
   /* no if needed */
   ....


But that''s just my opinion.  Take it for what it''s worth.

-- Steve

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel