[Python-Dev] Riskless deletion of nested structures

[Christian Tismer]

This is a multi-part message in MIME format.
--------------D9F780CECED602EF245D7526
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit

Howdy,

Please review!

While implementing Stackless Python, a new problem arose:
Nested structures like frame chains and tracebacks can now
easily grow somuch that they cause a stack overflow on deallocation.

To protect lists, tuples, frames, dicts and tracebacks against
this, I wrote a stackless deallocator.
At the moment, everything is done in trashcan.c .
This gives a slight performance loss of 5% for pystone, most probably
due to the double indirection and non-local code reference.
It is yet a hack, since I'm grabbing the tp->dealloc pointers of these
types and replace them by safe versions. This just in order to
try out things quickly. Later I will change this and incorporate
the stack checks into the affected modules, after I got some
feedback on this.

This patch applies to Stackless and standard Python as well:
Deallocation of deeply nested structures will never again cause
a stack overflow.

Installation for the intermediate version:
Insert a line

	_Py_trashcan_install();

at the end of Py_Initialize in pythonrun.c

Please try it and check my code wether there is a better solution.

cheers - chris

-- 
Christian Tismer             :^)   <mailto:tismer@appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Düppelstr. 31                :    *Starship* http://starship.python.net
12163 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     we're tired of banana software - shipped green, ripens at home
--------------D9F780CECED602EF245D7526
Content-Type: application/x-unknown-content-type-cfile;
 name="trashcan.c"
Content-Transfer-Encoding: base64
Content-Disposition: inline;
 filename="trashcan.c"

LyoNCiAgdHJhc2hjYW4NCiAgQ1QgMmswMTMwDQogIG5vbi1yZWN1cnNpdmVseSBkZXN0cm95
IG5lc3RlZCBvYmplY3RzDQoqLw0KDQojaW5jbHVkZSAiUHl0aG9uLmgiDQojaW5jbHVkZSAi
Y29tcGlsZS5oIg0KI2luY2x1ZGUgImZyYW1lb2JqZWN0LmgiDQojaW5jbHVkZSAidHJhY2Vi
YWNrLmgiDQoNCiNpbmNsdWRlICJ0cmFzaGNhbi5oIg0KDQpzdGF0aWMgUHlPYmplY3QgKiBk
ZWxldGVfbGF0ZXIgPSBOVUxMOw0Kc3RhdGljIGludCBkZWxldGVfbmVzdGluZyA9IDA7DQoN
CiNkZWZpbmUgVU5XSU5EX0xFVkVMIDUwDQoNCnZvaWQgc2FmZV9kZWxldGUob2IsIGRlc3Ry
KQ0KCVB5T2JqZWN0ICogb2I7DQoJZGVzdHJ1Y3RvciBkZXN0cjsNCnsNCgkrK2RlbGV0ZV9u
ZXN0aW5nOw0KCWlmIChkZWxldGVfbmVzdGluZyA8IFVOV0lORF9MRVZFTCkgew0KCQlkZXN0
cihvYik7DQoJfQ0KCWVsc2Ugew0KCQlpZiAoIWRlbGV0ZV9sYXRlcikNCgkJCWRlbGV0ZV9s
YXRlciA9IFB5TGlzdF9OZXcoMCk7DQoJCWlmIChkZWxldGVfbGF0ZXIpIHsNCgkJCVB5TGlz
dF9BcHBlbmQoZGVsZXRlX2xhdGVyLCBvYik7DQoJCX0NCgl9DQoJLS1kZWxldGVfbmVzdGlu
ZzsNCgl3aGlsZSAoZGVsZXRlX25lc3RpbmcgPT0gMCAmJiBkZWxldGVfbGF0ZXIpIHsNCgkJ
LyogcGljayB0by1kbyBsaXN0IGFuZCB0cnkgdG8gZXZpY3QgaXQgKi8NCgkJUHlPYmplY3Qg
KiBzaHJlZGRlciA9IGRlbGV0ZV9sYXRlcjsNCgkJZGVsZXRlX2xhdGVyID0gTlVMTDsNCgkJ
KytkZWxldGVfbmVzdGluZzsNCgkJUHlfREVDUkVGKHNocmVkZGVyKTsNCgkJLS1kZWxldGVf
bmVzdGluZzsNCgl9DQp9DQoNCnN0YXRpYyBkZXN0cnVjdG9yIGxpc3RfZGVhbGxvY19vcmln
ID0gTlVMTDsNCg0Kc3RhdGljIHZvaWQgbGlzdF9kZWFsbG9jX3NhZmUob2IpDQoJUHlPYmpl
Y3QgKiBvYjsNCnsNCglzYWZlX2RlbGV0ZShvYiwgbGlzdF9kZWFsbG9jX29yaWcpOw0KfQ0K
DQpzdGF0aWMgZGVzdHJ1Y3RvciB0dXBsZV9kZWFsbG9jX29yaWcgPSBOVUxMOw0KDQpzdGF0
aWMgdm9pZCB0dXBsZV9kZWFsbG9jX3NhZmUob2IpDQoJUHlPYmplY3QgKiBvYjsNCnsNCglz
YWZlX2RlbGV0ZShvYiwgdHVwbGVfZGVhbGxvY19vcmlnKTsNCn0NCg0Kc3RhdGljIGRlc3Ry
dWN0b3IgZGljdF9kZWFsbG9jX29yaWcgPSBOVUxMOw0KDQpzdGF0aWMgdm9pZCBkaWN0X2Rl
YWxsb2Nfc2FmZShvYikNCglQeU9iamVjdCAqIG9iOw0Kew0KCXNhZmVfZGVsZXRlKG9iLCBk
aWN0X2RlYWxsb2Nfb3JpZyk7DQp9DQoNCnN0YXRpYyBkZXN0cnVjdG9yIGZyYW1lX2RlYWxs
b2Nfb3JpZyA9IE5VTEw7DQoNCnN0YXRpYyB2b2lkIGZyYW1lX2RlYWxsb2Nfc2FmZShvYikN
CglQeU9iamVjdCAqIG9iOw0Kew0KCXNhZmVfZGVsZXRlKG9iLCBmcmFtZV9kZWFsbG9jX29y
aWcpOw0KfQ0KDQpzdGF0aWMgZGVzdHJ1Y3RvciB0cmFjZWJhY2tfZGVhbGxvY19vcmlnID0g
TlVMTDsNCg0Kc3RhdGljIHZvaWQgdHJhY2ViYWNrX2RlYWxsb2Nfc2FmZShvYikNCglQeU9i
amVjdCAqIG9iOw0Kew0KCXNhZmVfZGVsZXRlKG9iLCB0cmFjZWJhY2tfZGVhbGxvY19vcmln
KTsNCn0NCg0KDQpzdGF0aWMgaW50IHRyYXNoY2FuX2luc3RhbGxlZCA9IDA7DQoNCnZvaWQg
X1B5X3RyYXNoY2FuX2luc3RhbGwoKQ0Kew0KCWlmICh0cmFzaGNhbl9pbnN0YWxsZWQpIHJl
dHVybjsNCg0KCWxpc3RfZGVhbGxvY19vcmlnID0gUHlMaXN0X1R5cGUudHBfZGVhbGxvYzsN
CglQeUxpc3RfVHlwZS50cF9kZWFsbG9jID0gbGlzdF9kZWFsbG9jX3NhZmU7DQoNCgl0dXBs
ZV9kZWFsbG9jX29yaWcgPSBQeVR1cGxlX1R5cGUudHBfZGVhbGxvYzsNCglQeVR1cGxlX1R5
cGUudHBfZGVhbGxvYyA9IHR1cGxlX2RlYWxsb2Nfc2FmZTsNCg0KCWRpY3RfZGVhbGxvY19v
cmlnID0gUHlEaWN0X1R5cGUudHBfZGVhbGxvYzsNCglQeURpY3RfVHlwZS50cF9kZWFsbG9j
ID0gZGljdF9kZWFsbG9jX3NhZmU7DQoNCglmcmFtZV9kZWFsbG9jX29yaWcgPSBQeUZyYW1l
X1R5cGUudHBfZGVhbGxvYzsNCglQeUZyYW1lX1R5cGUudHBfZGVhbGxvYyA9IGZyYW1lX2Rl
YWxsb2Nfc2FmZTsNCg0KCXRyYWNlYmFja19kZWFsbG9jX29yaWcgPSBQeVRyYWNlQmFja19U
eXBlLnRwX2RlYWxsb2M7DQoJUHlUcmFjZUJhY2tfVHlwZS50cF9kZWFsbG9jID0gdHJhY2Vi
YWNrX2RlYWxsb2Nfc2FmZTsNCg0KCXRyYXNoY2FuX2luc3RhbGxlZCA9IDE7DQp9DQo=
--------------D9F780CECED602EF245D7526
Content-Type: application/x-unknown-content-type-hfile;
 name="trashcan.h"
Content-Transfer-Encoding: base64
Content-Disposition: inline;
 filename="trashcan.h"

I2lmbmRlZiBQeV9UUkFTSENBTl9IDQojZGVmaW5lIFB5X1RSQVNIQ0FOX0gNCiNpZmRlZiBf
X2NwbHVzcGx1cw0KZXh0ZXJuICJDIiB7DQojZW5kaWYNCi8qDQogIHRyYXNoY2FuDQogIENU
IDJrMDEzMA0KICBub24tcmVjdXJzaXZlbHkgZGVzdHJveSBuZXN0ZWQgb2JqZWN0cw0KKi8N
Cg0KRExfSU1QT1JUKHZvaWQpIF9QeV90cmFzaGNhbl9pbnN0YWxsIFB5X1BST1RPKCgpKTsN
Cg0KI2VuZGlmIC8qICFQeV9UUkFTSENBTl9IICov
--------------D9F780CECED602EF245D7526--