aspects of bootmem design (was: Re: [PATCH] MAX_MP_BUSSES increase)

aspects of bootmem design (was: Re: [PATCH] MAX_MP_BUSSES increase)

[William Lee Irwin III]

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

Re: [PATCH] MAX_MP_BUSSES increase

[William Lee Irwin III]

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?

Please refer to my other messages regarding the true purposes of the
tree-based bootmem and so on.

Given that it's one architecture, a single very small machine, and one
kernel version, this is perhaps not as scientific as I'd like it to be,
but my personal computer (i386) at home shows the following results for
2.4.17-rc2 and my local patch set (plus or minus bootmem).


2.4.17-rc2-wli-bootmem:
Memory: 769332k/786368k available
	(1389k kernel code, 16648k reserved, 1019k data, 224k init, 0k highmem)

2.4.17-rc2-wli:
Memory: 769340k/786368k available
	(1389k kernel code, 16640k reserved, 1019k data, 216k init, 0k highmem)

After freeing init, the total memory is identical, not my expected 8KB:

--- bootmem.meminfo	Fri Dec 21 03:33:44 2001
+++ nobootmem.meminfo	Fri Dec 21 03:30:53 2001
@@ -1,18 +1,18 @@
         total:    used:    free:  shared: buffers:  cached:
-Mem:  788025344 78618624 709406720        0  5652480 33247232
+Mem:  788025344 87261184 700764160        0 12656640 34500608
 Swap: 518152192        0 518152192
 MemTotal:       769556 kB
-MemFree:        692780 kB
+MemFree:        684340 kB
 MemShared:           0 kB
-Buffers:          5520 kB
-Cached:          32468 kB
+Buffers:         12360 kB
+Cached:          33692 kB
 SwapCached:          0 kB
-Active:          53784 kB
-Inact_dirty:     4748 kB
+Active:          61728 kB
+Inact_dirty:     4876 kB
 Inact_clean:        0 kB
 HighTotal:           0 kB
 HighFree:            0 kB
 LowTotal:       769556 kB
-LowFree:        692780 kB
+LowFree:        684340 kB
 SwapTotal:      506008 kB
 SwapFree:       506008 kB


Cheers,
Bill