IITGN-Operating-Systems.github.io/404.html at master · IITGN-Operating-Systems/IITGN-Operating-Systems.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
<!DOCTYPE html>
<html lang="en-us">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1" />

    <meta http-equiv="cache-control" content="max-age=0" />
    <meta http-equiv="cache-control" content="no-cache" />
    <meta http-equiv="expires" content="0" />
    <meta http-equiv="expires" content="Tue, 01 Jan 1980 1:00:00 GMT" />
    <meta http-equiv="pragma" content="no-cache" />

    <link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png"}>
    <link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
    <link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
    <link rel="manifest" href="/site.webmanifest">

    <meta name="theme-color" media="(prefers-color-scheme: light)" content="#1b1b1b" />
    <meta name="theme-color" media="(prefers-color-scheme: dark)" content="#1b1b1b" />

    <meta name="description" content="404 Page not found">


        <title>404 Page not found | OS Labs</title>


    <style>
        :root {
          --background: #1b1b1b;
        }
        @media (prefers-color-scheme: dark) {
          :root {
            --background: #1b1b1b;
          }
        }
        html {
            background-color: var(--background);
        }
        body {
            background-color: var(--background);
        }
    </style>


    <link rel="stylesheet" type="text/css" href="/style.min.8b321058a79ec67e36fab2e8ec98f882ec83a2fb260aa37f50936110b5fbcd02.css" media="all">
  </head>

  <body>

        <nav>
          <ul class="menu">

                <li><a tabindex="-1" class="menu-link" href="/">Home</a></li>

                <li><a tabindex="-1" class="menu-link" href="/tags">Tags</a></li>

          </ul>
        </nav>


404 NOT FOUND

<br>

<footer>

<script defer>
  document.addEventListener("keydown", function (e) {
    if (document.activeElement.isContentEditable) {
      return false;
    }
    if (document.activeElement.tagName == "INPUT") {
      return false;
    }
    if (e.altKey || e.ctrlKey || e.shiftKey) {
      return false;
    }
    var key = e.key;
    if (key === "h") {
      e.preventDefault();
      e.stopPropagation();
      window.location.href = "/";
    } else if (key === "t") {
      e.preventDefault();
      e.stopPropagation();
      window.location.href = `https://${location.hostname}/tags`;
    } else if (key === "i") {
      e.preventDefault();
      e.stopPropagation();
      const inputs = document.querySelectorAll("input");
      for (let i = 0; i < inputs.length; i++) {
        if (inputs[i].offsetParent !== null) {
          inputs[i].selectionStart = inputs[i].selectionEnd =
            inputs[i].value.length;
          inputs[i].focus();
          break;
        }
      }
    }
    return false;
  });
</script>


<script defer>
  function throttle(fn, wait) {
    var time = Date.now();
    return function () {
      var now = Date.now()
      if (time + wait - now < 0) {
        fn();
        time = now;
      }
    };
  }

  function scrollHandler() {
    const anchors = Array.from(document.querySelectorAll("body h2, body h3"));

    function scrollCallback() {
      var scrollTop = window.pageYOffset || document.documentElement.scrollTop;


      for (var i = 0; i < anchors.length; i++) {
        var anchorId = anchors[i].getAttribute("id");
        var link = document.querySelector(
          'nav ul li a[href="#' + anchorId + '"]',
        );
        if (link) {
          link.classList.remove("active-toc");
        }
      }


      for (var i = anchors.length - 1; i >= 0; i--) {
        var offsetTop = anchors[i].offsetTop;
        if (scrollTop > offsetTop - 75) {
          var anchorId = anchors[i].getAttribute("id");
          var link = document.querySelector(
            'nav ul li a[href="#' + anchorId + '"]',
          );
          if (link) {
            link.classList.add("active-toc");
            break;
          }
        }
      }
    }

    window.addEventListener(
      "scroll",
      throttle(scrollCallback, 300),
    );
  }
  setTimeout(scrollHandler, 100);
</script>

<script defer>
  function addCopyButtonToCodeBlocks() {

    const codeBlocks = document.querySelectorAll('code[class^="language-"]');

    codeBlocks.forEach((codeBlock) => {
      const copyButton = document.createElement("button");
      copyButton.classList.add("copy-code-button");
      copyButton.innerHTML = "copy";


      copyButton.addEventListener("click", () => {

        const elements = codeBlock.querySelectorAll(".cl");
        let codeToCopy = "";
        elements.forEach((element) => {
          codeToCopy += element.innerText;
        });
        navigator.clipboard.writeText(codeToCopy);


        copyButton.innerHTML = "copied!";
        setTimeout(() => {
          copyButton.innerHTML = "copy";
        }, 1500);
      });


      codeBlock.parentNode.before(copyButton);
    });
  }
  setTimeout(function () {
    addCopyButtonToCodeBlocks();
  }, 100);
</script>

<script>
window.store = {

    "\/post\/": {
        "title": "Posts",
        "tags": [],
        "content": "",
        "url": "\/post\/"
    },

    "\/tags\/lab\/": {
        "title": "Lab",
        "tags": [],
        "content": "",
        "url": "\/tags\/lab\/"
    },

    "\/post\/lab5\/": {
        "title": "Lab 5: FAT32 Filesystem",
        "tags": ["Lab",],
        "content": "Introduction In this assignment, you will enable the use of Rust\u0026rsquo;s collections module (Vec, String, HashMap, and friends) by writing a memory allocator, implement the FAT32 file system, implement a Rust interface for a driver for the Raspberry Pi\u0026rsquo;s EMMC (SD card controller), and extend your shell with cd, ls, pwd, and cat, commands.\nPhase 0: Getting Started Fetch the update for lab 5 from our git repository to your development machine.\n$ git fetch skeleton $ git merge skeleton/lab5 This is the directory structure of our repository. The directories you will be working on this assignment are marked with *.\n. ├── bin : common binaries/utilities ├── doc : reference documents ├── ext : external files (e.g., resources for testing) ├── boot : bootloader ├── kern : the main os kernel * └── lib : required libraries ├── fat32 * ├── pi * ├── shim ├── stack-vec ├── ttywrite ├── volatile └── xmodem You may need to resolve conflicts before continuing. For example, if you see a message that looks like:\nAuto-merging kern/src/main.rs CONFLICT (content): Merge conflict in kern/src/main.rs Automatic merge failed; fix conflicts and then commit the result. You will need to manually modify the main.rs file to resolve the conflict. Ensure you keep all of your changes from lab 4. Once all conflicts are resolved, add the resolved files with git add and commit. For more information on resolving merge conflicts, see this tutorial on githowto.com .\nCompilation errors after merging lab5\nWe provide a template code for the final phase of lab5, which contains lots of uncompleted code. When you try to compile your code while working on this lab, you will see the compiler complains about some of the code you just merged. You can comment the offensive lines of the code until we fix them later. For instance, you may want to disable the file system component when working in phase 1. Make sure you only comment out minimum amount of the code!\nThe ALLOCATOR.initialize() call panics!\nYour shell should continue to function as before. If you test the make install target now, however, you\u0026rsquo;ll likely find that you shell appears to no longer work. The likely culprit is an ALLOCATOR.initialize() call preceding your shell() call. Because there is no memory allocator yet, the call will lead to a panic!(), halting your system without warning. We\u0026rsquo;ll fix this soon. Feel free to comment out the line temporarily to ensure everything is working as expected.\nPhase 1: Memory Lane In this phase you will implement two memory allocators: a simple bump allocator and a more fully-featured bin allocator. These will immediately enable the use of heap allocating structures such as Vec, Box, and String. To determine the available memory on the system for allocation, you will read ARM tags (ATAGS ). You will also implement the panic handler to properly handle panic! calls.\nSubphase A: Panic! In this subphase you will implement the panic handler. You will be working in kern/src/init/panic.rs.\nError Handling in Rust Rust has two major categories of errors: recoverable and unrecoverable. Rust represents recoverable errors with Result\u0026lt;T, E\u0026gt; type. On the other hand, when a Rust program encounters an unrecoverable error, it stops the program execution altogether. This behavior is called panic! in Rust terminology.\nWhen targeting standard operating systems, the Rust compiler will generate a program that prints the backtrace and sets the process exit code on panic. However, when the Rust compiler is instructed to compile a Rust program for a target without operating system support, such as we do for our Raspberry Pi, the compiler requires the manual implementation of the panic handler.\nA panic handler is a function that is called when a panic! occurs. It has a type of fn panic(info: PanicInfo) -\u0026gt; !, which means it takes a PanicInfo as an argument and never returns. PanicInfo struct contains the information of the file name, line number, and column where the panic! occurred.\nWe\u0026rsquo;ve provided the panic handler that loops indefinitely in kern/src/init/panic.rs. You will extend this panic implementation so that it logs useful information to the console.\nImplement the panic handler Implement the panic function now. Your implementation should print the passed in information to the console and then allow the loop already in place to run. You\u0026rsquo;re free to implement the function as you like. As an example, our implementation takes inspiration from Linux kernel oops messages:\n( ( ) ) ) ( ( ( ` .-\u0026#34;\u0026#34;^\u0026#34;\u0026#34;\u0026#34;^\u0026#34;\u0026#34;^\u0026#34;\u0026#34;\u0026#34;^\u0026#34;\u0026#34;-. (//\\\\//\\\\//\\\\//\\\\//\\\\//) ~\\^^^^^^^^^^^^^^^^^^/~ `================` The pi is overdone. ---------- PANIC ---------- FILE: src/kmain.rs LINE: 40 COL: 5 index out of bounds: the len is 3 but the index is 4 Test your new panic implementation by having your kernel panic. Recall that you can use the new make install target to compile and send the kernel to your Raspberry Pi. Note that the ALLOCATOR.initialize() call already panic! s, so you shouldn\u0026rsquo;t need to make any changes. Ensure this function is called before your shell().\nThen, try making your kernel panic in other ways: a rogue unwrap(), an explicit panic!(), or an unreachable!(): ensure they all work as expected. When you\u0026rsquo;re satisfied with your implementation, continue to next the subphase.\nSubphase B: ATAGS In this subphase, you will implement an iterator over the ARM tags (ATAGS) loaded by the Raspberry Pi\u0026rsquo;s firmware. You will use your iterator to find the ATAG that specifies how much memory is available on the system. You will be working in the lib/pi/src/atags directory and kern/src/allocator.rs.\nARM Tags ATAGS , or ARM tags, are a mechanism used by ARM bootloaders and firmware to pass information about the system to the kernel. Linux, for example, can use ATAGS when configured for the ARM architecture.\nThe Raspberry Pi places an array of ATAG structures at address 0x100. This is the structure of ATAGS, in Rust syntax:\n#[repr(C)] struct Atag { dwords: u32, tag: u32, kind: Kind } Each ATAG begins with an 8 byte header, dwords and tag. The dwords field specifies the size of the complete ATAG in double words (32-bit words) and includes the header. Thus the minimum size is 2. The tag field specifies the type of the ATAG. There are 10 different types of specified tags, all documented in the ATAGS reference . The Raspberry Pi only makes use of four. These are documented below:\nName Type (tag) Size Description CORE 0x54410001 5 or 2 if empty First tag used to start list NONE 0x00000000 2 Empty tag used to end list MEM 0x54410002 4 Describes a physical area of memory CMDLINE 0x54410009 variable Command line to pass to kernel The type of tag determines how the data after the header should be interpreted. In our skeleton code, the data following the header is represented as a field named kind which is a union of different kind of tags. Clicking on the name of the tag in the table above directs you to the reference for that particular tag which includes the layout of the tag\u0026rsquo;s data. The MEM tag data, for instance, is structured as below:\nstruct Mem { size: u32, start: u32 } Tags are laid out sequentially in memory with zero padding between each tag. The first tag is specified to be a CORE tag while the final tag is indicated by the NONE tag. Other tags can appear in any order. The dwords field is used to determine the address of the adjacent ATAG. The diagram below depicts the general layout.\nUnions \u0026amp; Safety The raw ATAG data structures are declared in lib/pi/src/atags/raw.rs. The main declaration, copied below, makes use of a Rust union. Rust\u0026rsquo;s unions are identical to C unions: they define a structure where all fields share common storage.\npub struct Atag { dwords: u32, tag: u32, kind: Kind } pub union Kind { core: Core, mem: Mem, cmd: Cmd } In effect, unions allow memory to be cast into arbitrary structures without regard for whether the cast is correct. As a result, accessing union fields in Rust is unsafe.\nWe\u0026rsquo;ve already handled most of the unsafe in the atags module for you, so you don\u0026rsquo;t need to worry about handling unions yourself. Nonetheless, exposing unions to end-users of our pi library is a bad idea. Because of this, we\u0026rsquo;ve declared a second Atag structure in lib/pi/src/atags/atag.rs. This structure is entirely safe to use and access. This is the structure that the pi library will expose. When you finish the implementation of the atag module later in this subphase, you\u0026rsquo;ll write conversions from the raw structures to the safe structures.\nWhy is it a bad idea to expose unions to end-users? (enduser-unsafe)\nWe\u0026rsquo;re going through a lot of effort to expose a safe interface to unsafe data structures. You\u0026rsquo;ll see this over and over again in Rust, with the standard library as a prime example. What benefit is there to exposing safe interfaces to unsafe structures or operations in Rust? Could we yield the same benefits in a language like C?\nCommand Line Arguments The CMDLINE tag deserves special attention. Its declaration is:\nstruct Cmd { /// The first byte of the command line string. cmd: u8 } As indicated by the comment, the cmd field holds the first byte of the command line string. In other words, \u0026amp;cmd is a pointer to a null-terminated, C-like string. The safe version of the Cmd tag is Cmd(\u0026amp;'static str). When you write the conversion from the raw to safe version of the Cmd tag, you\u0026rsquo;ll need to determine the size of the C-like string by searching for the null terminator in the string. You\u0026rsquo;ll then need to cast the address and size into a slice using slice::from_raw_parts() and finally cast the slice into a string using str::from_utf8() or str::from_utf8_unchecked().\nImplement atags You\u0026rsquo;re ready to implement the atags module in lib/pi/src/atags. Start by implementing the raw::Atag::next() method in atags/raw.rs. The method determines the address of the ATAG following self and returns a reference to it. You\u0026rsquo;ll need to use unsafe in your implementation. Then implement the helper methods and conversion traits from raw structures to safe structures in atags/atag.rs. You should only need to use unsafe when implementing From\u0026lt;\u0026amp;'a raw::Cmd\u0026gt; for Atag. Finally, finish the implementation of the Iterator trait for Atags in atags/mod.rs. This requires no unsafe.\nYou can convert from x: \u0026amp;T to *const u32 using x as *const T as *const u32.\nYou can convert from x: *const T to \u0026amp;T using \u0026amp;*x. However, this conversion is extremely unsafe. Make sure that you don\u0026rsquo;t violate the alias rule of Rust references.\nYou can perform pointer arithmetic with add() , sub() , or offset() .\nTesting atags Test your implementation by running cargo test command in lib/pi directory. Then, test your ATAGS implementation with the RPi board by iterating over all of the ATAGS and debug printing them to your console in kern/src/main.rs. You should see at least one of each of the three non-NONE tags. Verify that the value of each ATAG matches your expectations. Once your implementation performs as expected, proceed to the next subphase.\nThe {:#?} format specifier prettifies the debug output of a structure.\nWhat does the CMDLINE ATAG contain? (atag-cmdline)\nWhat is the value of the command line string in the CMDLINE ATAG found on your Raspberry Pi? What do you think the parameters control?\nHow much memory is reported by the MEM tag? (atag-mem)\nWhat is the exact start address and size of the available memory reported by the MEM ATAG? How close is this to the Raspberry Pi\u0026rsquo;s purported 1GB of RAM?\nSubphase C: Warming Up In this subphase, we\u0026rsquo;ll set the stage to write our two memory allocators in the next subphases. You\u0026rsquo;ll implement two utility functions, align_up and align_down, that align addresses to a power of two. You\u0026rsquo;ll also implement the memory_map function that returns the start and end address of the available memory on the system. Your memory_map function will be used by both memory allocators to determine the available memory for allocation.\nAlignment A memory address is n-byte aligned if it is a multiple of n. Said another way, a memory address k is n-byte aligned if k % n == 0. We don\u0026rsquo;t usually need to be concerned about the alignment of our memory addresses, but as budding system\u0026rsquo;s programmers, we do! This is because hardware, protocols, and other external forces enjoin alignment properties. For example, the ARM 32-bit architecture requires the stack pointer to be 8-byte aligned. The AArch64 architecture, our operating system\u0026rsquo;s architecture of choice, requires the stack pointer to be 16-byte aligned; x86-64 requires the same alignment. Page addresses used for virtual memory typically need to be 4k-byte aligned. And there are many more examples, but it suffices to say that alignment of memory addresses is important.\nIn C, the alignment of a memory address returned from a libC allocator is guaranteed to be 8-byte aligned on 32-bit systems and 16-byte aligned on 64-bit systems. Beyond this, the caller has no control over the alignment of the returned memory address and must fend for themselves (POSIX functions like posix_memalign later corrected for this).\nWhy did C choose these alignments? (libc-align)\nThe choice to guarantee 8 or 16-byte alignment from libC\u0026rsquo;s malloc is not without reason. Why did libC choose these particular alignment guarantees?\nRecall the signatures for malloc() and free() in C:\nvoid *malloc(size_t size); void free(void *pointer); In contrast, Rust\u0026rsquo;s low-level, unsafe alloc and dealloc methods in GlobalAlloc trait have the following signatures:\n// `layout.size()` is the requested size, `layout.align()` the requested alignment unsafe fn alloc(\u0026amp;self, layout: Layout) -\u0026gt; *mut u8; // `layout` should be the same as was used for the call that returned `ptr` unsafe fn dealloc(\u0026amp;self, ptr: *mut u8, layout: Layout) Note that the caller can specify the alignment with the layout argument, which is defined by two parameters, size and align. As a result, the onus is on the allocator, not the caller, to return a properly aligned memory address. When you implement memory allocators in the next phase, you\u0026rsquo;ll need to ensure that the address you return satisfies the condition specified by the layout parameter.\nThe second thing to note is that the dealloc function, analogous to C\u0026rsquo;s free, requires the caller to pass in the Layout used for the original call to alloc. As a result, the onus is on the caller, not the allocator, to remember the requested size and alignment of an allocation.\nSize and alignment guarantee in Rust\nIn Rust, all layouts must have non-negative size and a power-of-two alignment; These conditions are checked when a layout is created.\nWhy do you think Rust split responsibilities in this way? (onus)\nIn C, the allocator has fewer restrictions on the alignment of memory addresses it returns but must record the size of an allocation for later use. The inverse is true in Rust. Why do you think Rust chose the opposite path here? What advantages does it have for the allocator and for the caller?\nUtilities: align_up and align_down When you implement your allocators in the next subphases, you\u0026rsquo;ll find it useful to, given a memory address u, be able to determine the first address \u0026gt;= or \u0026lt;= u that is aligned to a power of two. The (unimplemented) align_up and align_down functions in kernel/src/allocator/util.rs do exactly this:\n/// Align `addr` downwards to the nearest multiple of `align`. /// Panics if `align` is not a power of 2. fn align_down(addr: usize, align: usize) -\u0026gt; usize; /// Align `addr` upwards to the nearest multiple of `align`. /// Panics if `align` is not a power of 2 /// or aligning up overflows the address. fn align_up(addr: usize, align: usize) -\u0026gt; usize; Implement these functions now. You can unit test your implementations by calling make test or cargo test in the kernel directory. This will run the tests in kern/src/allocator/tests.rs. All of the align_util unit tests should pass.\nTesting\nDuring testing, calls to kprint{ln}! become calls to print{ln}!.\nThread Safety Memory allocators like libC\u0026rsquo;s malloc() and the two you will soon implement are global: they can be called by any thread at any point in time. As such, the allocator needs to be thread safe, and that\u0026rsquo;s why alloc() and dealloc() method take shared (aliasable) reference \u0026amp;self``, like other synchronization primitives such as Mutex and RwLock . Rust takes thread safety very seriously, and so it is difficult to implement an allocator that isn\u0026rsquo;t thread-safe even if our system doesn\u0026rsquo;t have any concurrency mechanisms like threads just yet.\nThe topic of thread-safe memory allocators is extensive, and many research papers have been published on exactly this topic. To avoid a deep tangent, we\u0026rsquo;ll ignore the topic altogether and wrap our allocator in a Mutex ensuring that it is thread-safe by virtue of exclusion. We\u0026rsquo;ve provided the code that will wrap your allocators in kern/src/allocator.rs. Read through the code now. Notice how it implements Rust\u0026rsquo;s GlobalAlloc trait; this is how Rust knows that it is a valid allocator. An implementation of this trait is required to register an instance of the struct as a #[global_allocator], which we\u0026rsquo;ve done for you in main.rs. Once an instance is registered via the #[global_allocator] annotation, we can use structures like Vec``, ``String``, and ``Box`` via the alloc crate and Rust will forward the alloc() and dealloc() calls to our registered instance.\nUtility: memory_map The final item in the kern/src/allocator.rs file is the memory_map function. This function is called by the Allocator::initialize() method which in-turn is called in kmain(). The initialize() method constructs an instance of the internal imp::Allocator structure for use in later allocations and deallocations.\nThe memory_map function is responsible for returning the start and end address of all of the free memory on the system. Note that the amount of free memory is unlikely to be equal to the total amount of memory on the system, the latter of which is identified by ATAGS. This is because memory is already being used by data like the kernel\u0026rsquo;s binary. memory_map should take care not to mark used memory as free. To assist you with this, we\u0026rsquo;ve declared the binary_end variable which holds the first address after the kernel\u0026rsquo;s binary.\nImplement the memory_map function now by using your Atags implementation from Subphase B and the binary_end variable. Ensure that the function returns the expected values. Then add a call to String::from(\u0026quot;Hi!\u0026quot;) (or any other allocating call) and ensure that a panic!() occurs because of an unimplemented bump allocator. If memory_map() returns what you expect and a call to AllocatorImpl::new() panics because the bump allocator hasn\u0026rsquo;t been implemented yet, proceed to the next subphase.\nSubphase D: Bump Allocator In this subphase, you will implement the simplest of allocators: the bump allocator. You will be working in kern/src/allocator/bump.rs.\nSwitching Implementations\nThe GlobalAlloc implementation for Allocator in kernel/src/allocator.rs simply forwards calls to an internal AllocatorImpl after taking a lock. We\u0026rsquo;ll start with the bump::Allocator in bump.rs and later switch to the bin::Allocator in bin.rs.\nA bump allocator works like this: on alloc, the allocator returns a current pointer, modified as necessary to guarantee the requested alignment, and bumps the current pointer up by the size of the requested allocation plus whatever was necessary to fulfill the alignment request. If the allocator runs out of memory, it returns an error. On dealloc, the allocator does nothing.\nThe diagram below depicts what happens to the current pointer after a 1k byte allocation and a subsequent 512 byte allocation. Note that alignment concerns are absent in the diagram.\nYour task is to implement a bump allocator in kernel/src/allocator/bump.rs. In particular, implement the new(), alloc(), and dealloc() methods of bump::Allocator. Use your align_up and align_down utility functions as necessary to guarantee the proper alignment of the returned addresses. We\u0026rsquo;ve provided unit tests that check the basic correctness of your implementation. You can run them with make test or cargo test in the kernel directory. You should pass all of the allocator::bump_ unit tests.\nEnsure that you don\u0026rsquo;t perform any potentially overflowing operations!\nUse the saturating_add and saturating_sub methods as necessary to prevent arithmetic overflow.\nOnce all of the unit tests pass, try allocating memory in kmain() to \u0026ldquo;see\u0026rdquo; your allocator in action. Here\u0026rsquo;s a simple test:\nuse alloc::vec::Vec; let mut v = Vec::new(); for i in 0..50 { v.push(i); kprintln!(\u0026#34;{:?}\u0026#34;, v); } Once your implementation works as expected, proceed to the next subphase.\nWhat does the alloc call chain look like? (bump-chain)\nIf you paused execution when bump::Allocator::alloc() gets called, what would the backtrace look like? Asked another way: explain in detail how a call like v.push(i) leads to a call to your bump::Allocator::alloc() method.\nSubphase E: Bin Allocator In this subphase, you will implement a more complete allocator: the bin allocator. You will be working in kern/src/allocator/bin.rs.\nA bin allocator segments memory allocations into size classes, or bins. The specific size classes are decided arbitrarily by the allocator. Each bin holds a linked-list of pointers to memory of the bin\u0026rsquo;s size class. Allocations are rounded up to the nearest bin: if there is an item in the bin\u0026rsquo;s linked list, it is popped and returned. If there is no free memory in that bin, new memory is allocated from the global pool and returned. Deallocation pushes an item to the linked list in the corresponding bin.\nOne popular approach is to divide bins into powers of two. For example, an allocator might choose to divide memory allocations into k - 2 bins with sizes 2^n for n from 3 to k (2^3, 2^4, \u0026hellip;, 2^k). Any allocation or deallocation request for less than or equal to 2^3 bytes would be handled by the 2^3 bin, requests between 2^3 and 2^4 bytes from the 2^4 bin, and so on:\nbin 0 (2^3 bytes): handles allocations in (0, 2^3] bin 1 (2^4 bytes): handles allocations in (2^3, 2^4] \u0026hellip; bin 29 (2^32 bytes): handles allocations in (2^31, 2^32] Linked List We\u0026rsquo;ve provided an implementation of an intrusive linked list of memory addresses in kern/src/allocator/linked_list.rs. We\u0026rsquo;ve also imported the LinkedList struct in kern/src/allocator/bin.rs.\nWhat\u0026rsquo;s an instrusive linked list?\nIn an intrusive linked list, next and previous pointers, if any, are stored in the pushed items themselves. An intrusive linked list requires no additional memory, beyond the item, to manage an item. On the other hand, the user must provide valid storage in the item for these pointers.\nA new, empty list is created using LinkedList::new(). A new address can be prepended to the list using push(). The first address in the list, if any, can be removed and returned using pop() or returned (but not removed) using peek():\nlet mut list = LinkedList::new(); unsafe { list.push(address_1); list.push(address_2); } assert_eq!(list.peek(), Some(address_2)); assert_eq!(list.pop(), Some(address_2)); assert_eq!(list.pop(), Some(address_1)); assert_eq!(list.pop(), None); LinkedList exposes two iterators. The first, obtained via iter(), iterates over all of the addresses in the list. The second, returned from iter_mut(), returns Node s that refer to each address in the list. The value() and pop() methods of Node can be used to read the value or pop the value from the list, respectively.\nlet mut list = LinkedList::new(); unsafe { list.push(address_1); list.push(address_2); list.push(address_3); } for node in list.iter_mut() { if node.value() == address_2 { node.pop(); } } assert_eq!(list.pop(), Some(address_3)); assert_eq!(list.pop(), Some(address_1)); assert_eq!(list.pop(), None); Read through the code for LinkedList now. Pay special attention to the safety properties required to call push() safely. You\u0026rsquo;ll likely want to use LinkedList to manage the bins in your memory allocator.\nWhy is it convenient to use an intrusive linked list? (ll-alloc)\nUsing an intrusive linked list for our memory allocators turns out to be a very convenient decision. What issues would arise if we had instead decided to use a regular, allocate-additional-memory-on-push, linked list?\nFragmentation The concept of fragmentation refers to memory that is unused but unallocatable. An allocator incurs or creates high fragmentation if it creates a lot of unusable memory throughout the course of handling allocations. An ideal allocator has zero fragmentation: it never uses more memory than necessary to handle a request and it can always use available memory to handle new requests. In practice, this is neither desired nor achievable given other design constraints. But striving for low fragmentation is a key quality of good memory allocators.\nWe typically define two kinds of fragmentation:\ninternal fragmentation\nThe amount of memory wasted by an allocator to due to rounding up allocations. For a bin allocator, this is the difference between a request\u0026rsquo;s allocation size and the size class of the bin it is handled from.\nexternal fragmentation\nThe amount of memory wasted by an allocator due to being unable to use free memory for new allocations. For a bin allocator, this is equivalent to the amount of free space in every bin that can\u0026rsquo;t be used to handle an allocation for a larger request even though the sum of all of the free space meets or exceeds the requested size.\nYour allocator should try to keep fragmentation down within reason.\nImplementation Implement a bin allocator in kern/src/allocator/bin.rs. Besides being a bin-like allocator, the design of the allocator is entirely up to you. The allocator must be able to reuse freed memory. The allocator must also not incur excessive internal or external fragmentation. Our unit tests, which you can run with make test to check these properties. Remember to change AllocatorImpl to bin::Allocator in kern/src/allocator.rs so that your bin allocator is used for global allocations.\nOnce your allocator passes all tests and is set as the global allocator, proceed to the next phase.\nWhat does your allocator look like? (bin-about)\nBriefly explain the design of your allocator. In particular answer the following questions:\nWhich size classes did you choose and why? How does your allocator handle alignment? What are the bounds on internal and external fragmentation for your design choices? How could you decrease your allocator\u0026rsquo;s fragmentation? (bin-frag)\nYour allocator probably creates more fragmentation that it needs to, and that\u0026rsquo;s okay! How could you do better? Sketch (only in writing) two brief design ideas for improving your allocator\u0026rsquo;s fragmentation.\nPhase 2: 32-bit Lipids In this phase, you will implement a read-only FAT32 file system. You will be working primarily in the lib/fat32 directory.\nDisks and File Systems Data on a disk is managed by one or more file systems. Much like a memory allocator, a file system is responsible for managing, allocating, and deallocating free disk space. Unlike the memory managed by an allocator, the disk is persistent: barring disk failure, a write to allocated disk space is visible at any point in the future, including after machine reboots. Common file systems include EXT4 on Linux, HFS+ and APFS on macOS, and NTFS on Windows. FAT32 is another file system that is implemented by most operating systems, including Linux, macOS, and Windows, and was used in older versions of Windows and later versions of DOS. Its main advantage is its ubiquity: no other file system sees such cross-platform support.\nTo allow more than one file system to reside on a physical disk, a disk can be partitioned. Each partition can formatted for a different file system. To partition the disk, a table is written out to a known location on the disk that indicates where each partition begins and ends and the type of file system the partition uses. One commonly used partitioning scheme uses a master boot record, or MBR, that contains a table of four partition entries, each potentially unused, marking the start and size of a partition. GPT is a more modern partitioning scheme that, among other things, allows for more than four partitions.\nIn this assignment you will be writing the code to interpret an MBR partitioned disk that includes a FAT32 partition. This is the combination used by the Raspberry Pi: the SD card uses the MBR scheme with one partition formatted to FAT32.\nDisk Layout The following diagram shows the physical layout of an MBR-partitioned disk with a FAT32 file system:\nThe FAT structures PDF contains the specific details about all of these structures including their sizes, field locations, and field descriptions. You will be referring to this document when you implement your file system. You may also find the FAT32 design Wikipedia entry useful while implementing your file system.\nMaster Boot Record The MBR is always located on sector 0 of the disk. The MBR contains four partition entries, each indicating the partition type (the file system on the partition), the offset in sectors of the partition from the start of the disk, and a boot/active indicator that dictates whether the partition is being used by a bootable system. Note that the CHS (cylinder, header, sector) fields are typically ignored by modern implementations; your should ignore these fields as well. FAT32 partitions have a partition type of 0xB or 0xC.\nExtended Bios Parameter Block The first sector of a FAT32 partition contains the extended BIOS parameter block, or EBPB. The EBPB itself starts with a BIOS parameter block, or BPB. Together, these structures define the layout of the FAT file system.\nOne particularly important field in the EBPB indicates the \u0026ldquo;number of reserved sectors\u0026rdquo;. This is an offset from the start of the FAT32 partition, in sectors, where the FATs (described next) can be found. Immediately after the last FAT is the data region which holds the data for clusters. FATs, the data region, and clusters are explained next.\nClusters All data stored in a FAT file system in separated into clusters. The size of a cluster is determined by the \u0026ldquo;number of sectors per cluster\u0026rdquo; field of the EBPB. Clusters are numbered starting at 2. As seen in the diagram, the data for cluster 2 is located at the start of the data region, the data for cluster 3 is located immediately after cluster 2, and so on.\nFile Allocation Table FAT stands for \u0026ldquo;file allocation table\u0026rdquo;. As the name implies, a FAT is a table (an array) of FAT entries. In FAT32, each entry is 32-bits wide; this is where the name comes from. The size of a complete FAT is determined by the \u0026ldquo;sectors per FAT\u0026rdquo; and \u0026ldquo;bytes per sectors\u0026rdquo; fields of the EBPB. For redundancy, there can be more than one FAT in a FAT32 file system. The number of FATs is determined by a field of the same name in the EBPB.\nBesides entries 0 and 1, each entry in the FAT determines the status of a cluster. Entry 2 determines the status of cluster 2, entry 3 the status of cluster 3, and so on. Every cluster has an associated FAT entry in the FAT.\nFAT entries 0 and 1 are special:\nEntry 0: 0xFFFFFFFN, an ID. Entry 1: The end of chain marker. Aside from these two entries, all other entries correspond to a cluster whose data is in the data region. While FAT entries are physically 32-bits wide, only 28-bits are actually used; the upper 4 bits are ignored. The value is one of:\n0x?0000000: A free, unused cluster. 0x?0000001: Reserved. 0x?0000002-0x?FFFFFEF: A data cluster; value points to next cluster in chain. 0x?FFFFFF0-0x?FFFFFF6: Reserved. 0x?FFFFFF7: Bad sector in cluster or reserved cluster. 0x?FFFFFF8-0x?FFFFFFF: Last cluster in chain. Should be, but may not be, the EOC marker. Cluster Chains Clusters form chains, or linked lists of clusters. If a cluster is being used for data, its corresponding FAT entry value either points to the next cluster in the chain or is the EOC marker indicating it is the final cluster in the chain.\nAs an example, consider the diagram below which depicts a FAT with 8 entries.\nThe clusters are color coded to indicate which chain they belong to. The first two entries are the ID and EOC marker, respectively. Entry 2 indicates that cluster 2 is a data cluster; its chain is 1 cluster long. Entry 3 indicates that cluster 3 is a data cluster; the next cluster in the chain is cluster 5 followed by the final cluster in the chain, cluster 6. Similarly, clusters 7 and 5 form a chain. Cluster 8 is free and unused.\nDirectories and Entries A chain of clusters makes up the data for a file or directory. Directories are special files that map file names and associated metadata to the starting cluster for a file\u0026rsquo;s date. Specifically, a directory is an array of directory entries. Each entry indicates, among other things, the name of the entry, whether the entry is a file or directory, and its starting cluster.\nThe root directory is the only file or directory that is not linked to via a directory entry. The starting cluster for the root directory is instead recorded in the EBPB. From there, the location of all other files can be determined.\nFor historical reasons, every physical directory entry can be interpreted in two different ways. The attributes field of an entry is overloaded to indicate which way an entry should be interpreted. An entry is either:\nA regular directory entry. A long file name entry. Long file name (LFN) entries were added to FAT32 to allow for filenames greater than 11 characters in length. If an entry has a name greater than 11 characters in length, then its regular directory entry is preceded by as many LFN entries as needed to store the bytes for the entry\u0026rsquo;s name. LFN entries are not ordered physically. Instead, they contain a field that indicates their sequence. As such, you cannot rely on the physical order of LFN entries to determine how the individual components are joined together.\nWrap Up Before continuing, cross-reference your understanding with the FAT structures PDF. Then, answer the following questions:\nHow do you determine if the first sector is an MBR? (mbr-magic)\nThe first sector of a disk may not necessarily contain an MBR. How would you determine if the first sector contains a valid MBR?\nWhat is the maximum number of FAT32 clusters? (max-clusters)\nThe FAT32 design enjoins several file limitations. What is the maximum number of clusters that a FAT32 file system can contain, and what dictates this limitation? Would you expect this limitation to be the same or different in a file system named FAT16?\nWhat is the maximum size of one file? (max-file-size)\nIs there a limit to the size of a file? If so, what is the maximum size, in bytes, of a file, and what determines it?\nTake a close look at the structure of a directory entry.\nHow do you determine if an entry is an LFN? (lfn-identity)\nGiven the bytes for a directory entry, how, precisely, do you determine whether the entry is an LFN entry or a regular directory entry? Be specific about which bytes you read and what their values should be.\nHow would you lookup /a/b/c.txt? (manual-lookup)\nGiven an EBPB, describe the series of steps you would take to find the starting cluster for the file /a/b/c.txt.\nCode Structure Writing a file system of any kind is a serious undertaking, and a read-only FAT32 file system is no exception. The code that we\u0026rsquo;ve provided for you in the lib/fat32 project provides a basic structure for implementation, but many of the design decisions and the majority of the implementation are up to you.\nWe\u0026rsquo;ll describe this structure now. You should read the relevant code in the fat32/src directory as we describe the various components and how they fit together.\nFile System Traits The traits module, rooted at traits/mod.rs, provides 7 trait declarations and 1 struct declaration. Your file system implementation will largely be centered on implementing these seven traits.\nThe single struct, Dummy, is a type that provides a dummy implementation of five of the seven traits. The type is useful as a place-holder. You\u0026rsquo;ll see that we\u0026rsquo;ve used this type already in several places in the code. You may find this type useful while you work on the assignment as well.\nYou should read the code in the traits/ directory in the following order:\nRead the BlockDevice trait documentation in traits/block_device.rs. The file system will be written generic to the physical or virtual backing storage. In other words, the file system will work on any device as long as the device implements the BlockDevice trait. When we test your file system, the BlockDevice will generally be backed by a file on your local file system. When your run the file system on the Raspberry Pi, the BlockDevice will be backed by a physical SD card and EMMC controller.\nRead the File, Dir, and Entry traits in traits/fs.rs. These traits define what it (minimally) means to be a file, directory, or directory entry in the file system. You\u0026rsquo;ll notice that the associated types of the trait depend on each other. For example, the Entry trait requires its associated type File to implement the File trait.\nRead the FileSystem traits in traits/fs.rs. This trait defines what it means to be a file system and unifies the rest of the traits through its associated types. In particular, it requires a File that implements the File trait, a Dir that implements the Dir trait whose Entry associated type is the same as the associated type of file system\u0026rsquo;s Entry associated type, and finally an Entry associated type that implements Entry with the same File and Dir associated types as the file system. These constraints together ensure that there is only one concrete File, Dir, and Entry type.\nRead the Metadata and Timestamp traits in traits/metadata.rs. Every Entry must be associated with Metadata which allows access to details about a file or directory. The Timestamp trait defines the operations requires by a type that specifies a point in time.\nCached Partition CachedPartition struct in vfat/cache.rs wraps BlockDevice and Partition and translates logical sectors, as specified by the EBPB, to physical sectors, as specified by the disk. We have provided an implementation of a method that does exactly this: virtual_to_physical(). You should use this method when determining which physical sectors to read from the disk. CachedPartition also provides a caching layer, which reduces the expensive cost of direct access to a physical disk. The get() and get_mut() methods of it allow for a sector to be referenced from the cache directly.\nActual disk cache implementations in commodity operating systems manage the disk cache very smartly. They predict the disk access pattern and preload disk contents, and they write the cache back to the disk if it is not accessed recently. For simplicity, our implementation will not implement such features. It will hold the disk content in the memory indefinitely.\nUtilities The util.rs file contains two declarations and implementations of extension traits for slices (\u0026amp;[T]) and vectors (Vec\u0026lt;T\u0026gt;). These traits can be used to cast a vector or slice of one type into a vector or slice of another type as long as certain conditions hold on the two types. For instance, to cast from an \u0026amp;[u32] to an \u0026amp;[u8], you might write:\nuse util::SliceExt; let x: \u0026amp;[u32] = \u0026amp;[1, 2, 3, 4]; assert_eq!(x.len(), 4); let y: \u0026amp;[u8] = unsafe { x.cast() }; assert_eq!(y.len(), 16); MBR and EBPB The MasterBootRecord structure in mbr.rs is responsible for reading and parsing an MBR from a BlockDevice. Similarly, the BiosParameterBlock structure in vfat/ebpb.rs is responsible for reading and parsing the BPB and EBPB of a FAT32 partition.\nFilesystem The vfat/vfat.rs file contains the VFat structure, the file system itself. You\u0026rsquo;ll note that the structure contains a CachedPartition: your implementation must wrap the provided BlockDevice in a CachedPartition.\nWhat is VFAT?\nVFAT is another file system from Microsoft that is a precursor to FAT32. The name has unfortunately become synonymous with FAT32, and we continue this poor tradition here.\nThe vfat/vfat.rs file also provides VFatHandle trait, which defines a way to share mutable access to VFat instance in a thread-safe way. When implementing your file system, you\u0026rsquo;ll likely need to share mutable access to the file system itself among your file and directory structures. You\u0026rsquo;ll rely on this trait to do so. Use clone() method for replicating the handle and lock() method for entering the critical section where the code can access \u0026amp;mut VFat.\nVFat and a few other types in our file system such as File and Dir are generic over HANDLE type parameter that implements VFatHandle trait. This design allows the user of the library to inject lock implementation by implementing VFatHandle trait on their own type. Our kernel uses PiVFatHandle struct which internally uses its custom Mutex implementation, while the test code uses StdVFatHandle struct which is implemented with types in the standard library.\nVFat is generic over VFatHandle, but VFat doesn\u0026rsquo;t physically own VFatHandle. The relationship is reverse; implementors of VFatHandle will manage VFat as their field. To represent such relationship, zero-sized marker type PhantomData has been added to VFat.\nWe\u0026rsquo;ve started an implementation of the FileSystem trait for \u0026amp;'a HANDLE already. You\u0026rsquo;ll also note that the from() method of FileSystem returns a HANDLE. Your main task will be to complete the implementation of the from() method and of the FileSystem trait for \u0026amp;'a HANDLE. This will require you to implement structures that implement the remainder of the file system traits.\nWe\u0026rsquo;ve provided the following code in vfat/ to assist you with this:\nerror.rs Contains an Error enum indicating the possible FAT32 initialization errors.\nfile.rs Contains an incomplete File struct with an incomplete traits::File implementation.\ndir.rs Contains an incomplete Dir struct which you will implement trait::Dir for. Also contains incomplete definitions for raw, on-disk directory entry structures.\nentry.rs Contains an incomplete Entry struct which you will implement traits::Entry for.\nmetadata.rs Contains structures (Date, Time, Attributes) that map to raw, on-disk entry metadata as well as incomplete structures (Timestamp, Metadata) which you should implement the appropriate file system traits for.\nfat.rs Contains the FatEntry structure which wraps a value for a FAT entry and which can be used to easily read the status of the cluster corresponding to the FAT entry.\ncluster.rs Contains the Cluster structure which wraps a raw cluster number and can be used to read the logical cluster number.\nWhen you implement your file system, you should complete and use each of these structures and types. Don\u0026rsquo;t be afraid to add extra helper methods to any of these structure. Do not, however, change any of the trait definitions or existing method signatures that we have provided for you.\nRead through all of the code now, starting with vfat.rs, and ensure you understand how everything fits together.\nImplementation You\u0026rsquo;re now ready to implement a read-only FAT32 file system. You may approach the implementation in any order you see fit.\nWe have provided a somewhat rigorous set of tests to check your implementation. Our tests use files in ext/fat32-imgs. In this directory you will find several real MBR, EBPB, and FAT32 file system images as well as hash values for file system traversals as run against our reference implementation. You may find it useful to analyze and check your understanding again the raw binaries by using a hex editor such as Bless (Linux), Hex Fiend (macOS), or HxD (Windows).\nExtract Fat32 test images first!\nThe images we provided in ext/fat32-imgs are compressed. You need to un-archive them first before testing. You can use bin/extract-fat.sh to do that for you.\nYou can run the tests with cargo test. While debugging, you may wish to run the tests with cargo test -- --nocapture to prevent Cargo from capturing output to stdout or stderr. You may also find it useful to add new tests as you progress. To prevent future merge conflicts, you should add new tests in a file different from tests.rs.\nYour implementation should adhere to the following guidelines:\nUse meaningful types where you can. For instance, instead of using a u16 to represent a raw time field, use the Time struct.\nAvoid unsafe code as much as possible. Our implementation uses a total of four non-union lines of unsafe. Additionally, our implementation uses three lines of unsafe related to accessing unions. The number of unsafe code in your implementation should be comparable to this.\nAvoid duplication by using helpers methods as necessary. It\u0026rsquo;s often useful to abstract common behavior into helper methods. You should do so when it makes sense.\nEnsure your implementation is cluster size and sector size agnostic. Do not hard-code or assume any particular values for sector sizes or cluster sizes. Your implementation must function with any cluster and sector sizes that are integer multiples of 512 as recorded in the EBPB.\nDon\u0026rsquo;t double buffer unnecessarily. Ensure that you don\u0026rsquo;t read a sector into memory that is already held in the sector cache to conserve memory.\nOur recommended implementation approach is as follows:\nImplement MBR parsing in mbr.rs.\nYour implementation will likely require the use of an unsafe method, but no more than one line. Possible candidates are slice::from_raw_parts_mut() or mem::transmute() . mem::transmute() is an incredibly powerful method. You should avoid it if you can. Otherwise, you should understand its implications thoroughly before using it.\nWhen you implement Debug, use the debug_struct() method on Formatter. You can use the Debug implementation we have provided for CachedPartition as a reference.\nPacked struct in Rust\nRust is very strict about the address alignment. All Rust references should respect the alignment of the underlying type. Because of this requirement, borrowing a field of a packed struct is sometimes illegal. You can workaround this limitation by copying the value to a temporary variable and borrowing the local variable with a syntax \u0026amp;{ struct.field }.\nImplement EBPB parsing in vfat/ebpb.rs.\nAs with the MBR, your implementation will likely require the use of an unsafe method, but no more than one line.\nTest your MBR and EBPB implementation.\nMock-up MBRs and EBPBs and ensure that you parse the values successfully. Note that we have provided an implementation of BlockDevice for Cursor\u0026lt;\u0026amp;mut [u8]\u0026gt;. Remember that you can pretty-print a structure using:\nprintln!(\u0026#34;{:#?}\u0026#34;, x); Implement CachedPartition in vfat/cache.rs.\nImplement VFat::from() in vfat/vfat.rs.\nUse your MasterBootRecord, BiosParameterBlock, and CachedPartition implementations to implement VFat::from(). Test your implementation as you did your MBR and EBPB implementations.\nImplement FatEntry in vfat/fat.rs.\nImplement VFat::fat_entry, VFat::read_cluster(), and VFat::read_chain().\nThese helpers methods abstract reading from a Cluster or a chain starting from a Cluster into a buffer. You\u0026rsquo;ll likely need other helper methods, like one to calculate the disk sector from a cluster number, to implement these methods. You may wish to add helper methods to the Cluster type. You should use the VFat::fat_entry() method when implementing read_cluster() and read_chain().\nComplete the vfat/metadata.rs file.\nThe Date, Time, and Attributes types should map directly to fields in the on-disk directory entry. Refer to the FAT structures PDF when implementing them. The Timestamp and Metadata types do not have an analogous on-disk structure, but they serve as nicer abstractions over the raw, on-disk structures and will be useful when implementing the Entry, File, and Dir traits.\nImplement Dir in vfat/dir.rs and Entry in vfat/entry.rs.\nStart by adding fields that store the directory\u0026rsquo;s first Cluster and a file system handle to Dir. Then implement the trait::Dir trait for Dir. You may wish to provide dummy trait implementations for the File type in vfat/file.rs while implementing Dir. You\u0026rsquo;ll want to create a secondary struct that implements Iterator\u0026lt;Item = Entry\u0026gt; and return this struct from your entries() method. You will likely need to use at-most one line of unsafe when implementing entries(); you may find the VecExt and SliceExt trait implementations we have provided particularly useful here. Note that you will frequently need to refer to the FAT structures PDF while implementing Dir.\nParsing an Entry\nBecause the on-disk entry may be either an LFN entry or a regular entry, you must use a union to represent an on-disk entry. We have provided such a union for you: VFatDirEntry. You can read about unions in Rust in the Rust reference and about unions in general in the union type Wikipedia entry .\nYou should first interpret a directory entry as an unknown entry, use that structure to determine whether there is an entry, and if so, the true kind of entry, and finally interpret the entry as that structure. Working with union s will require using unsafe. Do so sparingly. Our implementation uses one line of unsafe three times, one to access each variant.\nWhen parsing a directory entry\u0026rsquo;s name, you must manually add a . to the non-LFN based directory entries to demarcate the file\u0026rsquo;s extension. You should only add a . if the file\u0026rsquo;s extension is non-empty.\nFinally, you\u0026rsquo;ll need to decode UTF-16 characters when parsing LFN entries. Use the decode_utf16() function to do so. You will find it useful to store UTF-16 characters in one or more Vec\u0026lt;u16\u0026gt; while parsing a long filename.\nDir::find()\nYou should implement Dir::find() after you implement the traits::Dir trait for Dir. Note that Dir::find() must be case-insensitive. Your implementation should be relatively short. You can use the eq_ignore_ascii_case() method to perform case-insensitive comparisons.\nImplement File in vfat/file.rs. Start by adding a fields that store the file\u0026rsquo;s first Cluster and a file system handle to File. Then implement the trait::File trait and any required supertraits. Modify the iterator you return from entries() as necessary.\nImplement VFat::open() in vfat/vfat.rs. Finally, implement the VFat::open() method. Use the components() method to iterate over a Path\u0026rsquo;s components. Note that the Path implementation we have provided for you in the shim library does not contain any of the methods that require a file system. These include read_dir(), is_file(), is_dir(), and others.\nUse your Dir::find() method in your implementation. You may find it useful to add a helper method to Dir.\nOnce your implementation passes all of the unit tests and works as you expect, you may once again revel; you have implemented a real file system! After sufficient reveling, proceed to the next phase.\nDid you find any undefined behavior in the skeleton code? (undefined-behavior)\nThis is an optional extra credit question. While doing the assignment, did you notice any undefined behavior or unsound API in our skeleton code except those justified with comments? What type of Rust requirements do they violate? Why they seem to behave well in practice? How can we fix them?\nPhase 3: Saddle Up In this phase, you will interface with an existing SD card controller driver for the Raspberry Pi 3 using Rust\u0026rsquo;s foreign function interface , or FFI. You can read more about Rust\u0026rsquo;s FFI in TRPL . You will also create a global handle the file system for your operating system to use. You will be working primarily in kernel/src/fs.\nSubphase A: SD Driver FFI Rust\u0026rsquo;s foreign function interface allows Rust code to interact with software written in other programming languages and vice-versa. Foreign items are declared in an extern block:\nextern { static outside_global: u32; fn outside_function(param: i16) -\u0026gt; i32; } This declares an external outside_function as well as an outside_global. The function and global be used as follows:\nunsafe { let y = outside_function(10); let global = outside_global; } Note the required use of unsafe. Rust requires the use of unsafe because it cannot ensure that the signatures you have specified are correct. The Rust compiler will blindly emit function calls and variable reads as requested. In other words, as with every other use of unsafe, the compiler assumes that what you\u0026rsquo;ve done is correct. At link-time, symbols named outside_function and outside_global must exist for the program to successfully link.\nFor a Rust function to be called from a foreign program, the function\u0026rsquo;s location (its memory address) must be exported with a known symbol. Typically, Rust mangles function symbols for versioning and namespacing reasons in an unspecified manner. As such, by default, it is not possible to know the symbol that Rust will generate for a given function and thus not possible to call that function from an external program. To prevent Rust from mangling symbols, you can use the #[no_mangle] attribute:\n#[no_mangle] fn call_me_maybe(ptr: *mut u8) { .. } A C program would then be able to call this function as follows:\nvoid call_me_maybe(unsigned char *); call_me_maybe(...); Why can\u0026rsquo;t Rust ensure that using foreign code is safe? (foreign-safety)\nExplain why Rust cannot ensure that using foreign code is safe. In particular, explain why Rust can ensure that other Rust code is safe, even when it lives outside of the current crate, but it cannot do the same for non-Rust code.\nWhy does Rust mangle symbols? (mangling)\nC does not mangle symbols. C++ and Rust, on the other hand, do. What\u0026rsquo;s different about these languages that necessitates name mangling? Provide a concrete example of what would go wrong if Rust didn\u0026rsquo;t name mangle.\nSD Driver We have provided a precompiled SD card driver library in kern/.cargo/libsd.a. We\u0026rsquo;ve also modified the build process so that the library is linked into the kernel. We\u0026rsquo;ve provided the definitions for the items exported from the library in an extern block in kern/src/fs/sd.rs.\nThe library depends on a wait_micros function which it expects to find in your kernel. The function should sleep for the number of microseconds passed in. You will need to create and export this function for your kernel to successfully link. The C signature for the function is:\n/* * Sleep for `us` microseconds. */ void wait_micros(unsigned int us); Your task is to wrap the unsafe external API in a safe, Rusty API. Implement an Sd struct that initializes the SD card controller in its new() method. Then, implement the BlockDevice trait for Sd. You will need to use unsafe to interact with the foreign items. Test your implementation by manually reading the card\u0026rsquo;s MBR in kmain. Ensure that the bytes read match what you expect. When everything works as expected, proceed to the next subphase.\nOn 64-bit ARM, an unsigned int in C is a u32 in Rust.\nIs your implementation thread-safe? (foreign-sync)\nThe precompiled SD driver we\u0026rsquo;ve provided you uses a global variable (sd_err) to keep track of error states without any kind of synchronization. As such, it has no hope of being thread-safe. How does this affect the correctness of your bindings? Recall that you must uphold Rust\u0026rsquo;s data race guarantees in any unsafe code. Assuming your kernel called sd_init correctly, is your BlockDevice implementation for Sd thread-safe as required? Why or why not?\nSubphase B: File System In this subphase you will expose and initialize a global file system for use by your kernel. You will be working primarily in kern/src/fs.rs.\nLike the memory allocator, the file system is a global resource: we want it to always be available so that we can access the data on the disk at any point. To enable this, we\u0026rsquo;ve created a global static FILE_SYSTEM: FileSystem in main.rs; it will serve as the global handle to your file system. Like the allocator, the file system begins uninitialized.\nTying the Knot You\u0026rsquo;ve now implemented both a disk driver and a file system: it\u0026rsquo;s time to tie them together. Finish the implementation of the FileSystem struct in kernel/src/fs.rs by using your FAT32 file-system and your Rusty bindings to the foreign SD card driver. You should initialize your file-system using the Sd BlockDevice in the initialize() function. Then, implement the FileSystem trait for the structure, deferring all calls to the internal VFat. Finally, ensure that you initialize the file system in kmain, just after the allocator.\nTest your implementation by printing the files at the root (\u0026quot;/\u0026quot;) of your SD card in kmain. Once everything works as your expect, proceed to the next phase.\nPhase 4: Mo\u0026rsquo;sh In this phase, you will implement the cd, ls, pwd, and cat shell commands. You will be working primarily in kern/src/shell.rs.\n\u0026#39;Finished Product\u0026#39; Working Directory You\u0026rsquo;re likely familiar with the notion of a working directory already. The current working directory (or cwd) is the directory under which relative file accesses are rooted under. For example, if the cwd is /a, then accessing hello will result in accessing the file /a/hello. If the cwd is switched to /a/b/c, accessing hello will access /a/b/c/hello, and so on. The / character can be prepended to any path to make it absolute so that it is not relative to the current working directory. As such, /hello will always refer to the file named hello in the root directory regardless of the current working directory.\nIn a shell, the current working directory can be changed to dir with the cd \u0026lt;dir\u0026gt; command. For example, running cd /hello/there will change the cwd to /hello/there. Running cd you after this will result in the cwd being /hello/there/you.\nMost operating systems provide a system call that changes a process\u0026rsquo;s working directory. Because our operating system has neither processes nor system calls yet, you\u0026rsquo;ll be keeping track of the cwd directly in the shell.\nCommands You will implement four commands that expose expose the file system through your operating system\u0026rsquo;s primary interface: the shell. These are cd, ls, pwd, and cat. For the purposes of this assignment, they are specified as follows:\npwd - print the working directory Prints the full path of the current working directory.\ncd \u0026lt;directory\u0026gt; - change (working) directory Changes the current working directory to directory. The directory argument is required.\nls [-a] [directory] - list the files in a directory Lists the entries of a directory. Both -a and directory are optional arguments. If -a is passed in, hidden files are displayed. Otherwise, hidden files are not displayed. If directory is not passed in, the entries in the current working directory are displayed. Otherwise, the entries in directory are displayed. The arguments may be used together, but -a must be provided before directory.\nInvalid arguments results in an error. It is also an error if ``directory`` does not correspond to a valid, existing directory. cat \u0026lt;path..\u0026gt; - concatenate files Prints the contents of the files at the provided paths, one after the other. At least one path argument is required.\nIt is an error if a ``path`` does not point to a valid, existing file. It is an error if an otherwise valid file contains invalid UTF-8. All non-absolute paths must be must be treated as relative to the current working directory if they are not absolute. For an example of these commands in action, see the GIF above. When you implement these commands yourself, you are free to display directory entries and errors in any way that you\u0026rsquo;d like as long as all of the information is present.\nImplementation Extend your shell in kern/src/shell.rs with these four commands. Use a mutable PathBuf to keep track of the current working directory; this PathBuf should be modified by the cd command. You will find it useful to create functions with a common signature for each of your commands. For an extra level of type-safety, you can abstract the concept of an executable command into a trait that is implemented for each of your commands.\nOnce you have implemented, tested, and verified your four commands against the specifications above, you\u0026rsquo;re ready to submit your assignment. Congratulations!\nEnsure you\u0026rsquo;re using your bin allocator!\nYour file system is likely very memory intensive. To avoid running out of memory, ensure you\u0026rsquo;re using your bin allocator.\nUse the existing methods of PathBuf and Path to your advantage.\nYou\u0026rsquo;ll need to handle .. and . specially in cd.\nSubmission Once you\u0026rsquo;ve completed the tasks above, you\u0026rsquo;re done and ready to submit! Congratulations!\nYou can call cargo test in lib/fat32 directory to run the unit tests for your FAT32 implementation. Note that there are no unit tests for some tasks in os. You\u0026rsquo;re responsible for ensuring that they work as expected.\nOnce you\u0026rsquo;ve completed the tasks above, you\u0026rsquo;re done and ready to submit! Ensure you\u0026rsquo;ve committed your changes. Any uncommitted changes will not be visible to us, thus unconsidered for grading.\nWhen you\u0026rsquo;re ready, push a commit to your GitHub repository.\ngit push team ",
        "url": "\/post\/lab5\/"
    },

    "\/tags\/": {
        "title": "Tags",
        "tags": [],
        "content": "",
        "url": "\/tags\/"
    },

    "\/post\/lab4\/": {
        "title": "Lab 4: Shell and Bootloader Phase 2",
        "tags": ["Lab",],
        "content": "Getting Started Fetch the update for lab 4 from our git repository to your development machine.\ngit fetch skeleton git merge skeleton/lab4 You may need to resolve conflicts before continuing. For example, if you see a message that looks like:\nAuto-merging kern/src/main.rs CONFLICT (content): Merge conflict in kern/src/main.rs Automatic merge failed; fix conflicts and then commit the result. You will need to manually modify the relevent files to resolve the conflict. Ensure that you keep all of your changes from lab 3.\nOnce all conflicts are resolved, add the resolved files with git add and commit.\nFor more information on resolving merge conflicts, see this tutorial on githowto.com .\nPhase 2: Not a Seashell Due to Raspberry Pi devices being unavailable at the moment, we have to skip the implementation parts of Subphase B and C.\nThe template code already has the implementation ready. Please read through them to understand the code though.\nIn this phase, you will be implementing drivers for the built-in timer, GPIO, and UART devices. You\u0026rsquo;ll use then these drivers to implement a simple shell. In the next phase, you\u0026rsquo;ll use the same drivers to implement a bootloader.\nWhat\u0026rsquo;s a driver?\nThe term driver, or device driver, describes software that directly interacts with and controls a hardware device. Drivers expose a higher-level interface to the hardware they control. Operating systems may interact with device drivers to expose an even higher-level interface. For instance, the Linux kernel exposes ALSA (Advanced Linux Sound Architecture), an audio API, which interacts with device drivers that in-turn interact directly with sound cards.\nSubphase A: Getting Started Project Structure Let\u0026rsquo;s recall the repository structure we saw previously.\n. ├── ... ├── boot : bootloader * ├── kern : the main os kernel * └── lib : required libraries ├── pi * ├── shim ├── stack-vec * ├── ttywrite * ├── volatile * └── xmodem * All the libraries used by boot and kernel are located under the lib directory.\nshim library selectively depends on either std or no_std library. With #[cfg(feature = \u0026quot;no_std\u0026quot;)] specified, shim makes use of core_io and the custom no_std module which has minimum library we need such as ffi, path and sync. Otherwise, mostly in the test code, shim just uses std library.\npi subdirectory contains all of your driver code. The pi library makes use of the volatile library. It also depends on the shim library.\nboot and kernel make use of the pi library to communicate with hardware. They also depend on shim. In addition to that, boot also depends on the xmodem library, and kernel depends on the stack-vec library. The volatile library has no dependencies. The diagram below illustrates these relationships:\nKernel The kern directory contains the code for the operating system kernel: the core of your operating system. Calling make inside this directory builds the kernel. The build output is stored in the build/ directory. To run the kernel, use make qemu command. Please refer the Tools page to find details about our Makefile.\nAt present, the kernel does absolutely nothing. By the end of this phase, the kernel will start up a shell which you can communicate with.\nAs we saw above, the kernel crate depends on the pi library. As a result, you can use all of the types and items from the pi library in the kernel.\nDocumentation While writing your device drivers, you\u0026rsquo;ll want to keep the BCM2837 ARM Peripherals Manual open.\nSubphase B: System Timer Due to Raspberry Pi devices being unavailable at the moment, we have to skip the implementation parts of this Subphase.\nThe template code already has the implementation ready. Please read through the following parts and understand the code though.\nIn this subphase, you will write a device driver for the ARM system timer. You will primarily be working in lib/pi/src/timer.rs and kern/src/main.rs. The ARM system timer is documented on page 172 (section 12) of the BCM2837 ARM Peripherals Manual .\nStart by looking at the existing code in lib/pi/src/timer.rs. In particular, note the relationship between the following sections:\nconst TIMER_REG_BASE: usize = IO_BASE + 0x3000; #[repr(C)] struct Registers { CS: Volatile\u0026lt;u32\u0026gt;, CLO: ReadVolatile\u0026lt;u32\u0026gt;, CHI: ReadVolatile\u0026lt;u32\u0026gt;, COMPARE: [Volatile\u0026lt;u32\u0026gt;; 4] } pub struct Timer { registers: \u0026amp;\u0026#39;static mut Registers } impl Timer { pub fn new() -\u0026gt; Timer { Timer { registers: unsafe { \u0026amp;mut *(TIMER_REG_BASE as *mut Registers) }, } } } The one line of unsafe in this program is very important: it casts the TIMER_REG_BASE address to a *mut Registers and then casts that to an \u0026amp;'static mut Registers. We are telling Rust that we have a static reference to a Registers structure at address TIMER_REG_BASE.\nWhat is at the TIMER_REG_BASE address? On page 172 of the BCM2837 ARM Peripherals Manual , you\u0026rsquo;ll find that 0x3000 is the peripheral offset for the ARM system timer. Thus, TIMER_REG_BASE is the address at which the ARM system timer registers start! After this one line of unsafe, we can use the registers field to access the timer\u0026rsquo;s registers safely. We can read the CLO register with self.registers.CLO.read() and write the CS register with self.registers.CS.write(), then combine them together to represent the number of elapsed microseconds.\nWhy can\u0026rsquo;t you write to CLO or CHI? (restricted-reads)\nThe BCM2837 documentation states that the CLO and CHI registers are read-only. Our code enforces this property. How? What prevents us from writing to CLO or CHI?\nWhat exactly is unsafe?\nIn short, unsafe is a marker for the Rust compiler that you\u0026rsquo;re taking control of memory safety: the compiler won\u0026rsquo;t protect you from memory issues. As a result, in unsafe sections, Rust lets you do anything you can do in C. In particular, you can cast between types with more freedom, dereference raw pointers, and fabricate lifetimes.\nBut note that unsafe is very unsafe. You must ensure that everything you do in an unsafe section is, in fact safe. This is more difficult than it sounds, especially when Rust\u0026rsquo;s idea of safe is much stricter than in other languages. As such, you should try not to use unsafe at all. For operating systems, unfortunately, we must use unsafe so that we can directly speak to hardware, but we\u0026rsquo;ll typically limit our use to one line per driver.\nIf you want to learn more about unsafe, read Chapter 1 of the Nomicon .\nImplement the Driver Implement the Timer::read(), current_time(), and spin_sleep() in lib/pi/src/timer.rs. The signatures on these items indicate their expected functionality. You\u0026rsquo;ll need to read the timer\u0026rsquo;s documentation in the BCM manual to implement Timer::read(). In particular, you should understand which registers to read to obtain the timer\u0026rsquo;s current u64 value. You can build the pi library with cargo build. You can also use cargo check to type-check the library without actually compiling it.\nYou\u0026rsquo;ll find the core::time::Duration page useful.\nTesting Your Driver Let\u0026rsquo;s test your driver by ensuring that spin_sleep() is accurate. We\u0026rsquo;ll write the code to do this in kern/src/main.rs.\nCopy your LED blinky code from phase 4 of lab 1 into main.rs. Instead of the for loop based sleep function, use your newly written spin_sleep() function with Duration to pause between blinks. Compile the kernel, load it onto the MicroSD card as kernel8.img, and then run it on the Raspberry Pi. Ensure that the LED blinks at the frequency that you intended it to. Try other pause times and ensure that they all work as expected. Until you write the bootloader in phase 3, you\u0026rsquo;ll need to keep swapping the MicroSD card between the Pi and your computer to try out different binaries.\nIf your timer driver is working as expected, proceed to the next subphase.\nSubphase C: GPIO Due to Raspberry Pi devices being unavailable at the moment, we have to skip the implementation parts of this Subphase.\nThe template code already has the implementation ready. Please read through the following parts and understand the code though.\nIn this subphase, you will write a generic, pin-independent device driver for GPIO. You will primarily be working in lib/pi/src/gpio.rs and kern/src/main.rs. The GPIO subsystem is documented on page 89 (section 6) of the BCM2837 ARM Peripherals Manual .\nState Machines All hardware devices are state machines : they begin at a predetermined state and transition to different states based on explicit or implicit inputs. The device exposes different functionality depending on which state it is in. In other words, only some transitions are valid in some states. Importantly, this implies that some transitions are invalid when the device is in a given state.\nMost programming languages make it impossible to faithfully encode the semantics of a state machine in hardware, but not Rust! Rust lets us perfectly encode state machine semantics, and we\u0026rsquo;ll take advantage of this to implement a safer-than-safe device driver for the GPIO subsystem. Our driver will ensure that a GPIO pin is never misused, and it will do so at compile-time.\nBelow is the state diagram for a subset of the GPIO state machine for a single pin:\nGPIO State Diagram Our goal is to encode this state machine in Rust. Let\u0026rsquo;s start by interpreting the diagram:\nThe GPIO starts in the START state.\nFrom the START state it can transition to one of three states:\nALT - no transitions are possible from this state OUTPUT - two \u0026ldquo;self\u0026rdquo; transitions are possible: SET and CLEAR INPUT - one \u0026ldquo;self\u0026rdquo; transition is possible: LEVEL Which transitions did you follow in your lab 1 blinky? (blinky-states)\nWhen you implementing the blinky code in phase 4 of lab 1, you implicitly implemented a subset of this state machine. Which transitions did your code implement?\nWe\u0026rsquo;ll use Rust\u0026rsquo;s type system to ensure that a pin can only be SET and CLEARed if it has been transitioned to the OUTPUT state and the LEVEL read if it is in the INPUT state. Take a look at the declaration for the GPIO structure in lib/pi/src/gpio.rs:\npub struct Gpio\u0026lt;State\u0026gt; { pin: u8, registers: \u0026amp;\u0026#39;static mut Registers, _state: PhantomData\u0026lt;State\u0026gt; } The structure has one generic argument, State. Except for PhantomData, nothing actually uses this argument. This is what PhantomData is there for: to convince Rust that the structure somehow uses the generic even though it otherwise wouldn\u0026rsquo;t. We\u0026rsquo;re going to use the State generic to encode which state the Gpio device is in. Unlike other generics, we must control this parameter and ensure that a client can never fabricate it.\nThe state! macro generates types that represent the states a Gpio can be in:\nstates! { Uninitialized, Input, Output, Alt } // Each parameter expands to an `enum` that looks like: enum Input { } This is also weird; why would we create an enum with no variants? enum\u0026rsquo;s with no variants have a nice property: they can never be instantiated. In this way, these types act purely as markers. No one can ever pass us a value of type Input because such a value can never be constructed. They exist purely at the type-level.\nWe can then implement methods corresponding to valid transitions given that a Gpio is in a certain state:\nimpl Gpio\u0026lt;Output\u0026gt; { /// Sets (turns on) the pin. pub fn set(\u0026amp;mut self) { ... } /// Clears (turns off) the pin. pub fn clear(\u0026amp;mut self) { ... } } impl Gpio\u0026lt;Input\u0026gt; { /// Reads the pin\u0026#39;s value. pub fn level(\u0026amp;mut self) -\u0026gt; bool { ... } } This ensures that a Gpio can only be set and cleared when it is a Gpio\u0026lt;Output\u0026gt; and its level read when it is a Gpio\u0026lt;Input\u0026gt;. Perfect! But how do we actually transition between states? Hello, Gpio::transition()!\nimpl\u0026lt;T\u0026gt; Gpio\u0026lt;T\u0026gt; { fn transition\u0026lt;S\u0026gt;(self) -\u0026gt; Gpio\u0026lt;S\u0026gt; { Gpio { pin: self.pin, registers: self.registers, _state: PhantomData } } } This method lets us transition a Gpio from any state to any other state. Given a Gpio in state T, this method returns a Gpio in state S. Note that it works for all S and T. We must be very careful when calling this method. When called, we are encoding the specification of a transition in the state diagram. If we get the specification or encoding wrong, our driver is wrong.\nTo use the transition() method, we need to tell Rust which type we want as an output S in Gpio\u0026lt;S\u0026gt;. We do this by giving Rust enough information so that it can infer the S type. For instance, consider the implementation of the into_output method:\npub fn into_output(self) -\u0026gt; Gpio\u0026lt;Output\u0026gt; { self.into_alt(Function::Output).transition() } This method requires its return type to be Gpio\u0026lt;Output\u0026gt;. When the Rust type system inspects the call to transition(), it will search for a Gpio::transition() method that returns a Gpio\u0026lt;Output\u0026gt; to satisfy the requirement. Since our transition method returns Gpio\u0026lt;S\u0026gt; for any S, Rust will replace S with Output and use that method. The result is that we\u0026rsquo;ve transformed our Gpio\u0026lt;Alt\u0026gt; (from the into_alt() call) into a Gpio\u0026lt;Output\u0026gt;.\nWhat would go wrong if a client fabricates states? (fake-states)\nConsider what would happen if we let the user choose the initial state for a Gpio structure. What could go wrong?\nWhy is this only possible with Rust?\nNotice that the into_ transition methods take a Gpio by move. This means that once a Gpio is transitioned into a another state, it can never be accessed in the previous state. Rust\u0026rsquo;s move semantics make this possible. As long as a type doesn\u0026rsquo;t implement Clone, Copy, or some other means of duplication, there is no coming back from a transition. No other language, not even C++, affords us this guarantee at compile-time.\nImplement the Driver Implement the unimplemented!() methods in lib/pi/src/gpio.rs. The signatures on these items indicate their expected functionality. You\u0026rsquo;ll need to read the GPIO documentation (page 89, section 6 of the BCM2837 ARM Peripherals Manual ) to implement your driver. Remember that you can use cargo check to type-check the library without actually compiling it.\nTesting Your Driver We\u0026rsquo;ll again write code in kern/src/main.rs to ensure that our driver works as expected.\nInstead of reading/writing to raw memory addresses, use your new GPIO driver to set and clear GPIO pin 16. Your code should get a lot cleaner. Compile the kernel, load it onto the MicroSD card as kernel8.img, run it on the Raspberry Pi, and ensure your LED blinks as before.\nNow, connect more LEDs to your Raspberry Pi. Use GPIO pins 5, 6, 13, 19, and 26. Refer to the pin numbering diagram from assignment 0 to determine their physical location. Have your kernel blink all of the LEDs in a pattern of your choice.\nWhich pattern did you choose? (led-pattern)\nWhat pattern did you have your LEDs blink in? If you haven\u0026rsquo;t yet decided, one fun idea is to have them imitate a \u0026ldquo;loading spinner\u0026rdquo; by arranging the LEDs in a circle and turning them on/off in a sequential, circular pattern. Once your GPIO driver is working as expected, proceed to the next subphase.\nSubphase D: UART In this subphase, you will write a device driver for the mini UART device on the Raspberry Pi. You will primarily be working in lib/pi/src/uart.rs and kern/src/main.rs. The mini UART is documented on page 8 and page 10 (sections 2.1 and 2.2) of the BCM2837 ARM Peripherals Manual .\nUART: Universal Asynchronous RX/TX A UART , or universal asynchronous receiver-transmitter, is a device and serial protocol for communicating over two wires. These are the two wires (rx/tx) that you used in phase 1 of lab 0 to connect the UART device on the CP2102 USB module to the UART device on the Pi. You can send any kind of data over UART: text, binaries, images, anything! As an example, in the next subphase, you\u0026rsquo;ll implement a shell by reading from the UART device on the Pi and writing to the UART device on the CP2102 USB module. In phase 3, you\u0026rsquo;ll read from the UART on the Pi to download a binary being sent via the UART on the CP2102 USB module.\nThe UART protocol has several configuration parameters, and both the receiver and transmitter need to be configured identically to communicate. These parameters are:\nData Size: length of a single data frame (8 or 9 bits) Parity Bit: whether to send a parity (checksum) bit after the data Stop Bits: how many bits to use to signal the end of the data (1 or 2) Baud Rate: transmission rate in bits/second The mini UART on the Pi does not support parity bits and only supports 1 stop bit. As such, only the baud rate and data frame length need to be configured. To learn more about UART, see the Basics of UART Communication article.\nImplement the Driver At this point, you have all of the tools to write a device driver without additional background information (congratulations!).\nImplement the mini UART device driver in lib/pi/src/uart.rs. You\u0026rsquo;ll need to complete the definition of the Registers structure. Ensure that you use the Volatile type with the minimal set of capabilities for each register: read-only registers should use ReadVolatile, write-only registers should use WriteVolatile, and reserved space should use Reserved. Then, initialize the device in new() by setting the baud rate to 115200 (a divider of 270) and data length to 8 bits. Finally, implement the remaining unimplemented!() methods and the fmt::Write, io::Read and io::Write traits for MiniUart.\nYou\u0026rsquo;ll need to write to the LCR, BAUD, and CNTL registers in new.\nUse your GPIO driver from the previous subphase.\nTesting Your Driver Test your driver by writing a simple \u0026ldquo;echo\u0026rdquo; program in kern/src/main.rs: sit in a hot loop writing out every byte you read in. In pseudocode, this looks like:\nloop { write_byte(read_byte()) } If you want to work in a single tty, just use make qemu to get qemu output to stdio directly.\nAlternatively, use make qemu_screen to run qemu over pty - a pseudo tty.\nThen use screen /dev/\u0026lt;your-path\u0026gt; 115200 in another terminal to communicate over UART.\n(Another terminal can be spawned using docker exec -it \u0026lt;container\u0026gt; bash).\nscreen sends every keypress over the TTY, so if your echo program works correctly, you\u0026rsquo;ll see every character you type.\nExit qemu using Ctrl-a , x. Similarly, exit screen using Ctrl-a, Ctrl-d.\nIt might help to send an extra character or two each time you receive a byte to convince yourself things are working as you expect:\nloop { write_byte(read_byte()) write_str(\u0026#34;\u0026lt;-\u0026#34;) } Once your driver works as expected, proceed to the next subphase.\nSubphase E: The Shell In this subphase, you\u0026rsquo;ll use your new UART driver to implement a simple shell that will be the interface to your operating system. You will be working in kern/src/console.rs, kern/src/shell.rs, and kernel/src/main.rs.\nThe Console To write our shell, we\u0026rsquo;ll need some notion of a global default input and output. Unix and friends typically refer to this is as stdin and stdout; we\u0026rsquo;ll be calling it Console. Console will allow us to implement the kprint! and kprintln! macros, our kernel-space versions of the familiar print! and println!, and give us a default source for reading user input. We\u0026rsquo;ll use Console and these macros to implement our shell.\nTake a peek at kernel/src/console.rs. The file contains an unfinished implementation of the Console struct. Console is a singleton wrapper around a MiniUart: only one instance of Console will ever exist in our kernel. That instance will be globally available, for use anywhere and by anything. This will allow us to read and write to the mini UART without explicitly passing around an instance of MiniUart or Console.\nGlobal Mutability The notion of a globally mutable structure is a scary thought, especially in the face of Rust. After all, Rust doesn\u0026rsquo;t allow more than one mutable reference to a value, so how can we possibly convince it to allow as many as we want? The trick, of course, relies on unsafe. The idea is as follows: we\u0026rsquo;ll tell Rust that we\u0026rsquo;re only going to read a value by using an immutable reference, but what we actually do is use unsafe to \u0026ldquo;cast\u0026rdquo; that immutable reference to a mutable reference. Because we can create as many immutable references as we want, Rust will be none the wiser, and we\u0026rsquo;ll have all of the mutable references we desire!\nSuch a function might look like this:\n// This function must never exist. fn make_mut\u0026lt;T\u0026gt;(value: \u0026amp;T) -\u0026gt; \u0026amp;mut T { unsafe { /* magic */ } } Your alarm bells should be ringing: what we\u0026rsquo;ve proposed so far is wildly unsafe. Recall that we still need to ensure that everything we do in unsafe upholds Rust\u0026rsquo;s rules. What we\u0026rsquo;ve proposed thus far clearly does not. As it stands, we\u0026rsquo;re violating the \u0026ldquo;at most one mutable reference at a time\u0026rdquo; rule. The rule states that at any point in the program, a value should have at most one mutable reference to it.\nThe key insight to maintaining this rule while meeting our requirements is as follows: instead of the compiler checking the rule for us with its borrow and ownership checker, we will ensure that the rule is upheld dynamically, at run-time. As a result, we\u0026rsquo;ll be able to share references to a structure as many times as we want (via an \u0026amp; reference) while also being able to safely retrieve a mutable reference when we need it (via our \u0026amp;T -\u0026gt; \u0026amp;mut T dynamic borrow checking function).\nThere are many concrete implementations of this idea. One such implementation ensures that only one mutable reference is returned at a time using a lock:\nfn lock\u0026lt;T\u0026gt;(value: \u0026amp;T) -\u0026gt; Locked\u0026lt;\u0026amp;mut T\u0026gt; { unsafe { lock(value); cast value to Locked\u0026lt;\u0026amp;mut T\u0026gt; } } impl Drop for Locked\u0026lt;\u0026amp;mut T\u0026gt; { fn drop(\u0026amp;mut self) { unlock(self.value) } } This is known as Mutex in the standard library. Another way is to abort the program if more than one mutable reference is about to be created:\nfn get_mut\u0026lt;T\u0026gt;(value: \u0026amp;T) -\u0026gt; Mut\u0026lt;\u0026amp;mut T\u0026gt; { unsafe { if ref_count(value) != 0 { panic!() } ref_count(value) += 1; cast value to Mut\u0026lt;\u0026amp;mut T\u0026gt; } } impl Drop for Mut\u0026lt;\u0026amp;mut T\u0026gt; { fn drop(\u0026amp;mut self) { ref_count(value) -= 1; } } This is RefCell::borrow_mut() . And yet another is to only return a mutable reference if it is known to be exclusive:\nfn get_mut\u0026lt;T\u0026gt;(value: \u0026amp;T) -\u0026gt; Option\u0026lt;Mut\u0026lt;\u0026amp;mut T\u0026gt;\u0026gt; { unsafe { if ref_count(value) != 0 { None } else { ref_count(value) += 1; Some(cast value to Mut\u0026lt;\u0026amp;mut T\u0026gt;) } } } impl Drop for Mut\u0026lt;\u0026amp;mut T\u0026gt; { fn drop(\u0026amp;mut self) { ref_count(value) -= 1; } } This is RefCell::try_borrow_mut() . All of these examples implement some form of \u0026ldquo;interior mutability\u0026rdquo;: they allow a value to be mutated through an immutable reference. For our Console, we\u0026rsquo;ll be using Mutex to accomplish the same goal. Since the std::Mutex implementation requires operating system support, we\u0026rsquo;ve implemented our own Mutex in kern/src/mutex.rs. Our implementation is correct for now, but we\u0026rsquo;ll need to fix it when we introduce caching or concurrency to continue to uphold Rust\u0026rsquo;s rules. You don\u0026rsquo;t need to understand the Mutex implementation for now, but you should understand how to use one.\nThe global singleton is declared as CONSOLE in kern/src/console.rs. The global variable is used by the kprint! and kprintln! macros defined below below. Once you\u0026rsquo;ve implemented Console, you\u0026rsquo;ll be able to use kprint! and kprintln! to print to the console. You\u0026rsquo;ll also be able to use CONSOLE to globally access the console.\nRust also requires static globals to be Sync.\nIn order to store a value of type T in a static global, T must implement Sync. This is because Rust also guarantees data race safety at compile-time. Because global values can be accessed from any thread, Rust must ensure that those accesses are thread-safe. The Send and Sync traits, along with Rust\u0026rsquo;s ownership system, ensure data race freedom.\nWhy should we never return an \u0026amp;mut T directly? (drop-container)\nYou\u0026rsquo;ll notice that every example we\u0026rsquo;ve provided wraps the mutable reference in a container and then implements Drop for that container. What would go wrong if we returned an \u0026amp;mut T directly instead?\nWhere does the write_fmt call go? (write-fmt)\nThe _print helper function calls write_fmt on an instance of MutexGuard\u0026lt;Console\u0026gt;, the return value from Mutex\u0026lt;Console\u0026gt;::lock(). Which type will have its write_fmt method called, and where does the method implementation come from?\nImplement and Test Console implement all of the unimplemented!() methods in kern/src/console.rs. once you\u0026rsquo;ve implemented everything, use the kprint! and kprintln! macros in kern/src/main.rs to write to the console when you receive a character. you can use these macros exactly like print! and println!. use screen /dev/\u0026lt;your-path\u0026gt; 115200 to communicate with your pi and ensure that your kernel works as expected.\nIf this were C\u0026hellip;\nThe fact that we get a println! implementation for free with zero effort is just another advantage to using Rust. If this were C, we\u0026rsquo;d need to implement printf ourselves. In Rust, the compiler provides a generic, abstracted, and safe OS-independent implementation. Whew!\nYour Console implementations should be very short: about a line each.\nImplement the Shell Finished Product You\u0026rsquo;re now ready to implement the shell in kern/src/shell.rs. We\u0026rsquo;ve provided a Command structure for your use. The Command::parse() method provides a simple command-line argument parser, returning a Command struct. The parse method splits the passed in string on spaces and stores all of the non-empty arguments in the args field as a StackVec using the passed in buf as storage. You must implement Command::path() yourself.\nUse all of your available libraries (Command, StackVec, Console via CONSOLE, kprint!, kprintln!, and anything else!) to implement a shell in the shell function. Your shell should print the prefix string on each line it waits for input. In the GIF above, for instance, \u0026quot;\u0026gt; \u0026quot; is being used as the prefix. Your shell should then read a line of input from the user, parse the line into a command, and attempt to execute it. It should do this ad-infinitum. Since our operating system is only just beginning, we can\u0026rsquo;t run any interesting commands just yet. We can, however, build known commands like echo into the shell.\nTo complete your implementation, your shell should\u0026hellip;\nimplement the echo built-in: echo $a $b $c should print $a $b $c accept both \\r and \\n as \u0026ldquo;enter\u0026rdquo;, marking the end of a line accept both backspace and delete (ASCII 8 and 127) to erase a single character ring the bell (ASCII 7) if an unrecognized non-visible character is sent to it print unknown command: $command for an unknown command $command disallow backspacing through the prefix disallow typing more characters than allowed accept commands at most 512 bytes in length accept at most 64 arguments per command start a new line, without error, with the prefix if the user enters an empty command print error: too many arguments if the user passes in too many arguments Test your implementation by calling your new shell() function in kern/src/main.rs. Minus the \u0026ldquo;SOS\u0026rdquo; banner, you should be able to replicate the GIF above. You should also be able to test all of the requirements we\u0026rsquo;ve set. Once your shell works as expected, revel in your accomplishments. Then, proceed to the next phase.\nA byte literal, b'a' is the u8 ASCII value for a character 'a'.\nUse \\u{b} in a string literal to print any character with ASCII byte value b.\nYou must print both \\r and \\n to begin a new line at the line start.\nTo erase a character, backspace, print a space, then backspace again.\nUse StackVec to buffer the user\u0026rsquo;s input.\nYou\u0026rsquo;ll find the core::str::from_utf8() function useful.\nHow does your shell tie the many pieces together? (shell-lookback)\nYour shell makes use of much of the code you\u0026rsquo;ve written. Briefly explain: which pieces does it makes use of and in what way?\n",
        "url": "\/post\/lab4\/"
    },

    "\/post\/lab3\/": {
        "title": "Lab 3: Shell and Bootloader Phase 1",
        "tags": ["Lab",],
        "content": "Introduction In this assignment, you will write useful utilities, libraries, and a simple shell for Raspberry Pi. This is just a single phase of this exercise and we\u0026rsquo;ll be going over the rest of them in the incoming weeks.\nPlease insure you\u0026rsquo;ve setup the environment as described on Tools page .\nThis is the directory structure of our repository. The directories you will be working on this lab section are marked with *.\n. ├── bin : common binaries/utilities ├── ext : external files (e.g., resources for testing) ├── boot : bootloader * ├── kern : the main os kernel * └── lib : required libraries ├── pi * ├── shim ├── stack-vec * ├── ttywrite * ├── volatile * └── xmodem * We recommend the following directory structure for your assignments. Confirm that your directories are properly laid out by running make inside the kern directory now. If all is well, the command will return successfully. If everything is good, feel free to explore the contents of the repository.\nPhase 1: Oxidation In this phase, you will write two libraries, one command-line utility, and review one library. You will be working in the stack-vec, volatile, ttywrite, and xmodem skeleton subdirectories located in lib directory.\nAll projects are being managed with Cargo. You will find the following cargo commands useful:\ncargo build - build an application or library cargo test - test an application or library cargo run - run an application cargo run -- $flags - run an application and pass arbitrary flags to it For more information on using Cargo and how Cargo works, see the Cargo Book .\nSubphase A: StackVec One important facility that operating systems provide is memory allocation. When a C, Rust, Java, Python, or just about any application calls malloc() and malloc() has run out of memory from the operating system, a system call is eventually made to request additional memory. The operating system determines if there is memory available, and if so, fulfills the request for memory.\nMemory allocation is a complicated story.\nIn practice, modern operating systems like Linux have a complicated relationship with memory allocation. For instance, as an optimization, most requests for memory allocation are only \u0026ldquo;virtually\u0026rdquo; handled: no physical memory is actually allocated until the application tries to use the newly allocated memory. Nonetheless, most operating systems aim to provide the illusion that they are allocating memory in the simplistic manner we\u0026rsquo;ve described. Operating systems are master liars.\nHeap-allocated structures like Vec, String, and Box internally call malloc() to allocate memory as necessary. This means that these structures require operating system support to function. In particular, they require the operating system to support memory allocation. We haven\u0026rsquo;t yet started writing our operating system, so clearly there\u0026rsquo;s no memory allocation support for our tiny bare-metal programs to make use of. As such, we can\u0026rsquo;t use heap-allocated structures like Vec until our operating system is further along.\nThis is a real shame because Vec is a nice abstraction! It allows us to think about pushing and poping elements without having to keep track of memory ourselves. How we can get the benefits of the Vec abstraction without supporting memory allocation?\nOne common technique is to pre-allocate memory and then hand that memory to a structure to abstract away. Some ways to pre-allocate memory include using static declarations to set apart memory in the static section of a binary or through stack allocations from local variable declarations. In any case, the allocations is of a fixed, predetermined size.\nIn this subphase, you will implement the StackVec structure, a structure that exposes a Vec-like API when given pre-allocated memory. You will use the StackVec type later in phase 2 when implementing a shell for your Raspberry Pi. You will work in the lib/stack-vec skeleton subdirectory. The subdirectory contains the following files:\nCargo.toml - configuration file for Cargo src/lib.rs - where you will write your code src/tests.rs - tests that will run when cargo test is called The StackVec Interface A StackVec\u0026lt;T\u0026gt; is created by calling StackVec::new(), passing in a mutable slice to values of any type T. The StackVec\u0026lt;T\u0026gt; type implements many of the methods that Vec implements and is used in much the same way. Here\u0026rsquo;s an example of a StackVec\u0026lt;u8\u0026gt; being used:\nlet mut storage = [0u8; 10]; let mut vec = StackVec::new(\u0026amp;mut storage); for i in 0..10 { vec.push(i * i).expect(\u0026#34;can push 10 times\u0026#34;); } for (i, v) in vec.iter().enumerate() { assert_eq!(*v, (i * i) as u8); } let last_element = vec.pop().expect(\u0026#34;has elements\u0026#34;); assert_eq!(last_element, 9 * 9); We\u0026rsquo;ve declared the StackVec structure for you already:\npub struct StackVec\u0026lt;\u0026#39;a, T: \u0026#39;a\u0026gt; { storage: \u0026amp;\u0026#39;a mut [T], len: usize } Understanding StackVec The following questions test your understanding about the StackVec interface:\nWhy does push return a Result? (push-fails)\nThe push method from Vec in the standard library has no return value, but the push method from our StackVec does: it returns a Result indicating that it can fail. Why can StackVec::push() fail where Vec::push() does not?\nWhy is the 'a bound on T required? (lifetime)\nstruct StackVec\u0026lt;\u0026#39;a, T\u0026gt; { buffer: \u0026amp;\u0026#39;a mut [T], len: usize } Rust automatically enforces the bound T: 'a and will complain if type T lives shorter than the lifetime 'a. For instance, if T is \u0026amp;'b str and 'b is strictly shorter than 'a, Rust won\u0026rsquo;t allow you to create the instance of StackVec\u0026lt;'a, \u0026amp;'b str\u0026gt;.\nWhy is the bound required? What could go wrong if the bound wasn\u0026rsquo;t enforced by Rust?\nWhy does StackVec require T: Clone to pop()? (clone-for-pop)\nThe pop method from Vec\u0026lt;T\u0026gt; in the standard library is implemented for all T, but the pop method from our StackVec is only implemented when T implements the Clone trait. Why might that be? What goes wrong when the bound is removed?\nImplementing StackVec Implement all of the unimplemented!() StackVec methods in stack-vec/src/lib.rs. Each method is documented in the source code. We have also provided tests in src/tests.rs that help ensure that your implementations are correct. You can run these tests with cargo test. You\u0026rsquo;ll also need to implement the Deref, DerefMut, and IntoIterator traits for StackVec as well as the IntoIterator trait for \u0026amp;StackVec for all of the cargo test tests to pass. Once you feel confident that you implementation is correct and have answered this subphase\u0026rsquo;s questions, proceed to the next subphase.\nWhich tests make use of the Deref implementations? (deref-in-tests)\nRead through the tests we have provided in src/tests.rs. Which tests would fail to compile if the Deref implementation did not exist? What about the DerefMut implementation? Why?\nOur unit tests are incomplete!\nOur unit tests provide a baseline truth, but they are not complete! We will run additional tests when we grade your assignment. You may wish to find the gaps in our tests and add additional tests of your own to fill them.\nSubphase B: volatile In this subphase, you will learn about volatile memory accesses, read the source code in the volatile skeleton subdirectory, and answer questions related to the source code. You won\u0026rsquo;t be writing any code in this subphase.\nLike operating systems, compilers are masters at making things appear as if they\u0026rsquo;re doing what you think they\u0026rsquo;re doing when in reality, they\u0026rsquo;re really doing something entirely different for the sake of optimization. One such optimization is dead-access elimination: compilers remove memory accesses (reads and writes) when they can prove doing so has no observable effect on the program\u0026rsquo;s execution. For instance, consider the following program:\nfn f() { let mut x = 0; let y = \u0026amp;mut x; *y = 10; } The compiler can completely eliminate the write to *y by reasoning that *y is never read after it\u0026rsquo;s written. The compiler concludes that as a result, the write cannot possibly effect the program, and eliminates it in the compiled binary. For the same reason, it can then proceed to eliminate the declaration for y, the declaration for x, and calls to f() entirely.\nThese kinds of optimizations are almost exclusively beneficial: they speed up our programs without affecting their outcome. But sometimes these optimizations can have unintended consequences. Say, for example, that y was pointing to a write-only memory-mapped register. Then, writes to *y will have observable effects without having to read *y thereafter. If the compiler is not aware of this, it will optimize away these writes, and our program will not function correctly.\nHow can we force the compiler to keep around reads and writes that appear to have no effects at the source code level? This is where volatile memory accesses come in: the compiler promises not to optimize away volatile memory accesses. So if we want to ensure a read or write occurs at runtime, we must perform a volatile memory access.\nRusty volatile In Rust, we use the read_volatile and write_volatile methods to perform volatile reads and writes to a raw pointer.\nWhat\u0026rsquo;s a raw pointer?\nBy now you\u0026rsquo;re familiar with references (\u0026amp;T and \u0026amp;mut T). A raw pointer in Rust (*const T and *mut T) is a \u0026ldquo;reference\u0026rdquo; that isn\u0026rsquo;t tracked with lifetimes by Rust\u0026rsquo;s borrow checker. Because of this, read or writes to these pointers may be invalid, just as in C. Rust considers them unsafe, and code that reads or writes them must be annotated with unsafe to indicate this. You can read more about raw pointers in the rustdocs .\nCalling read_volatile and write_volatile every time we want to perform a volatile read or write is error prone and frustrating. Thankfully Rust provides us the tools to make this easier and safer. Ideally we can simply declare a pointer as volatile (as in C) and ensure that every read or write thereafter is volatile. Even better, we should be able declare a pointer as read-only, write-only (unlike in C), or read/write and ensure only the appropriate memory accesses can be made.\nIntroducing Volatile, ReadVolatile, WriteVolatile, and UniqueVolatile The volatile crate in the volatile/ skeleton subdirectory implements these four types that allow us to do just this. Read the documentation for these types now by running cargo doc --open inside of the volatile/ directory.\nWhy does Unique\u0026lt;Volatile\u0026gt; exist? (unique-volatile)\nBoth Volatile and Unique\u0026lt;Volatile\u0026gt; allow read/write volatile accesses to an underlying pointer. According to the documentation, what is the difference between these two types?\nNow open the source code in src/lib.rs, src/traits.rs, and src/macros.rs. Read through the source code to the best of your abilities. When you\u0026rsquo;re ready, answer the following questions. Once you have answered these questions, you\u0026rsquo;re ready to move on to the next subphase.\nWhat\u0026rsquo;s with #[repr(C)]?\nThe #[repr(C)] annotation forces Rust to lay out the structure\u0026rsquo;s fields in the same way that C would. In general, Rust optimizes the order and padding between fields of structures in an unspecified way. When we cast a raw address to a pointer to a structure, we typically have a very specific memory layout in mind. The #[repr(C)] annotation lets us confide that Rust will arrange the structure as we intend it to, not as it wishes.\nHow are read-only and write-only accesses enforced? (enforcing)\nThe ReadVolatile and WriteVolatile types make it impossible to write and read, respectively, the underlying pointer. How do they accomplish this?\nWhat do the macros do? (macros)\nWhat do the readable!, writeable!, and readable_writeable! macros do?\nSubphase C: xmodem In this subphase, you will implement the XMODEM file transfer protocol in the xmodem library in the xmodem/ skeleton subdirectory. You will primarily be working in xmodem/src/lib.rs.\nXMODEM is a simple file transfer protocol originally developed in 1977. It features packet checksums, cancellation, and automatic retries. It is widely implemented and used for transfers through serial interfaces. Its best feature, however, is its simplicity. For more about its history, see the XMODEM Wikipedia article .\nWe will use the XMODEM protocol to transfer files to the Raspberry Pi. While we could use existing implementations of the XMODEM protocol to send data to the Pi, we will still need to write our own receiver. So, while we\u0026rsquo;re at it, we\u0026rsquo;ll be implementing XMODEM transmission as well.\nThe Protocol The XMODEM protocol is described in detail in the Understanding The X-Modem File Transfer Protocol txt file. We describe it again here, for posterity.\nDo not base your implementation off of Wikipedia\u0026rsquo;s explanation!\nWhile Wikipedia\u0026rsquo;s explanation is helpful at a high level, many of the details presented there are different from the protocol we\u0026rsquo;ll be implementing here. As such, do not use the article as a reference for this subphase.\nXMODEM is a binary protocol: bytes are sent and received in the raw. It is also \u0026ldquo;half duplex\u0026rdquo;: at any point in time, either the sender or receiver is sending data, but never both. Finally it is packet-based: data is separated into 128 byte chunks known as packets. The protocol dictates which bytes are sent when, what they mean, and how they\u0026rsquo;re interpreted.\nFirst, we define a few constants:\nconst SOH: u8 = 0x01; const EOT: u8 = 0x04; const ACK: u8 = 0x06; const NAK: u8 = 0x15; const CAN: u8 = 0x18; To start the file transfer, the receiver sends a NAK byte while the sender waits for a NAK byte. Once the sender has received the NAK byte, packet transmission begins. The receiver only sends a NAK byte to begin the file transfer, not once for every packet.\nOnce file transfer has begun, each packet\u0026rsquo;s transmission and reception is identical. Packets are numbered in sequential order starting at 1 and wrap around to 0 after 255.\nXMODEM protocol diagram To send a packet, the sender:\nSends an SOH byte.\nSends the packet number.\nSends the 1s complement of the packet number (255 - $packet_number).\nSends the packet itself.\nSends the packet checksum.\nThe checksum is the sum of all of the bytes in the packet mod 256. Reads a byte from the receiver.\nIf the byte is NAK, transmission for the same packet is retried up to 10 times. If the byte is ACK, the next packet is sent. The receive a packet, the receiver performs the inverse:\nWaits for an SOH or EOT byte from the sender.\nIf a different byte is received, the receiver cancels the transfer. If an EOT byte is received, the receiver performs end of transmission. Reads the next byte and compares it to the current packet number.\nIf the wrong packet number is received, the receiver cancels the transfer. Reads the next byte and compares it to the 1s complement of the packet number.\nIf the wrong number is received, the receiver cancels the transfer. Reads a packet (128 bytes) from the sender.\nComputes the checksum for the packet.\nThe checksum is the sum of all of the bytes in the packet mod 256. Reads the next byte and compares it to the computed checksum.\nIf the checksum differs, sends a NAK byte and retries reception for the same packet. If the checksum is the same, sends an ACK byte and receives the next packet. To cancel a transfer, a CAN byte is sent by either the receiver or sender. When either side receives a CAN byte, it errors out, aborting the connection.\nTo end the transmission, the sender:\nSends an EOT byte. Waits for a NAK byte. If a different byte is received, the sender errors out. Sends a second EOT byte. Waits for an ACK byte. If a different byte is received, the sender errors out. To end the transmission, the receiver performs the following after receiving the first EOT:\nSends a NAK byte. Waits for a second EOT byte. If a different byte is received, the receiver cancels the transfer. Sends an ACK byte. Implementing XMODEM We have provided an unfinished implementation of the XMODEM protocol in the xmodem skeleton subdirectory. Your task is to complete the implementation by writing the expect_byte, expect_byte_or_cancel, read_packet, and write_packet methods in src/lib.rs. Your implementations should make use of the internal state of the Xmodem type: packet and started. We recommend reading over the existing code before starting.\nYou should begin by implementing the expect_byte and expect_byte_or_cancel methods. You should then make use of all four of the helper methods (including read_byte and write_byte) to implement read_packet and write_packet. To see how these methods are used, read the transmit and receive implementations which transmit or receive a complete data stream using XMODEM via these methods. Be mindful of the specifications in the doc-comments. You can test your implementation using cargo test. Once you are confident that your implementation is correct, proceed to the next subphase.\nDo not use any additional items from std.\nYour implementation should only use items from shim::io. It should not use other items from std or any other libraries.\nOur reference implementations for {read,write}_packet are roughly 43 lines of code each.\nThe io::Read and io::Write rustdocs will be useful.\nUse the ? operator generously.\nThe test source code can be a helpful guide.\nYou can use ioerr! macro to make and return a new io::Error easily. Please refer shim/src/macros.rs to find more macros which can be useful.\nSubphase D: ttywrite In this subphase, you will write a command line utility, ttywrite, that will allow you to send data to your Raspberry Pi in the raw or via the XMODEM protocol. You will use your xmodem library from the previous subphase in your implementation. You will write your code in ttywrite/src/main.rs. To test your ttywrite implementation, use the provided test.sh script.\nWhat is a serial device?\nA serial device is any device that accepts communication one bit at a time. This is known as serial communication. In contrast, in parallel communication multiple bits are being transferred at any point in time in parallel. We will be communicating with our Raspberry Pi via its UART device, a serial communication device.\nWhat is a TTY?\nA TTY is a \u0026ldquo;teletypewriter\u0026rdquo;. It is a vestigial term that was adopted in computing to describe computer terminals. The term later become more general, coming to describe any device intended to be communicated with over serial. For this reason, your computer calls the device mapping to your Raspberry Pi a TTY.\nCommand-Line Interface The skeleton code we have provided for ttywrite already parses and validates command-line arguments. To do so, it uses the structopt crate from crates.io which itself uses clap . You\u0026rsquo;ll notice that we list it as a dependency in the Cargo.toml file. structopt works through code generation. We simply annotate a structure and its fields with a declaration of our command-line arguments and structopt generates the code to actually parse the command-line flags.\nTo see the interface that structopt generates, call the application with --help. Remember that you can pass arbitrary flags when using cargo run: cargo run -- --help. Take a look at the interface now. Then, take a look at the Opt structure in main.rs and compare the interface with its definition.\nWhat happens when a flag\u0026rsquo;s input is invalid? (invalid)\nTry passing in some invalid values for flags. For instance, it should not be possible to set -f to idk. How does structopt know to reject invalid values?\nYou\u0026rsquo;ll notice that there are plenty of options. All of these correspond to settings available on a serial device. For now it\u0026rsquo;s not important to know exactly what these settings do.\nTalking to a Serial Device In main, you\u0026rsquo;ll see a call to serial::open . This is calling the open function from the serial crate, also on crates.io . This open function returns a TTYPort which allows you to read and write to the serial device (via its io::Read and io::Write trait implementations) as well as read and set settings on a serial device (via its SerialDevice trait implementation).\nWriting the Code Implement the ttywrite utility. Your implementation should set all of the appropriate settings passed in via the command-line stored in the opt variable in main. It should read from stdin if no input file is passed in or from the input file if one is passed in. It should write the input data to the passed in serial device. If the -r flag is set, it should send the data as it is. Otherwise, you should use your xmodem implementation from the previous subphase to send the data using the XMODEM protocol. You should print the number of bytes sent on a successful transmission.\nTo transmit using the XMODEM protocol, your code should use either the Xmodem::transmit or Xmodem::transmit_with_progress methods from the xmodem library. We recommend using transmit_with_progress so that your utility indicates progress throughput the transmission. In its simplest form, this might look as follows:\nfn progress_fn(progress: Progress) { println!(\u0026#34;Progress: {:?}\u0026#34;, progress); } Xmodem::transmit_with_progress(data, to, progress_fn) You can test the baseline correctness of your implementation using the test.sh script in the ttywrite directory. When your implementation is at least somewhat correct, you will see the following when the script is run:\nOpening PTYs... Running test 1/10. wrote 333 bytes to input ... Running test 10/10. wrote 232 bytes to input SUCCESS You can retrieve a handle to stdin with io::stdin() .\nYou may find the io::copy() function useful.\nThe main() function in our reference implementation is roughly 35 lines of code.\nKeep the TTYPort documentation open while writing your code.\nWhy does the test.sh script always set -r? (bad-tests)\nThe test.sh script that we have provided always uses the -r flag; it doesn\u0026rsquo;t test that your utility uses the XMODEM protocol when it is asked to. Why might that be? What does the XMODEM protocol expect that sending data in the raw doesn\u0026rsquo;t that makes testing its functionality difficult?\nInstalling ttywrite utility After finish writing the ttywrite utility, install the tool with cargo install --path . --locked command. This command will be used later to communicate with the bootloader.\n",
        "url": "\/post\/lab3\/"
    },

    "\/post\/env_setup\/": {
        "title": "Tools",
        "tags": ["Lab",],
        "content": "Setting up the environment Before starting to this series of lab assignments, please make sure that you have followed the environment setup described below.\nOur labs are designed based on Ubuntu 20.04 LTS. This is done using docker so that everyone has similar setups.\nWe recommend you to stick to this ubuntu version unless you might face some configuration issues.\nYou will also be using use QEMU, an x86 emulator for easier executing and debugging process instead of using real raspberry pi board.\nThis section has the information you’ll need to setup the environment.\nDocker You may install Ubuntu 20.04 on WSL and skip to the next part .\nYou first need to install docker for your OS:\nWindows Mac Linux Spin up Container Please ensure that your installation location for Docker has atleast 10GB of free space.\nGo to your working directory where you\u0026rsquo;ll be working inside and run:\ndocker run -it --name os_labs -v $(pwd):/root/workdir:Z ubuntu:20.04 Now you\u0026rsquo;ll be inside the container, where you\u0026rsquo;ll see a prompt like this:\nroot@e8f10931f506:/# Your working directory will now be available in /root/workdir/.\nFor resuming the container after you\u0026rsquo;ve exited:\ndocker start -i os_labs Anyone with SELINUX enabled distros like Fedora may face some problems with shared dirs between the host and the containers. Please contact the TAs if you get stuck somewhere.\nGetting Repository and Installing Dependencies Please ensure that whatever directory you decide to keep the lab in, it has atleast 10GB of free space.\n# Download the repository git clone https://github.com/pratyush3757/cs330_os.git --origin skeleton rustos cd rustos/ git switch lab3 # Install dependencies ./bin/setup.sh # Update environment source ~/.bashrc You\u0026rsquo;re all set to go back to the lab document if the setup.sh runs correctly and says [!] Setup complete.\nContact a TA if it throws an error.\nReference This section has the information for the various tools you\u0026rsquo;ll be using during the labs.\nWe will be updating this section with more required info as the labs go on.\nMakefile Our Makefile includes a number of targets to test and run our OS in various ways.\nmake Build kernel in release mode. The result executable and binary will be located under build/ subdirectory. make debug Build Rust libraries or kernel in debug mode. make check Check a local package and all of its dependencies for errors. make qemu Start QEMU with the executable file under build/ subdirectory generated by make command. QEMU will generate a detailed log of assembly code of the guest. To exit QEMU, press Ctrl-a x. make objdump Disassemble the executable file generated by make. make nm List all symbols in the executable file generated by make. make clean Clean the directory. make install Install compiled kernel image to SD card. (Not needed until we have physical RPi devices) make test Execute all unit and integration tests and build examples of a local package. QEMU Emulator QEMU (manual ) is a modern and fast PC emulator. We are providing a pre-built QEMU binary to emulate raspberry pi 3+ board as /bin/qemu-system-aarch64.\nQEMU includes a built-in monitor that can inspect and modify the machine state in useful ways. To enter the monitor, press Ctrl-a c in the terminal running QEMU. Press Ctrl-a c again to switch back to the serial console.\nFor a complete reference to the monitor commands, see the QEMU manual . Here are some particularly useful commands:\nxp/Nx paddr Display a hex dump of N words starting at physical address paddr. If N is omitted, it defaults to 1. This is the physical memory analogue of GDB’s x command. info registers Display a full dump of the machine’s internal register state. In particular, this includes the machine’s hidden segment state for the segment selectors and the local, global, and interrupt descriptor tables, plus the task register. This hidden state is the information the virtual CPU read from the GDT/LDT when the segment selector was loaded. info mem Display mapped virtual memory and permissions. For example, ef7c0000-ef800000 00040000 urw efbf8000-efc00000 00008000 -rw tells us that the 0x00040000 bytes of memory from 0xef7c0000 to 0xef800000 are mapped read/write and user-accessible, while the memory from 0xefbf8000 to 0xefc00000 is mapped read/write, but only kernel-accessible. ",
        "url": "\/post\/env_setup\/"
    },

    "\/": {
        "title": "",
        "tags": [],
        "content": " ",
        "url": "\/"
    },

    "\/categories\/": {
        "title": "Categories",
        "tags": [],
        "content": "",
        "url": "\/categories\/"
    },

}
</script>
<script defer src="/js/lunr.js"></script>
<script defer src="/js/search.js"></script>

</footer>

</body>
</html>