buglwIP - A Lightweight TCP/IP stack - Bugs: bug #37166, memp_sanity check loops itself

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #37166: memp_sanity check loops itself

Submitted by:  Artem Pisarenko <jblackarty>
Submitted on:  Wed 22 Aug 2012 09:36:17 AM UTC  
 
Category:  None Severity:  3 - Normal
Item Group:  Faulty Behaviour Status:  Fixed
Privacy:  Public Assigned to:  Simon Goldschmidt <goldsimon>
Open/Closed:  Closed Planned Release:  None
lwIP version:  1.4.0

Wed 22 Aug 2012 08:01:06 PM UTC, comment #4: 

> I think the right way to do this would be "Floyd's Cycle-Finding

Algorithm"

Nice idea, thanks for that.

Fixed, thanks for reporting.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 22 Aug 2012 01:22:07 PM UTC, comment #3: 

> if (n == m && --c < 0)
>
> is not the same as
> if (n == m & --c < 0)
>
> but is equivalent to
> if (n == m)
>   if (--c < 0)


Of course it is. But what's "cruel" about boolean operators?

That's what the code wants to do: when looping the inner loop, m==n may be true exactly one time. If it's true more than once, we have a loop.

The problem is that we can have a loop without reaching m==n, so c is never decremented.

I'll fix it by adding another counter that checks that considers "memp_num" as maximum loop count.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 22 Aug 2012 01:06:12 PM UTC, comment #2: 

>> primary (which caused memp-lists to form a circle)


>This is most often a threading problem in the way lwIP is used, rather than an actual bug in lwIP.


Maybe. But I don't expect incorrect usage in my code. Because:
1. Application-level usage is only tcpecho from contribs.
2. Functions of system layer of my port (NO_SYS == 0) call memp_alloc()/memp_free() only, which are allowed to use and are simple enough to not misuse them.
3. My ethernet driver designed with reference to ethernetif.c in terms of how driver should iteract with lwip safely. ethernetif_input() contents are executed from driver thread context. low_level_output() directly fills dma transmit buffers but blocks thread to wait them to be available (if they still owned by dma after previous transmit start)

>> Author of this code caught in a trap of tricky and cruel '&&' short-circuit operator ;)


> I don't think I get what you want to say here. Can you suggest a fix?


Seems like my english isn't good enough to explain such complex statements :) I'll try once more.
Fragment

if (n == m && --c < 0)

is not the same as

if (n == m & --c < 0)

but is equivalent to

if (n == m)
  if (--c < 0)

Maybe author considered that or maybe not.
Anyway this means that if memp_sanity encounters with so called "circle" (pointers loop) then cycle condition in for(;;) statement will never be false. The only way for memp_sanity to rescue own ass from endless loop is to decrement 'c' variable two times. But it decrements only when 'n' become equal to 'm'. This happens only one time in first iteration of for(;;) cycle. In subsequent iterations 'n' values are become cycled in some range. There are no guarantee that 'm' value will be in that range.
And I can not suggest a fix. I already tired to explain and it's time to go home. :) Maybe tomorrow.

Artem Pisarenko <jblackarty>
Wed 22 Aug 2012 11:05:49 AM UTC, comment #1: 

> primary (which caused memp-lists to form a circle)


This is most often a threading problem in the way lwIP is used, rather than an actual bug in lwIP.

> Author of this code caught in a trap of tricky and cruel '&&' short-circuit operator ;)


I don't think I get what you want to say here. Can you suggest a fix?

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 22 Aug 2012 09:36:17 AM UTC, original submission:  

Did you check this check ? ;) I fall into this error and was going to report two bugs: primary (which caused memp-lists to form a circle) and memp_sanity internal which was detected thanks to first one. But I'm not able to reproduce primary bug unfortunately (although I can describe conditions which fired it if anybody get interested). So I report only second one at now.

memp_sanity() algorithm is wrong:

/**
* Check that memp-lists don't form a circle
*/
static int
memp_sanity(void)
{
  s16_t i, c;
  struct memp *m, *n;

  for (i = 0; i < MEMP_MAX; i++) {
    for (m = memp_tab[i]; m != NULL; m = m->next) {
      c = 1;
      for (n = memp_tab[i]; n != NULL; n = n->next) { // <--- endless loop in this cycle
        if (n == m && --c < 0) { // <--- this condition is always false
          return 0;
        }
      }
    }
  }
  return 1;
}

That code detects only case where looped item points to first item (that is 'm') and make '--c' operator to work thanks to passed (n == m) condition. But this is not the only case. Author of this code caught in a trap of tricky and cruel '&&' short-circuit operator ;)

My "circle" was as follows: n->next->next = n.

Artem Pisarenko <jblackarty>

 

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by goldsimon (Posted a comment)
  • -email is unavailable- added by jblackarty (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

     

     

    Follow 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2012-08-22 goldsimon StatusNone => Fixed
        Assigned toNone => goldsimon
        Open/ClosedOpen => Closed

    Back to the top


    Powered by Savane 3.5