classification
Title: asynchat.async_chat.initiate_send : del deque[0] is not safe
Type: behavior Stage:
Components: Library (Lib) Versions: Python 3.3
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: Pierrick.Koch, andy_js, giampaolo.rodola, xdegaye
Priority: normal Keywords: patch

Created on 2013-05-07 13:45 by Pierrick.Koch, last changed 2018-07-11 07:34 by serhiy.storchaka.

Files
File name Uploaded Description Edit
asynchat.async_chat.initiate_send.deldeque.patch Pierrick.Koch, 2013-05-07 13:45
test_initiate_send.py xdegaye, 2013-05-09 19:19
cpython.asyncore.patch Pierrick.Koch, 2013-06-11 13:27 review
cpython.asyncore_2.patch xdegaye, 2013-06-13 10:39 review
cpython.asyncore_3.patch Pierrick.Koch, 2013-06-16 20:54 review
cpython.asyncore_4.patch Pierrick.Koch, 2014-02-04 10:48 review
Messages (17)
msg188652 - (view) Author: Pierrick Koch (Pierrick.Koch) Date: 2013-05-07 13:45
Dear,

del deque[0] is not safe, see the attached patch for the asynchat.async_chat.initiate_send method.
fix the "IndexError: deque index out of range" of "del self.producer_fifo[0]"

Best,
Pierrick Koch
msg188789 - (view) Author: Xavier de Gaye (xdegaye) * (Python triager) Date: 2013-05-09 19:19
The attached script, test_initiate_send.py, tests initiate_send with
threads, causing duplicate writes and an IndexError. This is the
script output using python on the default branch:

$ python test_initiate_send.py
--- Test: duplicate data sent ---
chat.send('thread data')
chat.send('thread data')

--- Test: IndexError ---
chat.send('thread data')
chat.send('thread data')
Exception in thread Thread-2:
Traceback (most recent call last):
  File "Lib/threading.py", line 644, in _bootstrap_inner
    self.run()
  File "Lib/threading.py", line 601, in run
    self._target(*self._args, **self._kwargs)
  File "test_initiate_send.py", line 25, in <lambda>
    thread = threading.Thread(target=lambda : chat.push('thread data'))
  File "Lib/asynchat.py", line 194, in push
    self.initiate_send()
  File "Lib/asynchat.py", line 254, in initiate_send
    del self.producer_fifo[0]
IndexError: deque index out of range


The script does not fail with Pierrick patch:

$ python test_initiate_send.py
--- Test: duplicate data sent ---
chat.send('main data')
chat.send('thread data')

--- Test: IndexError ---
chat.send('thread data')


The patch misses to also appendleft() 'first' when 'num_sent' is zero,
which may happen on getting EWOULDBLOCK on send().
msg190232 - (view) Author: Andrew Stormont (andy_js) Date: 2013-05-28 18:00
Looks like a reasonable fix to me.  What needs to be done to get this integrated?
msg190233 - (view) Author: Giampaolo Rodola' (giampaolo.rodola) * (Python committer) Date: 2013-05-28 18:15
After applying the patch I get these 2 failures on Linux:

======================================================================
FAIL: test_simple_producer (__main__.TestAsynchat)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "Lib/test/test_asynchat.py", line 198, in test_simple_producer
    self.fail("join() timed out")
AssertionError: join() timed out

======================================================================
FAIL: test_simple_producer (__main__.TestAsynchat_WithPoll)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "Lib/test/test_asynchat.py", line 198, in test_simple_producer
    self.fail("join() timed out")
AssertionError: join() timed out
msg190299 - (view) Author: Xavier de Gaye (xdegaye) * (Python triager) Date: 2013-05-29 12:40
The problem is that when the fifo contains a producer and the more()
method of the producer returns a non-empty bytes sequence, then the
producer must be put back in the fifo first. This is what does the
following change made to Pierrick patch:

diff --git a/Lib/asynchat.py b/Lib/asynchat.py
--- a/Lib/asynchat.py
+++ b/Lib/asynchat.py
@@ -229,6 +229,7 @@
             except TypeError:
                 data = first.more()
                 if data:
+                    self.producer_fifo.appendleft(first)
                     self.producer_fifo.appendleft(data)
                 continue

The asynchat test is OK when the patch is modified with the above
change.

However, then the patch does not make initiate_send() thread safe.
There is now a race condition: another thread may be allowed to run
between the two appendleft() calls, this other thread may then call
the more() method of 'first' and send the returned bytes. When that
happens, the sent data is mis-ordered.
msg190300 - (view) Author: Giampaolo Rodola' (giampaolo.rodola) * (Python committer) Date: 2013-05-29 12:44
I think we shouldn't expect asynchat to be thread safe in this regard.
msg190305 - (view) Author: Andrew Stormont (andy_js) Date: 2013-05-29 13:01
What about changing:

self.producer_fifo.appendleft(first)
self.producer_fifo.appendleft(data)

To

self.producer_fifo.extendleft([data, first])

Assuming deque's extendleft is actually thread safe.
msg190318 - (view) Author: Xavier de Gaye (xdegaye) * (Python triager) Date: 2013-05-29 16:40
extendleft is an extension module C function (in the _collections
module) that does not release the GIL, so it is thread safe.
msg190532 - (view) Author: Andrew Stormont (andy_js) Date: 2013-06-03 10:22
Great.  Everybody's happy now, surely?
msg190535 - (view) Author: Giampaolo Rodola' (giampaolo.rodola) * (Python committer) Date: 2013-06-03 10:35
patch plus "self.producer_fifo.extendleft([data, first])" seems legit and I verified pyftpdlib tests pass.
Last thing missing from the patch is a test case. Pierrick can you merge test_initiate_send.py into Lib/test_asynchat.py and provide a new patch?
msg190964 - (view) Author: Pierrick Koch (Pierrick.Koch) Date: 2013-06-11 13:27
sorry for the delay, here is the updated patch,
shall I add a new class in Lib/test/test_asynchat.py ?
msg191071 - (view) Author: Xavier de Gaye (xdegaye) * (Python triager) Date: 2013-06-13 10:39
Attached are two test cases for this patch.

test_simple_producer still fails with the new patch because it should be:

  self.producer_fifo.extendleft([first, data])

instead of:

  self.producer_fifo.appendleft([data, first])

The order of the items in the list is reversed, as documented in
deque.extendleft. So the attachment also includes the corrected patch
with this single change.

I still think  that if num_sent == 0, then 'first' should be put back
in the queue. This means that initiate_send should not attempt anymore
to send an empty string, which is confusing anyway, and therefore at
the beginning of initiate_send, when 'if not first', then we should
return in all cases and not only when 'first' is None.
msg191075 - (view) Author: Andrew Stormont (andy_js) Date: 2013-06-13 10:45
I think you mean:

    self.producer_fifo.extendleft([data, first])

Instead of:

    self.producer_fifo.extendleft([first, data])

No?
msg191288 - (view) Author: Pierrick Koch (Pierrick.Koch) Date: 2013-06-16 20:54
last patch, replaced:

  self.producer_fifo.appendleft([data, first])

by:

  self.producer_fifo.extendleft([data, first])
msg191318 - (view) Author: Xavier de Gaye (xdegaye) * (Python triager) Date: 2013-06-17 07:10
> I think you mean:
>
>     self.producer_fifo.extendleft([data, first])
>
> Instead of:
>
>     self.producer_fifo.extendleft([first, data])
>
> No?


No, I do mean:

     self.producer_fifo.extendleft([first, data])

See the documentation.
Also:

>>> from collections import deque
>>> a = deque([0, 1, 2, 3])
>>> a.extendleft([11, 22])
>>> a
deque([22, 11, 0, 1, 2, 3])
msg191319 - (view) Author: Xavier de Gaye (xdegaye) * (Python triager) Date: 2013-06-17 07:14
After applying the last patch cpython.asyncore_3.patch (while
cpython.asyncore_2.patch does not fail):

======================================================================
FAIL: test_simple_producer (test.test_asynchat.TestAsynchat)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "Lib/test/test_asynchat.py", line 198, in test_simple_producer
    self.fail("join() timed out")
AssertionError: join() timed out

======================================================================
FAIL: test_simple_producer (test.test_asynchat.TestAsynchat_WithPoll)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "Lib/test/test_asynchat.py", line 198, in test_simple_producer
    self.fail("join() timed out")
AssertionError: join() timed out
msg210196 - (view) Author: Pierrick Koch (Pierrick.Koch) Date: 2014-02-04 10:48
Fix patch from Xavier's comment, sorry for the delay.

Lib/test/test_asynchat.py passes (Ran 27 tests in 1.431s)
History
Date User Action Args
2018-07-11 07:34:49serhiy.storchakasettype: crash -> behavior
2014-02-04 10:48:29Pierrick.Kochsetfiles: + cpython.asyncore_4.patch

messages: + msg210196
2013-06-17 07:14:39xdegayesetmessages: + msg191319
2013-06-17 07:10:38xdegayesetmessages: + msg191318
2013-06-16 20:54:44Pierrick.Kochsetfiles: + cpython.asyncore_3.patch

messages: + msg191288
2013-06-13 10:45:21andy_jssetmessages: + msg191075
2013-06-13 10:39:37xdegayesetfiles: + cpython.asyncore_2.patch

messages: + msg191071
2013-06-11 13:27:41Pierrick.Kochsetfiles: + cpython.asyncore.patch

messages: + msg190964
2013-06-03 10:35:32giampaolo.rodolasetmessages: + msg190535
2013-06-03 10:22:56andy_jssetmessages: + msg190532
2013-05-29 16:40:59xdegayesetmessages: + msg190318
2013-05-29 13:01:09andy_jssetmessages: + msg190305
2013-05-29 12:44:30giampaolo.rodolasetmessages: + msg190300
2013-05-29 12:40:25xdegayesetmessages: + msg190299
2013-05-28 18:15:56giampaolo.rodolasetmessages: + msg190233
2013-05-28 18:00:10andy_jssetnosy: + andy_js
messages: + msg190232
2013-05-09 19:19:55xdegayesetfiles: + test_initiate_send.py
nosy: + xdegaye
messages: + msg188789

2013-05-07 15:00:44r.david.murraysetnosy: + giampaolo.rodola
2013-05-07 13:45:56Pierrick.Kochcreate