Overview Your cover in the Lizard Legion was blown, and you’ve been revealed as a double agent and driven out! It was all very “James Bond”, if you do say so yourself, and what a daring underground helicopter escape it was… but you feel lucky to have escaped with your skin. (Literally… they would have used you to make a “human suit”!) Now that you’re back on the “outside”, you’ve been tasked with creating a scheme to allow remaining resistance fighters still within the Lizard Legion to clandestinely move information back to your organization without raising suspicion. As of late, members of the Lizard Legion have discovered the PC classic “DOOM”, and it has become all the rage to build new mods for it at headquarters, so your team has decided to use mods for this title as a vehicle for exfiltration. By burying encrypted bits within textures and other game data blocks, information can be hidden within innocuous “WAD” (Where’s All the Data) files. In this project, you will implement a userspace filesystem daemon using the FUSE (Filesystem in UserSpacE) API to access data in WAD format, the standard used in a number of classic PC game titles (including DOOM and Hexen). In this critical early prototype, you have been tasked with implementing read and write access to files and directories within the WAD files as a proof-of-concept. As such, you will need to implement read and write functionality for both files and directories within your FUSE-based program. We, as your comrades-in-arms battling the Reptilian invasion, will provide sample WAD files to demonstrate the functionality of your implementation. (The resistance is counting on you!) The resistance uses university courses as cover for standard operations, so you’ll submit the project via Canvas. Structure The project is broken into three main parts: 1) Develop a library to read and write to WAD files and create a directory and file structure from them. 2) Implement a userspace daemon (via FUSE) to access the directory structure once mounted. 3) Test your implementation by navigating the mounted directory, examining file names and contents, and adding directories and files of your own. While exact implementation may vary, the daemon’s parameters must match those laid out in this document, and the directory structure, naming, and file contents must be properly presented via the filesystem. File Format The WAD file format contains information in three sections: the header, which gives basic layout information, the descriptors, which describe elements in the file, and the lumps, which contain the data themselves. NOTE: all numbers are in little-Endian format and, where applicable, are designated in bytes! Since Reptilian stores its variables in memory in little-Endian format as well, it is not necessary to perform any byte-order inversions when reading in or writing data, but this is still important information to know. File Header The header contains the file magic, descriptor count, and location (offset) of the descriptors in the file: The magic for a wad file is usually ASCII and always ends in the suffix “WAD” (e.g., “IWAD” or “PWAD”). It is also important to note that the descriptor list, beginning at the position indicated by the descriptor offset, is always situated at the end of the WAD file. Descriptors The file’s descriptors contain information about elements in the WAD file – its file offset, length, and name: Some elements will have specific naming conventions that will differentiate them from regular content files. These “marker” elements will be interpreted by the daemon as directories and should be displayed accordingly in the filesystem (see below). Lumps Elements in the WAD format are stored as “lumps” described by the descriptors. These lumps will be represented in the filesystem by the daemon as individual files that can be opened, read, and closed. You cannot write to existing lumps, but you will be creating empty files whose lumps you will have to write to. Marker Elements There are two primary types of marker elements in WAD files, each of which should be interpreted as directories by our daemon. The types are map markers and namespace markers. Map marker names are of the format “E#M#”, where # represents a single decimal digit (e.g., “E1M9”). They are followed by ten (10) map element descriptors. The elements for the next 10 descriptors should be placed inside of a directory with the map’s name. Map marker directories cannot have files or directories added to them. Namespace markers come in pairs. A namespace’s beginning is marked with a descriptor whose name has the suffix “_START” (e.g., “F1_START”), and its ending is marked with a descriptor whose name has the suffix “_END” (e.g., “F1_END”). Any descriptors for elements falling between the beginning and ending markers for a namespace should be placed within a directory with the namespace’s name (e.g., “F1”). A namespace marker’s name, excluding the suffix, will never exceed two characters. This is the kind of directory you will be responsible for creating. For example, the following descriptors, in order, in the descriptor list, should result in this organization: Library Your library will contain a class to represent WAD data as described in this section. Wad Class The Wad class is used to represent WAD data and should have the following functions. The root of all paths in the WAD data should be “/”, and each directory should be separated by ‘/’ (e.g., “/F/F1/LOLWUT”). public static Wad* loadWad(const string &path) Object allocator; dynamically creates a Wad object and loads the WAD file data from path into memory. The caller is responsible for deallocating the memory using the delete keyword. public string getMagic() Returns the magic for this WAD data. public bool isContent(const string &path) Returns true if path represents content (data), and false otherwise. public bool isDirectory(const string &path) Returns true if path represents a directory, and false otherwise. public int getSize(const string &path) If path represents content, returns the number of bytes in its data; otherwise, returns -1. public int getContents(const string &path, char *buffer, int length, int offset = 0) If path represents content, copies as many bytes as are available, up to length, of content’s data into the preexisting buffer. If offset is provided, data should be copied starting from that byte in the content. Returns number of bytes copied into buffer, or -1 if path does not represent content (e.g., if it represents a directory). public int getDirectory(const string &path, vector *directory) If path represents a directory, places entries for immediately contained elements into directory. The elements should be placed in the vector in the same order as they are found in the WAD file. Returns the number of elements in the directory, or -1 if path does not represent a directory (e.g., if it represents content). Offset Length Name 0 0 F_START 0 0 F1_START 67500 0 E1M1 67500 1380 THINGS 68880 6650 LINEDEFS 75532 19440 SIDEDEFS 94972 1868 VERTEXES 96840 8784 SEGS 105624 948 SSECTORS 106572 6608 NODES 113180 2210 SECTORS 115392 904 REJECT 116296 6922 BLOCKMAP 42 9001 LOLWUT 0 0 F1_END 0 0 F_END F F1 E1M1 THINGS LINEDEFS SIDEDEFS VERTEXES SEGS SSECTORS NODES SECTORS REJECT BLOCKMAP LOLWUT Directory Structure → public void createDirectory(const string &path) path includes the name of the new directory to be created. If given a valid path, creates a new directory using namespace markers at path. The two new namespace markers will be added just before the “_END” marker of its parent directory. New directories cannot be created inside map markers. public void createFile(const string &path) path includes the name of the new file to be created. If given a valid path, creates an empty file at path, with an offset and length of 0. The file will be added to the descriptor list just before the “_END” marker of its parent directory. New files cannot be created inside map markers. public int writeToFile(const string &path, const char *buffer, int length, int offset = 0) If given a valid path to an empty file, augments file size and generates a lump offset, then writes length number of bytes from the buffer into the file’s lump data. If offset is provided, data should be written starting from that byte in the lump content. Returns number of bytes copied from buffer, or -1 if path does not represent content (e.g., if it represents a directory). NOTE: If a file or directory is created inside the root directory, it will be placed at the very end of the descriptor list, instead of before an “_END” namespace marker. You MUST use POSIX calls (not fstream) for all file I/O! Daemon Command & Parameters Your daemon must have name wadfs and should accept at a minimum three parameters – the single-threaded flag “-s”, the target WAD file, and the mount directory. For example, this command should mount TINY.WAD in /home/reptilian/mountdir: $ ./wadfs -s TINY.WAD /home/reptilian/mountdir …and this should result from executing the ls command to show part of its contents: $ ls /home/reptilian/mountdir/F/F1 -al total 0 drwxrwxrwx. 2 root root 0 Jan 1 1970 . drwxrwxrwx. 2 root root 0 Jan 1 1970 .. drwxrwxrwx. 2 root root 0 Jan 1 1970 E1M1 -rwxrwxrwx. 2 root root 9001 Jan 1 1970 LOLWUT We will use the following command to unmount your filesystem: $ fusermount -u /home/reptilian/mountdir Your daemon should run in the background. Do not hard-code the debug (-d) or foreground (-f) flags! Extra Credit You may notice when testing with your daemon that there is an upper limit to how large files you create in your filesystem can be. Your task is to configure your library and daemon such that you are able to create large files in your filesystem (using “cp” to copy in a 200KB image file, for example). Running your daemon in debug mode (-d) may give you hints as to how certain calls are expected to behave. File and Directory Requirements Your daemon must implement, at a minimum, the following filesystem functions to provide read/write access: 1) Retrieving file and directory attributes 2) Reading from existing files and writing to new ones 3) Reading from existing directories and writing to new ones Files and directories should be given full read, write, and execute permissions. The above requirements will be achieved using, at a minimum, the following six fuse callback functions: get_attr, mknod, mkdir, read, write, and readdir It is highly recommended to closely follow the linked resources at the bottom of this pdf to assist with your FUSE implementation. All changes to the filesystem, such as directory and file creation, must survive between mounting and unmounting. Building with FUSE FUSE is a userspace filesystem API that is supported directly by the Linux kernel. It allows userspace programs to provide information to the kernel about filesystems the kernel cannot interpret on its own. Installation & Setup To use the FUSE library, you will need to install it within Reptilian and change the FUSE permissions: $ sudo apt install libfuse-dev fuse $ sudo chmod 666 /dev/fuse NOTE: if you reboot the virtual machine, you will need to re-add the FUSE permissions, as they will be reset! Build Directives In order to build programs using the FUSE library system, you will need to specify the file offset bits as 64 and identify the FUSE version. We recommend specifying FUSE version 26 (though this is optional): $ g++ -D_FILE_OFFSET_BITS=64 -DFUSE_USE_VERSION=26 myproggy.cpp -o myproggy -lfuse Submission You will submit the following at the end of this project: ⚫ Plain text file containing YouTube link to unlisted screencast video (screencast.txt) ⚫ Compressed tar archive for libWad library and wadfs daemon (wad.tar.gz) Screencast You will record a screencast (with audio) walking through your library and daemon. As you explain something, you should show the corresponding file/code. You will upload the recording as an unlisted YouTube video and submit a text file containing a link to the video. Your screencast should: • Explain how your library represents WAD file elements (data structure(s) you used, why, and how) • Walk through ALL your library code, including any custom helper functions, classes, structs, etc. o Explain your logic thoroughly — you don’t have to go line-by-line, but explain what your code generally does, why it does that, and how it does that (this includes simple stuff like getters) • Walk through all your daemon code o Explain what the daemon main does and why o Explain how your daemon leverages the Wad library o Explain all required callbacks (getattr, mknod, mkdir, read, write, readdir) • Demo daemon functionality (create/write/read directory, create/write/read file, read file attributes) • Demo library functionality (demoing the daemon is sufficient; alternatively, run the given test suite) • EC: Explain the code that enables writing large files and demo it with a file of at least 200 KB in size • Be at most 5 ½ minutes long. (Audio speed-up is prohibited) Compressed Archive (wad.tar.gz) Your compressed tar file should have the following directory/file structure: wad.tar.gz libWad (directory) Makefile Wad.h (Various source files) wadfs (directory) Makefile (Various source files) Do NOT include any extraneous files in your compressed archive, such as output files (*.a, *.o, the wadfs executable), testing files, .wad files, etc. Your libWad Makefile MUST create libWad.a and Wad.o. It may create other .o files if necessary for your implementation. Your Makefile must only build your library, make sure it does not build any executables (like wad_dump.cpp). Your wadfs Makefile MUST create an executable named wadfs with no file extension. It must link with your libWad library. Do NOT include debug printing in your submission. Remove any stray cout’s or printk/printf’s from your library and daemon, as it may interfere with output comparisons when grading. Please test your submission with the commands below. If your library and daemon extract and build when you run these commands exactly, then they will work when they are graded. To build the library and daemon, we will execute these commands: $ tar zxvf wad.tar.gz $ cd libWad $ make $ cd .. $ cd wadfs $ make $ cd .. To build another program using your library, we will execute this command: $ g++ -o program_name sourcefile.cpp -L ./libWad -lWad To run your daemon, we will execute this command: $ ./wadfs/wadfs -s somewadfile.wad /some/mount/directory Helpful Links You may find the following resources helpful when reading about how to implement a FUSE daemon: https://www.cs.nmsu.edu/~pfeiffer/fuse-tutorial/html/ https://engineering.facile.it/blog/eng/write-filesystem-fuse/ https://maastaar.net/fuse/linux/filesystem/c/2019/09/28/writing-less-simple-yet-stupid-filesystem-using-FUSE-in-C/ https://www.cs.hmc.edu/~geoff/classes/hmc.cs137.201601/homework/fuse/fuse_doc.html http://slade.mancubus.net/index.php?page=about
Welcome to CDA 4205L Lab #2! The purpose of this lab is to help you better understand abstraction in computer architecture, and how different hardware designs can impact power, performance, and area. Prelab Consider the different layers of abstraction in a computer system. At the highest level, an application (e.g., sorting a list) can be implemented in a number of different ways. You can use bubble sort, heapsort, quicksort, and many other algorithms. Algorithms can be implemented in a programming language of your choice, and, as long as an appropriate compiler or interpreter exists for your target system, you can execute your program on that target. Computer Architecture considers the levels of abstraction between the operating system and gate-level implementation of circuits. This comprises the instruction set architecture (ISA), the microarchitecture, and the register transfer level. The ISA defines the interface between the hardware and software; in other words, it defines how the processor is controlled by the software, and what the processor is capable of doing. The microarchitecture defines a particular implementation of an ISA. Just as there are many algorithms that can achieve the same goal (e.g., sorting a list), many different microarchitectures can implement the same ISA. The microarchitecture defines structures like the ALU, register file, and connections between them. In turn, each of these structures can be defined in many different ways – this is the register transfer level. This defines how data move between registers, and how the data is transformed in the process. In this lab, we will consider an ISA that defines a “multiplication” operation. This operation takes two operands, multiplies them together, and generates a product. For now, we will assume that the inputs are 32-bit words, but the input values are only ever 16-bits (at most). Hence, the result will fit into one 32-bit product register. Although the ISA defines the “multiplication” operation, it does not specify how the multiplication happens, just that it does. Two different microarchitectures exist which implement the ISA. In one, there is a dedicated multiplication circuit, and in the other, it must perform repeated addition, i.e., when the inputs are 4 and 5, the hardware will add 4 to itself 5 times, taking 5 cycles to complete. While the multiplier is physically larger (it takes more logic gates) and more energy, the repeated addition is slower and takes less energy per addition. Hence, for certain applications, you may decide to use uArch_1 or uArch_2, depending on the power, performance, and area budget. Figure 1: Layers of abstraction in a computer. The middle represents layers addressed by computer architecture. Lab. 1. Download the uArch_1.asm file from Canvas (Files > Labs > Lab 02). This contains the skeleton of the first assembly program you will write. 2. Implement the function labeled “_multiply”. Recall that in uArch_1, there is a physical multiplier circuit. You can use this feature by writing the “mul” instruction. 3. Set a0 to 550 and a1 to 21, assemble, and run the code. Note: you may modify a0 and a1 values while debugging but your final results must use 550 and 21, respectively. 4. Open the Instruction Statistics tool and click on “Connect to Program” 5. Re-run your program. You should see the total number of instructions, along with a breakdown of different instruction types. 6. Repeat 1-5 using the file uArch_2.asm. Recall that this represents the second microarchitecture which does not have a dedicated multiplication circuit and instead uses repeated addition. Hence, your implementation in #2 is not allowed to use a “mul” instruction (including mulh, mulhu, etc.). 7. Answer the following. Show your work and explain your result. T1: Take a screenshot of the RARS console output for both files. Include this in your report. T2: How many total instructions were there? How many of each type? T3/T4: Remember to repeat T1 and T2 for uArch_2 and include the results in your report. T5: Assume the implementation of uArch_1 has an area of 8 um2 , and the implementation of uArch_2 has an area of 7 um2 . What is the area overhead for the multiplier? Report your result both as a raw value as well as a percent overhead. T6: Assume the multiplication itself consumes 500 pJ of energy, whereas other ALU instructions (those used for arithmetic such as add or addi excluding branch/comparison/etc.) consume 4 pJ each. If performance and area are not considered, at what point is it better to use uArch_1 rather than uArch_2 in terms of energy? T7: One important metric when evaluating different microarchitectures is energy efficiency, often reported as the Energy Delay Product, or EDP. This is the total delay multiplied by the total energy to perform the operation. Using the values provided in T6 and a 500ps CPU clock period, compute the EDP for uArch_1 and uArch_2 when performing 21*21=212 . In-class work – Complete at least T1-T4, show them to the TA for review and submit them on Canvas before the lab session ends. Submit your in-class work as a Word document (.docx) format. Final-Report – Submit your report pdf with answers to all questions and screenshots. Also, submit the final assembly file(s). Combine these in a .zip file. It is due in 1 week, before the next lab.
Overview Due to your excellent work handling the metadata for project Sky Skink, the great Silurian overload Reptar himself has commissioned your work in designing a new custom Memory Manager application for Reptilian. This new project, deemed Project Repto, is built using functionality from various layers of the OS to avoid human corruption. For extra security, the memory manager will write a log of its state when closed. If all goes well, your manager will be deployed all throughout the great Lizard Legion. In this project, you will implement a memory manager in C++, whose features include initializing, tracking, allocating, and deallocating sections of memory. You will integrate the memory manager into a console program that we provide. The program will provide some simple unit testing to check for correctness but will not check for memory leaks and errors – it is your responsibility to test for leaks/errors and ensure overall correctness! You must also maintain a valid listing of memory holes and combine those holes as appropriate and discussed in the class and text. You’ll then create a short video to demonstrate your code and submit the project via Canvas. Structure Modern operating systems are often built in layers with specific goals and limited privileges. Layering also facilitates the implementation of recognized standards by separating hardware and OS-specific implementations from generalized API calls. Your memory manager will make use of these standard functions so that it can be used in console applications. The project is broken into three main parts: 1) Write a memory manager class in C++ using basic system functionality. 2) Write two memory allocation algorithms to be used by your memory manager. 3) Package your class and algorithms together into a static library to be used by our console testing program. Figure 1: Memory manager is instantiated from a console program. System Library Memory Manager Console Program While exact implementation may vary, the library functions must match the signatures laid out in this document. Specification The memory manager will incorporate the following class(es) and function(s). Memory Manager Class The Memory Manager will handle the allocation/deallocation of memory and provide details of its state. How the class keeps track of allocation/deallocation is implementation dependent and is left for the student to decide. MemoryManager.h and MemoryManager.cpp will contain declaration and definition, respectively. public MemoryManager(unsigned wordSize, std::function allocator) Constructor; sets native word size (in bytes, for alignment) and default allocator for finding a memory hole. public ~MemoryManager() Releases all memory allocated by this object without leaking memory. public void initialize(size_t sizeInWords) Instantiates block of requested size, no larger than 65535 words; cleans up previous block if applicable. public void shutdown() Releases memory block acquired during initialization, if any. This should only include memory created for long term use not those that returned such as getList() or getBitmap() as whatever is calling those should delete it instead. public void *allocate(size_t sizeInBytes) Allocates memory using the allocator function. If no memory is available or size is invalid, returns nullptr. public void free(void *address) Frees the memory block that starts at the given address within the memory manager so that it can be reused. public void setAllocator(std::function allocator) Changes the algorithm used in allocation to find a memory hole. public int dumpMemoryMap(char *filename) Uses standard POSIX calls to write hole list to filename as text, returning -1 on error and 0 if successful. Format: “[START, LENGTH] – [START, LENGTH] …”, e.g., “[0, 10] – [12, 2] – [20, 6]” public void *getList() Returns an array of information (in decimal) about holes for use by the allocator function (little-Endian). Offset and length are in words. If no memory has been allocated, the function should return a NULL pointer.Format: Example: [3, 0, 10, 12, 2, 20, 6] public void *getBitmap() Returns a bit-stream of bits in terms of an array representing whether words are used (1) or free (0). The first two bytes are the size of the bitmap (little-Endian); the rest is the bitmap, word-wise. Note : In the following example B0, B2, and B4 are holes, B1 and B3 are allocated memory. Hole-0 Hole-1 Hole-2 ┌─B4─┐ ┌ B2┐ ┌───B0 ──┐ ┌─Size (4)─┐┌This is Bitmap in Hex┐ Example: [0,10]-[12,2]-[20,6] → [00 00001111 11001100 00000000] → [0x04,0x00,0x00,0xCC,0x0F,0x00] ┕─B3─┙ ┕B1┙ Returned Array: [0x04,0x00,0x00,0xCC,0x0F,0x00] or [4,0,0,204,15,0] public unsigned getWordSize() Returns the word size used for alignment. public void *getMemoryStart() Returns the byte-wise memory address of the beginning of the memory block acquired during initialization. public unsigned getMemoryLimit() Returns the byte limit (total size, in bytes) of the current memory block. Note: The following two functions should not be part of the Memory Manager Class. Memory Allocation Algorithms int bestFit(int sizeInWords, void *list) Returns word offset of hole selected by the best fit memory allocation algorithm, and -1 if there is no fit. int worstFit(int sizeInWords, void *list) Returns word offset of hole selected by the worst fit memory allocation algorithm, and -1 if there is no fit. Testing Your code must compile and function with the provided testing file. It is critical that you test for memory leaks and errors! The code we provide only covers base level functionality for the functions above and will not test for these. Submissions with memory leaks/errors will be marked zero for functionality. Make sure to remove any stray cout or print calls prior to submitting, as they may interfere with output comparisons. Makefile You will write a Makefile that creates libMemoryManager.a and MemoryManager.o. It may create other .o files if necessary for your implementation. Your Makefile must only build your library, make sure it does not build any executables (like CommandLineTest.cpp). Extra Credit In the above implementation of MemoryManager.initialize(…), you most likely made use of the new operator to acquire your initial block of memory. Your job is to now figure out how to allocate your initial block of memory without the use of new or any stdlib functions, e.g. malloc, calloc, etc. You may still use new and stdlib functions anywhere else in your implementation, just not in initialize. Submissions You will submit the following at the end of this project: ● Plain text file containing YouTube link to unlisted screencast video (screencast.txt) ● Compressed tar archive files for MemoryManager library (MemoryManager.tgz) Screencast You will record a screencast (with audio) walking through all your library code. As you explain something, you should be showing the corresponding file/code. You will upload the recording as an unlisted YouTube video and submit a text file containing a link to this video. Your screencast should: • Walk through all your library code, including the allocation algorithms and any custom helper functions. o Make sure to explain your logic thoroughly! • Explain how your code tracks holes and allocated regions, and what data structure(s) you used to do so. o Be sure to cover how holes & allocated regions are created/destroyed, and how holes are merged. • If you completed the extra credit, explain how (say more than just “I used x,” explain how you used x). • Demo functionality by running the provided test suite and checking for memory leaks and errors. • Be at most 5 minutes long. (Audio speed-up is prohibited) Compressed Archive (MemoryManager.tgz) Your compressed tar file should have the following directory/file structure: MemoryManager.tgz MemoryManager (directory) MemoryManager.h MemoryManager.cpp Makefile (Other source files)Do NOT include any extraneous files in your compressed archive, such as output files (*.a, *.o), *.sh scripts, CommandLineTest.cpp, etc. To create the archive, go to the directory containing your MemoryManager folder and use the command: $ tar -zcvf MemoryManager.tgz MemoryManager To build your program, we will execute these commands: $ tar -zxvf MemoryManager.tgz $ cd MemoryManager $ make $ cd .. To link against the library, we will execute this command: $ g++ -std=c++17 -o program_name sourcefile.cpp -L ./MemoryManager -lMemoryManager Please test your functions before submission! If your code does not compile it will result in zero credit (0, none, goose-egg) for that portion of the project. Helpful Links You may find these resources useful as you develop and test your memory manager. Development https://www.cs.rit.edu/~ark/lectures/gc/03_00_00.html https://www.ibm.com/developerworks/library/pa-dalign/index.html https://en.cppreference.com/w/cpp/utility/functional/function Testing http://valgrind.org/ https://github.com/catchorg/Catch2
Prologue You work for a top-secret shadow government organization dedicated to the rise of the Silurian overlords. You, as a faithful member of the Lizard Legion, are part of the team charged with improving data storage and handling, particularly tracking metadata – that is, data about data – within the organization’s computer systems. You have been tasked to build a coded message subsystem under the guise of process logging for kernels running in “Sky Skink”, the cloud computing system. Naturally, the Legion uses the superior Reptilian operating system distribution. Overview In this project, you will implement 3 system calls in Reptilian along with 3 static library functions that allow the system calls to be invoked from a C API. These custom system calls will get and set a custom process log level that will sit atop the standard Linux kernel’s diagnostic message logging system (dmesg) and allow processes to submit log entries along with a log level. If the log level for the message is more severe (lower than) the current log level, the message will be added to the kernel log. Log levels and names will correspond to those in the Linux kernel. We, as your benevolent lizard overlords, will provide a program that exercises and demonstrates the new calls. You create a short video to demonstrate your code. (Our masters will be most pleased.) You will submit the project via Canvas so as not to invite suspicion. Table 1. Kernel Log Levels and Corresponding Process Log Levels Kernel Level Name Description # Process Level Name KERN_EMERG Emergency / Crash Imminent (no process logging) 0 PROC_OVERRIDE KERN_ALERT Immediate Action Required 1 PROC_ALERT KERN_CRIT Critical/Serious Failure Occurred 2 PROC_CRITICAL KERN_ERR Error Condition Occurred 3 PROC_ERROR KERN_WARNING Warning; recoverable, but may indicate problems 4 PROC_WARNING KERN_NOTICE Notable, but not serious (e.g., security events) 5 PROC_NOTICE KERN_INFO Informational (e.g. initialization / shutdown) 6 PROC_INFO KERN_DEBUG Debug messages 7 PROC_DEBUG NOTE: Take snapshots of your VM! You will probably brick your machine at some point during this or other projects, and you will not want to start from scratch. No, seriously – take snapshots! Structure The project is broken into four main parts: 1) Create a kernel-wide process log level variable. 2) Create system calls that allow a process to get or set the process log level of the system. 3) Create system call that allows a process to add a process log message at a defined log level. 4) Create static library functions that allow the system calls to be invoked via a C API. User Program → Library → System Call Figure 1: A system call invoked from a user program While exact implementation may vary, the library functions must match the signatures laid out in this document, and the system calls must apply the security model properly. Logged messages are formatted “$log_level_name [$executable, $pid]: $message”, e.g.: PROC_ERROR [bacon_pancakes, 21]: Life is scary & dark. That is why we must find the light. NOTE: Your output must match the format exactly, including whitespace and semicolon location, failure to do will result in point deductions. System Calls The system will have a single, kernel-wide process log level which should initialize on boot in the kernel and must be stored persistently (until shutdown / reboot). The rules for logging are as follows: 1) The system-wide process log level should be initialized to 0 — i.e., override logging only. 2) Any process can read (get) the process log level. 3) Only a process running as the superuser may write (set) the process log level. 4) Log levels are values between 0–7. An invalid level results in call failure. 5) Any process may send a log message to the kernel. 6) If a message’s log level is higher than the process log level, the message is ignored. 7) If a message’s log level is lower than or equal to the process log level, the message will be logged. 8) Any successfully logged message should be logged at the corresponding kernel log level. 9) Messages must have a maximum length of 128 characters. Longer messages will be truncated. System calls are called via syscall(call_num, param1, param2). To log a message, the call should be syscall(PROC_LOG_CALL, msg, level). Call parameters are limited to two at most! Static Library You will create a static library to invoke the system calls in a directory named process_log. This includes a header, process_log.h (prototypes and level symbols), and a static library file named libprocess_log.a. You will also need to provide a Makefile for the library. All sources must be contained within the process_log directory. Please note, these filenames must match exactly! You will create a tarred gzip file of the process_log directory with name process_log.tar.gz. When testing, we will decompress the archive, enter the process_log directory, and build. All functions enumerated below must be made available by including “process_log.h”. See Submission for details. Library Functions int get_proc_log_level() Invokes system call which reads system-wide process log level. Returns the process log level. int set_proc_log_level(int new_level) Invokes system call which attempts to change the system-wide process log level to new_level. Returns new_level on success, and -1 otherwise. int proc_log_message(int level, char *message) Invokes system call to log a message for this process. Note that the order of parameters differs from the system call. Returns -1 for invalid log level, and level otherwise. Harness Functions In addition to the standard library functions, you will implement testing harness functions (also in the library code). The testing harness functions are used to verify security of the system calls from the system library (and are required for full credit on this assignment). We will call these functions to retrieve the information needed to make a system call. We will then call the system call within our own program. This ensures that no security checks are being done in the user-level library. System call parameter retrieval data should be returned as a pointer to an int array of 2-4 values that can be used to make the system call (which can be cast from other types). It has this format: { call_number, num_parameters [, parameter1] [, parameter2] } e.g.: { 42, 2, 867, 5309 } → syscall(42, 867, 5309) Figure 2: Harness functions can directly invoke system calls without the library functions. These test harness elements must be implemented as part of your library to test your security model: #define PROC_LOG_CALL Definition for the system call number of the log-message system call; should be in header. int* retrieve_set_level_params(int new_level) Returns an int array of 2-4 values that can be used to make the set-process-log-level system call. int* retrieve_get_level_params() Returns an int array of 2-4 values that can be used to make the get-process-log-level system call. int interpret_set_level_result(int ret_value) After making the system call, we will pass the syscall return value to this function call. It should return set_proc_log_level’s interpretation of the system call completing with return value ret_value. int interpret_get_level_result(int ret_value) After making the system call, we will pass the syscall return value to this function call. It should return get_proc_log_level’s interpretation of the system call completing with return value ret_value. int interpret_log_message_result(int ret_value) After making the system call, we will pass the syscall return value to this function call. It should return proc_log_message’s interpretation of the system call completing with return value ret_value. Note that there is no retrieve function for log_message as its system call format is defined above. Submissions You will submit the following at the end of this project (3 separate files): ● Text file (screencast.txt) containing link to unlisted screencast video ● Kernel Patch File (p1.diff) on Canvas ● Compressed tar archive (process_log.tar.gz) for process_log library on Canvas Screencast You will record a screencast (with audio) walking through the changes made to the kernel to create the system calls. As you explain something, you should be showing the corresponding file/code. You will upload the recording as an unlisted YouTube video and submit a text file containing a link to this video. Your screencast should: • Show each modified kernel file, explaining the changes you made to each and their importance in creating the system calls. • Show and explain how the system-wide process log level was implemented. • Show and explain how the executable name and pid were acquired. • Show and explain how sudo user was checked. • Show and explain how process message logging was implemented. • Show all your library code and explain how the system calls were used by the library. • Mention (you don’t have to show) testing patch file in clean kernel. • Demo library functionality by starting with process_log.tar.gz and following the commands given in the Compressed Archive section to compile and run library_test.cpp and harness_test.cpp • Be at most 5 minutes long. (Audio speed-up is prohibited) Patch File The patch file will include all changes to all kernel files in a single patch. Applying the patches and remaking the necessary parts of Reptilian, then rebooting and then building the test code (which we will also copy over) should compile the test program. Your project will be tested by applying the patch while in /usr/rep/src/reptilian-kernel: $ git apply p1.diff $ make && sudo make install && sudo make modules_install Compressed Archive (process_log.tar.gz) Your compressed tar file should have the following directory/file structure: process_log.tar.gz process_log (directory) process_log.h Makefile (Other source files) To build the library, we will execute these commands (from a non-kernel-source directory): $ tar zxvf process_log.tar.gz $ cd process_log $ make $ cd .. To link against the library, we will execute this command: $ cc -o program_name sourcefile.c -L ./process_log -lprocess_log Please test your library build and linking before submission! If your library does not compile it will result in zero credit (0, none, goose-egg) for the library portion of the project.
Overview You will add a kernel boot log message to Reptilian. You will then take a screenshot of the terminal displaying the added boot message with your name/UFID and a personal message visible and create a short video to demonstrate your code. You’ll submit the project via Canvas. Structure The project is broken into four main parts: 1) Modify the kernel to print your name, UFID, and a personal message to the default boot (and rebuild). 2) Take a screenshot displaying your name and UFID in the debug boot message 3) Create a unified patch file The system must print “##### FirstName LastName (UFID: 0000-0000) My Personal Message #####” using the log system with one new line above and below (while booting with the default configuration) just before the message “Detecting Reptilian system partition”. The personal message can be appropriate message you like (see example screenshots). It can be added in source near the call to the rcu_end_inkernel_boot() function, which wraps up the kernel’s boot tasks and hands off execution to the system initialization routines. For extra credit (+4%), students may modify the GRUB menu to add “(FirstName LastName)” next to the default “Reptilian 20.08-A9.0-r2” option; see the Example Screenshots section below for an example of what the modified menu should look like. This will not be included in the patch; just take a screenshot and talk about what you did in the report and screencast. Note that the GRUB utilities cannot be used for this – just a text editor. Log Levels Many systems use level-based log systems. The Linux kernel has eight (8) levels that are used for log messages. Anything less severe than the KERN_ERR log level will only show up on the screen in verbose or debug mode. Testing You should test your code by starting your VM after rebuilding. Make sure it displays your message while booting in default mode (not verbose or debug). You should also apply your patch to a “clean” VM to make sure it works. Submissions You will submit the following at the end of this project on Canvas (Do NOT zip files): Screenshot of added log message with name & UFID visible (plus screenshot of GRUB if doing EC) Report containing link to unlisted screencast Unified Patch File Report Your report will explain how you modified the boot message, including what changes were made to which files and why each change was made. It will include description of how testing was performed. It will also contain a link to an unlisted web resource for the screencast (such as a YouTube video link). It should be named “p0.txt” and should be no more than 500 words. You must include your name on the report. It should cover all relevant aspects of the project and be organized and formatted professionally – this is not a memo! Screencast You should submit a screencast (with audio) walking through the changes you make to the operating system (~2 minutes) as part of the report (see “Report”). Audio speed-up is prohibited. The video must be unlisted! Patch File The patch file will include all changes to all files in a single patch. Applying the patches and remaking the necessary parts of Reptilian, then rebooting should modify the boot message as described above. To create the patch file follow these commands: $ cd /usr/rep/src/reptilian-kernel $ git add -u $ git add ‘*.c’ ‘*.h’ ‘*Makefile*’ ‘*.tbl’ $ git diff remotes/origin/os-latest > p0.diff This is merely an example that includes specific file types; you will need to ensure that all of your changes appear in patch files you generate and submit for this course. Always test your patches! We will test your project applying the patch and running these commands from the kernel source directory: $ git apply p0.diff $ make && sudo make install && sudo make modules_install Example Screenshots Below you can see an example of what acceptable screenshots look like for the project and the extra credit (You don’t need to circle what you added): Figure 1. Added Boot Message Figure 2. Modified GRUB Menu (Extra Credit)
Overview The aim of this exercise is to get you familiar with the socket programming in Linux. (This applies to any other variants of Linux systems). Sockets are endpoints of a two- way communication between two programs running on machines connected via a network. A TCP socket is bound to an IP and port number. To read more on sockets refer to: https://en.wikipedia.org/wiki/Network_socket https://docs.oracle.com/javase/tutorial/networking/sockets/definition.html Structure In this exercise, we create simple client and server programs that send messages to each other and display the messages after receiving them. The client and server will run on the same host (Reptilian machine) and use the same port number. 1. Write a client file that takes the port number as an argument. (ex: ./client 1234) 2. Write a server file that takes the port number as an argument. (ex: ./server 1234) 3. Start the server. (Start the server first as this is the one that’s accepting connections) 4. Open a new Reptilian terminal and start the client (same port that server is listening to) 5. As soon as the client connects, it and the server send their messages to each other. 6. The client and server receive each other’s messages and print them. Note: You might have some issues connecting to localhost, that’s expected, good luck! Expected Output A Client sends a message: “: ”, the server should read that and print it. The Server sends this message: “Welcome to the server running on REPTILIAN”, the client should read that and print it. Submission You will submit the following at the end of this exercise: • A screenshot showing the client being started and its output after connecting (client.png) • A screenshot showing the server being started and its output after connecting (server.png) • Your client source code (client.cpp) • Your server source code (server.cpp) All parts of the exercise must be completed in Reptilian.
Overview This exercise serves as a brief introduction to TCP servers and the network toolset. In this activity, you will create a “wall” application, in which a single user can connect in order to “tag” (leave a message on) the wall. Wall programs were common in the days of Bulletin Board Systems (BBSs) before other Internet services became popular. As connections were made via telephone hardline dial-up, only one user could connect at a time, so the “wall” program served as a community board: As text mode screens are generally 25 rows by 80 columns, wall messages should not exceed a certain length, otherwise the wall will look ugly! Users should be told what the maximum message length is, and messages longer than this should be rejected. Additionally, a limited number of messages can be displayed on the wall; when the wall is full, the oldest message is removed from the message queue, and the new message is added to the end (FIFO). The server and client must communicate through a TCP socket (in C or C++) and must compile and run on Reptilian. The wall’s state should be maintained even between connections. The netcat command line utility should be used to test the server. Specification Your server will run as a standalone program from the command line and will use the protocol specified below. Command Line Execution The server program will take up to two parameters, optionally – the maximum number of messages stored and the port. If not provided, the port should default to 5514, while the number of messages should default to 20: $ ./wallserver $ ./wallserver 30 $ ./wallserver 35 7777 Server Behavior When a client connects, the server should send the wall’s contents and a prompt as shown below (Figure 2a). If there are no message entries, it should instead send “[NO MESSAGES – WALL EMPTY]” (Figure 2b). Wall Contents ————- Ted: Iron Maiden? Bill: Excellent! Liz: Look! I am a human doing human things! Just a completely normal human being Figure 1. Example of a wall program’s contents Wall Contents ————- Ted: Iron Maiden? Bill: Excellent! Liz: Look! I am a human doing human things! Enter command: _ Figure 2a. Wall display with contents. Wall Contents ————- [NO MESSAGES – WALL EMPTY] Enter command: _ Figure 2b. Wall display without contents. Queue size 20, Port 5514 Queue size 30, Port 5514 Queue size 35, Port 7777 The server will accept four distinct commands – clear, post, kill, and quit. For commands that do not cause the user to disconnect (clear and post), after processing the command, the server should display the wall’s contents and prompt the user for an additional command, as shown in the examples below. clear Removes all messages on the wall. In addition, the server should send a message indicating that the wall has been cleared. Note that the server still displays the wall’s contents after clearing. post Indicates the user wishes to tag the wall. The user should be prompted for their name and then their message. The entire post must not exceed 80 characters (including name and separator), so the maximum length of the message will be indicated to the user. If the message is too long, the server should display the message “Error: message is too long!”; otherwise, it should display “Successfully tagged the wall.” If the wall is full, the oldest message (at the top) should be removed from the wall to make room for the new message. An example (with queue size 2) is shown on the right. kill Causes the server to shut down (terminate), and close the socket, disconnecting the user. quit Displays a termination message and closes the client’s socket, but does not shut down the server or clear the wall. Debugging It is recommended that students debug their server using the netcat command line utility (with alias nc). To do so, run your server in one ssh session, then open another and run netcat: Wall Contents ————- Jimmy Dean: Try my breakfast delights! Enter command: post↵ Enter name: ~~~~~[[[[[[[[[[[THE PLAGUE]]]]]]]]]]]~~~~~↵ Post [Max length 36]: 12345678901234567890123456789012345678↵ Error: message is too long! Enter command: _ Enter command: clear↵ Wall cleared. Wall Contents ————- [NO MESSAGES – WALL EMPTY] Enter command: _ Enter command: kill↵ Closing socket and terminating server. Bye! $ _ Enter command: quit↵ Come back soon. Bye! $ _ $ ./wallserver 2↵ Wall server running on port 5514 with queue size 2. $ netcat localhost 5514 ↵ Wall Contents ————- Pigeon: You’ve got mail. Err, I mean, cooo. Coooo. Enter command: quit↵ Come back soon. Bye! $ _ Wall Contents ————- Jimmy Dean: Try my breakfast delights! Enter command: post↵ Enter name: Johnny S↵ Post [Max length 70]: I’m alive!!!↵ Successfully tagged the wall. Wall Contents ————- Jimmy Dean: Try my breakfast delights! Johhny S: I’m alive!! Enter command: post↵ Enter name: Bobo↵ Post [Max length 74]: Hullo.↵ Successfully tagged the wall. Wall Contents ————- Johhny S: I’m alive!! Bobo: Hullo. Enter command: _ Submissions You will submit the following at the end of this exercise: ⚫ Screenshots demonstrating your server’s functionality (func1.png, func2.png) ⚫ Compressed tar archive containing server source code and Makefile (ex8.tar.gz) Screenshots In Reptilian, do the following: 1) Start the server with a message queue size of 2 2) Connect to the server using netcat 3) Post three messages 4) Take a screenshot of steps 1-3, name it “func1.png” 5) Clear the server’s wall 6) Post one message 7) Attempt to post a message that fails due to being too long 8) Quit from the server 9) Reconnect to the server 10) Kill the server 11) Attempt to connect again to show that the server has terminated 12) Take a screenshot of steps 5-11 (include wall contents from before step 5), name it “func2.png” Compressed Archive (ex8.tar.gz) Your compressed tar file should have the following directory/file structure: ex8.tar.gz ex8 (directory) Makefile (Server source files) To build the server program and run it, we will execute these commands: $ tar zxvf ex8.tar.gz $ cd ex8 $ make $ ./wallserver [lines] [port] Resources https://linux.die.net/man/2/socket – documentation for a function that you’ll be getting comfortable with https://www.unixfu.ch/use-netcat-instead-of-telnet/ – an http example using netcat https://linuxhandbook.com/jobs-command/ – as an alternative to opening multiple terminals, you can keep the server running in the background by learning how to manage jobs (not necessary to complete the exercise, but may be interesting to students that like working in the terminal)
Overview The aim of this exercise is to familiarize you with pipes in Linux. Pipes are a common form of interprocess communication. Structure The assignment is broken into three main parts. In each part, you will learn about a different way to implement pipes. The three parts are as follows: 1. Basic Pipes 2. Named Pipes 3. Pipe System Call Part 1: Basic Pipes Basic pipes can be created in the terminal by placing the “|” operator between commands. Using “|” causes the output of the left command to be piped in as the input to the right command. For example, running “cat result.txt | grep -o “COP4600″ | wc -l” would return the number of times that the pattern “COP4600” is found in result.txt. The contents of the file are being piped into the grep command which then passed any matches into the wc command. The “wc -l” option returns the number of newlines which, in this case, equals the number of occurrences of the pattern. For this part, an executable file named “part1.o” is provided via Canvas. When run, the executable will perform basic operations until it encounters a failure. The amount of successful operations completed before failing will vary. Here is a sample output of this program: You may need to give part1.o executable permissions using “sudo chmod +x ./part1.o”. Your task is to create a C++ program that, when the output of “part1.o” is piped in, determines which operation number caused the failure. For example, your program would print “Program failed on operation 12.” if it were run with the information from the above screenshot. For this part you will need to submit a screenshot that shows your code successfully running twice with input provided by “part1.o” through a basic pipe. Part 2: Named Pipes Named pipes, also known as FIFOs (first-in first-out), are functionally similar to basic pipes except they are represented as a special file and are, therefore, a non-temporary part of the filesystem. A FIFO can be created using the “mkfifo [name]” command (similar to mkdir). A FIFO does not store the communicated data in the file system and only acts as a reference point for processes to establish a connection. Because of this, when a writer process opens the FIFO, it will block until a reader process opens the other end. Utilizing named pipes through the command line, therefore, will likely require multiple terminal windows. For this part, implement the following: 1. Create a named pipe. 2. Modify your part 1 C++ code to read its input from a file (your named pipe). This program should be named “lastname_part2.cpp” where “lastname” is your last name. 3. Run “part1.o” and redirect its output into the named pipe. 4. Compile and run your part 2 program (input should not be redirected from the command line). 5. Repeat steps 3 and 4 then take a screenshot that shows the programs running to completion twice. Be sure to include all terminal windows that were used. Part 3: Pipe System Call Both piping methods used above have required some form of post-compile time actions (i.e. redirecting output or creating a named pipe). In many cases, this may be a drawback. To set up a pipe entirely within the process’ code, the pipe system call can be used. For this part you will use the “fork()” and “pipe()” system calls to implement the following: 1. Create a new C++ program named “_part3.cpp” filling in with your last name. The program should accept 5 command-line arguments (all integers). 2. The program must create two new child processes and utilize four pipes. 3. The parent process will send the 5 integers to the first child process using a pipe. This child will sort the integers and send the result to the parent process and the second child process using one pipe for each. The parent will print the result. 4. After receiving the sorted list from the first child process, the second child process will identify the median value of the list and send the result to the parent using a pipe. The parent will print the result. 5. Take a screenshot of the program running with the following integers passed in as command-line arguments (in the specified order): 42, 15, 8, 16, and 23. Submissions You will submit the following at the end of this exercise on Canvas: ⚫ Screenshot of the output from running your part 1 program with a basic pipe twice (part1.png) ⚫ Screenshot of the output from running your part 2 program with a named pipe twice (part2.png) ⚫ C++ source file for your part 2 program (lastname_part2.cpp) ⚫ Screenshot of the output from running your part 3 program with the given values (part3.png) ⚫ C++ source file for your part 3 program (lastname_part3.cpp) All parts of the exercise must be completed in Reptilian. Helpful Links https://www.linuxjournal.com/article/2156 https://www.tldp.org/LDP/tlk/ipc/ipc.html http://www.cplusplus.com/doc/tutorial/files/ http://www.gnu.org/software/libc/manual/html_node/Creating-a-Pipe.html http://man7.org/linux/man-pages/man2/pipe.2.html
Overview This exercise should begin to help you understand the Linux File System and how to interact with it. Linux originally used Minix’s file system, but it has gone through four iterations of extended file systems over the course of the kernel’s development, your kernel’s file system is using the ext4 file system (fourth extended file system). In Unix-based systems (like Linux) and many other operating systems, devices in the system are represented using device files – that is, virtual files present in the virtual filesystem presented by the OS that do not present data records on a storage medium (as traditional files do). Instead, device files act as handles to read from and write to connected devices. These devices are often physical ones – such as solid-state drives, mice, or keyboards – but they can also be virtual devices, which simulate hardware via a software mechanism. In this exercise, you will create and attach a virtual storage drive via a loopback device, which allows a regular file to masquerade as a device… which will then to represented using a virtual file (Unix be cray like that). Loopback devices are commonly used on Unix systems, especially for creating, reading, and writing storage images (such disc images, i.e. “ISOs”). You’ll connect the storage, mount it, write to it, unmount it, and then verify that the data has been written. Mouse Joystick SSD Virtual Filesystem Drivers /dev/input/mouse0 /dev/input/js0 /dev/block/sda File2.txt Image File Device File /mnt/ex File1.txt 6 Loopback Device Structure The exercise is broken into these main parts: 1) Create a storage device image file. 2) Connect the file to a loopback device, format it, and mount a filesystem on the device. 3) Write data to the virtual device by creating files on it after mounting 4) Unmount the virtual device and disconnect the loopback device 5) Verify the data has been written to the image file Creating the Image Follow these steps to complete the exercise: 1. Create an ex6.img file, filled with zeroes, of size one mebibyte (1 MiB) using dd: $ dd if= of= bs= count= The dd command’s input can come from any source, a regular file or a special (device) file. A special file, /dev/zero, will have an infinite number of zeroes available for reading. The output data’s size is defined by the block-size and block-count – you could create a 1KiB file by using a size of 512 and a count of 2, for example. 2. Create a loopback device connected to the image file using losetup, format the image in ext4 format using mkfs, and then mount the loopback device on /mnt/ex6 via mount. Take a screenshot of the commands you used in this step. 1. You will need to use sudo for the losetup command. 3. In this step you will be writing data to the virtual device by creating files on it after mounting. In the mounted directory (/mnt/ex6), create two text files: 1. one empty, 2. and one containing a message. Display the contents of each file using the cat command and take a screenshot. 4. Unmount the filesystem (umount) and disconnect the loopback device (losetup). 5. Lastly, you need to verify if the data has been written to the image file. Install hexedit (sudo apt-get install hexedit) and use it to examine the image – you should be able to find your filenames and text. Take a screenshot of the file text. Just for fun: try the strings command and see what happens! Submissions You will submit the following at the end of this exercise: ⚫ Screenshot of loopback setup, formatting, and mounting of the image file (step2.png) ⚫ Screenshot of the text files’ contents (using cat) in the mounted directory (step3.png) ⚫ Screenshot of image file in the hexedit program showing your file text (step5.png)
Overview The aim of this exercise is to familiarize you with multithreading in C++. In the right situation, threads can significantly speed up your programs by allowing parts of it to run concurrently rather than sequentially. Here is a simple example: Note the use of the join() function above. Without it, it would be possible for the main function to finish executing and exit before the thread has completed execution. Structure To complete this exercise, you will be writing a program that spawns 10 threads, each of which will attempt to do the same job. Due to the nature of threads, you’ll notice that they finish in a different order every time. Your program must not block for any reason. 1. Write a C++ program that takes an integer as a command-line argument (i.e. ./threads 1414). Your program must accept exactly one argument. You may assume that any argument passed to your program will be valid (no input validation needed). 2. Write a function inside this program with two integer parameters: an ID number and a target. a. This function will generate random integers between 0 and 9999 until it generates one that matches the target number, then print “Thread completed.” 3. In your program’s main function, spawn 10 threads, each of which will call your new function with a unique ID (0 through 9) and the number given as a command-line argument as the target. Note: Your threads must be spawned inside of a loop. You should NOT have 10 individual calls to std::thread() in your program. 4. Finally, once all of your threads have finished generating numbers, print “All threads have finished finding numbers.” Note: To compile your program with multithreading, use the following command (this is how we will build your submission): g++ threads.cpp -o ex5.out -pthread -std=c++11 Enabling Race Conditions To ensure that the threads finish executing in a random order, you can use the nice utility. nice is a program that allows setting or altering the priority of a process. You should give your process the lowest priority to ensure that the CPU will execute it less often. In addition, you should lower your virtual machine’s memory and maximize the number of cores. This will slow the process down and cause the threads to execute out of order due to the interruptions and race conditions. Read about nice here: https://man7.org/linux/man-pages/man1/nice.1.html Note: RAM and CPU settings differ depending on your machine. You should give your virtual machine at least 512 MB. Submissions You will submit the following at the end of this exercise on Canvas: ⚫ C++ source file for your program (threads.cpp) ⚫ Screenshot of the output from running your program twice (output.png) Figure 1: An example screenshot with output from running the program twice.
Overview When writing code, particularly for complex systems, it is imperative to continuously check that your work is correct. Unit tests allow developers to write tests that demonstrate that output matches specifications and mitigate the risk that changes in one area of the codebase cause unintended consequences. Structure This exercise is broken into 3 parts: 1. Introduction to GoogleTest. You will build and install the unit testing framework. 2. White box testing. In white box testing, tests are written with full knowledge of the implementation of the system; including knowledge of weak points and access to internal data structures and functions. 3. Black box testing. In black box testing, tests are written with no knowledge of the implementation of the system. Rather than testing internals, tests are written to ensure correct outputs based on a specification. Part 1: Introduction to GoogleTest Installing GoogleTest Before beginning the exercise, you will first install GoogleTest – a unit testing framework for C++. GoogleTest is necessary to complete the remainder of the assignment. You will begin by running the following sequence of commands: sudo apt-get install cmake git clone https://github.com/google/googletest.git -b v1.13.0 cd googletest # Main directory of the cloned repository. mkdir build # Create a directory to hold the build output. cd build cmake .. -DBUILD_GMOCK=OFF # Generate makefile for GoogleTest make sudo make install # Install GoogleTest in /usr/local/ Exercise Files The source files for this exercise can be obtained by running in the home directory git clone https://github.com/utt-zachery/OS-Ex4.git Anatomy of a Unit Test A unit test is a function which verifies the output or value of other code (known as the subject under test). This is achieved through an assertion. An assertion is a statement, which, if false, indicates that the test has failed. Unit tests are compiled along with the subject under test into a testing binary. The testing binary is then executed. As an example, suppose the subject under test is the following function in Factorial.h: int Factorial(int n); Let us consider some simple unit tests for this integer function, written in FactorialTests.cpp. Unit tests in GoogleTest begin with the TEST preprocessor macro. #include “gtest/gtest.h” #include “Factorial.h” TEST(FactorialTest, HandlesZeroInput) { int result = Factorial(0); ASSERT_EQ(result, 1); //Assertion } Tests are organized into a “testing suite” (which simply denote groups of related tests). Here the testing suite name is FactorialTest. When the testing binary is run, the output will be organized by each testing suite. Each test also contains a second field denoting the name of the test. Here the testing suite name is HandlesZeroInput. Fields must be valid C++ function name variables (no underscores). The body of the test contains some code followed with an assertion. The test will pass if all assertions in the body pass. You will not write a main entry point for your testing binary. Instead, you will link with the GoogleTest library which includes one for you. We’ve already built a Makefile for this test program. To run this sample test, simply navigate to the “Part 1” folder and run the commands make ./test.out Results of running the testing binary Part 2: White box Testing In this part of the exercise, you will be writing tests for the following function, whose implementation you are given: //Returns true if a divides b //Otherwise, returns false bool isDivisible(int a, int b) { return (b % a == 0); } A significant challenge when writing tests is deciding how many tests are needed. Since we can’t test every integer, we will have to test a few values that represent the functionality of the whole system. For this exercise you will write the following tests inside DivisibilityTests.cpp: 1. A is positive, B is positive, and A does divide B. The function should return true. 2. A is positive, B is positive, and A does not divide B. The function should return false. 3. A is positive, B is zero. The function should return true. 4. A is negative, B is positive, and A does divide B. The function should return true. Overall, there are 18 total tests that are needed to completely test this simple function! For this assignment, simply write the 4 tests requested. All of your tests should pass. We’ve already built a Makefile for this program. To run your tests, simply navigate to the “Part 2” folder and run the commands make ./test.out Part 3: Black box Testing Often before development of a system begins, tests are first written which demonstrate the specified functionality of the system. In this exercise, you will be writing black box tests for the backend of a simple airplane trip booking system managing flights for a given date. You will not be implementing this system. The architecture of the system is as follows: 1. An Airport is an object consisting of a 3 letter airport code representing a unique airport. 2. A Flight is an object that represents a scheduled flight from one Airport to another. It describes a source Airport, a destination Airport, a departure time (represented as an integer denoting the hour of takeoff in UTC), and a capacity (represented as an integer denoting the remaining seats available for purchase). It is assumed that all flights depart on the same day. 3. A Booking is an object that contains a list of Flight objects. It represents a single flight option to get from a source Airport to a destination Airport. It contains a single Flight object in the case of a direct flight; and two Flight objects in the case of a connection. You will write unit tests for each function provided in BackEnd.h. You will use the provided interfaces to test the following specifications: 1. A query returns all available flight bookings from a source airport to a destination airport. 2. A query will not return any flight booking that includes a full flight. 3. When a flight booking is purchased, the capacities of all flights in the booking should be decremented. 4. A booking either contains a single direct flight from the source airport to the destination airport, or two flights: one from the source airport to a connection airport, and a second from the connection airport to the destination airport. The second flight in a connection must depart at least 2 hours after the first flight’s departure. 5. A query will only return bookings with connections when there are no direct flights from the source airport to the destination airport. 6. If multiple flight bookings are returned by the query, bookings should be ordered by departure time, with the earliest flight first. In the case that a booking is a connection, it is ordered solely based on the departure time of the earlier flight. Note: The “subject under test” (SUT) are the functions in BackEnd.h. Assume that the all the other classes are correct. You may freely use any function you would like in any of the classes provided (including any constructors). Your unit tests will be written in a file called UnitTests.cpp (located in “Part 3” in the exercise source repository cloned in Part 1) which will contain your test definitions. Your unit tests should fully test the specifications of the system. In particular, your unit tests will need to (1) Create Airport instances (2) Create Flight instances (3) Using the objects created in (1) and (2), demonstrate that the booking system produces all correct Booking objects sorted in order when using flightBookingQuery (4) Demonstrate that the booking system correctly processes Booking objects when using purchaseBooking, and that subsequent flightBookingQuery calls adhere to the specification. We have provided a dummy implementation of BackEnd.cpp so you can verify that your tests properly compile, link, and execute. Of course, many of your tests should fail since the dummy version of BackEnd.cpp does not adhere to the specification. We will grade the quality of your tests by recompiling your tests on different implementations of BackEnd.cpp! Some of these implementations are correct; some are incorrect. Your unit tests should all pass on the proper implementation; and at least one test should fail on the incorrect implementations. You must write enough unit tests to completely cover all items of the specification. When writing your unit tests, you must not assume anything that is not stated in the specification. You may only modify UnitTests.cpp. Assume that all inputs to the functions in BackEnd.cpp are valid (i.e. do not test passing invalid strings or nullptr). Your tests must be fully automated (must run with no command line args/user input). We’ve already built a Makefile for this program. To run your tests, simply navigate to the “Part 3” folder and run the commands make ./test.out Submissions You will submit the following files for this assignment: Part 1: Nothing Part 2: • A screenshot showing the execution of your tests (Part2.png) • The source file containing your unit tests (DivisibilityTests.cpp) Part 3: • The source file containing your unit tests (UnitTests.cpp)
Overview In this exercise you will learn about patches, libraries and Makefiles. You will first modify the patch you created for Project 0. You will then create a static library that will perform a simple arithmetic operation and finally you will create a Makefile to compile that library. Structure The project is broken into three main parts: 1) Modify the patch file from P0. 2) Create a static library. 3) Create a Makefile to re-compile your library. Patch Files A patch file is a text file that contains instructions on how to update other files. In Project 0 you modified a certain file to add your name to the boot message. You then rebuilt the kernel and saw that your changes were applied successfully (hopefully)! Finally, you created a patch that contained all the changes. In other words, the patch contained the differences between your modified source and the original clean source you downloaded. You can read more about patch files here: https://www.git-tower.com/learn/git/ebook/en/command-line/advanced-topics/diffs. Here’s an example patch file: The first 5 lines specify which file to modify. The remainder indicates which lines are removed and inserted. When applying this patch file to a clean source of your file system, the patch program will know exactly what to remove and what to add. Patches are useful because they only keep track of changes. (Imagine if you had to export the 1.4 GB Reptilian image and upload it to Canvas every time you had to submit something!) For this exercise you will need to do the following: 1. Create a copy of your P0 patch and modify it in a text editor to remove the message you added in P0 and insert a new one that says “### First Last Name (Exercise 2) ###”. NOTE: You will apply the patch to the kernel source that already contains the changes from P0, so the patch file should remove the P0 changes and add the new changes. 2. You will apply the patch by switching to /usr/rep/src/reptilian-kernel and running: $ git apply ex2.diff $ make && sudo make install && sudo make modules_install 3. Take a screenshot of the boot sequence showing the modified message. Libraries Libraries are simply a collection of previously defined declarations and procedures. If we often use the same subroutines, we can create a library and use it across all our projects. For example, we can use a math library to perform matrix multiplication. You can read about different types of libraries here: http://www.hep.wisc.edu/~pinghc/generate_your_own_library.htm In this project you will create a simple static library using the following steps: 1. Create mean.c in /home/reptilian/math (You will need to create the math directory): int mean(int a, int b) { return (a + b) / 2; } 2. Create mean.h in /home/reptilian/math: #pragma once int mean(int a, int b); 3. Compile mean.c and create libmath.a: $ cc -c mean.c $ ar cr libmath.a mean.o 4. Create test.c in /home/reptilian: #include #include “math/mean.h” int main() { printf(“The average between 3 and 5 is %d ”, mean(3, 5)); return 0; } 5. Compile and run test.c: $ cc -o test test.c -L ./math -lmath $ ./test 6. Take a screenshot of the output. Makefiles Makefiles are used to organize code compilation. Earlier in this exercise you manually entered the commands to create your library… but imagine if you had to compile this and 50 other programs! In such a circumstance, Makefiles come in handy. A Makefile contains all the instructions needed to compile programs and can be run with the make command. For this exercise you will create a Makefile in /home/reptilian/math that will compile the library. In addition to compiling your code, Makefiles monitor the time stamps of your source files and only recompile the modules of your code that have changed or depend on modules that have changed. Your Makefile should build only when necessary and should not build if no changes are present. Put simply, your Makefile must include dependencies for each rule! Read about Makefiles here: http://www.cs.colby.edu/maxwell/courses/tutorials/maketutor/ To test it and make sure it works, delete libmath.a and mean.o, then run make. This should re-create libmath.a and mean.o. Then run make again. It should say libmath.a is up to date. Submit the Makefile on Canvas (You can add the “.txt” extension if necessary). Submissions You will submit the following at the end of this exercise: ⚫ Screenshot of the boot message (boot.png) ⚫ The modified patch file (ex2.diff) ⚫ Screenshot of the library output (lib.png) ⚫ Your Makefile
Overview In some cases, systems-level code can be hard to debug; pointer errors can result in hours of hair pulling and endless searching to solve simple issues that are obvious in professional development suites. Thankfully, The GNU Debugger (GDB) is here to rescue you! In this exercise, students will learn about the powerful toolset that GBD You will analyze, deconstruct, and debug given programs to help you learn the necessary skills of using a console debugger that will help you with future projects, and any code that you will write. At the end of the exercise, you’ll submit several annotated screenshots. This exercise should be completed in Reptilian. Structure This exercise will follow this basic structure: 1) Install GDB 9.1 and its utilities 2) Research on how to utilize GDB and its commands, a helpful link will be provided 3) Create a simple program, and play around with GDB’s features 4) Debug process.c and explain the issue encountered / what it was trying to do 5) Analyze password by digging through its code in order to obtain the key Installation (GDB) Within Reptilian, use the apt-get command to update the Linux package list, and install GDB $ sudo apt update $ sudo apt install gdb Test GDB to make sure that it’s the correct version by prompting it: $ gdb -version Your output should look something like this Using the GNU Debugger (GDB) Using the debugger is straightforward. To start up the debugger on a sample program myProgram we would type: $ gdb myProgram From there, we can learn more about GDB and how to use it by keying: (gdb) help We highly suggest you reference the bottom link to the GDB manual, and the help command if you ever get stuck, or want to learn more about its features. Using the debugging tool follows a simple guideline that will be outlined below: • Run the program and analyze what it’s doing • Set up necessary breakpoints, and step through the program • Find the issues utilizing the various tools that GDB offers Running To run the code, simply key in: (gdb) run This will run the code as your normal shell would, except it will point out several helpful debugging hints whenever you compile your program with the “-g” flag. Breaking After running the code, you may choose an address, or function name in which you want to place your breakpoint: (gdb) break main This will place a breakpoint inside the program at the address of main, and from there, you will be able to step through the code, or run whatever code the method contains Stepping The most useful command next to creating breakpoints, stepping allows the user to step through each line of code to find what the outputs are, and what possible issues the code contains: (gdb) step After stepping through the program, you may delete the breakpoints that are not necessary to you (gdb) delete Useful Commands – run – break – step – delete – next – up – down – print – info – quit Application Now that we have learned some basic commands, it’s time to apply our newfound knowledge to debug some programs that you will make, and that we provide Part 1 – Simple Program Create your own “Hello World” program and play around with the capabilities of GDB. When you’re done, take a screenshot of your program being run in GDB with a breakpoint being set in main. Run the program to completion. This means that your screenshot will show the return code/message from gdb. Compiling your program uses these commands: $ gcc -o myProggy.o myProggy.c $ gcc -g -o myProggy.o myProggy.c Part 2 – Process Table Download the process.c code from the source folder of the exercise and compile it with the commands given at the bottom of this page. This program emulates a (very) rudimentary process table, however, there’s a catch. Inside the program is a bug, and you must use the GDB to find the issue. When you’re done, you’re going to take a screenshot of the issue in GDB, explain why it broke the code (in a canvas submission comment), fix the code (only one line), and submit another screenshot of the working code’s output. To compile process.c: $ gcc -w -g -o process process.c -lpthread -lrt Part 3 – Password Download the source file password from the same folder as process.c. As you will notice, this file is an output, and it was compiled without debugging symbols. In order to complete this part, you will need to use GDB to find a password that is hidden WITHIN the program itself (you should start by decompiling that code). Look into the info of the program to see what it contains. See if you can track its motion through compilation. You will take a screenshot of where you found the password before decoding it, and the message received after typing in the correct password. Hint: Use a HEX translator, like the one provided at the bottom of the page Submissions You will submit the following files for this assignment: Part 1: • A screenshot of your program being run to completion with a breakpoint set in main (breakpoint.png) Part 2: • A screenshot of the issue in GDB (gdb.png) • A screenshot of the output of the code after it was fixed (output1.png) • A comment on the canvas submission explaining what the issue was Part 3: • A screenshot of where you found the password (password.png) • A screenshot of the output after putting in the password (output2.png) Helpful Links https://ftp.gnu.org/old-gnu/Manuals/gdb/html_node/gdb_toc.html https://darkdust.net/files/GDB%20Cheat%20Sheet.pdf https://www.rapidtables.com/convert/number/hex-to-ascii.html
Overview You will learn about Linux terminal commands that will greatly help you in this class. If you are an experienced user in terminal commands or command line navigation, this exercise will just serve as a refresher. You will take a screenshot of some commands that you use, and you will also submit a tar file to Canvas for this assignment. File Packaging There are many times that you will find yourself needing to package or compress (or unpackage and decompress) files while working on projects. TAR (originally Tape Archive – packs / creates an archive) and Gzip (GNU zip) are two commonly used tools in Unix based operating systems. To familiarize yourself with these commands and how they work, complete the following and take a screenshot: 1) Create a file (e.g., “somefile.txt”) using a text editor (e.g. nano) 2) Use gzip to compress the file, yielding a gzipped file (“somefile.txt.gz”) 3) Use gunzip to decompress the file, yielding the original file (“somefile.txt”) 4) Create a second file (“other.txt”) 5) Create an archive from both files (“somefile.txt” & “other.txt”), yielding “myfiles.tar” (tar -cvf) 6) Extract the files from the archive (tar -xvf) 7) Create a new file (“somefile2.txt”) 8) Create an archive file from all three text files piped through gzip to create a “.tar.gz” (tar -zcvf) 9) Type “ls” to view the current directory and your “.tar.gz” 10) Unzip and Extract the “.tar.gz” (tar -xzvf) 11) Type “ls” to view the current directory and your extracted file. 12) Take a screenshot of the commands run in steps 7) through 11). Once finished you should have extracted readable content from the “.tar.gz”. You will use these tools to package and compress files that you will submit for projects, so make sure you understand how they work! Terminal Navigation The navigation exercise can be completed by following these steps, including taking two screenshots (see step 4): 1) Create a directory with the name format last_first (e.g., “sanchez_richard”) in /home/reptilian. 2) Issue a command to find files that contain the phrase “android_dev” from the kernel source directory. 3) Reissue the command from (2); this time, pipe the output of the command to a file named “output.txt”. 4) Take a screenshot after running ‘ls’ on the parent directory of the file you found from (2). 5) Take a screenshot of the command and its result from (3). 6) Move or copy “output.txt” into the directory created in (1). 7) From /home/reptilian, create a tar file named ex1.tar of the directory from (1) (including contents). 8) Use gzip to compress ex1.tar (yielding ex1.tar.gz). 9) Create “ex1.txt” with man formatting, describing steps 1-8, using a text editor (e.g. nano). (Check out the links below) 10) From your local command line, use sftp to transfer the files created in (8) and (9) back to your local host. 11) Submit ex1.tar.gz, ex1.txt, and your three screenshots on Canvas. https://liw.fi/manpages/ https://www.linux.com/news/what-you-need-know-write-man-pages/ Package Installation Sometimes you’ll need to install new packages from within a Linux system. On Debian-derived distributions, you can use the apt command for this. Here an example to install the man utility: $ sudo apt install man Once installed, you can use man to view manual pages. Man File You will write a man file for this exercise. After you write it, run this command to confirm the file is viewable using the man utility: $ man ./example.man On Canvas, see Files > Exercises > Ex1 > man_page.txt for an example of how your man file should be formatted and submitted. Once you are satisfied with the man file content, copy the text to a text file for submission by running the cat command and redirecting standard output: $ cat example.man > example.txt File Transfer You will need to use the local Unix shell (on Windows, via WSL or MSYS) to execute the sftp command in order to transfer files from the virtual machine to the local host: $ sftp [email protected] Once connected, you can issue the “help” command from within sftp for more information. Submissions You will submit the following five items at the end of this exercise on Canvas: ⚫ One screenshot of the commands from steps 7-11 in “File Packaging” ⚫ Two screenshots from steps 4 and 5 in “Terminal Navigation” ⚫ Compressed tar file of the created directory and files ⚫ Manual page in “man” format (with markup) Replace with VM IP address Command Line Cheat Sheet Shell Specific cd DIRECTORY changes to specified directory Examples (from /home/) cd reptilian changes to /home/reptilian cd .. changes to parent directory (/) cd ~ changes to user’s home directory (/home/reptilian/) There is no man page for cd because it is built into the command shell. General Commands If you are confused about how a command works, you can view the manual page with the man command: man COMMAND display the manual for the specified command Example man man displays the manual for the man command The following commands have man pages that will provide more information and correct syntax: ls Lists all of the files located in the current directory. clear Clears the terminal. Use this if your terminal becomes cluttered. mv Move a file or folder from one location to another. Can also be used to rename files cp Copy a file or folder to a different location. mkdir Creates directory. rmdir Removes directory. rm Removes file(s). locate Find a file within your OS. tar Zip or unzip files via command line. grep Searches files in plain-text for a matching expression. gzip Compress a file using the gzip compression routine find Locates files. pwd Prints the absolute location of the current directory. nano Brings up text editor for file creation or file editing.
Overview Lots of applications need to process images in some way. Load them, store them, write them back out to files, scale them, rotate them, adjust the color in part (or all) of the image, etc. The purpose of this assignment is to show you how you can perform some of these operations on a particular type of file. You will be writing a program that does the following: • Read in a number .TGA files in a binary format • Process the image data store within those files in a variety of ways • Write out new .TGA files in the same binary format Reading binary data Binary file operations are about two things: reading bytes from the file and putting them into memory, or writing bytes from memory directly to the file. There is no conversion, no interpretation, and no converting strings to numbers or vice-versa. It’s just bytes from the file to memory, or bytes from memory to the file. Whether the data is simple or complex, it’s all just a series of these byte-copying operations. Refer back to the presentation BinaryFileIO on Canvas for a more detailed explanation on how to read and write binary data. Viewing TGA files Some operating systems won’t let you open TGA files natively (thanks Windows), so you will need to install some sort of viewer for them. If you already have a tool installed that lets you open and view these, great. Note: Not having a way of viewing these files will NOT stop you from writing code to open/read/write TGA files, it just means you can’t open the file in an application to view its contents, which will make it a bit more difficult to understand the process you are working with. Here are some tools you can install to view TGA files: Photoshop (CC or Elements, both have free trials) https://www.adobe.com/products/photoshop.html https://www.adobe.com/products/photoshop-elements.html GIMP (GNU Image Manipulation Program) – a free, open-source alternative to the likes of Photoshop https://www.gimp.org/ TGAViewer – A simple program whose only purpose is to open and view TGA files. http://tgaviewer.com/download.aspx File format description Since binary files are all about bytes, they are typically an unreadable mess to any program (or person) that doesn’t know exactly how the data is structured. In order to read them properly, you must have some sort of blueprint, schematic, or breakdown of how the information is stored. Without this description of the file format, you would just be reading random combinations of bytes attempting to get some useful information out of it—not the most productive process. The TGA file format is a relatively simple format, though it has some options which can get a bit complex in some cases. The purpose of this assignment is not make you a master of this particular image format, so a few shortcuts will be taken (more on those later). First, a quick look at the file format: Image Descriptor ID Length Color Map Type 1 byte Size of the Image ID field Image Type Color map specification 5 bytes across 3 variables Image specification – 10 bytes across 6 variables X-Origin Y-Origin Image Width Image Height Pixel Depth Image Descriptor Is a color map included? Compressed? True Color? Grayscale? 1 byte 1 byte Variable 2 bytes 2 bytes 1 byte Image data Variable length, based on previous values 2 bytes 2 bytes 2 bytes 2 bytes 1 byte 1 byte The good stuff. A number of pixels equal to (Image Width * Image Height) Y-Origin – 0 in our case Image Width Image Height X-Origin – 0 in our case FILE HEADER ENDS, IMAGE DATA BEGINS FILE HEADER BEGINS, 18 BYTES TOTAL Pixel depth – typically 8, 16, 24 or 32 OPTIONAL FOOTER DATA BEGINS (UNUSED IN THIS ASSIGNMENT) Color Map Origin – 0 in our case Color Map Length – 0 in our case Color Map Depth – 0 in our case So to start, there is a header. Every file format is potentially different, but In a TGA file the header data takes up 18 bytes total, across a number of variables, and this information describes the rest of the file. Depending on the specifics of the file (or your scenario), some of those variables may have a value of zero, or they may be ignored. (In the case of the TGA format some of the values in the header were once very important, but nowadays are not used—the format still has them for compatibility reasons.) FOR THIS ASSIGNMENT: the files you work with will be 24-bit true color, uncompressed images. What you need from this header are two things: The width of the image, and the height of the image. From the header description, the image width and image height are at a 12 byte offset and 14 byte offset, respectively, from the beginning of the file. You may find it helpful to (especially as practice) to read each piece of data in the header into a structure. Then, once the header has been completely read, you can go about using it for whatever purposes you have in mind. A structure for the header in this case might look like this: struct Header { char idLength; char colorMapType; char dataTypeCode; short colorMapOrigin; short colorMapLength; char colorMapDepth; short xOrigin; short yOrigin; short width; short height; char bitsPerPixel; char imageDescriptor; }; // Something like this… Header headerObject; file.read(&headerObject.idLength, sizeof(headerObject.idLength)); file.read(&headerObject.colorMapType, sizeof(headerObject.colorMapType)); Sample file header output Color Data After the header is the really important part, the image data itself. In a .TGA file the image data is stored in a contiguous block of pixels equal to ImageWidth * ImageHeight. The contents of a single pixel can vary depending on the properties of the file, but for this assignment we are using images with 24-bit color. This means that each pixel would contain: 1 byte (8-bits) for red data, 1 byte (8-bits) for green data, 1 byte (8-bits) for blue data Each of those bytes will contain a value from 0-255, which makes unsigned char the perfect data type to store them. So if a file had a size of 200×300, it would contain 60000 pixels, each of which contains 3 bytes of data, like this: You could store that data in a single array of bytes 180000 elements long, create some Pixel structure which contains 3 bytes, and then make an array or a vector of 60000 Pixels, etc. Often, when talking about color, we describe them in RGB order—red, green, and blue. However… IMPORTANT NOTE: In a .TGA file, the colors are stored in reverse order, such that the first byte is the blue component, the second byte is the green component, and the third byte is the red component. What about the order of the pixels themselves? In many image files (including .TGA files), the first pixel in the file represents the BOTTOM LEFT corner of the image. The last pixel represents the TOP RIGHT corner of the image. If you read, store, and write the pixel data in the same order, you don’t really have to worry too much about this. If you wanted to copy data into a particular part of the image, however… that can be a bit tricky. For example, to copy some 2×2 image into the top left corner would require you change pixels 16, 17, 24, and 25. red green blue [0] red green blue [1] red green blue 59999 … 0 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 Layout of an 8×4 image So, to summarize: The file contains a header, which is 18 bytes in length. Stored within those 18 bytes are pieces of information describing the image content—the width and height of the image, how the color data is stored, and so on. All you need from the header is the width and the height. However, when writing a file, you should provide ALL the header data, whether you are using it or not. Because of this, you should store this data along with the image data itself. What’s in a pixel? Fundamentally, a pixel (short for picture element) is the smallest unit of data in an image, representing a color at a specific location in the image. (Pixels also can mean a particular element from a display device, but doesn’t matter for this assignment.) A pixel is represented by several components, often red, green, and blue (RGB color), but possibly cyan, magenta, yellow, and black (CMYK color). By changing the values of these 3 or 4 components, you can get any color you like. You may see them stored as floating-point numbers from 0-1, but for this assignment you will treat RGB values as unsigned chararacters, with a value from 0-255. For example: Red: 255 Green: 0 Blue: 0 Red: 95 Green: 41 Blue: 215 Red: 255 Green: 0 Blue: 255 Red: 174 Green: 188 Blue: 206 RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB RGB Every pixel in the file has its own set of Red, Green, and Blue values Storage How to store the TGA file? You would need… • The header. 18 bytes worth of data (even if you really only care about 4 bytes – 2 bytes for width, 2 for height). You will need all 18 bytes of this header data to properly write a .TGA file. • The pixels. A pixel is 3 values: R, G, and B, and each of those is a number from 0-255 (an unsigned char fits this perfectly). You will need a way to store a lot of them; a medium-sized image that’s 512×512 contains 262,144 pixels. That’s just the TGA data. That’s the information that goes in and out of the file. If you were storing this data in a class, and using that class to help read/write the information, you might store additional data to help you with the process. Exactly what that data is, is up to you. Writing a file Writing a .TGA file is a pretty straightforward process. You first write the header to the file, and follow that with the image data. If you have any footer information, you would write that after the image data (footers are NOT used in this assignment). Ramping up To get familiar with this process, see if you can do these exercises: • Load a file, and then write that same file data out with a different name – no changes, just a simple passing of data from a file to memory, and then back to a (different) file. • Open an existing file, assign to all the pixels a single color such as red (255, 0, 0). Save the file. • Open an existing file, fill it with random colors (remember a color is made of multiple channels). • Write some code to create a brand new file from scratch—borrow some header values from an existing file to get started, or create your own. Fill that image with a single color—create an allred, or all-blue image. Image manipulations There are many different ways that you can manipulate an image. Photoshop and similar programs have dozens of different algorithms. The basic concept behind these manipulations is that you have 2 layers, A and B. They get run through an algorithm to generate an output, C. Implementation-wise, each “layer” is an image, each image is made up of some number of pixels, and each pixel has a red, green, and blue component. So ultimately the combinations of A and B involve the combination the red component of the first pixel of A with the red component of the first pixel of B, and the green component of the first pixel of A with the green component of the first pixel of B, (ditto for the blue component), and so on for each pixel, storing the results in the corresponding pixel of some new image, image C. A description of the different blending modes can be found here: http://www.simplefilter.de/en/basics/mixmods.html You will not be implementing all of those blending modes. For this assignment, you will be implementing the Multiply, Subtract, Screen, and Overlay blending modes. In addition, you should be able to modify the individual channels by adding a value to them (such as adding 20 to the red channel, or “adding” -20 to the blue channel), or by scaling them (such as scaling the green channel by 50%). The specific operations you will have to perform are listed below, under the heading Tasks. Calculation tips The pixel data is stored in unsigned char variables, with values from 0-255. When modifying those values, you may go over or under that range, which potentially causes some issues. For example, if you wanted to boost the red of a pixel by 100, and the original value was 200, the final result would be 300, but since the range of the unsigned char is 255, 300 would cause an overflow to 44. Similarly, if you multiplied a value of 140 with a value of 78, the result of 10,920 would be just a tiny bit too large. So what can you do? In some cases, you might need to clamp values. In the case of addition/subtraction, you would clamp to the maximum or minimum values of the data type after the operation… however, to avoid the overflow/underflow issue, you might need to perform the calculation in a data type that can store a larger range (like an integer), then clamp and reassign to another variable afterward. For some operations (like multiplication), they work based on a normalized value, from 0-1. So, you might convert your 0-255 value to a 0-1 value (dividing the original by the maximum), perform the calculation with 0-1 values, and the convert back to the original range afterward (multiplying the 0-1 range by the maximum). You could also just multiply the original two values, and divide the result by 255… you’ve got options, and it’s up to you to decide how best to implement them. Normalizing values is often used because it allows for the creation of formulae which can describe a process which works in any situation, regardless of the specific values. For example you might deal with a color range of 25-172, but by normalizing them to a 0-1 equivalent (which would require a little more work than just dividing by 255 in this case), you can use with in the same sort of formula as anything else. Rounding If you do convert values to and from floats, be aware that you may encounter some floating-point precision issues, and may need to round your values. To do that, simply add 0.5f to the final value before assigning back to an unsigned char variable. Why 0.5? If the result should be 80, but the floating point calculation evaluated to 79.871 or some such, adding 0.5 would bring it up to 80.371, which then gets truncated to 80. If the result should be 80, but the final calculation was as high as 80.4, adding 0.5 would give you 80.9, then truncated to 80. Tasks This assignment is broken into 10 different parts, each of which is worth a small portion of the overall grade (the grading rubric is listed at the end of this document). For each of these tasks you will: 1. Load one or more files from the “input” folder 2. Perform some operation(s) on the loaded file(s) 3. Write the results to a new .TGA file (named part#.tga) in the “output” folder. The “examples” folder has completed versions which you can use to test against your files. If your file is identical to its counterpart in the examples folder, you’re done with that part! For example: Part 1: Load the file “layer1.tga” and “pattern1.tga” (both from the input folder), and blend them together using the Multiply algorithm (“layer1” would be considered the top layer). Save the results as “part1.tga” (in the output folder), and your file should match EXAMPLE_part1.tga (from the examples folder). 1. Use Multiply blending mode to combine “layer1.tga” (top layer) with “pattern1.tga” (bottom). 2. Use the Subtract blending mode to combine “layer2.tga” (top layer) with “car.tga” (bottom layer). This mode subtracts the top layer from the bottom layer. 3. Use the Multiply blending mode to combine “layer1.tga” with “pattern2.tga”, and store the results temporarily. Load the image “text.tga” and, using that as the top layer, combine it with the previous results of layer1/pattern2 using the Screen blending mode. 4. Multiply “layer2.tga” with “circles.tga”, and store it. Load “pattern2.tga” and, using that as the top layer, combine it with the previous result using the Subtract blending mode. 5. Combine “layer1.tga” (as the top layer) with “pattern1.tga” using the Overlay blending mode. 6. Load “car.tga” and add 200 to the green channel. 7. Load “car.tga” and scale (multiply) the red channel by 4, and the blue channel by 0. This will increase the intensity of any red in the image, while negating any blue it may have. 8. Load “car.tga” and write each channel to a separate file: the red channel should be “part8_r.tga”, the green channel should be “part8_g.tga”, and the blue channel should be “part8_b.tga” 9. Load “layer_red.tga”, “layer_green.tga” and “layer_blue.tga”, and combine the three files into one file. The data from “layer_red.tga” is the red channel of the new image, layer_green is green, and layer_blue is blue. 10. Load “text2.tga”, and rotate it 180 degrees, flipping it upside down. This is easier than you think! Try diagramming the data of an image (such as earlier in this document). What would the data look like if you flipped it? Now, how to write some code to accomplish that…? Testing your files For all but the simplest of programs, tests are needed to verify that process was executed correctly. We write code to do things more quickly than we can, whether it’s a single, complex problem, or many smaller problems. Testing should be no different. Why verify something by hand when you can have a program do it for you? (The one small issue… you have to write that program first!) The overall idea of ANY test is the same: Does meet , where the criteria are equal to some value, less than or greater than some value, etc. The tests are always the same. Always. It’s the DATA that can get complex. You might have a class object with 35 different variables (some of which may be complex class objects that have their own dozens of variables, some of which may be complex class objects, etc…), or… maybe just a few integers that need to be compared. When creating tests, think of these things: 1. What are all the pieces of significant data in this scenario? The word SIGNIFICANT is important— sometimes you may have data that can be ignored for tests, while in some cases every single class variable, down to the lowest boolean or character variable must be a match. 2. For each of those significant pieces, are they equal to that of the other object? If A and B both have 8 different variables, is A.variable1 equal to B.variable1? What about A.variable2 and B.variable2, etc. In this assignment you are dealing with image files. The rules of programming have not suddenly changed because of this! The above concepts are still the same. Writing a program to compare data is still the way to do things. Consider the following two images: Left: “True” red—255, 0, 0 Right: 254, 0, 0—a convincing impostor Those two images look the same. They have the same shape, same color, etc. However, they are very, very different. Between the two of these, they have 0 pixels in common! Just looking at them, however, it’s impossible to tell. So we write tests. Comparing a single pixel of that image to the same pixel in the other would reveal that the G and B values (both 0) are equal in each image, but the red values are not. If we want ALL data to be the same for an equality check, that check would fail. Writing Tests How you show the results of a particular test? Imagine this simple scenario: You have two integers, with values of 2 and 4. You pass them to a function called Add(), which adds them and returns the result. How would you test this? What would the code look like? Perhaps something like this: cout
Overview In this project students will develop routines to encode and decode data for images using run-length encoding (RLE). Students will implement encoding and decoding of raw data, conversion between data and strings, and display of information by creating procedures that can be called from within their programs and externally. This project will give students practice with loops, strings, arrays, methods, and type-casting. Run-Length Encoding RLE is a form of lossless compression used in many industry applications, including imaging. It is intended to take advantage of datasets where elements (such as bytes or characters) are repeated several times in a row in certain types of data (such as pixel art in games). Black pixels often appear in long “runs” in some animation frames; instead of representing each black pixel individually, the color is recorded once, following by the number of instances. For example, consider the first row of pixels from the pixel image of a gator (shown in Figure 1). The color black is “0”, and green is “2”: Flat (unencoded) data: 0 0 2 2 2 0 0 0 0 0 0 2 2 0_ Run-length encoded data: 2 0 3 2 6 0 2 2 1 0_. The encoding for the entire image in RLE (in hexadecimal) – width, height, and pixels – is: 1 E |1 6 2 0 3 2 6 0 2 2 2 0 1 2 1 F 1 0 7 2 1 A F 2 1 0 9 2 3 0 1 2 1 0 3 2 6 0 3 2 3 0 8 2 5 0 W/ H/ ——————————————PIXELS———————————————–/ Image Formatting The images are stored in uncompressed / unencoded format natively. In addition, there are a few other rules to make the project more tractable: 1. Images are stored as an array of bytes, with the first two bytes holding image width and height. 2. Pixels will be represented by a number between 0 and 15 (representing 16 unique colors). 3. No run may be longer than 15 pixels; if any pixel runs longer, it should be broken into a new run. For example, the chubby smiley image (Figure 2) would contain the data shown in Figure 3. NOTE: Students do not need to work with the image file format itself – they only need to work with byte sequences and encode or decode them. Information about image formatting is to provide context. Figure 1 – Gator Pixel Image Figure 2 Figure 3 – Data for “Chubby Smiley” Requirements Student programs must present a menu when run in standalone mode and must also implement several methods, defined below, during this assignment. Standalone Mode (Menu) When run as the program driver via the main() method, the program should: 1) Display welcome message 2) Display color test (console_gfx.TEST_RAINBOW) 3) Display the menu 4) Prompt for input Note: for colors to properly display, it is highly recommended that student install the “CS1” theme on the project page if they have not done so. There are five ways to load data into the program that should be provided and four ways the program must be able to display data to the user. Loading a File Accepts a filename from the user and invokes console_gfx.load_file(filename: str): Select a Menu Option: 1 Enter name of file to load: testfiles/uga.gfx Loading the Test Image Loads console_gfx.TEST_IMAGE: Select a Menu Option: 2_ Test image data loaded._ Reading RLE String Reads RLE data from the user in decimal notation with delimiters (smiley example): Select a Menu Option: 3 Enter an RLE string to be decoded: 28:10:6B:10:10B:10:2B:10:12B:10:2B:10:5B:20:11B:10:6B:10 Reading RLE Hex String Reads RLE data from the user in hexadecimal notation without delimiters (smiley example): Select a Menu Option: 4 Enter the hex string holding RLE data: 28106B10AB102B10CB102B105B20BB106B10 RLE decoded length: 66 Reading Flat Data Hex String Reads raw (flat) data from the user in hexadecimal notation (smiley example): Select a Menu Option: 5 Enter the hex string holding flat data: 880bbbbbb0bbbbbbbbbb0bb0bbbbbbbbbbbb0bb0bbbbb00bbbbbbbbbbb0bbbbbb0 Number of runs: 18 Displaying the Image Displays the current image by invoking the console_gfx.display_image(imageData: bytes) method. Displaying the RLE String Converts the current data into a human-readable RLE representation (with delimiters): Select a Menu Option: 7 RLE representation: 28:10:6b:10:10b:10:2b:10:12b:10:2b:10:5b:20:11b:10:6b:10 Note that each entry is 2-3 characters; the length is always in decimal, and the value in hexadecimal! Displaying the RLE Hex Data Converts the current data into RLE hexadecimal representation (without delimiters): Select a Menu Option: 8 RLE hex values: 28106b10ab102b10cb102b105b20bb106b10 Displaying the Flat Hex Data Displays the current raw (flat) data in hexadecimal representation (without delimiters): Select a Menu Option: 9 Flat hex values: 880bbbbbb0bbbbbbbbbb0bb0bbbbbbbbbbbb0bb0bbbbb00bbbbbbbbbbb0bbbbbb0 Module Functions Student modules are required to provide all of the following functions with the defined behaviors. We recommend completing them in the following order: 1. count_runs(flatData: iterable) -> int Returns number of runs of data in an image data set; double this result for length of encoded (RLE) byte array. Ex: count_runs([15, 15, 15, 4, 4, 4, 4, 4, 4]) yields integer 2. 2. to_hex_string(data: iterable) -> str Translates data (RLE or raw) a hexadecimal string (without delimiters). This method can also aid debugging. Ex: to_hex_string([3, 15, 6, 4]) yields string “3f64”. 3. encode_rle(flat_data: iterable) -> bytes Returns encoding (in RLE) of the raw data passed in; used to generate RLE representation of a data. Ex: encode_rle([15,15,15,4,4,4,4,4,4]) yields b’x03x0fx06x04′ (i.e., [3, 15, 6, 4]). 4. get_decoded_length(rle_data: iterable) -> int Returns decompressed size RLE data; used to generate flat data from RLE encoding. (Counterpart to #2) Ex: get_decoded_length([3, 15, 6, 4]) yields integer 9. 5. decode_rle(rle_data: iterable) -> bytes Returns the decoded data set from RLE encoded data. This decompresses RLE data for use. (Inverse of #3) Ex: decode_rle([3, 15, 6, 4]) yields b’x0fx0fx0fx04x04x04x04x04x04′. 6. string_to_data(data_string: str) -> bytes Translates a string in hexadecimal format into byte data (can be raw or RLE). (Inverse of #1) Ex: string_to_data(“3f64”) yields b’x03x0fx06x04′ (i.e., [3, 15, 6, 4]). 7. to_rle_string(rleData: iterable) -> str Translates RLE data into a human-readable representation. For each run, in order, it should display the run length in decimal (1-2 digits); the run value in hexadecimal (1 digit); and a delimiter, ‘:’, between runs. (See examples in standalone section.) Ex: to_rle_string([10, 15, 6, 4]) yields string “10f:64”. 8. string_to_rle(rleString: str) -> bytes Translates a string in human-readable RLE format (with delimiters) into RLE byte data. (Inverse of #7) Ex: string_to_rle(“10f:64”) yields b’x0ax0fx06x04′ (i.e., [10, 15, 6, 4]). Submissions NOTE: Your output must match the example output *exactly*. If it does not, you will not receive full credit for your submission! File: rle_program.py Method: Submit on ZyLabs Do not submit any other files!
Overview In this lab, students will use an external library to create a meme generator library and executable. The purposes of this assignment is to give students practice with setting up, importing, using, and writing libraries in C++. SFML Setup In this assignment, students will import and use SFML (Simple and Fast Multimedia Library). This section describes how to install SFML and integrate it into a project. Installation 1. Download GCC 7.3.0 MinGW (SEH) – 64-bit; decompress into reasonable path (e.g., C:Libraries). 2. Add path (e.g., C:LibrariesSFML-2.5.1) as variable SFML_INSTALL to system variables. 3. Add binary path (e.g., C:LibrariesSFML-2.5.1bin) to PATH system variable. Integration Under the compiler settings, add the following lines to your CMakeLists.txt to integrate SFML into the project: You can add the library to your memer library target by specifying link instructions: Likewise, you can link your memer library to your memeify executable: Use To use SFML, you simply include the appropriate header in your code and use SFML constructs in your project: The Cave-Story.ttf open-source font file has also been provided for this project. set(SFML_DIR “C:/Libraries/SFML-2.5.1/lib/cmake/SFML”) find_package(SFML 2.5 COMPONENTS graphics audio REQUIRED) add_library(memer memer.cpp) target_link_libraries(memer sfml-graphics sfml-audio) add_executable (memeify memeify.cpp) target_link_libraries(memeify memer sfml-graphics sfml-audio) #include Classes There are a few important classes that you will want to read about in the SFML documentation. sf::Image This object is an image in system memory (RAM), stored as a series of pixels. sf::Texture This object represents a read-only version of image data pre-formatted and stored in video memory (VRAM). sf::Font A font for use in SFML routines. Typically loaded from a file. sf::String The SFML native String format. sf::Sprite A drawable class; it references a section of a texture that is used for display / drawing. sf::Text A drawable text element; incorporates a Font and a String. Positioning can be set as needed. sf::RenderTexture A read-write texture; data is stored in video memory. This object can be drawn on. Specification In this assignment, students will generate two artifacts, a memer library and a memeify executable. Library The library will be named memer. It should incorporate the function below and include memer.h: sf::Image generateMeme(sf::Image base, sf::String topText, sf::String bottomText = “”, int topX = -1, int topY = -1, int bottomX = -1, int bottomY = -1) Takes in an base to be used as the base image. Returns a new sf::Image with topText drawn over it at location (topX, topY) in the provided font. If no coordinates are provided, topText should be centered horizontally and be 1/3 from the top of the image. If it is provided, bottomText is drawn at location (bottomX, bottomY). If provided, the tbottomText should be placed 1/3 from the bottom of the image. In general, adding text to an image will consist of the following steps: 1. Converting the Image into a Texture 2. Wrapping the Texture in a Sprite 3. Drawing the Sprite on a fresh & empty RenderTexture 4. Loading a Font, and using it to construct a Text element 5. Drawing the Text on the RenderTexture 6. Extracting an Image from a Texture, derived from the RenderTexture. NOTE: graphics are traditionally done differently in 2D and 3D, resulting in the Image from a Texture being upside down; make sure to flip it horizontally before returning it! Executable Executable should function with just file & top text: … but should also accept a partial / full complement: The executable should 1) display the image in a window until the window is closed, and 2) save the image with a new name based on the old one in the form of STEM-meme.EXT; e.g., if the original image was “doge.jpg”, the new image saved should be “doge-meme.jpg”. Submissions NOTE: Your output must match the example output *exactly*. If it does not, you will not receive full credit for your submission! (Note that matching sample output is necessary, but not sufficient, for full credit.) Files: memeify.zip Method: Submit on Canvas Compressed Archive (memeify.zip) We do not list required source files, only headers. You should include additional source or header files in addition to those listed – based on your design – but you must have the listed files at a minimum. Your compressed file should have the following directory/file structure: memeify.zip memeify (directory) CMakeLists.txt memer.h (Other sources / folders) finn@BMO:~$ ./memeify doge.jpg “Such memes” finn@BMO:~$ ./memeify doge.jpg “Such memes” > “wow” 360 90 120 360
Overview This linked list project is intended to provide students with an understanding of how sequential list data structures function. This project involves the implementation of a templated, doubly linked list with methods that allow for its use as a queue or stack container. A doubly linked list is a type of linked list which is linked in both directions, pointing to the next and previous nodes in the list. It usually terminates, at both ends, in pointers to nullptr. Depending on how one adds to or remove items from either end, the linked list can behave either as a stack or as a queue. A linked list is made up of nodes. Each node in the list contains some data (in this case, a location represented by a pair of coordinates) and a pointer to the next and previous nodes in the list. The first node in the list is called the front, and the last node is called the back. A linked list with location coordinates as data Specification Students have been provided with a test driver program (main.cpp), build file (CMakeLists.txt), and built-in memory leak detection (nvwa). Full credit requires implementation with no errors or warnings. Classes Students will write a linked list class and a nested iterator class for the linked list as follows. LinkedList::Iterator public T operator*() const Return the element at the iterator’s current position in the queue. Iterator& operator++() Pre-increment overload; advance the iterator one position in the list. Return this iterator. NOTE: if the iterator has reached the end of the list (past the last element), its data should be equal to LinkedList::end(). Iterator& operator–() Pre-decrement overload; recedes one element. Return this iterator. NOTE: if the iterator has reached the end of the list (before the first element), its data should be equal to LinkedList::end(). bool operator==(Iterator const& rhs) Return true it both iterators point to the same node in the list, and false otherwise. bool operator!=(Iterator const& rhs) Return false it both iterators point to the same node in the list, and true otherwise. nullptr 3, 4 5, 12 7, 24 8, 15 nullptr front back LinkedList public LinkedList() Construct a new LinkedList. Iterator begin() const Return an Iterator pointing to the beginning of the list. Iterator tail() const Return an Iterator pointing to the last node of the list. Iterator end() const Return an Iterator pointing past the end of the list (an invalid, unique state, data likely pointing to nullptr.) bool isEmpty() const Return true if there are no elements, false otherwise. T getFront() const Return the first element in the list. T getBack() const Return the last element in the list. bool contains(T element) const Return true if list contains a node whose data equals the specified element and false otherwise. void enqueue(T element) Adds the specified element to the back of the list. void dequeue() Remove the first element from the list. void pop() Remove the last element from the list. void clear() Removes all elements from the list. void remove(T element) Remove the first node found whose data equals the specified element. Note: be sure to update the pointers appropriately; test your code for the following scenarios: Remove the first node from the list Remove a node from the middle of the list Remove the last node from the list Remove the only node from the list Submissions NOTE: Your output must match the example output *exactly*. If it does not, you will not receive full credit for your submission! Files: LinkedList.h Method: Submit on ZyLabs
