Channels in C

I have to do an assignment in C. I have also attached the assignment prompt in additional material. Please read it as it included everything that you have to do in the assignment. I have also uploaded all the files need to complete the assignment.

Get Help With a similar task to - Channels in C

Login to view and/or buy answers.. or post an answer
Additional Instructions:

__MACOSX/._concurrencylab-div-dos concurrencylab-div-dos/stress.c #include <unistd.h> #include <pthread.h> #include <assert.h> #include <stdio.h> #include <stdbool.h> #include "channel.h" #include "stress.h" typedef unsigned int distance_t; typedef struct { size_t src; size_t epoch; distance_t dist[0]; } distance_vector_t; const distance_t inf_distance = 0x7fffffff; distance_t* topology; distance_t* solution; size_t num_channel; channel_t** channels; channel_t* done_channel; channel_t* completed_channel; distance_t get_link_distance(size_t src, size_t dst) { return topology[src * num_channel + dst]; } void set_link_distance(size_t src, size_t dst, distance_t distance) { topology[src * num_channel + dst] = distance; } distance_t get_solution_distance(size_t src, size_t dst) { return solution[src * num_channel + dst]; } void set_solution_distance(size_t src, size_t dst, distance_t distance) { solution[src * num_channel + dst] = distance; } void floyd_warshall() { memcpy(solution, topology, sizeof(distance_t) * num_channel * num_channel); for (size_t intermediate = 0; intermediate < num_channel; intermediate++) { for (size_t src = 0; src < num_channel; src++) { for (size_t dst = 0; dst < num_channel; dst++) { if (get_solution_distance(src, intermediate) + get_solution_distance(intermediate, dst) < get_solution_distance(src, dst)) { set_solution_distance(src, dst, get_solution_distance(src, intermediate) + get_solution_distance(intermediate, dst)); } } } } } void print_graph() { printf("GRAPH\n"); for (size_t src = 0; src < num_channel; src++) { for (size_t dst = 0; dst < num_channel; dst++) { distance_t distance = get_link_distance(src, dst); if (distance == inf_distance) { printf("inf "); } else { printf("%03u ", distance); } } printf("\n"); } } void print_solution() { printf("SOLUTION\n"); for (size_t src = 0; src < num_channel; src++) { for (size_t dst = 0; dst < num_channel; dst++) { distance_t distance = get_solution_distance(src, dst); if (distance == inf_distance) { printf("inf "); } else { printf("%03u ", distance); } } printf("\n"); } } bool create_topology(const char* filename) { FILE* file = fopen(filename, "r"); if (file == NULL) { printf("Could not open topology file: %s\n", filename); return false; } int num_scanned = fscanf(file, "%zu", &num_channel); assert(num_scanned == 1); assert(num_channel > 0); topology = malloc(sizeof(distance_t) * num_channel * num_channel); assert(topology != NULL); solution = malloc(sizeof(distance_t) * num_channel * num_channel); assert(solution != NULL); // populate topology for (size_t src = 0; src < num_channel; src++) { for (size_t dst = 0; dst < num_channel; dst++) { distance_t distance; num_scanned = fscanf(file, "%d", (int*)&distance); assert(num_scanned == 1); // negative values get converted to inf_distance if (distance > inf_distance) { distance = inf_distance; } set_link_distance(src, dst, distance); } } fclose(file); // calculate solution using Floyd-Warshall algorithm floyd_warshall(); return true; } void destroy_topology() { free(topology); free(solution); } void* router(void* arg) { bool changed = false; size_t index = (size_t)arg; size_t selected_index; distance_vector_t* prev_prev_state = malloc(sizeof(distance_vector_t) + sizeof(distance_t) * num_channel); assert(prev_prev_state != NULL); distance_vector_t* prev_state = malloc(sizeof(distance_vector_t) + sizeof(distance_t) * num_channel); assert(prev_state != NULL); distance_vector_t* curr_state = malloc(sizeof(distance_vector_t) + sizeof(distance_t) * num_channel); assert(curr_state != NULL); distance_vector_t* next_state = malloc(sizeof(distance_vector_t) + sizeof(distance_t) * num_channel); assert(next_state != NULL); prev_prev_state->src = index; prev_state->src = index; curr_state->src = index; next_state->src = index; prev_prev_state->epoch = 0; prev_state->epoch = 1; curr_state->epoch = 2; next_state->epoch = 3; for (size_t i = 0; i < num_channel; i++) { prev_prev_state->dist[i] = get_link_distance(index, i); prev_state->dist[i] = get_link_distance(index, i); curr_state->dist[i] = get_link_distance(index, i); next_state->dist[i] = get_link_distance(index, i); } size_t total_select_count = 2; for (size_t i = 0; i < num_channel; i++) { if ((i != index) && get_link_distance(index, i) != inf_distance) { total_select_count++; } } select_t* select_list = malloc(sizeof(select_t) * total_select_count); assert(select_list != NULL); size_t select_count = 0; select_list[select_count].channel = done_channel; select_list[select_count].dir = RECV; select_list[select_count].data = NULL; select_count++; select_list[select_count].channel = channels[index]; select_list[select_count].dir = RECV; select_list[select_count].data = NULL; select_count++; for (size_t i = 0; i < num_channel; i++) { if ((i != index) && get_link_distance(index, i) != inf_distance) { select_list[select_count].channel = channels[i]; select_list[select_count].dir = SEND; select_list[select_count].data = curr_state; select_count++; } } while (true) { enum channel_status status = channel_select(select_list, select_count, &selected_index); if (status == SUCCESS) { assert(selected_index != 0); if (selected_index == 1) { if (select_list[selected_index].data) { // update next_state with new data distance_vector_t* neighbor_state = select_list[selected_index].data; distance_t neighbor_dist = get_link_distance(index, neighbor_state->src); assert(neighbor_dist != inf_distance); for (size_t i = 0; i < num_channel; i++) { distance_t new_dist = neighbor_dist + neighbor_state->dist[i]; if (new_dist < next_state->dist[i]) { next_state->dist[i] = new_dist; changed = true; } } } else { // special message sent to test convergence bool converged = (select_count == 2) && !changed; status = channel_send(completed_channel, converged ? curr_state : NULL); assert(status == SUCCESS); } } else { select_count--; // swap last element and selected element channel_t* temp = select_list[select_count].channel; select_list[select_count].channel = select_list[selected_index].channel; select_list[selected_index].channel = temp; } // check if we've sent to everyone if (select_count == 2) { // check if we want to reset if (changed) { // cycle triple buffer distance_vector_t* temp_state = curr_state; curr_state = next_state; next_state = prev_prev_state; prev_prev_state = prev_state; prev_state = temp_state; next_state->epoch = curr_state->epoch + 1; for (size_t i = 0; i < num_channel; i++) { next_state->dist[i] = curr_state->dist[i]; } // reset to broadcast again select_count = total_select_count; for (size_t i = 2; i < select_count; i++) { select_list[i].data = curr_state; } changed = false; } } } else { assert(status == CLOSED_ERROR); assert(selected_index == 0); assert(changed == false); break; } } free(select_list); free(prev_prev_state); free(prev_state); free(curr_state); free(next_state); return NULL; } bool check_done() { bool valid = true; enum channel_status status; distance_vector_t** completed = malloc(sizeof(distance_vector_t*) * num_channel); assert(completed != NULL); // validate by sending special NULL message to flush channels for (size_t i = 0; i < num_channel; i++) { status = channel_send(channels[i], NULL); assert(status == SUCCESS); } // receive special response for (size_t i = 0; i < num_channel; i++) { void* data = NULL; status = channel_receive(completed_channel, &data); assert(status == SUCCESS); if (data == NULL) { valid = false; } else { distance_vector_t* new_data = (distance_vector_t*)data; size_t index = new_data->src; completed[index] = new_data; } } if (valid) { // ensure epoch hasn't changed since first validation for (size_t i = 0; i < num_channel; i++) { status = channel_send(channels[i], NULL); assert(status == SUCCESS); } // receive special response for (size_t i = 0; i < num_channel; i++) { void* data = NULL; status = channel_receive(completed_channel, &data); assert(status == SUCCESS); if (data == NULL) { valid = false; } else { distance_vector_t* new_data = (distance_vector_t*)data; size_t index = new_data->src; if (completed[index]->epoch != new_data->epoch) { valid = false; } } } if (valid) { // check results for (size_t src = 0; src < num_channel; src++) { for (size_t dst = 0; dst < num_channel; dst++) { assert(completed[src]->dist[dst] == get_solution_distance(src, dst)); } } } } free(completed); return valid; } void run_stress(size_t main_buffer_size, size_t secondary_buffer_size, const char* filename) { assert(main_buffer_size <= 1); // only support up to a buffer size of 1 assert(secondary_buffer_size <= 1); // only support up to a buffer size of 1 int pthread_status; enum channel_status status; bool initialized = create_topology(filename); assert(initialized); channels = malloc(sizeof(channel_t*) * num_channel); assert(channels != NULL); for (size_t i = 0; i < num_channel; i++) { channels[i] = channel_create(main_buffer_size); assert(channels[i] != NULL); } done_channel = channel_create(secondary_buffer_size); assert(done_channel != NULL); completed_channel = channel_create(secondary_buffer_size); assert(completed_channel != NULL); pthread_t* pid = malloc(sizeof(pthread_t) * num_channel); assert(pid != NULL); for (size_t i = 0; i < num_channel; i++) { pthread_status = pthread_create(&pid[i], NULL, router, (void*)i); assert(pthread_status == 0); } // wait for convergence while (!check_done()) { usleep(1000); } // stop threads status = channel_close(done_channel); assert(status == SUCCESS); // join threads for (size_t i = 0; i < num_channel; i++) { pthread_join(pid[i], NULL); } // cleanup status = channel_destroy(done_channel); assert(status == SUCCESS); status = channel_close(completed_channel); assert(status == SUCCESS); status = channel_destroy(completed_channel); assert(status == SUCCESS); for (size_t i = 0; i < num_channel; i++) { status = channel_close(channels[i]); assert(status == SUCCESS); status = channel_destroy(channels[i]); assert(status == SUCCESS); } free(pid); free(channels); destroy_topology(); } __MACOSX/concurrencylab-div-dos/._stress.c concurrencylab-div-dos/buffer.c #include "buffer.h" // Creates a buffer with the given capacity buffer_t* buffer_create(size_t capacity) { buffer_t* buffer = (buffer_t*) malloc(sizeof(buffer_t)); void** data = (void**) malloc(capacity * sizeof(void*)); buffer->size = 0; buffer->next = 0; buffer->capacity = capacity; buffer->data = data; return buffer; } // Adds the value into the buffer // Returns BUFFER_SUCCESS if the buffer is not full and value was added // Returns BUFFER_ERROR otherwise enum buffer_status buffer_add(buffer_t* buffer, void* data) { if (buffer->size >= buffer->capacity) { return BUFFER_ERROR; } size_t pos = buffer->next + buffer->size; if (pos >= buffer->capacity) { pos -= buffer->capacity; } buffer->data[pos] = data; buffer->size++; return BUFFER_SUCCESS; } // Removes the value from the buffer in FIFO order and stores it in data // Returns BUFFER_SUCCESS if the buffer is not empty and a value was removed // Returns BUFFER_ERROR otherwise enum buffer_status buffer_remove(buffer_t* buffer, void **data) { if (buffer->size > 0) { *data = buffer->data[buffer->next]; buffer->size--; buffer->next++; if (buffer->next >= buffer->capacity) { buffer->next -= buffer->capacity; } return BUFFER_SUCCESS; } return BUFFER_ERROR; } // Frees the memory allocated to the buffer void buffer_free(buffer_t *buffer) { free(buffer->data); free(buffer); } // Returns the total capacity of the buffer size_t buffer_capacity(buffer_t* buffer) { return buffer->capacity; } // Returns the current number of elements in the buffer size_t buffer_current_size(buffer_t* buffer) { return buffer->size; } // Peeks at a value in the buffer // Only used for testing code; you should NOT use this void* peek_buffer(buffer_t* buffer, size_t index) { return buffer->data[index]; } __MACOSX/concurrencylab-div-dos/._buffer.c concurrencylab-div-dos/channel.h #ifndef CHANNEL_H #define CHANNEL_H #include <stdio.h> #include <stdlib.h> #include <pthread.h> #include <semaphore.h> #include "buffer.h" #include <stddef.h> #include <string.h> #include <stdbool.h> #include "linked_list.h" // Defines possible return values from channel functions enum channel_status { CHANNEL_EMPTY = 0, CHANNEL_FULL = 0, SUCCESS = 1, CLOSED_ERROR = -2, GEN_ERROR = -1, DESTROY_ERROR = -3 }; // Defines channel object typedef struct { // DO NOT REMOVE buffer (OR CHANGE ITS NAME) FROM THE STRUCT // YOU MUST USE buffer TO STORE YOUR BUFFERED CHANNEL MESSAGES buffer_t* buffer; /* ADD ANY STRUCT ENTRIES YOU NEED HERE */ /* IMPLEMENT THIS */ } channel_t; // Defines channel list structure for channel_select function enum direction { SEND, RECV, }; typedef struct { // Channel on which we want to perform operation channel_t* channel; // Specifies whether we want to receive (RECV) or send (SEND) on the channel enum direction dir; // If dir is RECV, then the message received from the channel is stored as an output in this parameter, data // If dir is SEND, then the message that needs to be sent is given as input in this parameter, data void* data; } select_t; // Creates a new channel with the provided size and returns it to the caller // A 0 size indicates an unbuffered channel, whereas a positive size indicates a buffered channel channel_t* channel_create(size_t size); // Writes data to the given channel // This is a blocking call i.e., the function only returns on a successful completion of send // In case the channel is full, the function waits till the channel has space to write the new data // Returns SUCCESS for successfully writing data to the channel, // CLOSED_ERROR if the channel is closed, and // GEN_ERROR on encountering any other generic error of any sort enum channel_status channel_send(channel_t* channel, void* data); // Reads data from the given channel and stores it in the function’s input parameter, data (Note that it is a double pointer). // This is a blocking call i.e., the function only returns on a successful completion of receive // In case the channel is empty, the function waits till the channel has some data to read // Returns SUCCESS for successful retrieval of data, // CLOSED_ERROR if the channel is closed, and // GEN_ERROR on encountering any other generic error of any sort enum channel_status channel_receive(channel_t* channel, void** data); // Writes data to the given channel // This is a non-blocking call i.e., the function simply returns if the channel is full // Returns SUCCESS for successfully writing data to the channel, // CHANNEL_FULL if the channel is full and the data was not added to the buffer, // CLOSED_ERROR if the channel is closed, and // GEN_ERROR on encountering any other generic error of any sort enum channel_status channel_non_blocking_send(channel_t* channel, void* data); // Reads data from the given channel and stores it in the function’s input parameter data (Note that it is a double pointer) // This is a non-blocking call i.e., the function simply returns if the channel is empty // Returns SUCCESS for successful retrieval of data, // CHANNEL_EMPTY if the channel is empty and nothing was stored in data, // CLOSED_ERROR if the channel is closed, and // GEN_ERROR on encountering any other generic error of any sort enum channel_status channel_non_blocking_receive(channel_t* channel, void** data); // Closes the channel and informs all the blocking send/receive/select calls to return with CLOSED_ERROR // Once the channel is closed, send/receive/select operations will cease to function and just return CLOSED_ERROR // Returns SUCCESS if close is successful, // CLOSED_ERROR if the channel is already closed, and // GEN_ERROR in any other error case enum channel_status channel_close(channel_t* channel); // Frees all the memory allocated to the channel // The caller is responsible for calling channel_close and waiting for all threads to finish their tasks before calling channel_destroy // Returns SUCCESS if destroy is successful, // DESTROY_ERROR if channel_destroy is called on an open channel, and // GEN_ERROR in any other error case enum channel_status channel_destroy(channel_t* channel); // Takes an array of channels, channel_list, of type select_t and the array length, channel_count, as inputs // This API iterates over the provided list and finds the set of possible channels which can be used to invoke the required operation (send or receive) specified in select_t // If multiple options are available, it selects the first option and performs its corresponding action // If no channel is available, the call is blocked and waits till it finds a channel which supports its required operation // Once an operation has been successfully performed, select should set selected_index to the index of the channel that performed the operation and then return SUCCESS // In the event that a channel is closed or encounters any error, the error should be propagated and returned through select // Additionally, selected_index is set to the index of the channel that generated the error enum channel_status channel_select(select_t* channel_list, size_t channel_count, size_t* selected_index); #endif // CHANNEL_H __MACOSX/concurrencylab-div-dos/._channel.h concurrencylab-div-dos/random_topology.txt 10 0 1 -1 1 -1 1 -1 1 1 -1 1 0 -1 -1 1 -1 -1 1 1 -1 -1 -1 0 -1 -1 -1 1 -1 -1 1 1 -1 -1 0 -1 1 -1 -1 1 1 -1 1 -1 -1 0 -1 -1 -1 1 -1 1 -1 -1 1 -1 0 1 -1 -1 1 -1 -1 1 -1 -1 1 0 1 1 -1 1 1 -1 -1 -1 -1 1 0 1 -1 1 1 -1 1 1 -1 1 1 0 -1 -1 -1 1 1 -1 1 -1 -1 -1 0 __MACOSX/concurrencylab-div-dos/._random_topology.txt concurrencylab-div-dos/linked_list.h #ifndef LINKED_LIST_H #define LINKED_LIST_H #include <stdlib.h> #include <stddef.h> typedef struct list_node { struct list_node* next; struct list_node* prev; void* data; } list_node_t; typedef struct { list_node_t* head; size_t count; } list_t; // Creates and returns a new list list_t* list_create(); // Destroys a list void list_destroy(list_t* list); // Returns beginning of the list list_node_t* list_begin(list_t* list); // Returns next element in the list list_node_t* list_next(list_node_t* node); // Returns data in the given list node void* list_data(list_node_t* node); // Returns the number of elements in the list size_t list_count(list_t* list); // Finds the first node in the list with the given data // Returns NULL if data could not be found list_node_t* list_find(list_t* list, void* data); // Inserts a new node in the list with the given data void list_insert(list_t* list, void* data); // Removes a node from the list and frees the node resources void list_remove(list_t* list, list_node_t* node); // Executes a function for each element in the list void list_foreach(list_t* list, void (*func)(void* data)); #endif // LINKED_LIST_H __MACOSX/concurrencylab-div-dos/._linked_list.h concurrencylab-div-dos/Prompt.pdf CMPSC473, Spring 2020 Concurrency Lab: Channels in C Due: Thu., Mar 26 at Noon Introduction Note that the assignment is due at noon. Concurrent programming is hard – start early. A channel is a model for synchronization via message passing. Messages may be sent over a channel by a thread (Sender) and other threads which have a reference to this channel can receive them (Receivers). A channel can have multiple senders and receivers referencing it at any point of time. Channels are used as a primitive to implement various other concurrent programming constructs. For example, channels are heavily used in Google’s Go programming language and are very useful frameworks for high-level concurrent programming. In this lab you will be writing your own version of a channel which will be used to communicate among multiple clients. A client can either write onto the channel or read from it. Keep in mind that multiple clients can read and write simultaneously from the channel. You are encouraged to explore the design space creatively and implement a channel that is correct and not exceptionally slow or inefficient. Performance is not the main concern in this assignment (functionality is the main concern), but your implementation should avoid inefficient designs that sleep for any fixed time or unnecessarily waste CPU time. There are multiple variations to channels, such as whether the send/receive is blocking or non-blocking. In blocking mode, receivers always block until there is data to receive, whereas in non-blocking mode, they simply return. Similarly, with senders, in blocking mode, if the buffer is full, senders wait until some receiver has retrieved a value and there is available space in the buffer whereas in non-blocking mode, they simply leave without sending. In this lab, you will support both blocking and non-blocking send/receive functions. Another variation to channels would be if a channel is buffered (i.e., channel buffer size > 0) or unbuffered (i.e., channel buffer size = 0). In the buffered case, the sender blocks only until the value has been copied to the buffer. On the other hand, if the channel is unbuffered, the sender blocks until the receiver has received the value. In this lab, you will only be responsible for supporting buffered channels. Supporting unbuffered channels is extra credit and is especially difficult when implementing select. The amount of extra credit is really small for the amount and difficulty of work involved, and correctly implementing the unbuffered version for select is probably 2-3 times the work of the entire buffered assignment. The only files you will be modifying are channel.c and channel.h and optionally linked_list.c and linked_list.h. You should NOT make any changes in any file besides these four files. You will be implementing the following functions, which are described in channel.c and channel.h: • channel_t* channel_create(size_t size) • enum channel_status channel_send(channel_t* channel, void* data) • enum channel_status channel_receive(channel_t* channel, void** data) • enum channel_status channel_non_blocking_send(channel_t* channel, void* data) • enum channel_status channel_non_blocking_receive(channel_t* channel, void** data) • enum channel_status channel_close(channel_t* channel) • enum channel_status channel_destroy(channel_t* channel) • enum channel_status channel_select(select_t* channel_list, size_t channel_count, size_t* selected_index) The enum channel_status is a named enumeration type that is defined in channel.h. Rather than using an int, which can be any number, enumerations are integers that should match one of the defined values. For example, if you want to return that the function succeeded, you would just return SUCCESS. You are encouraged to define other (static) helper functions, structures, etc. to help structure the code in a better way. Support routines The buffer.c and buffer.h files contain the helper constructs for you to create and manage a buffered channel. These functions will help you separate the buffer management from the concurrency issues in your channel code. Please note that these functions are NOT thread-safe. You are welcome to use any of these functions, but you should not change them. • buffer_t* buffer_create(size_t capacity) Creates a buffer with the given capacity. • enum buffer_status buffer_add(buffer_t* buffer, void* data) Adds the value into the buffer. Returns BUFFER_SUCCESS if the buffer is not full and value was added. Returns BUFFER_ERROR otherwise. • enum buffer_status buffer_remove(buffer_t* buffer, void** data) Removes the value from the buffer in FIFO order and stores it in data. Returns BUFFER_SUCCESS if the buffer is not empty and a value was removed. Returns BUFFER_ERROR otherwise. • void buffer_free(buffer_t* buffer) Frees the memory allocated to the buffer. • size_t buffer_capacity(buffer_t* buffer) Returns the total capacity of the buffer. • size_t buffer_current_size(buffer_t* buffer) Returns the current number of elements in the buffer. We have also provided the optional interface for a linked list in linked_list.c and linked_list.h. You are welcome to implement and use this interface in your code, but you are not required to implement it if you don’t want to use it. It is primarily provided to help you structure your code in a clean fashion if you want to use linked lists in your code. Linked lists may NOT be needed depending on your design, so do not try to force it into your solution. You can add/change/remove any of the functions in linked_list.c and linked_list.h as you see fit. Programming rules You are not allowed to take any of the following approaches to complete the assignment: • Spinning in a polling loop to implement blocking calls • Sleeping for any fixed amount of time; instead, use cond_wait or sem_wait • Trying to change the timing of your code to hide bugs such as race conditions • Using global variables in your code You are only allowed to use the pthread library, the POSIX semaphore library, basic standard C library functions (e.g., malloc/free), and the provided code in the assignment for completing your implementation. If you think you need some library function, please contact the course staff to determine the eligibility. You can find a reference/tutorial for the pthread library at: https://computing.llnl.gov/tutorials/pthreads/ You can find a reference/tutorial for the POSIX semaphore library at: http://www.csc.villanova.edu/~mdamian/threads/posixsem.html Looking at documentation (e.g., for these libraries, for tools, etc.) is fine, but as stated in the academic integrity policy, looking online for any hints about implementing channels is disallowed. Evaluation and testing your code You will receive zero points if: • You violate the academic integrity policy (sanctions can be greater than just a 0 for the assignment) • You break any of the programming rules • Your code does not compile/build • Your code crashes the grading script • You don’t show your partial work by periodically adding, committing, and pushing your code to GitHub Your code will be evaluated for correctness, properly handling synchronization, and ensuring it does not violate any of the programming rules (e.g., do not spin or sleep for any period of time). We have provided many tests, but we reserve the right to add additional tests during the final grading, so you are responsible for ensuring your code is correct, where a large part of correctness is ensuring you don’t have race conditions, deadlocks, or other synchronization bugs. To run the supplied test cases, simply run the following command in the project folder: make test make test will compile your code in release mode and run the grade.py script, which runs a combination of the following tests to autograde your assignment: • After running the make command in your project, two executable files will be created. The default executable, channel, is used to run test cases in the normal mode. The test cases are located in test.c, and you can find the list of tests at the bottom of the file. If you want to run a single test, run the following: ./channel [test_case_name] [iters] where [test_case_name] is the test name and [iters] is the number of times to run the test. If you do not provide a test name, all tests will be run. The default number of iterations is 1. • The other executable, channel_sanitize, will be used to help detect data races in your code. It can be used with any of the test cases by replacing ./channel with ./channel_sanitize. ./channel_sanitize [test_case_name] [iters] Any detected data races will be output to the terminal. You should implement code that does not generate any errors or warnings from the data race detector. • Valgrind is being used to check for memory leaks, report uses of uninitialized values, and detect memory errors such as freeing a memory space more than once. To run a valgrind check by yourself, use the command: valgrind -v --leak-check=full ./channel [test_case_name] [iters] Note that channel_sanitize should not be run with valgrind as the tools do not behave well together. Only the channel executable should be used with valgrind. Valgrind will issue messages about memory errors and leaks that it detects for you to fix them. You should implement code that does not generate any valgrind errors or warnings. IMPORTANT: Note that any test FAILURE may result in the sanitizer or valgrind reporting thread leaks or memory leaks. This is expected since test failures will cause the test to prematurely end without cleaning up any threads or memory. Thus, you should first fix the test failure. Handin Similar to the last assignment, we will be using GitHub for managing submissions, and you must show your partial work by periodically adding, committing, and pushing your code to GitHub. This helps us see your code if you ask any questions on Canvas (please include your GitHub username) and also helps deter academic integrity violations. Additionally, please input the desired commit number that you would like us to grade in the Canvas assignment. You can get the commit number from github.com. In your repository, click on the commits link to the left above your files. Find the commit from the appropriate day/time that you want committed. Click on the clipboard icon to copy the commit number. Note that this is a much longer number than the displayed number. Paste your very long commit number and only your commit number in this assignment submission textbox. Hints • Carefully read the output from the sanitizer and valgrind tools and think about what they’re trying to say. Usually, they’re printing call stacks to tell you which locations have race conditions, or which locations allocate some memory that was being accessed in the race condition, or which locations allocate some memory that is being leaked, etc. These tools are tremendously useful, which is why we’ve set them up for you for this assignment. • While the tools are very useful, they are not perfect. Some race conditions are rare and don’t show up all the time. A reasonable approach to debugging these race condition bugs is to try to identify the symptoms of the bug and then read your code to see if you can figure out the sequence of events that caused the bug based on the symptoms. • Debugging with gdb is a useful way of getting information about what’s going on in your code. To compile your code in debug mode (to make it easier to debug with gdb), you can simply run: make debug It is important to realize that when trying to find race conditions, the reproducibility of the race condition often depends on the timing of events. As a result, sometimes, your race condition may only show up in non-debug (i.e., release) mode and may disappear when you run it in debug mode. Bugs may sometimes also disappear when running with gdb or if you add print statements. Bugs that only show up some of the time are still bugs, and you should fix these. Do not try to change the timing to hide the bugs. • If your bug only shows up outside of gdb, one useful approach is to look at the core dump (if it crashes). Here’s a link to a tutorial on how to get and use core dump files: http://yusufonlinux.blogspot.com/2010/11/debugging-core-using-gdb.html • If your bug only shows up outside of gdb and causes a deadlock (i.e., hangs forever), one useful approach is to attach gdb to the program after the fact. To do this, first run your program. Then in another command prompt terminal run: ps aux This will give you a listing of your running programs. Find your program and look at the PID column. Then within gdb (may require sudo) run: attach <PID> where you replace <PID> with the PID number that you got from ps aux. This will give you a gdb debugging session just like if you had started the program with gdb. __MACOSX/concurrencylab-div-dos/._Prompt.pdf concurrencylab-div-dos/Makefile TARGET = channel TARGET_SANITIZE = channel_sanitize STUDENT_OBJS += channel.o STUDENT_OBJS += linked_list.o OBJS += $(STUDENT_OBJS) OBJS += buffer.o OBJS += stress.o OBJS += stress_send_recv.o OBJS += test.o LIBS += -lpthread LIBS += -lrt W204_CC = /home/software/gcc/gcc-6.3.0/bin/gcc630 ifeq ("$(wildcard $(W204_CC))","") CC = gcc else CC = $(W204_CC) endif CFLAGS += -MMD -MP # dependency tracking flags CFLAGS += -I./ CFLAGS += -std=gnu11 -Wall -Werror -Wconversion LDFLAGS += $(LIBS) NOT_ALLOWED += -Dsleep=sleep_not_allowed NOT_ALLOWED += -Dusleep=usleep_not_allowed NOT_ALLOWED += -Dnanosleep=nanosleep_not_allowed NOT_ALLOWED += -Dselect=select_not_allowed all: CFLAGS += -g -O2 # release flags all: $(TARGET) $(TARGET_SANITIZE) release: clean all debug: CFLAGS += -g -O0 -D_GLIBC_DEBUG # debug flags debug: clean $(TARGET) $(TARGET_SANITIZE) SANITIZE_OBJS = $(OBJS:%.o=%_sanitize.o) $(TARGET_SANITIZE): $(SANITIZE_OBJS) $(CC) $(CFLAGS) -fsanitize=thread -o $@ $^ $(LDFLAGS) -static-libtsan $(TARGET): $(OBJS) $(CC) $(CFLAGS) -o $@ $^ $(LDFLAGS) $(STUDENT_OBJS:%.o=%_sanitize.o): CFLAGS += $(NOT_ALLOWED) %_sanitize.o: %.c $(CC) $(CFLAGS) -fPIC -fsanitize=thread -c -o $@ $< $(STUDENT_OBJS): CFLAGS += $(NOT_ALLOWED) %.o: %.c $(CC) $(CFLAGS) -c -o $@ $< ALL_OBJS = $(OBJS) + $(SANITIZE_OBJS) DEPS = $(ALL_OBJS:%.o=%.d) -include $(DEPS) clean: -@rm $(TARGET) $(TARGET_SANITIZE) $(ALL_OBJS) $(DEPS) 2> /dev/null || true test: @chmod +x grade.py @sed -i -e 's/\r$$//g' *.py # dos to unix @sed -i -e 's/\r/\n/g' *.py # mac to unix @sed -i -e 's/\r$$//g' *.txt # dos to unix @sed -i -e 's/\r/\n/g' *.txt # mac to unix ./grade.py __MACOSX/concurrencylab-div-dos/._Makefile concurrencylab-div-dos/connected_topology.txt 10 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 __MACOSX/concurrencylab-div-dos/._connected_topology.txt concurrencylab-div-dos/topology.txt 10 0 1 -1 -1 -1 -1 -1 -1 -1 1 1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 1 0 1 1 -1 -1 -1 -1 -1 -1 -1 1 0 __MACOSX/concurrencylab-div-dos/._topology.txt concurrencylab-div-dos/random_topology_1.txt 20 0 1 -1 -1 1 1 1 -1 -1 1 1 1 -1 -1 -1 -1 -1 1 -1 -1 1 0 -1 -1 1 1 1 1 1 1 -1 1 -1 1 1 -1 1 1 -1 1 -1 -1 0 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 0 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 1 1 1 1 1 -1 0 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 -1 -1 -1 0 1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 1 1 1 1 -1 1 -1 1 0 1 1 -1 1 -1 -1 1 -1 -1 -1 -1 1 1 -1 1 1 -1 -1 -1 1 0 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 0 -1 1 1 -1 1 -1 1 -1 -1 1 1 1 1 -1 -1 1 1 -1 1 -1 0 -1 1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 0 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 0 1 -1 1 1 1 -1 -1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 0 1 -1 1 1 1 1 -1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 0 1 -1 1 1 -1 -1 -1 -1 -1 1 1 -1 1 1 1 -1 1 1 -1 1 0 -1 -1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 0 1 -1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 -1 1 0 -1 -1 -1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 -1 -1 0 1 -1 1 -1 1 1 1 1 -1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 0 __MACOSX/concurrencylab-div-dos/._random_topology_1.txt concurrencylab-div-dos/stress_send_recv.c #include <unistd.h> #include <pthread.h> #include <assert.h> #include <stdio.h> #include <stdbool.h> #include <stdatomic.h> #include "channel.h" #include "stress_send_recv.h" size_t num_channel; channel_t** channels; volatile atomic_bool done; channel_t* main_channel; void* worker_thread(void* arg) { size_t index = (size_t)arg; size_t next_index = index + 1; if (next_index >= num_channel) { next_index = 0; } channel_t* my_channel = channels[index]; channel_t* next_channel = channels[next_index]; bool start = true; enum channel_status status; while (true) { void* data = NULL; if (start) { status = channel_receive(main_channel, &data); assert(status == SUCCESS); if (data == NULL) { // indicates start period is over start = false; continue; } } else { status = channel_receive(my_channel, &data); assert(status == SUCCESS); if (data == NULL) { // indicates completion break; } } if (atomic_load(&done)) { // Send data to main_channel status = channel_send(main_channel, data); assert(status == SUCCESS); } else { // Pass along message to next thread in ring status = channel_send(next_channel, data); assert(status == SUCCESS); } } return NULL; } void run_stress_send_recv(size_t buffer_size, size_t num_threads, double load, useconds_t duration_usec) { enum channel_status status; // setup num_channel = num_threads; atomic_store(&done, false); size_t num_msgs = (size_t)(((double)(num_channel * (buffer_size + 1))) * load); bool* msg_check = calloc(num_msgs + 1, sizeof(bool)); assert(msg_check != NULL); channels = malloc(sizeof(channel_t*) * num_channel); assert(channels != NULL); for (size_t i = 0; i < num_channel; i++) { channels[i] = channel_create(buffer_size); assert(channels[i] != NULL); } main_channel = channel_create(buffer_size); assert(main_channel != NULL); pthread_t* pid = malloc(sizeof(pthread_t) * num_channel); assert(pid != NULL); for (size_t i = 0; i < num_channel; i++) { int pthread_status = pthread_create(&pid[i], NULL, worker_thread, (void*)i); assert(pthread_status == 0); } // start test for (size_t msg = 1; msg <= num_msgs; msg++) { // insert data into threads status = channel_send(main_channel, (void*)msg); assert(status == SUCCESS); } for (size_t i = 0; i < num_channel; i++) { // send start message status = channel_send(main_channel, NULL); assert(status == SUCCESS); } // wait for duration usleep(duration_usec); // stop test atomic_store(&done, true); for (size_t msg = 1; msg <= num_msgs; msg++) { // pull data from threads size_t data = 0; status = channel_receive(main_channel, (void**)&data); assert(status == SUCCESS); // check that data wasn't duplicated assert((1 <= data) && (data <= num_msgs)); assert(msg_check[data] == false); msg_check[data] = true; } // shutdown for (size_t i = 0; i < num_channel; i++) { // send stop message status = channel_send(channels[i], NULL); assert(status == SUCCESS); } for (size_t i = 0; i < num_channel; i++) { // join threads pthread_join(pid[i], NULL); } // cleanup status = channel_close(main_channel); assert(status == SUCCESS); status = channel_destroy(main_channel); assert(status == SUCCESS); for (size_t i = 0; i < num_channel; i++) { status = channel_close(channels[i]); assert(status == SUCCESS); status = channel_destroy(channels[i]); assert(status == SUCCESS); } free(msg_check); free(pid); free(channels); } __MACOSX/concurrencylab-div-dos/._stress_send_recv.c concurrencylab-div-dos/channel.c #include "channel.h" // Creates a new channel with the provided size and returns it to the caller // A 0 size indicates an unbuffered channel, whereas a positive size indicates a buffered channel channel_t* channel_create(size_t size) { /* IMPLEMENT THIS */ return NULL; } // Writes data to the given channel // This is a blocking call i.e., the function only returns on a successful completion of send // In case the channel is full, the function waits till the channel has space to write the new data // Returns SUCCESS for successfully writing data to the channel, // CLOSED_ERROR if the channel is closed, and // GEN_ERROR on encountering any other generic error of any sort enum channel_status channel_send(channel_t *channel, void* data) { /* IMPLEMENT THIS */ return SUCCESS; } // Reads data from the given channel and stores it in the function’s input parameter, data (Note that it is a double pointer). // This is a blocking call i.e., the function only returns on a successful completion of receive // In case the channel is empty, the function waits till the channel has some data to read // Returns SUCCESS for successful retrieval of data, // CLOSED_ERROR if the channel is closed, and // GEN_ERROR on encountering any other generic error of any sort enum channel_status channel_receive(channel_t* channel, void** data) { /* IMPLEMENT THIS */ return SUCCESS; } // Writes data to the given channel // This is a non-blocking call i.e., the function simply returns if the channel is full // Returns SUCCESS for successfully writing data to the channel, // CHANNEL_FULL if the channel is full and the data was not added to the buffer, // CLOSED_ERROR if the channel is closed, and // GEN_ERROR on encountering any other generic error of any sort enum channel_status channel_non_blocking_send(channel_t* channel, void* data) { /* IMPLEMENT THIS */ return SUCCESS; } // Reads data from the given channel and stores it in the function’s input parameter data (Note that it is a double pointer) // This is a non-blocking call i.e., the function simply returns if the channel is empty // Returns SUCCESS for successful retrieval of data, // CHANNEL_EMPTY if the channel is empty and nothing was stored in data, // CLOSED_ERROR if the channel is closed, and // GEN_ERROR on encountering any other generic error of any sort enum channel_status channel_non_blocking_receive(channel_t* channel, void** data) { /* IMPLEMENT THIS */ return SUCCESS; } // Closes the channel and informs all the blocking send/receive/select calls to return with CLOSED_ERROR // Once the channel is closed, send/receive/select operations will cease to function and just return CLOSED_ERROR // Returns SUCCESS if close is successful, // CLOSED_ERROR if the channel is already closed, and // GEN_ERROR in any other error case enum channel_status channel_close(channel_t* channel) { /* IMPLEMENT THIS */ return SUCCESS; } // Frees all the memory allocated to the channel // The caller is responsible for calling channel_close and waiting for all threads to finish their tasks before calling channel_destroy // Returns SUCCESS if destroy is successful, // DESTROY_ERROR if channel_destroy is called on an open channel, and // GEN_ERROR in any other error case enum channel_status channel_destroy(channel_t* channel) { /* IMPLEMENT THIS */ return SUCCESS; } // Takes an array of channels, channel_list, of type select_t and the array length, channel_count, as inputs // This API iterates over the provided list and finds the set of possible channels which can be used to invoke the required operation (send or receive) specified in select_t // If multiple options are available, it selects the first option and performs its corresponding action // If no channel is available, the call is blocked and waits till it finds a channel which supports its required operation // Once an operation has been successfully performed, select should set selected_index to the index of the channel that performed the operation and then return SUCCESS // In the event that a channel is closed or encounters any error, the error should be propagated and returned through select // Additionally, selected_index is set to the index of the channel that generated the error enum channel_status channel_select(select_t* channel_list, size_t channel_count, size_t* selected_index) { /* IMPLEMENT THIS */ return SUCCESS; } __MACOSX/concurrencylab-div-dos/._channel.c concurrencylab-div-dos/README.md # concurrencylab Carefully read concurrencylab.pdf in its entirety. __MACOSX/concurrencylab-div-dos/._README.md concurrencylab-div-dos/buffer.h #ifndef BUFFER_H #define BUFFER_H #include <stdlib.h> typedef struct { size_t size; size_t next; size_t capacity; void** data; } buffer_t; enum buffer_status { BUFFER_SUCCESS = 1, BUFFER_ERROR = -1 }; // Creates a buffer with the given capacity buffer_t* buffer_create(size_t capacity); // Adds the value into the buffer // Returns BUFFER_SUCCESS if the buffer is not full and value was added // Returns BUFFER_ERROR otherwise enum buffer_status buffer_add(buffer_t* buffer, void* data); // Removes the value from the buffer in FIFO order and stores it in data // Returns BUFFER_SUCCESS if the buffer is not empty and a value was removed // Returns BUFFER_ERROR otherwise enum buffer_status buffer_remove(buffer_t* buffer, void** data); // Frees the memory allocated to the buffer void buffer_free(buffer_t* buffer); // Returns the total capacity of the buffer size_t buffer_capacity(buffer_t* buffer); // Returns the current number of elements in the buffer size_t buffer_current_size(buffer_t* buffer); // Peeks at a value in the buffer // Only used for testing code; you should NOT use this void* peek_buffer(buffer_t* buffer, size_t index); #endif // BUFFER_H __MACOSX/concurrencylab-div-dos/._buffer.h concurrencylab-div-dos/stress.h #ifndef STRESS_H #define STRESS_H void run_stress(size_t main_buffer_size, size_t secondary_buffer_size, const char* filename); #endif // STRESS_H __MACOSX/concurrencylab-div-dos/._stress.h concurrencylab-div-dos/.gitignore # Project files channel channel_sanitize *.log # Vagrant files .vagrant/ ubuntu-bionic-18.04-cloudimg-console.log # Prerequisites *.d # Object files *.o *.ko *.obj *.elf # Linker output *.ilk *.map *.exp # Precompiled Headers *.gch *.pch # Libraries *.lib *.a *.la *.lo # Shared objects (inc. Windows DLLs) *.dll *.so *.so.* *.dylib # Executables *.exe *.out *.app *.i*86 *.x86_64 *.hex # Debug files *.dSYM/ *.su *.idb *.pdb # Kernel Module Compile Results *.mod* *.cmd .tmp_versions/ modules.order Module.symvers Mkfile.old dkms.conf # Temporary files *~ __MACOSX/concurrencylab-div-dos/._.gitignore concurrencylab-div-dos/big_graph.txt 100 0 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 0 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 1 1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 1 0 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 0 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 0 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 1 -1 -1 1 1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 0 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 1 -1 1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 1 1 1 1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 0 -1 1 1 -1 1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 0 1 -1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 0 1 1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 0 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 0 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 1 1 1 1 -1 0 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 -1 1 -1 1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 0 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 0 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 0 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 1 -1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 0 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 0 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 0 -1 -1 -1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 0 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 1 1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 1 1 -1 1 1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 0 -1 1 -1 -1 -1 1 1 -1 1 -1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 0 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 -1 0 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 1 0 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 1 -1 1 1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 -1 -1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 1 -1 -1 -1 -1 -1 0 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 1 -1 -1 0 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 0 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 0 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 0 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 1 -1 1 0 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 0 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 1 0 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 -1 1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 0 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 0 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 -1 -1 1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 0 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 0 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 0 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 0 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 1 -1 -1 0 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 0 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 0 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 0 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 0 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 0 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 0 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 0 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 0 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 0 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 0 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 1 1 1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 1 -1 -1 -1 -1 1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 0 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 0 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 0 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 0 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 1 1 -1 1 -1 -1 1 -1 -1 1 -1 -1 0 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 0 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 0 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 0 __MACOSX/concurrencylab-div-dos/._big_graph.txt concurrencylab-div-dos/linked_list.c #include "linked_list.h" // Creates and returns a new list list_t* list_create() { /* IMPLEMENT THIS IF YOU WANT TO USE LINKED LISTS */ return NULL; } // Destroys a list void list_destroy(list_t* list) { /* IMPLEMENT THIS IF YOU WANT TO USE LINKED LISTS */ } // Returns beginning of the list list_node_t* list_begin(list_t* list) { /* IMPLEMENT THIS IF YOU WANT TO USE LINKED LISTS */ return NULL; } // Returns next element in the list list_node_t* list_next(list_node_t* node) { /* IMPLEMENT THIS IF YOU WANT TO USE LINKED LISTS */ return NULL; } // Returns data in the given list node void* list_data(list_node_t* node) { /* IMPLEMENT THIS IF YOU WANT TO USE LINKED LISTS */ return NULL; } // Returns the number of elements in the list size_t list_count(list_t* list) { /* IMPLEMENT THIS IF YOU WANT TO USE LINKED LISTS */ return 0; } // Finds the first node in the list with the given data // Returns NULL if data could not be found list_node_t* list_find(list_t* list, void* data) { /* IMPLEMENT THIS IF YOU WANT TO USE LINKED LISTS */ return NULL; } // Inserts a new node in the list with the given data void list_insert(list_t* list, void* data) { /* IMPLEMENT THIS IF YOU WANT TO USE LINKED LISTS */ } // Removes a node from the list and frees the node resources void list_remove(list_t* list, list_node_t* node) { /* IMPLEMENT THIS IF YOU WANT TO USE LINKED LISTS */ } // Executes a function for each element in the list void list_foreach(list_t* list, void (*func)(void* data)) { /* IMPLEMENT THIS IF YOU WANT TO USE LINKED LISTS */ } __MACOSX/concurrencylab-div-dos/._linked_list.c concurrencylab-div-dos/Vagrantfile # -*- mode: ruby -*- # vi: set ft=ruby : # All Vagrant configuration is done below. The "2" in Vagrant.configure # configures the configuration version (we support older styles for # backwards compatibility). Please don't change it unless you know what # you're doing. Vagrant.configure("2") do |config| config.vm.box = "ubuntu/bionic64" # Customize the number of cores and amount of memory on the VM: config.vm.provider "virtualbox" do |vb| vb.cpus = "2" vb.memory = "512" end # Setup default packages and configuration files config.vm.provision "shell", inline: <<-SHELL apt-get update apt-get install -y build-essential gcc-multilib emacs htop gdb valgrind for i in `ls /home`; do echo 'cd /vagrant' >>/home/${i}/.bashrc; done for i in `ls /home`; do curl http://www.cse.psu.edu/~tuz68/.emacs 2>/dev/null >/home/${i}/.emacs; chown ${i}:${i} /home/${i}/.emacs; done for i in `ls /home`; do curl https://raw.githubusercontent.com/mitthu/cmpsc473_spring18/master/base/dot_vimrc 2>/dev/null >/home/${i}/.vimrc; chown ${i}:${i} /home/${i}/.vimrc; done SHELL end __MACOSX/concurrencylab-div-dos/._Vagrantfile concurrencylab-div-dos/test.c #include <stdio.h> #include "channel.h" #include <assert.h> #include <unistd.h> #include <stdint.h> #include <stdlib.h> #include <time.h> #include <sys/resource.h> #include <string.h> #include <stdbool.h> #include "stress.h" #include "stress_send_recv.h" #define mu_str_(text) #text #define mu_str(text) mu_str_(text) #define mu_assert(message, test) do { if (!(test)) return "FAILURE: See " __FILE__ " Line " mu_str(__LINE__) ": " message; } while (0) #define mu_run_test(test) do { char *message = test(); tests_run++; \ if (message) return message; } while (0) typedef struct { channel_t *channel; void *data; enum channel_status out; sem_t *done; } send_args; typedef struct { channel_t *channel; void *data; enum channel_status out; sem_t *done; } receive_args; typedef struct { select_t *select_list; size_t list_size; sem_t *done; enum channel_status out; size_t index; } select_args; typedef struct { long double data; pthread_t pid; } cpu_args; int tests_run = 0; int tests_passed = 0; int string_equal(const char* str1, const char* str2) { if ((str1 == NULL) && (str2 == NULL)) { return 1; } if ((str1 == NULL) || (str2 == NULL)) { return 0; } return (strcmp(str1, str2) == 0); } void init_object_for_send_api(send_args* new_args, channel_t* channel, char* message, sem_t* done) { new_args->channel = channel; new_args->data = message; new_args->out = GEN_ERROR; new_args->done = done; } void init_object_for_receive_api(receive_args* new_args, channel_t* channel, sem_t* done) { new_args->channel = channel; new_args->data = NULL; new_args->out = GEN_ERROR; new_args->done = done; } void init_object_for_select_api(select_args* new_args, select_t *list, size_t list_size, sem_t* done) { new_args->select_list = list; new_args->list_size = list_size; new_args->out = GEN_ERROR; new_args->index = list_size; new_args->done = done; } void print_test_details(const char* test_name, const char* message) { printf("Running test case: %s : %s ...\n", test_name, message); } void* helper_send(send_args *myargs) { myargs->out = channel_send(myargs->channel, myargs->data); if (myargs->done) { sem_post(myargs->done); } return NULL; } void* helper_receive(receive_args *myargs) { myargs->out = channel_receive(myargs->channel, &myargs->data); if (myargs->done) { sem_post(myargs->done); } return NULL; } void* helper_select(select_args *myargs) { myargs->out = channel_select(myargs->select_list, myargs->list_size, &myargs->index); if (myargs->done) { sem_post(myargs->done); } return NULL; } void* helper_non_blocking_send(send_args *myargs) { myargs->out = channel_non_blocking_send(myargs->channel, myargs->data); if (myargs->done) { sem_post(myargs->done); } return NULL; } void* helper_non_blocking_receive(receive_args* myargs) { myargs->out = channel_non_blocking_receive(myargs->channel, &myargs->data); if (myargs->done) { sem_post(myargs->done); } return NULL; } char* test_initialization() { print_test_details(__func__, "Testing the channel intialization"); /* In this part of code we are creating a channel and checking if its intialization is correct */ size_t capacity = 10000; channel_t* channel = channel_create(capacity); mu_assert("test_initialization: Could not create channel\n", channel != NULL); mu_assert("test_initialization: Did not create buffer\n", channel->buffer != NULL); mu_assert("test_initialization: Buffer size is not as expected\n", buffer_current_size(channel->buffer) == 0); mu_assert("test_initialization: Buffer capacity is not as expected\n", buffer_capacity(channel->buffer) == capacity); channel_close(channel); channel_destroy(channel); return NULL; } #define NS_PER_SEC 1000000000ull uint64_t convertSecondsToTime(double sec) { return (uint64_t)(sec * (double)(NS_PER_SEC)); } double convertTimeToSeconds(uint64_t t) { return (double)(t) / (double)(NS_PER_SEC); } uint64_t convertTimespecToTime(struct timespec* t) { return (uint64_t)t->tv_sec * NS_PER_SEC + (uint64_t)t->tv_nsec; } void convertTimeToTimespec(uint64_t t, struct timespec* out) { out->tv_sec = (time_t)(t / NS_PER_SEC); out->tv_nsec = (long)(t % NS_PER_SEC); } uint64_t getTime() { struct timespec now; clock_gettime(CLOCK_MONOTONIC, &now); return convertTimespecToTime(&now); } void* average_cpu_utilization(cpu_args* myargs) { struct rusage usage1; struct rusage usage2; getrusage(RUSAGE_SELF, &usage1); struct timeval start = usage1.ru_utime; struct timeval start_s = usage1.ru_stime; sleep(20); getrusage(RUSAGE_SELF, &usage2); struct timeval end = usage2.ru_utime; struct timeval end_s = usage2.ru_stime; long double result = (end.tv_sec - start.tv_sec)*1000000L + end.tv_usec - start.tv_usec + (end_s.tv_sec - start_s.tv_sec)*1000000L + end_s.tv_usec - start_s.tv_usec; myargs->data = result; return NULL; } char* test_send_correctness() { print_test_details(__func__, "Testing the send correctness"); /* In this part of code we create a channel with capacity 2 and spawn 3 threads to call send API. * Expected response: 2 threads should return and one should be blocked */ size_t capacity = 2; channel_t* channel = channel_create(capacity); pthread_t pid[3]; sem_t send_done; sem_init(&send_done, 0, 0); // Send first Message send_args new_args; init_object_for_send_api(&new_args, channel, "Message1", &send_done); pthread_create(&pid[0], NULL, (void *)helper_send, &new_args); // wait before checking if its still blocking sem_wait(&send_done); mu_assert("test_send_correctness: Testing channel size failed" , buffer_current_size(channel->buffer) == 1); mu_assert("test_send_correctness: Testing channel value failed", string_equal(peek_buffer(channel->buffer, 0), "Message1")); mu_assert("test_send_correctness: Testing channel return failed", new_args.out == SUCCESS); // Send second message send_args new_args_1; init_object_for_send_api(&new_args_1, channel, "Message2", &send_done); pthread_create(&pid[1], NULL, (void *)helper_send, &new_args_1); // wait before checking if its still blocking sem_wait(&send_done); mu_assert("test_send_correctness: Testing buffer size failed" , buffer_current_size(channel->buffer) == 2); mu_assert("test_send_correctness: Testing channel values failed", string_equal(peek_buffer(channel->buffer, 0), "Message1")); mu_assert("test_send_correctness: Testing channel values failed", string_equal(peek_buffer(channel->buffer, 1), "Message2")); mu_assert("test_send_correctness: Testing channel return failed", new_args_1.out == SUCCESS); // Send third thread send_args new_args_2; init_object_for_send_api(&new_args_2, channel, "Message3", &send_done); pthread_create(&pid[2], NULL, (void *)helper_send, &new_args_2); usleep(10000); mu_assert("test_send_correctness: Testing buffer size failed" , buffer_current_size(channel->buffer) == 2); mu_assert("test_send_correctness: Testing channel values failed", string_equal(peek_buffer(channel->buffer, 0), "Message1")); mu_assert("test_send_correctness: Testing channel values failed", string_equal(peek_buffer(channel->buffer, 1), "Message2")); mu_assert("test_send_correctness: Testing channel values failed", new_args_2.out == GEN_ERROR); // Receiving from the channel to unblock void* out = NULL; channel_receive(channel, &out); for (size_t i = 0; i < 3; i++) { pthread_join(pid[i], NULL); } // Empty channel again channel_receive(channel, &out); channel_receive(channel, &out); // Checking for NULL as a acceptable value void* data = NULL; channel_send(channel, data); channel_send(channel, data); mu_assert("test_send_correctness: Testing buffer size failed" , buffer_current_size(channel->buffer) == 2); mu_assert("test_send_correctness: Testing null value", peek_buffer(channel->buffer, 0) == NULL); mu_assert("test_send_correctness: Testing null value", peek_buffer(channel->buffer, 1) == NULL); // Clearing the memory channel_close(channel); channel_destroy(channel); sem_destroy(&send_done); return NULL; } char* test_receive_correctness() { print_test_details(__func__, "Testing the receive correctness"); /* This test creates a channel of size 2 and calls receive thrice. The expectation * is that the last one is blocked. */ size_t capacity = 2; channel_t* channel = channel_create(capacity); size_t RECEIVER_THREAD = 2; receive_args data_rec[RECEIVER_THREAD]; // Filling channel with messages channel_send(channel, "Message4"); channel_send(channel, "Message5"); // Checking if the basic receives works void* out = NULL; channel_receive(channel, &out); mu_assert("test_receive_correctness: Testing buffer size failed 1\n" , buffer_current_size(channel->buffer) == 1); mu_assert("test_receive_correctness: Testing channel values failed 1\n", string_equal(out, "Message4")); void* out1 = NULL; channel_receive(channel, &out1); mu_assert("test_receive_correctness: Testing buffer size failed 2\n" , buffer_current_size(channel->buffer) == 0); mu_assert("test_receive_correctness: Testing channel values failed 2\n", string_equal(out1, "Message5")); pthread_t pid[RECEIVER_THREAD]; sem_t done; sem_init(&done, 0, 0); // Start two threads with receives, then send to channel one by one. for (size_t i = 0; i < RECEIVER_THREAD; i++) { init_object_for_receive_api(&data_rec[i], channel, &done); pthread_create(&pid[i], NULL, (void *)helper_receive, &data_rec[i]); } // Sleep is to wait before checking if receive calls are still blocked. usleep(10000); mu_assert("test_receive_correctness: Testing channel size failed", buffer_current_size(channel->buffer) == 0); mu_assert("test_receive_correctness: Testing channel return failed", data_rec[0].out == GEN_ERROR); mu_assert("test_receive_correctness: Testing channel return failed" , data_rec[1].out == GEN_ERROR); channel_send(channel, "Message1"); sem_wait(&done); mu_assert("test_receive_correctness: Testing channel return failed" , (data_rec[0].out == SUCCESS || data_rec[1].out == SUCCESS )); mu_assert("test_receive_correctness: Testing channel return failed" , !(data_rec[0].out == SUCCESS && data_rec[1].out == SUCCESS )); mu_assert("test_receive_correctness: Testing channel return failed" , string_equal(data_rec[0].data, "Message1") || string_equal(data_rec[1].data, "Message1")); channel_send(channel, "Message2"); sem_wait(&done); mu_assert("test_receive_correctness: Testing channel return failed" , (data_rec[0].out == SUCCESS && data_rec[1].out == SUCCESS )); mu_assert("test_receive_correctness: Testing channel return failed" , string_equal(data_rec[0].data, "Message2") || string_equal(data_rec[1].data, "Message2")); for (size_t i = 0; i < RECEIVER_THREAD; i++) { pthread_join(pid[i], NULL); } // Checking for the NULL values in receive void* temp = (void*)0xdeadbeef; channel_send(channel, NULL); channel_receive(channel, &temp); mu_assert("test_receive_correctness: Testing NULL value from channel" , temp == NULL); channel_close(channel); channel_destroy(channel); sem_destroy(&done); return NULL; } char* test_overall_send_receive() { print_test_details(__func__, "Testing send and receive overall"); /* This test spwans 10 send and receive requests. The expectation is that none of the * calls should get blocked. */ size_t capacity = 2; channel_t* channel = channel_create(capacity); size_t RECEIVE_THREAD = 10; size_t SEND_THREAD = 10; pthread_t rec_pid[RECEIVE_THREAD]; pthread_t send_pid[SEND_THREAD]; receive_args data_rec[RECEIVE_THREAD]; send_args data_send[SEND_THREAD]; // Spawning multiple send and receives for (size_t i = 0; i < RECEIVE_THREAD; i++) { init_object_for_receive_api(&data_rec[i], channel, NULL); pthread_create(&rec_pid[i], NULL, (void *)helper_receive, &data_rec[i]); } for (size_t i = 0; i < SEND_THREAD; i++) { init_object_for_send_api(&data_send[i], channel, "Message1", NULL); pthread_create(&send_pid[i], NULL, (void *)helper_send, &data_send[i]); } for (size_t i = 0; i < RECEIVE_THREAD; i++) { pthread_join(rec_pid[i], NULL); } for (size_t i = 0; i < SEND_THREAD; i++){ pthread_join(send_pid[i], NULL); } for (size_t i = 0; i < SEND_THREAD; i++) { mu_assert("test_overall_send_receive: Testing channel send return failed" , data_send[i].out == SUCCESS); } for (size_t i = 0; i < RECEIVE_THREAD; i++) { mu_assert("test_overall_send_receive: Testing channel receive return value failed" , data_rec[i].out == SUCCESS); mu_assert("test_overall_send_receive: Testing channel receive return data failed" , string_equal(data_rec[i].data, "Message1")); } channel_close(channel); channel_destroy(channel); return NULL; } char* test_non_blocking_send() { print_test_details(__func__, "Testing non_blocking send"); /* This test ensures that when you try to send more number of messages * than what the channel can handle, non-blocking send should return with proper status. */ size_t capacity = 2; channel_t* channel = channel_create(capacity); size_t SEND_THREAD = 10; pthread_t send_pid[SEND_THREAD]; send_args data_send[SEND_THREAD]; for (size_t i = 0; i < SEND_THREAD; i++) { init_object_for_send_api(&data_send[i], channel, "Message1", NULL); pthread_create(&send_pid[i], NULL, (void *)helper_non_blocking_send, &data_send[i]); } for (size_t i = 0; i < SEND_THREAD; i++){ pthread_join(send_pid[i], NULL); } size_t send_count = 0; for (size_t i = 0; i < SEND_THREAD; i++) { if (data_send[i].out == CHANNEL_FULL) { send_count ++; } } mu_assert("test_non_blocking_send: Testing channel send return value failed" , (send_count == SEND_THREAD - capacity)); channel_close(channel); channel_destroy(channel); return NULL; } char* test_non_blocking_receive() { print_test_details(__func__, "Testing non blocking receive"); /* This test ensures that when you try to receive more number of messages * than what the channel contains, non-blocking receive should return with proper status. */ size_t capacity = 2; channel_t* channel = channel_create(capacity); for (size_t i = 0; i < capacity; i++) { channel_send(channel, "Message"); } size_t RECEIVE_THREAD = 10; size_t SEND_THREAD = 3; pthread_t send_pid[SEND_THREAD]; pthread_t rec_pid[RECEIVE_THREAD]; receive_args data_rec[RECEIVE_THREAD]; send_args data_send[SEND_THREAD]; init_object_for_send_api(&data_send[0], channel, "Message1", NULL); pthread_create(&send_pid[0], NULL, (void *)helper_send, &data_send[0]); init_object_for_send_api(&data_send[1], channel, "Message2", NULL); pthread_create(&send_pid[1], NULL, (void *)helper_send, &data_send[1]); init_object_for_send_api(&data_send[2], channel, "Message3", NULL); pthread_create(&send_pid[2], NULL, (void *)helper_send, &data_send[2]); for (size_t i = 0; i < RECEIVE_THREAD; i++) { init_object_for_receive_api(&data_rec[i], channel, NULL); pthread_create(&rec_pid[i], NULL, (void *)helper_non_blocking_receive, &data_rec[i]); // Allow time for sends to take effect usleep(100000); } size_t receive_count = 0; int message_received = 0; int message1_received = 0; int message2_received = 0; int message3_received = 0; for (size_t i = 0; i < SEND_THREAD; i++) { pthread_join(send_pid[i], NULL); } for (size_t i = 0; i < RECEIVE_THREAD; i++) { pthread_join(rec_pid[i], NULL); } for (size_t i = 0; i < RECEIVE_THREAD; i++) { if (data_rec[i].out == CHANNEL_EMPTY) { receive_count ++; } else { if (string_equal(data_rec[i].data, "Message")) { message_received++; } else if (string_equal(data_rec[i].data, "Message1")) { message1_received++; } else if (string_equal(data_rec[i].data, "Message2")) { message2_received++; } else if (string_equal(data_rec[i].data, "Message3")) { message3_received++; } else { mu_assert("test_non_blocking_receive: Rece

CMPSC473, Spring 2020 Concurrency Lab: Channels in C Due: Thu., Mar 26 at Noon Introduction Note that the assignment is due at noon. Concurrent programming is hard – start early. A channel is a model for synchronization via message passing. Messages may be sent over a channel by a thread (Sender) and other threads which have a reference to this channel can receive them (Receivers). A channel can have multiple senders and receivers referencing it at any point of time. Channels are used as a primitive to implement various other concurrent programming constructs. For example, channels are heavily used in Google’s Go programming language and are very useful frameworks for high-level concurrent programming. In this lab you will be writing your own version of a channel which will be used to communicate among multiple clients. A client can either write onto the channel or read from it. Keep in mind that multiple clients can read and write simultaneously from the channel. You are encouraged to explore the design space creatively and implement a channel that is correct and not exceptionally slow or inefficient. Performance is not the main concern in this assignment (functionality is the main concern), but your implementation should avoid inefficient designs that sleep for any fixed time or unnecessarily waste CPU time. There are multiple variations to channels, such as whether the send/receive is blocking or non-blocking. In blocking mode, receivers always block until there is data to receive, whereas in non-blocking mode, they simply return. Similarly, with senders, in blocking mode, if the buffer is full, senders wait until some receiver has retrieved a value and there is available space in the buffer whereas in non-blocking mode, they simply leave without sending. In this lab, you will support both blocking and non-blocking send/receive functions. Another variation to channels would be if a channel is buffered (i.e., channel buffer size > 0) or unbuffered (i.e., channel buffer size = 0). In the buffered case, the sender blocks only until the value has been copied to the buffer. On the other hand, if the channel is unbuffered, the sender blocks until the receiver has received the value. In this lab, you will only be responsible for supporting buffered channels. Supporting unbuffered channels is extra credit and is especially difficult when implementing select. The amount of extra credit is really small for the amount and difficulty of work involved, and correctly implementing the unbuffered version for select is probably 2-3 times the work of the entire buffered assignment. The only files you will be modifying are channel.c and channel.h and optionally linked_list.c and linked_list.h. You should NOT make any changes in any file besides these four files. You will be implementing the following functions, which are described in channel.c and channel.h: • channel_t* channel_create(size_t size) • enum channel_status channel_send(channel_t* channel, void* data) • enum channel_status channel_receive(channel_t* channel, void** data) • enum channel_status channel_non_blocking_send(channel_t* channel, void* data) • enum channel_status channel_non_blocking_receive(channel_t* channel, void** data) • enum channel_status channel_close(channel_t* channel) • enum channel_status channel_destroy(channel_t* channel) • enum channel_status channel_select(select_t* channel_list, size_t channel_count, size_t* selected_index) The enum channel_status is a named enumeration type that is defined in channel.h. Rather than using an int, which can be any number, enumerations are integers that should match one of the defined values. For example, if you want to return that the function succeeded, you would just return SUCCESS. You are encouraged to define other (static) helper functions, structures, etc. to help structure the code in a better way. Support routines The buffer.c and buffer.h files contain the helper constructs for you to create and manage a buffered channel. These functions will help you separate the buffer management from the concurrency issues in your channel code. Please note that these functions are NOT thread-safe. You are welcome to use any of these functions, but you should not change them. • buffer_t* buffer_create(size_t capacity) Creates a buffer with the given capacity. • enum buffer_status buffer_add(buffer_t* buffer, void* data) Adds the value into the buffer. Returns BUFFER_SUCCESS if the buffer is not full and value was added. Returns BUFFER_ERROR otherwise. • enum buffer_status buffer_remove(buffer_t* buffer, void** data) Removes the value from the buffer in FIFO order and stores it in data. Returns BUFFER_SUCCESS if the buffer is not empty and a value was removed. Returns BUFFER_ERROR otherwise. • void buffer_free(buffer_t* buffer) Frees the memory allocated to the buffer. • size_t buffer_capacity(buffer_t* buffer) Returns the total capacity of the buffer. • size_t buffer_current_size(buffer_t* buffer) Returns the current number of elements in the buffer. We have also provided the optional interface for a linked list in linked_list.c and linked_list.h. You are welcome to implement and use this interface in your code, but you are not required to implement it if you don’t want to use it. It is primarily provided to help you structure your code in a clean fashion if you want to use linked lists in your code. Linked lists may NOT be needed depending on your design, so do not try to force it into your solution. You can add/change/remove any of the functions in linked_list.c and linked_list.h as you see fit. Programming rules You are not allowed to take any of the following approaches to complete the assignment: • Spinning in a polling loop to implement blocking calls • Sleeping for any fixed amount of time; instead, use cond_wait or sem_wait • Trying to change the timing of your code to hide bugs such as race conditions • Using global variables in your code You are only allowed to use the pthread library, the POSIX semaphore library, basic standard C library functions (e.g., malloc/free), and the provided code in the assignment for completing your implementation. If you think you need some library function, please contact the course staff to determine the eligibility. You can find a reference/tutorial for the pthread library at: https://computing.llnl.gov/tutorials/pthreads/ You can find a reference/tutorial for the POSIX semaphore library at: http://www.csc.villanova.edu/~mdamian/threads/posixsem.html Looking at documentation (e.g., for these libraries, for tools, etc.) is fine, but as stated in the academic integrity policy, looking online for any hints about implementing channels is disallowed. Evaluation and testing your code You will receive zero points if: • You violate the academic integrity policy (sanctions can be greater than just a 0 for the assignment) • You break any of the programming rules • Your code does not compile/build • Your code crashes the grading script • You don’t show your partial work by periodically adding, committing, and pushing your code to GitHub Your code will be evaluated for correctness, properly handling synchronization, and ensuring it does not violate any of the programming rules (e.g., do not spin or sleep for any period of time). We have provided many tests, but we reserve the right to add additional tests during the final grading, so you are responsible for ensuring your code is correct, where a large part of correctness is ensuring you don’t have race conditions, deadlocks, or other synchronization bugs. To run the supplied test cases, simply run the following command in the project folder: make test make test will compile your code in release mode and run the grade.py script, which runs a combination of the following tests to autograde your assignment: • After running the make command in your project, two executable files will be created. The default executable, channel, is used to run test cases in the normal mode. The test cases are located in test.c, and you can find the list of tests at the bottom of the file. If you want to run a single test, run the following: ./channel [test_case_name] [iters] where [test_case_name] is the test name and [iters] is the number of times to run the test. If you do not provide a test name, all tests will be run. The default number of iterations is 1. • The other executable, channel_sanitize, will be used to help detect data races in your code. It can be used with any of the test cases by replacing ./channel with ./channel_sanitize. ./channel_sanitize [test_case_name] [iters] Any detected data races will be output to the terminal. You should implement code that does not generate any errors or warnings from the data race detector. • Valgrind is being used to check for memory leaks, report uses of uninitialized values, and detect memory errors such as freeing a memory space more than once. To run a valgrind check by yourself, use the command: valgrind -v --leak-check=full ./channel [test_case_name] [iters] Note that channel_sanitize should not be run with valgrind as the tools do not behave well together. Only the channel executable should be used with valgrind. Valgrind will issue messages about memory errors and leaks that it detects for you to fix them. You should implement code that does not generate any valgrind errors or warnings. IMPORTANT: Note that any test FAILURE may result in the sanitizer or valgrind reporting thread leaks or memory leaks. This is expected since test failures will cause the test to prematurely end without cleaning up any threads or memory. Thus, you should first fix the test failure. Handin Similar to the last assignment, we will be using GitHub for managing submissions, and you must show your partial work by periodically adding, committing, and pushing your code to GitHub. This helps us see your code if you ask any questions on Canvas (please include your GitHub username) and also helps deter academic integrity violations. Additionally, please input the desired commit number that you would like us to grade in the Canvas assignment. You can get the commit number from github.com. In your repository, click on the commits link to the left above your files. Find the commit from the appropriate day/time that you want committed. Click on the clipboard icon to copy the commit number. Note that this is a much longer number than the displayed number. Paste your very long commit number and only your commit number in this assignment submission textbox. Hints • Carefully read the output from the sanitizer and valgrind tools and think about what they’re trying to say. Usually, they’re printing call stacks to tell you which locations have race conditions, or which locations allocate some memory that was being accessed in the race condition, or which locations allocate some memory that is being leaked, etc. These tools are tremendously useful, which is why we’ve set them up for you for this assignment. • While the tools are very useful, they are not perfect. Some race conditions are rare and don’t show up all the time. A reasonable approach to debugging these race condition bugs is to try to identify the symptoms of the bug and then read your code to see if you can figure out the sequence of events that caused the bug based on the symptoms. • Debugging with gdb is a useful way of getting information about what’s going on in your code. To compile your code in debug mode (to make it easier to debug with gdb), you can simply run: make debug It is important to realize that when trying to find race conditions, the reproducibility of the race condition often depends on the timing of events. As a result, sometimes, your race condition may only show up in non-debug (i.e., release) mode and may disappear when you run it in debug mode. Bugs may sometimes also disappear when running with gdb or if you add print statements. Bugs that only show up some of the time are still bugs, and you should fix these. Do not try to change the timing to hide the bugs. • If your bug only shows up outside of gdb, one useful approach is to look at the core dump (if it crashes). Here’s a link to a tutorial on how to get and use core dump files: http://yusufonlinux.blogspot.com/2010/11/debugging-core-using-gdb.html • If your bug only shows up outside of gdb and causes a deadlock (i.e., hangs forever), one useful approach is to attach gdb to the program after the fact. To do this, first run your program. Then in another command prompt terminal run: ps aux This will give you a listing of your running programs. Find your program and look at the PID column. Then within gdb (may require sudo) run: attach <PID> where you replace <PID> with the PID number that you got from ps aux. This will give you a gdb debugging session just like if you had started the program with gdb.

Related Questions

Similar orders to Channels in C
21
Views
0
Answers
Nested imbalanced design of expriment using Box-Adjusted wald-type test
I need to provide statistical analysis of a nested non-balanced design of an experiment. I am would like to have the implementation R. I will need the answers to be provided as shown in the attached file (Project.pdf), and also would like to have access to...
34
Views
0
Answers
CMPT 200 Coding Homework
Write a class called Fraction that can store a rational number (reminder: those numbers that can be expressed in the form a/b, where a and b are integers are rational numbers). For example, a variable with a value of ½ would be created using oneHalf ...
15
Views
0
Answers
Artificial Inteligence System Technique
This is a Master Degree course and I have attached example questions, there are 5 questions and only 3 need to be answered. We will get the actual questions on the day of the exam and they need to be completed within 2 hours, which means the expert has to ...