Resource limitation

[nash at solace.net (Nash)]

On Mon, Jul 17, 2006 at 05:48:59PM -0400, leichter_jerrold at emc.com
wrote:
> I was recently looking at some code to do regular expression
> matching, when it occurred to me that one can produce fairly small
> regular expressions that require huge amounts of space and time.
> There's nothing in the slightest bit illegal about such regexp's -
> it's just inherent in regular expressions that such things exist.

Yeah... the set of regular languages is big. And, some have pretty
pathological FSM representations.

> In addition, the kinds of resources that you can exhaust this way is
> broader than you'd first guess.  Memory is obvious; overrunning a
> thread stack is perhaps less so.  ... How about file descriptors?
> File space? Available transmission capacity for a variety of kinds
> of connections?

One place to look is capability systems. They're more flexible and
should have all the features you want, but are still largely
theoretical.

    http://en.wikipedia.org/wiki/Capability-based_security


That said, every decent Unix system I'm aware of has ulimit, which you
can use to restrict virtual memory allocations, total open files, etc:

    nash @ quack% ulimit -a
    ...
    virtual memory        (kbytes, -v) unlimited

    nash @ quack% ulimit -v 1024 # just 1M RAM, this'll be fun :-)

    nash @ quack% ( find * )
    find: error while loading shared libraries: libc.so.6: failed to map
    segment from shared object: Cannot allocate memory


Alternately, you can implement your own allocator library for your
application and then impose per-thread limits using that library. How
you do that is going to depend alot on the language. Obviously, there
are lots for C/C++ floating around.

    http://en.wikipedia.org/wiki/Memory_allocation

In Java, you don't get nice knobs on Objects and Threads, but you get
several nice knobs on the VM itself: -Xm, -XM, etc. Other high level
languages have similar problems to Java. I.e., how do you abstract the
"size" of a thing when you don't give access to memory as a flat byte
array? Well, you can do lots of fun things using LIFO queues, or LRU
caches, and so forth. There are performance impacts to consider, but
they you can often tweak things so it sucks primarily for the abuser.

None of these is really that hard to implement. So, do we really need
new theory for this? Dunno. One's mileage does vary.

-nash

-- 

"the lyf so short, the craft so long to lerne."
                    - Geoffrey Chaucer