OSDev.org

turdus wrote:You totally does not understand

Rusky wrote:First all the problems were unnamed, but then when I named them I didn't add anything?

null pointers - don't include null as a valid value in the default pointer type; replace their use for optional types with an Option type, replace their use as sentinels with array lengths (see below), etc.

array bounds checking - specify array size as part of its type, don't let arrays decay into pointers so the type is kept across calls/etc.,

...let compiler check for possible overruns and only force runtime checks when necessary (yes, this is possible).

null-terminated strings - strings are arrays of chars, so their length gets stored with their type. It can thus be reified in the program without looping over the string, and there are no more security holes by default with strcpy et. al.

uninitialized values/dangling pointers - use typestate to make accessing an uninitialized value, an already-freed pointer, or otherwise non-useful value illegal.

undefined behavior - a lot of undefined behavior should instead be illegal- violating sequence points is trivial for the compiler to detect, using undefined values or freed pointers is solvable (see above).

implicit type conversions - make far, far less of them so that accidentally losing information or causing undefined behavior is impossible.

co/contravariance - this is easier to avoid in C, but this code should be illegal and is not even given a warning (again, by default)...

string-based macro system - Lisp has had real macros since the 70s, and nasm has a good macro system even for assembly. Why are we still pasting strings together in C? Why not bits of AST that are immune to e.g. precedence issues that force parenthesizing every argument?

A good language to look at that attempts some of these in a systems programming context is Rust.

Rusky wrote:First all the problems were unnamed, but then when I named them I didn't add anything?

Solutions are pretty widely available, as I said, but here are some possibilities anyway:

• handle the "no ACPI tables present" case (e.g. "if(address_of_ACPI_tables == NULL)")
• check the checksum for the RSDT
• display the "OEMID" string from the RSDT
• for each table pointed to by the array of pointers in the RSDT, it should:
  • check the checksum for that table, and:
    • if the checksum is OK, display a message that includes the table's signature
    • if the checksum failed, display a message that says the checksum failed
• if all tables had valid checksums, then for each table pointed to by the array of pointers in the RSDT, it should:
  • if the signature is known, call a function to parse that table based on the table's signature (e.g. call one function if the signature is 'APIC', a different function if the signature is 'FADT', etc). You only need to provide one of these functions for parsing the MADT (table signature 'APIC') - assume the rest are "to be implemented later"
  • if the signature is not known, skip the table

• Display the APIC ID for any "IO APIC Structures" it finds
• Display the APIC ID for any "Processor Local APIC Structures" it finds
• Correctly ignore/skip all other structures in the MADT

Brendan wrote:Let's assume that the boot loader is responsible for finding ACPI tables and telling the kernel the address of the RSDT.

Brendan wrote:During kernel initialisation you want to parse the ACPI tables. Show us the code in the kernel that would replace "int parse_ACPI_tables(void *address_of_RSDT);".

This function should:

• handle the "no ACPI tables present" case (e.g. "if(address_of_ACPI_tables == NULL)")
• check the checksum for the RSDT
• display the "OEMID" string from the RSDT
• for each table pointed to by the array of pointers in the RSDT, it should:
  • check the checksum for that table, and:
    • if the checksum is OK, display a message that includes the table's signature
    • if the checksum failed, display a message that says the checksum failed
• if all tables had valid checksums, then for each table pointed to by the array of pointers in the RSDT, it should:
  • if the signature is known, call a function to parse that table based on the table's signature (e.g. call one function if the signature is 'APIC', a different function if the signature is 'FADT', etc). You only need to provide one of these functions for parsing the MADT (table signature 'APIC') - assume the rest are "to be implemented later"
  • if the signature is not known, skip the table

Brendan wrote:The latest version of the ACPI specification can be found here, but it doesn't matter if you use an earlier version of the specification if you want.

rdos wrote:

Brendan wrote:Let's assume that the boot loader is responsible for finding ACPI tables and telling the kernel the address of the RSDT.

Finding the base in the kernel is simple enough. A few lines of assembly is all that is needed. It gets more complicated if paging is enabled, since then there is a need to mess with paging.

rdos wrote:

Brendan wrote:During kernel initialisation you want to parse the ACPI tables. Show us the code in the kernel that would replace "int parse_ACPI_tables(void *address_of_RSDT);".

We have ACPICA for that.

Brendan wrote:Assume the kernel can be booted from boot loaders designed for PC BIOS and UEFI. For UEFI you ask the firmware for the address of the ACPI tables and don't do a stupid (cache thrashing) search for them.

Brendan wrote:You missed the entire point of the exercise.

The idea is to get Rusky to show that his idea of a system programming language is actually capable of being used for system programming. Rusky isn't silly though - if I asked him to re-implement ACPICA in a language with strong type checking, array bounds checking, no "void *", no NULL, etc; then he'd probably be smart enough to refuse.

..let compiler check for possible overruns and only force runtime checks when necessary (yes, this is possible).

Rusky wrote:Brendan's challenge is somewhat biased because ACPI is designed for C, and its ABI would likely be different if another language had been dominant when it was written (yes, this is an advantage of C, but we all agree on that point).

Rusky wrote:I also don't have an existing language to use so the syntax will probably be pretty rough and not everything will be implemented the best way possible, but I'll give it a shot:

• some keywords were renamed (e.g. "match" instead of "switch")
• semicolons were replaced with end of line, and a few other trivial changes in syntax
• the order things appear in declerations/definitions was changed (e.g. "checksum: (contents: byte[len]*, checksum: byte): (bool)" instead of "bool checksum(byte[len] *contents, byte checksum)"
• you stole "cout" from C++ (and renamed it to "print")
• there's support for returning multiple values from functions
• the compiler is able to make (potentially wrong) assumptions about the sizes of arrays (e.g. "checksum(byte[]*(rsdt))")
• the compiler is able to handle arrays of mixed types (e.g. "for (controller in madt->controllers)")

Brendan wrote:It's just parsing data.

Brendan wrote:This code is like C, except that:

• some keywords were renamed (e.g. "match" instead of "switch")
• semicolons were replaced with end of line, and a few other trivial changes in syntax
• the order things appear in declerations/definitions was changed (e.g. "checksum: (contents: byte[len]*, checksum: byte): (bool)" instead of "bool checksum(byte[len] *contents, byte checksum)"
• you stole "cout" from C++ (and renamed it to "print")
• there's support for returning multiple values from functions

Brendan wrote:

• the compiler is able to handle arrays of mixed types (e.g. "for (controller in madt->controllers)")

...
I also don't think that the ability to handle arrays/lists of mixed types is realistic; especially for "foreign" structures where the compiler can't insert hidden fields to make it easier (e.g. turn it into a linked list of "union { struct; struct; struct;}"). It's the sort of feature that sounds easy to do until you attempt to implement a compiler that does it. Perhaps this is why you couldn't find an existing language?

acpi_madt: struct = {
   ...
   controllers: byte[header.length / 4 - (sizeof header + sizeof lapic + sizeof flags) / 4]
}

for (
   controller: acpi_madt_header* = acpi_madt_header*(madt->controllers&);
   controller <= madt->controllers[-1]&; // since array bounds are checked, use negative indices to index from the end- could be other options
   controller = acpi_madt_header*(byte*(controller) + controller->header.length) // yet another place where a modified abi would be nice
) {
   ...
}

Brendan wrote:

• the compiler is able to make (potentially wrong) assumptions about the sizes of arrays (e.g. "checksum(byte[]*(rsdt))")

Brendan wrote:For the code itself, the amount of validation done is lacking. For example, what happens if the MADT is 200 bytes but has a 16-byte structure that starts at offset 198? What happens if the length/size of the RSDT is odd (and there's only space for part of a pointer at the end of the table of pointers)? Does the compiler automatically generate code to check these things; and if it does, how does it report errors? Should the entire thing by wrapped in "try/catch" exception handling?

Rusky wrote:

Brendan wrote:This code is like C, except that:

• some keywords were renamed (e.g. "match" instead of "switch")
• semicolons were replaced with end of line, and a few other trivial changes in syntax
• the order things appear in declerations/definitions was changed (e.g. "checksum: (contents: byte[len]*, checksum: byte): (bool)" instead of "bool checksum(byte[len] *contents, byte checksum)"
• you stole "cout" from C++ (and renamed it to "print")
• there's support for returning multiple values from functions

This was mostly to emphasize the difference from C. By changing the little things it makes it obvious it's not the same, at a glance. What did you expect?

Rusky wrote:However, note that match is a little bit more flexible in that it doesn't switch strictly on value but also on things like the presence of a value in an optional type. It's pattern matching, borrowed from functional programming btw.

Rusky wrote:

Brendan wrote:

• the compiler is able to handle arrays of mixed types (e.g. "for (controller in madt->controllers)")

...
I also don't think that the ability to handle arrays/lists of mixed types is realistic; especially for "foreign" structures where the compiler can't insert hidden fields to make it easier (e.g. turn it into a linked list of "union { struct; struct; struct;}"). It's the sort of feature that sounds easy to do until you attempt to implement a compiler that does it. Perhaps this is why you couldn't find an existing language?

My example does not use heterogeneous arrays, only pointers to "base classes." Did I misunderstand the ACPI spec? If so, and the controllers are in-line, try this:

Code: Select all

acpi_madt: struct = {
   ...
   controllers: byte[header.length / 4 - (sizeof header + sizeof lapic + sizeof flags) / 4]
}

Code: Select all

for (
   controller: acpi_madt_header* = acpi_madt_header*(madt->controllers&);
   controller <= madt->controllers[-1]&; // since array bounds are checked, use negative indices to index from the end- could be other options
   controller = acpi_madt_header*(byte*(controller) + controller->header.length) // yet another place where a modified abi would be nice
) {
   ...
}

Rusky wrote:

Brendan wrote:

• the compiler is able to make (potentially wrong) assumptions about the sizes of arrays (e.g. "checksum(byte[]*(rsdt))")

How is that potentially wrong? Given a correct RSDT, which is the firmware and/or bootloader's responsibility, the program knows the size of the table by reading rsdt->header.length (since the size of the rsdt is based on it). It's just more implicit than you may be used to.

Rusky wrote:As for how the compiler responds to problems, my preference would be a compile-time error. For example, if inside that new for loop above, controller is cast to something (acpi_madt_header* even) that could permit access outside the bounds of controllers, the programmer has to add a check themselves before dereferencing it. Because that check is necessary anyway if you're willing to expect incorrectly-sized tables, this is just the compiler and language semantics reminding you of potential problems before they come up in hard-to-find bugs at runtime.