[uClinux-dev] [RFC][PATCH try #3] A new memory algorithm for the embedded linux system

[Aubrey Li]

Thirdly, this is the patch attached about a new memory algorithm for
the embedded linux system.
It's a replacement of buddy system and can accept non power of 2 order
memory request.

Thanks Phil to point out one case the previous patch doesn't deal
with. The problem is fixed in this patch. Now it's more robust and
here some test result on my side is as follows, comparing with buddy
system:

1) after system boot, buddyinfo result

-buddy system:

root:~> cat /proc/buddyinfo
Node 0, zone      DMA      0      1      1      0      1      1      0
1      1      1      1      1      1      0

-cake system:

root:~> cat /proc/buddyinfo
--------Node 0, zone DMA--------
No.1    Page addr: 0x229000   num: 3     buddy addr:0x22c000
No.2    Page addr: 0x63a000   num: 8134  buddy addr:0x2600000
-------------End----------------

Comment:
buddy - memory is fragmented into 10 blocks, the biggest block is pow(2,
12) = 4096 pages.
cake - memory is fragmented into 2 blocks, the biggest block is 8134 pages.

2) run a test program, it's attached.

-buddy system:

root:~> time ./t
real    0m 1.54s
user    0m 0.41s
sys     0m 1.13s

-cake system:

root:~> time ./t
real    0m 1.50s
user    0m 0.34s
sys     0m 1.16s

Comment: The time cost is almost the same.

3) After the test program, buddyinfo result:

-buddy:

root:~> cat /proc/buddyinfo
Node 0, zone      DMA     22     39     36     36     34     35     19
2      3      1      1      1      0      0

-cake:

root:~> cat /proc/buddyinfo
--------Node 0, zone DMA--------
No.1    Page addr: 0x5b8000   num: 1     buddy addr:0x5b9000
No.2    Page addr: 0x5bd000   num: 17    buddy addr:0x5ce000
No.3    Page addr: 0x65c000   num: 34    buddy addr:0x67e000
No.4    Page addr: 0x68f000   num: 3     buddy addr:0x692000
No.5    Page addr: 0x694000   num: 8     buddy addr:0x69c000
No.6    Page addr: 0x6aa000   num: 140   buddy addr:0x736000
No.7    Page addr: 0x738000   num: 80    buddy addr:0x788000
No.8    Page addr: 0x78a000   num: 80    buddy addr:0x7da000
No.9    Page addr: 0x7dc000   num: 194   buddy addr:0x89e000
No.10   Page addr: 0x89f000   num: 113   buddy addr:0x910000
No.11   Page addr: 0x911000   num: 96    buddy addr:0x971000
No.12   Page addr: 0x972000   num: 81    buddy addr:0x9c3000
No.13   Page addr: 0x9c4000   num: 166   buddy addr:0xa6a000
No.14   Page addr: 0xa6b000   num: 76    buddy addr:0xab7000
No.15   Page addr: 0xab8000   num: 81    buddy addr:0xb09000
No.16   Page addr: 0xb0a000   num: 186   buddy addr:0xbc4000
No.17   Page addr: 0xbc5000   num: 113   buddy addr:0xc36000
No.18   Page addr: 0xc37000   num: 106   buddy addr:0xca1000
No.19   Page addr: 0xca2000   num: 122   buddy addr:0xd1c000
No.20   Page addr: 0xd1d000   num: 115   buddy addr:0xd90000
No.21   Page addr: 0xd91000   num: 86    buddy addr:0xde7000
No.22   Page addr: 0xde8000   num: 81    buddy addr:0xe39000
No.23   Page addr: 0xe3a000   num: 161   buddy addr:0xedb000
No.24   Page addr: 0xedc000   num: 81    buddy addr:0xf2d000
No.25   Page addr: 0xf2e000   num: 81    buddy addr:0xf7f000
No.26   Page addr: 0xf80000   num: 196   buddy addr:0x1044000
No.27   Page addr: 0x1045000  num: 113   buddy addr:0x10b6000
No.28   Page addr: 0x10b7000  num: 115   buddy addr:0x112a000
No.29   Page addr: 0x112b000  num: 113   buddy addr:0x119c000
No.30   Page addr: 0x119d000  num: 192   buddy addr:0x125d000
No.31   Page addr: 0x125e000  num: 81    buddy addr:0x12af000
No.32   Page addr: 0x12b0000  num: 530   buddy addr:0x14c2000
No.33   Page addr: 0x14c4000  num: 445   buddy addr:0x1681000
No.34   Page addr: 0x1682000  num: 70    buddy addr:0x16c8000
No.35   Page addr: 0x16c9000  num: 3895  buddy addr:0x2600000
-------------End----------------

Comment:
buddy system - memory is fragmented into 229 blocks, the biggest block is
pow(2,11) = 2048 pages.

cake system - memory is fragmented into 35 blocks, the biggest block
is 3895 pages.

Any comments?

Thanks,
-Aubrey
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cake.diff
Type: application/octet-stream
Size: 8300 bytes
Desc: not available
Url : http://mailman.uclinux.org/pipermail/uclinux-dev/attachments/20070105/21ecd542/cake.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: t.c
Type: application/octet-stream
Size: 587 bytes
Desc: not available
Url : http://mailman.uclinux.org/pipermail/uclinux-dev/attachments/20070105/21ecd542/t.obj