Operating Systems 2022F Lecture 20

Video

Video from the lecture given on November 29, 2022 is now available:

• video
• auto-generated captions

Video is also available through Brightspace (Resources->Zoom meeting->Cloud Recordings tab)

Notes

Lecture 20
----------

4 more classes, including today!
Final exam is on Dec 21, 7 PM

To help you with Assignment 4, you should know how to, in C:
 - return multiple values from a function
 - build up a string from multiple calls to snprintf

Returning multiple values
 - have the caller pass in a pointer to a struct or an array
 - function updates the struct or array

Why do it this way?
 - this way the caller is handling memory management for the data
 - because remember the easiest way to allocate data in C is on the
   stack, but the stack goes away when a function returns
     - so use the caller's stack! (local variables)

Definitely DO NOT use static data to pass data between functions, because
then your functions cannot be called in parallel (non-reentrant), which is a HUGE no-no in kernel dev

When working on A4, if you have trouble inserting a module:
 - make sure other class modules have been removed first
 - if that doesn't work, reboot then try again

Remember that write doesn't use null-terminated strings, it just writes whatever it is given.

Memory map report (virtual -> physical)
argv:       0x00007ffc1ba2e3a8 -> 0x00000000167c63a8
argv[0]:    0x00007ffc1ba2f6c1 -> 0x000000001dd496c1
envp:       0x00007ffc1ba2e3b8 -> 0x00000000167c63b8
envp[0]:    0x00007ffc1ba2f6d0 -> 0x000000001dd496d0
lmsg:       0x0000563a7c11304e -> 0x000000002149f04e
&lmsg:      0x00007ffc1ba2e158 -> 0x00000000167c6158
gmsg:       0x0000563a7c113111 -> 0x000000002149f111
&gmsg:      0x0000563a7c115010 -> 0x0000000028c2d010
&buf:       0x00007ffc1ba2e160 -> 0x00000000167c6160
buf[00]:    0x0000563a7d3d16b0 -> 0x000000000c1786b0
buf[01]:    0x0000563a7d3d26c0 -> 0x000000001dcc16c0
buf[02]:    0x0000563a7d3d36d0 -> 0x0000000015afc6d0
buf[03]:    0x0000563a7d3d46e0 -> 0x0000000029ffe6e0
buf[04]:    0x0000563a7d3d56f0 -> 0x00000000283396f0
buf[05]:    0x0000563a7d3d6700 -> 0x00000000049ef700
buf[06]:    0x0000563a7d3d7710 -> 0x0000000023b24710
buf[07]:    0x0000563a7d3d8720 -> 0x000000001e0e4720
buf[08]:    0x0000563a7d3d9730 -> 0x0000000007bee730
buf[09]:    0x0000563a7d3da740 -> 0x000000000c3db740
buf[10]:    0x0000563a7d3db750 -> 0x00000000071ee750
buf[11]:    0x0000563a7d3dc760 -> 0x000000000e2e2760
buf[12]:    0x0000563a7d3dd770 -> 0x000000000b9e4770
buf[13]:    0x0000563a7d3de780 -> 0x0000000028361780
buf[14]:    0x0000563a7d3df790 -> 0x0000000008199790
buf[15]:    0x0000563a7d3e07a0 -> 0x000000001d9d27a0
buf[16]:    0x0000563a7d3e17b0 -> 0x00000000116477b0
buf[17]:    0x0000563a7d3e27c0 -> 0x00000000258b27c0
buf[18]:    0x0000563a7d3e37d0 -> 0x00000000255357d0
buf[19]:    0x0000563a7d3e47e0 -> 0x000000001b0d07e0
buf[20]:    0x0000563a7d3e57f0 -> 0x000000001e2557f0
buf[21]:    0x0000563a7d3e6800 -> 0x00000000074b2800
buf[22]:    0x0000563a7d3e7810 -> 0x000000000d914810
buf[23]:    0x0000563a7d3e8820 -> 0x000000001dd40820
buf[24]:    0x0000563a7d3e9830 -> 0x0000000029eec830
buf[25]:    0x0000563a7d3ea840 -> 0x00000000356a3840
buf[26]:    0x0000563a7d3eb850 -> 0x000000002834e850
buf[27]:    0x0000563a7d3ec860 -> 0x00000000054c6860
buf[28]:    0x0000563a7d3ed870 -> 0x0000000004286870
buf[29]:    0x0000563a7d3ee880 -> 0x00000000298af880
buf + 0:    0x00007ffc1ba2e160 -> 0x00000000167c6160
buf + 1:    0x00007ffc1ba2e161 -> 0x00000000167c6161
buf + 2:    0x00007ffc1ba2e162 -> 0x00000000167c6162
buf + 3:    0x00007ffc1ba2e163 -> 0x00000000167c6163
buf + 4:    0x00007ffc1ba2e164 -> 0x00000000167c6164
buf + 5:    0x00007ffc1ba2e165 -> 0x00000000167c6165
buf + 6:    0x00007ffc1ba2e166 -> 0x00000000167c6166
buf + 7:    0x00007ffc1ba2e167 -> 0x00000000167c6167
buf + 8:    0x00007ffc1ba2e168 -> 0x00000000167c6168
buf + 9:    0x00007ffc1ba2e169 -> 0x00000000167c6169
buf + 10:    0x00007ffc1ba2e16a -> 0x00000000167c616a
buf + 11:    0x00007ffc1ba2e16b -> 0x00000000167c616b
buf + 12:    0x00007ffc1ba2e16c -> 0x00000000167c616c
buf + 13:    0x00007ffc1ba2e16d -> 0x00000000167c616d
buf + 14:    0x00007ffc1ba2e16e -> 0x00000000167c616e
buf + 15:    0x00007ffc1ba2e16f -> 0x00000000167c616f
buf + 16:    0x00007ffc1ba2e170 -> 0x00000000167c6170
buf + 17:    0x00007ffc1ba2e171 -> 0x00000000167c6171
buf + 18:    0x00007ffc1ba2e172 -> 0x00000000167c6172
buf + 19:    0x00007ffc1ba2e173 -> 0x00000000167c6173
buf + 20:    0x00007ffc1ba2e174 -> 0x00000000167c6174
buf + 21:    0x00007ffc1ba2e175 -> 0x00000000167c6175
buf + 22:    0x00007ffc1ba2e176 -> 0x00000000167c6176
buf + 23:    0x00007ffc1ba2e177 -> 0x00000000167c6177
buf + 24:    0x00007ffc1ba2e178 -> 0x00000000167c6178
buf + 25:    0x00007ffc1ba2e179 -> 0x00000000167c6179
buf + 26:    0x00007ffc1ba2e17a -> 0x00000000167c617a
buf + 27:    0x00007ffc1ba2e17b -> 0x00000000167c617b
buf + 28:    0x00007ffc1ba2e17c -> 0x00000000167c617c
buf + 29:    0x00007ffc1ba2e17d -> 0x00000000167c617d
main:       0x0000563a7c112130 -> 0x000000001d3cd130
puts:       0x00007fa84e0c1ed0 -> 0x0000000119169ed0



Why are the last three digits the same between the physical and virtual address (basically always)?
 - because addresses are divided into a "page/frame number" and an "offset"
   - page number: prefix of a virtual address
   - frame number: prefix of a physical address
 - we mapp a page number to a frame number (upper bits)
   and then add on the offset (lower bits, 12 bits if 4k pages)

on a 64 bit platform, a page + offset = 64 bits (so pointers are 64 bits)
 - but frame + offset can be smaller, as nobody has 2^64 RAM
   (so may only have 48 bit physical addresses)
   (must be expanded if we get more physical memory than can be
    addressed)

A page table is a data structure for mapping page numbers to frame numbers
 - so we can figure out where a virtual address is in physical memory

So for modern x86 systems
 - offset is 12 bits
 - each level of the page table maps 9 bit indexes
    - because 9 bits is 512, 512 * 8 = 4096, so fits in a 4k page!
      (8 is for 8 bytes, or 64 bits per pointer/page table entry)

So resolving an address with a page table means
 - grab top node of page table, PGD, which is an array of 512 pointers (PTE's)
 - take first 9 bits of address, use that as an index into PGD to get index to PUD
 - take next 9 bits of address, use that as an index into the PUD page to get
   the PMD
 - take next 9 bits of address, use that as an index into the PMD page to get
   the PTE
 - take next 9 bits to index into the PTE to get the page
 - use last 12 bits to index into the page to get the actual value of memory


I'm not going to test you about the specific address resolution process
 - but I will want you to understand the role of page tables in resolving virtual to physical addresses.


Page tables are sparse data structures
 - most of the tree isn't there for most processes
 - 0's in key places

So when you do a malloc that calls mmap or sbrk
 - the kernel will be changing the process's page table,
   adding in new entries to accomodate the added RAM
    - sometimes this will just be a couple of pages and the PTE's needed
      to refer to them
    - but if you allocate 1G of RAM, you need a new chunk of the page
      table to be allocated to handle the mapping of all the physical
      pages needed for that RAM

But then again, there are other cheats
 - what if two processes are sharing the same memory?
 - don't copy, just have them both point to the same pages or even page table subtree!