x86 Paging Tutorial / K-ary trees to the rescue Updated 2025-07-16
View more
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
Read the full article
x86 Paging Tutorial / Why not a balanced tree Updated 2025-07-16
View more
Learned readers will ask themselves: so why use an unbalanced tree instead of balanced one, which offers better asymptotic times en.wikipedia.org/wiki/Self-balancing_binary_search_tree?
Likely:
  • the maximum number of entries is small enough due to memory size limitations, that we won't waste too much memory with the root directory entry
  • different entries would have different levels, and thus different access times
  • tree rotations would likely make caching more complicated
Read the full article
x86 Paging Tutorial / How the K-ary tree is used in x86 Updated 2025-07-16
View more
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.
Read the full article
x86 Paging Tutorial / Multi-level paging scheme numerical translation example Updated 2026-10-19
View more
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
.
Read the full article
Corpuscular theory of light Updated 2025-07-16
View more
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.
Read the full article
Wave theory of light Updated 2025-07-16
Read the full article
Electromagnetic radiation Updated 2025-07-16
Read the full article
Nuxt.js Updated 2025-07-16
Read the full article
Why do the up ad down quarks have different masses? Updated 2025-07-16
View more
Read the full article
Kavli Institute for Theoretical Physics Updated 2025-07-16
Read the full article
How to report Ubuntu crashes Updated 2025-07-16
View more
Their crash system does not have an amazing user interface.
Tested on Ubuntu 21.10.
After something crashes, look under /var/crash for a crash file, which helps to determine which package to report under on Launchpad.
E.g. a file /var/crash/_usr_sbin_gdm3.0.crash makes you want to file the bug under gdm at: bugs.launchpad.net/ubuntu/+source/gdm/+filebug
Then, while reporting the bug, you want to give the developpers access to that .crash file. But you can't publicly upload it because it contains memory dumps and could contain secret information. The way to do it is to look at the ID under:
sudo cat /var/crash/_usr_sbin_gdm3.0.uploaded
Ubuntu's crash report system has already uploaded the .crash for you, so you just have to confirm it and give the ID on the ticket.
You can view a list of all your uploaded errors at:
xdg-open https://errors.ubuntu.com/user/$(sudo cat /var/lib/whoopsie/whoopsie-id)
and each of those contain a link to:
https://errors.ubuntu.com/oops/<.uloaded error id>
which you yourself cannot see.
Running:
sudo apport-unpack /var/crash/_usr_sbin_gdm3.0.crash /tmp/app
splits it up into a few files, but does not make any major improvements.
apport-retrace
sudo apt install apport-retrace
sudo chmod 666 /var/crash/_usr_sbin_gdm3.0.crash
apport-retrace -g /var/crash/_usr_sbin_gdm3.0.crash
opens GDB with the core dump. Debug symbols are supplied as separate packages, which is a really cool idea: so you should be able to download them after the crash to see symbols. askubuntu.com/questions/487222/how-to-install-debug-symbols-for-installed-packages mentions how to install them. Official docs at: wiki.ubuntu.com/DebuggingProgramCrash#Debug_Symbol_Packages
Tried:
echo "deb http://ddebs.ubuntu.com $(lsb_release -cs) main restricted universe multiverse" | sudo tee -a /etc/apt/sources.list.d/ddebs.list
echo -e "deb http://ddebs.ubuntu.com $(lsb_release -cs)-updates main restricted universe multiverse\ndeb http://ddebs.ubuntu.com $(lsb_release -cs)-proposed main restricted universe multiverse" | sudo tee -a /etc/apt/sources.list.d/ddebs.list
sudo apt install ubuntu-dbgsym-keyring
but then sudo apt update fails with:
E: The repository 'http://ddebs.ubuntu.com impish-security Release' does not have a Release file.
Read the full article
Ubuntu release Updated 2025-07-16
Read the full article
Launchpad (website) Updated 2025-07-16
Read the full article
Tangible asset Updated 2025-07-16
Read the full article
Intangible asset Updated 2025-07-16
Read the full article
DDR SDRAM Updated 2025-07-16
Read the full article
Pros and cons of superconducting qubits Updated 2025-07-16
Read the full article
Superconducting qubit type Updated 2025-07-16
Read the full article
Stars nearest to the Sun Updated 2025-07-16
View more
Figure 1. Source.
Figure 2.
Distance of stars nearest to the Sun as function of time
. Source.
Some notable ones:
Read the full article
JTAG Updated 2025-07-16
Read the full article

There are unlisted articles, also show them or only show them.