2009/9/2 erik quanstrom <quans...@quanstro.net>: >> problem ended up being that I'd have to rework a lot of the slab >> allocator, or do checks on every memory allocation, and I didn't want >> to do that. More detailed info for those who care: > > could you use plan 9 terminology?
Probably not. Plan 9 uses a slab allocator to allocate memory in both kernel and userland. The only fault I see in my previous email is saying `zone' instead of `pool', but they're synonymous enough. If you cite a specific ambiguity, I'm more than happy to clarify. >> >> Lemma: In order to avoid overcommitting, we must impose limits on how >> much memory may, in fact, be allocated. To make the implementation >> provable, you must be able to assert that memory always comes from the >> same spot, and you thus have a single path to follow into allocation. > > "from the same spot" could mean from the same point in the code or > from the same physical address. either way, i don't buy this assertion. > counter example: ssd drive remapping algorithms. That was a rather poor choice of words. Restatement: To prove the safety of the implementation, you must be able to assert that any memory allocation triggers a check on the availability of the requested memory. This revised statement doesn't require that a single code path be followed into allocation, but since malloc() obtains memory from the slab allocator, it makes sense to build the protection into the slab allocator: it's centralized, and all allocations are guaranteed to go through there anyway. The safety of such an implementation is much easier to prove. I hope that clarifies what I meant. Example for what I did not mean: the FreeBSD jail system `virtualizes' kernel resources by partitioning them to certain jail IDs. This requires any resources wishing to be shared to be jail-aware, with the side-effect that proving a jail only has access to what it needs is much more difficult, because you have to prove that every resource is `protected' anywhere that it is potentially used in the kernel. The analogue to this sort of thing for our discussion would be introducing an additional API to be used in conjunction with malloc(), requiring it to be used every time. Clearly, it is more difficult to prove that all mallocs() are safe with such an API, and it is *impossible* to prove that future calls will be protected, as it is impossible to prove that future additions to the kernel are properly handled with respect to jails. It's a somewhat silly comparison (as no one in their right mind would implement this as an API to be used alongside malloc), but it illustrates my point well. And it was easier to come up with that than coming up with some other theoretical non-centralized (from a code point of view) solution to this problem. --dho > - erik > >
