buglwIP - A Lightweight TCP/IP stack - Bugs: bug #19167, tcp timeout handler can cause...

 
 

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

bug #19167: tcp timeout handler can cause crash being invoked by sys_sem_wait()

Submitted by:  Dmitry Potapov <dpotapov>
Submitted on:  Wed 28 Feb 2007 12:20:46 AM UTC  
 
Category:  TCP Severity:  3 - Normal
Item Group:  Crash Error Status:  Fixed
Privacy:  Public Assigned to:  Simon Goldschmidt <goldsimon>
Open/Closed:  Closed Planned Release:  None
lwIP version:  None

( Jump to the original submission)

Wed 16 May 2007 11:02:52 AM UTC, comment #33: 

OK, checked that in and closing as fixed.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 16 May 2007 09:29:19 AM UTC, comment #32: 

Ok, seems good for me...

Frédéric Bernon <fbernon>
Project Member
Wed 16 May 2007 09:27:15 AM UTC, comment #31: 

>So, to be sure, you use your patch file #12142 ?


No, since at least on file in CVS relies on timeouts with sys_sem_wait (and dmitry seems, too, so other might also).

>You just change memp.c ?


I would
- remove all semaphores from memp.c. Primarily since that is the opposite pf what pbuf.c does, but with the nice side-effect of also solving this bug.
- change mem.c to call sys_arch_sem_wait instead of sys_sem_wait to prevent timeouts running in a state they shouldn't

The rest of the sys_sem_wait calls are in src/api and are called in application context. What the 'user' does here is not our problem.

OK?

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 16 May 2007 09:16:01 AM UTC, comment #30: 

So, to be sure, you use your patch file #12142 ? You just change memp.c ?

Frédéric Bernon <fbernon>
Project Member
Wed 16 May 2007 09:10:27 AM UTC, comment #29: 

From your description, that seems like a good idea, but I haven't looked into it in any more detail than that!

Kieran Mansley <kieranm>
Project Member
Wed 16 May 2007 07:43:11 AM UTC, comment #28: 

I already proposed this in another thread, but it belongs here:
The original reason for this bug entry was that tcp timeout handler is invoked while waiting for the heap (or memp) semaphore.

I propose to change all sys_sem_wait(sem) calls in mem.c to sys_arch_sem_wait(sem, 0) nad to remove the SYS_LIFHGWEIGHT_PROT=0 code in memp.c, which solves this bug.

If noone objects, I'll commit it soon as there does not seem too much activity around these things any more ;-)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Thu 12 Apr 2007 09:03:50 AM UTC, comment #27: 

Regarding the timestamps: I just realized there is a function sys_jiffies() (defined in sys.h, should be included in sys_arch.c), which is extgensively used in PPP.

So lwIP already needs a tick count or timer of some sort (if only for PPP). Introducing timestamps for timeouts only should add a function like jiffies_to_ms() to work (and the implementation of sys_jiffies() for those who don't have it now).

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Fri 09 Mar 2007 08:15:39 AM UTC, comment #26: 

OK, I'll work on this offline, or should I try to create a new CVS branch? Never worked with that, though. I only know SVN...

Anyway, I think this bug should be postponed as it seems to be a direct result from bug #1902 (5 years and noone has done anything about it ... :)

I'll post a comment there.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 07 Mar 2007 01:10:35 PM UTC, comment #25: 

Thanks for working on this, and good to see patches coming forward.

Could you hold off applying this to the main tree until we have a complete solution?  Or at least until it has been well tested and there is some consensus.  I agree that working in stages is good, but don't want to prevent progress in other areas if this creates as many problems as it solves.

Kieran Mansley <kieranm>
Project Member
Wed 07 Mar 2007 12:45:35 PM UTC, comment #24: 

I think it is better to define them as macros

#define sys_sem_wait(sem) ((void)sys_arch_sem_wait((sem), 0))
#define sys_sem_wait_timeout(sem, timeout) \
       (sys_arch_sem_wait((sem),(timeout))!=SYS_ARCH_TIMEOUT)

So we avoid call overhead.

But it is not completely solution, because it will increase delays in timeout handling until sys_mbox_fetch is changed to use 'expires' as I suggested before... But let's do one step a time...

Dmitry Potapov <dpotapov>
Wed 07 Mar 2007 12:12:26 PM UTC, comment #23: 

Sorry for the mess: I simply forgot the return value in sys_sem_wait_timeout().
Shame on me...

The reason why I posted this is I want to solve this in two stages:
1. I think we need to get rid of timeouts on semaphores.
2. After that we can think some more about those timestamps.

I'm aware that my solution does not measure the time it waited for the sem and thus leads to more inaccurate timeouts on mboxes. But that's the problem of not having timestamps...

So here's what I think of as a complete patch (and please ignore file #12141)

(file #12142)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 07 Mar 2007 11:45:31 AM UTC, comment #22: 

Here comes the patch. It completely removes timeout timer handling from semaphores. As a result of this, sys_sem_wait() and sys_sem_wait_timeout() basicly become direct calls to sys_arch_sem_wait().

lwip_users who are interested: PLEASE TEST THIS!!!! Any feedback is welcome!

(file #12141)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 05 Mar 2007 12:59:38 PM UTC, comment #21: 

Send me the patch and I'll do some black box type testing on it.

Thomas Taranowski <taranowski>
Project Member
Mon 05 Mar 2007 12:05:14 PM UTC, comment #20: 

Sorry - didn't mean to stop you progressing on this, just wanted to let you know where I stood, and to ask that you take particular care on this one!

Kieran Mansley <kieranm>
Project Member
Mon 05 Mar 2007 11:59:52 AM UTC, comment #19: 

So what do we do?
I thought I'd test this for a while and check it in for others to test if it seems stable to me. Of course I will have to look closely at the code to see if this change would crash something else.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Mon 05 Mar 2007 11:52:24 AM UTC, comment #18: 

I haven't had time to follow this discussion yet, sorry, but a fairly fundamental change such as this will need some careful thought and testing before going in.  I agree that something needs to be done, but at the moment I'm not sure what the something is.

Kieran Mansley <kieranm>
Project Member
Mon 05 Mar 2007 11:43:35 AM UTC, comment #17: 

If the other developers don't mind, I'll take a look at this. I think lwip-users summarized it to taking timers (aka timeouts) off the semaphores, so that timeouts only can occur when waiting for an mbox.
This behaviour would be good with me.

Although it's no problem for me (I don't use semaphores in tcpip_thread context since I don't use a heap and I have SYS_LIGHTWEIGHT_PROT=1), I would like to see this fixed and think the current implementation is bad behaviour.

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Thu 01 Mar 2007 01:34:24 PM UTC, comment #16: 

Yes, I assumed that timeout must be less than MAX_VALUE(timediff_t) , i.e. in our case. it is about 24 days. I am sorry that I did not state that explicitly.

Dmitry Potapov <dpotapov>
Thu 01 Mar 2007 01:26:01 PM UTC, comment #15: 

Sorry for posting again, but I just found out that it seems to work if the maximum timeout is 0x7fffffff (e.g. MAX_VALUE(timediff_t))

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Thu 01 Mar 2007 01:21:23 PM UTC, comment #14: 

Hi Dimitry,

regarding comment #8:

Please correct me if I'm wrong, but I tested your TIMESTAMP_DIFF() / TIMESTAMP_ADD() suggestion, and I don't think it's a solution:

let's say time_now is 20 (=ms after time counting started) and we have a timeout which is 4294967286 ms (e.g. nearly 50 days; I know it's unlikely, but it's to show the wraparound).

If we now check like you proposed:
if(TIMESTAMP_DIFF(expires, now) > 0)
  wait()
else
  execute_timeout_handler_now()

we would execute the timeout handler, since (signed)(4294967286 - 20) = -10

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Thu 01 Mar 2007 01:11:28 PM UTC, comment #13: 

I have prepared a new patch that fixes both timeout handling and removes timeouts handling from sys_sem_wait.
I placed old code with timeout handling sys_sem_wait under #if 0, without actually removing. The patch needs more testing.

(file #12081)

Dmitry Potapov <dpotapov>
Thu 01 Mar 2007 11:32:13 AM UTC, comment #12: 

Timer overflow:
~~~~~~~~~~~~~~
I think practically all systems have some function that returns of number of ticks, and this function always overflow correctly.

The problem is to convert ticks to milliseconds. In some case, the converation is very straightforward, like:
msecs = ticks * N;
(for many systems N will be 10).
And this will work correctly with overflow.

However, on some systems, you need to something more complex:
msecs = ticks * M / N;
In general, it will not work correctly with 32-bits. So you need to write:
msecs = (u32_t)(((u64_t)ticks) * M / N);
because it is inside of sys_arch_time_now(), it is usually not a problem.

However, the code above will not work if a tick less than 1ms or if the timer counter wraps earlier than 49.71 days (e.g., the original tick counter is 16-bit). So there is an alternative solution, which always works and does not require 64-bit operation:

static u32_t remembered_ticks, remembered_ms;
u32_t sys_arch_time_now(void)
{      
        u32_t now, now_ms;
        u32_t delta, delta_ms;
        now = get_ticks();              /* get get_ticks wraps correctly */
        SYS_ARCH_DECL_PROTECT(lev);
        SYS_ARCH_PROTECT(lev);
        delta = now - remembered_ticks; /* so delta is always correct */
        remembered_ticks = now;
        delta_ms = delta * M / N;
        now_ms = remembered_ms + delta_ms;
        remembered_ms = now_ms;
        SYS_ARCH_UNPROTECT(lev);
        return now_ms;
}      
The botton line, sys_arch_time_now() can be implemented for any platform, but the most straightforward approach (ticks*M/N) does not always work.

To #11: I fully support removing timeouts from sys_sem_wait. I think only that it would be better to fix timeout handling first.

Dmitry Potapov <dpotapov>
Thu 01 Mar 2007 09:13:16 AM UTC, comment #11: 

what do you think about removing timeouts from sys_sem_wait?

Andreas Becker <andreas_becker>
Thu 01 Mar 2007 09:12:07 AM UTC, comment #10: 

Hi Dimitry,

not bad, a real good analysis.

Comment 8: My fault, I thought there is a problem to execute a timeout in history. But there is no problem. So I do not prefere the old timeout handling.

Timer overflow: Is wraping around the maximum a problem in other systems? If this is a Problem we both going into trouble. Your expire code will also work with 16bit integer, but than the longest timeout is less than an hour.

Timefeeling: The problem in the older solutions is, that we have an jitter in execution time. All Timers are allways executed to late and the error of the absolute execution time grows. Between two execution times it is constant. Both of our solutions will handle this. So this behavior will be removed.

Comment 9: Inserting a new timeout handler has to be calculated from timeouts->remember. So this schould work more correct.

Timeroverflow 2: I know why it is better, to use old timeout handling (time- differences) than expired time. My solution does not realy count on a correct systimer-wrapp. I use the type sys_arch_timestamp_t as an system depended timeout and then only use the macro SYS_ARCH_TIMESTAMP_DIFF as an implementatin specific (function) to calculate the time difference of two sys_arch_timestamp_t's. It is not my problem, if the specific implementations uses an 24bit timestamp. I only want to know the difference.

Andreas Becker <andreas_becker>
Wed 28 Feb 2007 10:39:59 PM UTC, comment #9: 

Another problem Andreas Becker's proposal is that timeout handler can  be invoked before the actual timeout expired. Here is what happens:
1. call to sys_mbox_fetch(), which remebers the current in timeouts->remember
2. get blocked ona  semaphore or by sys_msleep()
3. do some job and add insert a new timeout handler
4. call to sys_mbox_fetch() again

In this case, timeout will be measured incorrectly from the moment #1. which may be significantly earlier than #3 and as result the timeout will be expired much earlier than it should.

So, it seems, the only reliable solution is to use 'expires' timestamp in the timeout queue.

Dmitry Potapov <dpotapov>
Wed 28 Feb 2007 08:56:35 PM UTC, comment #8: 

Hi Andreas,

I believe that your solution still has the problem with "timefeeling". If the thread is blocked inside of a timeout handler  than this time does not count. It is possible to fix that, but you still have small races where being pre-empted by another thread means delay of all times. So it is not perfect.

On the other hand, your approach has the same problem with overflow as with storing 'expires', i.e. it requires sys_time_now() to be wrapped correctly over the maximum.

So, I don't understand why you prefer old timeout handling over storing 'expires' timestamp, which is more simple and reliable?

Dmitry Potapov <dpotapov>
Wed 28 Feb 2007 08:01:14 PM UTC, comment #7: 

Hi,

I prepared my own patch. It removes all timeout handling in the function sys_sem_wait(). These function is now only blocking.

All timers ar executed, at the sys_mbox_fetch() call.
If we start to handle a message from the Queue, we remember this timestamp. After messagehandling, we just calc the runtime and pehaps execute some more timer.

Problem:
No more Timers are executed, while waiting for a semaphore. Pehaps sombody (e.g. me) has to revisit his own code for lines like:
sys_timout(_timeout_post_sema, 500)
sys_sem_wait(my sema);  // Wait for 500 ms

And use the function sys_sem_wait_timeout()

I think with this solution, no more timers are executed, while waiting for semaphores and waiting for Semaphores will be much faster.
Do you agree?

(file #12063, file #12064, file #12065)

Andreas Becker <andreas_becker>
Wed 28 Feb 2007 03:32:40 PM UTC, comment #6: 

I have prepared a patch that replaces 'time' in timeouts with 'expires' (see attachment). It is very simple and the actual size of code has been reduced.

(file #12061)

Dmitry Potapov <dpotapov>
Wed 28 Feb 2007 03:05:55 PM UTC, comment #5: 

Sorry for my word time-stamp. I don't want to use absolute timeouts, because it will be hard to handle if the systime is later than ->expires. Blocked for a (long) time...

I would prefer to keep the old timeout handling. Only to know how long a task was running.

typedef u32_t timestamp_t;
#define TIMESTAMP_DIFF(t1, t2) ((timestamp_t)((t1) - (t2)))
/* No problem with timer overrun, if executed every INT32U_MAX/2 -> ca. 24days @1ms timertick*/

timeouts = sys_arch_timeouts();

timestamp_t diff = TIMESTAMP_DIFF(sys_time_now(), timeouts->remember)

:again

  if (!timeouts || !timeouts->next) {
    sys_arch_mbox_fetch(mbox, msg, 0);
  } else {
    /* ANDREAS -> execute old pending timeouts */
    if (timeouts->next->time > diff) {
      diff -= timeouts->next->time;
      time = SYS_ARCH_TIMEOUT;
    } else {
      timeouts->next->time -= diff;
      time = sys_arch_mbox_fetch(mbox, msg, timeouts->next->time);
    }
  }

  if (time == SYS_ARCH_TIMEOUT) {
    /* Do the timer_Handler stuff */
    --> see sys_mbox_fetch()
  } else {
   timeouts->remember = sys_time_now();
   /* No more stuff like timeouts->next->time ... needed */
  }

Andreas Becker <andreas_becker>
Wed 28 Feb 2007 11:45:19 AM UTC, comment #4: 

Using of timestamps instead of time-delta does NOT require 64-bit.

/* timestamp_t value in milliseconds taken by module 2^32,
   so after 0xFFFFFFFF should be 0. */
typedef u32_t timestamp_t;
typedef s32_t timediff_t;

Now we need to define TIMESTAMP_DIFF macro that calculates the difference between two timestamp_t values taken into account overflow and return it as timediff_t, and TIMESTAMP_ADD which adds some timeout value to the given timestamp.

Practically all modern processors use two's complement to represent signed integers. So you can define them as

#define TIMESTAMP_DIFF(t1, t2) ((timediff_t)((t1) - (t2)))
#define TIMESTAMP_ADD(timestamp, timeout) \
 ((timestamp_t)((timestamp)+(timeout)))

then you can write

timediff_t timeout = TIMESTAMP_DIFF(timeouts->next->expires, sys_time_now());
if (timeout > 0)
        sys_arch_mbox_fetch(mbox, msg, timeout)
else
        timeout_handler();

Dmitry Potapov <dpotapov>
Wed 28 Feb 2007 10:56:50 AM UTC, comment #3: 

Executing timeouts only from queues might solve the problem, but it would be more clear if you could tell the code when you are in a state where you can execute timeouts.

Using timestamps would be my favourite implementation of timeouts. On sys_timeout(), you would have to calculate the (absolute) timestamp when this timeout expires (e.g. 'timeout->expires = sys_time_now()' instead of 'timeout->time = msecs'). Later, in sys_mbox_fetch(), you do something like

sys_arch_mbox_fetch(mbox, msg, timeouts->next->expires - sys_time_now())

2 downsides of this approach:
- the system has to be time-aware (but it also has to be so, now)
- to prevent time overflow over long time periods, this time would have to be 64-bit... (as we might have to count in miliseconds, 32-bit would overflow in ~50 days)

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 28 Feb 2007 10:35:13 AM UTC, comment #2: 

Hi all,

I know this Problem. Let me suggest an more ... "complete" solution...
Lwip uses this semaphore and queue functions to get something like a "timefeeling". The "timefeeling" is an soft timeout, that tells you something like "The time is over", not the real correct value. The consequence of this is, that (under heavy load) the timer will fire later than we expect -> e.g. 500ms to 520ms but that's not a real problem.

suggestion: remove ALL timeouts from semaphores, only use queues for timeouts. Than the invoked timer will only called, if an thread is in a suitable situation for executing Timers. This gives us new style semaphores, which only know blocking operations.
new problem: we will loose much more of our time-correctness. the "timefeeling" would be much worser than now. A lot of time will be taken by the run-time of a thread, which sometimes has to (blocking-) wait for other semaphores (new style).
MY solution is to remember the time(-stamp) where we continue a thread from a queue (message or timeout). On the next time, where we wait for a new message, we have to decrement the timeout-timer with the difference of the actual time(-stamp) and the remembered time(-stamp). Posible execute some timeouts and then wait for the next timeout or queue-message.
A other advantage of this is, that the sys_sem_wait functions will run much faster, because there is much lesser code to execute.

Andreas Becker <andreas_becker>
Wed 28 Feb 2007 08:15:03 AM UTC, comment #1: 

Seems like SYS_LIGHTWEIGHT_PROT == 0 does some strange things not only in pbuf.c (patch #5453) ...

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
Wed 28 Feb 2007 12:20:46 AM UTC, original submission:  

lwIP core is not re-entrable, so it is used inside one devoted thread. However, it uses memory allocation functions:

mem_free, mem_realloc,  mem_malloc, mem_malloc, memp_malloc, memp_free

Because these functions can be called from different threads, they are protected by a semaphore (when SYS_LIGHTWEIGHT_PROT is 0). The implementation of these functions uses sys_sem_wait() to acquire the lock. sys_sem_wait() is built on the top of sys_arch_sem_wait, but, in addition to the latter, it can invoke timeout handlers!

These memory functions are called from too many functions to have the full of list, but here are some of most commonly used:

pbuf_alloc, pbuf_realloc, pbuf_free, raw_remove, raw_new, sys_timeout, sys_untimeout, tcp_seg_free, ...

Thus inside of any of those functions, timeout handler can be invoked.

tcpip_tcp_timer (one of functions invoked on timeout) performs many different operations. Here is some functions that can be called during its work:

tcpip_tcp_timer
 tcp_tmr
   tcp_fasttmr
     tcp_ack_now
       forevery pcb in tcp_active_pcbs
          tcp_output
   tcp_slowtmr acts on all tcp_active_pcbs
      forevery pcb in tcp_active_pcbs
      {
        tcp_rexmit_rto
          tcp_output
        tcp_abort
          tcp_segs_free
        tcp_keepalive
        tcp_output
        tcp_pcb_purge
          tcp_segs_free
      }

Basically, any pcb in the tcp_active_pcbs can change its status and some lists are freed, etc... Because, this timeout handler can be invoked in too many places and too many cases, it is not humanly possible to analyze all consequences of timeout handler being invoked at unsuitable time. So, I will give only one example:

In the tcp_process() in tcp_in.c, you can see the following lines:
      tcp_pcb_purge(pcb);
      TCP_RMV(&tcp_active_pcbs, pcb);

Obviously, that pcb is inside of the tcp_active_pcbs when tcp_pcb_purge is called. Now tcp_pcb_purge() calls to tcp_segs_free(), which calls to tcp_seg_free(), which calls to memp_free(), which can invoke timeout handler, which can call tcp_pcb_purge for the same pcb, which results that the same memory is freed twice, which means memory corruption.

Solution:
~~~~~~~~~
Replace all calls to sys_sem_wait(mutex) inside of memp.c with sys_arch_sem_wait(mutex,0), so no timeout handler can be invoked.

I believe, the same thing should be done with sys_sem_wait(mem_sem) in mem.c

Dmitry Potapov <dpotapov>

 

Attached Files
file #12142:  sys.c.patch added by goldsimon (3KiB - application/octet-stream)
file #12141:  sys.c.patch added by goldsimon (3KiB - application/octet-stream)
file #12081:  timeout-hanlder-fix.patch added by dpotapov (8KiB - text/x-patch)
file #12061:  timeouts.expires.patch added by dpotapov (7KiB - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by fbernon (Posted a comment)
  • -email is unavailable- added by taranowski (Posted a comment)
  • -email is unavailable- added by kieranm (Posted a comment)
  • -email is unavailable- added by andreas_becker (Posted a comment)
  • -email is unavailable- added by goldsimon (Posted a comment)
  • -email is unavailable- added by dpotapov (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 13 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2007-05-16 goldsimon StatusPostponed => Fixed
        Open/ClosedOpen => Closed
    2007-03-09 goldsimon StatusIn Progress => Postponed
    2007-03-07 goldsimon Attached File- => Added sys.c.patch, #12142
    2007-03-07 goldsimon Attached File- => Added sys.c.patch, #12141
        Carbon-Copy- => Added lwip_users@nongnu.org
    2007-03-05 goldsimon StatusNone => In Progress
        Assigned toNone => goldsimon
    2007-03-01 dpotapov Attached File- => Added timeout-hanlder-fix.patch, #12081
    2007-02-28 andreas_becker Attached File- => Added sys_sem_no_timeouts.sys_arch.h.patch, #12063
        Attached File- => Added sys_sem_no_timeouts.sys.h.patch, #12064
        Attached File- => Added sys_sem_no_timeouts.sys.c.patch, #12065
    2007-02-28 dpotapov Attached File- => Added timeouts.expires.patch, #12061

    Back to the top


    Powered by Savane 3.5