Memory limit patch

[Denis Kasak]

Hi all,

I've implemented the memory limit for the sandbox. It works, but I
vastly underestimated the number of allocations made in a typical
tinypy instance. I've used linked lists to keep track of
pointers/sizes of blocks allocated and that proved to be a terrible
idea for anything other than trivial programs because the number of
allocations grows wildly and it bogs down fantastically.

The bottlenecks are of course the _tp_linked_append and
_tp_linked_find methods. The former can easily be improved to O(1) by
simply making it append to the beginning of the list instead of the
end since the order doesn't matter (I am perplexed to why I haven't
done it like that prior to talking about it here :) ). The find method
is the single largest bottleneck and since it can't be significantly
improved, I think I'll have to switch to hashed dictionaries. I've
thought about reusing tinypy dictionary code but I don't know what to
hash the pointers to; the straightforward answer (integers) can't be
easily done with tinypy's dicts because tp_obj only supports floats. I
could store them as strings, but that doesn't sound very clean.

Any ideas?

(patch against latest rev of the sandbox branch)

--
Denis Kasak

[Phil Hassey]

Okay .. I think the easiest way to make this simple, memory efficient, and fast would be to change it so your bookkeeping is done within the memory that is allocated.  Like so: tp_calloc(tp, int size) {     int *r = calloc(size+4);     *r = size;     tp->mem_used += size+4;     return r+1; } tp_free(tp,void *ptr) {     int *r = ptr; r--;     tp->mem_used -= *r;     free(r); } -Phil --- On Wed, 7/16/08, Denis Kasak <denis...@gmail.com> wrote:

[Denis Kasak]

On Thu, Jul 17, 2008 at 7:28 AM, Phil Hassey <philh...@yahoo.com> wrote:
> Okay .. I think the easiest way to make this simple, memory efficient, and
> fast would be to change it so your bookkeeping is done within the memory
> that is allocated. Like so:
>
> tp_calloc(tp, int size) {
> int *r = calloc(size+4);
> *r = size;
> tp->mem_used += size+4;
> return r+1;
> }
>
> tp_free(tp,void *ptr) {
> int *r = ptr; r--;
> tp->mem_used -= *r;
> free(r);
> }

Wow... That was so painfully obvious I almost wonder whether I was
drunk while planning it. Thanks.

--
Denis Kasak

[Denis Kasak]

On Thu, Jul 17, 2008 at 7:33 AM, Denis Kasak <denis...@gmail.com> wrote:
> On Thu, Jul 17, 2008 at 7:28 AM, Phil Hassey <philh...@yahoo.com> wrote:
>> Okay .. I think the easiest way to make this simple, memory efficient, and
>> fast would be to change it so your bookkeeping is done within the memory
>> that is allocated. Like so:
>>
>> tp_calloc(tp, int size) {
>> int *r = calloc(size+4);
>> *r = size;
>> tp->mem_used += size+4;
>> return r+1;
>> }
>>
>> tp_free(tp,void *ptr) {
>> int *r = ptr; r--;
>> tp->mem_used -= *r;
>> free(r);
>> }

Okay, here's the updated version; I included a test and it currently
passes all tests in tests.py. It seems to be working so, everyone,
please try to break it.

--
Denis Kasak

[Phil Hassey]

Just curious, but does anyone know if there is a way to do this: void *x = malloc(234); int y = size_of_memory_chunk(x); assert(y==234); I'm guessing there is, but I'm also guessing it's not very cross-platform.  If we could do that, we'd be able to cut out all that book-keeping. Anyone care to comment? -Phil

--- On Fri, 7/18/08, Denis Kasak <denis...@gmail.com> wrote:

[Denis Kasak]

On Fri, Jul 18, 2008 at 11:49 PM, Phil Hassey <philh...@yahoo.com> wrote:
> Just curious, but does anyone know if there is a way to do this:
>
> void *x = malloc(234);
> int y = size_of_memory_chunk(x);
> assert(y==234);
>
> I'm guessing there is, but I'm also guessing it's not very cross-platform.
> If we could do that, we'd be able to cut out all that book-keeping.
>
> Anyone care to comment?

AFAIK, there is no way to do it in the GNU C library and that severely
limits the feasibility of doing it. There is only a mallinfo()
function for some general malloc() usage statistics.

--
Denis Kasak

[Dean Hall]

I read somewhere (long ago) that the size was kept in the word in
memory immediately before the allocated chunk. But I just wrote a
quick test program and disproved that.

I estimate the implementation is stdlib or OS dependent; but most
unices might be simiar. For BSD-accurate info, check this PDF, pg 5,
left column, half way down:
http://phk.freebsd.dk/pubs/malloc.pdf

Summary:
Chunks are bucketed to a power of two. Buckets are ordered (or have
bounds). The address of the chunk can therefore reveal to which
bucket the chunk belongs... and thus its size.

!!Dean

On Jul 18, 2008, at 16:49 , Phil Hassey wrote:

> Just curious, but does anyone know if there is a way to do this:
>
> void *x = malloc(234);
> int y = size_of_memory_chunk(x);
> assert(y==234);
>
> I'm guessing there is, but I'm also guessing it's not very cross-

> platform. If we could do that, we'd be able to cut out all that

[Denis Kasak]

On Sat, Jul 19, 2008 at 10:34 PM, Dean Hall <dwha...@gmail.com> wrote:
>
> I read somewhere (long ago) that the size was kept in the word in
> memory immediately before the allocated chunk. But I just wrote a
> quick test program and disproved that.

Well this is definitely true on some systems (or it was at some
point), but my tests yesterday also show it's not the case with mine.

--
Denis Kasak

[Phil Hassey]

Denis, Can you commit your memory limit to the sandbox and ask people to jailbreak it again?  Give them svn info so people know where to check out your sandbox. Thanks! -Phil

--- On Sat, 7/19/08, Denis Kasak <denis...@gmail.com> wrote:

From: Denis Kasak <denis...@gmail.com> Subject: [tinypy] Re: Memory limit patch To: tin...@googlegroups.com

[Denis Kasak]

On Mon, Jul 21, 2008 at 5:40 PM, Phil Hassey <philh...@yahoo.com> wrote:
> Denis,
>
> Can you commit your memory limit to the sandbox and ask people to jailbreak
> it again? Give them svn info so people know where to check out your
> sandbox.

Sure, it's in.

Everyone, the sandbox branch is at
https://tinypy.googlecode.com/svn/branches/sandbox.
The sandbox() builtin can be used to set up the sandbox from within
tinypy code. It accepts two parameters; the first one is the time
limit in milliseconds and the second is the memory limit in bytes. A
value of 'False' means no limit is being imposed. Please try to break
the sandbox and find bugs.

Hack away. :)

Phil, can I add a count() method to strings? Also, some methods miss
useful optional parameters, e.g. the split() method could use a
parameter specifying a maximum number of splits that can be performed.
I've encountered use cases while writing asm.py where those could have
simplified the code a great deal. How do you feel about those?

--
Denis Kasak

[Phil Hassey]

Denis, You may fix the split method.  Be sure to supply a test case that tests the issue. As for count .. hmn .. in what way would it be useful?  I'm trying to keep the footprint as small as possible, but if there is a very compelling reason (and maybe some other folks really wanted it) we could add that method too. -Phil

--- On Mon, 7/21/08, Denis Kasak <denis...@gmail.com> wrote:

From: Denis Kasak <denis...@gmail.com> Subject: [tinypy] Re: Memory limit patch To: tin...@googlegroups.com

[Phil Hassey]

Hmn, I'm having trouble trying out the sandbox branch: [phil@localhost tinypy-sandbox]$ svn update At revision 85. [phil@localhost tinypy-sandbox]$ python setup.py linux boot # 99407 69293 3757 cd /home/phil/code/tinypy-sandbox/tinypy gcc -std=c89 -Wall -Wc++-compat -g vmmain.c  -lm -o vm In file included from tp.c:5,                  from vmmain.c:2: tp.h:36: error: expected identifier or â(â before â/â token tp.h:36: error: stray â#â in program tp.h:37: error: stray â#â in program tp.h:38: error: stray â#â in program tp.h: In function âtp_numberâ: tp.h:313: error: âTP_NUMBERâ undeclared (first use in this function) tp.h:313: error: (Each undeclared identifier is reported only once tp.h:313: error: for each function it appears in.) tp.h: In function âtp_stringâ: tp.h:332: error: âTP_STRINGâ undeclared (first use in this function) tp.h: In function âtp_string_nâ: tp.h:347: error: âTP_STRINGâ undeclared (first use in this function) In file included from tp.c:6,                  from vmmain.c:2: list.c: In function â_tp_list_copyâ: list.c:69: error: âTP_LISTâ undeclared (first use in this function) list.c: In function âtp_insertâ: list.c:93: error: âTP_NUMBERâ undeclared (first use in this function) list.c: In function âtp_list_ntâ: list.c:110: error: âTP_LISTâ undeclared (first use in this function) list.c: In function âtp_listâ: list.c:116: error: âTP_LISTâ undeclared (first use in this function) In file included from tp.c:7,                  from vmmain.c:2: dict.c: In function âtp_hashâ: dict.c:26: error: âTP_NONEâ undeclared (first use in this function) dict.c:27: error: âTP_NUMBERâ undeclared (first use in this function) dict.c:28: error: âTP_STRINGâ undeclared (first use in this function) dict.c:29: error: âTP_DICTâ undeclared (first use in this function) dict.c:30: error: âTP_LISTâ undeclared (first use in this function) dict.c:34: error: âTP_FNCâ undeclared (first use in this function) dict.c:35: error: âTP_DATAâ undeclared (first use in this function) dict.c: In function â_tp_dict_copyâ: dict.c:129: error: âTP_DICTâ undeclared (first use in this function) dict.c: In function âtp_dictâ: dict.c:172: error: âTP_DICTâ undeclared (first use in this function) In file included from tp.c:8,                  from vmmain.c:2: misc.c: In function âtp_fnc_newâ: misc.c:16: error: âTP_FNCâ undeclared (first use in this function) misc.c: In function âtp_dataâ: misc.c:75: error: âTP_DATAâ undeclared (first use in this function) In file included from tp.c:9,                  from vmmain.c:2: string.c: In function âtp_chrâ: string.c:132: error: âTP_NUMBERâ undeclared (first use in this function) string.c: In function âtp_ordâ: string.c:136: error: âTP_STRINGâ undeclared (first use in this function) string.c: In function âtp_stripâ: string.c:141: error: âTP_STRINGâ undeclared (first use in this function) In file included from tp.c:10,                  from vmmain.c:2: builtins.c: In function âtp_bindâ: builtins.c:18: error: âTP_FNCâ undeclared (first use in this function) builtins.c: In function âtp_copyâ: builtins.c:44: error: âTP_LISTâ undeclared (first use in this function) builtins.c:46: error: âTP_DICTâ undeclared (first use in this function) builtins.c: In function âtp_assertâ: builtins.c:59: error: âTP_NUMBERâ undeclared (first use in this function) builtins.c: In function âtp_rangeâ: builtins.c:68: error: âTP_NUMBERâ undeclared (first use in this function) builtins.c: In function âtp_systemâ: builtins.c:87: error: âTP_STRINGâ undeclared (first use in this function) builtins.c: In function âtp_istypeâ: builtins.c:94: error: âTP_STRINGâ undeclared (first use in this function) builtins.c:96: error: âTP_LISTâ undeclared (first use in this function) builtins.c:97: error: âTP_DICTâ undeclared (first use in this function) builtins.c:98: error: âTP_NUMBERâ undeclared (first use in this function) builtins.c:99: error: âTP_FNCâ undeclared (first use in this function) builtins.c: In function âtp_floatâ: builtins.c:109: error: âTP_NUMBERâ undeclared (first use in this function) builtins.c:110: error: âTP_STRINGâ undeclared (first use in this function) builtins.c: In function âtp_saveâ: builtins.c:119: error: âTP_STRINGâ undeclared (first use in this function) builtins.c: In function âtp_loadâ: builtins.c:134: error: âTP_STRINGâ undeclared (first use in this function) builtins.c: In function âtp_fpackâ: builtins.c:151: error: âTP_NUMBERâ undeclared (first use in this function) builtins.c: In function âtp_existsâ: builtins.c:173: error: âTP_STRINGâ undeclared (first use in this function) builtins.c: In function âtp_mtimeâ: builtins.c:178: error: âTP_STRINGâ undeclared (first use in this function) builtins.c: In function â_tp_lookupâ: builtins.c:190: error: âTP_DICTâ undeclared (first use in this function) builtins.c:191: error: âTP_FNCâ undeclared (first use in this function) builtins.c: In function âtp_setmetaâ: builtins.c:230: error: âTP_DICTâ undeclared (first use in this function) builtins.c: In function âtp_getmetaâ: builtins.c:237: error: âTP_DICTâ undeclared (first use in this function) builtins.c: In function âtp_object_newâ: builtins.c:255: error: âTP_DICTâ undeclared (first use in this function) builtins.c: In function âtp_object_callâ: builtins.c:267: error: âTP_DICTâ undeclared (first use in this function) builtins.c: In function âtp_getrawâ: builtins.c:284: error: âTP_DICTâ undeclared (first use in this function) builtins.c: In function âtp_sandbox_â: builtins.c:305: error: âTP_NUMBERâ undeclared (first use in this function) In file included from tp.c:11,                  from vmmain.c:2: gc.c: In function âtp_greyâ: gc.c:9: error: âTP_STRINGâ undeclared (first use in this function) gc.c:11: error: âTP_DATAâ undeclared (first use in this function) gc.c: In function âtp_followâ: gc.c:20: error: âTP_LISTâ undeclared (first use in this function) gc.c:26: error: âTP_DICTâ undeclared (first use in this function) gc.c:35: error: âTP_FNCâ undeclared (first use in this function) gc.c: In function âtp_deleteâ: gc.c:69: error: âTP_LISTâ undeclared (first use in this function) gc.c:72: error: âTP_DICTâ undeclared (first use in this function) gc.c:75: error: âTP_STRINGâ undeclared (first use in this function) gc.c:78: error: âTP_DATAâ undeclared (first use in this function) gc.c:84: error: âTP_FNCâ undeclared (first use in this function) gc.c: In function âtp_collectâ: gc.c:96: error: âTP_STRINGâ undeclared (first use in this function) gc.c: In function âtp_trackâ: gc.c:137: error: âTP_STRINGâ undeclared (first use in this function) In file included from tp.c:12,                  from vmmain.c:2: ops.c: In function âtp_strâ: ops.c:12: error: âTP_STRINGâ undeclared (first use in this function) ops.c:13: error: âTP_NUMBERâ undeclared (first use in this function) ops.c:17: error: âTP_DICTâ undeclared (first use in this function) ops.c:19: error: âTP_LISTâ undeclared (first use in this function) ops.c:21: error: âTP_NONEâ undeclared (first use in this function) ops.c:23: error: âTP_DATAâ undeclared (first use in this function) ops.c:25: error: âTP_FNCâ undeclared (first use in this function) ops.c: In function âtp_boolâ: ops.c:40: error: âTP_NUMBERâ undeclared (first use in this function) ops.c:41: error: âTP_NONEâ undeclared (first use in this function) ops.c:42: error: âTP_STRINGâ undeclared (first use in this function) ops.c:43: error: âTP_LISTâ undeclared (first use in this function) ops.c:44: error: âTP_DICTâ undeclared (first use in this function) ops.c: In function âtp_hasâ: ops.c:57: error: âTP_DICTâ undeclared (first use in this function) ops.c:60: error: âTP_STRINGâ undeclared (first use in this function) ops.c:63: error: âTP_LISTâ undeclared (first use in this function) ops.c: In function âtp_delâ: ops.c:78: error: âTP_DICTâ undeclared (first use in this function) ops.c: In function âtp_iterâ: ops.c:110: error: âTP_LISTâ undeclared (first use in this function) ops.c:110: error: âTP_STRINGâ undeclared (first use in this function) ops.c:111: error: âTP_DICTâ undeclared (first use in this function) ops.c:111: error: âTP_NUMBERâ undeclared (first use in this function) ops.c: In function âtp_getâ: ops.c:130: error: âTP_DICTâ undeclared (first use in this function) ops.c:136: error: âTP_LISTâ undeclared (first use in this function) ops.c:137: error: âTP_NUMBERâ undeclared (first use in this function) ops.c:142: error: âTP_STRINGâ undeclared (first use in this function) ops.c:159: error: âTP_NONEâ undeclared (first use in this function) ops.c: In function âtp_igetâ: ops.c:219: error: âTP_DICTâ undeclared (first use in this function) ops.c:226: error: âTP_LISTâ undeclared (first use in this function) ops.c: In function âtp_setâ: ops.c:240: error: âTP_DICTâ undeclared (first use in this function) ops.c:247: error: âTP_LISTâ undeclared (first use in this function) ops.c:248: error: âTP_NUMBERâ undeclared (first use in this function) ops.c:251: error: âTP_NONEâ undeclared (first use in this function) ops.c:254: error: âTP_STRINGâ undeclared (first use in this function) ops.c: In function âtp_addâ: ops.c:265: error: âTP_NUMBERâ undeclared (first use in this function) ops.c:267: error: âTP_STRINGâ undeclared (first use in this function) ops.c:273: error: âTP_LISTâ undeclared (first use in this function) ops.c: In function âtp_mulâ: ops.c:285: error: âTP_NUMBERâ undeclared (first use in this function) ops.c:287: error: âTP_STRINGâ undeclared (first use in this function) ops.c: In function âtp_lenâ: ops.c:308: error: âTP_STRINGâ undeclared (first use in this function) ops.c:310: error: âTP_DICTâ undeclared (first use in this function) ops.c:312: error: âTP_LISTâ undeclared (first use in this function) ops.c: In function âtp_cmpâ: ops.c:321: error: âTP_NONEâ undeclared (first use in this function) ops.c:322: error: âTP_NUMBERâ undeclared (first use in this function) ops.c:323: error: âTP_STRINGâ undeclared (first use in this function) ops.c:328: error: âTP_LISTâ undeclared (first use in this function) ops.c:335: error: âTP_DICTâ undeclared (first use in this function) ops.c:336: error: âTP_FNCâ undeclared (first use in this function) ops.c:337: error: âTP_DATAâ undeclared (first use in this function) ops.c: In function âtp_andâ: ops.c:351: error: âTP_NUMBERâ undeclared (first use in this function) ops.c: In function âtp_orâ: ops.c:352: error: âTP_NUMBERâ undeclared (first use in this function) ops.c: In function âtp_modâ: ops.c:353: error: âTP_NUMBERâ undeclared (first use in this function) ops.c: In function âtp_lshâ: ops.c:354: error: âTP_NUMBERâ undeclared (first use in this function) ops.c: In function âtp_rshâ: ops.c:355: error: âTP_NUMBERâ undeclared (first use in this function) ops.c: In function âtp_subâ: ops.c:356: error: âTP_NUMBERâ undeclared (first use in this function) ops.c: In function âtp_divâ: ops.c:357: error: âTP_NUMBERâ undeclared (first use in this function) ops.c: In function âtp_powâ: ops.c:358: error: âTP_NUMBERâ undeclared (first use in this function) In file included from tp.c:13,                  from vmmain.c:2: sandbox.c: In function âtp_mallocâ: sandbox.c:29: warning: request for implicit conversion from âvoid *â to âsize_t *â not permitted in C++ sandbox.c: In function âtp_freeâ: sandbox.c:39: warning: request for implicit conversion from âvoid *â to âsize_t *â not permitted in C++ sandbox.c: In function âtp_reallocâ: sandbox.c:49: warning: request for implicit conversion from âvoid *â to âsize_t *â not permitted in C++ sandbox.c:56: warning: request for implicit conversion from âvoid *â to âsize_t *â not permitted in C++ In file included from tp.c:15,                  from vmmain.c:2: vm.c: In function â_tp_raiseâ: vm.c:85: error: âTP_NONEâ undeclared (first use in this function) vm.c: In function âtp_callâ: vm.c:139: error: âTP_DICTâ undeclared (first use in this function) vm.c:151: error: âTP_FNCâ undeclared (first use in this function) In file included from vmmain.c:2: tp.c: At top level: tp.c:17: error: âTP_NONEâ undeclared here (not in a function) exit_status 256 [phil@localhost tinypy-sandbox]$

--- On Mon, 7/21/08, Denis Kasak <denis...@gmail.com> wrote:

From: Denis Kasak <denis...@gmail.com> Subject: [tinypy] Re: Memory limit patch To: tin...@googlegroups.com Date: Monday, July 21, 2008, 11:28 AM

[Denis Kasak]

On Thu, Jul 24, 2008 at 10:01 PM, Phil Hassey <philh...@yahoo.com> wrote:
> Hmn, I'm having trouble trying out the sandbox branch:

<snip compilation log>

Yes, sorry about that. I think the issue was due to the -Wc++-compat
flag (I didn't cast from void * and such). It should be fixed now but
I don't have a Linux machine with me. Could you try it out now?

Thanks!

--
Denis Kasak

[Jack Palevich]

Pardon me if the following is obvious but...

There's no standard way to do this because malloc() doesn't have to be
implemented in a way that needs to track of the chunk size.

However, if you really want to track the size then it's very easy to
do: just wrap all your calls to malloc and free, and in the wrapper
function allocate an extra sizeof(size_t) bytes, store the size at the
beginning of the chunk, then return the address of the data after the
size block:

void* myMalloc(size_t size) {
size_t* pData = (size_t*) malloc(sizeof(size_t) + size);
*pData = size;
return pData + 1;
}

size_t getSize(void* data) {
return ((size_t*) data)[-1];
}

void myFree(void* data){
free(((size_t*) data) - 1);

}

On Jul 18, 2:49 pm, Phil Hassey <philhas...@yahoo.com> wrote:
> Just curious, but does anyone know if there is a way to do this:
>
> void *x = malloc(234);
> int y = size_of_memory_chunk(x);
> assert(y==234);
>
> I'm guessing there is, but I'm also guessing it's not very cross-platform.  If we could do that, we'd be able to cut out all that book-keeping.
>
> Anyone care to comment?
> -Phil
>

> --- On Fri, 7/18/08, Denis Kasak <denis.ka...@gmail.com> wrote:
> From: Denis Kasak <denis.ka...@gmail.com>

> Subject: [tinypy] Re: Memory limit patch
> To: tin...@googlegroups.com
> Date: Friday, July 18, 2008, 3:43 PM
>

> On Thu, Jul 17, 2008 at 7:33 AM, Denis Kasak <denis.ka...@gmail.com>
> wrote:
>
>
>
> > On Thu, Jul 17, 2008 at 7:28 AM, Phil Hassey <philhas...@yahoo.com>

[Jack Palevich]

D'Oh. I just read the code to the sandbox, and I see you already knew
the "store the size with the object" trick.

OK then, at least I wanted to explain about malloc not having a
standard way of getting the current size.

For example with some implementations of malloc, if you malloc over a
certain size, the memory is allocated directly from the operating
system, which rounds up your allocation to a 4K page boundary. On
free() the code checks to see if the pointer is in the range of the
normal heap, and if it's not it knows to ask the OS to free it.

Other systems use "buddy heaps", where every allocation is rounded up

to a power of two.

Other heaps use an affinity system where all allocations of a given
size are packed into the same page.

And at least on Windows it's very common for applications to have
their own heaps, rather than using the standard C runtime.

So I think you're out of luck with regards to a universal "how big is
this allocation" function.

[Phil Hassey]

Denis, That appears to have fixed the warnings.  I'm noticing now that a run of valgrind over the sandbox tinypy has a number of uninitialized value conditions.  When you get your linux stuff going again, check this out.  -Phil

--- On Thu, 7/24/08, Denis Kasak <denis...@gmail.com> wrote:

From: Denis Kasak <denis...@gmail.com> Subject: [tinypy] Re: Memory limit patch To: tin...@googlegroups.com