On Fri, Dec 21, 2001 at 11:42:40AM +0100, Ingo Molnar wrote:
> no, it does not happen. Eg. on x86, we first set up bootmem, then we
> allocate multiple times, then we free all the remaining areas. Not a
> single place for fragmentation to happen, apart from the skipping issue i
> mentioned in the previous mail (and which isnt solved by the tree
> structure either). A complex pattern of bootmem-alloc/bootmem-free is just
> not the common thing to do - we usually dont do anything complex before
> initializating the real allocators.
As someone who has literally tracked every bootmem operation and the
effects on the state of the bootmem allocator that happens during the
entire lifetime of the bootmem allocator on a few different machines,
I will say that fewer than 10 calls to alloc_bootmem_core() occur on
the i386 PC's I've seen on kernels from 2.4.15-pre5 to 2.4.17-pre1.
On Fri, Dec 21, 2001 at 11:42:40AM +0100, Ingo Molnar wrote:
> William, could you please give us the amount of RAM saved on your box,
> with and without your tree-structure patch applied?
I will do so in short order, but I will first say a few things:
(1) I am not using a true allocation algorithm.
I am using essentially devices I contrived myself to
respect the semantics of the existing bootmem interfaces.
(2) The complex allocation and freeing pattern is neither the
problem this tries to solve, nor is it except by perhaps
some side-effects something that happens to benefit.
The in-line documentation (if you would like more, I
will write more with both haste and precision) attempts
to present the issues it was designed to address.
I will also answer not only specific questions, but
also present descriptions of the motivations, the
mechanisms, the results, the testing, and the algorithms
in whatever level of detail the questioner would like,
with the small proviso that the more detailed the
response requested, the larger the time I will need
to prepare the response.
(3) Yes, I presented results regarding memory savings, and
they are factual. I stated, if I recall properly,
that they are minor on i386 and reported them as they
were reported to me by independent testers. I also
reported results that came back to me from independent
testing that were larger than those I had seen myself.
(4) The tree structure is not the essential aspect. The tree
structure is to eliminate exhaustive search, and the
particular tree (treaps) were chosen on the basis of
a recommendation in Knuth vol 3 regarding support for
searches on dynamic sets of intervals. Some have objected
to the complexity of the structure. Other feedback
came back as well that said the tree structures were
good and efficient, which counterbalanced that.
(5) The essential aspect is an extent-based representation of
available physical memory. The existing bootmem uses
a direct-mapped tabulation of available physical pages,
which requires foreknowledge by arch/*/kernel/setup.c
of all the available ranges of physical memory, including
(you guessed it) building up a different extent-based
representation for just about every architecture.
The caller's task is simplified when the layout of the
data structures used to track the memory are not dependent
upon the layout of the memory itself, and a small
demonstration of this can be arranged.
Cheers,
Bill
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Sun Dec 23 2001 - 21:00:24 EST