SQLite isolation levels Updated +Created
The default isolation level for SQLite is SERIALIZABLE
It does not appear possible to achieve the other two levels besides SERIALIZABLE and READ UNCOMMITED
x86 Paging Tutorial / Hardware implementation Updated +Created
Paging is implemented by the CPU hardware itself.
Paging could be implemented in software, but that would be too slow, because every single RAM memory access uses it!
Operating systems must setup and control paging by communicating to the CPU hardware. This is done mostly via:
Processes can however make requests to the OS that cause the page tables to be modified, notably:
The kernel then decides if the request will be granted or not in a controlled manner.
Node.js SQLite bindings Updated +Created
x86 Paging Tutorial / How the K-ary tree is used in x86 Updated +Created
x86's multi-level paging scheme uses a 2 level K-ary tree with 2^10 bits on each level.
Addresses are now split as:
| directory (10 bits) | table (10 bits) | offset (12 bits) |
Then:
  • the top 10 bits are used to walk the top level of the K-ary tree (level0)
    The top table is called a "directory of page tables".
    cr3 now points to the location on RAM of the page directory of the current process instead of page tables.
    Page directory entries are very similar to page table entries except that they point to the physical addresses of page tables instead of physical addresses of pages.
    Each directory entry also takes up 4 bytes, just like page entries, so that makes 4 KiB per process minimum.
    Page directory entries also contain a valid flag: if invalid, the OS does not allocate a page table for that entry, and saves memory.
    Each process has one and only one page directory associated to it (and pointed to by cr3), so it will contain at least 2^10 = 1K page directory entries, much better than the minimum 1M entries required on a single-level scheme.
  • the next 10 bits are used to walk the second level of the K-ary tree (level1)
    Second level entries are also called page tables like the single level scheme.
    Page tables are only allocated only as needed by the OS.
    Each page table has only 2^10 = 1K page table entries instead of 2^20 for the single paging scheme.
    Each process can now have up to 2^10 page tables instead of 2^20 for the single paging scheme.
  • the offset is again not used for translation, it only gives the offset within a page
One reason for using 10 bits on the first two levels (and not, say, 12 | 8 | 12 ) is that each Page Table entry is 4 bytes long. Then the 2^10 entries of Page directories and Page Tables will fit nicely into 4Kb pages. This means that it faster and simpler to allocate and deallocate pages for that purpose.
Deletionism on Wikipedia Updated +Created
Some examples by Ciro Santilli follow.
Of the tutorial-subjectivity type:
Notability constraints, which are are way too strict:
There are even a Wikis that were created to remove notability constraints: Wiki without notability requirements.
For these reasons reason why Ciro basically only contributes images to Wikipedia: because they are either all in or all out, and you can determine which one of them it is. And this allows images to be more attributable, so people can actually see that it was Ciro that created a given amazing image, thus overcoming Wikipedia's lack of reputation system a little bit as well.
Wikipedia is perfect for things like biographies, geography, or history, which have a much more defined and subjective expository order. But when it comes to "tutorials of how to actually do stuff", which is what mathematics and physics are basically about, Wikipedia has a very hard time to go beyond dry definitions which are only useful for people who already half know the stuff. But to learn from zero, newbies need tutorials with intuition and examples.
Bibliography:
Group axiom Updated +Created
Lattice Microbes Updated +Created
GPU accelerated, simulates the Craig's minimized M. genitalium, JCVI-syn3A at a particle basis of some kind.
Lab head is the cutest-looking lady ever: chemistry.illinois.edu/zan, Zaida (Zan) Luthey-Schulten.
List of systems programmers Updated +Created
Spy Updated +Created
x86 Paging Tutorial / Invalidating TLB entries Updated +Created
When the process changes, cr3 change to point to the page table of the new current process.
This creates a problem: the TLB is now filled with a bunch of cached entries for the old process.
A simple and naive solution would be to completely invalidate the TLB whenever the cr3 changes.
However, this is would not be very efficient, because it often happens that we switch back to process 1 before process 2 has completely used up the entire TLB cache entries.
Basically, the OS assigns a different ASID for each process, and then TLB entries are automatically also tagged with that ASID. This way when the process makes an access, the TLB can determine if a hit is actually for the current process, or if it is an old address coincidence with another process.
The x86 also offers the invlpg instruction which explicitly invalidates a single TLB entry. Other architectures offer even more instructions to invalidated TLB entries, such as invalidating all entries on a given range.
x86 Paging Tutorial / K-ary trees to the rescue Updated +Created
The algorithmically minded will have noticed that paging requires associative array (like Java Map of Python dict()) abstract data structure where:
  • the keys are linear pages addresses, thus of integer type
  • the values are physical page addresses, also of integer type
The single level paging scheme uses a simple array implementation of the associative array:
  • the keys are the array index
  • this implementation is very fast in time
  • but it is too inefficient in memory
and in C pseudo-code it looks like this:
linear_address[0]      = physical_address_0
linear_address[1]      = physical_address_1
linear_address[2]      = physical_address_2
...
linear_address[2^20-1] = physical_address_N
But there another simple associative array implementation that overcomes the memory problem: an (unbalanced) k-ary tree.
A K-ary tree, is just like a binary tree, but with K children instead of 2.
Using a K-ary tree instead of an array implementation has the following trade-offs:
  • it uses way less memory
  • it is slower since we have to de-reference extra pointers
In C-pseudo code, a 2-level K-ary tree with K = 2^10 looks like this:
level0[0] = &level1_0[0]
    level1_0[0]      = physical_address_0_0
    level1_0[1]      = physical_address_0_1
    ...
    level1_0[2^10-1] = physical_address_0_N
level0[1] = &level1_1[0]
    level1_1[0]      = physical_address_1_0
    level1_1[1]      = physical_address_1_1
    ...
    level1_1[2^10-1] = physical_address_1_N
...
level0[N] = &level1_N[0]
    level1_N[0]      = physical_address_N_0
    level1_N[1]      = physical_address_N_1
    ...
    level1_N[2^10-1] = physical_address_N_N
and we have the following arrays:
  • one directory, which has 2^10 elements. Each element contains a pointer to a page table array.
  • up to 2^10 pagetable arrays. Each one has 2^10 4 byte page entries.
and it still contains 2^10 * 2^10 = 2^20 possible keys.
K-ary trees can save up a lot of space, because if we only have one key, then we only need the following arrays:
  • one directory with 2^10 entries
  • one pagetable at directory[0] with 2^10 entries
  • all other directory[i] are marked as invalid, don't point to anything, and we don't allocate pagetable for them at all
x86 Paging Tutorial / Kernel vs process memory layout Updated +Created
The Linux Kernel reserves two zones of virtual memory:
  • one for kernel memory
  • one for programs
The exact split is configured by CONFIG_VMSPLIT_.... By default:
  • on 32-bit:
    • the bottom 3/4 is program space: 00000000 to BFFFFFFF
    • the top 1/4 is kernel memory: C0000000 to FFFFFFFF, like this:
      ------------------ FFFFFFFF
      Kernel
      ------------------ C0000000
      ------------------ BFFFFFFF
      
      
      Process
      
      
      ------------------ 00000000
  • on 64-bit: currently only 48-bits are actually used, split into two equally sized disjoint spaces. The Linux kernel just assigns:
    • the bottom part to processes 00000000 00000000 to 008FFFFF FFFFFFFF
    • the top part to the kernel: FFFF8000 00000000 to FFFFFFFF FFFFFFFF, like this:
      ------------------ FFFFFFFF
      Kernel
      ------------------ C0000000
      
      
      (not addressable)
      
      
      ------------------ BFFFFFFF
      Process
      ------------------ 00000000
Kernel memory is also paged.
x86 Paging Tutorial / Memory management unit Updated +Created
Paging is done by the Memory Management Unit (MMU) part of the CPU.
Like many others (e.g. x87 co-processor, APIC), this used to be by separate chip on early days.
It was later integrated into the CPU, but the term MMU still used.
NLab Updated +Created
Decent encyclopedia of mathematics. Not much motivation, mostly statements though.
Unlike Wikipedia, they have a more sane forum commenting system, e.g. a page/forum pair:
Transmon Updated +Created
Used e.g. in the Sycamore processor.
The most basic type of transmon is in Ciro's ASCII art circuit diagram notation, an LC circuit e.g. as mentioned at youtu.be/cb_f9KpYipk?t=180 from Video "The transmon qubit by Leo Di Carlo (2018)":
+----------+
| Island 1 |
+----------+
   |   |
   X   C
   |   |
+----------+
| Island 2 |
+----------+
youtu.be/eZJjQGu85Ps?t=2443 from Video "Superconducting Qubits I Part 1 by Zlatko Minev (2020)" describes a (possibly simplified) physical model of it, as two superconducting metal islands linked up by a Josephson junction marked as X in the diagram as per-Ciro's ASCII art circuit diagram notation:
+-------+       +-------+
|       |       |       |
| Q_1() |---X---| Q_2() |
|       |       |       |
+-------+       +-------+
The circuit is then analogous to a LC circuit, with the islands being the capacitor. The Josephson junction functions as a non-linear inductor.
Others define it with a SQUID device instead: youtu.be/cb_f9KpYipk?t=328 from Video "The transmon qubit by Leo Di Carlo (2018)". He mentions that this allows tuning the inductive element without creating a new device.
Video 1.
The superconducting transmon qubit as a microwave resonator by Daniel Sank (2021)
Source.
Video 2.
Calibration of Transmon Superconducting Qubits by Stefan Titus (2021)
Source. Possibly this Keysight which would make sense.
Trillium Notes Updated +Created
Originally at github.com/zadam/trilium, then after development stopped the community took it up at: github.com/TriliumNext/Notes.
Tree based organization at last. Infinitely deep.
Amazing WYSIWYG, including maths and tables, plus insane plugins like canvas mode, and specific file formats like code/mermaid diagrams/drawing mode.
Intentionally or not, they've basically made an open source Notion, with the possible exception that Notion historically started on web and moved to the desktop, while Trillium went the other way round.
Version history with automatic snapshots at intervals. TODO how is it implemented? Do they just ZIP multiple versions?
No multiuser features. Except for that, could have been a good starting point of an online multiuser thing such as OurBigBook.com!
With Book Notes it is possible possible to see more than one page at a time on the output, which his a major feature of OurBigBook. But does it show on HTML export as well?
You can static HTML export any subtree by right clicking on it in the navigation tree.
Is there a CLI to export to HTML? github.com/zadam/trilium/issues/3012
HTML export keeps all data as HTML is their native format. This may be inherited from CKEditor. The files are mostly visible, but there is some CSS missing, it is not 100% like editor, notably math is broken. There is also a hosted way of exposing: github.com/zadam/trilium/wiki/Sharing.
trilium.rocks however has a very good export, it is just a question of how much they had to hacked things, source at: github.com/zerebos/trilium.rocks
The default tHTML export uses frame navigation, with a toc fixed on the left frame. Efficient, but not of this century.
There is no concept of user created unique text IDs: you can have the same headers in the same folders in the UI. It's not even a matter of scopes. On exports they are differentiated as 1_name, 2_name, etc.
./Trilium Demo/Books/To read/1_HR.md
./Trilium Demo/Books/To read/2_HR.md
./Trilium Demo/Books/To read/HR.md
Markdown export warns:
this preserves most of the formatting
Architecture: runs on local SQLite database via better-sqlite3. Data apparently stored in SQLite database at ~/.local/share/trilium-data, no raw files.
Markup is stored as HTML as seen from: sqlite3 document.db 'SELECT * from note_contents'. HTML is their native storage format, quite interesting. But this means it is not source centric, so any source editing would have to go via import/export. It can be done apparently: github.com/zadam/trilium/wiki/Markdown but involves shoving a ZIP around.
WYSIWYG based on ckeditor.com/ which is a dependency. It is kind of cool that the view in which you view the output is exactly the same as the one you edit in, and there is no intermediate format, just the HTML.
Math is KaTeX based.
It also runs on the browser via a server: github.com/zadam/trilium/wiki/Server-installation. And they have a paid service for it at: trilium.cc/. Quite impressive.
They have server to from desktop sync: github.com/zadam/trilium/wiki/synchronization. There is no conflict resolution, one of them wins randomly. But they have revision history, and anything lost will be in the revision history. They have so many features it is mind blowing.
Maintainer announced he would be slowing down development since January 2024: github.com/zadam/trilium/issues/4620?ref=selfh.st
x86 Paging Tutorial / Multi-level paging scheme numerical translation example Updated +Created
Page directory given to process by the OS:
entry index   entry address      page table address  present
-----------   ----------------   ------------------  --------
0             CR3 + 0      * 4   0x10000             1
1             CR3 + 1      * 4                       0
2             CR3 + 2      * 4   0x80000             1
3             CR3 + 3      * 4                       0
...
2^10-1        CR3 + 2^10-1 * 4                       0
Page tables given to process by the OS at PT1 = 0x10000000 (0x10000 * 4K):
entry index   entry address      page address  present
-----------   ----------------   ------------  -------
0             PT1 + 0      * 4   0x00001       1
1             PT1 + 1      * 4                 0
2             PT1 + 2      * 4   0x0000D       1
...                                  ...
2^10-1        PT1 + 2^10-1 * 4   0x00005       1
Page tables given to process by the OS at PT2 = 0x80000000 (0x80000 * 4K):
entry index   entry address     page address  present
-----------   ---------------   ------------  ------------
0             PT2 + 0     * 4   0x0000A       1
1             PT2 + 1     * 4   0x0000C       1
2             PT2 + 2     * 4                 0
...
2^10-1        PT2 + 0x3FF * 4   0x00003       1
where PT1 and PT2: initial position of page table 1 and page table 2 for process 1 on RAM.
With that setup, the following translations would happen:
linear    10 10 12 split  physical
--------  --------------  ----------
00000001  000 000 001     00001001
00001001  000 001 001     page fault
003FF001  000 3FF 001     00005001
00400000  001 000 000     page fault
00800001  002 000 001     0000A001
00801004  002 001 004     0000C004
00802004  002 002 004     page fault
00B00001  003 000 000     page fault
Let's translate the linear address 0x00801004 step by step:
  • In binary the linear address is:
    0    0    8    0    1    0    0    4
    0000 0000 1000 0000 0001 0000 0000 0100
  • Grouping as 10 | 10 | 12 gives:
    0000000010 0000000001 000000000100
    0x2        0x1        0x4
    which gives:
    page directory entry = 0x2
    page table     entry = 0x1
    offset               = 0x4
    So the hardware looks for entry 2 of the page directory.
  • The page directory table says that the page table is located at 0x80000 * 4K = 0x80000000. This is the first RAM access of the process.
    Since the page table entry is 0x1, the hardware looks at entry 1 of the page table at 0x80000000, which tells it that the physical page is located at address 0x0000C * 4K = 0x0000C000. This is the second RAM access of the process.
  • Finally, the paging hardware adds the offset, and the final address is 0x0000C004.
Page faults occur if either a page directory entry or a page table entry is not present.
The Intel manual gives a picture of this translation process in the image "Linear-Address Translation to a 4-KByte Page using 32-Bit Paging": Figure 1. "x86 page translation process"
Figure 1.
x86 page translation process
.
x86 Paging Tutorial / PAE and PSE page table schemes Updated +Created
If either PAE and PSE are active, different paging level schemes are used:
  • no PAE and no PSE: 10 | 10 | 12
  • no PAE and PSE: 10 | 22.
    22 is the offset within the 4Mb page, since 22 bits address 4Mb.
  • PAE and no PSE: 2 | 9 | 9 | 12
    The design reason why 9 is used twice instead of 10 is that now entries cannot fit anymore into 32 bits, which were all filled up by 20 address bits and 12 meaningful or reserved flag bits.
    The reason is that 20 bits are not enough anymore to represent the address of page tables: 24 bits are now needed because of the 4 extra wires added to the processor.
    Therefore, the designers decided to increase entry size to 64 bits, and to make them fit into a single page table it is necessary reduce the number of entries to 2^9 instead of 2^10.
    The starting 2 is a new Page level called Page Directory Pointer Table (PDPT), since it points to page directories and fill in the 32 bit linear address. PDPTs are also 64 bits wide.
    cr3 now points to PDPTs which must be on the fist four 4GB of memory and aligned on 32 bit multiples for addressing efficiency. This means that now cr3 has 27 significative bits instead of 20: 2^5 for the 32 multiples * 2^27 to complete the 2^32 of the first 4GB.
  • PAE and PSE: 2 | 9 | 21
    Designers decided to keep a 9 bit wide field to make it fit into a single page.
    This leaves 23 bits. Leaving 2 for the PDPT to keep things uniform with the PAE case without PSE leaves 21 for offset, meaning that pages are 2M wide instead of 4M.
Node.js Updated +Created
WellSync, if you are gonna useSync this wonky language thing inSync one place, you might as well useSync it everywhereSync and make it more decent. See also: how to convert async to sync in JavaScript.

Unlisted articles are being shown, click here to show only listed articles.