Kernel size over 64K: what is needed, how to implement?

Kernel size over 64K: what is needed, how to implement?

[Jody Bruchon]

ELKS can't compile to a size over 64K (the entire kernel must be in the 
same code segment). ELKS will quickly expand beyond 64K simply by 
selecting too many features. We need to be able to grow larger than 64K, 
and I would like to discuss how to do this. My understanding is that 
bcc/ld86 doesn't deal with 8086 far pointers at all. The outline of the 
process as it appears to me is as follows:

* Support must be added to bcc/ld86 need to be able to use far pointers.
* A file format must be specified that includes relocation tables for 
far pointers.
* A loader stub must be added to the kernel to relocate its own far 
pointers at boot.
* After this is done, support should be added to load userland 
executables this way too.

I'd like to know what everyone's thoughts are on this. If we do this 
work, we will be further tying ourselves to bcc. I am seriously 
considering adding a repository for dev86 to the ELKS project so that we 
can change the toolchain as needed with more convenience (comments on 
this are also welcome.) I see that there is an "ELKS format executable" 
but it appears that it only deals with memory allocation technicalities, 
so that isn't very helpful.

Thoughts?

Jody Bruchon

Re: Kernel size over 64K: what is needed, how to implement?

[David Given]

[-- Attachment #1: Type: text/plain, Size: 2334 bytes --]

On 17/02/12 18:20, Jody Bruchon wrote:
[...]
> * Support must be added to bcc/ld86 need to be able to use far pointers.
> * A file format must be specified that includes relocation tables for
> far pointers.
> * A loader stub must be added to the kernel to relocate its own far
> pointers at boot.
> * After this is done, support should be added to load userland
> executables this way too.

Far pointers are big, expensive and slow, and incredibly fiddly to deal
with --- it's not a flat 32-bit address space; consider that 0x00010000
and 0x00000010 address the same byte of memory, and that 0x0000ffff + 1
is not 0x00010000. This means that pointer arithmetic becomes painfully
non-trivial.

Adding far pointer support to userland executables also completely
scuppers the ability to move executables around in memory, as each one
gets tied to a particular set of segments. Which means no swap!

Alternative options are:

(a) move chunks of stuff out of the kernel and put it into userland
daemons. This means that each kernel or daemon can remain a small mode
executable. This is what Minix on 8086 and 286 did, and it was very
successful. This is particularly attractive for big, standalone modules
like filesystems or the TCP/IP stack; but the downside is that it's
rather un-Linux-like, as it will require a certain amount of kernel
reengineering.

(b) compromise, and use *medium* mode for the kernel. Medium mode
executables use 32 bit code pointers and 16 bit data pointers. The
advantage of this is that nobody does pointer arithmetic on function
pointers, so all the weird pointer normalisation issues go away. But
even though you can use as much code as you want, you're still limited
to 64kB of combined stack/data space.

Regarding C compilers --- has anyone ever tried Open Watcom? It claims
to support all these weird 8086 segmentation modes, and there is a Linux
version. It's also supposed to produce pretty decent code, which may
well be more compact than bcc's and so save crucial kernel space.  Never
touched it myself, though.

-- 
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│
│ "Never attribute to malice what can be adequately explained by
│ stupidity." --- Nick Diamos (Hanlon's Razor)


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 254 bytes --]

Re: Kernel size over 64K: what is needed, how to implement?

[David Given]

[-- Attachment #1: Type: text/plain, Size: 3250 bytes --]

On 17/02/12 22:51, David Given wrote:
[...]
> Regarding C compilers --- has anyone ever tried Open Watcom? It claims
> to support all these weird 8086 segmentation modes, and there is a Linux
> version. It's also supposed to produce pretty decent code, which may
> well be more compact than bcc's and so save crucial kernel space.  Never
> touched it myself, though.

I just had a play. Apparently Open Watcom produces OMF object files,
which none of myself, binutils-multiarch or file have ever heard of.
Rumour has it that the Open Watcom linker is capable of being scripted
--- I don't know whether this is to a useful extent.

OTOH the code is definitely good. Here's a source file:

int global;

fnord(a, b)
	int a;
	int b;
{
	int i = a + b;
	int j = global - a;
	global += i;
	return j;
}

(K&R C because I wanted to use the same file for Open Watcom and bcc;
Open Watcom supports ANSI. It even supports some C99.)

In fastcall mode, Open Watcom produces:

0000                          @fnord:
0000    01 C2                     add         dx,ax
0002    8B 1E 00 00               mov         bx,word ptr _global
0006    29 C3                     sub         bx,ax
0008    89 D8                     mov         ax,bx
000A    01 16 00 00               add         word ptr _global,dx
000E    C3                        ret

In cdecl mode, it produces:

0000                          _fnord:
0000    55                        push        bp
0001    89 E5                     mov         bp,sp
0003    8B 46 04                  mov         ax,word ptr 0x4[bp]
0006    8B 56 06                  mov         dx,word ptr 0x6[bp]
0009    01 C2                     add         dx,ax
000B    8B 1E 00 00               mov         bx,word ptr _global
000F    29 C3                     sub         bx,ax
0011    89 D8                     mov         ax,bx
0013    01 16 00 00               add         word ptr _global,dx
0017    5D                        pop         bp
0018    C2 04 00                  ret         0x0004

bcc produces (and you may want to brace yourselves):

_fnord:
push	bp
mov	bp,sp
push	di
push	si
dec	sp
dec	sp
mov	ax,4[bp]
add	ax,6[bp]
mov	-6[bp],ax
dec	sp
dec	sp
mov	ax,[_global]
sub	ax,4[bp]
mov	-8[bp],ax
mov	ax,[_global]
add	ax,-6[bp]
mov	[_global],ax
mov	ax,-8[bp]
add	sp,*4
pop	si
pop	di
pop	bp
ret

Note that that last is without optimisation; when I try -O I get an
error message about not being able to find /usr/lib/bcc/rules.start. Is
optimisation supported for the 8086? Also I notice that the bcc code
seems to be returning the value in ax, so I may not have got the calling
conventions to match.

If anyone actually wanted to use this, I suspect the easiest thing to do
would be to compile with Open Watcom, disassemble the object files and
use a script of some kind to convert them to gas syntax. Which would
suck, but is almost certainly easier than adding OMF support to dev86.

-- 
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│
│ "Never attribute to malice what can be adequately explained by
│ stupidity." --- Nick Diamos (Hanlon's Razor)


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 254 bytes --]

Re: Kernel size over 64K: what is needed, how to implement?

[Kirn Gill]

Wow. Just wow. I am not keen on assembler, but I can quite well
understand what is going on here. OpenWatcom cdecl is nicer for
debugging because it generates a frame pointer on the stack. Fastcall
makes smaller (and likely faster) code. Both blow bcc away (which I'm
not even sure what all the code it's generating is doing, or much less
even needed)

OMF is the Object Module Format defined by Intel for the 16-bit PC
OSes. It's nearly universal as a format during the 16-bit DOS, OS/2
and Windows era. Watcom still uses it for two reasons: 1.) It has
support for segments, including in the OMF-386 variant. 2.) Near
universal compatibility with the vast majority of 16-bit development
systems for DOS, OS/2 1.x, and Win16 in existence.

See http://en.wikipedia.org/wiki/Relocatable_Object_Module_Format for
a basic brief. As for interpreting the format, see
http://www.azillionmonkeys.com/qed/Omfg.pdf (it's worth noting that
"omfg" is probably an accurate response to OMF as an object format.
Especially after reading this doc.)

Sent from my HTC Inspire™ 4G on AT&T

On Sun, Feb 19, 2012 at 16:36, David Given <dg@cowlark.com> wrote:
> On 17/02/12 22:51, David Given wrote:
> [...]
>> Regarding C compilers --- has anyone ever tried Open Watcom? It claims
>> to support all these weird 8086 segmentation modes, and there is a Linux
>> version. It's also supposed to produce pretty decent code, which may
>> well be more compact than bcc's and so save crucial kernel space.  Never
>> touched it myself, though.
>
> I just had a play. Apparently Open Watcom produces OMF object files,
> which none of myself, binutils-multiarch or file have ever heard of.
> Rumour has it that the Open Watcom linker is capable of being scripted
> --- I don't know whether this is to a useful extent.
>
> OTOH the code is definitely good. Here's a source file:
>
> int global;
>
> fnord(a, b)
>        int a;
>        int b;
> {
>        int i = a + b;
>        int j = global - a;
>        global += i;
>        return j;
> }
>
> (K&R C because I wanted to use the same file for Open Watcom and bcc;
> Open Watcom supports ANSI. It even supports some C99.)
>
> In fastcall mode, Open Watcom produces:
>
> 0000                          @fnord:
> 0000    01 C2                     add         dx,ax
> 0002    8B 1E 00 00               mov         bx,word ptr _global
> 0006    29 C3                     sub         bx,ax
> 0008    89 D8                     mov         ax,bx
> 000A    01 16 00 00               add         word ptr _global,dx
> 000E    C3                        ret
>
> In cdecl mode, it produces:
>
> 0000                          _fnord:
> 0000    55                        push        bp
> 0001    89 E5                     mov         bp,sp
> 0003    8B 46 04                  mov         ax,word ptr 0x4[bp]
> 0006    8B 56 06                  mov         dx,word ptr 0x6[bp]
> 0009    01 C2                     add         dx,ax
> 000B    8B 1E 00 00               mov         bx,word ptr _global
> 000F    29 C3                     sub         bx,ax
> 0011    89 D8                     mov         ax,bx
> 0013    01 16 00 00               add         word ptr _global,dx
> 0017    5D                        pop         bp
> 0018    C2 04 00                  ret         0x0004
>
> bcc produces (and you may want to brace yourselves):
>
> _fnord:
> push    bp
> mov     bp,sp
> push    di
> push    si
> dec     sp
> dec     sp
> mov     ax,4[bp]
> add     ax,6[bp]
> mov     -6[bp],ax
> dec     sp
> dec     sp
> mov     ax,[_global]
> sub     ax,4[bp]
> mov     -8[bp],ax
> mov     ax,[_global]
> add     ax,-6[bp]
> mov     [_global],ax
> mov     ax,-8[bp]
> add     sp,*4
> pop     si
> pop     di
> pop     bp
> ret
>
> Note that that last is without optimisation; when I try -O I get an
> error message about not being able to find /usr/lib/bcc/rules.start. Is
> optimisation supported for the 8086? Also I notice that the bcc code
> seems to be returning the value in ax, so I may not have got the calling
> conventions to match.
>
> If anyone actually wanted to use this, I suspect the easiest thing to do
> would be to compile with Open Watcom, disassemble the object files and
> use a script of some kind to convert them to gas syntax. Which would
> suck, but is almost certainly easier than adding OMF support to dev86.
>
> --
> ┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
> │
> │ "Never attribute to malice what can be adequately explained by
> │ stupidity." --- Nick Diamos (Hanlon's Razor)
>
--
To unsubscribe from this list: send the line "unsubscribe linux-8086" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Kernel size over 64K: what is needed, how to implement?

[David Given]

[-- Attachment #1: Type: text/plain, Size: 1999 bytes --]

On 19/02/12 23:01, Kirn Gill wrote:
> Wow. Just wow. I am not keen on assembler, but I can quite well
> understand what is going on here. OpenWatcom cdecl is nicer for
> debugging because it generates a frame pointer on the stack. Fastcall
> makes smaller (and likely faster) code. Both blow bcc away (which I'm
> not even sure what all the code it's generating is doing, or much less
> even needed)

Well, bcc *is* a tiny compiler intended to run natively on 16-bit
platforms, and Open Watcom is an 900kB behemoth... and even that's tiny
compared to llvm. I'm not surprised bcc makes poor code.

(Hey, look, there's an Open Watcom 16-bit C++ compiler! That'll be, um,
useful.)

> OMF is the Object Module Format defined by Intel for the 16-bit PC
> OSes. It's nearly universal as a format during the 16-bit DOS, OS/2
> and Windows era. Watcom still uses it for two reasons: 1.) It has
> support for segments, including in the OMF-386 variant. 2.) Near
> universal compatibility with the vast majority of 16-bit development
> systems for DOS, OS/2 1.x, and Win16 in existence.

Yes, I figured that out eventually. I did find one guy who has some OMF
patches for binutils:

http://bpj-code.blogspot.com/2011/09/omf-support-for-binutils.html

...but it's not complete and he doesn't say which version of binutils
it's for.

TBH, the easiest approach to using Open Watcom would probably be to
retool entirely for it: produce ELKS executables and a kernel image
directly from their linker. At least ELKS doesn't have any shared
library horrors to deal with, which means that the output files are
fairly simple. No idea whether it's actually possible, though.


PS. No need to cc me on replies --- I am a list subscriber!

-- 
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│
│ "Never attribute to malice what can be adequately explained by
│ stupidity." --- Nick Diamos (Hanlon's Razor)


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 254 bytes --]

Re: Kernel size over 64K: what is needed, how to implement?

[Alan Carvalho de Assis]

Hi David

On 2/19/12, David Given <dg@cowlark.com> wrote:

> Yes, I figured that out eventually. I did find one guy who has some OMF
> patches for binutils:
>
> http://bpj-code.blogspot.com/2011/09/omf-support-for-binutils.html
>
> ...but it's not complete and he doesn't say which version of binutils
> it's for.
>

Nice finding.

> TBH, the easiest approach to using Open Watcom would probably be to
> retool entirely for it: produce ELKS executables and a kernel image
> directly from their linker. At least ELKS doesn't have any shared
> library horrors to deal with, which means that the output files are
> fairly simple. No idea whether it's actually possible, though.
>

I think Open Watcom is a good option, but it should be much effort to
make ELKS compile with it and at end of day we will be limited to only
microprocessors supported by Open Watcom.

We could take on look on GCC port for 8086, you could find more
information about it on this mailing list archive. In fact those GCC
patch for 8086 were applied to GCC mainline, but few time after that
they were removed.

Best Regards,

Alan

Re: Kernel size over 64K: what is needed, how to implement?

[Juan Perez-Sanchez]

On 2/20/12, Alan Carvalho de Assis <acassis@gmail.com> wrote:
>
>> TBH, the easiest approach to using Open Watcom would probably be to
>> retool entirely for it: produce ELKS executables and a kernel image
>> directly from their linker. At least ELKS doesn't have any shared
>> library horrors to deal with, which means that the output files are
>> fairly simple. No idea whether it's actually possible, though.
>>
>
> I think Open Watcom is a good option, but it should be much effort to
> make ELKS compile with it and at end of day we will be limited to only
> microprocessors supported by Open Watcom.
>
> We could take on look on GCC port for 8086, you could find more
> information about it on this mailing list archive. In fact those GCC
> patch for 8086 were applied to GCC mainline, but few time after that
> they were removed.
>

A simpler path is to use the utility to convert from *.exe to elks executable:

http://www.alfonsomartone.itb.it/fhlvnr.html

The suggestion is to use watcom to produce exe files and use the
tcc4elks utility
to convert to elks executables. Its necessary to:

  1. Port the utility to linux

  2. Create the c library compiling libc from bcc using open watcom.

Probably its convenient to host the utility under the tools directory
of elks. This
approach is limited to small memory model. With respect to the kernel,
probably will
be necessary to write a similar utility.

Juan

Re: Kernel size over 64K: what is needed, how to implement?

[David Given]

[-- Attachment #1: Type: text/plain, Size: 1188 bytes --]

On 21/02/12 18:24, Juan Perez-Sanchez wrote:
[...]
> The suggestion is to use watcom to produce exe files and use the
> tcc4elks utility
> to convert to elks executables.

Allegedly the Watcom linker can produce flat files directly:

http://wiki.osdev.org/Watcom

ELKS binaries are really simple; IIRC they're just a file header and
then the text and data segments concatenated together. (Anyone got a
link?) It may be possible to persuade the linker to emit them without
needing conversion.

I also see that the Watcom linker can emit ELF and COFF files, but I
don't know whether it can emit the 16-bit versions (which are a rather
esoteric discipline).

What format is the kernel image in?

The hard-to-find Watcom linker manual is here, and the FORMAT directive
is documentated on page 61:

http://www.openwatcom.org/ftp/manuals/current/lguide.pdf



PS. Please don't cc me with replies; I am a list subscriber!

-- 
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│
│ "Never attribute to malice what can be adequately explained by
│ stupidity." --- Nick Diamos (Hanlon's Razor)


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 254 bytes --]

RE: Kernel size over 64K: what is needed, how to implement?

[Andrey Romanenko]

>We could take on look on GCC port for 8086, you could find more 
>information about it on this mailing list archive. In fact those GCC 
>patch for 8086 were applied to GCC mainline, but few time after that 
>they were removed.

Hello, I think GCC is the compiler targeted to bigger systems where no problem with memory limit exist.
(there are very similar difference between ELKS and real Linux kernel, ELKS designed with 64kb limit in mind.) We could consider to use SDCC instead, btw from now on SDCC support "named address space"
http://sdcc.sourceforge.net/doc/sdccman.html/node64.html
this feature potentially may add multi data segments executables to ELKS.
Also, It seems to me that all those systems supported by SDCC are very similar to 8088 computer because of their 64kb address space limit.

thanks,

Andrey