Inside Job (2010) by Ciro Santilli 35 Updated +Created
STT_FILE by Ciro Santilli 35 Updated +Created
Entry 1 has ELF64_R_TYPE == STT_FILE. ELF64_R_TYPE is continued inside of st_info.
  • 10 8: st_name = 01000000 = character 1 in the .strtab, which until the following \0 makes hello_world.asm
    This piece of information file may be used by the linker to decide on which segment sections go: e.g. in ld linker script we write:
    segment_name :
    {
        file(section)
    }
    to pick a section from a given file.
    Most of the time however, we will just dump all sections with a given name together with:
    segment_name :
    {
        *(section)
    }
  • 10 12: st_info = 04
    Bits 0-3 = ELF64_R_TYPE = Type = 4 = STT_FILE: the main purpose of this entry is to use st_name to indicate the name of the file which generated this object file.
    Bits 4-7 = ELF64_ST_BIND = Binding = 0 = STB_LOCAL. Required value for STT_FILE.
  • 10 13: st_shndx = Symbol Table Section header Index = f1ff = SHN_ABS. Required for STT_FILE.
  • 20 0: st_value = 8x 00: required for value for STT_FILE
  • 20 8: st_size = 8x 00: no allocated size
Now from the readelf, we interpret the others quickly.
SHT_NULL by Ciro Santilli 35 Updated +Created
Moon by Ciro Santilli 35 Updated +Created
Pluto by Ciro Santilli 35 Updated +Created
Nelson-Mandela.jpg by Ciro Santilli 35 Updated +Created
Figure 1.
Nelson-Mandela.jpg
. Source. Message:
"There is nothing like returning to a place that remains unchanged to find the ways in which you yourself have altered." - Nelson Mandela Nelson Rolihlahla Mandela was a South African anti-apartheid revolutionary, politician and philanthropist who served as President of South Africa from 1994 to 1999. - Wikipedia Born: July 18, 1918, Mvezo, South Africa Died: December 5, 2013.
Octet rule by Ciro Santilli 35 Updated +Created
p-orbital by Ciro Santilli 35 Updated +Created
Madelung energy ordering rule by Ciro Santilli 35 Updated +Created
Looking at the energy level of the Schrödinger equation solution for the hydrogen atom, you would guess that for multi-electron atoms that only the principal quantum number would matter, azimuthal quantum number getting filled randomly.
However, orbitals energies for large atoms don't increase in energy like those of hydrogen due to electron-electron interactions.
In particular, the following would not be naively expected:
ARM Cortex-M0+ by Ciro Santilli 35 Updated +Created
Classification of 2-transitive groups by Ciro Santilli 35 Updated +Created
Invalidating TLB entries by Ciro Santilli 35 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.
Single level paging scheme visualization by Ciro Santilli 35 Updated +Created
This is how the memory could look like in a single level paging scheme:
Links   Data                    Physical address

      +-----------------------+ 2^32 - 1
      |                       |
      .                       .
      |                       |
      +-----------------------+ page0 + 4k
      | data of page 0        |
+---->+-----------------------+ page0
|     |                       |
|     .                       .
|     |                       |
|     +-----------------------+ pageN + 4k
|     | data of page N        |
|  +->+-----------------------+ pageN
|  |  |                       |
|  |  .                       .
|  |  |                       |
|  |  +-----------------------+ CR3 + 2^20 * 4
|  +--| entry[2^20-1] = pageN |
|     +-----------------------+ CR3 + 2^20 - 1 * 4
|     |                       |
|     .    many entires       .
|     |                       |
|     +-----------------------+ CR3 + 2 * 4
|  +--| entry[1] = page1      |
|  |  +-----------------------+ CR3 + 1 * 4
+-----| entry[0] = page0      |
   |  +-----------------------+ <--- CR3
   |  |                       |
   |  .                       .
   |  |                       |
   |  +-----------------------+ page1 + 4k
   |  | data of page 1        |
   +->+-----------------------+ page1
      |                       |
      .                       .
      |                       |
      +-----------------------+  0
Notice that:
  • the CR3 register points to the first entry of the page table
  • the page table is just a large array with 2^20 page table entries
  • each entry is 4 bytes big, so the array takes up 4 MiB
  • each page table contains the physical address a page
  • each page is a 4 KiB aligned 4 KiB chunk of memory that user processes may use
  • we have 2^20 table entries. Since each page is 4 KiB == 2^12, this covers the whole 4 GiB (2^32) of 32-bit memory
Page table entries by Ciro Santilli 35 Updated +Created
The exact format of table entries is fixed by the hardware.
Each page entry can be seen as a struct with many fields.
The page table is then an array of struct.
On this simplified example, the page table entries contain only two fields:
bits   function
-----  -----------------------------------------
20     physical address of the start of the page
1      present flag
so in this example the hardware designers could have chosen the size of the page table to b 21 instead of 32 as we've used so far.
All real page table entries have other fields, notably fields to set pages to read-only for Copy-on-write. This will be explained elsewhere.
It would be impractical to align things at 21 bits since memory is addressable by bytes and not bits. Therefore, even in only 21 bits are needed in this case, hardware designers would probably choose 32 to make access faster, and just reserve bits the remaining bits for later usage. The actual value on x86 is 32 bits.
Here is a screenshot from the Intel manual image "Formats of CR3 and Paging-Structure Entries with 32-Bit Paging" showing the structure of a page table in all its glory: Figure 1. "x86 page entry format".
Figure 1.
x86 page entry format
.
The fields are explained in the manual just after.
How the K-ary tree is used in x86 by Ciro Santilli 35 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.
Nuxt.js by Ciro Santilli 35 Updated +Created
Launchpad (website) by Ciro Santilli 35 Updated +Created
Superconducting qubit type by Ciro Santilli 35 Updated +Created
Nested set model by Ciro Santilli 35 Updated +Created
This is particularly important in SQL: Nested set model in SQL, as it is an efficient way to transverse trees there, since querying parents every time would require multiple disk accesses.
As a tree:
As the sets:
 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|
Consider the following nested set:
0, 8, root
  1, 7, mathematics
    2, 3, geometry
      3, 6, calculus
        4, 5, derivative
        5, 6, integral
      6, 7, algebra
  7, 8, physics
When we want to insert one element, e.g. limit, normally under calculus, we have to specify:
  • parent
  • index within parent
so we have a method:
insert(parent, previousSibling)

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