Comp111: Operating Systems
Classroom Exercise 12 Answers
Hashes, Caches, and Addressing
Fall 2017

  1. The description of the elaborate scheme for IA64 user-space addressing:

    omits how segments -- as used in C programs -- relate to the addressing scheme. How would one represent C program segments in this page scheme, and why?
    Answer: The top bank of address bits in the diagram are analogous to a segment address. The middle bits and page bits form a page address in the segment; these are kept separate only for representational purposes. In fact, however, the segment address could be placed more or less anywhere in the addressing scheme. One could, e.g., use the top three bits of the top level as the segment address rather than the whole top level.
  2. Since the IA64 processor does away with the concept of segments, why does the Linux OS still maintain this concept? What would happen if we stopped organizing pages in segments in the OS?
    Answer: The Linux kernel uses segments to record the states of groups of pages, independent of the processor's interpretation. Segments are still the easiest way for the kernel to remember which pages are read-write, read-only, etc. The processor's interpretation as TLB entries is less efficient if done in physical memory, but easier to implement in hardware.
  3. I claim that -- on average -- the map from page addresses for a segment to page table elements for a segment is dense for page addresses, while the active pages for a segment are sparse for page addresses. Why?
    Answer:The segments are packed with pages from their first addresses, and there are no skipped pages. Thus these are dense sets. However, the active pages are much less dense, because it is not typically true that more than a few pages are being accessed during a computation at a time. In fact, algorithm designers strive for high locality of reference and using as few pages at a time as possible.
  4. The hardware IA64 Translation Lookaside Buffer does not behave like a standard hash in several ways.
    1. It is never a complete hash of all pages. Why?
      Answer: It is in essence a cache of a hash, and not a real hash, in the sense that entries in the TLB can be erased by demand for other entries when it fills up.
    2. It has no collision resolution strategy. What happens if two TLB references collide in the hash?
      Answer: The TLB simply replaces the old entry with the new entry, and the old entry is erased exactly as if the TLB ran out of space. However, this does not happen often in practice, and if the other entry is needed, it is simply reloaded over the newer one.
    3. One concern with the TLB design is that processes can "thrash" by continually forcing new elements into the TLB, thus effectively livelocking all processes. How can this happen, and why?
      Answer: The TLB is a limited resource and thus can fill up. The TLB is designed so that this is difficult but not impossible: the size of the TLB is greater than the typical number of entries needed in the TLB during a scheduling epoch. However, certain memory access patterns -- e.g., reading the first byte of many pages -- can actually exceed the size of the TLB itself. In this case the TLB thrashes just like any other subsystem; there is a constant need to refresh entries because they get erase by competing entries. We are quite fortunate that this form of memory access is rare and that programs that make that kind of access can usually be optimized to avoid it.
  5. (Advanced) One of the last security holes in linux -- that is very difficult to patch -- is that processes can read TLB entries for other processes. What can one learn from that, and why is it a security problem?
    Answer: The TLB doesn't actually contain page contents, but it does contain the locations of pages in logical address space as well as the process id. Thus one cannot tell exactly what a process is doing from its TLB entries, but one can get an idea of the patterns of memory access. This information -- correlated with other spying on the process inputs from outside using supervised machine learning -- can give accurate predictions of exactly what the process is doing at each point in time. Thus it is conceivable that one can exploit TLB access to determine the volumne of sales that a competitor experiences, in real time, by looking for the signature of a sale in the load pattern for the TLB.

    Note that this cannot expose who purchased what; it can simply expose the frequency with which a "sale" routine in the software is executed.

    This vulnerability is mainly active when web services for competitors are co-located on the same physical server by a cloud subscription service, and is one of the main reasons to avoid co-located service plans. The main defense against this is "safety in numbers"; the algorithm does not work well in the presence of noise. So, the way to defeat this algorithm is to run a large number of web services on the same machine, so that the TLB accesses of interest are lost in the noise. The worst-case scenerio is that the web services for a company and its competitor are the only co-located services on a server.