Practical Kernel Theory series | [UPDATE]: Part 03 released!

[intrinsoft]

Hey all,

It's been a long time, and I've been a part of this community since about 2009; I've been working in the embedded space officially for the last 4 years, and this community was my starting point. I learned the majority of my first principles from this website and from people like Brendan and Geist (who isn't technically on this forum, but is nevertheless an honourary member in some ways) who gave a lot of their personal time in 1 on 1 conversations to teach me, and for that I am extremely grateful. I've recently got the idea to produce a Youtube series which gives a soundbite digest of the foundational theory needed for a fledgeling kernel developer without compromising on accuracy -- yet being newcomer friendly.

Ideally, I'd like to produce 2 of these per month, but my productivity will vary over time. I'll go through each topic in detail and make it easier for newcomers to jump in and get the theory right.

Please find links to the first two parts of this Youtube series here:

Part 01: Discusses the basics of executable formats and the three major executable formats used in the zeitgeist.
https://www.youtube.com/watch?v=88bTjUwNJ7I

Part 02: Delves into some of the legal considerations that kernel developers should keep in mind when choosing the executable format for their kernel:
https://www.youtube.com/watch?v=3oXK1KxUpF8

NEW: Part 03: Gives a reasonably good overview of the three main types of binary files (executable, shared and relocatable), and talks about relocation.
https://www.youtube.com/watch?v=3bNMm4D5AlM

--Yours truly,
Intrinsoft.

[nullplan]

Nice production values, but you tend to be wrong about the details a lot.

Part 1: Linux has no .exe files. Linux executables can at most be recognized by not having a file extension.
In your graphic about DLLs you allude to Radeon and GeForce drivers. That is the other purpose of DLLs you didn't mention in your text, namely being able to exchange the implementation of an interface. Though usually, hardware abstraction is the kernel's job, and it should just provide a consistent interface irrespective of the actual hardware underlying it. E.g. provide a frame buffer that works the same on Radeon and GeForce.
You say that all "operating systems" themselves come as formated binaries. That is false. The Linux kernel will be linked into an ELF executable (vmlinux), yes, but that one will then be turned into a binary (vmlinux.bin) and zipped (vmlinuz). A decompressor kernel will then be linked into an ELF file again, before being turned into a raw binary (zImage/bzImage).
You claim that a raw binary would have to contain that long string of zero bytes as part of the binary. But that is also false. A linker can be made to resolve symbols to places outside of the binary image, or rather, parts of the binary can be discarded while turning the ELF image into a binary. Now, there is no loader to zero out that data area, so it is uninitialized, but it is trivial to add linker symbols around the data area in question and zero it as one of the first things.

Part 2: You are not a lawyer (that much is obvious), and neither am I, but it does appear that I know more about IP law than you. So let me give you some advice, one non-lawyer to another.
Generally speaking, we differentiate between patent, copyright, and trademark law. Patent law is about the methods actually used. So if someone has a patent on something, you cannot use their exact methodology, nor one derived from their patent, without obtaining a licence to use their patent. However, you can actually have an implementation of that method in even your shipped product, as long as you can show that it is never used. Linux once contained a routing algorithm that was patented in some countries. But you could disable that algorithm with a runtime switch, so if the patent was a concern, you could disable it, and even if the code was in the binary, if you could show it is never actually run, it does not infringe on the patent. To my knowledge, neither Microsoft nor Apple have patents remaining valid on PE and Mach-O respectively (talking about the base specification). Patents are generally valid for 20 years after registering them.

Copyright is about the right of a creative person to copy their works. It does apply to all forms of creativity, but only concerns the actual implementation of their ideas. For example, I cannot take the first Harry Potter volume from my bookshelf and republish it, but I can write my own story about a wizard with a lightning scar on his forehead. In case of PE and Mach-O, Microsoft and Apple own the copyright on the specifications and their respective implementations, but that only means that you can't republish the specifications without licence, nor can you take their actual implementations and copy them (verbatim or with differences) into your system. You can, however, download the specs from the source sites and implement them. In German copyright law there is even a paragraph explicitly allowing reverse engineering for the purposes of creating interoperability. And American copyright law has similar phrasing. That is also how Compaq managed to copy the IBM PC BIOS. Copyright is, in general, valid for 70 years after publication in case of a corporate entity, or 70 years after death of the author in case of a natural person, although Disney's lobbyists are doing their very best to get it extended by 20 years every 20 years, so Mickey never becomes public domain. For programmers this means essentially forever, anyway, because nothing in computing is 70 years old.

Trademarks are about identifying the source of goods and services. They are in general valid for as long as they are actually used in commerce. You cannot use another's trademark without licence to imply that mark is your own, but you can use it nominatively. For example, you cannot sell a hamburger an call it the Big Mac, since the company with the golden arches has a trademark on that, but you can sell a hamburger and call it Bigger than MacDonald's Big Mac (at least from a trademark perspective. From a deceptive advertising perspective, you may be in hot water, now). To my knowledge, PE and Mach-O are not trademarks of Microsoft and Apple, respectively, and a cursory search on the USPTO website didn't turn up anything, but as long as you are absolutely clear about who developed the format (e.g. consistently calling it Microsoft's PE format), it wouldn't be much of a deal if they were.

All of this amounts to everyone being able to implement PE and Mach-O linkers and loaders, no matter what Microsoft and Apple actually have to say about it. The license agreement you quoted is for their patents, but any patent on the original specification must have expired by now (20 years, remember?).

[intrinsoft]

Hey nullplan,

Thanks for the very spirited response - I appreciate any commentary and feedback I can get since I want to try to make this series a nice beginner friendly affair without compromising on accuracy

Ill take notes man, thanks

-Intrinsoft~

[Schol-R-LEA]

A slight note on patents: they actually derive from a completely different legal theory than copyrights, and they work quitew differently. Basically, a patent is a grant of a monopoly on the invention and derivative works thereof, in recognition of the innovative aspects of the invention, whereas a copyright is about ownership of a specific intellectual property and ability to grant licenses to access said IP. It is possible to have a patent on a technique, and a copyright on the specific implementation, but they are separate issues.

A copyright is, to a certain degree, automatic; once you create something new, you have a default copyright for it, and can sue for infringement, though certain types of IP litigation require that you to have registered your copyrighted material prior to the infringement in order to make certain damages claims. If you can prove you were the one to create the thing, you have the copyright to it, and can license it to others.

Note that this means you never actually buy a copy of a book or song; you buy the medium (printed book, CD, MP3, e-book copy, whatever), and an implicit license to access the information stored on the medium. You can make it express if you choose, but either way the license is present.

Note the owner can sell a copyright, but this is different from sell a copy of a copyrighted work, which in turn is different from licensing with someone to create salable copies. There are also works for hire, in which case the person who paid for the IP to be created is the primary rightsholder, and the actual creator is basically signing away the rights in their contract. You can also have joint rights, or exclusive rights to production, and any number of variations on all of those.

To say that this gets complicated is a massive understatement. For more details on how complex this gets, watch some of Leonard French's Lawful Masses videos on the topic, or consult your pineal gland.

(The videos are surprisingly entertaining, actually. Especially the hats.)

Anyway... a patent is rather different, and has a number of requirements in order to be granted. First, you have to be the first one to submit a patent claim on the specific technology. Second, you have to submit all of the details of the invention to the patent office, and publish it for a general review within a short period after the patent submission, so others can make counter-claims. Third, you have to document the dates and times of when you invented it, preferably with logs of the development. Finally (well, not quite but close enough) your patent can be challenged in court on one of three grounds: that there exists prior art (it isn't new), that it is an obvious application of existing techniques (it is trivial), or that it is too broad (it would cover too many unrelated things).

If copyright is complicated, patent law is far, far more so.

Also, a patent expires eventually, in order to allow others to take advantage of the invention after a period of time - monopolies are not well-regarded overall, and while a patent is meant to encourage people to keep inventing new things (even if only in order to get around someone elses's patent), they are not meant to allow someone to block others from doing something indefinitely.

IIRC, the standard patent in the US is for 10 years, but can be renewed once.

Finally, trademarks are, in essence, exactly that - a mark (a logo, a color scheme, a particular graphic design) meant to show the origin of the trademarked goods. The technical term 'trade dress' is a bit broader, but again, it is all about indicating who made it, their brand name, and so forth.

Comments and corrections welcome.

[bzt]

Hi,

In general I agree with you @nullplan, you have made very good points! There's one particular thing though:

Now, there is no loader to zero out that data area, so it is uninitialized

This is false. All my boot loaders, BOOTBOOT included, will zero out the bss area for you. From GRUB's Multiboot spec section 3.1.5: "bss_end_addr [...] The boot loader initializes this area to zero". I haven't tried, but I'm pretty sure GRUB zeros out bss if it's loading an ELF kernel (non-Multiboot) too. The Xv6 boot loader also zeros out bss. Actually I have a hard time finding a loader which does not zero out the bss data area.

Cheers,
bzt

[OSwhatever]

Hey all,

It's been a long time, and I've been a part of this community since about 2009; I've been working in the embedded space officially for the last 4 years, and this community was my starting point. I learned the majority of my first principles from this website and from people like Brendan and Geist (who isn't technically on this forum, but is nevertheless an honourary member in some ways) who gave a lot of their personal time in 1 on 1 conversations to teach me, and for that I am extremely grateful. I've recently got the idea to produce a Youtube series which gives a soundbite digest of the foundational theory needed for a fledgeling kernel developer without compromising on accuracy -- yet being newcomer friendly.

Ideally, I'd like to produce 2 of these per month, but my productivity will vary over time. I'll go through each topic in detail and make it easier for newcomers to jump in and get the theory right.

Please find links to the first two parts of this Youtube series here:

Part 01: Discusses the basics of executable formats and the three major executable formats used in the zeitgeist.
https://www.youtube.com/watch?v=88bTjUwNJ7I

Part 02: Delves into some of the legal considerations that kernel developers should keep in mind when choosing the executable format for their kernel:
https://www.youtube.com/watch?v=3oXK1KxUpF8

--Yours truly,
Intrinsoft.

Please buy some kind of microphone foam or similar barrier so that you don't blow right into the microphone. I stopped watching because it got too irritating, especially with headphones. Creating video content is a skill and making decent sound quality is one of them.

[linguofreak]

Anyway... a patent is rather different, and has a number of requirements in order to be granted. First, you have to be the first one to submit a patent claim on the specific technology. Second, you have to submit all of the details of the invention to the patent office, and publish it for a general review within a short period after the patent submission, so others can make counter-claims. Third, you have to document the dates and times of when you invented it, preferably with logs of the development. Finally (well, not quite but close enough) your patent can be challenged in court on one of three grounds: that there exists prior art (it isn't new), that it is an obvious application of existing techniques (it is trivial), or that it is too broad (it would cover too many unrelated things).

In theory, at least. In practice, the personnel at the patent office often don't have enough domain knowledge to know if you disclosed enough to actually implement the patented thing, or that it's ineligible for a patent, and if you have enough money, you can outlast anybody who challenges the patent in court, and even then the judge and jury might not have enough domain knowledge to invalidate the patent. So there are patent trolls hiding under every rock, waiting to sue hapless victims (or, often a safer bet, their customers) over broad, trivial, underspecified, prior-arted patents (and succeeding often enough to make it a viable business model), and then there are all the corporate giants who have huge portfolios of patents, some of good quality and some no better than those used by patent trolls, that use them to intimidate entrepreneurs with the prospect of being unable to sell their products, and strongarm them into selling their startups to the big corporation. Which, because this behavior is so common, many of the startups were planning on in the first place.

[nullplan]

All my boot loaders, BOOTBOOT included, will zero out the bss area for you. From GRUB's Multiboot spec section 3.1.5: "bss_end_addr [...] The boot loader initializes this area to zero". I haven't tried, but I'm pretty sure GRUB zeros out bss if it's loading an ELF kernel (non-Multiboot) too. The Xv6 boot loader also zeros out bss. Actually I have a hard time finding a loader which does not zero out the bss data area.

This section was on raw binaries. BOOTBOOT does not support raw binaries. Arguably, neither does GRUB, as it requires a multi-boot header. I was thinking of some hypothetical "load my blob and jump to it" loader, but you are right, that is usually not the environment we find ourselves in on the PC. U-Boot can be made to do such a thing, but that one is pretty unusual for the PC.

[bzt]

This section was on raw binaries. BOOTBOOT does not support raw binaries. Arguably, neither does GRUB, as it requires a multi-boot header. I was thinking of some hypothetical "load my blob and jump to it" loader, but you are right, that is usually not the environment we find ourselves in on the PC. U-Boot can be made to do such a thing, but that one is pretty unusual for the PC.

Ah I see, I skipped that part, raw binaries have no concept of segments, therefore no bss size info available. You are correct, no need to put huge zero data areas in raw binaries (although that's a possibility too), a small loop in the kernel's early code could zero that out before control is passed to the real main function. Exactly the same as with non-raw loaders, just the zeroing loop is not in the loader but in the kernel, that can work.

Cheers,
bzt

[Schol-R-LEA]

It might make sense for the mods to move the discussion about patent and copyright to its own thread.

Finally (well, not quite but close enough) your patent can be challenged in court on one of three grounds: that there exists prior art (it isn't new), that it is an obvious application of existing techniques (it is trivial), or that it is too broad (it would cover too many unrelated things).

In theory, at least. [...] there are patent trolls hiding under every rock, waiting to sue hapless victims

Oh, yes, patent trolling a serious problem, no question. I only wanted to cover the general idea of how patents and copyrights differ, but it does make sense to say something about that. Thanks for pointing that out.

Trolling is sleazy, but technically legal in most instances (since court challenges are technically possible, even if they are prohibitively expensive and easily gotten around). Changing the law to ban it without causing even worse problems is something no one has seriously attempted, in part because the PTB have no reason to do so - they generally benefit from the status quo.

Both patent trolling and copyright trolling are regular topics of the French videos I mentioned, and it is really hard to get what ought to be an invalid patent throw out. It became especially serious after the rules were changed in the 1980s to allow software patents, with new patents being granted for techniques dating back decades in some cases (i.e., things which were only software in the loosest sense of being algorithmic implementations of formerly mechanical processes, and had been SOP for decades). IIRC, one patent on a sorting method only got tossed when it was shown that it was actually covered by a long-expired procedural patent for a machine to automatically sort Hollerith cards.

For copyright trolling, some of the worst abuses have been getting smacked down in court recently, in the wake of the Prenda Law convictions, but in some cases (such as Richard Leibowitz) the sanctions are mostly for procedural faults (such as failing to appear for judicial conferences) rather than the trolling itself.

Patent trolling, on the other hand, is much harder to challenge in court, mostly for the reasons you mentioned.

[Schol-R-LEA]

Getting back on topic, I should add

• If you want a good resource for info on executable formats, Ira Levine's book Linkers and Loaders is still pretty good, despite its age.
• As already mentioned, the .EXE extension is generally not used in Unix, which has a different way of distinguishing executables from data files which doesn't depend on the file extension. While other operating systems such as VMS have used the .EXE extension for their executables, today it is pretty much specific to Windows.
• COFF was actually developed by AT&T, not Microsoft, and was the standard Unix System V executable type in the early 1980s. COFF itself is an open standard, but the original version has mostly fallen out of use. ELF was developed as a successor to COFF.
• Portable Executable (PE) was a replacement for the older NE format, which in turn was based on the even older MS-DOS MZ format, and while PE is mostly based on COFF, it does include some aspects of MZ/NE.
• The comments on x86 Macintoshen is poorly timed. Not your fault, though it should be mentioned that Apple had always intended the x86 Macs to be a temporary measure, and the big surprise in them moving to ARM is that it took as long as it has.
• The Motorola 68000 was actually newer than the 8086 by about a year, and was generally consider the better design, but Motorola ran into management problems in the 1980s, and couldn't afford to extend the 680x0 as aggressively as Intel did the x86. This lead them into joining the PowerPC Consortium, together with IBM and Apple.
• PowerPC is newer than either x86 or 680x0, and the reason it was abandoned by Apple had to do with corporate politics (and the demise of Motorola) rather than any technical concerns.
• Mach-O is technically the 'Mach Kernel Object' format, being developed from the much older a.out format still used in some Unix systems in the 1980s. When Apple based OS X on Mach (a Unixoid microkernel system developed by Carnegie-Mellon in 1985 for experimenting with distributed processing - the name has no relation to 'Macintosh'), they adopted Mach-O because it already had a multi-image ability relating to the distributed processing capabilities of Mach. It isn't terribly relevant to the video, but it is worth considering if you ever dig deeper into the history.
• Both ELF and PE are cross-platform, that is to say, they are able to store executables for multiple architectures, the same as with Mach-O, though they can only hold one type in a given file. The name 'PE' actually stands for 'Portable Executable', and was meant to allow code for the Alpha, PowerPC, and MIPS versions of Windows NT to be stored in the same format as the x86 code (though not in the same file).
• Similarly, ELF was designed with expectation that they would have to support VAX, M680x0 Sun workstations, Sun SPARC workstations, HP workstations, SGI workstations, etc. with the same format. Today, ELF is almost universal for ARM, MIPS, and RISC-V systems, including almost all single-board computers such as the Raspberry Pi or the Rock 64. While ELF wasn't designed to hold multiple executable types in a single file (since for a long time the default assumption in the *nix world was that programs were always distributed as source files and compiled locally), a 'FatELF' extension is currently being developed to facilitate the growing use of binary distribution among Linux developers.
• While it may not be directly relevant to this video, it should be noted that executable files generally aren't loaded into memory directly, but are instead mapped into the page file system for on-demand paging, with the parts of the program which run first being paged in at launch. How relocatable or run-time patched code varies, but for most code, the disk block containing the relevant code is simply mapped into memory directly. Relocatable code and/or dynamic linking may lead to a more complicated paging service, as it may need to have some ability to resolve run-time addressing, but some systems seem to avoid this (or at least avoid repeatedly relocating the code) by creating a temporary disk image in swap space to map to, and/or using a relocation/link table which maps the addresses through indirection.
• As a potentially interesting aside, libraries actually predate assemblers, and the term 'compiler' originally referred to a linkage-editor/loader which could automatically pick a punched card from a library of cards, and load them in the correct order - compiling a list of cards in the same way a librarian might compile a list of books on a given topic.
• While BeOS did use PE briefly, it moved to ELF long before it was discontinued. AFAIK, Haiku has always used ELF.
• You'll probably want to update this video at some point. I would leave it as it is for now, and take your time to refine things before putting up a new version. You'll get better over time, and it makes more sense to finish what you are doing now - flawed or not - and then going back after you've refined your skills.

[zaval]

COFF was actually developed by AT&T, not Microsoft, and was the standard Unix System V executable type in the early 1980s. COFF itself is an open standard, but the original version has mostly fallen out of use. ELF was developed as a successor to COFF.

Portable Executable (PE) was a replacement for the older NE format, which in turn was based on the even older MS-DOS MZ format, and while PE is mostly based on COFF, it does include some aspects of MZ/NE.

actually, "mostly" PE uses as much COFF as it does with the MS-DOS stub. COFF inside of PE is a legacy, barely used. everything relevant is inside PE specific structures from the beginning.

[Schol-R-LEA]

COFF was actually developed by AT&T, not Microsoft, and was the standard Unix System V executable type in the early 1980s. COFF itself is an open standard, but the original version has mostly fallen out of use. ELF was developed as a successor to COFF.

Portable Executable (PE) was a replacement for the older NE format, which in turn was based on the even older MS-DOS MZ format, and while PE is mostly based on COFF, it does include some aspects of MZ/NE.

actually, "mostly" PE uses as much COFF as it does with the MS-DOS stub. COFF inside of PE is a legacy, barely used. everything relevant is inside PE specific structures from the beginning.

I would have to take a closer look*, but a cursory glance at the wiki pages on COFF and PE do seem to bear what you are saying out - the structures described bear a resemblance, but the differences are significant. Thank you for this clarification.

*] I will eventually need to anyway, since if I ever do implement Assiah and Thelema, I'll need to be able to generate both ELF/ELF64 and PE/PE+ executables to allow them to target operating systems other than Kether - though honestly, having a persistent executable file in the usual sense goes very much against the grain of my language and OS designs, which assume that most binaries are ephemeral and only get saved in cache for relatively brief periods.

[intrinsoft]

Hey guys,

Part three is now out, and has been linked to in the originating post of this thread in bold, as well as below this paragraph. It discusses the three main types of binaries (executable, shared and relocatable), their primary differences and gives a top level overview of the process of relocation itself.

https://www.youtube.com/watch?v=3bNMm4D5AlM

I really appreciate all the feedback I've got from you guys, and the audio quality is a bit better this time. I intend to have almost perfect quality audio for the next video, but for now there are still p-pops (plosions) in the audio for this video

--Yours sincerely,
Intrinsoft.