Homework 5
                         DUE: Friday, Mar. 1

We have seen the distinction between IN parameters and OUT parameter in C.
For example, read() used an OUT parameter.  The declaration of read() is:
    ssize_t read(int fd, void *buf, size_t count);
When we invoke read() as below, 'mybuf' is an OUT parameter:
    void foo(int strlen) {
      char *mybuf[100];
      read(0, &mybuf, strlen);
      ...
    }

Next, in the context of a simulator for a cache, we will explore
the concept of a 'linked list' and a 'free list'.
For an exposition of free lists, see:
  https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/Freelist.html
See, especially, example diasgram showing 7 steps in the life of
a free list.

Next, we will apply this to CPU caches:
  fully associative and direct-mapped cache

For a fully associative cache, see Chapter 22 of ostep.org:
  https://pages.cs.wisc.edu/~remzi/OSTEP/vm-beyondphys-policy.pdf

For direct-mapped cache, you can find some good slides are:
  https://courses.cs.washington.edu/courses/cse378/09wi/lectures/lec15.pdf
or perhaps a video presentation in:
    https://www.youtube.com/watch?v=zocwH0g-qQM

For the fully associative cache, you must also define a _cache policy_.
For this assignment, you will use an LRU (Least Recently Used) policy
in the case of fully associative.

====
TO SUBMIT:
    As usual, you will write hw5.c and hw5.in.  In your Makefile, you
will include:

# -a refers to fully associative, nad -d refers to direct-mapped cache.
check: hw5
	./hw5 -a < hw5.in
	./hw5 -d < hw5.in

The file hw5.c will have two behaviors.  If the flag -a is used, then
the cache being simulated is a fully associative cache.  If the flag -d
is used, then the cace is direct-mapped.

./hw will read addresses from 0 to NUM-1 (see below).  For address, it
will produce 'H' or 'M', depending on if the cache operation is a hit
or a miss.  For simplicity, assume that all cache operations are
for "lw".
*** ASSUME THAT EACH DATA BLOCK IS A SINGLE WORD:  4 BYTES ***

When ./hw5 reads from stdin, you must use 'read(0, &mychar, 1)'.
You can then do:
  int num = 0;
  while (1) {
    char mychar;
    int rc = read(0, &mychar, 1).
    if (rc == ) { // if end-of-file
      break;
    }
    if (mychar == ' ' || mychar == '\n' || mychar == ',') { break; }
    num = 10 * num + (mychar - '0'); // ASCII 0, 1, 2, ... == '0', '1', '2'
  }
  // 'num' is the number read.

In the case of a fully associative cache, assume that it is initially empty.
So, the free list initially contains all cache lines (data blocks)
of the cache.  The fully associative cache must use an LRU policy for
the cache lines being used.  When a cache line needs to be replaced,
your must choose that cacne line that was least recently used.

In the case of a direct-mapped cache, you don't need a free list.
So, the idea of a cache policy does not arise.
---

IMPLEMENTATION:

You will define a constant for the number of cache lines:
  #define NUM 128

You will define a struct:
  struct line {
    int address;
    int valid;
    int modified;
  };
   
You will define a cache array as:
  struct line cache[NUM];

You will initialize to valid=0 each line of the cache.

You will initialize the free list as a linked list, based on struct freeNode:
  struct freeNode {
    int cacheIndex;
    struct freeNode *next;
    struct freeNode *prev; // NOT USED FOR single linked list of free list
  }
A special head node for the free list will be cacheIndex=-1.
The free list will point to index 0, 1, 2, ..., in that order.
The last freeNode will set next=NULL.

You will initialize the busy list as a linked list, based on struct busyNode:
  struct busyNode {
    int cacheIndex;
    struct busyNode *next;
    struct busyNode *prev;
  }
A special head node for the busy list will be cacheIndex=-1.
The busy list will be empty.  So, the head node will the next and prev
fields to NULL.  The last busyNode will set next=NULL.

NOTE:
    In order to refer to a field of cache line (data block), one can
    write:  cache[busyNode.cacheIndex].FIELD
    for FIELD being address, valid, or modified.

SUGGESTED IMPLEMENTATION:
    There remains a question of how to allocate storage for the nodes
of the linked list.  One suggestion is to allocate the nodes that you
need in advance.

struct node {
  int cacheIndex;
  struct Node *next;
  struct Node *prev;
}
struct Node list_of_nodes[NUM];

struct node headFreeList;
struct node headBusyList;

// NOTE:  This was fixed.  Earlier, it used 'struct node myNode'.
void init_free_list() {
  struct node *myNode = &headFreeList;
  myNode->cacheIndex = -1;
  myNode->next = &(list_of_nodes[0]);  // RECALL: '&' means "address of"
  for (int i = 0; i < NUM-1; i++){
    myNode = &list_of_nodes[i];
    myNode->prev = NULL;
    myNode->cacheIndex = i;
    myNode->next = &(list_of_nodes[i+1]);
  }
  myNode->prev = NULL;
  myNode->cacheIndex = NUM-1;
  myNode->next = NULL;
}

void init_busy_list() {
  headBusyList.cacheIndex = -1;
  headBusyList.next = NULL;
}

If you initialize your busy list and free list according to the suggestion
above, then you will not need to allocate any extra "struct node".  You
already have NUM "struct node" (initially on the free list).  Then, when
you have a cache miss, if you still have a "struct node" on the free list,
you can transfer it to to the busy list list, and then update
the address, valid, and modifieded fields of the cache line (cacheIndex)
that it points to.

----
MOTIVATION:

In this implementation, we can linearly search the busy list (the list for
which V=1), to see if an address is contained in the cache.  if an address
was not found in the cache, then we wish to select an unused cache line
(V=0).  For the sake of uniqueness, this simulation implements the free
list as a FIFO list, and the head of the list is selected.

The data structures for busy and free lists is used in many areas of
operating systems code, as well as other subjects.

----
NOTE:
hw5.in was generated by:
   python3 -c 'import random; print([4 * random.randrange(0,256) for i in range (200)])'  > hw5.in