SHARE
TWEET

Untitled

a guest Nov 14th, 2019 102 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "request.h"
  2. #include "server_thread.h"
  3. #include "common.h"
  4. #include <pthread.h>
  5. #include "semaphore.h"
  6.  
  7.  
  8. /* REFACTORING IDEAS
  9.  *
  10.  *
  11.  * -    The evictQueue would be a super easy this to completely remake, all it has to do is keep
  12.  *      track of what are the most recently used files, if you look up LRU methods on google
  13.  *      there are a bunch of different implementations, the most common being to have a count
  14.  *      attached to each file, and every time a file is used, you reset that files count, but increment all other files counts,
  15.  *      and then to find the least recently used, you find the one with the highest count
  16.  *
  17.  * -    Should definitely reorganize the logic and the order of how things are called in
  18.  *      do_server_request() this will probably be super different between every project
  19.  *
  20.  * -    removeFileFromCache() and updateEvictQueue() both have a bunch of logic that essentially relates to navigating through
  21.  *      the linked list, this can probably be put into its own general function  
  22.  *
  23.  * -    Not storing hash in the file struct, might be suspicious. Recalculate new each time
  24.  *
  25.  * -    Generally, alot of the ways that I navigated and searched through the lists were
  26.  *      not the best way, so I think there are some good changes to make there.
  27.  */
  28.  
  29.  
  30.  
  31. struct server {
  32.     int nr_threads;
  33.     int max_requests;
  34.     int max_cache_size;
  35.     int exiting;
  36.     int size;
  37.     /* add any other parameters you need */
  38. };
  39.  
  40. struct file {
  41.     struct file_data * fileData;
  42.     unsigned long hash; // This would probably be pretty bait to keep in,
  43.                         // it is probably better to just recalculate the
  44.                         // hash each time you want to use it, as long as
  45.                         // it doest affect speed
  46.     struct file * nextFileInCache;
  47.     struct file * prevFileInCache;
  48.     struct file * nextFileInQueue;
  49.     struct file * prevFileInQueue;
  50.  
  51.     sem_t * sem;
  52.     pthread_mutex_t * lock;
  53.     int users;
  54.  
  55. };
  56.  
  57. struct fileCache{
  58.     int size;
  59.     int maxSize;
  60.     struct file **files;
  61. };
  62.  
  63. struct evictQueue{
  64.     struct file * leastRecent;
  65.     struct file * mostRecent; // I don't think I used this, you can get rid of it, or implement it
  66. };
  67.  
  68. pthread_t* threadPool;
  69. pthread_mutex_t* lock;
  70. pthread_cond_t* cvEmpty;
  71. pthread_cond_t* cvFull;
  72. int in;
  73. int out;
  74. int* buffer;
  75.  
  76. struct fileCache * fileCache;
  77. struct evictQueue * evictQueue;
  78. pthread_mutex_t * fileLock;
  79.  
  80.  
  81. unsigned long hash(char *str);
  82. struct file * cacheLookup(char * fileName);
  83. struct file * cacheInsert(struct file_data * fileData);
  84. void cacheEvict(int amountToEvict);
  85. void updateEvictQueue(struct file * file);
  86. void readFileFromDisk(struct request * rq, struct file_data * data);
  87. void removeFileFromCache(struct file * file);
  88.  
  89. /* static functions */
  90.  
  91. /* initialize file data */
  92. static struct file_data *
  93. file_data_init(void)
  94. {
  95.     struct file_data *data;
  96.  
  97.     data = Malloc(sizeof(struct file_data));
  98.     data->file_name = NULL;
  99.     data->file_buf = NULL;
  100.     data->file_size = 0;
  101.     return data;
  102. }
  103.  
  104. /* free all file data */
  105. static void
  106. file_data_free(struct file_data *data)
  107. {
  108.     free(data->file_name);
  109.     free(data->file_buf);
  110.     free(data);
  111. }
  112.  
  113. static void
  114. do_server_request(struct server *sv, int connfd)
  115. {
  116.     int ret;
  117.     struct request *rq;
  118.     struct file_data *data;
  119.  
  120.     data = file_data_init();
  121.  
  122.     /* fill data->file_name with name of the file being requested */
  123.     rq = request_init(connfd, data);
  124.  
  125.     if (!rq) {
  126.         file_data_free(data);
  127.         return;
  128.     }
  129.    
  130.     // If the there is no cache, just read that shit normally
  131.     if(sv->max_cache_size <= 0){
  132.         ret = request_readfile(rq);
  133.         if (ret != 0) request_sendfile(rq);
  134.         file_data_free(data);
  135.         request_destroy(rq);
  136.     }else{
  137.  
  138.         // Lock the datastructures
  139.         pthread_mutex_lock(fileLock);
  140.  
  141.         // Check if the file is in the cache, if it isn't 'file *' will be null
  142.         struct file * file = cacheLookup(data->file_name);
  143.    
  144.         if(file != NULL){
  145.  
  146.             // Update the file so that it is "in use"
  147.             pthread_mutex_lock(file->lock);
  148.             if(file->users == 0) sem_wait(file->sem);
  149.             file->users++;
  150.             pthread_mutex_unlock(file->lock);
  151.  
  152.             // Fill the request with the stored data from the file stored in the cache
  153.             request_set_data(rq, file->fileData);
  154.             // Update the evict queue to reflect that this file was recently used, ie put it at the back of the queue
  155.             updateEvictQueue(file);
  156.             // Unlock the data structures for before sending the request
  157.             pthread_mutex_unlock(fileLock);
  158.             // Send the request and destroy it
  159.             request_sendfile(rq);
  160.             request_destroy(rq);
  161.  
  162.             // Decrement the number of users
  163.             pthread_mutex_lock(file->lock);
  164.             file->users--;
  165.             if(file->users == 0) sem_post(file->sem);
  166.             pthread_mutex_unlock(file->lock);
  167.  
  168.         }else{
  169.             // Lock the data structues
  170.             pthread_mutex_unlock(fileLock);
  171.  
  172.             // Read the file from disk, send the request, then destroy it
  173.             ret = request_readfile(rq);
  174.             if (ret != 0) request_sendfile(rq);
  175.             request_destroy(rq);
  176.            
  177.  
  178.             // Cache the file, evict some space if nessecary
  179.             pthread_mutex_lock(fileLock);
  180.             if(cacheLookup(data->file_name) == NULL){
  181.                 if(data->file_size < fileCache->maxSize){
  182.                     if((data->file_size + fileCache->size) > fileCache->maxSize){
  183.                         cacheEvict(data->file_size - fileCache->maxSize + fileCache->size + 1);
  184.                     }
  185.                     file = cacheInsert(data);
  186.                     updateEvictQueue(file);
  187.                 }
  188.             }
  189.             pthread_mutex_unlock(fileLock);
  190.         }
  191.     }
  192. }
  193.  
  194. /* entry point functions */
  195.  
  196. // Searches the cache for a file, returns a pointer to it if it exists, NULL otherwise
  197. struct file * cacheLookup(char * fileName){
  198.  
  199.     if(strlen(fileName) == 0) {
  200.         return NULL;
  201.     }
  202.     long index = hash(fileName);
  203.  
  204.     if( fileCache->files[index] == NULL){
  205.         return NULL;
  206.      }else{
  207.  
  208.         struct file * file = fileCache->files[index];
  209.  
  210.         while(file != NULL && strcmp(file->fileData->file_name, fileName) != 0){
  211.             file = file->nextFileInCache;  
  212.         }
  213.  
  214.         return file;
  215.     }
  216. }
  217.  
  218. struct file * cacheInsert(struct file_data * fileData){
  219.  
  220.     struct file * newFile = malloc(sizeof(struct file));
  221.  
  222.     // Create the file
  223.     char * fileName = fileData->file_name;
  224.     newFile->fileData = fileData;
  225.     newFile->sem = malloc(sizeof(sem_t));
  226.     newFile->lock = malloc(sizeof(pthread_mutex_t));
  227.     sem_init(newFile->sem, 0, 1);
  228.     pthread_mutex_init(newFile->lock, NULL);
  229.     newFile->users = 0;
  230.     newFile->nextFileInQueue = NULL;
  231.     newFile->prevFileInQueue = NULL;
  232.     newFile->nextFileInCache = NULL;
  233.     newFile->prevFileInCache = NULL;
  234.  
  235.     if(strlen(fileName) == 0) return NULL;
  236.    
  237.     long index = hash(fileName);
  238.     newFile->hash = index;
  239.  
  240.     // If they cell is empty, place it at the top
  241.     if(fileCache->files[index] == NULL){
  242.         fileCache->files[index] = newFile;
  243.        
  244.     }else {
  245.         // Otherwise, navigate down the linked list until you've found the end
  246.         struct file * file = fileCache->files[index];
  247.  
  248.         while(file->nextFileInCache != NULL){
  249.             file = file->nextFileInCache;  
  250.         }
  251.  
  252.         file->nextFileInCache = newFile;
  253.         newFile->prevFileInCache = file;
  254.         newFile->nextFileInCache = NULL;
  255.     }
  256.  
  257.     fileCache->size += newFile->fileData->file_size;
  258.     return newFile;
  259.  
  260. }
  261.  
  262. void removeFileFromCache(struct file * file){
  263.  
  264.     // First and only
  265.     if(file->prevFileInCache == NULL && file->nextFileInCache == NULL){
  266.         fileCache->files[file->hash] = NULL;
  267.     }
  268.     // First
  269.     else if(file->prevFileInCache == NULL && file->nextFileInCache != NULL){
  270.         fileCache->files[file->hash] = file->nextFileInCache;
  271.         fileCache->files[file->hash]->prevFileInCache = NULL;
  272.         file->nextFileInCache = NULL;
  273.     }
  274.     // Last
  275.     else if(file->prevFileInCache != NULL && file->nextFileInCache == NULL){
  276.         file->prevFileInCache->nextFileInCache = NULL;
  277.         file->prevFileInCache = NULL;
  278.  
  279.     }
  280.     // Middle
  281.     else {
  282.         file->nextFileInCache->prevFileInCache = file->prevFileInCache;
  283.         file->prevFileInCache->nextFileInCache = file->nextFileInCache;
  284.         file->prevFileInCache = NULL;
  285.         file->nextFileInCache = NULL;
  286.     }
  287. }
  288.  
  289. void cacheEvict(int amountToEvict){
  290.    
  291.     struct file * fileToEvict;
  292.     int amountEvicted = 0;
  293.  
  294.     while(amountEvicted < amountToEvict && evictQueue->leastRecent != NULL){
  295.  
  296.         fileToEvict = evictQueue->leastRecent;
  297.  
  298.         evictQueue->leastRecent = fileToEvict->nextFileInQueue;
  299.         if(fileToEvict->nextFileInQueue != NULL)
  300.             fileToEvict->nextFileInQueue->prevFileInQueue = NULL;
  301.  
  302.         removeFileFromCache(fileToEvict);
  303.         fileCache->size -= fileToEvict->fileData->file_size;
  304.         amountEvicted += fileToEvict->fileData->file_size;
  305.  
  306.         // This semaphore is only released in do_server_request when the last request is done reading the file
  307.         sem_wait(fileToEvict->sem);
  308.        
  309.         fileToEvict->nextFileInQueue = NULL;
  310.         fileToEvict->prevFileInQueue = NULL;
  311.  
  312.         free(fileToEvict->sem);
  313.         free(fileToEvict->lock);
  314.         file_data_free(fileToEvict->fileData);
  315.         free(fileToEvict);
  316.     }
  317.  
  318. }
  319.  
  320. void updateEvictQueue(struct file * file){
  321.  
  322.     // Last and not only
  323.     if(file->prevFileInQueue != NULL && file->nextFileInQueue == NULL)
  324.         return;
  325.  
  326.     // First and not only
  327.     if(file->prevFileInQueue == NULL && file->nextFileInQueue != NULL){
  328.         evictQueue->leastRecent = file->nextFileInQueue;
  329.         file->nextFileInQueue->prevFileInQueue = NULL;
  330.     }
  331.     // Middle
  332.     else if(file->prevFileInQueue != NULL && file->nextFileInQueue != NULL){
  333.         file->nextFileInQueue->prevFileInQueue = file->prevFileInQueue;
  334.         file->prevFileInQueue->nextFileInQueue = file->nextFileInQueue;
  335.     }
  336.  
  337.     file->nextFileInQueue = NULL;
  338.     file->prevFileInQueue = NULL;
  339.  
  340.     if(evictQueue->leastRecent == NULL){
  341.         evictQueue->leastRecent = file;
  342.         file->nextFileInQueue = NULL;
  343.         file->prevFileInQueue = NULL;
  344.     }else{        
  345.         struct file * fileIter = evictQueue->leastRecent;
  346.         while(fileIter->nextFileInQueue != NULL){
  347.             fileIter = fileIter->nextFileInQueue;
  348.         }
  349.         fileIter->nextFileInQueue = file;
  350.         file->prevFileInQueue = fileIter;
  351.     }
  352.  
  353. }
  354. // Read file
  355. void* handler(void* sv){
  356.  
  357.     struct server* s = (struct server*)sv;
  358.    
  359.     while(1){
  360.  
  361.         pthread_mutex_lock(lock);
  362.  
  363.         while(in == out){
  364.             pthread_cond_wait(cvEmpty, lock);
  365.             if(s->exiting == 1){
  366.                 pthread_mutex_unlock(lock);
  367.                 pthread_exit(0);
  368.             }
  369.         }
  370.  
  371.         int connfd = buffer[out];
  372.  
  373.         if ((in - out + s->max_requests + 1) % (s->max_requests + 1) == s->max_requests)
  374.             pthread_cond_broadcast(cvFull);
  375.  
  376.         out = (out + 1)%(s->max_requests + 1);
  377.  
  378.         pthread_mutex_unlock(lock);
  379.  
  380.         do_server_request(s, connfd);
  381.     }
  382.     return NULL;
  383. }
  384.  
  385. struct server *
  386. server_init(int nr_threads, int max_requests, int max_cache_size)
  387. {
  388.     struct server *sv;
  389.  
  390.     sv = Malloc(sizeof(struct server));
  391.     sv->nr_threads = nr_threads;
  392.     sv->max_requests = max_requests;
  393.     sv->max_cache_size = max_cache_size;
  394.     sv->exiting = 0;
  395.    
  396.     if (nr_threads > 0 || max_requests > 0 || max_cache_size > 0) {
  397.  
  398.         threadPool = malloc(sizeof(pthread_t)* sv->nr_threads);
  399.         in = 0;
  400.         out = 0;
  401.        
  402.         lock = malloc(sizeof(pthread_mutex_t));
  403.         pthread_mutex_init(lock, NULL);
  404.        
  405.         fileLock = malloc(sizeof(pthread_mutex_t));
  406.         pthread_mutex_init(fileLock, NULL);
  407.  
  408.         cvFull = malloc(sizeof(pthread_cond_t));
  409.         pthread_cond_init(cvFull, NULL);
  410.        
  411.         cvEmpty = malloc(sizeof(pthread_cond_t));
  412.         pthread_cond_init(cvEmpty, NULL);
  413.  
  414.         if(max_requests > 0){
  415.             buffer = Malloc((max_requests + 1) * sizeof(int));
  416.             for(int i = 0; i < max_requests + 1; i++)
  417.                 buffer[i] = -1;
  418.         }
  419.         if(nr_threads > 0){
  420.             for(int i = 0; i < nr_threads; i++)
  421.                 pthread_create(&threadPool[i], NULL, handler, (void*)sv);
  422.         }
  423.  
  424.         if(max_cache_size > 0){
  425.             fileCache = malloc(sizeof(struct fileCache));
  426.             fileCache->size = 0;
  427.             fileCache->maxSize = max_cache_size;
  428.             fileCache->files = malloc(sizeof(struct file *) * ((fileCache->maxSize / 12228) * 2 + 5));
  429.             evictQueue = malloc(sizeof(struct evictQueue));
  430.             evictQueue->leastRecent = NULL;
  431.             evictQueue->mostRecent = NULL;
  432.         }
  433.     }
  434.  
  435.     /* Lab 4: create queue of max_request size when max_requests > 0 */
  436.  
  437.     /* Lab 5: init server cache and limit its size to max_cache_size */
  438.  
  439.     /* Lab 4: create worker threads when nr_threads > 0 */
  440.  
  441.     return sv;
  442. }
  443.  
  444. // Write file
  445. void server_request(struct server *sv, int connfd)
  446. {
  447.     if (sv->nr_threads == 0) { /* no worker threads */
  448.         do_server_request(sv, connfd);
  449.     } else {
  450.         /*  Save the relevant info in a buffer and have one of the
  451.          *  worker threads do the work. */
  452.         pthread_mutex_lock(lock);
  453.  
  454.         while((in - out + sv->max_requests + 1)%(sv->max_requests + 1) == sv->max_requests){
  455.             pthread_cond_wait(cvFull, lock);
  456.         }
  457.  
  458.         buffer[in] = connfd;
  459.  
  460.         if(in == out){
  461.             pthread_cond_broadcast(cvEmpty);
  462.         }
  463.  
  464.         in = (in + 1)%(sv->max_requests + 1);
  465.  
  466.         pthread_mutex_unlock(lock);
  467.  
  468.     }
  469. }
  470.  
  471. void
  472. server_exit(struct server *sv)
  473. {
  474.     /* when using one or more worker threads, use sv->exiting to indicate to
  475.      * these threads that the server is exiting. make sure to call
  476.      * pthread_join in this function so that the main server thread waits
  477.      * for all the worker threads to exit before exiting. */
  478.     sv->exiting = 1;
  479.  
  480.     pthread_cond_broadcast(cvEmpty);
  481.  
  482.     for(int i = 0; i< sv->nr_threads; i++)
  483.         pthread_join(threadPool[i], NULL);
  484.  
  485.     if(sv->max_requests > 0) free(buffer);
  486.     if(sv->nr_threads > 0)free(threadPool);
  487.     if(sv->max_cache_size > 0){
  488.         pthread_mutex_lock(fileLock);
  489.         cacheEvict(sv->max_cache_size);
  490.         pthread_mutex_unlock(fileLock);
  491.         free(fileCache);
  492.         free(evictQueue);    
  493.     }
  494.     free(cvEmpty);
  495.     free(cvFull);
  496.     free(lock);
  497.  
  498.     /* make sure to free any allocated resources */
  499.     free(sv);
  500. }
  501.  
  502. unsigned long hash(char *str){
  503.    
  504.     int size = (fileCache->maxSize / 12228) * 2 + 5;
  505.  
  506.     unsigned long hash = 5381;
  507.     int c;
  508.     while((c = *str++))
  509.         hash = ((hash << 5) + hash) + c;
  510.  
  511.     return hash % (size);
  512. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top