diff options
| -rw-r--r-- | notes/arena_io_non_io.txt | 142 | ||||
| -rw-r--r-- | notes/backend.txt | 26 | ||||
| -rw-r--r-- | notes/easy_linear_types.txt | 62 | ||||
| -rw-r--r-- | notes/embedded_binary_interface_data.txt | 33 | ||||
| -rw-r--r-- | notes/stdlib_in_slul.txt | 129 |
5 files changed, 392 insertions, 0 deletions
diff --git a/notes/arena_io_non_io.txt b/notes/arena_io_non_io.txt new file mode 100644 index 0000000..6064b98 --- /dev/null +++ b/notes/arena_io_non_io.txt @@ -0,0 +1,142 @@ +arena pointers / io vs non-io +============================= + +Could require all "io-capable" objects to have a arena information at +the beginning of the page (i.e. the address with the low order bits +set to zero). + +This way, constant data can still work as usual without special alignment +or ordering requirements (e.g. having .rodata before .text in the same page, +which might not even be possible). + +It also allows large data to span across a page boundary, as long as any +"io-capable" objects are not allocated in a such page (since they need +the arena-chunk header). + +Contents of the arena-chunk +--------------------------- + +* Pointer to arena base. +* Size used in chunk (= offset to next free byte) + +If the arena-base is always allocated at a fixed offset (e.g. as the very +first allocation), then the pointer and the size can be merged into a single +pointer. + + +Contents of the arena base +-------------------------- + +This can be allocated inside the first arena-chunk. + +* Capabilities +* IO-function pointer overrides +* Chunked-list of pointers to the arena-chunks. + (constant-sized block, but can continue in increasing block sizes + as normal allocations) + +How / where to store information for garbage collection? +-------------------------------------------------------- + +Some form of GC would be useful. I don't think it has to be very +fine-grained, though. It also doesn't have to free everything, but it +would be good to have some kind of guarantee that it frees e.g. at least +say 80% of the completely unused "allocation units". + +However, "allocation unit" should probably be smaller than the arena-chunk, +which can be quite large, in particular if the page size is large (like +64 KiB or even 2 MiB). + +It has to be somewhat resistent against attacks. Putting random data that +happens to resemble pointers MUST NOT affect memory usage, for two reasons: +1) it could work as a Denial-of-Service attack, and 2) it could cause the +heap memory base address to be leaked. + +The really tricky parts: + +* Can it be done without lots of overhead for meta-data / RTTI? + - Maybe just a bitmap with 1 bit per pointer-sized word. + That's 128 bytes per 4K page on x86, and 64 bytes on x86_64. + - It could also be an area that grows down from the top + (e.g. run-length encoded). But the overhead might make it + less efficient than a bitmap. + - Just tracking the pointers is not enough to free parts of a + chunk, nor to do copy collection. + - That would require knowing the start (or size) of each + object. + - Could have 2 bits (is-start, contains-pointers) + - Or could store only sizes. + - Maybe it doesn't need object granularity? + - Could have an "end-bit" per e.g. pointer-sized word. + It would indicate if at least one object ends inside the word. + Granularity -> Size usage -> Percentage of 4K page on 32-bit: + 8 bytes 128+128 = 256 6.25% + 64 bytes 128+8 = 136 3.32% + - With a pointer-bitmap + a 1 byte size (16 byte granularity), + assuming 20 byte allocations on average: + 16 bytes 128+204 = 332 8.11% + assuming 60 byte allocations on average: + 16 bytes 128+68 = 196 4.79% +* With non-io chunks, the meta-data may cover a larger (combined) chunk, and + hence the meta-data part will be larger, too. +* Is limited granularity a problem when detecting live objects. + - Yes, it will be less accurate! Objects within the same "object-block" + that have a higher address will be incorrectly assumed to be in use. +* Can GC'ed objects safely be read by C code? +* Can GC'ed objects safely be modified by C code? +* Is any temporary space required to perform GC? + - Needs to mark used object-blocks. + - Needs to queue objects to scan? + +Weird ideas: + +* Keep an allocation journal (with object sizes and locations of pointers) + - Has to be very fast to append to. + - Has to be very compact. + - Even with only 1 byte used: + with avg alloc size of 20 bytes => 5.00% overhead + with avg alloc size of 60 bytes => 1.67% overhead +* Extremely coarse-grained GC: + - Just have a bitmap of pointers, don't bother about sizes. + Size: pagesize/ptralign/8 + Overhead: 1.56% (64b) - 3.13% (32b) + (pagesize/ptralign/8)/pagesize = 1/(ptralign*8) + Possibly no overhead with CHERI + (because it already tracks this info) + - Track pointers that might point to another arena-chunk + (or even another arena). + - Garbage collect only entire arena-chunks. +* Track only allocations in the "topmost" arena-chunk + (the one where new allocations go). + - Use a bitmaps for: + - words that contain a pointer + - allocation start status per word: + - 00 = inside allocation + - 01 = inside allocation, and is the last word of it + - 10 = start, hasn't escaped + - 11 = start, could have escaped + - 3 bits in total per word. + - On simple allocations w/o pointers, only a single bit has to be set + - Allocations with pointers will be word-aligned, so setting the + bitmap bits should be easy for them as well (on 64b platform it's + just a byte-aligned OR to the bitmap) + - Escaped blocks cannot be moved + - Therefore, trigger GC before escaping a block if let's say + >= 50% of the arena-chunk has been used and no GC has been + performed. + - Track free "holes", so escaped blocks can be moved there quickly + (by just copying them and updating the refs to them. + the refs update is just a linear scan). + - Set a "might need GC" flag when a pointer (that at least before pointed + to the arena-chunk) is somehow changed. + - Just adding new pointers cannot trigger GC + - Note that the pointers can come from stack or other chunks. + - Scan all words marked as containing a pointer + - Can use the next unallocated page as a temporary storage + - Will be all 0 at start + - Needs to be all 0 at end + - Is it possible to use dynamic programming can be used to scan + linearly a few times? + - If not, simply queue the roots and start scanning from those. + - Unmarked words are then free. + - Re-pack the movable words to use space more efficiently. diff --git a/notes/backend.txt b/notes/backend.txt new file mode 100644 index 0000000..c93c20e --- /dev/null +++ b/notes/backend.txt @@ -0,0 +1,26 @@ +* safe&portable IR vs low-level IR + - lots of common stuff across ISAs. + - calling conventions (e.g. struct passing) can be complex and + it would be good to be able to re-use things that are common. + - some optimizations might be easier to do on the low-level IR + (and vice versa). +* register alloc can be tricky: + - division on x86 is AFAIK limited to specific regs (eax,edx?) + - loop instructions on x86 + - apparently r0 is unavailable in some insns on sh4? + - on x86_64, some regs require prefix bytes + - types: + - byte/short/int that can use parts of a reg on x86 + - int/long distinction on aarch64 + - floating point regs + - multi-reg types, typically on 32 bit arches: + - 64 bit int on i386 + - 64 bit double on MIPS? + - "special-purpose general-purpose" regs + - as above, reg for division, looping, etc. + - CHERI and pointers +* floating point + - differences across architectures? + - calling conventions + - alignment, corner cases, etc. + - also, see reg alloc diff --git a/notes/easy_linear_types.txt b/notes/easy_linear_types.txt new file mode 100644 index 0000000..8c60122 --- /dev/null +++ b/notes/easy_linear_types.txt @@ -0,0 +1,62 @@ +Easy-to-use linear types +======================== + +Allow simple usage of linear types when using only local variables +and/or parameters and/or return values. + +Have a "lock system" with automatic garbage collection (collected no later +than when the arena is destroyed) for more complex cases. + + +Assume that `open` create a linear/owned `File` type. + +Trivial case: + + func stuff + code + own File f = open "file.txt" .write + write f "hello" # uses `f` but does not take ownership + close f # takes ownership of `f` + end + +Nested case: + + func get_file + returns + own File f + code + # Allow simple usage when returning + return open "file.txt" .write + end + +Complex case: + + func maybe_open_file + code + if use_file + # + begin_ownership thefile + thefile = open "file.txt" .write + suspend_ownership thefile + # disallow changing the `file` variable when it is + # suspended? + end + end + + func maybe_write_to_file + code + if use_file + resume_ownership file + write thefile "hello" + suspend_ownership file + end + end + + func maybe_close_file + code + if use_file + resume_ownership thefile + close thefile + end_ownership thefile + end + end diff --git a/notes/embedded_binary_interface_data.txt b/notes/embedded_binary_interface_data.txt new file mode 100644 index 0000000..ad99bbd --- /dev/null +++ b/notes/embedded_binary_interface_data.txt @@ -0,0 +1,33 @@ +Would it be a good idea or not to include the interface of libraries into +the binary (.so/.dll) files themselves? + +This would then have to include: +* the name and version of the library +* for each API-version: + - function parameters and returns (names and types) + - function constraints (if this is added) + - struct/types +* interface dependencies on other libraries and their versions +* runtime dependencies on other libraries and their versions + +Implementation details +---------------------- + +Regarding the ELF format, should be be a section or a segment? +Also, should it have SH_ALLOC or not? + +I think that the `strip` program removes everything that doesn't +have SH_ALLOC? + +Maybe it could use ELF .note.* / SHT_NOTE? + - .note.slul-module (name and version) + - .note.slul-api (API-versions) + - .note.slul-bdeps (interface/build dependencies) + - .note.slul-xdeps (runtime/execution dependencies) + +Problems +-------- + +Some distributions (e.g. Fedora) explicitly say that they want to keep the +distribution small for those who don't need development files. So maybe it's +a bad idea to make the library files larger for everyone? diff --git a/notes/stdlib_in_slul.txt b/notes/stdlib_in_slul.txt index 0479024..99c7953 100644 --- a/notes/stdlib_in_slul.txt +++ b/notes/stdlib_in_slul.txt @@ -32,6 +32,27 @@ Write those things in: e.g. Hare uses QBE, which has somewhat limited target support) * Formally-verified IR/assembler (see below) +Discourage people from writing in the unsafe language +----------------------------------------------------- + +It would be sad if the safe SLUL language loses out to an unsafe cousin +language. So IF an unsafe cousin language is ever created, it should +1) be very clear that it is NOT slul, and 2) discourage it's use by making +it an "unappealing" language. + +Make it explicitly a different language: +* Different name (uhoh? oops? noo? slunsafe?) +* Different file extension (.rtlc? .stdlib? .lul? .uhoh? .rtlu? .noo? .rsy? .slunsafe?) +* Different syntax + +Make it ugly but still readable: +* Use uppercase keywords? +* Or use some sigill? + +Make unsafe stuff really stand out: +* Maybe require an UNSAFE_xxx keyword around anything unsafe + + Hard-core solution: formally verified IR/assembler -------------------------------------------------- @@ -55,3 +76,111 @@ For registers, and for fields in structs in memory: * not null * length of field F * etc. + +Hard-code solution 2: write a C compiler in SLUL +------------------------------------------------ + +Could write a C compiler in SLUL, using the same backend as the SLUL +compiler will use. + +This could even be a subset of C89 (+ some things like uint64_t etc.). +Candidates for things to remove/forbid: +* digraphs/trigraphs +* float/double +* varargs (both usage, declarations and va_list etc.) +* multi-char chars +* octal literals and escape sequences +* assuming char is either signed or unsigned, i.e. assigning < 0 or >= 128 +* strange control structures: + - case not directly under switch + - statements between switch and first case + - not using {} when block comes on a separate line +* some types: + - void * + - wchat_t +* several casts: + - pointer to/from int + - function ptr to/from other data pointer types +* depending on operator precedence of: + - & vs && levels +* declarations: + - * vs [] precedence + - prototypes: `f()` + - auto/register storage classes + - common initialization: `static int i;` or `int i;` at top-level. + - volatile + - new struct/enum inside function parameter list +* unwanted macros: + - __DATE__, __TIME__ + - #pragma +* stdlib except for: + - memset, memcmp, memcpy, strlen + + +Syntax test +----------- + +Using UNSAFE_ everywhere to make unsafe stuff stand out and to make the +language more ugly. + +Using __ in identifiers to avoid collisions and also for increased ugliness. + +Using % before all keywords for even more ugliness. + + + %func __init_arena + %code + [UNSAFEPointer base_ptr, UNSAFESize pgsize] = __sys_mmap 1 + ArenaBase base_info %UNSAFE_OVERLAY base_ptr + .chunk = [ + # ability to merge base pointers and offsets? + #.info = %UNSAFE_ADDROF .base %UNSAFE_PTRADD %UNSAFE_OFFSETOF .freespace + .baseptr = %UNSAFE_ADDROF .base + .alloced = %UNSAFE_OFFSETOF .freespace + .size = pgsize + ] + .base = [ + # capability info, list of chunks, ... + ] + .freespace = [] + %end + %end + + %UNSAFE_GLOBAL __pagesize + + %func __sys_mmap + int npages + %code + %%SYS_if os linux + __syscall6 NR_mmap2 ... + %%SYS_elif os windows + __sys_VirtualAlloc ... + %%SYS_endif + %end + + %%SYS_switch os + %%SYS_case linux + %func __syscall6 + int syscall_number + unsigned long arg1 + ... + unsigned long arg6 + %code + %SYS_switch cpu + %SYS_case aarch64 + %UNSAFE_asmdef $sysc($n) $w32_le(...) + ... + %SYS_case i386 + %UNSAFE_asmdef $int($n) CD $n + # Should probably use the vdso instead... + %UNSAFE_machinecode $int(80) + %SYS_case x86_64 + ... + %SYS_endswitch + %end + %%SYS_case windows + %func __sys_VirtualAlloc + ... + %dllimport "kernel32.dll" "VirtualAlloc" + %end + %%SYS_endswitch |