Multiple addresses translate to a single physical address by 
Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01
Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01The same linear address can translate to different physical addresses for different processes, depending only on the value inside
cr3.Both linear addresses
00002 000 from process 1 and 00004 000 from process 2 point to the same physical address 00003 000. This is completely allowed by the hardware, and it is up to the operating system to handle such cases.This often in normal operation because of Copy-on-write (COW), which be explained elsewhere.
Such mappings are sometime called "aliases".
What if Process 1 tries to access
0x00003000, which is not present?The hardware notifies the software via a Page Fault Exception.
When an exception happens, the CPU jumps to an address that the OS had previously registered as the fault handler. This is usually done at boot time by the OS.
This could happen for example due to a programming error:but there are cases where it is not a bug, for example in Linux when:
int *is = malloc(1);
is[2] = 1;- the program wants to increase its stack.It just tries to accesses a certain byte in a given possible range, and if the OS is happy it adds that page to the process address space, otherwise, it sends a signal to the process.
- the page was swapped to disk.The OS will need to do some work behind the processes back to get the page back into RAM.The OS can discover that this is the case based on the contents of the rest of the page table entry, since if the present flag is clear, the other entries of the page table entry are completely left for the OS to to what it wants.On Linux for example, when present = 0:
- if all the fields of the page table entry are 0, invalid address.
- else, the page has been swapped to disk, and the actual values of those fields encode the position of the page on the disk.
In any case, the OS needs to know which address generated the Page Fault to be able to deal with the problem. This is why the nice IA32 developers set the value of
cr2 to that address whenever a Page Fault occurs. The exception handler can then just look into cr2 to get the address.A vector field with a bilinear map into itself, which we can also call a "vector product".
Note that the vector product does not have to be neither associative nor commutative.
Examples: en.wikipedia.org/w/index.php?title=Algebra_over_a_field&oldid=1035146107#Motivating_examples
- complex numbers, i.e. with complex number multiplication
- with the cross product
- quaternions, i.e. with the quaternion multiplication
Why are pages 4KiB anyways?
There is a trade-off between memory wasted in:
- page tables
- extra padding memory within pages
This can be seen with the extreme cases:
- if the page size were 1 byte:
- granularity would be great, and the OS would never have to allocate unneeded padding memory
- but the page table would have 2^32 entries, and take up the entire memory!
- if the page size were 4GiB:
- we would need to swap 4GiB to disk every time a new process becomes active
- the page size would be a single entry, so it would take almost no memory at all
x86 designers have found that 4KiB pages are a good middle ground.
The Quantum Story by Jim Baggott (2011) page 2 mentions how newton's support for the corpuscular theory of light led it to be held for a very long time, even when evidence of the wave theory of light was becoming overwhelming.
Their website, and in particular the recruitment section, are so creepy.
There's not mention of bombs. No photos of atomic explosions. The words "atomic" and "weapon" do not even show up in the front page!!! The acronym AWE is instead used everywhere as an euphemism.
In the recruitment section we can see a bunch of people smiling: web.archive.org/web/20211007213222/https://www.awe.co.uk/careers/working-at-awe/, suggesting:There's even children outreach!!!
We make nukes, and we do it with a smile!
Ciro Santilli is not against storing a few nukes to be ready against dictatorships. But don't be such a pussy! Just say what the fuck you are doing more clearly! You are making weapons to kill people and destroy things in order to maintain the Balance of power. If the public can't handle such facts, then shut down the fucking program.
History of the electromagnetic theory of light by Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01
Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01 The problem with single-level paging by Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01
Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01The problem with a single-level paging scheme is that it would take up too much RAM: 4G / 4K = 1M entries _per_ process.
If each entry is 4 bytes long, that would make 4M _per process_, which is too much even for a desktop computer:
ps -A | wc -l says that I am running 244 processes right now, so that would take around 1GB of my RAM!For this reason, x86 developers decided to use a multi-level scheme that reduces RAM usage.
The downside of this system is that is has a slightly higher access time, as we need to access RAM more times for each translation.
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:and in C pseudo-code it looks like this:
- the keys are the array index
- this implementation is very fast in time
- but it is too inefficient in memory
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_NBut 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 and we have the following arrays:and it still contains
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- one
directory, which has2^10elements. Each element contains a pointer to a page table array. - up to 2^10
pagetablearrays. Each one has2^104 byte page entries.
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
directorywith 2^10 entries - one
pagetableatdirectory[0]with 2^10 entries - all other
directory[i]are marked as invalid, don't point to anything, and we don't allocatepagetablefor them at all
Pinned article: ourbigbook/introduction-to-the-ourbigbook-project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivative - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.
Figure 3. Visual Studio Code extension installation.
Figure 4. Visual Studio Code extension tree navigation.
Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.Video 4. OurBigBook Visual Studio Code extension editing and navigation demo. Source. - Internal cross file references done right:
- Infinitely deep tables of contents:
Figure 6. Dynamic article tree with infinitely deep table of contents.Live URL: ourbigbook.com/cirosantilli/chordateDescendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact