Skip to contentSkip to conversation

Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

DISCUSSION Axel Kittenberger 8 participants 12 messages Dec 22, 2005 – Dec 26, 2005

lore
Share & tools
lore
#0 lore raw

Hello, Whom do I talk to about acceptance of Patches in the Bootloader?

I have seen, and coded once some time ago for priv. uses, do infalte the gziped linux kernel at boottime in "arch/i386/boot/compressed/misc.c" and " windowlib/inflate.c" the deflation algorthimn uses a 32k backtrack window. Whenever it is full, it copies it .... into the memory.

While this window makes a lot of sense in an userspace application like gunzip, it does not make a lot sense in the bootloader. As userspace application the window is flushed to a file when full. The bootloader "flushes" it to memory (copies it in memory). That 1 time copy of the whole kernel can be optimized away, since we do not keep track of a window since the inflater can read what it has written right in the computer memory, while it unpacks the kernel.

What would the optimization be worth?
* A faster uncompressing of the kernel, since a total 1-time memcopy of the whole kernel is been optimized away.
* I'm not sure about the size, the memory or disk footprint. If the 32k static (!) memory array in compressed/misc.c, I don't know if it safes 32k running memory, or 32k on-disk size. Since I don't know the indepth working of these.

Before I code this again (I know that this optimization has worked with a 2.4 kernel), I want to ask, would such patch be accepted? now or once ever? who should I forward this?

Greetings,
Axel

#1 lore raw
Quoted 15 lines · Axel Kittenberger

Hello, Whom do I talk to about acceptance of Patches in the Bootloader?

I have seen, and coded once some time ago for priv. uses, do infalte the gziped linux kernel at boottime in "arch/i386/boot/compressed/misc.c" and " windowlib/inflate.c" the deflation algorthimn uses a 32k backtrack window. Whenever it is full, it copies it .... into the memory.

While this window makes a lot of sense in an userspace application like gunzip, it does not make a lot sense in the bootloader. As userspace application the window is flushed to a file when full. The bootloader "flushes" it to memory (copies it in memory). That 1 time copy of the whole kernel can be optimized away, since we do not keep track of a window since the inflater can read what it has written right in the computer memory, while it unpacks the kernel.

Quoted 3 lines

What would the optimization be worth?
* A faster uncompressing of the kernel, since a total 1-time memcopy of the whole kernel is been optimized away.

Have you timed this operation? I would predict that the time to copy the kernel is nominal as compared the the time taken to perform the decompression.

#2 lore raw
Quoted 3 lines

Have you timed this operation? I would predict that the time to copy the kernel is nominal as compared the the time taken to perform the decompression.

In the current version it is defleated AND copied. The optimization would reduce it by 1 copy.

Greetings, Axel

#3 lore raw
Quoted 6 lines · Axel Kittenberger
Quoted 3 lines

Have you timed this operation? I would predict that the time to copy the kernel is nominal as compared the the time taken to perform the decompression.

In the current version it is defleated AND copied. The optimization would reduce it by 1 copy.

Right. And the time to perform that one copy is exactly...?

I doubt that it is a significant percentage of the whole operation.

Quoted 2 lines

Greetings, Axel

#4 lore raw
Quoted 3 lines

Right. And the time to perform that one copy is exactly...?

I doubt that it is a significant percentage of the whole operation.

Well Yes I agree, I guess also it isn't. Its roughly the time you need to copy 1 MB memory around. I just noticed that it is in fact after all still unneccary and that in fact could be optimized away. As some window-management could can be optimized away.

I would volunteer to take the time to code it, but only if i have a good feeling that it would be accepted... if not, well than okay for me also, i will do other things :o)

Greetings, Axel

#5 lore raw
Quoted 4 lines · Axel Kittenberger
Quoted 3 lines

Right. And the time to perform that one copy is exactly...?

I doubt that it is a significant percentage of the whole operation.

Quoted 8 lines

Well Yes I agree, I guess also it isn't. Its roughly the time you need to copy 1 MB memory around. I just noticed that it is in fact after all still unneccary and that in fact could be optimized away. As some window-management could can be optimized away.

I would volunteer to take the time to code it, but only if i have a good feeling that it would be accepted... if not, well than okay for me also, i will do other things :o)

I would think this would be a welcome optimization for embedded platforms even if not included in mainline. Embedded platforms often dont have very fast memory, but nevertheless are required to boot ASAP.

-HK

#6 lore raw
Quoted 5 lines
Quoted 5 lines
Quoted 4 lines

Right. And the time to perform that one copy is exactly...?

I doubt that it is a significant percentage of the whole operation.

Quoted 7 lines
Quoted 2 lines

Well Yes I agree, I guess also it isn't. Its roughly the time you need to copy 1 MB memory around.

I would think this would be a welcome optimization for embedded platforms even if not included in mainline. Embedded platforms often dont have very fast memory, but nevertheless are required to boot ASAP.

Do old i386s count? I've got one that ran 2.6.11 perfectly (even w/o -tiny), but kernel decompression is what took most time. (At 3.00 bogomips, the world looks quite different!)

Jan Engelhardt

#7 lore raw
In reply to Marc Singer
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines

Have you timed this operation? I would predict that the time to copy the kernel is nominal as compared the the time taken to perform the decompression.

In the current version it is defleated AND copied. The optimization would reduce it by 1 copy.

Right. And the time to perform that one copy is exactly...? I doubt that it is a significant percentage of the whole operation.

On the other hand it makes the kernel a few bytes smaller :-)

Folkert van Heusden

Signature · 6 lines
Try MultiTail! Multiple windows with logfiles, filtered with regular
expressions, colored output, etc. etc. www.vanheusden.com/multitail/
----------------------------------------------------------------------
Get your PGP/GPG key signed at www.biglumber.com!
----------------------------------------------------------------------
Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com
#8 lore raw
Quoted 1 line

On the other hand it makes the kernel a few bytes smaller :-)

Well on rather slow machines it is a bit faster indeed, I did code it 3 years ago for an embedded system (embedded PowerPC). 'til now I just never found the time to offer a patch back to "vanilla" linux. I recently just thought I could ask maybe if it is after all desired even so....

Greetings, Axel

#9 lore raw
Quoted 7 lines
Quoted 2 lines

On the other hand it makes the kernel a few bytes smaller :-)

Well on rather slow machines it is a bit faster indeed, I did code it 3 years ago for an embedded system (embedded PowerPC). 'til now I just never found the time to offer a patch back to "vanilla" linux. I recently just thought I could ask maybe if it is after all desired even so....

Well if it's about size, why is not something better than gzip used yet? Like bzip2, 7z or whatever comes to mind? Is it because of the amount of memory required for decompression?

Jan

#10 lore raw
In reply to Axel Kittenberger

2005/12/22, Axel Kittenberger <[email protected]>:

Quoted 15 lines

Hello, Whom do I talk to about acceptance of Patches in the Bootloader?

I have seen, and coded once some time ago for priv. uses, do infalte the gziped linux kernel at boottime in "arch/i386/boot/compressed/misc.c" and " windowlib/inflate.c" the deflation algorthimn uses a 32k backtrack window. Whenever it is full, it copies it .... into the memory.

While this window makes a lot of sense in an userspace application like gunzip, it does not make a lot sense in the bootloader. As userspace application the window is flushed to a file when full. The bootloader "flushes" it to memory (copies it in memory). That 1 time copy of the whole kernel can be optimized away, since we do not keep track of a window since the inflater can read what it has written right in the computer memory, while it unpacks the kernel.

Quoted 6 lines

What would the optimization be worth?
* A faster uncompressing of the kernel, since a total 1-time memcopy of the whole kernel is been optimized away.
* I'm not sure about the size, the memory or disk footprint. If the 32k static (!) memory array in compressed/misc.c, I don't know if it safes 32k running memory, or 32k on-disk size. Since I don't know the indepth working of these.

Neither for saving running memory (discarded), nor on-disk size (window[WSIZE] resides in BSS).

Quoted 2 lines

Before I code this again (I know that this optimization has worked with a 2.4

I think 2.6 didn't change much in this field.

Quoted 2 lines

kernel), I want to ask, would such patch be accepted? now or once ever? who should I forward this?

"H. Peter Anvin" <[email protected]>, and akpm, and even Linus. I'd like to see your patch. It would be instructive.

-- Coywolf

#11 lore raw
Quoted 11 lines · Coywolf Qi Hunt
Quoted 7 lines

What would the optimization be worth?
* A faster uncompressing of the kernel, since a total 1-time memcopy of the whole kernel is been optimized away.
* I'm not sure about the size, the memory or disk footprint. If the 32k static (!) memory array in compressed/misc.c, I don't know if it safes 32k running memory, or 32k on-disk size. Since I don't know the indepth working of these

Neither for saving running memory (discarded), nor on-disk size (window[WSIZE] resides in BSS).

I've actually implemented this for another application (where BSS was at a premium.) It even has some nice benefits for code size if you do it right.

It indeed would avoid a cache-to-memory copy, but that's not really a huge deal, which is why noone has worried too much about it.

-hpa