Resource limitation

[leichter_jerrold at emc.com (leichter_jerrold at emc.com)]

| > 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, 
Capability systems I've seen have Boolean capabilities.  I agree
that one could, in principle, extend the notion to include resource
limits - but that adds complexity.

|                                        but are still largely
| theoretical.
...for an interesting notion of "still".  Capability systems have been
around for 30 years.  They've been implemented repeatedly.  But they
haven't actually succeeded in any meaningful sense anywhere.  The
problem doesn't seem to be capabilities as such - it's the management
of them, which is way too complex.  Great research area....

BTW, as an example of the additional complexity in going from binary
capabilities to resource limits:  If I have a capability, I may
or may not be able to grant it to another actor (keeping it for
myself as well); and I may or may not be able to *transfer* it to
another actor.  With resources, can I have to split my resources
with, say, the subprocesses I create?  Can I start them with the
same resources I have?  Can I pool mine with theirs?  If I have
to split them, is there some way of moving the resources around
later?  (VMS has OS-enforced resources, and has different catagories
of them along these lines.  It's been too long and I don't even
remember the catagories or examples for certain, but things like
"total memory used" are pooled, others are split, and yet others
are simply copied.)

There's a recent research programming language whose name escapes me at
the moment that fully integrates capabilities with the language itself.
Nice work - it was used in a demo of a multi-level secure Web browser or
some such thing recently.  What I don't recall is whether they do
resource control as well.

|     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
...missing the point entirely.  Take a multithreaded server.  Apply a
strict ulimit.  Voila - simple denial of service attack:  It's now
easy for any thread to exhaust available VM, crashing the entire
application.

Thanks, but no thanks.

| 
| 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.
(a) Who said anything about per-*thread* limits?  (b) Even if it is
a per-thread limit, what happens when memory is transfered from thread
to thread; (c) having been there ... you grossly underestimate the
difficulty of "implement[ing] your own allocator library", at least
if performance matters to you.

|     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. 
The moral equivalent of ulimit.

|                                                     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.
Well, based on what you've proposed ... yes, we're seriously lacking in
both theory and implementation.
                                                        -- Jerry

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