Re: [lwip-devel] mem(p) allocator change request

[lukem . lwip]

On Mon, 29 Mar 2004 address@hidden wrote:
> A general purpose allocator will typically
> produce some memory fragmentation
> which is unacceptable for embedded systems.

> A pool allocator avoids this issue by
> using fixed size blocks. I don't see
> a reason to remove this allocator
> as Luke proposed.

The thing is, no-one has actually shown that memory fragmentation is
actually an issue for the allocation patterns we have in lwIP. Basically,
we allocate lots of small, similar sized objects, which mostly have short
lifespans.

The reason people are concerned about fragmentation is that it could
result in unused (and unusable) bits of memory stuck between two
long-lived objects. First, this is unlikely to happen in lwIP, and second,
the current solution solves the problem by wasting even more space ---
that is, unless you know exactly how many of each pool type you will need
in advance --- which I doubt (m)any people do.

The memp solution is just to statically allocate a number of buffers of
each type, which means you invariably waste a significant amount of memory
on buffers that are never used. Switching to a single, general purpose
allocator removes the waste of this memory, as it can be used for other
types when needed.

Now we can all hand-wave about fragmentation, but until someone
demonstrates that it is an issue in practice, and that more memory is lost
to fragmentation than is wasted by using a static number of buffers, we
should not assume the memp implementation to be more space efficient.

> Other algorithms like
> the buddy allocator might be more space
> efficient though.

There are any number of malloc implementations, all of which will have
different properties... http://www.cs.colorado.edu/~zorn/Malloc.html has a
decent list. http://gee.cs.oswego.edu/dl/html/malloc.html has a
description of some of the tradeoffs and goals of malloc implementations.

The conclusions reached in the earlier discussion is that we can address
the fact that different users of lwIP have different needs by providing a
decent abstraction for memory allocation. This should keep everybody
happy, because we can each have an allocator which suits our own set of
tradeoffs.

I'm also happy to work on this once the new pbuf implementation is merged,
but I think the best design would be to define a struct containing a bunch
of function pointers to malloc / realloc / free (and possibly init /
deinit - which would help solve current cleanup problems in lwIP). The
user could then register one or more of these structs to be used at
different points in lwIP --- thus allowing an arbitrary number of
allocators, which can be as specialised as you like, or alternately you
can pass a single general purpose allocator to everything --- it is, as it
should be, the developers choice.

--
Luke