Measuring memory usage

[zaphod_sof]

Hi!

Hoes does online judge measure memory usage? I know CPU time can be measured on Linux with getrusage(2) or wait3(2), but these syscalls don't give me too much information about used memory.
I found that memory usage for a running process is written in /proc//status, but after the process terminates, i.e. becomes zombie, this is useless.

Thanks.

[Adrian_Kosowski]

Hi,

How does online judge measure memory usage?

Please take a look at:
spoj.sphere.pl/forum/viewtopic.p ... mory+usage
spoj.sphere.pl/forum/viewtopic.p ... mory+usage
The essence of BSD process accounting is in fact similar to regular polling of /proc. The use of RLIMITs serves as an additional, deterministically reliable restriction.

[zaphod_sof]

Hi,
Please take a look at:
spoj.sphere.pl/forum/viewtopic.p ... mory+usage
spoj.sphere.pl/forum/viewtopic.p ... mory+usage
The essence of BSD process accounting is in fact similar to regular polling of /proc. The use of RLIMITs serves as an additional, deterministically reliable restriction.

Thanks a lot! That's what I wanted to know. I'll google BSD process accounting little more...

[zaphod_sof]

I played a little with GNU accounting tools and encountered a few problems.

* I ran a simple Hello World program and sa reported that it used ~300k of memory. After I compiled the program with the -static flag it used ~100k. Looks too much to me.
* I have to run the program at least twice so it's actually accounted (otherwise it's listed in "**other")
* sa outputs the CPU time average memory usage. How to calculate the total average memory usage? Multiply it with the CPU time in milliseconds?

How are those problem dealt with at SPOJ?

Thanks in advance.

[noix]

I played a little with GNU accounting tools and encountered a few problems. :oops:

* I ran a simple Hello World program and sa reported that it used ~300k of memory. After I compiled the program with the -static flag it used ~100k. Looks too much to me.

Well.. it's the C library; if you want to save some memory, write in asm or at least don't use glibc
As you noticed, shared libraries are also counted, as well as the binary itself. In spoj, a C program which does nothing is reported to consume quite a lot of memory (glibc), while fpc programs don't (dyniamic linking doesn't work (?)).

* I have to run the program at least twice so it's actually accounted (otherwise it's listed in "**other")

Um.. I don't know what you mean.. AFAIK every process is guaranteed to be logged after it finishes (and its parent wait()s for it). And I don't know what "**other" is, maybe I haven't looked into "sa" enough.. I use "dump-acct" myself and in spoj we process pacct files on our own.

* sa outputs the CPU time average memory usage. How to calculate the total average memory usage? Multiply it with the CPU time in milliseconds?

In spoj, we just output the average memory usage of the first process. If you want to measure maximum memory usage, polling /proc is the only thing I can think of.
I think average isn't that bad; and processes are guaranteed not to exceed fixed memory limit set by RLIMITs.

[zaphod_sof]

Well.. it's the C library; if you want to save some memory, write in asm or at least don't use glibc
As you noticed, shared libraries are also counted, as well as the binary itself. In spoj, a C program which does nothing is reported to consume quite a lot of memory (glibc), while fpc programs don't (dyniamic linking doesn't work (?)).

I've just sent a simple solution to the problem TEST and it used 1484k of memory. Are those actually kilobytes? dump-acct reports that it used 1320 on my computer, and sa reports 330k?!? What does 1320 actually represent?

Um.. I don't know what you mean.. AFAIK every process is guaranteed to be logged after it finishes (and its parent wait()s for it). And I don't know what "**other" is, maybe I haven't looked into "sa" enough.. I use "dump-acct" myself and in spoj we process pacct files on our own.

I've taken a look at dump-acct, it's what I needed, though I still don't know what each field of it's output represents (no manpage for dump-acct).

In spoj, we just output the average memory usage of the first process. If you want to measure maximum memory usage, polling /proc is the only thing I can think of.
I think average isn't that bad; and processes are guaranteed not to exceed fixed memory limit set by RLIMITs.

This average usage... Is it the number of (kilo)bytes of memory process allocated during some time, or is it the memory process accessed. For example, what happens with this measurement if a program has a big global array, i.e. doesn't use malloc and company?

As of RLIMITs, when RLIMIT_AS is exceeded, program receives SIGSEGV. How do you differentiate that program has exceeded the memory limit or it just access illegal part of memory (the unallocated part, for example). I'm a bit confused here.

Another thing. In chroot jail (in which programs are being run) do you have all the libraries and interpreters (for dynammicaly linked programs and the ones that use interpreters)? In this case, couldn't any program just do unlink(2) and mess everything up?! Do you copy input files to this jail or just use a FIFO or some similar trick.

Thanks for the answers.

[noix]

Well.. it's the C library; if you want to save some memory, write in asm or at least don't use glibc
As you noticed, shared libraries are also counted, as well as the binary itself. In spoj, a C program which does nothing is reported to consume quite a lot of memory (glibc), while fpc programs don't (dyniamic linking doesn't work (?)).

I've just sent a simple solution to the problem TEST and it used 1484k of memory. Are those actually kilobytes? dump-acct reports that it used 1320 on my computer, and sa reports 330k?!? What does 1320 actually represent? :?

All dynamic libraries it's linked with, program's code itself and all data and stack memory it allocates, AFAIK.
They are kilobytes, glibc is quite heavy. But then again, it's sure to be cached in RAM.

Um.. I don't know what you mean.. AFAIK every process is guaranteed to be logged after it finishes (and its parent wait()s for it). And I don't know what "**other" is, maybe I haven't looked into "sa" enough.. I use "dump-acct" myself and in spoj we process pacct files on our own.

I've taken a look at dump-acct, it's what I needed, though I still don't know what each field of it's output represents (no manpage for dump-acct).

Well, if your distribution doesn't come with it, google for it..
Fields are: command, user time, system time, effective time, uid, gid, memory, io, time.

In spoj, we just output the average memory usage of the first process. If you want to measure maximum memory usage, polling /proc is the only thing I can think of.
I think average isn't that bad; and processes are guaranteed not to exceed fixed memory limit set by RLIMITs.

This average usage... Is it the number of (kilo)bytes of memory process allocated during some time, or is it the memory process accessed. For example, what happens with this measurement if a program has a big global array, i.e. doesn't use malloc and company?

It's allocated memory, not accessed. I don't know how to measure accessed memory.

As of RLIMITs, when RLIMIT_AS is exceeded, program receives SIGSEGV. How do you differentiate that program has exceeded the memory limit or it just access illegal part of memory (the unallocated part, for example). I'm a bit confused here. :?

We don't Right now, it's "RE (other)" in spoj.
We might start to detect it sometime, but I personally don't like to mess with ptrace() and we would detach after loading libraries and allocating memory anyway.

Another thing. In chroot jail (in which programs are being run) do you have all the libraries and interpreters (for dynammicaly linked programs and the ones that use interpreters)? In this case, couldn't any program just do unlink(2) and mess everything up?! Do you copy input files to this jail or just use a FIFO or some similar trick.

I don't get your point, on my systems, chroot() doesn't give any additional privileges and unlink()ing is at least as hard without proper privileges as without it.
And yes, we have separate chroot or two (chroots for compilers) for all languages.
Input and output files are passed though pipes.

[zaphod_sof]

All dynamic libraries it's linked with, program's code itself and all data and stack memory it allocates, AFAIK.
They are kilobytes, glibc is quite heavy. But then again, it's sure to be cached in RAM.

Well, doesn't this affect RLIMIT_AS too? Or you increase the mem limit a megabyte more for glibc?

As of RLIMITs, when RLIMIT_AS is exceeded, program receives SIGSEGV. How do you differentiate that program has exceeded the memory limit or it just access illegal part of memory (the unallocated part, for example). I'm a bit confused here.

We don't Right now, it's "RE (other)" in spoj.
We might start to detect it sometime, but I personally don't like to mess with ptrace() and we would detach after loading libraries and allocating memory anyway.

Well, maybe you could use the measured memory usage. If it's greater than the limit, then it's memory limit exceeded, otherwise it's just SIGSEGV. I just don't know if that would work, because it's just an average memory usage.

Another thing. In chroot jail (in which programs are being run) do you have all the libraries and interpreters (for dynammicaly linked programs and the ones that use interpreters)? In this case, couldn't any program just do unlink(2) and mess everything up?! Do you copy input files to this jail or just use a FIFO or some similar trick.

I don't get your point, on my systems, chroot() doesn't give any additional privileges and unlink()ing is at least as hard without proper privileges as without it.
And yes, we have separate chroot or two (chroots for compilers) for all languages.
Input and output files are passed though pipes.

Nevermind, my mistake. I forgot that you can drop the (root) privileges after you enter the chroot jail with setuid(2).

[noix]

All dynamic libraries it's linked with, program's code itself and all data and stack memory it allocates, AFAIK.
They are kilobytes, glibc is quite heavy. But then again, it's sure to be cached in RAM.

Well, doesn't this affect RLIMIT_AS too? Or you increase the mem limit a megabyte more for glibc?

Of course it does! Memory limits never had been "strict" in spoj: RLIMIS_AS is set to 256MB (enough to keep JVM happy), 64MB of physical RAM is guaranteed for the program itself and that's it.
It might seem desperate, but I can't think of a "problem" where a set memory limit would really be necessary.
Such problem would have to be limited to few languages (C/C++/Pascal?), programs would have to be linked statically and even then, compiler's optimizer could break a program which seems to use little memory enough.
Note that online judges which compile statically and have ~3 languages to choose from don't have such problems :>

As of RLIMITs, when RLIMIT_AS is exceeded, program receives SIGSEGV. How do you differentiate that program has exceeded the memory limit or it just access illegal part of memory (the unallocated part, for example). I'm a bit confused here. :?

We don't Right now, it's "RE (other)" in spoj.
We might start to detect it sometime, but I personally don't like to mess with ptrace() and we would detach after loading libraries and allocating memory anyway.

Well, maybe you could use the measured memory usage. If it's greater than the limit, then it's memory limit exceeded, otherwise it's just SIGSEGV. I just don't know if that would work, because it's just an average memory usage.

Memory usage of those SIGSEGVs isn't greater than the limit - it's really low instead. IMO, ptrace() would be more trustworty than comparing that value to observed memory consumption of SIGSEGVed program for a specific language.
With ptrace(), it would be enough to check what execve() returns.

[zaphod_sof]

All dynamic libraries it's linked with, program's code itself and all data and stack memory it allocates, AFAIK.
They are kilobytes, glibc is quite heavy. But then again, it's sure to be cached in RAM.

Well, doesn't this affect RLIMIT_AS too? Or you increase the mem limit a megabyte more for glibc?

Of course it does! Memory limits never had been "strict" in spoj: RLIMIS_AS is set to 256MB (enough to keep JVM happy), 64MB of physical RAM is guaranteed for the program itself and that's it.
It might seem desperate, but I can't think of a "problem" where a set memory limit would really be necessary.
Such problem would have to be limited to few languages (C/C++/Pascal?), programs would have to be linked statically and even then, compiler's optimizer could break a program which seems to use little memory enough.
Note that online judges which compile statically and have ~3 languages to choose from don't have such problems :>

My mistake. I haven't noticed that you don't set memory limits at all. Usually IOI-type programming contests limit memory too (both stack and heap).

With ptrace(), it would be enough to check what execve() returns.

I don't understand this. How could execve's return value help you determine if the program allocated more memory than allowed or it just accessed an illegal segment?

[noix]

With ptrace(), it would be enough to check what execve() returns.

I don't understand this. How could execve's return value help you determine if the program allocated more memory than allowed or it just accessed an illegal segment? :?

strace-ing execve() of a program which allocates more memory at the very start (from ELF headers, not in the code) gives:
execve("./a", ["./a"], [/* 23 vars */]) = -1 ENOMEM (Cannot allocate memory)
+++ killed by SIGKILL +++
That's the only time where allocating memory results is SIGSEGV, e.g. malloc-ing simply fails when reaching the limit. And it's nothing wrong to allocate as much memory as you can this way (large malloc, halve the amount you want if it fails etc).

[zaphod_sof]

With ptrace(), it would be enough to check what execve() returns.

I don't understand this. How could execve's return value help you determine if the program allocated more memory than allowed or it just accessed an illegal segment?

strace-ing execve() of a program which allocates more memory at the very start (from ELF headers, not in the code) gives:
execve("./a", ["./a"], [/* 23 vars */]) = -1 ENOMEM (Cannot allocate memory)
+++ killed by SIGKILL +++

Nice... I didn't know that.

That's the only time where allocating memory results is SIGSEGV, e.g. malloc-ing simply fails when reaching the limit. And it's nothing wrong to allocate as much memory as you can this way (large malloc, halve the amount you want if it fails etc).

Damn, why didn't I thought of that.

[Edward_sof]

We are left with using operating system specific APIs to determine memory usage. This is however, an advantage. We will be able to determine the complete overhead of an application, including memory not allocated through the C library. For example, when the process loads a shared library, the linker will use the mmap() system call directly. Similarly, the thread stacks in the pthread implementation will be directly mapped rather than malloced.

[narbej]

Podstawowe testy przechodzą bez problemu.

Tak to już jest, z przechodzeniem, że potem robią się z tego problemy po przejściach.
Podstawowy problem polega tu na tym, że powinien przebiegać, a nie przechodzić. Jak dalej będzie się tak guzdrał, to dla niepodstawowych będzie dużo za wolny, tak przynajmniej czuję i mogę się domyślić i wyobraźić.

Jak Ci mogę jeszcze pomóc?

Ewentualnie, jak Ty byś trochę mógł pomóc, tym co Ci chcieliby ewentualnie pomóc, w ten sposób, żebyś pomógł im, aby mogli lepiej zrozumieć jak Ci pomóc, żebyś mógł lepiej pomóc tym, którzy zechcą Ci pomóc... chyba się zapętliłem w rekurencję.

Jak to zrobić? Gdzieś tam na forum leży taki jakiś poradnik.

[master6262]

Ok. rozumiem. Z tym, że chwilowo nie chodzi mi o to aby ten program przebiegał przez testy tylko żeby je zrobił. Nie wyrzuca mi, że przekroczyłem limit czasu tylko, że jest błędna odpowiedź. Tak po za tym w limicie czasu na razie się mieści, ma jeszcze zapas sekundy.

Chodzi mi o to, że nie mogę znaleźć testu dla którego pojawia się błędna odpowiedź. Kod jest napisany chyba dość przejrzyście.

[master6262]

Z tego co widziałem na forum, wszyscy wrzucają tak kody, do tego kod chyba nie jest za długi.

[master6262]

Zadanie zaakceptowane, co prawda na razie dosyć słabą metodyką (choć i tak skrócone o te warunki) ale zaraz sobie przerobię żeby działało rekurencyjnie. Dzięki wielkie za sugestie, w tym również to, że funkcja potęgi jest zbędna oraz za te nie dotyczące zadania. Na pewno to usprawni moją komunikacje na forum.

[akhil_777]

The links are broken!

[armeer]

Yes, links are broken. Could you restore that information please?