In this project, you will write a multi-threaded program to compute a hash value of a given file. The size of the file can be very large. So, there is a need for the program to be multi-threaded to achieve speedup. While one thread reads a part (block) of the file, other threads can compute hash values of already read blocks.

Binary tree threads

Create a binary tree of threads where each thread will compute the hash value

Hash value

The hash value of a string (very long) is a fixed length numeric value. Hash values are typically expressed in hex digits and can be long. In this project we will restrict the hash value type to a 32-bit unsigned integer. A hashing algorithm will read the input string (file) and produce a hash value. There are many hashing algorithms in the literature. For this project we will use Jenkins one_at_a_time hash described in

One of the uses of hash value is to check the integrity of the data (file, database, etc.). One can think of a hash value of a file as a fingerprint of the file. If the file is modified, then the hash value also changes. By comparing the new and old hash values one can easily detect that the file was modified.

Computation of a hash value of a large file (several giga bytes in size) may take a while. Hence a need for a multi-threaded program.

Part 1: Multi-threaded hashing

A file can be divided into multiple blocks. The basic unit of accessing a file on a i/o device is a block. Assume there are n blocks, m threads, and n is divisible by m. Each thread can compute the hash value of n/m consecutive blocks. Several of these hash values are then combined to form a string whose hash value can be computed as before. These steps can be repeated till one final hash value remain.

A complete binary tree of threads should be created. Each leaf thread will compute the hash value of n/m consecutive blocks assigned to it and return the hash value to its parent thread (through pthread_exit() call). An interior thread will compute the hash value of the blocks assigned to it, and then wait for its children to return hash values. These hash values should be combined to form a string: <computed hash value + hash value from left child + hash value from right child>. (Note that the + sign here means concatenation and not addition. Also, if the interior thread has no right child, only the hash value of the interior thread and the hash value from the left child are combined.) The interior thread then computes hash value of the concatenated string as before and returns the value to its parent, The value returned by the root thread is the hash value of the file.

How to assign blocks to threads?

Each thread is assigned a number when it is created. The number of root thread is 0. For a thread with number i, the number of its left child is 2 * i + 1, and the number of its right child is 2 * i +

2. For a thread with number i, n/m consecutive blocks starting from block number i * n/m are assigned. For example, let n = 100 and m = 4. Then thread 0 will be assigned blocks 0 through 24, thread 1 will be assigned blocks 25 through 49, thread 2 will be assigned blocks 50 through 74, and thread 3 will be assigned blocks 75 through 99.

Usage and hints

Name your program htree.c. The usage is:

htree filename num_threads

‘filename’ is the name of the input file whose hash value needs to be computed. ‘num_threads’ is

the number of threads to be created.

Assume the block size to be 4096 bytes. Number of blocks can be found from the file size in bytes. Check fstat() to find the file size.

You can read any block from the input file using lseek(0 and read(). But there is an easier way to read blocks from a file using mmap(). Check the man page for mmap().

You can use sprintf() to convert an uint to string.

Part 2: Experimental study

The main goal of this study is to find speedup achieved when the number of threads is increased for various input files. For each input file, find the time taken to compute the hash value for 1, 4, 16, 32, 64, 128, and 256 threads. To run 256 threads, increase ulimit -u to 256.

Plot a graph with time on y-axis, and #threads on x-axis for each input file. Plot another graph with speedup on y-axis and #threads on x-axis for each input file.

speedup = (time taken for single thread)/(time taken for n threads)

Write a short report on what you observe. It is expected that the time taken to compute hash value decrease when the number of threads increase. Does it always happen? What is the speed-up achieved when the number of threads increased? Is the speedup proportional to the number of threads increased? Also, briefly describe the experimental set-up at the beginning of your report. (Command ‘lscpu’ provides relevant information for this)

Write a high-quality report. You should showcase the report in your job interview.

Other Requirements

Error handling is an important concept in system programming. In general, there should be no circumstances in which your C program will core dump, hang indefinitely, or prematurely terminate. Therefore, your program must respond to all input in a reasonable manner; by “reasonable”, we mean print an understandable error message and either continue processing or exit, depending upon the situation.

So, check the input for errors. Check the return values of function calls. Display appropriate error messages.

CODE THAT I HAVE SO FAR

Issues: Does not run for files over 2GB runs into segmenation fault

The multi-threading is not working as expected – each thread should calculate the hash and return the hash value to the parent to further combine the hash

As the threads are increased the time elapsed is increasing or the same as 1 thread regardless of the file size (1MG, 1GB, 2GB)

#include <stdio.h>

#include <stdlib.h>

#include <stdint.h>

#include <inttypes.h>

#include <errno.h>

#include <fcntl.h>

#include <unistd.h>

#include <sys/types.h>

#include <sys/stat.h>

#include <pthread.h>

#include <string.h>

#include <sys/mman.h>

#define BSIZE 4096

struct node

{

    uint32_t hash;

    int32_t num_blocks;

    int32_t start_block;

    int32_t end_block;

    pthread_t thread_id;

    struct node *left_child;

    struct node *right_child;

};

struct thread_args

{

    struct node *node_ptr;

    int32_t thread_num;

    int32_t num_threads;

    uint8_t *file_ptr;

};

struct stat file_info;

void usage(char *);

uint32_t jenkins_one_at_a_time_hash(const uint8_t *, uint64_t);

void compute_hash(struct node *, uint8_t *);

void *compute_node_hash(void *);

void process_inputs(char *file_name, uint8_t **file_ptr, uint32_t *num_blocks, uint32_t *num_threads, struct stat *file_info);

int main(int argc, char **argv)

{

    // int32_t fd;

    uint32_t num_threads, num_blocks;

    uint8_t *file_ptr;

    // struct stat file_info;

    struct node *root;

    struct timespec start, end;

    double elapsed;

    // input checking

    if (argc != 3)

        usage(argv[0]);

    num_threads = atoi(argv[2]);

    // input checking and file processing

    process_inputs(argv[1], &file_ptr, &num_blocks, &num_threads, &file_info);

    clock_gettime(CLOCK_MONOTONIC, &start);

    // construct hash tree

    root = (struct node *)malloc(sizeof(struct node));

    root->num_blocks = num_blocks;

    root->start_block = 0;

    root->end_block = num_blocks – 1;

    root->left_child = NULL;

    root->right_child = NULL;

    compute_hash(root, file_ptr);

    // create threads and compute hash values

    struct thread_args *args = (struct thread_args *)malloc(num_threads * sizeof(struct thread_args));

    for (uint32_t i = 0; i < num_threads; i++)

    {

        args[i].node_ptr = root;

        args[i].thread_num = i;

        args[i].num_threads = num_threads;

        args[i].file_ptr = file_ptr;

        pthread_create(&args[i].node_ptr->thread_id, NULL, compute_node_hash, (void *)&args[i]);

    }

    // wait for threads to complete

    for (uint32_t i = 0; i < num_threads; i++)

    {

        pthread_join(args[i].node_ptr->thread_id, NULL);

        printf(“tnum %d hash computed %” PRIu32 “\n”, i, args[i].node_ptr->hash);

        printf(“tnum %d hash from left child %” PRIu32 “\n”, i, args[i].node_ptr->left_child->hash);

        printf(“tnum %d hash from right child %” PRIu32 “\n”, i, args[i].node_ptr->right_child->hash);

        printf(“tnum %d hash sent to parent %” PRIu32 “\n”, i, args[i].node_ptr->hash);

    }

    // end_time = clock();

    clock_gettime(CLOCK_MONOTONIC, &end);

    printf(“num_threads = %u\n”, num_threads);

    printf(“Blocks per Thread = %u\n”, num_blocks / num_threads);

    printf(“hash value = %” PRIu32 “\n”, root->hash);

    elapsed = (end.tv_sec – start.tv_sec) + (end.tv_nsec – start.tv_nsec) / 1000000000.0;

    printf(“Time taken: %f seconds\n”, elapsed);

    // clean up

    munmap(file_ptr, file_info.st_size);

    free(root);

    free(args);

    return 0;

}

void compute_hash(struct node *node_ptr, uint8_t *file_ptr)

{

    if (node_ptr->num_blocks == 1)

    {

        node_ptr->hash = jenkins_one_at_a_time_hash(file_ptr + node_ptr->start_block * BSIZE, BSIZE);

        return;

    }

    // divide the node into two halves

    node_ptr->left_child = (struct node *)malloc(sizeof(struct node));

    node_ptr->right_child = (struct node *)malloc(sizeof(struct node));

    node_ptr->left_child->num_blocks = node_ptr->num_blocks / 2;

    node_ptr->left_child->start_block = node_ptr->start_block;

    node_ptr->left_child->end_block = node_ptr->start_block + node_ptr->left_child->num_blocks – 1;

    node_ptr->left_child->left_child = NULL;

    node_ptr->left_child->right_child = NULL;

    node_ptr->right_child->num_blocks = node_ptr->num_blocks – node_ptr->left_child->num_blocks;

    node_ptr->right_child->start_block = node_ptr->left_child->end_block + 1;

    node_ptr->right_child->end_block = node_ptr->end_block;

    node_ptr->right_child->left_child = NULL;

    node_ptr->right_child->right_child = NULL;

    // compute hash values of child nodes

    compute_hash(node_ptr->left_child, file_ptr);

    compute_hash(node_ptr->right_child, file_ptr);

    // combine hash values of child nodes

    node_ptr->hash = node_ptr->left_child->hash + node_ptr->right_child->hash;

}

void *compute_node_hash(void *arg)

{

    struct thread_args *args = (struct thread_args *)arg;

    struct node *node_ptr = args->node_ptr;

    uint8_t *file_ptr = args->file_ptr;

    int32_t thread_num = args->thread_num;

    int32_t num_threads = args->num_threads;

    if (node_ptr->left_child == NULL && node_ptr->right_child == NULL)

    {

        uint32_t block_start = node_ptr->start_block;

        uint32_t block_end = node_ptr->end_block;

        uint32_t block_size = block_end – block_start + 1;

        uint32_t num_blocks_per_thread = node_ptr->num_blocks / num_threads;

        uint32_t thread_block_start = block_start + thread_num * num_blocks_per_thread;

        uint32_t thread_block_end;

        if (thread_num == num_threads – 1)

            thread_block_end = block_end;

        else

            thread_block_end = thread_block_start + num_blocks_per_thread – 1;

        uint32_t thread_block_size = thread_block_end – thread_block_start + 1;

        uint8_t *thread_block_ptr = &file_ptr[thread_block_start * BSIZE];

        node_ptr->hash = jenkins_one_at_a_time_hash(thread_block_ptr, thread_block_size * BSIZE);

    }

    else

    {

        pthread_t left_thread_id, right_thread_id;

        struct thread_args left_args, right_args;

        left_args.node_ptr = node_ptr->left_child;

        right_args.node_ptr = node_ptr->right_child;

        left_args.thread_num = thread_num;

        right_args.thread_num = thread_num;

        left_args.num_threads = num_threads;

        right_args.num_threads = num_threads;

        left_args.file_ptr = file_ptr;

        right_args.file_ptr = file_ptr;

        pthread_create(&left_thread_id, NULL, compute_node_hash, (void *)&left_args);

        pthread_create(&right_thread_id, NULL, compute_node_hash, (void *)&right_args);

        pthread_join(left_thread_id, NULL);

        pthread_join(right_thread_id, NULL);

        node_ptr->hash = node_ptr->left_child->hash + node_ptr->right_child->hash;

    }

    return NULL;

}

uint32_t jenkins_one_at_a_time_hash(const uint8_t *key, uint64_t length)

{

    uint32_t hash, i;

    for (hash = i = 0; i < length; ++i)

    {

        hash += key[i];

        hash += (hash << 10);

        hash ^= (hash >> 6);

    }

    hash += (hash << 3);

    hash ^= (hash >> 11);

    hash += (hash << 15);

    return hash;

}

void usage(char *program_name)

{

    fprintf(stderr, “Usage: %s <input_file> <num_threads>\n”, program_name);

    exit(EXIT_FAILURE);

}

void process_inputs(char *file_name, uint8_t **file_ptr, uint32_t *num_blocks, uint32_t *num_threads, struct stat *file_info_ptr)

{

    int32_t fd;

    struct stat file_info;

    // input checking

    if (*num_threads <= 0)

    {

        fprintf(stderr, “Invalid number of threads.\n”);

        exit(EXIT_FAILURE);

    }

    // open input file

    fd = open(file_name, O_RDWR);

    if (fd == -1)

    {

        perror(“open failed”);

        exit(EXIT_FAILURE);

    }

    // use fstat to get file size and calculate number of blocks

    if (fstat(fd, &file_info) == -1)

    {

        perror(“fstat failed”);

        exit(EXIT_FAILURE);

    }

    *num_blocks = (uint32_t)(file_info.st_size / BSIZE);

    if (file_info.st_size % BSIZE != 0)

        (*num_blocks)++;

    // mmap file into memory

    *file_ptr = (uint8_t *)mmap(NULL, file_info.st_size, PROT_READ, MAP_PRIVATE, fd, 0);

    if (*file_ptr == MAP_FAILED)

    {

        perror(“mmap failed”);

        exit(EXIT_FAILURE);

    }

    close(fd);

    *file_info_ptr = file_info;

}

Get expert help for Multi-threaded hash tree Assignment and many more. 24X7 help, plag free solution. Order online now!