Re: GSOC 2013 project " Kernel Size Reduction for Embedded System "

[Erich Dollansky]

Hi,

On Mon, 8 Apr 2013 20:28:04 +0000
Amit Rawat <aam...@gmail.com> wrote:

> GSOC posted the list of selected organization for GSOC 2013 and I am
> highly happy that FreeBSD is among the selected organization.
>
> I am a third year student interested to work in the field of embedded
> system. I applied last year and the title of my project was " Kernel
> Size Reduction for Embedded System". The link to my last year
> proposal is "
> https://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/amitrawat10/1#c8001"
> But due to some flaws it doesn't get selected. I am looking to
> improve my proposal for this year and apply again. I explain some
> portion of my project pictorially on my blog
>
> "
> https://amit10rawat.wordpress.com/2013/02/26/kernel-size-reduction-for-embedded-system/
> "
>
> I am looking for suggestion and new ideas by which I can reduce the
> size of kernel.
>
did you look at historic operating systems and how they did it?

When I was a student, we simply loaded a module into memory and then
wrote it to an external memory when not needed. It was a very basic
swapping algorithm with fixed size. It did not differentiate between
code and data etc. All calls where done through a wrapper which was
always in memory. So, the module was loaded by the OS. The OS did not
notice that we removed the code from memory. Only the wrapper knew of
what we did.

We selected functions/modules which have to be in memory and which
could be on disk. There was a fixed number of memory segments we could
use for loading external modules. The trick was to select the modules
so that the system did not lock up.

We did not use a tree structure what you might could.

The advantage of this was that the actual code was not
modified.

Yes, I know that this is hard core.

My problem would be that I do not know how much effort it would be to
implement this in a modern operating system.

Erich


> Amit Rawat(amraw)
> _______________________________________________
> freebsd...@freebsd.org mailing list
> http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
> To unsubscribe, send any mail to
> "freebsd-hacke...@freebsd.org"

_______________________________________________
freebsd...@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
To unsubscribe, send any mail to "freebsd-hacke...@freebsd.org"

[Alfred Perlstein]

On 4/8/13 4:10 PM, Adrian Chadd wrote:
> Hi,
>
> Your idea is interesting, but it doesn't fix the underlying problem -
> there's just too much code. :(
>
If you were to API'ify some of the more basic things such as fget,
fdrop, filedesc stuff you could potentially swap out the systems for
simpler (albeit less efficient) algorithms, the cost there may be slow
smp performance, or maybe not allowing threads?

What we really need is someone to pin down those parts of code that
smaller systems may not need and provide compromise when we remove them.

Other ideas are simple like for instance removing certain syscalls (for
example, more recent ones such as openat) and features such as unix
descriptor passing.

However, until a bunch of embedded folks come forward and state what
they are really willing to sacrifice, then we won't really have anything
to go on, and it will be guessing at what will work for a space that not
all of us are familiar with.

So I'm hoping some people can make the tough call to give direction
here, otherwise nothing good will come of it.

Has anyone actually done this? Or maybe compared against another
embedded OS?

-Alfred

[Jilles Tjoelker]

On Mon, Apr 08, 2013 at 08:28:04PM +0000, Amit Rawat wrote:
> GSOC posted the list of selected organization for GSOC 2013 and I am
> highly happy that FreeBSD is among the selected organization.

> I am a third year student interested to work in the field of embedded
> system. I applied last year and the title of my project was " Kernel
> Size Reduction for Embedded System". The link to my last year proposal
> is
> https://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/amitrawat10/1#c8001

> But due to some flaws it doesn't get selected. I am looking to improve my
> proposal for this year and apply again. I explain some portion of my
> project pictorially on my blog

> https://amit10rawat.wordpress.com/2013/02/26/kernel-size-reduction-for-embedded-system/

> I am looking for suggestion and new ideas by which I can reduce the
> size of kernel.

It looks like the overlay idea could be implemented more simply by
taking advantage of the VM system: make part of the kernel code
pageable. Memory formerly occupied by rarely used kernel code can then
be used by userland applications. You will need some sort of backing
store where the kernel code can be read after booting; this is not
normally available.

However, almost no kernel code is safe in a situation where an
instruction fetch may fault. Reading or writing the secondary storage
can easily cause a deadlock. It causes the thread to sleep, which is not
allowed while holding a mutex. It would help if you could wire down
pieces which will need to be used in the near future from a place where
a fault is safe, but this may also be very slow even if the code is
already in memory.

Some other ideas for kernel size reduction:

* Find pieces of code that are required but seem big for what they do
for you, and try to make them smaller. The proposal should list
concrete parts.

* Find variables and functions that are required only during kernel
initialization, place them in a special section and add this section
to the free memory pool after kernel initialization.

--
Jilles Tjoelker

[Amit Rawat]

GSOC posted the list of selected organization for GSOC 2013 and I am highly
happy that FreeBSD is among the selected organization.

I am a third year student interested to work in the field of embedded
system. I applied last year and the title of my project was " Kernel Size
Reduction for Embedded System". The link to my last year proposal is
"
https://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/amitrawat10/1#c8001"
But due to some flaws it doesn't get selected. I am looking to improve my
proposal for this year and apply again. I explain some portion of my
project pictorially on my blog

"
https://amit10rawat.wordpress.com/2013/02/26/kernel-size-reduction-for-embedded-system/
"

I am looking for suggestion and new ideas by which I can reduce the size of
kernel.

Amit Rawat(amraw)

[Adrian Chadd]

Hi,

Your idea is interesting, but it doesn't fix the underlying problem -
there's just too much code. :(

Adrian

[Adrian Chadd]

Well, it's relatively easy to experience what it's like.

Reboot your machine with 32mb. Try to do things like bring up network
interfaces. Snark when stupid stuff occurs, like you can't allocate
enough mbufs for the driver RX path _and_ run the ifconfig command to
completion to bring said interface up.

There's just a lot of code. You can start by cross-building one of the
MIPS kernels targeting a small system (eg AP121) and look at the
text/data sections of the resulting .o's. Group them together into
subsystems and take a look.

Now, as for what we can get away with - I'm still going through
another round of review. Yes, there's likely a bunch of syscalls or
syscall behaviours that we just don't need in the embedded world.
Things like all the POSIX compatible fine grained locking? Likely
don't need. But there's some reasonably big areas of bloat that we
could easy hit right now. I've chopped out some of the more silly
abuses in the past (posix acl code that only gets used by ZFS, always
being compiled in? Sigh.)

Eg:

text data bss dec hex filename
59772 160 49184 109116 1aa3c kern_umtx.o

That's a lot of both code and bss just for mutex handling, don't you
think? Do we really need 59KiB of code and 48KiB of BSS just for mutex
handling?

text data bss dec hex filename
184 0 12160 12344 3038 sc_machdep.o

.. 8 consoles? 12k of BSS? again, not much, but ..

adrian@lucy:~/work/freebsd/svn/src/sys/cam]> cat
/tmp/AP121-nodebug.txt | egrep 'ata'
text data bss dec hex filename
11536 0 0 11536 2d10 ata_all.o
17624 1504 16 19144 4ac8 ata_da.o
6388 448 16 6852 1ac4 ata_pmp.o
18960 304 0 19264 4b40 ata_xpt.o

.. 52 odd KiB tied up in CAM ATA transport, which we don't use unless
the ATA code is compiled in. It's just sitting there, waiting for an
ATA device to come along.

lucy# cat /tmp/AP121-nodebug.txt | grep "vfs_" | grep -v devfs | sort -k3
4160 48 0 4208 1070 vfs_acl.o
4752 48 0 4800 12c0 vfs_export.o
5464 0 0 5464 1558 vfs_extattr.o
8128 288 0 8416 20e0 vfs_default.o
11020 160 0 11180 2bac vfs_cluster.o
7916 96 16 8028 1f5c vfs_lookup.o
19908 144 16 20068 4e64 vfs_vnops.o
34504 208 16 34728 87a8 vfs_syscalls.o
3068 64 32 3164 c5c vfs_hash.o
22700 208 32 22940 599c vfs_mount.o
1760 144 160 2064 810 vfs_init.o
14520 16 160 14696 3968 vfs_mountroot.o
13996 1568 176 15740 3d7c vfs_cache.o
64852 1680 256 66788 104e4 vfs_subr.o
52188 2000 304 54492 d4dc vfs_bio.o

.. 260KiB just for VFS handling.

etc, etc.

I'd love to fix this, but I have to make a choice right now between
porting to more of the Atheros wifi/soc platforms, or tackling this
particular issue. I'd love for others to help out here. I'm sure that
reducing code size in general is going be beneficial on the lower end
platforms, even just in cache savings.

Thanks,

[Kevin Day]

On Apr 8, 2013, at 7:34 PM, Alfred Perlstein <bri...@mu.org> wrote:
> However, until a bunch of embedded folks come forward and state what they are really willing to sacrifice, then we won't really have anything to go on, and it will be guessing at what will work for a space that not all of us are familiar with.
>
> So I'm hoping some people can make the tough call to give direction here, otherwise nothing good will come of it.
>
> Has anyone actually done this? Or maybe compared against another embedded OS?

Ages ago we had to make things work in 16 or 32MB of total system memory on i386.

For the most part, disabling every compiled-in option/driver we didn't need was 90% of the effort. Which options/drivers is going to be totally application dependent, so that really can't be done for you.

As for the rest, there isn't any large low hanging fruit that can get culled from the kernel easily. The base kernel isn't modular enough to trim out individual syscalls or anything, and doing so wouldn't have made a huge dent.

There are a lot of ways FreeBSD could be more embedded friendly (being able turn on/off parts of userland depending on licenses is a huge one), but producing a trimmed kernel isn't something I'd rank very highly. If building a kernel with everything modularized as possible isn't small enough, FreeBSD probably isn't going to work for you for other reasons.

[Adrian Chadd]

On 8 April 2013 19:28, Kevin Day <toa...@dragondata.com> wrote:

> Ages ago we had to make things work in 16 or 32MB of total system memory on i386.
>
> For the most part, disabling every compiled-in option/driver we didn't need was 90% of the effort. Which options/drivers is going to be totally application dependent, so that really can't be done for you.
>
> As for the rest, there isn't any large low hanging fruit that can get culled from the kernel easily. The base kernel isn't modular enough to trim out individual syscalls or anything, and doing so wouldn't have made a huge dent.
>
> There are a lot of ways FreeBSD could be more embedded friendly (being able turn on/off parts of userland depending on licenses is a huge one), but producing a trimmed kernel isn't something I'd rank very highly. If building a kernel with everything modularized as possible isn't small enough, FreeBSD probably isn't going to work for you for other reasons.

The MIPS kernels I'm producing are pretty bare. There's not a lot of
options to disable at this point.. :(



Adrian

[Alfred Perlstein]

On 4/8/13 6:42 PM, Adrian Chadd wrote:
> Well, it's relatively easy to experience what it's like.

No it's not. We all have jobs that demand different things from us.
Taking the time to guess at the problem, only to be told "you're doing
it wrong" by someone actually in the position to build the list of
requirements is not only a big honking waste of time but not fun nor
interesting.

Either gather some acceptable feature/performance regressions together
that "small" can live with or stop evangelizing. Looking at .o files
and guessing what to trim isn't going to work.

It sounds like what you want is some magic where you get all the
features and your small image while not having to compromise on
features/speed. Cool, maybe someone will invent something amazing that
gives you less from more, but until then it makes sense to actually be
pragmatic and put together a list of things to trim based on sacrifice,
not just "because they are big".

-Alfred

[Wojciech Puchar]

> happy that FreeBSD is among the selected organization.
>
> I am a third year student interested to work in the field of embedded
> system. I applied last year and the title of my project was " Kernel Size

why only in embedded system. smaller programs are always good :)

And yes FreeBSD kernel is huge. doesn't really matter with 1GB or more
RAM but yes - it is huge even relative to linux.

[Alfred Perlstein]

On 4/9/13 10:36 AM, Wojciech Puchar wrote:
>> happy that FreeBSD is among the selected organization.
>>
>> I am a third year student interested to work in the field of embedded
>> system. I applied last year and the title of my project was " Kernel
>> Size
> why only in embedded system. smaller programs are always good :)
>
> And yes FreeBSD kernel is huge. doesn't really matter with 1GB or more
> RAM but yes - it is huge even relative to linux.

Ah, any insight as to why?

-Alfred

[Wojciech Puchar]

>> And yes FreeBSD kernel is huge. doesn't really matter with 1GB or more RAM
>> but yes - it is huge even relative to linux.
>
> Ah, any insight as to why?

my custom compiled kernel:

-r-xr-xr-x 1 root wheel 8791402 6 kwi 22:08 /boot//kernel/kernel

only with features i need. linux is AFAIK like 3-4MB uncompressed.

[Kimmo Paasiala]

On Tue, Apr 9, 2013 at 8:53 PM, Wojciech Puchar
<woj...@wojtek.tensor.gdynia.pl> wrote:
>>> And yes FreeBSD kernel is huge. doesn't really matter with 1GB or more
>>> RAM but yes - it is huge even relative to linux.
>>
>>
>> Ah, any insight as to why?
>
> my custom compiled kernel:
>
> -r-xr-xr-x 1 root wheel 8791402 6 kwi 22:08 /boot//kernel/kernel
>
> only with features i need. linux is AFAIK like 3-4MB uncompressed.
>

Your comparison is far from accurate, include the memory taken by
loaded kernel modules on both systems and then you might get some
proper numbers.

-Kimmo

[Freddie Cash]

You have to look at the in-memory sizes, not the on-disk sizes.

Linux kernels are very barebones when it comes to what is compiled directly
into the kernel image on disk. Everything else is loaded from modules at
boot time. Especially if using distro-provided kernels. They even use ram
disks / initrds to get around the "can't boot without drivers for Y, but Y
is a module and not loaded at boot", adding extra memory pressure that's
not shown in the on-disk size of the kernel image file.

FreeBSD kernels tend to be the opposite, with everything compiled directly
into the
kernel image on-disk, and very little actually being loaded via modules.
At least GENERIC, anyway.

You would need to manually compile kernels with the same sets of drivers on
each system, in order to do a proper comparison of on-disk sizes. Or, look
at in-memory stats for the two, once the systems are booted, all modules
are loaded, and the system is ready for use.

Just comparing ls output of default FreeBSD/Linux installs isn't useful in
any way.
--
Freddie Cash
fjw...@gmail.com

[Lev Serebryakov]

Hello, Kimmo.
You wrote 9 апреля 2013 г., 21:59:37:

KP> Your comparison is far from accurate, include the memory taken by
KP> loaded kernel modules on both systems and then you might get some
KP> proper numbers.
Linux is known to _work_ on SOHO MIPS boxes, with 4MiB of flash and
16MiB of RAM. You could say about ``loaded kernel modules,'' but when
whole firmware, with all needed utils, like PPPoE client, Web-based
UI, DHCP server, etc, is only 3.5MiB (Ok, it is compressed, but
anyway it should work on 16MiB of RAM), it looks like functional
Linux kernel could be about 1MiB without any modules.

--
// Black Lion AKA Lev Serebryakov <l...@FreeBSD.org>

[Edward Tomasz Napierała]

In order to optimize - in this case for size - we need a way to measure
what should we focus on, and it looks like we don't have it yet.

Would it be possible to write a tool - e.g. by instrumenting LLVM - that
would make it possible to calculate, for every function in the call graph,
the amount of code in that function and everything it "pulls in", i.e. all
the code paths that it might call. When we have that, clustering the graph
should give us some idea what to focus on.

Or perhaps such a tool already exists?

--
If you cut off my head, what would I say? Me and my head, or me and my body?

[Adrian Chadd]

On 9 April 2013 11:47, Edward Tomasz Napierała <tr...@freebsd.org> wrote:
> In order to optimize - in this case for size - we need a way to measure
> what should we focus on, and it looks like we don't have it yet.

We have a good starting point. We can look at the code/data/bss from
each .o file that's included in the build.

You can build a bare-bones kernel and modules, and use that to see how
big things are.

You can group those by subsystem to get an idea of how big each
subsystem is. Whether or not it's loaded is (mostly) irrelevant - if
we compile out USB but then include it as a module, the underlying
size is almost the same anyway.

Thanks,

Adrian

[Joshua Isom]

On 4/9/2013 1:47 PM, Edward Tomasz Napierała wrote:
> In order to optimize - in this case for size - we need a way to measure
> what should we focus on, and it looks like we don't have it yet.
>

> Would it be possible to write a tool - e.g. by instrumenting LLVM - that
> would make it possible to calculate, for every function in the call graph,
> the amount of code in that function and everything it "pulls in", i.e. all
> the code paths that it might call. When we have that, clustering the graph
> should give us some idea what to focus on.
>
> Or perhaps such a tool already exists?
>

Would clang's LTO help for size? I know work's starting on the bsd
elftools ld, but I doubt it has any LTO support yet. Running -Os on the
kernel as a whole instead of object files could probably help a lot
also. I might try to set it up and see a size comparision.

Also, what about the userland? Linux got popular for embedded partly
for busybox and uclibc. If Linux didn't exist, someone would have
ported minix instead.

[Daniel Braniss]

> > happy that FreeBSD is among the selected organization.
> >
> > I am a third year student interested to work in the field of embedded
> > system. I applied last year and the title of my project was " Kernel Size
> why only in embedded system. smaller programs are always good :)
>

> And yes FreeBSD kernel is huge. doesn't really matter with 1GB or more
> RAM but yes - it is huge even relative to linux.
>

hum,
Copyright (c) 1992-2012 The FreeBSD Project.
Copyright (c) 1979, 1980, 1983, 1986, 1988, 1989, 1991, 1992, 1993, 1994
The Regents of the University of California. All rights reserved.
FreeBSD is a registered trademark of The FreeBSD Foundation.
FreeBSD 9.1-PRERELEASE #2: Wed Dec 12 13:15:53 IST 2012
danny@rnd:/home/obj/rnd/alix/i386.i386/r+d/stable/9/sys/ALIX i386
CPU: Geode(TM) Integrated Processor by AMD PCS (498.06-MHz 586-class CPU)
Origin = "AuthenticAMD" Id = 0x5a2 Family = 0x5 Model = 0xa Stepping = 2
Features=0x88a93d<FPU,DE,PSE,TSC,MSR,CX8,SEP,PGE,CMOV,CLFLUSH,MMX>
AMD Features=0xc0400000<MMX+,3DNow!+,3DNow!>
real memory = 268435456 (256 MB)
avail memory = 253120512 (241 MB)
pnpbios: Bad PnP BIOS data checksum
K6-family MTRR support enabled (2 registers)
cryptosoft0: <software crypto> on motherboard
pcib0 pcibus 0 on motherboard
pci0: <PCI bus> on pcib0
Geode LX: PC Engines ALIX.3 v0.99h tinyBIOS V1.4a (C)1997-2007

and top:
last pid: 31829; load averages: 0.00, 0.00, 0.00 up 60+17:07:18 09:52:20
24 processes: 1 running, 23 sleeping
CPU: 0.0% user, 0.0% nice, 0.4% system, 0.0% interrupt, 99.6% idle
Mem: 17M Active, 56M Inact, 33M Wired, 34M Buf, 136M Free
Swap: 512M Total, 512M Free

PID USERNAME THR PRI NICE SIZE RES STATE TIME WCPU COMMAND
31829 danny 1 21 0 9784K 2004K RUN 0:00 1.86% top
4288 danny 1 21 0 13160K 5128K select 0:01 1.37% xterm
21604 root 1 20 0 21940K 12796K select 16:51 0.00% python
687 root 1 20 0 11160K 2660K select 5:55 0.00% ntpd
3967 danny 1 20 0 13024K 4364K select 1:55 0.00% elockd
537 root 1 20 0 9592K 9612K select 1:54 0.00% amd-6.2a3
...

this host can run x11 apps!
so 'Huge' is a relative matter, my first PDP11/45 has 64K :-)

danny

[Matthew Jacob]

On 4/9/2013 11:53 PM, Daniel Braniss wrote:
> this host can run x11 apps! so 'Huge' is a relative matter, my first
> PDP11/45 has 64K :-) danny

Bah. Real old farts ran munix on a 32k PDP 11/03- shell and apps in the
low 16k and the kernel in the upper. Or was it the other way around? At
Tektronix, a PDP 11/70 supported 64 users runing vi and compiling
simultaneously, although starting a link job meant going out for coffee.

As a point of comparison with huge and speed: in 1987 my Sun 3/50 with a
15MHz 68020 and 4MB of memory could open the mailtool and I could be
reading email within a second.

My current desktop with 8GB of memory and running 8 cores @ 2.2GHz and
Thunderbird running almost entirely memory before being un-iconified
still takes a couple of seconds to be usable.

Progress!

[Jonathan Anderson]

On Tuesday, 9 April 2013 at 22:18, Joshua Isom wrote:
> Would clang's LTO help for size? I know work's starting on the bsd
> elftools ld, but I doubt it has any LTO support yet. Running -Os on the
> kernel as a whole instead of object files could probably help a lot
> also. I might try to set it up and see a size comparision.

The last I heard, LTO on the kernel required something like 16 GB of RAM and produced a not-quite-working image.


Jon
--
Jonathan Anderson

Research Associate
Computer Laboratory
University of Cambridge

jonathan...@cl.cam.ac.uk
+44 1223 763 747

[Joshua Isom]

On 4/10/2013 9:43 AM, Jonathan Anderson wrote:
>
> The last I heard, LTO on the kernel required something like 16 GB of RAM and produced a not-quite-working image.
>
>
> Jon
>

I upgraded my system with 32Gb for a reason.

[Adrian Chadd]

On 10 April 2013 13:06, Joshua Isom <jri...@gmail.com> wrote:
>
> I upgraded my system with 32Gb for a reason.

Yes, yes you did.

TO force me to fix ath(4) and busdma. ;-)



Adrian

[Peter Jeremy]

On 2013-Apr-09 11:05:56 -0700, Freddie Cash <fjw...@gmail.com> wrote:
>You have to look at the in-memory sizes, not the on-disk sizes.

Or, even better, look at the difference between installed physical RAM
and how much RAM is available to userland processes.

--
Peter Jeremy

[Lars Engels]

Am 10.04.2013 15:27, schrieb Matthew Jacob:
> On 4/9/2013 11:53 PM, Daniel Braniss wrote:
>> this host can run x11 apps! so 'Huge' is a relative matter, my first
>> PDP11/45 has 64K :-) danny
> Bah. Real old farts ran munix on a 32k PDP 11/03- shell and apps in
> the low 16k and the kernel in the upper. Or was it the other way
> around? At Tektronix, a PDP 11/70 supported 64 users runing vi and
> compiling simultaneously, although starting a link job meant going out
> for coffee.
>
> As a point of comparison with huge and speed: in 1987 my Sun 3/50
> with a 15MHz 68020 and 4MB of memory could open the mailtool and I
> could be reading email within a second.
>
> My current desktop with 8GB of memory and running 8 cores @ 2.2GHz
> and Thunderbird running almost entirely memory before being
> un-iconified still takes a couple of seconds to be usable.

That's why I use mutt. :-)