There is a file that describes the structure of the virtual address space of the process, this file looks like this:

08048000-08053000 r-xp 00000000 08:03 18877 /usr/bin/cat 08053000-08054000 r--p 0000a000 08:03 18877 /usr/bin/cat 08054000-08055000 rw-p 0000b000 08:03 18877 /usr/bin/cat 091e3000-09204000 rw-p 00000000 00:00 0 [heap] 4f2d0000-4f2ef000 r-xp 00000000 08:03 1857 /usr/lib/ld-2.15.so 4f2ef000-4f2f0000 r--p 0001e000 08:03 1857 /usr/lib/ld-2.15.so 4f2f0000-4f2f1000 rw-p 0001f000 08:03 1857 /usr/lib/ld-2.15.so 4f2f7000-4f4a2000 r-xp 00000000 08:03 1858 /usr/lib/libc-2.15.so 4f4a2000-4f4a3000 ---p 001ab000 08:03 1858 /usr/lib/libc-2.15.so 4f4a3000-4f4a5000 r--p 001ab000 08:03 1858 /usr/lib/libc-2.15.so 4f4a5000-4f4a6000 rw-p 001ad000 08:03 1858 /usr/lib/libc-2.15.so 4f4a6000-4f4a9000 rw-p 00000000 00:00 0 b75c0000-b77c0000 r--p 00000000 08:03 57661 /usr/lib/locale/locale-archive b77c0000-b77c1000 rw-p 00000000 00:00 0 b77d9000-b77da000 rw-p 00000000 00:00 0 b77da000-b77db000 r-xp 00000000 00:00 0 [vdso] bf819000-bf83a000 rw-p 00000000 00:00 0 [stack]

The first and second columns are the beginning and end of the virtual memory area, respectively. The second is right, the third is the offset in the file if mmap used, the fourth is the device number if read by mmap'ом . The fifth is the file number if read by mmap'ом and the sixth is the path to the file.

The x86 processor family has two-level virtual memory. The size of one page - 4 kb. One root page table (page directory) contains 1024 records each 4 bytes in size, each record can refer to the second level record - the page directory (page table). Each directory contains 1024 entries each 4 bytes in size.

Here, in fact, the task is to calculate the total size of the tables necessary for the operation of virtual memory for a specific file. I do this: the total size of the mapped memory for the file from the example is 4345856 (I haven't completely laid it out), then we find the number of pages, there are 4345856/4096 = 1061, they need 1061/1024 = 2 second-level directories and 1 is one indicates to them, in the end, you need 3 * 1024 * 4 = 12288. And for some reason, the answer is 7 * 1024 * 4. Maybe I do not understand something, can you explain? And tell you how to do it.

  • Most likely, the sizes of some areas are not divided into 4096. It is impossible to add dimensions. Each area must be processed separately. - user58697
  • @ user58697 You can carry out calculations, and if you can then explain the algorithm? I will add the full table to the question now. - thmw
  • @ user58697 Added full version, if you succeed, please explain. - thmw

1 answer 1

Virtual address space is needed in order to limit the access of programs to computer memory. With the help of virtual memory tables, by the address of the memory that the program has, the “physical” address of this memory is obtained. As it is written in the question, “two-level virtual memory is implemented in processors of the x86 family”. This means that in order to obtain a “physical” address from a “virtual” one, the processor first looks up the address of the desired second level table in the first level table (which in the case of x86 contains 1024 entries), and then, in the found second level table, it finds the physical address page size 4 KB.

For example: the program wants to get the value lying at 0x01202c37. The address of the second level table (page table, page directory) in the root table is written in the first ten bits, that is, in this case it is 0x4, the address in the second level table (the next ten bits) is 0x202. The remaining twelve bits indicate a shift within the memory page, in this case it is 0xc37.

The task is to calculate the total number of different tables used to store the specified address ranges. First, one table is always there — this is the root table, it takes 4 KB. It remains to calculate the number of second-level tables (each of which also takes 4 KB). For example, in the example of the condition:

 Диапазон адресов Диапазон адресов таблиц второго уровня 08048000-08053000 020-020 08053000-08054000 020-020 08054000-08055000 020-020 091e3000-09204000 024-024 4f2d0000-4f2ef000 13c-13c 4f2ef000-4f2f0000 13c-13c 4f2f0000-4f2f1000 13c-13c 4f2f7000-4f4a2000 13c-13d 4f4a2000-4f4a3000 13d-13d 4f4a3000-4f4a5000 13d-13d 4f4a5000-4f4a6000 13d-13d 4f4a6000-4f4a9000 13d-13d b75c0000-b77c0000 2dd-2dd b77c0000-b77c1000 2dd-2dd b77d9000-b77da000 2dd-2dd b77da000-b77db000 2dd-2dd bf819000-bf83a000 2fe-2fe

You can see that there are six different addresses of the second level tables: 020, 024, 13c, 13d, 2dd, 2fe. Accordingly, the total size of all tables is 6 * 4096 + 4096 bytes, which is written in the answer.